Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity

Introduction

Recent years have witnessed numerous successes of reinforcement learning (RL) in many applications, e.g., playing strategy games (OpenAI, 2018; Vinyals et al., 2019), playing the game of Go (Silver et al., 2016, 2017), autonomous driving (Shalev-Shwartz et al., 2016), and security (Nguyen and Reddi, 2019; Zhang et al., 2019b). Most of these successful applications involve more than one decision-maker, giving birth to the surging interests and efforts in studying multi-agent RL (MARL) recently, especially on the theoretical side (Wei et al., 2017; Zhang et al., 2018a; Sidford et al., 2020; Zhang et al., 2019a; Xie et al., 2020; Shah et al., 2020; Bai and Jin, 2020; Bai et al., 2020). See also comprehensive surveys on MARL in Busoniu et al. (2008); Zhang et al. (2021a); Nguyen et al. (2020).

In general MARL, all agents affect both the state transition and the rewards of each other, while each agent may possess different, sometimes even totally conflicting objectives. Without knowledge of the model, the agents have to resort to data to either estimate the model, improve their own policy, and/or infer other agents’ policies. One fundamental challenge in MARL is the emergence of non-stationarity during the learning process (Busoniu et al., 2008; Zhang et al., 2021a): when multiple agents improve their policies concurrently and directly using samples, the environment becomes non-stationary from each agent’s perspective. This has posed great challenge to development of effective MARL algorithms based on single-agent ones, especially model-free ones, as the condition for guaranteeing convergence in the latter fails to hold in MARL. One tempting remedy for this non-stationarity issue is the simple while intuitive method — model-basedNote that we here follow the convention of model-based approach in the generative model setting (Azar et al., 2013; Agarwal et al., 2019a; Li et al., 2020), which separates these two stages explicitly. In general, model-based RL approaches do not have to separate the two stages, see e.g., Bayesian RL (Poupart et al., 2006; Ghavamzadeh et al., 2015), and model-based RL in online exploration settings (Azar et al., 2017; Bai and Jin, 2020). MARL: one first estimates an empirical model using data, and then finds the optimal, more specifically, equilibrium policies in this empirical model, via planning. Model-based MARL naturally decouples the learning and planning phases, and can be incorporated with any black-box planning algorithm that is efficient, e.g., value iteration (Shapley, 1953) and (generalized) policy iteration (Patek, 1997; Pérolat et al., 2015). More importantly, after estimating the model, this approach can potentially handle more than one MARL tasks with different reward functions but a common transition model, without re-sampling the data. Being able to handle this reward-agnostic case greatly expands the power of such a model-based approach.

Though intuitive and widely-used, rigorous theoretical justifications for these model-based MARL methods are relatively rare. In this work, our goal is to answer the following standing question: how good is the performance of this naïve “plug-in” method in terms of non-asymptotic sample complexity? To this end, we focus on arguably the most basic MARL setting since Littman (1994): two-player discounted zero-sum Markov games (MGs) with simultaneous-move agents, given only access to a generative model. This generative model allows agents to sample the MG, and query the next state from the transition process, given any state-action pair as input. The generative model setting has been a benchmark in RL when studying the sample efficiency of algorithms (Kearns and Singh, 1999; Kakade, 2003; Azar et al., 2013; Sidford et al., 2018; Agarwal et al., 2019a). Indeed, this model allows for the study of sample-based multi-agent planning over a long horizon, and helps develop better understanding of the statistical properties of the algorithms, decoupled from the exploration complexity.

Motivated by recent minimax optimal complexity results for single-agent model-based RL (Agarwal et al., 2019a), we address the question above with a positive answer: the model-based MARL approach can achieve near-minimax optimal sample complexity — in terms of dependencies on the size of the state space, the horizon, and the desired accuracy — for finding both the Nash equilibrium (NE) value and the NE policies. We also provide a separation in the achievable sample complexity, unique to the multi-agent setting, where, with regards to the dependencies on the number of actions, the naïve model-based approach is sub-optimal. A detailed description is provided next.

We establish the sample complexities of model-based MARL in zero-sum discounted Markov games, when a generative model is available. First, observing that the sampling process in this setting is agnostic to the reward function, we distinguish between two algorithmic frameworks: reward-aware and reward-agnostic cases, depending on whether the reward is revealed before or after the sampling. The model-based approach can inherently handle both cases, especially the latter case with multiple reward functions, without re-sampling the data. Second, by establishing lower bounds for both cases, we show that there is indeed a separation in sample complexity, which is unique in the multi-agent setting. Third, we show that up to some logarithmic factors, the model-based approach is indeed minimax optimal in all parameters in the more challenging reward-agnostic case, and has only a gap on the $|\mathcal{A}|,|\mathcal{B}|$ (both agents’ action space size) dependence in the reward-aware case. This separation and the (near-)minimax results have not only justified the sample efficiency of this simple approach, but also highlighted both its power (easily handling multiple reward functions known in hindsight) and its limitation (less adaptive and can hardly achieve optimal complexity with reward knowledge), particularly arising in the multi-agent RL context. These results are first-of-their-kind in model-based MARL, and among the first (near-)minimax results in general MARL, to the best of our knowledge. We also believe that this separation may shed some light on the choice of model-free and model-based approaches in various MARL scenarios in practice, and provide new understandings for algorithm-design in other MARL settings, e.g., with no generative model, and going beyond two-player zero-sum MGs.

Related Work.

Stemming from the formative work Littman (1994), MARL has been mostly studied under the framework of Markov games (Shapley, 1953). There has been no shortage of provably convergent MARL algorithms ever since then (Littman, 2001; Hu and Wellman, 2003; Greenwald et al., 2003). However, most of these early results are Q-learning-based (thus model-free) and asymptotic, with no sample complexity guarantees. To establish non-asymptotic results, Pérolat et al. (2015, 2016a, 2016b); Fan et al. (2019); Zhang et al. (2018b) have studied the sample complexity of batch model-free MARL methods. There are also increasing interests in policy-based (thus also model-free) methods for solving special MGs with non-asymptotic convergence guarantees (Pérolat et al., 2018; Srinivasan et al., 2018; Zhang et al., 2019a). No result on the (near-)minimax optimality of these complexities has been established prior to the present work.

Specific to the two-player zero-sum setting, Jia et al. (2019) and Sidford et al. (2020) have considered turn-based MGs, a special case of the simultaneous-move MGs considered here, with a generative model. Specifically, Sidford et al. (2020) established near-optimal sample complexity of $\widetilde{\mathcal{O}}((1-\gamma)^{-3}\epsilon^{-2})$ for a variant of Q-learning for this setting. More recently, Bai and Jin (2020); Xie et al. (2020) have established both regret and sample complexity guarantees for episodic zero-sum MGs, without a generative model, with focus on efficient exploration. The work in Shah et al. (2020) also focused on the turn-based setting, and combined Monte-Carlo Tree Search and supervised learning to find the NE values. In contrast, model-based MARL theory has relatively limited literature. Brafman and Tennenholtz (2002) proposed the R-MAX algorithm for average-reward MGs, with polynomial sample complexity. Wei et al. (2017) developed a model-based upper confidence algorithm with polynomial sample complexities for the same setting. These methods differ from ours, as they are either specific model-free approaches, or not clear yet if they are (near-)minimax optimal in the corresponding setups. Concurrent to our work, Bai et al. (2020) developed model-free algorithms with near-optimal sample complexities in episodic settings without a generative model. The results are optimal in $|{\mathcal{S}}|,|\mathcal{A}|,|\mathcal{B}|$ dependence, but not in the horizon $H$. Finally, we note that MARL in Markov games is not restricted to the competitive setting of two-player zero-sum, and the studies in (multi-player) cooperative/potential settings (Leonardos et al., 2021; Zhang et al., 2021b; Ding et al., 2022; Sayin et al., 2022) and general-sum settings (Hu and Wellman, 2003; Liu et al., 2021; Jin et al., 2021; Mao et al., 2022; Mao and Başar, 2023) also exist, and is not the focus of the present paper.

