All posts by neil

About neil

data scientist in using deep learning for Natural Language Processing and Social Network Analysis.

Setup Amazon AWS GPU instance with MXnet

Number 2147483647

Niba Meisje met de parel

(every blog should have a cat, right? This cat is “Niba”, and she is Pogo’s younger sister. The neural art style is “Girl with a Pearl Earring“. More about Neural Art with MXnet, please refer to my last blog.)

With popular requests, I wrote this blog for starting an Amazon AWS GPU instance and install MXnet for kaggle competitions, like Second Annual Data Science Bowl. Installing CUDA on AWS is kind of tricky: one needs to update kernels and solve some conflicts. I want to have special thanks to Caffe EC2 installation guide,-CUDA-7,-cuDNN)

Have you clicked “star” on MXnet’s github repo? If not yet, do it now:

Create AWS GPU instance

For creating an AWS instance, please follow AWS spot instance can be an inexpensive solution for competing on Kaggle, and one can request a g2.2xlarge (single GPU) or a g2.8xlarge (4x GPUs)…

View original post 443 more words

Learning values across many orders of magnitude

Hado van Hasselt

Our paper about adaptive target normalization in deep learning was accepted at NIPS 2016. A preprint can be found on  The abstract and a more informal summary can be found below.

Update: There are now videos of the effect of the new approach on Atari.


Most learning algorithms are not invariant to the scale of the function that is being approximated. We propose to adaptively normalize the targets used in learning. This is useful in value-based reinforcement learning, where the magnitude of appropriate value approximations can change over time when we update the policy of behavior. Our main motivation is prior work on learning to play Atari games, where the rewards were all clipped to a predetermined range. This clipping facilitates learning across many different games with a single learning algorithm, but a clipped reward function can result in qualitatively different behavior. Using the adaptive normalization we…

View original post 458 more words

NIPS 2015 Part 3


Day 3 and 4 of NIPS main meeting (part 1, part 2). More amazing deep learning results.

Embed to control: a locally linear latent dynamics model for control from raw images
Manuel Watter, Jost Springenberg, Joschka Boedecker, Martin Riedmiller

E2CTo implement optimal control in the latent state space, they used iterative Linear-Quadratic-Gaussian control applied directly to video. A gaussian latent state space was decoded from images through a deep variational latent variable model. One step prediction of latent dynamics was modeled to be locally linear where the dynamics matrices were parameterized by a neural network that depends on the current state. A variant of a variational cost that minimizes instantaneous reconstruction, and also KL divergence between predicted latent and the reconstructed latent. Deconvolution network was used, and as can be seen in the [video online], the generated images are a bit blurry, but iLQG control works well.

Deep visual…

View original post 859 more words

REINFORCE algorithm


本节,我们将学习一下经典 REINFORCE 算法的实现,这样被称为“基本”策略梯度方法。我们会从一个应用在固定策略和环境开始。下一节会实现进阶版本,使用框架提供的功能来让整个项目更加结构化并对命令行友好。


首先,我们简要回顾一下算法和一些基本符号。我们采用定义为 (\mathcal{S},\mathcal{A},P,r,\mu_0,\gamma,T),其中\mathcal{S}是状态集合,\mathcal{A} 是行动集合,P:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\rightarrow [0,1] 是转移概率,P:\mathcal{S}\times \mathcal{A} \rightarrow \mathbb{R} 是奖励函数,\gamma \in [0,1] 是折扣因子,而 T\in \mathbb{N} 是片段长度。REINFORCE 算法直接优化参数化的随机策略 \pi_\theta: \mathcal{S}\times\mathcal{A}\rightarrow [0,1],通过执行在期望奖励目标函数的梯度上升:

\eta(\theta) = \mathbb{E}\Bigg[\sum\limits_{t=0}^{T} \gamma^t r(s_t, a_t)\Bigg]

其中期望是隐式地覆盖所有可能的轨迹,按照采样过程 s_0\sim \mu_0, a_t\sim \pi_\theta(\dot|s_t),而 s_{t+1}\sim P(\dot|s_t, a_t)。通过似然比例技巧,目标函数关于 \theta 的梯度如下式给出:

\nabla_\theta \eta(\theta) = \mathbb{E}\Bigg[(\sum\limits_{t=0}^{T} \gamma^t r(s_t, a_t))(\sum\limits_{t=0}^{T}\nabla_\theta \log \pi_\theta (a_t|s_t))\Bigg]

注意到对 t'<t

\mathbb{E} [r(s_{t'},a_{t'}) \nabla_\theta \log\pi_\theta (a_t|s_t)] = 0



\nabla_\theta\eta(\theta) = \mathbb{E}\Bigg[\sum\limits_{t=0}^{T}\nabla_\theta\log \pi_\theta(a_t|s_t)\sum\limits_{t'=t}^{T}\gamma^{t'}r(s_{t'},a_{t'})\Bigg]


\nabla_\theta\eta(\theta) = \mathbb{E}\Bigg[\sum\limits_{t=0}^{T}\nabla_\theta\log \pi_\theta(a_t|s_t)\sum\limits_{t'=t}^{T}\gamma^{t'-t}r(s_{t'},a_{t'})\Bigg]

其中,\gamma^{t'} 由 \gamma^{t'-t} 代替。我们将折扣因子看成是对无折扣目标函数的方差降低因子时,会得到更小偏差的梯度估计,会带来一定的方差增大。我们定义 R_t := \sum\limits_{t'=t}^{T} \gamma^{t'-t} r(s_{t'},a_{t'}) 为经验折扣奖励。


  • 初始化参数为 \theta_1 的策略 \pi.
  • 对迭代 k = 1,2,\dots:
    • 根据当前策略 \theta_k 采样 N 个轨迹 \tau_1,\dots,\tau_n,其中 \tau_i = (s_t^i, a_t^i, R_t^i)_{t=0}^{T-1}.注意到因为在观察到最后的状态时无行动了已经,所以最后的状态丢弃。
    • 计算经验策略梯度:\widehat{\nabla_\theta\eta(\theta)} = \frac{1}{NT}\sum\limits_{i=1}^{N}\sum\limits_{t=0}^{T-1} \nabla_\theta\log \pi_\theta(a_t^i|s_t^i)R_t^i
    • 进行一步梯度计算:\theta_{k+1} = \theta_k + \alpha\widehat{\nabla_\theta\eta(\theta)}


作为开始,我们试着使用神经网络策略来解决 cartpole 平衡问题. 后面我们会推广算法来接受配置参数. 现在先看看最简单形式.

from __future__ import print_function
from rllab.envs.box2d.cartpole_env import CartpoleEnv
from rllab.policies.gaussian_mlp_policy import GaussianMLPPolicy
from rllab.envs.normalized_env import normalize
import numpy as np
import theano
import theano.tensor as TT
from lasagne.updates import adam

# normalize() makes sure that the actions for the environment lies
# within the range [-1, 1] (only works for environments with continuous actions)
env = normalize(CartpoleEnv())
# Initialize a neural network policy with a single hidden layer of 8 hidden units
policy = GaussianMLPPolicy(env.spec, hidden_sizes=(8,))

# We will collect 100 trajectories per iteration
N = 100
# Each trajectory will have at most 100 time steps
T = 100
# Number of iterations
n_itr = 100
# Set the discount factor for the problem
discount = 0.99
# Learning rate for the gradient update
learning_rate = 0.01



paths = []

for _ in xrange(N):
observations = []
actions = []
rewards = []

observation = env.reset()

