Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

Introduction

Modern reinforcement learning (RL) problems are often challenging due to the huge state space. To tackle this challenge, function approximation schemes are often employed to provide a compact representation, so that reinforcement learning can generalize across states. A common paradigm is to first use a feature extractor to transform the raw input to features (a succinct representation) and then apply a linear predictor on top of the features. Traditionally, the feature extractor is often handcrafted (Sutton & Barto 2018), while more modern methods often train a deep neural network to extract features. The hope of this paradigm is that, if there exists a good low dimensional (linear) representation, then efficient reinforcement learning is possible.

Empirically, combining various RL function approximation algorithms with neural networks for feature extraction has lead to tremendous successes on various tasks (Mnih et al. 2015; Schulman et al. 2015; Schulman et al. 2017). A major problem, however, is that these methods often require a large amount of samples to learn a good policy. For example, deep $Q$-network requires millions of samples to solve certain Atari games (Mnih et al. 2015). Here, one may wonder if there are fundamental statistical limitations on such methods, and, if so, under what conditions it would be possible to efficiently learn a good policy?

In the supervised learning context, it is well-known that empirical risk minimization is a statistically efficient method when using a low-complexity hypothesis space (Shalev-Shwartz & Ben-David 2014), e.g. a hypothesis space with bounded VC dimension. For example, polynomial number of samples suffice for learning a near-optimal $d$-dimensional linear classifier, even in the agnostic setting Here we only study the sample complexity and ignore the computational complexity.. In contrast, in the more challenging RL setting, we seek to understand if efficient learning is possible (say from a sample complexity perspective) when we have access to an accurate (and compact) parametric representation — e.g. our policy class contains a near-optimal policy or our hypothesis class accurately approximates the optimal value function. In particular, this work focuses on the following question:

Is a good representation sufficient for sample-efficient reinforcement learning?

This question has largely been studied only with respect to approximation error in the more classical approximate dynamic programming literature, where it is known that algorithms are stable to certain worst-case approximation errors. With regards to sample efficiency, this question is largely unexplored, where the extant body of literature mainly focuses on conditions which are sufficient for efficient reinforcement learning though there is little understanding of what are necessary conditions for efficient reinforcement learning. In reinforcement learning, there is no direct analogue of empirical risk minimization as in the supervised learning context, and it is not evident what are the statistical limits of learning based on properties of our underlying hypothesis class (which may be value-based, policy-based, or model-based).

Many recent works have provided polynomial upper bounds under various sufficient conditions, and in what follows we list a few examples. For value-based learning, the work of Wen & Van Roy 2013 showed that for deterministic systems MDPs where both reward and transition are deterministic., if the optimal $Q$-function can be perfectly predicted by linear functions of the given features, then the agent can learn the optimal policy exactly with polynomial number of samples. Recent work (Jiang et al. 2017) further showed that if certain complexity measure called Bellman rank is bounded, then the agent can learn a near-optimal policy efficiently. For policy-based learning, Agarwal et al. 2019 gave polynomial upper bounds which depend on a parameter that measures the difference between the initial distribution and the distribution induced by the optimal policy.

Our Contributions. This paper gives, perhaps surprisingly, strong negative results to this question. The main results are exponential lower bounds in terms of planning horizon $H$ for value-based, model-based, and policy-based algorithms with given good representations Our results can be easily extend to infinite horizon MDPs with discount factors by replacing the planning horizon $H$ with $\frac{1}{1-\gamma}$, where $\gamma$ is the discount factor. We omit the discussion on discount MDPs for simplicity. . Notably, the requirements on the representation that suffice for sample efficient RL are even more stringent than the more traditional approximation viewpoint. A comprehensive summary of previous upper bounds and our lower bounds is given in Table 1, and here we briefly summarize our hardness results.

For value-based learning, we show even if $Q$-functions of all policies can be approximated by linear functions of the given representation with approximation error $\delta=\Omega\left(\sqrt{\frac{H}{d}}\right)$ where $d$ is the dimension of the representation and $H$ is the planning horizon, then the agent still needs to sample exponential number of trajectories to find a near-optimal policy.

We show even if optimal policy can be perfectly predicted by a linear function of the given representation with a strictly positive margin, the agent still requires exponential number of trajectories to find a near-optimal policy.

These lower bounds hold even in deterministic systems and even if the agent knows the transition model. Note these negative results apply to the case where the $Q$-function, the model, or the optimal policy can be predicted well by a linear function of the given representation. Since the class of linear functions is a strict subset of many more complicated function classes, including neural networks in particular, our negative results imply lower bounds for these more complex function classes as well. Our results highlight the following conceptual insights:

The requirements on the representation that suffice for sample efficient RL are significantly more stringent than the more traditional approximation viewpoint; our statistical lower bounds show that there are hard thresholds on the worst-case approximation quality of the representation which are not necessary from the approximation viewpoint.

