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

Chi JinQinghua LiuTiancheng Yu

article2022ICML61 citations

Develops an exploiter-driven self-play algorithm alongside a multi-agent Bellman-Eluder dimension to provide provable sample-efficiency guarantees for learning Nash equilibria in two-player zero-sum Markov games with general function approximation.

Listen

Multi-agent reinforcement learning (MARL) has demonstrated remarkable empirical success across complex domains such as competitive games, robotics, and autonomous driving. However, practical applications involve massive state spaces that require function approximation, such as neural networks, to represent policies or value functions. While single-agent reinforcement learning with general function approximation is well understood theoretically, existing multi-agent theory has remained largely limited to tabular domains or restricted linear models. This gap persists because competitive settings introduce non-stationary opponents that continuously adapt, invalidating standard exploration techniques that rely on unrealistic assumptions like optimistic closure.

The article establishes a rigorous theoretical foundation for MARL by determining whether sample-efficient learning is achievable in two-player zero-sum Markov games using general function approximation. Specifically, it introduces a novel framework that guarantees finding an approximate Nash equilibrium policy—a strategy profile where neither player benefits by deviating—using a number of data samples that scales polynomially with problem complexity rather than exponentially with the state space size.

To achieve this, the authors develop an algorithmic framework called GOLF WITH EXPLOITER and propose a new structural complexity metric termed the multi-agent Bellman-Eluder (BE) dimension. The methodology departs from traditional self-play by pairing an optimistic primary learner with an auxiliary exploiter subroutine. In each training round, the main player executes an optimistic strategy based on historical data confidence sets, while the exploiter computes an approximate best response designed specifically to expose and penalize weaknesses in the primary player's policy. The analysis evaluates theoretical performance bounds across both self-play and adversarial online settings, establishing validity under generalized completeness and realizability conditions.

The article presents several primary findings that advance reinforcement learning theory. First, any two-player zero-sum Markov game exhibiting a low multi-agent BE dimension can be solved to an approximate Nash equilibrium with sample efficiency that is completely independent of the state space size. Second, the exploiter mechanism guarantees that the primary player's cumulative regret scales with the square root of total rounds, providing strong convergence guarantees even against fully adversarial opponents. Third, the framework subsumes a broad range of rich problem classes, including tabular games, kernel function approximations, rich observation environments with hidden latent states, and kernel feature selection. Fourth, for linear Markov games, the proposed approach improves sample complexity over existing state-of-the-art benchmarks by reducing the dependence on feature dimension from a cubic rate to a quadratic rate.

These findings carry significant implications for the design and deployment of competitive autonomous systems. By eliminating the reliance on restrictive structural assumptions like optimistic closure, the framework proves that strategic exploration can be decoupled from symmetric opponent assumptions. This substantially lowers the theoretical risk of policies failing when encountering adversarial edge cases in real-world deployments. Furthermore, the demonstrated sample efficiency confirms that data collection budgets for training multi-agent systems need not scale with environment size, directly lowering the simulated or empirical data gathering costs required to achieve robust performance.

For technical leaders and researchers, the article recommends adopting exploiter-based curricula when designing exploration strategies for multi-agent training pipelines rather than relying strictly on symmetric self-play. However, because the current framework guarantees statistical efficiency but remains computationally intractable for general non-linear function classes, immediate deployment requires developing practical optimization heuristics that approximate the confidence-set planning steps. Future work should prioritize designing computationally efficient approximations and exploring extensions to multi-player, general-sum game environments.

Confidence in these mathematical findings is high, as the sample complexity and regret bounds are rigorously derived using concentration inequalities and covering number techniques that accommodate function approximation misspecification. Nevertheless, practitioners must exercise caution regarding boundary conditions: the theoretical guarantees assume that the function classes satisfy approximate completeness and realizability, and practical performance will ultimately depend on how well empirical neural networks can approximate these underlying structural requirements in polynomial compute time.

Massachusetts Institute of Technology Princeton University function approximation kernel function nash equilibrium multi-agent reinforcement learning large state spaces exploiter framework

arXiv: 2106.03352

Paper: Markov Games as a Framework for Multi-Agent Reinforcement Learning, Michael L. Littman (1994). Littman’s Markov-game formulation and minimax-Q establish the two-player zero-sum setting that GOLF WITH EXPLOITER extends beyond tabular learning.
Paper: Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms, Kaiqing Zhang et al. (2019). This overview maps the non-stationarity and equilibrium challenges in MARL that motivate the source’s exploiter-based guarantees.
Paper: R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning, R. Brafman et al. (2001). R-MAX provides an early provable optimism-based exploration approach for stochastic games, clarifying the exploration framework the source generalizes.
Paper: Near-optimal Regret Bounds for Reinforcement Learning, Thomas Jaksch et al. (2008). UCRL2’s confidence-set optimism and regret analysis provide useful single-agent foundations for understanding the source’s optimistic learner and guarantees.

