Semantic verification of dynamic programming.

We prove that the generic framework for specifying and solving finite-horizon, monadic sequential decision problems proposed in (Botta et al.,2017) is semantically correct. By semantically correct we mean that, for a problem specification $P$ and for any initial state $x$ compatible with $P$, the verified optimal policies obtained with the framework maximize the $P$-measure of the $P$-sums of the $P$-rewards along all the possible trajectories rooted in $x$. In short, we prove that, given $P$, the verified computations encoded in the framework are the correct computations to do. The main theorem is formulated as an equivalence between two value functions: the first lies at the core of dynamic programming as originally formulated in (Bellman,1957) and formalized by Botta et al. in Idris (Brady,2017), and the second is a specification. The equivalence requires the two value functions to be extensionally equal. Further, we identify and discuss three requirements that measures of uncertainty have to fulfill for the main theorem to hold. These turn out to be rather natural conditions that the expected-value measure of stochastic uncertainty fulfills. The formal proof of the main theorem crucially relies on a principle of preservation of extensional equality for functors. We formulate and prove the semantic correctness of dynamic programming as an extension of the Botta et al. Idris framework. However, the theory can easily be implemented in Coq or Agda.