Pith. sign in

REVIEW 4 major objections 5 minor 41 references

Learning from Local Walks on Dynamic Graphs with Bandit Feedback

T0 review · 4 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Local exploration on a dynamic graph achieves sublinear regret when the canonical walk mixes in every sliding window, despite optimal nodes being unreachable at times.

desk verdict A clean sublinear-regret result for fixed-degree dynamic graphs, wrapped in a framing that promises more generality than Definition 1 actually delivers. read the letter →

arxiv 2607.10571 v2 pith:UAFHOMYX submitted 2026-07-12 cs.LG cs.AIstat.ML

Sourav Chakraborty , Amit Kiran Rege , Claire Monteleoni , Lijun Chen This is my paper
classification cs.LGcs.AIstat.ML MSC 05C8160J1068T05
keywords dynamicgraphbanditslocalmovementexplore-then-commitcanonicalrandomwalksliding-windowmixingspectralgapsublinearregretreward-awareexploration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies stochastic bandits on a dynamic graph where the learner can only move to its current vertex or an immediate neighbor. It argues that the obstacle to learning is not local movement itself but the stability of the graph's canonical random walk. If every sliding time window contains enough well-connected rounds and all snapshot walks share a common stationary distribution, then a simple explore-then-commit policy identifies the best vertex and navigates to it often enough to obtain expected regret that grows sublinearly in the horizon. The analysis separates statistical identification from the structural cost of navigation, which remains independent of the horizon. If true, the result gives a process-agnostic sufficient condition for learnability in a broad class of dynamic networks, including fixed-degree rewiring and rotating regular overlays.

What carries the argument

The central object is the canonical walk kernel U_t(u,v) = (1 + deg_t(u))^{-1} for v in the closed neighborhood N_t(u) union {u}, with absolute spectral gap gap_abs(U_t). Definition 1 requires every snapshot kernel to be reversible with respect to the same distribution pi and every interval of W consecutive rounds to contain at least ceil(rho W) rounds with gap_abs at least gamma. The proofs thin the trajectory to every tau0-th step, use a one-sided Chernoff bound for adapted Bernoulli variables to guarantee per-arm visits, apply Hoeffding or a uniform confidence event to identify the best arm, and bound navigation by coupling to a pure canonical walk, yielding a hitting-time bound of 2 tau0

What would settle it

A direct calculation or simulation where a graph sequence satisfying Definition 1 still produces superlinear expected regret for CB-LEX with delta = T^{-2} would refute Corollary 2. Equivalently, constructing a (W, rho, gamma, pi)-mixing sequence on which the uniform mixing bound in Lemma 3 fails—either because the absolute spectral gap does not contract as claimed or because the common stationary distribution is not preserved—would collapse the argument. On the scope side, a process with drifting degrees that nevertheless yields sublinear regret would show the condition is not necessary.

Watch

Extended reading notes

Core claim

The central claim is that if the realized graph sequence is (W, rho, gamma, pi)-mixing for the canonical walk, then the graph's intrinsic walk—stay put or move uniformly to a neighbor—is a sufficient exploration and navigation primitive. Theorem 2 and its corollary show that a confidence-based explore-then-commit policy (CB-LEX) stops by a deterministic time and identifies the optimal arm with probability at least 1 minus delta, with expected regret O(tau0 Psi_CB(T^{-2}) + tau0/pi(a*)); in d-regular graphs this simplifies to O((W + log n/(rho gamma)) n (Delta_min^{-2} log(nT) + 1)). The paper also gives a fixed-budget baseline and a reward-aware variant that retains a fixed floor of canonica

Load-bearing premise

The proofs stand on the requirement that every snapshot's canonical walk shares the same stationary distribution pi; Proposition 3 shows this holds when degrees are fixed over time, so any process where degrees drift over time falls outside the theorem, and without this common pi the mixing and visitation lemmas no longer hold.

Editorial extensions

