Independent Policy Gradient Methods for Competitive Reinforcement Learning

Constantinos Daskalakis; Dylan J. Foster; Noah Golowich

Source-linked AI summary

Independent Policy Gradient Methods for Competitive Reinforcement Learning

Constantinos Daskalakis, Dylan J. Foster, Noah Golowich

arXiv:2101.04233v1Jan 11, 2021cs.LG

TL;DR

Independent policy-gradient learning lacks global finite-sample convergence guarantees in competitive reinforcement learning when agents observe only local trajectory information. This paper analyzes two-player zero-sum stochastic games and shows that two-timescale policy-gradient updates converge to Nash equilibrium under the stated parameterization and learning-rate conditions.

Problem
Independent reinforcement learning can fail to converge because agents’ policy updates induce distribution shift, leaving global guarantees comparatively elusive.
Method
The paper analyzes independent policy-gradient updates in two-player zero-sum stochastic games under a two-sided gradient-dominance condition and an ε-greedy direct parameterization.
Results
Two-timescale policy-gradient updates converge to a Nash equilibrium, with learning rates ηx ≍ ϵ^10.5 and ηy ≍ ϵ^6 and exploration parameters εx ≍ ϵ and εy ≍ ϵ^2.
Takeaways & Limitations
The results provide global non-asymptotic convergence guarantees for independent policy-gradient methods in competitive reinforcement learning.
Takeaways & Limitations
The paper does not optimize the dependence on ϵ^-1 or other parameters, which can almost certainly be improved.

Abstract

from arXiv · show

We obtain global, non-asymptotic convergence guarantees for independent learning algorithms in competitive reinforcement learning settings with two agents (i.e., zero-sum stochastic games). We consider an episodic setting where in each episode, each player independently selects a policy and observes only their own actions and rewards, along with the state. We show that if both players run policy gradient methods in tandem, their policies will converge to a min-max equilibrium of the game, as long as their learning rates follow a two-timescale rule (which is necessary). To the best of our knowledge, this constitutes the first finite-sample convergence result for independent policy gradient methods in competitive RL; prior work has largely focused on centralized, coordinated procedures for equilibrium computation.

1 Introduction

The introduction motivates independent multi-agent reinforcement learning and frames the paper’s convergence analysis for policy-gradient methods in two-player zero-sum stochastic games. It presents two-timescale convergence to Nash equilibrium and a broader nonconvex minimax result as the main contributions.

Motivation: Multi-agent reinforcement learning must account for other agents whose actions affect both the environment state and rewards.
Independent learning: Independent algorithms use local observations and treat the environment as fixed, making them more versatile in uncertain multi-agent settings.
Theoretical gap: Independent reinforcement learning lacks the theoretical guarantees developed for centralized methods and can fail to converge because policy updates induce distribution shift.
Paper focus: The paper analyzes independent policy gradient methods in two-player zero-sum stochastic games, where agents observe their own actions and rewards but not the opponent’s action.
Contributions: Two-timescale policy gradient updates converge to a Nash equilibrium, while a general theorem extends convergence guarantees to nonconvex minimax problems with two-sided gradient dominance.

2 Preliminaries

The preliminaries define finite two-player zero-sum stochastic games as episodic Markov interactions with simultaneous actions, rewards, transitions, and eventual stopping. They also introduce trajectory values, minimax equilibria, visitation distributions, and the paper’s notation and assumptions.

Game model: A two-player zero-sum stochastic game contains finite state and action spaces, transition probabilities, rewards, a stopping rule, and an initial state distribution.
Game dynamics: At each step, both players observe the state, act simultaneously, receive the resulting reward, transition according to P, and eventually stop with probability one.
Policies and values: Randomized policies induce trajectory distributions, and V_s(π1,π2) is the expected reward from initial state s under those policies.
Equilibrium objective: Shapley’s minimax theorem guarantees a Nash equilibrium, motivating algorithms that seek ε-approximate equilibria through the min-max value.
Notation and assumptions: The framework uses discounted state-visitation distributions and assumes deterministic rewards for simplicity, with immediate extension to stochastic rewards.

3 Independent Learning

The independent-learning protocol lets each player repeatedly execute separately chosen policies and update from only their own trajectories. The section specifies policy-gradient updates, an ε-greedy parameterization, formal independence constraints, and the convergence challenge motivating the analysis.

