Accelerated and instance-optimal policy evaluation with linear function approximation
This work addresses the challenge of efficient and optimal policy evaluation in reinforcement learning, providing a novel algorithm with instance-optimal guarantees, though it is incremental in improving upon existing methods like variance-reduced temporal difference learning.
The authors tackled the problem of policy evaluation with linear function approximation by developing an accelerated, variance-reduced fast temporal difference algorithm (VRFTD) that simultaneously matches instance-dependent lower bounds for deterministic and stochastic errors, achieving strong optimality guarantees as confirmed by numerical experiments.
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 matches both lower bounds and attains a strong notion of instance-optimality. Finally, we extend the VRFTD algorithm to the setting with Markovian observations, and provide instance-dependent convergence results. Our theoretical guarantees of optimality are corroborated by numerical experiments.