High-probability Sample Complexities For Policy Evaluation With Linear Function Approximation
2023 · Gen Li, Weichen Wu, Yuejie Chi, et al.
Abstract
This paper is concerned with the problem of policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes. We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms: the temporal difference (TD) learning algorithm and the two-timescale linear TD with gradient correction (TDC) algorithm. In both the on-policy setting, where observations are generated from the target policy, and the off-policy setting, where samples are drawn from a behavior policy potentially different from the target policy, we establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level. We also exhihit an explicit dependence on problem-related quantities, and show in the on-policy setting that our upper bound matches the minimax lower bound on crucial problem parameters, in
Authors
(none)
Tags
Stats
Related papers
- Accelerated And Instance-optimal Policy Evaluation With Linear Function Approximation (2021)0.00
- A Finite Time Analysis Of Temporal Difference Learning With Linear Function Approximation (2018)0.00
- A Finite Sample Analysis Of Distributional TD Learning With Linear Function Approximation (2025)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
- Minimax-optimal Off-policy Evaluation With Linear Function Approximation (2020)0.00
- Finite-sample Analysis Of Decentralized Temporal-difference Learning With Linear Function Approximation (2019)0.00
- Sample Complexity Bounds For Two Timescale Value-based Reinforcement Learning Algorithms (2020)0.00