Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL

Introduction

While the grand goal of reinforcement learning (RL) is to design fully autonomous agents capable of improving their performance over time by learning from past mistakes, oftentimes a batch approach — which predicts some quantity of interest using past observations only — is preferable. For example, past data may be available in large quantities and should not be disregarded by adopting a purely online method. In other applications, safety concerns require that the dataset be collected by a carefully monitored procedure, involving a human or a safe controller. In addition, batch algorithms are key tools to build complex online procedures.

These considerations motivate us to investigate whether there exists any fundamental limitation to using a batch approach for RL compared to online learning. Concretely, we consider two classical batch RL problems: 1) the off-policy evaluation (OPE) problem, where the batch algorithm needs to predict the performance of a target policy and 2) the best policy identification (BPI) problem, where the batch algorithm needs to identify a near optimal policy.

As many applications of RL require very large state and action spaces, the hope is that by leveraging strong prior knowledge, for example on the form of the optimal solution, we can learn the critical features of a Markov decision process (MDP) to solve the task at hand without probing the full state-action space. For the OPE problem, we assume that the action-value function $Q^{\pi}$ of the target policy $\pi$ can be written at any state action pair $(s,a)$ as an inner product $\phi(s,a)^{\top}\theta$ between a known feature extractor $\phi$ and an unknown parameter $\theta$ that the learner seeks to identify. For the BPI problem, this representation condition applies to the action-value function $Q^{\star}$ of an optimal policy.

Quality of the dataset and assumptions

Batch algorithms are limited by the quality and quantity of the available data: for example, in a tabular MDP, without adequate coverage of the area of the MDP that the optimal policy tends to visit, there is little hope that we can identify such policy or even predict its performance. However, given enough samples in each state-action pairs, it becomes easy to identify the optimal policy (Azar et al., 2012) or to evaluate the value of another (Yin et al., 2020). In addition, without any prior knowledge about the problem or information about the target policy, a uniform distribution over the state-action space is a priori optimal.

Very recently, some authors have derived exponential lower bounds for the off-policy evaluation problem with linear function approximations (Wang et al., 2020a; Amortila et al., 2020). They discover that even if a sampling distribution induces the best-conditioned covariance matrix, at least exponentially many samples are needed to estimate the value of a target policy reasonably well. As their hard instances are tabular MDPs (i.e., with small state-action spaces), certainly there exists a better batch distribution for their setting: the OPE problem in tabular MDPs is easily solvable by using a uniform distribution over the state-actions coupled with the policy evaluation algorithm on the empirical model. Therefore, their works show that the assumption on the condition number of the covariance matrix is insufficient in batch RL. However, their works leave open the question of whether the OPE problem with linear value functions can always be solved by using a better sampling distribution that generates a dataset of polynomial size (in the horizon and feature dimension), leading to the following, more fundamental question in the context of batch RL with function approximation:

What can a batch algorithm learn using the best a priori distribution for the problem class at hand?

In particular, we wonder whether there is any penalty in using an entirely batch approach in place of an online (and adaptive) method if a good dataset is provided to the batch algorithm. To answer this question for both the OPE and BPI problems in the strongest possible way, we consider an auxiliary process or oracle that provides the batch algorithm with the best data distribution for the task; together they form a learning algorithm. However, in contrast to fully online / adaptive algorithms, the oracle is not allowed to change its data acquisition strategy while information is being acquired. As we explain in Appendix A, this framework allows us to derive strong batch RL lower bounds, because they will hold for every batch distribution. Thanks to this framework, we can recover the concurrent lower bound by (Wang et al., 2020a) — which holds for one specific choice of the sampling distribution — in infinite horizon RL as a corollary.

Learning process and assumptions

We consider oracles that can decide on a set of strategic policies to gather data. Alternatively, the oracles can directly specify the state-actions where they want to observe the rewards and transitions (for example, with a simulator). In either case, the oracle selects a sampling strategy and the batch algorithm later receives a dataset of states, actions, rewards and transitions. Using the dataset, the batch algorithm makes a prediction, i.e., it estimates the value of a target policy (OPE problem) or returns a near optimal policy (BPI problem). We make two other assumptions that favor the learner:

Realizability, i.e., there is no misspecification.

Exact feedback: the exact reward and transition function is observed for each point in the dataset. This is equivalent to observing infinite data.

1 Contributions

there exists OPE and BPI problems where any batch algorithm must receive an exponential $\approx(\frac{1}{1-\gamma})^{d}$ dataset to return a good answer,

if the dataset does not originate from policy rollouts then the lower bounds hold even if the action-value function of every policy admits a linear representation,

there exist exponentially hard batch BPI problems (even under the best data distribution) which are easy to solve with online / adaptive algorithms, showing an exponential separation between batch and online RL,

there exist exponentially hard problems for infinite horizon batch RL which cannot arise in finite horizon problems, showing exponential separation between finite and infinite horizon batch RL.

As a corollary, our work recovers (Wang et al., 2020a)’s lower bound in infinite horizon RL and also shows that the classical globally optimal experimental design yields provably bad distributions for infinite horizon RL, making learning impossible even in the limit of infinite data; we discuss this in Appendix A.

We make the following technical contributions:

we introduce a new ‘oracle + batch algorithm’ framework to derive lower bounds for every a priori distribution; this automatically yields fixed distribution lower bounds (e.g., (Wang et al., 2020a)) as a special case,

we help formalize the hardness induced by the deadly triad (Sutton & Barto, 2018), i.e., the combination of off-policy learning, bootstrapping and function approximation; in particular, we explain that the bootstrapping problem is fundamentally different and potentially more severe than the extrapolation problem,

we present new classes of hard MDPs where critical MDP information is ‘deferred’ — through bootstrapping — and hidden in an unknown and exponentially small region in feature space, too small to be covered by a batch dataset but easy to locate using an online algorithm.

2 Literature

Polynomial lower bounds are often derived to certify that a certain algorithm is sample efficient (Jiang & Li, 2016; Duan & Wang, 2020; Hao et al., 2020); in this work we are interested in exponential lower bounds. Divergence of dynamic programing algorithms with function approximation is well known (Baird, 1995; Tsitsiklis & Van Roy, 1996) and has prompted researchers to look for information-theoretic lower bounds for generic predictors (Chen & Jiang, 2019) and in presence of misspecification (Du et al., 2019). Concurrently, Weisz et al. (2020); Wang et al. (2020a) also show information-theoretic lower bounds highlighting the danger of extrapolation; for additional literature, please see app. B.

Preliminaries

Batch Reinforcement Learning

We first formally define the two learning problems, namely the task of returning a near optimal policy, also known as best policy identification (BPI) problem, and the task of predicting the value of a target policy, also known as off-policy evaluation (OPE) problem. Then, in the next four sub-sections we describe the learning process in more detail. The lower bounds that we later derive will hold for all algorithms of the form described in this section.

A BPI problem $(s^{\star},\{M\in\mathcal{M}\})$ is defined by a starting state $s^{\star}$ and a class $\mathcal{M}$ of MDPs sharing the same state space, action space and discount factor. An OPE problem $(s^{\star},\{(M,\pi_{M})\mid M\in\mathcal{M}\})$ additionally requires us to identify one or more target policies $\pi_{M}$ for each $M\in\mathcal{M}$.

Depending on the problem, the oracle selects a sampling strategy such that for every problem instance $(s^{\star},M,\pi_{M})$ (of an OPE problem) or $(s^{\star},M)$ (of a BPI problem) the batch algorithm experiences a dataset $\mathcal{D}$ from $M$ and uses it to return an accurate estimate $\widehat{Q}_{\mathcal{D}}$ of the action-value function of $\pi_{M}$ at $s^{\star}$ (for the OPE problem) or a near optimal policy $\widehat{\pi}^{\star}_{\mathcal{D}}$ on $M$ from $s^{\star}$ (for the BPI problem).

2 Step II: Query Selection

The purpose of the oracle is to help the batch algorithm by providing it with the best dataset for the specific problem at hand. To capture different mechanisms of data acquisition, we consider two methods to specify the query set, i.e., the set of state-action pairs where the oracle wants the batch algorithm to observe the rewards and the transitions. In the first mechanism the oracle directly selects the state-actions; we place no restriction on the mechanism to obtain these queries as long as the sampling distribution is fixed for all MDPs in the class.

