📊 statistics

Learning from Local Walks on Dynamic Graphs with Bandit Feedback

This paper addresses stochastic multi-armed bandits on dynamic graphs with local movement constraints by introducing a sliding-window mixing condition to ensure topological stability and proposing explore-then-commit algorithms that achieve sublinear expected regret.

Original authors: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a treasure hunter in a magical, shifting city. The city is made of islands (the "arms" or options), and bridges connect them. Every day, the bridges rearrange themselves: some open, some close, and new ones appear. Your goal is simple: find the island with the golden chest (the best reward) and spend the rest of your time there collecting gold.

But here's the catch: you can't just teleport. You can only walk to an island you are currently standing on, or cross a bridge to a neighbor that is open right now. This is the world of Dynamic Graph Bandits.

The Big Problem: Finding vs. Reaching

In a normal treasure hunt, once you know where the gold is, you just run straight there. But in this shifting city, knowing the location isn't enough. You might spot the golden island from afar, but if the bridges to it are closed, you're stuck wandering in a dead-end neighborhood.

The paper argues that you can't just look at the "big picture" of the city over the whole day to see if it's connected. Even if the city is fully connected when you add up every bridge that ever existed, you could still be trapped in a corner for hours because the specific bridges you need are closed today. The authors show that relying on these "whole-day" summaries is a trap; it doesn't guarantee you can actually get to the gold.

The Solution: A "Sliding Window" Rule

To fix this, the authors propose a new rule for the city's layout. Instead of checking the whole day, they check a sliding window of time (say, the last 5 minutes).

They say the city is "safe" to learn in if, within any 5-minute window, there are enough "well-connected" moments where the bridges form a nice, open network. If this happens often enough, it guarantees that your random wandering will eventually mix you around the whole city, and you won't get stuck in a corner forever. They call this the Common-Stationary Sliding-Window Mixing condition.

Think of it like a dance floor that changes its shape every few seconds. As long as the floor opens up enough times in every short burst, you can't get trapped in a corner, no matter when you start dancing.

The Strategy: Explore, Then Commit

The paper tests three ways to play this game:

The "Blind" Walker (LEX): You wander randomly for a set amount of time, just to see what's out there. Once the time is up, you pick the best island you saw and try to get there. The math proves that if the city follows the "sliding window" rule, you will find the gold and get there, and your total lost gold (regret) will be very low compared to the total time.
The "Confident" Walker (CB-LEX): This is smarter. Instead of wandering for a fixed time, you keep wandering until you are sure you've found the best island. You stop as soon as the evidence is strong enough. The paper proves this works just as well as the blind walker but saves time by stopping early when the gold is easy to find.
The "Searchlight" Walker (RALEX): This one tries to be clever. It looks at the gold it's found so far and tries to walk toward the promising islands, rather than wandering randomly.
- The Safety Net: The authors prove that even if this "Searchlight" gets too excited and tries to rush, it has a safety floor. It always keeps a tiny bit of random wandering in its steps. This guarantees that even in the worst-case scenario, it won't get stuck and will still find the gold eventually.
- The Payoff: In simulations, this "Searchlight" strategy was a huge hit. On a difficult map where the gold was hard to spot, the Searchlight found it in about 1,850 rounds, while the blind walker needed 6,000 rounds. That's nearly 70% faster.

What the Paper Rules Out

The authors are very clear about what doesn't work. They explicitly rule out the idea that you can just check if the city is connected over the entire day. They show through examples that even if the city is connected in the long run, you can still be stuck in a dead end for a long time if the bridges close up at the wrong moments. You need that "sliding window" guarantee to be safe.

How Sure Are They?

The authors didn't just guess; they built a mathematical fortress around their ideas.

Proven: They have rigorous mathematical proofs showing that if the city follows their "sliding window" rule, the "Blind" and "Confident" walkers will always succeed with low regret. They also proved the "Searchlight" walker is safe in the worst case.
Simulated: They ran computer simulations with 205 islands over 70,000 rounds to test the "Searchlight" strategy. These simulations showed that the Searchlight really does find the gold much faster than the others in tricky situations.
Not a Magic Bullet: They admit that while the Searchlight is faster in their tests, the math only guarantees it's safe. The extra speed depends on the gold being in a specific spot that the Searchlight can actually "see" and move toward.

In short, the paper gives us a new rulebook for navigating shifting mazes. It proves that if the maze opens up often enough in short bursts, we can find the treasure. And if we add a little bit of "smart" direction to our wandering, we can find it even faster, without ever getting hopelessly lost.

Technical Summary: Learning from Local Walks on Dynamic Graphs with Bandit Feedback

Problem Formulation
This paper addresses the stochastic multi-armed bandit (MAB) problem in a setting where the learner is constrained to local movement on a dynamic graph. Unlike classical MAB models where any arm is available at every round, or feedback-graph models where side observations are available, here the learner can only select its current node or an immediate neighbor based on the graph's connectivity at that specific time step.

Setting: The arms correspond to vertices $A = \{1, \dots, n\}$ of a time-varying undirected graph $G_t = (A, E_t)$ .
Constraints: At round $t$ , the learner observes only the local neighborhood $L_t(a_{t-1})$ and must choose $a_t \in L_t(a_{t-1})$ . The graph process is oblivious (independent of the learner's actions).
Core Challenge: The setting decouples best-arm identification from exploitation. In classical bandits, identifying the optimal arm $a^\star$ allows immediate exploitation. In this dynamic setting, even after $a^\star$ is identified, the learner may be structurally isolated from it due to the evolving topology. Learnability requires that the environment consistently provides navigable pathways, not just that the union of all graphs over the horizon is connected.

Methodology and Structural Conditions
The authors adopt an explore-then-commit framework, separating the problem into exploration (gathering samples) and navigation (reaching the identified target). To ensure learnability, they introduce a process-agnostic structural condition based on the canonical walk (a simple random walk where the learner stays or moves uniformly to a neighbor).

Common-Stationary Sliding-Window Mixing (Definition 1): The paper rejects whole-horizon connectivity conditions (e.g., the union of all graphs being connected) as insufficient, as they fail to guarantee reachability at arbitrary stopping times. Instead, they impose a condition on the induced random walk:
1. Common Stationary Distribution: Every graph snapshot $G_t$ induces a reversible kernel $U_t$ with a common stationary distribution $\pi$ (e.g., achieved by fixed-degree sequences).
2. Sliding-Window Mixing: In every time window of length $W$ , at least a fraction $\rho$ of rounds must have a spectral gap $\ge \gamma$ .
  This condition ensures the walk mixes toward $\pi$ uniformly over time, preventing the learner from being trapped in local subgraphs indefinitely, regardless of when exploration ends.

Algorithms
The paper analyzes a family of algorithms operating under this regime:

LEX (Fixed-Budget Lazy Exploration): Uses the canonical walk for exploration for a fixed budget $T_{exp}$ determined by mixing parameters and reward gaps. It commits to the empirical leader and navigates using the canonical walk if the target is not immediately reachable.
CB-LEX (Confidence-Based Stopping): Replaces the fixed budget with a data-dependent stopping rule. It terminates when the Lower Confidence Bound (LCB) of the empirical leader dominates the Upper Confidence Bounds (UCBs) of all other arms (not just the runner-up), ensuring robustness against uneven sampling.
RALEX (Reward-Aware Exploration): Introduces a reward-biased kernel that mixes the canonical walk with an optimistic proposal (softmax over estimated rewards). Crucially, it maintains a "canonical floor" ( $\epsilon_0$ ) to ensure the structural mixing properties of the canonical walk are preserved, guaranteeing worst-case safety.

Key Results and Regret Bounds
Under the $(W, \rho, \gamma, \pi)$ -mixing condition, the authors establish sublinear expected regret ( $o(T)$ ) for all proposed algorithms. The regret bounds decompose into two distinct components:

Learning Regret: Scales with the statistical difficulty (inverse gaps $\Delta^{-2}$ ) and the mixing overhead ( $\tau_0$ ), representing the cost of identifying the best arm.
Navigation Regret: A structural cost independent of the horizon $T$ , representing the expected time to reach the identified optimal arm from the stopping point.

LEX/CB-LEX: Achieve regret of order $O(\tau_0 \cdot \Psi \cdot \log T)$ , where $\Psi$ captures the complexity of the gaps and stationary masses.
RALEX: Proves that reward-aware bias is compatible with sublinear regret. While the worst-case bound is conservative (due to the canonical floor), the paper provides a separate theorem (Theorem 4) showing that if the reward-aware bias successfully increases the visitation probability of "near-bottleneck" arms, a provable performance gain (multiplicative improvement in the learning term) is achieved.

Significance and Claims
The paper positions itself as a structural characterization of learnability for locally constrained bandits on dynamic graphs, rather than a proposal for near-optimal regret minimization on specific graph families (like complete graphs).

Shift-Invariance: The primary contribution is the shift-invariant, sliding-window mixing condition. This ensures that the structural assumptions required for navigation hold after the random stopping time of exploration, a requirement that whole-horizon conditions fail to meet.
Decoupling: The work explicitly separates the statistical cost of learning from the structural cost of navigation, providing a clean theoretical framework for dynamic environments.
Process-Agnosticism: Unlike prior work relying on specific graph processes (e.g., i.i.d. Erdős–Rényi or edge-Markovian), this paper provides a theorem that holds for any graph sequence satisfying the walk-centric mixing condition, covering natural processes like rotating regular overlays and degree-preserving rewirings.
Safety vs. Gain: The RALEX analysis distinguishes between a "safety theorem" (guaranteeing sublinear regret with any bias parameter) and a "gain theorem" (certifying performance improvement under specific conditions on the reward-aware proposal).

The authors conclude that their work establishes a "positive regime" where the intrinsic canonical walk is sufficient for learning, offering a foundation for future extensions to more complex kernels like Metropolis-type walks.