Search papers, labs, and topics across Lattice.
The paper introduces Flickering Multi-Armed Bandits (FMAB), a novel MAB framework where the set of available arms changes at each round, dependent on the agent's previous action, modeled using random graph processes. They analyze FMAB under i.i.d. Erdős--Rényi and Edge-Markovian graph models, proposing a two-phase algorithm with lazy random walk exploration and navigation-commitment exploitation. The authors establish high-probability and expected sublinear regret bounds for both graph settings and demonstrate near-optimal exploration cost via a matching information-theoretic lower bound.
Forget static arms: this new bandit framework tackles dynamically changing action sets, revealing the fundamental cost of exploration under local-move constraints.
We introduce Flickering Multi-Armed Bandits (FMAB), a new MAB framework where the set of available arms (or actions) can change at each round, and the available set at any time may depend on the agent's previously selected arm. We model this constrained, evolving availability using random graph processes, where arms are nodes and the agent's movement is restricted to its local neighborhood. We analyze this problem under two random graph models: an i.i.d. Erdős--Rényi (ER) process and an Edge-Markovian process. We propose and analyze a two-phase algorithm that employs a lazy random walk for exploration to efficiently identify the optimal arm, followed by a navigation and commitment phase for exploitation. We establish high-probability and expected sublinear regret bounds for both graph settings. We show that the exploration cost of our algorithm is near-optimal by establishing a matching information-theoretic lower bound for this problem class, highlighting the fundamental cost of exploration under local-move constraints. We complement our theoretical guarantees with numerical simulations, including a scenario of a robotic ground vehicle scouting a disaster-affected region.