No sufficiently relevant recommendations were found.

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

Abstract

Modern reinforcement learning (RL) commonly engages practical problems with large state spaces, where function approximation must be deployed to approximate either the value function or the policy. While recent progresses in RL theory address a rich set of RL problems with general function approximation, such successes are mostly restricted to the single-agent setting. It remains elusive how to extend these results to multi-agent RL, especially in the face of new game-theoretical challenges. This paper considers two-player zero-sum Markov Games (MGs). We propose a new algorithm that can provably find the Nash equilibrium policy using a polynomial number of samples, for any MG with low multi-agent Bellman-Eluder dimension—a new complexity measure adapted from its single-agent version (Jin et al., 2021). A key component of our new algorithm is the exploiter, which facilitates the learning of the main player by deliberately exploiting her weakness. Our theoretical framework is generic, which applies to a wide range of models including but not limited to tabular MGs, MGs with linear or kernel function approximation, and MGs with rich observations.

Topics

function approximation kernel function nash equilibrium single-agent software agents state space value functions agent based

Keywords

multi-agent reinforcement learning large state spaces exploiter framework multi-agent BE dimension Markov games Nash Bellman operator Nash policies stochastic games extensive-form games

1. Introduction
2. Related Works
3. Preliminaries
3.1. Function Approximation
4. Main Results
4.1. Algorithm
4.2. Complexity Measure
4.3. Theoretical Guarantees
4.4. Adversarial Opponents
5. Examples
6. Conclusion
Acknowledgements
References
A. Discussion on Technical Challenges
B. V-type Bellman Eluder Dimension
B.1. Complexity Measure
B.2. Theoretical Guarantees
C. Proofs for Section 4
C.1. Proof of the Online Guarantee
C.2. Proof of the Self-play Guarantee
C.3. Proofs of the Concentration Arguments
C.3.1. Proof of Lemma C.3
C.3.2. Proof of Lemma C.4
C.3.3. Proof of Lemma C.5
C.3.4. Proof of Lemma C.6
D. Proofs for Section 5
D.1. Proofs for Examples
E. Proofs for Appendix B

Knowls

Knowl 1 — GOLF WITH EXPLOITER: optimistic self-play with a best-response learner
algorithm
GOLF WITH EXPLOITER learns in a finite-horizon, two-player zero-sum Markov game with horizon $H$ and fixed initial state $s_1$ . Its inputs are a main action-value function class $\mathcal F=\mathcal F_1\times\cdots\times\mathcal F_H$ , an auxiliary regression class $\mathcal G=\mathcal G_1\times\cdots\times\mathcal G_H$ , an episode budget $K$ , a confidence tolerance $\beta$ , and a stopping threshold $\Delta$ . For each step $h$ , it stores transitions in a dataset $D_h$ and maintains a confidence set $\mathcal C$ of candidate functions.

For a candidate function $f$ , let $V_{f,h}(s)=\max_{\mu\in\Delta A}\min_{\nu\in\Delta B}\mu^\top f_h(s)\nu$ be its induced game value, and let $V^{\mu}_{f,h}(s)=\min_{\nu\in\Delta B}\mu_h(s)^\top f_h(s)\nu$ when the max-player policy $\mu$ is fixed. Here $\Delta A$ and $\Delta B$ are the probability simplices over the players' action sets. Define squared losses on a dataset of tuples $(s,a,b,r,s')$ by
$L_{D_h}(\xi_h,\zeta_{h+1})=\sum_{(s,a,b,r,s')\in D_h}[\xi_h(s,a,b)-r-V_{\zeta,h+1}(s')]^2,$
and define $L^{\mu}_{D_h}$ by replacing $V_{\zeta,h+1}$ with $V^{\mu}_{\zeta,h+1}$ . The main confidence set retains functions satisfying, for every $h$ , $L_{D_h}(f_h,f_{h+1})\leq\inf_{g\in\mathcal G_h}L_{D_h}(g,f_{h+1})+\beta$ . The exploiter confidence set uses the analogous inequality with $L^{\mu}_{D_h}$ .

