arXiv:2402.05203v3 Announce Type: replace-cross Abstract: We introduce Bellman Conformal Inference (BCI), a framework that wraps around any time series forecasting models and provides calibrated prediction intervals. Unlike the existing methods, BCI is able to leverage multi-step ahead forecasts and explicitly optimize the average interval lengths by solving a one-dimensional stochastic control problem (SCP) at each time step. In particular, we use the dynamic programming algorithm to find the optimal policy for the SCP. We prove that BCI achieves long-term coverage under arbitrary distribution shifts and temporal dependence, even with poor multi-step ahead forecasts. When the raw forecast intervals are approximately calibrated, we prove that BCI is near optimal for its surrogate model predictive control problem. We find empirically that BCI avoids uninformative intervals with infinite lengths under our main experimental configuration and generates substantially shorter prediction intervals when the raw forecast intervals are poorly calibrated.