Corruption-Robust Offline Two-Player Zero-Sum Markov Games

Andi Nika Debmalya Mandal† Adish Singla Goran Radanovic MPI-SWS University of
Warwick MPI-SWS MPI-SWS

###### Abstract

We study data corruption robustness in offline two-player zero-sum Markov
games. Given a dataset of realized trajectories of two players, an adversary
is allowed to modify an $\epsilon$-fraction of it. The learner’s goal is to
identify an approximate Nash Equilibrium policy pair from the corrupted data.
We consider this problem in linear Markov games under different degrees of
data coverage and corruption. We start by providing an information-theoretic
lower bound on the suboptimality gap of any learner. Next, we propose robust
versions of the Pessimistic Minimax Value Iteration algorithm (Zhong et al.,
2022), both under coverage on the corrupted data and under coverage only on
the clean data, and show that they achieve (near)-optimal suboptimality gap
bounds with respect to $\epsilon$. We note that we are the first to provide
such a characterization of the problem of learning approximate Nash
Equilibrium policies in offline two-player zero-sum Markov games under data
corruption.

###  1 INTRODUCTION

Figure 1: Relationship between coverage assumptions. The minimal coverage
requirements are single policy coverage and LRU coverage for the single-player
and two-player settings, respectively. Arrows stand for implications. The
middle (dashed) arrow denotes the restriction from the two-player to the
single-player setting: when fixing the second player’s policy, the LRU
coverage assumption reduces to the uniform coverage assumption.

Some of the most successful applications of Multi-agent Reinforcement Learning
(MARL) are in competitive game-playing (Silver et al., 2017; Berner et al.,
2019), where we have a model of the environment that we can use for training
purposes. Given that many real-world multi-agent applications, such as
autonomous driving (Pan et al., 2017) or healthcare (Wang et al., 2018), do
not have readily available simulators, there has recently been a growing
interest in studying offline settings, where offline data is used to derive
agents’ policies. Since a dynamic exploration of the environment is
impossible, state-of-the-art (SOTA) algorithms use the paradigm of pessimism
in the face of uncertainty to derive these policies (Jin et al., 2021).
Moreover, these works typically assume that the data is coming from a latent
distribution with “nice” properties.

In practice, however, datasets may be subject to adversarial attacks that
corrupt data points and can significantly impact the performance of the
learning process. Such security threats have already been explored in single-
agent RL, where prior work has proposed corruption robust algorithms (Zhang et
al., 2022). However, these results do not directly translate to MARL due to
the intricacies of multi-agent settings. For instance, the learning objective
in these settings requires a more complex solution concept of learning a Nash
Equilibrium (NE) policy pair for agents instead of simply learning a near-
optimal policy for an agent. In this work, we initiate the study of corruption
robust algorithms for learning equilibrium policies in offline MARL. More
specifically, we focus on two-agent zero-sum Markov games and consider the
following research question:

Can we design algorithms that approximately solve offline two-player zero-sum
Markov games under data corruption?

To effectively answer this question, we need to account for another crucial
factor in offline learning, that is, the quality of the collected data, which
drastically affects the quality of the learned policy. It is thus common
practice to assume that the collected data covers at least some trajectories
of interest. It turns out that the necessary coverage assumptions for solving
the offline single-player problem are not enough to solve the offline two-
player problem (see Figure 1). Thus, stronger assumptions are required, i.e.,
the so-called Low Relative Uncertainty (LRU) assumption. This problem is
exacerbated by the presence of corruption in our setting. If good coverage in
the clean setting seems natural, supposing that the data has been collected by
a good enough policy, such an assumption is no longer guaranteed when a
potentially malicious adversary intervenes in the data.

Coverage | Covariates | Algorithm | Suboptimality Gap | Result
---|---|---|---|---
Uniform $\Sigma$ on corrupted data | Corrupted | R-PMVI | $\widetilde{O}\Bigl{(}H^{2}d\epsilon+H^{3/2}f(d)K^{-1/2}\Bigr{)}$ | [Theorem 2]
LRU on corrupted data | Clean | S-PMVI | $\widetilde{O}\Bigl{(}H^{2}d\epsilon+H^{2}K^{-1/2}d^{3/2}\Bigr{)}$ | [Theorem 3]
LRU on clean data | Corrupted | S-PMVI | $\widetilde{O}\Bigl{(}H^{2}d^{3/2}\sqrt{\epsilon}+H^{2}K^{-1/2}d^{3/2}\Bigr{)}$ | [Theorem 4]
LRU on clean data & A.4 | Corrupted | S-PMVI | $\widetilde{O}\Bigl{(}H^{2}d^{3}\epsilon+H^{2}K^{-1/2}d^{3}\Bigr{)}$ | [Theorem 5]

Table 1: Summary of our results under Low Relative Uncertainty and uniform
$\Sigma$-coverage assumptions (see Assumptions 2 and 3 for definitions) on
clean or corrupted data, and different corruption levels of the feature
covariance matrix. Here $\epsilon$ denotes the corruption level, $K$ denotes
the number of trajectories contained in the data, and $f(x)$ denotes a
polynomial function of $x$. The Covariates column refers to whether the state-
action part of the data tuple is corrupted or not. We have omitted linear
dependence on noise variance $\gamma^{2}$ of the rewards for ease of
presentation. We point the reader to the relevant results for a detailed
description. We note that the universal lower bound for the offline two-player
zero-sum MG setting is $\Omega(Hd\epsilon)$.

Motivated by these observations, we study the problem of corruption in the
offline two-player setting under various assumptions. First, we tackle
corruption under the minimal LRU coverage and the more relaxed uniform
$\Sigma$-coverage (defined in Assumption 2) assumptions on the corrupted data.
Furthermore, we also consider the more difficult setting where the minimal LRU
coverage holds only on the clean dataset. We build upon recent techniques for
the offline two-player zero-sum setting (Zhong et al., 2022) and propose
robust versions of their method. We tackle the corruption problem by using two
setting-specific robust estimators and carefully designing new bonus terms
that capture the additional estimation errors coming from corruption. More
concretely, our main results and contributions are summarized below (also, see
Table 1):

  1. I.

Lower bound. First, we formulate the problem of data corruption in offline
two-player zero-sum Markov games. We prove an information-theoretic lower
bound of $\Omega(Hd\epsilon)$ on the suboptimality gap of any algorithm that
uses a corrupted dataset where $H$ is the episode length, $d$ is the
dimension, and $\epsilon$ is the corruption level.

  2. II.

Uniform $\Sigma$ and corrupted covariates. Next, we consider the corruption
problem under the Uniform $\Sigma$-coverage assumption on the corrupted data.
We propose R-PMVI that uses a Robust Least Squares estimator (Zhang et al.,
2022) and show that it incurs a near-optimal bound on the error coming from
corruption with high probability, showing an improvement on the single-player
bounds of Zhang et al. (2022) by a factor of $H$.

  3. III.

LRU and clean covariates. Furthermore, we consider the LRU coverage on the
corrupted data. We additionally assume that corruption is done only on the
reward and next state part of the data tuples, i.e., assuming clean
covariates. In this setting, we propose S-PMVI that uses the Spectrally
Regularized Alternating Minimization algorithm (Chen et al., 2022a) oracle as
a robust estimator and provide a high probability near-optimal bound on its
suboptimality gap. We note that, under no corruption, we recover the SOTA
bounds of Zhong et al. (2022), while obtaining similar rates of $\epsilon$ as
in the single agent SOTA (Zhang et al., 2022).

  4. IV.

LRU on the clean data. Finally, we consider the most restrictive setting where
no guarantees of coverage on the corrupted data are given but only make the
necessary LRU assumption on the clean data. In this setting, we propose a new
bonus term for the S-PMVI algorithm, that takes into account the additional
error terms. Our method yields $O(d^{3/2}\sqrt{\epsilon})$ bounds on the
suboptimality gap, similar to the single-player setting. Moreover, under an
additional mild assumption on the feature space, we are able to recover the
optimal $O(\epsilon)$ rate, at the cost of an additional $O(d^{3/2})$ factor.

Furthermore, we observe that convergence to Nash equilibria, without knowledge
of $\epsilon$ and uniform coverage, is impossible in the offline two-player
setting, which is a direct implication of the single-player setting (Zhang et
al., 2022). Finally, we provide a comprehensive discussion on the relationship
between used coverage assumptions and other similar assumptions found in the
offline MARL literature and position them relative to each other.

###  2 PRELIMINARIES

Notation. We begin this section by introducing the notation to be used
throughout the paper. As usual, $I$ denotes the identity matrix,
$\left\lVert\cdot\right\rVert_{2}$ denotes the Euclidean norm,
$\left\lVert\cdot\right\rVert_{A}$ denotes the Mahalanobis norm given square
matrix $A$, and $\Delta(\mathcal{X})$ denotes the probability simplex on set
$\mathcal{X}$. When $\widetilde{O}$ is used, any polylogarithmic terms are
omitted. Furthermore, $[H]$ denotes the set of natural numbers up to and
including $H$, $\langle\cdot,\cdot\rangle$ denotes the inner product,
$\mathbf{1}\\{\cdot\\}$ denotes the indicator function, and $\succeq$ denotes
the Loewner order, where $A\succeq B$ is equivalent to $A-B$ being positive
semi-definite. Finally, we define $\Pi_{h}(x)=\min\\{h,\max\\{x,0\\}\\}$.

####  2.1 Two-player Zero-sum Markov Games

Let $\mathcal{G}=(\mathcal{S},\mathcal{A},\mathcal{B},p,r,H)$ be a finite-
horizon zero-sum Markov game between two players, one of which is trying to
maximize the total reward and the other is trying to minimize it. Here
$\mathcal{S}$ denotes the state space with $S$ states111We only introduce the
state space cardinality notation for convenience. Note that in linear Markov
games, $S$ may be intractably large., $\mathcal{A}$ is the action space of the
first player with $A$ actions, $\mathcal{B}$ is the action space of the second
player with $B$ actions, $p=(p_{1},\ldots,p_{H})$ where
$p_{h}\in\mathbb{R}^{SAB\times S}$ $\forall h\in[H]$ denote the transition
kernels, $r=(r_{1},\ldots,r_{H})$ where $r_{h}\in\Delta(\mathbb{R})^{SAB}$
$\forall h\in[H]$ are $\gamma^{2}$-subGaussian rewards, and $H$ is the horizon
length. At each time step $h$ and state $s_{h}$ the $\max$ player selects
action $a_{h}\in\mathcal{A}$ and the $\min$ player selects action
$b_{h}\in\mathcal{B}$ and both observe reward $r_{h}(s_{h},a_{h},b_{h})$.
Then, the next state $s_{h+1}$ is sampled from
$p_{h}(\cdot|s_{h},a_{h},b_{h})$.

A strategy pair $(\pi,\nu)$ is comprised of the strategy of the first player
$\pi=(\pi_{1},\ldots,\pi_{H})$,
$\pi_{h}:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ $\forall h\in[H]$ and that
of the second player $\nu=(\nu_{1},\ldots,\nu_{H})$,
$\nu_{h}:\mathcal{S}\rightarrow\Delta(\mathcal{B})$ $\forall h\in[H]$. Given
$h\in[H]$, we define the state-value function and state-action value function
as

$\displaystyle V^{\pi,\nu}_{h}(s_{h})$
$\displaystyle=\mathbb{E}\left[\sum^{H}_{t=h}r_{h}(s_{t},a_{t},b_{t})|\pi,\nu,s_{h}\right]~{},$
$\displaystyle Q^{\pi,\nu}_{h}(s_{h},a_{h},b_{h})$
$\displaystyle=\mathbb{E}\left[\sum^{H}_{t=h}r_{h}(s_{t},a_{t},b_{t})|\pi,\nu,s_{h},a_{h},b_{h}\right]~{}.$

####  2.2 Nash Equilibria and Performance Metrics

Let $\nu$ be a fixed strategy of the second player. Then, an optimal policy
with respect to the MDP induced by $\nu$ is called the best response of the
first player and we denote it by $\text{br}(\nu)$. Similarly, for a fixed
strategy $\pi$ of the first player, the best response of the second player is
denoted by $\text{br}(\pi)$. Further, for any $\pi$, $\nu$ and $h\leq H$, we
define

$\displaystyle V^{\pi,*}_{h}(s_{h})$
$\displaystyle=V^{\pi,\text{br}(\pi)}_{h}(s_{h})=\inf_{\nu}V^{\pi,\nu}_{h}(s_{h})~{},$
$\displaystyle V^{*,\nu}_{h}(s_{h})$
$\displaystyle=V^{\text{br}(\nu),\nu}_{h}(s_{h})=\sup_{\mu}V^{\mu,\nu}_{h}(s_{h})~{}.$

######  Definition 1.

A Nash Equilibrium (NE) is a strategy pair $(\pi^{*},\nu^{*})$ such that, for
all $h\in[H]$ and $s\in\mathcal{S}$:

$\displaystyle\sup_{\pi}\inf_{\nu}V^{\pi,\nu}_{h}(s)=V^{\pi^{*},\nu^{*}}_{h}(s)=\inf_{\nu}\sup_{\pi}V^{\pi,\nu}_{h}(s)~{}.$

It is well-known that the NE of a zero-sum Markov game with a unique value
function exists (Shapley, 1953). We define
$V^{*}_{h}(s_{h})=V^{\pi^{*},\nu^{*}}_{h}(s_{h})$, for all $h\leq H$. Then,
for all strategy pairs $(\pi,\nu)$, the weak duality is written as
$V^{\pi,*}_{h}(s_{h})\leq V^{*}_{h}(s_{h})\leq V^{*,\nu}_{h}(s_{h}),\forall
h\leq H$. Consequently, the suboptimality gap of $(\pi,\nu)$ is

$\displaystyle\text{SubOpt}(\pi,\nu,s)=V^{*,\nu}_{1}(s)-V^{\pi,*}_{1}(s)~{}.$

Note that the duality is always non-negative, and it is zero only when
$(\pi,\nu)$ is a NE strategy. We say that a strategy $(\pi,\nu)$ is a
$\eta$-approximate NE if we have $\text{SubOpt}(\pi,\nu,s)\leq\eta$ for all
$s\in\mathcal{S}$.

####  2.3 Linear Markov Games

We consider linear two-player zero-sum Markov games
$\mathcal{G}=(\mathcal{S},\mathcal{A},\mathcal{B},p,r,H)$. Here, we formally
state the linearity assumption for Markov games, standard in the literature
(Xie et al., 2020).

######  Definition 2 (Linear Markov games).

For each $(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$ we have

$\displaystyle r_{h}(s,a,b)$
$\displaystyle=\phi(s,a,b)^{\top}\theta_{h}+\zeta\;\;\text{and}$
$\displaystyle p_{h}(\cdot|s,a,b)$
$\displaystyle=\phi(s,a,b)^{\top}\mu_{h}(\cdot)~{},$

where
$\phi:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow\mathbb{R}^{d}$
is a known feature map, $\theta_{h}\in\mathbb{R}^{d}$ is an unknown vector,
$\zeta$ is zero-mean $\gamma^{2}$-subGaussian noise, and
$\mu_{h}=(\mu^{(i)}_{h})_{i\in[d]}$ is a vector of $d$ unknown signed measures
on $\mathcal{S}$. We assume that
$\left\lVert\phi(\cdot,\cdot,\cdot)\right\rVert_{2}\leq 1$,
$\left\lVert\theta_{h}\right\rVert_{2}\leq\sqrt{d}$, and
$\left\lVert\mu_{h}(\mathcal{S})\right\rVert_{2}\leq\sqrt{d}$ for all
$h\in[H]$.

As previously observed (Zhong et al., 2022), given a policy pair $(\pi,\nu)$
and time-step $h$, there exists a $d$-dimensional weight vector
$\omega^{\pi,\nu}_{h}$, with
$\left\lVert\omega^{\pi,\nu}_{h}\right\rVert_{2}\leq H\sqrt{d}$, such that
$Q^{\pi,\nu}_{h}(s,a,b)=\phi(s,a,b)^{\top}\omega^{\pi,\nu}_{h}$ for any
$(s,a,b)$ tuple.

####  2.4 Offline Data Collection

In offline RL, the objective is to learn an optimal policy from data that has
already been collected beforehand (Levine et al., 2020). Similarly, in offline
Markov Games, the objective is to learn an approximate NE strategy based on a
given dataset. Formally, we are given a dataset
$D=\\{(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h},r^{\tau}_{h},s^{\tau}_{h+1})\\}^{\tau\in[K]}_{h\in[H]}$
of $K$ trajectories, gathered from a behavioral policy
$\rho=(\rho_{1},\ldots,\rho_{H}),\rho_{h}:\mathcal{S}\rightarrow\Delta(\mathcal{A}\times\mathcal{B})$,
$\forall h\in[H]$.222The behavioral policy can be thought of as a product of a
$\min$ and $\max$ policy.

Given $h\in[H]$, a strategy pair $(\pi,\nu)$, and a tuple $(s,a,b)$, we denote
by $d^{\pi,\nu}_{h}(s,a,b)$ the probability that the state-action tuple
$(s,a,b)$ is traversed in time step $h$ by $(\pi,\nu)$, i.e.,
$d^{\pi,\nu}_{h}(s,a,b)=\mathbb{P}\left(s_{h}=s,a_{h}=a,b_{h}=b|\pi,\nu\right)$.
If $d^{\pi,\nu}_{h}(s,a,b)>0$, for all $h\in[H]$, we say that state-action
tuple $(s,a,b)$ is covered by policy pair $(\pi,\nu)$.

Next, we formally define the compliance of a given offline dataset with an
underlying Markov game, which basically implies that the clean collected data
follows the same dynamics as the environment. We will assume later on that the
clean dataset is in compliance with the underlying Markov game.

######  Definition 3 (Compliance of dataset).

Given a Markov game $\mathcal{G}=(\mathcal{S},\mathcal{A},\mathcal{B},p,r,H)$
and a dataset
$D=\\{(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h},r^{\tau}_{h},s^{\tau}_{h+1})\\}^{\tau\in[K]}_{h\in[H]}~{},$
we say the dataset $D$ is compliant with $\mathcal{G}$ if, for all $h\in[H]$
and $s\in\mathcal{S}$,

