Обучение с подкреплением — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 33 промежуточные версии 4 участников)
Строка 1: Строка 1:
 +
{{Определение
 +
|definition=
 +
'''Обучение с подкреплением''' (англ. ''reinforcement learning'') {{---}} способ машинного обучения, при котором система обучается, взаимодействуя с некоторой средой.
 +
}}
 +
 
== Обучение с подкреплением ==  
 
== Обучение с подкреплением ==  
'''Обучение с подкреплением''', идея которого была почерпнута в смежной области психологии, является подразделом [[машинное обучение|машинного обучения]], изучающим, как ''агент'' должен ''действовать'' в ''окружении'', чтобы максимизировать некоторый долговременный ''выигрыш''.
 
Алгоритмы с частичным обучением пытаются найти ''стратегию'', приписывающую ''состояниям'' окружающей среды действия, которые должен предпринять агент в этих состояниях.
 
В экономике и теории игр обучение с подкреплением рассматривается в качестве интерпретации того, как может установиться равновесие.
 
  
Окружение обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
+
В обучении с подкреплением существует агент (''agent'') взаимодействует с окружающей средой (''environment''), предпринимая действия (''actions''). Окружающая среда дает награду (''reward'') за эти действия, а агент продолжает их предпринимать.
 +
 
 +
Алгоритмы с частичным обучением пытаются найти стратегию, приписывающую состояниям (''states'') окружающей среды действия, одно из которых может выбрать агент в этих состояниях.
 +
 
 +
Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
 
Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
 
Вероятности выигрышей и перехода состояний в МППР обычно являются величинами случайными, но стационарными в рамках задачи.
  
При обучении с подкреплением, в отличии от [[обучение с учителем|обучения с учителем]], не предоставляются верные пары „входные данные-ответ“, а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.
+
При обучении с подкреплением, в отличии от обучения с учителем, не предоставляются верные пары "входные данные-ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.
Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний.
+
Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний (''exploration vs exploitation'').
Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандита].
+
Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit о многоруком бандите].
  
Формально простейшая модель обучения с подкреплением состоит из
+
Формально простейшая модель обучения с подкреплением состоит из:
# множества состояний окружения  <i>S</i>
+
* множества состояний окружения (''states'') <tex>S</tex>;
# множества действий <i>A</i>
+
* множества действий (''actions'') <tex>A</tex>;
# множества вещественнозначных скалярных "выигрышей"
+
* множества вещественнозначных скалярных "выигрышей" (''rewards'').
  
В произвольный момент времени <i>t</i> агент характеризуется состоянием <tex>s_t \in S</tex> и множеством возможных действий <tex>A(s_t)</tex>.
+
В произвольный момент времени <tex>t</tex> агент характеризуется состоянием <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>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>\pi: S \to A</tex>, которая максимизирует величину <tex>R=r_0 + r_1+\cdots+r_n</tex> в случае МППР, имеющего терминальное состояние, или величину:
::<tex>R=\sum_t \gamma^t r_t</tex> <br />
+
 
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> - дисконтирующий множитель для „предстоящего выигрыша“).
+
::<tex>R=\sum_t \gamma^t r_t</tex>,
 +
 
 +
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{---}} дисконтирующий множитель для "предстоящего выигрыша").
  
 
Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой.
 
Таким образом, обучение с подкреплением особенно хорошо подходит для решения задач, связанных с выбором между долгосрочной и краткосрочной выгодой.
Строка 26: Строка 34:
 
=== Постановка задачи обучения с подкреплением ===
 
=== Постановка задачи обучения с подкреплением ===
  