In the single-agent regime, there has been extensive literature on non-asymptotic efficiency of RL in MDPs; see Kearns and Singh (1999); Kakade (2003); Strehl et al. (2009); Jaksch et al. (2010); Azar et al. (2013); Osband and Van Roy (2014); Dann and Brunskill (2015); Azar et al. (2017); Wang (2017); Sidford et al. (2018); Jin et al. (2018); Li et al. (2020). Amongst them, we highlight the minimax optimal ones: Azar et al. (2013) and Azar et al. (2017) have provided minimax optimal results for sample complexity and regret in the settings with and without a generative model, respectively. Specifically, Azar et al. (2013) has shown that to achieve the $\epsilon$-optimal value in Markov decision processes (MDPs), at least $\widetilde{\Omega}(|{\mathcal{S}}||\mathcal{A}|(1-\gamma)^{-3}\epsilon^{-2})$ samples are needed, for $\epsilon\in(0,1]$. They also showed that to find an $\epsilon$-optimal policy, the same minimax complexity order in $1-\gamma$ and $\epsilon$ can be attained, if $\epsilon\in(0,(1-\gamma)^{-1/2}|{\mathcal{S}}|^{-1/2}]$ and the total sample complexity is $\widetilde{\mathcal{O}}(|{\mathcal{S}}|^{2}|\mathcal{A}|)$, which is in fact linear in the model size. Later, Sidford et al. (2018) has proposed a Q-learning based approach to attain this lower bound and remove the extra dependence on $|{\mathcal{S}}|$, for $\epsilon\in(0,1]$. More recently, Agarwal et al. (2019a) developed new techniques based on absorbing MDPs, to show that model-based RL also achieves the lower bound for finding an $\epsilon$-optimal policy, with a larger $\epsilon$ range of $(0,(1-\gamma)^{-1/2}]$While preparing the present work, Li et al. (2020) has further improved the minimax optimal results in Agarwal et al. (2019a), in that they cover the entire range of sample sizes. We believe the improvement can also be incorporated in the MARL setting here, which is left as our future work.. Finally, our separation of the reward-agnostic case is motivated by the recent novel framework of reward-free RL in Jin et al. (2020).

Preliminaries

Consider a zero-sum MGWe will hereafter refer to this model simply as a MG. $\mathcal{G}$ characterized by $({\mathcal{S}},\mathcal{A},\mathcal{B},P,r,\gamma)$, where ${\mathcal{S}}$ is the state space; $\mathcal{A},\mathcal{B}$ are the action spaces of agents $1$ and $2$, respectively; $P:{\mathcal{S}}\times\mathcal{A}\times\mathcal{B}\to\Delta({\mathcal{S}})$ denotes the transition probability of states; $r:{\mathcal{S}}\times\mathcal{A}\times\mathcal{B}\to$ denotes the reward functionOur results can be generalized to other ranges of reward function by a standard reduction, see e.g., Sidford et al. (2018), and randomized reward functions. of agent $1$ (thus $-r$ is the bounded reward function of agent $2$); and $\gamma\in[0,1)$ is the discount factor. The goal of agent $1$ (agent $2$) is to maximize (minimize) the long-term accumulative discounted reward. In MARL, the agents aim to achieve this goal using data samples collected from the model.

At each time $t$, agent $1$ (agent $2$) has a stationary (not necessarily deterministic) policy $\mu:{\mathcal{S}}\to\Delta(\mathcal{A})$ ($\nu:{\mathcal{S}}\to\Delta(\mathcal{B})$), where $\Delta(\mathcal{X})$ denotes the space of all probability measures over $\mathcal{X}$, so that $a_{t}\sim\mu(\cdot{\,|\,}s_{t})$ ($b_{t}\sim\nu(\cdot{\,|\,}s_{t})$). The state makes a transition from $s_{t}$ to $s_{t+1}$ following the probability distribution $P(\cdot{\,|\,}s_{t},a_{t},b_{t})$, given $(a_{t},b_{t})$. As in the MDP model, one can define the state-value function under a pair of joint policies $(\mu,\nu)$ as

Note that $V^{\mu,\nu}(s)\in[0,1/(1-\gamma)]$ for any $s\in{\mathcal{S}}$ as $r\in$, and the expectation is taken over the random trajectory produced by the joint policy $(\mu,\nu)$. Also, the state-action/Q-value function under $(\mu,\nu)$ is defined by

The solution concept considered is the (approximate) Nash equilibrium, as defined below.

For a zero-sum MG $({\mathcal{S}},\mathcal{A},\mathcal{B},P,r,\gamma)$, a Nash equilibrium policy pair $(\mu^{*},\nu^{*})$ satisfies the following pair of inequalitiesIn game theory, this pair is commonly referred to as saddle-point inequalities. for any $s\in{\mathcal{S}}$, $\mu\in\Delta(\mathcal{A})^{|{\mathcal{S}}|}$, and $\nu\in\Delta(\mathcal{B})^{|{\mathcal{S}}|}$

If (1) holds with some $\epsilon>0$ relaxation, i.e., for some policy $(\mu^{\prime},\nu^{\prime})$, such that

then $(\mu^{\prime},\nu^{\prime})$ is an $\epsilon$-Nash equilibrium policy pair.

By Shapley (1953); Patek (1997), there exists a Nash equilibrium policy pair $(\mu^{*},\nu^{*})\in\Delta(\mathcal{A})^{|{\mathcal{S}}|}\times\Delta(\mathcal{B})^{|{\mathcal{S}}|}$ for two-player discounted zero-sum MGs. The state-value $V^{*}:=V^{\mu^{*},\nu^{*}}$ is referred to as the value of the game. The corresponding Q-value function is denoted by $Q^{*}$. The objective of the two agents is to find the NE policy of the MG, namely, to solve the saddle-point problem

for every $s\in{\mathcal{S}}$, where the order of $\max$ and $\min$ can be interchanged (Von Neumann et al., 1953; Shapley, 1953). For notational convenience, for any policy $(\mu,\nu)$, we define

and denote the corresponding optimizers by $\nu(\mu)$ and $\mu(\nu)$, respectively. We refer to these values and optimizers as the best-response values and policies, given $\mu$ and $\nu$, respectively.

Reward-Aware v.s. Reward-Agnostic.

We first differentiate between two algorithmic mechanisms in the generative-model setting. In the reward-aware case, the reward function is either known to the agents (Azar et al., 2013; Sidford et al., 2018; Agarwal et al., 2019a; Sidford et al., 2020; Li et al., 2020), or can at least be estimated from data. The reward knowledge can thus be used to potentially guide the sampling process, making the algorithm adaptive. In the reward-agnostic case, reward knowledge is not used to guide sampling, and is possibly only revealed after the sampling. This especially fits in the scenario when there is more than one reward function of interest, or when the reward function is engineered iteratively, since it can now handle a class of reward functions that are not pre-specified, without re-sampling the data for each of them. Existing works in single-agent settings have no such a separation (Azar et al., 2013; Sidford et al., 2018; Agarwal et al., 2019b; Li et al., 2020), as the sample complexity of estimating the reward function is typically of lower order, and the reward function is thus assumed to be known. In particular, the model-based approaches in Azar et al. (2013); Agarwal et al. (2019b); Li et al. (2020) are reward-agnostic, while the model-free approaches in Sidford et al. (2018, 2020) are reward-aware. Interestingly, in two-agent Markov games, whether the reward is known beforehand or not may lead to different sample complexity lower-bounds, as we will see in §3.1. We thus point out this separation here for clarity.

The reward-agnostic case we advocate here is closely related to the recent novel algorithmic framework of reward-free RL (Jin et al., 2020), where there are also two phases, exploration and planning, while trajectories are only collected in the exploration phase, without any reward knowledge, and various reward functions are fed to the algorithm for evaluation in the planning phase. One key difference is that the reward-free setting aims to be effective for all reward function in the planning phase simultaneously, while the reward-agnostic setting only focuses on handling the underlying single-reward (or a few, e.g., polynomial number of, reward functions) that is not pre-specified. Being less general than the pure reward-free setting, the sample complexity bounds are thus possibly better, as we will show in §3.

Model-Based Approach with Generative Model.

As a standard setting, suppose that we have access to a generative model/sampler, which can provide us with samples $s^{\prime}\sim P(\cdot{\,|\,}s,a,b)$ for any $(s,a,b)$. The model-based MARL algorithm simply calls the sampler $N$ times at each state-joint-action pair $(s,a,b)$, and constructs an empirical estimate of the transition model $P$, denoted by $\widehat{P}$, following

Here $\text{count}(s^{\prime},s,a,b)$ is the number of times the state-action pair $(s,a,b)$ forces a transition to state $s^{\prime}$. Note that the reward function is not estimated, in either the reward-aware or reward-agnostic cases, as for the former, the sample complexity of estimating $r$ is only a lower order term, and $r$ is thus typically assumed to be known (Azar et al., 2013; Sidford et al., 2018; Agarwal et al., 2019a; Li et al., 2020); while for the latter, no reward information is even available in the sampling processes. This model-based approach via estimating $P$ inherently handles both cases. Such a model-estimation can be implemented by both agents independently.

Planning Oracle.

The reward function, together with the empirical transition model $\widehat{P}$ and the components $({\mathcal{S}},\mathcal{A},\mathcal{B},\gamma)$ in the true model $\mathcal{G}$, constitutes an empirical game model $\widehat{\mathcal{G}}$. As in Azar et al. (2013); Agarwal et al. (2019a); Jin et al. (2020); Li et al. (2020) for single-agent RL, we assume that an efficient planning oracle is available, which takes $\widehat{\mathcal{G}}$ as input, and outputs a policy pair $(\widehat{\mu},\widehat{\nu})$. This oracle decouples the statistical and computational aspects of the empirical model $\widehat{\mathcal{G}}$. The output policy pair, referred to as being near-equilibrium, is assumed to satisfy certain $\epsilon_{opt}$-order of equilibrium, in terms of value functions, and we evaluate the performance of $(\widehat{\mu},\widehat{\nu})$ on the original MG $\mathcal{G}$. Common planning algorithms include value iteration (Shapley, 1953) and (generalized) policy iteration (Patek, 1997; Pérolat et al., 2015), which are efficient in finding the ($\epsilon$-)NE of $\widehat{\mathcal{G}}$. In addition, it is not hard to have an oracle that is smooth in generating policies, i.e., the change of the approximate NE policies can be bounded by the changes of the NE value. See our Definition 7 later for a formal statement. Finally, we note that our definition of model-based approach in the generative-model-setting follows from that in (Azar et al., 2013; Agarwal et al., 2019a; Li et al., 2020), which separates these two stages explicitly. In general, model-based RL approaches do not have to separate the two stages, see e.g., Bayesian RL (Ghavamzadeh et al., 2015), and model-based RL in online exploration settings (Azar et al., 2017; Bai and Jin, 2020).

Main Results

We now introduce the main results of this paper. For notational convenience, we use $\widehat{V}^{\mu,\nu}$, $\widehat{V}^{\mu,*}$, $\widehat{V}^{*,\nu}$, and $\widehat{V}^{*}$ to denote the value under $(\mu,\nu)$, the best-response value under $\mu$ and $\nu$, and the NE value, under the empirical game model $\widehat{\mathcal{G}}$, respectively. A similar convention is also used for Q-functions.

We first establish lower bounds on both approximating the NE value function and learning the $\epsilon$-NE policy pair, in both reward-aware and reward-agnostic cases.

Let $\mathcal{G}$ be an unknown zero-sum MG, and the agents learn in a reward-aware case, i.e., the reward knowledge is available during sampling. Then, there exist $\epsilon_{0},\delta_{0}>0$, such that for all $\epsilon\in(0,\epsilon_{0})$, $\delta\in(0,\delta_{0})$, the sample complexity of learning an $\epsilon$-NE policy pair, or an $\epsilon$-approximate NE value, i.e., finding a $\widehat{Q}$ such that $\|\widehat{Q}-Q^{*}\|_{\infty}\leq\epsilon$ for $\mathcal{G}$, with a generative model with probability at least $1-\delta$, is \widetilde{\Omega}\big{(}{|{\mathcal{S}}|(|\mathcal{A}|+|\mathcal{B}|)}{(1-\gamma)^{-3}\epsilon^{-2}}\log({1}/{\delta})\big{)}.

The proof of Lemma 3, via a straightforward adaptation from the lower bounds for MDPs (Azar et al., 2013; Feng et al., 2019), is provided in §A.1. In particular, one can design a two-player zero-sum Markov game such that one of the players is dummy – she has no control on the reward nor the transition dynamics. Then, the existing lower bound in Azar et al. (2013); Feng et al. (2019) for MDPs leads to the desired result. Note that as in Azar et al. (2013); Sidford et al. (2018, 2020); Agarwal et al. (2019a); Li et al. (2020), the reward function is known in this case. As we will show momentarily, our sample complexity is tight in $1-\gamma$ and $|{\mathcal{S}}|$, while has a gap in $|\mathcal{A}|,|\mathcal{B}|$ dependence ($\widetilde{\mathcal{O}}(|\mathcal{A}||\mathcal{B}|)$ versus $\widetilde{\Omega}(|\mathcal{A}|+|\mathcal{B}|)$). In §A.1, we discuss that the $\widetilde{\Omega}(|\mathcal{A}|+|\mathcal{B}|)$ lower bound may not be improved in this reward-aware case, and might be attainable by model-free algorithms instead (as $\widetilde{\mathcal{O}}(|\mathcal{A}||\mathcal{B}|)$ is inherent in model-based approaches due to estimating $P$). Interestingly, in the concurrent work Bai et al. (2020), under a different MARL setting, such an $\widetilde{\Omega}(|\mathcal{A}|+|\mathcal{B}|)$ complexity is indeed shown to be attainable by a model-free algorithm with online updates.

On the other hand, note that our model-based approach can inherently also handle the more challenging reward-agnostic case. Indeed, estimating the transition model $P$ seems a bit of an overkill for the reward-aware case, in terms of sample complexity. A natural two-part question then becomes: what is the sample complexity lower bound in this more challenging reward-agnostic case, and can the model-based approach attain it? We formally answer the first part of the question in the following theorem, whose proof is deferred to §A.2, and answer the second part in §3.2 and §3.3.

Let $\mathcal{G}$ be an unknown zero-sum MG, and the agents learn in a reward-agnostic case, i.e., they first call the generative model for sampling, without reward knowledge, and then are fed with the reward function $r$ in $\mathcal{G}$, for finding either an $\epsilon$-NE policy pair, or an $\epsilon$-approximate NE value for $\mathcal{G}$. Then, there exist $\epsilon_{0},\delta_{0}>0$, such that for all $\epsilon\in(0,\epsilon_{0})$, $\delta\in(0,\delta_{0})$, the sample complexity of achieving either goal with probability at least $1-\delta$, is

Compared to Lemma 3, the dependence on $|\mathcal{A}|,|\mathcal{B}|$ is increased from $\widetilde{\Omega}(|\mathcal{A}|+|\mathcal{B}|)$ to $\widetilde{\Omega}(|\mathcal{A}||\mathcal{B}|)$. Several remarks are now in order. First, this suggests that without guidance from the reward, the reward-agnostic case can be more challenging to tackle. The intuition is that, when the reward is only given in hindsight, which might be chosen adversarially, costs the algorithm to at least sample at all $|\mathcal{A}||\mathcal{B}|$ elements in the Q-value $Q(s,\cdot,\cdot)$ at each state $s$ often enough. Second, when reduced to the single-agent setting (e.g., with $|\mathcal{B}|=1$), such a separation disappears, showing its unique emergence in the multi-agent setting, and explaining why these two cases were not differentiated explicitly in the single-agent literature. Third, this lower bound is also related to the reward-free setting (Jin et al., 2020) with a single unknown reward (not infinitely many as in Jin et al. (2020)).

The basic intuition regarding the separation between the lower bounds in reward-aware and reward-agnostic cases, when compared to the single-agent setting (where there is no such a separation), is the insensitivity of Nash equilibrium (NE) to the changes in payoff matrices in two-player zero-sum games (Jansen, 1981). In particular, NE in general depends on the joint behavior and preferences of both agents. Specifically, to construct the lower bound (even in the single-agent case, see e.g., Azar et al. (2013); Feng et al. (2019)), we needed to carefully perturb the Q-value function at each state-action pair of some null hypothesis instance, so that the solution (which is the maximum in the single-agent case, and Nash equilibrium in the multi-agent case) is also changed in the perturbed alternative hypothesis cases. Hence, for each alternative hypothesis case, we need to change the NE by only changing $\mathcal{O}(1)$ elements in the payoff matrix, i.e., the Q-value table. In the reward-aware setting, since the reward is known (or can be estimated accurately with negligible sample complexity), we can only perturb the transition matrix to perturb the Q-value table, which share the same size (i.e., the degree-of-freedom). Due to the insensitivity, we can hardly construct $\Theta(|\mathcal{A}||\mathcal{B}|)$ different hard cases (as needed to construct a $\Omega(|\mathcal{A}||\mathcal{B}|)$ lower bound) while by only perturbing $\mathcal{O}(1)$ elements in the transition matrix in each case. Note that such a perturbation can be effective in the single-agent MDP setting, as by only perturbing one element in the transition matrix, the maximum of the Q-value can be changed, see e.g., Azar et al. (2013); Feng et al. (2019).

In contrast, in the reward-agnostic setting, the reward information is given after the sampling phase and the estimation of the model. This way, more freedom is allowed to construct $\Theta(|\mathcal{A}||\mathcal{B}|)$ different hard cases, by adversarially choosing the reward function afterwards. In particular, the Q-value will be affected by both the transition matrix and the reward, and with polynomial number of reward functions, we were able to construct Q-value tables in $\Theta(|\mathcal{A}||\mathcal{B}|)$ different hard cases. Note that taking a union bound over the polynomial number of reward functions do not affect the total sample complexity, as it is still dominated by the sample complexity of estimating the transition matrix. In other words, the freedom of constructing and perturbing the reward functions adversarially afterwards forces the algorithm to estimate all the elements in the transition matrix well, in order to handle the reward-agnostic setting. This has been inherently done by our model-based approach. We defer more details about the lower bounds comparison in Appendix A.

2 Near-Optimality in Finding ϵitalic-ϵ\epsilon-Approximate NE Value

We now establish the near-minimax optimal sample complexities of model-based MARL. Note that theses results apply to both reward-aware and reward-agnostic cases, as the implementation of our model-based approach does not rely on the reward function. We start by showing the sample complexity to achieve an $\epsilon$-approximate NE value.

Suppose that the policy pair $(\widehat{\mu},\widehat{\nu})$ is obtained from the Planning Oracle using the empirical model $\widehat{\mathcal{G}}$, which satisfies

Then, for any $\delta\in(0,1]$ and $\epsilon\in(0,1/(1-\gamma)^{1/2}]$, if

for some absolute constant $c$, it holds that with probability at least $1-\delta$,

Theorem 5 shows that if the planning error $\epsilon_{opt}$ is made small, e.g., with the order of $\mathcal{O}((1-\gamma)\epsilon)$, then the Nash equilibrium Q-value can be estimated with a sample complexity of $\widetilde{\mathcal{O}}(|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|(1-\gamma)^{-3}\epsilon^{-2})$, as $N$ queries are made for each $(s,a,b)$ pair. This planning error can be achieved by performing any efficient black-box optimization technique over the empirical model $\widehat{\mathcal{G}}$. Examples of such oracles include value iteration (Shapley, 1953) and (generalized) policy iteration (Patek, 1997; Pérolat et al., 2015). Moreover, note that, in contrast to the single-agent setting, where only a $\max$ operator is used, a $\min\max$ (or $\max\min$) operator is used in these algorithms, which involves solving a matrix game at each state. This can be solved as a linear program (Osborne and Rubinstein, 1994), with at best polynomial runtime complexity (Grötschel et al., 1981; Karmarkar, 1984). This in total leads to an efficient polynomial runtime complexity algorithm.

As per Lemma 3, our $\widetilde{\mathcal{O}}(|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|(1-\gamma)^{-3}\epsilon^{-2})$ complexity is near-minimax optimal for the reward-aware case, in that it is tight in the dependence of $1-\gamma$ and $|{\mathcal{S}}|$, and sublinear in the model-size (which is $|{\mathcal{S}}|^{2}|\mathcal{A}||\mathcal{B}|$). However, there is a gap on the $|\mathcal{A}|,~{}|\mathcal{B}|$ dependence ($\widetilde{\mathcal{O}}(|\mathcal{A}||\mathcal{B}|)$ versus $\widetilde{\mathcal{O}}(|\mathcal{A}|+|\mathcal{B}|)$). Unfortunately, without further assumption on the MG, e.g., being turn-based, the model-based algorithm can hardly avoid the $\widetilde{\mathcal{O}}(|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|)$ dependence, as it is required to estimate each $\widehat{P}(\cdot{\,|\,}s,a,b)$ accurately to perform the planning. It is only minimax-optimal if the action-space size of one agent dominates the other’s (e.g., $|\mathcal{A}|\gg|\mathcal{B}|$).

In the reward-agnostic case, as per Theorem 4, $\widetilde{\mathcal{O}}(|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|(1-\gamma)^{-3}\epsilon^{-2})$ is indeed minimax-optimal, and is tight in all $|{\mathcal{S}}|,|\mathcal{A}|,|\mathcal{B}|$ and $1-\gamma$ dependence. More significantly, in this case, more than one reward functions can be handled simultaneously, as long as the transition model is estimated accurately enough. Specifically, with $M$ reward functions, by letting $\delta=\delta/M$ in Theorem 5 and using union bounds, the sample complexity of finding $\epsilon$-approximate NE value corresponding to all $M$ reward functions becomes $\widetilde{\mathcal{O}}(\log(M)|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|(1-\gamma)^{-3}\epsilon^{-2})$, which, with $M$ being polynomial in $|{\mathcal{S}}|,~{}|\mathcal{A}|,~{}|\mathcal{B}|$, is of the same order as that in Theorem 5.

However, this (near-)optimal result does not necessarily lead to near-optimal sample complexity for obtaining the $\epsilon$-NE policies. We first use a direct translation to obtain such an $\epsilon$-NE policy pair based on Theorem 5, for any Planning Oracle.

Let $(\widehat{\mu},\widehat{\nu})$ and $N$ satisfy the conditions in Theorem 5. Let

and $(\widetilde{\mu},\widetilde{\nu})$ be the one-step Nash equilibrium of $\widehat{Q}^{\widehat{\mu},\widehat{\nu}}$, namely, for any $s\in{\mathcal{S}}$

Then, with probability at least $1-\delta$,

namely, $(\widetilde{\mu},\widetilde{\nu})$ constitutes a $2\widetilde{\epsilon}$-Nash equilibrium policy pair.

Corollary 6 is equivalently to saying that the sample complexity of achieving an $\epsilon$-NE policy pair is $\widetilde{\mathcal{O}}((1-\gamma)^{-5}\epsilon^{-2})$. This is worse than the model-based single-agent setting (Agarwal et al., 2019a), and also worse than both the model-free single-agent (Sidford et al., 2018) and turn-based two-agent (Sidford et al., 2020) settings, where $\widetilde{\mathcal{O}}((1-\gamma)^{-3}\epsilon^{-2})$ can be achieved for learning the optimal policy. This also has a gap from the lower bound in both Lemma 3 and Theorem 4. Note that the above sample complexity still matches that of the Empirical QVI in Azar et al. (2013) if $\epsilon\in(0,1]$ for single-agent RL, but with a larger choice of $\epsilon$ of $(0,(1-\gamma)^{-1/2}]$. As the Markov game setting is more challenging than MDPs, it is not clear yet if the lower bounds in Lemma 3 and Theorem 4 in finding $\epsilon$-NE policies can be achieved, using a general Planning Oracle. In contrast, we show next that a stable Planning Oracle can indeed (almost) match the lower bounds.

3 Near-Optimality in Finding ϵitalic-ϵ\epsilon-NE Policy

Admittedly, Corollary 6 does not fully exploit the model-based approach, since it finds the NE policy according to the Q-value estimate $\widehat{Q}^{\widehat{\mu},\widehat{\nu}}$, instead of using the output policy pair $(\widehat{\mu},\widehat{\nu})$ directly. This loses a factor of $1-\gamma$. To improve the sample complexity of obtaining the NE policies, we first introduce the following definition of a smooth Planning Oracle.

A smooth Planning Oracle generates policies that are smooth with respect to the NE Q-values of the empirical model. Specifically, for two empirical models $\widehat{\mathcal{G}}_{1}$ and $\widehat{\mathcal{G}}_{2}$, the generated near-equilibrium policy pair $(\widehat{\mu}_{1},\widehat{\nu}_{1})$ and $(\widehat{\mu}_{2},\widehat{\nu}_{2})$ satisfy that for each $s\in{\mathcal{S}}$, $\|\widehat{\mu}_{1}(\cdot{\,|\,}s)-\widehat{\mu}_{2}(\cdot{\,|\,}s)\|_{TV}\leq C\cdot\|\widehat{Q}_{1}^{*}-\widehat{Q}_{2}^{*}\|_{\infty}$ and $\|\widehat{\nu}_{1}(\cdot{\,|\,}s)-\widehat{\nu}_{2}(\cdot{\,|\,}s)\|_{TV}\leq C\cdot\|\widehat{Q}_{1}^{*}-\widehat{Q}_{2}^{*}\|_{\infty}$ for some constantWe allow $C$ to depend polynomially on $|\mathcal{A}|,~{}|\mathcal{B}|$, which, as we will show later, does not affect the sample complexity as it appears as $\log C$. $C>0$, where $\widehat{Q}_{i}^{*}$ is the NE Q-value of $\widehat{\mathcal{G}}_{i}$ for $i=1,2$, and $\|\cdot\|_{TV}$ is the total variation distance.

