Learning from Local Walks on Dynamic Graphs with Bandit Feedback
2026-07-12 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors study a scenario where someone tries to find the best choice (arm) in a network that changes over time, but can only move locally from one point to a nearby one. This limitation means that even if they learn which choice is best, they might not be able to get to it easily. They identify a condition that helps ensure the network stays navigable for both learning and moving to good choices. Using this, they analyze strategies that explore first then commit, showing these have low overall mistakes (regret). They also design a method that pays attention to rewards and prove it is safe and can perform better in some cases.
stochastic multi-armed banditsdynamic graphslocal movement constraintbest-arm identificationexpected regretexplore-then-commit algorithmssliding-window mixingreward-aware strategygraph navigation
Authors
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen
Abstract
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.