Online Sparse Temporal Difference Learning Based on Nested Optimization and Regularized Dual Averaging
提出一种在线稀疏时序差分学习算法，通过L1正则化选择特征，避免过拟合并提高估计精度，计算复杂度与特征维度呈线性关系。
In policy evaluation of reinforcement learning tasks, the temporal difference (TD) learning with value function approximation has been widely studied. However, feature representation has a decisive influence on both accuracy of value function approximation and convergence rate. Therefore, it is important to develop the feature selection theory and methods that can efficiently prevent overfitting and improve estimation accuracy in TD learning algorithms. In this article, we propose an online sparse TD learning algorithm for policy evaluation by using <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> -regualrization for feature selection. The per-step-time runtime computational complexity of the proposed algorithm is linear with respect to feature dimension. The loss function is defined as a nested optimization with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> -regularization penalty, and the solver minimizes two suboptimization problems by running stochastic gradient descent and regularized dual averaging method, alternately. The convergence results for the fixed points are also established. The experiments on benchmarks with high-dimensional features show the abilities of learning and generalization of the proposed algorithms.