Independent protocol: In each episode, players independently propose policies, execute them, and observe only their own state-action-reward trajectories, not the opponent’s actions.
Formal constraints: The formal protocol restricts players to independent game access and limited private storage, although two-timescale updates require minimal prior coordination over which player is faster.
Policy-gradient updates: Each player treats the game value as a continuous optimization objective and uses trajectories to construct stochastic policy gradients for iterative updates.
Convergence question: The central question is when independent policy-gradient updates in a zero-sum stochastic game converge to a Nash equilibrium.
Parameterization: The analyzed policies use ε-greedy direct parameterization, mixing each state-action distribution with uniform exploration controlled by εx and εy.
Challenges: Independent learning can cycle even in simple stochastic games and matrix games, while no global convergence result was known for general finite state/action zero-sum stochastic games.

4 Main Result

The paper proves that independent policy-gradient learners in two-player zero-sum stochastic games converge globally to approximate Nash equilibria under coordinated two-timescale learning rates. The analysis uses ε-greedy exploration, a minimax mismatch coefficient, and a two-sided gradient-dominance framework.

Main result: Independent policy-gradient updates converge to a Nash equilibrium when the players’ learning rates follow a two-timescale rule.The min-player uses a much smaller stepsize than the max-player, avoiding limit-cycle behavior associated with equal-rate updates.
Main result: ηx ≍ ϵ^10.5 and ηy ≍ ϵ^6, with εx ≍ ϵ and εy ≍ ϵ^2, guarantee convergence under the stated parameterization.The guarantee applies to direct parameterization with ε-greedy exploration.
Main result: N ≤ poly(ϵ^-1, C_G, S, A, B, ζ^-1) episodes suffice for the convergence guarantee.The result is finite-sample and global, although the dependence on ϵ^-1 and other parameters is not optimized.
Main result: The protocol is independent because each learner uses only its own trajectories and stores a single parameter vector, but the learning rates must be coordinated in advance.The required coordination is a caveat arising from the different timescales.
Main result: The min-player’s iterates have expected error below ϵ when an iterate is selected uniformly at random from the sequence.The guarantee is asymmetric because the faster max-player approximates a best response to the slower min-player.
Proof strategy: The proof establishes two-sided gradient dominance for stochastic games and develops a two-timescale convergence theorem for nonconvex minimax problems satisfying that condition.The analysis controls the faster player’s approximation to a best response while minimizing the Moreau-envelope gradient for the slower player.

5 Discussion

The discussion examines why last-iterate convergence remains open for independent policy-gradient methods, despite encouraging extragradient experiments. It also situates the contribution as a first step toward a broader theory of independent competitive reinforcement learning.

5.1 Toward Last-Iterate Convergence for Stochastic Games: Last-iterate convergence for independent policy-gradient updates remains an open problem, even for simple ratio games with exact gradients.The paper explicitly leaves open whether constant-learning-rate extragradient converges in the last iterate.
5.1 Toward Last-Iterate Convergence for Stochastic Games: The paper argues that formally proving last-iterate convergence for extragradient or related methods likely requires new analytical tools.This limitation motivates an explicit open problem about constant-learning-rate extragradient.
5.1 Toward Last-Iterate Convergence for Stochastic Games: Figure 1 contrasts the sign of ⟨F(z),z −z∗⟩ across parameter regions with extragradient’s primal-dual and primal-gap convergence curves.The plots use learning rate 0.01 and initialize at z0 = (1,0,1,0), inside each game’s region where MVI does not hold.
5.1 Toward Last-Iterate Convergence for Stochastic Games: Extragradient converges experimentally in ratio games despite MVI failure, but one example shows slower convergence with oscillations.The first game satisfies MVI locally, whereas the randomly generated game fails MVI even locally.
5.2 Related Work: Prior independent-learning results include asymptotic guarantees, restricted stochastic-game structures, or non-independent inner-loop and best-response procedures.Reducing general stochastic games to extensive-form games can also cause exponential blowup with respect to horizon.
5.3 Future Directions: The paper presents the first independent policy-gradient algorithms for competitive reinforcement learning in zero-sum stochastic games and identifies extensions beyond two-player zero-sum settings.Future directions include games with more than two players, cooperative interactions, and weaker solution concepts.

