# Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for
Dimension-Dependent Adaptivity

Emmeran Johnson  Department of Mathematics, Imperial College London, United
Kingdom  Correspondence<EMAIL_ADDRESS>Ciara Pike-Burke
Department of Mathematics, Imperial College London, United Kingdom  Patrick
Rebeschini  Department of Statistics, University of Oxford, United Kingdom

###### Abstract

We theoretically explore the relationship between sample-efficiency and
adaptivity in reinforcement learning. An algorithm is sample-efficient if it
uses a number of queries $n$ to the environment that is polynomial in the
dimension $d$ of the problem. Adaptivity refers to the frequency at which
queries are sent and feedback is processed to update the querying strategy. To
investigate this interplay, we employ a learning framework that allows sending
queries in $K$ batches, with feedback being processed and queries updated
after each batch. This model encompasses the whole adaptivity spectrum,
ranging from non-adaptive ‘offline’ ($K=1$) to fully adaptive ($K=n$)
scenarios, and regimes in between. For the problems of policy evaluation and
best-policy identification under $d$-dimensional linear function
approximation, we establish $\Omega(\log\log d)$ lower bounds on the number of
batches $K$ required for sample-efficient algorithms with $n=O(poly(d))$
queries. Our results show that just having adaptivity ($K>1$) does not
necessarily guarantee sample-efficiency. Notably, the adaptivity-boundary for
sample-efficiency is not between offline reinforcement learning ($K=1$), where
sample-efficiency was known to not be possible, and adaptive settings.
Instead, the boundary lies between different regimes of adaptivity and depends
on the problem dimension.

##  1 Introduction

Data collection in Reinforcement Learning (RL) usually falls into two main
paradigms: online and offline. An online learner interacts with the
environment, immediately receiving feedback and adapting its decisions in
real-time. In contrast in offline RL, the dataset is collected in a single
batch prior to observing any feedback. Many practical applications consider RL
algorithms with limited adaptivity, which fall between online and offline RL.
For example, in clinical trials, groups of patients undergo multiple
treatments simultaneously and the treatment allocations are only be updated
once the outcomes of the all the previous group have been observed (Yu et al.,
2021). Similar settings with parallelized data-collection include marketing,
advertising and numerical simulations (Esfandiari et al., 2021). There are
also applications where the data collection needs to be validated prior to
deployment by a human due to concerns of safety (Dann et al., 2019) and
fairness (Koenecke et al., 2020), which with large scale data collection, is
not feasible to have at every data point.

This motivates considering the multi-batch learning model (Perchet et al.,
2015) where a data-set of size $n$ is collected in $K$ batches, and feedback
from within a batch is only observed at the end of a batch. This means only
data from previous batches can be used to select how the next batch is
collected. This is also known as growing batch RL (Lange et al., 2012). We
refer to it as _multi-batch RL_ to avoid any confusion with offline RL, also
called batch RL, which considers a single batch.

The multi-batch setting covers different levels of adaptivity to feedback,
which refers to how frequently the learner can process feedback and use it to
update its data collection strategy. We measure it by the number of batches
$K$. At one extreme, all the data is collected in a single batch ($K=1$,
offline-RL, no adaptivity). At the other extreme, each batch contains a single
data-point ($K=n$, full adaptivity111Typically, online refers to a setting
with full-adaptivity along a single trajectory (sequence of transitions from a
starting state, potentially with restarts). Our notion of full-adaptivity
covers this, but is more general since we allow settings with a generative
model where samples from any state-action pair can be drawn.). We say a
learner is _adaptive_ when $K>1$. In some of the applications that parallelize
data-collection mentioned above, algorithms with low-adaptivity where $K$ is
as small as possible are of interest since there may be a cost associated to
unifying and processing the parallelized data.

We study adaptivity in infinite-horizon discounted Markov Decision Processes
(MDPs). We focus on 1) the policy evaluation (PE) problem, where the learner
is tasked with estimating the value of a target policy, and 2) the best policy
identification (BPI) problem, where the learner is tasked with finding a near-
optimal policy. A desirable property of the learner is that it is sample-
efficient, i.e. it only needs a dataset size that is polynomial in the
dimension of the problem (e.g. state space size). We aim to understand the
minimum level of adaptivity necessary for sample efficient learning.

Linear Function Approximation: MDPs faced in practice often have state spaces
$\mathcal{S}$ or action spaces $\mathcal{A}$ that are infinite or too large to
handle directly (Silver et al., 2016). Function approximation is used to
reduce the learning problem to a smaller set of parameters that leverage
structure in the problem. We consider a form of linear function approximation
(Bellman et al., 1963) that assumes the (action)-value of a policy is a linear
combination of known features of the state-action pair with an unknown
parameter, each of dimension $d$. The sample complexity of algorithms is then
measured with respect to the smaller dimension $d$ instead of the dimensions
of the MDP ($|\mathcal{S}|,|\mathcal{A}|$).

Adaptive vs Non-Adaptive: It is known there is a sample-efficiency separation
between offline RL ($K=1$) and fully-adaptive RL ($K=n$) under linear function
approximation. Algorithms have been shown to be sample-efficient in the fully-
adaptive setting (Lattimore et al., 2020) and under various assumptions in the
offline setting (Duan et al., 2020; Xie & Jiang, 2020). Without assumptions in
the offline setting, it has been shown information-theoretically that no
sample-efficient algorithms can solve the PE or BPI problem (Zanette, 2021)
even under the best possible offline dataset, showing the separation. However,
the MDP constructions of Zanette (2021) are easily solved with algorithms
using $K=2$ batches (see proofs of their Theorems 1 and 3), suggesting that
the boundary of this separation may be between offline RL ($K=1$) and RL with
adaptivity ($K>1$). This motivates studying the values of $K$ where sample-
efficiency is not possible and asking the following questions:

Does the boundary of sample-efficiency under linear function approximation lie
between offline RL ($K=1$) and RL with adaptivity ($K>1$)? If not, is the
boundary dimension-dependent?

In this paper, we establish an $\Omega(\log\log d)$ lower-bound on the number
of adaptive updates, $K$, required to solve both PE and BPI problems sample-
efficiently. This answers the first question negatively and the second
positively. This is achieved through a non-trivial extension of the framework
of (Zanette, 2021) for the offline setting to the multi-batch setting, which
we describe next.

Learning Process: When faced with an unknown MDP within a known class of MDPs,
we consider a learner over $K$ rounds. In a round, the learner chooses a set
of state-action queries with knowledge of the feedback from previous rounds.
The following characteristics strengthen our lower bounds:

  * •

Exact feedback: the feedback for a state-action query is the reward and
transition _functions_ , not a single sample. This makes a query equivalent to
observing infinite samples from the reward and transition functions if these
are stochastic and removes any hardness due to uncertainty.

  * •

We consider two ways for the learner to specify the set of queries. The first
(policy-induced) is through trajectories induced by chosen policies. The
second (policy-free) explicitly specifies the state-action queries. Our
results hold for any such set of queries whose size is polynomial in $d$.

  * •

Realizability: the MDPs considered satisfy the linear representation of the
action-values.

Tabular and finite-horizon MDPs and linear bandits are easily solved in the
offline setting ($K=1$) under this framework but infinite-horizon discounted
MDPs are not (Zanette, 2021). Our work studies what happens beyond the offline
setting ($K>1$) for infinite-horizon discounted MDPs.

Contributions: Our results show that a number of batches $K$ constant with
respect to the dimension $d$ is not enough to solve PE or BPI problems sample-
efficiently. Specifically, we show that if we restrict the total number of
queries (over all batches) to be polynomial in $d$ (sample-efficiency), then

  * •

there are PE problems that require $K=\Omega(\log\log d)$ to be solved to
arbitrary accuracy.

  * •

with only policy-free queries, there are PE and BPI problems that require
$K=\Omega(\log\log d)$ to be solved to arbitrary accuracy, even if all
policies satisfy linear realizability of their action-values.

These results show that adaptivity ($K>1$) does not guarantee sample-
efficiency. The level of adaptivity, or number of batches $K$, needed to
guarantee sample-efficiency scales with the dimension $d$ of the linear
representation. In particular, the boundary of sample-efficiency does not lie
between offline RL ($K=1$) and adaptive RL ($K>1$). Instead this boundary must
lie within a regime of adaptivity scaling with dimension: $\Omega(\log\log
d)\leq K\leq n$.

Interestingly, the class of MDPs considered in Zanette (2021) can be solved
with $d+1$ queries and $K=2$ batches (observing feedback from the first batch
is enough to select queries in the second that fully solve the MDPs) [Zanette
(2021), Theorem 4]. Our results show that this is not possible in general and
that the class of MDPs we use for our results is fundamentally harder. From a
technical perspective, our work uses tools from the theory of subspace packing
with chordal distance (Soleymani & Mahdavifar, 2021). This enables the
environment to erase information across multiple dimensions ($m$-dimensional
subspaces, see Section 5) in response to queries, instead of a single
direction as in Zanette (2021), which ultimately allows us to achieve lower-
bounds for $K>1$.

##  2 Preliminaries

A Markov Decision Process (MDP) (Puterman, 1994) is a discrete-time stochastic
process comprised of a set of states $\mathcal{S}$, a set of actions
$\mathcal{A}=\bigcup_{s\in\mathcal{S}}\\{\mathcal{A}_{s}\\}$ where
$\mathcal{A}_{s}$ is the action space in state $s\in\mathcal{S}$ and, for each
state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}_{s}$, a next-state
transition function given by a measure $p(\cdot|s,a)$ and a (deterministic)
reward function $r(s,a)\in[-1,1]$. In a state $s$, an agent chooses an action
$a$, receives a reward $r(s,a)$ and transitions to a new state according to
$p(\cdot|s,a)$. Once in the new state, the process continues. The actions
chosen by an agent are formalised by policies. A deterministic policy
$\pi:\mathcal{S}\rightarrow\mathcal{A}$ is a mapping from a state to an
action. In each state $s\in\mathcal{S}$, an agent following policy $\pi$
chooses action $\pi(s)\in\mathcal{A}_{s}$. We do not consider stochastic
policies.

In this work, for a discount factor $\gamma\in[0,1)$, we consider
$\gamma$-discounted infinite-horizon MDPs. We measure the performance of a
policy $\pi$ with respect to the value function
$V^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$,

$V^{\pi}(s)=\mathbb{E}\Big{[}\sum\limits_{t=0}^{\infty}\gamma^{t}r(s_{t},\pi(s_{t}))|\pi,s_{0}=s\Big{]},$

where $s_{t},a_{t}$ are the state and action in time-step $t$ and the
expectation is with respect to the randomness in the transitions. This is a
notion of long-term reward that describes the discounted rewards accumulated
over future time-steps when following policy $\pi$ and starting in state $s$.
We consider $\gamma$ as fixed throughout. It is also useful to work with the
action-value function
$Q^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$,

$Q^{\pi}(s,a)=\mathbb{E}\Big{[}\sum\limits_{t=0}^{\infty}\gamma^{t}r(s_{t},\pi(s_{t}))|\pi,s_{0}=s,a_{0}=a\Big{]},$

which is similar to $V^{\pi}$, with the additional constraint of taking action
$a$ in the first time-step. For a policy $\pi$, we define the Bellman
evaluation operator $\mathcal{T}^{\pi}$ for action-value functions as:

$\displaystyle(\mathcal{T}^{\pi}Q)(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a)}[Q(s^{\prime},\pi(s^{\prime}))].$

The action-value $Q^{\pi}$ of a policy $\pi$ is the unique fixed-point of the
Bellman evaluation operator $\mathcal{T}^{\pi}$.

Under certain conditions on the state and action space, it is known that there
exists a deterministic policy that simultaneously maximises $V^{\pi}$ and
$Q^{\pi}$ for all states and actions [Puterman (1994), Theorem 6.2.12]. We
call such a policy an optimal policy and denote it by $\pi^{\star}$. We will
also denote $V^{\pi^{\star}}=V^{\star}$ and $Q^{\pi^{\star}}=Q^{\star}$. Given
an MDP $M$, we will sometimes write $V^{\pi}_{M}$ to denote the value of a
policy $\pi$ in the MDP $M$ (similarly for
$V^{\star}_{M},Q^{\pi}_{M},Q^{\star}_{M},p_{M},r_{M},\mathcal{T}^{\pi}_{M}$).
We denote the unit Euclidean ball in $\mathbb{R}^{d}$ by
$\mathcal{B}=\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq 1\\}$ and its boundary by
$\partial\mathcal{B}=\\{x\in\mathbb{R}^{d}:\|x\|_{2}=1\\}$. For $n$ vectors
$v_{1},...,v_{n}\in\partial\mathcal{B}$, we denote the subspace spanning the
vectors by $\langle v_{1},...,v_{n}\rangle$. For two positive functions $f$
and $g$, we say $f(x)=\Omega(g(x))$ if $\exists c>0,N$ such that for all
$x>N$, $f(x)\geq cg(x)$.

##  3 Problem Setting

In this section, we formally define the RL problems and the learning model we
consider. We borrow the framework from the work of Zanette (2021) and extend
it beyond the offline RL setting.

###  3.1 Policy Evaluation (PE)

Let $\mathcal{M}$ be a class of MDPs with the same $\mathcal{S}$ and
$\mathcal{A}$. For $M\in\mathcal{M}$, let $\Pi_{M}$ be a set of
(deterministic) policies and $\Pi=\\{\Pi_{M}\\}_{M\in\mathcal{M}}$. A PE
problem defined by $(\mathcal{M},\Pi)$ consists of:

  1. 1.

An instance $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$, where $M\in\mathcal{M}$ is
an MDP, $\pi_{M}\in\Pi_{M}$ is a target policy and $\bar{s}\in\mathcal{S}$ is
a starting state. $\mathcal{M}$, $\Pi$ and $\bar{s}$ are known but $M$ and
$\pi_{M}$ are unknown.

  2. 2.

An interaction procedure with the MDP $M$ to collect a dataset $\mathcal{D}$
(see Section 3.3).

  3. 3.

An objective: Following the collection of the dataset $\mathcal{D}$, the
target policy $\pi_{M}$ becomes known to the learner. Based on $\mathcal{D}$
and $\pi_{M}$, the learner produces an output
$\widehat{Q}_{\mathcal{D}}(\bar{s},\cdot)$ estimating the action-value
$Q^{\pi_{M}}_{M}(\bar{s},\cdot)$ of the target policy $\pi_{M}$. The
performance of the learner is evaluated by the accuracy of the output on any
instance, formalized as$(\varepsilon,\delta)$-soundness (Definition 3.1).

######  Definition 3.1.

A learner is $(\varepsilon,\delta)$-sound for PE problems characterised by
$(\mathcal{M},\Pi)$ if for all $M\in\mathcal{M},\pi_{M}\in\Pi_{M}$, the
learner faced with instance $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$ outputs
$\widehat{Q}_{\mathcal{D}}$ that is $\varepsilon$-accurate with
probability222There is no randomness in the feedback of the dataset
$\mathcal{D}$ (see Section 3.3) so the probabilities are with respect to
randomness arising from the learner’s query selection or output strategies. at
least $1-\delta$, i.e. it satisfies
$\mathbb{P}\Big{(}\sup_{a\in\mathcal{A}}|Q^{\pi_{M}}_{M}(\bar{s},a)-\widehat{Q}_{\mathcal{D}}(\bar{s},a)|<\varepsilon\Big{)}>1-\delta$.

###  3.2 Best Policy Identification (BPI)

Let $\mathcal{M}$ be a class of MDPs with the same $\mathcal{S}$ and
$\mathcal{A}$. A BPI problem defined by $\mathcal{M}$ consists of:

  1. 1.

An instance $(\bar{s},M,\mathcal{M})$, where $M\in\mathcal{M}$ is an MDP in
$\mathcal{M}$ and $\bar{s}\in\mathcal{S}$ is a starting state. $\mathcal{M}$
and $\bar{s}$ are known but $M$ is unknown.

  2. 2.

An interaction procedure with the MDP $M$ to collect a dataset $\mathcal{D}$
(see Section 3.3).

  3. 3.

An objective: Based on $\mathcal{D}$, the learner produces an output
$\widehat{\pi}_{\mathcal{D}}$ of a near-optimal policy for $M$. The
performance of the learner is evaluated by $(\varepsilon,\delta)$-soundness
(Definition 3.2), i.e. the sub-optimality of the output policy on any instance
(see 1.).

######  Definition 3.2.

A learner is $(\varepsilon,\delta)$-sound for BPI problems characterised by
$\mathcal{M}$ if for all $M\in\mathcal{M}$, the learner faced with instance
$(\bar{s},M,\mathcal{M})$ outputs $\widehat{\pi}_{\mathcal{D}}$ that is
$\varepsilon$-optimal with probability2 at least $1-\delta$, i.e. it satisfies
$\mathbb{P}\Big{(}(V^{\star}_{M}-V^{\widehat{\pi}_{\mathcal{D}}}_{M})(\bar{s})<\varepsilon\Big{)}>1-\delta$.

###  3.3 Multi-Batch Learning Model

We define some important notions related to our learning model. A query is a
state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}_{s}$ that is submitted
to the unknown MDP $M$ and for which feedback is returned. A query formalises
how the learner interacts with an MDP, the feedback received is defined next.

######  Definition 3.3 (Query-Feedback).

In return for a query $(s,a)$ the environment provides feedback to the
learner. For BPI, the feedback is the reward $r_{M}(s,a)$ and the transition
function $p_{M}(\cdot|s,a)$. For PE, the learner also receives evaluations of
the target policy $\pi_{M}$ for all states in the support of
$p_{M}(\cdot|s,a)$, i.e. $\\{\pi_{M}(s’):s’\in\mathcal{S}\text{ s.t.\
}p_{M}(s’|s,a)>0\\}$.

######  Remark 3.4.

