acceptodds
Under review as a conference paper at ICLR 2027

Safe to Switch: Target-Covered Off-Policy Evaluation via Policy Replacement

Abstract

Offline reinforcement learning enables policy learning from existing data when further interaction is costly or unsafe. However, target occupancy coverage and linear realizability of the target's action values alone do not guarantee sample-efficient off-policy evaluation. We show that target coverage suffices under replacement-policy linear realizability, using safe partial corrections to logged returns. Replacement policies retain a drawn logger action or replace it with a fresh target draw, with arbitrary probabilities across stages, states and drawn actions. At every stage, every replacement policy's action values must be linear on all state–action pairs in known features, with uniform feature and parameter norm bounds. For a fixed target, our estimator achieves error at most with probability at least using iid complete trajectories from one unknown fixed Markov logger, without logger probabilities or model oracles. Here bounds target-to-logger occupancy ratios, is the horizon and the feature dimension. The sample bound has logarithmic norm dependence and no state or action cardinality factor. Separate families establish strict representation and coverage relaxations: replacement-policy values admit a two-dimensional feature map while all-policy dimension is unbounded, and finite target coverage coexists with infinite mixture coverage. The finite-sample guarantee and both separations are formalized in Lean 4.

Primary area:
reinforcement learning
Keywords:
off-policy evaluation, offline reinforcement learning, linear function approximation, target coverage, policy replacement, 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_6ZwHOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how to estimate the expected cumulative return of a fixed target strategy by using the complete trajectory collected by the unknown behavior strategy. The author proposes a reverse recursive regression algorithm, which adds the correction based on the advantage estimation to the actual observed follow-up return, and shrinks the correction to zero according to the confidence interval. When the confidence interval is valid, the conditional mean of the modified label still corresponds to the value of a replacement strategy. Based on this property, the paper gives a finite sample error guarantee without knowing the action probability of the behavior strategy under the condition that the value of the replacement strategy family meets the linear realizability and the data coverage target strategy. The author also proves by constructing an example that the realizability of the replacement strategy and the target coverage can still be satisfied when the corresponding full strategy conditions are not tenable, and reports the main statistical guarantee and the lean formal verification of the separation results.

Critical strengths

One of the key ideas of this paper is to link the return correction with the strategy replacement. After conservatively shrinking the estimated advantage, as long as the confidence interval is valid, the conditional mean of the corrected return still corresponds to the value of a replacement strategy. In this way, the regression needs to represent the value of the intermediate strategy, but the data only needs to cover the target strategy, not all the places that the intermediate strategy will access. Using this difference, the author gives a clear estimation algorithm and sample guarantee without knowing the probability of behavior strategy. The separation examples in this paper also show that the relaxation of these conditions does make the theorem applicable to the situation that the previous relevant guarantees cannot cover.

Critical weaknesses

The experimental part of this paper is relatively simple, which can supplement more experiments and conduct more comprehensive empirical analysis.

Questions for authors

no question

2 comments

Dear Reviewer 6ZwH,

Thank you for the careful summary of the replacement mechanism and for asking for a more comprehensive empirical analysis. The submission contained only small numerical diagnostics. The revision adds a numerical study, Appendix I, organized around one question: where does each class of estimator fail, and does the proposed correction avoid those failures?

The experimental part of this paper is relatively simple, which can supplement more experiments and conduct more comprehensive empirical analysis.

The main study uses 20 independently drawn models (Appendix I.2). Each has four decisions, three supplied features and 65,536 states per middle layer, and is evaluated under four unknown loggers in a two-by-two design. One target action, in a region the target never visits, is either logged or never logged ("missing support"). The logger's action probabilities are either constant or a non-monotone "band" function of a public feature. Target coverage is finite in all four cases.

The construction says where particular baselines should lose accuracy. Missing support makes regression extrapolate, which should break fitted Q evaluation (FQE) with a minimum-norm or ridge fit and corrections applied without shrinkage. The band logger should break weighted importance sampling (WIS) with a logistic logger model, and with per-state counts when support is also missing. After a pilot on two development models, and before drawing any test model, we fixed the protocol and 44 predictions of which methods would be accurate (RMSE at most .02.02) or fail (at least .05.05). 43 held. The exception is count-logger WIS in the last regime, whose RMSE of .042.042 is just below the failure threshold.

The table below gives RMSE at N=262,144N=262{,}144 trajectories, with 200 datasets per column (Table 4 in the paper).

