9.5.3 Concerns Regarding the Nondeterministic Model

Given all of the problems with probabilistic modeling, it is tempting to abandon the whole framework and work strictly with the nondeterministic model. This only requires specifying $ \Theta$, without indicating anything about the relative likelihoods of various actions. Therefore, most of the complicated issues presented in Sections 9.5.1 and 9.5.2 vanish. Unfortunately, this advantage comes at a substantial price. Making decisions with worst-case analysis under the nondeterministic model has its own shortcomings. After considering the trade-offs, you can decide which is most appropriate for a particular application of interest.

The first difficulty is to ensure that $ \Theta$ is sufficiently large to cover all possibilities. Consider Formulation 9.6, in which nature acts twice. Through a nature observation action space, $ \Psi(\theta)$, interference is caused in the measurement process. Suppose that $ \Theta =
{\mathbb{R}}$ and $ h(\theta,\psi) = \theta +
\psi$. In this case, $ \Psi(\theta)$ can be interpreted as the measurement error. What is the maximum amount of error that can occur? Perhaps a sonar is measuring the distance from the robot to a wall. Based on the sensor specifications, it may be possible to construct a nice bound on the error. Occasionally, however, the error may be larger than this bound. Sonars sometimes fail to hear the required echo to compute the distance. In this case the reported distance is $ \infty$. Due to reflections, extremely large errors can sometimes occur. Although such errors may be infrequent, if we want guaranteed performance, then large or even infinite errors should be included in $ \Psi(\theta)$. The problem is that worst-case reasoning could always conclude that the sensor is useless by reporting $ \infty$. Any statistically valid information that could be gained from the sensor would be ignored. Under the probabilistic model, it is easy to make $ \Psi(\theta)$ quite large and then assign very small probabilities to larger errors. The problem with nondeterministic uncertainty is that $ \Psi(\theta)$ needs to be smaller to make appropriate decisions; however, theoretically ``guaranteed'' performance may not truly be guaranteed in practice.

Once a nondeterministic model is formulated, the optimal decision rule may produce results that seem absurd for the intended application. The problem is that the DM cannot tolerate any risk. An action is applied only if the result can be guaranteed. The hope of doing better than the worst case is not taken into account. Consider the following example:

Example 9..28 (A Problem with Conservative Decision Making)   Suppose that a friend offers you the choice of either a check for 1000 Euros or 1 Euro in cash. With the check, you must take it to the bank, and there is a small chance that your friend will have insufficient funds in the account. In this case, you will receive nothing. If you select the 1 Euro in cash, then you are guaranteed to earn something.

The following cost matrix reflects the outcomes (ignoring utility theory):

$\displaystyle \begin{tabular}{cc} & $U$  $\Theta$ & \begin{tabular}{\vert c...
... c\vert}\hline 1 & 1000  \hline 1 & 0  \hline \end{tabular} \end{tabular} .$ (9.93)

Using probabilistic analysis, we might conclude that it is best to take the check. Perhaps the friend is even known to be very wealthy and responsible with banking accounts. This information, however, cannot be taken into account in the decision-making process. Using worst-case analysis, the optimal action is to take the 1 Euro in cash. You may not feel too good about it, though. Imagine the regret if you later learn that the account had sufficient funds to cash the check for 1000 Euros. $ \blacksquare$

Thus, it is important to remember the price that one must pay for wanting results that are absolutely guaranteed. The probabilistic model offers the flexibility of incorporating statistical information. Sometimes the probabilistic model can be viewed as a generalization of the nondeterministic model. If it is assumed that nature acts after the robot, then the nature action can take this into account, as incorporated into Formulation 9.4. In the nondeterministic case, $ \Theta(u)$ is specified, and in the probabilistic case, $ P(\theta \vert u)$ is specified. The distribution $ P(\theta \vert u)$ can be designed so that nature selects with very high probability the $ \theta \in \Theta$ that maximizes $ L(u,\theta)$. In Example 9.28, this would mean that the probability that the check would bounce (resulting in no earnings) would by very high, such as $ 0.999999$. In this case, even the optimal action under the probabilistic model is to select the 1 Euro in cash. For virtually any decision problem that is modeled using worst-case analysis, it is possible to work backward and derive possible priors for which the same decision would be made using probabilistic analysis. In Example 9.4, it seemed as if the decision was based on assuming that with very high probability, the check would bounce, even though there were no probabilistic models.

This means that worst-case analysis under the nondeterministic model can be considered as a special case of a probabilistic model in which the prior distribution assigns high probabilities to the worst-case outcomes. The justification for this could be criticized in the same way that other prior assignments are criticized in Bayesian analysis. What is the basis of this particular assignment?

Steven M LaValle 2012-04-20