In each episode, the algorithm (1) chooses $f^k\in\mathcal C$ maximizing $V_{f,1}(s_1)$ and plays its induced max-player policy $\mu^k$ ; (2) forms the exploiter confidence set for this fixed $\mu^k$ , chooses a function $\tilde f^k$ in that set minimizing $V^{\mu^k}_{f,1}(s_1)$ , and plays the min-player best response to $\mu^k$ under $\tilde f^k$ ; (3) stops and outputs $\mu^k$ if the optimistic value minus the exploiter's value estimate is less than $\Delta$ ; otherwise, it collects data and updates $\mathcal C$ using the main confidence constraint. The standard data-collection option follows $(\mu^k,\nu^k)$ for one full trajectory and adds its step- $h$ transition to $D_h$ . An alternative option collects one trajectory per step, following $(\mu^k,\nu^k)$ before that step and selecting a uniformly random action pair at the selected step; only that step's transition is added to its dataset. The method's optimistic planning and confidence-set optimization are not computationally efficient in general.
Knowl 2 — Multi-agent Bellman–Eluder dimension
definition
For a finite-horizon two-player zero-sum Markov game, let $\mathcal F$ be a class of candidate action-value functions. Each $g\in\mathcal F$ induces a max-player Nash policy $\mu_g$ . For $f\in\mathcal F$ , define the $\mu_g$ -Bellman target by $[T_h^{\mu_g}f](s,a,b)=r_h(s,a,b)+\mathbb E_{s'\sim P_h(\cdot\mid s,a,b)}V^{\mu_g}_{f,h+1}(s')$ , where $V^{\mu_g}_{f,h}(s)=\min_{\nu\in\Delta B}\mu_{g,h}(s)^\top f_h(s)\nu$ . The step- $h$ residual class is $\mathcal H_{\mathcal F,h}=\{f_h-T_h^{\mu_g}f:f,g\in\mathcal F\}$ , with residuals viewed as functions on $\mathcal S\times\mathcal A\times\mathcal B$ .

For a function class $\mathcal H$ and distributions $\rho_1,\ldots,\rho_n$ over its domain, a distribution $\rho_i$ is $\eta$ -independent of its predecessors if some $u\in\mathcal H$ satisfies $\sqrt{\sum_{j<i}(\mathbb E_{\rho_j}u)^2}\leq\eta$ while $|\mathbb E_{\rho_i}u|>\eta$ . The distributional Eluder dimension $\dim_{\rm DE}(\mathcal H,\Pi,\epsilon)$ is the length of the longest sequence from $\Pi$ in which every distribution is independent of its predecessors at some common tolerance at least $\epsilon$ .

Two distribution families are used at step $h$ : point masses on individual state-action pairs, $\mathcal D_{\Delta,h}=\{\delta_{(s,a,b)}\}$ , and distributions over state-action pairs generated by policies $(\mu_f,\nu_{f,g})$ for $f,g\in\mathcal F$ , where $\nu_{f,g}$ is a min-player best response to $\mu_f$ according to $g$ . The multi-agent Bellman–Eluder dimension is
$\dim_{\rm BE}(\mathcal F,\epsilon)=\max_{h\in[H]}\min_{\mathcal D_h\in\{\mathcal D_{\Delta,h},\mathcal D_{\mathcal F,h}\}}\dim_{\rm DE}(\mathcal H_{\mathcal F,h},\mathcal D_h,\epsilon).$
It measures how many distinguishable Bellman residuals can arise under either pointwise evaluation or policy-generated sampling distributions, and controls the paper's self-play guarantees without depending directly on the number of states.
Knowl 3 — Approximate realizability and completeness conditions
assumption
Let $Q_h^*$ be the Nash-equilibrium action-value function at step $h$ , and let $Q_h^{\mu_f,\dagger}$ be the action-value function when the max-player uses the policy $\mu_f$ induced by $f\in\mathcal F$ and the min-player best responds. The paper assumes approximate realizability: for every $f\in\mathcal F$ and step $h$ , the class $\mathcal F_h$ contains approximations to both $Q_h^*$ and $Q_h^{\mu_f,\dagger}$ with sup-norm error at most $\epsilon_{\rm real}$ .

It also assumes approximate completeness. For every $f,f'\in\mathcal F$ and step $h$ , the auxiliary class $\mathcal G_h$ contains sup-norm approximations, with error at most $\epsilon_{\rm comp}$ , to both the Nash Bellman target $T_h f_{h+1}=r_h+P_hV_{f,h+1}$ and the policy Bellman target $T_h^{\mu_f}f'=r_h+P_hV^{\mu_f}_{f',h+1}$ . Here $P_hV(s,a,b)$ denotes the expectation of $V(s')$ under the game's next-state distribution given $(s,a,b)$ ; $V_f$ is the value from the matrix game defined by $f$ , and $V^{\mu_f}_{f'}$ is the value when the max-player policy is fixed to $\mu_f$ . These assumptions allow misspecified function classes when the approximation errors are nonzero. Infinite classes can be handled through finite sup-norm coverings, with the approximation errors enlarged by the covering accuracy.
Knowl 4 — Self-play regret guarantee
theoretical result
Consider $K$ episodes of a finite-horizon, two-player zero-sum Markov game with fixed initial state $s_1$ . Suppose the candidate and auxiliary function classes satisfy approximate realizability and completeness: the Nash action-value function and every induced max-policy's best-response action-value function are approximated in $\mathcal F$ within sup-norm error $\epsilon_{\rm real}$ , and the Nash and induced-policy Bellman targets of functions in $\mathcal F$ are approximated in $\mathcal G$ within $\epsilon_{\rm comp}$ . Run GOLF WITH EXPLOITER using its full-trajectory sampling option and
$\beta=c\bigl(\log(KH|\mathcal F||\mathcal G|/\delta)+K\epsilon_{\rm comp}^2+K\epsilon_{\rm real}^2\bigr),$
where $c$ is a sufficiently large absolute constant and $\delta\in(0,1]$ . With probability at least $1-\delta$ , for every $k\leq K$ the max-player's cumulative best-response regret satisfies
$\operatorname{Reg}(k)=\sum_{t=1}^{k}\bigl[V_1^*(s_1)-V_1^{\mu^t,\dagger}(s_1)\bigr]\leq O\!\left(H\sqrt{d k\beta}\right),\qquad d=\dim_{\rm BE}(\mathcal F,1/K).$
Here $V_1^*$ is the Nash value and $V_1^{\mu^t,\dagger}$ is the value of the max-player's episode- $t$ policy against its best response. Thus low multi-agent Bellman–Eluder dimension yields sublinear regret, with no direct dependence on the state-space size.
Knowl 5 — Episode complexity for finding an approximate Nash policy
theoretical result
Under approximate realizability and completeness, GOLF WITH EXPLOITER can stop when its optimistic value estimate and exploiter value estimate differ by less than a threshold. Let $\epsilon>0$ , $\delta\in(0,1]$ , and $d=\dim_{\rm BE}(\mathcal F,\epsilon/H)$ . With $\beta=c(\log(KH|\mathcal F||\mathcal G|/\delta)+K\epsilon_{\rm comp}^2+K\epsilon_{\rm real}^2)$ and $\Delta=c'(H\sqrt{d\beta/K}+\epsilon)$ for absolute constants $c,c'$ , the stopping condition is met in one of the first $K$ episodes with probability at least $1-\delta$ . If
$K\geq\Omega\!\left(\frac{H^2d}{\epsilon^2}\log\frac{H|\mathcal F||\mathcal G|d}{\epsilon}\right),$
the returned max-player policy is $O(\epsilon+H\sqrt d\,(\epsilon_{\rm real}+\epsilon_{\rm comp}))$ -approximate Nash: its value against a best response is within that amount of the Nash value. For finite classes, this is, up to logarithmic factors, $H^2\dim_{\rm BE}(\mathcal F,\epsilon)/\epsilon^2$ episodes, independent of the number of states. The same sample order applies to computing an approximate Nash policy for the min-player by symmetry.
Knowl 6 — Regret against an adversarial opponent
theoretical result
In the online setting, the learner controls only the max-player and the min-player may choose an arbitrary, adaptively changing policy in each episode. Assume that for every step $h$ the Nash action-value function $Q_h^*$ is within $\epsilon_{\rm real}$ in sup norm of its projection onto $\mathcal F_h$ , and every Nash Bellman target $T_hf_{h+1}$ , for $f\in\mathcal F$ , is within $\epsilon_{\rm comp}$ of its projection onto $\mathcal G_h$ . Define the online Bellman–Eluder dimension using the residual class $\{f_h-T_hf:f\in\mathcal F\}$ and only point-mass distributions on state-action pairs; write it as $d_{\rm on}=\dim_{\rm OBE}(\mathcal F,1/K)$ .

