马尔科夫决策过程

1.1 随机过程

1.1.1 概率论的公理化

见笔记：概率论的公理化.

了解即可，不要求掌握.

1.1.2 随机过程的概念

见笔记：随机过程的概念.

了解什么是随机过程即可，概率特征不需要掌握.

1.1.3 随机过程的分类

见笔记：随机过程的分类.

不看也没关系，独立增量过程、马尔可夫过程、计数过程后面都会重新提到.

1.2 马尔科夫过程

1.2.1 基本概念

见笔记：马尔科夫过程、马尔科夫链.

备注

• 若随机过程 $\{X(t),t\in T\}$$\Bqty{X(t), t \in T}$ 满足无后效性, 则称为 马尔科夫过程.

  • 若时间空间 $T$$T$ 为有限集或可列集, 则称为 马尔科夫链 (如伯努利过程).

  • 若时间空间 $T$$T$ 为连续集, 则称为 连续参数马尔科夫链. (如泊松过程).

  • 若时间空间 $T=[0,+\mathrm{\infty })$$T = \bpqty{0, +\infty}$, 则称为 扩散过程 (如布朗运动).

• 对于马尔科夫链, 我们只研究 $T=\mathbb{N}$$T = \N$ 的情况, 即 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$.

  • 一步转移概率 为 $p_{ij}(n):=P\{X_{n+1}=j\mid X_n=i\}$$p_{ij}(n) := P\Bqty{X_{n+1} = j \mid X_n = i}$,

  • 若一步转移概率与时间无关, 即 $p_{ij}(n)=p_{ij}$$p_{ij}(n) = p_{ij}$, 则称为 齐次马氏链.

  • 以后我们只研究齐次马氏链的情况, $\mathit{P}=(p_{ij})$$\bm P = (p_{ij})$ 称为 概率转移矩阵.

• 对于无后效性的说明,

  • $P\{X_{n+1}\mid X_n,X_{n-1}\}=P\{X_{n+1}\mid X_n\}$$P\Bqty{X_{n+1} \mid X_n, X_{n-1}} = P\Bqty{X_{n+1} \mid X_n}$.

  • 可证 $P\{X_{n+1}\mid X_n\}$$P\Bqty{X_{n+1} \mid X_n}$ 与 $P\{X_{n-1}\mid X_n\}$$P\Bqty{X_{n-1} \mid X_n}$ 独立.

  • 但是 $P\left\{X_{n+1}\right\}$$P\Bqty{X_{n+1}}$ 与 $P\left\{X_{n-1}\right\}$$P\Bqty{X_{n-1}}$ 不一定独立.

• 马尔科夫链的状态空间 $S$$S$ 一般为 $\mathbb{N}$$\N$ 或其子集.

1.2.2 CK 方程

定义 称 $p_{ij}^{(m)}=P\{X_{n+m}=j\mid X_n=i\}$$p_{ij}^{(m)} = P\Bqty{X_{n + m} = j \mid X_n = i}$ 为 $m$$m$ 步转移概率, ${\mathit{P}}^{(m)}=(p_{ij}^{(m)})$$\bm P^{(m)} = (p_{ij}^{(m)})$ 为 $m$$m$ 步转移概率矩阵. 约定 $p_{ii}^{(0)}=0$$p_{ii}^{(0)} = 0$.

定理 (Chapman-Kolmogorov 方程)

推论 $\mathrm{\forall }n\in {\mathbb{N}}^{+}:{\mathit{P}}^{(n)}={\mathit{P}}^{(n-1)}{\mathit{P}}^{(1)}={\left({\mathit{P}}^{(1)}\right)}^n={\mathit{P}}^n$$\forall n \in \N^+ \colon \bm P^{(n)} = \bm P^{(n-1)} \bm P^{(1)} = \pqty{\bm P^{(1)}}^n = \bm P^n$.

1.2.3 极限概率

定义 马氏链的概率分布向量定义为

并称 $\mathit{\pi }(0)$$\bm \pi(0)$ 为马氏链的 初始分布.

备注 $\mathit{\pi }(n)=\mathit{\pi }(0){\mathit{P}}^n$$\bm \pi(n) = \bm \pi(0) \bm P^n$.

