在动态图上用局部移动策略实现高效探索，解决边变化时的寻优难题。
Learning from Local Walks on Dynamic Graphs with Bandit Feedback
- 基于滑动窗口混合的结构条件，保证图上随机游走稳定。
- 提出局部探索-然后确定算法，实现次线性期望遗憾。
- 适合研究动态网络中的在线学习与资源调度问题。
我们研究动态图上的随机多臂赌博机问题，其中臂对应具有随时间变化边的网络顶点。学习者受限于局部移动，每轮只能选择当前节点或其直接邻居。这一限制使最优臂识别与利用解耦：即使找到最优臂，也可能因拓扑演变而无法到达。我们识别出一种过程无关的结构性条件——基于滑动窗口混合，确保图的内在随机游走对探索和导航均保持稳定。在此条件下，我们分析了一类局部探索-然后确定算法，并建立了次线性期望遗憾。我们的框架包含一种奖励感知策略，对其证明了最坏情况安全性定理和独立的性能提升定理。
原文摘要 · Abstract (English)
We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges. In this setting, the learner is restricted to local movement, selecting only its current node or an immediate neighbor at each round. This constraint decouples best-arm identification from exploitation: even after the optimal arm is identified, the learner may remain unable to reach it through the evolving topology. We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation. Under this regime, we analyze a family of local explore-then-commit algorithms and establish sublinear expected regret. Our framework includes a reward-aware strategy, for which we prove a worst-case safety theorem and a separate performance gain theorem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。