Hierarchical, Symbolic, Language, and Multi-Agent Planning

Much of the planning machinery introduced so far in Part VII: Planning and Agency is easiest to present at the primitive-action level: torque commands, joint velocities, discrete moves, or token-level gestures. That representation becomes awkward when one task spans thousands of decisions. A robot retrieving a mug from a cabinet or negotiating a traffic merge needs feedback at the motor level, but its task planner should not enumerate every motor command. Long primitive rollouts also expose a learned world model to compounding error and states outside its training support.

The combinatorics are easy to see. If a task requires $T$ primitive timesteps and the agent has $|\mathcal{A}|$ actions at each step, a naive full tree has $|\mathcal{A}|^T$ leaves. Four moves over fifty steps already give $4^{50} \approx 1.3 \times 10^{30}$ action sequences. Heuristics, pruning, constraints, and replanning can avoid enumerating that tree. Temporal abstraction offers another lever: it can reduce the number of high-level decisions, and a carefully chosen skill library can keep the high-level branching factor manageable.

There is a second reason to avoid long primitive rollouts: model error compounds. A learned option-outcome model can replace many primitive predictions with one high-level prediction, but that helps only when its initiation states and outcomes are covered by training data or checked during execution. An option can itself traverse unfamiliar states, so hierarchy is not an automatic cure for distribution shift.

The practical move is to structure the problem. Skills can compress many primitive timesteps into one high-level choice. Symbols can discard continuous detail irrelevant to a task. Language can specify goals and constraints without requiring a user to write reward code. Models of other agents can expose strategic dependence that a single-agent transition model hides. These mechanisms change different dimensions of planning; only temporal abstraction directly shortens the decision horizon. Human-readable abstractions can also make plans easier to inspect and communicate, although learned latent skills need not be interpretable.

Abstraction is familiar elsewhere in computing. High-level programming languages let programmers express algorithms in functions and statements that compilers lower into machine instructions. Operating systems expose files and processes rather than disk sectors and page tables. Hierarchical planning applies the same separation of interfaces to decisions: a high-level controller selects a meaningful behavior while a lower-level controller handles its internal feedback.

This chapter develops four interfaces for that structure. Temporal abstraction uses options and skills. Symbolic abstraction maps task-relevant state into predicates and operators. Language grounding converts an instruction into a goal, constraint, reward, or plan sketch. Multi-agent planning represents joint actions, private information, and assumptions about other policies. They are related because each factorizes a planning problem, not because they share one compression formula.

The organizing question is therefore precise: what variable has been simplified, and what assumption makes the simplification valid? Options simplify decision time but rely on competent closed-loop skills. Predicates simplify state descriptions but rely on sound grounding and effects. Language simplifies task specification but relies on reference resolution and semantic alignment. Opponent or teammate models structure strategic uncertainty, but often enlarge rather than shrink the represented state. Each interface creates a distinct failure mode.

By the end of the chapter you will be able to:

• define an option as a temporally extended action with a policy, a termination condition, and an initiation set;
• write the semi-Markov decision process equations that make options composable with ordinary planners;
• build a symbolic abstraction from a continuous world model, including predicates, operators, and the STRIPS-style planning loop;
• condition a plan on a natural-language instruction by grounding it into a goal predicate or reward signal;
• reason about opponents and nested beliefs using the tools of game theory and recursive belief modeling;
• recognize when each abstraction fails and design evaluations that catch the failure.

We assume you have worked through Search and Belief-Space Planning, Policies Learned in Imagination, and Active Perception, Dual Control, and Exploration. This chapter reuses their state, belief, policy, and information notation while changing the structure of the decisions being planned.

The single most important idea in this section is that a high-level decision can take time. In the primitive-action MDP formulation from Markov and Partially Observable Decision Processes, each decision epoch selects one primitive action $a_t$. An MDP modeler could encode a macro as an action or augment state with a commitment variable, but the option formalism gives variable-duration closed-loop behavior an explicit interface.

If the agent selects “walk to the door,” the choice must carry both a low-level feedback policy and a rule for returning control. The option formalism supplies those pieces and leads to duration-aware value backups. The standard definition follows Sutton, Precup, and Singh (1999).

Each of the three components answers a different question, and it is worth separating them explicitly. The initiation set answers "when am I allowed to try this?" If the option is "grasp the cup," it makes no sense to start it when the cup is on the other side of the room, so the initiation set excludes those states. The policy answers "what do I actually do while the option is running?" This is the low-level controller, and it can be a hand-written script, a learned neural network, or a classical motion planner. The termination probability answers "when do I stop and reconsider?" A deterministic termination condition is the special case where $\beta$ is either zero or one at every state, which is what you get from a discrete detector such as "the fingers have closed around the cup."

An option is best thought of as a reusable subroutine. "Grasp the cup" is an option whose policy is a learned grasping controller and whose termination is a detector for the fingers closing around the cup. When the option's policy is stochastic, an outcome model must describe terminal state $s'$, duration $\tau$, and cumulative reward. Once you have a small library of such models, a higher-level planner can treat each option as one decision while the option policy handles primitive feedback internally.

The subroutine analogy has a limit. A software subroutine has a specified interface, but its runtime can still depend on inputs and the execution environment. A physical option also evolves through stochastic state transitions, so both its terminal state and its duration can vary. The SMDP equations account for this variable duration explicitly.

Planning over variable-duration options gives a semi-Markov decision process (SMDP) at option decision epochs; one-step options recover the MDP special case. The distinguishing feature of an SMDP is that transitions can have variable duration. Let $\tau$ be the random number of primitive timesteps that option $\omega$ runs before terminating. For the normalized terminal-outcome models in this section, assume the selected option terminates almost surely. Otherwise, its finite-duration outcomes form a subprobability model and nontermination must be handled separately. Write $\Omega(s)=\{\omega:s\in\mathcal I_\omega\}$ for the options eligible to start at $s$. Assume every nonterminal decision state has at least one eligible option; in the displayed backup, take the continuation maximum to be zero if the termination state is terminal. For an eligible $\omega$, its value is the expected discounted return accumulated while it runs, plus the discounted value of the best eligible continuation option once it terminates:

where:

• $s$: the state at which the option is initiated
• $\omega$: the eligible option being evaluated (a temporally extended action with $s\in\mathcal I_\omega$)
• $\tau$: the random number of primitive timesteps the option runs before its termination condition triggers
• $t$: the primitive timestep at which the option is initiated, so the option executes at primitive steps $t, t+1, \dots, t+\tau-1$
• $r_{t+k+1}$: the reward received at primitive timestep $t+k+1$, while the option is executing
• $k$: the index over primitive steps within the option, running from $0$ to $\tau-1$
• $\gamma \in [0, 1)$: the discount factor applied to each primitive timestep
• $\gamma^\tau$: the discount applied to the value of the state where the option terminates, scaled by the option's random duration
• $s_{t+\tau}$: the state at which the option terminates and control returns to the high-level planner
• $\omega'$: the continuation option selected at the termination state
• $\max_{\omega'\in\Omega(s_{t+\tau})} Q^\star(s_{t+\tau}, \omega')$: the value of the best eligible option at a nonterminal termination state; the continuation term is zero at a terminal state

The outer expectation is taken over the two random quantities inside the option: the run length $\tau$ (how long the option keeps going before $\beta_\omega$ triggers) and the trajectory of states and rewards encountered while it runs. The expectation is taken under the option's own stochastic process, i.e., the distribution over $(\tau, s_t, s_{t+1}, \dots, s_{t+\tau}, r_{t+1}, \dots, r_{t+\tau})$ induced by following $\pi_\omega$ from $s$ until $\beta_\omega$ triggers, not under the state distribution of the data or under the planner's prior. The sum accumulates the discounted per-step rewards $r_{t+k+1}$ for the $k = 0, 1, \dots, \tau-1$ primitive steps the option actually executes. The second term is the value of the best option available once the option has terminated, discounted by $\gamma^\tau$ so that it is measured in units of the option's initiation time rather than the termination time. Concretely, the reward accrued at primitive step $t+k+1$ is discounted by $\gamma^k$ because it occurs $k$ steps after the option is initiated, and the continuation value at $s_{t+\tau}$ is discounted by $\gamma^\tau$ because the option ran for $\tau$ primitive steps before reaching that state.

The discount exponent is the key difference from a one-step Bellman backup. With the reward indexing above, the immediate reward has exponent zero and the continuation value is multiplied by $\gamma$ because one primitive transition has elapsed. In an SMDP, each internal reward keeps its own offset $k$, while the continuation value is multiplied by $\gamma^\tau$. For $0<\gamma<1$, with otherwise comparable internal rewards and the same positive continuation value, a slower option has a smaller continuation term and is less attractive. At $\gamma=0$, every positive-duration continuation term is zero, so duration creates no preference through that term. For $0<\gamma<1$, a negative common continuation value reverses the continuation-term preference; different intermediate rewards, costs, or terminal values can also reverse the overall preference.

The multiplier $\gamma^\tau$ isolates the attenuation due to duration; it does not by itself determine the option's total return.

The same structure carries over to the state-value function. At a nonterminal state, define $V^\star(s) = \max_{\omega\in\Omega(s)} Q^\star(s, \omega)$; at a terminal state, set $V^\star(s)=0$. The nonterminal optimality equation becomes

which has the shape of a Bellman optimality equation with a max over eligible options and a duration-aware return. Many dynamic-programming and temporal-difference methods have SMDP counterparts, but the backup must include cumulative option reward, duration, terminal state, and option eligibility. This is more than replacing a one-step transition matrix.

A useful sanity check is to ask what happens when the option library is trivial. Suppose every option is a single primitive action, so that the option's policy picks that action and the termination probability is one at every state. Then $\tau = 1$ with probability one, the sum reduces to the single reward $r_{t+1}$, the discount $\gamma^\tau$ becomes $\gamma$, and the SMDP equation collapses exactly onto the ordinary MDP Bellman equation. The SMDP is therefore a strict generalization: it contains the MDP as the special case where every option is one-step. This containment is the reason we can mix primitive actions and options freely inside a single planner, using primitive actions where fine control matters and options everywhere else.

Planning over options can use dynamic programming on the SMDP. A learned primitive-step model can estimate an option outcome by rolling its closed-loop policy forward, while an option-level model can predict cumulative reward, duration, and terminal state directly. Either route avoids additional real-environment interaction, but neither is free: primitive rollouts accumulate model error and computation, while option-level models introduce their own abstraction and coverage errors.

The equation assumes call-and-return execution: once selected, an option runs until $\beta_\omega$ terminates it. The initiation set controls where an option may start; it does not interrupt an active option. Mid-option reconsideration therefore requires a modified termination rule or a separate polling/interruption mechanism. Termination and interruption rules are design choices because they determine when control returns to the high-level planner.

For model-based planning, define the discounted cumulative option reward $R_\omega = \sum_{k=0}^{\tau-1}\gamma^k r_{t+k+1}$ and model the joint outcome $P(R_\omega,s',\tau\mid s,\omega)$. The state-duration marginal obeys the product rule

The conditioning on $\tau=n$ matters because terminal state and duration are usually dependent. Summing over $n$ gives the terminal-state marginal, but discarding duration loses the exponent needed for $\gamma^\tau$. Many value-estimation algorithms admit option-level variants built from this SMDP outcome model; sampling-based planners can likewise search over option outcomes.

The joint model also preserves correlations among reward, duration, and terminal state. A slow option might accrue more reward or reach a better state, so an expected duration and a marginal terminal distribution are not generally enough to reconstruct its value.

There are three practical ways to obtain options, and each teaches a different lesson about world models.

Hand-designed. A human specifies a controller such as pick, place, follow-path, or grip. Hand design can improve inspectability and make intended behavior easier to validate, but it does not guarantee correctness under perception error, implementation bugs, or unmodeled dynamics. Its coverage is limited to the skills and conditions the engineer anticipated.

Discovered from data. Option discovery asks which temporal chunks recur or provide useful control. One family of methods identifies graph bottlenecks: narrow gateways through which many trajectories between regions pass. Another seeks branching or high-control states from which many futures are reachable. These notions are related but not identical. Task-relevant bottlenecks and decision points are useful termination candidates, not a universal rule for where every option should end.

Learned jointly with a high-level policy. One active approach learns skills, termination rules, and the high-level selector together, sometimes using diversity or information objectives. The resulting skills can be useful without corresponding to human concepts, which makes them harder to inspect. This is distinct from the Dreamer family: Dreamer learns latent dynamics and a policy through imagination, but its standard formulation is not an option hierarchy with initiation and termination rules.

Whichever route you take, the planner needs an outcome model for each option: eligibility, cumulative reward, duration, and terminal state. A primitive-step world model can simulate the option policy, while an efficient high-level system may learn or cache an option-level model. The latter changes the model interface and must be validated on the option's execution distribution.

Options shrink the number of high-level decisions but restrict when the high-level policy can switch. The intra-option policy remains closed-loop and may adapt at every primitive step. Under call-and-return execution, however, a different option cannot be selected until termination unless an explicit interruption mechanism is available.

The design tension is: longer options compress more decision epochs but postpone high-level reselection. Reaching, grasping, moving between waypoints, and opening a door are plausible task units. Their boundaries may align with useful symbols, although temporal skills and state abstractions capture different aspects of task structure.

For a deliberately crude full-tree comparison, suppose the primitive horizon is $T$ and each selected option lasts $\bar{\tau}$ steps on average. An option tree then has about $|\Omega|^{T/\bar{\tau}}$ leaves rather than $|\mathcal{A}|^T$. Under these assumptions the option tree is smaller exactly when $|\Omega| < |\mathcal{A}|^{\bar{\tau}}$. Real planners add pruning, state merging, stochastic durations, failures, and unequal option costs; the calculation isolates only branching and depth.

This relationship between horizon and branching factor is easiest to grasp as a pair of growth curves. On a log scale, the primitive cost climbs steeply with horizon while the option cost climbs at a rate set by the mean option duration.

Two useful design tests are whether high-level replanning is valuable at a boundary and whether the abstract state predicts rewards and future abstract states well enough for the next decision. A doorway may satisfy both in one domain and neither in another. Approximate Markov sufficiency and graph bottlenecks are therefore criteria to test, not consequences of using options.

Options let us plan over long horizons, but they do not tell us which option to pick. For that, we need a higher-level representation of what is true in the world and what each option can change. That is exactly what symbolic abstraction provides.

The idea is to project continuous state $s \in \mathbb{R}^n$ onto Boolean or discrete predicates. For a fixed object set and finite grounded vocabulary, a predicate such as $\texttt{on(cup, table)}$ is either present or absent from a symbolic state. An option can then be represented by an operator with preconditions and effects. This supports graph search over grounded states and classical planning formalisms such as STRIPS.

The projection removes continuous detail from symbolic search, but it does not guarantee a small problem: $m$ Boolean ground atoms admit up to $2^m$ valuations, and grounding more objects can create many atoms. What it buys is a task-specific state description whose transitions can be searched discretely. What it gives up is resolution and often geometry, so the abstraction must preserve the distinctions needed for feasibility and reward.

A STRIPS-style operator defines when a symbolic action applies and how it changes the state. Formally, it takes the form

where:

• $\mathrm{pre}$: the precondition set, i.e., the predicates that must all be true in the current symbolic state for the operator to be applicable
• $\mathrm{add}$: the add set, the predicates that become true after the operator is applied
• $\mathrm{del}$: the delete set, the predicates that become false after the operator is applied

The operator applies if all predicates in $\mathrm{pre}$ are true, and produces a new state where the predicates in $\mathrm{add}$ become true and the predicates in $\mathrm{del}$ become false:

where:

• $s$: the current symbolic state, represented as a set of predicates that are true
• $\mathrm{pre}$: the precondition set, which must be a subset of $s$ for the operator to be applicable
• $\mathrm{add}$: the predicates the operator turns on
• $\mathrm{del}$: the predicates the operator turns off
• $\mathrm{result}(s)$: the symbolic state after the operator is applied, i.e., the original state with the delete set removed and the add set inserted

Classical planners search over sequences of operators that take an initial symbolic state to a goal state. The search operates over symbolic states, i.e., sets of predicates, and each operator application must satisfy $\mathrm{pre} \subseteq s$ in the current state before the update $s \mapsto (s \setminus \mathrm{del}) \cup \mathrm{add}$ is applied.

Two assumptions are easy to conflate. Under a closed-world state representation, unlisted ground facts are treated as false. Under STRIPS persistence semantics, facts not mentioned in an applicable operator's add or delete effects retain their truth values. Exogenous events violate the modeled persistence rule: if a cup falls while no operator records the change, the symbolic state becomes stale.

The interesting question for us is not how STRIPS works in the abstract, which is a well-covered topic in classical planning literature, but how the symbols relate to the world model. Specifically:

1. Predicates are grounded in observations or latent state. Object-centric representations can provide inputs for learning task-specific relations such as on(x, y) or holding(x), but slots do not automatically supply calibrated predicates.
2. Operators summarize option effects. Rolling an option through a model can estimate its predicate-level outcomes. This is one neuro-symbolic planning pattern, alongside hand-authored operators and integrated geometric checks.
3. Goals come from the task specification. In the basic STRIPS setting used here, a goal is a conjunction of ground predicates. Richer planning languages also support numeric, quantified, disjunctive, and temporal goals.

Layering can decouple symbolic search from continuous evaluation. A fully compiled symbolic model may avoid low-level simulation during search. Integrated task-and-motion or model-validated planners instead query geometry or learned dynamics while constructing candidate plans. Either design can extend the useful planning horizon, but physical validity still depends on grounding, operator models, and execution monitoring.

The interface must answer at least two questions: which predicates hold now, and what predicate-level outcomes can an option produce? Reliable answers are necessary but not sufficient. Planner correctness also depends on complete goals, applicable operators, exogenous-event assumptions, resource limits, and monitoring. A symbolic plan can therefore be internally valid yet physically infeasible.

A practical failure mode is that grounded predicates may be wrong or stale. If a detector says on(cup, table) after the cup has fallen, subsequent search starts from a false state. This reliability problem is related to, but narrower than, Harnad's symbol grounding problem, which asks how symbols acquire semantic content from nonsymbolic representations. Several engineering responses help:

• Re-check preconditions before acting. Before executing an option, verify its preconditions still hold. If not, replan.
• Interleave symbolic and continuous reasoning. Instead of planning symbolically once and executing blindly, alternate a symbolic plan step with a short continuous rollout that validates it. This is one interleaved task-and-motion or model-validated planning pattern.
• Train predicates and effects for feasibility. Joint objectives can favor features predictive of feasible actions, but that property must be included and evaluated explicitly.
• Let symbolic planners propose and continuous planners dispose. The symbolic plan is a sketch; the continuous planner fills in the details.

These remedies treat a symbolic plan as a hypothesis rather than a fact. Rechecking high-risk or changeable preconditions is often worth the sensing cost, but monitoring can itself be expensive, delayed, or occluded. Its frequency should reflect uncertainty and consequence. In noisy physical domains, recovery matters because perfectly reliable learned predicates are generally unrealistic.

Symbolic planning also omits continuous parameters. Task-and-motion planning (TAMP) combines discrete operator choices with continuous state, geometry, and motion constraints. A simple decomposition proposes an operator skeleton $o_{1:m}$ and solves for continuous parameters $\theta_{1:m}$ and states $x_{1:m}$:

where:

• $x_k$: the continuous state after operator $o_k$
• $\theta_k \in \mathbb{R}^{d_k}$: continuous parameters such as a grasp or target pose
• $\mathcal{F}_{o_k}$: admissible state-parameter pairs whose resulting motion satisfies collision, kinematic, and dynamic constraints
• $F_{o_k}$: the continuous transition or trajectory endpoint induced by $o_k$
• $\operatorname{pre}(o_k,x)$: applicability, including relevant geometric conditions
• $G(x_m)$: the terminal goal constraint
• $c_k$: execution cost over the feasible state-parameter choices

A skeleton-first solver fixes the operator order while solving continuous feasibility. Integrated TAMP methods interleave these searches and revise the skeleton when geometry fails; Garrett et al. (2021) survey these designs. We will not implement a full TAMP solver here.

The transition and precondition constraints couple consecutive operators: the state produced by one parameterized motion must make the next operator applicable. The feasible-set constraint separately rules out motions that violate collision, kinematic, or dynamic limits even when their endpoints satisfy symbolic predicates. Initial applicability and the terminal goal are separate constraints, which avoids the undefined $o_{m+1}$ that a shorthand “next precondition” would create.

If symbols ground plans, language specifies them. "Put the red mug on the top shelf" is a natural-language instruction that a symbolic planner can translate directly into a goal state: on(red_mug, top_shelf). The instruction does not say how to do it (that is the planner's job), but it does say what "done" means. Language-conditioned planning turns natural-language instructions into executable plans by grounding the instruction into predicates, rewards, or constraints that the planner can optimize.

Language is a useful planning interface because it can name objects, relations, preferences, and orderings. The mapping is not syntactic substitution: reference resolution, context, missing concepts, and ambiguity all matter. A phrase such as “the red mug” must first identify an entity represented by the system before a goal such as on(red_mug, top_shelf) is meaningful.

There are three regimes worth distinguishing.

Instruction as goal. The simplest regime: the instruction names a target state, and the planner finds a path there. "Go to the kitchen" translates to agent_at(kitchen). The instruction acts as a goal specification channel: the target predicate becomes the goal, and the planner uses the same world model and search machinery it would use for any other goal-conditioned problem. The plan it produces is only as good as the grounding, so a wrong predicate yields a wrong plan even when the planner is correct. Because the world model is the same one you would use for any other goal, the machinery is nearly identical to what we built in Search and Belief-Space Planning.

Instruction as procedure. The instruction gives intermediate steps, ordering, or constraints. “First heat the pan, then add oil, then add the eggs” is a totally ordered procedure; a partially ordered example could allow whisking the eggs while the pan heats, then require both to finish before cooking. The planner fills in missing details and checks feasibility. A supplied order can reduce search, but it can also exclude a necessary alternative.

Instruction as reward. A third regime: the instruction defines a preference, not a hard constraint. "Tidy the room" does not specify a particular arrangement; it describes a family of acceptable outcomes. In this regime the instruction can be compiled into a reward or cost function, and planning proceeds as ordinary reward maximization. This is the regime most relevant to language-conditioned RL and to the reward-from-language literature. A common instantiation treats the instruction as defining a reward $r(s, a; u)$ that depends on the instruction $u$, so that the induced objective is the expected return

where:

• $\pi$: the policy being optimized, mapping states to distributions over actions
• $u$: the natural-language instruction that conditions the reward
• $r(s_t, a_t; u)$: the instruction-conditioned reward at timestep $t$
• $\gamma \in [0, 1)$: the discount factor
• $J(\pi; u)$: the expected discounted return of policy $\pi$ under instruction $u$

Maximizing this objective yields an instruction-conditioned policy. Rolling that policy out from a particular initial state produces a trajectory; computing a contingent or open-loop plan requires the corresponding planning procedure.

These interfaces trade specificity and flexibility in different ways; none is uniformly more expressive without fixing the goal, procedure, and reward languages. A procedure can constrain action order more than a goal, while a reward can encode graded preferences yet leave behavior under-specified. The right interface depends on which parts of the task the instruction states reliably and which parts the planner should infer.

For the goal-predicate regime, let $\mathcal{P}$ be the vocabulary of atomic grounded predicates. A grounding function maps an instruction $u$ and state or observation context $s$ to a desired goal set $G \subseteq \mathcal{P}$:

where:

• $\mathcal{U}$: the space of instructions (natural-language strings or token sequences)
• $\mathcal{S}$: the state space of the world model (continuous or latent)
• $\mathcal{P}$: the atomic grounded-predicate vocabulary
• $u$: the specific instruction being grounded
• $s$: the specific state the instruction is being grounded against

A common supervised approach fits a probabilistic grounder to paired instructions, contexts, and goal sets. With data distribution $p_{\text{data}}(u,s,G)$, maximum conditional likelihood gives

Here $G$ is the whole target set, so $-\log p_\theta(G\mid u,s)$ is a per-example negative log likelihood. A multilabel Bernoulli model is one implementation; contrastive and pretrained-model approaches are also possible. Reward, constraint, and procedure grounding use different output types rather than pretending they are predicate sets. Even with a useful world-state representation, grounding may require relational reasoning, reference resolution, and uncertainty estimation.

A useful first stage is referent selection: given an instruction and an observation, identify candidate objects and relations. Object-centric representations can supply candidate entities, but slots may not align with names, attributes, events, affordances, or sets. Grounding remains a modeling problem rather than a lookup.

If a fixed world representation and action interface do not encode a referred concept, language-only scaling cannot reliably ground or execute it. Joint representation learning, new perception, tools, or external memory can change that interface, so the limitation belongs to the fixed system rather than to language in general.

One family of systems uses a language model to propose high-level skills, then scores proposals with affordance or value models, simulators, or environmental feedback. SayCan combines language scores with learned skill affordances; Inner Monologue conditions replanning on feedback. These scoring components are fallible models, not correctness certificates. The analogy to neural MCTS is limited: a policy prior guides exploration and a value model estimates leaves; neither automatically verifies feasibility.

Proposal and checking separate candidate coverage from candidate evaluation. Reliability depends on both: the proposer must include a workable candidate, and the scorer must be calibrated on that candidate's state-action distribution. Model error, missing constraints, and distribution shift can still admit an infeasible plan.

In the fixed-library architecture developed here, language specifies objectives and helps compose existing skills. It cannot create a missing actuator or low-level controller. It can still improve task decomposition, parameterization, tool selection, and plan quality within those physical limits.

If a robot has no controller or tool for opening a drawer, a clearer instruction does not supply the missing physical capability. Better language reasoning can nevertheless choose and compose available skills more effectively, so grounding quality and skill coverage should be evaluated separately.

Other agents introduce joint actions, private information, and strategic dependence. A Markov game's transition kernel can remain stationary when all policies are fixed. From one independent learner's perspective, however, the induced dynamics become nonstationary when teammates or opponents update their policies. Explicit opponent modeling is useful when adaptation to particular agents matters, but robust policies, self-play, population training, and centralized planning need not expose an opponent model as a named state variable.

A fully observed multi-agent decision problem can be written as a stochastic (Markov) game, introduced by Shapley (1953) and adopted as a multi-agent reinforcement-learning framework by Littman (1994):

where:

• $\mathcal{S}$: the shared state space of the environment
• $\mathcal{A}_i$: the action space of agent $i$, with $N$ the number of agents
• $P(s' \mid s, a_1, \dots, a_N)$: the transition kernel, which depends on the joint action of all agents
• $r_i: \mathcal{S} \times \mathcal{A}_1 \times \cdots \times \mathcal{A}_N \to \mathbb{R}$: the reward function for agent $i$
• $\gamma \in [0, 1)$: the discount factor shared by all agents

Each action may affect the shared transition and other agents' outcomes. When $N=1$, the tuple reduces to an MDP. Under partial observability, agent $i$ receives observation $o_i$ and conditions its policy on a local history $h_i^t=(o_i^0,a_i^0,\ldots,o_i^t)$ rather than on the shared state. A decentralized planner must therefore reason about joint behavior without assuming that every actor sees the same information.

The value of one action can depend on what others do and on what they believe about the focal agent. Rock-paper-scissors provides a minimal warning: against an adaptive opponent, a deterministic policy is exploitable, while the equilibrium mixed strategy randomizes uniformly.

The standard tools for reasoning in these settings include:

• Nash equilibrium, where no agent can improve by a unilateral deviation, for strategic interactions generally Nash (1951);
• subgame-perfect equilibrium for extensive-form games, requiring a Nash equilibrium in every proper subgame;
• level-$k$ or cognitive-hierarchy reasoning, where level 0 is a specified nonstrategic baseline and higher levels respond to lower levels Camerer, Ho, and Chong (2004);
• Opponent modeling as a supervised learning problem: predict the opponent's action given the history.

These tools encode different assumptions. The Nash definition is mutual best response; using it as a behavioral prediction can additionally require strong rationality and information assumptions. Subgame perfection rules out non-credible behavior in proper subgames, while imperfect-information settings often need refinements defined at information sets. Level-$k$ models can fit bounded reasoning in some laboratory games, but their advantage is context dependent. Learned opponent models avoid an equilibrium requirement, yet still assume a policy class, stationarity window, and training distribution.

The recursive structure of “what I think you think” can be represented with interactive beliefs. For focal agent $i$, let $\Theta_{-i}^{(d-1)}$ denote a chosen class of depth-$(d-1)$ models of the other agents. A depth-$d$ belief has type

where $\Delta(X)$ denotes probability distributions over $X$. A base type in $\Theta^{(0)}$ is a specified behavioral model; it need not be uniform. At the next depth, a type may itself contain a belief about physical state and lower-depth models. This typed construction follows the interactive-state view of Gmytrasiewicz and Doshi (2005). It has no general $N D$ dimension formula. A factorized implementation may store $N$ summaries with $D$ parameters each, but correlated types, histories, and deeper model classes can grow much faster.

Bounding depth is one approximation. Another shares parameters across agents or keeps only a small population of opponent types. The approximation must state what one node represents, which agents can appear next, and whether repeated identities are allowed.

The following count makes one deliberately uncompressed approximation concrete. In a toy tree where each modeled agent branches to every other agent identity, each additional depth multiplies the node count by $N-1$. This is an illustration, not a general complexity law.

The switch occurs because the posterior exceeds the threshold $q=0.5$, where $4q=2$. Different likelihoods or incentives can leave the best response unchanged. This tiny example does not solve decentralized planning; it shows how a communication observation enters a belief-dependent action choice.

The dynamics of coordination depend sharply on whether other agents are cooperative, adversarial, or indifferent:

• Fully cooperative. Agents share a reward, but decentralized execution remains difficult when observations differ. Centralized training with decentralized execution (CTDE) is one widely used research pattern when joint information is available during training.
• Two-player zero-sum. Rewards satisfy $r_1+r_2=0$; finite games have a minimax value. Constant-sum games can be normalized to this form.
• Mixed-motive. Agents' interests partially overlap. Many real coordination and negotiation problems are mixed-motive: two companies negotiating a deal, two robots sharing a corridor, two nations managing a border. Nash equilibrium is a central solution concept, but there can be multiple equilibria with very different welfare properties, so which one gets selected becomes a first-order design question.

In mixed-motive settings, equilibria can have different welfare properties and equilibrium selection matters. Exact solution becomes intractable in many large or partially observable formulations, though complexity depends on the game class, representation, horizon, and solution concept. Practical methods exploit structure, self-play, approximation, or learned models rather than applying one universal recipe.

In CTDE, a centralized critic can condition on joint information during training while decentralized actors use local observations at execution. This can improve credit assignment and reduce apparent nonstationarity, as in Lowe et al. (2017). It does not guarantee equilibrium selection, communication, robustness, or coordination under distribution shift.

For world models, the requirement is to account for other agents' behavior. A model may represent policies, types, and beliefs explicitly, or encode them implicitly in a history-dependent latent state. Either way, evaluation should separate prediction under fixed co-player policies from adaptation after those policies change.

The gridworld below has a start, a key, a locked door, and a goal. The state includes position, key possession, and door status. Navigation, unlocking, and goal-reaching are separate options with explicit initiation predicates and structured results. The example is deterministic and illustrative; it compares decision granularity, not runtime or sample efficiency.

Now the symbolic layer will choose the sequence. A single abstraction function maps an environment state into mutually exclusive location predicates plus key and door facts. Every symbolic operator has an option with matching initiation and effects.

The planner sees predicates and operators, not coordinates. The executor then checks each precondition, dispatches the bound option, and compares predicted effects with the abstraction of the resulting environment state. Symbolic search remains independent of grid geometry only while the grounded operator set is fixed and valid; a new map can change option feasibility or grounding cost even if the abstract sequence remains reusable.

The final layer maps a small set of instructions to goal predicates. This hand-written grounder accepts a state argument for the interface but does not use it to choose a goal; its accepted mappings are context-insensitive. It requires the relevant object token and rejects negation rather than silently reversing its meaning.

Every link remains a potential failure point: grounding can select the wrong goal, symbolic effects can be inaccurate, and an option can fail despite valid preconditions. The end-to-end assertion proves only this deterministic toy instance; it does not turn any learned component into a verifier.

An end-to-end success rate cannot tell you which abstraction helped or which interface failed. A useful evaluation therefore treats every boundary in the stack as a contract. The contract states what enters a component, what it returns, which uncertainty accompanies the return, and which downstream decision uses it.

The distinction from earlier chapters remains essential. A model can predict an option's terminal-state distribution accurately while a planner chooses the wrong option because its reward or constraint is misspecified. Conversely, a biased predictor can still support the correct action on a narrow decision boundary. Report both kinds of measurement:

• Predictive measurements test option duration, cumulative reward, predicate effects, language-grounding probabilities, and opponent-action probabilities against held-out outcomes.
• Decision measurements test task return, constraint violations, replanning frequency, coordination success, and regret against a stated baseline.
• Interface measurements test whether predicted symbolic effects agree with the predicates observed after option execution and whether language-derived goals match annotated intent.

The measurements should share evaluation episodes, but they should not be collapsed into one score. A high task success rate can hide a poor grounder when the planner reaches the goal through a dataset shortcut. A low success rate can blame the grounder unfairly when the required option does not exist.

The toy program uses deterministic states and effects so that the binding logic is visible. A learned system should expose distributions or confidence sets instead:

• An option model can return $P(R_\omega,s',\tau\mid s,\omega)$ rather than one terminal state.
• A predicate detector can return calibrated probabilities or abstain near its decision boundary rather than assert a brittle Boolean fact.
• A language grounder can return several goal hypotheses with posterior weights rather than silently choose one interpretation.
• An opponent model can maintain a distribution over types or policies and update it after observed actions and messages.

Passing those uncertainties forward does not require every layer to share one representation. It requires the consumer to know what the producer's number means. A calibrated predicate probability is not the same object as an option-success probability, and neither is automatically a probability that the whole plan will succeed. The events are dependent: a grounding error changes which options are attempted, while an option failure changes which predicates are observed next.

For a fixed candidate plan $o_{1:m}$, a planner may estimate a joint success probability by propagating its belief through each option model,

with the mass of $b_k$ equal to the probability that the prefix has succeeded under the modeled dynamics. Here $b_{k-1}$ is a subprobability mass function over state and successful-prefix execution; its total mass is the modeled probability that the prefix has succeeded. Failure probability remains visible as missing mass rather than being hidden by renormalization. Multiplying independent scalar success rates would be valid only under a conditional-independence model that is rarely justified. Belief propagation preserves how earlier outcomes alter later preconditions.

A focused test suite should deliberately perturb one interface at a time:

The point is not to make all perturbations equally realistic. It is to give each component a falsifiable contract. In the gridworld, execute_symbolic_plan performs two such checks: it rejects a violated precondition before dispatch and compares the operator's predicted symbolic effects with the abstraction of the physical result afterward. A stochastic implementation would replace equality with a calibrated likelihood or acceptance region.

Hierarchical planning should not be compared only with exhaustive primitive search. Useful baselines include a receding-horizon primitive planner, a reactive or learned policy, and the same high-level planner with different option libraries. Symbolic planning should be compared both with a continuous planner and with an ablation that removes online feasibility checks. Language grounding should be compared with an oracle goal specification so that grounding error is separated from planning error. Multi-agent methods should face fixed policies, held-out populations, and adapting co-players rather than a single training opponent.

Control the quantity that supports each conclusion. If a plot claims that temporal abstraction reduces node expansions, hold the search algorithm, heuristic, task, and solution-quality requirement fixed while changing the action representation. If it claims faster wall-clock planning, include the cost of building option models and checking continuous feasibility. If it claims transfer, re-ground the same operator schema in changed environments and report both successful reuse and rejected infeasible instances.

This evaluation discipline also prevents a common category error. The symbolic plan in the worked example is geometry-independent as a data structure, but the system is not geometry-independent: the bound navigation options and effect checks still depend on the map. The abstraction is valuable because it isolates that dependence behind a testable interface, not because it makes the dependence disappear.

The key design parameters across the abstractions in this chapter are:

• Option horizon, termination, and interruption: duration affects high-level decision frequency and continuation discounting. A closed-loop option still reacts internally; termination or an explicit interruption rule determines when the high-level policy can reselect.
• Option library size: a larger library can improve coverage while increasing high-level branching. Under the toy full-tree model, the depth benefit exceeds the branching cost when $|\Omega| < |\mathcal{A}|^{\bar{\tau}}$; real selection also depends on option quality and overlap.
• Predicate granularity: the number and coarseness of symbolic predicates, which trades grounding reliability against planner tractability. Coarse predicates are easier to detect reliably but blur distinctions the planner may need; fine predicates capture more structure but are harder to ground correctly.
• Recursion depth $d$: how many levels of nested belief the multi-agent model captures, trading strategic depth against computational cost and sensitivity to opponent assumptions. Higher depth can represent deeper strategic reasoning but is more expensive and more fragile when the assumptions are violated.
• Grounding vocabulary and training coverage: broader coverage can handle more concepts, but reliability depends on representation, data, compositional generalization, and calibrated abstention—not vocabulary size alone.

The four interfaces in this chapter restructure different parts of planning. Options reduce high-level decision frequency. Symbols reduce continuous detail in task search. Language changes how goals and constraints are specified. Multi-agent models represent strategic coupling and can increase computational burden. Their common bargain is that useful structure comes with assumptions whose failure must be detected.

Options trade high-level flexibility for temporal reach. Their internal policies remain adaptive, but call-and-return execution postpones option reselection. Boundaries near task-relevant decision points can work well, yet no location type is universally correct. The governing assumptions are that the skill remains competent over its initiation distribution and that its termination or interruption rule returns control soon enough when its purpose changes.

Symbolic abstractions trade resolution and grounding effort for discrete search. A coarse reliable predicate may be preferable to a fine unstable one, but the choice is task dependent. The model assumes that predicate detectors, operator effects, and exogenous-event handling remain valid over execution. A cup falling while no modeled operator records it violates persistence and can invalidate the plan.

Language trades compact specification for grounding ambiguity. New object names, relations, syntax, and unrepresented concepts can break a grounder; the exact failure rate is empirical and domain specific. Evaluation should separate reference resolution, goal extraction, planning, and physical execution rather than report only end-to-end success.

Multi-agent approximations trade model detail for scalability. Exact solution is hard in many large or partially observable formulations, but tractability depends on the game class and representation. An explicit opponent model can overfit to one behavior distribution; an implicit history model can fail after a policy change for the same reason. Evaluation should vary co-player populations and adaptation regimes.

The compounded problem. Because these abstractions stack, their errors also stack. An error at one layer can propagate to later layers, making diagnosis difficult without targeted evaluations. A language instruction that grounds into a symbolic goal whose predicates come from a world model that is itself imperfect produces a plan whose failure is not attributable to any single layer. Diagnostic evaluation therefore becomes essential: when the agent fails, you need to know which layer failed. Was the instruction misunderstood? Was the grounding wrong? Was the world model inaccurate? Was the option library missing a skill? Was the opponent behaving unexpectedly? Evaluation in hierarchical and multi-agent systems is more about attributing failure than measuring success, and this is the theme we will return to in Part XI: Evaluation and Understanding.

The practical consequence of compounding is that evaluation should probe one layer at a time. Test the grounder on instructions whose correct predicate set you know. Test the symbolic planner on predicate sets whose correct plan you know. Test the option library on tasks within its intended scope. Test the opponent model against a range of opponent behaviors, including ones it was not trained on. These component tests make failures easier to diagnose, but they do not replace end-to-end testing of interactions among layers.

Reusable skills and grounded symbols can make some long-horizon tasks substantially more tractable and inspectable. Language can reduce the cost of specifying tasks. Multi-agent models can improve prediction or coordination when their assumptions match the co-players. Reactive policies, receding-horizon control, search, and learned value functions remain viable alternatives or complements.

The next part, beginning with PILCO, PETS, Ensembles, and MBPO, turns to concrete model-based reinforcement-learning lineages. Those methods study probabilistic dynamics, uncertainty-aware control, and synthetic rollouts. Their machinery can later be combined with hierarchical or symbolic interfaces, but it does not automatically instantiate options, language grounding, or recursive multi-agent beliefs.

Large planning problems have several distinct sources of complexity. This chapter separated four ways to structure them rather than forcing them into one compression formula.

• Options turn a primitive action into a temporally extended subroutine with a policy, an initiation set, and a termination condition. They compose via the semi-Markov decision process equations, where transitions have variable duration and the Bellman equation must handle the option length by discounting both the intra-option rewards by $\gamma^k$ and the continuation value by $\gamma^\tau$.
• Symbolic abstractions project task-relevant continuous state onto predicates and option effects onto operators. Fully compiled and integrated task-and-motion architectures make different choices about when to query continuous models.
• Language-conditioned planning can map an instruction to a goal, procedure, reward, or constraint. In the fixed-library example it changes the goal and composition, not the available physical controllers.
• Multi-agent planning accounts for joint actions, private information, and changing co-player behavior. Interactive beliefs, bounded reasoning, opponent models, and CTDE are different approximations with different assumptions.

The unifying pattern is structured factorization. Options compress decision time; predicates compress state description; language compresses task specification; multi-agent models structure uncertainty about other policies. Only the first is explicitly designed to change temporal depth. In every case the interface must be tested against the causal and informational structure of the task.

A second unifying pattern is that every interface relies on assumptions. Options rely on skill competence over their initiation distributions. Symbols rely on grounded predicates and modeled effects. Language relies on semantic alignment between instructions and the planner's representation. Multi-agent methods rely on assumptions about co-player behavior or the robustness of a history-dependent model. Naming those assumptions makes the corresponding evaluation target explicit.

The open design question is how much structure to specify and how much to learn. The decision-centric lineages in the next part provide concrete dynamics and control mechanisms against which that choice can be evaluated.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about hierarchical, symbolic, language, and multi-agent planning.