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.
Figures & tables
Figure 1: Comparison across breast cancer diagnosis, stock investment, and SafetyBench. We report risk and empirical risk satisfaction on two rows; each column corresponds to one task. See Figure 5 for reward. Risk for breast cancer, stock investment, and SafetyBench is measured by FNR, the probability of selecting the worst investment, and the error rate among answered questions, respectively. Reward represents task-specific utility: accuracy for breast cancer, investment income for stock investment, and cumulative correct answers for SafetyBench. Results are based on 500 runs for breast cancer and stock investment, and 200 calibration histories for SafetyBench. Breast cancer uses α=0.04 and δ=0.1 . Stock investment uses α=0.1 and δ=0.1 . SafetyBench uses α=0.1 and δ=0.2 for RCL-HP. RCL-E achieves expected risk control in the monotonic risk setting (breast cancer), and RCL-HP achieves empirical high-probability control across the three tasks and outperforms baselines.
Figure 2: Comparison of medical QA across target risk levels α . Risk is measured by mean held-out false discovery proportion (FDP), and reward by supported-claim recall. Results are based on 1,000 random calibration/test splits. The satisfaction rate is the fraction of splits with mean held-out FDP at most α . Both LTT and RCL-HP use δ=0.2 .
Figure 3: (a)-(b) Experiment on Breast Cancer Diagnosis. Our risk evaluator exhibits lower variance and bias than the importance-weighted method in O-CRC. (c) We compare against the multi-step permutation weight estimator. Our full-assignment permutation approximation achieves lower risk.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Validation accuracy at T=0.8 on 1,000 SafetyBench questions. Qwen2.5-1.5B-Instruct is fine-tuned with LoRA (rank 64) on 4,409 questions for five epochs. Checkpoints 1–11 correspond to optimizer steps 0,69,…,690 , respectively, with checkpoint 1 denoting the pretrained model. We use the checkpoint sequence as the policy sequence.
Experiment
Effect of λ
Risk metric
Breast cancer
Probability of selecting malignancy
False negative rate
Stock
Probability of selecting each asset
Probability of selecting the worst-performing asset
SafetyBench
Deployment distribution over answers and abstention
Error rate among answered questions
Medical QA
Which claims are retained in fixed responses
Expected false discovery proportion of retained claims
Appendix
Table 1: Control parameters and risk metrics.
Experiment
Shift type
Monotonic risk function?
Control type
Breast cancer
Feedback covariate shift
Yes
Policy control
Stock
Feedback covariate shift
No
Policy control
SafetyBench
Non-adaptive policy-induced covariate shift
No
Policy control
Medical QA
No distribution shift
No
Risk control
Appendix
Table 2: Distribution shifts and control settings.
Figure 5: Reward comparisons across the three experiments.
Figure 6: Risk control probability under different 1−δ quantile/confidence. The baselines remain close to perfect risk satisfaction even for large δ , indicating substantial conservativeness rather than adaptively adjusting the degree of conservativeness to the target high-probability risk control level.
Figure 7: SafetyBench results with warmup calibration sizes m0∈{512,1024,4096} . LTT ignores policy shift. The target risk is α=0.1 , with δ=0.2 for HP calibration. Repeat 200 times. LTT may fail as it ignores the shift. Also, when the warmup size is larger, the failure is more significant even though it is more conservative.
Figure 8: Empirical P(ℓ<ℓ^+q1−δ) under different δ . The P(ℓ<ℓ^+q1−δ) of our method shows that the Gaussian bootstrap method achieves 1−δ coverage, while for UCB P(ℓ<ℓ^+q1−δ)=1 for all δ . These results suggest that the bootstrap correction provides a more adaptive uncertainty estimate for FCS data, while the UCB method can be overly conservative no matter how we choose δ .
Adaptive exact permutation weights versus Sinkhorn
0.00132
Appendix
Table 4: Adaptive exact (retrain policy sequence for different permutations) versus Sinkhorn.
Dataset / setting
Satisfaction rate
Mean ΔJ
Mean ΔQ
Breast Cancer
97.20%
4.595
2.854
Appendix
Table 5: Satisfaction rates and the mean log range of the Q and J .
Figure 9: VarGTVarEstimated . The ratio is close to 1 as the number of data increases.
Figure 10: Empirical diagnostics for the three conclusions of Lemma F.7 , F.9 , F.11 . Results use the Sinkhorn estimator under Breast Cancer configuration B, with 200 fixed empirical contexts, three frozen candidate policies, and 2,500 independent histories.
We study risk-aware offline policy learning, aiming to learn a decision rule from logged data that is optimal under general risk criteria. This problem is crucial in high-stakes domains where online interaction is infeasible and adverse outcomes must be carefully controlled. However, existing literature on offline contextual bandits either centers on expected-reward criteria or restricts risk considerations to policy evaluation instead of optimization. In this work, we propose a unified distributional framework for optimizing Lipschitz-continuous risk functionals, a broad class of risk measures encompassing mean-variance, entropic risk, and conditional value-at-risk, among others. By developing novel empirical concentration inequalities for importance sampling-based distributional estimators, our analysis derives data-dependent suboptimality bounds with an O~(1/n) rate, without relying on restrictive uniform overlap assumptions. This rate is minimax optimal and matches that of risk-neutral offline policy optimization, indicating that optimizing general Lipschitz risk criteria incurs no additional statistical cost relative to the expected-reward.
Predictive models are often deployed through existing decision policies that stakeholders are reluctant to change unless a risk constraint requires intervention. We study risk-controlled post-processing: given a deterministic baseline policy, choose a new policy that maximizes agreement with the baseline subject to a chance constraint on a user-specified loss. At the population level, we show that the optimal policy has a threshold structure: it follows the baseline except on contexts where switching to the oracle fallback policy yields a large reduction in conditional violation risk. At the finite-sample level, given a fitted fallback policy and score, we develop a post-processing algorithm that uses calibration data to select a threshold. Leveraging tools from algorithmic stability and stochastic processes, we show that under regularity conditions, in the i.i.d. setting, the expected excess risk of the post-processed policy is O(logn/n). In the special case when an exact-safe fallback policy is available, the algorithm achieves precise expected risk control under exchangeability. In this setting, we also give high-probability near-optimality guarantees on the post-processed policy. Experiments on a COVID-19 radiograph diagnosis task, an LLM routing problem, and a synthetic multiclass decision task show that targeted post-processing can meet or nearly meet risk budgets while preserving substantially more agreement with the baseline than score-blind random mixing.
Developing efficient function-approximation methods for policy evaluation is a fundamental challenge in risk-aware reinforcement learning. Existing approaches either focus on restrictive classes of risk measures or rely on access to a simulator, limiting their applicability in fully online settings. In this work, we propose computationally efficient online learning algorithms for policy evaluation in Markov decision processes (MDPs) with dynamic utility-based shortfall risk (UBSR) measures under linear function approximation. Specifically, we introduce the UBSR-TD algorithm, establish conditions under which it converges almost surely, and develop several variants designed to accelerate convergence. Our formulation shows that existing policy evaluation algorithms for risk-neutral MDPs can be readily adapted to dynamic UBSR settings by incorporating a loss function into the temporal-difference error. Numerical experiments support our theoretical findings, and an application to a perishable inventory management problem with shelf-life uncertainty demonstrates the practical effectiveness of the proposed methods.
Weikai Wang, Erick Delage
GERAD & Department of Decision Sciences, HEC Montr´eal, Canada