$\displaystyle\mathbb{P}$
$\displaystyle\left(r^{\tau}_{h}=r,s^{\tau}_{h+1}=s|\\{(s^{i}_{h},a^{i}_{h},b^{i}_{h})\\}^{\tau}_{i=1},\\{(r^{i}_{h},s^{i}_{h+1})\\}^{\tau-1}_{i=1}\right)$
$\displaystyle=\mathbb{P}_{h}\left(r_{h}=r,s_{h+1}=s|s_{h}=s^{\tau}_{h},a_{h}=a^{\tau}_{h},b_{h}=b^{\tau}_{h}\right)~{},$

where $\mathbb{P}$ is with respect to $D$ and $\mathbb{P}_{h}$ is the
probability measure taken with respect to the underlying Markov game
$\mathcal{G}$.

####  2.5 Corruption Robust Estimation

The standard assumption in statistical estimation is that the samples we are
given come from a fixed distribution, allowing one to directly use probability
laws to obtain unbiased estimates of interest. However, it is usually the case
that outliers are present in the data that do not belong to the underlying
distribution, or that an adversary can arbitrarily corrupt the data. Only one
outlier is enough to arbitrarily shift the empirical mean of the data, and
therefore acquiring robust estimators for the moments of the distribution is
important. We will use the Huber contamination model, akin to the corruption
model in single-player offline RL (Zhang et al., 2022).

######  Assumption 1 ($\epsilon$-contamination in offline Markov games).

Given $\epsilon\in[0,1]$ and a set of clean tuples
$\widetilde{D}=\\{(\widetilde{s}_{i},\widetilde{a}_{i},\widetilde{b}_{i},\widetilde{r}_{i},\widetilde{s}^{\prime}_{i})\\}^{N}_{i=1}$,
an adversary is allowed to inspect the tuples and replace any $\epsilon N$ of
them with arbitrary contaminated tuples
$(s,a,b,r,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times\mathcal{R}\times\mathcal{S}$.
The resulting set $D=\\{(s_{i},a_{i},b_{i},r_{i},s^{\prime}_{i})\\}^{N}_{i=1}$
is then revealed to the learner.

We say that a set of samples is $\epsilon$-corrupted if it is generated by the
above process. Given an $\epsilon$-corrupted set of data points, the goal of
robust statistics is to compute accurate estimates of the first and second
moments. In (Diakonikolas et al., 2017), the authors provide efficient and
nearly sample-optimal filtering algorithms for mean and covariance estimation.

For the linear regression problem, different robust estimators require
different coverage assumptions. For instance, SCRAM (Chen et al., 2022a) does
not make strong coverage assumptions but assumes clean covariates, while
Robust Least Squares (RLS) (Bakshi and Prasad, 2021; Pensia et al., 2020;
Zhang et al., 2022) needs stronger coverage while allowing for corrupted
covariates. We will use both aforementioned methods as robust estimator
oracles under different coverage assumptions and corruption models.

###  3 PROBLEM FORMULATION

We assume that an unknown experimenter collects a dataset $\widetilde{D}=$
$\\{(\tilde{s}^{\tau}_{h},\tilde{a}^{\tau}_{h},\tilde{b}^{\tau}_{h},\tilde{r}^{\tau}_{h},\tilde{s}^{\tau}_{h+1})\\}^{K,H}_{\tau=1,h=1}$of
$K$ trajectories, in compliance with $\mathcal{G}$. We assume that
$\\{(\tilde{s}^{\tau}_{h},\tilde{a}^{\tau}_{h},\tilde{b}^{\tau}_{h},\tilde{r}^{\tau}_{h},\tilde{s}^{\tau}_{h+1})\\}^{K,H}_{\tau=1,h=1}$is
collected from behavioral policy $\rho=(\rho^{1},\rho^{2})$. Formally, for any
$h\in[H]$, we have
$(\widetilde{s}_{h},\widetilde{a}_{h},\widetilde{b}_{h})\sim d^{\rho}_{h}$ and
$\widetilde{s}_{h+1}\sim
p_{h}(\cdot|\widetilde{s}_{h},\widetilde{a}_{h},\widetilde{b}_{h})$ for any
$(\widetilde{s}_{h},\widetilde{a}_{h},\widetilde{b}_{h},\widetilde{r}_{h},\widetilde{s}_{h+1})\in\widetilde{D}$.
Subsequently, an adversary contaminates an $\epsilon$-fraction of all tuples
of $\widetilde{D}$ and provides us with the corrupted dataset
$D=$$\\{(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h},r^{\tau}_{h},s^{\tau}_{h+1})\\}^{K,H}_{\tau=1,h=1}$.

The learner’s objective is, given access to an $\epsilon$-corrupted dataset
$D$, to be able to compute an approximate Nash equilibrium policy pair. In the
clean offline setting, this is usually done by leveraging pessimism in order
to penalize samples that were not sufficiently covered. However, if the
dataset does not cover state actions of interest, i.e., those traversed by
equilibrium policies, then learning becomes impossible, even in the clean
setting. First, we formally define what we mean by coverage.

######  Definition 4.

A strategy pair $(\pi,\nu)$ is covered by the dataset generated by behavioral
policy $\rho$ if and only if every tuple $(s,a,b)$ that is covered by
$(\pi,\nu)$ is also covered by $\rho$. In other words, we have

$\displaystyle\frac{d^{\pi,\nu}_{h}(s,a,b)}{d^{\rho}_{h}(s,a,b)}<\infty,\forall(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B},h\in[H]~{}.$

For the offline single-player setting, it has been established that coverage
of the optimal (or any target policy used as reference) policy is necessary to
achieve convergence. For the two-player zero-sum Markov game setting, Zhong et
al. (2022) show that coverage of a Nash equilibrium policy pair and its
neighbors across each player is necessary for learning, as we will see in the
next section.333Formal definitions are given in the next section. We will
consider the corruption problem under different coverage assumptions, starting
from strong assumptions on the corrupted data, and ending with the setting
where minimal coverage assumptions hold only on the clean dataset.

###  4 RESULTS UNDER COVERAGE ON CORRUPTED DATA

Recall from Section 2.3 that, given $(\pi,\nu)$,
$(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$, and $h\in[H]$,
Definition 2 implies that
$Q^{\pi,\nu}_{h}(s,a,b)=\phi(s,a,b)^{\top}\omega^{\pi,\nu}_{h}$, for some
$\omega^{\pi,\nu}_{h}\in\mathbb{R}^{d}$. Thus, learning the action value
function $Q^{*}_{h}$ that corresponds to a Nash equilibrium (NE) pair reduces
to learning the optimal weights, which we denote by $\omega^{*}_{h}$. For
that, we will rely on Pessimistic Minimax Value Iteration (PMVI) (Zhong et
al., 2022), which computes an approximate NE pair using offline data. However,
PMVI computes estimates of $\omega^{*}_{h}$ by solving regularized least-
squares on the Bellman operator. We cannot directly use those estimates since
our data contains corrupted samples. Instead, we use a robust estimator to
tackle the corruption problem. Let R-EST denote a generic robust estimator.

First, we randomly split the data into $H$ batches $D_{h}$ and set
$\underline{V}_{H+1}(\cdot)=\overline{V}_{H+1}(\cdot)=0$. Then, for each time
step $h=H,H-1,\ldots,1$, we obtain

$\displaystyle\underline{\omega}_{h}$
$\displaystyle\leftarrow\textrm{R-EST}\Bigl{(}\\{\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}),r^{\tau}_{h}+\underline{V}_{h+1}(s^{\tau}_{h+1})\\}^{K}_{\tau=1}\Bigr{)}~{},$
$\displaystyle\overline{\omega}_{h}$
$\displaystyle\leftarrow\textrm{R-EST}\Bigl{(}\\{\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}),r^{\tau}_{h}+\overline{V}_{h+1}(s^{\tau}_{h+1})\\}^{K}_{\tau=1}\Bigr{)}~{}.$

Once we have estimates of the optimal weights, the algorithm proceeds to
construct estimates of the $Q$-values for both players, which depend on
carefully constructed bonus terms $\Gamma_{h}$ – we provide different bonus
terms depending on the robust estimators we use and other characteristics of
corruption.

Next, we compute a Nash equilibrium corresponding to payoffs
$\underline{Q}(\cdot,\cdot,\cdot)$ and $\overline{Q}(\cdot,\cdot,\cdot)$, and
obtain $(\widehat{\pi}_{h},\nu^{\prime}_{h})$ and
$(\pi^{\prime},\widehat{\nu}_{h})$, as solutions corresponding to
$\underline{Q}(\cdot,\cdot,\cdot)$ and $\overline{Q}(\cdot,\cdot,\cdot)$,
respectively.

Finally, the algorithm estimates the value functions for both players based on
the computed policy pairs. After $H$ steps, the algorithm terminates and
outputs the estimated pairs of strategies $(\widehat{\pi},\widehat{\nu})$. The
pseudocode of the described method is given in Algorithm 1.

Algorithm 1 Robust PMVI

1:Input: Dataset $D$, failure probability $\delta$, robust estimator R-EST,
bonus functions $\Gamma_{h}(\cdot,\cdot,\cdot)$.

2:Initialize: Randomly split dataset $D$ into $H$ subsets $D_{h}$ of
cardinality $K$; set $\underline{V}_{H+1}(s)=\overline{V}_{H+1}(s)=0$, for all
$s\in\mathcal{S}$.

3:for $h=H,H-1,\ldots,1$ do:

4: Compute estimates $\underline{\omega}_{h}$ and $\overline{\omega}_{h}$ via
R-EST.

5:
$\underline{Q}_{h}(\cdot,\cdot,\cdot)\leftarrow\Pi_{H-h+1}\left(\phi(\cdot,\cdot,\cdot)^{\top}\underline{\omega}_{h}-\Gamma_{h}(\cdot,\cdot,\cdot)\right)$.

6:
$\overline{Q}_{h}(\cdot,\cdot,\cdot)\leftarrow\Pi_{H-h+1}\left(\phi(\cdot,\cdot,\cdot)^{\top}\underline{\omega}_{h}+\Gamma_{h}(\cdot,\cdot,\cdot)\right)$.

7: Compute $(\widehat{\pi}_{h},\nu^{\prime}_{h})$ and
$(\pi^{\prime}_{h},\widehat{\nu}_{h})$ as NE solutions to
$\underline{Q}_{h}(\cdot,\cdot,\cdot)$ and
$\overline{Q}_{h}(\cdot,\cdot,\cdot)$, respectively.

8:
$\underline{V}_{h}(\cdot)\leftarrow\mathbb{E}_{a\sim\widehat{\pi}_{h},b\sim\nu^{\prime}_{h}}[\underline{Q}_{h}(\cdot,a,b)]$.

9:
$\overline{V}_{h}(\cdot)\leftarrow\mathbb{E}_{a\sim\pi^{\prime}_{h},b\sim\widehat{\nu}_{h}}[\overline{Q}_{h}(\cdot,a,b)]$.

10:end for

11:Output:
$\widehat{\pi}=(\widehat{\pi}_{h})^{H}_{h=1},\widehat{\nu}=(\widehat{\nu}_{h})^{H}_{h=1}$.

In the following sections, we will introduce different estimators that compute
the Bellman operator weights under different coverage assumptions. Depending
on which estimator we use, we also get the corresponding convergence
guarantees. Intuitively, the error of estimating the Bellman operator is
inflated by an extra term coming from data corruption. To have a sense of the
strength of such guarantees in terms of $\epsilon$, we now present our first
contribution, a result that states an algorithm-independent minimax lower
bound for the corruption problem in the offline two-player zero-sum setting.

######  Theorem 1.

For every algorithm $L$, there exists a Markov game $\mathcal{G}$, an instance
of the corrupted dataset, corruption level $\epsilon$, and a data collecting
distribution $\rho$, such that, with probability at least $1/4$, $L$ will find
a no-better than $\Omega(Hd\epsilon)$-approximate NE policy pair
$(\widetilde{\pi},\widetilde{\nu})$. That is, with a probability of at least
$1/4$, we have, for every $s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widetilde{\pi},\widetilde{\nu},s)=\Omega(Hd\epsilon)~{}.$

####  4.1 Uniform $\Sigma$-Coverage and Corrupted Covariates

We start by considering the strongest coverage assumption first. Throughout
Section 4.1, we assume that the corrupted data $D$ satisfies the following.

######  Assumption 2 (Uniform $\Sigma$-coverage).

For all $h\in[H]$ and $s\in\mathcal{S}$,
$\mathbb{E}_{\rho}\left[\Sigma_{h}|s_{1}=s\right]\succeq\kappa I$ for some
$\kappa>0$, where
$\Sigma_{h}=\phi(s_{h},a_{h},b_{h})\phi(s_{h},a_{h},b_{h})^{\top}$.

Assumption 2 implies that every state-action tuple in the support of the
behavioral policy $\rho$ is covered by the offline data. In Section 6 we
further discuss the strength of this assumption relative to other coverage
assumptions studied in the literature.

Inspired by the Robust Value Iteration algorithm (Zhang et al., 2022) that
uses a Robust Least Squares (RLS) oracle as a subroutine for estimating the
weights of the value function, we propose RLS-PMVI, which uses a similar
oracle that relies on Assumption 2. However, it allows for an arbitrary
corruption model, where an $\epsilon$-fraction of the dataset can be
arbitrarily corrupted, that is, any component of the data samples can be
modified arbitrarily. RLS-PMVI returns an approximate NE policy pair that
incurs the following bounds on the gap.

######  Theorem 2.

Suppose that Assumption 2 holds on an $\epsilon$-corrupted dataset $D$
corresponding to a linear Markov game. Then, given $\delta>0$, with
probability at least $1-\delta$, RLS-PMVI with bonus term
$\Gamma_{h}(s,a,b)=0$ achieves suboptimality gap upper bounded by

$\displaystyle\widetilde{O}\left(\sqrt{\frac{H(H+\gamma)^{2}poly(d)}{\kappa^{2}K}}+\frac{H(H+\gamma)}{\kappa}\epsilon\right)~{}.$

The proof of Theorem 2 is based on similar ideas to those used in the single-
player setting. We provide the full proof in Appendix for completion. The
following remarks are in order.

######  Remark 1.

Note that the order of $\epsilon$ is optimal. Furthermore, since the bonus
term is $0$, the algorithm does not require knowledge of $\epsilon$. Thus, if
we have uniform coverage, under a stricter corruption model, i.e., the
features can also be corrupted, and without knowledge of $\epsilon$, RLS-PMVI
incurs a suboptimality gap with optimal dependence on $\epsilon$.

######  Remark 2.

Note that the coverage constant $\kappa$ is in the order of $1/d$, since
$\left\lVert\phi\right\rVert_{2}\leq 1$. Thus, the bound corresponding to the
corruption error becomes $O(H^{2}d\epsilon)$.

####  4.2 LRU Coverage and Clean Covariates

As mentioned in the previous section, Assumption 2 is a very strong
requirement to make on the data. Thus, we now focus our attention on a relaxed
scenario, where the observed data covers only policies of interest. In the
two-player zero-sum setting, it turns out that coverage of the NE policy pair
alone is not enough to efficiently compute an approximate solution. We state
such an assumption below. Given dataset $\mathcal{D}$ of $K$ trajectories, let
us denote by

$\displaystyle\Lambda_{h}=\sum^{K}_{\tau=1}\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})^{\top}+I$
(1)

the regularized sample covariance with respect to $\mathcal{D}$.

######  Assumption 3 (Low relative uncertainty).

There exists a constant $c_{1}>0$ such that, for all $x\in\mathcal{S}$:

$\displaystyle\Lambda_{h}\succeq I+c_{1}K$
$\displaystyle\max\left\\{\sup_{\nu}\;\mathbb{E}_{\pi^{*},\nu}[\phi_{h}\phi_{h}^{\top}|s_{1}=x],\right.$
$\displaystyle\quad\quad\left.\sup_{\pi}\;\mathbb{E}_{\pi,\nu^{*}}[\phi_{h}\phi_{h}^{\top}|s_{1}=x]\right\\}~{},$

where $\phi_{h}=\phi(s_{h},a_{h},b_{h})$, for any $h\in[H]$.

As shown in (Zhong et al., 2022) (and (Cui and Du, 2022) for tabular
settings), Assumption 3 (and Assumption 6 for tabular settings444See Section
6.) is necessary for learning NE policies in two-player settings. Thus, the
focus of Section 4.2 will be on data that satisfies such an assumption. An
immediate problem that naturally follows is choosing the right robust
estimator. The RLS estimator, described in the previous section, provides nice
guarantees but it relies on Assumption 2. If we are to assume only LRU
coverage on the data, then we need a different estimator.

To that end, we utilize a result by Chen et al. (2022a) that does not require
Assumption 2 to hold. Their algorithm, SCRAM, utilizes an alternating
minimization scheme to compute first-order stationary points. However, the
utilization of such an oracle relies on the assumption that the covariates of
the dataset are not corrupted. Translated into our setting, this assumption
requires the features $\phi(s,a,b)$, and, as a consequence, tuples $(s,a,b)\in
D$ to be clean, i.e., only an $\epsilon$-fraction of the rewards and the next
states are allowed to be arbitrarily corrupted. Below, we state the conditions
of SCRAM and its guarantee. A detailed version can be found in Appendix.

######  Lemma 1 (Chen et al. (2022a)).

Given a dataset $D=\\{x_{i},y_{i}\\}_{i\in[K]}$, which is an
$\epsilon$-corrupted version of dataset
$\widetilde{D}=\\{x_{i},\widetilde{y}_{i}\\}$, where
$\widetilde{y}_{i}=\langle\omega^{*}_{i},x_{i}\rangle+\xi_{i}$,
$\epsilon<0.499$, $\left\lVert x_{i}\right\rVert_{2}\leq 1$ and $\xi_{i}$ are
conditionally zero-mean $\gamma^{2}$ sub-Gaussian, then SCRAM returns
estimators $(\omega_{k})_{k\in[K]}$, such that

$\displaystyle\left\lVert\omega-\omega^{*}\right\rVert_{\Sigma}\leq
O(\epsilon\gamma+\gamma d^{1/2}K^{-1/4})~{},$ (2)

omitting poly-log factors, where $\Sigma=(1/K)\sum^{K}_{k=1}x_{k}x^{\top}_{k}$
is the sample covariance.555For explicit bounds, see Appendix.

In Section 4.2, we use SCRAM as a robust estimator with bonus term defined as

$\displaystyle\Gamma_{h}(s,a,b)=\left(\sqrt{K}\mathcal{E}+2H\sqrt{d}\right)\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}~{},$

where $\Lambda_{h}$ is defined in Equation 1 and $\mathcal{E}$ denotes the
upper bound in Equation (2).

We are now ready to state the main result of Section 4.2, which gives an upper
bound on the suboptimality gap of the policy pair returned by SCRAM-PMVI.

######  Theorem 3.

Suppose that Assumption 3 holds with given constant $c_{1}$. Let $\delta>0$,
$\epsilon<1/2$ and let $D$ be the $\epsilon$-corrupted version of the dataset
$\widetilde{D}$ comprised of $K$ trajectories of length $H$, where
$K\geq\log(\min(K,d))/\epsilon$ and
$(\widetilde{s}^{\tau}_{h},\widetilde{a}^{\tau}_{h},\widetilde{b}^{\tau}_{h})=(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$,
for all $\tau\in[K]$, $h\in[H]$. Then, with probability at least $1-\delta$,
SCRAM-PMVI outputs $(\widehat{\pi},\widehat{\nu})$ that satisfy, for every
$s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)$
$\displaystyle\leq\widetilde{O}\left(\frac{1}{\sqrt{c_{1}}}(\gamma+H)H\sqrt{d}\epsilon+\frac{H^{2}d}{\sqrt{c_{1}K}}\right)~{}.$

Note the $\sqrt{d}$ factor in the term coming from the corruption error. This
might seem contradictory to our lower bound of Theorem 1 at first. However,
there is a hidden dependence on $d$ in the $c_{1}$ constant, since $c_{1}$
cannot be arbitrarily large. By Assumption 3, first one can easily see that
$0<c_{1}\leq 1$. Moreover, as shown in the proof of Proposition 1 (see
Appendix), $c_{1}$ can be $O(1/d)$, in which case the bounds would be written
as

$\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)\leq\widetilde{O}\left((\gamma+H)Hd\epsilon+H^{2}d^{3/2}K^{-1/2}\right).$

Note that one can always construct other examples in which the dependence of
the gap on $d$ is looser. However, here we are interested in showing that
there is an explicit dependence in order to confirm the matching order.

It is worth mentioning that knowledge of $\epsilon$ is required by both SCRAM
and RLS oracles. Moreover, agnostic learning without knowledge of $\epsilon$
is impossible for linear Markov games, without uniform data coverage, as the
next result shows. The proof follows immediately from that of Theorem 3.4 of
(Zhang et al., 2022), by restricting the second player’s action space to a
single action and observing that the LRU coverage reduces to their finite
relative condition number assumption.

######  Corollary 1.

Under Assumption 3, for every algorithm $L$ that achieves a diminishing
suboptimality gap in a clean environment, there exist linear Markov games
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, an instance of corrupted data, and a
data collecting distribution $\rho$, such that, for every
$\epsilon\in(0,1/2]$, $L$ achieves
$\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)\geq 1/2$, for any
$s\in\mathcal{S}$, with probability at least $1/4$, on at least one of the
games.

With this result, we end our discussion under corrupted data coverage
assumptions. In order to give a formal characterization of the used coverage
assumptions and other similar ones in the literature, we provide a formal
discussion in Section 6. In the next section, we turn our attention to the
more difficult setting where coverage guarantees are no longer present in the
corrupted data and provide near-optimal bounds on the suboptimality of SCRAM-
PMVI with novel bonus terms designed to account for this corrupted coverage.

###  5 RESULTS UNDER COVERAGE ON CLEAN DATA

In previous sections, we considered the problem of corruption in the linear
setting, under the assumption that the corrupted data preserves the coverage
that is necessary to solve the underlying Markov game. However, this might be
too restrictive of an assumption since, in the worst case, the attacker would
corrupt precisely those state-action tuples that belong to trajectories
covered by LRU policies. Thus, the next natural question is whether we can
approximately solve the problem given that we are not guaranteed that the
available corrupted data satisfies the LRU coverage assumption.

Apart from not assuming any guarantees on coverage, we also assume fully
arbitrary corruption, in the sense that the attacker can arbitrarily corrupt
an $\epsilon$-fraction of both covariates and observations. If we are to apply
SCRAM in this setting, we would expect an additional error coming from the
corruption of covariates, and another one coming from the corrupted coverage.

We find that by carefully designing a bonus term that also takes into account
these two additional errors, we are able to approximately solve the corruption
robust offline two-player zero-sum game, as the following result states.

######  Theorem 4.

Suppose that the condition of Assumption 3 is satisfied only on the clean
dataset $\widetilde{D}$, for a given constant $c_{1}$, that is, assume that
the clean sample covariance matrix
$\sum^{K}_{\tau=1}\widetilde{\phi}^{\tau}_{h}(\widetilde{\phi}^{\tau}_{h})^{\top}+I,$
where $\widetilde{\phi}^{\tau}_{h}$ denotes the clean feature of the sample at
time-step $h$ of episode $\tau$, satisfies Assumption 3. Furthermore, let
$\delta>0$, $\epsilon\in(0,1/2)$, and $K\geq\log(\min\\{K,d\\})/\epsilon$.
Then, under Assumption 1, with probability at least $1-\delta$, SCRAM-PMVI
with bonus defined as

$\displaystyle\Gamma_{h}(\cdot)=\left(\sqrt{(1-\epsilon)K}\mathcal{E}+(\sqrt{\epsilon
K}+2)H\sqrt{d}\right)\left\lVert\phi(\cdot)\right\rVert_{\Lambda^{-1}_{h}}$

returns $(\widehat{\pi},\widehat{\nu})$ that satisfy, for every
$s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)\leq
O\left(\frac{1}{\sqrt{c_{1}}}(\gamma+H)Hd\sqrt{\epsilon}+\frac{H^{2}d}{\sqrt{c_{1}K}}\right)~{}.$

Note that we incur an additional $\sqrt{d}$ factor in the corruption error and
that the order of $\epsilon$ is not optimal. This is due to both the error
from corrupted covariates and the one from the corrupted coverage. Thus, the
next natural question is whether these bounds can be improved, at least in
terms of the dependence on $\epsilon$. We answer this question in the
affirmative. We show that, under a mild assumption on the feature space, we
can improve the order of $\epsilon$ at the cost of an extra $d^{3/2}$ factor,
thus recovering the optimal dependency on the corruption level. First, we
state the assumption.

######  Assumption 4.

Given a linear Markov game as in Definition 2, we assume that the features
satisfy $\min_{s,a,b}\left\lVert\phi(s,a,b)\right\rVert_{2}\geq c_{2}$, for
some $c_{2}>0$.

We emphasize that such an assumption is not restrictive and that $c_{2}$ is in
the order of $1/\sqrt{d}$ under various feature constructions, such as random
Fourier features (Rahimi and Recht, 2007). We find that Assumption 4 is enough
to obtain order-optimal bounds in terms of $\epsilon$, albeit having an
additional $O(d)$ term when comparing with Theorem 4 coming from the constant
$c_{2}$.

######  Theorem 5.

Suppose that the conditions of Theorem 4 and Assumption 4 hold. Then, with
probability at least $1-\delta$, SCRAM-PMVI with bonus $\Gamma_{h}(\cdot)$
defined as

$\displaystyle\left(2(1-\epsilon)K\mathcal{E}+\epsilon
KH\sqrt{d}+H\sqrt{Kd}\right)\left\lVert\phi(\cdot)^{\top}\Lambda^{-1}_{h}\right\rVert_{2}~{},$

returns $(\widehat{\pi},\widehat{\nu})$ that satisfy, for every
$s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)\leq\widetilde{O}\left(\frac{1}{c_{1}c_{2}}H^{2}d^{3/2}\epsilon+\frac{H^{2}d^{3/2}}{c_{1}c_{2}\sqrt{K}}\right)~{}.$

This improvement comes as a result of a novel bonus term and a different style
of analysis based on an application of the Woodbury matrix identity to account
for the extra terms coming from corruption.

###  6 DISCUSSION ON MARL COVERAGE ASSUMPTIONS

In this section, we discuss the relationship between various coverage
assumptions used in the literature. First, we state three additional
assumptions, apart from Assumption 2 and 3.

######  Assumption 5 (Single-policy coverage).

The NE strategy pair $(\pi^{*},\nu^{*})$ is covered by the dataset $D$.

######  Assumption 6 (Unilateral coverage).

For all strategies $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ and
$\nu:\mathcal{S}\rightarrow\Delta(\mathcal{B})$, the strategy pairs
$(\pi^{*},\nu)$ and $(\pi,\nu^{*})$ are covered by $D$.

######  Assumption 7 (Uniform coverage).

For all $h\in[H]$ and
$(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$, the tuple $(s,a,b)$
at time step $h$ is covered by $D$.

Note that Assumption 5 is the weakest assumption. Moreover, it is a direct
extension of Assumption 3.2 of (Zhang et al., 2022), while Assumption 7 is an
extension of the uniform policy coverage in the single-player setting (Cai et
al., 2020). We show that Assumption 6 implies Assumption 3 with high
probability, when the feature matrix has full rank, and that, for tabular
Markov games,666For tabular Markov games, we have $\phi(s,a,b)=e_{s,a,b}$,
where $e_{s,a,b}$ is the $SAB$-dimensional zero vector with $1$ in the
$(s,a,b)$ entry. these two assumptions are equivalent. All proofs of our
results can be found in the Appendix.

######  Proposition 1.

Let $\Phi\in\mathbb{R}^{SAB\times d}$ denote the feature matrix. Assume $\Phi$
has full rank and let $\delta\in(0,1)$. Then, if Assumption 6 holds, there
exists a positive constant that depends on $\delta$ for which Assumption 3
holds, with probability at least $1-\delta$. Moreover, in the tabular Markov
game setting, these two assumptions are equivalent.

Furthermore, it is obvious that uniform coverage is stronger than unilateral
coverage. The relation between Assumption 2 and Assumption 7 is given as
follows.

######  Proposition 2.

Assume that $\Phi$ has full rank. Then, if Assumption 2 holds, Assumption 7
holds. Moreover, in the tabular MG setting, these two assumptions are
equivalent.

As already shown in (Zhong et al., 2022), assuming that the collected data
covers only the NE strategy pair $\pi^{*}=(\mu^{*},\nu^{*})$ is not enough to
learn an approximate NE policy pair. Indeed, Assumption 3 is necessary for
solving offline two-player zero-sum Markov games, even in clean environments.

######  Remark 3.

Note that, under the assumption that $\Phi$ is full rank (if not,
orthogonalization can be applied), the given coverage assumptions are listed
according to their strength. With high probability, we have

$A.\ref{asn:uniform-phi-coverage}\Rightarrow A.\ref{asn:uniform-
coverage}\Rightarrow A.\ref{asn:unilateral-coverage}\Rightarrow
A.\ref{asm:low_relative_uncertainty}\Rightarrow A.\ref{asn:single-
coverage}~{}.$

Moreover, for the tabular setting, Assumption 2 is equivalent to 7 and
Assumption 6 is equivalent to 3.

###  7 RELATED WORK

Offline RL. Our work is related to the offline RL literature, where there have
been substantial developments in recent years, both on the empirical front
(Jaques et al., 2019; Laroche et al., 2019; Fujimoto et al., 2019; Kumar et
al., 2020; Agarwal et al., 2020; Kidambi et al., 2020) and the theoretical
front (Jin et al., 2021; Xie et al., 2021; Rashidinejad et al., 2021; Uehara
and Sun, 2021; Zanette et al., 2021b). As previously mentioned, coverage
assumptions on the data are key in this setting, and there has been a variety
of different assumptions in the single-player setting, starting from the all-
policy coverage $\left\lVert d^{\pi}/d^{\rho}\right\rVert_{\infty}\leq B$, for
all $\pi$ (Munos and Szepesvári, 2008), to optimal policy coverage
$\left\lVert d^{*}/d^{\rho}\right\rVert_{\infty}\leq B$ (Xie et al., 2021),
and $\alpha$-regularized optimal policy coverage $\left\lVert
d^{*}_{\alpha}/d^{\rho}\right\rVert_{\infty}\leq B$ (Zhan et al., 2022).
First, all of these assumptions are with respect to the original data-
collecting distribution $d^{\rho}$, while our weakest assumption (LRU
coverage) relies only upon the sample covariance matrix of the data. Second,
note that the weakest of the assumptions above ($\alpha$-regularized optimal
policy coverage) requires coverage of only the optimal solution to the
regularized LP problem, while coverage of the NE policy pair and its
unilateral neighbors is necessary for finding NE policy pairs in our setting
(Zhong et al., 2022). This is arguably due to the higher complexity of the
problem compared to the single-player setting.

Adversarial attacks in RL. Our work also adds to the vast literature on
adversarial attacks in ML (Szegedy et al., 2013; Biggio et al., 2013; Nguyen
et al., 2015; Papernot et al., 2017; Biggio et al., 2012; Li et al., 2016;
Xiao et al., 2012) and the existing body of work on adversarial attacks in RL
and MARL (Huang et al., 2017; Lin et al., 2017; Wu et al., 2022; Gleave et
al., 2020; Sun et al., 2020a, b; Ma et al., 2019; Rakhsha et al., 2021;
Everitt et al., 2017; Huang and Zhu, 2019; Rangi et al., 2022; Mohammadi et
al., 2023). Specifically, we consider the problem of robustness to data
corruption, which is a type of training-time attack (Mei and Zhu, 2015; Xiao
et al., 2015; Rakhsha et al., 2020). Popular types of defense against such
attacks include randomized smoothing (Cohen et al., 2019; Wu et al., 2021),
outlier detection (Diakonikolas et al., 2019) and robust estimator methods
(Chen et al., 2022a; Diakonikolas et al., 2017; Banihashem et al., 2023). In
this work, we use the latter methods, for both weight estimation in linear
games and mean estimation in tabular ones. Arguably, the closest work to ours
is (Zhang et al., 2022), which studies the corruption problem in single-agent
RL. On the other hand, while our analysis of the lower bounds is inspired by
their work, our analysis leads to tighter upper bounds in terms of $\epsilon$
and $H$ for two-player zero-sum Markov games. Yang et al. (2022) also study
the robustness problem in the offline RL setting. However, their attack model
assumes observation perturbations of bounded radius. Our attack model is
stronger since it allows for the arbitrary perturbation of the tuples.
Recently, adversarial corruption in the online setting has been studied in
linear contextual bandits (He et al., 2022) and more generally in MDPs with
general function approximation (Ye et al., 2023). These works also broadly
relate to corruption-robust approaches in distributed RL (Chen et al., 2022b;
Fan et al., 2021), that focus on MDP settings.

Reward perturbation in MARL. Ma et al. (2022) study the problem of reward
design in online systems with no-regret learners. Their goal is to modify the
utility function iteratively so that the agents converge to a desired action
profile, while maintaining low cost of perturbation. While we also consider
multi-agent systems subject to a third-party intervention, our focus is in the
offline setting with an adversarial corruption framework, with an emphasis on
the defense front. On the other hand, Wu et al. (2023) is more closely related
to ours. They also study an offline corruption model, where the attacker can
perturb the reward signal in order to enforce a particular policy, while at
the same time maintaining a low perturbation cost. While their focus in on
designing cost-efficient attacks of that form, our work studies defenses
against a broad class of data poisoning attacks, defined by the Huber
contamination model.

Learning in Markov games. Finally, our work also relates to the research area
of learning in Markov games (Vrancx et al., 2008; Littman, 1994, 2001; Tian et
al., 2021; Wang and Sandholm, 2002; Sayin et al., 2021; Xie et al., 2020). In
particular, we consider offline two-player zero-sum games, which have been
recently considered in (Cui and Du, 2022) for tabular settings and (Zhong et
al., 2022) for linear settings. While they solve the offline problem by
assuming that the collected data is sampled from a benign behavioral policy,
we consider the problem of robustness of their proposed methods to data
corruption. More specifically, we assume that an $\epsilon$ fraction of
collected data has been corrupted, and our aim is to learn NE strategy pairs
under such an assumption. When $\epsilon=0$, we recover the same bounds as
theirs on the suboptimality gap.

###  8 CONCLUSION

We considered the problem of data corruption in offline two-player zero-sum
Markov games. Our contribution was to provide an extensive characterization of
the problem under various coverage assumptions on both the clean and corrupted
data. To the best of our knowledge, we are the first to provide such a
characterization for the problem of corruption in offline Markov games. For
the hardest setting where minimal coverage is guaranteed only on the clean
data, we are able to match the optimal order of $\epsilon$ under mild
structural assumptions, thus providing a full picture of this setting. There
are many interesting future directions to pursue: i) studying robustness under
adversarial corruption in Markov games with general function approximation;
ii) extending the two-player zero-sum Markov game setting to online data
corruption, where, in each round the reward/transition data is corrupted with
probability $\epsilon$; iii) studying robustness to adversarial corruption in
larger structured games (e.g. Markov potential games).

### Acknowledgements

The authors thank anonymous reviewers for their valuable suggestions and
comments. This research was, in part, funded by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) – project number
467367360.

### References

  * Agarwal et al. (2020) Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi.  An Optimistic Perspective on Offline Reinforcement Learning.  In _ICML_ , 2020.
  * Bakshi and Prasad (2021) Ainesh Bakshi and Adarsh Prasad.  Robust Linear regression: Optimal Rates in Polynomial time.  In _ACM SIGACT_ , 2021.
  * Banihashem et al. (2023) Kiarash Banihashem, Adish Singla, and Goran Radanovic.  Defense Against Reward Poisoning Attacks in Reinforcement Learning.  _Trans. Mach. Learn. Res._ , 2023.
  * Berner et al. (2019) Christopher Berner et al.  Dota 2 with Large Scale Deep Reinforcement Learning.  _CoRR_ , abs/1912.06680, 2019.
  * Biggio et al. (2012) Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning Attacks Against Support Vector Machines.  _CoRR_ , abs/1206.6389, 2012.
  * Biggio et al. (2013) Battista Biggio et al.  Evasion Attacks Against Machine Learning at Test Time.  In _ECML PKDD_ , 2013.
  * Cai et al. (2020) Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang.  Provably Efficient Exploration in Policy Optimization.  In _ICML_ , 2020.
  * Chen et al. (2022a) Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau.  Online and Distribution-free Robustness: Regression and Contextual Bandits with Huber Contamination.  In _FOCS_ , 2022a.
  * Chen et al. (2022b) Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu.  Byzantine-robust Online and Offline Distributed Reinforcement Learning.  _CoRR_ , abs/2206.00165, 2022b.
  * Cohen et al. (2019) Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.  Certified Adversarial Robustness via Randomized Smoothing.  In _ICML_ , 2019.
  * Cui and Du (2022) Qiwen Cui and Simon S Du.  When is Offline Two-player Zero-sum Markov Game Solvable?  _CoRR_ , abs/2201.03522, 2022.
  * Diakonikolas et al. (2017) Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Being Robust (in High Dimensions) Can be Practical.  In _ICML_ , 2017.
  * Diakonikolas et al. (2019) Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart.  Sever: A Robust Meta-algorithm for Stochastic Optimization.  In _ICML_ , 2019.
  * Everitt et al. (2017) Tom Everitt, Victoria Krakovna, Laurent Orseau, Marcus Hutter, and Shane Legg.  Reinforcement Learning with a Corrupted Reward Channel.  _CoRR_ , abs/1705.08417, 2017.
  * Fan et al. (2021) Xiaofeng Fan, Yining Ma, Zhongxiang Dai, Wei Jing, Cheston Tan, and Bryan Kian Hsiang Low.  Fault-tolerant Federated Reinforcement Learning with Theoretical Guarantee.  In _NeurIPS_ , 2021.
  * Fujimoto et al. (2019) Scott Fujimoto, David Meger, and Doina Precup.  Off-policy Deep Reinforcement Learning without Exploration.  In _ICML_ , 2019.
  * Gleave et al. (2020) Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell.  Adversarial Policies: Attacking Deep Reinforcement Learning.  In _ICLR_ , 2020.
  * He et al. (2022) Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu.  Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions.  In _NeurIPS_ , 2022.
  * Henderson and Searle (1981) Harold V Henderson and Shayle R Searle.  On Deriving the Inverse of a Sum of Matrices.  _Siam Review_ , 1981.
  * Huang et al. (2017) Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel.  Adversarial Attacks on Neural Network Policies.  _CoRR_ , abs/1702.02284, 2017.
  * Huang and Zhu (2019) Yunhan Huang and Quanyan Zhu.  Deceptive Reinforcement Learning under Adversarial Manipulations on Cost Signals.  In _GameSec_ , 2019.
  * Jaques et al. (2019) Natasha Jaques et al.  Way Off-policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialog.  _CoRR_ , abs/1907.00456, 2019.
  * Jin et al. (2021) Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is Pessimism Provably Efficient for Offline RL?  In _ICML_ , 2021.
  * Kidambi et al. (2020) Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims.  Morel: Model-based Offline Rinforcement Learning.  In _NeurIPS_ , 2020.
  * Kumar et al. (2020) Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine.  Conservative Q-learning for Offline Reinforcement Learning.  In _NeurIPS_ , 2020.
  * Laroche et al. (2019) Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes.  Safe Policy Improvement with Baseline Bootstrapping.  In _ICML_ , 2019.
  * Levine et al. (2020) Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.  _CoRR_ , abs/2005.01643, 2020.
  * Li et al. (2016) Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik.  Data Poisoning Attacks on Factorization-based Collaborative Filtering.  In _NeurIPS_ , 2016.
  * Lin et al. (2017) Yen-Chen Lin, Zhang-Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming-Yu Liu, and Min Sun.  Tactics of Adversarial Attack on Deep Reinforcement Learning Agents.  In _IJCAI_ , 2017.
  * Littman (1994) Michael L. Littman.  Markov Games as a Framework for Multi-agent Reinforcement Learning.  In _ICML_ , 1994.
  * Littman (2001) Michael L Littman.  Value-function Reinforcement Learning in Markov Games.  _Cognitive Systems Research_ , 2:55–66, 2001.
  * Ma et al. (2019) Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu.  Policy Poisoning in Batch Reinforcement Learning and Control.  In _NeurIPS_ , 2019.
  * Ma et al. (2022) Yuzhe Ma, Young Wu, and Xiaojin Zhu.  Game Redesign in No-regret Game Playing.  In _IJCAI_ , 2022.
  * Mei and Zhu (2015) Shike Mei and Xiaojin Zhu.  Using Machine Teaching to Identify Optimal Training-set Attacks on Machine Learners.  In _AAAI_ , 2015.
  * Mohammadi et al. (2023) Mohammad Mohammadi, Jonathan Nöther, Debmalya Mandal, Adish Singla, and Goran Radanovic.  Implicit poisoning attacks in two-agent reinforcement learning: Adversarial policies for training-time attacks.  In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ , pages 1835–1844, 2023.
  * Munos and Szepesvári (2008) Rémi Munos and Csaba Szepesvári.  Finite-time Bounds for Fitted Value Iteration.  _JMLR_ , 2008.
  * Nguyen et al. (2015) Anh Nguyen, Jason Yosinski, and Jeff Clune.  Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images.  In _CVPR_ , 2015.
  * Pan et al. (2017) Yunpeng Pan et al.  Agile Autonomous Driving Using End-to-end Deep Imitation Learning.  _CoRR_ , abs/1709.07174, 2017.
  * Papernot et al. (2017) Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami.  Practical Black-box Attacks Against Machine Learning.  In _ACM_ , 2017.
  * Pensia et al. (2020) Ankit Pensia, Varun Jog, and Po-Ling Loh.  Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination.  _CoRR_ , abs/2009.12976, 2020.
  * Rahimi and Recht (2007) Ali Rahimi and Benjamin Recht.  Random Features for Large-scale Kernel Machines.  In _NeurIPS_ , 2007.
  * Rakhsha et al. (2020) Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla.  Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning.  In _ICML_ , 2020.
  * Rakhsha et al. (2021) Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla.  Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks.  _JMLR_ , 2021.
  * Rangi et al. (2022) Anshuka Rangi, Haifeng Xu, Long Tran-Thanh, and Massimo Franceschetti.  Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning.  _CoRR_ , abs/2208.13663, 2022.
  * Rashidinejad et al. (2021) Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell.  Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism.  In _NeurIPS_ , 2021.
  * Sayin et al. (2021) Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar.  Decentralized Q-learning in Zero-sum Markov Games.  In _NeurIPS_ , 2021.
  * Shapley (1953) Lloyd S Shapley.  Stochastic Games.  _PNAS_ , 39, 1953.
  * Silver et al. (2017) David Silver et al.  Mastering the Game of Go Without Human Knowledge.  _Nature_ , 550, 2017.
  * Sun et al. (2020a) Jianwen Sun, Tianwei Zhang, Xiaofei Xie, Lei Ma, Yan Zheng, Kangjie Chen, and Yang Liu.  Stealthy and Efficient Adversarial Attacks Against Deep Reinforcement Learning.  In _AAAI_ , 2020a.
  * Sun et al. (2020b) Yanchao Sun, Da Huo, and Furong Huang.  Vulnerability-aware Poisoning Mechanism for Online RL with Unknown Dynamics.  In _ICLR_ , 2020b.
  * Szegedy et al. (2013) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing Properties of Neural Networks.  _CoRR_ , abs/1312.6199, 2013.
  * Tian et al. (2021) Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra.  Online Learning in Unknown Markov Games.  In _ICML_ , 2021.
  * Uehara and Sun (2021) Masatoshi Uehara and Wen Sun.  Pessimistic Model-based Offline Reinforcement Learning Under Partial Coverage.  _CoRR_ , abs/2107.06226, 2021.
  * Vrancx et al. (2008) Peter Vrancx, Katja Verbeeck, and Ann Nowé.  Decentralized Learning in Markov Games.  _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , 38, 2008.
  * Wang et al. (2018) Lu Wang, Wei Zhang, Xiaofeng He, and Hongyuan Zha.  Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendation.  In _ACM SIGKDD_ , 2018.
  * Wang and Sandholm (2002) Xiaofeng Wang and Tuomas Sandholm.  Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games.  In _NeurIPS_ , 2002.
  * Wu et al. (2021) Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li.  CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing.  _CoRR_ , abs/2106.09292, 2021.
  * Wu et al. (2022) Young Wu, Jermey McMahan, Xiaojin Zhu, and Qiaomin Xie.  Reward Poisoning Attacks on Offline Multi-agent Reinforcement Learning.  _CoRR_ , abs/2206.01888, 2022.
  * Wu et al. (2023) Young Wu, Jeremy McMahan, Xiaojin Zhu, and Qiaomin Xie.  Reward Poisoning Attacks on Offline Multi-agent Reinforcement Learning.  In _AAAI_ , 2023.
  * Xiao et al. (2012) Han Xiao, Huang Xiao, and Claudia Eckert.  Adversarial Label Flips Attack on Support Vector Machines.  In _ECAI_ , 2012.
  * Xiao et al. (2015) Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli.  Is Feature Selection Secure Against Training Data Poisoning?  In _ICML_ , 2015.
  * Xie et al. (2020) Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang.  Learning Zero-sum Simultaneous-move Markov Games Using Function Approximation and Correlated Equilibrium.  In _COLT_ , 2020.
  * Xie et al. (2021) Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent Pessimism for Offline Reinforcement Learning.  In _NeurIPS_ , 2021.
  * Yang et al. (2022) Rui Yang, Chenjia Bai, Xiaoteng Ma, Zhaoran Wang, Chongjie Zhang, and Lei Han.  RORL: Robust Offline Reinforcement Learning via Conservative Smoothing.  In _NeurIPS_ , 2022.
  * Ye et al. (2023) Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang.  Corruption-robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes.  In _ICML_ , 2023.
  * Zanette et al. (2021a) Andrea Zanette, Ching-An Cheng, and Alekh Agarwal.  Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation.  In _COLT_ , 2021a.
  * Zanette et al. (2021b) Andrea Zanette, Martin J Wainwright, and Emma Brunskill.  Provable Benefits of Actor-critic Methods for Offline Reinforcement Learning.  In _NeurIPS_ , 2021b.
  * Zhan et al. (2022) Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee.  Offline Reinforcement Learning with Realizability and Single-policy Concentrability.  In _COLT_ , 2022.
  * Zhang et al. (2022) Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun.  Corruption-robust Offline Reinforcement Learning.  In _AISTATS_ , 2022.
  * Zhong et al. (2022) Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang.  Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets.  In _ICML_ , 2022.

##  Appendix

###  Appendix A Proofs of Section 4

In this section, we derive the proofs of the results in Section 4.

####  A.1 Proof of Theorem 1

We first restate the result.

######  Statement.

For every algorithm $L$, there exists a Markov game $\mathcal{G}$, an instance
of the corrupted dataset, corruption level $\epsilon$, and a data collecting
distribution $\rho$, such that, with probability at least $1/4$, $L$ will find
a no-better than $\Omega(Hd\epsilon)$-approximate NE policy pair
$(\widetilde{\pi},\widetilde{\nu})$. That is, with a probability of at least
$1/4$, we have, for every $s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widetilde{\pi},\widetilde{\nu},s)=\Omega(Hd\epsilon)~{}.$

###### Proof.

We will construct an example to prove our statement. Consider the following
Markov game
$\mathcal{G}=(\mathcal{S},\mathcal{A},\mathcal{B},P,H,r,\gamma,s_{0})$, with
$\left\lvert\mathcal{S}\right\rvert=S$,
$\left\lvert\mathcal{A}\right\rvert=A$,
$\left\lvert\mathcal{B}\right\rvert=B$, deterministic transitions, episode
length $H$ and initial state $s_{0}$, with $S\leq(AB)^{H/2}$. Note that, in
this case, we have $d=SAB$. Here $r$ denotes the reward with respect to the
$\max$ player. Assume that the transition dynamics follow a tree structure,
that is, let $\mathcal{T}$ be a tree with nodes represented by states
$s\in\mathcal{S}$ and edges represented by action tuples
$(a,b)\in\mathcal{A}\times\mathcal{B}$, with root node $s_{0}$, such that, for
every $(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$, node $s$ is
parent to node $\arg\max_{s^{\prime}}P(s^{\prime}|s,a,b)$. We denote by $p(s)$
the parent of node $s$. Moreover, assume that all states represented by the
leaf nodes are self-absorbing states, i.e. the state does not change, no
matter what action is taken. Let $q$ denote the depth of $\mathcal{T}$. Note
that we have

$\displaystyle q=O(\left\lceil(\log_{AB}(S(AB-1)+1)-1\right\rceil)~{}.$

Now let us denote by $\mathcal{L}_{i}$ the subset of $\mathcal{S}$ containing
the states represented by nodes in level $i$ of $\mathcal{T}$, for all
$i\in\\{0\\}\cup[q]$, and let $s^{j}_{i}$ enumerate the states in level
$\mathcal{L}_{i}$, for $j\in[(AB)^{i-1}]$. Let us define the reward function
as follows. Fix a sequence of states
$(s^{*}_{0},s^{*}_{1},\ldots,s^{*}_{q})\in\mathcal{L}_{0}\times\ldots\times\mathcal{L}_{q}$,
where $s^{*}_{0}=s_{0}$ and $s^{*}_{i}$ is a node in the $i$th level of
$\mathcal{T}$ such that $P(s^{*}_{i}|\;s^{*}_{i-1},a,b_{1})=1$, for all
$i\in[q]$ and $a\in\mathcal{A}$. Furthermore, for all $s\neq s^{*}_{i-1}$ and
$(a,b)\in\mathcal{A}\times\mathcal{B}$, we have $P(s^{*}_{i}|s,a,b)=0$, for
all $i\in[q]$. Let $\alpha\in(0,1/3)$ and assume $(s^{*}_{q},a_{1},b_{1})$ is
the least represented state according to data collecting distribution
$d^{\rho}$.

Then, for all $i\in\\{0,1,\ldots,q-1\\}$, we define

$r(s^{*}_{i},a,b)=\begin{cases}\alpha&\text{if}\;\;a=a_{1},b=b_{1}\\\
2\alpha&\text{if}\;\;a=a_{1},b\neq b_{1}\\\
0&\text{otherwise}\end{cases}\hskip 28.45274pt\text{and}\hskip
28.45274ptr(s^{*}_{q},a,b)=\begin{cases}\alpha&\text{if}\;\;a=a_{1},b=b_{1}\\\
X&\text{if}\;\;a=a_{1},b=b_{2}\\\
3\alpha&\text{if}\;\;a=a_{1},b\in\mathcal{B}\setminus\\{b_{1},b_{2}\\}\\\
0&\text{otherwise}\end{cases}$

where $X$ is a Bernoulli random variable with parameter $2\alpha$. On the
other hand, for all
$s\in\mathcal{S}\setminus\\{s^{*}_{0},\ldots,s^{*}_{q}\\}$, let

$r(s,a,b)=\begin{cases}1&\text{if}\;\;a=a_{1}\\\
0&\text{otherwise}\end{cases}$

Let us determine the value of the game in each state, using the method of
backward induction. Set $V^{*}_{H+1}(s)=0$, for all $s\in\mathcal{S}$. Then,
for all $s\in\mathcal{L}_{q}\setminus\\{s^{*}_{q}\\}$, we have

$Q^{*}_{H}(s,\cdot,\cdot)$ | $b_{1}$ | $b_{2}$ | … | $b_{B}$
---|---|---|---|---
$a_{1}$ | $1$ | $1$ | … | $1$
$a_{2}$ | $0$ | $0$ | … | $0$
$\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$
$a_{A}$ | $0$ | $0$ | … | $0$

and  $Q^{*}_{H}(s^{*}_{q},\cdot,\cdot)$ $b_{1}$ $b_{2}$ $b_{3}$ … $b_{B}$
$a_{1}$ $\alpha$ $2\alpha$ $3\alpha$ … $3\alpha$ $a_{2}$ $0$ $0$ $0$ … $0$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\ddots$ $\vdots$ $a_{A}$ $0$ $0$ $0$ …
$0$

Thus, we obtain $V^{*}_{H}(s)=1$, for all
$s\in\mathcal{L}_{d}\setminus\\{s^{*}_{q}\\}$ and
$V^{*}_{H}(s^{*}_{q})=\alpha$. Moreover, note that, for all
$s\in\mathcal{L}_{d-1}\setminus\\{s^{*}_{q-1}\\}$, we have

$Q^{*}_{H-1}(s,\cdot,\cdot)$ | $b_{1}$ | $b_{2}$ | … | $b_{B}$
---|---|---|---|---
$a_{1}$ | $2$ | $2$ | … | $2$
$a_{2}$ | $0$ | $0$ | … | $0$
$\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$
$a_{A}$ | $0$ | $0$ | … | $0$

and  $Q^{*}_{H-1}(s^{*}_{q},\cdot,\cdot)$ $b_{1}$ $b_{2}$ $b_{3}$ … $b_{B}$
$a_{1}$ $2\alpha$ $3\alpha$ $4\alpha$ … $4\alpha$ $a_{2}$ $0$ $0$ $0$ … $0$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\ddots$ $\vdots$ $a_{A}$ $0$ $0$ $0$ …
$0$

and thus $V^{*}_{H-1}(s^{*}_{q})=2\alpha$. Continuing in this fashion, we
obtain

$\displaystyle V^{*}_{1}(s_{0})=H\alpha,$

where the first $q$ steps come from the trajectory
$(s^{*}_{0},\ldots,s^{*}_{q})$, and the rest of the $H-q$ steps come from
staying in state $s^{*}_{q}$.

Now let $\mathcal{G}^{\prime}$ be a Markov game that is identical to
$\mathcal{G}$, except for one difference. Let $r^{\prime}$ denote the reward
function of $\mathcal{G}^{\prime}$. Then
$r^{\prime}(s^{*}_{q},a_{1},b_{1})=r(s^{*}_{q},a_{1},b_{1})+Ber(2\alpha)$, and
$r^{\prime}(s,a,b)=r(s,a,b)$, for all other state-action tuples. Then for
$\mathcal{G}^{\prime}$ we have

$\widetilde{Q}^{*}_{H}(s,\cdot,\cdot)$ | $b_{1}$ | … | $b_{B}$
---|---|---|---
$a_{1}$ | $1$ | … | $1$
$a_{2}$ | $0$ | … | $0$
$\vdots$ | $\vdots$ | $\ddots$ | $\vdots$
$a_{A}$ | $0$ | … | $0$

and  $\widetilde{Q}^{*}_{H}(s^{*}_{q},\cdot,\cdot)$ $b_{1}$ $b_{2}$ $b_{3}$ …
$b_{B}$ $a_{1}$ $3\alpha$ $2\alpha$ $2\alpha$ … $2\alpha$ $a_{2}$ $0$ $0$ $0$
… $0$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\ddots$ $\vdots$ $a_{A}$ $0$ $0$
$0$ … $0$

where $\widetilde{Q}(\cdot,\cdot,\cdot)$ denotes the matrices of $Q$-values of
NE policies for $\mathcal{G}^{\prime}$. Note that the trajectory traversed by
the NE policy pair in $\mathcal{G}^{\prime}$ is still
$(s^{*}_{0},\ldots,s^{*}_{q-1},s^{*}_{q})$. However, when at state
$s^{*}_{q}$, the NE policy is $(a_{1},b_{2})$, instead of $(a_{1},b_{1})$.
Thus, we have

$\displaystyle\widetilde{V}^{*}_{1}(s_{0})=(2H-d)\alpha,$

since the system will stay in state $s^{*}_{q}$ for $H-q$ steps, until the
episode ends. Note that no policy pair can be simultaneously optimal in both
games. In the worst case, a policy pair which is a NE in
$\mathcal{G}^{\prime}$ will incur a suboptimality gap of

$\displaystyle(H-q)\alpha=(H-\left\lceil(\log_{AB}(S(AB-1)+1)-1\right\rceil)\alpha\geq\Omega(H\alpha),$

in $\mathcal{G}$, where the second inequality follows from the fact that
$S\leq(AB)^{H/2}$.

Now, let $\alpha=SAB\epsilon/2$. Since $(s^{*}_{q},a_{1},b_{1})$ is the least
represented state with respect to $d^{\rho}$, by pigeon-hole principle, we
must have $d^{\rho}(s^{*}_{d},a_{1},b_{1})\leq 1/SAB$. Assume the adversary
uses all its budget only to perturb the reward of this state-action tuple.
Concretely, if the game is $\mathcal{G}$, then the adversary perturbs it into
$\mathcal{G}^{\prime}$ by adding $Ber(SAB\epsilon)$ to
$r(s^{*}_{q},a_{1},b_{1})$.

With probability at least $1/2$, the number of times $(s^{*}_{q},a_{1},b_{1})$
is counted in a dataset with $KH$ tuples is no more than $KH/SAB$, since
$(s^{*}_{q},a_{1},b_{1})$ is the least represented tuple. Conditioned on this,
with probability at least $1/2$, the reward seen from
$(s^{*}_{q},a_{1},b_{1})$ is $2SAB\epsilon$. Thus, perturbing the reward of
$(s^{*}_{q},a_{1},b_{1})$ at least $KH\epsilon$ times is enough to make one of
the games indistinguishable from the other one. Thus, the agent will
inevitably incur

$\displaystyle\text{SubOpt}(\pi,\nu,s)\geq\Omega(HSAB\epsilon).$

∎

####  A.2 Proof of Theorem 2

The main result of this section relies on the RLS oracle guarantee stated
below.

######  Theorem 6.

(Zhang et al., 2022) Given an $\epsilon$-corrupted dataset
$D=\\{x_{i},y_{i}\\}_{i\in[n]}$, where the clean data is generated as
$\widetilde{x}_{i}\sim\beta$,
$\mathbb{P}(\left\lVert\widetilde{x}_{i}\right\rVert\leq 1)=1$,
$\widetilde{y}_{i}=\widetilde{x}_{i}^{\top}\omega^{*}+\xi_{i}$, where
$\xi_{i}$ is zero-mean $\sigma^{2}$-variance sub-Gaussian random noise, then a
robust least square estimator returns an estimator $\omega$ such that, if
$\mathbb{E}_{\beta}[xx^{\top}]\succeq\kappa I$, for some strictly positive
constant $\kappa$, then with probability at least $1-\delta$, we have

  * •

If $\mathbb{E}_{\beta}[xx^{\top}]\succeq\kappa I$, then with probability at
least $1-\delta$, we have

$\left\lVert\omega^{*}-\omega\right\rVert_{2}\leq
c_{1}(\delta)\cdot\left(\sqrt{\frac{\sigma^{2}poly(d)}{\kappa^{2}n}}+\frac{\sigma}{\kappa}\epsilon\right);$

  * •

With probability at least $1-\delta$, we have

$\mathbb{E}\left[\left\lVert\widetilde{x}^{\top}(\omega^{*}-\omega)\right\rVert^{2}_{2}\right]\leq
c_{2}(\delta)\cdot\left(\frac{\sigma^{2}poly(d)}{n}+\sigma^{2}\epsilon\right),$

where $c_{1}$ and $c_{2}$ hide constants and $polylog(1/\delta)$ terms.

Using the above guarantee, we are now ready to prove Theorem 2. First, we
recall its statement.

######  Statement.

Suppose that Assumption 2 holds on an $\epsilon$-corrupted dataset $D$
corresponding to a linear Markov game. Then, given $\delta>0$, with
probability at least $1-\delta$, RLS-PMVI with bonus term
$\Gamma_{h}(s,a,b)=0$ achieves suboptimality gap upper bounded by

$\displaystyle\widetilde{O}\left(\sqrt{\frac{H(H+\gamma)^{2}poly(d)}{\kappa^{2}K}}+\frac{H(H+\gamma)}{\kappa}\epsilon\right)~{}.$

###### Proof.

Let us define the error in Theorem 6 as

$\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)=c_{1}(\delta)\cdot\left(\sqrt{\frac{\sigma^{2}poly(d)}{\kappa^{2}K}}+\frac{\sigma}{\kappa}\epsilon\right)~{}.$
(3)

First, we provide upper and lower bounds on the Bellman error.

######  Lemma 2.

Given the tuple $(s,a,b)$, let us define the Bellman error as

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)~{},$
$\displaystyle\overline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\overline{V}_{h+1})(s,a,b)-\overline{Q}_{h}(s,a,b)~{},$

for all $h\in[H]$. Then, with probability at least $1-\delta$, we have

$\displaystyle-\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)$
$\displaystyle\leq\underline{\iota}_{h}(s,a,b)\leq\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)~{},$
$\displaystyle-\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)$
$\displaystyle\leq-\overline{\iota}_{h}(s,a,b)\leq\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)~{},$

for all $(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$ and
$h\in[H]$.

###### Proof.

We start by deriving upper bounds on the Bellman error. Note that, with
probability at least $1-\delta$, Theorem 6 and Assumption 2 imply

$\displaystyle|\phi^{\top}\underline{\omega}_{h}-(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)|\leq\left\lVert\phi(s,a,b)\right\rVert_{2}\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert_{2}\leq\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)$
(4)

We show the first case. Note that we have

$\underline{Q}_{h}(s,a,b)=\max\\{0,\phi^{\top}\underline{\omega}_{h}\\}\geq\phi^{\top}\underline{\omega}_{h},$

which, together with Equation (4), imply

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)$
$\displaystyle\leq(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\phi^{\top}\underline{\omega}_{h}$
$\displaystyle\leq\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)~{}.$

For the lower bound, consider two cases. First, if
$\phi^{\top}\underline{\omega}_{h}\leq 0$, then we have

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-0$
$\displaystyle\geq 0.$

On the other hand, if $\phi^{\top}\underline{\omega}_{h}\geq 0$, then we have

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\phi^{\top}\underline{\omega}_{h}$
$\displaystyle\geq-\mathcal{E}_{1}(\epsilon,K,D,H,\sigma)~{}.$

∎

Next, we consider the relationship between the estimated value function and
the true ones based on the best responses.

######  Lemma 3.

If the bounds on the Bellman error given above hold, then, for any
$s\in\mathcal{S}$, we have

$\displaystyle\underline{V}_{h}(s)\leq
V^{\widehat{\pi},*}_{h}(s)+\mathcal{E}_{1}\;\;\text{and}\;\;V^{*,\widehat{\nu}}_{h}(s)-\mathcal{E}_{1}\leq\overline{V}_{h}(s)~{},$

where we omit the dependence of $\mathcal{E}_{1}$ on the relevant variables
for brevity.

###### Proof.

We prove the left inequality. The right follows similar arguments. We use
backward induction. For $h=H+1$, we have
$\underline{V}_{h}(s)=V^{\hat{\pi},*}_{h}(s)=0$. We assume the inequality hold
for $h+1$ and prove it for $h$. We have

$\displaystyle V^{\hat{\pi},*}_{h}(s)-\underline{V}_{h}(s)$
$\displaystyle=\mathbb{E}_{a\sim\hat{\pi},b\sim*}\left[Q^{\hat{\pi},*}_{h}(s,a,b)\right]-\mathbb{E}_{a\sim\hat{\pi},b\sim\hat{\nu}}\left[\underline{Q}_{h}(s,a,b)\right]$
$\displaystyle=\mathbb{E}_{a\sim\hat{\pi},b\sim*}\left[Q^{\hat{\pi},*}_{h}(s,a,b)-\underline{Q}_{h}(s,a,b)\right]+\left(\mathbb{E}_{a\sim\hat{\pi},b\sim*}\left[\underline{Q}_{h}(s,a,b)\right]-\mathbb{E}_{a\sim\hat{\pi},b\sim\hat{\nu}}\left[\underline{Q}_{h}(s,a,b)\right]\right)~{}.$

First, note that

$\displaystyle
Q^{\hat{\pi},*}_{h}(s,a,b)-\underline{Q}_{h}(s,a,b)=\mathbb{B}_{h}\left(V^{\hat{\pi},*}_{h+1}(s,a,b)-\underline{V}_{h+1}(s,a,b)\right)+\underline{\iota}_{h}(s,a,b)\geq-\mathcal{E}_{1}~{},$

where the second inequality follows from Lemma 2 and the induction assumption.
Furthermore, by the NE value property, we have

$\displaystyle\mathbb{E}_{a\sim\hat{\pi},b\sim*}\left[\underline{Q}_{h}(s,a,b)\right]-\mathbb{E}_{a\sim\hat{\pi},b\sim\hat{\nu}}\left[\underline{Q}_{h}(s,a,b)\right]\geq
0~{}.$

Thus, we obtain $\underline{V}_{h}(s)\leq
V^{\hat{\pi},*}_{h}(s)+\mathcal{E}_{1}$. ∎

Next, we prove a result that gives us an upper bound on $\sigma^{2}$ in terms
of the reward variance and $H$.

######  Lemma 4.

We have
$Var(\xi_{h}^{\tau}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})=\sigma^{2}\leq(H+\gamma)^{2}$.

###### Proof.

We consider $\underline{V}_{h+1}$. The case for $\overline{V}_{h+1}$ is
similar. We have

$\displaystyle Var(\xi_{h}^{\tau}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$
$\displaystyle=\mathbb{E}\left[(r^{\tau}_{h}+\underline{V}_{h+1}(s^{\tau}_{h+1})-(\mathbb{B}_{h}\underline{V}_{h+1})(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}))^{2}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}\right]$
$\displaystyle=\mathbb{E}\left[(r^{\tau}_{h}+\underline{V}_{h+1}(s^{\tau}_{h+1})-\mathbb{E}[r^{\tau}_{h}+\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])^{2}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}\right]$
$\displaystyle=\mathbb{E}\left[(r^{\tau}_{h}-\mathbb{E}[r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])^{2}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}\right]+\mathbb{E}\left[(\underline{V}_{h+1}(s^{\tau}_{h+1})-\mathbb{E}[\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])^{2}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}\right]$
$\displaystyle\quad+2\mathbb{E}\left[(r^{\tau}_{h}-\mathbb{E}[r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])(\underline{V}_{h+1}(s^{\tau}_{h+1})-\mathbb{E}[\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])\right]$
$\displaystyle=Var(r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})+Var(\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$
$\displaystyle\quad+2\sqrt{\mathbb{E}\left[(r^{\tau}_{h}-\mathbb{E}[r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])^{2}\right]\mathbb{E}\left[(\underline{V}_{h+1}(s^{\tau}_{h+1})-\mathbb{E}[\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}])^{2}\right]}$
$\displaystyle\leq
Var(r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})+Var(\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$
$\displaystyle\quad+2\sqrt{Var(r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})Var(\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})}$
$\displaystyle=\left(\sqrt{Var(r^{\tau}_{h}|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})}+\sqrt{Var(\underline{V}_{h+1}(s^{\tau}_{h+1})|s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})}\right)^{2}\leq(\gamma+H)^{2}~{},$

where the fourth equality uses Cauchy-Schwarz and the last one uses the fact
that $0\leq\underline{V}_{h+1}(s)\leq H$, for all $h\in[H]$,
$s\in\mathcal{S}$. ∎

Next, we state the following well-known result which will help us express the
suboptimality gap in terms of quantities that we can control. For a proof, see
(Cai et al., 2020).

######  Lemma 5.

(Value difference lemma) Given an MG
$(\mathcal{S},\mathcal{A},\mathcal{B},r,H)$, let
$\hat{\pi}\otimes\hat{\nu}=\\{\hat{\pi}_{h}\otimes\hat{\nu}_{h}:\mathcal{S}\rightarrow\Delta(\mathcal{A})\times\Delta(\mathcal{B})\\}_{h\in[H]}$
be a product policy, $(\pi,\nu)$ be a policy pair, and
$(\widehat{Q}_{h})_{h\in[H]}$ be any estimated $Q$-functions. For any
$h\in[H]$ we define the estimated value function
$\widehat{V}_{h}:\mathcal{S}\rightarrow\mathbb{R}$ by setting
$\widehat{V}_{h}(s)=\langle\widehat{Q}_{h}(s,\cdot,\cdot),\hat{\pi}_{h}(\cdot|s)\otimes\hat{\nu}(\cdot|s)\rangle$,
for all $s\in\mathcal{S}$. Then, for all $s\in\mathcal{S}$, we have

$\displaystyle\widehat{V}_{1}(s)-V^{\pi,\nu}_{1}(s)$
$\displaystyle=\sum^{H}_{h=1}\mathbb{E}_{\pi,\nu}\left[\langle\widehat{Q}_{h}(s,\cdot,\cdot),\hat{\pi}_{h}(\cdot|s)\otimes\hat{\nu}(\cdot|s)-\pi(\cdot|s)\otimes\nu(\cdot|s)\rangle|s_{1}=s\right]$
$\displaystyle\quad+\sum^{H}_{h=1}\mathbb{E}_{\pi,\nu}\left[\widehat{Q}_{h}(s_{h},a_{h},b_{h})-(\mathbb{B}_{h}V_{h+1})(s_{h},a_{h},b_{h})|s_{1}=s\right]~{}.$

Now, the first term in the lemma above can be bounded by $0$ (see Lemma A.3 of
(Zhong et al., 2022)). Thus, we obtain

$\displaystyle\widehat{V}_{1}(s)-V^{\pi,\nu}_{1}(s)\leq\sum^{H}_{h=1}\mathbb{E}_{\pi,\nu}\left[\widehat{Q}_{h}(s_{h},a_{h},b_{h})-(\mathbb{B}_{h}V_{h+1})(s_{h},a_{h},b_{h})|s_{1}=s\right]~{}.$
(5)

Now we write the suboptimality gap as:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)=V^{*,\widehat{\nu}}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)=\left(V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)\right)+\left(V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)\right)~{}.$
(6)

For the first term, we have

$V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)\leq\overline{V}_{1}(s)-V^{*}_{1}(s)+\mathcal{E}_{1}\leq\overline{V}_{1}(s)-V^{\pi^{\prime},\nu^{*}}_{1}(s)+\mathcal{E}_{1}~{},$

for some $\pi^{\prime}$, where the first inequality follows from Lemma 3 and
the second inequality follows from the fact that $(\pi^{*},\nu^{*})$ is an NE
policy. Similarly, we have that $V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)\leq
V^{\pi^{*},\nu^{\prime}}_{1}(s)-\underline{V}_{1}(s)+\mathcal{E}_{1}$, for
some $\nu^{\prime}$. Then, Equation (5), Lemma 2 and Lemma 5 imply

$\displaystyle V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)$
$\displaystyle\leq\overline{V}_{1}(s)-V^{\pi^{\prime},\widehat{\nu}}_{1}(s)+\mathcal{E}_{1}(\epsilon,K,H,d,\sigma)$
$\displaystyle\leq\sum^{H}_{h=1}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[-\overline{\iota}_{h}(s_{h},a_{h},b_{h})\right]+H\mathcal{E}_{1}(\epsilon,K,H,d,\sigma)$
$\displaystyle\leq
2H\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\mathcal{E}_{1}(\epsilon,K,H,d,\sigma)|s_{1}=s\right]$
$\displaystyle\leq
2Hc_{1}(\delta)\cdot\left(\sqrt{\frac{\sigma^{2}poly(d)}{\kappa^{2}K}}+\frac{\sigma}{\kappa}\epsilon\right)$
$\displaystyle\leq
2Hc_{1}(\delta)\cdot\left(\sqrt{\frac{(H+\gamma)poly(d)}{\kappa^{2}K}}+\frac{H+\gamma}{\kappa}\epsilon\right)~{},$

where the last inequality follows from Lemma 4. Similarly, we have

$\displaystyle V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)$ $\displaystyle\leq
2Hc_{1}(\delta)\cdot\left(\sqrt{\frac{(H+\gamma)poly(d)}{\kappa^{2}K}}+\frac{H+\gamma}{\kappa}\epsilon\right)~{}.$

Finally, we obtain

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)$ $\displaystyle\leq
O\left(\sqrt{\frac{H(H+\gamma)^{2}poly(d)}{\kappa^{2}K}}+\frac{H(H+\gamma)}{\kappa}\epsilon\right)~{}.$

∎

####  A.3 Proof of Theorem 3

Given clean dataset
$\widetilde{D}=\\{(\tilde{x}_{1},\tilde{y}_{1}),\ldots,(\tilde{x}_{K},\tilde{y}_{K})\\}$,
consider the observation model

$\displaystyle\tilde{y}_{i}=\langle\omega^{*},\tilde{x}_{i}\rangle+\xi_{i}~{},$

where $\xi_{i}$ are $\gamma^{2}$-sub-Gaussian independent noise variables and
$\omega^{*}$ is the true regressor with $\left\lVert\omega^{*}\right\rVert\leq
R$, for some $R<\infty$, and $\left\lVert\tilde{x}_{i}\right\rVert_{2}\leq 1$,
for $i\in[K]$. Furthermore, given $\epsilon<1/2$, assume that
$\epsilon$-fraction of the outcomes in $\widetilde{D}$ are corrupted and let
$D=\\{(x_{1},y_{1}),\ldots,(x_{K},y_{K})\\}$ denote the corrupted dataset.
Formally, we assume that the covariates remain clean, that is,
$x_{i}=\tilde{x}_{i}$, for $i\in[K]$, and that, for any $i\in[K]$, a coin is
flipped with success rate $\epsilon$ to determine whether $\tilde{y}_{i}$ is
corrupted into $y_{i}$ or not.

Furthermore, let

$\displaystyle\Sigma=\frac{1}{K}\sum^{K}_{k=1}x_{k}x_{k}^{T}$

denote the covariance matrix of $D$. The following result (Chen et al., 2022a)
provides error norm bounds of the regressor estimated using the SCRAM method
on the corrupted dataset $D$.

######  Theorem 7.

Let $0<\epsilon<0.5$ be an upper bound on the contamination level, and suppose
$K$ satisfies $K\geq O(\log(\min\\{K,d\\})/\epsilon)$. Then, given
$\delta\in(0,1)$, there exists a $poly(K,d)$ algorithm which takes as input
the dataset $D$ and, with probability at least $1-\delta$, outputs a vector
$\omega$ that satisfies

$\displaystyle\left\lVert\omega^{*}-\omega\right\rVert_{\Sigma}\leq
O\left(\epsilon\gamma\log(1/\epsilon)+\min\left\\{\gamma\sqrt{\frac{d+\log(1/\delta)}{K}},(R\gamma)^{1/2}\sqrt[4]{\frac{\log(1/\delta)}{K}}\right\\}\right)~{}.$

For every $h\in[H]$, we define the datasets

$\displaystyle\widetilde{D}_{min}(h)=\\{\underbrace{\phi(\tilde{s}^{\tau}_{h},\tilde{a}^{\tau}_{h},\tilde{b}^{\tau}_{h})}_{\text{covariates}},\underbrace{\tilde{r}^{\tau}_{h}+\underline{V}_{h+1}(\tilde{s}^{\tau}_{h+1})}_{\text{clean
obs.}}\\}^{K}_{\tau=1}$

and

$\displaystyle\widetilde{D}_{max}(h)=\\{\phi(\tilde{s}^{\tau}_{h},\tilde{a}^{\tau}_{h},\tilde{b}^{\tau}_{h}),\tilde{r}^{\tau}_{h}+\overline{V}_{h+1}(\tilde{s}^{\tau}_{h+1}))\\}^{K}_{\tau=1}~{}.$

Similarly, the partitions of the corrupted data are defined as

$\displaystyle
D_{min}(h)=\\{\underbrace{\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})}_{\text{covariates}},\underbrace{r^{\tau}_{h}+\underline{V}_{h+1}(s^{\tau}_{h+1})}_{\text{$\epsilon$-corrupted
obs.}})\\}^{K}_{\tau=1}$

and

$\displaystyle
D_{max}(h)=\\{\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h}),r^{\tau}_{h}+\overline{V}_{h+1}(s^{\tau}_{h+1}))\\}^{K}_{\tau=1}~{}.$

Note that we assume
$\phi(\tilde{s}^{\tau}_{h},\tilde{a}^{\tau}_{h},\tilde{b}^{\tau}_{h})=\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$,
for all $\tau\in[K]$. Assumption 2 implies that there exist weight vectors
$\underline{\omega}^{*}_{h},\overline{\omega}^{*}_{h}\in\mathbb{R}^{d}$ such
that we have

$\displaystyle\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})^{\top}\underline{\omega}^{*}_{h}+\xi^{\tau}_{h}=(\mathbb{B}_{h}\underline{V}_{h+1})(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})+\xi^{\tau}_{h}=\left(\tilde{r}^{\tau}_{h}+\underline{V}_{h+1}(\tilde{s}^{\tau}_{h+1})\right)$
(7)

and

$\displaystyle\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})^{\top}\overline{\omega}^{*}_{h}+\xi^{\tau}_{h}=(\mathbb{B}_{h}\overline{V}_{h+1})(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})+\xi^{\tau}_{h}=\left(\tilde{r}^{\tau}_{h}+\overline{V}_{h+1}(\tilde{s}^{\tau}_{h+1})\right)~{},$
(8)

where $\xi^{\tau}_{h}$ are zero-mean $\gamma^{2}$-subGaussian random
variables.

Now, let us define the covariance matrices, for all $h\in[H]$, as:

$\displaystyle\Sigma_{h}=\frac{1}{K}\sum^{K}_{\tau=1}\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})^{\top}~{}.$

Note that $\Sigma_{h}$ depend on the triples
$(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$, $\tau\in[K]$, which are not
changed under corruption. Thus, the covariance matrices are clean. However,
the observations on both $\widetilde{D}_{min}(h)$ and
$\widetilde{D}_{max}(h)$, for all $h\in[H]$, are $\epsilon$-corrupted. Then,
Theorem 7 implies the following result.

######  Corollary 2.

Under the conditions of Theorem 7, there exist a $poly(K,d)$ algorithm that
returns a sequence of estimators
$(\underline{\omega}_{h},\overline{\omega}_{h})^{H}_{h=1}$ such that, given
$\delta>0$, the following inequalities are satisfied, for all $h\in[H]$, with
probability at least $1-\delta/2$:

$\displaystyle\left\lVert\underline{\omega}^{*}_{h}-\underline{\omega}_{h}\right\rVert_{\Sigma_{h}}$
$\displaystyle\leq
O\left(\gamma\epsilon\log(1/\epsilon)+\min\left\\{\gamma\sqrt{\frac{d+\log(8H/\delta)}{K}},\sqrt{H\gamma}\sqrt[4]{\frac{d\log(8H/\delta)}{K}}\right\\}\right)~{},$
(9)
$\displaystyle\left\lVert\overline{\omega}^{*}_{h}-\overline{\omega}_{h}\right\rVert_{\Sigma_{h}}$
$\displaystyle\leq
O\left(\gamma\epsilon\log(1/\epsilon)+\min\left\\{\gamma\sqrt{\frac{d+\log(8H/\delta)}{K}},\sqrt{H\gamma}\sqrt[4]{\frac{d\log(8H/\delta)}{K}}\right\\}\right)~{}.$
(10)

We will denote the right-hand side bound on the errors of norms by
$\mathcal{E}(\epsilon,K,H,d)$, as shorthand notation.

###### Proof.

The result follows immediately from Theorem 7 by applying the union bound over
$2H$ events, and also by noting that
$\left\lVert\underline{\omega}^{*}_{h}\right\rVert,\left\lVert\overline{\omega}^{*}_{h}\right\rVert\leq
H\sqrt{d}$, for all $h\in[H]$, by Lemma E.1 of (Zhong et al., 2022). ∎

Next, we prove the upper bounds on the Bellman error in terms of corruption
level and bonus term. Given
$(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$ and $h\in[H]$,
recall that the bonus term is defined as

$\displaystyle\Gamma_{h}(s,a,b)=\left(\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}\right)\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}~{},$

where

$\displaystyle\Lambda_{h}=\sum^{K}_{\tau=1}\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})\phi(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})^{\top}+I~{}.$

Note that $\Lambda_{h}$ is positive definite, and hence, invertible, since
$\Sigma_{h}$ is positive semi-definite.

From here on, let us use the following notation for ease of presentation. For
a given $(s,a,b)$ and $h\in[H]$, let

$\displaystyle\phi:=\phi(s,a,b),\;\;\text{and}\;\;\phi_{h}:=\phi(s_{h},a_{h},b_{h})~{}.$

######  Lemma 6.

Given tuple $(s,a,b)$, let $\underline{\iota}_{h}(s,a,b)$ and
$\overline{\iota}_{h}(s,a,b)$ be defined as in Lemma 2. Then, with probability
at least $1-\delta$, we have

$\displaystyle 0$ $\displaystyle\leq\underline{\iota}_{h}(s,a,b)\leq
2\Gamma_{h}(s,a,b)~{},$ (11) $\displaystyle 0$
$\displaystyle\leq-\overline{\iota}_{h}(s,a,b)\leq 2\Gamma_{h}(s,a,b)~{},$
(12)

for all $(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$.

###### Proof.

We will prove the first inequality, and the second will follow by symmetry of
argument. Let $\underline{\omega}^{*}_{h}$ be defined as in Equation 7. First,
note that Corollary 2 implies

$\displaystyle\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\Lambda_{h}}$
$\displaystyle=(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})^{\top}\Lambda_{h}(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})$
$\displaystyle=(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})^{\top}(K\Sigma_{h}+I)(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})$
$\displaystyle=K(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})^{\top}\Sigma_{h}(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})+(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})^{\top}I(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})$
$\displaystyle\leq
K\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\Sigma_{h}}+4H^{2}d$
$\displaystyle\leq K\mathcal{E}(\epsilon,K,H,d)^{2}+4H^{2}d$

where the first inequality comes from the fact that
$\left\lVert\underline{\omega}^{*}_{h}\right\rVert_{2}\leq H\sqrt{d}$, from
Lemma E.1 of (Zhong et al., 2022) and also
$\left\lVert\underline{\omega}_{h}\right\rVert_{2}\leq H\sqrt{d}$, by design
of SCRAM (Chen et al., 2022a). Thus, taking the square roots of both sides, we
obtain

$\displaystyle\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert_{\Lambda_{h}}$
$\displaystyle\leq\sqrt{K\mathcal{E}(\epsilon,K,H,d)^{2}+4H^{2}d}\leq\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}~{}.$
(13)

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

$\displaystyle|\phi^{\top}\underline{\omega}_{h}-(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)|$
$\displaystyle=|\phi^{\top}(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})|\leq\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert_{\Lambda_{h}}\left\lVert\phi\right\rVert_{\Lambda^{-1}_{h}}\leq\left(\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}\right)\left\lVert\phi\right\rVert_{\Lambda^{-1}_{h}}~{},$

where the first inequality follows from extended Cauchy-Schwarz.

Note that each of the bounds on the right-hand side of the last inequality
holds with probability at least $1-\delta/2$, thus, by union bound, the
inequality above holds with probability at least $1-\delta$. Therefore, we
obtain

$\displaystyle\phi^{\top}\underline{\omega}_{h}-\Gamma_{h}(s,a,b)\leq\mathbb{B}_{h}\underline{V}_{h+1}\leq
H-h+1~{},$

where in the last inequality we have used the fact that $|r_{h}|\leq 1$ and
$|\underline{V}_{h+1}(s)|\leq H-h$. Furthermore,

$\displaystyle\underline{Q}_{h}(s,a,b)=\max\\{0,\phi^{\top}\underline{\omega}_{h}-\Gamma_{h}(s,a,b)\\}\geq\phi^{\top}\underline{\omega}_{h}-\Gamma_{h}(s,a,b)~{}.$

Thus, we have

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)$
$\displaystyle\leq(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\phi^{\top}\underline{\omega}_{h}+\Gamma_{h}(s,a,b)$
$\displaystyle\leq 2\Gamma_{h}(s,a,b)~{}.$

To prove the non-negativity of $\underline{\iota}_{h}(s,a,b)$, we consider two
cases. First, if $\phi^{\top}\underline{\omega}_{h}-\Gamma_{h}(s,a,b)\geq 0$,
then we have

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-0\geq 0~{},$

since $\underline{V}_{h+1}(s)\in[0,H]$ and $r(s,a,b)\in[0,1]$. On the other
hand, if $\phi^{\top}\underline{\omega}_{h}-\Gamma_{h}(s,a,b)\leq 0$, we have

$\displaystyle\underline{\iota}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\underline{Q}_{h}(s,a,b)$
$\displaystyle=(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)-\phi^{\top}\underline{\omega}_{h}+\Gamma_{h}(s,a,b)\geq
0~{}.$

∎

Next, we give bounds on the best response values in terms of the estimated
value functions.

######  Lemma 7.

If Equations (11) and (12) in Lemma 6 hold, then, for any $s\in\mathcal{S}$,
we have

$\displaystyle\underline{V}_{h}(s)\leq
V^{\hat{\pi},*}_{h}(s),\;\;\text{and}\;\;V^{*,\hat{\nu}}_{h}(s)\leq\overline{V}_{h}(s)~{}.$

###### Proof.

This is an immediate implication of Lemma A.2 of (Zhong et al., 2022). ∎

The next result provides upper bounds on the expected values of the feature
norms, for all the trajectories followed by the policy pairs in the unilateral
set of the NE policy pair. This result is based on the Low Relative
Uncertainty assumption.

######  Lemma 8.

Assume that Assumption 3 holds, that is, assume that there exists a constant
$c_{1}>0$ such that, for all $h\in[H]$, we have

$\displaystyle\Lambda_{h}\succeq
I+c_{1}K\max\left\\{\sup_{\nu}\;\mathbb{E}_{\pi^{*},\nu}[\phi_{h}\phi_{h}^{\top}|s_{1}=x],\;\sup_{\pi}\;\mathbb{E}_{\pi,\nu^{*}}[\phi_{h}\phi_{h}^{\top}|s_{1}=x]\right\\}~{}.$

Then, for all $h\in[H]$, with probability at least $1-\delta$, we have

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]+\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]\leq
2\sqrt{\frac{d}{c_{1}K}}~{}.$

###### Proof.

We derive an upper bound for the first expectation. The argument is identical
to the second one. Let

$\displaystyle\overline{\Sigma}_{h}(x)=\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\phi(s_{h},a_{h},b_{h})^{\top}\phi(s_{h},a_{h},b_{h})|s_{1}=x\right]~{}.$
(14)

First, note that, given two matrices $A,B\in\mathbb{R}^{n\times n}$ such that
$A\preceq B$, then, for any $x\in\mathbb{R}^{n}_{+}$, we have $\left\lVert
x\right\rVert_{A}\leq\left\lVert x\right\rVert_{B}$. This follows immediately
by observing that, since $A-B\succeq 0$, which means that $A-B$ is positive
semi-definite, we obtain $x^{T}(A-B)x\geq 0$, which implies the desired
result. Now, for any $h\in[H]$, we have

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s_{h},a_{h},b_{h})\right\rVert_{\Lambda_{h}^{-1}}\right]$
$\displaystyle=\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\phi^{\top}_{h}\Lambda_{h}^{-1}\phi_{h}}\right]$
$\displaystyle\leq\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\phi^{\top}_{h}\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)^{-1}\phi_{h}}\big{|}s_{1}=x\right]$
$\displaystyle\leq\sqrt{\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[Tr\left(\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)^{-1}\phi_{h}\phi^{\top}_{h}\right)\bigg{|}s_{1}=x\right]}$
$\displaystyle=\sqrt{Tr\left(\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)^{-1}\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\phi_{h}\phi^{\top}_{h}\big{|}s_{1}=x\right]\right)}$
$\displaystyle=\sqrt{Tr\left(\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)^{-1}\overline{\Sigma}_{h}(x)\right)}$
$\displaystyle=\sqrt{\frac{1}{c_{1}K}Tr\left(\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)^{-1}\left(\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)-I\right)\right)}$
$\displaystyle=\sqrt{\frac{1}{c_{1}K}}\sqrt{Tr\left(I-\left(c_{1}K\overline{\Sigma}_{h}(x)+I\right)^{-1}\right)}$
$\displaystyle\leq\sqrt{\frac{d}{c_{1}K}}~{},$

where the first inequality follows by assumption; the second inequality
follows from Jensen; the second equality follows from the fact that
$Tr(\mathbb{E}X)=\mathbb{E}[Tr(X)]$, for a given random matrix $X$; for the
fourth equality, we have used the observation that $Tr(I-A)\leq\dim(A)$, for a
positive definite matrix $A$. ∎

Now we are ready to prove Theorem 3. We restate it below for convenience.

######  Statement.

Suppose that Assumption 3 holds with given constant $c_{1}$. Let $\delta>0$,
$\epsilon<1/2$ and let $D$ be the $\epsilon$-corrupted version of the dataset
$\widetilde{D}$ comprised of $K$ trajectories of length $H$, where
$K\geq\log(\min(K,d))/\epsilon$ and
$(\widetilde{s}^{\tau}_{h},\widetilde{a}^{\tau}_{h},\widetilde{b}^{\tau}_{h})=(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})$,
for all $\tau\in[K]$, $h\in[H]$. Then, with probability at least $1-\delta$,
SCRAM-PMVI outputs $(\widehat{\pi},\widehat{\nu})$ that satisfy, for every
$s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)$
$\displaystyle\leq\widetilde{O}\left(\frac{1}{\sqrt{c_{1}}}(\gamma+H)H\sqrt{d}\epsilon+\frac{H^{2}d}{\sqrt{c_{1}K}}\right)~{}.$

We decompose the suboptimality gap as in Equation (6):

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)=V^{*,\widehat{\nu}}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)=\left(V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)\right)+\left(V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)\right)~{}.$

First, we bound the left difference.

$\displaystyle
V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)\leq\overline{V}_{1}(s)-V^{*}_{1}(s)\leq\overline{V}_{1}(s)-V^{\pi^{\prime},\nu^{*}}_{1}(s)~{},$

for some $\pi^{\prime}$, where the first inequality follows from Lemma 7 and
the second inequality follows from the fact that $(\pi^{*},\nu^{*})$ is an NE
policy. Similarly, we have that $V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)\leq
V^{\pi^{*},\nu^{\prime}}_{1}(s)-\underline{V}_{1}(s)$, for some
$\nu^{\prime}$. Then, similar to the proof of Theorem 2, we have