Since our lower bounds apply even when the agent knows the transition model, the hardness is not due to the difficulty of exploration in the standard sense. The unknown reward function is sufficient to make the problem exponentially difficult.

Our lower bounds are not due to the agent’s inability to perform efficient supervised learning, since our assumptions do admit polynomial sample complexity upper bounds if the data distribution is fixed.

Our lower bounds are not pathological in nature and suggest that these concerns may arise in practice. In a precise sense, almost all feature extractors induce a hard MDP instance in our construction (see Section 4.4).

Instead, one interpretation is that the hardness is due to a distribution mismatch in the following sense: the agent does not know which distribution to use for minimizing a (supervised) learning error (see Kakade 2003 for discussion), and even a known transition model is not information-theoretically sufficient to reduce the sample complexity.

Furthermore, our work implies several interesting exponential separations on the sample complexity between: 1) value-based learning with perfect representation and value-based learning with a good-but-not-perfect representation, 2) value-based learning and policy-based learning, 3) policy-based learning and supervised learning and 4) reinforcement learning and imitation learning. We provide more details in Section 5.

Related Work

A summary of previous upper bounds, together with lower bounds proved in this paper, is provided in Table 1. Some key assumptions are formally stated in Section 3 and Section 4. Our lower bounds highlight that classical complexity measures in supervised learning including small approximation error and margin, and standard assumptions in reinforcement learning including optimality gap and deterministic systems, are not enough for efficient RL with function approximation. We need additional assumptions, e.g., ones used in previous upper bounds, for efficient RL.

Existing exponential lower bounds, to our knowledge, construct unstructured MDPs with an exponentially large state space and reduce a bandit problem with exponentially many arms to an MDP (Krishnamurthy et al. 2016; Sun et al. 2017). However, these lower bounds cannot apply to MDPs whose transition models, value functions, or policies can be approximated with some natural function classes, e.g., linear functions, neural networks, etc. The current paper gives the first set of lower bounds for RL with linear function approximation (and thus also hold for super classes of linear functions such as neural networks).

2 Previous Upper Bounds

We divide previous algorithms (with provable guarantees) into three classes: those that utilize uncertainty-based bonuses (e.g. UCB variants or Thompson sampling variants); approximate dynamic programming variants (which often make assumptions with respect to concentrability coefficients); and direct policy search-based methods (such as conserve policy iteration (CPI, see Kakade 2003) or policy gradient methods, which make assumptions with respect to distribution mismatch coefficients). The first class of methods include those based on witness rank, Belman rank, and the Eluder dimension, while the latter two classes of algorithms make assumptions either on concentrability coefficients or on distribution mismatch coefficients (see Agarwal et al. 2019; Scherrer 2014 for discussions).

Uncertainty bonus-based algorithms. Now we discuss existing theoretical results on value-based learning with function approximation. The most relevant work is Wen & Van Roy 2013 which showed in deterministic systems, if the optimal $Q$-function is within a pre-specified function class which has bounded Eluder dimension, for which the class of linear functions is a special case, then the agent can learn the optimal policy using polynomial number of samples. This result has recently been generalized by Du et al. 2019a which can deal with stochastic reward and low variance transition but requires strictly positive optimality gap. As we listed in Table 1, it is an open problem whether the condition that the optimal $Q$-function is linear itself is sufficient for efficient RL.

Li et al. 2011 proposed a $Q$-learning algorithm which requires the Know-What-It-Knows oracle. However, it is in general unknown how to implement such oracle in practice. Jiang et al. 2017 proposed the concept of Bellman Rank to characterize the sample complexity of value-based learning methods and gave an algorithm that has polynomial sample complexity in terms of the Bellman Rank, though the proposed algorithm is not computationally efficient. Bellman rank is bounded for a wide range of problems, including MDP with small number of hidden states, linear MDP, LQR, etc. Later work gave computationally efficient algorithms for certain special cases (Dann et al. 2018; Du et al. 2019a; Yang & Wang 2019b; Jin et al. 2019). Recently, Witness rank, a generalization of Bellman rank to model-based methods, is studied in Sun et al. 2019.

Direct policy search-based algorithms. Stronger guarantees over approximate dynamic programming-based algrithm can be obtained with direct policy search-based methods, where instead of having a bounded concentrability coefficient, one only needs to have a bounded distribution mismatch coefficient. The latter assumption requires the agent to have access to a “good” initial state distribution (e.g. a measure which has coverage over where an optimal policy tends to visit); note that this assumption does not make restrictions over the class of MDPs. There are two classes of algorithms that fall into this category. First, there is Conservative Policy Iteration (Kakade & Langford 2002), along with Policy Search by Dynamic Programming (PSDP) (Bagnell et al. 2004), and other boosting-style of policy search-based methods Scherrer & Geist 2014; Scherrer 2014, which have guarantees in terms of bounded distribution mismatch ratio. Second, more recently, Agarwal et al. 2019 showed that policy gradient styles of algorithms also have comparable guarantees.

