Sequential Decision Making For Choice Functions On Gambles

Abstract

Choice functions on gambles (uncertain rewards) provide a framework for studying diverse preference and uncertainty models. For single decisions, applying a choice function is straightforward. In sequential problems, where the subject has multiple decision points, it is less easy. One possibility, called a normal form solution, is to list all available strategies (specifications of acts to take in all eventualities). This reduces the problem to a single choice between gambles.

We primarily investigate three appealing behaviours of these solutions. The first, subtree perfectness, requires that the solution of a sequential problem, when restricted to a sub-problem, yields the solution to that sub-problem. The second, backward induction, requires that the solution of the problem can be found by working backwards from the final stage of the problem, removing everything judged non-optimal at any stage. The third, locality, applies only to special problems such as Markov decision processes, and requires that the optimal choice at each stage (considered separately from the rest of the problem) forms an optimal strategy.

For these behaviours, we find necessary and sufficient conditions on the choice function. Showing that these hold is much easier than proving the behaviour from first principles. It also leads to answers to related questions, such as the relationship between the normal form and another popular form of solution, the extensive form. To demonstrate how these properties can be checked for particular choice functions, and how the theory can be easily extended to special cases, we investigate common choice functions from the theory of coherent lower previsions.