77
правок
Изменения
Нет описания правки
Формально простейшая модель обучения с подкреплением состоит из:
* множества состояний окружения (''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> {{---}} дисконтирующий множитель для "предстоящего выигрыша").
Игра агента со средой:
* инициализация стратегии <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>\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>\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''.
* Выбираем действие с максимальной оценкой математического ожидания:
:<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>.
В чем проблема?
На каждом шаге <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> {{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.
