If you have an NP oracle, you can first ask it “is there an action with EU >= k” for some medium k value, then binary search until you find the highest k value (within epsilon) for which there is an action with EU >= k, assuming that EU can be computed in polynomial time. I agree that you can’t prove that a particular sequence of actions has the highest possible EU.
“what move should open with in reversi” would be considered as an admissible decision-theory problem by many people. Or in other words: Your argument that EU maximization is in NP only holds for utility functions that permit computation in P of expected utility given your actions. That’s not quite true in the real world.
Thanks for the links, those are relevant.
If you have an NP oracle, you can first ask it “is there an action with EU >= k” for some medium k value, then binary search until you find the highest k value (within epsilon) for which there is an action with EU >= k, assuming that EU can be computed in polynomial time. I agree that you can’t prove that a particular sequence of actions has the highest possible EU.
“what move should open with in reversi” would be considered as an admissible decision-theory problem by many people. Or in other words: Your argument that EU maximization is in NP only holds for utility functions that permit computation in P of expected utility given your actions. That’s not quite true in the real world.