Research map / Bandits and online learning / Multi-armed bandits
Offline Learning for Combinatorial Multi-armed 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 Off-CMAB, the first offline learning framework for combinatorial multi-armed bandits, using a pessimistic CLCB algorithm with two data coverage conditions and near-optimal suboptimality bounds.
Problem
Offline learning of combinatorial actions in CMAB with probabilistically triggered arms, where only a pre-collected dataset is available and it may lack coverage of optimal or feasible actions.
Approach
Apply pessimism via base-arm lower confidence bounds fed into an approximate combinatorial oracle, with suboptimality analyzed through triggering-probability-modulated data coverage conditions that only require coverage of the optimal action's arms.
Key results
- CLCB reduces suboptimality gaps by 47.75% vs CUCB-Offline and 20.02% vs EMP in synthetic cascading bandit experiments.
- CLCB-LLM-C achieves at least 1.32x improvement over LFU and LEC on synthetic LLM cache setup.
- On SciQ with GPT-4o cost, CLCB-LLM-C reduces costs by up to 36.01% and 20.70% vs LFU and LEC.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CLCB instead of CUCB-Offline | Offline cascading bandits · Synthetic cascading bandits | suboptimality gap: 47.75% | Helped |
| Use CLCB instead of EMP | Offline cascading bandits · Synthetic cascading bandits | suboptimality gap: 20.02% | Helped |
| Use CLCB instead of the compared baselines | Offline cascading bandits · Yelp | suboptimality gap | Helped |
| Use CLCB-LLM-C instead of LFU and LEC | LLM cache · Synthetic LLM cache | improvement: at least 1.32× | Helped |
| Use CLCB-LLM-C instead of LFU | LLM cache · SciQ | cost: 36.01% | Helped |
| Use CLCB-LLM-C instead of LEC | LLM cache · SciQ | cost: 20.70% | Helped |
| Use the empirical mean for arrival probabilities instead of a UCB (ablation) | CLCB-LLM-C · LLM cache | suboptimality gap bound: a factor of sqrt{m} | Helped |
Surprising findings
- Using a UCB-based offline data generation policy, the proposed method still outperforms baselines significantly, consistent with theory.
Limitations
- Results depend on an alpha-approximate oracle and monotonicity/smoothness conditions on the reward function.
- Matching lower bound holds only up to logarithmic factors and for the k-path problem; variance-adaptive guarantees left open.
Experimental setup
Datasets: Yelp SciQ
Benchmarks: Yelp SciQ
Metrics: suboptimality gap cost
Baselines: CUCB-Offline EMP LFU LEC
Builds on: CUCB BCUCB-T CMAB-T triggering framework cascading bandits LLM cache bandit
Closest papers by meaning
- Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond (ICML 2024 · similarity 0.89)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.88)
- Adversarial Attacks on Combinatorial Multi-Armed Bandits (ICML 2024 · similarity 0.88)
- Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.87)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.87)
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.