A set $\mu$ of state-action pairs is said to be policy-free for an OPE or BPI problem if $\mu$ does not depend on the specific MDP instance $M\in\mathcal{M}$.

Since the batch algorithm observes the exact reward and transition function at the selected query points, the number of policy-free queries is the size of the support of the distribution $\mu$.

The second mechanism to collect data is by selecting deterministicThis is not a restriction: for any given stochastic policy the agent can sample an action from the distribution of actions in every state before deploying the policy. policies. The policies will generate random trajectories that the batch algorithm later observes. Since we are interested in what the agent can learn in the limit of infinite data (i.e., under exact feedback) we let the batch algorithm observe all possible realizations of such trajectories. With this aim, we define the state-action space reachable in $c$ or less timesteps from $s_{0}$ using policy $\pi$ as $\operatorname*{Reach}(s_{0},\pi,c)=$

where $(s_{t},a_{t})$ is the random state-action encountered at timestep $t$ upon following $\pi$ from $s_{0}$. We let the oracle select the best combination of trajectory lengths and number of distinct policies.

Consider an OPE or BPI problem and fix a set $T=\{(s_{0i},\pi_{i},c_{i})\}_{i=1}^{\kappa}$ of triplets, each containing a starting state $s_{0i}$, a deterministic policy $\pi_{i}$ and a trajectory length $c_{i}$ such that $\sum_{i=1}^{\kappa}c_{i}\leq n$. Then the query set $\mu$ induced by $T$ is defined as

The condition $\sum_{i=1}^{\kappa}c_{i}\leq n$ attempts to make the amount of information acquired using policy-free queries comparable to the policy-induced query method, although the latter generates $|\mu|\geq n$ if the dynamics are stochastic. In other words, the batch learner always observes at least $n$ state-actions if these are induced by policies.

A policy-induced query set is also policy-free whenever the dynamics of each MDP $M\in\mathcal{M}$ are the same.

When prescribing a set $T$ the oracle has knowledge of the induced dataset $\mu$ for each choice of $T$ (e.g., by having access to a connectivity graph of the MDP).

While a policy-free query set may seem less constrained than a policy-induced query set, the latter may implicitly reveal additional information about the dynamics of the MDP whenever the induced trajectories are all different across different MDPs.

3 Step III: Data Collection

After the oracle has submitted the sampling strategy, the batch learner receives a dataset $\mathcal{D}$ which contains the exact reward and transition function, $r(s,a)$ and $p(s,a)$, from the MDP $M\in\mathcal{M}$ for each $(s,a)$ in the query set $\mu$.

4 Step IV: Output

The batch algorithm is finally required to make a prediction using the acquired dataset $\mathcal{D}$. For the OPE problem, the batch algorithm also receives the target policy $\pi_{M}$ and it is required to output an estimator $\widehat{Q}_{\mathcal{D}}$ for the action-value function of the target policy $Q_{M}^{\pi_{M}}(s^{\star},\cdot)$; for the BPI problem, it must output a near-optimal policy $\widehat{\pi}^{\star}_{\mathcal{D}}$ at $s^{\star}$.

5 Evaluation Criterion

The oracle and the batch algorithm together form a learning algorithm. This framework allows us to derive batch lower bounds in a strong form as they will hold for any data distribution. We say that the learning algorithm is $(\epsilon,\delta)$-sound for an OPE problem if for every instance $(s^{\star},M,\pi_{M})$ of the problem the returned estimator $\widehat{Q}_{\mathcal{D}}$ is accurate w.h.p.:

Similarly, we say that that the learning algorithm is $(\epsilon,\delta)$-sound for a BPI problem if for every instance $(s^{\star},M)$ it holds that the returned policy $\widehat{\pi}^{\star}_{\mathcal{D}}$ is near optimal w.h.p.:

As the query set is always non-random and the batch algorithm experiences the exact reward and transition function, the only randomness lies in the possible randomization internal to the batch algorithm when it returns an answer.

6 Adaptive and Online Algorithms

Consider a policy-free mechanism. We say that a learning algorithm is adaptive if every time the oracle submits a state-action it receives the feedback from the environment and can use it to select the next state-action to query the MDP.

Likewise, consider a policy-induced mechanism. We say that a learning algorithm is acting online if every time the oracle selects a policy and trajectory length, it can use the acquired feedback to select the next combination of policy and trajectory length (its position is reset in every episode).

Intuition

The mechanism that induces hardness for infinite horizon problems must be different than that in finite horizon: the constructions from Weisz et al. (2020); Wang et al. (2020b) rely on the extrapolation issue that compounds the errors multiplicatively. In our case, the reward and transition functions are observed exactly, so there is no error to extrapolate in the first place. Instead, bootstrapping, i.e., the fact that the value function in one state depends on the same value function at successor states (Sutton & Barto, 2018), is the root cause of hardness; here we provide some intuition.

While each of our theorems need a different construction, they all build on the intuition presented in this section; at a high level, bootstrapping can “erase” the information gained along certain directions in feature space.

An online algorithm can detect that the next-state feature matrix $\Phi^{+}$ is acting adversarially. In addition, $\Phi^{+}$ reveals the location of the spherical cap in Fig. 1 (right). The online algorithm can then probe the spherical cap to ensure that the linear system in Eq. 1 is full rank.

Exponential Lower Bounds

We define the query complexity to $(\epsilon,\delta)$-soundness of a problem (OPE or BPI) to be the minimum value for $n$ (as in Definitions 1 and 2) such that there exists a $(\epsilon,\delta)$-sound learning algorithm for that problem. In particular, the query complexity depends on the MDP class $\mathcal{M}$ and can be different for the OPE and BPI tasks and for the policy-free and policy-induced query mechanism. Our lower bounds on the query complexity are significantly stronger than typical sample complexity lower bounds: they are really lower bounds on the size of the support of the distribution $\mu$ and automatically imply infinite sample complexity lower bounds since the batch algorithm already observes the exact reward and transition functions where $\mu$ is supported.

The lower bounds are expressed in terms of the regularized incomplete beta function $I_{x}(a,b)=B(x,a,b)/B(1,a,b)$ where $B(x,a,b)$ is the incomplete beta function for some positive real numbers $a,b$ and $x\in$; for the precise definitions, please see Section D.1. For brevity, define $\mathcal{N}(\gamma,d)=I^{-1}_{1-\gamma^{2}}\left(\frac{d-1}{2},\frac{1}{2}\right)$. Corollary 2 ensures $\mathcal{N}(\gamma,d)$ is exponential in the dimension $d$ for $d\geq 5$ (here the $\approx$ symbol highlights an approximate dependence without a formal definition):

Unless additional assumptions are made regarding the MDP class $\mathcal{M}$ that defines the OPE and BPI problems, the query complexity of a reasonably sound learner is exactly the size of the state and action space (we assume exact feedback). One hopes that by restricting the MDP class $\mathcal{M}$, the query complexity of the OPE and BPI problems can be brought down to a more manageable level, in particular, independent of the state-action spaces.

We make one of the following three assumptions (only one assumption will hold at any given time, depending on the theorem); two are known as realizability, and the third is strictly stronger than the first two. The first concerns the OPE problem; $\mathcal{B}$ is the unit Euclidean ball.

Given an OPE problem $(s^{\star},\{(M,\pi_{M}),M\in\mathcal{M}\})$, there exists a $d$-dimensional map $\phi(\cdot,\cdot)$ such that $\|\phi(\cdot,\cdot)\|_{2}\leq 1$ and for any $M\in\mathcal{M}$ the action-value function of the target policy $\pi_{M}$ satisfies $\forall(s,a),Q_{M}^{\pi_{M}}(s,a)=\phi(s,a)^{\top}\theta_{M}$ for some $\theta_{M}\in\mathcal{B}$.

For the BPI problem the representation condition applies to the action-value function of an optimal policy.

Given a BPI problem $(s^{\star},\{M\in\mathcal{M}\})$, there exists a $d$-dimensional feature map $\phi(\cdot,\cdot)$ such that $\|\phi(\cdot,\cdot)\|_{2}\leq 1$ and for any $M\in\mathcal{M}$ there exists $\theta_{M}^{\star}\in\mathcal{B}$ such that the optimal action-value function is linear: $\forall(s,a),Q^{\star}_{M}(s,a)=\phi(s,a)^{\top}\theta_{M}^{\star}$.

A stronger assumption we make is that the action-value function of every policy has a linear representation.

