Markov Decision Processes and Dynamic Programming

5.1 MDP Review and Agent-Environment Interface

5.1.1 Definition and Explanation

A Markov Decision Process (MDP) is the mathematical framework for formulating reinforcement learning problems. It gives RL algorithms a formal structure to work within.

An MDP is defined by the tuple $(S,A,p,r,\gamma )$, where:

• $S$ — the state set — all possible situations the agent can face
• $A$ — the action set — all choices available to the agent (we sometimes write $A(s)$ when the available actions depend on the state)
• $p(s^{\prime },r|s,a)$ — the dynamics function — the probability of landing in state $s^{\prime }$ with reward $r$ given you were in state $s$ and took action $a$. This function fully defines how the environment behaves.
• $r$ — the reward — a scalar signal the agent receives after each action
• $\gamma$ — the discount factor — a number in $[0,1)$ that controls how much the agent values future rewards

The agent-environment boundary is a key concept. Everything the agent can control (its choices) sits on one side. Everything it cannot change sits on the other side — that is the environment. This includes the rules of the world, the reward function, and even the agent's own sensors and actuators (the agent cannot arbitrarily change its camera; it can only choose actions). The textbook puts it well: "anything that cannot be changed arbitrarily by the agent is considered to be outside of it."

At each time step $t$, the agent and environment produce a trajectory:

$$S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3,\dots$$

The agent sees state $S_t$, picks action $A_t$, and the environment returns reward $R_{t+1}$ and next state $S_{t+1}$. This loop repeats.

The dynamics function satisfies:

$$\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)=1\text{for all }s\in S,a\in A(s)$$

From $p$, we can derive:

• State transition probabilities: $p(s^{\prime }|s,a)={\sum }_{r}p(s^{\prime },r|s,a)$
• Expected reward for state-action pairs: $r(s,a)={\sum }_{r}r{\sum }_{s^{\prime }}p(s^{\prime },r|s,a)$

5.1.2 Symbol Registry

• $S$ — state set — finite set of all possible states
• $A$ or $A(s)$ — action set — finite set of available actions (may depend on state)
• $p(s^{\prime },r|s,a)$ — dynamics function — probability of next state $s^{\prime }$ and reward $r$ given state $s$ and action $a$
• $R_t$ — reward at time $t$ — scalar
• $\gamma$ — discount factor — scalar in $[0,1)$
• $S_t$ — state at time $t$ — element of $S$
• $A_t$ — action at time $t$ — element of $A$

The Markov property means the future depends only on the current state, not on how you got there. Formally:

$$P(S_{t+1}|S_t,A_t,S_{t-1},A_{t-1},\dots )=P(S_{t+1}|S_t,A_t)$$

If the state captures all relevant history, the Markov property holds. This is a restriction on what counts as a state, not on the problem itself.

5.1.3 Worked Examples

The agent-environment interface diagram works like this: the agent picks action $A_t$, the environment responds with reward $R_{t+1}$ and next state $S_{t+1}$. This loop repeats at every time step.

An MDP is not just a toy model. Traffic engineers use it to optimize signal timing. Game AI researchers use it to train agents that play Atari games at superhuman level. Robotics teams use it to plan actions for warehouse robots. The framework is abstract enough to cover all of these, yet concrete enough to be computationally useful. It sits at the core of every RL algorithm — model-free methods just learn the dynamics instead of being given them.

5.2 Reward Hypothesis

5.2.1 Definition and Explanation

The reward hypothesis states that all goals of an RL agent can be framed as the maximization of the expected value of the cumulative sum of a received scalar signal.

Formally, the agent's objective is to maximize the expected return:

$$G_t=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

where:

• $R_{t+k+1}$ — the reward received $k+1$ steps after time $t$ — scalar
• $\gamma$ — the discount factor — a scalar in $[0,1)$ that controls how much future rewards matter relative to immediate ones
• $G_t$ — the return from time $t$ — the total discounted reward the agent receives from that point onward

The agent chooses actions to maximize $\mathbb{E}[G_t]$, the expected return.

5.2.2 Symbol Registry

• $R_t$ — reward signal at time $t$ — scalar
• $\gamma$ — discount factor — scalar in $[0,1)$
• $G_t$ — return (cumulative discounted reward from time $t$) — scalar

5.2.3 Key Concepts

Simple (undiscounted) sum: ${\sum }_{t=0}^{\infty }{R}_t$ — adds every reward equally. This diverges to infinity if rewards are positive and the task never ends. Only works for tasks that end in finite time.

Discounted sum: ${\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$ — weights future rewards less. If $\gamma =0$, the agent only cares about the immediate reward. If $\gamma$ is close to 1, the agent cares about rewards far into the future.

The discount factor $\gamma$ has two roles:

1. Mathematical: It keeps the infinite sum finite. If rewards are bounded and $\gamma <1$, the sum always converges.
2. Behavioral: It encodes how much the agent values the future vs the present. A high $\gamma$ makes the agent "far-sighted"; a low $\gamma$ makes it "myopic."

The return at successive time steps satisfies a useful recursive relation:

$$G_t=R_{t+1}+\gamma G_{t+1}$$

This means: today's return equals today's reward plus discounted tomorrow's return. You will use this relation constantly in RL derivations.

This idea — compressing all goals into a single scalar signal — powers every RL system from game-playing AIs to robotic control. It is the reason RL can solve problems we do not know how to specify with explicit rules.

5.3 Episodic vs Continuing Tasks

5.3.1 Definition and Explanation

An episodic task has natural terminal states. The agent's experience breaks into episodes, each ending at a terminal state, followed by a reset. The return is a finite sum:

$$G_t=R_{t+1}+R_{t+2}+\cdots +R_T$$

where $T$ is the final time step of the episode.

A continuing task has no natural endpoint. The agent interacts indefinitely. Here, the undiscounted return would diverge, so we must use discounting:

$$G_t=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

with $\gamma <1$ to keep the sum finite.

5.3.2 Symbol Registry

• $G_t$ — return from time $t$ — scalar (cumulative discounted reward)
• $T$ — terminal time step of an episode — positive integer
• $\gamma$ — discount factor — scalar in $[0,1)$
• $R_t$ — reward at time $t$ — scalar

5.3.3 Worked Example: Cart-Pole Balancing

The choice between episodic and continuing formulation affects everything downstream: the return, the value functions, and the algorithms. The textbook notes that the pole-balancing task can be modeled either way, and both are valid. The continuing formulation is slightly more general.

5.4 Policy

5.4.1 Definition and Explanation

A policy $\pi$ defines the agent's behavior. It maps states to actions.

5.4.2 Symbol Registry

• $\pi$ — policy — function mapping states to actions (or action probabilities)
• $\pi (s)$ — deterministic policy — the single action chosen in state $s$
• $\pi (a|s)$ — stochastic policy — probability of taking action $a$ in state $s$, with ${\sum }_a\pi (a|s)=1$
• $s$ — state — element of state set $S$
• $a$ — action — element of action set $A$

5.4.3 Example

The policy is the central object in RL. Every algorithm — value-based, policy-based, or actor-critic — ultimately produces or improves a policy. Value-based methods compute values first and extract a policy from them. Policy-based methods optimize the policy directly. Both are different paths to the same goal: finding a good $\pi$.

5.5 State Value Function (Vπ)

5.5.1 Definition and Explanation

The state value function $V_{\pi }(s)$ quantifies how good it is to be in state $s$ when following policy $\pi$. It is the expected return starting from $s$ and following $\pi$ thereafter.

5.5.2 Mathematical Formulation

The verbal description: "The value of state $s$ under policy $\pi$ is the expected cumulative discounted reward if you start in $s$ and follow $\pi$ from then on."

Expanding the return $G_t$:

$$V_{\pi }(s)={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s\right]$$

This sums over all possible future trajectories, each weighted by its probability under $\pi$ and the environment dynamics $p$.

5.5.3 Symbol Registry

• $V_{\pi }(s)$ — state value function under policy $\pi$ — scalar
• $G_t$ — return from time $t$ (cumulative discounted reward) — scalar
• $\gamma$ — discount factor — scalar in $[0,1)$
• $\pi$ — policy — function mapping states to action probabilities

5.5.4 Example with Numerical Values

State values are the first building block for RL algorithms. Policy evaluation (covered later) computes $V_{\pi }$ for a given policy. Policy improvement uses $V_{\pi }$ to find a better policy. This cycle — evaluate, improve, repeat — drives all dynamic programming methods.

5.6 Action Value Function (Qπ)

5.6.1 Definition and Explanation

The action value function $Q_{\pi }(s,a)$ quantifies how good it is to take action $a$ in state $s$ and then follow policy $\pi$ thereafter.

5.6.3 Mathematical Formulation

$$Q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a]$$

