Belief-State and Online Search

The companion lesson, Search Under Uncertainty, handled the case where the agent knows its state but its actions are nondeterministic, and found that the solution is a branching contingency plan built by AND-OR search. This lesson takes the next two steps into ignorance. First the agent loses sight of its own state — it is only partially observable — and must reason over the set of states it might be in. Then it loses the map entirely, dropped into an unknown environment where it must act in order to learn what states and actions even exist. The tools are belief-state search and online search, and in both a solution stops being a path and becomes a policy.

Partial observations: belief-state search

Now let the agent's percepts leave the true state uncertain. To keep this tractable, shift the whole problem up one level: instead of tracking the true state (which the agent cannot see), track the set of states it could be in. The central object is the belief state: the agent's current knowledge of which physical states it might be in, given all actions taken and percepts received so far.

In belief-state space the problem is fully observable: the agent may not know its physical state, but it always knows its own belief state exactly. So the machinery of Chapter 3 applies — once we say what the belief-state problem's states, actions, transition model, and goal test are.

Sensorless (conformant) planning

Start at the extreme, where the agent has no sensors at all. This is a sensorless (or conformant) problem. Acting without ever sensing sounds hopeless, yet such agents are often useful precisely because they don't depend on sensors working. Manufacturing systems orient parts from an unknown initial position by a fixed action sequence with no sensing, and a doctor prescribing a broad-spectrum antibiotic is running a conformant plan rather than paying for a diagnostic test.¹

The sensorless agent relies on coercion: even without seeing anything, a fixed sequence of actions can drive every possible starting state into the same goal. Take the sensorless vacuum world: the agent knows the world's geography but not its location or the dirt distribution, so its initial belief state is the set of all eight physical states, $\{1,2,3,4,5,6,7,8\}$. Actions shrink it. Move Right, and every state where the robot could go right does so; the belief collapses to $\{2,4,6,8\}$ (robot now in the right square, in some dirt configuration). The sequence [Right, Suck] narrows it to $\{4,8\}$. And the sequence [Right, Suck, Left, Suck] reaches state 7 no matter where the agent started — it coerces the world into a known goal.

The belief-state problem is built mechanically from the underlying physical problem $P$. If $P$ has $N$ states, the belief space has up to $2^N$ of them, though most are unreachable. The initial belief is typically all of $P$'s states. Actions are the union ${\bigcup }_{s\in b}{\text{Actions}}_P(s)$ (if illegal actions do nothing), or the intersection if illegality is dangerous. The transition model applies the action to every member of the belief and unions the results — the prediction step:

With deterministic actions $b^{\prime }$ is never larger than $b$; with nondeterministic actions it can grow. The goal test succeeds only if all physical states in $b$ satisfy the physical goal test — the agent may accidentally reach the goal earlier but won't know it. The reachable belief-state space is often tiny compared to the $2^N$ worst case: for the deterministic sensorless vacuum world, only 12 of the 256 belief states are reachable.

Trace the coercion in full. The initial belief is all eight states. Each action applies to every member and unions the results; because the actions here are deterministic, the belief only shrinks.

After step 4 the belief is the singleton $\{7\}$ — the goal — reached with no sensing at all. The plan [Right, Suck, Left, Suck] works from any starting state because it drives the whole belief, not one physical state, into the goal. Note the goal test fired only at step 4: at step 2 the belief $\{4,8\}$ contains the goal state 8, but also state 4 (left square still dirty), so the agent cannot yet know it is done.

Sensorless solving has one extra pruning trick unavailable to ordinary search. If a plan solves belief state $b$, it solves every subset of $b$. So if $\{1,3,5,7\}$ has already been generated, its subset $\{5,7\}$ need not be searched again — a superset already covers it. This can help dramatically. The real obstacle is not the number of belief states but their size: the initial belief for a $10\times 10$ vacuum world holds around $10^{32}$ physical states, far too many to list explicitly. The remedy is a compact description of the belief (nothing known, then not in the rightmost column) — the logical representation we develop later.

Contingent planning with percepts

Restore some sensing, and the belief-state transition gains an extra stage. In the local-sensing vacuum world the agent has a position sensor and a local dirt sensor but cannot see the other square, so its percept in state 1 is $[A,\text{Dirty}]$. Fully observable problems are the special case $\text{Percept}(s)=s$; sensorless problems are the special case $\text{Percept}(s)=\text{null}$. Everything in between is partial observability.

Because several states can produce the same percept, a belief-state transition now runs in three stages for a given action: act (which may enlarge the belief), observe, then keep only the states consistent with the percept (which shrinks it again).

• Prediction — apply the action to the current belief: $\hat{b}=\text{Predict}(b,a)$, exactly as in the sensorless case.
• Observation prediction — compute the percepts the predicted belief could generate: $\text{Possible-Percepts}(\hat{b})=\{o:o=\text{Percept}(s),s\in \hat{b}\}$.
• Update — for each possible percept $o$, keep just the states in $\hat{b}$ that could have produced it: $b_o=\text{Update}(\hat{b},o)=\{s:o=\text{Percept}(s),s\in \hat{b}\}$.

Putting the three stages together gives the full nondeterministic transition over belief states — nondeterministic because the agent cannot predict which percept it will get:

Notice the structure: prediction may enlarge the belief, but each update can only shrink it — observations can never add uncertainty — and for deterministic sensing the different percepts partition $\hat{b}$ into disjoint pieces. This is now an ordinary nondeterministic problem over belief states, so we can hand it straight to the And-Or-Graph-Search of the previous lesson. Feeding it the local-sensing vacuum problem with initial percept $[A,\text{Dirty}]$ (initial belief $\{1,3\}$) returns a conditional plan that tests the belief rather than the physical state:

The condition is on the belief state, as it must be — in a partially observable world the agent cannot execute a plan that tests the true state, because it cannot see it.

The prediction-observation-update cycle as filtering

An agent executing a contingent plan must keep its belief current as it acts. Given belief $b$, action $a$, and the actual percept $o$ received, the new belief is

This is a recursive state estimator: it computes the new belief from the previous belief and the latest percept, never re-scanning the whole history. Maintaining a belief this way is called monitoring or filtering or state estimation, and it is a core function of any agent in a partially observable world. A robot doing localization — working out where it is, given a map and a stream of percepts and moves — runs exactly this loop: from complete ignorance, each percept Update narrows the possible locations, each Move Predicts them forward, and the belief can collapse to a single location after only a couple of observations.

Predict grows the belief; Update shrinks it back — as long as the percepts carry identifying information. When they don't (a long featureless corridor of identical NS percepts), the belief never collapses. As environments grow complex the exact update becomes infeasible, and the agent must maintain an approximate belief. The probabilistic version of this loop, where the belief is a distribution rather than a set and Predict/Update become the operations of a Bayes filter, is the whole subject of reasoning over time. This set-based version is its logical skeleton.

Online search and unknown environments

So far the agent still had a map: it could compute the whole plan before moving. Take away the map and even that becomes impossible. Everything so far is offline search: the agent computes a complete solution before acting, then executes it. Online search interleaves computation and action — take an action, observe the result, compute the next action — and it is a necessity when the environment is unknown.

Online search is a good idea in dynamic domains, where deliberating too long is penalized, and in nondeterministic domains, where it lets the agent spend effort only on the contingencies that actually arise. It is mandatory in unknown environments, where the agent faces an exploration problem: it does not know what states exist or what its actions do, and must use its actions as experiments to learn enough to act well. The canonical case is a robot dropped in a new building that must explore to build a map. The binding constraint is that the agent cannot compute $\text{Result}(s,a)$ except by actually being in $s$ and doing $a$ — it knows $\text{Actions}(s)$, the step cost $c(s,a,s^{\prime })$ (but only once $s^{\prime }$ is revealed), and $\text{Goal-Test}(s)$, and perhaps an admissible heuristic $h(s)$, but the outcomes are discovered only by trying them.

The competitive ratio

An exploring agent is graded against the agent that had the map all along. The agent's cost is the total path cost of the route it actually travels; compare that to the cost of the route it would have taken had it known the space in advance (the true shortest path). Their ratio is the competitive ratio, and we want it small.

The bad news is that the best achievable competitive ratio is sometimes infinite. If some actions are irreversible, the agent can wander into a dead end from which no goal is reachable. And no algorithm can avoid every dead end: an adversary can build the state space as the agent explores it, placing goals and dead ends wherever it likes. Two state spaces can look identical to an agent that has seen the same states so far, forcing it into the same choice in both — so it must fail in at least one.

To make progress at all, we assume the state space is safely explorable: some goal is reachable from every reachable state, so no action is a trap. State spaces with reversible actions — mazes, the 8-puzzle — are undirected graphs and hence safely explorable. Even then, no bounded competitive ratio is guaranteed when paths can have unbounded cost: an adversary can keep walling off the chosen route with long, thin barriers, so the followed path is arbitrarily longer than the best one. For this reason online performance is usually stated in terms of the size of the whole state space rather than the depth of the shallowest goal.

Online depth-first search

One offline algorithm carries over when the agent can only expand the node it is physically standing on: depth-first search, because it explores locally. After each action the online agent gets a percept identifying its new state, and augments its map. Because it can only expand the node it physically occupies (not jump around the tree the way offline A* does), it wants a local expansion order — and depth-first search has exactly that property: except when backtracking, the next node expanded is a child of the current one. The catch is backtracking: offline DFS just pops a node off the queue, but online the agent must physically walk back to the state it came from. So the algorithm records, in a result table, which state each action led to, and an unbacktracked table of predecessors it can still retreat to.

Trace it. From S the agent pops an untried action, say the one to a, and stores $result[S,\text{that action}]=a$. From a it goes to b, a dead end with no new actions; untried[b] is empty, so it pops unbacktracked[b] and physically walks back to a. At a an untried action remains (to c), so it takes it, then c to G — goal, stop. The dashed retrace from b to a is the physical backtrack that offline DFS gets for free by popping a queue.

In the worst case the agent traverses every edge exactly twice, which is optimal for exploring everything, but its competitive ratio for finding a goal can be arbitrarily bad if it goes off on a long excursion while a goal sits right next to the start. An online variant of iterative deepening fixes this for uniform trees. Online-DFS-Agent only works where actions are reversible (backtracking must be possible); more general algorithms exist, but none has a bounded competitive ratio. Hill climbing shows the flip side: a random walk is guaranteed to reach a goal in a finite space eventually, but eventually can be exponential — in a state space shaped like a long corridor where each step is twice as likely to go backward as forward, the expected number of steps to escape grows exponentially with the corridor length, which is precisely the trap LRTA*'s learned estimates avoid.

LRTA*: learning a heuristic while exploring

Depth-first exploration is systematic but not smart — it doesn't use cost estimates. Hill climbing does keep only one current state (so it is already an online algorithm) but gets stuck at local minima with nowhere to go, and it cannot use random restarts because the agent cannot teleport to a new state. A random walk will eventually find a goal in a finite space, but eventually can be exponentially long.

The effective idea is to give hill climbing a memory of its own mistakes: store a current best estimate $H(s)$ of the cost to reach a goal from each visited state. $H(s)$ starts as the heuristic $h(s)$ and is refined as experience accumulates. This is learning real-time A*, or LRTA*.² From the current state the agent looks at each neighbor $s^{\prime }$, estimates the cost of reaching a goal through it as $c(s,a,s^{\prime })+H(s^{\prime })$, and moves to the best one — after first correcting $H$ for the state it is leaving, setting it to the minimum such estimate. Untried actions are assumed to lead straight to the goal at cost $h(s)$ — optimism under uncertainty, which pushes the agent toward unexplored, possibly promising paths.

Trace the dip. The shaded state's estimate is 2, but its two neighbors cost $1+9$ and $1+2$, so the best move (right, cost 3) reveals that the old estimate of 2 was too optimistic — the state must be at least 3 steps from a goal, so $H$ is raised to 3 before the agent leaves. Repeating this flattens the local minimum: each pass raises the trapped state's estimate a little more, until the accumulated cost finally tips the agent out of the dip and onward to the goal.

An LRTA* agent is guaranteed to find a goal in any finite, safely explorable environment. Unlike A*, it is not complete for infinite spaces — it can be led infinitely astray — and it can take $O(n^2)$ steps to explore $n$ states in the worst case, but usually does far better. It is one member of a large family of online agents defined by different action-selection and update rules.

From search to reinforcement learning

The initial ignorance of online search is also an opportunity to learn, and here search becomes reinforcement learning. Two things get learned. First, the agent learns a map — the outcome $result[s,a]$ of each action — simply by recording each experience; in a deterministic world one experience per action suffices. Second, agents like LRTA* learn better cost estimates through local update rules. In stochastic environments those updates, iterated the right way, provably converge to the exact cost of every state; and once exact costs are known, the optimal policy is trivial — move to the lowest-cost successor, so pure hill climbing becomes optimal.

That convergence result is the basis of value-based reinforcement learning: LRTA* is a special case of RL algorithms for stochastic environments, its optimism under uncertainty a search heuristic that reappears as an exploration strategy. What is still missing is a way to generalize — to learn that Up increases the $y$-coordinate everywhere, not just at one visited cell — which requires a manipulable representation of the transition model in place of the black-box Result table, the concern of knowledge representation and learning.

Real-time search, AND-OR planners, and POMDPs

Each of the settings in these two lessons opened into a research line that AIMA's chapter only gestures at.

Real-time heuristic search. LRTA* is one member of a family that Korf introduced in the same paper (Korf, 1990), alongside RTA* (real-time A*), which keeps the second-best neighbor estimate to decide when a state is worth abandoning, and gives a cleaner competitive bound on trees. The line matured into game and robotics use, where an agent must commit to a move within a fixed time budget. LRTA-LS* and LSS-LRTA* (Koenig and Sun, 2009) expand a bounded local search space each step instead of a single node, propagating heuristic updates over the whole frontier so the learned $H$ converges far faster — the version used in real-time pathfinding for games. Surveys of the area (Bulitko and Lee, 2006) map dozens of such agents by their lookahead, learning, and control-strategy choices, all variations on hill-climb, but remember and repair.³

Optimal AND-OR planners. The And-Or-Graph-Search of the previous lesson returns some contingency plan; finding a least-cost one is the province of AO* (Nilsson, 1980), which does best-first expansion of an AND-OR graph with an admissible heuristic, and LAO* (Hansen and Zilberstein, 2001), which extends AO* to graphs with loops — exactly the cyclic solutions the slippery world forces. LAO* is the bridge from AND-OR search to decision-theoretic planning: it solves the same recursion those lessons set up, but over a Markov decision process, and its value function is computed by the dynamic-programming updates that reappear as reinforcement learning.⁴

Partial observability at scale. The belief-state machinery, made probabilistic, is the partially observable Markov decision process (POMDP). A POMDP's belief is a probability distribution over states rather than a set, and the predict-observe-update cycle becomes a Bayes filter — the exact continuation this lesson points to. Exact POMDP solving is intractable in general (PSPACE-hard; Papadimitriou and Tsitsiklis, 1987), but point-based approximations — PBVI (Pineau, Gordon, Thrun, 2003) and SARSOP (Kurniawati, Hsu, Lee, 2008) — plan over a sampled set of reachable beliefs and scale to problems with thousands of states, and they underpin robot navigation and dialogue systems that must act under sensing noise. The set-based belief here is the logical skeleton these distributional methods flesh out.⁵

Online search in modern systems. The interleaving of planning and acting that defines online search is the core loop of model-predictive control and of Monte Carlo tree search (Coulom, 2006; Kocsis and Szepesvári's UCT, 2006), where an agent repeatedly plans a short horizon from its current state, acts, and replans — the same focus effort on the contingencies that actually arise argument AIMA gives for online search, scaled up by sampling. UCT's optimism-under- uncertainty exploration term is a direct descendant of LRTA*'s assumption that untried actions lead straight to the goal.⁶

The through-line

These two lessons are one idea at increasing distances from certainty. When the effect of an action is uncertain, plans branch on outcomes: AND-OR search returns a contingent tree, with cyclic plans when retrying is the only option. When the state is uncertain, plans reason over belief states, and a predict-observe-update cycle keeps the belief current — the logical core of the probabilistic filtering that follows. When the environment itself is unknown, the agent must act to learn: online search interleaves planning and acting, the competitive ratio measures the cost of not knowing the map, and LRTA* refines its own heuristic as it goes, one step from reinforcement learning.

The common thread is that a solution stops being a fixed sequence and becomes a policy — a mapping from what the agent knows to what it should do. That shift, from computing a path to computing a policy, is precisely the move from classical search to planning in the real world and to decision-making under uncertainty, where the notion of a best action given a belief becomes the language of making decisions.