Обучение с подкреплением - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:13:27Z

rollbackEdits.php mass rollback

94.16.121.91 в 05:57, 1 сентября 2022

2022-09-01T05:57:30Z

Dariyakovleva в 19:43, 30 января 2019

2019-01-30T19:43:48Z

Dariyakovleva в 19:39, 30 января 2019

2019-01-30T19:39:20Z

Внесённые изменения

Flyingleafe в 17:50, 25 января 2019

2019-01-25T17:50:56Z

Внесённые изменения

Flyingleafe в 22:57, 24 января 2019

2019-01-24T22:57:05Z

Flyingleafe: /* Алгоритм Actor-Critic */

2019-01-24T11:46:01Z

‎Алгоритм Actor-Critic

Flyingleafe: /* Использование будущего выигрыша вместо полного выигрыша */

2019-01-24T11:44:40Z

‎Использование будущего выигрыша вместо полного выигрыша

Flyingleafe в 01:07, 24 января 2019

2019-01-24T01:07:09Z

Flyingleafe в 23:17, 23 января 2019

2019-01-23T23:17:04Z

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
@@ Строка 229: / Строка 208: @@
 == Q-learning ==
-На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{---}} то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.
+На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{---}} то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.
 Таким образом, алгоритм это функция качества от состояния и действия:

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
@@ Строка 208: / Строка 229: @@
 == Q-learning ==
-На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{---}} то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.
+На основе получаемого от среды вознаграждения агент формирует функцию полезности <tex>Q</tex>, что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ <tex>Q</tex>-обучения {{---}} то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.
 Таким образом, алгоритм это функция качества от состояния и действия:

@@ Строка 40: / Строка 40: @@
 Игра агента со средой:
 * инициализация стратегии <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>r_{t + 1} ∼ p(r | a_t, s_t)</tex> и новое состояние <tex>s_{t + 1} ∼ p(s | a_t, s_t)</tex>;
@@ Строка 88: / Строка 88: @@
 ::<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>t = 1 \ldots T</tex>;
+* для всех <tex>t = 1 \ldots T</tex>:
 ** агент выбирает действие (ручку) <tex>a_t ∼ \pi_t(a)</tex>;
 ** среда генерирует награду <tex>r_t ∼ p_{a_t}(r)</tex>;
 ** агент корректирует стратегию <tex>\pi_{t+1}(a)</tex>.
