Agents as Markov Decision Processes¶

Agentic AI · L-MDP

A formal lens on agent decision-making: states, actions, observations and rewards — the language in which agent benchmarks, evaluations and safety arguments are written.

This is the MDP framing for agents — the vocabulary, not the solution methods. Solving an MDP (returns and discounting, the Bellman equations, optimal policies, exploration–exploitation, options) belongs to a reinforcement-learning course and is out-of-scope.

Learning Objectives¶

1. Define an MDP and the Markov property; read the dynamics $p(s',r\mid s,a)$ — how likely the next state $s'$ and the reward $r$ are, after action $a$ in state $s$.
2. Define a policy $\pi(a\mid s)$ — which action in which state — and the state-value $v_\pi$ — the reward still to come from a state — and say what a trajectory is.
3. Explain decision theory (probability + utility → MEU) as the single-decision foundation, and name its sequential and multi-agent generalisations.
4. Map an LLM agent onto an MDP, and say why it is strictly a POMDP — the agent conditions on its context, not on the world state.
5. Read the goal-conditioned policy $\pi(a\mid g,s,m)$ a benchmark actually specifies — the action given the goal $g$, the state $s$ and the memory $m$ — and say what follows for evaluation.
6. Say who is the environment in a given formalisation — the human, the world, or the language model itself — and read prompting as an MDP whose actions are DECOMPOSE, RANK, SUMMARIZE.
7. Read the deliberation strategies of → L-ReAct, → L-Decomp and → L-ToT as three ways of computing one policy, differing only in how much computation the harness spends per action.
8. Reason about reward mis-specification ⚖️ and its twin goal misgeneralization, and about uncertainty over the objective (assistance games, corrigibility).

Overview¶

A Markov decision process (MDP) is a formal model of sequential decision-making: an agent selects actions, and an environment answers each action with a next state and a reward. Part I defines the model, Part II maps an LLM agent onto it, and Part III treats a reward that does not express the intended objective:

Part I — Markov Decision Processes¶

A Markov decision process (MDP) describes sequential decision-making by a state space, an action space, a dynamics function and a discount factor: a policy selects an action in each state, and the value of a state is the expected discounted reward that follows that state.

The Agent–Environment Interface¶

At each discrete time step $t=0,1,2,\dots$ the agent observes a state $S_t$ from the state space $\mathcal S$, takes an action $A_t$ from the action space $\mathcal A$, and the environment answers with a scalar reward $R_{t+1}\in\mathbb R$ and a next state $S_{t+1}$:

This produces a trajectory $S_0, A_0, R_1, S_1, A_1, R_2, \dots$ — the run of the agent, written out. Its behaviour is a policy $\pi(a\mid s)$: the probability of choosing action $a$ when the state is $s$. The goal is to maximise long-run reward, not the immediate one (Sutton & Barto, 2018).

(Three alphabets, three roles — the course convention: calligraphic $\mathcal S,\mathcal A$ are the sets (state and action space), capitals $S_t, A_t, R_t$ are the random variables — which state, action and reward actually occurred at $t$ — and lowercase $s,a,r$ are the values they take, the ones we write inside a formula.)

Decision Theory: The Single-Decision Foundation¶

Under uncertainty, a rational agent takes the action with the best expected outcome (→ L-Intro). The formal machinery for that is decision theory = probability theory + utility theory (Russell & Norvig, 2021, §1.1): let $\omega\in\Omega$ be an outcome the action may lead to, $P(\omega\mid a)$ the probability of that outcome given action $a$, and the utility $U(\omega)\in\mathbb R$ how much the agent values it. A decision-theoretic agent then takes the action $a^{*}$ of maximum expected utility (MEU): $$ a^{*}=\arg\max_{a}\;\mathbb E[\,U\mid a\,]=\arg\max_{a}\sum_{\omega\in\Omega}P(\omega\mid a)\,U(\omega). $$

An MDP is decision theory made sequential: instead of one action's expected utility, we maximise the expected return $G_t$ (the reward still to come after step $t$, defined below) over a whole trajectory — utility becomes reward-to-go.

The MDP Formalism¶

A finite Markov Decision Process is $(\mathcal S, \mathcal A, p, \gamma)$:

• $\mathcal S$ the finite state space, and $\mathcal A$ the finite action space.
• Dynamics $p$ — one distribution that captures transitions and rewards, where $s'$ is the next state and $r$ the reward the pair $(s,a)$ produces: $$ p(s',r\mid s,a)=P(\,S_{t+1}{=}s',\, R_{t+1}{=}r \mid S_t{=}s,\, A_t{=}a\,). $$ Both letters appear on purpose: capital $P$ is the formal probability operator that acts on explicit random variable events, whereas lowercase $p$ is the shorthand function name used to evaluate and manipulate those exact probabilities algebraically. Everything the model induces keeps that letter: $p(s'\mid s,a)$, the start distribution $p(s_0)$, the trajectory distribution $p_\pi(\tau)$.
• From it: the transition $p(s'\mid s,a)=\sum_r p(s',r\mid s,a)$ and the expected-reward function $r(s,a)=\mathbb E[R_{t+1}\mid s,a]=\sum_r r\sum_{s'} p(s',r\mid s,a)$ — the letter $r$ bare is a reward value, $r(s,a)$ with arguments is the function (Sutton & Barto's convention).

Markov property: the future depends only on the current $(s,a)$, not the full history — it is the Markov chain of the training ladder, now with actions.

Reward¶

Reward hypothesis (Sutton & Barto): goals can be framed as maximising expected cumulative reward. The reward $R_{t+1} \in \mathbb{R}$ is a scalar feedback signal emitted by the environment at time $t+1$ that evaluates the quality of taking action $a_t$ in state $s_t$. The underlying reward function $r: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ deterministically or stochastically maps state-action pairs to this scalar value: $R_{t+1} = r(s_t, a_t)$.

The reward function is not a mere detail of the model—it is the formal specification of the task, and everything the agent does follows from it.

• The agent maximises long-run reward, not just immediate feedback. Written out, that is the discounted return: $$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{i=0}^{\infty}\gamma^{i} R_{t+i+1}, $$ with the discount factor $\gamma\in[0,1)$ weighting sooner rewards over later ones.
• What matters here is the modelling step: writing the reward function $r(s,a)$ down is an active design decision. In agentic workflows, it is usually sparse (e.g., binary task completion tests), and getting it wrong is a primary failure mode (see Reward Mis-Specification below).

Macro vs. Micro Actions

In LLM literature, you will see two levels of abstraction for "actions":

• Micro-Level (Token-by-Token): An action $a_t$ is a single token. This is used when analyzing model internals, value functions ($v_\pi$), beam search, or RLHF fine-tuning (e.g., PPO).
• Macro-Level (Turn-by-Turn): An action $a$ is a complete generated output (an entire message or tool call). This is used when evaluating multi-turn agent benchmarks or high-level planning.

Policy & Value¶

• Policy $\pi(a\mid s)$ — The agent’s strategy mapping a state $s$ (the active context window: instructions, history, tool outputs) to an action $a$ (the generated tokens or tool call). For an LLM agent, $\pi$ is the full system producing this mapping: model weights, system rules, sampling parameters, and runtime loop.
• State-value $\;v_\pi(s)=\mathbb E_\pi\!\left[G_t \mid S_t=s\right]$ — the expected return from $s$, where the subscript $\pi$ says the expectation is taken over trajectories the agent generates by following $\pi$: how good is it to be here, if I keep behaving this way?

Viewing token generation as a sequence of decisions—each with an expected outcome value $v_\pi$—helps identify which tokens truly matter. A step where different token choices cause a large swing in expected value is a choice point, where the model's decision significantly alters the final output quality.

Part II — LLM Agents as MDPs¶

An LLM agent is a partially observable MDP (POMDP), an MDP in which the agent receives an observation instead of the state: the policy is the language model together with its prompt, tools and loop, and the choice of the environment — the human, the external world or the language model — fixes the meaning of every symbol.

An LLM Agent as an MDP¶

• State = the conversation / context so far (+ world state). The agent sees only an observation, not the full world state → strictly a POMDP (partially observed). (Indices: $t$ is MDP time, $k$ the agent-loop step of — one loop step is one MDP step, so $k=t$ here.)
• Action = emit text / call a tool.
• Transition = a tool result / user reply updates the state.
• Reward = task success (often sparse, and hard to specify).

Just-in-time planning = choosing the next action from the current state — acting in the MDP without a stored plan. The weights never change: the policy is the model plus the prompt, the tools and the loop around it, so the harness computes $\pi$ at inference time — which is why changing the system-prompt or the runtime changes the policy.

Reinforcement learning is the contrasting case: it tunes the policy by changing the model against the reward — training, before deployment, and out of scope here (see the excursion).

The POMDP a Benchmark Actually Uses¶

The mapping on the previous slide is not only a teaching device — it is how agent benchmarks define their tasks. AgentBoard (Ma et al., 2024) relies on the Partially Observable Markov Decision Processes (POMDPs) fomalism. Nine text environments are specified as the tuple

$$\mathcal{M} = \langle g,\; \mathcal S,\; \mathcal A,\; \mathcal O,\; \mathcal T \rangle$$

— with goal $g$, state space $\mathcal S$, action space $\mathcal A$, observation spaces $\mathcal O$ (including environment feedback), and transition function $\mathcal T: \mathcal S \times \mathcal A \rightarrow \mathcal S$.

Here we have a deterministic $\mathcal{T}$: Given a specific current state $s_t$ and action $a_t$, the environment produces one specific next state $s_{t+1} = \mathcal{T}(s_t, a_t)$ with $100\%$ certainty.

State vs. Observation¶

• State ($s_t$): The complete, true, and underlying condition of the entire environment at time $t$. It includes all information—both visible and hidden—necessary to fully determine the environment's dynamics.
• Observation ($o_t$): The partial view or signal of the state that the agent actually receives from the environment at time $t$.

Why the Distinction Matters for LLM Agents

In a Fully Observable MDP, the agent directly sees the true state ($o_t = s_t$). However, an LLM agent operates in a POMDP (Partially Observable MDP):

• The full environment state $s_t$ includes hidden variables like external database contents, unseen API backends, or the human user's internal mental state.
• The agent only sees the observation $o_t$—such as the latest user text response, tool outputs, or API return values.
• Because $o_t$ alone does not contain the full state, the agent must maintain a memory history ($m_t$) of past observations and actions to approximate the missing state information when making decisions.

Memory¶

The agents predictions at step $t$ are based on the goal and the memory $m_t$. The memory is written explicitly as the interleaved history sequence of actions and observations:

$$m_t = \{o_j, a_j, o_{j+1}, a_{j+1}, \dots, o_t\},\qquad 0 \le j < t.$$

A trajectory $\tau = [s_0, a_0, s_1, a_1, \dots, s_n]$ of $n$ steps — one concrete run, hence lowercase — then has probability, with $p(s_0)$ the distribution the environment starts from,

$$p_\pi(\tau) \;=\; p(s_0)\prod_{t=0}^{n-1} \pi(a_t \mid g,\, s_t,\, m_t)\; T(s_{t+1}\mid s_t, a_t).$$

By writing $\pi(a_t \mid g, s_t, m_t)$, the authors took a standard mathematical shortcut called collapsing the observation step.

The Fully Rigorous POMDP FactorizationIn a true POMDP, the complete joint distribution over states, observations, and actions expands to (noting that in Transformer-based agents, memory $m_t$ acts as an implicit, uncompressed belief state):

$$p_\pi(\tau) = p(s_0) \prod_{t=0}^{n-1} \underbrace{p(o_t \mid s_t)}_{\text{Observation Step}} \cdot \underbrace{\pi(a_t \mid g, m_t)}_{\text{Agent Policy}} \cdot \underbrace{T(s_{t+1} \mid s_t, a_t)}_{\text{State Transition}}$$

Three things are worth reading off that product.

1. The policy is conditioned on $m_t$, not just $s_t$. The memory $m_t$ is the agent's context window $c_t$. Conditioning on history is precisely how a partially observed agent operates: because $s_t$ is unobservable, the agent uses historical observations to maintain an implicit belief state. When context truncation/compression (see L-Memory) drops past turns to fit token limits, it fundamentally alters the policy's input distribution, not merely its compute overhead.
2. The index $j > 0$ formalizes the context window. Setting a lower history bound $j$ models sliding-window truncation. Rather than halting the agent when context fills, dropping older observations shifts $j$ forward—a core design decision that appears directly in the math as the dynamic start of the history sequence.
3. The goal $g$ sits inside the policy. A goal-conditioned policy $\pi(a_t \mid g, s_t, m_t)$ is the formal representation of "the task instruction lives in the system prompt." Because $g$ directly conditions the policy distribution, modifying the prompt alters the policy itself, making prompt engineering and policy evaluation mathematically inseparable.

Three MDPs, Differing in Who Is the Environment¶

The mapping above places the human and the physical world on the environment side. This is a choice of agent-environment boundary, not an inherent property of the LLM. Following the conceptual framework in Yang et al. (2023), we can construct three distinct MDP factorizations for the same underlying system by shifting where the boundary is drawn:

Dialogue MDP (Human-as-Environment)¶

In the Dialogue MDP, the human interlocutor serves as the environment $\mathcal{T}$, while the combination of the language model and its scaffold acts as the agent policy $\pi$.

The Dialogue framework is defined by the tuple $\mathcal{M}_{\text{dialogue}} = \langle g, \mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{T} \rangle$:

• Goal ($g$): The overarching conversational objective or user intent supplied in the system context.
• State Space ($\mathcal{S}$): The ground-truth state of the environment, including the unobservable mental state, intent, and satisfaction of the human interlocutor at time $t$.
• Action Space ($\mathcal{A}$): Natural language utterances generated by the agent policy: $a_t \sim \pi(\cdot \mid g, m_t)$.
• Observation Space ($\mathcal{O}$): The visible natural language user messages received by the agent scaffold.
• State Transition & History Updates ($\mathcal{T}$ - here probabilistic): The human's cognitive dynamics $\mathcal{T}(s_{t+1} \mid s_t, a_t)$ yield a new ground-truth state $s_{t+1}$ and emit an observation $o_{t+1} \sim P(o_{t+1} \mid s_{t+1})$. The agent updates its context memory $m_t$ via concatenation: $$m_{t+1} = m_t \mathbin{\Vert} a_t \mathbin{\Vert} o_{t+1}$$

Crucial Insight: The Markov property is bought, not assumed. It holds for the agent's internal history representation $m_t$ because $m_t$ is defined as the complete sequence of past turns up to time $t$, serving as an uncompressed belief state proxy. This forces $m_t$ to grow monotonically, directly causing the context-window limits that dynamic memory architectures must manage.

Tool use¶

Tools use extends the same history-concatenation mechanics to a hybrid action space (see L-ReAct):

$$ \hat{\mathcal{A}} \;=\; \mathcal{A} \cup \mathcal{L}, $$ (where $\mathcal{A}$ is the external action space (tool calls) and $\mathcal{L}$ the language space (free-form text)).

This hybrid action space introduces three fundamental decision sub-problems unique to tool environments:

1. Tool Invocation: Deciding when to execute an external tool versus generating raw text ($a_t \in \mathcal{A}$ vs. $a_t \in \mathcal{L}$).
2. Tool Selection: Selecting which specific tool $a_{\text{tool}} \in \mathcal{A}$ addresses the immediate sub-goal.
3. Parameter Construction: Structuring arguments or reformulating queries if previous tool outputs $o_t$ were unhelpful or returned errors.

Iterative Prompting (Harness-as-Agent MDP)¶

Iterative prompting is a control framework that inverts the standard LLM agent boundary, modeling the interaction as a Markov Decision Process (MDP) where a program execution wrapper (the harness/scaffold) serves as the acting policy $\pi$, and the parametric Language Model (LLM) acts as the state-transition environment $\mathcal{T}$. In hybrid implementations, the policy boundary may expand beyond pure code to include auxiliary models (e.g., LLM_plan or LLM_judge) or human-in-the-loop interventions to execute specific operators.

A prompting scheme becomes a policy over high-level structural actions that map string states to string outputs:

Two fundamental properties follow from this formulation:

1. Decomposition and compaction inhabit a unified action space ($\mathcal{A}_{\text{harness}}$). Every action consumes context tokens and alters the state $s_t$. Deciding when to compact memory via SUMMARIZE/PRUNE or divide tasks via DECOMPOSE is an active control optimization performed by the policy, rather than an external exception-handling routine.
2. The reward function is an explicit goal test predicate. $\mathcal{R}(s_t, a_t) = 1$ if the language model's generated state successfully satisfies the target goal test, and $0$ otherwise. This sparse binary reward function directly implements the $\text{done}$ termination predicate of the execution loop.

Crucial Conceptual Boundary: Which structural reading you adopt dictates the precise physical meaning of every variable:

• Dialogue: Environment = Human Interlocutor; Policy = Model + Scaffold
• Tool Use: Environment = External World/APIs; Policy = Model + Scaffold
• Prompting: Environment = Language Model Itself; Policy = Scaffold (or Scaffold + Auxiliary Models)

Conflating these boundaries within a single analysis is the primary source of formal confusion in LLM literature. The Prompting MDP does not deny that an LLM generates text; rather, it asserts that when the primary object of system design is the prompting scheme, the model functions formally as the state-transition dynamics $\mathcal{T}$ being acted upon.

Deliberation Strategies as Formulations of Policy $\pi$¶

The entire landscape of planning and reasoning methods simplifies down to a single question: How does the policy $\pi$ select an action $a$?

In this unified view, ReAct, explicit planning, and Tree-of-Thoughts are not different agent architectures—they are three different search strategies used by the policy $\pi$ to choose an action, differing only in how much compute the harness spends before committing to $a_t$.

• Policy Boundary ($\pi$): The composite decision-making system formed by the Scaffold Loop + LLM Call(s).
• Environment Boundary ($\mathcal{T}$): The external target system being acted upon—either the External World/APIs (in Tool Use) or the Primary LLM context (in Prompting).

Deliberation Strategies (Inference-Time Search over Fixed Policy $\pi_\theta$)¶

Key Takeaways¶

1. The Core Agent Loop Is Invariant. All three planning approaches run inside the exact same control loop: the policy requests actions, and the harness control plane executes them against the environment. Deliberation simply shifts locations across the stack:

   • ReAct: Inside the LLM's token generation context.
   • Explicit Planning: Into a structured DAG object managed by the harness.
   • Tree Search (ToT): Into a graph search algorithm executed by the harness.

   ReAct is not the agent loop. ReAct is simply the cheapest, single-sample policy that runs inside it.

2. Inference-Time Search Trades Compute for Accuracy. Expanding a search tree (ToT) buys what additional compute always buys in an MDP: a mathematically superior estimate of $Q^*(s_t, a_t)$—the action that maximizes expected cumulative return. However, inference-time search can only optimize action selection over the given reward function; it cannot fix a fundamentally mis-specified reward $\mathcal{R}$.

Post-Training RL as Internalized Deliberation¶

The same MDP formalism used to build agent harnesses also explains how reasoning models (e.g., DeepSeek-R1, OpenAI o1) are trained.

By treating each generated token or thought as an action $x_t$, the state as the preceding prompt and text history $x_{1:t-1}$, and applying standard policy gradient updates:

$$\nabla_\theta J(\pi_\theta) \;=\; \mathbb{E}_\tau\!\left[\sum_{t=1}^{T} \nabla_\theta \log \pi_\theta(x_t \mid x_{1:t-1})\; A(s_t, a_t)\right]$$

(where $A(s_t, a_t)$ is the advantage—a scalar weighting that reinforces token sequences leading to higher-than-average final rewards).

This optimization yields two critical insights for agent engineering:

1. Unfaithful Reasoning: Outcome-based rewards ($\mathcal{R}_{\text{final}}$) optimize solely for correct final answers, not factual reasoning steps—explaining why internal chains of thought can be plausible yet unfaithful.
2. Search Location: RL pushes search into the model weights ($\theta$). The model deliberates within a single forward generation, making intermediate reasoning steps (thoughts) invisible and uninterruptible to the harness.

Part III — Objective Specification¶

The reward function is the formal specification of the task: an agent that maximises a reward which does not express the intended objective optimises the wrong objective, and an assistance game models an agent that is uncertain about the objective and infers it from the behaviour of the human.

⚖️ Responsible AI — Reward Mis-Specification¶

Reward Misspecification¶

If the reward is wrong, a capable agent will optimise the wrong thing (reward hacking / Goodhart's law). Sparse, gameable, or proxy rewards are dangerous — a core AI-safety concern, and the reason the specification of the reward matters as much as the optimisation of it.

Specify goals well — SMART. A good objective is Specific, Measurable, Achievable, Relevant, Time-bound; a vague or gameable one is a mis-specified reward (monitored in → L-Eval).

Goal Misgeneralization: Competently Pursuing the Wrong Objective¶

Reward mis-specification is only one of two major goal-alignment failure modes. Goal misgeneralization occurs when the task specification $r(s,a)$ is completely correct, yet the system competently pursues a proxy goal at runtime (Shah et al., 2022).

Failure Mode Taxonomy¶

Key Mechanism: Underdetermination & Proxies¶

Goal misgeneralization happens because training or test environments are underdetermined: multiple distinct goals yield identical, successful behavior under normal conditions.

• The Canonical Gridworld Example: An agent is trained to collect apples (+1) and avoid monsters (−1), using shields for protection. When tested in an extended environment with zero monsters, it endlessly gathers shields instead of apples.
  • Diagnosis: The reward function was never broken—shields yielded 0 reward. However, because shields and survival were correlated in early trials, the agent learned the proxy goal ("gather shields") rather than the intended goal ("gather apples").
• The Fix is Coverage, Not Reward: Fixing goal misgeneralization requires adding test cases that decouple the proxy goal from the true goal, forcing the agent to distinguish between them.

Takeaway for Inference Scaffolding & Prompt Engineering¶

Even without updating model parameters $\theta$, prompt instructions, few-shot examples, and unit tests serve as the agent's "training situations."

If your prompt examples or test suites fail to decouple proxy behaviors from your true intent, the agent will pass every benchmark test during development, only to execute something confidently wrong on its first novel deployment case.

Scaffolding Rule: Build evaluation sets specifically designed to separate proxy shortcuts from true goals, rather than just testing happy paths.

Uncertainty about the Objective: Assistance Games ⚖️¶

Reward mis-specification assumes the agent has a fixed reward function $r$ — just the wrong one. A deeper response is to let the agent stay uncertain about the true objective and treat the human's reward as something to be inferred, not assumed.

Formally this is an assistance game (Russell & Norvig, 2021, §17.2.5): a two-player game between a human and a robot in which both maximise the human's payoff parameter $\theta$, but only the human observes $\theta$; the robot holds a prior $P(\theta)$ and updates it from what the human does. Solving it reduces to a POMDP whose hidden state includes the preference parameters $\theta$ — i.e. objective uncertainty is just more partial observability, on top of the POMDP view of an LLM agent above.

Two consequences matter for safe agents:

• The off-switch / corrigibility result. An agent uncertain about the human's objective has a positive incentive to defer — to ask, and to allow itself to be switched off — because being corrected is evidence about $\theta$, which it wants. An agent certain of its (possibly wrong) reward will resist shutdown. Uncertainty ⇒ corrigibility.
• Provably beneficial AI. Behaviours we might hand-script — asking permission, learning from demonstration, teaching — emerge from the equilibrium rather than being bolted on (Russell, 2019, Human Compatible).

The standard-model limit. This is the flip side of the rational agent whose objective we supply: when the objective is hard to specify completely — the norm for real tasks — the safer design is an agent uncertain about the reward, not one confidently maximising a proxy. The human oversight enforced at the gateway (→ L-Gateway) is the operational face of this same idea.

In Practice / This Week's Lab¶

• Formulate an MDP for a support agent — $\mathcal S$, $\mathcal A$, a transition, $r$ — and name one way the reward could be mis-specified.
• The off-switch calculation: an agent uncertain about the human's payoff prefers to defer; redo it for an agent that is certain, and read off why uncertainty buys corrigibility.

Summary¶

• Decision theory (probability + utility → MEU) is the single-decision foundation; an MDP is its sequential form, and game theory its multi-agent form.
• MDP $(\mathcal S,\mathcal A,p,\gamma)$ with dynamics $p(s',r\mid s,a)$ formalises sequential decisions; Markov = memoryless in the state. A run is a trajectory $S_0,A_0,R_1,S_1,\dots$ — the unit an agent is evaluated on.
• Policy $\pi(a\mid s)$, value $v_\pi$. The MDP is a modelling framework: it describes an agent running on a fixed checkpoint just as well as one being trained. Solving it is a reinforcement-learning question and is out of scope — see excursions/solving-mdps/.
• An LLM agent maps on: state = context / observation (→ POMDP), action = text/tool, reward = success. The benchmark's own form is goal-conditioned, $\pi(a\mid g,s,m)$ — so the prompt is inside the policy, and prompt and model cannot be evaluated separately.
• "Environment" and "policy" are role assignments, not facts. The same agent is three MDPs depending on where the boundary is drawn — the human (dialogue), the world through tools, or the model itself, with the harness as policy and DECOMPOSE / SUMMARIZE as its actions. In dialogue the state is the whole history, so the Markov property is bought by definition — and so is the unbounded growth memory management has to absorb.
• The three strategies are one policy computed three ways — the loop and the architecture never changed, only how much computation the harness spends before committing to an action.
• Reward mis-specification is one of two ways to get the wrong goal; goal misgeneralization is the other, and it is fixed by training coverage, not by a better reward. Uncertainty about the objective (assistance games) turns it into a latent $\theta$ to infer — a POMDP over preferences — yielding corrigibility (the off-switch result).

References¶

Peer-reviewed papers

• Hadfield-Menell, Dylan, et al. "The Off-Switch Game." Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), 2017. — objective uncertainty ⇒ deference. (Further reading, safe objectives.)
• Ma, Chang, et al. "AgentBoard: An Analytical Evaluation Board of Multi-turn LLM Agents." Advances in Neural Information Processing Systems. Vol. 37. 2024. arXiv:2401.13178. — nine text agent environments specified as POMDPs $\langle g, S, A, O, T\rangle$, with the goal-conditioned trajectory distribution $p_\pi(\tau)$ and the agent's history $m_t$ written out. The same paper supplies the progress rate used in evaluation.
• Yao, Shunyu, et al. "Tree of Thoughts: Deliberate Problem Solving with Large Language Models." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.10601. — deliberate search as a way of computing the policy, and its token cost relative to CoT.

Preprints & other non-peer-reviewed papers

• Shah, Rohin, et al. "Goal Misgeneralization: Why Correct Specifications Aren't Enough For Correct Goals." arXiv preprint arXiv:2210.01790 (2022). — the distinction from specification gaming; the definition with its capability clause; the Monster Gridworld example in which the reward is correct and training diversity is the fix.
• Yang, Sherry, et al. "Foundation Models for Decision Making: Problems, Methods, and Opportunities." arXiv preprint arXiv:2303.04129 (2023). — §2.1.1 the MDP written with reward and transition apart, $\langle \mathcal S,\mathcal A,\mathcal R,\mathcal T,\mu,\gamma\rangle$, and the POMDP restriction that "policies can only depend on observations and previous actions"; §5 the three formalisations — dialogue ($s_t=\{\tau_{<t},e_t\}$), tool use (the when / which / how decisions), and prompting as an MDP with the language model as the environment and DECOMPOSE / RANK / SUMMARIZE / PRUNE as high-level actions; §4.2 why a task specified in language beats a scalar reward.

Textbooks & monographs

• Russell, Stuart. Human Compatible: Artificial Intelligence and the Problem of Control. Viking, 2019. (Further reading, safe objectives.)
• Russell, Stuart, and Peter Norvig. Artificial Intelligence: A Modern Approach. 4th ed., Pearson, 2021. — §1.1 decision theory = probability + utility → maximum expected utility (MEU) (the single-decision foundation the MDP makes sequential); §17.2.5 uncertain payoffs & assistance games (Ch. 17 Global Ed.; = US-ed. Ch. 18) — the off-switch/corrigibility result and its reduction to a POMDP over preferences.
• Sutton, Richard S., and Andrew G. Barto. Reinforcement Learning: An Introduction. 2nd ed., MIT Press, 2018. — Ch. 3 (Finite MDPs): the agent–environment interface, the trajectory, the dynamics $p(s',r\mid s,a)$ and the reward hypothesis. The solution machinery this week does not develop — returns and discounting, value functions, the Bellman (optimality) equations, exploration–exploitation — is in Ch. 2–4 and Ch. 8, and is worked through in excursions/solving-mdps/.