foundations of computational agents
The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).
Dimensions: flat, features, finite horizon, partially observable, stochastic, utility, non-learning, single agent, offline, perfect rationality
Basic decision theory applied to intelligent agents relies on the following assumptions:
Agents know what actions they can carry out.
The effect of each action can be described as a probability distribution over outcomes.
An agent’s preferences are expressed by utilities of outcomes.
It is a consequence of Proposition 9.3 that, if agents only act for one step, a rational agent should choose an action with the highest expected utility.
Consider the problem of the delivery robot in which there is uncertainty in the outcome of its actions. In particular, consider the problem of going from position ${o}{\mathit{}}{\mathrm{109}}$ in Figure 3.1 to the ${m}{\mathit{}}{a}{\mathit{}}{i}{\mathit{}}{l}$ position, where there is a chance that the robot will slip off course and fall down the stairs. Suppose the robot can get pads that will not change the probability of an accident but will make an accident less severe. Unfortunately, the pads add extra weight. The robot could also go the long way around, which would reduce the probability of an accident but make the trip much slower.
Thus, the robot has to decide whether to wear the pads and which way to go (the long way or the short way). What is not under its direct control is whether there is an accident, although this probability can be reduced by going the long way around. For each combination of the agent’s choices and whether there is an accident, there is an outcome ranging from severe damage to arriving quickly without the extra weight of the pads.
In one-off decision making, a decision variable is used to model an agent’s choice. A decision variable is like a random variable, but it does not have an associated probability distribution. Instead, an agent gets to choose a value for a decision variable. A possible world specifies values for both random and decision variables. Each possible world has an associated utility. For each combination of values to decision variables, there is a probability distribution over the random variables. That is, for each assignment of a value to each decision variable, the measures of the worlds that satisfy that assignment sum to $1$.
Figure 9.6 shows a decision tree that depicts the different choices available to the agent and the outcomes of those choices. To read the decision tree, start at the root (on the left in this figure). For the decision nodes, shown as squares, the agent gets to choose which branch to take. For each random node, shown as a circle, the agent does not get to choose which branch will be taken; rather there is a probability distribution over the branches from that node. Each leaf corresponds to a world, which is the outcome if the path to that leaf is followed.
In Example 9.6 there are two decision variables, one corresponding to the decision of whether the robot wears pads and one to the decision of which way to go. There is one random variable, whether there is an accident or not. Eight possible worlds correspond to the eight paths in the decision tree of Figure 9.6.
What the agent should do depends on how important it is to arrive quickly, how much the pads’ weight matters, how much it is worth to reduce the damage from severe to moderate, and the likelihood of an accident.
The proof of Proposition 9.3 specifies how to measure the desirability of the outcomes. Suppose we decide to have utilities in the range [0,100]. First, choose the best outcome, which would be ${{w}}_{{\mathrm{5}}}$, and give it a utility of ${\mathrm{100}}$. The worst outcome is ${{w}}_{{\mathrm{6}}}$, so assign it a utility of ${\mathrm{0}}$. For each of the other worlds, consider the lottery between ${{w}}_{{\mathrm{6}}}$ and ${{w}}_{{\mathrm{5}}}$. For example, ${{w}}_{{\mathrm{0}}}$ may have a utility of 35, meaning the agent is indifferent between ${{w}}_{{\mathrm{0}}}$ and ${\mathrm{[}}{\mathrm{0.35}}{\mathrm{:}}{{w}}_{{\mathrm{5}}}{\mathrm{,}}{\mathrm{0.65}}{\mathrm{:}}{{w}}_{{\mathrm{6}}}{\mathrm{]}}$, which is slightly better than ${{w}}_{{\mathrm{2}}}$, which may have a utility of 30. ${{w}}_{{\mathrm{1}}}$ may have a utility of 95, because it is only slightly worse than ${{w}}_{{\mathrm{5}}}$.
In medical diagnosis, decision variables correspond to various treatments and tests. The utility may depend on the costs of tests and treatment and whether the patient gets better, stays sick, or dies, and whether they have short-term or chronic pain. The outcomes for the patient depend on the treatment the patient receives, the patient’s physiology, and the details of the disease, which may not be known with certainty.
The same approach holds for diagnosis of artifacts such as airplanes; engineers test components and fix them. In airplanes, you may hope that the utility function is to minimize accidents (maximize safety), but the utility incorporated into such decision making is often to maximize profit for a company and accidents are simply costs taken into account.
In a one-off decision, the agent chooses a value for each decision variable simultaneously. This can be modeled by treating all the decision variables as a single composite decision variable, $D$. The domain of this decision variable is the cross product of the domains of the individual decision variables.
Each world $\omega $ specifies an assignment of a value to the decision variable $D$ and an assignment of a value to each random variable. Each world has a utility, given by the variable $u$.
A single decision is an assignment of a value to the decision variable. The expected utility of single decision $D={d}_{i}$ is $\mathcal{E}(u\mid D={d}_{i})$, the expected value of the utility conditioned on the value of the decision. This is the average utility of the worlds where the worlds are weighted according to their probability:
$$\mathcal{E}(u\mid D={d}_{i})=\sum _{\omega :D(\omega )={d}_{i}}u(\omega )*P(\omega ),$$ |
where $D(\omega )$ is the value of variable $D$ in world $\omega $, $u(\omega )$ is the value of utility in $\omega $, and $P(\omega )$ is the probability of world $\omega $.
An optimal single decision is the decision whose expected utility is maximal. That is, $D={d}_{max}$ is an optimal decision if
$$\mathcal{E}(u\mid D={d}_{max})=\underset{{d}_{i}\in domain(D)}{\mathrm{max}}\mathcal{E}(u\mid D={d}_{i}),$$ |
where $domain(D)$ is the domain of decision variable $D$. Thus,
$${d}_{max}=\mathrm{arg}\underset{{d}_{i}\in domain(D)}{\mathrm{max}}\mathcal{E}(u\mid D={d}_{i}).$$ |
The delivery robot problem of Example 9.6 is a single decision problem where the robot has to decide on the values for the variables ${W}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathit{}}{\mathrm{\_}}{\mathit{}}{p}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{s}$ and ${W}{\mathit{}}{h}{\mathit{}}{i}{\mathit{}}{c}{\mathit{}}{h}{\mathit{}}{\mathrm{\_}}{\mathit{}}{w}{\mathit{}}{a}{\mathit{}}{y}$. The single decision is the complex decision variable $$. Each assignment of a value to each decision variable has an expected value. For example, the expected utility of ${W}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathit{}}{\mathrm{\_}}{\mathit{}}{p}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{s}{\mathrm{=}}{t}{\mathit{}}{r}{\mathit{}}{u}{\mathit{}}{e}{\mathrm{\wedge}}{W}{\mathit{}}{h}{\mathit{}}{i}{\mathit{}}{c}{\mathit{}}{h}{\mathit{}}{\mathrm{\_}}{\mathit{}}{w}{\mathit{}}{a}{\mathit{}}{y}{\mathrm{=}}{s}{\mathit{}}{h}{\mathit{}}{o}{\mathit{}}{r}{\mathit{}}{t}$ is given by
${\mathcal{E}}{(}{u}{\mid}{w}{e}{a}{r}{\mathrm{\_}}{p}{a}{d}{s}{\wedge}{W}{h}{i}{c}{h}{\mathrm{\_}}{w}{a}{y}{=}{s}{h}{o}{r}{t}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{=}{P}{(}{a}{c}{c}{i}{d}{e}{n}{t}{\mid}{w}{e}{a}{r}{\mathrm{\_}}{p}{a}{d}{s}{\wedge}{W}{h}{i}{c}{h}{\mathrm{\_}}{w}{a}{y}{=}{s}{h}{o}{r}{t}{)}{*}{u}{(}{{w}}_{{0}}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{+}{(}{1}{-}{P}{(}{a}{c}{c}{i}{d}{e}{n}{t}{\mid}{w}{e}{a}{r}{\mathrm{\_}}{p}{a}{d}{s}{\wedge}{W}{h}{i}{c}{h}{\mathrm{\_}}{w}{a}{y}{=}{s}{h}{o}{r}{t}{)}{)}{*}{u}{(}{{w}}_{{1}}{)}{,}$ |
where ${u}{\mathit{}}{\mathrm{(}}{{w}}_{{i}}{\mathrm{)}}$ is the value of the utility in worlds ${{w}}_{{i}}$, the worlds ${{w}}_{{\mathrm{0}}}$ and ${{w}}_{{\mathrm{1}}}$ are as in Figure 9.6, and ${w}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathit{}}{\mathrm{\_}}{\mathit{}}{p}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{s}$ means ${W}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathit{}}{\mathrm{\_}}{\mathit{}}{p}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{s}{\mathrm{=}}{t}{\mathit{}}{r}{\mathit{}}{u}{\mathit{}}{e}$.