Coverage Cliffs in Off-Policy Quantile Certification

Before a new policy replaces a deployed one, we often want a certificate, computed from logged episodes, that it is better. We ask how many episodes such a certificate needs when the logging policy is known but history-dependent, and the error probability must stay below $δ$ in every environment consistent with the logs. The answer is an exponent $K^\star$: the smallest KL divergence from the logged law to a law with the same logged action probabilities under which the target does not improve. No sound certifier stops in fewer than $\log(1/δ)/K^\star$ expected episodes, at any $δ$, and whenever $0<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $δ\to0$. Coverage, computed by one backward induction, decides whether certification is impossible ($K^\star=0$), possible at a finite rate, or possible in a constant number of episodes ($K^\star=\infty$). By convex duality, the optimal certificate bets on the importance-weighted advantage and also places fair bets on the logged actions, so doubly robust control variates act as hedges rather than estimators. As a consequence, no choice of off-policy estimator changes $K^\star$, a coverage ceiling explains the curse of memory, and structural assumptions can be priced in exponent units. A cushion certifier extends the approach to trees too large to enumerate. In experiments the plug-in's median stopping time is 1.13-1.43x the lower bound on memory tasks, 1.13-1.51x on Tiger ($H\le5$) and 1.17-1.64x on random trees. The best scalar betting baselines need up to 2.65x (memory) and 4.1x (Tiger) the plug-in's episodes; only on a few shallow random trees is a doubly robust bet faster, by at most 18%.

Stochastic bandit algorithms are usually analyzed under a mean-reward criterion, yet many problems favor arms with strong upper-tail performance, which we study herein. For a fixed miscoverage level $α$, the natural upper-tail target of arm $j$ is the upper endpoint $F_j^{-1}(1-α/2)$ of a central prediction interval. This target can rank arms differently from their means, creating a central mismatch with the classical bandit objective. To this end, we propose ACP-UCB1, a conformal-style policy that combines an adaptive conformal estimate of the upper endpoint with a UCB-type optimism bonus. The technical challenge is that the conformity scores used by ACP-UCB1 are recomputed from evolving empirical quantile estimates and evaluated at an adaptive level. We control this endpoint through reward-quantile concentration, a perturbation argument for recomputed score quantiles, and deterministic localization of the adaptive level. ACP-UCB1 achieves logarithmic upper-quantile regret with per-arm contribution $O(\nicefrac{\log n}{Δ_j^{\mathrm{ACP}}})$. We also provide metric-specific regret decompositions comparing ACP-UCB1 with UCB1 and use numerical experiments to validate performance and improvement.

Critical sequential decisions are rarely single-timescale: a strategic decision causally shapes the context in which every subsequent tactical choice is made; standard bandit and reinforcement-learning theory does not capture this causal coupling between timescales. We formalise the problem class as Nested Contextual Causal Bandits (NCCBs), a hierarchical SCM where each level's action sets the next level's context distribution, and propose Nested Causal Thompson Sampling (NCTS), which draws one mechanism-factorised belief per episode and acts recursively under it. Our main theoretical result is a causal PAC-Bayesian excess-risk bound that certifies any candidate deployment policy from historic data alone, off-policy and anytime, answering the deployment question: can we trust this agent here, and at what risk? Experiments on a hierarchical SCM show that, against a matched RFF-GP joint regression on the same function class, the factorised SCM-mechanism posterior transfers significantly better zero-shot under exogenous distribution shifts, the recursive meta-to-inner commit significantly dominates the joint-commit alternative in distribution, and the certificate significantly contracts as offline data accumulates. Combining these results, we establish progressive certified handover, a safe-deployment method: each timescale flips from a legacy controller to NCTS when gains can be certified, independently of the others.