MDP, отдача и функции ценности

Зачем это нужно

До сих пор модель училась на правильных ответах: у каждого примера был эталон, и loss измерял расстояние до него. Так устроены регрессия, классификация (ступень 2) и претрейн (ступени 4–5). Но для многих задач эталона нет, зато есть оценка: решила ли модель задачу, прошли ли тесты, понравился ли ответ человеку. Учиться по такой оценке — задача обучения с подкреплениемобучение с подкреплениемEN reinforcement learning (RL) (reinforcement learning, RL).

На RL стоит вся вторая половина ступени 6. RLHF в ChatGPT (урок 6.3.2) — это алгоритм PPO, GRPO в DeepSeek-R1 (урок 6.4.1) — его упрощение. В их формулах встречаются $\pi$, $V$, $Q$, $A$, $\gamma$, $\lambda$ и без подготовки читаются как шифр. Модуль 6.0 даёт эту подготовку на простых примерах, без языковых моделей:

• 6.0.1 (этот урок) — язык RL и планирование, когда правила среды известны: MDP, отдача, функции ценности, Беллман;
• 6.0.2 — обучение на собственном опыте, без знания правил: Монте-Карло, TD, Q-learning;
• 6.0.3 — градиент политики, actor-critic, GAE и PPO целиком, и как всё это переносится на LLM.

Что посмотреть параллельно

• Текст: Spinning Up от OpenAI, раздел Introduction to RL → Part 1: Key Concepts in RL. Читается за час, это тот же материал сжатым английским языком.
• Видео: лекции DeepMind × UCL 2021, лекция 3 «Markov Decision Processes and Dynamic Programming» (около полутора часов, на YouTube есть автоперевод субтитров).
• По-русски: Practical_RL ШАДа, неделя week02_value_based — слайды и семинар.
• Учебник: Саттон и Барто, главы 3–4 (бесплатный PDF на английском, есть платное русское издание).

Агент и среда

В RL два участника. АгентагентEN agentВ китайском встречается и «дайли» («посредник»), но в AI-контексте стандарт — «чжинэнти» (буквально «интеллектуальное тело»). принимает решения. Средасреда (в RL и для агентов)EN environmentТо, с чем взаимодействует агент — инструменты, песочница, симулятор пользователя — вместе с правилами выдачи награды. — всё остальное: она показывает агенту ситуацию и реагирует на его действия. Взаимодействие идёт по шагам:

flowchart LR
A["Агент: политика π"] -->|"действие a_t"| E["Среда"]
E -->|"новое состояние s_t+1"| A
E -->|"награда r_t"| A

Цикл обучения с подкреплением: агент действует, среда отвечает состоянием и наградой

На шаге $t$ агент видит состояниесостояние (в RL)EN stateВсё, что агенту нужно знать о ситуации, чтобы выбрать действие. У LLM — промпт плюс уже написанные токены. $s_t$, выбирает действиедействие (в RL)EN actionВыбор агента на шаге. У LLM действие — следующий токен. $a_t$, получает наградунаграда, вознаграждениеEN rewardЧисло, которым среда оценивает действие или весь ответ. У LLM обычно одна награда в конце ответа. $r_t$ (число, может быть нулём или отрицательным) и оказывается в состоянии $s_{t+1}$. Цепочка от старта до конца — эпизодэпизодEN episodeОдна партия взаимодействия от старта до конечного состояния. У LLM — один ответ до токена конца.. Лучше всего понятия видны на примерах:

Пример	Состояние	Действие	Награда	Конец эпизода
Дрессировка собаки	что сказал хозяин, где собака	сесть, лечь, подать лапу	лакомство или ничего	конец занятия
Робот-пылесос	карта комнаты, заряд батареи	ехать, повернуть, на базу	+1 за чистую клетку, −10 за разряд	батарея села или всё убрано
Шахматы	позиция на доске	ход	+1 победа, −1 поражение, только в конце	мат или ничья
Ответ LLM	промпт и уже написанные токены	следующий токен	оценка готового ответа	токен конца ответа

Чем RL отличается от обучения с учителем из урока 2.1.1:

1. Нет правильных ответов. Собаке не показывают «эталонную лапу», ей дают лакомство за результат.
2. Награда запаздывает. В шахматах ход на 10-й минуте мог решить партию, а награда пришла на 40-й. Понять, какое действие «заслужило» награду, — главная трудность RL (её называют распределением заслуг, credit assignment).
3. Агент сам выбирает свои данные. Что он увидит дальше, зависит от его действий. Плохая стратегия — плохие данные.

