# Stanford CS234 Reinforcement Learning I Tabular MDP Planning I 2024 I Lecture 2

Источник: https://www.youtube.com/watch?v=gHdsUUGcBC0
Канал: Stanford Online
Опубликовано: 30.10.2024

---

Вторая лекция курса Стэнфордского университета CS234 «Обучение с подкреплением» (Reinforcement Learning) посвящена переходу от простых марковских процессов к полноценному планированию в рамках марковских процессов принятия решений (MDP). Профессор Эмма Брунскилл (Emma Brunskill) подробно разбирает математический аппарат, лежащий в основе современных алгоритмов ИИ, от AlphaGo до систем обучения с подкреплением на основе человеческой обратной связи (RLHF).

## 🧩 От оценки к действию: основы MDP
[[JUMP:05:43]]

Обучение с подкреплением часто начинают с «табулярных» миров, таких как задача о семисостоянии марсохода (Mars Rover) [05:55]. Хотя эти примеры кажутся упрощенными, они служат фундаментальными кирпичиками для самых продвинутых алгоритмов современности. Главное отличие марковского процесса принятия решений (MDP) от марковского процесса вознаграждения (MRP) — наличие действий.

Марковский процесс принятия решений определяется кортежем из пяти элементов [14:50]:

*   **S (States):** множество состояний.
*   **A (Actions):** множество доступных действий.
*   **P (Transition Dynamics):** модель динамики, определяющая вероятность перехода в следующее состояние при выборе конкретного действия.
*   **R (Reward Model):** функция вознаграждения, зависящая от состояния и действия.
*   **γ (Gamma):** коэффициент дисконтирования.

Брунскилл подчеркивает, что если зафиксировать определенную политику (правила выбора действий), то MDP фактически превращается в MRP [16:08]. Это позволяет использовать все математические инструменты оценки вознаграждений для анализа качества конкретной стратегии.

## 📈 Стратегия итерирования политики (Policy Iteration)
[[JUMP:23:14]]

Одним из ключевых свойств, которые разработчики стремятся получить в реальных системах, является монотонное улучшение [01:10]. Это гарантия того, что с каждой новой итерацией вычислений или с получением новых данных система будет принимать решения не хуже, чем на предыдущем этапе.

Алгоритм итерации политики (Policy Iteration) реализует этот принцип через два чередующихся шага [24:09]:

1.  **Оценка политики (Policy Evaluation):** вычисление функции ценности (V) или Q-функции для текущей стратегии.
2.  **Улучшение политики (Policy Improvement):** обновление стратегии путем выбора действий, максимизирующих Q-функцию в каждом состоянии.

### Q-функция как ключ к оптимизации
Для шага улучшения критически важно понятие Q-функции (State-Action Value Function) [24:52]. В отличие от функции ценности V(s), которая оценивает состояние в целом, Q(s, a) показывает ожидаемую выгоду от совершения конкретного действия `а` в состоянии `s` с последующим следованием текущей политике.

Профессор Брунскилл представила доказательство того, что новая политика, полученная через выбор `argmax` по Q-функции, всегда будет монотонно улучшать общий результат [31:31]. Исключение составляет лишь случай, когда текущая политика уже является оптимальной. Поскольку в табулярном мире количество детерминированных политик конечно ($A^S$), алгоритм гарантированно сходится к оптимуму за конечное число шагов [44:31].

## 🔄 Итерация ценности (Value Iteration) и уравнение Беллмана
[[JUMP:47:45]]

В отличие от итерации политики, где на каждом шаге мы имеем «полноценную» (хоть и плохую) стратегию для бесконечного горизонта планирования, алгоритм итерации ценности (Value Iteration) работает иначе [47:55].

Основные идеи Value Iteration:

*   На каждой итерации вычисляется оптимальная ценность, но для ограниченного горизонта (например, «что лучше всего сделать, если у меня остался всего один шаг?», затем — два шага и так далее) [48:26].
*   Алгоритм использует оператор резервного копирования Беллмана (Bellman backup operator).
*   Процесс продолжается до тех пор, пока функция ценности не перестанет существенно меняться (сходимость по L-бесконечность норме) [51:09].

По словам Брунскилл, итерация ценности не гарантирует монотонного улучшения стратегии на промежуточных этапах, так как она всегда оптимизирует решение для «неправильного» (укороченного) горизонта планирования, пока не достигнет сходимости [55:27].

## 📐 Математика сходимости: оператор сжатия
[[JUMP:57:45]]

Почему мы можем быть уверены, что итерация ценности вообще сойдется к единому решению? Ответ кроется в свойстве оператора Беллмана как «оператора сжатия» (contraction operator) [58:51].

Брунскилл математически доказывает, что при коэффициенте дисконтирования γ < 1 применение оператора Беллмана к двум разным векторам ценности уменьшает максимальное расстояние между ними [01:03:53].

*   Если взять две любые инициализации функции ценности и применить к ним оператор Беллмана, они станут ближе друг к другу как минимум в $1/\gamma$ раз [01:04:06].
*   Это гарантирует существование единственной неподвижной точки (fixed point) — уникальной функции ценности [1:04:34].

## 🧪 Практические подходы: симуляция вместо вычислений
[[JUMP:1:09:19]]

В сложных системах, таких как Amazon или базы данных здравоохранения, часто невозможно в явном виде выписать модель динамики (все вероятности переходов между миллионами состояний) [1:10:37]. В таких случаях применяется метод Монте-Карло или симуляция.

Вместо суммирования по всем возможным будущим состояниям, разработчики просто «прогоняют» текущую политику через среду множество раз и усредняют полученные вознаграждения [1:09:57]. Профессор отмечает, что согласно неравенству Хофдинга, точность такой оценки растет пропорционально $1/\sqrt{n}$, где `n` — количество симуляций, и это не зависит от размера пространства состояний [1:10:24]. Более того, такой подход не требует строгого соблюдения марковского свойства среды, что делает его крайне гибким для реальных задач [1:10:51].

--- --- ---