Why this subject matters now
The reinforcement-learning results that reached the public between 2015 and 2025, the Atari agents, the Go and StarCraft players, the robotic hands, the reasoning language models, share a property that the textbook flat MDP does not have: they operate over abstractions. A Go engine does not reason at the granularity of single stone placements when it plans; a robot hand does not plan finger torques one control step at a time from first principles; a reasoning model does not treat every token as an independent decision with a reward attached. Temporal abstraction, transfer between tasks, calibrated handling of risk, coordination among several learners, and directed exploration are the differences between an algorithm that works on a gridworld and one that works on a problem a person would care about.
Five years ago a practitioner could get by knowing DQN and policy gradients. Today the expected fluency is wider. An interviewer for an applied-RL role will assume you can explain why independent Q-learners fail to converge in a two-player game, what the categorical projection in C51 actually computes and why you need it, why hindsight experience replay makes a sparse-reward manipulation task learnable when nothing else does, what random network distillation measures and why it is more robust than a forward dynamics model, and how a constrained MDP encodes a safety budget as a Lagrangian. The reproducibility literature, Henderson and colleagues chief among it, is now part of the required reading too: knowing that a single algorithm can look state-of-the-art or mediocre depending on five random seeds is a piece of professional competence, not trivia.
The through-line of the page is that every one of these topics is a controlled generalization of one object from the fundamentals page: the Bellman equation. Options give it a variable time step. Distributional RL gives it a random variable in place of an expectation. Multi-agent RL gives it a second decision-maker inside the transition. Successor features factor its reward out of its dynamics. Constrained RL bolts a second Bellman equation on for cost. Seeing them as deformations of a single fixed-point equation is what lets you carry intuition from one to the next instead of memorizing nine disconnected algorithms.
Core theory
Options and the semi-Markov decision process
An option, in the sense of Sutton, Precup, and Singh (1999), is a temporally extended action: a closed-loop policy you can invoke and that runs for a while before returning control. Formally an option is a triple \( \omega = (\mathcal{I}_\omega, \pi_\omega, \beta_\omega) \) where \( \mathcal{I}_\omega \subseteq \mathcal{S} \) is the initiation set (the states from which the option may be started), \( \pi_\omega(a \mid s) \) is the option's internal policy over primitive actions, and \( \beta_\omega(s) \in [0,1] \) is the termination probability in state \( s \). A primitive action is the special case of an option that is available everywhere, executes exactly one action, and terminates with probability one.
Execution follows the call-and-return model. In state \( s \) the agent picks an option \( \omega \) available there according to a policy over options \( \mu(\omega \mid s) \). It then follows \( \pi_\omega \) until, at each subsequent state \( s' \), the option terminates with probability \( \beta_\omega(s') \); on termination the agent returns to \( \mu \) and picks the next option. Because the number of primitive steps an option consumes is itself random, the process the policy over options sees is not a standard MDP but a semi-Markov decision process (SMDP): the time between decision points is a random variable rather than a fixed unit.
Discounting is where the SMDP structure shows up in the algebra. Suppose an option started in \( s \) runs for a random number \( k \) of primitive steps, collecting rewards \( r_0, r_1, \dots, r_{k-1} \), and then hands back control in state \( s' \). Define the option's cumulative discounted reward and its effective discount as
$$ R(s,\omega) = \E\!\left[ \sum_{t=0}^{k-1} \gamma^{t} r_t \;\Big|\; s, \omega \right], \qquad \Gamma(s,\omega,s') = \E\!\left[ \gamma^{k} \mid s, \omega, s' \right]. $$The two quantities separate the reward accumulated during the option from the discount that must be applied to whatever value follows it. With them the value of a policy over options obeys a Bellman equation that looks exactly like the primitive one, but with the primitive reward replaced by \( R \) and the primitive discount \( \gamma \) replaced by the option-dependent \( \Gamma \):
$$ V_\mu(s) = \sum_{\omega} \mu(\omega \mid s)\Big[ R(s,\omega) + \sum_{s'} P(s' \mid s,\omega)\,\Gamma(s,\omega,s')\,V_\mu(s') \Big]. $$Here \( P(s' \mid s,\omega) \) is the multi-step transition kernel: the probability that the option, started in \( s \), eventually terminates in \( s' \). The option-value function is the same statement conditioned on the first option,
$$ Q_\mu(s,\omega) = R(s,\omega) + \sum_{s'} P(s' \mid s,\omega)\,\Gamma(s,\omega,s')\, V_\mu(s'), \qquad V_\mu(s) = \sum_\omega \mu(\omega\mid s)\, Q_\mu(s,\omega). $$The operator defined by the right-hand side is a contraction in the same way the primitive Bellman operator is, because \( \Gamma(s,\omega,s') \le \gamma < 1 \) for any option that takes at least one step, so all the convergence theory from the fundamentals page transfers verbatim. The value of temporal abstraction is not that it changes what is optimal, the flat optimal value is still an upper bound, but that it changes the geometry of the problem the learner faces: with good options, credit assignment spans many primitive steps in a single backup, so the effective horizon the learner must reason over shrinks.
Intra-option learning. The naive SMDP update only learns about the option that was actually executed, and only once it has terminated, which wastes the primitive transitions collected along the way. Intra-option methods fix this by exploiting the fact that a single primitive transition \( (s, a, r, s') \) is consistent with the internal policy of every option that would have taken \( a \) in \( s \). For any such Markov option \( \omega \), the intra-option value update targets
$$ U(s',\omega) = \big(1 - \beta_\omega(s')\big)\, Q(s',\omega) + \beta_\omega(s')\, \max_{\omega'} Q(s',\omega'), $$ $$ Q(s,\omega) \leftarrow Q(s,\omega) + \alpha\big[\, r + \gamma\, U(s',\omega) - Q(s,\omega)\,\big]. $$The bracket \( U \) is the crux: at \( s' \) the option either continues, with probability \( 1-\beta_\omega(s') \), in which case its own value applies, or it terminates, with probability \( \beta_\omega(s') \), in which case control returns to the policy over options and the greedy value applies. This is a one-step, off-policy backup that updates many options from one transition, and it is the object the option-critic architecture makes differentiable.
The option-critic architecture
Sutton-Precup-Singh assumed the options were given. Option-critic (Bacon, Harb, Precup, 2017) learns the internal policies and terminations end to end from the return, with no subgoals or pseudo-rewards specified by hand. Parameterize the intra-option policies \( \pi_{\omega,\theta}(a\mid s) \) by \( \theta \) and the terminations \( \beta_{\omega,\vartheta}(s) \) by \( \vartheta \). The objects to differentiate are the option-value \( Q_\Omega(s,\omega) \) and the value of a state-option pair after the action is committed but before it is taken,
$$ Q_U(s,\omega,a) = r(s,a) + \gamma \sum_{s'} P(s'\mid s,a)\, U(s',\omega), $$with \( U \) the continuation value defined exactly as above. Differentiating the expected return with respect to \( \theta \) gives the intra-option policy gradient, which is the ordinary policy-gradient theorem applied inside a fixed option:
$$ \frac{\partial J}{\partial \theta} = \E\!\left[ \frac{\partial \log \pi_{\omega,\theta}(a\mid s)}{\partial \theta}\, Q_U(s,\omega,a) \right]. $$Differentiating with respect to the termination parameters is the part unique to option-critic. The termination function enters the return only through the continuation value \( U(s',\omega) \), and \( \partial U / \partial \beta_\omega(s') = -\big(Q_\Omega(s',\omega) - V_\Omega(s')\big) \). Carrying that through yields the termination gradient
$$ \frac{\partial J}{\partial \vartheta} = -\,\E\!\left[ \frac{\partial \beta_{\omega,\vartheta}(s')}{\partial \vartheta}\, A_\Omega(s',\omega) \right], \qquad A_\Omega(s',\omega) = Q_\Omega(s',\omega) - V_\Omega(s'). $$The advantage \( A_\Omega \) is the entire content of the result. When the current option is better than average at \( s' \), the advantage is positive, the minus sign drives \( \beta \) down, and the option is encouraged to keep running; when it is worse than average, the advantage is negative and the option is encouraged to terminate so control returns to the policy over options, which can switch to something better. The gradient says, in one line, stop an option exactly when continuing it is worse than re-deciding. The known failure mode follows from the same expression: with no cost on switching, options tend to collapse, either terminating almost every step (so the hierarchy degenerates to a flat policy) or never terminating (so one option swallows the whole task). A small additive advantage margin, a deliberation cost that raises the bar for termination, is the standard regularizer that keeps options temporally extended.
Goal-conditioned hierarchies and hindsight experience replay
A parallel line to options builds hierarchy through goals rather than through learned sub-policies. In the feudal formulation (Dayan and Hinton, 1993; Vezhnevets et al., 2017, FeUdal Networks) a manager emits a goal, a direction or a target state, at a slow timescale, and a worker is rewarded for moving toward that goal at a fast timescale. Concretely the value and policy are conditioned on a goal \( g \), giving a goal-conditioned action value \( Q(s, a, g) \) and policy \( \pi(a \mid s, g) \). Universal value function approximators (Schaul et al., 2015) are the representation that makes this work: one network approximates \( Q(s,a,g) \) jointly over states and goals so that value generalizes across goals rather than being relearned for each.
The hard case for any goal-conditioned method is a sparse reward: the agent receives \( r = 0 \) for reaching the goal and \( r = -1 \) otherwise, with the goal reached almost never under an untrained policy. Every trajectory is a string of \( -1 \)s, so every temporal-difference target is identical and the gradient carries no information about which actions were better. Hindsight experience replay (Andrychowicz et al., 2017) is a strikingly small idea that dissolves this. After collecting a trajectory \( s_0, a_0, s_1, \dots, s_T \) that failed to reach the intended goal \( g \), store it not only with \( g \) but also with a relabeled goal \( g' \) drawn from the states actually visited, most simply \( g' = s_T \), the final achieved state. Under \( g' \) the same trajectory succeeded by construction, so its last transition carries a reward of \( 0 \) and the temporal-difference target becomes informative.
Why relabeling helps, made precise. Let \( \rho(s' \mid s, a) \) be the environment dynamics, which do not depend on the goal, and let the reward be a deterministic function of the achieved state and the goal, \( r(s', g) = -\,\mathbb{1}[\,d(s',g) > \varepsilon\,] \). The learning signal available from a transition is the variance of the temporal-difference target across the goals it is trained on. Under the original goal alone, in the sparse regime, \( r(s_{t+1}, g) = -1 \) for every \( t \) with probability approaching one, so the target \( r + \gamma \max_{a'} Q(s_{t+1}, a', g) \) has essentially zero across-sample variance in its reward component: the reward channel is constant and the bootstrap is being fit to a constant. Under the hindsight distribution over relabeled goals \( g' \), the same transition \( (s_t, a_t, s_{t+1}) \) is trained with \( r(s_{t+1}, g') = 0 \) whenever \( g' \) is a state reached at or after \( t+1 \), and \( -1 \) otherwise, so the reward channel now takes both values with non-negligible probability. A channel that varies carries gradient; a channel that is constant does not. Because the dynamics are goal-independent, the transition is equally valid evidence for every goal, so relabeling injects no bias: it reweights which \( (s,a,s',g) \) tuples the replay buffer contains without falsifying any of them. The mechanism is, at bottom, importance-free data augmentation over the goal argument that is legal precisely because the goal does not touch the dynamics. This is the same off-policy reasoning that makes DQN's replay buffer valid, applied to the goal rather than to the action; DQN and replay are derived on the deep RL page.
Successor features and transfer
Transfer asks how value learned for one reward function can be reused when the reward changes but the dynamics do not. Successor features (Barreto et al., 2017), building on Dayan's (1993) successor representation, give a clean answer by factoring the action value into a part that depends only on dynamics and a part that depends only on the reward. Assume the one-step reward is linear in a feature map \( \phi(s,a,s') \in \R^{d} \),
$$ r(s,a,s') = \phi(s,a,s')^{\T} w, $$where \( w \in \R^{d} \) encodes the task. Define the successor features of a policy \( \pi \) as the expected discounted sum of the feature map under that policy,
$$ \psi^{\pi}(s,a) = \E^{\pi}\!\left[ \sum_{t=0}^{\infty} \gamma^{t}\, \phi(s_t,a_t,s_{t+1}) \;\Big|\; s_0=s, a_0=a \right]. $$The decomposition of the action value is then immediate. Push the reward's linear form through the definition of \( Q^{\pi} \) and use linearity of expectation:
$$ Q^{\pi}_{w}(s,a) = \E^{\pi}\!\left[ \sum_{t=0}^{\infty} \gamma^{t}\, \phi(s_t,a_t,s_{t+1})^{\T} w \right] = \left(\E^{\pi}\!\left[ \sum_{t=0}^{\infty} \gamma^{t}\, \phi(s_t,a_t,s_{t+1}) \right]\right)^{\!\T} w = \psi^{\pi}(s,a)^{\T} w. $$The factorization \( Q = \psi^{\T} w \) is the whole idea. The successor features \( \psi^{\pi} \) satisfy their own vector-valued Bellman equation, \( \psi^{\pi}(s,a) = \E[\phi + \gamma\, \psi^{\pi}(s',a')] \), and can be learned by ordinary temporal-difference updates on the \( d \)-dimensional feature target. Because \( \psi^{\pi} \) knows nothing about \( w \), once it is learned for a set of policies, the value of any new task \( w_{\text{new}} \) is a dot product, computable without further environment interaction.
Generalized policy improvement (GPI) turns a library of such policies into a single better one. Given policies \( \pi_1, \dots, \pi_n \) with successor features \( \psi^{\pi_i} \), define the improved policy as greedy with respect to the best value any library policy assigns:
$$ \pi(s) \in \argmax_{a} \; \max_{i} \; \psi^{\pi_i}(s,a)^{\T} w_{\text{new}}. $$The GPI theorem states that this policy is at least as good as every \( \pi_i \) on the new task, with a suboptimality bound that degrades gracefully in how well the new reward vector is covered by the library. The practical payoff is zero-shot transfer: to solve a new task you evaluate one dot product per stored policy and take the best action, no gradient steps required, which is why successor features became a standard tool for fast adaptation across reward changes.
Distributional reinforcement learning
Every method so far tracks the expected return. Distributional RL (Bellemare, Dabney, Munos, 2017) tracks the full distribution of the return and treats the expectation as merely one of its statistics. Let \( Z^{\pi}(s,a) \) be the random return, \( \sum_{t} \gamma^{t} r_t \), so that \( Q^{\pi}(s,a) = \E[Z^{\pi}(s,a)] \). The return distribution obeys a distributional Bellman equation, an equality of random variables rather than of their means:
$$ Z^{\pi}(s,a) \;\overset{D}{=}\; r(s,a) + \gamma\, Z^{\pi}(s', a'), \qquad s' \sim P(\cdot\mid s,a),\ a' \sim \pi(\cdot\mid s'). $$The distributional Bellman operator \( \mathcal{T}^{\pi} \) that this defines is a \( \gamma \)-contraction, but only in the right metric. It is not a contraction in the KL divergence or in total variation; it is a contraction in the maximal Wasserstein metric \( \bar d_p(Z_1, Z_2) = \sup_{s,a} W_p\big(Z_1(s,a), Z_2(s,a)\big) \), because multiplying a random variable by \( \gamma \) scales Wasserstein distance by exactly \( \gamma \) while adding a constant leaves it unchanged. This is the theoretical reason the two leading algorithm families, C51 and QR-DQN, are built the way they are: each chooses a representation of a distribution and a projection back onto that representation that behaves well under this operator.
C51 and the categorical projection
C51 represents \( Z(s,a) \) as a categorical distribution on a fixed grid of \( N \) atoms \( z_0 < z_1 < \dots < z_{N-1} \), evenly spaced between \( V_{\min} \) and \( V_{\max} \) with spacing \( \Delta z = (V_{\max}-V_{\min})/(N-1) \). The network outputs probabilities \( p_i(s,a) \) on the atoms, so \( Z(s,a) = z_i \) with probability \( p_i(s,a) \). The problem the categorical projection solves is that applying the Bellman operator moves the atoms: the shifted-and-scaled support \( \mathcal{T} z_i = r + \gamma z_i \) does not land on the grid. C51 projects the transformed distribution back onto the fixed atoms by splitting each displaced atom's probability mass between its two nearest grid neighbors, in proportion to closeness, which is exactly the operation that preserves the mean and minimizes the move in Wasserstein-1.
The projection \( \Phi \) of the Bellman target onto atom \( i \) is
$$ \big(\Phi \hat{\mathcal{T}} Z\big)_i = \sum_{j=0}^{N-1} \left[ 1 - \frac{\big| [\,\mathcal{T} z_j\,]_{V_{\min}}^{V_{\max}} - z_i \big|}{\Delta z} \right]_{0}^{1} \, p_j(s', a^\ast), $$where \( [\,\cdot\,]_{a}^{b} \) clips to \( [a,b] \), the inner clip keeps the transformed atom inside the support and the outer clip \( [\cdot]_0^1 \) makes the triangular weight vanish beyond one grid spacing. The loss is then the cross-entropy between this projected target and the predicted distribution, \( \KL\big(\Phi\hat{\mathcal{T}}Z \,\|\, Z_\theta(s,a)\big) \), which for a fixed target is a plain categorical cross-entropy. The name "C51" is just this construction with \( N = 51 \) atoms, the value that worked best on the Atari benchmark in the original paper.
QR-DQN and the quantile-Huber loss
QR-DQN (Dabney et al., 2018) inverts C51's choice. Instead of fixing the atom locations and learning their probabilities, it fixes the probabilities, \( N \) equal-mass quantiles each carrying \( 1/N \), and learns their locations \( \theta_i(s,a) \). The target quantile levels are the midpoints \( \hat\tau_i = (2i-1)/(2N) \) for \( i = 1,\dots,N \). Fitting a quantile is a regression problem with an asymmetric loss: the quantile at level \( \tau \) is the minimizer of the pinball (quantile) loss
$$ \rho_\tau(u) = u\big(\tau - \mathbb{1}[u < 0]\big), \qquad u = \text{(target)} - \theta, $$which penalizes under- and over-estimates with weights \( \tau \) and \( 1-\tau \). Because the pinball loss has a discontinuous derivative at \( u = 0 \), QR-DQN smooths it near the origin with a Huber function of width \( \kappa \), giving the quantile-Huber loss
$$ \rho^{\kappa}_\tau(u) = \big|\tau - \mathbb{1}[u<0]\big|\, \cdot \, \mathcal{L}_\kappa(u), \qquad \mathcal{L}_\kappa(u) = \begin{cases} \tfrac12 u^2 & |u| \le \kappa \\[2pt] \kappa\big(|u| - \tfrac12\kappa\big) & |u| > \kappa. \end{cases} $$The advantage over C51 is that there is no projection step and no bounded support: the quantile locations can move anywhere, so \( V_{\min} \) and \( V_{\max} \) do not have to be guessed in advance, and the estimator is consistent for the quantile function under the Wasserstein contraction. IQN (Dabney et al., 2018) takes the final step of sampling the quantile level \( \tau \) from a continuous distribution instead of fixing \( N \) of them, which lets a single network represent the entire quantile function and makes risk-sensitive policies, greedy with respect to a distorted expectation, a matter of changing the sampling distribution.
Multi-agent reinforcement learning
When more than one agent learns at once, the single-agent MDP generalizes to a stochastic game (Shapley, 1953), also called a Markov game: a tuple \( (\mathcal{S}, \{\mathcal{A}_i\}, P, \{r_i\}, \gamma) \) with a joint action \( \mathbf{a} = (a_1,\dots,a_n) \), a transition kernel \( P(s' \mid s, \mathbf{a}) \) that depends on all agents' actions, and a separate reward \( r_i(s, \mathbf{a}) \) for each agent. The solution concept is no longer a single optimal policy but an equilibrium. A joint policy \( (\pi_1,\dots,\pi_n) \) is a Nash equilibrium if no agent can improve its own expected return by unilaterally changing its policy,
$$ V_i^{\pi_i, \pi_{-i}}(s) \;\ge\; V_i^{\pi_i', \pi_{-i}}(s) \quad \text{for all } \pi_i',\ \text{all } i,\ \text{all } s, $$where \( \pi_{-i} \) is the joint policy of everyone except agent \( i \). A correlated equilibrium (Aumann, 1974) generalizes this by allowing the agents' actions to be correlated through a shared signal: a joint distribution over action profiles such that, conditioned on the recommendation an agent receives, deviating is not profitable. Every Nash equilibrium is a correlated equilibrium with independent marginals, but the correlated set is larger, convex, and, unlike Nash, computable by a linear program, which is why it appears in learning algorithms that need a tractable target.
The non-stationarity problem. The reason multi-agent learning is hard, and the single fact an interview will probe, is that from any one agent's point of view the environment is non-stationary. Agent \( i \)'s effective transition and reward, \( P(s' \mid s, a_i) = \sum_{a_{-i}} P(s'\mid s, a_i, a_{-i})\,\pi_{-i}(a_{-i}\mid s) \), depend on the other agents' policies \( \pi_{-i} \), which are themselves changing as those agents learn. An independent learner that treats the others as part of a fixed environment is fitting a moving target: the Markov property it assumes holds only if \( \pi_{-i} \) is frozen. This voids the convergence guarantees from the fundamentals page, which all assume a stationary MDP, and it is why independent Q-learning can cycle indefinitely in games as small as matching pennies. Experience replay makes it worse, not better, because a replayed transition was generated under an opponent policy that no longer exists.
Centralized training, decentralized execution (CTDE) is the dominant response. During training a critic is allowed to see the global state and every agent's action, which restores stationarity because conditioning on \( \mathbf{a} \) removes the dependence on the unknown \( \pi_{-i} \); at execution each agent runs only its own policy on its own observation, so no central coordinator is needed in deployment. MADDPG (Lowe et al., 2017) implements this directly: each agent has its own deterministic policy trained by a centralized action-value critic \( Q_i(s, a_1, \dots, a_n) \) that takes all agents' actions as input. The gradient for agent \( i \)'s policy is the deterministic policy gradient (derived on the deep RL page) with the centralized critic in place of the single-agent one,
$$ \nabla_{\theta_i} J_i = \E\!\left[ \nabla_{\theta_i} \mu_i(a_i \mid o_i)\, \nabla_{a_i} Q_i(s, a_1,\dots,a_n) \big|_{a_i = \mu_i(o_i)} \right]. $$QMIX (Rashid et al., 2018) addresses the cooperative case, where all agents share one team reward, and adds a structural constraint that makes decentralized execution provably consistent with centralized value learning. It represents the joint action value as a monotonic mixing of per-agent utilities \( Q_i(o_i, a_i) \),
$$ Q_{\text{tot}}(s, \mathbf{a}) = f_s\big(Q_1(o_1,a_1), \dots, Q_n(o_n, a_n)\big), \qquad \frac{\partial Q_{\text{tot}}}{\partial Q_i} \ge 0 \ \ \text{for all } i. $$The monotonicity constraint is the entire point. If \( Q_{\text{tot}} \) is monotone increasing in each \( Q_i \), then the joint argmax factorizes: \( \argmax_{\mathbf{a}} Q_{\text{tot}} = (\argmax_{a_1} Q_1, \dots, \argmax_{a_n} Q_n) \). Each agent can act greedily on its own local utility and recover the globally greedy joint action, which is what makes decentralized execution optimal rather than merely convenient. QMIX enforces monotonicity by generating the mixing network's weights from a hypernetwork conditioned on the global state and constraining those weights to be non-negative, so the mixing is monotone by construction while still depending richly on the state through the biases.
Self-play, fictitious play, and populations. In competitive games the opponent policy is a design choice. Self-play trains an agent against copies of itself, which supplies an automatically scaling curriculum but can chase intransitive cycles (rock-paper-scissors dynamics) or overfit to its own quirks. Fictitious play (Brown, 1951) is the classical fix: each player best-responds to the time-average of the opponents' historical play rather than their latest policy, and in two-player zero-sum games this average converges to a Nash equilibrium. Modern systems generalize this to a population: AlphaStar (Vinyals et al., 2019) trained a league of agents including deliberate exploiters whose job was to find and punish the weaknesses of the main agents, and population-based training (Jaderberg et al., 2017; 2019) evolved hyperparameters and policies jointly by periodically copying the weights of stronger population members onto weaker ones and perturbing them. The common thread is that a single fixed opponent is never a safe training signal in a game; robustness comes from training against a diverse, adapting distribution of opponents.
Exploration beyond epsilon-greedy
Epsilon-greedy explores by acting randomly a fixed fraction of the time. In a problem where reward is reached only after a long, specific sequence of actions, this is hopeless: the probability of stumbling onto the sequence by chance decays exponentially in its length. Directed exploration replaces undirected noise with an intrinsic reward that pays the agent for reaching states it understands poorly, so that novelty itself becomes something to seek.
Counts and pseudo-counts. The theory of optimism in the face of uncertainty says to add an exploration bonus that decays with how often a state has been visited, classically \( \tilde r(s) = r(s) + \beta / \sqrt{N(s)} \) with \( N(s) \) the visitation count. In large or continuous state spaces exact counts are meaningless because no state is visited twice. Pseudo-counts (Bellemare et al., 2016) recover the idea by deriving an implied count from a density model \( \rho \) over states: if \( \rho(s) \) is the model's probability of \( s \) before observing it and \( \rho'(s) \) is the probability after training on one more occurrence of \( s \), the pseudo-count
$$ \hat N(s) = \frac{\rho(s)\,\big(1 - \rho'(s)\big)}{\rho'(s) - \rho(s)} $$is the count a tabular estimator would have needed to produce that much change in probability. It reduces to a true count in the tabular case and degrades gracefully to a generalized count when the model shares statistical strength across similar states, which is what lets a bonus \( \beta / \sqrt{\hat N(s)} \) drive exploration in pixel spaces.
Intrinsic curiosity (ICM). The intrinsic curiosity module (Pathak et al., 2017) rewards prediction error under a learned forward model, but in a feature space chosen to ignore what the agent cannot control. It learns an inverse model that predicts the action from consecutive states, which forces the feature encoder \( \phi \) to keep only the controllable part of the observation and discard distractors like moving backgrounds, and then rewards the agent by the error of a forward model in that feature space, \( r^i_t = \tfrac12 \| \hat\phi(s_{t+1}) - \phi(s_{t+1}) \|^2 \). The feature selection is what distinguishes ICM from naively rewarding pixel-prediction error, which would chase any source of noise.
Random network distillation (RND). RND (Burda et al., 2018) is the most robust of the family and the cleanest to derive. Fix a randomly initialized target network \( f: \mathcal{S} \to \R^{k} \) and never train it. Train a predictor network \( \hat f_\theta \) to regress the target's output by minimizing \( \| \hat f_\theta(s) - f(s) \|^2 \) on the states the agent actually visits. The intrinsic reward is the predictor's error,
$$ r^{i}(s) = \big\| \hat f_\theta(s) - f(s) \big\|^{2}. $$Why this measures novelty: the target \( f \) is a fixed deterministic function, so its output on \( s \) is a fixed but arbitrary vector, and the only thing the predictor can do to lower its error on \( s \) is to have been trained on \( s \) or on states near it. For a state visited many times the predictor has fit \( f \) there and the error is small; for a novel state the predictor has never received a gradient pulling it toward \( f(s) \), so the error is large. The signal is a measure of epistemic novelty, distance from the training distribution in the predictor's function class, and it sidesteps the noisy-TV problem that plagues forward-dynamics curiosity. A forward model rewards unpredictable transitions, so a source of pure noise (a screen of static, a random number generator the agent can trigger) yields permanently high reward and traps the agent. RND regresses a deterministic target, so stochasticity in the environment does not inflate the error: once a state has been seen enough, \( f(s) \) is learnable regardless of how random the dynamics leaving it are. That single property, deterministic target instead of stochastic prediction, is why RND generalizes where ICM's forward term can fail.
Information gain (VIME). A more principled objective rewards actions for the information they reveal about the environment's dynamics. VIME (Houthooft et al., 2016) maintains a Bayesian posterior over the parameters \( \theta \) of a dynamics model and rewards the agent by the information gain each transition provides, the KL divergence from prior to posterior, \( r^{i}_t = \KL\big(p(\theta \mid \xi_t, a_t, s_{t+1}) \,\|\, p(\theta \mid \xi_t)\big) \). This is exactly the reduction in uncertainty about the world model, so the agent is paid to run experiments that teach it the dynamics; the practical difficulty is that the posterior is intractable and must be approximated variationally, which is why the simpler prediction-error proxies above are more common in practice.
Constrained MDPs and safe reinforcement learning
Safety in RL is most cleanly formalized not as a modified reward but as a constraint. A constrained MDP (Altman, 1999) augments the MDP with one or more cost functions \( c(s,a) \) and requires the policy to keep expected discounted cost under a budget \( d \):
$$ \max_{\pi}\ J_r(\pi) = \E^{\pi}\!\left[\sum_t \gamma^t r_t\right] \quad \text{subject to} \quad J_c(\pi) = \E^{\pi}\!\left[\sum_t \gamma^t c_t\right] \le d. $$Folding the cost into the reward with a fixed penalty weight is exactly what a CMDP avoids, because the right weight is unknown and task-dependent; the CMDP instead solves for the weight. Form the Lagrangian with a multiplier \( \lambda \ge 0 \),
$$ \mathcal{L}(\pi, \lambda) = J_r(\pi) - \lambda\big(J_c(\pi) - d\big), $$and solve the saddle-point problem \( \max_\pi \min_{\lambda \ge 0} \mathcal{L} \). The dual variable \( \lambda \) is the price of cost: gradient ascent on \( \pi \) and gradient descent on \( \lambda \), with the update \( \lambda \leftarrow [\lambda + \eta(J_c - d)]_+ \), raises the price whenever the constraint is violated and lowers it whenever there is slack, so \( \lambda \) settles at the shadow price that makes the constraint tight. This is Lagrangian PPO/SAC, the workhorse of safe RL, and it inherits both the strengths and the oscillation of primal-dual methods: because \( \lambda \) chases a moving policy, the constraint is satisfied only on average and can spike during training.
CPO (Constrained Policy Optimization, Achiam et al., 2017) enforces the constraint at every update instead of asymptotically. It extends the trust-region argument behind TRPO (also on the deep RL page) to the constrained setting: at each step it maximizes a local linear model of the reward advantage subject to a local linear model of the cost advantage staying under budget and a KL trust region keeping the step small,
$$ \theta_{k+1} = \argmax_{\theta}\ g_r^{\T}(\theta - \theta_k) \quad \text{s.t.}\quad J_c(\theta_k) + g_c^{\T}(\theta - \theta_k) \le d, \ \ \tfrac12 (\theta-\theta_k)^{\T} H (\theta - \theta_k) \le \delta, $$where \( g_r, g_c \) are the reward and cost advantage gradients and \( H \) is the Fisher information. CPO comes with a monotonic-improvement-with-constraint guarantee: it bounds the worst-case constraint violation of the new policy in terms of the trust-region radius, so the policy stays near-feasible throughout training rather than only at convergence. The cost is a per-step constrained quadratic program, and a recovery rule for the case where the current policy is already infeasible.
Shielding takes a different stance: rather than learn to satisfy the constraint, wrap the policy in a shield (Alshiekh et al., 2018), a correct-by-construction filter synthesized from a formal specification that overrides any proposed action that could lead to a violation, substituting a safe one. Learning proceeds unchanged inside the safe set, and the guarantee is hard rather than expected: the specification is never violated during learning or deployment, at the price of needing a model good enough to synthesize the shield. The three approaches, Lagrangian, trust-region, and shield, trade off softness of the guarantee against how much prior knowledge of the dynamics they require, and Garcia and Fernandez (2015) survey the full landscape.
The reproducibility problem in deep RL
A page on advanced RL that did not warn about how easily its own results mislead would be incomplete. Henderson et al. (2018) documented that deep policy-gradient results are far less stable than published numbers suggest. Their findings, which have held up, are worth stating precisely because they change how you should read every benchmark on this page. Running the same algorithm with the same hyperparameters and only different random seeds produced learning curves that differed enough that two disjoint sets of five seeds of the same algorithm could be reported as one beating the other with apparent statistical significance. The choice of the codebase mattered as much as the choice of algorithm: independent implementations of the same method differed by more than the gap between different methods. Reward scale, network architecture, and even the activation function moved results by amounts comparable to the algorithmic contribution being tested.
The methodological consequences are now standard practice, and they are the answer expected when an interview asks how you would evaluate an RL agent honestly. Report results across many seeds, not three, and report the full distribution or a bootstrap confidence interval rather than the max or the mean of the top runs. Separate the seeds used for tuning from the seeds used for the final reported number, or the evaluation leaks. Compare against a strong, identically tuned baseline in the same codebase, because a weak baseline manufactures an improvement out of nothing. Agarwal et al. (2021), in Deep RL at the Edge of the Statistical Precipice, extended this into a concrete protocol built on interquantile means and stratified bootstrap intervals, and it is the current standard for reporting on benchmark suites. The reproducibility literature is not a footnote to the algorithms; it is the reason to trust or distrust any claim about them.
Worked problems
An option started in state \( s \) executes for exactly four primitive steps and then terminates in state \( s' \), collecting the reward sequence \( (r_0, r_1, r_2, r_3) = (2, 0, 1, 3) \). The discount is \( \gamma = 0.9 \), and the current value estimate of the return state is \( V(s') = 5 \). Compute the option's cumulative discounted reward \( R(s,\omega) \), its effective discount \( \Gamma \), and the one-step SMDP target \( R + \Gamma\, V(s') \).
Solution. The cumulative discounted reward sums the rewards each weighted by the discount at its step, \( R = 2 + 0.9\cdot 0 + 0.9^2\cdot 1 + 0.9^3 \cdot 3 = 2 + 0 + 0.81 + 0.729\cdot 3 \). Since \( 0.9^3 = 0.729 \), the last term is \( 0.729 \times 3 = 2.187 \), so \( R = 2 + 0.81 + 2.187 = 4.997 \). The effective discount for a deterministic four-step option is \( \Gamma = \gamma^{4} = 0.9^4 = 0.6561 \). The SMDP target is \( R + \Gamma\, V(s') = 4.997 + 0.6561 \times 5 = 4.997 + 3.2805 = 8.2775 \). The point to internalize is that a single SMDP backup discounts the bootstrap by \( \gamma^{4} \), not \( \gamma \): four primitive steps are collapsed into one decision, which is precisely the credit-assignment shortcut temporal abstraction buys.
A C51 network uses \( N = 11 \) atoms uniformly spaced on \( [V_{\min}, V_{\max}] = [-10, 10] \), so \( \Delta z = 2 \) and the atoms are \( z = (-10, -8, \dots, 10) \). The greedy next-state distribution places mass \( 0.5 \) on the atom at \( z_4 = -2 \) and mass \( 0.5 \) on the atom at \( z_7 = 4 \). With reward \( r = 1 \) and discount \( \gamma = 0.9 \), project the Bellman target \( \mathcal{T} z_j = 1 + 0.9 z_j \) back onto the atoms and give the resulting probability vector.
Solution. Take the two atoms carrying mass. For \( z_4 = -2 \), the transformed value is \( \mathcal{T} z_4 = 1 + 0.9(-2) = -0.8 \), inside \( [-10,10] \) so no clipping. Its position on the grid is \( b = (\mathcal{T} z_4 - V_{\min})/\Delta z = (-0.8 + 10)/2 = 4.6 \), which lies between atom \( 4 \) and atom \( 5 \). Split its mass by closeness: atom \( 4 \) gets \( 0.5\,(5 - 4.6) = 0.5 \times 0.4 = 0.2 \) and atom \( 5 \) gets \( 0.5\,(4.6 - 4) = 0.5 \times 0.6 = 0.3 \). For \( z_7 = 4 \), the transformed value is \( \mathcal{T} z_7 = 1 + 0.9(4) = 4.6 \), with \( b = (4.6 + 10)/2 = 7.3 \), between atoms \( 7 \) and \( 8 \). Atom \( 7 \) gets \( 0.5\,(8 - 7.3) = 0.5 \times 0.7 = 0.35 \) and atom \( 8 \) gets \( 0.5\,(7.3 - 7) = 0.5 \times 0.3 = 0.15 \). The projected distribution is therefore \( m_4 = 0.2,\ m_5 = 0.3,\ m_7 = 0.35,\ m_8 = 0.15 \) and zero elsewhere, which sums to \( 0.2 + 0.3 + 0.35 + 0.15 = 1.0 \), confirming the projection conserves probability. The cross-entropy loss then compares this target vector against the network's predicted distribution at \( (s,a) \).
Consider a five-state line, states \( 0,1,2,3,4 \), where the reward is \( 0 \) at the goal and \( -1 \) everywhere else, and the agent's intended goal is \( g = 4 \). A rollout under the current (untrained) policy visits \( 0 \to 1 \to 2 \) and stops, never reaching \( 4 \). Explain, in terms of the temporal-difference target, why standard replay learns nothing from this rollout, and show what hindsight relabeling to \( g' = 2 \) changes.
Solution. Under the intended goal \( g = 4 \), every state visited on this rollout satisfies \( d(s, 4) > 0 \), so every transition has reward \( -1 \). The Q-learning target for the last transition \( (s=1, a=\text{right}, s'=2) \) is \( r + \gamma \max_{a'} Q(2, a', 4) = -1 + \gamma \max_{a'} Q(2, a', 4) \), and the same \( -1 \) appears in every target on the trajectory. With the reward channel pinned to a constant, the only variation across transitions comes from the bootstrap term, which is itself near-uniform for an untrained network, so the gradient carries essentially no information about which action was good. Now relabel the goal to the achieved final state \( g' = 2 \). The transition into state \( 2 \) now has \( d(2, 2) = 0 \), so its reward becomes \( 0 \), and its target is \( 0 + \gamma \max_{a'} Q(2, a', 2) \). The reward channel across the buffer now takes both values, \( 0 \) for the transition that reached \( g' \) and \( -1 \) for the earlier ones, so the target varies and the gradient distinguishes the action that reached the goal from the ones that did not. No bias is introduced because the dynamics do not depend on the goal: the transition \( 1 \to 2 \) is a true fact of the environment under any goal label. Relabeling converts a constant, uninformative reward channel into a varying one, which is the entire mechanism of HER.
Two players play the Battle of the Sexes. The row player's payoffs are \( \begin{psmallmatrix} 2 & 0 \\ 0 & 1 \end{psmallmatrix} \) and the column player's are \( \begin{psmallmatrix} 1 & 0 \\ 0 & 2 \end{psmallmatrix} \), where the first row/column is action A and the second is action B, and both prefer to coordinate. Find all Nash equilibria, including the mixed one, and give the row player's expected payoff at the mixed equilibrium.
Solution. The two pure equilibria are read off directly: at \( (A, A) \) neither player gains by deviating, giving payoffs \( (2, 1) \), and at \( (B, B) \) likewise, giving \( (1, 2) \). For the mixed equilibrium, let the row player play A with probability \( p \) and the column player play A with probability \( q \). The row player mixes only if indifferent between A and B given the column player's \( q \): the payoff to A is \( 2q + 0(1-q) = 2q \), and to B is \( 0\,q + 1(1-q) = 1 - q \). Setting them equal, \( 2q = 1 - q \Rightarrow 3q = 1 \Rightarrow q = 1/3 \). By the symmetric argument on the column player, whose payoffs to A and B are \( 1\cdot p \) and \( 2(1-p) \), indifference gives \( p = 2(1-p) \Rightarrow 3p = 2 \Rightarrow p = 2/3 \). So the mixed Nash equilibrium is \( (p, q) = (2/3,\ 1/3) \). The row player's expected payoff at this equilibrium is \( 2q = 2 \times 1/3 = 2/3 \approx 0.667 \), strictly worse than either pure equilibrium's \( 1 \) or \( 2 \) for the row player, which is the classic lesson: the mixed equilibrium of a coordination game is Pareto-dominated, and miscoordination is costly.
Derive the option-critic termination gradient sign rule. Given that the termination function \( \beta_\omega(s') \) enters the return only through the continuation value \( U(s',\omega) = (1-\beta_\omega(s'))\,Q_\Omega(s',\omega) + \beta_\omega(s')\,V_\Omega(s') \), show that \( \partial U / \partial \beta_\omega(s') = -A_\Omega(s',\omega) \), and state when the optimal termination probability is \( 0 \) versus \( 1 \).
Solution. Differentiate \( U \) with respect to \( \beta_\omega(s') \), treating \( Q_\Omega \) and \( V_\Omega \) as constants at \( s' \): \( \partial U / \partial \beta = -Q_\Omega(s',\omega) + V_\Omega(s') = -\big(Q_\Omega(s',\omega) - V_\Omega(s')\big) = -A_\Omega(s', \omega) \), where \( A_\Omega \) is the advantage of the current option over the value of re-deciding. By the chain rule the termination parameter gradient of the objective is \( \partial J / \partial \vartheta = \E[\,(\partial \beta_{\omega,\vartheta}(s')/\partial \vartheta)\cdot(\partial U/\partial\beta)\,] = -\,\E[\,(\partial \beta/\partial\vartheta)\, A_\Omega(s',\omega)\,] \), which is the stated gradient. To maximize the return, ascend it: when \( A_\Omega(s',\omega) > 0 \) the current option is better than average, the gradient pushes \( \beta \) toward \( 0 \), and the option should continue; when \( A_\Omega(s',\omega) < 0 \) the option is worse than average, the gradient pushes \( \beta \) toward \( 1 \), and the option should terminate so the policy over options can switch. The optimal deterministic termination is thus the indicator \( \beta^\ast(s') = \mathbb{1}[A_\Omega(s',\omega) < 0] \): stop exactly when continuing is worse than re-deciding. This is why an unregularized option-critic collapses, since any strictly positive or negative advantage drives \( \beta \) to a corner, and why a deliberation cost that adds a margin to the advantage is needed to keep options extended.
A constrained MDP has a policy whose expected discounted cost is currently \( J_c(\pi) = 30 \) against a budget \( d = 25 \). The Lagrange multiplier is updated by \( \lambda \leftarrow [\lambda + \eta(J_c - d)]_+ \) with step size \( \eta = 0.1 \) and starts at \( \lambda = 0.5 \). Compute the next two multiplier values assuming the cost stays at \( 30 \), then at \( 20 \), and explain what the multiplier is converging to.
Solution. The constraint is violated, \( J_c - d = 30 - 25 = 5 > 0 \), so the multiplier rises: \( \lambda_1 = [0.5 + 0.1 \times 5]_+ = [0.5 + 0.5]_+ = 1.0 \). If the cost stays at \( 30 \), the next step is \( \lambda_2 = [1.0 + 0.1 \times 5]_+ = 1.5 \): the price of cost keeps climbing while the policy overspends, which in the coupled saddle-point dynamics makes the reward-plus-penalty objective increasingly favor cheaper policies. Now suppose the raised price has pushed the policy to \( J_c = 20 \), giving slack \( J_c - d = 20 - 25 = -5 < 0 \). The multiplier falls: \( \lambda_3 = [1.5 + 0.1 \times(-5)]_+ = [1.5 - 0.5]_+ = 1.0 \). The projection \( [\cdot]_+ \) matters because a multiplier can never go negative, a slack constraint should not reward cost. The multiplier is performing dual gradient descent and converges to the shadow price \( \lambda^\ast \) at which the constraint is exactly tight, \( J_c(\pi) = d \); at that fixed point the update leaves \( \lambda \) unchanged because \( J_c - d = 0 \). The oscillation seen here, up while overspending, down while underspending, is the characteristic behavior of Lagrangian safe RL and the reason the constraint is satisfied only on average during training.
Implementation
The C51 categorical projection is the piece of distributional RL most often
gotten wrong, because the index arithmetic on the grid is fiddly and an
off-by-one silently corrupts the target. The two implementations below compute
the projection of Problem 2 exactly, vectorized over the batch and over atoms.
The PyTorch version uses index_add_ to scatter the split mass onto
the target grid; the JAX version uses segment_sum for the same
scatter under jit. Both return the projected target distribution
\( m \) that the cross-entropy loss consumes.
import torch
def categorical_projection(next_probs, rewards, dones, gamma,
v_min=-10.0, v_max=10.0, n_atoms=11):
"""Project the distributional Bellman target onto a fixed atom grid (C51).
next_probs: (B, n_atoms) greedy next-state distribution p(s', a*)
rewards: (B,) scalar reward r
dones: (B,) 1.0 if terminal else 0.0
returns m: (B, n_atoms) projected target distribution
"""
B = next_probs.shape[0]
z = torch.linspace(v_min, v_max, n_atoms) # (n_atoms,) atom values
dz = (v_max - v_min) / (n_atoms - 1)
# Tz = r + gamma * z, zeroed after a terminal transition, then clipped.
Tz = rewards[:, None] + (1.0 - dones)[:, None] * gamma * z[None, :]
Tz = Tz.clamp(v_min, v_max) # (B, n_atoms)
b = (Tz - v_min) / dz # continuous grid position
lo = b.floor().long() # lower atom index
hi = b.ceil().long() # upper atom index
# Guard the exact-integer case so mass is not double counted.
lo = torch.where((hi == lo) & (lo > 0), lo - 1, lo)
hi = torch.where((hi == lo) & (lo < n_atoms - 1), lo + 1, hi)
m = torch.zeros(B, n_atoms)
offset = (torch.arange(B) * n_atoms)[:, None] # flatten batch for index_add_
w_lo = next_probs * (hi.float() - b) # mass to the lower atom
w_hi = next_probs * (b - lo.float()) # mass to the upper atom
m.view(-1).index_add_(0, (lo + offset).view(-1), w_lo.view(-1))
m.view(-1).index_add_(0, (hi + offset).view(-1), w_hi.view(-1))
return m
if __name__ == "__main__":
p = torch.zeros(1, 11); p[0, 4] = 0.5; p[0, 7] = 0.5
m = categorical_projection(p, torch.tensor([1.0]), torch.tensor([0.0]), 0.9)
print(m.round(decimals=3)) # -> 0.2 at 4, 0.3 at 5, 0.35 at 7, 0.15 at 8
import jax, jax.numpy as jnp
from functools import partial
@partial(jax.jit, static_argnums=(5,))
def categorical_projection(next_probs, rewards, dones, gamma,
bounds=(-10.0, 10.0), n_atoms=11):
"""C51 projection, jit-compiled. Shapes match the PyTorch version:
next_probs (B, n_atoms), rewards (B,), dones (B,) -> m (B, n_atoms)."""
v_min, v_max = bounds
B = next_probs.shape[0]
z = jnp.linspace(v_min, v_max, n_atoms) # (n_atoms,)
dz = (v_max - v_min) / (n_atoms - 1)
Tz = rewards[:, None] + (1.0 - dones)[:, None] * gamma * z[None, :]
Tz = jnp.clip(Tz, v_min, v_max) # (B, n_atoms)
b = (Tz - v_min) / dz
lo = jnp.floor(b).astype(jnp.int32)
hi = jnp.ceil(b).astype(jnp.int32)
exact = (hi == lo)
lo = jnp.where(exact & (lo > 0), lo - 1, lo)
hi = jnp.where(exact & (lo < n_atoms - 1), lo + 1, hi)
offset = (jnp.arange(B) * n_atoms)[:, None] # flatten batch index
w_lo = (next_probs * (hi - b)).reshape(-1)
w_hi = (next_probs * (b - lo)).reshape(-1)
idx_lo = (lo + offset).reshape(-1)
idx_hi = (hi + offset).reshape(-1)
flat = (jax.ops.segment_sum(w_lo, idx_lo, num_segments=B * n_atoms)
+ jax.ops.segment_sum(w_hi, idx_hi, num_segments=B * n_atoms))
return flat.reshape(B, n_atoms)
if __name__ == "__main__":
p = jnp.zeros((1, 11)).at[0, 4].set(0.5).at[0, 7].set(0.5)
m = categorical_projection(p, jnp.array([1.0]), jnp.array([0.0]), 0.9)
print(jnp.round(m, 3)) # -> 0.2 at 4, 0.3 at 5, 0.35 at 7, 0.15 at 8
Random network distillation is the second implementation, and the one whose subtlety is not the code but the normalization. The intrinsic reward is a squared prediction error, but that error's scale drifts wildly over training, so RND standardizes it by a running estimate of its standard deviation and standardizes the observations fed to both networks; without those two normalizations the bonus is unusable. The target network is created once, its parameters are frozen (no gradient ever flows to it), and only the predictor is optimized.
import torch, torch.nn as nn
class RND(nn.Module):
"""Random network distillation intrinsic reward (Burda et al., 2018).
The target is fixed at init; only the predictor learns. The bonus is the
per-state squared error between predictor and target embeddings."""
def __init__(self, obs_dim, feat_dim=128):
super().__init__()
def net():
return nn.Sequential(nn.Linear(obs_dim, 256), nn.ReLU(),
nn.Linear(256, feat_dim))
self.target = net()
self.predictor = net()
for p in self.target.parameters(): # freeze the target permanently
p.requires_grad_(False)
self.register_buffer("rew_var", torch.ones(())) # running reward variance
def intrinsic_reward(self, obs):
# obs: (B, obs_dim), assumed already observation-normalized
with torch.no_grad():
tgt = self.target(obs) # (B, feat_dim)
pred = self.predictor(obs) # (B, feat_dim)
err = (pred - tgt).pow(2).mean(dim=1) # (B,) novelty per state
# standardize the bonus by a running std so its scale stays stable
self.rew_var.mul_(0.99).add_(0.01 * err.detach().var())
return err / (self.rew_var.sqrt() + 1e-8)
def loss(self, obs):
with torch.no_grad():
tgt = self.target(obs)
return (self.predictor(obs) - tgt).pow(2).mean() # predictor regression
if __name__ == "__main__":
rnd = RND(obs_dim=8)
obs = torch.randn(4, 8)
print(rnd.intrinsic_reward(obs)) # high for novel obs, shrinks as trained
opt = torch.optim.Adam(rnd.predictor.parameters(), lr=1e-3)
for _ in range(200):
opt.zero_grad(); L = rnd.loss(obs); L.backward(); opt.step()
print(rnd.intrinsic_reward(obs)) # smaller after fitting these states
import jax, jax.numpy as jnp
import flax.linen as nn
import optax
class Embed(nn.Module):
feat_dim: int = 128
@nn.compact
def __call__(self, x):
x = nn.relu(nn.Dense(256)(x))
return nn.Dense(self.feat_dim)(x)
def make_rnd(key, obs_dim, feat_dim=128):
kt, kp = jax.random.split(key)
net = Embed(feat_dim)
dummy = jnp.zeros((1, obs_dim))
target_params = net.init(kt, dummy) # frozen: never passed to the optimizer
pred_params = net.init(kp, dummy)
return net, target_params, pred_params
def intrinsic_reward(net, target_params, pred_params, obs):
tgt = jax.lax.stop_gradient(net.apply(target_params, obs)) # (B, feat_dim)
pred = net.apply(pred_params, obs)
err = jnp.mean((pred - tgt) ** 2, axis=1) # (B,) novelty
return err / (jnp.sqrt(err.var()) + 1e-8) # standardized bonus
def rnd_loss(pred_params, net, target_params, obs):
tgt = jax.lax.stop_gradient(net.apply(target_params, obs))
pred = net.apply(pred_params, obs)
return jnp.mean((pred - tgt) ** 2)
if __name__ == "__main__":
key = jax.random.PRNGKey(0)
net, tgt_p, pred_p = make_rnd(key, obs_dim=8)
obs = jax.random.normal(jax.random.PRNGKey(1), (4, 8))
print(intrinsic_reward(net, tgt_p, pred_p, obs)) # high for novel obs
opt = optax.adam(1e-3); state = opt.init(pred_p)
grad_fn = jax.grad(rnd_loss)
for _ in range(200):
g = grad_fn(pred_p, net, tgt_p, obs)
updates, state = opt.update(g, state); pred_p = optax.apply_updates(pred_p, updates)
print(intrinsic_reward(net, tgt_p, pred_p, obs)) # smaller after fitting
The final two implementations are the pure-Python computations behind Problems
1 and 4: the SMDP option discount and a two-player matrix-game equilibrium
solver. They use only numpy for arithmetic and reproduce the hand
calculations exactly, so they double as executable checks on the worked
problems above.
import numpy as np
# --- Problem 1: SMDP option discounting -------------------------------------
def smdp_target(rewards, gamma, v_next):
"""Cumulative discounted reward, effective discount, and one-step SMDP target
for an option that ran len(rewards) primitive steps."""
k = len(rewards)
R = sum(gamma ** t * r for t, r in enumerate(rewards))
Gamma = gamma ** k
return R, Gamma, R + Gamma * v_next
R, G, target = smdp_target([2, 0, 1, 3], gamma=0.9, v_next=5.0)
print(R, G, target) # 4.997 0.6561 8.2775
# --- Problem 4: 2x2 mixed Nash equilibrium ----------------------------------
def mixed_nash_2x2(row_payoff, col_payoff):
"""Interior mixed equilibrium of a 2x2 game. Each player mixes to make the
other indifferent. Returns (p, q) = P(row plays A), P(col plays A)."""
a, b, c, d = row_payoff.flatten() # row: A->[a,b], B->[c,d] over col's A,B
e, f, g, h = col_payoff.flatten() # col payoffs, same layout
# Row indifferent in col's mix q: a*q + b*(1-q) = c*q + d*(1-q)
q = (d - b) / ((a - c) - (b - d))
# Col indifferent in row's mix p: e*p + g*(1-p) = f*p + h*(1-p)
p = (h - g) / ((e - f) - (g - h))
return p, q
row = np.array([[2, 0], [0, 1]])
col = np.array([[1, 0], [0, 2]])
p, q = mixed_nash_2x2(row, col)
print(p, q) # 0.6667 0.3333 (row plays A 2/3, col plays A 1/3)
print(2 * q) # 0.6667 row's expected payoff at the mixed NE
How it is done in practice
The gap between these derivations and a working system is mostly about scale, engineering discipline, and the fact that the clean assumptions rarely hold. A few concrete observations from deployed systems.
Distributional RL earns its keep inside Rainbow (Hessel et al., 2018), which found that the C51 head was one of the largest single contributors when the Atari improvements were combined and ablated, second only to prioritized replay. The current successor, DreamerV3 and the model-based line, and the IQN-style implicit quantile heads used in production agents, keep the distributional representation because it stabilizes learning even when only the mean is used to act: fitting the whole distribution is a richer auxiliary signal than fitting the mean alone. The reference implementations to trust are Dopamine's, which reproduce the published curves.
Multi-agent CTDE is where theory and practice diverge most. QMIX's monotonicity constraint is provably limiting, it cannot represent joint value functions where an agent's best action depends on another's, and follow-up work (QTRAN, weighted QMIX, QPLEX) relaxed it, yet plain QMIX remains a stubbornly strong baseline on the StarCraft multi-agent challenge because the constraint is a useful inductive bias more often than it is a fatal restriction. AlphaStar's league was the practical demonstration that self-play alone is insufficient at scale: without dedicated exploiter agents mining for weaknesses, the main agents converged to exploitable strategies. Running that league required thousands of concurrent actors, which is the real engineering content, the throughput problem discussed on the deep RL page is even more acute with a population.
Exploration bonuses are notoriously finicky in production. RND is the method most people reach for precisely because it has the fewest moving parts and no forward-model instability, but its bonus must be normalized carefully, both the observations and the reward, and the intrinsic and extrinsic returns are usually estimated with separate value heads and combined, because their scales and discount horizons differ. The Montezuma's Revenge result that made RND famous depended on these details as much as on the core idea.
Safe RL in the field leans on the Lagrangian formulation far more than on CPO, despite CPO's stronger guarantees, because the per-step constrained quadratic program is expensive and brittle, and a well-tuned Lagrangian PPO is simpler to operate. The Safety Gym and later Safety-Gymnasium benchmarks are where these are compared, and the honest summary is that no method keeps the constraint perfectly satisfied throughout training; the practical question is how large and how frequent the violations are, which returns the discussion to careful, multi-seed evaluation.
The current research frontier
Several threads are active as of the mid-2020s, and they draw on different groups. Hierarchy has largely shifted from learning options end to end, which proved unstable, toward goal-conditioned and skill-discovery methods that learn a reusable repertoire without external reward: DIAYN (Eysenbach et al., Berkeley, 2018) and its information-theoretic descendants learn diverse skills by maximizing the mutual information between a latent skill code and the states it visits, and this unsupervised-skill line now feeds pretraining for downstream RL.
Distributional RL has moved toward using the distribution for more than variance reduction: risk-sensitive control through distortion of the quantile function (from the IQN line, DeepMind), and the observation that distributional heads improve representation learning even in actor-critic methods, are both active. The theoretical question of exactly why distributional RL helps when only the mean is used to act remains only partly answered.
Multi-agent learning has been reshaped by the success of population methods and by the connection to game-theoretic solvers. PSRO (Policy-Space Response Oracles, Lanctot et al., DeepMind, 2017) frames the whole enterprise as iteratively expanding a population and solving the resulting meta-game, unifying self-play, fictitious play, and the double oracle method under one umbrella, and it underlies much of the recent work on solving large imperfect-information games.
The largest practical shift, though, is that RL's center of gravity has moved to language-model post-training, where several topics on this page reappear in new clothing. The exploration problem in reasoning is a sparse-reward, long-horizon-credit-assignment problem; the reproducibility concerns of Henderson and Agarwal apply directly to reported gains from RL fine-tuning; and constrained optimization reappears as the KL-to-reference penalty that keeps a policy from drifting too far during RLHF. That connection, and the GRPO objective that realizes it, is developed on the deep RL page; the point here is that the advanced single-environment machinery and the language-model work are converging, not diverging.
Open source to read
-
DLR-RM/stable-baselines3
is the reference for correct, well-tested single-agent implementations. Read
common/buffers.pyfor the replay and hindsight-relabeling logic, and theHerReplayBufferto see the goal-relabeling of this page in production code. -
google/dopamine
is the cleanest distributional-RL codebase. Open
dopamine/jax/agents/rainbow/rainbow_agent.pyand read theproject_distributionfunction; it is the categorical projection of Problem 2, and comparing it to the code above is the fastest way to be sure you understand the index arithmetic. -
oxwhirl/pymarl
is the canonical QMIX and multi-agent codebase. Read
modules/mixers/qmix.pyto see the hypernetwork that generates the non-negative mixing weights, which is exactly how the monotonicity constraint is enforced in practice. - openai/random-network-distillation is the original RND release. Read the observation and reward normalization in the runner; the core idea is a few lines, and the normalization is where the difficulty actually lives, as the text above stresses.
-
Farama-Foundation/PettingZoo
is the standard multi-agent environment API, the multi-agent analogue of
Gymnasium. Read
pettingzoo/utils/env.pyfor the agent-iteration model that makes turn-based and simultaneous games share one interface. -
google-deepmind/acme
is a research framework built around a clean actor/learner split and reference
agents including distributional and multi-agent ones. Read
acme/agents/jax/for how the algorithms on this page are factored into reusable learner and actor components.
Common misconceptions
"Options are just macro-actions, a fixed sequence of primitives." No. An option is a closed-loop policy with a termination condition, not an open-loop sequence. It reacts to the states it encounters and stops when its termination function fires, which is why it can be robust to stochastic dynamics where a fixed action sequence would fail.
"Distributional RL helps because it reduces variance in the value estimate." That is not the established explanation. The action is still taken by the mean, so the point estimate used to act is the same; the benefit is largely an auxiliary-task and representation-learning effect from fitting a richer target, and the distributional Bellman operator is a contraction in Wasserstein, not in the moments, so it is not simply a smoother mean estimator.
"HER works by adding reward shaping." No. HER changes the goal an episode is labeled with, not the reward function's form. Because the dynamics do not depend on the goal, relabeling introduces no bias, whereas hand-designed reward shaping generally changes the optimal policy unless it is a potential-based transformation.
"Independent Q-learners will converge in a multi-agent game if you train long enough." Not in general. The environment each learner sees is non-stationary because the others are changing, which voids the stationary-MDP assumption behind Q-learning's convergence proof, and simple games like matching pennies produce persistent cycles rather than convergence.
"QMIX can represent any cooperative value function." No. The monotonic mixing constraint restricts \( Q_{\text{tot}} \) to functions monotone increasing in each agent's utility, which cannot express tasks where an agent's optimal action flips depending on another agent's action. That limitation is provable and is what motivated QTRAN and QPLEX.
"Curiosity means rewarding whatever the agent cannot predict." That is the naive version, and it fails on stochastic transitions, the noisy-TV problem, where a source of pure noise yields permanent reward. ICM predicts in a controllability-filtered feature space and RND regresses a deterministic target precisely to avoid rewarding irreducible randomness.
"A safe-RL agent trained with a Lagrangian satisfies its constraint throughout training." No. The multiplier chases a moving policy, so the constraint is satisfied only asymptotically and on average; violations during training are expected and are exactly what CPO's trust-region guarantee and shielding's hard filter are designed to prevent.
"If a paper reports a gain over three seeds, the method is better." Three seeds is too few to conclude anything in deep RL. Henderson et al. showed two disjoint five-seed samples of the same algorithm can look significantly different; a credible claim needs many seeds, a confidence interval, and an identically tuned baseline.
Self-check
References
- Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018. incompleteideas.net/book
- Altman, E. Constrained Markov Decision Processes, Chapman & Hall/CRC, 1999. book PDF
- Sutton, R. S., Precup, D., Singh, S. "Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning." Artificial Intelligence 112, 1999. doi:10.1016/S0004-3702(99)00052-1
- Bacon, P.-L., Harb, J., Precup, D. "The option-critic architecture." AAAI 2017. arXiv:1609.05140
- Vezhnevets, A. S. et al. "FeUdal networks for hierarchical reinforcement learning." ICML 2017. arXiv:1703.01161. Dayan, P. and Hinton, G. E. "Feudal reinforcement learning." NeurIPS 1993.
- Schaul, T., Horgan, D., Gregor, K., Silver, D. "Universal value function approximators." ICML 2015. PMLR v37
- Andrychowicz, M. et al. "Hindsight experience replay." NeurIPS 2017. arXiv:1707.01495
- Dayan, P. "Improving generalisation for temporal difference learning: the successor representation." Neural Computation 5, 1993. Barreto, A. et al. "Successor features for transfer in reinforcement learning." NeurIPS 2017. arXiv:1606.05312
- Bellemare, M. G., Dabney, W., Munos, R. "A distributional perspective on reinforcement learning." ICML 2017. arXiv:1707.06887
- Dabney, W., Rowland, M., Bellemare, M. G., Munos, R. "Distributional reinforcement learning with quantile regression (QR-DQN)." AAAI 2018. arXiv:1710.10044. Dabney, W. et al. "Implicit quantile networks for distributional RL (IQN)." ICML 2018. arXiv:1806.06923
- Hessel, M. et al. "Rainbow: combining improvements in deep reinforcement learning." AAAI 2018. arXiv:1710.02298
- Shapley, L. S. "Stochastic games." PNAS 39, 1953. Aumann, R. J. "Subjectivity and correlation in randomized strategies." J. Mathematical Economics 1, 1974.
- Lowe, R. et al. "Multi-agent actor-critic for mixed cooperative-competitive environments (MADDPG)." NeurIPS 2017. arXiv:1706.02275
- Rashid, T. et al. "QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning." ICML 2018. arXiv:1803.11485
- Brown, G. W. "Iterative solution of games by fictitious play." In Activity Analysis of Production and Allocation, 1951. Lanctot, M. et al. "A unified game-theoretic approach to multiagent RL (PSRO)." NeurIPS 2017. arXiv:1711.00832
- Vinyals, O. et al. "Grandmaster level in StarCraft II using multi-agent reinforcement learning (AlphaStar)." Nature 575, 2019. doi:10.1038/s41586-019-1724-z
- Jaderberg, M. et al. "Population based training of neural networks," 2017. arXiv:1711.09846; "Human-level performance in 3D multiplayer games with population-based reinforcement learning." Science 364, 2019.
- Bellemare, M. G. et al. "Unifying count-based exploration and intrinsic motivation (pseudo-counts)." NeurIPS 2016. arXiv:1606.01868
- Pathak, D., Agrawal, P., Efros, A. A., Darrell, T. "Curiosity-driven exploration by self-supervised prediction (ICM)." ICML 2017. arXiv:1705.05363
- Burda, Y., Edwards, H., Storkey, A., Klimov, O. "Exploration by random network distillation." ICLR 2019. arXiv:1810.12894
- Houthooft, R. et al. "VIME: variational information maximizing exploration." NeurIPS 2016. arXiv:1605.09674
- Achiam, J., Held, D., Tamar, A., Abbeel, P. "Constrained policy optimization (CPO)." ICML 2017. arXiv:1705.10528. Alshiekh, M. et al. "Safe reinforcement learning via shielding." AAAI 2018. arXiv:1708.08611
- Garcia, J. and Fernandez, F. "A comprehensive survey on safe reinforcement learning." JMLR 16, 2015. jmlr.org/v16
- Eysenbach, B., Gupta, A., Ibarz, J., Levine, S. "Diversity is all you need: learning skills without a reward function (DIAYN)." ICLR 2019. arXiv:1802.06070
- Henderson, P. et al. "Deep reinforcement learning that matters." AAAI 2018. arXiv:1709.06560. Agarwal, R. et al. "Deep reinforcement learning at the edge of the statistical precipice." NeurIPS 2021. arXiv:2108.13264