Provable Self-Play Algorithms for Competitive Reinforcement Learning

Yu Bai; Chi Jin

Source-linked AI summary

Provable Self-Play Algorithms for Competitive Reinforcement Learning

Yu Bai, Chi Jin

arXiv:2002.04017v3Feb 10, 2020cs.LGcs.AIstat.ML

TL;DR

The paper addresses whether self-play can be provably sample-efficient in competitive reinforcement learning, where existing theory largely concerns fixed environments. It develops self-play algorithms for two-player zero-sum Markov games and establishes regret guarantees, including a polynomial-runtime explore-then-exploit variant, while identifying limitations in multi-step games and beyond tabular settings.

Problem
The paper asks whether self-play can be provably effective in competitive reinforcement learning, especially when exploration and exploitation must be managed.
Method
The paper develops VI-ULCB, which constructs upper and lower value-function bounds and iteratively solves subgames, plus an explore-then-exploit algorithm.
Results
The algorithms provide provably sample-efficient self-play for zero-sum Markov games, with improved computational efficiency from the explore-then-exploit variant and reduced state-action dependence in one-step games.
Takeaways & Limitations
Self-play can achieve low-regret learning against fully adversarial opponents in the studied zero-sum Markov-game setting without requiring an expert opponent.
Takeaways & Limitations
The analysis leaves a regret gap in multi-step games and currently applies only to tabular games, leaving function-approximation extensions open.

Abstract

from arXiv · show

Self-play, where the algorithm learns by playing against itself without requiring any direct supervision, has become the new weapon in modern Reinforcement Learning (RL) for achieving superhuman performance in practice. However, the majority of exisiting theory in reinforcement learning only applies to the setting where the agent plays against a fixed environment; it remains largely open whether self-play algorithms can be provably effective, especially when it is necessary to manage the exploration/exploitation tradeoff. We study self-play in competitive reinforcement learning under the setting of Markov games, a generalization of Markov decision processes to the two-player case. We introduce a self-play algorithm---Value Iteration with Upper/Lower Confidence Bound (VI-ULCB)---and show that it achieves regret $\tilde{\mathcal{O}}(\sqrt{T})$ after playing $T$ steps of the game, where the regret is measured by the agent's performance against a \emph{fully adversarial} opponent who can exploit the agent's strategy at \emph{any} step. We also introduce an explore-then-exploit style algorithm, which achieves a slightly worse regret of $\tilde{\mathcal{O}}(T^{2/3})$, but is guaranteed to run in polynomial time even in the worst case. To the best of our knowledge, our work presents the first line of provably sample-efficient self-play algorithms for competitive reinforcement learning.

1 Introduction

The paper studies provably effective self-play for competitive reinforcement learning in two-player zero-sum Markov games. It introduces sample-efficient algorithms with regret and runtime guarantees, while identifying unresolved dependence and multi-step limitations.

Motivation: Self-play has achieved superhuman performance empirically, motivating theoretical analysis without expert opponents.The cited motivation describes repeated play among current policies and policy updates from self-play trajectories.
Problem setting: The paper targets low-regret learning in two-player zero-sum Markov games under performance evaluation against episode-specific best responses.Markov games generalize MDPs to two players, and the regret notion allows the best response to vary across episodes.
Contributions: The paper introduces provably sample-efficient self-play algorithms for zero-sum Markov games without restrictive assumptions.This is presented as the paper’s main contribution.
Results: VI-ULCB achieves ˜O(H3S2ABT) regret in general games and ˜O(H3S2(A + B)T) regret with guaranteed polynomial runtime in turn-based games.Here H is game length, S the number of states, A and B the players’ action counts, and T the total number of steps.
Results: An explore-then-exploit algorithm has guaranteed polynomial runtime in general zero-sum Markov games with slightly worse ˜O(T 2/3) regret.The algorithm trades regret for computational efficiency in the general setting.
Open questions: The paper leaves open the optimal dependence on S, A, and B, while a lower bound Ω(S(A + B)T) is achieved in simple two-step turn-based games.The lower bound and matching result concern a restricted two-step setting and a mirror-descent-style algorithm.

2 Preliminaries

The preliminaries define tabular episodic zero-sum Markov games, their policies, values, best responses, regret, and turn-based specialization. These concepts establish the setting in which self-play algorithms are analyzed.

Markov games: A zero-sum Markov game generalizes an MDP to two players, with one maximizing total return and the other minimizing it.The game is specified by horizon H, state and action spaces, transitions, and rewards.
Markov games: Each episode begins from an adversarially selected state, after which both players act simultaneously, receive rewards, and transition according to the action pair.Rewards are bounded in [0, 1], and transitions may depend on the current state and both actions.
Policies and values: Policies specify action distributions at each state and step, while value and Q-value functions measure expected cumulative rewards under those policies.The value function starts from a state and step; the Q-value additionally conditions on the players’ actions.
Best responses and regret: Best responses optimize one player’s performance against the other player’s fixed strategy, and minimax optimal strategies form a Nash equilibrium.The preliminaries use these properties to motivate regret based on performance against best responses.
Best responses and regret: Regret evaluates deployed policy pairs across episodes against best responses, while self-play chooses strategies for both players.The starting state may be adversarial, and the algorithm controls both sides of each episode.
Turn-based games: Turn-based games partition steps between the max-player and min-player, representing the inactive player with a single dummy action.This specialization includes games such as GO and yields pure Nash-equilibrium strategies.

3 Main Results

The paper extends optimistic exploration to two-player zero-sum Markov games through VI-ULCB, using separate upper and lower value estimates to coordinate self-play policies. It proves regret guarantees against adversarial opponents, with improved runtime and regret in turn-based games.

Algorithm: VI-ULCB extends UCB-style exploration to two-player games by maintaining upper and lower Q estimates for the players’ conflicting objectives.The algorithm jointly determines policies using both estimates rather than assigning each player an independent greedy response.
Algorithm: The algorithm computes joint policies through a Nash equilibrium of a general-sum game whose payoff matrices are Qup and Qlow.This construction addresses the mutual dependence between each player’s greedy strategy and the opponent’s action choice.
Guarantees: VI-ULCB’s estimates remain optimistic with respect to both game uncertainty and the opponent’s best response, enabling regret against a fully adversarial opponent.The corresponding guarantee would not follow from estimates that only upper- and lower-bound Nash-equilibrium values.
Guarantees: The regret theorem yields a PAC bound: with fixed initial state, near-equilibrium policies are obtained after K ≥ Ω(H^4S^2ABι/ε^2) episodes.The bound holds with probability at least 1 − p, where ι = log(HSAB/(pε)).
Computational trade-offs: The general algorithm is sample-efficient but not guaranteed polynomial-time because its general-sum Nash subroutine has PPAD-complete approximation complexity.Practical implementations may work efficiently, and a separate algorithm trades statistical efficiency for guaranteed polynomial runtime.
Turn-based games: For turn-based games, VI-ULCB achieves polynomial runtime and regret O(H^3S^2(A + B)Tι) with probability at least 1 − p.Turn-based structure reduces the Nash computations to vector games that are solvable in linear time.

4 Computationally Efficient Algorithm

The paper presents a polynomial-time explore-then-exploit algorithm for general zero-sum Markov games, trading statistical efficiency for computational efficiency. Reward-free exploration estimates the game model before value iteration computes and deploys its Nash equilibrium.

O(T^2/3) regret accompanies a guaranteed polynomial runtime for the explore-then-exploit algorithm in general zero-sum Markov games.This improves computational efficiency relative to Algorithm 1 while incurring slightly worse regret.
The algorithm first performs polynomial-time reward-free exploration to estimate transitions and rewards, then applies value iteration to the empirical game.It deploys the resulting Nash-equilibrium policy for the remaining episodes.
Reward-free exploration visits possible states and gathers transition and reward information without using reward signals to guide exploration.The estimates are designed to make the empirical and true games' Nash equilibria close.
Artificial rewards reduce state-coverage exploration to single-agent reinforcement learning over the joint action set C = A × B.For each target state, the artificial reward is one at that state and zero elsewhere.
The empirical Nash equilibrium can be computed by value iteration, which uses the estimated transition and reward functions.The text states that value iteration only calls the NASH subroutine.

5 Towards the Optimal Regret

This section examines whether the regret bounds are tight, identifying gaps between general-game upper and lower bounds and matching the lower bound in short-horizon settings. It also explains why multi-step games remain technically difficult.

The optimal regret dependence on H, S, A, and B for general Markov games remains an open question.
The known lower bound is Ω(√(SAT)) for turn-based games and therefore also applies to general zero-sum games.
General-game upper bounds have gaps in both state dependence and action dependence when compared with the lower bound.The comparison is between ˜O(S^2ABT · poly(H)) for general games and the stated lower bound.
Mirror descent algorithms match the lower bound's ˜O(√(S(A + B)T)) scaling in one-step general games and two-step turn-based games.These are the settings in which each player plays only once.
Weak regret evaluates performance against a fixed opponent across episodes, and it is always no larger than the standard regret.This weaker measure underlies the short-horizon matching results.
Unbiased counterfactual Q-value estimates enable the short-horizon mirror descent guarantees but are unavailable in multi-step games.Closing the multi-step and standard-versus-weak regret gaps remains an open question.

6 Conclusion

The paper concludes that VI-ULCB provides a self-play route to efficiently finding Nash equilibrium policies in zero-sum Markov games, while explore-then-exploit methods improve runtime at some regret cost. Remaining directions include sharper regret dependence, computational efficiency, and extension beyond tabular games.

VI-ULCB constructs upper and lower value-function bounds and iteratively solves general-sum subgames.
Explore-then-exploit algorithms improve computational efficiency while accepting slightly worse regret, and mirror descent reduces state and action dependence in one-step games.
The paper identifies computationally efficient algorithms with ˜O(√T) regret and optimal dependence on S, A, and B as future goals.
The present results apply only to tabular games, leaving function approximation as an open extension.

A Proofs for Section 3

The proofs establish confidence bounds for the running upper and lower Q estimates through induction and concentration arguments, then use these bounds to derive the regret guarantee. The analysis relies on bounded value functions, covering arguments, and martingale concentration.

The proof concludes after combining the concentration and update bounds with the selected confidence bonus.
Lemma 11 provides high-probability upper and lower bounds for the running Q estimates across states, actions, steps, and episodes.
The ULCB proof verifies the bounds by backward induction from the terminal step through the game horizon.
Uniform concentration is established over value functions bounded in [0, H], using an ε-cover and a union bound.
The regret proof combines the ULCB bounds with the algorithm's updates and controls martingale differences using the Azuma-Hoeffding inequality.

A.2 Proof of Corollary 3

The proof converts the episodic VI-ULCB policies into a uniformly sampled policy pair and applies a high-probability regret bound. Choosing sufficiently many episodes makes the resulting error at most ε.

The proof uses a standard online-to-batch conversion by uniformly sampling the policies deployed across episodes.The sampled policies are denoted (bµ, bν).
Theorem 2 supplies a high-probability regret bound for the deployed policies.
K ≥ Õ(H^4S^2AB/ε^2) episodes suffice to make the resulting bound at most ε.

B Proofs for Section 4

This section proves the exploration-based guarantees through a value-estimation lemma and then derives an explore-then-exploit regret bound. The exploration phase identifies ε-optimal policies before exploitation.

The proofs of Theorem 5 and Corollary 6 rely on a lemma about the RE-EXPLORATION subroutine.The lemma’s proof is deferred to Appendix D.
Lemma 13 bounds the difference between estimated and true value functions uniformly over policies with high probability.The estimated and true values correspond to MG(ˆP, ˆr) and MG(P, r).
The proof uses contraction of the infimum and supremum operators together with the Nash-equilibrium property of the estimated game.
T0 = c(H^5S^2ABι/ε^2 + H^7S^4ABι^3/ε) episodes are required to obtain ε-optimal policies.
The algorithm explores for T0 episodes to find ε-optimal policies, then exploits the same policy pair for the remaining episodes.

C.1 Proof of Theorem 9

Theorem 9 is proved by reducing weak regret to adversarial bandit problems and applying mirror-descent guarantees. The construction handles one-step games, multiple initial states, and both players.

The proof’s main ingredient is a loss estimator with computability, boundedness, unbiasedness, and bounded-variance properties.These properties enable standard mirror-descent analysis.
For S = 1, the game reduces to a zero-sum matrix game with noisy bandit feedback.
The max-player uses mirror descent to bound one regret component by Õ(√(AT)), while the min-player obtains Õ(√(BT)) for the other.
The resulting weak-regret bound scales as Õ(√((A + B)T)).
For S > 1, the algorithm treats the states as independent zero-sum matrix games and sums their regret bounds.
Algorithm 3 updates each player’s action distribution using exponential-weights rules with state-dependent learning rates.

C.2 Proof of Theorem 10

Theorem 10 analyzes mirror descent for one-step turn-based games and combines contextual bandit regret with martingale concentration. Its exploration component estimates the game model before exploitation.

The one-step turn-based setting is not a zero-sum matrix game because the transition dynamics are unknown.
The max-player’s regret is reduced to online linear optimization over the action simplex with bandit feedback.
The loss estimator is computable, bounded, and analyzed through its conditional expectation and variance.
When initial states vary, the algorithm updates each state-specific policy only when that state occurs, effectively solving separate bandit problems.
The contextual-bandit analysis uses EXP3++ scheduling because state occurrence counts are unknown in advance.
Algorithm 4 constructs empirical transitions and rewards through policy sampling and trajectory data collection for reward-free exploration.Its policy set targets visits to significant states before empirical model estimation.

E Connection to Algorithms against Adversarial Opponents and R-MAX

Low-regret algorithms against adversarial opponents can be converted into provable self-play algorithms, but some existing guarantees are too weak or mismatched for this setting.

Low-regret guarantees against adversarial opponents can be used to design self-play algorithms with low regret in Markov games.The construction runs the algorithm for both players and uses symmetry to obtain the self-play guarantee.
The resulting self-play guarantee requires the adversarial-opponent regret bound to have the paper's specified form.Guarantees outside that form cannot directly yield the paper's regret bound.
R-MAX: R-MAX provides a weaker guarantee involving comparison with a Nash equilibrium, so it cannot establish regret in this paper's setting.Although R-MAX studies Markov games and handles adversarial strategies, its guarantee is not strong enough for the required reduction.
Adversarial MDPs: Adversarial-MDP results with adversarial rewards do not directly apply because an opponent's action in a Markov game also changes state transitions.The distinction concerns both received rewards and the transition to the next state.