Research map / Bandits and online learning / Multi-armed bandits
From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Use PAC-Wrapper instead of a worst-case sample-complexity method | Plackett-Luce best-item identification with winner feedback · Plackett-Luce best-item identification | sample complexity | Helped |
| Use Top-m Ranking feedback instead of winner-only feedback | PAC-Wrapper · Plackett-Luce best-item identification | sample complexity: 1/m factor | Helped |
| Use adaptive batch sampling with Score-Estimate rather than fixed-duration batch sampling | ε,δ-PAC best-item subroutine · Plackett-Luce ε-best-item identification | sample complexity: O\bigg(\frac{\thetg}{m\epsilon^2} \ln \frac{2n}{\delta}\bigg) vs. O\bigg(\frac{k}{m\epsilon^2} \ln \frac{2n}{\delta}\big | Helped |
| Increase the length of top-ranked feedback | PAC-Wrapper · Plackett-Luce best-item identification | sample complexity: 1/m | Helped |
| Decrease ε below the smallest item gap | PAC-Wrapper · Plackett-Luce ε-best-item identification | sample complexity | No clear effect |
| Increase the fixed query budget | Uniform-Allocation · Plackett-Luce fixed-budget best-item identification | success probability | Helped |
Closest papers by meaning
- Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.88)
- Instance-optimal PAC Algorithms for Contextual Bandits (NeurIPS 2022 · similarity 0.88)
- Majority-of-Three is an Optimal PAC Learner (NeurIPS 2026 · similarity 0.87)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.86)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.85)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.85)
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.