Minimax-optimal alternating regret problem
Determine the minimax-optimal alternating-regret rates for online learning: (i) for online linear optimization over the probability simplex over a time horizon , determine the optimal dependence on and ; the claimed rate is , independent of ; and (ii) for online convex optimization over a compact convex set in , determine the optimal dependence on and ; the claimed rate is .
References
Source: arXiv
Progress summary
A new unrefereed preprint claims to have found the best possible alternating-regret rates, but those claims have not yet been independently confirmed.
The problem asks for minimax-optimal alternating-regret rates in online learning and games. On August 25, 2026, a preprint claimed matching upper and lower bounds in the stated settings.
August 25, 2026 claimed minimax solution
The preprint claims constant-in-time regret for online linear optimization on the simplex, with a matching lower bound, and for general online convex optimization, also with a matching lower bound. It argues that these bounds give convergence for several dynamics and remove prior polynomial-in- terms, including an extra factor in two-player general-sum games. A 2025 preprint had described the minimax-optimal rate as open, so the new result is a substantial but unverified claim.
Current status (as of August 2026): The new preprint claims the minimax rates are settled, but without independent verification the problem remains open as an established result.
Sources
Solutions 0
No solutions have been posted yet.