Literature
Display
← All papers

Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning

Antoine Bergerault · Volkan Cevher · Negar Mehr

· ICLR 2026 ↗

Robotics13 min text · CondensedOriginal paper ↗
Contents

Overview

This edition covers the ICLR 2026 paper, arXiv v1 dated 24 February 2026, including all six appendices. Antoine Bergerault completed the work while visiting UC Berkeley as an EPFL master’s student and is now at the University of Zurich. The original formal statements and equations are retained alongside concise explanations; notation and proof qualifications are identified where they affect interpretation.

At a glance

Matching a Nash expert’s demonstrated behavior need not yield a policy robust to another player’s strategic deviation. State-only matching can fail despite full state coverage; even state–action matching can fail when demonstrations miss states reachable after a deviation.

The paper states a PPAD-hardness result for a tight best-case exploitability bound, then derives upper bounds under strategic dominance or a stronger best-response sensitivity condition. A small regularized tag game illustrates the latter. These are conditional theoretical results, not an offline learning algorithm or broad empirical guarantee.

1 Introduction

ValueGap compares each player’s return with the expert’s return; NashGap measures the largest gain available from a unilateral deviation. Good joint imitation can satisfy the first criterion while remaining exploitable under the second.

A consistent bound vanishes with imitation error, and a tractable bound is computable efficiently from its assumptions. Exact matching is first analyzed, then approximate matching and game-dependent sensitivity. Zero Nash gap means a Nash equilibrium, which may be mixed; the introduction’s reference to a pure equilibrium is stronger than its definitions warrant.

2 Previous work

The background connects single-agent imitation guarantees with multi-agent strategic failures and prior coverage/concentrability assumptions.

Single-agent Imitation Learning.

Behavioral cloning fits expert actions, inverse reinforcement learning fits rewards, and GAIL matches occupancy measures adversarially. Single-agent analyses bound return loss from imitation error; they do not directly measure how another strategic player can exploit a learned policy.

Multi-agent Imitation Learning.

Multi-agent extensions support driving, crowds and robot interaction, but reward ambiguity and strategic deviations complicate their interpretation. Independent cloning produces product policies; matching jointly generated demonstrations alone does not certify Nash behavior.

Theoretical Barriers for MA-IL.

Tang et al. distinguish value from regret; Freihaut et al. provide bounds involving a deviation-related concentrability coefficient. Such coefficients may be unbounded or hard to compute. This paper instead seeks conditions on support and best-response changes.

3 Preliminaries

The model uses discounted Markov games, independent stochastic policies and normalized occupancy measures. The exact definitions of equilibrium, value loss, exploitability and imitation error are preserved below.

3.1 Markov Games

n players act simultaneously with product policy π₁×⋯×πₙ, rewards in [−1,1], initial distribution ν₀ and discount γ<1. State occupancy is the normalized discounted visitation distribution; state–action occupancy multiplies it by the joint policy.

The displayed state-value formula uses occupancy defined from ν₀, so its right-hand side does not depend on the displayed state s. Read it as the ν₀-averaged value unless occupancy is reinitialized at s; the printed formula is preserved unchanged.

Equations
μπ​(s)≔(1−γ)​∑t=0∞γt​ℙ​(st=s),ρπ​(s,a)≔μπ​(s)​π​(a|s),\mu_{\pi}(s)\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s),\hskip 50.00008pt\rho_{\pi}(s,a)\coloneqq\mu_{\pi}(s)\pi(a|s),
Viπ​(s)=11−γ⋅𝔼(s,a)∼ρπ​[ri​(s,a)]∀i∈[n],V_{i}^{\pi}(s)=\frac{1}{1-\gamma}\cdot\mathbb{E}_{(s,a)\sim\rho_{\pi}}[r_{i}(s,a)]\quad\forall i\in[n],

G=(𝒮,𝒜,P,{ri}i=1n,ν0,γ)G=(\mathcal{S},\mathcal{A},P,\{r_{i}\}_{i=1}^{n},\nu_{0},\gamma)

𝒜=𝒜1×⋯×𝒜n\mathcal{A}=\mathcal{A}_{1}\times\dots\times\mathcal{A}_{n}

Π=Π1×⋯×Πn\Pi=\Pi_{1}\times\dots\times\Pi_{n}

Viπ​(ν)=𝔼s∼ν​[Viπ​(s)]V_{i}^{\pi}(\nu)=\mathbb{E}_{s\sim\nu}[V_{i}^{\pi}(s)]

P:𝒮×𝒜→Δ𝒮P:\mathcal{S}\times\mathcal{A}\to\Delta_{\mathcal{S}}

πi:𝒮→Δ𝒜i\pi_{i}:\mathcal{S}\to\Delta_{\mathcal{A}_{i}}

π≔π1×⋯×πn\pi\coloneqq\pi_{1}\times\dots\times\pi_{n}

ri:𝒮×𝒜→[−1,1]r_{i}:\mathcal{S}\times\mathcal{A}\to[-1,1]

3.2 Measuring optimality in games

A best response maximizes a player’s discounted return against fixed opponents. A Nash equilibrium is a product policy in which every component is a best response. Policies may be stochastic; independent does not mean deterministic, and a correlated joint policy is outside this definition.

Equations
Definition 1 (Best-response mapping).

For an agent i∈[n]i\in[n], the best-response mapping to π−i\pi_{-i} is defined as

BRi⁡(π−i)≔arg⁡maxπi′​Viπi′,π−i​(ν0).\operatorname{BR}_{i}(\pi_{-i})\coloneqq\arg\max_{\pi_{i}^{\prime}}V^{\pi^{\prime}_{i},\pi_{-i}}_{i}(\nu_{0}).
Definition 2 (Nash equilibrium).

A policy π\pi is a Nash equilibrium of the game if π\pi is a product policy and each individual policy is a best-response to the other policies, i.e.

πi∈BRi⁡(π−i)∀i∈[n].\pi_{i}\in\operatorname{BR}_{i}(\pi_{-i})\quad\forall i\in[n].

3.3 Offline Imitation learning

Offline data consist of expert-equilibrium trajectories, without further environment access. NashGap is the maximum unilateral improvement, while ValueGap is the largest expert-minus-learner return difference. Rewards imply the trivial exploitability bound 2/(1−γ).

BC error is the maximum per-player L1 policy error averaged under expert state occupancy. State and state–action errors are L1 distances between true occupancy measures. These are population quantities; an empirical training loss does not certify them without additional estimation/generalization arguments. Known value-loss bounds need not transfer to NashGap.

Equations 1–2
Definition 3 (Value gap).

Given an expert policy πE\pi^{E} of GG, the Value gap of a policy π\pi is:

ValueGap⁡(π)≔maxi⁡(ViπE​(ν0)−Viπ​(ν0)).\operatorname{ValueGap(\pi)}\coloneqq\max_{i}\left(V^{\pi^{E}}_{i}(\nu_{0})-V^{\pi}_{i}(\nu_{0})\right).
Definition 4 (Nash gap, see Ramponi et al. (2023)).

We define the Nash (imitation) gap of a product policy π\pi of the game GG as

NashGap⁡(π)≔maxi⁡(Viπi∗,π−i​(ν0)−Viπ​(ν0))\operatorname{NashGap(\pi)}\coloneqq\max_{i}\left(V^{\pi^{*}_{i},\pi_{-i}}_{i}(\nu_{0})-V^{\pi}_{i}(\nu_{0})\right) (1)

with any πi∗∈BRi⁡(π−i)\pi^{*}_{i}\in\operatorname{BR}_{i}(\pi_{-i}).

ϵBC≔maxi𝔼s∼μπE[‖πi(⋅|s)−πiE(⋅|s)‖1],\epsilon_{\text{BC}}\coloneqq\max_{i}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\left\lVert\pi_{i}(\cdot|s)-\pi^{E}_{i}(\cdot|s)\right\rVert_{1}\right], (2)
ϵμ≔∥μπ−μπE∥1,andϵρ≔∥ρπ−ρπE∥1,\epsilon_{\mu}\coloneqq\lVert\mu_{\pi}-\mu_{\pi^{E}}\rVert_{1},\qquad\text{and}\qquad\epsilon_{\rho}\coloneqq\lVert\rho_{\pi}-\rho_{\pi^{E}}\rVert_{1},

Viπi,π−iE​(ν0)−ViπE​(ν0)≤ϵV^{\pi_{i},\pi^{E}_{-i}}_{i}(\nu_{0})-V^{\pi^{E}}_{i}(\nu_{0})\leq\epsilon

ValueGap⁡(π)≤n​ϵBC/(1−γ)2\operatorname{ValueGap(\pi)}\leq n\epsilon_{\text{BC}}/(1-\gamma)^{2}

ValueGap⁡(π)≤ϵρ/(1−γ)\operatorname{ValueGap}(\pi)\leq\epsilon_{\rho}/(1-\gamma)

|τk|∼Geometric⁡(1−γ)|\tau_{k}|\sim\operatorname{Geometric}(1-\gamma)

4 Impossibility results for exact measure matching

Exact state–action matching identifies the expert only where expert occupancy is positive. Full-state support closes that gap; removing support coverage or discarding action information permits horizon-sized exploitability. The counterexamples establish failure in general games, not failure of every incomplete-coverage task.

Equation

𝒮π+={s:μπ​(s)>0}\mathcal{S}^{+}_{\pi}=\{s:\mu_{\pi}(s)>0\}

𝒮π−={s:μπ​(s)=0}\mathcal{S}^{-}_{\pi}=\{s:\mu_{\pi}(s)=0\}

4.1 Sufficiency of state-action matching under full-state support

Summing equal state–action measures over actions gives equal state occupancies. Dividing by a positive occupancy then recovers the same action distribution at that state. With full support, the entire policy equals the expert and therefore has zero Nash gap.

This is an exact population statement. Full support alone supplies neither a useful finite-sample guarantee nor a lower bound on how often rare states appear.

Equations
Theorem 1.

Let π,π′∈Π\pi,\pi^{\prime}\in\Pi be such that ρπ=ρπ′\rho_{\pi}=\rho_{\pi^{\prime}}. Then, 𝒮π+=𝒮π′+\mathcal{S}^{+}_{\pi}=\mathcal{S}^{+}_{\pi^{\prime}} and π(⋅|s)=π′(⋅|s)\pi(\cdot|s)=\pi^{\prime}(\cdot|s) for every s∈𝒮π+s\in\mathcal{S}^{+}_{\pi}.

Corollary 1.

Let πE,π∈Π\pi^{E},\pi\in\Pi be such that 𝒮πE+=𝒮\mathcal{S}^{+}_{\pi^{E}}=\mathcal{S} and ρπE=ρπ\rho_{\pi^{E}}=\rho_{\pi}; then, NashGap⁡(π)=0\operatorname{NashGap}(\pi)=0.

4.2 Insufficiency of state-only matching with full-state support

The three-state cooperative example uses a uniform initial distribution, so every state has positive occupancy. The expert repeatedly takes the rewarding cycle, while another joint policy self-loops with reward −1 and the same uniform state occupancy.

One player can restore the expert cycle by deviating, gaining 5/[3(1−γ)]. Thus matching visited-state frequencies loses strategically important action information, even when coverage is complete. Both transition and reward diagrams remain.

Equation
Lemma 1.

There exists a game and a corresponding expert policy πE\pi^{E} such that 𝒮πE+=𝒮\mathcal{S}^{+}_{\pi^{E}}=\mathcal{S}. Moreover, there exists a policy π\pi such that μπE=μπ\mu_{\pi^{E}}=\mu_{\pi} and NashGap⁡(π)≥Ω⁡(1/(1−γ))\operatorname{NashGap}(\pi)\geq\Omega\left(1/(1-\gamma)\right).

Complete original S4.F1.sf1, including all labels and relationships.
(a) Description of the game transition dynamics. Note that a tuple (ai,aj)(a_{i},a_{j}) corresponds to player 1 playing aia_{i} and player 2 playing aja_{j}. Arrows represent deterministic transitions from a state to another.
Diagram mathematical labels

s0s_{0}

s1s_{1}

s2s_{2}

(a1,a1)(a_{1},a_{1})

(a1,a1)(a_{1},a_{1})

(a1,a1)(a_{1},a_{1})

Complete original S4.F1.sf2, including all labels and relationships.
(b) Description of the reward function. The number on each arrow is the reward associated with the corresponding transition. The rewards are the same for both players.
Diagram mathematical labels

s0s_{0}

s1s_{1}

s2s_{2}

1/31/3

−1-1

2/32/3

−1-1

−1-1

11

Figure 1: Cooperative two-player game GG: the transitions and rewards are described by the left and right sub-figures, respectively. In this game, there exists a Nash equilibrium πE\pi^{E} with full-state support and a policy π\pi such that μπE=μπ\mu_{\pi^{E}}=\mu_{\pi} with a Nash gap linear in the effective horizon 1/(1−γ)1/(1-\gamma).
Equations
NashGap⁡(π)≥V2πE​(νU)−V2π​(νU)=5/31−γ≥Ω⁡(11−γ).\operatorname{NashGap}(\pi)\geq V_{2}^{\pi^{E}}(\nu_{U})-V_{2}^{\pi}(\nu_{U})=\frac{5/3}{1-\gamma}\geq\Omega\left(\frac{1}{1-\gamma}\right).

𝒜1=𝒜2={a1,a2}\mathcal{A}_{1}=\mathcal{A}_{2}=\{a_{1},a_{2}\}

𝒮={s0,s1,s2}\mathcal{S}=\{s_{0},s_{1},s_{2}\}

πE​((a1,a1)|s)=1\pi^{E}((a_{1},a_{1})|s)=1

V2π​(νU)=−11−γV_{2}^{\pi}(\nu_{U})=-\frac{1}{1-\gamma}

V2πE​(νU)=2/31−γV_{2}^{\pi^{E}}(\nu_{U})=\frac{2/3}{1-\gamma}

μπ′​(s)≥(1−γ)​νU​(s)>0\mu_{\pi^{\prime}}(s)\geq(1-\gamma)\nu_{U}(s)>0

4.3 Insufficiency of state-action measure matching with unvisited states

An imitation policy can agree with the expert on every observed state–action pair yet behave differently at an unvisited state. A unilateral deviation can reach that state and exploit the difference. Theorem 2, adapted from Tang et al., gives an order-1/(1−γ) gap; Appendix B.3 supplies the explicit construction.

Equation
Theorem 2.

(Adapted from Tang et al. (2024, Theorem 4.3)) There exists a Markov Game with expert policy πE\pi^{E} and a learned policy π\pi such that even if ρπE=ρπ\rho_{\pi^{E}}=\rho_{\pi}, the Nash gap scales linearly with the discounted horizon; i.e., NashGap⁡(π)≥Ω⁡(1/(1−γ))\operatorname{NashGap}(\pi)\geq\Omega\left(1/(1-\gamma)\right).

Complete original S4.F2.fig1, including all labels and relationships.
Figure 2: Transitions of a two-player Markov Game. The unique initial state is s1s_{1}. The rest of the chain (⋯\cdots) and reward functions can be designed to induce linear Nash gap for state-action matching.

We can design reward functions for the transitions of Figure 2 such that the expert would always take the solid arrows.

The dataset missing information about πE(⋅|s2′)\pi^{E}(\cdot|s^{\prime}_{2}), a best-response can lead to states s2′s^{\prime}_{2} then sexps_{\text{exp}}. This last state sexps_{\text{exp}} can be designed to incur high rewards for one player, while the expert region SπE+S^{+}_{\pi^{E}} incurs linear less.

Diagram mathematical labels

s1s_{1}

s2s_{2}

…\dots

s2′s^{\prime}_{2}

sexps_{\text{exp}}

5 On the Infeasibility of Tractable Lower Bounds for Exploitability

The tight lower bound minimizes NashGap over both expert equilibria and learned policies at exactly a prescribed state–action distance. It is a best-case quantity over a constrained family, not the exploitability of one supplied policy or a worst-case learning guarantee.

Theorem 3 states that computing this quantity is PPAD-hard even for known bimatrix games, with a Markov-game corollary. This does not forbid loose bounds or special tractable games, nor does PPAD-hardness prove that no polynomial algorithm can exist.

The reduction is retained in full mathematical form. Its support-recovery argument has unresolved details: the displayed linear programs omit comparisons against actions outside the supplied support, and the approximate-support argument does not specify the required approximation regime. These limit what can be inferred directly from the printed proof.

Equations
Definition 5 (Tight Nash gap lower bound).

Let GG be a Markov Game and let ΠE\Pi^{E} the set of Nash equilibria of GG. We define the tight Nash gap lower bound for GG with occupancy matching error ϵρ\epsilon_{\rho} as

mρ​(G,ϵρ)=minπE∈ΠE⁡minπ∈ℳϵρ​(πE)​NashGap⁡(π),m_{\rho}(G,\epsilon_{\rho})=\min_{\pi^{E}\in\Pi^{E}}\min_{\pi\in\mathcal{M}_{\epsilon_{\rho}}(\pi^{E})}\operatorname{NashGap}(\pi),

where ℳϵρ​(πE)={π∈Π:‖ρπ−ρπE‖1=ϵρ}\mathcal{M}_{\epsilon_{\rho}}(\pi^{E})=\left\{\pi\in\Pi:\left\lVert\rho_{\pi}-\rho_{\pi^{E}}\right\rVert_{1}=\epsilon_{\rho}\right\}.

Theorem 3.

The problem of computing mρ​(Gbi,ϵρ)m_{\rho}(G_{\text{bi}},\epsilon_{\rho}) given an arbitrary bimatrix game GbiG_{\text{bi}} and an arbitrary ϵρ∈ℝ+\epsilon_{\rho}\in\mathbb{R_{+}} is PPAD-hard55 5 See Appendix A for more formal details on the PPAD complexity class..

Corollary 2.

The problem of computing mρ​(G,ϵρ)m_{\rho}(G,\epsilon_{\rho}) given an arbitrary Markov game GG and an arbitrary ϵρ∈ℝ+\epsilon_{\rho}\in\mathbb{R_{+}} is PPAD-hard.

6 Tractable and Consistent Exploitability Upper Bounds from Best-Response Continuity

The positive results separate ordinary imitation error from how much optimal responses can change when opponents depart from equilibrium. The resulting upper bound is useful only when that game-dependent sensitivity can itself be controlled and estimated.

6.1 Characterization of Markov Games via Best-Response delta-continuity

Definition 6 bounds the distance from the expert to every best response after a small change in the opponents’ joint policy, measured on expert-visited states. This is stronger than continuity of one selected response: ties can already make the maximum large.

A long chain makes a strategically decisive state rare in discounted occupancy, so a small BC error can switch a best response across the visited region. This defeats any uniform nontrivial δ over the broad class considered. The example’s additional claim that zero state-only error is equivalent to zero BC error is not justified: player-2 actions affect rewards while leaving its state transitions unchanged.

Equations
Definition 6 (δ\delta-continuity of the best-response correspondence).

