PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

Qinghua Liu, Tiancheng Yu, Yu Bai, Chi Jin

arXiv:2010.01604v2cs.LGcs.AIstat.ML

TL;DR

Multi-agent reinforcement learning needs many samples, and existing model-based sample-complexity guarantees for Markov games were suboptimal relative to model-free methods. The paper analyzes model-based self-play and introduces Nash-VI for two-player zero-sum games. Nash-VI achieves ˜O(H^3SAB/epsilon^2) episodes, nearly matching the information-theoretic lower bound, and the analysis also supports reward-free and general-sum algorithms.

  • Problem

    For multi-agent reinforcement learning in Markov games, existing model-based sample-complexity guarantees were suboptimal and compared unfavorably with recent model-free approaches.

    Source: §1 · pp. 1–2

  • Method

    The paper develops a sharp analysis of model-based self-play and designs Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games.

    Source: §1 · p. 2

  • Results

    Nash-VI finds an ǫ-approximate Nash equilibrium in ˜O(H^3SAB/epsilon^2) episodes, almost matching the lower bound except for the AB versus A + B dependency.

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

  • Takeaways & Limitations

    The analysis also yields a task-agnostic algorithm for zero-sum games and the first line of sample-efficient algorithms for multi-player general-sum games.

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

    Nash-VI has higher computational complexity than Nash V-Learning because it solves linear programs for CCEs in each episode.

    Source: §3.2 · p. 10

Abstract

from arXiv · show

Model-based algorithms -- algorithms that explore the environment through building and utilizing an estimated model -- are widely used in reinforcement learning practice and theoretically shown to achieve optimal sample efficiency for single-agent reinforcement learning in Markov Decision Processes (MDPs). However, for multi-agent reinforcement learning in Markov games, the current best known sample complexity for model-based algorithms is rather suboptimal and compares unfavorably against recent model-free approaches. In this paper, we present a sharp analysis of model-based self-play algorithms for multi-agent Markov games. We design an algorithm -- Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games that is able to output an $\epsilon$-approximate Nash policy in $\tilde{\mathcal{O}}(H^3SAB/\epsilon^2)$ episodes of game playing, where $S$ is the number of states, $A,B$ are the number of actions for the two players respectively, and $H$ is the horizon length. This significantly improves over the best known model-based guarantee of $\tilde{\mathcal{O}}(H^4S^2AB/\epsilon^2)$, and is the first that matches the information-theoretic lower bound $\Omega(H^3S(A+B)/\epsilon^2)$ except for a $\min\{A,B\}$ factor. In addition, our guarantee compares favorably against the best known model-free algorithm if $\min \{A,B\}=o(H^3)$, and outputs a single Markov policy while existing sample-efficient model-free algorithms output a nested mixture of Markov policies that is in general non-Markov and rather inconvenient to store and execute. We further adapt our analysis to designing a provably efficient task-agnostic algorithm for zero-sum Markov games, and designing the first line of provably sample-efficient algorithms for multi-player general-sum Markov games.

1 Introduction

The paper asks whether model-based methods can attain sharp sample complexity in multi-agent reinforcement learning, where prior guarantees for two-player zero-sum games lagged the lower bound. It presents Nash-VI and extends its analysis to reward-free and multi-player general-sum settings.

1 Introduction

  • Prior two-player zero-sum model-based bounds were ˜O(H^4S^2AB/ǫ^2), while the information-theoretic lower bound is Ω(H^3S(A + B)/ǫ^2).The cited model-free Nash V-Learning guarantee is ˜O(H^6S(A + B)/ǫ^2), near the lower bound except for a polynomial factor in H.Source: §1 · p. 2
  • Nash-VI finds an ǫ-approximate Nash equilibrium in ˜O(H^3SAB/ǫ^2) episodes, improving the best prior model-based guarantee by O(HS) and matching the lower bound except for a ˜O(min {A, B}) factor.It outputs a simple Markov policy, unlike Nash V-Learning's nested mixture of Markov policies.Source: §1 · p. 2
  • VI-Zero finds ǫ-approximate Nash policies for N games sharing transitions and having different known rewards in ˜O(H^4SAB log N/ǫ^2) episodes.Its episode bound scales logarithmically with the number of games.Source: §1 · p. 3
  • The paper presents the first line of sample-efficient algorithms for multi-player general-sum Markov games.The introduction states that these algorithms can target Nash, CE, or CCE equilibria, using a multi-player Nash-VI or reward-free value-iteration variant.Source: §1 · p. 3

1.1 Related work

  • Earlier non-asymptotic work studied Markov games without reachability assumptions, and Nash V-Learning returns a nested mixture that is hard to implement.The paper contrasts that output with Nash-VI's simple Markov policy.Source: §1 · p. 2, §1.1 · p. 4

2 Preliminaries

The preliminaries specify a finite-horizon, tabular two-player zero-sum Markov game and its interaction protocol. They introduce Markov policies and value functions, then frame learning in terms of approximate Nash equilibrium and sample-complexity or regret guarantees.

2 Preliminaries

  • A two-player zero-sum game has H steps, at most S states, action sets of sizes at most A and B, transition matrices, and deterministic rewards in [0, 1].The reward is the max-player's gain and the min-player's loss.Source: §2 · p. 5
  • At each step, both players observe the state, choose actions simultaneously, observe the opponent's action, receive reward, and transition to the next state.Episodes start from a fixed initial state and end after step H.Source: §2 · p. 5
  • A Markov policy maps each state and step to an action distribution, while value functions describe expected cumulative rewards under a policy pair.The preliminaries also define a Bellman equation for these value functions.Source: §2 · p. 5
  • The learning objective measures suboptimality against best responses, and the paper considers both ǫ-approximate Nash equilibrium PAC bounds and regret bounds.The text notes that sublinear regret can be converted to a polynomial-sample PAC algorithm by online-to-batch conversion.Source: §2 · p. 6

3 Optimistic Nash Value Iteration

Nash-VI combines optimistic planning with an auxiliary bonus to improve model-based learning guarantees for two-player zero-sum Markov games. Its Bernstein-bonus guarantee is near the information-theoretic lower bound, with a remaining action-factor gap.

3.1 Algorithm description

  • Each episode plans optimistically using the estimated transition, plays the resulting policy, and updates the transition estimate from collected samples.The algorithm outputs the policy from the episode with minimum gap.Source: §3.1 · p. 7

3.1.1 Overview of techniques

  • The auxiliary bonus γ permits a smaller β while preserving valid confidence bounds, removing an S factor from the sample complexity.Its coefficient is c/H, so the added error affects the overall sample complexity only by a constant factor.Source: §3.1.1 · p. 7

3.2 Theoretical guarantees

  • ˜O(H^3SAB/ε^2) episodes with Bernstein bonuses match the lower-bound dependencies on H, S, and ε, leaving only an AB/(A+B) ≤ min{A,B} action-factor gap.The bound improves the leading sample-complexity term by a factor of H over the Hoeffding-bonus guarantee.Source: §3.1.1 · p. 8, §3.2 · p. 9

3.1.1 Overview of techniques

  • Nash-VI uses coarse correlated equilibria (CCEs) instead of Nash equilibria during planning, avoiding a PPAD-complete matrix-game computation and enabling polynomial-time computation.A CCE can be computed by linear programming, and its correlated policies require cooperation between the players.Source: §3.1.1 · pp. 8–9

3.2 Theoretical guarantees

  • ˜O(H^4SAB/ε^2) episodes suffice with Hoeffding bonuses, improving the model-based sample-complexity dependence on S from S^2 to S.For large T, the regret bound scales as ˜O(H^3SABT).Source: §3.2 · p. 9
  • Compared with Nash V-Learning, Nash-VI has better H dependence, returns a single pair of Markov policies, and has a T-regret guarantee, while Nash V-Learning has better computational complexity.Nash-VI requires solving linear programs for CCEs in each episode; Nash V-Learning returns a nested mixture of Markov policies.Source: §3.2 · pp. 9–10

4 Reward-free Learning

VI-Zero separates reward-free exploration from planning for multiple tasks that share transition dynamics. Its learned transition supports approximate Nash equilibria across fixed reward functions, with sample complexity scaling logarithmically in the number of tasks.

