Research map / Bandits and online learning / Multi-armed bandits

Graph-Triggered Rising Bandits

ICML 2024 · Bandits and online learning › Multi-armed bandits · approach: Non-stationary and structured-reward bandits

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Graph-Triggered Rising Bandits, where a graph over arms governs how pulling one arm evolves the expected rewards of connected arms, generalizing rested and restless rising bandits, with NP-hardness, closed-form optimal policies for clique structures, and regret bounds.

Problem

Learning in rising bandits where pulling an arm changes the expected rewards of graph-connected arms; generalizes rested and restless bandits, and the optimal policy and regret minimization are unclear for general graphs.

Approach

Arms are linked by an undirected graph so that a pull of arm i advances the evolution of its own reward and of all its neighbors; rested and restless bandits are recovered as the identity and all-ones graphs. For block-diagonal (clique) graphs the optimal policy is greedy within the best clique, and the authors give regret bounds for deterministic and stochastic cases.

Key results

• Computing the optimal policy for a general graph G in GTRBs is NP-hard (Theorem 1), while for block-diagonal (clique) graphs the optimal policy is greedy within the best clique and has closed form (Theorem 2).
• DR-BG-UB and DR-G-UB achieve sublinear deterministic regret with graph-dependent bounds; R-□-UCB, which does not need the graph, attains e O(T^{2/3}) variance term plus graph-dependent bias terms in the stochastic case.
• R-□-UCB's bounds match up to constants the known results for the rested and restless rising bandit corner cases.

Surprising findings

• The stochastic algorithm R-□-UCB plays as if the graph were the identity (rested) and never needs the graph, yet still obtains sublinear regret for any graph.

Limitations

• Optimal policy for general graphs is NP-hard, so the clairvoyant benchmark is not computable in general.
• Stochastic regret bounds contain a T^{2/3} variance term and the restless bias term has a suboptimal dependence on stochasticity.
• Analysis is restricted to rising (non-decreasing concave) reward evolutions and undirected graphs in the main text.

Experimental setup

Metrics: expected policy regret

Baselines: R-□-UCB (Metelli et al., 2022)

Builds on: rested and restless rising bandits (Metelli et al., 2022) R-UCB / sliding-window UCB estimator (Metelli et al., 2022) restless bandits (Tekin & Liu, 2012)

Closest papers by meaning

• Networked Restless Bandits with Positive Externalities (AAAI 2023 · similarity 0.89)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits (NeurIPS 2020 · similarity 0.89)
• Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.88)
• Efficient Graph Bandit Learning with Side-Observations and Switching Constraints (AAAI 2025 · similarity 0.87)
• Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.87)
• On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.86)