定义 若定义在 $S$$S$ 上的概率分布 $\mathit{\pi }=\{{\pi }_1,{\pi }_2,\cdots \}$$\bm \pi = \Bqty{\pi_1, \pi_2, \cdots}$ 满足 $\mathit{\pi }=\mathit{\pi }\mathit{P}$$\bm \pi = \bm \pi \bm P$, 即

则称为马氏链的 平稳分布 (或不变概率测度).

备注

• 于是平稳分布满足 $\mathit{\pi }=\mathit{\pi }{\mathit{P}}^n$$\bm \pi = \bm \pi \bm P^n$.

• 平稳分布可能不存在, 存在也不一定唯一.

定义 若 $\underset{n\to \mathrm{\infty }}{lim}\mathit{\pi }(n)={\mathit{\pi }}^{\ast }$$\nlim \bm \pi(n) = \bm \pi^*$ 存在, 则称 ${\mathit{\pi }}^{\ast }$$\bm \pi^*$ 为马氏链的 极限分布.

备注

• 若 极限概率 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{P}}^n$$\nlim \bm P^n$ 存在, 则极限分布 $\underset{n\to \mathrm{\infty }}{lim}\mathit{\pi }(n)=\mathit{\pi }(0)\underset{n\to \mathrm{\infty }}{lim}{\mathit{P}}^n$$\nlim \bm \pi(n) = \bm \pi(0) \nlim \bm P^n$ 存在.

• 极限分布是平稳分布, 即 ${\mathit{\pi }}^{\ast }=\underset{n\to \mathrm{\infty }}{lim}\mathit{\pi }(0){\mathit{P}}^n=\underset{n\to \mathrm{\infty }}{lim}\mathit{\pi }(0){\mathit{P}}^{(n+1)}={\mathit{\pi }}^{\ast }\mathit{P}$$\bm \pi^* = \nlim \bm \pi(0) \bm P^n = \nlim \bm \pi(0) \bm P^{(n+1)} = \bm \pi^* \bm P %= \bm \pi^* \bm P^n$.

• 平稳分布不一定是极限分布. 极限分布若存在则唯一, 而平稳分布则不然.

定理 不可约遍历链有如下性质

1. 极限概率存在, 且 $\underset{n\to \mathrm{\infty }}{lim}{p}_{ij}^{(n)}$$\nlim p_{ij}^{(n)}$ 与 $i$$i$ 无关.

2. 平稳分布唯一存在, 且 $\mathrm{\forall }i,j\in S:{\pi }_j=\underset{n\to \mathrm{\infty }}{lim}{p}_{ij}^{(n)}$$\forall i, j \in S \colon \pi_j = \nlim p_{ij}^{(n)} %= \dfrac{1}{\mu_i}$.

备注

• 于是联立 $\mathrm{\forall }j\in S:{\pi }_j={\displaystyle \sum _{i\in S}{\pi }_i{p}_{ij}}$$\forall j \in S \colon \pi_j = \dsum_{i \in S} \pi_i p_{ij}$ 与 ${\displaystyle \sum _{i\in S}{\pi }_i=1}$$\dsum_{i \in S} \pi_i = 1$ 即可求得极限概率.

• 不可约遍历链的定义、定理的证明、更多的性质可参考马尔科夫链笔记.

1.3 马尔科夫奖励过程

1.3.1 基本概念

这里重新表述马尔科夫过程, 并引入马尔科夫奖励过程:

• 马尔可夫过程 $⟨\mathcal{S},\mathcal{P}⟩$$\aqty{\cal S, \bm{\cal P}}$.

  • 简称 MP, 即 Markov Process.

  • $\mathcal{S}\subseteq \mathbb{N}$$\cal S \subseteq \N$ 是状态空间, $S_t\in \mathcal{S}$$S_t \in \cal S$ 表示 $t$$t$ 时刻的状态.

  • $\mathcal{P}$$\bm{\cal P}$ 是状态转移概率矩阵, ${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[S_{t+1}=s^{\prime }\mid S_t=s]$$\cal P_{ss'} = \bb P\bqty{S_{t+1} = s' \mid S_t = s}$.

  • 状态的 轨迹 $\tau =\{s_1,s_2,\cdots \}$$\tau = \Bqty{s_1, s_2, \cdots}$ 即固定事件下随机过程的样本.

• 马尔科夫决策过程 $⟨\mathcal{S},\mathcal{P},\mathcal{R},\gamma ⟩$$\aqty{\cal S, \cal P, \cal R, \gamma}$.

  • 简称 MRP, 即 Markov Reward Process.

  • 在 $⟨\mathcal{S},\mathcal{P}⟩$$\aqty{\cal S, \bm{\cal P}}$ 的基础上, 这里的 $\mathcal{S}$$\cal S$ 是有限集.

  • $\mathcal{R}$$\cal R$ 称为回报或者奖励, $R_t$$R_t$ 是 $t$$t$ 时刻的 立即奖励.

  • ${\mathcal{R}}_s=\mathbb{E}[R_{t+1}\mid S_t=s]$$\cal R_s = \bb E\bqty{R_{t+1} \mid S_t = s}$ 是状态 $s$$s$ 的奖励函数, 或称 状态奖励.

1.3.2 整体回报与值函数

• 整体回报

  • 常数 $\gamma \in [0,1]$$\gamma \in [0, 1]$ 称为 折扣因子.

  • 整体回报 $G_t={\displaystyle \sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}}$$G_t = \dsum_{k=0}^\infty \gamma^k R_{t + k \color{red}+ 1}$ 又称为长期回报.

  • $\gamma$$\gamma$ 表示整体回报中未来奖励的权重. 其余解释见 PPT 或教材.

• 值函数 (状态值函数)

  • 值函数 $v(s)=\mathbb{E}[G_t\mid S_t=s]$$v(s) = \bb E\bqty{G_t \mid S_t = s}$ 是整体回报的条件期望.

  • $v(s)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots \mid S_t=s]$$v(s) = \bb E\bqty{R_{t+1} + \gamma R_{t+2} + \cdots \mid S_t = s}$. (对回报和轨迹的期望)

  • $v(s)=\mathbb{E}[{\mathcal{R}}_{S_t}+\gamma {\mathcal{R}}_{S_{t+1}}+{\gamma }^2{\mathcal{R}}_{S_{t+2}}+\cdots \mid S_t=s]$$v(s) = \bb E\bqty{\cal R_{S_t} + \gamma \cal R_{S_{t+1}} + \gamma^2 \cal R_{S_{t+2}} + \cdots \mid S_t = s}$.(对轨迹的期望)

1.3.2 贝尔曼方程

• $v(s)=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})\mid S_t=s]$$v(s) = \bb E\bqty{R_{t + 1} + \gamma v(S_{t + 1}) \mid S_t = s}$.

