Recursive Least-Squares Temporal Difference With Gradient Correction.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Reinforcement Learning

Background:

• Temporal Difference (TD) learning dominates policy evaluation but suffers from low data-efficiency and off-policy divergence.
• Gradient-based and least-squares-based algorithms are prominent TD-based approaches addressing these limitations.

Purpose of the Study:

• To combine the strengths of gradient-based and least-squares-based algorithms for efficient policy evaluation.
• To develop a novel algorithm with O(n^2) per-time-step runtime complexity.
• To improve data efficiency and convergence performance in policy evaluation.

Main Methods:

• Revision of the O(n^3) batch algorithm, Least-Squares TD with Gradient Correction (LS-TDC).
• Development of RC, an O(n^2) counterpart using recursive least-squares technique.
• Generalization of RC with eligibility traces for enhanced data efficiency.
• Off-policy extension using importance sampling.
• Convergence analysis for LS-TDC and RC.

Main Results:

• RC demonstrates higher estimation accuracy compared to RLSTD.
• RC exhibits significantly lower runtime complexity than LS-TDC.
• Empirical results validate RC's performance in both on-policy and off-policy benchmarks.

Conclusions:

• RC effectively combines gradient correction and least-squares methods for efficient policy evaluation.
• The proposed algorithm addresses TD learning defects, offering improved accuracy and reduced computational cost.
• RC represents a significant advancement in policy evaluation algorithms for reinforcement learning.