参考书：
Barto&Sutton: Reinforcement Learning-An Introduction, 2rd edition
强化学习(第2版)

3 有限马尔可夫决策过程

MDP（Markov Decision Process） 是强化学习问题在数学上的理想化形式。
马尔可夫性（Markov Property） 是马尔可夫过程的核心特征，它描述了随机过程的一种特殊性质，即“无记忆性”或“无后效性”。简单来说，马尔可夫性意味着系统的未来状态只依赖于当前状态，而与过去的状态无关。
有限MDP是指状态空间集合为有限的，且具有马尔科夫性的决策过程。

3.1 “智能体-环境”交互接口

MDP是通过交互式学习来实现目标的理论框架。
进行学习和实施决策的对象被称为智能体（agent）。
智能体之外所有与其相互作用的事物都被称为环境（environment）。
智能体和环境之间产生交互，智能体选择动作，环境对这些动作做出相应的响应，并向智
能体呈现出新的状态。环境产生收益，智能体尝试最大化收益。如图3.1所示。

使用符号表达，在每个离散时刻$t=0,1,2,3,\dots ,$，智能体：

• 观察到环境状态：$S_t\in \mathcal{S}$
• 执行动作：$A_t\in \mathcal{A}(s)$
• $t+1$时刻，收到一个数值化的收益：$R_{t+1}\in \mathcal{R}\subset \mathbb{R}$
• 进入新的状态$S_{t+1}$

这样，智能体和环境共同产生了一个轨迹(trajectory)：
$$S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3,\dots \text{\hspace{1em}(3.1)}$$
在 有限 MDP中，集合$\mathcal{S},\mathcal{A},\mathcal{R}$只有有限个元素。
而在马尔可夫决策过程中，我们定义随机变量$R_t,S_t$只依赖于前一时刻的状态和动作，与更早之前的无关。
对任意$s^{\prime },s\in \mathcal{S},r\in \mathcal{R},a\in \mathcal{A}(s)$可以定义以下等式（后续称为四参数动态函数p）：
p ( s ′ , r ∣ s , a ) = ⋅ P { S t ′ = s ′ , R t = r ∣ S t − 1 = s , A t − 1 = a } (3.2) p(s',r | s, a)\overset{\cdot}{=}\mathbb{P}\{S'_t=s',R_t=r|S_{t-1}=s,A_{t-1}=a\} \tag{3.2} p(s′,r∣s,a)=⋅P{St′​=s′,Rt​=r∣St−1​=s,At−1​=a}(3.2)

例3.3 回收机器人

设想一个机器人进行回收易拉罐的工作。假设它的状态根据电量可分为 S = { high, low } \mathcal{S}=\{\text{high, low}\} S={high, low}。
可采取的动作集合根据电量可分为 A ( high ) = { s e a r c h , w a i t } \mathcal{A}(\text{high})=\{search, wait\} A(high)={search,wait}和 A ( low ) = { s e a r c h , w a i t , r e c h a r g e } \mathcal{A}(\text{low})=\{search, wait,recharge\} A(low)={search,wait,recharge}。
回报则为捡到一个易拉罐为$1$，电量耗尽前未充电为$-3$。
能量水平为高时下一个状态仍为高的概率为$\alpha$，下一个状态为低的概率为$1-\alpha$。能量水平为低时下一个状态仍为低的概率为$\beta$，下一个状态为高的概率为$1-\beta$。
这个系统则是一个有限MDP, 我们可以写出其转移概率和期望收益，其动态变化如下图所示。右图是一个转移图。其中大圆为状态节点，中间一个实心圆带箭头表示动作节点。每个箭头都对应着一个三元组$(s,s^{\prime },a)$，其中$s^{\prime }$是下一个状态。我们把每个箭头都标上一个转移概率p和转移的期望收益。

3.2 目标和收益

收益假设：我们所有的“目标”或“目的”都可以归结为：最大化智能体接收到的标量信号（称之为收益）累积和的概率期望值。
设立收益时，需要注意收益与我们最终想要达到的目标是一致的，避免智能体以无法达到最终目标的代价获得高收益。

3.3 回报和分幕

分幕

将长期收益简单定义为：
$$G_t=R_{t+1}+R_{t+2}+R_{t+3}+\cdots +R_T\text{\hspace{1em}(3.7)}$$
其中T是最终时刻。在一些任务中，交互过程可以被分为子序列，每个子序列被称为 “幕（episode）” ，此时这里的“最终时刻”就是每个幕的结束状态，也称为 终结状态。
下一幕的开始状态与上一幕的结束方式完全无关。
如果交互是持续的，则$T=\infty$（但这样$G_t$会变为无穷）。下面是一个解决$G_t$计算的方法。

回报

将t时刻开始之后的期望回报（也就是我们希望最大化的目标函数）定义为：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}\text{\hspace{1em}(3.8)}$$
其中$0\le \gamma \le 1$称为折扣率，决定我们有多关注当前收益/未来收益。
根据式子3.8的定义，我们也可以导出：
$$G_t=R_{t+1}+\gamma G_{t+1}\text{\hspace{1em}(3.9)}$$
可以证明，当$\gamma <1$时，即使$T=\infty$，也不会导致$G_t\to \infty$的情况。

3.4 分幕式和持续性任务的统一表示法