This conditions on a specific action $a$ being taken at time $t$, then follows $\pi$ for all later steps.

5.6.4 Why Q is Preferred Over V

The Q-function is central to many RL algorithms. Q-learning (Chapter 6 in the textbook) learns $Q^{\ast }$ directly from experience without knowing the transition probabilities. Deep Q-Networks (DQN) approximate $Q^{\ast }$ with neural networks to play Atari games. The concept extends from this simple definition to state-of-the-art methods.

5.7 Bellman Expectation Equation

5.7.1 Definition and Explanation

The Bellman expectation equation defines $V_{\pi }(s)$ recursively:

5.7.2 Mathematical Formulation

The full Bellman equation for $V_{\pi }$:

$$V_{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V_{\pi }(s^{\prime })\right]$$

This is a system of $|S|$ linear equations in $|S|$ unknowns (one equation per state). For a finite MDP, this system has a unique solution as long as $\gamma <1$ or eventual termination is guaranteed.

The textbook derives this from the return's recursive structure:

$$V_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}\mid S_t=s]$$

Using $G_t=R_{t+1}+\gamma G_{t+1}$ (the recursive return relation), the expectation separates into the immediate reward and the discounted expected future value.

5.7.3 Symbol Registry

• $\pi (a|s)$ — probability of taking action $a$ in state $s$ under policy $\pi$ — scalar in $[0,1]$
• $p(s^{\prime },r|s,a)$ — dynamics function — probability of transitioning to state $s^{\prime }$ with reward $r$ given state $s$ and action $a$
• $s^{\prime }$ — next (successor) state — element of $S$
• $r$ — immediate reward — scalar

5.7.4 Understanding the Two Levels of Probability

The equation involves two distinct probability sources:

1. Policy probability $\pi (a|s)$: How likely the agent is to choose action $a$ in state $s$. This is under the agent's control — it defines the behavior.
2. Model dynamics $p(s^{\prime },r|s,a)$: How likely the environment is to transition to state $s^{\prime }$ with reward $r$. This is outside the agent's control — it defines the world.

If action outcomes are deterministic (action $a$ always leads to exactly one state $s^{\prime }$ with reward $r$), the inner sum collapses to a single term — the dynamics probability is 1 for that outcome, and 0 for all others.

5.7.5 Backup Diagram

The backup diagram shows the recursive structure visually:

