Вторая лекция курса Стэнфордского университета CS234 «Обучение с подкреплением» (Reinforcement Learning) посвящена переходу от простых марковских процессов к полноценному планированию в рамках марковских процессов принятия решений (MDP). Профессор Эмма Брунскилл (Emma Brunskill) подробно разбирает математический аппарат, лежащий в основе современных алгоритмов ИИ, от AlphaGo до систем обучения с подкреплением на основе человеческой обратной связи (RLHF).
🧩 От оценки к действию: основы MDP 5:43
Обучение с подкреплением часто начинают с «табулярных» миров, таких как задача о семисостоянии марсохода (Mars Rover) . Хотя эти примеры кажутся упрощенными, они служат фундаментальными кирпичиками для самых продвинутых алгоритмов современности. Главное отличие марковского процесса принятия решений (MDP) от марковского процесса вознаграждения (MRP) — наличие действий.
Марковский процесс принятия решений определяется кортежем из пяти элементов :
- S (States): множество состояний.
- A (Actions): множество доступных действий.
- P (Transition Dynamics): модель динамики, определяющая вероятность перехода в следующее состояние при выборе конкретного действия.
- R (Reward Model): функция вознаграждения, зависящая от состояния и действия.
- γ (Gamma): коэффициент дисконтирования.
Брунскилл подчеркивает, что если зафиксировать определенную политику (правила выбора действий), то MDP фактически превращается в MRP . Это позволяет использовать все математические инструменты оценки вознаграждений для анализа качества конкретной стратегии.
📈 Стратегия итерирования политики (Policy Iteration) 23:14
Одним из ключевых свойств, которые разработчики стремятся получить в реальных системах, является монотонное улучшение . Это гарантия того, что с каждой новой итерацией вычислений или с получением новых данных система будет принимать решения не хуже, чем на предыдущем этапе.
Алгоритм итерации политики (Policy Iteration) реализует этот принцип через два чередующихся шага :
- Оценка политики (Policy Evaluation): вычисление функции ценности (V) или Q-функции для текущей стратегии.
- Улучшение политики (Policy Improvement): обновление стратегии путем выбора действий, максимизирующих Q-функцию в каждом состоянии.
Q-функция как ключ к оптимизации
Для шага улучшения критически важно понятие Q-функции (State-Action Value Function) . В отличие от функции ценности V(s), которая оценивает состояние в целом, Q(s, a) показывает ожидаемую выгоду от совершения конкретного действия а в состоянии s с последующим следованием текущей политике.
Профессор Брунскилл представила доказательство того, что новая политика, полученная через выбор argmax по Q-функции, всегда будет монотонно улучшать общий результат . Исключение составляет лишь случай, когда текущая политика уже является оптимальной. Поскольку в табулярном мире количество детерминированных политик конечно ($A^S$), алгоритм гарантированно сходится к оптимуму за конечное число шагов .
🔄 Итерация ценности (Value Iteration) и уравнение Беллмана 47:45
В отличие от итерации политики, где на каждом шаге мы имеем «полноценную» (хоть и плохую) стратегию для бесконечного горизонта планирования, алгоритм итерации ценности (Value Iteration) работает иначе .
Основные идеи Value Iteration:
- На каждой итерации вычисляется оптимальная ценность, но для ограниченного горизонта (например, «что лучше всего сделать, если у меня остался всего один шаг?», затем — два шага и так далее) .
- Алгоритм использует оператор резервного копирования Беллмана (Bellman backup operator).
- Процесс продолжается до тех пор, пока функция ценности не перестанет существенно меняться (сходимость по L-бесконечность норме) .
По словам Брунскилл, итерация ценности не гарантирует монотонного улучшения стратегии на промежуточных этапах, так как она всегда оптимизирует решение для «неправильного» (укороченного) горизонта планирования, пока не достигнет сходимости .
📐 Математика сходимости: оператор сжатия 57:45
Почему мы можем быть уверены, что итерация ценности вообще сойдется к единому решению? Ответ кроется в свойстве оператора Беллмана как «оператора сжатия» (contraction operator) .
Брунскилл математически доказывает, что при коэффициенте дисконтирования γ < 1 применение оператора Беллмана к двум разным векторам ценности уменьшает максимальное расстояние между ними .
- Если взять две любые инициализации функции ценности и применить к ним оператор Беллмана, они станут ближе друг к другу как минимум в $1/\gamma$ раз .
- Это гарантирует существование единственной неподвижной точки (fixed point) — уникальной функции ценности .
🧪 Практические подходы: симуляция вместо вычислений 1:09:19
В сложных системах, таких как Amazon или базы данных здравоохранения, часто невозможно в явном виде выписать модель динамики (все вероятности переходов между миллионами состояний) . В таких случаях применяется метод Монте-Карло или симуляция.
Вместо суммирования по всем возможным будущим состояниям, разработчики просто «прогоняют» текущую политику через среду множество раз и усредняют полученные вознаграждения . Профессор отмечает, что согласно неравенству Хофдинга, точность такой оценки растет пропорционально $1/\sqrt{n}$, где n — количество симуляций, и это не зависит от размера пространства состояний . Более того, такой подход не требует строгого соблюдения марковского свойства среды, что делает его крайне гибким для реальных задач .
