Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
By Masatoshi Uehara, M. Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, Tengyang Xie. 2021
60 citations recorded by the source corpus.
We offer a theoretical characterization of off-policy evaluation (OPE) in reinforcement learning using function approximation for marginal importance weights and $q$-functions when these are estimated using recent minimax methods. Under various combinations of realizability and completeness assumptions, we show that the minimax approach enables us to achieve a fast rate of convergence for weights and quality functions, characterized by the critical inequality \citep{bartlett2005}. Based on this result, we analyze convergence rates for OPE. In particular, we introduce novel alternative completeness conditions under which OPE is feasible and we present the first finite-sample result with first-order efficiency in non-tabular environments, i.e., having the minimal coefficient in the leading term.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Software
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
- Audrey Huang
- Nan Jiang
- Masatoshi Uehara
- Nathan Kallus
- Emma Brunskill
- Jiawei Huang
- Sergey Levine
- Stefan Riezler
In Computational Theory and Mathematics
In Software
Citations in the corpus
- Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, unknown): “√ Algorithms developed for this regime are demonstrated to achieve a 1 / N sub-optimality competing with the optimal policy [53, 16, 50].”
- Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions (2022, methodology): “This is in accordance with similar results from [KU20] and [UIJKSX21].”