Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank

## Abstract

Abstract We study the problem of learning an approximate equilibrium in the offline multi-agent reinforcement learning (MARL) setting. We introduce a structural assumption—the interaction rank —and establish that functions with low interaction rank are significantly more robust to distribution shift compared to general ones. Leveraging this observation, we demonstrate that utilizing function classes with low interaction rank, when combined with regularization and no-regret learning, admits decentralized, computationally and statistically efficient learning in offline MARL. Our theoretical results are complemented by experiments that showcase the potential of critic architectures with low interaction rank in offline MARL, contrasting with commonly used single-agent value decomposition architectures.

## 1 Introduction

Multi-agent reinforcement learning (MARL) is a general framework for interactive decision-making with multiple agents. Recent breakthroughs in this field include learning superhuman strategies in games like Go (Silver et al.,, ), StarCraft II (Vinyals et al.,, ), Texas hold’em poker (Brown and Sandholm,, ), and Diplomacy (Bakhtin et al.,, ). Additionally, MARL has been successfully applied in real-world domains, including auctions (Jin et al.,, ), pricing systems (Nanduri and Das,, ), and traffic control (Wu et al.,, ).
However, most of these successes rely on online and iterative interaction with the environment, which enables the collection of diverse and exploratory data. In practice, online interaction with exploratory policies is often infeasible or prohibitive due to safety constraints, making it necessary to use offline datasets instead.

Several recent works have investigated the application of modern deep RL algorithms to the offline MARL setting (Yang et al.,, ; Tseng et al.,, ; Wang et al.,, ). Despite recent advances, there remains a lack of standardized methods that can effectively tackle complex, real-world problems beyond simulated or simplistic settings.
Recent works (Cui and Du,, ; ) studied offline MARL from a sample complexity perspective. Specifically,  designed the BCEL algorithm, a sample-efficient algorithm for the offline general-sum MARL setting with general function classes. However, its implementation poses significant challenges due to the need to solve a non-convex problem in the joint action space. Furthermore, the algorithm’s sample complexity is tied to the unilateral coverage coefficient, which can scale exponentially with the number of agents in the worst-case scenario.
This raises the following question, which becomes the focus of this work:

Are there any natural structural assumptions that allow for both sample efficient and computationally efficient algorithms in the offline MARL setting?

