Frontiers: Beyond the Standard MDP

Every lesson so far has fixed the same three things and varied only the method: the state was given, the reward was given, and the action was a single primitive step. The Markov decision process handed the agent a Markov state; the environment emitted a scalar reward; and a policy chose one action per time step. That triple is a modeling convenience, and this chapter loosens all three. What we predict need not be reward; what we do need not last one step; and the state the agent reasons over is something it constructs, not something it is handed. These are the frontiers — partly known, partly open — that the deep-learning machinery of the last two lessons meets outside the benchmarks.¹

General value functions

A value function answers one question: starting here and following $\pi$, how much reward will I accumulate? Over the course of the subject that question has quietly widened. Off-policy learning let the value be conditioned on a target policy $\pi$ different from the one generating the data. Generalized discounting then replaced the constant $\gamma$ with a state-dependent termination function $\gamma :\mathcal{S}\to [0,1]$, so a different horizon could apply at each step. The last generalization is to drop reward itself. Instead of summing future rewards, sum the future values of any signal — a sound, a pixel intensity, an internal feature, even another prediction.²

A value function predicts a discounted sum into the future, and nothing forces that sum to be reward. Substituting any other signal gives a forecast of that signal, learned by the same machinery.

The accumulated signal is the cumulant $C_t\in \mathbb{R}$, and the resulting prediction is a general value function, or GVF:

A GVF is specified by three questions: a policy $\pi$ (act how?), a termination $\gamma$ (over what horizon?), and a cumulant $C$ (accumulate what?). Set $C_t=R_t$ and $\gamma$ constant and it collapses to the ordinary value function. Because a GVF has no necessary connection to reward, calling it a value is a slight misnomer; it is really a prediction, or forecast. But it has exactly the form of a value function, so every method here — semi-gradient TD, Generalized Policy Iteration, actor–critic — learns and controls it without change.²

Auxiliary tasks

One prediction is a curiosity; the point is to learn many at once. An artificial neural network can be built with its final layer split into several heads, each computing a different GVF over one shared body. One head predicts the true value (reward as its cumulant); the others predict change in pixels, the next step's reward, the distribution of the return, and so on. All heads backpropagate their errors into the same preceding layers, so the shared representation must serve every prediction at once.³

These extra predictions are auxiliary tasks: in addition to, and in service of, the main task of maximizing reward. The mechanism is representation learning. Some auxiliary tasks are easier than the main one — less delay, a clearer link between action and outcome — so good features surface early on them, and those features then speed the harder main task. Predicting and controlling its sensors over a few seconds might, for instance, force the network to discover the idea of an object — the structure long-horizon reward prediction depends on. In practice this multi-head arrangement has been shown to sharply accelerate learning on the main task.³

A second reason to care about many predictions is biological. One reading of classical conditioning is that evolution wired a fixed reflex to the prediction of a signal rather than to the signal itself: an animal blinks when its prediction of being poked in the eye crosses a threshold, and is spared many pokes. A self-driving car that predicts a collision can be given a built-in reflex to brake before one occurs. The prediction is learned; the response to it is designed. This is the thread that reconnects the algorithms here to the psychology of reinforcement.³

Temporal abstraction via options

The MDP framework is scale-agnostic: it can formalize which muscle to twitch, which flight to book, and which career to pursue. The trouble is doing all three inside one MDP. Planning a flight at the level of muscle twitches is hopeless, yet people move between such levels without seeming to switch at all. The options framework stretches the MDP to cover many time scales at once: formalize the world at a fine time step, but let the agent plan with extended courses of action that terminate on their own.⁴

An option couples two of the objects we already have. It is a pair $\omega =({\pi }_{\omega },{\gamma }_{\omega })$: a policy ${\pi }_{\omega }$ that says which action to take, and a termination function ${\gamma }_{\omega }:\mathcal{S}\to [0,1]$ that says, at each state, the probability the option ends. To execute $\omega$ from state $S_t$, draw the action $A_t$ from ${\pi }_{\omega }(\cdot \mid S_t)$; then with probability $1-{\gamma }_{\omega }(S_{t+1})$ continue, drawing $A_{t+1}$ from the same policy, or else terminate. A single primitive action is the special case of an option whose policy always picks that action and which terminates after one step. Options therefore extend the action space rather than replacing it: the agent may pick a one-step action or an extended option that runs for many steps before returning control.⁴

Because an option is interchangeable with an action, everything built on actions generalizes. The action-value function $q_{\pi }$ becomes an option-value function that returns the expected return of running an option to termination and then following $\pi$. A policy becomes a hierarchical policy that selects among options; the chosen option runs to termination before the next choice. In the simplest learning scheme the update jumps from option initiation to option termination, treating the whole extended run as one transition; intra-option methods update on every intermediate step instead, at the cost of requiring off-policy learning.⁴

The deeper benefit is a model that spans time. A conventional model gives, for each action, the next state and the expected immediate reward. An option model gives, for each option, the expected cumulative discounted reward earned along the way and a discounted distribution over where the option lands and when. The reward part is

where $\tau$ is the random step at which the option terminates. The overall discount $\gamma$ discounts reward along the way, while ${\gamma }_{\omega }$ governs termination — two distinct roles for two distinct discounts. The state part is subtler: because an option can terminate after any number of steps, each landing state is discounted by its own ${\gamma }^k$, so the resulting quantity $p(s^{\prime }\mid s,\omega )$ is no longer a transition probability and no longer sums to one. With these option models one can write Bellman equations and value-iteration algorithms that plan over options and ordinary actions alike, and planning is faster because each option can leap over many steps.⁴

One natural way to learn an option model is to phrase it as a collection of GVFs and learn them with the methods above: choose the cumulant to be reward for the reward part, and a discounted transition indicator for the state part. So the two frontiers meet — GVFs are the mechanism by which temporal abstraction becomes learnable — though assembling all the pieces, with function approximation, remains beyond the current state of the art.⁴

An option model, worked. Take a walk to the door option that runs a deterministic four-step path collecting rewards $R_1=0$, $R_2=0$, $R_3=-1$ (bumped a wall), $R_4=+10$ (reached the door), then terminates at step $\tau =4$. With $\gamma =0.9$ the option's reward-model entry is the discounted sum along the way:

The state-model entry for the landing state $s^{\prime }$ (the doorway) is ${\gamma }^{\tau }=0.9^4=0.656$ — not a probability but a discounted weight, which is why it lands below $1$ even though the option reaches $s^{\prime }$ with certainty. Now suppose the hierarchical policy above compares this option against a go to the window option with model value $r(s,{\omega }^{\prime })=3.0$ and landing weight $0.9^2=0.81$ onto a state $s^{\prime \prime }$ whose value is $v(s^{\prime \prime })=4.0$, versus the door's landing value $v(s^{\prime })=5.0$. The option-value of each is $r(s,\omega )+{\gamma }^{\tau }v(\text{landing})$:

The door option wins, $9.76$ against $6.24$, and the hierarchical policy makes one decision to commit to four primitive steps. Planning over options collapses a four-step lookahead into a single Bellman backup, which is why option models make planning faster — the option leaps over its own internal steps.

Observations and state

Every learned value function so far has been a function of the environment's state. In Part I that state lived in a table, which is to assume the environment is fully observed — any state distinguishable in principle gets its own cell. Real sensory input is not like that. A robot's camera sees part of a room; objects are occluded, behind the agent, or miles away. Important aspects of the world are simply not in the observation, and treating a value function as a table over true states is a strong and unrealistic assumption.⁵

Parametric function approximation already softens this. If a state variable is not observable, the parameterization can be chosen not to depend on it, and the value behaves as if that variable were absent — so the approximate-value results carry over to partial observability unchanged. But some issues need partial observability made explicit. Sutton and Barto lay out four steps.

First, change the problem. The environment emits not states but observations$O_t\in \mathcal{O}$ — signals that depend on the underlying state but reveal it only in part. The interaction becomes an alternating stream of actions and observations, $A_0,O_1,A_1,O_2,A_2,O_3,\dots$, with no state anywhere in the data.

Second, recover state as a construction. Define the history $H_t\doteq A_0,O_1,\dots ,A_{t-1},O_t$: everything knowable from the data stream so far. The history is the most any agent could know, but it grows without bound. State is a compact summary of history that is as good as the full history for predicting the future. That as good as is precise. A summarizing function $S_t=f(H_t)$ has the Markov property when any two histories it maps to the same state yield the same distribution over the next observation:

When $f$ has this property, $S_t=f(H_t)$ is a Markov state — and the crucial point is that the Markov state is built by choosing $f$, not read off the world. A Markov state summarizes not only the next observation but every future test (any sequence of actions and resulting observations), and hence every GVF; it is enough to predict and control anything.⁵

Third, make it compact and incremental. The identity function $S_t=H_t$ is Markov but useless: it grows forever and never recurs, so no state is ever seen twice. Instead the agent maintains a state-update function that folds each new observation into the previous state,

with $S_0$ given. Learning a good $u$ — one that is compact, recurrent, and near-Markov — is the representation-learning problem, restated for partial observability. Two classical constructions illustrate this. A POMDP posits a hidden latent state and takes $S_t$ to be the belief state, the posterior distribution over latent states given the history, updated by Bayes' rule; it is principled but scales poorly. A predictive state representation instead defines the state as the probabilities of a set of future tests, grounding its meaning in observable data rather than an unobservable latent, which can make it easier to learn.⁵

A belief update, worked. The belief state is a probability vector over hidden states, and Bayes' rule folds each observation into it. Take a two-state tiger problem: the reward is behind the left door or the right, and the agent starts believing $b=(0.5,0.5)$. A listen action returns a noisy observation: it hears the correct side with probability $0.85$ and the wrong side with $0.15$. Suppose it hears left. The Bayes update multiplies each prior by that state's likelihood of producing the observation and renormalizes:

One noisy observation moved the belief from $(0.5,0.5)$ to $(0.85,0.15)$. Listen again and hear left a second time: the new prior is $(0.85,0.15)$, so

The belief sharpens toward certainty with each confirming observation, and this belief vector — not the raw observation — is the Markov state a POMDP planner acts on. The state-update function $u$ here is precisely the Bayes filter; a predictive state representation would instead track the probabilities of future listen outcomes and reach an equivalent summary without ever naming the hidden door.

Fourth, re-introduce approximation. In practice $u$ produces an approximate state that may not be Markov — the simplest being the last observation $S_t=O_t$, or the last $k$ observations and actions. When the Markov property holds only approximately, long-horizon predictions can degrade sharply, and there are no strong theoretical guarantees at present. What remains is a heuristic that echoes the auxiliary-task argument: a representation that is good for some predictions tends to be good for others. So partial observability and representation learning fold into one problem — learn a state-update function by pursuing many predictions and keeping the features that serve them.⁵ This lesson loosened the state and the action. The third assumption — the reward, its design, and the reward-hacking hazard — together with the open problems the whole subject still faces and how the frontiers were pushed after Sutton & Barto, continues in Reward Design and Open Problems.