Learning as Approximation：把学习看成受控近似

很多 learning algorithms 第一眼看起来并不像一类东西。

Gradient descent 来自 optimization。Monte Carlo methods 更像 statistical estimation。Temporal difference learning 属于 reinforcement learning。Robbins-Monro stochastic approximation 听起来像 numerical analysis。Kalman filtering 又更接近 control 和 signal processing。

但如果把这些 update rules 放在一起看，我总会看到同一种数学习惯：

$$\begin{aligned} \text{new estimate} &= \text{old estimate} \\ &\quad + \text{step size}\times\text{correction}. \end{aligned}$$

最小的形式就是：

$$X \leftarrow X+\alpha(Y-X).$$

保留当前估计 $X$，拿它和某个 target 或 feedback signal $Y$ 比较，然后沿着 error 的方向移动一点点。不断重复。

这篇文章不是想说所有 learning algorithms 都是同一个东西。它们当然不是。Gradient descent 在优化 loss。Monte Carlo 在估计 return。Temporal difference learning 会从当前 value estimate 里 bootstrap。Q-learning 做的是 off-policy control。Kalman filtering 是 probabilistic state estimation。

我想表达的是一个更弱、但更有用的观点：很多 learning algorithms 都可以被理解成 controlled approximation under uncertainty。它们从一个不完美的估计开始，收到不完美的反馈，小心地修正，然后重复，直到 error 慢慢变成 structure。

学习的最小形式

在 neural networks、reinforcement learning 或 intelligence 之前，有一个更小的操作：从重复观测中估计某个未知量。

假设 $X$ 是当前估计，$Y$ 是新的观测。一个最基本的 correction rule 是：

$$X \leftarrow X+\alpha(Y-X).$$

$Y-X$ 是当前相信的东西和刚刚看到的东西之间的 error。Step size $\alpha$ 决定我们有多相信这次新信息。

如果 $\alpha$ 很大，estimate 反应很快，但也会很 noisy。如果 $\alpha$ 很小，estimate 更稳定，但适应会慢。这一个 tradeoff 里已经有很多 learning theory 的味道。

Running mean 就是这个形式：

$$\mu_{n+1}=\mu_n+\frac{1}{n+1}(x_{n+1}-\mu_n).$$

Exponential moving average 则使用固定 step size：

$$m_{t+1}=m_t+\alpha(x_t-m_t).$$

最简单的 learning algorithm 并不神秘。它就是不断修正一个 estimate。

通过误差修正

在 supervised learning 里，correction 通常来自 prediction error。

如果模型预测 $\hat{y}$，真实 target 是 $y$，那么 error 是：

$$y-\hat{y}.$$

LMS rule，也就是 delta rule，把这件事写得非常直接：

$$w_{t+1}=w_t+\alpha(y-\hat{y})x.$$

参数向量 $w$ 是当前 estimate。$(y-\hat{y})x$ 告诉我们，为了减小这个样本上的 prediction error，weights 应该怎样改。

Perceptron update 也有类似的味道。当一个样本被 misclassified 时：

$$w_{t+1}=w_t+\alpha yx.$$

模型把 mistake 变成 correction direction。这个 update 发生在 parameter space，而不是直接发生在 prediction space，但外层逻辑仍然一样：观察 feedback，计算 correction，移动当前 estimate。

通过损失函数修正

Gradient descent 把 error correction 从 scalar estimate 推广到了高维 parameter space。

它的 update 是：

$$\theta_{t+1}=\theta_t-\alpha\nabla_\theta L(\theta_t).$$

这看起来和 $X+\alpha(Y-X)$ 不太一样，因为 correction 现在变成了 gradient。但如果 loss 是 squared error：

$$L=\frac{1}{2}(Y-X)^2,$$

那么 correction direction 就和下面这个量成正比：

$$Y-X.$$

所以 gradient descent 可以被看成 error correction 的几何版本。我们不是直接朝一个可见 target 移动，而是沿着最能降低 loss 的方向移动。

Stochastic gradient descent 又加了一层 noise：

$$\theta_{t+1}=\theta_t-\alpha \widehat{\nabla_\theta L}(\theta_t).$$

Gradient 只来自一个 sample 或 mini-batch。SGD 因此就是一个 noisy approximation process。它每一步都看不到完整 objective surface，只能拿到一个 partial signal，小心走一步，然后继续。

随机近似

Stochastic approximation 给这个模式提供了更一般的数学语言。

一种常见形式是：

$$x_{t+1}=x_t+\alpha_t(h(x_t)+M_{t+1}),$$

其中 $h(x_t)$ 是平均意义上走向 solution 的方向，$M_{t+1}$ 是 sampling noise，$\alpha_t$ 是 step size。

在 Robbins-Monro 的设定里，目标通常是找到一个 root：

$$h(x^*)=0.$$

困难在于 $h(x)$ 不能被精确观测。我们只能拿到 noisy samples。于是算法看起来像是在追随 $h$，但每一步都会被 noise 干扰。

经典 step-size condition 是：

$$\sum_t \alpha_t = \infty,\quad \sum_t \alpha_t^2 < \infty.$$

第一个条件说，算法总共必须移动得足够多，否则到不了 target。第二个条件说，步子必须慢慢变小，否则 noise 会永远主导过程。

这是 learning as controlled approximation 最干净的数学版本之一：朝 solution 移动，但不要过度相信任何一次 noisy observation。

朝 fixed point 修正

Reinforcement learning 加入了一个新的复杂性：target 不一定是外部给定的 label。有时候 target 依赖当前 estimate。

对于 fixed policy，value function 满足 Bellman equation：

$$V^\pi = r^\pi + \gamma P^\pi V^\pi.$$

也就是：

$$V^\pi = T^\pi V^\pi.$$

这是一个 fixed-point equation。我们不是单纯拟合 labels，而是在找一个 value function，使得它经过 Bellman operator 之后保持不变。

这也是为什么 value-based reinforcement learning 不能简单当成普通 supervised learning。在 supervised learning 里，target 通常在模型外部。在 value learning 里，target 很可能来自模型自己对未来的当前估计。

动态规划

Dynamic programming 是 Bellman approximation 的 exact、model-based 版本。

在 value iteration 里，update 是：

$$V_{k+1}(s)=\max_a\left[R(s,a)+\gamma\sum_{s'}P(s'|s,a)V_k(s')\right].$$

在 fixed policy 的 policy evaluation 里：

$$V_{k+1}(s)=R^\pi(s)+\gamma\sum_{s'}P^\pi(s'|s)V_k(s').$$

这些公式直接使用 model：

$$P(s'|s,a),\quad R(s,a).$$

因为 transition probabilities 和 rewards 已知，dynamic programming 可以用 exact expectations 来应用 Bellman operator。它是没有 sampling noise 的 fixed-point iteration。

采样的 Bellman 近似

当 model 未知，或者直接使用 model 太贵时，reinforcement learning 就出现了。我们不再应用 exact Bellman operator，而是从 experience 中采样，并用 sample 构造 target。

外层模板回来了：

$$X \leftarrow X+\alpha(Y-X).$$

很多 RL algorithms 的主要区别，就是它们怎样定义 target $Y$。

Monte Carlo 预测

Monte Carlo prediction 使用完整 return：

$$V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t)).$$

这里：

$$Y=G_t.$$

Target 是从时间 $t$ 之后采样到的 return。

Temporal Difference 预测

TD prediction 使用一个真实 reward，加上对未来的 bootstrapped estimate：

$$V(S_t)\leftarrow V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t)).$$

这里：

$$Y=R_{t+1}+\gamma V(S_{t+1}).$$

Sarsa

Sarsa 用实际采取的下一个 action 来更新 action-value estimate：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)].$$

它的 target 是：

$$Y=R_{t+1}+\gamma Q(S_{t+1},A_{t+1}).$$

Q-learning

Q-learning 使用当前 value estimate 下 greedy 的下一个 action：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\max_a Q(S_{t+1},a)-Q(S_t,A_t)].$$

它的 target 是：

$$Y=R_{t+1}+\gamma\max_a Q(S_{t+1},a).$$

这些 algorithms 的主要区别，就是 $Y$ 是怎么构造出来的。

Algorithm	Current Estimate $X$	Target $Y$	Main Difference
Monte Carlo	$V(S_t)$	$G_t$	使用完整 sampled return
TD	$V(S_t)$	$R+\gamma V(S')$	从 next state bootstrap
Sarsa	$Q(S,A)$	$R+\gamma Q(S',A')$	使用实际 next action
Q-learning	$Q(S,A)$	$R+\gamma\max_a Q(S',a)$	使用 greedy next action

外层 update shape 很稳定。真正改变算法语义的是 target。

Monte Carlo 和 TD

Monte Carlo 和 TD 展示了一个基本 statistical tradeoff。

Monte Carlo 使用：

$$Y=G_t.$$

它等待真实 return。这个 target bias 较低，但 variance 较高，而且必须等 episode 结束后才能更新。

Temporal difference learning 使用：

$$Y=R_{t+1}+\gamma V(S_{t+1}).$$

这个 target 因为使用了当前 value estimate，所以有 bias；但它通常 variance 更低，也可以 online learning。

一句话总结：

Monte Carlo 相信 sampled future。TD 相信自己当前对 future 的估计。

两者没有绝对优劣。它们只是控制 approximation error 的不同方式。

Sarsa 和 Q-learning

Sarsa 和 Q-learning 说明，同样的 update shape 可以对应完全不同的 policy meaning。

Sarsa 使用：

$$R+\gamma Q(S',A').$$

其中 $A'$ 是 behavior policy 实际采取的 action。所以 Sarsa 是 on-policy。

Q-learning 使用：

$$R+\gamma\max_a Q(S',a).$$

这个 target 评估的是 greedy action，不管 behavior policy 实际做了什么。所以 Q-learning 是 off-policy。

因此，同一个 correction template 并不意味着同一种 learning semantics。Target 决定了正在被学习的东西。

为什么它可能有效

收敛性的故事通常结合两件事：contraction 和 step size。

当 $\gamma<1$ 时，很多 Bellman operators 是 contractions：

$$\|TV-TU\|_\infty \le \gamma \|V-U\|_\infty.$$

直觉上，contraction 会把 value functions 拉得更近。反复应用之后，estimate 会朝唯一 fixed point 移动。

Sampling 会引入 noise，所以 step size 很重要。更新步必须足够大，才能靠近 fixed point；但又不能太激进，否则 random samples 会主导整个过程。

这也是为什么 Bellman fixed-point theory 和 stochastic approximation 会自然地在 reinforcement learning 里相遇。

相邻的想法

这种 correction-and-approximation pattern 不只出现在 reinforcement learning。

在 bandit learning 里，一个 action 的 value estimate 可以这样更新：

$$Q_{n+1}(a)=Q_n(a)+\alpha(R_n-Q_n(a)).$$

在 Kalman filter 里，correction step 是：

$$\hat{x}_{t|t}=\hat{x}_{t|t-1}+K_t(z_t-H\hat{x}_{t|t-1}).$$

这就是 prediction 加上 gain 乘以 innovation。

EM algorithm 也是 iterative approximation：先估计 hidden structure，再更新 parameters，然后重复。它没有那么直接地落在 $X+\alpha(Y-X)$ 形式里，但它属于更广义的一类过程：把一个难以直接解决的问题，替换成一串更容易的 approximation steps。

Mirror descent 则通过改变 correction 发生的 geometry 来推广 gradient descent。“沿着改进方向移动”的思想还在，但 distance 和 update geometry 不一定再是 Euclidean。

重点不是把这些 algorithms 压扁成一个公式，而是看到 statistics、optimization、control 和 machine learning 之间共享的一种习惯。

类比危险的地方

共享 update shape 很有用，但也可能误导。

相同的形状不代表相同的保证。

Gradient descent 优化 loss。Monte Carlo 估计 expectation。TD 解决 bootstrapped fixed-point problem。Q-learning 做 off-policy control。Kalman filtering 做 probabilistic state estimation。EM 通过 latent-variable approximation 最大化 likelihood。

Deep reinforcement learning 让这个 warning 更明显。我们不再更新 table entries，而是在更新一个 function approximator：

$$Q_\theta(s,a).$$

这引入了 deadly triad：

• bootstrapping
• off-policy learning
• function approximation

每一项单独看在某些设定下都可以处理。但放在一起，就可能带来 instability。

所以 correction template 是一个 mental model，不是 proof。它帮助我们组织公式，但不能擦掉每个 algorithm 背后的 assumptions。

把学习看成受控近似

我一直会回到这句话：

Learning algorithms are disciplined ways of becoming less wrong.

它们从不完美的 estimate 开始，收到不完美的 feedback，然后谨慎地修正。有时候 correction 是 error。有时候是 gradient。有时候是 sampled return。有时候是 bootstrapped Bellman target。有时候是 state estimator 里的 innovation term。

Lens	What Learning Looks Like
Statistics	从 samples 中估计未知量
Optimization	沿着 objective surface 移动 parameters
Numerical analysis	迭代逼近 fixed point
Reinforcement learning	应用 sampled Bellman backups
Control theory	用 observed innovation 修正 prediction
Stochastic approximation	在 noisy feedback 下朝 solution 移动

学习不是魔法。它是在 uncertainty 下进行 approximation，并且足够谨慎地重复这个过程，让 error 慢慢变成 structure。