Sparse Proximal Reinforcement Learning via Nested Optimization
Tianheng Song, Dazi Li, Qibing Jin, Kotaro Hirasawa · IEEE Transactions on Systems Man and Cybernetics Systems · 2018
We consider the tasks of feature selection and policy evaluation based on linear value function approximation in reinforcement learning problems. High-dimension feature vectors and limited number of samples can easily cause over-fitting and computation expensive. To prevent this problem, ℓ1-regularized method obtains sparse solutions and thus improves generalization performance. We propose an efficient ℓ1-regularized recursive least squares-based online algorithm with O(n2) complexity per time-step, termed ℓ1-RC. With the help of nested optimization decomposition, ℓ1-RC solves a series of standard optimization problems and avoids minimizing mean squares projected Bellman error with ℓ1-regularization directly. In ℓ1-RC, we propose RC with iterative refinement to minimize the operator error, and we propose an alternating direction method of multipliers with proximal operator to minimize the fixed-point error. The convergence of ℓ1-RC is established based on ordinary differential equation method and some extensions are also given. In empirical computations, some state-of-the-art ℓ1-regularized methods are chosen as the baselines, and ℓ1-RC are tested in both policy evaluation and learning control benchmarks. The empirical results show the effectiveness and advantages of ℓ1-RC.