Given a BPI problem $(s^{\star},\{M\in\mathcal{M}\})$ or an OPE problem $(s^{\star},\{(M,\pi_{M}),M\in\mathcal{M}\})$, there exists a $d$-dimensional feature map $\phi(\cdot,\cdot)$ such that $\|\phi(\cdot,\cdot)\|_{2}\leq 1$ and for any MDP $M\in\mathcal{M}$ the value of every policy $\pi$ satisfies $\forall(s,a),Q_{M}^{\pi}(s,a)=\phi(s,a)^{\top}\theta^{\pi}_{M}$ for some $\theta^{\pi}_{M}\in\mathcal{B}$.

The learners that we consider are aware of these assumptions because they can examine each MDP in the class $\mathcal{M}$ they receive (see Section 3.1).

2 Off-Policy Evaluation

The first result of this work is contained in the following lower bound for the OPE problem; since all MDPs in $\mathcal{M}$ share the same dynamics, the oracle has full knowledge of the actions it needs to take to visit any state-action it desires.

There exists an OPE problem $(s^{\star},\{(M,\pi_{M}),M\in\mathcal{M}\})$ satisfying 1 such that its policy-induced query complexity to $(1,1/2)$-soundness is at least $\mathcal{N}(\gamma,d)$.

It is useful to compare the form of the above lower bound with that of some concurrent results for the off-policy evaluation problem: for example, (Wang et al., 2020a; Amortila et al., 2020) show that there exist a sampling distribution $\mu$ (that induces the best-conditioned covariance matrix), a target policy $\pi$ and an MDP class $\widetilde{\mathcal{M}}$, each satisfying certain properties, such that the best estimator on the most difficult MDP in $\widetilde{\mathcal{M}}$ performs poorly if less than exponentially many samples are used. However, in their case there exists a better batch distribution of polynomial size that solves the problem. Our instances are instead much harder, as they command an exponential dataset even for the best distribution for the task: since the oracle can prescribe any data distribution, we can claim that for all distributions of polynomial size we can find an MDP subclass $\widetilde{\mathcal{M}}\subseteq\mathcal{M}$ and a target policy such that all MDPs in $\widetilde{\mathcal{M}}$ generate similar datasets but the value of the target policy is very different on these MDPs in $\widetilde{\mathcal{M}}$, giving lower bounds in a stronger form.

3 Best Policy Identification

As in Theorem 1, in the next lower bound the oracle knows the set $\mu$ induced by any choice of $T$ (see Definition 2).

There exists a BPI problem $(s^{\star},\{M\in\mathcal{M}\})$ satisfying 2 with features in dimension $d+1$ such that its policy-induced query complexity to $(1/2,1/2)$-soundness is at least $2^{-d}\mathcal{N}(\gamma,d)$.

Hard BPI problems for adaptive and online algorithms are given by Weisz et al. (2020). Clearly, their construction can be embedded in an infinite horizon MDP, giving a lower bound under their assumptions. However, our framework allows the learner to observe the exact reward and transition function, which is equivalent to having infinite data at the selected state-actions. In such case, the construction of Weisz et al. (2020) no longer gives rise to hard instances. In particular, the BPI problem with our assumptions becomes straightforward in finite horizon, showing an exponential separation between finite and infinite horizon batch RL.

4 Lower Bounds with Stronger Representation

We wonder what is achievable if the oracle can specify the queries anywhere in the state-action space without the restriction imposed by following policies (i.e., using a policy-free query set). Under this assumption the situation gets surprisingly worse, as the lower bounds now hold even if the action-value function of every policy is linear.

There exist an OPE problem $(s^{\star},\{(M,\pi_{M}),M\in\mathcal{M}\})$ and a BPI problem $(s^{\star},\{M\in\mathcal{M}\})$, which satisfy 3 and share the same $s^{\star}$ and $\mathcal{M}$, such that their policy-free query complexity to $(1,1/2)$-soundness is at least $\mathcal{N}(\gamma,d)$. In addition, an MDP class $\mathcal{M}$ that yields the lower bounds (but with $\frac{1}{\sqrt{d}},1/2)$-soundness) can be constucted with at most $|\mathcal{A}|=2d$ actions.

Contrasting Theorem 3 with Theorems 1 and 2 shows that there is a sharp distinction in what can be achieved depending on the assumptions on the mechanism that generates the batch dataset, a distinction which is absent in tabular RL.

Exponential Separation with Online Learning

Consider the same BPI problem as in Theorem 2. There exists an online algorithm that can identify an optimal policy with probability one by observing trajectories of length one with exact feedback from $d+1$ distinct policies from $s^{\star}$.

This result shows exponential separation with online learning even when the best batch distribution is used. The key information is hidden in an exponentially small area of the feature space whose position is a priori unknown. This region is too small to be covered by a batch dataset. However, an online algorithm can learn where this information is hidden and then probe such region as we show in Section 7.

A similar exponential separation with online learning is available for the BPI problem in Theorem 3 (see the end of the proof in the appendix). In addition, assuming access to a generative model an even stronger result is readily available in the literature using the Least-Square Policy Iteration (LSPI) algorithm (Lagoudakis & Parr, 2003): with a generative model (Lattimore et al., 2020) show that with probability at least $1-\delta$, LSPI finds an $\epsilon$ optimal policy for any BPI problem $(s^{\star},\{M\in\mathcal{M}\})$ that satisfies 3 using at most $\operatorname*{poly}(d,\frac{1}{1-\gamma},\frac{1}{\epsilon},\ln\frac{1}{\delta})$ samples. However, LSPI is non-batch as it relies on Monte-Carlo rollouts at every iteration. Our result thus shows that it is not possible to start from a batch dataset obtained from a generative model and run LSPI (or any algorithm) successfully without acquiring further data even if a strong representation holds.

Proof Sketch of Theorem 2 and Theorem 4

We first describe the state and action space which are fixed across all MDPs in the class $\mathcal{M}$. Then we describe the instance-dependent reward and transition functions. Finally we prove the theorems.

At a high level, each MDP contains a two-armed bandit instance in $s^{\star}$ (the starting state). There, the learner has two choices: 1) take the special action $a^{\star}$ that gives a known return or 2) take any other action in the positive orthant $\mathcal{B}^{+}=\{x\in\mathcal{B}\mid x_{i}\geq 0,i\in[d]\}$, see Fig. 2.

Crucially, on $\mathcal{B}^{+}$ the reward function is almost everywhere zero except inside the exponentially small spherical cap $\mathcal{C}_{\gamma}(w)=\{\|x\|_{2}\leq 1\mid\frac{x^{\top}w}{\|w\|_{2}}\geq\gamma\}$ (Fig. 2) for some $w\in\mathcal{B}$. Unless the oracle prescribes an action inside $\mathcal{C}_{\gamma}(w)$, the batch algorithm only observes a zero reward function and is unable to distinguish different MDPs using this information.

The state space $\mathcal{S}=\{s^{\star},\overline{s},s^{\dagger}\}$ consists of a start state $s^{\star}$, an intermediate state $\overline{s}$ and a terminal state $s^{\dagger}$.

Action space

In the starting state $s^{\star}$ the special action $a^{\star}$ is available in addition to any action $a\in\mathcal{B}^{+}$. In the intermediate state $\overline{s}$ any action in $\mathcal{B}^{+}$ is available but not $a^{\star}$. Finally, in the terminal state $s^{\dagger}$ only $\vec{0}\in\mathcal{B}^{+}$ is available. Mathematically $\mathcal{A}_{s^{\star}}=\mathcal{B}^{+}\cup\{a^{\star}\};\;\mathcal{A}_{\overline{s}}=\mathcal{B}^{+};\;\mathcal{A}_{s^{\dagger}}=\{\vec{0}\}.$

Feature map

The feature map only depends on the action:

2 Setup: MDP-specific Rewards and Transitions

Every MDP $M\in\mathcal{M}$ is identified by a vector $w$ in the outer portion of the positive orthant $\partial\mathcal{B}^{+}=\{x\in\mathcal{B}^{+}\mid\|x\|_{2}=1\}$ and by a $\pm$ sign, and is denoted with $M_{w,+}$ or $M_{w,-}$.

The transition function $p_{w}$ depends on the vector $w$ that identifies each MDP in the class, but not on the sign $+$ or $-$. Fix the MDP by fixing $w\in\partial\mathcal{B}^{+}$ (two MDPs correspond to a given choice of $w$). If the agent plays the special action $a^{\star}$, which is only available in the starting state $s^{\star}$, it transitions with probability one to the terminal state $s^{\dagger}$. If the agent plays $a\neq a^{\star}$, the transition function only depends on the action $a$ (and not on the current state $s$) and the successor state is $\overline{s}$ with some probability, and is otherwise the absorbing state $s^{\dagger}$.

Mathematically, if $a=a^{\star}$ then $p_{w}(s^{\dagger}\mid(s^{\star},a^{\star}))=1$ and if conversely $a\in\mathcal{B}^{+}$:

The definition implies that the successor state is always either $\overline{s}$ or the terminal state $s^{\dagger}$.

Reward function

The reward function $r_{w,\pm}$ depends on both the vector $w\in\partial\mathcal{B}^{+}$ and on the sign $+$ or $-$ that identifyies the MDP. It is always $\frac{1}{2}$ if the special action $a^{\star}$ is taken and otherwise it is everywhere on $M_{w,-}$ or is positive only in the spherical cap on $M_{w,+}$. Mathematically:

3 Proof Sketch of Theorem 2 (Batch Lower Bound)

The steps for the proof are the following: we show that 1) $Q^{\star}$ is linear 2) policy-induced queries are also policy-free for this problem 3) using less than exponentially many queries ensures that at least one spherical cap $\mathcal{C}_{\gamma}(\widetilde{w})$ is not probed 4) the corresponding MDPs $M_{\widetilde{w},+}$ and $M_{\widetilde{w},-}$ look the same outside the spherical cap $\mathcal{C}_{\gamma}(\widetilde{w})$ 5) the agent does not have enough information to distinguish $M_{\widetilde{w},+}$ from $M_{\widetilde{w},-}$.

By inspection we can verify realizability.

For any $w\in\partial\mathcal{B}^{+}$ let $Q^{\star}_{w,+}$ and $Q^{\star}_{w,-}$ be the optimal $Q^{\star}$ values on $M_{w,+}$ and $M_{w,-}$, respectively. It holds that

Policy-free vs policy-induced queries

Notice that although the dynamics are different for different $w$’s (that identify the MDP), any set $T$ (Definition 2) induces the same set $\mu$ of state-actions (possibly with the exception of $(s^{\star},a^{\star})$ and $(s^{\dagger},\vec{0})$) regardless of the vector $w$ and the sign $\pm$. We can therefore consider the case that the oracle has chosen a policy-free query set $\mu=\{(s_{i},a_{i})\}_{i=1}^{n}\cup\{(s^{\star},a^{\star}),(s^{\dagger},\vec{0})\}$.

Existence of exponentially many spherical caps

Assume that less than $2^{-d}\mathcal{N}(\gamma,d)$ actions $a_{1},\dots,a_{n}$ on $\mathcal{B}^{+}$ are selected. Then there exists a spherical cap $\mathcal{C}_{\gamma}(\widetilde{w})$ that no action has probed, i.e., $\exists\widetilde{w}\in\partial\mathcal{B}^{+}\text{s.t.}\forall i\in[n],a_{i}\not\in\mathcal{C}_{\gamma}(\widetilde{w})$.

In this case, the agent does not have any information originating from inside the dark gray spherical cap in Fig. 2.

Batch algorithm does not have enough information

The above equation implies that the transitions and the rewards in the dataset could have originated from either $M_{\widetilde{w},+}$ or $M_{\widetilde{w},-}$. In $s^{\star}$, the batch algorithm has two choices to determine the policy $\widehat{\pi}^{\star}_{\mathcal{D}}$ to return: choose action $a^{\star}$ and get a total return of $\frac{1}{2}$ or choose an action $a\neq a^{\star}$. The second choice is $\frac{1}{2}$-suboptimal on $M_{\widetilde{w},-}$, while the first is at least $\frac{1}{2}$-suboptimal on $M_{\widetilde{w},+}$. At best, the batch algorithm can randomize between the two, showing the result.

4 Proof Sketch of Theorem 4 (Online Upper Bound)

It remains to exhibit an online algorithm that can solve every problem instance from this MDP class using $d+1$ queries. The algorithm proceeds as follows: 1) it tries to locate the position of the spherical cap by learning the vector $w$ and 2) it probes the spherical cap to learn the $\pm$ sign of the MDP, precisely identifying the MDP.

Consider the following adaptive algorithm that submits policy-induced queries. The algorithm first plays the actions $\gamma e_{1},\dots,\gamma e_{d}$ in $s^{\star}$ where $e_{i}$ is the vector of all zeros and $1$ in position $i$ (these are $d$ policies that generate trajectories of length one where $\gamma e_{i}$ is the only action).

Upon receiving the transition functions $p_{w}(\overline{s}\mid s^{\star},\gamma e_{i})=\min\{\frac{1}{\gamma}(\gamma e_{i})^{\top}w,1\}=e_{i}^{\top}w$ for all $i\in[d]$ (see Eq. 2), the agent can determine each component of the vector $w$. By construction, $w$ identifies the spherical cap $\mathcal{C}_{\gamma}(w)$.

Identifying the sign ±plus-or-minus\boldsymbol{\pm} of the MDP

Next, the algorithm plays the state-action $(s^{\star},w)$ to probe the spherical cap and observe the reward ($1-\gamma$ on $M_{w,+}$ and on $M_{w,-}$) which identifies the sign of the MDP. Since the MDP is now precisely identified, the agent can predict the value of any policy, and in particular, it can return the optimal policy.

Discussion

This work presents exponential lower bounds for batch RL. In general, models are never correct, observations are noisy, and a batch algorithm needs to return an answer using whatever dataset is available; clearly the lower bounds continue to hold in these more general settings as much as they do when using more general predictors (like neural networks) which contain the linear setting as a special case. As these hard instances can only arise in infinite horizon settings, there is an exponential separation between finite and infinite horizon batch RL.

The strength of our results arise from the ‘oracle + batch algorithm’ protocol which allows us to derive lower bounds for every a priori data distribution; as a special case, we recover the concurrent lower bound of (Wang et al., 2020a) for the infinite horizon setting. We highlight that our lower bounds always imply an infinite sample complexity.

Beyond the exponential lower bounds, an important result is that online exploration may be required to achieve polynomial sample efficiency on certain RL problems. This is surprising, because online RL has the additional exploration burden compared to batch RL with a good dataset.

Finally, this work helps formalize some of the dangers of the deadly triad, which has long been known to cause algorithmic instabilities and divergence of dynamic programming algorithms. In a sense, the bootstrapping problem is for infinite horizon what the extrapolation problem is for finite horizon MDPs (and finite-steps algorithms), but unlike extrapolation, it cannot be mitigated by adding more samples.

Acknowledgment

The author is grateful to Emma Brunskill, Mykel Kochenderfer and Martin Wainwright for providing useful feedback. The author also thanks the reviewers for their helpful and detailed comments. The work was done while the author was visiting the Simons Institute for the Theory of Computing.

References

Appendix A Benefits of the Setup

One of the technical innovation of this work lies in the ‘oracle + batch algorithm’ protocol, which allows us to obtain lower bounds that hold for every distribution that the oracle can choose; this automatically yields lower bounds for fixed distributions as a special case. The key idea is that if the batch algorithm cannot return a good answer for any distribution chosen by the oracle, it certainly cannot return a good answer for an a priori fixed distribution, otherwise the oracle would have chosen it! To formally highlight the strength of the oracle setup, we derive (Wang et al., 2020a)’s lower bound (theorem 4.1 in their paper) for infinite horizon RL as a special case and with an additional remark about infinite data.

There exist an MDP class $\mathcal{M}$ and a feature extractor $\phi$ that satisfy 3 ( ($Q^{\pi}$ is Realizable for every Policy).) together with a target policy $\pi$ and a distribution $\mu=\{(s_{i},a_{i})\}_{i=1}^{n}$ that induces a covariance matrix

such that no algorithm can predict the value of the target policy $\pi$ with probability $>\frac{1}{2}$ and additive error $<1$ (or return a policy with suboptimality $<1$) even in the limit of infinite data (i.e., sampled rewards and transitions) generated from $\mu$.

Consider the MDP class $\mathcal{M}$ described in the proof of theorem 4. Since any feature vector in the unit Euclidean ball is available, simply choose a distribution $\mu$ that samples the feature vectors $e_{1},\dots,e_{d}$ (concretely, we can choose $\mu=\{(s^{\star},e_{1}),\dots,(s^{\star},e_{d})\}$).

