From a task description to a decision problem
A robot can execute a search algorithm correctly and still pursue the wrong objective. A fault monitor rewarded for the number of warnings can improve its score by warning constantly. A controller that treats its latest sensor reading as the physical state can choose an action inappropriate to everything it observed earlier. Modeling an agent therefore begins before choosing a search or learning algorithm: what counts as success, what can the agent observe, and how do its actions change its situation?
A useful task specification lists performance, environment, actuators and sensors, abbreviated PEAS. For an equipment controller, performance might penalize downtime, failed operations and maintenance expenditure over one shift. The environment includes equipment condition and its evolution; actuators include operate, inspect and reset; sensors provide diagnostic reports. This list becomes mathematically useful when it exposes omissions. If inspection consumes a time slot, its time cost belongs in the decision model. If a reset changes condition, the next prediction must use the reset transition law.
The externally evaluated performance measure and the agent's internal utility are distinct objects. An internal objective is a proposed representation of the task, not automatically the task itself. Counting successful operations while ignoring failures is a different objective from successful operations minus a failure penalty. A good optimizer cannot repair that specification error. In this unit, rationality means maximizing the stated expected objective using the available history and model; it does not mean knowing the hidden state, predicting the realized future, or obtaining the best outcome in hindsight.
States, histories and the information available for action
Let S, A and Y be nonempty finite sets of physical states, actions and sensor symbols. We assume every action is available in every state; state-dependent feasibility would need an explicit observation-compatible policy. At time t the agent has already received its current observation and chooses . Its history records observations and all previous actions.
Definition 21.1.1
(Belief state)
The belief state at time is the conditional distribution
on . It is not a declaration that the equipment has several actual conditions simultaneously; it expresses uncertainty about one actual state.
If an initial observation precedes every action, specify an initial kernel and prior . For a positive-probability observation, . Alternatively, supply the initial belief directly without an initial observation. A policy may depend on the entire history and the number of decisions remaining.
We specify a transition kernel and an observation kernel . Entries are nonnegative; each transition row sums to one over , and each observation row sums to one over y. The timing is action, state transition, then observation of the new state. Our conditional-independence assumption is
Thus these kernels do not secretly depend on earlier history. If an unrecorded battery temperature or a persistent sensor fault changes future behavior, the chosen state may be too small. Add that variable to the state or state the approximation. Calling a variable a state does not prove the required conditional independence.
For a fixed finite horizon H, let be a finite real reward and define performance by expected total reward over the next H decisions. Costs can be represented by negative rewards. We omit discounting and terminal rewards to keep the model explicit; either can be added with a stated recurrence. A utility function over outcomes may encode risk attitudes, but maximizing expected raw monetary reward and maximizing expected utility of money are generally different tasks. No theorem below identifies those preferences.
Prediction and correction are different operations
Starting from belief b and action a, first predict the next physical state, then condition on the sensor report:
Definition 21.1.2
(Belief update)
For an action and an observation with , the updated belief is
The numerator is a joint probability; the denominator makes the entries sum to one. An observation with zero denominator has probability zero under the model. There is no conditional distribution given by this quotient in that case. An implemented controller must report the model mismatch or invoke a separately specified recovery policy. Substituting a uniform belief without saying so adds an assumption.
Proposition 21.1.3
(A belief summarizes the predictive history under the model)
For the finite kernels and conditional-independence assumption above, the prediction and correction formulas give the conditional law of the next state after every positive-probability history. Given the current belief and next action, the distribution of the next observation and updated belief is independent of the rest of the history. Current expected reward is . Consequently the belief, together with the remaining horizon, suffices for the finite-horizon optimization problem.
Proof
(Belief as a sufficient statistic)
Sum the displayed conditional law over the current state, weighting by . This gives joint probability . Summing over gives p, and division by positive p gives the posterior. Nonnegativity is immediate, and summing transition or observation rows verifies normalization. Expected reward is obtained by conditioning on the current state. Applying the same argument repeatedly shows that, for each future action selection, future distributions are determined by the updated belief. Hence histories that yield the same belief offer the same future decision problem when the remaining horizon is the same.
Proof X-ray
The sufficiency claim depends on the chosen state
The proof removes history only by using the asserted kernel factorization. If sensor reliability depends on a hidden persistent mode, two histories can give the same marginal equipment belief but different beliefs about that mode. Those marginal beliefs are then insufficient. A joint belief over equipment and sensor mode restores the argument when the enlarged state satisfies the assumptions.
Planning on beliefs and the value of information
Set . If h decisions remain, the optimal expected reward satisfies
An action determines both immediate reward and future information. An action with poor immediate reward may improve the next decision. Conversely, looking only for the most informative sensor report ignores what information is useful for the objective.
Theorem 21.1.4
(Finite-horizon optimality and deterministic choices)
Under the preceding finite model, the recurrence equals the maximum expected total reward among all history-dependent policies, including randomized policies. At every positive-probability history, some deterministic action attains that value. This is a finite-horizon statement; it does not assert that one time-independent rule is optimal for every horizon.
Proof
(Induction on the number of remaining decisions)
Induct on h. With no decisions, every policy receives zero. Suppose the result holds for . Condition any h-step policy on its first action and next observation. By belief sufficiency, each continuation earns at most at the corresponding posterior. For a fixed first action, its total value is therefore bounded by the bracketed expression. A randomized first choice takes a weighted average of these finitely many expressions and cannot exceed their largest value. Choose an action attaining the maximum, and after every positive-probability observation choose an optimal continuation supplied by the induction hypothesis. This constructs a deterministic policy attaining the bound and closes the induction.
Although S is finite, the set of probability vectors on S is generally continuous. The proof does not turn belief space into a finite state table. For a fixed initial belief and finite horizon, only finitely many action-observation histories occur, so a finite decision tree can be evaluated exactly. A belief grid is an additional approximation requiring a separate error analysis.
Concept lensStructural
An extra observation enlarges the decision options
Suppose an observation is free, consumes no time, changes no state and leaves all later actions available. Every old policy can be used after the observation by ignoring it. Maximization over the enlarged policy set therefore cannot lower optimal expected reward. For losses, the optimal expected loss cannot increase. A costly test, a delayed action or a restricted controller does not satisfy these assumptions.
For a single terminal decision, the same argument can be checked algebraically. If observation y has probability and posterior , choose the best action separately at each y. This is at least as good as choosing one common action first, because . The inequality concerns expected optimal performance; an individual unlucky observation can still lead to a worse realized outcome.
Worked control examples
Worked example 21.1.5
(An alarm changes a decision without revealing the state)
Condition is faulty F or good G, with prior . A static-state test reports alarm + with probabilities and . Thus , and Bayes' rule gives . A negative report has probability and posterior fault probability .
For one terminal decision, operating incurs loss 10 if faulty and zero if good. A terminal repair option incurs fixed loss 3, including all its consequences in this toy objective. At fault belief b, operating has expected loss and repair has loss 3. Repair is optimal when ; either action is optimal at equality. Without testing, operate at expected loss 2. After an alarm, repair; after a negative, operate. Neither report establishes the actual condition with certainty.
Worked example 21.1.6
(Information is worth its decision improvement, not its entropy alone)
Charge for the preceding test and assume it causes no delay or state change. The expected loss of testing and then acting optimally is
This improves on loss 2 by . The expected post-test action loss, excluding test cost, is , so the largest test cost for which testing is weakly preferred is . A test costing 1 is informative but not worth buying here. The comparison includes the possibility of ignoring a report; no rule forces action merely because information was acquired.
Worked example 21.1.7
(A reset changes the prediction before the next alarm)
Now consider a different, continuing control model: after an alarm the fault belief is , and a reset repairs a faulty device with probability while leaving a good one good. Do not import the previous terminal repair assumption into this transition model. The predicted fault probability after reset is . Using the same alarm sensor, another alarm gives
Updating the old belief directly with an alarm would instead give . That calculation describes repeated sensing without the reset. The difference comes from action-dependent state prediction, not a different version of Bayes' rule. Choosing reset optimally would additionally require its reward and the remaining horizon, which this state-estimation example does not specify.
Architectures implement different amounts of this model
A simple reflex agent maps the current observation to an action. It may be adequate when that observation already contains everything needed for the decision. A model-based agent maintains an internal state; the posterior b is one mathematically specified choice. A goal-based planner seeks actions reaching an acceptable condition, while a utility-based planner can compare acceptable outcomes having different costs, risks or delays. These are architectural descriptions, not theorems that each later label is better on every task.
A belief filter plus the one-step threshold above is a model-based utility controller for that terminal problem. Replacing the threshold by finite-horizon dynamic programming accounts for later rewards and observations. A learning component could estimate T or Z from data, but the control proof assumes those kernels are already specified. Plugging in an estimate is not proof that it equals the true model. If parameter uncertainty matters, it must be represented, for example by enlarging the hidden state to include a fixed unknown mode.
Counterexample mode
The same current report can require different actions
Keep the static-state sensor model and conditionally independent reports. Prior fault odds are . An alarm multiplies the odds by 8; a negative report multiplies them by . The three-report history gives odds , hence posterior . History gives odds , hence posterior . The latest symbol is + in both cases, and the history lengths and remaining terminal decision are the same, but the loss threshold calls for repair in the first case and operation in the second. No deterministic rule depending only on the latest symbol and time index can make both choices. A memory of relevant history, rather than a more complicated name for the agent, repairs the defect.
Expected optimality is model-relative. Incorrect failure costs can reverse the threshold; correlated sensor errors can invalidate multiplying likelihood ratios; a changing device may invalidate a static-state calculation. Conversely, a rational choice can fail on a particular run because a low-probability state occurred. Evaluation should separate objective specification, state estimation, policy computation and realized outcomes.
Common mistakes
Common mistake
(Skipping the prediction step after an action)
After a reset, applying the alarm likelihoods to the old belief gives , whereas the model gives . Bayes' rule is applied to the predicted belief , not to the previous belief , because the action may change the state before the report is generated. Using directly is correct only when leaves the state unchanged.
Common mistake
(Judging a decision by one realized outcome)
After a negative report the fault belief is , and operating is optimal. In the remaining of such cases the device is faulty and the loss is 10. That outcome does not show the decision was irrational: a choice is assessed by expected loss under the model at the moment of choice, and a repeated pattern of such surprises is evidence about the model instead.
Common mistake
(Treating every informative test as worth its price)
In the loss-3 problem the noisy test is worth at most , so at price 1 it should be declined even though its reports shift the belief. Information is valued by the decision improvement it buys, and a report that cannot change the optimal action is worth nothing.
Exercises
Quick check
(A monitor is scored only by the number of genuine faults it reports, with no penalty for other warnings. Explain why warning on every case can maximize that measure. Propose a finite objective that distinguishes missed faults, false alarms and inspection cost, and name the corresponding PEAS entries.)
Ask what the score rewards and what it fails to penalize.
Solution · Answer
If a genuine fault earns a point whenever reported, reporting every case captures every available point; extra warnings have no stated cost. For a finite sequence, a possible loss is , where M counts missed faults, F counts false warnings and I counts paid inspections, with specified positive coefficients. The objective is to minimize its expectation, including any delayed consequences in the chosen horizon. Performance is this loss; environment includes fault generation and evolution; actuators are report, inspect or withhold; sensors are the available readings. The coefficients express task preferences and need justification from the evaluator.
Quick check
(For the static-state sensor above, derive the negative-report posterior from joint probabilities. If a terminal repair costs rather than 3, determine the optimal action before sensing and after each report.)
Compute the two joint probabilities first, then normalize; compare each belief with the new threshold.
Solution · Answer
The joint negative/fault probability is , and negative/good probability is . Normalizing gives . The new threshold is . Prior and alarm posterior both exceed it. Even , so repair is optimal after a negative too. The noisy test now changes beliefs without changing the terminal action; its decision value before any test charge is zero.
Quick check
(Compute the expected terminal action loss after a free perfect inspection in the original loss-3 repair problem. Find its maximum worthwhile price. Explain why this differs from the noisy test's threshold.)
After a perfect inspection the posterior is 0 or 1; compare the resulting action loss with 2.
Solution · Answer
Perfect inspection reveals F with probability and G with probability . Repair only in F, giving expected action loss . Relative to the unsensed loss 2, the largest worthwhile price is . The noisy report sometimes leads to unnecessary repairs and sometimes leaves faults undetected, producing action loss instead. More information can enlarge the available contingent policies, but each test must be priced using the actual decision problem.
Quick check
(An observation kernel has independent of . Show that any positive-probability observation leaves the predicted belief unchanged. Does this imply the action itself cannot improve the physical condition?)
Substitute into the numerator and the denominator of the update.
Solution · Answer
The denominator is . For a positive denominator, cancellation gives . This sensor supplies no extra state information conditional on the chosen action. The transition T may nevertheless move a faulty state to a good one; lack of information and lack of physical control are different properties.
Quick check
(At a particular belief, two first-action values, including their optimal continuations, are 4 and 7. A policy chooses the first with probability . Find its expected value and explain the deterministic-policy conclusion. Why does this calculation not prove that one fixed action is optimal at every belief?)
Average the two values with the given weights.
Solution · Answer
The randomized value is . Choosing the second action deterministically attains 7. The argument compares actions at this belief and remaining horizon, using the same correctly computed continuation values. At another belief or horizon their order can reverse, so it supplies no universally optimal fixed action.