Learning from Local Walks on Dynamic Graphs with Bandit Feedback
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen
cs.LG, cs.AI, stat.ML
Submitted: 2026-07-12
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges.
Terminology
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.
Sources
- Portfolio Allocation for Bayesian Optimization
- Incentivized Exploration of Non-Stationary Stochastic Bandits
- Flickering Multi-Armed Bandits
- Incentivized Lipschitz Bandits
- Multi-Agent Lipschitz Bandits
- Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis
- The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
- A study of the edge-switching Markov-chain method for the generation of random graphs
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks