Research map / Probabilistic and scientific modeling / Dynamical systems
Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how observer uncertainty (covariance of cumulative strategies and payoffs) grows under random initialization in FTRL zero-sum game dynamics across continuous, Euler, and symplectic discretizations, and proves a Heisenberg-type inequality for general regularizers.
Problem
Prediction accuracy of deterministic learning dynamics (FTRL) in two-player zero-sum games under random initialization; existing differential entropy measure fails to capture alternating updates.
Approach
Uses covariance of canonical Hamiltonian coordinates (cumulative strategy, cumulative payoff) as the uncertainty measure, shows differential entropy is constant under symplectic (alternating) updates, derives covariance growth rates per discretization, and establishes a Heisenberg-type uncertainty inequality via Gromov width / non-squeezing.
Key results
- Euler discretization (GDA/MWU) gives exponential covariance growth Theta((1+gamma eta^2)^{2t}), while symplectic discretization (AltGDA/AltMWU) gives Theta(t^2) growth for cumulative strategy when AA^T is singular and bounded covariance otherwise.
- Differential entropy is shown to remain constant under symplectic (alternating) updates for any step size, while it grows linearly under MWU.
- A Heisenberg-type inequality Delta X * Delta y >= w_L(P(t0))/(sqrt(2) pi) is established for FTRL with general regularizers under small initial deviations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Euler discretization instead of continuous-time or Symplectic FTRL | Euclidean-regularized FTRL · Zero-sum games with random initialization | Covariance of cumulative strategy and payoff: 𝒪(1) or Θ(t^2) -> Θ ((1+γ η^2)^{2t}) | Hurt |
| Use Symplectic discretization rather than Euler discretization | Euclidean-regularized FTRL · Zero-sum games with random initialization | Prediction accuracy: Θ ((1+γ η^2)^{2t}) -> Θ(t^2) or 𝒪(1) | Helped |
| Use Symplectic discretization rather than Euler discretization | Euclidean-regularized FTRL when AAᵀ is singular · Zero-sum games with random initialization | Covariance of cumulative strategy: Θ ((1+γ η^2)^{2t}) -> Θ(t^2) | Helped |
| Use alternating MWU instead of simultaneous MWU | FTRL with entropy regularizers · Zero-sum games | Differential entropy: S(X_i^t,y_i^t) ≥ S(X_i^{t_0},y_i^{t_0}) + c t; S(X_i^t,y_i^t) = S(X_i^{t_0},y_i^{t_0}) | Mixed |
| Use covariance rather than differential entropy to track uncertainty in alternating updates | FTRL learning dynamics · Alternating updates | Ability to capture uncertainty evolution | Helped |
| Use general regularizers under the stated smoothness and small-initial-uncertainty assumptions | Continuous-time FTRL · General FTRL dynamics | Product of standard deviations of cumulative strategy and payoff: ≥\frac{1}{\sqrt{2}}\frac{w_L (P(t_0))}{\pi } | Helped |
Surprising findings
- Differential entropy stays constant under alternating updates, so it fails to capture their uncertainty growth.
- Covariance of cumulative strategies grows quadratically in the singular case even though the continuous-time system is deterministic.
Limitations
- Covariance analysis relies on linear Hamiltonian structure, so it applies to Euclidean regularizers; extension to entropy regularizers is nontrivial.
- Symplectic discretization requires equal step sizes for both players.
- Experiments are limited to small games (2x2 and 3x3) with numerical illustration only.
Experimental setup
Metrics: variance of cumulative strategy variance of cumulative payoff differential entropy
Baselines: GDA AltGDA MWU AltMWU
Builds on: Follow-the-Regularized-Leader Hamiltonian formulation of game dynamics differential entropy predictability of MWU non-squeezing theorem
Closest papers by meaning
- On the Rate of Convergence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Beyond (NeurIPS 2021 · similarity 0.88)
- The Evolution of Uncertainty of Learning in Games (ICLR 2022 · similarity 0.88)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.87)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.87)
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.86)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.