4 Reward-free Learning

  • Reward-free learning targets multiple tasks with shared transition dynamics, collecting transitions before using task-specific reward information in planning.The paper notes applications such as robotics, where tasks share the world but have different rewards.Source: §4 · p. 10

4.1 Algorithm description

  • VI-Zero explores with zero reward and maximizing policies, treating its estimated values as measures of uncertainty or suboptimality rather than actual value bounds.It outputs the transition estimate from the episode minimizing the initial estimated value.Source: §4.1 · p. 10
  • For each task, planning computes a Nash equilibrium using the estimated transition and that task’s empirical reward, with no sampling error in this computation.The paper notes that vanilla Nash value iteration without optimism is one possible planning algorithm.Source: §4.1 · p. 10

4.2 Theoretical guarantees

  • ˜O(H^4SAB/ε^2) samples suffice, when ε is small, to learn a transition estimate supporting ε-approximate Nash equilibria for all N fixed reward functions.The theorem gives a high-probability guarantee when the episode count also meets its stated lower bound.Source: §4.2 · p. 11
  • VI-Zero’s sample complexity scales logarithmically with N, unlike reward-aware approaches that must be rerun for each task, but it loses a leading factor of H versus Nash-VI and has no regret guarantee.Without reward information, the exploration policies are naturally suboptimal.Source: §4.2 · p. 11
  • The exploration and planning stages are decoupled: the transition estimate can be paired with an arbitrary planner that computes a Nash equilibrium for known transitions and rewards.Source: §4.2 · p. 12
  • In reward-free learning, AB dependence is unavoidable; the lower bound makes the sample complexity optimal in S, A, B, and ε.The paper contrasts this with reward-aware learning, where A+B dependence is achievable through reward-aware sampling.Source: §4.2 · p. 12

5 Multiplayer General-sum Markov Games

The paper extends its model-based algorithms to multiplayer general-sum Markov games, treating Nash, correlated equilibrium, and coarse correlated equilibrium as distinct solution concepts. It gives sample-efficient guarantees for equilibrium finding and reward-free learning, with computational and scaling trade-offs.

5 Multiplayer General-sum Markov Games

  • The paper extends its model-based algorithms to multiplayer general-sum Markov games through Multi-Nash-VI and Multi-VI-Zero.The game formulation uses each player's action space and reward function with shared transition dynamics.Source: §5 · p. 12, §5.1 · p. 12, §5.2 · p. 14

5.1 Problem formulation

  • Nash, CE, and CCE coincide in two-player zero-sum games but are distinct solution notions in multiplayer general-sum games.The paper gives the nesting Nash ⊆ CE ⊆ CCE; CE and CCE need not be product policies.Source: §5.1 · pp. 12–14

5.2 Multiplayer optimistic Nash value iteration

  • With K ≥ Ω(H^4S^2(∏ Ai)ι/ε^2), Multi-Nash-VI outputs an ε-approximate Nash, CE, or CCE in multiplayer general-sum Markov games.The bound grows exponentially with the number of players because it depends on the product of their action counts; the analysis lacks the auxiliary bonus and Bernstein technique used in the two-player result.Source: §5.2 · pp. 14–15
  • Using the NASH subroutine gives the strongest guarantee but may be PPAD-hard; CE and CCE subroutines run in polynomial time but provide weaker guarantees.CE and CCE policies are not guaranteed to be product policies.Source: §5.2 · pp. 14–15

5.3 Multiplayer reward-free learning

  • Multi-VI-Zero learns a transition model whose equilibria are ε-approximate in the true game for all N fixed reward functions.The guarantee applies to Nash, CE, or CCE of the learned game for each reward function.Source: §5.3 · pp. 15–16

6 Conclusion

The conclusion presents Nash-VI's sample complexity for zero-sum Markov games and identifies open questions on action-count dependence and general-sum sample complexity. The appendices provide Bellman equations and establish properties of coarse correlated equilibrium.

6 Conclusion

  • Nash-VI finds an ε-approximate Nash equilibrium in zero-sum Markov games in Õ(H^3SAB/ε^2) episodes, nearly matching the lower bound except for the AB versus A + B dependence.The paper leaves reducing the dependence to A + B as future work.Source: §6 · p. 16
  • The paper identifies improving general-sum sample complexity, for example from O(S^2) to O(S), as future work.It also asks whether model-based zero-sum methods can achieve A + B rather than AB dependence.Source: §6 · p. 16

A Bellman Equations for Markov Games

  • The appendix presents Bellman equations for different value types in Markov games, including fixed policies, best responses, and Nash equilibria.The Nash equations are described as Bellman optimality equations.Source: A Bellman Equations for Markov Games · p. 20

B Properties of Coarse Correlated Equilibrium

  • For a one-step game with payoff matrix Q, the marginals of CCE(Q, Q) form a Nash equilibrium.The appendix also states that CCEs can be efficiently computed by linear programming, while general-sum CCEs need not be Nash equilibria.Source: B Properties of Coarse Correlated… · pp. 20–21

C.1 Proof of Theorem 3

The proof bounds transition-estimation error with concentration inequalities, establishes upper and lower value bounds by backward induction, and uses these bounds to control regret and derive the PAC guarantee.

C.1 Proof of Theorem 3

  • Bernstein concentration and a union bound control empirical transition estimates across state-action-step tuples and visit counts.The proof uses an equivalent process that samples successor states independently for each fixed tuple.Source: §C.1 · p. 22
  • Backward induction establishes that the algorithm's upper and lower Q- and V-value bounds hold at every step.The proof combines the event controlling transition estimates with the bonus definition.Source: §C.1 · pp. 23–24
  • The proof uses the value bounds to upper-bound regret, then selects an output policy for the PAC guarantee.The final regret bound combines the high-probability events used in the argument.Source: §C.1 · pp. 24–25

C.2 Proof of Theorem 4

The proof of Theorem 4 establishes value and Q-value bounds under a high-probability event, then controls the empirical-variance error and sums variance terms to complete the theorem proof.

C.2 Proof of Theorem 4

  • Under event E1, backward induction establishes bounds for V-values and Q-values, with the Q-value argument requiring a more careful bound on term (B).The proof reuses the V-value argument and bounds term (A) as before.Source: §C.2 · p. 26
  • A separate lemma controls the empirical-variance estimator error under event E1.The proof then uses a martingale concentration bound to control the sum of variance terms.Source: §C.2 · pp. 27, 29
  • With probability at least 1−2p, the proof combines its concentration event and a variance-term bound to complete Theorem 4.The two probability contributions are each bounded by p.Source: §C.2 · p. 29

D.1 Proof of Theorem 5

Theorem 5’s proof relates empirical optimal values to true optimal values through exploration value functions. The appendix also describes Vanilla Nash Value Iteration for computing an equilibrium in a known model.

D.1 Proof of Theorem 5

  • For multiple reward functions, the proof extends the single-reward case by replacing failure probability p with Np using a union bound.The stated proof first treats N = 1.Source: §D.1 · p. 29
  • The proof obtains its concentration event by applying concentration inequalities and a union bound; each state-action-stage tuple is reached at most K times.The empirical transition estimate is controlled over interaction counts up to K.Source: §D.1 · p. 30
  • The empirical optimal value functions are close to the true optimal ones, with their difference controlled by Algorithm 2’s exploration value functions.The proof develops this relationship through backward induction and a key lemma.Source: §D.1 · pp. 30–31

D.2 Vanilla Nash Value Iteration

  • Vanilla Nash Value Iteration replaces the MDP maximum operator with a minimax operator and outputs a Nash equilibrium for the known model.The two-player zero-sum Nash equilibrium can be computed in polynomial time.Source: §D.2 · p. 33

D.3 Proof of Theorem 6

This section proves reward-free sample-complexity lower bounds, first for matrix games and then for Markov games.

D.3 Proof of Theorem 6

  • The section establishes a Θ(AB/ε^2) lower bound for reward-free learning of matrix games, where S = H = 1.Source: §D.3 · p. 33
  • It then generalizes the reward-free lower bound to Θ(SABH^2/ε^2) for Markov games.Source: §D.3 · p. 33
  • The lower bounds concern reward-free learning, distinguishing the matrix-game case from the general Markov-game setting.Source: §D.3 · p. 33

D.3.1 Reward-free learning of matrix games

