n-step Bootstrapping简介

• 是MC方法和一步TD方法的结合。
• 是资格痕迹（eligibility traces，具体见第12章）的基础先验知识。

时序差分（Temporal-Difference）简介

• 时序差分是强化学习的核心观点。
• 时序差分是DP和MC方法的结合。
• MC要等一个完整的序列结束，比如玩21点扑克，直到玩完才能知道是胜是负；相反，时序差分每经历一步，都会更新价值函数，因为每一步都会观察到一个新的Reward，比如Grid World，每走一步都知道reward是什么。
• TD往往比MC高效；TD和MC都使用经验（experience）来解决预测问题。
• 所谓差分就是下一个时刻的估计和当前时刻的估计的差。

蒙特卡洛方法简介

使用蒙特卡洛方法不需要像DP一样，对环境要有完整的知识，而是通过经验去学习。所谓经验就是对状态、动作、奖励的采样（sample sequence）。

用sample的均值去近似期望。

DP方法简介

• 由于其大量的计算损耗，已经不实用，但理论上非常重要。
• 本书后续的所有方法可以看做想要取得和DP类似的效果；只不过是减少了计算或者假设没有完美的环境模型。
• 假设解决的问题是有限的MDP，即给定动作a，状态s，和奖励r，可以通过\(p(s',r|s,a)\)描述动态变化。

Agent和Environment的交互

• 学习者和决策者称为agent。
• agent交互的对象，外部环境，称为Environment。
• 在时刻t，agent的所处的环境用状态：\(S_t \in S\)表示，\(S\)是可能的状态集。假设agent采用了动作\(A_t\in A(S_t)\)，\(A(S_t)\)代表在状态\(S_t\)下可能的动作集。
• 到了下一个时刻t+1，agent收到了一个奖励：\(R_{t+1} \in R\)，并且发现自己处在一个新的state中：\(S_{t+1}\)。

k-armed Bandit Problem，K臂老虎机

问题描述：重复面临有k种选择的情况，每一次选择之后，都会收到一个reward。这个reward服从一个跟你的选择相关的分布。你的目标是，在选择t次后，找到最大的期望reward。

为什么叫K臂老虎机：有K个单臂老虎机，每个时间节点，你可以选择K个中任意一个老虎机选择按下它的臂，然后获得一个奖励。目标自然是多次选择之后的累计奖励最大。