If GOLF WITH EXPLOITER uses the confidence parameter $\beta=c(\log(KH|\mathcal F||\mathcal G|/\delta)+K\epsilon_{\rm comp}^2+K\epsilon_{\rm real}^2)$ for a sufficiently large absolute constant $c$ , then, with probability at least $1-\delta$ , for every $k\leq K$ ,
$\sum_{t=1}^{k}\bigl[V_1^*(s_1)-V_1^{\mu^t,\nu^t}(s_1)\bigr]\leq O\!\left(H\sqrt{d_{\rm on}k\beta}\right),$
where $\nu^t$ is the adversary's policy in episode $t$ . This guarantee compares the learner's reward against the actual opponent, not against that opponent's best response, and holds under weaker function-class conditions than the self-play guarantee.
Knowl 7 — V-type Bellman–Eluder dimension and uniformly randomized sampling
theoretical result
A state-based variant of the multi-agent Bellman–Eluder dimension supports an alternative sampling procedure: at each step $h$ , collect a separate trajectory that follows the current policy pair before step $h$ and selects a uniformly random action pair at step $h$ , recording the transition at that step. For $f,g,w\in\mathcal F$ , let $\mu_g$ be the max-player policy induced by $g$ , and let $\nu_{g,w}$ be its min-player best response according to $w$ . Define the state residual $E_h(f,g,w)(s)$ as the expectation of $(f_h-T_h^{\mu_g}f)(s,a,b)$ over $(a,b)\sim\mu_{g,h}(s)\times\nu_{g,w,h}(s)$ . The V-type residual class consists of these functions on states. Its distribution families are point masses on states and state distributions generated by the policy pairs $(\mu_f,\nu_{f,g})$ ; the V-type dimension $d_{\rm VBE}(\mathcal F,\epsilon)$ is the maximum over steps of the smaller distributional Eluder dimension over these two families.

Under approximate realizability and completeness, the uniformly randomized sampling version of GOLF WITH EXPLOITER has, with high probability, pseudo-regret bounded for every $k\leq K$ by
$\sum_{t=1}^{k}\bigl[V_1^*(s_1)-V_1^{\mu^t,\dagger}(s_1)\bigr] \leq O\!\left(H\sqrt{|\mathcal A||\mathcal B|\,d_{\rm VBE}(\mathcal F,1/K)\,k\beta}\right),$
where $\beta=c(\log(KH|\mathcal F||\mathcal G|/\delta)+K\epsilon_{\rm comp}^2+K\epsilon_{\rm real}^2)$ . The action-set factor arises because this procedure explores joint actions uniformly; its regret is called pseudo-regret because the data-collection actions include this additional randomization.
Knowl 8 — Linear function approximation has low multi-agent BE dimension
empirical result
Let each step's action-value class be $\mathcal F_h=\{(s,a,b)\mapsto\phi_h(s,a,b)^\top\theta:\theta\in\mathbb R^d,\ \|\theta\|_2\leq R\}$ , where $\phi_h$ maps state-action triples into the unit Euclidean ball. Suppose the class is self-complete: applying the induced-policy Bellman operator $T_h^{\mu_f}$ to any next-step function in $\mathcal F_{h+1}$ yields a function in $\mathcal F_h$ , for every $f\in\mathcal F$ . This condition implies the approximate realizability and completeness needed by the learning guarantees. Under self-completeness,
$\dim_{\rm BE}(\mathcal F,\epsilon)\leq O\!\left(d\log(1+R/\epsilon)\right).$
This function-approximation setting is broader than Markov games whose transition and reward models are themselves linear: the stated condition concerns Bellman closure of the value-function class. For games with linear transitions and rewards, the paper consequently obtains an $\widetilde O(H^2d^2/\epsilon^2)$ episode bound for an $\epsilon$ -approximate Nash policy, improving the previously reported cubic dependence on feature dimension.
Knowl 9 — Kernel value-function approximation is controlled by effective dimension
theoretical result
Let $\mathcal H$ be a decomposable Hilbert space and consider action-value functions $f_h(s,a,b)=\langle\phi_h(s,a,b),\theta\rangle_{\mathcal H}$ , with $\|\phi_h(s,a,b)\|_{\mathcal H}\leq1$ and $\|\theta\|_{\mathcal H}\leq R$ . Assume self-completeness: every induced-policy Bellman update of a function in the next-step class belongs to the current-step class. For each step define $X_h=\{\mathbb E_{\rho}[\phi_h(s,a,b)]:\rho\in\mathcal D_{\mathcal F,h}\}$ , where $\mathcal D_{\mathcal F,h}$ is the family of state-action distributions generated by the policy pairs used in the multi-agent BE definition.