• Open circles represent states (where you are)
• Solid circles represent action choices (decision points)
• From a state node, lines fan out to action nodes (one per possible action, weighted by $\pi (a|s)$)
• From each

  5.7.6 Worked Example: Expressing V in Terms of Q

  The state value can be written using Q-values:

  $$V_{\pi }(s)=\sum _a\pi (a|s)Q_{\pi }(s,a)$$

  Numerical example: Suppose policy $\pi$ gives:

  Action	$\pi (a\mid s)$	$Q_{\pi }(s,a)$
  up	0.7	10
  right	0.1	20
  down	0.1	15
  left	0.1	20

  $$V_{\pi }(s)=0.7\times 10+0.1\times 20+0.1\times 15+0.1\times 20=7+2+1.5+2=12.5$$

  Sense-check: The policy heavily favors "up" (Q = 10), so the state value is close to 10. The other actions have higher Q-values but are chosen rarely, so they pull the average up slightly to 12.5. This makes sense.

  5.7.7 Worked Example: Computing Q-Value

  From state $s$, take action "up". The Q-value depends on all possible outcomes:

  Deterministic case: "up" always leads to one state with reward 20 and that state has value 70. With $\gamma =0.9$:

  $$Q(s,\text{up})=20+0.9\times 70=20+63=83$$

  Stochastic case: "up" leads to four possible outcomes:

  Outcome	Probability	Reward	Next state value	Contribution
  Go up	$p_1$	20	70	$p_1\times (20+0.9\times 70)$
  Go down	$p_2$	10	100	$p_2\times (10+0.9\times 100)$
  Go right	$p_3$	30	80	$p_3\times (30+0.9\times 80)$
  Go left	$p_4$	20	100	$p_4\times (20+0.9\times 100)$

  $$Q(s,\text{up})=\sum _{i=1}^4{p}_i\left[r_i+\gamma V_{\pi }(s_i^{\prime })\right]$$

  where $p_1+p_2+p_3+p_4=1$.

  Assumptions & Scope:

  • Requires known dynamics. To compute $V_{\pi }$ from the Bellman equation, you need $p(s^{\prime },r|s,a)$. In model-free RL, you do not have this — so you sample transitions instead.
  • Requires a defined policy. The Bellman equation is for a given $\pi$. It evaluates that policy. Finding the best policy is a separate problem (Bellman optimality equation, Section 5.9).
  • Linear system. For $|S|$ states, you have $|S|$ equations in $|S|$ unknowns. For small state spaces, you can solve directly. For large spaces, you use iterative methods (policy evaluation, covered in DP chapter).

  Pitfalls:

  1. Confusing the Bellman expectation equation with the Bellman optimality equation. The expectation equation uses ${\sum }_a\pi (a|s)$ — a weighted average over actions. The optimality equation uses ${\max }_a$ — the best action. They look similar but solve different problems.
  2. Forgetting the two probability layers. The outer sum is over actions (policy probability). The inner sum is over outcomes (environment dynamics). Mixing them up leads to wrong formulas.
  3. Thinking V and Q are independent. They are tightly linked: $V_{\pi }(s)={\sum }_a\pi (a|s)Q_{\pi }(s,a)$ and $Q_{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V_{\pi }(s^{\prime })]$. You can express one in terms of the other.

  Recap + Bridge: The Bellman expectation equation connects the value of a state to the values of its successors through a one-step lookahead. It involves two probability layers: the policy and the dynamics. Solving this equation gives you $V_{\pi }$ for a given policy. Next, we verify this equation by hand on a grid world example.

  Q: We have two probabilities here — policy and model dynamics. What if each action leads to only one state?

  A: Then the model dynamics probability is 1 for that single outcome. The branch collapses to a single path. You just multiply: probability of taking that action (from policy) times (reward + gamma times next state value). No inner sum needed.

  Q: What does "expectation with respect to $\pi$" mean exactly?

  A: It means the average is computed using $\pi$'s probability distribution over actions. If $\pi (\text{up}|s)=0.7$, then 70% of the weight goes to the "up" outcome. It is like computing your expected commute time using your historical driving habits — the expectation depends on your behavior pattern.

5.8 Policy Evaluation & 1D Grid Example

5.8.1 Iterative Policy Evaluation Algorithm

Policy evaluation answers the prediction problem: if an agent follows policy $\pi$ indefinitely, what is the expected return from each state? Iterative policy evaluation starts with arbitrary initial values $V_0(s)$ (with $V(\text{terminal})=0$) and repeatedly applies the Bellman expectation backup:

$$V_{k+1}(s)=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma V_k(s^{\prime })\right]\forall s\in S$$

Input: policy pi to be evaluated
Parameter: small threshold theta > 0
Initialize V(s) arbitrarily for all s in S+, with V(terminal) = 0

