Beyond Worst-Case: Instance-Dependent Optimality in Reinforcement Learning
summary
Derives asymptotic and non‑asymptotic instance‑dependent lower bounds for tabular policy evaluation, identifying an optimal covariance matrix that determines the 1/√n constant; shows the classic two‑state hard instance produces the worst‑case cubic dependence ~ (1−γ)−3, while a family with reward scaling λ raises/eases that to (1−γ)−1.5−λ. Proves TD0+Polyak‑Ruppert is asymptotically optimal but variance‑reduced policy evaluation (epoched control‑variates) matches the finite‑sample lower bound up to logs, with simulations showing multi‑order improvements (≈4× at high γ) and the predicted slope −1.5.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:09Problem Statement
- 8:38Global Minimax
- 13:30Policy Evaluation
- 18:03Is TD Learning Optimal
- 21:56How to Get an InstanceOptimal Algorithm
- 26:23Useful Bounds
- 28:23Summary
- 30:23Questions
- 34:13Decoupling
- 35:43Optimal Site
- 40:41QA
related talks
11mLinear Predictors in Reinforcement Learning: ...
53mOff-policy Policy Optimization
45mPolicy Gradient: Optimal Estimation, Convergence, and Generalization beyond Cumulative Rewards
28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement Learning
01h 15mBridging Stochastic and Adversarial Bandits
55mOptimality and Approximation with Policy Gradient Methods in Markov Decision Processes
29mPure Exploration Problems
01h 05mFoundations of RL