马尔可夫和贝尔曼公式以及生成模式

一、马尔可夫

环境的状态必须是全部能够获取的（fully observable），即环境的 observation 就是 state。

1. 马尔可夫性（Markov Property）

环境的下一个状态只由当前的的状态决定，与过去无关。

$$\mathbb{P}[S_{t+1}|S_t] = \mathbb{P}[S_{t+1} | S_1, \ldots, S_t]$$

比如下棋，只用关心当前的局面，不用管过去操作。

2. 状态转移矩阵（State Transition matrix）

环境从一个状态转化成另一个状态的概率组成的矩阵。

$$P_{ss\prime} = \mathbb{P}[S_{t+1}=s\prime | S_t=s] \tag{2}$$

公式2 表示马尔可夫状态 $s$ 转移到其后继状态 $s\prime$ 的概率为 $P_{ss\prime}$，而状态转移矩阵则表示对于所有状态转移到其所有后继状态的概率，如下：

$$P = \left[ \begin{matrix} P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \\ \end{matrix} \right]$$

$P$ 中任意行的值的和为1。

3. 马尔可夫过程（Markov Process, MP）

若环境状态变化的过程满足马尔可夫性，则称为马尔可夫过程。马尔可夫过程（或者马尔可夫链）由一个二元组 $\lt S, P \gt$ 定义。其中：

• $S$ 表示环境所有可能状态的有限集合
• $P$ 表示这些状态之间转移概率的矩阵 $P_{ss\prime} = \mathbb{P}[S_{t+1}=s\prime | S_t=s]$

4. 马尔可夫链（Markov Chain）

马尔可夫过程下产生的有限状态的集合。

5. 马尔科夫回报过程（Markov Reward Process, MRP）

包含 价值（values） 的马尔可夫链就是马尔科夫回报过程，由一个四元组 $\lt S, P, R, \gamma \gt$ 定义。其中：

• $S$ 表示环境所有可能状态的有限集合
• $P$ 表示这些状态之间转移概率的矩阵 $P_{ss\prime} = \mathbb{P}[S_{t+1}=s\prime | S_t=s]$
• $R$ 表示回报计算函数 $R_s = \mathbb{E}[R_{t+1} | S_t=s]$
• $\gamma$ 衰减系数（Discount factor），$\gamma \in [0, 1]$

5.1 回报（Return）

从时刻 $t$ 开始所有的折扣回报之和

$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0} ^{\infty} \gamma^k R_{t+k+1}$$

5.2 衰减系数（Discount factor）

存在的原因：

• 数学表达更方便
• 避免陷入循环
• 长远的利益具有不确定性

意义：

• 值越接近0表示越看重当前的利益
• 值越接近1表示越看重长远的利益

5.3 状态价值函数（Value Function）

状态价值函数用于计算从状态 $s$ 开始的期望回报

$$v(s) = \mathbb{E}[G_t | S_t=s]$$

5.4 贝尔曼方程（Bellman Equation）

$$\begin{aligned} v(s) & = \mathbb{E}[G_t | S_t = s] \\ & = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + {\gamma}^2 R_{t+3} + \cdots | S_t = s] \\ & = \mathbb{E}[R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \cdots) | S_t = s] \\ & = \mathbb{E}[R_{t+1} + \gamma G_{t+1} | S_t = s] \\ & (注意 v(S_{t+1}) 是大写的 S_{t+1} 是因为 S_t = s 的下一个状态是随机的) \\ & = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s] \\ & (分别对 R_{t+1} 和 v(S_{t+1}) 求期望，和的期望等于期望的和) \\ & = \mathbb{E}[R_{t+1} | S_t = s] + \gamma \mathbb{E}[v(S_{t+1}) | S_t = s] \\ & (如果已知状态转移矩阵 P ，则可以将上式展开) \\ & = R_s + \gamma \sum_{s\prime \in S} P_{ss\prime} v(s\prime) \\ \end{aligned}$$

即：

$$v(s) = R_s + \gamma \sum_{s\prime \in S} P_{ss\prime} v(s\prime)$$

对应的矩阵形式的方程为：

$$v = R + \gamma Pv$$ $$\left[ \begin{matrix} v(1) \\ \vdots \\ v(n) \\ \end{matrix} \right] = \left[ \begin{matrix} R_{1} \\ \vdots \\ R_{n} \\ \end{matrix} \right] + \gamma \left[ \begin{matrix} P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \\ \end{matrix} \right] \left[ \begin{matrix} v(1) \\ \vdots \\ v(n) \\ \end{matrix} \right]$$

其中 $R_{t+1}$ 是立即回报， $\gamma v(S_{t+1})$ 是后续状态的折扣值函数

5.5 贝尔曼方程的求解方法

1. 直接求解

   $$\begin{aligned} v &= R + \gamma Pv \\ (I - \gamma P)v &= R \\ v &= (I - \gamma P)^{-1} R \\ \end{aligned}$$

   问题：复杂度太高 $O(n^3)$，n为状态的数量

2. 迭代求解

   • 动态规划（Dynamic programming）
   • 蒙地卡罗评估（Monte-Carlo evaluation）
   • 时序差分学习（Temporal-Difference learning）

6. 马尔科夫决策过程（Markov Decision Process, MDP）

包含 决策（decisions） 的马尔科夫回报过程就是马尔科夫决策过程，由一个五元组 $\lt S, A, P, R, \gamma \gt$ 定义。其中：

• $S$ 表示环境所有可能状态的有限集合
• $A$ 表示有限的动作集合
• $P$ 表示这些状态之间转移概率的矩阵 $P_{ss\prime}^a = \mathbb{P}[S_{t+1}=s\prime | S_t=s, A_t=a]$
• $R$ 表示回报计算函数 $R_s^a = \mathbb{E}[R_{t+1} | S_t=s, A_t=a]$
• $\gamma$ 衰减系数（Discount factor），$\gamma \in [0, 1]$

6.1 策略（Policy）

策略 $\pi$ 是状态 $s$ 时可能执行的动作 $a$ 的概率分布

$$\pi (a|s) = \mathbb{P}[A_t=a | S_t=s]$$

当给定马尔科夫决策过程 $\lt S,A,P,R,\gamma \gt$ 和策略 $\pi$ 时：

• 状态序列 $S_1, S_2, \ldots$ 就是一个马尔可夫过程 $\lt S,P^{\pi} \gt$
• 状态回报序列 $S_1, R_2, S_2, \ldots$ 就是一个马尔科夫回报过程 $\lt S, P^{\pi}, R^{\pi}, \gamma \gt$

其中：

$$P_{s,s\prime}^{\pi} = \sum_{a \in A}\pi(a|s) P_{s,s\prime}^a$$ $$R_s^{\pi} = \sum_{a \in A}\pi(a|s) R_s^a$$

6.2 基于策略的状态价值函数

马尔科夫决策过程中，基于策略 $\pi$ 的 状态 价值函数用于计算从状态 $s$ 开始，遵循策略 $\pi$ 时的期望回报

$$v_{\pi}(s) = \mathbb{E}[G_t | S_t=s]$$

6.3 基于策略的动作价值函数

马尔科夫决策过程中，基于策略 $\pi$ 的 动作 价值函数用于计算从状态 $s$ 开始，先采取动作 $a$，再遵循策略 $\pi$ 时的期望回报

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

6.4 贝尔曼期望方程（Bellman Expectation Equation）

1. 基于策略的 状态 价值函数的贝尔曼方程可以分解为 立即回报 与 后续状态的折扣回报 的和

   $$v_{\pi}(s) = \mathbb{E}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s]$$

   对应的矩阵形式的方程为：

   $$v_{\pi} = R^{\pi} + \gamma P^{\pi} v_{\pi}$$ $$v_{\pi} = (I - \gamma P^{\pi})^{-1} R^{\pi}$$

   同时，状态 $s$ 的价值也可以通过计算在遵循策略 $\pi$ 时采取所有可能 动作的价值 与对应 动作发生的概率 乘积的和来获得，即：

   $$v_{\pi}(s) = \sum_{a \in A}\pi(a|s) q_{\pi}(s,a) \tag{6.4.1}$$

2. 基于策略的 动作 价值函数的贝尔曼方程也是类似的

   $$q_{\pi}(s,a) = \mathbb{E}[R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1}) | S_t=s, A_t=a]$$

   类似的，状态 $s$ 下执行动作 $a$ 的价值也可以分解为 离开状态 $s$ 的立即回报 与 所有可能会进入状态的价值与对应进入概率 的乘积的和，即：

   $$q_{\pi}(s,a) = R_s^a + \gamma \sum_{s\prime \in S} P_{ss\prime}^a v_{\pi}(s\prime) \tag{6.4.2}$$

3. 组合上面的 方程6.4.1 和 方程6.4.2 ，可以得到

   $$v_{\pi}(s) = \sum_{a \in A}\pi(a|s) \left( R_s^a + \gamma \sum_{s\prime \in S} P_{ss\prime}^a v_{\pi}(s\prime) \right)$$ $$q_{\pi}(s,a) = R_s^a + \gamma \sum_{s\prime \in S} P_{ss\prime}^a \sum_{a\prime \in A}\pi(a\prime|s\prime) q_{\pi}(s\prime,a\prime)$$

6.5 最优价值函数（Optimal Value Function）

1. 最优状态价值函数（Optimal State-Value Function） 就是从所有可能的策略中，选取 产生最大状态价值函数值的 策略的函数

   $$v_*(s) = \max_{\pi} v_{\pi}(s) \tag{6.5.1}$$

   $v_*(s)$ 是 $v_{\pi_*}(s)$ 的简写，都可以表示最优状态价值函数。

2. 最优动作价值函数（Optimal Action-Value Function） 就是从所有可能的策略中，选取 产生最大动作状态价值函数值的 策略的函数

   $$q_*(s,a) = \max_{\pi} q_{\pi}(s,a) \tag{6.5.2}$$

   $q_*(s,a)$ 是 $q_{\pi_*}(s,a)$ 的简写，都可以表示最优动作价值函数。

3. 最优价值函数能够在马尔科夫决策过程中找到最好的策略。所以，如果我们找到了最优价值函数，那么我们就可以解决马尔科夫决策问题

6.6 最优策略（Optimal Policy）

1. 对于任意可能的状态，如果遵循一个策略的价值总是不差于遵循另一个策略，那么前一个策略就要优于后一个策略

   $$\pi \ge \pi\prime \quad if \; v_{\pi}(s) \ge v_{\pi\prime}(s), \forall{s}$$

2. 定理：对任意马尔科夫决策过程，有：

• 存在一个最优策略 ${\pi}_*$ 不差于其他任何策略

  $${\pi}_* \ge \pi, \forall{\pi}$$

• 所有的最优策略有相同的最优状态价值函数

  $$v_{\pi_*}(s) = v_*(s) \tag{6.6.2a}$$

• 所有的最优策略具有相同的最优动作价值函数

  $$q_{\pi_*}(s,a) = q_*(s,a) \tag{6.6.2b}$$

6.7 寻找最优策略

可以通过最大化最优动作价值函数 $q_*(s,a)$ 来找到最优策略

$$\pi_*(a|s) = \begin{cases} 1 & if \; a = \underset{a \in A}{\operatorname{argmax}} \; q_*(s,a) \\ 0 & otherwise \\ \end{cases} \tag{6.7}$$

• 对任意马尔科夫决策过程，总存在一个确定性的最优策略
• 如果我们知道最优动作价值函数 $q_*(s,a)$ ，则表明我们找到了最优策略

6.8 贝尔曼最优方程（Bellman Optimality Equation）

1. 一个状态的最优价值等于从该状态出发采取的所有动作产生的动作价值中最大的那个动作价值

   $$\begin{aligned} v_*(s) & = v_{\pi_*}(s) & \text{公式6.6.2a} \\ & = \sum_{a \in A}\pi_*(a|s) q_{\pi_*}(s,a) & \text{公式6.4.1} \\ & = \max_a q_{\pi_*}(s,a) & \text{公式6.7} \\ & = \max_a q_*(s,a) & \text{公式6.6.2b} \\ \end{aligned}$$

   即

   $$v_*(s) = \max_a q_*(s,a) \tag{6.8.1}$$

2. 与 方程6.4.2 类似，状态 $s$ 下执行动作 $a$ 的最优价值也可以分解为 离开状态 $s$ 的立即回报 与 所有可能会进入状态的最优状态价值与对应进入概率 的乘积的和，即：

   $$q_*(s,a) = R_s^a + \gamma \sum_{s\prime \in S} P_{ss\prime}^a v_*(s\prime) \tag{6.8.2}$$

3. 组合上面的 方程6.8.1 和 方程6.8.2 ，可以得到

   $$q_*(s,a) = R_s^a + \gamma \sum_{s\prime \in S} P_{ss\prime}^a \max_{a\prime} q_*(s\prime,a\prime)$$ $$v_*(s) = \max_a \left(R_s^a + \gamma \sum_{s\prime \in S} P_{ss\prime}^a v_*(s\prime)\right)$$

6.9 贝尔曼最优方程的求解方法

1. 贝尔曼最优方程是非线性的
2. 贝尔曼最优方程通常没有固定的解决方案
3. 可以通过一些迭代的方法来解决：
   • 价值迭代（Value Iteration）
   • 策略迭代（Policy Iteration）
   • Q-learning
   • Sarsa

6.10 贝尔曼期望方程和贝尔曼最优方程的关系

1. 贝尔曼期望方程中，策略是已知的，求解贝尔曼期望方程就是在评价策略的优劣
2. 贝尔曼最优方程中，策略是未知的，求解贝尔曼最优方程就是在找最优的策略

---

二、生成模式（Generating Patterns）

1. 确定性模式（Deterministic Patterns）

环境的下一个状态可以根据上一个状态计算出来。

比如：过完生日你就长了一岁。

2. 非确定性模式（Non-deterministic patterns）

环境的下一个状态不能根据上一个状态计算出来。

比如：掷骰子。

马尔可夫假设：环境当前的状态仅仅依赖于之前的几个状态。
$n$ 阶马尔可夫模型：环境的下一个状态只由过去的 $n$ 个状态决定，与其他状态无关。

3. 隐藏模式（Hidden Patterns）

隐马尔可夫模型（Hidden Markov Model, HMM）

---

参考：RL Course by David Silver - Lecture 2: Markov Decision Process