acceptodds
Under review as a conference paper at ICLR 2027

Sample Complexity of Equivariant Reinforcement Learning

Abstract

Reinforcement learning (RL) is a powerful framework for robotic control, yet its practical application is often hindered by high sample complexity. This is particularly restrictive in physical domains where interaction data is costly. While the world often exhibits geometric and physical symmetries, standard RL algorithms typically fail to exploit this structure. In this paper, we demonstrate that exploiting group symmetries significantly reduces the sample complexity of RL. Focusing on finite-horizon Markov decision processes, we find that leveraging homomorphisms induced by group symmetries significantly reduces the theoretical upper and lower bounds on the number of environment interactions required to reach an optimal return. We further extend these bounds to continuous state and action spaces, providing corresponding sample-complexity guarantees under appropriate regularity assumptions. Beyond theory, we validate our findings through controlled experiments and demonstrate the advantages of symmetry-aware policy learning on high-dimensional continuous robotic simulations. Our results show that integrating symmetry into the learning pipeline yields substantial gains in sample efficiency and performance, offering a principled path toward more data-efficient robotics.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Sample Complexity, Group Symmetry, MDP Homomorphisms.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_6cYQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies reinforcement learning in MDPs with group symmetry by constructing an abstract MDP that quotients symmetry-equivalent states and actions according to their group orbits, and analyzes the resulting sample efficiency from a PAC sample-complexity perspective. In the discrete finite-horizon setting, the paper claims that reductions in the sizes of the state, action, and successor spaces induce corresponding reductions in PAC upper and lower bounds through symmetry-dependent reduction factors. The paper further extends the analysis to continuous state and action spaces using covering numbers over quotient spaces. Empirically, the paper evaluates 1D/3D cyclic domains, Rubik’s cube, and continuous robotic manipulation tasks, and reports that symmetry-aware learning through canonicalization or equivariant/homomorphic architectures achieves better sample efficiency than non-equivariant baselines.

Critical strengths

S1. Continuous-space extension:

The analysis of continuous PAC sample complexity on the quotient MDP in Theorem 3 is, in my view, the most substantive theoretical component of the paper. It attempts to extend the intuition developed in the discrete setting to continuous state and action spaces through quotient-space covering numbers.

S2. Empirical consistency across increasingly complex domains:

The paper reports a consistent empirical trend that equivariant or symmetry-aware RL can leverage symmetry structure beyond toy environments. In particular, the empirical advantage tends to become more pronounced as the problem becomes more complex, which is qualitatively consistent with the paper’s theoretical motivation.

Critical weaknesses

There are important gaps in the justification of the assumptions and correctness of the main theoretical results. First, Proposition 1 states that the successor complexity satisfies

\bar C =C/|G_c |

but it is unclear whether this relation holds for a general group-invariant MDP. Although the paper distinguishes GC from GS, it does not define sufficiently clearly how GC should be constructed for the local successor set associated with a fixed state-action pair. Theorem 1 directly depends on this reduction.

Second, Theorem 2 appears to omit the quantification required for a PAC lower bound, as well as an argument showing that an appropriate hard instance exists within the symmetry-constrained class considered in this paper.

Appendix A also switches from the stochastic finite-horizon setting used in the main text to a deterministic discounted transition model without explaining the relationship between the two formulations. In addition, the proof of optimal-policy equivariance does not clearly address the case of non-unique maximizers and the corresponding argmax tie-breaking issue. W2. The novelty and the evidence-to-claim chain are not sufficiently convincing. The discrete theoretical result emphasized as a main contribution appears to amount largely to applying a symmetry-dependent reduction factor to an existing PAC bound on the quotient MDP. It is also unclear to me whether this constitutes a sufficiently distinct theoretical contribution relative to existing work.

For example, Asadi et al. (2019) and Lyu et al. (2023) already analyze learning-complexity improvements under state-action equivalence, in terms of regret and PAC-type sample complexity, respectively. On the continuous side, both covering-number-based PAC analysis and continuous MDP homomorphisms have also been studied previously.

The empirical evidence is also not clearly connected to the theoretical claims. The experiments show that symmetry-aware methods learn faster, but the paper does not explicitly explain which theoretical prediction each experiment is intended to test, or how the observed evidence supports the claimed PAC reduction or quotient-covering-number analysis. In particular, it is difficult to determine from the current presentation how the continuous robotic manipulation experiments correspond to the assumptions or covering-number reduction in Theorem 3.

There are also inconsistencies between the main paper and supplementary material regarding the number of seeds, the N-range, and reported standard errors, which make the provenance of some empirical results unclear.

Questions for authors

Q1. Successor-complexity reduction

What exactly does GC denote in Proposition 1, and under what assumptions does \bar C =C/|G_c | hold? Group invariance generally maps Succ(s,a) to Succ(gs,ga), rather than implying that the full group acts within the successor set of a fixed state-action pair. Therefore, it is not clear why the global orbit size of successor states should reduce the local branching factor by the same multiplicative factor. Since the |GC| improvement in Theorem 1 directly depends on this relation, please clarify the precise definition, assumptions, and derivation.

Q2. PAC Lower-bound statement

Could the authors clarify the precise quantification and probabilistic form of Theorem 2? As currently written, the theorem appears to give a positive lower bound for an arbitrary fixed MDP. However, for example, in an MDP with identically zero rewards, every policy is optimal and the number of ϵ-suboptimal episodes is always zero. If the intended statement is a worst-case result of the form “for every learning algorithm, there exists a hard MDP,” please state this explicitly and explain why such a hard instance exists within the group-invariant/symmetry-constrained MDP class considered in this paper. Please also clarify how the probability statement in Theorem 2 follows from the lower-bound result being invoked.

Q3. Experimental protocol inconsistencies

Could the authors clarify the inconsistencies between the experimental protocols described in the main paper and supplementary material? Main Table 1 reports mean ± SE over 10 independent seeds and includes results for N=35 and N=40, whereas Appendix C.2.1 describes a sweep only up to N=30 and states that all runs use seed 42. Similarly, the main text reports standard errors or refers to multiple random seeds for the 3D experiments and Figure 5, while the supplementary material again specifies seed 42. Please provide the exact number of seeds, N-range, and aggregation procedure used for each reported result.

Q4. Relation to prior equivalence and abstraction literature.

