Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Stochastic contextual bandits with graph feedback: from independence number to MAS number
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.
Establishes a minimax regret lower bound for stochastic contextual bandits with graph feedback via a new graph quantity beta_M(G) interpolating between independence number and MAS number, with matching upper bounds for self-avoiding contexts and transitively closed/undirected graphs.
Problem
Characterize the minimax regret of stochastic contextual bandits with feedback graphs across actions and complete cross-learning across contexts, where the independence number (multi-armed case) and MAS number (known upper bound) do not tightly describe the complexity.
Approach
Introduces graph quantity beta_M(G), the max total size of M disjoint independent sets with no edges from I_i to I_j for i<j, which interpolates between alpha(G) at M=1 and the MAS number m(G) for large M; proves a matching lower bound and arm-elimination algorithms with layering that match it under self-avoiding contexts or transitively closed/undirected graphs.
Key results
- Minimax lower bound Omega(sqrt(beta_M(G) T)) for T >= beta_M(G)^3, with beta_M(G) interpolating from alpha(G) at M=1 to m(G) when M >= m(G).
- Arm-elimination with layering achieves O~(sqrt(beta_M(G) T)) regret under self-avoiding contexts, matching the lower bound.
- For general contexts, regret O~(sqrt(min{overline-beta_M(G), m(G)} T)); tight for undirected or transitively closed graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the context-dependent graph quantity \beta_M(G) to characterize the minimax lower bound | Stochastic contextual bandits with graph feedback · Contextual bandits with graph feedback | minimax regret: \Omega(\sqrt{\beta_M(G) T}) | Mixed |
| Restrict context sequences to self-avoiding sequences | Arm elimination algorithm · Self-avoiding contexts | regret: \widetilde{O}(\sqrt{\beta_M(G)T}) | Helped |
| Allow general context sequences instead of self-avoiding sequences | Arm elimination with sequential game II · General context sequences | regret: \widetilde{O}\left(\sqrt{\min\left\{\overline{\beta}_M(G),\mathsf{m}(G)\right\}T}\right) | Mixed |
| Assume the feedback graph is undirected or transitively closed | Arm elimination algorithm · General context sequences | regret: \widetilde{O}(\sqrt{\beta_M(G)T}) | Helped |
| Use explore-then-commit and explore a minimum dominating set | Weakly observable feedback graphs with complete cross-learning · Weakly observable feedback graphs | regret: \widetilde{O}(\delta(G)^{1/3}T^{2/3}) | Helped |
| Increase the number of contexts to M\ge\mathsf{m}(G) | Stochastic contextual bandits with graph feedback · Contextual bandits with graph feedback | minimax regret: \Omega(\sqrt{\mathsf{m}(G)T}) | Mixed |
Surprising findings
- The optimal complexity with many contexts is governed by the MAS number rather than the independence number, closing a gap left by prior work.
Limitations
- null
Experimental setup
Metrics: minimax regret
Baselines: UCB with feedback graphs (Lykouris et al. style analysis) Contextual bandits with graph feedback upper bound O(sqrt(m(G)T)) Cross-learning bound O(sqrt(min{alpha(G)M,K}T))
Builds on: arm elimination bandits with feedback graphs (Alon et al.) cross-learning in contextual bandits
Closest papers by meaning
- Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.93)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.90)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.90)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.90)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.90)
- Mixed-Effects Contextual Bandits (AAAI 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.