Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Oracle-Efficient Combinatorial Semi-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.
Proposes oracle-efficient combinatorial semi-bandit algorithms (adaptive and scheduled rare oracle query frameworks) that reduce oracle calls to O(log log T) or O(d log log T) while retaining near-optimal gap-free regret for linear, covariance-dependent, and general monotone rewards.
Problem
Combinatorial semi-bandits require solving an NP-hard combinatorial optimization oracle at every round, so oracle usage (adaptivity and query complexity) grows linearly in T; the paper asks how to keep near-optimal gap-free regret with far fewer oracle calls.
Approach
Two frameworks for rare oracle queries: AROQ triggers an oracle call only when a base arm's epoch-wise selection count doubles-plus-sqrt(Tm/d) threshold is met (per-arm epochs), and SROQ uses a fixed doubly-exponential time grid with an elimination-based batch strategy that queries oracles only at scheduled epochs, with representative actions per base arm.
Key results
- AROQ-CMAB and SROQ-CMAB achieve regret Õ(√(mdT)) and Õ(m√(dT)) respectively with O(d log log(Tm/d)) and Θ(log log T) adaptivity complexity, versus Θ(T) for CUCB.
- In the synthetic experiment (d=20, m=3), the proposed algorithms show significantly lower oracle adaptivity and query complexities and faster runtime than CUCB, with slightly higher regret.
- Covariance-adaptive variants achieve regret Õ(√(d max_a Σ σ_i²(a) T)) with Θ(log log T) adaptivity and O(d² log log T) query complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive rare oracle queries instead of querying every round | linear worst-case CMAB · Linear (worst-case) | oracle adaptivity and query complexity: \(\Theta(T)\) to \(O(d\log\log(Tm/d))\) | Helped |
| use adaptive rare oracle queries instead of querying every round | linear worst-case CMAB · Linear (worst-case) | regret bound: \(\tilde{O}(\sqrt{mdT})\) for both | No clear effect |
| use scheduled rare oracle queries rather than adaptive rare oracle queries | linear worst-case CMAB · Linear (worst-case) | adaptivity complexity: \(O(d\log\log(Tm/d))\) to \(\Theta(\log\log T)\) | Helped |
| use scheduled rare oracle queries rather than adaptive rare oracle queries | linear worst-case CMAB · Linear (worst-case) | regret bound: \(\tilde{O}(\sqrt{mdT})\) to \(\tilde{O}(m\sqrt{dT})\) | Hurt |
| use covariance-adaptive rare oracle queries instead of querying every round | covariance-dependent CMAB · Linear (covariance-dependent) | oracle adaptivity and query complexity: \(\Theta(T)\) to \(O(d^2\log(Tm))\) | Helped |
| use scheduled rather than adaptive covariance-adaptive rare oracle queries | covariance-dependent CMAB · Linear (covariance-dependent) | adaptivity complexity: \(O(d^2\log(Tm))\) to \(\Theta(\log\log T)\) | Helped |
| use scheduled rather than adaptive covariance-adaptive rare oracle queries | covariance-dependent CMAB · Linear (covariance-dependent) | worst-case regret bound: \(\tilde{O}(\sqrt{mdT})\) to \(\tilde{O}(m\sqrt{dT})\) | Hurt |
| use general-reward rare oracle queries instead of querying every round | general-reward CMAB · General rewards | oracle adaptivity and query complexity: \(\Theta(T)\) to \(O(d\log\log(Tm/d))\) | Helped |
| use scheduled rather than adaptive rare oracle queries | general-reward CMAB · General rewards | adaptivity complexity: \(O(d\log\log(Tm/d))\) to \(\Theta(\log\log T)\) | Helped |
| use scheduled rather than adaptive rare oracle queries | general-reward CMAB · General rewards | regret bound: \(\tilde{O}(L\sqrt{mdT})\) to \(\tilde{O}(Lm\sqrt{dT})\) | Hurt |
| use SROQ-CMAB rather than AROQ-CMAB | synthetic linear-reward experiment (d=20, m=3) · Synthetic linear rewards | runtime | Helped |
| use AROQ-CMAB rather than CUCB | synthetic linear-reward experiment (d=20, m=3) · Synthetic linear rewards | regret | Hurt |
Surprising findings
- SROQ-CMAB incurs somewhat larger regret than CUCB in experiments, consistent with its extra √m factor in theory.
- AROQ-CMAB also incurs slightly higher regret than CUCB, reflecting an extra logarithmic factor.
Limitations
- SROQ variants pay an extra √m factor in regret relative to worst-case optimal bounds.
- Covariance-adaptive algorithms achieve asymptotic regret bounds and require warm-up exploration of all arm pairs.
- Experiments are limited to a single synthetic setting (d=20, m=3).
Experimental setup
Datasets: synthetic linear bandit instances (d=20, m=3, means ~ Unif[0,1])
Benchmarks: synthetic linear combinatorial bandit (d=20, m=3)
Metrics: regret oracle adaptivity complexity oracle query complexity runtime
Baselines: CUCB OLS-UCB-C SDCB
Builds on: CUCB OLS-UCB-C SDCB
Closest papers by meaning
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.91)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.90)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.90)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.90)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.89)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.89)
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.