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ő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 simulation.
Figures & tables
Figure 1: A 4-arm FMAB problem at t=s,s+1,s+2 , with pull sequence as=3,as+1=4,as+2=2 (from as−1=1 ). (A) Problem view: Blue/White arms are accessible/inaccessible. Pulled arm has a dark blue border. (B) Graph view: Learner starts at the dark blue node ( at−1 ) and can move to blue neighbors ( Lt(at−1) ).
Figure 2: Evolution of FMAB availability graphs . (A) i.i.d. ER evolution: edge re-sampling with some probability pij for each edge (i,j) across snapshots t,t+1,t+2 . (B) Edge-Markovian process: evolution featuring appearing edges (green solid, with probability α ) and disappearing edges (red dotted, with probability β ) relative to the preceding round.
Figure 3: (a) Average cumulative regret R(t)/t over time for i.i.d ER case. The main plot and the inset (showing the initial t≤200 rounds) demonstrate the algorithm’s rapid convergence. (b) Same plot for the Edge-Markovian Case. (c) Box plot for the navigation cost for ER case with respect to the sparsity.
Figure 4: (a) Average cumulative regret R(t)/t for the disaster response scenario. (b) Spatial visitation density (log-scale) illustrating the behavioral transition from the exploration and exploitation rounds.
Institute of Communications Engineering, National Yang Ming Chaio Tung University, Hsinchu, Taiwan · Department of Computer Science, National Yang Ming Chaio Tung University, Hsinchu, Taiwan