On the Curses of Future and History in Off-policy Evaluation in non-Markov Environments
summary
Claims that OPE in partially observable settings gets polynomial (no exponential-in-horizon) sample complexity by replacing history-based value functions with future-dependent value functions; identifies two POMDP-tailored coverage notions—belief coverage and outcome coverage—and gives Bellman-error–style estimators that provably work for memoryless policies under those assumptions. Notes that naive density-ratio coverage explodes (empirical ratios ~exp(25)), explains why the new estimators avoid that, and shows outcome coverage is needed for solutions to exist.
AI-written summary · about
chapters (9)
- 0:00Reinforcement learning intro
- 7:50Policy evaluation in non-Markov envs
- 13:58Generalization in decision making
- 21:50Importance sampling limits
- 29:02Markov assumptions and ratios
- 33:30Non-Markov challenges in RLHF
- 39:14Latent models and POMDPs
- 49:21Coverage in POMDPs
- 51:55Summary and implications
related talks
34mUniform Offline Policy Evaluation (OPE) and Offline Learning in Tabular RL
28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement Learning
43mControlling Probabilistic Systems Under Partial Observation
53mOff-policy Policy Optimization
48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from Samples
29mPure Exploration Problems
44mBeyond Worst-Case: Instance-Dependent Optimality in Reinforcement Learning
09mTowards Credible and Effective Data-Driven Decision-Making