MethodFull support, constant loggerMissing support, constantFull, bandMissing, bandWorst case
Bias-floor correction (ours).0055.0053.0055.0053.0055
Correction without shrinkage.0055.168.0055.190.190
FQE.0047.382.0044.403.403
WIS, count logger.0137.0127.0462.0421.0462
WIS, logistic logger.0091.0090.133.132.133
Doubly robust, count logger.0124.122.0114.0120.122
Doubly robust, logistic logger.0052.0050.0062.0340.0340
Doubly robust, true logger (extra access).0052.0052.0123.0117.0123

Each baseline that does not use the true logger is accurate in some columns and loses accuracy in others: its worst-column RMSE is between .034.034 and .40.40, against .0055.0055 for the bias-floor correction. That correction is accurate in all four and has the smallest worst-case error at every budget (Figure 2). The 95% bootstrap interval of every entry lies within ±18%\pm18\% of it. With full support, FQE is slightly more accurate.

The rule comes from Proposition A.1, which is new in the revision and formally verified in Lean. It shows that the main theorem holds with a radius split into a deterministic part, which accounts for directions the data cannot determine, and a noise part. The bias-floor rule keeps only the deterministic part. Corollary A.2, also verified in Lean, guarantees on every dataset that it makes no correction at a query whose target actions all have leverage above a cap, which is the case for the never-logged action here. Its accuracy is an empirical finding. The finite-sample accuracy guarantee applies to the theorem's radius, which makes no correction at these budgets (RMSE .60.60–.62.62, Table 4) and converges at larger ones, as shown in our second comment.

We also studied weak support (Appendix I.2, Table 5). A second protocol sweeps the logging probability of the critical action from 00 to .1.1 on 20 further models. At N=262,144N=262{,}144 the bias-floor correction with the smaller leverage cap τ=.1\tau=.1 stays between .0054.0054 and .0085.0085 over the whole sweep, as predicted; with the default cap τ=1\tau=1 it rises to .056.056 at probability 10−410^{-4} under the band logger. Under the same logger, FQE and the correction without shrinkage improve only gradually, from .38.38 and .18.18 at probability 00 to .13.13 and .074.074 at 10−410^{-4} and .012.012 and .0086.0086 at 10−210^{-2}.

Two further families are reported in Appendix I.3 (Table 6). RMSE at the largest budget:

SettingBias-floor (ours)Without shrinkageFQEWIS, count loggerDR, count logger
Three-stage example of Appendix D.4, unlogged action<10−4<10^{-4}.667.667<10−4<10^{-4}<10−4<10^{-4}
Same example, logger support .1.1<10−4<10^{-4}<10−4<10^{-4}<10−4<10^{-4}<10−4<10^{-4}<10−4<10^{-4}
Random linear MDPs, (d,H)=(4,3)(d,H)=(4,3).0083.0083.0056.0184.0124
(8,3)(8,3).0086.0086.0069.0178.0106
(8,5)(8,5).0157.0157.0099.0935.0486
(16,8)(16,8).0258.0259.0164.493.349

The random family has a full-support logger, the setting most favorable to FQE. There our rule stays within a factor 1.21.2–1.61.6 of FQE and is far more accurate than importance weighting at longer horizons.

On the three-stage example the verified rule itself converges: Algorithm 1 with the theorem's radius follows roughly the N−1/2N^{-1/2} rate, with RMSE .27.27, .072.072, .019.019, .0050.0050 at N=2×105N=2\times10^5, 3×1063\times10^6, 5×1075\times10^7, 8.1×1088.1\times10^8. On the random linear MDPs it remains conservative at the tested budgets (RMSE .22.22–.60.60).

On protocol, the pre-specified part of the study uses 9,380 independent test datasets from 80 test models and one fixed example. Each protocol and its predictions were fixed before its test data were drawn, and all methods share each dataset. The convergence run is counted separately, and the feature-dimension diagnostic of Appendix I.4 is descriptive, without a frozen protocol. The order of events matters for the leverage cap. The four-regime and benchmark studies were run first, with the default cap τ=1\tau=1. The smaller cap τ=.1\tau=.1 was then chosen on separate development models, after those test data had been inspected, and the support sweep tested it on new models. In Tables 4 and 6, which report the largest budgets, the two caps give the same values. The smaller cap costs accuracy when a block is small relative to the feature dimension (Appendix I.3). The code documentation gives protocols, seeds and commands, and every table is regenerated by one script.

