# The Role of Inherent Bellman Error in Offline Reinforcement Learning with
Linear Function Approximation

Noah Golowich
MIT Email<EMAIL_ADDRESS>Supported by a Fannie & John Hertz Foundation
Fellowship and an NSF Graduate Fellowship. Ankur Moitra
MIT Email<EMAIL_ADDRESS>Supported in part by a Microsoft Trustworthy AI
Grant, an ONR grant and a David and Lucile Packard Fellowship.

###### Abstract

In this paper, we study the offline RL problem with linear function
approximation. Our main structural assumption is that the MDP has _low
inherent Bellman error_ , which stipulates that linear value functions have
linear Bellman backups with respect to the greedy policy. This assumption is
natural in that it is essentially the minimal assumption required for value
iteration to succeed. We give a computationally efficient algorithm which
succeeds under a _single-policy coverage_ condition on the dataset, namely
which outputs a policy whose value is at least that of any policy which is
well-covered by the dataset. Even in the setting when the inherent Bellman
error is 0 (termed _linear Bellman completeness_), our algorithm yields the
first known guarantee under single-policy coverage.

In the setting of positive inherent Bellman error
$\varepsilon_{\mathsf{BE}}>0$, we show that the suboptimality error of our
algorithm scales with $\sqrt{\varepsilon_{\mathsf{BE}}}$. Furthermore, we
prove that the scaling of the suboptimality with
$\sqrt{\varepsilon_{\mathsf{BE}}}$ cannot be improved for _any_ algorithm. Our
lower bound stands in contrast to many other settings in reinforcement
learning with misspecification, where one can typically obtain performance
that degrades _linearly_ with the misspecification error.

##  1 Introduction

The study of _reinforcement learning (RL)_ focuses on the problem of
sequential decision making in a stateful and stochastic environment, typically
modeled as a _Markov Decision Process (MDP)_. An agent aims to maximize its
expected reward over a finite time horizon $H$, also known as its _value_ , by
choosing a _policy_ , or a mapping from states to actions. In the _offline_
(or _batch_) _RL_ problem, an agent’s only knowledge of its environment comes
from a dataset $\mathcal{D}$ consisting of samples drawn from the state
transition distributions and reward functions of the MDP. Given $\mathcal{D}$,
the learning algorithm aims to compute a policy $\hat{\pi}$ whose value is at
least as good as that of some _reference policy_ $\pi^{\star}$.

A key challenge in offline RL is understanding how to choose the policy
$\hat{\pi}$ when the dataset $\mathcal{D}$ exhibits incomplete coverage of the
environment, meaning that the transitions from many states are not represented
in $\mathcal{D}$. The naive approach to this problem would proceed via some
variant of _value iteration_. At each step $h=H,H-1,\ldots,1$ of the time
horizon, given a policy acting at steps $h^{\prime}>h$, value iteration uses
$\mathcal{D}$ to compute estimates of the _value function_ of the policy,
which maps each state-action pair to the policy’s expected reward starting at
that state-ation pair. Value iteration then greedily chooses a policy at step
$h$ which maximizes this estimated value, and proceeds to step $h-1$.
Unfortunately, this approach suffers from the fact that state-action pairs
which are _undercovered_ by the dataset $\mathcal{D}$ may have, due to random
fluctuations in $\mathcal{D}$, overly optimistic estimates of their value. The
chosen policy $\hat{\pi}$ will then aim to visit such state-action pairs,
which could in fact be very suboptimal.

A common approach to correcting the above issue is the principle of
_pessimism_ (e.g., [FMP19, XCJ+21, LSAB20, YTY+20, JYW21]), which chooses
$\hat{\pi}$ so as to maximize an _underestimate_ of its value, where the
underestimate is chosen according to constraints that force it to be
consistent with the dataset. By ensuring that $\hat{\pi}$ takes actions whose
value is robust to random fluctuations in the dataset, pessimistic algorithms
typically ensure a guarantee of the following form: for any policy
$\pi^{\star}$ whose state-action pairs are well-covered by $\mathcal{D}$, the
value of $\hat{\pi}$ is guaranteed to be at least that of $\pi^{\star}$. The
assumption made on $\pi^{\star}$ here is typically known as a _single-policy
coverage_ condition (formalized in 2.2); along with several variants, it has
come to represent a gold standard for obtaining offline RL guarantees.

#### Function approximation & misspecification in offline RL.

As the state and action spaces encountered in practice tend to be large or
infinite, much of the theoretical work on offline RL makes _function
approximation_ assumptions, which introduce function classes $\mathcal{Q}_{h}$
for steps $h\in[H]$, whose elements can be used to approximate the value
function for a policy. Due to the complexity of the offline RL problem, our
understanding of the optimal guarantees attainable remains limited even for
the fundamental special case in which the classes $\mathcal{Q}_{h}$ are
_linear_ , which is the focus of this paper. Concretely, letting the state and
action spaces be denoted by $\mathcal{X}$ and $\mathcal{A}$, respectively, we
assume the following: for some known _feature mappings_
$\phi_{h}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$, $\mathcal{Q}_{h}$ is
the class of functions $(x,a)\mapsto\langle\phi_{h}(x,a),w\rangle$, where
$w\in\mathbb{R}^{d}$ belongs to some bounded set. As an added benefit of
focusing on the linear setting, we will be able to obtain end-to-end
computationally efficient algorithms, without reliance on a regression oracle
for $\mathcal{Q}_{h}$.

It is unreasonable to expect that elements of the classes $\mathcal{Q}_{h}$
coincide exactly with the actual value functions for the underlying MDP.
Therefore, it is essential to understand the price paid by having
_misspecification error_ in $\mathcal{Q}_{h}$. To quantify this
misspecification error we use the _inherent Bellman error_ [MS08, Mun05],
denoted $\varepsilon_{\mathsf{BE}}$, which describes the maximum distance
between the Bellman backup of any function in $\mathcal{Q}_{h+1}$ with respect
to the greedy policy and a best-approximating function in $\mathcal{Q}_{h}$.
The inherent Bellman error is particularly natural since it is exactly what
quantifies the degree to which value iteration succeeds: in particular, the
regression problems solved by value iteration are
$\varepsilon_{\mathsf{BE}}$-approximatly well-specified. As a result, it can
be shown that, if $\mathcal{D}$ covers the entire state space in an
appropriate sense and the inherent Bellman error is bounded by
$\varepsilon_{\mathsf{BE}}$, then value iteration produces a policy whose
suboptimality may be bounded by
$\operatorname{poly}(d,H)\cdot\varepsilon_{\mathsf{BE}}$ [MS08]. Moreover, the
linear growth of suboptimality error with respect to
$\varepsilon_{\mathsf{BE}}$ cannot be improved in general [TvR96].

The results of [MS08, Mun05] discussed above serve as a useful sanity check on
the reasonableness of low inherent Bellman error, but do little to address the
problems encountered in typical offline RL situations as a result of their
stringent assumption that $\mathcal{D}$ covers the full state space. In most
such settings, ranging from autonomous driving to healthcare, one should
expect the offline data to be gathered in regions of the state space that
result from executing reasonably good policies. (For instance, one should not
expect much offline data involving states corresponding to driving a car off a
cliff.) Thus, positive results under only single-policy coverage conditions
are much more desirable. Our main goal is to address the following question:
_is boundedness of the inherent Bellman error sufficient for computationally
efficient offline RL under only a single-policy coverage condition?_ Prior to
our work, this question was open even for the special case of 0 inherent
Bellman error, which is typically known as _linear Bellman completeness_.

###  1.1 Main results

Our first result is a positive answer to our main question; to state it, we
need the following notation (introduced formally in Section 2). An offline RL
algorithm takes as input a dataset $\mathcal{D}$ of size $n$, consisting of
$n$ tuples $(h,x,a,r,x^{\prime})$, denoting a sample of the transition at step
$h\in[H]$: namely, at state $x$, action $a$ was taken, reward $r$ was
received, and the next state observed was $x^{\prime}$. For each $h\in[H]$,
let $\Sigma_{h}$ denote the unnormalized covariance matrix of feature vectors
in $\mathcal{D}$ at step $h$. Moreover, for a policy $\pi$, let
$\mathscr{C}_{\mathcal{D},\pi}:=\sum_{h=1}^{H}\|\mathbb{E}^{\pi}[\phi_{h}(x_{h},a_{h})]\|_{n\Sigma_{h}^{-1}}$
denote the _coverage parameter_ for $\pi$ with respect to $\mathcal{D}$, which
measures to what degree vectors in $\mathcal{D}$ extend in the direction of a
typical feature vector drawn from $\pi$. We denote the inherent Bellman error
of the MDP by $\varepsilon_{\mathsf{BE}}\geq 0$.

######  Theorem 1.1 (Informal version of Theorem 4.1).

There is an algorithm (namely, Algorithm 1) which given the dataset
$\mathcal{D}$ as input, outputs a policy $\hat{\pi}$ at random so that for any
policy $\pi^{\star}$, we have

$\displaystyle\mathbb{E}\left[V_{1}^{\pi^{\star}}(x_{1})-V_{1}^{\hat{\pi}}(x_{1})\right]\leq$
$\displaystyle\mathscr{C}_{\mathcal{D},\pi^{\star}}\cdot\operatorname{poly}(d,H)\cdot\left(\sqrt{\varepsilon_{\mathsf{BE}}}+\frac{1}{\sqrt{n}}\right).$

Moreover, Algorithm 1 runs in time $\operatorname{poly}(d,H,n)$.

A notable feature of Theorem 1.1 is the fact that the suboptimality of
$\hat{\pi}$ scales with $\sqrt{\varepsilon_{\mathsf{BE}}}$, which contrasts
with the _linear_ scaling in $\varepsilon_{\mathsf{BE}}$ seen in classic works
on offline RL [MS08, Mun05] and recent works studying _online RL_ under low
inherent Bellman error [ZLKB20a, ZLKB20b], as well as linear dependence on the
misspecification error for other types of misspecification in both online and
offline RL settings [XCJ+21, ZWB21, NTA23, JYWJ20a, WL21].111Note that, in
[XCJ+21], the realizability error $\varepsilon_{\mathcal{F}}$ and policy
completeness error $\varepsilon_{\mathcal{F},\mathcal{F}}$ appear in a square
root (see Theorem 3.1 of [XCJ+21]), since the quantities
$\varepsilon_{\mathcal{F}},\varepsilon_{\mathcal{F},\mathcal{F}}$ actually
represent the mean _squared_ errors. Moreover, the cube-root dependence on
$\varepsilon_{\mathcal{F}},\varepsilon_{\mathcal{F},\mathcal{F}}$ in [XCJ+21]
is suboptimal and is improved in [NTA23, Theorem 2]. We show below that,
perhaps surprisingly, the square-root dependence on
$\varepsilon_{\mathsf{BE}}$ cannot be improved, even in a statistical sense:

######  Theorem 1.2 (Informal version of Theorem 5.1).

Fix $\varepsilon_{\mathsf{BE}}\in(0,1)$, $n\in\mathbb{N}$, and set $d=H=2$.
There are feature mappings
$\phi_{h}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$, $h\in[H]$, where
$|\mathcal{A}|=4$, so that for any (randomized) offline RL algorithm
$\mathfrak{A}$, the following holds. There is some MDP with inherent Bellman
error bounded by $\varepsilon_{\mathsf{BE}}$, together with some policy
$\pi^{\star}$ so that $\mathscr{C}_{\mathcal{D},\pi^{\star}}=O(1)$ yet the
output policy $\hat{\pi}$ of $\mathfrak{A}$ satisfies

$\displaystyle\mathbb{E}\left[V_{1}^{\pi^{\star}}(x_{1})-V_{1}^{\hat{\pi}}(x_{1})\right]\geq\Omega\left(\sqrt{\varepsilon_{\mathsf{BE}}}+\frac{1}{\sqrt{n}}\right).$

We emphasize that Theorem 1.2 establishes a surprising separation between
offline and online RL: whereas in the online setting, as mentioned above, one
can learn a policy whose suboptimality scales linearly with
$\varepsilon_{\mathsf{BE}}$, the optimal scaling in the offline setting is
linear in $\sqrt{\varepsilon_{\mathsf{BE}}}$. Thus, _misspecification is more
expensive in the offline setting_ , i.e., when one is not allowed to
adaptively gather data.

#### Relation to prior work.

[WFK21, Zan21] showed exponential lower bounds for offline RL under the
assumption of _all-policy realizability_ , which stipulates that the $Q$-value
function of all policies is linear (i.e., belongs to $\mathcal{Q}_{h}$). This
lower bound is incomparable to that of Theorem 1.2: whereas the inherent
Bellman error of the instances in [WFK21, Zan21] satisfies
$\varepsilon_{\mathsf{BE}}=\Omega(1)$ (so that lower bounds of
$\sqrt{\varepsilon_{\mathsf{BE}}}$ and $\varepsilon_{\mathsf{BE}}$ are
indistinguishable), the instance used to prove Theorem 1.2 does not satisfy
all-policy realizability. Moreover, the lower bounds are unrelated on a
technical level.

A recent line of work has investigated a strengthening of all-policy
realizability under which offline RL can be achieved, known as _Bellman
restricted closedness_ (or often simply as _(policy) completeness_). Under
this condition, there are statistically efficient algorithms for offline RL
with only single-policy coverage, for general function classes
$\mathcal{Q}_{h}$ [ZWB21, XCJ+21, CXJA22, NTA23]. Moreover, given a regression
oracle for the class $\mathcal{Q}_{h}$ which implements a variant of
regularized least-squares, many of these works [XCJ+21, CXJA22, NTA23] show
that the same offline RL guarantee can be obtained in an oracle-efficient
manner. Since regularized least-squares is computationally efficient when
$\mathcal{Q}_{h}$ is linear, it follows that, under Bellman restricted
closedness computationally efficient offline RL algorithms are known [XCJ+21,
CXJA22, NTA23, ZWB21].

For a class $\Pi$ of policies, an MDP satisfies $\Pi$-Bellman restricted
closedness if the Bellman backup of any function in $\mathcal{Q}_{h+1}$, _with
respect to any policy in $\Pi$_, belongs to $\mathcal{Q}_{h}$ (see C.2).
Generally speaking, the above papers achieving the strongest bounds assume
$\Pi$-Bellman restricted closedness for the class $\Pi^{\mathsf{soft}}$ of
softmax policies (C.1) [ZWB21, NTA23]. While technically speaking such an
assumption is incomparable with linear Bellman completeness (i.e., 0 inherent
Bellman error), the latter has the advantage of being universal in the sense
that it is defined so as to allow the fundamental approach of _value
iteration_ to succeed. In contrast, $\Pi$-Bellman restricted closedness only
enjoys a similar “universality” property when one takes $\Pi$ to be the class
of _all Markov policies_ , in which case $\Pi$-Bellman restricted closedness
allows _policy iteration_ to succeed [DKWY20, Theorem D.1]. However, as we
discuss further in Appendix A, in this case $\Pi$-Bellman restricted
closendess becomes significantly stronger than linear Bellman completeness: in
fact, if each state has two distinct feature vectors, then it becomes
equivalent to the linear MDP assumption [JYWJ20b, Proposition 5.1].

######  Remark 1.1 (Confluence of terminology).

Due to an unfortunate confluence of terminology, some prior works in the
literature (e.g., [US22]) refer to the setting of $\Pi$-Bellman restricted
closedness when the classes $\mathcal{Q}_{h}$ are linear as “linear Bellman
completeness”. We do not use this convention, and use “linear Bellman
completeness” to refer to the setting when the inherent Bellman error is $0$.

Finally, we remark that in the construction used to prove Theorem 1.2, the
comparator policy $\pi^{\star}$ is not the optimal policy in the MDP. This
observation suggests the following intriguing open problem: if one further
assumes that $\pi^{\star}$ is the optimal policy, then can one improve the
$\sqrt{\varepsilon_{\mathsf{BE}}}$ upper bound in Theorem 1.1 to be linear in
$\varepsilon_{\mathsf{BE}}$, or does an analogue of Theorem 1.2 continue to
hold?

###  1.2 Overview of techniques

#### Proof idea of the upper bound.

A key ingredient in the proof of Theorem 4.1 (the formal version of Theorem
1.1) is a new structural condition (Theorem 4.2 below) proving that MDPs with
low inherent Bellman error satisfy $\Pi$-Bellman restricted closedness for a
certain class $\Pi$ consisting of _perturbed linear policies_. To understand
this result, we first consider the special case of linear Bellman
completeness, i.e., $\varepsilon_{\mathsf{BE}}=0$. In this case, we show (as a
special case of Theorem 4.2) that $\Pi^{\mathsf{lin}}$-Bellman restricted
closedness holds, where $\Pi^{\mathsf{lin}}$ denotes the class of linear
policies, namely those of the form
$x\mapsto\operatorname*{arg\,max}_{a\in\mathcal{A}}\langle\phi_{h}(x,a),\theta\rangle$,
for some $\theta\in\mathbb{R}^{d}$. Unfortunately, when
$\varepsilon_{\mathsf{BE}}$ is positive but small,
$\Pi^{\mathsf{lin}}$-Bellman restricted closedness may no longer hold even in
an approximate sense. We correct for this deficiency by modifying the policy
class $\Pi^{\mathsf{lin}}$ to instead consist of perturbed linear policies: a
perturbed linear policy at step $h$,
$\pi_{h}:\mathcal{X}\to\Delta(\mathcal{A})$, is indexed by a vector
$v\in\mathbb{R}^{d}$ and a scalar $\sigma>0$. It chooses an action by first
drawing a random vector $\theta$ from the normal distribution with mean $v$
and covariance $\sigma^{2}\cdot I_{d}$, and then chooses
$\operatorname*{arg\,max}_{a^{\prime}\in\mathcal{A}}\langle\phi_{h}(x,a^{\prime}),\theta\rangle$.
We denote the set of such policies by $\Pi^{\mathsf{Plin},{\sigma}}$.

######  Theorem 1.3 ($\Pi^{\mathsf{Plin},{\sigma}}$-Bellman restricted
closedness; informal version of Corollary 3.2).

Suppose that $\pi\in\Pi^{\mathsf{Plin},{\sigma}}$ and $h\in[H-1]$. Then there
is a matrix $\mathcal{T}_{h}^{\pi}:\mathbb{R}^{d\times d}$ so that, for all
$w\in\mathbb{R}^{d}$ and $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\pi}w\rangle-\mathop{\mathbb{E}}_{\begin{subarray}{c}x^{\prime}\sim
P_{h}(x,a)\\\
a^{\prime}\sim\pi_{h+1}(x^{\prime})\end{subarray}}\left[\langle\phi_{h+1}(x^{\prime},a^{\prime}),w\rangle\right]\right|\leq\tilde{O}\left(\|w\|_{2}d^{3/2}\cdot\left(\sqrt{d}+\frac{1}{\sigma}\right)\right)\cdot\varepsilon_{\mathsf{BE}}.$
(1)

Previous work [ZWB21] shows that, under Bellman restricted closedness with
respect to a _softmax_ policy class, an actor-critic method suffices to obtain
offline RL guarantees under single-policy coverage. While Bellman restricted
closedness does not hold in general for the softmax policy class under the
assumption of linear Bellman completeness (see Lemma C.1), we prove Theorem
1.1 by adapting the actor-critic method in [ZWB21] to work instead with the
set of perturbed linear policies. To explain the requisite modifications, we
briefly overview the actor-critic method: roughly speaking, the overall goal
is to solve the problem
$\max_{\pi}\min_{M\in\mathcal{M}_{\mathcal{D}}(\pi)}V^{\scriptscriptstyle{M,\pi}}(x_{1})$,
where $\mathcal{M}_{\mathcal{D}}(\pi)$ indicates a set of MDPs which, under
trajectories drawn from $\pi$, are statistically consistent with the dataset
$\mathcal{D}$. Moreover, $V^{\scriptscriptstyle{M,\pi}}(x_{1})$ denotes the
value of policy $\pi$ in MDP $M$. Minimization over
$M\in\mathcal{M}_{\mathcal{D}}(\pi)$ corresponds to the pessimism principle,
and standard arguments [XCJ+21, ZWB21] show that an exact solution to this
max-min problem would solve the offline RL task.

To solve this max-min problem in a computationally efficient manner, the
actor-critic method uses the “no-regret learning vs. best response” approach:
a sequence of policies $\pi^{(t)}$ and MDPs
$M^{(t)}\in\mathcal{M}_{\mathcal{D}}(\pi^{(t)})$ is generated in the following
manner. At each step $t$, a no-regret learning algorithm, called the Actor,
generates a policy $\pi^{(t)}$; in response, an optimization algorithm, called
the Critic, chooses $M^{(t)}\in\mathcal{M}_{\mathcal{D}}(\pi^{(t)})$ so as to
minimize $V^{\scriptscriptstyle{M^{(t)},\pi^{(t)}}}(x_{1})$. If $T$ is chosen
sufficiently large, then, as shown in [ZWB21], a policy drawn uniformly from
$\\{\pi^{(t)}\ :\ t\in[T]\\}$ will have sufficiently large value in the true
MDP.

The Actor algorithm in [ZWB21] uses the exponential weights algorithm at each
state to update the policies $\pi^{(t)}$, which leads $\pi^{(t)}$ to be
softmax policies. We replace exponential weights with a variant of the
_expected follow-the-perturbed leader (FTPL)_ algorithm [Haz17, Algorithm 16],
which has the key advantage that the policies it produces are perturbed linear
policies, as opposed to softmax policies. The optimal choice of the standard
deviation of the perturbation turns out to be
$\sigma\approx\sqrt{\varepsilon_{\mathsf{BE}}}$, which together with Theorem
4.2 and appropriate modifications of the analysis in [ZWB21] suffices to prove
Theorem 1.1.

#### Proof idea of the lower bound.

To explain the idea behind Theorem 1.2, we first consider the following “toy
setup”: suppose that $H=d=2$, $\mathcal{A}=\\{0,1\\}$, that rewards at step
$h=1$ are known to be 0, and rewards at step $h=2$ are known to be induced by
a coefficient vector $\theta^{\mathsf{r}}_{2}\in\\{(1,1),(-1,1)\\}$.
Concretely, this type of uncertainty in $\theta^{\mathsf{r}}_{2}$ may be
implemented by having a dataset $\mathcal{D}$ for which all feature vectors at
step 2 are parallel to $(0,1)$; thus, the first coordinate of
$\theta^{\mathsf{r}}_{2}$ may remain unknown.

Consider an MDP with states $x_{2},x_{2}^{\prime}\in\mathcal{X}$ so that, for
each $a\in\mathcal{A}$, $(x_{1},a)$ transitions to either $x_{2}$ or
$x_{2}^{\prime}$, but which one is unknown. Moreover suppose that feature
vectors at $x_{2},x_{2}^{\prime}$ are given as follows: for $a\in\\{0,1\\}$,

$\displaystyle\phi_{2}(x_{2},a)=(1-2a,1-(1-2a)\cdot\varepsilon_{\mathsf{BE}}/2),\quad\phi_{2}(x_{2}^{\prime},a)=(1-2a,1+(1-2a)\cdot\varepsilon_{\mathsf{BE}}/2).$
(2)

We may ensure that the transitions described above are consistent with the
requirement that the inherent Bellman error be bounded by
$\varepsilon_{\mathsf{BE}}$, since the feature vector $\phi_{2}(x_{2},a)$ is
within distance $\varepsilon_{\mathsf{BE}}$ from $\phi_{2}(x_{2}^{\prime},a)$
for each $a$.

At a high level, our lower bound results from the following consideration:
suppose the policy we wish to compete with at step 2, namely
$\pi_{2}^{\star}$, takes a uniformly random action at step 2 (so that its
expected feature vector at step 2 is $(0,1)$). Not knowing any information
about the first coordinate of $\theta^{\mathsf{r}}_{2}$, a natural choice for
$\hat{\pi}_{2}$ is the “naive” policy that maximizes the reward in the one
“known” direction $(0,1)$, i.e., let $\hat{\pi}_{2}^{\mathsf{naive}}$ be the
linear policy which, at state $x$, chooses
$\operatorname*{arg\,max}_{a\in\mathcal{A}}\langle\phi_{h}(x,a),(0,1)\rangle$.
However, this choice suffers from the issue that, due to the
$\varepsilon_{\mathsf{BE}}$ perturbation between $\phi_{2}(x_{2},a)$ and
$\phi_{2}(x_{2}^{\prime},a)$, $\hat{\pi}_{2}^{\mathsf{naive}}$ will choose an
action $a$ at step 2, whose feature vector is either
$(1,1+\varepsilon_{\mathsf{BE}}/2)$ (if $x_{1}$ transitions to
$x_{2}^{\prime}$) or $(-1,1+\varepsilon_{\mathsf{BE}}/2)$ (if $x_{1}$
transitions to $x_{2}$). By choosing $\theta^{\mathsf{r}}_{2}=(-1,1)$ in the
former case and $\theta^{\mathsf{r}}_{2}=(1,1)$ in the latter case, we can
thus force this naive choice $\hat{\pi}_{2}^{\mathsf{naive}}$ to have
suboptimality $-\Omega(1)$ compared to $\pi_{2}^{\star}$. This issue stems
from the fact that the policy $\hat{\pi}_{2}^{\mathsf{naive}}$ is extremely
brittle to small perturbations of $\phi_{2}(x_{2},a)$: a change of size
$\varepsilon_{\mathsf{BE}}$ in each of the feature vectors leads to a
$\Omega(1)$-size change in the actual feature vector chosen by
$\hat{\pi}_{2}^{\mathsf{naive}}$.

Of course, in this specific example, one can simply instead set
$\hat{\pi}_{2}$ to be the policy which chooses each action at step 2 with
probability $1/2$, which will lead to a policy $\hat{\pi}$ whose value is
within $O(\varepsilon_{\mathsf{BE}})$ of $\pi^{\star}$. Roughly speaking,
doing so corresponds to considering a perturbed linear policy, in the vein of
Theorem 4.2. We can show, however, that such a perturbation must hurt the
value of $\hat{\pi}$, for some alternative choice of MDP. Formally, we add
transitions to states $x_{2}^{(\ell)}$ at step 2 with state-action feature
vectors
$\phi_{2}(x_{2}^{(\ell)},a)=(1-2a,1\pm(1-2a)\cdot\ell\cdot\varepsilon_{\mathsf{BE}})$,
for each value of $\ell\in\\{1,2,\ldots,\lfloor
1/\sqrt{\varepsilon_{\mathsf{BE}}}\rfloor\\}$. A suboptimality of
$\Omega(\sqrt{\varepsilon_{\mathsf{BE}}})$, with respect to some reference
policy $\pi^{\star}$, arises because avoiding it would require $\hat{\pi}_{2}$
to act in a way consistent with the naive policy
$\hat{\pi}_{2}^{\mathsf{naive}}$ (i.e., without perturbation) at states with
features $\phi_{\ell}$, for $\ell=\Omega(1/\sqrt{\varepsilon_{\mathsf{BE}}})$.
(At such states, the second component of the feature vectors deviates from $1$
by enough that it cannot be “ignored”.) But because the MDP has inherent
Bellman error of $\varepsilon_{\mathsf{BE}}$, similar reasoning to the
previous paragraph shows that the algorithm’s output policy $\hat{\pi}$ cannot
act significantly differently at states with feature vectors
$\phi_{2}(x_{2}^{(\ell)},a),\phi_{2}(x_{2}^{(\ell-1)},a)$, for each value of
$\ell$ and $a$. Since, per the previous paragraph, the algorithm must add
large perturbations to $\hat{\pi}_{2}$ for $\ell=O(1)$, we will ultimately
reach a contradiction. There are many details we have omitted from this high-
level description, such as ensuring that $\mathcal{D}$ satisfies the requisite
coverage property with respect to $\pi^{\star}$, and the fact that we wish to
allow the algorithm to output arbitrary choices of $\hat{\pi}$, and not just
perturbed linear policies – the full details are in Section 5.

#### Organization of the paper.

In Section 2, we introduce preliminaries. In Section 3, we prove Theorem 4.2,
and in Section 4 we use this result to prove our main upper bound, Theorem
1.1. Finally, in Section 5 we prove our lower bound, Theorem 1.2.

##  2 Preliminaries

We consider the standard setting of a _finite-horizon Markov decision process_
, which consists of a tuple
$M=(H,\mathcal{X},\mathcal{A},(P_{h}^{\scriptscriptstyle{M}})_{h=1}^{H},(r_{h}^{\scriptscriptstyle{M}})_{h=1}^{H},x_{1})$,
where $H\in\mathbb{N}$ denotes the _horizon_ , $\mathcal{X}$ denotes the
_state set_ , $\mathcal{A}$ denotes the _action set_ ,
$P_{h}^{\scriptscriptstyle{M}}(\cdot\mid x,a)\in\Delta(\mathcal{X})$ denote
the _transition kernels_ (for $h\in[H]$),
$r_{h}^{\scriptscriptstyle{M}}:\mathcal{X}\times\mathcal{A}\to[0,1]$ denote
the _reward functions_ (for $h\in[H]$), and $x_{1}\in\mathcal{X}$ denotes the
initial state. We omit the superscript $M$ from these notations when its value
is clear.

A _Markov policy_ (or simply _policy_) $\pi$ is a tuple
$\pi=(\pi_{1},\ldots,\pi_{H})$, where
$\pi_{h}:\mathcal{X}\to\Delta(\mathcal{A})$ for each $h\in[H]$. We let
$\Pi^{\mathsf{M}}$ denote the set of Markov policies. A policy
$\pi\in\Pi^{\mathsf{M}}$ defines a distribution over _trajectories_
$(x_{1},a_{1},r_{1},\ldots,x_{H},a_{H},r_{H})\in(\mathcal{X}\times\mathcal{A}\times[0,1])^{H}$,
in the following manner: for each $h\in[H]$, given the state $x_{h}$, an
action $a_{h}$ is drawn according to $a_{h}\sim\pi_{h}(x_{h})$, a reward
$r_{h}(x_{h},a_{h})$ is received, and the subsequent state $x_{h+1}$ is
generated according to $x_{h}\sim P_{h}^{\scriptscriptstyle{M}}(\cdot\mid
x_{h},a_{h})$. We use the notation
$\mathbb{E}^{\scriptscriptstyle{M,\pi}}[\cdot]$ to denote expectaton under the
draw of a trajectory from policy $\pi$ in the MDP $M$, and we write
$\mathbb{E}^{\scriptscriptstyle{\pi}}[\cdot]$ if the value of $M$ is clear.

Fix an MDP $M$. The _$Q$ -value function_ and _$V$ -value function_ associated
to a policy $\pi\in\Pi^{\mathsf{M}}$ in MDP $M$ are defined as follows: for
$h\in[H],x\in\mathcal{X},a\in\mathcal{A}$,

$\displaystyle
Q_{h}^{\pi}(x,a):=r_{h}(x,a)+\mathbb{E}^{\pi}\left[\sum_{g=h+1}^{H}r_{g}(x_{g},a_{g})\mid(x_{h},a_{h})=(x,a)\right],\qquad
V_{h}^{\pi}(x):=Q_{h}^{\pi}(x,\pi_{h}(x)),$

where for a function $Q:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$, we write
$Q(x,\pi_{h}(x)):=\mathbb{E}_{a\sim\pi_{h}(x)}[Q(x,a)]$. We use the convention
that all rewards and value functions evaluate to 0 at step $H+1$.

Given $h\in[H]$, a function
$Q_{h+1}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$, and a policy
$\pi\in\Pi^{\mathsf{M}}$, the _Bellman backup of $Q_{h+1}$ with respect to
$\pi$_ is the function $Q_{h}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$
defined by $Q_{h}(x,a):=r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[Q_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime}))]$. It is straightforward
to see that, for any $\pi\in\Pi^{\mathsf{M}}$, $Q_{h}^{\pi}$ is the Bellman
backup of $Q_{h+1}^{\pi}$ with respect to $\pi$, for each $h\in[H]$.

The _optimal policy_ $\pi^{\mathsf{opt}}\in\Pi^{\mathsf{M}}$ is defined as
$\pi^{\mathsf{opt}}:=\operatorname*{arg\,max}_{\pi\in\Pi^{\mathsf{M}}}V_{1}^{\pi}(x_{1})$.

###  2.1 Inherent Bellman Error

MDPs encountered in practical scenarios tend to have enormous state and action
spaces. To address this challenge, it is common to use _function
approximation_ assumptions, which consider function classes
$\mathcal{Q}_{h}\subset\mathbb{R}^{\mathcal{X}\times\mathcal{A}}$ and posit
that the value functions for the optimal policy belong to $\mathcal{Q}_{h}$,
i.e., $Q_{h}^{\pi^{\mathsf{opt}}}\in\mathcal{Q}_{h}$ for $h\in[H]$. As our
goal is to obtain provable _end-to-end computationally efficient algorithms_
for offline RL, without reliance on intractable regression oracles, we focus
on the setting when the classes $\mathcal{Q}_{h}$ are linear. In particular,
for some dimension $d\in\mathbb{N}$ together with _known_ feature mappings
$\phi_{h}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$, we take
$\mathcal{Q}_{h}:=\\{(x,a)\mapsto\langle\phi_{h}(x,a),w\rangle\ :\
w\in\mathbb{R}^{d}\\}$. For simplicity of notation, we use the convention that
$\phi_{H+1}(x,a)$ is the all-zeros vector for each $x,a$.

Generally speaking, prior work on offline RL in the linear setting [ZWB21,
XCJ+21, CXJA22, GNOP23, NTA23] interprets elements of the classes
$\mathcal{Q}_{h}$ as approximations of the $Q$-value functions $Q_{h}^{\pi}$,
for all $\pi$ belonging to some subset $\Pi\subseteq\Pi^{\mathsf{M}}$
consisting of policies whose values the learning algorithm wishes to compete
with. Accordingly, these works make the assumption of _$\Pi$ -realizability_,
which posits that for all $\pi\in\Pi$ and $h\in[H]$,
$Q_{h}^{\pi}\in\mathcal{Q}_{h}$. This assumption is natural in that it is
sufficient for correctness of the _Least-Squares Policy Iteration (LSPI)_
algorithm [LP03] (which assumes knowledge of the transitions and rewards of
$M$) for finding an optimal policy [DKWY20, Theorem D.1]. However, as shown in
[WFK21, AJX20, Zan21], $\Pi$-realizability alone is insufficient for offline
RL to succeed with polynomial sample complexity under our desired single-
policy coverage condition.222In fact, these results rule out offline RL even
under a stronger _all-policy_ coverage condition. Thus, it is typical to make
the stronger assumption of _$\Pi$ -Bellman restricted closedness_ [ZWB21]
(also known as _policy completeness_), namely that for all $\pi\in\Pi$ and
$Q_{h+1}\in\mathcal{Q}_{h+1}$, there is some $Q_{h}\in\mathcal{Q}_{h}$ so that
$Q_{h}(x,a)=\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[r_{h}(x,a)+Q_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime}))]$.

#### Inherent Bellman error.

Bellman-restricted closedness is an unwieldy assumption in that it requires
quantifying over both a policy and a value function at step $h+1$. In this
work, we study offline RL under the alternative assumption of _low inherent
Bellman error_ [ZLKB20a], as defined in Assumption 2.1 below. For $h\in[H]$,
write $\mathcal{B}_{h}:=\\{w\in\mathbb{R}^{d}:\
|\langle\phi_{h}(x,a),w\rangle|\leq 1\
\forall(x,a)\in\mathcal{X}\times\mathcal{A}\\}$.

######  Assumption 2.1 (Low Inherent Bellman Error; [ZLKB20a]).

We say that a MDP $M$ has _inherent Bellman error $\varepsilon_{\mathsf{BE}}$_
if for each $h\in[H]$, there is a mapping
$\mathcal{T}_{h}:\mathcal{B}_{h+1}\to\mathcal{B}_{h}$ so that

$\displaystyle\sup_{\theta\in\mathcal{B}_{h+1}}\sup_{(x,a)\in\mathcal{X}\times\mathcal{A}}\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}\theta\rangle-\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}\left[r_{h}(x,a)+\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{h+1}(x^{\prime},a^{\prime}),\theta\rangle\right]\right|\leq\frac{\varepsilon_{\mathsf{BE}}}{2}.$
(3)

If $M$ has inherent Bellman error $\varepsilon_{\mathsf{BE}}=0$, then we say
that $M$ is _linear Bellman complete_.

The assumption of linear Bellman completeness is sufficient for correctness of
the _Least-Squares Value Iteration (LSVI)_ algorithm [MS08, Mun05], which
assumes knowledge of the transitions and rewards of $M$. This fact has made it
a popular assumption under which to study _online RL_ , for which algorithms
typically proceed via approximate variants of LSVI [ZLKB20a, ZLKB20b]. In
contrast, as recent offline RL algorithms typically bear more resemblance to
_LSPI_ [ZWB21, XCJ+21, CXJA22, GNOP23, NTA23], offline RL has not previously
been studied under linear Bellman completeness as opposed to Bellman
restricted closedness. As discused in Section 3, one of the contributions of
this work is to draw connections between these two types of assumptions.

It is convenient to separate the components of $\mathcal{T}_{h}$ capturing the
rewards at step $h$ and the transitions at step $h$, as follows: an immediate
consequence of Assumption 2.1 (see [ZWB21, Proposition 2]) is that there are
mappings $\mathcal{T}_{h}^{\circ}:\mathcal{B}_{h+1}\rightarrow\mathcal{B}_{h}$
for each $h\in[H-1]$ and a vector $\theta_{h}^{\mathsf{r}}\in\mathcal{B}_{h}$
for each $h\in[H]$ so that the below inequalities hold:

$\displaystyle\sup_{\theta\in\mathcal{B}_{h+1}}\sup_{(x,a)\in\mathcal{X}\times\mathcal{A}}\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\circ}\theta\rangle-\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(x,a)}\left[\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{h+1}(x^{\prime},a^{\prime}),\theta\rangle\right]\right|\leq$
$\displaystyle\varepsilon_{\mathsf{BE}}$ (4)
$\displaystyle\sup_{(x,a)\in\mathcal{X}\times\mathcal{A}}\left|r_{h}(x,a)-\langle\phi_{h}(x,a),\theta_{h}^{\mathsf{r}}\rangle\right|\leq$
$\displaystyle\varepsilon_{\mathsf{BE}}.$ (5)

It was observed in [ZLKB20a, Proposition 5] that, in general, the assumptions
of linear Bellman completeness and $\Pi^{\mathsf{M}}$-realizability are
incomparable, in that neither one implies the other. Moreover, it is
straightforward to see that linear Bellman completeness is a strictly weaker
condition than $\Pi^{\mathsf{M}}$-Bellman restricted closedness. For an
arbitrary subset of policies $\Pi\subset\Pi^{\mathsf{M}}$, linear Bellman
completeness may be incomparable to the assumption of $\Pi$-Bellman restricted
closedness.

Finally, we make the following standard boundedness assumptions.

######  Assumption 2.2 (Boundedness).

We assume the following:

  1. 1.

For all $h\in[H],x\in\mathcal{X},a\in\mathcal{A}$, we have
$\|\phi_{h}(x,a)\|_{2}\leq 1$.

  2. 2.

For some parameter $B\in\mathbb{R}_{+}$: for all $w_{h}\in\mathcal{B}_{h}$, it
holds that $\|w_{h}\|_{2}\leq B$.

  3. 3.

For all $h\in[H]$, $\|\theta_{h}^{\mathsf{r}}\|_{2}\leq 1$ (and hence
$\sup_{x,a,h}|r_{h}(x,a)|\leq 1$).

The assumption that $\|\phi_{h}(x,a)\|_{2}\leq 1$ together with the definition
of $\mathcal{B}_{h}$ ensures that $\mathcal{B}_{h}$ contains a ball of radius
1 centered at the origin.

###  2.2 Perturbed linear policies

Given $w\in\mathbb{R}^{d},h\in[H],x\in\mathcal{X}$, define
$\mathcal{A}_{h,w}(x):=\operatorname*{arg\,max}_{a\in\mathcal{A}}\langle
w,\phi_{h}(x,a)\rangle\subset\mathcal{A}$, where $\operatorname*{arg\,max}$ is
interpreted as the set of all actions maximizing $\langle
w,\phi_{h}(x,a)\rangle$.

######  Definition 2.1 (Perturbed linear policies).

For $\sigma>0$, $h\in[H]$ and $w\in\mathbb{R}^{d}$, define
$\pi_{h,w,\sigma}:\mathcal{X}\rightarrow\Delta(\mathcal{A})$ by

$\displaystyle\pi_{h,w,\sigma}(x)(a)=\operatorname{Pr}_{\theta\sim\mathcal{N}(w,\sigma^{2}\cdot
I_{d})}\left(a\in\mathcal{A}_{h,\theta}(x)\right).$

