77
правок
Изменения
Нет описания правки
Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары "входные данные-ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.
Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний.
Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандита].
Формально простейшая модель обучения с подкреплением состоит из:# * множества состояний окружения <tex>S</tex># * множества действий <tex>A</tex># * множества вещественнозначных скалярных "выигрышей"
В произвольный момент времени <tex>t</tex> агент характеризуется состоянием <tex>s_t \in S</tex> и множеством возможных действий <tex>A(s_t)</tex>.
::<tex>R=\sum_t \gamma^t r_t</tex>
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{- --}} дисконтирующий множитель для "предстоящего выигрыша").
Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой.
[[File:RL.png|thumb|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>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>\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>
=== Жадная (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_argmax \limits_{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>\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 будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (режим исследования). При <tex>\tau \rightarrow 0</tex> стратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (режим эксплуатации).
Экспонента используется для того, чтобы данный вес был ненулевым даже у действий, награда от которых пока нулевая.
Предыдущие алгоритмы при принятии решения используют данные о среднем выигрыше. Проблема в том, что если действие даёт награду с какой-то вероятностью, то данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие.
Алгоритм верхнего доверительного интервала (''Upper upper confidence bound'' или UCB) {{---}} семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша.
Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:
'''for''' <tex> s \in S</tex>:
'''for''' <tex> a \in A</tex>:
Q[(s][, a] ) = rand()
'''while''' Q не сошелся:
s = <tex> \forall s \in 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