For reference, the revision adds Proposition A.1 (split radius) and Corollary A.2 (zero correction above the leverage cap), with proofs and Lean verification (Appendices A.5 and F), and the numerical study: rules and baselines (I.1), the four-regime study and support sweep (I.2, Tables 4–5, Figure 2), two benchmark families and the convergence study (I.3, Table 6), and a feature-dimension study of Assumption 1 (I.4).

We hope the new study addresses your concern about the experimental part, and we would be glad to discuss any of it.

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

This paper provides statistical and computational complexity bound for off-policy evaluation problem in reinforcement learning. Specifically, with probability at least 1−δ1-\delta, it requires O(CH6dϵ−2)O(CH^6d\epsilon^{-2}) trajectories for error at most epsilon. This sample bound does not depends on state/action space.

Critical strengths
  1. presentation, writing, proof are easy to follow. As far as I can understand, they are correct. 2., the motivation for considering "safe" in RL is quite important
  2. the statitsical performacne guaranteee is very solid.
Critical weaknesses
  1. Please justify the Assumption 1, it covers each action-dependent replacement policy and each current state-action pair. It can be restrictive in practice.
  2. the computational complexity may be too conservative. discuss the bound presented in Appendix C2, page 18.
Questions for authors

In general, I feel this paper is clearly written and easy to follow. I recommend weak acceptance.

3 comments

Dear Reviewer zrxw,

Thank you for the careful review and for assessing the statistical guarantee as "very solid." Your two points led to a new proposition, formally verified in Lean, and a numerical study. We answer them in two comments.

Please justify the Assumption 1, it covers each action-dependent replacement policy and each current state-action pair. It can be restrictive in practice.

Assumption 1 is never stronger than the standard condition. All-policy linear realizability, used by Tkachuk et al. (COLT 2026, Theorem 1), implies it with the same features and norm bound (Corollary 3.3). Our guarantee therefore applies wherever theirs does, with an unknown logger and target coverage Ce≤CallC_e\le C_{\rm all}.

It can also be strictly weaker. In Proposition 5.1 two features suffice for every m≥3m\ge3, while all-policy realizability needs at least mm dimensions. Bounded linear MDPs satisfy the assumption, and Proposition E.1 gives a state-abstraction criterion under which it holds.

Both quantifiers come from the proof. On a valid confidence interval, the mean of a corrected label is the value of a policy that keeps the logged action with some probability and otherwise draws from the target, and this probability may depend on the action. The regression must represent these intermediate policies, which gives the policy quantifier. The regression is then queried at logged states for target actions, including actions never logged there, which gives the quantifier over current pairs. "Safe" refers to corrections that preserve this policy-value interpretation.

We also measured how demanding the assumption is. Appendix I.4 computes how well features of growing dimension realize replacement-policy values on ten models whose dynamics are a rank-four factor model plus a dense perturbation of weight ϵ\epsilon. With spectral features of dimension dd, the largest residual over 64 sampled replacement policies has median .28.28 at d=2d=2 and vanishes from d=4d=4 when ϵ=0\epsilon=0, where every stage matrix [Ph∣rh][P_h\mid r_h] has rank at most four. For ϵ=.05\epsilon=.05 it is .008.008–.011.011 for 5≤d≤325\le d\le32, within .0013.0013 of the residual over 64 sampled arbitrary policies. With these features and d≥5d\ge5, the bias-floor rule of Appendix I, an empirical variant of Algorithm 1 discussed in our second comment, has RMSE .015.015–.04.04 at N=65,536N=65{,}536, against .010.010–.012.012 for FQE and .31.31–.33.33 for Algorithm 1 with the theorem's radius.

the computational complexity may be too conservative. discuss the bound presented in Appendix C2, page 18.

We agree that the count in C.2 is conservative. The revision identifies where the slack comes from and what can be done about it.

For H=d=3H=d=3, B=1B=1, Ce=4C_e=4, δ=.05\delta=.05, ε=.1\varepsilon=.1, the closed form gives 2.72×10152.72\times10^{15} trajectories and direct verification of the error inequality gives 5.19×10115.19\times10^{11}. The radius is β=H+3H2Hlog⁡(8nH2/δ)\beta=H+3H\sqrt{2H\log(8nH^2/\delta)} times a leverage width. The first summand is a range bound. The second multiplies a worst-case noise scale, 3HH3H\sqrt H, by a union-bound quantile, and it dominates.