Could the authors more directly compare the discrete theoretical contribution of this paper with prior work on state-action equivalence and abstraction? For example, Asadi et al. (2019) analyze regret improvements under known state-action equivalence, while Lyu et al. (2023) provide a non-asymptotic PAC-type sample-complexity analysis using state-action equivalence. If group-orbit equivalence can be viewed as a special case of these more general equivalence structures, what new theoretical insight do Theorems 1 and 2 provide beyond these results? I would appreciate either a direct comparison with these works or a clear explanation of why such a comparison is not appropriate. Q5. Scientific content of Theorem 3. Does Theorem 3 provide a scientific or technical insight beyond replacing the covering numbers N(S, α) and N(A, α) in existing continuous-space PAC analyses with the quotient-space covering numbers (N(S/G, α) and N(A/G, α)? From the current proof sketch, the result can also be read as a relatively direct combination of continuous-space discretization/covering-number analysis with symmetry quotienting. Clarifying the nontrivial contribution of Theorem 3 would materially affect my assessment of the paper’s novelty.

3 comments

We thank the reviewer for recognizing the significance of our continuous-space theoretical contribution and the consistent empirical improvements across increasingly complex domains. We appreciate the opportunity to clarify the mathematical assumptions, theoretical novelty, and experimental methodology. We address each concern below.

1. Successor-complexity reduction (Q1). The group action maps Succ(s,a)\mathrm{Succ}(s,a) to Succ(gs,ga)\mathrm{Succ}(gs,ga), while the quotient successor complexity counts distinct successor orbits reachable from an abstract state-action pair. We will clarify this distinction in Proposition 1. In general, the quotient successor complexity is Cˉ=max⁡(s,a)∣{[s′]:s′∈Succ(s,a)}∣\bar C=\max_{(s,a)}|\{[s']:s'\in\mathrm{Succ}(s,a)\}|. The multiplicative expression Cˉ=C/∣GC∣\bar C=C/|G_C| requires additional structural conditions and will be stated accordingly. The general PAC upper bound remains valid in terms of the actual quotient complexity.

2. PAC lower bound (Q2). Theorem 2 is intended as a worst-case lower bound over the class of symmetry-constrained MDPs, rather than a statement applying to every individual MDP. We will make the quantification explicit: for every learning algorithm, there exists a hard instance within the considered class. Such instances can be constructed by lifting suitable hard quotient MDPs to symmetric MDPs, preserving their learning difficulty. We will provide the construction and align the probability statement with the underlying PAC lower-bound result.

3. Experimental protocol (Q3). We appreciate the reviewer identifying discrepancies between the main text and Appendix C. The main tables report aggregated results over 10 independent seeds, while the supplementary descriptions refer to a representative seed and an earlier parameter sweep. We will reconcile the experimental documentation by explicitly reporting the seed counts, complete parameter ranges, and aggregation procedures for each experiment, ensuring consistency between the main manuscript and supplementary material.

4. Relation to prior work (Q4). We acknowledge the relevance of Asadi et al. (2019) and Lyu et al. (2023). Our contribution focuses specifically on group-induced MDP homomorphisms and explicitly relates orbit structure to PAC sample complexity. Unlike general state-action equivalence formulations, our framework characterizes the reduction through the underlying group action and extends the analysis to continuous domains. We will strengthen the related-work discussion to distinguish these contributions.

5. Continuous-space contribution (Q5). Theorem 3 connects group-invariant continuous MDPs to quotient-space covering numbers under geometric and Lipschitz regularity assumptions. Its significance lies in identifying how geometric symmetry changes the effective metric complexity governing sample efficiency, rather than simply reducing finite state-action cardinalities. We will expand the derivation to clarify the quotient metric, equivariant discretization, and approximation-error guarantees.

6. Experimental connection to theory. The structured experiments investigate symmetry-dependent scaling, while the robotic benchmarks evaluate whether symmetry-aware representations improve learning efficiency in continuous-control settings. We will distinguish these empirical observations from formal verification of the PAC bounds and clarify how the continuous experiments relate to the assumptions of Theorem 3.

These revisions will strengthen the mathematical precision, reproducibility, and positioning of our contributions while preserving the central conclusion that exploiting group symmetry can reduce reinforcement learning sample complexity.

We would like to respectfully follow up as the author-reviewer discussion deadline approaches. We believe we have comprehensively addressed all concerns and questions raised in the review. Given that no further objections have been raised, we respectfully encourage the reviewer to reconsider the initial assessment and increase the score in light of our clarifications.

Thank you for your response and follow-up. However, I do not consider all of my concerns to have been fully resolved. In particular, the following issues remain unresolved and continue to affect my assessment: Q1: Please specify the additional structural conditions and clarify the resulting statement and validity of Theorem 1. Q2: The proposed hard-instance construction and justification of the probabilistic lower bound have not yet been provided. Q3: The actual seed counts, parameter ranges, and aggregation procedures underlying the reported results remain to be clarified. Q4: A concrete comparison with the cited prior work is still needed to establish the distinct theoretical contribution. Q5: The nontrivial contribution of Theorem 3 beyond existing covering-number arguments remains unclear. Much of the response consists of commitments such as "we will provide" or "we will expand," without the corresponding arguments or evidence. A revised manuscript would be helpful, but I am also open to considering concrete arguments and supporting evidence provided directly in the discussion. At this stage, I do not find sufficient grounds to revise my assessment based solely on commitments to future changes. I appreciate the authors' constructive engagement.

Reviewer_JwDfOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the sample complexity of learning in MDPs with known state and action space symmetries. The first contribution is sample complexity lower and upper bounds when the states and actions equivalent under symmetries are grouped together (this is called the quotient MDP). The second contribtuion is empricially evaluating whether leveraging the present symmetries could give gains in learning efficiency.

Critical strengths

The critical strength of this paper is the question itself: can leveraging group symmetries present in certain MDPs reduce the sample complexity of learning?

Critical weaknesses
  1. The proof for Proposition 1 is incorrect. One should parition the state space into distinct orbits and then count the effective number of states in the quotient MDP by reducing each partition separately. Also, the proof currently reduces the sizes for both states and actions independently, which is not true since the quotient MDP needs to preserve the relations between (s, a) and (gs, ga).
  2. The actual sample complexity bound needs to account for the samples needed to identify the quotient MDP (if there is even an efficient algorithm to do that, is another question). Otherwise, the bounds trivially follow from existing results and the comparison isn't fair.
  3. The empricial contribution is unclear. The experiements use domain-knowledge of group symmetries to realize gains. It is unclear how it would work for general MDPs that could have unknown symmetries.
Questions for authors
  1. Could you please explain why the proof for Proposition 1 doesn't consider distinct orbits separately?
  2. How does one construct the quotient MDP when the agent can only identify the MDP through experience? Is the homomorphism known already? If so, the sample complexity results directly follow from existing bounds in the literature, so what is the theoretical contribution?
4 comments

We thank the reviewer for recognizing the importance of investigating how group symmetries affect reinforcement learning sample complexity. We appreciate the opportunity to clarify the mathematical formulation, the assumptions underlying the quotient MDP, and the significance of our theoretical and empirical contributions. We address each concern below.

1. Proposition 1 and orbit counting. The quotient construction preserves state-action dependencies through the group action. Formally, defining E={(s,a):s∈S, a∈A(s)}\mathcal E=\{(s,a):s\in S,\ a\in A(s)\}, the quotient is characterized by S/GS/G and E/G\mathcal E/G. This accounts for distinct orbits without assuming independent state-action reductions. The general PAC bound depends on the quotient cardinalities and successor complexity, while the multiplicative reduction factors follow under additional uniformity and structural conditions. We will clarify these conditions in Proposition 1 without changing the central quotient-based result.

2. Quotient construction and sample complexity. Our framework considers known symmetries but unknown transition dynamics. The quotient representation is determined by the group action and does not require learning the original transition kernel. Each observed transition can be mapped directly into the quotient space, allowing the reduced dynamics to be learned from experience. Therefore, no additional environment interactions are inherently required to discover a symmetry structure already assumed known. Computational quotient construction and statistical sample complexity are distinct considerations.

3. Theoretical significance. Our contribution extends beyond applying existing PAC bounds to smaller MDPs by explicitly characterizing the relationship between group-theoretic structure and learning complexity. The discrete analysis identifies symmetry-dependent reductions, while Theorem 3 extends the framework to continuous state-action spaces through quotient-space covering numbers, providing a theoretical connection to continuous robotic learning.

4. Experimental validation. The experiments intentionally exploit known symmetries, consistent with our theoretical assumptions. The cyclic-ring experiments investigate symmetry-dependent scaling, while Rubik's cube and robotic manipulation benchmarks demonstrate improvements across combinatorial and continuous-control domains. Discovering unknown symmetries is a separate research problem.

These clarifications strengthen the mathematical presentation while preserving the central conclusion that exploiting known group symmetries can reduce reinforcement learning sample complexity.

We would like to respectfully follow up as the author-reviewer discussion deadline approaches. We believe we have comprehensively addressed all concerns and questions raised in the review. Given that no further objections have been raised, we respectfully encourage the reviewer to reconsider the initial assessment and increase the score in light of our clarifications.

Thanks for the rebuttal.

  1. If by "uniformity" you mean that all state orbits have equal sizes, then an orbit with just one element (singleton) would force all other orbits to use size 1. Therefore, that would lead to no state space reduction. Does uniformity hold in your results?

  2. If the symmetries are already known, the PAC bound is straightforward to derive given a valid quotient MDP.

  3. "... the multiplicative reduction factors follow under additional uniformity and structural conditions. We will clarify these conditions in Proposition 1 without changing the central quotient-based result." This is still missing in the paper.

With these points in mind, I maintain my current rating.

We thank the reviewer for the follow-up and clarify the three points:

  1. Uniformity: Uniform orbit cardinality is not required for constructing a quotient MDP. Singleton orbits do not prevent other orbits from yielding state-space reductions. Uniformity is relevant only to the explicit multiplicative reduction factors, not to the general quotient construction.

  2. PAC bounds and novelty: Our main contribution is to characterize how symmetry-induced reductions affect the relevant complexity parameters, including the extension to continuous state-action spaces through quotient covering numbers. This is a valuable result because it provides a theoretical framework for quantifying the sample-efficiency benefits of exploiting symmetry, rather than merely demonstrating that symmetry-aware representations reduce the effective state space. In particular, the continuous-space analysis connects geometric structure directly to PAC sample complexity, providing a principled basis for understanding scalability in high-dimensional reinforcement learning.

  3. Proposition 1: We acknowledge that the multiplicative reduction factors require additional structural assumptions. We will explicitly state these assumptions and revise the dependent results accordingly, distinguishing them from the general quotient-based PAC bound.

Given these clarifications, we respectfully ask the reviewer to reconsider the central contribution independently of the conditional multiplicative reduction factors and reassess the assigned score.

Reviewer_o4ECOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

Estimates on the sample complexity of learning in MDP homomorphisms using PAC bounds from Dann and Brunskill (2015). They also extend their results to continuous state-action spaces and provide experimental results to test their bounds.

Critical strengths

The paper is well written and easy to follow.

The authors provide experimental results that appear to mostly match the bounds presented by the authors.

The paper formalizes an intuition, MDP homomorphisms create abstract MDPs with fewer states and actions. Fewer states and actions means learning can converge more quickly.

Critical weaknesses

The theory plugs in the bounds from Dann and Brunskill (2015) into the MDP homomorphism framework and provides new bounds. However, I am not sure what I have learned from this result. It seems pretty clear that fewer states and actions lets an agent learn more quickly. I would like the authors to discuss the significance of the contribution of these bounds.

Questions for authors

What future work does these results lead to? Does Proposition 1 require that all orbits are the same size?

4 comments

We thank the reviewer for their constructive feedback and for recognizing the clarity of our presentation and the agreement between our theoretical predictions and empirical results. We address the concerns regarding the significance of our theoretical contributions, the assumptions of Proposition 1, and future research directions below.

Significance and novelty of the theoretical results. We respectfully disagree that our contribution is simply the observation that fewer states and actions lead to faster learning. While this intuition is well established, it does not provide a quantitative characterization of how group symmetry affects reinforcement learning sample complexity. Our contribution is to establish an explicit connection between the algebraic structure of group symmetries, the induced MDP homomorphisms, and PAC sample-complexity guarantees. In particular, Theorems 1 and 2 characterize how symmetry-induced reductions in the effective state-action space translate into upper and lower sample-complexity bounds. These results make the dependence on symmetry explicit and provide a theoretical framework for quantifying the benefits of exploiting structural redundancy.

Importantly, our analysis is not restricted to finite state-action spaces. Theorem 3 extends the framework to continuous domains by characterizing sample complexity through the covering numbers of quotient state and action spaces under appropriate regularity assumptions. This extension is particularly relevant to robotics, where continuous configurations and geometric symmetries arise naturally. Together, these results provide a quantitative connection between group-theoretic structure and learning efficiency, rather than relying solely on the intuitive benefits of state-space reduction.

Clarification of Proposition 1. We thank the reviewer for highlighting the orbit-size assumption. The multiplicative cardinality expressions in Proposition 1 apply when the corresponding orbits have uniform cardinality. For general group actions, orbit sizes may differ due to nontrivial stabilizers, and the quotient cardinality must be determined by counting distinct orbits. We will clarify this assumption and express the general result directly in terms of the quotient state and admissible state-action cardinalities, recovering the multiplicative reduction factors under the appropriate uniformity conditions. We will also clarify the additional conditions required for a reduction in local successor-state complexity. These refinements preserve the underlying quotient-MDP sample-complexity formulation while making its applicability more precise.

Future research directions. Our results establish a foundation for several directions. First, extending the analysis to approximate symmetries would enable guarantees for environments in which geometric or physical symmetries are only partially preserved. Second, developing symmetry-aware exploration algorithms could translate the theoretical reductions into algorithms with explicit sample-efficiency guarantees. Third, extending the framework to learned symmetry representations and equivariant world models would enable its application when the relevant group structure is not known in advance. These directions are particularly relevant to robotic learning, where exploiting geometric structure can reduce costly environment interactions.

We will strengthen the revised manuscript by clarifying the assumptions underlying the quotient construction and expanding the discussion of the theoretical significance and practical implications of our results.

We would like to respectfully follow up as the author-reviewer discussion deadline approaches. We believe we have comprehensively addressed all concerns and questions raised in the review. Given that no further objections have been raised, we respectfully encourage the reviewer to reconsider the initial assessment and increase the score in light of our clarifications.

Thank you for your response. I maintain my original score. I am not convinced the impact of the theoretical contributions is significant.

We respectfully disagree with the reviewer's assessment. Our rebuttal explicitly clarified the theoretical contributions, including the quantitative characterization of symmetry-induced sample-complexity reductions and the extension to continuous state-action spaces through quotient covering numbers. These results go beyond the qualitative observation that smaller MDPs require fewer samples.

We would appreciate a more specific explanation of why these contributions are considered insignificant, particularly given that the reviewer has not identified substantive technical objections to these results. We respectfully encourage the Area Chair to consider the theoretical contributions and our detailed clarifications when evaluating the paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Lack of Reviewer Engagement

Dear Area Chair,

We would like to emphasize the lack of reviewer engagement during the author–reviewer discussion period. We addressed the concerns raised by the three reviewers and subsequently posted follow-up comments, yet none has responded. We respectfully request that the Area Chair consider this lack of engagement and independently assess our rebuttals when making the final decision, including reconsideration of the initial scores to ensure a fair evaluation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.