Since $\mu$ is a distribution that the oracle could have chosen and consists of just $|\mu|=d\leq\mathcal{N}(\gamma,d)$ queries, apply Theorem 3 ( (Policy-Free Lower Bounds).) to deduce that even if infinite data is generated from $\mu$, no batch algorithm can return the value of $Q^{\pi}(s^{\star},\cdot)$ for some action with additive error $<1$ and with probability $>\frac{1}{2}$; likewise it cannot return a policy with suboptimality error $<1$ from $s^{\star}$ with probability $>\frac{1}{2}$. ∎

In summary, there exist problems where the batch algorithm cannot return a reasonable answer even with infinite data, the best conditioned covariance matrix and a strong representation for the action value function. We highlight that the exponential lower bound in (Wang et al., 2020a)’s construction can potentially be avoided by choosing a better batch distribution since their MDPs are tabular with small state-action spaces; our MDPs are instead much harder and cannot be solved even if one chooses — through an oracle — the best distribution for such problem class. Similar results can be derived for any assumption on the covariance matrix.

Finally, we highlight that all theorems that we present in this work are expressed as a function of the number of state-action queries, i.e., the size of the support of $\mu$, instead of the number of sampled rewards and transitions. This way, if the support of the batch distribution is small $|\mu|\leq 2^{-d}\mathcal{N}(\gamma,d)$ then our theorems ensure that even infinite samples from the state-actions where $\mu$ is supported do not suffice to make accurate predictions, because the batch algorithm already receives the full reward and transition functions in our interaction protocol. As a clarifying example, consider choosing a sampling distribution $\mu$ according to globally-optimal design of experiments (Pukelsheim, 2006), which is an optimal procedure in linear bandits to recover the unknown parameter (Lattimore & Szepesvári, 2020). Design of experiments fails to be effective in our hard instances because it prescribes only $O(d^{2})$ distinct state-actions, i.e., queries, where to (repeatedly) acquire samples, but to escape the lower bound one does not need more samples at the same state-actions; instead the support of the sampling distribution needs to grow.

Appendix B Related Literature

For tabular MDPs one query in each state and action pair with exact feedback is sufficient to identify the MDP. The available results for learning in tabular MDPs consider a similar setting, where only noisy observations are available (Azar et al., 2012; Li et al., 2020; Agarwal et al., 2020b). The algorithms examined by these authors are batch algorithms which specify a uniform distribution over all the state-actions and are minimax optimal. Adaptive algorithms with a generative model (Zanette et al., 2019a; Marjani & Proutiere, 2020) exist but offer little minimax advantage.They can however remove the explicit dependence on the action space from the main rate even in minimax problems, see (Zanette et al., 2019a), section $6$. In the following discussion we primarily consider the function approximation setting with linear value functions.

Polynomial lower bounds are routinely derived to certify that a certain algorithm is sample efficient. For example, (Jiang & Li, 2016) present lower bounds for tabular RL and (Duan & Wang, 2020; Hao et al., 2020) for the linear setting under additional closure assumptions on the Bellman operator. Instead, in this work we are interested in exponential lower bounds.

Dynamic programming algorithms like least-square value and policy iteration (Bradtke & Barto, 1996; Lagoudakis & Parr, 2003) are widely adopted but they are prone to divergence (Baird, 1995; Tsitsiklis & Van Roy, 1996). The hardness of obtaining statistically efficient algorithms has motivated researchers to look for information-theoretic lower bounds. In particular, (Chen & Jiang, 2019) provide a generic lower bound in absence of concentrability; such lower bound does not apply to our setting as we further assume a linear structure. Du et al. (2019) show that if a linear predictor is highly misspecified then an exponential number of queries is needed, and Lattimore et al. (2020) generalize this result through a corollary to show that using $\epsilon$-accurate linear predictors in dimension $d$ can only give $\sqrt{d}\epsilon$-optimal policies for linear bandits and RL. While these results are relevant to our setting, they becomes vacuous in absence of misspecification, i.e., when realizability holds. We examine the relation with concurrent work (Weisz et al., 2020; Wang et al., 2020a; Amortila et al., 2020) in Section 5; however, here we mention that their constructions are easily solvable under our assumptions.

Positive results: upper bounds

When the action value function has a linear parameterization and the transitions are low rank, Yang & Wang (2020); Jin et al. (2020); Zanette et al. (2020a) propose regret-minimizing online algorithms; these works implicitly imply that both the BPI and OPE batch problems are easily solvable under low-rank dynamics. For the more general setting that the value function is closed under the Bellman operator, batch upper bounds for the BPI problem exist (Munos, 2005; Munos & Szepesvári, 2008) and these have been recently generalized to the online setting (Zanette et al., 2020b) with a computationally tractable algorithm (Zanette et al., 2020c); collectively, these works show that online RL can operate under batch assumptions, and our work shows that online RL is in fact exponentially easier than batch RL on certain problems. Minimax results for batch OPE problems are also available (Duan & Wang, 2020) for a setting essentially equivalent to low inherent Bellman error; for the BPI problem see instead (Xie & Jiang, 2020a). Batch methods based on minimizing the Bellman residual also exist (Antos et al., 2008). When the action value function of all policies can be linearly represented Munos (2003); Lazaric et al. (2012); Lattimore et al. (2020); Agarwal et al. (2020c) provide algorithms to learn a good policy using a simulator, and online using stronger conditions (Agarwal et al., 2020a); all these methods are non-batch, and our Theorem 3 rules out the existence of batch algorithms operating under the same assumptions. Other linear models recently considered include (Ayoub et al., 2020; Zhou et al., 2020) and when the Bellman equations are linearly representable up to a low-rank error (Jiang et al., 2017); although the focus of these works is online exploration, learning should be possible in the batch setting as well.

The optimal policy (as opposed to a near optimal one) can be identified if there exists some separation between the best and the second best policy (Du et al., 2020), although a sample complexity proportional to the inverse gap (which can be exponentially small) must be suffered; learning in such setting is also possible with an entirely batch algorithm. Near-convexity also ensures that both the BPI and OPE learning problems are solvable in the batch setting (Zanette et al., 2019b); under exact convexity (Cui & Yang, 2020) give an optimal sample complexity for the BPI problem. Deterministic systems with linear value functions are also learnable (Wen & Van Roy, 2013) in finite horizon, and it is easy to derive a batch algorithm for both the BPI and OPE problem under this assumption. Xie & Jiang (2020b) show that under strong concentrability assumptions the BPI problem is solvable using only realizability and general (non-linear) function approximators and Liu et al. (2020) show how to find the best-in-class solution to the BPI problem while avoiding concetrability for general approximators. Finally, importance sampling estimators (Precup, 2000; Li et al., 2015) make very little assumptions but as such they do not leverage the linear structure of the problem and can exhibit unbounded variance. However, methods to reduce the variance exist (Jiang & Li, 2016; Thomas & Brunskill, 2016; Liu et al., 2018; Xie et al., 2019).

Appendix C Globally Optimal Experimental Design is Not a Good Sampling Strategy in RL

We wonder if the classical globally optimal design of experiment (DoE) (Pukelsheim, 2006) from statistics produces acceptable results in light of our lower bounds, for example, whether it yields a matching exponential upper bound. DoE prescribes a set of states and actions (the design) where to acquire several samples; multiple samples are acquired at the selected state-actions, according to the design. The procedure thus prescribes policy-free queries. In finite horizon DoE is successful: Weisz et al. (2020) conclude that DoE with value iteration can identify a near optimal policy in finite horizon given exponentially many samples.

Dishearteningly, we find that in infinite horizon this is no longer true: in the limit of infinite samples over the feature vectors selected by DoE the learner receives exact feedback, but since DoE always prescribes at most $d(d+1)/2$ distinct vectors where samples are acquired (see (Lattimore & Szepesvári, 2020; Pukelsheim, 2006)), the support of the query set is always at most $d(d+1)/2$ regardless of the number of actual samples along these feature vectors. For large enough $d$ and $\gamma$ close to $1$ we have $d(d+1)/2\leq I_{1-\gamma^{2}}^{-1}(\frac{d-1}{2},\frac{1}{2})$ as the left hand side is polynomial and the right hand side is exponential. In light of Theorem 3, we conclude that even if infinite data are collected over the feature vectors chosen by DoE and all policies have a linear representation, no batch algorithm can output a good policy or estimate the value of another with good enough probability. This happens because traditional DoE fails to account for the effect of bootstrapping, as we explain in Section 4. Thus, in infinite horizon the challenge is much greater than in finite horizon, because a good policy (or the value of a target policy) cannot eventually be learned by just collecting more samples, instead, the support of the sampling distribution needs to grow.