For a feature set $Z$ in a Hilbert space, its $\eta$ -effective dimension is the smallest integer $n$ such that
$\sup_{z_1,\ldots,z_n\in Z}\frac{1}{n}\log\det\!\left(I+\frac{1}{\eta^2}\sum_{i=1}^n z_i z_i^*\right)\leq e^{-1},$
where $z_i z_i^*$ is the rank-one operator induced by $z_i$ . Under self-completeness, the multi-agent BE dimension obeys
$\dim_{\rm BE}(\mathcal F,\epsilon)\leq\max_{h\in[H]}\operatorname{deff}\!\left(X_h,\frac{\epsilon}{2R+1}\right).$
Thus the guarantee can depend on the effective dimension of policy-generated feature expectations rather than the ambient dimension of the Hilbert space; in finite-dimensional Euclidean space the effective-dimension term is bounded, up to logarithmic factors, by the feature dimension.
Knowl 10 — Tabular Markov games have low multi-agent BE dimension
theoretical result
For a finite state set $\mathcal S$ and finite joint action set $\mathcal A\times\mathcal B$ , every candidate action-value function class $\mathcal F\subseteq(\mathcal S\times\mathcal A\times\mathcal B\to[0,1])$ has multi-agent Bellman–Eluder dimension bounded by
$\dim_{\rm BE}(\mathcal F,\epsilon)\leq O\!\left(|\mathcal S||\mathcal A||\mathcal B|\log(1+1/\epsilon)\right).$
The bound follows from the finite number of state-action triples and applies to any such function class, rather than requiring a particular tabular parameterization. Substituting this bound into the generic learning results recovers guarantees whose complexity scales with the number of state-action triples.
Knowl 11 — Rich observations with few effective states have low V-type BE dimension
theoretical result
Suppose a Markov game has an unknown decoder $q:\mathcal S\to[m]$ such that states mapped to the same effective state have identical reward and transition behavior for every step and joint action. The physical state space may be large, but the number $m$ of effective states is small. For any candidate action-value function class $\mathcal F\subseteq(\mathcal S\times\mathcal A\times\mathcal B\to[0,1])$ , the paper establishes
$\dim_{\rm VBE}(\mathcal F,\epsilon)\leq O\!\left(m\log(1+1/\epsilon)\right),$
where $\dim_{\rm VBE}$ is the state-based Bellman–Eluder dimension used with uniformly randomized joint-action sampling. Consequently, the learning complexity can depend on the number of behaviorally distinct state classes rather than the cardinality of the observed state space.
Knowl 12 — Kernel feature selection admits an effective-dimension VBE bound
theoretical result
Consider a kernel Markov game with a decomposable Hilbert space $\mathcal H$ , transition features $\phi_h:\mathcal S\times\mathcal A\times\mathcal B\to\mathcal H$ , and state features $\psi_h:\mathcal S\to\mathcal H$ such that $P_h(s'\mid s,a,b)=\langle\phi_h(s,a,b),\psi_h(s')\rangle_{\mathcal H}$ and $r_h(s,a,b)=\langle\phi_h(s,a,b),\theta_h^r\rangle_{\mathcal H}$ . The regularity conditions are $\|\theta_h^r\|_{\mathcal H}\leq1$ and $\|\sum_s V(s)\psi_h(s)\|_{\mathcal H}\leq1$ for every $V:\mathcal S\to[0,1]$ .

The learner receives a feature class $\Phi$ containing the true transition features, with every candidate feature map having norm at most one. It forms the union of linear value classes $f_h(s,a,b)=\langle\tilde\phi_h(s,a,b),\theta\rangle_{\mathcal H}$ over $\tilde\phi\in\Phi$ and $\|\theta\|_{\mathcal H}\leq R$ . Define $X_h=\{\mathbb E_{\rho}[\phi_h(s,a,b)]:\rho\in\mathcal D_{\mathcal F,h}\}$ . The resulting state-based complexity is bounded by
$\dim_{\rm VBE}(\mathcal F,\epsilon)\leq\max_{h\in[H]}\operatorname{deff}\!\left(X_h,\frac{\epsilon}{2R+1}\right),$
with effective dimension defined by the log-determinant criterion. This gives a low-complexity guarantee for selecting among candidate kernel features when the true transition representation is included in the supplied feature class.
Knowl 13 — Computational efficiency is not guaranteed
limitation
GOLF WITH EXPLOITER provides sample-efficiency guarantees but is not computationally efficient in general. Its optimistic planning and exploiter steps require optimization over function classes, and the paper leaves the design of computationally efficient algorithms for general function approximation as an open problem. The guarantees for infinite function classes can use finite coverings, but this statistical reduction does not establish efficient computation of those coverings or of the required optimizers.

Coverage note — Proof-only concentration arguments and the motivating rock–paper–scissors counterexample for optimistic-closure methods are omitted because they support, rather than add separate guarantees to, the algorithm and complexity results extracted here.

References