In words, to draw an action $a\sim\pi_{h,w,\sigma}(x)$, we draw
$\theta\sim\mathcal{N}(w,\sigma^{2}\cdot I_{d})$ and then play
$\operatorname*{arg\,max}_{a^{\prime}\in\mathcal{A}}\langle\phi_{h}(x,a^{\prime}),\theta\rangle$.
We extend to the case that $\sigma=0$ by taking a limit, i.e., define
$\pi_{h,w,0}(x)(x)(a):=\lim_{\sigma\downarrow 0}\pi_{h,w,\sigma}(x)(a)$ (it is
straightforward to see that this limit is well-defined). Given $\sigma\geq 0$,
we denote the set of all $\pi_{h,w,\sigma^{\prime}}$, where
$w\in\mathbb{R}^{d},\sigma^{\prime}\geq 0$ satisfy
$\sigma^{\prime}/\|w\|_{2}\geq\sigma$, by $\Pi^{\mathsf{Plin},{\sigma}}_{h}$,
and
$\Pi^{\mathsf{Plin},{\sigma}}:=\prod_{h=1}^{H}\Pi^{\mathsf{Plin},{\sigma}}_{h}$.
Moreover, we write
$\Pi^{\mathsf{Plin}}_{h}:=\Pi^{\mathsf{Plin},{0}}_{h}=\bigcup_{\sigma\geq
0}\Pi^{\mathsf{Plin},{\sigma}}_{h}$ and
$\Pi^{\mathsf{Plin}}:=\Pi^{\mathsf{Plin},{0}}=\bigcup_{\sigma\geq
0}\Pi^{\mathsf{Plin},{\sigma}}$.

Note that, for any $c>0$, $\pi_{h,cw,\sigma}=\pi_{h,w,\sigma/{c}}$. We refer
to the policies in $\Pi^{\mathsf{Plin}}$ as _perturbed linear policies_. Given
a (possibly randomzied) policy $\pi_{h}:\mathcal{X}\to\Delta(\mathcal{A})$, we
use the convention that $\phi_{h}(x,\pi_{h}(x))$ refers to
$\mathbb{E}_{a\sim\pi_{h}(x)}[\phi_{h}(x,a)]$.

#### Gaussian smoothing.

For $\theta\in\mathbb{R}^{d}$ and $\sigma>0$, we write

$\displaystyle\mathcal{N}_{\sigma}(\theta):=\mathcal{N}(0,\sigma^{2}\cdot
I_{d})(\theta)=\frac{1}{(2\pi)^{d/2}\sigma^{d}}\cdot\exp\left(-\frac{1}{2\sigma^{2}}\|\theta\|_{2}^{2}\right).$

Furthermore, for $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$, we write
$\mathsf{S}_{\sigma}f(\theta)$ to denote the convolution of $f$ with
$\mathcal{N}_{\sigma}$, namely

$\displaystyle\mathsf{S}_{\sigma}f(\theta):=\int_{\mathbb{R}^{d}}f(z)\mathcal{N}_{\sigma}(\theta-z)dz=\int_{\mathbb{R}^{d}}f(\theta-z)\mathcal{N}_{\sigma}(z)dz=\mathbb{E}_{z\sim\mathcal{N}(0,\sigma^{2}\cdot
I_{d})}[f(\theta-z)].$ (6)

###  2.3 The offline learning problem

In the _offline learning model_ , the algorithm is not allowed to interact
with the environment. Rather, it is given a dataset $\mathcal{D}$ consisting
of tuples $(h,x,a,r,x^{\prime})$, where $r=r_{h}(x,a)$ and $x^{\prime}\sim
P_{h}(\cdot|x,a)$. We allow the values of $h,x,a$ in the dataset $\mathcal{D}$
to be chosen in an arbitrary adaptive manner, as formalized by the following
assumption:

######  Assumption 2.3.

We assume the dataset
$\mathcal{D}=\\{(h_{i},x_{i},a_{i},r_{i},x_{i}^{\prime})\\}_{i=1}^{n}$ is
drawn from a distribution satisfying the following conditions. For $i\in[n]$,
let $\mathcal{F}_{i}$ denote the sigma-algebra generated by
$\\{(h_{j},x_{j},a_{j},r_{j},x_{j}^{\prime})\\}_{j=1}^{i-1}\cup\\{(h_{i},x_{i},a_{i})\\}$.
We assume that, for each $i\in[n]$, conditioned on $\mathcal{F}_{i}$, the
reward $r_{i}$ is equal to
$r_{h_{i}}(x_{i},a_{i})=\langle\phi_{h_{i}}(x_{i},a_{i}),\theta_{h_{i}}^{\mathsf{r}}\rangle$,
and $x_{i}^{\prime}\sim P_{h_{i}}(x_{i},a_{i})$.

We remark that Assumption 2.3 is essentially the same as Assumption 1 of
[ZWB21]. Based on the dataset $\mathcal{D}$, the algorithm must output a
policy $\hat{\pi}$ whose value, $V_{1}^{\hat{\pi}}(x_{1})$ is as large as
possible. Of course, it may be impossible to make $V_{1}^{\hat{\pi}}(x_{1})$
very large if the dataset $\mathcal{D}$ does not include states
$(h_{i},x_{i},a_{i})$ which explore certain directions of the feature space
$\mathbb{R}^{d}$. A large number of conditions have been proposed in the
offline RL literature which capture the degree to which $\mathcal{D}$ exhibits
good “coverage” properties of the state space. Our bounds depend on one of the
weakest such conditions, namely the following variant of _single-policy
coverage_ , which is identical to that in [ZWB21].

######  Definition 2.2 (Coverage parameter).

Given a dataset $\mathcal{D}$ as in Assumption 2.3, we define
$\Sigma_{h}:=\sum_{i:h_{i}=h}\phi_{h_{i}}(x_{i},a_{i})\phi_{h_{i}}(x_{i},a_{i})^{\top}$.
For a policy $\pi\in\Pi^{\mathsf{M}}$, its _coverage parameter_ for the
dataset $\mathcal{D}$ is

$\displaystyle\mathscr{C}_{\mathcal{D},\pi}:=\sum_{h=1}^{H}\left\|\mathbb{E}^{\pi}[\phi_{h}(x_{h},a_{h})]\right\|_{n\Sigma_{h}^{-1}}.$

In words, $\mathscr{C}_{\mathcal{D},\pi}$ measures the degree to which an
average feature vector drawn from $\pi$ at each step $h$ lines up with
directions spanned by feature vectors in $\mathcal{D}$. We refer to [GNOP23,
Section 6], [NTA23, Section 4], and [Jia23] for a detailed comparison between
$\mathscr{C}_{\mathcal{D},\pi}$ and other coverage parameters considered in
prior work. As discussed there, assuming boundedness of
$\mathscr{C}_{\mathcal{D},\pi}$ is essentially the _weakest_ coverage
assumption in the literature, as many previous works (e.g., [JYW21]) require
instead boundedness of
$\mathbb{E}^{\pi}[\|\phi_{h}(x_{h},a_{h})\|_{n\Sigma_{h}^{-1}}]$, where the
norm is _inside_ the expectation.

##  3 Low Inherent Bellman Error: Structural Properties

In this section, we prove Theorem 4.2 (restated below formally as Corollary
3.2), which shows that the Bellman backup of any linear function at step
$h+1$, with respect to any perturbed linear policy, is an approximately linear
function at step $h$. The main ingredient in the proof of Corollary 3.2 is
Lemma 3.1 below, which shows that the expected feature vector induced by a
perturbed linear policy at step $h+1$ is a linear transformation of the state-
action feature vector at step $h$. Lemma 3.1 is a generalization of Lemma 4.3
of [GM24], which treats the special case of $\varepsilon_{\mathsf{BE}}=0$ and
used the result to develop an efficient algorithm for the related setting of
_online RL_ under linear Bellman completeness.

######  Lemma 3.1.

Suppose that the MDP $M$ has inherent bellman error bounded by
$\varepsilon_{\mathsf{BE}}$, and fix $\sigma>0$. Then for each $h\in[H]$ and
$w\in\mathbb{R}^{d}$, there is a linear map
$L_{h,w,\sigma}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ so that for all
$(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle\left\|L_{h,w,\sigma}^{\top}\cdot\phi_{h}(x,a)-\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(x,a)}[\phi_{h+1}(x^{\prime},\pi_{h+1,w,\sigma}(x^{\prime}))]\right\|_{2}$
$\displaystyle\leq$ $\displaystyle C_{\ref{lem:ibe-
linear}}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/(\varepsilon_{\mathsf{BE}}\sigma))}+\frac{1}{\sigma}\right),$

for some constant $C_{\ref{lem:ibe-linear}}$. Moreover, for any
$w,w^{\prime},\sigma,\sigma^{\prime}$ for which
$\pi_{h+1,w,\sigma}(x^{\prime})=\pi_{h+1,w^{\prime},\sigma^{\prime}}$ for all
$x^{\prime}\in\mathcal{X}$, we have
$L_{h,w,\sigma}=L_{h,w^{\prime},\sigma^{\prime}}$.

Given a perturbed linear policy $\pi_{h+1}\in\Pi^{\mathsf{Plin}}_{h+1}$, so
that $\pi_{h+1}=\pi_{h+1,\theta,\sigma}$ for some
$\theta\in\mathbb{R}^{d},\sigma>0$, we define
$\mathcal{T}_{h}^{\pi_{h+1}}w:=\theta_{h}^{\mathsf{r}}+L_{h,\theta,\sigma}\cdot
w$, where $L_{h,\theta,\sigma}$ is the map of Lemma 3.1 and where
$\theta_{h}^{\mathsf{r}}$ was defined in Assumption 2.1. Note that
$\mathcal{T}_{h}^{\pi_{h+1}}$ is well-defined in the sense that it only
depends on $\pi_{h+1}$ (and not on the particular choice of $\theta,\sigma$),
since for any $\theta,\sigma,\theta^{\prime},\sigma^{\prime}$ satisfying
$\pi_{h+1,\theta,\sigma}=\pi_{h+1,\theta^{\prime},\sigma}$, we have by Lemma
3.1 that $L_{h,\theta,\sigma}=L_{h,\theta^{\prime},\sigma^{\prime}}$. We will
at times abuse notation by writing
$\mathcal{T}_{h}^{\pi}:=\mathcal{T}_{h}^{\pi_{h+1}}$ for a policy
$\pi\in\Pi^{\mathsf{Plin}}$. Given Lemma 3.1, the proof of Corollary 3.2,
stated below, is straightforward.

######  Corollary 3.2.

Suppose that $\pi\in\Pi^{\mathsf{Plin},{\sigma}}$. Then for all $h\in[H-1]$,
$w\in\mathbb{R}^{d}$, and $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\pi}w\rangle-\left(r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[\langle\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime})),w\rangle]\right)\right|\leq\left\|{w}\right\|_{2}\cdot\zeta_{\sigma},$
(7)

where $\zeta_{\sigma}=C_{\ref{cor:ibe-
linear}}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/(\varepsilon_{\mathsf{BE}}\sigma))}+\frac{1}{\sigma}\right)$,
for some constant $C_{\ref{cor:ibe-linear}}$. Moreover, if $\zeta_{\sigma}\leq
1$, then $\mathcal{T}_{h}^{\pi}w\in(1+2\|w\|_{2})\cdot\mathcal{B}_{h}$.

###### Proof.

The inequality Eq. 7 follows directly from Lemma 3.1 and the definition of
$\mathcal{T}_{h}^{\pi}$, as well as Eq. 5. To see that
$\mathcal{T}_{h}^{\pi}w\in(1+2\|w\|_{2})\cdot\mathcal{B}_{h}$, we note that,
by Eq. 7, for all $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\pi}w\rangle|\leq
1+\|w\|_{2}+\|w\|_{2}\cdot\zeta_{\sigma}\leq 1+2\|w\|_{2},$

since $\zeta_{\sigma}\leq 1$. ∎

As a further corollary of Corollary 3.2, the $Q$-function for a perturbed
linear policy is linear.

######  Corollary 3.3.

Suppose that $M$ is linear Bellman complete, $\sigma>0$, and that
$\pi\in\Pi^{\mathsf{Plin},{\sigma}}$. Then for each $h\in[H]$, there is a
vector $w_{h}^{\pi}\in 2H\cdot\mathcal{B}_{h}\subset\mathbb{R}^{d}$ so that
for all $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle\left|Q_{h}^{\pi}(x,a)-\langle
w_{h}^{\pi},\phi_{h}(x,a)\rangle\right|\leq 3(H+1-h)HB\cdot\zeta_{\sigma},$

where $\zeta_{\sigma}$ is as defined in Corollary 3.2. Moreover, if
$3HB\zeta_{\sigma}\leq 1$, then $w_{h}^{\pi}\in 2H\cdot\mathcal{B}_{h}$ and
$\|w_{h}^{\pi}\|_{2}\leq 2HB$.

###### Proof.

We use reverse induction on $h$; the base case $h=H$ is immediate, so suppose
the statement holds at step $h+1$. By Assumption 2.1 and Corollary 3.2, we
have that for all $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle\left|r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[\langle\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime})),w_{h+1}^{\pi}\rangle-\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\pi}w_{h+1}^{\pi}\rangle\right|$
$\displaystyle\leq$
$\displaystyle\varepsilon_{\mathsf{BE}}+\zeta_{\sigma}\cdot\|w_{h+1}^{\pi}\|_{2}.$

Let us write $w_{h}^{\pi}:=\mathcal{T}_{h}^{\pi}w_{h+1}^{\pi}$, Since
$Q_{h}^{\pi}(x,a)=r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[Q_{h+1}^{\pi}(x,\pi_{h+1}(x))]$, the inductive hypothesis then
gives us that

$\displaystyle|Q_{h}^{\pi}(x,a)-\langle w_{h}^{\pi},\phi_{h}(x,a)\rangle|$
$\displaystyle\leq$ $\displaystyle\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[|Q_{h+1}^{\pi}(x^{\prime},\pi_{h+1}(x^{\prime}))-\langle
w_{h+1}^{\pi},\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime}))\rangle|]$
$\displaystyle+\left|r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[\langle\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime})),w_{h+1}^{\pi}\rangle-\langle\phi_{h}(x,a),w_{h}^{\pi}\rangle\right|$
$\displaystyle\leq$ $\displaystyle
3(H-h)HB\cdot\zeta_{\sigma}+(\varepsilon_{\mathsf{BE}}+\zeta_{\sigma}\cdot\|w_{h+1}^{\pi}\|_{2})\leq
3(H+1-h)HB\cdot\zeta_{\sigma},$ (8)

where the final inequality uses that
$\varepsilon_{\mathsf{BE}}\leq\zeta_{\sigma}$. To see the upper bound on
$\|w_{h}^{\pi}\|_{2}$, note that, by definition of $Q_{h}^{\pi}$ and Eq. 8, we
have $|\langle w_{h}^{\pi},\phi_{h}(x,a)\rangle|\leq
H+3(H+1-h)HB\zeta_{\sigma}\leq 2H$ for all $x,a,h$, where we have used that
$3HB\zeta_{\sigma}\leq 1$. Then it follows that $\|w_{h}^{\pi}\|_{2}\leq 2HB$
by Assumption 2.2. ∎

###### Proof of Lemma 3.1.

We may assume without loss of generality that $\|w\|_{2}=1$, by increasing
$\sigma$ by a factor of $1/\|w\|_{2}$. Fix $h\in[H]$. For
$x^{\prime}\in\mathcal{X}$ and $w\in\mathbb{R}^{d}$, define
$V(x^{\prime},w):=\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{h+1}(x^{\prime},a^{\prime}),w\rangle$.
For $x\in\mathcal{X},a\in\mathcal{A},w\in\mathbb{R}^{d}$, define
$Q(x,a,w)=\mathbb{E}_{x^{\prime}\sim P_{h}(x,a)}[V(x^{\prime},w)]$. Since
$\mathcal{A},\mathcal{X}$ are assumed to be countable, the mapping $w\mapsto
Q(x,a,w)$ is piecewise linear with countably many pieces (and is also
continuous). Next, Assumption 2.1 together with the fact that
$\\{w\in\mathbb{R}^{d}:\ \|w\|_{2}\leq 1\\}\subset\mathcal{B}_{h+1}$ gives us
that

$\displaystyle\sup_{\|w\|_{2}\leq
1}\sup_{(x,a)\in\mathcal{X}\times\mathcal{A}}\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\circ}w\rangle-Q(x,a,w)\right|\leq\varepsilon_{\mathsf{BE}}.$
(9)

Next, we may choose $k\leq d$ and
$(x_{1},a_{1}),\ldots,(x_{k},a_{k})\in\mathcal{X}\times\mathcal{A}$ so that
$\\{(\phi_{h}(x_{i},a_{i})\\}_{i=1}^{k}$ forms a barycentric spanner of
$\\{\phi_{h}(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$, and so that
$\phi_{h}(x_{i},a_{i})$, $1\leq i\leq k$, are linearly independent. By linear
independence of $\phi_{h}(x_{i},a_{i})$, for each $w\in\mathbb{R}^{d}$, there
is a matrix $L_{h,w,\sigma}\in\mathbb{R}^{d\times d}$ so that, for all
$i\in[k]$,

$\displaystyle
L_{h,w,\sigma}^{\top}\cdot\phi_{h}(x_{i},a_{i})=\nabla\mathsf{S}_{\sigma}Q(x_{i},a_{i},w).$
(10)

Next, for each $(x,a)\in\mathcal{X}\times\mathcal{A}$ and
$w\in\mathbb{R}^{d}$, we have

$\displaystyle\nabla_{w}\mathsf{S}_{\sigma}Q(x,a,w)=$
$\displaystyle\nabla_{w}\mathbb{E}_{z\sim\mathcal{N}(0,\sigma^{2}\cdot
I_{d})}\mathbb{E}_{x^{\prime}\sim P_{h}(x,a)}[Q(x^{\prime},w)]$
$\displaystyle=$ $\displaystyle\mathbb{E}_{z\sim\mathcal{N}(0,\sigma^{2}\cdot
I_{d})}\mathbb{E}_{x^{\prime}\sim P_{h}(x,a)}[\nabla_{w}V(x^{\prime},w+z)]$
$\displaystyle=$ $\displaystyle\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}\mathbb{E}_{z\sim\mathcal{N}(0,\sigma^{2}\cdot
I_{d})}[\phi_{h+1}(x^{\prime},\pi_{h+1,w+z}(x^{\prime}))]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[\phi_{h+1}(x^{\prime},\pi_{h+1,w,\sigma}(x^{\prime}))],$ (11)

where the second equality uses the dominated convergence theorem together with
the fact that for each $x^{\prime}\in\mathcal{Z},z\in\mathbb{R}^{d}$,
$w\mapsto V(x^{\prime},w+z)$ is piecewise linear with finitely many pieces,
with bounded derivative, i.e.,
$\|\nabla_{w}V(x^{\prime},w+z)\|\leq\max_{a^{\prime}\in\mathcal{A}}\|\phi_{h+1}(x^{\prime},a^{\prime})\|_{2}\leq
1$. (Note that $\mathsf{S}_{\sigma}Q(x,a,w)$ is infinitely differentiable
since we can write
$\mathsf{S}_{\sigma}Q(x,a,w)=\int_{\mathbb{R}^{d}}Q(x,a,w)\mathcal{N}_{\sigma}(w-z)dz$
and since $\mathcal{N}_{\sigma}(w-z)$ is infinitely differentiable in $w$.)
Using Eq. 11 with $(x,a)=(x_{i},a_{i})$ (for each $i\in[k]$), we see that
$L_{h,w,\sigma}=L_{h,w^{\prime},\sigma^{\prime}}$ for all
$w,w^{\prime},\sigma,\sigma^{\prime}$ satisfying
$\pi_{h+1,w,\sigma}(x^{\prime})\pi_{h+1,w^{\prime},\sigma^{\prime}}(x^{\prime})$
for all $x^{\prime}\in\mathcal{X}$.

Fix any $(x,a)\in\mathcal{X}\times\mathcal{A}$. By the barycentric spanner
property, there are coefficients $\alpha_{1},\ldots,\alpha_{k}\in[-1,1]$
(depending on $x,a$) so that
$\phi_{h}(x,a)=\sum_{i=1}^{k}\alpha_{i}\cdot\phi_{h}(x_{i},a_{i})$. It
therefore follows that, for all $w\in\mathcal{B}_{h+1}$,

$\displaystyle\left|Q(x,a,w)-\sum_{i=1}^{k}\alpha_{i}Q(x_{i},a_{i},w)\right|$
$\displaystyle\leq$
$\displaystyle|Q(x,a,w)-\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\circ}w\rangle|+\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\circ}w\rangle-\sum_{i=1}^{k}\alpha_{i}\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\circ}w\rangle\right|$
$\displaystyle+\left|\sum_{i=1}^{k}\alpha_{i}\cdot(Q(x_{i},a_{i},w)-\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\circ}w\rangle)\right|$
$\displaystyle\leq$
$\displaystyle|Q(x,a,w)-\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\circ}w\rangle|+\sum_{i=1}^{k}|Q(x_{i},a_{i},w)-\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\circ}w\rangle|$
$\displaystyle\leq$ $\displaystyle(d+1)\varepsilon_{\mathsf{BE}},$ (12)

