Uniform Offline Policy Evaluation (OPE) and Offline Learning in Tabular RL

on YouTube ↗34m

" summary

Analyzes offline RL in episodic tabular (time-inhomogeneous) MDPs with N logged trajectories under a coverage assumption and proves pointwise OPE achieves the Cramer‑Rao lower bound (leading term ~ H^2/(N·D_M), with D_M ≈ 1/(SA) in best case), plus matching lower bounds and examples showing H^3 behavior; shows a model-based ERM yields uniform OPE sufficient for offline learning with only an extra √H factor; proof uses martingale decomposition, Rademacher complexity, a fictitious‑estimator trick and anchoring around empirically near‑optimal policies.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 1:18Reinforcement learning is among the hottest area of research in ML!
3. 2:11Topic today: Offline Reinforcement Learning, aka. Batch RL • Task 1: Offline Policy Evaluation. (OPE)
4. 3:37Example applications of Offline RL
5. 5:19Formal problem setup: Episodic, Tabular, Non-Stationary MDPS • Number of states, actions, horizon: 5AH
6. 7:58We will not deal with exploration in offline RL, because we can't • The logging policy is out of our control
7. 9:11Observation 1: OPE is in its essence a statistical estimation problem. . But is slightly non-trivial because we are estimating a single number, when the number of parameters describing the distribution are numerous.
8. 10:24Observation 2: Offline Learning is a statistical learning problem . But with a structured hypothesis class (the policy class), and structured observations (trajectories).
9. 14:05TL;DR: Our main contributions are: Optimal OPE and near optimal OPL 1. Characterizing the OPE for any fixed policy
10. 15:54Comparing with prior results Offline Policy Evaluation Simulation
11. 18:24Our result is the first that achieves optimal rates in the offline setting
12. 19:22Why is uniform convergence in RL a nontrivial problem? • Even pointwise convergence is nontrivial
13. 22:12Uniform convergence theorem for
14. 23:30near-empirically optimal policies
15. 24:27Key techniques used in the proof
16. 25:44To reiterate the main points
17. 26:26Future work / open problems

" related talks

• 54mGeneralization and Robustness in Offline Reinforcement LearningWen Sun · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?Sham Kakade · Mathematics of Online Decision Making 2020
• 48mOffline Reinforcement Learning With Only RealizabilityJason Lee · Adversarial Approaches in Machine Learning 2022
• 56mOn the Curses of Future and History in Off-policy Evaluation in non-Markov EnvironmentsNan Jiang · Emerging Generalization Settings 2024
• 31mOnline Reinforcement Learning With The Help Of Confounded Offline DataUri Shalit · Learning from Interventions 2022
• 43mContextual Inverse Optimization: Offline and Online LearningIlan Lobel · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 01h 05mFoundations of RLRayadurgam Srikant · Data-Driven Decision Processes Boot Camp 2022
• 49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust LearningNika Haghtalab · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond