Minimax-optimal alternating regret problem

Determine the minimax-optimal alternating-regret rates for online learning: (i) for online linear optimization over the probability simplex $\Delta_d$ over a time horizon $T$ , determine the optimal dependence on $d$ and $T$ ; the claimed rate is $\Theta(\log d)$ , independent of $T$ ; and (ii) for online convex optimization over a compact convex set in $\mathbb{R}^d$ , determine the optimal dependence on $d$ and $T$ ; the claimed rate is $\Theta\!\left(d\log\left(1+T/d\right)\right)$ .

References

Primary source

arXiv

Additional references

Optimal Alternating Regret for Online Learning and Games — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

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 $\mathrm{OLO}/\mathrm{OCO}$ settings.

August 25, 2026 claimed minimax solution

The preprint claims constant-in-time $\mathcal{O}(\log d)$ regret for online linear optimization on the simplex, with a matching lower bound, and $\mathcal{O}\!\left(d\log(1+T/d)\right)$ for general online convex optimization, also with a matching lower bound. It argues that these bounds give $\mathcal{O}(\log d/T)$ convergence for several dynamics and remove prior polynomial-in- $T$ terms, including an extra $\log T$ 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

No solutions have been posted yet.