Loop:
    Delta <- 0
    For each s in S:
        v <- V(s)                                    # store old value
        V(s) <- Sum_a pi(a|s) Sum_{s',r} p(s',r|s,a) [r + gamma * V(s')] # expectation backup
        Delta <- max(Delta, |v - V(s)|)              # track largest change
Until Delta < theta
Output: approximation V approx v_pi

5.8.2 Worked Example: One-Dimensional 5-Cell Grid Line

5.8.3 4x4 Grid World Setup & Converged State Values

Now consider a 4×4 grid world with two special teleport states:

• State A (row 1, col 2): Any action yields reward $R=+10$ and teleports to $A^{\prime }$ (row 3, col 1, value $-1.3$)
• State B (row 1, col 4): Any action yields reward $R=+5$ and teleports to $B^{\prime }$ (row 3, col 4)
• Normal moves: Reward 0, move one cell in chosen direction
• Off-grid moves: Moving off the grid keeps agent in place with reward $R=-1$
• Policy: Equiprobable random $\pi (a|s)=0.25$ for all 4 actions, $\gamma =0.9$

5.8.4 Worked Verification: Cell (3,3) and State A

5.9 Policy Improvement & Policy Improvement Theorem

5.9.1 Constructing a Greedy Policy

Given the value function $v_{\pi }$ for a policy $\pi$, the expected return for taking action $a$ in state $s$ and then following $\pi$ is:

$$q_{\pi }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma v_{\pi }(s^{\prime })\right]$$

A new greedy policy ${\pi }^{\prime }$ selects the action that achieves the maximum one-step lookahead return:

$${\pi }^{\prime }(s)=\arg \underset{a}{\max }{q}_{\pi }(s,a)=\arg \underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma v_{\pi }(s^{\prime })\right]$$

5.9.2 Policy Improvement Theorem

5.10 Policy Iteration Algorithm & Race-Car Demonstration

5.10.1 Policy Iteration Pseudocode

1. Initialization
   V(s) in R and pi(s) in A(s) arbitrarily for all s in S

2. Policy Evaluation
   Repeat:
       Delta <- 0
       For each s in S:
           v <- V(s)
           V(s) <- Sum_{s',r} p(s',r | s, pi(s)) [r + gamma * V(s')]
           Delta <- max(Delta, |v - V(s)|)
   Until Delta < theta (a small positive number)

3. Policy Improvement
   policy_stable <- true
   For each s in S:
       old_action <- pi(s)
       pi(s) <- argmax_a Sum_{s',r} p(s',r | s, a) [r + gamma * V(s')]
       If old_action != pi(s), then policy_stable <- false

   If policy_stable is true, then stop and return V approx v* and pi approx pi*
   Else go back to Step 2 (Policy Evaluation)

5.10.2 Race-Car Demonstration for Policy Iteration

5.11 Optimal Policies & Optimal Value Functions

5.11.1 Mathematical Formulation

$$V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma V^{\ast }(s^{\prime })\right]$$

$$Q^{\ast }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })\right]$$

5.12 Value Iteration Algorithm & Grid Demonstrations

5.12.1 Value Iteration Algorithm Pseudocode

Parameter: small threshold theta > 0
Initialize V(s) arbitrarily for all s in S+, with V(terminal) = 0