where the second inequality uses that
$\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\circ}w\rangle=\sum_{i=1}^{k}\alpha_{i}\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\circ}w\rangle$
and the final equality uses Eq. 9 applied to each of the tuples
$(x,a),(x_{1},a_{1}),\ldots,(x_{k},a_{k})$.

Next we apply Lemma 3.4 with

$\displaystyle f(w)=$ $\displaystyle
Q(x,a,w)-\sum_{i=1}^{k}\alpha_{i}Q(x_{i},a_{i},w)$ $\displaystyle\epsilon=$
$\displaystyle(1+100\sigma\sqrt{d\log(2d/(\varepsilon_{\mathsf{BE}}\sigma))})(d+1)\varepsilon_{\mathsf{BE}},$

$D=2d$, $B=1$, and $\mathcal{B}=\\{w\in\mathbb{R}^{d}:\ \|w\|_{2}\leq 1\\}$.
Since, for all $x\in\mathcal{X},a\in\mathcal{A},w\in\mathbb{R}^{d}$,
$|Q(x,a,w)|\leq\|w\|_{2}$, we have $|f(w)|\leq(d+1)\cdot\|w\|_{2}\leq
2d\|w\|_{2}$ for $w\in\mathbb{R}^{d}$, verifying that the choice of $D=2d$ is
admissible. Moreover, the set of $z$ with $\mathrm{dist}(z,\mathcal{B})\leq
100\sigma\sqrt{d\log(2d/(\epsilon\sigma))}$ is contained in
$(1+100\sigma\sqrt{d\log(2d/\varepsilon_{\mathsf{BE}}\sigma)})\cdot\mathcal{B}$,
since $\epsilon>\varepsilon_{\mathsf{BE}}$ and $\mathcal{B}$ is a unit ball.
Therefore, scaling Eq. 12 verifies that for all $w$ with
$\mathrm{dist}(w,\mathcal{B})\leq 100\sigma\sqrt{d\log(2d/(\epsilon\sigma))}$,

$\displaystyle\left|Q(x,a,w)-\sum_{i=1}^{k}\alpha_{i}Q(x_{i},a_{i},w)\right|\leq$
$\displaystyle(1+100\sigma\sqrt{d\log(2d/(\varepsilon_{\mathsf{BE}}\sigma))})\cdot(d+1)\cdot\varepsilon_{\mathsf{BE}}=\epsilon.$

Then the guarantee of Lemma 3.4 gives that for some constant $C>0$, for all
$w$ with $\|w\|_{2}\leq 1$,

$\displaystyle\left\|\nabla\mathsf{S}_{\sigma}Q(x,a,w)-\sum_{i=1}^{k}\alpha_{i}\cdot\nabla\mathsf{S}_{\sigma}Q(x_{i},a_{i},w)\right\|_{2}\leq$
$\displaystyle\frac{C\epsilon\sqrt{d}}{\sigma}.$

By our choice of $\alpha_{i}$ and Eq. 10, for all $w\in\mathbb{R}^{d}$,

$\displaystyle\sum_{i=1}^{k}\alpha_{i}\cdot\nabla\mathsf{S}_{\sigma}Q(x_{i},a_{i},w)=L_{h,w,\sigma}^{\top}\cdot\sum_{i=1}^{k}\alpha_{i}\cdot\phi_{h}(x_{i},a_{i})=L_{h,w,\sigma}^{\top}\cdot\phi_{h}(x,a).$

Combining the above with Eq. 11 and the definition of $\epsilon$ gives that,
for some constants $C,C^{\prime}$, for $\|w\|_{2}\leq 1$,

$\displaystyle\left\|\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[\phi_{h+1}(x^{\prime},\phi_{h+1,w,\sigma}(x^{\prime}))]-L_{h,w,\sigma}^{\top}\cdot\phi_{h}(x,a)\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\varepsilon_{\mathsf{BE}}\cdot\frac{C\cdot(1+100\sigma\sqrt{d\log(2d/(\varepsilon_{\mathsf{BE}}\sigma))})(d+1)\cdot\sqrt{d}}{\sigma}$
$\displaystyle\leq$ $\displaystyle
C^{\prime}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/(\varepsilon_{\mathsf{BE}}\sigma))}+\frac{1}{\sigma}\right),$

as desired. ∎

#### Bounding the gradient of a Gaussian convolution.

For a subset $\mathcal{B}\subset\mathbb{R}^{d}$ and $z\in\mathbb{R}^{d}$, we
write $\mathrm{dist}(z,\mathcal{B}):=\inf\\{\|w-z\|_{2}\ :\
w\in\mathcal{B}\\}$.

######  Lemma 3.4.

There is a constant $C>0$ so that the following holds. Let
$\sigma,\epsilon\in(0,1/2)$ and $B,D\geq 1$ be given, and suppose that
$\mathcal{B}\subset\mathbb{R}^{d}$ is a set with nonempty interior
$\mathcal{B}^{\circ}$, and for which
$\max_{\theta\in\mathcal{B}}\|\theta\|\leq B$. Suppose
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ satisfies $|f(z)|\leq\epsilon$ for
all $z$ with $\mathrm{dist}(z,\mathcal{B})\leq
100\sigma\sqrt{d\log(BD/(\epsilon\sigma))}$, as well as $|f(z)|\leq
D\|z\|_{2}$ for all $z\in\mathbb{R}^{d}$, for some $D>0$. Then for all
$z\in\mathcal{B}^{\circ}$,

$\displaystyle\|\nabla\mathsf{S}_{\sigma}f(z)\|_{2}\leq\frac{C\epsilon\sqrt{d}}{\sigma}.$

###### Proof.

Let us write $\Delta:=100\sigma\sqrt{d\log(BD/(\epsilon\sigma))}$. Let
$\mathcal{B}_{\Delta}:=\\{z\in\mathbb{R}^{d}\ :\
\mathrm{dist}(z,\mathcal{B})\leq\Delta\\}$, so that, by assumption,
$|f(z)|\leq\epsilon$ for all $z\in\mathcal{B}_{\Delta}$. Then, for any
$\theta\in\mathcal{B}$,

$\displaystyle\|\nabla\mathsf{S}_{\sigma}f(\theta)\|_{2}=$
$\displaystyle\left\|\nabla\int_{\mathbb{R}^{d}}f(z)\mathcal{N}_{\sigma}(\theta-z)dz\right\|_{2}$
$\displaystyle=$
$\displaystyle\left\|\int_{\mathbb{R}^{d}}f(z)\cdot\nabla\mathcal{N}_{\sigma}(\theta-z)dz\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\int_{\mathcal{B}_{\Delta}}\left\|f(z)\cdot\nabla\mathcal{N}_{\sigma}(\theta-z)\right\|_{2}dz+\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\left\|f(z)\cdot\nabla\mathcal{N}_{\sigma}(\theta-z)\right\|_{2}dz.$
(13)

Note that
$\nabla\mathcal{N}_{\sigma}(\theta)=-\frac{\theta}{\sigma^{2}}\cdot\mathcal{N}_{\sigma}(\theta)$.
Then we have

$\displaystyle\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\left\|f(z)\cdot\nabla\mathcal{N}_{\sigma}(\theta-z)\right\|_{2}dz\leq$
$\displaystyle\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\frac{D\|z\|_{2}\cdot\|\theta-z\|_{2}}{\sigma^{2}}\cdot\mathcal{N}_{\sigma}(\theta-z)dz$
$\displaystyle\leq$ $\displaystyle
D\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\frac{\|\theta-z\|_{2}^{2}+B\|\theta-z\|_{2}}{\sigma^{2}}\cdot\mathcal{N}_{\sigma}(\theta-z)dz,$
(14)

where the second inequality uses that $\|z\|\leq\|\theta-z\|_{2}+B$ since
$\theta\in\mathcal{B}$.

Using the tail bound
$\operatorname{Pr}_{z\sim\mathcal{N}(0,\sigma^{2}I_{d})}(\|z\|_{2}^{2}>2td\sigma^{2})\leq
e^{-td/10}$ for $t\geq 1$ [LM00, Lemma 1]333See also
https://math.stackexchange.com/questions/2864188/chi-squared-distribution-
tail-bound. it holds that

$\displaystyle\int_{\|z\|_{2}\geq\Delta}\Delta\|z\|_{2}\cdot\mathcal{N}_{\sigma}(z)dz\leq\int_{\|z\|_{2}\geq\Delta}\|z\|_{2}^{2}\cdot\mathcal{N}_{\sigma}(z)dz\leq$
$\displaystyle\Delta^{2}\cdot
e^{-\Delta^{2}/(20\sigma^{2})}+\int_{\Delta^{2}}^{\infty}e^{-y/(20\sigma^{2})}d\sigma$
$\displaystyle=$ $\displaystyle\Delta^{2}\cdot
e^{-\Delta^{2}/(20\sigma^{2})}+\frac{1}{20\sigma^{2}}\cdot
e^{-\Delta^{2}/(20\sigma^{2})}$ $\displaystyle\leq$
$\displaystyle\left(\Delta^{2}+\frac{1}{\sigma^{2}}\right)\cdot
e^{-5d\log(BD/(\epsilon\sigma))}$ $\displaystyle\leq$
$\displaystyle\left(10^{4}d\log
BD/(\epsilon\sigma)+\frac{1}{\sigma^{2}}\right)\cdot(\epsilon\sigma/(BD))^{5d}$
$\displaystyle\leq$
$\displaystyle\frac{10^{4}\epsilon\sigma^{3}\epsilon}{BD}+\frac{\epsilon\sigma^{3}}{BD}=\frac{10001\epsilon\sigma^{3}}{BD},$
(15)

where the second inequality uses the layer cake formula and the fact that
$\Delta^{2}/\sigma^{2}\geq{2d}$, and the final inequality uses that
$(\epsilon\sigma/(BD))^{5d}\cdot
d\log(BD/\epsilon\sigma)\leq(\epsilon\sigma/BD)^{4d}\cdot
d\leq\epsilon\sigma^{3}/(BD)$ (since $\epsilon,\sigma\leq 1/2$) and that
$(\epsilon\sigma/(BD))^{5d}/\sigma^{2}\leq\epsilon\sigma^{3}/(BD)$.

Note that for all $z\in\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}$, we have
that $\|\theta-z\|\geq\Delta$ since $\theta\in\mathcal{B}$. Thus, combining
Eqs. 14 and 15, we have, for some constant $C$,

$\displaystyle\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\|f(z)\cdot\nabla\mathcal{N}_{\sigma}(\theta-z)\|_{2}dz\leq$
$\displaystyle\frac{D}{\sigma^{2}}\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\|\theta-z\|_{2}^{2}\cdot\mathcal{N}_{\sigma}(\theta-z)dz+\frac{BD}{\sigma^{2}}\int_{\mathbb{R}^{d}\backslash\mathcal{B}_{\Delta}}\|\theta-z\|_{2}\cdot\mathcal{N}_{\sigma}(\theta-z)dz$
$\displaystyle\leq$
$\displaystyle\frac{D}{\sigma^{2}}\cdot\frac{C\epsilon\sigma^{3}}{BD}+\frac{BD}{\sigma^{2}}\cdot\frac{C\epsilon\sigma^{3}}{BD\Delta}\leq
2C\epsilon,$ (16)

where we have used in the second-to-last inequality that $B\geq 1$ and
$\sigma/\Delta\leq 1$.

Next, we compute

$\displaystyle\int_{\mathcal{B}_{\Delta}}\|f(z)\cdot\nabla\mathcal{N}_{\sigma}(\theta-z)\|_{2}dz\leq$
$\displaystyle\int_{\mathcal{B}_{\Delta}}|f(z)|\cdot\frac{\|\theta-z\|_{2}}{\sigma^{2}}\mathcal{N}_{\sigma}(\theta-z)dz$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{\sigma^{2}}\int_{\mathcal{B}_{\Delta}}\|\theta-z\|_{2}\mathcal{N}_{\sigma}(\theta-z)dz$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{\sigma^{2}}\int_{\mathbb{R}^{d}}\|\theta-z\|_{2}\mathcal{N}_{\sigma}(\theta-z)dz\leq\frac{\epsilon}{\sigma^{2}}\cdot\sigma\sqrt{d}=\frac{\epsilon\sqrt{d}}{\sigma},$
(17)

where the final inequality uses the fact that
$\mathbb{E}_{Z\sim\mathcal{N}(0,\sigma^{2}\cdot
I_{d})}[\|Z\|_{2}]=\sigma\sqrt{d}$.

Combining Eq. 13, Eq. 16, and Eq. 17, we obtain that, for some constant
$C^{\prime}>0$,

$\displaystyle\|\nabla\mathsf{S}_{\sigma}f(\theta)\|_{2}\leq
2C\epsilon+\epsilon\sqrt{d}/\sigma\leq\frac{C^{\prime}\epsilon\sqrt{d}}{\sigma},$

which is the desired bound. ∎

##  4 The offline actor-critic algorithm

In this section, we prove our main upper bound, Theorem 4.1, which shows a
performance guarantee for the output policy $\hat{\pi}$ of the Actor algorithm
(Algorithm 1).

######  Theorem 4.1.

Consider any dataset $\mathcal{D}$ with $n$ examples drawn according to
Assumption 2.3, as well as parameters
$\varepsilon_{\mathsf{final}},\delta\in(0,1)$. Suppose
$\varepsilon_{\mathsf{BE}}\leq c_{0}(BH)^{-2}d^{-3}$ for some sufficiently
small constant $c_{0}$. Then, for $\eta$ set as prescribed in 4.2,
$\texttt{Actor}(\mathcal{D},\varepsilon_{\mathsf{final}},\delta,\eta)$
(Algorithm 1) returns a policy $\hat{\pi}$ so that, with probability
$1-\delta$ the following holds: for any $\pi^{\star}\in\Pi$,

$\displaystyle V_{1}^{\pi^{\star}}(x_{1})-V_{1}^{\hat{\pi}}(x_{1})$
$\displaystyle\leq$ $\displaystyle
O\left(d^{3/2}BH\cdot\varepsilon_{\mathsf{BE}}^{1/2}\log(1/\varepsilon_{\mathsf{BE}})+\frac{BHd\log^{1/2}(dnBH/(\varepsilon_{\mathsf{final}}\delta))}{\sqrt{n}}\right)\cdot\left({H}+\mathscr{C}_{\mathcal{D},\pi^{\star}}\right)+\varepsilon_{\mathsf{final}}.$

The overall computational cost of Algorithm 1 is bounded above by
$\operatorname{poly}(d,H,n,\log(B/\delta),1/\varepsilon_{\mathsf{final}})$.

A key ingredient in the proof of Theorem 4.1 (the formal version of Theorem
1.1) is a new structural condition (Theorem 4.2 below) proving that MDPs with
low inherent Bellman error satisfy $\Pi$-Bellman restricted closedness for a
certain class $\Pi$ consisting of _perturbed linear policies_. To understand
this result, we first consider the special case of linear Bellman
completeness, i.e., $\varepsilon_{\mathsf{BE}}=0$. In this case, we show (as a
special case of Theorem 4.2) that $\Pi^{\mathsf{lin}}$-Bellman restricted
closedness holds, where $\Pi^{\mathsf{lin}}$ denotes the class of linear
policies, namely those of the form
$x\mapsto\operatorname*{arg\,max}_{a\in\mathcal{A}}\langle\phi_{h}(x,a),\theta\rangle$,
for some $\theta\in\mathbb{R}^{d}$. Unfortunately, when
$\varepsilon_{\mathsf{BE}}$ is positive but small,
$\Pi^{\mathsf{lin}}$-Bellman restricted closedness may no longer hold even in
an approximate sense. We correct for this deficiency by modifying the policy
class $\Pi^{\mathsf{lin}}$ to instead consist of perturbed linear policies: a
perturbed linear policy at step $h$,
$\pi_{h}:\mathcal{X}\to\Delta(\mathcal{A})$, is indexed by a vector
$v\in\mathbb{R}^{d}$ and a scalar $\sigma>0$. It chooses an action by first
drawing a random vector $\theta$ from the normal distribution with mean $v$
and covariance $\sigma^{2}\cdot I_{d}$, and then chooses
$\operatorname*{arg\,max}_{a^{\prime}\in\mathcal{A}}\langle\phi_{h}(x,a^{\prime}),\theta\rangle$.
We denote the set of such policies by $\Pi^{\mathsf{Plin},{\sigma}}$.

######  Theorem 4.2 ($\Pi^{\mathsf{Plin},{\sigma}}$-Bellman restricted
closedness; informal version of Corollary 3.2).

Suppose that $\pi\in\Pi^{\mathsf{Plin},{\sigma}}$ and $h\in[H-1]$. Then there
is a matrix $\mathcal{T}_{h}^{\pi}:\mathbb{R}^{d\times d}$ so that, for all
$w\in\mathbb{R}^{d}$ and $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle\left|\langle\phi_{h}(x,a),\mathcal{T}_{h}^{\pi}w\rangle-\mathop{\mathbb{E}}_{\begin{subarray}{c}x^{\prime}\sim
P_{h}(x,a)\\\
a^{\prime}\sim\pi_{h+1}(x^{\prime})\end{subarray}}\left[\langle\phi_{h+1}(x^{\prime},a^{\prime}),w\rangle\right]\right|\leq\tilde{O}\left(\|w\|_{2}d^{3/2}\cdot\left(\sqrt{d}+\frac{1}{\sigma}\right)\right)\cdot\varepsilon_{\mathsf{BE}}.$
(18)

Previous work [ZWB21] shows that, under Bellman restricted closedness with
respect to a _softmax_ policy class, an actor-critic method suffices to obtain
offline RL guarantees under single-policy coverage. While Bellman restricted
closedness does not hold in general for the softmax policy class under the
assumption of linear Bellman completeness (see Lemma C.1), we prove Theorem
1.1 by adapting the actor-critic method in [ZWB21] to work instead with the
set of perturbed linear policies. To explain the requisite modifications, we
briefly overview the actor-critic method: roughly speaking, the overall goal
is to solve the problem
$\max_{\pi}\min_{M\in\mathcal{M}_{\mathcal{D}}(\pi)}V^{\scriptscriptstyle{M,\pi}}(x_{1})$,
where $\mathcal{M}_{\mathcal{D}}(\pi)$ indicates a set of MDPs which, under
trajectories drawn from $\pi$, are statistically consistent with the dataset
$\mathcal{D}$. Moreover, $V^{\scriptscriptstyle{M,\pi}}(x_{1})$ denotes the
value of policy $\pi$ in MDP $M$. Minimization over
$M\in\mathcal{M}_{\mathcal{D}}(\pi)$ corresponds to the pessimism principle,
and standard arguments [XCJ+21, ZWB21] show that an exact solution to this
max-min problem would solve the offline RL task.

To solve this max-min problem in a computationally efficient manner, the
actor-critic method uses the “no-regret learning vs. best response” approach:
a sequence of policies $\pi^{(t)}$ and MDPs
$M^{(t)}\in\mathcal{M}_{\mathcal{D}}(\pi^{(t)})$ is generated in the following
manner. At each step $t$, a no-regret learning algorithm, called the Actor,
generates a policy $\pi^{(t)}$; in response, an optimization algorithm, called
the Critic, chooses $M^{(t)}\in\mathcal{M}_{\mathcal{D}}(\pi^{(t)})$ so as to
minimize $V^{\scriptscriptstyle{M^{(t)},\pi^{(t)}}}(x_{1})$. If $T$ is chosen
sufficiently large, then, as shown in [ZWB21], a policy drawn uniformly from
$\\{\pi^{(t)}\ :\ t\in[T]\\}$ will have sufficiently large value in the true
MDP.

The Actor algorithm in [ZWB21] uses the exponential weights algorithm at each
state to update the policies $\pi^{(t)}$, which leads $\pi^{(t)}$ to be
softmax policies. We replace exponential weights with a variant of the
_expected follow-the-perturbed leader (FTPL)_ algorithm [Haz17, Algorithm 16],
which has the key advantage that the policies it produces are perturbed linear
policies, as opposed to softmax policies. The optimal choice of the standard
deviation of the perturbation turns out to be
$\sigma\approx\sqrt{\varepsilon_{\mathsf{BE}}}$, which together with Theorem
4.2 and appropriate modifications of the analysis in [ZWB21] suffices to prove
Theorem 1.1.

Algorithm 1
$\texttt{Actor}(\mathcal{D},\varepsilon_{\mathsf{final}},\delta,\eta)$

1:Dataset
$\mathcal{D}=\\{(h_{i},x_{i},a_{i},r_{i},x_{i}^{\prime})\\}_{i=1}^{n}$;
parameters $\varepsilon_{\mathsf{final}},\delta\in(0,1)$ and $\eta>0$.

2:Define $T,\varepsilon_{\mathsf{apx}},\alpha,\beta$ as a function of
$n,\varepsilon_{\mathsf{final}},\delta$ per 4.2.

3:for $1\leq t\leq T+1$ do

4: for $1\leq h\leq H$ do

5: Set $\theta_{h}^{(t)}=\sum_{s=1}^{t-1}w_{h}^{(s)}$.

6: Define $\pi_{h}^{(t)}:=\pi_{h,\theta_{h}^{(t)},\eta}$. $\triangleright$
_(See 2.1) _

7: Set
$(w_{1}^{(t)},\ldots,w_{H}^{(t)})=\texttt{Critic}(\mathcal{D},\pi^{(t)},\varepsilon_{\mathsf{apx}},\alpha,\beta,\delta/(2T))$,
where $\pi^{(t)}=(\pi_{1}^{(t)},\ldots,\pi_{H}^{(t)})$. $\triangleright$
_Algorithm 2_

8:return a policy $\hat{\pi}$ drawn as
$\hat{\pi}\sim\operatorname{Unif}(\\{\pi^{(1)},\ldots,\pi^{(T)}\\})$.

Algorithm 2
$\texttt{Critic}(\mathcal{D},\pi,\varepsilon_{\mathsf{apx}},\alpha,\beta,\delta)$

1:Dataset
$\mathcal{D}=\\{(h_{i},x_{i},a_{i},r_{i},x_{i}^{\prime})\\}_{i=1}^{n}$; policy
$\pi\in\Pi^{\mathsf{Plin}}$; parameters
$\varepsilon_{\mathsf{apx}},\alpha,\beta>0$.

2:For each $h\in[H]$, let $\mathcal{I}_{h}\subset[n]$ denote the set of $i$ so
that $h_{i}=h$.

3:For $h\in[H]$, define
$\Sigma_{h}=I_{d}+\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\phi_{h}(x_{i},a_{i})^{\top}$.

4: For $i\in[n]$, set
$\hat{\phi}_{i}^{\pi}\leftarrow\texttt{EstFeature}(x_{i}^{\prime},\pi,h_{i}+1,\varepsilon_{\mathsf{apx}},\delta/n)$.
$\triangleright$ _Algorithm 3_

5:Solve the following convex program with variables $w,\xi\in\mathbb{R}^{dH}$:
$\displaystyle\min\langle w_{1},\phi_{1}(x_{1},\pi_{1}(x_{1}))\rangle$ (19a)
s.t. $\displaystyle
w_{h}=\xi_{h}+\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\left(r_{i}+\langle\hat{\phi}_{i}^{\pi},w_{h+1}\rangle\right)\quad\forall
h\in[H]$ (19b)
$\displaystyle\|\xi_{h}\|_{\Sigma_{h}}^{2}\leq\alpha^{2}\quad\forall h\in[H]$
(19c) $\displaystyle\|w_{h}\|_{2}^{2}\leq\beta^{2}\quad\forall h\in[H].$ (19d)

6:return the solution $w=(w_{1},\ldots,w_{H})\in\mathbb{R}^{dH}$ of the convex
program.

Algorithm 3 $\texttt{EstFeature}(x,\pi,h,\varepsilon_{\mathsf{apx}},\delta)$

1:State $x\in\mathcal{X}$, policy $\pi\in\Pi^{\mathsf{Plin}}$, step $h\in[H]$,
error $\varepsilon_{\mathsf{apx}}\in(0,1)$, failure probability
$\delta\in(0,1)$.

2:Choose $w\in\mathbb{R}^{d},\sigma>0$ so that $\pi_{h}=\pi_{h,w,\sigma}$
$\triangleright$ _(This is possible by definition of $\Pi^{\mathsf{Plin}}$)_.

3:Choose $N\leftarrow 2\varepsilon_{\mathsf{apx}}^{-2}\log(2d/\delta)$.

4:Draw $N$ samples
$\theta_{1},\ldots,\theta_{N}\sim\mathcal{N}(w,\sigma^{2}\cdot I_{d})$.

5:return
$\hat{\phi}:=\frac{1}{N}\sum_{i=1}^{N}\phi_{h}(x,\pi_{h,\theta_{i}}(x))$.

###  4.1 Algorithm description

In our setting, the Actor algorithm and its associated Critic (Algorithm 2)
function similarly to the Actor and Critic algorithms in [ZWB21]. For an
appropriate choice of the number of iterations $T$, Actor repeats the
following steps $T$ times: at each iteration $t\in[T]$, Actor lets
$\theta_{h}^{(t)}$ be the sum of vectors $w_{h}^{(s)}$ for iterations $s<t$,
and lets $\pi_{h}^{(t)}$ be a perturbed linear policy with mean vector
$\theta_{h}^{(t)}$. The vector $\theta_{h}^{(t)}$ represents an aggregation of
the pessimistic estimates of the value function produced by the Critic at
previous iterations. In turn, at time step $t$, the Critic (Algorithm 2),
given $\pi^{(t)}=(\pi_{1}^{(t)},\ldots,\pi_{H}^{(t)})$ as input, then produces
vectors $w_{h}^{(t)}\in\mathbb{R}^{d}$ for $h\in[H]$, which constitute a
solution to the optimization problem Eq. 19. The program Eq. 19 has as its
objective to minimize the value at the initial state (namely, Eq. 19a),
subject to constraints that force $w_{h}^{(t)}$ to have Bellman backups with
respect to $\pi^{(t)}$ which are consistent with $\mathcal{D}$ (Eqs. 19b, 19c
and 19d).

The main difference between Algorithms 1 and 2 and the approach in [ZWB21] is
the choice of the policies $\pi_{h}^{(t)}$ in the Actor (Algorithm 1). While
we take $\pi_{h}^{(t)}$ to be a perturbed linear policy corresponding to
$\theta_{h}^{(t)}$ and an appropriate choice of the noise parameter $\eta$, in
[ZWB21], $\pi_{h}^{(t)}$ was taken to be a softmax policy corresponding to
$\theta_{h}^{(t)}$, with an appropriate choice of temperature. As we discuss
further in Section 4.3, our choice of $\pi_{h}^{(t)}$ implicitly leads
$\pi_{h}^{(t)}(x)$ to implement the no-regret _follow-the-perturbed-leader_
algorithm at each state $x$. In contrast, the softmax policy from [ZWB21]
corresponds to the exponential weights algorithm. This difference is crucial
to allow us to use Corollary 3.2 to ensure that the program Eq. 19 is feasible
and outputs a pessimistic estimate of the value function
$V_{1}^{\pi^{(t)}}(x_{1})$, for each $t\in[T]$. The settings of the parameters
in our algorithms are given in 4.2 below.

######  Remark 4.1 (Relation to prior work: Bellman restricted closedness).

We point out that many works on offline RL consider similar actor-critic
methods to ours in the setting of general function approximation [ZWB21,
XCJ+21, CXJA22, NTA23], generally under the assumption of $\Pi$-Bellman
restricted closedness for various policy classes $\Pi$. While some of these
results are sufficiently general to be instantiated in our setting (of low
inherent Bellman error) using Theorem 4.2, which establishes (approximate)
$\Pi^{\mathsf{Plin},{\sigma}}$-Bellman restricted closedness when
$\varepsilon_{\mathsf{BE}}$ is small, none of the resulting implications will
be as strong as Theorem 4.1, either suffering from suboptimal statistical
rates or computational intractability. We defer detailed discussion to
Appendix A.

######  Definition 4.2 (Parameter settings for the algorithms).

Given $d,H,B>0$ specifying the dimension, horizon, and boundedness parameters
for the unknown MDP $M$, as well as dataset size $n$ and error parameters
$\varepsilon_{\mathsf{final}},\delta\in(0,1)$, we define the following
parameters to be used in Algorithms 1 and 2 and its analysis:

  * •

$\beta:=2BH$.

  * •

$T:=\frac{16\beta^{2}d^{1/2}}{\varepsilon_{\mathsf{final}}^{2}}$.

  * •

$\varepsilon_{\mathsf{apx}}:=1/\sqrt{n}$.

  * •

$\eta:=\beta\cdot\max\left\\{T^{1/2}d^{-1/4},T\varepsilon_{\mathsf{BE}}^{1/2}\right\\}$.

  * •

$\sigma:=\frac{\eta}{T\beta}$.

  * •

$\zeta=C_{\ref{cor:ibe-
linear}}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/(\varepsilon_{\mathsf{BE}}\sigma))}+\frac{1}{\sigma}\right)$,
where $C_{\ref{cor:ibe-linear}}$ is the constant from Corollary 3.2. (Note
that $\zeta=\zeta_{\sigma}$, where $\zeta_{\sigma}$ was defined in Corollary
3.2.)

  * •

$\alpha:=4\beta\zeta\sqrt{n}+C_{\ref{lem:good-event-prob}}\beta
d\log^{1/2}(dn\beta/(\sigma\delta))$, where $C_{\ref{lem:good-event-prob}}$ is
a constant chosen sufficiently large so as to ensure Lemma 4.6 holds.

###  4.2 Critic analysis

Consider a tuple $f=(f_{1},\ldots,f_{H})$, where
$f_{h}:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$, and a policy $\pi$.
We define an MDP $M^{f,\pi}$ (called the _induced MDP_ , per [ZWB21]), whose
transitions are identical to those of $M$, but whose rewards are given as
follows: for $h\in[H]$ and $(x,a)\in\mathcal{X}\times\mathcal{A}$,

$\displaystyle
r_{h}^{\scriptscriptstyle{M^{f,\pi}}}(x,a)=f_{h}(x,a)-\mathbb{E}_{x^{\prime}\sim
P_{h}(x,a)}[f_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime}))].$ (20)

######  Lemma 4.3 (Lemma 1 of [ZWB21]).

Fix any $f=(f_{1},\ldots,f_{H})$ with
$f_{h}:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$, any $\pi\in\Pi$,
and write $M^{\prime}:=M^{f,\pi}$. Then the $Q$-value function of $M^{\prime}$
for the policy $\pi$, denoted $Q^{\scriptscriptstyle{M^{\prime},\pi}}$,
satisfies the following:

$\displaystyle\forall h\in[H],\ (x,a)\in\mathcal{X}\times\mathcal{A},\qquad
Q_{h}^{\scriptscriptstyle{M^{\prime},\pi}}(x,a)=f_{h}(x,a),$

which implies in particular that
$V_{h}^{\scriptscriptstyle{M^{\prime},\pi}}(x)=f_{h}(x,\pi_{h}(x))$.

The proof of Lemma 4.3 follows a simple telescoping argument and is provided
in [ZWB21]. Next, we establish the following straightforward guarantee for
EstFeature:

######  Lemma 4.4.

For any $x\in\mathcal{X}$, $\pi\in\Pi^{\mathsf{Plin}}$, $h\in[H]$,
$\varepsilon_{\mathsf{apx}}\in(0,1)$ and $\delta\in(0,1)$, EstFeature
(Algorithm 3) runs in time $O(d\varepsilon_{\mathsf{apx}}^{-2}\log(d/\delta))$
and returns a vector $\hat{\phi}$ so that, with probability $1-\delta$,
$\|\hat{\phi}-\phi_{h}(x,\pi_{h,w}(x))\|_{2}\leq\varepsilon_{\mathsf{apx}}$.

###### Proof.

By the definition of $\pi_{h,w,\sigma}$, it holds that for each
$\theta_{i}\sim\mathcal{N}(w,\sigma^{2}\cdot I_{d})$ in Algorithm 3, we have
$\mathbb{E}[\phi_{h}(x,\pi_{h,\theta_{i}}(x))]=\phi_{h}(x,\pi_{h}(x))$. Then
by Hoeffding’s inequality and a union bound, we have that, with probability
$1-\delta$,

$\displaystyle\left\|\frac{1}{N}\sum_{i=1}^{N}\phi_{h}(x,\pi_{h,\theta_{i}}(x))-\phi_{h}(x,\pi_{h}(x))\right\|_{2}\leq\sqrt{d}\cdot\left\|\frac{1}{N}\sum_{i=1}^{N}\phi_{h}(x,\pi_{h,\theta_{i}}(x))-\phi_{h}(x,\pi_{h}(x))\right\|_{\infty}\leq\varepsilon_{\mathsf{apx}}.$

∎

Recall that Critic (Algorithm 2) computes a vector
$w=(w_{1},\ldots,w_{H})\in\mathbb{R}^{dH}$. Given such $w$, we define a
function $f^{w}=(f^{w}_{1},\ldots,f^{w}_{H})$, where
$f^{w}_{h}(x,a):=\langle\phi_{h}(x,a),w_{h}\rangle$. We introduce the
following notation, in the context of Critic (Algorithm 2). Given a dataset
$\mathcal{D}=\\{(h_{i},x_{i},a_{i},r_{i},x_{i}^{\prime})\\}_{i=1}^{n}$, at
step $h\in[H]$, a policy $\pi\in\Pi^{\mathsf{Plin}}$, a collection of feature
vectors $\hat{\phi}=(\hat{\phi}_{1},\ldots,\hat{\phi}_{n})$ (as produced in
4), and a vector $w\in\mathbb{R}^{d}$, we define

$\displaystyle\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w:=\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot(r_{i}+\langle\hat{\phi}_{i},w\rangle),$
(21)

where
$\Sigma_{h}=I_{d}+\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\phi_{h}(x_{i},a_{i})^{\top}$
and $\mathcal{I}_{h}=\\{i:\ h_{i}=h\\}$ are defined as in Algorithm 2. Given
parameters $\alpha,\sigma>0$, we define the following good event
$\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}$:

$\displaystyle\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}=\left\\{\sup_{\|w_{h+1}\|_{2}\leq\beta}\sup_{\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}}\sup_{\begin{subarray}{c}(\hat{\phi}_{i})_{i\in[n]}\in(\mathbb{R}^{d})^{n}:\
\forall i\in[n],\\\
\|\hat{\phi}_{i}-\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime}))\|_{2}\leq\varepsilon_{\mathsf{apx}}\end{subarray}}\left\|\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}-\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi_{h+1}}w_{h+1}\right\|_{\Sigma_{h}}\leq\alpha\right\\}.$
(22)

Lemma 4.5 below establishes that under the good event
$\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}$, upon given a
perturbed linear policy $\pi$ as input, Critic produces a vector
$w^{\star}\in\mathbb{R}^{dH}$ so that the value of $\pi$ in the induced MDP
$M^{f^{w^{\star}},\pi}$ lower bounds the value of $\pi$ in the true MDP (Item
1). Moreover, for _any_ policy $\pi^{\prime}\in\Pi$, the value of
$\pi^{\prime}$ in $M^{f^{w^{\star}},\pi}$ is close to the value of
$\pi^{\prime}$ in $M$, as controlled by a concentrability coefficient
depending on $\pi^{\prime}$ (Item 2). Recall from Corollary 3.2 that we have
defined $\zeta_{\sigma}=C_{\ref{cor:ibe-
linear}}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/(\varepsilon_{\mathsf{BE}}\sigma))}+\frac{1}{\sigma}\right)$.

######  Lemma 4.5.

Consider any $\sigma,\alpha,\varepsilon_{\mathsf{apx}},\delta>0$ for which
$3BH\zeta_{\sigma}\leq 1$, suppose $\beta=2BH$, and let
$\pi\in\Pi^{\mathsf{Plin},{\sigma}}$ be given. Consider the execution of
$\texttt{Critic}(\mathcal{D},\pi,\varepsilon_{\mathsf{apx}},\alpha,\beta,\delta)$:
there is some event $\mathcal{E}_{\pi}$ depending only on the randomness in
the call to EstFeature in 4, with
$\operatorname{Pr}(\mathcal{E}_{\pi})>1-\delta$, so that the following holds.
Under the event
$\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}\cap\mathcal{E}_{\pi}$,
the output of
$\texttt{Critic}(\mathcal{D},\pi,\varepsilon_{\mathsf{apx}},\alpha,\beta,\delta)$
is a pair of vectors $w^{\star},\xi^{\star}\in\mathbb{R}^{dH}$ satisfying the
following conditions, for $f:=f^{w^{\star}}$:

  1. 1.

$V_{1}^{\scriptscriptstyle{M^{f,\pi}}}(x_{1})\leq
V_{1}^{\scriptscriptstyle{M,\pi}}(x_{1})$.

  2. 2.

For any $\pi^{\prime}\in\Pi$,

$\displaystyle\left|V_{1}^{\scriptscriptstyle{M^{f,\pi},\pi^{\prime}}}(x_{1})-V_{1}^{\scriptscriptstyle{M,\pi^{\prime}}}(x_{1})\right|\leq
3\beta
H\zeta_{\sigma}+2\alpha\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}[\phi_{h}(x_{h},a_{h})]\|_{\Sigma_{h}^{-1}}.$

Moreover, given an oracle which can solve the convex program Eq. 19, the
computational cost of Critic is
$\operatorname{poly}(d,n,H,\log(1/\delta)/\varepsilon_{\mathsf{apx}}^{2})$.

For simplicity, we assume in the statement and proof of Lemma 4.5 that the
convex program Eq. 19 may be efficiently solved exactly (i.e., that an oracle
provides the answer). While strictly speaking this may not be the case, it is
known that for any $\epsilon>0$, an $\epsilon$-approximate solution to Eq. 19
may be found in time
$\operatorname{poly}(\alpha,\beta,n,d,H,\log(1/\epsilon))$. The guarantee of
Lemma 4.5 as well as those of subsequent lemmas hold with only minor
modifications if we can only solve the program Eq. 19 $\epsilon$-approximately
in this manner. In particular, our main guarantee (Theorem 4.1) may be
achieved computationally efficiently, without assumption of any oracle; the
necessary modifications to the proof are described in Remark 4.4.

###### Proof of Lemma 4.5.

By Lemma 4.4 and a union bound over $i\in\mathcal{I}_{h}$, there is some event
$\mathcal{E}_{\pi}$ with $\operatorname{Pr}(\mathcal{E}_{\pi})\geq 1-\delta$
so that, under $\mathcal{E}_{\pi}$, the estimates $\hat{\phi}_{i}^{\pi}$
produced on 4 of Algorithm 2 satisfy
$\max_{i\in[n]}\|\hat{\phi}_{i}^{\pi}-\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime}))\|_{2}\leq\varepsilon_{\mathsf{apx}}$
for all $i\in\mathcal{I}_{h}$. We prove the two statements of the lemma in
turn:

#### Proof of Item 1.

Let $w_{h}^{\pi}\in 2H\cdot\mathcal{B}_{h}$ be defined per Corollary 3.3: in
particular, $w_{h}^{\pi}=\mathcal{T}_{h}^{\pi}w_{h+1}^{\pi}$.

For each $h\in[H]$, define
$\xi_{h}^{\pi}:=\mathcal{T}_{h}^{\pi}w_{h+1}^{\pi}-\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w_{h+1}^{\pi}$.
We claim that the vectors $(w_{h}^{\pi})_{h\in[H]},(\xi_{h}^{\pi})_{h\in[H]}$
constitute a feasible solution to the program Eq. 19. By the definition of
$\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}$ in Eq. 21, note that Eq.
19b requires that
$w_{h}^{\pi}=\xi_{h}^{\pi}+\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w_{h+1}^{\pi}$.
This equality holds by definition of $\xi_{h}^{\pi}$ and since
$w_{h}^{\pi}=\mathcal{T}_{h}^{\pi}w_{h+1}^{\pi}$. Next, the fact that
$\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}\cap\mathcal{E}_{\pi}$
holds, $\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$, and $w_{h}^{\pi}\in
2H\cdot\mathcal{B}_{h}$ (and hence $\|w_{h}^{\pi}\|_{2}\leq 2BH$; here we use
Corollary 3.3 together with the fact that $3BH\zeta_{\sigma}\leq 1$) gives
that
$\|\xi_{h}^{\pi}\|_{\Sigma_{h}}=\|\mathcal{T}_{h}^{\pi}w_{h+1}^{\pi}-\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w_{h+1}^{\pi}\|_{\Sigma_{h}}\leq\alpha$;
this verifies Eq. 19c. Finally, since $\beta=2BH$ we have that Eq. 19d holds.
It follows that Eq. 19 is feasible under the event
$\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}\cap\mathcal{E}_{\pi}$.

Let us denote the solution to Eq. 19 by $w^{\star},\xi^{\star}$. Since
$w_{h}^{\pi},\xi_{h}^{\pi}$ are feasible to Eq. 19, we must have that $\langle
w_{1}^{\star},\phi_{1}(x_{1},\pi_{1}(x_{1}))\rangle\leq\langle
w_{1}^{\pi},\phi_{1}(x_{1},\pi_{1}(x_{1}))\rangle=V_{1}^{\pi}(x_{1})$. But
Lemma 4.3 together with our choice of $f=f^{w^{\star}}$ (so that
$f_{h}(x,a)=\langle\phi_{h}(x,a),w_{h}^{\star}\rangle$) guarantees that
$\langle
w_{1}^{\star},\phi_{1}(x_{1},\pi_{1}(x_{1}))\rangle=V_{1}^{M^{f},\pi}(x_{1})$,
which yields $V_{1}^{M^{f},\pi}(x_{1})\leq V_{1}^{\pi}(x_{1})$.

