贝叶斯设计原则在频率主义序贯学习中的应用

《Journal of the ACM》：Bayesian Design Principles for Frequentist Sequential Learning

本文提出一种基于Algorithmic Information Ratio（AIR）的通用理论框架，优化序列学习问题中的频繁主义遗憾。通过结合贝叶斯后验与频繁主义分析，设计了APS（自适应后验采样）和AMS（自适应最小最大采样）算法，适用于对抗性、非平稳环境。实验验证了其在多臂老虎机中的优越性，并扩展到强化学习，建立了与DEC和IR的理论联系。

　　在本文中，我们提出了一个新颖的理论框架，用于优化序列学习问题中的频繁主义遗憾（frequentist regret）。这一理论不仅能够为基于贝叶斯原理的算法提供统一的优化路径，还能生成“算法信念”（algorithmic beliefs），并利用贝叶斯后验（Bayesian posterior）进行决策。通过这一方法，我们定义了一个称为“算法信息比”（Algorithmic Information Ratio, AIR）的内在复杂性度量，它能够有效刻画任何算法的频繁主义遗憾。尽管AIR的最小最大遗憾与Decision-Estimation Coefficient（DEC）框架提供的结果一致，但AIR还提供了与特定算法相关的视角，从而有助于算法的设计和分析。

在传统的方法中，频繁主义方法通常不需要环境的先验知识，但它们依赖于针对特定问题的个案分析。例如，基于回归的方法难以推广到对抗性问题，而逆概率加权（Inverse Probability Weighting, IPW）估计器通常只适用于简单的奖励/损失结构，如离散或线性结构。另一方面，贝叶斯方法依赖于已知的先验，这在复杂或对抗性环境中可能难以实现，且维护后验在大多数情况下计算成本较高。本文提出的AIR方法则结合了频繁主义和贝叶斯方法的优势，既不需要先验，又能够通过信念参数化和梯度优化来设计计算效率高的算法。

在这一理论框架下，我们提出了一个新颖的算法，该算法在伯努利多臂老虎机（Bernoulli Multi-Armed Bandit, MAB）问题中表现出色，适用于随机、对抗和非平稳环境。此外，我们还展示了该理论在诸如线性老虎机、凸老虎机和强化学习（Reinforcement Learning, RL）等其他问题中的应用。这些算法的结构简单，计算效率高，能够实现与现有方法相当甚至更优的性能。

在具体的应用中，我们以伯努利MAB为例，展示了如何通过优化AIR来生成“算法信念”，并利用这些信念进行决策。与传统的上界置信区间（Upper Confidence Bound, UCB）算法和对抗性MAB算法EXP3相比，我们的算法在对抗性环境中表现更优，在随机环境中表现接近Thompson Sampling（TS），并且在非平稳环境中优于专门为非平稳环境设计的基准算法。实验结果表明，我们的算法在各种环境下均表现出“最佳表现”（best-of-all-worlds）的性能，即在所有环境中都能达到最优或接近最优的遗憾边界。

此外，我们还提出了一个通用的算法设计方法，通过最大化AIR来生成“算法信念”。这一方法不仅适用于MAB，还适用于线性老虎机、凸老虎机和强化学习等其他问题。对于线性老虎机问题，我们推导出了一种改进的EXP2算法，该算法建立了IPW与贝叶斯后验之间的新联系。在强化学习中，我们通过将DEC框架与贝叶斯方法相结合，开发了能够达到现有结果的算法。

在理论分析方面，我们探讨了AIR与经典信息比（Information Ratio, IR）和DEC之间的关系。我们证明了在最坏情况下，AIR可以被IR和DEC上界所约束，从而保证了算法的理论性能。同时，我们还引入了MAIR（Model-index AIR），它适用于随机环境，并且能够与DEC框架中的现有结果相兼容。通过将AIR和MAIR应用于不同问题，我们展示了如何利用这些度量来设计和分析算法。

本文还提出了一个关于动态遗憾（dynamic regret）的理论保证，即在非平稳环境中，我们的算法能够自动适应最优决策的变化。我们通过引入“强制探索”（forced exploration）的混合策略，将算法的信念生成过程与动态环境中的性能提升相结合。实验结果表明，我们的算法在动态环境中能够显著优于传统的EXP3.S和“先知”重启算法。

在方法论上，我们强调了AIR与贝叶斯方法之间的联系，以及如何通过优化AIR来实现算法的信念生成。这不仅为算法设计提供了理论基础，还为实际应用中的计算效率和可实现性提供了指导。我们还讨论了如何在非平稳环境中利用动态后悔来改进算法的性能，并展示了如何通过参数化和梯度优化来实现这一点。

总的来说，本文提出了一种新的理论框架，通过优化AIR来设计和分析序列学习问题中的算法。这一框架不仅适用于多臂老虎机问题，还能够推广到线性老虎机、凸老虎机和强化学习等其他领域。我们展示了该框架在各种环境中的优势，包括计算效率、适应性以及与现有方法的兼容性。未来的研究方向包括开发更高效的算法、探索AIR在其他问题中的应用，以及进一步研究其在信息理论和优化理论中的潜在价值。