The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces

Introduction

Multi-agent reinforcement learning (MARL) systems have recently achieved significant success in many AI challenges including the game Go , Poker , real-time strategy games , decentralized controls or multiagent robotics systems , autonomous driving , as well as complex social scenarios such as hide-and-seek . Two crucial components that contribute to these successes are function approximation and self-play. Function approximation is frequently used in modern applications with large state spaces, where either the value function or the policy is approximated by parametric function classes, which are typically deep neural networks. Meanwhile, self-play enables the learner to improve by playing against itself instead of traditional human experts.

Despite the empirical success of MARL, existing theoretical guarantees in MARL only apply to the basic settings where the value functions can be represented by either tables (in cases where the states and actions are discrete) or linear maps . While a recent line of works significantly advance our understanding of RL with general function approximation, and provide sample-efficient guarantees for RL with kernels, neural networks, rich observations, and several special cases of partial observability, they are all restricted to the single-agent setting. Distinct from single-agent RL, each agent in MARL are facing not only the unknown environment, but also the opponents that can constantly adapt their strategies in response to the behavior of the learning agent. This additional game-theoretical feature makes it challenging to extend the single-agent general function approximation results to the multi-agent setting. This motivates us to ask the following question:

Can we design sample-efficient MARL algorithms for general function approximation?

By “sample-efficient”, we mean the algorithms provably learn within a polynomial number of samples that is independent of the number of states. This paper provides the first positive answer to this question in the context of two-player zero-sum Markov Games (MGs) . In particular, we make the following contributions:

We design a new self-play algorithm for MARL—Golf_with_Exploiter. Our algorithm maintains a main player and an exploiter, where the exploiter facilitates the learning of the main player by deliberately exploiting her weakness. Our algorithm features optimism, and can simultaneously address multi-agent, general function approximation, as well as the trade-off between exploration and exploitation.

We introduce a new general complexity measure for MARL—Multi-agent Bellman Eluder (BE) dimension, which is adapted from its single-agent version . We prove that our algorithm can learn the Nash equilibrium policies of any MARL problem with low multi-agent BE dimension, using a number of samples that is polynomial in all relevant parameters, but independent of the size of the state space. We further provide an online guarantee for our algorithm when facing against adversarial opponents.

We remark that our algorithm is sample-efficient but not computationally efficient. Designing computationally efficient algorithms in the context of general function approximation is an open problem even in the single-agent setting , which we left as an interesting topic for future research.

There is an extensive literature on empirical MARL, in distributed, cooperative, and competitive settings [see, e.g., 34, 38, 48, 6, 30, 57, and the references therein]. Due to space limit, we focus on reviewing the theoretical works in this section.

Markov Game (MG), also known as stochastic game , is a popular model in multi-agent RL . Early works have mainly focused on finding Nash equilibria of MGs with known transition and reward , or under strong reachability conditions such as simulators where exploration is not needed.

A recent line of works provide non-asymptotic guarantees for learning two-player zero-sum tabular MGs, in the setting that requires strategic exploration. and develop the first provably-efficient learning algorithms in MGs based on optimistic value iteration. and improve upon these works and achieve best-known sample complexity for model-free and model-based methods, respectively. Several extensions are also studied, including multi-player general-sum MGs , unknown games This terminology stems from game theory, which means the actions of the opponents are not observed. , vector-valued MGs , etc.

Beyond tabular MGs, and also study learning MGs with linear function approximation. Their techniques heavily rely on “optimistic closure” (see Appendix A for more details), which can not be directly extended to the general function approximation setting with weak assumptions. To our best knowledge, this paper provides the first positive result on learning MGs with general function approximation.

There has been a long line of research studying Markov Decision Process (MDP), which can be viewed as a single-agent version of Markov Game. Tabular MDP has been studied thoroughly in recent years . Particularly, in the episodic setting, the minimax regret or sample complexity is achieved by both model-based and model-free methods, up to logarithmic factors. When the state space is large, the tabular formulation of RL is impractical and function approximation is necessary. The most studied case is linear function approximation .

For general function approximation, there are two common measures of complexity: Eluder dimension and Bellman rank , which are unified by a more generic notion—Bellman-Eluder dimension . Recently, develops a new problem class termed bilinear class, which can be considered as an infinite-dimensional extension of low Bellman rank class. Low complexity RL problems under the above criteria are statistically tractable. Polynomial sample complexity guarantees , or even regret guarantees are established, under additional completeness and realizability conditions. However, most of the above algorithms are not computationally efficient and it remains open how to design computationally efficient algorithms for these settings.

Finally, we remark that there is another long line of research on MARL based on the model of extensive-form games (EFG) [see, e.g., 28, 19, 64, 9, 10, 12]. Results on learning EFGs do not directly imply results for learning MGs, since EFGs are naturally tree-structured games, which can not efficiently represent MGs—graph-structured games where a state at the $h^{\text{th}}$ step can be the child of multiple states at the $(h-1)^{\text{th}}$ step.

Preliminaries

A Markov policy $\mu$ of the max-player is a collection of vector-valued functions $\{\mu_{h}:\ \mathcal{S}\rightarrow\Delta_{\mathcal{A}}\}_{h\in[H]}$, each mapping a state to a distribution in the probability simplex over $\mathcal{A}$. We use the $a^{\rm th}$ coordinate of $\mu_{h}(s)$ to refer to the probability of taking action $a$ at state $s$ and step $h$. Similarly, we can define a Markov policy $\nu$ over $\mathcal{B}$ for the min-player.

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$. And for step $H+1$, we have $V_{H+1}^{\mu,\nu}\equiv 0$.

For any policy of the max-player $\mu$, there exists a best response policy of the min-player $\nu^{\dagger}(\mu)$ satisfying $V_{h}^{\mu,\nu^{\dagger}(\mu)}=\inf_{\nu}V_{h}^{\mu,\nu}(s)$ for all $(s,h)$. For cleaner notation, we denote $V_{h}^{\mu,\dagger}:=V_{h}^{\mu,\nu^{\dagger}(\mu)}$. Similarly, we can define $\mu^{\dagger}(\nu)$ and $V_{h}^{\dagger,\nu}$. It is known that there exists policies $\mu^{\star},\nu^{\star}$ that are optimal against the best responses of the oponents, i.e.,

We call these optimal policies $(\mu^{\star},\nu^{\star})$ a Nash equilibrium of the Markov game, which are further known to satisfy the following minimax equation:

We call the value functions of $(\mu^{\star},\nu^{\star})$ Nash value functions, and abbreviate $V_{h}^{\mu^{\star},\nu^{\star}}$ as $V_{h}^{\star}$ and $Q_{h}^{\mu^{\star},\nu^{\star}}$ as $Q_{h}^{\star}$. Intuitively speaking, in a Nash equilibrium, no player can benefit by unilaterally deviating from her own policy.

We say a policy $\mu$ of the max-player is an $\epsilon$-approximate Nash policy if $V_{1}^{\mu,\dagger}(s_{1})\geq V_{1}^{\star}(s_{1})-\epsilon$. Suppose an agent interacts with the environment for $K$ episodes, and denote by $\mu^{k}$ the policy executed by the max-player in the $k^{\rm th}$ episode. Then the (cumulative) regret of the max-player is defined as

The goal of reinforcement learning is to learn $\epsilon$-approximate Nash policies or to achieve sublinear regret. In this paper, we focus on learning the Nash policies of the max-player. By symmetry, the definitions and techniques directly extend to learning the Nash policies of the min-player.

1 Function Approximation

This paper considers reinforcement learning with value function approximation. Formally, the learner is provided with a function class $\mathcal{F}=\mathcal{F}_{1}\times\dots\times\mathcal{F}_{H}$ where each $\mathcal{F}_{h}\subseteq(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow)$ consists of candidate functions to approximate some target action-value functions at step $h$. Since there is no reward at step $H+1$, we set $f_{H+1}\equiv 0$ for any $f\in\mathcal{F}$ without loss of generality.

For any value function $f\in\mathcal{F}$, we denote by $\mu_{f}=(\mu_{f,1},\ldots,\mu_{f,H})$ the Nash policy of the max-player induced by $f$, where

Moreover, we denote by $V_{f}$ the Nash value function induced by $f$, so that

Based on $V_{f}$ and $V_{f}^{\mu}$, two types of Bellman operators are defined as below

which naturally generalize the optimal Bellman operator and the policy Bellman operator from MDPs to MGs. In the remainder of this paper, we will refer to them as the Nash Bellman operator and $\mu$-Bellman operator, respectively.

It is known that RL with function approximation is in general statistically intractable without further assumptions (see, e.g., hardness results in ). Below, we present two assumptions that are generalizations of commonly adopted assumptions in MDP literature.

For any $f\in\mathcal{F}$ and $h\in[H]$, there exist $Q_{h},Q^{\prime}_{h}\in\mathcal{F}_{h}$ s.t. $\|Q_{h}^{\star}-Q_{h}\|_{\infty}\leq\varepsilon_{\rm real}$ and $\|Q_{h}^{\mu_{f},\dagger}-Q^{\prime}_{h}\|_{\infty}\leq\varepsilon_{\rm real}$.

Realizability requires the function class to be well-specified so that the value function of the Nash policy and the value function of any induced policy $\mu_{f}$ against its best response lie inside $\mathcal{F}$ approximately.

Let $\mathcal{G}=\mathcal{G}_{1}\times\dots\times\mathcal{G}_{H}$ be an auxiliary function class provided to the learner where each $\mathcal{G}_{h}\subseteq(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow)$. Completeness requires the auxiliary function class $\mathcal{G}$ to be rich enough so that applying Bellman operators to any function in the primary function class $\mathcal{F}$ will end up in $\mathcal{G}$ approximately.

For any $f,f^{\prime}\in\mathcal{F}$ and $h\in[H]$, there exist $Q_{h},Q^{\prime}_{h}\in\mathcal{G}_{h}$ s.t. $\|\mathcal{T}_{h}f_{h+1}-Q_{h}\|_{\infty}\leq\varepsilon_{\rm comp}$ and $\|\mathcal{T}_{h}^{\mu_{f}}f^{\prime}-Q^{\prime}_{h}\|_{\infty}\leq\varepsilon_{\rm comp}$.

In the single-agent setting , the realizability and completeness conditions are stated for the special case $\varepsilon_{\rm real}=\varepsilon_{\rm comp}=0$, while this paper considers a strictly more general condition. This extension makes it possible to handle the misspecified setting, i.e., $\mathcal{F}$ and $\mathcal{G}$ only satisfy these conditions approximately, but not exactly. Even when $\mathcal{F}$ and $\mathcal{G}$ satisfy these conditions exactly, the above extension can still help us avoid some technical redundancy caused by the possible infinite cardinality of $\mathcal{F}$ and $\mathcal{G}$, by only considering their finite coverings. To be precise,

The following lemma implies that we can always restrict our attention to finite coverings, which also approximately satisfy the realizability and completeness conditions up to satisfying accuracy.

As a result, we only need to consider finite function class $\mathcal{F}$ and $\mathcal{G}$ in Section 3. Some of the examples introduced in Section 4 involve infinite function classes. To address this inconsistency, we can first compute the finite coverings of $\mathcal{F}$ and $\mathcal{G}$, which satisfy the approximate realizability and completeness conditions by Lemma 2, and then invoke the algorithms in Section 3 with the coverings instead of the original function classes. It is straightforward to verify that by replacing the cardinality with the covering number, all theoretical guarantees derived in Section 3 still hold.

Finally, we define the $L^{\infty}$ Projection Operator, which will be frequently used in our technical statements and proofs.

Main Results

In this section, we present an optimization-based algorithm Golf_with_Exploiter, and its theoretical guarantees for any multi-agent RL problem with low Bellman-Eluder dimension.

We describe Golf_with_Exploiter in Algorithm 1. At a high level, Golf_with_Exploiter follows the principle of optimism in face of uncertainty, and maintains a global confidence set for Nash value function $Q^{\star}$ based on local constraints. It extends the single-agent Golf algorithm by introducing an exploiter subroutine—Compute_Exploiter, which facilitates the learning of the main player (the max player) by continuously exploiting her weakness.

In each episode, Golf_with_Exploiter performs four main steps:

Optimistic planning (Line 3): compute the value function $f^{k}$ that induces the most optimistic Nash value from the current confidence set $\mathcal{C}$, and choose $\mu^{k}$ to be its induced Nash policy of the max-player.

Finding exploiter (Line 4): compute an approximate best response policy $\nu^{k}$ for the min-player, by invoking the subroutine Compute_Exploiter on historical data $\mathcal{D}$ and the policy of the max-player $\mu^{k}$.

Data collection (Line 7-8): we provide two different options for the Sampling procedure

Roll a single trajectory by following $(\mu^{k},\nu^{k})$.

For each $h$, roll a trajectory by following $(\mu^{k},\nu^{k})$ in the first $h-1$ steps and take uniformly random action at step $h$. This option will roll $H$ trajectories each time, but in the $h^{\rm th}$ trajectory, only the $h^{\rm th}$ transition-reward tuple is augmented into $\mathcal{D}_{h}$.

Confidence set update (Line 9): update confidence set $\mathcal{C}$ using the renewed dataset $\mathcal{D}$.

The core components of Golf_with_Exploiter are the construction of the confidence set and the subroutine Compute_Exploiter, which we elaborate below in sequence.

For each $h\in[H]$, Golf_with_Exploiter maintains a local constraint using the historical data $\mathcal{D}_{h}$ at this step

where the squared loss $\mathcal{L}_{\mathcal{D}_{h}}$ is defined as

The main challenge of learning MGs compared to learning MDPs lies in the choice of behavior policies as discussed in Section 1. Motivated by the empirical breakthrough work AlphaStar , we adapt the methodology of exploiter. Specifically, we design the Compute_Exploiter subroutine that approximately computes a best-response policy $\nu^{k}$ against the policy of the max-player $\mu^{k}$. By executing $\nu^{k}$, the min-player exposes the flaws of the max-player, and helps improve her strategy. The pseudocode of Compute_Exploiter is given in Algorithm 2, which basically follows the same rationale as Algorithm 1 except that we change the regression target by replacing $V_{f}$ with $V_{f}^{\mu}$, because the confidence set $\mathcal{C}^{\mu}$ is constructed for the best-response value function $Q^{\mu,\dagger}$ instead of the Nash value function $Q^{\star}$. Formally, Algorithm 2 adapts a new square loss function defined below

Finally, we remark that the optimistic planning and exploiter computation steps are computationally inefficient in general. Designing computationally efficient algorithms in the context of general function approximation is an open problem even in the single-agent setting , which we left as an interesting topic for future research.

2 Complexity Measure

In this subsection, we introduce our new complexity measure—multi-agent Bellman-Eluder (BE) dimension, which is generalized from its single-agent version . We will show in Section 4 that the family of low BE dimension problems includes many interesting multi-agent RL settings, such as tabular MGs, MGs with linear or kernel function approximation, and MGs with rich observation.

We start by recalling the definition of distributional Eluder (DE) dimension .

Let $\mathcal{G}$ be a function class defined on $\mathcal{X}$, and $\Pi$ be a family of probability measures over $\mathcal{X}$. The distributional Eluder dimension $\dim_{\textrm{DE}}(\mathcal{G},\Pi,\epsilon)$ is the length of the longest sequence $\{\rho_{1},\ldots,\rho_{n}\}\subset\Pi$ such that there exists $\epsilon^{\prime}\geq\epsilon$ where $\rho_{i}$ is $\epsilon^{\prime}$-independent of $\{\rho_{1},\ldots,\rho_{i-1}\}$ for all $i\in[n]$.

DE dimension generalizes the original Eluder dimension from points to distributions. The main advantage of this generalization is that for RL problems with large state space, it is oftentimes easier to evaluate a function with respect to certain distribution family than to estimate it point-wisely. And for the purpose of this paper, we will focus on the following two specific distribution families.

