acceptodds
Under review as a conference paper at ICLR 2027

Semiparametrically Efficient Off-Policy Evaluation and Learning in Constrained Markov Decision Processes

Abstract

We study off-policy evaluation (OPE) in constrained Markov decision processes (CMDPs): estimating the reward value and the constraint cost values of a new policy from data collected by another. Before a policy is deployed as safe, its feasibility must be certified from confidence intervals, not point estimates. Such a certificate concerns a combination of the estimates—typically the Lagrangian —so its validity depends on how the reward and cost errors covary. Existing methods fall short in two ways. Concatenating the step-wise doubly robust estimator across objectives inherits its exponential variance in the horizon. Applying a marginally efficient estimator to each objective separately breaks the curse of horizon, but treating the objectives as independent for inference discards the covariance induced by the marginal density ratio they share. We instead treat the reward and cost values as a single vector target, derive its efficient influence function, and propose the Constrained Doubly Robust (CDR) estimator. CDR is unbiased whenever either the density ratio or the -functions are correctly specified, attains the joint semiparametric efficiency bound under a product-rate condition, and reports the full reward–cost covariance from one cross-fitted pass. The sign of that covariance governs the failure this repairs: when positive, independent treatment is merely conservative; when negative, it is anti-conservative—the Lagrangian intervals under-cover and an unsafe policy can be certified. Experiments on tabular and continuous-state CMDPs, and on a constrained Taxi benchmark at horizon , confirm the theory, including the negative-covariance regime and a diagnostic in which violating the product-rate condition collapses coverage.

Primary area:
reinforcement learning
Keywords:
off-policy evaluation, constrained Markov decision processes, doubly robust estimation, semiparametric efficiency, safe reinforcement learning, offline reinforcement learning

Reviews

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

This paper studies off-policy evaluation in CMDP settings. The authors proposed to jointly estimate the reward and constraint costs of the target policy from the observed trajectories with doubly robust estimators. The joint semi-parametric efficiency is established for the proposed CDR estimator, and the proposed method is evaluated on both tabular and continuous synthetic environments.

Critical strengths
  1. I think this paper provides a unified framework for joint off-policy evaluation under CMDP. The theoretical development of covariance estimation and semi-parametric efficiency are very solid and would provide valuable insights for the research community.
Critical weaknesses
  1. My biggest concern is relatively limited novelty of the proposed framework. The approach appears to primarily combine existing efficient estimators and account for their joint covariance. It remains unclear what additional theoretical and empirical benefits this provides beyond applying existing scalar methods to the reward and each constraint cost separately.
Questions for authors
  1. Section 2: a few clarification questions:
  • When define CMDP, can authors clarify what are the constraints in Line 132-134?
  • Line 156: I believe ZiZ_i is never defined earlier, what does it refer to exactly? It would be necessary to specify what values are being observed
  1. Proposition 1: Can authors provide more explanation and intuition on this proposition? Specifically, it’s a bit hard to follow for the discussion at the end of the proposition.
  2. Theorem 3: The construction essentially stack the scalar EIFs and estimate their joint covariance using the same trajectories. Could the authors clarify what technical challenges are specific to the CMDP setting? Would the same approach apply to jointly evaluating multiple signals in a standard MDP, and would it offer the same benefits?
  3. Section 4: I was wondering for a fixed λ\lambda, how does the proposed approach compared with directly apply a scaler OPE estimator to the combined r−λcr-\lambda c? Since the scalar construction appears to account for reward–cost covariance automatically, could the authors clarify the additional advantages of the joint approach?
  4. Section 6: For the proposed extension to policy learning on CMDP, can authors clarify how the proposed approach would ensure the constraints are being satisfied for the learned optimal policy?
  5. Table 1: I was wondering why the proposed method only achieve around 90% coverage for Taxi environments, which should be a relatively simple environments. Are there any specific reason for such under coverage?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 3o2L

We sincerely thank the reviewer for the detailed and constructive questions, and for finding the theoretical development solid and valuable to the community. Your Q4 in particular directly motivated the new experiment reported in our General Response. We answer the weakness and the six questions in order.

Weakness — benefits beyond applying scalar methods to each signal separately. Applying a scalar method to the reward and to each cost gives correct marginal intervals, but no valid statement about them jointly. Any decision that uses several of them at once (all costs within budget and the return improved; a trade-off curve over λ) then needs either the covariance or a conservative correction. Theoretically, we show that this covariance is generically non-zero (Prop. 4) and that its sign decides whether treating the signals as independent is anti-conservative or wasteful (Thm 5). Empirically, the independence report covers 0.84–0.87 instead of 0.95 when reward and cost are negatively correlated (Table 1), and in the new Experiment 13 the valid alternatives without the covariance are 30–46% wider (Bonferroni) or about 200× more expensive (bootstrap).

Q1 — Section 2. (a) Constraints (l. 132–134): the constraints are c_j(π) ≤ b_j for j = 1, …, J. The thresholds b_j currently appear only in Section 6 and Appendix B; we will define them with the CMDP in Section 2.1. (b) Z_i (l. 156): Z_i is the i-th observed trajectory, generated by the behavior policy π₀: Z_i = (s₁, a₁, r₁, c₁, …, s_H, a_H, r_H, c_H, s_{H+1}), where c_h is the vector of the J costs at step h. We will define it explicitly where the data are introduced.

Q2 — intuition for Prop. 1. Step-wise DR multiplies all earlier importance ratios into each correction term, so each step where π and π₀ differ multiplies the variance by at least 1 + χ². Over H steps this compounds: on Taxi, χ² = 0.148 per step gives 1.148¹⁰⁰ ≈ 10⁶. Our estimator reweights each step only by the marginal ratio of reaching (s_h, a_h), so its variance adds over steps instead (here the largest marginal ratio is 9.5). This needs the marginal ratio to stay bounded as H grows; on tree-structured problems the two estimators coincide (Remark 5). We will rewrite the closing paragraph accordingly.

Q3 — what is specific to CMDPs? The construction applies verbatim to multiple signals in a standard MDP, with the same benefits whenever several combinations are used at once; we will say so. The parts that are not a stacking argument are the closed form of the off-diagonal bound (eq. 8–9), Prop. 4, Thm 5 and Thm 8. CMDPs are where these matter most, because feasibility is one-sided and must hold for all constraints jointly.

Q4 — fixed λ vs. scalar OPE on r − λc. You are right: for a fixed, pre-specified λ, the two give the same estimate and variance, by linearity of the score; we will state this as a remark. The joint approach adds value when several combinations are needed at once, e.g. when λ is chosen after seeing the data. Experiment 13 (General Response) tests a band over a grid of λ: per-λ scalar intervals cover only 0.80–0.92, while the joint band is calibrated and the narrowest valid band.

Q5 — constraints for the learned policy. Theorem 8 (Appendix B): maximize the estimated return subject to estimated cost ≤ b_j − ε_{n,j}, with margins ε_{n,j} of order 1/√n (eq. 13). With probability at least 1 − δ − o(1), the learned policy satisfies every true constraint, with O(1/√n) return regret. In Experiment 9 (20 policies, 300 runs), the violation rate is 0.3% at n = 100 and 0 for n ≥ 200, versus 22.7% and 11.7% without margins. This is verified for a finite policy class only, as stated in the Conclusion.

Q6 — ~90% coverage on Taxi. It is a finite-sample effect of learning the nuisances, and it disappears as n grows. With exact nuisances, the Lagrangian interval covers 0.93–0.96 at every n. The deployable estimator must learn FQE and a density ratio over 500 states × 6 actions at H = 100; at small n this leaves a bias in the cost estimate (0.033 at n = 500, 0.005 at n = 4000) and extra variance. We extended the experiment to larger n, 900 replications each:

n = 8000n = 16000
Bias of the cost estimate0.00130.0002
Lagrangian coverage, deployable estimator0.9260.940
Lagrangian coverage, exact nuisances0.9410.939

(Monte Carlo SE ≤ 0.009.) At n = 16000 the deployable interval matches the exact-nuisance one. The joint χ² region closes more slowly (0.919 / 0.924, vs 0.942 / 0.949 with exact nuisances), because the learned density ratio still inflates the variance of the cost component and the plug-in covariance captures most but not all of it. We will add these runs to Section 7.3.

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

The paper studies the problem of off-policy evaluation in constrained Markov decision processes where there is reward and multiple costs. The goal is to estimate the combination of reward and cost, typically the Lagrangian between reward and cost. They aim to estimate the confidence interval and for this need, they propose to estimate the covariance between the reward and costs since they are estimated with same trajectories. And for each individual estimator, they use the doubly robust off-policy estimator. Based on these results, they derive the asymptotic confidence interval results for the Lagrangian target. Through experiments, they show the effectiveness of their proposed algorithm.

