← All AI/ML open problems

Optimization & optimizers · Learning dynamics & scaling · Multi-agent communication & games / Open question

Fast Self-Play at Every Step Size

Aggressive or persistent updates can keep cycling yet learn efficiently in self-play. This problem asks whether shrinking the learning rate is unnecessary throughout a concrete higher-dimensional game family. Efficiency payoff: Keep a productive fixed update scale in coupled learning when diminishing steps are unnecessary.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

For n≥5n\geq5, let Ai,i+1=−1A_{i,i+1}=-1, Ai+1,i=1A_{i+1,i}=1 cyclically and all other entries be zero. Under symmetric two-player self-play, set y0=0y_0=0, choose x0∈Δnx_0\in\Delta_n, and update yt+1=yt+ηAxty_{t+1}=y_t+\eta Ax_t, xt+1=ΠΔn(yt+1)x_{t+1}=\Pi_{\Delta_n}(y_{t+1}), where Π\Pi is Euclidean projection. For every fixed η>0\eta>0, does RT=2max⁡i(∑t=0T−1Axt)i≤C(n,η,x0)TR_T=2\max_i(\sum_{t=0}^{T-1}Ax_t)_i\leq C(n,\eta,x_0)\sqrt T hold for all T≥1T\geq1 and Lebesgue-almost-every x0x_0? Prove the bound or give a positive-measure counterexample.

Assumptions and scope

  • Both players use the same initialization and exact full payoff-vector feedback. The payoff matrix is the unweighted directed cycle made skew-symmetric; its uniform mixed strategy is an interior equilibrium.
  • Eta is fixed independently of T, and C may depend on n, eta and initialization but not T. This is quadratic FTRL/dual averaging: projection of accumulated payoffs, not projection of the previous primal iterate plus one gradient.
  • Regret is the total external regret of both players. A square-root bound implies an O(1/sqrt(T)) duality gap for averaged strategies; convergence of the individual iterates is not required. Almost-everywhere refers to relative Lebesgue measure on the simplex.

What would settle it?

The displayed bound for every fixed eta and n, or some fixed n and eta with a positive-measure initialization set on which R_T/sqrt(T) is unbounded. A bound for a vanishing or horizon-tuned stepsize, or only sufficiently large fixed steps, does not settle it.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Lazarsfeld et al. prove O(sqrt(T)) regret for sufficiently large constant steps and boundary invariance for arbitrary positive steps; Section 5.2 explicitly leaves the full constant-step regret question open. Their unweighted, vertex-initialized fictitious play also has O(1) regret with tournament tiebreaking. Optimistic or alternating variants use different updates. The new record specializes the open question to unweighted cycles to fix the model completely. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Lazarsfeld, Piliouras, Sim and Wibisono — Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play ↗problem statement · source checked 2026-11-19

    HTML Definition 3, quadratic FTRL recurrence, Theorem 17, Sections 5.2–6 and Theorem 24 checked. Large fixed steps have square-root regret; arbitrary fixed steps remain explicitly open. The selected benchmark is unweighted cycles, and the update is cumulative-payoff projection rather than a generic primal projected-gradient step.

  2. Bailey and Piliouras — Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes ↗partial theory · source checked 2026-11-19

    The two-strategy, interior-equilibrium baseline is described in Lazarsfeld et al.'s introduction. Its full proof was not audited here; it does not establish arbitrary-step square-root regret for the higher-dimensional simplex-cycle benchmark.