Golden Roof ISIPTA'11 home Nordkette mountain range

Nathan Huntley, Matthias Troffaes

Dynamic Programming and Subtree Perfectness for Deterministic Discrete-Time Systems with Uncertain Rewards


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.


optimal control, dynamic programming, deterministic discrete-time systems, backward induction, subtree perfectness, choice function

Download area

The paper is available in the following formats:

Plenary talk: file

Poster: file

Authors’ addresses

Nathan Huntley
Dept of Mathematical Sciences
Durham University
Science Laboratories
South Rd.

Matthias Troffaes
Department of Mathematical Sciences
Durham University
Science Laboratories, South Road
Durham, DH1 3LE

E-mail addresses

Nathan Huntley
Matthias Troffaes

Send any remarks to