

![0_image_0.png](0_image_0.png)

Figure 9: A two-step decision tree. Rectangles correspond to the decision nodes (moves of the decision-maker) and circles to chance nodes (moves of the environment). Black rectangles represent leaves of the tree.  The reward for a specific path is associated with every leaf of the tree.  Decision nodes are associated with information states obtained by following action and observation choices along the path from the root of the tree. For example, b 1 , is a belief state obtained by performing action a 1 from the initial belief state b and observing observation o 1 .

## 2.7  Forward (Decision Tree) Methods

The methods discussed so far assume no prior knowledge of the initial belief state and treat all belief states as equally likely. However, if the initial state is known and fixed, methods can often be modified to take advantage of this fact. For example, for the finite-horizon problem, only a finite number of belief states can be reaed from a given initial state.  In this case it is very often easier to enumerate all possible histories (sequences of actions and observations) and represent the problem using stochastic decision trees (Raiffa, 1970). An example of a two-step decision tree is shown in Figure 9.

The algorithm for solving the stochastic decision tree basically mimics value-function updates, but is restricted only to situations that can be reached from the initial belief state.

The key difficulty here is that the number of all possible trajectories grows exponentially with the horizon of interest.

## 2.7.1 Combining Dynamic-Programming And Decision-Tree Techniques

To solve a POMDP for a fixed initial belief state, we can apply two strategies: one constructs the decision tree first and then solves it, the other solves the problem in a backward fashion via dynamic programming. Unfortunately, both these techniques are inefficient, one suffering from exponential growth in the decision tree size, the other from super-exponential growth in the value function complexity. However, the two techniques can be combined in