Обучение с подкреплением

Обучение с подкреплением

Обучение с подкреплением, идея которого была почерпнута в смежной области психологии, является подразделом машинного обучения, изучающим, как агент должен действовать в окружении, чтобы максимизировать некоторый долговременный выигрыш. Алгоритмы с частичным обучением пытаются найти стратегию, приписывающую состояниям окружающей среды действия, которые должен предпринять агент в этих состояниях. В экономике и теории игр обучение с подкреплением рассматривается в качестве интерпретации того, как может установиться равновесие.

Окружение обычно формулируется как марковский процесс принятия решений (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием. Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.

При обучении с подкреплением, в отличии от обучения с учителем, не предоставляются верные пары „входные данные-ответ“, а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно. Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний. Баланс изучения-применения при обучении с подкреплением исследуется в задаче многорукого бандита.

Формально простейшая модель обучения с подкреплением состоит из

1. множества состояний окружения S
2. множества действий A
3. множества вещественнозначных скалярных "выигрышей"

В произвольный момент времени t агент характеризуется состоянием [math]s_t \in S[/math] и множеством возможных действий [math]A(s_t)[/math]. Выбирая действие [math]a \in A(s_t)[/math], он переходит в состояние [math]s_{t+1}[/math] и получает выигрыш [math]r_t[/math]. Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию [math]\pi: S \to A[/math], которая максимизирует величину [math]R=r_0 + r_1+\cdots+r_n[/math] в случае МППР, имеющего терминальное состояние, или величину

[math]R=\sum_t \gamma^t r_t[/math]

для МППР без терминальных состояний (где [math]0 \leq \gamma \leq 1[/math] - дисконтирующий множитель для „предстоящего выигрыша“).

Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой.

Постановка задачи обучения с подкреплением

S - множество состояний среды
Игра агента со средой:

1. инициализация стратегии [math]\pi_1(a|s)[/math] и состояния среды [math]s_1[/math]
2. для всех [math]t = 1..T[/math]
   1. агент выбирает действие [math]a_t ∼ \pi_t(a|s_t)[/math]
   2. среда генерирует премию [math]r_{t + 1} ∼ p(r|a_t, s_t)[/math] и новое состояние [math]s_{t + 1} ∼ p(s|a_t, s_t)[/math]
   3. агент корректирует стратегию [math]\pi_{t + 1}(a|s)[/math]

Это марковский процесс принятия решений (МППР), если [math]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)[/math]

МППР называется финитным, если [math]|A| \lt \infty[/math], [math]|S| \lt \infty[/math]

Алгоритмы

Теперь, когда была определена функция выигрыша, нужно определить алгоритм, который будет использоваться для нахождения стратегии, обеспечивающей наилучший результат.

Наивный подход к решению этой задачи подразумевает следующие шаги:

1. опробовать все возможные стратегии;
2. выбрать стратегию с наибольшим ожидаемым выигрышем.

Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или же бесконечно. Вторая проблема возникает, если выигрыши стохастические — чтобы точно оценить выигрыш от каждой стратегии потребуется многократно применить каждую из них. Этих проблем можно избежать, если допустить некоторую структуризацию и, возможно, позволить результатам, полученным от пробы одной стратегии, влиять на оценку для другой. Двумя основными подходами для реализации этих идей являются оценка функций полезности и прямая оптимизация стратегий.

Подход с использованием функции полезности использует множество оценок ожидаемого выигрыша только для одной стратегии [math]\pi[/math] (либо текущей, либо оптимальной). При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния s, при дальнейшем следовании стратегии [math]\pi[/math],

[math]V(s)=E[R|s,\pi][/math],

либо ожидаемый выигрыш, при принятии решения a в состоянии s и дальнейшем соблюдении [math]\pi[/math],

[math]Q(s,a)=E[R|s,\pi,a][/math].

Если для выбора оптимальной стратегии используется функция полезности Q, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность. Если же мы пользуемся функцией V, необходимо либо иметь модель окружения в виде вероятностей [math]P(s'|s,a)[/math], что позволяет построить функцию полезности вида

[math]Q(s,a)=\sum_{s'}V(s')P(s'|s,a)[/math],

либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния V, и исполнитель, выбирающий подходящее действие в каждом состоянии.

Имея фиксированную стратегию [math]\pi[/math], оценить [math]E[R|\cdot][/math] при [math]\gamma=0[/math] можно просто усреднив непосредственные выигрыши. Наиболее очевидный способ оценки при [math]\gamma\gt 0[/math] — усреднить суммарный выигрыш после каждого состояния. Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).

Поэтому построение искомой оценки при [math]\gamma\gt 0[/math] неочевидно. Однако, можно заметить, что R образуют рекурсивное уравнение Беллмана:

[math]E[R|s_t]=r_t+\gamma E[R|s_{t+1}][/math].

Подставляя имеющиеся оценки, V, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму обучения с временными воздействиями. В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния. Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), SARSA и Q-обучение (Q-learning). Все вышеупомянутые используют различные методы приближения, но в некоторых случаях сходимость не гарантируется. Для уточнения оценок используется метод градиентного спуска или метод наименьших квадратов в случае линейных приближений.

Задача о многоруком бандите

Многорукий бандит

Формулировка

[math]A[/math] — множество возможных действий
[math]p_a(r)[/math] — неизвестное распределение награды [math]r \in R[/math] за [math]\forall a \in A[/math]
[math]\pi_t(a)[/math] — стратегия агента в момент [math]t[/math], распределение на [math]A[/math]
Игра агента со средой:

