Efficient Graph Bandit Learning with Side-Observations and Switching Constraints

Xueping Gong, Jiheng ZhangAAAI 2025 · DOI

Introduction

In many real-world sequential decision-making tasks, an agent's actions are constrained by physical or logical structures. For instance, a cleaning robot cannot teleport between rooms; it must navigate a physical path (a switching constraint). Simultaneously, the robot may learn about its environment beyond its immediate location, such as sensors detecting dirt levels in adjacent areas (side-observations).

Standard Multi-Armed Bandit (MAB) models typically assume that any arm can be selected at any time and that feedback is limited to the chosen arm. While Reinforcement Learning (RL) can model these constraints as state transitions, generic RL algorithms often fail to exploit the specific mathematical structure of graphs, leading to high computational costs and suboptimal learning speed. This paper introduces a dedicated "Graph Bandit" framework that simultaneously handles graph-structured side-observations and switching constraints with near-optimal efficiency.

Proposed Methodology

The authors propose two primary algorithms tailored to different levels of prior environmental knowledge:

  1. UCB-GGmax (Graph-agnostic): This algorithm is designed for scenarios where the agent does not know the exact feedback probabilities of the reward graph. It utilizes an Upper Confidence Bound (UCB) approach to identify nodes with high potential rewards or high uncertainty. To manage movement costs, it employs a doubling trick—staying at a node for exponentially increasing durations—and uses offline shortest-path planning (e.g., Dijkstra) to navigate the constraint graph efficiently.
  2. LP-GG (Graph-aware): When the reward graph structure and observation probabilities are known, this algorithm solves a Linear Programming (LP) problem to identify "informative" nodes. These are actions that provide the maximum information about the rest of the graph. By iteratively eliminating suboptimal nodes, LP-GG focuses exploration only where it is most beneficial, reducing switching costs to the theoretical minimum of $O(\log T)$.

Key Insights

  • Structural Advantage: By leveraging graph structures instead of treating the problem as a generic RL state-transition task, the proposed methods achieve a regret reduction factor of approximately $\sqrt{|V|}$, where $V$ is the number of nodes.
  • Space Efficiency: Traditional RL approaches often require $O(|V|^2)$ space. These graph-aware methods reduce this requirement to $O(|V|)$, significantly improving scalability for large-scale networks like road systems or product recommendation graphs.
  • Exploitation via Neighbors: A core innovation in UCB-GGmax is the ability to "peek" at uncertain nodes by visiting high-reward neighbors. This balances exploration and exploitation more effectively than standard local search methods.

Empirical Results

The researchers evaluated their algorithms using synthetic topologies (star, k-tree, etc.) and real-world datasets, including the California Road network and Amazon Product data.

Comparison of cumulative regret across different algorithms. The proposed LPGG and UCBGG variants significantly outperform standard Reinforcement Learning (Q-learning) and local UCB baselines.

As shown in the experimental results, the proposed algorithms consistently outperform benchmarks like Q-learning and Local UCB. Q-learning, in particular, proved unstable and required extensive hyperparameter tuning, whereas the graph bandit algorithms converged faster and maintained lower regret without such overhead.

Impact of graph size |V| on cumulative regret. The algorithms maintain sub-linear regret even as the number of nodes increases, demonstrating robust scalability.

Furthermore, the algorithms demonstrate excellent scalability. Even as the number of nodes $|V|$ increases, the regret remains sub-linear and well-behaved, confirming the theoretical minimax and instance-dependent regret upper bounds established by the authors.

Conclusion and Future Work

This framework provides a robust solution for bandit problems with complex structural constraints. While the current work focuses on undirected, static graphs, future research may extend these methods to directed graphs (e.g., one-way streets) and dynamic environments where the graph structure evolves over time. The transition from "overkill" RL methods to specialized graph bandit algorithms represents a significant step forward in both computational and sample efficiency for autonomous agents.

Summary updated

BibTeX
@inproceedings{gong2025efficient,
  author = {Xueping Gong and Jiheng Zhang},
  title = {{Efficient Graph Bandit Learning with Side-Observations and Switching Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i16.33854},
}
Figure