Agents
Flickering Multi-Armed Bandits
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, wher
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. Erdos--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.
Related
- Deep Learning for Sequential Decision Making under Uncertainty: Foundations, Frameworks, and Frontiers
- Multi-agent Adaptive Mechanism Design
- Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning
- Learning the Value of Value Learning
Source: arXiv cs.AI | 2026-04-28