多臂赌博机问题里，玩家面临 $k$ 个选择，但是每一个时间点上这 $k$ 个选择对应的奖励分布没有变化，只是通过玩的经验，玩家对它们的估计有了更新。可以认为，多臂赌博机只有一个状态。
但还记得我们说RL是“通过与环境交互来学习”的吗，对于大部分RL问题，在做出动作的时候，自己的状态是会发生改变的。所谓状态会改变，就是玩家可选的动作空间、做出动作获得的收益以及导向下个状态的转换关系发生的一系列改变，可以认为是“玩家所处的环境发生了改变”。研究状态改变的一个领域叫马尔可夫链或马尔可夫过程，其中，通过玩家的动作完成状态改变，并的马尔可夫过程叫做马尔可夫决策过程 (Markov Decision Process, MDP)。
用MDP可以定义绝大多数强化学习问题，也是 RLAI 这本书对强化学习任务的正式数学表述。接下来我们介绍MDP的数学定义、一些重要性质、以及解MDP问题的几种方法。
1. Markov Decision Process (MDP)
1.1 定义和符号
- $S_{t} \in \mathcal{S}$ 表示状态(state)和状态空间；
- $A_{t} \in \mathcal{A}\left(S_{t}\right)$ 表示玩家(agent)在 $S_t$ 状态下从该状态的动作空间中选择的一个动作(action)；
- $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$ 表示在时间 $t$ 选择动作 $A_t$ 后，在下一个时间获得一个数值奖励(numerical reward)，同时状态转变为 $S_{t+1}$
-
玩家在时间 $t$ ，根据一个策略 (policy) 按照一定概率选择各个动作，用 $\pi_{t}(a s)$ 表示在 $S_t=s$ 的情况下选择 $A_t=a$ 的概率
1.2 强化学习的MDP定义
有了这些定义，就可以给出一个适用广泛的强化学习定义：
-
所谓强化学习，就是从经验(experience)中学习一个策略，使得依据此策略在长期的运行时间(long run)内获得最大的奖励总和(maximize the total amount of rewards)
- 强化学习的任务由奖励来而定义，任何一个目标，把他量化成标量、可叠加、且我们希望其总和最大的指标，就可以成为一个强化学习任务的奖励。
- 比如我们想让一个机器人去捡垃圾，奖励可以设计成“每捡到一个垃圾，给出+1的奖励，没有捡到奖励则是0，但如果掉进了坑里，就给出一个的负值奖励”；
- 奖励也可以最后再给出，比如玩象棋，途中奖励一直都是0，但是终局时，赢了奖励为1，输了奖励为-1，平局则为0
- 奖励是你想让学习机器达成什么目标(what)，而不是你想让它怎么达成这个目标(how)，所以下象棋的时候不要把吃对面的棋子加到奖励里面去
-
学习机器和环境的边界 (interface) 应该设定在控制系统外，也就是说，如果要学习一个机器人的运动，最好把传感器、运动单元、电池这些硬件都设定成环境，只有控制系统设定成agent。换句话说，agent只包括自己能完全掌控的部分。
- RL的返回值（也就是我们想要最大化的总奖励）有两种定义方式，一种是单纯的把所有时间点的奖励加起来，即 \(G_{t} \doteq R_{t+1}+R_{t+2}+R_{t+3}+\cdots+R_{T}\) 显然这种定义只适合有明确结束时间的任务，即存在“最终状态(terminal state)”，达到最终状态就结束一局游戏(an episode)。 但还有一些任务是无限时间的连续任务(continuing task)，上面那种定义就有问题了，很有可能都是无穷大，这里可以加入一个折扣因子(discounting factor) $\gamma \in [0,1]$，把返回值定义成 \(G_{t} \doteq R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\cdots=\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}\) 如果按照这个定义，很容易改写成 \(G_t = R_{t+1} + \gamma G_{t+1}\) 这个式子以后在TD等算法中非常有用
1.3 MDP的数学定义
这里我们先只考虑有限状态的MDP，即状态空间、动作空间都有限的finite MDP
一个finite MDP模型，就是给定当前的状态和动作，转换为下一状态以及获得奖励的联合概率分布，即 \(p\left(s^{\prime}, r | s, a\right) \doteq \operatorname{Pr}\left\{S_{t+1}=s^{\prime}, R_{t+1}=r | S_{t}=s, A_{t}=a\right\}\)
有了这个联合概率分布，我们可以计算：
- 当前状态、动作下的奖励期望 \(r(s, a) \doteq \mathbb{E}\left[R_{t+1} | S_{t}=s, A_{t}=a\right]=\sum_{r \in \mathcal{R}} r \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime}, r | s, a\right)\)
- 下一时刻转变为某个状态的概率 \(p\left(s^{\prime} | s, a\right) \doteq \operatorname{Pr}\left\{S_{t+1}=s^{\prime} | S_{t}=s, A_{t}=a\right\}=\sum_{r \in \mathcal{R}} p\left(s^{\prime}, r | s, a\right)\)
- 已知下一状态，奖励的期望 \(r\left(s, a, s^{\prime}\right) \doteq \mathbb{E}\left[R_{t+1} | S_{t}=s, A_{t}=a, S_{t+1}=s^{\prime}\right]=\frac{\sum_{r \in \mathcal{R}} r p\left(s^{\prime}, r | s, a\right)}{p\left(s^{\prime} | s, a\right)}\)
1.4 值函数
很多强化学习算法是通过估计值函数来制定决策的，值函数就是评估价值的函数，价值也就是未来长时间内获得奖励的期望。根据评估价值的对象不同，值函数分为两种：状态值函数和状态-动作值函数
-
状态值函数 状态值函数(state-value function)，顾名思义就是评估状态的价值，指在当前状态下，如果我们按照一个策略 $\pi$ 来进行之后的决策，获得奖励的期望，一般用 $v_{\pi}(s)$ 表示，即
-
状态-动作值函数 状态-动作值函数(state-action-value function，也叫action-value function)，是指给定一个状态和在该状态下执行的一个动作，获得奖励的期望，一般用 $q_{\pi}(s,a)$ 来表示
1.5 贝尔曼等式
由于某个时刻的奖励可以用之后时刻的奖励表示，即$ G_t = R_{t+1} + \gamma G_{t+1} $。我么也可以把某个时刻的值函数用下一时刻的值函数表示出来，对于状态值函数，这个公式是
对于动作值函数，就是（待续）