POMDPs for AI Agents

Reference entry · last updated 20260908

A partially observable Markov decision process (POMDP) is a mathematical model for choosing actions when the underlying state is only partly observed. It describes how actions change the state, what evidence becomes available, and which outcomes earn rewards. [1]

1. First Principles: State and Observation

The state is the underlying situation. An observation is evidence available to the agent about that situation. Different states can produce the same observation, so the agent may have to act before it knows which state it is in. [1]

For an illustrative debugging task, an agent is asked to fix a failing test. It sees an error message but has not yet inspected the code or environment that caused it.

It reads a source file to narrow down possible causes.
It edits the code and runs the test.
The result provides new evidence for its next decision.

Reading a file can give the agent more information without changing the code. Editing changes the code, but the effect still needs checking. Both are actions in this model.

Concept	Debugging example
State	Code and relevant environment details, including the cause of the failure.
Action	Read a file, edit code, run a test, or finish.
Observation	Returned file contents, a tool error, or test output.
Transition	How an action changes the state, such as an edit changing the code.
Observation model	How likely a tool result is, given the resulting state and the action.

2. Reward and Policy

A reward is a numerical score specified by the model designer. It expresses which outcomes the objective favors and can include costs. The reward function gives the expected immediate reward for an action in a state. [2]

One illustrative debugging objective could award 100 points once, when the agent finishes with a correct fix, and subtract one point per tool call. These invented scores express a preference for a correct fix with fewer calls. They are not scores that every coding agent computes.

The score must match the intended task. Rewarding a passing test alone can favor deleting the test or weakening its assertion. Even an unchanged passing test provides evidence within its coverage; it does not prove that the program is correct.

A policy is a rule for choosing the next action from the available history. In the example, a policy might choose another inspection after a failure or a broader test run after a pass. An action can have value because it gathers information that improves later choices. [1]

3. The Mathematical Model

In a stationary POMDP, the transition, observation, and reward rules stay fixed over time. One notation is:

$$\mathcal{M} = \langle \mathcal{S},\mathcal{A},\mathcal{O},\mathcal{T},\mathcal{Z},\mathcal{R},b_0 \rangle$$

$\mathcal{S}$: possible states; $\mathcal{A}$: available actions; $\mathcal{O}$: possible observations.
$\mathcal{T}(s_{t+1}\mid s_t,a_t)$: probability of the next state after an action.
$\mathcal{Z}(o_{t+1}\mid s_{t+1},a_t)$: probability of an observation given the resulting state and action.
$\mathcal{R}(s_t,a_t)$: expected immediate reward.
$b_0(s)$: initial probability distribution over states, given the information available before the first action.

At step $t$, the policy selects an action using the available history $h_t$. The system moves to a new state and produces an observation. A belief distribution can summarize the agent's uncertainty over states and be updated after each action and observation. [1]

For a finite horizon of $H$ decisions, at steps $0$ through $H-1$, one objective is:

$$\pi^* = \arg\max_\pi \mathbb{E}_{\pi,b_0}\left[\sum_{t=0}^{H-1}\gamma^t\mathcal{R}(s_t,a_t)\right]$$

This chooses the policy with the highest expected total reward over those steps. The expectation accounts for uncertainty in the initial state, transitions, observations, and any randomized action choices. [2]

Horizon $H$: the number of decisions considered. The best action may depend on how many steps remain.
Discount factor $\gamma\in[0,1]$: the weight on later rewards. With $\gamma=1$, all steps have equal weight. Smaller values favor earlier rewards.

The horizon and discount factor specify this objective. No separate terminal reward is assumed here. A task that finishes early can enter a terminal state with zero rewards afterward. [2]

4. Assumptions and Limits

Markov state: the state must capture what determines the next-state probabilities and expected reward. Earlier history adds no further information once that state and the action are known.
Stationary rules: the transition, observation, and reward rules above stay fixed over time. A changing environment needs a richer state or a model with time-dependent rules.

These are assumptions about the model, not guarantees about a software project. Missing environment details can make the chosen state description inadequate. [2]

An LLM agent can choose tools and use their results without computing transition probabilities, maintaining a belief distribution, or solving the equation at runtime. The POMDP describes a decision problem; the implementation may use a language model to choose its next action. Its host controls tool execution, permissions, and stopping limits. [3]