Recent lower bounds show that computing an equilibrium in a MARL setting is hard in general (Daskalakis et al.,, , ). Nevertheless, for some specialized MARL classes, this need not be the case. In this work, we study the MARL setting with low *interaction rank* (IR). In this setting the reward model decomposes to a sum of terms, each involving the interactions of only a subset of the agents (Section [3](#S3)). Our key statistical result is that functions with low interaction rank are more robust to distribution shift compared to general functions. This result, which, as we show, has natural applications in offline MARL, may also be of general interest.

**Table 1: Comparison of the results presented in this work (highlighted in orange) and prior work. $C$ is the single-agent coverage coefficient. Here we present the worst-case dependence of the sample complexity in the single-agent coverage coefficient, where $N$ is the number of agents.**
| Offline Setting | Reward Assumption | Sample Complexity | Efficient Algorithm |
| --- | --- | --- | --- |
| Markov Game | — | $O\left(C^{N}\right)$ | ✗ |
| Contextual Game | $K$-Interaction Rank | $O\left(C^{K}\right)$ | ✓ |
| Markov Game w/ Decoupled Transition | $K$-Interaction Rank | $O\left(C^{K}\right)$ | ✓ |

Assuming the reward model has low interaction rank, we leverage regularization and no-regret learning to develop decentralized computationally-efficient offline algorithms for the contextual game (CG) setting, and for Markov games (MG) with a decoupled transition model (Section [4](#S4) and Section [5](#S5)). Notably, we prove that applying structures with low interaction rank allows these algorithms to achieve sample-efficient learning, avoiding the exponential dependence in the number of agents. Lastly, in Section [6](#S6), we empirically corroborate our findings. This shows the potential of using reward architectures with low interaction rank in offline MARL setting, and the need to go beyond the standard single agent value decomposition architectures, which have been popularized for MARL (Sunehag et al.,, ; Rashid et al.,, ; Yu et al.,, ).

## 2 Preliminaries

We define the general offline multi-agent RL setting, which includes all of the models we study.

#### General-sum contextual MG.

A contextual MG is defined by the tuple $\mathcal{M}=(N,H,\mathcal{C},\mathcal{S}:=\prod_{i=1}^{N}\mathcal{S}_{i},\mathcal{A}:=\prod_{i=1}^{N}\mathcal{A}_{i},\{R^{\star}_{i,h}\}_{i=1,h=1}^{N,H})$ where $N$ is the number of agents and $H$ is the horizon. $\mathcal{C}$ is the context space. In each episode, a public context $c\in\mathcal{C}$, which is observed by all agents and stays invariant throughout the episode, is drawn from the distribution $\rho$. $\mathcal{S}_{i}$ and $\mathcal{A}_{i}$ are the local state and action spaces of the $i$-th agent. We assume the initial local state of each agent is fixed for simplicity, but our analysis can be easily extended to accommodate stochastic initial states.
$R^{\star}_{i,h}(c,\bm{s},\bm{a})$ is the reward distribution of agent $i$ at step $h$ given the context $c$, joint state $\bm{s}$ and joint action $\bm{a}$. We assume the value of $R^{\star}_{i,h}$ lies in $[0,1]$ and denote the mean of $R^{\star}_{i,h}$ by $r^{\star}_{i,h}$. In this paper, we study general-sum RL (Littman,, ) and thus $r^{\star}_{i,h}:\mathcal{C}\times\mathcal{S}\times\mathcal{A}\to[0,1]$ can be an arbitrary reward function.

#### Policy and value functions.

A joint policy $\pi=\{\pi_{h}\}_{h=1}^{H}$ is a mapping from $\mathcal{C}\times\mathcal{S}$ to the simplex $\Delta_{\mathcal{A}}$ which determines the joint action selection probability under the public context and joint state at each step. Given $\pi$, we use $\pi_{i}=\{\pi_{i,h}\}_{h=1}^{H}$ to denote the marginalized policy for agent $i$. In the decentralized setting (; DeWeese and Qu,, ; Qu et al.,, ; Lin et al.,, ; Jin et al.,, ),
each agent $i$ independently executes its local policy $\pi_{i}$ based only on the public context $c$ and its local state $s_{i}$, i.e., $\pi=\prod_{i=1}^{N}\pi_{i}$ where $\pi_{i,h}:\mathcal{C}\times\mathcal{S}_{i}\to\Delta_{\mathcal{A}_{i}}$ for all $i,h$. In this case, we call the joint policy $\pi$ a product policy.

Given a reward function $r_{i}$ of agent $i$ and joint policy $\pi$, we define the value function and Q-function associated with agent $i$ to be agent $i$’s expected return conditioned on the current joint state (and action):

$$ $\displaystyle V^{\pi,r}_{i,h}(c,\bm{s}):=\mathbb{E}_{\pi}\left[\sum_{h^{\prime}=h}^{H}r_{i,h^{\prime}}(c,\bm{s}_{h^{\prime}},\bm{a}_{h^{\prime}})\,\Bigg{|}\,c,\bm{s}_{h}=\bm{s}\right],$ $\displaystyle Q^{\pi,r}_{i,h}(c,\bm{s},\bm{a}):=\mathbb{E}_{\pi}\left[\sum_{h^{\prime}=h}^{H}r_{i,h}(c,\bm{s}_{h^{\prime}},\bm{a}_{h^{\prime}})\,\Bigg{|}\,c,\bm{s}_{h}=\bm{s},\bm{a}_{h}=\bm{a}\right].$ $$

Here, $\mathbb{E}_{\pi}[\cdot]$ denotes the expectation under the distribution of the trajectory when executing $\pi$ in $\mathcal{M}$.
We will omit the superscript $r$ in $V^{\pi,r}_{i,h}$ and $Q^{\pi,r}_{i,h}$ if $r$ is the ground truth reward $r^{\star}$.

#### Offline equilibrium learning.

For any joint policy $\pi$, if each agent cannot increase its own expected reward by changing its policy while the other agents fix their policies, then $\pi$ is a coarse correlated equilibrium (CCE) (Aumann,, ). More specifically, let $\Pi_{i}:=\{\mu_{i}:\mathcal{C}\times\mathcal{S}_{i}\to\Delta_{\mathcal{A}_{i}}\}$ denote the local policy class of the agent $i$, then an $\epsilon$-approximate CCE can be defined as follows:

###### Definition 1 (Coarse Correlated Equilibrium) .

A joint policy $\pi$ is called an $\epsilon$-approximate CCE if

$$ $\displaystyle\mathsf{Gap}_{i}(\pi):=\max_{\mu_{i}\in\Pi_{i}}\mathbb{E}_{c\sim\rho}[V^{\mu_{i}\times\pi_{-i}}_{i,1}(c,\bm{s}_{1})]-\mathbb{E}_{c\sim\rho}[V^{\pi}_{i,1}(c,\bm{s}_{1})]\leq\epsilon,\quad\forall i\in[N],$ $$

where $\pi_{-i}$ is the marginalized policy of $\pi$ for all agents excluding $i$.

If $\pi$ is a product policy and satisfies [Definition 1](#Thmdefinition1), then $\pi$ is the well-known Nash equilibrium (NE) (Nash et al.,, ). Given the fact that NE can be hard to compute for even general-sum normal games (Daskalakis et al.,, ), our goal is to learn an $\epsilon$-approximate CCE. In particular, we want to identify a natural structural property for MARL, under which we can design both statistically and computationally efficient offline algorithm, which means that we assume access to an offline dataset $\mathcal{D}$ without allowing interaction with the environment beyond this.

###### Definition 1 (Coarse Correlated Equilibrium) .

## 3 Interaction Rank Implies Robustness to Distribution Shift

In this section, we define the key structural property introduced in this work—the interaction rank (IR) of a function. We show that a function with a low interaction rank is significantly more robust to distribution shift compared to a general function in a standard offline supervised learning setting. This observation later enables us to derive sample efficient guarantees for the MARL setting.
For an arbitrary function, we define its interaction rank as follows.

###### Definition 2 (Interaction Rank) .

A function $f:\mathcal{X}\times\mathcal{Y}_{1}\times\cdots\times\mathcal{Y}_{W}\to[0,1]$ has interaction rank $K$ ($K$-IR) if there exists a positive integer $K$ such that there exists a group of sub-functions $\cup_{0\leq k\leq K}\{g_{j_{1},\ldots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ which satisfies

$$ $\displaystyle f(x,y_{1},\ldots,y_{W})=\!\sum_{k=0}^{K-1}\,\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}\!\!\!g_{j_{1},\ldots,j_{k}}(x,y_{j_{1}},\ldots,y_{j_{k}}),\forall x\in\mathcal{X},y_{1}\in\mathcal{Y}_{1},\ldots,y_{W}\in\mathcal{Y}_{W}.$ $$

Intuitively, the function
can be decomposed into a sum of $g$, called sub-functions, each depending only on a subset of the input variables.
This structure is common in practice and finds application in fields including physics (Grana,, ), economics, (Asghari et al.,, ) and statistics (Vonesh et al.,, ).

###### Definition 2 (Interaction Rank) .

#### Relation to Taylor series.

When restricting the inputs of a function to a local neighborhood, [Definition 2](#Thmdefinition2) can understood as a Taylor expansion of function. To see this, fix an $x\in\mathcal{X}$, then any $K$-differentiable function $f$ in a local region of $\{y_{w}\}_{w=1}^{W}\in\prod_{w}^{W}\mathcal{Y}_{w}$ can be approximated as

$$ $\displaystyle f(x,y_{1},\ldots,y_{W})\simeq f(x,y^{\prime}_{1},\ldots,y^{\prime}_{W})+\sum_{k=1}^{K}\frac{1}{k!}\sum_{j_{1},\ldots,j_{k}}\frac{\partial f(x,y^{\prime}_{1},\ldots,y^{\prime}_{W})}{\partial y_{j_{1}}\cdots\partial y_{j_{k}}}\prod_{k^{\prime}=1}^{k}(y_{j_{k^{\prime}}}-y^{\prime}_{j_{k^{\prime}}}).$ $$

Hence, the interaction rank of a $K$-order Taylor expansion is upper bounded by $K+1$. Further, if the Taylor series is close to $f$, we can find a good approximation of $f$ with low interaction rank.

#### Bounded interaction rank implies distribution shift robustness.

The key property that makes functions with low interaction rank useful in the offline MARL is their robustness to distribution shift. Towards formalizing this statement, let us first consider an offline supervised learning setting.
Suppose we wish to learn a target function $f^{\star}$ in an offline setting. The training distribution is $x\sim p,y_{i}\sim p_{i}(\cdot|x),\forall i$ and the target distribution is $x\sim p^{\prime},y_{i}\sim p^{\prime}_{i}(\cdot|x),\forall i$. The distribution shift is quantified by the density ratio:

$$ $\displaystyle\max_{x\in\mathcal{X}}\frac{p^{\prime}(x)}{p(x)}\leq C_{\mathsf{DS}},\quad\max_{i\in[N],x\in\mathcal{X},y_{i}\in\mathcal{Y}_{i}}\frac{p^{\prime}_{i}(y_{i}|x)}{p_{i}(y_{i}|x)}\leq C_{\mathsf{DS}}.$ $$

Let $\widehat{f}$ denote the learned function. Standard guarantees imply that the training error (i.e., under $p$ and $p_{i}$) can be upper bounded by $\epsilon$:

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{1}\sim p_{1}(\cdot|x),\ldots,y_{W}\sim p_{W}(\cdot|x)}\left[\left((f^{\star}-\widehat{f})(x,y_{1},\cdots,y_{W})\right)^{2}\right]\leq\epsilon.$ (1) $$

When $f^{\star}$ and $\widehat{f}$ are general functions, the optimal worst-case learning error under the *target distribution* is $O\bigl{(}(C_{\mathsf{DS}})^{W+1}\epsilon\bigr{)}$, which scales exponentially with the input size $W$. However, if $f^{\star}$ and $\widehat{f}$ have bounded interaction rank, this result can be significantly improved; the error under distribution shift only scales exponentially with the interaction rank.

###### Theorem 1 .

If $f^{\star}$ and $\widehat{f}$ are $K$-IR, we have

$$ $\displaystyle\mathbb{E}_{x\sim p^{\prime},y_{1}\sim p^{\prime}_{1}(\cdot|x),\ldots,y_{W}\sim p^{\prime}_{W}(\cdot|x)}\left[\left((f^{\star}-\widehat{f})(x,y_{1},\ldots,y_{W})\right)^{2}\right]\lesssim(2W)^{2(K-1)}C_{\mathsf{DS}}^{K}\,\epsilon.$ $$

Here for any two functions $g$ and $g^{\prime}$, $g\lesssim g^{\prime}$ means that there exists a constant $c>0$ such that $g<cg^{\prime}$ always holds. [Theorem 1](#Thmtheorem1) indicates that when $K\ll W$, function classes with bounded interaction rank are more robust to distribution shift and can significantly alleviate the curse of dimensionality due to multiple agents in offline learning. In MARL, $W+1$ will be the number of agents, while $K$ is the interaction rank of the reward.

###### Theorem 1 .

## 4 Warm Up: Contextual Games

The robustness to distribution shift of low-IR functions suggests that such a property may be useful for offline MARL. Indeed, in the offline setting we need to properly estimate quantities that deviate from the data distribution. To provide intuition for the benefits of low-IR reward classes and corresponding algorithmic design, we start by considering the *contextual games* (CG) setting as a warm up.

#### Offline CG.

The CG problem is a general-sum contextual MG where $\mathcal{S}_{i}=\emptyset$ for all $i$ and $H=1$. To simplify notation, we omit the $h$ subscript in $r_{h}$ and $\pi_{h}$ for this setting. We assume the offline dataset $\mathcal{D}=\mathcal{D}_{\mathsf{R}}$ where each sample $(c,\bm{a}=\{a_{i}\}_{i=1}^{N},\{r_{i}\}_{i=1}^{N})$ is i.i.d. sampled from $c\sim\rho,a_{i}\sim\nu_{i}(\cdot|c),r_{i}\sim R^{\star}_{i}(c,\bm{a})$ for all $i\in[N]$. We call $\nu_{i}$ the offline behavior policy for each agent $i$ and use $\nu$ to denote the product behavior policy $\prod_{i\in[N]}\nu_{i}$. Let us assume for simplicity that we have learned reward functions $\{\widehat{r}_{i}\in[0,1]\}_{i\in[N]}$ from the offline dataset with in-distribution training error $\epsilon$:

$$ $\displaystyle\mathbb{E}_{c\sim\rho,\bm{a}\sim\nu(\cdot|c)}\left[\left(r^{\star}_{i}-\widehat{r}_{i}\right)^{2}\right]\leq\epsilon,\quad\forall i\in[N].$ $$

#### Algorithm: Decentralized χ 2 superscript 𝜒 2 \chi^{2} -Regularized Policy Gradient.

Given $\widehat{r}$, we propose a decentralized, $\chi^{2}$-regularized, no-regret policy gradient based algorithm. As we show, this algorithm produces a set of policies which are near equilibrium. In each iteration $t$ , each agent will update their policy via:

$$ $\displaystyle\pi^{t+1}_{i}(c)=\arg\min_{p\in\Delta_{\mathcal{A}_{i}}}-\langle\widehat{r}^{t}_{i}(c,\cdot),p\rangle+\lambda\underbrace{\chi^{2}(p,\nu_{i}(c))}_{\color[rgb]{0,0.609375,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.609375,0}\text{regularization}}+\frac{1}{\eta}\underbrace{D_{c,i}(p,\pi^{t}_{i}(c))}_{\color[rgb]{0,0.609375,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.609375,0}\text{no-regret learning}}.$ (2) $$

Here $\widehat{r}^{t}_{i}(c,a_{i})=\mathbb{E}_{a_{j}\sim\pi^{t}_{j}(c),\forall j\neq i}\left[\widehat{r}_{i}(c,\bm{a})\right]$ is the expected reward of agent $i$ given that the other agents’ policies are $\prod_{j\neq i}\pi^{t}_{j}$. The regularizer $\chi^{2}(p,\nu_{i}(c)):=\mathbb{E}_{a_{i}\sim\nu_{i}(\cdot|c)}[(p(a_{i})/\nu_{i}(a_{i}|c)-1)^{2}]$ is the $\chi^{2}$-divergence between distribution $p$ and $\nu_{i}(c)$ and $D_{c,i}(p,\pi^{t}_{i}(c))$ is the Bregman divergence between distribution $p$ and $\pi^{t}_{i}(c)$:

$$ $\displaystyle D_{c,i}(p,\pi^{t}_{i}(c))$ $\displaystyle:=\chi^{2}(p,\nu_{i}(c))-\chi^{2}(\pi^{t}_{i}(c),\nu_{i}(c))-\langle\nabla_{\pi^{t}_{i}}(c)\chi^{2}(\pi^{t}_{i}(c),\nu_{i}(c)),p-\pi^{t}_{i}(c)\rangle$ $\displaystyle=\mathbb{E}_{a_{i}\sim\nu_{i}(\cdot|c)}\left[\left(\frac{p(a_{i})-\pi^{t}_{i}(a_{i}|c)}{\nu_{i}(a_{i}|c)}\right)^{2}\right].$ $$

We denote the total number of iterations by $T$. [Eq. 2](#S4.E2) has two divergence terms, which serve different roles. We add the $\chi^{2}$-divergence regularization term to encourage the policy trajectory to stay close to the behavior policy $\nu_{i}$ and thus lessen the distribution shift issue. On the other hand, to ensure the update enjoys no regret, we have a Bregman divergence term which is motivated from the policy mirror descent literature (; Lan,, ). Notably, [Eq. 2](#S4.E2) is a quadratic optimization problem whose input size is only $|\mathcal{A}_{i}|$. Thus, for small action and state space we can solve it efficiently without incurring exponential computation cost as the number of agents increase.

###### Remark 1 .

The key ingredients of our algorithm are (1) regularization and (2) no-regret learning. We choose $\chi^{2}$-divergence and its corresponding Bregman divergence for a tractable theoretical analysis. In practice, other regularizers can also be utilized, such as KL divergence (Rafailov et al.,, ) or the $L_{2}$ behavior cloning term in TD3-BC (Fujimoto and Gu,, ). Additionally, in practice, one-step online gradient (Zinkevich,, ) can be used as the no-regret learning algorithm.

###### Remark 1 .

#### Theoretical analysis.

Now we analyze the statistical sample complexity of the above algorithm. If the reward function class has no specific structure, the sample complexity can still scale exponentially with $N$ due to distribution shift. To address this, we leverage a low-IR reward function class:

###### Assumption 1 ( $K$ -IR Reward) .

Suppose that the interaction rank of $r^{\star}_{i}$ and $\widehat{r}_{i}$ are upper bounded by $K$, with $\mathcal{X}=\mathcal{C}\times\mathcal{A}_{i}$ and $\mathcal{Y}_{j}=\mathcal{A}_{j}$ in [Definition 2](#Thmdefinition2) for all $i\in[N]$.

[1](#Thmassumption1) naturally holds in a variety of games. For example, polymatrix games (Howson Jr,, ; Kalogiannis and Panageas,, ; MacQueen and Wright,, ) characterize the reward function via pairwise interactions and, thus, for these settings [1](#Thmassumption1) holds with $K=2$. In network games (Galeotti et al.,, ; DeWeese and Qu,, ; Park et al.,, ), the reward only depends on the neighbors and thus [1](#Thmassumption1) holds with $K$ equal to the degree of the network. Note that for all of these examples, we have $K\ll N$.

Now we introduce a bound on the maximum gap of the output policy $\widehat{\pi}$ under $K$-IR reward classes. Let $r(\pi)$ be the expected reward under the distribution $c\sim\rho,\bm{a}\sim\pi(\cdot|c)$. Similar to existing offline RL analysis techniques (Xie et al.,, ), we split the bound into on-support and off-support components:

###### Theorem 2 (Informal) .

Suppose [1](#Thmassumption1) holds. Let $\Pi_{i}(C):=\{\mu_{i}:\mathbb{E}_{c\sim\rho}[\chi^{2}(\mu_{i}(c),\nu_{i}(c))]\leq C\}$ denote the policy class which has bounded $\chi^{2}$-divergence from the behavior policy $\nu_{i}$. Fix any $\delta\in(0,1]$ and select $T,\eta,\lambda$ in [Eq. 2](#S4.E2) properly. Then, with probability at least $1-\delta$, we have

$$ $\displaystyle\max_{i}\mathsf{Gap}_{i}(\widehat{\pi})\lesssim\max_{i\in[N]}\min_{C\geq 1}\left\{C\left((2N^{2})^{K-1}\epsilon\right)^{\frac{1}{3K-1}}+\mathsf{subopt}_{i}(C,\widehat{\pi})\right\},$ (3) $$

where $\mathsf{subopt}_{i}(C,\widehat{\pi}):=\max_{\mu_{i}\in\Pi_{i}}r^{\star}_{i}(\mu_{i},\widehat{\pi}_{-i})-\max_{\mu_{i}\in\Pi_{i}(C)}r^{\star}_{i}(\mu_{i},\widehat{\pi}_{-i})$ is the off-support bias.

###### Assumption 1 ( K 𝐾 K -IR Reward) .

###### Theorem 2 (Informal) .

#### Optimal bias-variance tradeoff.

We call $\Pi_{i}(C)$ a covered policy class because policies within it have bounded $\chi^{2}$-divergence from the behavior policy $\nu$, which implies that we can estimate their performance relatively accurately from the offline dataset. The right hand side of [Eq. 3](#S4.E3) can be viewed as a bias-variance decomposition of the gap. The first term is the variance term which measures the distribution-shift effect of comparing against policies from $\Pi_{i}(C)$. The second term is the bias term which quantifies the performance difference between the global optimal policy and the optimal policy in the covered policy class. As $C$ increases, the considered covered policy class will expand and thus the variance term will grow while the bias term will diminish. Notably, our algorithm does not require any information about $C$ and the gap in [Theorem 2](#Thmtheorem2) is upper bounded by the optimal $C$, which means that we can identify the best bias-variance tradeoff automatically.

#### Polynomial sample complexity with single-agent concentrability.

Let us consider the following single-agent all-policy concentrability coefficient $C_{\mathsf{sin}}:=\max_{i\in[N],\mu_{i},c\in\mathcal{C},a_{i}\in\mathcal{A}_{i}}\frac{\mu_{i}(a_{i}|c)}{\nu_{i}(a_{i}|c)}$.
Note that $C_{\mathsf{sin}}$ will not scale with $N$ exponentially. Then [Theorem 2](#Thmtheorem2) implies that if $C_{\mathsf{sin}}<\infty$, the maximum gap under the interaction rank structure can be upper bounded by

$$ $\displaystyle\max_{i}\mathsf{Gap}_{i}(\widehat{\pi})\lesssim C_{\mathsf{sin}}\left((2N^{2})^{K-1}\epsilon\right)^{\frac{1}{3K-1}}.$ $$

Therefore, given a fixed $K$, we can learn an approximate CCE with polynomial sample complexity with respect to the number of agents $N$ under single-agent all-policy concentrability. This demonstrates the power of low-IR reward classes for MARL. When combined with regularization and no-regret learning, the sample complexity is significantly improved, making computationally- and statistically-efficient algorithm design possible in MARL.

#### Proof highlights.

We provide a proof sketch of [Theorem 2](#Thmtheorem2) for $K=2$, supplying intuition for how $K$-IR reward classes benefit theoretical sample complexity. For any agent $i\in[N]$ and policy $\mu_{i}\in\Pi_{i}(C)$ where $C>1$, we can bound the in-support gap $\sum_{t=1}^{T}\left(r^{\star}_{i}(\mu_{i},\pi^{t}_{-i})-r^{\star}_{i}(\pi^{t})\right)$ as follows:

$$ $\displaystyle\underbrace{\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(c),\bm{a}_{-i}\sim\pi^{t}_{-i}}[(r^{\star}_{i}-\widehat{r}_{i})(c,\bm{a})]}_{(1)}+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,\bm{a}\sim\pi^{t}}[(\widehat{r}_{i}-r^{\star}_{i})(c,\bm{a})]}_{(2)}+\underbrace{\sum_{t=1}^{T}\left(\widehat{r}_{i}(\mu_{i},\pi^{t}_{-i})-\widehat{r}_{i}(\pi^{t})\right)}_{(3)}.$ $$

We need to bound terms (1), (2), and (3). Term (3) is the performance difference when changing the policy of agent $i$ to $\mu_{i}$. Note that this is equivalent to the regret of agent $i$ with loss function $-\widehat{r}^{t}_{i}$ and thus we can bound it with similar techniques in policy mirror descent literature ().

Term (1) represents the reward learning error under the comparator policy $\mu_{i}$ and learned policy $\pi^{t}_{-i}$, which is different from $\nu$. To control it, we need to tackle the distribution shift between the two. We use $g^{i}_{\emptyset},\{g^{i}_{j}\}_{j\neq i}$ and $\widehat{g}^{i}_{\emptyset},\{\widehat{g}^{i}_{j}\}_{j\neq i}$ to denote the decomposition of $r^{\star}_{i}$ and $\widehat{r}_{i}$, and use $\Delta^{i}_{j}$ to denote $g^{i}_{j}-\widehat{g}^{i}_{j}$. Since we apply a $K$-IR reward class [1](#Thmassumption1), we can decompose term (1) as follows

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),\bm{a}_{-i}\sim\pi^{t}_{-i}(\cdot|c)}[(r^{\star}_{i}-\widehat{r}_{i})(c,\bm{a})]$ $\displaystyle\qquad=\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c)}\left[\Delta^{i}(c,a_{i})\right]+\sum_{j\neq i}\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),a_{j}\sim\pi^{t}_{j}(\cdot|c)}\left[\Delta^{i}_{j}(c,a_{i},a_{j})\right].$ $$

Meanwhile, from the property of $\chi^{2}$-divergence, we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),a_{j}\sim\pi^{t}_{j}(\cdot|c)}\left[\Delta^{i}_{j}(c,a_{i},a_{j})\right]$ $\displaystyle\qquad\leq\sqrt{\mathbb{E}_{c\sim\rho,a_{i}\sim\nu_{i}(\cdot|c),a_{j}\sim\nu_{j}(\cdot|c)}\left[\left(\Delta^{i}_{j}(c,a_{i},a_{j})\right)^{2}\right]\cdot\left(1+\chi^{2}\left(\rho\circ(\mu_{i}\times\pi^{t}_{j}),\rho\circ(\nu_{i}\times\nu_{j})\right)\right)},$ $$

where we use $\rho\circ p$ to denote the joint distribution $c\sim\rho,a\sim p(\cdot|c)$ for some conditional distribution $p$. For the $\chi^{2}$-divergence term, $\chi^{2}(\mu_{i}(c),\nu_{i}(c))$ is bounded because $\mu_{i}$ is from the covered policy class; we can also upper bound $\chi^{2}(\pi^{t}_{j}(c),\nu_{j}(c))$ due to the $\chi^{2}$ regularizer term in [Eq. 2](#S4.E2). Thus, we only need to bound $\mathbb{E}_{c\sim\rho,a_{i}\sim\nu_{i}(\cdot|c),a_{j}\sim\nu_{j}(\cdot|c)}\left[\left(\Delta^{i}_{j}(c,a_{i},a_{j})\right)^{2}\right]$.

This is non-trivial because we are only regressing with respect to $r^{\star}$, which is the summation of the sub-function $g$, and there exist infinite number of IR decompositions of $r^{\star}$. Fortunately, we are able to show that such an *aligned* decomposition exists:

###### Lemma 1 (Sub-function Alignment for $K=2$ , informal) .

There exists a standardized IR decomposition of $r^{\star}$ and $\widehat{r}$, denoted by $g_{\emptyset},g_{1},\ldots,g_{W}$ and $\widehat{g}_{\emptyset},\widehat{g}_{1},\ldots,\widehat{g}_{W}$ such that we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\nu_{i}(\cdot|c),a_{j}\sim\nu_{j}(\cdot|c)}\left[\left(\Delta^{i}_{j}(c,a_{i},a_{j})\right)^{2}\right]\leq 2\epsilon,\quad\forall j\neq i.$ $$

With [Lemma 1](#Thmlemma1), we are able to bound term (1) efficiently. Term (2) can be handled similarly. Notably, [Lemma 1](#Thmlemma1) holds for general $K$ as shown in [Lemma 4](#Thmlemma4) and the IR decomposition circumvents exponential scaling with $N$. The above discussion illustrates that low-IR reward classes are quite effective when mitigating the learning error under distribution shift in MARL.

###### Lemma 1 (Sub-function Alignment for K = 2 𝐾 2 K=2 , informal) .

## 5 Decentralized Regularized Actor-Critic in Markov Games with Decoupled Transitions

We are now ready to investigate the benefits of low interaction rank in offline MGs. In particular, we will propose our main algorithmic framework to utilize low-IR function classes.

#### MGs with decoupled transitions.

In this work we assume the transition of the local state only depends on the local state, public context and local action (; DeWeese and Qu,, ; Jin et al.,, ), which can be characterized by the kernel $P^{\star}_{i,h}:\mathcal{C}\times\mathcal{S}_{i}\times\mathcal{A}_{i}\mapsto\Delta_{\mathcal{S}_{i}}$ for all $i\in[N],h\in[H]$. Note that the reward function $R^{\star}_{i,h}(c,\bm{s},\bm{a})$ is still of a general-sum game and depends on the joint state and joint action. Notice that CGs are a special case of MGs with decoupled transitions.

###### Remark 2 .

The decoupled transitions property finds application in many practical scenarios including sensor coverage, autonomous vehicles, and robotics, and has been studied under online decentralized learning setting (; DeWeese and Qu,, ; Jin et al.,, ). For more general MGs, decentralized no-regret algorithms are hard to design even in full-information setting. As far as we know, Erez et al., () is the only existing work which achieves sublinear regret in general MGs when all the agents adopt the decentralized algorithm. However, they only focus on tabular cases in the full information setting or online setting with a minimum reachability assumption. Therefore, we leave it as an important future direction to extend our analysis to more general MGs.

In particular, we consider the decentralized setting where each agent $i$ executes its policy $\pi_{i}$ only based on the public context $c$ and its local state $s_{i}$ (; DeWeese and Qu,, ; Qu et al.,, ; Lin et al.,, ; Jin et al.,, ). For agent $i$, given a local policy $\pi_{i}=\{\pi_{i,h}\}_{h\in[H]}$ and a public context $c$, the transition of the local state is indeed independent from other agents and thus we can define the local state visitation measure as follows:

$$ $\displaystyle d^{\pi_{i}}_{h}(s|c):=\mathbb{P}^{\pi_{i}}(s_{i,h}=s|c),\qquad\forall h\in[H],s\in\mathcal{S}_{i},i\in[N],$ $$

where $s_{i,h}$ is the local state of agent $i$ at step $h$ and $\mathbb{P}^{\pi}(\cdot|c)$ denotes the distribution of the trajectories under policy $\pi_{i}$ and public context $c$. We also define $d^{\pi_{i}}_{h}(s,a|c):=d^{\pi_{i}}_{h}(s|c)\pi_{i,h}(a|s)$.

###### Remark 2 .

#### Offline dataset.

We assume access to an offline dataset $\{\mathcal{D}_{h}\}_{h=1}^{H}$. $\mathcal{D}_{h}$ consists of $M$ i.i.d. samples $(c,\{s_{i},a_{i},s^{\prime}_{i}\}_{i\in[N]},\{r_{i}\}_{i\in[N]})$ where $c\sim\rho,s_{i}\sim\sigma_{i,h}(\cdot|c),a_{i}\sim\nu_{i,h}(\cdot|c,s_{i}),s^{\prime}_{i}\sim P^{\star}_{i,h}(\cdot|c,s_{i},a_{i})$ and $r_{i}\sim R^{\star}_{i,h}(c,\{s_{i},a_{i}\}_{i\in[N]})$. Note that $\sigma_{i,h}$ may not be the local state visitation measure $d^{\nu_{i}}_{h}(\cdot|c)$. We also use $\sigma_{h}$ to denote $\prod_{i\in[N]}\sigma_{i,h}$.

#### General function approximation.

We consider the general function approximation setting. This makes the algorithm applicable in potentially large or even infinite state space and action space. Suppose that we have function classes $\mathcal{R}=\{\mathcal{R}_{i}\}_{i=1}^{N}$ to approximate the reward function $r^{\star}_{i,h}$ where $\mathcal{R}_{i}\subseteq\{r:\mathcal{C}\times\mathcal{A}\to[0,1]\}$ for all $i\in[N]$. In addition, we use function classes $\{\mathcal{P}_{i}\}_{i\in[N]}$ where $\mathcal{P}_{i}\subseteq\{P:\mathcal{C}\times\mathcal{S}_{i}\times\mathcal{A}_{i}\to\Delta_{\mathcal{S}_{i}}\}$ to approximate the transition model. We assume here that $\mathcal{R}_{i}$ and $\mathcal{P}_{i}$ are finite, but the analysis can be extended to infinite function classes naturally by replacing the cardinality of $\mathcal{R}_{i}$ and $\mathcal{P}_{i}$ with its covering or bracketing number (Wainwright,, ). To simplify notation, we use $|\mathcal{R}|$ and $|\mathcal{P}|$ to denote $\max_{i\in[N]}|\mathcal{R}_{i}|$ and $\max_{i\in[N]}|\mathcal{P}_{i}|$.

### 5.1 Algorithmic Framework

Figure: Algorithm 1 Decentralized Regularized Actor-Critic (DR-AC)

For general-sum MGs with decoupled transitions, we consider a widely-used kind of algorithmic framework in practice, the actor-critic method (Barto et al.,, ). Arming it with regularization and no-regret learning, we propose DR-AC for offline learning in MGs. The full algorithm is stated in [Algorithm 1](#alg1). Notably, DR-AC is a decentralized model-based algorithm which is computationally efficient given that we are able to solve a least squares regression (LSR) and maximum likelihood estimation (MLE) problem. DR-AC consists of two phases: offline reward and transition learning, followed by decentralized actor-critic updates.

#### Offline reward and transition learning.

We first learn the reward function $\widehat{r}_{i}$ for each agent $i$ using LSR on the offline dataset $\mathcal{D}_{\mathsf{R}}$. In particular, here we will use a function class $\mathcal{R}_{i}$ where all the functions have bounded IR so that our learned reward has higher robustness to distribution shift, as we have shown in the previous section. We also learn the transition model for each $i$ via MLE on the offline dataset with function classes $\mathcal{P}_{i}$. Note that LSR and MLE problems are common in supervised learning and can be solved with simple methods like stochastic gradient descent (Jain et al.,, ). The RL literature has also assumed the existence of efficient solutions to these optimization problems, calling algorithms that depend on them oracle-efficient (Dann et al.,, ; Agarwal et al.,, ; Uehara et al.,, ; Song et al.,, ).

#### Critic update.

In each iteration, for each agent $i$, we estimate its current single-agent Q-function, given other agents’ policies, with the learned reward $\widehat{r}$ and transition model $\widehat{P}$:

$$ $\displaystyle\widehat{Q}^{t}_{i,h}(c,s_{i},a_{i})=\mathbb{E}_{(s_{j},a_{j)}\sim\widehat{d}^{\pi_{j}}_{h}(\cdot|c),\forall j\neq i}\left[\widehat{Q}^{\pi^{t},\widehat{r}}_{i,h}(c,\bm{s},\bm{a})\right],$ $$

where we use $\widehat{Q}^{\pi,\widehat{r}}_{i,h}$ and $\widehat{d}^{\pi_{j}}_{h}$ to denote the joint Q-function and local state visitation measure of $\pi$ under reward $\widehat{r}$ and transition $\widehat{P}$. In practice, we can simply use a Monte-Carlo-type method to estimate $\widehat{Q}^{t}_{i,h}$, which only requires solving an LSR problem and is thus computationally efficient. See [Appendix B](#A2) for more details.

#### Actor update.

Given the estimated Q-function, we use regularized policy gradient to update each agent’s policy. The update formula [Eq. 4](#S5.E4) is almost the same as the update in [Eq. 2](#S4.E2) for CGs, except the estimated reward is replaced with the estimated Q-function. We use $\chi^{2}$-divergence for regularization and Bregman divergence in [Algorithm 1](#alg1). Nevertheless, DR-AC allows other regularizers and no-regret learning techniques as mentioned in [Remark 1](#Thmremark1). Note that [Eq. 4](#S5.E4) is a quadratic optimization problem with input size $|\mathcal{A}_{i}|$ and thus can be solved efficiently.

### 5.2 Theoretical Analysis

We now present the sample complexity guarantee for DR-AC. We assume the function class $\{\mathcal{R}_{i}\}_{i\in[N]}$ and $\{\mathcal{P}_{i}\}_{i\in[N]}$ are realizable.

###### Assumption 2 .

Suppose that we have $r^{\star}_{i,h}\in\mathcal{R}_{i}$ and $P^{\star}_{i,h}\in\mathcal{P}_{i}$ for all $i\in[N],h\in[H]$.

In general, DR-AC can have exponentially large statistical complexity with respect to the number of agents $N$. However, similarly to the CG result, a low-IR reward function class alleviates this.

###### Assumption 3 ( $K$ -IR Reward) .

Suppose that the IR of $r_{i}$ is upper bounded by $K$ with $\mathcal{X}=\mathcal{C}\times\mathcal{S}_{i}\times\mathcal{A}_{i}$ and $\mathcal{Y}_{j}=\mathcal{S}_{j}\times\mathcal{A}_{j}$ in [Definition 2](#Thmdefinition2) for all $j\neq i,r_{i}\in\mathcal{R}_{i},i,j\in[N]$.

In addition, we assume that the offline dataset satisfies single-agent all-policy concentrability for the local state distribution. Recall that $\sigma_{i,h}$ is the dataset distribution.

###### Assumption 4 .

Suppose that for all $i\in[N]$ we have

$$ $\displaystyle\max_{i\in[N],\mu_{i},c\in\mathcal{C},s\in\mathcal{S}_{i},h\in[H]}\frac{d^{\mu_{i}}_{h}(s|c)}{\sigma_{i,h}(s|c)}\leq C_{\mathsf{S}}<\infty.$ $$

We need [4](#Thmassumption4) because bounded $\chi^{2}$-divergence between the action probabilities of two policies does not imply bounded $\chi^{2}$-divergence between their state visitation measure. In DR-AC we can only regularize the action probability and therefore require additional concentrability for the local states. Nevertheless, here we only need single-agent concentrability and thus $C_{\mathsf{S}}$ does not scale exponentially with $N$. Now we can bound on the maximum gap of the output policy $\widehat{\pi}$ by DR-AC:

###### Theorem 3 .

Suppose [2](#Thmassumption2), [3](#Thmassumption3) and [4](#Thmassumption4) hold. Let ${\Pi}_{i}(C):=\{\mu_{i}:\mathbb{E}_{c\sim\rho,s\sim d^{\mu_{i}}_{h}(\cdot|c)}[{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{2}(\mu_{i,h}(c,s),\nu_{i,h}(c,s))]\leq C,\forall h\}$ denote the policy class which has bounded $\chi^{2}$-divergence from the behavior policy $\nu_{i}$. Fix any $\delta\in(0,1]$ and select

$$ $\displaystyle\lambda=C_{\mathsf{S}}^{\frac{K}{3K+2}}H^{\frac{3K}{3K+2}}(2N^{2})^{\frac{K-1}{3K+2}}\epsilon_{\mathsf{RP}}^{\frac{1}{3K+2}},\quad\eta=\frac{\lambda}{H^{2}},\quad T=\frac{H^{2}}{\lambda^{2}},$ $$

where $\epsilon_{\mathsf{RP}}:=\frac{\log(NH|\mathcal{R}||\mathcal{P}|/\delta)}{M}$. Then, with probability at least $1-\delta$ the output of DR-AC, $\widehat{\pi}$, satisfies:

$$ $\displaystyle\max_{i}\mathsf{Gap}_{i}(\widehat{\pi})\lesssim\max_{i\in[N]}\min_{C\geq 1}\left\{CC_{\mathsf{S}}^{\frac{K}{3K+2}}H^{\frac{6K+2}{3K+2}}(2N^{2})^{\frac{K-1}{3K+2}}\epsilon_{\mathsf{RP}}^{\frac{1}{3K+2}}+{\mathsf{subopt}}_{i}(C,\widehat{\pi})\right\},$ $$

where ${\mathsf{subopt}}_{i}(C,\widehat{\pi}):=\max_{\mu_{i}}\mathbb{E}_{c\sim\rho}[V^{\mu_{i}\circ\widehat{\pi}_{-i}}_{i,1}(c,\bm{s}_{1})]-\max_{\mu_{i}\in{\Pi}_{i}(C)}\mathbb{E}_{c\sim\rho}[V^{\mu_{i}\circ\widehat{\pi}_{-i}}_{i,1}(c,\bm{s}_{1})]$.

Similarly to [Theorem 2](#Thmtheorem2), [Theorem 3](#Thmtheorem3) indicates that DR-AC admits an optimal bias-variance tradeoff over the covered policy class $\Pi_{i}(C)$. In addition, if we have single-agent all-policy concentrability $C_{\mathsf{sin}}:=\max_{h,i,\mu_{i},c,s_{i}\in\mathcal{S}_{i},a_{i}\in\mathcal{A}_{i}}\frac{\mu_{i,h}(a_{i}|c,s_{i})}{\nu_{i,h}(a_{i}|c,s_{i})}<\infty$, DR-AC is capable of learning an $\epsilon$-approximate CCE given sample complexity

$$ $\displaystyle M\gtrsim\frac{C_{\mathsf{sin}}^{3K+2}C_{\mathsf{S}}^{K}H^{6K+2}(2N^{2})^{K-1}\log(NH|\mathcal{R}||\mathcal{P}|/\delta)}{\epsilon^{3K+2}},$ $$

Therefore, given a fixed $K$ and single-agent all-policy concentrability, DR-AC can learn an approximate CCE in polynomial sample complexity with respect to $N$ for general-sum MGs with decoupled transitions. This suggests that introducing low-IR structure to the reward class is still beneficial for offline learning in general-sum MGs.

###### Remark 3 .

For $|\mathcal{R}|$, note that we require the function classes $\mathcal{R}_{i}$ to have IR bounded by $K$. This means that their complexity will at most only scale with $K$ exponentially.

###### Assumption 2 .

###### Assumption 3 ( K 𝐾 K -IR Reward) .

###### Assumption 4 .

###### Theorem 3 .

###### Remark 3 .

#### Comparison with existing works.

To our knowledge, Cui and Du, (); are the only existing offline general-sum MARL works with provable statistical guarantees. However, the proposed methods
are not decentralized and require evaluating the gap for every possible candidate joint policies, resulting in an impractically high computational burden.

Statistically, although Cui and Du, () achieves $\widetilde{O}(1/\epsilon^{2})$ complexity, they require stronger concentrability assumption, which is the following unilateral concentrability with a target policy $\pi^{\star}$:

$$ $\displaystyle C_{\mathsf{uni}}(\pi^{\star}):=\max_{h,i,\mu_{i},c,\bm{s}\in\mathcal{S},\bm{a}\in\mathcal{A}}\frac{d^{\mu_{i}}_{h}(s_{i},a_{i}|c)d^{\pi^{\star}_{-i}}_{h}(\bm{s}_{-i},\bm{a}_{-i}|c)}{\sigma_{h}(\bm{s}|c)\,\nu(\bm{a}|\bm{s},c)},$ $$

where $\bm{s}_{-i}$ and $\bm{a}_{-i}$ are the joint state and action of the agents excluding $i$. Note that the single-agent all-policy concentrability coefficient $C_{\mathsf{S}}C_{\mathsf{sin}}$ is indeed weaker than $C_{\mathsf{uni}}$ and we have $C_{\mathsf{S}}C_{\mathsf{sin}}\leq C_{\mathsf{uni}}(\pi^{\star})$ for any $\pi^{\star}$. In the worst case, $C_{\mathsf{uni}}$ can still scale exponentially with number of agents $N$, whereas our sample complexity scales with the IR $K$.

For , in CGs, they have the following concentrability assumption:

$$ $\displaystyle C_{\mathsf{uni}}^{\prime}(\mathcal{R},\pi^{\star}):=\max_{i,\mu_{i},r\in\mathcal{R}_{i}}\frac{\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),\bm{a}_{-i}\sim\pi^{\star}_{-i}(\cdot|c)}[(r-r^{\star})^{2}]}{\mathbb{E}_{c\sim\rho,\bm{a}\sim\nu(\cdot|c)}[(r-r^{\star})^{2}]}.$ $$

In their work $\mathcal{R}_{i}$ can be a general function class and thus $C_{\mathsf{uni}}^{\prime}(\mathcal{R},\pi^{\star})$ can be as large as $C_{\mathsf{uni}}(\pi^{\star})$ in the worst case. Notably, if we use function class with $K$-IR instead, [Theorem 1](#Thmtheorem1) shows that $C_{\mathsf{uni}}^{\prime}(\mathcal{R},\pi^{\star})\lesssim C_{\mathsf{sin}}^{K}$. Therefore, we indeed find a particular function class such that the concentrability in is not vacuous. For MGs, uses a function class to approximate the joint Q function while we use $\mathcal{F}$ to approximate the single-agent Q-function, and thus the results are not directly comparable.

## 6 Experiments

Figure: Figure 1: Network diagrams for the $i$th agent.

In this section, we examine the practical implications of our results. With this in mind, our findings can be interpreted as providing the following guideline: Use a reward or Q-function class with the smallest possible IR that can still represent the underlying true model. This approach strikes a balance between two factors: it ensures realizability by requiring the model can be represented accurately, and it improves sample efficiency, as demonstrated in Theorem [2](#Thmtheorem2) and Theorem [3](#Thmtheorem3).

Figure: Figure 2: Comparison of TD3+BC instantiated with different critic architectures, i) 1-IR critic, ii) 2-IR critic, and iii) joint-action critic. The underlying true reward is a 2-IR. This figure showcases the advantage of using 2-IR critic architecture compared to 1-IR or the general joint-action critics when the underlying model is 2-IR. The shaded area represents the standard error across trials.
Refer to caption: /html/2410.01101/assets/figures/proper_max_gap.png

#### Implementation and experimental setting.

To examine the usefulness of this observation, we study a simple offline CG environment.
We implement the actor update in DR-AC to be a single gradient descent update with respect to TD3+BC objective (Fujimoto and Gu,, ) from Tianshou library (Weng et al.,, ). Further, recall that TD3+BC adds explicit $L_{2}$ regularization term that keeps the policy close to the data collection policy and thus fits into the framework of DR-AC. To test the potential benefits of low rank reward critic architectures we experimented with three different types, depicted in Figure [1](#S6.F1): i) joint-action, ii) 2-IR, and iii) 1-IR reward critics. The joint-action reward critic is a general mapping from the joint action space to a number, and, hence, is the most expressive; it can represent both 2-IR and 1-IR. On the other hand, the 1-IR architecture is the least expressive, as it cannot represent 2-IR reward models, since it only accesses a single agent action. Notably, we choose the number of parameters of the 2-IR and joint-action architectures to be of the same order of magnitude for fair comparison.

The details of our environment setting are as follows (see Appendix [A](#A1) for additional information). We consider the continuous action setting, where $\forall i\in[N],\ a_{i}\in[-1,1]$. The underlying reward model is a 2-IR function of the form $\forall i\in[N],\ r^{\star}_{i}(\bm{s},)=\sum_{j=1}^{N}a_{i}a_{j}/\sqrt{N}+\epsilon$ where $\epsilon\sim\mathrm{Uniform}(-\sigma,\sigma)$ and $\sigma>0$. Further, we set number of agents as $N=50$. We collect offline data with the uniform policy and set the number of samples $M$ such that $\sigma N/M=0.1$. In this noise regime, the reward model is learnable but the noise level may effect the training procedure. We experiment with few architectures for each reward critic type and report here the best one. We also experimented with an additional environment in which the underlying reward is a 1-IR model (see additional results in Appendix [A](#A1)).

#### Results.

Experiment results are depicted in Figure [2](#S6.F2). The 2-IR critic approach leads to the best performing result by significant margin compared to the joint-action and 1-IR reward critics. For the 2-IR critic the maximum gap across agents is the smallest, meaning the joint policy is in a near equilibrium point. Interestingly, the simpler 1-IR model has the worst performance among the three candidates. Such an approach for critic modeling is common in the online cooperative MARL setting (Sunehag et al.,, ; Rashid et al.,, ; Yu et al.,, ). Nevertheless, as our experiments show, it can dramatically fail in offline MARL. This is because in the online setting, the agent can continually collect fresh samples to update the estimated 1-IR reward so that the critic can learn accurate local approximations of the current expected reward even if the other agents’ policies change. However, in offline setting, a 1-IR critic cannot make such updates because iterative data collection is not allowed. In the offline MARL setting, single agent critic models may be severely biased and degrade the performance of the learned policies.

## 7 Conclusions

In this work, we investigated the benefits of using reward models with low IR in the offline MARL setting. We showed that learning an approximate equilibrium in offline MARL can scale exponentially with the IR instead of exponentially with the number of agents. Our proposed algorithm is a decentralized, no-regret learning algorithm that can be implemented in practical settings while utilizing standard RL algorithms. The empirical results demonstrate superior performance of the critic with the smallest IR that can still represent the underlying true model in offline MARL, while the widely-used single-agent critic can fail catastrophically in this setting. Moving forward, building critics with low IR in MARL is a promising direction for future work, as well as exploring additional structural assumptions to alleviate the MARL problem.

## Appendix A Additional Experimental Details

**Table 2: Hyperparameters used in the experiments.**
| Hyperparameter | Value |
| --- | --- |
| Critic learning rate | 1e-4 |
| Critic batch size | 64 |
| Patience parameter for critic | 20 |
| Actor learning rate | 1e-3 |
| Actor batch size | 64 |
| Number of epochs | 500 |
| Optimizer | Adam |
| Policy architecture | MLP, 3 layers, width 128, w/ ReLu activations |
| TD3+BC $\alpha$ parameter | 5 |
| # of trials per experiment | 10 |

In this section we give additional information on the experiment design. Additional hyper-parameters related to training are given in Table [2](#A1.T2).

Our high-level implementation follows the framework of DR-AC and has three steps:

- 1.
Data collection. Collect data via a uniform policy, where each agent executes a random action $a_{i}\sim\mathrm{Uniform}([-1,1])$ for all $i\in[N]$.
- 2.
Learn critic. Learn $N$ reward critic models using LSR and the collected offline data. Namely, for each agent $i\in[N]$, estimate a reward critic by solving the following LSR:
$\arg\min_{r\in\mathcal{R}_{i}}\!\!\!\sum_{(r_{i})\in\mathcal{D}_{h}}\!\!\!\!\!(r()-r_{i})^{2}.$
We experiment with three types of reward critic types, namely, different reward classes $\mathcal{R}_{i}$: 1-IR, 2-IR, and joint-action critic models. We solve this by gradient descent, which iteratively samples a batch from $\mathcal{D}_{h}$, and takes a gradient step. Our method returns the critic with the smallest validation loss, calculated with respect to a holdout validation dataset, through the course of training. Lastly, if during the run the critic does not show improvement after number of steps specified by the ‘patience’ parameter we stop the run (see Table [2](#A1.T2) for hyper-parameter values).
- 3.
Learn actor. Apply TD3+BC on all agents to get a policy per agent.

Next we elaborate on the critic architectures we used and their implementation.

- 1.
Joint-action critic. We experimented with architectures with 3 layers and 2 layers. Recall that $N$ is the number of agents. The 3 layer architectures are of size $N\times\mathrm{width}\times\mathrm{width}\times\mathrm{width}\times 1$ where $\mathrm{width}\in[512,1028,2056]$, and the 2 layer architectures are of size $N\times\mathrm{width}\times\mathrm{width}\times 1$ where $\mathrm{width}\in[128,512,2056]$.
- 2.
2-IR critic. We experimented with 2 layer architectures of size $2\times\mathrm{width}\times\mathrm{width}\times 1$ where $\mathrm{width}\in[64,128,256]$. For the $i^{\mathrm{th}}$ agent, there are $N$ such networks, where each network represents the interaction term with the $j^{\mathrm{th}}$ agent. Let this network be denoted as $\mathrm{DNN}_{ij}:\mathcal{A}\times\mathcal{A}\rightarrow\mathbb{R}$. With these, the reward of the $i^{\mathrm{th}}$ agent is given by
$\displaystyle\hat{r}_{i}()=\sum_{j}\mathrm{DNN}_{ij}(a_{i},a_{j}).$
- 3.
1-IR critic. We experimented with 2 layer architectures of size $1\times\mathrm{width}\times\mathrm{width}\times 1$ where $\mathrm{width}\in[128,256,512],$ where the only input to the network is the action of the $i^{\mathrm{th}}$ agent.

The metric which we measure is the maximum gap defined by

$$ $\displaystyle\max_{i\in[N]}\max_{a_{i}\in[-1,1]}a_{i}\left(a_{i}+\sum_{j\neq i}\pi_{j}\right)-\pi_{i}\left(\sum_{j\in[N]}\pi_{j}\right),$ $$

where $\pi_{j}$ is the policy for agent $j$ (note that here we use deterministic policies). In particular, the above expression obtains its maximum at $a_{i}=\pm 1$.

Details of the environment with the underlying reward of 2-IR are presented in Section [6](#S6). Figure [3](#A1.F3) depicts additional results that measure the performance of various architectures for the 2-IR environment. As observed, the 2-IR critic consistently performs better compared to the joint-action architecture and the 1-IR architecture.

We experimented with an additional environment in which the underlying reward model is a 1-IR reward model of the form $\forall i\in[N],\ r^{\star}_{i}(\bm{s},)=a_{i}^{2}+\epsilon$. Additional parameters of the environment are similar to those described in Section [6](#S6). Since the underlying reward model is a 1-IR, we expect the 1-IR critic type to result in good performance. Further, since the 2-IR critic is not significantly more expressive compared to the 1-IR critic, we may expect it to have good performance as well. Figure [4](#A1.F4) depicts the results of this experiment for all reward critic types and architectures. These show that both the 1-IR and 2-IR reward critics have good performance, whereas the joint-action critic performs significantly worse with respect to the maximum gap metric.

Figure: Figure 3: Comparison of TD3+BC instantiated with different critic architectures, i) 1-IR critic, ii) 2-IR critic, and iii) joint-action critic. The underlying true reward is a 2-IR. The shaded area represents the standard error computed across trials.
Refer to caption: /html/2410.01101/assets/figures/2IR_low.png

Figure: Figure 4: Comparison of TD3+BC instantiated with different critic architectures, i) 1-IR critic, ii) 2-IR critic, and iii) joint-action critic. The underlying true reward is a 1-IR. The shaded area represents the standard error computed across trials.
Refer to caption: /html/2410.01101/assets/figures/1IR_low.png

## Appendix B Q-function Estimation

In this section we provide a computationally efficient method to estimate $\widehat{Q}^{t}_{i,h}$ in [Algorithm 1](#alg1). We assume access to a function class $\{\mathcal{F}_{i}\}_{i\in[N]}$ where $\mathcal{F}_{i}\subseteq\{f:\mathcal{C}\times\mathcal{S}_{i}\times\mathcal{A}_{i}\to[0,H]\}$ to approximate the single-agent Q-functions. The full algorithm is shown in [Algorithm 2](#alg2).

Specifically, in [Algorithm 2](#alg2), we will sample $c\sim\rho,s_{i,h}\sim\sigma_{i,h}(\cdot|c),a_{i,h}\sim\frac{1}{2}\nu_{i,h}(\cdot|c,s_{i,h})+\frac{1}{2}\pi_{i,h}(\cdot|c,s_{i,h}),(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi^{t}_{-i}}_{h}(\cdot|c)$ and then roll out the joint policy $\pi^{t}$ in $\widehat{P}$. It can be observed that the cumulative reward $q$ is indeed an unbiased estimate of $\widehat{Q}^{t}_{i,h}(c,s_{i,h},a_{i,h})$. Notably, we sample the state $s_{i,h}$ from the offline dataset to leverage the offline information. We also sample $a_{i,h}$ from $\frac{1}{2}\nu_{i,h}+\frac{1}{2}\pi^{t}_{i,h}$ such that the actions can cover the current policy $\pi^{t}_{i,h}$ and the competing policy $\mu_{i,h}$, which has bounded $\chi^{2}$-divergence from $\nu_{i,h}$. Then we only need to run LSR on the collected batch to estimate the Q-function. In summary, we can see that [Algorithm 2](#alg2) can be implemented with LSR oracles.

Figure: Algorithm 2 Q-function Estimation

### B.1 Theoretical Guarantee

Next we want to show that the estimated $\widetilde{Q}^{t}_{i,h}$ is close to $\widehat{Q}^{t}_{i,h}$. We have the following lemma:

###### Lemma 2 (Q-function estimation error) .

Suppose $\widehat{Q}^{t}_{i,h}\in\mathcal{F}_{i}$ for all $t,i,h$ and [4](#Thmassumption4) holds. With probability at least $1-\delta$, we have for all $i,t,h,\mu_{i}\in\Pi_{i}(C)$ that

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{i}\sim d^{\mu_{i}}_{h}(\cdot|c)}\left[\left\langle\widehat{Q}^{t}_{i,h}(c,s_{i},\cdot)-\widetilde{Q}^{t}_{i,h}(c,s_{i},\cdot),\mu_{i,h}(\cdot|c,s_{i})-\pi^{t}_{i,h}(\cdot|c,s_{i})\right\rangle\right]$ $\displaystyle\lesssim\sqrt{\frac{CC_{\mathsf{S}}H^{2}\log(NTH|\mathcal{F}|/\delta)}{M_{\mathsf{sim}}}}.$ $$

Recall that for any two functions $g$ and $g^{\prime}$, $g\lesssim g^{\prime}$ means that there exsits a constant $c>0$ such that $g<cg^{\prime}$ always holds. Note that from the proof of [Theorem 3](#Thmtheorem3), [Lemma 2](#Thmlemma2) suggests that we can use $\widetilde{Q}^{t}_{i,h}$ as a surrogate of $\widehat{Q}^{t}_{i,h}$ and [Theorem 3](#Thmtheorem3) still holds as long as $M_{\mathsf{sim}}\gtrsim\frac{CC_{\mathsf{S}}H^{2}\log(NTH|\mathcal{F}|/\delta)}{\epsilon^{2}}$. Therefore, [Algorithm 2](#alg2) is indeed a computationally and statistically efficient Q-function estimator.

###### Lemma 2 (Q-function estimation error) .

#### Proof of Lemma 2 .

From the guarantee of LSR ([Lemma 13](#Thmlemma13)), we know with probability at least $1-\delta$ that for all $i\in[N],t\in[T],h\in[H]$

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{i}\sim\sigma_{i,h}(\cdot|c),a_{i}\sim\frac{1}{2}\nu_{i,h}(\cdot|c,s_{i,h})+\frac{1}{2}\pi^{t}_{i,h}(\cdot|c,s_{i,h})}\bigg{[}\bigg{(}\widehat{Q}^{t}_{i,h}(c,s_{i},a_{i})-\widetilde{Q}^{t}_{i,h}(c,s_{i},a_{i})\bigg{)}^{2}\bigg{]}$ $\displaystyle\lesssim\frac{H^{2}\log(NTH|\mathcal{F}|/\delta)}{M_{\mathsf{sim}}}.$ $$

Therefore, from Cauchy-Schwartz, we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{i}\sim d^{\mu_{i}}_{h}(\cdot|c),a_{i}\sim\pi^{t}_{i,h}(\cdot|c,s_{i})}\left[\left|\widehat{Q}^{t}_{i,h}(c,s_{i},a_{i})-\widetilde{Q}^{t}_{i,h}(c,s_{i},a_{i})\right|\right]\lesssim\sqrt{\frac{C_{\mathsf{S}}H^{2}\log(NTH|\mathcal{F}|/\delta)}{M_{\mathsf{sim}}}}.$ $$

On the other hand, since $\mu_{i}\in\Pi_{i}(C)$, from [Lemma 5](#Thmlemma5) we know

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{i}\sim d^{\mu_{i}}_{h}(\cdot|c),a_{i}\sim\mu_{i,h}(\cdot|c,s_{i})}\left[\left|\widehat{Q}^{t}_{i,h}(c,s_{i},a_{i})-\widetilde{Q}^{t}_{i,h}(c,s_{i},a_{i})\right|\right]\lesssim\sqrt{\frac{CC_{\mathsf{S}}H^{2}\log(NTH|\mathcal{F}|/\delta)}{M_{\mathsf{sim}}}}.$ $$

Therefore we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{i}\sim d^{\mu_{i}}_{h}(\cdot|c)}\left[\left\langle\widehat{Q}^{t}_{i,h}(c,s_{i},\cdot)-\widetilde{Q}^{t}_{i,h}(c,s_{i},\cdot),\mu_{i,h}(\cdot|c,s_{i})-\pi^{t}_{i,h}(\cdot|c,s_{i})\right\rangle\right]$ $\displaystyle\lesssim\sqrt{\frac{CC_{\mathsf{S}}H^{2}\log(NTH|\mathcal{F}|/\delta)}{M_{\mathsf{sim}}}}.$ $$

## Appendix C Proofs in Section 3

### C.1 Proof of Theorem 1

We first define a specific IR decomposition for any function $f$ in [Definition 2](#Thmdefinition2) that is useful in the rest of the proof.

###### Lemma 3 (Standardized IR Decomposition) .

For any function $f$ with interaction rank $K$ and training distribution $x\sim p,y_{i}\sim p_{i}(\cdot|x),\forall i$, there exists a group of sub-functions $\cup_{0\leq k\leq K-1}\{g^{\prime}_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ where

$$ $\displaystyle\mathbb{E}_{y_{j_{l}}\sim p_{j_{l}}(\cdot|x)}[g^{\prime}_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})]=0$ (5) $$

for all $k\in[K-1],l\in[k],x\in\mathcal{X},y_{j_{l^{\prime}}}\in\mathcal{Y}_{j_{l^{\prime}}}(l^{\prime}\neq l)$ and

$$ $\displaystyle f(x,y_{1},\cdots,y_{W})=\sum_{k=0}^{K-1}\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}g^{\prime}_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}}),\forall x\in\mathcal{X},y_{1}\in\mathcal{Y}_{1},\cdots,y_{W}\in\mathcal{Y}_{W}.$ $$

We call this group of sub-functions $\cup_{0\leq k\leq K-1}\{g^{\prime}_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ the standardized IR decomposition of $f$.

The standardized decomposition separates the variations and mean of $f$ under the training distribution. With [Lemma 3](#Thmlemma3), we are able to provide an upper bound per-sub-function fitting error by simply fitting their summation $f$:

###### Lemma 4 (Sub-function Alignment) .

For any functions $f^{\star}$ and $\widehat{f}$ with interaction rank $K$, let $\cup_{0\leq k\leq K-1}\{g_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ and $\cup_{0\leq k\leq K-1}\{\widehat{g}_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ denote the standardized decomposition of $f^{\star}$ and $\widehat{f}$ in [Lemma 3](#Thmlemma3). Assume that the following holds

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{1}\sim p_{1}(\cdot|x),\cdots,y_{W}\sim p_{W}(\cdot|x)}\left[\left((f^{\star}-\widehat{f})(x,y_{1},\cdots,y_{W})\right)^{2}\right]\leq\epsilon.$ $$

Then for any $0\leq k\leq K-1$ and $1\leq j_{1}<\cdots<j_{k}\leq W$, we have:

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{1}}\sim p_{j_{1}}(\cdot|x),\cdots,y_{j_{k}}\sim p_{j_{k}}(\cdot|x)}\left[\left(\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right]\leq 2^{k}\epsilon,$ $$

where $\Delta_{j_{1},\cdots,j_{k}}:=g_{j_{1},\cdots,j_{k}}-\widehat{g}_{j_{1},\cdots,j_{k}}$.

[Lemma 4](#Thmlemma4) implies that the learning error of standardized sub-functions can be upper bounded by the fitting error of $f$ efficiently when the interaction rank is small. This property is the key reason why interaction rank is a more precise measure of the function complexity than the input size.

Now let $\cup_{0\leq k\leq K-1}\{g_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ and $\cup_{0\leq k\leq K-1}\{\widehat{g}_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ denote the standardized decomposition of $f^{\star}$ and $\widehat{f}$. Then from [Lemma 4](#Thmlemma4), we know for any $0\leq k\leq K-1$ and $j_{1}<\cdots<j_{k}$ that

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{1}}\sim p_{j_{1}}(\cdot|x),\cdots,y_{j_{k}}\sim p_{j_{k}}(\cdot|x)}\left[\left(\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right]\leq 2^{k}\epsilon,$ $$

which implies that

$$ $\displaystyle\mathbb{E}_{x\sim p^{\prime},y_{j_{1}}\sim p^{\prime}_{j_{1}}(\cdot|x),\cdots,y_{j_{k}}\sim p^{\prime}_{j_{k}}(\cdot|x)}\left[\left(\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right]\leq(C_{\mathsf{DS}})^{k+1}2^{k}\epsilon.$ (6) $$

On the other hand, we know

$$ $\displaystyle\mathbb{E}_{x\sim p^{\prime},y_{1}\sim p^{\prime}_{1}(\cdot|x),\cdots,y_{W}\sim p^{\prime}_{W}(\cdot|x)}\left[\left((f^{\star}-\widehat{f})(x,y_{1},\cdots,y_{W})\right)^{2}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{x\sim p^{\prime},y_{1}\sim p^{\prime}_{1}(\cdot|x),\cdots,y_{W}\sim p^{\prime}_{W}(\cdot|x)}\left[\left(\sum_{k=0}^{K-1}\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right]$ $\displaystyle\lesssim$ $\displaystyle W^{K-1}\sum_{k=0}^{K-1}\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}\mathbb{E}_{x\sim p^{\prime},y_{j_{1}}\sim p^{\prime}_{j_{1}}(\cdot|x),\cdots,y_{j_{k}}\sim p^{\prime}_{j_{k}}(\cdot|x)}\left[\left(\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right],$ $$

where the last step is due to AM-GM inequality. Now substitute [Eq. 6](#A3.E6) into the above inequality, we have

$$ $\displaystyle\mathbb{E}_{x\sim p^{\prime},y_{1}\sim p^{\prime}_{1}(\cdot|x),\cdots,y_{W}\sim p^{\prime}_{W}(\cdot|x)}\left[\left((f^{\star}-\widehat{f})(x,y_{1},\cdots,y_{W})\right)^{2}\right]\lesssim(2W)^{2(K-1)}C_{\mathsf{DS}}^{K}\epsilon.$ $$

This concludes our proof.

###### Lemma 3 (Standardized IR Decomposition) .

###### Lemma 4 (Sub-function Alignment) .

### C.2 Proof of Lemma 3

From [Definition 2](#Thmdefinition2), we know that there exists a group of sub-functions $\cup_{0\leq k\leq K-1}\{g_{j_{1},\cdots,j_{k}}\}_{j_{1}<\cdots<j_{k}}$ which satisfies

$$ $\displaystyle f(x,y_{1},\cdots,y_{W})=\sum_{k=0}^{K-1}\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}g_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}}),\forall x\in\mathcal{X},y_{1}\in\mathcal{Y}_{1},\cdots,y_{W}\in\mathcal{Y}_{W}.$ $$

We prove the proposition with induction on $K$. First for $K=1$, [Lemma 3](#Thmlemma3) holds naturally. Now we suppose the proposition holds for $K-1$ where $K\geq 2$. Then for any $\{j_{l}\}_{l=1}^{K-1}$, we can construct $g^{\prime}_{j_{1},\cdots,j_{K-1}}(x,y_{j_{1}},\cdots,y_{j_{K-1}})$ as follows:

$$ $\displaystyle g^{\prime}_{j_{1},\cdots,j_{K-1}}(x,y_{j_{1}},\cdots,y_{j_{K-1}})=g_{j_{1},\cdots,j_{K-1}}(x,y_{j_{1}},\cdots,y_{j_{K-1}})$ $\displaystyle\qquad+\sum_{k=1}^{K-1}(-1)^{k}\sum_{1\leq l_{1}<\cdots<l_{k}\leq K-1}\mathbb{E}_{y_{j_{l_{1}}}\sim p_{j_{l_{1}}}(\cdot|x),\cdots,y_{j_{l_{k}}}\sim p_{j_{l_{k}}}(x)}\left[g_{j_{1},\cdots,j_{K-1}}(x,y_{j_{1}},\cdots,y_{j_{K-1}})\right].$ $$

It can be verified that $g^{\prime}_{j_{1},\cdots,j_{K-1}}(x,y_{j_{1}},\cdots,y_{j_{K-1}})$ satisfies the property of standardized decomposition, i.e., [Eq. 5](#A3.E5). Now consider the function $f^{\prime}$:

$$ $\displaystyle f^{\prime}(x,y_{1},\cdots,y_{W})=f(x,y_{1},\cdots,y_{W})-\sum_{1\leq j_{1}<\cdots<j_{K-1}\leq W}g^{\prime}_{j_{1},\cdots,j_{K-1}}(x,y_{j_{1}},\cdots,y_{j_{K-1}}).$ $$

Note that $f^{\prime}$ satisfies [Definition 2](#Thmdefinition2) with IR $K-1$. By induction hypothesis, we know there exists a standardized decomposition for $f^{\prime}$:

$$ $\displaystyle f^{\prime}(x,y_{1},\cdots,y_{W})=\sum_{k=0}^{K-2}\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}g^{\prime}_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}}),\forall x\in\mathcal{X},y_{1}\in\mathcal{Y}_{1},\cdots,y_{W}\in\mathcal{Y}_{W}.$ $$

where $g^{\prime}_{j_{1},\cdots,j_{k}}$ satisfies the requirement in [Eq. 5](#A3.E5) for all $k\in[K-2]$. This implies that we have

$$ $\displaystyle f(x,y_{1},\cdots,y_{W})=\sum_{k=0}^{K-1}\sum_{1\leq j_{1}<\cdots<j_{k}\leq W}g^{\prime}_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}}),\forall x\in\mathcal{X},y_{1}\in\mathcal{Y}_{1},\cdots,y_{W}\in\mathcal{Y}_{W},$ $$

where $g^{\prime}_{j_{1},\cdots,j_{k}}$ satisfies the requirement in [Eq. 5](#A3.E5) for all $k\in[K-1]$. Therefore the argument holds for $K$ as well. By induction we can prove the proposition.

### C.3 Proof of Lemma 4

Fix any $0\leq k\leq K-1$ and $1\leq j_{1}<\cdots<j_{k}\leq W$. With slight abuse of notations, we also use $f^{\star}$ and $\widehat{f}$ to denote the expected function value under the training distribution:

$$ $\displaystyle f^{\star}(x,y_{j_{1}},\cdots,y_{j_{k}}):=\mathbb{E}_{y_{j}\sim p_{j}(\cdot|x),\forall j\notin\{j_{l}\}_{l\in[k]}}\left[f(x,y_{1},\cdots,y_{W})\right],$ $\displaystyle\widehat{f}(x,y_{j_{1}},\cdots,y_{j_{k}}):=\mathbb{E}_{y_{j}\sim p_{j}(\cdot|x),\forall j\notin\{j_{l}\}_{l\in[k]}}\left[\widehat{f}(x,y_{1},\cdots,y_{W})\right].$ $$

From Cauchy-Schwartz inequality, we can observe that

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{l}}\sim p_{j_{l}}(\cdot|x),\forall l\in[k]}\left[\left((f^{\star}-\widehat{f})(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right]\leq\epsilon.$ (7) $$

Since we are considering standardized decomposition, from [Lemma 3](#Thmlemma3) we have

$$ $\displaystyle f^{\star}(x,y_{j_{1}},\cdots,y_{j_{k}})=\sum_{k^{\prime}=0}^{k}\sum_{1\leq l_{1}<\cdots<l_{k^{\prime}}\leq k}g_{j_{l_{1}},\cdots,j_{l_{k^{\prime}}}}(x,y_{j_{l_{1}}},\cdots,y_{j_{l_{k^{\prime}}}}),$ $\displaystyle\widehat{f}(x,y_{j_{1}},\cdots,y_{j_{k}})=\sum_{k^{\prime}=0}^{k}\sum_{1\leq l_{1}<\cdots<l_{k^{\prime}}\leq k}\widehat{g}_{j_{l_{1}},\cdots,j_{l_{k^{\prime}}}}(x,y_{j_{l_{1}}},\cdots,y_{j_{l_{k^{\prime}}}}).$ $$

Now we use symmetrization trick to prove the result. Consider the following symmetrization operation of function $f$:

$$ $\displaystyle G(f^{\star})(x,\{y_{j_{l}}\}_{l\in[k]},\{y^{\prime}_{j_{l}}\}_{l\in[k]}):=\sum_{k^{\prime}=0}^{k}(-1)^{k^{\prime}}\sum_{1\leq l_{1}<\cdots<l_{k^{\prime}}\leq k}f^{\star}(x,\{y_{j_{l}}\}_{l\notin\{l_{1},\cdots,l_{k^{\prime}}\}},\{y^{\prime}_{j_{l}}\}_{l\in\{l_{1},\cdots,l_{k^{\prime}}\}}).$ $$

It can be verified that

$$ $\displaystyle G(f^{\star})(x,\{y_{j_{l}}\}_{l\in[k]},\{y^{\prime}_{j_{l}}\}_{l\in[k]})=\sum_{k^{\prime}=0}^{k}(-1)^{k^{\prime}}\sum_{1\leq l_{1}<\cdots<l_{k^{\prime}}\leq k}g_{j_{1},\cdots,j_{k}}(x,\{y_{j_{l}}\}_{l\notin\{l_{1},\cdots,l_{k^{\prime}}\}},\{y^{\prime}_{j_{l}}\}_{l\in\{l_{1},\cdots,l_{k^{\prime}}\}}).$ $$

This implies that we have

$$ $\displaystyle(G(f^{\star}-\widehat{f}))(x,\{y_{j_{l}}\}_{l\in[k]},\{y^{\prime}_{j_{l}}\}_{l\in[k]})=\sum_{k^{\prime}=0}^{k}(-1)^{k^{\prime}}\sum_{1\leq l_{1}<\cdots<l_{k^{\prime}}\leq k}\Delta_{j_{1},\cdots,j_{k}}(x,\{y_{j_{l}}\}_{l\notin\{l_{1},\cdots,l_{k^{\prime}}\}},\{y^{\prime}_{j_{l}}\}_{l\in\{l_{1},\cdots,l_{k^{\prime}}\}}).$ (8) $$

On the one hand, from AM-GM inequality and [Eq. 7](#A3.E7) we have

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{l}}\sim p_{j_{l}}(\cdot|x),y^{\prime}_{j_{l}}\sim p_{j_{l}}(\cdot|x),\forall l\in[k]}\left[\left((G(f^{\star}-\widehat{f}))(x,\{y_{j_{l}}\}_{l\in[k]},\{y^{\prime}_{j_{l}}\}_{l\in[k]})\right)^{2}\right]\leq 2^{2k}\epsilon.$ $$

On the other hand, we can expand the left hand side of the above inequality:

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{l}}\sim p_{j_{l}}(\cdot|x),y^{\prime}_{j_{l}}\sim p_{j_{l}}(\cdot|x),\forall l\in[k]}\left[\left((G(f^{\star}-\widehat{f}))(x,\{y_{j_{l}}\}_{l\in[k]},\{y^{\prime}_{j_{l}}\}_{l\in[k]})\right)^{2}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{l}}\sim p_{j_{l}}(\cdot|x),y^{\prime}_{j_{l}}\sim p_{j_{l}}(\cdot|x),\forall l\in[k]}\left[\left(\sum_{k^{\prime}=0}^{k}(-1)^{k^{\prime}}\sum_{1\leq l_{1}<\cdots<l_{k^{\prime}}\leq k}\Delta_{j_{1},\cdots,j_{k}}(x,\{y_{j_{l}}\}_{l\notin\{l_{1},\cdots,l_{k^{\prime}}\}},\{y^{\prime}_{j_{l}}\}_{l\in\{l_{1},\cdots,l_{k^{\prime}}\}})\right)^{2}\right]$ $\displaystyle=$ $\displaystyle 2^{k}\mathbb{E}_{x\sim p,y_{j_{l}}\sim p_{j_{l}}(\cdot|x),\forall l\in[k]}\left[\left(\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right],$ $$

where the second step is due to [Eq. 8](#A3.E8) and the third step is because the cross terms are 0 due to the independence between $y_{j}$ and $y^{\prime}_{j}$ given $x$ and [Lemma 3](#Thmlemma3). Therefore we have

$$ $\displaystyle\mathbb{E}_{x\sim p,y_{j_{1}}\sim p_{j_{1}}(\cdot|x),\cdots,y_{j_{k}}\sim p_{j_{k}}(\cdot|x)}\left[\left(\Delta_{j_{1},\cdots,j_{k}}(x,y_{j_{1}},\cdots,y_{j_{k}})\right)^{2}\right]\leq 2^{k}\epsilon,$ $$

which concludes our proof.

## Appendix D Proof of Theorem 2

We first present the formal statement of [Theorem 2](#Thmtheorem2):

###### Theorem 4 .

Suppose [1](#Thmassumption1) hold. Let $\Pi_{i}(C):=\{\mu_{i}:\mathbb{E}_{c\sim\rho}[\chi^{2}(\mu_{i}(c),\nu_{i}(c))]\leq C\}$ denote the policy class which has bounded $\chi^{2}$-divergence from the behavior policy $\nu_{i}$. Fix any $\delta\in(0,1]$ and select

$$ $\displaystyle T=(2N^{2})^{-\frac{2K-2}{3K-1}}\epsilon^{-\frac{2}{3K-1}},\qquad\eta=\lambda=(2N^{2})^{\frac{K-1}{3K-1}}\epsilon^{\frac{1}{3K-1}}.$ $$

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

$$ $\displaystyle\max_{i}\mathsf{Gap}_{i}(\widehat{\pi})\lesssim\max_{i\in[N]}\min_{C\geq 1}\left\{C\left((2N^{2})^{K-1}\epsilon\right)^{\frac{1}{3K-1}}+\mathsf{subopt}_{i}(C,\widehat{\pi})\right\},$ $$

where $\mathsf{subopt}_{i}(C,\widehat{\pi}):=\max_{\mu_{i}\in\Pi_{i}}r^{\star}_{i}(\mu_{i},\widehat{\pi}_{-i})-\max_{\mu_{i}\in\Pi_{i}(C)}r^{\star}_{i}(\mu_{i},\widehat{\pi}_{-i})$ is the off-support bias.

###### Theorem 4 .

#### Proof of Theorem 4 .

Note that for any agent $i\in[N]$ and policy $\mu_{i}\in\Pi_{i}(C)$ where $C>1$, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(r^{\star}_{i}(\mu_{i},\pi^{t}_{-i})-r^{\star}_{i}(\pi^{t})\right)=$ $\displaystyle\underbrace{\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(c),_{-i}\sim\pi^{t}_{-i}}[(r^{\star}_{i}-\widehat{r}_{i})(c,)]}_{(1)}$ $\displaystyle+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,\sim\pi^{t}}[(\widehat{r}_{i}-r^{\star}_{i})(c,)]}_{(2)}+\underbrace{\sum_{t=1}^{T}\left(\widehat{r}_{i}(\mu_{i},\pi^{t}_{-i})-\widehat{r}_{i}(\pi^{t})\right)}_{(3)}.$ (9) $$

With slight abuse of the notations, we use $\cup_{0\leq k\leq K-1}\{g^{i}_{j_{1},\cdots,j_{k}}\}$ and $\cup_{0\leq k\leq K-1}\{\widehat{g}^{i}_{j_{1},\cdots,j_{k}}\}$ to denote the standardized decomposition of $r^{\star}_{i}$ and $\widehat{r}_{i}$, as defined in [Lemma 3](#Thmlemma3). We also use $\Delta^{i}_{j_{1},\cdots,j_{k}}$ to denote $g^{i}_{j_{1},\cdots,j_{k}}-\widehat{g}^{i}_{j_{1},\cdots,j_{k}}$. First note that from [Lemma 4](#Thmlemma4), we have for all $i\in[N],0\leq k\leq K-1$ and $1\leq j_{1}<\cdots<j_{k}\leq N$ where $j_{l}\neq i$ for all $l\in[k]$ that:

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\nu_{i}(\cdot|c),a_{j_{l}}\sim\nu_{j_{l}}(\cdot|c),\forall l\in[k]}\left[\left(\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right)^{2}\right]\leq 2^{k}\epsilon,$ (10) $$

Next we bound terms (1), (2) and (3) in [Eq. 9](#A4.E9) respectively.

#### Bounding term (1).

For term (1), from [Lemma 3](#Thmlemma3), we know for all policy $\mu_{i}\in\Pi_{i}(C)$ where $C\geq 1$ that:

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),_{-i}\sim\pi^{t}_{-i}(\cdot|c)}[(r^{\star}_{i}-\widehat{r}_{i})(c,)]$ $\displaystyle=\sum_{k=0}^{K}\sum_{1\leq j_{1}<\cdots<j_{k}\leq N:j_{l}\neq i,\forall l\in[k]}\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),a_{j_{l}}\sim\pi^{t}_{j_{l}}(\cdot|c),\forall l\in[k]}\left[\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right].$ $$

To quantify the above transfer error, we have the following lemma which leverages the $\chi^{2}$-divergence between the target distribution and training distribution:

###### Lemma 5 .

For two distributions $d^{1},d^{2}\in\Delta(\mathcal{Z})$ and any function $f$ defined on $\mathcal{Z}$, we have

$$ $\displaystyle\mathbb{E}_{z\sim d^{1}}[f(z)]\leq\sqrt{\mathbb{E}_{z\sim d^{2}}[(f(z))^{2}](1+\chi^{2}(d^{1},d^{2}))}.$ $$

###### Proof.

Note that we have

$$ $\displaystyle 1+\chi^{2}(d^{1},d^{2})=1+\sum_{z\in\mathcal{Z}}\frac{\left(d^{1}(z)-d^{2}(z)\right)^{2}}{d^{2}(z)}=\sum_{z\in\mathcal{Z}}\frac{\left(d^{1}(z)\right)^{2}}{d^{2}(z)}.$ $$

Then the lemma comes directly from Cauchy-Schwartz inequality.
∎

From [Lemma 5](#Thmlemma5) we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(\cdot|c),a_{j_{l}}\sim\pi^{t}_{j_{l}}(\cdot|c),\forall l\in[k]}\left[\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right]$ $\displaystyle\qquad\leq\sqrt{\mathbb{E}_{c\sim\rho,a_{i}\sim\nu_{i}(c),a_{j_{l}}\sim\nu_{j_{l}}(\cdot|c),\forall l\in[k]}\left[\left(\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right)^{2}\right]}$ $\displaystyle\qquad\quad\cdot\sqrt{\left(1+\chi^{2}\left(\rho\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)\right)}$ $\displaystyle\qquad\leq\sqrt{2^{k}\epsilon\left(1+\chi^{2}\left(\rho\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)\right)},$ $$

where recall that we use $\rho\circ p$ to denote the joint distribution $c\sim\rho,a\sim p(\cdot|c)$ for some conditional distribution $p$. In the last step we utilize [Eq. 10](#A4.E10).

Now we only need to bound $\chi^{2}$-divergence between $\rho\circ\mu_{i}\circ\prod_{l\in[k]}\pi^{t}_{j_{l}}$ and $\rho\circ\nu_{i}\circ\prod_{l\in[k]}\nu_{j_{l}}$. We achieve this with the following lemma:

###### Lemma 6 .

For any $2k$ policies $\{p_{j}\}_{j=1}^{k}$ and $\{q_{j}\}_{j=1}^{k}$, we have

$$ $\displaystyle 1+\chi^{2}\left(\rho\circ\prod_{j=1}^{k}p_{j},\rho\circ\prod_{j=1}^{k}q_{j}\right)=\mathbb{E}_{c\sim\rho}\left[\prod_{j=1}^{k}\left(1+\chi^{2}\left(p_{j}(c),q_{j}(c)\right)\right)\right].$ $$

###### Proof.

Note that we have

$$ $\displaystyle 1+\chi^{2}\left(\rho\circ\prod_{j=1}^{k}p_{j},\rho\circ\prod_{j=1}^{k}q_{j}\right)=\sum_{c,a_{1},\cdots,a_{k}}\frac{\left(\rho(c)\prod_{j\in[k]}p_{j}(a_{j}|c)\right)^{2}}{\rho(c)\prod_{j\in[k]}q_{j}(a_{j}|c)}$ $\displaystyle\qquad=\sum_{c}\rho(c)\sum_{a_{1},\cdots,a_{k}}\frac{\left(\prod_{j\in[k]}p_{j}(a_{j}|c)\right)^{2}}{\prod_{j\in[k]}q_{j}(a_{j}|c)}=\sum_{c\in\mathcal{S}}\rho(c)\prod_{j\in[k]}\left(\sum_{a_{j}}\frac{\left(p_{j}(a_{j}|c)\right)^{2}}{q_{j}(a_{j}|c)}\right)$ $\displaystyle\qquad=\sum_{c}\rho(c)\prod_{j\in[k]}\left(1+\chi^{2}\left(p_{j}(c),q_{j}(c)\right)\right)=\mathbb{E}_{c\sim\rho}\left[\prod_{j=1}^{k}\left(1+\chi^{2}\left(p_{j}(c),q_{j}(c)\right)\right)\right].$ $$

∎

Therefore, from [Lemma 6](#Thmlemma6) we have

$$ $\displaystyle 1+$ $\displaystyle\chi^{2}\left(\rho\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)$ (11) $\displaystyle=\mathbb{E}_{c\sim\rho}\left[\left(\chi^{2}(\mu_{i}(c),\nu_{i}(c))+1\right)\prod_{l\in[k]}(\chi^{2}(\pi^{t}_{j_{l}}(c),\nu_{j_{l}}(c))+1)\right].$ $$

Meanwhile, from the policy update formula [Eq. 2](#S4.E2), we have for all $t\in[T]$ and $c\in\mathcal{C}$:

$$ $\displaystyle-\langle\widehat{r}^{t}_{i}(c,\cdot),\pi^{t+1}_{i}(c)\rangle+\lambda\chi^{2}(\pi^{t+1}_{i}(c),\nu_{i}(c))+\frac{1}{\eta}D_{c,i}(\pi^{t+1}_{i}(c),\pi^{t}_{i}(c))$ $\displaystyle\qquad\leq-\langle\widehat{r}^{t}_{i}(c,\cdot),\pi^{t}_{i}(c)\rangle+\lambda\chi^{2}(\pi^{t}_{i}(c),\nu_{i}(c))+\frac{1}{\eta}D_{c,i}(\pi^{t}_{i}(c),\pi^{t}_{i}(c)).$ $$

Note that $D_{c,i}(\pi^{t}_{i}(c),\pi^{t}_{i}(c))=0$ and $\widehat{r}^{t}_{i}\in[0,1]$, we know

$$ $\displaystyle\chi^{2}(\pi^{t+1}_{i}(c),\nu_{i}(c))\leq\chi^{2}(\pi^{t}_{i}(c),\nu_{i}(c))+\frac{1}{\lambda}.$ $$

Since $\chi^{2}(\pi^{1}_{i}(c),\nu_{i}(c))=\chi^{2}(\nu_{i}(c),\nu_{i}(c))=0$, for all $t\in[T]$ and $s\in\mathcal{S}$ we have

$$ $\displaystyle\chi^{2}(\pi^{t}_{i}(c),\nu_{i}(c))\leq\frac{t-1}{\lambda},\forall t\in[T+1].$ (12) $$

Substitute [Eq. 12](#A4.E12) into [Eq. 11](#A4.E11) and we have

$$ $\displaystyle 1+\chi^{2}\left(\rho\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)$ $\displaystyle\leq\left(\frac{T}{\lambda}\right)^{k}\mathbb{E}_{c\sim\rho}\left[\left(\chi^{2}(\mu_{i}(c),\nu_{i}(c))+1\right)\right]$ $\displaystyle\leq(C+1)\left(\frac{T}{\lambda}\right)^{k},$ $$

where the second step is due to $\mu_{i}\in\Pi_{i}(C)$.

Therefore, we have for all policies $\mu_{i}\in\Pi_{i}(C)$ where $C\geq 1$ that

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\mu_{i}(c),a_{j_{l}}\sim\pi^{t}_{j_{l}}(\cdot|c),\forall l\in[k]}\left[\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right]\lesssim\sqrt{C\epsilon\cdot\left(\frac{2T}{\lambda}\right)^{k}}.$ $$

This implies that we have

$$ $\displaystyle(1)\lesssim T\sum_{k=0}^{K-1}\mathbb{C}^{k}_{N-1}\sqrt{C\epsilon_{i}\cdot\left(\frac{T}{\lambda}\right)^{k}}\lesssim T\sqrt{C\epsilon\cdot\left(\frac{2TN^{2}}{\lambda}\right)^{K-1}}.$ (13) $$

Here $\mathbb{C}$ is the combination number.

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

#### Bounding term (2).

Similarly, for term (2), following the same arguments as bounding term (1), we know for all policy $\mu_{i}\in\Pi_{i}(C)$ where $C\geq 1$ that:

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\pi^{t}_{i}(c),a_{j_{l}}\sim\pi^{t}_{j_{l}}(c),\forall l\in[k]}\left[\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right]\leq\sqrt{\epsilon\left(\mathbb{E}_{x\sim\rho}[f_{c,i}(\pi^{t}_{i})]+1\right)\cdot\left(\frac{2T}{\lambda}\right)^{k}}.$ $$

Recall that we use $f_{c,i}(p)$ to denote the chi-squared divergence $\chi^{2}(p,\nu_{i}(c))$. Then with AM-GM inequality, we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,a_{i}\sim\pi^{t}_{i}(c),a_{j_{l}}\sim\pi^{t}_{j_{l}}(c),\forall l\in[k]}\left[\Delta^{i}_{j_{1},\cdots,j_{k}}(c,a_{i},a_{j_{1}},\cdots,a_{j_{k}})\right]$ $\displaystyle\qquad\leq\frac{\lambda}{N^{K-1}}\mathbb{E}_{x\sim\rho}[f_{c,i}(\pi^{t}_{i})]+\frac{N^{K-1}}{\lambda}\cdot\left(\frac{2T}{\lambda}\right)^{k}\cdot\epsilon+\sqrt{\epsilon\cdot\left(\frac{2T}{\lambda}\right)^{k}}.$ $$

Therefore, we have

$$ $\displaystyle(2)-\lambda\sum_{t=1}^{T}\mathbb{E}_{x\sim\rho}[f_{c,i}(\pi^{t}_{i})]\lesssim\frac{T}{\lambda}\cdot\left(\frac{2TN^{2}}{\lambda}\right)^{K-1}\cdot\epsilon+T\sqrt{\epsilon\cdot\left(\frac{2TN^{2}}{\lambda}\right)^{K-1}}.$ (14) $$

#### Bounding term (3).

First we have the following lemma to characterize the no-regret guarantee of regularized policy gradient (see Appendix [D.1](#A4.SS1) for proof):

###### Lemma 7 (No-Regret Regularized Policy Gradient) .

Given a sequence of loss functions $\{l^{t}\}_{t\in[T]}$ where $l^{t}:\mathcal{X}\times\mathcal{Y}\to[0,B]$ for some $B>0$ and a reference policy $\nu:\mathcal{X}\mapsto\Delta_{\mathcal{Y}}$. Suppose we initialize $p^{1}$ to be $\nu$ and run the following regularized policy gradient for $T$ iterations:

$$ $\displaystyle p^{t+1}(x)=\arg\min_{p\in\Delta_{\mathcal{Y}}}-\langle l^{t}(x,\cdot),p\rangle+\lambda\chi^{2}(p,\nu(x))+\frac{1}{\eta}D_{x}(p,p^{t}),$ $$

where $D_{x}(p,p^{t})$ is the Bregman divergence between $p(x)$ and $p^{t}(x)$. Then we have for all policy $\mu$ and $x\in\mathcal{X}$ that

$$ $\displaystyle\sum_{t=1}^{T}\left\langle l^{t}(x),\mu(x)-p^{t}(x)\right\rangle+\lambda\sum_{t=1}^{T+1}\chi^{2}(p^{t}(x),\nu(x))\leq\left(T\lambda+\frac{1}{\eta}\right)\chi^{2}(\mu(x),\nu(x))+\frac{\eta TB^{2}}{4}.$ $$

Note that $(3)=\sum_{t=1}^{T}\mathbb{E}_{x\sim\rho}[\left\langle\widehat{r}^{t}_{i}(c),\mu(c)-\pi^{t}(c)\right\rangle]$. Thus, [Lemma 7](#Thmlemma7) implies that for any policy $\mu_{i}\in\Pi_{i}(C)$, we have:

$$ $\displaystyle(3)+\lambda\sum_{t=1}^{T}\mathbb{E}_{x\sim\rho}[f_{c,i}(\pi^{t}_{i})]\lesssim$ $\displaystyle TC\lambda+\frac{C}{\eta}+\frac{\eta T}{4}.$ (15) $$

###### Lemma 7 (No-Regret Regularized Policy Gradient) .

#### Putting all pieces together.

Now substituting Eq ([13](#A4.E13)),([14](#A4.E14)),([15](#A4.E15)) into Eq ([9](#A4.E9)), we have for all policy $\mu_{i}\in\Pi_{i}(C)$ where $C\geq 1$ that

$$ $\displaystyle r^{\star}_{i}(\mu_{i},\widehat{\pi}_{-i})-r^{\star}_{i}(\widehat{\pi})\lesssim C\lambda+\frac{C}{\eta T}+\frac{\eta}{4}+\sqrt{C\epsilon\cdot\left(\frac{2TN^{2}}{\lambda}\right)^{K-1}}+\frac{1}{\lambda}\cdot\left(\frac{2TN^{2}}{\lambda}\right)^{K-1}\cdot\epsilon.$ $$

Therefore by setting

$$ $\displaystyle T=(2N^{2})^{-\frac{2K-2}{3K-1}}\epsilon^{-\frac{2}{3K-1}},\qquad\eta=\lambda=(2N^{2})^{\frac{K-1}{3K-1}}\epsilon^{\frac{1}{3K-1}},$ $$

we have for all policy $\mu_{i}\in\Pi_{i}(C)$ where $C\geq 1$ that

$$ $\displaystyle r^{\star}_{i}(\mu_{i},\widehat{\pi}_{-i})-r^{\star}_{i}(\widehat{\pi})\lesssim C\left((2N^{2})^{K-1}\epsilon\right)^{\frac{1}{3K-1}}.$ $$

This concludes our proof.

### D.1 Proof of Lemma 7

Let $f_{x}(p)$ denote the $\chi^{2}$-divergence $\chi^{2}(p(x),\nu(x))$. First due to first order optimality in the policy update step , we know for all $p:\mathcal{X}\to\Delta_{\mathcal{Y}}$ and all $t\in[T],x\in\mathcal{X}$ that:

$$ $\displaystyle\left\langle-\eta l^{t}(x)+(1+\eta\lambda)\nabla f_{x}(p^{t+1})-\nabla f_{x}(p^{t}),p(x)-p^{t+1}(x)\right\rangle\geq 0.$ (16) $$

This implies that for all $t\in[T],x\in\mathcal{X}$ and any policy $\mu$, we have

$$ $\displaystyle\left\langle\eta l^{t}(x),\mu(x)-p^{t}(x)\right\rangle+\eta\lambda f_{x}(p^{t})-\eta\lambda f_{x}(\mu)$ $\displaystyle=$ $\displaystyle\left\langle\eta l^{t}(x)-(1+\eta\lambda)\nabla f_{x}(p^{t+1})+\nabla f_{x}(p^{t}),\mu(x)-p^{t+1}(x)\right\rangle$ $\displaystyle+\left\langle\nabla f_{x}(p^{t+1})-\nabla f_{x}(p^{t}),\mu(x)-p^{t+1}(x)\right\rangle+\left\langle\eta l^{t}(x),p^{t+1}(x)-p^{t}(x)\right\rangle$ $\displaystyle+\left\langle\eta\lambda\nabla f_{x}(p^{t+1}),\mu(x)-p^{t+1}(x)\right\rangle+\eta\lambda f_{x}(p^{t})-\eta\lambda f_{x}(\mu),$ $\displaystyle\leq$ $\displaystyle\underbrace{\left\langle\nabla f_{x}(p^{t+1})-\nabla f_{x}(p^{t}),\mu(x)-p^{t+1}(x)\right\rangle}_{(4)}+\underbrace{\left\langle\eta l^{t}(x),p^{t+1}(x)-p^{t}(x)\right\rangle}_{(5)}$ $\displaystyle+\underbrace{\left\langle\eta\lambda\nabla f_{x}(p^{t+1}),\mu(x)-p^{t+1}(x)\right\rangle+\eta\lambda f_{x}(p^{t})-\eta\lambda f_{x}(\mu)}_{(6)}.$ $$

Next we bound terms (4), (5) and (6) respectively.

First for term (4), note that we have the following lemma:

###### Lemma 8 .

For any $i\in[N]$ and $p_{1},p_{2},p_{3}:\mathcal{X}\to\Delta_{\mathcal{Y}}$, we have for all $x\in\mathcal{X}$

$$ $\displaystyle\left\langle\nabla f_{x}(p_{1})-\nabla f_{x}(p_{2}),p_{3}(x)-p_{1}(x)\right\rangle=D_{x}(p_{3},p_{2})-D_{x}(p_{3},p_{1})-D_{x}(p_{1},p_{2}).$ $$

###### Proof.

By definition, we know

$$ $\displaystyle D_{x}(p,p^{\prime})=f_{x}(p)-f_{x}(p^{\prime})-\langle\nabla f_{x}(p^{\prime}),p-p^{\prime}\rangle.$ $$

Substitute the definition into [Lemma 8](#Thmlemma8) and we can prove the lemma.
∎

From Lemma [8](#Thmlemma8), we can rewrite (4) as follows:

$$ $\displaystyle(4)=D_{x}(\mu,p^{t})-D_{x}(\mu,p^{t+1})-D_{x}(p^{t+1},p^{t}).$ $$

Then for term (5), from Cauchy-Schwartz inequality, we have

$$ $\displaystyle(5)\leq\sum_{y\in\mathcal{Y}}\frac{(p^{t+1}(y|x)-p^{t}(y|x))^{2}}{\nu(y|x)}+\frac{\nu(y|x)\eta^{2}(l^{t}(x,y))^{2}}{4}\leq D_{x}(p^{t+1},p^{t})+\frac{\eta^{2}B^{2}}{4},$ $$

where the last step comes from the definition of $D_{x}$.

Finally for term (6), Since $f_{x}$ is convex, we know

$$ $\displaystyle\left\langle\eta\lambda\nabla f_{x}(p^{t+1}),\mu(x)-p^{t+1}(x)\right\rangle\leq\eta\lambda f_{x}(\mu)-\eta\lambda f_{x}(p^{t+1}).$ $$

This implies that

$$ $\displaystyle(6)\leq\eta\lambda\left(f_{x}(p^{t})-f_{x}(p^{t+1})\right).$ $$

In summary, for all $t\in[T],s\in\mathcal{S}$ and any policy $\mu$, we have

$$ $\displaystyle\left\langle\eta l^{t}(x),\mu(x)-p^{t}(x)\right\rangle+\eta\lambda f_{x}(p^{t})-\eta\lambda f_{x}(\mu)$ $\displaystyle\qquad\leq\left(D_{x}(\mu,p^{t})-D_{x}(\mu,p^{t+1})\right)+\eta\lambda\left(f_{x}(p^{t})-f_{x}(p^{t+1})\right)+\frac{\eta^{2}B^{2}}{4}.$ $$

Therefore, summing up from $t=1$ to $T$, we have

$$ $\displaystyle\sum_{t=1}^{T}\left\langle l^{t}(x),\mu(x)-p^{t}(x)\right\rangle+\lambda\sum_{t=1}^{T+1}\chi^{2}(p^{t}(x),\nu(x))\leq\left(T\lambda+\frac{1}{\eta}\right)\chi^{2}(\mu(x),\nu(x))+\frac{\eta TB^{2}}{4},$ $$

where we use the fact that $D_{x}(\mu,p^{1})=D_{x}(\mu,\nu)=\chi^{2}(p^{t}(x),\nu(x))$.

###### Lemma 8 .

###### Proof.

## Appendix E Proof of Theorem 3

Let $f_{c,s,i,h}(p)$ to denote the $\chi^{2}$-divergence ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{2}(p_{h}(c,s),\nu_{i,h}(c,s))$. Note that for any agent $i\in[N]$ and policy $\mu_{i}\in{\Pi}_{i}(C)$ where $C\geq 1$, we have

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho}\left[V^{\mu_{i}\circ\pi^{t}_{-i},r^{\star}}_{i,1}(c,\bm{s}_{1})\right]-\mathbb{E}_{c\sim\rho}\left[V^{\pi^{t},r^{\star}}_{i,1}(c,\bm{s}_{1})\right]$ $\displaystyle\qquad=\underbrace{\left(\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,\bm{s}_{h}\sim d^{\mu_{i}\circ\pi^{t}_{-i}}_{h}(\cdot|c),a_{i,h}\sim\mu_{i,h}(\cdot|c,s_{i,h}),_{-i,h}\sim\pi^{t}_{-i}(\cdot|c,\bm{s}_{-i,h})}\left[r^{\star}_{i,h}(c,\bm{s}_{h},_{h})-\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]\right)}_{(1)}$ $\displaystyle\qquad\quad+\underbrace{\left(\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,\bm{s}_{h}\sim d^{\pi^{t}}_{h}(\cdot|c),_{h}\sim\pi^{t}(\cdot|c,\bm{s}_{h})}\left[-r^{\star}_{i,h}(c,\bm{s}_{h},_{h})+\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]\right)}_{(2)}$ $\displaystyle\qquad\quad+\underbrace{\left(\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho}\left[V^{\mu_{i}\circ\pi^{t}_{-i},\widehat{r}}_{i,1}(c,\bm{s}_{1})\right]-\mathbb{E}_{c\sim\rho}\left[\widehat{V}^{\mu_{i}\circ\pi^{t}_{-i},\widehat{r}}_{i,1}(c,\bm{s}_{1})\right]\right)}_{(3)}$ $\displaystyle\qquad\quad+\underbrace{\left(\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho}\left[\widehat{V}^{\pi^{t},\widehat{r}}_{i,1}(c,\bm{s}_{1})\right]-\mathbb{E}_{c\sim\rho}\left[V^{\pi^{t},\widehat{r}}_{i,1}(c,\bm{s}_{1})\right]\right)}_{(4)}$ $\displaystyle\qquad\quad+\underbrace{\left(\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho}\left[\widehat{V}^{\mu_{i}\circ\pi^{t}_{-i},\widehat{r}}_{i,1}(c,\bm{s}_{1})\right]-\mathbb{E}_{c\sim\rho}\left[\widehat{V}^{\pi^{t},\widehat{r}}_{i,1}(c,\bm{s}_{1})\right]\right)}_{(5)},$ $$

where we use $\widehat{V}^{\pi,\widehat{r}}_{i,h}$ to denote the joint value function under reward $\widehat{r}$ and transition $\widehat{P}$. Next we will bounded these terms separately. In particular, terms (1) and (2) are bounded by statistical guarantees on the reward model and the distribution shift robustness of low IR models; term (3) and (4) are bounded by the statistical guarantees of the transition model, while using the decoupling property, and term (5) is bounded by no-regret analysis while identifying proper value and Q functions that satisfies Bellman equation.

We use $\cup_{0\leq k\leq K-1}\{g^{i,h}_{j_{1},\cdots,j_{k}}\}$ and $\cup_{0\leq k\leq K-1}\{\widehat{g}^{i,h}_{j_{1},\cdots,j_{k}}\}$ to denote the standardized decomposition of $r^{\star}_{i,h}$ and $\widehat{r}_{i,h}$, as defined in [Lemma 3](#Thmlemma3). We also use $\Delta^{i,h}_{j_{1},\cdots,j_{k}}$ to denote $g^{i,h}_{j_{1},\cdots,j_{k}}-\widehat{g}^{i,h}_{j_{1},\cdots,j_{k}}$. From [2](#Thmassumption2) and the LSR guarantee [Lemma 13](#Thmlemma13), with probability at least $1-\delta/2$ we have for all $i\in[N],h\in[H]$ that:

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{j}\sim\sigma_{j,h}(\cdot|c),a_{j}\sim\nu_{j,h}(\cdot|c,s_{j}),\forall j}\left[\left(r^{\star}_{h,i}(c,\bm{s},)-\widehat{r}_{h,i}(c,\bm{s},)\right)^{2}\right]\lesssim\frac{\log(NH|\mathcal{R}|/\delta)}{M}:={\epsilon}_{\mathsf{R}}.$ $$

Combining the above inequality with [Lemma 4](#Thmlemma4), we have for all $i\in[N],h\in[H],0\leq k\leq K-1$ and $1\leq j_{1}<\cdots<j_{k}\leq N$ where $j_{l}\neq i$ for all $l\in[k]$ that:

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{i}\sim\sigma_{i,h}(\cdot|c),a_{i}\sim\nu_{i}(\cdot|c,s_{i}),s_{j_{l}}\sim\sigma_{i,h}(\cdot|c),a_{j_{l}}\sim\nu_{j_{l}}(\cdot|c,s_{j_{l}}),\forall l\in[k]}\left[\left(\Delta^{i,h}_{j_{1},\cdots,j_{k}}(c,z_{i},z_{j_{1}},\cdots,z_{j_{k}})\right)^{2}\right]\leq 2^{k}{\epsilon}_{\mathsf{R}},$ $$

where we use $z_{j}$ to denote $(s_{j},a_{j})$. Next we bound terms (1), (2) and (3) in [Eq. 9](#A4.E9) respectively.

For term (1), fix $h\in[H]$ and $t\in[T]$, then we know

$$ $\displaystyle\mathbb{E}_{c\sim\rho,\bm{s}_{h}\sim d^{\mu_{i}\circ\pi^{t}_{-i}}_{h}(\cdot|c),a_{i,h}\sim\mu_{i,h}(c,s_{i,h}),_{-i,h}\sim\pi^{t}_{-i}(c,\bm{s}_{-i,h})}\left[r^{\star}_{i,h}(c,\bm{s}_{h},_{h})-\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]$ $\displaystyle\qquad=\sum_{k=0}^{K-1}\sum_{1\leq j_{1}<\cdots<j_{k}\leq N:j_{l}\neq i,\forall l\in[k]}\mathbb{E}_{c\sim\rho,z_{i}\sim d^{\mu_{i}}_{h}(\cdot|c),z_{j_{l}}\sim d^{\pi^{t}_{j_{l}}}_{h}(\cdot|c),\forall l}[\Delta^{i,h}_{j_{1},\cdots,j_{k}}(c,z_{i},z_{j_{1}},\cdots,z_{j_{k}})]$ $$

With similar arguments in the proof of [Theorem 2](#Thmtheorem2), from [Lemma 5](#Thmlemma5) we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho,z_{i}\sim d^{\mu_{i}}_{h}(\cdot|c),z_{j_{l}}\sim d^{\pi^{t}_{j_{l}}}_{h}(\cdot|c),\forall l}[\Delta^{i,h}_{j_{1},\cdots,j_{k}}(c,z_{i},z_{j_{1}},\cdots,z_{j_{k}})]$ $\displaystyle\leq$ $\displaystyle\sqrt{\mathbb{E}_{c\sim\rho,s_{i}\sim d^{\mu_{i}}_{h}(\cdot|c),a_{i}\sim\nu_{i,h}(\cdot|c,s_{i}),s_{j_{l}}\sim d^{\pi^{t}_{j_{l}}}_{h}(\cdot|c),a_{j_{l}}\sim\nu_{j_{l},h}(\cdot|c,s_{j_{l}})\forall l}\left[\left(\Delta^{i,h}_{j_{1},\cdots,j_{k}}(c,z_{i},z_{j_{1}},\cdots,z_{j_{k}})\right)^{2}\right]}$ $\displaystyle\quad\cdot\sqrt{\left(1+\chi^{2}\left(\rho\circ\left(d^{\mu_{i}}_{h}\times\prod_{l\in[K]}d^{\pi^{t}_{j_{l}}}_{h}\right)\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(d^{\mu_{i}}_{h}\times\prod_{l\in[K]}d^{\pi^{t}_{j_{l}}}_{h}\right)\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)\right)}$ $\displaystyle\leq$ $\displaystyle\sqrt{(C_{\mathsf{S}})^{k+1}2^{k}{\epsilon}_{\mathsf{R}}}$ $\displaystyle\quad\cdot\sqrt{\left(1+\chi^{2}\left(\rho\circ\left(d^{\mu_{i}}_{h}\times\prod_{l\in[K]}d^{\pi^{t}_{j_{l}}}_{h}\right)\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(d^{\mu_{i}}_{h}\times\prod_{l\in[K]}d^{\pi^{t}_{j_{l}}}_{h}\right)\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)\right)}.$ $$

On the other hand, from [Lemma 6](#Thmlemma6) we know

$$ $\displaystyle 1+\chi^{2}\left(\rho\circ\left(d^{\mu_{i}}_{h}\times\prod_{l\in[K]}d^{\pi^{t}_{j_{l}}}_{h}\right)\circ\left(\mu_{i}\times\prod_{l\in[k]}\pi^{t}_{j_{l}}\right),\rho\circ\left(d^{\mu_{i}}_{h}\times\prod_{l\in[K]}d^{\pi^{t}_{j_{l}}}_{h}\right)\circ\left(\nu_{i}\times\prod_{l\in[k]}\nu_{j_{l}}\right)\right)\lesssim C\left(\frac{TH}{\lambda}\right)^{k}.$ $$

This implies that

$$ $\displaystyle\mathbb{E}_{c\sim\rho,z_{i}\sim d^{\mu_{i}}_{h}(\cdot|c),z_{j_{l}}\sim d^{\pi^{t}_{j_{l}}}_{h}(\cdot|c),\forall l}[\Delta^{i,h}_{j_{1},\cdots,j_{k}}(c,z_{i},z_{j_{1}},\cdots,z_{j_{k}})]\lesssim\sqrt{C_{\mathsf{S}}^{k+1}C\left(\frac{2TH}{\lambda}\right)^{k}{\epsilon}_{\mathsf{R}}}$ $$

Therefore we have

$$ $\displaystyle(1)\lesssim TH\sqrt{CC_{\mathsf{S}}^{K}\left(\frac{2THN^{2}}{\lambda}\right)^{K-1}{\epsilon}_{\mathsf{R}}}.$ $$

Similarly, term (2) is bounded by

$$ $\displaystyle(2)\lesssim TH\sqrt{\left(\frac{C_{\mathsf{S}}TH}{\lambda}\right)^{K}(2N^{2})^{K-1}{\epsilon}_{\mathsf{R}}}.$ $$

For term (3), note that we have

$$ $\displaystyle(3)$ $\displaystyle=\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho,\bm{s}_{h}\sim d^{\mu_{i}\circ\pi^{t}_{-i}}_{h}(\cdot|c),a_{i,h}\sim\mu_{i,h}(\cdot|c,s_{i,h}),_{-i,h}\sim\pi^{t}_{-i}(\cdot|c,\bm{s}_{-i,h})}\left[\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]$ $\displaystyle\qquad\qquad\qquad-\mathbb{E}_{c\sim\rho,\bm{s}_{h}\sim\widehat{d}^{\mu_{i}\circ\pi^{t}_{-i}}_{h}(\cdot|c),a_{i,h}\sim\mu_{i,h}(\cdot|c,s_{i,h}),_{-i,h}\sim\pi^{t}_{-i}(\cdot|c,\bm{s}_{-i,h})}\left[\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]$ $\displaystyle\leq\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\left|d^{\mu_{i}\circ\pi^{t}_{-i}}_{h}(\bm{s},|c)-\widehat{d}^{\mu_{i}\circ\pi^{t}_{-i}}_{h}(\bm{s},|c)\right|\right]$ $$

At the same time, due to decoupled transition, we have the following lemma:

###### Lemma 9 .

For any policy product $\pi$, we have for all $h\in[H]$ that

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\left|d^{\pi}_{h}(\bm{s},|c)-\widehat{d}^{\pi}_{h}(\bm{s},|c)\right|\right]\leq\sum_{j=1}^{N}\mathbb{E}_{c\sim\rho}\left[\sum_{s_{j},a_{j}}\left|d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|$ $$

Thus, from [Lemma 9](#Thmlemma9), we only need to bound $\mathbb{E}_{c\sim\rho}\left[\sum_{s_{j},a_{j}}\left|d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|\right]$ for any agent $j$ and single-agent policy $\pi_{j}$. This is achieved in the following lemma:

###### Lemma 10 .

For any $j\in[N]$ and single-agent policy $\pi_{j}$, we have for all $h\in[H]$ that

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[\sum_{s_{j},a_{j}}\left|d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|\right]$ $\displaystyle\qquad\qquad\qquad\leq\sum_{h^{\prime}=1}^{h-1}\mathbb{E}_{c\sim\rho,(s_{j},a_{j})\sim d^{\pi_{j}}_{h^{\prime}}(\cdot|c)}\left[\left\|\widehat{P}_{j,h^{\prime}}(\cdot|c,s_{j},a_{j})-P^{\star}_{j,h^{\prime}}(\cdot|c,s_{j},a_{j})\right\|_{1}\right].$ $$

On the other hand, from the guarantee of MLE in the literature (Liu et al.,, ; Zhan et al.,, ; ) ([Lemma 14](#Thmlemma14)), we know with probability at least $1-\delta/2$ that for all $j\in[N],h\in[H]$

$$ $\displaystyle\mathbb{E}_{c\sim\rho,s_{j}\sim\sigma_{j,h}(\cdot|c),a_{j}\sim\nu_{j,h}(\cdot|c,s_{j})}\left[\left\|\widehat{P}_{j,h}(\cdot|c,s_{j},a_{j})-P^{\star}_{j,h}(\cdot|c,s_{j},a_{j})\right\|_{1}^{2}\right]\lesssim\frac{\log(HN|\mathcal{P}|/\delta)}{M}:={\epsilon}_{\mathsf{P}}.$ (17) $$

From [Lemma 5](#Thmlemma5), this implies that with probability at least $1-\delta/2$, we have for all $j\in[N],h\in[H],t\in[T],\mu_{i}\in{\Pi}_{i}(C)$ that

$$ $\displaystyle\mathbb{E}_{c\sim\rho,(s_{i},a_{i})\sim d^{\mu_{i}}_{h}(\cdot|c)}\left[\left\|\widehat{P}_{i,h}(\cdot|c,s_{i},a_{i})-P^{\star}_{i,h}(\cdot|c,s_{i},a_{i})\right\|_{1}\right]\lesssim\sqrt{C_{\mathsf{S}}C{\epsilon}_{\mathsf{P}}},$ (18) $\displaystyle\mathbb{E}_{c\sim\rho,(s_{j},a_{j})\sim d^{\pi^{t}_{j}}_{h}(\cdot|c)}\left[\left\|\widehat{P}_{j,h}(\cdot|c,s_{j},a_{j})-P^{\star}_{j,h}(\cdot|c,s_{j},a_{j})\right\|_{1}\right]\lesssim\sqrt{\frac{C_{\mathsf{S}}TH{\epsilon}_{\mathsf{P}}}{\lambda}}.$ $$

Therefore, we have

$$ $\displaystyle(3)\lesssim H^{2}T\sqrt{C_{\mathsf{S}}C{\epsilon}_{\mathsf{P}}}+H^{2}TN\sqrt{\frac{C_{\mathsf{S}}TH{\epsilon}_{\mathsf{P}}}{\lambda}}.$ $$

For term (4), following the same arguments for term (3), we have

$$ $\displaystyle(4)\lesssim H^{2}TN\sqrt{\frac{C_{\mathsf{S}}TH{\epsilon}_{\mathsf{P}}}{\lambda}}.$ $$

For term (5), we first need to show that the expected single-agent Q function $\widehat{Q}^{t}_{i,h}$ satisfies Bellman equation. In particular, let $\widehat{Q}^{\pi,\widehat{r}}:=\mathbb{E}_{(s_{j},a_{j)}\sim\widehat{d}^{\pi_{j}}_{h}(\cdot|c),\forall j\neq i}\left[\widehat{Q}^{\pi,\widehat{r}}_{i,h}(c,\bm{s},)\right]$ for any product policy $\pi$ and we have the following lemma:

###### Lemma 11 .

Given a joint policy $\pi_{-i}$ for agents except $i$, for all $i\in[N],h\in[H],c\in\mathcal{C},s_{i}\in\mathcal{S}_{i},a\in\mathcal{A}_{i}$ and policy $\mu_{i}$, we have

$$ $\displaystyle\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i}):=\mathbb{E}_{a_{i}\sim\mu_{i,h}(\cdot|c,s_{i})}\left[\widehat{Q}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i},a_{i})\right],$ $\displaystyle\widehat{Q}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i},a_{i})=\mathbb{E}_{(\bm{s}_{-i},_{-i})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\widehat{r}_{i,h}(c,\bm{s},)\right]+\mathbb{E}_{s^{\prime}_{i}\sim\widehat{P}_{i,h}(\cdot|c,s_{i},a_{i})}\left[\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h+1}(c,s^{\prime}_{i})\right].$ $$

[Lemma 11](#Thmlemma11) indeed implies that $\widehat{Q}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i},a_{i})$ is a valid Q function w.r.t. to the reward function $\mathbb{E}_{(\bm{s}_{-i},_{-i})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\widehat{r}_{i,h}(c,\bm{s},)\right]$ under transition model $\widehat{P}$ and thus we have the following performance difference lemma:

###### Lemma 12 .

Given a joint policy $\pi_{-i}$ for agents except $i$, for any policies $\mu_{i}$ and $\mu^{\prime}_{i}$, we have

$$ $\displaystyle\widehat{V}^{\mu^{\prime}_{i}\circ\pi_{-i},\widehat{r}}_{i,1}(c,s_{i,1})-\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,1}(c,s_{i,1})=\sum_{h=1}^{H}\mathbb{E}_{s_{i,h}\sim\widehat{d}^{\mu^{\prime}_{i}}_{h}(\cdot|c)}\left[\left\langle\widehat{Q}^{\mu_{i}\circ\pi_{-i},r}_{i,h}(c,s_{i,h},\cdot),\mu^{\prime}_{i,h}(\cdot|c,s_{i,h})-\mu_{i,h}(\cdot|c,s_{i,h})\right\rangle\right].$ $$

Now given [Lemma 12](#Thmlemma12), we have

$$ $\displaystyle(5)$ $\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{c\sim\rho}\left[\widehat{V}^{\mu_{i}\circ\pi^{t}_{-i},\widehat{r}}_{i,1}(c,s_{i,1})\right]-\mathbb{E}_{c\sim\rho}\left[\widehat{V}^{\pi^{t},\widehat{r}}_{i,1}(c,s_{i,1})\right]$ $\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{c\sim\rho,s_{i}\sim\widehat{d}^{\mu_{i}}_{h}(\cdot|c)}\left[\sum_{t=1}^{T}\left\langle\widehat{Q}^{t}_{i,h}(c,s_{i},\cdot),\mu_{i,h}(\cdot|c,s_{i})-\pi^{t}_{i,h}(\cdot|c,s_{i})\right\rangle\right]$ $\displaystyle\leq\underbrace{\sum_{h=1}^{H}\mathbb{E}_{c\sim\rho,s_{i}\sim d^{\mu_{i}}_{h}(\cdot|c)}\left[\sum_{t=1}^{T}\left\langle\widehat{Q}^{t}_{i,h}(c,s_{i},\cdot),\mu_{i,h}(\cdot|c,s_{i})-\pi^{t}_{i,h}(\cdot|c,s_{i})\right\rangle\right]}_{(6)}$ $\displaystyle\quad+\underbrace{TH\sum_{h=1}^{H}\mathbb{E}_{c\sim\rho}\left[\sum_{s_{i}}\left|\widehat{d}^{\mu_{i}}_{h}(s_{i}|c)-d^{\mu_{i}}_{h}(s_{i}|c)\right|\right]}_{(7)}$ $$

Apply [Lemma 7](#Thmlemma7) and since $\mu_{i}\in{\Pi}_{i}(C)$, we have

$$ $\displaystyle(6)\lesssim TH\lambda C+\frac{HC}{\eta}+\frac{\eta H^{3}T}{4}.$ $$

From [Lemma 10](#Thmlemma10) and [Eq. 18](#A5.E18),we have

$$ $\displaystyle(7)\lesssim TH^{3}\sqrt{C_{\mathsf{S}}C{\epsilon}_{\mathsf{P}}}.$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[V^{\mu_{i}\circ\widehat{\pi}_{-i},r^{\star}}_{i,1}(c,\bm{s}_{1})\right]-\mathbb{E}_{c\sim\rho}\left[V^{\widehat{\pi},r^{\star}}_{i,1}(c,\bm{s}_{1})\right]$ $\displaystyle\qquad\lesssim H\sqrt{C\left(\frac{C_{\mathsf{S}}TH}{\lambda}\right)^{K}(2N^{2})^{K-1}{\epsilon}_{\mathsf{R}}}+H\lambda C+\frac{HC}{T\eta}+\frac{\eta H^{3}}{4}+H^{3}\sqrt{C_{\mathsf{S}}C{\epsilon}_{\mathsf{P}}}+H^{2}N\sqrt{\frac{C_{\mathsf{S}}TH{\epsilon}_{\mathsf{P}}}{\lambda}}.$ $$

Let

$$ $\displaystyle T=C_{\mathsf{S}}^{-\frac{2K}{3K+2}}H^{\frac{4}{3K+2}}(2N^{2})^{-\frac{2K-2}{3K+2}}\epsilon_{\mathsf{RP}}^{-\frac{2}{3K+2}},\qquad\eta=C_{\mathsf{S}}^{\frac{K}{3K+2}}H^{-\frac{3K+4}{3K+2}}(2N^{2})^{\frac{K-1}{3K+2}}\epsilon_{\mathsf{RP}}^{\frac{1}{3K+2}},$ $\displaystyle\lambda=C_{\mathsf{S}}^{\frac{K}{3K+2}}H^{\frac{3K}{3K+2}}(2N^{2})^{\frac{K-1}{3K+2}}\epsilon_{\mathsf{RP}}^{\frac{1}{3K+2}},$ $$

where $\epsilon_{\mathsf{RP}}:=\frac{\log(NH|\mathcal{R}||\mathcal{P}|/\delta)}{M}$ and then we have for all $\mu_{i}\in{\Pi}_{i}(C)$ that

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[V^{\mu_{i}\circ\widehat{\pi}_{-i},r^{\star}}_{i,1}(c,\bm{s}_{1})\right]-\mathbb{E}_{c\sim\rho}\left[V^{\widehat{\pi},r^{\star}}_{i,1}(c,\bm{s}_{1})\right]\lesssim CC_{\mathsf{S}}^{\frac{K}{3K+2}}H^{\frac{6K+2}{3K+2}}(2N^{2})^{\frac{K-1}{3K+2}}\epsilon_{\mathsf{RP}}^{\frac{1}{3K+2}}.$ $$

This concludes our proof.

###### Lemma 9 .

###### Lemma 10 .

###### Lemma 11 .

###### Lemma 12 .

### E.1 Proof of Lemma 9

Note that given $c$, the distribution of $(s_{j},a_{j})$ is independent from each other due to the decoupled transition. Therefore we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\left|d^{\pi}_{h}(\bm{s},|c)-\widehat{d}^{\pi}_{h}(\bm{s},|c)\right|\right]=\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\left|\prod_{j\in[N]}d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\prod_{j\in[N]}\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|$ $$

Now for any $0\leq k\leq N-1$, consider the following difference:

$$ $\displaystyle I_{k}:=\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\left|\prod_{1\leq j\leq k}d^{\pi_{j}}_{h}(s_{j},a_{j}|c)\prod_{k+1\leq j\leq N}\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\prod_{1\leq j\leq k+1}d^{\pi_{j}}_{h}(s_{j},a_{j}|c)\prod_{k+2\leq j\leq N}\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|$ $$

Note that we have

$$ $\displaystyle I_{k}$ $\displaystyle=\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\prod_{1\leq j\leq k}d^{\pi_{j}}_{h}(s_{j},a_{j}|c)\prod_{k+2\leq j\leq N}\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\left|\widehat{d}^{\pi_{k+1}}_{h}(s_{k+1},a_{k+1}|c)-d^{\pi_{k+1}}_{h}(s_{k+1},a_{k+1}|c)\right|$ $\displaystyle=\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{k+1},a_{k+1}}\left|\widehat{d}^{\pi_{k+1}}_{h}(s_{k+1},a_{k+1}|c)-d^{\pi_{k+1}}_{h}(s_{k+1},a_{k+1}|c)\right|$ $\displaystyle\qquad\qquad\qquad\qquad\qquad\cdot\sum_{\bm{s}_{-(k+1)},_{-(k+1)}}\prod_{1\leq j\leq k}d^{\pi_{j}}_{h}(s_{j},a_{j}|c)\prod_{k+2\leq j\leq N}\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\Bigg{]}$ $\displaystyle=\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{k+1},a_{k+1}}\left|\widehat{d}^{\pi_{k+1}}_{h}(s_{k+1},a_{k+1}|c)-d^{\pi_{k+1}}_{h}(s_{k+1},a_{k+1}|c)\right|\Bigg{]}$ $$

Therefore we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[\sum_{\bm{s},}\left|d^{\pi}_{h}(\bm{s},|c)-\widehat{d}^{\pi}_{h}(\bm{s},|c)\right|\right]\leq\sum_{k=0}^{N-1}I_{k}=\sum_{j=1}^{N}\mathbb{E}_{c\sim\rho}\left[\sum_{s_{j},a_{j}}\left|d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|\right]$ $$

This concludes our proof.

### E.2 Proof of Lemma 10

Let $\delta_{h}$ denote $\mathbb{E}_{c\sim\rho}\left[\sum_{s_{j},a_{j}}\left|d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|\right]$. Then we know $\delta_{1}=0$. In addition, for any $1\leq h\leq H$, we have

$$ $\displaystyle\delta_{h}$ $\displaystyle=\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j}}\Bigg{|}\sum_{s^{\prime}_{j},a^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)P_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})$ $\displaystyle\qquad\qquad\qquad\qquad-\sum_{s^{\prime}_{j},a^{\prime}_{j}}\widehat{d}^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Bigg{|}\Bigg{]}$ $\displaystyle=\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j}}\Bigg{|}\Bigg{(}\sum_{s^{\prime}_{j},a^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)P_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})$ $\displaystyle\qquad\qquad\qquad\qquad-\sum_{s^{\prime}_{j},a^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Bigg{)}$ $\displaystyle\qquad\qquad\qquad\quad+\Bigg{(}\sum_{s^{\prime}_{j},a^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})$ $\displaystyle\qquad\qquad\qquad\qquad-\sum_{s^{\prime}_{j},a^{\prime}_{j}}\widehat{d}^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Bigg{)}\Bigg{|}\Bigg{]}$ $\displaystyle\leq\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j}}\Bigg{|}\sum_{s^{\prime}_{j},a^{\prime}_{j}}\Big{(}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)P_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})$ $\displaystyle\qquad\qquad\qquad\qquad\qquad-d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Big{)}\Bigg{|}\Bigg{]}$ $\displaystyle\qquad+\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j}}\Bigg{|}\sum_{s^{\prime}_{j},a^{\prime}_{j}}\Big{(}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})$ $\displaystyle\qquad\qquad\qquad\qquad\qquad-\widehat{d}^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Big{)}\Bigg{|}\Bigg{]}$ $\displaystyle\leq\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j},s^{\prime}_{j},a^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\pi_{j,h}(a_{j}|c,s_{j})\left|P_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})-\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\right|\Bigg{]}$ $\displaystyle\qquad+\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j},s^{\prime}_{j},a^{\prime}_{j}}\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Big{|}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)-\widehat{d}^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\Big{|}\Bigg{]}$ $\displaystyle=\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j},s^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\left|P_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})-\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\right|\sum_{a_{j}}\pi_{j,h}(a_{j}|c,s_{j})\Bigg{]}$ $\displaystyle\qquad+\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s^{\prime}_{j},a^{\prime}_{j}}\Big{|}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)-\widehat{d}^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\Big{|}\sum_{s_{j},a_{j}}\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Bigg{]}$ $\displaystyle=\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s_{j},a_{j},s^{\prime}_{j}}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\left|P_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})-\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\right|\sum_{a_{j}}\pi_{j,h}(a_{j}|c,s_{j})\Bigg{]}$ $\displaystyle\qquad+\mathbb{E}_{c\sim\rho}\Bigg{[}\sum_{s^{\prime}_{j},a^{\prime}_{j}}\Big{|}d^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)-\widehat{d}^{\pi_{j}}_{h-1}(s^{\prime}_{j},a^{\prime}_{j}|c)\Big{|}\sum_{s_{j},a_{j}}\widehat{P}_{j,h}(s_{j}|c,s^{\prime}_{j},a^{\prime}_{j})\pi_{j,h}(a_{j}|c,s_{j})\Bigg{]}$ $\displaystyle=\mathbb{E}_{c\sim\rho,(s_{j},a_{j})\sim d^{\pi_{j}}_{h-1}(\cdot|c)}\left[\left\|\widehat{P}_{j,h-1}(\cdot|c,s_{j},a_{j})-P^{\star}_{j,h-1}(\cdot|c,s_{j},a_{j})\right\|_{1}\right]+\delta_{h-1}.$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}_{c\sim\rho}\left[\sum_{s_{j},a_{j}}\left|d^{\pi_{j}}_{h}(s_{j},a_{j}|c)-\widehat{d}^{\pi_{j}}_{h}(s_{j},a_{j}|c)\right|\right]$ $\displaystyle\qquad\qquad\qquad\leq\sum_{h^{\prime}=1}^{h-1}\mathbb{E}_{c\sim\rho,(s_{j},a_{j})\sim d^{\pi_{j}}_{h^{\prime}}(\cdot|c)}\left[\left\|\widehat{P}_{j,h^{\prime}}(\cdot|c,s_{j},a_{j})-P^{\star}_{j,h^{\prime}}(\cdot|c,s_{j},a_{j})\right\|_{1}\right].$ $$

This concludes our proof.

### E.3 Proof of Lemma 11

First it can be observed that $\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i,h})=\mathbb{E}_{\bm{s}_{-i}\sim\widehat{d}^{\pi_{-i}}_{h}}\left[\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,\bm{s}_{h})\right]$. Note that we have

$$ $\displaystyle\widehat{Q}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i,h},a_{i,h})=\mathbb{E}_{(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\mathbb{E}_{\mu_{i}\circ\pi_{-i},\widehat{P}}\left[\sum_{h^{\prime}=h}^{H}\widehat{r}_{i,h^{\prime}}(c,\bm{s}_{h^{\prime}},_{h^{\prime}})\Big{|}c,\bm{s}_{h},_{h}\right]\right]$ $\displaystyle\qquad=\mathbb{E}_{(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]$ $\displaystyle\qquad\quad+\mathbb{E}_{(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\mathbb{E}_{\mu_{i}\circ\pi_{-i},\widehat{P}}\left[\sum_{h^{\prime}=h+1}^{H}\widehat{r}_{i,h}(c,\bm{s}_{h^{\prime}},_{h^{\prime}})\Big{|}c,\bm{s}_{h},_{h}\right]\right],$ $$

where we use $\mathbb{E}_{\pi,\widehat{P}}[\cdot]$ to denote the distribution of the trajectory when executing joint policy $\pi$ with transition model $\widehat{P}$.

On the other hand we know

$$ $\displaystyle\mathbb{E}_{\mu_{i}\circ\pi_{-i},\widehat{P}}\left[\sum_{h^{\prime}=h+1}^{H}\widehat{r}_{i,h}(c,\bm{s}_{h^{\prime}},_{h^{\prime}})\Big{|}c,\bm{s}_{h},_{h}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{s_{j,h+1}\sim\widehat{P}_{j,h}(\cdot|c,s_{j,h},a_{j,h}),\forall j}\left[\mathbb{E}_{\mu_{i}\circ\pi_{-i},\widehat{P}}\left[\sum_{h^{\prime}=h+1}^{H}\widehat{r}_{i,h}(c,\bm{s}_{h^{\prime}},_{h^{\prime}})\Big{|}c,\bm{s}_{h+1}\right]\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{s_{j,h+1}\sim\widehat{P}_{j,h}(\cdot|c,s_{j,h},a_{j,h}),\forall j}\left[\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h+1}(c,\bm{s}_{h+1})\right].$ $$

Therefore we know

$$ $\displaystyle\widehat{Q}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i,h},a_{i,h})$ $\displaystyle\qquad=\mathbb{E}_{(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]$ $\displaystyle\qquad\quad+\mathbb{E}_{s_{i,h+1}\sim\widehat{P}_{i,h}(\cdot|c,s_{i,h},a_{i,h}),(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c),\bm{s}_{j,h+1}\sim\widehat{P}_{j,h}(\cdot|c,s_{j,h},a_{j,h}),\forall j\neq i}\left[\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h+1}(c,\bm{s}_{h+1})\right]$ $\displaystyle\qquad=\mathbb{E}_{(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]+\mathbb{E}_{s_{i,h+1}\sim\widehat{P}_{i,h}(\cdot|c,s_{i,h},a_{i,h}),\bm{s}_{-i,h+1}\sim\widehat{d}^{\pi_{-i}}_{h+1}(\cdot|c)}\left[\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h+1}(c,\bm{s}_{h+1})\right]$ $\displaystyle\qquad=\mathbb{E}_{(\bm{s}_{-i,h},_{-i,h})\sim\widehat{d}^{\pi_{-i}}_{h}(\cdot|c)}\left[\widehat{r}_{i,h}(c,\bm{s}_{h},_{h})\right]+\mathbb{E}_{s_{i,h+1}\sim\widehat{P}_{i,h}(\cdot|c,s_{i,h},a_{i,h})}\left[\widehat{V}^{\mu_{i}\circ\pi_{-i},\widehat{r}}_{i,h}(c,s_{i,h+1})\right].$ $$

This concludes our proof.

### E.4 Proof of Lemma 12

Let $\widetilde{r}_{i,h}(c,s_{i},a_{i})$ denote $\mathbb{E}_{(\bm{s}_{-i},_{-i})\sim d^{\pi_{-i}}_{h}(\cdot|c)}\left[r_{i,h}(c,\bm{s},)\right]$. From [Lemma 11](#Thmlemma11), we have

$$ $\displaystyle V^{\mu^{\prime}_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})-V^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})=\mathbb{E}_{\mu^{\prime}_{i}}\left[\sum_{h=1}^{H}\widetilde{r}_{i,h}(c,s_{i,h},a_{i,h})\Big{|}c\right]-V^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})$ $\displaystyle=\mathbb{E}_{\mu^{\prime}_{i}}\left[\sum_{h=2}^{H}\widetilde{r}_{i,h}(c,s_{i,h},a_{i,h})\Big{|}c\right]+\mathbb{E}_{\mu^{\prime}_{i}}\left[\widetilde{r}_{i,1}(s_{i,1},a_{i,1})-V^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})\Big{|}c\right]$ $\displaystyle=\mathbb{E}_{\mu^{\prime}_{i}}\left[\sum_{h=2}^{H}\widetilde{r}_{i,h}(c,s_{i,h},a_{i,h})\Big{|}c\right]+\mathbb{E}_{\mu^{\prime}_{i}}\left[Q^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1},a_{i,1})-V^{\mu_{i}\circ\pi_{-i},r}_{i,2}(c,s_{i,2})-V^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})\Big{|}c\right]$ $\displaystyle=\mathbb{E}_{\mu^{\prime}_{i}}\left[\sum_{h=2}^{H}\widetilde{r}_{i,h}(c,s_{i,h},a_{i,h})\Big{|}c\right]-\mathbb{E}_{\mu^{\prime}_{i}}\left[V^{\mu_{i}\circ\pi_{-i},r}_{i,2}(c,s_{i,2})\right]$ $\displaystyle\quad+\mathbb{E}_{s_{i,1}\sim d^{\mu^{\prime}_{i}}_{1}(\cdot|c)}\left[\left\langle Q^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1},\cdot),\mu^{\prime}_{i,1}(\cdot|c,s_{i,1})-\mu_{i,1}(\cdot|c,s_{i,1})\right\rangle\right].$ $$

