Q-Learning впервые был представлен в 1989 году Кристофером Уоткинсом как расширение парадигмы динамического программирования. Q-обучение также послужило основой для некоторых потрясающих достижений в области глубокого обучения с подкреплением, появившихся в результате Google DeepMind в 2013 году, и помогло вывести эти методы на карту. Но прежде чем мы начнем учиться играть в игры Atari, давайте сначала сосредоточимся на создании основ, сосредоточившись на табличном Q-обучении.
Простой пример
Обучение с подкреплением основано на Марковских процессах принятия решений (MDP), которые состоят из состояний (s_t), в которых находится агент, и действий (a_t), которые агент может предпринять, чтобы перейти в новое состояние (s_{t+1}) и получить награда или наказание (R_{t+1}). Q-обучение направлено на изучение соответствующего Q-значения (подумайте о качестве) данной пары действие-состояние. Когда количество состояний и действий невелико и четко определено, мы можем представить эти состояния и действия в таблице.
Давайте представим простой мир сетки с двумя действиями, левым и правым, и четырьмя ячейками сетки с целью (G) на дальней стороне. Если агент достигает цели, он получает награду +1, и эпизод заканчивается.
Решить такую маленькую среду несложно, но она позволяет легко визуализировать Q-таблицу.
Q-значения здесь понимаются как ожидаемое дисконтированное вознаграждение, которое получит агент, если он выполнит действие (левое или правое в данном случае) в заданном состоянии (1, 2, 3 или 4). Чтобы рассчитать значения Q, мы используем уравнение обновления Q-обучения.
Так как это работает? Начиная со скобок, мы берем вознаграждение, полученное за выбранное нами действие (R_{t+1}), добавляем его к дисконтированному максимальному значению Q для этого состояния и вычитаем его из нашей текущей оценки Q- ценность этого состояния. Это вычисляет ошибку между действием, которое мы только что предприняли, и тем, что мы считаем лучшим действием, доступным нам в этом новом состоянии (S_{t+1}). Затем мы уменьшаем ошибку на величину нашего шага (α) и добавляем ее к нашей текущей оценке для Q(s_t, a_t), что затем дает нашу новую оценку для Q(s_t,a_t).
Это имеет смысл, потому что Q(s_t,a_t) является приблизительным значением общей дисконтированной будущей награды от этого состояния при совершении этого действия. Это означает, что когда мы совершаем это действие и получаем вознаграждение, вознаграждение плюс наше приближение должны равняться дисконтированной сумме всех будущих вознаграждений, если мы следуем жадной политике. Другими словами, мы хотим изучить функцию, чтобы:
Если мы инициализируем все значения в нашей Q-таблице равными 0, выберем γ=1 и α=0,1, мы увидим, как это может работать. Скажем, агент находится в позиции 1 и движется вправо. В этом случае наше новое значение Q, Q(1, R), останется равным 0, потому что мы не получаем вознаграждение от 1 → 2, и у нас нет ненулевых значений в нашей Q-таблице. То же самое, если мы снова перейдем вправо от 2 до 3. Если мы переместимся 3→4, мы получим вознаграждение, поэтому мы можем обновить нашу таблицу. Теперь у нас есть:
Это значение начнет распространяться по таблице с каждым эпизодом, давая нашему агенту возможность чему-то научиться! Поскольку позиция 4 — это конечное состояние, мы можем вернуться к началу и повторить это снова. Но теперь наша Q-таблица выглядит так:
Выполнив ту же процедуру еще раз, мы получим Q(1, R) = 0, но теперь мы получим значение для Q(2, R).
Из нашей таблицы видно, что max(Q(3))=0,1, поэтому имеем:
Мы можем продолжать это, пока не достигнем некоторых критериев сходимости. В этой сверхпростой среде мы можем определить оптимальную политику путем проверки (всегда идти правильно). Для реальных тренировочных сред нам нужно какое-то правило выбора действия. Как правило, выбираются ε-жадные политики, что означает, что мы смотрим на нашу Q-таблицу и выбираем действие, соответствующее наибольшему значению для этого состояния (max(Q(s_t))), это жадная часть. Но у нас есть некоторая вероятность ϵ (часто равная 0,05), что мы выбираем случайное действие, чтобы гарантировать, что мы достаточно изучаем окружающую среду.
Полный алгоритм Q-обучения выглядит следующим образом:
Давайте посмотрим, как это работает, на другом простом примере мира сетки.
Сеточный мир
Если вы еще этого не сделали, вы можете получить код для этого мира сетки здесь, на GitHub. Оттуда вы можете импортировать следующие пакеты, и все будет готово.
import numpy as np import matplotlib.pyplot as plt from gridworld import * # Get this from GitHub! np.random.seed(1234)
Мир сетки представляет собой среду 3×5 с двумя конечными состояниями, ловушкой (T) и целью (G). Вы получаете награду −5 за ловушку и +10 за цель. Вы можете визуализировать мир сетки с помощью следующих команд:
env = gridworld() env.show_grid()
Для начала давайте инициализируем нашу Q-таблицу нулями. Обратите внимание, что Q-таблица будет иметь на одно измерение больше, чем мир сетки. В приведенном выше простом одномерном примере у нас была двумерная Q-таблица. В этом двухмерном сеточном мире у нас будет трехмерная таблица. Для этого я настроил его так, чтобы строки и столбцы Q-таблицы соответствовали строкам и столбцам мира сетки, а глубина соответствовала действиям. В этом случае у нас есть четыре действия (вверх, вниз, влево и вправо), поэтому у нас будет таблица 3×5×4.
q_table = np.zeros((env.dim[0], env.dim[1], len(env.action_space))) q_table.shape
(3, 4, 5)
Используя Q-таблицу, мы можем легко получить доступ к записям, используя состояния и действия в качестве индексов.
Теперь давайте настроим наши параметры и реализуем алгоритм. Установите количество эпизодов равным 1000, γ=0,99, ϵ=0,05 и α=0,01.
# Parameters num_episodes = 1000 gamma = 0.99 eps = 0.05 lr = 0.01 # learning rate = alpha
Реализованный ниже алгоритм соответствует приведенному выше описанию алгоритма и должен быть простым (если нет, оставьте комментарий).
# Empty lists to track the number of rewards
ep_rewards = []
n_steps = []
# Zero out the Q-table
q_table = np.zeros((env.dim[0], env.dim[1], len(env.action_space)))
# Loop through the algorithm
for ep in range(num_episodes):
s_0 = env.reset()
done = False
rewards = 0
while done == False:
# Take random action with epsilon probability
if np.random.rand() < eps:
action = np.random.choice(env.action_space)
else:
# Take greedy action
action = np.argmax(q_table[s_0[0], s_0[1]])
s_1, reward, done = env.step(action)
# Update the Q-table
q_table[s_0[0], s_0[1], action] += lr*(reward + \
gamma*np.max(q_table[s_1[0], s_1[1]]) \
- q_table[s_0[0], s_0[1], action])
s_0 = s_1.copy()
rewards += reward
if done:
ep_rewards.append(rewards)
# Calculate rolling average
mean_rewards = [np.mean(ep_rewards[n-10:n]) if n > 10 else np.mean(ep_rewards[:n])
for n in range(1, len(ep_rewards))]
# Plot results
plt.figure(figsize=(12,8))
plt.plot(ep_rewards)
plt.plot(mean_rewards)
plt.title('Gridworld Rewards')
plt.xlabel('Episode')
plt.ylabel('Reward')
plt.show()
Мы видим, что алгоритм быстро учится хорошей политике, позволяющей ему решать окружающую среду.
Кроме того, мы можем увидеть, как он оценивает каждую из пар состояние-действие, отобразив значения Q-таблицы для каждого действия в виде тепловой карты.
plt.figure(figsize=(12,8))
for a_idx in env.action_space:
plt.subplot(2,2,a_idx + 1)
sns.heatmap(q_table[:,:, a_idx], cmap='hot',
vmin=np.min(q_table), vmax=np.max(q_table))
# Get direction name from dictionary
direction = [i for i in env.action_dict if env.action_dict[i] == a_idx]
plt.title('Q-Values for Moving {}'.format(direction[0]))
plt.tight_layout()
plt.show()
Как и ожидалось, движение вниз и вправо — лучшие доступные нам варианты.
Наконец, я создал метод plot_policy в среде gridworld, который вы можете вызывать для просмотра политики, заданной вашей текущей Q-таблицей. Это помогает синтезировать различные представления и посмотреть, что алгоритм рекомендует нам делать.
env.plot_policy(q_table)
Алгоритм будет сходиться к оптимальной политике q∗ в пределе и может быстро аппроксимировать большие и сложные среды. Почувствуйте это, реализовав алгоритм для решения некоторых табличных сред OpenAI Gym или создайте свой собственный. Некоторые из них носят стохастический характер (например, среда замерзшего озера) и все еще могут быть успешно решены с помощью табличного подхода Q-обучения.
Q-обучение — это мощный алгоритм обучения, который многого достиг в мире RL. Этот табличный метод довольно прост и понятен, что делает его ключевым шагом к пониманию нюансов глубокого Q-обучения и более продвинутых методов.
Первоначально опубликовано на https://www.datahubbs.com 6 января 2019 г.
