77
правок
Изменения
Нет описания правки
Игра агента со средой:
* инициализация стратегии <tex>\pi_1(a | s)</tex> и состояния среды <tex>s_1</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>;
::<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>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_1(a)</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^∗(a) = \lim \limits_{t \rightarrow \infty} Q_t(a) \rightarrow max </tex> {{---}} ценность действия <tex>a</tex>.
У нас есть автомат {{---}} <tex>N</tex>-рукий бандит, на каждом шаге мы выбираем за какую из <tex>N</tex> ручек автомата дернуть,
==== Жадная (''greedy'') стратегия ====
* <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>t</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>t</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>. Обновление функции использует взвешенное среднее между старым и новым значениями:
[[File:Q-Learning.png|thumb|313px|link=https://en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]]
* <tex>S</tex> — множество состояний,* <tex>A</tex> — множество действий,* <tex>R = S \times A \rightarrow \mathbb{R}</tex> {{---}} функция награды,* <tex>T = S \times A \rightarrow 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>):
