Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL

By Andrea Zanette. 2020

75 citations recorded by the source corpus.

Several practical applications of reinforcement learning involve an agent learning from past data without the possibility of further exploration. Often these applications require us to 1) identify a near optimal policy or to 2) estimate the value of a target policy. For both tasks we derive \emph{exponential} information-theoretic lower bounds in discounted infinite horizon MDPs with a linear function representation for the action value function even if 1) \emph{realizability} holds, 2) the batch algorithm observes the exact reward and transition \emph{functions}, and 3) the batch algorithm is given the \emph{best} a priori data distribution for the problem class. Furthermore, if the dataset does not come from policy rollouts then the lower bounds hold even if the action-value function of \emph{every} policy admits a linear representation. If the objective is to find a near-optimal policy, we discover that these hard instances are easily solved by an \emph{online} algorithm, showing that there exist RL problems where \emph{batch RL is exponentially harder than online RL} even under the most favorable batch data distribution. In other words, online exploration is critical to enable sample efficient RL with function approximation. A second corollary is the exponential separation between finite and infinite horizon batch problems under our assumptions. On a technical level, this work introduces a new `oracle + batch algorithm' framework to prove lower bounds that hold for every distribution, and automatically recovers traditional fixed distribution lower bounds as a special case. Finally this work helps formalize the issue known as \emph{deadly triad} and explains that the \emph{bootstrapping} problem \citep{sutton2018reinforcement} is potentially more severe than the \emph{extrapolation} issue for RL because unlike the latter, bootstrapping cannot be mitigated by adding more samples.

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

Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “With probability at least 1 − δ , for any f, g 1 , g 2 ∈ F and π ∈ Π , Lemma A.8 ( ε -covering Number for F Φ and Π Φ , Lemma 6 of [Zanette et al., 2021]) .”
Instabilities of Offline RL with Pre-Trained Neural Representation (2021, result): “Similar hardness results are also obtained by Zanette [2020], showing that oﬄine RL could be exponentially harder than online RL. Empirical Work.”
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).”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “Zanette, A. (2020). Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. arXiv preprint arXiv:2012.08005 . Zanette, A., & Brunskill, E. (2019). Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using ”