• $v(s)={\mathcal{R}}_s+\gamma {\displaystyle \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}v(s^{\prime })}$$v(s) = \cal R_s + \gamma \dsum_{s' \in S} \cal P_{ss'} v(s')$.

• $\left[\begin{array}{c}v(1)\\ ⋮\\ v(n)\end{array}\right]=\left[\begin{array}{c}{\mathcal{R}}_1\\ ⋮\\ {\mathcal{R}}_n\end{array}\right]+\gamma \left[\begin{array}{ccc}{\mathcal{P}}_{11}& \cdots & {\mathcal{P}}_{1n}\\ ⋮& & ⋮\\ {\mathcal{P}}_{11}& \cdots & {\mathcal{P}}_{nn}\end{array}\right]\left[\begin{array}{c}v(1)\\ ⋮\\ v(n)\end{array}\right]$$\begin{bmatrix} v(1) \\ \vdots \\ v(n) \end{bmatrix} = \begin{bmatrix} \cal R_1 \\ \vdots \\ \cal R_n \end{bmatrix} + \gamma \begin{bmatrix} \cal P_{11} & \cdots & \cal P_{1n} \\ \vdots & & \vdots \\ \cal P_{11} & \cdots & \cal P_{nn} \end{bmatrix} \begin{bmatrix} v(1) \\ \vdots \\ v(n) \end{bmatrix}$.

• $\mathit{v}=\mathcal{R}+\gamma \mathcal{P}\mathit{v}=(\mathit{I}-\gamma \mathcal{P}{)}^{-1}\mathcal{R}$$\bm v = \bm{\cal R} + \gamma \bm{\cal P} \bm v = (\bm I - \gamma \bm{\cal P})\inv \bm{\cal R}$.

1.4 马尔科夫决策过程

1.4.1 基本概念

马尔科夫决策过程 $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$$\aqty{\cal S, \cal A, \cal P, \cal R, \gamma}$ 简称 MDP, 即 Markov Decision Process.

在马尔科夫奖励过程的基础上, 每次进入一个状态 $s\in \mathcal{S}$$s \in \cal S$ 后, 执行动作 (行为) $a\in \mathcal{A}$$a \in \cal A$ 后进入下一个状态.

• $\mathcal{A}\subset \mathbb{N}$$\cal A \subset \N$ 是有限的行为集合.

  • ${\mathcal{P}}_{s{s}^{\prime }}^a=P\{S_{t+1}=s^{\prime }\mid S_t=s,A_t=a\}$$\cal P_{ss'}^a = P\Bqty{S_{t + 1} = s' \mid S_t = s, A_t = a}$.

  • ${\mathcal{R}}_s^a=E\{R_{t+1}\mid S_t=s,A_t=a\}$$\cal R_s^a = E\Bqty{R_{t + 1} \mid S_t = s, A_t = a}$.

• 策略 $\pi$$\pi$ 给出了任一状态下采取行为的概率分布.

  • 这里的策略 $\pi$$\pi$ 与之前提到的初始分布等没有任何关系.

  • $\pi (a\mid s)=P\{A_t=a\mid S_t=s\}$$\pi(a \mid s) = P\Bqty{A_t = a \mid S_t = s}$. (概率分布)

  • $\pi (s)$$\pi(s)$ 表示在 $s$$s$ 状态下可能采取的行为的集合.

  • ${\mathcal{P}}_{s{s}^{\prime }}^{\pi }={\displaystyle \sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{P}}_{s{s}^{\prime }}^a}$$\cal P_{ss'}^\pi = \dsum_{a \in \cal A} \pi(a \mid s) \cal P_{ss'}^a$. (即全概率公式)

  • ${\mathcal{R}}_s^{\pi }={\displaystyle \sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{R}}_s^a}$$\cal R_s^\pi = \dsum_{a \in \cal A} \pi(a \mid s) \cal R_s^a$. (即 $\mathbb{E}\left[X\right]=\mathbb{E}\left[\mathbb{E}[X\mid Y]\right]$$\bb E\bqty{X} = \bb E\bqty{\bb E\bqty{X \mid Y}}$)

1.4.2 值函数与贝尔曼期望方程

状态值函数的定义与结论马尔科夫奖励过程的相同.

• 状态值函数

  • $v_{\pi }(s):=E_{\pi }[G_t\mid S_t=s]$$v_\pi(s) := E_\pi\bqty{G_t \mid S_t = s}$.

  • $v_{\pi }(s)=E_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s]$$v_\pi(s) = E_\pi\bqty{R_{t+1} + \gamma v_\pi(S_{t + 1}) \mid S_t = s}$.

  • ${\mathit{v}}_{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{\mathit{v}}_{\pi }={(\mathit{I}-\gamma {\mathcal{P}}^{\pi })}^{-1}{\mathcal{R}}^{\pi }$$\bm v_\pi = \bm{\cal R}^\pi + \gamma \bm{\cal P}^\pi \bm v_\pi = \pqty{\bm I - \gamma \bm{\cal P}^\pi}\inv \bm{\cal R}^\pi$.

• 行为值函数

  • $q_{\pi }(s,a):=E_{\pi }[G_t\mid S_t=s,A_t=a]$$q_\pi(s, a) := E_\pi\bqty{G_t \mid S_t = s, A_t = a}$.

  • $q_{\pi }(s,a)=E_{\pi }[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]$$q_\pi(s, a) = E_\pi\bqty{R_{t + 1} + \gamma q_\pi(S_{t + 1}, A_{t + 1}) \mid S_t = s, A_t = a}$.

• 由 $\mathbb{E}\left[X\right]=\mathbb{E}\left[\mathbb{E}[X\mid Y]\right]$$\bb E\bqty{X} = \bb E\bqty{\bb E\bqty{X \mid Y}}$ 得到相互关系:

  • $v_{\pi }(s)={\displaystyle \sum _{a\in \mathcal{A}}\pi (a\mid s)q_{\pi }(s,a)}$$v_\pi(s) = \dsum_{a \in \cal A} \pi(a \mid s) q_\pi(s, a)$.

  • $q_{\pi }(s,a)={\mathcal{R}}_s^a+\gamma {\displaystyle \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })}$$q_\pi(s, a) = \cal R_s^a + \gamma \dsum_{s' \in \cal S} \cal P_{ss'}^a v_\pi(s')$.

• 于是代入即得

  • $v_{\pi }(s)={\displaystyle \sum _{a\in \mathcal{A}}\pi (a\mid s)({\mathcal{R}}_s^a+\gamma {\displaystyle \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })})}$$v_\pi(s) = \dsum_{a \in \cal A} \pi(a \mid s) \pqty{ \cal R_s^a + \gamma \dsum_{s' \in \cal S} \cal P_{ss'}^a v_\pi(s') }$. (不包含行为值函数的方程)

  • $q_{\pi }(s,a)={\mathcal{R}}_s^a+\gamma {\displaystyle \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{\displaystyle \sum _{a^{\prime }\in \mathcal{A}}\pi (a^{\prime }\mid s^{\prime })q_{\pi }(s^{\prime },a^{\prime })}}$$q_\pi(s, a) = \cal R_s^a + \gamma \dsum_{s' \in \cal S} \cal P_{ss'}^a \dsum_{a' \in \cal A} \pi(a' \mid s') q_\pi(s', a')$. (不包含状态值函数的方程)

以上除定义之外均称为贝尔曼期望方程, 其中以最后两个公式最为重要.

1.4.3 最优值函数与贝尔曼最优方程

• 最优值函数

  • 最优状态值函数 ${\displaystyle v_{\ast }(s):=\underset{\pi }{max}{v}_{\pi }(s)}$$\d v_*(s) := \max\limits_\pi v_\pi(s)$.

  • 最优行为值函数 $q_{\ast }(s,a):={\displaystyle \underset{\pi }{max}{q}_{\pi }(s,a)}$$q_*(s, a) := \d\max_\pi q_\pi(s, a)$.

• 相互关系

  • 最优状态值函数 $v_{\ast }(s)=\underset{a}{max}{q}_{\ast }(s,a)$$v_*(s) = \max\limits_a q_*(s, a)$.

  • 最优行为值函数 $q_{\ast }(s,a)={\mathcal{R}}_s^a+\gamma {\displaystyle \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })}$$q_*(s, a) = \cal R_s^a + \gamma \dsum_{s' \in \cal S} \cal P_{ss'}^a v_*(s')$.

• 代入即得

  • ${\displaystyle v_{\ast }(s)=\underset{a}{max}({\mathcal{R}}_s^a+\gamma {\displaystyle \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })})}$$\d v_*(s) = \max_a \pqty{ \cal R_s^a + \gamma \dsum_{s' \in \cal S} \cal P_{ss'}^a v_*(s') }$. (不包含最优行为值函数的方程)

  • $q_{\ast }(s,a)={\mathcal{R}}_s^a+\gamma {\displaystyle \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a\underset{a^{\prime }}{max}{q}_{\ast }(s^{\prime },a^{\prime })}$$q_*(s, a) = \cal R_s^a + \gamma \dsum_{s' \in \cal S} \cal P_{ss'}^a \max\limits_{a'} q_*(s', a')$. (不包含最优状态值函数的方程)

    这两个公式最为重要.

• 最优策略 ${\pi }_{\ast }$$\pi_*$ 即使得状态值函数最大的策略.

  最优策略及以下表达式了解即可.

  • $v_{{\pi }_{\ast }}(s)=v_{\ast }(s)$$v_{\pi_*}(s) = v_*(s)$.

  • $q_{{\pi }_{\ast }}(s,a)=q_{\ast }(s,a)$$q_{\pi_*}(s, a) = q_*(s, a)$.

  • ${\pi }_{\ast }(a\mid s)=\mathbb{I}\{a=\underset{a\in \mathcal{A}}{\mathrm{argmax}}{q}_{\ast }(s,a)\}$$\pi_*(a \mid s) = \bb I\Bqty{a = \argmax{a \in \cal A} q_*(s, a)}$.

  • 其中示性函数 $\mathbb{I}\left\{A\right\}$$\bb I\Bqty{A}$ 在 $A$$A$ 发生 (或为真) 时为 1, 其余情况为 0.