1. инициализация стратегии [math]\pi_1(a)[/math]
2. для всех [math]t = 1..T[/math]
   1. агент выбирает действие [math]a_t ∼ \pi_t(a)[/math]
   2. среда генерирует награду [math]r_t ∼ p_{a_t}(r)[/math]
   3. агент корректирует стратегию [math]\pi_{t+1}(a)[/math]

[math]Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max [/math] — средняя награда в t играх
[math]Q^∗(a) = \lim \limits_{y \rightarrow \infty} Q_t(a) \rightarrow max [/math] — ценность действия [math]a[/math]

Задача является модельной для понимания конфликта между exploitation (применение, эксплуатация) и exploration (изучение, исследование).

Задача выглядит следующим образом.
У нас есть автомат - "[math]N[/math]-рукий бандит", на каждом шаге мы выбираем за какую из [math]N[/math] рук автомата дернуть, т.е. множество действий будет [math]A={1,2,…,N}[/math].
Выбор действия [math]a_t[/math], на шаге [math]t[/math], влечет награду [math]R(a_t)[/math] при этом [math]R(a), a \in A[/math] есть случайная величина, распределение которой мы не знаем. Состояние среды у нас от шага к шагу не меняется, а значит множество [math]S = \{s\}[/math] тривиально, ни на что не влияет, так что мы его игнорируем.

Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.
Проблема ровно одна: про распределения мы ничего не знаем.
Однако, оценивать математическое ожидание некоторой случайной величины [math]\xi[/math] c неизвестным распределением мы умеем. Делаем [math]P[/math] экспериментов, получаем [math]{\xi_p|p=1..P}[/math] величин, берем среднее арифметическое:

[math]\xi′ = \frac{1}{P} \cdot \sum_{p=1}^{P}{\xi_p} [/math]

это и будет оценка математического ожидания. Очевидно, что чем больше [math]P[/math] тем оценка точнее.

Жадные и эпсилон-жадные стратегии

Объединяя всё вышеизложенное, получаем простую "жадную" стратегию.

Жадная (greedy) стратегия

Заведем массивы
[math]\{P_a=0|a=1,…,N\}[/math], [math]P_a[/math] - сколько раз было выбрано действие [math]a[/math]
[math]\{Q_a=0|a=1,…,N\}[/math], [math]Q_a[/math] - текущая оценка математического ожидания награды для действия [math]a[/math]

На каждом шаге [math]t[/math].
Выбираем действие с максимальной оценкой математического ожидания:
[math]a_t = argmax\{Q_a|a=1..N\}[/math]
Выполняем действие at и получаем награду [math]R_t[/math]
Обновляем оценку математического ожидания для действия [math]a_t[/math]:
[math]P_{a_t} = P_{a_{t+1}}[/math]
[math]Q_{a_t} = Q_{a_{t+1}} P_{a_t} (R_t − Q_{a_t})[/math]

Почему это не так хорошо как кажется?

Пример.
Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до [math]Q_1 = 1[/math]. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.

Т.е. желательно всё таки не фиксироваться на одной ручке. Понятно, что для нашего примера достаточно попробовать в начале каждую из ручек. Но если награда все-таки случайная величина, то единичной попытки будет явно не достаточно. В связи с этим предлагается следующая модификация жадной стратегии:

[math]\epsilon[/math]-жадная ([math]\epsilon[/math]-greedy) стратегия

Зададимся некоторым параметром [math]\epsilon \in (0,1)[/math]

Заведем массивы
[math]\{P_a=0|a=1,…,N\}[/math], [math]P_a[/math] - сколько раз было выбрано действие [math]a[/math]
[math]\{Q_a=0|a=1,…,N\}[/math], [math]Q_a[/math] - текущая оценка математического ожидания награды для действия [math]a[/math]

На каждом шаге [math]t[/math].
Получаем значение [math]\alpha[/math] случайной величины равномерно расределенной на отрезке [math](0,1)[/math]
Если [math]\alpha \in (0,\epsilon)[/math], то выберем действие [math]a_t[/math] из набора [math]A[/math] случайно и равновероятно.

Иначе как и в жадной стратегии выбираем действие с максимальной оценкой математического ожидания:

[math]a_t = argmax{Q_a|a=1,...,N}[/math]
Выполняем действие [math]a_t[/math] и получаем награду [math]R_t[/math]
Обновляем оценку математического ожидания для действия [math]a_t[/math]:

[math]P_{a_t} = P_{a_{t+1}}[/math]
[math]Q_{a_t} = Q_{a_{t+1}} P_{a_t}(R_t−Q_{a_t})[/math]

Ясно, что если выбрать [math]\epsilon = 0[/math] мы вернемся к просто жадной стратегии. Однако, если [math]\epsilon \gt 0[/math], в отличии от просто "жадной", у нас на каждом шаге с вероятностью [math]\epsilon[/math] присходит "исследование".

Пример. Награда для стратегии с различными [math]\epsilon[/math]:

Стратегия Softmax

Мягкий вариант компромисса "exploitation-exploration":
чем больше [math]Q_t(a)[/math], тем больше вероятность выбора [math]a[/math]:
[math]\pi_{t+1}(a) = \frac{exp(Q_t(a)/τ)}{\sum\limits_{b \in A} {exp(Q_t(b)/τ)}}[/math]
где [math]\tau[/math] — параметр температуры,
при [math]\tau \rightarrow 0[/math] стратегия стремится к жадной,
при [math]\tau \rightarrow \infty[/math] — к равномерной, т.е. чисто исследовательской
Эвристика: параметр [math]\tau[/math] имеет смысл уменьшать со временем.

Ссылки

• Wikipedia: Reinforcement learning
• Обучение с подкреплением
• Многорукий бандит
• Задача о многоруком бандите
• Обучение с подкреплением (Reinforcement Learning) К.В.Воронцов