Research map / Learning theory and algorithms / Submodular and game algorithms

The impact of uncertainty on regularized learning in games

ICML 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Opponent modeling and subgame solving · 0 citations (OpenAlex)

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 a stochastic (SDE) perturbation of follow-the-regularized-leader dynamics and proves that uncertainty drives players toward pure strategies, with limits restricted to pure Nash equilibria and drift to the boundary in harmonic games.

Problem

How random shocks in payoff observations and strategy updates affect regularized learning (FTRL) in games, and which outcomes remain stable or attracting under such uncertainty.

Approach

Model FTRL under uncertainty as a stochastic differential equation with a martingale noise term in score space; show that in any game every player reaches a neighborhood of a pure strategy in finite time, the only possible limits are pure Nash equilibria, and stable attractors are exactly spans of closed sets of pure strategies ("uncertainty favors extremes").

Key results

• In any finite game, every player's strategy reaches a 1-threshold neighborhood of a pure strategy in finite time, with expected hitting time bounded by roughly e^λ/λ.
• Stochastically asymptotically stable sets are exactly spans of closed sets of pure strategies; a state is stable iff it is a strict Nash equilibrium.
• In harmonic games (e.g., zero-sum with fully mixed equilibrium), the expected energy diverges to infinity, so the stochastic dynamics drift toward the boundary, unlike the deterministic recurrent case.

Measured effects reported in the paper

Surprising findings

• In Matching Pennies the deterministic dynamics cycle away from the boundary, but under any noise the trajectories are driven to the boundary, reversing the noiseless picture.
• Under the stochastic FTRL dynamics, the limit set of play must be a pure Nash equilibrium, so convergence to non-pure profiles is impossible even when half of deterministic initializations converge to them.

Limitations

• Analysis restricted to finite games and continuous-time dynamics with vanishing or fixed step; discrete-time analysis deferred.
• Some results require bounded kernels or a kernel growth condition, excluding the log-barrier kernel for some statements.
• Some stability results are not established for all stochastic models; the conjecture that stable limit sets lie entirely on the boundary remains open.

Experimental setup

Baselines: stochastic replicator dynamics of exponential weights stochastic replicator dynamics with aggregate shocks stochastic replicator dynamics of pairwise imitation

Builds on: follow-the-regularized-leader replicator dynamics exponential weights closedness under better replies

Closest papers by meaning

• Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.92)
• Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.92)
• No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.91)
• Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.89)
• No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.89)
• Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.89)