For a given game GG, the best-response mapping is said to be δ\delta-continuous at equilibrium πE\pi^{E} for some δ:ℝ+→[0,2]\delta:\mathbb{R}^{+}\to[0,2] if for all i∈[n]i\in[n], and ϵ>0\epsilon>0, we have:

𝔼s∼μπE[‖π−i(⋅|s)−π−iE(⋅|s)‖1]≤ϵ⟹maxπi∗∈BRi⁡(π−i)𝔼s∼μπE[∥πi∗(⋅|s)−πiE(⋅|s)∥1]≤δ(ϵ).\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\left\lVert\pi_{-i}(\cdot|s)-\pi^{E}_{-i}(\cdot|s)\right\rVert_{1}\right]\leq\epsilon\implies\max_{\pi^{*}_{i}\in\operatorname{BR}_{i}(\pi_{-i})}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\lVert\pi_{i}^{*}(\cdot|s)-\pi_{i}^{E}(\cdot|s)\rVert_{1}\right]\leq\delta(\epsilon).
Definition 7 (δ\delta-continuity of a class of games).

A class 𝒞\mathcal{C} of Markov Games is δ\delta-continuous if every game G∈𝒞G\in\mathcal{C} is δ\delta-continuous at all its Nash equilibria.

Lemma 2.

Let 𝒞\mathcal{C} be the class of games with consistent bounds. This class is δ\delta-continuous only for trivial δ\delta such that δ⁡(ϵ)=2\delta(\epsilon)=2 for all ϵ>0\epsilon>0.

Complete original S6.F3, including all labels and relationships.
Figure 3: Deterministic transition dynamics of a two-player game GG, with states s0s_{0}, sexps_{\text{exp}} and sub-Markov chain MkM_{k}. Player 1 has action space 𝒜1={a1r,a2r}\mathcal{A}_{1}=\{a^{r}_{1},a^{r}_{2}\} and player 2 has action space 𝒜2={a1c,a2c}\mathcal{A}_{2}=\{a^{c}_{1},a^{c}_{2}\}.
Diagram mathematical labels

s0s_{0}

MkM_{k}

sexps_{\text{exp}}

a1=a1ra_{1}=a^{r}_{1}

a1=a2ra_{1}=a^{r}_{2}

Equations
r1​(⋅,a1c,sexp)=1,r2​(⋅,a2c,sexp)=1,r1​(⋅,a2c,sexp)=−1,r_{1}(\cdot,a^{c}_{1},s_{\text{exp}})=1,\qquad r_{2}(\cdot,a^{c}_{2},s_{\text{exp}})=1,\qquad r_{1}(\cdot,a^{c}_{2},s_{\text{exp}})=-1,

k=⌈log⁡(ϵ2​(1−γ))log⁡(γ)⌉k=\left\lceil\frac{\log(\frac{\epsilon}{2}(1-\gamma))}{\log(\gamma)}\right\rceil

πE​((a1r,a2c)|s)=1\pi^{E}((a^{r}_{1},a^{c}_{2})|s)=1

μπE​(sexp)≤ϵ/2\mu_{\pi^{E}}(s_{\text{exp}})\leq\epsilon/2

π⁡((a1,a2)|s)=πE​((a1,a2)|s)\pi((a_{1},a_{2})|s)=\pi^{E}((a_{1},a_{2})|s)

π⁡((a1r,a1c)|sexp)=1\pi((a^{r}_{1},a^{c}_{1})|s_{\text{exp}})=1

π1∗​(a2r|s)=1\pi^{*}_{1}(a^{r}_{2}|s)=1

𝔼s∼μπE[‖π1∗(⋅|s)−π1E(⋅|s)‖1]=2\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\left\lVert\pi^{*}_{1}(\cdot|s)-\pi^{E}_{1}(\cdot|s)\right\rVert_{1}\right]=2

ϵBC=0⇔ϵμ=0⇔ϵρ=0\epsilon_{\text{BC}}=0\Leftrightarrow\epsilon_{\mu}=0\Leftrightarrow\epsilon_{\rho}=0

6.2 Provable convergence under strategic dominance

At a weak dominant-strategy equilibrium, each expert component remains a best response against any opponents. Adding/subtracting the expert value and bounding two policy differences gives NashGap ≤2nϵBC/(1−γ)²; the appendix obtains the slightly sharper coefficient 2n−1. The corollary inverts this bound to select a sufficient BC tolerance.

Weak dominance permits other tied best responses far from the expert. It therefore suffices for this value argument but does not imply δ=0 under Definition 6’s maximum over all best responses, despite the source’s stated equivalence.

Equations 3
Definition 8 (Dominant Strategy Equilibrium (DSE)).

A policy πE\pi^{E} is a (weak) dominant strategy equilibrium if for every player ii, πiE\pi^{E}_{i} is a weak dominant strategy, i.e.:

ViπiE,π−i​(ν0)≥Viπi,π−i​(ν0)∀π∈Π.V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})\geq V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\quad\forall\pi\in\Pi.
Lemma 3.

Suppose πE\pi^{E} is a (weak) Dominant Strategy Equilibrium. Then, any learned policy π\pi with BC error ϵBC\epsilon_{\text{BC}} satisfies NashGap⁡(π)≤2​n​ϵBC/(1−γ)2\operatorname{NashGap}(\pi)\leq 2n\epsilon_{\text{BC}}/(1-\gamma)^{2}.

NashGap⁡(π)=maxi⁡[ViπiE,π−i​(ν0)−Viπi,π−i​(ν0)].\operatorname{NashGap}(\pi)=\max_{i}\left[V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]. (3)
NashGap(π)≤1(1−γ)2⋅maxi𝔼s∼μπE[‖π−i(⋅|s)−π−iE(⋅|s)‖1+‖π(⋅|s)−πE(⋅|s)‖1].\operatorname{NashGap}(\pi)\leq\frac{1}{(1-\gamma)^{2}}\cdot\max_{i}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\left\lVert\pi_{-i}(\cdot|s)-\pi^{E}_{-i}(\cdot|s)\right\rVert_{1}+\left\lVert\pi(\cdot|s)-\pi^{E}(\cdot|s)\right\rVert_{1}\right].
Corollary 3.

Suppose πE\pi^{E} is a (weak) Dominant Strategy Equilibrium; then, the recovered behavioral cloning policy π\pi is an ϵ\epsilon-Nash equilibrium if ϵBC≤ϵ​(1−γ)22​n\epsilon_{\text{BC}}\leq\frac{\epsilon(1-\gamma)^{2}}{2n}.

6.3 Relaxing the dominance assumption

Lemma 4 prints NashGap ≤[2nϵBC+δ(ϵBC)]/(1−γ)². Its proof adds the distance between the new best response and the expert to the ordinary imitation terms.

For more than two players, Definition 6 measures the opponents’ joint-policy error, whereas ϵBC is per player. The product-distribution bound gives joint error at most (n−1)ϵBC. Substituting δ(ϵBC) therefore needs an additional interpretation or stronger assumption; the source does not supply it. The numerical experiments are two-player.

Equation
Lemma 4.

Suppose the equilibrium expert is πE\pi^{E} and the game is δ\delta-continuous at πE\pi^{E}. Then, NashGap⁡(π)≤2​n​ϵBC+δ⁡(ϵBC)(1−γ)2\operatorname{NashGap}(\pi)\leq\frac{2n\epsilon_{\text{BC}}+\delta(\epsilon_{\text{BC}})}{(1-\gamma)^{2}}.

Properties of the bound.

An efficiently computable valid δ makes the displayed bound computable. A bound that vanishes as error tends to zero requires δ to tend to zero there, not merely an isolated declaration δ(0)=0. Computing a valid δ for an arbitrary game is not solved by expressing the bound in terms of it.

On the sensitivity of game equilibria.

Best-response sensitivity can remain informative where deviation occupancy has poor overlap with demonstrations. Conversely, the trivial δ=2 makes the proposed bound looser than the basic reward-range bound.

Entropy regularization may smooth responses, and risk aversion is proposed as another direction. These modifications change the optimization/game being studied. The paper does not prove that increasing regularization always reduces the unregularized game’s exploitability.

7 Conclusion

The practical message is to evaluate strategic robustness separately from imitation fit. Coverage, unilateral deviations and response stability determine whether an imitation error is meaningful for equilibrium learning. Reachability assumptions, stronger distribution control and demonstrations of off-equilibrium behavior are proposed future directions.

Acknowledgments

Support came from NSF grants ECCS-2438314 and CCF-2423134, Army Research Laboratory grant W911NF-26-1-0002 and EPFL.

Appendix A Additional background

The background appendix defines the complexity class used in the hardness claim and explains the occupancy-matching view of adversarial imitation.

A.1 PPAD complexity class

PPAD is defined through polynomial reduction to End-of-the-Line: from one source in an implicitly represented directed graph with at most one predecessor/successor per vertex, find another source or a sink. The parity argument guarantees a solution, placing these search problems within TFNP.

General Nash computation is the motivating example. PPAD-hard is a conditional computational barrier, not an unconditional impossibility result. The original problem definition and references are retained.

Equation
Definition 9 (PPAD class).

A search problem Π\Pi belongs to the complexity class PPAD (Polynomial Parity Arguments on Directed graphs) if and only if it is polynomial-time reducible to the End-of-the-Line problem defined as follows:

End-of-the-Line Problem

Input:

  • •

    A directed graph G=(V,E)G=(V,E) implicitly represented by two polynomial-time computation mutually inverse functions PP and SS:

    • –

      P:V→VP:V\to V maps every vertex v∈Vv\in V to its unique predecessor, or itself.

    • –

      S:V→VS:V\to V maps every vertex v∈Vv\in V to its unique successor, or itself.

  • •

    A source vertex s∈Vs\in V such that P⁡(s)=sP(s)=s and S⁡(s)≠sS(s)\neq s.

Output: Either a sink vertex or another source vertex.

A.2 GAIL and occupancy-measure matching

GAIL combines cost inference and entropy-regularized control into a discriminator/policy minimax objective. With the stated regularizer and unrestricted cost class, it corresponds to Jensen–Shannon state–action occupancy matching plus an entropy term.

This connection explains the matching errors analyzed in the paper. It does not turn occupancy agreement into a strategic guarantee, and the occupancy objective should not be conflated with supervised BC.

Equations
IRLψ⁡(πE)=arg⁡maxc∈𝒞−ψ⁡(c)+(minπ∈Π−H⁡(π)+𝔼π​[c⁡(s,a)])−𝔼πE​[c⁡(s,a)]\operatorname{IRL}_{\psi}(\pi^{E})=\arg\max_{c\in\mathcal{C}}-\psi(c)+\left(\min_{\pi\in\Pi}-H(\pi)+\mathbb{E}_{\pi}[c(s,a)]\right)-\mathbb{E}_{\pi^{E}}[c(s,a)]
RL⁡(c)=arg⁡minπ∈Π−H⁡(π)+𝔼π​[c⁡(s,a)],\operatorname{RL}(c)=\arg\min_{\pi\in\Pi}-H(\pi)+\mathbb{E}_{\pi}[c(s,a)],
minπ∈Π⁡maxD∈(0,1)𝒮×𝒜​𝔼π​[log⁡(D⁡(s,a))]+𝔼πE​[log⁡(1−D⁡(s,a))]−λ​H​(π),\min_{\pi\in\Pi}\max_{D\in(0,1)^{\mathcal{S}\times\mathcal{A}}}\mathbb{E}_{\pi}[\log(D(s,a))]+\mathbb{E}_{\pi^{E}}[\log(1-D(s,a))]-\lambda H(\pi),
minπ⁡ψ∗​(ρπ−ρπE)−H⁡(π)\min_{\pi}\psi^{*}(\rho_{\pi}-\rho_{\pi^{E}})-H(\pi)

H⁡(π)=𝔼π​[−log⁡π⁡(a|s)]H(\pi)=\mathbb{E}_{\pi}[-\log\pi(a|s)]

ψ:ℝ𝒮×𝒜→ℝ∪{∞}\psi:\mathbb{R}^{\mathcal{S}\times\mathcal{A}}\to\mathbb{R}\cup\{\infty\}

D:𝒮×𝒜→(0,1)D:\mathcal{S}\times\mathcal{A}\to(0,1)

𝒞=ℝ𝒮×𝒜\mathcal{C}=\mathbb{R}^{\mathcal{S}\times\mathcal{A}}

minπ⁡DJS⁡(ρπ,ρπE)−λ​H​(π)\min_{\pi}\operatorname{D_{JS}}(\rho_{\pi},\rho_{\pi^{E}})-\lambda H(\pi)

Appendix B Proofs of hardness results

The hardness appendix proves policy identification on visited states, supplies explicit failure games, and presents the support-based reduction claimed for the tight lower bound. All proof equations and the reduction algorithm are preserved.

B.1 Proof of Theorem 1

Equal state–action occupancies force the same visited region: a positive action probability at a visited state would otherwise contradict equality. Within that region, their action marginals agree and normalized conditional policies must coincide. Nothing constrains behavior where both occupancies vanish.

Equations
∑a′∈𝒜π⁡(a′|s)<∑a′∈𝒜π′​(a′|s)=1\sum_{a^{\prime}\in\mathcal{A}}\pi(a^{\prime}|s)<\sum_{a^{\prime}\in\mathcal{A}}\pi^{\prime}(a^{\prime}|s)=1

ρπ′​(a,s)=μπ′​(s)​π′​(a|s)=0\rho_{\pi^{\prime}}(a,s)=\mu_{\pi^{\prime}}(s)\pi^{\prime}(a|s)=0

B.2 Proof of Nash equilibria for the game in Figure 1

Against an opponent always taking a₁, a unilateral a₂ produces the worst reward and a self-loop. Its advantage cannot be positive when the expert value is at least −1/(1−γ), establishing the cycle policy as a Nash equilibrium. The original advantage algebra is retained.

Equations
AiπE​(ai,s)=QiπE​(s,ai,a−i)−ViπE​(s),with ​a−i=a1A^{\pi^{E}}_{i}(a^{i},s)=Q^{\pi^{E}}_{i}(s,a^{i},a^{-i})-V^{\pi^{E}}_{i}(s),\quad\text{with }a^{-i}=a_{1}
AiπE​(ai,s)\displaystyle A^{\pi^{E}}_{i}(a^{i},s) =ri​(ai≠a−i,s)−ViπE​(s)+γ​QiπE​(s,ai,a−i)\displaystyle=r_{i}(a^{i}\neq a^{-i},s)-V^{\pi^{E}}_{i}(s)+\gamma Q^{\pi^{E}}_{i}(s,a^{i},a^{-i})
=−1−(1−γ)​ViπE​(s)+γ​AiπE​(ai,s)\displaystyle=-1-(1-\gamma)V^{\pi^{E}}_{i}(s)+\gamma A^{\pi^{E}}_{i}(a^{i},s)
≤γ​AiπE​(ai,s)\displaystyle\leq\gamma A^{\pi^{E}}_{i}(a^{i},s)

QiπE​(s,ai,a−i)≔ri​(s,ai,a−i)+γ​∑s′∈𝒮P⁡(s′|s,a)​ViπE​(s′)Q^{\pi^{E}}_{i}(s,a^{i},a^{-i})\coloneqq r_{i}(s,a^{i},a^{-i})+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V^{\pi^{E}}_{i}(s^{\prime})

B.3 Proof of Theorem 2

In the infinite chain, odd states reward one and even states reward zero. Expert and learner follow the same even branch, but differ at the unvisited first odd state. A deviating player can exploit the learner there and continue through rewarding states; the expert’s off-path response prevents that gain.

The printed lower bound is 1/(1−γ)−1. The explicit policy and all transitions are retained; the example explains why identical demonstrated occupancy does not identify strategic off-path behavior.

Complete original A2.F4, including all labels and relationships.
Figure 4: Transition dynamics for the two-player game. s0s_{0} is the initial state. The top branch contains all odd states while the bottom branch together with s0s_{0} comprises all even states.
Diagram mathematical labels

s0s_{0}

s1s_{1}

s2s_{2}

s3s_{3}

s4s_{4}

s5s_{5}

s6s_{6}

s2​k−1s_{2k-1}

s2​ks_{2k}

…\dots

…\dots

(a2,a1)(a_{2},a_{1})

(a2,a1)(a_{2},a_{1})

⋯\cdots

⋯\cdots

