Sparse Proximal Reinforcement Learning via Nested Optimization

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, ℓ
₁
-regularized method obtains sparse solutions and thus improves generalization performance. We propose an efficient ℓ
₁
-regularized recursive least squares-based online algorithm with O(n
²
) complexity per time-step, termed ℓ
₁
-RC. With the help of nested optimization decomposition, ℓ
₁
-RC solves a series of standard optimization problems and avoids minimizing mean squares projected Bellman error with ℓ
₁
-regularization directly. In ℓ
₁
-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 ℓ
₁
-RC is established based on ordinary differential equation method and some extensions are also given. In empirical computations, some state-of-the-art ℓ
₁
-regularized methods are chosen as the baselines, and ℓ
₁
-RC are tested in both policy evaluation and learning control benchmarks. The empirical results show the effectiveness and advantages of ℓ
₁
-RC.