PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Optimal Reinforcement Learning with Self-Play

Yu Bai, Chi Jin, Tiancheng Yu

arXiv:2006.12007v2cs.LGcs.AIstat.ML

TL;DR

The paper asks how to reduce sample demands for near-optimal learning in multi-agent games. It develops self-play algorithms for approximate Nash equilibria and reports sample complexity matching the information-theoretic lower bound up to polynomial factors in episode length.

  • Problem

    Sample-complexity theory for multi-agent reinforcement learning remains limited compared with single-agent MDPs, where near-optimal guarantees are known.

    Source: §1 · p. 1

  • Method

    The paper develops self-play algorithms for approximate Nash equilibria, including optimistic Nash Q-learning with incremental Q-value updates and refreshed greedy policies.

    Source: §1 · p. 2, §3 · p. 6

  • Results

    The self-play algorithms match the information-theoretic lower bound up to a polynomial factor in episode length.

    Source: §6 · p. 11

  • Takeaways & Limitations

    Learning fixed-opponent best responses and achieving sublinear regret against adversarial opponents are computationally hard in Markov games.

    Source: §6 · p. 11

    The computational-hardness claim is conditional on Conjecture 7, which rules out polynomial-time learning of party with noise.

    Source: §5 · p. 10

Abstract

from arXiv · show

This paper considers the problem of designing optimal algorithms for reinforcement learning in two-player zero-sum games. We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. In a tabular episodic Markov game with $S$ states, $A$ max-player actions and $B$ min-player actions, the best existing algorithm for finding an approximate Nash equilibrium requires $\tilde{\mathcal{O}}(S^2AB)$ steps of game playing, when only highlighting the dependency on $(S,A,B)$. In contrast, the best existing lower bound scales as $\Omega(S(A+B))$ and has a significant gap from the upper bound. This paper closes this gap for the first time: we propose an optimistic variant of the \emph{Nash Q-learning} algorithm with sample complexity $\tilde{\mathcal{O}}(SAB)$, and a new \emph{Nash V-learning} algorithm with sample complexity $\tilde{\mathcal{O}}(S(A+B))$. The latter result matches the information-theoretic lower bound in all problem-dependent parameters except for a polynomial factor of the length of each episode. In addition, we present a computational hardness result for learning the best responses against a fixed opponent in Markov games---a learning objective different from finding the Nash equilibrium.

1 Introduction

The introduction frames a gap between multi-agent Markov-game sample-complexity upper and lower bounds, then presents self-play algorithms and related computational results. Its contributions include near-optimal Nash-equilibrium learning and a hardness result for best responses to fixed opponents.

1 Introduction

  • Multi-agent sample complexity remains open: the best known Nash-equilibrium algorithm scales as S^2AB, versus a lower bound scaling as S(A + B).The question is whether algorithms can attain near-optimal sample complexity for Markov games.Source: §1 · p. 2
  • The paper introduces self-play algorithms for two-player Markov games whose sample complexity matches the lower bound up to a poly(H) factor.The algorithms learn by playing against themselves without direct supervision.Source: §1 · p. 2

1.1 Our contributions

  • The paper proves optimistic Nash Q-learning finds an ǫ-approximate Nash equilibrium with sample complexity ˜O(H^5SAB/ǫ^2).It builds optimistic upper and lower Q-value estimates and computes a Coarse Correlated Equilibrium over them for execution policies.Source: §1.1 · p. 2
  • Nash V-learning achieves sample complexity ˜O(H^6S(A + B)/ǫ^2), matching the minimax lower bound up to a poly(H) factor.It improves on Nash Q-learning when min {A, B} > H and combines FTRL with standard Q-learning to determine execution policies.Source: §1.1 · p. 2
  • Learning best responses to fixed opponents is as hard as learning parity with noise; the result also implies computational hardness for sublinear regret against adversarial opponents.The paper notes that this rules out efficient Nash-equilibrium algorithms based on running separate no-regret algorithms for each player.Source: §1.1 · p. 2
  • The paper proposes extracting certified policies from Nash Q- and V-learning estimates, with performance similar to Nash-equilibrium policies even against best responses.The authors suggest the technique may be of broader interest.Source: §1.1 · p. 2

