Minimax-optimal Off-policy Evaluation With Linear Function Approximation
2020 · Yaqi Duan, Mengdi Wang
Abstract
This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history generated by unknown behavioral policies. We study a regression-based fitted Q iteration method, and show that it is equivalent to a model-based method that estimates a conditional mean embedding of the transition operator. We prove that this method is information-theoretically optimal and has nearly minimal estimation error. In particular, by leveraging contraction property of Markov processes and martingale concentration, we establish a finite-sample instance-dependent error upper bound and a nearly-matching minimax lower bound. The policy evaluation error depends sharply on a restricted \(\chi^2\)-divergence over the function class between the long-term distribution of the target policy and the distribution of past data. This restricted \(\chi^2\)-di
Authors
(none)
Tags
Stats
Related papers
- Variance-aware Off-policy Evaluation With Linear Function Approximation (2021)0.00
- Accelerated And Instance-optimal Policy Evaluation With Linear Function Approximation (2021)0.00
- Reinforcement Learning With Unbiased Policy Evaluation And Linear Function Approximation (2022)0.00
- The Optimal Approximation Factors In Misspecified Off-policy Value Function Estimation (2023)0.00
- Off-policy Fitted Q-evaluation With Differentiable Function Approximators: Z-estimation And Inference Theory (2022)0.00
- A Maximum-entropy Approach To Off-policy Evaluation In Average-reward Mdps (2020)0.00
- Infinite-horizon Offline Reinforcement Learning With Linear Function Approximation: Curse Of Dimensionality And Algorithm (2021)0.00
- Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00