[[File:RL.png|thumb|RL-схема]]
+
[[File:RL.png|thumb|link=https://econophysica.ru/services/machine-learning/|Взаимодействие агента со средой]]
 +
 
 +
<tex>S</tex> {{---}} множество состояний среды
  
<i>S</i> - множество состояний среды <br />
 
 
Игра агента со средой:
 
Игра агента со средой:
# инициализация стратегии <tex>\pi_1(a|s)</tex> и состояния среды <tex>s_1</tex>
+
* инициализация стратегии <tex>\pi_1(a | s)</tex> и состояния среды <tex>s_1</tex>;
# для всех <tex>t = 1..T</tex>
+
* для всех <tex>t = 1 \ldots T</tex>:
## агент выбирает действие <tex>a_t ∼ \pi_t(a|s_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>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>\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>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| < \infty</tex>, <tex>|S| < \infty</tex>
Строка 46: Строка 55:
  
 
Наивный подход к решению этой задачи подразумевает следующие шаги:
 
Наивный подход к решению этой задачи подразумевает следующие шаги:
# опробовать все возможные стратегии;
+
* опробовать все возможные стратегии;
# выбрать стратегию с наибольшим ожидаемым выигрышем.
+
* выбрать стратегию с наибольшим ожидаемым выигрышем.
  
Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или же бесконечно.
+
Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или бесконечно.
 
Вторая проблема возникает, если выигрыши стохастические — чтобы точно оценить выигрыш от каждой стратегии потребуется многократно применить каждую из них.
 
Вторая проблема возникает, если выигрыши стохастические — чтобы точно оценить выигрыш от каждой стратегии потребуется многократно применить каждую из них.
 
Этих проблем можно избежать, если допустить некоторую структуризацию и, возможно, позволить результатам, полученным от пробы одной стратегии, влиять на оценку для другой.
 
Этих проблем можно избежать, если допустить некоторую структуризацию и, возможно, позволить результатам, полученным от пробы одной стратегии, влиять на оценку для другой.
Строка 55: Строка 64:
  
 
Подход с использованием функции полезности использует множество оценок ожидаемого выигрыша только для одной стратегии <tex>\pi</tex> (либо текущей, либо оптимальной).
 
Подход с использованием функции полезности использует множество оценок ожидаемого выигрыша только для одной стратегии <tex>\pi</tex> (либо текущей, либо оптимальной).
При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния <i>s</i>, при дальнейшем следовании стратегии <tex>\pi</tex>, <br />
+
При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния <tex>s</tex>, при дальнейшем следовании стратегии <tex>\pi</tex>,
::<tex>V(s)=E[R|s,\pi]</tex>, <br />
+
 
либо ожидаемый выигрыш, при принятии решения <i>a</i> в состоянии <i>s</i> и дальнейшем соблюдении <tex>\pi</tex>, <br />
+
::<tex>V(s) = E[R|s, \pi]</tex>,
::<tex>Q(s,a)=E[R|s,\pi,a]</tex>. <br />
 
Если для выбора оптимальной стратегии используется функция полезности <i>Q</i>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.
 
Если же мы пользуемся функцией <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>\pi</tex>, оценить <tex>E[R|\cdot]</tex> при <tex>\gamma=0</tex> можно просто усреднив непосредственные выигрыши.
+
либо ожидаемый выигрыш, при принятии решения <tex>a</tex> в состоянии <tex>s</tex> и дальнейшем соблюдении <tex>\pi</tex>,
Наиболее очевидный способ оценки при <tex>\gamma>0</tex> усреднить суммарный выигрыш после каждого состояния.
+
 
 +
::<tex>Q(s, a) = E[R|s, \pi, a]</tex>,
 +
 
 +
Если для выбора оптимальной стратегии используется функция полезности <tex>Q</tex>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.
 +
 
 +
Если же мы пользуемся функцией <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 = 1</tex> можно просто усреднив непосредственные выигрыши.
 +
Наиболее очевидный способ оценки при <tex>\gamma \in (0, 1)</tex> {{---}} усреднить суммарный выигрыш после каждого состояния.
 
Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).
 
Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).
  
Поэтому построение искомой оценки при <tex>\gamma>0</tex> неочевидно. Однако, можно заметить, что <i>R</i> образуют рекурсивное уравнение Беллмана: <br />
+
Поэтому построение искомой оценки при <tex>\gamma \in (0, 1)</tex> неочевидно. Однако, можно заметить, что <tex>R</tex> образуют рекурсивное уравнение Беллмана:
::<tex>E[R|s_t]=r_t+\gamma E[R|s_{t+1}]</tex>. <br />
+
 
