What are the Statistical Limits of Offline RL with Linear Function Approximation?

By Ruosong Wang, Dean Phillips Foster, Sham M. Kakade. 2020

175 citations recorded by the source corpus.

Offline reinforcement learning seeks to utilize offline (observational) data to guide the learning of (causal) sequential decision making strategies. The hope is that offline reinforcement learning coupled with function approximation methods (to deal with the curse of dimensionality) can provide a means to help alleviate the excessive sample complexity burden in modern sequential decision making problems. However, the extent to which this broader approach can be effective is not well understood, where the literature largely consists of sufficient conditions. This work focuses on the basic question of what are necessary representational and distributional conditions that permit provable sample-efficient offline reinforcement learning. Perhaps surprisingly, our main result shows that even if: i) we have realizability in that the true value function of \emph{every} policy is linear in a given set of features and 2) our off-policy data has good coverage over all features (under a strong spectral condition), then any algorithm still (information-theoretically) requires a number of offline samples that is exponential in the problem horizon in order to non-trivially estimate the value of \emph{any} given policy. Our results highlight that sample-efficient offline policy evaluation is simply not possible unless significantly stronger conditions hold; such conditions include either having low distribution shift (where the offline data distribution is close to the distribution of the policy to be evaluated) or significantly stronger representational conditions (beyond realizability).

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

Citations in the corpus

Offline RL Without Off-Policy Evaluation (2021, methodology): “Another idea, proposed by [Wang et al., 2018, Siegel et al., 2020, Wang et al., 2020b, Chen et al., 2020] is to modify an imitation learning algorithm either by ﬁltering or weighting the observed actions to incentivize policy improvement.”
A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting (2020, unknown): “Wang et al. (2020) recently showed that in finite-horizon batch RL, the sample complexity of evaluating a given policy π has an information-theoretic lower bound that is exponential in the horizon, even if realizable linear features are given (i.e., ϕ : S × A → Rd such that Qπ(·) = 〈ϕ(·), θπ〉 for…”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…Laroche et al., 2019; Jaques et al., 2019; Wu et al., 2019; Kumar et al., 2019; 2020; Agarwal et al., 2020b; Yu et al., 2020; Kidambi et al., 2020; Wang et al., 2020c; Siegel et al., 2020; Nair et al., 2020; Liu et al., 2020) demonstrate the empirical success of various algorithms, which fall…”
Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error (2022, background): “Several recent papers examined the sample complexity of offline RL, noting that without access to on-policy data, the number of necessary transitions is exponential with respect to the horizon (Wang et al., 2020; Zanette, 2021; Chen et al., 2021; Xiao et al., 2021).”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, unknown): “(P, gapmin) in Wang et al. [2022]. In their setting, P stands for a uniform optimal policy coverage coefficient in the tabular MDP, which is analogous to our σ̃−1 h,φ in the linear function approximation setting.”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, background): “Prior works have shown that even if one is given the magic representation that exactly linearizes the optimal policy (Du et al., 2019b) or the optimal value functions (Wang et al., 2020; Weisz et al., 2021), RL is still challenging (i.e., one may still need exponentially many samples to learn).”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “With regards to necessary conditions for sample efficient offline RL, [Wang et al., 2020] proves that offline RL is impossible, under only the weaker assumptions of realizability and feature coverage.”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “Assumptions on Batch Dataset One of the main challenges in offline RL is the insufficient coverage of the dataset caused by lack of online exploration [54]–[56] and in particular the distribution shift in which the occupancy density of the behavior policy and the one induced by the learned policy ar”
Instabilities of Offline RL with Pre-Trained Neural Representation (2021, background): “Polynomial sample complexity results are also obtained under the realizability assumption, albeit under coverage conditions Xie and Jiang [2020] or stringent distribution shift conditions [Wang et al., 2021].”