arXiv:2510.08908cs.LGcs.AI2025-10

用频域分析重新解读探索与利用的权衡,让经典算法更直观。

A Frequency-Domain Analysis of the Multi-Armed Bandit Problem: A New Perspective on the Exploration-Exploitation Trade-off

  • 将老虎机问题视为信号处理,把每条臂的收益估计看作频谱分量。
  • 证明UCB的置信区间在频域等价于随访问次数平方根反比变化的增益。
  • 为自适应调参的新一代算法设计提供理论基础,适合研究强化学习机制者。

随机多臂老虎机(MAB)是序列决策中的基础模型,核心挑战在于探索与利用的权衡。尽管上置信界(UCB)和汤普森采样等算法及其后悔率理论已成熟,但现有分析多基于时域和累积后悔视角,难以刻画学习过程的动态特性。本文提出一种全新的频域分析框架,将老虎机过程重构成信号处理问题:每条臂的收益估计被视为一个谱成分,其不确定性对应频率,算法被解释为自适应滤波器。我们构建了形式化的频域老虎机模型,并证明主定理:UCB中的置信边界项在频域中等价于对不确定谱成分施加随访问次数平方根反比变化的时间可变增益。基于此,进一步推导出关于探索率衰减的有限时间动态界。该理论不仅为经典算法提供了新颖直观的物理解释,也为设计具备自适应参数调节能力的下一代算法奠定了严谨的理论基础。

原文摘要 · Abstract (English)

The stochastic multi-armed bandit (MAB) problem is one of the most fundamental models in sequential decision-making, with the core challenge being the trade-off between exploration and exploitation. Although algorithms such as Upper Confidence Bound (UCB) and Thompson Sampling, along with their regret theories, are well-established, existing analyses primarily operate from a time-domain and cumulative regret perspective, struggling to characterize the dynamic nature of the learning process. This paper proposes a novel frequency-domain analysis framework, reformulating the bandit process as a signal processing problem. Within this framework, the reward estimate of each arm is viewed as a spectral component, with its uncertainty corresponding to the component's frequency, and the bandit algorithm is interpreted as an adaptive filter. We construct a formal Frequency-Domain Bandit Model and prove the main theorem: the confidence bound term in the UCB algorithm is equivalent in the frequency domain to a time-varying gain applied to uncertain spectral components, a gain inversely proportional to the square root of the visit count. Based on this, we further derive finite-time dynamic bounds concerning the exploration rate decay. This theory not only provides a novel and intuitive physical interpretation for classical algorithms but also lays a rigorous theoretical foundation for designing next-generation algorithms with adaptive parameter adjustment.

强化学习贝叶斯优化理论分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。