- 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
Follow-up
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.
Rebuttal
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) to 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)}∣. The multiplicative expression Cˉ=C/∣GC∣ 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.