17.3. Q-обучение¶
В предыдущем разделе мы обсудили алгоритм итерации значений, который требует доступа к полной модели марковского процесса принятия решений (MDP), например, к функциям переходов и вознаграждений. В этом разделе мы рассмотрим Q-Learning (Watkins and Dayan, 1992) — алгоритм обучения функции значения без необходимости знания MDP. Этот алгоритм воплощает центральную идею обучения с подкреплением: он позволяет роботу собирать собственные данные.
17.3.1. Алгоритм Q-обучения¶
Вспомним, что итерация метода значения для функции значения действия в Итерация значений соответствует обновлению
Как мы обсуждали, реализация этого алгоритма требует знания МДП, в частности функции переходов \(P(s' \mid s, a)\). Ключевая идея Q-Learning заключается в замене суммирования по всем \(s' \in \mathcal{S}\) в вышеприведенном выражении суммированием по состояниям, посещенным роботом. Это позволяет нам обойтись без знания функции переходов.
17.3.2. Задача оптимизации, лежащая в основе Q-обучения¶
Представим, что робот использует политику \(\pi_e(a \mid s)\) для выбора действий. Как и в предыдущей главе, он собирает набор данных \(n\) траекторий, каждая из которых состоит из \(T\) шагов по времени \(\{ (s_t^i, a_t^i)_{t=0,\ldots,T-1}\}_{i=1,\ldots, n}\). Напомним, что итерация значений — это на самом деле набор ограничений, связывающих значение действия \(Q^*(s, a)\) для различных состояний и действий между собой. Мы можем реализовать приближённую версию итерации значений, используя данные, собранные роботом, применяя \(\pi_e\) в качестве
Сначала рассмотрим сходства и различия между этим выражением и итерацией значений, описанной выше. Если бы политика робота \(\pi_e\) совпадала с оптимальной политикой \(\pi^*\) и если бы он собрал бесконечное количество данных, то эта задача оптимизации была бы идентична задаче оптимизации, лежащей в основе итерации значений. Однако, если итерация значений требует знания \(P(s' \mid s, a)\), то целевая функция оптимизации не содержит этого члена. Мы не обманываем: поскольку робот использует политику \(\pi_e\) для выполнения действия \(a_t^i\) в состоянии \(s_t^i\), следующее состояние \(s_{t+1}^i\) представляет собой пример, выбранный из функции перехода. Таким образом, целевая функция оптимизации также имеет доступ к функции перехода, но неявно, через данные, собранные роботом.
Переменными нашей задачи оптимизации являются \(Q(s, a)\) для всех \(s \in \mathcal{S}\) и \(a \in \mathcal{A}\). Мы можем минимизировать целевую функцию с помощью градиентного спуска. Для каждой пары \((s_t^i, a_t^i)\) в нашем наборе данных мы можем записать
где \(\alpha\) — скорость обучения. Обычно в реальных задачах, когда робот достигает целевой точки, траектория завершается. Значение такого терминального состояния равно нулю, поскольку робот не совершает никаких дальнейших действий после этого состояния. Мы должны модифицировать наше обновление, чтобы обрабатывать такие состояния как
где \(\mathbb{1}_{s_{t+1}^i \textrm{ is terminal}}\) — индикаторная переменная, равная единице, если \(s_{t+1}^i\) является терминальным состоянием, и нулю в противном случае. Значение кортежей «состояние-действие» \((s, a)\), не входящих в набор данных, устанавливается равным \(-\infty\). Этот алгоритм известен как Q-обучение.
Решая эти обновления \(\hat{Q}\), которые аппроксимируют оптимальную функцию значения \(Q^*\), мы можем легко получить оптимальную детерминированную политику, соответствующую этой функции значения, используя
Могут возникать ситуации, когда несколько детерминированных политик соответствуют одной и той же оптимальной функции значения; такие ситуации можно разрешать произвольным образом, поскольку они имеют одинаковую функцию значения.
17.3.3. Исследование в Q-обучении¶
Политика, используемая роботом для сбора данных \(\pi_e\), имеет решающее значение для обеспечения корректной работы Q-Learning. В конце концов, мы заменили математическое ожидание по \(s'\), вычисляемое с помощью функции перехода \(P(s' \mid s, a)\), на данные, собранные роботом. Если политика \(\pi_e\) не исследует разнообразные области пространства состояний и действий, то легко представить, что наша оценка \(\hat{Q}\) будет плохим приближением к оптимальному \(Q^*\). Также важно отметить, что в такой ситуации оценка \(Q^*\) будет плохой во всех состояниях \(s \in \mathcal{S}\), а не только в тех, которые были посещены политикой \(\pi_e\). Это связано с тем, что цель Q-Learning (или итерация значений) представляет собой ограничение, связывающее значения всех пар «состояние-действие». Поэтому критически важно выбрать правильную политику \(\pi_e\) для сбора данных.
Мы можем смягчить эту проблему, используя полностью случайную политику \(\pi_e\), которая равномерно и случайно выбирает действия из множества \(\mathcal{A}\). Такая политика позволит посетить все состояния, но для этого потребуется большое количество траекторий.
Таким образом, мы приходим ко второй ключевой идее Q-обучения, а именно к исследованию. Типичные реализации Q-обучения связывают текущую оценку \(Q\) и политику \(\pi_e\) для определения
где \(\epsilon\) называется «параметром исследования» и выбирается пользователем. Политика \(\pi_e\) называется политикой исследования. Эта конкретная \(\pi_e\) называется \(\epsilon\)-жадной политикой исследования, поскольку она выбирает оптимальное действие (согласно текущей оценке \(\hat{Q}\)) с вероятностью \(1-\epsilon\), а остальную вероятность \(\epsilon\) тратит на случайное исследование. Мы также можем использовать так называемую политику исследования на основе софтмакс
где гиперпараметр \(T\) называется температурой. Большое значение \(\epsilon\) в \(\epsilon\)-жадной политике действует аналогично большому значению температуры \(T\) для софтмакс-политики.
Важно отметить, что при выборе стратегии исследования, зависящей от текущей оценки функции значения действия \(\hat{Q}\), нам необходимо периодически решать задачу оптимизации. В типичных реализациях Q-Learning после выполнения каждого действия с использованием \(\pi_e\) выполняется одно обновление на мини-пакете, использующее несколько пар «состояние-действие» из собранного набора данных (как правило, тех, что были собраны на предыдущем временном шаге работы робота).
17.3.4. Свойство «самовосстановления» Q-обучения¶
The dataset collected by the robot during Q-Learning grows with time. Both the exploration policy \(\pi_e\) and the estimate \(\hat{Q}\) evolve as the robot collects more data. This gives us a key insight into why Q-Learning works well. Consider a state \(s\): if a particular action \(a\) has a large value under the current estimate \(\hat{Q}(s,a)\), then both the \(\epsilon\)-greedy and the softmax exploration policies have a larger probability of picking this action. If this action actually is not the ideal action, then the future states that arise from this action will have poor rewards. The next update of the Q-Learning objective will therefore reduce the value \(\hat{Q}(s,a)\), which will reduce the probability of picking this action the next time the robot visits state \(s\). Bad actions, e.g., ones whose value is overestimated in \(\hat{Q}(s,a)\), are explored by the robot but their value is correct in the next update of the Q-Learning objective. Good actions, e.g., whose value \(\hat{Q}(s, a)\) is large, are explored more often by the robot and thereby reinforced. This property can be used to show that Q-Learning can converge to the optimal policy even if it begins with a random policy \(\pi_e\) (Watkins and Dayan, 1992).
Эта способность не только собирать новые данные, но и собирать данные нужного типа, является ключевой особенностью алгоритмов обучения с подкреплением, и именно это отличает их от обучения с учителем. Q-Learning, использующий глубокие нейронные сети (которые мы рассмотрим в главе DQN позже), стал причиной возрождения интереса к обучению с подкреплением (Mnih et al., 2013).
17.3.5. Реализация Q-обучения¶
Теперь мы покажем, как реализовать Q-обучение на задаче FrozenLake из Open AI Gym. Обратите внимание, что это та же настройка, которую мы рассматривали в эксперименте Итерация значений.
%matplotlib inline
import random
import numpy as np
from d2l import torch as d2l
seed = 0 # Random number generator seed
gamma = 0.95 # Discount factor
num_iters = 256 # Number of iterations
alpha = 0.9 # Learing rate
epsilon = 0.9 # Epsilon in epsilion gready algorithm
random.seed(seed) # Set the random seed
np.random.seed(seed)
# Now set up the environment
env_info = d2l.make_env('FrozenLake-v1', seed=seed)
В среде FrozenLake робот перемещается по \(4 \times 4\)-кратной сетке (это состояния) с помощью действий «вверх» (\(\uparrow\)), «вниз» (\(\rightarrow\)), «влево» (\(\leftarrow\)) и «вправо» (\(\rightarrow\)). Среда содержит множество ям (H) и замёрзших клеток (F), а также целевую клетку (G), которые все неизвестны роботу. Чтобы упростить задачу, мы предполагаем, что действия робота надёжны, то есть \(P(s' \mid s, a) = 1\) для всех \(s \in \mathcal{S}, a \in \mathcal{A}\). Если робот достигает цели, испытание завершается, и робот получает награду \(1\) независимо от действия; награда в любом другом состоянии равна \(0\) для всех действий. Цель робота — научиться такой политике, которая позволяет достичь целевой локации (G) из заданной стартовой локации (S) (это \(s_0\)), чтобы максимизировать возврат.
We first implement \(\epsilon\)-greedy method as follows:
def e_greedy(env, Q, s, epsilon):
if random.random() < epsilon:
return env.action_space.sample()
else:
return np.argmax(Q[s,:])
Теперь мы готовы реализовать Q-обучение:
def q_learning(env_info, gamma, num_iters, alpha, epsilon):
env_desc = env_info['desc'] # 2D array specifying what each grid item means
env = env_info['env'] # 2D array specifying what each grid item means
num_states = env_info['num_states']
num_actions = env_info['num_actions']
Q = np.zeros((num_states, num_actions))
V = np.zeros((num_iters + 1, num_states))
pi = np.zeros((num_iters + 1, num_states))
for k in range(1, num_iters + 1):
# Reset environment
state, done = env.reset(), False
while not done:
# Select an action for a given state and acts in env based on selected action
action = e_greedy(env, Q, state, epsilon)
next_state, reward, done, _ = env.step(action)
# Q-update:
y = reward + gamma * np.max(Q[next_state,:])
Q[state, action] = Q[state, action] + alpha * (y - Q[state, action])
# Move to the next state
state = next_state
# Record max value and max action for visualization purpose only
for s in range(num_states):
V[k,s] = np.max(Q[s,:])
pi[k,s] = np.argmax(Q[s,:])
d2l.show_Q_function_progress(env_desc, V[:-1], pi[:-1])
q_learning(env_info=env_info, gamma=gamma, num_iters=num_iters, alpha=alpha, epsilon=epsilon)
Этот результат показывает, что Q-обучение может найти оптимальное решение для данной задачи примерно после 250 итераций. Однако при сравнении этого результата с результатом алгоритма итерации значений (см. Реализация итерации значений) видно, что алгоритму итерации значений требуется значительно меньше итераций для нахождения оптимального решения этой задачи. Это связано с тем, что алгоритм итерации значений имеет доступ к полной марковской модели принятия решений (MDP), тогда как Q-обучение — нет.
17.3.6. Резюме¶
Q-learning — один из самых фундаментальных алгоритмов обучения с подкреплением. Он находится в центре недавнего успеха этого направления, в частности, в задачах обучения игре в видеоигры (Mnih et al., 2013). Для реализации Q-learning не требуется полное знание марковского процесса принятия решений (MDP), например, функций переходов и вознаграждений.
17.3.7. Упражнения¶
Попробуйте увеличить размер сетки до \(8 \times 8\). По сравнению с сеткой \(4 \times 4\), сколько итераций потребуется для нахождения оптимальной функции значения?
Запустите алгоритм Q-обучения снова с \(\gamma\) (т. е. «gamma» в приведённом выше коде), когда он равен \(0\), \(0.5\) и \(1\), и проанализируйте полученные результаты.
Запустите алгоритм Q-обучения ещё раз с \(\epsilon\) (т. е. «epsilon» в приведённом выше коде), равным \(0\), \(0.5\) и \(1\), и проанализируйте полученные результаты.