# Learning from Local Walks on Dynamic Graphs with Bandit Feedback

arXiv: https://arxiv.org/abs/2607.10571 · HTML: https://mlsanity.com/paper/2607.10571/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 12 Jul 2026.

## Builds on (most cited first, 17 of 17)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020)
- [Configuring Random Graph Models with Fixed Degree Sequences](https://mlsanity.com/paper/1608.00607/) (2016)
- [Bandits with Movement Costs and Adaptive Pricing](https://mlsanity.com/paper/1702.07444/) (2017)
- [Multi-Armed Bandits with Metric Movement Costs](https://mlsanity.com/paper/1710.08997/) (2017)
- [Incentivized Exploration for Multi-Armed Bandits under Reward Drift](https://mlsanity.com/paper/1911.05142/) (2019)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Multi-armed Bandit Learning on a Graph](https://mlsanity.com/paper/2209.09419/) (2022)
- [Incentivized Exploration of Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2403.10819/) (2024)
- [Incentivized Lipschitz Bandits](https://mlsanity.com/paper/2508.19466/) (2025)
- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis](https://mlsanity.com/paper/2401.10383/) (2024)
- [Multi-Agent Lipschitz Bandits](https://mlsanity.com/paper/2602.16965/) (2026)
- [Flickering Multi-Armed Bandits](https://mlsanity.com/paper/2602.17315/) (2026)

## Abstract (arXiv)

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.