- 强化学习基础 (1) 多臂赌博机
- 强化学习基础 (2) 有限马尔可夫过程
- 强化学习基础 (3) 动态规划求解
引言
在本文中，我们将形式化地定义有限马尔可夫过程 (Finite Markov Decision Process) 。在后续的所有内容中，我们都将问题抽象为一个有限MDP。
MDP是线性决策问题的一种经典建模方式。在MDP的每一步中，采取不同的动作不仅对瞬时奖励有影响，也会影响后续的状态。因此，求解一个MDP的最优策略需要在瞬时奖励和未来奖励之间取得较好的平衡。
与赌博机问题不同的是，在MDP中我们需要估计的价值函数是关于动作和状态的函数，即 $q_{*}(s,a)$。这种依赖于状态的价值函数能够帮助我们更好地为长序列中的每一个动作决策进行信用分配 (credit assignment) 。
一、形式化定义
在MDP的定义中，有两个至关重要的角色：智能体 (Agent) 和环境 (Environment)。
具体来说，智能体在离散的时间步上与环境进行多次交互。在每一个时间步 $t\in{0,1,\dots}$ 上，智能体首先获得环境当前所处的状态 $S_t\in\mathcal{S}$，并采取某个动作 $A_t\in\mathcal{A}$。在下一个时间步上，智能体获得一个数值奖励 $R_{t+1}\in\mathcal{R}\subseteq \mathbb{R}$，并转移到一个新的状态 $S_{t+1}$，然后继续重复上面的过程。在经过一个时间步序列后，智能体和环境共同生成了一条轨迹 (trajectory)：
\[\begin{equation} \tau=S_0,A_0,R_1,S_1,A_1,R_2,\dots \end{equation}\]有限MDP中的“有限”是指状态集合 $\mathcal{S}$、动作集合 $\mathcal{A}$ 和奖励集合 $\mathcal{R}$ 都包含有限个元素。
MDP最重要的性质是被称为【马尔可夫性】的性质（也被称为无记忆性），即当前时间步下的奖励 $R_t$ 和状态 $S_t$ 都只与前一个时间步的状态 $S_t$ 和动作 $A_t$ 有关，即：
\[\begin{equation} \begin{aligned} P(S_t,R_t\mid S_0,A_0,R_1,\dots,S_{t-1},A_{t-1}) &=P(S_t,R_t\mid S_{t-1},A_{t-1}) \end{aligned} \end{equation}\]因此对于每一个MDP，都有如下的动力学方程 $p:\mathcal{S}\times\mathcal{R}\times\mathcal{S}\times\mathcal{A}\mapsto[0,1]$ ：
\[\begin{equation} p(s',r\mid s,a):=P(S_t=s',R_t=r\mid S_{t-1}=s,A_{t-1}=a) \end{equation}\]由于 $p$ 是一个概率分布，因此满足
\[\begin{equation} \forall s\in\mathcal{S},a\in\mathcal{A}(s),\sum_{s'\in\mathcal{S}}\sum_{r\in\mathcal{R}}p(s',r\mid s,a)=1 \end{equation}\]给定动力学方程 $p$，我们可以给状态-动作空间定义如下的奖励函数 $r:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}$ ：
\[\begin{equation} \begin{aligned} r(s,a) &:=\mathbb{E}[R_t\mid S_{t-1}=s,A_{t-1}=a]\\ &=\sum_{r\in\mathcal{R}}r\sum_{s'\in\mathcal{S}}p(s',r\mid s,a) \end{aligned} \end{equation}\]MDP 框架是目标导向学习 (goal-directed learning) 问题的一个抽象表述。它提出，无论感知、记忆和控制方法的细节如何，也无论试图实现的目标是什么，任何学习目标导向行为的问题都可以简化为在智能体与其环境之间来回传递的三个信号：一个信号表示智能体所做的选择（动作），一个信号表示做出选择的基础（状态），以及一个信号定义智能体的目标（奖励）。
二、学习目标
用一句话来说明强化学习的目标就是：最大化智能体在一段时间内获得的累计奖励。
这里的累计奖励（也被称为期望回报）有多种定义方式。比如说最简单的一种定义方式就是把未来得到的所有奖励直接求和：
\[\begin{equation} G_t:=R_{t+1}+R_{t+2}+\cdots+R_T \end{equation}\]然而这种定义方式并没有考虑不同时间步上的差异。一般来说，越近时间步上的奖励应当越重要。因此，我们一般用 折扣回报 (discounted return) 来刻画：
\[\begin{equation} \begin{aligned} G_t&:=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots\gamma^{T-t-1} R_T \\ &=\sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}\\ &=\sum_{k=t+1}^{T}\gamma^{k-t-1}R_k \end{aligned} \end{equation}\]其中，$\gamma\in[0,1]$ 称为折扣因子。$\gamma$ 越大，表示越重视未来收益，否则表示更重视当前的瞬时收益。
由折扣回报的定义，我们可以写出它的递推式：
\[\begin{equation} \begin{aligned} G_t&:=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots+\gamma^{T-t-1} R_T\\ &=R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\cdots+\gamma^{T-t-2} R_T)\\ &=R_{t+1} + \gamma G_{t+1} \end{aligned} \end{equation}\]三、策略和价值函数
3.1. 策略、价值函数与贝尔曼方程
策略 (policy) 是指从状态空间映射到动作空间到概率分布。具体来说，如果一个智能体在时间步 $t$ 上使用策略 $\pi$，则我们有：
\[\begin{equation} \pi(a\mid s):=P(A_t=a\mid S_t=s) \end{equation}\]即智能体在状态 $s$ 下选择动作 $a$ 的概率。
更进一步地，我们可以分别定义策略 $\pi$ 下的 状态价值函数 $v_{\pi}(s)$ 和 动作价值函数 $q_{\pi}(s,a)$：
\[\begin{equation} \begin{aligned} v_{\pi}(s) &:=\mathbb{E}_{\pi}[G_t\mid S_t=s]\\ &=\mathbb{E}_{\pi}\left[ \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}\mid S_t=s \right]\\ q_{\pi}(s,a) &:=\mathbb{E}_{\pi}[G_t\mid S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi}\left[ \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}\mid S_t=s,A_t=a \right]\\ \end{aligned} \end{equation}\]状态价值函数一个重要性质是它满足下面的 贝尔曼方程 (Bellman equation)：
\[\begin{equation} \begin{aligned} v_{\pi}(s) &:=\mathbb{E}_{\pi}[G_t\mid S_t=s]\\ &=\mathbb{E}_{\pi}[ R_{t+1} + \gamma G_{t+1} \mid S_t=s]\\ &=\sum_{a}\pi(a\mid s)\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma \mathbb{E}_{\pi}[G_{t+1}\mid S_{t+1}=s'] \right]\\ &=\sum_{a}\pi(a\mid s)\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{\pi}(s') \right]\\ \end{aligned} \end{equation}\]贝尔曼方程描述了 状态 $s$ 的价值与后续状态 $s’$ 的价值之间的关系。借助贝尔曼方程，我们就可以在一条轨迹 $\tau$ 上 从后往前 地使用动态规划来求解每一个状态的价值函数。
值得一提的是，状态价值函数 $v_{\pi}(s)$ 是贝尔曼方程的 唯一解。因此在强化学习算法中，贝尔曼方程是我们对 $v_{\pi}(s)$ 进行计算、近似或学习的重要工具。
3.2. 求解最优策略与最优价值函数
正如上面所说的，强化学习任务就是找到一个最优的策略 $\pi$，使得累计期望回报最大。借助状态价值函数，我们可以对上面的目标进行更加形式化的表述。
状态价值函数实际上是一个关于策略的偏序函数，如果在所有状态 $s$ 下，使用策略 $\pi$ 带来的价值都比使用策略 $\pi’$ 带来的价值更高，则我们称 $\pi$ 是一个“更优”的策略。即：
\[\begin{equation} \pi\succeq\pi'\iff\forall s\in\mathcal{S},v_{\pi}(s)\ge v_{\pi'}(s) \end{equation}\]在这个意义下，我们称比其他所有策略都“更优”的策略为最优策略 $\pi_{*}$ 。
注意最优策略可能不止一个，但所有的最优策略都有同样的最优状态价值函数 $v_{}(s):=\max_{\pi} v_{\pi}(s)$ 和 最优动作价值函数 $q_{}(s,a):=\max_{\pi} q_{\pi}(s,a)$ 。
最优的状态价值函数同样满足贝尔曼方程，特别地，这个方程被称为 贝尔曼最优方程 (Bellman optimality equation)：
\[\begin{equation} \begin{aligned} v_{*}(s) &=\max_{a}q_{*}(s,a)\\ &=\mathbb{E}_{\pi}[G_t\mid S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi}[ R_{t+1} + \gamma G_{t+1} \mid S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi}[ R_{t+1} + \gamma v_{*}(S_{t+1}) \mid S_t=s,A_t=a]\\ &=\max_a\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{*}(s') \right]\\ \end{aligned} \end{equation}\]贝尔曼最优方程实际上描述了下面这样的事实：在最优策略下，状态 $s$ 的价值必须等于在状态 $s$ 下最优动作 $a$ 带来的价值。
同样地，最优动作价值函数也满足以下的贝尔曼最优方程：
\[\begin{equation} \begin{aligned} q_{*}(s,a) &=\mathbb{E}_{\pi}[ R_{t+1} + \gamma \max_{a'}q_{*}(S_{t+1},a') \mid S_t=s,A_t=a]\\ &=\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\max_{a'}\gamma q_{*}(s',a') \right]\\ \end{aligned} \end{equation}\]