Research map / Bandits and online learning / Multi-armed bandits
Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits
Reda Ouhamma, Rémy Degenne, Pierre Gaillard, Vianney Perchet
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 |
|---|---|---|---|
| analyse LSA with generic index-based proof instead of original proof | LSA · Thresholding bandit unit cost | exponent constant in loss bound: 1/16020 -> 4005 times better | Improved |
| analyse APT with new proof | APT · Thresholding bandit zero-one loss | exponent constant in loss bound: 1/32 -> 1/4 | Improved |
| use Frank-Wolfe index F(n,x;a)=max{x,1}-log max{x,1}+log(n/a) (FWT) instead of APT index | APT · Thresholding bandit weighted errors | bound onset (T needed) | Improved |
| use adaptive algorithms (APT, LSA, FWT) instead of the non-adaptive oracle with uniform allocation | non-adaptive oracle · N(1,1)/N(-1,1) arms, K=100 | error ratio to oracle | Improved |
| use adaptive stop-on-nonzero sampling instead of uniform allocation | uniform allocation · toy problem on {0,x} | expected errors: 1/2^(T/K) -> 1/2^(T/2) | Improved |
| use FWT instead of APT | APT · mu_k=(-1)^k(k/K)^2, K=50 | error ratio to oracle | Improved |
| use FWT instead of LSA | LSA · Thresholding bandit simulations | error ratio to oracle | No clear effect |
| set LSA parameter alpha to 1 instead of 1/10 | LSA · Thresholding bandit unit cost | exponent constant in loss bound: 1/16020 -> 4005 times better | Improved |
| sample arms near threshold less (follow oracle M-shape allocation) | sequential algorithms · Thresholding bandit | feasibility | Hurt |
Closest papers by meaning
- Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination (NeurIPS 2021 · similarity 0.88)
- Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.87)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.87)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.86)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.86)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 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.
