---
title: Belief-State and Online Search
module: Search
moduleNumber: 2
lessonNumber: 12
order: 212
summary: >
  When the agent cannot see the full state, a plan can no longer test where it
  actually is — it must reason over the set of states it might be in. This lesson
  develops belief-state search, from sensorless (conformant) planning that coerces
  an unknown world into a goal, through the predict-observe-update cycle of
  contingent planning with percepts, to online search in unknown environments,
  where the agent must act in order to learn. It closes with LRTA*, which refines
  its own heuristic as it explores, one step from reinforcement learning.
topics: [Search]
sources:
  - book: AIMA
    ref: "Ch. 4 — Beyond Classical Search; §4.4 Searching with Partial Observations"
  - book: AIMA
    ref: "§4.5 Online Search Agents and Unknown Environments"
---

The companion lesson,
[Search Under Uncertainty](/artificial-intelligence/search/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.

> **Definition (Belief state).** A set $b$ of physical states, representing all the
> states the agent believes it might currently occupy. The agent reasons and plans
> in the space of belief states rather than the space of physical states.

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.[^aima-sensorless]

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.

$$
% caption: A sensorless plan coerces the belief state toward a goal. The fixed
% sequence Right, Suck, Left, Suck drives the initial belief (all 8 states) down to
% the single goal state 7, with no sensing anywhere along the way.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bel/.style={draw, ellipse, minimum width=26mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[bel] (b0) at (0,0) {1,2,3,4,\\5,6,7,8};
  \node[bel] (b1) at (3.4,0) {2,4,6,8};
  \node[bel] (b2) at (6.4,0) {4,8};
  \node[bel, draw=acc, text=acc] (b3) at (9.2,0) {7};
  \draw[->, acc, thick] (b0) -- (b1) node[midway, above, black, font=\footnotesize] {Right};
  \draw[->, acc, thick] (b1) -- (b2) node[midway, above, black, font=\scriptsize] {Suck};
  \draw[->, acc, thick] (b2) -- (b3) node[midway, above, black, font=\footnotesize] {Left,Suck};
\end{tikzpicture}
$$

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} \textsc{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:

$$
b' \;=\; \textsc{Predict}(b, a) \;=\; \bigcup_{s \in b} \textsc{Results}_P(s, a).
$$

With deterministic actions $b'$ 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.

$$
% caption: The prediction step under nondeterminism. From belief {1,3}, a
% deterministic Right yields {2,4}, but a slippery Right (movement may fail) yields
% {1,2,3,4} — nondeterminism enlarges the belief.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bel/.style={draw, ellipse, minimum width=18mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % deterministic
  \node[bel] (d0) at (0,1.4) {1,3};
  \node[bel, draw=acc, text=acc] (d1) at (3.2,1.4) {2,4};
  \draw[->, acc, thick] (d0) -- (d1) node[midway, above, black, font=\footnotesize] {Right (det.)};
  % slippery
  \node[bel] (s0) at (0,-1.4) {1,3};
  \node[bel, draw=red, text=red] (s1) at (3.6,-1.4) {1,2,3,4};
  \draw[->, red, thick] (s0) -- (s1) node[midway, above, black, font=\footnotesize] {Right (slip)};
\end{tikzpicture}
$$

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.

| Step | Action | Belief before | Belief after | Why |
| --- | --- | --- | --- | --- |
| 0 | — | — | $\{1,2,3,4,5,6,7,8\}$ | total ignorance |
| 1 | `Right` | $\{1,\ldots,8\}$ | $\{2,4,6,8\}$ | robot now in the right square, any dirt config |
| 2 | `Suck` | $\{2,4,6,8\}$ | $\{4,8\}$ | right square becomes clean in every state |
| 3 | `Left` | $\{4,8\}$ | $\{3,7\}$ | robot moves to the left square |
| 4 | `Suck` | $\{3,7\}$ | $\{7\}$ | left square becomes clean; both squares clean |

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\times10$
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](/artificial-intelligence/logic-and-planning/knowledge-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, \textit{Dirty}]$. Fully observable problems are the special case
$\textsc{Percept}(s) = s$; sensorless problems are the special case
$\textsc{Percept}(s) = \textit{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} = \textsc{Predict}(b, a)$, exactly as in the sensorless case.
- **Observation prediction** — compute the percepts the predicted belief could
  generate: $\textsc{Possible-Percepts}(\hat{b}) = \{o : o = \textsc{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 = \textsc{Update}(\hat{b}, o) = \{s : o = \textsc{Percept}(s),\ s \in \hat{b}\}$.

$$
% caption: The prediction-observation-update cycle for one action, mapping belief
% $b$ to the predicted belief $\hat b$, then splitting by percept into updated
% beliefs $b_{o_1}, b_{o_2}$. Prediction grows (or holds) the belief; each percept's
% update keeps only the consistent states, shrinking uncertainty back down.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bel/.style={draw, ellipse, minimum width=17mm, minimum height=11mm, align=center, font=\footnotesize},
  lstep/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[bel] (b) at (0,0) {belief b};
  \node[bel] (pred) at (3.6,0) {predict\\b-hat};
  \node[bel] (o1) at (7.4,1.3) {update\\b(o1)};
  \node[bel] (o2) at (7.4,-1.3) {update\\b(o2)};
  \draw[->, acc, thick] (b) -- (pred) node[midway, above, black, font=\footnotesize] {action a};
  \draw[->, acc, thick] (pred) -- (o1) node[midway, above left=-1pt, black, font=\footnotesize] {percept o1};
  \draw[->, acc, thick] (pred) -- (o2) node[midway, below left=-1pt, black, font=\footnotesize] {percept o2};
  \node[lstep, acc, anchor=north] at (3.6,-1.05) {prediction};
\end{tikzpicture}
$$

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

$$
\textsc{Results}(b, a) = \{\, b_o : b_o = \textsc{Update}(\textsc{Predict}(b, a), o),\ o \in \textsc{Possible-Percepts}(\textsc{Predict}(b, a)) \,\}.
$$

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, \textit{Dirty}]$ (initial belief
$\{1,3\}$) returns a conditional plan that tests the _belief_ rather than the
physical state:

$$
[\,\textit{Suck},\ \textit{Right},\ \textbf{if } \textit{Bstate}=\{6\} \textbf{ then } \textit{Suck} \textbf{ else } [\,]\,].
$$

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

$$
b' = \textsc{Update}(\textsc{Predict}(b, a), o).
$$

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` `Predict`s them
forward, and the belief can collapse to a single location after only a couple of
observations.

$$
% caption: Localization as filtering. From an all-locations belief, an obstacle
% percept prunes the belief (Update), a Move spreads it (Predict), and the next
% percept prunes again — the belief tightens toward the true location.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bel/.style={draw, minimum width=18mm, minimum height=9mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[bel] (b0) at (0,0) {all\\locations};
  \node[bel] (b1) at (2.9,0) {4 spots};
  \node[bel] (b2) at (5.7,0) {spread};
  \node[bel, draw=acc, text=acc] (b3) at (8.5,0) {1 spot};
  \draw[->, acc, thick] (b0) -- (b1) node[midway, above, black, font=\footnotesize] {update};
  \draw[->, thick] (b1) -- (b2) node[midway, above, black, font=\footnotesize] {move};
  \draw[->, acc, thick] (b2) -- (b3) node[midway, above, black, font=\footnotesize] {update};
  \node[font=\footnotesize, anchor=north] at (1.45,-0.75) {percept NSW};
  \node[font=\footnotesize, anchor=north] at (7.1,-0.75) {percept NS};
\end{tikzpicture}
$$

`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](/artificial-intelligence/uncertainty/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.

> **Definition (Online search).** A search paradigm in which the agent interleaves
> planning and acting: it commits to and executes one action, observes the outcome,
> and only then decides the next. Offline search, by contrast, computes the whole
> plan before executing any of it.

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
$\textsc{Result}(s, a)$ except by actually being in $s$ and doing $a$ — it knows
$\textsc{Actions}(s)$, the step cost $c(s,a,s')$ (but only once $s'$ is revealed),
and $\textsc{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.

> **Definition (Competitive ratio).** The ratio of the total cost of the path an
> online agent actually travels to the cost of the shortest path it could have
> taken with full advance knowledge of the state space. A ratio of 1 is
> optimal; unbounded means arbitrarily bad relative to the best possible.

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.

$$
% caption: The adversary argument. After visiting S and A, the two state spaces are
% indistinguishable, so any online agent makes the same choice in both; the
% adversary places the dead end wherever that choice leads. No algorithm avoids
% every dead end.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  nd/.style={draw, circle, minimum size=6mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % space 1
  \node[nd] (s1) at (0,1.2) {S};
  \node[nd] (a1) at (1.3,1.2) {A};
  \node[nd] (g1) at (2.8,1.8) {G};
  \node[nd] (d1) at (2.8,0.6) {};
  \draw[->] (s1) -- (a1);
  \draw[->] (a1) -- (g1);
  \draw[->] (a1) -- (d1);
  \draw[->, red] (d1) to[out=-40,in=-90,looseness=6] (d1);
  \node[red, font=\scriptsize, anchor=west] at (3.2,0.6) {dead end};
  % space 2 (mirror)
  \node[nd] (s2) at (0,-1.4) {S};
  \node[nd] (a2) at (1.3,-1.4) {A};
  \node[nd] (d2) at (2.8,-0.8) {};
  \node[nd] (g2) at (2.8,-2.0) {G};
  \draw[->] (s2) -- (a2);
  \draw[->] (a2) -- (d2);
  \draw[->] (a2) -- (g2);
  \draw[->, red] (d2) to[out=40,in=90,looseness=6] (d2);
  \node[font=\scriptsize, anchor=west] at (3.2,-2.0) {goal here instead};
\end{tikzpicture}
$$

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.

```algorithm
caption: $\textsc{Online-DFS-Agent}$ — depth-first exploration, reversible actions
function ONLINE-DFS-AGENT($s'$):
  persistent: $result$, a table $result[s,a]$; $untried$; $unbacktracked$; $s, a$ (prev, init null)
  if GOAL-TEST($s'$) then return stop
  if $s'$ is a new state (not in $untried$) then $untried[s'] \gets \textsc{Actions}(s')$
  if $s$ is not null then
    $result[s, a] \gets s'$
    add $s$ to the front of $unbacktracked[s']$
  if $untried[s']$ is empty then
    if $unbacktracked[s']$ is empty then return stop
    else $a \gets$ an action $b$ with $result[s', b] = \textsc{Pop}(unbacktracked[s'])$ // backtrack
  else $a \gets \textsc{Pop}(untried[s'])$
  $s \gets s'$
  return $a$
```

$$
% caption: Online DFS on a small maze. The agent starts at S, walks the unexplored
% frontier depth-first (solid arrows), and when it dead-ends it physically retraces
% its steps (dashed) to the nearest state with an untried action. Each edge is
% walked at most twice.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cell/.style={draw, circle, minimum size=7mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (s) at (0,0) {S};
  \node[cell] (a) at (2.0,0) {a};
  \node[cell] (b) at (4.0,0) {b};
  \node[cell] (c) at (2.0,1.6) {c};
  \node[cell] (g) at (4.0,1.6) {G};
  \draw[->, acc, thick] (s) -- (a);
  \draw[->, acc, thick] (a) to[bend left=14] (b);
  \draw[->, dashed] (b) to[bend left=14] (a);
  \draw[->, acc, thick] (a) -- (c);
  \draw[->, acc, thick] (c) -- (g);
  \node[acc, font=\scriptsize, anchor=north] at (1.0,-0.15) {explore};
  \node[font=\scriptsize, anchor=south] at (3.0,0.35) {try b};
  \node[font=\scriptsize, anchor=north] at (3.0,-0.35) {dead end: retrace};
\end{tikzpicture}
$$

Trace it. From `S` the agent pops an untried action, say the one to `a`, and stores
$\mathit{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***.[^aima-lrta] From the current state
the agent looks at each neighbor $s'$, estimates the cost of reaching a goal
_through_ it as $c(s, a, s') + H(s')$, 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.

$$
% caption: LRTA* flattening a local minimum on a one-dimensional line, cost H(s)
% inside each node, edges cost 1. The agent (shaded) is trapped in the dip at the
% third node; each visit raises that node's H estimate, until the raised cost lets
% the agent escape to the right.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={draw, circle, minimum size=7mm, inner sep=0pt, font=\scriptsize},
  cur/.style={draw, circle, minimum size=7mm, inner sep=0pt, font=\scriptsize, double, very thick}]
  \definecolor{acc}{HTML}{2348F2}
  % row (a): initial estimates, agent at the "2" dip
  \node[font=\scriptsize] at (-1.1,0.9) {(a)};
  \node[st] (a0) at (0,0.9) {8};
  \node[st] (a1) at (1.2,0.9) {9};
  \node[cur] (a2) at (2.4,0.9) {2};
  \node[st] (a3) at (3.6,0.9) {2};
  \node[st] (a4) at (4.8,0.9) {4};
  \node[st] (a5) at (6.0,0.9) {3};
  \draw (a0) -- (a1); \draw (a1) -- (a2); \draw (a2) -- (a3);
  \draw (a3) -- (a4); \draw (a4) -- (a5);
  % row (b): after update, H raised to 3, agent moved right
  \node[font=\scriptsize] at (-1.1,-0.9) {(b)};
  \node[st] (b0) at (0,-0.9) {8};
  \node[st] (b1) at (1.2,-0.9) {9};
  \node[st] (b2) at (2.4,-0.9) {3};
  \node[cur] (b3) at (3.6,-0.9) {2};
  \node[st] (b4) at (4.8,-0.9) {4};
  \node[st] (b5) at (6.0,-0.9) {3};
  \draw (b0) -- (b1); \draw (b1) -- (b2); \draw (b2) -- (b3);
  \draw (b3) -- (b4); \draw (b4) -- (b5);
  \node[font=\scriptsize, anchor=south] at (3.0,1.25) {each edge costs 1};
  \node[acc, font=\scriptsize, anchor=west] at (6.5,-0.9) {escapes right};
\end{tikzpicture}
$$

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.

```algorithm
caption: $\textsc{LRTA*-Agent}$ — real-time search that learns $H$ as it moves
function LRTA*-AGENT($s'$):
  persistent: $result$, a table $result[s,a]$; $H$, cost estimates by state; $s, a$ (prev, init null)
  if GOAL-TEST($s'$) then return stop
  if $s'$ is a new state (not in $H$) then $H[s'] \gets h(s')$
  if $s$ is not null then
    $result[s, a] \gets s'$
    $H[s] \gets \min_{b \in \textsc{Actions}(s)} \textsc{LRTA*-Cost}(s, b, result[s, b], H)$
  $a \gets$ an action $b$ in $\textsc{Actions}(s')$ minimizing $\textsc{LRTA*-Cost}(s', b, result[s', b], H)$
  $s \gets s'$
  return $a$

function LRTA*-COST($s$, $a$, $s'$, $H$):
  if $s'$ is undefined then return $h(s)$ // untried: optimistic
  else return $c(s, a, s') + H[s']$
```

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](/artificial-intelligence/logic-and-planning/knowledge-representation)
and [learning](/artificial-intelligence/learning/knowledge-in-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."[^rts]

$$
% caption: The real-time search family, all descended from LRTA*. They differ in
% how much they look ahead each step and how they update the learned heuristic,
% trading per-step cost against total steps to the goal.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum width=30mm, minimum height=6mm, inner sep=2pt, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[bx, draw=acc, thick] (lrta) at (0,0) {LRTA* (Korf 1990)};
  \node[bx] (rta) at (-3.4,-1.5) {RTA*:\\second-best bound};
  \node[bx] (lss) at (0,-1.5) {LSS-LRTA*:\\local search space};
  \node[bx] (fam) at (3.6,-1.5) {game / robot\\route search};
  \draw[->] (lrta) -- (rta);
  \draw[->, acc, thick] (lrta) -- (lss);
  \draw[->] (lss) -- (fam);
\end{tikzpicture}
$$

**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.[^aostar]

**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.[^pomdp]

**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.[^mcts]

## 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](/artificial-intelligence/uncertainty/reasoning-over-time) 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](/artificial-intelligence/logic-and-planning/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](/artificial-intelligence/uncertainty/making-decisions).

[^aima-sensorless]: **AIMA**, §4.4 — Searching with Partial Observations: the belief state as the set of possible physical states; §4.4.1 sensorless (conformant) planning, coercion, the Predict step $b' = \bigcup_{s\in b}\textsc{Results}_P(s,a)$, and belief-state pruning by the subset property; §4.4.2 contingent planning with the prediction–observation–update stages and Equation (4.5).
[^aima-lrta]: **AIMA**, §4.5 — Online Search Agents and Unknown Environments: online vs. offline search, exploration problems, the competitive ratio and the adversary/dead-end argument, safely explorable spaces, Online-DFS-Agent (Figure 4.21), and §4.5.3 LRTA* (Figure 4.24) with its optimism under uncertainty; §4.5.4 relates the local cost updates to reinforcement learning.
[^rts]: **R. E. Korf**, "Real-Time Heuristic Search," _Artificial Intelligence_ 42(2–3), 1990 — introduces LRTA* and RTA*. **S. Koenig & X. Sun**, "Comparing Real-Time and Incremental Heuristic Search for Real-Time Situated Agents," _AAMAS_ 18(3), 2009 — LSS-LRTA* with a bounded local search space. **V. Bulitko & G. Lee**, "Learning in Real-Time Search: A Unifying Framework," _JAIR_ 25, 2006 — a taxonomy of real-time search agents.
[^aostar]: **N. J. Nilsson**, _Principles of Artificial Intelligence_, 1980 — the AO* best-first AND-OR search algorithm. **E. A. Hansen & S. Zilberstein**, "LAO*: A Heuristic Search Algorithm That Finds Solutions with Loops," _Artificial Intelligence_ 129(1–2), 2001 — optimal AND-OR search over cyclic graphs, bridging to MDP planning.
[^pomdp]: **C. Papadimitriou & J. Tsitsiklis**, "The Complexity of Markov Decision Processes," _Mathematics of Operations Research_ 12(3), 1987 — POMDP hardness. **J. Pineau, G. Gordon, S. Thrun**, "Point-Based Value Iteration," _IJCAI_ 2003, and **H. Kurniawati, D. Hsu, W. Lee**, "SARSOP," _Robotics: Science and Systems_ 2008 — scalable point-based POMDP solvers.
[^mcts]: **R. Coulom**, "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search," _Computers and Games_ 2006, and **L. Kocsis & C. Szepesvári**, "Bandit Based Monte-Carlo Planning" (UCT), _ECML_ 2006 — plan-act-replan online search by sampling, with optimism-under-uncertainty exploration.