Source-linked AI summary
Fast Convergence of Regularized Learning in Games
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, Robert E. Schapire
TL;DR
The paper studies faster convergence in arbitrary multiplayer normal-form games, extending results previously limited to two-player zero-sum settings. It develops regularized no-regret dynamics with recency bias and reports O(1/T) convergence of average welfare to approximately optimal welfare, alongside decentralized coarse correlated equilibrium computation and robustness to adversarial opponents.
Problem
Prior analyses were limited to two-player zero-sum games, leaving practically important multiplayer non-zero-sum settings such as auctions and routing games uncovered.
Method
The paper generalizes these techniques to arbitrary multiplayer normal-form games using regularized no-regret algorithms with recency bias, together with a black-box reduction for robustness.
Results
Average welfare converges to approximately optimal welfare at O(1/T), and the results entail decentralized computation of coarse correlated equilibria with significantly faster convergence than existing methods.
Takeaways & Limitations
The results provide rapidly convergent decentralized dynamics for correlated-equilibrium computation and for understanding agent behavior in complex multiplayer games.
Takeaways & Limitations
The fast rates do not apply to vanilla Hedge without modification, and the necessity of the modification remains an open question.
Abstract
from arXiv · showhide
We show that natural classes of regularized learning algorithms with a form of recency bias achieve faster convergence rates to approximate efficiency and to coarse correlated equilibria in multiplayer normal form games. When each player in a game uses an algorithm from our class, their individual regret decays at $O(T^{-3/4})$, while the sum of utilities converges to an approximate optimum at $O(T^{-1})$--an improvement upon the worst case $O(T^{-1/2})$ rates. We show a black-box reduction for any algorithm in the class to achieve $\tilde{O}(T^{-1/2})$ rates against an adversary, while maintaining the faster rates against algorithms in the class. Our results extend those of [Rakhlin and Shridharan 2013] and [Daskalakis et al. 2014], who only analyzed two-player zero-sum games for specific algorithms.
1 Introduction
The paper generalizes fast-converging decentralized no-regret dynamics from two-player zero-sum games to arbitrary multiplayer normal-form games. Regularized algorithms with recency bias achieve faster welfare and regret rates, while a black-box reduction preserves worst-case robustness.
- Arbitrary multi-player normal-form games replace the two-player zero-sum setting addressed by earlier fast-convergence results.
- O(1/T) welfare convergence improves on the previously known O(1/T) rate for average welfare in the stated contribution.
- Stability and recency bias are identified as key structural ingredients, covering Optimistic Mirror Descent and optimistic FTRL variants with weighted history windows.
- The paper simulates a 4-bidder simultaneous auction and compares optimistic algorithms with Hedge on utilities, regrets, and equilibrium convergence.
2 Repeated Game Model and Dynamics
The model studies repeated finite multiplayer games in which players independently choose mixed strategies and receive counterfactual utility feedback. Smoothness connects individual regret to approximate welfare, yielding faster welfare convergence for suitable no-regret algorithms.
- Repeated Game Model and Dynamics: Each player chooses a mixed strategy over a finite strategy space at every round and observes expected utilities for every possible pure strategy.
- Repeated Game Model and Dynamics: Vanishing regret means that each player’s cumulative regret relative to the best fixed strategy is sublinear in T.
- Approximate Efficiency of No-Regret Dynamics: Social welfare is the sum of player utilities, and OPT is the maximum welfare achievable by a centrally chosen strategy profile.
- Approximate Efficiency of No-Regret Dynamics: In a (λ, µ)-smooth game, regret bounds imply welfare at least (λ/(1 + µ))OPT minus an O(1/T)-scaled error term.
- Approximate Efficiency of No-Regret Dynamics: The price of anarchy is ρ = (1 + µ)/λ, and convergence toward it is governed by the regret quantity in the smoothness bound.
- Approximate Efficiency of No-Regret Dynamics: For suitable no-regret algorithms, average welfare converges at O(n^2 log(d)/T), faster than the O(n log(d)/T) rate obtained from standard regret bounds.
3 Fast Convergence to Approximate Efficiency
The paper characterizes regularized no-regret dynamics with the RVU property and recency bias, showing faster convergence of social welfare and individual utilities in smooth multiplayer games.
- RVU framework: The RVU property bounds regret using variation in utilities and negative variation terms, providing the central condition for faster convergence.Vanilla Mirror Descent and FTRL do not satisfy this property, but optimistic variants do.
- Social welfare: Theorem 4 bounds total regret when players satisfy RVU with β ≤ γ/(n −1)^2 under the ℓ1 norm, yielding convergence of social welfare.The proof sums the players’ RVU bounds and drops the second terms because they are dominated by the negative third terms.
- Social welfare: The framework allows different algorithms for different players, provided their RVU constants share a common bound.This generalizes earlier analyses that required all players to use the same algorithm.
- Algorithmic instantiations: Optimistic Mirror Descent satisfies RVU with α = R/η, β = η, and γ = 1/(8η), extending its fast-rate guarantee from two-player zero-sum games to general games.Its update uses an adaptive predictor sequence and a strongly convex regularizer.
- Algorithmic instantiations: Optimistic FTRL provides one-step, H-step, and geometrically discounted recency-bias variants, with RVU constants that depend on η, H, and the discount factor δ.For H-step recency bias, setting η = 1/(2H(n −1)) yields an analogue with an extra factor of H.
- Individual utilities and CCE: Combining RVU with stability yields fast convergence of individual utilities and of players’ strategies to the game’s coarse correlated equilibria.The same conclusion extends to the other recency-bias forms and to OMD.
4 Robustness to Adversarial Opponent
The paper wraps RVU algorithms in a black-box, epoch-based reduction that preserves fast convergence in favorable games while recovering worst-case regret guarantees against arbitrary opponents.
- Motivation: The black-box reduction addresses whether fast favorable-case convergence sacrifices guarantees when opponents do not satisfy the RVU property.It modifies any parametric RVU algorithm rather than relying on an algorithm-specific construction.
- Construction: The wrapper A′ uses an epoch-based doubling schedule to adapt the algorithm’s parameter according to an upper bound on observed variation.At each epoch it starts a new run of the underlying algorithm with an updated parameter.
- Guarantees: Theorem 14 guarantees that A′ achieves the minimum of its favorable-case and worst-case regret bounds while retaining the RVU property.This makes the reduction applicable to the social-welfare convergence theorem.
- Individual guarantees: The reduction also supports robust convergence results for individual utilities when the transformed algorithm is played against itself or against arbitrary opponents.OFTRL satisfies the required conditions, implying robust convergence.
5 Experimental Evaluation
The experiments compare Hedge with Optimistic Hedge in repeated auction games, finding faster regret convergence and more stable dynamics under Optimistic Hedge, while average welfare remains similar.
- Algorithms: Optimistic Hedge modifies Hedge by double-counting the last iteration’s utility for each strategy.The modification is implemented through optimistic follow the regularized leader with the entropy regularizer.
- Regret: In a repeated auction with 4 bidders, 4 items, valuation 20, and bids in, Optimistic Hedge produces lower maximum individual and summed regret than Hedge.Both methods use η = 0.1.
- Dynamics: Figure 2 tracks one player’s expected bid and per-iteration utility for one of four items under Hedge and Optimistic Hedge.Hedge is shown in blue and Optimistic Hedge in red.
- Robustness: Similar behavior appears when players value randomly selected player-specific subsets of items or use other step sizes.
- Dynamics: Optimistic Hedge yields more stable expected bids, whereas Hedge exhibits sawtooth behavior in the auction dynamics.The paper identifies this stability as an intuitive reason for Optimistic Hedge’s faster regret convergence.
- Welfare: The methods show no significant difference in average welfare because welfare depends on regret against smooth-game benchmark strategies, which is experimentally comparable for both algorithms.The paper reports faster Hedge efficiency convergence in some cost-minimization games, but with a worse POA.
6 Discussion
The discussion highlights broad implications of the RVU-based results while identifying open questions about vanilla Hedge, strategy stability, and partial information.
- Implications: The results show no-regret algorithms that converge rapidly against one another while remaining robust to adversarial opponents.The discussion connects this combination to correlated-equilibrium computation and understanding multi-player games.
- Open questions: The paper’s fast rates do not apply to unmodified Hedge.The discussion asks whether the RVU modification is merely sufficient or also necessary, and mentions a sketch suggesting a counterexample.
- Open questions: Optimistic FTRL often produces more stable empirical trajectories toward equilibrium than Hedge, but this behavior lacks a precise quantification.
- Open questions: The paper leaves open whether faster rates remain possible when players observe only other players’ moves rather than the expected utility function.
Supplementary material for “Fast Convergence of Regularized Learning in Games”
The proposition links individual regret in smooth games to social welfare, using the price of total anarchy to express the resulting efficiency guarantee.
- Proposition: In a (λ, µ)-smooth game, Proposition 2 assumes each player i has regret at most r_i(T).
- Proposition: The welfare guarantee has the form W(w_t) ≥ λ/(1 + µ)OPT minus a term that decreases with T.The displayed bound is the proposition’s smoothness-based efficiency statement.
- Interpretation: The factor ρ = (1 + µ)/λ is called the price of total anarchy.
- Proof: The proof obtains the welfare bound by applying each player’s regret inequality, summing over players, using smoothness, and rearranging.
B Proof of Proposition 5
This proof establishes RVU bounds for optimistic mirror descent by invoking an earlier regret theorem and presenting the needed regret formulation explicitly.
- RVU parameters: Optimistic mirror descent satisfies RVU with α = R/η, β = η, and γ = 1/(8η), where R is defined through the regularizer’s divergence.
- Proof strategy: The argument uses Theorem 17 of Rakhlin and Sridharan as a foundational regret result.
- Proof strategy: The authors instantiate optimistic mirror descent with M_t^i to verify the sufficient RVU condition established earlier.
- Main theorem: Theorem 18 states a regret bound for optimistic mirror descent with respect to any comparator w∗.
- Proof steps: The proof proceeds by instantiating Theorem 17 and applying successive bounds before summing over timesteps and rescaling the resulting inequality.
C Proof of Proposition 7
The proof establishes RVU constants for the algorithm and transfers optimistic mirror descent regret bounds to optimistic FTRL. It uses strong convexity, optimality conditions, and auxiliary leader-sequence notation.
- α = R/η, β = η and γ = 1/(4η) are the RVU constants established for the algorithm.
- The proof introduces be-the-leader variables analytically even though the algorithms do not use a secondary sequence.These variables represent a one-step-ahead sequence in the analysis.
- Theorem 19 bounds optimistic FTRL regret against any comparator w∗, with the proof relying on induction and strong convexity.The displayed bound is not recoverable from the supplied passage fragment.
- Optimistic FTRL achieves the same regret form as optimistic mirror descent, with equivalent theorem and corollary guarantees.The text also states that slightly stronger optimistic FTRL bounds can be obtained from additional lemmas.
- Lemma 20 supplies stability inequalities for optimistic FTRL by combining optimality conditions with strong convexity.
D Proof of Proposition 9
The proof derives Proposition 9 by combining optimistic FTRL regret bounds with stability and summing across adaptive rounds. Algorithm A′ is analyzed through two alternative bounds, yielding the minimum stated in Theorem 14.
- The analysis combines Theorem 19, Lemma 20, and Inequality (10) to derive the proposition’s regret bound.
- For discounted optimistic FTRL with δ ∈ (0, 1), the RVU constants include β = η/(1 −δ)^3 and γ = 1/(8η).
- Theorem 14 states that Algorithm A′ achieves regret at most the minimum of two terms.
- The proof splits into two corresponding parts, each analyzing a round r through its final iteration and accumulated quantity I_r.
- At most log(T) rounds occur because the bound B_r doubles each round while P_T∗ ≤ T.
G Proof of Corollary 16
The proof shows that a black-box wrapper A′ preserves fast self-play regret while providing a more robust guarantee against arbitrary opponents. Its analysis uses the base algorithm’s parameter and regret properties.
- η∗ = T^-1/4 gives A′ regret ˜O(T^1/4) against itself and ˜O(T) against any opponent.
- Every round runs the base algorithm with η_r ≤ η∗, implying ∥w_t∥ ≤ κT^-1/4.
- When all players use A′, the proof invokes the fast-convergence reasoning from Theorem 4 to bound each player’s regret.
H Fast convergence via a first order regret bound for cost-minimization
This section extends fast-convergence analysis to first-order regret bounds for smooth cost-minimization games and to continuous strategy spaces. It derives welfare guarantees under smoothness and states assumptions and examples for continuous games.
- First-order regret and smooth games: For a (λ, µ)-smooth game, first-order no-regret bounds are used to derive a convergence guarantee for total cost.
- First-order regret and smooth games: The analysis applies a regret bound, Cauchy–Schwarz, and the smoothness assumption before solving a quadratic inequality.
- First-order regret and smooth games: The resulting total-cost bound is stated after substituting the derived bound into Eq. (22).
- First-order regret and smooth games: The price of total anarchy is larger than in the previous analysis by a multiplicative factor of 1 + 1/µ, while convergence is n times faster.
- Continuous strategy spaces: Continuous-game results assume convex player costs and L-Lipschitz gradients, with regularized learning driven by utility gradients.
- Continuous strategy spaces: A continuous strategy-space formulation contains discrete mixed-strategy games as a special case through the simplex representation.
- Continuous strategy spaces: Splittable congestion games provide an example with convex, increasing, twice-differentiable, K-Lipschitz latency functions and flow-splitting path strategies.
- Continuous strategy spaces: For splittable congestion games with an entropic regularizer, the path-count bound gives R ≤ B·m and total regret at most 2K(B + 1) ... .The supplied passage truncates the final expression.