Chapter 3 — Finite Markov Decision Processes, explained.

Asha re-enables the robot's wheels. Her bandit chose a route heuristic at one loading bay and immediately scored it; now each turn changes the robot's location, battery, congestion exposure, and future options. A quick move can lead into a long queue. Waiting can preserve a safe path. The same action can be wise with a full battery and disastrous with 4% remaining. Her one-step bandit has become a sequence. To reason precisely, she needs the language of finite Markov decision processes.

01 From a bandit to a sequential decision process

A bandit evaluates A_t by its immediate R_t. An MDP adds S_t and a transition: the selected action helps determine the next state. This creates delayed consequences because tomorrow's available actions depend on today's choice.

The interaction is a trajectory S₀,A₀,R₁,S₁,A₁,R₂,…. For finite MDPs the state and action sets are finite, and environment dynamics are captured by:

This one distribution contains both state-transition and reward dynamics. Summing over rewards gives p(s′|s,a); summing weighted rewards gives expected immediate reward r(s,a). The framework can represent stochastic traffic, uncertain battery consumption, or deterministic board games with the same notation.

02 The agent–environment boundary and the Markov state

The boundary is conceptual. The agent is everything that learns and chooses; the environment is everything it cannot directly choose. A robot's motors may be considered part of the environment if the agent outputs desired torque, while the control algorithm is inside the agent. Rewards belong to the environment interface even if a designer wrote the code that calculates them.

The Markov property says the conditional distribution of the next reward and state depends on the current state and action, not on earlier history once the current state is known. It does not say the world has no memory. It says the state representation already summarizes the relevant memory.

Asha's camera image may show the robot at the dock but not whether its battery is failing. Then identical observations can produce different next outcomes. The observation is not Markov. Adding battery health—or giving the agent memory to infer it—can repair the representation.

03 Goals, rewards, and why “maximize reward” is subtle

The reward hypothesis states that goals can be represented as maximizing expected cumulative scalar reward. Reward should describe what outcome is desired, not prescribe how to achieve it. Giving +1 for moving toward the target may hard-code a route heuristic and create loops; rewarding successful delivery, time, energy, and violations leaves behavior to learning.

Rewards must be based on information available to the environment, and their scale changes optimization behavior. A collision penalty of −10 cannot dominate a +20 delivery if a risky shortcut succeeds often enough; a hard safety constraint may be more appropriate than a finite penalty.

Asha writes +20 for delivery, −1 per minute, −3 for entering a congested zone, and a separate non-negotiable collision constraint. She then red-teams the signal: can the robot collect reward without completing the intended job? This audit is part of MDP design.

04 Returns: episodic and continuing tasks

For an episodic task, interaction naturally breaks into episodes with terminal state S_T. The undiscounted return is the sum until termination:

For continuing interaction without terminal states, an infinite undiscounted sum may diverge. Discounted return uses γ∈[0,1):

The recursive identity G_t=R_t+1+γG_t+1 is the seed of Bellman equations. Discounting weights near rewards more strongly and makes bounded continuing returns finite. It can also model a constant probability of termination, but γ should not be treated as a casual “patience knob” without considering the actual task objective.

The book unifies notation by introducing an absorbing terminal state and allowing γ to be one for finite episodes. Asha models each delivery as an episode, while fleet operation is continuing. The framing determines what “long term” means and which objective the learned policy actually optimizes.

05 Policies and value functions

A stochastic policy π(a|s) is the probability of choosing action a in state s. The state-value function under π is:

The action-value function conditions on the first action too:

Both values are policy-dependent. The same congested aisle can be valuable under a policy that knows how to exit quickly and poor under one that loops. Values are expectations over policy randomness and environment randomness, not guaranteed outcomes.

V answers whether a situation is promising when behavior is fixed. Q compares available decisions directly. If the model p is known, Q can be computed from V by one-step lookahead; without a model, learning Q is often convenient for control.

06 Bellman expectation equations from first principles

Start with v_π(s)=E[G_t|S_t=s]. Substitute the recursive return R_t+1+γG_t+1. Then average over the action chosen by π and the next outcome generated by p:

This is not an update rule yet. It is a consistency condition: the value assigned to each state must agree with immediate reward plus the values assigned to successor states. A backup diagram represents the same idea graphically—branch over actions under the policy, then outcomes under the environment.

Suppose at the dock π chooses shortcut and safe aisle equally. Shortcut gives expected immediate −1 and next value 12; safe gives −2 and next value 15; γ=.9. Then v(dock)=.5(−1+.9×12)+.5(−2+.9×15)=10.65. Every number has a role: policy probabilities weight actions, dynamics weight outcomes, reward accounts for the step, and γ carries future value back.

07 Optimal policies and Bellman optimality

A policy π is at least as good as π′ if v_π(s)≥v_π′(s) for every state. Finite MDPs have at least one optimal policy π_*. All optimal policies share the same optimal state-value function v_* and action-value function q_*.

If q_* is known, an optimal policy is easy: choose any maximizing action in each state. The hard work is computing or learning q_*. These nonlinear max equations are the target of dynamic programming, Q-learning, and many later methods.

There can be multiple optimal policies when actions tie. An optimal policy need not be stochastic in a finite fully observed MDP, though stochastic policies remain useful for exploration and may be required under constraints or partial observability.

08 Approximation, horizons, and the engineering reality

Exact optimality assumes correct dynamics, a Markov state, stationary rewards, and manageable finite spaces. Asha's real warehouse has continuous positions, people, changing maps, and imperfect sensors. Even listing every state is impossible.

RL therefore spends most computation near states actually encountered and uses approximate value functions to generalize. The book emphasizes that agents often have more computation than one decision but far less than exhaustive search. Useful algorithms prioritize relevant experience and tolerate approximation rather than solving every hypothetical state exactly.

The discount factor defines an effective horizon: rewards roughly 1/(1−γ) steps away still matter appreciably. With γ=.9 that scale is about 10 steps; with .99 it is about 100. Larger γ spreads credit farther but can raise variance and slow propagation. Objective choice and algorithmic difficulty are coupled.

09 Questions master's students should answer

10 Key takeaways

• An MDP adds state transitions: actions affect both immediate reward and future decision opportunities.
• p(s′,r|s,a) is the finite MDP's complete one-step environment model.
• A state is Markov when it summarizes all history relevant to predicting the next outcome.
• Return turns many future rewards into one objective; episodes terminate naturally, while continuing tasks often use discounting.
• v_π evaluates states and q_π evaluates state–action pairs under a policy.
• Bellman expectation equations express policy-value self-consistency; Bellman optimality replaces policy averaging with maximization.
• Exact solutions are conceptually clean but state explosion, partial observability, and model error force approximation in real systems.

11 Wrapping up and source trail

Asha can now state her research problem instead of merely describing a robot. She has a Markov state hypothesis, action set, transition-and-reward model, return objective, policy, and value questions. Bellman's equations reveal the reusable structure: the future can be summarized recursively one step at a time. Chapter 4, dynamic programming, asks what happens when the model is known and those equations are turned into algorithms.

These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.