The learner receives the transition function $p_{M}(\cdot|s,a)$ for a query
$(s,a)$, instead of a sample from $p_{M}(\cdot|s,a)$. This removes any
statistical uncertainty and is equivalent to observing infinite samples, which
strengthens any lower-bounds proven under this frame-work. The evaluations of
the target policy $\pi_{M}$ are motivated by giving partial information about
$\pi_{M}$ to the learner.

Algorithm 1 Multi-Batch Learning Model

1:(Input) PE or BPI problem and a number of batches $K$.

2:Initialise $\widebar{\mathcal{D}}_{0}=\emptyset$.

3:for $k=1,...,K$ do

4: (Query Selection) With knowledge of $\widebar{\mathcal{D}}_{k-1}$, learner
chooses a set of queries $\mu_{k}$.

5: (Data Collection) Environment receives queries $\mu_{k}$ and returns to
learner $\mathcal{D}_{k}$ (set of queries + feedback for all queries in
$\mu_{k}$ \- see Definition 3.3). Learner updates
$\widebar{\mathcal{D}}_{k}=\bigcup_{i=1}^{k}\mathcal{D}_{i}$.

6:Set
$\mathcal{D}=\widebar{\mathcal{D}}_{K}\equiv\bigcup_{i=1}^{K}\mathcal{D}_{i}$
(and for PE, $\pi_{M}$ becomes known).

7:(Output) Learner returns $\widehat{Q}_{\mathcal{D}}$ (PE) or
$\widehat{\pi}_{\mathcal{D}}$ (BPI).

We summarise the learning model in Algorithm 1. We consider two mechanisms for
the learner to specify the set of queries $\mu_{k}$ at round $k$ (line 4). For
both, we denote $n_{k}=|\mu_{k}|$ the number of queries at round $k$ and
$n=\sum_{k=1}^{K}n_{k}$ the total number of queries.

1\. Policy-Free Queries: In the first mechanism, the learner explicitly
selects the set of queries $\mu_{k}$ by selecting a set of state-action pairs.
The learner has access to the dataset $\widebar{\mathcal{D}}_{k-1}$, which
contains the feedback of the queries from the previous rounds from the MDP $M$
the learner is faced with. Let $\mathcal{M}_{k}\subset\mathcal{M}$ be the set
of MDPs in $\mathcal{M}$ that would produce exactly the feedback in dataset
$\widebar{\mathcal{D}}_{k-1}$ given the queries in the previous rounds. Given
the queries this is deterministic since there is no randomness in the feedback
of a query (see Definition 3.3). The learner can use $\mathcal{M}_{k}$ in the
selection of the queries at round $k$ but the specific MDP it is interacting
with remains unknown if $|\mathcal{M}_{k}|>1$.

2\. Policy-Induced Queries: The second mechanism produces queries indirectly
by selecting policies and using the queries along trajectories induced by
these policies interacting with the MDP $M$. Stochastic transitions imply
different realizations of a trajectory for a policy from a same starting-
state. We allow the queries to be the state-actions pairs along all
realizations of the trajectories.

######  Definition 3.5 (Policy-Induced Queries (Zanette (2021), Definition
2)).

Fix a set $T_{k}=\\{(s_{0i}^{k},\pi_{i}^{k},c_{i}^{k})\\}_{i=1}^{\kappa_{k}}$
of $\kappa_{k}$ triplets, each containing a starting state $s_{0i}^{k}$, a
deterministic policy $\pi_{i}^{k}$ and a trajectory length $c_{i}^{k}$. Then
the query set $\mu_{k}$ induced by $T_{k}$ is defined as

$\displaystyle\mu_{k}=\bigcup_{(s_{0},\pi,c)\in T_{k}}Reach(s_{0},\pi,c)$
$\displaystyle\text{ where }\qquad Reach(s_{0},\pi,c)=\\{(s,a)|\exists
t<c\text{ s.t.\ }\mathbb{P}((s_{t},a_{t})=(s,a)|\pi,s_{0})>0\\}$

are the state-action pairs reachable in $c$ or less time-steps from $s_{0}$
using policy $\pi$. Note $(s_{t},a_{t})$ is the random state-action pair
encountered at time-step $t$ upon following $\pi$ from $s_{0}$.

The learner specifies a set $T_{k}$ from which a set of queries $\mu_{k}$ is
induced333A sample-efficient learner requires $|\mu_{k}|$ to be polynomial in
$d$ but the learner does not directly select $\mu_{k}$. For example, if the
transition function is stochastic it is possible that $T_{k}$ induces a
$\mu_{k}$ with $|\mu_{k}|=\infty$ or non-polynomial in dimension. The MDPs we
consider all have deterministic transitions so this is not an issue..
Similarly to policy-free queries, the learner can use $\mathcal{M}_{k}$ in the
selection of $T_{k}$ at round $k$ but the specific MDP it is interacting with
remains unknown if $|\mathcal{M}_{k}|>1$.

######  Remark 3.6.

Policy-induced queries include policy-free queries as a special case
($c_{i}^{k}=1$). However, if the dynamics of all MDPs in the class
$\mathcal{M}$ are the same, then policy-induced queries are also policy free
because the learner knows the dynamics of the MDP it is interacting with. So
it knows exactly the queries that any set $T_{k}$ will induce and can specify
these as policy-free queries. If the dynamics of all MDPs in the class
$\mathcal{M}$ are not the same, then policy-induced queries can reveal more
information because a trajectory is guided by the dynamics of the MDP while
policy-free queries only reveal information about individual distinct
transitions. Because of this, we will obtain slightly stronger results for
policy-free queries in Section 4.

Adaptivity: The multi-batch learning model encompasses different levels of
adaptivity to feedback, which is measured by the number of batches $K$:

  * •

For $K=1$, the learner is non-adaptive and the dataset $\mathcal{D}$ is
collected in a single batch. This is the model considered by Zanette (2021)
for offline RL that we extend for general $K$.

  * •

For $K>1$, the learner is adaptive and the dataset $\mathcal{D}$ is collected
in multiple batches. Queries for a batch are selected based on feedback from
previous batches.

  * •

For $K=n$ (i.e. each batch contains a single data-point), the learner is
fully-adaptive. The queries are selected sequentially and depend on the
feedback from previous queries.

##  4 Main Results

In this section, we present our main results: lower-bounds on the number of
rounds $K$ for sample-efficient algorithms. First, we state some assumptions.
We assume $\gamma>\sqrt{3/4}$.

We consider a linear representation of the action-values for a known feature
map of state-action pairs. This is a form of linear function approximation
that is strictly more general than linear MDPs (Zanette et al., 2020), which
assume the reward and transition functions are linearly representable.
Specifically, we consider the following assumptions:

######  Assumption 4.1 ($Q^{\pi}_{M}$-Realizability (Zanette (2021),
Assumption 1)).

Given any PE problem instance $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$, there
exists a known feature map
$\phi:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$ s.t.
$\|\phi(\cdot,\cdot)\|_{2}\leq 1$ and there exists
$\theta_{M}^{\pi_{M}}\in\mathcal{B}$ such that for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle Q^{\pi_{M}}_{M}(s,a)=\phi(s,a)^{T}\theta_{M}^{\pi_{M}}.$

This first assumption is only used for results on PE problems.

######  Assumption 4.2 ($Q^{\pi}$-Realizability for every policy (Zanette
(2021), Assumption 3)).

