状态转移概率一般是不知道的，所以我们需要 model-free 的方法，如 MC 和 TD

蒙特卡洛方法（MC）

$\epsilon$-贪心策略：

贪心动作选择概率：1 - $\epsilon +\frac{\epsilon }{|A|}$
非贪心动作选择概率： $\frac{\epsilon }{|A|}$
这就是 $\epsilon$-贪心策略

策略评估

s0, a0, r1, s1, a1, r2, s2, a2, … rT, sT（收集很多长度为 T 的 episode，使用任意 $\epsilon$
-软性策略产生）
构造 hash-map
s0 -> G1, G2, …
s1 -> G1’, G2’, …
s2-> G1’‘, G2’', …
每个 key 下的 G 取平均（大数定理），就是策略评估。
需要注意的是，Gt = r + $\gamma$
Gt+1，这种递归表示，从后往前计算更快。
但是要满足无穷多 episode 和 试探性出发假设的条件，才能准确策略评估，但这样无穷多 episode 效率太低了，我们可以采用类似价值迭代和异步价值迭代的方法避免无穷多 episode。

策略改进

使用 $\epsilon$-贪心策略，同样满足策略改进定理。且对 $\forall s \in S, a \in A, $ 有 $ \pi(a|s) > 0$ ，是一个软性策略，避免试探性出发假设。

同轨策略 MC 控制

行动策略（用来采样) = 目标策略（用来优化，我们想要的最终策略），所以必须都是软性策略。
控制指的是 PE + PI 两步过程。

离轨策略 MC 控制

行动策略 $\ne$目标策略，所以只要保证行动策略是软性策略，目标策略可以是贪心策略。
实现的方法：重要性采样，因为重要性采样的原因，目标策略和行动策略生成的 episode 必须保证相同，如果非贪心的行为比较普遍，则会降低学习速度。

增量式更新

这个很好理解，我们不必须等很多 episode 采样完之后再进行平均（同轨策略不存在这个问题，因为每次采样完* 1/n 就可以计算平均）。v’ 代表采样一次得到 g 之后的新平均值

$$v^{\prime }\leftarrow \frac{(n-1)\ast v+g}{n}=v+\frac{1}{n}\ast (g-v)$$

同轨策略不存在 g 权重不同的情况，把离轨策略的权重加上就可以得到离轨策略增量式更新：
$c\leftarrow c+w$
$v‘\leftarrow v+\frac{w}{c}(g-v)$（1）

常量 $\alpha$ 更新

从平均的角度，我们得到了增量式更新的表达试，我们从另一个角度来 （1）式：
v 是我们想要得到的期望回报，g-v 是 error， $\frac{w}{c}$ 替换成 $\alpha$ ，如果 error 大于 0，我们应该增加 v ，小于 0 我们应该减小 v ，那么多次后，就可以接近我们的的期望回报。
$v\leftarrow v+\alpha (g-v)=（1-\alpha ）v+\alpha g$

我看可以考到 $\alpha$ = 0，我们完全不会更新 v ，只考虑现在， $\alpha =1$ ，我们只考虑未来， $\alpha$ 保持不变就是所谓的常量 $\alpha$ 更新。
补充：虽然 v 可以通过 pi 和 q 求出来，但是实际上 PE 和 PI 是分开的，所以一般实践上我们更关心的是 q，后面介绍 TD 算法的时候，就把 v 换成 q 了。（DRL 的神奇之处，神经网络可以直接求 v，所以 PPO 我们看到了新的定义，advantage = q - v)。

时序差分（TD）

根据常量 $\alpha$更新，用 bootstrap 的思想可以很简单的推出时序差分的常用算法

Sarsa（同轨）

• 策略改进（把策略改进提前实现起来更简单，也可以像 MC 那样使用任意 $\epsilon$-策略采样）

$\pi \leftarrow \epsilon$-greedy(Q) （目标策略）

• 策略评估

$\pi \leftarrow \epsilon$-greedy(Q) （行动策略）

$$q(s_{t+1},a_{t+1})\leftarrow q(s_t,a_t)+\alpha \underset{td-error}{\underbrace{\underset{td-target}{\underbrace{(r+\gamma q(s_{t+1},a_{t+1})}}-q(s_t,a_t))}}$$
(小写表示一次采样）所以 Sarsa 的核心就是每次采样变成了 （st, at, rt+1, st+1, at+1)，这也是算法名字的来源。

Q-learning（离轨）

• 策略改进（把策略改进提前实现起来更简单，也可以像 MC 那样使用任意 $\epsilon$-策略采样）
  贪心策略 （目标策略）
• 策略评估
  $\pi \leftarrow \epsilon$-greedy(Q) （行动策略）

$$q(s_{t+1},a_{t+1})\leftarrow q(s_t,a_t)+\alpha \underset{td-error}{\underbrace{\underset{td-target}{\underbrace{(r+\gamma ma{x}_{a}q(s_{t+1},a)}}-q(s_t,a_t))}}$$
(小写表示一次采样）
为什么这里没有用重要性采样，因为目标策略的序列和行动策略没关系，不像 MC off-policy 需要用行动策略的采样来评估目标策略的采样。（理解这点很重要）

期望 Sarsa（同轨）

期望 Sarsa 和 Sarsa 类似，只不过取了加权平均

• 策略改进（把策略改进提前实现起来更简单，也可以像 MC 那样使用任意 $\epsilon$-策略采样）
  $\pi \leftarrow \epsilon$-greedy(Q) （目标策略）
• 策略评估
  $\pi \leftarrow \epsilon$-greedy(Q) （行动策略）
  $$q(s_{t+1},a_{t+1})\leftarrow q(s_t,a_t)+\alpha \underset{td-error}{\underbrace{\underset{td-target}{\underbrace{(r+\gamma \sum _a\pi (a|s_{t+1})q(s_{t+1},a)}}-q(s_t,a_t))}}$$
  (小写表示一次采样）

参考

1. https://www.bilibili.com/medialist/play/97068901?from=space&business=space_series&business_id=594040&desc=1&spm_id_from=333.999.0.0
2. http://incompleteideas.net/book/RLbook2020.pdf
3. https://nbviewer.org/github/MathFoundationRL/Book-Mathmatical-Foundation-of-Reinforcement-Learning/blob/main/Lecture%20slides/L7-Temporal-difference%20learning.pdf