Research map / Bandits and online learning / Multi-armed bandits
Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy
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 Pairwise-Elimination (PE) and PE-CS algorithms for multi-armed bandits with cost subsidy, proving order-logarithmic instance-dependent cost and quality regret bounds and matching lower bounds for the known reference arm setting.
Problem
Minimizing cumulative cost in stochastic bandits subject to a per-step reward constraint defined relative to a reference arm (known or unknown best arm), i.e., the multi-armed bandits with cost subsidy (MAB-CS) problem.
Approach
Evaluate candidate arms in ascending cost order via pairwise elimination against a reference arm, reusing reference-arm samples across episodes and building on Improved-UCB rounds; PE-CS prepends a best-arm-identification stage to handle the unknown best-reward arm.
Key results
- PE and PE-CS achieve O(log T) instance-dependent upper bounds on both cost and quality regret.
- PE matches the lower bound up to constant factors for all known reference arm instances, so it is order-optimal.
- PE-CS offers better reliability than UCB-CS and ETC-CS in experiments on MovieLens and Goodreads, though TS-CS has lower average regret in some runs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Evaluate candidate arms against the known reference arm in ascending cost order using PE instead of UCB-CS Known ℓ | Known reference arm bandits · MovieLens 25M and Goodreads | summed cost and quality regret | Helped |
| Add a best-arm-identification stage before pairwise elimination | PE-CS · MovieLens 25M and Goodreads, subsidized best reward | summed cost and quality regret | Helped |
| Use PE-CS instead of UCB-CS | Subsidized best reward bandits · MovieLens 25M and Goodreads | summed cost and quality regret | Helped |
| Use TS-CS instead of PE-CS | Subsidized best reward bandits · MovieLens 25M and Goodreads | average summed regret | Helped |
| Use TS-CS instead of PE-CS | Subsidized best reward bandits · MovieLens 25M and Goodreads | regret trend and reliability | Hurt |
| Use PE-CS instead of ETC-CS | Subsidized best reward bandits · Toy experiment, 12 four-arm instances | summed terminal cost and quality regret | Mixed |
| Use PE-CS instead of UCB-CS or TS-CS | Subsidized best reward bandits · Toy experiment, especially μ1 = 0.78 | successful constraint satisfaction | Helped |
| Use PE-CS rather than a method that interleaves exploration and exploitation | Subsidized best reward bandits · MovieLens 25M and Goodreads | regret reliability | Helped |
| Use asymmetric-PE, reusing more advanced reference-arm samples (ablation) | PE · Known reference arm setting | regret | Helped |
Surprising findings
- TS-CS achieves lower average regret than PE-CS, but shows a slow steady upward regret trend over time.
Limitations
- PE-CS is not order-optimal for all instances; gap to lower bound arises when identifying the best arm detracts from sampling cheap feasible arms.
- Costs in experiments are synthetic (uniform random) because royalty data is unavailable.
- Experiments use a finite set of arms derived from genre-level ratings with arbitrary reference arm choice.
Experimental setup
Datasets: MovieLens 25M Goodreads
Benchmarks: MovieLens 25M bandit instances Goodreads bandit instances
Metrics: cost regret quality regret summed terminal regret
Baselines: ETC-CS UCB-CS TS-CS UCB-CS Known l
Builds on: Improved-UCB MAB-CS framework Conservative Bandits UCB
Closest papers by meaning
- Lenient Regret for Multi-Armed Bandits (AAAI 2021 · similarity 0.89)
- Delay as Payoff in MAB (AAAI 2025 · similarity 0.88)
- On Multi-Armed Bandit with Impatient Arms (ICML 2024 · similarity 0.88)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.88)
- Contextual Linear Bandits with Delay as Payoff (ICML 2025 · 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.