$\mathcal{D}_{\Delta}:=\{\mathcal{D}_{\Delta,h}\}_{h\in[H]}$, where $\mathcal{D}_{\Delta,h}=\{\delta_{(s,a,b)}(\cdot)~{}|~{}(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\}$, i.e., the collections of probability measures that put measure $1$ on a single state-action pair.

$\mathcal{D}_{\mathcal{F}}:=\{\mathcal{D}_{\mathcal{F},h}\}_{h\in[H]}$, where $\mathcal{D}_{\mathcal{F},h}$ denotes the collections of all probability measures over $\mathcal{S}\times\mathcal{A}\times\mathcal{B}$ at the $h^{\text{th}}$ step, which can be generated by executing some $(\mu_{f},\nu_{f,g})$ with $f,g\in\mathcal{F}$. Here $\nu_{f,g}$ is the best response to $\mu_{f}$ regarding to Q-value $g$:

Now, we are ready to introduce our key complexity notion—multi-agent Bellman-Eluder (BE) dimension, which is simply the DE dimension on the function class of Bellman residuals, minimizing over the two aforementioned distribution families, and maximizing over all steps.

Let $\mathcal{H}_{\mathcal{F}}$ be the function classes of Bellman residuals where $\mathcal{H}_{\mathcal{F},h}:=\{f_{h}-\mathcal{T}_{h}^{\mu_{g}}f_{h+1}~{}|~{}f,g\in\mathcal{F}\}$. Then the Bellman-Eluder dimension is defined as

We remark that the Bellman residual functions used in Definition 6 take both state and action as input. By choosing an alternative class of Bellman residuals defined over the state space only, we can similarly define a variant of this notion—V-type BE dimension. For clean presentation, we defer the formal definition to Appendix B.

3 Theoretical Guarantees

Now we are ready to present the theoretical guarantees.

Theorem 7 claims that Golf_with_Exploiter can achieve $\sqrt{K}$ regret on any RL problem with low BE dimension, under the realizability and the completeness assumption. Moreover, the regret scales polynomially with respect to the length of episode, the BE dimension of function class $\mathcal{F}$, and the log-cardinality of the two function classes. In particular, it is independent of the size of the state space, which is of vital importance for practical RL problems, where the state space is oftentimes prohibitively large.

By pigeonhole principle, we also derive a sample complexity guarantee for Golf_with_Exploiter.

Under Assumption 1 and 2, there exists absolute constants $c,c^{\prime}$ such that for any $\epsilon>0$, choose $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$ and $\Delta=c^{\prime}(H\sqrt{d\beta/K}+\epsilon)$, where $d=\dim_{\textrm{BE}}(\mathcal{F},\epsilon/H)$ is the BE dimension of $\mathcal{F}$,then with probability at least $1-\delta$, the output condition (Line 5) will be satistied at least once in the first $K$ episodes. Furthermore, the output policy $\mu^{\text{out}}$ of Algorithm 1 with Option I is $\mathcal{O}(\epsilon+H\sqrt{d}(\varepsilon_{\rm real}+\varepsilon_{\rm comp}))$-approximate Nash, if K\geq\Omega\big{(}(H^{2}d/\epsilon^{2})\cdot\log(H|\mathcal{F}||\mathcal{G}|d/\epsilon)\big{)}.

We also derive similar sample complexity guarantee in terms of V-type BE dimension for Algorithm 1 with Option II, which can be found in Appendix B.

4 Adversarial Opponents

So far we have been focusing on the self-play setting, where the learner can control both players and the goal is to learn an approximate Nash policy. Another setting of importance is the online setting, where the learner can only control the max-player, and the goal is to achieve high cumulative reward against the adversarial min-player. Intuitively, it is reasonable to expect Golf_with_Exploiter could still work in the online setting, because Theorem 7 demonstrates that it can achieve sublinear regret competing against the exploiter, which is the strongest possible adversary. This is indeed the case. The only place we need to change in Algorithm 1 is Line 4: instead of computing $\nu^{k}$ using Algorithm 2, we let the adversary pick policy $\nu^{k}$. Before stating the theoretical guarantee, we introduce an online version of Bellman Eluder dimension.

Let $\mathcal{H}_{\mathcal{F}}$ be the function classes of Bellman residuals where $\mathcal{H}_{\mathcal{F},h}:=\{f_{h}-\mathcal{T}_{h}f_{h+1}~{}|~{}f\in\mathcal{F}\}$. Then the online Bellman-Eluder dimension is defined as:

Compared to the BE dimension in Definition 6, this online version uses a smaller function class that includes only the residuals with respect to the Nash Bellman operator. Another difference is the choice of distribution family is now limited to only $\mathcal{D}_{\Delta}$ because the learner cannot control the policy of the min-player in the online setting. Now, we are ready to present the theoretical guarantee.

Theorem 11 claims that on any problem of low online BE dimension, Golf_with_Exploiter can achieve $\sqrt{K}$ regret against an adversarial opponent. Moreover, the multiplicative factor scales linearly in the horizon length, and sublinearly in the online BE dimension as well as the log-cardinality of the function classes. Comparing to the self-play regret guarantee, Theorem 11 holds under a weaker condition, but only guarantees Algorithm 1 can play favorably against the adversary, instead of the best-response policy. This is unavoidable because if the adversary is very weak, then it is impossible to learn Nash policies by playing against it.

Examples

In this section, we introduce five concrete multi-agent RL problems with low BE dimension: tabular MGs, MGs with linear function approximation, MGs with kernel function approximation, MGs with rich observation, and feature selection for kernel MGs, which generalize their single-agent versions from MDPs to MGs. Except for tabular MGs, all above examples are new and can not be addressed by existing works .

Starting with the simplest scenario, we show that MGs with finite state-action space has BE dimension no larger than the size of its state-action space, up to a logarithmic factor.

Consider a tabular MG with state set $\mathcal{S}$ and action set $\mathcal{A}\times\mathcal{B}$. Then any function class $\mathcal{F}\subseteq(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow)$ satisfies

We consider linear function class $\mathcal{F}$ consisting of functions linear in a $d$-dimensional feature mapping. Specifically, for each $h\in[H]$, we choose $\mathcal{F}_{h}=\{\phi_{h}(\cdot,\cdot,\cdot)^{\top}\theta~{}\mid~{}\theta\in B_{d}(R)\}$ where $\phi_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow B_{d}(1)$ maps a state-action pair into the $d$-dimensional unit ball centered at the origin.

$\mathcal{T}_{h}^{\mu_{f}}\mathcal{F}_{h+1}\subset\mathcal{F}_{h}$ for any $(f,h)\in\mathcal{F}\times[H]$.

Assumption 3 is a special case of Assumption 2 (completeness) by choosing auxiliary function class $\mathcal{G}=\mathcal{F}$. Assumption 3 also implies Assumption 1 (realizability) by backward induction. Below, we show under self-completeness, the BE dimension of $\mathcal{F}$ is upper bounded by the dimension of the feature mappings $d$ up to a logarithmic factor.

The $\epsilon$-effective dimension of a set $\mathcal{Z}$ is the minimum integer $d_{{\rm eff}}(\mathcal{Z},\epsilon)=n$ such that

Consider an MG with decoding function $q:\mathcal{S}\rightarrow[m]$. Then any function class $\mathcal{F}\subseteq(\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow)$ satisfies

where $\dim_{\textrm{VBE}}$ denotes the V-type BE dimension defined in Appendix B.

Conclusion

This paper presents the first line of sample-efficient results for Markov games with large state space and general function approximation. We propose a new complexity measure—multiagent Bellman-Eluder dimension, and design a new algorithm that can sample-efficiently learn any MGs with low BE dimension. At the heart of our algorithm is the exploiter, which facilitates the learning of the main player by continuously exploiting her weakness. Our generic framework applies to a wide range of new problems including MGs with linear or kernel function approximation, MGs with rich observations, and kernel feature selection, all of which can not be addressed by existing works.

References

Appendix A Discussion on Technical Challenges

In this section, we discuss some technical challenges faced when designing provably efficient algorithms for MGs with general function approximation, which explains why direct extension of existing algorithmic solutions is not enough.

The algorithmic solutions designed for tabular MGs and linear MGs can be viewed as special cases of solving the following sub-problem: in each episode $k$, given the confidence set of possible functions $f\in\mathcal{C}^{k}$, find function pair $(f^{k},g^{k})$ and policy pair $(\mu^{k},\nu^{k})$ s.t. for any state $s$

Here we omit the dependence on $h$ by considering a single-step special case. This is similar to the contextual bandits problem, but a game version.

Once the above sub-problem is solved, using the fact that the true value function $f^{\star}$ is contained in $\mathcal{C}^{k}$, we can bound the duality gap by

where the summation of the RHS over $k$ can be further bounded by pigeon-hole type of arguments.

Then a natural question is: how can we solve this sub-problem (8)? A helpful condition is optimistic closure, which indeed holds for tabular and linear MGs . For the max-player version, this means the pointwise upper bound defined by $\overline{f}^{k}\left(s,a,b\right):=\underset{f\in\mathcal{C}^{k}}{\max}f\left(s,a,b\right)$ remains in the function class, i.e., $\overline{f}^{k}\in\mathcal{C}^{k}\subseteq\mathcal{F}$. The min-player version is similar.

Under this condition, the function pair $(\overline{f}^{k},\underline{f}^{k})$ is clearly the maximizer/minimizer to the subproblem, and therefore it reduces to finding $(\mu^{k},\nu^{k})$ so that

By definition, the solution is a coarse correlated equilibrium.

However, the optimistic closure may not hold in general. Even worse, no solution may exist for the sub-problem (8), as we will see below in a concrete example. In that case, the existing techniques fail and it becomes unclear how to bound the two-sided duality gap. As a result, the general function approximation problem is significantly harder than the special cases mentioned before.

Now we describe a concrete example where sub-problem (8) has no solution when optimisic closure condition does not hold. We consider rock-paper-scissors, with one state and three actions for both players, i.e., $|\mathcal{S}|=1$ and $|\mathcal{A}|=|\mathcal{B}|=3$. Then each function $f\in\mathcal{F}:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow$ We assign the reward $$instead of$$ to make the example looks simpler. Everything stated here still hold after scaling. is essentially a $3\times 3$ matrix and we will use $M$ to represent such matrices. The matrix corresponding to Nash value $Q^{\star}$ is

which describes the true reward associated with different actions. Assume there are $6$ other matrices in our confidence set $\mathcal{C}^{k}$:

Now suppose we find a pair of matrices $(\overline{M},\underline{M})$ and a pair of policies $(\mu,\nu)$ which solves sub-problem (8). If we can prove such $(\mu,\nu)$ must be deterministic, then we get into a contradiction, since whatever $(\overline{M},\underline{M})$ is, it is impossible for deterministic policies $\mu$ and $\nu$ to be the best response of each other. Therefore, in order to show sub-problem (8) has no solution, it suffices to prove $(\mu,\nu)$ must be deterministic.

Since $\mu$ is a solution of sub-problem (8), we must have

Since we are maximizing the above quantity, $\overline{M}$ can only take $M_{1}$,$M_{4}$ or $M_{5}$ because the others are dominated. Direct computation gives

Now that $\mu$ maximizes $(\mu^{\prime})^{T}\overline{M}\nu$, if it is not deterministic, there will be at least two entries in $\overline{M}\nu$ that take the same highest value, say $(\overline{M}\nu)=(\overline{M}\nu)\geq(\overline{M}\nu)$.

If $\overline{M}=M_{1}$, the above condition is just

If $\nu>0$, we can choose $\overline{M}=M_{4}$ to make $(\overline{M}\nu)=(M^{\star}\nu)+0.1\nu>(M^{\star}\nu)$. Therefore, the value of $\max(\mu^{\prime})^{T}\overline{M}\nu$ is increased, which is contradictory to the maximization condition.

If $\nu=0$, the condition $(M^{\star}\nu)=(M^{\star}\nu)+0.1\nu$ is just $\nu+0.1\nu=-\nu$, which impliess $\nu=\nu=0$. This is impossible since $\nu$ is a probability distribution.

As a result, we prove $\overline{M}$ cannot be $M_{1}$. Similarly, $\overline{M}$ cannot be $M_{4}$ or $M_{5}$. We obtain a contradiction! Therefore, $\mu$ must be deterministic and by symmtrical argument so is $\nu$. Putting everything together completes the proof. That is, when optimisic closure condition does not hold, sub-problem (8) can have no solution.

Appendix B V-type Bellman Eluder Dimension

In this section, we define V-type Bellman-Eluder (VBE) dimension, and provide the corresponding theoretical guarantee for Algorithm 1 with Option II.

With slight abuse of notation, we redefine the following distribution families for VBE dimension. The only difference is that now we use distributions over $\mathcal{S}$ instead of $\mathcal{S}\times\mathcal{A}\times\mathcal{B}$.

$\mathcal{D}_{\Delta}:=\{\mathcal{D}_{\Delta,h}\}_{h\in[H]}$, where $\mathcal{D}_{\Delta,h}=\{\delta_{s}(\cdot)~{}|~{}s\in\mathcal{S}\}$, i.e., the collections of probability measures that put measure $1$ on a single state.

$\mathcal{D}_{\mathcal{F}}:=\{\mathcal{D}_{\mu,h}\}_{h\in[H]}$, where $\mathcal{D}_{\mu,h}$ denotes the collections of all probability measures over $\mathcal{S}$ at the $h^{\text{th}}$ step, which can be generated by executing some $(\mu_{f},\nu_{f,g})$ with $f,g\in\mathcal{F}$. Here, $\nu_{f,g}$ is the best response to $\mu_{f}$ regarding to Q-value $g$:

To proceed, we introduce the following Bellman residual function defined over the state space $\mathcal{S}$

Equipped with the new definition, we can define V-type BE dimension.

Let $\mathcal{H}_{\mathcal{F}}$ be the function classes of Bellman residual where $\mathcal{H}_{\mathcal{F},h}:=\{\mathcal{E}_{h}(f,g,w)~{}|~{}f,g,w\in\mathcal{F}\}$. Then the V-type Bellman-Eluder (VBE) dimension is defined as

We comment that we do not have the online version of V-type BE dimension, because the uniform sampling step in Option II is in general not compatible with the policy of the opponent.

B.2 Theoretical Guarantees

Now we are ready to present the theoretical guarantees.

where $d=\dim_{\textrm{VBE}}(\mathcal{F},1/K)$ is the VBE dimension.

Theorem 18 provides a $\sqrt{K}$ pseudo-regret guarantee in terms of VBE dimension for Algorithm 1 with Option II. The reason for calling it pseudo-regret is that in each episode, the samples are collected following a combination of $(\mu^{k},\nu^{k})$ and uniform sampling, instead of only $(\mu^{k},\nu^{k})$ as in Option I. Still, this is enough for applying the pigeonhole principle to derive the sample complexity of Golf_with_Exploiter.

Under Assumption 1 and 2, there exists an absolute constant $c$ such that for any $\epsilon>0$, choose $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$ and $\Delta=c^{\prime}(H\sqrt{|\mathcal{A}||\mathcal{B}|d\beta/K}+\epsilon)$, where $d=\dim_{\textrm{VBE}}(\mathcal{F},\epsilon/H)$ is the VBE dimension of $\mathcal{F}$, then with probability at least $1-\delta$, the output condition (Line 5) will be satistied at least once in the first $K$ episodes. Furthermore, the output policy $\mu^{\text{out}}$ of Algorithm 1 with Option II is $\mathcal{O}(\epsilon+H\sqrt{d}(\varepsilon_{\rm real}+\varepsilon_{\rm comp}))$-approximate Nash, if K\geq\Omega\big{(}(H^{2}d/\epsilon^{2})\cdot\log(H|\mathcal{F}||\mathcal{G}|d/\epsilon)\big{)} .

Appendix C Proofs for Section 3

In this section, we present the proof of Theorem 7, Corollary 8, and Theorem 11.

The following auxiliary lemma (Lemma 26 in ) will be useful.

Another useful decomposition is the value difference lemma (Lemma 1 in ).

For any function $f$ s.t. $f_{H+1}=0$ and policy $\pi$,

We begin with the proof of Theorem 11. The following two concentration lemmas help us upper bound the Bellman residuals. We defer their proofs to Appendix C.3.1 and C.3.2.

Assuming $\|Q_{h}^{\star}-\mathcal{P}_{\mathcal{F}_{h}}(Q_{h}^{\star})\|\leq\varepsilon_{\rm real}$ and $\|\mathcal{T}_{h}f_{h+1}-\mathcal{P}_{\mathcal{G}_{h}}(\mathcal{T}_{h}f_{h+1})\|\leq\varepsilon_{\rm comp}$ for all $f\in\mathcal{F}$ and $h\in[H]$, if we choose $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$ with some large absolute constant $c$ in Algorithm 1 with Option I, then with probability at least $1-\delta$, for all $(k,h)\in[K]\times[H]$, we have

$\sum_{i=1}^{k-1}{\left(f^{k}_{h}(s_{h}^{i},a_{h}^{i},b_{h}^{i})-(\mathcal{T}_{h}f_{h+1}^{k})(s_{h}^{i},a_{h}^{i},b_{h}^{i})\right)}^{2}{\leq}\mathcal{O}(\beta)$,

where $(s_{1}^{i},a_{1}^{i},,b_{1}^{i},\ldots,s_{H}^{i},a_{H}^{i},b_{H}^{i})$ denotes the trajectory sampled by following $\pi^{i}=(\mu^{i},\nu^{i})$ in the $i^{\rm th}$ episode.

Under the same condition of Lemma 22, with probability at least $1-\delta$, we have $\mathcal{P}_{\mathcal{F}}(Q^{\star})\in\mathcal{C}^{k}$ for all $k\in[K]$.

By Lemma 23, $\mathcal{P}_{\mathcal{F}}(Q^{\star})\in\mathcal{C}^{k}$. Since we choose $f^{k}$ optimistically and $\mathcal{F}$ satisfies $\varepsilon_{\rm real}$-approximate realizability,

where $(i)$ is by value difference (Lemma 21), $(ii)$ is due to $\mu^{k}=\mu_{f^{k}}$, $(iii)$ is by Azuma-Hoeffding, and $(iv)$ is by incurring Lemma 20 with $\mathcal{G}=\mathcal{H}_{\mathcal{F},h}$ (here, $\mathcal{H}_{\mathcal{F}}$ refers to the one introduced in Definition 10), $\Pi=\mathcal{D}_{\Delta,h}$, $\epsilon=1/K$ and Lemma 22. The final inequality follows from the choice of $\beta$. ∎

C.2 Proof of the Self-play Guarantee

Proving Theorem 7 requires more work because we need to develop guarantees for the sub-routine Compute_Exploiter. Similar to Lemma 22 and 23, we establish two concentration lemmas below, whose proofs are deferred to Section C.3.3 and C.3.4.

Under Assumption 1 and 2, if we choose $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$ with some large absolute constant $c$ in Algorithm 1 with Option I, then with probability at least $1-\delta$, for all $(k,h)\in[K]\times[H]$, we have

Under the same condition of Lemma 24, with probability at least $1-\delta$, we have $\mathcal{P}_{\mathcal{F}}(Q^{\mu^{k},\dagger})\in\mathcal{C}^{\mu^{k}}$ for all $k\in[K]$.

By Lemma 25, $\mathcal{P}_{\mathcal{F}}(Q^{\mu^{t},\dagger})\in\mathcal{C}^{t}$. Since we choose $f^{t}$ optimistically and $\mathcal{F}$ satisfies $\varepsilon_{\rm real}$-approximate realizability,

By Lemma 24 (b), we have for all $k\in[K]$

So we can apply Lemma 20 with $\mathcal{G}=\mathcal{H}_{\mathcal{F},h}$, $\Pi=\mathcal{D}_{\Delta,h}$, $\epsilon=1/K$ and obtain

Plugging this inequality back into (10) gives us the first upper bound.

We can also invoke Lemma 24 (a) with Jensen’s inequality, and obtain for all $k\in[K]$

Again, we can apply Lemma 20 with $\mathcal{G}=\mathcal{H}_{\mathcal{F},h}$ (here, $\mathcal{H}_{\mathcal{F}}$ refers to the one introduced in Definition 6), $\Pi=\mathcal{D}_{\mathcal{F},h}$, $\epsilon=1/K$, and obtain

Plugging this inequality back into (10) gives us the second upper bound.

Combining the two upper bounds and noticing that $k\varepsilon_{\rm real}\leq\mathcal{O}(H\sqrt{k\beta\cdot\dim_{\textrm{BE}}(\mathcal{F},1/K)})$ (because of the choice of $\beta$) conclude the proof. ∎

Now we are ready to prove the regret guarantee.

The regret can be decomposed into two terms

By Theorem 11, where the opponent’s policy $\{\nu^{k}\}_{k=1}^{K}$ can be arbitrary, $(A)$ can be upper bounded by

By Proposition 26, $(B)$ can be upper bounded by

Combining the two inequalities concludes the proof. ∎

By the standard online-to-batch reduction, we can also derive the sample complexity guarantee.

We proceed as in the proof of Theorem 7 but take $\omega=\epsilon/H$ (instead of $\omega=1/K$) every time we incur Lemma 20.

where we have used the fact that $\dim_{\textrm{OBE}}(\mathcal{F},\epsilon/H)\leq\dim_{\textrm{BE}}(\mathcal{F},\epsilon/H)$.

Comparing with the form in Theorem 7, now we have an additional $\mathcal{O}(K\epsilon)$ term, since we take $\omega=\epsilon/H$ when incurring Lemma 20.

with probability at least $1-\delta$, where $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$.

By pigeonhole prinple, there must exist some $k$ s.t. $\overline{V}^{k}-\underline{V}^{k}\leq\Delta=c^{\prime}(H\sqrt{\dim_{\textrm{BE}}(\mathcal{F},\epsilon/H)\beta/K}+\epsilon)$. Therefore, the output condition must be satisfied by some $k\in[K]$.

To make the right hand side order $\mathcal{O}(\epsilon+H\sqrt{d}(\varepsilon_{\rm real}+\varepsilon_{\rm comp}))$, it suffices to take

where $d=\dim_{\textrm{BE}}(\mathcal{F},\epsilon/H)$. ∎

C.3 Proofs of the Concentration Arguments

Consider a fixed $(k,h,f)$ tuple. For notational simplicity, we denote $z_{h}^{t}:=(s_{h}^{t},a_{h}^{t},b_{h}^{t})$. Let

and $\mathfrak{F}_{t,h}$ be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}\bigcup\{z_{1}^{t},r_{1}^{t},\ldots,z_{h}^{t}\}.$ We have

