REVIEW 3 major objections 4 minor 25 references
Mirror Descent and the Information Ratio
T0 review · 3 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read This paper proves that a Bayesian quantity called the information ratio controls the stability of mirror descent, converting non-constructive information-theoretic regret bounds into explicit algorithms and yielding a bandit algorithm…
desk verdict A valuable and likely sound bridge from information ratios to mirror-descent stability, but the showcased sqrt(2dn) bandit bound rests on a stability lemma whose printed proof does not compute. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the paper's generalised information ratio (Definition 4), a triple $(\alpha,\beta,\lambda)$ with the property that for every posterior distribution there is an exploratory action distribution whose expected one-step regret is at most $\alpha + \beta^{1-1/\lambda} E[D(E[A^*|\Phi_A(Z),A],E[A^*])]^{1/\lambda}$. On the algorithmic side the workhorse is the stability term $\Psi_q(x)=D^*(\nabla F(q)-x,\nabla F(q))$ that appears in the standard MD/FTRL regret decomposition. The key move is to define an objective $\Lambda_{q,\eta}(z,a^*,p,g)$ that adds together sampling loss, estimator bias, and this stability term, then prove by Sion's minimax theorem (a classical convexity/compactness criterion for exchanging a minimum and a maximum) and a Bregman-duality calculation that its inf-sup value is bounded by the information ratio. That inequality is what converts an information-theoretic bound into an explicit policy; for bandits, the concrete estimator $g$ from Section 9 is the object that makes the bound tight.
What would settle it
Take the estimator $g$ in Section 9, fix any $q$ in the relative interior of the simplex and any $z \in [0,1]^d$, and verify the identity $E[\langle b-c, g(A,\Phi_A(z))/p(A)\rangle]=\langle b-c,z\rangle$ for all actions $b,c$; a single nonzero deviation means Eq. (14) carries an unaccounted bias term. Independently, maximise the quotient in Lemma 19 over $q$ and $z$ at $\eta=\sqrt{2}$: any value exceeding $\eta\sqrt{d}/4$ would break the bandit bound.
Extended reading notes
Core claim
The paper's central claim is Theorem 9 together with Corollary 10: if a partial monitoring game has an information ratio of $(\alpha,\beta,\lambda)$ with $\lambda>1$, then the value $\Lambda^*_{\eta}$ of the exploration-by-optimisation objective is at most $\alpha + \beta(1-1/\lambda)(\eta/\lambda)^{1/(\lambda-1)}$, and the mirror-descent/FTRL policy of Algorithm 3 has adversarial regret $R_n \le n(\epsilon + \epsilon_D + \alpha) + \operatorname{diam}(D)^{1/\lambda}(\beta n)^{1-1/\lambda}$, where $\epsilon$ is an optimisation precision that can be taken arbitrarily small and $\epsilon_D$ vanishes when $D=\operatorname{conv}(A)$. Section 9 sharpens this for d-armed bandits: with the potential $F(q)=-2\sum_{i=1}^d\sqrt{q_i}$, sampling from the mirror-descent point itself, and the explicit unbiased estimator $g$ displayed there, the regret decomposition in Eq. (14) yields $R_n \le \sqrt{2dn}$.
Load-bearing premise
For the finite-armed bandit result, the entire $\sqrt{2dn}$ bound rests on the closed-form estimator in Section 9 being exactly unbiased for every loss vector and on the stability inequality of Lemma 19 holding for all $q$ and $z$; the paper reports that the estimator was found by an extended symbolic computation and compresses the proof of that inequality into a lengthy calculation. If either condition fails, the regret decomposition in Eq. (14) gains an unaccounted term.
Editorial extensions
If this is right
- Any game with an $(\alpha,\beta,\lambda)$ information ratio gets an explicit MD/FTRL policy with regret at most $n(\epsilon+\epsilon_D+\alpha)+\operatorname{diam}(D)^{1/\lambda}(\beta n)^{1-1/\lambda}$, so information-theoretic existence proofs for partial monitoring become algorithmic recipes.
- For finite non-degenerate locally observable partial monitoring games, Algorithm 3 is a finite convex program and achieves $R_n \le n\epsilon + 6|\Sigma||\mathcal{A}|^{3/2}\sqrt{n\log|\mathcal{A}|}$, matching the best known rate.
- For d-armed adversarial bandits, mirror descent with the explicit estimator achieves $\sqrt{2dn}$, improving the previous efficient algorithm's $\sqrt{2dn}+48d$ bound.
- The adaptive information-ratio version yields data-dependent regret bounds, and the corresponding FTRL variant can tune its learning rate online using observed signals.
Reading between the lines
- The same theorem gives a computational route to algorithm design: in finite games, any claimed information ratio can be plugged into the convex problem defining $\Lambda^*_\eta$ and the output is a concrete policy, so hand-derived estimators like the one in Section 9 may be replaceable by numerical search.
- For continuous action or signal spaces the obstruction is mainly technical, since the minimax exchange requires compactness; discretising the game and passing to the limit is a natural way to test whether the same regret bounds hold with an extra approximation term.
- A natural test of the approach is to run the same estimator search for graph feedback or linear bandits, where information ratios are known; the paper's general theorem predicts matching constants if suitable unbiased estimators exist.
- Because the bandit bound matches the best known information-theoretic upper bound, the estimator in Section 9 is a candidate for proving matching lower-order or first-order variants, though the paper itself does not establish those.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a general framework connecting the information ratio of Russo and Van Roy to the stability term in mirror descent and follow-the-regularized-leader for linear partial monitoring. After defining a generalized (α,β,λ)-information ratio, it proves Bayesian-regret bounds for information-directed sampling and shows (Theorem 9) that an information-ratio bound implies a bound on the saddle value Λ*η, yielding an explicit Algorithm 3 with adversarial regret n(ε+ε_D+α)+diam(D)^{1/λ}(βn)^{1−1/λ}. An adaptive version is also given. The framework is applied to finite-armed bandits, where an estimator g is proposed and the regret bound Rn≤√(2dn) is claimed, improving on the previous √(2dn)+48d. The main structural argument appears sound, but the proof of the key stability lemma for the bandit application is algebraically incorrect as printed, and a second supporting lemma relies on an unproved calculation.
Significance. If the central results are valid, the paper makes a substantial conceptual contribution: it shows that information-ratio bounds can be converted into constructive mirror-descent/FTRL policies, unifying two previously separate toolkits. Theorem 9, Corollary 10, and the adaptive theorems are elegant and likely to be influential. The claimed √(2dn) bandit improvement is modest but clean and exactly the sort of parameter-free consequence advertised. However, the current manuscript does not establish the headline bandit bound because Lemma 19 is internally inconsistent, and Theorem 12 depends on an omitted algebraic step. The framework is promising and probably correct, but the most visible application is unverified in the present version.
major comments (3)
- [Section 9, Lemma 19 (Eq. (14))] The proof of Lemma 19 as printed is not a valid proof of the stated bound. With F(q)=-2∑√q_i, the dual Bregman formula gives per-component stability Ψ_q(v)=q_b^{3/2}v_b^2/(1+v_b√q_b), so substituting v=ηg(a,Φ_a(z))/q_a and summing yields a denominator 1+ηg_b√q_b/q_a, not the printed √(1/q_b+ηg_b/q_a). The displayed calculation is therefore internally inconsistent. A direct numerical check confirms this: for d=2, q=(1/2,1/2), z=(1,1), η=1, the first display evaluates to about 0.504, exceeding the claimed bound η√d/4≈0.3535, while the exact value is about 0.335. Since Eq. (14) and the final bound Rn≤√(2dn) rest entirely on this lemma, the bandit claim is not established by the current proof. Please replace the 'messy calculation' with a correct derivation or a machine-checked computation.
- [Section B, Lemma 23] Lemma 23 asserts that the maximizer r satisfies r≤e q by 'a tedious calculation', but the calculation is not supplied. The lemma is used at the inequality marked (⋆) in the proof of Theorem 12, which in turn is needed for Corollary 13. As printed, Theorem 12 and Corollary 13 are conditional on an unverified algebraic fact. Please provide the missing argument or a citation to a proof.
- [Section 9, estimator g] The estimator g is introduced as the output of an 'extended Mathematica session' and its unbiasedness is asserted without proof. The stability claim is exactly Lemma 19, whose proof fails as noted above. Please give a self-contained derivation of the estimator and verify both the unbiasedness condition and the stability bound explicitly, or state the result as conditional on a computation that is included in full.
minor comments (4)
- [References and text] There are several author-name typos, including 'Szespvári' for 'Szepesvári' and 'György' with accent corruption; please correct them throughout.
- [Section 9] The phrase 'After an extended Mathematica session' is informal for a journal; describing the derivation would improve reproducibility.
- [Eq. (14)] The displayed line break after the second inequality is typographically confusing; consider aligning the inequalities more clearly.
- [Section 9] The remark that the bound is immediate for n≤4 is not justified in the text; if kept, please give a one-line argument or remove it.
Circularity Check
No significant circularity: the information-ratio bound is a stated assumption, and the bandit estimator is explicitly constructed and then verified rather than fitted to force the regret bound.
full rationale
The paper's derivation chain is self-contained in the relevant sense. Definition 4 introduces the generalized information ratio as an assumption about a partial-monitoring game, and Theorem 5 derives a Bayesian regret bound from it via Jensen's inequality and telescoping Bregman divergences; this is a standard implication, not a hidden restatement. Theorem 9 then converts the information-ratio bound into a bound on the stability-optimization value Lambda*_eta; the proof explicitly selects the estimator g and exploratory distribution p supplied by the information-ratio assumption and applies elementary optimization. No equation in this chain defines its conclusion into its inputs. For the d-armed bandit example, the paper imports an information-ratio bound for the potential F(q) = -2 sum sqrt(q_i) from Lattimore and Szepesvári [2019]; this is a parameter-free theorem from prior work, not a uniqueness claim or an unverified assertion unique to this paper, so it does not create circularity. The subsequent Section 9 contribution is constructive: rather than claiming a prediction from fitted values, the paper explicitly proposes the estimator g(a,sigma)_b, states its unbiasedness as a checkable algebraic property, and proves Lemma 19 as a bound on the resulting stability term. Even if Lemma 19's displayed calculation has the algebraic issues described in the skeptic note, that would be a correctness or proof-gap problem, not a circularity problem, because the claimed bound is not equivalent to the estimator's definition by construction. The 'extended Mathematica session' remark is a search heuristic for finding an explicit estimator; the estimator is then exhibited and analyzed, not used as a fitted parameter that is later renamed a prediction. Self-citations to the authors' own earlier work occur, but they are used as ordinary references to independent published theorems, not as the sole justification of a premise that is itself the paper's conclusion. Therefore no circular step is present.
Assumptions & free parameters
assumptions (5)
- domain assumption Assumption 1: finite action set, bounded losses in [0,1], D compact with non-empty relative interior, Legendre potential with finite diameter on D.
- domain assumption The partial monitoring game has a generalized information ratio (alpha, beta, lambda) (Definition 4) or adaptive version (Definition 14).
- standard math Sion's minimax theorem can be applied after the compact approximation D_epsilon (Theorem 9, Step 2).
- ad hoc to paper Lemma 23's claim that the maximizer r satisfies r <= e q, obtained by 'a tedious calculation'.
- ad hoc to paper The explicit estimator g in Section 9 is unbiased and satisfies Lemma 19's stability bound.
Cite this review
Pith. "Pith review of Mirror Descent and the Information Ratio." pith.science (2026). https://pith.science/paper/LJDCBQWA
@misc{pith2026200912228,
author = {Pith},
title = {Pith review of: Mirror Descent and the Information Ratio},
year = {2026},
howpublished = {\url{https://pith.science/paper/LJDCBQWA}},
note = {Machine review of arXiv:2009.12228}
}
read the original abstract
We establish a connection between the stability of mirror descent and the information ratio by Russo and Van Roy [2014]. Our analysis shows that mirror descent with suitable loss estimators and exploratory distributions enjoys the same bound on the adversarial regret as the bounds on the Bayesian regret for information-directed sampling. Along the way, we develop the theory for information-directed sampling and provide an efficient algorithm for adversarial bandits for which the regret upper bound matches exactly the best known information-theoretic upper bound.
Reference graph
Works this paper leans on
-
[1]
J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Conference on Learning Theory, pages 263--274. Omnipress, 2008
work page 2008
-
[2]
C. Allenberg, P. Auer, L. Gy\" o rfi, and G. Ottucs\' a k. Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In Proceedings of the 17th International Conference on Algorithmic Learning Theory, pages 229--243, Berlin, Heidelberg, 2006. Springer-Verlag
work page 2006
-
[3]
J.-Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In Proceedings of the 22nd Conference on Learning Theory, pages 217--226, 2009
work page 2009
-
[4]
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 322--331. IEEE, 1995
work page 1995
-
[5]
S. Bubeck and R. Eldan. Exploratory distributions for convex functions. Mathematical Statistics and Learning, 1 0 (1): 0 73--100, 2018
work page 2018
-
[6]
S. Bubeck and M. Sellke. First-order bayesian regret analysis of thompson sampling. In Algorithmic Learning Theory, pages 196--233, 2020
work page 2020
- [7]
- [8]
Show all 25 references
-
[9]
Bubeck, Y-T
S. Bubeck, Y-T. Lee, and R. Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72--85, 2017
2017
-
[10]
Dong and B
S. Dong and B. Van Roy . An information-theoretic analysis for T hompson sampling with many actions. In Advances in Neural Information Processing Systems, Red Hook, NY, USA, 2018. Curran Associates Inc
2018
-
[11]
S. Dong, T. Ma, and B. Van Roy. On the performance of thompson sampling on logistic bandits. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1158--1160, P...
2019
-
[12]
G. J. Gordon. Regret bounds for prediction problems. In Proceedings of the 12th Conference on Learning Theory, pages 29--40, 1999
1999
-
[13]
Kirschner, T
J. Kirschner, T. Lattimore, and A. Krause. Information directed sampling for linear partial monitoring. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 232...
2020
-
[14]
Lattimore
T. Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. arXiv preprint arXiv:2006.00475, 2020
2006 arXiv
-
[15]
Lattimore and Cs
T. Lattimore and Cs. Szepesv \'a ri. An information-theoretic approach to minimax regret in partial monitoring. In Proceedings of the 32nd Conference on Learning Theory, pages 2111--2139, Phoenix, USA, 2019. PMLR
2019
-
[16]
Lattimore and Cs.\ Szepesv \'a ri
T. Lattimore and Cs.\ Szepesv \'a ri. Bandit algorithms. Cambridge University Press, 2020
2020
-
[17]
Lattimore and Cs
T. Lattimore and Cs. Szespv \'a ri. Exploration by optimisation in partial monitoring. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of 33rd Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2488--2515, 2020
2020
-
[18]
A. S. Nemirovsky. Efficient methods for large-scale convex optimization problems. Ekonomika i Matematicheskie Metody, 15, 1979
1979
-
[19]
R. T. Rockafellar. Convex analysis. Princeton university press, 2015
2015
-
[20]
Russo and B
D. Russo and B. Van Roy . Learning to optimize via information-directed sampling. In Advances in Neural Information Processing Systems, pages 1583--1591. Curran Associates, Inc., 2014
2014
-
[21]
Russo and B
D. Russo and B. Van Roy . An information-theoretic analysis of T hompson sampling. Journal of Machine Learning Research, 17 0 (1): 0 2442--2471, 2016. ISSN 1532-4435
2016
-
[22]
M. Sion. On general minimax theorems. Pacific Journal of mathematics, 8 0 (1): 0 171--176, 1958
1958
-
[23]
Wei and H
C-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Conference On Learning Theory, pages 1263--1291. JMLR.org, 06--09 Jul 2018
2018
-
[24]
Zimmert and T
J. Zimmert and T. Lattimore. Connections between mirror descent, thompson sampling and the information ratio. In Advances in Neural Information Processing Systems, pages 11973--11982. Curran Associates, Inc., 2019
2019
-
[25]
Zimmert and Y
J. Zimmert and Y. Seldin. An optimal algorithm for stochastic and adversarial bandits. In AISTATS, pages 467--475, 2019
2019
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.