- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper establishes the existence of a fixed step size for which the Optimistic Hedge algorithm achieves a horizon-independent regret bound in all finite games of given dimensions. The proof is non-constructive and relies on tools from real analytic geometry, and, as a result, both the step size and the regret bound remain implicit, and their dependence on the number of players and actions is unknown.
Critical strengths
The paper’s main strength lies in its result and its connection with distant tools from real analytic geometry, which, despite being non-constructive, remain of some interest.
Critical weaknesses
First, I have some reservations about the value of the result from a machine learning and computational viewpoint. The step size for which Optimistic Hedge achieves constant regret as well as the resulting bound are left implicit and are not computable from the analysis, and their existence relies on general and rather exotic non-constructive tools from real analytic geometry, notably the Noetherianity of rings of analytic germs. As a consequence, even from a theoretical standpoint, I believe the result does not meaningfully achieve the aim of establishing a constant regret bound for this algorithm, as an important motivation for such a result would be to provide new computational or algorithmic insights and explicit bounds that other researchers in the field or practitioners could build upon. This should be contrasted with the paper by Daskalakis, Fishelson & Golowich, "Near-Optimal No-Regret Learning in General Games," which establishes an explicit polylogarithmic regret bound for Optimistic Hedge and introduces new and insightful computational tools for proving such bounds, notably their higher-order smoothness framework, which the present paper also makes use of.
Second, I found the proofs quite difficult to follow, and I believe the exposition could be substantially improved. Indeed, the tools introduced are from highly specialized subareas of pure mathematics and clearly unfamiliar to researchers in learning in games and likely to all of the machine learning community, and despite this, they receive only minimal explanation. For this reason also, I believe the paper, if well rewritten, would be better suited to a mathematical game theory or theoretical computer science conference or journal. It is also unclear how specific the argument is to Optimistic Hedge given the generality of the tools used, in that the new part of the analysis appears to rely on the analyticity of the update map while the Hedge-specific ingredients are imported from prior work, often again with minimal and terse exposition. This reinforces my view that the paper in its current form is not clear enough and does not help clarify our understanding of the Optimistic Hedge algorithm, or more generally of learning in games.
Questions for authors
- What part of the argument are specific to Optimistic Hedge in the proof, and what parts would generalize to other algorithms ?
- How is the finite game structure specifically used here ? Can one obtain at least an order of magnitude for the regret bound ?
- Lemmas C.8 and C.9 rely on results stated for complex analytic settings. How exactly do these transfer to the real analytic setting used here, and where is semianalyticity essential ? Could the proof be made more simple and natural by using specific tools tailored to this algorithm and games rather than very general, non-constructive tools ?
- What is the practical purpose of such a result ? Even from a theoretical standpoint, does this algorithm help us better understand the behaviour of Optimistic Hedge for a given fixed, explicit step size ?