Flickering Multi-armed Bandits

Abstract

arXiv:2602.17315v2 Announce Type: replace-cross Abstract: We introduce Flickering Multi-Armed Bandits (FMAB) to model sequential decision-making in environments with changing action availability, where accessibility of the next action is restricted to a subset dependent on the agent's current choice. We formalize these constraints through stochastically evolving graphs where actions are limited to local neighborhoods. This mobility-constrained structure imposes a dual challenge: the statistical requirement of information acquisition and the physical overhead of navigation. We analyze FMAB under i.i.d. Erd\H\{o\}s--R'enyi and Edge-Markovian process, proposing a two-phase lazy random walk algorithm for robust exploration. We establish high-probability sublinear regret bounds and prove near-optimality via a matching information-theoretic lower bound. Our results characterize the intrinsic cost of learning under local-move constraints, complemented by a robotic disaster-response simulatio

Stats

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

Related papers

• Provably Efficient Reinforcement Learning For Adversarial Restless Multi-armed Bandits With Unknown Transitions And Bandit Feedback (2024)0.00
• A Frequency-domain Analysis Of The Multi-armed Bandit Problem: A New Perspective On The Exploration-exploitation Trade-off (2025)0.00
• Multi-action Restless Bandits With Weakly Coupled Constraints: Simultaneous Learning And Control (2024)0.00
• Learning In Restless Bandits Under Exogenous Global Markov Process (2021)6.34
• Pure Exploration Under Mediators' Feedback (2023)0.00
• Bandit Social Learning: Exploration Under Myopic Behavior (2023)0.00
• Online Learning For Cooperative Multi-player Multi-armed Bandits (2021)5.24
• A Closer Look At The Worst-case Behavior Of Multi-armed Bandit Algorithms (2021)0.00