【笔记】强化学习的数学原理

分享一下学习这门课程时的笔记

$\S 1$ 基本概念

State: 智能体的状态。State space: $S={si}^9{i=1}$.

Action: 可进行的动作。Action space of a state: 与 $si$有关的集合。$A(s_i)={a_k}^5{k=1}$.

State transition: 进行动作后，智能体从一个状态转移到另一个状态的过程。State transition probability: $p(s_i|s_j,a_k)=\text{prob}$.

Policy: 指导智能体在某一状态下采取某一措施。数学表示：条件概率 $\pi(a_i|s_j)=\text{prob}.$

Reward: 在做出一个动作后得到的一个标量。正为鼓励，负为惩罚。数学表示 $p(r=c|s_i,a_j)=\text{prob}.$

Trajectory: 一条 state-action-reward 链。

Return: 一条路径的reward的和。

Discounted rate: $\gamma \in (0,1)$, discounted return = $\sum_{i=0}^{\infty}\gamma^ir_i$，$\gamma$ 越小，智能体越近视，反之越远视。

Episode: 从开始到结束的trajectory。

到达目标后如何停下来？将目标状态视为一种一般状态并制定一种策略，使得智能体仍可离开目标状态，并在进入目标状态时获得$r = +1$的奖励。我们无需将目标状态与其他状态区分开来，可将其视为一种正常状态。

Markov decision process (MDP)

MDP的要素：

1. 集合（Sets）: State$S$, Action$A(s)$, Reward$R(s,a)$

2. 概率分布（Probability distribution）：

   状态转移概率（State transition probability）: 在state $s$, 选择action $a$, 转移到state $s’$ 的概率记为$p(s’|s,a)$.

   奖励概率（Reward probability）: 在state $s$, 选择action $a$, 得到奖励 $r$ 的概率记为 $p(r|s, a)$.

3. 策略（Poicy）: 在state$s$，选择action $a$ 的可能性$\pi(a|s)$.

MDP性质：memoryless property 与历史无关

$$\begin{align} p(s_{t+1}|a_{t+1},s_t,...,a_1,s_0)=p(s_{t+1}|a_{t+1},s_t)\\ p(r_{t+1}|a_{t+1},s_t,...,a_1,s_0)=p(r_{t+1}|a_{t+1},s_t) \end{align}$$

当Policy确定时，马尔科夫随机过程变成马尔科夫过程。

$\S 2$ 贝尔曼公式

计算return的方法

使用$v_i$表示从$s_i$出发的return。

例：

直接用定义计算：

$$\begin{align} &v_1=r_1+\gamma r_2+\gamma^2r_3+...\\ &v_2=r_2+\gamma r_3+\gamma^2r_4+...\\ &... \end{align}$$

使用Bootstrapping（自举法）:

$$\begin{align} &v_1=r_1+\gamma (r_2+\gamma r_3+...)&=r_1+\gamma v_2\\ &v_2=...&=r_2+\gamma v_3\\ &v_3=...&=r_3+\gamma v_4\\ &v_4=...&=r_4+\gamma v_1 \end{align}$$

将上式转化成矩阵形式：

$$\underbrace{\left[\begin{array}{c}v_{1}\\ v_{2}\\ v_{3}\\ v_{4}\end{array}\right]}_{\mathbf{v}} = \left[\begin{array}{c}r_{1}\\ r_{2}\\ r_{3}\\ r_{4}\end{array}\right] + \left[\begin{array}{c}\gamma v_{2}\\\gamma v_{3}\\\gamma v_{4}\\\gamma v_{1}\end{array}\right] = \underbrace{\left[\begin{array}{c}r_{1}\\ r_{2}\\ r_{3}\\ r_{4}\end{array}\right]}_{\mathbf{r}} + \gamma\underbrace{\left[\begin{array}{cccc}0 &1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0\end{array}\right]}_{\mathbf{P}} \underbrace{\left[\begin{array}{c}v_{1}\\ v_{2}\\ v_{3}\\ v_{4}\end{array}\right]}_{\mathbf{v}}$$

化简得到贝尔曼公式的特殊形式：

$$\mathbf{v} = \mathbf{r} + \gamma\mathbf{P}\mathbf{v}$$

求解：

$$\mathbf{v}=(I-\gamma\mathbf{P})^{-1}\mathbf{r}$$

核心思想：一个状态的value依赖其它状态的value。

State value

首先引入一些符号：

单步过程分析

考虑以下单步过程：

$$S_t \xrightarrow{A_t} R_{t + 1}, S_{t + 1}$$

