Sequential Decision Problems

"For five parts of this book I sat very still and forecasted. I read the tape, I extrapolated the curve, I quoted my confidence interval, and the world rolled on without the faintest interest in what I thought. Then someone handed me a lever. The instant I pulled it I understood the terrible new rule of my existence: the data I will see tomorrow is now partly my fault."

An Agent Realizing Its Choices Today Shape the Data It Sees Tomorrow

From Chapter 1 onward this book has organized temporal intelligence around three verbs: predict the future, reason about why it unfolds as it does, and decide what to do about it. Parts II through V lived almost entirely inside the first verb. We built models that forecast a return series, that filter a noisy state, that flag an anomaly, that quantify uncertainty; in every case the world was a given, an external process we observed and modeled but never touched. The decision, when there was one, was a thin afterthought layered on top of the forecast: predict tomorrow's demand, then someone, somewhere, decides how much to order. This chapter is where the afterthought becomes the subject. We now study agents that choose actions, where the choice itself reshapes the future the agent will then have to predict and reason about. This is the pivot of the whole book, the hinge on which "From Forecasting to Sequential Decision Making" in the title turns.

The reframing is not cosmetic, and it is worth being precise about why. In a forecasting problem the data-generating process is fixed: the equity index would have printed the same prices, the patient's vitals would have followed the same trajectory, the turbine would have vibrated the same way, whether or not a model was watching. The model is a passive reader of a stream it cannot perturb. In a sequential decision problem the agent is inside the data-generating process. When an inventory agent orders stock it changes next week's on-hand level and therefore next week's state; when a clinician's policy starts a drug it changes the patient's future vitals and therefore the future observations; when a controller opens a valve it changes the downstream pressure the next sensor reading will report. The action is an input to the dynamics, so the distribution of future data is a function of the policy. That single dependency, future data depends on present action, is the source of every new idea in Part VI and the reason the tools of supervised learning do not transfer unchanged.

Concretely, this section installs four competencies. First, to name the four ingredients of any sequential decision problem, states, actions, rewards, and dynamics, and to recognize them in a messy real situation. Second, to write down the agent-environment loop and the cumulative discounted return it maximizes, in the notation that the rest of Part VI uses without further comment. Third, to tell a one-shot decision apart from a sequential one, and to articulate why the sequential case introduces credit assignment over time. Fourth, to instrument a sequential decision problem in code, both from scratch and through the standard Gymnasium interface, so that every algorithm in Chapters 23 through 29 has an environment to act in. These are the load-bearing concepts for all of sequential decision making.

1. From Predicting the Future to Acting to Shape It Beginner

A forecasting problem and a decision problem can look deceptively similar on the surface: both involve time, both involve uncertainty, both involve a model that maps the past to something about the future. The difference is in what the model is allowed to do. A forecaster outputs a prediction, a statement about what will happen, and is scored on how close that statement lands to the truth. An agent outputs an action, an intervention on the world, and is scored on the consequences that action sets in motion. The forecaster's output is compared to reality; the agent's output changes reality. That is the whole distinction, and it is enormous.

To make the four ingredients precise, a sequential decision problem is specified by a state, an action set, a reward, and dynamics. The state $s_t$ is a summary of the situation at time $t$ that is sufficient to decide what to do next: the inventory on hand, the patient's current vitals, the pressures and temperatures of the plant. The action $a_t$ is the choice the agent makes from a set $\mathcal{A}$ of available actions: how many units to order, which drug and dose to administer, how far to open a valve. The reward $r_t$ is a scalar that scores the step, the immediate payoff or cost the agent receives: profit minus holding cost, a clinical outcome, throughput minus energy spent. The dynamics describe how the world responds, the rule (typically stochastic) that produces the next state $s_{t+1}$ and reward $r_t$ given the current state $s_t$ and action $a_t$. We write the dynamics as a conditional distribution $p(s_{t+1}, r_t \mid s_t, a_t)$, and the agent's behavior as a policy $\pi(a_t \mid s_t)$, a (possibly stochastic) rule mapping states to actions. These five symbols, $s, a, r, p, \pi$, recur on every page of Part VI and are catalogued in the unified notation of Appendix A.

