Изменения

Окружение В обучении с подкреплением существует агент (''agent'') взаимодействует с окружающей средой (''environment''), предпринимая действия (''actions''). Окружающая среда дает награду (''reward'') за эти действия, а агент продолжает их предпринимать. Алгоритмы с частичным обучением пытаются найти стратегию, приписывающую состояниям (''states'') окружающей среды действия, одно из которых может выбрать агент в этих состояниях. Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.

При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары „входные "входные данные-ответ“ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний(''exploration vs exploitation'').Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандитао многоруком бандите].

Формально простейшая модель обучения с подкреплением состоит из:# * множества состояний окружения (''states'') <itex>S</itex>;# * множества действий (''actions'') <itex>A</itex>;# * множества вещественнозначных скалярных "выигрышей"(''rewards'').

В произвольный момент времени <itex>t</itex> агент характеризуется состоянием <tex>s_t \in S</tex> и множеством возможных действий <tex>A(s_t)</tex>.

Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию <tex>\pi: S \to A</tex>, которая максимизирует величину <tex>R=r_0 + r_1+\cdots+r_n</tex> в случае МППР, имеющего терминальное состояние, или величину <br />: ::<tex>R=\sum_t \gamma^t r_t</tex> <br /> , для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{--- }} дисконтирующий множитель для „предстоящего выигрыша“"предстоящего выигрыша").

[[File:Simple_RLRL.png|thumb|RLlink=https://econophysica.ru/services/machine-схемаlearning/|Взаимодействие агента со средой]] <tex>S</tex> {{---}} множество состояний среды

# * инициализация стратегии <tex>\pi_1(a|s)</tex> и состояния среды <tex>s_1</tex>;# * для всех <tex>t = 1..\ldots T</tex>:## ** агент выбирает действие <tex>a_t ∼ \pi_t(a|s_t)</tex>;## ** среда генерирует премию награду <tex>r_{t + 1} ∼ p(r|a_t, s_t)</tex> и новое состояние <tex>s_{t + 1} ∼ p(s|a_t, s_t)</tex>;## ** агент корректирует стратегию <tex>\pi_{t + 1}(a|s)</tex>.

<tex>P(s_{t+1} = s′, r_{t+1} = r | s_t, a_t, r_t, s_{t−1}, a_{t−1}, r_{t−1}, .. ,s_1, a_1) == P(s_{t+1} = s′,r_{t+1} = r | s_t, a_t)</tex>,

# * опробовать все возможные стратегии;# * выбрать стратегию с наибольшим ожидаемым выигрышем.

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

При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния <itex>s</itex>, при дальнейшем следовании стратегии <tex>\pi</tex>, <br />::<tex>V(s)=E[R|s,\pi]</tex>, <br />либо ожидаемый выигрыш, при принятии решения <i>a</i> в состоянии <i>s</i> и дальнейшем соблюдении <tex>\pi</tex>, <br />::<tex>Q(s,a)=E[R|s,\pi,a]</tex>. <br />Если для выбора оптимальной стратегии используется функция полезности <i>Q</i>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.Если же мы пользуемся функцией <i>V</i>, необходимо либо иметь модель окружения в виде вероятностей <tex>P(s'|s,a)</tex>, что позволяет построить функцию полезности вида <br />::<tex>Q(s,a)=\sum_{s'}V(s')P(s'|s,a)</tex>, <br />либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния <i>V</i>, и исполнитель, выбирающий подходящее действие в каждом состоянии.

::<tex>V(s) = E[R|s, \pi]</tex>, либо ожидаемый выигрыш, при принятии решения <tex>a</tex> в состоянии <tex>s</tex> и дальнейшем соблюдении <tex>\pi</tex>, ::<tex>Q(s, a) = E[R|s, \pi, a]</tex>, Если для выбора оптимальной стратегии используется функция полезности <tex>Q</tex>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность. Если же мы пользуемся функцией <tex>V</tex>, необходимо либо иметь модель окружения в виде вероятностей <tex>P(s'|s, a)</tex>, что позволяет построить функцию полезности вида ::<tex>Q(s, a) = \sum_{s'}V(s')P(s'|s, a)</tex>, либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния <tex>V</tex>, и исполнитель, выбирающий подходящее действие в каждом состоянии. Имея фиксированную стратегию <tex>\pi</tex>, оценить <tex>E[R|\cdot]</tex> при <tex>\gamma=01</tex> можно просто усреднив непосредственные выигрыши.Наиболее очевидный способ оценки при <tex>\gamma>\in (0, 1)</tex> — {{---}} усреднить суммарный выигрыш после каждого состояния.

Поэтому построение искомой оценки при <tex>\gamma>\in (0, 1)</tex> неочевидно. Однако, можно заметить, что <itex>R</itex> образуют рекурсивное уравнение Беллмана: <br /> ::<tex>E[R|s_t]=r_t+\gamma E[R|s_{t+1}]</tex>. <br />, Подставляя имеющиеся оценки, <itex>V</itex>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями](''temporal difference (TD) learning'').

== Задача о многоруком бандите (''The multi-armed bandit problem'') ==

[[File:bandit.jpg|thumb|link=http://toppromotion.ru/blog/seo-category/novyij-algoritm-pod-nazvaniem-%C2%ABmnogorukij-bandit%C2%BB.html|Многорукий бандит]]

 <tex>A</tex> — {{---}} множество возможных ''действий'' <br />(ручек автомата), <tex>p_a(r)</tex> — {{---}} неизвестное распределение ''награды'' <tex>r \in R</tex> за <tex>\forall a \in A</tex> <br />, <tex>\pi_t(a)</tex> — {{---}} ''стратегия'' агента в момент <tex>t</tex>, распределение на <tex>\forall a \in A</tex> <br />. 

# * инициализация стратегии <tex>\pi_1(a)</tex>;# * для всех <tex>t = 1..\ldots T</tex>:## ** агент выбирает действие (ручку) <tex>a_t ∼ \pi_t(a)</tex>;## ** среда генерирует награду <tex>r_t ∼ p_{a_t}(r)</tex>;## ** агент корректирует стратегию <tex>\pi_{t+1}(a)</tex>. <tex>Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max </tex> {{---}} средняя награда в <i>t</i> играх <br />,<tex>Q^∗(a) = \lim \limits_{t \rightarrow \infty} Q_t(a) \rightarrow max </tex> {{---}} ценность действия <tex>a</tex>. У нас есть автомат {{---}} <tex>N</tex>-рукий бандит, на каждом шаге мы выбираем за какую из <tex>N</tex> ручек автомата дернуть,т.е. множество действий <tex>A = {1,2 \ldots ,N}</tex>. Выбор действия <tex>a_t</tex> на шаге <tex>t</tex> влечет награду <tex>R(a_t)</tex> при этом <tex>R(a)</tex> <tex>\forall a \in A</tex> есть случайная величина, распределение которой неизвестно. Состояние среды у нас от шага к шагу не меняется, а значит множество состояний <tex>S</tex> тривиально, ни на что не влияет, поэтому его можно проигнорировать. Для простоты будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали эти распределения, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге. Проблема в том, что распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением. Для <tex>K</tex> экспериментов <tex>\xi_k</tex>, оценка математического ожидания это среднее арифметическое результатов экспериментов: <tex>E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex>, Задача является модельной для понимания конфликта между ''exploitation''-''exploration''. === Жадные и <tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===  ==== Жадная (''greedy'') стратегия ====

* <tex>Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i P_a = a]}} \rightarrow max 0</tex> — средняя награда в <i>t</i> играх <br /><tex>Q^∗(\forall a) = \lim in \limits_{y 1 \rightarrow ldots N\infty} Q_t(a) \rightarrow max </tex> — ценность действия {{---}} сколько раз было выбрано действие <tex>a</tex>,

