Yixin Tao

Optimal Alternating Regret for Online Learning and Games

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $\Delta_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a...