1632
правки
Изменения
м
'''Обучение В обучении с подкреплениемсуществует агент (''agent' {{---}} подраздел [[машинное обучение|машинного обучения]], изучающий как ') взаимодействует с окружающей средой (''агентenvironment'' должен ), предпринимая действия (''действоватьactions'' в ). Окружающая среда дает награду (''средеreward'') за эти действия, чтобы максимизировать некоторый долговременный ''выигрыш''а агент продолжает их предпринимать. Алгоритмы с частичным обучением пытаются найти ''стратегию'', приписывающую состояниям (''состояниямstates'' ) окружающей среды действия, которые должен предпринять одно из которых может выбрать агент в этих состояниях.
Задача является модельной для понимания конфликта между ''exploitation'' <tex>E(применение, эксплуатация\xi) и ''exploration'' (изучение= \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex>, исследование).
== Жадные и <tex>\epsilon</tex>Задача является модельной для понимания конфликта между ''exploitation''-жадные стратегии == ''exploration''.
TODO=== Жадные и <tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Обучение с подкреплением''' (англ. ''reinforcement learning'') {{---}} способ машинного обучения, при котором система обучается, взаимодействуя с некоторой средой.
}}
== Обучение с подкреплением ==
Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары "входные данные-ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний(''exploration vs exploitation'').Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандитао многоруком бандите].
Формально простейшая модель обучения с подкреплением состоит из:# * множества состояний окружения (''states'') <tex>S</tex>;# * множества действий (''actions'') <tex>A</tex>;# * множества вещественнозначных скалярных "выигрышей"(''rewards'').
В произвольный момент времени <tex>t</tex> агент характеризуется состоянием <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> в случае МППР, имеющего терминальное состояние, или величину:
::<tex>R=\sum_t \gamma^t r_t</tex>,
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{- --}} дисконтирующий множитель для "предстоящего выигрыша").
Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой.
=== Постановка задачи обучения с подкреплением ===
[[File:RL.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>,
МППР называется финитным, если <tex>|A| < \infty</tex>, <tex>|S| < \infty</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>\pi</tex>, оценить <tex>E[R|\cdot]</tex> при <tex>\gamma = 01</tex> можно просто усреднив непосредственные выигрыши.Наиболее очевидный способ оценки при <tex>\gamma > \in (0, 1)</tex> — {{---}} усреднить суммарный выигрыш после каждого состояния.
Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).
Поэтому построение искомой оценки при <tex>\gamma > \in (0, 1)</tex> неочевидно. Однако, можно заметить, что <tex>R</tex> образуют рекурсивное уравнение Беллмана:
::<tex>E[R|s_t]=r_t + \gamma E[R|s_{t+1}]</tex>.,
Подставляя имеющиеся оценки, <tex>V</tex>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями](''temporal difference (TD) learning'').
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), [http://en.wikipedia.org/wiki/SARSA SARSA] и Q-обучение ([http://en.wikipedia.org/wiki/Q-Learning Q-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> {{---}} множество возможных ''действий''(ручек автомата),
<tex>p_a(r)</tex> {{---}} неизвестное распределение ''награды'' <tex>r \in R </tex> <tex>\forall a \in A</tex>,
<tex>\pi_t(a)</tex> {{---}} ''стратегия'' агента в момент <tex>t </tex> <tex>\forall a \in A</tex>.
Игра агента со средой:
* инициализация стратегии <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|k=1..K}</tex>, оценка математического ожидания это среднее арифметическое результатов экспериментов: <tex>E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex> TODO пока очень тупо
==== Жадная (''greedy'') стратегия ====
* <tex>P_a = 0 </tex> <tex>\forall a \in \{1 \ldots N\} </tex>, <tex>P_a</tex> {{---}} сколько раз было выбрано действие <tex>a</tex>,
* <tex>Q_a = 0 </tex> <tex>\forall a \in \{1 \ldots N\}</tex>, <tex>Q_a</tex> {{---}} текущая оценка математического ожидания награды для действия <tex>a</tex>.
На каждом шаге <tex>t</tex>
* Выбираем действие с максимальной оценкой математического ожидания:
:<tex>a_t = argmax_{a \in A} Q_a </tex>,
* Выполняем действие <tex>a_t</tex> и получаем награду <tex>R(a_t)</tex>, <tex> r_a = \frac{1}{T} \sum_{t=1}^{T}{R(a_t)} </tex>;
* Обновляем оценку математического ожидания для действия <tex>a_t</tex>:
:<tex>P_{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>.
В чем проблема?
Но если награда случайная величина, то единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:
==== <tex>\epsilon</tex>-жадная (<tex>\epsilon</tex>-''greedy'') стратегия ====
[[File:Eps-greedy.png|thumb|313px|link=https://vbystricky.github.io/2017/01/rl_multi_arms_bandits.html|Пример. Награда для стратегии с различными <tex>\epsilon</tex>]]
Введем параметр <tex>\epsilon \in (0,1)</tex>.
На каждом шаге <tex>t</tex>
* Получим значение <tex>\alpha</tex> {{---}} случайной величины равномерно распределенной на отрезке <tex>(0, 1)</tex>;* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>a_t \in A</tex> случайно и равновероятно, иначе как в жадной стратегии выбирем выберем действие с максимальной оценкой математического ожидания:;* Обновляем оценки так же как в жадной стратегии.
Если <tex>\epsilon = 0</tex>, то это обычная жадная стратегия. Однако если <tex>\epsilon > 0</tex>, то в отличии от жадной стратегии на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование" случайных действий.
=== Стратегия Softmax ===
Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>:
<tex>\pi_{t+1}(a) = \frac{exp(Q_t(a) / \tau)}{\sum\limits_{b \in A} {exp(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 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> {{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.
Таким образом, алгоритм это функция качества от состояния и действия:
:<tex>Q: S \times A \to \mathbb{R}</tex>,
Перед обучением <tex>Q</tex> инициализируется случайными значениями. После этого в каждый момент времени <tex>t</tex> агент выбирает действие <tex>a_t</tex>, получает награду <tex>r_t</tex>, переходит в новое состояние <tex>s_{t+1}</tex>, которое может зависеть от предыдущего состояния <tex>s_t</tex> и выбранного действия, и обновляет функцию <tex>Q</tex>. Обновление функции использует взвешенное среднее между старым и новым значениями:
=== Aлгоритм Q-learning ===
[[File:Q-Learning.png|thumb|313px|link=https://en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]]
* <tex>S</tex> — множество состояний,* <tex>A</tex> — множество действий,* <tex>R = S \times A \rightarrow \mathbb{R}</tex> — {{---}} функция награды,* <tex>T = S \times A \rightarrow S</tex> — {{---}} функция перехода,* <tex>\alpha \in [0, 1]</tex> — {{---}} learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации,* <tex>\gamma \in [0, 1]</tex> — {{---}} discounting factor, чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.
'''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 - \alpha) Q[(s'][, a] ) + \alpha * (r + \gamma * \max_max\limits_{a'}{Q[(s'][, a'])})</tex>
s = s'
return Q
== Ссылки ==
*[http://en.wikipedia.org/wiki/Reinforcement_learning Wikipedia: Reinforcement learning]
*[https://login.cs.utexas.edu/sites/default/files/legacy_files/research/documents/1%20intro%20up%20to%20RL%3ATD.pdf Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 135. Cambridge: MIT press, 1998.]
*[https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf Sutton R. S., Barto A. G. Reinforcement learning: An introduction. – 2011.]
*[http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BF%D0%BE%D0%B4%D0%BA%D1%80%D0%B5%D0%BF%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC Обучение с подкреплением]
* [https://en.wikipedia.org/wiki/Multi-armed_bandit Многорукий бандит]
* [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]
[[Категория: Машинное обучение]]
[[Категория: Обучение с подкреплением]]
