acceptodds
Under review as a conference paper at ICLR 2027

Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs

Abstract

In safety-critical applications, deployment uses a single policy, whose performance and constraint satisfaction should hold directly rather than only for an average or mixture of training policies. This motivates last-iterate guarantees in constrained reinforcement learning. Recent progress has established such guarantees in exact-gradient or tabular online settings, yet scalable results for structured large-state problems remain open. We develop a general, statistically efficient framework for last-iterate convergence in structured Constrained MDPs (CMDPs). Our analysis separates contraction of the regularised primal-dual dynamics from actor approximation and statistical errors in policy evaluation under online exploration. This enables model-free on- and off-policy learning with structured function approximation: optimistic policy evaluation avoids explicit transition-model construction, while a compact parametric actor avoids maintaining mixtures or histories of past policies. We instantiate the framework for linear CMDPs and general function approximation, obtaining representation-dependent complexity and improved target-accuracy dependence over prior optimistic regularised primal-dual analyses. We further validate the stabilising effect predicted by our theory on a synthetic linear CMDP: the regularised method exhibits stable last-iterate behaviour, whereas its unregularised counterpart shows larger oscillations.

Primary area:
reinforcement learning
Keywords:
Constrained MDPs, last iterate convergence, online RL, primal-dual method, safe robotics

Reviews

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

This paper establishes last-iterate guarantees for online constrained RL in structured CMDPs, bounds on the reward suboptimality and constraint violation of the single policy the algorithm returns, rather than of an average over training iterates. The method is an entropy- and quadratically-regularised primal-dual scheme built on two oracles, an optimistic policy-evaluation oracle and a log-linear actor-fitting oracle, whose errors feed a single geometric contraction on a potential combining a KL term with the multiplier gap (Theorem 3.4). Its sharpest technical step is the conversion from the regularised saddle point back to the original CMDP, fixing the dual box radius through the Slater margin and showing the regularised multiplier stays strictly inside it removes the radius's dependence on the target accuracy, so the temperature may be taken an order larger than in prior analyses. The framework is then instantiated twice, for linear CMDPs with a model-free least-squares critic and elliptical bonuses, and for general function approximation through the eluder dimension, each under either fresh on-policy batches or cumulative off-policy data, yielding episode complexities of order ϵ−6\epsilon^{-6} off-policy and ϵ−10\epsilon^{-10} on-policy up to an actor-approximation floor.

Critical strengths
  1. The fixed dual radius, and the resulting conversion, is a clean and consequential technical contribution.
Critical weaknesses
  1. Outside the tabular case, the structured-CMDP guarantee has a non-vanishing actor floor whose smallness is never established — and the paper’s own analysis suggests it may not be small.
Questions for authors

Can you exhibit a concrete non-tabular instance — e.g. a linear CMDP with dc=da=dd_c=d_{\rm a}=d and infinite S\mathcal{S} — in which Assumption 3.2 provably holds with ϵact=O~(ξϵ3/H5)\epsilon_{\rm act}=\widetilde O(\xi\epsilon^3/H^5) and da=poly(d)d_{\rm a}=\mathrm{poly}(d)? Given your own remark at lines 883–885, what prevents the clipped, bonus-augmented critic from forcing ϵact=Ω(1)\epsilon_{\rm act}=\Omega(1) for a dd-dimensional log-linear actor?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 2dkN

Part 1

We sincerely thank the reviewer for the careful reading and constructive comments and questions. We address each point below:

Example that ϵact\epsilon_{\mathrm act} is small.

Our analysis is general enough to capture settings for any actor representation and any structured MDPs. To see how it is useful in practice, let us give some examples with small actor representations, say, ϕ=φ\phi=\varphi and dc=da=dd_c = d_a = d that achieve ϵact=0\epsilon_{\rm act} = 0.

Example 1. Large linear CMDPs with anchor state-action pairs

These MDPs may have large state spaces and complicated dynamics. However, the policy can influence the dynamics only at a small set of mm states, referred to as anchor states. All other states are passive: their transition laws are independent of the chosen action. The MDPs with anchor state-action have been studied extensively in prior work [3, 4].

Formmaly, suppose there are mm anchor states and ∣A∣|\mathcal A| actions, set dc=da=d=m∣A∣d_{\mathrm c}=d_{\mathrm a}=d=m|\mathcal A|. We use the same features for the actor and critic:

\begin{cases} e_{(s,a)}, & s\text{ is an anchor state},\\\\ p(s), & s\text{ is a passive state}. \end{cases}$$ Here $e_{(s,a)}$ is the coordinate vector for $(s,a)$, and $p(s) \in \Delta([d])$ is independent of the action. Choose arbitrary probability measures $\mu_h^{(1)},\ldots,\mu_h^{(d)}$ and reward and utility coefficient vectors in $[0,1]^d$. Define the transition law, reward, and utilities by $$P_h(\cdot\mid s,a)=\sum_{i=1}^d\phi_i(s,a)\mu_h^{(i)}(\cdot), \qquad r_h(s,a)=\langle\phi(s,a),\upsilon_{r,h}\rangle, \qquad u_{i,h}(s,a)=\langle\phi(s,a),\upsilon_{u_i,h}\rangle.$$ **Zero $\epsilon_{\mathrm bias}$.** Fix $k,h$ and the realized dataset, choose actor's parameter $\omega$ by setting $$(\omega-\omega_h^k)_{(s,a)} = \eta Q_{z_k,h}^k(s,a) \qquad \text{for every anchor state }s \text{ and action } a.$$ This only fits exactly the actual optimistic critic at every anchor state, hence the actor fitting error is $0$ there with $b(s)=0$. Now we show that the fittine error of action difference is also $0$ at passive states. At a passive state $s$, it is straightforward that $Q_{z_k,h}^k(s,a)=Q_{z_k,h}^k(s,a')$ for any action $a, a'$ since they are action-dependent. Choose any action $a'$ and set $$b(s)=Q_{z_k,h}^k(s,a') -\frac{1}{\eta}\langle p(s),\omega-\omega_h^k\rangle .$$ This choice gives, for every action $a$, $$\eta \bigl( Q_{z_k,h}^k(s,a)-b(s) \bigr) - \langle \varphi(s,a),\omega-\omega_h^k \rangle = 0.$$ Which mean that the fitting error is also $0$ at passive states. Thus the fitting error is $0$ at every state-action pair, giving $\epsilon_{\rm bias}=0$. **Coreset.** Fix a reference action $a_0\in\mathcal{A}$, we can choose the coreset as $$\mathcal{D}_{\mathrm{exp}} = \\{(s,a,a_0):s\text{ is an anchor state},\\ a\ne a_0\\}, \qquad \rho_{\mathrm{exp}}(s,a,a_0)=\frac{1}{m(|\mathcal{A}|-1)}.$$ It is straightforward to show that the coreset spans every action-feature difference $\Delta\varphi$, and $\kappa_G < \infty$. Our Proposition 3.3 gives $\epsilon_{\rm act}=2(\kappa_G+1)\epsilon_{\rm bias}=0$. ### Example 2. Block CMDPs Another important class of MDP that admit $\epsilon_{\mathrm{act}} = 0$ is block MDP, which is heavily studied in the literature [5]. Particularly, partition the state space into $m$ blocks $\mathcal{S}_1,\ldots,\mathcal{S}_m$. Given action, states in the same block share the same reward, utilities, and next-state distribution. Set $d_{\mathrm{c}}=d_{\mathrm{a}}=d=m|\mathcal{A}|$. For $s\in\mathcal{S}_i$, define $$P_h(\cdot\mid s,a)=\mu_h^{(i,a)}(\cdot), \qquad \phi(s,a)=\varphi(s,a)=e_{(i,a)},$$ where $\mu_h^{(i,a)}$ is the common next-state distribution and $e_{(i,a)}$ is the coordinate vector for block $i$ and action $a$. The reward can be written as $r_h(s,a)=r_h(s_i,a), s\in\mathcal{S}_i.$ The same holds for each utility function. **Zero \$\\epsilon_{\mathrm bias} \$.** Choose a representative $s_i\in\mathcal{S}_i$ for each block. For any $s\in\mathcal{S}_i$, it is straightforward to show that $Q_{z_k,h}^k(s,a)=Q_{z_k,h}^k(s_i,a)$. Choose $\omega$ by setting $$(\omega-\omega_h^k)_{(i,a)} = \eta Q_{z_k,h}^k(s_i,a).$$ This fits the actual optimistic critic exactly at every state-action pair with $b(s)=0$, giving $\epsilon_{\mathrm{bias}}=0$. **Coreset.** At each representative $s_i$, use all ordered pairs of distinct actions, with uniform weights: $$\mathcal{D}_{\mathrm{exp}} = \\{(s_i,a,a'):i\in[m],\\ a,a'\in\mathcal{A},\\ a\ne a'\\}, \qquad \rho_{\mathrm{exp}}(s_i,a,a')=\frac{1}{m|\mathcal{A}|(|\mathcal{A}|-1)}.$$
AuthorsOpenReview ↗

Response to Reviewer 2dkN

Part 2 (Continued)

Every action-feature difference at s∈Sis\in\mathcal{S}_i equals the corresponding difference at sis_i. Thus the coreset spans all action-feature differences and κG<∞\kappa_G < \infty. Proposition 3.3 gives ϵact=2(κG+1)ϵbias=0\epsilon_{\mathrm{act}}=2(\kappa_G+1)\epsilon_{\mathrm{bias}}=0.

These examples show that a small log-linear actor can represent the optimistic policy update exactly. In general settings, a more expressive actor, such as a neural network, may improve the actor fitting error. Our analysis applies to actor classes beyond log-linear policies, provided the actor update satisfies the projection-error bound with a controlled ϵact\epsilon_{\mathrm{act}}.

We have added the discussion above to the revised paper (lines 991–1072).

Reference

[3] Sample-efficient reinforcement learning for linearly-parameterized MDPs with a generative mode, Wang et al., 2021.

[4] Sample-optimal parametric Q-learning using linearly additive features, Yang and Wang, 2019.

[5] Provably efficient RL with Rich Observations via Latent State Decoding, Du et al., 2019.

Thank you for your clarification. I maintain my rating.

We thank the reviewer again for their positive assessment of our paper.

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

The paper studies last-iterate guarantees for online primal-dual learning in CMDPs with structured function approximation. The method pairs entropy and quadratic dual regularization with a model-free optimistic critic and a log-linear actor fitted on action differences over a fixed coreset. Theorem 3.4 gives a geometric contraction in which critic error, a local moment term and actor projection error enter as separate certificates. A fixed dual domain, λmax⁡=2Hlog⁡(e∣A∣)/ξ\lambda_{\max} = 2H \log(e|A|)/\xi, makes the regularization bias O(τ)\mathcal{O}(\tau). For linear CMDPs this yields episode complexities scaling as O~(ε−10)\tilde{\mathcal{O}}(\varepsilon^{-10}) on-policy and O~(ε−6)\tilde{\mathcal{O}}(\varepsilon^{-6}) off-policy. It also gives eluder-dimension analogues for general function classes and, in the tabular case, an improvement over the O~(ε−14)\tilde{\mathcal{O}}(\varepsilon^{-14}) implied by Müller et al. (2024). All bounds carry an actor-approximation floor of order H5/3ξ−1/3εact1/3H^{5/3} \xi^{-1/3} \varepsilon_{\text{act}}^{1/3}. On a small synthetic linear CMDP, regularization sharply reduces late-training oscillation relative to τ=0\tau = 0.

Critical strengths
  • Well-motivated objective. Appendix A makes a concrete case for last-iterate guarantees with a parametric actor. Averaging log-linear parameters does not inherit a mixture’s guarantees, and implementing the mixture requires storing past actors.
  • A simple, well-explained conversion. Using Slater's condition to show that the regularized multiplier lies strictly inside the dual box (eqs. 33--36) yields an O(τ)\mathcal{O}(\tau) bias and allows τ=Θ(ε)\tau = \Theta(\varepsilon). Remark C.1 explains exactly why the radius-dependent conversion forces λmax⁡≍ε−1\lambda_{\max} \asymp \varepsilon^{-1} and τ≍ε2\tau \asymp \varepsilon^2. The B.2 table isolates the effect of the change on every budget.
Critical weaknesses
  • The experiments do not test what is claimed to be novel, and they run outside the analyzed regime.

    • \textbf{Scope.} There is one tiny instance (H=4H = 4, ten non-terminal states, ∣A∣=6|A| = 6, dc=da=6d_c = d_a = 6, one constraint) and one baseline (τ=0\tau = 0 at the same step sizes). That regularization stabilizes the last iterate is already established in exact and tabular settings (Ding et al., 2023; Müller et al., 2024). The experiment uses the structured critic and compact actor but measures nothing specific to them: not the actor floor, not on- vs.\ off-policy sample efficiency, not scaling in dimension or ∣A∣|A|.
    • \textbf{Step sizes.} The parameters violate Lemma 4.2's condition ηH(1+Iλmax⁡+τlog⁡∣A∣)⩽1/4\eta H (1 + I\lambda_{\max} + \tau \log|A|) \leqslant 1/4. With H=4H = 4, I=1I = 1, λmax⁡≈22.5\lambda_{\max} \approx 22.5 and τ=0.02\tau = 0.02, the left side is ≈1.9\approx 1.9 on-policy (η=0.02\eta = 0.02) and ≈4.7\approx 4.7 off-policy (η=0.05\eta = 0.05). This is understandable given how small the prescribed η\eta is, but it should be stated. The paper should also say whether the theoretical confidence radii were used.
    • \textbf{Untested assumption.} This instance is the one place where Assumption 3.2 can be checked directly. Since φ=ϕ\varphi = \phi, every linear critic is exactly representable, so εbias\varepsilon_{\text{bias}} comes only from bonuses and truncation. The realized residual in (28) is computable over all (s,a,a′)(s, a, a'), and reporting it would say more about the paper's central assumption than the oscillation plots do.
  • Computational cost. The "computationally efficient" claim assumes the coreset (Dexp,ρexp)(D_{exp}, \rho_{exp}) is given. Appendix B.1 is explicit that its existence result does not come with an efficient construction, and a G-optimal design over S×A×AS\times A\times A for a large state space is itself nontrivial.

Questions for authors

Is there any non-tabular setting in which ϵ\epsilon_bias for the bonus-augmented, truncated critic is provably small, for example by enriching φ\varphi with features that capture the bonus geometry? Can ε_bias be defined over the deterministic critic class rather than the realized iterates?

3 comments
AuthorsOpenReview ↗

Response to Reviewer rPAa

Part 1

We sincerely thank the reviewer for their careful reading of our paper and for their constructive comments and questions. We address each point below.

Example that ϵact\epsilon_{\mathrm act} is small.

Our analysis is general enough to capture settings for any actor representation and any structured MDPs. To see how it is useful in practice, let us give some examples with small actor representations, say, ϕ=φ\phi=\varphi and dc=da=dd_c = d_a = d that achieve ϵact=0\epsilon_{\rm act} = 0.

Example 1. Large linear CMDPs with anchor state-action pairs

These MDPs may have large state spaces and complicated dynamics. However, the policy can influence the dynamics only at a small set of mm states, referred to as anchor states. All other states are passive: their transition laws are independent of the chosen action. The MDPs with anchor state-action have been studied extensively in prior work [3, 4].

Formmaly, suppose there are mm anchor states and ∣A∣|\mathcal A| actions, set dc=da=d=m∣A∣d_{\mathrm c}=d_{\mathrm a}=d=m|\mathcal A|. We use the same features for the actor and critic:

\begin{cases} e_{(s,a)}, & s\text{ is an anchor state},\\\\ p(s), & s\text{ is a passive state}. \end{cases}$$ Here $e_{(s,a)}$ is the coordinate vector for $(s,a)$, and $p(s) \in \Delta([d])$ is independent of the action. Choose arbitrary probability measures $\mu_h^{(1)},\ldots,\mu_h^{(d)}$ and reward and utility coefficient vectors in $[0,1]^d$. Define the transition law, reward, and utilities by $$P_h(\cdot\mid s,a)=\sum_{i=1}^d\phi_i(s,a)\mu_h^{(i)}(\cdot), \qquad r_h(s,a)=\langle\phi(s,a),\upsilon_{r,h}\rangle, \qquad u_{i,h}(s,a)=\langle\phi(s,a),\upsilon_{u_i,h}\rangle.$$ **Zero $\epsilon_{\mathrm bias}$.** Fix $k,h$ and the realized dataset, choose actor's parameter $\omega$ by setting $$(\omega-\omega_h^k)_{(s,a)} = \eta Q_{z_k,h}^k(s,a) \qquad \text{for every anchor state }s \text{ and action } a.$$ This only fits exactly the actual optimistic critic at every anchor state, hence the actor fitting error is $0$ there with $b(s)=0$. Now we show that the fittine error of action difference is also $0$ at passive states. At a passive state $s$, it is straightforward that $Q_{z_k,h}^k(s,a)=Q_{z_k,h}^k(s,a')$ for any action $a, a'$ since they are action-dependent. Choose any action $a'$ and set $$b(s)=Q_{z_k,h}^k(s,a') -\frac{1}{\eta}\langle p(s),\omega-\omega_h^k\rangle .$$ This choice gives, for every action $a$, $$\eta \bigl( Q_{z_k,h}^k(s,a)-b(s) \bigr) - \langle \varphi(s,a),\omega-\omega_h^k \rangle = 0.$$ Which mean that the fitting error is also $0$ at passive states. Thus the fitting error is $0$ at every state-action pair, giving $\epsilon_{\rm bias}=0$. **Coreset.** Fix a reference action $a_0\in\mathcal{A}$, we can choose the coreset as $$\mathcal{D}_{\mathrm{exp}} = \\{(s,a,a_0):s\text{ is an anchor state},\\ a\ne a_0\\}, \qquad \rho_{\mathrm{exp}}(s,a,a_0)=\frac{1}{m(|\mathcal{A}|-1)}.$$ It is straightforward to show that the coreset spans every action-feature difference $\Delta\varphi$, and $\kappa_G < \infty$. Our Proposition 3.3 gives $\epsilon_{\rm act}=2(\kappa_G+1)\epsilon_{\rm bias}=0$. ### Example 2. Block CMDPs Another important class of MDP that admit $\epsilon_{\mathrm{act}} = 0$ is block MDP, which is heavily studied in the literature [5]. Particularly, partition the state space into $m$ blocks $\mathcal{S}_1,\ldots,\mathcal{S}_m$. Given action, states in the same block share the same reward, utilities, and next-state distribution. Set $d_{\mathrm{c}}=d_{\mathrm{a}}=d=m|\mathcal{A}|$. For $s\in\mathcal{S}_i$, define $$P_h(\cdot\mid s,a)=\mu_h^{(i,a)}(\cdot), \qquad \phi(s,a)=\varphi(s,a)=e_{(i,a)},$$ where $\mu_h^{(i,a)}$ is the common next-state distribution and $e_{(i,a)}$ is the coordinate vector for block $i$ and action $a$. The reward can be written as $r_h(s,a)=r_h(s_i,a), s\in\mathcal{S}_i.$ The same holds for each utility function. **Zero \$\\epsilon_{\mathrm bias} \$.** Choose a representative $s_i\in\mathcal{S}_i$ for each block. For any $s\in\mathcal{S}_i$, it is straightforward to show that $Q_{z_k,h}^k(s,a)=Q_{z_k,h}^k(s_i,a)$. Choose $\omega$ by setting $$(\omega-\omega_h^k)_{(i,a)} = \eta Q_{z_k,h}^k(s_i,a).$$ This fits the actual optimistic critic exactly at every state-action pair with $b(s)=0$, giving $\epsilon_{\mathrm{bias}}=0$. **Coreset.** At each representative $s_i$, use all ordered pairs of distinct actions, with uniform weights: $$\mathcal{D}_{\mathrm{exp}} = \\{(s_i,a,a'):i\in[m],\\ a,a'\in\mathcal{A},\\ a\ne a'\\}, \qquad \rho_{\mathrm{exp}}(s_i,a,a')=\frac{1}{m|\mathcal{A}|(|\mathcal{A}|-1)}.$$
AuthorsOpenReview ↗

Response to Reviewer rPAa

Part 2 (Continued)

Every action-feature difference at s∈Sis\in\mathcal{S}_i equals the corresponding difference at sis_i. Thus the coreset spans all action-feature differences and κG<∞\kappa_G < \infty. Proposition 3.3 gives ϵact=2(κG+1)ϵbias=0\epsilon_{\mathrm{act}}=2(\kappa_G+1)\epsilon_{\mathrm{bias}}=0.

These examples show that a small log-linear actor can represent the optimistic policy update exactly. In general settings, a more expressive actor, such as a neural network, may improve the actor fitting error. Our analysis applies to actor classes beyond log-linear policies, provided the actor update satisfies the projection-error bound with a controlled ϵact\epsilon_{\mathrm{act}}.

We have added the discussion above to the revised paper (lines 991–1072).

On the construction of coreset $ \mathcal D_{\mathrm exp} $

We thank the reviewer for raising this point. Our method and analysis are agnostic to how the coreset is constructed, provided it satisfies the coverage conditions in Assumption 3.2. In the worst case, when the state space absolutely has no structure to exploit, a direct GG-optimal design can involve enumerating all triplets in S×A×A\mathcal{S}\times\mathcal{A}\times\mathcal{A}.

However, many structured settings admit simpler constructions of Dexp\mathcal{D}_{\mathrm{exp}} as for the two examples above or often in practice. In particular, when the image Δφ(S×A×A)\Delta\varphi(\mathcal{S}\times \mathcal{A} \times \mathcal{A}) is well distributed in Rda\mathbb{R}^{d_a}, one can find the coreset Dexp\mathcal{D}_{\mathrm{exp}} with probability 1−δ1-\delta and computational complexity O~(da)\widetilde{O}(d_a).

To formalise this, let

\mathbb{E}_{(s,a,a')\sim\operatorname{Unif}(\mathcal{S}\times\mathcal{A}\times\mathcal{A})} \bigl[\Delta\varphi(s,a,a')\Delta\varphi(s,a,a')^\top\bigr], \qquad r=\operatorname{rank}(M).$$ By saying that the image $\Delta\varphi(\mathcal{S}\times\mathcal{A}\times\mathcal{A})$ is well distributed, we mean that, for some constant $C$, $$\max_{s,a,a'}\\|\Delta\varphi(s,a,a')\\|_{M^\dagger}^{2} \le Cr.$$ Intuitively, this condition means that, for any direction $v$ in the span of $\Delta\varphi(\mathcal{S}\times\mathcal{A}\times\mathcal{A})$, no single triplet $(s,a,a')$ accounts for more than $Cr/N$ of the total squared length $\sum_{(s,a,a')}(\Delta\varphi(s,a,a')^\top v)^2$ along $v$. For example, the image of $\Delta\varphi$ can consist of i.i.d. draws from any sub-Gaussian distribution on $\mathbb{R}^{d_a}$. Under this well-distributedness condition, we can construct $\mathcal{D}_{\mathrm{exp}}$ as follows. Draw $n$ triplets independently and uniformly. Keep the distinct sampled triplets in $\mathcal{D}_{\mathrm{exp}}$ and weight each by its frequency divided by $n$. A direct application of the matrix Chernoff bound [1] gives, for $n\ge 8Cr\log(r/\delta)$, $$G_{\mathrm{exp}}\succeq \tfrac{1}{2} M \qquad\text{and}\qquad \kappa_G^2\le 2Cr$$ with probability at least $1-\delta$ . Since $r\le d_{\mathrm{a}}$, for fixed $C$ the construction uses $\widetilde{O}(d_{\mathrm{a}})$ sampled triplets and has a total computational complexity of $\widetilde{O}(d_{\mathrm{a}})$. Finally, fitting a succinct actor to a critic-derived update using collected training data is common in practice, as exemplified by Soft Actor-Critic [2]. In our setting, a practical heuristic is to reuse the data collected during training to form $\mathcal{D}_{\mathrm{exp}}$. We have added the discussion above to the revised paper (lines 958–990). ## On the experiment. We used the parameter choices derived in the theory as guidelines. These choices are designed to guarantee worst-case error bounds and can be conservative. In particular, the prescribed stepsize $\eta$ and regularisation parameter $\tau$ can be small enough to require substantially longer runs. We therefore tuned these parameters manually to test whether the regularised method could damp oscillations and stabilise the last iterates. We observed this behaviour in both the on-policy and off-policy settings. Regarding $\epsilon_{\mathrm act}$ in our experiment, the largest observed actor projection error, was approximately $4\times10^{-4}$ on-policy and $2\times10^{-3}$ off-policy, which is negligibly small. We have added the discussion above to the revised paper (lines 2807--2809, and 2868--2871).
AuthorsOpenReview ↗

Response to Reviewer rPAa

Part 3 (Continued)

Can $ \epsilon_{\mathrm bias} $ be defined over a deterministic critic class rather than the realised iterates?

Yes, our analysis also applies when ϵbias\epsilon_{\mathrm{bias}} is defined uniformly over a deterministic critic class. However, this imposes a stronger condition than our current iterate-based assumption.

The actor projection error over a deterministic critic class can be formalised as follows. For the linear OPE, we can construct such a class Qh\mathcal{Q}_h to contain all possible Q‾k,h=Qzk,hk+τlog⁡πhk\overline{Q}_{k,h}=Q_{z_k,h}^k+\tau\log\pi_h^k, as follows. For each component j∈r,u1,…,uI,ψj\in\\{r,u_1,\ldots,u_I,\psi\\}, let gj,h(s,a)=Truncate⁡[0,Rj,h](⟨ϕ(s,a),wj⟩+αjϕ(s,a)⊤Mϕ(s,a)).g_{j,h}(s,a) = \operatorname{Truncate}_{[0,R_{j,h}]} \left( \langle\phi(s,a),w_j\rangle +\alpha_j\sqrt{\phi(s,a)^\top M\phi(s,a)} \right).

Let Qh\mathcal{Q}_h consist of all sums gr,h+∑i=1Iλigui,h+τgψ,hg_{r,h}+\sum_{i=1}^I\lambda_i g_{u_i,h}+\tau g_{\psi,h} obtained by varying wj∈Rdcw_j\in\mathbb{R}^{d_{\mathrm{c}}}, αj≥0\alpha_j\geq0, 0⪯M⪯Idc0\preceq M\preceq I_{d_{\mathrm{c}}}, and λ∈Λ\lambda\in\Lambda. The class is fixed before collecting data. We can then take the deterministic bias bound to be

\left|Q(s,a)-\langle\varphi(s,a),v\rangle-b(s)\right|.$$ This bound therefore implies Assumption 3.2 and gives the same certificate in Proposition 3.3. Both examples above have zero bias over this deterministic class. Our iterate-based assumption is weaker than imposing the same tolerance over $\mathcal{Q}_h$: it only requires accurate fitting of the critics used by the algorithm. ## Reference [1] User-friendly tail bounds for sums of random matrices, Joel A. Tropp, 2011. [2] Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, Haarnoja, 2018. [3] Sample-efficient reinforcement learning for linearly-parameterized MDPs with a generative mode, Wang et al., 2021. [4] Sample-optimal parametric Q-learning using linearly additive features, Yang and Wang, 2019. [5] Provably efficient RL with Rich Observations via Latent State Decoding, Du et al., 2019.
Reviewer_vkusOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies last-iterate convergence in unknown structured CMDPs, extending the tabular, model-based setting of Müller et al. (2024). The algorithm combines regularized primal-dual updates with optimistic policy evaluation from trajectory data and fits a compact log-linear actor on a coreset. The analysis covers on-policy and off-policy sampling for linear CMDPs and general critic function classes, subject to actor approximation conditions, and improves the dependence on the target accuracy.

Critical strengths
  1. Sharper guarantees. The analysis removes the inverse-radius term from the constraint-violation bound, permitting an accuracy-independent dual radius and less conservative regularization. This improves the dependence on the target accuracy even in the comparable tabular setting.

  2. More general settings. The framework extends online last-iterate analysis beyond tabular CMDPs to linear CMDPs and general critic function approximation under explicit actor and critic conditions. It also accommodates both fresh on-policy batches and cumulative off-policy data.

Critical weaknesses

My main concern is that the claimed generality beyond tabular CMDPs depends on Assumption 3.2. Actor representability is automatic in the tabular setting, whereas the proposed result requires an additional uniform approximation condition that linear-CMDP realizability alone does not imply. Thus, moving to a broader environment class does not by itself establish a more general guarantee; the additional actor restriction must also be considered.

Technically, this restriction substantially simplifies the analysis: the fixed log-linear representation makes the actor covering argument tractable, while the approximation condition supplies the fitting-error control in Proposition 3.3. The significance of the extension therefore depends on whether a modest actor dimension can satisfy Assumption 3.2 with small error for the actual optimistic critics.

As a minor issue, the related-work discussion should cover the following recent papers, distinguishing regret and cumulative violation guarantees from last-iterate guarantees. Lin et al. is already cited in its 2025 workshop form; that reference should be updated to the published AISTATS version.

Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses, ICLR 2026.

Towards Achieving Optimal Strong Regret and Constraint Violation via Computationally Efficient Model-free RL, ICML 2026.

Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes, AISTATS 2026.

Questions for authors
  1. Can the authors provide a concrete family of non-tabular linear CMDPs and actor features for which Assumption 3.2 holds with small approximation error for the actual optimistic critics, including their bonuses and clipping?

  2. Can the experiments include a comparison with an existing regularized CMDP method under the same trajectory budget? Since the simulation setup considers finite states, algorithms for tabular CMDPs can apply.

3 comments
AuthorsOpenReview ↗

Response to Reviewer vkus

Part 1

We sincerely thank the reviewer for the careful reading and constructive comments and questions. We tackle each point below:

Why a succinct actor representation matters.

Our succinct actor provides a practical implementation that follows standard actor-critic practice by maintaining an explicitly parameterised policy. Without a succinct actor representation, one would need either to store the policy in a table covering all state-action pairs or to store all past QQ-functions (Qk)k=1K(Q^k)_{k=1}^K, making it impractical.

To better see its role, suppose we use the direct recursive policy update without projection. With uniform initialization, $ \pi_h^K(a\mid s) \propto \pi_h^{K-1}(a\mid s)\exp\bigl(\eta Q_{z_{K-1},h}^{K-1}(s,a)\bigr) \propto \exp\left(\eta\sum_{k=1}^{K-1}Q_{z_k,h}^k(s,a)\right). $

Now, to implement the policy in the update above without storing a table over all (s,a)(s,a), previous work [1] stores the QQ function from all previous iterates (1...K)(1...K) and computes πhK(a∣s)\pi_h^K(a\mid s) on the fly by querying (Qhk(s,a))k=1K−1(Q_h^k(s,a))_{k=1}^{K-1} for each action.

However, as pointed out by [1], the actor's memory requirement in this implementation scales linearly with KK. Consequently, the resulting algorithm is much less practical than one that uses a succinct representation such as ours.

Using a succinct actor representation avoids both the statistical problem of a log-covering bound that scales linearly with KK and the computational problem of an actor memory requirement that scales linearly with KK. Together, these benefits make our method theoretically tractable and practical.

Example that ϵact\epsilon_{\mathrm act} is small.

Our analysis is general enough to capture settings for any actor representation and any structured MDPs. To see how it is useful in practice, let us give some examples with small actor representations, say, ϕ=φ\phi=\varphi and dc=da=dd_c = d_a = d that achieve ϵact=0\epsilon_{\rm act} = 0.

Example 1. Large linear CMDPs with anchor state-action pairs

These MDPs may have large state spaces and complicated dynamics. However, the policy can influence the dynamics only at a small set of mm states, referred to as anchor states. All other states are passive: their transition laws are independent of the chosen action. The MDPs with anchor state-action have been studied extensively in prior work [3, 4].

Formmaly, suppose there are mm anchor states and ∣A∣|\mathcal A| actions, set dc=da=d=m∣A∣d_{\mathrm c}=d_{\mathrm a}=d=m|\mathcal A|. We use the same features for the actor and critic:

\begin{cases} e_{(s,a)}, & s\text{ is an anchor state},\\\\ p(s), & s\text{ is a passive state}. \end{cases}$$ Here $e_{(s,a)}$ is the coordinate vector for $(s,a)$, and $p(s) \in \Delta([d])$ is independent of the action. Choose arbitrary probability measures $\mu_h^{(1)},\ldots,\mu_h^{(d)}$ and reward and utility coefficient vectors in $[0,1]^d$. Define the transition law, reward, and utilities by $$P_h(\cdot\mid s,a)=\sum_{i=1}^d\phi_i(s,a)\mu_h^{(i)}(\cdot), \qquad r_h(s,a)=\langle\phi(s,a),\upsilon_{r,h}\rangle, \qquad u_{i,h}(s,a)=\langle\phi(s,a),\upsilon_{u_i,h}\rangle.$$ **Zero $\epsilon_{\mathrm bias}$.** Fix $k,h$ and the realized dataset, choose actor's parameter $\omega$ by setting $$(\omega-\omega_h^k)_{(s,a)} = \eta Q_{z_k,h}^k(s,a) \qquad \text{for every anchor state }s \text{ and action } a.$$ This only fits exactly the actual optimistic critic at every anchor state, hence the actor fitting error is $0$ there with $b(s)=0$. Now we show that the fittine error of action difference is also $0$ at passive states. At a passive state $s$, it is straightforward that $Q_{z_k,h}^k(s,a)=Q_{z_k,h}^k(s,a')$ for any action $a, a'$ since they are action-dependent. Choose any action $a'$ and set $$b(s)=Q_{z_k,h}^k(s,a') -\frac{1}{\eta}\langle p(s),\omega-\omega_h^k\rangle .$$ This choice gives, for every action $a$, $$\eta \bigl( Q_{z_k,h}^k(s,a)-b(s) \bigr) - \langle \varphi(s,a),\omega-\omega_h^k \rangle = 0.$$ Which mean that the fitting error is also $0$ at passive states. Thus the fitting error is $0$ at every state-action pair, giving $\epsilon_{\rm bias}=0$. **Coreset.** Fix a reference action $a_0\in\mathcal{A}$, we can choose the coreset as $$\mathcal{D}_{\mathrm{exp}} = \\{(s,a,a_0):s\text{ is an anchor state},\\ a\ne a_0\\}, \qquad \rho_{\mathrm{exp}}(s,a,a_0)=\frac{1}{m(|\mathcal{A}|-1)}.$$ It is straightforward to show that the coreset spans every action-feature difference $\Delta\varphi$, and $\kappa_G < \infty$. Our Proposition 3.3 gives $\epsilon_{\rm act}=2(\kappa_G+1)\epsilon_{\rm bias}=0$.
AuthorsOpenReview ↗

Response to Reviewer vkus

Part 2

Example 2. Block CMDPs

Another important class of MDP that admit ϵact=0\epsilon_{\mathrm{act}} = 0 is block MDP, which is heavily studied in the literature [5]. Particularly, partition the state space into mm blocks S1,…,Sm\mathcal{S}_1,\ldots,\mathcal{S}_m. Given action, states in the same block share the same reward, utilities, and next-state distribution.

Set dc=da=d=m∣A∣d_{\mathrm{c}}=d_{\mathrm{a}}=d=m|\mathcal{A}|. For s∈Sis\in\mathcal{S}_i, define

\qquad \phi(s,a)=\varphi(s,a)=e_{(i,a)},$$ where $\mu_h^{(i,a)}$ is the common next-state distribution and $e_{(i,a)}$ is the coordinate vector for block $i$ and action $a$. The reward can be written as $r_h(s,a)=r_h(s_i,a), s\in\mathcal{S}_i.$ The same holds for each utility function. **Zero \$\\epsilon_{\mathrm bias} \$.** Choose a representative $s_i\in\mathcal{S}_i$ for each block. For any $s\in\mathcal{S}_i$, it is straightforward to show that $Q_{z_k,h}^k(s,a)=Q_{z_k,h}^k(s_i,a)$. Choose $\omega$ by setting $$(\omega-\omega_h^k)_{(i,a)} = \eta Q_{z_k,h}^k(s_i,a).$$ This fits the actual optimistic critic exactly at every state-action pair with $b(s)=0$, giving $\epsilon_{\mathrm{bias}}=0$. **Coreset.** At each representative $s_i$, use all ordered pairs of distinct actions, with uniform weights: $$\mathcal{D}_{\mathrm{exp}} = \\{(s_i,a,a'):i\in[m],\\ a,a'\in\mathcal{A},\\ a\ne a'\\}, \qquad \rho_{\mathrm{exp}}(s_i,a,a')=\frac{1}{m|\mathcal{A}|(|\mathcal{A}|-1)}.$$ Every action-feature difference at $s\in\mathcal{S}_i$ equals the corresponding difference at $s_i$. Thus the coreset spans all action-feature differences and $\kappa_G < \infty$. Proposition 3.3 gives $\epsilon_{\mathrm{act}}=2(\kappa_G+1)\epsilon_{\mathrm{bias}}=0$. These examples show that a small log-linear actor can represent the optimistic policy update exactly. In general settings, a more expressive actor, such as a neural network, may improve the actor fitting error. Our analysis applies to actor classes beyond log-linear policies, provided the actor update satisfies the projection-error bound with a controlled $\epsilon_{\mathrm{act}}$. We have added the discussion above to the revised paper (lines 991–1072). ## On experiment comparing with tabular method We thank the reviewer for suggesting this ablation test. We ran the regularised method with tabular one-shot features of dimension $d_c=d_a=|S|\times|A|=60$, compared with the original feature dimension of $d_c=d_a=6$. For tabular feature-based methods, we need to scale the optimism bonus appropriately with dimension $d$, which is $60$ for the tabular-feature experiment. For on-policy, we also need to tune the batch $N = 3.2\times 10^6$ for the tabular-feature method, to guarantee the same theoretical estimated error for policy evaluation compared to the linear-feature method. The detailed experimental results can be found in the revised paper (lines 2872--2907). Briefly, in the on-policy setting, Figure 4 shows that the method with tabular features requires about $100$ times as much data per update to achieve performance comparable to that of the method with linear features. In the off-policy setting, Figure 4 shows that the method with linear features exhibits strong convergence after $15000$ updates, while the method with tabular features converges much more slowly. Both the on-policy and off-policy experiments confirm our theory that the method with linear features requires much less data to achieve the desired error. ## Reference [1] Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL, Liu et al., 2023. [2] Optimistic Actor-Critic with Parametric Policies: Unifying Sample Efficiency and Practicality, Lin et al., 2025. [3] Sample-efficient reinforcement learning for linearly-parameterized MDPs with a generative mode, Wang et al., 2021. [4] Sample-optimal parametric Q-learning using linearly additive features, Yang and Wang, 2019. [5] Provably efficient RL with Rich Observations via Latent State Decoding, Du et al., 2019.

I thank the author for their detailed response, and I think the paper’s theoretical result is interesting. However, in my view, it still reminds me that the results follow from a natural combination of existing techniques from Lin et al., Zuo et al., and Muller et al. For a theory paper, this leaves me with some reservations about the technical novelty. Therefore, I would like to maintain my current evaluation of the paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of our responses to the reviewers

As the discussion period is coming to an end, we would like to encourage the reviewers to engage with us on any remaining questions or concerns about our paper.

During the rebuttal, we addressed several points raised by the reviewers:

  • We explain how ordinary mirror descent, which is used in many prior works, can incur high memory and computational costs that make it impractical, and how our actor projection step avoids the high memory cost and follows standard implementation practice.

  • We give two important examples in which the actor and critic share a compact feature representation, with da=dc=dd_{\mathrm{a}}=d_{\mathrm{c}}=d , and the actor projection error is zero (ϵact=0\epsilon_{\mathrm{act}}=0). We also explain how our analysis can apply to more flexible actors, such as neural networks, when their projection error is small.

  • We explain how to construct the coreset Dexp\mathcal{D}_{\mathrm{exp}} efficiently for a broad range of structured CMDPs and discuss how training data can be reused to build Dexp\mathcal{D}_{\mathrm{exp}} in practice.

  • We extended our experiments in response to the reviewers’ suggestions. The results showed that the actor projection error was negligible and that our method converged faster with linear features than with tabular features.

Thank you again for taking the time to review our work. Please let us know if any concerns remain so we can address them before the discussion closes. If our responses and revisions have addressed your concerns, we would be grateful if you could reconsider your evaluation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.