DP, MC and TD

三个方法可以看作对环境的要求逐渐放低，先给出一个总览

方法 核心思想 环境模型 完整 episode bootstrapping
DP 已知 Model 做 Bellman backup 需要 不需要 是
MC 完整采样回报 $G_t$ 更新 不需要 需要 否
TD 用一步采样 + 后继状态估计更新 不需要 不需要 是

DP

首先对于 DP 来说，因为我们要遍历所有状态转移，所以需要环境模型来给出 $P(s'|s,a)$，DP 的更新过程是使用 Bellman backup 来逐步更新状态值函数 $V(s)$ 直到收敛

$$ V_{\pi}(s_t) = \sum_a \pi(a|s_t) \sum_{s',r}\textcolor{red}{P(s',r|s_t,a)} [r + \gamma V_{\pi}(s')] $$

DP 的 Target 可以写成

$$ \mathbb{E}_{\pi} \left[ r + \gamma V_{\pi}(S_{t+1}) | S_t = s \right] $$

Monte Carlo

MC 更新不再需要环境模型，它的更新目标需要从完整的 episode 中计算得到 $G_t$

$$ G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k} $$

更新过程

$$ V(s_t) \leftarrow V(s_t) + \alpha (\textcolor{red}{G_t - V(s_t)}) $$

Temporal Difference

在 MC 的基础上，用一步采样来代替完整的 episode 来计算回报，TD 的更新目标是

$$ \mathbb{E}_{\pi} \left[ r + \gamma V_{\pi}(S_{t+1}) | S_t = s \right] $$

TD 的更新过程

$$ V(s_t) \leftarrow V(s_t) + \alpha (\textcolor{red}{r_{t} + \gamma V(s_{t+1}) - V(s_t)}) $$

其中，$r_t + \gamma V(s_{t+1}) - V(s_t)$ 是 TD error

这里介绍的是 TD(0)，当 TD 更新的 Step 越来越长直到和 episode 长度一致时，也就从 TD 算法过渡到了 MC 算法，

$$ TD(0) \rightarrow TD(\lambda) \rightarrow MC $$

TD Lambda

TD($\lambda$) 是 TD(0) 和 MC 的一个折中方案，它的更新目标是 $\lambda$ 加权的 n-step return

$$ G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)} $$

其中

$$ G_t^{(n)} = r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1} + \gamma^n V(s_{t+n}) $$

而且 $(1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} = 1$

前向视角更新

$$ v(s_t) \leftarrow v(s_t) + \alpha (G_t^{\lambda} - v(s_t)) $$

存在一个问题就是无法进行在线更新，我们需要等到未来几步的结果才能更新当前的状态值函数

为了解决这个问题，可以引入后向视角更新: 每一个 episode 开始时，初始化一个 eligibility trace $e(s) = 0$，每当访问一个状态 $s$ 时，就把 $e(s)$ 加 1，然后在每一步更新时，计算 TD error $\delta_t = r_{t} + \gamma V(s_{t+1}) - V(s_t)$，并按照下面的方式更新 eligibility trace

$$e(s) \leftarrow \gamma \lambda e(s) + \mathbb{I}(s = s_t)$$

最后对 所有状态 进行更新

$$V(s) \leftarrow V(s) + \alpha \delta_t e(s)$$

SARSA vs Q-learning

on policy (SARSA) 和 off policy (Q-learning) 的区别

$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha (r_{t} + \textcolor{red}{\gamma Q(s_t, \pi(s_{t+1}))} - Q(s_t, a_t)) $$

上面 SARSA 的更新使用的还是当前策略给出的 action 来计算 TD error

$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha (r_{t} + \textcolor{red}{ \gamma \max_a Q(s_{t+1}, a)} - Q(s_t, a_t)) $$

上面 Q-learning 的更新使用的是最优策略给出的 action 来计算 TD error

两种更新方式的区别造成了 SARSA 和 Q-learning 在 Cliff walking 中的表现差异

值函数估计

Value Function Estimation 是很重要的一个概念，因为当我们解决复杂问题的时候，状态空间 $\mathcal{S}$ 的维度直接爆炸，想要用一个 tabular 去记录每一个可能的 s 的 value 效率极低且不现实，所以用一个函数去近似这个 Value function 就十分重要

线性值函数估计

使用线性函数去近似 Value Function $\hat{V}(s, \theta) = w^t \phi(s)$

$$ J(\theta) = \sum_{s \in \mathcal{S}} (V^{\pi}(s) - \hat{V}(s, \theta))^2 $$

那么可以使用梯度下降来更新

$$ \frac{1}{2} \nabla_{\theta} J(\theta) = \sum_{s \in \mathcal{S}} (V^{\pi}(s) - \hat{V}(s, \theta)) \nabla_{\theta} \hat{V}(s, \theta) $$

带入线性函数的表达方式，更新过程可以写成

$$ w \leftarrow w + \alpha (\textcolor{red}{\text{target}} - \hat{V}(s, w)) \phi(s) $$

对于 MC 和 TD，他们的区别就在于 Target 的选择上，MC 的 Target 是 $G_t$，而 TD 的 Target 是 $r_{t} + \gamma \hat{V}(s_{t+1}, w)$

TD 是一个 semi-gradient 的方法 TD 的更新过程是一个 semi-gradient 的过程，我们在求梯度时，忽略了 Target 的部分
Bellman Operation & 不动点 Bellman Operation: $$ (\mathcal{T}_\pi V)(s) = \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma V(S_{t+1}) | S_t = s \right] $$

Bellman Operation 输入一个 function $V$，输出一个新的 function $\mathcal{T}_\pi V$，如果 $\mathcal{T}_\pi V = V$，那么这个 $V$ 就是一个不动点

从上面的定义可以很容易推断出，真实的 Value Function $V^\pi$ 就是 Bellman Operation 的不动点

TD 的更新过程就是在求解 Bellman Operation 的不动点（因为当 V 是不动点时， TD error 正好为 0）

Bellman Operation 的收敛性 $$ \mathcal{T}_\pi v = r_\pi + \gamma P_\pi v $$ 任意两个 Value Function $u$ 和 $v$，有 $$\begin{aligned} (\mathcal{T}_\pi u)(s) - (\mathcal{T}_\pi v)(s) &=\sum_{s'} P(s, s') [r + \gamma u(s') - r - \gamma v(s')] \\ & = \gamma \left| \sum_{s'} P(s, s') [u(s') - v(s')] \right| \\ & \leq \gamma \sum_{s'} P(s, s') |u(s') - v(s')| \\ & \leq \gamma \|u - v\|_\infty \end{aligned}$$

假设存在两个不动点 $u$ 和 $v$，那么有

$$\begin{aligned} \|u - v\|_\infty & = \|\mathcal{T}_\pi u - \mathcal{T}_\pi v\|_\infty \\ & \leq \gamma \|u - v\|_\infty \end{aligned}$$

因为 $\gamma < 1$，所以上面的不等式只能在 $\|u - v\|_\infty = 0$ 的时候成立，也就是说 $u$ 和 $v$ 是同一个函数，所以 Bellman Operation 的不动点是唯一的

收敛性证明

Monte Carlo

$$ G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k} $$

当我们使用一般的函数拟合 Value Function 时，MC 的更新过程是

$$ \hat{v}(s,w) = f_w(s) \quad J(w) = \frac{1}{2} \mathbb{E}[(G_t - \hat{v}(s,w))^2] $$

如果 $f_w$ 是线性的，那么 $J(w)$ 就是一个凸函数，MC 更新会收敛到全局最优解，但是一般情形下，$J(w)$ 是一个非凸函数，MC 更新只会收敛到满足 $\nabla J(w) = 0$ 的局部最优解