Equations
NashGap⁡(π)≥V1π1′,π2​(s0)−V1π​(s0)=11−γ−1≥Ω⁡(11−γ)\operatorname{NashGap}(\pi)\geq V_{1}^{\pi^{\prime}_{1},\pi_{2}}(s_{0})-V_{1}^{\pi}(s_{0})=\frac{1}{1-\gamma}-1\geq\Omega\left(\frac{1}{1-\gamma}\right)
π1′​(a1|s)={1if ​a1=a2​ and ​s∈{s0,s1}0if ​a1≠a2​ and ​s∈{s0,s1}π1​(a1|s)otherwise\pi^{\prime}_{1}(a^{1}|s)=\begin{cases}1&\text{if }a^{1}=a_{2}\text{ and }s\in\{s_{0},s_{1}\}\\ 0&\text{if }a^{1}\neq a_{2}\text{ and }s\in\{s_{0},s_{1}\}\\ \pi_{1}(a^{1}|s)&\text{otherwise}\end{cases}

𝒜i={a1,a2,a3}\mathcal{A}_{i}=\{a_{1},a_{2},a_{3}\}

πE​((a1,a1)|s0)=1\pi^{E}((a_{1},a_{1})|s_{0})=1

πE​((a3,a3)|s1)=1\pi^{E}((a_{3},a_{3})|s_{1})=1

π⁡((a1,a1)|s0)=1\pi((a_{1},a_{1})|s_{0})=1

π⁡((a1,a1)|s1)=1\pi((a_{1},a_{1})|s_{1})=1

B.4 Proof of Theorem 3

The claimed reduction first seeks an approximate equilibrium support, then uses a tight-lower-bound oracle to identify it. Exact support recovery and approximate support recovery are distinct subclaims, each with its original statement retained.

Equation
Lemma 5.

Finding an ϵ\epsilon-Nash equilibrium support in a general bimatrix game is PPAD-complete.

B.4.1 Proof of Lemma 5

For an exact known equilibrium support, indifference equalities and probability normalization motivate a linear feasibility problem. The printed program includes only equalities among supported actions; it omits inequalities ruling out profitable unsupported actions. A feasible solution to the displayed constraints alone need not be an equilibrium.

The approximate version replaces indifference equalities with ±ϵ slack. Approximate Nash regret does not require every supported action to be within ϵ of every other supported action: a poor action can have tiny probability. The displayed argument therefore needs additional support/approximation conditions; the programs remain unchanged for inspection.

Equations
Theorem 4.

Finding the support of any Nash equilibrium in a bimatrix game is PPAD-complete.

π1⊤​A1​π2=maxi⁡A1,i⊤​π2⟹A1,j⊤​π2=A1,k⊤​π2​∀j,k∈ν1,\pi_{1}^{\top}A_{1}\pi_{2}=\max_{i}{A_{1,i}}^{\top}\pi_{2}\implies{A_{1,j}}^{\top}\pi_{2}={A_{1,k}}^{\top}\pi_{2}\ \forall j,k\in\nu_{1},
Find\displaystyle\textrm{Find} x∈ℝ|ν1|,y∈ℝ|ν2|\displaystyle x\in\mathbb{R}^{|\nu_{1}|},\ y\in\mathbb{R}^{|\nu_{2}|}
s.t.\displaystyle\textrm{s.t.} ∑i=1|ν1|xi=∑i=1|ν2|yi=1\displaystyle\sum_{i=1}^{|\nu_{1}|}x_{i}=\sum_{i=1}^{|\nu_{2}|}y_{i}=1
(A2,j−A2,k)⊤​x=0∀j,k∈ν2\displaystyle(A_{2,j}-A_{2,k})^{\top}x=0\quad\forall j,k\in\nu_{2}
(A1,j−A1,k)⊤​y=0∀j,k∈ν1\displaystyle(A_{1,j}-A_{1,k})^{\top}y=0\quad\forall j,k\in\nu_{1}
xi≥0∀i∈ν1\displaystyle x_{i}\geq 0\quad\forall i\in\nu_{1}
yi≥0∀i∈ν2\displaystyle y_{i}\geq 0\quad\forall i\in\nu_{2}
Find\displaystyle\textrm{Find} x∈ℝ|ν1|,y∈ℝ|ν2|\displaystyle x\in\mathbb{R}^{|\nu_{1}|},\ y\in\mathbb{R}^{|\nu_{2}|}
s.t.\displaystyle\textrm{s.t.} ∑i=1|ν1|xi=∑i=1|ν2|yi=1\displaystyle\sum_{i=1}^{|\nu_{1}|}x_{i}=\sum_{i=1}^{|\nu_{2}|}y_{i}=1
(A2,j−A2,k)⊤​x≤ϵ∀j,k∈ν2\displaystyle(A_{2,j}-A_{2,k})^{\top}x\leq\epsilon\quad\forall j,k\in\nu_{2}
(A1,j−A1,k)⊤​y≤ϵ∀j,k∈ν1\displaystyle(A_{1,j}-A_{1,k})^{\top}y\leq\epsilon\quad\forall j,k\in\nu_{1}
(A2,k−A2,j)⊤​x≤ϵ∀j,k∈ν2\displaystyle(A_{2,k}-A_{2,j})^{\top}x\leq\epsilon\quad\forall j,k\in\nu_{2}
(A1,k−A1,j)⊤​y≤ϵ∀j,k∈ν1\displaystyle(A_{1,k}-A_{1,j})^{\top}y\leq\epsilon\quad\forall j,k\in\nu_{1}
xi≥0∀i∈ν1\displaystyle x_{i}\geq 0\quad\forall i\in\nu_{1}
yi≥0∀i∈ν2\displaystyle y_{i}\geq 0\quad\forall i\in\nu_{2}

A1,A2∈ℝn×nA_{1},A_{2}\in\mathbb{R}^{n\times n}

ν1,ν2⊆{1,…,n}\nu_{1},\nu_{2}\subseteq\{1,\dots,n\}

B.4.2 Reduction for the proof of Theorem 3

Algorithm 1 depresses candidate action payoffs to a value K below the original rewards and queries the lower-bound oracle. Its comparison with a baseline s decides whether to retain each action, aiming to recover a lexicographically selected support with polynomially many calls.

The argument assumes that a change in the constrained minimum identifies an indispensable support action. Its oracle-error notation switches between δ and s in the minimizer definition, and the support-selection step is asserted rather than fully established by the displayed constraints. These are qualifications on the printed reduction, not alterations to its formal statement.

Complete original alg1, including all labels and relationships.
Algorithm 1 Lower bound reduction
Copyable reduction algorithm

Given a game A1,A2A_{1},A_{2} and a target Nash precision ϵ\epsilon.
Define A1ν=A1A_{1}^{\nu}=A_{1}, A2ν=A2A_{2}^{\nu}=A_{2}.
Define KK such that −1<K<−maxi,j⁡max⁡{|A1i,j|,|A2i,j|}-1<K<-\max_{i,j}\max\{|{A_{1}}_{i,j}|,|{A_{2}}_{i,j}|\}.
Define ν1=ν2=∅\nu_{1}=\nu_{2}=\emptyset.
Define δ=∥ϵ/K⋅e1∥1\delta=\lVert\epsilon/K\cdot e_{1}\rVert_{1} such that s=L⁡((A1,A2),δ)≤ϵs=L((A_{1},A_{2}),\delta)\leq\epsilon, for a canonical vector e1e_{1}.
for i∈{1,…,n}i\in\{1,\dots,n\} do

  Define A1iA_{1}^{i} such that
  • •

    {A1i}a,b={A1ν}a,b​∀a,b∈[n]∖{i}×[n]\{A_{1}^{i}\}_{a,b}=\{A_{1}^{\nu}\}_{a,b}\ \forall a,b\in[n]\setminus\{i\}\times[n]

  • •

    {A1i}i=K⋅1\{A_{1}^{i}\}_{i}=K\cdot 1

Use the oracle to compute l1i=L⁡((A1i,A2),δ)l_{1}^{i}=L((A_{1}^{i},A_{2}),\delta).
if l1i>sl_{1}^{i}>s then
ν1←ν1∪{i}\nu_{1}\leftarrow\nu_{1}\cup\{i\}. 
else
A1ν←A1iA_{1}^{\nu}\leftarrow A_{1}^{i}. 
for i∈{1,…,n}i\in\{1,\dots,n\} do
  Define A2iA_{2}^{i} such that
  • •

    {A2i}a,b={A2ν}a,b​∀a,b∈[n]∖{i}×[n]\{A_{2}^{i}\}_{a,b}=\{A_{2}^{\nu}\}_{a,b}\ \forall a,b\in[n]\setminus\{i\}\times[n]

  • •

    {A2i}i=K⋅1\{A_{2}^{i}\}_{i}=K\cdot 1

Use the oracle to compute l2i=L⁡((A1,A2i),δ)l_{2}^{i}=L((A_{1},A_{2}^{i}),\delta).
if l2i>sl_{2}^{i}>s then
ν2←ν2∪{i}\nu_{2}\leftarrow\nu_{2}\cup\{i\}. 
else
A2ν←A2iA_{2}^{\nu}\leftarrow A_{2}^{i}. 
Return ν1,ν2\nu_{1},\nu_{2}
Equations
Πmins≔argminπ1,π2:∥π1​π2⊤−π1E​π2E⊤∥1=sNashGap(π1,π2),\Pi^{s}_{\min}\coloneqq{\arg\min}_{\pi_{1},\pi_{2}:\lVert\pi_{1}\pi_{2}^{\top}-\pi^{E}_{1}{\pi^{E}_{2}}^{\top}\rVert_{1}=s}\operatorname{NashGap}(\pi_{1},\pi_{2}),

maxi,j⁡max⁡{|A1i,j|,|A2i,j|}<1\max_{i,j}\max\{|{A_{1}}_{i,j}|,|{A_{2}}_{i,j}|\}<1

Appendix C Proofs of upper bounds

The upper-bound proofs use performance differences, bounded rewards and the L1 distance between product policies. Their dependence on the best-response assumption is explicit.

C.1 Proof of Lemma 3

Dominance allows replacing the optimizing deviation by the expert’s own component. Insert the all-expert value between learner and mixed-profile values; bound both differences under expert occupancy by the supremum Q-value and policy L1 error.

The product bound contributes n errors for the joint policy and n−1 for opponents, yielding (2n−1)ϵBC/(1−γ)². This reasoning is applied per player before maximizing; a displayed intermediate subtraction of two maxima should not be read as a generally valid identity.

Equations
NashGap⁡(π)=maxi,πi∗⁡[Viπi∗,π−i​(ν0)−Viπi,π−i​(ν0)]=maxi⁡[ViπiE,π−i​(ν0)−Viπi,π−i​(ν0)]\operatorname{NashGap}(\pi)=\max_{i,\pi^{*}_{i}}\left[V_{i}^{\pi^{*}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]=\max_{i}\left[V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]
NashGap⁡(π)\displaystyle\operatorname{NashGap}(\pi) =maxi⁡[ViπiE,π−i​(ν0)−Viπi,π−i​(ν0)]\displaystyle=\max_{i}\left[V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]
=maxi⁡[ViπiE,π−i​(ν0)−ViπE​(ν0)+ViπE​(ν0)−Viπi,π−i​(ν0)]\displaystyle=\max_{i}\left[V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi^{E}}(\nu_{0})+V_{i}^{\pi^{E}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]
≤11−γ⋅maxi⁡𝔼s∼μπE​[∑aQπ​(s,a)​(πE​(a|s)−π⁡(a|s))]\displaystyle\leq\frac{1}{1-\gamma}\cdot\max_{i}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\sum_{a}Q^{\pi}(s,a)\left(\pi^{E}(a|s)-\pi(a|s)\right)\right]
−11−γ⋅maxi𝔼s∼μπE[∑aQπiE,π−i(s,a)(π−iE(a−i|s)−π−i(a−i|s))πiE(ai|s)]\displaystyle\quad-\frac{1}{1-\gamma}\cdot\max_{i}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\sum_{a}Q^{\pi^{E}_{i},\pi_{-i}}(s,a)\left(\pi^{E}_{-i}(a_{-i}|s)-\pi_{-i}(a_{-i}|s)\right)\pi^{E}_{i}(a_{i}|s)\right]
NashGap⁡(π)\displaystyle\operatorname{NashGap}(\pi) ≤1(1−γ)2⋅maxi𝔼s∼μπE[‖π(⋅|s)−πE(⋅|s)‖1+‖π−i(⋅|s)−π−iE(⋅|s)‖1]\displaystyle\leq\frac{1}{(1-\gamma)^{2}}\cdot\max_{i}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\left\lVert\pi(\cdot|s)-\pi^{E}(\cdot|s)\right\rVert_{1}+\left\lVert\pi_{-i}(\cdot|s)-\pi^{E}_{-i}(\cdot|s)\right\rVert_{1}\right]
NashGap⁡(π)≤(2​n−1)​ϵBC(1−γ)2≤2​n​ϵBC(1−γ)2\operatorname{NashGap}(\pi)\leq\frac{(2n-1)\epsilon_{\text{BC}}}{(1-\gamma)^{2}}\leq\frac{2n\epsilon_{\text{BC}}}{(1-\gamma)^{2}}

∥Qπ′∥∞≤1/(1−γ)\lVert Q^{\pi^{\prime}}\rVert_{\infty}\leq 1/(1-\gamma)

C.2 Proof of Lemma 4

Without dominance, insert the actual best response. Triangle inequality separates opponent imitation error from response-to-expert distance, adding the δ term. The same product-policy accounting gives 2n−1 for ordinary errors. The joint-versus-per-player δ argument qualification from Section 6.3 still applies.

Equations
NashGap⁡(π)\displaystyle\operatorname{NashGap}(\pi) ≤1(1−γ)2⋅maxi𝔼s∼μπE[‖π(⋅|s)−πE(⋅|s)‖1+‖(πi∗,π−i)(⋅|s)−πE(⋅|s)‖1]\displaystyle\leq\frac{1}{(1-\gamma)^{2}}\cdot\max_{i}\mathbb{E}_{s\sim\mu_{\pi^{E}}}\left[\left\lVert\pi(\cdot|s)-\pi^{E}(\cdot|s)\right\rVert_{1}+\left\lVert(\pi^{*}_{i},\pi_{-i})(\cdot|s)-\pi^{E}(\cdot|s)\right\rVert_{1}\right]
NashGap⁡(π)≤(2​n−1)​ϵBC+δ⁡(ϵBC)(1−γ)2≤2​n​ϵBC+δ⁡(ϵBC)(1−γ)2\operatorname{NashGap}(\pi)\leq\frac{(2n-1)\epsilon_{\text{BC}}+\delta(\epsilon_{\text{BC}})}{(1-\gamma)^{2}}\leq\frac{2n\epsilon_{\text{BC}}+\delta(\epsilon_{\text{BC}})}{(1-\gamma)^{2}}

Appendix D Additional lemmas

Lemma D.1 expresses return differences as an advantage expectation under the alternative policy’s occupancy. Lemma D.2 proves that the L1 distance between product distributions is at most the sum of component L1 distances.

For the product lemma, add/subtract one mixed product, apply triangle inequality and use probability normalization; induction extends the two-factor step. These identities explain both the horizon factors and the linear dependence on the number of players.

Equations
Lemma D.1 (Performance Difference Lemma, see e.g. Theorem IX.5 in Alatur et al. (2024)).

For any π,π′∈Π,i∈[n]\pi,\pi^{\prime}\in\Pi,i\in[n],

Viπi′,π−i​(ν0)−Viπi,π−i​(ν0)=11−γ​𝔼s,a∼ρπi′,π−i​[Qiπ​(s,a)−Viπ​(s)],V_{i}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})=\frac{1}{1-\gamma}\mathbb{E}_{s,a\sim\rho_{\pi^{\prime}_{i},\pi_{-i}}}\left[Q^{\pi}_{i}(s,a)-V^{\pi}_{i}(s)\right],

where Qiπ​(s,a)≔ri​(s,a)+γ​∑s′∈𝒮P⁡(s′|s,a)​Viπ​(s′)Q^{\pi}_{i}(s,a)\coloneqq r_{i}(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V^{\pi}_{i}(s^{\prime}).

And more generally,

Viπ′​(ν0)−Viπ​(ν0)=11−γ​𝔼s,a∼ρπ′​[Qiπ​(s,a)−Viπ​(s)],V_{i}^{\pi^{\prime}}(\nu_{0})-V_{i}^{\pi}(\nu_{0})=\frac{1}{1-\gamma}\mathbb{E}_{s,a\sim\rho_{\pi^{\prime}}}\left[Q^{\pi}_{i}(s,a)-V^{\pi}_{i}(s)\right],
Lemma D.2.

Let n∈ℕn\in\mathbb{N}, and let pi,qi∈Δmi−1p_{i},q_{i}\in\Delta_{m_{i}-1} be probability distributions over a discrete set of size mim_{i} isomorphic to [mi][m_{i}]. Further, note p=×i=1npi,q=×i=1nqip=\times_{i=1}^{n}p_{i},q=\times_{i=1}^{n}q_{i}. Then,

∑j∈[m1]×⋯×[mn]|p⁡(j)−q⁡(j)|≤∑i=1n∑j=1mi|pi​(j)−qi​(j)|\sum_{j\in[m_{1}]\times\dots\times[m_{n}]}\lvert p(j)-q(j)\rvert\leq\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\lvert p_{i}(j)-q_{i}(j)\rvert
∑j∈Sn×[mn+1]|p⁡(j)−q⁡(j)|\displaystyle\sum_{j\in S_{n}\times[m_{n+1}]}\lvert p(j)-q(j)\rvert =∑j1∈Sn∑j2∈[mn+1]|pn​(j1)​pn+1​(j2)−qn​(j1)​qn+1​(j2)|\displaystyle=\sum_{j_{1}\in S_{n}}\sum_{j_{2}\in[m_{n+1}]}\lvert p^{n}(j_{1})p_{n+1}(j_{2})-q^{n}(j_{1})q_{n+1}(j_{2})\rvert
=∑j1∈Sn∑j2∈[mn+1]|pn(j1)pn+1(j2)−qn(j1)pn+1(j2)\displaystyle=\sum_{j_{1}\in S_{n}}\sum_{j_{2}\in[m_{n+1}]}\lvert p^{n}(j_{1})p_{n+1}(j_{2})-q^{n}(j_{1})p_{n+1}(j_{2})
+qn(j1)pn+1(j2)−qn(j1)qn+1(j2)|\displaystyle\qquad\qquad\qquad+q^{n}(j_{1})p_{n+1}(j_{2})-q^{n}(j_{1})q_{n+1}(j_{2})\rvert
≤∑j1∈Sn∑j2∈[mn+1]|pn​(j1)​pn+1​(j2)−qn​(j1)​pn+1​(j2)|\displaystyle\leq\sum_{j_{1}\in S_{n}}\sum_{j_{2}\in[m_{n+1}]}\lvert p^{n}(j_{1})p_{n+1}(j_{2})-q^{n}(j_{1})p_{n+1}(j_{2})\rvert
+∑j1∈Sn∑j2∈[mn+1]|qn(j1)pn+1(j2)−qn(j1)qn+1(j2)|\displaystyle+\sum_{j_{1}\in S_{n}}\sum_{j_{2}\in[m_{n+1}]}\lvert q^{n}(j_{1})p_{n+1}(j_{2})-q^{n}(j_{1})q_{n+1}(j_{2})\rvert
=∑j1∈Sn|pn​(j1)−qn​(j1)|+∑j2∈[mn+1]|pn+1​(j2)−qn+1​(j2)|\displaystyle=\sum_{j_{1}\in S_{n}}\lvert p^{n}(j_{1})-q^{n}(j_{1})\rvert+\sum_{j_{2}\in[m_{n+1}]}\lvert p_{n+1}(j_{2})-q_{n+1}(j_{2})\rvert
≤∑i=1n∑j=1mi|pi​(j)−qi​(j)|+∑j2∈[mn+1]|pn+1​(j2)−qn+1​(j2)|\displaystyle\leq\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\lvert p_{i}(j)-q_{i}(j)\rvert+\sum_{j_{2}\in[m_{n+1}]}\lvert p_{n+1}(j_{2})-q_{n+1}(j_{2})\rvert
=∑i=1n+1∑j=1mi|pi​(j)−qi​(j)|\displaystyle=\sum_{i=1}^{n+1}\sum_{j=1}^{m_{i}}\lvert p_{i}(j)-q_{i}(j)\rvert

Sn=×i=1n[mi]S_{n}=\times_{i=1}^{n}[m_{i}]

pn=×i=1npi,qn=×i=1nqip^{n}=\times_{i=1}^{n}p_{i},q^{n}=\times_{i=1}^{n}q_{i}

Appendix E Numerical Validation

The numerical example is a two-player zero-sum tag game on a 2×3 grid with γ=0.8. Players move in four directions, exchange tagger roles on contact and receive boundary penalties. Two nonsymmetric corner initializations represent the tested starts.

A regularized Nash value-iteration solution supplies the expert. Random perturbations generate imitation policies; 2,000 episodes estimate expert occupancy, and induced-MDP value iteration computes responses. The resulting cumulative maxima are estimates over sampled policies, not certified uniform envelopes over all deviations.

Equation

𝒜1=𝒜2={0,1,2,3}\mathcal{A}_{1}=\mathcal{A}_{2}=\{0,1,2,3\}

E.1 On the validity of the upper bound (Lemma 4 )

With temperature 0.1, 400 noise levels span [0,0.4]. The plot compares sampled cumulative maxima of Nash gap and response distance; both generally increase with BC error. The proposed horizon-squared bound is loose in this toy game.

Agreement with these samples illustrates the conditional theory but cannot independently prove a valid global δ or the bound for arbitrary games. The plot’s “tight” terminology refers to the sampled envelope.

Complete original A5.F5, with all plotted curves, labels and legend.
Figure 5: Evolution of the tight Nash gap upper bound and the tight δ\delta function with the behavior cloning error. This shows how the delta function and Nash gap tend to increase together in the simple Tag-Game environment.

E.2 On the impact of entropy regularization

Using 250 perturbations across noise levels [0,1], higher entropy temperatures reduce the estimated response-sensitivity envelope in this game. The same trend is shown near BC error 10⁻².

Lower δ does not necessarily lower actual NashGap because the bound is not tight and regularization changes the equilibrium/response objective. The paper explicitly limits this inference; extensions to human demonstrations and risk aversion remain motivation rather than established results.

Complete original A5.F6.sf1, with all plotted curves, labels and legend.
(a) Large range of ϵBC\epsilon_{\text{BC}}
Complete original A5.F6.sf2, with all plotted curves, labels and legend.
(b) ϵBC\epsilon_{\text{BC}} at scale 10−210^{-2}
Figure 6: Evolution of the tight δ\delta for different entropy temperature parameters. This shows that a greater temperature leads to a better control on δ\delta. This behavior is consistent on the full range of ϵBC\epsilon_{\text{BC}} values.

Appendix F Finite horizon case

The finite-horizon appendix replaces discounted occupancy with time-indexed visitation and develops analogous counterexamples and H² upper bounds. The full finite-horizon formulas are preserved, including notation irregularities.

F.1 Definitions

Policies and rewards become time-dependent over H stages. Error assumptions take a maximum over time, which differs from an average under discounted occupancy.

F.1.1 Finite horizon Markov Games

Each time t has a state distribution μᵗ and state–action distribution ρᵗ. Values accumulate rewards from t through H−1. The printed value definition keeps t in its summand while summing over h, and omits explicit conditioning on the starting state; those indexing/conditioning details require interpretation.

Equations
μπt​(s)≔ℙ⁡(st=s)ρπt​(s,a)≔μπt​(s)​πt​(a|s)\mu^{t}_{\pi}(s)\coloneqq\mathbb{P}(s_{t}=s)\hskip 50.00008pt\rho^{t}_{\pi}(s,a)\coloneqq\mu^{t}_{\pi}(s)\pi^{t}(a|s)
Vi,tπ​(s)≔∑h=tH−1𝔼(s,a)∼ρπt​[rit​(s,a)]∀i∈[n],V_{i,t}^{\pi}(s)\coloneqq\sum_{h=t}^{H-1}\mathbb{E}_{(s,a)\sim\rho^{t}_{\pi}}[r^{t}_{i}(s,a)]\quad\forall i\in[n],

(𝒮,𝒜,P,{ri}i=1n,ν0,H)(\mathcal{S},\mathcal{A},P,\{r_{i}\}_{i=1}^{n},\nu_{0},H)

Viπ​(s)=Vi,0π​(s)V_{i}^{\pi}(s)=V_{i,0}^{\pi}(s)

rit:𝒮×𝒜→[−1,1]r^{t}_{i}:\mathcal{S}\times\mathcal{A}\to[-1,1]

πit:𝒮→Δ𝒜\pi^{t}_{i}:\mathcal{S}\to\Delta_{\mathcal{A}}

F.1.2 Assumptions on matching errors

Finite-horizon BC error is the largest expert-occupancy-averaged per-player L1 error over all times. State-only and state–action errors likewise take the maximum time-indexed occupancy discrepancy. These worst-time quantities should not be replaced by average training error.

Equation

ϵBC≔maxi,t𝔼s∼μπEt[‖πi,t(⋅|s)−πi,tE(⋅|s)‖1]\epsilon_{\text{BC}}\coloneqq\max_{i,t}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi_{i,t}(\cdot|s)-\pi^{E}_{i,t}(\cdot|s)\right\rVert_{1}\right]

ϵμ≔maxt⁡‖μπt−μπEt‖1\epsilon_{\mu}\coloneqq\max_{t}\left\lVert\mu^{t}_{\pi}-\mu^{t}_{\pi^{E}}\right\rVert_{1}

ϵρ≔maxt⁡‖ρπt−ρπEt‖1\epsilon_{\rho}\coloneqq\max_{t}\left\lVert\rho^{t}_{\pi}-\rho^{t}_{\pi^{E}}\right\rVert_{1}

F.2 Performance difference lemma for finite horizon

Expand the Q-function one step, add/subtract the reference value, and telescope through the H stages. This yields a sum of reference-policy advantages evaluated under the alternative trajectory distribution. The more general joint-policy statement follows the same construction; the source’s malformed closing-parenthesis notation remains visible.

Equations
Lemma F.1 (Finite horizon version of Lemma D.1).

For any π,π′∈Π,i∈[n]\pi,\pi^{\prime}\in\Pi,i\in[n],

Viπi′,π−i​(ν0)−Viπi,π−i​(ν0)=∑t=0H−1𝔼s,a∼ρ(πi′,π−i)t​[Qi,tπ​(s,a)−Vi,tπ​(s)],V_{i}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})=\sum_{t=0}^{H-1}\mathbb{E}_{s,a\sim\rho^{t}_{(\pi^{\prime}_{i},\pi_{-i})}}\left[Q^{\pi}_{i,t}(s,a)-V^{\pi}_{i,t}(s)\right],

where Qi,tπ​(s,a)≔rit​(s,a)+∑s′∈𝒮P⁡(s′|s,a)​Vi,t+1π​(s′)Q^{\pi}_{i,t}(s,a)\coloneqq r^{t}_{i}(s,a)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V^{\pi}_{i,t+1}(s^{\prime}).

And more generally,

Complete original A6.Ex52, including all labels and relationships.
Original source MathML
Viπ′​(ν0)−Viπ​(ν0)=∑t=0H−1𝔼s,a∼ρ(π′CLOSEt​[Qi,tπ​(s,a)−Vi,tπ​(s)],V_{i}^{\pi^{\prime}}(\nu_{0})-V_{i}^{\pi}(\nu_{0})=\sum_{t=0}^{H-1}\mathbb{E}_{s,a\sim\rho^{t}_{(\pi^{\prime}}}\left[Q^{\pi}_{i,t}(s,a)-V^{\pi}_{i,t}(s)\right],
Qi,tπ~(s,ai)=𝔼a−i∼π~−i,t(⋅|s)[rit(s,a)+𝔼s′[Vi,t+1π~(s′)]],0≤t≤H−1Q^{\tilde{\pi}}_{i,t}(s,a_{i})=\mathbb{E}_{a_{-i}\sim\tilde{\pi}_{-i,t}(\cdot|s)}\left[r^{t}_{i}(s,a)+\mathbb{E}_{s^{\prime}}\left[V_{i,t+1}^{\tilde{\pi}}(s^{\prime})\right]\right],\quad 0\leq t\leq H-1
Vi,tπi′,π−i​(νt)\displaystyle V_{i,t}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{t}) =Vi,tπi′,π−i(νt)−𝔼s∼νt,ai∼π′i,t(⋅|s)[Qi,tπ(s,ai)]+𝔼s∼νt,ai∼π′i,t(⋅|s)[Qi,tπ(s,ai)]\displaystyle=V_{i,t}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{t})-\mathbb{E}_{s\sim\nu_{t},a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi}_{i,t}(s,a_{i})\right]+\mathbb{E}_{s\sim\nu_{t},a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi}_{i,t}(s,a_{i})\right]
=𝔼s∼νt,ai∼π′i,t(⋅|s)[Qi,tπi′,π−i(s,ai)]\displaystyle=\mathbb{E}_{s\sim\nu_{t},a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi^{\prime}_{i},\pi_{-i}}_{i,t}(s,a_{i})\right]
−𝔼s∼νt,ai∼π′i,t(⋅|s)[Qi,tπ(s,ai)]+𝔼s∼νt,ai∼π′i,t(⋅|s)[Qi,tπ(s,ai)]\displaystyle\qquad-\mathbb{E}_{s\sim\nu_{t},a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi}_{i,t}(s,a_{i})\right]+\mathbb{E}_{s\sim\nu_{t},a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi}_{i,t}(s,a_{i})\right]
=Vi,t+1πi′,π−i(νt+1)−Vi,t+1πi,π−i(νt+1)+𝔼s∼νt,ai∼π′i,t(⋅|s)[Qi,tπ(s,ai)]\displaystyle=V_{i,t+1}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{t+1})-V_{i,t+1}^{\pi_{i},\pi_{-i}}(\nu_{t+1})+\mathbb{E}_{s\sim\nu_{t},a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi}_{i,t}(s,a_{i})\right]
Viπi′,π−i(ν0)−Viπ(ν0)=∑t=0H−1𝔼s∼μπi′,π−it[𝔼ai∼π′i,t(⋅|s)[Qi,tπ(s,ai)]−Vi,tπ(s)]V_{i}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi}(\nu_{0})=\sum_{t=0}^{H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{\prime}_{i},\pi_{-i}}}\left[\mathbb{E}_{a_{i}\sim\pi^{\prime}_{i,t}(\cdot|s)}\left[Q^{\pi}_{i,t}(s,a_{i})\right]-V_{i,t}^{\pi}(s)\right]
Viπi′,π−i​(ν0)−Viπi,π−i​(ν0)\displaystyle V_{i}^{\pi^{\prime}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0}) =∑t=0H−1𝔼s,a∼ρ(πi′,π−i)t​[Qi,tπ​(s,a)−Vi,tπ​(s)]\displaystyle=\sum_{t=0}^{H-1}\mathbb{E}_{s,a\sim\rho^{t}_{(\pi^{\prime}_{i},\pi_{-i})}}\left[Q^{\pi}_{i,t}(s,a)-V^{\pi}_{i,t}(s)\right]

νt∼μπi′,π−it\nu_{t}\sim\mu^{t}_{\pi^{\prime}_{i},\pi_{-i}}

F.3 Results

The appendix states finite analogues of the matching impossibilities and response-sensitive bounds. It preserves the same distinction between lack of action information, missing coverage and unstable best responses.

F.3.1 Section 4

The three-state example gives order-H exploitability despite state-only matching. Truncating the off-path chain yields a finite-state, finite-horizon example with matching state–action distributions at each time but order-H exploitability.

Equations
Lemma F.2 (Finite version of Lemma 1).

There exists a game and a corresponding expert policy πE\pi^{E} such that 𝒮πE+=𝒮\mathcal{S}^{+}_{\pi^{E}}=\mathcal{S}. Moreover, there exists a policy π\pi such that μπE=μπ\mu_{\pi^{E}}=\mu_{\pi} and NashGap⁡(π)≥Ω⁡(H)\operatorname{NashGap}(\pi)\geq\Omega\left(H\right).

Theorem F.1 (Finite horizon version of Theorem 2).

There exists a Markov Game with expert policy πE\pi^{E} and a learner policy π\pi such that even if ρπEt=ρπt\rho^{t}_{\pi^{E}}=\rho^{t}_{\pi} for all 0≤t≤H−10\leq t\leq H-1, the Nash gap scales linearly with the horizon; i.e., NashGap⁡(π)≥Ω⁡(H)\operatorname{NashGap}(\pi)\geq\Omega\left(H\right).

F.3.2 Section 6

Dominance gives NashGap ≤2nϵBC H² by bounding each stage’s Q-values by H and summing H occupancy-weighted errors. A response-distance assumption adds δ(ϵBC)H²; the appendix again obtains the sharper 2n−1 coefficient before relaxing it.

The claimed finite-horizon sensitivity counterexample only says to adapt the chain length k. It does not spell out how discounted rarity becomes small occupancy under the newly defined worst-time errors. Lemma F.5 also states an order-δ assumption but prints a unit-coefficient δ bound; any hidden constant needs to be retained when applying it.

Equations
Lemma F.3 (Finite horizon version of Lemma 2).

Let 𝒞\mathcal{C} be the class of games with consistent bounds. This class is δ\delta-continuous only for trivial δ\delta such that δ⁡(ϵ)=2\delta(\epsilon)=2 for all ϵ>0\epsilon>0.

Lemma F.4 (Finite horizon version of Lemma 3).

Suppose πE\pi^{E} is a (weak) Dominant Strategy Equilibrium. Then, any learned policy π\pi with BC error ϵBC\epsilon_{\text{BC}} satisfies NashGap⁡(π)≤2​n​ϵBC​H2\operatorname{NashGap}(\pi)\leq 2n\epsilon_{\text{BC}}H^{2}.

NashGap⁡(π)\displaystyle\operatorname{NashGap}(\pi) =maxi,πi∗⁡[Viπi∗,π−i​(ν0)−Viπi,π−i​(ν0)]\displaystyle=\max_{i,\pi^{*}_{i}}\left[V_{i}^{\pi^{*}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]
=maxi⁡[ViπiE,π−i​(ν0)−ViπE​(ν0)+ViπE​(ν0)−Viπi,π−i​(ν0)]\displaystyle=\max_{i}\left[V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi^{E}}(\nu_{0})+V_{i}^{\pi^{E}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0})\right]
ViπE​(ν0)−Viπi,π−i​(ν0)\displaystyle V_{i}^{\pi^{E}}(\nu_{0})-V_{i}^{\pi_{i},\pi_{-i}}(\nu_{0}) =∑t=0H−1𝔼s,a∼ρπEt​[Qi,tπ​(s,a)−Vi,tπ​(s)]\displaystyle=\sum_{t=0}^{H-1}\mathbb{E}_{s,a\sim\rho^{t}_{\pi^{E}}}\left[Q^{\pi}_{i,t}(s,a)-V^{\pi}_{i,t}(s)\right]
=∑t=0H−1𝔼s∼μπEt​[∑aQi,tπ​(s,a)​(πtE​(a|s)−πt​(a|s))]\displaystyle=\sum_{t=0}^{H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\sum_{a}Q^{\pi}_{i,t}(s,a)\left(\pi^{E}_{t}(a|s)-\pi_{t}(a|s)\right)\right]
≤H∑t=0H−1𝔼s∼μπEt[‖πtE(⋅|s)−πt(⋅|s)‖1]\displaystyle\leq H\sum_{t=0}^{H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi^{E}_{t}(\cdot|s)-\pi_{t}(\cdot|s)\right\rVert_{1}\right]
≤H2⋅max0≤t≤H−1𝔼s∼μπEt[‖πtE(⋅|s)−πt(⋅|s)‖1]\displaystyle\leq H^{2}\cdot\max_{0\leq t\leq H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi^{E}_{t}(\cdot|s)-\pi_{t}(\cdot|s)\right\rVert_{1}\right]
ViπiE,π−i​(ν0)−ViπE​(ν0)\displaystyle V_{i}^{\pi^{E}_{i},\pi_{-i}}(\nu_{0})-V_{i}^{\pi^{E}}(\nu_{0}) =∑t=0H−1𝔼s,a∼ρπEt​[Vi,tπiE,π−i​(s)−Qi,tπiE,π−i​(s,a)]\displaystyle=\sum_{t=0}^{H-1}\mathbb{E}_{s,a\sim\rho^{t}_{\pi^{E}}}\left[V^{\pi^{E}_{i},\pi_{-i}}_{i,t}(s)-Q^{\pi^{E}_{i},\pi_{-i}}_{i,t}(s,a)\right]
=∑t=0H−1𝔼s∼μπEt​[∑aQi,tπiE,π−i​(s,a)​(π−i,t​(a|s)−π−i,tE​(a|s))​πi,tE​(ai|s)]\displaystyle=\sum_{t=0}^{H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\sum_{a}Q^{\pi^{E}_{i},\pi_{-i}}_{i,t}(s,a)\left(\pi_{-i,t}(a|s)-\pi^{E}_{-i,t}(a|s)\right)\pi^{E}_{i,t}(a_{i}|s)\right]
≤H∑t=0H−1𝔼s∼μπEt[‖π−i,t(⋅|s)−π−i,tE(⋅|s)‖1]\displaystyle\leq H\sum_{t=0}^{H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi_{-i,t}(\cdot|s)-\pi^{E}_{-i,t}(\cdot|s)\right\rVert_{1}\right]
≤H2⋅max0≤t≤H−1𝔼s∼μπEt[‖π−i,t(⋅|s)−π−i,tE(⋅|s)‖1]\displaystyle\leq H^{2}\cdot\max_{0\leq t\leq H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi_{-i,t}(\cdot|s)-\pi^{E}_{-i,t}(\cdot|s)\right\rVert_{1}\right]
NashGap⁡(π)≤(2​n−1)​ϵBC​H2≤2​n​ϵBC​H2\operatorname{NashGap}(\pi)\leq(2n-1)\epsilon_{\text{BC}}H^{2}\leq 2n\epsilon_{\text{BC}}H^{2}
Lemma F.5 (Finite horizon version of Lemma 4).

Let π\pi be the learned policy, and assume for all i∈[n]i\in[n] and 0≤t≤H−10\leq t\leq H-1 that 𝔼s∼μπEt[∥πi,t∗(⋅|s)−πi,tE(⋅|s)∥1]≤𝒪(δ(ϵBC))\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\lVert\pi_{i,t}^{*}(\cdot|s)-\pi_{i,t}^{E}(\cdot|s)\rVert_{1}\right]\leq\mathcal{O}(\delta(\epsilon_{\text{BC}})) for some function δ\delta, where πi∗∈BRi⁡(π)\pi_{i}^{*}\in\operatorname{BR}_{i}(\pi). Then, NashGap⁡(π)≤(2​n​ϵBC+δ⁡(ϵBC))​H2\operatorname{NashGap}(\pi)\leq\left(2n\epsilon_{\text{BC}}+\delta(\epsilon_{\text{BC}})\right)H^{2}.

NashGap⁡(π)\displaystyle\operatorname{NashGap}(\pi) ≤maxi(max0≤t≤H−1𝔼s∼μπEt[‖πtE(⋅|s)−πt(⋅|s)‖1]\displaystyle\leq\max_{i}\left(\max_{0\leq t\leq H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi^{E}_{t}(\cdot|s)-\pi_{t}(\cdot|s)\right\rVert_{1}\right]\right.
+max0≤t≤H−1𝔼s∼μπEt[‖πtE(⋅|s)−(πi,t∗,π−i,t)(⋅|s)‖1])H2\displaystyle\qquad\left.+\max_{0\leq t\leq H-1}\mathbb{E}_{s\sim\mu^{t}_{\pi^{E}}}\left[\left\lVert\pi^{E}_{t}(\cdot|s)-(\pi^{*}_{i,t},\pi_{-i,t})(\cdot|s)\right\rVert_{1}\right]\right)H^{2}
≤((2​n−1)​ϵBC+δ⁡(ϵBC))​H2\displaystyle\leq\left((2n-1)\epsilon_{\text{BC}}+\delta(\epsilon_{\text{BC}})\right)H^{2}
≤(2​n​ϵBC+δ⁡(ϵBC))​H2\displaystyle\leq\left(2n\epsilon_{\text{BC}}+\delta(\epsilon_{\text{BC}})\right)H^{2}

μπE​(sexp)≤ϵ/2\mu_{\pi^{E}}(s_{\text{exp}})\leq\epsilon/2

Concept demonstration

Open image ↗