$\displaystyle V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)$
$\displaystyle\leq\overline{V}_{1}(s)-V^{\pi^{\prime},\widehat{\nu}}_{1}(s)$
$\displaystyle\leq\sum^{H}_{h=1}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[-\overline{\iota}_{h}(s_{h},a_{h},b_{h})\right]$
$\displaystyle\leq
2\sum^{H}_{h=1}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\Gamma_{h}(s_{h},a_{h},b_{h})|s_{1}=s\right]$
$\displaystyle\leq
2\left(\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}\right)\sum^{H}_{h=1}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]$

Similarly, we have

$\displaystyle V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)$ $\displaystyle\leq
2\left(\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}\right)\sum^{H}_{h=1}\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]~{}.$

Finally, applying Lemma 8, we obtain

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)$ $\displaystyle\leq
2\left(\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}\right)\sum^{H}_{h=1}\left(\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]\right)$
$\displaystyle\leq
4\left(\sqrt{K}\mathcal{E}(\epsilon,K,H,d)+2H\sqrt{d}\right)\sum^{H}_{h=1}\sqrt{\frac{d}{c_{1}K}}$
$\displaystyle=O\left(\frac{\gamma}{c_{1}}H\sqrt{d}\epsilon+H^{2}K^{-1/2}d\right)$
$\displaystyle\leq
O\left(\frac{1}{c_{1}}(\gamma+H)H\sqrt{d}\epsilon+\frac{H^{2}d}{c_{1}\sqrt{K}}\right)~{},$

where the last inequality follows from Lemma 4.

###  Appendix B Proofs of Section 5

In this section, we derive the proofs of the results in Section 5.

####  B.1 Proof of Theorem 4

For this section, we prove a similar result which gives us general bounds when
no coverage is guaranteed on the corrupted dataset, but the underlying clean
data has LRU coverage.

First, since we assume corrupted covariates, we rewrite the overall covariance
as

$\displaystyle\Lambda_{h}=\widetilde{\Lambda}_{h}+\widehat{\Lambda}_{h}=\sum_{\text{clean}\;\tau}\widetilde{\phi}^{\tau}_{h}\left(\widetilde{\phi}^{\tau}_{h}\right)^{\top}+\sum_{\text{corrupted}\;\tau}\widehat{\phi}^{\tau}_{h}\left(\widehat{\phi}^{\tau}_{h}\right)^{\top}+I=(1-\epsilon)\left(K\widetilde{\Sigma}_{h}+I\right)+\epsilon\left(K\widehat{\Sigma}_{h}+I\right)$
(15)

We start by deriving upper bounds on the Bellman error.

######  Lemma 9.

With probability at least $1-\delta$, we have

$\displaystyle 0$ $\displaystyle\leq\underline{\iota}_{h}(s,a,b)\leq
2\widehat{\Gamma}_{h}(s,a,b)~{},$ $\displaystyle 0$
$\displaystyle\leq-\overline{\iota}_{h}(s,a,b)\leq
2\widehat{\Gamma}_{h}(s,a,b)~{},$

where

$\displaystyle\widehat{\Gamma}_{h}(s,a,b)=\left(\sqrt{(1-\epsilon)K}\mathcal{E}+(\sqrt{\epsilon
K}+2)H\sqrt{d}\right)\left\lVert\phi(s,a,b)\right\rVert_{\Lambda^{-1}_{h}}$

###### Proof.

Let us consider the first part. The second part will follow by a similar
argument. Similar to the argument of Lemma 6, we have

$\displaystyle\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\Lambda_{h}}$
$\displaystyle=(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})^{\top}\Lambda_{h}(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})$
$\displaystyle=(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})^{\top}\left((1-\epsilon)\left(K\widetilde{\Sigma}_{h}+I\right)+\epsilon\left(K\widehat{\Sigma}_{h}+I\right)\right)(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})$
$\displaystyle=(1-\epsilon)K\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\widetilde{\Sigma}_{h}}+\epsilon
K\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\widehat{\Sigma}_{h}}+H^{2}d$
$\displaystyle\leq(1-\epsilon)K\mathcal{E}^{2}+\epsilon
K\left\lVert\widehat{\Sigma}_{h}\right\rVert_{2}H^{2}d+4H^{2}d$
$\displaystyle\leq(1-\epsilon)K\mathcal{E}^{2}+\epsilon KH^{2}d+4H^{2}d~{}.$

Thus, we obtain

$\displaystyle\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert_{\Lambda_{h}}\leq\sqrt{(1-\epsilon)K}\mathcal{E}+(\sqrt{\epsilon
K}+2)H\sqrt{d}~{}.$

Then, similar to Lemma 6, with probability at least $1-\delta$, we have

$\displaystyle|\phi^{\top}\underline{\omega}_{h}-(\mathbb{B}_{h}\underline{V}_{h+1})(s,a,b)|$
$\displaystyle=|\phi^{\top}(\underline{\omega}_{h}-\underline{\omega}^{*}_{h})|\leq\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert_{\Lambda_{h}}\left\lVert\phi\right\rVert_{\Lambda^{-1}_{h}}\leq\left(\sqrt{(1-\epsilon)K}\mathcal{E}+(\sqrt{\epsilon
K}+2)H\sqrt{d}\right)\left\lVert\phi\right\rVert_{\Lambda^{-1}_{h}}~{}.$

The rest of the proof follows similar arguments to Lemma 6. ∎

Next, we derive upper bounds on the additional error term coming from the
damage on coverage.

######  Lemma 10.

Assume that the condition of Lemma 8 holds only for the underlying clean data,
but not for the corrupted dataset. Then, we have

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]+\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda_{h}^{-1}}\right]\leq
2\left(\sqrt{\frac{d}{c_{1}K}}+\sqrt{\frac{d\epsilon}{c_{1}K(1-\epsilon)}}\right)~{}.$

###### Proof.

First, using the definition of $\Lambda_{h}$, we can equivalently write
$\Lambda_{h}=S_{h}-\Delta_{h}$, where

$\displaystyle
S_{h}=\sum^{K}_{\tau=1}\widetilde{\phi}^{\tau}_{h}\left(\widetilde{\phi}^{\tau}_{h}\right)^{\top}+I$
(16)

is the clean sample covariance matrix coming from $\widetilde{D}$, and
$\Delta_{h}$ is defined as

$\displaystyle\Delta_{h}=\sum_{\textrm{corrupted
}\tau}\tilde{\phi}_{h}^{\tau}\tilde{\phi}_{h}^{\tau^{\top}}-{\phi}_{h}^{\tau}{\phi}_{h}^{\tau^{\top}}~{}.$
(17)

Since $\Delta_{h}$ is a symmetric matrix, we can write
$\Delta_{h}=U_{h}E_{h}U_{h}^{\top}$, where $E_{h}$ is a diagonal matrix
composed of the eigenvalues of $\Delta_{h}$. Note that the absolute value of
each entry of $E_{h}$ is at most $\epsilon K$. We will use the following
formula for the inverse of a sum of two matrices (Henderson and Searle, 1981):

$(A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}~{},$

provided that $I+BVA^{-1}U$ is non-singular. In contrast to the Woodbury
matrix identity, the matrix $B$ here can be non-invertible. Using $A=S_{h}$
and $UBV=-U_{h}E_{h}U_{h}^{\top}$ we get the following identity.

$\displaystyle\Lambda_{h}^{-1}=\left(S_{h}-\Delta_{h}\right)^{-1}=\left(S_{h}-U_{h}E_{h}U_{h}^{\top}\right)^{-1}=S_{h}^{-1}+S_{h}^{-1}\underbrace{U_{h}\left(I-E_{h}U_{h}^{\top}S_{h}^{-1}U_{h}\right)^{-1}E_{h}U_{h}^{\top}}_{:=M_{h}}S_{h}^{-1}~{}.$
(18)

This identity gives us the following bound on the bonus term with respect to
$\pi^{*}$ and $\nu^{\prime}$.

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s_{h},a_{h},b_{h})\right\rVert_{\Lambda_{h}^{-1}}\right]$
$\displaystyle=\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\phi^{\top}_{h}\Lambda_{h}^{-1}\phi_{h}}\right]\leq\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\phi^{\top}_{h}S_{h}^{-1}\phi_{h}}\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\left|\phi^{\top}_{h}S_{h}^{-1}M_{h}S_{h}^{-1}\phi_{h}\right|}\right]$
(19)

The first term can be bounded by $\sqrt{\frac{d}{c_{1}K}}$ by Lemma 8, since
it depends on the clean covariance matrix. For the second term, we first upper
bound the maximum eigenvalue of the inverse of the middle expression in
$M_{h}$. For that, we make use of the following Lemma.

######  Lemma 11.

Given $\Sigma_{h}(x)$ as defined in Equation (14), $S_{h}$ as defined in
Equation (16), $\Delta_{h}=U_{h}S_{h}U_{h}^{\top}$ as defined in Equation
(17), and $M_{h}$ as in Equation (18), we have

$\displaystyle
Tr\left(S^{-1}_{h}M_{h}S^{-1}_{h}\Sigma_{h}(x)\right)\leq\frac{d\epsilon}{c_{1}K(1-\epsilon)}~{}.$

###### Proof.

First, note that, since $U_{h}$ is an orthonormal matrix, we can write

$\displaystyle
E_{h}U_{h}^{\top}S_{h}^{-1}U_{h}=E_{h}U_{h}^{-1}S_{h}^{-1}U_{h}=E_{h}\left(S_{h}U_{h}\right)^{-1}U_{h}~{}.$

Next, observe that

$\displaystyle\left\lVert S_{h}U_{h}\right\rVert_{2}$
$\displaystyle=\max_{x\neq 0}\frac{\left\lVert
U_{h}x+\sum^{K}_{\tau=1}\widetilde{\phi}_{h}^{\tau}(\widetilde{\phi}_{h}^{\tau})^{\top}U_{h}x\right\rVert_{2}}{\left\lVert
x\right\rVert_{2}}$ $\displaystyle\leq\max_{x\neq 0}\frac{\left\lVert
U_{h}x\right\rVert_{2}+\left\lVert\sum^{K}_{\tau=1}\widetilde{\phi}_{h}^{\tau}(\widetilde{\phi}_{h}^{\tau})^{\top}\right\rVert_{2}\left\lVert
U_{h}x\right\rVert_{2}}{\left\lVert x\right\rVert_{2}}$
$\displaystyle\leq\max_{x\neq 0}\frac{\left\lVert
x\right\rVert_{2}+K\left\lVert x\right\rVert_{2}}{\left\lVert
x\right\rVert_{2}}$ $\displaystyle=1+K~{},$

where the first inequality follows by the triangle inequality and matrix norm
properties, and for the second inequality we have used the fact that the
maximum eigenvalue of the clean covariance matrix does not exceed $1+K$. This
implies that

$\left(S_{h}U_{h}\right)^{-1}\succcurlyeq\frac{1}{1+K}I_{d}$

and, consequently,

$\displaystyle
I-E_{h}U_{h}^{\top}S_{h}^{-1}U_{h}\succcurlyeq\left(1-\frac{\epsilon
K}{1+K}\right)I_{d}~{},$ (20)

since the minimum eigenvalue of $-E_{h}$ is at least $-\epsilon K$. Thus, we
obtain

$\displaystyle\left(I-E_{h}U_{h}^{\top}S_{h}^{-1}U_{h}\right)^{-1}\preceq\frac{1}{1-\frac{\epsilon
K}{1+K}}I_{d}~{}\preceq\frac{1}{1-\epsilon}I_{d}~{}.$

Using the argument above, we have

$\displaystyle Tr\left(S^{-1}_{h}M_{h}S^{-1}_{h}\Sigma_{h}(x)\right)$
$\displaystyle=Tr\left(S^{-1}_{h}U_{h}\left(I-E_{h}U_{h}^{\top}S^{-1}_{h}U_{h}\right)^{-1}E_{h}U_{h}^{\top}S^{-1}_{h}U_{h}U_{h}^{\top}\Sigma_{h}(x)\right)$
$\displaystyle=Tr\left(S^{-1}_{h}U_{h}\left(\underbrace{\left(I-E_{h}U_{h}^{\top}S^{-1}_{h}U_{h}\right)^{-1}}_{A}-I\right)U_{h}^{\top}\Sigma_{h}(x)\right)$
$\displaystyle\leq\frac{1}{c_{1}K}Tr\left(U_{h}\left(A-I\right)U_{h}^{\top}\left(c_{1}K\Sigma_{h}(x)+I-I\right)\underbrace{\left(c_{1}K\Sigma_{h}(x)+I\right)^{-1}}_{B}\right)$
$\displaystyle=\frac{1}{c_{1}K}Tr\left(U_{h}\left(A-I\right)U_{h}^{\top}\left(I-B\right)\right)$
$\displaystyle\leq\frac{d}{c_{1}K}\left\lVert
U_{h}\left(A-I\right)U_{h}^{\top}\left(I-B\right)\right\rVert_{2}$
$\displaystyle\leq\frac{d}{c_{1}K}\left\lVert A-I\right\rVert_{2}\left\lVert
I-B\right\rVert_{2}$
$\displaystyle\leq\frac{d}{c_{1}K}\left(\frac{1}{1-\epsilon}-1\right)$
$\displaystyle=\frac{d\epsilon}{c_{1}K(1-\epsilon)}~{},$

where the first inequality uses Assumption 3 and the fact that $S^{-1}_{h}$ is
symmetric; the second inequality uses the fact that $Tr(A)\leq d\left\lVert
A\right\rVert_{2}$; the third inequality uses the property $\left\lVert
AB\right\rVert_{2}\leq\left\lVert A\right\rVert_{2}\left\lVert
B\right\rVert_{2}$, and the fact that, for orthonormal matrices, we have
$\left\lVert U_{h}\right\rVert_{2}\leq 1$. Thus, by putting everything
together, we obtain the desired bounds. ∎

Now, note that

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\phi^{\top}S^{-1}_{h}M_{h}S^{-1}_{h}\phi_{h}}\right]$
$\displaystyle\leq\sqrt{Tr\left(S^{-1}_{h}M_{h}S^{-1}_{h}\Sigma_{h}(x)\right)}\leq\sqrt{\frac{d\epsilon}{c_{1}K(1-\epsilon)}}~{},$

by Lemma 11. Thus, by putting everything together, we obtain

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s_{h},a_{h},b_{h})\right\rVert_{\Lambda^{-1}_{h}}\right]\leq\sqrt{\frac{d}{c_{1}K}}+\sqrt{\frac{d\epsilon}{c_{1}K(1-\epsilon)}}~{}.$

∎

Now we are ready to prove the main result of this section. We restate the
result for convenience.

######  Statement.

Suppose that the condition of Assumption 3 is satisfied only on the clean
dataset $\widetilde{D}$, for a given constant $c_{1}$, and that an
$\epsilon$-fraction of tuples in $D$ is arbitrarily corrupted. Furthermore,
let $\delta>0$ and $\epsilon\in(0,1/2)$, and
$K\geq\log(\min\\{K,d\\})/\epsilon$. Then, with probability at least
$1-\delta$, $S-PMVI$ returns $(\widehat{\pi},\widehat{\nu})$ that satisfy, for
any $s\in\mathcal{S}$

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)\leq
O\left(\underbrace{\frac{1}{\sqrt{c_{1}K}}H^{2}d}_{\begin{subarray}{c}\text{clean
signal}\\\ \text{\& clean covariates}\\\ \text{\& LRU
coverage}\end{subarray}}+\underbrace{\frac{1}{\sqrt{c_{1}}}H^{2}\sqrt{d}\epsilon}_{\begin{subarray}{c}\text{corrupted
signal}\\\ \text{\& clean covariates}\\\ \text{\& LRU
coverage}\end{subarray}}+\underbrace{\frac{1}{\sqrt{c_{1}}}H^{2}d\sqrt{\epsilon}}_{\begin{subarray}{c}\text{corrupted
signal}\\\ \text{\& corrupted covariates}\\\ \text{\& LRU
coverage}\end{subarray}}+\underbrace{\frac{1}{\sqrt{c_{1}(1-\epsilon)}}H^{2}d^{3/2}\epsilon}_{\begin{subarray}{c}\text{corrupted
signal}\\\ \text{\& corrupted covariates}\\\ \text{\& corrupted
coverage}\end{subarray}}\right)$

###### Proof.

As in the proof of Theorem 3, we have, for some policies $\pi^{\prime}$ and
$\nu^{\prime}$:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)$
$\displaystyle=V^{*,\widehat{\nu}}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)=\left(V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)\right)+\left(V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)\right)$
$\displaystyle\leq\left(\overline{V}_{1}(s)-V^{\pi^{\prime},\nu^{*}}_{1}(s)\right)+\left(V^{\pi^{*},\nu^{\prime}}_{1}(s)-\underline{V}_{1}(s)\right)$
(21)
$\displaystyle\leq\sum^{H}_{h=1}\bigg{(}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[-\overline{\iota}_{h}(s_{h},a_{h},b_{h})\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\underline{\iota}_{h}(s_{h},a_{h},b_{h})\right]\bigg{)}$
(22) $\displaystyle\leq
2\sum^{H}_{h=1}\bigg{(}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\widehat{\Gamma}_{h}(s,a,b)|s_{1}=s\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\widehat{\Gamma}_{h}(s,a,b)|s_{1}=s\right]\bigg{)}$
(23) $\displaystyle\leq 2\left(\sqrt{(1-\epsilon)K}\mathcal{E}+(\sqrt{\epsilon
K}+2)H\sqrt{d}\right)\sum^{H}_{h=1}\left(\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda^{-1}_{h}}\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s,a,b)\right\rVert_{\Lambda^{-1}_{h}}\right]\right)$
$\displaystyle\leq 4H\left(\sqrt{(1-\epsilon)K}\mathcal{E}+\sqrt{\epsilon
Kd}H+2H\sqrt{d}\right)\left(\sqrt{\frac{d}{c_{1}K}}+\sqrt{\frac{d\epsilon}{c_{1}K(1-\epsilon)}}\right)$
(24) $\displaystyle\leq
O\left(\underbrace{\frac{1}{\sqrt{c_{1}K}}H^{2}d}_{\begin{subarray}{c}\text{clean
signal}\\\ \text{\& clean covariates}\\\ \text{\& LRU
coverage}\end{subarray}}+\underbrace{\frac{1}{\sqrt{c_{1}}}H^{2}\sqrt{d}\epsilon}_{\begin{subarray}{c}\text{corrupted
signal}\\\ \text{\& clean covariates}\\\ \text{\& LRU
coverage}\end{subarray}}+\underbrace{\frac{1}{\sqrt{c_{1}}}H^{2}d\sqrt{\epsilon}}_{\begin{subarray}{c}\text{corrupted
signal}\\\ \text{\& corrupted covariates}\\\ \text{\& LRU
coverage}\end{subarray}}+\underbrace{\frac{1}{\sqrt{c_{1}(1-\epsilon)}}H^{2}d\epsilon}_{\begin{subarray}{c}\text{corrupted
signal}\\\ \text{\& corrupted covariates}\\\ \text{\& corrupted
coverage}\end{subarray}}\right)$ $\displaystyle\leq
O\left(H^{2}d^{3/2}K^{-1/2}+H^{2}d^{3/2}\sqrt{\epsilon}\right)~{},$ (25)

