Research map / Bandits and online learning / Online convex optimization and games
Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang
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 |
|---|---|---|---|
| Lift the decision set and use a normal barrier, modified sampling, and increasing learning rates | SCRiBLe for adversarial linear bandits · Adversarial linear bandits | high-probability regret: \otil\left(d^2\nu\sqrt{ T\ln\frac{1}{\delta}}+d^2\nu\ln\frac{1}{\delta}\right) against an oblivious adversary; \otil\lef | Improved |
| Replace the prior MDP approach's regularizer with a log-barrier and add an increasing learning-rate schedule | OMD for adversarial MDPs · Adversarial MDPs | high-probability regret: \otil\left(|X|\sqrt{J|A| L^{\star}\ln \frac{1}{\delta}}+|X|^5 |A|^2\ln^2 \frac{1}{\delta}\right) | Improved |
| Use the increasing-learning-rate approach to obtain small-loss guarantees | Adversarial MDP learning · Adversarial MDPs | high-probability regret: The new bound depends on L^{\star}; the prior bound is stated as \otil(J|X|\sqrt{|A|T}) | Improved |
Closest papers by meaning
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.90)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.90)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.90)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.90)
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.
