77
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Обучение с подкреплением''' (англ. ''reinforcement learning'') {{---}} способ машинного обучения, при котором система обучается, взаимодействуя с некоторой средой.
}}
== Обучение с подкреплением ==
Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары „входные "входные данные-ответ“ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний(''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>a \in A(s_t)</tex>, он переходит в состояние <tex>s_{t+1}</tex> и получает выигрыш <tex>r_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|RLlink=https://econophysica.ru/services/machine-схемаlearning/|Взаимодействие агента со средой]] <tex>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>\pi</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>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.Если же мы пользуемся функцией <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</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'').
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
Другие похожие методы: Адаптивный эвристический критик (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> — {{---}} множество возможных ''действий'' <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>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_{y 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>E(\xi′ xi) = \frac{1}{PK} \cdot \sum_{pk=1}^{PK}{\xi_pxi_k} </tex>,
=== Жадные и эпсилон<tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===
На каждом шаге <tex>t</tex>.<br />* Выбираем действие с максимальной оценкой математического ожидания: <br /><tex>a_t = argmax\{Q_a|a=1..N\}</tex> <br />Выполняем действие at и получаем награду <tex>R_t</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})</tex>
:<tex>\epsilonP_{a_t} = P_{a_t} + 1</tex>-жадная (<tex>\epsilon</tex>-greedy) стратегия,
<tex>Q_a \pi_{t+1}(a) = average_arm_reward + arm_bonus<\frac{exp(Q_t(a) /tex><br \tau)}{\sum\limits_{b \in A} {exp(Q_t(b) /><tex>average_arm_reward\tau)}}</tex> - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.
<tex>arm_bonus\tau \in (0, \infty)</tex> {{--- это бонусное значение, которые показывает}} параметр, насколько недоисследована эта рука по сравнению с остальнымипомощью которого можно настраивать поведение алгоритма. Он вычисляется следующим образом:
При <tex>arm_bonus = \sqrt{tau \frac{2 rightarrow \cdot \ln{total_count}}{arm_count}} </tex><tex>total_countinfty</tex> - это суммарное количество использований всех рук стратегия стремится к равномерной, а <tex>arm_count</tex> - это количество использований данной рукито есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (exploration).
Алгоритм мягкого максимума верхнего доверительного интервала (softmax''upper confidence bound'' или UCB) {{-- это чуть более сложный алгоритм. Его основная идея - уменьшение потерь }} семейство алгоритмов, которые пытаются решить эту проблему, используя при исследовании за счёт более редкого выбора руквыборе данные не только о среднем выигрыше, но и о том, которые дали маленький выигрыш в прошломнасколько можно доверять значениям выигрыша. Чтобы этого добиться для каждой руки вычисляется весовой коэффициент, на базе которого происходит выбор руки:
<tex>average_arm_reward\pi_{t+1}(a) = Q_t(a) + b_a</tex> - это среднее значение выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам.,
== Q-learning ==
На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения — обучения {{---}} то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.
Таким образом, алгоритм это функция качества от состояния и действия:
:<tex>Q: S \times A \to \mathbb{R}</tex>,
Перед обучением {{tmath|<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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
:<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>,
=== 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]
[[Категория: Машинное обучение]]
[[Категория: Обучение с подкреплением]]