Задача выглядит следующим образом. <br />У нас есть автомат - ":<tex>N</tex>-рукий бандит", на каждом шаге мы выбираем за какую из <tex>N</tex> рук автомата дернуть,т.е. множество действий будет <tex>Aa_t =argmax_{1,2,…,N}</tex>.<br />Выбор действия <tex>a_t</tex>, на шаге <tex>t</tex>, влечет награду <tex>R(a_t)</tex> при этом <tex>R(a), a \in A</tex> есть случайная величина, распределение которой мы не знаем. Состояние среды у нас от шага к шагу не меняется, а значит множество <tex>S = \{s\}Q_a </tex> тривиально, ни на что не влияет, так что мы его игнорируем.<br />

Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать * Выполняем действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.<br />Проблема ровно одна: про распределения мы ничего не знаем.<br />Однако, оценивать математическое ожидание некоторой случайной величины <tex>\xia_t</tex> c неизвестным распределением мы умеем. Делаем <tex>P</tex> экспериментов, и получаем награду <tex>{\xi_p|p=1..P}R(a_t)</tex> величин, берем среднее арифметическое:;

* Обновляем оценку математического ожидания для действия <tex>\xi′ = \frac{1}{P} \cdot \sum_{p=1}^{P}{\xi_p} a_t</tex>:

это и будет оценка математического ожидания. Очевидно, что чем больше :<tex>PP_{a_t} = P_{a_t} + 1</tex> тем оценка точнее.,

:<tex>Q_{a_t} == Жадные и эпсилон-жадные стратегии == Q_{a_t} + \frac{1}{P_{a_t}} (R(a_t) − Q_{a_t})</tex>.