Given any BPI $(\bar{s},M,\mathcal{M})$ or PE
$(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$ problem instance, there exists a known
feature map $\phi:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$ s.t.
$\|\phi(\cdot,\cdot)\|_{2}\leq 1$ and for any policy $\pi$ there exists
$\theta_{M}^{\pi}\in\mathcal{B}$ s.t. for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle Q^{\pi}_{M}(s,a)=\phi(s,a)^{T}\theta_{M}^{\pi}.$

The second assumption is stronger as the action-value of every policy (not
just policies in $\Pi$) is linearly represented and in particular it holds for
$Q^{\star}$ as it corresponds to the action-value of the optimal policy
$\pi^{\star}$. We assume that when these assumptions hold, the learner is
aware of them.

Finally, we formally define a sample-efficient learner:

######  Definition 4.3.

A learner for PE or BPI problems under Assumptions 4.1 or 4.2 is sample-
efficient if its total number of queries $n=\sum_{k=1}^{K}n_{k}$ is polynomial
in $d$.

###  4.1 Policy-Induced Queries

We first present a result for PE under policy-induced queries. Since all MDPs
in the class used in the proof share the same dynamics, policy-induced queries
are equivalent to policy-free queries (see Remark 3.6) and the result holds
for both. The full proof can be found in Appendix D.

######  Theorem 4.4.

Fix $d$ sufficiently large. There exists a class of MDPs $\mathcal{M}$ and
policies $\Pi$ defining PE problems $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$
satisfying Assumption 4.1 such that any sample-efficient learner better than
$(1,1/2)$-sound using policy-induced or policy-free queries requires
$K=\Omega(\log\log d)$.

In the class of MDPs used for Theorem 4.4 we can hide information about
$M\in\mathcal{M}$ in the target-policy for PE but cannot for BPI. Instead, we
could hide information in the transitions but this can be revealed by
following policy trajectories (policy-induced queries) in our constructions.
In the next section, we restrict the learner to policy-free queries and
provide results for both PE and BPI.

###  4.2 Policy-Free Queries

We now consider only policy-free queries, which gives the environment freedom
to hide information in the transition function of the MDP and leads to lower-
bounds for PE and BPI that hold for the stronger Assumption 4.2 of all-policy
realizability. The full proof can be found in Appendix E.

######  Theorem 4.5.

Fix $d$ sufficiently large. There exists a class of MDPs $\mathcal{M}$ and
policies $\Pi$ defining problems for PE $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$
and BPI $(\bar{s},M,\mathcal{M})$ satisfying Assumption 4.2 such that any
sample-efficient learner better than $(1,1/2)$-sound using policy-free queries
requires $K=\Omega(\log\log d)$.

###  4.3 Discussion

The results indicate that $K=\Omega(\log\log d)$ batches are necessary for
solving PE or BPI tasks sample-efficiently under realizable linear function
approximation. Beyond the exact dependence on $d$, the significance of these
results is that just having $K>1$ is insufficient. In particular, more
adaptivity is needed as the dimension of the linear representation increases.
These results demonstrate that sample efficiency is impossible not only in
offline RL, but also in settings with some level of adaptivity ($K=o(\log\log
d)$). Therefore, the boundary at which sample-efficiency becomes impossible is
at a dimension-dependent level of adaptivity between offline and full-
adaptivity. This leaves interesting open directions on the existence of a
sample-efficient algorithm using $K=O(\log\log d)$ batches.

Furthermore, in Appendix A we provide results for the fully adaptive setting
where the number of batches $K$ is equal to the number of total queries $n$
(i.e. each batch contains a single query). We show that if the feature-space
covers $\mathcal{B}$, there is a learner that solves any realizable
(Assumption 4.1) PE problem in $d$ queries. Assuming a known target policy
$\pi$, a linear dependence on $d$ was already known to be possible using roll-
outs from $\pi$ (Lattimore et al., 2020), however the dependence on $d$ was
coupled with other quantities such as the effective horizon $1/(1-\gamma)$ and
desired accuracy $\varepsilon$. Our result states that $d$-queries are
sufficient to find $Q^{\pi}$ exactly ($\varepsilon=0$), independently of
$\gamma$. Our result relies heavily on the condition that the learner observes
the transition function $p_{M}(\cdot|s,a)$ rather than a sample
$s^{\prime}\sim p_{M}(\cdot|s,a)$ for a query $(s,a)$ (see Section 3.3),
though our result under this condition is strong since using this condition
with the roll-outs from $\pi$ would not give exact convergence in $d$-queries.
We also provide a matching lower-bound (that also holds for BPI). These
results serve to illustrate the trade-off between sample-efficiency and low-
adaptivity for PE under our framework. Full-adaptivity allows low sample-
complexity, while reducing adaptivity below $K=o(\log\log d)$ comes at the
cost of high sample-complexity (losing sample-efficiency).

##  5 Proof Sketch

In this section, we provide intuition for the proof of Theorem 4.4 regarding
the hardness of learning under the framework described in Section 3. We extend
the ideas of Zanette (2021) beyond offline RL to our multi-batch problem. We
consider the PE problem with policy-free queries under Assumption 4.1 for
feature vectors $\phi(\cdot,\cdot)$ covering the unit Euclidean ball
$\mathcal{B}$ (see Figure 1). The intuition for Theorem 4.5 is closely
related.

Consider the first batch of data with $n_{1}$ queries and let $(s_{i},a_{i})$
be the i-th query and $(s_{i}^{+},\pi_{M}(s_{i}^{+}))$ the corresponding
(assumed deterministic) successor state and target policy evaluation. Define

$\displaystyle\Phi=\begin{bmatrix}\phi(s_{1},a_{1})^{T}\\\ ...\\\
\phi(s_{n_{1}},a_{n_{1}})^{T}\\\ \end{bmatrix},\quad
r=\begin{bmatrix}r(s_{1},a_{1})\\\ ...\\\ r(s_{n_{1}},a_{n_{1}})\\\
\end{bmatrix},\quad\Phi^{+}=\begin{bmatrix}\phi(s_{1}^{+},\pi_{M}(s_{1}^{+})^{T}\\\
...\\\ \phi(s_{n_{1}}^{+},\pi_{M}(s_{n_{1}}^{+}))^{T}\\\ \end{bmatrix}.$

Since $Q^{\pi_{M}}$ is the fixed point of the Bellman evaluation operator:
$Q^{\pi_{M}}(s,a)=(\mathcal{T}^{\pi_{M}}Q^{\pi_{M}})(s,a)$ and by Assumption
4.1 there exists $\theta^{\pi_{M}}_{M}$ such that
$Q^{\pi_{M}}(s,a)=\phi(s,a)^{T}\theta^{\pi_{M}}_{M}$ for any $(s,a)$, the
learner aims to find a solution $\theta$ satisfying the (local) Bellman
equation

$\displaystyle\Phi\theta=r+\gamma\Phi^{+}\theta\implies(\Phi-\gamma\Phi^{+})\theta=r.$

If $X=\Phi-\gamma\Phi^{+}$ is not full-rank, this equation does not have a
unique solution. The learner only chooses $\Phi$. The environment, with
knowledge of $\Phi$, can pick $\Phi^{+}$ to maximise the dimension of the
null-space444By the rank-nullity theorem, this is equivalent to minimising the
rank of $X$. of $X$, which can be viewed as erasing information along many
directions (see Figure 1 left). This phenomenon where the value of a policy in
a state depends on the same value in the successor states is known as
bootstrapping and is the mechanism inducing hardness in our setting as it
allows the environment to choose these successor states adversarially to erase
information.

Although the learner can prevent the environment from erasing information
along certain directions (see Figure 1 right), since $n_{1}$ is polynomial in
$d$ this only prevents the environment from erasing information in a limited
number of directions. Specifically, we show that if $n_{1}$ is less than
exponential in $d^{1/4}$ then there is a subspace of dimension $d^{1/4}$ that
can be included in the null-space of $X$.

Prior to choosing $n_{2}$ queries for the 2nd batch, the learner observes the
feedback from the first batch. It becomes aware of the directions of the null-
space and can focus its queries for the next round on these directions.
However, the null-space is still at least $d^{1/4}$-dimensional and so the
same reasoning as in the first round can be applied where the original
dimension is now $d^{1/4}$. So if $n_{2}$ is less than exponential in
$d^{1/16}$ then there is a subspace of dimension $d^{1/16}$ that can be
included in the null-space of the new local Bellman equation that includes the
data from the 1st and 2nd batch.

After $k$ rounds if the number of queries at round $k$, $n_{k}$ is less than
exponential in $d^{1/4^{k}}$, then the null-space of the local Bellman
equation is still at least $d^{1/4^{k}}$-dimensional. If $\exp(d^{1/4^{k}})$
is more than polynomial in $d$, the sample-efficient learner cannot prevent a
non-zero null-space and the problem cannot be solved. The learner must reach a
round $K$ where $\exp(d^{1/4^{K}})$ becomes polynomial in $d$, requiring
$K=\Omega(\log\log d)$ rounds, from which we get our lower-bound.

Figure 1: Left: Information can be erased in multiple directions: Consider the
setting where information is being erased along the pink plane $\mathcal{N}$:
the learner’s queries $\phi(s_{i},a_{i})$ are shown in blue and the
environment’s responses $-\gamma\phi(s_{i}^{+},\pi_{M}(s_{i}^{+}))$ are shown
in black. The rows of $X$,
$\phi(s_{i},a_{i})-\gamma\phi(s_{i}^{+},\pi_{M}(s_{i}^{+}))$ (blue + black
vectors) all lie on the yellow line so the learner acquires no information in
the directions of the pink subspace $\mathcal{N}$, the null-space of $X$.
Right: Information cannot be erased in all directions: Consider the opposite
setting where information is being erased along the pink line $\mathcal{N}$.
Because of the constraint $\|\phi(s,a)\|_{2}\leq 1$ and $\gamma<1$, a query
$\phi_{1}$ (in blue) in the pink cap cannot have $\phi_{1}-\gamma\phi^{+}_{1}$
(blue + black vector) projected back onto the yellow plane (unless
$\|\gamma\phi_{1}\|_{2}>\gamma\implies\|\phi_{1}\|_{2}>1$). Despite the
environment not being able to erase information in certain directions, if the
number of queries is ”small”, it can always find directions to erase.

Description of the MDP construction for which the learner cannot do better
than $(1,1/2)$-soundness. Consider an MDP class $\mathcal{M}$ with
$\mathcal{S}=\mathcal{A}=\mathcal{B}$ and a feature map $\phi$ such that
$\phi(s,a)=a$. The successor state of $(s,a)$ is deterministic and is the
action $a$. Fix $w\in\partial\mathcal{B}$ and consider two MDPs: $M_{w,+}$ and
$M_{w,-}$. We denote the reward function for either MDP with the same
subscript:

$\displaystyle\text{for }z\in\\{+,-\\}\text{ : }\quad\text{ on }M_{w,z}:\qquad
r_{w,z}(s,a)=\begin{cases}0,&\text{if}\
a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)\\\
z(1-\gamma)a^{T}w,&\text{otherwise},\end{cases}$

where $\mathcal{C}_{\gamma}(w)=\\{x\in\mathcal{B}:x^{T}w/\|w\|_{2}>\gamma\\}$
is the $\gamma$-hyperspherical cap of $w$. For a $w\in\partial\mathcal{B}$ and
a carefully designed target policy $\pi_{w}$, we show that Assumption 4.1
holds. We also show with some of the reasoning described earlier in this
section that if $n_{k}=poly(d)$ for all $k$ and $K=o(\log\log d)$, then none
of the learner’s queries are in
$\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$. Therefore the feedback
observed contains only rewards of $0$ and no information about the sign of the
rewards in $\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$. $M_{w,+}$ is
indistinguishable from $M_{w,-}$. Since $Q_{M_{w,+}}^{\pi_{w}}(\bar{s},w)=1$
and $Q_{M_{w,-}}^{\pi_{w}}(\bar{s},w)=-1$, the learner must incur an error of
$1$ with probability at least $1/2$. We provide all the details in Appendix D.
The construction for Theorem 4.5 is similar but the transitions differ across
MDPs (see Appendix E).

##  6 Related Works

The works discussed below are for infinite-horizon discounted MDPs unless
stated otherwise.

Tabular MDPs ($|\mathcal{A}|,|\mathcal{S}|$ are “small”) can be solved in the
offline setting under policy-free queries: model-based approaches (Li et al.,
2020; Agarwal et al., 2020) under a generative model are minimax-optimal (Azar
et al., 2013) with sample-complexity linear in the dimension of the MDP
$|\mathcal{A}|\times|\mathcal{S}|$. These methods estimate the MDP by sampling
equally from all state-action pair and then use dynamic programming approaches
on the estimated MDP. In particular, all the samples are drawn in a single-
batch. Beyond the generative model and under a restricted form of our policy-
induced queries (Definition 3.5), tabular offline RL is no longer sample
efficient (Xiao et al., 2022) and requires a number of samples exponential in
$|\mathcal{S}|$ or $1/(1-\gamma)$.

Linear Function Approximation: In the offline setting, there are lower-bounds
showing OPE or BPI is not possible with samples polynomial in the effective
horizon $1/(1-\gamma)$ or the linear dimension (Amortila et al., 2020; Chen et
al., 2021; Zanette, 2021). The bound of Zanette (2021) is the strongest as it
holds for any data-distribution. These exponential lower-bounds can be
overcome with assumptions such as low-distribution shift (Chen et al., 2021),
low inherent Bellman-error (Xie & Jiang, 2020; Duan et al., 2020) or low local
inherent Bellman error (Zanette, 2023). We refer the reader to the work of
Zanette (2021) for a more in depth discussion of offline RL. In the fully-
adaptive setting, there are sample-efficient algorithms under all-policy
realizability (Lattimore et al., 2020), under $V^{\star}$-realizability only
(Weisz et al., 2021) (if the action space is finite) and under linear MDPs
(Taupin et al., 2023; Kitamura et al., 2023).

Low-Switching Cost: Limited adaptivity in RL has mostly been studied in the
context of regret-minimisation algorithms with low-switching cost for finite-
horizon episodic MDPs, i.e. minimising the number of times the policy used
changes from one episode to the next. These works are not directly comparable
because they study regret-minimisation for finite-horizon MDPs and we study
BPI and PE in the discounted setting. Nevertheless, there are works on tabular
MDPs (Qiao et al., 2022; Bai et al., 2019; Zhang et al., 2020), linear MDPs
(Gao et al., 2021; Wang et al., 2021; Qiao & Wang, 2023) and MDPs with a
linear representation for the action values (Qiao et al., 2023).

The multi-batch learning model has been studied extensively for bandit
algorithms (Perchet et al., 2015; Jun et al., 2016; Gao et al., 2019;
Esfandiari et al., 2021; Duchi et al., 2018; Han et al., 2020; Ruan et al.,
2021). In RL, it has been studied in the regret-minimisation setting for
finite-horizon tabular (Zihan et al., 2022) and linear MDPs (Wang et al.,
2021) and MDPs under general function approximation (Xiong et al., 2023). A
closely related notion is deployment efficiency (Matsushima et al., 2021),
which constrains batches to be of a fixed size consisting of trajectories from
a single policy. In finite-horizon linear MDPs, it has been shown that BPI can
be solved to arbitrary accuracy with a number of deployments independent of
the dimension $d$ (Huang et al., 2022; Qiao & Wang, 2023) where the deployed
policy is a finite mixture of deterministic policies. Our results suggest that
infinite-horizon discounted MDPs under more general linear representation of
action-values are fundamentally harder since the number of deployments must
scale with dimension.

The policy finetuning setting assumes access to an offline dataset that can be
complemented with online trajectories (Xie et al., 2021) but is different from
our setting since there is no adaptivity constraint in the online algorithm,
i.e. once the initial dataset has been collected, the query selection strategy
can be updated after each new observation (or episode in the episodic
setting). However, if the additional trajectories are collected using a non-
adaptive policy instead of an online algorithm, we can recover our setting
with $K=2$ batches. This is studied by Zhang & Zanette (2023) who show that
for finite-horizon tabular MDPs, $K=2$ is enough to solve the BPI problem to
arbitrary accuracy. Our results rule out achieving a similar result for
infinite-horizon discounted MDPs under policy-free queries and linear function
approximation.

##  7 Conclusion

In this work, we have studied the connection between adaptivity and sample-
efficiency for RL algorithms solving PE and BPI problems under $d$-dimensional
linear function approximation. For multi-batch learning, we have established
$\Omega(\log\log d)$ lower-bounds on the number of batches $K$ needed to solve
the RL problems sample-efficiently (number of queries polynomial in $d$). In
particular, having adaptivity ($K>1$) does not guarantee sample-efficiency.
Consequently the boundary of sample efficiency must not lie between batch RL
($K=1$) and adaptive RL ($K>1$) but rather within a regime of adaptivity
scaling with dimension. These insights contribute to a deeper understanding of
the trade-offs and possibilities in designing sample-efficient RL algorithms
with low-adaptivity.

It remains unclear if the $\log\log d$ dependence on $d$ is tight. An upper-
bound similar to the one we have given for the fully-adaptive PE problem in
Appendix A could be established by developing new tools in the theory of
subspace covering. These would formalise the number of directions for which
the learner can prevent information erasure. It is also unclear if Theorem 4.4
under policy-induced queries also holds for BPI or if the sample-efficiency of
BPI-algorithms in low-adaptivity settings differs for policy-induced and
policy-free queries. We leave these as future work.

## References

  * Agarwal et al. (2020) Alekh Agarwal, Sham Kakade, and Lin F. Yang.  Model-based reinforcement learning with a generative model is minimax optimal.  In _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pp. 67–83. PMLR, 2020.
  * Amortila et al. (2020) Philip Amortila, Nan Jiang, and Tengyang Xie.  A variant of the wang-foster-kakade lower bound for the discounted setting.  2020\.  Preprint, arXiv: 2011.01075.
  * Azar et al. (2013) Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen.  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  _Machine Learning_ , 91(3):325–349, 2013.
  * Bai et al. (2019) Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang.  Provably efficient q-learning with low switching cost.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Bellman et al. (1963) Richard Bellman, Robert Kalaba, and Bella Kotkin.  Polynomial approximation–a new computational technique in dynamic programming: Allocation processes.  _Mathematics of Computation_ , 17(82):155–161, 1963.
  * Chen et al. (2021) Lin Chen, Bruno Scherrer, and Peter L Bartlett.  Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm.  2021\.  Preprint, arXiv: 2103.09847.
  * Conway et al. (1996) John H. Conway, Ronald H. Hardin, and Neil J. A. Sloane.  Packing lines, planes, etc.: packings in Grassmannian spaces.  _Experimental Mathematics_ , 5(2):139 – 159, 1996.
  * Dann et al. (2019) Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill.  Policy certificates: Towards accountable reinforcement learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 1507–1516. PMLR, 2019.
  * Duan et al. (2020) Yaqi Duan, Zeyu Jia, and Mengdi Wang.  Minimax-optimal off-policy evaluation with linear function approximation.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 2701–2709. PMLR, 2020.
  * Duchi et al. (2018) John Duchi, Feng Ruan, and Chulhee Yun.  Minimax bounds on stochastic batched convex optimization.  In _Proceedings of the 31st Conference On Learning Theory_ , volume 75 of _Proceedings of Machine Learning Research_ , pp. 3065–3162. PMLR, 2018.
  * Esfandiari et al. (2021) Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni.  Regret bounds for batched bandits.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(8):7340–7348, 2021.
  * Gao et al. (2021) Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang.  A provably efficient algorithm for linear markov decision process with low switching cost.  2021\.  Preprint, arXiv: 2101.00494.
  * Gao et al. (2019) Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou.  Batched multi-armed bandits problem.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Han et al. (2020) Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye.  Sequential batch learning in finite-action linear contextual bandits.  2020\.  Preprint, arXiv: 2004.06321.
  * Huang et al. (2022) Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie-Yan Liu.  Towards deployment-efficient reinforcement learning: Lower bound and optimality.  In _International Conference on Learning Representations_ , 2022.
  * Jia et al. (2023) Zeyu Jia, Randy Jia, Dhruv Madeka, and Dean P Foster.  Linear reinforcement learning with ball structure action space.  In _International Conference on Algorithmic Learning Theory_ , pp. 755–775. PMLR, 2023.
  * Jun et al. (2016) Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu.  Top arm identification in multi-armed bandits with batch arm pulls.  In _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , volume 51 of _Proceedings of Machine Learning Research_ , pp. 139–148. PMLR, 2016.
  * Kitamura et al. (2023) Toshinori Kitamura, Tadashi Kozuno, Yunhao Tang, Nino Vieillard, Michal Valko, Wenhao Yang, Jincheng Mei, Pierre Ménard, Mohammad Gheshlaghi Azar, Rémi Munos, Olivier Pietquin, Matthieu Geist, Csaba Szepesvári, Wataru Kumagai, and Yutaka Matsuo.  Regularization and variance-weighted regression achieves minimax optimality in linear MDPs: Theory and practice.  2023\.  Preprint, arXiv: 2305.13185.
  * Koenecke et al. (2020) Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups, John R. Rickford, Dan Jurafsky, and Sharad Goel.  Racial disparities in automated speech recognition.  _Proceedings of the National Academy of Sciences_ , 117(14):7684–7689, 2020.
  * Lange et al. (2012) Sascha Lange, Thomas Gabel, and Martin Riedmiller.  _Batch Reinforcement Learning_ , pp. 45–73.  Springer, 2012.
  * Lattimore et al. (2020) Tor Lattimore, Csaba Szepesvari, and Gellert Weisz.  Learning with good feature representations in bandits and in RL with a generative model.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 5662–5670. PMLR, 2020.
  * Li et al. (2020) Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen.  Breaking the sample size barrier in model-based reinforcement learning with a generative model.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Matsushima et al. (2021) Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu.  Deployment-efficient reinforcement learning via model-based offline optimization.  In _International Conference on Learning Representations_ , 2021.
  * Perchet et al. (2015) Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg.  Batched bandit problems.  In _Proceedings of The 28th Conference on Learning Theory_ , volume 40 of _Proceedings of Machine Learning Research_ , pp. 1456–1456. PMLR, 2015.
  * Puterman (1994) Martin L. Puterman.  _Markov decision processes : discrete stochastic dynamic programming_.  Wiley-Interscience, 1994.
  * Qiao & Wang (2023) Dan Qiao and Yu-Xiang Wang.  Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Qiao et al. (2022) Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang.  Sample-efficient reinforcement learning with loglog(T) switching cost.  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 18031–18061. PMLR, 2022.
  * Qiao et al. (2023) Dan Qiao, Ming Yin, and Yu-Xiang Wang.  Logarithmic switching cost in reinforcement learning beyond linear MDPs.  2023\.  Preprint, arXiv: 2302.12456.
  * Ruan et al. (2021) Yufei Ruan, Jiaqi Yang, and Yuan Zhou.  Linear bandits with limited adaptivity and learning distributional optimal design.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 74–87, 2021.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Soleymani & Mahdavifar (2021) Mahdi Soleymani and Hessam Mahdavifar.  New packings in grassmannian space.  In _2021 IEEE International Symposium on Information Theory (ISIT)_ , pp. 807–812, 2021.
  * Taupin et al. (2023) Jérôme Taupin, Yassir Jedra, and Alexandre Proutiere.  Best policy identification in discounted linear MDPs.  In _Sixteenth European Workshop on Reinforcement Learning_ , 2023.
  * Wang et al. (2021) Tianhao Wang, Dongruo Zhou, and Quanquan Gu.  Provably efficient reinforcement learning with linear function approximation under adaptivity constraints.  In _Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Weisz et al. (2021) Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, and Csaba Szepesvari.  On query-efficient planning in mdps under linear realizability of the optimal state-value function.  In _Proceedings of Thirty Fourth Conference on Learning Theory_ , volume 134 of _Proceedings of Machine Learning Research_ , pp. 4355–4385. PMLR, 2021.
  * Xiao et al. (2022) Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari.  The curse of passive data collection in batch reinforcement learning.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pp. 8413–8438. PMLR, 2022.
  * Xie & Jiang (2020) Tengyang Xie and Nan Jiang.  Q* approximation schemes for batch reinforcement learning: A theoretical comparison.  In _Conference on Uncertainty in Artificial Intelligence_ , pp. 550–559. PMLR, 2020.
  * Xie et al. (2021) Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai.  Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Xiong et al. (2023) Nuoya Xiong, Zhaoran Wang, and Zhuoran Yang.  A general framework for sequential decision-making under adaptivity constraints.  2023\.  Preprint, arXiv: 2306.14468.
  * Yu et al. (2021) Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin.  Reinforcement learning in healthcare: A survey.  _ACM Comput. Surv._ , 55(1):1–36, 2021.
  * Zanette (2021) Andrea Zanette.  Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 12287–12297. PMLR, 2021.
  * Zanette (2023) Andrea Zanette.  When is realizability sufficient for off-policy reinforcement learning?  In _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 40637–40668. PMLR, 2023.
  * Zanette et al. (2020) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent Bellman error.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 10978–10989. PMLR, 2020.
  * Zhang & Zanette (2023) Ruiqi Zhang and Andrea Zanette.  Policy finetuning in reinforcement learning via design of experiments using offline data.  2023\.  Preprint, arXiv: 2307.04354.
  * Zhang et al. (2020) Zihan Zhang, Yuan Zhou, and Xiangyang Ji.  Almost optimal model-free reinforcement learningvia reference-advantage decomposition.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Zihan et al. (2022) Zhang Zihan, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji.  Near-optimal regret bounds for multi-batch reinforcement learning.  In _Advances in Neural Information Processing Systems_ , 2022.

##  Appendix A Bounds for the Fully Adaptive Setting

In this section, we show an upper-bound result for the fully adaptive setting
($K=n$ \- see Section 3.3). In this setting, the oracle selects one query in
each round or batch of data, so chooses $(s_{k},a_{k})$ at round $k$ with
knowledge of the feedback from queries up to time $k-1$. The number of rounds
$K$ coincides with the number of queries $n$ (each batch contains one query).
In particular, since it is one query at a time, there is no difference between
policy-induced or policy-free queries. The upper bound we show relies on the
following assumptions on the feature space:

######  Assumption A.1 (Feature Map).

Fix a feature map $\phi$. Given any orthonormal set of vectors
$\\{u_{1},...,u_{n}\\}$ with $n<d$, it is possible to choose a state-action
pair $(s,a)$ such that $\phi(s,a)\in\langle u_{1},...,u_{n}\rangle^{\perp}$
and $\|\phi(s,a)\|_{2}=1$.

The superscript $\perp$ on a subspace refers to the orthogonal complememnt of
the subspace.

######  Theorem A.2.

Fix $d>0$. Consider any PE problem $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$
satisfying Assumptions 4.1 and A.1 for the same feature map $\phi$, then there
exists a fully-adaptive learner that solves the PE problem exactly in at most
$d$ queries.

We complement our upper-bound with a matching lower-bound, which holds for
both PE and BPI.

######  Theorem A.3.

Fix $d>0$. There exists a class of MDPs $\mathcal{M}$ and target policies
$\Pi$ characterising PE problems $(\bar{s},M,\mathcal{M},\pi_{M},\Pi)$ and BPI
problems $(\bar{s},M,\mathcal{M})$ that satisfy Assumption 4.2 and share the
same $\bar{s}$ and $M$ such that any fully-adaptive learner that is better
than $(1,1/2)$-sound requires $K=n\geq d$.

Theorem A.2 together with Theorem A.3 shows that exactly $d$ queries are
optimal for solving a PE problem under our feedback model and Assumption A.1.
The lower-bound is to be expected because the learner is operating in a
$d$-dimensional feature space so has to learn in $d$ directions. However, it
is interesting that the structure imposed by Assumption A.1 on the learner’s
capacity to explore the feature space is sufficient for the learner to fully
solve the problem in only $d$ queries. A similar assumption was studied by Jia
et al. (2023) to obtain a sample-efficient algorithm for BPI in finite-horizon
MDPs. We can obtain this result for PE with a simple analysis because the
learner can exploit that the action-value of a policy is the fixed point of a
linear operator, the Bellman evaluation operator. An equivalent approach does
not work for BPI since the action-value of the optimal policy is not the fixed
point of a linear operator.

The proofs of the theorems in this section can be found in Appendix F.

##  Appendix B Hyper-spherical caps and sectors for subspaces

Recall that $\mathcal{B}=\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq 1\\}$ is the
$d$-dimensional unit hyper-sphere.

