Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
We address the problem of policy evaluation in discounted Markov decision processes, and provide instance-dependent guarantees on the $\ell_\infty$-error under a generative model. We establish both asymptotic and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms. Theory-inspired simulations show that the widely-used temporal difference (TD) algorithm is strictly suboptimal when evaluated in a non-asymptotic setting, even when combined with Polyak-Ruppert iterate averaging. We remedy this issue by introducing and analyzing variance-reduced forms of stochastic approximation, showing that they achieve non-asymptotic, instance-dependent optimality up to logarithmic factors.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Accelerated and instance-optimal policy evaluation with linear function approximation
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 bas…
Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
Reinforcement learning (RL) has been successfully used to solve many continuous control tasks. Despite its impressive results however, fundamental questions regarding the sample complexity of RL on continuous problems re…
continuous-controlContinuous ControlReinforcement LearningReinforcement Learning (RL)Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
In this paper we consider the problem of obtaining sharp bounds for the performance of temporal difference (TD) methods with linear function approximation for policy evaluation in discounted Markov decision processes. We…
Optimal oracle inequalities for solving projected fixed-point equations
Linear fixed point equations in Hilbert spaces arise in a variety of settings, including reinforcement learning, and computational methods for solving differential and integral equations. We study methods that use a coll…
Instance-Dependent Confidence and Early Stopping for Reinforcement Learning
Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. Such problem-dependent behavior is not captured by worst-case analyses and has …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)