Here the first step is due to the definition of value function and the third step is due to [Lemma 11](#Thmlemma11). Now apply the above arguments recursively to $\mathbb{E}_{\mu^{\prime}_{i}}\left[\sum_{h=2}^{H}\widetilde{r}_{i,h}(c,s_{i,h},a_{i,h})\Big{|}c\right]-\mathbb{E}_{\mu^{\prime}_{i}}\left[V^{\mu_{i}\circ\pi_{-i},r}_{i,2}(c,s_{i,2})\right]$ and we have

$$ $\displaystyle V^{\mu^{\prime}_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})-V^{\mu_{i}\circ\pi_{-i},r}_{i,1}(c,s_{i,1})=\sum_{h=1}^{H}\mathbb{E}_{s_{i,h}\sim d^{\mu^{\prime}_{i}}_{h}(\cdot|c)}\left[\left\langle Q^{\mu_{i}\circ\pi_{-i},r}_{i,h}(c,s_{i,h},\cdot),\mu^{\prime}_{i,h}(\cdot|c,s_{i,h})-\mu_{i,h}(\cdot|c,s_{i,h})\right\rangle\right].$ $$

This concludes our proof.

## Appendix F Auxiliary Lemmas

###### Lemma 13 ( Song et al., ( 2022 ) ) .