Loop:
    Delta <- 0
    For each s in S:
        v <- V(s)
        V(s) <- max_a Sum_{s',r} p(s',r | s, a) [r + gamma * V(s')] # optimality backup
        Delta <- max(Delta, |v - V(s)|)
Until Delta < theta

Output: deterministic policy pi approx pi* such that
pi(s) = argmax_a Sum_{s',r} p(s',r | s, a) [r + gamma * V(s')]

5.12.2 In-Place vs Not-In-Place Updates

5.12.3 Worked Example: 3x3 Grid Value Iteration Propagation

5.13 Asynchronous Dynamic Programming

5.13.1 Backup Formula and Scheduling

The basic asynchronous value-iteration backup for a selected state $s$ is:

$$V(s)\leftarrow \underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)\left[r+\gamma V(s^{\prime })\right]$$

5.13.2 Practical Advantages and Convergence

• Large Tabular MDPs: Avoids spending computational effort on irrelevant or unvisited states.
• Real-Time Planning: Interleaves DP updates with real interaction, focusing updates on states near the agent's current trajectory.
• Prioritized Sweeping: Updates states with large Bellman errors earlier to accelerate convergence.
• Convergence Guarantee: Asynchronous DP converges to $V^{\ast }$ provided no state is systematically ignored forever (i.e., every state is updated infinitely often).

5.14 Generalized Policy Iteration (GPI)

5.14.1 The GPI Spectrum

Almost all RL algorithms can be viewed as different granularities of GPI:

• Policy Iteration: Coarse-grained GPI. Complete policy evaluation runs to full numerical convergence before a single greedy policy improvement step is taken.
• Value Iteration: Fine-grained GPI. Policy evaluation is truncated to exactly one sweep before taking a greedy improvement step.
• Asynchronous DP: Flexible GPI. Evaluation and improvement backups are applied asynchronously to selected individual states.
• Monte Carlo & TD Control (SARSA/Q-learning): Sample-based GPI. Evaluation is learned from sampled experience transitions, and policy improvement proceeds incrementally.

5.15 Issues in Applying Dynamic Programming Methods

5.15.1 Detailed Breakdown of Practical Challenges

1. Full Sweeps over State Space: Performing systematic passes over millions of states becomes computationally intractable. Asynchronous and prioritized updates mitigate this burden.
2. Extracting Policy from State Values vs Action Values: Extracting $\pi$ from state values $V(s)$ requires a one-step lookahead using the model dynamics $p(s^{\prime },r|s,a)$. Action values $Q(s,a)$ eliminate this model requirement at decision time.
3. Policy Stabilization before Value Convergence: In many control tasks, the greedy policy stops changing long before value numbers fully converge to decimal precision. Monitoring policy stability prevents unnecessary sweeps.
4. Need for a Known Environment Model: DP requires explicit transition probabilities $p(s^{\prime },r|s,a)$. Model-free RL methods (Monte Carlo, TD) replace expected backups with sampled transitions when dynamics are unknown.
5. Finite and Discrete Action Sets: Tabular DP enumerates actions. Continuous action spaces (e.g., steering torque) require discretization or policy-gradient actor-critic methods.
6. Curse of Dimensionality / State Space Explosion: Storing tabular values scales exponentially with state variables. High-dimensional state spaces necessitate function approximation (deep neural networks).
7. When DP is Appropriate: Tabular DP is best suited for small, fully specified MDPs, offline planning simulators, and as the theoretical backbone for modern RL.

5.16 Practice Review Questions

Exam Guidance Summary

• Solve practice problems from the notes to build facility with the computations. The race car problem and grid world verification are the types of questions to expect.
• The notes cover the complete story and should be read with no omissions. Every section builds on the previous one.
• Policy iteration and value iteration are both essential algorithms to know. Focus on understanding their update rules, convergence criteria, and the in-place vs not-in-place distinction.

Key Industry Applications

• Traffic control: The MDP framework models traffic signal optimization. States represent traffic conditions, actions are signal changes, and rewards reflect flow efficiency. City traffic systems use RL to learn signal timing policies that reduce congestion.
• Atari games: The classic RL benchmark. States are raw game frames (pixels), actions are controller inputs, and rewards are score changes. Deep Q-Networks (DQN) use the MDP formulation to learn directly from pixels, achieving superhuman performance on many games.
• Recycling robot: An MDP example for autonomous agents operating under resource constraints. The robot must balance exploration (searching for cans) against conservation (waiting or recharging) — a fundamental trade-off in RL.
• Cart-pole balancing: Demonstrates episodic vs continuing task formulation. The same physical problem can be modeled either way, showing how the MDP framework is flexible. This is a standard testbed for RL algorithms.
• Race car problem: Illustrates policy iteration and value iteration with a simple 3-state MDP (Cool, Warm, Overheated). The agent learns that driving fast is rewarding in the short term but risks overheating — a classic exploration-exploitation and risk-reward trade-off.
• Dynamic programming in operations research: DP methods (policy iteration, value iteration) are used in supply chain management, inventory control, scheduling, and resource allocation — anywhere a known MDP model exists and the state space is tractable.