Accelerated And Instance-optimal Policy Evaluation With Linear Function Approximation
2021 · Tianjiao Li, Guanghui Lan, Ashwin Pananjady
Abstract
We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees. We begin by proving lower bounds that establish baselines on both the deterministic error and stochastic error in this problem. In particular, we prove an oracle complexity lower bound on the deterministic error in an instance-dependent norm associated with the stationary distribution of the transition kernel, and use the local asymptotic minimax machinery to prove an instance-dependent lower bound on the stochastic error in the i.i.d. observation model. Existing algorithms fail to match at least one of these lower bounds: To illustrate, we analyze a variance-reduced variant of temporal difference learning, showing in particular that it fails to achieve the oracle complexity lower bound. To remedy this issue, we develop an accelerated, variance-reduced fast temporal difference algorithm (VRFTD) that simultaneously match
Authors
(none)
Tags
Stats
Related papers
- High-probability Sample Complexities For Policy Evaluation With Linear Function Approximation (2023)0.00
- Minimax-optimal Off-policy Evaluation With Linear Function Approximation (2020)0.00
- Reinforcement Learning With Unbiased Policy Evaluation And Linear Function Approximation (2022)0.00
- Variance-aware Off-policy Evaluation With Linear Function Approximation (2021)0.00
- The Role Of Lookahead And Approximate Policy Evaluation In Reinforcement Learning With Linear Value Function Approximation (2021)0.00
- Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00
- Infinite-horizon Offline Reinforcement Learning With Linear Function Approximation: Curse Of Dimensionality And Algorithm (2021)0.00
- Adaptive Temporal Difference Learning With Linear Function Approximation (2020)0.00