By Freedman’s inequality, we have, with probability at least $1-\delta$,

Now taking a union bound for all $(k,h,f)\in[K]\times[H]\times\mathcal{F}$, we obtain that with probability at least $1-\delta$, for all $(k,h,f)\in[K]\times[H]\times\mathcal{F}$

where $\iota=\log(HK|\mathcal{F}|/\delta)$. From now on, we will do all the analysis conditioning on this event being true.

Consider an arbitrary pair $(h,k)\in[H]\times[K]$. By the definition of $\mathcal{C}^{k}$ and Assumption 2

Putting (11) and (12) together, we obtain

which concludes the proof of inequality $(b)$.

To prove inequality $(a)$, we only need to redefine $\mathfrak{F}_{t,h}$ to be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}$ and then repeat the arguments above verbatim. ∎

C.3.2 Proof of Lemma 23

We will continue to use the notations defined in the proof of Lemma 22. To further simplify notations, we denote

Consider a fixed tuple $(k,h,g)\in[K]\times[H]\times\mathcal{G}$. Let

and $\mathfrak{F}_{t,h}$ be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}\bigcup\{z_{1}^{t},r_{1}^{t},\ldots,z_{h}^{t}\}.$ We have

By Freedman’s inequality, we have, with probability at least $1-\delta$,