Заведем массивы <br /><tex>\{P_a=0|a=1В данном случае достаточно попробовать в начале каждую из ручек вместо того,…,N\}</tex>, <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex> <br />чтобы фокусироваться только на одной.<tex>\{Q_a=0|a=1,…,N\}</tex>Но если награда случайная величина, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>то единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:

На каждом шаге <tex>t</tex>.<br />Выбираем действие с максимальной оценкой математического ожидания: <br /><tex>a_t = argmax\{Q_a|a=1..N\}== </tex> \epsilon<br />Выполняем действие at и получаем награду <tex>R_t-жадная (</tex> <br />Обновляем оценку математического ожидания для действия <tex>a_t\epsilon</tex>: <br /><tex>P_{a_t} -''greedy'') стратегия === P_{a_{t+1}}</tex> <br /><tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t} (R_t − Q_{a_t})</tex>

Пример.Введем параметр <br /tex>Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную \epsilon \in (0,1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до <tex>Q_1 = 1</tex>. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.

* Получим значение <tex>\epsilonalpha</tex>{{---жадная }} случайной величины равномерно распределенной на отрезке <tex>(0, 1)</tex>;* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>a_t \in A</tex>-greedy) стратегияслучайно и равновероятно, иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания;* Обновляем оценки так же как в жадной стратегии.

Зададимся некоторым параметром Если <tex>\epsilon = 0</tex>, то это обычная жадная стратегия. Однако если <tex>\in (epsilon > 0</tex>,1)то в отличии от жадной стратегии на каждом шаге с вероятностью <tex>\epsilon</tex>присходит "исследование" случайных действий.

Заведем массивы<br /><tex>\{P_a=0|a=1,…,N\}</tex>, <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex> <br /><tex>\{Q_a=0|aСтратегия Softmax ===1,…,N\}</tex>, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>

На каждом шаге <tex>t</tex>Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом.<br />Получаем значение <tex>\alpha</tex> случайной величины равномерно расределенной Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на отрезке <tex>(0,1)базе которого происходит выбор действия. Чем больше </tex> <br />Если <tex>\alpha \in Q_t(0,\epsilona)</tex>, то выберем действие тем больше вероятность выбора <tex>a_ta</tex> из набора <tex>A</tex> случайно и равновероятно. <br />:

<tex>a_t = argmax{Q_a|a=1,...\tau \in (0,N}\infty)</tex> <br />Выполняем действие <tex>a_t</tex> и получаем награду <tex>R_t</tex> <br />Обновляем оценку математического ожидания для действия <tex>a_t</tex>:{{---}} параметр, с помощью которого можно настраивать поведение алгоритма.

При <tex>P_{a_t} = P_{a_{t+1}}\tau \rightarrow \infty</tex> <br /><tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t} стратегия стремится к равномерной, то есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (R_t−Q_{a_t}exploration)</tex>.

Ясно, что если выбрать При <tex>\epsilon = tau \rightarrow 0</tex> мы вернемся стратегия стремится к просто жадной стратегии. Однако, если <tex>\epsilon > 0</tex>, в отличии от просто "жадной", у нас то есть алгоритм будет больше ориентироваться на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование"известный средний выигрыш действий (exploitation).

Пример. Награда Экспонента используется для стратегии с различными <tex>\epsilon</tex>:[[File:Eps-greedyтого, чтобы данный вес был ненулевым даже у действий, награда от которых пока нулевая.png]]

Алгоритм верхнего доверительного интервала (''Upper confidence bound'' или просто UCB) - это семейство алгоритмов, которые пытаются решить эту проблему, используя Предыдущие алгоритмы при выборе принятии решения используют данные не только о среднем выигрыше, но и о . Проблема в том, насколько можно доверять этим значениям выигрыша. В книге описывается один такой алгоритм что если действие даёт награду с какой- UCBто вероятностью, то данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие.

Как и в softmax в UCB при выборе рук используется весовой коэффициент, который представляет собой верхнюю границу Алгоритм верхнего доверительного интервала (''upper confidence bound'' или UCB) {{---}} семейство алгоритмов, что которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и дало название алгоритму) значения о том, насколько можно доверять значениям выигрыша:.

<tex>Q_a = average_arm_reward + arm_bonus</tex><br /><tex>average_arm_reward</tex> - это среднее значение Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.:

<tex>arm_bonus\pi_{t+1}(a) = Q_t(a) + b_a</tex> - это бонусное значение, которые показывает, насколько недоисследована эта рука по сравнению с остальными. Он вычисляется следующим образом:

<tex>arm_bonus b_a = \sqrt{\frac{2 \cdot ln{\log{total_countsum_a P_a}}{arm_countP_a}} </tex><tex>total_count</tex> {{--- это суммарное количество использований всех рук}} бонусное значение, которые показывает, а <tex>arm_count</tex> - это количество использований данной рукинасколько недоисследовано действие по сравнению с остальными.

В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора рукидействия, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждая каждое из рук действий выбирается по одному разу (это нужно для того, чтобы можно было вычислить размер бонуса для всех рукдействий). После этого в каждый момент времени выбирается рука действие с максимальным значением весового коэффициента.

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

== Стратегия Softmax Q-learning ==

Алгоритм мягкого максимума (softmax) На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{-- это чуть более сложный алгоритм. Его основная идея - уменьшение потерь при исследовании за счёт более редкого выбора рук}} то, которые дали маленький выигрыш что оно в прошломсостоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Чтобы этого добиться Применяется для каждой руки вычисляется весовой коэффициентситуаций, на базе которого происходит выбор руки:которые можно представить в виде МППР.

:<tex>average_arm_rewardQ: S \times A \to \mathbb{R}</tex> - это среднее значение выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам.,

temperature - это параметрПеред обучением <tex>Q</tex> инициализируется случайными значениями. После этого в каждый момент времени <tex>t</tex> агент выбирает действие <tex>a_t</tex>, с помощью которого можно настраивать поведение алгоритма (он называется температура). Он получает награду <tex>r_t</tex>, переходит в новое состояние <tex>s_{t+1}</tex>, которое может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша предыдущего состояния <tex>s_t</tex> и выбирать руки более равномерно (т.е. перейдёт в режим исследования). Если он близок к нулювыбранного действия, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации)и обновляет функцию <tex>Q</tex>.Обновление функции использует взвешенное среднее между старым и новым значениями:

Экспонента используется для того:<tex>Q^{new}(s_{t}, чтобы данный вес был ненулевым даже у рукa_{t}) \leftarrow (1-\alpha) \cdot \underbrace{Q(s_{t},a_{t})}_{\text{old value}} + \underbrace{\alpha}_{\text{learning rate}} \cdot \overbrace{\bigg( \underbrace{r_{t}}_{\text{reward}} + \underbrace{\gamma}_{\text{discount factor}} \cdot \underbrace{\max_{a}Q(s_{t+1}, a)}_{\text{estimate of optimal future value}} \bigg) }^{\text{learned value}} </tex>, выигрыш от которых пока нулевой.

Вероятность выбора руки равна отношению её весового коэффициента где ''<tex>r_{t}</tex>'' это награда, полученная при переходе из состояния <tex>s_{t}</tex> в состояние <tex>s_{t+1}</tex>, и сумме весовых коэффициентов всех рук. При выборе генерируется случайное число от <tex>\alpha</tex> это скорость обучения (<tex>0 до < \alpha \le 1, на основании которого произойдёт выбор конкретной руки</tex>).

Мягкий вариант компромисса "exploitationАлгоритм заканчивается, когда агент переходит в терминальное состояние <tex>s_{t+1}</tex>. === Aлгоритм Q-exploration"learning === [[File:Q-Learning.png|thumb|313px|link=https:<br />/en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]] чем больше * <tex>Q_t(a)S</tex>— множество состояний, тем больше вероятность выбора * <tex>aA</tex>: <br />— множество действий,* <tex>\pi_{t+1}(a) R = S \frac{exp(Q_t(a)/τ)}{times A \sum\limits_{b rightarrow \in A} mathbb{exp(Q_t(b)/τ)}R}</tex> <br />{{---}} функция награды,где * <tex>T = S \tautimes A \rightarrow S</tex> — параметр температуры{{---}} функция перехода,<br />при * <tex>\tau alpha \rightarrow in [0, 1]</tex> стратегия стремится к жадной{{---}} learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации,<br />при * <tex>\tau gamma \rightarrow \inftyin [0, 1]</tex> — к равномерной{{---}} discounting factor, чем он меньше, т.е. чисто исследовательской<br />Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временемтем меньше агент задумывается о выгоде от будущих своих действий.

'''fun''' Q-learning(<tex>S, A, R, T, \alpha, \gamma</tex>): '''for''' <tex> s \in S</tex>: '''for''' <tex> a \in A</tex>: Q(s, a) = rand() '''while''' Q is not converged: s = <tex> \forall s \in S</tex> '''while''' s is not terminal: <tex>\pi(s) = argmax_{a}{Q(s, a)}</tex> a = <tex>\pi(s)</tex> r =R(s, a) s' = T(s, a) <tex>Q(s', a) = (1 -learning =\alpha) Q(s', a) + \alpha (r + \gamma \max\limits_{a'}{Q(s', a')})</tex> s = s' return Q