Подставляя имеющиеся оценки, <i>V</i>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями].
+
::<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'').
 
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
 
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
 +
 
Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), [http://en.wikipedia.org/wiki/SARSA SARSA] и Q-обучение ([http://en.wikipedia.org/wiki/Q-Learning Q-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|Многорукий бандит]]
+
[[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>A</tex> {{---}} множество возможных ''действий'' (ручек автомата),
<tex>\pi_t(a)</tex> ''стратегия'' агента в момент <tex>t</tex>, распределение на <tex>A</tex> <br />
+
 
 +
<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>\pi_1(a)</tex>;
# для всех <tex>t = 1..T</tex>
+
* для всех <tex>t = 1 \ldots T</tex>:
## агент выбирает действие <tex>a_t ∼ \pi_t(a)</tex>
+
** агент выбирает действие (ручку) <tex>a_t ∼ \pi_t(a)</tex>;
## среда генерирует награду <tex>r_t ∼ p_{a_t}(r)</tex>
+
** среда генерирует награду <tex>r_t ∼ p_{a_t}(r)</tex>;
## агент корректирует стратегию <tex>\pi_{t+1}(a)</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_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 \rightarrow \infty} Q_t(a) \rightarrow max </tex> ценность действия <tex>a</tex>
+
<tex>Q^∗(a) = \lim \limits_{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>.
  
Задача является модельной для понимания конфликта между ''exploitation'' (применение, эксплуатация) и ''exploration'' (изучение, исследование).
+
Выбор действия <tex>a_t</tex> на шаге <tex>t</tex> влечет награду <tex>R(a_t)</tex> при этом <tex>R(a)</tex> <tex>\forall a \in A</tex> есть случайная величина, распределение которой неизвестно.
 +
 +
Состояние среды у нас от шага к шагу не меняется, а значит множество состояний <tex>S</tex> тривиально, ни на что не влияет, поэтому его можно проигнорировать.
  
Задача выглядит следующим образом. <br />
+
Для простоты будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали эти распределения, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.
У нас есть автомат - "<tex>N</tex>-рукий бандит", на каждом шаге мы выбираем за какую из <tex>N</tex> рук автомата дернуть,
 
т.е. множество действий будет <tex>A={1,2,…,N}</tex>.<br />
 
Выбор действия <tex>a_t</tex>, на шаге <tex>t</tex>, влечет награду <tex>R(a_t)</tex> при этом <tex>R(a), a \in A</tex> есть случайная величина, распределение которой мы не знаем.
 
Состояние среды у нас от шага к шагу не меняется, а значит множество <tex>S = \{s\}</tex> тривиально, ни на что не влияет, так что мы его игнорируем.<br />
 
  
Для простоты пока будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали, что за распределение, соответствуют каждому действию, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.<br />
+
Проблема в том, что распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением. Для <tex>K</tex> экспериментов <tex>\xi_k</tex>, оценка математического ожидания это среднее арифметическое результатов экспериментов:
Проблема ровно одна: про распределения мы ничего не знаем.<br />
 
Однако, оценивать математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением мы умеем. Делаем <tex>P</tex> экспериментов, получаем <tex>{\xi_p|p=1..P}</tex> величин, берем среднее арифметическое:
 
  
<tex>\xi′ = \frac{1}{P} \cdot \sum_{p=1}^{P}{\xi_p} </tex>
+
<tex>E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex>,
  
это и будет оценка математического ожидания. Очевидно, что чем больше <tex>P</tex> тем оценка точнее.
+
Задача является модельной для понимания конфликта между ''exploitation''-''exploration''.
  
== Жадные и эпсилон-жадные стратегии ==  
+
=== Жадные и <tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===  
  
Объединяя всё вышеизложенное, получаем простую "жадную" стратегию.
+
==== Жадная (''greedy'') стратегия ====
  
Жадная (greedy) стратегия
+
* <tex>P_a = 0</tex> <tex>\forall a \in \{1 \ldots N\} </tex> {{---}} сколько раз было выбрано действие <tex>a</tex>,
  
Заведем массивы <br />
+
* <tex>Q_a = 0</tex> <tex>\forall a \in \{1 \ldots N\}</tex> {{---}} текущая оценка математического ожидания награды для действия <tex>a</tex>.
<tex>\{P_a=0|a=1,…,N\}</tex>, <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex> <br />
 
<tex>\{Q_a=0|a=1,…,N\}</tex>, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>
 
  
На каждом шаге <tex>t</tex>.<br />
+
На каждом шаге <tex>t</tex>
Выбираем действие с максимальной оценкой математического ожидания: <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>a_t = argmax_{a \in A} Q_a </tex>,
  
Пример.<br />
+
* Выполняем действие <tex>a_t</tex> и получаем награду <tex>R(a_t)</tex>;
Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку (поскольку в начале у нас оценка математических ожиданий одинаковые и равны нулю) повысим её оценку до <tex>Q_1 = 1</tex>. И в дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.
 
  
Т.е. желательно всё таки не фиксироваться на одной ручке. Понятно, что для нашего примера достаточно попробовать в начале каждую из ручек.
+
* Обновляем оценку математического ожидания для действия <tex>a_t</tex>:
Но если награда все-таки случайная величина, то единичной попытки будет явно не достаточно. В связи с этим предлагается следующая модификация жадной стратегии:
 
  
<tex>\epsilon</tex>-жадная (<tex>\epsilon</tex>-greedy) стратегия
+
:<tex>P_{a_t} = P_{a_t} + 1</tex>,
  
Зададимся некоторым параметром <tex>\epsilon \in (0,1)</tex>
+
:<tex>Q_{a_t} = Q_{a_t} + \frac{1}{P_{a_t}} (R(a_t) − Q_{a_t})</tex>.
  
Заведем массивы<br />
+
В чем проблема?
<tex>\{P_a=0|a=1,…,N\}</tex>, <tex>P_a</tex> - сколько раз было выбрано действие <tex>a</tex> <br />
 
<tex>\{Q_a=0|a=1,…,N\}</tex>, <tex>Q_a</tex> - текущая оценка математического ожидания награды для действия <tex>a</tex>
 
  
На каждом шаге <tex>t</tex>.<br />
+
Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку, так как в начале оценки математических ожиданий равны нулю, увеличим её оценку до <tex>Q_1 = 1</tex>. В дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.
Получаем значение <tex>\alpha</tex> случайной величины равномерно расределенной на отрезке <tex>(0,1)</tex> <br />
 
Если <tex>\alpha \in (0,\epsilon)</tex>, то выберем действие <tex>a_t</tex> из набора <tex>A</tex> случайно и равновероятно. <br />
 
  
Иначе как и в жадной стратегии выбираем действие с максимальной оценкой математического ожидания:
+
В данном случае достаточно попробовать в начале каждую из ручек вместо того, чтобы фокусироваться только на одной.
 +
Но если награда случайная величина, то единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:
  
<tex>a_t = argmax{Q_a|a=1,...,N}</tex> <br />
+
==== <tex>\epsilon</tex>-жадная (<tex>\epsilon</tex>-''greedy'') стратегия ====
Выполняем действие <tex>a_t</tex> и получаем награду <tex>R_t</tex> <br />
 
Обновляем оценку математического ожидания для действия <tex>a_t</tex>:
 
  
<tex>P_{a_t} = P_{a_{t+1}}</tex> <br />
+
[[File:Eps-greedy.png|thumb|313px|link=https://vbystricky.github.io/2017/01/rl_multi_arms_bandits.html|Пример. Награда для стратегии с различными <tex>\epsilon</tex>]]
<tex>Q_{a_t} = Q_{a_{t+1}} P_{a_t}(R_t−Q_{a_t})</tex>
 
  
Ясно, что если выбрать <tex>\epsilon = 0</tex> мы вернемся к просто жадной стратегии. Однако, если <tex>\epsilon > 0</tex>, в отличии от просто "жадной", у нас на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование".
+
Введем параметр <tex>\epsilon \in (0,1)</tex>.
  
Пример. Награда для стратегии с различными <tex>\epsilon</tex>:
+
На каждом шаге <tex>t</tex>
[[File:Eps-greedy.png]]
 
  
== Метод UCB (upper confidence bound) ==
+
* Получим значение <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> присходит "исследование" случайных действий.
  
Алгоритм верхнего доверительного интервала (''Upper confidence bound'' или просто UCB) - это семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять этим значениям выигрыша. В книге описывается один такой алгоритм - UCB.
+
=== Стратегия Softmax ===
  
Как и в softmax в UCB при выборе рук используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound, что и дало название алгоритму) значения выигрыша:
+
Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>:
  
<tex>Q_a = average_arm_reward + arm_bonus</tex><br />
+
<tex>\pi_{t+1}(a) = \frac{exp(Q_t(a) / \tau)}{\sum\limits_{b \in A} {exp(Q_t(b) / \tau)}}</tex>,
<tex>average_arm_reward</tex> - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.
 
  
<tex>arm_bonus</tex> - это бонусное значение, которые показывает, насколько недоисследована эта рука по сравнению с остальными. Он вычисляется следующим образом:
+
<tex>\tau \in (0, \infty)</tex> {{---}} параметр, с помощью которого можно настраивать поведение алгоритма.
  
<tex>arm_bonus = \sqrt{\frac{2 \cdot \ln{total_count}}{arm_count}} </tex>
+
При <tex>\tau \rightarrow \infty</tex> стратегия стремится к равномерной, то есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (exploration).
<tex>total_count</tex> - это суммарное количество использований всех рук, а <tex>arm_count</tex> - это количество использований данной руки.
 
  
Доказательство [http://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm здесь]
+
При <tex>\tau \rightarrow 0</tex> стратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (exploitation).
  
В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора руки, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждая из рук выбирается по одному разу (это нужно для того, чтобы можно было вычислить размер бонуса для всех рук). После этого в каждый момент времени выбирается рука с максимальным значением весового коэффициента.
+
Экспонента используется для того, чтобы данный вес был ненулевым даже у действий, награда от которых пока нулевая.
  
Несмотря на это отсутствие случайности, результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные руки.
+
Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временем.
  
== Стратегия Softmax ==  
+
=== Метод UCB (''upper confidence bound'') ===  
  
Алгоритм мягкого максимума (softmax) - это чуть более сложный алгоритм. Его основная идея - уменьшение потерь при исследовании за счёт более редкого выбора рук, которые дали маленький выигрыш в прошлом. Чтобы этого добиться для каждой руки вычисляется весовой коэффициент, на базе которого происходит выбор руки:
+
Предыдущие алгоритмы при принятии решения используют данные о среднем выигрыше. Проблема в том, что если действие даёт награду с какой-то вероятностью, то данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие.
  
<tex>Q_a = \exp(average_arm_reward / temperature)</tex>
+
Алгоритм верхнего доверительного интервала (''upper confidence bound'' или UCB) {{---}} семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша.
  
<tex>average_arm_reward</tex> - это среднее значение выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам.
+
Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:
  
temperature - это параметр, с помощью которого можно настраивать поведение алгоритма (он называется температура). Он может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша и выбирать руки более равномерно (т.е. перейдёт в режим исследования). Если он близок к нулю, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации).
+
<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> {{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.
  
Вероятность выбора руки равна отношению её весового коэффициента и сумме весовых коэффициентов всех рук. При выборе генерируется случайное число от 0 до 1, на основании которого произойдёт выбор конкретной руки.
+
Доказательство [http://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm здесь]
  
Мягкий вариант компромисса "exploitation-exploration":<br />
+
В отличие от предыдущих алгоритмов UCB не использует в своей работе ни случайные числа для выбора действия, ни параметры, которыми можно влиять на его работу. В начале работы алгоритма каждое из действий выбирается по одному разу (для того чтобы можно было вычислить размер бонуса для всех действий). После этого в каждый момент времени выбирается действие с максимальным значением весового коэффициента.
чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>: <br />
+
 
<tex>\pi_{t+1}(a) = \frac{exp(Q_t(a)/τ)}{\sum\limits_{b \in A} {exp(Q_t(b)/τ)}}</tex> <br />
+
Несмотря на это отсутствие случайности результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные действия.
где <tex>\tau</tex> — параметр температуры,<br />
 
при <tex>\tau \rightarrow 0</tex> стратегия стремится к жадной,<br />
 
при <tex>\tau \rightarrow \infty</tex> — к равномерной, т.е. чисто исследовательской<br />
 
Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временем.
 
  
 
== Q-learning ==  
 
== Q-learning ==  
  
'''Q-обучение''' (Q-learning) — метод, применяемый в [[Искусственный интеллект|искусственном интеллекте]] при [[Агентный подход|агентном подходе]]. Относится к экспериментам вида [[Обучение с подкреплением|oбучение с подкреплением]]. На основе получаемого от среды вознаграждения [[Интеллектуальный агент|агент]] формирует [[Функция полезности|функцию полезности]] Q, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ Q-обучения — то, что оно в состоянии сравнить ожидаемую [[Полезность (экономика)|полезность]] доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде [[Марковский процесс принятия решений|марковского процесса принятия решений]].
+
На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{---}} то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.
  
=== Aлгоритм Q-learning ===
+
Таким образом, алгоритм это функция качества от состояния и действия:
[[File:Q-Learning.png|thumb|313px|Процесс Q-обучения]]
 
  
The weight for a step from a state <math>\Delta t</math> steps into the future is calculated as <math>\gamma^{\Delta t}</math>. <math>\gamma</math> (the ''discount factor'') is a number between 0 and 1 (<math>0 \le \gamma \le 1</math>) and has the effect of valuing rewards received earlier higher than those received later (reflecting the value of a "good start"). <math> \gamma </math> may also be interpreted as the probability to succeed (or survive) at every step <math>\Delta t</math>.
+
:<tex>Q: S \times A \to \mathbb{R}</tex>,
  
The algorithm, therefore, has a function that calculates the quality of a state-action combination:
+
Перед обучением <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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
  
:<math>Q: S \times A \to \mathbb{R}</math> .
+
:<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>,
  
Before learning begins, {{tmath|Q}} is initialized to a possibly arbitrary fixed value (chosen by the programmer). Then, at each time <math>t</math> the agent selects an action <math>a_t</math>, observes a reward <math>r_t</math>, enters a new state <math>s_{t+1}</math> (that may depend on both the previous state <math>s_t</math> and the selected action), and <math>Q</math> is updated. The core of the algorithm is a simple [[Markov decision process#Value iteration|value iteration update]], using the weighted average of the old value and the new information:
+
где ''<tex>r_{t}</tex>'' это награда, полученная при переходе из состояния <tex>s_{t}</tex> в состояние <tex>s_{t+1}</tex>, и <tex>\alpha</tex> это скорость обучения (<tex>0 < \alpha \le 1</tex>).
  
:<math>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}} </math>
+
Алгоритм заканчивается, когда агент переходит в терминальное состояние <tex>s_{t+1}</tex>.
  
where ''<math>r_{t}</math>'' is the reward received when moving from the state <math>s_{t}</math> to the state <math>s_{t+1}</math>, and <math>\alpha</math> is the learning rate (<math>0 < \alpha \le 1</math>).
+
=== Aлгоритм Q-learning ===
  
An episode of the algorithm ends when state <math>s_{t+1}</math> is a final or ''terminal state''. However, ''Q''-learning can also learn in non-episodic tasks.{{citation needed|date=December 2017}} If the discount factor is lower than 1, the action values are finite even if the problem can contain infinite loops.
+
[[File:Q-Learning.png|thumb|313px|link=https://en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]]
  
For all final states <math>s_f</math>, <math>Q(s_f, a)</math> is never updated, but is set to the reward value <math>r</math> observed for state <math>s_f</math>. In most cases, <math>Q(s_f,a)</math> can be taken to equal zero.
+
* <tex>S</tex> множество состояний,
 
+
* <tex>A</tex> множество действий,
Обозначения
+
* <tex>R = S \times A \rightarrow \mathbb{R}</tex> {{---}} функция награды,
* <tex>S</tex> -- множество состояний
+
* <tex>T = S \times A \rightarrow S</tex> {{---}} функция перехода,
* <tex>A</tex> -- множество действий
+
* <tex>\alpha \in [0, 1]</tex> {{---}} learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации,
* <tex>R = S * A \rightarrow R</tex> -- функция награды
+
* <tex>\gamma \in [0, 1]</tex> {{---}} discounting factor, чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.
* <tex>T = S * A -> 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>):
 
  '''fun''' Q-learning(<tex>S, A, R, T, \alpha, \gamma</tex>):
 
     '''for''' <tex> s \in S</tex>:
 
     '''for''' <tex> s \in S</tex>:
 
         '''for''' <tex> a \in A</tex>:
 
         '''for''' <tex> a \in A</tex>:
             Q[s][a] = rand()
+
             Q(s, a) = rand()
     '''while''' Q не сошелся:
+
     '''while''' Q is not converged:
 
         s = <tex> \forall s \in S</tex>
 
         s = <tex> \forall s \in S</tex>
         '''while''' s не конечное состояние:
+
         '''while''' s is not terminal:
 
           <tex>\pi(s) = argmax_{a}{Q(s, a)}</tex>
 
           <tex>\pi(s) = argmax_{a}{Q(s, a)}</tex>
 
           a = <tex>\pi(s)</tex>
 
           a = <tex>\pi(s)</tex>
 
           r = R(s, a)
 
           r = R(s, a)
 
           s' = T(s, a)
 
           s' = T(s, a)
           Q[s'][a] = (1 - \alpha) Q[s'][a] + \alpha * (r + \gamma * \max_{a'}{Q[s'][a']})
+
           <tex>Q(s', a) = (1 - \alpha) Q(s', a) + \alpha (r + \gamma \max\limits_{a'}{Q(s', a')})</tex>
 
           s = s'
 
           s = s'
 
     return Q
 
     return Q
 
  
 
== Ссылки ==
 
== Ссылки ==
  
 
*[http://en.wikipedia.org/wiki/Reinforcement_learning Wikipedia: Reinforcement learning]
 
*[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 Обучение с подкреплением]
 
*[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/Multi-armed_bandit Многорукий бандит]
Строка 264: Строка 260:
 
* [https://en.wikipedia.org/wiki/Q-learning Q-learning]
 
* [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]
 
* [https://medium.freecodecamp.org/an-introduction-to-q-learning-reinforcement-learning-14ac0b4493cc An introduction to Q-Learning: reinforcement learning]
 +
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Обучение с подкреплением]]

Текущая версия на 19:13, 4 сентября 2022

Определение:
Обучение с подкреплением (англ. reinforcement learning) — способ машинного обучения, при котором система обучается, взаимодействуя с некоторой средой.


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

В обучении с подкреплением существует агент (agent) взаимодействует с окружающей средой (environment), предпринимая действия (actions). Окружающая среда дает награду (reward) за эти действия, а агент продолжает их предпринимать.

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

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

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

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

  • множества состояний окружения (states) [math]S[/math];
  • множества действий (actions) [math]A[/math];
  • множества вещественнозначных скалярных "выигрышей" (rewards).

В произвольный момент времени [math]t[/math] агент характеризуется состоянием [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] — дисконтирующий множитель для "предстоящего выигрыша").

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

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

Взаимодействие агента со средой

[math]S[/math] — множество состояний среды

Игра агента со средой:

  • инициализация стратегии [math]\pi_1(a | s)[/math] и состояния среды [math]s_1[/math];
  • для всех [math]t = 1 \ldots T[/math]:
    • агент выбирает действие [math]a_t ∼ \pi_t(a | s_t)[/math];
    • среда генерирует награду [math]r_{t + 1} ∼ p(r | a_t, s_t)[/math] и новое состояние [math]s_{t + 1} ∼ p(s | a_t, s_t)[/math];
    • агент корректирует стратегию [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]

Алгоритмы

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

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

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

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

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

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

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

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

Если для выбора оптимальной стратегии используется функция полезности [math]Q[/math], то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.

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

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

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

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

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

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

Подставляя имеющиеся оценки [math]V[/math] и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму обучения с временными воздействиями (temporal difference (TD) learning). В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.

Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), SARSA и Q-обучение (Q-learning).

Задача о многоруком бандите (The multi-armed bandit problem)

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

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

[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]\forall a \in A[/math].

Игра агента со средой:

  • инициализация стратегии [math]\pi_1(a)[/math];
  • для всех [math]t = 1 \ldots T[/math]:
    • агент выбирает действие (ручку) [math]a_t ∼ \pi_t(a)[/math];
    • среда генерирует награду [math]r_t ∼ p_{a_t}(r)[/math];
    • агент корректирует стратегию [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_{t \rightarrow \infty} Q_t(a) \rightarrow max [/math] — ценность действия [math]a[/math].

У нас есть автомат — [math]N[/math]-рукий бандит, на каждом шаге мы выбираем за какую из [math]N[/math] ручек автомата дернуть, т.е. множество действий [math]A = {1,2 \ldots ,N}[/math].

Выбор действия [math]a_t[/math] на шаге [math]t[/math] влечет награду [math]R(a_t)[/math] при этом [math]R(a)[/math] [math]\forall a \in A[/math] есть случайная величина, распределение которой неизвестно.

Состояние среды у нас от шага к шагу не меняется, а значит множество состояний [math]S[/math] тривиально, ни на что не влияет, поэтому его можно проигнорировать.

Для простоты будем полагать, что каждому действию соответствует некоторое распределение, которое не меняется со временем. Если бы мы знали эти распределения, то очевидная стратегия заключалась бы в том, чтобы подсчитать математическое ожидание для каждого из распределений, выбрать действие с максимальным математическим ожиданием и теперь совершать это действие на каждом шаге.

Проблема в том, что распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины [math]\xi[/math] c неизвестным распределением. Для [math]K[/math] экспериментов [math]\xi_k[/math], оценка математического ожидания это среднее арифметическое результатов экспериментов:

[math]E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} [/math],

Задача является модельной для понимания конфликта между exploitation-exploration.

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

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

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

На каждом шаге [math]t[/math]

  • Выбираем действие с максимальной оценкой математического ожидания:
[math]a_t = argmax_{a \in A} Q_a [/math],
  • Выполняем действие [math]a_t[/math] и получаем награду [math]R(a_t)[/math];
  • Обновляем оценку математического ожидания для действия [math]a_t[/math]:
[math]P_{a_t} = P_{a_t} + 1[/math],
[math]Q_{a_t} = Q_{a_t} + \frac{1}{P_{a_t}} (R(a_t) − Q_{a_t})[/math].

В чем проблема?

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

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

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

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

Введем параметр [math]\epsilon \in (0,1)[/math].

На каждом шаге [math]t[/math]

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

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

Стратегия Softmax

Основная идея алгоритма softmax — уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше [math]Q_t(a)[/math], тем больше вероятность выбора [math]a[/math]:

[math]\pi_{t+1}(a) = \frac{exp(Q_t(a) / \tau)}{\sum\limits_{b \in A} {exp(Q_t(b) / \tau)}}[/math],

[math]\tau \in (0, \infty)[/math] — параметр, с помощью которого можно настраивать поведение алгоритма.

При [math]\tau \rightarrow \infty[/math] стратегия стремится к равномерной, то есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (exploration).

При [math]\tau \rightarrow 0[/math] стратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (exploitation).

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

Эвристика: параметр [math]\tau[/math] имеет смысл уменьшать со временем.

Метод UCB (upper confidence bound)

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

Алгоритм верхнего доверительного интервала (upper confidence bound или UCB) — семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша.

Также как softmax в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:

[math]\pi_{t+1}(a) = Q_t(a) + b_a[/math],

[math]b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} [/math] — бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.

Доказательство здесь

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

Несмотря на это отсутствие случайности результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные действия.

Q-learning

На основе получаемого от среды вознаграждения агент формирует функцию полезности [math]Q[/math], что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ [math]Q[/math]-обучения — то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.

Таким образом, алгоритм это функция качества от состояния и действия:

[math]Q: S \times A \to \mathbb{R}[/math],

Перед обучением [math]Q[/math] инициализируется случайными значениями. После этого в каждый момент времени [math]t[/math] агент выбирает действие [math]a_t[/math], получает награду [math]r_t[/math], переходит в новое состояние [math]s_{t+1}[/math], которое может зависеть от предыдущего состояния [math]s_t[/math] и выбранного действия, и обновляет функцию [math]Q[/math]. Обновление функции использует взвешенное среднее между старым и новым значениями:

[math]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}} [/math],

где [math]r_{t}[/math] это награда, полученная при переходе из состояния [math]s_{t}[/math] в состояние [math]s_{t+1}[/math], и [math]\alpha[/math] это скорость обучения ([math]0 \lt \alpha \le 1[/math]).

Алгоритм заканчивается, когда агент переходит в терминальное состояние [math]s_{t+1}[/math].

Aлгоритм Q-learning

Процесс Q-обучения
  • [math]S[/math] — множество состояний,
  • [math]A[/math] — множество действий,
  • [math]R = S \times A \rightarrow \mathbb{R}[/math] — функция награды,
  • [math]T = S \times A \rightarrow S[/math] — функция перехода,
  • [math]\alpha \in [0, 1][/math] — learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации,
  • [math]\gamma \in [0, 1][/math] — discounting factor, чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.
fun Q-learning([math]S, A, R, T, \alpha, \gamma[/math]):
   for [math] s \in S[/math]:
       for [math] a \in A[/math]:
            Q(s, a) = rand()
   while Q is not converged:
       s = [math] \forall s \in S[/math]
       while s is not terminal:
          [math]\pi(s) = argmax_{a}{Q(s, a)}[/math]
          a = [math]\pi(s)[/math]
          r = R(s, a)
          s' = T(s, a)
          [math]Q(s', a) = (1 - \alpha) Q(s', a) + \alpha (r + \gamma \max\limits_{a'}{Q(s', a')})[/math]
          s = s'
   return Q

Ссылки