- 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 off-policy and on-policy up to an actor-approximation floor.
Critical strengths
- The fixed dual radius, and the resulting conversion, is a clean and consequential technical contribution.
Critical weaknesses
- 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 and infinite — in which Assumption 3.2 provably holds with and ? Given your own remark at lines 883–885, what prevents the clipped, bonus-augmented critic from forcing for a -dimensional log-linear actor?
4 comments
Response to Reviewer 2dkN
Part 2 (Continued)
Every action-feature difference at equals the corresponding difference at . Thus the coreset spans all action-feature differences and . Proposition 3.3 gives .
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 .
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.
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 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, ϕ=φ and dc=da=d that achieve ϵ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 m 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 m anchor states and ∣A∣ actions, set dc=da=d=m∣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)}.$$