Such a smooth Planning Oracle can be readily obtained in several ways. For example, one simple (but possibly computationally expensive) approach is to output the average over the entire policy space, using a softmax randomization over best-response values induced by $\widehat{Q}^{*}$. Specifically, for agent $1$, the output $\widehat{\mu}$ is given by

Another more tractable way to obtain $(\widehat{\mu},\widehat{\nu})$ is by directly solving a regularized matrix game induced by $\widehat{Q}^{*}$. Specifically, one solves

for each $s\in{\mathcal{S}}$, where $\Omega_{i}$ is the regularizer for agent $i$’s policy, usually a strongly convex function, $\tau_{i}>0$ are the temperature parameters. This strongly-convex-strongly-concave saddle point problem admits a unique solution, and can be solved efficiently (Facchinei and Pang, 2007; Cherukuri et al., 2017; Liang and Stokes, 2019). This regularization has been widely used in both single-agent MDPs (Neu et al., 2017; Haarnoja et al., 2018; Chow et al., 2018; Geist et al., 2019), and learning in games (Syrgkanis et al., 2015; Mertikopoulos and Sandholm, 2016; Grill et al., 2019), to improve both the exploration and convergence.

With small enough $\tau_{i}$ (with the order of $\mathcal{O}(\epsilon)$, see §B.1), the solution to (6) will be $\epsilon$-close to that of the unregularized one (Geist et al., 2019). More importantly, many commonly used regularizations, including negative entropy (Neu et al., 2017), Tsallis entropy (Chow et al., 2018) and Rényi entropy with certain parameters (Mertikopoulos and Sandholm, 2016), naturally yield a smooth Planning Oracle; see Lemma 24 in §B.1 for a formal statement. Note that the smoothness of the oracle does not affect the sample complexity of our model-based MARL algorithm.

Now we present another theorem, which gives the $\epsilon$-Nash equilibrium policy pair directly, with the (near-)minimax optimal sample complexity of $\widetilde{\mathcal{O}}(|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|(1-\gamma)^{-3}\epsilon^{-2})$.

Suppose that the policy pair $(\widehat{\mu},\widehat{\nu})$ is obtained from a smooth Planning Oracle using the empirical model $\widehat{\mathcal{G}}$ (see Definition 7), which satisfies

Then, for any $\delta\in(0,1]$ and $\epsilon\in(0,1/(1-\gamma)^{1/2}]$, if

for some absolute constant $c$, then, letting $\widetilde{\epsilon}:=\epsilon+{4\epsilon_{opt}}/({1-\gamma})$, with probability at least $1-\delta$,

namely, $(\widehat{\mu},\widehat{\nu})$ constitutes a $2\widetilde{\epsilon}$-Nash equilibrium policy pair.

Theorem 8 shows that the sample complexity of achieving an $\epsilon$-NE policy can be near-minimax optimal for the reward-aware case, and minimax-optimal for the reward-agnostic case, if a smooth Planning Oracle is used. The dependence on $|{\mathcal{S}}|$ and $1-\gamma$ also matches the only known near-optimal complexity in MGs in Sidford et al. (2020), with a turn-based setting and a model-free algorithm. Inherited from Agarwal et al. (2019a), this improves the second result in Azar et al. (2013) that also has $\widetilde{\mathcal{O}}((1-\gamma)^{-3}\epsilon^{-2})$ in finding an $\epsilon$-optimal policy, by removing the dependence on $|{\mathcal{S}}|^{-1/2}$ and enlarging the choice of $\epsilon$ from $(0,(1-\gamma)^{-1/2}|{\mathcal{S}}|^{-1/2}]$ to $(0,(1-\gamma)^{-1/2}]$, and removing a factor of $|{\mathcal{S}}|$ in the total sample complexity for any fixed $\epsilon$. In addition, Theorem 8 also applies to the multi-reward setting, as Theorem 5, by taking a union bound argument over all reward functions in the reward-agnostic case. If the number of reward functions $M$ is of order $\text{poly}(|{\mathcal{S}}|,|\mathcal{A}|,|\mathcal{B}|)$, the sample complexity of handling multiple reward functions has the same order as that in Theorem 8.

Theorems 5 and 8 together justify that, this simple model-based MARL algorithm is indeed sample-efficient, in approximating both the Nash equilibrium values and policies. Moreover, our separation of the reward-aware and reward-agnostic cases highlights both the power (easily handling multiple reward functions), and the limitation (less adaptive and can hardly achieve $\widetilde{\mathcal{O}}(|\mathcal{A}|+|\mathcal{B}|)$) of the model-based approach, particularly arising in the multi-agent RL context.

Proofs

We first introduce some additional notation for convenience.

Hence, the Q-value function can be written as

Then, we define $\Sigma_{\mathcal{G}}^{\mu,\nu}$ to be the variance of the discounted reward under the MG $\mathcal{G}$, i.e.,

It can be shown (see an almost identical formula for MDPs in (Azar et al., 2013, Lemma 6)) that $\Sigma_{\mathcal{G}}^{\mu,\nu}$ satisfies some Bellman-type equation for any policy pair $(\mu,\nu)$:

It can also be verified that $\|\Sigma_{\mathcal{G}}^{\mu,\nu}\|_{\infty}\leq\gamma^{2}/(1-\gamma)^{2}$ (Azar et al., 2013; Agarwal et al., 2019a). Before proceeding further, we provide a roadmap for the proof.

Proof Roadmap.

Our proof mainly consists of the following steps:

Helper lemmas and a crude bound. We first establish several important lemmas, including the component-wise error bounds for the final Q-value errors, the variance error bound, and a crude error bound that directly uses Hoeffding’s inequality. Some of the results are adapted from the single-agent setting to zero-sum MGs, see Agarwal et al. (2019a). See §4.1.

Establishing an auxiliary Markov game. To improve the crude bound, we build up an absorbing Markov game, in order to handle the statistical dependence between $\widehat{P}$ and some value function generated by $\widehat{P}$, which occurs as a product in the component-wise bound above. By carefully designing the auxiliary game, we establish a Bernstein-like concentration inequality, despite this dependency. See §4.2, more precisely, Lemmas 17 and 18.

Final bound for $\epsilon$-approximate NE value. Lemma 17 in Step 2 allows us to exploit the variance bound, see Lemma 11, to obtain an $\widetilde{\mathcal{O}}(\sqrt{1/[(1-\gamma)^{3}]N})$ order bound on the Q-value error, leading to a $\widetilde{\mathcal{O}}((1-\gamma)^{-3}\epsilon^{-2})$ near-minimax optimal sample complexity for achieving the $\epsilon$-approximate NE value. See §4.3.

Final bounds for $\epsilon$-NE policy. Based on the final bound in Step 3, we then establish a $\widetilde{\mathcal{O}}((1-\gamma)^{-5}\epsilon^{-2})$ sample complexity for obtaining an $\epsilon$-NE policy pair, by solving an additional matrix game over the output Q-value $\widehat{Q}^{\widehat{\mu},\widehat{\nu}}$. See §4.4. In addition, given a smooth Planning Oracle, by Lemma 18 in Step 2, and more careful self-bounding techniques, we establish a $\widetilde{\mathcal{O}}((1-\gamma)^{-3}\epsilon^{-2})$ sample complexity for achieving such an $\epsilon$-NE policy, directly using the output policies $(\widehat{\mu},\widehat{\nu})$. See §4.5.

1 Important Lemmas

We start with the component-wise error bounds.

For any policy pair $(\mu,\nu)$, it follows that

where we recall that $\nu(\mu)$ and $\mu(\nu)$ denote the best-response policy given $\mu$ and $\nu$, respectively (see (4)). Moreover, we have

Similar arguments yield the third inequality in the first argument.

which, combined with triangle inequality, yields the first inequality. Similarly, we have

