Изменения

Окружение В обучении с подкреплением существует агент (''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:RL.png|thumb|link=https://econophysica.ru/services/machine-learning/|Взаимодействие агента со средой]] <itex>S</itex> {{- --}} множество состояний среды <br /> 

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

Имея фиксированную стратегию <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> {{---}} множество возможных ''действий'' (ручек автомата),pa<tex>p_a(r) — </tex> {{---}} неизвестное распределение премии ''награды'' <tex>r ∈ \in R за ∀a ∈ </tex> <tex>\forall a \in A</tex>,πt<tex>\pi_t(a) — </tex> {{---}} ''стратегия '' агента в момент <tex>t, распределение на </tex> <tex>\forall a \in A</tex>. 

1: * инициализация стратегии π1<tex>\pi_1(a)</tex>;2: * для всех <tex>t = 1, . . . \ldots T, . . .</tex>:3: ** агент выбирает действие at (ручку) <tex>a_t ∼ πt\pi_t(a)</tex>;4: ** среда генерирует премию rt награду <tex>r_t ∼ patp_{a_t}(r)</tex>;5: ** агент корректирует стратегию πt<tex>\pi_{t+1}(a);</tex>. Qt<tex>Q_t(a) =Pt\frac{\sum^{t}_{i=1 ri}{r_i[ai a_i = a]Pt}}{\sum^{t}_{i=1}{[ai a_i = a]→ }} \rightarrow max — </tex> {{---}} средняя премия награда в <i>t </i> играх<br />,Q∗<tex>Q^∗(a) = limt→∞Qt\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>.

Задача является модельной для понимания конфликта между exploitation (применениеПроблема в том, эксплуатация) и exploration (изучениечто распределения неизвестны, исследование)однако можно оценить математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением.Для <tex>K</tex> экспериментов <tex>\xi_k</tex>, оценка математического ожидания это среднее арифметическое результатов экспериментов:

Задача выглядит следующим образом. У нас есть автомат - “N-рукий бандит”, на каждом шаге мы выбираем за какую из N рук автомата дернуть, т.е. множество действий будет A<tex>E(\xi) =\frac{1,2,…,N}. Выбор действия at, на шаге t, влечет награду R(at) при этом R(a),a∈A есть случайная величина, распределение которой мы не знаем. Состояние среды у нас от шага к шагу не меняется, а значит множество S{K} \sum_{k=1}^{K}{s\xi_k} тривиально, ни на что не влияет</tex>, так что мы его игнорируем.

Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание Задача является модельной для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге. Проблема ровно одна: про распределения мы ничего не знаемпонимания конфликта между ''exploitation''-''exploration''.

Однако, оценивать математическое ожидание некоторой случайной величины ξ c неизвестным распределением мы умеем. Делаем P экспериментов, получаем {ξp|p=1,…,P} величин, берем среднее арифметическое:== Жадные и <tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===

ξ′=1P∑p=1Pξp,это и будет оценка математического ожидания. Очевидно, что чем больше P тем оценка точнее.== Жадная (''greedy'') стратегия ====

* <tex>Q_a == Жадные и эпсилон0</tex> <tex>\forall a \in \{1 \ldots N\}</tex> {{---жадные стратегии == Объединяя всё вышеизложенное, получаем простую “жадную” стратегию}} текущая оценка математического ожидания награды для действия <tex>a</tex>.

{Pa=0|a:<tex>a_t =1,…,N}, Pa - сколько раз было выбрано действие aargmax_{Qa=0|a=1,…,N\in A}Q_a </tex>, Qa - текущая оценка математического ожидания награды для действия aНа каждом шаге t.

Выбираем * Выполняем действие с максимальной оценкой математического ожидания:<tex>a_t</tex> и получаем награду <tex>R(a_t)</tex>;

at=argmax{Qa|a=1,...,N}Выполняем действие at и получаем награду Rt* Обновляем оценку математического ожидания для действия at <tex>a_t</tex>:

Pat:<tex>P_{a_t} =PatP_{a_t} +1Qat=Qat+1Pat(Rt−Qat)</tex>,

Пример.Пусть у нас есть “двурукий” бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до Q1=1. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, В чем могли бы.проблема?

ТПусть у нас есть "двурукий" бандит.еПервая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. желательно всё таки не фиксироваться на одной ручке. Понятно. что для нашего примера достаточно попробовать Действуя согласно жадной стратегии мы дёрнем в начале первую ручку, так как в начале каждую из ручекоценки математических ожиданий равны нулю, увеличим её оценку до <tex>Q_1 = 1</tex>. Но если награда все-таки случайная величинаВ дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, то единичной попытки будет явно не достаточночем могли бы. В связи с этим предлагается следующая модификация жадной стратегии:

ϵ-жадная (ϵ-greedy) стратегияВ данном случае достаточно попробовать в начале каждую из ручек вместо того, чтобы фокусироваться только на одной.Зададимся некоторым параметром ϵ∈(0Но если награда случайная величина,1)Заведем массивыто единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:

{Pa=0|a=1,…,N}, Pa == <tex>\epsilon</tex>-жадная (<tex>\epsilon</tex>- сколько раз было выбрано действие a{Qa''greedy'') стратегия ===0|a=1,…,N}, Qa - текущая оценка математического ожидания награды для действия aНа каждом шаге t.

Получаем значение α случайной величины равномерно расределенной на отрезке (0,1)Если α∈(0,ϵ), то выберем действие at из набора A случайно и равновероятно [[File:Eps-greedy.png|thumb|313px|link=https://vbystricky.github.io/2017/01/rl_multi_arms_bandits.html|Пример. Награда для стратегии с различными <tex>\epsilon</tex>]]

Pat=Pat+* Получим значение <tex>\alpha</tex> {{---}} случайной величины равномерно распределенной на отрезке <tex>(0, 1)</tex>;Qat=Qat+1Pat* Если <tex>\alpha \in (Rt−Qat0, \epsilon)Ясно</tex>, что если выбрать ϵ=0 мы вернемся к просто жадной стратегии. Однако, если ϵто выберем действие <tex>a_t \in A</tex>0случайно и равновероятно, иначе как в отличии от просто “жадной”, у нас на каждом шаге жадной стратегии выберем действие с вероятностью ϵ присходит “исследование”максимальной оценкой математического ожидания;* Обновляем оценки так же как в жадной стратегии.

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

=== Стратегия Softmax ===

Мягкий вариант компромисса «изучение—применение»:чем Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше Qt<tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>:πt<tex>\pi_{t+1}(a) = \frac{expQt(Q_t(a)/τ�Pb∈A\tau)}{\sum\limits_{b \in A} {expQt(Q_t(b)/τ�\tau)}}</tex>,где τ — <tex>\tau \in (0, \infty)</tex> {{---}} параметр температуры,с помощью которого можно настраивать поведение алгоритма.при τ → При <tex>\tau \rightarrow \infty</tex> стратегия стремится к равномерной, то есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (exploration). При <tex>\tau \rightarrow 0 </tex> стратегия стремится к жадной,то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (exploitation).при τ → ∞ — к равномернойЭкспонента используется для того, чтобы данный вес был ненулевым даже у действий, тнаграда от которых пока нулевая.е. чисто исследовательской Эвристика: параметр τ <tex>\tau</tex> имеет смысл уменьшать со временем.Какая из стратегий лучше?— зависит === Метод UCB (''upper confidence bound'') ===  Предыдущие алгоритмы при принятии решения используют данные о среднем выигрыше. Проблема в том, что если действие даёт награду с какой-то вероятностью, то данные от конкретной задачинаблюдений получаются шумные и мы можем неправильно определять самое выгодное действие. Алгоритм верхнего доверительного интервала (''upper confidence bound'' или UCB) {{---}} семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша. Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша: <tex>\pi_{t+1}(a) = Q_t(a) + b_a</tex>,— решается <tex>b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} </tex> {{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными. Доказательство [http://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm здесь] В отличие от предыдущих алгоритмов UCB не использует в экспериментесвоей работе ни случайные числа для выбора действия, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждое из действий выбирается по одному разу (для того чтобы можно было вычислить размер бонуса для всех действий). После этого в каждый момент времени выбирается действие с максимальным значением весового коэффициента. Несмотря на это отсутствие случайности результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные действия.

* [http://www.machinelearning.ru/wiki/images/archive/3/35/20121120213057%21Voron-ML-RL-slides.pdf Обучение с подкреплением(Reinforcement Learning) К.В.Воронцов]* [https://pryazhnikov.com/ru/bandit-algorithms-for-website-optimization/ Обзор книги «Bandit Algorithms for Website Optimization»]* [https://en.wikipedia.org/wiki/Q-learning Q-learning]* [https://medium.freecodecamp.org/an-introduction-to-q-learning-reinforcement-learning-14ac0b4493cc An introduction to Q-Learning: reinforcement learning] [[Категория: Машинное обучение]][[Категория: Обучение с подкреплением]]