## 本章核心目标
本章要建立强化学习后续所有章节都会反复使用的概念：
- 状态 state
- 动作 action
- 状态转移 state transition
- 策略 policy
- 奖励 reward
- 轨迹 trajectory、回报 return、回合 episode
- 马尔可夫决策过程 Markov decision process, MDP
- 马尔可夫性质 Markov property
一句话概括：
强化学习研究的是 agent 在环境中通过试错交互，==根据奖励反馈学习“好策略”==的问题；本章把这个过程用 MDP 统一描述。
---
## 1.1 网格世界例子
本书从头到尾使用一个 grid world 例子。
- 机器人称为 agent。
- 机器人在网格中移动，每个时间步只能占据一个格子。
- 白色格子可以进入。
- 橙色格子是禁区 forbidden。
- 有一个目标格 target。
- agent 的目标：找到一个“好”策略，从任意初始格出发都能到达目标，同时避免进入禁区、撞边界、走无意义绕路。
如果 agent 事先知道地图，那么找路径很简单；
但强化学习通常假设 agent 不知道环境模型，必须通过与环境交互、试错来学习。
因此需要定义状态、动作、转移、策略、奖励等概念。
---
## 1.2 状态与动作
### 状态 state
状态描述 agent 相对环境的状态。
在 grid world 中，状态就是 agent 的位置。
图 1.3(a) 中有 9 个格子，因此有 9 个状态：
$$
\mathcal{S}=\{s_1,s_2,\ldots,s_9\}
$$
$\mathcal{S}$ 称为 状态空间 state space。
### 动作 action
每个状态中，agent 可以采取 5 种动作：
- $a_1$：向上
- $a_2$：向右
- $a_3$：向下
- $a_4$：向左
- $a_5$：停留不动
动作集合称为 动作空间 action space：
$$
\mathcal{A}=\{a_1,a_2,a_3,a_4,a_5\}
$$
不同状态可以有不同的动作空间。例如在 $s_1$，向上或向左会撞边界，因此可以设：
$$
\mathcal{A}(s_1)=\{a_2,a_3,a_5\}
$$
但本书为了简单，通常取：
$$
\mathcal{A}(s_i)=\mathcal{A}=\{a_1,\ldots,a_5\}
$$
对所有状态都成立。
---
## 1.3 状态转移
### 定义
agent 在状态 $s$ 采取动作 $a$ 后，可能转移到另一个状态 $s'$，这个过程叫 状态转移 state transition。
例如：
$$
s_1 \xrightarrow{a_2} s_2
$$
表示在 $s_1$ 向右走，到达 $s_2$。
### 两个重要例子
1. 撞边界
在 $s_1$ 执行 $a_1$，试图向上出界。
由于不能离开状态空间，agent 会被弹回：
$$
s_1 \xrightarrow{a_1} s_1
$$
2. 进入禁区
例如在 $s_5$ 执行 $a_2$，试图进入 $s_6$。
有两种可能：
- 禁区虽然 forbidden，但仍可进入，只是会受罚；
- 禁区不可进入，agent 被弹回。
本书选择第一种：**禁区可进入，但进入会得到负奖励**。
因此：
$$
s_5 \xrightarrow{a_2} s_6
$$
### 表格表示
表 1.1 是状态转移的表格表示：
- 每一行对应一个状态；
- 每一列对应一个动作；
- 单元格表示采取该动作后转移到的下一个状态。
这种表格只能描述**确定性状态转移**。
### 概率表示
更一般地，状态转移是随机的，用条件概率表示：
$$
p(s'|s,a)
$$
表示在状态 $s$ 采取动作 $a$ 后转移到 $s'$ 的概率。
必须满足：
$$
\sum_{s'\in \mathcal{S}} p(s'|s,a)=1
$$
例如：
$$
p(s_2|s_1,a_2)=1
$$
$$
p(s_1|s_1,a_2)=0,\quad p(s_3|s_1,a_2)=0,\ldots
$$
说明在 $s_1$ 向右走一定到 $s_2$。
如果存在随机风等情况，则可能出现：
$$
p(s_5|s_1,a_2)>0
$$
本书 grid world 为简单起见，主要考虑确定性转移。
---
## 1.4 策略
### 定义
策略 policy 告诉 agent 在每个状态应该采取什么动作。
策略可以用箭头表示，见图 1.4(a)。
### 数学表示
策略是条件概率分布：
$$
\pi(a|s)
$$
表示在状态 $s$ 选择动作 $a$ 的概率。
必须满足：
$$
\sum_{a\in \mathcal{A}(s)} \pi(a|s)=1
$$
### 确定性策略
例如图 1.4 的策略在 $s_1$ 一定向右：
$$
\pi(a_2|s_1)=1
$$
其他动作概率为 0：
$$
\pi(a_1|s_1)=0,\quad \pi(a_3|s_1)=0,\quad \pi(a_4|s_1)=0,\quad \pi(a_5|s_1)=0
$$
### 随机策略
图 1.5 是一个随机策略。
在 $s_1$，agent 可能向右，也可能向下，概率各 0.5：
$$
\pi(a_2|s_1)=0.5,\quad \pi(a_3|s_1)=0.5
$$
其他动作概率为 0。
### 表格表示
表 1.2 是策略的表格表示：
- 每一行是状态；
- 每一列是动作；
- 单元格是采取该动作的概率。
后续第 8 章会==把策略从表格表示推广到参数化函数表示==。
---
## 1.5 奖励
### 定义
agent 在状态 $s$ 执行动作 $a$ 后，会从环境获得一个奖励 reward，记为 $r$。
奖励是状态和动作的函数：
$$
r(s,a)
$$
奖励可以是正数、负数或零。
- 正奖励：鼓励 agent 采取该动作；
- 负奖励：抑制 agent 采取该动作。
### 本书 grid world 的奖励设置
- 试图出界：$r_{\text{boundary}}=-1$
- 试图进入禁区：$r_{\text{forbidden}}=-1$
- 到达目标：$r_{\text{target}}=+1$
- 其他情况：$r_{\text{other}}=0$
### 目标状态 $s_9$ 的特殊处理
奖励过程不一定在到达 $s_9$ 后终止。
- 若在 $s_9$ 执行 $a_5$ 停留，下一状态仍是 $s_9$，奖励为 $+1$；
- 若在 $s_9$ 执行 $a_2$ 向右，下一状态仍是 $s_9$，但奖励为 $-1$，因为相当于撞边界。
### 表格表示
表 1.3 是奖励的表格表示：
- 每一行是状态；
- 每一列是动作；
- 单元格是采取该动作后获得的奖励。
### 关键提醒
不能只根据即时奖励选择动作。
因为一个动作的即时奖励大，不一定长期总回报大。
强化学习关注的是**长期累计奖励**，即 return。
### 随机奖励
更一般地，奖励也可以是随机的，用：
$$
p(r|s,a)
$$
描述，并满足：
$$
\sum_{r\in \mathcal{R}(s,a)} p(r|s,a)=1
$$
本书 grid world 中奖励过程是确定性的。
### 奖励设计的意义
奖励可以看作一种 人机接口 human-machine interface。
通过设计奖励，我们可以==引导 agent 表现出我们期望的行为==。
但奖励设计本身通常并不简单，尤其对复杂任务。
---
## 1.6 轨迹、回报与回合
### 轨迹 trajectory
轨迹是 state-action-reward 链。
例如图 1.6(a) 中，策略生成轨迹：
$$
s_1 \to s_2 \to s_5 \to s_8 \to s_9
$$
对应奖励为：
$$
0,0,0,1
$$
### 回报 return
回报是==轨迹上所有奖励之和==。
有限轨迹中：
$$
\text{return}=0+0+0+1=1
$$
图 1.6(b) 中另一条轨迹：
$$
s_1 \to s_4 \to s_7 \to s_8 \to s_9
$$
奖励为：
$$
0,-1,0,1
$$
回报为：
$$
0-1+0+1=0
$$
因此左策略回报为 1，右策略回报为 0，所以左策略更好。
这与直觉一致：右策略经过了禁区。
### 即时奖励与未来奖励
==回报 = 即时奖励 + 未来奖励==。
有时即时奖励为负，但未来奖励更大，因此不能短视。
必须根据回报，而不是即时奖励，来决定动作。
### 无限长轨迹与折扣回报
如果到达 $s_9$ 后一直停留，且每次得 $+1$，则：
$$
1+1+1+\cdots=\infty
$$
直接求和发散。
因此引入 折扣回报 discounted return：
$$
G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots
$$
其中 $\gamma\in(0,1)$ 是 折扣率 discount rate。
例如：
$$
0+\gamma 0+\gamma^2 0+\gamma^3 1+\gamma^4 1+\cdots
= \gamma^3(1+\gamma+\gamma^2+\cdots)
= \frac{\gamma^3}{1-\gamma}
$$
### 折扣率的作用
1. 去掉必须终止的限制，允许无限长轨迹；
2. 调节对近期奖励和远期奖励的重视程度：
- $\gamma$ 接近 0：重视近期奖励，策略短视；
- $\gamma$ 接近 1：重视远期奖励，策略远视，敢于冒风险。
### 回合 episode
agent 按策略与环境交互，可能停在某个终止状态。
这样得到的轨迹叫 episode 或 trial。
- episodic tasks：有终止状态的回合任务；
- continuing tasks：没有终止状态，交互永不结束。
### 如何把 episodic 转成 continuing
有两种方式：
1. 把终止状态视为吸收态 absorbing state，agent 到达后永远停留；
2. 把终止状态视为普通状态，agent 可以离开再回来。
本书采用第二种：
目标状态 $s_9$ 视为普通状态，动作空间仍为：
$$
\mathcal{A}(s_9)=\{a_1,\ldots,a_5\}
$$
因为到达 $s_9$ 可反复获得正奖励，所以必须使用折扣率避免回报发散。
---
## 1.7 马尔可夫决策过程 MDP
前面用例子介绍了概念，本节用 MDP 形式化。
MDP 是==描述随机动力系统==的通用框架。
### MDP 的组成
#### 1. 集合
- 状态空间：$\mathcal{S}$
- 动作空间：$\mathcal{A}(s)$，与每个状态 $s$ 相关
- 奖励集：$\mathcal{R}(s,a)$，与每个状态-动作对 $(s,a)$ 相关
#### 2. 模型 model / dynamics
- 状态转移概率：
$$
p(s'|s,a)
$$
满足：
$$
\sum_{s'\in \mathcal{S}} p(s'|s,a)=1
$$
- 奖励概率：
$$
p(r|s,a)
$$
满足：
$$
\sum_{r\in \mathcal{R}(s,a)} p(r|s,a)=1
$$
#### 3. 策略
$$
\pi(a|s)
$$
表示在状态 $s$ 选择动作 $a$ 的概率，满足：
$$
\sum_{a\in \mathcal{A}(s)} \pi(a|s)=1
$$
#### 4. 马尔可夫性质
马尔可夫性质是“无记忆性”：
$$
p(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\ldots,s_0,a_0)
=
p(s_{t+1}|s_t,a_t)
$$
$$
p(r_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\ldots,s_0,a_0)
=
p(r_{t+1}|s_t,a_t)
$$
也就是说，下一状态和奖励只依赖当前状态和动作，==与更早历史无关==。
马尔可夫性质是推导 Bellman 方程的基础。
### 模型是 stationary 还是 nonstationary
- stationary model：模型不随时间变化；
- nonstationary model：模型随时间变化。
本书只考虑 stationary model。
### MDP 与 Markov process 的关系
一旦策略固定，MDP 就退化为一个 Markov process, MP。
如果状态有限或可数，MP 也叫 Markov chain。
本书主要考虑 有限 MDP：状态数和动作数都有限。
### agent-environment 交互
- agent：决策者，能感知状态、维护策略、执行动作；
- environment：agent 之外的一切；
- agent 执行动作后，环境返回新状态和奖励；
- 形成闭环。
---
## 1.8 本章总结
本章用 grid world 例子引入了强化学习基本概念，然后用 MDP 形式化。
核心概念包括：
- 状态、动作、状态转移
- 策略
- 奖励
- 轨迹、回报、回合
- 折扣回报
- MDP、马尔可夫性质
- agent-environment 交互
这些概念是后续章节的基础。
后续会从这些概念出发，引入状态价值、Bellman 方程、最优策略、值迭代、策略迭代、蒙特卡洛、时序差分、值函数逼近、策略梯度和 Actor-Critic。
---
## 1.9 Q&A 精选
### Q1：奖励可以全为负或全为正吗？
可以。
决定鼓励或抑制的是**相对奖励值**，不是绝对奖励值。
例如把原来所有奖励都加 $-2$：
- $r_{\text{boundary}}=-3$
- $r_{\text{forbidden}}=-3$
- $r_{\text{target}}=-1$
- $r_{\text{other}}=-2$
虽然全是负数，但最优策略不变。
原因是：最优策略对奖励的**仿射变换**不变。
这一点第 3.5 章会详细证明。
### Q2：奖励是下一状态的函数吗？
奖励实际上依赖 $s,a,s'$。
但 $s'$ 又由 $s,a$ 决定，因此可以写成：
$$
p(r|s,a)=\sum_{s'} p(r|s,a,s')p(s'|s,a)
$$
这样写的好处是便于建立 Bellman 方程。
---
## 本章关键公式速查
状态空间：
$$
\mathcal{S}=\{s_1,\ldots,s_9\}
$$
动作空间：
$$
\mathcal{A}=\{a_1,\ldots,a_5\}
$$
状态转移概率：
$$
p(s'|s,a),\quad \sum_{s'}p(s'|s,a)=1
$$
奖励概率：
$$
p(r|s,a),\quad \sum_r p(r|s,a)=1
$$
策略：
$$
\pi(a|s),\quad \sum_a \pi(a|s)=1
$$
马尔可夫性质：
$$
p(s_{t+1}|s_t,a_t,\ldots)=p(s_{t+1}|s_t,a_t)
$$
折扣回报：
$$
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots
$$
---
## 本章易错点
1. 即时奖励不等于长期回报。
不能只看一步奖励，要看累计折扣回报。
2. 策略是条件概率，不是动作本身。
确定性策略只是随机策略的特例。
3. 表格表示只能描述确定性转移和奖励。
一般情况需要条件概率。
4. 目标状态不一定终止。
本书把目标状态当普通状态，可以反复获得奖励，因此需要折扣率。
5. 固定策略后，MDP 退化为 MP。
这是 MDP 和 Markov process 的关系。
6. 奖励仿射变换不改变最优策略，但会改变状态价值。
这一点后续会严格证明。
---