Траектория «Обучение с подкреплением» · конспект 3 из 12

Марковские процессы принятия решений

О чём эта тема: Математический фундамент всей траектории: марковское свойство, формальное определение MDP, функции ценности состояния и действия и уравнение Беллмана — с выводами, вплоть до доказательства существования и единственности решения через принцип сжимающих отображений. По конспектам преподавателя и лекции 2 курса «RL: от бандитов до RLHF» (мехмат МГУ).
Аннотация: Конспект начинается с марковского свойства и примера марковского процесса — управления двигателем. Затем даётся строгое определение марковского процесса принятия решений: множества состояний и действий, функция динамики среды с её нормировкой, и выводятся производные характеристики — вероятности переходов и ожидаемые награды. Далее доказывается рекурсивное свойство возврата, вводятся функции ценности состояния и действия при фиксированной политике и доказывается связь между ними; обсуждаются сравнение политик и единственность оптимальной функции ценности. Центральная часть — уравнение Беллмана: сначала доказывается свойство одного перехода, из него выводится само уравнение, а затем вводится оператор Беллмана и доказывается, что он является γ-сжатием, — по теореме Банаха уравнение имеет единственное решение, и итерации оператора сходятся к нему из любого начального приближения. Этот факт проверяется руками в интерактивном тренажёре на MDP «двигатель» и станет основой методов следующего конспекта.
Пререквизиты: Конспект 1 (агент, среда, политика, возврат, дисконтирование), конспект 2 (ценность действия, угловые скобки как математическое ожидание). Из математики: условная вероятность, формула полной вероятности, условное математическое ожидание, геометрическая прогрессия; для раздела 6 — понятие нормы и сходимости последовательности.
Мотивация: В конспекте 1 ценности состояний считались перебором всех траекторий — для дерева из семи состояний это работало, но у FrozenLake 16 состояний и бесконечные траектории со случайными скольжениями, а у шахмат состояний больше, чем атомов во Вселенной. Уравнение Беллмана заменяет перебор траекторий на систему уравнений «один шаг вперёд»: ценность состояния выражается через ценности соседних. Почти всё дальнейшее — динамическое программирование, TD-обучение, Q-обучение, DQN — способы решать это уравнение в разных условиях.

1. Марковское свойство

Марковский процесс — случайный процесс, для которого вероятностные характеристики будущего зависят только от состояния в данный момент и не зависят от того, когда и как система пришла в это состояние. Коротко: будущее зависит от прошлого только через настоящее.

Граф марковского процесса из четырёх состояний со стрелками переходов и вероятностями на рёбрах — Марковский процесс как граф: вершины — состояния, рёбра — переходы с вероятностями; сумма вероятностей исходящих рёбер каждой вершины равна 1. Из презентации курса

Пример из презентации курса: управление двигателем. Двигатель имеет состояния холодный, горячий и перегретый; при разгоне он нагревается, при замедлении — остывает, при неправильном управлении — перегревается. Связав состояния через действия «разгон» и «замедление» и задав вероятности переходов, получаем марковский процесс, управляемый агентом:

Схема управления двигателем: состояния холодный, горячий и перегретый, переходы по действиям разгон и замедление с вероятностями — Управляемый марковский процесс «двигатель»: разгон греет, замедление остужает. Из презентации курса

Марковское свойство — не безобидная формальность, а требование к тому, что считать состоянием. Наблюдение CartPole без скоростей (конспект 1) марковским состоянием не является: по одному кадру будущее не определено. Добавив скорости — или пару последовательных кадров, — состояние снова становится марковским. Умение «доупаковать» наблюдение до марковского состояния — часть постановки задачи.

2. Определение MDP

Марковский процесс принятия решений (англ. Markov Decision Process, MDP) — четвёрка

\[ \mathcal{M} = \bigl( \mathcal{S},\; \{\mathcal{A}(s)\}_{s \in \mathcal{S}},\; p,\; \gamma \bigr), \tag{3.1}\]

где \(\mathcal{S}\) — конечное множество состояний; \(\mathcal{A}(s)\) — конечное множество действий, доступных в состоянии \(s\); \(\gamma \in [0, 1)\) — коэффициент дисконтирования; \(p(s', r \,|\, s, a)\) — функция динамики среды: вероятность того, что после действия \(a\) в состоянии \(s\) среда перейдёт в состояние \(s'\) и выдаст награду \(r\) (награды считаем ограниченными: \(|r| \le R_{\max}\)). Динамика должна удовлетворять двум условиям: нормировке

\[ \sum_{s' \in \mathcal{S}} \sum_{r} p(s', r \,|\, s, a) = 1 \qquad \forall s, a, \tag{3.2}\]

и марковскому свойству — распределение следующего шага зависит только от текущей пары «состояние, действие», а не от всей истории:

\[ P\bigl(S_{t+1} = s', R_{t+1} = r \,\big|\, S_t, A_t, S_{t-1}, A_{t-1}, \ldots\bigr) = P\bigl(S_{t+1} = s', R_{t+1} = r \,\big|\, S_t, A_t\bigr). \tag{3.3}\]

Из полной динамики выводятся производные характеристики. Суммирование по наградам даёт вероятности переходов, а взвешивание наград — их ожидание:

\[ p(s' \,|\, s, a) = \sum_{r} p(s', r \,|\, s, a), \qquad r(s, a) = \bigl\langle R_{t+1} \,\big|\, s, a \bigr\rangle = \sum_{s'} \sum_{r} r\, p(s', r \,|\, s, a) \tag{3.4}\]

(второе равенство — определение математического ожидания, расписанное по совместному распределению; в непрерывных пространствах суммы заменяются интегралами). Политика \(\pi(a \,|\, s)\), напомним из конспекта 1, — распределение на действиях в каждом состоянии; если в каждом состоянии одно действие выбирается с вероятностью 1, политика детерминированная.

Задачи делятся на эпизодические (есть терминальный момент \(T\): FrozenLake, CartPole) и продолжающиеся (взаимодействие бесконечно: управление роботом, рекомендательная система). Для продолжающихся задач условие \(\gamma < 1\) обязательно: при постоянной награде \(R_t = c\) возврат равен геометрическому ряду \(G_t = c \sum_k \gamma^k = c/(1-\gamma)\), конечному только при \(\gamma < 1\).

3. Возврат и его рекурсия

Дисконтированный возврат был введён в конспекте 1, формула (1.2): \(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\). Докажем его ключевое рекурсивное свойство, на котором держится всё дальнейшее.

Теорема (рекурсия возврата).

\[ G_t = R_{t+1} + \gamma\, G_{t+1}. \tag{3.5}\]

Доказательство. Вынесем из определения первый член и общий множитель \(\gamma\) из остальных:

\[ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots = R_{t+1} + \gamma \bigl( R_{t+2} + \gamma R_{t+3} + \ldots \bigr) = R_{t+1} + \gamma\, G_{t+1}. \;\blacksquare \]

Смысл: возврат «сегодня» — это награда за один шаг плюс дисконтированный возврат «завтра». Рекурсия (3.5) превращает бесконечную сумму в соотношение между соседними моментами времени — именно она позволит записать уравнение Беллмана.

4. Функции ценности

Зафиксируем политику \(\pi\). Функция ценности состояния и функция ценности действия — ожидаемые возвраты при условии старта из состояния (и действия):

\[ V^{\pi}(s) = \bigl\langle G_t \,\big|\, S_t = s \bigr\rangle_{\pi}, \qquad Q^{\pi}(s, a) = \bigl\langle G_t \,\big|\, S_t = s,\, A_t = a \bigr\rangle_{\pi}. \tag{3.6}\]

Утверждение (связь V и Q). Для любых \(\pi\) и \(s\)

\[ V^{\pi}(s) = \sum_{a \in \mathcal{A}(s)} \pi(a \,|\, s)\, Q^{\pi}(s, a). \tag{3.7}\]

Доказательство. По формуле полной вероятности относительно значения действия \(A_t\):

\[ V^{\pi}(s) = \sum_{a} P_{\pi}(A_t = a \,|\, S_t = s)\, \bigl\langle G_t \,\big|\, S_t = s, A_t = a \bigr\rangle_{\pi} = \sum_{a} \pi(a \,|\, s)\, Q^{\pi}(s, a). \;\blacksquare \]

Ценность состояния — средняя ценность доступных действий, взвешенная политикой. Политики сравниваются поточечно: \(\pi'\) не хуже \(\pi\), если \(V^{\pi'}(s) \ge V^{\pi}(s)\) во всех состояниях. Оптимальные функции ценности — точные верхние грани по всем политикам:

\[ V^*(s) = \sup_{\pi} V^{\pi}(s), \qquad Q^*(s, a) = \sup_{\pi} Q^{\pi}(s, a), \tag{3.8}\]

а политика оптимальна, если её ценность совпадает с \(V^*\) всюду. Оптимальных политик может быть много (если два действия равноценны, любой их выбор оптимален), но оптимальная функция ценности единственна: у любых двух оптимальных политик \(V^{\pi_1} = V^{\pi_2} = V^*\) по определению (3.8). Зная \(Q^*\), оптимально действовать жадно: \(a^*(s) \in \arg\max_a Q^*(s, a)\) и \(V^*(s) = \max_a Q^*(s, a)\) — поэтому многие методы траектории будут искать не политику, а именно \(Q^*\).

5. Уравнение Беллмана

Соединим рекурсию возврата (3.5) с определениями ценностей.

Теорема (свойство одного перехода). Для любой политики \(\pi\) и состояния \(s\)

\[ V^{\pi}(s) = \bigl\langle R_{t+1} + \gamma\, V^{\pi}(S_{t+1}) \,\big|\, S_t = s \bigr\rangle_{\pi}. \tag{3.9}\]

Доказательство. Подставим (3.5) в определение (3.6) и воспользуемся линейностью условного ожидания:

\[ V^{\pi}(s) = \bigl\langle R_{t+1} + \gamma G_{t+1} \,\big|\, S_t = s \bigr\rangle_{\pi} = \bigl\langle R_{t+1} \,\big|\, s \bigr\rangle_{\pi} + \gamma\, \bigl\langle G_{t+1} \,\big|\, s \bigr\rangle_{\pi}. \]

Ко второму слагаемому применим формулу повторного ожидания, обусловив по \(S_{t+1}\): внутреннее ожидание \(\langle G_{t+1} | S_{t+1} \rangle_\pi\) — это по определению \(V^{\pi}(S_{t+1})\) (здесь работает марковское свойство (3.3): будущий возврат зависит от прошлого только через \(S_{t+1}\)). Получаем (3.9). ∎

Теорема (уравнение Беллмана для \(V^\pi\)). Раскрывая ожидание в (3.9) сначала по действию (с весами \(\pi(a|s)\)), затем по паре \((s', r)\) (с весами \(p(s', r | s, a)\)):

\[ V^{\pi}(s) = \sum_{a} \pi(a \,|\, s) \sum_{s'} \sum_{r} p(s', r \,|\, s, a) \bigl[ r + \gamma\, V^{\pi}(s') \bigr]. \tag{3.10}\]

Аналогичное раскрытие для ценности действия (первый шаг уже сделан — действие \(a\) фиксировано, усреднять по политике нужно только следующее действие \(a'\)):

\[ Q^{\pi}(s, a) = \sum_{s'} \sum_{r} p(s', r \,|\, s, a) \Bigl[ r + \gamma \sum_{a'} \pi(a' \,|\, s')\, Q^{\pi}(s', a') \Bigr]. \tag{3.11}\]

Уравнение (3.10) — система из \(|\mathcal{S}|\) линейных уравнений с \(|\mathcal{S}|\) неизвестными \(V^\pi(s)\): никакого перебора траекторий, ценность каждого состояния выражена через ценности соседей на один шаг вперёд.

Разобранный пример (из лекции курса). В состоянии \(s\) два действия. Действие \(a_1\): с вероятностью 0,7 — переход в \(s_1\) с наградой 2, с вероятностью 0,3 — в \(s_2\) с наградой 0. Действие \(a_2\): с вероятностью 1 — в \(s_3\) с наградой 1. Известно \(V^\pi(s_1) = 5\), \(V^\pi(s_2) = 1\), \(V^\pi(s_3) = 4\), \(\gamma = 0{,}9\). По (3.11):

\[ Q^{\pi}(s, a_1) = 0{,}7\,(2 + 0{,}9 \cdot 5) + 0{,}3\,(0 + 0{,}9 \cdot 1) = 4{,}82, \qquad Q^{\pi}(s, a_2) = 1 + 0{,}9 \cdot 4 = 4{,}6. \]

Если политика выбирает \(a_1\) с вероятностью 0,4 и \(a_2\) с вероятностью 0,6, то по (3.7) \(V^{\pi}(s) = 0{,}4 \cdot 4{,}82 + 0{,}6 \cdot 4{,}6 = 4{,}688\). Жадный выбор действия дал бы \(\max(4{,}82;\, 4{,}6) = 4{,}82\) — жадное улучшение политики поднимает ценность состояния; этот эффект станет главным героем следующего конспекта.

Типичная ошибка В уравнении Беллмана дисконтируют и немедленную награду: пишут \(\gamma(r + V(s'))\) вместо \(r + \gamma V(s')\). Дисконт применяется только к будущим наградам — награда текущего шага входит с весом 1, что видно из рекурсии (3.5): множитель \(\gamma\) стоит перед \(G_{t+1}\), а не перед \(R_{t+1}\).

6. Оператор Беллмана и неподвижная точка

Правая часть уравнения (3.10) — рецепт: возьми любую функцию \(V\), подставь, получи новую функцию. Это определяет оператор Беллмана:

\[ (\mathcal{B}^{\pi} V)(s) = \sum_{a} \pi(a \,|\, s) \sum_{s'} \sum_{r} p(s', r \,|\, s, a) \bigl[ r + \gamma\, V(s') \bigr], \tag{3.12}\]

а уравнение Беллмана — в одну строку: \(V^{\pi} = \mathcal{B}^{\pi} V^{\pi}\), то есть \(V^\pi\) — неподвижная точка оператора. Почему решение существует, единственно, и как его найти? Ответ даёт следующая лемма.

Лемма (γ-сжатие). Для любых ограниченных функций \(V, W\) в равномерной норме \(\|V\|_\infty = \max_s |V(s)|\):

\[ \bigl\| \mathcal{B}^{\pi} V - \mathcal{B}^{\pi} W \bigr\|_{\infty} \;\le\; \gamma\, \bigl\| V - W \bigr\|_{\infty}. \tag{3.13}\]

Доказательство. Награды \(r\) в (3.12) не зависят от \(V\) и при вычитании сокращаются:

\[ (\mathcal{B}^{\pi} V)(s) - (\mathcal{B}^{\pi} W)(s) = \gamma \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a)\, \bigl[ V(s') - W(s') \bigr]. \]

Каждая разность под суммой не превосходит по модулю \(\|V - W\|_\infty\), а веса \(\pi(a|s)\, p(s', r|s, a)\) неотрицательны и в сумме дают 1 (нормировки политики и (3.2)) — значит, модуль всей правой части не превосходит \(\gamma \|V - W\|_\infty\) при каждом \(s\). Максимум по \(s\) даёт (3.13). ∎

По теореме Банаха о неподвижной точке сжимающее отображение полного пространства имеет ровно одну неподвижную точку, и последовательность \(V_{k+1} = \mathcal{B}^\pi V_k\) сходится к ней из любого начального приближения, причём ошибка убывает геометрически:

\[ \bigl\| V_k - V^{\pi} \bigr\|_{\infty} \;\le\; \gamma^k\, \bigl\| V_0 - V^{\pi} \bigr\|_{\infty}. \tag{3.14}\]

Это не абстракция, а готовый алгоритм: «начни с нулей и повторяй одношаговый прогноз» — в следующем конспекте он появится под именем итеративной оценки политики. Проверим сжатие руками.

Тренажёр: неподвижная точка оператора Беллмана

состояние, действие	переход	награда
холодный, разгон	→ горячий	+2
холодный, замедление	→ холодный	+1
горячий, разгон	0.5 → горячий · 0.5 → перегрев (терминал)	+2 · −10
горячий, замедление	→ холодный	+1

π(разгон | холодный) π(разгон | горячий) γ

сходимость итераций к неподвижной точке

MDP «двигатель» по мотивам примера из презентации (числа иллюстративные): перегрев — терминальное состояние с V = 0. Точное решение V* найдено из линейной системы (3.10); каждый «шаг оператора» применяет (3.12) к текущему V. На логарифмическом графике ошибка ложится на прямую — это и есть геометрическая сходимость (3.14) со знаменателем γ (сравните наклон при γ = 0.9 и γ = 0.6). Попробуйте найти политику с максимальными ценностями: всегда «газовать» — провал (перегрев), полезно разгоняться из холодного и остывать из горячего.

Типичная ошибка Думают, что итерации оператора Беллмана сходятся только из «хорошего» начального приближения. Сжатие (3.13) гарантирует сходимость из любого начального V — важна не стартовая точка, а коэффициент γ: чем он ближе к 1, тем медленнее сходимость (ошибка убывает как γ^k), что видно в тренажёре.

7. Уравнение Беллмана в коде

Вся математика конспекта умещается в двадцать строк numpy. Начнём с предельного случая из конспекта преподавателя — марковской цепочки без действий: среда сама переходит из состояния \(i\) в состояние \(j\) с вероятностью \(P_{ij}\), награда \(r_j\) начисляется за попадание в состояние \(j\). Уравнение Беллмана (3.10) теряет сумму по действиям:

\[ V_i = \sum_{j} P_{ij}\,\bigl( r_j + \gamma\, V_j \bigr), \tag{3.15}\]

Одношаговая схема усреднения: из состояния i стрелки с вероятностями ведут в состояния с наградами и ценностями — Смысл (3.15): награды соседей плюс их дисконтированные ценности, взвешенные вероятностями переходов. Из конспекта преподавателя

а в матричной записи \(V = P\,(r + \gamma V)\) решается в одну строку:

\[ (1 - \gamma P)\, V = P\, r \quad\Longrightarrow\quad V = (1 - \gamma P)^{-1} P\, r. \tag{3.16}\]

Пример из конспекта преподавателя: шесть состояний, из них 3 и 4 — терминальные, а состояние 5 — «фиктивное»: попав в него, среда остаётся там навсегда с нулевой наградой (удобный приём, чтобы терминальные состояния не выпадали из матричной записи):

Граф марковской цепочки: шесть состояний с вероятностями переходов на стрелках и наградами возле состояний, терминальные состояния закрашены — Марковская цепочка: вероятности — на стрелках, награды — возле состояний. Из конспекта преподавателя

import numpy as np
from numpy.linalg import inv

r = np.array([2., -1.,  1., -4.,  8.,  0.])      # награды за попадание в состояние
P = np.array([[0.,  0.6, 0.,  0.4, 0.,  0. ],
              [0.,  0.4, 0.5, 0.,  0.1, 0. ],
              [0.7, 0.,  0.,  0.2, 0.1, 0. ],
              [0.,  0.,  0.,  0.,  0.,  1.0],
              [0.,  0.,  0.,  0.,  0.,  1.0],
              [0.,  0.,  0.,  0.,  0.,  1.0]])

np.sum(P, axis=1)      # проверка нормировки (3.2): [1. 1. 1. 1. 1. 1.]

gamma = 0.9
V = np.dot(inv(np.eye(len(r)) - gamma * P), np.dot(P, r))   # формула (3.16)
# V = [-1.195  1.861  0.647  0.  0.  0.]

Ценности терминальных состояний нулевые — из них будущих наград нет. Самое «дорогое» состояние — 1 (рядом выигрышное состояние 4 с наградой 8), самое невыгодное — 0 (рядом проигрышное 3). Заметьте: состояние 1 ценно, хотя его собственная награда отрицательна, — ценность смотрит вперёд, а не на сиюминутную награду.

Теперь общий случай с действиями и политикой. Пусть \(\pi_{i\alpha}\) — вероятность действия \(\alpha\) в состоянии \(i\), а \(P_{i\alpha j}\) — вероятность перехода \(i \to j\) при действии \(\alpha\). Усреднение по политике сворачивает MDP в цепочку с эффективными переходами

\[ \tilde{P}_{ij} = \sum_{\alpha} \pi_{i\alpha}\, P_{i\alpha j}, \tag{3.17}\]

к которой применимо решение (3.16); ценности действий восстанавливаются по (3.11). Код из конспекта преподавателя (случайная среда: 10 состояний, 3 действия):

num_states, num_actions = 10, 3

# случайная политика: строки (состояния) нормированы на 1
pi = np.random.random((num_states, num_actions))
pi = pi / np.sum(pi, axis=1).reshape(-1, 1)

# случайная модель среды: P[i, a, j], нормировка по j
P = np.random.random((num_states, num_actions, num_states))
P = P / np.sum(P, axis=2).reshape(num_states, num_actions, 1)

r = np.linspace(-10, 10, num_states)                # награды состояний

# эффективные переходы (3.17): broadcasting (10,3,1)*(10,3,10) -> сумма по действиям
piP = np.sum(np.expand_dims(pi, axis=2) * P, axis=1)

V = np.dot(inv(np.eye(len(r)) - gamma * piP), np.dot(piP, r))  # формула (3.16)
Q = np.dot(P, r + gamma * V)                                   # формула (3.11)

# проверка связи (3.7): среднее Q по политике возвращает V
assert np.allclose(np.sum(pi * Q, axis=1), V)

Последняя строка — формула (3.7) в действии: связь \(V = \sum_a \pi\, Q\) выполняется машинно точно. Такие перекрёстные проверки — правильная привычка: каждая формула конспекта проверяема одной строкой кода.

Типичная ошибка Пытаются решать уравнение Беллмана обращением матрицы в среде с тысячами состояний: сложность обращения растёт как куб размера. Матричное решение (3.16) — инструмент учебных примеров и эталон для проверки; в больших задачах работает итерация оператора из раздела 6, а когда модель среды неизвестна — методы следующего конспекта.

Контрольные вопросы

Распределение следующего состояния и награды зависит только от текущей пары (состояние, действие), а не от всей истории — формула (3.3). По одному кадру CartPole (без скоростей) будущее не определено: стержень с одинаковым углом может падать влево или вправо. Состояние нужно дополнить — скоростями или вторым кадром.
Четвёрка (3.1): множество состояний, множества доступных действий, функция динамики p(s', r | s, a) и коэффициент дисконтирования γ. Динамика — совместное распределение следующего состояния и награды при условии текущих состояния и действия; из неё суммированием получаются вероятности переходов и ожидаемые награды (3.4).
G_t = R_{t+1} + γ(R_{t+2} + γR_{t+3} + …) = R_{t+1} + γG_{t+1} — формула (3.5), вынесение первого члена и множителя γ. Роль: превращает бесконечную сумму в соотношение соседних шагов, из которого выводится уравнение Беллмана.
V^π(s) = Σ_a π(a|s)Q^π(s,a) — формула (3.7): по формуле полной вероятности относительно выбранного действия, где P(A_t = a|S_t = s) = π(a|s), а условное ожидание возврата при известном действии — это Q^π(s,a). Ценность состояния — средняя ценность действий, взвешенная политикой.
В (3.10) неизвестные V^π(s) входят линейно с коэффициентами из политики и динамики; уравнений столько же, сколько состояний. Решение ровно одно: оператор Беллмана — γ-сжатие (лемма (3.13)), и по теореме Банаха неподвижная точка единственна.
Применение оператора Беллмана к двум функциям сближает их в равномерной норме не менее чем в γ раз (3.13). Следствия: решение уравнения Беллмана существует и единственно, а итерации V ← B^π V сходятся к нему из любого начального приближения с геометрической скоростью γ^k (3.14) — это готовый алгоритм вычисления V^π.
При известном Q* оптимально жадное действие argmax_a Q*(s,a) — сравнение чисел. Чтобы действовать жадно по V*, нужно заглянуть на шаг вперёд: перебрать действия и усреднить r + γV*(s') по динамике среды — то есть требуется модель p(s', r|s, a), которой у агента часто нет. Поэтому безмодельные методы учат именно Q.