Bayesian Online Model Selection
贝叶斯在线模型选择
https://arxiv.org/pdf/2602.17958
摘要
的 Oracle 风格保证，其中 M 是基学习器的数量，是最优基学习器的遗憾系数， T 是时间范围。我们还在一系列随机强盗设置中对我们的方法进行了实证验证，展示了其与最佳基学习器具有竞争力的性能。此外，我们研究了在基学习器之间共享数据的效果及其在缓解先验误设（prior mis-specification）中的作用。
1 引言
随机强盗问题（stochastic bandit problem）是交互式决策的一个基础模型 [Lattimore and Szepesvári, 2020]。在每一轮交互中，学习器从几个动作中选择一个，每个动作都关联着一个未知的奖励分布，并观察从该分布中抽取的随机奖励。学习器的性能通常用遗憾（regret）来衡量：即所选动作的累积奖励与该环境中最佳可能策略的累积奖励之间的差值。目标是设计能够实现次线性遗憾（sublinear regret）的算法，确保随着学习器与环境交互次数的增加，其平均遗憾趋于消失。这个简单而强大的框架捕捉了从（部分）反馈中学习的本质，并且处于许多现实世界应用的核心，例如推荐系统、机器人技术和金融 [Silva et al., 2022; Ni et al., 2023; Klarich et al., 2024]。
在其贝叶斯公式化中，随机强盗问题假设未知奖励分布上存在一个先验分布，以捕捉关于环境的现有信念。这种视角催生了诸如 Thompson Sampling [Thompson, 1933; Russo et al., 2020] 等强大的算法，该算法通过从后验分布中采样并选择对采样实例最优的动作来诱导探索 [Agrawal and Goyal, 2012]。当可以通过易处理的后验推断（tractable posterior inference）来整合和更新先验知识时（例如在存在共轭先验的情况下），贝叶斯强盗特别具有吸引力。当共轭性不可用且精确推断难以处理时，人们通常诉诸近似方法：马尔可夫链蒙特卡洛（MCMC）方法，其渐近地逼近真实后验；或者确定性替代方案，如拉普拉斯近似（Laplace approximations）和变分推断（variational inference），它们提供了易处理的代理后验 [Shahriari et al., 2016; Mazumdar et al., 2020]。
在本文中，我们研究了最初在频率学派（frequentist）设定中引入的在线模型选择问题 [Agarwal et al., 2017; Pacchiano et al., 2020b; Marinov and Zimmert, 2021]。在该问题中，学习者被给定一组有限的 bandit 算法（“模型”），我们将其称为基学习器（base learners）。每个基学习器可能都适合不同的环境实例，例如，一个基学习器可能针对稀疏线性结构进行了调整，而另一个则针对低维广义线性奖励进行了优化。我们在贝叶斯（Bayesian）设定下研究这个问题，在交互开始时，环境是从一个已知的先验分布中采样的，并且学习者随时间与该固定实例进行交互。在每一轮中，学习者选择一个基学习器，遵循其策略选择一个动作，并观察产生的奖励。我们的目标是设计一种贝叶斯模型选择策略，该策略在贝叶斯遗憾（Bayesian regret）上具有预言机最优（oracle-best）保证：即在对从先验中抽取环境的期望下，学习者的遗憾与一个预言机（oracle）的遗憾具有竞争力；该预言机知晓实现的环境实例，并会针对该实例固定选择单个最佳的基算法。
现有的贝叶斯遗憾最小化方法，例如 Thompson 采样（TS）及其变体，在随机 bandit 问题中表现出强大的实证性能并享有次线性遗憾保证 [Zhang, 2022]。然而，它们并非专为在线模型选择量身定制。经典 TS 是为决策集设计的，其中每个动作都有一个固定的奖励分布；相比之下，在模型选择中，学习者在基学习器之间进行选择，每个基学习器本身就是一个 bandit 算法，其行为和性能随着运行而演变。因此，识别实现环境下的最佳基学习器需要跨学习器的刻意元探索（meta-exploration），而不仅仅是单个学习者内部的动作层面探索。此外，标准 TS 通过后验采样进行探索，随后针对采样出的模型进行贪婪博弈（greedy play），并且没有明确利用额外的结构信号（例如，某些动作的信息价值），而这些信号对于快速区分竞争的学习者可能至关重要。
这种局限性在具有“信息锁”（information locks）的环境中变得尤为明显，在这些环境中，某些动作在先验中的每个环境下都是一致次优的，但对于哪些动作是最优的却具有高度的信息量 [Brukhim et al., 2025; Pacchiano et al., 2023]。在这种设定下，故意查询信息丰富动作的专用策略可以显著优于标准 TS。这些观察结果激发了一种用于在线模型选择的贝叶斯方法，该方法能够结合互补的算法行为并自动适应实现的环境实例。虽然先前的文献已经为频率学派设定下的模型选择开发了预言机风格的保证 [Dann et al., 2024b; Cutkosky et al., 2021]，但具有可比理论保证的贝叶斯对应方法仍未被探索。为此，我们提出了一种用于一般随机 bandit 问题的在线模型选择的新贝叶斯算法。我们将我们的贡献总结如下：
2 预备知识
贝叶斯序贯决策已经在一系列设定中得到了广泛研究，包括强化学习、上下文老虎机（contextual bandits）以及更一般的部分观测环境 [Fu et al., 2022; Ghavamzadeh et al., 2015]。
3 问题设定 (Problem Setup)
4 方法论与算法
贝叶斯在线模型选择算法利用后验样本在整个训练过程中估计基学习器的性能。在时刻 t ∈ [ T ] ，元学习器从后验分布中采样对应于每个动作的平均奖励，
贝叶斯在线模型选择算法的一个关键性质是，它在所有基学习器之间维护一个全局后验分布，利用所有基学习器收集到的动作-奖励对来更新该后验分布。因此，尽管基学习器之间不进行直接通信，它们通过后验分布共享信息，从而获得了统计效率。贝叶斯在线模型选择算法的伪代码如算法 1 所示。
5 分析
在接下来的章节中，我们将提供算法 1 的理论分析。我们首先陈述我们的假设，以及我们在分析中使用的一些关键引理。然后，我们提供预言机最优保证（oracle-best guarantee）的证明概要，并指引读者参阅附录 A.1 以获取完整证明。
5.1 假设
我们在分析中考虑以下假设：
5.2 关键引理
6 与 Thompson 采样的比较
附录中的图 5 显示，我们的算法（简称为 B-MS），当配备 K K 个随时间推移具有不同固定臂选择的基学习器时，其实现的贝叶斯遗憾与 Thompson 采样高度重合。这提供了强有力的证据，表明在这种 的特殊情况下，我们的贝叶斯遗憾界与 TS 的既定界限相吻合，因为最优基学习器总是选择最优臂，从而导致零遗憾。
7 实验
为了评估我们算法的性能，我们进行了实验研究，将我们提出的元学习器与基学习器的单独运行进行了比较。给定从先验分布中采样的环境，该框架允许基学习器是不同的老虎机（bandit）算法，或者是具有不同配置的相同算法。
7.2 结果
我们的元学习器在 UCB 和 LinTS 老虎机设定中都实现了与表现最佳的基学习器相当的性能。平均累积遗憾曲线与最优基学习器紧密跟踪，而最优动作选择率提供了令人信服的证据：B-MS 算法在 UCB 设定（c = 1）中实现了与最佳基学习器几乎相同的性能，并在 LinTS 设定（c = 0.16）中接近最佳表现者。
此外，我们的算法成功地避免了探索不足和过度探索。在图 2 中，B-MS 的平均遗憾曲线呈现出次线性增长，这与在近乎贪婪的策略（c = 0.01, c = 0.1）中观察到的近似线性遗憾累积形成了对比。同时，与那些过度探索的配置（c = 5, c = 10）相比，它保持了显著更低的遗憾。图 3 进一步证明，极端的参数选择会导致次优行为：c = 0 代表一种纯粹的利用策略，会迅速累积高额遗憾，而像 c = 25 这样的大值则会引发过度探索，同样导致性能不佳。元学习器成功适应了这些配置，其遗憾表现与最佳的 LinTS 变体相当。
我们还研究了在基学习器之间共享数据对元学习器性能的影响。结果如图 1 所示。我们可以看到，在所有图表中存在一个共同趋势：共享数据提高了元学习器的性能，并使算法更加高效。这与我们的理论预期一致，因为共享数据使得每个基学习器能够观察到更多样本，从而在其学习曲线上更快地进步。
我们在图 1 中进一步挑战了我们关于设定正确的先验（well-specified prior）的假设 5.1。我们考虑元学习器设定错误（mis-specified），但其中一个基学习器设定正确的情况（图 1b）。有趣的是，我们观察到，即使元学习器设定错误，池中存在一个设定正确的基学习器也有助于元学习器从设定错误中恢复。在没有任何设定正确的基学习器的情况下（即图 1d 的设定），设定错误的元学习器不会表现出具有竞争力的性能，这反映了关于设定正确的先验这一假设的重要性。
在最后一个实验中，我们将基学习器指定为 Thompson 采样算法和信息锁求解器（Information Lock Solver）算法，并应用我们提出的元算法 1。如图 4a 所示，元学习器成功地利用了这些基学习器的多样化建模范式，实现了比朴素 Thompson 采样基线更低的累积遗憾。重要的是，该框架并不局限于那些共享相同算法但仅通过超参数配置而有所不同的基学习器。
8 讨论与未来工作
从应用角度来看，该框架特别适用于在线超参数调优，在这种情况下，必须在有限的计算预算下自适应地评估多种算法或参数配置。更广泛地说，我们的方法论涵盖了随机老虎机之外的应用，例如具有非线性奖励结构的在线学习场景，或具有结构化先验的强化学习，其中不同的基学习器编码了不同的模型假设。
继扩散 Thompson 采样（Diffusion Thompson Sampling）以及 [Hsieh et al., 2023; Aouali, 2024] 的发展之后，一个有趣的方向是在贝叶斯在线模型选择中利用扩散先验（diffusion priors）。这一扩展将使得更具表达力的先验分布成为可能，从而能够涵盖更广泛变化的模型选择问题。
9 结论
在本文中，我们研究了贝叶斯随机老虎机（Bayesian stochastic bandits）中的在线模型选择问题，并引入了贝叶斯在线模型选择（Bayesian Online Model Selection）算法。我们的选择策略利用从后验分布中抽取的样本来为每个基学习器计算一个势函数。该势函数提供了对实现遗憾（realized regret）的一种随机估计，并且随着后验采样的进行而不断改进。
我们在多臂老虎机（multi-armed）和线性老虎机（linear bandit）算法的模型选择任务上评估了我们方法的实证性能。我们的算法能够调整 UCB 和 LinTS 的超参数，实现了与我们的理论分析相一致的实证性能。此外，实验表明，在基学习器之间共享数据提高了算法的整体性能，这在元学习器具有误设先验（mis-specified prior）时尤为有益。
原文链接：https://arxiv.org/pdf/2602.17958
热门跟贴