有限马尔可夫决策过程
基本定义
马尔可夫决策过程（MDP）描述的是这样一个框架：一个智能体在一个环境中行动，$t$ 时刻智能体根据它当前感知的状态 $s_t$ 做出动作 $a_t$，每执行一个动作，环境中的状态会进行一次转移变为 $s_{t+1}$，同时环境会给智能体一个回报信息 $r_{t+1}$。智能体执行动作的目标是最大化累计的回报 $\sum_t{r_t}$。这个过程可以由下图表示。
在智能体不断根据状态执行动作的设置下，会得到一条轨迹 $\tau$
$$\tau = \{s_0,a_0,r_1,s_1,a_1,r_2,…,s_n,a_n,r_{n+1},s_{n+1}\}$$
状态 $s_{n+1}$ 可能是智能体想要最终达到的状态，MDP 解决的问题一般称之为序列决策问题。下面介绍一些 MDP 中的常见符号：
- $\mathcal{A}$ 表示动作空间，它包含了智能体能执行的所有动作。
- $\mathcal{S}$ 为状态空间，它表示环境中所有可能的状态。
- $p(s’|s,a)$: 这一般被称之为状态转移概率, 表示在状态 $s$ 下执行动作 $a$ 后, 状态转移到 $s’$ 的概率, 其中 $\sum_{s’\in \mathcal{S}}p(s’|s,a)=1$, 其映射可以表示为 $\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow [0,1]$。这一定义表明状态的转移只与当前的状态有关，与过去的状态无关，这一性质称之为马尔可夫性。
- $r(s,a,s’)$ 表示在状态 $s$ 下执行动作 $a$ 后, 状态转移到 $s’$ 得到的回报值大小, 用映射表示为 $\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$. 对于不确定性的系统动力学模型中，回报用这一种。
- $r(s,a)$: 在状态 $s$ 下执行动作 $a$ 后得到的回报值大小, $r(s,a)=\sum_{s’\in\mathcal{S}}p(s’|s,a)r(s,a,s’)$, 用映射表示为 $\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$。对于确定性的系统动力学模型中，回报用这一种。
在这种框架下，我们可以对很多种序列决策问题进行建模，对于不同的问题可以灵活的选择不同的动作空间和状态空间。
累计回报的定义
我们知道智能体的最终目标是最大化长期受益, 所以我们要定义累计回报 $G_t$，它表示 $t$ 时刻之后智能体收到的回报之和。累计回报一般会有两种定义，根据不同任务分为：持续性任务下的累计回报和有限步长任务下的累计回报，后者也被称为分幕式任务。但它们都有一个基本的形式：
$$\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=t+1}^T\gamma^{k-t-1}r_k \end{aligned}$$
式中 $\gamma$ 称为折扣因子，$T$ 为最终的时刻. 对于持续性任务 $(T=\infty)$, 要求 $\gamma \in [0,1)$, 对于分幕式任务 $(T\neq\infty)$, 则要求 $\gamma \le 1$. 折扣因子用于表明最近时刻的收益具有更大的权重。
多说一点，邻近时刻的回报可以用递归方式联系起来：
$$\begin{aligned} G_t&:= r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3} + \cdots \\ &= r_{t+1} + \gamma(r_{t+2} + \gamma r_{t+3} + …) \\ &= r_{t+1} + \gamma G_{t+1} \end{aligned}$$
策略和价值函数
强化学习中，还有两个较为重要的定义：策略和价值函数。
策略定义为: $\pi(a|s)$，它表示智能体在状态 $s$ 下执行动作 $a$ 的概率, 其中 $\sum_{a\in\mathcal{A}}\pi(a|s)=1$, 映射可以写为 $\mathcal{S}\times\mathcal{A}\rightarrow [0,1]$。价值函数则是与状态或者与状态-动作二元组有关的函数，用于评估当前策略在给定状态下的好坏。准确的说，它是累计回报的期望值。
我们把策略 $\pi$ 下状态 $s$ 的价值函数记为 $V_\pi(s)$，表示的是从状态 $s$ 开始，智能体按照策略 $\pi$ 进行决策所获得的回报的期望值。
$$V_\pi(s) := \mathbb{E}[G_t | s_t = s] = \mathbb{E_\pi}\left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} | s_t=s \right]$$
上式中 $t$ 可以是任意时刻。$V_\pi$ 表示策略 $\pi$ 的状态价值函数。
类似的，我们把策略 $\pi$ 下在状态 $s$ 时执行动作 $a$ 的价值函数记为 $Q_\pi (s,a)$，他表示从状态 $s$ 开始，执行动作 $a$ 后，智能体按照策略 $\pi$ 进行决策所获得的回报的期望值。
$$Q_\pi(s,a) := \mathbb{E}[G_t | s_t = s, a_t=a] = \mathbb{E_\pi}\left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} | s_t=s,a_t=a \right]$$
上式中 $t$ 可以是任意时刻。$Q_\pi$ 表示策略 $\pi$ 的状态-动作价值函数。
对于 $V_\pi,Q_\pi$ 的估算，可以让智能体在环境中以策略 $\pi$ 行动，同时收集环境中给出的回报值，对某一状态后出现的回报值取平均来估算对应的价值函数，这种采样方法称之为蒙特卡洛方法。当采样次数无穷大时，估计值会收敛到价值函数的期望值。
贝尔曼方程
价值函数有一个基本特性，它们满足某种递归关系，直接看公式：
$$\begin{aligned} V_\pi(s) :&= \mathbb{E}[G_t|s_t=s] \\ &= \mathbb{E}[r_{t+1}+\gamma G_{t+1} | s_t=s] \\ &=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma\mathbb{E}[G_{t+1}|s_{t+1}=s’]\right] \\ &=\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s’\in\mathcal{S}}p(s’|s,a)\left[r(s,a,s’)+\gamma V_\pi(s’)\right] \end{aligned}$$
上式被称为状态价值函数的贝尔曼方程，它的导出完全是根据马尔可夫决策过程中价值函数的定义得出来的。假设 $\mathcal{S}$ 中包含 $n$ 种状态，那么贝尔曼方程就有 $n$ 个，解贝尔曼方程只需要解一个线性方程组就行了。
此外，补充一个式子，根据价值函数的定义，显然有：
$$V_\pi(s) = \sum_{a\in\mathcal{A}} \pi(a|s) Q_\pi(s,a) $$
至于 $Q_\pi(s,a)$，同样根据定义显然有关于状态-动作价值函数的贝尔曼方程：
$$\begin{aligned} Q_\pi(s,a) &= \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma V_\pi(s’) \right] \\ &= \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma \sum_{a’\in\mathcal{A}} \pi(a’|s’) Q_\pi(s’,a’) \right] \end{aligned}$$
贝尔曼最优方程
解决一个强化学习的任务就是要找到一个最优策略，如果一个策略 $\pi$ 在所有状态上的累计期望回报都大于等于其他策略，即 $V_{\pi_\star}(s) \ge V_{\pi\prime}(s), s\in \mathcal{S}$。那么 $\pi_\star$ 是最优策略。注意到最优策略可能不止一个。最优策略对应的价值函数称之为最优价值函数。下面两个式子分别是最优状态价值函数和最优动作价值函数。
$$\begin{aligned} V_{\pi_\star}(s) &:= \max_\pi V_\pi(s),\quad s\in \mathcal{S} \\ Q_{\pi_\star}(s,a) &:= \max_\pi Q_\pi(s,a),\quad s\in \mathcal{S},a\in\mathcal{A} \end{aligned}$$
根据最优策略的定义有：
$$\begin{aligned} V_{\pi_\star}(s) &=\sum_{a\in\mathcal{A}} \pi_\star(a|s) Q_{\pi_\star}(s,a) \\ &=\max_{a\in \mathcal{A}} Q_{\pi_\star}(s,a) \\ &=\max_{a\in \mathcal{A}} \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma V_{\pi_\star}(s’) \right] \end{aligned}$$
上式中，第二个等号是因为最优策略一定是一个固定的策略，那么 $\pi_\star$ 一定会执行一个固定的动作，并且这个动作的累计回报的期望最大。一般的，上式被称之为状态价值函数的贝尔曼最优方程。贝尔曼最优方程阐述了一个事实：最优策略下各个状态的价值一定等于这个状态下最优动作的回报的期望值。贝尔曼最优方程只表明了，最优策略对应的价值函数一定满足贝尔曼最优方程，但满足贝尔曼最优方程的价值函数不一定是最优价值函数，这里需要一个唯一性证明，证明满足贝尔曼最优方程的价值函数是唯一的。唯一性，讲动态规划的时候会证明。
根据状态-动作价值函数的贝尔曼方程，同理有 状态-动作价值函数的贝尔曼最优方程，形式如下：
$$\begin{aligned} Q_{\pi_\star}(s,a) &= \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma \sum_{a’\in\mathcal{A}} \pi_\star(a’|s’) Q_{\pi_\star}(s’,a’) \right] \\ &= \sum_{s’\in\mathcal{S}} p(s’|s,a) \left[r(s,a,s’) + \gamma \max_{a’\in\mathcal{A}} Q_{\pi_\star}(s’,a’) \right] \end{aligned}$$
第二个等号的原因同上。
注意：贝尔曼最优方程隐含了一个结论：对于最优价值函数来说，任何贪心策略都是最优策略，每次执行动作贪心的找 $\max_{a\in \mathcal{A}} Q_{\pi_\star}(s,a)$ 就行了，此时最优策略就是一张表格，每种状态对应一个最优的动作（只要得到了最优价值函数就能得到最优策略）。此时我们称这种任务为表格型任务。
求解贝尔曼最优方程
解贝尔曼最优方程也比较简单，就是解 $n$ 个带有 $\max$ 的方程组。但是这种求法很少情况是可行的，一般需要强大的算力。这是一种类似于穷举的求法，预估所有的可能性。这种求方程组的方法通常需要满足几个条件：
- 状态空间和动作空间是离散的
- 系统动力学 $p(s’|s,a)$ 是已知的
- 有足够的计算资源
- 系统模型满足马尔可夫性质
在大部分情况下，上面的条件是无法满足的，因此强化学习中会考虑一些近似算法。