Batch Value-function Approximation with Only Realizability
summary
Claims a polynomial sample complexity guarantee under only realizability by introducing a batch value-function tournament that compares every pair f, f' and scores candidates by worst-case projected Bellman error; builds piecewise aggregations (size ~1/ε for one function, ~1/ε^2 for two) and proves error propagation under a strong concentrability variant so sample bounds scale polylogarithmically in |F| and polynomially in 1/(1−γ) and the coverage constant C. Algorithm is statistically consistent but computationally intractable (O(|F|^2) pairwise partitions); shows practicality for offline model selection.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:38Value-function approximation
- 1:13A Batch RL 101 Result?
- 3:25Markov Decision Process (MDP)
- 4:39Batch learning in large MDPS
- 7:48Why realizability seems insufficient?
- 12:09Hint from State Abstractions
- 20:13Batch Value Function Tournament Xi Jiang 200
- 21:22Batch Value Function Tournament 2001
- 24:18Error propagation
- 25:15Limitations & Possibilities
- 27:39Finite-sample analyses of batch VFA
related talks
54mOn the Hardness of Reinforcement Learning With Value-function Approximation
55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
29mPure Exploration Problems
43mLearning about Auctions
15mFABLE: Batched Evaluation on Confidential Lookup Tables in 2PC
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
25mReal Algebraic Geometry in Computational Game Theory
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities