强化学习简记
Table of Contents
起因：在实验室的书架上捞到一本强化学习（Richard & Andrew），简单记录一下笔记。享受线性阅读和手打笔记的乐趣。
导论
强调这本书是研究交互学习中的计算性方法，而不是直接建立关于人或动物如何学习的理论。
试错和延迟收益是强化学习的两个最重要最显著的特征。
当我们在提到强化学习（或者机器学习）的时候，要尤其注意这既表示一个问题，也表示解决问题的方法（甚至还表示一个领域）。不能混淆。
与监督学习不同，在一个未知领域中的交互问题场景下，若想要做到收益最大，智能体必须能够从自身的经验中学习。与无监督学习也不同，强化学习的目标在于最大化收益信号，而不是找出数据的隐藏结构。
强化学习有其独特的挑战：“试探”与“开发”的折中权衡。这个困境至今仍未被解决。另外一个关键的特征是明确了目标导向的智能体与不确定的环境交互这整个问题，通过感知环境的各个方面，选择动作来影响它们所处的环境。强化学习既可以涉及规划也可以涉及监督学习，因而如果想要有效地进行强化学习算法的研究，必须对自问题进行单独的考虑和研究。
强化学习和其他工程与科学学科之间有良好的互动，比如强化学习利用参数近似法解决了运筹学和控制论的研究中经典的“维度灾难”的问题。它和神经科学和心理学之间也有很强的相互作用。
曾经基于一般规则的方法，比如搜索或学习，被定性为“弱方法”，而基于知识的方法则被称为“强方法”。强化学习研究无疑在追求更简单的人工智能普适原则。
强化学习有四个核心要素：策略，收益信号，价值函数，（以及对环境建立的模型）。
- 策略是强化学习智能体的核心，是环境状态到动作的映射。它可能是简单的查找表，也可以是一个复杂的搜索的过程。一般来说，策略可能是环境状态和智能体所采取动作的随机函数。
- 收益信号是强化学习问题中的目标。收益信号表明了在短时间内什么是好的。
- 价值函数表示了从长远角度来看什么是好的。状态的价值是一个智能体从这个状态开始，对将来累积的总收益的期望。
从某种意义上来说，收益更加重要，而收益预测的价值次之。然而，在制定或者评估策略的时候，我们更关心的是价值。动作是基于对价值的判断做出的，但是确定价值的难度要比确定收益难得多。收益基本上是由环境直接给予的，但是价值必须综合评估，并根据智能体在整个观察过程中观察到的收益序列重新估计。事实上，价值评估方法才几乎是所有强化学习算法中最重要的组成部分。
- 对环境建立的模型是预测外部环境的下一个状态和下一个收益。环境模型会被用于做规划。简单的无模型方法是直接地试错，现代强化学习已经学会使用模型来进行规划。
强化学习非常依赖“状态”的概念。状态既作为策略和价值函数的输入，又作为模型的输入与输出。一般来说，可以非正式地思考状态的含义，并且把它理解为当前智能体可知的环境信息。这本书不处理构建状态信号的问题，并不是因为状态的表征不重要，而是希望专注于策略问题。
这本书对价值函数的估计进行了大量的讨论，但是一些优化算法，比如遗传算法、遗传规划、模拟退火算法以及其他算法也可以用来解决强化学习问题，而不用显式地估计价值函数。这些进化方法采用了大量静态策略，每个策略在扩展过的较长时间内与环境的一个独立实例进行交互，然后产生下一代。这类算法在当个个体的生命周期中不学习。如果决策空间足够小，或者可以很好地结构化地找到好的策略，或者智能体不能精确感知环境状态，那么进化方法是有效的（或者有优势的）。
然而，进化方法忽视了强化学习问题中的一些有用结构：忽略了索求策略是状态到动作的函数这一事实，也没有注意个体在生命周期内的状态和动作的迭代。这本书认为进化方法就其自身而言不适合强化学习问题，因此不介绍。
例子：井字棋。我们会将在贪心动作之后得到的状态所对应的价值“回溯更新”到动作之前的状态上。更准确地说，是对早先的状态的价值进行调整，使其更接近于后面的状态对应的价值。设 $S_t$ 表示在贪心动作之前的状态，$S_{t+1}$ 为转移之后的状态。价值函数用 $V(S_t)$ 来表示。那么：
$$ V(S_t) \gets V(S_{t+1}) + \alpha \Big [ V(S_{t+1}) -V(S_t) \Big] $$$\alpha$ 称为步长参数，会影响学习速率。更新规则是时序差分的一个特例。如果步长参数随着时间的推移逐渐减小，对于任意固定对手，方法会收敛于最优策略下每个状态下真正的获胜概率。
此时再和评估策略的进化方法进行比较：进化方法会忽略博弈中间的过程，进而当玩家获胜时，误认为这次游戏中的所有动作都有功劳。而学习价值函数的过程利用了博弈过程中的可用信息。即使不用对手的模型，也不用显示地搜索所有可能的未来状态与动作的序列，简单的强化学习玩家也能针对短视的对手设置多步陷阱。
甚至强化学习理论也适用于连续时间问题。
在一些场景下，神经网络为程序提供了从其经验中进行归纳的能力，因此在新的状态中，它根据保存的过去遇到的相似状态的信息来选择动作，并由神经网络来做出最后决策。在大的状态集中强化学习系统能起到多达作用，与它从过去的经验中进行总结推广的能力密切相关。对于这些问题，神经网络和深度学习并不是唯一的，也不是最好的方法。
可以先学习无模型的方法，再学习如何将他们作为更复杂的有模型方法的组成部分。
关于左右互搏、对称性、贪心策略的，还有试探性学习可以进行更深入的讨论。
强化学习是第一个严格意义上的解决从环境互动中学习以达到长期目标这一计算问题的领域。
DOTO: 阅读强化学习早期历史
[P1] 代表表格型求解方法
[P1] 多臂赌博机
一个 $k$ 臂赌博机问题
考虑如下问题：你要重复地在 $k$ 个选项或动作中进行选择。每次做出选择，你都会得到一定数值的收益，收益由选择的动作决定的平稳概率分布产生。目标是在某一段时间内最大化总收益期望。也可以称之为老虎机。
$k$ 个动作中的每一个在被选择时都有一个期望或者平均收益，称之为动作的价值。记动作 $A_t$ 和收益 $R_t$，对任一动作 $a$ 的价值记作 $q_*(a)$ 是给定动作 $a$ 时收益的期望：
$$ q_*(a):=\mathbb{E}[R_t|A_t=a] $$我们将对动作 $a$ 在 $t$ 时刻的价值的估计记作 $Q_t(a)$，我们希望它接近 $q_*(a)$。
在 $k$ 臂赌博机问题和相关问题中，有很多复杂方法可以用来平衡开发和试探，但是这些方法中的很多都对平稳情况和先验知识做出了很强的假设。但在实际问题中，这些假设要么难以被满足，要么无法被验证。在这本书中我们更关心的是要不要去平衡它们。
动作-价值方法
一种估算价值的方法是根据计算实际收益的平均值：
$$ Q_t(a) :=\frac{\sum_{i=1}^{t-1}R_i\mathbb{I}_{A_i=a}}{\sum_{i=1}^{t-1}\mathbb{I}_{A_i=a}} $$称这种方法为平均采样方法，这是最简单的一种估值方法。
接下来我们采用贪心 $A_t:=\argmax _a Q_t(a)$ 来选择动作。如果偶尔采用 $\varepsilon$ 的概率来等概率随机选择，称为 $\varepsilon$-贪心。
10 臂测试平台
对于 10 个选择，每个选择的均值 $q_*(a)$ 从一个 0-1 高斯分布中生成，每个实际收益从 $\mathcal{N}(q_*(a),1)$ 中生成（平稳的情形）。
TODO: 写代码验证。取不同的 $\varepsilon$，甚至变化的 $\varepsilon$，比如可以考虑随着时间递减 $\varepsilon$。
增量式实现
对于上面提到的平均采样方法，为了减少占用的内存，推导递推公式：
$$ \begin{aligned} Q_{n+1} &= \frac{1}{n}\sum_{i\in 1..=n}R_i \\ &=\frac{1}{n}\Big(R_n + (n-1)Q_n \Big) \\ &=Q_n+\frac{1}{n}[R_n-Q_n] \end{aligned} $$注意到这个形式和我们第一章井字棋更新估值函数的形式是一致的，这里的步长为 $1/n$，更一般地，我们记步长为 $\alpha_t(a)$。
跟踪一个非平稳问题
上面我们讨论的都是平稳的，即收益的概率分布不随着时间变化的赌博机问题。但当我们遇到非平稳的强化学习问题时，给近期的收益赋予比过去很久的收益更高的权值就是一种合理的处理方式。最简单的方法是使用固定步长（如上文所述），展开后是 $Q_{n+1}$ 是关于 $R_i$ 的加权平均和，准确来说是指数近因加权平均。
另外，对于 $\alpha_n(a)=1/n$，大数定律保证它可以收敛到真值。随机逼近理论中的一个著名结果给出了保证收敛概率为 1 的所需条件（Robbins–Monro）
$$ \sum _{n=1} ^{\infin} \alpha_n(a) = \infin \land \sum _{n=1}^{\infin} \alpha^2_n(a) \lt \infin $$TODO: 补充新的一页来给出 Robbins–Monro 条件的理论与证明。
第一个条件需要保证足够大的步长，克服任何初始条件或随机波动。第二个条件保证最终步长变小，以保证收敛。
尽管在理论中常常用到，但是符合这个条件的步长参数序列往往收敛得很慢，而且或者需要大量调试才能得到一个满意的收敛率。
TODO: 编程证实采用采样平均方法解决非平稳问题的困难。使用 10 臂测试，其中所有 $q_*(a)$ 初始值相等，然后进行随机游走。在每一步，所有的 $q_*(a)$ 加上一个 $\mathcal{N}(0,0.01)$ 生成的增量。对比：(1)采样平均-增量步长计算(2)常数步长($\alpha=0.1$)-动作-价值。$\epsilon=0.1$
乐观初始值
初始值可以设置预期的收益的先验知识。此外，设置一个乐观的初始值也容易让学习器感到“失望”，从而转向其他的动作，进而导致所有动作在估计值收敛之前都被尝试了好几次，系统会进行大量的试探。
乐观初始值在开始可能会表现得很差，但是随着时间的推移，试探的次数逐渐减少，它也会表现得更好。这在平稳问题中非常有效。但它不太适合非平稳问题，因为它试探的驱动力是暂时的。采样平均也是把开始时间当作一个特殊的时间点，用相同权重去平均后续的收益。但是事实上，任何仅仅关注初始条件的方法都不太可能对一般的非平稳情况有帮助，因为开始时刻只出现一次。
无偏恒定步长技巧
平均采样相较于恒定步长的好处在于，它不会像恒定步长那样产生偏差。然而平均采样在非平稳问题上表现得很差。一种可行的，利用了恒定步长在非平稳过程中的优势并且避免了它的偏差的方法是：针对某个特定动作的第 $n$ 个收益
$$ \begin{aligned} \beta _n &:= \alpha / \bar{o} _n \\ \bar{o}_n &:= \bar{o}_{n-1} +\alpha (1-\bar{o}_{n-1}) \end{aligned} $$基于置信度上界的动作选择
upper confidence bound 置信上界
$$ A_t:= \argmax _a \Big [ Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}} \Big] $$其中 $N_t(a)$ 表示在时刻 $t$ 之前 $a$ 动作被选择的次数。
TODO: 解释尖峰及其出现时刻
梯度赌博机算法
考虑对每一个动作 $a$ 学习一个数值化的偏好函数 $H_t(a)$。利用这个 $H_t(a)$ 和玻尔兹曼分布确定动作概率：
$$ \Pr\{A_t=a\} := \frac{e^H_t(a)}{\sum_{i=1}^ke^{H_t(i)}} := \pi_t(a) $$$\pi_t(a)$ 表示被选择的概率。进而提出一种自然学习算法：当选择动作 $A_t$ 并获得收益 $R_t$ 后，偏好函数的更新方式为
$$ \begin{aligned} H_{t+1}(A_t) &:= H_t(A_t) + \alpha (R_t - \bar{R} _t)(1-\pi_t(A_t)), \\ H_{t+1}(a) &:=H_t(a) -\alpha (R_t - \bar{R} _t)\pi_t(a), \quad a\neq A_t \end{aligned} $$其中 $\alpha$ 是步长，$\bar{R}_t$ 表示在时刻 $t$ 内所有收益的平均值，作为比较收益的基准项。
通过随机梯度上升实现梯度赌博机算法
在精确的梯度随机上升算法中，每一个动作的偏好函数 $H_t(a)$ 与增量对性能的影响成正比。
$$ \begin{aligned} H_{t+1}(a)-H_t(a) &= \alpha \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} \\ \mathbb{E}[R_t] :&= \sum_x \pi_t(x)q_*(x) \end{aligned} $$当然，因为 $q_*(x)$ 未知，因此不可能实现真正精确的随机梯度上升算法。注意到 $\sum_x\pi_t(x) = 1$，因而 $\sum _x \partial \pi_t(x)/\partial H_t(a) = 0$，所以：
$$ \begin{aligned} \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} &= \sum_x q_*(x) \frac{\partial\pi_t(x)}{\partial H_t(a)} \\ &=\sum_x (q_*(x)-B_t) \frac{\partial\pi_t(x)}{\partial H_t(a)} \\ &=\sum_x \pi_t(x) \frac{(q_*(x)-B_t) \frac{\partial\pi_t(x)}{\partial H_t(a)}}{\pi_t(x)}\\ &=\mathbb{E}\Big [(q_*(A_t)-B_t)\frac{\partial\pi_t(A_t)}{\partial H_t(a)}/{\pi_t(A_t)} \Big]\\ &=\mathbb{E}\Big [(R_t-\bar{R}_t)\frac{\partial\pi_t(A_t)}{\partial H_t(a)}/{\pi_t(A_t)} \Big] \end{aligned} $$关于最后一步的解释：