  We introduce Bellman Conformal Inference (BCI), a framework that wraps around
any time series forecasting models and provides approximately calibrated
prediction intervals. Unlike 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. We find empirically that BCI avoids uninformative
intervals that have infinite lengths and generates substantially shorter
prediction intervals in multiple applications when compared with existing
methods.
