🤖 machine learning

Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

This paper proposes a non-convex sparse reinforcement learning approach that augments least-squares temporal-difference policy evaluation with a projected minimax concave penalty and establishes novel convergence guarantees for the forward-reflected-backward splitting method to solve the resulting non-monotone inclusion problem, demonstrating superior feature selection performance over state-of-the-art methods in noisy environments.

Original authors: Kyohei Suzuki, Konstantinos Slavakis

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kyohei Suzuki, Konstantinos Slavakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to navigate a maze. The robot learns by trial and error, but in the real world, you can't always let it run around endlessly because it might break things or waste time. So, instead, you give the robot a "notebook" of past experiences (a fixed dataset) and ask it to figure out the best path based on that.

The problem is, these notebooks are often messy. They contain thousands of details, but most of them are just noise (like the color of the walls or the temperature of the air) that doesn't actually help the robot navigate. If the robot tries to learn from everything in the notebook, it gets confused, makes bad guesses, and learns a "biased" view of the world.

This paper presents a new, smarter way to clean up that notebook and teach the robot, using a mix of advanced math and a clever new strategy. Here is the breakdown:

1. The Problem: The "Noisy Notebook"

In the past, researchers tried to solve this by using a technique called L1 regularization (think of it as a "strict filter"). This filter says, "Keep only the most important features and ignore the rest."

The Flaw: This strict filter is too harsh. It tends to shrink the important numbers too much, like a photographer who accidentally makes the main subject look smaller than they really are. This is called estimation bias. The robot learns a policy that is "okay," but not the best possible one.

2. The Solution: A "Smart, Flexible Filter"

The authors introduce a new tool called the PMC penalty.

The Analogy: Imagine the strict filter (L1) is a rigid metal sieve that breaks big rocks (important data) into dust. The new PMC penalty is like a smart sieve with adjustable holes. It knows which parts of the data are truly important and lets them pass through at full size, while still filtering out the useless noise.
The Result: This removes the "shrinking" bias. The robot learns a much more accurate map of the maze, even when the notebook is full of garbage data.

3. The Mathematical Hurdle: The "Wobbly Hill"

Usually, when you try to find the best solution in math, you are climbing a smooth, bowl-shaped hill. You know that if you keep walking downhill, you will eventually reach the bottom (the best answer).

The Twist: Because the new "smart filter" (PMC) is so flexible, the hill it creates isn't smooth and bowl-shaped anymore. It's wobbly and non-convex. It has bumps and dips that could trick a standard algorithm into thinking it's at the bottom when it's actually stuck on a small bump.
The Risk: Standard math tools (algorithms) usually give up or get lost on these wobbly hills because they rely on the hill being perfectly smooth.

4. The New Strategy: The "Reflected Step"

To solve this, the authors developed a new way to walk down this wobbly hill. They used a method called Forward-Reflected-Backward Splitting (FRBS).

The Analogy: Imagine you are walking down a dark, bumpy path.
- Old Way: You take a step forward, look at the ground, and hope you didn't trip. If the ground is weird, you might fall.
- New Way (FRBS): You take a step forward, but you also look back at where you just came from and use that memory to adjust your next step. It's like having a "ghost" of your previous step helping you balance.
The Guarantee: The authors proved mathematically that even on this wobbly, non-convex hill, this "look-back" strategy will eventually lead you to the bottom. They showed that the robot won't get stuck in a loop or wander off forever; it will find the solution.

5. The Results: Winning the Race

The authors tested this new method on three classic robot challenges (a chain walk, a car on a hill, and a swinging robot arm).

The Competition: They compared their method against the old "strict filter" (LARS-TD) and other standard methods.
The Outcome:
- When the data was full of noise (irrelevant features), the old methods got confused and failed often.
- The new method won consistently. It found the best path more often, took fewer steps to reach the goal, and ignored the noise effectively.
- Crucially, it did this even when the dataset was small or very messy.

Summary

This paper is about teaching a robot to ignore the noise and learn the truth, even when the math gets messy.

They replaced a rigid filter with a smart, flexible filter to stop the robot from underestimating important facts.
They invented a new walking strategy (FRBS) that allows the robot to find the best answer even when the math landscape is bumpy and unpredictable.
They proved this strategy works and showed that it makes robots learn faster and more accurately than current state-of-the-art methods.

Technical Summary: Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

Problem Statement
Reinforcement learning (RL) often faces the "curse of dimensionality" when approximating Q-functions in high-dimensional state spaces. While linear function approximation is a standard remedy, it introduces a trade-off between approximation accuracy and computational complexity. Feature selection via sparse modeling is a common strategy to mitigate this, yet conventional approaches relying on $\ell_1$ -norm regularization (e.g., LARS-TD, LSTD with $\ell_1$ ) suffer from estimation bias, systematically underestimating large-amplitude components. Furthermore, in batch RL settings where data is fixed and potentially noisy, robustness to irrelevant features and outliers is critical. While non-convex penalties like the Minimax Concave (MC) penalty have been proposed in sparse regression to reduce bias, their application to RL remains unexplored due to the resulting non-convexity of the optimization problem, which breaks the monotonicity assumptions required by standard convergence guarantees in operator splitting methods.

Methodology
The paper proposes a novel batch algorithm for feature selection in RL that integrates the non-convex Projective Minimax Concave (PMC) penalty into the Least-Squares Temporal-Difference (LSTD) formulation.

Problem Reformulation: The authors formulate the policy evaluation problem as finding a fixed point of a mapping that minimizes a least-squares temporal-difference error regularized by the PMC penalty. Unlike standard LSTD, this objective is non-convex.
Operator Splitting: By exploiting the weak convexity of the PMC penalty, the fixed-point problem is reformulated as finding the zero of the sum of two operators: a monotone Lipschitz operator and a hypomonotone operator. This places the problem within the class of non-monotone inclusions.
Algorithmic Solution: The authors employ the Forward-Reflected-Backward Splitting (FRBS) method to solve this inclusion problem. A key technical contribution is the derivation of a closed-form expression for the resolvent of the hypomonotone part (involving the soft-shrinkage operator), which renders the algorithm tractable without auxiliary variables.
Hyperparameter Tuning: The method introduces a tunable hyperparameter $q$ that controls the subspace $M$ onto which the debiasing effect of the PMC penalty is confined. This generalizes the original PMC definition, allowing for optimization of the penalty's performance even when the input Gram matrix has very small positive eigenvalues.

Key Contributions
The paper makes four primary contributions:

RL Algorithm: It introduces an efficient batch feature selection method for RL that incorporates the non-convex PMC penalty into LSTD. This addresses the estimation bias inherent in $\ell_1$ -regularized methods.
Theoretical Extension: It extends the convergence analysis of the FRBS method to a broader class of non-monotone inclusion problems. Specifically, it establishes:
- Lyapunov Stability: Under mild conditions, the iterates are shown to be quasi-Fejér monotone, ensuring the existence of a limit point and stability.
- Exact Convergence: Under the weak Minty Variational Inequality (MVI) assumption, the sequence is proven to converge exactly to a solution.
Generalized PMC Penalty: The paper generalizes the PMC penalty by allowing the subspace $M$ to be controlled by a tunable parameter $q$ , rather than being fixed to the orthogonal complement of the null space. This prevents performance degradation in ill-conditioned settings.
Error Bounds: An error bound for policies generated by the proposed Approximate Policy Iteration (API) scheme is provided, linking the approximation error to the Q-function estimation error.

Results
Numerical tests were conducted on three benchmark RL tasks: the 50-state chain walk, the mountain car, and the acrobot. The proposed method was compared against state-of-the-art batch feature selection methods, including LSTD, LARS-TD, and Basis Pursuit Denoising (BPDN).

Performance: The proposed method substantially outperformed competitors, particularly in scenarios with numerous noisy or irrelevant features. In the mountain car and acrobot tasks, it achieved the highest success rates and the fewest average steps to the goal.
Bias Mitigation: The results demonstrated that the proposed method effectively mitigates the estimation bias associated with $\ell_1$ -norm regularization, leading to more accurate Q-function estimates.
Hyperparameter Sensitivity: Experiments on the 50-state chain walk showed that the hyperparameter $q$ significantly influences performance. A moderate range of $q$ yielded the lowest Normalized Mean Square Error (NMSE), while extreme values degraded performance by either failing to debias sufficiently or forcing the penalty to approximate the biased $\ell_1$ norm.

Significance
The paper claims to provide a rigorous theoretical foundation for applying non-convex penalties in RL, a domain where such methods have previously been avoided due to convergence concerns. By establishing convergence guarantees for FRBS in non-monotone settings, the work bridges the gap between non-convex sparse modeling theory and practical RL applications. The authors assert that their approach offers a robust alternative to convex regularization, delivering superior feature selection and policy performance in high-dimensional, noisy environments without sacrificing theoretical convergence guarantees. The work extends a preliminary conference version by providing full convergence proofs under weak MVI assumptions and extensive numerical validation.