Conformal Prediction Beyond the Horizon: Distribution-Free Inference for Policy Evaluation
Authors: Feichen Gan
Lu Youcun
Yingying Zhang
Yukun Liu
Venue: NeurIPS 2025 poster ()
Keywords: Conformal Prediction
Reinforcement Learning
Policy Evaluation
Infinite-Horizon
Primary area: reinforcement_learning
TL;DR: We propose a unified conformal prediction framework for infinite-horizon policy evaluation that seamlessly accommodates both on-policy and off-policy scenarios.

Abstract: Reliable uncertainty quantification is crucial for reinforcement learning (RL) in high-stakes settings. We propose a unified conformal prediction framework for infinite-horizon policy evaluation that constructs distribution-free prediction intervals for returns in both on-policy and off-policy settings. Our method integrates distributional RL with conformal calibration, addressing challenges such as unobserved returns, temporal dependencies, and distributional shifts. We propose a modular pseudo-return construction based on truncated rollouts and a time-aware calibration strategy using experience replay and weighted subsampling. These innovations mitigate model bias and restore approximate exchangeability, enabling uncertainty quantification even under policy shifts. Our theoretical analysis provides coverage guarantees that account for model misspecification and importance weight estimation. Empirical results, including experiments in synthetic and benchmark environments like Mountain Car, show that our method significantly improves coverage and reliability over standard distributional RL baselines.

Conformal Prediction Beyond the Horizon: Distribution-Free Inference for Policy Evaluation
Feichen Gan, Youcun Lu, Yingying Zhang' and Yukun Liu
KLATASDS MOF, School of Statistics, East China Normal University
Abstract
Reliable uncertainty quantification is crucial for reinforcement learning (RL) in high-stakes settings. We propose unified conformal prediction framework for infinite-horizon policy evaluation that constructs distribution-fied prediction inter- vals for returns in both on-policy and off-policy settings. Our method integrates distributional RL with conformal calibration, addressing challenges such un- observed returns, temporal dependencies, and distributional shifts. We propose a modular pseudo-return construction based truncated rollouts and time-aware calibration strategy using experience replay and weighted subsampling. These in- novations mitigate model bias and restore approximate exchangeability. enabling uncertainty quantification even under policy shifts. Our thcoretical analysis pro- vides coverage guarantees that account for model misspecification and impor- tance weight estimation. Empirical results, including experiments in synthetic and benchmark environments like Mountain Car, show that method significantly improves coverage and reliability over standard distributional RL baselines.
Introduction
Motivation. As reinforcement learning (RL) are increasingly deployed in high-stakes domains, such healthcare, robotics, and autonomous systems, robust uncertainty quantification becomes essential. While traditional policy evaluation methods focus on estimating the expected return, this insufficient when decisions must account for risk, reliability, and rare outcomes. For example, in clinical decision-making, treatment policy may appear beneficial on average but hide adverse effects for specific patient subgroups. Even in less safety-sensitive applications such as recommen- dation systems or finance, overlooking uncertainty can lead to unstable behavior and degraded user experience. Prediction intervals (PIs) for returns offer a principled way to quantify uncertainty, en- abling risk-aware planning and safer deployments.
This paper focuses constructing valid Pis for infinitehhorizon RL settings, where the return is defined as the sum of discounted rewards. In on-policy settings, PIs help assess the variability of returns under the current policy, enabling more robust policy improvement and risk-sensitive exploration. In off-policy scenarios, where evaluating new policy offline based on an observational dataset, PIs serve gauge the reliability of point estimation from historical data. By constructing PIs for the return, our approach improves the transparency, reliability, and robustness of RL systems across a wide range of domains.
Challenges. Constructing valid PIs for returns in RL is closely tied to estimating the full return distribution, studied in Distributional RL (DRL). In principle, conditional quantiles from this distribution can be used to form Pls. However, existing DRL-based approaches often suffer from model misspecification, leading biased or inconsistent return distribution estimates and a lack of
Corresponning author: www.an/@@@ecccc.cc...co.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

formal statistical guarantees. To address this, building on the framework of conformal prediction. we propose a flexible, model-agnostic methodology for constructing PIs with asymptotic coverage guarantees. Applying conformal prediction to the infinite-horizon RI. setting requires substantial methodological innovation, as it poses several fundamental challenges:
Unobserved Returns. In infinite-horizon RL, the return cannot be directly observed, since in practice only finite-horizon trajectories (of length T) are available and future rewards beyond T are unobserved. Although mitigated by discounting, the truncation error remains non-negligible in offline settings when I' is moderate, making it challenging to evaluate prediction errors calibrate uncertainty.
Temporal Dependence. RL data are inherently sequential, violating the exchangeability assump- tion required by standard conformal prediction methods.
Distribution Shifts. In on-policy setting, discrepancies over time lead to complex covariate shift in the state distribution. In off- off-policy evaluation, discrepancies between the behavior policy and the target policy also lead to covariate shift the state-action distribution.
Contributions. We propose novel, distribution-free method that integrates conformal prediction with distributional RL to construct prediction intervals for infinite-horizon returns under both on- policy and off-policy settings. Our contributions are as follows: (1) Pseudo-Returi Construction. We develop a modular approximation scheme for unobserved returns, combining truncated rollouts with tail sampling from learned return distributions. This design is inspired by temporal cemporal-difference -differncce learning and enables calibration despite partial observability. (2) Calibration via Experience Replay. To mitigate temporal dependence and approximate exchangeability, we adopt experience replay and apply random subsampling to the calibration set. This design recovers approximate exchangeability. enabling valid conformal calibration. (3) Time-Aware Weighted Subsampling. We address distri- bution shifts both over time and between policies, using a simple, weighted subsampling scheme. This enables valid calibration in off-policy settings and improves efficiency in on-policy scenarios. (4) Theoretical Guarantees. We establish asymptotic lower bounds on coverage using Wasserstein metries, characterizing how model bias and density ratio estimation affect conformal validity. (5) Empirical Validation. We demonstrate the effectiveness of our method through empirical studies on synthetic and the Mountain Car environments.
Together, these contributions extend conformal prediction to the anfinitehhoizon RL setting and offer a scalable, practical framework for uncertainty-awant policy evaluation.
1.1 Related Work
Risk-aware RL. RL is a framework in which an agent interacts with an unknown environment to maximize its expected total reward. Due to the intrinsic randomness of the environment. even policies with high expected returns may occasionally yield very low rewards, which can be problem- atic in risk-sensitive applications such healthcare [19] or competitive games [21]. For instance, in clinical decision-making patient responses to treatments are stochastic, making it desirable to select actions that achieve high effectiveness while minimizing the likelihood of adverse effects. To address these concerns, awsee RL aims to learn policies that reduce the probability of low to- tal rewards [16], using variety of risk measures including entropic or exponential utility [11, 22], conditional value-at-risk [25, 6]. and coherent risk measures [18].
In parallel, safe RL and constrained Markov Decision Processes (MDPs) offer an alternative ap- proach to managing uncertainty; a comprehensive survey of safe RL is provided in [14]. Unlike risk-aware MDPs, these methods do not modify the optimality criteria; instead, risk aversion is en- forced through constraints on rewards or risks [5]. While both risk-aware and safe RL approaches incorporate risk considerations into policy learning, they primarily focus modeling risk prefer- ences and generally do not provide formal uncertainty quantification for Pls.
Distributional RL. Distributional RL focuses on modeling the full return distribution rather than just its expectation. Pioneering work by [2] introduces this paradigm, followed by quantile-based approaches such as Quantile Temporal Difference (QTD) learning [7, 27]. which approximates re- turn distributions via quantile regression. These methods have led to practical advances roboties, control, and decision decision-making making under uncertainty [1, 4, 10, 34]. However, most DRL methods provide

---

pointwise quantile estimates and lack formal statistical coverage guarantees, especially under model misspecification.
By integrating conformal prediction with DRL- distribution estimation, our framework ensures asymptotic coverage for predictive intervals, even in challenging infinite-horizon settings.
Conformal Prediction for RL. Conformal prediction offers distribution-fiee confidence intervals under exchangeable data [32]. Extending it to RL is challenging due to the inherent temporal de- pendencies and evolving state distributions. Recent efforts have attempled to bridge this gap. Early work such [8] applies conformal prediction to construct trajectory
prediction intervals in finite-horizon MDPs. Building on this idea, [12] develop a weighted conformal prediction method for off- off-policy evaluation, using importance sampling weights to correct for distributional shifts be- tween behavior and target policies. However, this approach suffers from the curse of horizon, as the importance weights accumulate multiplicatively over time, resulting in high variance in long-horizon settings. In parallel. [35] introduce the COPP algorithm for contextual bandits, which approximates exchangeability via pseudo-policies and trajectory subsampling; yet, its applicability is largely lim- ited to short-horizon problems with finite discrete action spaces. [36] further analyze how temporal correlations in Markovian data affect the coverage and width of split conformal intervals. Finally, we note a growing line of work that applies adaptive conformal prediction to online safe RL settings [29, 37J, which differs fundamentally from our setting.
Despite these advances, existing methods largely focus on finite-horizon scenarios or on settings with limited state or action spaces. Prior conformal RI. approaches typically handle distribution shifts between behavior and target policies using trajectory-level importance weighting, which be- comes computationally inefficient the trajectory horizon grows. In contrast, our work is the first to tackle mulinitehhorizor off-policy prediction in general RL settings with arbitrary state and action spaces using conformal prediction. By constructing stepwise pseudo-returns and leveraging expe- rience replay, our method scales conformal prediction to infinite-horizon settings with standard RL data and remains effective even when only partial trajectory fragments are available.
2 Problem Formulation
We consider the standard RL framework [2, 17, 30), where the environment is modeled as time- homogeneous MDP, as specified in the assumptions provided in the supplementary material. Our goal is to construct distribution free PIs for the return of given policy in infinite- -hrizon settings under both on-policy and off-policy scenarios.
Data and Setup. Let D = { be a dataset of N trajectories, each consisting of I' time steps. For simplicity, we assume trajectories have uniform length, but our method naturally extends to variable-length settings. Each trajectory 4; ((S,, Aue R2c) TT consists of the state Sa the action Ag and the immediate reward R4t. These transitions are generated by a behavior policy To, such that Aa ~ Tx(- S/)) and evolve under transition kernel P with (Ru, St,++) ~ P(- S Aa). In healthcare applications, each trajectory corresponds to a patient, with S₁, representing clinical features, Art the administered treatment, and R,, the resulting clinical response.
Objective. Let i be target policy of interest. The return starting from the state is defined as (T)ss= E 7 Re, where R2 the reward at time t under policy æ and y E (0, 1) is the discount factor. This return captures the long-term outcome of following policy π from state s. Given new test state Sust. we aim construct a prediction interval for GH GO (Stest) that achieves a sper-spe
coverage level - a. That is, we seek set C(Sust) such that:
Pr(GT (Sues) E C(Susst) 2 1 a.
In healthcare applications, GH (Suest) represents the long-term treatment effect for new patient under policy и. The prediction interval thus provides principled range of plausible outcomes for the patient, enabling informed decision-making before the policy is actually deployed in practice. In this paper, we consider two settings:
1. On-Policy Setting: the target policy n is the same as the behavior policy ny. This setting enables evaluation using in-distribution transitions, but still faces the challenges of infinite horizon and unobserved returns.
3

---

2. Off-Policy Setting: the target policy т differs from To. In this case, the data distribution differs from that under the target policy, and appropriate corrections for distribution shift are necessary.
Preliminaries of DRL. The goal of DRL is learn the distribution of returns (s) for each state s. Let (s) denote the the probability distribution of the random return. Numerous DRL methods exist for both on-policy and off- off-policy settings [3]. In this paper, we adopt quantile tem- poral difference (QTD) learning for experiments, a prominent approach within DRL. QTD seeks to approximate the return distribution by 11" (s) R m _i=1 δe(a,)), which is an equally mixture of Dirac deltas at locations 0(s, i). The aim is have these particles approximate the = (2i - 1)/(2m)-th quantiles of (7) for = I,..., m. Like other temporal-difference meth- ods, QTD updates its parameters {(0(s, i) =0) using observed transitions (Sye, Rae. St,441). In continuous and nigh-dimensional state spaces, function approximation offers powerful approach for modeling ((((s, }) and generalizing across states.
Limitations of DRL. A naive approach to constructing PIs would be to take the empirical quantiles of of (x), f.e. using [0(s, ((),((s)))) where I. == [(ma+1)/2 and m++1 - T. However, such DRL-bbased quantile intervals, referred to as DRI.QQR, can be unreliable finite-sample settings and do not come with formal guarantees of asymptotic validity. For instance, [3] show that the QTD algorithm converges to a limiting distribution in finite state and action spaces; yet this limiting dis- tribution not guaranteed to match the true return distribution, and thus the convergence provides no assurance that QTD-based prediction intervals are asymptotically valid. In continuous state and action spaces, distributional RL methods must rely on function approximation distributions. The theoretical guarantees of these approaches consequently depend critically on the accuracy of the modeling assumptions, rendering them susceptible to potential model misspecifica- tion. To address these limitations, we develop conformal prediction framework that wraps around any return distribution estimator (such as QTD), correcting for model bias and enabling finite-sample statistical guarantees.
estimate return
Conformal Policy Prediction Beyond the Horizon
We propose novel conformal prediction (CP) framework that addresses the unique challenges of uncertainty quantification in infinite- -oriztn RL. Our approach combines three key innovations: (1) pseudo-returns that blend finite rollouts with learned distributional tails, (2) time-aware calibration addressing both temporal dependence and distribution shifts, and (3) replay- based weighted subsam- pling to restore exchangeability.
3.1 Overview of the Conformal Framework
Our method follows the split conformal prediction paradigm, adapted to the RI. setting. Given a dataset of transition tuples {Sa, Aa, Riz, S,,+1)), we partition it into training set Drr used to fit a predictive model for the return distribution, and calibration set Deal, used to quantify predictive uncertainty. The overall pipeline consists of four key steps illustrated in Figure 1:
1. Train a DRL model, such as QTD learning, on Dúr to construct a return distribution estimate (s) and value function estimate 6td (s) under the target policy π.
For each calibration state, construct pseudo-returns by combining observed rewards with samples drawn from the estimated return distribution. The procedure for generating pseudo-returns is detailed in Section 3.2.
3. Compute nonconformity scores using the pseudo-returns in the calibration set, typically using the absolute deviation from the estimated value function: V(s) = G (s) - (s)], where (*)( denotes the pseudo-return.
4. Apply conformal prediction to construct a prediction interval for a new test state Steets using weighted subsampling adjust for distribution shifts and experience replay approximate ex- changeability by decorrelating transitions, detailed in Section 3.3.
The nonconformity score plays a central role in quantifying uncertainty and correcting for potential estimation bias. While our framework is compatible with more sophisticated nonconformity mea-

---

sures, such as those used in conformalized quantile regression [26], the Double-quantily score [12]. and various others. we use the simple absolute-error score here for clarity and illustration.
Input
Training set
DRL model (*(A)
Experience Replay
Conformal Prediction
Output
Observed trajectoriss
Paeuaoo relurn (m00)
Rarkanl U.5 577 Si.5
Cur
Gaa
Calibaaton sel
Roplay bufler
Figure 1: Pipeline of the proposed conformal policy prediction framework.
3.2 Pseudo-Return Construction via Truncated Rollouts
A key challenge in infinite-horizon RL is that the true return (s) is unobservable in a finite-step trajectory, making difficult to directly evaluate nonconformity scores for conformal prediction. To address this, we introduce a novel pseudo-return construction that inspired by k-step temporal difference (TD) learning. We reinterprete k-step TD learning through the lens of distributional inference. Specifically, for each calibration point (Sa, Au, Rai S1,+1),, we define the k-step pseudo- return as:
k-1
(S,) = Σ A Ri,4h + (S,,,t))
h=0
where the first term accumulates observed rewards under the behavior policy To. and the second term approximates the unobserved tail using sample from the estimated return distribution (Si,,44))
Advantages Pseudo-return construction approximates the infinite- horizon return using a finite rollouts combined with bootstrapped tail. First, this decomposition bridges model-based and model-free RL. within the conformal inference framework. Second, the tail value sampled from learned return distribution, allowing seamless integration with DRL methods such QTD C51 [2]. Finally, the rollout horizon & offers a natural bias-variance trade-off: increasing l incorporates more observed data, potentially reducing model bias but requiring longer rollouts; decreasing increases reliance on model predictions, offering faster calibration at the cost of higher bias.
On-policy setting. We detail the QTD learning procedure for DRL used in this paper, although any DRL estimation method can be integrated into our framework. In the on-policy case, QTD estimates the return distribution conditioned on the initial state, f (s), via the iterative update
0(s, i) - (s. +p-
T T(r +0
(30 (1) ((s 0)],
where A(s, i) denotes the -, quantile ij (s), (8, a, s'))) is sampled under the behavior policy x, which coincides with the target policy in the on-policy setting, and is a learning rate.
Off-policy setting. Extending QTD to the off-policy setting requires careful modifications to ac- count for distributional shifts between n. and æ. We first define the return starting from a state-action pair as G (x, a) E:zo 7 R. where the agent takes action a in state and follows policy there- after. The distribution of this return is denoted by 17" a). The goal of QTD is to estimate the
5

---

quantile functions of (s. The iterative update for the 7,-th quantile ((s, a, i) is given by
0(s + (s)
a)
2 IT 70''s
a(s,a, 0)],
where ((s, a, i) is the T--th quantile of (s, a). (s, a. s') sampled from the behavior policy mi- and a' is drawn from the target policy The result is marginalized over the action space according to T: (s) = En ((" (s, a). This modification necessary to correct for the action distribution mismatch between behavior and target policies. For further details on distributional RI. in off-policy evaluation, see [23, 15].
3.3 Time-Aware Calibration via Experience Replay and Weighted Subsampling
A core challenge in applying CP to RL lies in the violation of its key assumption: exchangeability between the calibration and test data. In RL, this is broken due to (i) temporal dependencies across transitions and (ii) distribution shifts in the state space both over time and across policies. To address these challenges, we introduce two-pronged calibration strategy through experience replay-base based sampling to decorrelate temporally linked transitions and time-aware importance weighting to cor- rect for dynamic policy-dependent distributional shifts.
Experience Replay. Temporal dependence between transitions in RL makes the direct application of conformal prediction invalid. To mitigate this, we draw inspiration from deep RL techniques and treat the calibration set as a replay buffer, storing transition tuples (Sat Au,, Rit, S1,++)) We then apply random subsampling from this buffer construct approximately i.i.d. calibration samples [9]. This technique mirrors the prioritized or uniform experience replay used in deep Q-learning, effectively decorrelating transitions [28]. For the construction of k-step pseudo-returss, we store S1,++)]
extended tuples of the form {SSa, Au.
Weighted Subsampling (WS). Instead of adopting weighted conformal prediction (WCP) [31], which is commonly used to correct for covariate shifts. we employ a sampling- -bsed strategy. Specif- ically, we perform weighted subsampling from the calibration buffer based estimated importance weights, producing a recalibrated set of approximately exchangeable samples tailored to the target distribution. The importance weights differ depending on whether the setting is on-policy off- policy:
1. On-Policy Setting. Here, the distribution shift stems from time-indexed variation in state visita- tion. We define the importance weight as
dPo(s) dP
P() 0) 3)) x
p(o 1
Won
(2)
P(O 0
where Po is the probability distribution of test states, Pesl is the marginal probability distribution over calibration states, and 8 is an indicator variable, where calibration set, and å = indicates that is in the test set. The second equality in Eq. (2) follows from Bayes rule, expressing the likelihood ratio as a ratio of classifier probabilities [13, 24]. In practice, (s) can be estimated using standard propensity scoring or density ratio estimation methods. In simulations. we employ logistic regression for this purpose.
denotes that belongs the
2. Off-Policy Setting, In this case, both temporal drift and policy mismatch must be corrected. We define the importance weight over a k-step trajectory segment as
d'Po(so)
1-1 1 Taa 8h)
Worl (50, .o......y.. sk) x d' (s0)
(3)
(30)
h= (a
This formulation adjusts for discrepancies in both state visitation and action selection between the behavior and target policies. This ratio can also be estimated using propensity scoring techniques.
To reduce the variance in PIs caused by subsampling randomness, we repeat the process B times and aggregate the intervals. This technique draws from recent work conformal prediction under dis- tribution shift [35] and improves both coverage stability and efficiency. The complete algorithm for the on-policy setting in Algorithm 1, while the off-policy version is deferred to the supplementary material to save space.

---

Why WS Works. In the off-policy setting, let Sws := Swat denote a test state drawn from the marginal distribution Po(s). and consider the joint distribution:
(Stest A Rust, ................................ Sust GO (Sust.)) Po" do To. ................................ Sks G). Similarly, let Poff denote the joint distribution of rollout segments in the calibration set:
(Sa, Ast, Ra..... G (Sx)) ~ Pall (80, do ro, 88, G). The two distributions are related through the importance weight Worrs such that:
dPol (Su+ do, ro. G) Wor (S,, dp.............................. ............ 8k) d'Pall (so: oo, ro..... Sky G).
(4)
This identity shows that sampling from the calibration distribution according to the importance weights Woll produces samples that approximate the test-time distribution Po By reweighting the calibration set in this way, we recover approximate exchangeability between the calibration and test samples, thereby restoring the validity of conformal prediction in the presence of both temporal and policy-induced distribution shifts.
Why Not Use WCP. Weighted conformal prediction (WCP) typically assumes access to the full
set of test-time covariates, In contrast, our setting only observes the initial state Sies.o at test time,
while subsequent states S Swa,& remain unobserved. The WCP weight defined in
Eq. 12 of [12] involves marginalizing over entire trajectories, which are unobserved. Although [12] further propose an optimization-
approximation (Eq. 14), this approach introduces additional model assumptions and tends to exhibit high variance, especially in long-horizon settings, limiting their practical applicability in our context. On the other hand, while one could adopt more elaborate designs such as that of [35] tailored for sequential decision- making, weighted subsampling scheme offers a significantly simpler and more practical alternative, especially when only the initial states of test trajectories are observed.
Theoretical Results
In this section, we provide statistical guarantees for the PIs constructed by our method. Standard CP yields marginal coverage at level a under the assumption of exchangeability. However, in practice, distribution shifts violate this assumption, leading to gap between the nominal level 1 - a and the actual coverage. Previous studies have bounded this gap using total variation dis- tance, which fails to capture how different choices of k-step rollouts affect the coverage gap. To address this, we propose a tighter upper bound on the coverage gap based the Wasserstein distance, leveraging a recent theoretical result from [33]. Let μ and v be two probability mea- sures the real space R. For any p > O, the p- Wassersstnin distance between μ and v is defined as v), := inf infR {aax |x yi (x(dd, )/p, where [(u, v) denotes the set of all cou- plings with marginals μ and v.
Let be the cardinality of the calibration set Deal. and (s) denote estimate of the re- turn distribution r7'(s) under the target policy т. We take to be the state space and define Wi(n", , 77") == supses Wi (1))ss),, (s)). Let (s)(s) be an estimate of the on-policy importance weight defined in (2), and let CR (.) be the prediction interval produced by Algorithm 1. The following theorem establishes asymptotic lower bound on the coverage in the on-policy setting.
Condition 1. (i) The return distribution n7 (s) has Lebesgue density bounded by L for all E S. (ii) E[ ( (Sa) | [D.,] < 3o and E| (Sa)) < co for all 0 < t T k.
THEOREM (On-Policy Coverage Guarantee). Assume Condition 1, and redefine won(s) as so that --kF ΣT-K E|won (St) (Pul 1. Then
won(s) (s)/ T ET-
lim Pr THHH (Stea) E Öon (Steat)) n-0
-aaaa-Aoonnn > 1 a a- A(Won )" where
T-k
A(won; 2(T - k +
[|ioon (Stt) (S:))l + + 22L [W
7

---

Algorithm 1: for Infinite Horizon On-policy Evaluation
Data: D {(S,, Au, Ru,,S,, S1,,+) S N,ists TT) and state Steat.
Input: 1 - a, target coverage level; A, an on-policy distributional RL algorithm; W, density ratio estimation algorithm; k, step width; B, resampling number; subsample size; 5.
multiple subsampling parameter
Output: Prediction interval for G* (Stest)
Split the data: D = Drr U Deal where Der [(Su, Ait, S(t+1) (7, E Iir) and : (i,4) E Iem)]. Here, Ier and Zeal denote the indices of transitions in the training and calibration datasets, respectively.
=
= ((Sit, Ase: Rit, .l..,.... ...,,,.,. S(,+.)
2 Train a conditional return model f) using A based on Du.
Obtain the value function estimator 0 (s). the expectation of (s).
Obtain Won (s) as an estimator the density ratio (2) based on {Soo (i, 0) E Inc and
{Ste (i,t) I using W.
5 for b = 1 B do
Sample / data tuples {(Sa, Ar.,, Rs ......... S1,+k) (i,t) I from Deat according to the importance weight won (S²)).
Calculate pseudo return (I) and obtain ((0) cal
: {(Stt. (( (i, E I(A)
Calculate the nonconformity scores: {Vx = ( 0"d (St)] (i, E EZ
Obtain o the [1(1 - a smallest value of (Vi : (1.t) I
Obtain (b)
Na (Sust) 8td (Sust) + fi-as-
Result: A conformal predictive region for GH (Suat) with coverage rate of a is
Ton CN (Srest) = (G
1 B
Σ
G
2(0)
(Srest) 2 1 2
(5)
B
Theorem 1 shows that the deviation from nominal coverage depends on two main factors: (i) the estimation error in the importance weights, which arises due to the distribution shift, and (ii) the approximation error in the return distribution 7" (s), measured by the Wasserstein distance. Notably, the second term decays with the truncation step & at rate proportional to y². When the approxima- tion error in the return distribution 7 (s) is large, choosing a larger & can help reduce the deviation from nominal coverage by relying more observed rewards. However, this introduces trade-off: too large, it becomes difficult to accurately estimate the off-policy weights, especially un- der substantial distributional shifts. In this case, the method effectively reduces to a Monte Carlo estimator that relies on full trajectories, resulting in the high variance we aim to avoid.
Next, we establish an asymptotic lower bound on the coverage of the PI in the off-policy setting. Let non() (.) be an estimate of the importance weight worl (.) defined in (4). Let Cxff (.) denote the conformal interval produced by Algorithm I in the supplementary material.
Condition 2. (i) The return distribution 17 (s) has a Lebesgue density bounded by L. for all s E S. (ii) of (He::++)) [Dtr] < oo, (HHe+++) < oo for all 0 < < T - k. where Hast k == (Se, Ap..... .,+4). denotes the local trajectory segment following policy TG, independent of Dur- (iii) (overlapping) (a(ss) s) is uniformly bounded away from O for any
THEOREM 2 (Off-Policy Coverage Guarantee). Assume Condition 2, and redefine Wonl (Su, ag...... ... 1k-1) as wor(So. ag...., . T-K+1
ΣT=
T-k E[ioa (Hea- so that
(Hea)n)))ud) (1 - ET- Elwot
= Then we have
lim Pr (GTh (Stest) CN. (Scest) > 1( f),, where n-0
T-k
A(Wott (7) 2(T - 11
off (Hess:u) - wast (Hee44 + 22 [W((
8

---

Theorem 2 shows that the coverage deviation has the same form as in the on on-policy case (Theorem 1). The main difference the additional estimation error in the importance weights Coff which arises from evaluating different target policy.
Remark. For continuous return distributions, the bounded Lebesgue density assumption is mild and typically satisfied practice. It holds for many commonly-used distributions, including the Gaussian, exponential, and Gamma distributions with shape parameter no less than 1. For example, in Examples and 2 of our experiments, the return distributions can be readily verified to satisfy this condition. In contrast, this assumption does not apply to discrete return distributions, as discrete random variables are not absolutely continuous with respect to the Lebesgue measure. Hence, the bounded density condition is neither required nor meaningful for discrete returns, as in Example of our experiments.
5 Experiments
In this section, we conduct simulation studies to investigate the empirical performance of our pro- posed methods. In particular, we focus on the following two examples:
Example I: two-state MDP (Example 3 of [27]) The state space of the environment discrete with two possible values: and 12. The agent transfers from current state to different state with a certain probability determined by the policy and the discount factor is 7 = 0.8. The reward obtained when transitioning from state 2 is distributed as (2, 1), and the reward obtained when transitioning from state 22 is distributed as (),
Example 2: continuous state (Scenario B of [30]) The action is binary and S(+1 = (S.+1,1, St+12), where S1+1.1 3(2A,
1) 2r,1, SH+12 3(1 2A,)Sr,2 + 21,2 21 = (2,,1, 21,), for 2 (0th20~~(022.) 12,,1//4) are i.i.d and So ~ N (02,, 12). The immedi- ate reward R2 2S,+1,1 S41,2 (2A, 1)/4. The discount factor is y 0.8.
For each example, we consider both an on-policy setting and an off off-policy setting:
In Example 1, when there is no policy shift, the probabilities of transferring from #1 to 22 and x2 to Iy 0.4 and 0.8, respectively, when there exists policy shift, the training data has the same transition dynamics as in the on-policy setting, while the test agent transitions from æ1 to 22 with probability 0.5 and from 22 21 with probability 0.7.
Example 2, when there is no policy shift, both the observed data and the test agents satisfy + (S):;) when there exists a policy shift, the observed data follows the same policy as in the on-policy setting while the test data satisfies Pr(A. SSS 0.6sigmoid(( (S,,) + 0. 4sigmoid(Ss.)).
Pr(A, = S), 0.5sigmoid(S5
Implementation details. The sample size is fixed to N = 400 for Example 1 and N = 200 for Example 2, with each trajectory consisting of = 30 stages. For Example 1, we approximate the return distribution using 20 conditional quantiles estimated by QTD. In Example 2, where the state space continuous, we use 30 conditional quantiles estimated by QTD and model the conditional quantile functions with neural network. The detailed architecture of the neural network is provided in the supplementary material. We evaluate the performance of the proposed method with step sizes k ...... 5, and set the number of intervals B 50. For each simulation, points from the target policy to evaluate the converge probability. In the supplementary material, we include simulation results for Example to examine the impact of and k a comparison with [12] based on the same example, and an extension of Example to a high-dimensional setting.
generate 310 test
Benchmark and Results. We compare our method with the quantile region given by the learned QTD model (DRL-QR). Since the DRL algorithm directly learns the return distribution = : by (S), a quantile region for the test instance Stest can be constructed as (Q./((Stes). Q (1-a/2(S(ex)) where Q is the ä-th quantile of (Stostt) Figure 2 presents boxplots based on 50 independent repetitions. It shows that our method consistently achieves near- nominal 90% coverage across various k-step pscudo-returns in both on- on-policy and off off-policy settings.

---

In contrast, the DRL-QR baseline suffers from undercoverage due to model bias in the estimated re- turn distribution. This highlights the effectiveness of our conformal framework in correcting such bias and ensuring valid uncertainty quantification. We also observe that the average interval length increases with larger k reflecting the higher variance introduced by longer truncation horizons.
(a) Coverage probability
(b) Average length
Coverage probability and average interval length at the 90% level for the proposed method with k-step pseudo-returns (k .,...... 5. from left right) and DRL-QR (rightmost), under on- policy and off-policy settings in Example (columns 1-2) and Example 2 (columns 3-4).
Figure 2:
Example 3: Mountain Car (adapted from [17]) We generate the dataset using a behavior policy defined m aTQ (1 a), where To is policy trained via Q-learning. Nо is uniformly random policy, and a = 0.3. The target policy is constructed similarly with a = 0.2, reflecting an off-policy setting. To conserve space, implementation details and results provided in the sup- plementary material. As benchmark, we apply kernel density estimation (KDE) to approximate the return distribution from Monte Carlo rollouts and construct baseline prediction intervals using quantiles (KDE-QR). As shown in Figure of the supplementary material, our method effectively corrects the model bias in KDE and achieves near-nominal 90% coverage, highlighting the robust- ness of the proposed CP framework in complex, continuous control task.
Conclusion
In this paper, we propose a novel CP framework for infinite-horizon policy evaluation with asymp- totic coverage guarantees. By constructing k-step pseudo-returns, method balances predictive accuracy and statistical efficiency, addressing key challenges in long-horizon evaluation. This for- mulation enables the construction of valid PIs without relying full trajectory rollouts. Although the choice of remains underexplored, we suggest practical remedies such as evaluating stability across multiple values (e.g., intervals are correlated, aggregation is nontrivial. A promising direction is to construct unified prediction region by combining the corresponding p-values, leveraging the connection between pre- diction intervals and hypothesis testing. Methods such as the Cauchy Combination Test [20], which robust arbitrary dependencies, offer viable approach. Moreover, extending framework to policy optimization represents an exciting avenue for future work and could further broaden the applicability of conformal prediction in RL.
1, ...... 5) or aggregating PIs across different k. Since these
Acknowledgement
Zhang's 's research was supported by the National Natural Science Foundation of China (Grant No. 12471280 (247 and the Shanghai Municipal Education Commission (Grant No. 2024A101002), Liu's research was supported by the National Natural Science Foundation of China (Grant No. 12571283).
10

---

References
[1] Mare Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C Machado, Subhodeep Moitra, Sameera S Ponda, and Ziyu Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77-82, 2020.
[2] Mare Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforce- ment learning- In Proceedings of the 34th International Conference on Machine Learning, pages 449-458 PMLR, 2017.
[3] Mare G Bellemare, Will Dabney, and Mark Rowland. Distributional Reinforcement Leurning. MIT Press, 2023.
[4] Cristian Bodnar, Adrian Li, Karol Hausman, Peter Pastor, and Mrinal Kalakrishnan, Quantile qt-opt for risk-aware vision-based robotic grasping. arXiv preprint urXiv:/910.022 2019.
[5] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(167):1-11, 2018.
[6] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: a evar optimization approach. Advances in neural information processing systems, 28, 2015.
[7] Will Dabney, Mark Rowland, Mare G. Bellemare, and Rémi Munos. Distributional reinforce- ment learning with quantile regression. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), volume 32, 2018.
[8] Thomas G. Dietterich and Jesse Hostetler. Conformal prediction intervals for markov decision process trajectories. arXiv preprint arXiv:2206.0448 2022.
[9] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-leaming. In Proceedings of the 2nd Conference Learning for Dynamics and Control (I.DC), volume 120 of Proceedings of Machine Learning Research, pages 486-489. PMLR, 2020.
[10] Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mo- hammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grze- gorz Swirsze7, al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-53, 2022.
[11] Yingjie Fei, Zhuoran Yang, and Zhaoran Wang. Risk-sensitive reinforcement learning with function approximation: A debiasing approach. In International Conference on Machine Learning, pages 3198-3207. PMLR, 2021.
[12] Daniele Foffano, Alessio Russo, and Alexandre Proutiere. Conformal off-policy evaluation in markov decision processes. In Proceedings of the 62nd IEEE Conference Decision and Control (CDC), pages 3087-3094. IEEE, 2023.
[13] Jerome Friedman. On multivariate goodness-of-fit and two-sample testing. Technical report, SLAC National Accelerator Laboratory (SLAC), Menlo Park, CA (United States), 2004.
[14] Shangding Gu, Long Yang, Yali Du, Guang Chen, Florian Walter, Jun Wang, and Alois Knoll. review safe reinforcement learning: Methods, theories and applications. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 2024.
[15] Sungee Hong. Zhengling Qi, and Raymond KW Wong. Distributional off-policy evaluation with bellman residual minimization. arXiv preprint #xXiv:2422.01900 2024.
[16] Ronald A Howard and James E Matheson. Risk-sensitive markov decision processes. Man- agement science, 369, 1972.
[17] Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, 21677) 63, 2020.
11

---

[18] Thanh Lam, Arun Verma, Bryan Kian Hsiang Low, and Patrick Jaillet. aware reinforce- ment learning with coherent risk measures and non- non-linear function approximation. In The Eleventh International Conference on Learning Representations, 2022.
[19] Siqi Liu, Kay Choong See, Kee Yuan Ngiam, Leo Anthony Celi, Xingzhi Sun, and Mengling Feng. Reinforcement learning for clinical decision support in critical care: comprehensive review. Journal of medical Internet research, 22(7):e18477) 2020.
[20] Yaowu Liu and Jun Xie. Cauchy combination test: a powerful test with analytic p-value calcu- lation under arbitrary dependency structures. Journal of the American Statistical Association, 115(529):393-402 2020.
[21] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 2013.
[22] Mehrdad Moharrami, Yashaswini Murthy, Arghyadip Roy, and Rayadurgam Srikant. A policy gradient algorithm for the risk-sensitive exponential cost mdp. Mathematics of operations research, 50(1):331-455) 2025.
[23] Zhengling Qi. Chenjia Bai, Zhaoran Wang, and Lan Wang. Distributional off-policy evaluation in reinforcement learning. Journal of the American Statistical Association, (just-accepted):1- 24, 2025.
[24] Hongxiang Qiu, Edgar Dobriban, and Eric Tchetgen Tchetgen. Prediction sets adaptive to unknown covariate shift. Journal of the Royal Statistical Society Series B: Statistical Method- ology, 856)):1800-11055 2023.
[25] R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-riss Jour- nal of risk, 2:21 122114222220 2000.
[26] Yaniv Romano, Evan Patterson, and Emmanuel J. Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems, volume 32, pages 3543-3553, 2019.
[27] Mark Rowland, Rémi Munos, Mohammad Gheshlaghi Azar, Yunhao Tang, Georg Ostrovski, Anna Harutyunyan, Karl Tuyls, Mare G. Bellemare, and Will Dabney, An analysis of quantile demporal-differemee learning. Journal of Machine Learning Research, 25(163): 2024.
[28] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint 15X.v:151..0555. 2015.
[29] Shili Sheng, Pian Yu, David Parker, Marta Kwiatkowska, and Lu Feng. Safe pomdp online planning among dynamic agents via adaptive conformal prediction. JEEE Robotics and Au- tomation Letters, 2024.
[30] Chengehun Shi, Sheng Zhang, Wenbin Lu, and Rui Song. Statistical inference of the value function for reinforcement learning in infinite-horizon settings. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(3):765-793, 2022.
[31] Ryan J. Tibshirani, Rina F. Barber, Emmanuel J. Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. In Advances in Neural Information Processing Systems, vol- ume 32, pages 2530-2540, 2019.
[32] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithumic Learning in a Random World. Springer, New York, NY, 2005.
[33] Rui Xu, Chao Chen, Yue Sun, Parvathinathan Venkitasubramaniam, and Sihong Xie. Wasserstein-regullariedd conformal prediction under general distribution shift. arXiv preprint 1333:30501.13430, 2025.
[34] Derek Yang, Li Zhao, Zichuan Lin, Tao Qin, Jiang Bian, and Tie-Yan Liu. Fully parameterized quantile function for distributional reinforcement learning. In Advances Neural Information Processing Systems, volume 32, 2019.
12

---

[35] Yingying Zhang, Chengchun Shi, and Shikai Luo. Conformal off- off-policy prediction. In Inter- national Conference on Artificial Intelligence and Statistics, pages 2751-2768. PMLR, 2023.
[36] Frédéric Zheng and Alexandre Proutiere. Conformal predictions under markovian data, arXiv preprint 15277 2024.
[37] Hao Zhou, Yanze Zhang, and Wenhao Luo. Computationally and sample efficient safe inforcement learning using adaptive conformal prediction. arXiv preprint arXiv:2503. 17678 2025.
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: The abstract and introduction clearly state the contributions: we develop novel conformal prediction (CP) framework construct prediction intervals (PIs) for rein- forcement learning (RL) settings, addressing key challenges such as unobserved returns, temporal dependencies, and distribution shifts. We further establish asymptotic lower bounds on coverage based on Wasserstein metrics and demonstrate the effectiveness of our method through empirical studies on both synthetic data and the Mountain Car environ- ment.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: The conclusion section outlines the limitations of the proposed method and proposes potential directions for future investigation.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes].
Justification: All the theorems, formulas, and proofs in the paper should numbered and cross-referenced. All assumptions should be clearly stated or referenced in the statement any theorems. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes].
Justification: Section 4.1 specifies datasets, model sizes, hyper-parameters, and links (in Appendix) to an open GitHub repository, enabling faithful replication of the core experi- ments.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes].
Justification: Code is publicly released on GitHub, and all referenced datasets are publicly available, with citations provided for each.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes].
Justification: All the experimental settings are specified at the beginning and section 4, and details such as training and test sample sizes, DRL training details appear in implementa- tion details of Section 4, offering sufficient context.
7. Experiment statistical significance
14

---

Does the paper report eтrоr bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yes].
Justification: Results reported as boxplots and medians.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes].
Justification:
The paper provide the amount of compute required for each of the individual experimental
well as estimate the total compute.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::/ /ttpe////euupupeeeeeeeee http://weeerip..cppppiiiieeeeeee httpssp.ccccbppiittttttttttttti heppblit/thhiiecciieeeeeeeee cecuiidcineeee
Answer: [Yes].
Justification: The study uses only publicly available data, releases code responsibly, in- volves no human subjects, and follows standard ethical practice.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No].
Justification: The manuscript does not contain a Broader-Impact discussion of how the proposed method might be beneficial or misused.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [No]
Justification: Although the model is publicly released, the paper does not outline usage restrictions, filters, or other safeguards against malicious exploitation.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes].
Justification: Prior models and datasets are cited.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The work does not release a new dataset; the proposed policy evaluation framework is not provided separate asset.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA].
Justification: No crowdsourcing human-subject research is involved.
15

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The study does not involve human subjects and therefore requires no IRB review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs as any important, original, or non- standard components.
16


Reviews:
[{"review_id": "mO3oqfj0Nc", "reviewer": "Reviewer_g7gT", "summary": "This paper proposes a conformal prediction (CP) framework for constructing distribution-free prediction intervals (PIs) for infinite-horizon on-policy and off-policy evaluation in RL. To do so, the authors propose a i) pseudo-return construction using truncated rollouts and learned return distributions (inspired by k-steps TD learning); ii) experience replay (to decorrelate temporally linked transitions) and weighted subsampling (to correct distribution shifts) to restore approximate exchangeability. Moreover, the authors propose coverage guarantees that depend on the Wasserstein distance between true and estimated return distributions. Eventually, empirical evaluations are provided on synthetic and standard environments (Mountain Car, etc.).", "questions": "Could you compare against more methods, particularly from recent conformal off-policy evaluation literature and risk-aware RL ?\n\nApart from what you wrote line 228 about Zhang et al 2023, why not implementing Foffano et al. (2023? \n\nCan you further elaborate on adaptive or cross-validated strategies for k, or propose heuristics ?\n\nI am very likely to update my score according to other reviews and answers to all feedbacks.", "limitations": "The authors did not discuss broader impacts of the paper and their answer to that in the checklist (10. Broader impacts) is rather odd: “The manuscript does not contain a Broader-Impact discussion of how autonomous tool-using LLMs might be beneficial or misused.” Is that a copy paste from another NeurIPS submission?", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1) Strengths\n\nThe research problem is very relevant to the NeurIPS community. Uncertainty quantification in RL is important and few existing methods offer finite sample guarantees. The authors propose an integration of conformal prediction with distributional RL with a plug-and-play method of any return distribution estimator. \n\nThe coverage bounds are derived under approximate exchangeability using Wasserstein distances. These bounds bring nuanced insights of model and weight estimation errors. The difference in the bounds of Theorem 1 and 2 is well explained and the intuition on differences between on and off-policy is well explained. Moreover, the empirical results across on policy and off-policy scenarios show clear improvements in coverage over standard DRL-QR, which are quantile methods. \n\nThe paper is clearly written with very well articulated sections, well defined related work and problem setting. I did not check the novelty w.r.t related work however.\n\n2) Weaknesses\n\nEmpirical evaluation: A few things that to my mind represent weaknesses in the experiment section. The choice of the step size k in pseudo-returns is a little underexplored (experiments run with k=1...5 only). The authors mention aggregating different PIs over k in the conclusion but don’t offer a principled selection method or guidelines. Also, the only comparisons are to DRL-QR and KDE-QR. There is no comparison to recent methods in conformal RL like Foffano et al. (2023), Zhang et al. (2023). Moreover, the settings considered in the experiments are mostly low-dimensional.", "was_revised": true, "final_justification": "The rebuttal has addressed concerns I had and reading the concerns raised in other reviews, I have decided to keep my score, which still leans towards an acceptance.", "rebuttal": "# Author Response to Reviewer g7gT\nWe sincerely thank Reviewer g7gT for the recognition of our work and for providing constructive comments.\n\n## Q1: Add comparison with Foffano et al. (2023), Zhang et al. (2023) and risk-aware RL.\n\nWe appreciate the constructive feedback provided. Following the suggestion, we add a comparison with Foffano et al. (2023) in **Rebuttal Table A**, where our method demonstrates superior performance in terms of both coverage probability and average length.   \n\nWe would like to highlight that Foffano et al. (2023) focused on **finite-horizon** Markov Decision Processes (MDPs) and addressed the distributional shift problem \nusing estimates of  importance sampling weights. The importance sampling weight function (see Equation (12) of Foffano et al. (2023)) is \n$$\n w(x,y) = E_{\\tau\\sim P_{\\tau|X=x,Y=y}^{\\pi_b}} \\left[ \\frac{\\prod_{t=1}^H\\pi(a_t|x_t)}{\\prod_{t=1}^H\\pi^b(a_t|x_t)} \\right], \n$$\nwhere $H$ is the time horizon,  $\\tau =  (x_1, a_1, r_1, x_2, a_2, r_2, \\ldots, x_H, a_H, r_H) $ is a  trajectory of length $H$,  $x$ is the initial state, $y$ denotes the $H$-step cumulative return under the behavior policy $\\pi^b$, and $\\pi$ is the target policy. \nFoffano et al. (2023)  repeatedly emphasized the difficulty caused by the **curse of horizon**  in the concluding paragraphs of their Sections V-B.1, V-B.2, and VI-D.2. In contrast, our approach is specifically designed for the **infinite-horizon** setting, where we construct pseudo-returns based on truncated rollouts. This leads to a fundamentally different framework that avoids the compounding challenges associated with long-horizon importance weighting. \n\n   **Rebuttal Table A.** We compare the performance on Example 1 with a fixed horizon of 20. For Foffano’s method, we follow their gradient-based approach to train the likelihood ratio model $w(x, y)$ via linear regression, and apply WCP to construct prediction intervals. For our method, we replace the nonconformity score with the double-quantile score from Foffano et al.(2023), with $\\xi$ set to 0.5 and 0.6. Each experiment is repeated 100 times, and we report the mean and standard deviation of coverage probability (cov) and interval length (len) when the nominal coverage level is  90%.\n\n||||\n|-|-|-|\n||cov|len|\n|Foffano|0.85(0.01)|6.51(0.11)|\n|our proposal|||\n|k=2,$\\xi$=0.5|0.91(0.01)|7.67(0.15)|\n|k=3,$\\xi$=0.5|0.91(0.01)|7.77(0.13)|\n|k=2,$\\xi$=0.6|0.92(0.01)|8.00(0.16)|\n|k=3,$\\xi$=0.6|0.92(0.01)|8.02(0.15)|  \n\nAs for Zhang et al. (2023), their COPP algorithm is specifically designed for contextual bandits and can only be extended to **short-horizon** decision-making scenarios (e.g., $H=5$). In such short-horizon settings, employing truncated rollouts, as done in our method for infinite-horizon problems, is generally unnecessary. Moreover, the resampling-and-matching strategy proposed in COPP is limited to finite discrete action spaces, whereas our method is applicable to **both discrete and continuous** action spaces. Therefore, we consider the two methods to be fundamentally different in scope: COPP targets short-horizon, discrete-action problems, while our approach is designed for more general and challenging infinite-horizon settings. As such, a direct comparison is not applicable.\n\nFinally, we thank the reviewer for pointing us to the literature on **risk-aware RL**. We acknowledge that risk-aware RL constitutes an important line of work aiming to optimize risk-sensitive objectives, such as CVaR or variance-penalized returns (e.g., [1,2]). These methods focus on modeling risk preferences rather than constructing valid uncertainty quantification for prediction intervals. We will incorporate a discussion on this literature in the revised ``Related Work'' section.\n\n## Q2: Apart from line 228 about Zhang et al 2023, why not Foffano et al. (2023)?\n\nWe appreciate the reviewer's insightful question, which prompted deeper reflection on the relationship between our method and that of Foffano et al. (2023). According to our understanding, the method proposed by Foffano et al. (2023) consists of two key components: \n\n- A new construction of nonconformity scores, such as the double-quantile score;\n- The estimation of importance sampling weights, as described in our response to Q1.\n\nThese components are combined within the standard Weighted Conformal Prediction (WCP) framework. As such, implementing  Foffano et al. (2023)'s method in our setting on line 228 essentially amounts to implementing WCP. In response, we will add this point in line 228. While this is feasible, we discuss the limitations of WCP in lines 224--230 and provide a rationale for adopting the Weighted Subsampling approach instead, as detailed in lines 215--218.\n\nMoreover, we find their construction of nonconformity scores particularly insightful. Given that our framework permits flexible selection of nonconformity scores (Step 3), their double-quantile score can be seamlessly integrated. We have presented supporting simulations in **Rebuttal Table A**. In response, we will add this point in line 153. \n\n\n## Q3: Add exploration of $k$, adaptively choosing $k$, and aggregation of PIs across $k$\n\n### Q3-1: Add exploration of the step size $k$\n\nFollowing your suggestion,  we conducted additional  experiments with $k = 6, 7, 8$ in Example 1. The results presented in **Rebuttal Table B** demonstrate that larger $k$ values consistently lead to overcoverage and consequently wider prediction intervals of our method. This empirical finding is consistent with our theoretical analysis in Section 4 (Theorems 1 and 2), which establishes that the coverage probability incorporates an additional slack  or an error term $\\Lambda(\\widehat{w},\\widehat\\eta^{\\pi})$. The error component originates from two distinct sources:  \n(i) the estimation error of the weight function $\\widehat{w}$, and  \n(ii) the approximation error of the return distribution $\\widehat\\eta^{\\pi}$.\n\nThis creates a **trade-off**: a larger $k$ reduces the approximation error in estimating $\\widehat\\eta^{\\pi}$ but increases the difficulty of accurately estimating the off-policy weights, particularly under significant distributional shift. Based on our empirical findings, we recommend using $k = 2$ or $3$ to balance these competing factors. We will add the above discussion on the role of $k$ in the Theorem section.\n\n**Rebuttal Table B.** We conduct the experiments for Example 1 across $k=1,2,\\ldots,8$. Each experiment is repeated 100 times, and we report the mean and standard deviation of coverage probability (cov) and interval length (len) when the nominal coverage level is  90%. \n\n||||||||||\n|-|-|-|-|-|-|-|-|-|\n|**on policy**|||||||||\n|cov|k=1|k=2|k=3|k=4|k=5|k=6|k=7|k=8|\n|$\\xi$=0.8|0.87(0.01)|0.90(0.01)|0.91(0.01)|0.92(0.01)|0.92(0.01)|0.93(0.01)|0.94(0.01)|0.94(0.01)| \n|len|k=1|k=2|k=3| k=4|k=5|k=6|k=7|k=8||\n|$\\xi$=0.8|7.78(0.10)|8.24(0.10)|8.56(0.13)|8.78(0.14)|9.00(0.15)|9.15(0.19)|9.31(0.23)|9.50(0.22)|\n|**off policy**|||||||||\n|cov|k=1|k=2|k=3|k=4|k=5|k=6|k=7|k=8|\n|$\\xi$=0.8|0.87(0.01)|0.91(0.01)|0.92(0.01)|0.92(0.01)|0.93(0.01)|0.93(0.01)|0.93(0.01)|0.94(0.02)|     \n|len|k=1|k=2|k=3| k=4|k=5|k=6|k=7|k=8|\n|$\\xi$=0.8 |7.57(0.10)|8.13(0.11)|8.47(0.14)|8.67(0.14)|8.90(0.17)|9.02(0.18)|9.20(0.18)|9.26(0.20)|\n\n### Q3-2: Adaptive or cross-validated strategies for choosing $k$\n\nWe appreciate the reviewer’s suggestion on exploring adaptive or cross-validated strategies for selecting $k$. While these approaches are conceptually straightforward in on-policy settings where target policy validation data are readily available, they present significant challenges in off-policy settings due to the absence of independent validation data sampled from the target policy. This limitation makes performance-based tuning of $k$ difficult under distribution shift.\n\n### Q3-3: Aggregating PIs across $k$\n\nWe also thank the reviewer for raising the interesting question of aggregating prediction intervals across different $k$ values. Since these intervals are correlated, aggregation is nontrivial. A promising direction is to construct a unified prediction region by combining the corresponding p-values, leveraging the connection between prediction intervals and hypothesis testing. Methods such as the **Cauchy Combination Test** (e.g., [4,5,6]), which are robust to arbitrary dependencies, offer a viable approach. We will include this discussion in the Conclusion section.\n\n## Q4: The settings considered in the experiments are mostly low-dimensional.\n\nOur experiments primarily focus on low-dimensional settings to clearly demonstrate the method’s performance. Due to time constraints during the rebuttal period, we will incorporate high-dimensional experiments in the revised version.\n\n# References\n\n[1] Risk-sensitive and robust decision-making: a cvar optimization approach.\n\n[2] Risk-constrained reinforcement learning with percentile risk criteria. \n\n[3] Conformal off-policy evaluation in markov decision processes. \n\n[4] ACAT: a fast and powerful p value combination method for rare-variant analysis in sequencing studies. \n\n[5] Cauchy combination test: a powerful test with analytic p-value calculation under arbitrary dependency structures. \n\n[6] Multi‐split conformal prediction via Cauchy aggregation. \n\n[7] Conformal off-policy prediction."}, {"review_id": "nKMkOkjO0K", "reviewer": "Reviewer_dgcF", "summary": "This article considers conformal prediction for policy evaluation in the discounted infinite horizon RL setting. They introduce a new algorithm implementing several trick to address the challenges, namely Pseudo-return construction with Distributional RL to address the unobservable exact returns, Experience replay for the temporal dependence, and Time-Aware Weighted Subsampling for the distribution shift induced. They provide an asymptotic lower bound on coverage as a theoretical guarantee and experiments for empirical validation.", "questions": "- Can you detail briefly how this article improves on the current literature ? Mainly:\n  - (1) What are the differences in modeling assumption ?\n  - (2) How does the scalability compares ?\n\n- Algorithms such as QTD are proven to converge (see [1]), with theoretical guarantees on the limit and the true distribution. Isn’t it enough to get asymptotic prediction intervals ? If it isn’t, could you give a brief explanation on why ? If it is, are they are any other reasons to not use it, other than empirical performances ?\n\n[1] Rowland, Mark, et al. \"An analysis of quantile temporal-difference learning.\" Journal of Machine Learning Research 25.163 (2024): 1-47.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths :\n- Combines ideas stemming from different theories to address all the challenges posed by the problem they consider.\n- The paper is well written, well referenced and all the different ideas are well introduced in the first sections.\n- The experiments are reproducible with the code provided.\n\nWeaknesses :\n- It is not entirely clear how this paper positions itself in the literature of Conformal Prediction for RL. The paragraph \"Conformal Prediction\" in section 1.1 Related Work mentions some other papers but do not explain with them. The sentence \"existing methods are limited by scalability issues, strong modeling assumptions, or the curse of the horizon\" could be worth given more details.\n- In several parts of the paper, such as in Section 1 Introduction line 37, there is a mention of finite-sampling coverage guarantees. Yet to the best of my understanding, this paper only provide asymptotic bounds, as mentioned in the \"Contribution\" paragraph.\n- Minor remarks: \n\t- In the code provided in the Supplementary Material, some headers are written in Chinese. English would be appreciated for better anonymity and understanding of the code.\n\t- In the Algorithms, the sets $\\mathcal I$ are not explicitly defined.\n\t- I don’t understand what the paragraph \"Off-Policy Setting\" in section 3.2 is trying to explain, behind the fact that return distribution can be estimated directly by algorithms such as QTD.", "was_revised": true, "final_justification": "The ideas are original and the contribution is overall significant. Furthermore, the authors addressed all the concerns of the reviewers with their rebuttals.", "rebuttal": "# Author response to reviewer dgcF\n\nWe sincerely thank Reviewer dgcF for the recognition of our work and for providing constructive comments.\n\n## Q1: Can you detail briefly how this article improves on the current literature ?\n\nWe thank the reviewer for raising this important question regarding the positioning and contribution of our method within the conformal prediction literature for RL. We agree that this is an important point and have revised the Introduction section accordingly.\n\n- **Positioning in Conformal RL Literature.** Our work is the first to tackle **infinite-horizon** off-policy prediction in general reinforcement learning settings for **any state and action spaces** using conformal prediction. Most existing conformal RL methods concentrate on **finite-horizon** scenarios or **finite state or action spaces**, as noted in [1] and [5]. Our approach extends conformal prediction to the infinite-horizon setting while preserving asymptotic coverage guarantees, making it both methodologically novel and technically challenging.\n\n- **Differences in Modeling Assumptions.** As mentioned above, the primary distinction lies in the infinite-horizon framework and the consideration of more general state and action spaces. Furthermore, while most existing methods require access to complete trajectories, our approach remains effective even when only partial trajectory fragments are available, provided that a $k$-step pseudo return can be constructed.\n\n- **Scalability.**   Prior conformal RL methods typically address distribution shifts between behavior and target policies through trajectory-level importance weighting, which exhibits computational inefficiency scaling for  trajectories with increasing horizon. In contrast, our approach utilizes $k$-step pseudo returns and address distribution shift only through a $k$-step importance weighting, therefore it can be implemented efficiently in infinite-horizon settings and continuous tasks, as demonstrated by our experiments on the MountainCar environment. \n\nWe will add a more detailed discussion of these points in the revised paper.\n\n## Q2: Since algorithms like QTD are proven to converge with guarantees on the limiting distribution, isn't that sufficient?\n\nWe appreciate this valuable comment. Our response is structured in three parts:\n\n1. **Limiting distribution.** While QTD is proven to converge to some limiting distribution, this limiting distribution is not guaranteed to be the true return distribution. Please see the last paragraph in Section 4 of [4]. Consequently, this convergence does not provide any guarantee on the asymptotically validity of QTD-based prediction intervals.\n\n2. **Tabular settings.**  [4] proved the convergence of QTD only in the contex of   finite state and action spaces. To the best of our knowledge, no existing distributional RL algorithm has been proven to consistently recover the true return distribution in general settings with continuous state and action spaces.\n\n3. **Function approximation.** In continuous state and action spaces, distributional RL methods necessarily employ function approximation for return distribution estimation. The theoretical validity of such approaches is inherently contingent upon the accuracy of the modeling assumptions, rendering them susceptible to potential model misspecification. Conformal prediction helps address this by providing model-agnostic prediction intervals, thereby improving the robustness and reliability of uncertainty quantification in practice. \n\nWe will incorporate the above discussions in the ''Limitations of DRL\" paragraph.\n\n## Q3: Clarification on Finite-Sample and Asymptotic Coverage Guarantees\n\nThank you for pointing this out. We apologize for the confusion. You are absolutely right that our current theoretical results establish asymptotic coverage guarantees. We will revise the wording in lines 37 and 75 in  the Introduction section, and in line 323 in the  Conclusion section to clarify this point.\n\n## Q4: Minor Remarks\n\nThank you very much for your careful reading. We will incorporate the following changes in the revised paper:\n\n- We will rewrite the code headers in English to ensure better anonymity and clarity.\n\n- In Algorithm 1, $\\mathcal{I}$ refers to the index of the transition $(S_{i,t}, A_{i,t}, R_{i,t}, S_{i,t+1})$ in the training dataset. We will explicitly add this definition in our paper for clarity.\n\n- The QTD algorithm presented in Algorithm 1 of [4] is designed for the **on-policy** setting. Extending QTD to the **off-policy** setting requires careful modifications to account for the distribution shifts between the behavior policy used to collect data and the target policy.\n\n  Specifically, in the on-policy case, QTD estimates the return distribution conditioned on the initial state, $\\widehat{\\eta}^{\\pi}(s)$, using the following iterative update:\n  $$\n  \\theta(s,i) \\leftarrow \\theta(s,i)+\\alpha\\frac{1}{m}\\sum_{j=1}^{m}\\left[\\tau_i - I(r+\\gamma\\theta(s^\\prime,j)-\\theta(s,i)<0) \\right],\n  $$\n  where $\\theta(s, i)$ denotes the $i$-th quantile of $\\widehat{\\eta}^{\\pi}(s)$ and $(s, a, r, s')$ is sampled under the behavior policy $\\pi$, which in the on-policy case coincides with the target policy.\n\n  In contrast, the off-policy setting requires estimating the return distribution conditional on both the state and the action, $\\widehat{\\eta}^{\\pi}(s, a)$, using the modified update:\n  $$\n  \\theta(s,a,i) \\leftarrow \\theta(s,a,i)+\\alpha\\frac{1}{m}\\sum_{j=1}^{m}\\left[\\tau_i - I(r+\\gamma\\theta(s^\\prime,a^\\prime,j)-\\theta(s,a,i)<0) \\right],\n  $$\n  where $\\theta(s, a, i)$ is the $i$-th quantile of $\\widehat{\\eta}^{\\pi}(s, a)$, and $(s, a, r, s')$ is sampled from the behavior policy $\\pi_b$. Crucially, $a'$ is drawn from the target policy $\\pi$, and the result is marginalized over the action space according to $\\pi$. This added complexity arises from the need to correct for the action distribution mismatch between the behavior and target policies.\n\n  This distinction is analogous to the difference \n  between **the TD algorithm** for estimating the state-value function $V^{\\pi}(s)$ and **the SARSA algorithm** for estimating the state-action value function $Q^{\\pi}(s,a)$. We will clarify this point in the revised paper and refer readers to relevant literature, including [2] and [3] for more details on distributional off-policy evaluation.\n\n# Reference\n\n[1] Conformal off-policy evaluation in markov decision processes. \n\n[2] Distributional Off-policy Evaluation with Bellman Residual Minimization.\n\n[3] Distributional Off-Policy Evaluation in Reinforcement Learning.\n\n[4] An analysis of quantile temporal-difference learning.\n\n[5] Conformal off-policy prediction."}, {"review_id": "mMGQFmnLEW", "reviewer": "Reviewer_SpYL", "summary": "The paper  proposes a split-conformal‐prediction for infinite-horizon reinforcement-learning (RL) returns. The authors propose a method based on distributional RL to compute pseudo-returns, which are then used to build the conformal scores. For their method, they derive an asymptotic guarantee on coverage.\n    Experiments on a two-state toy MDP, a continuous 2-D benchmark and Mountain-Car show that the method hits the nominal 90 % coverage while a plain DRL quantile interval under-covers.", "questions": "- Why use the term \"Prediction interval\" instead of \"Confidence interval\"? Furthermore, when writing PI it looks like Policy Improvement.\n- Eq. 2: what if $k$ exceeds the trajectory length?\n- Possible misunderstanding: why it seems like that a small value of $k$ seems to improve the coverage? the second term in the square root will be larger (thm 1)\n- Clarify $N$ and $n$ in the manuscript.\n- Unclear what is ${\\cal I}$ in the algorithm\n\nPossible typos:\n- Line 16: \"As reinforcement learning (RL) are \" -> \"As reinforcement learning (RL) _algorithms_ are\"?\n- Line 93: \"uniform length\" -> \"_constant_ length\"\n- Figure 1, under conformal prediction, (1) is repeated twice", "limitations": "Limitations and impact do not seem to be discussed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strenghts**\n- Using an approach based on computing the pseudo-returns make more intuitive sense than prior approaches, as well as using a replay buffer for breaking dependency.\n- Experiments seem to demonstrate the validity of the approach\n- The authors provide an asymptotic coverage analysis for their method\n\n\n**Weaknessess**\n\n- Problematic claims:\n  - The authors in the introduction claim that \"Unobserved Returns\" is a challenge, since full return is not directly observable in the infinite-horizon setting. However, that depends also on the characteristics of the underlying MDP. In some MDPs (e.g., finite and communicating), if one can estimate well the stationary distribution, then it is not necessary to observe the \"entire\" return.\n  - It's not clear why the authors state that \"Model Misspecification\" is a challenge for conformal prediction, since it should be a model-free approach. The overall statement is a bit questionable.\n  - Confusion with DRL in line 125. When the authors write \"DRL-based quantile intervals, referred to as DRL-QR,\", in reality this type of construction is not only limited to DRL, but it's more general than that. It is quite common to use empirical CDFs to build confidence intervals using the lower/upper quantiles (e.g., using bootstrap).\n  - About not using WCP the authors write \"in the RL setting, intermediate transitions along the test trajectory are not available at prediction time, making direct application of WCP infeasible\". But one could use a learned model of the transition, or use an approach base don eq.14 of Foffano et al. 2023\n  - Line 235: not clear why the authors write \" Previous studies have bounded this gap using total variation distance, which235\nfails to capture how different choices of k in k-step rollouts affect the coverage gap. \". Isn't their work the first to use k-step rollouts? Why TV  fails?\n\n- Missing assumptions, notation and possibly not correct equations\n  - The MDP model is missing. The authors write \"we use the standard RL framework\", but what is this standard framework? What are the assumptions on the MDP? Furthemore, also the assumptions on how the trajectories are collected are missing.\n  - The authors define $\\mathcal{P}$ to be the transition function. What is then ${\\rm d}{\\cal P}_0(s)$ in eq 4? Similarly, what do they mean by $P$ in eq 4? They write \" is the distribution of test state\", but a precise definition is missing. Overall, the equation does not seem to be correct.\n  - Off policy setting, lines 171-178: this paragraph just does not seem correct. The goal is to estimate the return distribution from data collected from a different policy, but the section does not seem to explain that (not even uses importance sampling), and I am confused about the intent of the authors here overall.\n  - Theorem 1/2: I don't think this theorem is correct, due to the dubious definition of ${\\rm d}{\\cal P}_0(s)$  (similarly for the calibration) in eq 4. This should depend on the stationary distributions (and we need assumptions on the MDP). Furthermore, what is the limit in $n$ (you mean $N$?) and under which assumptions on the MDP/data/policies we have that the Lebesgue density is bounded by $L$? Also, the boundedness on the importance sampling terms puts assumptions on the data collected, this should be stated more clearly. Also, the statement only holds asymptotically (as the number of trajectories tends to infinity), which affects the strength of the result.\n  - From the proofs is also not clear how the replay buffer should make the samples exchangeable. \n- Experiments are limited to simple examples, and only compare to DRL, but not to other techniques (e.g., Foffano et al 2023). \n- I believe the main challenge in conformal prediction for MDPs is to adequately address the off-policy setting, but as of now,  I believe the paper lacks sufficient clarity/precision to address this point.\n\n- Missing reference on conformal prediction with Markovian data:  Zheng, Frédéric, and Alexandre Proutiere. \"Conformal Predictions under Markovian Data.\" Forty-first International Conference on Machine Learning.", "was_revised": true, "final_justification": "The authors’ responses substantively address my main concerns about correctness and positioning, thus I increase my score from 3 to 4.\n\nThe authors have  substantively address my main concerns about correctness and positioning.  They also added a comparison to Foffano et al. (2023),  and discussed the $k$-step trade-off and why WCP can be unstable in long-horizon settings. These clarifications,tip the balance for me toward acceptance, albeit narrowly. Remaining issues regarding presentation of the concepts are camera-ready items rather than fatal flaws.\n\n\nResidual weaknesses:\n-   Guarantees remain asymptotic; the role of replay/weighted subsampling in restoring exchangeability should be stated crisply in the main text, with assumptions up front. \n- Evaluation is still mostly low-dimensional; at least two higher-dimensional or continuous-control benchmark would improve external validity. Off-policy experiments should be given the priority given the high practical relevance.\n\nProvided the authors address all the concerns that were initially raised in my review, I suggest a borderline accept score.", "rebuttal": "# Author response to reviewer SpYL\n\nWe thank Reviewer SpYL for your careful reading and valuable comments.\n\n## Q1: Problematic claims\n- Q1-1:  We agree that in certain classes of MDPs the stationary distribution $\\mu^\\pi(s,a)$ can be well estimated. However, our method depends critically on a more challenging quantity: the long-term return distribution\n   $$\\eta^{\\pi}(s) = \\mathrm{Law} \\left( \\sum_{t=0}^{\\infty} \\gamma^t r_t \\middle| s_0 = s \\right).$$\n   Estimating this distribution (e.g., quantiles) requires knowledge **not only** of $\\mu^{\\pi}$ but also of the conditional distribution of cumulative future rewards. For a detailed background, please see DRL literature such as [1].\n   \n   In infinite-horizon settings, the return is inherently unobservable from finite trajectories, especially under off-policy data, which motivates our work.\n\n   While long-horizon trajectories enable Monte Carlo estimation, it is more common to exploit time-homogeneity of MDP to use all immediate transitions, as in temporal difference (TD) methods, which is our focus in this work.\n- Q1-2: The term “model misspecification” refers to the difficulty of constructing valid PIs using estimated return distributions. For example, quantiles estimated by DRL models may be inaccurate, leading to poor coverage. \n\n   While we agree that CP is model-free with guaranteed marginal coverage, applying CP to infinite-horizon and continuous RL remains challenging. Our work addresses this gap, and we will clarify this point in the paper.\n- Q1-3: While quantile-based intervals via empirical CDFs are standard, in infinite-horizon RL, full return trajectories are rarely observed. Thus, direct estimation is often infeasible. Though long-horizon Monte Carlo rollouts can approximate return distributions, they are often sample-inefficient, especially in off-policy or high-variance settings. Instead, like much of RL, our work adopts the TD-based approach, where return quantiles are learned from immediate transitions. “DRL-QR” refers to intervals built from these TD-based quantile estimates.\n- Q1-4: WCP typically assumes access to full test-time covariates, while our setting only observes the initial state $S_{\\text{test},0}$ at test time. Estimating the WCP weight from Foffano et al. (2023, Eq.12) requires **marginalizing over full trajectories**, which are unobserved and intractable to approximate without strong assumptions.\n\n  We may estimate the WCP weight by solving the objective function in their Eq.14, this requires additional modeling assumptions and may suffer from high variance, particularly in long-horizon settings. The resulting weights can be unstable and sensitive to model choice, limiting practical use in our setting.\n\n  Finally, simulating trajectories with learned **transition model** $p(s' \\mid s,a)$ introduces approximation error and places the burden of accuracy on the model class. **More critically**, it doesn’t address a key requirement of conformal prediction: distributional alignment between calibration and test data.\n- Q1-5: We initially considered a TV-based coverage bound following [5], but it fails to capture how rollout length $k$ affects distributional mismatch. Inspired by [10] which shows Wasserstein distance better reflects conformal coverage under distribution shift (see their Section B for a detailed comparison), we adopt a Wasserstein-based bound to characterize the effect of $k$.\n## Q2: Missing assumptions and so on\n- Q2-1: We assume a standard time-homogeneous Markov Decision Process with data collected from i.i.d. trajectories under a fixed behavior policy. We originally stated these assumptions in the Supplement and  will move them to the main paper.\n- Q2-2: In our notation, $\\mathcal{P}$ denotes a probability distribution. For example, $\\mathcal{P}_0$ represents the distribution of the initial state. Since we only observe the initial state of the test trajectory, we refer to this as the distribution of the test state. We use $P$ to denote the probability measure induced by a distribution. \n- Q2-3: Lines 171–178 explain how the QTD algorithm from [7], originally developed for the on-policy case, is adapted to the off-policy setting in our work. The key change is that we estimate the return distribution $\\widehat{\\eta}^\\pi(s,a)$ instead of $\\widehat{\\eta}^\\pi(s)$, and account for the mismatch between the behavior policy $\\pi_b$ and the target policy $\\pi$ by sampling $a'$ from $\\pi$ and marginalizing accordingly. This is conceptually similar to moving from TD (estimating $V^\\pi(s)$) to SARSA (estimating $Q^\\pi(s,a)$). For full update rules, please see our response to  Q2 of Reviewer #4. We will  clarify this point and cite [4,8] for related work on off-policy distributional evaluation.\n- Q2-4: Our responses are organized point-by-point below.\n\n   1. **$\\mathcal{P}_0$ and assumptions.** Please refer to Q2-1 and Q2-2.\n\n   2. **On $n$.** Please refer to Q4-4.\n\n   3. **Boundedness of density.** The assumption that the Lebesgue density is bounded holds for any continuous random variable that has a continuous density function that does not tend to infinity at the boundary of its support. Examples include Gaussian distribution, exponential distribution, etc. It can be verified that both   **Example 1** and  **Example 2** satisfy this assumption. Please refer to our response to Q5 of Reviewer #4 for details.\n\n   4. **Assumptions of IS.** We interpret the comment as referring to the weighting function $w$. Our analysis only requires a bounded **first moment** of $w$, which is a common and mild assumption in the CP literature, including [5,11].\n   5. **Asymptotic coverage.** The theorem ensures asymptotic coverage as the number of calibration samples $n$ tends to infinity, **not the number of trajectories**. Please refer to Q4-4.\n- Q2-5: To address the issue of temporal dependence among transitions, we follow a common technique in the RL literature known as experience replay ([6,7]). Specifically, we apply weighted subsampling from a large replay buffer to construct a subset of transitions that are approximately i.i.d. This approach is widely used in RL to break temporal correlations and is supported both empirically and theoretically in prior work such as [2].\n## Q3: Weekness 3-5\n- Q3-1: **Weekness 3.** Following your suggestion, we add a comparison with Foffano et al. (2023) in **Rebuttal Table A**, where our method demonstrates superior performance across coverage probability and average length.\n\n   We highlight that Foffano et al.(2023) address **finite-horizon** MDPs and mitigate distributional shift via importance weighting (see their Eq.12), but their method is subject to the curse of horizon. In contrast, our approach targets the infinite-horizon setting and reduces the challenge to a $k$-step distributional shift problem. Please refer to our response to Q1 of Reviewer #1 for further discussion.\n\n  **Rebuttal Table A.** We compare the performance on Example 1 with a fixed horizon of 20. For Foffano’s method, we use their gradient-based linear regression to train $w(x, y)$ and apply WCP. Each experiment is repeated 100 times, and we report the mean and standard deviation of coverage probability (cov) and interval length (len) at the nominal coverage rate 90%.\n||||\n|-|-|-|\n||cov|len|\n|Foffano|0.85(0.01)|6.51(0.11)|\n|our proposal|||\n|k=2,$\\xi$=0.5|0.91(0.01)|7.67(0.15)|\n|k=3,$\\xi$=0.5|0.91(0.01)|7.77(0.13)|\n|k=2,$\\xi$=0.6|0.92(0.01)|8.00(0.16)|\n|k=3,$\\xi$=0.6|0.92(0.01)|8.02(0.15)|  \n\n- Q3-2: **Weekness 4.**  We agree that off-policy evaluation poses major challenges for applying CP to MDPs. Addressing this is a central contribution of our work. To mitigate severe distributional shift in the infinite-horizon setting, we estimate the return distribution using DRL and apply CP to correct model misspecification. We also propose $k$-step pseudo returns to reduce the infinite-horizon shift to a more tractable $k$-step shift.\n- Q3-3: **Weekness 5.** Thanks for pointing out this interesting paper. We will cite it.\n## Q4: Questions 1-5\n- Q4-1:  A confidence interval is an interval estimate for a parameter (fixed), whereas a prediction interval is an interval estimate for a random variable (random)  with a large probability. Given an initial state of a trajectory, the return is unobserved and can be seen as a random variable. \nThis is why we use “Prediction interval” instead of “Confidence interval”. \n“PI” is defined at Line 23 and follows standard terminology in CP.\n- Q4-2: The event that $k$ exceeds the trajectory length will never happen as we are focusing on the  infinite-horizon settings.\n- Q4-3: We apologize for the typo in $\\Lambda$ in Theorems 1/2. It should be the sum of two estimation errors and we will correct it.\n- Q4-4: As defined in Section 2,  $N$ is the number of trajectories and $T$ the horizon. In line 242, $n$ denotes the number of calibration samples, not trajectories. Since we extract overlapping $k$-step transitions, $n \\approx NT/2$ in split CP.\n- Q4-5: In Algorithm 1, $\\mathcal{I}$ refers to the index of the transition $(S_{i,t}, A_{i,t}, R_{i,t}, S_{i,t+1})$ in the training dataset. We will add this definition.\n## Q5: Possible typos\n\nWe will correct these typos in our paper.\n\n[1] A distributional perspective on reinforcement learning. \n\n[2] A theoretical analysis of deep Q-learning. \n\n[3] Conformal off-policy evaluation in markov decision processes. \n\n[4] Distributional Off-policy Evaluation with Bellman Residual Minimization. \n\n[5] Conformal inference of counterfactuals and individual treatment effects. \n\n[6] Self-improving reactive agents based on reinforcement learning, planning and teaching. \n\n[7] Human-level control through deep reinforcement learning. \n\n[8] Distributional Off-Policy Evaluation in Reinforcement Learning. \n\n[9] An analysis of quantile temporal-difference learning. \n\n[10] Wasserstein-regularized conformal prediction under general distribution shift. \n\n[11] Conformal off-policy prediction."}, {"review_id": "m98aUBwYY0", "reviewer": "Reviewer_jGpc", "summary": "This paper leverages conformal prediction to derive distribution-free predictive intervals (PI) for the return $G^\\pi(s_{test})$ in discounted MDPs for a fixed policy $\\pi$ and a test state $s_{test}$, applicable to both on-policy and off-policy settings. The method is particularly suited for neural network-based predictions due to its distribution-free nature. Specifically, the authors split the data into training and calibration sets: the QTD algorithm is trained on the training set to estimate the value function and generate approximate samples of $G^\\pi(s)$, while k-step TD estimates ($G^\\pi(s_k)$ is sampled from the QTD model) of $G^\\pi(s_{cal})$ on the calibration set are used to compute nonconformity scores (defined as the difference between the k-step TD estimates and the value function estimates). To enhance performance, the authors incorporate weighted subsampling and resampling techniques.\nUnder the assumption that $G^\\pi(s)$ admits a bounded Lebesgue density, the authors establish coverage guarantees for the derived PI. Numerical experiments demonstrate that, compared to PI obtained directly via distributional RL (DRL), the proposed method achieves the desired coverage probability without significantly inflating interval widths.", "questions": "The coverage guarantees rely on the return distribution having a bounded Lebesgue density. How does the method perform empirically when this assumption is violated which is often the case? A brief discussion or experiment would strengthen the practical relevance.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThis work elegantly integrates conformal prediction with distributional RL and replay buffer techniques to derive a theoretically guaranteed predictive interval for $G^\\pi(s_{test})$. The empirical results convincingly validate the method’s effectiveness, making this a compelling contribution.\n\nWeaknesses:\n\nI do not find major flaws, I offer the following refinements to enhance clarity and rigor.\n\n1. Notational Clarity: The symbol m is overloaded for both QTD and resampling parameters.\n\n2. Clarify Methodology for Off-Policy Evaluation (Line 171-178): The current description of estimating $\\eta^\\pi(s,a)$ in the off-policy setting is vague. Explicitly state the distributional off-policy evaluation method used in the paper (e.g., distributional variant of Fitted Q Evaluation) or cite relevant work.\n\n3. Clarify Methodology used in Eqn. (4): Please explain how to estimate P(\\delta | s) (e.g. logistic regression?) and explicitly note that \n P(δ=0)/P(δ=1) can be estimated via frequency ratios (if this aligns with the authors’ intent).\n\n4. In Algorithm 1, on Result line, conformal predictive region can be replaced with conformal predictive interval (because it is indeed an interval). And the impact of the multiple subsampling parameter $\\xi$ is not discussed in the paper (although it is discussed in the Appendix).", "was_revised": true, "final_justification": "The authors have addressed my concerns. I will keep my positive score unchanged.", "rebuttal": "# Author response to reviewer jGpc\n\nWe sincerely thank Reviewer jGpc for the recognition of our work and for providing constructive comments.\n\n## Q1: Notational Clarity.\n\nThank you for your careful reading and thoughtful comments. To avoid confusion, we have revised the notation in Algorithm 1: the subsample size, previously denoted by $m$ in the submitted version, is now written as $l$ in the revised manuscript.\n\n## Q2: Clarify Methodology for Off-Policy Evaluation (Line 171-178).\n\nThank you for your valuable comments. Lines 171–178 aim to explain how the QTD algorithm of [3] can be adapted to the off-policy setting.\nThe QTD algorithm presented in Algorithm 1 of [3] is designed for the **on-policy** setting. Extending QTD to the **off-policy** setting requires careful modifications to account for the distribution shifts between the behavior policy used to collect data and the target policy.\n\n- In the on-policy case, QTD estimates \n  the return distribution conditioned on the initial state, $\\widehat{\\eta}^{\\pi}(s)$, using the following iterative update:\n  $$\n  \\theta(s,i) \\leftarrow \\theta(s,i)+\\alpha\\frac{1}{m}\\sum_{j=1}^{m}\\left[\\tau_i - I(r+\\gamma\\theta(s^\\prime,j)-\\theta(s,i)<0) \\right],\n  $$\n  where $\\theta(s, i)$ denotes the $i$-th quantile of $\\widehat{\\eta}^{\\pi}(s)$ and $(s, a, r, s')$ is sampled under the behavior policy $\\pi$, which in the on-policy case coincides with the target policy.\n\n- In contrast, the off-policy setting requires \n  estimating the return distribution conditional on both the state and the action, $\\widehat{\\eta}^{\\pi}(s, a)$, using the modified update:\n  $$\n  \\theta(s,a,i) \\leftarrow \\theta(s,a,i)+\\alpha\\frac{1}{m}\\sum_{j=1}^{m}\\left[\\tau_i - I(r+\\gamma\\theta(s^\\prime,a^\\prime,j)-\\theta(s,a,i)<0) \\right],\n  $$\n  where $\\theta(s, a, i)$ is the $i$-th quantile of $\\widehat{\\eta}^{\\pi}(s, a)$, and $(s, a, r, s')$ is sampled from the behavior policy $\\pi_b$. Crucially, $a'$ is drawn from the target policy $\\pi$, and the result is marginalized over the action space according to $\\pi$. This added complexity arises from the need to correct for the action distribution mismatch between the behavior and target policies.\n\n- This distinction is analogous to the difference \n  between **the TD algorithm** for estimating the state-value function $V^{\\pi}(s)$ and **the SARSA algorithm** for estimating the state-action value function $Q^{\\pi}(s,a)$. We will clarify this point in the revised paper and refer readers to relevant literature, including [1] and [2] for more details on distributional off-policy evaluation.\n\n## Q3: Clarify Methodology used in Eqn. (4).\n\nThank you very much for the insightful comments. We estimate $P(\\delta \\mid s)$ using logistic regression in our implementation, although other models such as neural networks can also be employed. As for the ratio $P(\\delta = 0)/P(\\delta = 1)$, it is a constant and does not need to be explicitly estimated, since we normalize the resulting weights into probabilities in the subsequent weighted subsampling procedure. We will clarify this point in the revised paper.\n\n## Q4: In Algorithm 1, conformal predictive region can be replaced with interval. And the impact of $\\xi$ is not discussed in the paper (although it is discussed in the Appendix).\n\nThank you for your thoughtful comment. We will replace the conformal prediction region in result line of Algorithm 1 by conformal prediction interval. In addition, following your suggestion, we conducted experiments with $\\xi=0,1,0.2,\\ldots,0.9$ in Example 1, as shown in **Rebuttal Table C**. The results indicate that smaller $\\xi$ and larger $k$ tend to produce over-coverage, while overall, settings with $\\xi\\ge0.5$ and $k=2,3$ yield satisfactory performance. We will incorporate these findings into the paper.\n\n**Rebuttal Table C.**  We conduct the experiments for Example 1 across $xi$ for $k=2,3,4$. Each experiment is repeated 100 times, and we report the mean and standard deviation of coverage probability (cov) and interval length (len) at the nominal coverage rate 90%. \n\n|||||||||\n|-|-|-|-|-|-|-|-|\n|**on policy**|||||||\n|cov|k=2|k=3|k=4|len|k=2|k=3|k=4| \n|$\\xi$=0.1|0.95(0.01)|0.96(0.01)|0.96(0.01)| |10.21(0.20)|10.71(0.21)|11.04(0.26)| \n|$\\xi$=0.2|0.95(0.01)|0.95(0.01)|0.95(0.01)| |9.68(0.15)|10.10(0.16)|10.40(0.17)| \n|$\\xi$=0.3|0.94(0.01)|0.95(0.01)|0.95(0.01)| |9.30(0.12)|9.67(0.14)|9.95(0.16)|\n|$\\xi$=0.4|0.92(0.01)|0.94(0.01)|0.95(0.01)| |8.98(0.10)|9.34(0.13)|9.62(0.15)|\n|$\\xi$=0.5|0.92(0.01)|0.93(0.01)|0.94(0.01)| |8.73(0.08)|9.07(0.13)|9.33(0.15)|\n|$\\xi$=0.6|0.91(0.01)|0.92(0.01)|0.93(0.01)| |8.53(0.09)|8.87(0.13)|9.09(0.16)|\n|$\\xi$=0.7|0.91(0.01)|0.92(0.01)|0.92(0.01)| |8.37(0.09)|8.69(0.12)|8.92(0.14)|\n|$\\xi$=0.8|0.90(0.01)|0.91(0.01)|0.92(0.01)| |8.24(0.10)|8.56(0.13)|8.78(0.14)|    \n|$\\xi$=0.9|0.90(0.01)|0.91(0.01)|0.92(0.01)| |8.20(0.12)|8.51(0.14)|8.72(0.16)|\n|**off policy**|||||||\n|cov|k=2|k=3|k=4|len|k=2|k=3|k=4| \n|$\\xi$=0.1|0.96(0.01)|0.96(0.01)|0.97(0.01)| | 10.17(0.19)|10.68(0.22)|10.95(0.30)| \n|$\\xi$=0.2|0.95(0.01)|0.95(0.01)|0.96(0.01)| |9.62(0.15)|10.08(0.17)|10.33(0.20)| \n|$\\xi$=0.3|0.94(0.01)|0.95(0.01)|0.96(0.01)| |9.24(0.12)|9.64(0.15)|9.90(0.17)|\n|$\\xi$=0.4|0.93(0.01)|0.94(0.01)|0.95(0.02)| |8.93(0.10)|9.30(0.13)|9.57(0.15)|\n|$\\xi$=0.5|0.92(0.01)|0.93(0.01)|0.94(0.01)| |8.68(0.11)|9.03(0.14)|9.28(0.15)|\n|$\\xi$=0.6|0.92(0.01)|0.93(0.01)|0.93(0.01)| |8.43(0.11)|8.78(0.14)|8.99((0.14)|\n|$\\xi$=0.7|0.91(0.01)|0.92(0.01)|0.93(0.01)| |8.26(0.11)|8.61(0.13)|8.82(0.14)|\n|$\\xi$=0.8|0.91(0.01)|0.92(0.01)|0.92(0.01)| |8.13(0.11)|8.47(0.14)|8.67(0.14)|\n|$\\xi$=0.9|0.91(0.01)|0.92(0.01)|0.92(0.01)| |8.07(0.13)|8.41(0.16)|8.61(0.15)|\n\n## Q5:  A brief discussion or experiment on  bounded Lebesgue density would strengthen the practical relevance.\n\nWe appreciate your constructive comments. Our response is structured in three parts:\n\n- The assumption of a bounded Lebesgue density applies only to continuous return distributions, since discrete random variables are not absolutely continuous with respect to the Lebesgue measure. Accordingly, this condition is not required or applicable when the return is discrete, as in Example 3 of our experiments. We acknowledge this and will clarify it in the revised paper.\n\n- For continuous return distributions, the bounded density assumption is mild and satisfied by many commonly used distributions such as Gaussian, exponential, and Gamma with shape parameter no less than 1. For instance, in Examples 1 and 2 of our experiments, the return is continuous and satisfies the bounded density condition. \n\n- To illustrate, consider **Example 1** in our paper. In this example, the state space of the environment is discrete with two possible values: $S_t=1$ and $S_t=2$. The agent transfers from a current state to a different state with a certain probability determined by the policy and the discount factor is $\\gamma = 0.8$.\nThe reward obtained when transitioning from state $1$ is distributed as $N(2, 1)$, and the reward obtained when transitioning from state $2$ is distributed as N (1, 1), i.e., $R_t|S_t\\sim N(-3S_t+5,1)$.\nGiven a history of states $(S_0,S_1,\\ldots)$, the $R_t$'s are independent Gaussian variables, so the return $G=\\sum_{t=0}^\\infty\\gamma^tR_t$ also follows a Gaussian distribution.\nPlease note that the Gaussian density is upper-bounded by $1/\\sqrt{2\\pi\\sigma^2}$ where $\\sigma^2$ is its variance.\nThe variance of $G$ conditional on $(S_0,S_1,\\ldots)$ is $\\sum_{t=0}^\\infty \\gamma^{2t} = 1/(1-\\gamma^2)$, so the conditional density is upper-bounded by $\\sqrt{\\frac{1-\\gamma^2}{2\\pi}}$. Since this upper bound is irrelevant with $(S_1,S_2,\\ldots)$, the conditional density of $G$ given $S_0$ is also bounded by $\\sqrt{\\frac{1-\\gamma^2}{2\\pi}}$.\nSimilarly, we can verify that **Example 2** also satisfies this bounded density condition.\n\n\n# Reference\n\n[1] Distributional Off-policy Evaluation with Bellman Residual Minimization.\n\n[2] Distributional Off-Policy Evaluation in Reinforcement Learning.\n\n[3] An analysis of quantile temporal-difference learning."}]

Author rebuttal:

Meta-review: The paper proposes a conformal prediction framework for off-policy evaluation. All reviewers feel positive about the paper, as it studies an important topic that the NeurIPS community cares about and takes an important initial step. Reading through the paper and the reviews, the AC has some comments and suggestions about the framing of the work:

1. Standard OPE formulation often cares about the expected return, which is described as "insufficient" in intro. However, CP guarantees are not strictly stronger than mean estimation guarantees, as the latter cannot be induced from the former even with infinite amount of data.

2. The authors distinguish the submission from prior works in paper and rebuttal by (1) the infinite-horizon settings (vs. finite-horizon), and (2) accounting for misspecification (and prior works somehow don't do as well). For (1), it is mentioned that Foffano et al suffer the curse of horizon which is avoided by the current work. The AC's feeling is that you can't have both simultaneously, and the paper does not really solve these issues in some fundamental sense, but rather provide some soft mitigations using standard ideas from the RL toolbox (such as return truncation and multi-step learning). In particular, Theorems 1 and 2 has the error of tail distribution $\eta(s)$ (which I assume partially stems from model misspecification) discounted by $\gamma^k$. To say you do much better than prior works on model misspecification you'd want large $k$ so that this term is negligible, but any non-constant $k$ would cause curse of horizon in the off-policy setting, making the approach not fundamentally different from the situation in Foffano et al's work.
Decision: Accept (poster)