如果说监督学习是“老师教你做题”，无监督学习是“你自己整理笔记”，那么**强化学习 (Reinforcement Learning, RL)**就是 “把你扔进迷宫，自己找出口”。
下面的内容已经在第一章简单介绍了一遍。不过为了更好的理解，这里重新讲解一遍：
RL的核心是一个**智能体 (Agent)和环境 (World)**之间的不断对话，其中：
Observation：智能体睁眼看世界，发现当前状态是$s_t$。比如智能体发现自己在某个迷宫的某个格子里
Action: 智能体做出决策，执行动作$a_t$。比如往北走。
Feedback：环境根据规则或者智能体的决策发生变化。反馈能够带来两样东西：
- 新的状态 $s_{t + 1}$，智能体走到了下一个格子，以及：
- 奖励 (Reward, $r_t$)。这是一个标量数字。比如走到陷阱扣除100奖励值，走到出口+100，每走一步消耗1奖励值。
智能体的目标极其功利：那就是最大化未来的总奖励，同时不能掉入当前短期奖励陷阱内。智能体需要规划他这一辈子能尽可能拿到多少奖励。
RL比监督学习更难训练和实现，由于下面两个客观问题的存在：
信用分配 (Credit Assignment)
你整个学期每天学习15分钟，而考试那天早上bro背了一整张提纲。最后你拿到A+。你如何确定导致你拿到A+的原因，是因为你平时努力学习，还是你背了那张提纲？
在强化学习中，奖励往往是延迟分配的。下围棋下了100步才能赢，机器很难知道是哪一步导致了胜局。
探索与利用 (Exploration vs. Exploitation)
你知道学校食堂的皮蛋口水鸡好吃，所以你决定每天都去吃它。这样你每天都至少能吃得很开心。这就是利用 (Exploitation)。
但是隔壁也新开了一家铁板烧，你要不要去试一试？你可能发现这铁板烧比口水鸡更好吃，同时也可能极其难吃。这样的过程就叫做探索 (Exploration)。探索可能会带给你更好的结果，同时也有可能带给你更差的结果。
如果你是智能体，你就要学会如何从“稳拿奖励”和“尝试新事物”之间寻找平衡。
强化学习建模
为了能够让计算机来解决问题，我们需要将这个模糊的世界数学化。这就是马尔可夫决策过程 (Markov Decision Processes, MDP)。
我们定义：
- State Set ($S$)：代指所有可能状态的集合。例如迷宫中所有格子的坐标。
- Action Set ($A$)：代指你能做的所有动作。例如往东西南北走。
- Reward Function ($R(s)$或$R(s, a, s')$)：这个就是规则书。例如$R(s) = -0.004$，可能就意味着每走一步扣你点分，这样你就能逼着智能体走快一点。
- Transition Model ($P$)：决定世界该如何变化的物理引擎。
我们使用概率形式来表达$P$：$P(s_{t+1}|s_t, a_t)$。
我在$s_t$做出了动作$a_t$，我们有多大可能会变成$s_{t+1}$这样的一个状态？我们之所以要定义这样一个“物理引擎”，因为现实世界可能是随机的。机器人想要往北走，但可能由于脚滑了走到了东边。
注意Transition Model的公式：$P(s_{t+1} | s_t, a_t)$。这意味着当前的状态$s_t$和$a_t$，与我们过去的历史($s_{t-1}, s_{t-2}...$)完全无关。
这就是强化学习的核心假设：马尔可夫性 (The Markov Property)。我们的核心假设未来只取决于现在你的决定，与过去无关。只要我知道我现在迷宫的坐标，那么我怎么走到这而儿的并不重要。
折扣因子
由于我们的目标是最大化未来奖励的总和：
$$U = r_0 + r_1 + r_2 + r_3 + ...$$
我们发现一个问题，那就是如果这个游戏永远不结束，$r$加起来会导致你的奖励无穷大。假设你训练一个强化学习模型走迷宫，由于你每一步都会给你一些奖励，那么模型就更倾向于一直在迷宫里打转——为什么不呢？反正这样奖励最大不是（
为了我们能达成数学上的收敛，也为了提现“时间就是金钱”，我们引入了折扣因子 (Discount Factor)。记作$\gamma$，$\gamma \in [0, 1)$。
经过这一步，我们修正的目标函数为：
$$U = r_0 + \gamma r_1 + \gamma^2 r_2 + \gamma^3 r_3 + ... = \sum_{t = 0}^\infty \gamma^t r_t$$
如果$\gamma \rightarrow 0$，则你的模型会机器短视。你的智能体只在乎眼前的$r_0$，完全不考虑明天的死活。
如果$\gamma \rightarrow 1$，则你的模型极其远视。未来的奖励和现在的奖励几乎一样重要。
价值函数与贝尔曼方程
那么我们通过MDP定义了状态，动作和奖励，现在我们的核心难题是：智能体怎么判断现在的处境到底好不好？
想象你是这个智能体。你站在一个格子里，这一步的奖励$R(s)$是-0.04，这是Living Cost。如果你是一个短视的人，你会觉得：“这地真烂，我在扣分。”
但如果你是个有远见的人，你会说：“虽然现在在扣分，但是我只要再走两步就能拿到+100的钻石了”。因此，比较远见的模型能够看到每一个状态的价值如何。
这就引出了价值函数 (Value Function, $V(s)$)的定义：它不是指你现在能拿到多少米，而是从现在开始，一直走到未来，在经过各种打折之后一共能拿到多少米。这是对未来的预期。
但是未来是不确定的。未来取决于你接下来该怎么走。所以我们在谈论价值时，必须给予一个特定的策略 (Policy, $\pi$)。策略就好像是一张藏宝图，它规定了你在每个路口应当往哪里拐。
现在我们就可以定义$V^{\pi}(s)$：如果我站在状态$s$，并且死心塌地地按照策略$\pi$这张地图走下去，我预期地累积回报是多少。
贝尔曼方程
那么我们该如何计算$V^{\pi}(s)$？笨方法就好比模拟一万次游戏，把每次的总分加起来求平均。但这太慢了，而且如果游戏时间无限长该怎么办？
贝尔曼方程根据他发现的一个规律展开：今天的价值，等于今天的奖励，加上明天的价值。因此我们可以根据加入折扣因子的目标函数来进行推导：
$$U = r_0 + \gamma r_1 + \gamma^2 r_2 + \gamma^3 r_3 + ... $$
提取公因式$\gamma$：
$$U = r_0 + \gamma (r_1 + \gamma r_2 + \gamma^2 r_3 + ...) $$
你会发现$r_0$后面的所有内容，就是下一时刻的总价值！
因此，我们就得到了著名的贝尔曼方程 (Bellman Equation)：
$$ V^\pi(s) = R(s) + \gamma \sum_{s'} P(s' | s, \pi(s)) V^\pi(s') $$
这个公式的物理含义极其深刻：
- $R(s)$ (Immediate Reward): 代表我现在站在 $s$ 能立刻拿到手的钱。
- $\gamma$ (Discount): 代表折扣。这项决定“钱的贬值”。
- $\sum P(\dots) V^\pi(s')$ (Future Expectation): 代表期货。我按照策略 $\pi(s)$ 做动作，世界可能会把我送到不同的下一站 $s'$。这一项是对“下一站地盘价值”的加权平均。
所以通过贝尔曼方程我们可以知道，我们不需要模拟无穷远的未来。只要我知道了所有邻居格子的价值 $V(s')$，我就能算出我现在的价值 $V(s)$。这把一个无限的问题转化为了邻里之间的递归关系。
寻找最优解
刚才我们只是在评估一张给定的地图（Policy $\pi$）。但我们的真正目标是寻找那张最好的地图。
这就是 最优策略 $\pi^*$ 和 最优价值函数 $V^*(s)$ 的用处。
最优价值函数$V^*(s)$ 的定义是：在所有可能的策略中，我能拿到的最高期望回报。
我们可以将这样的想法升级刚才的方程，变成贝尔曼最优方程 (Bellman Optimality Equation)：
$$ V^*(s) = R(s) + \max_{a} \gamma \sum_{s'} P(s' | s, a) V^*(s') $$
你会发现普通方程里，动作是固定的（由 $\pi$ 决定）。
而在贝尔曼最优方程中，动作是挑选出来的。我在当前路口，把东南西北四个方向全看一遍。向东走的未来价值是 10，向西是 50... 我当然选那个能让未来价值最大的动作（$\max_a$）。
想象你走进了一家非常有名的米其林三星餐厅。你现在正坐在餐桌前，这就是你的状态$s$。
那你的状态对应的价值是什么？你的朋友这时候问你：“坐在米其林三星餐厅感觉咋样？”
你会说“太棒了！感觉今天绝对能吃的很好！”因为你知道这家的菜品一定会很好吃，你预期接下来你会吃到很棒的东西。这就是$V^*(s)$。它评估你“处于当前这个处境本身有多好”，它假设你会租出最明智的选择。
Q函数
你会发现目前为止我们一直盯着价值方程 $V(s)$ 看。但做决策时，我们更关心的是：“在状态 $s$，做动作 $a$ 到底好不好？”
这就引入了 Q-Function (Action-Value Function), $Q(s, a)$。
$Q(s, a)$ 意思是：我现在站在 $s$，虽然我的策略可能让我往东，但我强行先往北走一步（动作 $a$），然后在此之后再按照策略走下去。这一套操作的总价值是多少？
如果按照最优价值方程来看，那么我们就可以得到最优Q函数：
$$ Q^*(s, a) = R(s) + \gamma \sum_{s'} P(s' | s, a) V^*(s') $$
继续刚才的米其林餐厅来帮助理解：服务员拿来了菜单，上面有两道菜：
- $a_1$：米其林招牌牛排
- $a_2$：白开水泡饭
那么如果你在现在的状态$s$强行选择点牛排($a_1$)，这顿饭能值多少分？大概率是100分，则这个分数就是$Q^*(a, a_1)$。相反，强行选择白开水泡饭($a_2$)可能就值10分。这就是$Q^*(a, a_2)$
$V$和$Q$之间存在一个非常美妙的层级关系：
$Q^*(s, a)$ 拆解了第一步：它等于“现在的奖励 $R(s)$” 加上 “做完 $a$ 以后到达的新状态 $s'$ 的最优价值 $V^*(s')$”。
$V^*(s)$ 是从所有可能的 $Q$ 里面挑最高的：
$$ V^*(s) = \max_{a} Q^*(s, a) $$这个公式代表，在这个状态$s$的价值“等于”我能做的所有动作中，那个评分最高的动作的价值。在我们的例子中，$100 = max(100, 10)$
什么意思？当你评估“坐在餐厅里($s$)有多好($V(s)$)”，你潜意识里其实就是在挑选菜单里最好的那道菜。因为菜单里有牛排，值100分，所以你觉得坐在餐厅里值100分。反之如果菜单里只有白开水，值10分，那你就觉得坐在餐厅里就只剩10分了。
我们把这个关系放到贝尔曼方程里看，一切豁然开朗。
1. $V^*(s)$ 的定义：
$$ V^*(s) = R(s) + \max_{a} \gamma \sum_{s'} P(s' | s, a) V^*(s') $$
把中括号里的东西拿出来，给个名字，就叫 $Q$。
$$ Q^*(s, a) = R(s) + \gamma \sum_{s'} P(s' | s, a) V^*(s') $$
现在你发现，
- $Q(s, a)$ 是特定动作 的价值：它把你第一步锁死了（必须做 $a$），后面再走最优。
- $V(s)$ 是“最佳”的价值：它第一步就让你自由选择（选 max）。
那么既然$V$就是$Q$的最大值，那么我们只算$V$不就好了？搞个$Q$出来是不是多此一举？
不是。我们引入$Q$的目的是去模型化。这直接导向了后面我们要讲的Q-learning。
如果你只有$V(s)$，如果你想做出抉择是A是B，你就需要计算$R + \gamma \sum P(s'|s, A) V(s')$ vs. $R + \gamma \sum P(s'|s, B) V(s')$。
你发现你必须知道$P$转移概率才能做出决策。如果你不知道世界的物理引擎如何运作，你就没法做决策。
而如果我们有$Q(s, a)$，做决策只需要比较$Q(s, A)$和$Q(s, B)$即可。你不需要知道$P$，也不需要知道$R$的具体公式。只需要比较两个动作的得分，你就可以做出决策了。
价值迭代
我们已经拥有了$V^*$和$Q^*$的数学定义，即贝尔曼最优方程，那么接下来问题是，我们如何算出这些数？
首先我们先带入上帝视角，来想象一下：
回顾贝尔曼最优方程：
$$ V^*(s) = \max_a [ R(s) + \gamma \sum P(s'|s,a) V^*(s') ] $$
这是一个方程组。如果你有 100 个状态，这就是 100 个联立方程。
但讨厌的是里面有个 $\max$。这是一个非线性操作，导致线性代数（矩阵求逆）解不了它。
那么既然解不出来，我们就用迭代来“猜”。
- Day 0: 假设所有状态的价值都是 0。$V_0(s) = 0$。
- Day 1: 根据 Day 0 的价值，算一遍贝尔曼方程，更新所有状态的价值，得到 $V_1(s)$。
- 这时，那些能直接拿到奖励 $R$ 的状态（比如悬崖边的咖啡），价值率先变成了正数。
- Day 2: 根据 $V_1(s)$ 再算一遍，得到 $V_2(s)$。
- 这时，那些邻近奖励点的状态，发现“咦，我旁边那个格子变值钱了”，于是它们的价值也开始上升。
- ... Repeat: 无限重复。
你可以发现价值就像热量一样，从有奖励 ($R$) 的地方开始，通过贝尔曼方程这个介质，一步步向四周扩散。
只要 $\gamma < 1$，这个过程数学上保证收敛。最终 $V_k$ 会变成 $V^*$。这就是 Value Iteration 算法。
上帝视角看起来很完美啊，但之所以叫上帝视角，是因为但它有一个极其苛刻的前提：计算时，你必须知道 $P(s'|s, a)$ 和 $R(s)$。
这意味着你需要拥有这个世界的物理引擎说明书。在下围棋时，你知道“我落这颗子，棋局肯定会变成那样”（规则已知）。但在教机器人走路时，你不知道“我要它迈左腿，它会不会摔倒”（物理未知）。
如果不知道 $P$ 和 $R$，我们就没法算求和。怎么办？
Q-Learning
当我们不知道概率 $P$ 时，我们无法计算期望 $\sum P(s') V(s')$。
但我们可以做实验！虽然我算不出平均值，但我可以去试一次：
我站在 $s$，真的做一次动作 $a$，然后看老天爷把我扔到了哪个 $s'$，给了我多少 $r$。
这一次经历 Sample = $(s, a, r, s')$ 就是宝贵的数据。
更新公式
我们的目标是估计 $Q(s, a)$。根据 sample $(s, a, r, s')$，我们看到了一个“现实”的结果：
$$ \text{Target} = r + \gamma \max_{a'} Q(s', a') $$
这代表了基于这一次尝试，结合我们对下一站 $s'$ 的最高预估（$\max Q$），算出的“这一步到底值多少钱”。
但是，我们不能直接把 $Q(s,a)$ 设为这个 Target，因为这只是一次偶然的尝试，大概率包含噪音。
我们需要一点点相信这个新发现，同时保留一部分旧的记忆。这就是 Temporal Difference (TD) Learning：
$$ Q(s, a) \leftarrow (1 - \alpha) Q(s, a) + \alpha \left( r + \gamma \max_{a'} Q(s', a') \right) $$
$Q(s, a)$是你的旧记忆，而$( r + \gamma \max_{a'} Q(s', a'))$就是你的新发现，也就是$Target$。
其中的 $\alpha$ (Learning Rate) 代表学习率。
- $\alpha=1$：代表模型喜新厌旧，完全只看最新的这次结果。会导致结果不稳定
- $\alpha=0$：代表模型顽固不化，死守旧记忆。这导致模型永不学习
我们通常取一个小数值（如 0.1），表示“稍微修正一下我的认知”。
这就是 Q-Learning 的秘密：需要知道世界规则，只要不断尝试，不断用“新发现”去修正“旧估计”，最终 $Q$ 值会收敛到真理。
Online Q-learning
当我们在讲Q-Learning时，我们更多把它当作一个数学公式。但是真正上线的时候，(也就是Online)，智能体就会面临一个巨大的生存哲学问题，就是之前的探索或利用问题：
探索与利用 (Exploration vs. Exploitation)
在训练 Q-Learning 时，我们如何选择动作？
如果我们每次都选当前 $Q$ 值最高的动作，我们可能永远发现不了那条虽然开头难走、但后面有大宝藏的路。
因此，向你介绍 $\epsilon$-Greedy 策略。 策略的流程大概是：
- 扔一个骰子。
- 以 $\epsilon$ 的概率 (比如 0.1)： 闭眼瞎选一个动作（Exploration，去探索未知）。
- 以 $1-\epsilon$ 的概率 (比如 0.9)： 选当前 $Q$ 值最高的那个动作（Exploitation，利用现有知识）。
这样既保证了能利用好经验，又保证了总有机会去看看外面的世界。
因此，你的流程就大概是：
- 初始化$Q$表
- 进入游戏回合。在每一回合，你需要先：
- 用$\epsilon$-Greedy来选择动作$a$
- 所以我们执行$a$，观测到奖励$r$和新状态$s'$。
- 接下来更新Q值：$Q(s, a) \leftarrow (1 - \alpha)Q(s, a) + \alpha (r + \gamma max Q(s', all))$
- $s \leftarrow s'$
- 重复，直到游戏结束。
SARSA
SARSA代表 State - Action - Reward - State - Action，实际上代表的是一次更新所需要的数据链条：$s_t, a_t, r_t, s_{t+1}, a^{t+1}$
SARSA与常规的Q-Learning存在一些显著区别：
Q-Learning的更新公式是$Target = r + \gamma Q(s', a')$。如果使用Q-Learning，我们的心态大概是：“虽然我下一步可能会因为$\epsilon$来瞎走，但是在更新这张表时，我假设我下一步会走完美的那一步（$max$）”。
这样就导致Q-Learning的特点比较乐观，同样追求理论最优。那么SARSA呢？
SARSA的更新公式是：$Target =r + \gamma Q(s', a')$。与Q-Learning不同：“我真的去执行了下一步，发现我实际上选择了$a'$。无论是我手滑瞎选的，但既然我来都来了，我就用这步的Q值进行更新”。
SARSA的特点现实且保守。如果悬崖边上有一条路，那么Q-Learning 会贴着悬崖走，因为理论上最近；而 SARSA 会离悬崖远一点，因为它怕自己$\epsilon$探索时掉下去，那个 -100 的惩罚会真实的进入它的 Q 表。
Deep Q-Learning (DQN)
为什么这也要deep？
之前我们的Q-Learning用的都是查找表，状态$s$是行，动作$a$是列。在之前的迷宫游戏中状态只有寥寥几个，所以表格的尺寸不会太大。
但是假设你想要训练一个能够玩游戏的bot。你的状态是屏幕像素。假设屏幕分辨率仅有$84 \times 84$，每个像素都有256个颜色，那么你的状态数量就来到了惊人的$256^{84 \times 84}$。你的表格绝对存不下。
与其是存表，我们采用函数近似。我们训练一个卷积神经网络，这个网络的：
- 输入：游戏画面($s$)
- 模型用来提取状态的特征，最后
- 输出：每一个动作的Q值。
我们把 Q-Learning 的更新公式变成一个 Loss Function：
$$ Loss = (r + \gamma \max Q(s') - Q(s, a))^2 $$
用 SGD 去更新神经网络的参数，让网络输出的 Q 值越来越准。