PaperlayerView exact revision on arXiv

Source-linked AI summary

Counterfactual Online Conformal Prediction Under Adaptive Logging

Xinyu Qiao, Yichen Lin, Kaihong Ji, Xue Wang, Tao Yao

arXiv:2609.30811v1cs.LG

TL;DR

Online conformal prediction under adaptive logging can preserve realized-stream coverage while leaving counterfactual outcomes for rarely selected actions miscalibrated. The paper introduces propensity-weighted and doubly robust calibration, and reports improved counterfactual coverage and regret across benchmarks while retaining sharp sets.

  • Problem

    Adaptive logging determines which outcomes enter calibration, so realized-stream coverage does not establish coverage for the counterfactual outcomes of rarely selected actions.

    Source: §1 · p. 1, §3 · p. 3

  • Method

    PW-OCP uses an inverse-propensity-weighted miscoverage estimator, while DR-OCP further reduces nuisance bias to the product of outcome-model and propensity errors.

    Source: §1 · p. 1

  • Results

    Across seven synthetic, open-bandit, and financial benchmarks, PW-OCP and DR-OCP reduce counterfactual gaps and decision regret while retaining sharp prediction sets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The sharpness–coverage decomposition links downstream decision regret to tighter prediction sets rather than marginal coverage alone.

    Source: §1 · p. 2

    Uniform counterfactual coverage requires positivity; logging with πmin → 0 cannot support it, and maintaining an exploration floor may be costly.

    Source: §8 · pp. 9–10

Abstract

from arXiv · show

Online conformal prediction can fail when predictions shape actions and actions determine which outcomes enter calibration. Standard adaptive methods may retain marginal coverage while systematically miscovering the counterfactual outcomes of rarely selected actions. This paper formalizes the failure through counterfactual coverage and introduces Propensity-Weighted Online Conformal Prediction, an inverse-propensity-weighted recursion that debiases calibration. A doubly robust variant further reduces nuisance bias to the product of outcome-model and propensity errors. Under positivity, the resulting coverage rate matches an information-theoretic lower bound up to logarithmic factors. Experiments on synthetic decision tasks, open bandit data, and financial rebalancing show that PW-OCP and DR-OCP improve counterfactual coverage and downstream regret without sacrificing prediction-set sharpness.

1 Introduction

Adaptive logging can preserve coverage on observed outcomes while leaving counterfactual outcomes for rarely selected actions miscalibrated. The paper formalizes this gap, introduces propensity-weighted corrections, and connects counterfactual coverage to downstream regret and benchmark performance.

1 Introduction

  • Standard online conformal methods preserve average coverage on the realized stream, but rarely selected actions can remain miscalibrated.Those actions may be alternatives that downstream rules need to compare.Source: §1 · p. 1
  • PW-OCP replaces the observed error indicator with an inverse-propensity-weighted estimator, and DR-OCP further reduces nuisance bias to the product of outcome-model and propensity errors.Under positivity, the methods attain a high-probability counterfactual coverage rate matching an information-theoretic lower bound up to logarithmic factors.Source: §1 · pp. 1–2
  • Logged-quantile per-action calibrators suffer a counterfactual coverage gap of order Ω(ρ), where ρ quantifies action-induced shifts in the outcome law.The gap is structural: standard recursion converges to a logged-score quantile that can differ persistently from the counterfactual target.Source: §1 · pp. 1–2
  • A sharpness–coverage decomposition translates the coverage gap into a robust pseudo-regret bound, linking improved downstream decisions to tighter prediction sets rather than marginal coverage alone..Source: §1 · p. 2
  • On seven synthetic, open-bandit, and financial benchmarks, PW-OCP and DR-OCP reduce counterfactual gaps and decision regret while retaining sharp prediction sets.Source: §1 · p. 2

2 Problem Formulation

The setup allows history-dependent logging and defines action-specific counterfactual coverage alongside observable realized-stream measures. Its assumptions and endogeneity framing distinguish logged calibration from the per-action counterfactual target.