-<tex>Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max </tex> {{---}} средняя награда в <i>t</i> играх <br />
+<tex>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> ручек автомата дернуть,
@@ Строка 134: / Строка 134: @@
 ==== Жадная (''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>
@@ Строка 162: / Строка 162: @@
 [[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>
@@ Строка 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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
@@ Строка 226: / Строка 226: @@
 [[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>):

← Предыдущая		Версия 22:57, 24 января 2019
Строка 415:		Строка 415:
	* [http://rll.berkeley.edu/deeprlcourse/f17docs/lecture_4_policy_gradient.pdf Policy Gradients. CS 294-112: Deep Reinforcement Learning, Sergey Levine.]		* [http://rll.berkeley.edu/deeprlcourse/f17docs/lecture_4_policy_gradient.pdf Policy Gradients. CS 294-112: Deep Reinforcement Learning, Sergey Levine.]
	* [http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_5_actor_critic_pdf.pdf Actor-Critic Algorithms. CS 294-112: Deep Reinforcement Learning, Sergey Levine.]		* [http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_5_actor_critic_pdf.pdf Actor-Critic Algorithms. CS 294-112: Deep Reinforcement Learning, Sergey Levine.]
		+
		+	[[Категория: Машинное обучение]]
		+	[[Категория: Обучение с подкреплением]]

@@ Строка 370: / Строка 370: @@
 Здесь <tex>Q_{\tau_i, t}</tex> -- это оценка будущего выигрыша из состояния <tex>s_t^i</tex> при условии действия <tex>a_t^i</tex>, которая базируется только на одном сценарии <tex>\tau_i</tex>. Это плохое приближение ожидаемого будущего выигрыша -- истинный ожидаемый будущий выигрыш выражается формулой
-: <tex> Q^{\pi}(s_t, a_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'} | s_t, a_t] } </tex>
+: <tex> Q^{\pi}(s_t, a_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'}) | s_t, a_t] } </tex>
 Также, в целях уменьшения дисперсии случайной величины, введем опорное значение для состояния <tex>s_t</tex>, которое назовем ''ожидаемой ценностью'' (value) этого состояния. Ожидаемая ценность состояния <tex>s_t</tex> -- это ожидаемый будущий выигрыш при совершении некоторого действия в этом состоянии согласно стратегии <tex>\pi_{\theta}(a|s)</tex>:
-: <tex> V^{\pi}(s_t) = E_{a_t \sim \pi_{\theta}(a_t | s_t)} [Q^{\pi}(s_t, a_t)] = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'} | s_t]}</tex>
+: <tex> V^{\pi}(s_t) = E_{a_t \sim \pi_{\theta}(a_t | s_t)} [Q^{\pi}(s_t, a_t)] = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'}) | s_t]}</tex>
 Таким образом, вместо ожидаемого будущего выигрыша при оценке <tex>\nabla_{\theta} J(\theta)</tex> будем использовать функцию ''преимущества'' (advantage):
@@ Строка 391: / Строка 391: @@
 : <tex> A^{\pi}(s_t^i, a_t^i) = Q^{\pi}(s_t, a_t) - V^{\pi}(s_t) \approx r(s_t, a_t) + V^{\pi}(s_{t+1}) - V^{\pi}(s_t) </tex>
-Теперь нам нужно уметь оценивать <tex>V^{\pi}(s_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'} | s_t] }</tex>. Мы можем делать это, опять же, с помощью метода Монте-Карло -- так мы получим несмещенную оценку. Но это будет работать не существенно быстрее, чем обычный policy gradient. Вместо этого заметим, что при фиксированных <tex>s_t</tex> и <tex>a_t</tex> выполняется:
+Теперь нам нужно уметь оценивать <tex>V^{\pi}(s_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'}) | s_t] }</tex>. Мы можем делать это, опять же, с помощью метода Монте-Карло -- так мы получим несмещенную оценку. Но это будет работать не существенно быстрее, чем обычный policy gradient. Вместо этого заметим, что при фиксированных <tex>s_t</tex> и <tex>a_t</tex> выполняется:
 : <tex> V^{\pi}(s_t) = r(s_t, a_t) + V^{\pi}(s_{t+1})</tex>
@@ Строка 399: / Строка 399: @@
 : <tex> V^{\pi}(s_t) \leftarrow (1 - \beta) V^{\pi}(s_t) + \beta (r(s_t, a_t) + V^{\pi}(s_{t+1})) </tex>
 Такой пересчет мы можем производить каждый раз, когда агент получает вознаграждение за действие.
 == Ссылки ==

@@ Строка 358: / Строка 358: @@
 Так как в момент времени <tex>t</tex> от действия <tex>a_t</tex> зависят только <tex>r(s_{t'}, a_{t'})</tex> для <tex> t' \leq t</tex>, это выражение можно переписать как
-: <tex> \nabla_{\theta} J(\theta) \approx E_{\tau \sim p_{\theta}(\tau)} \left[ \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \underbrace{\left( \sum_{t'=t}^{T} {r(s_t', a_t')} \right)}_{= Q_{\tau, t}} \right]</tex>
+: <tex> \nabla_{\theta} J(\theta) \approx E_{\tau \sim p_{\theta}(\tau)} \left[ \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \underbrace{\left( \sum_{t'=t}^{T} {r(s_{t'}, a_{t'})} \right)}_{= Q_{\tau, t}} \right]</tex>
 Величина <tex>Q_{\tau, t}</tex> -- ''будущий выигрыш'' (reward-to-go) на шаге <tex>t</tex> в сценарии <tex>\tau</tex>

@@ Строка 326: / Строка 326: @@
 * Очень низкая скорость работы -- требуется большое количество вычислений для оценки <tex>\nabla_{\theta} J(\theta)</tex> по методу Монте-Карло, так как:
 ** для получения всего одного семпла требуется произвести <tex>T</tex> взаимодействий со средой;
-** случайная величина <tex>\nabla_{\theta} \log p_{\theta}(\tau) R_{\tau}</tex> имеет большую дисперсию, поэтому для точной оценки <tex>\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right]</tex> требуется много семплов;
+** случайная величина <tex>\nabla_{\theta} \log p_{\theta}(\tau) R_{\tau}</tex> имеет большую дисперсию, так как для разных <tex>\tau</tex> значения <tex>R_{\tau}</tex> могут очень сильно различаться, поэтому для точной оценки <tex>\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right]</tex> требуется много семплов;
 ** cемплы, собранные для предыдущих значений <tex>\theta</tex>, никак не переиспользуются на следующем шаге, семплирование нужно делать заново на каждом шаге градиентного спуска.
 * В случае конечных МППР Q-learning сходится к глобальному оптимуму, тогда как policy gradient может застрять в локальном.
@@ Строка 360: / Строка 360: @@
 : <tex> \nabla_{\theta} J(\theta) \approx E_{\tau \sim p_{\theta}(\tau)} \left[ \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \underbrace{\left( \sum_{t'=t}^{T} {r(s_t', a_t')} \right)}_{= Q_{\tau, t}} \right]</tex>
-Величина <tex>Q_{\tau, t}</tex> -- ''будущий выигрыш'' на шаге <tex>t</tex> в сценарии <tex>\tau</tex>
+Величина <tex>Q_{\tau, t}</tex> -- ''будущий выигрыш'' (reward-to-go) на шаге <tex>t</tex> в сценарии <tex>\tau</tex>
 == Ссылки ==

@@ Строка 314: / Строка 314: @@
 Двигаясь вверх по этому градиенту, мы повышаем логарифм функции правдоподобия для сценариев, имеющих большой положительный <tex>R_{\tau}</tex>.
 === Преимущества и недостатки policy gradient по сравнению с Q-learning ===
@@ Строка 325: / Строка 324: @@
 Недостатки:
-* Скорость работы: требуется большое количество вычислений для оценки <tex>\nabla_{\theta} J(\theta)</tex> по методу Монте-Карло, так как для получения всего одного семпла требуется произвести <tex>T</tex> взаимодействий со средой.
+* Очень низкая скорость работы -- требуется большое количество вычислений для оценки <tex>\nabla_{\theta} J(\theta)</tex> по методу Монте-Карло, так как:
 * В случае конечных МППР Q-learning сходится к глобальному оптимуму, тогда как policy gradient может застрять в локальном.
 == Ссылки ==