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

---

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

系列博文索引：

• 强化学习的数学原理学习笔记 - RL基础知识
• 强化学习的数学原理学习笔记 - 基于模型（Model-based）
• 强化学习的数学原理学习笔记 - 蒙特卡洛方法（Monte Carlo）
• 强化学习的数学原理学习笔记 - 时序差分学习（Temporal Difference）
• 强化学习的数学原理学习笔记 - 值函数近似（Value Function Approximation）
• 强化学习的数学原理学习笔记 - 策略梯度（Policy Gradient）
• 强化学习的数学原理学习笔记 - Actor-Critic

参考资料：

1. 【强化学习的数学原理】课程：从零开始到透彻理解（完结）（主要）
2. Sutton & Barto Book: Reinforcement Learning: An Introduction
3. 机器学习笔记

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

Roadmap

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

🟡基础概念

MDP概念：

• 状态（state）、动作（action）、奖励（reward）
• 状态转移概率：$p(s^{\prime }|s,a)$
• 奖励概率：$p(r|s,a)$

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

名称	含义	形式	备注
策略（policy）	从状态映射至所有动作的概率分布	$\pi (a|s)$：在状态$s$下选择动作$a$的概率	策略决定了每个状态下应该执行什么样的动作
期望折扣回报（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}$ - $\gamma \in [0,1]$：折扣因子 - 习惯性写成$R_{t+1}$，而非$R_t$	评估某个策略的好坏，针对单个trajectory
值函数 / 状态值函数（state-value function）	从状态$s$开始遵循策略$\pi$取得的预期总回报（均值）	$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$：策略$\pi$的状态-值函数	评估某个状态本身的价值，进而反映对应策略的价值
Q函数 / 动作值函数（action-value function）	从状态$s$开始采取动作$a$，之后遵循策略$\pi$取得的预期总回报（均值）	$q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$：策略$\pi$的动作-值函数	评估某个状态下特定动作的价值，注意动作$a$可以不遵循策略$\pi$

贝尔曼方程（Bellman Equation）

基本形式

每个状态$S_t$的值函数，实际上等于按照策略$\pi$行动后的奖励（$R_{t+1}$）加上后一个状态$S_{t+1}$的值函数的折扣值（$\gamma G_{t+1}$），也就是即时奖励（immediate reward）和未来奖励（future rewards）的和。这种思想叫做Bootstrapping（自举法），对应的公式就是贝尔曼方程：
$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & =\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })],\forall s\in \mathcal{S}\end{array}$$

贝尔曼方程描述了不同状态之间的值函数的关系。给定策略后求解贝尔曼方程的过程 也称之为策略评估（Policy Evaluation）。
比如有两个策略${\pi }_1$和${\pi }_2$，如果对于任何$s\in \mathcal{S}$，$v_{{\pi }_1}(s)\ge v_{{\pi }_2}(s)$都成立，那么可以认为${\pi }_1$优于${\pi }_2$。

矩阵-向量形式

贝尔曼方程也可以转化为矩阵-向量形式：
$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$

• 状态向量：$v_{\pi }=[v_{\pi }(s_1),\cdots ,v_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• 奖励向量：$r_{\pi }=[r_{\pi }(s_1),\cdots ,r_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• 状态转移矩阵：$P_{\pi }\in {\mathbb{R}}^{n\times n}$，其中$[P_{\pi }{]}_{ij}=p_{\pi }(s_j|s_i)$

*四个状态时的示例：

迭代求解

$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$
先假设一个$v_k$的值，基于该值计算出$v_{k+1}$，进而重复该过程不断计算出$v_{k+2},v_{k+3},\cdots$。
可以证明，当$k\to \infty$时，$v_k$会收敛到$v_{\pi }$。

状态值 vs. 动作值

$v_{\pi }(s)={\sum }_a\pi (a|s)q_{\pi }(s,a)$
状态值可以看作是策略$\pi$的每个动作值的加权平均。

$q_{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$
动作值可以通过状态值求解，也可以不依赖于状态值求解。

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

RL的目标是最大化累计奖励，则必然存在至少一个最优策略，记作${\pi }_{\ast }$，其对任意策略$\pi$都满足：$v_{{\pi }_{\ast }}(s)\ge v_{\pi }(s),\forall s\in \mathcal{S}$。

基本形式

最优策略共享相同的最优状态值$v_{\ast }$与最优动作值$a_{\ast }$。寻找最优策略相当于求贝尔曼方程（$v_{\pi }$、$a_{\pi }$）的最优解（${\max }_{\pi }$），则贝尔曼最优方程为：
$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{\pi }{\max }{v}_{\pi }(s)\\ & =\underset{\pi }{\max }\sum _a\pi (a|s)q_{\pi }(s,a)\end{array}$$
$$\begin{array}{rl}{q}_{\ast }(s,a)& =\underset{\pi }{\max }{q}_{\pi }(s,a)\\ & =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]\end{array}$$

对应的矩阵-向量形式：
$v={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$

贝尔曼最优方程是一个特殊的贝尔曼方程，即当策略$\pi$为最优策略${\pi }_{\ast }$时的贝尔曼方程：
${\pi }_{\ast }={\mathrm{argmax}}_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_{\ast })$
$v_{\ast }=(r_{{\pi }_{\ast }}+\gamma P_{{\pi }_{\ast }}{v}_{\ast })$

注意：

• 最优状态值唯一，但最优策略并不唯一
• 对于一个给定系统，其最优状态值和最优策略受奖励值$r$与折扣因子$\gamma$的影响
  • 最优策略不受奖励值的绝对大小影响，但受其相对大小影响
  • 折扣因子越小（接近0），策略越短视，反之（接近1）策略越长远

迭代求解

考虑贝尔曼最优方程的矩阵-向量形式，设$f(v)={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$，则贝尔曼最优方程可以写作：$v=f(v)$。

• 其中$f(v)$为向量，$[f(v){]}_s={\max }_{\pi }{\sum }_a\pi (a|s)q(s,a),\forall s\in \mathcal{S}$

基于压缩映射定理（contraction mapping theorem）可知，$v=f(v)$的解（即最优状态值$v_{\ast }$）存在且唯一。可以通过迭代的方式进行求解，即：
$v_{k+1}={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_k)$，其中$k=0,1,2,\cdots$
可以证明，当$k\to \infty$时，$v_k\to v_{\ast }$。

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

• 对于任意一个状态$s\in \mathcal{S}$，估计当前的状态值为$v_k(s)$
• 对于任意一个动作$a\in \mathcal{A}(s)$，计算$q_k(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_k(s^{\prime })]$
  • $v_k(s^{\prime })$在第一次迭代时取初始值，后续迭代时使用前一轮迭代中更新后的值
• 计算状态s下的确定性贪婪策略${\pi }_{k+1}(a|s)=\{\begin{array}{ll}1& a=a_k^{\ast }(s)\\ 0& a\ne a_k^{\ast }(s)\end{array}$
  • $a_k^{\ast }(s)={\mathrm{argmax}}_a{q}_k(s,a)$，表示使得当前状态动作值最大的那个动作
• 计算$v_{k+1}(s)={\max }_a{q}_k(s,a)$，继续下一轮迭代
  • $v_{k+1}(s)$实际上就是上一步的最优动作对应的动作值（因为当前策略下其他动作的概率均为0）

在实际应用中，当$\Vert v_{k+1}(s)-v_k(s)\Vert$低于某个阈值（如0.001）之后，就可以认为算法收敛了。

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

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

参考：

• 非常神奇的数学结论有哪些？ - 知乎
• Chapter 3: The Contraction Mapping Theorem - UC Davis Math
• 巴拿赫不动点定理 - 维基百科

直观认识：
将世界地图放在一个桌子上，则该桌子上必有一点，其实际位置会和地图上该点的对应位置重合，该点称之为“不动点（fixed point）”。
将该点的实际位置视作变量$x$，其在地图上的位置视作函数$f(x)$，则$f(x)$可以视作对于$x$的一种“压缩映射”，$f(x)=x$的解即为不动点。

数学描述：
若$\Vert f(x_1)-f(x_2)\Vert \le \gamma \Vert x_1-x_2\Vert$（其中$\gamma \in (0,1)$），则$f$为关于$x$的压缩映射。

• 此处$f(x)$与$x$均为向量，$\Vert \cdot \Vert$为向量范数（vector norm）
• 例如：$f(x)=0.5x$，取$\gamma =0.6$则上式成立。

压缩映射定理是指，若$f$为压缩映射，则必然存在（exist）一个不动点$x^{\ast }$使得$f(x^{\ast })=x^{\ast }$，且$x^{\ast }$唯一（unique）。

求解算法：迭代式算法
对于迭代序列$x_{k+1}=f(x_k)$，随着$k\to \infty$，该序列指数收敛至$x^{\ast }$。

• 例如：以迭代式算法求$f(x)=0.5x$的不动点，假设$x_0=10$，则可迭代得到：$x_1=5,x_2=2.5,x_3=1.25,\cdots$，最终会逼近于0。