The defining property, the one that separates this entire part of the book from everything before it, is that the dynamics depend on the action. Because $s_{t+1}$ is drawn from $p(\cdot \mid s_t, a_t)$, a different action leads to a different next state, which leads to a different set of available future actions, which leads to a different stream of rewards and observations. The agent does not merely predict the trajectory; it selects among trajectories. A passive forecaster confronts one fixed future and tries to describe it; an agent confronts a branching tree of possible futures and tries to steer into a good branch. The branch it steers into is the only data it then gets to observe, which is why an agent's choices today shape the data it sees tomorrow, the realization the epigraph's persona arrives at the instant it is handed a lever.

2. The Agent-Environment Loop and the Return Beginner

The mechanics of sequential decision making are captured by a single loop, repeated at every time step. The agent observes the current state $s_t$; it acts, choosing $a_t$ according to its policy $\pi(a_t \mid s_t)$; the environment responds, emitting a reward $r_t$ and a next state $s_{t+1}$ drawn from the dynamics $p(s_{t+1}, r_t \mid s_t, a_t)$; and the loop repeats from $s_{t+1}$. That is the entire interface between an agent and its world, and Figure 22.1.2 draws it. Notice how it differs from a forecasting pipeline: there is no fixed dataset arriving from outside, the agent's own actions are inside the cycle that produces the next observation.

Running this loop produces a trajectory, the sequence of states, actions, and rewards the interaction generates:

An episode runs until a terminal state or a time horizon; the trajectory is the complete record of one such run. The agent does not care about any single reward in isolation; it cares about the total reward accumulated over the trajectory, with later rewards discounted relative to earlier ones. This total is the cumulative discounted return from time $t$,

where $\gamma \in [0, 1)$ is the discount factor. The return obeys the recursive identity $G_t = R_{t+1} + \gamma\, G_{t+1}$, which peels off the immediate reward and discounts the rest; this one-line recursion is the seed of every value-based method in Chapter 24 and the Bellman equations that organize all of dynamic programming for MDPs. The agent's objective is to choose a policy $\pi$ that maximizes the expected return, $\mathbb{E}_\pi[G_0]$, where the expectation is over the randomness in both the policy and the dynamics.

The discount factor $\gamma$ earns its place for three reasons that are worth separating. Mathematically, with rewards bounded and $\gamma < 1$ the infinite sum converges, so the return is a finite, well-defined number even on an endless trajectory. Behaviorally, $\gamma$ encodes how much the agent values the future relative to the present: $\gamma$ near $0$ makes a myopic agent that grabs immediate reward and ignores the long game, while $\gamma$ near $1$ makes a far-sighted agent that will sacrifice now for a larger payoff later. Statistically, a smaller $\gamma$ shortens the effective horizon $1/(1-\gamma)$ over which credit is assigned, which can stabilize learning at the cost of foresight. Choosing $\gamma$ is therefore a modeling decision with real consequences, not a numerical convenience, a theme we return to when value estimates become noisy in Chapter 25.

The notation here is the standard reinforcement-learning convention, and it is deliberately the same shape as the recurrences that ran through Part III. The trajectory $\tau$ is a sequence indexed by time, exactly like the input sequences fed to the recurrent networks of Chapter 10; the difference is that here the agent generates part of the sequence itself, through its actions. This structural kinship is not a coincidence: it is what makes it possible, in Chapter 28, to treat the whole decision problem as a sequence-modeling problem and hand a trajectory to a Transformer. For now the point is simply that the agent-environment loop emits a temporal sequence, and the return is a discounted sum along it.

3. Sequential Decisions Across the Running Domains Intermediate

The four ingredients become concrete the moment they are mapped onto a real situation. The three running datasets of this book each host a natural sequential decision problem, and laying them side by side shows how general the framework is. Consider first inventory and ordering, the finance-and-retail setting. The state is the current stock on hand (and perhaps recent demand and price); the actions are the order quantities the manager may place; the reward is revenue from sales minus holding, ordering, and stockout costs; the dynamics are the stochastic demand that depletes stock plus the replenishment that an order brings. An order placed today raises next week's inventory, changes the probability of a stockout, and shifts the state the manager will face next, a clean instance of an action perturbing the future.

Second, treatment decisions, the healthcare setting threaded from Chapter 7. The state is the patient's current vitals and history; the actions are the clinical interventions available, which drug, which dose, whether to escalate care; the reward encodes the clinical objective, perhaps a negative cost for adverse events and a positive payoff for recovery; the dynamics are the patient's physiological response, how vitals evolve under treatment. A drug administered now alters the patient's trajectory, and therefore the future vitals the clinician observes and the future decisions that become available. The credit-assignment problem is acute here: a treatment's true effect may surface only days later.

Third, control of an industrial process, the sensor-and-IoT setting from Chapter 8. The state is the vector of plant measurements (pressures, temperatures, flow rates); the actions are the control settings the operator can adjust, valve positions, setpoints, pump speeds; the reward is throughput or product quality minus energy cost and constraint violations; the dynamics are the physics of the plant, how the measurements respond to the settings. Opening a valve now changes the downstream pressure the next sensor reading reports, the textbook closed-loop control problem that Chapter 27 studies in depth.

Contrast the one-shot and sequential versions of the same domain to feel the difference. A one-shot pricing decision sets a single price and observes a single sale: the loss is immediate and local. A sequential pricing decision sets prices over a season, where today's price changes inventory, demand learning, and competitor response, so that a price cut now might earn a small immediate loss but build market position that pays off over weeks. The one-shot version is a forecast-and-optimize problem solvable with the tools of earlier parts; the sequential version requires reasoning about how present actions reshape future states, and that is the territory of the MDP. The rest of this chapter formalizes the sequential case; the Markov property of Section 22.2 is the assumption that makes it tractable.

4. Exploration, Exploitation, and Delayed Reward Intermediate

Two challenges distinguish sequential decision making from the supervised learning of the earlier parts, and both follow directly from the fact that the agent generates its own data. The first is the exploration-exploitation dilemma. To act well the agent must exploit what it currently believes is the best action; to learn whether something better exists it must explore actions whose value is still uncertain. These pull in opposite directions. An agent that only exploits is trapped in whatever looked best early, never discovering a superior action it never tried; an agent that only explores throws away reward forever, never cashing in what it has learned. A supervised learner faces nothing like this, because its training labels are handed to it regardless of what it predicts. An agent's "labels", the rewards and states it observes, exist only for the actions it actually takes, so the agent must spend some of its actions buying information rather than reward.

The second challenge is delayed reward, the temporal credit-assignment problem named in subsection three, now seen as a learning obstacle. In supervised learning the loss for a prediction is available immediately and attaches cleanly to that prediction. In a sequential problem the reward that an action ultimately earns may not arrive until many steps later, and when it arrives it is the joint result of a whole sequence of actions, not any single one. The agent must somehow propagate that delayed signal back to the decisions responsible for it. This is the same backward-propagation-of-credit structure we met as backpropagation through time in Section 9.3, where a loss at the final step had to be assigned back across all earlier steps; here the "loss" is a delayed reward and the chain runs through the agent's own actions and the environment's dynamics. The recursive return and, later, value functions are the apparatus that performs this temporal credit assignment.

These two challenges interact, and the interaction is what makes the field hard. Exploration is costly precisely because reward is delayed: an exploratory action might look bad immediately yet set up a large payoff later, so the agent cannot evaluate an exploration by its instant reward alone, it must estimate the exploration's long-run return, which is itself uncertain because the agent has not explored enough. Delayed reward makes exploration hard to judge, and the need to explore makes delayed-reward estimates noisy. Untangling this knot is the project of the next several chapters: bandits in Chapter 24 isolate the exploration-exploitation dilemma in the simplest setting with no state at all, and full reinforcement learning then layers the temporal credit-assignment problem back on top. For this section it is enough to recognize the two challenges and see why neither appears in passive forecasting.

5. Worked Example: A Tiny Environment, From Scratch and in Gymnasium Advanced

We now make the agent-environment loop executable. The plan mirrors the from-scratch-then-library pattern used throughout the book: first build a minimal gridworld environment and its interaction loop entirely in plain Python, run a random policy, and measure the return; then wrap the exact same dynamics as a standard Gymnasium Env and run the identical loop through the field's universal interface, so that every algorithm of Chapters 23 to 29 can drive it unchanged. Code 22.1.1 is the from-scratch environment: a $4\times 4$ grid where the agent starts at the top-left, must reach the bottom-right goal, pays a small cost per step, and earns a payoff at the goal.

import numpy as np

class GridWorld:
    """A 4x4 gridworld coded from scratch: states, actions, reward, dynamics."""
    def __init__(self, n=4, gamma=0.9, step_cost=-0.04, goal_reward=1.0):
        self.n, self.gamma = n, gamma
        self.step_cost, self.goal_reward = step_cost, goal_reward
        self.goal = (n - 1, n - 1)            # bottom-right cell is the goal
        self.actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right

    def reset(self):
        self.pos = (0, 0)                     # start top-left; state s_0
        return self.pos

    def step(self, a):
        """Dynamics p(s', r | s, a): move, clip to the grid, score the step."""
        dr, dc = self.actions[a]
        r, c = self.pos
        nr = min(max(r + dr, 0), self.n - 1)  # walls: clip the move at the edge
        nc = min(max(c + dc, 0), self.n - 1)
        self.pos = (nr, nc)
        done = (self.pos == self.goal)        # terminal when the goal is reached
        reward = self.goal_reward if done else self.step_cost
        return self.pos, reward, done

def run_episode(env, policy, max_steps=100):
    """The agent-environment loop: observe, act, receive reward, transition."""
    s = env.reset()
    rewards, gamma = [], env.gamma
    for t in range(max_steps):
        a = policy(s)                         # agent acts from the policy
        s, r, done = env.step(a)              # environment responds
        rewards.append(r)
        if done:
            break
    G0 = sum(gamma ** k * r for k, r in enumerate(rewards))  # discounted return
    return G0, len(rewards)

rng = np.random.default_rng(0)
env = GridWorld()
random_policy = lambda s: rng.integers(0, 4)   # uniform random over the 4 actions
returns = [run_episode(env, random_policy)[0] for _ in range(2000)]
print("from-scratch random policy: mean return = %.3f over 2000 episodes" % np.mean(returns))

from-scratch random policy: mean return = -0.299 over 2000 episodes

The random policy's mean return of about $-0.30$ is the baseline a learner must beat: an aimless agent pays the step cost repeatedly while blundering toward the goal. Now the library equivalent. Code 22.1.2 wraps the identical dynamics as a Gymnasium Env, the de facto standard interface that every reinforcement-learning library in Appendix D consumes. The dynamics are the same; what changes is that the environment now speaks the standard reset and step protocol, so any off-the-shelf agent can drive it.

import gymnasium as gym
from gymnasium import spaces
import numpy as np

class GridWorldEnv(gym.Env):
    """The SAME gridworld dynamics, now as a standard Gymnasium Env."""
    metadata = {"render_modes": []}                            # targets the Gymnasium 1.x API
    def __init__(self, n=4):
        self.n = n
        self.goal = (n - 1, n - 1)
        self.moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.action_space = spaces.Discrete(4)                 # 4 moves
        self.observation_space = spaces.Discrete(n * n)        # flattened cell index

    def _obs(self):
        return self.pos[0] * self.n + self.pos[1]              # (r, c) -> integer state

    def reset(self, seed=None, options=None):
        super().reset(seed=seed)
        self.pos = (0, 0)
        return self._obs(), {}                                  # (observation, info)

    def step(self, a):
        dr, dc = self.moves[a]
        r, c = self.pos
        self.pos = (min(max(r + dr, 0), self.n - 1),
                    min(max(c + dc, 0), self.n - 1))
        done = (self.pos == self.goal)
        reward = 1.0 if done else -0.04
        return self._obs(), reward, done, False, {}            # obs, reward, terminated, truncated, info

env = GridWorldEnv()
rng = np.random.default_rng(0)
returns, gamma = [], 0.9
for _ in range(2000):
    obs, _ = env.reset()
    rewards = []
    for t in range(100):
        obs, r, terminated, truncated, _ = env.step(env.action_space.sample())  # random policy
        rewards.append(r)
        if terminated or truncated:
            break
    returns.append(sum(gamma ** k * rw for k, rw in enumerate(rewards)))
print("gymnasium random policy:    mean return = %.3f over 2000 episodes" % np.mean(returns))

gymnasium random policy:    mean return = -0.299 over 2000 episodes

The two implementations agree to three decimals because they are the same environment wearing different clothes. The from-scratch version in Code 22.1.1 spelled out the loop, the state encoding, and the return by hand in roughly 35 lines of bespoke code, with an ad-hoc reset/step convention that no other tool understands. The Gymnasium version exposes the identical dynamics through about 20 lines of standard interface, and in exchange every reinforcement-learning algorithm in the ecosystem, from a textbook Q-learner to a deep policy-gradient agent, can train on it without a single line of adapter code. The line-count reduction is modest here because the environment is tiny; the real saving is conceptual and ecosystem-wide: adopting the standard spaces, reset, and five-tuple step contract is what lets the rest of Part VI plug any agent into any environment.

import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=False)   # a built-in 4x4 gridworld, one line
obs, info = env.reset(seed=0)
for _ in range(100):
    obs, reward, terminated, truncated, info = env.step(env.action_space.sample())  # random policy
    if terminated or truncated:
        break