######  Definition B.1.

Fix $w\in\mathcal{B}$. Define the $\gamma$-hyperspherical cap of $w$ as:

$\displaystyle\mathcal{C}_{\gamma}(w)=\Big{\\{}x\in\mathcal{B}:\frac{x^{T}w}{\|w\|_{2}}>\gamma\Big{\\}}.$

A vector $x$ is in the $\gamma$-hyperspherical cap of $w$ if the angle
$\theta$ between $x$ and $w$ satisfies

$\displaystyle\gamma<\|x\|_{2}\cos\theta\iff\theta<\arccos(\frac{\gamma}{\|x\|_{2}}).$

With $\gamma$ close to $1$, these represent a set of vectors in the hyper-cone
around $w$ that are close to the boundary of $\mathcal{B}$ (see Figure 1
right). The key property that motivates considering vectors in this set is
that they require a vector of norm greater than $\gamma$ to be projected in a
direction orthogonal to $w$. We extend the notion of $\gamma$-hyperspherical
caps to subspaces of multiple dimensions.

######  Definition B.2.

Fix a subspace $H$ of $\mathbb{R}^{d}$. Define the $\gamma$-hyperspherical
sector of $H$ as

$\displaystyle\overset{\triangle}{\mathcal{C}}_{\gamma}(H)=\Big{\\{}x\in\mathcal{B}:\exists
v\in H\text{ s.t. }\frac{x^{T}v}{\|v\|_{2}\|x\|_{2}}>\gamma\Big{\\}}.$

Beyond the extension to subspaces of multiple dimensions, Definition B.2
differs from Definition B.1 in two ways. It is a hyper-spherical sector rather
than cap, which does not restrict the vectors to be close to the boundary of
$\mathcal{B}$. It is two sided meaning that if
$x\in\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$, then
$-v\in\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$. Note that the subspace
$H$ is defined on $\mathbb{R}^{d}$ but
$\overset{\triangle}{\mathcal{C}}_{\gamma}(H)\subset\mathcal{B}$.

Similar to the intuition in the 1-dimensional case, a vector $x$ is in
$\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$ if there is a vector in $H$
whose angle with $x$ is ”small”. It is equivalent to taking the unions of the
$1$-dimensional $\gamma$-hyperspherical sectors of all the vectors in $H$.
Again, the key property that motivates considering vectors in this set is that
they require a vector of norm greater than $\gamma$ to be projected in a
direction orthogonal to $H$.

##  Appendix C Subspace Packing

###  C.1 Preliminaries

Denote the set of all $m$-dimensional subspaces of $\mathbb{R}^{d}$ as
$\mathcal{G}_{m,d}(\mathbb{R})$, which is called the Grassmannian space. An
element $A\in\mathcal{G}_{m,d}(\mathbb{R})$ is an $m$-dimensional subspace of
$\mathbb{R}^{d}$.

We present a measure of distance between subspaces known as the chordal
distance (Conway et al., 1996). Fix two subspaces
$A,B\in\mathcal{G}_{m,d}(\mathbb{R})$. The principal angles
$\theta_{1},...,\theta_{m}\in[0,\pi/2]$ between $A$ and $B$ are defined as

$\displaystyle\cos\theta_{i}=\max_{a\in A}\max_{B\in
B}\frac{a^{T}b}{\|a\|_{2}\|b\|_{2}}=a_{i}^{T}b_{i},$

for $i=1,...,m$ such that $\|a_{i}\|_{2}=\|b_{i}\|_{2}=1$, $a^{T}a_{j}=0$,
$b^{T}b_{j}=0$ for $1\leq j\leq i-1$. The chordal distance $d_{c}$ is then
defined as

$\displaystyle
d_{c}(A,B)=\sqrt{\sin^{2}\theta_{1}+\sin^{2}\theta_{2}+...+\sin^{2}\theta_{m}}.$

We define the notion of subspace packing, which is the usual notion of a
packing where the set is the Grassmanian space $\mathcal{G}_{m,d}(\mathbb{R})$
and the distance is the chordal distance.

######  Definition C.1.

A subspace packing $\mathcal{C}$ of $\mathcal{G}_{m,d}(\mathbb{R})$ is a set
of $m$-dimensional subspaces in $\mathbb{R}^{d}$ of size $|\mathcal{C}|$, i.e.
it is a subset of $\mathcal{G}_{m,d}(\mathbb{R})$. The minimum distance
between elements of $\mathcal{C}$ is measured by the chordal distance and is
denoted

$\displaystyle d_{\min}(\mathcal{C})=\min_{A,B\in\mathcal{C},A\neq
B}d_{c}(A,B).$

###  C.2 A subspace packing bound

######  Lemma C.2 (Soleymani & Mahdavifar (2021), Theorem 4).

Fix $d=2^{N}$ for some $N\in\mathbb{N}$ and integers $k<d$ and $m<d$. There
exists a packing $\mathcal{C}$ in $G_{m,d}(\mathbb{R})$ of size
$|\mathcal{C}|=\Big{(}\frac{d}{2}\Big{)}^{\lceil
k/2\rceil-1}\lfloor\frac{d}{m}\rfloor$ s.t

$\displaystyle
d_{\min}(\mathcal{C})\geq\sqrt{m}\sqrt{1-\frac{m(k-1)^{2}}{d}}.$

Theorem 4 from Soleymani & Mahdavifar (2021) is presented for packings in
$G_{m,d}(\mathbb{C})$ but they give (in Remark 1) a mapping from a packing in
$G_{m/2,d/2}(\mathbb{C})$ to a packing in $G_{m,d}(\mathbb{R})$ that preserves
the normalized distance $\delta_{c}$ ($=d_{\min}(\mathcal{C})/\sqrt{m}$)
between the elements of the packing, giving the result presented above.

###  C.3 Existence of an isolated subspace

The following lemma is the key result for the construction of the class of
MDPs used in the proof of our main results. It establishes that if a number of
points $n$ is “small”, then for any $n$ points there exists a subspace whose
$\gamma$-sector contains none of the $n$ points. The environment can erase
information along this subspace (see Section 5). See Appendix B for the
definition of $\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$ for a subspace
$H$. The proof is given in Appendix C.3.2.

######  Lemma C.3.

Fix $d=2^{N}$ for some $N\geq 8$. Consider $D=\\{y_{1},...,y_{n}\\}$, a set of
$n$ points s.t $y_{i}\in\mathcal{B}$ for all $i\in[n]$. If

$\displaystyle
n+1\leq\Big{(}\frac{d}{2}\Big{)}^{\frac{1}{8}g(\gamma)d^{1/4}},$

then there exists a subspace $A\in\mathcal{G}_{2^{\lceil
N/4\rceil},d}(\mathbb{R})$ of dimension $2^{\lceil N/4\rceil}$ s.t

$\displaystyle\forall x\in D,\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(A).$

####  C.3.1 Preliminary Lemmas

The proof of Lemma C.3 relies on the following lemmas. See Appendix C for the
definition of $\mathcal{G}_{m,d}(\mathbb{R})$ and the definition of a subspace
packing $\mathcal{C}$.

######  Lemma C.4.

Fix $d=2^{N}$ for some $N\in\mathbb{N}$. If there exists a packing
$\mathcal{C}$ in $G_{m,d}(\mathbb{R})$ of size $|\mathcal{C}|\geq n+1$ s.t
$d_{\min}(\mathcal{C})\geq\sqrt{m-g(\gamma)^{2}}$, then given a set
$\\{y_{1},...,y_{n}\\}$ of $n$ queries s.t $y_{i}\in\mathcal{B}$ for all
$i\in[n]$, there exists a subspace $H\in G_{m,d}(\mathbb{R})$ of dimension $m$
s.t $y_{i}\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(A)$ for all $i$.

This lemma establishes that if $n+1$ subspaces are sufficiently far in terms
of chordal distance, then for any $n$ points there is a subspace whose
$\gamma$-sector does not contain any of the $n$ points. The proof is given in
Appendix C.3.3

######  Lemma C.5.

Consider $(n+1)$ subspaces $A_{1},...,A_{n+1}$ of dimension $m$ s.t for any
$i\neq j$,

$\displaystyle\max_{x\in A_{i},z\in
A_{j}}\frac{x^{T}z}{\|x\|_{2}\|z\|_{2}}<g(\gamma)=2\gamma^{2}-1.$

Given $n$ vectors $y_{1},...,y_{n}\in\mathcal{B}$ (w.l.o.g. all unit norm),
then there is a subspace $H\in\\{A_{1},...,A_{n+1}\\}$ s.t for all
$y\in\\{y_{1},...,y_{n}\\}$,

$\displaystyle\max_{w\in H}\frac{y^{T}w}{\|w\|_{2}}\leq\gamma,$

meaning $y_{i}\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$ for
$i=1,...,n$.

This lemma is similar to Lemma C.4 but uses a more explicit notion of distance
between subspaces. The proof is given in Appendix C.3.4.

####  C.3.2 Proof of Lemma C.3

To prove Lemma C.3, we show the existence of a subspace packing $\mathcal{C}$
in $\mathcal{G}_{m,d}(\mathbb{R})$ (with $m=2^{\lceil N/4\rceil}$) and use
Lemma C.4. The subspace packing must satisfy two conditions:

  * •

$|\mathcal{C}|\geq n+1$.

  * •

$d_{\min}(\mathcal{C})\geq\sqrt{m-g(\gamma)^{2}}$.

To show the existence of a suitable subspace packing, we use Lemma C.2 with
$k=\lfloor\frac{g(\gamma)}{m}\sqrt{d}+1\rfloor$ ($\leq d$). Lemma C.2 gives a
packing $\mathcal{C}$ of size
$|\mathcal{C}|\geq\Big{(}\frac{d}{2}\Big{)}^{\frac{g(\gamma)}{2m}\sqrt{d}-1}\lfloor\frac{d}{m}\rfloor$
s.t

$\displaystyle d_{\min}(\mathcal{C})\geq\sqrt{m-g(\gamma)^{2}}.$

Substituting in $m=2^{\lceil N/4\rceil}$ into the lower-bound on the size of
$\mathcal{C}$ gives

$\displaystyle\lfloor\frac{d}{m}\rfloor\Big{(}\frac{d}{2}\Big{)}^{\frac{g(\gamma)\sqrt{d}}{2m}-1}$
$\displaystyle=\lfloor\frac{d}{m}\rfloor\Big{(}\frac{d}{2}\Big{)}^{-3/4}\Big{(}\frac{d}{2}\Big{)}^{\frac{g(\gamma)}{2}2^{N/2-\lceil
N/4\rceil}-\frac{1}{4}}\geq 2^{3/4}\frac{\lfloor
2^{3N/4}\rfloor}{2^{3N/4}}\Big{(}\frac{d}{2}\Big{)}^{\frac{g(\gamma)}{4}2^{N/4}-\frac{1}{4}}\geq\Big{(}\frac{d}{2}\Big{)}^{\frac{g(\gamma)}{8}d^{1/4}},$

where we used

  * •

$N/2-\lceil N/4\rceil\geq N/4-1$ because $\lceil x\rceil\leq x+1$.

  * •

$2^{3/4}\frac{\lfloor 2^{3N/4}\rfloor}{2^{3N/4}}\geq 1$ if $N\geq 2$.

  * •

$\frac{g(\gamma)}{4}2^{N/4}-\frac{1}{4}\geq\frac{g(\gamma)}{8}2^{N/4}$ if
$N\geq 8$ and $\gamma\geq\sqrt{3/4}$.

Since the condition given in the statement of the lemma is

$\displaystyle
n+1\leq\Big{(}\frac{d}{2}\Big{)}^{\frac{g(\gamma)}{8}d^{1/4}}\leq|\mathcal{C}|,$

the packing $\mathcal{C}$ satisfies $|\mathcal{C}|\geq n+1$ and
$d_{\min}(\mathcal{C})\geq\sqrt{m-g(\gamma)^{2}}$. By Lemma C.4 there exists a
subspace $A\in G_{m,d}(\mathbb{R})$ of dimension $m=2^{\lceil N/4\rceil}$ s.t

$\displaystyle\forall x\in D,\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(A),$

which concludes the proof of the lemma. ∎

####  C.3.3 Proof of Lemma C.4

Consider distinct $A,B\in\mathcal{C}$, i.e $A,B$ are subspaces of dimension
$m$ s.t

$\displaystyle d_{C}(A,B)>\sqrt{m-g(\gamma)^{2}}.$

Now letting $0\leq\theta_{1}\leq...\leq\theta_{m}\leq\pi/2$ be the principal
angles between $A$ and $B$ (see Appendix C), we have

$\displaystyle
d_{C}(H,A)=\sqrt{\sin^{2}(\theta_{1})+...+\sin^{2}(\theta_{m})}\leq\sqrt{m-1+\sin^{2}\theta_{1}}.$

Combining with the inequality above,

$\displaystyle\sqrt{m-g(\gamma)^{2}}\leq\sqrt{m-1+\sin^{2}\theta_{1}}\implies\sin^{2}(\theta_{1})>1-g(\gamma)^{2}.$

The first principal angle $\theta_{1}=\arccos a^{T}b$ where $a\in A$, $b\in B$
are unit vectors chosen s.t

$\displaystyle a^{T}b=\max_{x\in A,y\in B}\frac{x^{T}y}{\|x\|_{2}\|y\|_{2}}.$

So we have

$\displaystyle\max_{x\in A,y\in
B}\frac{x^{T}y}{\|x\|_{2}\|y\|_{2}}=a^{T}b=\cos\theta_{1}=\sqrt{1-\sin^{2}(\theta_{1})}<g(\gamma).$

Since this applies to arbitrary distinct $A,B\in\mathcal{C}$, there are
$(n+1)$ subspaces $A_{1},...,A_{n+1}\in\mathcal{C}$ of dimension $m$ s.t for
any $i\neq j$,

$\displaystyle\max_{x\in A_{i},z\in
A_{j}}\frac{x^{T}z}{\|x\|_{2}\|z\|_{2}}<g(\gamma)=2\gamma^{2}-1.$

By Lemma C.5, there exists a subspace $H$ in $\\{A_{1},...,A_{n+1}\\}$ s.t for
all $y\in\\{y_{1},...,y_{n}\\}$,

$\displaystyle\max_{w\in H}\frac{y^{T}w}{\|w\|_{2}}\leq\gamma,$

i.e. $y_{i}\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$ for
$i=1,...,n$, which concludes the proof. ∎

####  C.3.4 Proof of Lemma C.5

Recall that we consider $(n+1)$ subspaces $A_{1},...,A_{n+1}$ of dimension $m$
s.t for any $i\neq j$,

$\displaystyle\max_{x\in A_{i},z\in
A_{j}}\frac{x^{T}z}{\|x\|_{2}\|z\|_{2}}<g(\gamma)=2\gamma^{2}-1.$ (1)

Identify each $y_{i}$ to the subspace $A_{h(i)}$ that is closest to $y_{i}$ in
terms of inner product or angle, formally

$\displaystyle h(i)=\operatorname*{arg\,max}_{j}\max_{u\in
A_{j}}y_{i}^{T}u/\|u\|_{2}.$

Since there are $n$ vectors $y_{i}$, there will be at least one subspace in
$\\{A_{1},...,A_{n+1}\\}$ that is not associated to any of the $y_{i}$s. Call
this subspace H.

We show that for any $y\in\\{y_{i}\\}_{i=1}^{n}$, $\max_{w\in
H}\frac{y^{T}w}{\|w\|_{2}}\leq\gamma.$

Fix $y\in\\{y_{i}\\}_{i=1}^{n}$ and let $A$ be its corresponding subspace
$A_{h(i)}$. Let

$\displaystyle w=\text{argmax}_{w^{\prime}\in
H}\frac{y^{T}w^{\prime}}{\|w^{\prime}\|_{2}}.$ $\displaystyle
a=\text{argmax}_{a^{\prime}\in A}\frac{y^{T}a^{\prime}}{\|a^{\prime}\|_{2}}.$

Assume both $w$ and $a$ are of unit norm w.l.o.g. We know:

  * •

1\. $w^{T}y\leq a^{T}y$ from the definition of $h(i)$.

  * •

2\. $w^{T}a<g(\gamma)$ from (1).

Let $x=\frac{w+a}{\|w+a\|_{2}}$ be the average of $w$ and $a$, with
$\|w+a\|_{2}^{2}=w^{T}w+2a^{T}w+a^{T}a=2+2a^{T}w=2(1+a^{T}w)$.

Claim: $w^{T}y\leq w^{T}x$ (intuition: $y$ is “closer” to $a$ than $w$, so $w$
should be ”closer” to average of $a$ and $w$ than to $y$).

Proof of claim: Assume $w^{T}y>w^{T}x$. From 1. this implies $a^{T}y>w^{T}x$.
Now

$\displaystyle
w^{T}x=w^{T}\frac{w+a}{\|w+a\|_{2}}=\frac{w^{T}w+w^{T}a}{\|w+a\|_{2}}=\frac{1+w^{T}a}{\|w+a\|_{2}}=\frac{a^{T}a+w^{T}a}{\|w+a\|_{2}}=a^{T}x.$

So we have $a^{T}y>a^{T}x\implies a^{T}(y-x)>0$. From the initial assumption
we also have $w^{T}(y-x)>0$. Combining:

$\displaystyle(w+a)^{T}(y-x)>0$ $\displaystyle\implies x^{T}(y-x)>0$
$\displaystyle\implies x^{T}y-x^{T}x>0$ $\displaystyle\implies x^{T}y-1>0$
$\displaystyle\implies x^{T}y>1,$

which is a contradiction since both $x$ and $y$ are of unit-norm. End of proof
of claim.