1.Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. Flambe: Structural complexity and representation learning of low rank mdps. Advances in Neural Information Processing Systems, 33, 2020.
2.Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. arXiv preprint arXiv:1703.05449, 2017.
3.Bai, Y. and Jin, C. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pp. 551–560. PMLR, 2020.
4.Bai, Y., Jin, C., and Yu, T. Near-optimal reinforcement learning with self-play. arXiv preprint arXiv:2006.12007, 2020.
5.Baker, B., Kanitscheider, I., Markov, T., Wu, Y., Powell, G., McGrew, B., and Mordatch, I. Emergent tool use from multi-agent autocurricula. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=SkxpxJBKwS.
6.Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06680, 2019.
7.Brafman, R. I. and Tennenholtz, M. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213–231, 2002.
8.Brambilla, M., Ferrante, E., Birattari, M., and Dorigo, M. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):1–41, 2013.
9.Brown, N. and Sandholm, T. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018.
10.Brown, N. and Sandholm, T. Superhuman ai for multiplayer poker. Science, 365(6456):885–890, 2019.
11.Cai, Q., Yang, Z., Jin, C., and Wang, Z. Provably efficient exploration in policy optimization. arXiv preprint arXiv:1912.05830, 2019.
12.Celli, A., Marchesi, A., Farina, G., and Gatti, N. No-regret learning dynamics for extensive-form correlated equilibrium. Advances in Neural Information Processing Systems, 33, 2020.
13.Chen, Z., Zhou, D., and Gu, Q. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint arXiv:2102.07404, 2021.
14.Dann, C. and Brunskill, E. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2818–2826, 2015.
15.Dong, K., Peng, J., Wang, Y., and Zhou, Y. Root-n-regret for learning in markov decision processes with function approximation and low bellman rank. In Conference on Learning Theory, pp. 1554–1557. PMLR, 2020.
16.Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103.10897, 2021.
17.Filar, J. and Vrieze, K. Competitive Markov decision processes. Springer Science & Business Media, 2012.
18.Foster, D. J., Rakhlin, A., Simchi-Levi, D., and Xu, Y. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective. arXiv preprint arXiv:2010.03104, 2020.
19.Gilpin, A. and Sandholm, T. Finding equilibria in large sequential games of imperfect information. In Proceedings of the 7th ACM conference on Electronic commerce, pp. 160–169, 2006.
20.Hansen, T. D., Miltersen, P. B., and Zwick, U. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1–16, 2013.
21.Hu, J. and Wellman, M. P. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov):1039–1069, 2003.
22.Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
23.Jia, Z., Yang, L. F., and Wang, M. Feature-based q-learning for two-player stochastic games. arXiv preprint arXiv:1906.00423, 2019.
24.Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704–1713. PMLR, 2017.
25.Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4863–4873, 2018.
26.Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137–2143, 2020.
27.Jin, C., Liu, Q., and Miryoosefi, S. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815, 2021.
28.Koller, D. and Megiddo, N. The complexity of two-person zero-sum games in extensive form. Games and economic behavior, 4(4):528–552, 1992.
29.Krishnamurthy, A., Agarwal, A., and Langford, J. Pac reinforcement learning with rich observations. arXiv preprint arXiv:1602.02722, 2016.
30.Li, H. and He, H. Multi-agent trust region policy optimization. arXiv preprint arXiv:2010.07916, 2020.
31.Littman, M. L. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157–163. Elsevier, 1994.
32.Littman, M. L. Friend-or-foe q-learning in general-sum games. In ICML, volume 1, pp. 322–328, 2001.
33.Liu, Q., Yu, T., Bai, Y., and Jin, C. A sharp analysis of model-based reinforcement learning with self-play. arXiv preprint arXiv:2010.01604, 2020.
34.Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-competitive environments. arXiv preprint arXiv:1706.02275, 2017.
35.Neu, G. and Pike-Burke, C. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
36.OpenAI. Openai five. https://blog.openai.com/openai-five/, 2018.
37.Osband, I. and Van Roy, B. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pp. 1466–1474, 2014.
38.Rashid, T., Samvelyan, M., Schroeder, C., Farquhar, G., Foerster, J., and Whiteson, S. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4295–4304. PMLR, 2018.
39.Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pp. 2256–2264, 2013.
40.Shalev-Shwartz, S., Shammah, S., and Shashua, A. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016.
41.Shapley, L. S. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095–1100, 1953.
42.Sidford, A., Wang, M., Yang, L., and Ye, Y. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pp. 2992–3002. PMLR, 2020.
43.Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016.
44.Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676):354–359, 2017.
45.Sun, W., Jiang, N., Krishnamurthy, A., Agarwal, A., and Langford, J. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pp. 2898–2933, 2019.
46.Szepesvari, C. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning, 4(1):1–103, 2010.
47.Tian, Y., Wang, Y., Yu, T., and Sra, S. Online learning in unknown markov games. arXiv preprint arXiv:2010.15020, 2021.
48.Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575 (7782):350–354, 2019.
49.Wang, R., Salakhutdinov, R., and Yang, L. F. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005.10804, 2020.
50.Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136, 2019.
51.Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. Online reinforcement learning in stochastic games. arXiv preprint arXiv:1712.00579, 2017.
52.Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-point optimization. arXiv e-prints, pp. arXiv–2006, 2020.
53.Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. arXiv preprint arXiv:2102.04540, 2021.
54.Weisz, G., Amortila, P., and Szepesvari, C. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. arXiv preprint arXiv:2010.01374, 2020.
55.Xie, Q., Chen, Y., Wang, Z., and Yang, Z. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pp. 3674–3682. PMLR, 2020.
56.Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. I. Bridging exploration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations. arXiv preprint arXiv:2011.04622, 2020.
57.Yu, C., Velu, A., Vinitsky, E., Wang, Y., Bayen, A., and Wu, Y. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955, 2021a.
58.Yu, T., Tian, Y., Zhang, J., and Sra, S. Provably efficient algorithms for multi-objective competitive rl. arXiv preprint arXiv:2102.03192, 2021b.
59.Zanette, A. and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. arXiv preprint arXiv:1901.00210, 2019.
60.Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. Learning near optimal policies with low inherent bellman error. arXiv preprint arXiv:2003.00153, 2020a.
61.Zanette, A., Lazaric, A., Kochenderfer, M. J., and Brunskill, E. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33, 2020b.
62.Zhang, K., Kakade, S. M., Bas¸ar, T., and Yang, L. F. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.07461, 2020a.
63.Zhang, Z., Zhou, Y., and Ji, X. Almost optimal model-free reinforcement learning via reference-advantage decomposition. arXiv preprint arXiv:2004.10019, 2020b.
64.Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20:1729–1736, 2007.

