Это был 1978 год. Математик, посвятивший годы изучению Марковского процесса принятия решений (MDP), посетил Рональда Ховарда и поинтересовался его областью применения. Рональд был профессором Стэнфорда, написавшим учебник по MDP в 1960-х годах. Рональд ответил, что знает очень мало практических применений MDP и нашел только одно в своей карьере, которое он считает успешным.
Математик расстроился. Затем они обсудили проблему больших требований к данным, налагаемых MDP. Это был 1978 год, поэтому данные были не так доступны, как сегодня.
Осознание того, что MDP неприменим, побудило Рональда продолжить его изучение. Однажды он попытался внедрить MDP для стратегии удержания потребителей в универмаге. Его модель работала превосходно, и он чувствовал себя потерянным из-за того, что «эта весьма полезная и общая модель принятия решений не нашла широкого применения».
Почему
История MDP или любой новой методологии — это путешествие в поисках «Почему?»: почему это важно? Почему он лучше старого метода? И так далее. Если «почему» понятно, то «как» легко.
Первоначальный «Почему» начался около 100 лет назад. Все началось с цепи Маркова, предшественницы MDP.
Русский математик Андрей Марков изучил роман Александра Пушкина Евгений Онегин. Его целью было изучить закономерности гласных и согласных в тексте. Этот анализ не изменил понимания и оценки поэмы Пушкина. Но разработанная им техника, известная теперь как цепь Маркова, расширила теорию вероятностей в новом направлении.
Во время Второй мировой войны цепь Маркова сыграла важную роль в теоретической и прикладной науке. К ним относятся расчет динамики газов, жидкостей и радиоактивных материалов в статистической физике.
Сегодня цепь Маркова по-прежнему актуальна в науке. Он помогает идентифицировать гены ДНК, оптимизировать поиск в Интернете и моделировать коллективное поведение взаимодействующих частиц, таких как электроны.
В отличие от MDP, цепь Маркова (или процесс Маркова) доказала свою применимость с момента своего создания.
Даже в 1985 году Дуглас Уайт все еще писал о MDP, что «было выявлено лишь несколько приложений, в которых были реализованы результаты». — приложения, использующие реальные данные, где результаты либо были реализованы, либо оказали явное влияние на решения.».
Марковский процесс принятия решений (MDP)
Чтобы понять MDP, мы должны взглянуть на его основные компоненты.
Свойство Маркова утверждает, что текущее состояние является достаточным предиктором будущего. Текущее состояние фиксирует всю соответствующую информацию из прошлого. Так что, как только это станет известно, история может быть выброшена.
Цепь Маркова — это система, обладающая марковским свойством. В цепи Маркова система должна иметь различные состояния с идентифицируемыми переходами.
В Марковский процесс принятия решений (MDP) включены дополнительные компоненты, такие как вознаграждения и действия. Структура MDP является абстрактной и гибкой, что позволяет применять ее для решения множества различных задач.
Ответ на вопрос «Почему?»
MDP имеет значение, потому что формализует последовательное принятие решений для структурирования проблем. В отличие от цепи Маркова, MDP рассматривает действия и вознаграждения, которые можно решить с помощью обучения с подкреплением.
Рассмотрим заявление Дэвида Сильвера, руководителя группы обучения с подкреплением (RL) в Deepmind, который сказал, что каждую проблему RL можно сформулировать как марковский процесс принятия решений. MDP — универсальное решение проблем с RL. С ростом объема данных и продвижением технологий к глубокому обучению мы обнаружим больше приложений MDP.
В настоящее время MDP имеет обширный список приложений, начиная от сбора урожая, робототехники и заканчивая финансами.
В 2002 году, более чем через двадцать лет после встречи со своим другом-математиком, Рональд Ховард так прокомментировал MDP: «Очень приятно видеть, как технический прогресс повысил практичность решения задач в этой области».
