Offline-to-Online Learning in Linear Bandits

技术摘要：线性 Bandits 中的离线到在线学习

问题陈述
本文研究了随机线性 Bandit (stochastic linear bandit) 设置下的离线到在线学习 (offline-to-online learning) 问题。在这种场景中，学习者需要在给定的动作集 $\mathcal{A} \subset \mathbb{R}^d$ 中顺序选择动作，以在时间跨度 $n$ 内最大化累积奖励，同时可以利用预先存在的离线数据集 $\mathcal{D}$。该离线数据是通过固定的、非自适应的设计（确定性的动作计数）收集的，并遵循带有亚高斯噪声（subgaussian noise）的线性奖励模型。

核心挑战在于两个竞争目标之间的权衡：

1. 在线遗憾 (Online Regret, $R_n$)：最小化相对于最优动作 $\mu^*$ 的遗憾。标准的在线算法（如 LinUCB）依赖于乐观主义进行探索，虽然能实现次线性遗憾，但如果忽略了离线数据，可能会遭受较高的初始遗憾。
2. 离线遗憾 (Offline Regret, $R_n^{off}$)：最小化相对于离线数据集均值 $\mu_{off}$ 的遗憾。标准的离线算法（如 LinLCB）依赖于悲观主义来利用已知数据，从而确保性能接近 $\mu_{off}$，但由于缺乏探索，如果离线数据是次优的或时间跨度很长，会导致线性遗憾。

现有工作主要将这些机制分开讨论，或者侧重于多臂 Bandit (MAB) 问题，其中遗憾随动作数量扩展。本文旨在弥补结构化（线性）环境中的这一差距，在这些环境中，遗憾应当随维度 $d$ 而扩展，而非动作空间的大小。

方法论：LinOtO 算法
作者提出了 LinOtO (Linear Offline-to-Online)，这是一种通过管理探索预算 (exploration budget) 来动态平衡探索与利用的算法。该算法通过基于由离线和在线数据共同构建的置信集 $C_t$ 在两种策略之间进行切换来运行：

1. 置信集 (Confidence Sets)：算法维护一个最小二乘估计量 $\hat{\theta}_t$ 和一个围绕真实参数 $\theta^*$ 的置信椭球 $C_t$。该集合的半径结合了来自离线数据 ($\beta_{off}$) 和在线交互 ($\beta_t$) 的不确定性。
2. 乐观与悲观动作：
   • UCB 动作 ($U_t$)：在 $C_t$ 内使置信上限（Upper Confidence Bound）最大的动作。这促进了探索并降低了 $R_n$，但存在增加 $R_n^{off}$ 的风险。
   • LCB 动作 ($L_t$)：使置信下限（Lower Confidence Bound，具体指随时间变化的最小置信下限的最大值）最大的动作。这促进了对离线数据的利用，降低了 $R_n^{off}$，但可能增加 $R_n$。
3. 预算机制：
   • 算法定义了一个安全基准奖励 $r_b$，它源自于一个特定“安全”动作 $L_{off}$（仅由离线数据计算出的 LCB 动作）的奖励下界。命题 2 保证了以高概率而言，$L_{off}$ 接近 $\mu_{off}$。
   • 算法维护一个探索预算 $B(t)$，代表算法相对于基准 $r_b$ 的累积超额奖励。
   • 决策规则：如果 $B(t) > 0$，算法选择乐观动作 $U_t$（探索）。如果 $B(t) \le 0$，则选择悲观动作 $L_t$（利用）以积累预算。
   • 该机制确保算法仅在通过保持相对于离线基准的安全来“赚取”了探索权利时才进行探索。

核心贡献

1. 算法设计：本文提出了 LinOtO，这是首个专门为离线到在线线性 Bandit 设置设计的算法，它通过基于预算的切换机制同时平衡了 UCB 和 LCB 策略。
2. 理论保证：作者为两种指标建立了高概率遗憾界限：
   • 在线遗憾 ($R_n$)：定理 1 表明 LinOtO 实现了相对于最优动作的次线性遗憾。该界限包含一个依赖于时间跨度 $n$ 的项（类似于 LinUCB）以及一个依赖于离线数据质量的加性常数。如果离线数据对空间的覆盖良好，界限会得到改善。
   • 离线遗憾 ($R_n^{off}$)：定理 2 证明了相对于离线参考的遗憾随 $n$ 线性缩放，但随着离线样本数 $m$ 的增加而以 $O(1/\sqrt{m})$ 的速度下降。这与纯离线（悲观）方案的性能相匹配。
3. 帕累托权衡分析 (Pareto Tradeoff Analysis)：分析揭示了一个由参数 $\alpha$ 控制的可调权衡。增加 $\alpha$ 会倾向于在线性能（更接近 LinUCB），而减小 $\alpha$ 则倾向于离线性能（更接近 LinLCB）。

实验结果
在合成线性 Bandit 任务（维度 $d=20$, $|A|=100$）上的实证评估表明：

• 时间跨度敏感性：对于短时间跨度，LinOtO 追踪保守的 LinLCB 基准。对于长时间跨度，它会转向探索，实现与 LinUCB 相当的次线性遗憾。
• 离线数据质量：
  • 当离线数据集排除最优动作时，LinOtO 能够成功偏离次优的离线先验进行探索，最终超越 LinLCB（后者遭受线性遗憾），并随着离线数据量 $m$ 的增加而趋近于 LinUCB 的性能。
  • 当离线数据集包含最优动作时，LinOtO 收敛迅速，表现与 LinUCB 和 LinLCB 相当。
• 鲁棒性：算法始终表现于纯探索（LinUCB）与纯利用（LinLCB）这两个极端之间，并能根据问题参数进行自适应。

意义与主张
本文声称 LinOtO 有效地解决了结构化环境中“理解不足”的离线到在线权衡问题。与以往在 MAB 设置中的工作（例如 Sentenac 等人，2025）不同，这种方法利用线性结构确保遗憾随维度 $d$ 扩展，而非动作数量，使其适用于高维问题。

作者谦虚地指出，其框架目前假设固定设计（fixed-design）的离线数据，并且未考虑离线与在线数据之间的分布偏移或自适应日志策略。他们指出，解决这些局限性以及将该框架扩展到非线性设置，是未来研究的重要方向。这项工作为如何利用先验知识（提示、离线数据）来引导在线学习中的探索-利用权衡做出了贡献。