####  Proof of Item 2.

For each $h\in[H]$ and $(x,a)\in\mathcal{X}\times\mathcal{A}$, we have, by the
definition Eq. 20,

$\displaystyle r_{h}^{\scriptscriptstyle{M^{f,\pi}}}(x,a)-r_{h}(x,a)=$
$\displaystyle\langle w_{h}^{\star},\phi_{h}(x,a)\rangle-
r_{h}(x,a)-\mathbb{E}_{x^{\prime}\sim P_{h}(x,a)}[\langle
w_{h+1}^{\star},\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime}))\rangle]$
$\displaystyle=$ $\displaystyle\varepsilon_{h}(x,a)+\langle
w_{h}^{\star}-\mathcal{T}_{h}^{\pi}w_{h+1}^{\star},\phi_{h}(x,a)\rangle$
$\displaystyle=$
$\displaystyle\varepsilon_{h}(x,a)+\langle\xi_{h}^{\star},\phi_{h}(x,a)\rangle+\langle\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w_{h+1}^{\star}-\mathcal{T}_{h}^{\pi}w_{h+1}^{\star},\phi_{h}(x,a)\rangle,$
(23)

where $\varepsilon_{h}(x,a)$ satisfies
$|\varepsilon_{h}(x,a)|\leq(1+2\|w_{h+1}^{\star}\|_{2})\cdot\zeta_{\sigma}\leq
3\beta\zeta_{\sigma}$ (for which such a choice is possible by Corollary 3.2).

Since the MDP $M^{f,\pi}$ has transitions identical to those of $M$, for any
$\pi^{\prime}\in\Pi$,

$\displaystyle\left|V_{1}^{\scriptscriptstyle{M^{f,\pi},\pi^{\prime}}}(x_{1})-V_{1}^{\scriptscriptstyle{M,\pi^{\prime}}}(x_{1})\right|=$
$\displaystyle\left|\sum_{h=1}^{H}\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}\left[r_{h}^{\scriptscriptstyle{M^{f,\pi}}}(x_{h},a_{h})-r_{h}(x_{h},a_{h})\right]\right|$
$\displaystyle\leq$ $\displaystyle 3\beta
H\zeta_{\sigma}+\sum_{h=1}^{H}\left|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}[\langle\xi_{h}^{\star},\phi_{h}(x_{h},a_{h})\rangle]\right|+\left|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}\left[\langle\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w_{h+1}^{\star}-\mathcal{T}_{h}^{\pi}w_{h+1}^{\star},\phi_{h}(x_{h},a_{h})\rangle\right]\right|$
$\displaystyle\leq$ $\displaystyle 3\beta
H\zeta_{\sigma}+\sum_{h=1}^{H}\left\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}[\phi_{h}(x_{h},a_{h})]\right\|_{\Sigma_{h}^{-1}}\cdot\left(\|\xi_{h}^{\star}\|_{\Sigma_{h}}+\|\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi}w_{h+1}^{\star}-\mathcal{T}_{h}^{\pi}w_{h+1}^{\star}\|_{\Sigma_{h}}\right)$
$\displaystyle\leq$ $\displaystyle 3\beta
H\zeta_{\sigma}+2\alpha\sum_{h=1}^{H}\left\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\prime}}}[\phi_{h}(x_{h},a_{h})]\right\|_{\Sigma_{h}^{-1}},$
(24)

where the first inequality uses Eq. 23 and the triangle inequality, and the
third inequality uses the fact that $(w_{h}^{\star},\xi_{h}^{\star})$ is
feasible for Eq. 19 (in particular, Eq. 19c) as well as the fact that
$\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}\cap\mathcal{E}_{\pi}$
holds and $\|w_{h+1}^{\star}\|_{2}\leq\beta=2BH$ (using Eq. 19d).

Finally, we analyze the computational cost of Algorithm 2. The call to
EstFeature in 4 takes time
$\operatorname{poly}(N,d)\leq\operatorname{poly}(d,\log(1/\delta)/\varepsilon_{\mathsf{apx}}^{2})$.
The remaining steps take time $\operatorname{poly}(d,H)$. ∎

######  Lemma 4.6.

There is a constant $C_{\ref{lem:good-event-prob}}$ so that the following
holds. Suppose the dataset $\mathcal{D}$ is drawn according to Assumption 2.3,
and $\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}>0$ are given so that
$\varepsilon_{\mathsf{apx}}\leq 1/\sqrt{n}$ and $\alpha\geq
4\beta\zeta_{\sigma}\sqrt{n}+C_{\ref{lem:good-event-prob}}\beta
d\log^{1/2}(dn\beta/(\sigma\delta))$. Then,
$\operatorname{Pr}(\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}})\geq
1-\delta/2$, where the probability is over the draw of $\mathcal{D}$.

We remark that the only source of randomness in Critic is over the randomness
of EstFeature in 4.

###### Proof of Lemma 4.6.

Given $h\in[H]$, $w_{h+1}\in\mathbb{R}^{d}$,
$\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}$, and
$\hat{\phi}=(\hat{\phi}_{i})_{i\in[n]}\in(\mathbb{R}^{d})^{n}$, let us write,
for $i\in\mathcal{I}_{h}$,

$\displaystyle\varepsilon_{i}(w_{h+1},\pi_{h+1}):=$ $\displaystyle
r_{i}+\langle\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime})),w_{h+1}\rangle-(r_{h}(x_{i},a_{i})+\mathbb{E}_{x^{\prime}\sim
P_{h}(x_{i},a_{i})}[\langle\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime})),w_{h+1}\rangle])$
$\displaystyle\xi_{i}(w_{h+1},\pi_{h+1}):=$ $\displaystyle
r_{h}(x_{i},a_{i})+\mathbb{E}_{x^{\prime}\sim
P_{h}(x_{i},a_{i})}[\langle\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime})),w_{h+1}\rangle]-\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\rangle$
$\displaystyle\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i}):=$
$\displaystyle\langle\hat{\phi}_{i}-\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime})),w_{h+1}\rangle.$

#### Error decomposition.

For any $w_{h+1}\in\mathbb{R}^{d}$,
$\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$, and
$\hat{\phi}=(\hat{\phi}_{i})_{i\in[n]}$, we can decompose

$\displaystyle\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi_{h+1}}w_{h+1}$
$\displaystyle=$
$\displaystyle\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot(r_{i}+\langle\hat{\phi}_{i},w_{h+1}\rangle)$
$\displaystyle=$
$\displaystyle\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot(r_{i}+\langle\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime})),w_{h+1}\rangle)+\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i})$
$\displaystyle=$
$\displaystyle\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\rangle$
$\displaystyle+\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\left(\varepsilon_{i}(w_{h+1},\pi_{h+1})+\xi_{i}(w_{h+1},\pi_{h+1})+\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i})\right)$
$\displaystyle=$
$\displaystyle-\Sigma_{h}^{-1}\cdot\cdot\mathcal{T}_{h}^{\pi}w_{h+1}+\Sigma_{h}^{-1}\left(+\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\phi_{h}(x_{i},a_{i})^{\top}\right)\cdot\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}$
$\displaystyle\quad+\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot(\varepsilon_{i}(w_{h+1},\pi_{h+1})+\xi_{i}(w_{h+1},\pi_{h+1})+\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i}))$
$\displaystyle=$
$\displaystyle\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}-\Sigma_{h}^{-1}\cdot\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}+$
$\displaystyle+\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot(\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i})+\xi_{i}(w_{h+1},\pi_{h+1})+\varepsilon_{i}(w_{h+1},\pi_{h+1})),$
(25)

where the final equality uses the definition of $\Sigma_{h}$ (in 3 of
Algorithm 2).

#### Bounding the error terms.

First, we note that for any $w_{h+1}$ satisfying $\|w_{h+1}\|_{2}\leq\beta$
and any $\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$,

$\displaystyle\|\Sigma_{h}^{-1}\cdot\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\|_{\Sigma_{h}}=\|\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\|_{\Sigma_{h}^{-1}}\leq\|\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\|_{2}\leq
3\cdot\beta B,$ (26)

where the first inequality uses that $\Sigma_{h}\succeq I_{d}$ and the second
inequality uses that, since $\|w_{h+1}\|_{2}\leq\beta$, we have
$\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\in 3\beta\cdot\mathcal{B}_{h}$ (Corollary
3.2), and hence $\|\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\|_{2}\leq 3\beta B$
(Assumption 2.2).

Next, as long as $\|w_{h+1}\|_{2}\leq\beta$ and
$\|\hat{\phi}_{i}-\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime}))\|_{2}\leq\varepsilon_{\mathsf{apx}}$
for all $i\in[n]$, we have

$\displaystyle|\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i})|\leq\|\hat{\phi}_{i}-\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime}))\|_{2}\cdot\|w_{h+1}\|_{2}\leq\beta\varepsilon_{\mathsf{apx}}$

for all $i\in[n]$ and thus

$\displaystyle\left\|\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i})\right\|_{\Sigma_{h}}=\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\eta_{i}(w_{h+1},\pi_{h+1},\hat{\phi}_{i})\right\|_{\Sigma_{h}^{-1}}\leq\beta\varepsilon_{\mathsf{apx}}\sqrt{n},$
(27)

where the inequality uses Lemma B.2.

Next, by Corollary 3.2, for any $w_{h+1}$ satisfying
$\|w_{h+1}\|_{2}\leq\beta$ and any $\pi_{h+1}\in\Pi^{\mathsf{Plin}}_{h+1}$,
for each $i\in\mathcal{I}_{h}$ we have

$\displaystyle\left|r_{h}(x_{i},a_{i})+\mathbb{E}_{x^{\prime}\sim
P_{h}(x_{i},a_{i})}[\langle\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime})),w_{h+1}\rangle]-\langle\phi_{h}(x_{i},a_{i}),\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\rangle\right|\leq$
$\displaystyle\beta\cdot\zeta_{\sigma}.$

Thus, by Lemma B.2,

$\displaystyle\left\|\Sigma_{h}^{-1}\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\xi_{i}(w_{h+1},\pi_{h+1})\right\|_{\Sigma_{h}}=\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\xi_{i}(w_{h+1},\pi_{h+1})\right\|_{\Sigma_{h}^{-1}}\leq\beta\zeta_{\sigma}\sqrt{n}.$
(28)

It remains to bound the final term in Eq. 25, namely the one involving
$\varepsilon_{i}(w_{h+1},\pi_{h+1})$. To do so, we use a covering based
argument. We define the following metric on
$\Pi^{\mathsf{Plin},{\sigma}}_{h}$: for
$\pi_{h},\pi_{h}^{\prime}\in\Pi^{\mathsf{Plin},{\sigma}}_{h}$, define

$\displaystyle\|\pi_{h}-\pi_{h}^{\prime}\|_{\infty,1}:=\sup_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}|\pi_{h}(a|x)-\pi_{h}^{\prime}(a|x)|.$
(29)

For $\epsilon>0$, we let
$\mathcal{N}_{\infty,1}(\Pi^{\mathsf{Plin},{\sigma}}_{h},\epsilon)$ denote the
minimum size of an $\epsilon$-cover of $\Pi^{\mathsf{Plin},{\sigma}}_{h}$ with
respect to $\|\cdot\|_{\infty,1}$. Similarly, let
$\mathcal{G}:=\\{w\in\mathbb{R}^{d}:\ \|w\|_{2}\leq\beta\\}$, and let
$\mathcal{N}_{2}(\mathcal{G},\epsilon)$ denote the miniimum size of an
$\epsilon$-cover of $\mathcal{G}$ with respect to $\|\cdot\|_{2}$. We use the
following lemma:

######  Lemma 4.7 (Covering number bounds).

There is a constant $C_{\ref{lem:covering}}$ so that for all $h\in[H]$,

$\displaystyle\log\mathcal{N}_{\infty,1}(\Pi^{\mathsf{Plin},{\sigma}}_{h},\epsilon)\leq$
$\displaystyle d\log(C_{\ref{lem:covering}}/(\epsilon\sigma))$
$\displaystyle\log\mathcal{N}_{2}(\mathcal{G},\epsilon)\leq$ $\displaystyle
d\log(C_{\ref{lem:covering}}\beta/\epsilon).$

Let $\widetilde{\mathcal{G}}\subset\mathcal{G}$ be an $\epsilon$-cover of
$\mathcal{G}$ with respect to $\|\cdot\|_{2}$ with size bounded per Lemma 4.7,
and
$\widetilde{\Pi}^{\mathsf{Plin},{\sigma}}_{h+1}\subset\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$
be an $\epsilon$-cover of $\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$ with respect to
$\|\cdot\|_{\infty,1}$ with size bounded per Lemma 4.7.

For fixed $\widetilde{w}_{h+1}\in\widetilde{\mathcal{G}}$ and
$\widetilde{\pi}_{h+1}\in\widetilde{\Pi}^{\mathsf{Plin},{\sigma}}$, for each
$i\in\mathcal{I}_{h}$, we have from the definition of
$\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})$ that

$\displaystyle|\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})|\leq
2+2\|\widetilde{w}_{h+1}\|_{2}\leq 2+2\beta\leq 4\beta,$ (30)

where we have used Assumption 2.2 and the fact that $\beta\geq 1$. Moreover,
by Assumption 2.3, if we let $\mathcal{F}_{i}$ denote the sigma-algebra
generated by all tuples $(h_{j},x_{j},a_{j},r_{j},x_{j}^{\prime})$ for $j\leq
i$ and by $(h_{i+1},x_{i+1},a_{i+1})$, we have
$\mathbb{E}[\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})|\mathcal{F}_{i-1}]=0$
and
$\mathbb{E}[e^{\lambda\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})}|\mathcal{F}_{i-1}]\leq
e^{\lambda^{2}\cdot(4\beta)^{2}/2}$, where we have used Eq. 30. Moreover,
$\phi_{h}(x_{i},a_{i})$ is measurable with respect to $\mathcal{F}_{i-1}$. Let
us write
$N:=|\widetilde{\mathcal{G}}|\cdot|\widetilde{\Pi}^{\mathsf{Plin},{\sigma}}|$,
so that $\log N\leq Cd\log(\beta/\epsilon\sigma)$, for some constant $C$. By
Lemma B.1, there is some event
$\mathcal{E}_{\widetilde{w},\widetilde{\pi}_{h+1}}$ which occurs with
probability at least $1-\delta/N$, so that under
$\mathcal{E}_{\widetilde{w},\widetilde{\pi}_{h+1}}$, we have

$\displaystyle\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})\right\|_{\Sigma_{h}^{-1}}\leq
32\beta^{2}\log^{1/2}\left(\frac{\det(\Sigma_{h})^{1/2}}{\delta/N}\right)\leq
8\beta d^{1/2}\log^{1/2}\left(N\cdot\frac{d+n}{d\delta}\right),$

where the final inequality uses

$\displaystyle\det(\Sigma_{h})\leq\left(\frac{1}{d}\operatorname{Tr}\Sigma_{h}\right)^{d}\leq\left(\frac{1}{d}\cdot\left(d+\sum_{i\in\mathcal{I}_{h}}\|\phi_{h}(x_{i},a_{i})\|_{2}^{2}\right)\right)^{d}\leq\left(\frac{d+n}{d}\right)^{d}.$

By a union bound, it follows that under some event $\mathcal{E}$ that occurs
with probability at least $1-\delta$, we have

$\displaystyle\sup_{\begin{subarray}{c}\widetilde{w}\in\widetilde{\mathcal{G}}\\\
\widetilde{\pi}_{h+1}\in\widetilde{\Pi}^{\mathsf{Plin},{\sigma}}_{h+1}\end{subarray}}\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})\right\|_{\Sigma_{h}^{-1}}\leq
8\beta d^{1/2}\log^{1/2}\left(N\cdot\frac{d+n}{d\delta}\right).$ (31)

Now consider any $w_{h+1}\in\mathcal{G}$ and
$\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$. Choose
$\widetilde{w}_{h+1}\in\widetilde{\mathcal{G}}$ and
$\widetilde{\pi}_{h+1}\in\widetilde{\Pi}^{\mathsf{Plin},{\sigma}}_{h+1}$ so
that $\|w_{h+1}-\widetilde{w}_{h+1}\|_{2}\leq\epsilon$ and
$\|\pi_{h+1}-\widetilde{\pi}_{h+1}\|_{\infty,1}\leq\epsilon$. We have

$\displaystyle\sup_{\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}}|\varepsilon_{i}(w_{h+1},\pi_{h+1})-\varepsilon_{i}(\widetilde{w}_{h+1},\pi_{h+1})|\leq$
$\displaystyle 2\cdot\|w_{h+1}-\widetilde{w}_{h+1}\|_{2}\leq 2\epsilon$ (32)
$\displaystyle\sup_{w_{h+1}\in\mathcal{G}}\left|\varepsilon_{i}(w_{h+1},\pi_{h+1})-\varepsilon_{i}(w_{h+1},\widetilde{\pi}_{h+1})\right|\leq$
$\displaystyle
2\beta\cdot\sup_{x^{\prime}\in\mathcal{X}}\|\phi_{h+1}(x^{\prime},\pi_{h+1}(x^{\prime}))-\phi_{h+1}(x^{\prime},\widetilde{\pi}_{h+1}(x^{\prime}))\|_{2}\leq
2\beta\epsilon,$ (33)

where Eq. 33 uses the definition of $\|\cdot\|_{\infty,1}$ in Eq. 29. Then,
under the event $\mathcal{E}$,

$\displaystyle\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\varepsilon_{i}(w_{h+1},\pi_{h+1})\right\|_{\Sigma_{h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})\right\|_{\Sigma_{h}^{-1}}+\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\left(\varepsilon_{i}(\widetilde{w}_{h+1},\pi_{h+1})-\varepsilon_{i}(w_{h+1},\pi_{h+1})\right)\right\|_{\Sigma_{h}^{-1}}$
$\displaystyle+\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\left(\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})-\varepsilon_{i}(\widetilde{w}_{h+1},\pi_{h+1})\right)\right\|_{\Sigma_{h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{i\in\mathcal{I}_{h}}\phi_{h}(x_{i},a_{i})\cdot\varepsilon_{i}(\widetilde{w}_{h+1},\widetilde{\pi}_{h+1})\right\|_{\Sigma_{h}^{-1}}+4\beta\epsilon\sqrt{n}$
$\displaystyle\leq$ $\displaystyle 8\beta
d^{1/2}\log^{1/2}\left(N\cdot\frac{d+n}{d\delta}\right)+4\beta\epsilon\sqrt{n},$
(34)

where the first inequality uses the triangle inequality, the second inequality
uses Lemma B.2 together with Eqs. 32 and 33, and the final inequality uses Eq.
31 together with the fact that $\mathcal{E}$ holds.

Combining Eqs. 25, 26, 27, 34 and 28, we conclude that under the event
$\mathcal{E}$, for any $w_{h+1}\in\mathcal{G}$,
$\pi_{h+1}\in\Pi^{\mathsf{Plin},{\sigma}}_{h+1}$, and
$\hat{\phi}\in(\mathbb{R}^{d})^{n}$ so that
$\max_{i\in[n]}\|\hat{\phi}_{i}-\phi_{h+1}(x_{i}^{\prime},\pi_{h+1}(x_{i}^{\prime}))\|_{2}\leq\varepsilon_{\mathsf{apx}}$,

$\displaystyle\|\hat{\mathcal{T}}_{h,\mathcal{D},\hat{\phi}}^{\pi_{h+1}}w_{h+1}-\mathcal{T}_{h}^{\pi_{h+1}}w_{h+1}\|_{\Sigma_{h}}\leq$
$\displaystyle 3\beta
B+\beta\varepsilon_{\mathsf{apx}}\sqrt{n}+\beta\zeta_{\sigma}\sqrt{n}+8\beta
d^{1/2}\log^{1/2}\left(N\cdot\frac{d+n}{d\delta}\right)+4\beta\epsilon\sqrt{n}$
$\displaystyle\leq$ $\displaystyle 11C\beta
d\log^{1/2}\left(\frac{dn\beta}{\epsilon\delta\sigma}\right)+4\beta(\epsilon+\varepsilon_{\mathsf{apx}}+\zeta_{\sigma})\sqrt{n},$

where the second inequality uses the bound $\log N\leq
Cd\log(\beta/\epsilon\sigma)$. Choosing $\epsilon=1/\sqrt{n}$, and as long as
$\varepsilon_{\mathsf{apx}}\leq 1/\sqrt{n}$, we see that
$\mathcal{E}\subset\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}}$,
since we have chosen $\alpha\geq 4\beta\zeta_{\sigma}\sqrt{n}+C\beta
d\log^{1/2}(dn\beta/(\sigma\delta))$ for a sufficiently large constant $C$.
Thus
$\operatorname{Pr}(\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}})\geq\operatorname{Pr}(\mathcal{E})\geq
1-\delta$. Rescaling $\delta$ to $\delta/2$ yields the result. ∎

