# Conformal Sequential Decision Making With Cost and Sublinear Policy Regret Guarantees

arXiv: https://arxiv.org/abs/2610.15011 · HTML: https://mlsanity.com/paper/2610.15011/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 19 references that are in the map.
- First posted on arXiv 10 Oct 2026.

## Builds on (most cited first, 15 of 15)

- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Safe Planning in Dynamic Environments using Conformal Prediction](https://mlsanity.com/paper/2210.10254/) (2022)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions](https://mlsanity.com/paper/2310.05921/) (2023)
- [Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents](https://mlsanity.com/paper/2502.02561/) (2025)
- [Forking Uncertainties: Reliable Prediction and Model Predictive Control with Sequence Models via Conformal Risk Control](https://mlsanity.com/paper/2310.10299/) (2023)
- [Localized Adaptive Risk Control](https://mlsanity.com/paper/2405.07976/) (2024)
- [Conformal Quantitative Predictive Monitoring of STL Requirements for Stochastic Processes](https://mlsanity.com/paper/2211.02375/) (2022)
- [Conformal Calibration: Ensuring the Reliability of Black-Box AI in Wireless Systems](https://mlsanity.com/paper/2504.09310/) (2025)
- [Prediction-Powered Communication with Distortion Guarantees](https://mlsanity.com/paper/2509.24373/) (2025)
- [Online Conformal Compression for Zero-Delay Communication with Distortion Guarantees](https://mlsanity.com/paper/2503.08340/) (2025)
- [Conformal Risk-Averse Decision Making with Action Conditional Guarantee](https://mlsanity.com/paper/2606.05551/) (2026)
- [Risk-Averse Decision Making with Multi-Level Reliability Guarantees](https://mlsanity.com/paper/2609.11524/) (2026)

## Abstract (arXiv)

Automated decision makers, such as AI agents that control robots or network devices, must often satisfy hard cost constraints while maintaining competitive performance. In such settings, a cost measure, such as a safety violation rate, energy consumption, or a distortion level, must stay within a given budget in every episode of operation. Furthermore, a cumulative reward metric, accounting for per-step performance, must stay close to the reward of a meaningful reference policy. We formulate this setup as an episodic sequential decision problem in which the state sequence is arbitrary, and the reward and cost may depend on past actions within the same episode. We propose the online conformal episodic agent (OCEA), a policy that selects one candidate action per episode using a regret-controlled algorithm, and switches to a zero-cost action when the remaining budget cannot absorb the maximum cost of one more round. We prove that OCEA satisfies per-episode cost constraints for every state sequence and for every realization of its internal randomness, while achieving a sublinear expected policy regret with respect to the best action sequence in hindsight from a comparator class satisfying the same per-episode cost constraints. We apply OCEA to risk-averse control and online compression with distortion guarantees.