强化学习的数学原理学习笔记 – RL基础知识

本文介绍: 强化学习的数学原理学习笔记：强化学习基础知识，包括对贝尔曼方程、贝尔曼最优方程的介绍。

文章目录

Roadmap
🟡基础概念
贝尔曼方程（Bellman Equation）
🟡贝尔曼最优方程（Bellman Optimality Equation，BOE）
- 基本形式
- 迭代求解

本系列文章介绍强化学习基础知识与经典算法原理，大部分内容来自西湖大学赵世钰老师的强化学习的数学原理课程（参考资料1），并参考了部分参考资料2、3的内容进行补充。

系列博文索引：

参考资料：

*注：【】内文字为个人想法，不一定准确

Roadmap

*图源：https://github.com/MathFoundationRL/Book-Mathmatical-Foundation-of-Reinforcement-Learning

🟡基础概念

MDP概念：

状态（state）、动作（action）、奖励（reward）
状态转移概率：
奖励概率：

马尔可夫性质：与历史无关（memoryless）
其他概念：轨迹（trajectory）、episode / trail、确定性（deterministic）、随机性（stochastic）

名称	含义	形式	备注
策略（policy）	从状态映射至所有动作的概率分布		策略决定了每个状态下应该执行什么样的动作
期望折扣回报（expected discounted return）	略 *reward和return的区别：reward指单步的奖励，return指多步的折扣回报	$G_t = R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + cdots = sum_{t=0}^{infty} gamma^t R_{t+k+1} Gt=Rt+1+γRt+2+γ2Rt+3+⋯=∑t=0∞γtRt+k+1 – γ ∈ [ 0 , 1 ] gamma in [0, 1] γ∈[0,1]：折扣因子 – 习惯性写成 R t + 1 R_{t+1} Rt+1，而非 R t R_t Rt$	评估某个策略的好坏，针对单个trajectory
值函数 / 状态值函数（state-value function）	从状态	$v_{pi}(s) = mathbb{E}_pi [ G_t \| S_t = s ] vπ(s)=Eπ[Gt∣St=s]：策略 π pi π的状态-值函数$	评估某个状态本身的价值，进而反映对应策略的价值
Q函数 / 动作值函数（action-value function）	从状态	$q_{pi}(s, a) = mathbb{E}_pi [ G_t \| S_t = s, A_t = a ] qπ(s,a)=Eπ[Gt∣St=s,At=a]：策略 π pi π的动作-值函数$	评估某个状态下特定动作的价值，注意动作

贝尔曼方程（Bellman Equation）

基本形式

每个状态

S_t

$S_{t}$ 的值函数，实际上等于按照策略

$π$ 行动后的奖励（

R_{t+1}

$R_{t + 1}$ ）加上后一个状态

S_{t+1}

$S_{t + 1}$ 的值函数的折扣值（

gamma G_{t+1}

$γ G_{t + 1}$ ），也就是即时奖励（immediate reward）和未来奖励（future rewards）的和。这种思想叫做Bootstrapping（自举法），对应的公式就是贝尔曼方程：

(

)

[

∣

]

∑

(

∣

)

∑

′

(

′

∣

)

[

(

′

)

]

∀

∈

begin{aligned} v_pi(s) &= mathbb{E}[R_{t+1} + gamma G_{t+1} | S_t =s] \ &= sum_a pi (a|s) sum_{s’, r} p(s’, r|s, a) [r + gamma v_pi(s’)], quad forall sin mathcal {S} end{aligned}

$v_{π} (s) = E [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s] = a \sum π (a ∣ s) s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})], \forall s \in S$

贝尔曼方程描述了不同状态之间的值函数的关系。给定策略后求解贝尔曼方程的过程也称之为策略评估（Policy Evaluation）。
比如有两个策略

pi_1

$π_{1}$ 和

pi_2

$π_{2}$ ，如果对于任何

∈

sin mathcal {S}

$s \in S$ ，

(

)

≥

(

)

v_{pi_1} (s) geq v_{pi_2} (s)

$v_{π_{1}} (s) \geq v_{π_{2}} (s)$ 都成立，那么可以认为

pi_1

$π_{1}$ 优于

pi_2

$π_{2}$ 。

矩阵-向量形式

贝尔曼方程也可以转化为矩阵-向量形式：

v_pi = r_pi + gamma P_pi v_pi

$v_{π} = r_{π} + γ P_{π} v_{π}$

状态向量： $v_pi = [v_pi(s_1), cdots, v_pi(s_n)]^T in mathbb{R}^n vπ=[vπ(s1),⋯,vπ(sn)]T∈Rn$
奖励向量： $r_pi = [r_pi(s_1), cdots, r_pi(s_n)]^T in mathbb{R}^n rπ=[rπ(s1),⋯,rπ(sn)]T∈Rn$
状态转移矩阵： $P_pi in mathbb{R}^{ntimes n} Pπ∈Rn×n，其中 [ P π ] i j = p π ( s j ∣ s i ) [P_pi]_{ij} = p_pi (s_j|s_i) [Pπ]ij=pπ(sj∣si)$

*四个状态时的示例：

迭代求解

v_{k+1} = r_pi + gamma P_pi v_k

$v_{k + 1} = r_{π} + γ P_{π} v_{k}$
先假设一个

v_k

$v_{k}$ 的值，基于该值计算出

v_{k+1}

$v_{k + 1}$ ，进而重复该过程不断计算出

⋯

v_{k+2}, v_{k+3}, cdots

$v_{k + 2}, v_{k + 3}, \dots$ 。
可以证明，当

→

∞

k rarr infin

$k \to \infty$ 时，

v_k

$v_{k}$ 会收敛到

v_pi

$v_{π}$ 。

状态值 vs. 动作值

(

)

∑

(

∣

)

(

)

v_pi (s) = sum_a pi (a | s) q_pi (s, a)

$v_{π} (s) = \sum_{a} π (a ∣ s) q_{π} (s, a)$
状态值可以看作是策略

$π$ 的每个动作值的加权平均。

(

)

∑

′

(

′

∣

)

[

(

′

)

]

q_pi (s,a) = sum_{s’, r} p(s’, r|s, a) [r + gamma v_pi(s’)]

$q_{π} (s, a) = \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$
动作值可以通过状态值求解，也可以不依赖于状态值求解。

🟡贝尔曼最优方程（Bellman Optimality Equation，BOE）

RL的目标是最大化累计奖励，则必然存在至少一个最优策略，记作

∗

pi_*

$π_{*}$ ，其对任意策略

$π$ 都满足：

∗

(

)

≥

(

)

∀

∈

v_{pi_*} (s) geq v_{pi}(s), forall sin mathcal{S}

$v_{π_{*}} (s) \geq v_{π} (s), \forall s \in S$ 。

基本形式

最优策略共享相同的最优状态值

∗

v_*

$v_{*}$ 与最优动作值

∗

a_*

$a_{*}$ 。寻找最优策略相当于求贝尔曼方程（

v_pi

$v_{π}$ 、

a_pi

$a_{π}$ ）的最优解（

max

⁡

max_pi

$max_{π}$ ），则贝尔曼最优方程为：

∗

(

)

max

⁡

(

)

max

⁡

∑

(

∣

)

(

)

begin{aligned} v_*(s) &= max_{pi} v_{pi}(s) \ &= max_{pi} sum_a pi (a | s) q_pi (s, a) end{aligned}

$v_{*} (s) = π max v_{π} (s) = π max a \sum π (a ∣ s) q_{π} (s, a)$

∗

(

)

max

⁡

(

)

∑

′

(

′

∣

)

[

∗

(

′

)

]

begin{aligned} q_*(s, a) &= max_{pi} q_{pi}(s, a) \ &= sum_{s’,r} p(s’, r|s, a) [r + gamma v_* (s’)] end{aligned}

$q_{*} (s, a) = π max q_{π} (s, a) = s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})]$

对应的矩阵-向量形式：

max

⁡

(

)

v = max_pi (r_pi+gamma P_pi v)

$v = max_{π} (r_{π} + γ P_{π} v)$

贝尔曼最优方程是一个特殊的贝尔曼方程，即当策略

$π$ 为最优策略

∗

pi_*

$π_{*}$ 时的贝尔曼方程：

∗

arg max

⁡

(

∗

)

pi_* = argmax_pi (r_pi + gamma P_pi v_*)

$π_{*} = arg max_{π} (r_{π} + γ P_{π} v_{*})$

∗

(

∗

)

v_* = (r_{pi_*}+gamma P_{pi_*} v_*)

$v_{*} = (r_{π_{*}} + γ P_{π_{*}} v_{*})$

注意：

最优状态值唯一，但最优策略并不唯一
对于一个给定系统，其最优状态值和最优策略受奖励值
r

r

$r$ 与折扣因子

γ

gamma

$γ$ 的影响
- 最优策略不受奖励值的绝对大小影响，但受其相对大小影响
- 折扣因子越小（接近0），策略越短视，反之（接近1）策略越长远

迭代求解

考虑贝尔曼最优方程的矩阵-向量形式，设

(

)

max

⁡

(

)

f(v) = max_pi (r_pi+gamma P_pi v)

$f (v) = max_{π} (r_{π} + γ P_{π} v)$ ，则贝尔曼最优方程可以写作：

(

)

v = f(v)

$v = f (v)$ 。

其中 $[f(v)]_s = max_pi sum_a pi(a|s)q(s, a), quadforall sinmathcal{S} [f(v)]s=maxπ∑aπ(a∣s)q(s,a),∀s∈S$

基于压缩映射定理（contraction mapping theorem）可知，

(

)

v = f(v)

$v = f (v)$ 的解（即最优状态值

∗

v_*

$v_{*}$ ）存在且唯一。可以通过迭代的方式进行求解，即：

max

⁡

(

)

v_{k+1} = max_pi (r_pi+gamma P_pi v_k)

$v_{k + 1} = max_{π} (r_{π} + γ P_{π} v_{k})$ ，其中

⋯

k=0, 1,2,cdots

$k = 0, 1, 2, \dots$
可以证明，当

→

∞

krarr infin

$k \to \infty$ 时，

→

∗

v_krarr v_*

$v_{k} \to v_{*}$ 。

通常的求解流程：【实际上就是基于模型（Model-based）中的值迭代（Value Iteration）算法】

对于任意一个状态 $v_k(s) vk(s)$
对于任意一个动作
a

∈

A

(

s

)

ainmathcal{A}(s)

$a \in A (s)$ ，计算

q

k

(

s

,

a

)

=

∑

s

′

,

r

p

(

s

′

,

r

∣

s

,

a

)

[

r

+

γ

v

k

(

s

′

)

]

q_k(s,a) = sum_{s’,r} p(s’, r|s, a) [r + gamma v_k (s’)]

$q_{k} (s, a) = \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{k} (s^{'})]$
- $v_k (s’) vk(s′)在第一次迭代时取初始值，后续迭代时使用前一轮迭代中更新后的值$
计算状态s下的确定性贪婪策略
π

k

+

1

(

a

∣

s

)

=

{

1

a

=

a

k

∗

(

s

)

0

a

≠

a

k

∗

(

s

)

pi_{k+1}(a|s) = begin{cases} 1 &a = a_k^*(s) \ 0 &a neq a_k^*(s) end{cases}

$π_{k + 1} (a ∣ s) = {10 a = a_{k}^{*} (s) a \neq = a_{k}^{*} (s)$
- $a_k^*(s) = argmax_a q_k(s, a) ak∗(s)=argmaxaqk(s,a)，表示使得当前状态动作值最大的那个动作$
计算
v

k

+

1

(

s

)

=

max

⁡

a

q

k

(

s

,

a

)

v_{k+1}(s) = max_a q_k (s, a)

$v_{k + 1} (s) = max_{a} q_{k} (s, a)$ ，继续下一轮迭代
- $v_{k+1}(s) vk+1(s)实际上就是上一步的最优动作对应的动作值（因为当前策略下其他动作的概率均为0）$

在实际应用中，当

∥

(

)

−

(

)

∥

|v_{k+1}(s) -v_{k}(s)|

$∥ v_{k + 1} (s) - v_{k} (s) ∥$ 低于某个阈值（如0.001）之后，就可以认为算法收敛了。

由于精确求解贝尔曼方程往往需要极高的计算开销，所以通常只获得近似解即可。

压缩映射定理（contraction mapping theorem），又称巴拿赫不动点定理（Banach fixed-point theorem）

参考：

非常神奇的数学结论有哪些？ – 知乎

Chapter 3: The Contraction Mapping Theorem – UC Davis Math

巴拿赫不动点定理 – 维基百科

直观认识：
将世界地图放在一个桌子上，则该桌子上必有一点，其实际位置会和地图上该点的对应位置重合，该点称之为“不动点（fixed point）”。
将该点的实际位置视作变量

x

x

$x$ ，其在地图上的位置视作函数

f

(

x

)

f(x)

$f (x)$ ，则

f

(

x

)

f(x)

$f (x)$ 可以视作对于

x

x

$x$ 的一种“压缩映射”，

f

(

x

)

=

x

f(x)=x

$f (x) = x$ 的解即为不动点。

数学描述：
若

∥

f

(

x

1

)

−

f

(

x

2

)

∥

≤

γ

∥

x

1

−

x

2

∥

|f(x_1)-f(x_2)| leq gamma| x_1 – x_2 |

$∥ f (x_{1}) - f (x_{2}) ∥ \leq γ ∥ x_{1} - x_{2} ∥$ （其中

γ

∈

(

0

,

1

)

gammain (0, 1)

$γ \in (0, 1)$ ），则

f

f

$f$ 为关于

x

x

$x$ 的压缩映射。

此处

例如：

压缩映射定理是指，若

f

f

$f$ 为压缩映射，则必然存在（exist）一个不动点

x

∗

x^*

$x^{*}$ 使得

f

(

x

∗

)

=

x

∗

f(x^*)=x^*

$f (x^{*}) = x^{*}$ ，且

x

∗

x^*

$x^{*}$ 唯一（unique）。

求解算法：迭代式算法
对于迭代序列

x

k

+

1

=

f

(

x

k

)

x_{k+1} = f(x_k)

$x_{k + 1} = f (x_{k})$ ，随着

k

→

∞

krarrinfin

$k \to \infty$ ，该序列指数收敛至

x

∗

x^*

$x^{*}$ 。

例如：以迭代式算法求 $x_0=10 x0=10，则可迭代得到： x 1 = 5 , x 2 = 2.5 , x 3 = 1.25 , ⋯ x_1=5, x_2=2.5, x_3=1.25, cdots x1=5,x2=2.5,x3=1.25,⋯，最终会逼近于0。$