value_eval

值函数估计

​ 在前面我们进行了 MDP 的理论推导，可以发现 value-based 算法的核心在于值函数的估计，状态值函数 $V^\pi(s)$ 的定义为：

$$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k r_{t+k+1} \bigg| s_t = s \right]$$

一般而言有两种方法来估计这个式子：

蒙特卡洛方法与TD方法对比

蒙特卡洛（MC）方法

​ 蒙特卡洛方法（Monte-Carlomethods）是一类广泛的计算算法，下面将最朴素估计方式变为增量更新方式：

$$\begin{aligned} V^\pi_N(s) &= \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k r_{t+k+1} \bigg| s_t = s \right] \approx \frac{1}{N} \sum_{i=1}^N g_t^{(i)} \\ &= \frac{1}{N} \left(\sum_{i=1}^{N-1} g_t^{(i)} + g_i^{(n)}\right) \\ &= \frac{N-1}{N} V^\pi_{N-1}(s) + \frac{1}{N}g_i^{(n)} \\ &\overset{simplify}{\approx} (1 - \alpha) V^\pi_{N-1}(s) + \alpha g_i^{(n)} \end{aligned}$$

即更新方式为：

$$V(s) \leftarrow V(s) + \alpha [g_i - V(s)]$$

• 对于非稳定的问题（环境随时间改变）这种更新方式可以随时间快速动态改变

• 缺点在于计算 $G_t$ 的复杂度很高（计算瓶颈），而且需要完整轨迹后才能更新

• 由于 $G_t$ 的轨迹很长，导致的问题是方差 variance 很差

策略改变带来的重要性采样

​ 使用策略 $\mu$ 产生的累计奖励数据（$ [s_1, a_1, r_1, s_2, a_2, r_2, …, s_T] \sim \mu $）来评估策略 $\pi$，则更具重要性采样原理，在更新策略 $\pi$ 的时候需要根据 $\pi$ 与 $\mu$ 之间的重要性比率（importance ratio）对累计奖励 $g_t$ 加权。

每个片段乘以重要性比率：

$$g_{t}^{\pi/\mu} = \frac{\pi(a_t|s_t)}{\mu(a_t|s_t)} \frac{\pi(a_{t+1}|s_{t+1})}{\mu(a_{t+1}|s_{t+1})} ... \frac{\pi(a_T|s_T)}{\mu(a_T|s_T)} g_t$$

更新方式变为：

$$V(s) \leftarrow V(s) + \alpha [g_i - V(s)]$$

​ 存在的问题是：

• 无法在 $\pi$ 非零而 $\mu$ 为零时使用
• 重要性采样将显著增大方差（variance）

为了解决 variance 过大的问题，可以通过牺牲一部分的 bias 来换取小 variance

时序差分（TD）方法

​ 时序差分（Temporal Difference Learning）方法，结合MC的采样思想和动态规划的自（Bootstrapping）。使用价值函数进行更新，因此是天然的 model-free RL

$TD(0)$ 更新公式：

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

结合重要性采样的方法，$TD(0)$ 修正为：

$$V(s_t) \leftarrow V(s_t) + \alpha \left(\frac{\pi(a_t|s_t)}{\mu(a_t|s_t)} \left( r_{t+1} + \gamma V(s_{t+1}) \right) - V(s_t) \right)$$

偏差（Bias）/方差（Variance）的权衡

• 累计奖励 $g_t = r_t + \gamma r_{t+1} + \cdots + \gamma^{T-t} r_T$ 是 $ V^\pi(s_t) $ 的无偏估计（无 bias）

• 时序差分真实目标 $ r_t + \gamma V^\pi(s_{t+1}) $ 是 $ V^\pi(s_t) $ 的无偏估计

• 时序差分目标 $ r_t + \gamma V(s_{t+1}) $ 是 $ V^\pi(s_t) $ 的有偏估计（有 bias）

• 时序差分目标具有比累计奖励更低的方差（使用 bias 换取 variance）

  • 累计奖励——取决于多步随机动作，多步状态转移和多步奖励
  • 时序差分目标——取决于单步随机动作，单步状态转移和单步奖励

算法	更新公式	特点
$TD(0)$	$V(s_t) \leftarrow V(s_t) + \alpha \delta_t$	单步回溯
$TD(\lambda)$	引入资格迹进行多步混合更新	平衡偏差-方差
Q-Learning	扩展到动作值函数估计	处理控制问题