A.2 Full Version of Theorem 1 and Proof

The theorem’s proof applies a general two-timescale convergence result to independent policy-gradient updates. It verifies gradient-domination, Lipschitz, parametrization, and variance conditions before selecting learning-rate and episode parameters for a target accuracy.

Theorem 1a: Theorem 1a guarantees convergence when both players follow the independent policy-gradient scheme with an appropriate parametrization and learning rates.The supplied theorem statement is fragmented, so the exact convergence target and full rate are not reproduced here.
Proof of Theorem 1a: The proof reduces Theorem 1a to Theorem 2a after bounding the relevant domain quantities and establishing the required smoothness and variance properties.The proof explicitly describes the result as an immediate consequence of Theorem 2a.
Proof of Theorem 1a: Lemma 1a verifies the gradient-domination conditions with parameters involving ζ and C_G, together with additive approximation terms.The extracted statement gives µ_y = µ_x = ζ/C_G and refers to ε_x and ε_y.
Proof of Theorem 1a: The desired accuracy is obtained by choosing parameters according to the theorem’s accuracy-dependent rate conditions.The supplied passages state that the choices follow from equations (15), (16), and (17), but do not preserve the complete formulas.
Proof of Theorem 1a: The proof uses ε-greedy parametrizations to approximate arbitrary policies while retaining Lipschitz control of the value function.It invokes policy approximation and Proposition 3’s L-Lipschitz property for ε-greedy parametrizations.

A.3 Proofs for Additional Results

This section develops the stochastic-game construction, policy-gradient estimators, and supporting lemmas used to analyze independent learning. It also establishes structural properties of visitation distributions, smoothness, and unbiased gradient estimation.

Game construction: The game’s value depends only on the players’ policies at state 1, while certain action choices make state 3 reachable under arbitrary policies.Best-response policies instead avoid state 3, yielding zero visitation probability there.
Gradient estimation: The REINFORCE estimator is shown to be unbiased for the policy gradients of the game value.The calculation uses trajectory probabilities and total rewards under the players’ policies; the result holds symmetrically for both players.
Supporting lemmas: The supporting analysis bounds gradient-estimator variance using state visitation distributions and establishes Lipschitz-gradient properties for the direct parameterization.The visitation distribution is related to the unnormalized occupancy measure through the stopping probability ζ.
Supporting lemmas: Performance-difference and smoothness lemmas connect policy changes, gradient estimates, and the optimization properties required by the convergence analysis.The arguments apply symmetrically to the two players and use compactness of the policy space where needed.

B.1 Algorithm and Main Theorem

This section formulates two-timescale stochastic gradient descent-ascent and states its convergence guarantee under smoothness, Lipschitzness, compactness, and gradient-domination assumptions. The resulting parameter choices provide an explicit iteration bound for reaching an approximate solution.

Algorithm: The analysis studies a continuously differentiable function f accessed only through a stochastic first-order oracle.The algorithm is a two-timescale version of simultaneous gradient descent-ascent.
Problem formulation: The max and min functions are defined through best responses over compact policy domains X and Y.The associated best-response mappings y⋆(x) and x⋆(y) specify the players’ optimization directions.
Assumptions: The assumptions require f to be ℓ-smooth and L-Lipschitz, with gradient-domination conditions for both players.The direct policy parameterization may have empty interior, so differentiability is assumed on a surrounding neighborhood.
Main theorem: If ηx is sufficiently small relative to ηy, two-timescale SGDA drives the iterates toward an optimal point on average under the theorem’s assumptions.The guarantee is stated for any ϵ ∈ (0,1) over a sufficiently large number of iterations.
Main theorem: ηy ≍ ϵ4 and ηx ≍ ϵ8 yield an ϵ-suboptimal point within T ≍ ϵ−10 iterations when the remaining parameters are treated as constants.This interpretation assumes εx = εy = 0 and constant problem and oracle parameters.

B.2 Technical Preliminaries for Proof

This section introduces nonsmooth optimization tools and descent arguments for analyzing two-timescale SGDA. Moreau envelopes, proximal mappings, and potential functions connect approximate stationarity with value suboptimality and best-response tracking.