2 Problem Formulation

  • The interaction has T rounds, a finite action space, and observed history H_{t−1}; the logging policy may depend on history without being i.i.d. or stationary.Source: §2 · p. 2
  • For each action, the learner maintains a threshold for a nonconformity score to form its prediction set.The target miscoverage level is α.Source: §2 · p. 2
  • Each round reveals a context, then prediction sets, then a logged action, and finally the outcome for that action.Source: §2 · p. 2

2.3 Endogeneity Coefficient

  • The classical online conformal setting is recovered when outcomes do not depend on the action; ρ = 0 likewise recovers exchangeable online conformal prediction.Source: §2 · p. 2, §2.3 · p. 3

2.1 Potential Outcomes and Structural Assumptions

  • Potential outcome Y_t(a) is the outcome under intervention a; the assumptions require no unmeasured confounding and positive logging probability for every action.The framework treats potential outcomes as conditionally independent of the chosen action given context and history.Source: §2.1 · p. 2

2.2 Coverage Targets

  • Marginal coverage is observable, action-conditional coverage uses rounds when an action was played, and counterfactual coverage averages over the marginal context distribution.Controlling marginal or action-conditional coverage need not control counterfactual coverage when ρ > 0.Source: §2.2 · pp. 2–3

2.3 Endogeneity Coefficient

  • When ρ > 0, logged scores come from a policy-dependent mixture rather than the per-action laws needed for counterfactual calibration, making calibration a causal estimation problem under selection-biased sampling.Source: §2.3 · p. 3

3 Failure of Standard Online CP Under Endogenous Logging

Standard online conformal prediction can preserve logged empirical coverage while failing on counterfactual outcomes. Under endogenous logging, per-action calibration to logged quantiles can leave a non-vanishing counterfactual coverage gap.

3.1 Logged Empirical Coverage Survives

  • The pathwise, distribution-free bound controls logged empirical coverage, not per-action counterfactual coverage, and leaves rarely selected actions unconstrained.The logged average may satisfy the bound even when the recursion drives prediction sets to degenerate extremes on a non-vanishing fraction of rounds.Source: §3.1 · p. 3, §3 · p. 3

3.2 Counterfactual Coverage Breaks

  • When ρ ≫ εT, logged-quantile per-action calibration can leave counterfactual coverage error at least c(α)ρ − O(T^-1/2), because logged and counterfactual quantiles differ by Θ(ρ).Figure 1 shows ACI’s counterfactual gap growing with mean shift while PW-OCP remains close to Oracle.Source: §3.2 · p. 4, Figure 1 · p. 4
  • The impossibility result applies to predictable per-action thresholds targeting logged action-conditional quantiles, including standard per-arm ACI and logged-quantile adaptive baselines.It also covers smoothing or aggregation when the per-arm fixed point remains the logged quantile; the proof uses a two-context Gaussian variance-shift construction.Source: §3.2 · p. 4

4 Propensity-Weighted Online Conformal Prediction

PW-OCP changes the calibration signal from observed logged errors to an inverse-propensity-weighted estimate of counterfactual miscoverage. Its doubly robust variant augments that signal with an outcome model.

4 Propensity-Weighted Online Conformal Prediction

  • PW-OCP replaces the logged error indicator with an inverse-propensity-weighted estimate of counterfactual miscoverage, realigning the recursion’s target.Under no unmeasured confounding, the propensity weight cancels the logger’s selection probability, making the signal unbiased for round-t counterfactual miscoverage.Source: §4 · p. 4, §4.1 · p. 5

4.2 Algorithm

  • The algorithm maintains one miscoverage index per action, computes thresholds from that action’s logged scores, and updates the recursion using the IPW signal.After observing the logged action and outcome, it updates the corresponding action’s score set and calibrates each action’s index.Source: §4.2 · p. 5

4.3 Doubly Robust Calibration

  • DR-OCP replaces the IPW signal with an outcome-model-augmented signal whose residual conditional bias is the product of outcome-model and propensity errors.The construction reduces to PW-OCP when the outcome model is zero and the propensity estimate equals the true logging propensity.Source: §4.3 · p. 6

5 Theoretical Analysis

The analysis establishes counterfactual coverage guarantees for PW-OCP and DR-OCP, compares them with an information-theoretic lower bound, and relates coverage to sharpness and decision regret.

5.1 Coverage Guarantees

  • PW-OCP’s counterfactual coverage error has leading order (Tπmin)^-1/2 up to logarithmic factors, with the rate non-vacuous when Tπmin is at least on the order of log(KT/δ).The IPW update restores the counterfactual error signal; the exact telescoping identity requires no clipping or projection.Source: §5.1 · p. 6
  • DR-OCP’s coverage bound includes a nuisance-bias term proportional to ϵµ,aϵπ,a/π̂min, which vanishes when either nuisance is consistent.Clipping or projecting the recursion to a fixed interval reduces its transient term to O(1/(γT)); using true propensities makes the outcome model a variance-reduction control variate.Source: §5.1 · pp. 6–7

5.2 Information-Theoretic Lower Bound

  • The minimax lower bound reflects the Tπmin effective observations for the rarest action: above the testing threshold the rate is log K/(Tπmin), and below it the bound is constant.The lower bound ranges over predictable threshold algorithms and context-free Gaussian potential-outcome instances with fixed logging policies.Source: §5.2 · p. 7
  • PW-OCP matches the lower bound up to logarithmic factors and the difference between high-probability and in-expectation risk, within the predictable score-threshold class.The leading dependence on T, K, and πmin is unimprovable in that class.Source: §5.2 · p. 7
  • Sharpness and regret results rule out attaining coverage simply by widening sets: under stated regularity conditions, projected PW-OCP controls threshold error near the oracle quantile and decomposes robust pseudo-regret.The decomposition includes sharpness, logged coverage, and exploration terms.Source: §5.2 · p. 7

6 Experiments

Across synthetic, open-bandit, and financial benchmarks, PW-OCP and DR-OCP improve counterfactual coverage and decision regret while retaining sharp prediction sets. Their advantage persists under propensity misspecification, although PW-OCP is sensitive to inaccurate propensities.

Counterfactual coverage

  • At K = 20, ACI’s gap is 0.418 ± 0.009, versus 0.074 ± 0.007 for PW-OCP and 0.065 ± 0.012 for DR-OCP.With mean shift ∆= 2 and K = 2, baseline gaps cluster in [0.25, 0.37], while PW-OCP reaches 0.017±0.007 and DR-OCP 0.018±0.006.Source: §6 · pp. 7–8, Figure 2 · p. 8

Prediction-set quality, rates, and decisions

  • As T grows, PW-OCP and DR-OCP move counterfactual coverage gaps toward Oracle while logged-calibration baselines retain persistent bias.Their average finite threshold error relative to the oracle counterfactual quantile also decreases with T.Source: Figure 3 · p. 8

Propensity robustness

  • DR-OCP retains a 0.030 ± 0.008 gap under the uniform propensity model, while PW-OCP collapses to the ACI gap.Across the misspecification sweep, DR-OCP remains stable as the outcome model absorbs first-order propensity bias.Source: §6 · pp. 8–9, Figure 3 · p. 8

Prediction-set quality, rates, and decisions

  • PW-OCP and DR-OCP combine large decision gains with the strongest counterfactual coverage across most benchmarks.Online COPP gives the largest reduction; Table 1 compares coverage gaps and normalized regret reduction across benchmarks.Source: Table 1 · p. 8, §6 · p. 9

Real data

  • On Open Bandit and DJIA, PW-OCP and DR-OCP remain among the best non-oracle methods across Women, Men, and financial rebalancing.Absolute gaps are smaller because several baselines already achieve near-nominal logged coverage.Source: §6 · p. 9

7 Related Work

Prior conformal methods address distribution shift, partial feedback, or downstream decisions, but do not jointly handle action-induced selection bias in online calibration. This work targets counterfactual coverage for every action as logging evolves.

Online CP under distribution shift

  • Adaptive conformal methods track realized errors under exogenous shift, but do not detect selection bias when prediction sets shape logging.The proposed inverse-propensity-weighted recursion targets counterfactual coverage on every action, including rarely selected ones.Source: §7 · p. 9

Partial-feedback CP

  • Partial-feedback conformal methods assume exogenous per-action outcome laws (ρ = 0), unlike the action-induced outcome shift (ρ > 0) addressed here.The paper presents IPW correction and a doubly robust extension for this latter regime.Source: §7 · p. 9

Counterfactual, batch, and decision-theoretic CP

  • Batch counterfactual and decision-theoretic conformal methods assume fixed offline or exogenous calibration data, not an evolving feedback loop.This work combines online per-action counterfactual coverage with a bound translating coverage error into downstream decision regret.Source: §7 · p. 9

8 Discussion and Limitations

Endogenous logging can leave online conformal prediction marginally valid while producing persistent counterfactual gaps; propensity-weighted calibration targets those gaps. The framework also specifies boundaries on its guarantees and outlines operational, baseline, and sharpness results.

8 Discussion and Limitations

  • Logged-quantile calibration can retain a persistent Ω(ρ) counterfactual gap, while PW-OCP removes it at the minimax rate and DR-OCP reduces nuisance sensitivity.Experiments report improved coverage and robust decisions on rarely selected actions.Source: §8 · p. 9

A Broader impacts

  • Reliable counterfactual coverage is relevant where rarely selected actions matter, including clinical trials, dynamic pricing, and recommendation.The paper advises auditing propensities, maintaining an exploration floor, and monitoring counterfactual coverage over time.Source: A Broader impacts · p. 13

B.1 Doubly Robust Online Conformal Prediction

  • DR-OCP uses predictable nuisance estimates from past data, then combines an outcome-model miscoverage estimate with an inverse-propensity residual for the played action.This construction removes first-order sensitivity to either the propensity model or the outcome model.Source: §B.1 · p. 13

B.2 Online COPP Baseline

  • Online COPP uses a sliding-window IPW empirical quantile of logged scores, unlike PW-OCP’s adaptive miscoverage-index recursion.The comparison isolates the contribution of that online stochastic-approximation recursion.Source: §B.2 · p. 13

B.3 Nuisance Estimation for DR-OCP

  • The DR coverage bound is conditional on realized nuisance errors; the experiments use predictable nuisance estimates fitted using past data.The guarantee applies to any predictable nuisance sequence through a product term in the outcome-model and propensity errors.Source: §B.3 · pp. 13–14

C Additional Theoretical Results

  • The appendix treats prediction-set sharpness and the bridge from coverage to decision regret as additional theoretical results.Sharpness is measured by time-averaged threshold error relative to the oracle counterfactual quantile.Source: C Additional Theoretical Results · p. 14, §C.1 · p. 14

C.1 Prediction Set Sharpness

  • PW-OCP’s thresholds converge to oracle counterfactual quantiles at (Tπmin)−1/4, slower than the (Tπmin)−1/2 coverage rate, because converting coverage error to quantile error incurs a square-root cost.Theorem C.4 states that tightening counterfactual coverage from δ to δ/2 at most doubles worst-case regret in its two-arm construction.Source: §C.1 · p. 15

C.2 From Prediction Sets to Decisions

The section connects prediction-set quality to robust decision regret, showing that counterfactual calibration controls the sharpness term while exploration and logged coverage contribute separate terms. It also states conditions for transferring coverage bounds and gives a pathwise proof of the logged-coverage result.

C.2 From Prediction Sets to Decisions

  • The learner chooses the action minimizing worst-case loss over its prediction set with probability 1−ε, and explores uniformly with probability ε.The played action is also the logged action.Source: §C.2 · p. 15
  • The regret decomposition separates exploration, logged coverage, and sharpness; counterfactual calibration enters through sharpness, where biased calibration can produce persistently wide or narrow sets on rarely selected actions.For unbounded losses such as Gaussian squared loss, the theorem applies after truncation, with residual tail error controlled separately.Source: §C.2 · p. 16
  • The coverage-transfer condition is needed only when replacing the logged-coverage term in the decision bound with a counterfactual coverage bound.The logged term concerns the realized action; counterfactual calibration affects the sharpness term.Source: §C.2 · p. 16
  • Endogenous logging leaves logged-quantile calibrators with Ω(ρ) persistent threshold error and Ω(LρT) regret, while PW-OCP reduces both to sublinear estimation terms.The comparison is subject to the stated assumptions and coverage-transfer condition.Source: §C.2 · p. 17

D.1 Proof of Theorem 3.1

  • Theorem 3.1’s logged empirical-coverage proof is pathwise and requires no exchangeability, exogeneity, stationarity, or distributional assumption.The proof adapts the adaptive-conformal empirical-coverage argument to the logged sequence.Source: §D.1 · p. 17

D.2 Proof of Theorem 3.2

These proofs analyze counterfactual coverage under endogenous logging, the inverse-propensity cancellation and weighted-method arguments, and projected quantile recursion. They also use testing arguments to connect rare-arm outcomes and exploitation loss with coverage, accounting for a bounded exploration penalty.

D.2 Proof of Theorem 3.2

  • A small variance shift yields a population counterfactual coverage gap of at least c0(α)Δ, and the construction converts this to a gap proportional to endogeneity ρ.The construction has ρ(Δ) = Θ(Δ) for sufficiently small Δ.Source: §D.2 · p. 18

D.3 Proof of Lemma 4.2

  • The inverse-propensity factor cancels under the logging policy, yielding the claimed conditional expectation when predictability, positivity, consistency, and ignorability hold.Source: §D.3 · pp. 18–19

D.4 Envelope for the Weighted Recursion

  • The weighted recursion has a high-probability envelope rather than ACI’s deterministic envelope, with excursions driven back toward [0, 1] and an additional πmin^-1 factor.The proof bounds excursions above and below the interval; a single weighted error can move the recursion by order γ/πmin.Source: §D.4 · pp. 19–20

E.1 Proof of Theorem 5.1

  • Theorem 5.1’s proof telescopes the PW-OCP recursion and applies martingale concentration to obtain its coverage bound, with the transient statement following from the weighted-recursion envelope.Source: §E.1 · p. 20

E.2 Proof of Theorem 5.2

  • Theorem 5.2’s proof controls the doubly robust martingale term with Freedman’s inequality and bounds predictable bias using sequential ignorability and Cauchy–Schwarz.The second martingale term is dominated when Tπ̂min ≳ log(K/δ); otherwise it can be retained explicitly.Source: §E.2 · pp. 20–21

E.3 Proof of Theorem 5.4

  • Fano’s argument shows that identifying a perturbed rare arm can be impossible, forcing a worst-arm expected counterfactual coverage error at the theorem’s lower-bound scale.The proof reduces coverage calibration to identifying which rare arm is perturbed and handles both small- and larger-separation regimes.Source: §E.3 · pp. 22–23

E.4 Proof of Theorem C.3

  • Theorem C.3’s projected-quantile error bound combines initial-condition cost, stochastic-approximation variance, and empirical-quantile error under stationarity, positivity, and density conditions.Source: §E.4 · pp. 23–24

E.5 Proof of Theorem C.4

  • At two separated quantiles, uniform expected coverage accuracy would make the reported thresholds distinguish the hypotheses, but only arm 2’s observations distinguish them.Source: §E.5 · pp. 24–25
  • The proof invokes Bretagnolle–Huber’s form of Le Cam’s lemma: tests succeeding bounded away from one half require a KL condition.The supplied passage truncates the KL expression, so its distributions and bound are not specified here.Source: §E.5 · p. 25
  • Under P1, arm 1 is optimal for squared loss, and each pull of arm 2 incurs excess risk.The passage does not include the amount of excess risk.Source: §E.5 · p. 25

E.6 Proof of Theorem C.5

  • On exploitation rounds, the chosen action equals the action minimizing d_t(a); covered outcomes incur loss at most d_t, while assumption (ii) bounds the uncovered-outcome addition by B.The proof also invokes a Lipschitz assumption to derive an inequality for every action.Source: §E.6 · p. 25
  • On exploration rounds, assumption (iii) adds at most Δ_max relative to the exploitation action; the pathwise sum’s middle term is T(1 − MCov_T).The proof then takes expectations, but the supplied passage truncates the resulting expression.Source: §E.6 · p. 25

E.7 Proof of Corollary C.6

The proofs translate persistent counterfactual coverage error into threshold and decision comparisons on the stated Gaussian construction. They contrast logged-quantile calibrators with projected PW-OCP using local regularity and coverage-transfer conditions.

E.7 Proof of Corollary C.6

  • On the Gaussian construction, logged-quantile calibrators retain a counterfactual coverage gap of order ρ, up to O(T^-1/2) threshold-tracking error.The proof uses a local upper bound on the counterfactual score density near the oracle quantile to convert coverage error to threshold error.Source: §E.7 · p. 25
  • The PW-OCP comparison combines Theorem C.3’s estimate with Theorem 5.1 and the coverage-transfer condition to establish Corollary C.6(b).The resulting estimates are substituted into the sharpness–coverage decomposition.Source: §E.7 · p. 26

E.8 Proof of Corollary C.7

  • For Corollary C.7, the proof converts the persistent coverage gap into a threshold gap using local score-density boundedness, then establishes the sharpness comparison.The comparison also uses the projected threshold range on the high-probability bound’s failure event.Source: §E.8 · p. 26

F.1 Benchmark Design

The benchmark design spans synthetic shifts and scaling, Open Bandit campaigns, and financial rebalancing. Appendix figures examine effective-sample-size dependence, step-size sensitivity, and logged versus counterfactual coverage diagnostics.

F.1 Benchmark Design

  • The benchmark setup uses common online-conformal settings and clips PW-OCP and DR-OCP iterates to [−0.5, 1.5]; DR-OCP estimates contextual miscoverage with an exponential moving average.The listed nonconformity scores differ between mean-shift and variance-shift or multi-arm simulations.Source: §F.1 · p. 26
  • Synthetic tests cover mean shifts, variance shifts under risk-averse logging, and multi-arm scaling with K contexts and actions and exploration probability ε=0.05.In the multi-arm setup, πmin=ε/K.Source: §F.1 · p. 27

F.2 Open Bandit and Financial Logging

  • Open Bandit experiments use Women and Men campaigns with the top 15 items and four aggregated contexts; DJIA rebalancing covers four stocks over 2,500 trading days.Potential rewards are constructed from random-policy item-context click-rate estimates while preserving observed heterogeneity.Source: §F.2 · p. 27

F.3 Additional Appendix Figures

  • Figure 5 varies T and πmin separately and reports improving counterfactual coverage with effective sample size Tπmin, matching Theorem 5.1’s dependence.It fixes K=10, πmin=0.05 in the T sweep, and T=20,000 in the πmin sweep.Source: Figure 5 · p. 28
  • Figure 6 plots counterfactual coverage gap against γ; PW-OCP performs best near γ⋆=πmin/T≈1.58×10^-3, and both methods remain stable nearby.The setting uses K=5 and T=20,000, with mean ±95% confidence intervals over 20 seeds.Source: Figure 6 · p. 29
  • Figure 4 contrasts marginal logged coverage with action-conditional gaps, while Figure 7 shows PW-OCP and DR-OCP among the best non-oracle methods across three real-data benchmarks.Figure 7’s absolute gaps are smaller than in synthetic stress tests because several baselines already have near-nominal logged coverage.Source: Figure 4 · p. 28, Figure 7 · p. 29
Loading 2609.30811v1…