We generalise de Cooman and Troffaes's sufficient condition for dynamic programming to work for deterministic discrete-time systems. To do so, we use the general framework developed by Huntley and Troffaes, for decision trees with arbitrary rewards and arbitrary choice functions. Whence, we allow deterministic discrete-time systems with arbitrary rewards and an arbitrary composition operator on rewards. We show that the principle of optimality reduces to two much simpler conditions on the choice function. We establish necessary and sufficient conditions on choice functions for deterministic discrete-time systems to be solvable by backward induction, that is, for dynamic programming to work. Finally, we also discuss subtree perfectness---which is a stronger form of dynamic consistency---for these systems, and show that, in general, decision criteria from imprecise probability theory violate it, even though dynamic programming may work.
The paper is available in the following formats:
Plenary talk: file
Dept of Mathematical Sciences
Department of Mathematical Sciences
Science Laboratories, South Road
Durham, DH1 3LE
Send any remarks to email@example.com.