Citation

MLA

Jin, C., et al. “The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces”. International Conference on Machine Learning, vol. 162, 2022, pp. 10251–79, https://proceedings.mlr.press/v162/jin22c.html.

APA

Jin, C., Liu, Q., & Yu, T. (2022). The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces. International Conference on Machine Learning, 162, 10251–10279. https://proceedings.mlr.press/v162/jin22c.html

Chicago

Jin, C., Q. Liu, and T. Yu. 2022. “The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces”. International Conference on Machine Learning 162: 10251–79. https://proceedings.mlr.press/v162/jin22c.html.

Harvard

Jin, C., Liu, Q. and Yu, T. (2022) “The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces”, International Conference on Machine Learning. PMLR, pp. 10251–10279. Available at: https://proceedings.mlr.press/v162/jin22c.html.

Vancouver

1. Jin C, Liu Q, Yu T (2022) The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces. In: International Conference on Machine Learning. PMLR, pp 10251–10279

BibTeX

@InProceedings{pmlr-v162-jin22c,
  title = 	 {The Power of Exploiter: Provable Multi-Agent {RL} in Large State Spaces},
  author =       {Jin, Chi and Liu, Qinghua and Yu, Tiancheng},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {10251--10279},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/jin22c/jin22c.pdf},
  url = 	 {https://proceedings.mlr.press/v162/jin22c.html},
  abstract = 	 {Modern reinforcement learning (RL) commonly engages practical problems with large state spaces, where function approximation must be deployed to approximate either the value function or the policy. While recent progresses in RL theory address a rich set of RL problems with general function approximation, such successes are mostly restricted to the single-agent setting. It remains elusive how to extend these results to multi-agent RL, especially in the face of new game-theoretical challenges. This paper considers two-player zero-sum Markov Games (MGs). We propose a new algorithm that can provably find the Nash equilibrium policy using a polynomial number of samples, for any MG with low multi-agent Bellman-Eluder dimension—a new complexity measure adapted from its single-agent version (Jin et al., 2021). A key component of our new algorithm is the exploiter, which facilitates the learning of the main player by deliberately exploiting her weakness. Our theoretical framework is generic, which applies to a wide range of models including but not limited to tabular MGs, MGs with linear or kernel function approximation, and MGs with rich observations.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — GOLF WITH EXPLOITER: optimistic self-play with a best-response learner

Knowl 2 — Multi-agent Bellman–Eluder dimension

Knowl 3 — Approximate realizability and completeness conditions

Knowl 4 — Self-play regret guarantee

Knowl 5 — Episode complexity for finding an approximate Nash policy

Knowl 6 — Regret against an adversarial opponent

Knowl 7 — V-type Bellman–Eluder dimension and uniformly randomized sampling

Knowl 8 — Linear function approximation has low multi-agent BE dimension

Knowl 9 — Kernel value-function approximation is controlled by effective dimension

Knowl 10 — Tabular Markov games have low multi-agent BE dimension

Knowl 11 — Rich observations with few effective states have low V-type BE dimension

Knowl 12 — Kernel feature selection admits an effective-dimension VBE bound

Knowl 13 — Computational efficiency is not guaranteed

References

Citation

BibTeX

Access the Paper