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

• URL: http://arxiv.org/abs/2010.11895v1
• Date: Thu, 22 Oct 2020 17:32:13 GMT
• Title: What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Authors: Ruosong Wang, Dean P. Foster, Sham M. Kakade
• Abstract summary: offline reinforcement learning seeks to utilize offline (observational) data to guide the learning of sequential decision making strategies. This work focuses on the basic question of what are necessary representational and distributional conditions that permit provable sample-efficient offline reinforcement learning.
• Score: 70.33301077240763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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).

Related papers

• Bi-Level Offline Policy Optimization with Limited Exploration [1.8130068086063336]
  We study offline reinforcement learning (RL) which seeks to learn a good policy based on a fixed, pre-collected dataset. We propose a bi-level structured policy optimization algorithm that models a hierarchical interaction between the policy (upper-level) and the value function (lower-level) We evaluate our model using a blend of synthetic, benchmark, and real-world datasets for offline RL, showing that it performs competitively with state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-10-10T02:45:50Z)
• Offline Reinforcement Learning with Additional Covering Distributions [0.0]
  We study learning optimal policies from a logged dataset, i.e., offline RL, with function approximation. We show that sample-efficient offline RL for general MDPs is possible with only a partial coverage dataset and weak realizable function classes.
  arXiv  Detail & Related papers  (2023-05-22T03:31:03Z)
• Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
  We propose value-based algorithms for offline reinforcement learning (RL) We show an analogous result for vanilla Q-functions under a soft margin condition. Our algorithms' loss functions arise from casting the estimation problems as nonlinear convex optimization problems and Lagrangifying.
  arXiv  Detail & Related papers  (2023-02-05T14:22:41Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  We study offline reinforcement learning (RL) in partially observable Markov decision processes. We propose the underlineProxy variable underlinePessimistic underlinePolicy underlineOptimization (textttP3O) algorithm. textttP3O is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.
  arXiv  Detail & Related papers  (2022-05-26T19:13:55Z)
• Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism [65.46524775457928]
  offline reinforcement learning seeks to utilize offline/historical data to optimize sequential decision-making strategies. We study the statistical limits of offline reinforcement learning with linear model representations.
  arXiv  Detail & Related papers  (2022-03-11T09:00:12Z)
• A Sharp Characterization of Linear Estimators for Offline Policy Evaluation [33.37672297925897]
  offline policy evaluation is a fundamental statistical problem in reinforcement learning. We identify simple control-theoretic and linear-algebraic conditions that are necessary and sufficient for classical methods. Our results provide a complete picture of the behavior of linear estimators for offline policy evaluation.
  arXiv  Detail & Related papers  (2022-03-08T17:52:57Z)
• Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation [74.3002974673248]
  We consider the offline reinforcement learning problem, where the aim is to learn a decision making policy from logged data. offline RL is becoming increasingly relevant in practice, because online data collection is well suited to safety-critical domains. Our results show that sample-efficient offline reinforcement learning requires either restrictive coverage conditions or representation conditions that go beyond complexity learning.
  arXiv  Detail & Related papers  (2021-11-21T23:22:37Z)
• Instabilities of Offline RL with Pre-Trained Neural Representation [127.89397629569808]
  In offline reinforcement learning (RL), we seek to utilize offline data to evaluate (or learn) policies in scenarios where the data are collected from a distribution that substantially differs from that of the target policy to be evaluated. Recent theoretical advances have shown that such sample-efficient offline RL is indeed possible provided certain strong representational conditions hold. This work studies these issues from an empirical perspective to gauge how stable offline RL methods are.
  arXiv  Detail & Related papers  (2021-03-08T18:06:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.