###### Proof of Lemma 4.7.

First, we note that $\log\mathcal{N}_{2}(\mathcal{G},\epsilon)\leq
d\cdot\log(3\beta/(\epsilon))$ by [Wai19, Example 5.8]. To bound the covering
number of $\Pi^{\mathsf{Plin},{\sigma}}_{h}$, let
$\mathcal{C}\subset\\{w\in\mathbb{R}^{d}:\ \|w\|_{2}\leq 1\\}$ denote a
$\epsilon\sigma$-cover of the unit ball, so that [Wai19, Example 5.8] ensures
that we can choose $\mathcal{C}$ with $|\mathcal{C}|\leq
d\log(3/(\epsilon\sigma))$. For any $w\in\mathbb{R}^{d}$ with $\|w\|_{2}\leq
1$, there is some $w^{\prime}\in\mathcal{C}$ with
$\|w-w^{\prime}\|_{2}\leq\epsilon\sigma$. Then we have

$\displaystyle D_{\mathsf{TV}}({\mathcal{N}(w,\sigma^{2}\cdot
I_{d})},{\mathcal{N}(w^{\prime},\sigma^{2}\cdot
I_{d})})\leq\sqrt{\frac{1}{2}\cdot\operatorname{KL}({\mathcal{N}(w,\sigma^{2}\cdot
I_{d})}||{\mathcal{N}(w^{\prime},\sigma^{2}\cdot
I_{d})})}=\frac{1}{2\sigma}\cdot\|w-w^{\prime}\|_{2}\leq\frac{\epsilon}{2},$

where we have used Pinsker’s inequality and the formula for the KL divergence
between two Gaussians. Moreover, for any $x\in\mathcal{X}$, we have

$\displaystyle\sum_{a\in\mathcal{A}}|\pi_{h,w,\sigma}(a|x)-\pi_{h,w^{\prime},\sigma}(a|x)|\leq$
$\displaystyle D_{\mathsf{TV}}({\mathcal{N}(w,\sigma^{2}\cdot
I_{d})},{\mathcal{N}(w^{\prime},\sigma^{2}\cdot I_{d})})$

by the data processing inequality for total variation distance (in particular,
the deterministic function
$W\mapsto\operatorname*{arg\,max}_{a\in\mathcal{A}}\langle\phi_{h}(x,a),W\rangle$
maps a random variable $W\sim\mathcal{N}(w,\sigma^{2}\cdot I_{d})$ to an
action $A\sim\pi_{h,w,\sigma}(\cdot|x)$). Combining the above displays gives
that $\|\pi_{h,w,\sigma}-\pi_{h,w^{\prime},\sigma}\|_{\infty,1}\leq\epsilon$,
as desired. ∎

###  4.3 Actor analysis

Notice that the Actor algorithm (Algorithm 1) is a special case of the Follow-
the-Perturbed-Leader (FTPL) algorithm. This observation is central to our
proof. Below we first review some basic facts pertaining to the FTPL
algorithm.

#### Review of FTPL.

For $J,L>0$, a distribution $\mu$ on $\mathbb{R}^{d}$ is defined to be
_$(J,L)$ -stable_ with respect to the Euclidean norm $\|\cdot\|_{2}$ if the
following two conditions hold:

$\displaystyle\mathbb{E}_{\rho\sim\mu}[\|\rho\|_{2}]\leq$ $\displaystyle J$
$\displaystyle\forall
v\in\mathbb{R}^{d},\quad\int_{\rho\in\mathbb{R}^{d}}|\mu(\rho)-\mu(\rho-v)|d\rho\leq$
$\displaystyle L\cdot\|v\|_{2}.$

We consider the setting of _online linear optimization_ : the algorithm is
given a set of actions $\Phi\subset\mathbb{R}^{d}$, and operates over some
number $T\in\mathbb{N}$ of rounds. At each round $t\in[T]$, an adversary
chooses a _reward vector_ $w^{(t)}$, which may be random and depend
arbitrarily on past choices of the algorithm (i.e., we consider the case of an
_adaptive adversary_). Simultaneously, the algorithm chooses a vector
$\phi^{(t)}\in\Phi$, and then observes $w^{(t)}$ and receives a reward
$\langle w^{(t)},\phi^{(t)}\rangle$. The algorithm’s goal is to minimize its
regret with respect to the best-in-hindsight fixed choice of action in $\Phi$.
The _expected FTPL_ algorithm, presented in Algorithm 4, solves the online
linear optimization problem. Its choice of action at each round is given by
the best action for the previous rounds, perturbed by a distribution which
satisfies $(J,L)$-stability.

Algorithm 4 Expected Follow-the-Perturbed-Leader:
$\texttt{ExpFTPL}(\Phi,\mu,T,\eta)$

1:Action set $\Phi\subset\mathbb{R}^{d}$, distribution
$\mu\in\Delta(\mathbb{R}^{d})$, parameters $\omega>0,T\in\mathbb{N}$.

2:for $1\leq t\leq T$ do

3: Choose
$\displaystyle\phi^{(t)}:=\mathbb{E}_{\rho^{(t)}\sim\mu}\left[\operatorname*{arg\,max}_{\phi\in\mathcal{A}}\left\\{\omega\cdot\sum_{s=1}^{t-1}\langle
w^{(s)},\phi\rangle+\langle\rho^{(t)},\phi\rangle\right\\}\right].$

4: Receive reward vector $w^{(t)}\in\mathbb{R}^{d}$, earn reward
$\langle\phi^{(t)},w^{(t)}\rangle$.

######  Theorem 4.8 ([Haz17], Theorem 5.8).

Suppose that $\mu$ is $(J,L)$-stable, and write
$D:=\max_{\phi\in\Phi}\|\phi\|_{2}$. Then for any adaptive adversary choosing
$w^{(1)},\ldots,w^{(T)}$ satisfying $\|w^{(t)}\|_{2}\leq G$ for all $t$, the
iterates $\phi^{(t)}$ produced by $\texttt{ExpFTPL}(\Phi,\mu,T,\omega)$
(Algorithm 4) satisfy

$\displaystyle\max_{\phi^{\star}\in\Phi}\left\\{\sum_{t=1}^{T}\langle\phi^{\star},w^{(t)}\rangle-\sum_{t=1}^{T}\langle\phi^{(t)},w^{(t)}\rangle\right\\}\leq\omega
LDG^{2}T+\frac{JD}{\omega}.$

We remark that since the iterates $\phi^{(t)}$ of Algorithm 4 are
deterministic, in the setting of no-regret learning (i.e., that of Theorem
4.8), adaptive and oblivious adversaries are equivalent.

#### Analysis of Actor.

Recall that for $w=(w_{1},\ldots,w_{H})\in\mathbb{R}^{dH}$, we have defined
$f^{w}:=(f_{1}^{w},\ldots,f_{H}^{w})$, where
$f_{h}^{w}(x,a):=\langle\phi_{h}(x,a),w_{h}\rangle$. To simplify notation, we
write $f^{(t)}:=f^{w^{(t)}}$, where $w^{(t)}=(w_{1}^{(t)},\ldots,w_{H}^{(t)})$
is the vector returned by Critic on 7 of Actor (Algorithm 1).

######  Lemma 4.9.

For any $\mathcal{D},\varepsilon_{\mathsf{final}},\delta$, the algorithm
$\texttt{Actor}(\mathcal{D},\varepsilon_{\mathsf{final}},\delta,\eta)$
(Algorithm 1) satisfies the following: for any $\pi^{\star}\in\Pi$, $h\in[H]$,
and $x\in\mathcal{X}$, we have

$\displaystyle\sum_{t=1}^{T}f_{h}^{(t)}(x,\pi_{h}^{\star}(x))-\sum_{t=1}^{T}f_{h}^{(t)}(x,\pi_{h}^{(t)}(x))\leq\eta^{-1}(2BH)^{2}T+{\eta\sqrt{d}}.$

We emphasize that the policy $\pi^{\star}$ in Lemma 4.9 is not required to be
a (perturbed) linear policy.

###### Proof of Lemma 4.9.

Fix $\pi^{\star}\in\Pi$ and $x\in\mathcal{X}$. Note that, by definition of
$f_{h}^{(t)}$,

$\displaystyle\sum_{t=1}^{T}f_{h}^{(t)}(x,\pi_{h}^{\star}(x))=\sum_{t=1}^{T}\langle
w_{h}^{(t)},\phi_{h}(x,\pi_{h}^{\star}(x))\rangle,$

and

$\displaystyle\sum_{t=1}^{T}f_{h}^{(t)}(x,\pi^{(t)}(x))=\sum_{t=1}^{T}\langle
w_{h}^{(t)},\phi_{h}(x,\pi_{h}^{(t)}(x))\rangle.$

Moreover, the definition of $\pi_{h}^{(t)}$ in Actor (Algorithm 1) ensures
that

$\displaystyle\phi_{h}(x,\pi_{h}^{(t)}(x))=$
$\displaystyle\mathbb{E}_{\rho_{h}^{(t)}\sim\mathcal{N}(0,\eta^{2}\cdot
I_{d})}\left[\operatorname*{arg\,max}_{a\in\mathcal{A}}\left\\{\left\langle\phi_{h}(x,a),\theta_{h}^{(t)}+\rho_{h}^{(t)}\right\rangle\right\\}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\rho_{h}^{(t)}\sim\mathcal{N}(0,\eta^{2}\cdot
I_{d})}\left[\operatorname*{arg\,max}_{a\in\mathcal{A}}\left\\{\sum_{s=1}^{t-1}\langle\phi_{h}(x,a),w_{h}^{(s)}\rangle+\langle\phi_{h}(x,a),\rho_{h}^{(t)}\rangle\right\\}\right],$

where we have written $\theta_{h}^{(t)}=\sum_{s=1}^{t-1}w_{h}^{(s)}$, as in
Algorithm 1. In particular, $\phi_{h}(x,\pi_{h}^{(t)}(x))$ is exactly the
choice of $\texttt{ExpFTPL}(\Phi,\mu,T,\omega)$ (Algorithm 4) at round $t$
with action set $\Phi=\bar{\Phi}_{h}(x)=\mathrm{co}(\\{\phi_{h}(x,a)\ :\
a\in\mathcal{A}\\})$, distribution $\mu=\mathcal{N}(0,\eta^{2}\cdot I_{d})$,
and $\omega=1$. It follows from Theorem 4.8 that

$\displaystyle\sum_{t=1}^{T}f_{h}^{(t)}(x,\pi_{h}^{\star}(x))-\sum_{t=1}^{T}f_{h}^{(t)}(x,\pi_{h}^{(t)}(x))=$
$\displaystyle\sum_{t=1}^{T}\langle
w_{h}^{(t)},\phi_{h}(x,\pi_{h}^{\star}(x))\rangle-\sum_{t=1}^{T}\langle
w_{h}^{(t)},\phi_{h}(x,\pi_{h}^{(t)}(x))\rangle$ $\displaystyle\leq$
$\displaystyle\eta^{-1}(2BH)^{2}T+{\eta\sqrt{d}},$

where we have used that $\|\phi_{h}(x,a)\|\leq 1$ for all $x,a,h$, that
$\mathcal{N}(0,\eta^{2}\cdot I_{d})$ is $(\eta\sqrt{d},\eta^{-1})$-stable
(Lemma 4.10), and that $\|w_{h}^{(t)}\|_{2}\leq\beta=2BH$, using the
constraint Eq. 19d in Critic (and where the value of $\beta$ is set on 2 of
Algorithm 1 per 4.2).∎

######  Lemma 4.10.

For any $\eta>0$, $\mathcal{N}(0,\eta^{2}\cdot I_{d})$ is
$(\eta\sqrt{d},\eta^{-1})$-stable.

###### Proof.

We first note that
$\mathbb{E}_{Z\sim\mathcal{N}(0,\eta^{2}I_{d})}[\|Z\|_{2}]\leq\eta\sqrt{\mathbb{E}_{Z\sim\mathcal{N}(0,I_{d})}[Z^{2}]}=\eta\sqrt{d}$.

Let $\mu_{\eta}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ denote the probability
density function of $\mathcal{N}(0,\eta^{2}I_{d})$. To verify the second
condition of stability, we compute, for any $v\in\mathbb{R}^{d}$,

$\displaystyle\int_{\rho\in\mathbb{R}^{d}}|\mu_{\eta}(\rho)-\mu_{\eta}(\rho-v)|d\rho=$
$\displaystyle
2D_{\mathsf{TV}}({\mathcal{N}(0,\eta^{2}I_{d})},{\mathcal{N}(v,\eta^{2}I_{d})})$
$\displaystyle\leq$
$\displaystyle\sqrt{2\operatorname{KL}({\mathcal{N}(0,\eta^{2}I_{d})}||{\mathcal{N}(v,\eta^{2}I_{d})})}=\|v\|_{2}/\eta,$

where we have used Pinsker’s inequality and the formula for KL divergence
between Gaussians. ∎

Finally, we are ready to prove Theorem 4.1.

###### Proof of Theorem 4.1.

Let the parameters $T,\eta,\varepsilon_{\mathsf{apx}},\alpha,\beta,\sigma$ be
chosen as in 4.2. Note that these parameter settings ensure that $1/\sigma\leq
1/\sqrt{\varepsilon_{\mathsf{BE}}}$, which in turn ensures that

$\displaystyle 3BH\zeta\leq 3BH\cdot C_{\ref{cor:ibe-
linear}}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/\varepsilon_{\mathsf{BE}}^{2})}+1/\sqrt{\varepsilon_{\mathsf{BE}}}\right)\leq
1,$ (35)

by our assumption that $\varepsilon_{\mathsf{BE}}\leq c_{0}(BH)^{-2}d^{-2}$
and as long as $c_{0}$ is sufficiently small.

Fix an arbitrary policy $\pi^{\star}\in\Pi$. Recall that $\pi^{(t)}$ denotes
the policy chosen by Actor (Algorithm 1) in step $t\in[T]$, and
$f^{(t)}=f^{w^{(t)}}$. Moreover, let us write
$M^{(t)}:=M^{f^{(t)},\pi^{(t)}}$. The choices of
$\alpha,\beta,\varepsilon_{\mathsf{apx}}$ in 4.2 ensure that, by Lemma 4.6, we
have that, over the draw of $\mathcal{D}$,
$\operatorname{Pr}(\mathcal{E}_{\alpha,\beta,\sigma,\varepsilon_{\mathsf{apx}}})\geq
1-\delta/2$. We next wish to use Lemma 4.5 with $\pi=\pi^{(t)}$, for each
$t\in[T]$. To do so, we need to check that
$\pi^{(t)}\in\Pi^{\mathsf{Plin},{\sigma}}$: indeed,
$\pi_{h}^{(t)}=\pi_{h,\theta_{h}^{(t)},\eta}$, where $\theta_{h}^{(t)}$
satisfies $\|\theta_{h}^{(t)}\|_{2}\leq t\cdot\max_{s\leq
t}\|w_{h}^{(s)}\|_{2}\leq T\beta$ (by Corollary 3.3, which is applicable
because of Eq. 35). Then
$\frac{\eta}{\|\theta_{h}^{(t)}\|_{2}}\geq\frac{\eta}{T\beta}=\sigma$, where
we have used the definition of $\eta,\sigma$ in 4.2.

If we let $\mathcal{F}^{(t)}$ denote the sigma-algebra generated by
$\mathcal{D},w^{(1)},\ldots,w^{(t)}$, then Lemma 4.5 ensures that, for each
$t$, $\operatorname{Pr}(\mathcal{E}_{\pi^{(t)}}|\mathcal{F}^{(t-1)})\geq
1-\delta/(2T)$. (In particular, we use here that the randomness in the call to
EstFeature in Critic is chosen independently at each step $t$.) By a union
bound, it follows that
$\operatorname{Pr}\left(\mathcal{E}_{\alpha,\sigma,\varepsilon_{\mathsf{apx}}}\cap\bigcap_{t\in[T]}\mathcal{E}_{\pi^{(t)}}\right)\geq
1-\delta$. We write
$\mathcal{E}^{\star}:=\mathcal{E}_{\alpha,\sigma,\varepsilon_{\mathsf{apx}}}\cap\bigcap_{t\in[T]}\mathcal{E}_{\pi^{(t)}}$.

By Lemma 4.5, under the event $\mathcal{E}^{\star}$, for each $t\in[T]$, we
have

$\displaystyle
V_{1}^{\scriptscriptstyle{M,\pi^{\star}}}(x_{1})-V_{1}^{\scriptscriptstyle{M,\pi^{(t)}}}(x_{1})\leq$
$\displaystyle
V_{1}^{\scriptscriptstyle{M^{(t)},\pi^{\star}}}(x_{1})-V_{1}^{\scriptscriptstyle{M^{(t)},\pi^{(t)}}}(x_{1})+3\beta
H\zeta+2\alpha\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M\,\pi^{\star}}}[\phi_{h}(x_{h},a_{h})]\|_{\Sigma_{h}^{-1}}.$
(36)

Next, using the performance difference lemma applied (Lemma B.3) to the MDP
$M^{(t)}$, we have

$\displaystyle\sum_{t=1}^{T}V_{1}^{\scriptscriptstyle{M^{(t)},\pi^{\star}}}(x_{1})-V_{1}^{\scriptscriptstyle{M^{(t)},\pi^{(t)}}}(x_{1})$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}^{\scriptscriptstyle{M^{(t)},\pi^{\star}}}\left[Q_{h}^{\scriptscriptstyle{M^{(t)},\pi^{(t)}}}(x_{h},\pi_{h}^{\star}(x_{h}))-Q_{h}^{\scriptscriptstyle{M^{(t)},\pi^{(t)}}}(x_{h},\pi_{h}^{(t)}(x_{h}))\right]$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}^{\scriptscriptstyle{M^{(t)},\pi^{\star}}}\left[f_{h}^{(t)}(x_{h},\pi_{h}^{\star}(x_{h}))-f_{h}^{(t)}(x_{h},\pi_{h}^{(t)}(x_{h}))\right]$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}\left[f_{h}^{(t)}(x_{h},\pi_{h}^{\star}(x_{h}))-f_{h}^{(t)}(x_{h},\pi_{h}^{(t)}(x_{h}))\right]$
$\displaystyle=$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}\left[\sum_{t=1}^{T}f_{h}^{(t)}(x_{h},\pi_{h}^{\star}(x_{h}))-f_{h}^{(t)}(x_{h},\pi^{(t)}_{h}(x_{h}))\right],$
(37)

where the second equality uses Lemma 4.3, the third equality uses the fact
that the dynamics of $M^{(t)}$ are the same as those of $M$, and the final
equality rearranges. Next, Lemma 4.9 guarantees that for each possible choice
of $x_{h}$, we have

$\displaystyle\sum_{t=1}^{T}f_{h}^{(t)}(x_{h},\pi_{h}^{\star}(x_{h}))-\sum_{t=1}^{T}f_{h}^{(t)}(x_{h},\pi_{h}^{(t)}(x_{h}))\leq\eta^{-1}(2BH)^{2}T+{\eta\sqrt{d}}.$
(38)

Combining Eq. 37, Eq. 38, and Eq. 36 yields that, under $\mathcal{E}^{\star}$,

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(V_{1}^{\scriptscriptstyle{M,\pi^{\star}}}-V_{1}^{\scriptscriptstyle{M,\pi^{(t)}}}(x_{1})\right)\leq$
$\displaystyle
2\alpha\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}[\phi_{h}(x_{h},a_{h})]\|_{\Sigma_{h}^{-1}}+\eta^{-1}(2BH)^{2}+\frac{\eta\sqrt{d}}{T}+3\beta
H\zeta.$ (39)

Note that the choices of $\eta,\sigma,\zeta$ in 4.2 gives that
$1/\sigma\leq\varepsilon_{\mathsf{BE}}^{-1/2}$, meaning that

$\displaystyle\zeta\leq C_{\ref{cor:ibe-
linear}}\varepsilon_{\mathsf{BE}}d^{3/2}\cdot\left(\sqrt{d\log(d/(\varepsilon_{\mathsf{BE}}\sigma))}+\varepsilon_{\mathsf{BE}}^{-1/2}\right)\leq
C\varepsilon_{\mathsf{BE}}^{1/2}d^{3/2}\log(1/\varepsilon_{\mathsf{BE}}),$
(40)

