Provably Good Batch Reinforcement Learning Without Great Exploration

By Yao Liu, Adith Swaminathan, Alekh Agarwal, Emma Brunskill. 2020

110 citations recorded by the source corpus.

Batch reinforcement learning (RL) is important to apply RL algorithms to many high stakes tasks. Doing batch RL in a way that yields a reliable new policy in large domains is challenging: a new decision policy may visit states and actions outside the support of the batch data, and function approximation and optimization with limited samples can further increase the potential of learning policies with overly optimistic estimates of their future performance. Recent algorithms have shown promise but can still be overly optimistic in their expected outcomes. Theoretical work that provides strong guarantees on the performance of the output policy relies on a strong concentrability assumption, that makes it unsuitable for cases where the ratio between state-action distributions of behavior policy and some candidate policies is large. This is because in the traditional analysis, the error bound scales up with this ratio. We show that a small modification to Bellman optimality and evaluation back-up to take a more conservative update can have much stronger guarantees. In certain settings, they can find the approximately best policy within the state-action space explored by the batch data, without requiring a priori assumptions of concentrability. We highlight the necessity of our conservative update and the limitations of previous algorithms and analyses by illustrative MDP examples, and demonstrate an empirical comparison of our algorithm and other state-of-the-art batch RL baselines in standard benchmarks.

How researchers see this paper

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

Citations in the corpus

COMBO: Conservative Offline Model-Based Policy Optimization (2021, methodology): “Prior model-free offline RL algorithms have been designed to regularize the learned policy to be “close“ to the behavioral policy either implicitly via regularized variants of importance sampling based algorithms [47, 58, 35, 59, 41], offline actor-critic methods [53, 45, 27, 16, 64], applying uncer”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…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 into two (possibly overlapping) categories: (i) regularized…”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “The closest prior result to our work is that of [Liu et al., 2020], who develop a pessimistic estimator that truncates Bellman backups from state-action pairs infrequently visited by μ, and analyzes the resulting pessimistic policy and value iteration algorithms under general function approximation.”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “Based on this intuition, a variety of model-based [55, 19, 56] and model-free [22, 33, 11, 34, 25, 37, 44, 14, 28, 23, 3] offline RL algorithms are proposed that achieve promising empirical results.”
Offline Reinforcement Learning from Images with Latent Space Models (2020, methodology): “…et al., 2019; Siegel et al., 2020; Peng et al., 2019), approximate dynamic programming algorithms (Fujimoto et al., 2018; Kumar et al., 2019, 2020; Liu et al., 2020; Agarwal et al., 2019), and model-based RL algorithms (Kidambi et al., 2020; Yu et al., 2020b; Argenson and Dulac-Arnold, 2020;…”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “2 On relationship between 1/dm and βμ, C In the function approximation regime, roughly speaking, the concentration coefficient assumption requires Munos (2003); Le et al.”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, background): “…show that under strong concentrability assumptions the BPI problem is solvable using only realizability and general (non-linear) function approximators and Liu et al. (2020) show how to ﬁnd the best-in-class solution to the BPI problem while avoiding concetrability for general approximators.”