for _ in xrange(T):
# policy.get_action() returns a pair of values. The second one returns a dictionary, whose values contains
# sufficient statistics for the action distribution. It should at least contain entries that would be
# returned by calling policy.dist_info(), which is the non-symbolic analog of policy.dist_info_sym().
# Storing these statistics is useful, e.g., when forming importance sampling ratios. In our case it is
# not needed.
action, _ = policy.get_action(observation)
# Recall that the last entry of the tuple stores diagnostic information about the environment. In our
# case it is not needed.
next_observation, reward, terminal, _ = env.step(action)
observation = next_observation
if terminal:
# Finish rollout if terminal state reached

# We need to compute the empirical return for each time step along the
# trajectory
returns = []
return_so_far = 0
for t in xrange(len(rewards) - 1, -1, -1):
return_so_far = rewards[t] + discount * return_so_far
# The returns are stored backwards in time, so we need to revert it
returns = returns[::-1]



observations = np.concatenate([p["observations"] for p in paths])
actions = np.concatenate([p["actions"] for p in paths])
returns = np.concatenate([p["returns"] for p in paths])


我们使用 Theano 来实现,假设读者已经对其有了了解。如果没有,请参考some tutorials.


# Create a Theano variable for storing the observations
# We could have simply written `observations_var = TT.matrix('observations')` instead for this example. However,
# doing it in a slightly more abstract way allows us to delegate to the environment for handling the correct data
# type for the variable. For instance, for an environment with discrete observations, we might want to use integer
# types if the observations are represented as one-hot vectors.
observations_var = env.observation_space.new_tensor_variable(
# It should have 1 extra dimension since we want to represent a list of observations
actions_var = env.action_space.new_tensor_variable(
returns_var = TT.vector('returns')


\widehat{\nabla_\theta\eta(\theta)} = \nabla_\theta\Bigg(\frac{1}{NT}\sum\limits_{i=1}^{N}\sum\limits_{t=0}^{T-1}\log\pi_\theta(a_t^i|s_t^i)R_t^i \Bigg) = \nabla_\theta L(\theta)

其中 L(\theta) = \frac{1}{NT} \sum\limits_{i=1}^{N}\sum\limits_{t=0}^{T-1} \log \pi_\theta(a_t^i|s_t^i)R_t^i 被称为 surrogate 函数. 因此,我们可以首先构造 L(\theta) 的计算图,然后用其梯度获得经验策略梯度.

# policy.dist_info_sym returns a dictionary, whose values are symbolic expressions for quantities related to the
# distribution of the actions. For a Gaussian policy, it contains the mean and (log) standard deviation.
dist_info_vars = policy.dist_info_sym(observations_var, actions_var)

# policy.distribution returns a distribution object under rllab.distributions. It contains many utilities for computing
# distribution-related quantities, given the computed dist_info_vars. Below we use dist.log_likelihood_sym to compute
# the symbolic log-likelihood. For this example, the corresponding distribution is an instance of the class
# rllab.distributions.DiagonalGaussian
dist = policy.distribution

# Note that we negate the objective, since most optimizers assume a
# minimization problem
surr = - TT.mean(dist.log_likelihood_sym(actions_var, dist_info_vars) * returns_var)

# Get the list of trainable parameters.
params = policy.get_params(trainable=True)
grads = theano.grad(surr, params)


我们基本上完成了!现在,你可以使用自己喜欢的随机优化算法来执行参数的更新。我们使用 ADAM:

f_train = theano.function(
inputs=[observations_var, actions_var, returns_var],
updates=adam(grads, params, learning_rate=learning_rate),
f_train(observations, actions, returns)


print('Average Return:', np.mean([sum(path["rewards"]) for path in paths]))

完整的代码参考 examples/


\widehat{\nabla_\theta\eta(\theta)} = \frac{1}{NT}\sum\limits_{i=1}^{N}\sum\limits_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(a_t^i|s_t^i)(R_t^i-b(s_t^i))

由于 \mathbb{E}[\nabla_\theta\log\pi_\theta(a_t^i|s_t^i)b(s_t^i)]=0 我们才能得到这个结果.

基准函数一般实现为 V^\pi(s) 的估计。这里,R_T^i - b(s_t^i)A^\pi(s_t^i, a_t^i) 的估计. 该框架实现了一些类基准函数的不同选择。通过使用状态特征的线性基准函数在性能和准确度方面进行了较好的平衡,可在 rllab/baselines/ 中查看. 使用这个实现的相关的代码如下:

# ... initialization code ...
from rllab.baselines.linear_feature_baseline import LinearFeatureBaseline
baseline = LinearFeatureBaseline(env.spec)
# ... inside the loop for each episode, after the samples are collected
path = dict(observations=np.array(observations),actions=np.array(actions),rewards=np.array(rewards),)
path_baseline = baseline.predict(path)
advantages = []
returns = []
return_so_far = 0
for t in xrange(len(rewards) - 1, -1, -1):
return_so_far = rewards[t] + discount * return_so_far
advantage = return_so_far - path_baseline[t]
# The advantages are stored backwards in time, so we need to revert it
advantages = np.array(advantages[::-1])
# And we need to do the same thing for the list of returns
returns = np.array(returns[::-1])


现在我们的学习率常会受到奖励的值范围的影响. 我们可以通过在计算梯度前进行白噪化 advantage 来降低这个依赖。用代码就是:

advantages = (advantages - np.mean(advantages)) / (np.std(advantages) + 1e-8)



在计算基准函数之后执行本步骤的原因是在极端情形下,如果我们从每个状态仅仅有一个轨迹,并且基准函数能够完美地拟合数据,那么所有的advantages会变成 0,这样就没有梯度信号了。

现在,我们可以更快地训练策略(我们需要改变学习率因为重新规范化了). 完整的代码在examples/ 可得.




from rllab.algos.trpo import TRPO
from rllab.baselines.linear_feature_baseline import LinearFeatureBaseline
from rllab.envs.box2d.cartpole_env import CartpoleEnv
from rllab.envs.normalized_env import normalize
from rllab.policies.gaussian_mlp_policy import GaussianMLPPolicy

env = normalize(CartpoleEnv())

policy = GaussianMLPPolicy(
# The neural network policy should have two hidden layers, each with 32 hidden units.
hidden_sizes=(32, 32)

baseline = LinearFeatureBaseline(env_spec=env.spec)

algo = TRPO(

执行第一次需要初始化 Theano 并且编译计算图,可能需要登上几分钟。后续执行会非常快,因为编译已经被缓存了。你可以看到下面的后续信息:

using seed 1
instantiating rllab.envs.box2d.cartpole_env.CartpoleEnv
instantiating rllab.policy.mean_std_nn_policy.MeanStdNNPolicy
using argument hidden_sizes with value [32, 32]
instantiating rllab.baseline.linear_feature_baseline.LinearFeatureBaseline
instantiating rllab.algo.trpo.TRPO
using argument batch_size with value 4000
using argument whole_paths with value True
using argument n_itr with value 40
using argument step_size with value 0.01
using argument discount with value 0.99
using argument max_path_length with value 100
using seed 0
0% 100%
[##############################] | ETA: 00:00:00
Total time elapsed: 00:00:02
2016-02-14 14:30:56.631891 PST | [trpo_cartpole] itr #0 | fitting baseline...
2016-02-14 14:30:56.677086 PST | [trpo_cartpole] itr #0 | fitted
2016-02-14 14:30:56.682712 PST | [trpo_cartpole] itr #0 | optimizing policy
2016-02-14 14:30:56.686587 PST | [trpo_cartpole] itr #0 | computing loss before
2016-02-14 14:30:56.698566 PST | [trpo_cartpole] itr #0 | performing update
2016-02-14 14:30:56.698676 PST | [trpo_cartpole] itr #0 | computing descent direction
2016-02-14 14:31:26.241657 PST | [trpo_cartpole] itr #0 | descent direction computed
2016-02-14 14:31:26.241828 PST | [trpo_cartpole] itr #0 | performing backtracking
2016-02-14 14:31:29.906126 PST | [trpo_cartpole] itr #0 | backtracking finished
2016-02-14 14:31:29.906335 PST | [trpo_cartpole] itr #0 | computing loss after
2016-02-14 14:31:29.912287 PST | [trpo_cartpole] itr #0 | optimization finished
2016-02-14 14:31:29.912483 PST | [trpo_cartpole] itr #0 | saving snapshot...
2016-02-14 14:31:29.914311 PST | [trpo_cartpole] itr #0 | saved
2016-02-14 14:31:29.915302 PST | ----------------------- -------------
2016-02-14 14:31:29.915365 PST | Iteration 0
2016-02-14 14:31:29.915410 PST | Entropy 1.41894
2016-02-14 14:31:29.915452 PST | Perplexity 4.13273
2016-02-14 14:31:29.915492 PST | AverageReturn 68.3242
2016-02-14 14:31:29.915533 PST | StdReturn 42.6061
2016-02-14 14:31:29.915573 PST | MaxReturn 369.864
2016-02-14 14:31:29.915612 PST | MinReturn 19.9874
2016-02-14 14:31:29.915651 PST | AverageDiscountedReturn 65.5314
2016-02-14 14:31:29.915691 PST | NumTrajs 1278
2016-02-14 14:31:29.915730 PST | ExplainedVariance 0
2016-02-14 14:31:29.915768 PST | AveragePolicyStd 1
2016-02-14 14:31:29.921911 PST | BacktrackItr 2
2016-02-14 14:31:29.922008 PST | MeanKL 0.00305741
2016-02-14 14:31:29.922054 PST | MaxKL 0.0360272
2016-02-14 14:31:29.922096 PST | LossBefore -0.0292939
2016-02-14 14:31:29.922146 PST | LossAfter -0.0510883
2016-02-14 14:31:29.922186 PST | ----------------------- -------------


rllab 同样提供一种“桩”模式来执行实验,这样能够支持更多的配置,例如记录日志和并行化。简单的脚本可在 examples/ 中看到。内容如下:

from rllab.algos.trpo import TRPO
from rllab.baselines.linear_feature_baseline import LinearFeatureBaseline
from rllab.envs.box2d.cartpole_env import CartpoleEnv
from rllab.envs.normalized_env import normalize
from rllab.misc.instrument import stub, run_experiment_lite
from rllab.policies.gaussian_mlp_policy import GaussianMLPPolicy


env = normalize(CartpoleEnv())

policy = GaussianMLPPolicy(
# The neural network policy should have two hidden layers, each with 32 hidden units.
hidden_sizes=(32, 32)

baseline = LinearFeatureBaseline(env_spec=env.spec)

algo = TRPO(

# Number of parallel workers for sampling
# Only keep the snapshot parameters for the last iteration
# Specifies the seed for the experiment. If this is not provided, a random seed
# will be used
# plot=True,

第一个需要注意的差异是代码的所有 import 语句后的这一行:stub(globals()),这个可以将所有已经导入的类的构造器用桩式方法替代。在这个调用后,类构造器如 TRPO() 将会返回一个序列化的桩对象,所有方法 invocation 和 属性获取方法同样会变成序列化的桩式调用和桩式属性。接着,run_experiment_lite 调用序列化最终的桩式方法调用,并启动一个脚本实际运行试验。

按照这样的方式启动试验的好处是,我们将试验参数的配置和试验的实际执行分割开来。run_experiment_lite 支持多种执行方式,本地式,在一个 docker 容器本地式,或者在 ec2 远程。按照这样的抽象,不同超参数的多个试验可以被快速构造并在多个 ec2 的机器上同时执行。
另一个微妙的地方是我们使用 Theano 来实现算法,这对混合 GPU 及 CPU 使用支持较弱。当主进程对批量优化使用 GPU 而多个 worker 进行想要使用 GPU 产生轨迹 rollout 的时候非常麻烦。所以分割实验让 worker 进程可以合适地进行 CPU 下的 Theano 的初始化。

run_experiment_lite 的另外参数:
* exp_name:如果该参数设置了,实验数据会被存放在 data/local/{exp_name} 中。默认来说,该文件夹名被设置为 experiment_{timestamp}
* exp_prefix:如果该参数设置了,并且 exp_name 没有指定,实验文件夹名将会被设置为 {exp_prefix}_{timestamp}



每个环境必须实现定义在文件 rllab/envs/ 中的方法、属性:

class Env(object):
def step(self, action):
Run one timestep of the environment's dynamics. When end of episode
is reached, reset() should be called to reset the environment's internal state. 执行环境转移动态的一个时间步,当回合的结尾到达,reset() 必须调用重置环境内部状态
action : an action provided by the environment
(observation, reward, done, info)
observation : agent's observation of the current environment
reward [Float] : amount of reward due to the previous action
done : a boolean, indicating whether the episode has ended
info : a dictionary containing other diagnostic information from the previous action
raise NotImplementedError

def reset(self):
Resets the state of the environment, returning an initial observation. 重置环境状态,返回初始观察状态
observation : the initial observation of the space. (Initial reward is assumed to be 0.) 初始状态,初始回报为 0
raise NotImplementedError

def action_space(self):
Returns a Space object 返回一个行动空间对象
raise NotImplementedError

def observation_space(self):
Returns a Space object 返回一个状态空间对象
raise NotImplementedError

我们会实现一个简单的 2D 状态和 2D 行动的环境。其目标是控制点机器人在 2D 中移动到源点。我们接受在 2D 平面 (x,y)∈ℝ<sup>2</sup> 点机器人的位置。行动是他的速度 (x˙,y˙)∈ℝ<sup>2</sup>,满足 |x˙|≤0.1 和 |y˙|≤0.1。我们通过定义奖励为负的到原点的距离鼓来励机器人往源点移动。r(x,y)=−sqrt(x<sup>2</sup>+y<sup>2</sup>)。

我们现在来创建环境的文件,假设被放在 example/ 中。首先,声明一个继承自基环境的类,加入一些 import 内容:

from rllab.envs.base import Env
from rllab.envs.base import Step
from rllab.spaces import Box
import numpy as np
class PointEnv(Env):

# ...


class PointEnv(Env):

# ...

def observation_space(self):
return Box(low=-np.inf, high=np.inf, shape=(2,))

def action_space(self):
return Box(low=-0.1, high=0.1, shape=(2,))


python scripts/ examples.point_env --mode random



from rllab.algos.trpo import TRPO
from rllab.baselines.linear_feature_baseline import LinearFeatureBaseline
from examples.point_env import PointEnv
from rllab.envs.normalized_env import normalize
from rllab.policies.gaussian_mlp_policy import GaussianMLPPolicy

env = normalize(PointEnv())
policy = GaussianMLPPolicy(
baseline = LinearFeatureBaseline(env_spec=env.spec)
algo = TRPO(

假设这个文件是 examples/。你可以运行下面的脚本:

python examples/

Reinforcement learning by David Silver in RLDM 2015



Bellman 方程

  • Bellman 期望方程将值函数 Q^{\pi} 展开:

Q^\pi(s,a) = \mathbb{E}~[r_{t+1} + \gamma r_{t+1} + \gamma^2r_{t+1} + \dots | s,a] =\mathbb{E}_{s',a'}[r + \gamma Q^\pi(s',a') | s, a]

  • Bellman 最优方程将最优值函数 Q^* 展开:

Q^*(s,a) = \mathbb{E}_{s'} [r + \gamma \max_{a'} Q^*(s',a') | s, a]

  • 策略迭代算法求解了 Bellman 期望方程

Q_{i+1}(s,a) = \mathbb{E}_{s'} [r + \gamma Q_i(s', a') | s,a]

  • 值迭代算法求解了 Bellman 最优方程

Q_{i+1} (s, a) = \mathbb{E}_{s',a'} [r + \gamma \max_{a'} Q_i(s',a')|s,a]

非线性 Sarsa 策略迭代

  • 使用参数为 w 的 Q-network 来表示值函数

Q(s, a, w) \approx Q^\pi(s,a)

  • 通过 Q-值的均方误差来定义目标函数

\mathcal{L}(w) = \mathbb{E} [(r + \gamma Q(s',a',w) - Q(s,a,w))^2]

  • 我们就有了下面的 Sarsa 梯度

\frac{\partial \mathcal{L}(w)}{\partial w} = \mathbb{E}[(r + \gamma Q(s',a',w) - Q(s,a,w)) \frac{\partial Q(s,a,w)}{\partial w}]

  • 借助 SGD 使用 \frac{\partial \mathcal{L}(w)}{\partial w} 端对端优化目标函数


基本的 Q-学习采用神经网络会出现振荡或者发散的情况

  1. 数据是序列化的
    1. 相邻的样本是相关的,非独立同分布的
  2. Q-值微小变化会导致策略迅速变化
    1. 策略可能会振荡
    2. 数据的分布会从一个极端摇摆到另一个极端
  3. 奖励和 Q-值的范围未知
    1. 基本的 Q-学习梯度会在反响传播时变得很大从而不能稳定

深度 Q-网络(DQN)

DQN 为深度基于值的强化学习问题提供了一种稳定解决方案

  1. 使用经验回放
    1. 将数据之间的关联打破,重回独立同分布的设定下
    2. 从过去的策略中学习
    3. 使用 免策略 Q-学习
  2. 冻结 目标 Q-网络
    1. 避免振荡
    2. 将 Q-网络和目标网络之间的关联打破
  3. 截断奖励或者正规化网络,适应到合适的范围内
    1. 可以得到健壮的梯度


为了打破关联,我们从 agent 自己的经验中构建数据集

  1. 根据 \epsilon-贪婪策略采取行动 a_t
  2. 将转换 (s_t, a_t, r_{t+1}, s_{t+1}) 存放在记忆 \mathcal{D}
  3. \mathcal{D} 中随机采样一个小批量样本 (s,a,r,a')
  4. 优化 Q-网络和 Q-学习目标之间的均方误差 MSE,如

\mathcal{L}(w) = \mathbb{E}_{s,a,r,s' \sim \mathcal{D}} [(r + \gamma \max_{a'}Q(s',a',w) - Q(s,a,w))^2]

稳定的深度强化学习(2):固定目标 Q-网络

为了避免振荡,固定在 Q-学习目标网络的参数

  • 根据旧的,固定的参数 w^- 计算 Q-学习目标函数

r + \gamma \max_{a'} Q(s',a',w^-)

  • 优化 Q-网络和 Q-学习目标之间的均方误差 MSE

\mathcal{L}(w) = \mathbb{E}_{s,a,r,s'\sim \mathcal{D}} [(r + \gamma \max_{a'}Q(s',a',w^-)-Q(s,a,w))^2]

  • 周期化地更新固定参数 w^- \leftarrow w


  • DQN 截断奖励在 [-1,+1] 之间
  • 让 Q-值不会过大
  • 确保梯度完好(well-conditioned)
  • 不能够区分奖励的大小
  • 更好的方式:正规化网络输出
  • 比如,通过 batch 正规化


  • 使用一个权重为 u 的深度神经网络 a = \pi(s,u) 来表示策略
  • 定义目标函数为总折扣奖励

J(u) = \mathbb{E} [r_1 + \gamma r_2 + \gamma^2 r_3 + \dots]

  • 使用 SGD 来端对端优化目标函数
  • 即,调整策略参数 u 来达到更大的奖励



\frac{\partial J(u)}{\partial u} = \mathbb{E}_s [\frac{\partial Q^\pi(s,a)}{\partial u}] = \mathbb{E}_s [\frac{\partial Q^\pi(s,a)}{\partial a} \frac{\partial \pi(s,u)}{\partial u}]

策略梯度是最大化提升 Q 的方向

确定型 Actor-Critic


  • Actor 是参数为 u 的策略 \pi(s, u)

s \xrightarrow[u_1]{}\dots\xrightarrow[u_n]{} a

  • Critic 是参数为 w 的值函数 Q(s, a, w)

s,a \xrightarrow[w_1]{}\dots\xrightarrow[w_n]{} Q

  • Critic 为 Actor 提供损失函数

s \xrightarrow[u_1]{}\dots\xrightarrow[u_n]{} a\xrightarrow[w_1]{}\dots\xrightarrow[w_n]{} Q

  • 梯度从 Critic 到 Actor 反向传播

\frac{\partial a}{\partial u} \xleftarrow[]{}\dots\xleftarrow[]{} \frac{\partial Q}{\partial a} \xleftarrow[]{} \dots\xleftarrow[]{}

确定型 Actor-Critic:学习规则

  • Critic 通过 Q-学习估计当前策略的值

\frac{\partial \mathcal{L}(w)}{\partial w} = \mathbb{E} [(r + \gamma Q(s',\pi(s'),w)-Q(s,a,w)) \frac{\partial Q(s,a,w)}{\partial w}]

  • Actor 按照提升 Q 的方向更新策略

\frac{\partial J(u)}{\partial u} = \mathbb{E}_s [\frac{\partial Q(s,a,w)}{\partial a} \frac{\partial \pi(s,u)}{\partial u}]


  • 基本的 actor-critic 使用神经网络会振荡或者发散
  • DDPG 给出了稳定解
  1. 对 actor 和 critic 均使用经验回放
  2. 冻结目标网络来避免振荡

\frac{\partial \mathcal{L}(w)}{\partial w} = \mathbb{E}_{s,a,r,s'\sim \mathcal{D}} [(r + \gamma Q(s',\pi(s',u^-),w^-)-Q(s,a,w)) \frac{\partial Q(s,a,w)}{\partial w}]

\frac{\partial J(u)}{\partial u} = \mathbb{E}_{s,a,r,s'\sim \mathcal{D}}[\frac{\partial Q(s,a,w)}{\partial a} \frac{\partial \pi(s,u)}{\partial u}]

用于连续行动控制的 DDPG

  • 从原始像素 s 端对端学习控制策略
  • 输入状态 s 是前 4 帧的图像的原始像素的栈
  • Q\pi 两个不同的卷积网络
  • 在 MuJoCo 中进行模拟




  • 使用转移模型来查找最优行动


  • 使用深度神经网络来表示转移模型 p(r,s'|s,a)
  • 定义目标函数来评价模型的好坏
  • 如,重新创建下一状态的比特数(Gregor et al.)
  • 通过 SGD 来优化目标函数



  • 转换模型的误差会整个轨迹上复合
  • 长轨迹的结尾,奖励就完全错了
  • 基于模型的强化学习在 Atari 游戏上无效(到目前为止)


  • 网络的每层执行任意的计算步骤
  • n-层网络可以向前看 n 步
  • 转换模型是否需要?


Monte-Carlo 搜索

  • MCTS 模拟未来轨迹
  • 构建巨大的拥有百万位置的向前搜索树
  • 目前最佳 19X19 程序使用的是 MCTS
  • 例如,第一个强大的围棋程序 MoGo (Gelly et al.)


  • 12 层的卷积网络可以训练来预测专家走法
  • 简单的卷积网络(只看一个位置,没有搜索)
  • 等价于有 10^5 位置的搜索树的 MoGo (Maddison et al.)


  • 强化学习为人工智能提供了一个通用途径的框架
  • 强化学习问题可以用端对端深度学习解决
  • 单个 agent 现在可以解决很多挑战性问题
  • 强化学习 + 深度学习 = 人工智能


“The only stupid question is the one you never asked.” – Richard Sutton


Deep Reinforcement Learning from OpenAI

强化学习研究决策制定和控制,以及一个进行决策的 agent 如何学会在一个未知环境中采取最优行动。深度强化学习研究如何在强化学习算法中使用神经网络,使得无需进行人工特征工程直接学习从原始感知数据到原始行动输出的映射变得可能。



已有的强化学习(RL)课本没有给出足够的关于如何使用函数近似的指导;基本上都是聚焦在离散状态空间的领域。而且,现有 RL 课本并没有对无导数优化和策略梯度方法给出充分讲述,而这些技术在很多的任务上都是相当重要的。






  • 如何训练神经网络进行回归和分类
  • 熟悉基本的 MDP、值迭代和策略迭代


  1. 预备知识,符号和术语
  2. 黑盒优化和交叉熵方法
    1. 练习
    2. 笔记
  3. 策略梯度
    1. 直觉解释
    2. 更加形式化的解释
    3. 实现注意点
    4. 参数化策略
    5. 练习
  4. 自然策略梯度(Natural Policy Gradient)和信赖区间方法(Trust Region Methods)
  5. Q-学习(Q-learning)
    1. 练习
  6. 参考文献

1 预备知识、符号和术语

强化学习包含一个 agent 和一个环境:每个时间步,agent 会选择一个行动,然后环境会返回给 agent 一个收益然后转换到下一个状态。在标准设置中,agent 和环境的交互被划分成一系列 回合(episode) 的序列。在每个回合,初始状态 s_0 从分布 \mu(s_o) 中采样出来。每个时间步,agent 随机或者确定地选择出一个行动;我们记此作 a_t \sim \pi(a_t|s_t) 表示行动是根据概率分布 \pi 采样出来的。下一个状态和收益根据转换概率分布 R(s_{t+1}, r_t | s_t, a_t)。这个过程持续进行直到 终止 状态达到,此时该回合结束。其过程可以写成下面的形式:

s_0 \sim \mu(s_0)

a_0 \sim \pi(a_0|s_0)

s_1, r_0 \sim P(s_1, r_0 | s_0, a_0)

a_1 \sim \pi(a_1 | s_1)

s_2, r_1 \sim P(s_2, r_1 | s_1, a_1)

a_{T-1}, r_{T-1}\sim \pi(a_{T-1} | s_{T-1})

s_T, r_{T-1} \sim P(s_T|s_{T-1},a_{T-1}) (s_T 是一个终止状态)

上面的定义是在 -可观察设定下的,这种情形下的 agent 能够获得系统的全部状态。在 部分-可观察设定下,agent 只能在每个时间步获得一个观察(y),这个观察可能是一个状态的噪声和不完全的信息。agent 可以将许多前期时间步信息进行组合,所以行动 a_t 依赖于前期历史 (y_0, a_0,y_1, a_1,\dots,y_{t-1}, a_{t-1},y_t);我们将历史记作 h_t

s_0, y_0 \sim \mu(s_0) (初始状态和观察)

a_0 \sim \pi(a_0|h_0)

s_1, y_1, r_0 \sim P(s_1, y_1, r_0 | s_0, a_0)

a_1 \sim \pi(a_1 | h_1)

s_2, y_2, r_1 \sim P(s_2, y_2, r_1 | s_1, a_1)

a_{T-1} \sim \pi(a_{T-1} | h_{T-1})

s_T, y_T, r_{T-1} \sim P(s_T, y_T, r_{T-1}|s_{T-1},a_{T-1}) (s_T 是一个终止状态)

如果我们称历史 h_t 为系统的状态,那么这个部分-可观察设定等价于 -可观察设定。因此,能够应用在 全-可观察设定下的 RL 算法同样能应用在 部分-可观察设定中,而无需做任何大的变动——所以,对算法的讨论就可以假设在全-可观察设定下。参考[BertsekasVol1] 对部分-可观察 MDP 如何规约到 MDP 的更加形式化的讨论。

在实际应用中,不适用整个原始的行动和观察的历史数据,agent 使用一个循环神经网络(RNN)将观察历史编码为一个定长向量 h_t,你可以将这个向量看成是 agent 的“短期记忆(short-term memory)”。


s 状态
a 行动
r 收益
y 观察
\tau 轨迹
\pi 策略
\theta 策略参数
R 总收益
\hat{A} 平均估计
V 状态-值函数
P 转换概率

2 黑盒优化和交叉熵方法


\mathrm{maximize}_{\theta} E[R|\theta],其中 R 是一个回合的总收益,行动是根据策略 \pi(a_t|s_t;\theta) 选择出来的。

(注意到我们可以仅仅使用一个确定的策略 a_t = \pi(s_t, \theta);但是上面的随机形式是可以推广使用的。)

最简单的方式就是把整个问题看做一个关于策略参数 \theta 的“黑盒”优化问题。也就是说,我们有一个参数向量 \theta 包含所有 agent 的参数,我们可以得到目标函数 E[R|\theta]  的带噪声的评价(evaluation)。我们称此为 黑盒 优化问题因为我们并不假设任何关于目标计算的知识,或者这是一个连续函数;我们仅仅通过在不同的输入 \theta_1, \theta_2,\dots 进行查询来学习这个函数。黑盒优化可以用下面一般的形式描述:

\max_\theta E_\zeta[f(\theta,\zeta)]

其中我们通过重复提供参数 \theta_i 来获得关于函数 f 的信息;然后采样出未观察噪声随机变量 \zeta_i,获得值 f(\theta_i, \zeta_i)。(如果是在计算机模拟中计算 f\zeta 可以对应于随机数生成器。)

在 RL 设定中,因为 \theta 是维度很高,黑盒方法(或者无导数优化算法)通常比其他 RL 算法(探索问题结构型的)低效。但是,在实际应用中,在小的问题上常常表现得很好,也是最为容易实现的算法。

交叉熵方法(CEM)是简单的黑盒优化算法。CEM 通过重复更新在候选参数向量 \theta 上的高斯分布的均值和方差进行。


Algorithm 1: 交叉熵方法 CEM

  1. 初始化 \mu\in \mathbb{R}^d,\sigma\in \mathbb{R}^d
  2. 迭代 = 1,2,\dots
    1. 采样 n 样本 \theta_i\sim N(\mu, diag(\sigma))
    2. 对每个样本执行噪声的评价 f(\theta_i, \zeta_i)
    3. 选择前 p\% 样本 (e.g. p=20),称为“精英集合(elite set)”
    4. 用精英集合拟合一个高斯分布,使用对角协方差,得到新的 \mu,\sigma
  3. 返回最终的 \mu

更多细节和实践中的提升可以在[SzitaLorincz06]中找到。在 RL 设定中,我们通过对一个或者更多的回合执行策略参数化评价 f(\theta_i, \zeta_i) ,并计算总收益。

2.1 练习

  1. (实践 *) 实现交叉熵方法,将其应用在CartPole 环境中。
  2. (实践 *) 将其应用在 Swimmer 环境中,这是一个连续行动空间的情形。尝试人工增加方差和逐步降低噪声为 0,如[SzitaLorincz06]
  3. (理论 ***) CEM 的一个弱点是精英集合中的元素可能已经碰巧选中,如幸运地成为 \zeta 的样本。 实际上,这会让 \thetaf 中产生高方差。所以,CEM 不会收敛到一个 \eta(\theta) = E_{\zeta}[f(\theta, \zeta)] 的局部最大值点。
    1. 解释为何 CEM 不能收敛到 \eta(\theta) 的局部最大值点
    2. 证明如果 f 是确定性的(即,如果不依赖于噪声 \zeta),那么 CEM 不会收敛到一个局部最大值点
    3. 在随机情形下,什么目标函数让 CEM 收敛到一个局部最优值点?
    4. 你能不能设计出一个算法通过在多个不同的  \theta 处评价同样的噪声样本 \zeta 在多个不同的  \theta 处解决这个问题?


2.2 笔记

你可能会想为何 CEM 叫这个名字。该名称最早来自积分估计的一种方法,你可以参考[Owen14]的第 10 章。

3 策略梯度

策略梯度算法通过梯度下降进行优化。就是说,通过重复计算策略的期望回报梯度的噪声估计,然后按照梯度方向来更新策略。该方法比其他 RL 方法(如 Q-学习)更有利主要是我们可以直接优化感兴趣的量——策略的期望总收益。该类方法由于梯度估计的高方差长期被认为不太实用,直到最近,[SchulmanEtAl15]和 [MnihEtAl16]等工作展示了神经网络策略在困难的控制问题上的采用策略梯度方法的成功应用。

3.1 直觉解释

你可能比较熟悉概率模型的监督学习,其中目标是最大化给定输入(x) 时的输出 (y) 的对数概率。

\max_{\theta} \sum_{n=1}^{N}\log p(y_n|x_n;\theta)

策略梯度方法通常需要假设一个随机策略,该策略给出了对每个状态 (s) 的行动 (a) 上的概率分布;我们将此分布写作 \pi(a|s;\theta)

如果我们知道对每个状态正确的行动 a^*,我们可以简单地最大化监督学习的目标函数:

\max_{\theta} \sum_{n=1}^{N}\log p(a^*_n|s_n;\theta)

然而,我们并不知道正确的行动。相反,我们会尝试对行动好坏进行粗略的猜测,试着去增加好的行动的概率。更加具体地讲,假设我们刚收集完 agent 和环境一个 agent 和环境回合的交互,所以我们有了一个状态、行动和收益的序列:\tau = (s_0, a_0, r_0,s_1, a_1, r_1,\dots,s_{T-1}, a_{T-1}, r_{T-1},s_T)。令 R 表示收益的和:R=\sum_{t=0}^{T-1} r_t。最简单的策略梯度公式就是:

\hat{g} = R\nabla_\theta \log(\prod_{t=0}^{T-1}\pi(a_t|s_t;\theta)) = R\nabla_\theta \sum_{t=0}^{T-1} \log \pi(a_t|s_t;\theta)

使用这个梯度的估计 \hat{g},我们可以用一个梯度上升的步骤,\theta\leftarrow \theta+\alpha \hat{g} 进行策略的更新,其中 \alpha 为学习率。我们会收集所有的回合,对那个回合中所有的行动的对数概率按照回合的总收益 R 为比例进行增加。换言之,如果我们收集了大量的回合数据,其中一些是好的(凭借运气),另外一些是差的。我们本质上是在进行监督学习——最大化好的回合的概率。


E[\hat{g}]=\nabla_\theta E[R]


如果我们用充足的样本(充足的回合),那么就可以任意精度计算出策略梯度。然而,估计量 \hat{g} 通常噪声很大,即有很高的方差。你可以想象,这里存在很大的提升空间。与其提高好的轨迹(trajectory)的概率,我们应该提高好的行动的概率,也就是说,我们应试着去推断哪些行动影响轨迹的好坏。


\hat{g} = \nabla_\theta \sum_{t=1}^{T} \hat{A_t}\log \pi(a_t|s_t;\theta)

其中 \hat{A_t} 是行动 a_t有利度 (advantage)的估计——比平均值好还是坏的程度。


\hat{A}_t=r_t + \gamma r_{t+1}+\gamma^2 r_{t+2} + \dots - V(s_t)

其中 \gamma 是折扣因子,V(s_t) 是 状态-值 函数 E[r_t+\gamma r_{t+1} + \gamma^2 r_{r+2}|s_t] 的近似。\gamma 用来定义一个有效时间区域,其中你忽略所有可能的超过未来 1/(1-\gamma) 的时间步的影响。关于有效度和时间区域更加详细的解释参见[SchulmanEtAl15]

3.2 更加形式化的解释

推导策略梯度公式的最简单的方式是使用分函数梯度估计量,这是估计期望梯度的通用方法。我们接着将此想法用在计算期望收益的梯度上。假设 x 是一个随机变量,其概率密度是 p(x|\theta),即概率密度依赖于参数向量 \thetaf 是一个标量值函数(就是收益),我们想要计算 \nabla_\theta E_x[f(x)]。我们得到了下面的等式:

\nabla_\theta E_x[f(x)] = E_x[\nabla_\theta \log p(x|\theta) f(x)]


\nabla_{\theta} E_{x}[f(x)] = \nabla_{\theta} \int \mathrm{d}x\ p(x | \theta) f(x) = \int \mathrm{d}x \nabla_\theta p(x|\theta) f(x) =\int \mathrm{d}x\ p(x|\theta) \nabla_\theta \log p(x|\theta) f(x)=  E_x[\nabla_\theta \log p(x|\theta) f(x)]

使用这个估计量,我们就可以采样 x \sim p(x|\theta),然后计算方程的左式(对 N 个样本进行平均)来获得梯度的估计(在 N \rightarrow \inf 时准确度更高)。就是说,我们采样 x_1, x_2, \dots, x_N \sim p(x|\theta),然后使用下面的梯度估计 \hat{g}

\hat{g} = \frac{1}{N} \sum_{n=1}^{N} \nabla_\theta \log p(x_i|\theta)f(x_i)

为了在强化学习中使用这个思想,我们需要用到随机策略。这意味着在每个状态 s,我们的策略给出了一个行动上的概率分布,记作 \pi(a|s)。因为策略同样有一个参数向量 \theta,我们就常写成 \pi(a|s, \theta)

在后续讨论中,轨迹 \tau 代表状态和行动的序列,即 \tau \equiv (s_0, a_0, s_1, \dots, s_T)。令 p(\tau | \theta) 表示在策略参数 \tau 下整个轨迹 \tau 的概率,令 R(\tau) 为整个轨迹的总收益。


\nabla_\theta E_{\tau} [R(\tau)] = E_{\tau} [\nabla_\theta \log p(\tau|\theta)R(\tau)

我们只需要采样轨迹 \tau,然后使用上面的公式计算策略梯度估计量。现在,我们需要显式地写出 \log p(\tau|\theta) 来推导出一个实用的公式。使用概率的链式法则,我们得到

p(\tau|\theta) = \mu(s_0)\pi(a_0|s_0,\theta)P(s_1|s_0, a_0)\pi(a_1|s_1,\theta)P(s_2|s_1, a_1)\dots\pi(a_{T-1}|s_{T-1},\theta)P(s_T|s_{T-1}, a_{T-1})

这里 \mu 是初始状态分布。我们对其取对数后,就得到一个和式,关于 \theta 求导,P(s_t|s_{t-1}, a_{t-1})\mu 一样就被消去了。我们得到

\nabla_\theta E_{\tau}[R(\tau)] = E_{\tau}[\sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t,\theta) R(\tau)]

这个公式非常厉害,因为我们可以不许知道系统动态知识(由转换概率 P 确定的)来计算策略梯度。直觉解释是我们收集了一个轨迹,然后与其总收益的好的程度(goodness)成比例提升概率。即,如果收益 R(\tau) 非常高,我们应该按照在参数空间中提高 \log p(\tau|\theta) 方向进行移动。

因此,通过一些数学推理,我们推导出一个更好(更低方差)的策略梯度估计。令 r_t 表示在时间步 t 的收益,令 b(s_t) 表示基准函数,该基准函数计算出状态-值函数的某个近似,即 b(s) \approx V^{\pi}(s) = E_{\tau} [\sum_{u=t}^{T}r_u|s_t = s](从状态 s 开始,未来收益的期望和)。改进的策略梯度公式如下:

\nabla_\theta E_{\tau}[R(\tau)] = E_\tau [\sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t,\theta) (\sum_{u=t}^{T}r_u - b(s_t))]


\nabla_\theta E_{\tau}[R(\tau)] \approx E_\tau [\sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t,\theta) (\sum_{u=t}^{T}\gamma^{u-t} r_u - b(s_t))]

其中 b(s_t) 就是对收益折扣和的近似 b(s) \approx  E_{\tau} [\sum_{u=t}^{T}\gamma^{u-t} r_u|s_t = s]

3.3 实现注意事项

有一种方便的方法计算策略梯度,就是对许多时间步使用你喜欢的自动微分软件进行批量操作。定义 L(\theta) = \sum_{t=0}^{T-1} \log \pi(a_t|s_t, \theta) \dot A_t,其中 A = (\sum_{u=t}^{T} r_u-b(s_t))。这里 A 表示有效度,因为它度量了回报超过期望值多少。这仅仅是不含梯度的上面策略梯度公式。你可以在程序中定义损失函数 L 。然后关于其参数进行微分,你就能得到策略梯度了!注意,不用花费长时间的总和,我们就能对 \log \pi(a_t|s_t,\theta) 进行向量化计算(该向量长度为 T )然后与一个同样长度为  T 的有效度的向量进行内积。

3.4 参数化策略

我们已经抽象式描述策略为 \pi(a|s,\theta)。我们如何使用一个神经网络进行表示?我们仅仅需要将 s 映射到某个向量 \mu 上,向量描述了行动 a 上的分布。例如,

  • 如果 a 来自一个离散的集合,那么我们设计一个神经网络将 s 到一个概率向量上。(我们一般在神经网络的最后层使用一个 softmax 激活函数)这完全就是我们用来进行分类器学习的形式。
  • 如果 a 是连续的,那么我们可以将 s 映射到一个高斯分布的均值和方差上。一般情况我们使用一个不依赖于 s 的对角协方差。
  • 如果 a 是二值的,那么我们可以使用一个单个输出的网络,表示输出 1 的概率。

3.5 练习

  1. 实现一个策略梯度算法将其应用在 CartPole 环境中。比较下面的变体:
    1. \hat{A_t} = R
    2. \hat{A_t} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots -V(s_t),包含(不包含)折扣因子和基准(共有 4 中情形)
  2. 将其应用在 Swimmer 环境中
  3. 改变问题 1 和 2 的实现,使用不同的 SGD 变体,包含 momentum、RMSProp 和 Adam

4 自然策略梯度和信任区间方法


5 Q-学习

到现在为止,我们讨论的都是策略优化的技术,不管是黑盒优化还是基于梯度的方法。另外一种不同的方法是估计一个衡量所有可能的行动好坏的函数,使用这个函数来定义策略。回想一下最优的状态-值函数 V^*(s) 衡量了在最优策略下状态的好坏,最优状态-行动值函数 Q^*(s,a) 给出了在状态 s 执行行动 a 时的好坏的衡量。

V^*(s)= E[r_0 +\gamma r_1 + \gamma^2 r_2 + \dots |s_0 = s, \pi^*]

Q^*(s,a)= E[r_0 +\gamma r_1 + \gamma^2 r_2 + \dots |s_0 = s, a_0 = a, \pi^*]

(稍微解释一下上面的表述,在 V^* 中,我们以开始状态 ss_0,依照 \pi^* 选择出的连续的变量 a_0, r_0, s_1, a_1, r_1, \dots 序列,在这个序列上取期望。)Q^* 更加适合我们对系统的动态模型没有知识的设定,这个原因后面会解释清楚。

本节会讨论学习 Q-函数的算法。最优 Q-函数(Q^*)满足下面的 Bellman 方程

Q^*(s,a) = E_{s'}[r(s,a,s') + \gamma V^*(s)] = E_{s'}[r(s,a,s') + \gamma \max_{a'} Q^*(s,a')]

我们可以使用下面的值迭代(value iteration)算法迭代更新 Q-函数,收敛到 Q^*


Algorithm 2: Q-值迭代

  1. 初始化 Q^{(0)}
  2. n = 1,2,\dots
    1. (s,a)\in S\times A (所有状态行动对)
      1. Q^{(n)}(s,a) =E_{s'}[r(s,a,s') + \gamma \max_{a'} Q^{(n-1)}(s,a')] (*)

最优 Q-函数(即,最优策略的 Q-函数)是更新 (*) 式的不动点,更严格点说,这是一个收缩(contraction),其误差指数级下降 ||Q^{(0)}-Q^*|| \propto \gamma^n

最优 Q-函数可用来引出一个形式——back-up 操作符 T,将 Q-函数映射到一个更新版本 TQ 上,定义如下:

[TQ](s,a) = E_{s'}[r(s,a,s') + \gamma \max_{a'} Q(s,a')]

这个被定义为 backup 操作符因为它使用向前看一步(对 s' 求期望)更新了 Q-值——也就是说,它让信息按照时间回流。使用backup 操作符,Q-值迭代对 (s,a) 的循环可以简洁地写作 Q^{(n)} = TQ^{(n-1)}

如果我们知道准确的转换模型和系统的收益函数,我们就可以仅计算准确的关于 s' 的期望。为了准确计算目标值,我们需要对 s' 求期望,就必须能够获取转换模型和收益函数的信息。但是,给定一个状态、行动、收益和下一状态 (s_t, a_t, r_t, s_{t+1}') 的转换,我们可以构造出一个 [TQ](s_t,a_t) 的无偏估计。然后我们可以给 Q(s,a) 噪声估计了目标值 [TQ](s,a) = E_{s'} [r(s,a,s') + \gamma \max_{a'} Q^{(n-1)}(s', a')]。我们称这个噪声估计为 \hat{TQ},定义如下

\hat{TQ}_t = r_t + \gamma \max_{a'} Q(s_{t+1},a')


E_{s_{t+1}} [\hat{TQ}_t|s_t,a_t] = TQ(s_t,a_t)

注意 \hat{TQ} 不依赖于我们在状态 s_{t+1} 时采取的行动,因此,这个无偏性不依赖于我们执行的策略,所以我们有很多的自由来考虑使用什么策略来收集数据。使用这些估计量,我们可以设计出下面的算法,收集批量的数据然后使用值迭代更新 Q-函数。由于不管采取何种策略都能够获得一个无偏估计,很多模型未知的情况下,基于 Q-函数的算法比之基于 V-函数的算法常常更受青睐。(如果模型已知,我们可以存储 V-函数来定义 Q-函数。)

Algorithm 3: 基于模拟的 Q-值迭代

  1. 初始化 Q^{(0)}
  2. n = 1,2,\dots
    1. 和环境交互 T 个时间步,通过从某种策略 \pi^{(n-1)} 中选择行动获得轨迹 (s_0, a_0, s_1, a_1,\dots,s_T) (如果是一个按照回合进行的任务,可能会包含多个回合)
      1. Q^{(n)} = \mathrm{minimize}_{Q} \sum_{t=1}^{T} ||Q(s_t,a_t) - \hat{TQ}||^2,其中 \hat{TQ} 使用当前 Q-函数 Q^{(n-1)} 算出

在第 n 次迭代时该选择什么策略 \pi^{(n-1)}?由于 \hat{TQ} 的无偏性,任何能够充分访问状态-值对的策略都能够给出所有目标 Q-值 [TQ](s,a) 一致的估计,就是说,若用无穷多的数据就能够给出正确的 [TQ](s,a)。典型方法是使用 \epsilon-贪婪策略,按照概率 \epsilon 随机行动,按照概率 1-\epsilon 使用 \mathrm{arg max}_{a} Q(s,a)。随机行动概率 \epsilon 通常从 1 缓慢退火为 0

算法 3 是一种批式算法:批式强化学习算法在收集数据和使用这个数据执行参数更新两步交替进行。这和在线算法有所不同,在线算法在数据收集的同时增量更新。我们能不能将 n=1 设计一个在线算法?可以,但是我们需要作出小的调整来限制在每个迭代对 Q 更新的大小(现在只有一个时间步)。通常,我们通过混合有噪声的估计和当前值计算目标 Q-值,混合比例 \alpha\in(0,1)

\hat{TQ}_t = (1-\alpha)Q(s_t, a_t) + \alpha(r_t + \gamma \max_{a'} Q(s_{t+1},a'))

Q(s_t,a_t) \leftarrow \hat{TQ}_t

这个算法称为 Watkins Q-学习算法[WatkinsDayan92]。给定合适的将 \alpha 下降到 0 的设计,并给定能够访问所有状态-行动对无穷多次的策略(如使用 \epsilon-贪婪策略),这个算法能够保证收敛到最优策略。[JaaJorSingh94] 给出了一个简洁的分析。然而在现实应用中,这个算法需要相当大的时间步数。

前面我们讨论了 Q-函数 Q(s,a)。如果状态空间和行动空间是离散的(有限集合),那么最为直接的方式是使用一个 Q 函数表,将 Q-函数作为一个数组存放,每个 (s,a) 对都有一个位置。而如果状态空间巨大或者是无穷的,这显然是不太现实的选择,所以我们需要找一个函数的近似方法,如神经网络,来表示 Q-函数。

我们记 Q_\theta 为由参数向量 \theta 参数化的 Q-函数。存在至少两个合理的方法来参数化 Q-函数:

  1. 网络以 (s,a) 为输入,以标量 Q-值为输出。
  2. 网络将 s 映射到某个参数向量 \mu,这个可以和行动组合来获得标量 Q-值。

实际情形下,第二种方式工作得更好,也得到了更加有效的算法。类比于我们前面对参数化策略的讨论,我们可以定义依赖于行动空间的 Q-函数的不同的参数化方式。

  • 如果 a 来自一个离散集合,那么我们设计一个神经网络将 s 映射到一个 Q-值的向量
  • 如果 a 是连续的,那么我们可以使用一个神经网络将 s 映射到一个二次函数的中心,其curvature,产生 Q-值 Q(s,a) = ||(a-\mathrm{center}) \odot \mathrm{curvature}||^2。参见[GuEtAl16]

给定该参数化 Q-函数,我们可以运行 Q-值迭代算法,优化的步骤变成:

\theta^{(n)} = \mathrm{minimize}_\theta \sum_t ||Q_\theta(s_t, a_t) - \hat{TQ}_t||^2

这个算法被称为 神经网络拟合 Q-迭代(Neural-Fitted Q-Iteration) [Riedmiller05]

最近,Mnih 等人提出了这个算法的变体版本,将数据采集纳入 Q-函数更新[MnihEtAl13]。他们使用了一个 目标网络,类似于前面的 Q-函数 Q^{(n-1)}。他们还使用了一个 回放缓冲区 (replay buffer),包含最近一些 Q-函数收集到的数据,而在算法 3 中,只是使用了 Q^{(n-1)} 采集的数据来拟合 Q^{(n)}

5.1 练习

  1. 实现 Watkins Q-学习算法,应用在 toy_text gym 环境中。你还可以使用策略迭代来计算最优解,比较一下性能。(注意这些环境给出了方便的转换模型和收益函数)
  2. 应用批式 Q-值迭代算法或者 DQN 在 classic_control 环境中。
  3. 应用批式 Q-值迭代算法或者 DQN 在 mujoco 环境中,使用一个二次的 Q-函数。

6 引用

[BertsekasVol1] Bertsekas, Dynamic Programming and Optimal Control, Volume I.
[SzitaLorincz06] (1, 2) Szita and Lorincz, Learning Tetris with the Noisy Cross-Entropy Method.
[SchulmanEtAl15] (1, 2) Schulman, Moritz, Levine, Jordan, Abbeel, High-Dimensional Continuous Control Using Generalized Advantage Estimation.
[MnihEtAl13] Mnih et al., Playing Atari with Deep Reinforcement Learning.
[MnihEtAl16] Mnih et al., Asynchronous Methods for Deep Reinforcement Learning.
[Owen14] Owen, Monte Carlo theory, methods and examples.
[GoschinWeinsteinLittman13] Goschin, Weinstein, Littman, The Cross-Entropy Method Optimizes for Quantiles
[GuEtAl16] Gu et al., Continuous Deep Q-Learning with Model-based Acceleration
[Riedmiller05] Riedmiller. Neural fitted Q iteration—first experiences with a data efficient neural reinforcement learning method.
[JaaJorSingh94] Jaakkola, Jordan, and Singh. On the convergence of stochastic iterative dynamic programming algorithms.
[WatkinsDayan92] Watkins, Dayan. Q-learning.
[KakadeLangford02] Kakade & Langford, Approximately optimal approximate reinforcement learning
[Kakade01] Kakade, Sham. A Natural Policy Gradient









SBT 修改远程仓库地址方法

sbt 直接修改sbt-lauch.jar/sbt/sbt.boot.properties的方式

  version: ${sbt.scala.version-auto}

  org: ${sbt.organization-org.scala-sbt}
  name: sbt
  version: ${sbt.version-read(sbt.version)[0.13.9]}
  class: ${sbt.main.class-sbt.xMain}
  components: xsbti,extra
  cross-versioned: ${sbt.cross.versioned-false}
  resources: ${sbt.extraClasspath-}

    Local-Maven-Repository: file:///Users/myname/Java/java-repositories, [organization]/[module]/[revision]/[type]s/[artifact](-[classifier]).[ext]
    typesafe-ivy:, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext] 

  directory: ${${${user.home}/.sbt}/boot/}

  checksums: ${sbt.checksums-sha1,md5} 
  override-build-repos: ${} 
  repository-config: ${sbt.repository.config-${${user.home}/.sbt}/repositories} 
  1. repositories 远程仓库地址
  2.  ` typesafe-ivy` 兼容ivy地址
  3. ivy-home:本地仓库地址,jar 存放地址

Guide to Data Science Competitions

Happy Endpoints

“Don't worry about a thing,every littleSummer is finally here and so are the long form virtual hackathons. Unlike a traditional hackathon, which focus on what you can build in one place in one limited time span, virtual hackathons typically give you a month or more to work from where ever you like.

And for those of us who love data, we are not left behind. There are a number of data science competitions to choose from this summer. Whether it’s a new Kaggle challenge (which are posted year round) or the data science component of Challenge Post’s Summer Jam Series, there are plenty of opportunities to spend the summer either sharpening or showing off your skills.

The Landscape: Which Competitions are Which?

  • Kaggle
    Kaggle competitions have corporate sponsors that are looking for specific business questions answered with their sample data. In return, winners are rewarded handsomely, but you have to win first.
  • Summer Jam

View original post 313 more words