{"id":"40063fdf-1df1-48a3-9887-48e0b43a5b92","arxiv_id":"2507.16236","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces PACOPP, a rejection-sampling plus conformal prediction algorithm that gives probably approximately correct coverage guarantees for off-policy reward prediction intervals in contextual bandits.","lead":"This paper presents PACOPP, an algorithm that builds prediction intervals for a target policy's reward using offline data from a different behavior policy, with a finite-sample guarantee that the interval covers the true reward with a prescribed confidence level even conditional on the given data set. The method targets safety-critical decisions such as personalized dosing or recommendations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is sound under its stated B<∞ condition, but that condition is load-bearing and is not reflected in the abstract's 'any ε,δ' and 'no distributional assumptions' claims.","rationale":"The reader's weakest assumption identifies B<∞ as load-bearing, and my read agrees. I examined the proof of Theorem 1 in detail: the rejection-sampling reduction (Proposition 1) is standard, the conditioning on N_rs and D_rs^1 is handled correctly, and the binomial quantile argument with k(M,ε,δ) is valid. Thus the PAC validity claim is internally consistent under the stated assumption. The finite-B restriction is the single most important limitation because without it the algorithm is not even executable, and the abstract overstates the scope by saying 'without relying on any distributional or space assumptions.' The other concerns noted by the reader, such as the unproven second half of Theorem 6 and the hand-waving in Theorem 5, affect secondary efficiency claims rather than the central PAC guarantee, so they do not change the verdict. A conditional accept remains appropriate: the paper should add a precise statement of the B<∞ assumption to the abstract and main theorem, and either prove or remove the omitted part of Theorem 6.","tokens_in":21110,"tokens_out":16680,"duration_ms":173194,"concrete_test":"Run Algorithm 1 in the setting S∼N(0,1), A|s∼N(s/4,4) (behavior policy) and πe(·|s)=N(s/4,1) (target policy) on an unbounded action space. The likelihood ratio w(s,a)=πe(a|s)/πb(a|s) grows without bound as |a|→∞, so B=∞, the RS acceptance probability is 0 for every point, and the algorithm produces no finite interval. This demonstrates that the theorem's scope is exactly the stated B<∞ regime; if the authors intend the unqualified claim in the abstract, they must either relax B<∞ or qualify Theorem 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central PAC guarantee (Theorem 1) is correct conditional on the rejection-sampling step being well defined, and that requires B = sup_{s,a} πe(a|s)/πb(a|s) < ∞, as stated in Section 3.1. This is load-bearing: Proposition 1 and the i.i.d. property of D_rs fail when B = ∞, and Algorithm 1's step 7 computes an infinite bound, so the algorithm cannot be run. The assumption is not merely technical; it restricts the target policy to be dominated by the behavior policy in the likelihood-ratio sense. Many natural policy pairs, such as a target policy with heavier-tailed action distributions than the behavior policy, violate it. The abstract's claim of 'without relying on any distributional or space assumptions' is therefore too strong. The paper is transparent about the assumption, but it limits the scope of the headline 'any ε,δ' guarantee. No internal inconsistency in Theorem 1's proof was found.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PACOPP, an algorithm for constructing probably approximately correct (PAC) prediction intervals for the reward of a target policy in offline contextual bandits, where data are collected under a possibly different behavior policy. The method applies rejection sampling to the offline data with weights equal to the target-to-behavior policy ratio, then uses a split-conformal construction whose threshold is a binomial quantile determined by the prescribed (ε, δ). Theorems 1--3 give finite-sample PAC validity and confidence/coverage-rate bounds, Theorem 5 claims asymptotic equivalence with the oracle quantile interval, and Theorems 6--7 extend the construction to an estimated behavior policy.","tokens_in":21249,"tokens_out":11244,"duration_ms":120724,"significance":"If the guarantees hold as stated, the paper makes a useful contribution to off-policy uncertainty quantification: it provides finite-sample training-conditional validity, rather than only marginal coverage, and the threshold is a binomial quantile rather than a data-fit constant, so the main PAC statement is not circular. The self-contained proof of Theorem 1 is a genuine strength, as is the explicit treatment of the unknown-behavior-policy case and the released simulation code. The principal limitation is that the whole construction is conditional on B = sup πe/πb < ∞, which is a substantive restriction on the policy pair; this limits the scope of the abstract's headline claims but does not, by itself, invalidate the main theorem.","major_comments":[{"comment":"The abstract's claim that the method works 'without relying on any distributional or space assumptions' is stronger than what is actually proven. Algorithm 1 and Proposition 1 require B = sup_{(s,a)} πe(a|s)/πb(a|s) < ∞ (Section 3.1), and Algorithm 1's step 7 computes this supremum explicitly. The paper is transparent about this condition in Section 3.1, but the headline claims in the abstract and introduction should be qualified to state that the PAC guarantee requires the target policy to be dominated by the behavior policy in the likelihood-ratio sense.","section":"Abstract; §3.1"},{"comment":"The second assertion of Theorem 6 is presented as a theorem, with the text saying 'a proof deferred to A.6', but Appendix A.6 ends with 'follows similarly and is omitted here.' Since this bound is part of the claimed counterpart to Theorems 1--3, it is not acceptable to leave it unproved in a formal theorem. The authors should either supply the full proof or demote the statement to a conjecture/remark with the missing argument sketched.","section":"Theorem 6; Appendix A.6, Eq. (14)"},{"comment":"Equation (18) writes F_{m,ε}(√m y_m), but y_m is already standardized by √m, so the argument appears to be a typo for F_{m,ε}(y_m). In addition, the final bound in the proof contains a term C1 B/√γ that is not of order 1/√n, so the constant in Theorem 2 as stated does not match the proof's decomposition. Please correct the typo and reconcile the constants so that the stated C/√n rate is what the proof actually delivers.","section":"Appendix A.3, proof of Theorem 2, Eq. (18)"},{"comment":"The second inequality, P[ε < LP ≤ ε + Δn] > δ − C/(√n Δn), does not follow from Theorems 2 and 3 as written. Theorem 2 only bounds P[LP ≤ ε] from above, which gives a lower bound on P[LP > ε], and no upper bound on P[LP > ε + Δn] is established in the displayed theorems or in the surrounding text. The corollary therefore needs a proof or a precise reference to a bound that supplies the missing tail control.","section":"Corollary 4"}],"minor_comments":[{"comment":"The pseudo-code does not define the (|D| + 1)-th smallest value when k = −1; the text defines τ_{M+1} = ∞, and the function should explicitly return ∞ in that case.","section":"Algorithm 1, function Pac-Cp"},{"comment":"The caption lists δ = 0.15 while the text reports PAC-0.25 for the same configuration; the reported simulation settings should be made consistent.","section":"Section 4.3 and Figure 2 caption"},{"comment":"There are several typos and infelicities, including 'aotonomous' (Introduction), 'dut to' (Section 3), 'dismatch' (Section 3.1), and 'In a mathematical view of point' (Introduction); the manuscript should be proofread.","section":"Throughout"},{"comment":"The statement that COPP-RS achieves marginal coverage 'under the conditions in Theorem 1' should specify the exact weighted-quantile construction and the conditions on the rejection sampling step, since the threshold is the 1−ε empirical quantile with the (M+1)-point distribution.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The central PAC validity theorem (Theorem 1) appears sound and is the paper's main contribution. The manuscript would be acceptable after the missing proof of Theorem 6(14) is supplied, the Corollary 4 gap is fixed, and the scope limitation B < ∞ is reflected in the abstract. The current version states more than it proves in several places, so major revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid, useful paper with a load-bearing assumption the abstract glosses over. Theorem 1 is sound as far as I can tell; the rejection-sampling reduction to i.i.d. from the target distribution is standard, and the PAC calibration argument is careful. The genuinely new pieces are Theorems 2 and 3 (PAC-type efficiency: attained confidence approaches 1-delta and coverage sits near the nominal level at 1/sqrt(n) rates) and Theorem 5 (asymptotic equivalence to the oracle interval). Those are real additions beyond Park et al.\n\nSoft spots, in decreasing order. First, the bounded likelihood ratio B = sup pi_e/pi_b < infinity is not a technical footnote. The algorithm literally cannot run when it fails (Step 7 computes an infinite bound), and the i.i.d. claim of Proposition 1 breaks. Many reasonable policy pairs violate it. The abstract's \"without relying on any distributional or space assumptions\" is simply too strong; the assumption is transparent in Section 3.1 but it should appear in the abstract and intro. Second, the second half of Theorem 6 (equation 14) is explicitly unproven, with Appendix A.6 saying \"follows similarly and is omitted.\" For a theorem stated as a result, that is a gap; either prove it or relegate it to a conjecture. The first half (13) is fine. Third, the proof of Theorem 5 has a hand-wavy step around the partition of the calibration set and the influence of the B_l set; I think it likely goes through, but it needs tightening before publication. Smaller issues: Theorem 2/3 constants contain typos, and the experiments lack error bars, a direct comparison to the closest PAC-prediction baseline, and any setting with large or infinite B. The paper does honestly cite Park et al. for the threshold construction; the conclusion's \"first to achieve PAC validity\" claim is mild overstatement and should be softened.\n\nWho this is for: people doing conformal off-policy evaluation or safe policy deployment with continuous actions. The central PAC validity result is credible, the efficiency analysis is a genuine step, and the limitations are addressable. I would send it to referees, not desk-reject it.","headline":"A credible PAC extension for off-policy prediction, with a load-bearing bounded-ratio assumption the abstract glosses over and one explicitly unproven bound; worth refereeing after fixes.","tokens_in":21824,"tokens_out":1860,"would_cite":true,"duration_ms":19418,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that logged data from one policy can be turned into a prediction interval for another policy's reward that is probably approximately correct: with confidence $1-\\delta$, its conditional miscoverage is at most $\\epsilon$.","keywords":["Contextual Bandits","Off-Policy Evaluation","Probably Approximately Correct Inference","Conformal Prediction","Reinforcement Learning","Prediction Intervals","Rejection Sampling"],"falsifier":"Take a two-action bandit with $\\pi_b$ choosing action 1 with probability 1 and $\\pi_e$ choosing action 2 with probability 1: then $B=\\infty$, Proposition 1 fails, and Algorithm 1 has no accepted sample from the target policy, so the claimed $(\\epsilon,\\delta)$ guarantee cannot hold for any fixed sample size. A quantitative check would simulate the known-$\\pi_b$ setting with a large but finite $B$ and compare the empirical probability that $L^{\\pi_e}(\\hat C_{\\tilde\\tau})\\le\\epsilon$ with the upper bound $1-\\delta+C/\\sqrt{n}$ from Theorem 2; exceeding the bound by more than the constant would refute the stated rate.","tokens_in":20865,"feed_emoji":"🎯","tokens_out":12276,"duration_ms":113647,"temperature":0.7,"pith_summary":"The paper sets out to show that off-policy evaluation in contextual bandits can be made training-conditional rather than merely marginal: from data logged under a behavior policy, one can build a prediction interval for the reward of a different target policy such that the interval's miscoverage is at most $\\epsilon$ with confidence at least $1-\\delta$. The construction, PACOPP, corrects the distribution shift by rejection sampling and then applies a PAC-valid conformal threshold, avoiding any need to estimate reward densities. The authors prove finite-sample PAC validity, show that the achieved confidence approaches $1-\\delta$ and coverage approaches $\\epsilon$ at a $1/\\sqrt{n}$ rate, and prove asymptotic equivalence to the oracle quantile interval. They also analyze the case of an unknown behavior policy, where the coverage guarantee degrades by the estimation error of the policy ratio. A sympathetic reader would care because safety-critical deployment needs guarantees that hold for the data set actually collected, not only averaged over repeated data sets.","feed_headline":"PAC intervals certify off-policy rewards from logged bandit data","feed_subtitle":"Its prediction intervals hit 1-epsilon conditional coverage with confidence 1-delta, no density model required.","key_machinery":"The load-bearing objects are three. The first is the policy ratio $w(s,a)=\\pi_e(a|s)/\\pi_b(a|s)$ with finite supremum $B$: rejection sampling keeps $(S_i,A_i,R_i)$ with probability $w(S_i,A_i)/B$, and Proposition 1 shows the accepted $(S_i,R_i)$ pairs are i.i.d. from the target marginal $P^{\\pi_e}$, the distribution of the test reward. The second is the family of candidate intervals $\\hat C_\\tau(S)=[\\hat q_{\\epsilon_{lo}}(S)-\\tau,\\hat q_{\\epsilon_{up}}(S)+\\tau]$ from conformal quantile regression, scored by non-conformity values $\\tau_i=\\max\\{\\hat q_{\\epsilon_{lo}}(S_i)-R_i,\\,R_i-\\hat q_{\\epsilon_{up}}(S_i)\\}$. The third is the PAC threshold $k(M,\\epsilon,\\delta)=\\max\\{k:F_{\\mathrm{Bin}(M,\\epsilon)}(k)\\le\\delta\\}$, which lets the algorithm pick the smallest $\\tau=\\tau_{(M-k)}$ such that no more than $k$ of the $M$ calibration points fall outside; the binomial tail is what converts one data set into a $1-\\delta$-confident, $\\epsilon$-coverage statement. The efficiency theorems then use the Berry-Esseen inequality to control the normal approximation of that binomial tail, and total-variation distance to bound the extra coverage loss when the behavior policy must be estimated.","core_discovery":"The central claim is that a probably approximately correct prediction interval for the reward of a target policy can be constructed from offline data logged under a different behavior policy, without estimating the reward distribution. The procedure PACOPP first rejects each logged tuple with probability $1 - w(S_i,A_i)/B$, where $w(s,a)=\\pi_e(a|s)/\\pi_b(a|s)$ and $B=\\sup w$; the surviving context-reward pairs are then i.i.d. from the target marginal $P^{\\pi_e}$ (Proposition 1). On a calibration split of this accepted sample, it fits conditional quantile estimators $\\hat q_{\\epsilon_{lo}}$ and $\\hat q_{\\epsilon_{up}}$, forms the nested intervals $\\hat C_\\tau(S)=[\\hat q_{\\epsilon_{lo}}(S)-\\tau,\\hat q_{\\epsilon_{up}}(S)+\\tau]$, and chooses $\\tilde\\tau=\\tau_{(M-k(M,\\epsilon,\\delta))}$ with $k(M,\\epsilon,\\delta)=\\max\\{k:F_{\\mathrm{Bin}(M,\\epsilon)}(k)\\le\\delta\\}$. Theorem 1 proves that this output is an $(\\epsilon,\\delta)$-PAC prediction interval; Theorems 2 and 3 show that the confidence in coverage approaches $1-\\delta$ and miscoverage concentrates around $\\epsilon$ at a $1/\\sqrt{n}$ rate; Theorem 5 proves asymptotic equality with the oracle interval $[q_{\\epsilon_{lo}}(S),q_{\\epsilon_{up}}(S)]$ under the target policy; Theorems 6 and 7 extend the guarantee to an estimated behavior policy, with coverage loss bounded by the estimation error of the weight function.","pith_inferences":["The finite ratio condition $B<\\infty$ is also a practical design rule: a target policy that ever assigns positive mass where the behavior policy is zero lies outside the method, so safe deployment needs either full-support logging or a clipped target.","Because the calibration threshold $k(M,\\epsilon,\\delta)$ uses only the binomial tail, the same PAC construction should extend to other offline inference tasks, such as quantile regression, risk measures, or treatment effects, wherever a rejection-sampling step can produce an i.i.d. target sample.","A note for readers: the second inequality in Theorem 6 (equation (14)) is asserted with its proof deferred to Appendix A.6, which omits the proof, so the unknown-policy efficiency statement rests on an assertion rather than a demonstrated argument.","Rejection sampling discards roughly $1-1/B$ of the logged data; a natural testable extension is a full-data importance-weighted version that reuses rejected samples, whose bias-variance trade-off the current analysis does not cover."],"forward_implications":["For any prescribed $\\epsilon$ and $\\delta$, Algorithm 1 returns a prediction interval whose data-conditional miscoverage is at most $\\epsilon$ with probability at least $1-\\delta$, with no assumptions on the reward distribution or action-space geometry.","Theorems 2 and 3 give matching upper and lower bounds: the probability that coverage misses its nominal level decays at a $1/\\sqrt{n}$ rate, so the interval is not just valid but efficient.","Theorem 5 shows that, when the conditional quantile estimators are consistent, the interval converges in Lebesgue measure to the oracle interval $[q_{\\epsilon_{lo}}(S),q_{\\epsilon_{up}}(S)]$ under the target policy.","When the behavior policy is unknown, Theorem 6 bounds the coverage loss by the $\\ell^1$ estimation error $\\Delta_w$ of the weights, and Theorem 7 gives an explicit PAC bound under maximum-likelihood estimation over a finite policy class.","The method applies to continuous action spaces and requires no estimate of the reward density, unlike weighted-conformal baselines."],"supporting_citations":[{"why":"Origin of rejection sampling; the RS procedure of Algorithm 1 is a direct application.","marker":"von Neumann [1951]"},{"why":"Theorem 4.2 is the basis of Proposition 1, giving the i.i.d. target-distribution property of the accepted sample.","marker":"Owen [2013]"},{"why":"Introduces PAC-valid conformal prediction; provides the split-CP comparison that motivates the modified threshold.","marker":"Vovk [2013]"},{"why":"Supplies the PAC confidence-set construction and the $k(M,\\epsilon,\\delta)$ threshold formula used in Pac-Cp.","marker":"Park et al. [2020]"},{"why":"Conformal quantile regression; provides the candidate intervals $\\hat C_\\tau(S)$ around fitted conditional quantiles.","marker":"Romano et al. [2019]"},{"why":"Weighted conformal prediction under covariate shift; the framework PACOPP avoids because it requires density ratios.","marker":"Tibshirani et al. [2019]"},{"why":"Baseline COPP for continuous-action off-policy prediction; PACOPP is compared against it and needs no reward density estimate.","marker":"Taufiq et al. [2022]"},{"why":"Berry-Esseen inequality (Theorem 3.4.17) used in the proofs of Theorems 2 and 3 for the $1/\\sqrt{n}$ confidence rates.","marker":"Durrett [2019]"},{"why":"Theorem 21 bounds the $\\ell^1$ error of MLE over a finite policy class, used in Theorem 7 for unknown $\\pi_b$.","marker":"Agarwal et al. [2020]"}],"fun_headline_variants":["PAC intervals for off-policy rewards, no density model","Log data, get PAC intervals for any target policy","Off-policy rewards: PAC intervals with finite-sample coverage","Conditional coverage intervals for logged bandit data","No reward model, just PAC intervals for off-policy evaluation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction depends on a finite density-ratio bound $B=\\sup_{s,a}\\pi_e(a|s)/\\pi_b(a|s)$: if the target policy can choose actions that the behavior policy essentially never picks, rejection sampling cannot produce an i.i.d. sample from the target distribution and the PAC guarantee has nothing to hold onto.","fun_headline_variants_meta":{"raw":{"variants":["PAC intervals for off-policy rewards, no density model","Log data, get PAC intervals for any target policy","Off-policy rewards: PAC intervals with finite-sample coverage","Conditional coverage intervals for logged bandit data","No reward model, just PAC intervals for off-policy evaluation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1508,"prompt_tokens":1000,"completion_tokens":508,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":429}},"tokens_in":616,"tokens_out":508,"duration_ms":6267,"temperature":1.0,"reasoning_tokens":429,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:15:41.026216+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-action bandit with $\\pi_b$ choosing action 1 with probability 1 and $\\pi_e$ choosing action 2 with probability 1: then $B=\\infty$, Proposition 1 fails, and Algorithm 1 has no accepted sample from the target policy, so the claimed $(\\epsilon,\\delta)$ guarantee cannot hold for any fixed sample size. A quantitative check would simulate the known-$\\pi_b$ setting with a large but finite $B$ and compare the empirical probability that $L^{\\pi_e}(\\hat C_{\\tilde\\tau})\\le\\epsilon$ with the upper bound $1-\\delta+C/\\sqrt{n}$ from Theorem 2; exceeding the bound by more than the constant would refute the stated rate.","supporting_citations":[{"cited_title":"Various techniques used in connection with random digits","cited_arxiv_id":null,"evidence_quote":"Origin of rejection sampling; the RS procedure of Algorithm 1 is a direct application."},{"cited_title":"Pac confidence sets for deep neural networks via calibrated prediction","cited_arxiv_id":null,"evidence_quote":"Supplies the PAC confidence-set construction and the $k(M,\\epsilon,\\delta)$ threshold formula used in Pac-Cp."},{"cited_title":"Conformalized quantile regression","cited_arxiv_id":null,"evidence_quote":"Conformal quantile regression; provides the candidate intervals $\\hat C_\\tau(S)$ around fitted conditional quantiles."},{"cited_title":"Conformal prediction under covariate shift","cited_arxiv_id":null,"evidence_quote":"Weighted conformal prediction under covariate shift; the framework PACOPP avoids because it requires density ratios."},{"cited_title":"Conformal off-policy prediction in contextual bandits","cited_arxiv_id":null,"evidence_quote":"Baseline COPP for continuous-action off-policy prediction; PACOPP is compared against it and needs no reward density estimate."},{"cited_title":"Probability: Theory and Examples","cited_arxiv_id":null,"evidence_quote":"Berry-Esseen inequality (Theorem 3.4.17) used in the proofs of Theorems 2 and 3 for the $1/\\sqrt{n}$ confidence rates."},{"cited_title":"Flambe: Structural complexity and representation learning of low rank mdps","cited_arxiv_id":null,"evidence_quote":"Theorem 21 bounds the $\\ell^1$ error of MLE over a finite policy class, used in Theorem 7 for unknown $\\pi_b$."}],"review_version":1}