Содержание страницы
Метод N шагов
Здравствуйте и вновь добро пожаловать на занятия по теме «Глубокое обучение с подкреплением: глубокое обучение на языке Python, часть 7».
В этой объёмной статье мы расширим наше понимание обучения методом временных разниц. В частности, как вы знаете, до этого момента мы рассматривали так называемый метод TD(0). Но есть и более обобщённая его форма – TD(λ). Эта часть полностью посвящена тому, как расширить метод TD(0), чтобы получить TD(λ). Вы увидите, что TD(λ) предоставляет собой компромисс между одношаговыми методами обучения вроде TD(0) и вычислением полной отдачи, как в методе Монте-Карло.
Первое, что необходимо узнать при обсуждении TD(λ), – это метод N шагов, и именно ему и посвящена данная лекция. Работает он следующим образом. Мы уже знаем, что функция ценности может быть описана рекурсивно:
Мы также знаем, что можем оценить V путём усреднения отдач по множеству различных эпизодов:
А ещё из метода TD(0) мы знаем, что можем оценить само G, используя текущую оценку V:
А ещё из метода TD(0) мы знаем, что можем оценить само G, используя текущую оценку V:
Справедливо спросить, что является наиболее точным в этой оценке G? Это должно быть вознаграждение r, ведь это фактическая величина, полученная из эксперимента. Тогда вполне вероятно, что если мы используем больше значений r и меньше значений V, то наша оценка G станет более точной. Например, вместо того, чтобы брать первое вознаграждение, а затем использовать V для оценки остального, можно взять первое вознаграждение, затем следующее за ним вознаграждение, а затем использовать для оценки остального следующее V:
Напомним, что метод Монте-Карло является крайним случаем, когда мы вовсе не используем V:
Заметьте, мы можем использовать верхний индекс для G, чтобы видеть, сколько используется R:
Как видите, это даёт нам нечто вроде дискретного перехода от метода TD(0) к методу Монте-Карло. Поскольку обучение методом Монте-Карло означает, что агент может быть обновлён только по окончании эпизода, а метод TD(0) означает, что агент может быть обновлён после одного этапа, то использование N этапов фактических вознаграждений означает, что необходимо выждать окончания N этапов, прежде чем агент может быть обновлён, так что можно сформировать целевую переменную, использовав полученные фактические вознаграждения. В общем случае, если мы хотим использовать n шагов R, то может создать целевую переменную следующим образом:
Для обновления V, если мы решаем проблему предсказания, уравнение обновления не меняется; единственное изменение – это само G: нужно подождать n шагов, прежде чем можно будет обновлять V для состояния, в котором мы сейчас находимся. Это, разумеется, относится как к табличным методам, так и методам приближения функций:
И, конечно же, это можно перенести на проблему управления, когда мы используем Q вместо V. Если мы выполняем алгоритм SARSA, обновление будет соответствовать избранному действию, а действие будет выбираться жадным или эпсилон-жадным алгоритмом относительно Q:
Метод N шагов в коде
Мы используем уже написанную программу Q-обучения для машины на склоне, чтобы, кроме всего прочего, можно было сосредоточиться на части с методом N шагов. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую сделать именно так, то соответствующий этой лекции файл называется n_step.py в папке mountaincar.
Вначале у нас идут все обычные импорты, а также кое-что из программы с Q-обучением:
from __future__ import print_function, division
from builtins import range
# Note: you may need to update your version of future
# sudo pip install -U future
#
# Note: gym changed from version 0.7.3 to 0.8.0
# MountainCar episode length is capped at 200 in later versions.
# This means your agent can’t learn as much in the earlier episodes
# since they are no longer as long.
#
# Adapt Q-Learning script to use N-step method instead
import gym
import os
import sys
import numpy as np
import matplotlib.pyplot as plt
from gym import wrappers
from datetime import datetime
# code we already wrote
import q_learning
from q_learning import plot_cost_to_go, FeatureTransformer, Model, plot_running_avg
Следующим идёт определение собственного класса SGDRegressor. Я обнаружил, что он работает лучше, чем SGDRegressor библиотеки Sci-kit Learn. Реализация та же, что и прежде, разве что пришлось изменить конструктор, так чтобы он принимал любой аргумент.
class SGDRegressor:
def __init__(self, **kwargs):
self.w = None
self.lr = 10e-3
Весовые коэффициенты так же инициируются в функции partial_fit, как это делается в SGDRegressor библиотеки Sci-kit Learn:
def partial_fit(self, X, Y):
if self.w is None:
D = X.shape[1]
self.w = np.random.randn(D) / np.sqrt(D)
self.w += self.lr*(Y – X.dot(self.w)).dot(X)
def predict(self, X):
return X.dot(self.w)
# replace SKLearn Regressor
q_learning.SGDRegressor = SGDRegressor
# calculate everything up to max[Q(s,a)]
# Ex.
# R(t) + gamma*R(t+1) + … + (gamma^(n-1))*R(t+n-1) + (gamma^n)*max[Q(s(t+n), a(t+n))]
# def calculate_return_before_prediction(rewards, gamma):
# ret = 0
# for r in reversed(rewards[1:]):
# ret += r + gamma*ret
# ret += rewards[0]
# return ret
Далее у нас идёт функция play_one. Обратите внимание на то, что она сложнее, чем наши предыдущие функции play_one. Это связано с тем обстоятельством, что мы должны отслеживать n последних вознаграждений, состояний и действий. Вначале мы инициируем все обычные переменные, а также переменную multiplier, которая нужна для вычислений в методе N шагов. Мы знаем, что множители должны быть равны γ0, γ1, и так далее до γn-1. В связи с этим лучше их вычислить заранее:
# returns a list of states_and_rewards, and the total reward
def play_one(model, eps, gamma, n=5):
observation = env.reset()
done = False
totalreward = 0
rewards = []
states = []
actions = []
iters = 0
# array of [gamma^0, gamma^1, …, gamma^(n-1)]
multiplier = np.array([gamma]*n)**np.arange(n)
В цикле мы, как обычно, выбираем и выполняем действие, однако теперь мы также должны отслеживать состояния, действия и вознаграждения – когда придёт время делать обновление, мы должны быть уверены, что собрали как минимум n вознаграждений. После этого мы умножаем наши последние вознаграждения на вычисленные ранее множители и прибавляем их к оставшемуся прогнозу функции ценности:
# while not done and iters < 200:
while not done and iters < 10000:
# in earlier versions of gym, episode doesn’t automatically
# end when you hit 200 steps
action = model.sample_action(observation, eps)
states.append(observation)
actions.append(action)
prev_observation = observation
observation, reward, done, info = env.step(action)
rewards.append(reward)
# update the model
if len(rewards) >= n:
# return_up_to_prediction = calculate_return_before_prediction(rewards, gamma)
return_up_to_prediction = multiplier.dot(rewards[-n:])
G = return_up_to_prediction + (gamma**n)*np.max(model.predict(observation)[0])
model.update(states[-n], actions[-n], G)
# if len(rewards) > n:
# rewards.pop(0)
# states.pop(0)
# actions.pop(0)
# assert(len(rewards) <= n)
totalreward += reward
iters += 1
Выйдя из цикла, надо иметь в виду, что всё ещё остаются некоторые не обновлённые состояния, которые также необходимо обновить. Не забывайте, что в новейших версиях Gym эпизод заканчивается на 200-м шаге, независимо от того, достигли вы цели или нет; в более же старых версиях мы просто продолжаем процесс, пока не достигнем цели. В связи с этим тяжело узнать, достигли ли мы цели, пока не проверим документацию. В документации же говорится, что цели достигнута, когда позиция достигает 0,5, и именно это мы и проверяем. Если цель достигнута, то все последующие вознаграждения можно считать равными нулю, если же не достигнута, то мы должны предположить, что не достигнём её и в последующие n шагов, а потому устанавливаем все последующие вознаграждения равными -1. Именно поэтому соответствующая переменная называется guess_rewards («угадай_вознаграждение»).
# empty the cache
rewards = rewards[-n+1:]
states = states[-n+1:]
actions = actions[-n+1:]
# unfortunately, new version of gym cuts you off at 200 steps
# even if you haven’t reached the goal.
# it’s not good to do this UNLESS you’ve reached the goal.
# we are “really done” if position >= 0.5
if observation[0] >= 0.5:
# we actually made it to the goal
# print(“made it!”)
while len(rewards) > 0:
G = multiplier[:len(rewards)].dot(rewards)
model.update(states[0], actions[0], G)
rewards.pop(0)
states.pop(0)
actions.pop(0)
else:
# we did not make it to the goal
# print(“didn’t make it…”)
while len(rewards) > 0:
guess_rewards = rewards + [-1]*(n – len(rewards))
G = multiplier.dot(guess_rewards)
model.update(states[0], actions[0], G)
rewards.pop(0)
states.pop(0)
actions.pop(0)
return totalreward
Далее у нас идёт раздел main, с которым вы уже должны быть знакомы.
if __name__ == ‘__main__’:
env = gym.make(‘MountainCar-v0’)
ft = FeatureTransformer(env)
model = Model(env, ft, “constant”)
gamma = 0.99
if ‘monitor’ in sys.argv:
filename = os.path.basename(__file__).split(‘.’)[0]
monitor_dir = ‘./’ + filename + ‘_’ + str(datetime.now())
env = wrappers.Monitor(env, monitor_dir)
N = 300
totalrewards = np.empty(N)
costs = np.empty(N)
for n in range(N):
# eps = 1.0/(0.1*n+1)
eps = 0.1*(0.97**n)
totalreward = play_one(model, eps, gamma)
totalrewards[n] = totalreward
print(“episode:”, n, “total reward:”, totalreward)
print(“avg reward for last 100 episodes:”, totalrewards[-100:].mean())
print(“total steps:”, -totalrewards.sum())
plt.plot(totalrewards)
plt.title(“Rewards”)
plt.show()
plot_running_avg(totalrewards)
# plot the optimal state-value function
plot_cost_to_go(env, model)
Итак, запустим программу и посмотрим, что у нас получится.
TD-лямбда
Теперь обсудим TD(λ) как обобщение метода N шагов.
λ – это параметр, связанный с вектором, который называется следом соответствия и с которым мы познакомимся в этой лекции. Вы могли заметить, что код для метода N шагов был довольно сложным. В частности, было не так и просто всё время отслеживать последние конечные вознаграждения. λ позволяет нам использовать более элегантный метод выбора компромисса между TD(0) и методом Монте-Карло. В частности, нам не нужно будет отслеживать последние N шагов и мы будем способны делать обновления без ожидания окончания этих N шагов, прождав лишь 1 шаг, как в методе TD(0). Мы увидим, что λ = 1 соответствует методу Монте-Карло, λ = 0 – методу TD(0), а любое значение между этими величинами является компромиссом между этими методами.
Итак, вначале обобщим метод N шагов. Не забывайте, что мы можем определить различные G в зависимости от количества R, от которых он зависит:
Возникает странная идея – сформировать отдачу, которая являлась бы комбинацией этих G, к примеру,
Перенесём эту странность на следующий уровень. Предположим, мы можем суммировать любое количество G, даже бесконечное. Единственное требование – чтобы сумма весовых коэффициентов этих G была равна 1, так как конечное G должно быть сопоставимо с исходными значениями G:
Перенесём эту странность на следующий уровень. Предположим, мы можем суммировать любое количество G, даже бесконечное. Единственное требование – чтобы сумма весовых коэффициентов этих G была равна 1, так как конечное G должно быть сопоставимо с исходными значениями G:
В методе TD(λ) λ присваиваются очень специфические значения. В частности, оно уменьшается в геометрической прогрессии и, если вы заметили, в формуле сумма не сходится к единице, поскольку уже первый весовой коэффициент равен 1, а потому их нужно нормализовать. Конкретно говоря, нас интересует нормализация для случая, когда n равно бесконечности. Из курса математического анализа мы знаем, что данная сумма равна единице, делённой на единицу 1 – λ:
Следовательно, мы должны отмасштабировать сумму отдач на величину 1 – λ. Это называется λ-отдачей:
Следовательно, мы должны отмасштабировать сумму отдач на величину 1 – λ. Это называется λ-отдачей:
Можете поставить видео на паузу и выписать всё это на бумаге, чтобы самим удостовериться, что всё правильно.
Имея λ-отдачу, можно предположить, что наш эпизод в какой-то момент закончится. Обозначим этот момент времени через T. Поскольку считается, что n пробегает значения от 1 до бесконечности, когда n достигает значения T – t, отдача на n-м шаге на самом деле становится лишь полной отдачей выборки G(t), без верхнего индекса. Тогда мы можем преобразовать λ-отдачу, чтобы отделить отдачи на n-м шаге и отдачи полной выборки:
Второй член можно преобразовывать до тех пор, пока не останется лишь часть, зависящая от n внутри суммы:
Далее, если использовать некоторые тождества, относящиеся к рядам, то можно найти решение для второй суммы в аналитическом виде:
Таким образом, теперь у нас есть выражение для λ-отдач через отдачи n шагов, продолжающихся до конца эпизода, а затем полной отдачи. Поставьте видео на паузу, если хотите понять это доказательство. Я бы рекомендовал пройтись по нему с ручкой и бумагой.
Следует отметить, что если в этом уравнении λ = 0, то мы получим отдачу от одного шага, поскольку 00 = 1. Это и есть метод TD(0). Если же λ = 1, то первый член равен нулю, а мы получаем полную отдачу – что составляет метод Монте-Карло. Любое значение λ между этими двумя величинами даёт нам комбинацию всех отдач для n шагов, убывающих в геометрической прогрессии.
Тут возникает очевидный вопрос: а не хуже ли всё это как метода Монте-Карло, так и метода N шагов с точки зрения вычислительных усилий? В методе Монте-Карло нам нужно лишь вычислить отдачи для эпизода, в методе N шагов – вычислить отдачу N-го шага для каждого момента времени. Теперь же нам надо вычислить как отдачу по методу Монте-Карло, так и отдачи от N = 1 и до конца эпизода. Выглядит так, будто необходимо проделать намного больше работы, причём совершенно неясно, в чём тут выгода.
Следующий этап требует кое-какого математического «волшебства», которое определённо выходит за рамки данного курса, а потому никаких доказательств приводится не будет. Впрочем, этот метод известен уже некоторое время, так что у вас не должно возникнуть трудностей с поиском статей, в которых обсуждается данный алгоритм. Тот же алгоритм, который мы рассмотрим, в действительности является лишь приближением для использования истинной λ-отдачи, которую мы только что обсуждали. Конечно же, на самом деле нам не нужно использовать истинную λ-отдачу ни в какой практической ситуации, поскольку это означало бы вычисление отдач всех различных n шагов и полной отдачи.
Прежде всего давайте вспомним, как выглядят обновления наших параметров в методе TD(0). У нас есть целевая переменная, равная Rt+1 + γV(st+1), прогноз, равный V(st), и разница между ними δt = Rt+1 + γV(st+1) – V(st) (эта δ называется TD-ошибкой). Это помогает нам немного более строго всё записать, но это по-прежнему просто выполнение градиентного спуска:
Для реализации метода TD(λ) нам необходимо ввести идею следа соответствия. След соответствия – это вектор той же размерности, что и наш вектор параметров θ. По сути, он отслеживает наши старые градиенты, во многом подобно импульсу в глубоком обучении. Мы определяем первый след соответствия как равный нулю, а затем каждый последующий след будет равным текущему градиенту плюс часть старого следа соответствия, причём эта часть – лишь произведение γ и λ:
Для реализации метода TD(λ) нам необходимо ввести идею следа соответствия. След соответствия – это вектор той же размерности, что и наш вектор параметров θ. По сути, он отслеживает наши старые градиенты, во многом подобно импульсу в глубоком обучении. Мы определяем первый след соответствия как равный нулю, а затем каждый последующий след будет равным текущему градиенту плюс часть старого следа соответствия, причём эта часть – лишь произведение γ и λ:
По сути, λ просто показывает, какую часть прошлого мы принимаем во внимание.
Теперь мы можем переопределить этап обновления параметров, использовав след соответствия вместо простого градиента:
Напомню, что импульс в глубоком обучении работает очень схожим образом: мы сохраняем вектор скорости, являющийся суммой последнего градиента и части старой скорости, после чего обновляем θ для движения в этом направлении, подобно тому, как наше θ движется в направлении следа соответствия:
Напомню, что импульс в глубоком обучении работает очень схожим образом: мы сохраняем вектор скорости, являющийся суммой последнего градиента и части старой скорости, после чего обновляем θ для движения в этом направлении, подобно тому, как наше θ движется в направлении следа соответствия:
Обратите внимание на то, что, поскольку обновление θ теперь зависит только от следующего состояния, мы можем выполнять наши обновления уже на следующем шаге, а не ждать N этапов, как в методе N шагов. Однако не забывайте и о том, что это лишь приближение для использования истинной λ-отдачи.
Тут иногда отмечается ещё одно отличие. Поскольку метод N шагов и истинная λ-отдача требуют просмотра позднейших состояний, они называются прямым представлением, тогда как в методе TD(λ) мы обновляем наше текущее θ, основываясь на прошлых ошибках, и потому это называется обратным представлением.
TD-лямбда в коде
Давайте воплотим алгоритм метода TD(λ) в коде. Мы используем тот же подход, что и в программе для метода N шагов, когда мы импортировали большую часть кода из более ранней программы для Q-обучения. При просмотре кода следует отметить, насколько он проще метода N шагов, несмотря на то что его теоретические основы сложнее. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую сделать именно так, соответствующий файл в репозитарии называется td_lambda.py и находится в папке mountaincar.
Вначале у нас идут все обычные импорты.
#***
from __future__ import print_function, division
from builtins import range
# Note: you may need to update your version of future
# sudo pip install -U future
#
# Note: gym changed from version 0.7.3 to 0.8.0
# MountainCar episode length is capped at 200 in later versions.
# This means your agent can’t learn as much in the earlier episodes
# since they are no longer as long.
#
# Adapt Q-Learning script to use TD(lambda) method instead
import gym
import os
import sys
import numpy as np
import matplotlib.pyplot as plt
from gym import wrappers
from datetime import datetime
# code we already wrote
from q_learning import plot_cost_to_go, FeatureTransformer, plot_running_avg
После этого идёт определение класса BaseModel. Он подобен написанному нами ранее классу SGDRegressor, однако я не хочу его так называть, поскольку теперь мы используем следы соответствия.
class BaseModel:
def __init__(self, D):
self.w = np.random.randn(D) / np.sqrt(D)
Я также переименовал некоторые аргументы функции fit, чтобы вы могли видеть, что есть что.
def partial_fit(self, input_, target, eligibility, lr=10e-3):
self.w += lr*(target – input_.dot(self.w))*eligibility
Функция predict – та же, как обычно.
def predict(self, X):
X = np.array(X)
return X.dot(self.w)
Далее у нас идёт класс Model. Он будет немного сложнее, так как теперь мы должны отслеживать векторы соответствия. В конструкторе мы инициируем BaseModel для каждого из действий и вектор соответствия.
# Holds one BaseModel for each action
class Model:
def __init__(self, env, feature_transformer):
self.env = env
self.models = []
self.feature_transformer = feature_transformer
D = feature_transformer.dimensions
self.eligibilities = np.zeros((env.action_space.n, D))
for i in range(env.action_space.n):
model = BaseModel(D)
self.models.append(model)
Функция predict остаётся прежней.
def predict(self, s):
X = self.feature_transformer.transform([s])
assert(len(X.shape) == 2)
return np.array([m.predict(X)[0] for m in self.models])
Самые большие изменения – в функции update. Прежде всего не забывайте, что часть обновления вектора соответствия – это просто γ, умноженное на λ и умноженное на само себя, поэтому мы можем вычислить это первым делом. Следующее – добавить градиент, который, как мы знаем, является собственно вектором признаков:
def update(self, s, a, G, gamma, lambda_):
X = self.feature_transformer.transform([s])
assert(len(X.shape) == 2)
self.eligibilities *= gamma*lambda_
self.eligibilities[a] += X[0]
self.models[a].partial_fit(X[0], G, self.eligibilities[a])
Функция sample_action также остаётся прежней.
def sample_action(self, s, eps):
if np.random.random() < eps:
return self.env.action_space.sample()
else:
return np.argmax(self.predict(s))
Затем у нас идёт функция play_one. Не думаю, что тут что-то может удивить, – весь код мы видели в предыдущих программах. У нас лишь появляется, как и следовало ожидать, дополнительный аргумент λ, однако мы по-прежнему выполняем Q-обучение. Обратите внимание, насколько проще и короче стала функция по сравнению с методом N шагов: нам больше не нужно ни отслеживать все вознаграждения, ни создавать цикл, чтобы пройти по всем оставшимся состояниям после окончания эпизода:
# returns a list of states_and_rewards, and the total reward
def play_one(model, eps, gamma, lambda_):
observation = env.reset()
done = False
totalreward = 0
iters = 0
# while not done and iters < 200:
while not done and iters < 10000:
action = model.sample_action(observation, eps)
prev_observation = observation
observation, reward, done, info = env.step(action)
# update the model
G = reward + gamma*np.max(model.predict(observation)[0])
model.update(prev_observation, action, G, gamma, lambda_)
totalreward += reward
iters += 1
return totalreward
Далее у нас идёт раздел main, который остаётся в точности прежним.
if __name__ == ‘__main__’:
env = gym.make(‘MountainCar-v0’)
ft = FeatureTransformer(env)
model = Model(env, ft)
gamma = 0.99
lambda_ = 0.7
if ‘monitor’ in sys.argv:
filename = os.path.basename(__file__).split(‘.’)[0]
monitor_dir = ‘./’ + filename + ‘_’ + str(datetime.now())
env = wrappers.Monitor(env, monitor_dir)
N = 300
totalrewards = np.empty(N)
costs = np.empty(N)
for n in range(N):
# eps = 1.0/(0.1*n+1)
eps = 0.1*(0.97**n)
# eps = 0.5/np.sqrt(n+1)
totalreward = play_one(model, eps, gamma, lambda_)
totalrewards[n] = totalreward
print(“episode:”, n, “total reward:”, totalreward)
print(“avg reward for last 100 episodes:”, totalrewards[-100:].mean())
print(“total steps:”, -totalrewards.sum())
plt.plot(totalrewards)
plt.title(“Rewards”)
plt.show()
plot_running_avg(totalrewards)
# plot the optimal state-value function
plot_cost_to_go(env, model)
Итак, запустим программу и посмотрим, что у нас получится.
TD-лямбда. Итоги
В заключение подведём итог всему изученному в данной части.
В данной части вы изучили методы обучения с подкреплением, которые можно применять в любой ситуации, где возможно использование обычного Q-обучения или SARSA. Поэтому и сделанные нами примеры были весьма специфичными – заметьте, они более похожи на общие инструменты, которые можно проверить в различных ситуациях. Хоть это, возможно, и не очевидно, но с технической точки зрения мы получили и дополнительную практику в работе с сетями радиальных базисных функций, поскольку именно они лежали в основе расширения признаков, использованного в программах. Удобно, что от такого рода тонкостей можно было абстрагироваться и сосредоточиться только на новом материале.
Вначале мы рассмотрели метод N шагов как обобщение метода TD(0). TD(0) имеет одношаговую отдачу, так как использует вознаграждение от одного примера. Но мы видели, что можем использовать любое количество вознаграждений в наших вычислениях отдачи. В частности, использование N вознаграждений даёт нам N-шаговую отдачу. Если же мы возьмём N до конца эпизода, то у нас получится метод Монте-Карло.
Далее мы увидели, что можем объединить все N-шаговые отдачи до бесконечности, что даёт нам λ-отдачу. В этой ситуации мы взвешиваем каждую N-шаговую отдачу на λ, убывающую в геометрической прогрессии. Мы видели, преобразуя наше выражение для λ-отдачи, что λ = 0 соответствует методу TD(0), а λ = 1, что ещё называется методом TD(1), – методу Монте-Карло.
Затем мы рассмотрели оперативный алгоритм с использованием следов соответствия, который приближённо выражает оперативное значение TD(λ). Интересно и обнадёживающе, что алгоритм TD(λ) во многом схож на обновление импульса из глубокого обучения.
Воспринимайте их как новые инструменты в своём инструментарии, как и все остальные алгоритмы, которые вы изучите в этом курсе. Нет никакой гарантии, что какой-либо конкретный алгоритм будет работать для вашей задачи, однако чем больше у вас имеется инструментов, тем больше вариантов вы можете перепробовать и тем более вероятно, что решение будет найдено.
