Preliminary Decision Tree MDP Plot

This is a plot of the results of the decision tree MDP on the Simple Graph Problem(8 arc, 6 nodes), where the arc costs can take the value 0 or 2 with equal probability. The decision tree MDP Algorithm is as follows:
1. Generate initial decision tree with computational cost set to zero.
2. Compress the decision tree into a quality tree which is used by the MDP.
3. From the quality tree get transition statistics and generate an metaplan.
4. From the metaplan, generatea new decision tree.
5. If no over max iteratations, goto 1.


There is instability in the generation the decision trees, where the expected value of the metaplan generated from successive iterations is not monotonically improving. This instability is currently not well understood. But in order to obtain some preliminary results, for each epsilon value, I ran the above algorithm 30 times, and recorded the result which yielded the minimum cost policy. The plot is given here.