Для меня разобраться в базовых концепциях Reinforcement Learning оказалось не так просто, особенно сложными оказались функции Беллмана. Эта статья — моя попытка систематизировать материал и объяснить себе (и, возможно, другим), что, откуда и почему берется. Будет здорово, если она поможет кому-то разложить все по полочкам.

¯\_(ツ)_/¯

Полезные ссылки:
Practical RL (ШАД) (самые полезные материалы были тут)
Лекция №15 "Обучение с подкреплением"
Тренировки. Лекция 3: Введение в обучение с подкреплением
Тренировки. Лекция 4: Q-learning, Deep Q-learning
Тренировки. Лекция 5: Современные методы обучения с подкреплением. Advantage actor critic, RLHF
11.1. Обучение с подкреплением

Мой тг канал: Not Magic Neural Networks

Содержание

1. Intro
2. Определения
3. Cross-Entropy Method, CEM
4. Markov decision process, MDP
5. Награда (reward) и коэффициент дисконтирования

6. Оценочные функции
6.1. Backup Tree & динамическое программирование
6.2. State-value function и Policy Evaluation
6.3. Policy Improvement и action-value function
6.4. Уравнения оптимальности Беллмана

7. Generalized Policy iteration

1. Intro

На гифке щенок учится через игру: он пробует разные действия, наблюдает за реакцией человека и запоминает, что именно приносит ему вкусняшку. Когда за правильное поведение он получает награду, у него формируется связь между действием и результатом — «сделал правильно → получил вкусняшку». Так шаг за шагом песик осваивает новые команды, учится понимать, чего от него ждут, и радостно повторяет то, что приносит успех.

Такое обучение называется Reinforcement Learning (RL) — обучение методом проб и ошибок. Термин reinforcement ("подкрепление") заимствован из поведенческой психологии и терапии и означает последствия (награду или наказание), которые увеличивают или уменьшают вероятность повторения определённого поведения.

Главное отличие RL от обучения с учителем (supervised learning) состоит в том, что этот подход не требует заранее размеченных данных и не опирается на дифференцируемую функцию потерь.

Опишем более формально рассуждения выше:
Пусть у нас есть агент, который взаимодействует с окружающей средой. В каждый момент времени агент наблюдает состояние среды и, опираясь на эти наблюдения, совершает действие. В результате действия состояние среды изменяется.
Процедуру выбора действия будем называть стратегией (или политикой).
За каждое свое действие агент получает награду (или штраф).
Цель агента – изменить свою политику так, чтобы получить максимальную награду. Процесс взаимодействия агента и среды задается динамикой среды, а серия взаимодействий агента со средой от начального до терминального состояния называется эпизодом.

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

2. Определения:

Reinforcement Learning — обучение методом проб и ошибок.
Agent (агент) — интеллектуальная система (программа, робот, алгоритм), которая принимает решения и совершает действия в некоторой среде с целью достижения определённых целей.
Environment (среда) — всё, с чем взаимодействует агент: внешний мир, в котором происходят события и изменения в ответ на действия агента.
Observation (наблюдение) — информация, которую агент получает от среды в каждый момент времени .
$a = \pi (s)$ : active (действие агента) — конкретное решение или команда, которую агент выбирает и выполняет в среде с целью повлиять на неё.
: stage (состояние) – описание текущей ситуации, в которой находится агент.
$\pi (a|s)$ : policy (политика или стратегия поведения агента) — вероятностное распределение действий при условии состояния .
$R_{s,s'}^{a}$ : Reward (награда) — цели и желания, закодированные в скалярном сигнале. Награда может быть положительной, отрицательной (штрафом) или нейтральной. Она зависит от текущего состояния среды , выбранного агентом действия и следующего состояния среды .
$G = \sum R_i$ : return или cumulative reward – просуммированый по времени reward.
$G \rightarrow \max_{\pi}$ : цель агента — максимизировать return с помощью оптимальной политики.
Траектория — цепочка генерируемых в ходе взаимодействия случайных величин

3. Cross-Entropy Method, CEM

Кросс-энтропийный метод (Cross-Entropy Method, CEM) — это простой алгоритм, который используется для поиска оптимальной политики путем итеративного улучшения выборки решений.

Для простоты будем считать, что количество состояний и действий нашей задачи – конечно. Тогда политику $\pi$ можно задать с помощью матрицы у которой по строкам — состояния, а по столбцам — действия.

Алгоритм:

Инициализируем политику $\pi$ (случайным или равновероятным образом).
$\pi = \begin{array}{c|cccc} & a_1 & a_2 & \dots & a_n \\ \hline s_1 & P(a_1|s_1) & P(a_2|s_1) & \dots & P(a_n|s_1) \\ s_2 & P(a_1|s_2) & P(a_2|s_2) & \dots & P(a_n|s_2) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ s_m & P(a_1|s_m) & P(a_2|s_m) & \dots & P(a_n|s_m) \end{array} = A_{s,a}$
Семплируем сессий с данной политикой.
Выбираем сессий с наибольшей наградой (элиту).
$\text{Elite} = [(s_0, a_0), (s_1, a_1), \ldots, (s_M, a_M)]$
Обновляем политику в соответствии с элитой (повышаем вероятность "правильных" действий, согласно элитным):
$\pi_{\text{new}}(a \mid s) = \frac{ \sum\limits_{s_t, a_t \in \text{Elite}} [s_t = s][a_t = a] }{ \sum\limits_{s_t, a_t \in \text{Elite}} [s_t = s] } = \frac{\text{Сколько раз совершали действие a в состоянии s}}{\text{Сколько раз были в состоянии s}}$
Возвращаемся к шагу 2.

Approximate cross-entropy method

Можно рассмотреть выбор действия при условии состояния (политику) как задачу классификации: $\pi(a|s) = f_{\theta}(a,s)$ , где $f_{\theta}$ может быть случайным лесом, логрегрессей или нейронной сетью.

Аналогично, семплируем сессий и выбираем из них элитных.

Максимизируем правдоподобие элитных сессий:

$\pi(a|s)_{\text{new}} = argmax_{\pi} \sum_{s,a \in \text{elite}} \log \pi(a_i|s_i)$

Отсюда название "метод кросс-энтропии": максимизация правдопобия = минимазация кросс-энтропии.

Из плюсов, кросс-энтропийный метод легко реализовывать и он дает хорошие результаты, устойчив относительно сходимости в локальный оптимум. Однако, этот метод рассматривает среду как «чёрный ящик» – то есть он ничего не знает о том что внутри среды происходит.

Ноутбук потыкать (вторая домашка с тренировок).

Попробуем улучшить его, учитывая внутреннюю структуру среды. Эта структура описывается Марковским свойством.

4. Markov decision process, MDP

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

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

Марковский процесс (цепь) — это кортеж , где — множество состояний, — матрица переходов (transition matrix), состоящая из вероятностей оказаться в состоянии , при условии, что среда находилась в состоянии .

$P_{ss'} = P(S_{t+1} = s' \mid S_{t} = s)$

Марковское свойство — это условная независимость от истории, кроме как от текущего состояния и текущего действия, для награды и следующего состояния.

Среда является Марковской, когда награда и следующее состояние зависят только от текущего состояния среды .

Марковский процессом принятия решений (MDP) – это кортеж $(\mathbb S,\mathbb A,\mathbb R,\mathbb P,\gamma)$ , где $\mathbb S$ — множество состояний, $\mathbb A$ — множество действий, $\mathbb P_{ss'}^{a}$ — матрица переходов, $\mathbb R_{ss'}^{a}$ — функция награды, $\gamma$ — коэффициент дисконтирования.

$MDP = (\mathbb S,\mathbb A,\mathbb R,\mathbb P,\gamma)$

5. Награда (reward) и коэффициент дисконтирования

Суммарная награда (cumulative reward) — это сумма всех наград на всех шагах агента:

$G_t = \sum_t^T R_i$

где — мгновенная награда (immediate reward),— конец эпизода.

Цель агента — максимизировать кумулятивную награду. То есть, это наше оптимизируемое значение.

Легко заметить, что цели агента и наши собственные цели могут сильно различаться. Более того, правильно задать функцию награды так, чтобы она действительно отражала наши намерения, на практике оказывается совсем непросто.

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

Для того чтобы избежать ситуацию, когда агент накапливает бесконечную сумму наград, используется коэффициент дисконтирования $\gamma$ , который показывает, насколько ценными являются будущие награды на текущий момент:

$G_t = \sum R_t + \gamma (R_{t-1} + \gamma R_{t-2} + \ldots) = R_t + \gamma G_{t-1}$

При $\gamma \rightarrow 0$ смотрим на меньшее количество шагов назад, при $\gamma = 0$ получим "жадный алгоритм".
При $\gamma \rightarrow 1$ смотрим на большее количество шагов, при $\gamma=1$ смотрим на всю историю.
При $\gamma = 0.99$ видим около 100 шагов назад, при $\gamma = 0.95$ около 20 шагов, при $\gamma = 0.9$ около 10 шагов.

Важно понимать, что выбор $\gamma$ не гиперпараметр алгоритма, а часть задачи. Оптимальное поведение агента для разных $\gamma$ может отличаться.

Таким образом, новая цель агента — максимизировать суммарную дисконтированную награду.

Однако, дисконтированная награда лишь отчасти убирает проблему зацикливания, но не решает ее полностью.

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

С одной стороны, функция награды должна максимально соответствовать целям, которые мы хотим, чтобы агент достигал. Кажется логичным награждать только за конечный успех — например, за победу. Но в таком случае возникает проблема разреженной награды (sparse rewards): агент получает обратную связь лишь в конце эпизода и не может понять, какие конкретно действия привели к успеху.

Чтобы облегчить обучение, применяют приём под названием reward shaping — формирование награды. Идея заключается в том, чтобы добавить вспомогательную функцию-подсказку , которая помогает агенту двигаться в нужном направлении. Обычно ) получается как разность потенциалов, где – текущее состояние, – действие, – будущее состояние.

$F(s,a,s') = \gamma \Phi(s') - \Phi(s)$

— оригинальная награда
— shaping-функция (дополнительная награда), которая зависит от состояний и/или действий.
$\Phi(s)$ — potential function, «потенциал» состояния, который показывает, насколько хорошо находиться в этом состоянии.

Таким образом, если агент движется в направлении «лучших» состояний, он получает дополнительную награду. Если идет «назад», получает штраф.

6. Оценочные функции

6.1. Backup Tree & динамическое программирование

Давайте построим дерево следующей структуры:
— на светлой вершине лежит текущее состояние
— на темных вершинах лежат действия
— после действия, на ребре лежит награда
— оказываемся в новом состоянии (н�� светлой вершине)
Оптимальной политикой будет путь, содержащий максимальную сумму наград от корня до листа.

Такая задача решается с помощью динамического программирования: идем от листьев к корню дерева и тащим за собой максимальную сумму наград. Но для того чтобы протащить значение будущей награды вверх по дереву, нужно ввести два понятия: функция полезности состояния и функция полезности состояния действия (state-value и action-value functions).

Функции ценности — это функции состояний (или пар состояний-действий), которые оценивают, насколько хорошо агенту находиться в данном состоянии (или насколько хорошо выполнять данное действие в данном состоянии).

6.2. State-value function

Пусть мы хотим понять, насколько хорошее наше текущее состояние .
Цель агента – максимизировать суммарную дисконтированную награду. Тогда пусть "хорошестю текущего состояния " будет ожидаемая суммарная дисконтированная награда, если мы будем следовать нашей политике $\pi$ .
При этом, путь от текущего состояния до терминального содержит очень много случайностей: начальное состояние, действие из нашей политики, следующее состояние, следующая награда... Эту "хорошесть" называют state-value function.

State-value function $v_{\pi}$ — это математическое ожидание суммарной дисконтированной награды , которую агент получит, находясь в состоянии и следуя политике $\pi$ .

Для фиксированной политики $\pi$ мы можем посчитать суммарную дисконтированную награду честно взяв мат. ожидание:

$v_\pi(s) \triangleq \mathbb{E}_\pi \big[ G_t \mid S_t = s \big] =$

$= \mathbb{E}\pi \left[ R_t + \gamma G_{t+1} \mid S_t = s \right] =$

$= \sum_a \pi(a \mid s) \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma \mathbb{E}\pi \big[ G_{t+1} \mid S_{t+1} = s' \big] \Big] =$

– текущее состояние, – следующее состояние.
Стохастичность политики $\pi(a|s)$ в том что агент может выбирать разные действия с ненулевыми вероятностями.
Стохастичность окружения в том что следующее состояние и награда могут быть случайными.
$\gamma \mathbb{E}\pi \big[ G_{t+1} \mid S_{t+1} = s' \big] \Big]$ — дисконтированное мат. ожидание от будущей награды, параметризованное только будущим действием , которое можно свернуть в $v_\pi(s')$ .

$= \sum_a \pi(a \mid s) \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma v_\pi(s') \Big]$

$[1] \quad \quad v_\pi(s) = \sum_a \pi(a \mid s) \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma v_\pi(s') \Big]$

Или так:

$[1] \quad \quad v_{\pi}(s) = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r(s, a) + \gamma v^{\pi}(s') \right]$

Обнаружив рекуррентное соотношение, мы поняли как пересчитать $v_\pi(s)$ имея $v_\pi(s')$ .

(функция качества состояния) — средняя награда, которую получит агент, начиная играть с состояния при следовании политики $\pi$ (оценка, насколько хорошо находиться в состоянии ).

Посчитаем v-функцию для текущего состояния s

Пусть мы имеем следующее дерево и находимся в состоянии (в корне).

Наша политика $\pi$ говорит, что из текущего состояния выберем действие с вероятностью , а действие c вероятностью .
Совершив действие награда будет , совершив действие , награда будет .
Действие приведет нас в терминальное состояние с вероятностью . Действие приведет нас в состояние с вероятностью , а в с вероятностью .
Значение функций-состояния $v_{\pi}$ в состояниях и нам уже известны.
Давайте посчитаем функцию-состояния $v_{\pi}$ для нашего текущего состояния без учета дисконтирования (для корня дерева).

Просто считаем математическое ожидание:

$V(s) = \color{red}{0.3} \left[ \color{blue}{0.1} (\color{yellow}{1} + \color{green}{10}) + \color{blue}{0.9} (\color{yellow}{1} + \color{green}{-10}) \right] + \color{red}{0.7} \left[ \color{blue}{1.0} (\color{yellow}{0} + \color{green}{0}) \right] = 2.76$

Если мы посчитаем -функцию для каждого состояния , то сможем понять как нам надо поменять нашу политику $\pi$ , чтобы она стала о��тимальной: нам просто надо идти туда, где награда больше.

Как же можно посчитать -функцию? Рассмотрим два способа: матричный и метод простой итерации.

Policy Evaluation: matrix way (первый способ)

Посмотрим еще раз на уравнение : $v_{\pi}(s) = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r(s, a) + \gamma v_{\pi}(s') \right]$

Разделим его на две части: $v_{\pi}(s) = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r(s, a)\right] + \mathbb{E}_{a} \mathbb{E}_{s'} \gamma \left[v_{\pi}(s') \right]$

Проиндексировав все состояния, посмотрим на -функцию как на вектор: каждому состоянию будет соответствовать свое значение .

Математическое ожидание награды по действиям и по следующему состоянию обозначим матрицей $B = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r(s, a)\right]$ – вектор средних наград.

Вторую часть запишем в следующем виде: $\gamma P v = \gamma \mathbb{E}_{a} \mathbb{E}_{s'} \left[v_{\pi}(s') \right]$ , где $P_{s \times s}$ – матрица содержащая вероятности перехода из одного состояния в другое, то есть $P_{ij} = p(s_j | s_i)$ – вероятность попасть в состояние при условии с учетом текущей политики $\pi$ .

Тогда уравнение можно записать $v_{\pi} = B + \gamma P v_{\pi}$ .
Значения для, $\gamma$ и нам известны. Решим матричное уравнение относительно $v_{\pi}$ :

$(I - \gamma P) v_{\pi} = B$

$v_{\pi} = B(I - \gamma P)^{-1}$

Данное уравнение всегда разрешимо (это гарантирует $0 < \gamma \leq 1$ ), но вычисление обратной матрицы может быть дорого и неустойчиво.

Policy Evaluation: fixed-point iteration (второй способ)

Можно решить уравнение методом простой итерации (fixed-point iteration).

Метод заключается в том что мы будем обновлять оценку до тех пор, пока при подставлении её в правую часть уравнения Беллмана ничего не изменится.

То есть, итеративно для каждого состояния будем пересчитывать $v_{\pi}$ по следующей формуле: $v^{k+1}(s) = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r(s, a) + \gamma v^{k}(s') \right]$

1. Input: policy $\pi(a|s)$ , discount factor $\gamma$ , small threshold $0 < \gamma \leq 1$
2. Initialize $v_{\pi} = 0$
3. Repeat:
4. ____For in :
5. ____ ____ $v^{k+1}(s) = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r(s, a) + \gamma v^{k}(s') \right]$
6. ____ ____ $delta = max(delta, |v^{k+1} - v^{k}|)$
7. until $delta < \varepsilon$
8. output

Этот процесс сходится, потому что оператор Беллмана является сжимающим отображением при $0 <\gamma < 1$ .

6.3. Policy Improvement и action-value function q

Посчитав значения -функции хочется понять как именно улучшить политику.
Давайте будем сравнивать разные политики с помощью -функции:

$\pi \geq \pi' \iff v_\pi(s) \geq v_{\pi'} (s) \quad \forall s$

И пусть $\pi^*$ будет лучшей (оптимальной) политикой.

Мы хотим чтобы чтобы оптимальная политика $\pi^*$ вела нас в состояния с большими наградами. Однако, -функция не зависит от действия.

Тогда давайте выбирать то действие, у которого будет максимальна мгновенная награда + дисконтированная функция состояния:

$\pi'(a|s) = \arg \max_a \mathbb{E}_{s'} [R + \gamma v_{\pi}(s)]$

То есть, мы даем себе выбор первого действия в состоянии .
И для простоты обозначим это новой функцией $q_{\pi}(s, a)$ .

Action-value function q

Action-value function — математическое ожидание суммарной дисконтированной награды , если из состояния мы делаем первое действие (причем не обязательно соответствующее политике $\pi$ ), а дальше играем следуя политике $\pi$ .

$q_\pi(s, a) = \mathbb{E}_\pi \big[ G_t \mid S_t = s, A_t = a \big] =$
Проделаем все тоже самое, что и в state-value

$= \mathbb{E}_\pi \big[ R_t + \gamma G_{t+1} \mid S_t = s, A_t = a \big] =$

$= \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma \mathbb{E}_\pi \big[ G_{t+1} \mid S_{t+1} = s' \big] \Big] =$

Замечаем, что $\mathbb{E}_\pi \big[ G_{t+1} \mid S_{t+1} = s' \big]$ — это $v_\pi(s')$ и обнаруживаем, что можно выписать через :

$= \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma v_\pi(s') \Big]$

$q_{\pi}(s, a)$ (функция качества всех действий из состояния ) – говорит насколько хорошо выбрать действие в состоянии , если потом следовать политике $\pi$ .

Выше мы выписали -функцию через :

$[2] \quad\quad q_\pi(s, a) = \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma v_\pi(s') \Big]$

Или так:

$[2] \quad\quad q_\pi(s, a) = \mathbb{E}_{s'} [r + \gamma v_{\pi}(s')]$

Тогда новая политика $\pi'(a|s)$ должна выбирать $\arg\max_{a} q_{\pi}(s, a)$ :

$\pi'(a|s) = \arg\max_{a} q_{\pi}(s, a)$

Более того, улучшение политики через максимизацию -функции приводит к глобально оптимальной политике. Это называется Policy Improvement.

Посчитаем значение q-функции в состоянии s для действий a_0 и a_1:

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

Если мы знаем политику $\pi$ , то можем выписать -функцию через :

$v_\pi(s)= \sum_a \pi(a \mid s) \sum_{r, s'} p(r, s' \mid s, a) \big[ r + \gamma v_\pi(s') \big] =$

Заметим, что $\sum_{r, s'} p(r, s' \mid s, a) \big[ r + \gamma v_\pi(s') \big]$ в точности из формулы выше (где выражали через ). Получаем:

$[3] \quad \quad v_\pi(s) = \sum_a \pi(a \mid s) q_\pi(s, a)$

Подставив в формулу вместо $v_\pi (s')$ формулу получим рекуррентное соотношение для :

$[4] \quad \quad q_\pi(s, a) = \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma \sum_{a'} \pi(a' \mid s') q_\pi(s', a') \Big]$

6.4. Уравнения оптимальности Беллмана

Формулы , , , называются уравнениями Беллмана для математического ожидания.

$[1] \quad \quad v_\pi(s) = \sum_a \pi(a \mid s) \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma v_\pi(s') \Big]$

$[2] \quad\quad q_\pi(s, a) = \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma v_\pi(s') \Big]$

$[3] \quad \quad v_\pi(s) = \sum_a \pi(a \mid s) q_\pi(s, a)$

$[4] \quad \quad q_\pi(s, a) = \sum_{r, s'} p(r, s' \mid s, a) \Big[ r + \gamma \sum_{a'} \pi(a' \mid s') q_\pi(s', a') \Big]$

Данные уравнения являются ключевым результатом для построения всех последующих RL-алгоритмов.

Если $\pi_*$ — лучшая (оптимальная) политика.
Оптимальная state-value функция: $v_∗(s) = \max v_\pi(s)$ .
Оптимальная action-value функция : $q_∗(s,a)=max_\pi a_\pi(s,a)$ .

В любом конечном MDP существует хотя бы одна оптимальная политика.

Уравнение оптимальности Беллмана для — это то же уравнение Беллмана для мат. ожидания, только с максимумом по действиям (сравниваем действия между собой по будущей награде).

$[5] \quad \quad v_{*}(s) = \color{red}{\max_{a}} \mathbb{E}_{s'}[r + \gamma v_{*}(s')]$

Уравнение оптимальности Беллмана для отличается от уравнения Беллмана для мат. ожидания тем, что мы берем максимум по политике:

$[6] \quad \quad q_{*}(s, a) = \mathbb{E}_{s'} \left[ R + \gamma \color{red}{\max_{a'}} q_{*}(s', \color{red}{a'}) \right]$

Aналогично определим связь между и :

$[7] \quad \quad q_{*}(s, a) = \mathbb{E}_{s'} \left[ R + \gamma v_{*}(s') \right]$ $[8] \quad \quad v_{*}(s) = \max_{a} q_{*} (s, a)$

7. Generalized Policy Iteration

Policy Iteration — это алгоритм, который ищет оптимальную политику $\pi_*$ с помощью итеративного чередования двух шагов: оценки политики (policy evaluation) и улучшения политики (policy improvement).

policy = Initialize_policy()
while not optimal:
  # оцениваем политику (матрично или итеративно)
  v = Evaluate_Policy(policy)  
  # улучшим политику, взяв действие как argmax
  new_policy = imprive_policy(v)
  # проверяем, сошлись ли к глобально оптимальной политике
  is_optimal = [new_polixy == policy] 
  policy = new_policy

Подставим конкретные способы оценки и обновления политики:

В качестве оценки политикиEvaluate_Policy(policy) возьмем метод простой итерации: для всех состояний $s \in S$ будем применять уравнение Беллмана к , пока не сойдемся.

for some iterations:
  for s in S:
     v(s) = evaluate_policy_in_state(s, policy)

В качестве улучшения политики imprive_policy(v) возьмём жадное обновление по argmax: для всех состояний $s \in S$ будем выбирать действие, которое максимизирует ожидаемое значение награды $\arg \max_{a} q(s,a)$ .

for s in S:
  policy(s) = improve_polic_in_statr(s, v)

На практике можно улучшать политику не во всех состояниях, а в некоторых на каждом шаге. Или, можно оценивать политику только частично (ограничив число итераций), не доводя до сходимости. Тем не менее, даже при таком чередовании частичных шагов оценки и улучшения, алгоритм всё равно гарантированно сойдётся. Такой подход называется обобщённой итерацией по политике (Generalized Policy Iteration, GPI).

Из GPI вытекают два важных частных случая:

Policy Iteration (итерация по политике) — когда оценка политики проводится до сходимости, а затем выполняется полное жадное улучшение политики (его рассмотрели выше).
Value Iteration (итерация по значениям) — когда выполняется всего один шаг оценки (частичное обновление) и сразу жадное улучшение политики.

for 1 iterations:
  for s in S:
     v(s) = evaluate_policy_in_state(s, policy)

for s in S:
  policy(s) = improve_polic_in_statr(s, v)

Выкинем for по iterations и объединим в один цикл по S:

for s in S:
  v(s) = evaluate_policy_in_state(s, policy)
  policy(s) = improve_policy_in_statr(s, v)

Распишем шаг Policy Evaluation:
$v(s) = \mathbb{E}_{a} \mathbb{E}_{s'} \left[ r + \gamma v(s') \right]$

Шаг improve policy:
$\pi(s) = \arg \max_a \mathbb{E}_{s'} \left[ r + \gamma v(s') \right]$

Подставив одну операцию в другую и получим в точности уравнение Беллмана для оптимальных политик: $v(s) = \max_a \mathbb{E}_{s'} \left[ r + \gamma v(s') \right]$

Данный алгоритм – это метод простой итерации для оптимального уравнения Беллмана. Он будет сходиться, поскольку оптимальные уравнения Беллмана тоже являются операторами сжатия.

1. Initialize $V^{(0)}(s)=0$ , for all
2. For $i=0, 1, 2, \dots$
3. ____ $\quad V_{(i+1)}(s) = \max_a \sum_{s'} P(s' | s,a) \cdot [ r(s,a,s') + \gamma V_{i}(s')] \text{,} \quad \forall s$

Ноутбук потыкать (семинар с курса Practical RL). Надеюсь что все верно (• ◡•)

Резюмируя

RL(обучение с подкреплением) – обучение методом проб и ошибок.
Главное отличие от обучения с учителем – не требует размеченной выборки и дифференцируемой лосс функции.

Reward (награда) – скалярная величина, которая предоставляет какой-то «сигнал» для обучения (хорошо/плохо). Задача агента – максимизировать сумму наград.
Правильно выбрать функцию награды не так просто: с одной стороны надо награждать агента только за достижение цели, с другой награды не должны быть слишком редкими.
Для задач с бесконечными эпизодами добавили параметр дисконтирования $\gamma$ чтобы учитывать лишь часть будущих наград, а не накапливать бесконечную сумму.

State-value function – функция, показывающая насколько в текущем состоянии все хорошо. С помощью Policy Evaluation оцениваем для каждого состояния . Есть два способа: решить СЛАУ (matrix way) или с помощью методы простых итерций (fixed-point iteration).

Action-value function – функция, показывающая насколько хорошо в текущем состоянии совершить действие . Policy Improvement помогает выбрать оптимальное действие в состоянии (политику) как $\arg \max_a q(s, a_i)$ .

Generalized Policy Iteration – алгоритм поиска оптимальной стратегии путем чередования Policy Evaluation и Policy Improvement. Существует две крайности данного алгоритма: Policy Iteration и Value Iteration.

Policy Iteration – когда Policy Evaluation считается до сходимости.
1. Инициализируем $\pi_0$ (случайно или равновероятно)
2. For $n=0, 1, 2, \dots$
3. ____ Считаем state-value функцию $V^{\pi_{n}}$ (методом фиксированной точки)
4. ____ Используем $V^{\pi_{n}}$ для подсчета state-action-value функции $Q^{\pi_{n}}$
5. ____ Ищем новую политику $Q^{\pi_{n}} = \sum_{s'} P(s' | s,a) \cdot [ r(s,a,s') + \gamma V_{i}(s')]$

Value Iteration – когда выполняется всего один шаг Policy Evaluation и сразу Policy Improvement.
1. Инициализируем $V^{(0)}(s)=0$ (или еще чем-то)
2. For $i=0, 1, 2, \dots$
3. ____ $\quad V_{(i+1)}(s) = \max_a \sum_{s'} P(s' | s,a) \cdot [ r(s,a,s') + \gamma V_{i}(s')] \text{,} \quad \forall s$
4. Ищем политику как $\pi(s) = \operatorname*{argmax}_a Q(s,a)$ .

Рассуждения выше справедливы для относительно простых задач, где известна матрица переходов из одного состояния в другое при каждом действии. Такие задачи еще называют Model-based RL.

На данный момент готовлю вторую часть про задачи, когда нам не известна модель среды Model-free RL.

Intro Reinforcement Learning