Nonsmooth minimization: The max function Φ(x) = maxy∈Y f(x,y) is treated as a potentially nonsmooth objective through weak-convexity tools.Danskin’s theorem characterizes its subgradients using gradients of f at maximizing responses.
Nonsmooth minimization: The Moreau envelope and proximal map provide smoothed objectives and approximate stationarity measures for constrained weakly convex functions.A small Moreau-envelope gradient implies proximity to a point with a small subgradient.
Descent analysis: The descent analysis tracks the gap ∆t = Φ(xt) − f(xt,yt) alongside the Moreau-envelope potential for the maximizing player.The potential decreases when its gradient remains large, up to an error controlled by the x-player’s learning rate.
Descent analysis: Two-timescale SGDA inherits descent inequalities that combine smoothness, proximal mappings, and stochastic-gradient properties.The y-player’s best-response tracking is analyzed through a negated Moreau envelope and its iteration-to-iteration changes.
Descent analysis: The technical lemmas bound the accumulated Moreau-envelope gradient and relate it to the objective gap through Lipschitzness and gradient domination.These bounds supply the ingredients used later to convert stationarity into approximate minimization.

B.3 Proof of Theorem 2a

The proof of Theorem 2a combines descent bounds for the x-player, tracking bounds for the y-player, and a stationarity-to-suboptimality conversion. The resulting argument establishes convergence of two-timescale SGDA under the stated regularity assumptions.

Proof strategy: The proof combines the x-player descent guarantee with the y-player’s Moreau-envelope tracking bound.The resulting inequalities control both the best-response gap and the change in the smoothed max objective.
Proof strategy: The Moreau-envelope analysis bounds cumulative stationarity through the potential change, smoothness, and the learning-rate-dependent error terms.The argument uses λ = 1/(2ℓ) when rearranging the final bound.
Stationarity conversion: For constrained domains, normal and tangent cone arguments support the conversion from proximal optimality conditions to bounds on subgradients.The normal cone is contained in the polar of the tangent cone.
Stationarity conversion: Gradient domination and Lipschitzness relate a small Moreau-envelope gradient to approximate minimization of the max function.The relevant bound includes the domination parameters, Lipschitz constant, smoothing parameter, and additive error.
Boundary cases: The proof extends the argument from differentiable points to nondifferentiable boundary points using continuity, dense interiors, and neighborhood enlargement.This handles domains whose interior is not dense or may be empty.

C Proofs from Section 5.1

The proofs establish equilibrium characterizations and analyze a ratio game with a unique global Nash equilibrium, while exhibiting failure of the MVI property away from equilibrium.

Proof of Proposition 2: The ratio game has a unique global Nash equilibrium at x⋆ = y⋆ = (0,1), with game value V(x⋆,y⋆) = 0.The minimum of Φ and maximum of Ψ occur at the same pure strategy profile.
Proof of Proposition 2: There exists a point z for which ⟨F(z),z − z∗⟩ < 0.5, demonstrating failure of the stated MVI property despite the unique equilibrium.The proposition also records ζ ≥ s for this ratio game.
Proof of equilibrium characterization: The proof derives a contradiction by constructing z such that ⟨z − ẑ,F(z)⟩ < 0, violating condition (47) whenever ẑ is not a Nash equilibrium.It starts from a profitable unilateral deviation and uses continuity along a segment between policies.
Proof of equilibrium characterization: First-order optimality conditions show that x⋆ minimizes V(·,y⋆) and y⋆ maximizes V(x⋆,·), yielding global optimality and Nash equilibrium.The proof checks global, not merely local, optimality for both players.

C.1 Experimental Details

The experiments instantiate two games: one from Proposition 2 and one rounded from a randomly discovered game, with specified payoff matrices for each pair of figures.

Figure 1(a) and Figure 1(b): Figures 1(a) and 1(b) use the Proposition 2 game with ϵ = 0.1 and s = 0.3.Its payoff matrices are R = (−1.0, 0.1, −0.1, 0.0) and S = (0.3, 0.3, 1.0, 1.0).
Figure 1(c) and Figure 1(d): Figures 1(c) and 1(d) use a rounded version of a game found via random search.Its payoff matrices are R = (−0.6, −0.3, 0.6, −0.3) and S = (0.9, 0.5, 0.8, 0.4).