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

---

参考资料：

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

本文大部分内容来自西湖大学赵世钰老师的强化学习的数学原理课程（参考资料1），并参考了部分参考资料2、3的内容进行补充。

系列博文索引：

• 强化学习的数学原理学习笔记 - RL基础知识
• 强化学习的数学原理学习笔记 - 基于模型（Model-based）

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

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}+?={\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 })],?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),?,v_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• 奖励向量：$r_{\pi }=[r_{\pi }(s_1),?,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},?$。
可以证明，当$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 }_{?}$，其对任意策略$\pi$都满足：$v_{{\pi }_{?}}(s)\ge v_{\pi }(s),?s\in \mathcal{S}$。

基本形式

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

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

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

注意：

• 最优状态值唯一，但最优策略并不唯一
• 对于一个给定系统，其最优状态值和最优策略受奖励值$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),?s\in \mathcal{S}$

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

通常的求解流程：【实际上就是值迭代（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^{?}(s)\\ 0& a\ne a_k^{?}(s)\end{array}$
  • $a_k^{?}(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 ?\Vert$为向量范数（vector norm）
• 例如：$f(x)=0.5x$，取$\gamma =0.6$则上式成立。

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

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

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