可以将幕的终止状态作为吸收状态的入口，如图所示，最终状态只会转移到自己并只产生零收益。这样式（3.7）和式（3.8）就可以统一：
$$G_t\stackrel{\cdot }{=}\sum _{k=t+1}^T{\gamma }^{k-t-1}{R}_k\text{\hspace{1em}(3.11)}$$
并允许上式包括 $T=\infty$ 或 $\gamma =1$（但不是二者同时）的可能性。

3.5 策略和价值函数

价值函数是状态（或状态与动作二元组）的函数，用来评估当前智能体在给定状态（或给定状态与动作）下有多好。
策略是从状态到每个动作的选择概率之间的映射。如果智能体在时刻$t$选择了策略$\pi$, 那么$\pi (a|s)$就是当$S_t=s$ 时$A_t=a$ 的概率。
策略$\pi$下状态$s$的价值函数记为$v_{\pi }(s)$（从状态$s$开始，智能体按照策略$\pi$进行决策获得回报的期望。 对于MDP：
$$v_{\pi }(s)\stackrel{\cdot }{=}{\mathbb{E}}_{\pi }[G_t|S_t=s]={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s\right]\text{\hspace{1em}(3.12)}$$
$v_{\pi }(s)$也称为策略$\pi$的状态价值函数。
类似的，定义策略$\pi$的动作价值函数：
$$q_{\pi }(s,a)\stackrel{\cdot }{=}{\mathbb{E}}_{\pi }[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]\text{\hspace{1em}(3.13)}$$
对于状态价值和动作价值的估算，蒙特卡洛方法通过从真实回报的多个随机样本中求平均值来估算。当环境中存在大量状态时，可采用参数化价值函数的方法，通过调整参数来近似计算回报值，从而避免独立估算每个状态的平均值。
在强化学习和动态规划中，价值函数有一个基本特性，就是它们满足某种递归关系，类似于我们前面为回报建立的递归公式。对于任何策略 $\pi$ 和任何状态 $s$，其价值满足以下关系：
$$v_{\pi }(s)\stackrel{\cdot }{=}{\mathbb{E}}_{\pi }[G_t|S_t=s]={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]$$
根据公式 (3.9)，可以展开为：
$$v_{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]\right]=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]，对于所有s\in \mathcal{S}(3.14)$$

其中，动作 $a\in \mathcal{A}(s)$，下一时刻状态 $s^{\prime }\in \mathcal{S}$，收益值 $r\in \mathcal{R}$。这个式子也被称为贝尔曼方程。

Note：收益，回报，和价值函数的比较

收益函数(Reward Function) $r_s$

• 定义：Reward function 通常用来描述在某个状态 $s$ 或状态-动作对 $(s,a)$ 下，智能体（agent）从环境（environment）获得的即时奖励。
• 特点：它是对环境反馈的即时量化，例如在迷宫任务中，每走对一步可能得到正奖励，撞墙得到负奖励。

收益(Reward) $R_t$

• 定义：Reward $R_t$ 是在时间步 $t$ 时，智能体实际收到的奖励值，它是一个随机变量。

回报(Return) $G_t$

• 定义：Return $G_t$ 是从时间步 $t$ 开始到终止状态（或无穷远）所获得的累积收益的折扣和。
• 特点：它衡量了某个时间步之后的总收益，用于评估某个状态或策略的长期效果，例如在投资决策中，评估某个时点后的总回报。

状态价值函数(Value Function) $v(s)$

• 定义：Value function（也称为状态值函数）衡量的是处于状态 $s$ 的期望回报。

策略$\pi$的状态价值函数$v_{\pi }(s)$

• 定义：从状态s开始，智能体按照策略$\pi$进行决策所获得的回报的概率期望值。

策略$\pi$的动作价值函数$q_{\pi }(s,a)$

• 定义：策略$\pi$下在状态s时采取动作a的价值。

3.6 最优策略和最优价值函数

用${\pi }_{\ast }$表示最优策略。它们应该享有相同的价值函数。对于最优状态价值函数有：
$$v_{\ast }(s)\stackrel{\cdot }{=}\underset{\pi }{\max }{v}_{\pi }(s)$$
对于最优动作价值函数有：
$$q_{\ast }(s,a)\stackrel{\cdot }{=}\underset{\pi }{\max }{q}_{\pi }(s,a)$$
状态价值函数的贝尔曼最优方程如下。可以理解为最优策略下对每个状态的最优价值都等于这个状态下最优动作的期望。
$$v_{\ast }(s)=\underset{a}{\max }\mathbb{E}\left[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a\right]=\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma v_{\ast }(s^{\prime })\right]$$
动作价值函数的贝尔曼最优方程如下。可以理解为在确定这一刻的动作后，对下一刻动作取最优。
$$q_{\ast }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }(S_{t+1},a^{\prime })|S_t=s,A_t=a\right]=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma \underset{a^{\prime }}{\max }{q}_{\ast }(s^{\prime },a^{\prime })\right]$$
使用$v_{\ast }$确定最优策略：进行单步搜索，选择产生最大价值的动作。（采用贪心策略）
使用$q_{\ast }$确定最优策略：直接选择使得$q_{\ast }(s,a)$值最大的a。

3.7 最优性和近似算法

虽然有了贝尔曼最优方程，但事实上对于$v_{\ast }$的解析求解还是很困难（特别是计算资源首先的问题）。因此，我们需要采用近似优化。有时，在近似优化的过程中可能使得对一些出现概率很小的状况反应不佳。