Hierarchical and Multi-Agent RL

A standard MDP forces an agent to choose a primitive action at every single timestep, so a plan that spans 500 steps is a point in a 500-dimensional decision space with no notion of reusable sub-routines. The options framework (Sutton, Precup, Singh, 1999) fixes this by adding a layer of temporally extended actions, called options. An option $\omega = (\mathcal{I}_\omega, \pi_\omega, \beta_\omega)$ consists of an initiation set $\mathcal{I}_\omega \subseteq \mathcal{S}$ (states where the option can be started), an internal policy $\pi_\omega$ over primitive actions, and a termination function $\beta_\omega(s) \in [0,1]$ giving the probability the option ends in state $s$. A policy over options $\mu(\omega \mid s)$ selects which option to run; when it terminates, control returns to $\mu$. The set of primitive actions is itself the special case of options that last exactly one step. This turns the original MDP into a semi-Markov decision process (SMDP): transitions now take a random, state-dependent number of primitive steps, and rewards accumulate (discounted) over that duration.

Hierarchical RL is the broader family of methods that exploit this idea: options, the MAXQ value-function decomposition, feudal networks (manager/worker hierarchies), and goal-conditioned RL where a high-level policy emits sub-goals that a low-level policy is rewarded for reaching. All of these share the same structural payoff: credit assignment happens on two timescales. The high level reasons about which sub-goal to pursue over tens or hundreds of steps; the low level reasons about primitive dynamics over a handful of steps. This shortens effective horizons for both levels and — crucially — lets sub-policies be reused across tasks that share structure, connecting naturally to skills learned via imitation or inverse RL.

Multi-agent RL generalizes the MDP in the orthogonal direction: instead of one decision-maker, there are $n$ agents acting simultaneously in a shared environment, formalized as a Markov game (Shapley, 1953; Littman, 1994) $\langle \mathcal{S}, \{\mathcal{A}^i\}_{i=1}^n, T, \{R^i\}_{i=1}^n, \gamma\rangle$: the transition function and each agent's reward depend on the joint action $a = (a^1, \dots, a^n)$. Because every agent is simultaneously learning, the "environment" as seen by agent $i$ — which includes the policies of all other agents — is non-stationary, violating the fixed-MDP assumption that underlies convergence guarantees for Q-learning and policy gradients. The correct notion of "solution" is no longer a single optimal policy but a Nash equilibrium: a joint policy $\pi^* = (\pi^{1*}, \dots, \pi^{n*})$ such that no agent can improve its own expected return by unilaterally deviating. Cooperative, competitive, and mixed-motive (general-sum) games all fit this template; the algorithmic question is how to train stable, well-coordinated policies despite the non-stationarity.

Part 1 — the options framework and intra-option learning. The core object is the option-value function $Q_\Omega(s, \omega)$, the expected discounted return of starting option $\omega$ in state $s$ and thereafter following the policy over options. It obeys an SMDP Bellman equation:

Learning this directly (SMDP Q-learning) only updates $Q_\Omega(s,\omega)$ once per completed option, wasting the primitive-level transitions that occur inside it. Intra-option Q-learning instead updates every option consistent with the action just taken, at every primitive step, using a one-step target with the option's own termination probability mixed in: ``` INTRA-OPTION Q-LEARNING Input: option set Ω (each ω has policy π_ω, termination β_ω), step size α, discount γ Initialize Q_Ω(s, ω) arbitrarily for all s, ω Initialize current state S, and current option Ω_t ~ μ(·|S) with Ω_t applicable in S repeat for each environment step: A ← sample from π_{Ω_t}(·|S) # act using the running option's internal policy take action A, observe reward R, next state S' for every option ω such that A is consistent with π_ω(·|S): # "all options" updates U(S', ω) ← (1 - β_ω(S')) · Q_Ω(S', ω) + β_ω(S') · max_{ω'} Q_Ω(S', ω') Q_Ω(S, ω) ← Q_Ω(S, ω) + α [ R + γ · U(S', ω) - Q_Ω(S, ω) ] S ← S' if Ω_t terminates in S (sampled from β_{Ω_t}(S)): Ω_t ← select new option ~ μ(·|S), among those with S ∈ I_ω until done ``` The `U(S', ω)` term is the option's own value if it continues blended with the best next option's value if it terminates, weighted by the termination probability — this is exactly the SMDP Bellman backup written one primitive step at a time. Because the update loop runs over every option whose policy agrees with the action taken (not just the one currently executing), a single environment transition propagates information to many options at once — this is the "off-policy-like" efficiency gain that makes intra-option learning far more data-efficient than SMDP Q-learning, which only learns from completed options.

Part 2 — feudal / goal-conditioned hierarchies. A complementary, more scalable design used in deep RL replaces discrete options with a manager network that periodically emits a continuous goal vector $g_t$, and a worker network that is rewarded for making progress toward $g_t$ (e.g. by cosine similarity between the state-change direction and $g_t$, as in FeUdal Networks), independent of the manager's actual environment reward. This separates "what to achieve" (learned by the manager, which sees a compressed, slow-timescale state) from "how to achieve it" (learned by the worker, which sees raw observations and acts every step). The manager operates on an SMDP exactly as in the options framework — its action (the goal) persists for $c$ steps — while the worker is trained by ordinary single-step policy gradients.

Part 3 — multi-agent training patterns. Three canonical patterns handle the non-stationarity problem, in increasing order of coordination they enable. ``` CENTRALIZED TRAINING, DECENTRALIZED EXECUTION (CTDE) — generic template Input: n agents, each with actor π_θ^i(a^i | o^i) and centralized critic Q_φ^i(s, a^1,...,a^n) Initialize actor and critic networks for all agents; replay buffer D repeat for each environment step: observe joint state s, each agent's local observation o^i for each agent i: sample a^i ~ π_θ^i(· | o^i) # decentralized ACTING execute joint action (a^1,...,a^n), observe reward r^i for each i, next state s' store (s, o^1..n, a^1..n, r^1..n, s') in D sample minibatch from D for each agent i: y^i = r^i + γ · Q_{φ'}^i(s', a'^1,...,a'^n) |_{a'^j = π_{θ'}^j(o'^j)} # centralized CRITIC target update φ^i by minimizing (Q_φ^i(s,a^1..n) - y^i)^2 update θ^i by policy gradient: ∇_{θ^i} J = E[ ∇_{θ^i} π^i(o^i) · ∇_{a^i} Q_φ^i(s,a^1..n) ] soft-update target networks φ', θ' until done ``` This is essentially MADDPG (Lowe et al., 2017): every agent's critic sees the joint action and (often) the global state during training, which restores stationarity for the critic's regression target, while each actor at execution time uses only its own local observation, so the system still runs in a decentralized way. QMIX applies the same CTDE principle to cooperative value-based learning: each agent has a local utility $Q^i(o^i, a^i)$, and a learned, non-negative-weighted mixing network combines them into a joint $Q_{tot}$, with monotonicity constrained ($\partial Q_{tot}/\partial Q^i \ge 0$) so that a greedy action for $Q_{tot}$ can be found by each agent greedily maximizing its own $Q^i$ — this is the Individual-Global-Max (IGM) property that makes decentralized execution consistent with centralized optimization. For competitive and mixed-motive settings, the standard procedure is self-play: each agent's opponent(s) are sampled from a pool of its own past policy checkpoints (to avoid cycling and forgetting), and the training loop otherwise looks like independent policy-gradient learning (e.g. independent PPO) against this evolving population.

Hierarchical RL — sample complexity intuition. Flat RL over a horizon of $H$ primitive steps must, in the worst case, explore an action space whose effective branching depth is $H$; the number of distinct action sequences of length $H$ grows as $|\mathcal{A}|^H$. If a task decomposes into $m$ options each lasting roughly $H/m$ steps on average, the high-level policy only has to search a decision tree of depth $m$ over $|\Omega|$ options, while each low-level option only has to solve a short-horizon sub-problem of length $H/m$. Under mild assumptions (options are Markov sub-policies whose termination states are well predicted, and reward is roughly separable across the decomposition), the effective search space shrinks from $|\mathcal{A}|^H$ toward $|\Omega|^m \cdot (|\mathcal{A}|^{H/m})^m = |\Omega|^m |\mathcal{A}|^H$ — this does not shrink the raw action-sequence count, but it shrinks the credit-assignment path: a reward signal at the end of a sub-task needs only propagate back through $H/m$ steps to update the option's internal policy, instead of through all $H$ steps to update a flat policy. This is the same mechanism that makes $n$-step returns and eligibility traces reduce variance in ordinary TD learning, applied at the option's natural timescale instead of an arbitrary fixed $n$.

Correctness of intra-option Q-learning. The key invariant is that the algorithm's fixed point is the same $Q_\Omega^*$ solving the SMDP Bellman optimality equation, provided every option is a Markov policy (its next action depends only on the current state, not on how long it has run) and all state–option pairs are visited infinitely often. The proof follows the same stochastic-approximation argument as ordinary Q-learning (Robbins–Monro conditions on step sizes, a contraction in sup-norm of the Bellman optimality operator), because the intra-option update is a sample-based instance of applying that same contracting operator — it just applies it to every option consistent with the observed primitive transition rather than to one, which changes the sample efficiency but not the fixed point. This is why intra-option learning is provably at least as data-efficient as SMDP Q-learning: it extracts strictly more consistent updates per environment step from the same trajectory, without introducing bias.

Multi-agent RL — why single-agent proofs break, and what replaces them. Q-learning's convergence proof relies on the Bellman optimality operator being a $\gamma$-contraction for a fixed MDP. In a Markov game, if every agent runs independent Q-learning, each agent's transition and reward distributions depend on the other agents' evolving policies, so the "MDP" each agent is solving changes between updates — the contraction argument no longer applies, and empirically this can cycle or fail to converge even in simple matrix games (e.g. matching pennies). The fix used by CTDE methods is to make the critic's training-time input the full joint state and joint action; conditioned on the joint action, the environment dynamics genuinely are Markov and stationary, restoring a valid regression target for the critic even though each actor only conditions on local information at execution time. QMIX's monotonicity constraint is what makes decentralized greedy execution consistent with the centrally learned optimum (the IGM property): if $\partial Q_{tot}/\partial Q^i \ge 0$ for all $i$, then $\arg\max_{a^1,\dots,a^n} Q_{tot} = (\arg\max_{a^1} Q^1, \dots, \arg\max_{a^n} Q^n)$, so decentralized per-agent maximization exactly recovers the joint maximizer — a genuine theorem, not a heuristic, though it restricts the class of joint value functions QMIX can represent (it cannot express Q-functions requiring genuinely non-monotonic coordination, a real expressiveness tradeoff).

Solution concept and equilibrium selection. Even with perfect optimization, "the" optimal joint policy may not exist in a general-sum game — only Nash equilibria, of which there can be several with different payoffs to different agents (an equilibrium-selection problem with no single correct answer, unlike single-agent optimality). Self-play provably converges to a Nash equilibrium in two-player zero-sum games under fictitious-play–style dynamics (a classical game-theory result), which is why competitive self-play (AlphaGo/AlphaZero-style, or OpenAI Five/AlphaStar-style leagues) is theoretically well grounded; for general-sum, cooperative, or many-player games there is no such guarantee, and training toward a stable equilibrium — not the optimal outcome — is the honest goal.

Complexity summary table.

The honest tradeoff in the last row: centralized critics buy stationarity at the price of an input (and sometimes output) space that grows with the number of agents, which is why practical systems restrict to factored or monotonic value decompositions (QMIX, VDN) rather than a fully joint tabular $Q_{tot}$.

Options trace — a 1D corridor. States $s \in \{0,1,2,3,4\}$ (goal at $4$), primitive actions {left, right}, $\gamma=0.9$, reward $-1$ per step until goal (reward $0$, episode ends). Define one option $\omega_R$ = "go right until the wall or 3 steps, whichever first" with $\beta_\omega(s)=1$ after 3 primitive steps or at $s=4$. Suppose the agent is at $s=0$ and executes $\omega_R$, taking the primitive path $0\to1\to2\to3$ (3 steps, rewards $-1,-1,-1$), then $\omega_R$ terminates at $s=3$. Intra-option update after the first primitive transition $0\to1$ ($R=-1$):

Since $\beta_{\omega_R}(1) = 0$ (hasn't run 3 steps yet, not at wall), this reduces to $U(1,\omega_R) = Q_\Omega(1,\omega_R)$, and:

— exactly a one-step TD update, even though the option itself hasn't terminated. This is the practical payoff: the value function is updated at every primitive step, not just once every three steps as SMDP Q-learning would require, so with initial $Q_\Omega \equiv 0$, $\alpha=0.5$, the sequence of updates along $0\to1\to2\to3$ gives $Q_\Omega(2,\omega_R) \leftarrow 0 + 0.5(-1) = -0.5$ after step 2, $Q_\Omega(1,\omega_R) \leftarrow 0 + 0.5(-1 + 0.9(-0.5)) = -0.725$ after step 3 is folded back, and so on — three independent option-consistent updates extracted from a single 3-step rollout.

Multi-agent trace — matrix game illustrating non-stationarity. Two agents play repeated matching pennies: each picks Heads/Tails simultaneously; agent 1 wins (+1, agent 2 gets −1) if they match, agent 2 wins if they differ. There is no deterministic Nash equilibrium — the unique Nash equilibrium is both agents randomizing 50/50.

This table is not a toy artifact: it is the textbook demonstration that independent value-based learners can cycle forever in a game whose only equilibrium is mixed. A CTDE critic conditioned on the joint action (here, the full $2\times2$ payoff structure) can represent this correctly, and algorithms with fictitious-play-style updates converge in expectation to the 50/50 equilibrium, while naive independent Q-learning provably does not.

Sutton and Precup's work grew directly out of the temporal-difference and eligibility-trace machinery Sutton had developed in the 1980s; the options framework was the first formalism to let "macro-actions" be learned and valued with the same Bellman-equation rigor as primitive actions, rather than hand-engineered. Littman's Markov games gave multi-agent RL a formal object to reason about at exactly the moment deep function approximation made it practical to train many interacting neural-network policies at scale — the two threads (temporal abstraction, multi-agent games) developed largely independently for two decades before both became central to the deep-RL era's most visible achievements: robotic skill hierarchies, StarCraft II leagues, and cooperative multi-robot systems.

Hierarchical decompositions underlie modern robot learning stacks, where a high-level planner selects sub-goals ("pick up object," "navigate to bin") executed by low-level continuous-control policies — this separation is what lets the same low-level walking or grasping skill be reused across many high-level tasks. Dialogue and task-oriented assistant systems use hierarchical structure to separate long-horizon planning ("book a trip") from turn-level language generation. Traffic-signal control, warehouse logistics, and swarm robotics are naturally posed as cooperative Markov games solved with QMIX-family algorithms, since agents (intersections, robots, drones) must coordinate under only local observability. Competitive self-play with CTDE-style critics or league training produced some of deep RL's most visible public results: OpenAI Five (Dota 2), AlphaStar (StarCraft II), and multi-agent hide-and-seek, all of which required managing non-stationarity across a population of co-evolving policies rather than a single fixed opponent. The equilibrium-based thinking developed for multi-agent RL — reasoning about a population of interacting policies rather than a single optimal one — also foreshadows how modern systems reconcile multiple human preferences and multiple learned reward signals, a connection developed further in RLHF Connections.

Ask the tutor: How would you design the option set and reward shaping for a robot that must both navigate and manipulate objects in a shared multi-robot warehouse?