Research map / Bandits and online learning / Multi-armed bandits
Combinatorial Pure Exploration with Bottleneck Reward Function
Yihan Du, Yuko Kuroki, Wei Chen
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace uniform sampling of base arms in critical super arms with the bottleneck-adaptive sample strategy (BLUCB- vs BLUCB) (ablation) | BLUCB · synthetic s-t path and matching instances, FC | sample complexity | Improved |
| use bottleneck-searching and check-near-bottleneck stopping instead of BLUCB under small delta=exp(-1000) | BLUCB · FC setting, small delta | sample complexity | Improved |
| use BLUCB instead of CLUCB-B (CPE-L algorithm run with bottleneck reward) | fixed-confidence CPE-B · synthetic and air route instances, FC | sample complexity | Improved |
| use BLUCB instead of UniformFC uniform sampling | fixed-confidence CPE-B · synthetic and air route instances, FC | sample complexity | Improved |
| add the special acceptance scheme to BSR (BSAR vs BSR) (ablation) | BSAR · synthetic and air route instances, FB | error probability | Improved |
| use BSAR instead of CSAR-B (CPE-L fixed-budget algorithm with bottleneck reward) | fixed-budget CPE-B · synthetic and air route instances, FB | error probability | Improved |
| use BSAR instead of CUCB-B returning the empirical best super arm after T steps | fixed-budget CPE-B · synthetic and air route instances, FB | error probability | Improved |
| use BSAR instead of UniformFB uniform sampling | fixed-budget CPE-B · synthetic and air route instances, FB | error probability | Improved |
Closest papers by meaning
- Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback (AAAI 2021 · similarity 0.91)
- Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (AAAI 2024 · similarity 0.87)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.87)
- Near Optimal Non-asymptotic Sample Complexity of 1-Identification (ICML 2025 · similarity 0.86)
- FraPPE: Fast and Efficient Preference-Based Pure Exploration (NeurIPS 2025 · similarity 0.86)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.86)
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.