Now taking a union bound for all $(k,h,g)\in[K]\times[H]\times\mathcal{G}$, we obtain that with probability at least $1-\delta$, for all $(k,h,g)\in[K]\times[H]\times\mathcal{G}$

where $\iota=\log(HK|\mathcal{G}|/\delta)$. From now on, we will do all the analysis conditioning on this event being true.

Since $\sum_{t=1}^{k}\left[(g_{h}-\mathcal{T}_{h}\hat{Q}_{h+1})(z_{h}^{t})\right]^{2}$ is nonnegative, by Cauchy-Schwarz inequality, (13) implies for all $(k,h,g)\in[K]\times[H]\times\mathcal{G}$

Plugging in the definition of $W_{t}(h,g)$ and the choice of $\beta$ completes the proof. ∎

C.3.3 Proof of Lemma 24

Recall $\mu_{f}$ denotes the Nash policy of the max-player induced by $f$. If there exist more than one induced Nash policies, we can break the tie arbitrarily so that $\mu_{f}$ is uniquely defined for each $f\in\mathcal{F}$. Denote $\Pi_{\mathcal{F}}:=\{\mu_{f}~{}|~{}f\in\mathcal{F}\}$. We have $|\Pi_{\mathcal{F}}|\leq|\mathcal{F}|$.

We prove inequality $(b)$ first. Consider a fixed tuple $(k,h,f,\mu)\in[K]\times[H]\times\mathcal{F}\times\Pi_{\mathcal{F}}$. Again we denote $z_{h}^{t}:=(s_{h}^{t},a_{h}^{t},b_{h}^{t})$. Let

