Изменения

'''Обучение с подкреплением''', идея которого была почерпнута в смежной области психологии, является подразделом {{---}} подраздел [[машинное обучение|машинного обучения]], изучающим, изучающий как ''агент'' должен ''действовать'' в ''окружениисреде'', чтобы максимизировать некоторый долговременный ''выигрыш''.

Окружение Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.

При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары „входные "входные данные-ответ“ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.

# множества состояний окружения <itex>S</itex># множества действий <itex>A</itex>

В произвольный момент времени <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> - дисконтирующий множитель для „предстоящего выигрыша“"предстоящего выигрыша").

<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 />либо ожидаемый выигрыш, при принятии решения <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=0</tex> можно просто усреднив непосредственные выигрыши.Наиболее очевидный способ оценки при <tex>\gamma>0</tex> — усреднить суммарный выигрыш после каждого состояния.

Поэтому построение искомой оценки при <tex>\gamma>0</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 обучения с временными воздействиями].

 <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^∗(a) = \lim \limits_{y t \rightarrow \infty} Q_t(a) \rightarrow max </tex> — ценность действия <tex>a</tex>

Задача является модельной Выбор действия <tex>a_t</tex> на шаге <tex>t</tex> влечет награду <tex>R(a_t)</tex> при этом <tex>R(a) \forall a \in A</tex> есть случайная величина, распределение которой неизвестно. Состояние среды у нас от шага к шагу не меняется, а значит множество состояний <tex>S</tex> тривиально, ни на что не влияет, поэтому его можно проигнорировать. Для простоты будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали эти распределения, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для понимания конфликта между ''exploitation'' (применениекаждого из распределений, эксплуатация) выбрать действие с максимальным математическим ожиданием и ''exploration'' (изучениетеперь совершать это действие на каждом шаге. Проблема в том, исследование)что распределения неизвестны.

Задача выглядит следующим образом. <br />У нас есть автомат - "Однако можно оценить математическое ожидание некоторой случайной величины <tex>N\xi</tex>-рукий бандит", на каждом шаге мы выбираем за какую из c неизвестным распределением. Для <tex>NK</tex> рук автомата дернуть,т.е. множество действий будет экспериментов <tex>A{\xi_k|k={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\K}</tex> тривиально, ни на что не влияет, так что мы его игнорируем.<br />оценка математического ожидания это среднее арифметическое результатов экспериментов:

Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.<br />Проблема ровно одна: про распределения мы ничего не знаем.<br />Однако, оценивать математическое ожидание некоторой случайной величины <tex>E(\xi</tex> c неизвестным распределением мы умеем. Делаем <tex>P</tex> экспериментов, получаем <tex>) = \frac{1}{K} \xi_p|psum_{k=1..P}^{K}{\xi_k}</tex> величин, берем среднее арифметическое:

это Задача является модельной для понимания конфликта между ''exploitation'' (применение, эксплуатация) и будет оценка математического ожидания. Очевидно''exploration'' (изучение, что чем больше <tex>P</tex> тем оценка точнееисследование).

Заведем массивы <br />* <tex>\{P_a=0|\forall a=\in \{1,…,\ldots 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 Q_a = argmax0 \forall a \in \{Q_a|a=1..\ldots N\}</tex> <br />Выполняем действие at и получаем награду , <tex>R_tQ_a</tex> <br />Обновляем оценку {{---}} текущая оценка математического ожидания награды для действия <tex>a_t</tex>: <br /><tex>P_{a_t} = P_{a_{t+1}}</tex> <br /><tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t} (R_t − Q_{a_t})a</tex>

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

Т.е. желательно всё таки не фиксироваться на одной ручке. Понятно* Выполняем действие <tex>a_t</tex> и получаем награду <tex>R(a_t)</tex>, что для нашего примера достаточно попробовать в начале каждую из ручек.Но если награда все-таки случайная величина, то единичной попытки будет явно не достаточно. В связи с этим предлагается следующая модификация жадной стратегии:<tex> r_a = \frac{1}{T} \sum_{t=1}^{T}{R(a_t)} </tex>

=== * Обновляем оценку математического ожидания для действия <tex>\epsilona_t</tex>-жадная (<tex>\epsilon</tex>-greedy) стратегия ===:

[[File:Eps-greedy.png|thumb|313px|Пример. Награда для стратегии с различными <tex>\epsilonP_{a_t} = P_{a_t} + 1</tex>]]

Зададимся некоторым параметром :<tex>Q_{a_t} = Q_{a_t} + \epsilon \in frac{1}{P_{a_t}} (R(0,1a_t) − Q_{a_t})</tex>

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

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

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

[[File:Eps-greedy.png|thumb|313px|Пример. Награда для стратегии с различными <tex>P_{a_t} = P_{a_{t+1}}</tex> <br /><tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t}(R_t−Q_{a_t})\epsilon</tex>]]

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

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

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

Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше <tex>Q_a = average_arm_reward + arm_bonusQ_t(a)</tex><br />, тем больше вероятность выбора <tex>average_arm_rewarda</tex> - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.:

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

<tex>arm_bonus = \sqrt{tau \frac{2 in (0, \cdot \lninfty)</tex> {total_count}}{arm_count---}} параметр, с помощью которого можно настраивать поведение алгоритма. При </tex><tex>total_count\tau \rightarrow \infty</tex> - это суммарное количество использований всех рук стратегия стремится к равномерной, а то есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (режим исследования). При <tex>arm_count\tau \rightarrow 0</tex> - это количество использований данной рукистратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (режим эксплуатации).

Доказательство [http://banditalgsЭкспонента используется для того, чтобы данный вес был ненулевым даже у действий, награда от которых пока нулевая.com/2016/09/18/the-upper-confidence-bound-algorithm здесь]

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

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

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

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

temperature <tex>b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} </tex> {{- это параметр--}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с помощью которого можно настраивать поведение алгоритма (он называется температура). Он может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша и выбирать руки более равномерно (т.е. перейдёт в режим исследования). Если он близок к нулю, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации)остальными.

Экспонента используется для того, чтобы данный вес был ненулевым даже у рук, выигрыш от которых пока нулевойДоказательство [http://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm здесь]

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

Мягкий вариант компромисса "exploitationНесмотря на это отсутствие случайности результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-exploration":<br />чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>: <br /><tex>\pi_{t+1}(a) = \frac{exp(Q_t(a)/τ)}{\sum\limits_{b \in A} {exp(Q_t(b)/τ)}}</tex> <br />где <tex>\tau</tex> — параметр температуры,<br />при <tex>\tau \rightarrow 0</tex> стратегия стремится к жадной,<br />при <tex>\tau \rightarrow \infty</tex> — к равномернойза того, т.е. чисто исследовательской<br />Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временемчто данный алгоритм сравнительно часто выбирает недоисследованные действия.

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

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