在线学习理论：后悔界分析

在线学习（Online Learning）是研究序列决策问题的理论框架，与强化学习有密切联系。¹

问题框架

在线学习设置

在在线学习中，学习者在每个时刻 $t$ 做出决策 $a_t\in \mathcal{A}$，然后收到损失 $l_t(a_t)$。目标是最小化累积损失或后悔。

累积损失：$L_T={\sum }_{t=1}^T{l}_t(a_t)$

后悔（Regret）：与最优固定策略的比较
${\text{Regret}}_T=L_T-{\min }_{a^{\ast }\in \mathcal{A}}{\sum }_{t=1}^T{l}_t(a^{\ast })$

与批量学习的对比

方面	在线学习	批量学习
数据	流式、顺序到达	一次性获取
目标	最小化累积损失/后悔	最小化期望损失
评估	累积后悔	泛化误差
适应能力	强	弱

---

经典在线算法

Follow-the-Leader (FTL)

FTL算法在每个时刻选择历史累积损失最低的策略：

$a_t=\arg {\min }_{a\in \mathcal{A}}{\sum }_{i=1}^{t-1}{l}_i(a)$

问题：FTL在某些情况下表现不稳定，可能过度适应最近的损失。

Follow-the-Regularized-Leader (FTRL)

FTRL在目标函数中添加正则化项：

$a_t=\arg {\min }_{a\in \mathcal{A}}\left[{\sum }_{i=1}^{t-1}{l}_i(a)+R_t(a)\right]$

其中 $R_t(a)$ 是正则化函数（通常选择强凸函数）。

常见正则化：

正则化	函数形式	特点
${\ell }_2$ 正则化	$\frac{\eta }{2}\Vert a{\Vert }_2^2$	平滑、闭式解
${\ell }_1$ 正则化	$\eta \Vert a{\Vert }_1$	稀疏性
Entropy 正则化	$\eta {\sum }_{a}a\log a$	概率分布

指数加权平均 (EWA)

EWA维护一个策略的加权分布：

$w_t^{(a)}\propto \exp \left(-\eta {\sum }_{i=1}^{t-1}{l}_i(a)\right)$

概率更新公式：
$p_t(a)=\frac{\exp (-\eta {\sum }_{i=1}^{t-1}{l}_i(a))}{{\sum }_{a^{\prime }}\exp (-\eta {\sum }_{i=1}^{t-1}{l}_i(a^{\prime }))}$

实现：

import numpy as np
 
class ExponentialWeightedAverage:
    def __init__(self, n_actions, eta=0.1):
        self.n_actions = n_actions
        self.eta = eta
        self.loss_sum = np.zeros(n_actions)
        self.t = 0
    
    def select_action(self):
        # 计算权重
        weights = np.exp(-self.eta * self.loss_sum)
        weights /= weights.sum()
        return np.random.choice(self.n_actions, p=weights)
    
    def update(self, action, loss):
        self.loss_sum[action] += loss
        self.t += 1
    
    def get_distribution(self):
        weights = np.exp(-self.eta * self.loss_sum)
        return weights / weights.sum()

---

后悔界分析

后悔界的定义

后悔界 ${\text{Regret}}_T=O(T^{\alpha })$ 描述算法性能相对于最优策略的增长速度。

后悔级别	后悔界	意义
常数	$O(1)$	与固定最优策略同级别
对数	$O(\log T)$	极快的适应速度
次线性	$O(\sqrt{T})$	随时间推移后悔占比减少
线性	$O(T)$	最差情况

Hedge算法

Hedge算法是EWA的离散动作版本：

定理（Hedge后悔界）：
$\mathbb{E}[{\text{Regret}}_T]\le \eta {\sum }_{a=1}^K{L}_T(a)+\frac{\ln K}{\eta }$

最优学习率选择 $\eta =\sqrt{\frac{\ln K}{T}}$ 可得：
$\mathbb{E}[{\text{Regret}}_T]\le 2\sqrt{T\ln K}$

---

对偶平均法 (Dual Averaging)

在线凸优化

当损失函数是凸函数时，可以使用对偶平均法（也称次梯度下降的在线版本）。²

更新公式：
$x_{t+1}={\text{Proj}}_{\mathcal{X}}\left({\sum }_{i=1}^t{g}_i\right)$

其中 $g_t\in \partial f_t(x_t)$ 是次梯度。

遗忘因子

引入遗忘因子 ${\eta }_t$：
$x_{t+1}={\text{Proj}}_{\mathcal{X}}\left({\eta }_t{\sum }_{i=1}^t{g}_i\right)$

---

神经网络在线学习

元学习视角

将在线学习与元学习结合，神经网络可以快速适应新任务。³

基本框架：

class MetaOnlineLearner:
    def __init__(self, model, lr=0.01, meta_lr=0.001):
        self.model = model
        self.lr = lr
        self.meta_lr = meta_lr
        self.optimizer = torch.optim.Adam(model.parameters(), lr=lr)
        self.task_losses = []
    
    def online_update(self, x, y):
        # 计算当前任务的损失
        loss = self.model.loss(x, y)
        
        # 一阶梯度更新
        grad = torch.autograd.grad(loss, self.model.parameters())
        with torch.no_grad():
            for p, g in zip(self.model.parameters(), grad):
                p -= self.lr * g
        
        self.task_losses.append(loss.item())
        
        # 元更新：调整学习率
        if len(self.task_losses) > 1:
            improvement = self.task_losses[-2] - self.task_losses[-1]
            self.lr = max(0.001, self.lr * (1 + self.meta_lr * improvement))
    
    def adapt_to_task(self, support_x, support_y):
        """在支持集上快速适应"""
        for _ in range(5):
            loss = self.model.loss(support_x, support_y)
            grad = torch.autograd.grad(loss, self.model.parameters())
            with torch.no_grad():
                for p, g in zip(self.model.parameters(), grad):
                    p -= self.lr * g

持续适应能力

持续适应能力（Continual Adaptation）是评估在线学习算法的重要指标。

评估指标：

指标	定义
遗忘率	在旧任务上性能的下降
前向迁移	在新任务上利用旧知识
后向迁移	改善旧任务的性能

---

与强化学习的联系

Bandit问题

MAB问题是在线学习的一个特例：

$l_t(a)=-r_t(a)$

优化累积奖励等价于最小化负奖励。

上下文老虎机

上下文老虎机可以形式化为在线凸优化：

$w_t=\arg {\min }_w{\sum }_{i=1}^{t-1}⟨\nabla l_i(w),w⟩+R(w)$

---

实践指南

学习率选择

场景	建议学习率
Hedge (有限动作)	$\eta =\sqrt{\frac{\ln K}{T}}$
FTRL (凸函数)	${\eta }_t=O(1/\sqrt{t})$
神经网络	自适应学习率 (Adam等)

梯度裁剪

为防止梯度爆炸，可以使用梯度裁剪：

torch.nn.utils.clip_grad_norm_(model.parameters(), max_norm=1.0)

---

参考资料

---

相关链接

• 多臂老虎机基础 — Bandit问题的经典算法
• 探索-利用权衡 — RL中的探索策略
• 上下文强化学习 — 上下文Bandit与RL的联系
• MDP基础 — 马尔可夫决策过程

Footnotes

1. Cesa-Bianchi & Lugosi, “Prediction, Learning, and Games”, 2006 ↩

2. Shalev-Shwartz, “Online Learning and Online Convex Optimization”, Foundations and Trends in Machine Learning, 2012 ↩

3. Finn et al., “Meta-Learning and Universally Weighted Optimization”, arXiv, 2017 ↩