Research map / Bandits and online learning / Online convex optimization and games
Learning from Delayed Feedback in Games via Extra Prediction
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.
Shows that time-delayed reward feedback breaks optimistic FTRL in learning in games, and proposes weighted OFTRL (optimism weight n = m+1) that restores constant social regret in normal-form games and last-iterate convergence in poly-matrix zero-sum games.
Problem
Learning in games with time-delayed observation of past rewards: optimistic FTRL loses its fast-convergence (constant social regret) and last-iterate convergence properties under even a single-step delay.
Approach
Weight the optimistic prediction term in OFTRL by n times (WOFTRL, m_i^t = n u_i^{t-m}); a Taylor-expansion argument shows the optimism weight n cancels the delay m, so n > m (concretely n = m+1) recovers the RVU property and convergence.
Key results
- Under a single-step-or-larger delay, OFTRL (n=1) has social regret Omega(sqrt(T)) and its distance to Nash equilibrium diverges in Matching Pennies.
- WOFTRL with n=m+1 satisfies the RVU property and yields social regret RegTot(T)=O(m^2) in general-sum normal-form games with learning rate eta=1/(2 lambda L), lambda=(m+1)(m+2)/2.
- WOFTRL with n=m+1 and eta <= 1/(sqrt(8) n^2 L) achieves last-iterate convergence to Nash equilibrium in poly-matrix zero-sum games (theory); experiments show convergence for n>m and non-convergence for n<=m in weighted Rock-Paper-Scissors (m=4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add a one-step feedback delay to OFTRL (n=1) | OFTRL on Matching Pennies · Matching Pennies, unconstrained Euclidean | social regret: constant social regret -> Ω(√T) | Hurt |
| Add a one-step feedback delay to OFTRL (n=1) | OFTRL on Matching Pennies · Matching Pennies, unconstrained Euclidean | distance to Nash equilibrium: convergence -> lim_{T→∞}Dis(T)→∞ | Hurt |
| Weight optimism n=m+1 and use η=1/(2λL) | WOFTRL · General-sum normal-form games | social regret: O(m²) | Helped |
| Weight optimism n=m+1 and use η≤1/(√8 n²L) | WOFTRL · Poly-matrix zero-sum games | last-iterate convergence: lim_{T→∞}||x^T−x*||₂=0 | Helped |
| Set optimism weight n>m rather than n≤m (ablation) | WOFTRL · Matching Pennies, m=10 | social regret: O(√T) -> O(1) | Helped |
| Set optimism weight n>m rather than n≤m (ablation) | WOFTRL · Sato's game | social regret: O(√T) -> constant social regret | Helped |
| Use η=1/√T instead of constant η (ablation) | WOFTRL, m=10, n=11 · Matching Pennies | social regret: O(1) -> O(√T) | Hurt |
| Set optimism weight n>m rather than n≤m (ablation) | WOFTRL · Weighted Rock-Paper-Scissors, m=4 | last-iterate convergence: Non-convergence -> last-iterate convergence | Helped |
| Increase optimism weight from n=5 to n=6 (ablation) | WOFTRL, m=4 · Weighted Rock-Paper-Scissors | convergence speed | Helped |
| Increase optimism weight from n=4 to n=3 (ablation) | WOFTRL, m=4 · Weighted Rock-Paper-Scissors | divergence speed | Hurt |
| Use a large delay with optimism only slightly above it (e.g., m=30, n=35) at finite η (ablation) | WOFTRL · Matching Pennies | social regret: O(1) -> O(√T) | Hurt |
Surprising findings
- Even a single-step delay makes OFTRL's social regret Omega(sqrt(T)) and causes divergence from Nash equilibrium in Matching Pennies, as opposed to constant regret without delay.
- Large delay with a finite learning rate can still yield O(sqrt(T)) regret even when n>m (e.g., m=30, n=35).
Limitations
- Analysis assumes a constant known delay m; stochastic or adversarial delays are not analyzed.
- Regret bound scales as O(m^2) and the learning rate must shrink by lambda=(m+1)(m+2)/2, degrading performance for large delays.
- Convergence rate of WOFTRL is not established.
Experimental setup
Benchmarks: Matching Pennies Sato's game weighted Rock-Paper-Scissors
Metrics: social regret distance from Nash equilibrium
Baselines: Vanilla FTRL OFTRL
Builds on: Optimistic FTRL RVU property Mirror Descent Follow the Regularized Leader
Closest papers by meaning
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.90)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.89)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.89)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.89)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.89)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.89)
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.