16822

Batch Value-function Approximation with Only Realizability

APA

(2020). Batch Value-function Approximation with Only Realizability. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/tbd-242

MLA

Batch Value-function Approximation with Only Realizability. The Simons Institute for the Theory of Computing, Dec. 01, 2020, https://simons.berkeley.edu/talks/tbd-242

BibTex

          @misc{ scivideos_16822,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-242},
            author = {},
            keywords = {},
            language = {en},
            title = {Batch Value-function Approximation with Only Realizability},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16822 see, \url{https://scivideos.org/Simons-Institute/16822}}
          }
          
Nan Jiang (University of Illinois at Urbana-Champaign)
Talk number16822
Source RepositorySimons Institute

Abstract

In this talk I will discuss recent progress on a long-standing open problem in batch RL: learning Q* from an exploratory and polynomial-sized dataset, using a realizable and otherwise arbitrary function class. In fact, all existing algorithms demand function-approximation assumptions stronger than realizability, and the mounting negative evidence has led to a conjecture that sample-efficient learning is impossible in this setting (Chen and Jiang, 2019). Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure that reduces the learning problem to pairwise comparison, and solves the latter with the help of a state-action partition constructed from the compared functions. I will also discuss how BVFT can be applied to model selection / holdout validation among other extensions and open problems.