关键要素

• 时间点：
  $t, t + 1$ 为离散时间点
• 状态：
  $S_t$ 表示 $t$ 时刻的状态
• 动作：
  $A_t$ 表示在状态 $S_t$ 下采取的动作
• 奖励：
  $R_{t + 1}$ 表示采取动作 $A_t$ 后获得的即时奖励
• 转移状态：
  $S_{t + 1}$ 表示执行动作 $A_t$ 后转移到的下一状态

注意：$St$、$A_t$、$R{t + 1}$ 均为随机变量。

概率控制模型

该过程由以下概率分布控制：

1. 策略函数： $\pi(A_t = a \mid S_t = s)$ 控制从状态 $S_t$ 选择动作 $A_t$ 的策略
2. 奖励函数：$p(R{t + 1} = r \mid S_t = s, A_t = a)$ 控制状态-动作对 $(S_t, A_t)$ 生成奖励 $R{t + 1}$ 的概率
3. 状态转移函数：$p(S{t + 1} = s’ \mid S_t = s, A_t = a)$控制从 $(S_t, A_t)$ 转移到下一状态 $S{t + 1}$ 的动态特性

假设：当前已知所有概率分布（即已知模型）。

多步动态过程可表示为：

$$S_{t}\xrightarrow{A_{t}} R_{t+1},S_{t+1}\xrightarrow{A_{t+1}} R_{t+2},S_{t+2}\xrightarrow{A_{t+2}} R_{t+3},\ldots$$

折扣回报 $G_t$ 的定义：未来奖励的加权和

$$G_{t} = R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + \ldots\\ =R_{t+1}+\gamma G_{t+1}$$

$G_t$ 也是随机变量。

State value 的定义： $G_t$的期望

$$v_{\pi}(s)=\mathbb{E}\left[G_{t} \mid S_{t} = s\right]$$

说明：

与策略有关，不同的策略有不同的state value。

return与state value 的区别和联系是：return 针对单个trajectory，而state value针对多个可能的trajectory的return再求平均值。

贝尔曼公式的推导

贝尔曼公式描述了不同状态的state value 之间的关系。

$$\begin{aligned} &v_\pi(s)=\mathbb{E}[G_t|S_t=s]=\mathbb{E}[R_t+\gamma G_{t+1}|S_t=s]\\ &=\mathbb{E}[R_t|S_t=t]+\gamma\mathbb{E}[G_{t+1}|S_t=s]\\ &=\sum_a \pi(a|s)\sum_r p(r|s,a)r+\gamma\sum_a \pi(a|s)\sum _{s'}p(s'|s,a)\mathbb{E}[G_{t+1}|S_{t+1}=s']\\ &=\sum_a \pi(a|s)\left[\sum_r p(r|s,a)r+\gamma \sum_{s'}p(s'|s,a)v_\pi(s')\right] \end{aligned}$$

最后一行即为贝尔曼公式。

贝尔曼公式的矩阵—向量形式

贝尔贝尔曼公式对任意的$s \in S$都成立，这意味着我们有$|S|$个方程，这些方程可以组成线性方程组。

将贝尔曼公式写成如下形式：

$$v_{\pi}(s)=r_{\pi}(s)+\gamma\sum_{s'}p_{\pi}(s'|s)v_{\pi}(s')$$

其中

$$r_{\pi}(s)\triangleq\sum_{a}\pi(a|s)\sum_{r}p(r|s,a)r,\qquad p_{\pi}(s'|s)\triangleq\sum_{a}\pi(a|s)p(s'|s,a)$$

将所有的状态编号为$s_i(i=1,…,n)$

将所有这些状态方程组合在一起，并重写为矩阵-向量形式：

$$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})$，是状态转移矩阵。

直观的例子

如果有4个状态：

$$\underbrace{\left[\begin{array}{l} v_{\pi}(s_{1}) \\ v_{\pi}(s_{2}) \\ v_{\pi}(s_{3}) \\ v_{\pi}(s_{4}) \end{array}\right]}_{v_{\pi}} = \underbrace{\left[\begin{array}{l} r_{\pi}(s_{1}) \\ r_{\pi}(s_{2}) \\ r_{\pi}(s_{3}) \\ r_{\pi}(s_{4}) \end{array}\right]}_{r_{\pi}} + \gamma \underbrace{\left[\begin{array}{llll} p_{\pi}(s_{1}|s_{1}) & p_{\pi}(s_{2}|s_{1}) & p_{\pi}(s_{3}|s_{1}) & p_{\pi}(s_{4}|s_{1}) \\ p_{\pi}(s_{1}|s_{2}) & p_{\pi}(s_{2}|s_{2}) & p_{\pi}(s_{3}|s_{2}) & p_{\pi}(s_{4}|s_{2}) \\ p_{\pi}(s_{1}|s_{3}) & p_{\pi}(s_{2}|s_{3}) & p_{\pi}(s_{3}|s_{3}) & p_{\pi}(s_{4}|s_{3}) \\ p_{\pi}(s_{1}|s_{4}) & p_{\pi}(s_{2}|s_{4}) & p_{\pi}(s_{3}|s_{4}) & p_{\pi}(s_{4}|s_{4}) \end{array}\right]}_{P_{\pi}} \underbrace{\left[\begin{array}{l} v_{\pi}(s_{1}) \\ v_{\pi}(s_{2}) \\ v_{\pi}(s_{3}) \\ v_{\pi}(s_{4}) \end{array}\right]}_{v_{\pi}}$$

贝尔曼公式的求解

可以直接求逆矩阵，但开销较大。

考虑迭代法：

$$v_{k+1}=r_{\pi}+\gamma P_{\pi}v_k$$

从而得到数列${v_0,v_1,v_2,…}$，且有

$$v_k \to v_{\pi} = (I-\gamma P_{\pi})^{-1}r_{\pi}, k\to \infty$$

Action value

State value：从某个state出发，智能体可以得到的平均return。

Action value：从某个state出发并选择某个action，智能体可以得到的平均return。

引入Action value是为了知道那个action更好。

Action value的定义：

$$q_{\pi}(s,a) = \mathbb{E}[G_t|S_t=s,A_t=a]$$

性质：

$q_{\pi}(s,a)$是关于state-action对$(s,a)$的方程，且由$\pi$决定。

由于

$$\underbrace{\mathbb{E}[G_{t}\mid S_{t}=s]}_{v_{\pi}(s)}=\sum_{a}\underbrace{\mathbb{E}[G_{t}\mid S_{t}=s,A_{t}=a]}_{q_{\pi}(s,a)}\pi(a\mid s)$$

我们得到：

$$v_{\pi}(s)=\sum_{a}\pi(a\mid s)q_{\pi}(s,a) \qquad(1)$$

之前推导的state value表达式为：

$$v_{\pi}(s)=\sum_{a}\pi(a\mid s)\left[\underbrace{\sum_{r}p(r\mid s,a)r+\gamma\sum_{s'}p\left(s^{\prime}\mid s,a\right)v_{\pi}(s^{\prime})}_{q_{\pi}(s,a)}\right] \qquad(2)$$

对比(1)(2)，我们你可以得出action-value的方程：

$$q_{\pi}(s,a)=\sum_{r}p(r\mid s,a)r+\gamma\sum_{s'}p\left(s^{\prime}\mid s,a\right) v_{\pi}(s^{\prime}) \qquad(3)$$

（1）用来从action value推state value。

（3）用来从state value推action value。

总结

为什么需要状态值？因为需要评价一个策略的好坏。

怎么得到状态值？求解贝尔曼方程。

为什么要关注不被策略$\pi$选择的动作的价值？因为策略$\pi$不一定最好，我们要关注所有的动作，来探索更优的策略。

$\S 3$ 最优状态值与贝尔曼最优方程

引入

强化学习的最终目标：寻找最优策略。

本章的核心概念：最优状态值。基于最优状态值可以定义最优策略。

本章的核心工具：贝尔曼最优方程。可以用来求解最优状态值和最优策略。贝尔曼最优方程是一个特殊的贝尔曼方程。

最优策略（optimal policy）与最优状态值

定义：对于策略$\pi ^$，若对任意状态$s\in S$ 和其他任意的策略$\pi$，都有$v_{\pi^}(s)\ge v_{\pi}(s)$，那么$\pi ^*$是一个最优策略，且其对应的状态是是最优状态值。

贝尔曼最优方程（BOE）

表达式：

$$v(s) = \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s) \left( \sum_{r \in \mathcal{R}} p(r \mid s, a) r + \gamma \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right) \right)$$ $$= \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s) q(s, a),$$

其中

$$q(s, a) \doteq \sum_{r \in \mathcal{R}} p(r \mid s, a) r + \gamma \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right) .$$

这里 $v(s)$, $v\left(s^{\prime}\right)$ 是待求解的未知量；$\pi(s)$ 表示状态 $s$ 的策略；$\Pi(s)$ 是在状态 $s$ 所有可能策略的集合。

（持续更新中）