- 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
- 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
- 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
- Section 2: a few clarification questions:
- When define CMDP, can authors clarify what are the constraints in Line 132-134?
- Line 156: I believe is never defined earlier, what does it refer to exactly? It would be necessary to specify what values are being observed
- 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.
- 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?
- Section 4: I was wondering for a fixed , how does the proposed approach compared with directly apply a scaler OPE estimator to the combined ? Since the scalar construction appears to account for reward–cost covariance automatically, could the authors clarify the additional advantages of the joint approach?
- 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?
- 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?
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:
(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.