1.2 Related Work

  • Earlier self-play work either assumes strong reachability or simulators, while results without those assumptions have suboptimal sample complexity.Wei et al. [35] assume an opponent-independent way to reach all states; Jia et al. [13] and Sidford et al. [29] assume simulators or generative models.Source: §1.2 · p. 3
  • Adversarial-MDP results do not directly yield self-play guarantees here because a Markov-game opponent can affect both rewards and transitions.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define the episodic zero-sum Markov-game setting, its policies and value functions, and the paper’s two learning objectives. They distinguish approximate Nash-equilibrium learning from learning a best response to a fixed opponent.

2 Preliminaries

  • A zero-sum Markov game generalizes an MDP to two players: the max-player maximizes total return and the min-player minimizes it.The tabular episodic model specifies states, both action sets, transition matrices, and deterministic rewards at each step.Source: §2 · p. 4
  • Each episode starts at a fixed state; players simultaneously choose actions, observe the opponent’s action, receive reward, and transition to the next state.Source: §2 · p. 4
  • Markov policies map states to action distributions, while V- and Q-value functions describe expected cumulative rewards from a state or state-action pair.The Bellman equation uses the transition operator and the expected Q-value under a policy.Source: §2 · p. 4
  • A Nash equilibrium consists of strategies optimal against the opponents’ best responses; an approximate equilibrium is evaluated by the gap to that performance.The preliminaries also allow history-dependent general policies, whose best responses need not be Markovian.Source: §2 · pp. 4–5
  • The paper studies both best-response learning against a fixed unknown opponent and finding a Nash equilibrium; worst-case best-response learning is described as more challenging.The approximate best-response objective fixes the opponent’s general policy, whereas the Nash objective evaluates both policies against best responses.Source: §2 · p. 5

3 Optimistic Nash Q-learning

Optimistic Nash Q-learning maintains upper and lower Q-value estimates and uses a CCE to choose execution policies; extracted certified policies achieve an approximate Nash equilibrium with a sample bound linear in S.

3 Optimistic Nash Q-learning

  • The algorithm maintains separate upper and lower Q-values and adds a visit-count-dependent bonus to their incremental updates.The updates use the number of visits to the state-action pair at the current step.Source: §3 · p. 6
  • A Coarse Correlated Equilibrium over the paired Q estimates supplies the greedy execution policies and can be computed by linear programming in polynomial time.The algorithm uses a CCE subroutine to calculate policies from the pair of estimates.Source: §3 · p. 6
  • Lemma 3 bounds the Nash value with upper and lower estimates and brings their averages close to the equilibrium value, but value learning alone does not certify near-Nash policies.The distinction motivates extracting policies that perform well even against best responses.Source: §3 · p. 7
  • The certified policies are non-Markovian nested mixtures, and executing them requires storing policies across episodes, so space complexity grows linearly with K.The extracted max- and min-player policies are defined symmetrically.Source: §3 · pp. 7–8
  • O(H^5SABι/ε²) episodes suffice for the extracted certified policies to be ε-approximate Nash, with probability at least 1−p.The guarantee applies to the policies extracted from optimistic Nash Q-learning.Source: §3 · p. 8
  • Online Q-learning updates support sample complexity linear in S because each sample updates a value function independent of that sample.The paper contrasts this independence property with value-iteration methods.Source: §3 · p. 8

4 Optimistic Nash V-learning

Optimistic Nash V-learning combines FTRL with Q-learning and achieves an approximate Nash equilibrium with sample complexity proportional to S(A+B), matching the information-theoretic lower bound up to polynomial factors in H.

