A Frequency-domain Analysis Of The Multi-armed Bandit Problem: A New Perspective On The Exploration-exploitation Trade-off

Abstract

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 frequenc

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhang2025a

Related papers

• A Closer Look At The Worst-case Behavior Of Multi-armed Bandit Algorithms (2021)0.00
• Bayesian Bandits: Balancing The Exploration-exploitation Tradeoff Via Double Sampling (2017)0.00
• Mean Field Equilibrium In Multi-armed Bandit Game With Continuous Reward (2021)0.00
• Non-stationary Latent Auto-regressive Bandits (2024)0.00
• Stochastic Multi-armed Bandits With Limited Control Variates (2026)0.00
• Flickering Multi-armed Bandits (2026)0.00
• Adaptive Sequential Experiments With Unknown Information Arrival Processes (2019)0.00
• Online Learning For Cooperative Multi-player Multi-armed Bandits (2021)5.24