77
правок
Изменения
Нет описания правки
В обучении с подкреплением существует агент (''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'') <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|link=https://skymindeconophysica.airu/wikiservices/deep-reinforcementmachine-learning/|RL-схемаВзаимодействие агента со средой]]
<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>\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'').
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
=== Формулировка ===
<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>\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''.
==== Жадная (''greedy'') стратегия ====
* <tex>P_a = 0</tex> <tex>\forall a \in \{1 \ldots N\} </tex> {{---}} сколько раз было выбрано действие <tex>a</tex>,
* <tex>Q_a = 0</tex> <tex>\forall a \in \{1 \ldots N\}</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>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>.
В чем проблема?
[[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'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше <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> {{---}} параметр, с помощью которого можно настраивать поведение алгоритма.
Также как ''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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
[[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> 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>
s = s'
return Q
== Ссылки ==
* [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]
[[Категория: Машинное обучение]]
[[Категория: Обучение с подкреплением]]
