研究受限移动下的智能体决策，提出新模型并证明高效学习的理论极限。
Flickering Multi-Armed Bandits
- 用随机图建模动作可达性，动作只能在局部邻域中选择。
- 设计双阶段懒惰随机游走算法，实现次线性后悔率。
- 适用于机器人救援等需移动导航的实时决策场景。
我们引入闪烁多臂老虎机（FMAB）来建模动作可用性动态变化环境中的序列决策问题，其中下一个可选动作受限于当前选择所决定的子集。通过随机动态演化的图结构刻画这些约束，动作仅限于局部邻域内。这种移动约束带来双重挑战：信息获取的统计需求与导航的物理开销。我们在独立同分布的埃拉托斯特尼-雷尼图与边马尔可夫过程中分析了FMAB，提出一种双阶段懒惰随机游走算法以实现稳健探索。我们建立了高概率次线性后悔界，并通过匹配的信息论下界证明了近似最优性。结果揭示了在局部移动约束下学习的内在代价，实验还包含一个机器人灾难响应模拟。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。