Recent extensions. Subsequent to this work, the work by Van Roy & Dong 2019 and Lattimore & Szepesvari 2019 made notable contributions to the misspecified linear bandit problem. In particular, both papers found that Theorem 4.1 in our paper can be extended to the misspecified linear bandit problem and gave upper bounds for this problem showing that our lower bound has tight dependency on $\delta$ and $d$. Lattimore & Szepesvari 2019 further gave an upper bound for the setting where the $Q$-functions of all policies can be approximated by linear functions with small approximation errors and the agent can interact with the environment using a generative model. This upper bound also demonstrates that our lower bound has tight dependency on $\delta$ and $d$.

Preliminaries

Throughout this paper, for a given integer $H$, we use $[H]$ to denote the set $\{0,1,\ldots,H-1\}$.

In this paper we prove lower bounds for deterministic systems, i.e., MDPs with deterministic transition $P$, deterministic reward $R$. In this setting, $P$ and $R$ can be regarded as functions instead of distributions. Since deterministic systems are special cases of general stochastic MDPs, lower bounds proved in this paper still hold for more general MDPs.

2 QQ-function and Optimality Gap

Here, $\rho$ is the smallest reward-to-go difference between the best set of actions and the rest. Recently, Du et al. 2019b gave a provably efficient $Q$-learning algorithm based on this assumption and Simchowitz & Jamieson 2019 showed that with this condition, the agent only incurs logarithmic regret in the tabular setting.

3 Query Models

Here we discuss three possible query oracles interacting with the MDP.

RL: The most basic and weakest query oracle for MDP is the standard reinforcement learning query oracle where the agent can only interact with the MDP by choosing actions and observe the next state and the reward.

Generative Model: A stronger query model assumes the agent can transit to any state (Kearns & Singh 2002; Kakade 2003; Sidford et al. 2018). This query model is available in certain robotic applications where one can control the robot to reach the target state.

Known Transition: The strongest query model considered is that the agent can not only transit to any state, but also knows the whole transition function. In this model, only the reward is unknown.

In this paper, we will prove lower bounds for the strongest Known Transition query oracle. Therefore, our lower bounds also apply to RL and Generative Model query oracles.

Main Results

In this section we formally present our lower bounds. We also discuss proof ideas in Section 4.4.

Here $\delta$ is the approximation error, which indicates the quality of the representation. If $\delta=0$, then $Q$-function can be perfectly predicted by a linear function of $\phi\left(\cdot,\cdot\right)$. In general, $\delta$ becomes smaller as we increase the dimension of $\phi$, since larger dimension usually has more expressive power. When the feature extractor is strong enough, previous papers (Chen & Jiang 2019; Farahmand 2011) assume that linear functions of $\phi$ can approximate the $Q$-function of any policy.

In the theoretical reinforcement learning literature, Assumption 4.2 is often called the (approximate) policy completeness assumption. This assumption is crucial in proving polynomial sample complexity guarantee for value iteration type of algorithms (Chen & Jiang 2019; Farahmand 2011).

The following theorem shows when $\delta=\Omega\left(\sqrt{\frac{H}{d}}\right)$, the agent needs to sample exponential number of trajectories to find a near-optimal policy.

There exists a family of MDPs with $|\mathcal{A}|=2$ and a feature extractor $\phi$ that satisfy Assumption 4.2, such that any algorithm that returns a $1/2$-optimal policy with probability $0.9$ needs to sample $\Omega\left(\min\{|\mathcal{S}|,2^{H},\exp(d\delta^{2}/16)\}\right)$ trajectories.

Note this lower bound also applies to MDPs that satisfy Assumption 4.1, since Assumption 4.2 is strictly stronger. We would like to emphasize that since linear functions is a subclass of more complicated function classes, e.g., neural networks, our lower bound also holds for these function classes. Moreover, in many scenarios, the feature extractor $\phi$ is the last layer of a neural network. Modern neural networks are often over-parameterized, which makes $d$ large. In this case, $d$ is much larger than $H$. Thus, our lower bound holds even if the representation has small approximation error. Furthermore, the assumption that $|\mathcal{A}|=2$ is only for simplicity. Our lower bound can be easily generalized to the case that $|\mathcal{A}|>2$, in which case the sample complexity lower bound is $\Omega\left(\min\{|\mathcal{S}|,|\mathcal{A}|^{H},\exp(d\delta^{2}/16)\}\right)$.

2 Lower Bound for Model-based Learning

It has been shown in Yang & Wang 2019b; Yang & Wang 2019a; Jin et al. 2019 if $\|P\left(\cdot\mid s,a\right)-\langle\psi(\cdot),\phi\left(s,a\right)\rangle\|_{1}$ is bounded, then the problem admits an algorithm with polynomial sample complexity. Now we show that when $\delta=\Omega\left(\sqrt{\frac{H}{d}}\right)$ in Assumption 4.3, the agent needs exponential number of samples to find a near-optimal policy.

There exists a family of MDPs with $|\mathcal{A}|=2$ and a feature extractor $\phi$ that satisfy Assumption 4.3, such that any algorithm that returns a $1/2$-optimal policy with probability $0.9$ needs to sample $\Omega\left(\min\{|\mathcal{S}|,2^{H},\exp(d\delta^{2}/16)\}\right)$ trajectories.

Again, our lower bound can be easily generalized to the case that $|\mathcal{A}|>2$.

3 Lower Bound for Policy-based Learning

Similar to value-based learning, a natural assumption for policy-based learning is that the optimal policy is realizable Unlike value-based learning, it is hard to define completeness on the policy-based learning with function approximation, since not all policy has the $\argmax$ form. , i.e., the optimal policy is linear.

Here we discuss another assumption. For learning a linear classifier in the supervised learning setting, one can reduce the sample complexity significantly if the optimal linear classifier has a margin.

Here we restrict the linear coefficients and features to have unit norm for normalization. Note that Assumption 4.5 is strictly stronger than Assumption 4.4. Now we present our result for linear policy.

There exists an absolute constant $\triangle_{0}$, such that for any $\triangle\leq\triangle_{0}$, there exists a family of MDPs with $|\mathcal{A}|=2$ and a feature extractor $\phi$ that satisfy Assumption 3.1 with $\rho=\frac{1}{2\min\{H,d\}}$ and Assumption 4.5, such that any algorithm that returns a $1/4$-optimal policy with probability at least $0.9$ needs to sample $\Omega\left(\min\{2^{H},2^{d}\}\right)$ trajectories.

Again, our lower bound can be easily generalized to the case that $|\mathcal{A}|>2$.

Compared with Theorem 4.1, Theorem 4.3 is even more pessimistic, in the sense that even with perfect representation with benign properties (gap and margin), the agent still needs to sample exponential number of samples. It also suggests that policy-based learning could be very different from supervised learning.

4 Proof Ideas

All our lower bound are proved based on reductions from the following hard instance. In this instance, both the transition $P$ and the reward $R$ are deterministic. There are $H$ levels of states, which form a full binary tree of depth $H$. There are $2^{h}$ states in level $h$, and thus $2^{H}-1$ states in total. Among all the $2^{H-1}$ states in level $H-1$, there is only one state with reward $R=1$, and for all other states in the MDP, the corresponding reward value $R=0$. Intuitively, to find a $1/2$-optimal policy for such MDPs, the agent must enumerate all possible states in level $H-1$ to find the state with reward $R=1$. Doing so intrinsically induces a sample complexity of $\Omega(2^{H})$. This intuition is formalized in Theorem A.1 using Yao’s minimax principle (Yao 1977).

Lower bound for value-based and model-based learning

Lower bound for policy-based learning.

It is straightfoward to construct a set of feature vectors for the binary tree instance so that Assumption 4.4 holds, even if $d=1$. We set $\phi(s,a)$ to be $+1$ if $a=a_{1}$ and $-1$ if $a=a_{2}$. For each level $h$, for the unique state $s$ in level $h$ with $Q^{*}=1$, we set $\theta_{h}$ to be $1$ if $\pi^{*}(s)=a_{1}$ and $-1$ if $\pi^{*}(s)=a_{2}$. With this construction, Assumption 4.4 holds.

Separations

Perfect representation vs. good-but-not-perfect representation. For value-based learning in deterministic systems, Wen & Van Roy 2013 showed polynomial sample complexity upper bound when the representation can perfectly predict the $Q$-function. In contrast, if the representation is only able to approximate the $Q$-function, then the agent requires exponential number of trajectories. This exponential separation demonstrates a provable exponential benefit of better representation.

Value-based learning vs. policy-based learning. Note that if the optimal $Q$-function can be perfectly predicted by the provided representation, then the optimal policy can also be perfectly predicted using the same representation. Since Wen & Van Roy 2013 showed polynomial sample complexity upper bound when the representation can perfectly predict the $Q$-function, our lower bound on policy-based learning, which applies to perfect representations, thus demonstrates that the ability of predicting the $Q$-function is much stronger than that of predicting the optimal policy.

Supervised learning vs. reinforcement learning. For policy-based learning, if the planning horizon $H=1$, the problem becomes learning a linear classifier, for which there are polynomial sample complexity upper bounds. For policy-based learning, the agent needs to learn $H$ linear classifiers sequentially. Our lower bound on policy-based learning shows the sample complexity dependency on $H$ is exponential.

Imitation learning vs. reinforcement learning. In imitation learning (IL), the agent can observe trajectories induced by the optimal policy (expert). If the optimal policy is linear in the given representation, it can be shown that the simple behavior cloning algorithm only requires polynomial number of samples to find a near-optimal policy (Ross et al. 2011). Our Theorem 4.3 shows if the agent cannot observe expert’s behavior, then it requires exponential number of samples. Therefore, our lower bound shows there is an exponential separation between policy-based RL and IL when function approximation is used.

Acknowledgments

The authors would like to thank Yuping Luo, Wenlong Mou, Martin Wainwright, Mengdi Wang and Yifan Wu for insightful discussions. Also, the authors would also like to gratefully acknowledge Benjamin Van Roy, Shi Dong, Tor Lattimore and Csaba Szepesvári for sharing a draft of their work and their comments. Simon S. Du is supported by NSF grant DMS-1638352 and the Infosys Membership. Sham M. Kakade acknowledges funding from the Washington Research Foundation Fund for Innovation in Data-Intensive Discovery; the NSF award CCF 1740551; and the ONR award N00014-18-1-2247. Ruosong Wang is supported in part by NSF IIS1763562, AFRL CogDeCON FA875018C0014, and DARPA SAGAMORE HR00111990016. Part of this work was done while Simon S. Du was visiting Google Brain Princeton and Ruosong Wang was visiting Princeton University.

References

Appendix A Proofs of Lower Bounds

We first introduce the INDEX-QUERY problem, which will be useful in our lower bound arguments.

In the $\mathsf{INDQ}_{n}$ problem, there is an underlying integer $i^{*}\in[n]$. The algorithm sequentially (and adaptively) outputs guesses $i\in[n]$ and queries whether $i=i^{*}$. The goal is to output $i^{*}$, using as few queries as possible.

For a real number $\delta\in(0,1)$, we say a randomized algorithm $\mathcal{A}$ is $\delta$-correct for $\mathsf{INDQ}_{n}$, if for any underlying integer $i^{*}\in[n]$, with probability at least $1-\delta$, $\mathcal{A}$ outputs $i^{*}$.

The following theorem states the query complexity of $\mathsf{INDQ}_{n}$ for $0.1$-correct algorithms, whose proof is provided in Section B.1.

Any $0.1$-correct algorithm $\mathcal{A}$ for $\mathsf{INDQ}_{n}$ requires at least $0.9n$ queries in the worst case.

In this section we prove Theorem 4.1. We need the following existential result, whose proof is provided in Section B.2.

$\|p_{i}\|_{2}=1$ for all $0\leq i\leq n-1$;

$\left|\langle p_{i},p_{j}\rangle\right|\leq\varepsilon$ for any $0\leq i,j\leq n-1$ with $i\neq j$.

Now we give the construction of the hard MDP instances. We first define the transitions and the reward functions. In the hard instances, both the rewards and the transitions are deterministic. There are $H$ levels of states, and level $h\in[H]$ contains $2^{h}$ distinct states. Thus we have $|\mathcal{S}|=2^{H}-1$. If $|\mathcal{S}|>2^{H}-1$ we simply add dummy states to the state space $\mathcal{S}$. We use $s_{0},s_{1},\ldots,s_{2^{H}-2}$ to name these states. Here, $s_{0}$ is the unique state in level $h=0$, $s_{1}$ and $s_{2}$ are the two states in level $h=1$, $s_{3}$, $s_{4}$, $s_{5}$ and $s_{6}$ are the four states in level $h=2$, etc. There are two different actions, $a_{1}$ and $a_{2}$, in the MDPs. For a state $s_{i}$ in level $h$ with $h<H-1$, playing action $a_{1}$ transits state $s_{i}$ to state $s_{2i+1}$ and playing action $a_{2}$ transits state $s_{i}$ to state $s_{2i+2}$, where $s_{2i+1}$ and $s_{2i+2}$ are both states in level $h+1$. See Figure 1 for an example with $H=3$.

In our hard instances, $r(s,a)=0$ for all $(s,a)$ pairs except for a unique state $s$ in level $H-2$ and a unique action $a\in\{a_{1},a_{2}\}$. It is convenient to define $\overline{r}(s^{\prime})=r(s,a)$, if playing action $a$ transits $s$ to $s^{\prime}$. For our hard instances, we have $\overline{r}(s)=1$ for a unique node $s$ in level $H-1$ and $\overline{r}(s)=0$ for all other nodes.

By construction, for each level $h\in[H]$, there is a unique state $s_{h}$ in level $h$ and action $a_{h}\in\{a_{1},a_{2}\}$, such that $Q^{*}(s_{h},a_{h})=1$. For all other $(s,a)$ pairs such that $s\neq s_{h}$ or $a\neq a_{h}$, it is satisfied that $Q^{*}(s,a)=0$. For a given level $h$ and policy $\pi$, we take $\theta_{h}^{\pi}$ to be $Q^{\pi}(s_{h},a_{h})\cdot\phi(s_{h},a_{h})$. Now we show that $|Q^{\pi}(s,a)-\langle\theta_{h}^{\pi},\phi(s,a)\rangle|\leq\delta$ for all states $s$ in level $h$ and $a\in\{a_{1},a_{2}\}$.

In this case, we have $Q^{\pi}(s,a)=0$ and $\langle\theta_{h}^{\pi},\phi(s,a)\rangle=0$, since $\theta_{h}^{\pi}$ and $\phi(s,a)$ do not have a common non-zero coordinate.

In this case, by the second property of $\mathcal{P}$ in Lemma A.1 and the fact that $Q^{\pi}(s_{h},a_{h})\leq 1$, we have $|\langle\theta_{h}^{\pi},\phi(s,a)\rangle|\leq\delta$. Meanwhile, we have $Q^{\pi}(s,a)=0$.

In this case, we have $\langle\theta_{h}^{\pi},\phi(s,a)\rangle=Q^{\pi}(s_{h},a_{h})$.

Finally, we prove any algorithm that solves these MDP instances and succeeds with probability at least $0.9$ needs to sample at least $\frac{9}{20}\cdot 2^{H}$ trajectories. We do so by providing a reduction from $\mathsf{INDQ}_{2^{H-1}}$ to solving MDPs. Suppose we have an algorithm for solving these MDPs, we show that such an algorithm can be transformed to solve $\mathsf{INDQ}_{2^{H-1}}$. For a specific choice of $i^{*}$ in $\mathsf{INDQ}_{2^{H-1}}$, there is a corresponding MDP instance with

Notice that for all MDPs that we are considering, the transition and features are always the same. Thus, the only thing that the learner needs to learn by interacting with the environment is the reward value. Since the reward value is non-zero only for states in level $H-1$, each time the algorithm for solving MDP samples a trajectory that ends at state $s_{i}$ where $s_{i}$ is a state in level $H-1$, we query whether $i^{*}=i-2^{H-1}+1$ or not in $\mathsf{INDQ}_{2^{H-1}}$, and return reward value 1 if $i^{*}=i-2^{H-1}+1$ and 0 otherwise. If the algorithm is guaranteed to return a $1/2$-optimal policy, then it must be able to find $i^{*}$.

A.2 Proof of Lower Bound for Model-based Learning

We use the same construction as in the proof of Theorem 4.1. Note we just need to verify that the construction satisfies Assumption 4.3. By construction, for all $h\in\{1,2,\ldots,H-1\}$, for each state $s^{\prime}$ in level $h$, there exists a unique $(s,a)$ pair such that playing action $a$ transits $s$ to $s^{\prime}$, and we take $\psi(s^{\prime})=\phi(s,a)$. We also take $\beta_{h}=0$ for $h\in\{0,1,\ldots,H-4,H-3\}$ and $\beta_{H-2}=\phi(s,a)$ where $(s,a)$ is the unique pair with $R(s,a)=1$. Now, according to the design of $\phi(\cdot,\cdot)$ and Lemma A.1, Assumption 4.3 is satisfied. ∎

A.3 Proof of Lower Bound for Policy-based Learning

In this section, we present our hardness results for linear policy learning. We first prove a weaker lower bound which only satisfies Assumption 4.4, and then prove Theoerem 4.3.

Verifying Assumption 4.4.

Recall that for each level $h\in[H]$, there is a unique state $s_{h}$ in level $h$ and action $a_{h}\in\{a_{1},a_{2}\}$, such that $Q^{*}(s_{h},a_{h})=1$. For all other $(s,a)$ pairs such that $s\neq s_{h}$ or $a\neq a_{h}$, it is satisfied that $Q^{*}(s,a)=0$. We simply take $\theta_{h}$ to be $1$ if $a_{h}=a_{1}$, and take $\theta_{h}$ to be $-1$ if $a_{h}=a_{2}$.

Using the same lower bound argument (by reducing INDEX-QUERY to MDPs), we have the following theorem.

There exists a family of MDPs and a feature map $\phi\left(\cdot,\cdot\right)$ that satisfy Assumption 4.4 with $d=1$ and Assumption 3.1 with $\rho=1$, such that any algorithm that returns a $1/2$-optimal policy with probability at least $0.9$ needs to sample $\Omega\left(2^{H}\right)$ trajectories.

Proof of Theoerem 4.3

Now we prove Theoerem 4.3. In order to prove Theoerem 4.3, we need the following geometric lemma whose proof is provided in Section B.3.

Now we are ready to prove Theorem 4.3. In the proof we assume $H=d$, since otherwise we can take $H$ and $d$ to be $\min\{H,d\}$ by decreasing the planning horizon $H$ or adding dummy dimensions to the feature extractor $\phi$.

