Chapter 3：有限Markov决策过程

有限MDPs问题和老虎机问题一样，也是评价性反馈，但是和bandit问题不同的是，MDPs问题除了immediate reward还涉及到delayed reward，需要在直接奖励和延迟奖励之间权衡。

在bandit问题中，估计的是每个动作$a$的value $q_{\ast }(a)$；在MDPs中，估计的是每个状态$s$下的每个动作$a$的value $q_{\ast }(s,a)$，或者估计给定最佳动作选择后每个状态的value $v_{\ast }(s)$。

本章介绍了MDPs问题的数学结构的关键元素：如returns，value function，Bellman equation。函数和Bellman方程。与所有人工智能一样，该问题在适用范围和数学易处理性之间存在着一种权衡。

2.1 Agent–Environment交互

事件发生顺序：

在有限MDPs中，状态、动作和奖励$(\mathcal{S},\mathcal{A},\mathcal{R})$集合都具有有限数量的元素。因此，随机变量$R_t$和$S_t$具有明确定义的离散概率分布，仅取决于先前的状态和动作。

函数$p:\mathcal{S}\times \mathcal{R}\times \mathcal{S}\times \mathcal{A}\to [0,1]$是含有四个参数的普通确定性函数。函数$p$表征了MDPs的动态。

Markov property: 状态$s$必须包含有关过去的agent-environment互动的所有信息。本书假设该性质成立。

根据带有4个参数的函数$p$，可以推导出其他有关environment的函数：
state-transition probabilities：
含有3个参数的函数$p:\mathcal{S}\times \mathcal{S}\times \mathcal{A}\to [0,1]$

expected rewards for state–action pairs:
含有2个参数的函数$p:\mathcal{S}\times \mathcal{A}\to \mathbb{R}$）

expected rewards for state–action-next state triples:
含有3个参数的函数$p:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \mathbb{R}$）

Markov transition graph

图种有两种节点：state nodes和action nodes

3.2 Goals and Rewards

如果采取的动作不仅有直接奖励，还有延迟奖励，那么目标变为最大化该行动带来的奖励（reward）累积和的期望价值（expected value）。
理解：最大化收到的reward总和（in the long run）。

3.2.1 returns and episodes

return $G_t$：step $t$之后的收到的rewards之和
$$G_t=R_{t+1}+R_{t+2}+...+R_T（3.7）$$

episodes:
当agent-environment交互能自然地分解为子序列时，把子序列叫作episodes，有些文献中也叫trials。
terminal state: 每个episode每集的结束状态。所有episodes都可以被认为是以相同的终端状态结束，但是对不同的结果有不同的奖励。
episodic tasks: 包括多个episodes的tasks。$\mathcal{S}$表示非终结状态的集合，${\mathcal{S}}^{+}$表示非终结状态加终结状态的集合。终止时间$T$是随机变量，根据不同的episode 变化。

continuing tasks: 不能被分解成episodes的tasks，实际情况中很多都是连续任务，此时式(3.7)不再适用，因为 $T=\infty$。

所以我们用了一个稍微复杂一点的return定义，引入了discounting，便于计算。

折现
选择$A_t$最大化expected discounted return:

$\gamma \in [0,1]$：折现率
$\gamma <1$：如果$R_k$有限，式（3.8）是有限。
$\gamma =0$：myopic，只考虑了直接奖励。
$\gamma$越接近1，说明越有远见，考虑future reward越多。

递推关系：

3.2.2 episodic tasks和continuing tasks的统一表示

对于episodic tasks来说，虽然又很多个episodes，但是我们通常只考虑其中单个的episode。
所以可以统一表示为：

其中，KaTeX parse error: Expected 'EOF', got '\infine' at position 3: T=\̲i̲n̲f̲i̲n̲e̲表示continuing tasks；$\gamma =1$表示episodic tasks。两个条件不能同时满足。

3.3 Policy and Value function

policy: 从状态到选择每个可能动作的概率的映射。 例如：现在有policy $\pi$，则$\pi (a|s)$表示$S_t=s$时$A_t=a$的概率。

value function: 在policy $\pi$ 和state $s$ 下的expected return记作$v_{\pi }(s)$


$v_{\pi }$是policy $\pi$ 的state-value function；$q_{\pi }$是policy $\pi$ 的action-value function。

Bellman equation: 在policy $\pi$ 和state $s$ 下的expected return记作$v_{\pi }(s)$

式（3.14）是$v_{\pi }$的Bellman Equation，表示一个state价值与其下一阶段的state价值之间的关系。

3.4 Optimal Policies and Optimal Value Functions

optimal state-value function：

optimal action-value function：

对于state-action pair $s,a$，函数$q_{\ast }(s,a)$表示在状态$s$中执行动作$a$并且此后遵循最优策略$\pi$的expected return。因此，$q_{\ast }$可以用$v_{\ast }$表示：

Bellman optimality equation:
含义：最优policy下的state value必须等于该state下的最佳action的expected return。

Bellman optimality equation for $v_{\ast }$：式（3.18）与式（3.19）
Bellman optimality equation for $q_{\ast }$：式（3.20）

3.5 Optimality and Approximation

因为很多原因，现实中可能无法得到最优解policy，此时就需要近似。强化学习的Online性质使得有可能以更多的方式接近最优策略，以便为频繁出现的state做出正确的决策，而不用考虑到出现频率低的state。这是将强化学习与其他近似解决MDP的方法区分开来的一个关键属性。