Source-linked AI summary
Optimal Alternating Regret for Online Learning and Games
Yixin Tao, Weiqiang Zheng
TL;DR
The paper addresses the open question of minimax-optimal alternating regret for OLO and OCO. It introduces alternation-aware Hedge algorithms and matching lower bounds, obtaining optimal rates and fast convergence guarantees for two-player games.
Problem
The paper asks whether the prior T^1/3 dependence is fundamental and what the minimax-optimal alternating regret is for OLO and OCO.
Method
The paper develops AA-Hedge for simplex OLO and continuous AA-Hedge for general OCO, together with matching lower-bound constructions.
Results
OLO over the simplex has Θ(log d) alternating regret, while general OCO has Θ(d log(1 + T/d)) alternating regret.
Takeaways & Limitations
The bounds imply O(log d/T) convergence to NE in two-player zero-sum games and to CCE in two-player general-sum games.
Takeaways & Limitations
The stated lower-bound construction for OCO uses an oblivious randomized adversary, while the simplex guarantee is formulated for adaptive loss sequences.
Abstract
from arXiv · showhide
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 $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.
1 Introduction
The paper asks for minimax-optimal alternating regret in OLO and OCO, then develops matching bounds and applies them to fast convergence in two-player games.
- Open problem: The central question is whether the prior T^1/3 dependence is fundamental and what minimax-optimal alternating regret is for OLO and OCO.Alternating regret exploits knowledge of the previous loss when choosing the current strategy.
- OLO over the simplex: AA-Hedge uses the known previous loss so the instantaneous combined loss can be charged to a potential without additional terms.This potential analysis yields a constant alternating-regret bound independent of T.
- General OCO: For general OCO over compact convex sets, continuous AA-Hedge achieves O(d log(1 + T/d)) alternating regret.For polytopes with N vertices, the bound improves to 8 log N.
- General OCO: The OCO rate is minimax-optimal: an adversary can force Ω(d log(1 + T/d)) alternating regret, establishing Θ(d log(1 + T/d)).The lower bound holds for a compact convex set contained in the d-dimensional unit ℓ2 ball, and Ω(log T) is necessary even for the 2-dimensional unit ball.
- Applications to games: The results yield O(log d/T) convergence to NE in two-player zero-sum games and to CCE in two-player general-sum games.The paper identifies this as the first O(1/T) convergence to CCE in two-player general-sum normal-form games without additional poly log T factors.
2 Constant alternating regret for OLO over the simplex
The paper introduces alternation-aware Hedge for OLO on the simplex, exploiting the previous loss while controlling effective cumulative losses with a potential function. It achieves constant-in-T alternating regret, and an adaptive adversary proves the logarithmic dependence on dimension is necessary.
- Setup: The learner chooses from the simplex using the history of previous losses, then incurs loss against the effective vector c_t−1 + c_t.The previous loss is known when the current strategy is selected.
- Algorithm: AA-Hedge biases its distribution toward the most recent known loss and modifies Hedge updates to exploit alternation.Its played strategy is designed so the effective loss can be charged to a potential without additional terms.
- Analysis: A concave potential remains at most log d, yielding alternating regret at most 8 log d for every pure comparator.The proof uses η = 1/8 and β = 1/32.
- Lower bound: Θ(log d) is minimax-optimal because an adaptive adversary can force cumulative alternating regret of logarithmic order.The adversary removes the learner’s most-weighted action over the first d−1 rounds and then repeats the final loss.
3 Alternating regret for online convex optimization
The continuous AA-Hedge algorithm extends the simplex construction to general compact convex action sets using probability measures and barycentric actions. It achieves O(d log(1 + T/d)) alternating regret, while polyhedral OLO retains logarithmic dependence on the number of vertices.
- Algorithm: Continuous AA-Hedge replaces finite weights with probability measures, corrects the measure, and plays its barycenter.For the simplex with linear losses, it reduces to the finite-dimensional AA-Hedge algorithm.
- Distributional guarantee: The distributional alternating regret is bounded in terms of KL divergence to a reference measure.The guarantee applies to every comparator distribution ρ absolutely continuous with respect to µ.
- Instantiation: O(d log T) follows when the reference measure is uniform over the action set.A smoothing comparator over a contracted copy of the set contributes KL cost d log(1/δ), while convexity bounds the loss gap by 2δ.
- General OCO: O(d log(1 + T/d)) alternating regret is guaranteed for general d-dimensional compact convex sets.The algorithm uses the uniform probability measure over the action set.
- Polyhedral OLO: O(log N) alternating regret holds for polyhedral OLO with N vertices, including 8 log d on the d-dimensional simplex.The comparator can be chosen at a vertex, whose KL divergence under the uniform vertex measure is log N.
4 Matching lower bounds for OCO
The paper proves matching lower bounds for OCO: logarithmic dependence on T already occurs on the two-dimensional unit ball, and dimension multiplies this cost in higher-dimensional constructions. Together, these bounds establish minimax optimality.
- Two-dimensional lower bound: Ω(log T) alternating regret is unavoidable even on the two-dimensional Euclidean unit ball.Theorem 9 applies to every possibly randomized online algorithm.
- Two-dimensional construction: The two-dimensional construction uses logarithmically many blocks with common and rare convex losses and occasional rotations of the block center.The rare-loss probability is chosen on the order of the squared angular scale.
- Regret gap: The algorithm incurs expected loss at least ν in every block, while the hindsight endpoint incurs only O(ν^2) expected common loss per block.This gap yields Ω(K) = Ω(log T) alternating regret.
- Dimension dependence: Ω(d log(1 + T/d)) alternating regret is necessary over suitable d-dimensional convex sets.The construction embeds independent two-dimensional lower-bound phases across coordinate blocks.
- Optimality: The upper and lower bounds together determine the worst-case alternating regret as Θ(d log(1 + T/d)) across all T and d regimes.The lower-bound proof handles both T ≥ 8d and T < 8d.
5 Conclusion
The paper settles minimax-optimal alternating regret for both OLO and OCO. Its guarantees also yield alternating learning dynamics with O(1/T) convergence to coarse correlated equilibria in two-player general-sum games.
- Conclusion: O(log d) alternating regret is optimal for OLO over the simplex, while O(d log(1 + T/d)) is matched by a lower bound for OCO.These results settle minimax optimality in both settings.
- Conclusion: The results imply the first alternating learning dynamics with O(1/T) convergence to CCE in two-player general-sum games.The stated convergence guarantee is a consequence of the paper’s alternating-regret bounds.
A Proofs for Online Convex Optimization
The proof establishes the update's well-definedness and feasibility, then uses a one-step inequality to show that a potential function is nonincreasing.
- The proof first verifies that the update is well defined and feasible.
- It then applies a one-step inequality to prove that the potential function is nonincreasing.
A.1 Existence and feasibility of the update
The update is shown to be well-defined through strict concavity and a unique maximizer, while the resulting measure and barycenter remain feasible in X.
- Ft is differentiable because it is the logarithm of a bounded integrand over a compact set.
- F''t < 0 makes Ft strictly concave, and Ft tends to −∞ as |θ| grows, ensuring a unique maximizer.
- The variance bound is at most 1 because ft−1 lies in [−1, 1].
- EPt[ξt] = 0 and ξt(u) ∈ [−2, 2], so the weighting factor 1 − ξt(u)/2 is nonnegative on supp(Pt).
- Qt is a probability measure, and compact convexity of X places its barycenter xt in X.
A.2 A potential proof of logarithmic alternating regret
The logarithmic alternating-regret proof constructs a potential from effective loss and pointwise regret, establishes its monotonicity through a functional one-step inequality, and concludes the bound from the initial potential.
- A.2 A potential proof of logarithmic alternating regret: The potential is defined using the learner’s cumulative effective loss and pointwise regret against comparator points.
- A.2 A potential proof of logarithmic alternating regret: The update maintains EPt[ξt] = 0, defines Qt = (1 − ξt/2)Pt, and sets xt to its barycenter before Jensen’s inequality is applied.
- A.2 A potential proof of logarithmic alternating regret: The continuous analysis replaces finite-dimensional updates with probability measures and uses a functional one-step inequality.The inequality applies to measurable functions bounded in [−2, 2] with zero expectation under the reference measure.
- A.2 A potential proof of logarithmic alternating regret: The auxiliary function H is concave under β = η/4 and η ≤ 1/8, with H(−ξ) = 0 providing the comparison point.
- A.2 A potential proof of logarithmic alternating regret: Concavity yields H(ζ) ≤ 0, which implies Φt+1 ≤ Φt and establishes potential monotonicity over time.
A.3 Proof of Theorem 7
The proof applies potential monotonicity with fixed parameters, then converts the resulting potential inequality into the theorem’s regret bound using relative entropy and variance control.
- A.3 Proof of Theorem 7: Choosing η = 1/8 and β = 1/32 gives ΦT+1 ≤ Φ1 = 0.
- A.3 Proof of Theorem 7: The argument handles infinite KL divergence immediately and otherwise introduces the density ratio r = dρ/dµ.
- A.3 Proof of Theorem 7: Jensen’s inequality applied under ρ converts the density-ratio expression into the needed logarithmic comparison.
- A.3 Proof of Theorem 7: Selecting θ = Eρ[fT] and using Varρ(fT) ≤ 1 completes the first inequality in (4), with η and β fixed as specified.