MDP: формальная модель среды

Чтобы считать, среду описывают марковским процессом принятия решениймарковский процесс принятия решений (MDP)EN Markov decision process (MDP)Пятёрка (S, A, P, R, γ): состояния, действия, вероятности переходов, награда и коэффициент дисконтирования. (Markov decision process, MDP). Это пять объектов:

• $S$ — множество состояний, $A$ — множество действий;
• $P(s' \mid s, a)$ — вероятность попасть в $s'$, если в $s$ выбрать $a$. Это условная вероятностьусловная вероятностьEN conditional probabilityP(A | B) = P(A ∩ B) / P(B) — вероятность A, если известно, что B произошло. В общем случае P(A | B) ≠ P(B | A). из урока 1.3.1;
• $R(s, a)$ — средняя награда за шаг: какое число в среднем получим, выбрав $a$ в $s$;
• $\gamma \in [0, 1]$ — коэффициент дисконтированиякоэффициент дисконтированияEN discount factorγ от 0 до 1: во сколько раз награда через шаг «дешевле» награды сейчас. Горизонт планирования ≈ 1/(1−γ)., о нём ниже.

Слово «марковский» означает марковское свойствомарковское свойствоEN Markov propertyБудущее зависит только от текущего состояния и действия, а не от всей предыстории.: будущее зависит только от текущего состояния и действия, а не от того, как мы сюда пришли. Вы встречали ту же идею в n-граммных моделях (урок 4.1.1): там следующий токен зависел только от нескольких предыдущих. Если в состояние положить всё нужное (у LLM — весь текущий контекст), свойство выполняется.

Переходы бывают детерминированными (из $s$ действием $a$ всегда в одно и то же $s'$) и случайными: робот на скользком полу иногда съезжает вбок. Задачи бывают эпизодическими (партия, ответ, уровень игры) и бесконечными (термостат, биржевой робот).

Сквозной пример — коридор. Три клетки: $A$, $B$ и выход. Действия — «влево» и «вправо». Из $A$ влево — стена, остаёмся в $A$. Из $B$ вправо — выход и награда $+1$, эпизод кончается. Все остальные награды нулевые.

flowchart LR
A["A"] -->|"вправо, r = 0"| B["B"]
A -->|"влево (стена), r = 0"| A
B -->|"влево, r = 0"| A
B -->|"вправо, r = +1"| X["Выход (конец)"]

Коридор: самая маленькая MDP, на которой видно всё, что будет дальше

Отдача и коэффициент дисконтирования

Агент максимизирует не награду за один шаг, а сумму будущих наград — отдачуотдача (return)EN returnG_t = r_t + γ r_{t+1} + γ² r_{t+2} + … — дисконтированная сумма наград от шага t до конца эпизода. (return):

$$G_t = r_t + \gamma\, r_{t+1} + \gamma^2\, r_{t+2} + \dots = \sum_{k=0}^{\infty} \gamma^k\, r_{t+k}$$

Как читать: отдача с шага $t$ — это награда сейчас плюс награда через шаг, умноженная на $\gamma$, плюс награда через два шага, умноженная на $\gamma^2$, и так далее. Если эпизод кончился, дальше стоят нули.

Главное свойство отдачи — рекурсия, на ней построен весь урок:

$$G_t = r_t + \gamma\, G_{t+1}$$

Пример. Эпизод из трёх шагов с наградами $[0, 0, 1]$ (до выхода три хода, награда в конце), $\gamma = 0.9$. Считаем с конца: $G_2 = 1$, $G_1 = 0 + 0.9 \cdot 1 = 0.9$, $G_0 = 0 + 0.9 \cdot 0.9 = 0.81$.

def returns(rewards, gamma):
    """Отдачи G_t для всех шагов эпизода: идём с конца, G_t = r_t + γ·G_{t+1}."""
    G, out = 0.0, []
    for r in reversed(rewards):
        G = r + gamma * G
        out.append(G)
    return out[::-1]


for gamma in [0.9, 0.5, 1.0]:
    print(gamma, [round(g, 3) for g in returns([0, 0, 1], gamma)])

0.9 [0.81, 0.9, 1.0]
0.5 [0.25, 0.5, 1.0]
1.0 [1.0, 1.0, 1.0]

Зачем дисконт. Три причины:

1. Конечность. В бесконечной задаче сумма наград может быть бесконечной. При $\gamma < 1$ и наградах не больше $r_{\max}$ отдача не больше $r_{\max}/(1-\gamma)$ — геометрическая прогрессия.
2. Синица в руках. Награда сейчас надёжнее награды потом: среда может измениться, эпизод — оборваться. Как с деньгами: рубль сегодня ценнее рубля через год.
3. Горизонт. Множитель $\gamma^k$ быстро тает, и агент фактически планирует примерно на $1/(1-\gamma)$ шагов вперёд.

$\gamma$	0	0.5	0.9	0.99	1
Горизонт $\approx 1/(1-\gamma)$	1 шаг	2 шага	10 шагов	100 шагов	весь эпизод
Поведение	думает только о текущем шаге	близорук	разумный баланс	дальновиден	только для конечных эпизодов

У языковых моделей эпизод конечен (ответ рано или поздно кончается), и в RLHF обычно берут $\gamma = 1$: награда за ответ одинаково важна для первого и для последнего токена.

Про индексы

Мы пишем $r_t$ для награды за действие $a_t$ — так в Spinning Up и в статьях про PPO и GAE. У Саттона и Барто та же награда обозначена $R_{t+1}$ («приходит на следующем шаге»). Формулы те же, сдвинут только индекс. Читая разные источники, проверяйте, какое соглашение принято.

Политика

Политикаполитика (стратегия агента)EN policy $\pi$ — правило выбора действий. Детерминированная политика — таблица «состояние → действие». Стохастическая — распределение $\pi(a \mid s)$: в коридоре можно идти вправо с вероятностью 0.5 и влево с вероятностью 0.5. Языковая модель — стохастическая политика: softmax над словарём даёт $\pi(\text{токен} \mid \text{контекст})$, а сэмплирование выбирает действие.

Цель RL — найти политику с максимальной средней отдачей: $J(\pi) = \mathbb{E}_\pi[G_0]$. Матожидание — потому что и политика, и среда случайны: одна и та же политика в разных эпизодах получает разную отдачу.

Функции ценности V и Q

Насколько хорошо находиться в состоянии $s$? Ответ зависит от того, как мы будем действовать дальше. Поэтому ценность всегда считают для конкретной политики.

Функция ценности состоянияфункция ценности состояния (V)EN state-value functionV^π(s) — средняя отдача, если стартовать из s и дальше действовать по политике π.:

$$V^\pi(s) = \mathbb{E}_\pi\big[\, G_t \mid s_t = s \,\big]$$

Как читать: средняя отдача, если стартовать из $s$ и дальше действовать по $\pi$. Это матожиданиематематическое ожидание (матожидание)EN expected value (expectation)E[X] = Σ x·p(x) — среднее значение «в долгую», центр тяжести распределения. из урока 1.3.1: сыграть из $s$ много эпизодов и усреднить отдачи.

Функция ценности действияфункция ценности действия (Q)EN action-value function (Q-function)Q^π(s, a) — средняя отдача, если в s выбрать действие a, а дальше действовать по π. уточняет первый шаг:

$$Q^\pi(s, a) = \mathbb{E}_\pi\big[\, G_t \mid s_t = s,\ a_t = a \,\big]$$

Как читать: средняя отдача, если в $s$ выбрать именно $a$, а дальше действовать по $\pi$. Связь между ними — обычное среднее: $V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a)$.

Разность называют преимуществомпреимущество (advantage)EN advantageA = r − b или A(s, a) = Q(s, a) − V(s): насколько действие лучше среднего в этой ситуации. (advantage):

$$A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)$$