We now show $w^{T}x\leq\gamma$. Using 2.,

$\displaystyle
w^{T}x=\frac{1+w^{T}a}{\|w+a\|_{2}}=\frac{\sqrt{1+a^{T}w}}{\sqrt{2}}\leq\frac{\sqrt{1+g(\gamma)}}{\sqrt{2}}=\frac{\sqrt{1+2\gamma^{2}-1}}{\sqrt{2}}=\frac{\sqrt{2\gamma^{2}}}{\sqrt{2}}=\gamma.$

Combining with the claim we have that $w^{T}y\leq\gamma$. Given the definition
of $w$ and that $y$ was arbitrary, we have shown

$\displaystyle\operatorname*{arg\,max}_{i}\max_{w\in
H}\frac{y_{i}^{T}w}{\|w\|_{2}}\leq\gamma,$

which concludes the proof. ∎

##  Appendix D Proof of Theorem 4.4

###  D.1 MDP Class

The PE problems used in the proof of Theorem 4.4 are characterised by a class
of MDPs $\mathcal{M}$ and target policies $\Pi$. In this section, we define
the class of MDPs $\mathcal{M}$. All MDPs $M\in\mathcal{M}$ in the class share
the same state-space $\mathcal{S}$, action space $\mathcal{A}$, feature map
and transition function $p$ but differ in the reward function $r_{M}$ and
target policy $\pi_{M}$. This class of MDPs is the same as the one used by
Zanette (2021) in the proof of their Theorem 1. Our constructions differ in
the set of target policies $\Pi_{M}\in\Pi$ which are defined in Appendix D.2.

  * •

State-space: $\mathcal{S}=\mathcal{B}$ and the starting state is the origin
$\bar{s}=\bm{0}\in\mathcal{B}$.

  * •

Action-space: For all $s\in\mathcal{S}$,
$\mathcal{A}_{s}=\mathcal{A}=\mathcal{B}$.

  * •

Feature-map: The feature map $\phi$ maps a state-action pair $(s,a)$ to the
action $a$, i.e. $\forall(s,a),\phi(s,a)=a$. Since $a\in\mathcal{B}$, the
feature space is the unit-hypersphere $\mathcal{B}$ and
$\|\phi(\cdot,\cdot)\|_{2}\leq 1$ holds for all inputs.

  * •

Transition-function: The successor state of a state-action pair $(s,a)$ is
deterministic and is the action $a$. This is well-defined because both the
action and state space are $\mathcal{B}$. This only depends on the chosen
action (and not the current state), so we will denote the unique successor
state when taking action $a$ by $s^{+}(a)=a$.

The MDP class $\mathcal{M}$ is known to the learner (see Section 3). Therefore
the learner knows the transition function and that all MDPs share it.
Therefore only the feedback of the reward function and target policy is useful
to the learner, as both of these are unknown. We define them in the following
section.

###  D.2 Instance of the class

Every MDP $M\in\mathcal{M}$ is fully characterised by a vector
$w\in\partial\mathcal{B}$ and a sign $+$ or $-$. Hence, they are denoted by
$M_{w,+}$ or $M_{w,-}$ and the reward function associated to either MDP will
be denoted with the same subscript. Specifically it is defined as follows:

$\displaystyle\text{on }M_{w,+}:\qquad r_{w,+}(s,a)=\begin{cases}0,&\text{if}\
a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w).\\\
+(1-\gamma)a^{T}w,&\text{otherwise}.\end{cases}$ $\displaystyle\text{on
}M_{w,-}:\qquad r_{w,-}(s,a)=\begin{cases}0,&\text{if}\
a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w).\\\
-(1-\gamma)a^{T}w,&\text{otherwise}.\end{cases}$

See Appendix B for the definition of hyper-spherical caps
$\mathcal{C}_{\gamma}(x)$. Note that the transition function is the same for
all MDPs in the class $\mathcal{M}$ and is defined in Appendix D.1. In
particular, the two MDPs $M_{w,+}$ or $M_{w,-}$ only differ in their reward
functions, which are opposite.

Target policy: The set of target policies $\Pi_{M}$ for an MDP
$M\in\mathcal{M}$ depends on the vector $w\in\partial\mathcal{B}$ that
partially characterises the MDP but not on the sign $\pm$. The set of target
policies is therefore the same for $M_{w,+}$ and $M_{w,-}$.

Fix $K>0$ and consider a sequence of $K$ nested (not necessarily strictly)
subspaces of $\mathbb{R}^{d}$:

$\displaystyle B_{K}\subset B_{K-1}\subset...\subset B_{2}\subset B_{1}\subset
B_{0}=\mathbb{R}^{d},$

s.t $\dim B_{K}>0$ and $w\in B_{K}$. Set $B_{K+1}=\langle w\rangle$. Let
$H_{w}=\\{B_{1},...,B_{K},B_{K+1}\\}$ denote the set of nested subspaces
(including $\langle w\rangle$). This is not defined as an ordered set, but for
notational purposes the order can always be recovered since the sequence must
be nested. If $A$ is a subspace of $\mathbb{R}^{d}$, let $\text{proj}_{A}(x)$
denote the orthogonal projection of $x$ onto $A$. See Appendix B for the
definition of hyper-spherical caps $\mathcal{C}_{\gamma}(w)$ and sectors
$\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$. A target policy $\pi_{H_{w}}$
is specified by the set of nested subspaces $H_{w}$ and is defined as:

$\displaystyle\pi_{H_{w}}(s)=\begin{cases}\frac{1}{\gamma}\text{proj}_{B_{k+1}}(s),&\text{if}\
s\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})\text{
for }k=0,...,K.\\\ \frac{1}{\gamma}\text{proj}_{B_{K+1}}(s),&\text{if}\
s\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\bigcup\mathcal{C}_{\gamma}(-w)).\\\
s,&\text{if}\
s\in\mathcal{C}_{\gamma}(w)\bigcup\mathcal{C}_{\gamma}(-w).\end{cases}$

The target policy is defined for all $s\in\mathcal{S}=\mathcal{B}$:

$\displaystyle\Big{[}\bigcup_{k=0}^{K}\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})\Big{]}\bigcup\Big{[}\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\bigcup\mathcal{C}_{\gamma}(-w))\Big{]}\bigcup\Big{[}\mathcal{C}_{\gamma}(w)\bigcup\mathcal{C}_{\gamma}(-w)\Big{]}$
$\displaystyle=\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{0})$
$\displaystyle=B_{0}$ $\displaystyle=\mathcal{B}.$

and the pair-wise intersections are all empty (so they form a partition). The
actions taken are also well-defined:

  * •

For $k=0,...,K$, if
$s\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$,
then $s\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$ and from
Definition B.2, this means that for any $u\in B_{k+1}$,
$|u^{T}s|/\|u\|_{2}\|s\|_{2}\leq\gamma$. Denoting
$x=\text{proj}_{B_{k+1}}(s)\in B_{k+1}$,

$\displaystyle\|x\|_{2}=\frac{x^{T}x}{\|x\|_{2}}=\frac{|x^{T}s|}{\|x\|_{2}}\leq\gamma\|s\|_{2}\leq\gamma,$

meaning that $\frac{1}{\gamma}\text{proj}_{B_{k+1}}(s)\in\mathcal{B}$.

  * •

If
$s\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$,
, then $s\notin(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$ and from
Definition B.1, this means that $|w^{T}s|\leq\gamma$. Denoting
$x=\text{proj}_{B_{K+1}}(s)\in B_{K+1}$,

$\displaystyle\|x\|_{2}=\frac{x^{T}x}{\|x\|_{2}}=\frac{|x^{T}s|}{\|x\|_{2}}\leq\gamma,$

meaning that $\frac{1}{\gamma}\text{proj}_{B_{K+1}}(s)\in\mathcal{B}$.

The set of target policies $\Pi_{M_{w,\pm}}$ for the MDP $M_{w,\pm}$ is the
set of (deterministic) policies $\pi_{H_{w}}$ for any sequence of nested
subspaces $H_{w}$ satisfying the above conditions ($w\in B_{K}$). We sometimes
use a ${{w,\pm}}$ subscript to refer to both MDPs simultaneously.

Crucially observing actions in
$\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
for $k\leq K$ may not reveal $w$. Without the knowledge of $w$, the reward
function is unknown and even with the knowledge of $w$ or the target policy
the reward function is not fully identified, in which case $M_{w,+}$ and
$M_{w,-}$ cannot be distinguished.

###  D.3 Realizability:

We show that the action-value of any target policy for any MDP
$M\in\mathcal{M}$ can be linearly represented with the feature map defined in
Appendix D.1. The action-value of a target policy $\pi_{H_{w}}$ only depends
on $w$ and the sign $\pm$ of the reward function of the MDP, the sequence of
nested subspace does not matter beyond $w$.

######  Lemma D.1 ($Q^{\pi}$ Realizability).

For any $w\in\partial\mathcal{B}$ let $Q_{w,+}$ and $Q_{w,-}$ be the action-
value functions of any $\pi\in\Pi_{M_{w,\pm}}$ (a target policy) on $M_{w,+}$
and $M_{w,-}$, respectively. Then it holds that

$\displaystyle\forall(s,a),\qquad\begin{cases}Q_{w,+}(s,a)=+\phi(s,a)^{T}w&\text{
on }M_{w,+}.\\\ Q_{w,-}(s,a)=-\phi(s,a)^{T}w&\text{ on }M_{w,-}.\\\
\end{cases}$

Proof: Consider $M_{w,+}$ and set $Q(s,a)=\phi(s,a)^{T}w$. We will show that
$Q$ satisfies the Bellman evaluation equations for $\pi$ at all state-actions
pairs, which will imply that $Q(s,a)=Q_{w,+}(s,a)$. Apply
$\mathcal{T}^{\pi}_{M_{w,+}}$ to $Q$ at $(s,a)$:

$\displaystyle\mathcal{T}^{\pi}_{M_{w,+}}(Q)(s,a)$
$\displaystyle=r_{w,+}(s,a)+\gamma Q(s^{+}(a),\pi(s^{+}(a)))$
$\displaystyle=r_{w,+}(s,a)+\gamma Q(a,\pi(a)),$

since $s^{+}(a)=a$ is the successor state of $(s,a)$. We consider the RHS of
the above for all possible cases.

Case 1: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
for some $k\in[0,...,K]$:

$\displaystyle r_{w,+}(s,a)+\gamma Q(a,\pi(a))$ $\displaystyle=0+\gamma
Q(a,\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a))$
$\displaystyle=\gamma\phi(a,\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a))^{T}w$
$\displaystyle=\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{k+1}}(a)w$
$\displaystyle=\text{proj}^{T}_{B_{k+1}}(a)w.$

However, recall that $w\in B_{k+1}$. Since $\text{proj}_{B_{k+1}}(a)$ is the
orthogonal projection of $a$: $w^{T}\text{proj}_{B_{k+1}}(a)=w^{T}a$. Plugging
into the above, we have: $r_{w,+}(s,a)+\gamma
Q(a,\pi(a))=a^{T}w=\phi(s,a)^{T}w=Q(s,a)$, which satisfies the Bellman
evaluation equation.

Case 2: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$,
as above (recalling $B_{K+1}=\langle w\rangle$) :

$\displaystyle r_{w,+}(s,a)+\gamma Q(a,\pi(a))$ $\displaystyle=0+\gamma
Q(a,\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a))$
$\displaystyle=\gamma\phi(a,\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a))^{T}w$
$\displaystyle=\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=(w^{T}a)w^{T}w=w^{T}a=\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

Case 3: If $a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$, the
reward is no longer 0 and we have:

$\displaystyle r_{w,+}(s,a)+\gamma Q(a,\pi(a))$
$\displaystyle=(1-\gamma)a^{T}w+\gamma Q(a,a)$
$\displaystyle=(1-\gamma)a^{T}w+\gamma\phi(a,a)^{T}w$
$\displaystyle=(1-\gamma)a^{T}w+\gamma a^{T}w$
$\displaystyle=a^{T}w=\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

For all cases, $Q$ satisfies the Bellman evaluation equations, so it is the
fixed point of the Bellman evaluation operator. In particular, it is the
action-value of the target policy $\pi$ on $M_{w,+}$.

Now consider $M_{w,-}$ and set $Q(s,a)=-\phi(s,a)^{T}w$. We will show that $Q$
satisfies the Bellman evaluation equations for $\pi$ at all state-actions
pairs, which will imply that $Q(s,a)=Q_{w,-}(s,a)$. As above, apply
$\mathcal{T}^{\pi}_{M_{w,-}}$ at $(s,a)$ to $Q$:

$\displaystyle\mathcal{T}^{\pi}_{M_{w,-}}(Q)(s,a)$
$\displaystyle=r_{w,-}(s,a)+\gamma Q(a,\pi(a)),$

and consider the RHS of the above for all possible cases.

Case 1: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
for some $k\in[0,...,K]$:

$\displaystyle r_{w,-}(s,a)+\gamma Q(a,\pi(a))$ $\displaystyle=0+\gamma
Q(a,\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a))$
$\displaystyle=-\gamma\phi(a,\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a))^{T}w$
$\displaystyle=-\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{k+1}}(a)w$
$\displaystyle=-\text{proj}^{T}_{B_{k+1}}(a)w$
$\displaystyle=-a^{T}w=-\phi(s,a)^{T}w=Q(s,a).$

Case 2: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$,
as above:

$\displaystyle r_{w,-}(s,a)+\gamma Q(a,\pi(a))$ $\displaystyle=0+\gamma
Q(a,\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a))$
$\displaystyle=-\gamma\phi(a,\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a))^{T}w$
$\displaystyle=-\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=-\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=-(w^{T}a)w^{T}w=-w^{T}a=-\phi(s,a)^{T}w=Q(s,a).$

Case 3: If $a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$, the
reward is no longer 0 and we have:

$\displaystyle r_{w,-}(s,a)+\gamma Q(a,\pi(a))$
$\displaystyle=-(1-\gamma)a^{T}w+\gamma Q(a,a)$
$\displaystyle=-(1-\gamma)a^{T}w-\gamma\phi(a,a)^{T}w$
$\displaystyle=-(1-\gamma)a^{T}w-\gamma a^{T}w$
$\displaystyle=-a^{T}w=-\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

For all cases, $Q$ satisfies the Bellman evaluation equations, so it is the
fixed point of the Bellman evaluation operator. In particular, it is the
action-value of the target policy $\pi$ on $M_{w,-}$. ∎

###  D.4 Proof of Theorem 4.4

Consider the MDP class described in Appendix D.1 and Appendix D.2. First, we
know from Lemma D.1 ($Q^{\pi}$ Realizability) that all instances of the PE
problem characterised by the MDP class $\mathcal{M}$ and target policies $\Pi$
satisfy Assumption 4.1 ($Q^{\pi}$ is Realizable) with the feature map
$\phi(\cdot,\cdot)$ defined in Appendix D.1.

The dynamics of the MDPs in the class $\mathcal{M}$ are the same, which as
discussed in Remark 3.6 means that policy-induced and policy-free queries are
equivalent. We provide a proof for policy-free queries.

We specify the instance with MDP $M\in\mathcal{M}$ and target policy
$\pi_{M}\in\Pi_{M}$ according to the queries selected by the learner. Fix
$K>0$. Recall that $n_{k}$ is the number of queries made by the learner at
round $k$ and $n=\sum_{k=1}^{K}n_{k}$ is the total number of queries. Let
$A_{k}$ be the set of actions queried by the learner at round k (i.e.
$|A_{k}|=n_{k}$). Set $\widebar{A}_{k}=\bigcup_{i=1}^{k}A_{k}$ to be the set
of all actions queried up to round $k$.

The learner is sample-efficient so $n$ is polynomial in $d$. Specifically,
there exists some constant $\alpha>0$ and some integer $T$ such that
$n\leq\alpha d^{T}$. Consider $N\in\mathbb{N}$ s.t $2^{N}\leq d<2^{N+1}$ and
set $d_{+}=2^{N}$. Note that $d_{+}\geq d/2$. Fix
$W=exp(\frac{1}{8}g(\gamma)d_{+}^{1/4^{K}})$. If $n\leq W$, we can show the
learner cannot solve the PE problem. Consider both cases:

####  D.4.1 Case 1

Suppose $W<n$, then

$\displaystyle W<n$ $\displaystyle\implies W<\alpha d^{T}$
$\displaystyle\implies\frac{g(\gamma)}{8}d_{+}^{1/4^{K}}<\log(\alpha d^{T})$
$\displaystyle\implies\frac{g(\gamma)}{8}(d/2)^{1/4^{K}}<\log(\alpha
d^{T})\qquad\text{ using that }d_{+}\geq\frac{d}{2}$
$\displaystyle\implies(d/2)^{1/4^{K}}<\frac{8}{g(\gamma)}\log(\alpha d^{T})$
$\displaystyle\implies\frac{1}{4^{K}}\log(d/2)<\log\Big{(}\frac{8}{g(\gamma)}\log(\alpha
d^{T})\Big{)}$
$\displaystyle\implies\frac{\log(d/2)}{\log\Big{(}\frac{8}{g(\gamma)}\log(\alpha
d^{T})\Big{)}}<4^{K}$ $\displaystyle\implies\frac{1}{\log
4}\log\Big{[}\frac{\log(d/2)}{\log\Big{(}\frac{8}{g(\gamma)}\log(\alpha
d^{T})\Big{)}}\Big{]}<K$ $\displaystyle\implies K\geq c^{\prime}\log\log
d\qquad\text{ for a constant $c^{\prime}>0$ and $d$ sufficiently large.}$

####  D.4.2 Case 2

$n\leq W\implies n_{k}\leq\exp(\frac{1}{8}g(\gamma)d_{+}^{1/4^{k}})$ for
$k=1,...,K$. We inductively define the sequence of nested subspaces
$B_{K}\subset...\subset B_{1}$ characterising $w$ ($\in B_{K}$) and used by
the target policy $\pi_{M}$ s.t for $k=1,...,K$, $\dim B_{k}=2^{\lceil
N/4^{k}\rceil}\geq 2^{8}$ and

$\displaystyle\forall a\in\widebar{A}_{k},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k}).$

Proof of existence of nested subspaces:

We proceed by induction. Let $B_{K}\subset...\subset B_{1}$ be an arbitrary
sequence of subspaces and $w\in B_{K}\cap\mathcal{B}$ arbitrary. We will
define these but for now consider the target policy $\pi_{H_{w}}$ (see
Appendix D.2) with $H_{w}=\\{\langle w\rangle,B_{K},...,B_{1}\\}$.

Base Case: At round $k=1$, the learner has observed no feedback and chooses a
set of action queries $A_{1}=\widebar{A}_{1}$ (we ignore the queried states
since the reward and transitions functions only depend on the action) such
that:

$\displaystyle|A_{1}|=n_{1}\leq\exp(\frac{1}{8}g(\gamma)d_{+}^{1/4})\leq\Big{(}\frac{d_{+}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{+}^{1/4}}-1\qquad\text{
(if $d_{+}\geq 12$) },$

so by Lemma C.3 there exists a subspace $H\in\mathcal{G}_{2^{\lceil
N/4\rceil},d_{+}}(\mathbb{R})$ of dimension $2^{\lceil N/4\rceil}$ ($\geq
d_{+}^{1/4}$) such that

$\displaystyle\forall x\in A_{1}=\widebar{A}_{1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H).$

Set $B_{1}=H$. The learner then observes the feedback for $A_{1}$ (The state
$s$ in the reward does not matter):

$\displaystyle\\{(r_{w,\pm}(s,a),\pi_{H_{w}}(s^{+}(a))):a\in A_{1}\\}.$

Not having fixed $B_{2},...,B_{K},w$ does not cause problems with the feedback
even though $\pi_{H_{w}}$ and $r_{w,\pm}$ depend on them since the feedback of
$A_{1}$ only depends on $B_{1}$: the learner only observes the projection of
the actions in $A_{1}$ into $B_{1}$,

$\displaystyle\forall a\in\widebar{A}_{1},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{1})$
$\displaystyle\implies$ $\displaystyle\forall
a\in\widebar{A}_{1},\qquad\pi_{H_{w}}(s^{+}(a))=\pi_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{1}}(a),\qquad
r_{w,\pm}(s,a)=0.$

In particular, there is no dependence on $w$ or $B_{1+i}\subset B_{1}$ for
$i\geq 1$, which can be arbitrary and fixed in later rounds.

Inductive Step: Suppose that at round $k$, there exists a sequence of nested
subspaces $B_{k}\subset...\subset B_{1}$ used by the target policy
$\pi_{H_{w}}$ s.t for $i=1,...,k$, $\dim B_{i}=2^{\lceil N/4^{i}\rceil}\geq
2^{8}$ and

$\displaystyle\forall a\in\widebar{A}_{i},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{i}).$

$B_{k+1}$ need not be fixed yet since the feedback of $\widebar{A}_{k}$ only
depends on $B_{1},...,B_{k}$:

$\displaystyle\forall a\in{A}_{k},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})$
$\displaystyle\implies$ $\displaystyle\forall
a\in{A}_{k},\qquad\pi_{H_{w}}(s^{+}(a))=\pi_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{j}}(a)\qquad\text{
for some }j\leq k,\qquad r_{w,\pm}(s,a)=0.$

The learner only observes the projection of actions in $\widebar{A}_{k}$ into
$B_{1},B_{2},...,B_{k}$. Note that the only constraint on $M$ up to this step
is $w\in B_{k}$.

Now $B_{k}$ is such that $\forall x\in\widebar{A}_{k}$,
$x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})$ with $d_{k}=\dim
B_{k}=2^{\lceil N/4^{k}\rceil}\geq d^{1/4^{k}}_{+}\geq 2^{8}$. The learner has
observed the feedback from $\widebar{A}_{k}$ and chooses a set of action
queries $A_{k+1}$ such that

$\displaystyle|A_{k+1}|=n_{k+1}\leq\exp(\frac{1}{8}g(\gamma)d_{+}^{1/4^{k+1}})\leq\Big{(}\frac{d_{k}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{+}^{1/4^{k+1}}}-1\leq\Big{(}\frac{d_{k}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{k}^{1/4}}-1\qquad\text{
(if $d_{+}\geq 12$) }.$

Then we know that the number of those queries that are in $B_{k}$ is also less
than $\Big{(}\frac{d_{k}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{k}^{1/4}}$.
Therefore by Lemma C.3, there exists a subspace $H\subset B_{k}$ of dimension
$2^{\lceil\lceil N/4^{k}\rceil/4\rceil}\geq d_{k+1}=2^{\lceil
N/4^{k+1}\rceil}$ (can reduce the dimension if they do not match, removing
dimensions will not add queries to
$\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$) such that

$\displaystyle\forall x\in{A}_{k+1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H).$

In particular, $A_{k+1}$ can be entirely contained in $B_{k}$ or can depend on
$B_{k},...,B_{1}$ in any arbitrary way. Set $B_{k+1}=H$. We know that $\forall
x\in\widebar{A}_{k},x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})$
and $B_{k+1}\subset B_{k}$ so we have

$\displaystyle\forall x\in\widebar{A}_{k+1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1}).$

The learner then observes the feedback for $A_{k+1}$ (The state $s$ in the
reward does not matter):

$\displaystyle\\{(r_{w,\pm}(s,a),\pi_{H_{w}}(s^{+}(a))):a\in A_{k+1}\\}.$

Not having fixed $B_{k+2},...,B_{K},w$ does not cause problems with the
feedback even though $\pi_{H_{w}}$ and $r_{w,\pm}$ depend on them since the
feedback observed up to this round of $\widebar{A}_{k+1}$ only depends on
$B_{1},...,B_{k+1}$: the learner only observes the projection of the actions
in $\widebar{A}_{k+1}$ into $B_{1},...,B_{k+1}$,

$\displaystyle\forall a\in\widebar{A}_{k+1},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
$\displaystyle\implies$ $\displaystyle\forall
a\in\widebar{A}_{k+1},\qquad\pi_{H_{w}}(s^{+}(a))=\pi_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{j}}(a)\qquad\text{
for some }j\leq k+1,\qquad r_{w,\pm}(s,a)=0.$

In particular, there is no dependence on $w$ or $B_{k+1+i}\subset B_{k+1}$ for
$i\geq 1$, which can be arbitrary and fixed in later rounds.

We remark Lemma C.3 establishes the existence of a subspace in
$\mathcal{G}_{2^{\lceil\lceil N/4^{k}\rceil/4\rceil},d_{k}}(\mathbb{R})$ where
the ambient space is $\mathbb{R}^{d_{k}}$ instead of $\mathbb{R}^{d}$. Any
$d_{k}$-dimensional subspace of $\mathbb{R}^{d}$ is isomorphic to
$\mathbb{R}^{d_{k}}$, so we can consider $B_{k}$, project the points of
$A_{k+1}$ into $B_{k}$, apply Lemma C.3 to get $H$ within $B_{k}$, and extend
$H$ to be defined in $\mathbb{R}^{d}$. We omit these steps here for clarity
but detail them fully in Appendix D.4.3. This also holds for the base case
(where $d_{+}$ is used as the ambient dimension instead of $d$)

When applying Lemma C.3 with ambient dimension $d_{k}=2^{\lceil
N/4^{k}\rceil}$, we require $\lceil N/4^{k}\rceil\geq 8$. Since $d_{k}\geq
d_{+}^{1/4^{k}}$ and $d_{+}\geq d/2$, it is enough to have

$\displaystyle(d/2)^{1/4^{k}}\geq 2^{8}$ $\displaystyle\iff K\leq\frac{1}{\log
4}\log\Big{(}\frac{1}{8\log 2}\log\frac{d}{2}\Big{)}$ $\displaystyle\impliedby
K\leq c\log\log d,$

for a constant $c>0$ and $d$ sufficiently large. If this condition on $K$ does
not hold, then

$\displaystyle K>c\log\log d.$ (2)

Suppose it does hold. Then the steps above go through and we have the
existence of our nested subspaces. We also have $d_{k}\geq 2^{8}>12$ for all
$k=1,...,K$, which was needed in some of the steps.

End of proof of existence of nested subspaces.

We now fully specify $M$. The complete set of queried actions by the learner
is $\widebar{A}_{K}$, and

$\displaystyle\forall a\in\widebar{A}_{K},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K}).$

Since $\dim B_{K}\geq 2^{8}>0$, we can pick some $w\in
B_{K}\cap\partial\mathcal{B}$ and let $H_{w}=\\{B_{1},...,B_{K},B_{K+1}\\}$
with $B_{K+1}=\langle w\rangle$. From the proof of the existence of nested
spaces, we can consider the PE problem instances with MDPs $M_{w,+}$ and
$M_{w,-}$ and $\pi_{H_{w}}$ as target policy. The transition function and
target policy are the same on $M_{w,+}$ and $M_{w,-}$. Since $\forall
a\in\widebar{A}_{K}$,
$a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ because
$a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K})$, the reward function
for any query $a\in\widebar{A}_{K}$ is $0$. Thus, the learner cannot
distinguish $M_{w,+}$ between $M_{w,-}$ from the submitted queries.

The learner has to produce an estimate of $Q^{\pi_{H_{w}}}(\bar{s},\cdot)$ for
$\bar{s}=\bm{0}$. But from Lemma D.1,

$\displaystyle
Q^{\pi_{H_{w}}}(\bar{s},w)=\phi(\bar{s},w)^{T}w=w^{T}w=1\quad\quad\quad\text{
on }M_{w,+}.$ $\displaystyle
Q^{\pi_{H_{w}}}(\bar{s},w)=-\phi(\bar{s},w)^{T}w=-w^{T}w=-1\quad\text{ on
}M_{w,-}.$

If the learner predicts a positive value for $Q^{\pi_{H_{w}}}(\bar{s},w)$, it
will incur an error greater than $1$ on $M_{w,-}$ and similarly for $M_{w,+}$
if it predicts a negative value. Even if it randomizes between both, with
probability at least $1/2$ it will incur an error of at least $1$ on one of
the MDPs. Therefore, the learner can be at most $(1,1/2)$-sound.

Therefore, to be more than $(1,1/2)$-sound, we must either be in Case 1 or be
in Case 2 and satisfy condition (2). In either case, we have the condition

$\displaystyle K>c\log\log d,$

for some constant $c>0$ and $d$ sufficiently large, which gives
$K=\Omega(\log\log d)$, showing the result. ∎

####  D.4.3 Dealing with switches in ambient space

In this section we write out the missing details of the proof of Theorem 4.4
in Appendix D.4. In particular, assuming the condition on $n_{k+1}$ is
satisfied, we show that we can use Lemma C.3 for the existence of a subspace
$H\subset B_{k}\subset\mathbb{R}^{d}$ of dimension $d_{k+1}$ s.t

$\displaystyle\forall x\in{A}_{k+1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H).$ (3)

Fix $k\in\\{0,1,...,K-1\\}$ and set $d_{0}=d_{+}$ and $B_{0}$ to any
$d_{+}$-dimensional subspace of $\mathbb{R}^{d}$. Picking up the proof of in
Appendix D.4, the condition on $n_{k+1}=|A_{k+1}|$ for Lemma C.3 is satisfied.
$B_{k}\in\mathcal{G}_{d_{k},d}(\mathbb{R})$ is a $d_{k}$-dimensional subspace
within $\mathbb{R}^{d}$. We find an orthonormal basis for $B_{k}$:

$\displaystyle\exists v_{1},...,v_{d_{k}}\in\mathbb{R}^{d}\text{ s.t.
}B_{k}=\langle v_{1},...,v_{d_{k}}\rangle\text{ and
}v_{i}^{T}v_{i}=1,v_{i}^{T}v_{j}=0\text{ for }i\neq j.$

Any vector in $B_{k}$ can be written as $\sum_{m=1}^{d_{k}}\alpha_{m}v_{m}$
for some $(\alpha_{m})_{m=1}^{d_{k}}$. $B_{k}$ is isomorphic to
$\mathbb{R}^{d_{k}}$ through the linear transformation
$T:B_{k}\rightarrow\mathbb{R}^{d_{k}}$ (which can be shown to be a bijection)
defined as

$\displaystyle
T(\sum_{m=1}^{d_{k}}\alpha_{m}v_{m})=[\alpha_{1},...,\alpha_{d_{k}}]^{T}\in\mathbb{R}^{d_{k}}.$

Letting $proj_{B_{k}}(x)$ denote the orthogonal projection of
$x\in\mathbb{R}^{d}$ onto $B_{k}$, consider

$\displaystyle A_{k+1}^{p}=\\{T(proj_{B_{k}}(x)):x\in
A_{k+1}\\}\subset\mathbb{R}^{d_{k}}.$

The size of $A_{k+1}^{p}$ is $|A_{k+1}^{p}|\leq|A_{k+1}|=n_{k+1}$ so we can
apply Lemma C.3: there exists a subspace
$H^{p}\in\mathcal{G}_{d_{k+1},d_{k}}(\mathbb{R})$ s.t

$\displaystyle\forall x^{p}\in{A}^{p}_{k+1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H^{p}).$

Recall $d_{k}=2^{\lceil N/4^{k}\rceil}$ and the lemma gives a subspace of
dimension $2^{\lceil\lceil N/4^{k}\rceil/4\rceil}\geq d_{k+1}=2^{\lceil
N/4^{k+1}\rceil}$ but we can reduce the dimension if they do not match.

$H^{p}\in\mathcal{G}_{d_{k+1},d_{k}}(\mathbb{R})$ is a $d_{k+1}$-dimensional
subspace within $\mathbb{R}^{d_{k}}$. We find an orthonormal basis for
$H^{p}$:

$\displaystyle\exists u_{1}^{p},...,u_{d_{k+1}^{p}}\in\mathbb{R}^{d_{k}}\text{
s.t. }H^{p}=\langle u_{1}^{p},...,u^{p}_{d_{k+1}}\rangle\text{ and
}(u^{p}_{i})^{T}u^{p}_{i}=1,(u^{p}_{i})^{T}u^{p}_{j}=0\text{ for }i\neq j.$

Define

$\displaystyle H=\langle
T^{-1}(u_{1}^{p}),...,T^{-1}(u_{d_{k+1}}^{p})\rangle.$

Remark that $T^{-1}(u_{i}^{p})=\sum_{m=1}^{d_{k}}u_{i}^{p}(m)v_{m}\in
B_{k}\subset\mathbb{R}^{d}$ so $H\subset B_{k}$. We use the notation $x(m)$
for a vector $x$ to refer to the $m$-th coordinate of $x$. Since
$\\{v_{1},...,v_{d_{k}}\\}$ is an orthonormal set:

$\displaystyle(T^{-1}(u_{i}^{p}))^{T}T^{-1}(u_{j}^{p})=\sum_{m=1}^{d_{k}}u_{i}^{p}(m)u_{j}^{p}(m)=(u_{i}^{p})^{T}u_{j}^{p}=\begin{cases}1,&\text{if}\
i=j.\\\ 0,&\text{if}\ i\neq j.\end{cases}$

So $\\{T^{-1}(u_{1}^{p}),...,T^{-1}(u_{d_{k+1}}^{p})\\}$ is an orthonormal
basis for $H$, which means $H\in\mathcal{G}_{d_{k+1},d}(\mathbb{R})$ is a
$d_{k+1}$ dimensional subspace within $\mathbb{R}^{d}$. $H$ is the subspace we
are trying to show the existence of, it remains to verify the condition (3).
The following claim concludes this section.

Claim: $\forall
x\in{A}_{k+1},x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$.

Proof of Claim: Suppose not: $\exists x\in{A}_{k+1}$ s.t.
$x\in\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$. Then there exists a unit-
normed $h\in H\subset B_{k}$ such that $x^{T}h>\gamma$. Since $h\in B_{k}$, we
also have $proj_{B_{k}}(x)^{T}h>\gamma$. $h,proj_{B_{k}}(x)$ are both in
$B_{k}$ so

$\displaystyle\exists\alpha_{1},...,\alpha_{d_{k}}\in\mathbb{R}\text{ s.t.
}h=\sum_{m=1}^{d_{k}}\alpha_{m}v_{m},$
$\displaystyle\exists\beta_{1},...,\beta_{d_{k}}\in\mathbb{R}\text{ s.t.
}proj_{B_{k}}(x)=\sum_{m=1}^{d_{k}}\beta_{m}v_{m}.$

and we have

$\displaystyle proj_{B_{k}}(x)^{T}h>\gamma$
$\displaystyle\implies\sum_{m=1}^{d_{k}}\alpha_{m}\beta_{m}>\gamma$
$\displaystyle\implies T(proj_{B_{k}}(x))^{T}T(h)>\gamma$
$\displaystyle\implies
T(proj_{B_{k}}(x))\in\overset{\triangle}{\mathcal{C}}_{\gamma}(H^{p}),$

since $T(h)\in H^{p}$ as $h\in H$. But $T(proj_{B_{k}}(x))\in A_{k+1}^{p}$,
which contradicts the definition of $H^{p}$. ∎

##  Appendix E Proof of Theorem 4.5

###  E.1 MDP Class

The BPI and PE problems used in the proof of Theorem 4.5 are characterised by
a class of MDPs $\mathcal{M}$ and target policies $\Pi$. In this section, we
define the class of MDPs $\mathcal{M}$. All MDPs $M\in\mathcal{M}$ in the
class share the same state-space $\mathcal{S}$, action space $\mathcal{A}$,
feature map and target policy $\pi$ (for the PE problem) but differ in the
transition function $p_{M}$ and reward function $r_{M}$. This class of MDPs is
similar to the one used by Zanette (2021) in the proof of their Theorem 3. Our
construction differs in the transition functions which are defined in Appendix
E.2.

  * •

