Research map / Learning theory and algorithms / Prediction and decision losses
Adaptive Concentration Inequalities for Sequential Decision Problems
Shengjia Zhao, Enze Zhou, Ashish Sabharwal, Stefano Ermon
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 |
|---|---|---|---|
| Use adaptive Hoeffding boundary instead of union-bound or LIL boundaries | Sequential sign testing · Bernoulli mean positiveness test | sample count: at least an order of magnitude fewer samples | Improved |
| Adaptive Hoeffding bound with adaptive stopping vs LIL bound of prior work | Finite-time threshold boundary · Boundary width comparison across n and delta | boundary tightness: roughly 1.5x tighter | Improved |
| Halve the adaptive boundary (ablation) | Sequential sign testing (AH-RW) · Bernoulli mean positiveness test | empirical accuracy: accuracy falls below 0.95 requirement despite ~4x speedup | Hurt |
| Exponentially sparse stopping times (batch sampling) applied to the boundary (ablation) | Sequential sign testing · Bernoulli mean positiveness test | sample count and accuracy | No clear effect |
| Exponentially sparse stopping times (batch sampling) in best arm identification (ablation) | Adaptive Hoeffding race · Best arm identification, Gaussian instance | sample count | Improved |
| Replace distribution-based elimination (state-of-the-art asymptotically) with adaptive Hoeffding race | Best arm identification · Gaussian instance, delta=0.05 | sample count | Improved |
Closest papers by meaning
- Near-Optimal Confidence Sequences for Bounded Random Variables (ICML 2021 · similarity 0.87)
- Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling (NeurIPS 2018 · similarity 0.86)
- Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards (NeurIPS 2020 · similarity 0.86)
- Fairness in Repeated Matching: A Maximin Perspective (AAAI 2026 · similarity 0.86)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.84)
- Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.84)
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.
