- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies reinforcement learning with general utilities, formulated as concave, potentially nonlinear functionals of policy-induced state–action occupancy measures. The authors combine dual pseudo-reward learning with multilevel Monte Carlo (MLMC) estimation and natural policy gradient (NPG). By reducing the expected critic-training cost at each outer iteration, the method improves the expected sample complexity from the guarantees of prior occupancy-approximation methods to , above a fixed approximation floor under the stated assumptions. The theoretical analysis appears sound, and the results are supported by the analysis.
However, the technical novelty appears limited. The approach closely follows the MLMC–NPG framework in Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning, which similarly uses randomized multilevel corrections to control estimation bias at low expected sampling cost. The dual formulation of general utilities is also established in prior work. The main extension therefore lies in applying this framework to learned, function-valued pseudo-rewards and accounting for critic optimization, approximation, and linearization errors. While this extension is relevant, it remains unclear whether it requires sufficiently substantial new technical insights beyond combining existing techniques.
Critical strengths
Compared with existing results the sample complexity the author derive improve from to , the proof and analysis is solid.
Critical weaknesses
The analysis appears to adapt existing MLMC-NPG techniques to general utility RL through a learned dual reward. Moreover, Risk-Sensitive RL with Optimized Certainty Equivalents via Reduction to Standard RL already establishes augmented-MDP reductions for a broad class of utility-based objectives and applies natural policy gradient. Although that reduction does not directly cover arbitrary occupancy utilities, these existing results make the additional methodological novelty unclear. The authors should clarify which technical challenges in their formulation require substantial new analysis beyond the established MLMC-NPG framework and utility-based RL reductions.
Questions for authors
Lemma 6 suggests that increasing the network width reduces the linearization error, but Equation (25) indicates that this can worsen the conditioning of the Gram matrix. For finite state–action spaces, Assumption 10 also fails once . Could the authors provide a concrete regime in which the width and parameter radius make both the linearization and critic approximation errors small, without the conditioning-dependent constants offsetting these improvements?
5 comments
My question has been addressed. I acknowledge that learning a function-valued pseudo-reward differs from estimating scalarization derivatives in finite-objective MLMC–NPG. However, dual pseudo-reward learning is already established in tabular RLGU. The main extension is neural reward approximation in infinite spaces, together with training and linearization error bounds. The additional NPG analysis largely propagates reward bias and second moments through the existing convergence framework, with an adjusted stepsize. While the resulting guarantee is useful, I view this as an incremental combination of established techniques without sufficiently substantial new analytical insights. I therefore maintain my rating of 2.
Thank you for the follow-up. While the individual tools (Fenchel duality, MLMC, approximate NPG) are established, the difficulty our analysis addresses is learning the dual reward itself with a parametric critic in continuous spaces, which is where the tabular setting and our setting differ. We clarify this below.
-
Dual reward learning beyond the tabular case: In tabular RLGU (e.g., [Zhang et al., 2020]), the dual reward is itself the optimization variable, a finite-dimensional vector, so any curvature of the dual objective in applies to it directly. With a neural critic, curvature in does not imply curvature in the critic parameters. Lemma 3 has to handle three issues that do not arise in the tabular case:
-
(i) Parameter-space curvature: Strong convexity of the linearized dual objective in requires the tangent-feature Gram condition (Assumption 10, Eq. (22)), giving effective curvature . Eq. (25) quantifies the resulting dimension–conditioning trade-off.
-
(ii) Persistent gradient bias: Evaluating the nonlinear network inside while updating along frozen tangent features creates a gradient discrepancy that does not vanish with further training. Eqs. (47)–(50) track this term, together with trajectory truncation, and establish convergence to a controlled neighborhood of the constrained dual minimizer.
-
(iii) Stochastic dual oracle: The functional-derivative term must be estimated from reference samples. Proposition 1 and Table 2 construct these estimators for concrete occupancy utilities, and Eq. (56) includes their sampling cost in the overall guarantee.
Moreover, the constrained dual minimizer generally differs from the best approximation of the exact pseudo-reward; Proposition 3 relates these quantities.
-
-
Coupling the learned reward with stochastic NPG: The NPG step builds on the existing framework, but one property had to be established for it to work with MLMC: conditional on the sampled critic, the mean of the inner NPG updates is linear in the supplied reward (Appendix B, leading to Eq. (43)). This is what lets the telescoped MLMC mean, rather than its root-mean-square error, enter the actor bias, while the larger second moment, with , is confined to the stepsize-weighted term. The stepsize in Eq. (26) then controls this contribution without requiring the critic representation to grow with the sampling budget.
Together, these steps give a global-optimality guarantee above an explicit approximation floor, including the samples used to learn the pseudo-reward. Among the RLGU guarantees compared in Table 1, it is the only one established for infinite state–action spaces.
We hope this clarifies the technical contribution, and thank the reviewer for the engagement.
[Zhang et al., 2020]: J. Zhang, A. Koppel, A. S. Bedi, C. Szepesv´ari, and M. Wang. Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems, volume 33, 2020.
We thank the reviewer for recognizing the sample-complexity improvement and the strength of the analysis. Below, we clarify the technical contributions beyond prior frameworks and the role of representation-dependent conditioning.
Response to Weaknesses:
1. Comparison with MLMC–NPG for concave multi-objective RL: [Ganesh et al. (2026)] apply corrections to known scalarization derivatives evaluated at empirical returns. Our additional challenge is to learn the policy-dependent pseudo-reward itself through stochastic neural dual optimization. MLMC therefore acts on trained functions, requiring control of optimization and linearization errors across training horizons (Lemmas 3-4). Residual errors are amplified through Hmax(ηm2+γ2B); our step-size choice controls their contribution to the final approximation floor. We then propagate the conditional mean of the corrected reward through NPG while controlling the second moments separately (Lemma 2). These arguments establish logarithmic expected critic-training cost and extend the guarantee to function-valued dual rewards; substituting a learned reward into the existing framework alone does not provide these guarantees.
2. Distinction from OCE reductions: [Wang et al. (2024)] study utilities of trajectory returns. Their reduction neither covers arbitrary occupancy functionals nor supplies their policy-dependent pseudo-rewards. Appendix F additionally establishes that our objective class extends beyond fixed finite-dimensional return scalarizations.
Response to Questions: We appreciate the reviewer’s observation. This tradeoff is explicitly reflected in Equation (25), the finite-space rank restriction, and the conditioning-dependent constants in Equation (50). Our sampling improvement does not rely on increasing width: Theorem 1 fixes the representation and establishes the stated rate above its associated approximation floor. As Remark 2 already notes, growing width requires separately tracking these constants. Lemma 6 quantifies local linearization error rather than prescribing a widening strategy. The requested joint scaling regime would additionally guide representation selection, but is not required for the fixed-representation sampling guarantee established here.
References:
[Ganesh et al. (2026)]: S. Ganesh and V. Aggarwal. Breaking the bias barrier in concave multi-objective reinforcement learning. arXiv preprint arXiv:2603.08518, 2026.
[Wang et al. (2024)]: Wang K, Liang D, Kallus N, Sun W. Risk-sensitive rl with optimized certainty equivalents via reduction to standard rl. arXiv preprint arXiv:2403.06323. 2024.