mlsanityData to 14 Oct 2026

Connections Between Mirror Descent, Thompson Sampling and the Information Ratio

arXiv 1905.11817 ↗First posted 28 May 2019cs.LG stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

The information-theoretic analysis by Russo and Van Roy (2014) in combination with minimax duality has proved a powerful tool for the analysis of online learning algorithms in full and partial information settings. In most applications there is a tantalising similarity to the classical analysis based on mirror descent. We make a formal connection, showing that the information-theoretic bounds in most applications can be derived from existing techniques for online convex optimisation. Besides this, for k-armed adversarial bandits we provide an efficient algorithm with regret that matches the best information-theoretic upper bound and improve best known regret guarantees for online linear optimisation on ℓp-balls and bandits with graph feedback.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 7; 2023: 6; 2024: 3; 2025: 2.

23 papers.

Sort:

  1. 2021Reinforcement Learning, Bit by Bitcited by 59
  2. 2022Anytime-valid off-policy inference for contextual banditscited by 37
  3. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
  4. 2022Generalization Bounds via Convex Analysiscited by 27
  5. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  6. 2021The Value of Information When Deciding What to Learncited by 15
  7. 2021Understanding Bandits with Graph Feedbackcited by 14
  8. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 14
  9. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  10. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  11. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 10
  12. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
11 more
  1. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5
  2. 2022Gaussian Imagination in Bandit Learningcited by 5
  3. 2023STEERING: Stein Information Directed Exploration for Model-Based Reinforcement Learningcited by 4
  4. 2023Bayesian Reinforcement Learning with Limited Cognitive Loadcited by 4
  5. 2023On Interpolating Experts and Multi-Armed Banditscited by 4
  6. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  7. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  8. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  9. 2021Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delayscited by 1
  10. 2022Improved Algorithms for Bandit with Graph Feedback via Regret Decompositioncited by 1
  11. 2025Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contextscited by 0