Let $\{(x_{m},y_{m})\}_{m=1}^{M}$ be $M$ samples that are independently sampled from $x_{m}\sim p$ and $y_{m}\sim q(\cdot|x_{m}):=f^{\star}(x_{m})+\epsilon_{m}$ where $\epsilon_{m}$ is a random noise. Suppose that $y_{m}\in[0,1]$ for all $m\in[M]$ and we have access to a function class $\mathcal{G}:\mathcal{X}\to[0,1]$ which satisfies $f^{\star}\in\mathcal{G}$. Then if $\{\epsilon_{m}\}_{m=1}^{M}$ are independent and $\mathbb{E}[y_{m}|x_{m}]=f^{\star}(x_{m})$, we have with probability at least $1-\delta$ that

$$ $\displaystyle\mathbb{E}_{x\sim p}[(\widehat{f}(x)-f^{\star}(x))^{2}]\lesssim\frac{\log(|\mathcal{G}|/\delta)}{M},$ $$

where $\widehat{f}=\arg\min_{f\in\mathcal{G}}\sum_{m=1}^{M}(f(x_{m})-y_{m})^{2}$ is the LSR solution.

###### Lemma 14 ( Zhan et al., 2023b ) .

Let $\{(x_{m},y_{m})\}_{m=1}^{M}$ be $M$ samples that are i.i.d. sampled from $x_{m}\sim p$ and $y_{m}\sim q^{\star}(\cdot|x_{m})$. Suppose we have access to a probability model class $\mathcal{Q}$ which satisfies $q^{\star}\in\mathcal{Q}$. Then we have with probability at least $1-\delta$ that

$$ $\displaystyle\mathbb{E}_{x\sim p}\left[\left\|\widehat{q}(\cdot|x)-q^{\star}(\cdot|x)\right\|_{1}^{2}\right]\lesssim\frac{\log(|\mathcal{Q}|/\delta)}{M},$ $$

where $\widehat{q}=\arg\min_{q\in\mathcal{Q}}\sum_{m=1}^{M}\log q(y_{m}|x_{m})$ is the MLE solution.

###### Lemma 13 ( Song et al., ( 2022 ) ) .

###### Lemma 14 ( Zhan et al., 2023b ) .

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Can the authors explain the on-support and off-support components in Theorem 2? The off-support component depends on the gap between the best response policy of agent i over the entire probability simplex and the best response policy within a bounded $\chi^2$ divergence ball. This seems to be due to the $\chi^2$ divergence regularizer in the algorithm. It is not clear here whether such a $\chi^2$ divergence regularizer is a wise choice, though it may provide some convenience for the analysis, it limits the performance of the obtained policy.

2. The authors then define the C_sin, which can be infinity due to taking the max over $\mu_i$ if $\nu_i$ is zero for some action a_i and context c. This reviewer is curious whether the single policy concentration coefficient can be defined here, and the optimality gap can be derived as a function of the single policy concentration coefficient. (similar comment for assumption 4).

3. Can the authors provide some examples where the low interaction rank assumption can be satisfied? If given unknown environment, how to verify such a low interaction rank assumption?
soundness: 2
strengths: The notion of interaction rank is new and interesting. The authors provide statistical convergence and sample complexity guarantee under the assumption of low interaction rank for decentralized Markov game.
summary: This paper proposes a new notion of interaction rank to characterize the structure of a Markov game. If the true reward function and the learned reward function has a low interaction rank, then the authors designed decentralized \chi^2 regularized policy gradient approach and prove it converges to a CCE. The idea of low interaction rank is interesting. It may have potential in practice to help understand a wide range of multi-agent RL problems.
weaknesses: 1. The assumption MGs with decoupled transitions is very restrictive.

2. Assumption that the reward function and transition kernel belong to the function class is restrictive. Further assumption that the function classes are finite are not practical at all. 

3. The algorithm 1, line 3, estimating the transition kernel may not be as easy as it looks to be. Solving for the arg max in practice will be difficult. 

4. In the discussion on page 9, the authors claim that existing studies are not decentralized. However, it looks to this reviewer that the advantage in this paper may come from the assumption of decoupled transition.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: * By leveraging the low interaction rank assumption, the proposed algorithm achieves a sample complexity that scales exponentially
 with the interaction rank instead of number of agents. Meanwhile, there exists a constant as the coefficient of the sample complexity that hides behind the operator "$\lesssim$". How to understand the constant? Does it scales with the problem size?
* In extreme case where the problem has full interaction rank, does the proposed sample complexity orderly equal to the case that scales with number of agents? If not what makes the difference?
soundness: 3
strengths: * The paper leverages a structural assumption that shows the potential of using reward architectures with low interaction rank in offline MARL setting with an orderly better sample complexity, which seems to be a promising future direction.
* The paper is well-written and easy to follow.
summary: This paper introduces a structural assumption -- the interaction rank (IR), and establishes that functions with low interaction rank are more robust to distribution shift compared to general ones. The authors show that learning an approximate equilibrium in offline MARL can scale exponentially with the IR instead of exponentially with the number of agents. The proposed algorithm is a decentralized, no-regret learning algorithm that can be implemented in practical settings while utilizing standard RL algorithms.
weaknesses: * I don't see much discussion on related MARL or RL literature regarding interaction rank or similar assumptions. Discussion on literature of related topic would help determine the novelty of the idea and quantify the contribution.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: - The authors considered specifically the decentralised setting. I wonder if a better performance guarantee can be obtained if we assumed centralised setting.
soundness: 3
strengths: - The paper states a clear research question and draws clear conclusions that explicitly show low interaction rank games are easier to learn. While this result is not surprising, it is good that the paper explicitly derives it and quantifies this dependence.
-  The paper proposes a novel algorithm, which is decentralised and can learn from offline data.
summary: The paper first shows that if the underlying problem has low interaction rank then it is robust to distribution shifts coming from the mismatch between training and target distributions. Then the authors propose a decentralised algorithm for multi-agent offline reinforcement learning and explicitly derive a performance guarantee that depends on the interaction rank of the function K. The theoretical results are verified with experiments on a toy problem.
weaknesses: - The empirical evaluation is limited to one toy problem only, with no real-world experiments
- The paper could use a more explicit related work section. For example, currently when reading the paper it is not clear what is the state of the art when it comes to offline, decentralised, MARL and how does the proposed algorithm compares to it.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: * I wonder does similar property applies to the cooperative setting? I would like to hear the author's insight on the difference between these two settings (cooperative and competitive).
* In MARL, another widely-used property is the exponential decay of transition dynamics, e.g., [1,2]. From a intuitive perspective, is "low interaction rank" basically assumes a similar property, instead of on the transition dynamics, but on the reward structure? If they do share relevant ideas, I suggest the authors also discuss in the paper. Also, do you think the exponential decay property can be used to alleviate the current decoupled transition property in the paper? 

[1] Qu, G., Wierman, A., & Li, N. (2022). Scalable reinforcement learning for multiagent networked systems. Operations Research, 70(6), 3601-3628.

[2] Ying, D., Zhang, Y., Ding, Y., Koppel, A., & Lavaei, J. (2024). Scalable primal-dual actor-critic method for safe multi-agent rl with general utilities. Advances in Neural Information Processing Systems, 36.
soundness: 3
strengths: * The paper is the first that proposes a decentralized algorithm for offline general-sum MARL games and establishes its probable statistical guarantees.
* The integration of interaction rank to MARL provides an interesting yet also technically non-trivial angle. 
* The paper flow is good, and the author uses contextual games to serve as a toy example to help readers understand the idea of the paper. I like the proof sketch provided for the contextual game when K = 2.
summary: The paper studies learning a coarse correlated equilibrium in the offline multi-agent reinforcement learning. By imposing assumptions on the interaction rank of reward models, the paper establishes a sample complexity bound that grows exponentially with respect to the interaction rank, instead of the number of agents. Finally, the author use numerical experiments to examine the effectiveness of the proposed algorithm.
weaknesses: * The authors are encouraged to release the codes of the numerical experiments.
* Just a suggestion, maybe the author can consider using Markov Game or MG to replace RL in the title or in the abstract. I feel like people usually refers to the cooperative setting when saying MARL.
* The considered problems are contextual game, which does not have the notion of state, and transition-decoupled MG. I believe the author could directly brought up the transition decouple assumption in the problem formulation, since it is an assumption on the setting instead of technical assumptions.

Meta-review: All reviewers appreciate the novelty of interaction rank, and its tight statistical characterization in multi-agent RL. Accept.

Decision: Accept (Poster)