三. 有限马尔科夫决策过程（有限MDP）

在有限MDP中，状态、动作和收益的集合（$S$、$A$和$R$）都只有有限个元素。
p ( s ′ , r ∣ s , a ) = P r { S t = s ′ , R t = r ∣ S t − 1 = s , A t − 1 = a } p(s',r|s,a)=Pr\{S_t=s',R_t=r|S_{t-1}=s,A_{t-1}=a\} p(s′,r∣s,a)=Pr{St​=s′,Rt​=r∣St−1​=s,At−1​=a}
$S_t$和$R_t$的每个可能值出现的概率只取决于前一状态$S_{t-1}$和前一动作$A_{t-1}$，并且与更早之前的状态和动作完全无关。

目标和收益

• 智能体的目标是最大化其收到的总收益；
• 提供收益的方式必须要使智能体在最大化收益的同时也实现目标；
• 收益信号并不是传授智能体如何实现目标的先验知识；
• 收益信号只能用来传达什么是你想要实现的目标，而不是如何实现这个目标；

回报和分幕

回报是收益的总和：
$$G_t=R_{t+1}+R_{t+2}+R_{t+3}+。。。+R_T$$
$T$是最终时刻，智能体与环境的交互被分成一个个子序列，我们称每一个子序列为幕（episodes）。

折扣后回报：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+。。。=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$
其中，$0\le \gamma \le 1$是一个参数，称为折扣率。

增量式计算回报：
$$G_t=R_{t+1}+\gamma G_{t+1}$$

策略和价值函数

策略是从状态到每个动作的选择概率之间的映射，例如：$\pi (a|s)$。

把策略$\pi$下状态$s$的价值函数记为$v_{\pi }(s)$，其定义为：
$$v_{\pi }(s)=E_{\pi }[G_t|S_t=s]=E_{\pi }[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s]$$
把函数$v_{\pi }$称为策略$\pi$的状态价值函数。

把策略把策略$\pi$下状态$s$时采取动作$a$的价值记为$q_{\pi }(s,a)$，其定义为：
$$q_{\pi }(s,a)=E_{\pi }[G_t|S_t=s,A_t=a]=E_{\pi }[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a]$$
把函数$q_{\pi }$称为策略$\pi$的动作价值函数。

贝尔曼方程：
$$v_{\pi }=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })],对于所有的s\in S$$

最优策略与最优价值函数

$$\begin{gathered} v_{\ast }(s)=\underset{\pi }{\max }{v}_{\pi }(s) \\ {q}_{\ast }(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a) \end{gathered}$$
贝尔曼最优方程：
$$\begin{gathered} v_{\ast }(s)=\underset{a}{\max }E[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a] \\ =\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })] \end{gathered}$$
贝尔曼最优方程可以直接求解，但是需要满足以下条件：

• 知道环境的动态变化特性；
• 足够的计算资源；
• 马尔科夫性质；

实际系统中，上述条件很难满足。