Редактирование: Обучение с подкреплением

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 18: Строка 18:
  
 
Формально простейшая модель обучения с подкреплением состоит из:
 
Формально простейшая модель обучения с подкреплением состоит из:
* множества состояний окружения (''states'')  <tex>S</tex>;
+
* множества состояний окружения (''states'')  <tex>S</tex>
* множества действий (''actions'') <tex>A</tex>;
+
* множества действий (''actions'') <tex>A</tex>
* множества вещественнозначных скалярных "выигрышей" (''rewards'').
+
* множества вещественнозначных скалярных "выигрышей" (''rewards'')
  
 
В произвольный момент времени <tex>t</tex> агент характеризуется состоянием <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>.
Строка 26: Строка 26:
 
Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию <tex>\pi: S \to A</tex>, которая максимизирует величину <tex>R=r_0 + r_1+\cdots+r_n</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>R=\sum_t \gamma^t r_t</tex>
  
 
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{---}} дисконтирующий множитель для "предстоящего выигрыша").
 
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{---}} дисконтирующий множитель для "предстоящего выигрыша").
Строка 34: Строка 34:
 
=== Постановка задачи обучения с подкреплением ===
 
=== Постановка задачи обучения с подкреплением ===
  
[[File:RL.png|thumb|link=https://econophysica.ru/services/machine-learning/|Взаимодействие агента со средой]]
+
[[File:RL.png|thumb|link=https://skymind.ai/wiki/deep-reinforcement-learning|RL-схема]]
  
 
<tex>S</tex> {{---}} множество состояний среды
 
<tex>S</tex> {{---}} множество состояний среды
  
 
Игра агента со средой:
 
Игра агента со средой:
* инициализация стратегии <tex>\pi_1(a | s)</tex> и состояния среды <tex>s_1</tex>;
+
* инициализация стратегии <tex>\pi_1(a | s)</tex> и состояния среды <tex>s_1</tex>
* для всех <tex>t = 1 \ldots 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>
Строка 55: Строка 55:
  
 
Наивный подход к решению этой задачи подразумевает следующие шаги:
 
Наивный подход к решению этой задачи подразумевает следующие шаги:
* опробовать все возможные стратегии;
+
* опробовать все возможные стратегии
* выбрать стратегию с наибольшим ожидаемым выигрышем.
+
* выбрать стратегию с наибольшим ожидаемым выигрышем
  
 
Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или бесконечно.
 
Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или бесконечно.
Строка 70: Строка 70:
 
либо ожидаемый выигрыш, при принятии решения <tex>a</tex> в состоянии <tex>s</tex> и дальнейшем соблюдении <tex>\pi</tex>,
 
либо ожидаемый выигрыш, при принятии решения <tex>a</tex> в состоянии <tex>s</tex> и дальнейшем соблюдении <tex>\pi</tex>,
  
::<tex>Q(s, a) = E[R|s, \pi, a]</tex>,
+
::<tex>Q(s, a) = E[R|s, \pi, a]</tex>.
  
 
Если для выбора оптимальной стратегии используется функция полезности <tex>Q</tex>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.
 
Если для выбора оптимальной стратегии используется функция полезности <tex>Q</tex>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.
Строка 84: Строка 84:
 
Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).
 
Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).
  
Поэтому построение искомой оценки при <tex>\gamma \in (0, 1)</tex> неочевидно. Однако, можно заметить, что <tex>R</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>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>V</tex>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями] (''temporal difference (TD) learning'').
 
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
 
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
  
Строка 99: Строка 99:
 
=== Формулировка ===
 
=== Формулировка ===
  
<tex>A</tex> {{---}} множество возможных ''действий'' (ручек автомата),
+
<tex>A</tex> {{---}} множество возможных ''действий'' (ручек автомата)
  
<tex>p_a(r)</tex> {{---}} неизвестное распределение ''награды'' <tex>r \in R</tex> <tex>\forall a \in 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_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 \ldots 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_{t \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>N</tex>-рукий бандит, на каждом шаге мы выбираем за какую из <tex>N</tex> ручек автомата дернуть,
Строка 126: Строка 126:
 
Проблема в том, что распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением. Для <tex>K</tex> экспериментов <tex>\xi_k</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>,
+
<tex>E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex>
  
 
Задача является модельной для понимания конфликта между ''exploitation''-''exploration''.
 
Задача является модельной для понимания конфликта между ''exploitation''-''exploration''.
Строка 134: Строка 134:
 
==== Жадная (''greedy'') стратегия ====
 
==== Жадная (''greedy'') стратегия ====
  
* <tex>P_a = 0</tex> <tex>\forall a \in \{1 \ldots N\} </tex> {{---}} сколько раз было выбрано действие <tex>a</tex>,
+
* <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>Q_a = 0</tex> <tex>\forall a \in \{1 \ldots N\}</tex> {{---}} текущая оценка математического ожидания награды для действия <tex>a</tex>
  
 
На каждом шаге <tex>t</tex>
 
На каждом шаге <tex>t</tex>
 
* Выбираем действие с максимальной оценкой математического ожидания:
 
* Выбираем действие с максимальной оценкой математического ожидания:
  
:<tex>a_t = argmax_{a \in A} Q_a </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>R(a_t)</tex>
  
 
* Обновляем оценку математического ожидания для действия <tex>a_t</tex>:
 
* Обновляем оценку математического ожидания для действия <tex>a_t</tex>:
  
:<tex>P_{a_t} = P_{a_t} + 1</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>Q_{a_t} = Q_{a_t} + \frac{1}{P_{a_t}} (R(a_t) − Q_{a_t})</tex>
  
 
В чем проблема?
 
В чем проблема?
Строка 162: Строка 162:
 
[[File:Eps-greedy.png|thumb|313px|link=https://vbystricky.github.io/2017/01/rl_multi_arms_bandits.html|Пример. Награда для стратегии с различными <tex>\epsilon</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>\epsilon \in (0,1)</tex>
  
 
На каждом шаге <tex>t</tex>
 
На каждом шаге <tex>t</tex>
  
* Получим значение <tex>\alpha</tex> {{---}} случайной величины равномерно распределенной на отрезке <tex>(0, 1)</tex>;
+
* Получим значение <tex>\alpha</tex> {{---}} случайной величины равномерно распределенной на отрезке <tex>(0, 1)</tex>
* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>a_t \in A</tex> случайно и равновероятно, иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания;
+
* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>a_t \in A</tex> случайно и равновероятно, иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания:
* Обновляем оценки так же как в жадной стратегии.
+
* Обновляем оценки так же как в жадной стратегии
  
 
Если <tex>\epsilon = 0</tex>, то это обычная жадная стратегия. Однако если <tex>\epsilon > 0</tex>, то в отличии от жадной стратегии на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование" случайных действий.
 
Если <tex>\epsilon = 0</tex>, то это обычная жадная стратегия. Однако если <tex>\epsilon > 0</tex>, то в отличии от жадной стратегии на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование" случайных действий.
Строка 176: Строка 176:
 
Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</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>\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 \in (0, \infty)</tex> {{---}} параметр, с помощью которого можно настраивать поведение алгоритма.
Строка 196: Строка 196:
 
Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:
 
Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:
  
<tex>\pi_{t+1}(a) = Q_t(a) + b_a</tex>,
+
<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>b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} </tex> {{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.
Строка 212: Строка 212:
 
Таким образом, алгоритм это функция качества от состояния и действия:
 
Таким образом, алгоритм это функция качества от состояния и действия:
  
:<tex>Q: S \times A \to \mathbb{R}</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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
 
Перед обучением <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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
Строка 226: Строка 226:
 
[[File:Q-Learning.png|thumb|313px|link=https://en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]]
 
[[File:Q-Learning.png|thumb|313px|link=https://en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]]
  
* <tex>S</tex> — множество состояний,
+
* <tex>S</tex> — множество состояний
* <tex>A</tex> — множество действий,
+
* <tex>A</tex> — множество действий
* <tex>R = S \times A \rightarrow \mathbb{R}</tex> {{---}} функция награды,
+
* <tex>R = S \times A \rightarrow \mathbb{R}</tex> функция награды
* <tex>T = S \times A \rightarrow S</tex> {{---}} функция перехода,
+
* <tex>T = S \times A \rightarrow S</tex> функция перехода
* <tex>\alpha \in [0, 1]</tex> {{---}} learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации,
+
* <tex>\alpha \in [0, 1]</tex> learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации
* <tex>\gamma \in [0, 1]</tex> {{---}} discounting factor, чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.
+
* <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>):
Строка 237: Строка 237:
 
         '''for''' <tex> a \in A</tex>:
 
         '''for''' <tex> a \in A</tex>:
 
             Q(s, a) = rand()
 
             Q(s, a) = rand()
     '''while''' Q is not converged:
+
     '''while''' Q не сошелся:
 
         s = <tex> \forall s \in S</tex>
 
         s = <tex> \forall s \in S</tex>
         '''while''' s is not terminal:
+
         '''while''' s не конечное состояние:
 
           <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>
Строка 247: Строка 247:
 
           s = s'
 
           s = s'
 
     return Q
 
     return Q
 +
  
 
== Ссылки ==
 
== Ссылки ==
Строка 260: Строка 261:
 
* [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]
 
[[Категория: Машинное обучение]]
 
[[Категория: Обучение с подкреплением]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: