强化学习

——————————————————————————————————————————————

强化学习笔记

——————————————————————————————————————————————

Tsui Dik Sang

2025 年 9 月 8 日——2026 年 2 月 9 日

Agent

Policy π(a|s)

Value / Update

Environment

Dynamics P (s

′

|s, a)

Reward R(s, a)

Action A

State S

t+1

Reward R

t+1

写在笔记之前

笔记只是探寻到了强化学习的冰山一角，实际的应用、如何调奖励、目标函数的技巧将由读者在科研探索的过程中自己去学

习领悟！

自学可参见西湖大学强化学习课程，

Tsui Dik Sang

2026 年 1 月 10 日

第一章 Bellman 5

1.1 强化学习基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 引入：马尔可夫决策过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 计算 return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.2 递推形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 矩阵形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Bellman 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.1 引入与定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.2 递推式的推导 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.3 Bellman 最优公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.3.1 条件数优化问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.4 压缩映射 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.4.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.4.2 不动点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.5 迭代求最优的算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.5.1

策略更新

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.5.2 状态值更新 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

第二章无模型方法 12

2.1 Monte Carlo 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.2 方法优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.2.1 ε-greedy 策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 随机近似与随机梯度下降 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.1.1 mean estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.1.2 一个改进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.2 Robbins-Monro 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.2.1 引入以及基础形态 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.2.2 收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.3 Stochastic Gradient Descent(SGD) 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.3.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.3.2 Gradient Descent(GD) 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.3.3 Batch Gradient Descent(BGD) 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.3.4 Stochastic Gradient Descent(SGD) 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.3.5 收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

强化学习笔记目录 Tsui Dik Sang

2.2.3.6 SGD 的收敛快慢 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.3.7 对比总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 时序差分方法 (TD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3.1 TD 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3.1.1 无模型的 Bellman 公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.2 Sarsa 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.2.1 action 的 Bellman 公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.2.2 基本形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.3 expected Sarsa 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.4 n-step Sarsa 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.5 Q-learning 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.5.1 算法内容 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.5.2 两种策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4 值函数近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.1.1 目标函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.1.2 状态分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.1.3 求梯度化简部分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.2 与两大算法的结合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.2.1 与 Sarsa 结合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.2.2 与 Q-learning 结合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.3 Deep Q-Network(DQN) 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

第三章基于策略 24

3.0.1 基本思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.0.1.1 目标函数的选取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.0.1.2 求梯度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.0.2 REINFORCE 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.0.3 算法伪代码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.0.4 核心逻辑解释 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1 Actor-Critic 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.1 基础 AC 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.2 A2C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.2.1 基线 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.2.2 重要性采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.3 DPG 策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

第四章近几年的策略优化算法 29

4.1 TRPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1.1 推导 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1.1.1 代理函数的引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1.1.2 KL 散度约束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2 PPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.2 Cliping Surrogate Objective(裁剪代理目标函数) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.3 Adaptive KL Penalty Coecient(自适应 KL 惩罚系数) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

第一章 Bellman

1.1 强化学习基本概念

几乎没有数学，因此从略

1.2 引入：马尔可夫决策过程

[1] 首先一个概念

定义 1.2.1 (回报 (Return)). 在某种策略下智能体在状态 s

时刻获得的收益和未来收益的折现和，

基础的 Markov 过程已经系统建模与仿真中讲过了，这里使用一个简单的链路来计算在一种策略下的 return 值

图 1.1: 考虑未来收益的 return 计算

强化学习笔记第一章 BELLMAN Tsui Dik Sang

1.2.1 计算 return

很显然这个图已经给定了一种策略，因此 return 的计算如下











= r

+ γv

+ γ

+ · · ·

= r

+ γv

+ · · ·

= r

+ γv

+ · · ·

= r

+ · · ·

(1.1)

1.2.2 递推形式

后面的求和将是无限的，但是如果 γ < 1，是收敛的，但是始终是不好计算，于是转成递推的形式

= r

+ γ(r

+ γr

+ · · · ) = r

+ γv

(1.2)

如此类推其他也可以写成递推的形式，然而，还是难求的。

1.2.3 矩阵形式

[1]（动态规划）然而，如果写成这样

v = r + γP v (1.3)

其中

v =































0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0







(1.4)

那么就可以很轻松的求出

v = (I − γP )

−1

r (1.5)

这是在固定策略下的一个例子计算，下面，将推导在策略也不知情况下一般 Bellman 方程的形式。

1.3 Bellman 方程

[1]

1.3.1 引入与定义

刚刚定义的回报是对于一种 trategy 的回报，如果策略也是未知但是概率已知的话，接下来就将推导

策略分解到单步是一个 action，于是策略之间转换的过程就可以写成

定义 1.3.1 (策略 (policy)).

−−→ R

t+1

, S

t+1

−−−→ R

t+2

, S

t+2

· · · (1.6)

着实际上就是一种已知的策略

在这种价值的定义下的损失价值函数为

= R

t+1

+ γR

t+2

+ γ

t+3

+ · · · (1.7)

如果策略对于 action 是不定的话，就需要平均值，于是就有定义

强化学习笔记第一章 BELLMAN Tsui Dik Sang

定义 1.3.2 (状态价值函数 (state-value function)). 在策略 π 下，状态 s 的价值函数为

(s) = E

= s] (1.8)

1.3.2 递推式的推导

接下来将展开 eq. (1.8)，使得其与可知道概率都扯上关系。首先，这一定是一个回环，因此写成递推式是第一步

(s) = E

= s]

= E

t+1

+ γG

t+1

= s]

= E

t+1

= s] + γE

t+1

= s]

(1.9)

先看第一项 E

t+1

= s]，我们先展开，再解释

t+1

= s] =

π(a|s)E[R

t+1

= s, A

= a]

π(a|s)

′

p(r|s, a)r

(1.10)

这里阐明几个可能搞混的点 π(a|s) 是策略在状态 s 下选择 actiona 的概率，而 p(r|s, a) 是状态 s 下选择 actiona 后获得奖励 r

的概率。因此后面还要乘以 r。

接下来是第二项 E

t+1

= s]，同样先展开

t+1

= s] =

′

t+1

= s, S

t+1

= s

′

]p(s

′

|s)

′

t+1

= s

′

]p(s

′

|s)

′

)p(s

′

|s)

′

)

π(a|s)p(s

′

|s, a)

(1.11)

其中第一行到第二行实际上反应的就是 Markov 的无记忆性，即在已经知道下一个状态是 s

′

的情况下，当前状态 s 就不重要了，

因此可以去掉。

而 v

′

) 就是下一个状态的价值函数，因此直接代入。

接下来对 p(s

′

|s) 的分解就是考虑到不同策略时候采取 actiona 的概率，因此要乘以 π(a|s)。

于是代入

定理 1.3.1 (Bellman 方程). 在策略 π 下，状态 s 的价值函数为

(s) =

π(a|s)

′

p(r|s, a)r

| {z }

即时奖励

+ γ

′

)

π(a|s)p(s

′

|s, a)

| {z }

未来奖励的折现值

π(a|s)





′

p(r|s, a)r + γ

′

)p(s

′

|s, a)





∀s ∈ S

(1.12)

这里标红的表征的就是两个状态之间价值的传递关系，这就是 Bellman 方程的核心，在其他乱七八糟概率都已知的情况下就是

一个简单的线性函数。

强化学习笔记第一章 BELLMAN Tsui Dik Sang

推论

1.3.2 (

策略的好坏

策略将影响

eq. (

1.12)

中的

(

)

，因此不同策略下的

(

)

也不同，而价值函数越大的策略越好。

1.3.3 Bellman 最优公式

何为最优，给出一个严谨的数学表示

定义 1.3.3 (策略的比较). 如果两个策略 π

和 π

，

∀s ∈ S, v

(s) ⩾ v

(s) (1.13)

则称策略 π

优于策略 π

，

于是最优策略就是

定义 1.3.4 (最优策略). 如果策略

∀s ∈ S, π ∈ Π, v

∗

(s) ⩾ v

(s) (1.14)

则称策略 π

∗

为最优策略

这个笔记是想从数学上理解强化学习，因此对于上面的定义，我们要问几个问题

• 最优策略是否存在？

• 最优策略是否唯一？

• 怎么样求解

• (特殊的问题) 最优策略是确定的还是概率性的？

下面将从数学上讲述这些问题。首先根据 eq. (1.12) 给出要优化的问题

定理 1.3.3 (Bellman 最优方程 (Bellman optimality equation)). 代数形式为

v(s) = max

π(a|s)





′

p(r|s, a)r + γ

′

v(s

′

)p(s

′

|s, a)





= max

π(a|s)q(s, a) ∀s ∈ S (1.15)

矩阵形式为

v = max

+ γP

v) (1.16)

可以发现，这个优化问题不是简单的线性优化，因为在优化式子右边有左边的项 v，我们分两步引入概念分析

1.3.3.1 条件数优化问题

引理 1.3.4 (有约束的线性优化问题). 考虑下面的最优化问题

max

,··· ,c

i=1

(1.17)

强化学习笔记第一章 BELLMAN Tsui Dik Sang

i=1

= 1 (1.18)

其中 c

⩾ 0 均已知，且不妨设 c

= max{c

, c

, · · · , c

}，那么最优解为 x

= 1，其他 x

= 0。

这个定理直观上很好理解，证明也不难。由此回顾我们的问题 eq. (1.15), 可以知道这也是这样的类似的问题。于是

推论 1.3.5 (最优策略的确定).

v(s) = max

π(a|s)q(s, a) = max

a∈A

q(s, a) (1.19)

在最优处

π(a|s) =







1, a = arg max

a∈A

q(s, a)

0, otherwise

(1.20)

用矩阵形式来写 eq. (1.19)

v = max

+ γP

v) = f (v) (1.21)

注意，上面式子是向量的，容易知道

f(v)

= max

π(a|s)q(s, a) (1.22)

1.3.4 压缩映射

1.3.4.1 定义

引入这个概念是为了接下来证明最优策略的唯一性和存在性

定义 1.3.5 (压缩映射 (Contraction mapping)). 如果映射 f 满足

∥f(x

) − f(x

)∥ ⩽ γ∥x

− x

∥, ∀x

, x

∈ X , γ ∈ (0, 1) (1.23)

则称 f 为压缩映射

1.3.4.2 不动点

定理 1.3.6. [不动点定理 (Banach xed-point theorem)] 如果 f 是 X 上的压缩映射，则存在唯一的不动点 x

∗

，即

f(x

∗

) = x

∗

(1.24)

并且对于任意的 x

∈ X ，迭代

n+1

= f (x

) (1.25)

都会收敛到 x

∗

。

定理 1.3.7 (压缩映射的不动点). 压缩映射都有唯一的不动点

然后不加证明的给出

强化学习笔记第一章 BELLMAN Tsui Dik Sang

定理 1.3.8. f (v) 是压缩映射，

∥f(v

) − f(v

)∥ ⩽ γ∥v

− v

∥ (1.26)

其中的 γ 就是折现因子！

于是根据 theorem 1.3.6知道

定理 1.3.9 (最优策略的存在与唯一). 存在一个唯一的最优策略其 state-value v

∗

满足

∗

= max

+ γP

∗

) (1.27)

并且对于任意的初始值 v

，迭代

n+1

= max

+ γP

) (1.28)

都会收敛到 v

∗

。

求解策略如下

• 先固定住最优 v

∗

= max

+ γP

∗

) (1.29)

• 然后再此等式右边求出最大值，此时的 π 就是最优策略 π

∗

= arg max

+ γP

∗

) (1.30)

• 此时原式就变成了

∗

= r

∗

+ γP

∗

(1.31)

可以证明

定理 1.3.10 (最优策略的确定性). 上式所确定的最优策略 π

∗

是确定性的，对应的状态价值函数为 v

∗

。

再一次的，确定一下这个算法

定理 1.3.11 (贪婪优化算法). 在状态 s 状态下，最优策略会选择 action-value 最大的 action。用数学的表示就是

∗

(a|s) =







1, a = arg max

a∈A

q(s, a)

0, otherwise

(1.32)

其中

∗

(s, a) =

′

p(r|s, a)r + γ

′

p(s

′

|s, a)v

∗

′

) (1.33)

1.3.5 迭代求最优的算法

下面介绍可用于编程实现的迭代过程

分为两部

• policy update

• state-value update

强化学习笔记第一章 BELLMAN Tsui Dik Sang

1.3.5.1 策略更新

回想一下刚刚提到的方法，对策略的更新是要在值给定的情况下求最大值

对于式子

k+1

(s) = arg max

π(a|s)





′

p(r|s, a)r + γ

′

p(s

′

|s, a)v

′

)





| {z }

(s,a)

(1.34)

直接使用贪婪算法。意味着

定理 1.3.12 (策略更新).

(a|s) =







1, a = arg max

a∈A

(s, a)

0, otherwise

(1.35)

1.3.5.2 状态值更新

在上述确定了下一轮的策略之后，就可以直接算出

定理 1.3.13 (状态值更新).

k+1

= r

k+1

+ γP

k+1

(1.36)

然后又可以算 π

k+2

，如此反复，直到收敛。

至于其收敛性，不加证明地指出

定理 1.3.14 (策略迭代收敛性). 该迭代过程会收敛到最优策略 π

∗

和最优状态值函数 v

∗

。

在赵老师的课中实际上他将上面的分成了三个算法，不过就算只用一个算法来解释也不难很清楚

推论 1.3.15 (策略迭代算法).

(j)

= r

+ γP

(j−1)

(1.37)

当 j = 1 时，是 value evaluation

•• 当

→ ∞

时，是

policy improvement

第二章无模型方法

2.1 Monte Carlo 方法

[1]

2.1.1 引入

实际上，我们已经在之前抽象过无模型的方法了，请看 eq. (1.15) 可能看得还不那么清楚，我们回归更原始的本质，在 eq. (1.15)

后面的一坨实际上源自于更数学期望

p(r|s, a)r + γ

′

p(s

′

|s, a)v

′

) = E [G

= s, A

= a] (2.1)

这是在有模型的时候我们可以根据左式精确算出，然而如果没有模型的话我们就只能通过数据来求右式，即

(s, a) = E [G

= s, A

= a] (2.2)

推论 2.1.1 (Monte Carlo 实验). 假设对于每一个状态动作对 (s, a)，我们都能多次采样到在该状态下采取该动作后得到一个

回报集 {g

(j)

(s, a)}, 则

(s, a) = E [G

= s, A

= a] ≈

N(s, a)

N(s,a)

j=1

(j)

(s, a) (2.3)

且当 n → ∞ 时，上式趋近于等号。

当 q

(s, a) 求出后，剩下的步骤即可用上一章节讲到的 Bellman 最优公式来迭代求解。

不过，既然是统计，那么精度就是一个要考量的点，包括：

• 样本的个数

• 往后选取的步数

如果选的过小，可能出现大片零值, 类似于半径范围内还没有目标

2.1.2 方法优化

实际上，如果对于每一个状态以及每一个 action 都进行枚举从而老实算出期望计算量较大，或者说有一些计算量其实是不

必须的。

因此思考，能否不将被研究的状态作为起点，而将其作为其他路径顺路经过的，因此其 episode 也是“顺路”计算的，这样

的话就简单很多。而如何实现呢？需要图论数据结构的知识了。

Explore & Start

强化学习笔记第二章无模型方法 Tsui Dik Sang

2.1.2.1 ε-greedy 策略

首先，这是一种和之前提到的贪婪策略不太相同的方法

定义 2.1.1 (soft 策略). 从一个或者几个 state 出发就可以遍历所有状态的策略

通过这种策略，“Explore & Start”的过程就可以大大减少，也意味着计算简便了。

于是，这种介于贪婪和随机的策略就可以定义了

定义 2.1.2 (ε-greedy 策略).

π(a|s) =











1 −

|A(s)|

(|A(s)| − 1), 策略是贪婪的时候

|A(s)|

, 其他

(2.4)

这相当于是在完全贪婪的策略中加入了探索性，其大小取决于 ε ∈ [0, 1]

2.2 随机近似与随机梯度下降

2.2.1 引入

2.2.1.1 mean estimation

也就是再普通的迭代式中找到一个递推的更新公式

定理 2.2.1 (逐步更新公式).

k+1

i=1

k−1

i=1

+ x

k − 1

= w

− w

) (2.5)

这实际上就已经是一种特殊的 SA 算法了。

2.2.1.2 一个改进

定理 2.2.2 (使用常数替代

k+1

= w

+ α(x

− w

) (2.6)

其中 α 是一个常数，

推论 2.2.3 (改进方法的收敛性). 上面描述的改进方法是收敛的

2.2.2 Robbins-Monro 方法

[1]

强化学习笔记第二章无模型方法 Tsui Dik Sang

2.2.2.1 引入以及基础形态

先提出逐个方法将要解决的问题

求下面方程的解

g(w) = 0 (2.7)

或者说想要求一个函数 J (w) 的极小值点

g(w) = ∇

J(w) = 0 (2.8)

如果这个函数是已知的，那么有很多种方法求到。但是如果这个函数未知，那么就需要使用 Robbins-Monro 方法了。

定理 2.2.4 (Robbins-Monro 方法).

k+1

= w

− α

˜g(w

, η

) (2.9)

其中 ˜g(w

, η

) 是 g(w

) 的一个采样，包含真值和一个噪音

˜g(w

, η

) = g(w

) + η

(2.10)

且 η

代表的是一个噪音

2.2.2.2 收敛性

上面的方法收敛吗？如果在满足一些条件下，是收敛的。具体详细证明不给出，但是可以直观去理解

推论 2.2.5 (Robbins-Monro 方法的收敛性). 如果被求函数 g(w) 以及序列 {α

} 满足一些条件，那么上面的 Robbins-Monro

方法是收敛的。

•

∀w 0 < c

⩽ ∇

g(w) ⩽ c

< ∞ (2.11)

•











∞

k=1

= ∞,

∞

k=1

< ∞

(2.12)

也即意味着此时

lim

k→∞

= w

∗

, g(w

∗

) = 0 (2.13)

2.2.3 Stochastic Gradient Descent(SGD) 算法

2.2.3.1 引入

要解决的问题如下

在我第二次看这个式子的时候被迷惑了，说明笔记做得还不够细，这里的 w

由下面的收敛性，应该是会越来越接近 w

∗

，也就意味着观测值 ˜g(w

) 会越来

越小，如果下面的收敛性得到证明的话这个式子直观理解就肯定是收敛的，希望这样能对这个式子理解更好

强化学习笔记第二章无模型方法 Tsui Dik Sang

min

J(w) = E

[f(w, X)] (2.14)

其中 X 是一个分布，是确定的，但是我们不知道

2.2.3.2 Gradient Descent(GD) 算法

定理 2.2.6 (Gradient Descent(GD) 算法).

k+1

= w

− α

∇

J(w

) = w

− α

[∇

f(w

, X)] (2.15)

2.2.3.3 Batch Gradient Descent(BGD) 算法

定理 2.2.7 (Batch Gradient Descent(BGD) 算法).

k+1

= w

− α

i=1

∇

f(w

, X

) (2.16)

其中 {X

} 是从分布 X 中采样得到的 N 个样本

这里的 n 可以小于 k，因此相比于第一种方法计算量是少了的。不过还是不够，于是就出现了

2.2.3.4 Stochastic Gradient Descent(SGD) 算法

只用一个样本来近似

定理 2.2.8 (Stochastic Gradient Descent(SGD) 算法).

k+1

= w

− α

∇

f(w

, X

) (2.17)

其中 X

是从分布 X 中采样得到的第 k 个样本

从形式来看这个方法一定是计算量最少的，但是是否收敛呢就是下面要讨论的

2.2.3.5 收敛性

我们只要能够以证明 SGD 算法是一种特殊的 Robbins-Monro 方法即可

对于 SGD 问题，我们解决的也是一个最小值问题，然后我们可以看到对于 α

后面的项

˜g(w

, X

) = ∇

f(w

, X

)

= E

[∇

f(w

, X)]

| {z }

g (w

)

+ (∇

f(w

, X

) − E

[∇

f(w

, X)])

| {z }

(2.18)

其中 η

是一个噪音，且满足 E

[η

] = 0，因此即证得

推论 2.2.9. SGD 算法是一个 Robbins-Monro 方法

进一步的由上面的 Robbins-Monro 方法的收敛性定理，我们可以得到

强化学习笔记第二章无模型方法 Tsui Dik Sang

推论 2.2.10 (SGD 算法的收敛性). 如果被求函数 J( w) 以及序列 {α

} 满足一些条件，那么上面的 SGD 算法是收敛的。

•

∀w 0 < c

⩽ ∇

J(w) ⩽ c

< ∞ (2.19)

•











∞

k=1

= ∞,

∞

k=1

< ∞

(2.20)

也即意味着此时

lim

k→∞

= w

∗

, ∇

J(w

∗

) = 0 (2.21)

2.2.3.6 SGD 的收敛快慢

显然一个数据虽然是少了，并且满足条件虽然也能收敛，但是快慢肯定是会有影响的，考虑相对误差

|∇

f(w

, X

) − E

[∇

f(w

, X)] |

[∇

f(w

, X)] |

(2.22)

用中值定理或者瞪眼法可以知道，当 δ

离精确值越远的时候，上式的分母会越大，因此收敛速度较快，而当 δ

离精确值越近的

时候，分母会越小，因此收敛速度较慢，其随机性增强，这也是少算的代价, 虽然不影响收敛性。

2.2.3.7 对比总结

• 如果 N=1，那么 BGD 算法就退化为 SGD 算法

• 如果 N= 样本总数，那么 SGD 算法就退化为 BGD 算法

大致了解！

2.3 时序差分方法 (TD)

先从 RM 引入一个本节将要解决的问题

引理 2.3.1 (时序差分方法要解决的问题). 在只有数据的情况下求解如下的均值

w = E[R + γv(X)] (2.23)

根据 RM 方法，可以得到如下的更新公式

k+1

= w

− α

− (R + γv(X))] (2.24)

2.3.1 TD 算法

首先明确需要什么

, a

, r

, s

, a

, r

, s

, · · · ) (2.25)

或者说对于任意时间点的一个

, r

t+1

, s

t+1

) (2.26)

然后利用下面的式子更新上面获得的数据，如果没有获得的就不更新

强化学习笔记第二章无模型方法 Tsui Dik Sang

定理 2.3.2 (TD 算法).







k+1

) = v

) − α

) − (r

t+1

+ γv

t+1

))] if s

is visited

k+1

(s) = v

(s) ∀s ̸= s

(2.27)

下面来拆解一下上面的公式

t+1

)

| {z }

新估计

= v

)

|{z}

旧估计

−α







) − (r

t+1

+ γv

t+1

))

| {z }

TD target( ¯v

)







| {z }

误差 (TD error)

(2.28)

对上面的式子简单变换可以得到

推论 2.3.3 (算法的收敛性).

t+1

) − ¯v

| = (1 − α

)|v

) − ¯v

| (2.29)

由于系数 1 − α

< 1，因此误差在不断减小，算法是收敛的。

对于误差根据定义我们可以得到

推论 2.3.4 (在最优策略下误差为零). 在最优策略情况下的 v

(s) 就是 state value function 的最优解 v

∗

(s)，此时误差为零

π,t

= v

) − E

t+1

+ γv

t+1

)|S

= s

] = 0 (2.30)

然而如果 v

(s) 不是最优解，那么误差就不为零，此时这个误差也相当于一个输入量进入式子迭代，进而向最优解靠近。

2.3.1.1 无模型的 Bellman 公式

于是我们从期望的角度来得到这个新定义

定理 2.3.5 (无模型的 Bellman 公式).

(s) = E

t+1

+ γG

= s] (2.31)

其中

= s] =

π(a|s)

′

p(s

′

|s, a)v

′

) = E

t+1

)|S

= s] (2.32)

所以又可以写成

(s) = E

t+1

+ γv

t+1

)|S

= s] (2.33)

于是对于一个任意初值 v

(s)，想要求出最后的 state value，就可以构造方程

g(v(s)) = v(s) − E

t+1

+ γv(S

t+1

)|S

= s] = 0 (2.34)

然后使用 RM 算法得到

推论 2.3.6 (用 RM 算法求解 Bellman 公式).

k+1

) = v

) − α

) − (r

t+1

+ γv

t+1

))] (2.35)

我的理解有一点负反馈的意味

强化学习笔记第二章无模型方法 Tsui Dik Sang

实际上上面标红的如果是 RM 算法应该是 v

t+1

)，然而显然这个是未知的没并且之后我们会证明替换成已知的 v

t+1

)

也是可以收敛的。

关于其收敛性要参考 RM 算法的收敛性定理 theorem 2.2.5, 这里不再赘述

比较 TD 算法，他是 online 的，也就是说会持续的更新，但是 Monte Carlo 方法是等一个 episode 结束才更新一次, 是 oine

的。

2.3.2 Sarsa 算法

[1] 不同于 TD 算法，Sarsa 算法估计的是 action value，也就是之前在式 eq. (1.15) 中提到的 q

(s, a)。

需要的数据

, a

, r

t+1

, s

t+1

, a

t+1

) (2.36)

这也是其名字由来。

2.3.2.1 action 的 Bellman 公式

定理 2.3.7 (action 的 Bellman 公式).

(s, a) = E

t+1

+ γq

t+1

, A

t+1

)|S

= s, A

= a] (2.37)

2.3.2.2 基本形式

其形式与 TD 基本一致

定理 2.3.8 (Sarsa 算法).







k+1

, a

) = q

, a

) − α

, a

) − (r

t+1

+ γq

t+1

, a

t+1

))] if (s

, a

) is visited

k+1

(s, a) = q

(s, a) ∀(s, a) ̸= ( s

, a

)

(2.38)

其收敛性也参见 RM 的收敛性可推得。

对于策略的更新，可以使用 ε-greedy 策略来进行 (仍然具有探索性)

2.3.3 expected Sarsa 算法

[1] 形式上还是对 ¯q

(s, a) 的一个更改

定理 2.3.9 (expected Sarsa 算法).







k+1

, a

) = q

, a

) − α

(

, a

)[q

, a

) − (r

t+1

+ γE

t+1

, A

t+1

)|S

t+1

= s

t+1

])] if (s

, a

) is visited

k+1

(s, a) = q

(s, a) ∀(s, a) ̸= ( s

, a

)

(2.39)

其中

t+1

, A

t+1

)|S

t+1

= s

t+1

] =

π(a|s

t+1

, a) (2.40)

显然的，这个算法需要的计算量更大，但是随机性更少一点

强化学习笔记第二章无模型方法 Tsui Dik Sang

2.3.4 n-step Sarsa 算法

[1] 我们要回到最开始关于 q

(s, a) 的写法

(s, a) = E

= s, A

= a] (2.41)

可以分多部写

Sara ←G

(1)

= R

t+1

+ γq

t+1

, A

t+1

)

Sara ←G

(2)

= R

t+1

+ γR

t+2

+ γ

t+2

, A

t+2

)

· · ·

n − step Sara ←G

(n)

= R

t+1

+ γR

t+2

+ · · · + γ

n−1

t+n

+ γ

t+n

, A

t+n

)

MonteCarlo ←G

(∞)

= R

t+1

+ γR

t+2

+ · · ·

(2.42)

也就是说他是 Sarsa 和 Monte Carlo 方法的一个折中方法因此其需要的数据比 Sarsa 更多一些，但是又不需要像 Monte Carlo

方法那样需要无穷多的 (或者说是一个 episode) 数据。具体如下

, a

, r

t+1

, s

t+1

, a

t+1

, r

t+2

, s

t+2

, a

t+2

, · · · , r

t+n

, s

t+n

, a

t+n

) (2.43)

实际上他后面讲了，这个的更新具有一个“滞后性”，也就是说，我的理解是——这是一个因果系统，其迭代需要等到 n 步之后

才能更新当前的值。即

t+n

, a

) = q

t+n−1

, a

) − α

t+n−1



t+n−1

, a

) − [r

t+1

+ γr

t+2

+ · · · + γ

n−1

t+n

+ γ

t+n−1

t+n

, a

t+n

)]



(2.44)

2.3.5 Q-learning 算法

[1]

2.3.5.1 算法内容

改动的还是只有 TD target ¯q

(s, a)

定理 2.3.10 (Q-learning 算法).











k+1

, a

) = q

, a

) − α



, a

) − (r

t+1

+ γ max

a∈A

t+1

, a))



if (s

, a

) is visited

k+1

(s, a) = q

(s, a) ∀(s, a) ̸= ( s

, a

)

(2.45)

实际上，Q-learning 算法并不是在解 Bellman 方程，解的是 Bellman 最优方程

q(s, a) = E



t+1

+ γ max

′

∈A

q(S

t+1

, a

′

)|S

= s, A

= a



(2.46)

2.3.5.2 两种策略

定义 2.3.1 (behavior policy). 用于生成数据的策略

定义 2.3.2 (target policy). 用于估计 action value 的策略

于是可以对上面的方法进行分类

强化学习笔记第二章无模型方法 Tsui Dik Sang

定义 2.3.3 (On-policy 方法和 O-policy 方法). -

• On-policy 方法：behavior policy 和 target policy 是同一个策略，比如 Sarsa 算法

• O-policy 方法：behavior policy 和 target policy 不是同一个策略，比如 Q-learning 算法

推论 2.3.11 (Sarsa 算法是 On-policy 方法). Sarsa 算法的 behavior policy 和 target policy 是同一个策略, 通过探索进行更

新策略，并且用同一个策略来继续估计 action value。

推论

2.3.12 (

Monte Carlo

和

n-step Sarsa

算法是

On-policy

方法

). Monte Carlo

方法和

n-step Sarsa

算法的

behavior policy

和 target policy 是同一个策略, 通过探索进行更新策略，这其实由 Sarsa 算法直接推广而来。

那么 Q-learning 算法呢

推论 2.3.13 (Q-learning 算法是 O-policy 方法). Q-learning 算法的 behavior policy 和 target policy 不是同一个策略, 通过

探索进行更新策略，但是用贪婪策略来估计 action value。

最后关于总结，这些上面的方法都算是广义的 TD 算法，区别就在于 TD target 的不同。这个再看即可

2.4 值函数近似

2.4.1 引入

首先理解这个方法，我的理解是其通过一个类似于插值拟合的方法用离散的个别点去表征连续空间。

在之前考虑的问题中，其实可以列出一个表来储存所有数据

State/Action a

· · · a

q(s

, a

) q(s

, a

) · · · q(s

, a

)

q(s

, a

) q(s

, a

) · · · q(s

, a

)

q(s

, a

) q(s

, a

) · · · q(s

, a

)

(2.47)

这在数学上表就是矩阵，然而取得太密 (计算量大) 或者太稀 (不够精确) 都不好，因此我们可以引入连续函数，这样的话，储存

的参数量就少很多了

拟合的形式可以看看这个

ˆv(s, w) = as

+ bs + c =

s 1













= ϕ(s)

w (2.48)

这里的 w 就是我们要学习的参数, 其维数越多，精度越高。

2.4.1.1 目标函数

到这里已经比较抽象了，我觉得是时候来看看代码了，不然纯看公式不够透彻了

真的就是拟合

强化学习笔记第二章无模型方法 Tsui Dik Sang

定义 2.4.1 (要优化的目标函数).

J(w) = E



(S) − ˆv(S, w))



(2.49)

如果认为每一个状态都是平等的, 那么上式子可以变为

J(w) =

|S|

s∈S

(s) − ˆv(s, w))

(2.50)

然而实际上，离目标越近的点显然应该更重要。那么就要引入

2.4.1.2 状态分布

引理 2.4.1 (状态分布). 根据 Markov 过程，随着时间的推移，各个状态被访问的频率会趋于一个稳定的分布，不妨设其为

(s)

此时变为

J(w) =

s∈S

(s)(v

(s) − ˆv(s, w))

(2.51)

至于这个 d 的具体定义呢

定义 2.4.2 (状态分布的定义).

(s) ≈

(s)

′

∈S

′

)

(2.52)

也可以用 Markov 链的平稳分布来算

推论 2.4.2.

(s) = d

(s)P

(2.53)

2.4.1.3 求梯度化简部分

现在需要最小化 eq. (2.49), 于是使用 RM 算法列出式子

k+1

= w

− α

∇

J(w

) (2.54)

容易化简其梯度为

推论 2.4.3.

∇

J(w) = −2E[(v

(S) − ˆv(S, w))∇

ˆv(S, w)] (2.55)

将系数放到前面系数里, 然后期望可以用 stochastic 的方法来近似

推论 2.4.4 (值函数近似的更新公式).

k+1

= w

+ α

) − ˆv(s

, w

))∇

ˆv(s

, w

) (2.56)

强化学习笔记第二章无模型方法 Tsui Dik Sang

这里的 v

) 是未知的，这在 Monte Carlo 方法和 TD 算法都有解决方案 Monte Carlo 方法中就是直接用平均值替代，而在

TD 算法中替换为如下

k+1

= w

+ α

t+1

+ γˆv(s

t+1

, w

) − ˆv(s

, w

))∇

ˆv(s

, w

) (2.57)

如果用拟合的方式表示呢就是

定理 2.4.5 (值函数近似的 TD 算法).

k+1

= w

+ α

t+1

+ γϕ( s

t+1

)

− ϕ(s

)

)ϕ(s

) (2.58)

然后还介绍了 ϕ 是单位向量时候的情况，从略

然后还介绍了其他的目标函数变式，包括范数等，还有一个是

定义 2.4.3 (Projected Bellman Error(PBE) 目标函数).

P BE

(w) = ∥ˆv(s, w ) − M T

ˆv(s, w)∥

(2.59)

即可能不会相等，但是如果做一个投影的话可能就相等了

2.4.2 与两大算法的结合

2.4.2.1 与 Sarsa 结合

将 v 化成 q 即可

定理 2.4.6 (值函数近似的 Sarsa 算法).

k+1

= w

+ α

t+1

+ γ ˆq(s

t+1

, a

t+1

, w

) − ˆq(s

, a

, w

)]∇

ˆq(s

, a

, w

) (2.60)

仍然还是 On-policy 的

2.4.2.2 与 Q-learning 结合

直接给公式了

定理 2.4.7 (值函数近似的 Q-learning 算法).

k+1

= w

+ α

t+1

+ γ max

a∈A

ˆq(s

t+1

, a, w

) − ˆq(s

, a

, w

)]∇

ˆq(s

, a

, w

) (2.61)

2.4.3 Deep Q-Network(DQN) 算法

[2] 先来看看他要优化的目标函数 loss function

J(w) = E



R + γ max

′

∈A

ˆq(S

′

, a, w) − ˆq(S, A, w)



(2.62)

意思是把 state value function 换成 action value function

现在对于这个算法过程已经有点晕乎乎了，可能真要看看代码哈哈哈

强化学习笔记第二章无模型方法 Tsui Dik Sang

于是尝试引入两个神经网络

将 max 里面的设置成主要网络，一直更新，而将外面的设置为 target 网络，隔一段时间更新一

次于是在式子中其可以先看成一个常量，求梯度的时候就只看后面，得到为

∇



max

′

∈A

(

′

, a, w

−

)

−

(

S, A, w

)



∇

(

S, A, w

)



(2.64)

如果想要求，知道变量的分布是不可避免的

显然的，这是 o-policy 的，

这是由下面的式子由来的

q(s, a) = E

[

t+1

+ γ max

′

∈A

q(S

t+1

, a

′

)|S

= s, A

= a

]

(2.63)

上面的 J(w) 反应的就是这样的一个误差

其实就是函数

参见视频第八课原因解释 , 还是相当的晕的

算法类似于一个反馈，反复的训练，不过还是相当的抽象的，不太懂。我建议要理解要找更底层的数学书，不过目前应该不影响你看代码了

第三章基于策略

[1] 之前我们是使用表格来描述策略的使用参数来描述策略的概念

π(a|s, θ) (3.1)

这个 θ 其实也是可以理解为神经网络，我们要优化的就是这个 θ，最简单的就是基于梯度的优化

t+1

= θ

+ α∇

J(θ) (3.2)

3.0.1 基本思路

3.0.1.1 目标函数的选取

一种简洁的想法是对各个 value 进行加权求和

¯v

s∈S

d(s)v

(s) = d

(3.3)

然后 d 源于一个分布，其实际上应该和 ¯v

是无关的。

有三种方式

• 认为是等概率的，则 d =

|S|

1；

• 认为每次都是从一个初始状态 s

开始的，则

) = 1, d

(s) = 0, s ̸= s

(3.4)

• 认为是马尔可夫链的平稳分布 d

，则

= d

(3.5)

接着将 eq. (3.3) 写成搞了的期望的形式，

¯r

= E

s∼d,s

(s)] (3.6)

State/Action a

· · · a

π(a

) π(a

) · · · π(a

)

π(a

) π(a

) · · · π(a

)

π(a

) π(a

) · · · π(a

)

强化学习笔记第三章基于策略 Tsui Dik Sang

又可以写成下面的形式

lim

n→∞

t=1

= s

(3.9)

推论 3.0.1 (不同目标函数的等价性). ¯v

，¯r

以及上面的极限形式是等价的。

¯v

= (1 − γ)¯r

(3.10)

还有下面的一个形式

推论 3.0.2.

J(θ) = E

∞

t=0

t+1

= s

(3.11)

3.0.1.2 求梯度

证明从略，直接给出梯度公式

引理 3.0.3 (策略梯度定理).

∇

J(θ) =

s∈S

η(s)

a∈A

∇

π(a|s, θ)q

(s, a) (3.12)

其中 η(s) 是状态 s 的概率分布

上面的式子可以写成下面的形式

推论 3.0.4 (对数形式).

∇

J(θ) = E [∇

ln π(A|S, θ)q

(S, A)] (3.14)

需要注意，这时候 π(a|s, θ) > 0。

所以这时候迭代式就变成了

t+1

= θ

+ α∇

ln π(A|S, θ)q

(S, A) = θ

+ α

(S, A)

π(A|S, θ)

| {z }

重要性采样比率β

∇

π(A|S, θ) (3.15)

这里的 β

能够很好的平衡探索和贪婪的关系

• 看分子，如果之前这个 action 的价值 q

(S, A) 很大，那么就应该增大这个动作被选择的概率，也就是贪婪

• 看分母，当 π(A|S, θ) 之前比较少的时候，就应该增大这个动作被选择的概率，也就是探索

(s) =

∑

a∈A

π(a|s)r(s, a) (3.7)

r(s, a) = E [R

t+1

= s, A

= a] (3.8)

使用下面的方式得到

∇

ln π(a|s, θ) =

∇

π(a|s, θ)

(3.13)

视频中有提到了一种构造函数的技巧，这里就从略了

强化学习笔记第三章基于策略 Tsui Dik Sang

3.0.2 REINFORCE 算法

[1] REINFORCE（蒙特卡洛策略梯度算法）是最基础的策略梯度方法，通过采样完整轨迹来估计策略梯度。

3.0.3 算法伪代码

Algorithm 1 REINFORCE 算法

Require: 策略参数初值 θ

，折扣因子 γ ∈ (0, 1]，学习率 α > 0，最大迭代次数 K

1: for k = 0 to K − 1 do

2: 初始化状态 s

∼ ρ

（初始分布）

3: 轨迹 τ ← ∅

4: repeat

5: 在状态 s

处，根据策略 π(a|s

, θ

) 采样动作 a

6: 在环境中执行 a

，获得奖励 r

t+1

和下一状态 s

t+1

7: 将 (s

, a

, r

t+1

) 加入轨迹 τ

8: until 到达终止状态或最大步数 T

9: 设轨迹长度为 T

10: for t = 0 to T − 1 do

11: 计算回报：G

T −1−t

k=0

t+k+1

12: 更新参数：θ

← θ

+ α∇

ln π(a

, θ

) · G

13: end for

14: end for

Ensure: 优化后的策略参数 θ

3.0.4 核心逻辑解释

• 生成轨迹：每次迭代使用当前策略完整地玩一局游戏，得到状态-动作-奖励序列。

• 计算回报：对轨迹中的每一时刻 t，计算从该时刻开始的所有后续奖励的折扣累积和 G

，衡量该动作的” 好坏”。

• 参数更新：沿着策略梯度 ∇

ln π(a

, θ

) 的方向，乘以回报 G

后进行更新，使高回报的动作被策略更倾向选中。

• 迭代优化：重复以上过程，逐步改进策略，最终获得接近最优的策略参数。

3.1 Actor-Critic 方法

[1] 首先，这里的 Actor 指更新的过程，Critic 指的是策略评估的过程。

3.1.1 基础 AC 模型

首先还是选取目标函数，可以是 ¯v

或者 ¯r

，

然后使用梯度的方法进行优化

t+1

= θ

+ α∇

J(θ) (3.16)

然后转化成不含有期望而通过采样即可得到的算法

t+1

= θ

+ α∇

ln π(A|S, θ)q

(S, A) (3.17)

然后后面的 q

(S, A)，如果是通过 Monte Carlo 的方法得到的, 那么就是 REINFORCE 算法，前面已经介绍过了，

如果用 TD 算法来估计的话，就是 AC 算法。至于算法，还是先生成一组 saras，然后更新，最后直接用更新的策略进行采

样。

强化学习笔记第三章基于策略 Tsui Dik Sang

3.1.2 A2C

3.1.2.1 基线

首先有一个引理

引理 3.1.1 (基函数的引入不会改变期望).

∀b(s), ∇

J(θ) = E

S∼η,A∼π

[∇

ln π(A|S, θ)q

(S, A)] = E

S∼η,A∼π

[∇

ln π(A|S, θ)(q

(S, A) − b(S))] (3.18)

证明要点是证

S∼η,A∼π

[∇

ln π(A|S, θ)b(S)] = 0 (3.19)

这个视频里有，这里就从略了。

那引入这个 b(S) 的意义是什么呢？其不会改变期望，但是会改变方差，所以可以找到一个最优的 b

∗

(S) 有最小的方差。同

样的不加证明的给出这个最优值

定理 3.1.2 (最优基函数).

∗

(s) =

A∼π

(∇

ln π(A|s, θ))

(s, A)

A∼π

(∇

ln π(A|s, θ))

(3.20)

于是将这个新的重新变成一个函数

(S, A) = q

(S, A) − b

∗

(S) (3.21)

然而实际上最优 b

∗

(S) 含有 q

(S, A)，所以无法直接使用, 所以一般使用

b(S) = v

(S) (3.22)

则

(S, A) = q

(S, A) − v

(S) (3.23)

但是注意，这不是最优的，只是一个权宜之计。

同样的这个也是一个兼顾了贪婪和探索的一个方法，并且通俗的理解——用相对值来衡量动作的好坏。

进一步的还可以改

= q

, A

) − v

) ≈ R

t+1

+ γv

t+1

) − v

) (3.24)

接下来有一个想法，想要用在 p

概率下采样的分布来估计在 p

概率下的期望，于是有重要性采样

3.1.2.2 重要性采样

引理 3.1.3 (重要性采样).

A∼p

[X] =

(x)X(x) =

(x)

X(x) = E

A∼p



(A)

X(A)



(3.25)

其中

(x)

称为重要性采样比率。

在课上说的是带基带的算法，稍微形象一点

强化学习笔记第三章基于策略 Tsui Dik Sang

举一个例子，如果 p

) ⩾ p

)，这个权重大于一，意味着这个点在 p

下采样的概率比较小，也就是说比较珍惜，所以需要

增大这个点的权重，反之亦然。

实际上，这个方法在离散运用不多，但是当 p 是连续的，而只能由神经网络得到，做积分就无法进行，这时候就很有用了

然后就可以实现 o-policy 的 AC 算法了

定理 3.1.4 (离线 AC 算法).

∇

J(θ) = E

S∼η,A∼β



π(A|S, θ)

β(A|S)

∇

ln π(A|S, θ)(q

(S, A) − v

(S))



(3.26)

其中 β 是行为策略，π 是目标策略。上面同样使用了 δ

(S, A) 来表示优势函数。

3.1.3 DPG 策略

也就是说确定性策略，π(s, θ) 可取 0 或者 1。于是我们可以更极端的定义一个状态空间的点到动作空间的映射

a = µ(s, θ) = µ(s) (3.27)

也就是对于一个确定的状态，其动作也就是确定的了。至于其梯度也是直接给出了

定理 3.1.5 (DPG 的梯度). (有 ai 的时候再更新)

至此，基于策略的方法就介绍完毕，也就是西湖大学赵世钰的课程全部结束

具体还是要给一些例子

第四章近几年的策略优化算法

4.1 TRPO

[4]

4.1.1 推导

4.1.1.1 代理函数的引入

我们要回到最原始的那一条式子

η(π) = E

,...∼π

∞

t=0

r(s

, a

)

(4.1)

其中策略和、状态等满足的分布设为











∼ ρ

(s)

∼ π(a |s

)

t+1

∼ P (s

′

, a

)

(4.2)

然后根据前面的定义求优势函数











(s, a) = E

t+1

,...

∞

l=0

r(s

t+l

, a

t+l

)|s

= s, a

= a

(s) = E

t+1

,...

∞

l=0

r(s

t+l

, a

t+l

)|s

= s

(4.3)

(s, a) = Q

(s, a) − V

(s) (4.4)

接下来的更新策略出自 2002 年的论文

引理 4.1.1 (策略改进定理).

η(˜π) = η(π) + E

,...∼˜π

∞

t=0

, a

)

(4.5)

即新策略的性能等于旧策略的性能加上新策略下的优势函数的期望累计折扣奖励

然后在有模型的情况下进行拆解得到

推论 4.1.2.

η(˜π) = η(π) +

˜π

(s)

˜π(a|s) A

(s, a) (4.6)

TPRO 的论文中也没有提到，因此我们也不证明

强化学习笔记第四章近几年的策略优化算法 Tsui Dik Sang

其中

˜π

(s) =

∞

t=0

P (s

= s|˜π) (4.7)

实际上这个是矛盾的，因此在新策略未知的情况下，ρ

˜π

(s) 无法计算

于是引入代理函数

定理 4.1.3 (代理函数).

(˜π) = η(π) +

(s)

˜π(a|s) A

(s, a) (4.8)

认为在旧策略下 L 和 η 梯度相同，优化 L 就是优化 η

在 2002 年的论文实际上旧已经提到了一个新能下界，而这篇论文引入 KL 散度

4.1.1.2 KL 散度约束

先给出这 KL 和 TV 散度，其衡量的是两个改了分布的“距离”

定义 4.1.1 (KL 散度).

(p, q) =

p(x) log

p(x)

q(x)

dx (4.9)

如果是离散的话

(p, q) =

p(x) log

p(x)

q(x)

(4.10)

定义 4.1.2 (TV 散度).

T V

(p, q) =

|p(x) − q(x)|dx (4.11)

如果是离散的话

T V

(p, q) =

|p(x) − q(x)| (4.12)

这两个定义之间有一个关系

引理 4.1.4 (Pinsker 不等式).

T V

(p, q) ⩽

(p, q) (4.13)

论文经过调整后证明了代理函数和真实函数之间的误差下界

引理 4.1.5 (TRPO 误差下界).

η(˜π) ⩾ L

(˜π) −

4ϵγ

(1 − γ)

(4.14)

那为什么 ˜π 未知还能计算 ˜π(a|s) 呢？(下面利用重要性采样的时候会给出回答)，给一下论文原句

However, if we have a parameterized policy π

, where π

(a|s) is a dierentiable function of the parameter vector θ, then L

matches η to rst

order (see Kakade & Langford (2002)).

We have modied it to make it slightly weaker but simpler.

强化学习笔记第四章近几年的策略优化算法 Tsui Dik Sang

其中

ϵ = max

s,a

(s, a)| (4.15)

α = D

max

T V

(π, ˜π) (4.16)

于是就得到了定理：

定理 4.1.6 (TRPO 下界).

η(˜π) ⩾ L

(˜π) − CD

max

(π, ˜π) (4.17)

其中

C =

4ϵγ

(1 − γ)

(4.18)

这也意味着只要去提升右边，就一定能让 η 单调提升其中 CD

max

(π, ˜π) 是一个惩罚项，如果过大的话意味着模型不敢更新策略，

因而步长会变小，所以论文中引入了“置信域”，对单纯的 max 优化问题加入了一个对 KL 散度的约束，如果以参数 θ 来表示

策略的话，最终的优化目标为







max

old

(θ)

(π

old

, π

) ⩽ δ

(4.19)

进一步的，根据重要性采样，

old

(θ) = E

s,a∼π

old



(a|s)

old

(a|s)

old

(s, a)



(4.20)

于是就可以根据旧策略进行更新了。

4.2 PPO

[5]

4.2.1 引入

论文是从一个典型的随机梯度目标函数开始的

ˆg = E

∇

log π

)

(4.21)

求上式等价于最大化如下的函数

P G

(θ) = E

log π

)

(4.22)

这时候面临的问题是，上式只有在新旧策略非常接近的时候才成立，否则的话得到的结果显然就不同了。

在上面的 TRPO 中我们引入了 KL 散度来约束新旧策略的距离，这确实解决了问题，不过这个 KL 散度计算复杂度较大，

并且是两个约束条件

我们还是希望只优化一个目标函数会好算一点, 如下

max



)

old

)

− βD

[π

old

(·|s

), π

(·|s

)]



(4.23)

PPO 提出了两种方法

4.2.2 Cliping Surrogate Objective(裁剪代理目标函数)

实际上就是给重要性采样参数手动设置了一个可变区间，要求新旧策略的差距不能太大。首先定义裁剪窗函数

后面是用 Hessian 矩阵来优化表达以及算法实现，先从略，但是总体的框架就是这样了

反正就是计算量大

强化学习笔记第四章近几年的策略优化算法 Tsui Dik Sang

定义 4.2.1 (裁剪窗).

clip(f(x), a, b) =











b f(x) > b

f(x) a ⩽ f(x) ⩽ b

a f(x) < a

(4.24)

定义 4.2.2 (裁剪代理目标函数).

clip

(θ) = E

min



(θ)

, clip(r

(θ), 1 − ϵ, 1 + ϵ)

i

(4.25)

其中 r

(θ) =

)

old

)

4.2.3 Adaptive KL Penalty Coecient(自适应 KL 惩罚系数)

这个方法是对后面的惩罚系数做手脚，一个简单的例子是

定义 4.2.3 (自适应 KL 惩罚目标函数).

KLP EN

(θ) = E

(θ)

− βKL[π

old

(·|s

), π

(·|s

)]

(4.26)

设 d =

[KL[π

old

(·|s

), π

(·|s

)]]

如果 d < d

target

/1.5，则 β ← β/2

•• 如果 d > 1.5d

target

，则 β ← 2β

参考文献

[1] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.

[2] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin

Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Iain Antonoglou, Helen King,

Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement

learning. Nature, 518(7540):529–533, 2015.

[3] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser,

Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalch-

brenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.

Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016.

[4] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In

Proceedings of the 34th International Conference on Machine Learning, pages 1889–1897, 2017.

[5] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms.

arXiv preprint arXiv:1707.06347, 2017.

No results found