notes/machine_learning/reinforcement_learning.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"tags": [
"обучение_с_подкреплением"
]
},
"source": [
"## Баланс между изучением и применением в задаче о многоруком бандите\n",
"\n",
"Задача о многоруком бандите (multi-armed bandit) формулируется так: имеется $n$ неизвестных вероятностных распределений, на каждом шаге даётся возможность просэмплировать случайную величину ровно из одного распределения и узнать её значение, а требуется совершить некоторое заранее заданное конечное число шагов так, чтобы сумма просэмплированных величин была наибольшей.\n",
"\n",
"В такой задаче возникает компромиссный выбор между пополнением знаний и применением уже накопленных знаний (exploration-exploitation dilemma). С одной стороны, после того, как из каждого распределения было просэмплировано сколько-то величин, можно просто далее сэмплировать величины только из распределения с наибольшим эмпирическим средним — это будет применение собранных знаний (exploitation). С другой стороны, оценки эмпирического среднего могут неточно приближать истинное среднее, и чем больше величин из распределения просэмплировано, тем точнее в смысле центральной предельной теоремы будет оценка среднего, так что имеет смысл сэмплировать величины из всех распределений — это будет пополнение знаний (exploration). Таким образом, нужно соблюсти оптимальный баланс между изучением и применением.\n",
"\n",
"Существуют следующие стратегии поиска баланса между изучением и применением:\n",
"* $\\varepsilon$-жадная стратегия: с вероятностью $\\varepsilon$ выбирать распределение, откуда сэмплировать значение на текущем шаге, равновероятно, а с вероятностью $(1 - \\varepsilon)$ сэмплировать значение из того распределения, которое имеет наибольшую текущую оценку среднего; параметр $\\varepsilon$ может быть константой, но лучше сделать, чтобы $\\varepsilon$ со временем затухал: например, положить $\\varepsilon = \\frac{1}{t}$, где $t$ — номер шага.\n",
"* Стратегия оптимистичных начальных значений: считать, что до первого шага оценки эмпирического среднего не неопределены, а равны какому-то чрезмерно завышенному значению, а сэмплировать всякий раз \"жадно\" — поскольку со временем оценки эмпирического среднего в таком случае будут только снижаться, это будет подталкивать изучать распределения, по которым собрано мало статистики, но из-за \"жадности\" не будет бесконечно долгого изучения.\n",
"* UCB, Upper Confidence Bound. Для $j$-го варианта рассчитанная полезность равна\n",
"$$\\overline{x}_j + \\sqrt{\\frac{2\\log n}{n_j}},$$\n",
"где $\\overline{x}_j$ — накопленное среднее при использовании $j$-го варианта, $n_j$ — количество предыдущих выборов $j$-го варианта, а $n$ — количество всех уже сделанных шагов. На каждом шаге выбирается тот вариант, у которого наибольшая рассчитанная полезность. На формулу рассчитанной полезности можно посмотреть как на эвристику, где к \"жадной\" полезности добавляется слагаемое, побуждающее исследовать, но у этой формулы есть и обоснование, восходящее к неравенству Хёффдинга.\n",
"* Сэмплирование Томпсона. Считается, что каждое распределение принадлежит к параметрическому семейству, параметры которого имеют своё собственное распределение (желательно такое, чтобы пара соответствующих распределений была сопряжённой). На каждом шаге происходит следующее:\n",
" - для каждого из вариантов сэмплируется значение его параметров;\n",
" - выбирается тот вариант, для которого при просэмплированных на предыдущем шаге параметрах математическое ожидание наибольшее;\n",
" - в зависимости от полученного значения-ответа обновляется распределение параметров выбранного варианта."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"обучение_с_подкреплением"
]
},
"source": [
"## Основные понятия обучения с подкреплением\n",
"\n",
"**Состояние (state), действие (action), награда (reward), агент (agent), среда (environment), наблюдение (observation), эпизод (episode)** — базовые понятия. В некоторый момент времени $t$ среда находится в состоянии $s_t$, а агент знает это состояние или по крайней мере получает наблюдение $o_t$, отражающее часть информации об $s_t$. На основании $s_t$ или $o_t$ агент совершает действие $a_t$, в результате чего момент времени становится равным $t+1$. В этот новый момент времени агент получает награду $r_{t+1} \\in \\mathbb{R}$, полностью или частично обусловленную действием $a_t$ (аналогично, в момент времени $t$ была награда $r_t$), а среда переходит в новое состояние $s_{t+1}$ и предоставляет наблюдение $o_{t+1}$. Может оказаться так, что в какой-то момент среда придёт в конечное состояние, из которого дальше нет ходов. Тогда говорят, что эпизод завершился.\n",
"\n",
"**Модель среды (environment model)** — формальное описание того, как устроена среда. Модель среды может быть известна, а может быть и неизвестна. Как правило, известность модели среды считают эквивалентной тому, что можно узнать любой элемент трёхмерных таблиц $\\mathcal{P}_{ss^{\\prime}}^a$ и $\\mathcal{R}_{ss^{\\prime}}^a$. Первая из них содержит вероятность перейти в состояние $s^{\\prime}$ при условии, что предыдущим состоянием было $s$ и было совершено действие $a$. Вторя содержит математические ожидания награды, которая выдаётся сразу же после того, как из состояния $s$ совершается действие $a$ и это приводит к приходу в состояние $s^{\\prime}$.\n",
"\n",
"**Стратегия (policy)** — формализация того, как агент выбирает действия. Начальная стратегия может быть взята произвольно; в дальнейшем целью является найти оптимальную стратегию. Обычно считают, что стратегия $\\pi$ — это отображение, которое состоянию среды (или наблюдению, доступному агенту, если состояние среды скрыто) сопоставляет вероятностное распределение на множестве всех действий.\n",
"\n",
"**Выигрыш (return, gain)** — то, математическое ожидание чего необходимо максимизировать. Пусть есть какая-то последовательность шагов взаимодействия агента со средой, то есть имеется последовательность действий $\\{a_t\\}$, совершённых агентом, и имеется последовательность наград $\\{r_t\\}$, полученных непосредственно после этих действий. Если среда предполагает конечные эпизоды, последовательность $\\{r_t\\}$ является конечной и состоит из всех наград, полученных от старта эпизода и вплоть до его заверешния. Если среда не предполагает наличие эпизодов, последовательность $\\{r_t\\}$ может быть бесконечной. Так вот, для некого момента времени $t$ определим ассоциированный с ним выигрыш как $G_t = \\sum_{i=0}^{+\\infty}\\gamma^i r_{t+i+1}$, где $0 < \\gamma \\le 1$ — гиперпараметр, называемый коэффициентом дисконтирования, а в случае конечных последовательностей суммирование прекращается с их концом. \n",
"\n",
"**Функции ценности (value functions)** — промежуточные понятия, отличающие обучение с подкреплением в узком смысле от других методов решения задач, где есть среда, агент и награда. Функция ценности состояния определяется как $V_\\pi(s) = \\mathbb{E}_\\pi [G_t \\, \\vert \\, s_t = s]$, где обозначение $\\mathbb{E}_\\pi$ указывает на то, что действия, награды за которые формируют $G_t$, совершаются в соответствии со стратегией $\\pi$. Функция ценности пары состояния и действия определяется как $Q_\\pi(s, a) = \\mathbb{E}_\\pi [G_t \\, \\vert \\, s_t = s, a_t = a]$. Зная $Q_\\pi$, всегда можно найти $V_\\pi$ по формуле $V_\\pi(s) = \\mathbb{P}_\\pi[a \\, \\vert \\, s] Q(s, a)$. Зная $V_\\pi$, получить $Q_\\pi$ можно, только если также известна модель среды: $Q_\\pi(s, a) = \\sum_{s^{\\prime}} \\mathcal{P}_{ss^{\\prime}}^a (\\mathcal{R}_{ss^{\\prime}}^a + \\gamma V_\\pi(s^{\\prime}))$. Хотя $Q_\\pi$ и сложнее оценить из-за большей размерности области определения, в задачах, где недоступна модель среды, оценивать приходится её, а не $V_\\pi$, потому что $V_\\pi$ может не позволить улучшить стратегию.\n",
"\n",
"**Задача предсказания (prediction problem)** — одна из двух задач, на которые разбивается задача обучения с подкреплением в узком смысле. В этой задаче есть возможность в соответствии с некоторой стратегией $\\pi^{\\prime}$ отыгрывать до конца эпизоды или, если среда не предполагает наличие эпизодов, просто совершать последовательности шагов. По собранным вышеописанным образом данным требуется оценить $V_\\pi$ или $Q_\\pi$. Если метод решения задачи предполагает, что $\\pi = \\pi^{\\prime}$, то такой метод называется методом с интегральной оценкой ценности (on-policy method). Если же не предполагается, что стратегия, порождающая данные, совпадает со стратегией, для которой ищется функция ценности, то такой метод называется методом с разделённой оценкой ценности (off-policy method).\n",
"\n",
"**Задача управления (control problem)** — вторая из двух задач, на которые разбивается задача обучения с подкреплением в узком смысле. В этой задаче есть возможность отыгрывать эпизоды или хотя бы совершать последовательности шагов, а на собранных таким образом данных решать задачу предсказания. Требуется же найти оптимальную стратегию. Примером подхода к решению является итерация по стратегии (policy iteration) — алгоритм, напоминающий EM-алгоритм. На вход подаётся некоторая детерминированная стратегия $\\pi_0$. На каждом этапе работы алгоритма для текущей стратегии $\\pi_i$ собираются данные и по ним оценивается $Q_{\\pi_i}$, а затем текущая стратегия обновляется до $\\pi_{i+1}$, являющейся жадной относительно $Q_{\\pi_i}$. Иными словами, берётся $\\pi_{i+1}(s) = \\arg\\max_a Q_{\\pi_i}(s, a)$. Если предположить, что $Q_{\\pi_i}$ оценена достаточно точно, будет применима теорема об улучшении стратегии и из неё будет следовать, что $\\pi_{i+1}$ не хуже $\\pi_i$, причём если они одинаковы, то обе они оптимальны."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"обучение_с_подкреплением",
"методы_оптимизации"
]
},
"source": [
"## Методы численной оптимизации и обучение с подкреплением\n",
"\n",
"Границы того, что относится к обучению с подкреплением, можно устанавливать по-разному. В относительно узкой трактовке, которая предлагалась, например, в первой редакции книги Саттона и Барто, в обучении с подкреплением обязательно должны присутствовать следующие составляющие:\n",
"* стратегия (policy), то есть то, что отображает наблюдение текущего состояния в действие (необязательно детерминированным образом);\n",
"* награда (reward), то есть то, что эпизоду (если они есть) или просто какой-то последовательности шагов (действий и получений обратной связи от среды) сопоставляет вещественное число (опять же, необязательно детерминированно);\n",
"* функция ценности (value function), то есть то, что отображает состояние в ожидаемую награду, которая будет получена, если прийти в это состояние и далее следовать имеющейся стратегии.\n",
"\n",
"На самом деле, при поиске стратегии, максимизирующей ожидаемую награду, можно обойтись и без функции ценности. Допустим, стратегия ищется в каком-либо параметрическом семействе. Тогда оптимальные значения параметров можно найти любым численным методом, предназначенным для так называемой black-box optimization.\n",
"\n",
"К задачам, решаемым при помощи обучения с подкреплением, успешно применяли метод [эволюционных стратегий](https://arxiv.org/pdf/1703.03864.pdf) и похожий на него метод [кросс-энтропии](http://web.mit.edu/6.454/www/www_fall_2003/gew/CEtutorial.pdf), а также различные генетические алгоритмы. Эти три метода можно отнести к методам, отталкивающимся от улучшения популяций. Помимо них можно применить и численные методы, основанные на иных эвристиках: например, метод имитации отжига (simulated annealing).\n",
"\n",
"Ещё стоит отметить, что к обучению с подкреплением относят методы градиента стратегии (в частности, Reinforce), но в них тоже не фигурирует функция ценности. \n",
"\n",
"Есть ли смысл вводить функцию ценности или нет, зависит от того, насколько ценна промежуточная информация, и от того, насколько велико пространство стратегий (если не очень, то функция ценности рискует стать переусложнением)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"обучение_с_подкреплением"
]
},
"source": [
"## TD($\\lambda$)-методы и следы приемлемости\n",
"\n",
"#### Введение\n",
"\n",
"TD($\\lambda$)-методы — методы решения задачи предсказания, то есть задачи оценки функции ценности для заданной стратегии. Эти методы образуют параметрическое семейство, включающее в себя в том числе TD(1)-метод, являющийся обобщением метода Монте-Карло. Для краткости в этой заметке будет разбираться оценивание функции ценности состояния $V_\\pi$. Для функции ценности пары состояния и действия $Q_\\pi$ всё выглядит аналогично.\n",
"\n",
"#### Прямой (концептуальный) подход\n",
"\n",
"Если задача предсказания решается методом Монте-Карло, то сначала собирается набор отыгранных в соответствии со стратегией $\\pi$ эпизодов, а затем по собранной статистике оценивается функция ценности $V_\\pi$. Но на это можно посмотреть и по-другому. Предположим, что $V_\\pi$ была инициализирована произвольно, а каждое посещение состояния $s$ (если речь идёт о методе Монте-Карло всех посещений) вносит инкрементальное обновление $V_\\pi(s)$. Тогда, чтобы получился именно метод Монте-Карло, такое обновление должно иметь вид:\n",
"$$V_\\pi(s) \\leftarrow V_\\pi(s) + c\\left(\\sum_{k=0}^{T - t - 1}\\gamma^k r_{t+k+1} - V_\\pi(s)\\right),$$\n",
"где $c$ — константа, зависящая в том числе от количества эпизодов и количества посещений $s$, $t$ — момент времени внутри эпизода, когда произошло рассматриваемое посещение $s$, $T$ — длина этого эпизода, а $\\{r_\\tau : 1 \\le \\tau \\le T\\}$ — последовательность наград, которые были получены после каждого из шагов этого эпизода. Иными словами, посещение состояния $s$ в момент времени $t$ сдвигает оценку $V_\\pi(s)$ в сторону следующей величины:\n",
"$$R_t = \\sum_{k=0}^{T - t - 1}\\gamma^k r_{t+k+1}.$$\n",
"Эта величина подсчитана исключительно по фактическим наградам, и, как следствие, она неизвестна до тех пор, пока эпизод не завершён.\n",
"\n",
"Рассмотрим оценку величины $R_t$, которую можно подсчитать спустя $n$ шагов после момента времени $t$:\n",
"$$R_t^{(n)} = \\sum_{k=0}^{n - 1}\\gamma^k r_{t+k+1} + \\gamma^n V_\\pi(s_{t+n}).$$\n",
"Уточним также, что если $t+n > T$, то по определению $R_t^{(n)} = R_t$. Так определённая оценка $R_t^{(n)}$ отличается от $R_t$ тем, что приведённая сумма наград за поздние шаги заменяется значением функции ценности того состояния, из которого эти шаги были совершены.\n",
"\n",
"Можно делать обновления не в сторону $R_t$, а в сторону $R_t^{(n)}$. Например, то, что называется TD-метод (он же TD(0)-метод, поскольку является частным случаем TD($\\lambda$)-метода при $\\lambda = 0$), делает обновления в сторону $R_t^{(1)}$.\n",
"\n",
"Тут уместно обратить внимание на один нюанс. Вообще-то, классический метод Монте-Карло не предполагает инкрементальных обновлений: вместо них происходит усреднение уже после того, как отыграны все эпизоды (поэтому этот метод можно назвать оффлайновым). Как следствие, не возникает вопроса о том, когда обновлять $V_\\pi$. Однако в определении $R_t^{(n)}$ участвует $V_\\pi$, так что то, когда она обновляется, становится важным. Помимо оффлайнового варианта возможны и онлайновые — например, такой: обновлять сразу же, как только $R_t^{(n)}$ становится известной. Тем самым $V_\\pi$ будет меняться в процессе отыгрывания эпизодов. Преимущество этого варианта в том, что в отличие от классического метода Монте-Карло его можно применять и к средам, где нет конечных эпизодов и последовательности шагов могут быть бесконечными.\n",
"\n",
"Наконец, перейдём к концептуальному определению TD($\\lambda$)-метода. Это метод, в котором есть гиперпараметр $0 \\le \\lambda \\le 1$ и в котором обновления функции ценности происходят в сторону следующей величины:\n",
"$$(1 - \\lambda)\\sum_{n=1}^{+\\infty} \\lambda^{n-1} R_t^{(n)}.$$\n",
"Чем такое определение хорошо, так это тем, что оно даёт интерпретацию, в какую сторону происходят обновления: в сторону средневзвешенного между обновлениями TD-метода, метода Монте-Карло и промежуточных между этими двумя крайностями вариантов. Чем такое определение плохо, так это тем, что напрямую по нему нельзя создать алгоритм, способный совершать обновления после каждого шага, ведь большая часть слагаемых к тому времени будет неизвестна.\n",
"\n",
"#### Обратный (механистический) подход\n",
"\n",
"У TD($\\lambda$)-метода есть и альтернативное определение, позволяющее обновлять $V_\\pi$ на каждом шаге.\n",
"\n",
"В виде псевдокода это определение записывается так:\n",
"* Инициализировать $V_\\pi$ произвольно\n",
"* Для каждого состояния $s$ положить $e(s) = 0$\n",
"* Для каждого эпизода:\n",
" - Инициализировать $s$ начальным состоянием\n",
" - Пока эпизод не завершился:\n",
" - Совершить действие $a$ в соответствии с заданной стратегией $\\pi$\n",
" - Получить вознаграждение $r$ и следующее состояние $s^{\\prime}$\n",
" - $\\delta \\leftarrow r + \\gamma V_\\pi(s^{\\prime}) - V_\\pi(s)$\n",
" - Для всех состояний $z$:\n",
" - $V_\\pi(z) \\leftarrow V_\\pi(z) + \\alpha e(z) \\delta$, где $\\alpha$ — гиперпараметр темпа обучения\n",
" - $e(z) \\leftarrow \\gamma\\lambda e(z)$\n",
" - $e(s) \\leftarrow e(s) + 1$\n",
" - $s \\leftarrow s^{\\prime}$\n",
" \n",
"Из этой онлайновой версии можно получить оффлайновую, на протяжении эпизода суммируя обновления для $V_\\pi$, но применяя их только после конца эпизода.\n",
"\n",
"Величина $e(s)$ называется следом приемлемости (eligibility trace) состояния $s$. Она, образно говоря, показывает, какая доля текущего обновления $\\delta$ должна быть применена к состоянию $s$, чтобы это обновление было учтено с тем же весом, с каким оно учитывается в прямом подходе. Выкладкой можно показать, что прямой и обратный подход дают одинаковые результаты."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"обучение_с_подкреплением"
]
},
"source": [
"## Некоторые табличные методы обучения с подкреплением\n",
"\n",
"#### Введение\n",
"\n",
"Метод обучения с подкреплением называется табличным, если функция ценности для него ищется в виде таблицы, где в одном столбце содержится значение состояния (для функции ценности состояния $V_\\pi$) или пары из состояния и действия (для функции ценности пары состояния и действия $Q_\\pi$), а в другом столбце содержится соответствующее значение функции. Разумеется, табличные методы работают, только если количество возможных состояний или пар состояния и действия невелико. В случае, когда их количество велико, используют аппроксимационные методы. Впрочем, для многих табличных методов легко получить их аппроксимационные версии.\n",
"\n",
"#### SARSA\n",
"\n",
"Для решения задачи предсказания в методе SARSA функция $Q_\\pi$ оценивается интегрально (on-policy) TD(0)-методом со следующей формулой обновления:\n",
"$$Q_\\pi(s_t, a_t) \\leftarrow Q_\\pi(s_t, a_t) - \\alpha(r_{t+1} + \\gamma Q_\\pi(s_{t+1}, a_{t+1}) - Q_\\pi(s_t, a_t)),$$\n",
"где последовательности $\\{s_t\\}$, $\\{a_t\\}$ и $\\{r_t\\}$ были получены при следовании текущей стратегии $\\pi$.\n",
"\n",
"Способ решения задачи управления является частным случаем обобщённой итерации по стратегии. После каждого шага (действия и вызванного им перехода в новое состояние) происходит обновление ровно одного значения $Q$-таблицы, а текущая стратегия $\\pi$ тоже обновляется после каждого шага.\n",
"\n",
"В виде псевдокода алгоритм SARSA записывается так:\n",
"* Инициализировать $Q$-таблицу для всех пар $(s, a)$ произвольным образом с единственным условием, что если $s$ — конечное состояние, из которого больше нет ходов, то $Q(s, \\cdot) = 0$\n",
"* Для каждого эпизода:\n",
" - Инициализировать $s$ начальным состоянием\n",
" - Положить стратегию $\\pi$ равной некоторой стратегии, основанной на текущей $Q$-таблице (например, стратегии, $\\varepsilon$-жадной относительно $Q$)\n",
" - Выбрать (но пока не совершать) действие $a$ в соответствии со стратегией $\\pi$, применённой к состоянию $s$\n",
" - Пока эпизод не завершился:\n",
" - Совершить действие $a$\n",
" - Получить награду $r$ и новое состояние $s^{\\prime}$\n",
" - Выбрать (но пока не совершать) действие $a^{\\prime}$ в соответствии со стратегией $\\pi$, применённой к состоянию $s^{\\prime}$\n",
" - Обновить одну ячейку $Q$-таблицы: $Q(s, a) \\leftarrow Q(s, a) + \\alpha(r + \\gamma Q(s^{\\prime}, a^{\\prime}) - Q(s, a))$\n",
" - Положить стратегию $\\pi$ равной некоторой стратегии, основанной на обновлённой $Q$-таблице (например, стратегии, $\\varepsilon$-жадной относительно $Q$)\n",
" - $a \\leftarrow a^{\\prime}$, $s \\leftarrow s^{\\prime}$\n",
" \n",
"#### Q-обучение\n",
"\n",
"Для решения задачи предсказания в методе Q-обучения $Q$-таблица оценивается раздельно (off-policy) TD(0)-методом со следующей формулой обновления:\n",
"$$Q(s_t, a_t) \\leftarrow Q(s_t, a_t) - \\alpha(r_{t+1} + \\gamma \\max_a Q(s_{t+1}, a) - Q(s_t, a_t)),$$\n",
"где последовательности $\\{s_t\\}$, $\\{a_t\\}$ и $\\{r_t\\}$ были получены при следовании некой стратегии $\\pi$, не обязанной быть оптимальной относительно $Q$-таблицы.\n",
"\n",
"Как и для SARSA способ решения задачи управления является частным случаем обобщённой итерации по стратегии. Обновление одного из значений $Q$-таблицы и обновление стратегии $\\pi$ происходят после каждого шага. Однако в отличие от SARSA $Q$-таблица представляет собой оценку функции ценности оптимальной стратегии, а не оценку функции ценности текущей стратегии $\\pi$.\n",
"\n",
"В виде псевдокода алгоритм Q-обучения записывается так:\n",
"* Инициализировать $Q$-таблицу для всех пар $(s, a)$ произвольным образом с единственным условием, что если $s$ — конечное состояние, из которого больше нет ходов, то $Q(s, \\cdot) = 0$\n",
"* Для каждого эпизода:\n",
" - Инициализировать $s$ начальным состоянием\n",
" - Пока эпизод не завершился:\n",
" - Положить стратегию $\\pi$ равной некоторой стратегии, основанной на текущей $Q$-таблице (например, стратегии, $\\varepsilon$-жадной относительно $Q$)\n",
" - Выбрать и совершить действие $a$ в соответствии со стратегией $\\pi$, применённой к состоянию $s$\n",
" - Получить награду $r$ и новое состояние $s^{\\prime}$\n",
" - Обновить одну ячейку $Q$-таблицы: $Q(s, a) \\leftarrow Q(s, a) + \\alpha(r + \\gamma \\max_{a^{\\prime}} Q(s^{\\prime}, a^{\\prime}) - Q(s, a))$\n",
" - $s \\leftarrow s^{\\prime}$"
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 2
}