acceptodds
Under review as a conference paper at ICLR 2027

Sample-Efficient Reinforcement Learning with General Utilities via Neural Dual Critics

Abstract

Reinforcement learning with general utilities optimizes nonlinear functionals of policy-induced occupancy measures. We develop a natural actor-critic method for concave RLGU objectives admitting an exact variational dual representation, with explicit constructions for a broad class of separable occupancy utilities. Rather than estimating the occupancy measure and then forming the policy-gradient pseudo-reward, our method learns this pseudo-reward directly as a function of the state-action pair using a neural critic. The critic is trained by projected stochastic updates, while multilevel Monte Carlo combines outputs across training horizons to control its bias at logarithmic expected cost. Our analysis separates conditional actor bias from estimator second moments and accounts explicitly for dual optimization, critic approximation, and neural linearization errors. Under policy-transfer, dual-stability, and local critic-regularity conditions, the method achieves global convergence above policy, critic-class, and finite-width approximation errors using expected environment transitions and reference samples. For a fixed critic representation, this yields sampling complexity above the approximation floor, covering infinite state-action spaces and occupancy utilities beyond fixed finite vectors of returns.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning with general utilities, concave utility RL, occupancy measure optimization, natural actor–critic, neural dual critics, Fenchel duality, multilevel Monte Carlo, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FqL5OpenReview ↗
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 O~(ϵ−4)\widetilde O(\epsilon^{-4}) guarantees of prior occupancy-approximation methods to O~(ϵ−2)\widetilde O(\epsilon^{-2}), 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 ϵ−4\epsilon^{-4} to ϵ−2\epsilon^{-2}, 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 Dm>∣S∣∣A∣D_m>|\mathcal S||\mathcal A|. 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

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)H_{\max}(\eta_m^2+\gamma^{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.

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.

  1. 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 rr applies to it directly. With a neural critic, curvature in rr 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 ζ\zeta requires the tangent-feature Gram condition (Assumption 10, Eq. (22)), giving effective curvature μcκ\mu_c\kappa. Eq. (25) quantifies the resulting dimension–conditioning trade-off.

    • (ii) Persistent gradient bias: Evaluating the nonlinear network inside ∇Ψ\nabla\Psi 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 L2L^2 approximation of the exact pseudo-reward; Proposition 3 relates these quantities.

  2. 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 Hmax⁡qmH_{\max}q_m second moment, with qm=ηm2+γ2Bq_m=\eta_m^2+\gamma^{2B}, 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 O~(ϵ−2)\widetilde O(\epsilon^{-2}) 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.

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

This paper proposes a natural actor-critic method for concave RLGU objectives with general utilities, which learns a neural pseudo-reward through variational duals, and thus avoids explicit occupancy estimation. Under four key assumptions and several auxiliary regularity conditions, the paper provides an O(ϵ−2)O(\epsilon^{-2}) sample complexity bound for the proposed method under a fixed-critic representation.

Critical strengths
  1. The research topic and the proposed method are well-motivated. Connection to concave utility RL is extensively and clearly discussed in Appendix F.
  2. The technical contributions are solid. The dual reward learning scheme and the critic bias control methods are novel and potentially generalizable to other RL algorithms.
  3. The theoretical analysis is well-articulated and technically sound. The proof sketch is very informative and promotes understanding.
Critical weaknesses
  1. Many assumptions are needed to derive the final theoretical guarantee. Although detailed discussions and remarks are provided right after the introduction of key assumptions, it is still unclear whether these assumptions hold in any, if not all, of the real-world use cases.
    • It would be helpful to figure out empirical methods for testing the validity of these assumptions.
    • It would also be helpful to establish theoretical results on the effects of "slightly" violated assumptions.
    • I appreciate that detailed discussions and concrete examples are provided in Section E for separable utility duals.
  2. Empirical evaluation is completely missing. Despite the theoretical nature of this paper, it would still be helpful to provide at least a working simulation to justify the practical value of the proposed algorithm.
Questions for authors

See weaknesses above.

2 comments

We thank the reviewer for recognizing the technical contributions and for the helpful suggestions on assumption validity and empirical evaluation. We address these points below.

Response to weakness 1:

Applicability: Relevant examples are discussed in [Ganesh et al. (2025a)], Section 4 “Comments on Assumptions 5–7”, and [Satheesh et al.], Section 5.1, covering softmax, Gaussian, and certain neural policy parameterizations. Neural-critic regularity is discussed in [Ganesh et al. (2025a)], Assumption 2 and Lemma 6, and [Satheesh et al.], Assumption 4 and Lemma 15. Appendix E of our paper provides complementary examples for the utility-specific dual assumptions.

Empirical checks: Fisher and tangent-feature Gram eigenvalues can be estimated from policy and reference samples, respectively. Score norms, score differences, linearization residuals, and utility-specific reward ranges provide further diagnostics. These checks can reveal violations but cannot certify uniform validity; transferred compatibility is harder to test because it involves the optimal comparator’s occupancy.

Slight violations: Theorem 1 already allows nonzero compatibility, critic-approximation, and linearization errors through its approximation floor. Additional conditional dual-oracle bias bounded by ξ\xi replaces dvd_v by dv+ξd_v+\xi in Equation (49), yielding Ek∣ζH−ζk∗∣2≤Ac/(H+1)+(dv+ξ)2/(μcκ)2\mathbb E_k|\zeta_H-\zeta_k^*|^2\leq A_c/(H+1)+(d_v+\xi)^2/(\mu_c\kappa)^2 under the same second-moment bound. Smaller positive conditioning constants worsen the bounds; loss of non-degeneracy requires further analysis.

Response to weakness 2: Please refer to our response to Reviewer WMwz, Weakness 3, regarding empirical evaluation.

References:

[Ganesh et al. (2025a)]: S. Ganesh, J. Chen, W. U. Mondal, and V. Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In Conference on Uncertainty in Artificial Intelligence, 2025a.

[Satheesh et al.]: A. Satheesh, P. K. Barman, W. U. Mondal, and V. Aggarwal. Global convergence of average-reward-constrained MDPs with a neural critic and general policy parameterization. In Conference on Uncertainty in Artificial Intelligence, 2026.

I thank the authors for their clarifications and responses. I'll keep my rating and lean towards acceptance of this paper.

Reviewer_WMwzOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents a novel algorithm for the problem of RL with general utilities (RLGU), in which the objective is defined as a nonlinear function of the state occupancy probabilities. While prior work has addressed this problem in environments with finite state and action spaces, this work develops an algorithm that is applicable to infinite state and action spaces, representing both the policy and the pseudo-reward as parametric functions. The paper presents an end-to-end theoretical analysis of the algorithm, yielding strong guarantees on the regret of policies learned via this algorithm.

Critical strengths
  1. The paper combines several techniques to derive a novel algorithm for RLGU that can be applied with neural function approximation to large or infinite state-action spaces. This method does not require explicit estimation of the state-action density under a policy, and instead learns the pseudo-reward directly as a scalar function, removing a major technical challenge for scalable RLGU.
  2. The paper provides a through analysis of the proposed algorithm, with strong sample complexity guarantees that do not require restrictive assumptions on the underlying MDP (that is, the MDP need not have bounded rank). These guarantees match or exceed (asymptotically) the best complexity guarantees for RLGU in MDPs with finite state and action spaces. Complete, rigorous proofs of these results are provided in the appendices, and all technical assumptions are stated clearly.
Critical weaknesses
  1. The characterization of the sample complexity results from the most closely related work (Barakat et al., 2026) may not be entirely correct. As I understand this previous work, they derive an algorithm that, in principle, should also be applicable to infinite state spaces (even if they only provide sample complexity results only for finite state and actions spaces). Furthermore, they report O(mϵ−2)O(m \epsilon^{-2}) sample complexity (Corollary 1) rather than O(mϵ−2)O(m \epsilon^{-2}).
  2. Where the sample complexity of previous work depends on the rank mm of the MDP, the sample complexity of the current algorithm is independent of the underlying MDP itself, and depends instead on the parameterization of the policy and the critic (the pseudo-reward estimator). While Theorem 1 clearly expresses the irreducible error ϵapp\epsilon_{\text{app}} introduced by the inability of the critic to represent the exact dual reward, the dependence on the complexity of the critic and policy networks is less clear. For example, the term ηm\eta_m depends on the size mm of the hidden layers of the critic, but it is unclear how the bound depends on he number of critic layers LL. It is also unclear how the bound depends on the complexity of the parametric policy space.
  3. The work presents no empirical results, so the practical efficacy of the method it not entirely clear.
Questions for authors
  1. Would constrained RL objectives with convex boundary functions be compatible with Assumption 3? In other words, would this method be applicable to constrained RL?
  2. Is the constant CC in Equation 11 distinct from the constant CC used in the sample complexity bounds in Theorem 1? (My assumption is that it is not.)
  3. Does constant CC in Theorem 1 (Equation 27) depend in any way on the complexity of the policy or critic space (for example, on the number of critic layers LL)?
  4. In Assumption 3, is cc a constant,and if so, what does it mean for cc to be measurable?
  5. In Theorem 1 (Equation 27) the parameter TT is set to T=KT = K, where KK is the number of iterations of the algorithm. Is there a reason why a separate symbol TT is used on the right hand side of Equation 27 if TT and KK are assumed to be identical?
2 comments

We thank the reviewer for the positive assessment of our contributions and theoretical analysis, as well as for the helpful questions and suggestions. We address each point below

Weakness 1: Corollary 1 of [Barakat et al.] gives O~(ϵ−2)\widetilde O(\epsilon^{-2}) complexity for stationarity, E∥∇θF(λθ)∥2≤ϵ\mathbb E\|\nabla_\theta F(\lambda_\theta)\|^2\leq\epsilon. Their global-optimality guarantee in Corollary 2 requires O~(ϵ−4)\widetilde O(\epsilon^{-4}) samples. Table 1 compares global-optimality guarantees unless otherwise marked. Regarding infinite spaces, Remark 3 states that their algorithm can be applied to continuous state–action spaces. However, Remark 2 explicitly restricts their analysis to finite spaces, and their conclusion lists continuous state–action extensions as future work. Our table concerns established theoretical guarantees, rather than algorithmic applicability.

Weakness 2: The bound constant CC in Theorem 1, Equation (27), is independent of TT, but depends on critic regularity and conditioning, including (μcκ)−2(\mu_c\kappa)^{-2} in Equation (50). Depth enters through these constants, Dm=mp+(L−1)m2D_m=mp+(L-1)m^2, and the Hessian constant CHC_H in ηm≤CHR2/(2m)\eta_m\leq C_HR^2/(2\sqrt{m}). Equation (25) further gives Dmκ≤ν0Cϕ2D_m\kappa\leq\nu_0C_\phi^2. Policy dependence enters through G1,G2,μF,Φ0G_1,G_2,\mu_F,\Phi_0. Thus, this is a fixed-representation guarantee, without an explicit depth bound. No low-rank assumption is required, but occupancy-dependent constants such as μF\mu_F can depend on the MDP.

Weakness 3: Our focus here is on establishing theoretical sample-complexity guarantees; assessing practical efficacy is an important direction for future applied work.

Question 1. For constraints gi(λ)≤0g_i(\lambda)\leq 0 with convex gig_i, the fixed-multiplier Lagrangian F(λ)−∑iyigi(λ)F(\lambda)-\sum_i y_i g_i(\lambda) is concave for yi≥0y_i\geq 0. It is compatible with Assumption 3 when it has the stated separable form and satisfies the regularity conditions; convexity alone does not ensure this. Our approach could therefore serve as a component of a primal–dual method. However, multiplier updates and constraint-violation guarantees require additional analysis and are not covered by Theorem 1.

Question 2. They are distinct. In Equation (11), CC is an additive constant that defines the utility; it cancels out in both the optimality gap and the learning updates. In Theorem 1, CC denotes a bound constant depending on the stated regularity parameters. We will rename the constants accordingly to avoid confusion.

Question 3. Please refer to our response to Weakness 2 above.

Question 4. Here c:S×A→Rc:\mathcal S\times\mathcal A\to\mathbb R is a fixed measurable function on the state–action space. Its contribution −Eλθ[c]-\mathbb E_{\lambda_\theta}[c] is a linear occupancy term. For example, quadratic density matching uses c(s,a)=−q(s,a)c(s,a)=-q(s,a), where qq is the target density.

Question 5. KK denotes the number of outer iterations, while TT is the common scaling parameter for the choices in Theorem 1, where K=TK=T. There is no essential distinction in that theorem; we will use KK throughout to simplify the notation. Neither denotes the total number of environment transitions, whose expected count is given separately in Equation (56).

I believe this response addresses all of my questions, thank you

Comments on the paper

3 comments
Area_Chair_vbt6OpenReview ↗

Questions to Authors

Dear authors,

I have a few questions regarding the contributions, their scope, and their positioning relative to prior RLGU work.

I appreciate that there is limited time remaining in the discussion period. Brief clarifications based on the existing analysis would be very helpful, particularly regarding the scope of the assumptions and the comparison with prior work.

  1. Comparison of guarantees in Table 1. Could Table 1 specify, for each result, whether the guarantee concerns a random iterate or the last iterate, and whether it gives ϵ\epsilon-optimality or accuracy above a fixed approximation error floor? My understanding is that Theorem 1 controls the average expected optimality gap (equivalently the expected gap of a uniformly selected iterate), whereas some prior global optimality guarantees, including Zhang et al. 2020, 2021 and Barakat et al. 2025, concern the last iterate. Could the authors clarify in what respects the result strengthens or complements prior guarantees, given these differences?

  2. What improvement specifically requires the dual critic? The dual formulation provides a sample-based objective for learning the pseudo-reward. Beyond this, which part of the improved sample complexity analysis specifically requires duality? In particular, could the same MLMC construction be applied to Rn=∇F(λ^n)R_n= \nabla F(\widehat\lambda_n), where nn is the sample or training budget of an occupancy estimator? What advantage does the dual formulation provide in establishing the error and moment bounds required by this construction, compared with occupancy estimation under comparable assumptions?

  3. Structural conditions for zero critic approximation error. Could the authors provide verifiable conditions on the MDP, utility, and policy parameterization under which the critic approximation error in Assumption 11 is zero (or even small if it cannot be zero), uniformly over the relevant policies, for a specified fixed tangent-feature class? A nontrivial class, preferably with continuous state or action spaces, would help clarify this assumption. Can such a class also satisfy the remaining assumptions along Algorithm 1 with zero total approximation error floor and constants independent of the target accuracy, yielding an expected ϵ\epsilon-optimal uniformly selected iterate with O~(ϵ−2)\widetilde O(\epsilon^{-2}) expected samples?

  4. Comparison of assumptions and applicability to the tabular setting. How do the policy and critic assumptions required for Theorem 1 compare with those underlying the linear and parametric occupancy-estimation results cited in Table 1? Which conditions are relaxed, strengthened, or incomparable? In particular, can Algorithm 1 be used without modification in the finite state-action setting, and does Theorem 1 apply with a tabular critic and direct or softmax policy parameterization? Which assumptions become automatic in this specialization, and which require additional restrictions?

Best regards,

AC

Thank you for these questions. We clarify the guarantees, role of duality, and assumptions below.

Question 1: Guarantees and improvement: We will add output-iterate and accuracy-target columns to Table 1. For fixed representation and problem constants, Theorem 1 gives E[F⋆−F(λθτ)]≤Δ+ϵ\mathbb E[F^\star-F(\lambda_{\theta_\tau})]\leq\Delta+\epsilon for a uniformly selected iterate, using O~(ϵ−2)\widetilde O(\epsilon^{-2}) expected environment transitions, where Δ\Delta constitutes function-approximation floor.

While the prior last-iterate guarantees have no fixed approximation floor, they all assume finite spaces. Zhang et al. (2020)'s global analysis additionally assumes exact gradients; Zhang et al. (2021) achieve O~(ϵ−2)\widetilde O(\epsilon^{-2}) through tabular occupancy estimation; and Barakat et al.'s O~(ϵ−4)\widetilde O(\epsilon^{-4}) Corollary 2 requires exact occupancy realizability. Our theorem extends the ϵ−2\epsilon^{-2} exponent to neural dual-reward learning in infinite spaces, including both critic training and policy optimization samples. Its floor explicitly quantifies the representation errors allowed in this setting.

Question 2: Role of duality: In continuous spaces, the occupancy-based approach may face density-estimation rates slower than H−1H^{-1} in mean square. If squared level differences are only controlled by O(2−βj)O(2^{-\beta j}) with 0<β<10<\beta<1, our MLMC calculation yields an O(Hmax⁡1−β)O(H_{\max}^{1-\beta}) bound for the statistical second-moment term, instead of logarithmic growth. Our dual analysis establishes the H−1H^{-1} training-error term directly for the reward under its stated assumptions.

Our dual objective uses occupancy samples through an expectation. Dual curvature and tangent-feature conditioning give effective curvature μcκ\mu_c\kappa; Lemma 3 bounds the trained reward's conditional mean-square error relative to the constrained dual minimizer by C/(H+1)+C(ηm2+γ2B)C/(H+1)+C(\eta_m^2+\gamma^{2B}). Proposition 3 relates that minimizer to the exact reward. These bounds yield Lemma 4's MLMC moments, including Hmax⁡(ηm2+γ2B)H_{\max}(\eta_m^2+\gamma^{2B}), and feed Lemma 2's NPG analysis. Parametric density estimators may also supply these bounds. Our contribution establishes these bounds directly for neural reward learning, including optimization error, without density estimation.

Question 3: Exact approximation and scope: Consider a one-state MDP with actions in [−1,1][-1,1], policies pθ(a)=eθa/Zθp_\theta(a)=e^{\theta a}/Z_\theta relative to the uniform measure, and F(λ)=−KL(λ∥Q)F(\lambda)=-\mathrm{KL}(\lambda\|Q), where Q=πβQ=\pi_\beta is available through samples. For ∣θ∣,∣β∣≤M|\theta|,|\beta|\leq M with fixed M>0M>0, rθ(a)=(β−θ)a+log⁡Zθ−log⁡Zβ−1r_\theta(a)=(\beta-\theta)a+\log Z_\theta-\log Z_\beta-1. The critic rζ(a)=ζ1+ζ2ar_\zeta(a)=\zeta_1+\zeta_2a, centered at (−1,0)(-1,0) with radius 22M2\sqrt{2}M, contains every such reward, giving εapp=ηm=0\varepsilon_{\rm app}=\eta_m=0. With ν=Q\nu=Q, G⪰(e−2M/3)IG\succeq(e^{-2M}/3)I. Appendix E's KL dual has uniform curvature and bounded oracle moments on this critic ball.

Moreover, uθ(a)=a−Eπθ[a]u_\theta(a)=a-\mathbb E_{\pi_\theta}[a] and Aθ(rθ)=(β−θ)uθA_\theta^{(r_\theta)}=(\beta-\theta)u_\theta, so εbias=0\varepsilon_{\rm bias}=0. Score regularity and finite initial KL hold, and I(θ)=Varπθ(a)≥e−2M/3I(\theta)=\mathrm Var_{\pi_\theta}(a)\geq e^{-2M}/3. All constants are accuracy-independent on this fixed interval, giving the zero-floor O~(ϵ−2)\widetilde O(\epsilon^{-2}) guarantee if the iterates remain there. The zero-floor conclusion holds provided Algorithm 1’s iterates remain in the fixed interval; establishing this property for the unprojected updates requires a separate argument.

Question 4: Assumptions and tabular specialization: The linear-occupancy result (Barakat et al., 2023, Section 5) also assumes approximation-error bounds and feature conditioning, but establishes stationarity. Our global guarantee adds Fisher non-degeneracy and transferred compatibility. These replace the parametric-occupancy global result's local invertibility condition; reward-approximation bounds replace occupancy realizability. We additionally require the dual regularity, linearization, and oracle conditions above. The assumption sets are generally incomparable.

Finite spaces require no change to Algorithm 1. A tabular critic with one-hot inputs and identity activation has ηm=0\eta_m=0; full-support ν\nu gives G≻0G\succ0, and a ball containing all exact rewards gives εapp=0\varepsilon_{\rm app}=0. With this critic and tabular softmax, Assumptions 4–6 hold automatically. Removing redundant logits and ensuring uniform state coverage and action probabilities bounded away from zero along updates give Fisher non-degeneracy and εbias=0\varepsilon_{\rm bias}=0; these uniform bounds are not automatic. Utility/dual conditions (Assumptions 1, 2, 9) remain necessary. Direct probability parameters require positive lower bounds for score regularity and simplex feasibility. The additive actor update does not ensure these; modifications need corresponding analysis.

Dear Authors,

Thank you for your responses.

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.