Decision Making with Dynamic Uncertain Events

When to make a decision is a key question in decision making problems characterized by uncertainty. In this paper we deal with decision making in environments where information ar-rives dynamically. We address the tradeoff between waiting and stopping strategies. On the one hand, waiting to obtain more information reduces uncertainty, but it comes with a cost. Stopping and making a decision based on an expected utility reduces the cost of waiting, but the decision is based on uncertain information. We propose an optimal algorithm and two approximation al-gorithms. We prove that one approximation is optimistic- waits at least as long as the optimal algorithm, while the other is pessimistic- stops not later than the optimal algorithm. We evaluate our algorithms theoretically and empirically and show that the quality of the decision in both ap-proximations is near-optimal and much faster than the optimal algorithm. Also, we can conclude from the experiments that the cost function is a key factor to chose the most effective algorithm. 1