4 Optimistic Nash V-learning

  • Nash V-learning combines FTRL with Q-learning, using an importance-weighted loss estimate and a cumulative-loss update to determine its policy.The policy update uses the FTRL principle.Source: §4 · pp. 8–9
  • The algorithm requires no information exchange beyond standard game play, so the two players can run their versions separately; its certified policies are non-Markovian.The max-player algorithm is described in the section, with the min-player version defined symmetrically.Source: §4 · p. 9
  • FTRL's regret can be independent of the opponent's action count, a property the paper identifies as crucial to Nash V-learning's sharper sample complexity.The algorithm combines this property with standard Q-learning.Source: §4 · pp. 8–9
  • O(H^6S(A+B)ι/ε²) episodes suffice for certified policies to be ε-approximate Nash, matching the information-theoretic lower bound up to poly(H) factors and logarithmic terms.The theorem states the guarantee with probability at least 1−p.Source: §4 · p. 9

5 Hardness for Learning the Best Response

The section establishes conditional computational hardness for best-response learning and adversarial no-regret learning, then uses the latter result to rule out a natural route to efficient Nash-equilibrium algorithms.

5 Hardness for Learning the Best Response

  • With deterministic transitions and rewards and S = A = B = 2, polynomial-time best-response learning would yield polynomial-time learning parity with noise.The paper notes that learning parity with noise is conjectured to be hard.Source: §5 · p. 10
  • The reduction’s difficulty arises when an opponent can use non-Markovian policies to encode long-term correlations such as parity with noise.The paper contrasts this with the Markov-opponent case, where best-response learning is as easy as learning an optimal policy in a standard MDP.Source: §5 · p. 10

5.1 Hardness for Playing Against Adversarial Opponent

  • Under the same small deterministic-game construction, polynomial-time no-regret learning would imply polynomial-time learning parity with noise, even against non-adaptive opponents using Markov policies each episode.This is the stated corollary of the best-response hardness result.Source: §5.1 · p. 11
  • Together with the parity-with-noise hardness conjecture, the corollary indicates fundamental difficulty in designing polynomial-time no-regret algorithms against adversarial opponents.The restriction to non-adaptive, per-episode Markov policies still applies.Source: §5 · p. 10, §5.1 · p. 11
  • Under the stated hardness conjecture, combining two no-regret algorithms cannot provide a polynomial-time approach to approximate Nash equilibrium.The section explains that symmetric regret bounds would make the mixture of the players’ policies an approximate Nash equilibrium, while the corollary rules out polynomial time for this approach.Source: §5.1 · p. 11

6 Conclusion

The paper concludes that its self-play algorithms bring approximate Nash-equilibrium sample complexity within a polynomial-in-horizon factor of the information-theoretic lower bound, while also establishing computational hardness for two related learning objectives.

6 Conclusion

  • The proposed self-play algorithms find approximate Nash equilibria with sample complexity matching the information-theoretic lower bound up to a polynomial factor in episode length.Source: §6 · p. 11
  • The paper also establishes computational hardness for finding best responses to fixed opponents in Markov games.Source: §6 · p. 11
  • It further establishes computational hardness for achieving sublinear regret against adversarial opponents in Markov games.Source: §6 · p. 11

C.1 Learning values

The proof section develops auxiliary bounds for Nash Q-learning, drawing on a single-agent Q-learning analysis and using induction and concentration arguments.

C.1 Learning values

  • Some of the analysis adapts results from single-agent Q-learning, including a cited lemma on properties used in the proof.Source: §C.1 · p. 16
  • The proof establishes a claim by induction over the step index and invokes a concentration result for the induction step.Source: §C.1 · p. 17
  • For the second claim, the argument sums terms and uses a martingale-difference sequence before combining the bounds.Source: §C.1 · pp. 17–18

C.2 Certified policies

This section analyzes certified policies derived from Nash Q-learning’s exploration process, since learning game values alone does not itself provide near-optimal policies.

C.2 Certified policies

  • Algorithm 1 learns the game value but does not itself provide a near-optimal policy, motivating analysis of certified policies from its exploration process.Source: §C.2 · p. 18
  • The analysis defines general policies and their values from a step onward when they do not depend on the history before that step.Source: §C.2 · p. 18
  • The section proves that the defined policies are certified and gives a high-probability guarantee that the induced policies are ϵ-optimal after running Nash Q-learning for K episodes.Source: §C.2 · pp. 19–21

D Proof for Nash V-learning

This appendix proves Nash V-learning’s guarantees by analyzing its state-wise weighted-regret updates and the induced policies. It also supplies the min-player counterpart and certifies the resulting policies as ε-optimal.

D.1 Missing algorithm details

  • Algorithm 7 gives the min-player counterpart to Algorithm 3, with a loss-function definition chosen to keep losses non-negative.The two algorithms are otherwise described as almost entirely symmetric.Source: §D.1 · p. 21

D.2 Learning values

  • Algorithm 3 is analyzed as Follow-the-Regularized-Leader with a changing step size for each state, using an optimistic biased estimator to handle bandit feedback.Its state-wise losses form an adversarial bandit problem, and the passage identifies their range as [0, H].Source: §D.2 · pp. 22–23

D.3 Certified policies

  • The induced policies from Nash V-learning are ε-optimal with probability at least 1 − p when the algorithm is run for the prescribed number of episodes.The proof uses bounds on the relevant value quantity to establish this guarantee.Source: §D.3 · pp. 25–26

E Proofs of Hardness for Learning the Best Responses

The proof reduces approximate best-response learning in a constructed Markov game to learning parity with noise. Under the stated computational-hardness conjecture, this establishes hardness for the best-response objective.

E Proofs of Hardness for Learning the Best Responses

  • The proof is inspired by an adversarial-MDP hardness construction and proceeds by constructing a game, defining a sequence of reductions, and applying the parity-learning hardness conjecture.The stated construction inspiration is [37, Section 4.2].Source: E Proofs of Hardness for Learning the… · p. 26

E.1 Markov game construction

  • The hard instance has deterministic transitions, two actions per player, and rewards only at the final step, determined by the min-player’s action.The min-player’s actions before the last step are revealed at the start of each episode, making the setting easier for the max-player.Source: §E.1 · pp. 26–27

E.2 A series of computationally hard problems

  • The proof defines parity learning with noisy labels and relates its learning variants through reductions before connecting the problem to best-response learning.The paper identifies Problem 2.3 as the formal learning-parity-with-noise problem and cites [20].Source: §E.2 · pp. 27–28

E.3 Putting them together

E.4 Proofs of Hardness Against Adversarial Opponents

This proof connects no-regret learning to best-response learning through an online-to-batch argument. It also extends the hardness claim to per-episode Markovian, non-adaptive opponent policies.

E.4 Proofs of Hardness Against Adversarial Opponents

  • With ε = poly(S, H, A, B)K^-δ and polynomial K, the proof keeps the running time for learning an ε-approximate best response polynomial.The stated running time is poly(S, H, A, B, 1/ε).Source: §E.4 · p. 29
  • The argument also considers opponent policies that are Markovian within each episode and non-adaptive to prior observations, using an online-to-batch conversion of the max-player’s policies.The passage says the corollary continues to hold for this opponent-policy setting.Source: §E.4 · p. 29

F Auxiliary Lemmas for Weighted Adversarial Bandit

This appendix develops high-probability regret and concentration bounds for weighted adversarial bandits. It presents an FTRL algorithm with changing step size and combines auxiliary bounds to obtain guarantees.

3. high probability regret bound

  • Algorithm 9 applies FTRL to weighted regret with a changing step size, assuming losses lie in [0, 1] and using unbiased loss estimates.The algorithm’s hyperparameters are set to support the stated regret guarantee.Source: F Auxiliary Lemmas for Weighted… · p. 29
  • Lemma 17 states that, following Algorithm 9, an assertion holds with probability 1 − 3p for any θ* ∈ ∆A and any t ≤ K.Source: F Auxiliary Lemmas for Weighted… · p. 30

F Auxiliary Lemmas for Weighted Adversarial Bandit

  • The proof bounds three terms separately using auxiliary lemmas, then combines the bounds with a union bound to obtain a concentration result.The appendix also supplies a concentration lemma for bounded, measurable coefficient sequences.Source: F Auxiliary Lemmas for Weighted… · pp. 30–31
Loading 2006.12007v2…