for some constant $C>0$; note that we have used that
$\varepsilon_{\mathsf{BE}}\leq d^{-1}$ and thus $\sqrt{d\log d}\leq
O(\varepsilon_{\mathsf{BE}}^{-1/2}\log^{1/2}(1/\varepsilon_{\mathsf{BE}}))$ in
the above display. Combining Eqs. 39 and 40 gives

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(V_{1}^{\scriptscriptstyle{M,\pi^{\star}}}-V_{1}^{\scriptscriptstyle{M,\pi^{(t)}}}(x_{1})\right)$
$\displaystyle\leq$ $\displaystyle
2\alpha\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}[\phi_{h}(x_{h},a_{h})]\|_{\Sigma_{h}^{-1}}+\frac{4BHd^{1/4}}{\sqrt{T}}+2BH\sqrt{d}\varepsilon_{\mathsf{BE}}^{1/2}+6CBH^{2}d^{3/2}\cdot\varepsilon_{\mathsf{BE}}^{1/2}\log(1/\varepsilon_{\mathsf{BE}}).$

Thus, by our choice of
$T=\frac{16B^{2}H^{2}d^{1/2}}{\varepsilon_{\mathsf{final}}^{2}}$ (4.2), it
follows that the policy $\hat{\pi}:=\frac{1}{T}\sum_{t=1}^{T}\pi^{(t)}$
satisfies

$\displaystyle
V_{1}^{\scriptscriptstyle{M,\pi^{\star}}}(x_{1})-V_{1}^{\scriptscriptstyle{M,\hat{\pi}}}(x_{1})$
$\displaystyle\leq$ $\displaystyle
2\alpha\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}[\phi_{h}(x_{h},a_{h})]\|_{\Sigma_{h}^{-1}}+\varepsilon_{\mathsf{final}}+O\left(BH^{2}d^{3/2}\cdot\varepsilon_{\mathsf{BE}}^{1/2}\log(1/\varepsilon_{\mathsf{BE}})\right)$
$\displaystyle\leq$ $\displaystyle
O\left(d^{3/2}BH\varepsilon_{\mathsf{BE}}^{1/2}\log(1/\varepsilon_{\mathsf{BE}})\sqrt{n}+BHd\log^{1/2}(dnBH/(\varepsilon_{\mathsf{final}}\delta))\right)\cdot\left(\frac{H}{\sqrt{n}}+\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}[\phi_{h}(x_{h},a_{h})]\|_{\Sigma_{h}^{-1}}\right)+\varepsilon_{\mathsf{final}},$

which is equal to the desired bound.

Finally, we analyze the computational cost of Algorithm 1. The only nontrivial
computation to be performed is the call to Critic in 7, which is made $T$
times. Thus, by Lemma 4.5, given an oracle which can solve the convex program
Eq. 19, the overall computational cost of Algorithm 1 is
$\operatorname{poly}(T,d,n,H,\log(1/\delta)/\varepsilon_{\mathsf{apx}}^{2})\leq\operatorname{poly}(d,H,n,\log(1/\delta),1/\varepsilon_{\mathsf{final}})$.
The same guarantee holds without existence of such an oracle; the necessary
modifications to the proof are described below in Remark 4.4. ∎

######  Remark 4.3.

Notice that in the case $\varepsilon_{\mathsf{BE}}=0$, the final steps of the
proof above yield the (slightly stronger) bound

$\displaystyle
V_{1}^{\scriptscriptstyle{M,\pi^{\star}}}(x_{1})-V_{1}^{\scriptscriptstyle{M,\hat{\pi}}}(x_{1})$
$\displaystyle\leq$ $\displaystyle
O\left(\frac{BHd\log^{1/2}(dnBH/(\varepsilon_{\mathsf{final}}\delta))}{\sqrt{n}}\right)\cdot\sum_{h=1}^{H}\|\mathbb{E}^{\scriptscriptstyle{M,\pi^{\star}}}[\phi_{h}(x_{h},a_{h})]\|_{n\Sigma_{h}^{-1}}+\varepsilon_{\mathsf{final}}.$

######  Remark 4.4 (Solving the convex program).

In this remark, we discuss the minor modifications necessary to the proof of
Theorem 4.1 to establish its guarantee without assumption of an oracle which
can solve the program Eq. 19.

Note that the program Eq. 19 is a convex program in $O(dH)$ variables
consisting of linear equalities and $\ell_{2}$ norm constraints, for which all
coefficients of the variables can be specified with
$\log\operatorname{poly}(\alpha,\beta,d,n)\leq\log\operatorname{poly}(n,B,d,H,\log(1/\delta))$
bits. Thus, for any $\epsilon>0$, the ellipsoid algorithm returns vectors
$w,\xi\in\mathbb{R}^{dH}$ which satisfy the constraints up to $\epsilon$ error
and $\epsilon$-approximately minimize the objective Eq. 19a in time
$\operatorname{poly}(d,H,\log(nB/(\delta\epsilon)))$. Then it is immediate
that Item 1 of Lemma 4.5 gives only the weaker guarantee
$V_{1}^{M^{f,\pi}}(x_{1})\leq V_{1}^{M,\pi}(x_{1})+\epsilon$. Moreover, in the
proof of Item 2 of Lemma 4.5, the right-hand side of Eq. 24 has an additional
$O(\epsilon\cdot\alpha H)$ term (as Eq. 19c holds up to additive $\epsilon$),
which may be absorbed in the first term (namely, $3\beta H\zeta_{\sigma}$) by
increasing the constants, as long as $\epsilon$ is sufficiently small. In
turn, Lemma 4.5 is used to establish Eq. 36: thus this equation gains an
additional term of $\epsilon$ on the right-hand side as well as additional
constant factor. This additional terms propagate to degrade the bound of
Theorem 4.1 by a constant factor.

##  5 Lower bounds

In this section we prove Theorem 1.2, restated formally below as Theorem 5.1.
In Section 5.1, we construct a family of MDPs that forms the basis of the
lower bound. Using this family of MDPs, we then prove Theorem 1.2 in Section
5.2.

######  Theorem 5.1.

Let $\varepsilon_{\mathsf{BE}}\in(0,1)$ and $n\in\mathbb{N}$ be given, and set
$d=H=2$. Then there are state and action spaces $\mathcal{X},\mathcal{A}$ with
$|\mathcal{A}|=4$ as well as feature mappings
$\phi_{h}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$ ($h\in[H]$), so that
the following holds, for any offline RL algorithm $\mathfrak{A}$. There is
some MDP $M$ which has inherent Bellman error with respect to the feature
mappings $\phi_{h}$ bounded by $2\varepsilon_{\mathsf{BE}}$ and which
satisfies Assumption 2.2, some distribution over datasets $\mathcal{D}$
satisfying Assumption 2.3, and some policy $\pi^{\star}\in\Pi^{\mathsf{Plin}}$
so that: $\mathscr{C}_{\mathcal{D},\pi^{\star}}=O(1)$ with probability 1 over
the draw of $\mathcal{D}$ yet the output policy $\hat{\pi}$ of $\mathfrak{A}$
satisfies

$\displaystyle\mathbb{E}\left[V_{1}^{\pi^{\star}}(x_{1})-V_{1}^{\hat{\pi}}(x_{1})\right]\geq\Omega\left(\sqrt{\varepsilon_{\mathsf{BE}}}+\frac{1}{\sqrt{n}}\right),$
(41)

where the expectation is over the draw of $\mathcal{D}$ and the randomness in
$\mathfrak{A}$.

###  5.1 Construction of the family $\mathcal{M}_{\varepsilon_{\mathsf{BE}}}$.

Fix $\varepsilon_{\mathsf{BE}}>0$. For simplicity we assume that
$L:=1/\sqrt{\varepsilon_{\mathsf{BE}}}$ is an even integer. Given bits
$b_{\mathsf{rew}},b_{\mathsf{init}}\in\\{0,1\\}$ and
$(b_{\ell,e})_{\ell\in[L],e\in\\{0,1\\}}\in\\{0,1\\}^{2L}$, we write
$\mathbf{b}=(b_{\mathsf{rew}},b_{\mathsf{init}},(b_{\ell,e})_{\ell\in[L],e\in\\{0,1\\}})\in\\{0,1\\}^{2L+2}$
to denote the collection of all these bits. We construct a class
$\mathcal{M}_{\varepsilon_{\mathsf{BE}}}=\\{M^{\mathbf{b}}\\}_{\mathbf{b}\in\\{0,1\\}^{2L+2}}$
of MDPs $M^{\mathbf{b}}$, each of which has inherent Bellman error bounded
above by $\varepsilon_{\mathsf{BE}}$ with respect to some fixed feature
mappings. All MDPs $M\in\mathcal{M}_{\varepsilon_{\mathsf{BE}}}$ have horizon
$H=2$ and feature dimension $d=2$. The state and action spaces of each
$M\in\mathcal{M}_{\varepsilon_{\mathsf{BE}}}$ are given as follows:

$\displaystyle\mathcal{X}=\\{\mathfrak{s}_{1},\mathfrak{t}_{1},\mathfrak{s}_{2},\bar{\mathfrak{s}}_{2},\mathfrak{q}_{2}\\}\cup\\{\mathfrak{s}_{2}^{\zeta},\mathfrak{t}_{2,0}^{\zeta},\mathfrak{t}_{2,1}^{\zeta}\\}_{\zeta\in[0,1]}\qquad\mathcal{A}=\\{0,1,2,3\\},$
(42)

where $\zeta$ ranges over $[0,1]$. (We remark that we will only need to use
the states
$\mathfrak{s}_{2}^{\zeta},\mathfrak{t}_{2,0}^{\zeta},\mathfrak{t}_{2,1}^{\zeta}$
for values of $\zeta$ which are in
$\\{0,\varepsilon_{\mathsf{BE}},2\varepsilon_{\mathsf{BE}},\ldots,\sqrt{\varepsilon_{\mathsf{BE}}}\\}$,
but to simplify notation we opt to define states corresponding to all
$\zeta\geq 0$.)

#### Feature vectors.

The feature vectors corresponding to $\mathcal{X},\mathcal{A}$ are defined
below. We use the convention that if we specify fewer than $4$ actions at a
state, then all remaining actions at the state have equal behavior (i.e.,
feature vectors and transition) to action 0 at that state. For normalizing
constant ${\alpha}:=(\sqrt{2})^{-1}$, we define, for each $h\in[2]$:

  * •

$\phi_{h}(\mathfrak{s}_{1},0)={\alpha}\cdot(1,0)$,
$\phi_{h}(\mathfrak{s}_{1},1)={\alpha}\cdot(0,1)$.

  * •

$\phi_{h}({\mathfrak{t}}_{1},0)={\alpha}\cdot(1,1)$ and
$\phi_{h}({\mathfrak{t}}_{1},1)={\alpha}\cdot(1,-1)$.

  * •

$\phi_{h}(\bar{\mathfrak{s}}_{2},0)={\alpha}\cdot(0,0)$.

  * •

$\phi_{h}(\mathfrak{s}_{2},0)={\alpha}\cdot(0,1)$,
$\phi_{h}(\mathfrak{s}_{2},1)={\alpha}\cdot(0,-1)$.

  * •

For each $\zeta\in[0,1]$,
$\phi_{h}(\mathfrak{s}_{2}^{\zeta},0)={\alpha}\cdot(0,\zeta)$,
$\phi_{h}(\mathfrak{s}_{2}^{\zeta},1)={\alpha}\cdot(1,0)$,
$\phi_{h}(\mathfrak{s}_{2}^{\zeta},2)={\alpha}\cdot(0,-\zeta)$,
$\phi_{h}(\mathfrak{s}_{2}^{\zeta},3)={\alpha}\cdot(-1,0)$.

  * •

For each $\zeta\in[0,1]$ and $b\in\\{0,1\\}$,
$\phi_{h}(\mathfrak{t}_{2,b}^{\zeta},0)={\alpha}\cdot(1,(1-2b)\zeta)$ and
$\phi_{h}(\mathfrak{t}_{2,b}^{\zeta},1)={\alpha}\cdot(-1,-(1-2b)\zeta)$. Via
slight abuse of notation, we identify
$\mathfrak{t}_{2,0}^{0},\mathfrak{t}_{2,1}^{0}$, i.e.,
$\mathfrak{t}_{2,0}^{0}=\mathfrak{t}_{2,1}^{0}$.

#### Transitions and rewards.

Consider any $M:=M^{\mathbf{b}}\in\mathcal{M}_{\varepsilon_{\mathsf{BE}}}$,
and write
$\mathbf{b}=(b_{\mathsf{rew}},b_{\mathsf{init}},\\{b_{\ell,e}\\}_{\ell\in[L],e\in\\{0,1\\}})\in\\{0,1\\}^{2L+2}$.
We proceed to define the initial state distribution, transitions and rewards
of $M$. The initial state distribution has all its mass concentrated on
$\mathfrak{t}_{1}$. The transitions are defined as follows:

  * •

$(\mathfrak{s}_{1},1)$ transitions to $\bar{\mathfrak{s}}_{2}$ with
probability 1.

  * •

$(\mathfrak{s}_{1},0)$ and $(\mathfrak{t}_{1},b_{\mathsf{init}})$ each
transition to the distribution that puts mass $1/L$ on each of the states
$\mathfrak{s}_{2}^{\ell\cdot\varepsilon_{\mathsf{BE}}}$, for $\ell\in[L]$.

  * •

$(\mathfrak{t}_{1},1-b_{\mathsf{init}})$ transitions to the distribution
which:

    * –

Puts mass $1/(2L)$ on $\mathfrak{t}_{2,0}^{(\ell-
b_{\ell,0})\cdot\varepsilon_{\mathsf{BE}}}$ for each $\ell\in[L]$;

    * –

Puts mass $1/(2L)$ on $\mathfrak{t}_{2,1}^{(\ell-
b_{\ell,1})\cdot\varepsilon_{\mathsf{BE}}}$ for each $\ell\in[L]$.

The rewards are defined as follows:

  * •

$r_{1}(x,a)=0$ for all $x\in\mathcal{X},a\in\mathcal{A}$, i.e., rewards at
step 1 are linear with $\theta^{\mathsf{r}}_{1}=(0,0)$.

  * •

The rewards at step 2 are linear with respect to the coefficient vector
$\theta^{\mathsf{r}}_{2}=(1-2b_{\mathsf{rew}},1/R)$, where $R:=16$.

#### Verifying low inherent bellman error.

Next, we verify that each MDP
$M^{\mathbf{b}}\in\mathcal{M}_{\varepsilon_{\mathsf{BE}}}$ has low inherent
Bellman error and satisfies Assumption 2.2 with respect to the feature
mappings $\phi_{h}$ defined above.

######  Lemma 5.2 (Low inherent Bellman error and boundedness).

For any $M=M^{\mathbf{b}}\in\mathcal{M}_{\varepsilon_{\mathsf{BE}}}$, $M$ has
inherent Bellman error $2\varepsilon_{\mathsf{BE}}$ and satisfies Assumption
2.2 with $B=\sqrt{2}$.

###### Proof.

It is straightforward to see that

$\displaystyle\mathcal{B}_{1}=\mathcal{B}_{2}=\left\\{w\in\mathbb{R}^{2}\ :\
{\alpha}|w_{1}|+{\alpha}|w_{2}|\leq 1\right\\},$

meaning that the second item of Assumption 2.2 is satisfied with
$B=1/\alpha=\sqrt{2}$. Moreover, by choice of $\alpha$ the first item is
immediate, and the third item holds since for all $(x,a)$,
$|r_{2}(x,a)|\leq\alpha\cdot\|\theta^{\mathsf{r}}_{2}\|_{1}=\alpha\cdot(1+1/R)\leq
1$.

We must verify Eq. 3 for $h\in\\{1,2\\}$. We begin with the case $h=1$. For
$\theta\in\mathbb{R}^{2}$, define

$\displaystyle\mathcal{T}_{1}\theta:=\left(\frac{1}{L}\sum_{\ell=1}^{L}\left(\max_{a\in\mathcal{A}}\langle\theta,\phi_{2}(\mathfrak{s}_{2}^{\ell\cdot\varepsilon_{\mathsf{BE}}},a)\rangle\right),0\right),$

which belongs to $\mathcal{B}_{1}$ since its first coordinate is bounded above
in absolute value by
$\alpha\cdot\max\\{|\theta_{1}|,L\varepsilon_{\mathsf{BE}}|\theta_{2}|\\}\leq\alpha\cdot(|\theta_{1}|+|\theta_{2}|)\leq
1$.

Since $r_{1}(x,a)=0$ for all $x,a$, we certainly have that, for each
$(x,a)\in(\\{\mathfrak{s}_{1}\\}\times\mathcal{A})\cup(\mathfrak{t}_{1},b_{\mathsf{init}})$,
$(\phi_{1}(x,a))_{1}=1$ and thus

$\displaystyle\langle\phi_{h}(x,a),\mathcal{T}_{1}\theta\rangle=\mathbb{E}_{x^{\prime}\sim
P_{h}^{\scriptscriptstyle{M}}(x,a)}\left[r_{1}(x,a)+\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(x^{\prime},a^{\prime}),\theta\rangle\right],$
(43)

meaning that Eq. 3 holds for these $(x,a)$. Now consider the state-action pair
$(x,a)=(\mathfrak{t}_{1},1-b_{\mathsf{init}})$. For each $\ell\in[L]$ and
$\theta\in\mathbb{R}^{2}$, we have

$\displaystyle\left|\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(\mathfrak{s}_{2}^{\ell\varepsilon_{\mathsf{BE}}},a^{\prime}),\theta\rangle-\frac{1}{2}\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(\mathfrak{t}_{2,0}^{(\ell-
b_{\ell,0})\varepsilon_{\mathsf{BE}}},a^{\prime}),\theta\rangle-\frac{1}{2}\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(\mathfrak{t}_{2,1}^{(\ell-
b_{\ell,1})\varepsilon_{\mathsf{BE}}},a^{\prime}),\theta\rangle\right|$
$\displaystyle\leq$
$\displaystyle\alpha|\theta_{2}|\varepsilon_{\mathsf{BE}}+\left|\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(\mathfrak{s}_{2}^{\ell\varepsilon_{\mathsf{BE}}},a^{\prime}),\theta\rangle-\frac{1}{2}\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(\mathfrak{t}_{2,0}^{\ell\varepsilon_{\mathsf{BE}}},a^{\prime}),\theta\rangle-\frac{1}{2}\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(\mathfrak{t}_{2,1}^{\ell\varepsilon_{\mathsf{BE}}},a^{\prime}),\theta\rangle\right|=\alpha|\theta_{2}|\varepsilon_{\mathsf{BE}}\leq\varepsilon_{\mathsf{BE}}.$

It follows that

$\displaystyle\left|\langle\phi_{h}(\mathfrak{t}_{1},1-b_{\mathsf{init}}),\mathcal{T}_{1}\theta\rangle-\mathbb{E}_{x^{\prime}\sim
P_{h}^{\scriptscriptstyle{M}}(\mathfrak{t}_{1},b_{\mathsf{init}})}\left[r_{1}(\mathfrak{t}_{1},b_{\mathsf{init}})+\max_{a^{\prime}\in\mathcal{A}}\langle\phi_{2}(x^{\prime},a^{\prime}),\theta\rangle\right]\right|\leq\varepsilon_{\mathsf{BE}},$

verifying Eq. 3 holds for $(x,a)=(\mathfrak{t}_{1},b_{\mathsf{init}})$.
Finally, the validity of Eq. 3 for $(x,a)=(\mathfrak{s}_{1},1)$ is immediate
since $(\mathcal{T}_{1}\theta)_{2}=0$.

Next we verify Eq. 3 for $h=2$. Since all feature vectors are identically 0 at
step $h=H+1=3$ (by convention), we take
$\mathcal{T}_{2}\theta=\theta^{\mathsf{r}}_{2}$ (which is in $\mathcal{B}_{2}$
since $\alpha\cdot(1+1/R)\leq 1$), and satisfies
$r_{2}(x,a)=\langle\phi_{2}(x,a),\theta^{\mathsf{r}}_{2}\rangle$ for all
$(x,a)$. ∎

###  5.2 Proof of Theorem 5.1

We are now ready to prove Theorem 5.1.

###### Proof of Theorem 5.1.

First, note that if $1/\sqrt{n}\geq\sqrt{\varepsilon_{\mathsf{BE}}}$, then the
lower bound is straightforward and well-known. In particular, consider
$\mathcal{X}:=\\{\mathfrak{s}_{1},\mathfrak{s}_{2}\\},\mathcal{A}:=\\{0,1\\}$
with $\phi_{1}(x,0)=(1,0),\phi_{1}(x,1)=(0,1)$ for each $x\in\mathcal{X}$, and
$\phi_{2}(\mathfrak{s}_{1},a)=(1,0),\phi_{2}(\mathfrak{s}_{2},a)=(0,1)$ for
each $a\in\mathcal{A}$. We let the rewards be linear with respect to some
vectors $\theta^{\mathsf{r}}_{1},\theta^{\mathsf{r}}_{2}\in\mathbb{R}^{2}$