Using triangle inequality proves the second inequality. For (10)-(11), we similarly have

Notice that for any $\mu\in\Delta(\mathcal{A})^{|{\mathcal{S}}|}$ and $\nu\in\Delta(\mathcal{B})^{|{\mathcal{S}}|}$,

Combining (12)-(13) and (14)-(15), together with triangle inequality, we arrive at (10)-(11), and complete the proof.

We establish the decomposition in (8)-(9) for the following intuition and reasons. The error in (8)-(9) contains three terms: the first and third terms $\|Q^{\mu,\nu}-\widehat{Q}^{\mu,\nu}\|_{\infty}$ and $\widehat{Q}^{*}\|_{\infty}-\|\widehat{Q}^{\mu^{*},*}-Q^{*}\|_{\infty}$ are the differences of the Q-value for some policy pairs in the true and estimated models, respectively, which will be handled later based on the statistical error of the model estimation; the second term $\|\widehat{Q}^{\mu,\nu}-\widehat{Q}^{*}\|_{\infty}$ is the optimization error we obtained from the algorithm that solves the empirical game, which will be controlled with an efficient Planning Oracle. To deal with the statistical errors, we first introduce the following lemma, which is adapted from Lemma $2$ in Agarwal et al. (2019a).

Proof The proof is straightforward. Letting $w=(I-\gamma P^{\mu,\nu})^{-1}v$, we have $v=(I-\gamma P^{\mu,\nu})w$. Triangle inequality yields $\|v\|_{\infty}\geq\|w\|_{\infty}-\gamma\|P^{\mu,\nu}w\|_{\infty}\geq\|w\|_{\infty}-\gamma\|w\|_{\infty}$, which completes the proof.

Next we establish the Bellman property of a policy pair $(\mu,\nu)$’s variance and its accumulation. This has been observed for MDPs before in Munos and Moore (1999); Lattimore and Hutter (2012); Azar et al. (2012); Agarwal et al. (2019a). We establish the counterpart for Markov games as follows.

For any policy pair $(\mu,\nu)$ and MG $\mathcal{G}$ with transition model $P$, we have

Proof The proof follows that of (Agarwal et al., 2019a, Lemma 3). For any positive vector $v$, by Jensen’s inequality, we have

In addition, by (7), we have $\Sigma_{\mathcal{G}}^{\mu,\nu}=\gamma^{2}(I-\gamma^{2}P^{\mu,\nu})^{-1}\operatorname{{\rm Var}}_{P}(V_{\mathcal{G}}^{\mu,\nu})$. Letting $v=\operatorname{{\rm Var}}_{P}(V_{\mathcal{G}}^{\mu,\nu})$ in (18) and noticing that $\|\Sigma_{\mathcal{G}}^{\mu,\nu}\|_{\infty}\leq\gamma^{2}/(1-\gamma)^{2}$ completes the proof.

Finally, if we just apply Hoeffding’s inequality, we obtain the following concentration argument, upon which we will improve to obtain our final results.

Let $(\mu^{*},\nu^{*})$ be the Nash equilibrium policy pair under the actual model $\mathcal{G}$. Then, for any $\delta\in(0,1]$, with probability at least $1-\delta$, we have

Proof First note that $V^{*}$ is fixed and independent of the randomness in $\widehat{P}$. Due to the boundedness of $V^{*}$ that $\|V^{*}\|_{\infty}\leq(1-\gamma)^{-1}$, and the union of Hoeffding bounds over ${\mathcal{S}}\times\mathcal{A}\times\mathcal{B}$, we have that with probability at least $1-\delta$

Similarly, let $\widehat{{\mathcal{T}}}_{\mu,\nu}$ be the corresponding operator defined under the estimated transition $\widehat{P}$. Note that $\widehat{Q}^{\mu,\nu}$ and $Q^{*}$ are the fixed points of $\widehat{{\mathcal{T}}}_{\mu,\nu}$ and ${\mathcal{T}}_{\mu^{*},\nu^{*}}$, respectively. We thus have

To show the first argument, letting $\mu=\mu^{*}$ and $\nu=\nu^{*}$, we have

Using (4.1) to bound the last term in (20), and solving for $\|Q^{*}-\widehat{Q}^{\mu^{*},\nu^{*}}\|_{\infty}$ from (20), we obtain the first argument.

For the second argument, letting $\mu=\mu^{*}$ and $\nu=\widehat{\nu(\mu^{*})}$ (note that $\widehat{Q}^{\mu^{*},*}=\widehat{Q}^{\mu^{*},\widehat{\nu(\mu^{*})}}$), we have

where the first inequality is due to the non-expansiveness of the $\min$ operator. Using (4.1) to bound the last term in (20), and solving for $\|Q^{*}-\widehat{Q}^{\mu^{*},*}\|_{\infty}$ from (20), we obtain the second argument. Similarly, we can obtain the third argument.

For the fourth argument, letting $\mu=\widehat{\mu}^{*}$ and $\nu=\widehat{\nu}^{*}$, the NE policy under $\widehat{P}$ (note that $\widehat{Q}^{\widehat{\mu}^{*},\widehat{\nu}^{*}}=\widehat{Q}^{*}$), we have

where the inequalities are due to the non-expansivenesses of both the $\max$ and the $\min$ operators. This, combined with (20), completes the proof.

The argument above will lead to a crude bound, with an additional $1/(1-\gamma)$ dependence compared to our main results in Theorem 5 and Theorem 8. The key reason is that we used some self-bounding of the error terms, e.g., $\|Q^{*}-\widehat{Q}^{\mu^{*},\nu^{*}}\|_{\infty}$, which appears on both sides of the inequality, with a $\gamma$ discounting on the right-hand side. This way, by subtracting the term on the right-hand side, we have an additional $1/(1-\gamma)$ order after dividing $(1-\gamma)$ on both sides. This was essentially due to the fact that the direct concentration argument can only deal with the concentration of \big{\|}(\widehat{P}-P)V^{*}\big{\|}_{\infty}, where $\widehat{P}$ and $V^{*}$ are not dependent as $V^{*}$ is a fixed vector. To obtain sharper rates, one has to directly deal with the quantities as \big{\|}(\widehat{P}-P)\widehat{V}\big{\|}_{\infty}, where $\widehat{V}$ denotes some value function obtained from the empirical model, and is correlated with $\widehat{P}$. Properly handling this interdependence will be the focus of our proof next.

2 An Auxiliary Markov Game

Motivated by the absorbing MDP technique in Agarwal et al. (2019a), we introduce an absorbing Markov game, in order to handle the interdependence between $\widehat{P}$ and $\widehat{V}^{\mu,\nu}$, for any $\mu,\nu$ (which may also depend on $\widehat{P}$), which will show up frequently in the analysis.

In addition, we define $U_{s}$ for some state $s$ to choose $u$ from, which is a set of evenly spaced elements in the interval $[V^{*}(s)-\Delta,V^{*}(s)+\Delta]$ for some $\Delta>0$, i.e., $U_{s}\subset[V^{*}(s)-\Delta,V^{*}(s)+\Delta]$. An appropriately chosen size of $|U_{s}|$ will be the key in the proof. We also use $\widehat{P}_{\mathcal{G}_{s,u}}$ to denote the transition model of the absorbing MG for the empirical MG $\widehat{\mathcal{G}}$, denoted by $\widehat{\mathcal{G}}_{s,u}$. Specifically, at all non-absorbing states, $\widehat{P}_{\mathcal{G}_{s,u}}$ is identical to $\widehat{P}$; while at the absorbing state, $\widehat{P}_{\mathcal{G}_{s,u}}(s{\,|\,}s,a,b)=1$ for any $(a,b)\in\mathcal{A}\times\mathcal{B}$. The corresponding value functions are for short denoted by $\widehat{V}^{\mu,\nu}_{s,u}$ and $\widehat{Q}^{\mu,\nu}_{s,u}$. Similar as in the original MG, we also use $\widehat{V}^{*}_{s,u}$ to denote the NE value under the model $\widehat{\mathcal{G}}_{s,u}$, and use $\widehat{V}^{\mu,*}_{s,u}$ and $\widehat{V}^{*,\nu}_{s,u}$ to denote the best-response values of some given $\mu$ and $\nu$, under the model $\widehat{\mathcal{G}}_{s,u}$. Now we first have the following lemma based on Bernstein’s inequality; see a similar argument in Lemma 5 in Agarwal et al. (2019a).

