efficient monte carlo decision tree solution in dynamic purchasing environments
This paper considers the problem of making decisions in a dynamic environment where one of possibly many bundles of items must be purchased and quotes for items open and close over time. Probability measures on item prices are used when exact prices are not yet known. We show that expected utility estimation can be improved by considering how future information can affect the purchasing agent's behaviour. An efficient Monte Carlo simulation method is presented that determines the expected utility of an option in our decision tree, referred to as a QR -tree, where the number of simulations needed is linear in the size of the tree. In our experiments simulating a purchase agent in a specific market, the expected utility was estimated more than 50 times more accurately than a greedy method that always pursues the bundle with the current highest expected utility.
monte carlo decision tree expected utility theory bundle purchasing decision analysis