We define a set of $2^{H-1}$ deterministic MDPs. The transitions of these hard instances are exactly the same as those in Section A.1. The main difference is in the definition of the feature map $\phi(\cdot,\cdot)$ and the reward function. Again in the hard instances, $r(s,a)=0$ for all $s$ in the first $H-2$ levels. Using the terminology in Section A.1, we have $\overline{r}(s)=0$ for all states in the first $H-1$ levels. Now we define $\overline{r}(s)$ for states $s$ in level $H-1$. We do so by recursively defining the optimal value function $V^{*}(\cdot)$. The initial state $s_{0}$ in level $0$ satisfies $V^{*}(s_{0})=1/2$. For each state $s_{i}$ in the first $H-2$ levels, we have $V^{*}(s_{2i+1})=V^{*}(s_{i})$ and $V^{*}(s_{2i+2})=V^{*}(s_{i})-1/2H$. For each state $s_{i}$ in the level $h=H-2$, we have $\overline{r}(s_{2i+1})=V^{*}(s_{i})$ and $\overline{r}(s_{2i+2})=V^{*}(s_{i})-1/2H$. This implies that $\rho=1/2H$. In fact, this implies a stronger property that each state has a unique optimal action. See Figure 2 for an example with $H=3$.

To define $2^{H-1}$ different MDPs, for each state $s$ in level $H-1$ of the MDP defined above, we define a new MDP by changing $\overline{r}(s)$ from its original value to $1$. This also affects the definition of the optimal $V$ function for states in the first $H-1$ levels. In particular, for each level $i\in\{0,1,2,\ldots,H-2\}$, we have changed the $V$ value of a unique state in level $i$ from its original value (at most $1/2$) to $1$. By doing so we have defined $2^{H-1}$ different MDPs. See Figure 3 for an example with $H=3$.

We now show that all the $2^{H-1}$ MDPs constructed above satisfy the linear policy assumption. Namely, we show that for any state $s$ in level $H-1$, after changing $\overline{r}(s)$ to be 1, the resulting MDP satisfies the linear policy assumption. As in Section A.1, for each level $h\in[H]$, there is a unique state $s_{h}$ in level $h$ and action $a_{h}\in\{a_{1},a_{2}\}$, such that $Q^{*}(s_{h},a_{h})=1$. For all other $(s,a)$ pairs such that $s\neq s_{h}$ or $a\neq a_{h}$, it is satisfied that $Q^{*}(s,a)=0$. For each level $h$, if $a_{h}=a_{1}$, then we take $(\theta_{h})_{H/2}=1$ and $(\theta_{h})_{H}=-1$, and all other entries in $\theta_{h}$ are zeros. If $a_{h}=a_{2}$, we use $\overline{p}$ to denote the vector formed by the first $H/2$ coordinates of $\phi(s_{h},a_{2})$. By construction, we have $\overline{p}\in\overline{\mathcal{P}}$. We take $\theta_{h}=[\omega_{\overline{p}};0]$ in this case. In any case, we have $\|\theta_{h}\|_{2}\leq\sqrt{2}$. Now for each level $h$, if $a_{h}=a_{1}$, then for all states $s$ in level $h$, we have $\pi^{*}(s)=a_{1}$. In this case, $\langle\phi(s,a_{1}),\theta_{h}\rangle=1$ and $\langle\phi(s,a_{2}),\theta_{h}\rangle=-1$ for all states in level $h$, and thus Assumption 4.5 is satisfied. If $a_{h}=a_{2}$, then $\pi^{*}(s_{h})=a_{2}$ and $\pi^{*}(s)=a_{1}$ for all states $s\neq s_{h}$ in level $h$. By construction, we have $\langle\theta_{h},\phi(s,a_{1})\rangle=0$ for all states $s$ in level $h$, since $\theta_{h}$ and $\phi(s,a_{1})$ do not have a common non-zero entry. We also have $\langle\theta_{h},\phi(s_{h},a_{2})\rangle\geq 2\triangle$ and $\langle\theta_{h},\phi(s,a_{2})\rangle\leq-2\triangle$ for all states $s\neq s_{h}$ in level $h$. Finally, we normalize all $\theta_{h}$ and $\phi(s,a)$ so that they all have unit norm. Since $\|\phi(s,a)\|_{2}=\sqrt{2}$ for all $(s,a)$ pairs before normalization, Assumption 4.5 is still satisfied after normalization.

Finally, we prove any algorithm that solves these MDP instances and succeeds with probability at least $0.9$ needs to sample at least $\Omega(2^{H})$ trajectories. We do so by providing a reduction from $\mathsf{INDQ}_{2^{H-1}}$ to solving MDPs. Suppose we have an algorithm for solving these MDPs, we show that such an algorithm can be transformed to solve $\mathsf{INDQ}_{2^{H-1}}$. For a specific choice of $i^{*}$ in $\mathsf{INDQ}_{2^{H-1}}$, there is a corresponding MDP instance with

Notice that for all MDPs that we are considering, the transition and features are always the same. Thus, the only thing that the learner needs to learn by interacting with the environment is the reward value. Since the reward value is non-zero only for states in level $H-1$, each time the algorithm for solving MDP samples a trajectory that ends at state $s_{i}$ where $s_{i}$ is a state in level $H-1$, we query whether $i^{*}=i-2^{H-1}+1$ or not in $\mathsf{INDQ}_{2^{H-1}}$, and return reward value 1 if $i^{*}=i-2^{H-1}+1$ and it original reward value otherwise. If the algorithm is guaranteed to return a $1/4$-optimal policy, then it must be able to find $i^{*}$.

