Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

In high-dimensional reinforcement learning (RL), there is a fundamental trade-off between approximation accuracy and computational complexity. While sparse regularization (like the L1-norm) is a common tool to manage this, it often introduces significant estimation bias. This paper asks: can non-convex, sparsity-inducing penalties be effectively used for feature selection in RL to reduce this bias while maintaining rigorous convergence guarantees?

The authors propose augmenting the classical least-squares temporal-difference (LSTD) policy evaluation with the projected minimax concave (PMC) penalty. Because the PMC penalty is weakly convex, the resulting fixed-point problem is non-monotone. To solve this, the authors reformulate the task as a non-monotone inclusion problem involving the sum of a monotone Lipschitz operator and a hypomonotone operator. They then apply the forward-reflected-backward splitting (FRBS) method, establishing new theoretical convergence conditions, including Lyapunov stability and exact convergence under the weak Minty variational inequality assumption.

The proposed method significantly outperforms state-of-the-art feature selection techniques (such as LARS-TD and BPDN) in benchmark RL tasks like the 50-state chain walk, mountain car, and acrobot. The authors demonstrate that the PMC penalty, when combined with their FRBS-based algorithm, provides a superior balance of sparsity and accuracy, especially in scenarios with numerous noisy features. They also show that the hyperparameter q, which controls the subspace of the debiasing effect, is a critical tunable parameter for performance.

This work bridges the gap between non-convex optimization theory and practical batch reinforcement learning. By providing a principled way to handle non-monotone inclusions in RL, the authors offer a robust alternative to standard convex regularization, potentially enabling more accurate and sample-efficient policy learning in high-dimensional, real-world applications where data is limited or noisy.