Appendix D Preliminaries

In the proofs for the lower bounds we consider a class $\mathcal{M}$ of MDPs containing MDP instances $M$ with certain properties. Every MDP in the class $\mathcal{M}$ can be identified by a vector $w$ and a sign $+$ or $-$, and is denoted by $M_{w,+}$ or $M_{w,-}$, respectively. We overload the notation slightly and write $M_{w}$ in a statement to indicate the statement holds for both $M_{w,+}$ and $M_{w,-}$. This allows us to write, for example, $\mathcal{M}=\{M_{w,+}\mid w\in\partial\mathcal{B}\}\cup\{M_{w,-}\mid w\in\partial\mathcal{B}\}=\{M_{w}\mid w\in\partial\mathcal{B}\}$.

If $x\in$ we can define the incomplete beta function

which allows us to define the regularized incomplete beta function

Useful bounds are provided in Lemma 3 ( (Upper Bound on $I$).).

D.2 Learning Finite Horizon MDPs with Policy-Free Queries

In this section we describe the process to learn a finite horizon MDPs with a linear representation $Q_{t}^{\pi}(s,a)=\phi_{t}(s,a)^{\top}\theta^{\pi}_{t}$ for the target policy $\pi$ and $Q_{t}^{\star}(s,a)=\phi_{t}(s,a)^{\top}\theta^{\star}_{t}$ for the optimal action-value function, $\forall t\in[H]$. We make the same assumptions as in the main text.

The OPE problem is analogous. The batch algorithm solves the following linear system of equations for $i\in[d]$ at timestep $t$.

D.3 Hypersphere and Hyperspherical Sectors

Fix $b\geq 0$ and define the $b$-hyperspherical cap in direction $w\in\mathcal{B}$ as

and the $b$-hyperspherical sector in direction $w$ as

The following formulas are useful to compute the volume of the hypersphere $\mathcal{B}$ and of a spherical sector $\overset{\triangle}{\mathcal{C}}_{b}(w)$.

The volume of an spherical sector is given by the formula

where the volume of the ball $\mathcal{B}$ is

For the proof, see (Li, 2011) where $\phi$ in their notation is the half-angle of the hypersector and $\sin^{2}\phi=1-\cos^{2}\phi=1-b^{2}$. ∎

D.4 Bounds on the Regularized Incomplete Beta Function

The following upper bound holds true for $\gamma\in(0,1)$ and $d\geq 3$:

We first compute an upper bound on the incomplete Beta function

Notice that $t\leq 1-\gamma^{2}$ and so $1-t\geq\gamma^{2}$ and finally $\frac{1}{1-t}\leq\frac{1}{\gamma^{2}}$. Therefore the following upper bound follows:

It remains to compute a lower bound on the Beta function:

We have $\Gamma(\frac{1}{2})=\sqrt{\pi}$; we thus focus on the ratio

The inequality is Gautschi’s inequality for the gamma function. Therefore, we conclude

The bounds just derived for the beta functions together yield an upper bound on the regularized incomplete beta function:

Using the above result we can derive the following easily interpretable lower bounds.

If $d\geq 5$ then the following lower bounds holds true for $\gamma\in(0,1)$:

Using Lemma 3 we can derive the following crude lower bound for $d\geq 5$

Under the same conditions we have the following lower bound

Appendix E Existence of a Lonely Hyperpherical Cap

Consider a set of $n$ points in the unit ball $\{y_{1},\dots,y_{n}\}\subseteq\mathcal{B}$. In this section we show that if $n$ is less than $N_{\gamma}\approx\left(\frac{1}{1-\gamma}\right)^{d}$ then there exists an hyperspherical cap $\mathcal{C}_{\gamma}(w)$ (identified by its direction $w$) such that none of the $y_{i}$’s is in $\mathcal{C}_{\gamma}(w)$ or its symmetric counterpart $\mathcal{C}_{\gamma}(-w)$. For short, define

Let $\mu=\{y_{1},\dots,y_{n}\}\subseteq\mathcal{B}$ be a collection of $n$ points. If $n<N_{\gamma}$ then there exists a point $\widetilde{w}\in\partial\mathcal{B}$ such that its $\gamma$-spherical cone does not contain any of the $y_{i}$’s, i.e.,

This follows from a geometrical argument; the idea is that the hyperspherical cones around $y_{1},\dots,y_{n}$ with parameter $\gamma$ are not sufficient to cover the whole hypersphere, leaving a “gap”. A point in that gap, which we denoteWe save the notation $\widetilde{w}$ for its normalization, i.e., $\widetilde{w}=\frac{w}{\|w\|_{2}}$. with $w\neq 0$ is not covered by any of the hyperspherical cones $\{\overset{\triangle}{\mathcal{C}}_{\gamma}\left(y_{1}\right),\dots,\overset{\triangle}{\mathcal{C}}_{\gamma}\left(y_{n}\right)\}\subseteq\mathcal{B}$, which in turn means that the hyperspherical cone $\overset{\triangle}{\mathcal{C}}_{\gamma}(w)$ around such point $w$ cannot cover any of the $y$’s.

More formally, consider the hyperspherical cones $\overset{\triangle}{\mathcal{C}}_{\gamma}\left(y_{1}\right),\dots,\overset{\triangle}{\mathcal{C}}_{\gamma}\left(y_{n}\right)$. The volume of their union is at most

where the first equality follows from 1 ( (Volume of a Hyperspherical Sector).). It is easily seen that if $n<N_{\gamma}$ then there must exist a point $w\neq 0,w\in\mathcal{B}$ (in fact, a whole subset of $\mathcal{B}$ of non-zero volume) not covered by any spherical sector around the $y$’s, i.e.,

Now denote with $\widetilde{w}\stackrel{{\scriptstyle def}}{{=}}\frac{w}{\|w\|_{2}}$ its normalization; it follows by definition that $\widetilde{w}\not\in\bigcup_{i=1}^{n}\overset{\triangle}{\mathcal{C}}_{\gamma}(y_{i})$ and $\widetilde{w}\in\partial B$. Consider the spherical cone around $\widetilde{w}$, i.e., consider $\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$. By symmetry we have that none of the $y_{i}$’s can be in $\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$. This is because $\widetilde{w}\not\in\overset{\triangle}{\mathcal{C}}_{\gamma}(y_{i})$ means

which is equivalent to saying $y_{i}\not\in\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$, and this can be repeated for every $i\in[n]$. ∎

We also need the following closely related result in the positive orthant.

Let $\mu=\{y_{1},\dots,y_{n}\}\subseteq\mathcal{B}^{+}$ be a collection of $n$ points. If $n<2^{-d}N_{\gamma}$ then there exists a point $\widetilde{w}\in\partial\mathcal{B}^{+}$ that also satisfies $e^{\top}_{i}\widetilde{w}>0,\;\forall i\in[d]$ such that its $\gamma$-spherical cone does not contain any of the $y_{i}$’s, i.e.,

The proof for the positive orthant (i.e., restricted to $\mathcal{B}^{+}$) is nearly identical to Lemma 4 ( (Existence of a Lonely Hyperspherical Cone).). Consider the hyperspherical sectors intersected with $\mathcal{B}^{+}$, i.e., $\overset{\triangle}{\mathcal{C}}_{\gamma}\left(y_{1}\right)\cap\mathcal{B}^{+},\dots,\overset{\triangle}{\mathcal{C}}_{\gamma}\left(y_{n}\right)\cap\mathcal{B}^{+}$. The volume of their union is at most

From geometry we know that the volume of the hypersphere in its positive orthant is $2^{-d}$ times the volume of the hypersphere:

where the second equality follows from 1 ( (Volume of a Hyperspherical Sector).). It is easily seen that if $n<2^{-d}N_{\gamma}$ then there must exist a whole subset of $\mathcal{B}^{+}$ of non-zero volume not covered by any hyperspherical cone around the $y$’s, which allows us to claim

