Differential TD Learning for Value Function Approximation
This addresses high variance and bias issues in TD learning for discounted and average cost settings, offering a domain-specific improvement for Markovian models with smooth dynamics.
The paper tackles the numerical challenges of computing Bellman equations in value function approximation by introducing a differential TD learning method, which reduces variance by two orders of magnitude in speed scaling applications.
Value functions arise as a component of algorithms as well as performance metrics in statistics and engineering applications. Computation of the associated Bellman equations is numerically challenging in all but a few special cases. A popular approximation technique is known as Temporal Difference (TD) learning. The algorithm introduced in this paper is intended to resolve two well-known problems with this approach: In the discounted-cost setting, the variance of the algorithm diverges as the discount factor approaches unity. Second, for the average cost setting, unbiased algorithms exist only in special cases. It is shown that the gradient of any of these value functions admits a representation that lends itself to algorithm design. Based on this result, the new differential TD method is obtained for Markovian models on Euclidean space with smooth dynamics. Numerical examples show remarkable improvements in performance. In application to speed scaling, variance is reduced by two orders of magnitude.