Critical strengths
  1. The motivation of estimating the covariance between reward and costs are well justified. And the main theorems and mathematical results seem correct to me.
Critical weaknesses
  1. The target to estimate is the quantity r−λcr-\lambda c, however, this is just a combination of reward and costs, how can it be decided that whether a constraint is satisfied through a confidence interval of this estimator. From this view, there is no difference between reward and costs, it is just estimating a combination of some quantities that are evaluated using the same trajectories, for example, the combination of two rewards. The paper formulates everything in the constrained MDPs which I feel is not necessary and over-claimed since no constraint-related guarantees are actually made. Besides, the contribution is a little bit incremental. The estimators are existing and covariance estimation results with same data are also established. The new thing is applying these stuff to CMDP, but only estimating the Lagrangian, instead of any constrain conditions.
Questions for authors

No.

1 comment
AuthorsOpenReview ↗

Response to Reviewer nMTE

We sincerely thank the reviewer for the careful reading and the valuable comments, and for finding the motivation well justified and the main theorems correct. Your question on how a confidence interval can decide constraint satisfaction points to a real weakness in how Section 4 is framed, and addressing it has made our claims more precise. Your weakness raises three points, which we answer in order.

1. "How can it be decided whether a constraint is satisfied through a confidence interval of this estimator?" You are right that a confidence interval for the Lagrangian alone cannot decide feasibility, and the paper should not suggest that it does. We will reframe Section 4: the Lagrangian is used there only because it is the simplest combination on which the effect of the reward–cost covariance (Theorem 5) can be shown in closed form. Feasibility is decided from the joint confidence region for the full vector (v(π), c₁(π), …, c_J(π)) given by Corollary 7, not from the Lagrangian:

  • Declare π feasible if, for every j, the upper confidence bound of the cost c_j(π) is below its threshold b_j (and, if desired, the lower bound of the return exceeds a reference value). Because all bounds come from one joint region, this rule wrongly certifies an infeasible policy with probability at most α asymptotically. Making the bounds simultaneous without being overly wide requires the reward–cost covariance, which is what our analysis estimates. We will state this as a corollary and define the thresholds b_j already in Section 2.1.

2. "No constraint-related guarantees are actually made." We apologize that this was not visible enough: the guarantee is summarized in Section 6 and stated as Theorem 8 in Appendix B. A learner that maximizes the estimated return subject to "estimated cost ≤ b_j − margin", with margins of order 1/√n, returns a policy that satisfies every true constraint c_j(π) ≤ b_j with probability at least 1 − δ − o(1), with O(1/√n) return regret. In Experiment 9 the violation rate is 0.3% at n = 100 and 0 for n ≥ 200, versus 22.7% and 11.7% for the same learner without margins. We will move the statement of this theorem into the main text.

On "no difference between reward and costs": mathematically we agree. The estimator applies to any vector of signals evaluated on the same trajectories, for example two rewards, and we will say so. What is specific to the constrained setting is how the estimate is used: one-sided thresholds, all J constraints holding at the same time, and safety margins. There, the sign of the reward–cost covariance has a direct safety meaning: when it is negative, intervals combined as if independent are too narrow and can certify an unsafe policy (coverage 0.84–0.87 instead of 0.95, Table 1).

3. "The contribution is a little bit incremental." We accept that the estimators are existing and that covariance estimation from shared data is classical, and we will state this explicitly and narrow our claims. What we add for the constrained setting: the closed form of the joint efficiency bound (eq. 8); the characterization of when an independence report is anti-conservative (Theorem 5) and that the covariance is generically non-zero (Proposition 4); the feasibility and learning guarantees above; and a new experiment (Experiment 13, in our General Response) showing that without the joint covariance, the only valid simultaneous report is 30–46% wider, or about 200× more expensive via a bootstrap.

We would be grateful if you would reconsider your assessment in light of these clarifications.

Reviewer_5LjvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies joint OPE (reward + constraints) for finite-horizon CMDPs. It proposes the constrained doubly robust (CDR) estimator with respect to the reward-cost vector target, deriving their joint EIF and using the resulting covariance to calibrate the Langevin inference. Simulations confirm the theory that a negative reward-cost covariance results in substantial under-coverage and thus undermines the safety of the policy.

Critical strengths
  1. The technical parts of the paper, i.e. the joint EIF analysis and the covariance formula, are clear by themselves, with clear assumptions and mostly sound proofs.
  2. Simulations are performed extensively to test the established theory, including learned nuisances, multiple constraints, and longer horizons. Specifically, those with negative covariances work well to support the main claims of the theory.
Critical weaknesses
  1. The writing of the paper needs significant improvement. The paper now looks like a mere collection of new results, which are simply listed with insufficient discussion or interpretation. I understand the paper is subject to page limits, but the current presentation is not satisfactory.
    • Appendix F does provide some remarks for the main text, but most of them are technical supplements rather than high-level explanations. I also find some of them pretty hard to follow (e.g., Remark 5 and Remark 11).
  2. The CDR estimator itself is hardly novel, in the sense that it merely stacks single-objective scores. The theoretical analysis focuses on quantifying the uncertainty reporting, but the estimate itself remains unchanged (correct me if I'm wrong on this).
Questions for authors

How would the theory established in this work benefit practical applications?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 5Ljv

We sincerely thank the reviewer for the time spent on our paper and for the valuable comments, and for recognizing the clarity of the joint EIF analysis and the breadth of the simulations. Your question about practical benefit helped us sharpen the motivation of the paper. We answer your two weaknesses and your question in order. Please also see our General Response, which reports a new experiment (Experiment 13).

Weakness 1 — "a mere collection of new results … Remark 5 and Remark 11 are hard to follow". We agree that the main text currently lists results with too little interpretation. We would note, however, that the results are not independent of each other but form one chain, and the revision will state this chain explicitly at the start of Section 3: Theorem 3 gives the joint efficiency bound, i.e. the smallest achievable joint uncertainty, including the reward–cost covariance; Proposition 4 shows that this covariance is generically non-zero, so it cannot simply be ignored; Theorem 5 shows that its sign decides whether ignoring it makes a safety report too optimistic or too conservative; Theorem 6 and Corollary 7 show that CDR attains the bound and estimates the covariance consistently, so the correct report can actually be computed; and Theorem 8 uses this report to learn a policy that satisfies the constraints. In the revision, each main result will be followed by one or two sentences on what it means for a practitioner, and Proposition 1's technical discussion will move to the appendix to make room. We will also rewrite the two remarks in plain terms:

  • Remark 5: when no two histories reach the same state (tree-structured problems), our estimator coincides with step-wise DR and has the same variance; the advantage appears exactly when different histories merge into the same state.
  • Remark 11: λ† = Σ⋆₀₁ / Σ⋆₁₁ is the multiplier that makes the Lagrangian estimate least noisy, while λ⋆ is the multiplier that solves the constrained problem; they generally differ, so the closed-form gain of Theorem 5(d) holds at λ†, and the gap at λ⋆ is problem-dependent.

Weakness 2 — "the estimate itself remains unchanged (correct me if I'm wrong)". You are right. The CDR point estimate is the stack of the single-objective efficient estimates computed with a shared density ratio. Our contribution is about the uncertainty attached to that estimate and the decisions built on it. We will say this plainly in Section 3 and reword Contribution 1 accordingly.

Question — how does the theory benefit practical applications? Before a policy learned from logged data is deployed, the go/no-go decision is never about a single number. A typical rule is "every cost is within its budget and the return improves on the current policy", or "the policy is acceptable for every trade-off weight λ that stakeholders may choose later". Such rules use several combinations of (reward, cost₁, …, cost_J) at once, and whether they hold jointly depends on the reward–cost covariance, which our theory characterizes and estimates. Concretely:

  • Safety. When reward and cost are negatively correlated, intervals combined as if independent under-cover: 0.84–0.87 instead of 0.95 (Table 1), and 0.89–0.91 for a band over λ (Experiment 13). An unsafe policy can then be certified as safe; the joint report removes this failure.
  • Efficiency. The alternatives that stay valid without the covariance are 30–46% wider (Bonferroni over λ) or about 200× more expensive (a bootstrap that refits the nuisances).
  • Constrained learning. With the safety margins of Theorem 8, the constraint-violation rate in Experiment 9 is 0.3% at n = 100 and 0 for n ≥ 200, versus 22.7% and 11.7% for the same learner without margins.

We hope these clarifications and the new experiment address your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

We sincerely thank all three reviewers for their time and for the valuable comments, which have helped us state our contribution more precisely and led to new experiments. Two concerns are shared: (i) novelty, and (ii) what the joint analysis adds over a scalar method in practice.

(i) Novelty — the reviewers are right that the point estimator is not new. The CDR point estimate equals the per-objective marginal-ratio DR estimates with a shared density ratio, and its EIF is the stack of the scalar EIFs. We will state this in Section 3 and reword Contribution 1. Our contribution is joint inference for decisions involving several objectives: the closed-form joint efficiency bound (eq. 8), the sign result that decides when an independence report is anti-conservative (Thm 5), joint asymptotic normality with a consistent plug-in covariance (Thm 6, Cor 7), and constrained learning with safety margins (Thm 8).

(ii) A fixed λ\lambda does not need the joint law; everything else does. For a fixed, pre-specified λ\lambda, scalar efficient OPE on r−λcr - \lambda c gives the same estimate and variance as CDR, by linearity of the score. We concede this and will add it as a remark. The covariance is needed whenever several combinations are used at once: certifying all JJ constraints and a return guarantee simultaneously; reporting the trade-off curve λ↦Lλ\lambda \mapsto L_\lambda so that λ\lambda can be chosen after seeing the data; constrained policy selection.

New Experiment 13: a simultaneous 95% band for LλL_\lambda over a grid of λ\lambda (31 values in [0,3][0,3] for J=1J=1; a 7×77\times 7 grid for J=2J=2). Deployable estimator (learned FQE and density ratio, 5-fold cross-fitting), 500 replications. Each cell is the simultaneous coverage at n = 500 / 2000, with the band width relative to the joint band in brackets.

BandJ=1J=1, Σ01∗<0\Sigma^*_{01}<0J=1J=1, Σ01∗>0\Sigma^*_{01}>0J=2J=2
Composite, per-λ\lambda (no correction)0.898 / 0.916 [×0.91]0.848 / 0.870 [×0.81]0.798 / 0.842 [×0.78]
Composite + Bonferroni over λ\lambda0.992 / 0.998 [×1.46]0.994 / 0.988 [×1.30]0.990 / 0.990 [×1.31]
Joint (CDR)0.940 / 0.946 [×1]0.940 / 0.952 [×1]0.920 / 0.950 [×1]
Independence (diagonal Σ^\hat\Sigma)0.886 / 0.906 [×0.88]0.964 / 0.986 [×1.33]0.914 / 0.942 [×1.08]
Bootstrap, 200 nuisance refits0.974 / 0.940 [×1.15 → 1.02]0.982 / 0.966 [×1.26 → 1.07]0.982 / 0.964 [×1.25 → 1.08]

Binomial SE ≤ 0.018. Per-λ\lambda intervals do not cover the curve (0.80–0.92). Bonferroni is valid but 30–46% wider. The joint band is calibrated (lowest value 0.920, for J=2J=2 at n = 500) and is the narrowest valid band. The independence report reproduces Thm 5: anti-conservative when Σ01∗<0\Sigma^*_{01}<0, too wide when Σ01∗>0\Sigma^*_{01}>0. The nuisance-refitting bootstrap is valid but 15–26% wider at n = 500 (2–8% at n = 2000) and about 200× more expensive (5.0 s vs 0.025 s per replication).

Revisions we will make:

  • Sec. 3: the logical chain connecting the main results stated at the start; Contribution 1 reworded (the point estimator is not new; the joint inference is).
  • Sec. 4: reframed as an illustration of the covariance effect, not a feasibility test; fixed-λ\lambda remark and a paragraph "when the joint law is needed".
  • Sec. 2.1 and 5: constraint thresholds bjb_j defined up front; a simultaneous feasibility corollary.
  • Sec. 6: the constraint-satisfaction guarantee (Thm 8) moved from the appendix into the main text.
  • Sec. 7: Experiment 13 added; the Taxi experiment extended to n = 8000 and 16000 (see our reply to Reviewer 3o2L, Q6).
  • Throughout: a plain-language interpretation after each main result; Remarks 5 and 11 rewritten; Prop. 1's technical discussion moved to the appendix.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.