Appendix B Technical Proofs

The proof is a straightforward application of Yao’s minimax principle Yao 1977. We provide the full proof for completeness.

Consider an input distribution where $i^{*}$ is drawn uniformly at random from $[n]$. Suppose there is a $0.1$-correct algorithm for $\mathsf{INDQ}_{n}$ with worst-case query complexity $T$ such that $T<0.9n$. By averaging, there is a deterministic algorithm $\mathcal{A}^{\prime}$ with worst-case query complexity $T$, such that

We may assume that the sequence of queries made by $\mathcal{A}^{\prime}$ is fixed. This is because (i) $\mathcal{A}^{\prime}$ is deterministic and (ii) before $\mathcal{A}^{\prime}$ correctly guesses $i^{*}$, all responses that $\mathcal{A}^{\prime}$ receives are the same (i.e., all guesses are incorrect). We use $S=\{s_{1},s_{2},\ldots,s_{m}\}$ to denote the sequence of queries made by $\mathcal{A}^{\prime}$. Notice that $m$ is the worst-case query complexity of $\mathcal{A}^{\prime}$. Suppose $m<0.9n$, there exist $0.1n$ distinct $i\in[n]$ such that $\mathcal{A}^{\prime}$ will never guess $i$, and will be incorrect if $i^{*}$ equals $i$, which implies

B.2 Proof of Lemma A.1

We need the following tail inequality for random unit vectors, which will be useful for the proof of Lemma A.1.

In particular, when $\beta\geq 6$,we have

It is clear that $\|q_{i}\|_{2}=1$ for all $i\in[n]$, since each $q_{i}$ is drawn from the unit sphere. We now prove that for any $i,j\in[n]$ with $i\neq j$, with probability at least $1-\frac{1}{n^{2}}$, we have $\left|\langle q_{i},q_{j}\rangle\right|\leq\varepsilon$. Notice that this is sufficient to prove the lemma, since by a union bound over all the $\binom{n}{2}=n(n-1)/2$ possible pairs of $(i,j)$, this implies that $\mathcal{Q}$ satisfies the two desired properties with probability at least $1/2$.

B.3 Proof of Lemma A.2

To prove the lemma, it suffices to show that $\mathcal{N}$ satisfies the property $equation~\ref{eqn:dist}$. Consider a point $x\in\mathcal{N}$, let $A$ be a hyperplane that is perpendicular to $x$ (notice that $x$ is a also a vector) and separates $x$ and every other points in $\mathcal{N}$. We let the distance between $x$ and $A$ be the largest possible, i.e., $A$ contains a point in $\mathcal{N}\backslash\{x\}$. Since $x$ is on the unit sphere and $\mathcal{N}$ is a $\sqrt{\epsilon}$-packing, we have that $x$ is at least $\sqrt{\epsilon}$ away from every point on the spherical cap not containing $x$, defined by the cutting plane $A$. More formally, let $b$ be the intersection point of the line segment $ox$ and $A$. Then

where $z\in\mathcal{N}\cap A$. Notice that the distance between $x$ and the convex hull of $\mathcal{N}\backslash\{x\}$ is lower bounded by the distance between $x$ and $A$, which is given by $|bx|$. Consider the triangles defined by $x,z,o,b$. We have $bz\perp ox$ (note that $bz$ lies inside $A$). By Pythagorean theorem, we have

Solve the above three equations for $|bx|$, we have

Appendix C Exact Linear Q∗Q^{*} + Gap in Generative Model

In this section we present and prove the following theorem.

We first describe the algorithm. For each level, the agent first construct a barycentric spanner $\Lambda_{h}\triangleq\left\{\phi(s_{h}^{1},a_{h}^{1}),\ldots\phi(s_{h}^{d},a_{h}^{d})\right\}\subset\Phi_{h}\triangleq\left\{\phi\left(s,a\right)\right\}_{s\in\mathcal{S}_{h},a\in\mathcal{A}}$ (Awerbuch & Kleinberg 2008). We have the property that any $\phi(s,a)$ with $s_{h}\in\mathcal{S}_{h},a\in\mathcal{A}$, we have $c_{s,a}^{1},\ldots,c_{s,a}^{d}\in$ such that $\phi(s,a)=\sum_{i=1}^{d}c_{s,a}^{i}\phi(s_{h}^{i},a_{h}^{i})$.

The algorithm learns the optimal policy from $h=H-1,\ldots,0$. At any level $h$, we assume the agent has learned the optimal policy $\pi_{h^{\prime}}^{*}$ at level $h^{\prime}=h+1,\ldots,H-1$.

Appendix D Linear QπQ^{\pi} for all π\pi in Generative Model

In this section we present and prove the following theorem.

Now we can bound the sub-optimality of $\hat{\pi}\triangleq\pi_{0}\circ\cdots\circ\pi_{H-1}$: