Graph Bandits

Ask about this topic

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

16 papers0 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

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

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

    Graduate School of Information Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan

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

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

    Google Research · Tel Aviv University · Courant Institute

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

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

    Department of Computer Science, University of Colorado, Boulder, CO 80309, USA · INRIA, Paris, France

  4. 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

    Department of Computer and Information Sciences, University of Delaware, USA · Department of Computer Science, Iowa State University, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA

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

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

    Department of Electrical Engineering and Information Technology Ruhr University Bochum Bochum, Germany

  6. 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

    SequeL team Inria Lille France · SequeL team, Inria France · Microsoft Research New England +2

  7. Bandits on graphs and structures

    May 5, 2026Michal ValkoMulti-Armed BanditsGraph Bandits

    L’ÉCOLE NORMALE SUPÉRIEURE DE CACHAN

  8. Revealing graph bandits for maximizing local influence

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

    Universität Potsdam · SequeL team, Inria Lille - Nord Europe

  9. Spectral bandits

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

    ENS de Lyon, 15 Parvis Ren´e Descartes, 69342 Lyon, France · Inria Lille – Nord Europe, SequeL team · DeepMind Paris, 14 Rue de Londres, 75009 Paris, France +2

  10. Spectral bandits for smooth graph functions

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

    INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France · INRIA Lille - Nord Europe, SequeL team, France · Microsoft Research New England, Cambridge, MA, USA +1

  11. Online learning with noisy side observations

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

    SequeL team, INRIA Lille - Nord Europe · Universitat Pompeu Fabra, Barcelona, Spain

  12. Spectral Thompson sampling

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

    SequeL team, INRIA Lille - Nord Europe, France · SequeL team, INRIA Lille, France · Microsoft Research NE, USA +1

  13. 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

    Department of Electrical and Computer Engineering, The Ohio State University, Columbus, Ohio, USA · Department of Computer Science, University of Kentucky, Lexington, Kentucky, USA · Department of Computer Science and Engineering, The Ohio State University, Columbus, Ohio, USA

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

    Feb 22, 2026Zirui Xu, Vasileios TzoumasMulti-Agent CoordinationSubmodular Optimization

    Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

  15. Flickering Multi-Armed Bandits

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

    University of Colorado Boulder, USA. · INRIA Paris, France.

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

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

    Politecnico di Milano2026 Piazza Leonardo da Vinci 32, Milan, 20133, Italy