A New Accelerated Off-Policy Stochastic Preconditioned TD(0) Algorithm.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Reinforcement Learning

Background:

• Off-policy policy evaluation is crucial for reinforcement learning.
• Existing methods often lack optimal convergence rates.
• Linear function approximation is widely used in RL.

Purpose of the Study:

• To propose a novel procedure for off-policy policy evaluation.
• To achieve the optimal convergence rate under linear function approximation.
• To analyze the finite-sample rates and asymptotic distribution.

Main Methods:

• Stochastic Preconditioned Temporal Difference (SPTD) algorithm.
• Analysis under Markovian sampling for differing policies.
• Derivation of finite-sample rates and asymptotic distribution.

Main Results:

• SPTD achieves the optimal O(1/t) convergence rate (MSE).
• Linear computational complexity in feature space dimension.
• First results on asymptotic distribution and near-optimal step size (αt = O(t^{-2/3})).
• Uniformly outperforms existing methods in numerical experiments.

Conclusions:

• SPTD offers a theoretically optimal and practically superior approach to off-policy policy evaluation.
• The method demonstrates strong performance in both on-policy and off-policy settings.
• SPTD advances the state-of-the-art in reinforcement learning evaluation.