Conformal Sequential Decision Making With Cost and Sublinear Policy Regret Guarantees

Abstract

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.