and $\mathfrak{F}_{t,h}$ be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}\bigcup\{z_{1}^{t},r_{1}^{t},\ldots,z_{h}^{t}\}.$ We have

By Freedman’s inequality, we have, with probability at least $1-\delta$,

Now taking a union bound for all $(k,h,f,\mu)\in[K]\times[H]\times\mathcal{F}\times\Pi_{\mathcal{F}}$, we obtain that with probability at least $1-\delta$, for all $(k,h,f,\mu)\in[K]\times[H]\times\mathcal{F}\times\Pi_{\mathcal{F}}$

where $\iota=\log(HK|\mathcal{F}|/\delta)$. From now on, we will do all the analysis conditioning on this event being true.

Consider an arbitrary pair $(h,k)\in[H]\times[K]$. By the definition of $\mathcal{C}^{k}$ and Assumption 2

Putting (14) and (15) together, we obtain

which concludes the proof of inequality $(b)$.

To prove inequality $(a)$, we only need to redefine $\mathfrak{F}_{t,h}$ to be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}$ and then repeat the arguments above verbatim. ∎

C.3.4 Proof of Lemma 25

Recall $\mu_{f}$ denotes the Nash policy of the max-player induced by $f$. If there exist more than one induced Nash policies, we can break the tie arbitrarily so that $\mu_{f}$ is uniquely defined for each $f\in\mathcal{F}$. Denote $\Pi_{\mathcal{F}}:=\{\mu_{f}~{}|~{}f\in\mathcal{F}\}$. We have $|\Pi_{\mathcal{F}}|\leq|\mathcal{F}|$.

Consider a fixed tuple $(k,h,g,\mu)\in[K]\times[H]\times\mathcal{G}\times\Pi_{\mathcal{F}}$. Let

and $\mathfrak{F}_{t,h}$ be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}\bigcup\{z_{1}^{t},r_{1}^{t},\ldots,z_{h}^{t}\}.$ We have

By Freedman’s inequality, we have, with probability at least $1-\delta$,

Now taking a union bound for all $(k,h,g,\mu)\in[K]\times[H]\times\mathcal{G}\times\Pi_{\mathcal{F}}$, we obtain that with probability at least $1-\delta$, for all $(k,h,g,\mu)\in[K]\times[H]\times\mathcal{G}\times\Pi_{\mathcal{F}}$

where $\iota=\log(HK|\mathcal{G}||\mathcal{F}|/\delta)$. From now on, we will do all the analysis conditioning on this event being true.

Since $\sum_{t=1}^{k}[(g_{h}-Q_{h}^{\mu,\dagger})(z_{h}^{t})]^{2}$ is nonnegative, (16) implies for all $(k,h,g,\mu)\in[K]\times[H]\times\mathcal{G}\times\Pi_{\mathcal{F}}$

By choosing $\mu=\mu^{k}$, we have for all $(k,h)\in[K]\times[H]$

We conclude the proof by recalling $\beta=\Theta\left(\log(HK|\mathcal{G}||\mathcal{F}|/\delta)+k\varepsilon_{\rm real}^{2}++k\varepsilon_{\rm comp}^{2}\right)$. ∎

Appendix D Proofs for Section 4

In this section, we will first generalize Bellman rank to the setting of Markov Game. Then we show any problems of low Bellman rank also have low BE dimension. Finally, we prove all the examples in Section 4 have low Bellman rank, and thus low BE dimension.

Denote $\Pi_{\mathcal{F}}:=\{(\mu_{f},\nu_{f,g})~{}\mid~{}f,g\in\mathcal{F}\}$, which is exactly the policy class that induces $\mathcal{D}_{\mathcal{F}}$.

The $\epsilon$-effective Bellman rank is the minimum integer $d$ so that

There exists $\phi_{h}:\Pi_{\mathcal{F}}\rightarrow\mathcal{H}$ and $\psi_{h}:\mathcal{F}\rightarrow\mathcal{H}$ for each $h\in[H]$ where $\mathcal{H}$ is a separable Hilbert space, such that for any $\pi\in\Pi$, $f,g\in\mathcal{F}$, the average Bellman error

where $\|\psi_{h}(f,g)\|_{\mathcal{H}}\leq 1$.

$d=\max_{h\in[H]}d_{\rm eff}(\mathcal{X}_{h}(\phi,\mathcal{F}),\epsilon)$ where $\mathcal{X}_{h}(\phi,\mathcal{F})=\{\phi_{h}(\pi):\ \pi\in\Pi_{\mathcal{F}}\}$.

If an MG with function class $\mathcal{F}$ has Q-type $\epsilon$-effective Bellman rank $d$, then

For notational simplicity, define $x_{i}=\phi_{h}(\pi^{i})$ and $\theta_{i}=\psi_{h}(f^{i},g^{i})$. Then

As a result, we should have $\|x_{t}\|_{\Sigma_{t}^{-1}}^{2}\geq 1/2$ for all $t\in[n]$. Now we can apply the standard log-determinant argument,

Choose $n=d_{\rm eff}(\mathcal{X}_{h}(\phi,\mathcal{F}),\epsilon)$ that is the minimum positive integer satisfying

This leads to a contradiction because $0.5>e^{e^{-1}}-1$. So we must have $n\leq d_{\rm eff}(\mathcal{X}_{h}(\psi,\mathcal{F}),\epsilon).$ ∎

Similarly, we can define V-type Bellman rank, and prove it is upper bounded by V-type BE dimension.

The $\epsilon$-effective Bellman rank is the minimum integer $d$ so that

There exists $\phi_{h}:\Pi_{\mathcal{F}}\rightarrow\mathcal{H}$ and $\psi_{h}:\mathcal{F}\rightarrow\mathcal{H}$ for each $h\in[H]$ where $\mathcal{H}$ is a separable Hilbert space, such that for any $\pi\in\Pi$, $f,g,w\in\mathcal{F}$, the average Bellman error

where $\|\psi_{h}(f,g,w)\|_{\mathcal{H}}\leq 1$.

$d=\max_{h\in[H]}d_{\rm eff}(\mathcal{X}_{h}(\phi,\mathcal{F}),\epsilon)$ where $\mathcal{X}_{h}(\phi,\mathcal{F})=\{\phi_{h}(\pi):\ \pi\in\Pi_{\mathcal{F}}\}$.

If an MG with function class $\mathcal{F}$ has V-type $\epsilon$-effective Bellman rank $d$, then

We omit the proof here because it is basically the same as Proposition 28.

Below, we prove the problems introduced in Section 4 have either low Q-type or low V-type Bellman rank. Therefore, by Proposition 28 and 30, they also have low Q-type or low V-type BE dimension.

where the LHS only depends on $\pi$, and the RHS only depends on $f,g$. ∎

Consider two arbitrary $\theta_{h},\theta_{h+1}\in B_{d}(R)$ and $g\in\mathcal{F}$. By self-completeness, there exists $\theta_{h}^{g}\in B_{d}(R)$ so that $\mathcal{T}_{h}^{\mu_{g}}(\phi_{h+1}^{\top}\theta_{h+1})=\phi_{h}^{\top}\theta_{h}^{g}$. Therefore, we have

where the LHS only depends on $\pi$, and the RHS only depends on $\theta_{h},\theta_{h+1},g$. ∎

Consider two arbitrary $\theta_{h},\theta_{h+1}\in B_{\mathcal{H}}(R)$ and $g\in\mathcal{F}$. By self-completeness, there exists $\theta_{h}^{g}\in B_{\mathcal{H}}(R)$ so that $\mathcal{T}_{h}^{\mu_{g}}(\phi_{h+1}^{\top}\theta_{h+1})=\phi_{h}^{\top}\theta_{h}^{g}$. Therefore, we have

where the LHS only depends on $\pi$, and the RHS only depends on $\theta_{h},\theta_{h+1},g$. ∎

Let $d(i)$ denote the distribution of state $s$ given $q(s)=i$. For any policy $\pi$ and $f,g,w\in\mathcal{F}$

where the LHS only depends on $\pi$ while the RHS only depends on $f,g,w$. Both of them are $m$-dimensional. ∎

The case $h=1$ is trivial. We only need to consider $h\geq 2$. For any policy $\pi$ and $f,g,w\in\mathcal{F}$

where the LHS only depends on $\pi$ while the RHS only depends on $f,g,w$. By the regularization condition of Kernel MGs, the norm of the RHS is bounded by $2R+1$. ∎

Appendix E Proofs for Appendix B

In this section, we present the proof of Theorem 18 and Corollary 19. The techniques are basically the same as those in Appendix C. Please notice that whenever coming across $\mathcal{D}_{\mathcal{F}}$ and $\mathcal{D}_{\Delta}$ in this section, we use their definitions introduced in Appendix B.

To begin with, we have the following concentration lemma (akin to Lemma 24 and 25) for the sub-routine Compute_Exploiter under the samples collected with Option II.

Under Assumption 1 and 2, if we choose $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$ with some large absolute constant $c$ in Algorithm 1 with Option II, then with probability at least $1-\delta$, for all $(k,h)\in[K]\times[H]$, we have

$\mathcal{P}_{\mathcal{F}}(Q^{\mu^{k},\dagger})\in\mathcal{C}^{\mu^{k}}$,

To prove (a), we only need to redefine the filtration $\mathfrak{F}_{t,h}$ in Appendix C.3.3 to be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}$ where $z_{h}^{i}=(s_{h}^{i},a_{h}^{i},b_{h}^{i})$, and repeat the arguments therein verbatim. Similarly, for (b), we only need to redefine $\mathfrak{F}_{t,h}$ in Appendix C.3.3 to be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}\bigcup\{z_{1}^{t},r_{1}^{t},\ldots,z_{h-1}^{t},r_{h-1}^{t},s_{h}^{t}\}$. And the proof of (c) is the same as that of Lemma 25 in Appendix C.3.4. ∎

By Jensen’s inequality and Lemma 31 (b), we have for all $k\in[K]$

So we can apply Lemma 20 with $\mathcal{G}=\mathcal{H}_{\mathcal{F},h}$ (here, $\mathcal{H}_{\mathcal{F}}$ refers to the one introduced in Definition 17), $\Pi=\mathcal{D}_{\Delta,h}$, $\epsilon=1/K$ and obtain

Similarly by using Lemma 31 (a), we can show

Putting all relations together as in Proposition 26 and noticing that

Equipped with the regret guarantee for Compute_Exploiter, we are ready to bound the pseudo-regret for the main algorithm Golf_with_Exploiter. To begin with, we have the following concentration lemma (akin to Lemma 22 and 23) under the samples collected with Option II.

Under Assumption 1 and 2, if we choose $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$ with some large absolute constant $c$ in Algorithm 1, then with probability at least $1-\delta$, for all $(k,h)\in[K]\times[H]$, we have

$\sum_{i=1}^{k-1}\sum_{(a,b)\in\mathcal{A}\times\mathcal{B}}{\left((f^{k}_{h}-\mathcal{T}_{h}f_{h+1}^{k})(s_{h}^{i},a,b)\right)}^{2}{\leq}\mathcal{O}(|\mathcal{A}||\mathcal{B}|\beta)$,

$\mathcal{P}_{\mathcal{F}}(Q^{\star})\in\mathcal{C}^{k}$,

where $s_{h}^{i}$ denotes the state at step h collected following $\pi^{i}$ until step $h$ in the $i^{\rm th}$ outer iteration.

To prove (a), we only need to redefine the filtration $\mathfrak{F}_{t,h}$ in Appendix C.3.1 to be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}$ where $z_{h}^{i}=(s_{h}^{i},a_{h}^{i},b_{h}^{i})$, and repeat the arguments therein verbatim. Similarly, for (b), we only need to redefine $\mathfrak{F}_{t,h}$ in Appendix C.3.1 to be the filtration induced by $\{z_{1}^{i},r_{1}^{i},\ldots,z_{H}^{i},r_{H}^{i}\}_{i=1}^{t-1}\bigcup\{z_{1}^{t},r_{1}^{t},\ldots,z_{h-1}^{t},r_{h-1}^{t},s_{h}^{t}\}$. And the proof of (c) is the same as that of Lemma 25 in Appendix C.3.2. ∎

The regret can be decomposed into two terms

By Proposition 32, $(B)$ can be upper bounded by with high probability,

So it remains to control $(A)$. By minicking the proof of Theorem 11, we have

By Jensen’s inequality and Lemma 33 (b), we have for all $k\in[K]$

So we can apply Lemma 20 with $\mathcal{G}=\mathcal{H}_{\mathcal{F},h}$ (here, $\mathcal{H}_{\mathcal{F}}$ refers to the one introduced in Definition 17), $\Pi=\mathcal{D}_{\Delta,h}$, $\epsilon=1/K$ and obtain

Similarly by using Lemma 33 (a), we can show

Putting all relations together completes the proof. ∎

By an standard online-to-batch reduction, we can also prove the sample complexity guarantee.

We proceed as in the proof of Theorem 18 but take $\omega=\epsilon/H$ (instead of $\omega=1/K$) every time we incur Lemma 20.

Comparing with the form in Theorem 7, now we have an additional $\mathcal{O}(K\epsilon)$ term, since we take $\omega=\epsilon/H$ when incurring Lemma 20.

with probability at least $1-\delta$, where $\beta=c\cdot(\log(KH|\mathcal{F}||\mathcal{G}|/\delta)+K\varepsilon_{\rm comp}^{2}+K\varepsilon_{\rm real}^{2})$.

By pigeonhole prinple, there must exist some $k$ s.t.

Therefore, the output condition must be satisfied by some $k\in[K]$.

To make the right hand side order $\mathcal{O}(\epsilon+H\sqrt{d}(\varepsilon_{\rm real}+\varepsilon_{\rm comp}))$, it suffices to take

where $d=\dim_{\textrm{VBE}}(\mathcal{F},\epsilon/H)$. ∎