- Rating
- 3(+1)
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper models transition densities with normalized squared feature expressions. It proposes Squared Family UCRL, an optimistic RL algorithm with a sublinear regret bound under known-feature, realizability, and regularity assumptions. Its practical method, RESNEF, uses squared neural families with analytically computable normalizers to learn transition models by maximum likelihood. It also expresses this neural construction as a linear transition model through a quadratic feature expansion. Experiments compare RESNEF and a random-feature variant with representation-learning baselines on continuous-control tasks. The regret guarantee is limited to Squared Family UCRL and does not extend to RESNEF.
Critical strengths
-
For the selected neural features and base measures, the squared family gives nonnegative transition densities whose normalizers can be computed analytically. This allows direct maximum likelihood training and addresses the normalization difficulty in expressive energy-based transition models.
-
The authors construct likelihood-based confidence sets using Hellinger geometry and a martingale argument. They use these sets to establish sublinear regret for an optimistic RL algorithm under the stated assumptions.
Critical weaknesses
-
There is a gap between the regret analysis and the practical algorithm. The theoretical algorithm is not directly implementable as presented. RESNEF uses neural networks and relaxes the theoretical assumptions, so the regret guarantee does not cover its design.
-
The empirical gains are inconsistent across tasks. Results from four random seeds also provide limited evidence about how reliably the method improves performance.
Questions for authors
I understand that RESNEF does not satisfy the assumptions used to establish the regret bound. Could you evaluate RESNEF on a MDP with a computable optimal policy, measure its cumulative regret as the number of environment steps increases and compare the observed regret with the regret bound in Theorem 4.6?
5 comments
Thank you for the clarification. I understand that the paper does not claim to fully close the theory–practice gap. However, the connection between the theoretical and empirical contributions remains insufficiently established, and I remain unconvinced that they jointly address a central research question.
My request concerned measuring RESNEF’s empirical regret. I acknowledge that Theorem 4.6 does not apply to RESNEF. Nevertheless, this evaluation would provide useful evidence about its learning behavior and help assess the practical relevance of the theoretical framework.
I appreciate the authors’ response, but my concerns remain unresolved, and I therefore retain my original rating.
Thank you for you reply. We respectfully disagree that the theoretical and empirical contributions lack a sufficiently strong connection or fail to address a central research question. A central objective of our work is to establish squared families as a theoretically sound class of transition models for sample-efficient RL, while demonstrating that their tractable likelihoods enable practical representation learning that remains closely aligned with the theoretical formulation. Specifically,
- Shared probabilistic framework. Definition 5.1 builds on top of SNEFY, a subclass of squared families defined in Definition 4.1. We have derived definition 5.1 from the feature embedding setting given just below Definition 4.1. We have also shown just below Definition 5.1 that it can be re-written in pretty much the same format as the one in Definition 4.1.
- Preservation of MLE. Definition 5.1 provides tractable normalisation term, which allows us to perform parameter estimations using MLE, essentially line 3 of the theoretical Squared Family UCRL algorithm. Retaining MLE for the same density models from theory and practice is therefore a substantive step towards bridging the theory–practice gap, rather than merely a superficial connection between two separate contributions.
- Connection to the random feature setting. Our theory considers known feature setting, and in fact, the variant RESNEF-RF freezes the kernel after random initialisation (acting like the random feature setting provided after Definition 4.1), making (equivalent to the parameter in Definition 4.1) the only learnable part. This makes RESNEF even closer to the theoretical formulation and in fact, it also performs well across many tasks as shown in the experiment while saving half of the training time budget compared to RESNEF (see our replies to 6taw).
There is always some sort of gap between sharp theory and scalable algorithm. In our case, the biggest gap comes from the planning module, as RESNEF replaces the planning around the confidence set (line 4 and 5 of Squared Family UCRL) with the actor critic framework. Acknowledging such gap exists, we hence provide empirical evidence by comparing RESENF against two strongest representational actor critic methods CTRL and DiffSR and one classic model free actor critic algorithm SAC. The fast-growing evaluation returns of RESNEF and RESNEF-RF hence demonstrates their sample efficiency.
Constructing a meaningful continuous-control benchmark with a computable optimal policy is challenging, and such evaluations are not generally required in this line of representation-learning research (Jin et.al., 2020, Agarwal et.al., 2020, Chowdhury et al., 2021, Uehara et. al., 2021, Zhang et.al., 2022, Shribak et al., 2024). Even if the regret is known, as we have mentioned in the last reply, comparing RESNEF’s regret against Theorem 4.6 is not informative because the theoretical algorithm does not match the practical algorithm. Since small cumulative regret corresponds to fast growing returns, the most widely adopted method to test the sample efficiency of empirical algorithms is to compare their return-to-environment-interaction curves against other baselines. This is exactly what we have done in our experiments to show the effectiveness of sticking to squared family MDP and estimating parameters with MLE for solving RL problems. Better yet, our empirical evidence is not only from toy simple problems, but more realistic and scalable continuous control problems across wide range of settings.
In summary, we respectfully maintain that our theoretical and empirical contributions address a coherent research question from complementary perspectives: whether squared-family transition models enable statistically efficient RL in theory, and whether their tractable likelihood structure can be exploited to improve practical representation learning. We have explicitly identified the remaining theoretical limitations and do not claim a regret guarantee for RESNEF. We believe the concrete methodological connections and extensive empirical evidence establish a considerably stronger theory–practice relationship than the reviewer's latest assessment suggests.
To reviewer RPPg,
Thank you for the review and for highlighting the theory-to-practice gap. We agree that the regret theorem does not directly cover RESNEF, and we already identify this as a limitation in Section 7. However, we would like to clarify why we view the theoretical and practical components as complementary rather than disconnected. It is actually our intention to close the theory to real gap along this line of research, as existing empirical works needs to bypass the MLE computation suggested by the theory, but we are the first to propose a theoretical framework that retains sharp regret bound under MLE and keeps MLE in the practical algorithm. Please see each of our point below.
W1: Gap between Squared Family UCRL and RESNEF
The theoretical contribution asks whether squared-family transition models admit statistically efficient RL under a standard realizable, known-feature setting. Squared Family UCRL answers this question by combining MLE concentration, confidence sets, optimistic planning, and an elliptical-potential argument.
The practical contribution addresses a different obstacle: making the likelihood-based representation learning mechanism itself tractable. Existing practical representation-learning methods such as CTRL and DiffSR are motivated by related low-rank/linear-MDP theory, but replace MLE with NCE or score matching because their probabilistic normalisers are intractable. SNEFY provides analytically tractable normalisation, allowing RESNEF to retain the MLE mechanism suggested by the theory while learning nonlinear representations.
We therefore do not claim that Theorem 4.6 is a regret guarantee for RESNEF. Rather, the theory establishes squared families as a statistically well-behaved transition class under MLE, and RESNEF demonstrates that the same tractability property can be exploited for learning representation using MLE and achieve good performances especially when compared to other representational approaches. We will sharpen this distinction in the introduction and limitations section.
Q1: Evaluating RESNEF against Theorem 4.6
We appreciate the suggestion to measure cumulative regret on an MDP with a computable optimal policy. Such an experiment could be useful for studying the empirical behaviour of the theoretical algorithm. However, directly comparing RESNEF’s regret to the bound in Theorem 4.6 would not constitute a meaningful verification of that theorem, because RESNEF neither implements the confidence-set optimistic planner analysed in Theorem 4.6 nor satisfies all of its assumptions. Agreement with, or violation of, the bound by RESNEF would therefore say little about the correctness or tightness of Theorem 4.6.
A faithful empirical test of the theorem would instead require implementing Squared Family UCRL on a deliberately constructed MDP with known features and realizable squared-family transitions, and repeatedly solving the confidence-set-constrained optimistic planning problem. That computational difficulty is precisely one of the motivations for introducing RESNEF as a practical relaxation. We will make this distinction explicit so that the theoretical guarantee is not interpreted as applying to the practical algorithm.
W2: Empirical variability and number of seeds
We agree that the gains are not uniform across tasks, and we will moderate the corresponding language in the abstract. Nevertheless, the overall empirical evidence is stronger than the weakest individual cases suggest.
Against the closely related representation-learning baselines (i.e. DiffSR and CTRL), RESNEF/RESNEF-RF achieve the best performance on 6 of 8 Gymnasium tasks and 4 of 5 DMC tasks. The MLE-versus-score-matching ablation further isolates the estimation objective: replacing MLE with score matching while keeping the RESNEF architecture otherwise fixed reduces performance. These results support our narrower claim that tractable MLE is a useful mechanism for learning transition representations, not that our method uniformly dominates every model-free or representation-learning algorithm. Meanwhile, our results are also not dominated by SAC either, as many settings our approaches perform better than SAC, hinting the usefulness of learning good representations.
We use four independent random seeds for all methods and report standard errors. Four seeds are also used by the compared baselines and are common in continuous-control evaluations under substantial computational cost.
Summary
Thank you again for the review. We hope the clarification above makes the big picture more clear: the theorem establishes sample-efficient learnability of the squared-family model class under explicit assumptions, while RESNEF exploits the same tractable likelihood structure to move practical representation learning closer to that theoretical mechanism. If these clarifications address the concerns, we would appreciate reconsideration of the rating as appropriate.