Now denote with $\widetilde{w}\stackrel{{\scriptstyle def}}{{=}}\frac{w}{\|w\|_{2}}$ its normalization; it follows by definition that $\widetilde{w}\not\in\bigcup_{i=1}^{n}\overset{\triangle}{\mathcal{C}}_{\gamma}(y_{i})$ and $\widetilde{w}\in\partial\mathcal{B}^{+},\;\widetilde{w}^{\top}e_{i}>0,\forall i\in[d]$. Consider the hyperspherical cone around $\widetilde{w}$, i.e., consider $\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$. By symmetry we have that none of the $y_{i}$’s can be in $\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$. This is because $\widetilde{w}\not\in\overset{\triangle}{\mathcal{C}}_{\gamma}(y_{i})$ means

which is equivalent to saying $y_{i}\not\in\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$, and this can be repeated for every $i\in[n]$. Since $\mathcal{C}_{\gamma}(\widetilde{w})\subset\overset{\triangle}{\mathcal{C}}_{\gamma}(\widetilde{w})$, the thesis follows. ∎

Building on Lemma 4 ( (Existence of a Lonely Hyperspherical Cone).), we can actually show there exists two symmetric hyperspherical sectors that do not contain any of $y$’s.

Let $\{y_{1},\dots,y_{n}\}\subseteq\mathcal{B}$ be a collection of $n$ points. If $n<N_{\gamma}/2$ then there exists a point $\widetilde{w}\in\partial\mathcal{B}$ such that the $\gamma$-hyperspherical cones around $\widetilde{w}$ and $-\widetilde{w}$ do not contain any of the $y^{\prime}s$, i.e.,

so in particular, $y_{i}\not\in\mathcal{C}_{\gamma}\left(\widetilde{w}\right)\cup\mathcal{C}_{\gamma}\left(-\widetilde{w}\right),\forall i\in[n]$.

Consider the augmented set $\{y_{1},\dots,y_{n},-y_{1},\dots,-y_{n}\}$. Then Lemma 4 ( (Existence of a Lonely Hyperspherical Cone).) applied to this set ensures that if $2n<N_{\gamma}$ then there exists a point $\widetilde{w}\in\mathcal{B}$ with unit norm $\|\widetilde{w}\|_{2}=1$ such that

and so in particular, $y_{i}\not\in\mathcal{C}_{\gamma}\left(\widetilde{w}\right)\cup\mathcal{C}_{\gamma}\left(-\widetilde{w}\right),\forall i\in[n]$. ∎

Appendix F Proof of Theorem 1

We consider a class $\mathcal{M}$ of MDPs sharing the same state-space $\mathcal{S}$, action space $\mathcal{A}$, discount factor $\gamma$, and transition function $p$. The MDPs differ only in the reward function $r$ and the prescribed target policy. We first describe the state and action space, the discount factor and the transition probabilities, which are fixed across all MDPs in the class $\mathcal{M}$.

Each state $s$ in the state space $\mathcal{S}$ can be identified by a point in the Euclidean ball, i.e., we write $\mathcal{S}=\mathcal{B}$. The starting state is the origin $s^{\star}=\vec{0}\in\mathcal{B}$.

Action space

In each state $s\in\mathcal{S}$ the action set coincides with the unit ball, i.e., $\forall s\in\mathcal{S},\mathcal{A}_{s}=\mathcal{B}$.

Discount factor

The discount factor $\gamma$ is in the interval $(0,1)$.

Feature map

The feature extractor returns the point in the Euclidean ball corresponding to the action chosen in the selected state. Mathematically

Since the available actions are always a subset of $\mathcal{B}$, it is easy to see that the image of the feature map is the set $\mathcal{B}$ and $\|\phi(\cdot,\cdot)\|_{2}\leq 1$ holds.

Transition Function

The transition function is deterministic and is only a function of the action chosen in the current state; it is thus convenient to denote with $s^{+}(a)$ the unique successor state reached upon taking action $a$ (in any state $s$). The successor state is equivalent to the action taken, i.e.,

Since $a\in\mathcal{B}$, we have that $s^{+}(a)\in\mathcal{B}$, which is a valid state, and so the above display identifies a valid transition function.

F.2 Instance of the Class

Every MDP in the class $\mathcal{M}$ can be identified by a vector $w\in\partial\mathcal{B}$ and a sign $+$ or $-$, and is denoted by $M_{w,+}$ or $M_{w,-}$, respectively. We now describe the MDP-specific reward function and target policy.

The target policy depends on the vector $w\in\partial\mathcal{B}$ that identifies the MDP $M_{w}$, but not on the sign $+$ or $-$ that distinguishes $M_{w,+}$ from $M_{w,-}$ (therefore, knowledge of the target policy does not reveal the exact MDP in the class). In addition, the target policy is deterministic. Let $\mathcal{C}_{\gamma}(w)$ be a $\gamma$-hyperspherical cap in direction $w$ (see Definition 3 ( (Hypersphere, hyperspherical cap and hyperspherical sector).)). Then the target policy is defined as

Since $s\in\mathcal{B}$ and $w\in\partial\mathcal{B}$, the linear algebra operations in the above definition are all well defined. In addition, $\text{if}\;s\not\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ we have $\|\frac{1}{\gamma}(s^{\top}w)w\|_{2}=\frac{|s^{\top}w|}{\gamma}\|w\|_{2}\leq\frac{\gamma}{\gamma}\|w\|_{2}=1$ using the definition of hyperspherical cap in Definition 3 ( (Hypersphere, hyperspherical cap and hyperspherical sector).), so $\frac{1}{\gamma}(s^{\top}w)w\in\mathcal{B}$ as well. This means the action chosen by the target policy $\pi_{w}(s)$ lives in $\mathcal{B}$ and it is thus a valid action, so the definition of the target policy in the above display is well posed.

Reward function

The reward function depends on both the vector $w\in\partial\mathcal{B}$ and on the sign $+$ or $-$ identifying the MDP and it is defined as follows:

Notice that this is a valid definition as the linear algebra operations are well defined.

The prescribed target policy is the same on $M_{w,+}$ and $M_{w,-}$. In particular, the two MDPs have identical transition functions but opposite reward functions. In addition, notice that $M_{w,+}=M_{-w,-}$ and $M_{w,-}=M_{-w,+}$.

Since the dynamics are the same for all MDPs $\in\mathcal{M}$, and the oracle has access to each one of them, it must know the dynamics, i.e., the oracle knows how to navigate the environment.

F.3 Realizability

We compute the action value function for each MDP (and its associated policy) in the class, showing realizability.

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

Consider $M_{w,+}$. At all $(s,a)$, $Q_{w,+}$ must satisfy the Bellman evaluation equations for $\pi_{w}$. In particular, consider applying $\mathcal{T}^{\pi_{w}}_{w,+}$ to $Q_{w,+}$

since $s^{+}_{w}(a)=a$ is the only possible successor state. We now evaluate the RHS. Two cases are possible: if $a\not\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ then the reward function is zero and the rhs of the above equation reads

If conversely $a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ then the rhs reads

Thus $Q_{w,+}$ is the action value function of the target policy on $M_{w,+}$.

Similarly we verify that $Q_{w,-}$ solves the Bellman evaluation equation on $M_{w,-}$.

We now evaluate the RHS. Two cases are possible: if $a\not\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ then the reward function is zero and the rhs of the above equation reads

If conversely $a\in\mathcal{C}_{\gamma}(w)\cup\mathcal{C}_{\gamma}(-w)$ then the rhs reads

F.4 Proof of Theorem 1

Consider the MDP class described in Section F.1 and Section F.2. First, from Lemma 7 ( ($Q^{\pi}$ Realizability).) we know that every instance of the OPE problem satisfies 1 ( ($Q^{\pi}$ is Realizable).) with a given feature map $\phi(\cdot,\cdot)$.

Next, we know that the set of query points is induced by one or more policies. However notice that any fixed policy visits the same states regardless of the MDP because the transition function does not depend on the particular MDP at hand. Therefore, the policy-induced query set is also policy-free. Thus, it suffices to do the proof for a policy free query set $\mu$. In addition, the size of the policy-free query set $\mu$ is exactly $n$ since the MDP is deterministic.

From Lemma 6 ( (Existence of two Symmetric Hyperspherical Cones).) we know that if $|\mu|<I^{-1}_{1-\gamma^{2}}(\frac{d-1}{2},\frac{1}{2})$ then $\exists\widetilde{w}\in\partial\mathcal{B}$ such that $\forall(s,a)\in\mu,a\not\in\mathcal{C}_{\gamma}(\widetilde{w})\cup\mathcal{C}_{\gamma}(-\widetilde{w})$. Consider the two associated MDPs $M_{\widetilde{w},+}$ and $M_{\widetilde{w},-}$. Notice that the transition function is by construction identical on $M_{\widetilde{w},+}$ and $M_{\widetilde{w},-}$ (and so is the target policy) while their reward functions are zero at any $(s,a)\in\mu$:

This implies that the reward and transition functions in the dataset could have originated from either $M_{\widetilde{w},+}$ or $M_{\widetilde{w},-}$, and likewise the target policy does not indicate whether the prediction concerns $M_{\widetilde{w},+}$ or $M_{\widetilde{w},-}$.

In $s^{\star}=\vec{0}$ the value of $Q^{\pi_{\widetilde{w}}}(s^{\star},\widetilde{w})$ is $+1$ on $M_{\widetilde{w},+}$ and $-1$ on $M_{\widetilde{w},-}$. The agent has thus two choices: either predict a positive value or a negative one. At best, it can randomize between the two, showing the result.

Appendix G Proof of Theorem 2 and Theorem 4

We consider a class $\mathcal{M}$ of MDPs sharing the same state-space $\mathcal{S}$, action space $\mathcal{A}$ and discount factor $\gamma>0$, but different transition function $p$ and reward function $r$. We first describe the state and action space and the discount factor which are fixed across all MDPs in the class $\mathcal{M}$.

At a high level, each MDP contains a two-armed bandit instance in $s^{\star}$ (the starting state). There, the learner has two choices: either take the special action $a^{\star}$ that leads to the terminal state $s^{\dagger}$ and gives an immediate reward of $\frac{1}{2}$, or take any other action that leads to either an intermediate state $\overline{s}$ or the terminal state $s^{\dagger}$. In any case, the agent never gets back to $s^{\star}$.

The state space can written as the union of three states, a starting state $s^{\star}$, an intermediate state $\overline{s}$ and a terminal state $s^{\dagger}$. Mathematically:

Action space

The action space is as follows. In the starting state $s^{\star}$ the special action $a^{\star}$ is available in addition to any action in $\mathcal{B}^{+}$. In $\overline{s}$, any action in $\mathcal{B}^{+}$ is available. Finally, in the terminal state $s^{\dagger}$ only $\vec{0}\in\mathcal{B}^{+}$ is available. Mathematically:

Discount factor

The discount factor $\gamma$ is in the interval $(0,1)$.

Feature map

For this BPI problem the feature map is the $(d+1)$-dimensional vector defined as follows

We notice that we must have $\|\phi(\cdot,\cdot)\|_{2}\leq 1$ and that the feature map only depends on the action.

G.2 Instance of the Class

Next we describe the MDP-specific transition and reward functions. Every MDP is identified by a vector $w\in\partial\mathcal{B}^{+}$ such that $e_{i}^{\top}w>0,\forall i\in[d]$, and by a $+$ and $-$ sign.

The transition function $p_{w}$ depends on the vector $w$ that identifies each MDP in the class, but not on the sign $+$ or $-$. Fix the MDP by fixing $w$ (two MDPs correspond to a given choice of $w$). If the agent plays the special action $a^{\star}$, which is only available in the starting state $s^{\star}$, it transitions with probability one to the terminal state $s^{\dagger}$. Otherwise, the transition function is only a function of the action and the successor state is $\overline{s}$ with some probability, and is otherwise the absorbing state $s^{\dagger}$.

Mathematically, if $a=a^{\star}$ (which implies $s=s^{\star}$) then

This is a valid definition in $(s^{\star},a^{\star})$. If conversely $a\in\mathcal{B}^{+}$:

Since the probabilities are positive (notice that in particular $a^{\top}w\geq 0$ since $a\in\mathcal{B}^{+}$ and $w\in\mathcal{B}^{+}$) and add up to one, the definition is well posed. In particular, the definition implies that the successor state is always either $\overline{s}$ or the terminal state $s^{\dagger}$:

Reward function

The reward function $r_{w,+}$ or $r_{w,-}$ depends on both the vector $w\in\partial\mathcal{B}^{+}$ and on the sign $+$ or $-$ that identifies the MDP. It is always $\frac{1}{2}$ if the special action $a^{\star}$ is taken and otherwise it is everywhere on $M_{w,-}$ or is positive only in the hyperspherical cap on $M_{w,+}$. Mathematically, it is defined as follows:

$M_{w,+}$ and $M_{w,-}$ have identical transition functions but different reward functions.

The reward functions on $M_{w,+}$ and $M_{w,-}$ differ only when the chosen action is inside the hyperspherical cap $\mathcal{C}_{\gamma}(w)$.

G.3 Realizability

We compute the optimal action value function for each MDP in the class $M$, showing realizability.

For any $w\in\partial\mathcal{B}^{+}$, let $Q^{\star}_{w,+}$ and $Q^{\star}_{w,-}$ be the optimal $Q^{\star}$ values on $M_{w,+}$ and $M_{w,-}$, respectively. Then it holds that

We first consider $M_{w,+}$. On any state $\neq s^{\dagger}$ the optimal policy is to take action $a=w$, achieving a return of $(1-\gamma)$ at every timestep. This way the agent transitions to the state $s=\overline{s}$ and then stays put there playing action $a=w$. This yields a total return of $1$. In the terminal state $s^{\dagger}$ action $\vec{0}$ is the only available and gives a reward of zero with a self loop. Thus:

Now we apply the Bellman operator to $V^{\star}_{w,+}$ to compute the optimal action-value function on $M_{w,+}$.

If $(s,a)\neq(s^{\star},a^{\star})$ and $a\not\in\mathcal{C}_{\gamma}(w)$ then by definition $a^{\top}w<\gamma$ and so

If $(s,a)\neq(s^{\star},a^{\star})$ and $a\in\mathcal{C}_{\gamma}(w)$ then

This shows that the optimal action-value function on $M_{w,+}$ is

which equals $\phi(s,a)^{\top}[w,\frac{1}{2}]$.

Now we reason on $M_{w,-}$. In $s^{\star}$, the optimal policy is play $a^{\star}$ once and transition to the terminal state $s^{\dagger}$. If conversely $s\neq s^{\star}$, the maximum attainable return by any policy is . Thus on $M_{w,-}$ the optimal value function reads

Now we apply the Bellman optimality operator to $V^{\star}_{w,-}$ to obtain the optimal action value function on $M_{w,-}$.

Conversely, if $(s,a)\neq(s^{\star},a^{\star})$

This shows that on $M_{w,-}$ the optimal action value function is

which equals $\phi(s,a)^{\top}[\vec{0},\frac{1}{2}]$. This concludes the proof. ∎

G.4 Proof of Theorem 2

Consider the MDP class described in Section G.1 and Section G.2. First, from Lemma 8 ( ($Q^{\star}$ is Realizable).) we know that every member of the class satisfies 2 ( ($Q^{\star}$ is Realizable).) with a given feature map $\phi(\cdot,\cdot)$.

Notice that any policy $\pi$ induces the same state-actions (possibly with the exception of the singletons $(s^{\star},a^{\star})$ and $(s^{\dagger},\vec{0})$) regardless of the MDP that the learner is interacting with. We can therefore consider the case that the oracle has chosen a policy-free query set $\mu=\{(s,a)\}_{i=1,2,\dots,n}$ of size $n$ in addition to the singletons $(s^{\star},a^{\star})$ and $(s^{\dagger},\vec{0})$ (these singletons do not convey any additional information). Here the $(s,a)$ pairs are the possible state-actions visited by the behavioral policies chosen by the oracle.

From Lemma 5 ( (Existence of a Lonely Spherical Cone in the Positive Orthant).) we know that if $|\mu|<2^{-d}I^{-1}_{1-\gamma^{2}}(\frac{d-1}{2},\frac{1}{2})$ then $\exists\widetilde{w}\in\partial\mathcal{B}^{+}$ such that $e_{i}^{\top}w>0,\forall i\in[d]$ and $\forall(s,a)\in\mu,a\not\in\mathcal{C}_{\gamma}(\widetilde{w})$. Consider the two associated MDPs $M_{\widetilde{w},+}$ and $M_{\widetilde{w},-}$. Notice that the transition function is by construction identical on $M_{\widetilde{w},+}$ and $M_{\widetilde{w},-}$ while their reward functions are zero at any $(s,a)\in\mu$: