🤖 machine learning

Reinforcement Learning Using known Invariances

This paper proposes a symmetry-aware optimistic least-squares value iteration framework that leverages known group symmetries via invariant kernels to theoretically and empirically demonstrate significant sample efficiency gains in reinforcement learning.

Original authors: Alexandru Cioba, Aya Kayal, Laura Toni, Sattar Vakili, Alberto Bernacchia

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandru Cioba, Aya Kayal, Laura Toni, Sattar Vakili, Alberto Bernacchia

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 to navigate a maze. In a standard Reinforcement Learning (RL) setup, the robot has to learn everything from scratch: "If I go left here, I hit a wall. If I go right, I find a coin." It tries thousands of times, making mistakes and slowly figuring out the rules. This is like a student trying to learn a language by only reading one book, over and over, without ever realizing that the grammar rules are the same for every sentence.

This paper proposes a smarter way to teach the robot by using known symmetries.

The Core Idea: "The Mirror Trick"

Many real-world environments have hidden patterns called symmetries.

Rotation: If you rotate a square room by 90 degrees, it looks exactly the same.
Reflection: If you look at a hallway in a mirror, the rules of walking down it don't change.
Translation: If you slide a puzzle piece one inch to the right, the way it fits is the same.

In this paper, the authors assume we already know these symmetries exist (like knowing a game board is rotationally symmetric). Instead of letting the robot learn the rules for every single spot on the board, they give the robot a "magic lens" (a mathematical tool called a kernel) that sees the board as if it were folded up.

The Analogy:
Imagine you are learning to play a video game where the level is a perfect circle.

Standard Learning: You try to learn the layout of the entire circle. You memorize that "at 12 o'clock, there is a pit." Then you have to memorize that "at 3 o'clock, there is a pit," and "at 6 o'clock," and so on. You are learning the same thing four times.
Symmetry-Aware Learning (This Paper): You tell the robot, "Hey, this level is a circle. If you learn what happens at 12 o'clock, you automatically know what happens at 3, 6, and 9." The robot only needs to learn one slice of the pie, and it instantly understands the whole pie.

How They Did It

The authors built a new version of a popular learning algorithm called LSVI (Least-Squares Value Iteration).

The "Magic Lens" (Invariant Kernels): They modified the math so that the robot's brain treats symmetrical situations as identical. If the robot sees a state and its mirror image, the math treats them as the exact same data point.
The Theory: They proved mathematically that by doing this, the robot needs far fewer attempts (samples) to learn the game. They calculated exactly how much faster it gets: the more symmetries you have, the fewer mistakes you need to make to get good at the task.
The "Covering Number": Think of this as the size of the "cheat sheet" the robot needs to keep in its head. By using symmetry, they proved the cheat sheet becomes much smaller, making the learning process much more efficient.

The Experiments: Did It Work?

They tested this idea in three different "games":

A Fake World (Synthetic): They created a simple math problem where the rules were perfectly symmetrical. The symmetry-aware robot learned much faster than the standard robot.
Frozen Lake: This is a classic AI game where a robot slides on ice to reach a goal without falling into holes.
- They took a standard ice level and also created levels where the holes and goal were randomly placed but still followed symmetry rules.
- Result: The symmetry-aware robot learned the path to the goal significantly faster and with fewer mistakes than the standard robot. It also beat a popular neural network method (DQN) that was trying to learn the same thing.
Chip Placement (2D Placement): Imagine you are an architect trying to fit 8 furniture pieces onto a grid without them overlapping.
- This is a hard problem because there are millions of ways to arrange the pieces.
- The symmetry-aware robot figured out the best arrangement much faster. It realized that rotating the whole room didn't change the difficulty, so it didn't waste time re-learning the same layout just because it was turned sideways.

The Bottom Line

The paper claims that if you know an environment has symmetries (like rotation or reflection), you shouldn't just "throw more data" at the problem. Instead, you should bake that knowledge directly into the learning algorithm.

By doing this, the robot doesn't have to re-learn the same lesson four times just because the room was turned 90 degrees. It learns the lesson once, applies it everywhere, and becomes an expert much faster. The authors provide the mathematical proof for why this works and show real-world examples where it saves a massive amount of time and effort.

What the paper does NOT claim:

It does not say this works for every problem (only those with known symmetries).
It does not claim the robot can discover these symmetries on its own; the paper assumes we tell the robot what the symmetries are beforehand.
It does not discuss medical or clinical applications; the examples are strictly about games, navigation, and design layouts.

1. Problem Statement

Reinforcement Learning (RL) often struggles with sample efficiency, particularly in environments with continuous state-action spaces and nonlinear function approximations. A significant source of inefficiency is the failure to exploit structural symmetries inherent in real-world problems (e.g., rotational invariance in robotics, reflectional symmetry in board games, or permutation invariance in multi-agent systems).

While previous works have explored symmetry via data augmentation or equivariant neural networks, there is a lack of rigorous theoretical frameworks that quantify the sample complexity gains of incorporating known group symmetries directly into non-parametric kernel-based RL methods. The paper addresses the question: How can known environment symmetries be systematically exploited to enhance sample efficiency and regret guarantees under nonlinear function approximation?

2. Methodology

The authors propose a Symmetry-Aware Kernel-based Optimistic Least-Squares Value Iteration (KOVI) algorithm. The core methodology involves three main components:

A. Invariant Kernels and RKHS

Instead of learning invariances from data, the authors assume the symmetry group $G$ is known a priori. They construct a totally invariant kernel $k_G$ from a base kernel $k$ :
$k_G(z, z') = \frac{1}{|G|} \sum_{g \in G} k(g(z), z')$
This kernel induces a Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}_{k_G}$ consisting only of functions that are invariant under the group action $G$ . By restricting the hypothesis space to this invariant RKHS, the algorithm inherently respects the symmetries of the reward and transition dynamics.

B. The Algorithm (KOVI)

The algorithm adapts the standard Kernel-based Optimistic Value Iteration (Yang et al., 2020a):

Optimistic LSVI: At each step $h$ of an episode, the agent estimates the optimal Q-function $\hat{Q}_h$ using kernel ridge regression on observed data.
Confidence Bonus: An upper confidence bound (UCB) bonus is added to encourage exploration: $Q_h = \min(\hat{Q}_h + \beta b_h, H-h+1)$ .
Symmetry Integration: The regression is performed using the invariant kernel $k_G$ , ensuring that the estimated value functions and the resulting greedy policies respect the group symmetries.

C. Theoretical Framework

The authors derive new theoretical bounds for this symmetry-aware setting:

Maximum Information Gain ( $\Gamma(T)$ ): They establish that for invariant kernels, the maximum information gain scales as $O(T^{1/p} / |G|^{1/p})$ , where $|G|$ is the group size and $p$ relates to the eigenvalue decay of the kernel.
Covering Numbers: They derive new bounds for the covering number of the function class of invariant Q-functions, showing a reduction proportional to $1/|G|$ .
Regret Bounds: Combining these, they prove that the cumulative regret $R(T)$ scales with a factor of $1/|G|$ compared to standard kernel-based methods. Specifically, for large dimensions, the regret bound improves significantly, quantifying the sample efficiency gain.

3. Key Contributions

Algorithmic Innovation: Introduction of a symmetry-aware variant of optimistic LSVI that incorporates group invariances in both reward and transition dynamics via totally invariant kernels.
Theoretical Advancement: The first theoretical analysis quantifying sample complexity gains in RL due to symmetry incorporation. They provide novel bounds on the maximum information gain and covering numbers for invariant RKHSs, explicitly showing a $1/|G|$ improvement in regret bounds.
Empirical Validation: Extensive experiments demonstrating that symmetry-aware RL significantly outperforms standard kernel counterparts and even equivariant deep neural networks in specific low-data regimes.

4. Experimental Results

The authors validated their approach on three distinct settings:

Synthetic MDP: A simplified setting with $|G|=2$ (identity and inversion). The invariant kernel KOVI achieved significantly lower cumulative regret compared to standard RBF kernel KOVI.
Frozen Lake (OpenAI Gym):
- Fixed Layout: The environment is invariant under the $D_4$ symmetry group (rotations and reflections of a square). KOVI with invariant kernels converged faster and achieved higher returns than standard RBF KOVI.
- Random Layout: A more challenging setting where the layout changes every episode but retains $D_4$ symmetry. The invariant kernel consistently outperformed the standard kernel, demonstrating robust generalization.
- Comparison with Deep RL: KOVI with invariant kernels outperformed both standard DQN and SymDQN (a DQN with equivariant layers) in terms of sample efficiency, converging to optimal returns with fewer timesteps.
2D Placement Problem (SynPl): A chip design-inspired task involving placing 8 units on an $8\times8$ grid. This problem involves complex geometric constraints and high-dimensional state spaces. The invariant kernel approach yielded lower regret and better placement configurations compared to the baseline, highlighting the utility of symmetry in structured design problems.

5. Significance and Conclusion

Sample Efficiency: The paper demonstrates that explicitly encoding known structural priors (symmetries) into the function approximation class (via invariant kernels) leads to substantial reductions in sample complexity. This is crucial for real-world applications where data collection is expensive or time-consuming.
Theoretical Rigor: Unlike heuristic data augmentation or parametric equivariant networks, this work provides formal regret guarantees and quantifies the exact benefit of symmetry in terms of the group size $|G|$ .
Non-Parametric Advantage: The results suggest that in low-data regimes, non-parametric kernel methods with symmetry constraints can outperform deep learning approaches (even those designed with symmetry), as they require less data to converge to optimal policies.
Limitations: The authors acknowledge that the computational complexity of kernel methods ( $O(HT^4)$ ) can be prohibitive for very large datasets, though they suggest optimizations like sparse GPs or Cholesky updates to mitigate this.

In summary, this work bridges the gap between theoretical group theory and practical RL, providing a robust framework for leveraging known symmetries to build more efficient and generalizable learning agents.