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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 6: Строка 6:
 
== Обучение с подкреплением ==  
 
== Обучение с подкреплением ==  
  
В обучении с подкреплением существует агент (''agent'') взаимодействует с окружающей средой (''environment''), предпринимая действия (''actions''). Окружающая среда дает награду (''reward'') за эти действия, а агент продолжает их предпринимать.
+
В обучении с подкреплением существует агент взаимодействует с окружающей средой, предпринимая действия. Окружающая среда его поощряет за эти действия, а агент продолжает их предпринимать.
  
Алгоритмы с частичным обучением пытаются найти стратегию, приписывающую состояниям (''states'') окружающей среды действия, одно из которых может выбрать агент в этих состояниях.
+
Алгоритмы с частичным обучением пытаются найти ''стратегию'', приписывающую ''состояниям'' окружающей среды действия, которые должен предпринять агент в этих состояниях.
  
 
Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
 
Среда обычно формулируется как [http://en.wikipedia.org/wiki/Markov_decision_process марковский процесс принятия решений] (МППР) с конечным множеством состояний, и в этом смысле алгоритмы обучения с подкреплением тесно связаны с динамическим программированием.
Строка 14: Строка 14:
  
 
При обучении с подкреплением, в отличии от обучения с учителем, не предоставляются верные пары "входные данные-ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.
 
При обучении с подкреплением, в отличии от обучения с учителем, не предоставляются верные пары "входные данные-ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно.
Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний (''exploration vs exploitation'').
+
Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний (англ. ''exploration vs exploitation'').
Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit о многоруком бандите].
+
Баланс изучения-применения при обучении с подкреплением исследуется в задаче [http://en.wikipedia.org/wiki/Multi-armed_bandit многорукого бандита].
  
 
Формально простейшая модель обучения с подкреплением состоит из:
 
Формально простейшая модель обучения с подкреплением состоит из:
* множества состояний окружения (''states'') <tex>S</tex>;
+
* множества состояний окружения  <tex>S</tex>
* множества действий (''actions'') <tex>A</tex>;
+
* множества действий <tex>A</tex>
* множества вещественнозначных скалярных "выигрышей" (''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 обучения с временными воздействиями].
 
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
 
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
  
 
Другие похожие методы: Адаптивный эвристический критик (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|link=http://toppromotion.ru/blog/seo-category/novyij-algoritm-pod-nazvaniem-%C2%ABmnogorukij-bandit%C2%BB.html|Многорукий бандит]]
 
[[File:bandit.jpg|thumb|link=http://toppromotion.ru/blog/seo-category/novyij-algoritm-pod-nazvaniem-%C2%ABmnogorukij-bandit%C2%BB.html|Многорукий бандит]]
Строка 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''.
  
=== Жадные и <tex>\epsilon</tex>-жадные стратегии (''greedy & <tex>\epsilon</tex>-greedy'') ===  
+
=== Жадные и <tex>\epsilon</tex>-жадные стратегии ===  
  
==== Жадная (''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>
  
 
В чем проблема?
 
В чем проблема?
Строка 158: Строка 158:
 
Но если награда случайная величина, то единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:
 
Но если награда случайная величина, то единичной попытки будет не достаточно. Поэтому модифицируем жадную стратегию следующим образом:
  
==== <tex>\epsilon</tex>-жадная (<tex>\epsilon</tex>-''greedy'') стратегия ====
+
==== <tex>\epsilon</tex>-жадная (<tex>\epsilon</tex>-greedy) стратегия ====
  
 
[[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> {{---}} параметр, с помощью которого можно настраивать поведение алгоритма.
Строка 188: Строка 188:
 
Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временем.
 
Эвристика: параметр <tex>\tau</tex> имеет смысл уменьшать со временем.
  
=== Метод UCB (''upper confidence bound'') ===  
+
=== Метод UCB (upper confidence bound) ===  
  
 
Предыдущие алгоритмы при принятии решения используют данные о среднем выигрыше. Проблема в том, что если действие даёт награду с какой-то вероятностью, то данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие.
 
Предыдущие алгоритмы при принятии решения используют данные о среднем выигрыше. Проблема в том, что если действие даёт награду с какой-то вероятностью, то данные от наблюдений получаются шумные и мы можем неправильно определять самое выгодное действие.
Строка 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
 +
  
 
== Ссылки ==
 
== Ссылки ==
  
 
*[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 Многорукий бандит]
Строка 260: Строка 259:
 
* [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]
 
[[Категория: Машинное обучение]]
 
[[Категория: Обучение с подкреплением]]
 

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

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

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

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