For decades, the theoretical foundation of reinforcement learning (RL) rested on a convenient but fragile assumption: that the features we use to describe the world are linearly independent. In this idealized view, every piece of information—every sensor reading or neural network activation—provides a unique, non-redundant signal. If you have two features, they must point in different directions in the mathematical space of the problem.
In practice, this assumption is almost always violated. Modern RL relies on over-parameterized neural networks where features are highly correlated, redundant, or even identical. For thirty years, a gap existed between the "messy" success of deep RL and the "clean" proofs of convergence that required full-rank feature matrices. Recent research has finally bridged this gap, proving that algorithms like Temporal Difference (TD) learning are inherently robust to redundancy.
The Problem with Uniqueness
The traditional requirement for linear independence was driven by a desire for a unique solution. If features are linearly independent, there is exactly one set of weights $w$ that best approximates the value of a state. If features are redundant—say, you have two identical sensors—the math becomes "underspecified." There are infinitely many ways to assign weights to those sensors to get the same result.
In classical optimization, this underspecification was seen as a potential source of instability. Researchers like Sarath Pattathil, Asuman E. Ozdaglar, and Kaiqing Zhang noted in Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence that when the feature matrix is not full rank, parameters can oscillate or "blow up" even if the underlying policy seems to be improving. This created a "theoretical safety" crisis: if we couldn't guarantee the weights would settle down, how could we trust the learning process in complex environments?
From Points to Solution Sets
The breakthrough in this field comes from shifting the goalpost. Instead of proving that an algorithm converges to a single point, researchers are now proving that it converges to a solution set.
In Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features, Jiuqi Wang and Shangtong Zhang demonstrated that Linear TD learning converges "almost surely" even with linearly dependent features. The algorithm doesn't get "confused" by redundancy; it simply finds one of the many valid ways to represent the solution.
This was extended to the finite-sample regime by Zixuan Xie, Rohan Chandra, and Shangtong Zhang in Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features. They showed that TD($\lambda$) maintains its efficiency—specifically an $O(\ln t / t)$ convergence rate—regardless of feature redundancy. The weights naturally drift toward the nearest point in the "solution manifold," effectively ignoring the over-parameterization.
Rank Invariance: The New Standard
If linear independence is too strict, what is the actual requirement for a solution to exist? Zechen Wu, Amy Greenwald, and Ronald Parr propose a principle called rank invariance in A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning.
Rank invariance ensures that the solution to the RL problem actually lies within the span of the features you've chosen, even if those features are redundant. This condition is far more realistic for modern AI. It suggests that as long as your neural network is "expressive enough" to contain the solution, the fact that it has "too many" neurons (redundancy) won't prevent it from finding that solution.
Beyond Reinforcement Learning
This shift in perspective isn't limited to RL; it's also clarifying why deep neural networks are so easy to optimize. In On skip connections and normalisation layers in deep optimisation, Lachlan Ewen MacDonald, Hemanth Saratchandran, and colleagues argue that traditional deep learning theory was held back by the same "linearly independent input" assumptions.
By moving away from these constraints, they showed that skip connections and normalization layers work by "shifting up" the singular values of the network's internal mappings. This makes the loss landscape more regular, even when the data itself is highly redundant.
Why It Works: The Intuition
The reason these algorithms work with redundant features is that the update rules (like the TD error) are driven by the projection of the error onto the feature space.
- If two features are identical, the update is simply split between them.
- If a feature is a zero vector, the update ignores it.
- If a feature is a combination of others, the system finds a stable equilibrium among them.
As Shangtong Zhang and Richard S. Sutton explored in the context of average-reward RL, the stability of the learning process is a structural property of the algorithm's dynamics, not a requirement of the data's "purity." We no longer need to prune our features or worry about collinearity; the math of temporal difference learning is, and always has been, robust enough to handle the redundancy of the real world.