Near-Optimal Reinforcement Learning with Self-Play

A Markov policy $\mu$ of the max-player is a collection of $H$ functions $\{\mu_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\}_{h\in[H]}$, which maps from a state to a distribution of actions. Here $\Delta_{\mathcal{A}}$ is the probability simplex over action set $\mathcal{A}$. Similarly, a policy $\nu$ of the min-player is a collection of $H$ functions $\{\nu_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{B}}\}_{h\in[H]}$. We use the notation $\mu_{h}(a|s)$ and $\nu_{h}(b|s)$ to present the probability of taking action $a$ or $b$ for state $s$ at step $h$ under Markov policy $\mu$ or $\nu$ respectively.

We use $V^{\mu,\nu}_{h}\colon\mathcal{S}\to\mathbb{R}$ to denote the value function at step $h$ under policy $\mu$ and $\nu$, so that $V^{\mu,\nu}_{h}(s)$ gives the expected cumulative rewards received under policy $\mu$ and $\nu$, starting from $s$ at step $h$:

We also define $Q^{\mu,\nu}_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\to\mathbb{R}$ to denote $Q$-value function at step $h$ so that $Q^{\mu,\nu}_{h}(s,a,b)$ gives the cumulative rewards received under policy $\mu$ and $\nu$, starting from $(s,a,b)$ at step $h$:

For simplicity, we use notation of operator $\mathbb{P}_{h}$ so that $[\mathbb{P}_{h}V](s,a,b)\mathrel{\mathop{:}}=\mathbb{E}_{s^{\prime}\sim\mathbb{P}_{h}(\cdot|s,a,b)}V(s^{\prime})$ for any value function $V$. We also use notation $[\mathbb{D}_{\pi}Q](s)\mathrel{\mathop{:}}=\mathbb{E}_{(a,b)\sim\pi(\cdot,\cdot|s)}Q(s,a,b)$ for any action-value function $Q$. By definition of value functions, we have the Bellman equation

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$. We define $V^{\mu,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}_{H+1}$.

For any Markov policy of the max-player $\mu$, there exists a best response of the min-player, which is a Markov policy $\nu^{\dagger}(\mu)$ satisfying $V_{h}^{\mu,\nu^{\dagger}(\mu)}(s)=\inf_{\nu}V_{h}^{\mu,\nu}(s)$ for any $(s,h)\in\mathcal{S}\times[H]$. Here the infimum is taken over all possible policies which are not necessarily Markovian (we will define later in this section). We define $V_{h}^{\mu,\dagger}\mathrel{\mathop{:}}=V_{h}^{\mu,\nu^{\dagger}(\mu)}$. By symmetry, we can also define $\mu^{\dagger}(\nu)$ and $V_{h}^{\dagger,\nu}$. It is further known (cf. [9]) that there exist Markov policies $\mu^{\star}$, $\nu^{\star}$ that are optimal against the best responses of the opponents, in the sense that

We call these optimal strategies $(\mu^{\star},\nu^{\star})$ the Nash equilibrium of the Markov game, which satisfies the following minimax equation: ²²2The minimax theorem here is different from the one for matrix games, i.e. $\max_{\phi}\min_{\psi}\phi^{\top}A\psi=\min_{\psi}\max_{\phi}\phi^{\top}A\psi$ for any matrix $A$, since here $V^{\mu,\nu}_{h}(s)$ is in general not bilinear in $\mu,\nu$.

Intuitively, a Nash equilibrium gives a solution in which no player has anything to gain by changing only her own policy. We further abbreviate the values of Nash equilibrium $V_{h}^{\mu^{\star},\nu^{\star}}$ and $Q_{h}^{\mu^{\star},\nu^{\star}}$ as $V_{h}^{{\star}}$ and $Q_{h}^{{\star}}$. We refer readers to Appendix A for Bellman optimality equations for values of best responses or Nash equilibria.

In certain situations, it is beneficial to consider general, history-dependent policies that are not necessarily Markovian. A (general) policy $\mu$ of the max-player is a set of $H$ maps $\mu\mathrel{\mathop{:}}=\big{\{}\mu_{h}:\mathbb{R}\times(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times\mathbb{R})^{h-1}\times\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\big{\}}_{h\in[H]}$, from a random number $z\in\mathbb{R}$ and a history of length $h$—say $(s_{1},a_{1},b_{1},r_{1},\cdots,s_{h})$, to a distribution over actions in $\mathcal{A}$. By symmetry, we can also define the (general) policy $\nu$ of the min-player, by replacing the action set $\mathcal{A}$ in the definition by set $\mathcal{B}$. The random number $z$ is sampled from some underlying distribution $\mathcal{D}$, but may be shared among all steps $h\in[H]$.

For a pair of general policy $(\mu,\nu)$, we can still use the same definitions (1) to define their value $V_{1}^{\mu,\nu}(s_{1})$ at step $1$. We can also define the best response $\nu^{\dagger}(\mu)$ of a general policy $\mu$ as the minimizing policy so that $V_{1}^{\mu,\dagger}(s_{1})\equiv V_{1}^{\mu,\nu^{\dagger}(\mu)}(s_{1})=\inf_{\nu}V_{h}^{\mu,\nu}(s_{1})$ at step 1. We remark that the best response of a general policy is not necessarily Markovian.

There are two possible learning objectives in the setting of Markov games. The first one is to find the best response for a fixed opponent. Without loss of generality, we consider the case where the learning agent is the max-player, and the min-player is the opponent.

The second goal is to find a Nash equilibrium of the Markov games. We measure the suboptimality of any pair of general policies $(\hat{\mu},\hat{\nu})$ using the gap between their performance and the performance of the optimal strategy (i.e. Nash equilibrium) when playing against the best responses respectively:

Loosely speaking, Nash equilibria can be viewed as “the best responses to the best responses”. In most applications, they are the ultimate solutions to the games. In Section 3 and 4, we present sharp guarantees for learning an approximate Nash equilibrium with near-optimal sample complexity. However, rather surprisingly, learning a best response in the worst case is more challenging than learning the Nash equilibrium. In Section 5, we present a computational hardness result for learning an approximate best response.

Our algorithm Optimistic Nash Q-learning (Algorithm 1) is an optimistic variant of Nash Q-learning [11]. For each step in each episode, it (a) takes actions according to the previously computed policy $\pi_{h}$, and observes the reward and next state, (b) performs incremental updates on Q-values, and (c) computes new greedy policies and updates $V$-values. Part (a) is straightforward; we now focus on explaining part (b) and part (c).

In part (b), the incremental updates on Q-values (Line 8, 9) are almost the same as standard Q-learning [34], except here we maintain two separate Q-values—$\overline{Q}_{h}$ and $\underline{Q}_{h}$, as upper and lower confidence versions respectively. We add and subtract a bonus term $\beta_{t}$ in the corresponding updates, which depends on $t=N_{h}(s_{h},a_{h},b_{h})$—the number of times $(s_{h},a_{h},b_{h})$ has been visited at step $h$. We pick parameter $\alpha_{t}$ and $\beta_{t}$ as follows for some large constant $c$ , and log factors $\iota$:

In part (c), our greedy policies are computed using a Coarse Correlated Equilibrium (CCE) subroutine, which is first introduced by [36] to solve Markov games using value iteration algorithms. For any pair of matrices $\overline{Q},\underline{Q}\in[0,H]^{A\times B}$, $\textsc{CCE}(\overline{Q},\underline{Q})$ returns a distribution $\pi\in\Delta_{\mathcal{A}\times\mathcal{B}}$ such that

It can be shown that a CCE always exists, and it can be computed by linear programming in polynomial time (see Appendix B for more details).

Now we are ready to state an intermediate guarantee for optimistic Nash Q-learning. We assume the algorithm has played the game for $K$ episodes, and we use $V^{k},Q^{k},N^{k},\pi^{k}$ to denote values, visitation counts, and policies at the beginning of the $k$-th episode in Algorithm 1.

Lemma 3 makes two statements. First, it claims that the $\overline{V}_{h}^{k}(s)$ and $\underline{V}_{h}^{k}(s)$ computed in Algorithm 1 are indeed upper and lower bounds of the value of the Nash equilibrium. Second, Lemma 3 claims that the averages of the upper bounds and the lower bounds are also very close to the value of Nash equilibrium $V_{1}^{\star}(s_{1})$, where the gap decrease as $1/\sqrt{K}$. This implies that in order to learn the value $V_{1}^{\star}(s_{1})$ up to $\epsilon$-accuracy, we only need $\mathcal{O}(H^{5}SAB\iota/\epsilon^{2})$ episodes.

However, Lemma 3 has a significant drawback: it only guarantees the learning of the value of Nash equilibrium. It does not imply that the policies $(\mu^{k},\nu^{k})$ used in Algorithm 1 are close to the Nash equilibrium, which requires the policies to have a near-optimal performance even against their best responses. This is a major difference between Markov games and standard MDPs, and is the reason why standard techniques from the MDP literature does not apply here. To resolve this problem, we propose a novel way to extract a certified policy from the optimistic Nash Q-learning algorithm.

We describe our procedure of executing the certified policy $\hat{\mu}$ of the max-player is described in Algorithm 2. Above, $\mu^{k}_{h},\nu^{k}_{h}$ denote the marginal distributions of $\pi^{k}_{h}$ produced in Algorithm 1 over action set $\mathcal{A},\mathcal{B}$ respectively. We also introduce the following quantities that directly induced by $\alpha_{t}$:

whose properties are listed in the following Lemma 11. Especially, $\sum_{i=1}^{t}\alpha_{t}^{i}=1$, so $\{\alpha_{t}^{i}\}_{i=1}^{t}$ defines a distribution over $[t]$. We use $k^{m}_{h}(s,a,b)$ to denote the index of the episode where $(s,a,b)$ is observed in step $h$ for the $m$-th time. The certified policy $\hat{\nu}$ of the min-player is easily defined by symmetry. We note that $\hat{\mu},\hat{\nu}$ are clearly general policies, but they are no longer Markov policies.

The intuitive reason why such policy $\hat{\mu}$ defined in Algorithm 2 is certified by Nash Q-learning algorithm, is because the update equation in line 8 of Algorithm 1 and equation (5) gives relation:

This certifies the good performance against the best responses if the max-player plays a mixture of policies $\{\mu_{h+1}^{k_{h}^{i}(s,a,b)}\}_{i=1}^{t}$ at step $h+1$ with mixing weights $\{\alpha_{t}^{i}\}_{i=1}^{t}$ (see Appendix C.2 for more details). A recursion of this argument leads to the certified policy $\hat{\mu}$—a nested mixture of policies.

We now present our main result for Nash Q-learning, using the certified policies $(\hat{\mu},\hat{\nu})$.

Theorem 4 asserts that if we run the optimistic Nash Q-learning algorithm for more than $\mathcal{O}(H^{5}SAB\iota/\epsilon^{2})$ episodes, the certified policies $(\hat{\mu},\hat{\nu})$ extracted using Algorithm 2 will be $\epsilon$-approximate Nash equilibrium (Definition 2).

We make two remarks. First, the executions of the certified policies $\hat{\mu},\hat{\nu}$ require the storage of $\{\mu^{k}_{h}\}$ and $\{\nu^{k}_{h}\}$ for all $k,h\in[H]\times[K]$. This makes the space complexity of our algorithm scales up linearly in the total number of episodes $K$. Second, Q-learning style algorithms (especially online updates) are crucial in our analysis for achieving sample complexity linear in $S$. They enjoy the property that every sample is only been used once, on the value function that is independent of this sample. In contrast, value iteration type algorithms do not enjoy such an independence property, which is why the best existing sample complexity scales as $S^{2}$ [2]. ³³3Despite [1] provides techniques to improve the sample complexity from $S^{2}$ to $S$ for value iteration in MDP, the same techniques can not be applied to Markov games due to the unique challenge that, in Markov games, we aim at finding policies that are good against their best responses.

Nash V-learning combines the idea of Follow-The-Regularized-Leader (FTRL) in the bandit literature with the Q-learning algorithm in reinforcement learning. This algorithm does not require extra information exchange between players other than standard game playing, thus can be ran separately by the two players. We describe the max-player version in Algorithm 3. See Algorithm 7 in Appendix D for the min-player version, where $\underline{V}_{h}$, $\underline{L}_{h}$, $\nu_{h}$, $\underline{\eta}_{t}$ and $\underline{\beta}_{t}$ are defined symmetrically.

For each step in each episode, the algorithm (a) first takes action according to $\mu_{h}$, observes the action of the opponent, the reward, and the next state, (b) performs an incremental update on $\overline{V}$, and (c) updates policy $\mu_{h}$. The first two parts are very similar to Nash Q-learning. In the third part, the agent first computes $\overline{\ell}_{h}(s_{h},\cdot)$ as the importance weighted estimator of the current loss. She then computes the weighted cumulative loss $\overline{L}_{h}(s_{h},\cdot)$. Finally, the policy $\mu_{h}$ is updated using FTRL principle:

Here $\mu_{0}$ is the uniform distribution over all actions $\mathcal{A}$. Solving above minimization problem gives the update equation as in Line 12 in Algorithm 3. In multi-arm bandit, FTRL can defend against adversarial losses, with regret independent of the number of the opponent’s actions. This property turns out to be crucial for Nash V-learning to achieve sharper sample complexity than Nash Q-learning (see the analog of Lemma 3 in Lemma 15).

Similar to Nash Q-learning, we also propose a new algorithm (Algorithm 4) to extract a certified policy from the optimistic Nash V-learning algorithm. The certified policies are again non-Markovian. We choose all hyperparameters as follows, for some large constant $c$ , and log factors $\iota$.

We now present our main result on the sample complexity of Nash V-learning.

Theorem 4 claims that if we run the optimistic Nash V-learning for more than $\mathcal{O}(H^{6}S(A+B)\iota/\epsilon^{2})$ episodes, the certified policies $(\hat{\mu},\hat{\nu})$ extracted from Algorithm 4 will be $\epsilon$-approximate Nash (Definition 2). Nash V-learning is the first algorithm of which the sample complexity matches the information theoretical lower bound $\Omega(H^{3}S(A+B)/\epsilon^{2})$ up to $\mathrm{poly}(H)$ factors and logarithmic terms.