If this is right

  • For d-regular dynamic graphs—such as rotating overlays and periodic expanders—expected regret grows like O(n Delta_min^{-2} log(nT)) plus an O(n) navigation term, which is sublinear in T.
  • The confidence-based stopping rule removes the need to pre-specify an exploration budget while preserving the same regret order as the fixed-budget baseline.
  • Reward-biased movement does not forfeit worst-case safety: as long as the kernel retains a fixed floor of canonical movement, sublinear regret holds for any bias strength.
  • The gain theorem implies that biased exploration improves the worst-case rate only if it raises the visit probability of every near-bottleneck arm; missing one can leave the dominant term unchanged.
  • Because the structural condition is shift-invariant, the same mixing guarantees apply after the random stopping time, which is exactly when the navigation phase begins.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: processes with drifting degrees—for example edge-Markovian random graphs—violate Definition 1(i), so the theorems do not apply to them; whether the canonical walk is still learnable there is left open, since the mixing lemmas collapse without a common stationary distribution.
  • Inference: the navigation term tau0/pi(a*) suggests the hardest regime is when the optimal arm lies in a low stationary-mass region; a natural design question is whether faster-than-random navigation rules could reduce this term beyond the direct-move rule used here.
  • Inference: the paper's own caveats, located in Section III-D and Section V, are that the RALEX gain theorem is conditional on the block-end condition (16) and that weakening Definition 1 is explicitly left to future work; the unconditional contribution is the mixing-condition learnability theorem, not a necessary-and-sufficient characterization.
  • Inference: a numerical check of the block-end gain condition for the softmax proposal on a fixed-degree dynamic graph would reveal whether the 1/(1+zeta) improvement certified by Theorem 4 is actually realized in practice.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies stochastic multi-armed bandits when arms are vertices of a time-varying graph and the learner can only move to its current node or a neighbor. It proposes a structural condition, common-stationary sliding-window mixing for the canonical lazy random-walk kernel, and analyzes explore-then-commit algorithms LEX, CB-LEX, and RALEX. Under this condition, Theorem 2 and Corollary 2 give a high-probability identification time and sublinear expected regret for CB-LEX; Theorem 3 gives a worst-case safety guarantee for a reward-aware softmax-biased kernel with a canonical floor; and Theorem 4 gives a conditional performance-gain bound for RALEX. The proofs are self-contained and decompose regret into statistical learning, exploration stopping, and navigation hitting time. The central caveat is that Definition 1(i) heavily restricts the graph class, the Section IV simulation appears inconsistent with that restriction, and the RALEX gain theorem rests on an unverified block-end-probability assumption.

Significance. If the stated mixing condition is accepted as the intended regime, the paper is a careful theoretical contribution. The coupling arguments in Theorems 2 and 3 are internally consistent, the visitation and navigation lemmas are detailed, and the regret decomposition into a logarithmic learning term plus a horizon-independent navigation term is clean and, under the assumptions, correct. The shift-invariant, walk-centric formulation is a genuine conceptual improvement over whole-horizon block-density conditions, and the paper correctly identifies fixed-degree and regular-graph processes as the primary graph-side instantiations. However, the advertised scope is broader than the assumptions support: the common-stationary clause essentially confines the main theorems to proportional/fixed degree sequences or regular snapshots, and the reward-aware gain theorem is conditional on an assumption that is never verified for the softmax proposal. These points need to be addressed before the paper can be accepted in its current form.

major comments (4)
  1. [Definition 1(i), Eq. (1), Proposition 3, Lemmas 3/5/6] The common-stationary clause is the load-bearing hypothesis, but it confines the main theorems to much less than 'time-varying edges'. For the canonical kernel (1), stationarity forces 1+deg_t(a) = Z_t pi(a), so degree ratios are constant over t; apart from regular snapshots with uniform pi, the allowed regimes are essentially fixed-degree or proportionally varying degree sequences. Lemmas 3, 5, and 6 all require a single L^2(pi) space, so the sublinear regret claims do not extend to general edge-Markovian or degree-drifting processes. This is not a proof error, but the abstract and introduction should state the scope explicitly, and Section II.C should make clear which dynamic graph families satisfy Definition 1(i).
  2. [Section IV, 'Environment and Reward Model'] The simulation description says the topology evolves via degree-preserving edge switches maintaining a fixed degree sequence, then immediately sets 'the edge appearance probability to 0.1 and the disappearance probability to 0.01.' If these are independent per-edge probabilities, degrees fluctuate and Definition 1(i) with the canonical kernel generally fails; if they are switch-acceptance rates, the switch mechanism must be specified. As written, the experiment cannot be checked against Theorem 2 or Theorem 3. Please clarify the actual dynamics and, if it does not satisfy the common-stationary condition, either implement a genuinely degree-preserving switch process or explicitly present the simulation as a heuristic extension outside the theorem's assumptions.
  3. [Section III-D, Theorem 4, Eq. (16)/(18)] The RALEX performance-gain theorem is conditional on the block-end probability lower bounds kappa_gain(a) in Eq. (16), and the sufficient condition Eq. (18) is not established for the softmax proposal (9) used in the algorithm and experiments. Without a derivation or numerical verification that the softmax kernel satisfies these inequalities for the chosen lambda, epsilon0, and graph process, the claim that reward-aware exploration 'provably' accelerates identification is not supported. Theorem 4 only shifts the burden to an unverified assumption. Please either prove a concrete sufficient condition for the softmax proposal, or explicitly label the gain theorem as conditional and qualify the corresponding simulation claims.
  4. [Definition 1 and Theorem 1-3] The quantity pi* = min_a pi(a) appears throughout tau0 and the complexity measures, and the proofs require every arm to have positive stationary mass. However, Definition 1 does not explicitly require pi(a) > 0 for all a in A. If pi(a*) = 0 for some arm, the visit bounds, Chernoff steps, and confidence-based stopping arguments collapse. Add an explicit positivity/support condition to Definition 1 or state it as a standing assumption before the main theorems.
minor comments (5)
  1. [Corollary 1] The d-regular simplification is stated twice in the same paragraph; keep one display and remove the duplicate.
  2. [Appendix XIII, Lemma 10] The residual-kernel decomposition and the factor epsilon0^{tau1-1} require epsilon0 < 1. The trivial epsilon0 = 1 case is handled in Lemma 9 but should be stated at the start of Lemma 10 as well.
  3. [Figure 2/3] Captions are minimal. Label axes, define the shaded region (one standard deviation), and describe what the heatmap colors represent in Figure 3.
  4. [Section IV] Averaging over five seeds is small for the reported tight interquartile ranges. This is not blocking, but additional seeds or a description of variance across seeds would strengthen the empirical claim.
  5. [References] Reference [31] is a workshop paper; if an archival version exists, it should be cited instead for the journal version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: regret bounds are conditional on an explicit structural assumption and derived with self-contained proofs.

full rationale

The derivation chain is assumption-to-bound, not circular. Definition 1 supplies a common stationary distribution pi and recurring spectral-gap contraction; Lemmas 2-6 derive uniform mixing, thinned visitation, and navigation bounds directly from that premise; Theorems 1-3 then combine these lemmas with standard Hoeffding/Chernoff concentration. No parameter is fitted to data, no regret term is set equal to an input by construction, and the proofs are self-contained. The pi appearing in the final regret bounds is exactly the pi assumed in Definition 1, which is a normal conditional theorem, not a circular fit. Theorem 4 is explicitly conditional: if block-end visit probabilities are at least kappa_gain(a) (Eq. 16), then the complexity is expressed in terms of that assumed kappa; this is a valid transfer/sufficient-condition statement, not a derivation of the gain from RALEX's update rule. The paper itself says the gain requires an additional condition and provides Lemma 10 only as a sufficient condition for verifying it. Self-citations such as [10] and [31] are used for positioning and context, not as load-bearing justification for the main bounds. The skeptic's point that Definition 1(i) effectively restricts the regime to fixed-degree sequences is a scope/framing concern, not a circularity: the theorems honestly take Definition 1 as their premise, and Proposition 3 makes the fixed-degree subclass explicit. No specific circular reduction can be quoted, so the score is 0.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical entity. Its load-bearing burden is a regime assumption — a common stationary distribution and a recurring spectral-gap floor in every sliding window — rather than an invented mechanism. The least-supported piece is the RALEX gain theorem, which is conditional on a block-end probability condition that is not shown to hold for the proposed softmax kernel.

free parameters (4)
  • Mixing parameters (W, rho, gamma, pi) = not fitted; assumed known in theorem statements
    Define the common-stationary sliding-window mixing regime; all mixing times and regret bounds depend on them.
  • RALEX canonical floor epsilon0 = user-chosen, e.g. in (0,1]
    Controls the canonical-walk floor in Eq. (10); appears as epsilon0^{-tau0} in the RALEX bound.
  • RALEX softmax bias lambda = set to 10 in simulations
    Strength of reward bias in Eq. (9); absent from the worst-case RALEX bound but central to the conditional gain condition.
  • Gain-theorem burn-in t_gain and near-bottleneck factor zeta = user-chosen
    Parameters in Theorem 4 and Corollary 4; the proven gain scales with t_gain and the selected zeta.
assumptions (6)
  • domain assumption Each canonical kernel U_t is reversible with a common stationary distribution pi (Definition 1(i)).
    This is the central regime restriction; for the canonical walk it essentially requires a fixed or proportional degree sequence (Proposition 3).
  • domain assumption Every interval of W consecutive rounds contains at least ceil(rho W) snapshots with absolute spectral gap at least gamma (Definition 1(ii)).
    Provides the recurring contraction needed for uniform mixing from any start time.
  • domain assumption The graph process is oblivious, i.e. independent of the learner's actions and randomization (Section II-A).
    Needed for the perpetual-walk coupling and for treating graph randomness separately from reward randomness.
  • domain assumption Rewards are i.i.d., supported on [0,1], with a unique optimal arm (Section II-A).
    Standard bandit assumption; enables Hoeffding-based concentration and gap-dependent bounds.
  • ad hoc to paper Theorem 4 assumes block-end probabilities satisfy Pr(X_{s_j+tau1}=a | G_{j-1}) >= kappa_gain(a) for a in B (Eq. 16), or the sufficient condition in Eq. (18).
    The advertised performance-gain theorem is conditional on this unverified behavior of the biased walk; no proof is given that softmax RALEX satisfies it.
  • standard math Standard tools: spectral-gap contraction for reversible chains, Hoeffding's inequality, and the one-sided Chernoff bound for adapted Bernoulli variables.
    Used throughout the proofs in Appendices IX–XIII.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning from Local Walks on Dynamic Graphs with Bandit Feedback." pith.science (2026). https://pith.science/paper/UAFHOMYX

@misc{pith2026260710571,
  author       = {Pith},
  title        = {Pith review of: Learning from Local Walks on Dynamic Graphs with Bandit Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UAFHOMYX}},
  note         = {Machine review of arXiv:2607.10571}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2607.10571 by the authors.

Figure 1
Figure 1. Common-stationary sliding-window mixing ( [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Quantitative performance. a) Environment and Reward Model.: The environment is modeled as a dynamic graph Gt = (A, Et) defined over a discrete set of n = |A| = 205 nodes, simulated over a total horizon of T = 70, 000 rounds. The network topology evolves via degree-preserving edge switches, maintaining a fixed degree sequence across all snapshots and thus a common stationary distribution π as required by Definition 1… view at source ↗
Figure 3
Figure 3. Exploration footprints. CB-LEX sweeps uniformly, while RA-LEX acts as a “searchlight” on the optimal region. is highly concentrated, resembling a “searchlight” focused on the true high-reward zones. This visually confirms that its biased random walk successfully prioritizes promising regions, explaining its superior sample efficiency. Efficiency of Reward-Aware Exploration: As shown in Figure 2a, both algorithms ach… view at source ↗

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

41 extracted references · 8 linked inside Pith

  1. [1]

    Nonstochastic Multi-Armed Bandits with Graph- Structured Feedback

    Noga Alon et al. “Nonstochastic Multi-Armed Bandits with Graph- Structured Feedback”. In:SIAM Journal on Computing46.6 (2017), pp. 1785–1820

    2017

  2. [2]

    Finite-time analysis of the multiarmed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. “Finite-time analysis of the multiarmed bandit problem”. In:Machine learning 47 (2002), pp. 235–256

    2002

  3. [3]

    How to Explore a Fast-Changing World: Cover Time of a Simple Random Walk on Evolving Graphs

    Chen Avin, Michal Kouck ´y, and Zvi Lotker. “How to Explore a Fast-Changing World: Cover Time of a Simple Random Walk on Evolving Graphs”. In:ICALP. 2008

    2008

  4. [4]

    Recent Trends in Robotic Patrolling

    Nicola Basilico. “Recent Trends in Robotic Patrolling”. In:Current Robotics Reports3 (June 2022).DOI: 10.1007/s43154- 022- 00078-5

    doi:10.1007/s43154- 2022

  5. [5]

    A Contextual-Bandit Algorithm for Mobile Context-Aware Recom- mender System

    Djallel Bouneffouf, A. Bouzeghoub, and Alda Lopes Gan c ¸arski. “A Contextual-Bandit Algorithm for Mobile Context-Aware Recom- mender System”. In:ICONIP. 2012

    2012

  6. [6]

    Port- folio Allocation for Bayesian Optimization

    Eric Brochu, Matthew W. Hoffman, and Nando de Freitas. “Port- folio Allocation for Bayesian Optimization”. In:arXiv e-prints, arXiv:1009.5419 (Sept. 2010), arXiv:1009.5419. arXiv: 1009.5419 [cs.LG]

    arXiv 2010

  7. [7]

    Leran Cai, Thomas Sauerwald, and Luca Zanetti.Random Walks on Randomly Evolving Graphs. 2020. arXiv: 2006 . 10589 [math.PR]

    2020

  8. [8]

    Revealing Graph Bandits for Maximizing Local Influence

    Alexandra Carpentier and Michal Valko. “Revealing Graph Bandits for Maximizing Local Influence”. In:AISTATS. 2016

    2016

Show all 41 references
  1. [9]

    Incentivized Explo- ration of Non-Stationary Stochastic Bandits

    Sourav Chakraborty and Lijun Chen. “Incentivized Explo- ration of Non-Stationary Stochastic Bandits”. In:arXiv preprint arXiv:2403.10819(2024)

    2024 arXiv

  2. [10]

    Flickering Multi-Armed Bandits

    Sourav Chakraborty et al. “Flickering Multi-Armed Bandits”. In: arXiv preprint arXiv:2602.17315(2026)

    2026 arXiv

  3. [11]

    Incentivized Lipschitz Bandits

    Sourav Chakraborty et al. “Incentivized Lipschitz Bandits”. In:arXiv preprint arXiv:2508.19466(2025)

    2025 arXiv

  4. [12]

    Multi-Agent Lipschitz Bandits

    Sourav Chakraborty et al. “Multi-Agent Lipschitz Bandits”. In:arXiv preprint arXiv:2602.16965(2026)

    2026 arXiv

  5. [13]

    Bandits with Switching Costs: T 2/3 Regret

    Ofer Dekel et al. “Bandits with Switching Costs: T 2/3 Regret”. In: STOC. 2014

    2014

  6. [14]

    A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks

    Tom´as Feder et al. “A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks”. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE. 2006, pp. 69–76

    2006

  7. [15]

    Configuring Random Graph Models with Fixed Degree Sequences

    Bailey K. Fosdick et al. “Configuring Random Graph Models with Fixed Degree Sequences”. In:SIAM Review60.2 (2018), pp. 315–355

    2018

  8. [16]

    Incentivizing Exploration

    Peter Frazier et al. “Incentivizing Exploration”. In:Proceedings of the Fifteenth ACM Conference on Economics and Computation. EC ’14. Palo Alto, California, USA: Association for Computing Machinery, 2014, pp. 5–22.ISBN: 9781450325653.DOI: 10.1145/2600057. 2602897.URL: https :...

    2014 doi

  9. [17]

    Learning Multiuser Channel Allocations in Cognitive Radio Networks: A Combinatorial Multi-Armed Bandit Formulation

    Yi Gai, Bhaskar Krishnamachari, and Ramesh Jain. “Learning Multiuser Channel Allocations in Cognitive Radio Networks: A Combinatorial Multi-Armed Bandit Formulation”. In: May 2010, pp. 1–9.DOI:10.1109/DYSPAN.2010.5457857

    2010

  10. [18]

    Bandit Processes and Dynamic Allocation Indices

    J. C. Gittins. “Bandit Processes and Dynamic Allocation Indices”. In: Journal of the Royal Statistical Society. Series B (Methodological) 41.2 (1979), pp. 148–177.ISSN: 00359246.URL: http://www. jstor.org/stable/2985029

    1979

  11. [19]

    Random Walks in Peer-to-Peer Networks

    Christos Gkantsidis, Milena Mihail, and Amin Saberi. “Random Walks in Peer-to-Peer Networks”. In: vol. 1. Apr. 2004, p. 130.ISBN: 0-7803-8355-9.DOI:10.1109/INFCOM.2004.1354487

    2004

  12. [20]

    Bandits and Experts in Metric Spaces

    Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. “Bandits and Experts in Metric Spaces”. In:J. ACM66.4 (May 2019).ISSN: 0004- 5411.DOI: 10.1145/3299873.URL: https://doi.org/10. 1145/3299873

    2019 doi

  13. [21]

    Multi-armed bandits in metric spaces

    Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. “Multi-armed bandits in metric spaces”. In:Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC ’08. Victoria, British Columbia, Canada: Association for Computing Machinery, 2008, pp. 681–690.ISBN: ...

    2008 doi

  14. [22]

    Bandits with Movement Costs and Adaptive Pricing

    Tomer Koren, Roi Livni, and Yishay Mansour. “Bandits with Movement Costs and Adaptive Pricing”. In:COLT. 2017

    2017

  15. [23]

    Multi-Armed Bandits with Metric Movement Costs

    Tomer Koren, Roi Livni, and Yishay Mansour. “Multi-Armed Bandits with Metric Movement Costs”. In:NeurIPS. 2017

    2017

  16. [24]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesv ´ari.Bandit Algorithms. Cambridge University Press, 2020

    2020

  17. [25]

    A contextual-bandit approach to personalized news article recommendation

    Lihong Li et al. “A contextual-bandit approach to personalized news article recommendation”. In:Proceedings of the 19th international conference on World wide web - WWW ’10(2010).DOI: 10.1145/ 1772690.1772758.URL: http://dx.doi.org/10.1145/ 1772690.1772758

    2010

  18. [26]

    Random Walks on Sensor Networks

    Lu´ısa Lima and Jo ˜ao Barros. “Random Walks on Sensor Networks”. In: May 2007, pp. 1–5.ISBN: 978-1-4244-0960-0.DOI: 10.1109/ WIOPT.2007.4480064

    2007

  19. [27]

    Incentivized Exploration for Multi-Armed Bandits under Reward Drift

    Zhiyuan Liu et al. “Incentivized Exploration for Multi-Armed Bandits under Reward Drift”. In:Proceedings of the AAAI Conference on Artificial Intelligence34.04 (Apr. 2020), pp. 4981–4988.DOI: 10. 1609/aaai.v34i04.5937.URL: https://ojs.aaai.org/ index.php/AAAI/article/view/5937

    2020

  20. [28]

    From Bandits to Experts: On the Value of Side-Observations

    Shie Mannor and Ohad Shamir. “From Bandits to Experts: On the Value of Side-Observations”. In:NeurIPS. 2011

    2011

  21. [29]

    Degree Fluctuations and the Convergence Time of Consensus Algorithms

    Alex Olshevsky and John N. Tsitsiklis. “Degree Fluctuations and the Convergence Time of Consensus Algorithms”. In:IEEE Transactions on Automatic Control58.10 (2013), pp. 2626–2631

    2013

  22. [30]

    Phevos Paschalidis, Runyu Zhang, and Na Li.Cooperative Multi- Agent Graph Bandits: UCB Algorithm and Regret Analysis. 2024. arXiv:2401.10383 [cs.LG]

    2024 arXiv

  23. [31]

    Bandit Learning on Dynamic Graphs

    Amit Kiran Rege et al. “Bandit Learning on Dynamic Graphs”. In: NeurIPS 2025 Workshop: Second Workshop on Aligning Reinforce- ment Learning Experimentalists and Theorists

    2025

  24. [32]

    Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities

    Thomas Sauerwald and Luca Zanetti. “Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities”. In: ICALP. 2019

    2019

  25. [33]

    Mark Sellke and Aleksandrs Slivkins.The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity. 2021. arXiv:2002.00558 [cs.GT]

    2021 arXiv

  26. [34]

    Reversible Random Walks on Dynamic Graphs

    Nobutaka Shimizu and Takeharu Shiraga. “Reversible Random Walks on Dynamic Graphs”. In:Random Structures & Algorithms(2022)

    2022

  27. [35]

    Introduction to Multi-Armed Bandits

    Aleksandrs Slivkins. “Introduction to Multi-Armed Bandits”. In:Foun- dations and Trends in Machine Learning12.1–2 (2019), pp. 1–286

    2019

  28. [36]

    Stauffer and Valmir C

    Alexandre O. Stauffer and Valmir C. Barbosa.A Study of the Edge- Switching Markov-Chain Method for the Generation of Random Graphs. 2005. arXiv:cs/0512105 [cs.DM]

    2005 arXiv

  29. [37]

    Bandits on Graphs and Structures

    Michal Valko. “Bandits on Graphs and Structures”. PhD thesis. Universit´e Lille 1, 2016

    2016

  30. [38]

    Multi-armed Bandits with Com- pensation

    Siwei Wang and Longbo Huang. “Multi-armed Bandits with Com- pensation”. In:Advances in Neural Information Processing Systems. Ed. by S. Bengio et al. V ol. 31. Curran Associates, Inc., 2018.URL: https : / / proceedings . neurips . cc / paper / 2018 / file / 8bdb5058376143fa358...

    2018

  31. [39]

    Preprint

    Yuxiao Wen, Yanjun Han, and Zhengyuan Zhou.Stochastic Contextual Bandits with Graph Feedback: From Independence Number to MAS Number. Preprint. 2024

    2024

  32. [40]

    Multi-Armed Bandit Learning on a Graph

    Tianpeng Zhang, Kasper Johansson, and Na Li. “Multi-Armed Bandit Learning on a Graph”. In:CISS. 2023. VI. RELATED WORK AND POSITIONING This paper lies at the intersection of stochastic bandits, graph-constrained decision problems, and random walks on dynamic graphs. The closes...

    2023

  33. [41]

    Fix an arm a∈A

    We therefore assume in the rest of the proof thatε 0 <1. Fix an arm a∈A . Let Fj be the full history of the process up to time jτ0, including states, rewards, and all internal randomization used to define the kernels. For convenience write ν:= (j−1)τ 0 for the start of blockj....

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.