An agent is a policy in a loop.
Strip away the branding and every AI agent, from a thermostat to a coding assistant that edits a repository, is the same object: a mapping from what it has seen to what it does next, run repeatedly against an environment that answers back.
This page builds that object up formally, then lets you poke at the parts that matter for research: Bellman backups, search over thoughts, memory retrieval, RL fine-tuning objectives, and why long-horizon reliability is hard.
Observe
The agent never sees \(s_t\) directly. It receives an observation (a tool output, a screenshot, a compiler error) drawn from an emission model, plus possibly a reward.
\[ o_t \sim \Omega(\cdot \mid s_t), \qquad r_t = R(s_{t-1}, a_{t-1}) \]Build context
The sufficient statistic is the belief \(b_t\). LLM agents approximate it with a context-construction map \(C\) that truncates, summarises or retrieves from the history under a window budget \(L\).
\[ h_t = (o_0,a_0,\dots,o_t),\quad b_t(s)=P(s_t{=}s\mid h_t),\quad c_t = C(h_t),\ |c_t|\le L \]Decide
For an LLM agent the policy is the autoregressive distribution over an action string \(y\), which a parser maps to an executable action. Chain-of-thought tokens are part of \(y\).
\[ \pi_\theta(a\mid c_t) = \sum_{y:\ \mathrm{parse}(y)=a}\ \prod_{k} p_\theta(y_k \mid c_t, y_{\lt k}) \]Act
The action is executed by a harness: a shell command, an API call, a click, a message to the user. Actions have side effects; this is what separates an agent from a chatbot.
\[ a_t \in \mathcal{A} = \mathcal{A}_{\text{tools}} \cup \mathcal{A}_{\text{text}} \cup \{\texttt{stop}\} \]Transition
The world moves. The episode ends at a terminal state or a step budget; the return is what we score.
\[ s_{t+1}\sim T(\cdot\mid s_t,a_t),\qquad G_0=\sum_{t=0}^{T}\gamma^t r_t \]The formal setting
Agents live in partially observable sequential decision problems. Most of the theory you need fits in four equations.
POMDP
\[ \mathcal{M} = \langle \mathcal{S}, \mathcal{A}, \mathcal{O}, T, R, \Omega, \gamma, \rho_0 \rangle \]States, actions, observations, transition kernel \(T(s'\mid s,a)\), reward \(R(s,a)\), emission \(\Omega(o\mid s)\), discount \(\gamma\in[0,1)\), initial distribution \(\rho_0\). If \(o_t = s_t\) it collapses to an MDP.
Bayes filter
\[ b_{t+1}(s') \propto \Omega(o_{t+1}\mid s') \sum_{s} T(s'\mid s,a_t)\, b_t(s) \]The belief is a sufficient statistic for the history. A transformer with a long context can be read as learning an amortised, approximate version of this update.
Bellman expectation
\[ Q^\pi(s,a) = R(s,a) + \gamma\, \mathbb{E}_{s'\sim T}\big[\, V^\pi(s') \big],\quad V^\pi(s)=\mathbb{E}_{a\sim\pi}Q^\pi(s,a) \]\(V^\pi\) is the expected return from \(s\) when following \(\pi\). Advantage \(A^\pi = Q^\pi - V^\pi\) says how much better an action is than the policy's average.
Bellman optimality
\[ V^*(s) = \max_{a} \Big[ R(s,a) + \gamma \sum_{s'} T(s'\mid s,a)\, V^*(s') \Big] \]The operator on the right is a \(\gamma\)-contraction in \(\lVert\cdot\rVert_\infty\), so iterating it converges to a unique fixed point. You can watch that happen in §2.
Why this matters for LLM agents. Prompting, tool design and context engineering change \(C\) and \(\mathcal{A}\); fine-tuning changes \(\theta\); scaffolds like search change how \(\pi\) is computed at inference time. Keeping the decomposition explicit makes it easier to say which component a paper actually improved.
Lab: watch a Bellman backup converge
A 7×5 gridworld with a slippery floor. Each sweep applies the optimality operator once to every state. Click empty cells to add or remove walls.
Things to try: push the slip probability up and the greedy arrows start hugging walls away from the pit. Drop the step reward to −0.3 and the agent gets reckless, because surviving costs more than falling in. Lower γ and the goal's influence fades before it reaches the start corner. The error contracts as \(\lVert V_{k}-V^*\rVert_\infty \le \gamma^{k}\lVert V_0-V^*\rVert_\infty\).
Reasoning and planning architectures
LLM agent scaffolds are mostly different answers to one question: how should inference-time compute be spent before committing to \(a_t\)?
Interleave reasoning and acting. ReAct augments the action space with free-form "thoughts" that have no effect on the environment but change the context for the next decision.
\[ \hat{\mathcal{A}} = \mathcal{A}\cup\mathcal{L},\qquad \hat a_t \in \mathcal{L} \Rightarrow s_{t+1}=s_t,\ o_{t+1}=\varnothing \]Cost: one forward pass per step. Weakness: greedy, so an early mistake propagates. Yao et al., 2022.
Thought: Test fails on empty input. Check parser. Action: grep -n "def parse" src/io.py Obs: 41: def parse(buf): Thought: No guard for len(buf)==0. Action: edit src/io.py:42 → add early return Action: pytest tests/test_io.py Obs: 7 passed in 0.31s Action: stop
Verbal reinforcement across episodes. After a failed episode the model writes a self-critique that is stored and prepended to future attempts. Parameters stay frozen; "learning" happens in context.
\[ m_k = \mathrm{LLM}_{\text{reflect}}(\tau_k, r_k),\qquad a_t^{(k+1)}\sim\pi_\theta(\cdot\mid c_t, m_{1:k}) \]Works well when a reliable evaluator \(r_k\) exists (unit tests, exact match). Shinn et al., 2023.
Episode 1 → r = 0 (2/5 tests fail) Reflect: I assumed sorted input; the spec never says so. Sort before merging. Episode 2 (memory: m₁) → r = 1 (5/5 tests pass)
Search over partial solutions. A state is the problem plus a prefix of thoughts. The LM proposes \(k\) continuations, the LM (or a verifier) scores them, and BFS keeps the best \(b\).
\[ S_{t} = \operatorname*{arg\,max}_{S\subseteq S_t',\ |S|=b}\ \sum_{s\in S} V_\theta(s),\quad S_t'=\{[s,z]: s\in S_{t-1},\ z\sim G_\theta(s)\} \]Trades \(O(bk)\) model calls per depth for the ability to backtrack. Yao et al., 2023.
x: use 4 9 10 13 to make 24 ├─ 13-9=4 (left 4 4 10) V=sure │ └─ 10-4=6 (left 4 6) V=sure │ └─ 4*6=24 ✓ ├─ 10-4=6 (left 6 9 13) V=likely └─ 4+9=13 (left 10 13 13) V=impossible ✗ pruned
Monte Carlo tree search with LM priors. Select by an upper confidence bound, expand with LM samples, evaluate with a value model or environment feedback, back up the result. LATS adds reflections at failed leaves.
\[ \mathrm{UCT}(s) = \bar V(s) + c\,\sqrt{\frac{\ln N(\mathrm{parent}(s))}{N(s)}} \]The \(c\) term trades exploration against exploitation and comes from the UCB1 bandit bound. Needs an environment you can reset or simulate. Zhou et al., 2023.
select root → a₂ → a₂₁ (UCT 0.81)
expand sample 3 actions from π_θ
evaluate V(leaf) = 0.6 (LM judge + tests)
backup N += 1, V̄ ← running mean
… × 50 rollouts
commit argmaxₐ N(root, a)
Hierarchy. A planner emits subgoals; an executor solves each; failures trigger replanning. Formally close to the options framework, where an option is a sub-policy with its own initiation set and termination condition.
\[ \omega = \langle \mathcal{I}_\omega,\ \pi_\omega,\ \beta_\omega \rangle,\qquad \beta_\omega: \mathcal{S}\to[0,1] \]Shortens the effective horizon for each decision, which matters given §7. Options: Sutton, Precup & Singh, 1999.
Plan: g₁ reproduce bug g₂ locate root cause g₃ patch + regression test g₄ run full suite exec g₁ … done exec g₂ … β fires: stack trace points elsewhere Replan: g₂' inspect serializer first
Self-consistency
\[ \hat a = \operatorname*{arg\,max}_{a}\ \sum_{i=1}^{n}\mathbb{1}[a_i = a],\quad a_i\sim\pi_\theta \]Majority vote over independent reasoning chains. The simplest test-time scaling baseline every search method should beat.
Best-of-n with a verifier
\[ \hat a = \operatorname*{arg\,max}_{i\le n}\ \hat r(a_i),\qquad P(\text{success}) = 1-(1-p)^n \]The second equality holds only for a perfect verifier and independent samples. Verifier error and correlated failures are where the gap appears.
Tools, memory and context
The context window is the agent's working memory. What goes into it is itself a decision, usually made by a retrieval score.
Tool calls as typed actions
\[ a_t = (f, \mathbf{x}),\ f\in\mathcal{F},\ \mathbf{x}\models\mathrm{schema}(f),\quad o_{t+1}=f(\mathbf{x}) \]A tool is a function with a JSON schema. Toolformer showed models can learn when to call one by keeping calls that lower the loss on the following tokens.
Dense retrieval
\[ \mathrm{rel}(q,m) = \frac{\langle e(q), e(m)\rangle}{\lVert e(q)\rVert\,\lVert e(m)\rVert} \]Cosine similarity between embeddings. Alone, it ignores how recent or how important a memory is.
Paged memory
\[ |c_t| = |c^{\text{main}}_t| + |c^{\text{fifo}}_t| \le L \]MemGPT treats the window like RAM and an external store like disk, with the agent issuing its own page-in and page-out calls.
Each term is min–max normalised over the store (the tilde). Park et al. (2023) use equal weights and λ = 0.995 per game hour.
Learning to act
Scaffolds change how a fixed \(\pi_\theta\) is used. Training changes \(\theta\). Agentic post-training is policy-gradient RL with a KL leash.
REINFORCE with baseline
\[ \nabla_\theta J = \mathbb{E}_{\tau\sim\pi_\theta}\Big[\sum_{t}\nabla_\theta\log\pi_\theta(a_t\mid h_t)\,\big(G_t - b(h_t)\big)\Big] \]Unbiased for any baseline \(b\) that does not depend on \(a_t\). For LLMs, \(\log\pi_\theta(a_t\mid h_t)\) is a sum of token log-probs.
KL-constrained objective
\[ \max_{\pi}\ \mathbb{E}_{y\sim\pi}[r(x,y)] - \beta\,D_{\mathrm{KL}}\big(\pi(\cdot\mid x)\,\Vert\,\pi_{\mathrm{ref}}(\cdot\mid x)\big) \]\[ \Rightarrow\ \pi^*(y\mid x)=\tfrac{1}{Z(x)}\,\pi_{\mathrm{ref}}(y\mid x)\,e^{r(x,y)/\beta} \]The closed form is what makes DPO possible.
DPO
\[ \mathcal{L}_{\mathrm{DPO}} = -\mathbb{E}\Big[\log\sigma\Big(\beta\log\tfrac{\pi_\theta(y_w\mid x)}{\pi_{\mathrm{ref}}(y_w\mid x)} - \beta\log\tfrac{\pi_\theta(y_l\mid x)}{\pi_{\mathrm{ref}}(y_l\mid x)}\Big)\Big] \]Substitute \(\pi^*\) into a Bradley–Terry model and \(Z(x)\) cancels. No reward model, no sampling during training.
GRPO
\[ \hat A_i = \frac{r_i - \mathrm{mean}(r_{1:G})}{\mathrm{std}(r_{1:G})},\qquad r_i = \mathbb{1}[\text{tests pass on }\tau_i] \]Sample a group of \(G\) trajectories per task and use the group as the baseline. Drops the critic network, which is attractive when episodes are long tool-use traces.
With \(\hat A>0\) the objective stops rewarding increases in \(\rho\) beyond \(1+\epsilon\); with \(\hat A\lt 0\) it stops rewarding decreases below \(1-\epsilon\). The gradient is zero on the flat parts, which keeps each update close to the sampling policy.
Multi-agent systems
Several policies sharing one environment. The theory comes from game theory; most current LLM practice is cooperative.
Markov game
\[ \mathcal{G}=\langle \mathcal{N},\mathcal{S},\{\mathcal{A}_i\}_{i\in\mathcal{N}},T,\{R_i\}_{i\in\mathcal{N}},\gamma\rangle \]Transitions depend on the joint action \(\mathbf{a}=(a_1,\dots,a_n)\). Identical \(R_i\) gives a cooperative team; \(R_1=-R_2\) gives a zero-sum game.
Nash equilibrium
\[ V_i^{(\pi_i^*,\,\pi_{-i}^*)}(s)\ \ge\ V_i^{(\pi_i,\,\pi_{-i}^*)}(s)\quad \forall i,\ \pi_i,\ s \]No agent gains by deviating alone. From each agent's view the others make the environment non-stationary, which breaks single-agent convergence guarantees.
Debate and voting
\[ P(\text{majority correct}) = \sum_{k>n/2}\binom{n}{k}p^k(1-p)^{n-k} \]Condorcet's jury theorem says this tends to 1 for \(p>\tfrac12\), but only with independent errors. Copies of one model share failure modes, so the real gain is smaller. Du et al. (2023) study rounds of debate.
Evaluation and reliability
Long tasks multiply small error rates. Choose your metric to match whether you care about capability or dependability.
Assumes independent, unrecoverable errors. Real agents can notice and repair mistakes, which is exactly what makes error recovery worth studying. METR (2025) measures capability as the human task length at which success falls to 50%.
Unbiased estimators from \(n\) samples with \(c\) successes (Chen et al., 2021; Yao et al., 2024). pass@k asks "can it ever?"; pass^k asks "does it every time?". A deployed agent is judged on the second.
| Benchmark | Environment | Success signal | Watch out for |
|---|---|---|---|
| SWE-bench | Real GitHub issues in Python repos; agent edits code | Hidden unit tests pass | Under-specified issues, weak tests; use the human-validated Verified subset |
| WebArena | Self-hosted e-commerce, forum, GitLab, CMS sites | Functional check of final site state | Long-horizon navigation, brittle evaluators |
| OSWorld | Full desktop OS via screenshots and input events | Execution-based scripts per task | Grounding clicks to pixels; slow episodes |
| GAIA | Open questions needing browsing, files, tools | Exact-match short answer | Contamination once answers leak online |
| τ-bench | Simulated user plus domain APIs and policy docs | Database end state matches goal; pass^k | Policy following, user simulator variance |
Open problems worth a thesis
Each one has a crisp formal core and a messy empirical reality.
Long-horizon credit assignment
\[ \mathrm{Var}\Big[\textstyle\sum_t \nabla\log\pi\, G_t\Big] \text{ grows with } T \]Sparse terminal rewards over hundreds of tool calls give high-variance gradients. Process rewards, learned critics and hindsight relabelling are partial answers.
Reward hacking
\[ \operatorname*{arg\,max}_\pi J_{\hat R}(\pi)\ \ne\ \operatorname*{arg\,max}_\pi J_{R}(\pi) \]Optimising a proxy \(\hat R\) (tests, judges) eventually exploits its gaps. Goodhart's law with a gradient. How do we bound the divergence?
Safe action spaces
\[ \pi_{\text{safe}}(a\mid h) \propto \pi(a\mid h)\,\mathbb{1}[a\in\mathcal{A}_{\text{safe}}(h)] \]Prompt injection turns observations into adversarial inputs. Sandboxing, permissioning and constrained MDPs meet systems security here.
Calibrated stopping
\[ \text{stop iff } \hat P(\text{success}\mid h_t) \ge \kappa \]Knowing when to ask the user, when to give up and when it is done. Requires calibrated self-assessment, which current models lack.
Test-time compute scaling
\[ \text{perf}(C) \text{ for } C = n_{\text{samples}}\times\text{depth}\times\text{tokens} \]How should a fixed inference budget be split between sampling, search and longer chains? Scaling laws here are still mostly empirical.
Valid evaluation
\[ \widehat{\text{acc}} \pm z\sqrt{\hat p(1-\hat p)/N} \]Many agent benchmarks have a few hundred tasks, noisy graders and contamination risk. Report confidence intervals and multiple seeds.
Reading list
The primary sources behind each section. Filter by topic.