CS Paper Radar

Occupancy-based Quantile Risk Control

Zihao Shi, Huajun Xi, Bingyi Jing, Hongxin Wei

cs.LG stat.ML ·submitted 2026-09-02 19:32 UTC · v1
theory

Abstract

Conformal risk control is an emerging framework for the safe deployment of machine learning models with finite-sample guarantees. To accommodate a broader class of risk notions, quantile risk control extends this framework to quantile-based risk measures. However, existing methods either suffer from excessive conservatism or lack rigorous finite-sample guarantees. To address these limitations, we introduce Occupancy-based Quantile Risk Control (OQRC), a novel method that provides tight risk control bounds with finite-sample validity. Our key idea is to formulate risk control as a finite-occupancy problem by partitioning the loss space with the ordered calibration losses. Specifically, we estimate the distribution of test losses across the resulting bins and upper-bound the risk by the maximum loss attained within each bin. We then select the parameter $λ$ such that this upper bound does not exceed a predefined threshold $α$ with high probability $1-δ$. Theoretically, we establish a finite-sample guarantee showing that OQRC yields tight risk control bounds that converge to the optimal bounds at a provable rate of $\mathcal{O}_ p(n^{-1/2})$. Extensive experiments demonstrate the effectiveness of our method, reducing the risk gap by up to 78.64\% on common benchmarks.

Closest papers

Nearest neighbours by meaning across the whole index.

High Probability Risk Control for Online Policy Learning

cs.LG ·2026-11-09 ·Yihong Guo, Drew Prinster, Suchi Saria, Anqi Liu
publishedbenchmarktheory similarity 0.65
Abstract

We study risk control for online policy learning, where an agent adaptively collects data and aims to learn a new policy whose risk stays below a tolerance threshold at every round with high probability. Such policy updates and data collection induce feedback covariate shift (FCS): observed data depend on history through evolving policies and the data-collection process. FCS brings two substantive problems for risk control: 1) efficient risk evaluation for each candidate policy and 2) valid policy selection with high-probability risk control. To address these, we propose a permutation-based weighted risk evaluator with weights efficiently approximated by the Sinkhorn algorithm and select policies whose estimated risk upper confidence bounds (UCB) fall below the target threshold, with the UCB obtained through a proposed Gaussian bootstrap method. Theoretically, we prove that our risk evaluator has a no-larger variance upper bound than that of the standard importance-weighted evaluator. Our policy control method also yields an asymptotically valid simultaneous risk bound and provides asymptotic high-probability risk control for the selected policy. Empirically, we evaluate our method on the online contextual bandit problem, safe question answering benchmark, and Medical Claim Filtering tasks. Our method maintains the target risk level, achieves lower risk than baseline methods, has lower variance in risk estimation, and achieves reliable policy selection with high-probability risk control. Further ablation studies support our theoretical claims.

0.20

Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent

cs.LG math.NA ·2026-09-11 ·Jamie Haddock, Anna Ma, Elizaveta Rebrova
theory similarity 0.63
Abstract

We study loss-based filtering for finite-sum optimization with a subset of corrupted component functions whose gradients may be highly unreliable. Motivated by minimum-loss-based SGD (min-$k$-loss) and quantile-based methods for corrupted linear systems, we propose and analyze a general loss-filtering framework -- Quantile-\(k\)-Loss SGD (Q\(k\)L-SGD) -- that samples \(k\) component losses at each iteration and updates using an index chosen uniformly from the lower empirical \(q\)-quantile. We prove linear convergence of this family of methods under standard convexity assumptions, requiring the sample size to scale with the number of corruptions and a subset strong-convexity threshold. For the cases when large enough sampling is impossible or undesirable, we give a complementary small-sample probabilistic analysis that covers any sample size $k$ and the convergence behavior depends on the probability of selecting an outlier and on the curvature of the selected good step. Experiments on polynomial regression, regularized logistic regression, and regularized hinge loss show that intermediate quantiles often outperform both standard SGD and min-\(k\)-loss SGD. In particular, min-\(k\) often stalls by repeatedly selecting nearly solved components, while intermediate quantiles retain robustness and produce more informative updates.

0.50

Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift

cs.LG math.STstat.ML ·2026-09-21 ·Rustam Isaev, Anton Conrad, Denis Belomestny, Eric Moulines, Sergey Samsonov
theory similarity 0.63
Abstract · 65 pages, 3 figures

In this paper, we study nonasymptotic $L^p$ error bounds for interval length and conditional coverage in split conformalized quantile regression (CQR). Our bounds rely on local regularity conditions and accuracy guarantees for the estimated quantiles. We further instantiate our bounds for quantile regression with sparse ReLU neural networks. We also consider covariate shift, where the calibration and test covariates have different distributions, and derive nonasymptotic bounds for this setting. We obtain matching minimax upper and lower bounds in expectation for two constructed fixed-score calibration benchmarks under known covariate shift. The bounds match for every $p\in[1,\infty]$ in the scalar problem and for finite $p$ in the $K$-threshold problem; for the latter, a high-probability minimax lower bound holds for every $p\in[1,\infty]$.

0.60

Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

cs.LG math.OC ·2026-08-23 ·Mohammad Alipour-Vaezi, Huaiyang Zhong, Sajad Khodadadian
theory similarity 0.63
Abstract

Reinforcement Learning (RL) has achieved tremendous success in recent years. However, the classical foundations of RL do not account for the risk sensitivity of the objective function, which is critical in various fields, including healthcare, finance, etc. A popular approach to incorporate risk sensitivity is to optimize a specific quantile of the cumulative reward distribution. However, exact quantile objectives are non-smooth and can change abruptly under small perturbations of the return distribution, making them difficult to optimize reliably when the transition model must be learned from data. Motivated by this instability, we develop UCB-BQRL, a model-based optimistic learning algorithm that maintains confidence sets for the transition kernel and plans using a lower-buffered quantile criterion. The buffered criterion smooths the exact quantile objective by averaging nearby lower quantiles, thereby improving stability under transition-estimation error. To compute the buffered-quantile policy at each episode, we introduce EVI-BQ, an exact dynamic-programming procedure. We establish a high-probability regret bound for UCB-BQRL, which up to logarithmic factors scales as $\mathcal{O}(\mathrm{e}^{τ/ρ_τ}+H^2\sqrt{SAT})$, where $ρ_τ$ is denoted as the root-level left-plateau threshold, which is a problem-dependent constant. Further, we establish an information-theoretic lower bound of $Ω(H/ρ_τ\sqrt{AT})$ for the regret of any algorithm dealing with a quantile objective function. Finally, we prove that the exact point-quantile evaluation and exact lower-buffered quantile evaluation are PP-hard under polynomial-time Turing reductions, even for a fixed policy in a two-state, one-action finite-horizon MDP.

0.35

Preference-Augmented Distributional Reinforcement Learning for Risk-Sensitive Navigation

cs.RO cs.LG ·2026-10-13 ·Zhaofan Zhang, Yue Chang, Rufeng Chen, Hechang Chen, Sihong Xie +1 more
hot direction similarity 0.63
Abstract

Ensuring safe and reliable navigation under diverse sources of uncertainty remains a central challenge for autonomous systems. Within distributional reinforcement learning (DistRL), Implicit Quantile Networks (IQN) have attracted interest for navigation under uncertainty because they enable risk adaptation through flexible quantile sampling. Existing approaches, however, typically use a fixed or randomly sampled Conditional Value-at-Risk (CVaR) level during training and adjust the risk level during deployment using hand-tuned hyperparameters or external sensor signals. This scalar-CVaR formulation confines learning to a narrow family of tail-risk preferences, creating a mismatch between training-time preference exposure and deployment-time risk adjustment. We instead represent variations in risk preference as shifts in quantile-weight distributions and expose the agent to diverse preferences through preference-guided exploration. At deployment, we optimize against the worst-case preference distribution to derive a conservative policy that accounts for multiple risk profiles. This reduces hyperparameter tuning and reliance on limited sensor signals under partial observability. Experiments across simulated environments and vehicle platforms show that our method reduces collisions while improving task success.

0.26

Available Guardrails: Certifying Selective Prediction across ML Systems

cs.LG ·2026-09-18 ·Parivesh Priye, Yufeng Wang, Haibin Ling, Michael Chaykowsky
similarity 0.62
Abstract

A selective predictor acts as a safety gate: it returns an output only when the prediction appears sufficiently trustworthy. Deployments increasingly require this reliability to be certified at a target precision for every reporting unit of interest, such as a tool, policy label, or patient subgroup. The main difficulty is often not whether a granted certificate is valid, but whether finite calibration data can produce one at all. As the gate becomes safer or more fine-grained, some units may receive too little evidence to certify. We make this notion of availability computable through classical exact-binomial inversion and formulate reporting-partition selection, under a fixed group order, as a dynamic program that exposes the trade-off among safety, granularity, and served traffic. The resulting frontier reveals a large population opportunity that finite-sample estimation nearly erases: a truth-informed planner gains $0.157$ mean coverage over support balancing, whereas a naive estimator recovers only $0.005$, making recovery from finite data the central challenge. Constructing candidate partitions on one planning split and selecting among them on another recovers part of this gap, improving mean coverage over support balancing by $0.060$, with the direction reproduced in $59$ of $60$ model effects across three intent-routing datasets and two architectures. A complementary validity-preserving lever, reallocating the familywise error budget across reporting units, recovers additional coverage both with population quantities and noisy estimates. The same frontier recurs, with predictor-specific ceilings, across LLM tool-calling, content moderation, lesion classification, and recommendation. Certified availability is therefore a plannable deployment resource that determines when a safety gate can be certified, at what granularity, and over how much traffic.

0.21

Selected-Risk Calibration for Feasibility at Returned Decisions

cs.LG stat.ML ·2026-11-05 ·Raghav Thind, Youran Sun, Ling Liang, Haizhao Yang
similarity 0.61
Abstract · 20 pages, 3 figures

When an optimization problem uses a surrogate constraint, a decision that is feasible for the surrogate need not be feasible for the true constraint. We propose Selected-Risk Calibration (SRC), a framework that calibrates a learned constraint against the optimizer's returned decisions for objectives drawn from a given distribution. SRC guarantees that, with probability at least $1-δ$, every margin it certifies on held-out objectives has selected risk, the probability that the returned decision is infeasible, of at most $γ$. We also show that the random-input coverage guarantee of split conformal prediction does not bound the selected risk, and that likelihood-ratio reweighting for feedback covariate shift does not apply when the learned constraint is active at the returned decision. Our experiments show that a conformal margin covering about $90\%$ of random inputs covered as few as $17\%$ of the returned decisions, and every certified margin had a violation rate below its target on unseen objectives. Moreover, at equal cost, SRC's correction had fewer or equal infeasible solutions to the baselines in 57 of 62 comparisons. The SRC framework applies to any setting in which a surrogate model chooses a decision whose feasibility can be verified for a sample of instances.

0.23

Provably Efficient Risk-Sensitive Offline Reinforcement Learning via Optimized Certainty Equivalents

cs.LG cs.AImath.OCstat.ML ·2026-10-15 ·Hanzhen Wang, Boxiang Lyu, Zhongxiang Dai, Siyang Gao, Dake Zhang +1 more
similarity 0.61
Abstract

Risk-sensitive reinforcement learning (RL) addresses decision-making under uncertainty and adverse outcomes. Learning risk-sensitive policies from fixed datasets is important when additional interaction with the environment is costly. Existing work on risk-sensitive RL focuses on online settings or specific risk measures, leaving a general theoretical understanding of its offline setting underdeveloped. In this work, we investigate efficient offline risk-sensitive RL using the optimized certainty equivalent (OCE), a general class of risk measures. We consider two formulations: dynamic-OCE RL, which applies OCE recursively at each step, and static-OCE RL, which applies a single OCE to the cumulative rewards. Under the tabular setting, we develop pessimistic value-iteration algorithms for both formulations and establish tight sublinear suboptimality bounds, explicitly capturing how risk sensitivity, encoded by utility functions, affects learning difficulty. Moreover, we establish minimax suboptimality lower bounds to characterize the problem's fundamental limits. To handle large state spaces, we further develop pessimistic least-squares value-iteration algorithms that incorporate the general OCE risk criterion into linear function approximation. We establish utility-dependent sublinear guarantees with explicit dependence on the feature dimension $d$. To our knowledge, we provide the first offline algorithms along with the first upper and lower suboptimality bounds for both dynamic- and static-OCE RL.

0.15