Research map / Bandits and online learning / Online convex optimization and games
Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
Julian Zimmert, Tor Lattimore
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 the shifted importance-weighted estimator instead of the standard estimator (ablation) | OSMD with the 1/2-Tsallis entropy potential · Adversarial k-armed bandits | regret: \sqrt{8nk} -> \sqrt{2 k n} + 48k | Improved |
| Use a clipped separable potential instead of prior potentials | OSMD · Online linear optimization over \ell_p-balls, full information | regret: \mathcal O\left(\sqrt{\min\left\{1 / (p-1),\log(d)\right\}n}\right) | Improved |
| Transfer OSMD stability analysis to modified Thompson sampling with a Bayesian update | Modified Thompson sampling · Bayesian online learning | Bayesian regret | Improved |
Closest papers by meaning
- Looking Through the Mirror: Minimax-Optimal Regularized Regrets in Online Learning and Bandits (NeurIPS 2026 · similarity 0.89)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.89)
- Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits (JMLR 2021 · similarity 0.88)
- Information Directed Sampling for Sparse Linear Bandits (NeurIPS 2021 · similarity 0.88)
- An Information-Theoretic Analysis for Thompson Sampling with Many Actions (NeurIPS 2018 · similarity 0.88)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
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.
