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
Poster: file
Nathan Huntley
Dept of Mathematical Sciences
Durham University
Science Laboratories
South Rd.
Durham
DH1 3LE
Matthias Troffaes
Department of Mathematical Sciences
Durham University
Science Laboratories, South Road
Durham, DH1 3LE
| Nathan Huntley | nathan.huntley@durham.ac.uk | |
| Matthias Troffaes | matthias.troffaes@gmail.com |
Send any remarks to isipta11@uibk.ac.at.