UCLA

When making decisions under uncertainty, the optimal choices are often difficult to discern, especially if not enough information has been gathered. Two key questions in this regard relate to whether one should stop the information gathering process and commit to a decision (stopping criterion), and if not, what information to gather next (selection criterion). The proposed thesis is concerned with addressing this problem in light of a new advance, known as the Same--Decision Probability (SDP), which is the probability that we would make the same decision had we known what we currently do not know. In this thesis, we show how the SDP can be used to be an effective stopping criterion, and compare it to traditional criteria to demonstrate how it provides a fresh perspective in decision making under uncertainty. Additionally, we develop the first exact algorithm to compute the SDP so that it may be used as a stopping criterion. We demonstrate the effectiveness of these algorithms on real and synthetic networks, and show that our proposed stopping criterion can lead to an early stopping of information gathering. Furthermore, we demonstrate that the SDP can be used as a selection criterion. In particular, since there are many criteria for measuring the value of information, each based on optimizing different objectives, we propose a new SDP-based criterion for measuring the value of information --- this criterion values information that leads to robust decisions (i.e., ones that are unlikely to change due to new information). We develop the first algorithm to optimize the value of information, given the SDP as the reward criterion, and show empirical results that prove the utility of this novel criterion. We further answer several questions regarding the computational complexity of the SDP, which is known to be PP^PP-complete. Finally, we present results of applying the SDP as an information gathering criterion in practical problems including tutoring systems (do we need to ask more questions?) and machine learning (do we have enough data?).