Source-linked AI summary
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Simon S. Du, Sham M. Kakade, Ruosong Wang, Lin F. Yang
TL;DR
The paper asks whether compact, accurate representations suffice for statistically efficient reinforcement learning, a question with limited prior study. It develops exponential lower bounds for value-based, model-based, and policy-based methods, showing that representation requirements are more stringent than approximation-focused analyses suggest.
Problem
The paper investigates whether efficient reinforcement learning is possible when accurate, compact parametric representations are available, addressing a largely unexplored statistical question.
Method
The paper constructs hard MDP instances and feature representations satisfying natural approximation assumptions, using approximate-rank arguments and modified binary-tree rewards to establish lower bounds.
Results
Exponential lower bounds in planning horizon H hold for value-based, model-based, and policy-based algorithms even with good representations.
Takeaways & Limitations
A good representation alone is insufficient for sample-efficient reinforcement learning under these representational conditions; the required approximation quality is more stringent than traditional approximation analyses indicate.
Takeaways & Limitations
The analysis studies sample complexity while ignoring computational complexity, and its stated setting includes MDPs with deterministic rewards and transitions.
Abstract
from arXiv · showhide
Modern deep learning methods provide effective means to learn good representations. However, is a good representation itself sufficient for sample efficient reinforcement learning? This question has largely been studied only with respect to (worst-case) approximation error, in the more classical approximate dynamic programming literature. With regards to the statistical viewpoint, this question is largely unexplored, and the extant body of literature mainly focuses on conditions which permit sample efficient reinforcement learning with little understanding of what are necessary conditions for efficient reinforcement learning. This work shows that, from the statistical viewpoint, the situation is far subtler than suggested by the more traditional approximation viewpoint, where the requirements on the representation that suffice for sample efficient RL are even more stringent. Our main results provide sharp thresholds for reinforcement learning methods, showing that there are hard limitations on what constitutes good function approximation (in terms of the dimensionality of the representation), where we focus on natural representational conditions relevant to value-based, model-based, and policy-based learning. These lower bounds highlight that having a good (value-based, model-based, or policy-based) representation in and of itself is insufficient for efficient reinforcement learning, unless the quality of this approximation passes certain hard thresholds. Furthermore, our lower bounds also imply 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.
1 INTRODUCTION
This paper asks whether an accurate compact representation is sufficient for sample-efficient reinforcement learning and answers with strong negative results. It establishes exponential sample-complexity lower bounds for value-based, model-based, and policy-based learning even when the relevant functions or policies are well represented.
- Motivation: Deep RL methods can learn effective representations yet often require large datasets, motivating fundamental questions about statistically efficient policy learning.The paper contrasts millions of samples required by some Atari applications with the sample efficiency of low-complexity supervised learning.
- Motivation: The statistical necessity of a good representation remains less understood than worst-case approximation error and sufficient-condition analyses.Prior work largely established stability to approximation error and polynomial upper bounds under selected assumptions, rather than necessary conditions.
- Contributions: The paper gives exponential lower bounds in planning horizon H for value-based, model-based, and policy-based algorithms with good representations.These results show that representation requirements for sample-efficient RL are more stringent than those suggested by the traditional approximation viewpoint.
- Model-based learning: For model-based learning, approximating transitions and rewards linearly still permits exponential trajectory requirements for near-optimal policy learning.The lower bound applies even when the approximation is measured in the ℓ∞ sense.
- Policy-based learning: Even a perfectly linearly predictable optimal policy with a strictly positive margin can require exponentially many trajectories, yielding separations across learning settings.The separations include perfect versus imperfect value representations, value-based versus policy-based learning, policy-based versus supervised learning, and reinforcement versus imitation learning.
2 RELATED WORK
Prior work established exponential lower bounds for unstructured MDPs and polynomial guarantees under several structural assumptions. This paper positions its results as the first exponential lower bounds for RL with linear function approximation, showing that common approximation conditions are insufficient.
- Implications: The results show that small approximation error, margin, optimality gap, and deterministic systems alone do not ensure efficient RL with function approximation.
- Previous lower bounds: Earlier exponential lower bounds used unstructured MDPs or reductions from bandits with exponentially many arms.
- This paper: The paper gives the first lower bounds for RL with linear function approximation, and therefore also for larger classes such as neural networks.
- Previous upper bounds: Existing algorithms obtain polynomial sample complexity under assumptions involving Eluder dimension, Bellman rank, concentrability, or distribution mismatch.
- Recent extensions: Subsequent work extended the value-based lower bound to misspecified linear bandits and established tight dependence on δ and d in related settings.
3 PRELIMINARIES
The preliminaries define finite-horizon MDPs, Q-functions, optimality gaps, and three interaction models. Lower bounds proved under the strongest Known Transition oracle consequently apply to weaker RL and Generative Model oracles.
- MDP setup: An MDP consists of states, actions, horizon H, transitions, and rewards, with the objective of maximizing expected total reward.
- Deterministic systems: The paper proves lower bounds for deterministic systems, which remain valid for general stochastic MDPs because deterministic systems are special cases.
- Q-functions: The Q-function represents expected reward-to-go for a policy at a given level and state-action pair.
- Optimality gap: The optimality gap assumption requires every suboptimal action to differ from the best action by at least ρ.
- Query oracles: The three query models are RL, Generative Model, and Known Transition, ordered from weakest to strongest access.
- Query-oracle consequence: Because the lower bounds hold for Known Transition, they also apply to RL and Generative Model query oracles.
4 MAIN RESULTS
The main results establish exponential-in-H lower bounds for value-based, model-based, and policy-based learning despite strong representation assumptions. They show that approximation quality, margins, and optimality gaps must satisfy stricter thresholds for efficient RL.
- Value-based learning: Value-based learning can require exponentially many trajectories even when all policy Q-functions are approximately represented by linear functions.
- Value-based learning: The value-based lower bound still applies to neural networks and can hold when the representation has small approximation error.
- Model-based learning: Model-based learning can require exponentially many samples under the approximate linear transition assumption.
- Model-based learning: Polynomial guarantees under stronger total-variation transition approximation do not contradict the lower bound for the weaker ℓ∞ condition.
- Policy-based learning: Policy-based learning requires exponentially many samples even when the optimal policy is linear and has a positive margin.
- Proof ideas: The hard instances use a deterministic binary tree with one rewarding terminal state, forcing exploration of exponentially many possible paths.
- Proof ideas: For value- and model-based bounds, approximate-rank constructions produce features satisfying the stated assumptions, and random feature extractors often induce hard instances.
- Proof ideas: For policy-based bounds, separated unit vectors and a modified reward function create unique optimal actions while preserving exponential hardness.
5 SEPARATIONS
The paper establishes exponential sample-complexity separations between perfect and imperfect value representations, value-based and policy-based learning, and reinforcement learning versus supervised or imitation learning.
- Perfect representation vs. good-but-not-perfect representation: Perfect Q-function prediction permits polynomial sample complexity, whereas merely approximate Q-function prediction can require exponentially many trajectories.This yields an exponential benefit for a perfect representation in deterministic systems.
- Value-based learning vs. policy-based learning: Perfect Q-function prediction is stronger than predicting the optimal policy, because policy-based learning remains exponentially hard even with perfect representations.An optimal Q-function representation can also represent the optimal policy, but the converse does not avoid the lower bound.
- Supervised learning vs. reinforcement learning: Policy-based learning requires learning H linear classifiers sequentially, producing exponential sample-complexity dependence on the planning horizon.When H = 1, the problem reduces to linear classification with polynomial sample-complexity upper bounds.
- Imitation learning vs. reinforcement learning: Imitation learning can use expert trajectories and polynomial-sample behavior cloning, while policy-based reinforcement learning without expert behavior requires exponentially many samples.This establishes an exponential separation between policy-based RL and imitation learning with function approximation.
A PROOFS OF LOWER BOUNDS
The proof appendix reduces a query-identification problem to reinforcement-learning hardness and establishes a linear worst-case query lower bound for reliable identification.
- INDEX-QUERY: The appendix introduces INDEX-QUERY, where an adaptive algorithm guesses an unknown integer and receives equality-query answers.The goal is to identify the hidden integer using as few queries as possible.
- δ-correct algorithms: A δ-correct INDEX-QUERY algorithm must output the hidden integer with probability at least 1 − δ for every possible underlying integer.This definition formalizes the reliability requirement used in the reduction.
- Query lower bound: 0.1-correct INDEX-QUERY algorithms require at least 0.9n queries in the worst case.The theorem supplies the query-complexity lower bound used by the subsequent MDP reductions.
A.1 PROOF OF LOWER BOUND FOR VALUE-BASED LEARNING
The value-based lower-bound proof constructs deterministic, layered MDPs with fixed transitions and features, then reduces INDEX-QUERY to finding the uniquely rewarded terminal node.
- Hard MDP construction: The hard MDPs contain H levels with 2^h states at level h, yielding 2^H − 1 states before any dummy states are added.There are two actions, and the transitions and rewards are deterministic.
- Hard MDP construction: Rewards are zero everywhere except at one state-action pair, equivalently one uniquely rewarded node at level H − 1.The unknown location of this reward creates the identification challenge.
- Feature construction: The feature map uses nearly orthogonal vectors in separate action blocks, with representation dimension constrained by d ≥ 2 · ⌈8 ln 2 · H/δ^2⌉.The construction invokes a vector set whose distinct inner products have magnitude at most ε.
- Representation verification: For each level, exactly one state-action pair has Q∗ = 1 while all other pairs have Q∗ = 0, and the constructed approximation error is at most δ.The verification chooses θπ proportional to the relevant feature vector.
- Reduction: 9/20 · 2^H trajectories suffice as a lower-bound threshold because each sampled terminal state answers one INDEX-QUERY equality question.The reduction maps the unknown INDEX-QUERY integer to the location of the unique reward.
A.2 PROOF OF LOWER BOUND FOR MODEL-BASED LEARNING
The model-based lower-bound proof reuses the hard construction and verifies its transition-representation assumption by assigning successor features to predecessor state-action features.
- Transition representation: For every nonterminal successor state, the construction assigns ψ(s′) to the feature of its unique predecessor state-action pair.The proof sets β_h = 0 at earlier levels and assigns the unique rewarding feature at level H − 2.
A.3 PROOF OF LOWER BOUND FOR POLICY-BASED LEARNING
The proof constructs deterministic hard MDP families showing exponential trajectory requirements even when optimal policies admit linear prediction with a positive margin. Geometric feature constructions separate many instances while preserving the policy representation assumptions.
- Hard-instance construction: The proof constructs 2^H−1 deterministic MDPs sharing transitions while varying rewards at level H−1.Each modified reward changes optimal values at earlier levels, producing exponentially many instances.
- Representation construction: The hard instances satisfy linear policy assumptions, including the stronger positive-margin condition, through separated feature vectors and level-specific linear predictors.A geometric packing supplies vectors whose separating hyperplanes distinguish the optimal actions.
- Lower bound: Ω(2^H) trajectories are required for algorithms that solve the constructed MDPs with probability at least 0.9.The lower bound follows by reducing INDQ2^H−1 to MDP solving.
- Reduction: The reduction works because transitions and features are fixed across MDPs, so interaction must identify the unknown reward location.Rewards are nonzero only at states in level H−1, making trajectory sampling equivalent to indexed queries.
B.1 PROOF OF THEOREM A.1
The proof establishes its query lower bound using Yao’s minimax principle and randomized geometric constructions. Random unit vectors yield many well-separated points, which support the required packing argument.
- Query lower bound: Yao’s minimax principle reduces the randomized query lower bound to analyzing a deterministic algorithm under a uniform hidden-index distribution.If fewer than 0.9n queries are made, at least 0.1n indices are never queried, preventing 0.9 correctness.
- Random-vector construction: A set of n independent random unit vectors in dimension d = ⌈8 ln n/ε^2⌉ has pairwise inner products at most ε with probability at least 1/2.The argument combines a random-vector tail bound with a union bound over all pairs.
- Geometric lemma: A √ε-packing of the unit sphere contains Ω(1/ε^(d/2)) points, and each point remains separated from the convex hull of the others.The proof uses a perpendicular separating hyperplane and a right-triangle calculation.
C EXACT LINEAR Q∗+ GAP IN GENERATIVE MODEL
Under exact linear Q∗ representation with a positive gap, the generative-model proof learns policies level by level. Barycentric spanners support Q-value estimation, and the induced policy remains optimal.
- Guarantee: Theorem C.1 states that the optimal policy can be found with polynomially many queries under the stated assumptions.The guarantee holds with probability 1−δ for a given failure probability δ > 0.
- Estimation: At each level, the agent queries feature vectors and estimates Q∗ using unbiased rollout rewards and concentration bounds.Barycentric spanners reduce estimation to a bounded set of feature queries, while Hoeffding’s inequality controls averages.
- Algorithm: The algorithm learns the optimal policy from level H−1 down to level 0.At each level it assumes policies at later levels have already been learned.
- Correctness: The estimated Q-function induces the same policy as π∗ when its error is below half the representation gap.The proof then propagates correctness backward by induction across levels.
D LINEAR Qπ FOR ALL π IN GENERATIVE MODEL
The generative-model result extends the level-by-level algorithm to settings where every policy’s Q-function is linearly represented. The analysis controls local suboptimality and aggregates it into an ϵ-optimal policy.
- Theorem: Theorem D.1 gives an algorithm that finds an ϵ-optimal policy under Assumption 4.2 in the generative-model query model.The theorem assumes δ = 0 and provides a polynomial trajectory guarantee.
- Algorithm: The algorithm is the same as in Theorem C.1, learning policies backward from level H−1 to level 0.The difference is in the analysis for policy-dependent Q-functions.
- Per-level guarantee: At each level, the learned policy is only ϵ/H-suboptimal relative to the optimal policy for the fixed rollout policy.The per-level guarantee holds with probability 1−0.01/H using polynomially many samples.
- Global guarantee: The final policy is formed by composing the policies learned at all levels and recursively bounding its total suboptimality.The proof applies the per-level error bound backward through the policy composition.