Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

By Simon Shaolei Du, Sham M. Kakade, Ruosong Wang, Lin F. Yang. 2019

215 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “In recent work, Zhang et al. (2020); Hansen-Estruch, Zhang, Nair, Yin, and Levine (2022); Ashcraft, Stoler, Ewulum, and Agarwala (2022) connect invariant causal prediction to model-irrelevance state abstractions to learn invariant representations in the Block MDP setting (Du et al., 2019b).”
D4RL: Datasets for Deep Data-Driven Reinforcement Learning (2020, background): “…those from deterministic expert policies, are particularly problematic for offline RL algorithms and may cause divergence both empirically [Fujimoto et al., 2018, Kumar et al., 2019] and theoretically [Munos, 2003, Farahmand et al., 2010, Kumar et al., 2019, Agarwal et al., 2019a, Du et al., 2020].”
DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, methodology): “This proof builds on the existence argument presented in (Du et al., 2020).”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “In fact, it is likely that this assumption is essential for developing efficient algorithms, in view of recent hardness result in Du et al. (2020) that only assumes near-linearity of value functions of MDPs (a special case of Markov games).”
Provably Efficient Exploration in Policy Optimization (2019, background): “See also (Du et al., 2019a; Van Roy & Dong, 2019; Lattimore & Szepesvari, 2019) for a related discussion on the necessity of the linear representation.”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “In particular, in our hard instance the optimal Q-function is exactly linear, while for the hard instance in [Du et al., 2020], the optimal Q-function is only approximately linear.”
Datasets for Data-Driven Reinforcement Learning (2020, background): “…those from deterministic expert policies, are particularly problematic for offline RL algorithms and may cause divergence both empirically [Fujimoto et al., 2018, Kumar et al., 2019] and theoretically [Munos, 2003, Farahmand et al., 2010, Kumar et al., 2019, Agarwal et al., 2019a, Du et al., 2020].”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, methodology): “The condition that the optimal Q-function is only approximately linear is crucial for the correctness of the hardness result in Du et al. [2020] The techniques in [Du et al., 2020] are later generalized to other settings, including [Kumar et al., 2020, Wang et al., 2020, Mou et al., 2020].”
Reinforcement Learning: Theory and Algorithms (2019, result): “The approximation limits with linear function approximation are results from [Du et al., 2019].”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “…sample complexity does not depend on |S| [Li et al., 2011, Wen and Van Roy, 2017, Krishnamurthy et al., 2016, Jiang et al., 2017, Dann et al., 2018, Du et al., 2019b, Feng et al., 2020, Du et al., 2019c, Zhong et al., 2019, Yang and Wang, 2019, Jin et al., 2019, Du et al., 2019a, Roy and Dong,…”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “These works require additional assumptions such as deterministic transitions (Dann et al., 2018), reachability (Misra et al., 2020; Du et al., 2019a), strong Bellman closure (Foster et al., 2020), and strong unsupervised learning oracles (Feng et al., 2020).”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “Algorithm Setting Sample Complexity Computation PCID (Du et al., 2019b) block MDP d4H2K4 ( 1 η4γ2 + 1 ε2 ) Oracle efficient HOMER (Misra et al., 2019) block MDP d8H4K4 ( 1 η3 + 1 ε2 ) Oracle efficient OLIVE (Jiang et al., 2017) low Bellman rank d2H3K ε2 Inefficient Sun et al. (2019) low Witness rank”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, background): “Du et al. [2020] showed that having a good approximate representation for the Q-function, transition kernel, or optimal Q-function is not sufficient for efficient learning, and can still have an exponential sample complexity unless the quality of the approximation is above a certain threshold.”