The matrix-game lower-bound argument makes learning an approximately optimal policy depend on identifying a hidden optimal row. It shows that limited sampling can prevent reliable row identification and thus yield a suboptimal policy.

D.3.1 Reward-free learning of matrix games

  • An ε/10-optimal policy in the constructed matrix game must play the hidden optimal row a* with probability at least 2/3.The optimal max-player policy always selects row a*; below the 2/3 threshold, the policy is at least ε/10 suboptimal.Source: §D.3.1 · p. 34
  • The reduction converts an ε/10-optimal policy into a row-identification procedure by guessing the most-played row.Any ε/10-optimal policy plays a* with probability at least 2/3.Source: §D.3.1 · p. 34
  • With at most AB/(103ε^2) samples, some game in the family makes a reward-free algorithm output a policy at least ε/10 suboptimal with probability at least 1/4.Source: §D.3.1 · p. 34
  • With the same sample cap, some game in the family makes a reward-free algorithm fail to identify the optimal row with probability at least 1/4.Source: §D.3.1 · p. 34

D.3.2 Reward-free learning of Markov games

The lower-bound construction embeds independent matrix games at each state and step, with uniformly random transitions. It shows reward-free learning requires order SABH^2/epsilon^2 episodes in the worst case.

D.3.2 Reward-free learning of Markov games

  • The construction embeds SH independently sampled Bernoulli matrix games, each from M(epsilon/H), and transitions uniformly among S states.The game has S+1 states and horizon H+1, with no reward at the initial step.Source: §D.3.2 · pp. 35–36
  • An epsilon/10^3-suboptimal policy would identify the optimal max-player action for at least SH − floor(SH/500) state-step pairs with the same success probability.The reduction converts a policy into guesses by selecting the most probable action at each pair.Source: §D.3.2 · p. 36
  • SABH^2/(104epsilon^2) episodes can leave a reward-free learner with a policy that is at least epsilon/10^3 suboptimal with probability at least 1/4.The claim gives the episode threshold for the lower-bound instance.Source: §D.3.2 · p. 37
  • The proof argues that under the episode threshold, some constructed game forces failures on more than floor(SH/500) state-step pairs with probability at least 1/4.It establishes a per-pair error lower bound of 1/3 under a uniformly chosen instance, contradicting successful identification of nearly all pairs.Source: §D.3.2 · p. 37

E Proof for Section 5 – Multi-player General-sum Markov Games

These appendix proofs establish high-probability bounds for optimistic value and Q estimates across Nash, coarse correlated, and correlated equilibria. They use the Nash arguments as a template and adapt the equilibrium-specific step for CCE and CE.

E.1.1 NE Version

  • For Nash equilibrium, the proof inductively establishes upper bounds for the optimistic value and Q estimates.The section identifies these bounds as the basis for proving Theorem 15.Source: §E.1.1 · p. 39

E.1.2 CCE Version

  • For CCE, the proof replaces the Nash-specific lemma with a counterpart and otherwise follows the same argument.Lemma 39 supplies the corresponding high-probability bound.Source: §E.1.2 · p. 41

E.1.3 CE Version

  • For CE, the proof likewise adapts the Nash-specific step, with Lemma 40 giving the corresponding high-probability bound.The induction uses the definition of correlated equilibrium in its equilibrium-specific step.Source: §E.1.3 · pp. 41–42

E.2 Proof of Theorem 16

  • For Theorem 16, the proof treats one reward function first; multiple reward functions follow by a union bound, replacing failure probability p with Np.This stated extension applies when N is greater than one.Source: §E.2 · p. 42

E.2.1 NE version

  • In the NE version, two lemmas on empirical-model value and Q estimates together imply the theorem’s Nash-equilibrium conclusion.The proof derives the bounds by induction over the horizon and uses uniform concentration.Source: §E.2.1 · pp. 42–43

E.2.2 CCE version

  • The CCE proof reuses the Nash value-function lemma and proves an analogous Q-function bound before combining them.The text says the argument is almost the same as the Nash proof.Source: §E.2.2 · p. 44

E.2.3 CE version

  • The CE proof also reuses the Nash value-function lemma and proves an analogous bound that covers strategy modifications.The stated bound ranges over strategy modifications for a player.Source: §E.2.3 · p. 45
Loading 2010.01604v2…