Русская Википедия:Марковский процесс принятия решений

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Марковский процесс принятия решений (МППР, Шаблон:Lang-en) — математический формализм для марковского дискретного стохастического процесса управления, основа для моделирования последовательного принятия решений в ситуациях, где результаты частично случайны и частично зависят от лица, принимающего решения. МППР используется во множестве областей, включая робототехнику, автоматизированное управление, экономику и производство. Подход обучения с подкреплениями, основанный на данной модели, применяется, например, в нейронной сети AlphaZero.

Определение

Файл:Markov diagram v2.svg

Диаграмма обучения с подкреплением в МППРШаблон:Sfn

Файл:Markov Decision Process example.png

Пример МППР с 3 состояниями и 2 действиями

Марковские процессы принятия решений представляют собой инструмент для постановки задачи обучения, где достижение цели осуществляется через взаимодействие и последовательное принятие решений. Окружающая среда (или просто среда), представляет собой сторону, с которой взаимодействует агент. Агент выбирает действия, в то время как среда реагирует на эти действия и предоставляет новые ситуации для агента. Кроме того, среда генерирует вознаграждения — числовые значения, которые агент стремится максимизировать с течением времени путем выбора действий. Инженерам будут более понятны термины: агент — устройство управления или контроллер, среда — управляемая система, действие — управляющий сигнал.Шаблон:Sfn

Формально определить марковский процесс принятия решений можно, задав 4-кортеж <math>(S,A,P_\cdot(\cdot,\cdot),R_\cdot(\cdot,\cdot))</math>, гдеШаблон:Sfn

• <math>S</math> — конечное множество состояний среды, из которых агент наблюдает <math>S_t \in S</math> в момент времени <math>t = 0, 1, 2 \dots</math>,
• <math>A(s)</math> — конечное множество действий, доступных из состояния <math>s</math>, из которых агент может выбрать для момента времени <math>t</math> действие <math>A_t \in A(s)</math>,
• <math>P_a(s,s') = \Pr(s_{t+1}=s' \mid s_t = s, a_t=a)</math> — вероятность перехода состояний. То есть, вероятность того, что действие <math>a</math> в состоянии <math>s</math> в момент времени <math>t</math> приведёт в состояние <math>s'</math> в момент <math>t+1</math>,
• <math>R_a(s,s')</math> вознаграждение, получаемое после перехода в состояние <math>s'</math> из состояния <math>s</math> при совершении действия <math>a</math>.

Совместно агент и среда порождают траекторию <math>S_0, A_0, R_0, S_1, A_1, R_1,\dots</math>.

Стратегия <math>\pi</math> — функция (в общем случае распределение вероятностей), сопоставляющая состоянию действие. При наличии такой функции МППР можно рассматривать как Марковскую цепь.

Формализм марковских процессов принятия решений является важной абстракцией задачи обучения целеустремленного агента в процессе взаимодействия. Он позволяет утверждает, что независимо от деталей механизмов восприятия, памяти и управления, а также от цели, которую преследует агент, любая задача обучения целенаправленному поведению может быть сведена к трем сигналам, которыми агент обменивается с окружающей средой: сигнал, представляющий выбор агента (действие), сигнал причины такого выбора (состояние среды), и сигнал, определяющий цель агента (вознаграждение). Этот формализм не всегда достаточен для описания всех задач обучения принятию решений, но он широко применяется и полезен.Шаблон:Sfn

Цель оптимизации

Решить марковский процесс принятия решений означает найти оптимальную стратегию, максимизирующую вознаграждение (функцию ценности). Самая простая функция ценности — это математическое ожидание формального ряда <math>E\left[\sum^{\infty}_{t=0} {R_{a_t} (s_t, s_{t+1})}\right]</math>, где <math>a_t = \pi(s_t)</math>, а математическое ожидание берётся в соответствии с распределением вероятности <math>s_{t+1} \sim P_{a_t}(s_t, .)</math>, но такую функцию можно использовать только если ряд сходится всегда, что обычно означает наличие конечного состояния МППР — такого, что <math>P_{a}(s, s) = 1</math> и <math>R_a(s, s) = 0</math>. Если же сходимость ряда не гарантируется, можно:

• Рассмотреть только конечное число слагаемых <math>E\left[\sum^{N}_{t=0} {R_{a_t} (s_t, s_{t+1})}\right]</math>
• Ввести <math>\gamma \in [0, 1]</math> — коэффициент обесценивания (дисконтирования) <math>E\left[\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})}\right]</math>, который контролирует предпочтение агентом мгновенных вознаграждений по сравнению с вознаграждениями в будущем

На практике второй вариант более гибкий, так как учитывает более долгосрочную перспективу и чаще используется именно он.

Для максимизации такого ряда вводят две функции:

• Функция полезности состояния <math>V_{\pi}(s) = E\left[\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})} \mid s_0 = s, a_t = {\pi}(s_t)\right]</math>, где математическое ожидание берётся в соответствии с распределением <math>s_{t+1} \sim P_{a_t}(s_t, .)</math>
• Функция полезности действия <math>Q_{\pi}(s, a) = E\left[\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})} \mid s_0 = s, a_0 = a, a_t = {\pi}(s_t) \; \forall t \geqslant 1 \right]</math>, где математическое ожидание берётся в соответствии с <math>s_{t+1} \sim P_{a_t}(s_t, .)</math>

А также их максимумы по всем стратегиям:

• <math>V_*(s) = \max\limits_{\pi}V_{\pi}(s)</math>
• <math>Q_*(s, a) = \max\limits_{\pi}Q_{\pi}(s, a)</math>

Можно доказать, что эти функции также являются функциями полезности состояния и полезности действия соответственно, а также, что они достигаются на детерминированной стратегии. Заметим, что по функции <math>Q_*</math> можно восстановить её стратегию, которая будет оптимальной.

Сравнение стратегий

Чтобы дать формальное определение оптимальной стратегии необходимо ввести отношение порядка на множестве стратегий. <math>\pi_1 \preccurlyeq \pi_2 \iff \forall V_{\pi_1}(s) \leqslant V_{\pi_2}(s),\; s \in S</math>. Наибольшая стратегия называется оптимальной.

Можно доказать, что оптимальная стратегия существует.

Алгоритмические реализации

Большинство алгоритмов марковских процессов принятия решений основаны на итерации уравнения Беллмана с фиксированной точкой. Примеры включают итерацию состояния среды (Шаблон:Lang-en), итерацию стратегии (Шаблон:Lang-en), метод временных разностей (Шаблон:Lang-en), Q-обучение и т. д. Анализ этих алгоритмов в табличном случае и случае линейной аппроксимации функции часто использует свойство сжатия оператора Беллмана. В последнее десятилетие нелинейные аппроксимации, такие как нейронные сети, стали более популярными. Однако для нелинейных аппроксимаций функций это свойство сжатия уже не выполняется, что часто приводит к нестабильности. Было предложено множество вариантов и модификаций для стабилизации обучения, например, DQN (Шаблон:Lang-en — «глубокая Q-сеть»), A3C (Шаблон:Lang-en — «агент-критик с асинхронным преимуществом»). Однако для этих алгоритмов по-прежнему отсутствуют теоретические гарантии.

Расширения

Дискретные марковские процессы принятия решений хорошо изучены. Существуют расширения для непрерывных состояний среды с линейной или нелинейной аппроксимацией функций, случаев частичной наблюдаемости (Шаблон:Lang-en), структурированных МППР (например, динамические байесовские сети Шаблон:Lang-en) и другие, но алгоритмы становятся намного менее устойчивыми.

См. также

• Теория игр

Литература

• Шаблон:Книга