For fixed state $s$, action $(a,b)$, a finite set $U_{s}$, and $\delta>0$, it holds that for all $u\in U_{s}$, with probability greater than $1-\delta$,

where $P_{s,a,b}$ and $\widehat{P}_{s,a,b}$ are the transition models extracted from the original game $\mathcal{G}$ and its empirical version $\widehat{\mathcal{G}}$, respectively (not related to either $\mathcal{G}_{s,u}$ or $\widehat{\mathcal{G}}_{s,u}$), and $(\widehat{\mu}_{s,a},\widehat{\nu}_{s,a})$ is the output of the Planning Oracle using the auxiliary empirical model $\widehat{\mathcal{G}}_{s,u}$

Proof The key observation is that the random variables $\widehat{P}_{s,a,b}$ and $\widehat{V}^{*}_{s,u}$ are independent. Using Bernstein’s inequality along with a union bound over all $u\in U_{s}$, we obtain the first inequality. The other inequalities follow similarly, as $\widehat{P}_{s,a,b}$ is independent of $\widehat{V}^{\mu^{*},*}_{s,u}$, $\widehat{V}^{*,\nu^{*}}_{s,u}$, $\widehat{V}^{\mu^{*},\nu^{*}}_{s,u}$, ${V}^{\widehat{\mu}_{s,u},*}$, and ${V}^{*,\widehat{\nu}_{s,u}}$. This is because the latter terms are all decided by the original game $\mathcal{G}$, and/or the auxiliary empirical game $\widehat{\mathcal{G}}_{s,u}$ (not the original empirical game $\widehat{\mathcal{G}}$).

Note that the arguments in Lemma 13 do not hold, if we replace $\widehat{V}^{*}_{s,u}$ by $\widehat{V}^{*}$, or $\widehat{V}^{\mu^{*},*}_{s,u}$ by $\widehat{V}^{\mu^{*},*}$, or $\widehat{V}^{*,\nu^{*}}_{s,u}$ by $\widehat{V}^{*,\nu^{*}}$. It will neither hold if we replace $\widehat{V}^{\mu^{*},*}_{s,u}$ and ${V}^{\widehat{\mu}_{s,u},*}$ by some $\widehat{V}^{\mu,*}$ and ${V}^{\mu,*}$, for any $\mu$ that is dependent on $\widehat{P}$, e.g., the NE policy $\widehat{\mu}^{*}$ for the original empirical game $\widehat{\mathcal{G}}$. This is one of the key subtleties that are worth emphasizing.

Next we establish two helpful lemmas that help guide the choices of $U_{s}$, so that $\widehat{V}^{*}_{s,u}$ (resp. $\widehat{V}^{\mu^{*},*}_{s,u}$, $\widehat{V}^{*,\nu^{*}}_{s,u}$, and $\widehat{V}^{\mu^{*},\nu^{*}}_{s,u}$) will be a good approximate of $\widehat{V}^{*}$ (resp. $\widehat{V}^{\mu^{*},*}$, $\widehat{V}^{*,\nu^{*}}$, and $\widehat{V}^{\mu^{*},\nu^{*}}$).

For the absorbing state $s$, and any joint policy $(\mu,\nu)$, suppose that $u^{*}=V^{*}_{\mathcal{G}}(s)$, $u^{\mu,*}=V^{\mu,*}_{\mathcal{G}}(s)$, $u^{*,\nu}=V^{*,\nu}_{\mathcal{G}}(s)$, and $u^{\mu,\nu}=V^{\mu,\nu}_{\mathcal{G}}(s)$. Then,

Proof For the first formula, we need to verify that $V^{*}_{\mathcal{G}}$ satisfies the optimal (Nash equilibrium) Bellman equation for the game $\mathcal{G}_{s,u^{*}}$. To this end, note that if $s^{\prime}=s$, then $u^{*}=V^{*}_{\mathcal{G}}(s)$ satisfies the Bellman equation trivially, since $s$ is absorbing with the value $V^{*}_{s,u^{*}}(s)=u^{*}$.

On the other hand, for any $s^{\prime}\neq s$, the outgoing transition model at $s^{\prime}$ in $\mathcal{G}_{s,u^{*}}$ is the same as that in $\mathcal{G}$, and $V^{*}_{\mathcal{G}}(s^{\prime})$ per se satisfies the Bellman equation in $\mathcal{G}$ (which are the same for $\mathcal{G}_{s,u^{*}}$ at these states $s^{\prime}\neq s$). Thus, $V^{*}_{\mathcal{G}}$ satisfies the Bellman equation in $\mathcal{G}_{s,u^{*}}$ for all states. This proves the first equation. The proofs for the remaining three equations are analogous.

Perfect choices of $u$ have been specified in Lemma 14 above. Moreover, we need to quantify how the value changes if we deviate from these perfect choices, i.e., the robustness to misspecification of $u$ (Agarwal et al., 2019a). This result is formally established in the following lemma; see also Lemma 7 in Agarwal et al. (2019a) for a similar result.

Proof Note that $\|r_{s,u}-r_{s,u^{\prime}}\|_{\infty}=(1-\gamma)|u-u^{\prime}|$, since the reward functions only differ at $s$, where $r_{s,u}(s,a,b)=(1-\gamma)u$ and $r_{s,u^{\prime}}(s,a,b)=(1-\gamma)u^{\prime}$. We denote the NE policy pair in $\mathcal{G}_{s,u}$ by $(\mu^{*}_{s,u},\nu^{*}_{s,u})$. Thus,

implying the relationships of the corresponding Q-values; (24) is by definition; (25) uses the observation that $P^{\mu^{*}_{s,u},\nu^{*}_{s,u^{\prime}}}_{s,u}$ is the same as $P^{\mu^{*}_{s,u},\nu^{*}_{s,u^{\prime}}}_{s,u^{\prime}}$ (transition is not affected by the value of $u$). Similarly, we can establish the lower bound that $Q^{*}_{s,u}-Q^{*}_{s,u^{\prime}}\geq-|u-u^{\prime}|$, which proves $\|Q^{*}_{s,u}-Q^{*}_{s,u^{\prime}}\|_{\infty}\leq|u-u^{\prime}|$. Moreover, we have

For the second one, recalling that the best-response policy of $\mu$ under $\mathcal{G}_{s,u}$ being $\nu_{s,u}(\mu)$, we have

where (27) uses the definition of a best-response value, (28) plugs in the best-response policy $\nu_{s,u^{\prime}}(\mu)$, and (29) also uses the fact that the transition does not depend on the value $u$. A lower bound can be established by noticing that $Q^{\mu,*}_{s,u^{\prime}}=\min_{\nu}Q^{\mu,\nu}_{s,u^{\prime}}\leq Q^{\mu,\nu_{s,u}(\mu)}_{s,u^{\prime}}$. This proves $\|Q^{\mu,*}_{s,u}-Q^{\mu,*}_{s,u^{\prime}}\|_{\infty}\leq|u-u^{\prime}|$. Furthermore, notice that

which proves the second inequality. Similar arguments can also be used to establish the third and the fourth inequalities. This completes the proof.

We are now ready to show the main result in this section.

For any state $s$, joint action pair $(a,b)$, and a finite set $U_{s}$, with probability greater than $1-\delta$, we have

Moreover, recalling that $(\widehat{\mu}_{s,u},\widehat{\nu}_{s,u})$ is the output of the Planning Oracle using $\widehat{\mathcal{G}}_{s,u}$, we have

Proof First, for all $u\in U_{s}$ and with probability greater than $1-\delta$, we have

where (30)-(31) use triangle inequality, (32) is due to Lemma 13, and (33) uses the facts that $\sqrt{\operatorname{{\rm Var}}_{P_{s,a,b}}(X+Y)}\leq\sqrt{\operatorname{{\rm Var}}_{P_{s,a,b}}(X)}+\sqrt{\operatorname{{\rm Var}}_{P_{s,a,b}}(Y)}$, and $\sqrt{\operatorname{{\rm Var}}_{P_{s,a,b}}(X)}\leq\|X\|_{\infty}$. Moreover, by Lemmas 14 and 15, we obtain that

which, combined with (33) and taken minimization over all $u\in U_{s}$, yields the first inequality. Proofs for the remaining inequalities are analogous, except that for the last two, the norms $\|{V}^{\widehat{\mu},*}-{V}^{\widehat{\mu}_{s,u},*}\|_{\infty}$ and $\|{V}^{*,\widehat{\nu}}-{V}^{*,\widehat{\nu}_{s,u}}\|_{\infty}$ are kept and not further bounded.

Next we establish the important result that characterizes the errors $|(P-\widehat{P})\widehat{V}^{*}|$, $|(P-\widehat{P})\widehat{V}^{\mu^{*},*}|$, $|(P-\widehat{P})\widehat{V}^{*,\nu^{*}}|$, and $|(P-\widehat{P})\widehat{V}^{\mu^{*},\nu^{*}}|$, which could not have been handled without the arguments above, due to the dependence between $\widehat{P}$ and $\widehat{V}^{*}$ (and also $\widehat{V}^{\mu^{*},*}$, $\widehat{V}^{*,\nu^{*}}$, and $\widehat{V}^{\mu^{*},\nu^{*}}$).

For any $\delta\in(0,1]$, with probability greater than $1-\delta$, it holds that

where $\Delta_{\delta,N}^{\prime}$ is defined as

Proof Let $U_{s}$ denote a set with evenly spaced elements in the interval $[V^{*}(s)-\Delta_{\delta/2,N},V^{*}(s)+\Delta_{\delta/2,N}]$, with $|U_{s}|=2/(1-\gamma)^{2}$, and $\Delta_{\delta,N}$ being defined in Lemma 12. Lemma 12 shows that with probability greater than $1-\delta/2$,

for all $s\in{\mathcal{S}}$. Since each subinterval determined by $U_{s}$ is of length $2\Delta_{\delta/2,N}/(|U_{s}|-1)$, and $\widehat{V}^{*}(s)$ will fall into one of them, we know that

where we have used the fact that $|U_{s}|\geq 1/(1-\gamma)^{2}+1$. We then choose $\delta/2$ to be $\delta/(2|{\mathcal{S}}||\mathcal{A}||\mathcal{B}|)$ in Lemma 16, so that it holds for all states and joint actions with probability greater than $1-\delta/2$. By substitution and noting that the two events in Lemmas 12 and 16 both fail with probability $\delta/2$, we obtain the first inequality by properly choosing the constant $c$. Similarly, for the other two inequalities, note that Lemma 12 can be applied to show that $\widehat{V}^{\mu^{*},*}(s)$, $\widehat{V}^{*,\nu^{*}}(s)$, and $\widehat{V}^{\mu^{*},\nu^{*}}(s)$, all lie in the interval in (34) (centered at $V^{*}(s)$). By similar arguments, the remaining three inequalities can be proved (note that Lemma 16 can be applied to $\widehat{V}^{\mu^{*},*}(s)$, $\widehat{V}^{*,\nu^{*}}(s)$, and $\widehat{V}^{\mu^{*},\nu^{*}}(s)$, as well).

Lastly, with a smooth Planning Oracle, see Definition 7, we can similarly establish the following error bounds on $|(P-\widehat{P})V^{\widehat{\mu},*}|$ and $|(P-\widehat{P})V^{*,\widehat{\nu}}|$, thanks to Lemma 16.

With a smooth Planning Oracle that has a smooth constant $C$ (see Definition 7), for any $\delta\in(0,1]$, with probability greater than $1-\delta$, it holds that

where $\Delta_{\delta,N}^{\prime\prime}$ is defined as

Proof Following the proof of Lemma 17, let $U_{s}$ denote a set with evenly spaced elements in the interval $[V^{*}(s)-\Delta_{\delta/2,N},V^{*}(s)+\Delta_{\delta/2,N}]$, with $\Delta_{\delta,N}$ being defined in Lemma 12. By Lemma 12, we know that $\widehat{V}^{*}(s)$ lies in this interval with probability greater than $1-\delta/2$, for all $s\in{\mathcal{S}}$. Now we choose $|U_{s}|=(C+1)/(1-\gamma)^{4}$, where $C$ is the smooth coefficient in Definition 7. As $\widehat{V}^{*}(s)$ will fall into one of the subintervals determined by $U_{s}$, we have

which also uses the fact $|U_{s}|\geq C/(1-\gamma)^{4}+1$. Furthermore, by Definition 7 and the proof of Lemma 15, we have

where (37) uses Hölder’s inequality, and (38) follows by expanding the Q-value functions, using (36), and noticing that $\|{Q}^{\widehat{\mu}_{s,u},*}\|_{\infty}\leq 1/(1-\gamma)$. Combining (38) and (35), and taking $\min$ over $u\in U_{s}$, we have

The rest of the proof follows the arguments of Lemma 17, which combines the last two inequalities in Lemma 16 to obtain the desired bound. Note that the absolute constant here might be different from that in Lemma 17. The proof for the second inequality is analogous.

Note that compared to Lemma 17, Lemma 18 has to additionally deal with the interdependence between $\widehat{P}$ and $V^{\widehat{\mu},*}$ (as well as that between $\widehat{P}$ and $V^{*,\widehat{\nu}}$). What can be guaranteed before, in the absorbing MGs, is that the value function can be controlled to be close to that in the original MG (see Lemmas 14 and 15, and the proof of Lemma 16). However, in general, it is unclear how much the NE policy changes, as well as how much the best-response value in the original true MG changes. This calls for some stability of the NE policy, and was made possible due to the smoothness of our Planning Oracle (see (36)-(38)). Lemma 18 will play an important role in obtaining the near-optimal sample complexity in Theorem 8 (see §4.5).

3 Proof of Theorem 5

We are now ready to prove Theorem 5. To this end, we first establish the following lemma.

For any policy pair $(\widehat{\mu},\widehat{\nu})$ that satisfies the condition in Theorem 5, there exists some absolute constant $c$ such that

where (39) is due to Lemma 9; (40) uses triangle inequality; and (41) is due to the non-negativeness of the entries in $(I-\gamma P^{\widehat{\mu},\widehat{\nu}})^{-1}$, the sub-optimality of $(\widehat{\mu},\widehat{\nu})$, and Lemma 10. Since the first term in (41) can be bounded using Lemma 17, we have

where (42) uses the fact that $\sqrt{\operatorname{{\rm Var}}_{P}(X+Y)}\leq\sqrt{\operatorname{{\rm Var}}_{P}(X)}+\sqrt{\operatorname{{\rm Var}}_{P}(Y)}$; (43) is due to Lemma 11, the fact that $\sqrt{\operatorname{{\rm Var}}_{P}({V}^{\widehat{\mu},\widehat{\nu}}-\widehat{V}^{\widehat{\mu},\widehat{\nu}})}\leq\|{V}^{\widehat{\mu},\widehat{\nu}}-\widehat{V}^{\widehat{\mu},\widehat{\nu}}\|_{\infty}$, and $\|\widehat{V}^{\widehat{\mu},\widehat{\nu}}-\widehat{V}^{*}\|_{\infty}\leq\epsilon_{opt}$; (44) is due to $\|{V}^{\widehat{\mu},\widehat{\nu}}-\widehat{V}^{\widehat{\mu},\widehat{\nu}}\|_{\infty}\leq\|{Q}^{\widehat{\mu},\widehat{\nu}}-\widehat{Q}^{\widehat{\mu},\widehat{\nu}}\|_{\infty}$. Solving for $\|Q^{\widehat{\mu},\widehat{\nu}}-\widehat{Q}^{\widehat{\mu},\widehat{\nu}}\|_{\infty}$ in (45) yields the desired inequality.

For the second inequality, by Lemma 9, we first have

For the first term in the $\max$ operator above, by similar arguments from (42)-(45), we have

where (47) is due to Lemma 17, (48) uses triangle inequality, and (50) uses Lemma 11. Solving for \big{\|}{Q}^{\mu^{*},\nu^{*}}-\widehat{Q}^{\mu^{*},\nu^{*}}\big{\|}_{\infty} gives the bound for it.

Similarly, the second term in the $\max$ operator in (46) can be bounded by

which can be solved to obtain a bound for \big{\|}Q^{\mu^{*},\widehat{\nu(\mu^{*})}}-\widehat{Q}^{\mu^{*},*}\big{\|}_{\infty}. Combining the two bounds and (46), we prove the second inequality in the lemma. The proof for the third inequality is analogous.

With Lemma 19 in hand, we are ready to prove Theorem 5. Note that the condition on $N$ in Theorem 5 makes $\alpha_{\delta,N}<1/2$. Thus, by (8)-(9) in Lemma 9 with $(\mu,\nu)$ being replaced by $(\widehat{\mu},\widehat{\nu})$, we have