Overview

Graph bandits study how to choose actions when a graph links arms, items, observations, or the evolution of rewards. Methods use graph-based side observations, spectral smoothness and effective dimension, triggering dependencies, or local walks, with algorithms such as UCB, Thompson sampling, and linear programming. These approaches support settings including recommendation, influence maximization, path selection, and decisions over changing networks, where structure can reduce the number of evaluations needed. A central challenge is balancing information gained from graph structure against errors from unknown, noisy, or changing graphs; for local-movement problems, learners must also pay the cost of reaching promising actions.

Latest papers

CardsList

18 papers2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

  1. Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits

    Nov 3, 2026Jongyeong Lee, Hyundam YooBest-of-Both-Worlds BanditsGraph Bandits

  2. Near-Optimal First-Order Regret for Bandits with Feedback Graphs

    Oct 29, 2026Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1Graph BanditsRegret Minimization

  3. Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting

    Sep 13, 2026Shunsuke Aoki, Atsuyoshi NakamuraGraph BanditsCombinatorial Semi-Bandits

  4. Beyond Binary: Continuous State Optimization with Graph-Structured Objectives

    Aug 10, 2026Corinna Cortes, Yishay Mansour, Mehryar MohriFactor Graph OptimizationMulti-Armed Bandits

  5. Learning from Local Walks on Dynamic Graphs with Bandit Feedback

    Jul 12, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Armed BanditsGraph Bandits

  6. Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

    Jun 26, 2026Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj SharmaMulti-Armed BanditsGraph Bandits

  7. Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals

    Jun 12, 2026Christoph Bauschmann, Setareh MaghsudiReward ModelingMulti-Armed Bandits

  8. Spectral bandits for smooth graph functions with applications in recommender systems

    May 19, 2026Tomáš Kocák, Michal Valko, Rémi Munos +2Graph Signal ProcessingMulti-Armed Bandits

  9. Bandits on graphs and structures

    May 5, 2026Michal ValkoMulti-Armed BanditsGraph Bandits

  10. Revealing graph bandits for maximizing local influence

    May 1, 2026Alexandra Carpentier, Michal ValkoMulti-Armed BanditsGraph Bandits

  11. Spectral bandits

    Apr 28, 2026Tomáš Kocák, Rémi Munos, Branislav Kveton +2Multi-Armed BanditsGraph Bandits

  12. Spectral bandits for smooth graph functions

    Apr 20, 2026Michal Valko, Rémi Munos, Branislav Kveton +1Graph Signal ProcessingMulti-Armed Bandits

  13. Online learning with noisy side observations

    Apr 15, 2026Tomáš Kocák, Gergely Neu, Michal ValkoOnline LearningGraph Bandits

  14. Spectral Thompson sampling

    Apr 15, 2026Tomas Kocak, Michal Valko, Remi Munos +1Thompson SamplingGraph Bandits

  15. An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability

    Mar 27, 2026Ashutosh Soni, Peizhong Ju, Atilla Eryilmaz +1Multi-Armed BanditsGraph Bandits

  16. Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization

    Feb 22, 2026Zirui Xu, Vasileios TzoumasOnline Submodular OptimizationMulti-Agent Coordination

  17. Flickering Multi-Armed Bandits

    Feb 19, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Armed BanditsBandit Learning

  18. Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting

    Sep 9, 2024Gianmarco Genalti, Marco Mussi, Nicola Gatti +3Multi-Armed BanditsGraph Bandits