State-space: $\mathcal{S}=\\{\bar{s}\\}\bigcup\mathcal{B}$ where $\bar{s}$ is
the starting state disjoint from $\mathcal{B}$ (i.e.
$\\{\bar{s}\\}\cap\mathcal{B}=\emptyset$).

  * •

Action-space: Each state has a single action (which we denote by the state
itself for convenience) other than the starting state $\bar{s}$ which can take
actions in $\mathcal{B}$. Formally:

$\displaystyle\mathcal{A}(s)=\begin{cases}\mathcal{B}&\text{ if }s=\bar{s}.\\\
\\{s\\}&\text{ if }s\in\mathcal{B}.\end{cases}$

This notation enables that $\forall
s\in\mathcal{S},\mathcal{A}(s)\subset\mathcal{B}$.

  * •

Feature-map: The feature map $\phi$ maps a state-action pair $(s,a)$ to the
action $a$, i.e. $\forall(s,a),\phi(s,a)=a$. Since $a\in\mathcal{B}$, the
feature space is the unit-hypersphere $\mathcal{B}$ and
$\|\phi(\cdot,\cdot)\|_{2}\leq 1$ holds for all inputs.

  * •

Target policy: For the PE problem, the target policy $\pi$ is the same for all
MDPs in the class: it takes action $\bm{0}$ in the starting state $\bar{s}$
and in the other states, there is a single action. In particular
$\Pi_{M}=\\{\pi\\}$ for all $M\in\mathcal{M}$.

###  E.2 Instance of the class

Fix $K>0$ and consider a sequence of $K$ nested subspaces of $\mathbb{R}^{d}$:

$\displaystyle B_{K}\subset B_{K-1}\subset...\subset B_{2}\subset B_{1}\subset
B_{0}=\mathbb{R}^{d}.$

s.t $\dim B_{K}>0$ and fix some $w\in B_{K}\cap\partial\mathcal{B}$. Set
$B_{K+1}=\langle w\rangle$. Let $H_{w}=\\{B_{1},...,B_{K},B_{K+1}\\}$ denote
the set of nested subspaces (including $\langle w\rangle$). This is not
defined as an ordered set, but for notational purposes the order can always be
recovered since the sequence must be nested.

Every MDP $M\in\mathcal{M}$ is fully characterised by the sequence of nested
subspaces $H_{w}$ and a sign $+$ or $-$. Hence, they are denoted by
$M_{H_{w},+}$ or $M_{H_{w},-}$.

Reward function: The reward function only depends on the vector $w$ and the
sign $\pm$ but we denote them with the same subscript as the MDP. Specifically
it is defined as follows:

$\displaystyle\text{on }M_{H_{w},+}:\qquad
r_{H_{w},+}(s,a)=\begin{cases}0,&\text{if}\
a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w).\\\
+(1-\gamma)a^{T}w,&\text{otherwise}.\end{cases}$ $\displaystyle\text{on
}M_{H_{w},-}:\qquad r_{H_{w},-}(s,a)=\begin{cases}0,&\text{if}\
a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w).\\\
-(1-\gamma)a^{T}w,&\text{otherwise}.\end{cases}$

See Appendix B for the definition of hyper-spherical caps
$\mathcal{C}_{\gamma}(w)$. We sometimes use a ${{w,\pm}}$ subscript to refer
to both MDPs simultaneously.

Transition Function: The transition function for an MDP $M\in\mathcal{M}$
depends on the sequence of nested subspaces $H_{w}$ but not on the sign $\pm$.
The transition function is therefore the same for $M_{H_{w},+}$ and
$M_{H_{w},-}$. If $A$ is a subspace of $\mathbb{R}^{d}$, let
$\text{proj}_{A}(x)$ denote the orthogonal projection of $x$ onto $A$. See
Appendix B for the definition of hyper-spherical caps
$\mathcal{C}_{\gamma}(w)$ and sectors
$\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$. The successor state of a
state-action pair $(s,a)$ is deterministic and only depends on the chosen
action (and not the current state), so we will denote the unique successor
state when taking action $a$ by $s^{+}_{H_{w}}(a)=a$, which is defined as:

$\displaystyle
s^{+}_{H_{w}}(a)=\begin{cases}\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a),&\text{if}\
a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})\text{
for }k=0,...,K.\\\ \frac{1}{\gamma}\text{proj}_{B_{K+1}}(a),&\text{if}\
a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)).\\\
a,&\text{if}\
a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w).\end{cases}$

The transition function is defined for all
$a\in\mathcal{A}=\bigcup_{s\in\mathcal{S}}\mathcal{A}_{s}=\mathcal{B}$:

$\displaystyle\Big{[}\bigcup_{k=0}^{K}\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})\Big{]}\bigcup\Big{[}\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\bigcup\mathcal{C}_{\gamma}(-w))\Big{]}\bigcup\Big{[}\mathcal{C}_{\gamma}(w)\bigcup\mathcal{C}_{\gamma}(-w)\Big{]}$
$\displaystyle=\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{0})$
$\displaystyle=B_{0}$ $\displaystyle=\mathcal{B}.$

and the pair-wise intersections are all empty (so they form a partition). The
successor states are also well-defined:

  * •

For $k=0,...,K$, if
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$,
then $a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$ and from
Definition B.2, this means that for any $u\in B_{k+1}$,
$|u^{T}s|/\|u\|_{2}\|s\|_{2}\leq\gamma$. Denoting
$x=\text{proj}_{B_{k+1}}(a)\in B_{k+1}$,

$\displaystyle\|x\|_{2}=\frac{x^{T}x}{\|x\|_{2}}=\frac{|x^{T}a|}{\|x\|_{2}}\leq\gamma\|a\|_{2}\leq\gamma,$

meaning that $\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a)\in\mathcal{B}$.

  * •

If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$,
, then $a\notin(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$ and from
Definition B.1, this means that $|w^{T}s|\leq\gamma$. Denoting
$x=\text{proj}_{B_{K+1}}(a)\in B_{K+1}$,

$\displaystyle\|x\|_{2}=\frac{x^{T}x}{\|x\|_{2}}=\frac{|x^{T}a|}{\|x\|_{2}}\leq\gamma,$

meaning that $\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a)\in\mathcal{B}$.

Note that the starting state $\bar{s}$ is not a successor state so a policy
trajectory can never return to $\bar{s}$.

Crucially actions queried in
$\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
for $k\leq K$ may not reveal $w$. Without the knowledge of $w$, the reward
function is unknown and even with the knowledge of $w$ the reward function is
not fully identified, in which case $M_{H_{w},+}$ and $M_{H_{w},-}$ cannot be
distinguished.

###  E.3 Realizability

We show that the action-value of any policy (not just the target policy) for
any MDP $M\in\mathcal{M}$ can be linearly represented with the feature map
defined in Appendix E.1. The action-value of a policy $\pi$ only depends on
$w$ and the sign $\pm$ of the reward function of the MDP, the sequence of
nested subspace does not matter beyond $w$.

######  Lemma E.1 (Realizability).

For any $w\in\partial\mathcal{B}$ and sequence of nested subspaces $H_{w}$
satisfying the construction from Appendix E.2, let $Q^{\pi}_{H_{w},+}$ and
$Q^{\pi}_{H_{w},-}$ be the action-value functions of an arbitrary policy $\pi$
on $M_{H_{w},+}$ and $M_{H_{w},-}$, respectively. Then it holds that

$\displaystyle\forall(s,a),\qquad\begin{cases}Q^{\pi}_{H_{w},+}(s,a)=+\phi(s,a)^{T}w&\text{
on }M_{H_{w},+}.\\\ Q^{\pi}_{H_{w},-}(s,a)=-\phi(s,a)^{T}w&\text{ on
}M_{H_{w},-}.\\\ \end{cases}$

Proof: Consider $M_{w,+}$ and set $Q(s,a)=\phi(s,a)^{T}w$. We will show that
$Q$ satisfies the Bellman evaluation equations for $\pi$ at all state-actions
pairs, which will imply that $Q(s,a)=Q^{\pi}_{H_{w},+}(s,a)$. Apply
$\mathcal{T}^{\pi}_{M_{H_{w},+}}$ to $Q$ at $(s,a)$:

$\displaystyle\mathcal{T}^{\pi}_{M_{H_{w},+}}(Q)(s,a)$
$\displaystyle=r_{H_{w},+}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a))).$

We consider the RHS of the above for all possible cases.

Case 1: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
for some $k\in[0,...,K]$,
$s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a)$. Furthermore,
$\pi$ must return the only action available in the successor state (and the
successor state is never $\bar{s}$), so
$\pi(s^{+}_{H_{w}}(a))=s^{+}_{H_{w}}(a)$ and we have:

$\displaystyle r_{H_{w},+}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a)))$ $\displaystyle=0+\gamma
Q(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))$
$\displaystyle=\gamma\phi(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))^{T}w$
$\displaystyle=\gamma s^{+}_{H_{w}}(a)^{T}w$
$\displaystyle=\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{k+1}}(a)w$
$\displaystyle=\text{proj}^{T}_{B_{k+1}}(a)w.$

However, recall that $w\in B_{k+1}$. Since $\text{proj}_{B_{k+1}}(a)$ is the
orthogonal projection of $a$: $w^{T}\text{proj}_{B_{k+1}}(a)=w^{T}a$. Plugging
into the above, we have:
$\mathcal{T}^{\pi}_{M_{H_{w},+}}(Q)(s,a)=a^{T}w=\phi(s,a)^{T}w=Q(s,a)$, which
satisfies the Bellman evaluation equation.

Case 2: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$,
$s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a)$, and as before the
policy can only take the only action available there, giving:

$\displaystyle r_{H_{w},+}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a)))$ $\displaystyle=0+\gamma
Q(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))$
$\displaystyle=\gamma\phi(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))^{T}w$
$\displaystyle=\gamma s^{+}_{H_{w}}(a)^{T}w$
$\displaystyle=\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=a^{T}w=\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

Case 3: If $a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$, the
reward is no longer 0 and $s^{+}_{H_{w}}(a)=a$, and again as before the policy
can only take the only action available there so we have:

$\displaystyle r_{H_{w},+}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a)))$
$\displaystyle=+(1-\gamma)a^{T}w+\gamma Q(a,a)$
$\displaystyle=(1-\gamma)a^{T}w+\gamma\phi(a,a)^{T}w$
$\displaystyle=(1-\gamma)a^{T}w+\gamma a^{T}w$
$\displaystyle=a^{T}w=\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

For all cases, $Q$ satisfies the Bellman evaluation equations, so it is the
fixed point of the Bellman evaluation operator. In particular, it is the
action-value of the policy $\pi$ on $M_{H_{w},+}$.

Now consider $M_{w,-}$, for which the argument is identical. Set
$Q(s,a)=-\phi(s,a)^{T}w$. We will show that $Q$ satisfies the Bellman
evaluation equations for $\pi$ at all state-actions pairs, which will imply
that $Q(s,a)=Q^{\pi}_{H_{w},-}(s,a)$. Apply $\mathcal{T}^{\pi}_{M_{H_{w},-}}$
to $Q$ at $(s,a)$:

$\displaystyle\mathcal{T}^{\pi}_{M_{H_{w},-}}(Q)(s,a)$
$\displaystyle=r_{H_{w},-}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a))).$

We consider the RHS of the above for all possible cases.

Case 1: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})\setminus\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
for some $k\in[0,...,K]$,
$s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{k+1}}(a)$. Furthermore,
$\pi$ must return the only action available in the successor state (and the
successor state is never $\bar{s}$), so
$\pi(s^{+}_{H_{w}}(a))=s^{+}_{H_{w}}(a)$ and we have:

$\displaystyle r_{H_{w},-}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a)))$ $\displaystyle=0+\gamma
Q(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))$
$\displaystyle=-\gamma\phi(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))^{T}w$
$\displaystyle=-\gamma s^{+}_{H_{w}}(a)^{T}w$
$\displaystyle=-\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{k+1}}(a)w$
$\displaystyle=-\text{proj}^{T}_{B_{k+1}}(a)w.$

However, recall that $w\in B_{k+1}$. Since $\text{proj}_{B_{k+1}}(a)$ is the
orthogonal projection of $a$: $w^{T}\text{proj}_{B_{k+1}}(a)=w^{T}a$. Plugging
into the above, we have:
$\mathcal{T}^{\pi}_{M_{H_{w},+}}(Q)(s,a)=-a^{T}w=-\phi(s,a)^{T}w=-Q(s,a)$,
which satisfies the Bellman evaluation equation.

Case 2: If
$a\in\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K+1})\setminus(\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w))$,
$s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{K+1}}(a)$, and as before the
policy can only take the only action available there, giving:

$\displaystyle r_{H_{w},-}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a)))$ $\displaystyle=0+\gamma
Q(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))$
$\displaystyle=-\gamma\phi(s^{+}_{H_{w}}(a),s^{+}_{H_{w}}(a))^{T}w$
$\displaystyle=-\gamma s^{+}_{H_{w}}(a)^{T}w$
$\displaystyle=-\gamma\frac{1}{\gamma}\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=-\text{proj}^{T}_{B_{K+1}}(a)w$
$\displaystyle=-a^{T}w=-\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

Case 3: If $a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$, the
reward is no longer 0 and $s^{+}_{H_{w}}(a)=a$, and again as before the policy
can only take the only action available there so we have:

$\displaystyle r_{H_{w},-}(s,a)+\gamma
Q(s^{+}_{H_{w}}(a),\pi(s^{+}_{H_{w}}(a)))$
$\displaystyle=-(1-\gamma)a^{T}w+\gamma Q(a,a)$
$\displaystyle=-(1-\gamma)a^{T}w-\gamma\phi(a,a)^{T}w$
$\displaystyle=-(1-\gamma)a^{T}w-\gamma a^{T}w$
$\displaystyle=-a^{T}w=-\phi(s,a)^{T}w=Q(s,a),$

which satisfies the Bellman evaluation equation.

For all cases, $Q$ satisfies the Bellman evaluation equations, so it is the
fixed point of the Bellman evaluation operator. In particular, it is the
action-value of the policy $\pi$ on $M_{H_{w},-}$. ∎

###  E.4 Proof of Theorem 4.5

Consider the MDP class described in Appendix E.1 and Appendix E.2. First, we
know from Lemma E.1 that all instances of the BPI and PE problem characterised
by the MDP class $\mathcal{M}$ and target policies $\Pi$ satisfy Assumption
4.2 ($Q^{\pi}$ is realizable for every $\pi$) with the feature map
$\phi(\cdot,\cdot)$ defined in Appendix E.1. The proof follows the same
reasoning as in Appendix D.4. We consider policy-free queries.

We specify the instance with MDP $M\in\mathcal{M}$ according to the queries
selected by the learner. Fix $K>0$. Recall that $n_{k}$ is the number of
queries made by the learner at round $k$ and $n=\sum_{k=1}^{K}n_{k}$ is the
total number of queries. Let $A_{k}$ be the set of (policy-free) actions
queried by the learner at round k (i.e. $|A_{k}|=n_{k}$). Set
$\widebar{A}_{k}=\bigcup_{i=1}^{k}A_{k}$ to be the set of all actions queried
up to round $k$.

The learner is sample-efficient so $n$ is polynomial in $d$. Specifically,
there exists some constant $\alpha>0$ and some integer $T$ such that
$n\leq\alpha d^{T}$. Consider $N\in\mathbb{N}$ s.t $2^{N}\leq d<2^{N+1}$ and
set $d_{+}=2^{N}$. Note that $d_{+}\geq d/2$. Fix
$W=exp(\frac{1}{8}g(\gamma)d_{+}^{1/4^{K}})$. If $n\leq W$, we can show the
learner cannot solve the PE problem. Consider both cases:

####  E.4.1 Case 1

Suppose $W<n$, then

$\displaystyle W<n$ $\displaystyle\implies W<\alpha d^{T}$
$\displaystyle\implies\frac{g(\gamma)}{8}d_{+}^{1/4^{K}}<\log(\alpha d^{T})$
$\displaystyle\implies\frac{g(\gamma)}{8}(d/2)^{1/4^{K}}<\log(\alpha
d^{T})\qquad\text{ using that }d_{+}\geq\frac{d}{2}$
$\displaystyle\implies(d/2)^{1/4^{K}}<\frac{8}{g(\gamma)}\log(\alpha d^{T})$
$\displaystyle\implies\frac{1}{4^{K}}\log(d/2)<\log\Big{(}\frac{8}{g(\gamma)}\log(\alpha
d^{T})\Big{)}$
$\displaystyle\implies\frac{\log(d/2)}{\log\Big{(}\frac{8}{g(\gamma)}\log(\alpha
d^{T})\Big{)}}<4^{K}$ $\displaystyle\implies\frac{1}{\log
4}\log\Big{[}\frac{\log(d/2)}{\log\Big{(}\frac{8}{g(\gamma)}\log(\alpha
d^{T})\Big{)}}\Big{]}<K$ $\displaystyle\implies K\geq c^{\prime}\log\log
d\qquad\text{ for a constant $c^{\prime}>0$ and $d$ sufficiently large.}$

####  E.4.2 Case 2

$n\leq W\implies n_{k}\leq\exp(\frac{1}{8}g(\gamma)d_{+}^{1/4^{k}})$ for
$k=1,...,K$. We inductively define the sequence of nested subspaces
$B_{K}\subset...\subset B_{1}$ characterising $w$ ($\in B_{K}$) and used in
the successor state function $s^{+}_{M}$ s.t for $k=1,...,K$, $\dim
B_{k}=2^{\lceil N/4^{k}\rceil}\geq 2^{8}$ and

$\displaystyle\forall a\in\widebar{A}_{k},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k}).$

Proof of existence of nested subspaces:

We proceed by induction. Let $B_{K}\subset...\subset B_{1}$ be an arbitrary
sequence of subspaces and $w\in B_{K}\cap\mathcal{B}$ arbitrary. We will
define these but for now consider the successor state function $s^{+}_{H_{w}}$
(see Appendix E.2) with $H_{w}=\\{\langle w\rangle,B_{K},...,B_{1}\\}$.

Base Case: At round $k=1$, the learner has observed no feedback and chooses a
set of action queries $A_{1}=\widebar{A}_{1}$ (we ignore the queried states
since the reward and transitions functions only depend on the action) such
that:

$\displaystyle|A_{1}|=n_{1}\leq\exp(\frac{1}{8}g(\gamma)d_{+}^{1/4})\leq\Big{(}\frac{d_{+}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{+}^{1/4}}-1\qquad\text{
(if $d_{+}\geq 12$) },$

so by Lemma C.3 there exists a subspace $H\in\mathcal{G}_{2^{\lceil
N/4\rceil},d_{+}}(\mathbb{R})$ of dimension $2^{\lceil N/4\rceil}$ ($\geq
d_{+}^{1/4}$) such that

$\displaystyle\forall x\in A_{1}=\widebar{A}_{1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H).$

Set $B_{1}=H$. The learner then observes the feedback for $A_{1}$ (The state
$s$ in the reward does not matter):

$\displaystyle\\{(r_{w,\pm}(s,a),s^{+}_{H_{w}}(a)):a\in A_{1}\\}.$

Not having fixed $B_{2},...,B_{K},w$ does not cause problems with the feedback
even though $s^{+}_{H_{w}}$ and $r_{w,\pm}$ depend on them since the feedback
of $A_{1}$ only depends on $B_{1}$: the learner only observes the projection
of the actions in $A_{1}$ into $B_{1}$,

$\displaystyle\forall a\in\widebar{A}_{1},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{1})$
$\displaystyle\implies$ $\displaystyle\forall a\in\widebar{A}_{1},\qquad
s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{1}}(a),\qquad
r_{w,\pm}(s,a)=0.$

In particular, there is no dependence on $w$ or $B_{1+i}\subset B_{1}$ for
$i\geq 1$, which can be arbitrary and fixed in later rounds.

Inductive Step: Suppose that at round $k$, there exists a sequence of nested
subspaces $B_{k}\subset...\subset B_{1}$ used by the successor state function
$s^{+}_{H_{w}}$ s.t for $i=1,...,k$, $\dim B_{i}=2^{\lceil N/4^{i}\rceil}\geq
2^{8}$ and

$\displaystyle\forall a\in\widebar{A}_{i},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{i}).$

$B_{k+1}$ need not be fixed yet since the feedback of $\widebar{A}_{k}$ only
depends on $B_{1},...,B_{k}$:

$\displaystyle\forall a\in{A}_{k},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})$
$\displaystyle\implies$ $\displaystyle\forall a\in{A}_{k},\qquad
s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{j}}(a)\qquad\text{ for some
}j\leq k,\qquad r_{w,\pm}(s,a)=0.$

The learner only observes the projection of actions in $\widebar{A}_{k}$ into
$B_{1},B_{2},...,B_{k}$. Note that the only constraint on $M$ up to this step
is $w\in B_{k}$.

Now $B_{k}$ is such that $\forall x\in\widebar{A}_{k}$,
$x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})$ with $d_{k}=\dim
B_{k}=2^{\lceil N/4^{k}\rceil}\geq d^{1/4^{k}}_{+}\geq 2^{8}$. The learner has
observed the feedback from $\widebar{A}_{k}$ and chooses a set of action
queries $A_{k+1}$ such that

$\displaystyle|A_{k+1}|=n_{k+1}\leq\exp(\frac{1}{8}g(\gamma)d_{+}^{1/4^{k+1}})\leq\Big{(}\frac{d_{k}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{+}^{1/4^{k+1}}}-1\leq\Big{(}\frac{d_{k}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{k}^{1/4}}-1\qquad\text{
(if $d_{+}\geq 12$) }.$

Then we know that the number of those queries that are in $B_{k}$ is also less
than $\Big{(}\frac{d_{k}}{2}\Big{)}^{\frac{1}{8}g(\gamma)d_{k}^{1/4}}$.
Therefore by Lemma C.3, there exists a subspace $H\subset B_{k}$ of dimension
$2^{\lceil\lceil N/4^{k}\rceil/4\rceil}\geq d_{k+1}=2^{\lceil
N/4^{k+1}\rceil}$ (can reduce the dimension if they do not match, removing
dimensions will not add queries to
$\overset{\triangle}{\mathcal{C}}_{\gamma}(H)$) such that

$\displaystyle\forall x\in{A}_{k+1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(H).$

In particular, $A_{k+1}$ can be entirely contained in $B_{k}$ or can depend on
$B_{k},...,B_{1}$ in any arbitrary way. Set $B_{k+1}=H$. We know that $\forall
x\in\widebar{A}_{k},x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k})$
and $B_{k+1}\subset B_{k}$ so we have

$\displaystyle\forall x\in\widebar{A}_{k+1},\qquad
x\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1}).$

The learner then observes the feedback for $A_{k+1}$ (The state $s$ in the
reward does not matter):

$\displaystyle\\{(r_{w,\pm}(s,a),s^{+}_{H_{w}}(a)):a\in A_{k+1}\\}.$

Not having fixed $B_{k+2},...,B_{K},w$ does not cause problems with the
feedback even though $s^{+}_{H_{w}}$ and $r_{w,\pm}$ depend on them since the
feedback observed up to this round of $\widebar{A}_{k+1}$ only depends on
$B_{1},...,B_{k+1}$: the learner only observes the projection of the actions
in $\widebar{A}_{k+1}$ into $B_{1},...,B_{k+1}$,

$\displaystyle\forall a\in{A}_{k+1},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{k+1})$
$\displaystyle\implies$ $\displaystyle\forall a\in{A}_{k},\qquad
s^{+}_{H_{w}}(a)=\frac{1}{\gamma}\text{proj}_{B_{j}}(a)\qquad\text{ for some
}j\leq k+1,\qquad r_{w,\pm}(s,a)=0.$

In particular, there is no dependence on $w$ or $B_{k+1+i}\subset B_{k+1}$ for
$i\geq 1$, which can be arbitrary and fixed in later rounds.

We remark Lemma C.3 establishes the existence of a subspace in
$\mathcal{G}_{2^{\lceil\lceil N/4^{k}\rceil/4\rceil},d_{k}}(\mathbb{R})$ where
the ambient space is $\mathbb{R}^{d_{k}}$ instead of $\mathbb{R}^{d}$. Any
$d_{k}$-dimensional subspace of $\mathbb{R}^{d}$ is isomorphic to
$\mathbb{R}^{d_{k}}$, so we can consider $B_{k}$, project the points of
$A_{k+1}$ into $B_{k}$, apply Lemma C.3 to get $H$ within $B_{k}$, and extend
$H$ to be defined in $\mathbb{R}^{d}$. We omit these steps here for clarity
but detail them fully in Appendix D.4.3. This also holds for the base case
(where $d_{+}$ is used as the ambient dimension instead of $d$)

When applying Lemma C.3 with ambient dimension $d_{k}=2^{\lceil
N/4^{k}\rceil}$, we require $\lceil N/4^{k}\rceil\geq 8$. Since $d_{k}\geq
d_{+}^{1/4^{k}}$ and $d_{+}\geq d/2$, it is enough to have

$\displaystyle(d/2)^{1/4^{k}}\geq 2^{8}$ $\displaystyle\iff K\leq\frac{1}{\log
4}\log\Big{(}\frac{1}{8\log 2}\log\frac{d}{2}\Big{)}$ $\displaystyle\impliedby
K\leq c\log\log d,$

for a constant $c>0$ and $d$ sufficiently large. If this condition on $K$ does
not hold, then

$\displaystyle K>c\log\log d.$ (4)

Suppose it does hold. Then the steps above go through and we have the
existence of our nested subspaces. We also have $d_{k}\geq 2^{8}>12$ for all
$k=1,...,K$, which was needed in some of the steps.

End of proof of existence of nested subspaces.

We now fully specify $M$. The complete set of queried actions by the learner
is $\widebar{A}_{K}$, and

$\displaystyle\forall a\in\widebar{A}_{K},\qquad
a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K}).$

Since $\dim B_{K}\geq 2^{8}>0$, we can pick some $w\in
B_{K}\cap\partial\mathcal{B}$ and let $H_{w}=\\{B_{1},...,B_{K},B_{K+1}\\}$
with $B_{K+1}=\langle w\rangle$. From the proof of the existence of nested
spaces, we can consider the BPI and PE problem instances with MDPs
$M_{H_{w},+}$ and $M_{H_{w},-}$. The transition function is the same on
$M_{H_{w},+}$ and $M_{H_{w},-}$. Since $\forall a\in\widebar{A}_{K}$,
$a\notin\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ because
$a\notin\overset{\triangle}{\mathcal{C}}_{\gamma}(B_{K})$, the reward function
for any queried action $a\in\widebar{A}_{K}$ is $0$. Thus, the learner cannot
distinguish $M_{H_{w},+}$ between $M_{H_{w},-}$ from the submitted queries.

For PE, the learner has to produce an estimate of $Q^{\pi}(\bar{s},\cdot)$.
But

$\displaystyle
Q^{\pi}(\bar{s},w)=\phi(\bar{s},w)^{T}w=w^{T}w=1\quad\quad\quad\text{ on
}M_{H_{w},+}.$ $\displaystyle
Q^{\pi}(\bar{s},w)=-\phi(\bar{s},w)^{T}w=-w^{T}w=-1\quad\text{ on
}M_{H_{w},-}.$

If the learner predicts a positive value for $Q^{\pi}(\bar{s},w)$, it will
incur an error greater than $1$ on $M_{H_{w},-}$ and similarly for
$M_{H_{w},+}$ if it predicts a negative value. Even if it randomizes between
both, with probability at least $1/2$ it will incur an error of at least $1$
on one of the MDPs.

Similarly for BPI, the learner has to produce a near-optimal policy in the
starting state $\bar{s}$. But

$\displaystyle
V^{\star}_{M_{H_{w},+}}(\bar{s})=Q^{\star}_{M_{H_{w},+}}(\bar{s},w)=\phi(\bar{s},w)^{T}w=w^{T}w=1.$
$\displaystyle
V^{\star}_{M_{H_{w},-}}(\bar{s})=Q^{\star}_{M_{H_{w},-}}(\bar{s},w)=-\phi(\bar{s},w)^{T}w=w-^{T}w=-1.$

If the learner outputs a policy taking action $a$ s.t $a^{T}w>0$, it will
incur an error greater than $1$ on $M_{H_{w},-}$ and similarly for
$M_{H_{w},+}$ if it produces an action $a$ s.t $a^{T}w\leq 0$. Even if it
randomizes between both, with probability at least $1/2$ it will incur an
error of at least $1$ on one of the MDPs.

Therefore, to be more than $(1,1/2)$-sound, we must either be in Case 1 or be
in Case 2 and satisfy condition (4). In either case, we have the condition

$\displaystyle K>c\log\log d,$

for some constant $c>0$ and $d$ sufficiently large, which gives
$K=\Omega(\log\log d)$, showing the result. ∎

##  Appendix F Proofs for Fully-Adaptive Setting

###  F.1 Proof of Theorem A.2

Fix an unknown MDP $M$. Consider a learning algorithm with the following
procedure:

Step 1: The learner selects an arbitrary query $(s_{1},a_{1})$ s.t
$\|\phi(s_{1},a_{1})\|_{2}=1$ (possible by Assumption A.1). The learner
receives from the environment the reward $r_{M}(s_{1},a_{1})$, the transition
function $p_{M}(\cdot|s_{1},a_{1})$ and evaluations of the target policy
$\pi_{M}$ for all states in the support of the transition function
$p_{M}(\cdot|s_{1},a_{1})$.

Step $k\leq d$: For $i<k$, let $(s_{i},a_{i})$ be the query at round $i$.
Define $v_{i}=\phi(s_{i},a_{i})-\gamma\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{i},a_{i})}[\phi(s^{\prime},\pi_{M}(s^{\prime}))]$. Select the
query $(s_{k},a_{k})$ s.t

$\displaystyle\phi(s_{k},a_{k})\in\langle
v_{1},...,v_{k-1}\rangle^{\perp}\quad\text{ and
}\quad\|\phi(s_{k},a_{k})\|_{2}=1.$

The feedback to the learner up to round $k$ means the learner has access to
$v_{1},...,v_{k-1}$. This together with Assumption A.1 ensures the query-
choice is possible.

Denote $v_{k}=\phi(s_{k},a_{k})-\gamma\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{k},a_{k})}[\phi(s^{\prime},\pi_{M}(s^{\prime}))]$.

Claim: $v_{k}\notin\langle v_{1},...,v_{k-1}\rangle$.

###### Proof.

Suppose the claim is not true, then $v_{k}\in\langle v_{1},...,v_{k-1}\rangle$
and $v_{k}^{T}\phi(s_{k},a_{k})=0$ since $\phi(s_{k},a_{k})\in\langle
v_{1},...,v_{k-1}\rangle^{\perp}$. Using this,

$\displaystyle\|\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{k},a_{k})}[\phi(s^{\prime},\pi_{M}(s^{\prime}))]\|_{2}^{2}$
$\displaystyle=\frac{1}{\gamma^{2}}(v_{k}-\phi(s_{k},a_{k}))^{T}(v_{k}-\phi(s_{k},a_{k}))$
$\displaystyle=\frac{1}{\gamma^{2}}(v_{k}^{T}v_{k}-2v_{k}^{T}\phi(s_{k},a_{k})+\phi(s_{k},a_{k})^{T}\phi(s_{k},a_{k}))$
$\displaystyle=\frac{1}{\gamma^{2}}(\|v_{k}\|_{2}^{2}+1)$
$\displaystyle\geq\frac{1}{\gamma^{2}}>1,$

which is not possible since $\phi(s,a)\in\mathcal{B}$ for all state-actions
pairs $(s,a)$, and by Jensen’s inequality

$\displaystyle\|\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{k},a_{k})}[\phi(s^{\prime},\pi_{M}(s^{\prime}))]\|_{2}\leq\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{k},a_{k})}[\|\phi(s^{\prime},\pi_{M}(s^{\prime}))\|_{2}]\leq
1.$

This proves the claim. ∎

The claim implies that $\\{v_{i}\\}_{i=1}^{k}$ is a linearly independent set
of vectors. To see why this is the case, suppose it is not true:

$\displaystyle\exists(\alpha_{i})_{i=1}^{k}\quad\text{ s.t one of them is non-
zero and }\qquad\sum\limits_{i=1}^{k}\alpha_{i}v_{i}=0.$

Let $j$ be the largest index s.t $\alpha_{j}\neq 0$, then

$\displaystyle
v_{j}=\frac{1}{\alpha_{j}}\Big{(}\sum\limits_{i<j}\alpha_{i}v_{i}\Big{)}\in\langle
v_{1},...,v_{j-1}\rangle,$

which contradicts the claim. So $\\{v_{i}\\}_{i=1}^{k}$ is a linearly
independent set of vectors.

Under realizability, we must have
$Q^{\pi_{M}}_{M}(s_{i},a_{i})=\phi(s_{i},a_{i})^{T}\theta_{M}^{\pi_{M}}$ for
some $\theta_{M}^{\pi_{M}}$ and since it is the fixed point of the Bellman
evaluation operator we also have

$\displaystyle
Q^{\pi_{M}}_{M}(s_{i},a_{i})=r(s_{i},a_{i})+\gamma\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{i},a_{i})}[Q^{\pi_{M}}_{M}(s^{\prime},\pi_{M}(s^{\prime}))].$

Let $\Phi=\begin{bmatrix}\phi(s_{1},a_{1})^{T}\\\ ...\\\
\phi(s_{d},a_{d})^{T}\\\ \end{bmatrix}$,
$r=\begin{bmatrix}r_{M}(s_{1},a_{1})\\\ ...\\\ r_{M}(s_{d},a_{d})\\\
\end{bmatrix}$ and $\Phi^{+}=\begin{bmatrix}\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{1},a_{1})}[\phi(s^{\prime},\pi_{M}(s^{\prime}))^{T}]\\\ ...\\\
\mathbb{E}_{s^{\prime}\sim
p_{M}(\cdot|s_{d},a_{d})}[\phi(s^{\prime},\pi_{M}(s^{\prime}))^{T}]\\\
\end{bmatrix}$.

Combining the realizability assumption with the Bellman fixed point equation
with the above notation we have:

$\displaystyle\Phi\theta_{M}^{\pi_{M}}=r+\gamma\Phi^{+}\theta_{M}^{\pi_{M}}\iff\Big{(}\Phi-\gamma\Phi^{+}\Big{)}\theta_{M}^{\pi_{M}}=r.$

Noticing that $v_{i}$ is the $i$th row of $\Phi-\gamma\Phi^{+}$ and using that
they are all linearly independent, $\Phi-\gamma\Phi^{+}$ is a square full rank
matrix and is thus invertible, giving the unique solution of the policy
evaluation problem $\theta_{M}^{\pi_{M}}$ in terms of quantities known to the
learner at the $d$-th round. ∎

###  F.2 Proof of Theorem A.3

####  F.2.1 MDP Class

We consider the same MDP class as for Theorem E \- see Appendix E.1.

####  F.2.2 Instance of the class

Consider a sequence of $d$ strictly nested subspaces of $\mathbb{R}^{d}$:

$\displaystyle B_{d-1}\subset B_{d-1}\subset...\subset B_{2}\subset
B_{1}\subset B_{0}=\mathbb{R}^{d},$