To see how conservative this is on an instance, we ran the verified rule on the three-stage example of Appendix D.4, which has different parameters (H=3H=3, d=2d=2, B=3B=3, Ce=4C_e=4). From N≈2×105N\approx2\times10^5 on its RMSE follows roughly the N−1/2N^{-1/2} rate: .14.14 at N=7.9×105N=7.9\times10^5, .072.072 at N=3.1×106N=3.1\times10^6 and .0050.0050 at N=8.1×108N=8.1\times10^8 (Appendix I.3). The sufficient count is a different kind of quantity, a high-probability guarantee that holds uniformly over all instances with these parameters. For this example and ε=.1\varepsilon=.1 it is 3.8×10113.8\times10^{11} by direct verification and 3.2×10153.2\times10^{15} in closed form, about five orders of magnitude above the budgets, between 7.9×1057.9\times10^5 and 3.1×1063.1\times10^6, at which the measured RMSE on this instance passes .1.1.

The revision also sharpens the statement. Proposition A.1, new and verified in Lean, shows that the main theorem holds with a smaller, split radius. Below a leverage cap τ∈[H/β,1]\tau\in[H/\beta,1] it is a deterministic width bounding the ridge bias, ∥V−1x∥2\lVert V^{-1}x\rVert_2, plus the noise multiplier times a noise width that vanishes in unobserved directions; above the cap it is the full range HH. The split radius never exceeds the original one, and the sample count is unchanged. It shows that protection against unsupported extrapolation comes from the deterministic width, which carries no logarithm and decays as 1/n1/n in observed directions. Corollary A.2, also verified, makes that protection unconditional: a query whose logged action, or every target action, has leverage above the cap receives a zero correction on every dataset, for every nonnegative noise multiplier.

Appendix I then asks what this buys in practice, using two rules that keep the deterministic width and reduce only the noise multiplier. With a plug-in residual scale in place of 3HH3H\sqrt H, no correction left its valid interval in any of the 9,380 test datasets, at the price of accuracy (RMSE .047.047–.053.053 in the four-regime study). With the noise multiplier set to zero (the "bias floor" rule), RMSE is .0053.0053–.0055.0055 at N=262,144N=262{,}144 in the four logger regimes over 20 models; this rule does leave the valid interval, at 23%–34% of queries with maximum overshoot .016.016, against 1.541.54 without shrinkage. In the same data the theorem's radius makes no correction (RMSE .60.60–.62.62). With a leverage cap of .1.1, chosen on development models after the four-regime data had been inspected and then tested on new models, its RMSE at N=262,144N=262{,}144 is at most .009.009 at each of the seven tested logging probabilities of the critical action from 00 to .1.1 (Table 5).

For these two rules the accuracy is empirical, while Corollary A.2 holds for them exactly. Extending the finite-sample accuracy guarantee to them, and closing the H4H^4 gap to the lower benchmark of Appendix G, are the natural next steps.

On computation, for a supplied dataset the cost is O(Hd3+Nd2+NH∣A∣d2)O(Hd^3+Nd^2+NH|\mathcal A|d^2) arithmetic operations (C.5). The four-regime study of 2,400 datasets runs in under three minutes on a laptop.

These points are now in the paper: Proposition A.1 and Corollary A.2 with proofs and Lean verification (Appendices A.5 and F), the numerical study of the radius rules against FQE and importance weighting, including the convergence of the verified rule (I.1–I.3), and the residual measurement for Assumption 1 (I.4).

Thank you again for both points, which improved the paper. We would be glad to continue the discussion.

Thank you for your efforts. I maintain my score.

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

This paper studies off-policy evaluation (OPE) from complete trajectories collected by an unknown fixed behavior policy. It proposes a backward regression estimator based on safe partial policy replacements: estimated advantages are conservatively shrunk so that corrected returns retain a valid policy-value interpretation. Under replacement-policy linear realizability and target occupancy coverage, the paper establishes a finite-sample guarantee of (O~(CeH6d/ε2))(\widetilde O(C_e H^6 d/\varepsilon^2)) trajectories without requiring behavior-policy probabilities or a model oracle. The paper also provides two separation constructions and formalizes the main finite-sample guarantee and the structural examples in Lean 4.

Critical strengths

The main advantage of this paper is its significant theoretical contribution, which reduces the assumptions under traditional OPE and improves the theoretical framework by reducing reliance on feature dimensions.

Critical weaknesses

For the first assumption in the paper, which is about the feature space assumption of the replacement strategy. Is it easy to satisfy this assumption regarding the structure in practical offline reinforcement learning tasks? Is there an experiment that can verify that this hypothesis is easily satisfied?

Questions for authors

The theoretical contribution of this article is very positive, but I am most concerned about assumption 1 in section 2.2. I believe that if the author could provide better explanations, it would help me better understand the paper.

1 comment

Dear Reviewer MBTp,

Thank you for recognizing the paper's "significant theoretical contribution." Your question about Assumption 1 led us to add a direct measurement.

Is it easy to satisfy this assumption regarding the structure in practical offline reinforcement learning tasks?

It holds whenever the standard condition holds. If the features represent the value of every policy, the condition used by Tkachuk et al. (COLT 2026), then Assumption 1 holds with the same features and norm bound (Corollary 3.3). Bounded linear MDPs are an example.

It can also hold with fewer features. Proposition 5.1 gives a family of instances indexed by m≥3m\ge3 on which two features suffice, while representing every policy needs dimension at least mm. Proposition E.1 gives a state-abstraction criterion.

The intuition is as follows. The algorithm moves each logged return toward what the target would have earned, by an amount that depends on its confidence. When the confidence intervals are valid, the conditional mean of the adjusted return is the value of an intermediate policy that sometimes keeps the logged action and sometimes follows the target. Assumption 1 asks the features to represent these intermediate policies, in addition to the logger and the target. Like linear-MDP or Bellman-completeness conditions, it is a modeling requirement on the feature map.

Is there an experiment that can verify that this hypothesis is easily satisfied?

The revision adds a diagnostic of this kind (Appendix I.4). We take ten random models whose dynamics are a rank-four factor model plus a dense perturbation, compute spectral features of dimension dd from the model, and measure the worst representation error over 64 intermediate policies (the logger, the target and 62 sampled ones). The table gives the median over the ten models.

Features dd2345 and above
Error, no perturbation.28.1000
Error, 5% perturbation.30.12.050.008–.011

Without perturbation the error vanishes once dd reaches four, the largest rank of the model's stage matrices; with a 5% perturbation it settles near .01.01 from d=5d=5. From d=5d=5 it is within .0013.0013 of the corresponding error over 64 sampled arbitrary policies, so on these models the features represent the intermediate policies as accurately as arbitrary ones. The same features also support accurate evaluation: with d≥5d\ge5 and N=65,536N=65{,}536 trajectories, the bias-floor rule of Appendix I, a variant of Algorithm 1 whose accuracy is an empirical finding, has RMSE between .015.015 and .04.04, against .010.010–.012.012 for fitted Q evaluation and .31.31–.33.33 for Algorithm 1 with the theorem's radius.

This is a diagnostic on finitely many policies, with features computed from the true model. It shows how the requirement behaves as the feature dimension grows in a controlled family; it does not settle how often the assumption holds in practical tasks.

Appendix I.2 additionally evaluates Algorithm 1 and its empirical variants on 40 models that satisfy the assumption with three features and 65,536 states in each middle layer. There the bias-floor variant is accurate, while the theorem's radius makes no correction at the tested budgets.

In the revision, the feature-dimension measurement of Assumption 1 is in Appendix I.4, and the numerical study of the estimator on models satisfying it is in Appendix I.2–I.3.

We hope this answers both questions, and we are happy to discuss Assumption 1 further.

Comments on the paper

1 comment

Dear Area Chair and Reviewers,

Thank you to Reviewers MBTp, zrxw, and 6ZwH for the reviews, and to Reviewer zrxw for following up. As the discussion period closes, we briefly summarize what the revised manuscript adds on the three questions raised.

On Assumption 1 (MBTp, zrxw), besides holding under all-policy realizability (Corollary 3.3) and state abstraction (Proposition E.1), Appendix I.4 measures representation error on perturbed rank-four models: with spectral features of dimension d≥5d \ge 5 under a 5% perturbation, the residual over sampled replacement policies is .008-.011, within .0013 of arbitrary policies.

On radius conservatism (zrxw), Proposition A.1 and Corollary A.2 (Appendices A.5 and F, verified in Lean 4) split the radius into a deterministic ridge-bias width and a noise width, giving zero correction above the leverage cap on every dataset, while Appendix I.3 shows Algorithm 1 with the theorem's radius converging at roughly the N−1/2N^{-1/2} rate on the three-stage example.

On the empirical evaluation (6ZwH, MBTp), Appendix I compares our estimator and split-radius variants against FQE, WIS, and DR on 9,380 pre-specified test datasets (Tables 4-6, Figure 2; 43 of 44 predictions held). The bias-floor rule has worst-regime RMSE .0055 at N=262,144N = 262,144 (vs. .034-.403 for baselines without the true logger), stays at .0054-.0085 across the weak-support sweep, and remains within a factor 1.2-1.6 of FQE under full support.

Thank you again for your time and feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.