Пример из жизни. Дорога на работу, награда — минус минуты в пути. Ваша привычка — 50/50 между метро и такси. Метро занимает в среднем 30 минут: $Q(\text{дом}, \text{метро}) = -30$. Такси — 20 минут: $Q(\text{дом}, \text{такси}) = -20$. Ценность утра «как обычно» $V(\text{дом}) = 0.5 \cdot (-30) + 0.5 \cdot (-20) = -25$. Преимущество такси $+5$, метро $-5$. Знак преимущества говорит, поднимать или опускать вероятность действия, — ровно это делают PPO и GRPO. Запомните формулу $A = Q - V$: в уроке 6.0.3 она станет сердцем алгоритма.

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

Как посчитать $V^\pi$, не играя миллион эпизодов? Подставим рекурсию $G_t = r_t + \gamma G_{t+1}$ в определение $V$. Матожидание суммы — сумма матожиданий, а среднее $G_{t+1}$ из следующего состояния — это $V^\pi(s_{t+1})$. Получаем уравнение Беллманауравнение БеллманаEN Bellman equationЦенность состояния = средняя немедленная награда + γ · средняя ценность следующего состояния.:

$$V^\pi(s) = \sum_a \pi(a \mid s) \Big[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s') \Big]$$

Как читать: ценность состояния = среднее по действиям политики от «немедленная награда + $\gamma$ × средняя ценность места, куда попадём». Выражение в квадратных скобках — это $Q^\pi(s, a)$. Так что уравнение говорит то же, что $V = \sum_a \pi Q$, только $Q$ расписано через $V$ следующего шага.

Это рекурсия, как функция, вызывающая саму себя (урок 0.2.2): ценность выражена через ценность. Метод, где большую задачу решают через подзадачи и переиспользуют их ответы, называют динамическим программированиемдинамическое программированиеEN dynamic programmingРешение задачи через ответы на подзадачи, которые хранятся и переиспользуются. В RL — методы для случая, когда модель среды известна.. Отсюда и название методов этого урока.

Решаем коридор руками

Политика случайная: 50/50, $\gamma = 0.9$, ценность выхода 0 (дальше наград нет). Пишем уравнение для каждой клетки:

$$\begin{aligned} V(A) &= 0.5 \cdot \big[0 + 0.9\, V(A)\big] + 0.5 \cdot \big[0 + 0.9\, V(B)\big] \quad &&\text{влево — стена, вправо — в } B \\ V(B) &= 0.5 \cdot \big[0 + 0.9\, V(A)\big] + 0.5 \cdot \big[1 + 0.9 \cdot 0\big] &&\text{влево — в } A \text{, вправо — выход} \end{aligned}$$

Из первого: $0.55\, V(A) = 0.45\, V(B)$, то есть $V(A) = \tfrac{9}{11} V(B)$. Подставляем во второе: $V(B) = 0.5 + 0.45 \cdot \tfrac{9}{11} V(B)$, откуда $V(B) = 110/139 \approx 0.791$ и $V(A) = 90/139 \approx 0.647$.

Теперь преимущества в $A$: $Q(A, \text{вправо}) = 0.9 \cdot 0.791 = 0.712$, $Q(A, \text{влево}) = 0.9 \cdot 0.647 = 0.583$. Средняя $V(A) = 0.647$, значит $A(A, \text{вправо}) = +0.065$, $A(A, \text{влево}) = -0.065$. В $B$ разница больше: $Q(B, \text{вправо}) = 1$, преимущество $+0.209$. Логично: в $B$ правильный выбор сразу приносит награду.

Решаем коридор итерациями

Систему из двух уравнений легко решить руками, из 10 тысяч — нет. Есть два компьютерных способа. Первый — записать уравнения как линейную систему $(I - \gamma P_\pi) V = R_\pi$ и вызвать np.linalg.solve (урок 1.1.2). Второй — итерации: начать с $V = 0$ и много раз подставлять текущую оценку в правую часть уравнения. Это называют оценкой политики (policy evaluation).

import numpy as np

gamma = 0.9
# Политика 50/50 в коридоре. Состояния: 0 = A, 1 = B (выход — ценность 0, его не храним).
P_pi = np.array([[0.5, 0.5],      # из A: 0.5 остаёмся (стена), 0.5 в B
                 [0.5, 0.0]])     # из B: 0.5 в A, 0.5 на выход
R_pi = np.array([0.0, 0.5])       # средняя награда за шаг: в B с вероятностью 0.5 получаем +1

V = np.zeros(2)
for k in range(1, 31):
    V = R_pi + gamma * P_pi @ V   # одна «подстановка» уравнения Беллмана
    if k in (1, 2, 3, 10, 30):
        print(k, V.round(4))
print("точно:", np.linalg.solve(np.eye(2) - gamma * P_pi, R_pi).round(4))

1 [0.  0.5]
2 [0.225 0.5  ]
3 [0.3262 0.6013]
10 [0.613  0.7701]
30 [0.6474 0.7913]
точно: [0.6475 0.7914]

Ценность «просачивается» от награды назад: после первой итерации её чувствует только $B$, после второй — и $A$. Каждая итерация уменьшает ошибку как минимум в $\gamma$ раз, поэтому процесс сходится к точному решению.

Оптимальность: уравнение Беллмана с максимумом

Нас интересует не любая политика, а лучшая. Её ценности обозначают $V^*$ и $Q^*$. Лучший агент в каждом состоянии выбирает лучшее действие, поэтому среднее по политике заменяется максимумом — получается уравнение оптимальности Беллманауравнение оптимальности БеллманаEN Bellman optimality equationТо же уравнение, но вместо усреднения по политике — максимум по действиям. Его решение — V* и Q*.:

$$V^*(s) = \max_a \Big[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^*(s') \Big], \qquad \pi^*(s) = \arg\max_a Q^*(s, a)$$

Как читать: ценность состояния при лучшей игре = ценность лучшего действия; лучшая политика — жадная по $Q^*$. В коридоре $V^*(B) = 1$ (сразу вправо), $V^*(A) = 0.9$ (вправо, вправо). Сравните со случайной политикой: 0.791 и 0.647.

Value iteration и policy iteration

Когда модель среды ($P$ и $R$) известна, оптимальную политику находят двумя классическими алгоритмами.

Итерация по ценностиитерация по ценности (value iteration)EN value iterationПовторять V(s) ← max_a Σ P(s′|s,a)[R + γV(s′)] до сходимости, затем взять жадную политику. (value iteration):

1. Начать с $V = 0$.
2. Для всех состояний сразу: $Q(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')$, затем $V(s) = \max_a Q(s, a)$.
3. Повторять, пока $V$ меняется больше допуска. В конце взять жадную политику $\arg\max_a Q(s, a)$.

В коридоре: после первой итерации $V = [0, 1]$, после второй $[0.9, 1]$, третья ничего не меняет — стоп.

Итерация по политикеитерация по политике (policy iteration)EN policy iterationЧередовать оценку политики (решить уравнение Беллмана для V^π) и её жадное улучшение, пока политика не перестанет меняться. (policy iteration):

1. Начать с любой политики.
2. Оценка: найти $V^\pi$ (решить линейную систему или итерациями, как выше).
3. Улучшение: в каждом состоянии взять действие с максимальным $Q^\pi(s, a)$. Новая политика не хуже старой — это теорема об улучшении политики.
4. Если политика не изменилась — она оптимальна. Иначе вернуться к шагу 2.

	Value iteration	Policy iteration
Что повторяем	один шаг Беллмана с максимумом	точную оценку + жадное улучшение
Цена итерации	дешёвая	дорогая (решить систему)
Число итераций	много: растёт при $\gamma \to 1$	обычно единицы раундов
Что нужно знать	$P$ и $R$	$P$ и $R$

Оба алгоритма требуют модели среды. В жизни её обычно нет: никто не выдаст вам таблицу вероятностей для шахматного противника или для пользователя чат-бота. Как учиться без модели — следующий урок.

Мир-сетка: как дисконт меняет поведение

Мир-сеткамир-сетка (gridworld)EN grid worldУчебная среда — агент ходит по клеткам поля, есть цели, ловушки и стены. (gridworld) — классическая учебная среда. Наше поле 5×5: старт S, большая цель G (+1), маленькая цель g (+0.4), ловушки X (−1), стена #. Цели и ловушки заканчивают эпизод. Value iteration при трёх значениях $\gamma$ даёт такие политики (стрелки) и ценности (цвет: зелёный — выше):

• $\gamma = 0.5$ — агент близорук. До g 4 шага, до G — 8. Сравним: $0.4 \cdot 0.5^3 = 0.05$ против $1 \cdot 0.5^7 \approx 0.008$. Синица в руках побеждает.
• $\gamma = 0.9$ — уже $0.4 \cdot 0.9^3 \approx 0.29$ против $0.9^7 \approx 0.48$: агент идёт к большой цели в обход ловушек.
• $\gamma = 0.99$ — путь тот же, но ценности почти не убывают с расстоянием ($V(S) = 0.99^7 \approx 0.93$): далёкое будущее весит почти как настоящее.

Если пол сделать скользким (агент с вероятностью 0.2 съезжает вбок), появится осторожность: рядом с ловушками стрелки начинают «упираться в стену», чтобы не соскользнуть в X. Это поведение никто не программировал — оно следует из уравнения Беллмана. Попробуйте сами в задании ниже (make_gridworld(slip=0.2)).

Почему ответ LLM — контекстный бандит, а агент — нет

Запишем генерацию ответа как MDP. Состояние — промпт плюс уже написанные токены, действие — следующий токен, переход детерминирован (токен просто дописывается в контекст), награда приходит один раз в конце, $\gamma = 1$. Раз переходы предсказуемы, а награда одна, весь ответ можно считать одним действием: увидели промпт — выдали ответ — получили оценку. Задачу из одного шага, но в разных ситуациях называют контекстным бандитомконтекстный бандитEN contextual banditЗадача RL из одного шага, но в разных ситуациях (контекстах). Ответ LLM целиком на промпт — пример такой задачи.: контекст — промпт, «ручка бандита» — ответ.

На языке этого урока: $V(\text{промпт})$ — средняя награда ответов модели на этот промпт, а преимущество ответа — $A = r - V(\text{промпт})$. Именно эту величину GRPO (урок 6.4.1) оценивает просто по выборке: генерирует на промпт группу ответов и сравнивает награду каждого со средней по группе.

У агента с инструментами (модуль 8.3) так не выйдет:

	Один ответ LLM	Агент с инструментами
Кто меняет состояние	только модель	модель и среда: вывод инструментов, веб-страницы, результаты тестов
Переходы	детерминированы	случайны, модель их не контролирует
Шагов с решениями	один (если считать ответ целиком)	десятки вызовов инструментов
Распределение заслуг	одна оценка на весь ответ	какой из 30 шагов привёл к успеху?

Для агента нужна полноценная MDP: функции ценности по шагам, критик и GAE из урока 6.0.3.

Практика

Задание: value iteration и policy iteration на мире-сетке

Модель среды (make_gridworld) и печать карты уже готовы. Реализуйте шаг Беллмана для всех состояний сразу, оценку политики, value iteration и policy iteration. Тесты проверят, что ценности решают уравнение оптимальности, что политика ведёт к цели в обход ловушек и что policy iteration приходит к той же $V$.

Value iteration и policy iteration на мире-сетке 5×5numpy · нужен интернет7 тестов

import numpy as np

# ── Среда уже готова: модель gridworld 5×5 ──────────────────────────────────
# S — старт, G — большая цель (+1), g — маленькая цель (+0.4), X — ловушка (−1),
# # — стена, . — пустая клетка. G, g и X — конечные клетки: эпизод там заканчивается.
LAYOUT = [
    "S....",
    ".X.X.",
    "..g..",
    "#X.X.",
    "....G",
]
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]   # действия: 0 ↑, 1 →, 2 ↓, 3 ←
ARROWS = "↑→↓←"
CELL_REWARD = {"G": 1.0, "g": 0.4, "X": -1.0}


def make_gridworld(layout=LAYOUT, slip=0.0):
    """Модель среды: P[s, a, s'] — вероятность перехода, R[s, a] — средняя награда за шаг.

    slip — вероятность «поскользнуться»: агент уходит вбок от выбранного направления
    (по slip/2 в каждую сторону). Упёрся в край поля или в стену — остаётся на месте.
    Конечные клетки (и стены) поглощающие: из них P = 1 в себя же, награда 0.
    """
    H, W = len(layout), len(layout[0])
    n = H * W
    P = np.zeros((n, 4, n))
    R = np.zeros((n, 4))
    for s in range(n):
        r, c = divmod(s, W)
        if layout[r][c] in "GgX#":
            P[s, :, s] = 1.0
            continue
        for a in range(4):
            for move, p in [(a, 1 - slip), ((a + 1) % 4, slip / 2), ((a + 3) % 4, slip / 2)]:
                if p == 0:
                    continue
                nr, nc = r + MOVES[move][0], c + MOVES[move][1]
                if not (0 <= nr < H and 0 <= nc < W) or layout[nr][nc] == "#":
                    nr, nc = r, c
                P[s, a, nr * W + nc] += p
                R[s, a] += p * CELL_REWARD.get(layout[nr][nc], 0.0)
    return P, R


def show(V, policy, layout=LAYOUT):
    """Печатает стрелки политики и «тепловую карту» V (числами) рядом."""
    W = len(layout[0])
    for r, row in enumerate(layout):
        arrows = " ".join(ch if ch in "GgX#" else ARROWS[policy[r * W + c]] for c, ch in enumerate(row))
        values = " ".join(f"{V[r * W + c]:+.2f}" for c in range(W))
        print(arrows, "   ", values)


# ── Ваша часть ──────────────────────────────────────────────────────────────

def bellman_q(P, R, V, gamma):
    """Q[s, a] = R[s, a] + gamma * sum_s' P[s, a, s'] * V[s'] для всех s и a сразу.

    Вход: P — [S, A, S], R — [S, A], V — [S]. Ответ — массив [S, A].
    Подсказка: P @ V перемножает последнюю ось P с V и даёт [S, A].
    """
    # TODO: ваш код
    ...


def policy_evaluation(P, R, policy, gamma, tol=1e-10):
    """Оценка политики: V^π итерациями уравнения Беллмана.

    policy — массив [S] с номером действия в каждом состоянии.
    Старт V = нули; повторять V_new[s] = Q[s, policy[s]] (Q считать через bellman_q),
    пока max |V_new - V| >= tol. Вернуть V_new.
    """
    # TODO: ваш код
    ...


def value_iteration(P, R, gamma, tol=1e-10):
    """Итерация по ценности. Вернуть (V, policy, n_iter).

    Старт V = нули; на каждой итерации Q = bellman_q(P, R, V, gamma), V_new = max по действиям.
    Остановка, когда max |V_new - V| < tol. policy — argmax по действиям у последнего Q,
    n_iter — сколько раз пересчитали V.
    """
    # TODO: ваш код
    ...


def policy_iteration(P, R, gamma, max_rounds=100):
    """Итерация по политике. Вернуть (V, policy).

    Старт: policy = нули (все «↑»). Раунд: V = policy_evaluation(...),
    Q = bellman_q(...), new_policy = argmax Q. Чтобы не «дрожать» на равных значениях,
    оставляйте старое действие, если оно всё ещё оптимально (np.isclose с максимумом).
    Политика не изменилась — стоп.
    """
    # TODO: ваш код
    ...


# Проверьте себя кнопкой «Запустить»: эксперимент с γ
P, R = make_gridworld()
for gamma in [0.5, 0.9, 0.99]:
    out = value_iteration(P, R, gamma)
    if out is not None:
        V, pi, n_iter = out
        print(f"γ = {gamma}: итераций {n_iter}, V(S) = {V[0]:.3f}")
        show(V, pi)

ЗапуститьПроверитьПодсказкаСбросить

После решения нажмите «Запустить»: вы увидите стрелки и ценности для $\gamma = 0.5$, $0.9$ и $0.99$. Затем поменяйте make_gridworld() на make_gridworld(slip=0.2) и посмотрите, как растёт число итераций (26, 100 и 333) и где агент начинает осторожничать.

Локально: тепловая карта и стрелки

Картинку выше рисует такой код (matplotlib из урока 0.3.3). Сохраните своё решение задания в файл solution.py рядом со скриптом:

import matplotlib.pyplot as plt
import numpy as np
from solution import LAYOUT, make_gridworld, value_iteration   # ваше решение задания

P, R = make_gridworld()
fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for ax, gamma in zip(axes, [0.5, 0.9, 0.99]):
    V, policy, _ = value_iteration(P, R, gamma)
    ax.imshow(V.reshape(5, 5), cmap="RdYlGn", vmin=-1, vmax=1)        # тепловая карта V
    for s in range(25):
        r, c = divmod(s, 5)
        ch = LAYOUT[r][c]
        if ch in "GgX#":
            ax.text(c, r, ch, ha="center", va="center", fontsize=16, weight="bold")
        else:                                                         # стрелка политики
            dr, dc = [(-1, 0), (0, 1), (1, 0), (0, -1)][policy[s]]
            ax.arrow(c - 0.2 * dc, r - 0.2 * dr, 0.4 * dc, 0.4 * dr, head_width=0.15, color="black")
    ax.set_title(f"γ = {gamma}, V(S) = {V[0]:.2f}")
    ax.set_xticks([]); ax.set_yticks([])
plt.tight_layout()
plt.savefig("gridworld_gamma.png", dpi=110, facecolor="white")

Получится файл gridworld_gamma.png — те же три панели, что выше. Видеокарта здесь не нужна: поле из 25 клеток считается за миллисекунды.

Китайский угол: курс Чжао Шиюя и мир-сетка

Лучший китайский курс именно по теме этого урока — «Математические основы обучения с подкреплением» профессора Чжао Шиюя (Shiyu Zhao, Западноозёрный университет, Ханчжоу). Книга выложена бесплатно на GitHub; английская версия вышла в издательствах Springer и Tsinghua University Press, китайская — под тем же названием — в издательстве Университета Цинхуа в 2025 году. По словам автора, его видеолекции набрали больше 2,1 млн просмотров, а у репозитория больше 10 тыс. звёзд.

Чем курс полезен вам: все примеры книги построены на мире-сетке, как наше задание. Лекция 2 выводит уравнение Беллмана и его матричную форму $V = R_\pi + \gamma P_\pi V$ (наш np.linalg.solve), лекция 3 — уравнение оптимальности, лекция 4 — value и policy iteration. Лекции есть на китайском (Bilibili) и на английском (YouTube, ссылка на плейлист — в README репозитория).

Ещё два китайских источника: easy-rl, «Грибная книга» (Datawhale), глава 2 «Марковский процесс принятия решений», и «Обучение с подкреплением своими руками» (Hands-on-RL, Шанхайский университет Цзяотун), главы 3 «Марковский процесс принятия решений» и 4 «Алгоритмы динамического программирования» — там value и policy iteration запускают на «прогулке по обрыву» (Cliff Walking) и «замёрзшем озере» (Frozen Lake).

Термины. MDP, отдача, функции ценности состояния ($V$) и действия ($Q$), уравнение Беллмана, value и policy iteration по-китайски называются дословно, а фамилии Маркова и Беллмана передаются по звучанию. Политику (policy) называют «стратегией», поэтому policy iteration — буквально «итерация стратегии», а коэффициент дисконтирования — «коэффициент скидки».

Проверь себя

Проверь себя6 вопросов·

1 Эпизод дал награды $[1, 0, 2]$. Чему равна отдача $G_0$ при $\gamma = 0.5$?

2 В состоянии $s$ политика выбирает действие 0 с вероятностью 0.2 и действие 1 с вероятностью 0.8; $Q(s, 0) = 1$, $Q(s, 1) = 3$. Чему равно преимущество $A(s, 0)$?

3 Какие утверждения о коэффициенте дисконтирования верны?Можно выбрать несколько ответов

Агент планирует примерно на $1/(1-\gamma)$ шагов вперёдПри $\gamma = 0$ агент учитывает только награду текущего шагаПри $\gamma < 1$ и ограниченных наградах отдача конечна даже в бесконечной задачеЧем ближе $\gamma$ к 1, тем быстрее сходится value iteration

4 Что означает слагаемое $\gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s')$ в уравнении Беллмана?

Награду, полученную на текущем шагеДисконтированную среднюю ценность состояния, в которое мы попадёмВероятность выбрать действие $a$Максимальную отдачу по всем политикам

5 Чем policy iteration отличается от value iteration?

Policy iteration не требует модели средыPolicy iteration чередует точную оценку политики и жадное улучшение и обычно сходится за малое число раундовPolicy iteration находит более оптимальную политику, чем value iterationValue iteration работает только при $\gamma = 1$

6 Почему RL для одного ответа LLM можно рассматривать как контекстный бандит?

Потому что у LLM нет политикиПотому что переходы детерминированы (токен дописывается в контекст), а награда одна в конце — весь ответ можно считать одним действием в контексте промптаПотому что у LLM всего два действияПотому что награда за каждый токен известна заранее

Проверить ответы

Итоги

• Задача RL — MDP $(S, A, P, R, \gamma)$: агент выбирает действия, среда отвечает состоянием и наградой. Цель — максимум средней отдачи $G_t = \sum_k \gamma^k r_{t+k}$, где $\gamma$ задаёт горизонт $\approx 1/(1-\gamma)$.
• $V^\pi(s)$ — средняя отдача из состояния, $Q^\pi(s, a)$ — после конкретного действия, преимущество $A = Q - V$ — насколько действие лучше обычного. На преимуществе построены PPO и GRPO.
• Уравнение Беллмана выражает ценность через ценность следующего шага; с максимумом вместо среднего оно задаёт оптимальную политику.
• Когда модель среды известна, value iteration и policy iteration находят оптимальную политику; на мире-сетке видно, как $\gamma$ превращает близорукого агента в дальновидного.
• Один ответ LLM — контекстный бандит ($V$ промпта = средняя награда его ответов), агент с инструментами — полноценная MDP.

Дальше: что делать, если модели среды нет и вероятности $P$ неизвестны, — учиться на собственном опыте методами Монте-Карло и TD, исследовать мир ε-жадно и находить оптимальную политику алгоритмом Q-learning.