where (21) follows from Lemma 3; (21) follows from Equation (5); (23) follows
from Lemma 6; (24) follows from Lemma 10 and (25) follows from the fact that,
for $\epsilon\in(0,1/2)$, we have that
$\epsilon/\sqrt{1-\epsilon}\leq\sqrt{\epsilon}$. ∎

####  B.2 Proof of Theorem 5

In this section, we improve the order of $\epsilon$ in Theorem 4 under an
additional assumption on the feature space (Assumption 4. We start by proving
upper bounds on the Bellman error in terms of the bonus term.

######  Lemma 12.

With probability at least $1-\delta$, we have

$\displaystyle 0$ $\displaystyle\leq\underline{\iota}_{h}(s,a,b)\leq
2\widehat{\Gamma}_{h}(s,a,b)~{},$ $\displaystyle 0$
$\displaystyle\leq-\overline{\iota}_{h}(s,a,b)\leq
2\widehat{\Gamma}_{h}(s,a,b)~{},$

for all $(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$ and
$h\in[H]$, where

$\displaystyle\widehat{\Gamma}_{h}(s,a,b)=\left(2(1-\epsilon)K\mathcal{E}+\epsilon
KH\sqrt{d}+H\sqrt{Kd}\right)\left\lVert\phi(s,a,b)^{\top}\Lambda^{-1}_{h}\right\rVert_{2}~{}.$

###### Proof.

First, we express the Bellman error of any given $(s,a,b)$ tuple at time-step
$h$ as

$\displaystyle\left|\overline{Q}_{h}(s,a,b)-(\mathbb{B}_{h}\overline{V}_{h+1})(s,a,b)\right|=\left|\phi^{\top}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|=\left|\phi^{\top}_{h}\Lambda^{-1}_{h}\Lambda_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|\leq\left\lVert\phi^{\top}_{h}\Lambda^{-1}_{h}\right\rVert_{2}\left\lVert\Lambda_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right\rVert_{2}~{}.$

The error coming from the second player is similarly bounded. Note that we
have

$\displaystyle\left\lVert\Lambda_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right\rVert^{2}_{2}=\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\left(\widetilde{\Lambda}_{h}+\widehat{\Lambda}_{h}\right)^{2}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|$
$\displaystyle=\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\left(\widetilde{\Lambda}^{2}_{h}+\widetilde{\Lambda}_{h}\widehat{\Lambda}_{h}+\widehat{\Lambda}_{h}\widetilde{\Lambda}_{h}+\widehat{\Lambda}_{h}^{2}\right)\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|$
$\displaystyle\leq\underbrace{\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\widetilde{\Lambda}^{2}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|}_{P_{1}}+\underbrace{\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\left(\widetilde{\Lambda}_{h}\widehat{\Lambda}_{h}+\widehat{\Lambda}_{h}\widetilde{\Lambda}_{h}\right)\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|}_{P_{2}}+\underbrace{\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\widehat{\Lambda}^{2}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|}_{P_{3}}$

We derive upper bounds for the three terms above separately. First, we have

$\displaystyle P_{1}$
$\displaystyle=(1-\epsilon)\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\left(K\widetilde{\Sigma}_{h}+I\right)\widetilde{\Lambda}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|$
$\displaystyle\leq(1-\epsilon)\left\lVert\widetilde{\Lambda}_{h}\right\rVert_{2}\left(K\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\widetilde{\Sigma}_{h}}+H^{2}d\right)$
$\displaystyle\leq(1-\epsilon)^{2}K^{2}\mathcal{E}^{2}+(1-\epsilon)^{2}KH^{2}d~{},$

where the first equality follows from Equation (15), the first inequality
follows from the fact that $\langle x,Ax\rangle\leq\left\lVert
A\right\rVert_{2}\left\lVert x\right\rVert^{2}_{2}$ and the last inequality
follows from the fact that the maximum eigenvalue of $\widetilde{\Lambda}_{h}$
is at most $(1-\epsilon)K$, the fact that
$\left\lVert\underline{\omega}^{*}_{h}\right\rVert_{2}\leq H\sqrt{d}$ (Lemma
E.1 of Zhong et al. (2022)) and Corollary 2, where we deliberately omit the
dependencies of $\mathcal{E}$ for brevity.

Next, we have

$\displaystyle P_{2}$
$\displaystyle\leq\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\widetilde{\Lambda}_{h}\widehat{\Lambda}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|+\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\widehat{\Lambda}_{h}\widetilde{\Lambda}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\right|$
$\displaystyle\leq
2\left\lVert\widehat{\Lambda}_{h}\right\rVert_{2}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\widetilde{\Lambda}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)$
$\displaystyle\leq 2\epsilon
K\left(K\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{\widetilde{\Sigma}_{h}}+H^{2}d\right)$
$\displaystyle=2\epsilon(1-\epsilon)K^{2}\mathcal{E}^{2}+2\epsilon(1-\epsilon)KH^{2}d~{},$

where we have used the fact that the maximum eigenvalue of
$\widehat{\Lambda}_{h}$ is at most $\epsilon K$ and applied similar arguments
as for $P_{1}$. For the last term, we have

$\displaystyle P_{3}$
$\displaystyle=\epsilon\left|\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)^{\top}\left(K\widehat{\Sigma}_{h}+I\right)\widehat{\Lambda}_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right|$
$\displaystyle\leq\epsilon\left\lVert\widehat{\Lambda}_{h}\right\rVert_{2}\left(K\left\lVert\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right\rVert^{2}_{2}\left\lVert\widehat{\Sigma}_{h}\right\rVert_{2}+H^{2}d\right)$
$\displaystyle\leq\epsilon^{2}K\left(KH^{2}d+H^{2}d\right)$
$\displaystyle=\epsilon^{2}K^{2}H^{2}d+\epsilon^{2}KH^{2}d~{},$

by applying the same arguments as above. Putting everything together, we
obtain

$\displaystyle\left\lVert\Lambda_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right\rVert^{2}_{2}$
$\displaystyle\leq P_{1}+P_{2}+P_{3}$
$\displaystyle=(1-\epsilon)^{2}K^{2}\mathcal{E}^{2}+(1-\epsilon)^{2}KH^{2}d+2\epsilon(1-\epsilon)K^{2}\mathcal{E}^{2}+2\epsilon(1-\epsilon)KH^{2}d+\epsilon^{2}K^{2}H^{2}d+\epsilon^{2}KH^{2}d$
$\displaystyle=(1-\epsilon)^{2}K^{2}\mathcal{E}^{2}+2\epsilon(1-\epsilon)K^{2}\mathcal{E}^{2}+\epsilon^{2}K^{2}H^{2}d+\left((1-\epsilon)H\sqrt{Kd}+\epsilon
H\sqrt{Kd}\right)^{2}$ $\displaystyle\leq
3(1-\epsilon)^{2}K^{2}\mathcal{E}^{2}+\epsilon^{2}K^{2}H^{2}d+KH^{2}d~{},$

where the last inequality follows from the fact that $\epsilon<1/2$. Taking
the square root of both sides and using the triangle inequality, we finally
obtain

$\displaystyle\left\lVert\Lambda_{h}\left(\underline{\omega}_{h}-\underline{\omega}^{*}_{h}\right)\right\rVert_{2}\leq
2(1-\epsilon)K\mathcal{E}+\epsilon KH\sqrt{d}+H\sqrt{Kd}~{}.$

∎

Next, we derive an upper bound on the expected value of the feature norms with
respect to policy pairs lying in the LRU set.

######  Lemma 13.

Assume that Assumption 3 holds on the clean dataset $\widetilde{D}$ only, with
given constant $c_{1}>0$. Then, for all $h\in[H]$, with probability at least
$1-\delta$, we have

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s_{h},a_{h},b_{h})^{\top}\Lambda^{-1}_{h}\right\rVert_{2}\right]+\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s_{h},a_{h},b_{h})^{\top}\Lambda^{-1}_{h}\right\rVert_{2}\right]\leq
2\left(\frac{d}{c_{1}c_{2}K}+\frac{d\epsilon}{c_{1}c_{2}K(1-\epsilon)}\right)~{},$

where $c_{2}\leq\min_{\phi\in\Phi}\left\lVert\phi\right\rVert_{2}$.

###### Proof.

Using the short-hand notation $\phi_{h}$ instead of $\phi(s_{h},a_{h},b_{h})$,
we have

$\displaystyle\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi_{h}^{\top}\Lambda^{-1}_{h}\right\rVert_{2}\right]$
$\displaystyle\leq\frac{1}{c_{2}}\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{\phi^{\top}_{h}\left(S^{-1}_{h}+S^{-1}_{h}M_{h}S^{-1}_{h}\right)^{2}\phi_{h}\phi^{\top}_{h}\phi_{h}}\right]$
$\displaystyle=\frac{1}{c_{2}}\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\sqrt{Tr\left(S^{-2}_{h}\left(I+M_{h}S^{-1}_{h}\right)^{2}\left(\phi_{h}\phi^{\top}_{h}\right)^{2}\right)}\right]$
$\displaystyle\leq\frac{1}{c_{2}}\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[Tr\left(S^{-1}_{h}\left(I+M_{h}S^{-1}_{h}\right)\phi_{h}\phi^{\top}_{h}\right)\right]$
$\displaystyle=\frac{1}{c_{2}}Tr\left(S^{-1}_{h}\left(I+M_{h}S^{-1}_{h}\right)\left(\Sigma_{h}(x)\right)\right)$
$\displaystyle\leq\frac{1}{c_{2}}\left(Tr\left(S^{-1}_{h}\Sigma_{h}(x)\right)+Tr\left(S^{-1}_{h}M_{h}S^{-1}_{h}\Sigma_{h}(x)\right)\right)~{}.$

The first factor is bounded as

$\displaystyle Tr\left(S^{-1}_{h}\Sigma_{h}(x)\right)\leq\frac{d}{c_{1}K}$

by Lemma 8, while the second term is bounded as

$\displaystyle
Tr\left(S^{-1}_{h}M_{h}S^{-1}_{h}\Sigma_{h}(x)\right)\leq\frac{d\epsilon}{c_{1}K(1-\epsilon)}~{},$

by Lemma 11. The result follows. ∎

######  Statement.

Suppose that the conditions of Theorem 4 and Assumption 4 hold. Then, with
probability at least $1-\delta$, $S-PMVI$ returns
$(\widehat{\pi},\widehat{\nu})$ that satisfy, for any $s\in\mathcal{S}$:

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)\leq
O\left(\frac{1}{c_{1}c_{2}}H^{2}d^{3/2}K^{-1/2}+\frac{1}{c_{1}c_{2}}H^{2}d^{3/2}\epsilon\right)~{}.$

###### Proof.

Again, as in Theorem 3, we have

$\displaystyle\text{SubOpt}(\widehat{\pi},\widehat{\nu},s)=V^{*,\widehat{\nu}}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)=\left(V^{*,\widehat{\nu}}_{1}(s)-V^{*}_{1}(s)\right)+\left(V^{*}_{1}(s)-V^{\widehat{\pi},*}_{1}(s)\right)$
$\displaystyle\leq\sum^{H}_{h=1}\bigg{(}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[-\overline{\iota}_{h}(s_{h},a_{h},b_{h})\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\underline{\iota}_{h}(s_{h},a_{h},b_{h})\right]\bigg{)}$
$\displaystyle\leq
2\sum^{H}_{h=1}\bigg{(}\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\widehat{\Gamma}_{h}(s,a,b)|s_{1}=s\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\widehat{\Gamma}_{h}(s,a,b)|s_{1}=s\right]\bigg{)}$
$\displaystyle\leq 2\left(2(1-\epsilon)K\mathcal{E}+\epsilon
KH\sqrt{d}+H\sqrt{Kd}\right)\sum^{H}_{h=1}\left(\mathbb{E}_{\pi^{\prime},\nu^{*}}\left[\left\lVert\phi(s,a,b)^{\top}\Lambda^{-1}_{h}\right\rVert_{2}\right]+\mathbb{E}_{\pi^{*},\nu^{\prime}}\left[\left\lVert\phi(s,a,b)^{\top}\Lambda^{-1}_{h}\right\rVert_{2}\right]\right)$
(26) $\displaystyle\leq 4H\left(2(1-\epsilon)K\mathcal{E}+\epsilon
KH\sqrt{d}+H\sqrt{Kd}\right)\sum^{H}_{h=1}\left(\frac{d}{c_{1}c_{2}K}+\frac{d\epsilon}{c_{1}c_{2}K(1-\epsilon)}\right)$
(27) $\displaystyle\leq
O\left(\frac{1}{c_{1}c_{2}}H^{2}d^{3/2}K^{-1/2}+\frac{1}{c_{1}c_{2}}H^{2}d^{3/2}\epsilon\right)~{},$

where (27) follows from Lemma 12, and (27) follows from Lemma 13 . ∎

###  Appendix C Proofs of Section 6

In this section, we provide the proofs of results related to coverage
assumptions in Section 6.

####  C.1 Proof of Proposition 1

Before proving Proposition 1, we state a result that provides bounds on the
concentration of covariance matrices. For proof see (Zanette et al., 2021a).

######  Lemma 14.

Let $\\{\phi_{i}\\}_{i\in[K]}\subset\mathbb{R}^{d}$ be i.i.d. samples from an
underlying bounded distribution $\nu$, with
$\left\lVert\phi_{i}\right\rVert_{2}\leq 1$, for $i\in[K]$ and covariance
$\Sigma$. Define

$\Lambda=\sum^{K}_{k=1}\phi_{i}\phi_{i}^{\top}+\lambda I~{},$

where $\lambda\geq\Omega(d\log(K/\delta))$. Then, with probability at least
$1-\delta$, we have

$\frac{1}{3}(K\Sigma+\lambda
I)\preceq\Lambda\preceq\frac{5}{3}(K\Sigma+\lambda I)~{}.$

We restate Proposition 1.

######  Statement.

Assume $\Phi$ has full rank and let $\delta\in(0,1)$. Then, if Assumption 6
holds, there exists a positive constant that depends on $\delta$ for which
Assumption 3 holds, with probability at least $1-\delta$. Moreover, in the
tabular MG setting, these two assumptions are equivalent.

###### Proof.

Fix $x\in\mathcal{S}$. Given policy pair $(\pi,\nu)$ and $h\in[H]$, let the
matrix $D^{\pi,\nu}_{h}\in\mathbb{R}^{SAB\times SAB}$ denote the diagonal
matrix composed of $d^{\pi,\nu}_{h}(s,a,b)$ diagonal entries, where we set
$d^{\pi,\nu}_{1}(x,a,b)=1$. Note that

$\mathbb{E}_{\pi,\nu}\left[\phi(s_{h},a_{h},b_{h})\phi(s_{h},a_{h},b_{h})^{\top}|s_{1}=x\right]=\Phi^{\top}D^{\pi,\nu}_{h}\Phi~{}.$
(28)

Further, let us denote by $\rho$ the behavioral policy from which the clean
tuples $(s,a,b)$ from the given offline data are sampled and let us define the
diagonal matrix $D^{\rho}_{\tau,h}\in\mathbb{R}^{SAB\times SAB}$, for every
$\tau\in[K],h\in[H]$, with diagonal entries

$\widetilde{D}^{\rho}_{\tau,h}[(s,a,b)]:=\widetilde{d}^{\rho}_{\tau,h}(s,a,b)=\begin{cases}1\;\;\text{if}\;(s^{\tau}_{h},a^{\tau}_{h},b^{\tau}_{h})=(s,a,b)\\\
0\;\;\text{otherwise}\end{cases}$

and let

$\widehat{D}^{\rho}_{h}=\frac{1}{K}\sum^{K}_{\tau=1}\widetilde{D}^{\rho}_{\tau,h}$

denote the sample covariance matrix. By assumption, there exists a finite
positive constant $c$ such that

$\frac{d^{\pi,\nu}_{h}(s,a,b)}{d^{\rho}_{h}(s,a,b)}<c<\infty,\forall
h\in[H],(\pi,\nu)\in\mathcal{U}(\pi^{*},\nu^{*}),(s,a,b)\in\\{(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}:d^{\pi,\nu}_{h}(s,a,b)>0\\}~{},$

where
$\mathcal{U}(\pi^{*},\nu^{*})=\\{(\pi^{*},\nu),(\pi,\nu^{*}),\forall\pi,\forall\nu\\}$.
This implies that

$\min_{(s,a,b)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}}\left(d^{\rho}_{h}(s,a,b)-\frac{1}{c}d^{\pi,\nu}_{h}(s,a,b)\right)\geq
0~{},$ (29)

which implies that

$D^{\rho}_{h}-\frac{1}{c}D^{\pi,\nu}_{h}\succeq 0~{}.$ (30)

Now, Lemma 14 implies that there exist constants
$\lambda_{h}\geq\Omega(d\log(KH/\delta))$, for $h\in[H]$, such that, with
probability at least $1-\delta$, we have

$\frac{1}{3}(KD^{\rho}_{h}+\lambda_{h}I)\preceq\sum^{K}_{k=1}\widetilde{D}^{\rho}_{k,h}+\lambda_{h}I\preceq\frac{5}{3}(KD^{\rho}_{h}+\lambda_{h}I)~{},$

for all $h\in[H]$. This implies that