I think in general, the only way to solve these problems optimally is to build a full decision tree, and then apply backward induction. The reason is that at every decision point, the expected utility of a choice depends on what you do after that, so you need to first figure out what is the optimal strategy for the subtree rooted at that choice.
Sometimes, there are mathematical shortcuts that you can use to solve the problem faster. (Since the decision tree is exponential in size, doing backward induction may be infeasible.) I don’t know if there is one here, but the decision tree seems to be small enough (at most size 9^12) that it can be solved by brute force using a computer. Apparently there are existing tools for doing this (which I found using Google) but I’m not really familiar with them.
I don’t think the decision tree is really exponential growth because the order of operations doesn’t matter. It only matters how many red and black cards you’ve gotten, not their order; it only matters how many treatments, not their order. Different orders involved different beliefs in the middle, but they don’t involve different beliefs at the end, do they?
Yes, I think you’re right. Because the order of observations doesn’t influence posterior probabilities in this game, we can simplify the backward induction computation to take O(n^5) time instead of exponential. (n^5 because 5 variables, each less than n, are sufficient to describe a history: number of red and black cards, number of each type of treatment). This is still too long to do by hand, but easy with a computer.
I think three variables are sufficient: The excess of red over black cards, and the amount of damage done (by the combination of waiting and side effects) to each of (fungus-sufferers, allergy-sufferers).
According to my present implementation (which likely has bugs), the total number of triples that one needs to investigate before obtaining proof in the form of “if they weren’t X, they″d be dead by now” is 906.
I think in general, the only way to solve these problems optimally is to build a full decision tree, and then apply backward induction. The reason is that at every decision point, the expected utility of a choice depends on what you do after that, so you need to first figure out what is the optimal strategy for the subtree rooted at that choice.
Sometimes, there are mathematical shortcuts that you can use to solve the problem faster. (Since the decision tree is exponential in size, doing backward induction may be infeasible.) I don’t know if there is one here, but the decision tree seems to be small enough (at most size 9^12) that it can be solved by brute force using a computer. Apparently there are existing tools for doing this (which I found using Google) but I’m not really familiar with them.
I don’t think the decision tree is really exponential growth because the order of operations doesn’t matter. It only matters how many red and black cards you’ve gotten, not their order; it only matters how many treatments, not their order. Different orders involved different beliefs in the middle, but they don’t involve different beliefs at the end, do they?
Yes, I think you’re right. Because the order of observations doesn’t influence posterior probabilities in this game, we can simplify the backward induction computation to take O(n^5) time instead of exponential. (n^5 because 5 variables, each less than n, are sufficient to describe a history: number of red and black cards, number of each type of treatment). This is still too long to do by hand, but easy with a computer.
I think three variables are sufficient: The excess of red over black cards, and the amount of damage done (by the combination of waiting and side effects) to each of (fungus-sufferers, allergy-sufferers).
According to my present implementation (which likely has bugs), the total number of triples that one needs to investigate before obtaining proof in the form of “if they weren’t X, they″d be dead by now” is 906.