Lecture 10.2: MDPs and Reinforcement Learning

In traditional supervised machine learning, models require massive amounts of labeled data. Collecting such data is often expensive, and real-world datasets may contain missing, noisy, or untrustworthy values.

Reinforcement Learning (RL) overcomes data collection constraints by enabling an agent to learn directly through trial-and-error interactions with an environment, receiving positive rewards for effective actions and negative rewards for undesirable outcomes.

Markov Decision Processes (MDPs)

A Markov Decision Process (MDP) provides the formal mathematical foundation for decision-making under uncertainty in discrete time steps.

The Markov Property

An MDP assumes the Markov Property (memorylessness): the probability of reaching the next state depends only on the current state and action, not on the sequence of preceding states or past history: $P(S_{t+1} \mid S_t, S_{t-1}, \dots, S_0) = P(S_{t+1} \mid S_t)$

Why is the Markov Property important?

• Efficient Computation: Eliminates the need to store or process full state histories.
• Mathematical Tractability: Enables recursive algorithms (like Value Iteration and Dynamic Programming).
• RL Foundation: Forms the backbone of both model-based and model-free reinforcement learning algorithms.

Formal MDP Definition

An MDP is formally specified by a tuple $(S, A, T, r, s_1)$:

1. States ($S$): The set of all valid environmental states.
2. Actions ($A$): The set of all possible actions.
3. Transition Function ($T(s, a, s')$): The probability distribution of transitioning to state $s'$ after taking action $a$ in state $s$.
4. Reward Function ($r: S \rightarrow \mathbb{R}$): The immediate scalar reward received for being in state $s$.
5. Start State ($s_1 \in S$): The initial starting state of the process.

Concrete 4-State MDP Example

Consider a sample MDP with four states $S = \{s_1, s_2, s_3, s_4\}$, start state $s_1$, and actions $A = \{a_1, a_2, a_3, a_4\}$.

Reward & Transition Tables

Policy and Discounted Future Rewards

The Policy Dilemma

Should an agent take 100 actions with no reward to reach a state with a massive reward of $100$, or take 100 actions that each yield a reward of 1?

Key trade-offs in defining agent policies:

1. Agents don't live forever: Waiting too many steps for a distant reward introduces survival risk.
2. Immediate rewards are safer: Immediate rewards are more reliable than uncertain future possibilities.
3. Delaying gratification: Delaying gratification can be intelligent—but only up to a reasonable point.

Discounted Return & The Bellman Equation

To model preference for earlier rewards, we apply a Discount Factor ($\gamma \in (0, 1)$) to future rewards. The total discounted return over an infinite sequence of states is: $\text{Discounted Return} = \gamma^0 r(s_1) + \gamma^1 r(s_2) + \gamma^2 r(s_3) + \dots = \sum_{t=0}^{\infty} \gamma^t r(s_t)$

The long-term utility $u(s)$ of being in state $s$ under an optimal policy satisfies the Bellman Equation: $u(s) = r(s) + \gamma \max_{a \in A} \sum_{s' \in S} T(s, a, s') u(s')$

System of Bellman Equations

For an environment with $n$ states, there are $n$ Bellman equations with $n$ unknown utility variables.

• Why can't we solve this directly with matrix algebra? The presence of the non-linear $\max_{a}$ operator prevents direct linear algebra solutions. We must use dynamic programming algorithms like Value Iteration.

The Value Iteration Algorithm

Value Iteration starts with initial arbitrary utility estimates $u^0(s)$ and iteratively updates state utilities over time steps $t$ using the Bellman Update Equation: $u^{t+1}(s) \leftarrow r(s) + \gamma \max_{a \in A} \sum_{s' \in S} T(s, a, s') u^t(s')$

Stopping Criterion & Error Bound ($\epsilon$)

Iterations continue until the maximum change in utility across all states in a time step falls below a threshold: $\max_{s \in S} |u^{t+1}(s) - u^t(s)| < \epsilon \frac{1 - \gamma}{\gamma}$ When this holds, the error of the current utility estimates relative to true optimal values is guaranteed to be less than $\epsilon$.

Role of Parameters ($\epsilon$ and $\gamma$)

• User Error Threshold ($\epsilon$): Controls precision. A smaller $\epsilon$ yields higher accuracy but requires more iterations to converge.
• High Discount Factor ($\gamma \to 1$): Agent strongly values long-term future rewards. Slower convergence because tiny changes in distant states propagate across many iterations.
• Low Discount Factor ($\gamma \ll 1$): Agent prioritizes immediate rewards. Faster convergence because distant rewards decay rapidly.

[!WARNING] Stopping Criteria Nuances

1. No Absolute Guarantees: The utility difference criterion signals that further updates yield minimal change, but doesn't guarantee discovering absolute optimal policy values in non-convex or high-dimensional approximations.
2. Local Optima: The algorithm may stabilize at local optima in complex domains.
3. Combined Criteria: In practice, value iteration is often combined with a maximum iteration count limit and environmental performance checks.

Value Iteration Algorithm Pseudocode & Execution Trace

VALUE-ITERATION(T, r, gamma, epsilon)
1  do
2      u <- u'
3      delta <- 0
4      for each s in S do
5          u'(s) <- r(s) + gamma * max_a sum_{s'} T(s, a, s') * u(s')
6          if |u'(s) - u(s)| > delta then
7              delta <- |u'(s) - u(s)|
8  until delta < epsilon * (1 - gamma) / gamma
9  return u

Solved Example: Value Iteration

Problem Statement

Consider a Markov Decision Process (MDP) defined by state space $S = \{s_1, s_2, s_3, s_4\}$, action space $A = \{a_1, a_2, a_3, a_4\}$, and discount factor $\gamma = 0.5$.

• State Rewards: $r(s_1) = 0$, $r(s_2) = 0$, $r(s_3) = 1$ (Goal State), $r(s_4) = 0$
• Transition Probabilities $T(s, a, s')$:

Tasks:

1. Compute state utility values $u^t(s)$ for iterations $t = 0, 1, 2, 3, 4$ using Value Iteration starting with $u^0(s) = 0$. Show step-by-step action evaluations.
2. Extract the optimal policy $\pi^*(s)$ for all states.

Step-by-Step Value Iteration Solution

Iteration $t = 0$ (Initialization)

Initial state utility estimates are initialized to zero: $u^0(s_1) = 0.000, \quad u^0(s_2) = 0.000, \quad u^0(s_3) = 0.000, \quad u^0(s_4) = 0.000$

Iteration $t = 1$

Update formula: $u^1(s) = r(s) + 0.5 \max_{a} \sum_{s'} T(s, a, s') u^0(s')$

• For State $s_1$ ($r=0$):

  • Action $a_1$: $0.2(0) + 0.8(0) = 0.000$
  • Action $a_2$: $0.2(0) + 0.8(0) = 0.000$ $\implies u^1(s_1) = 0 + 0.5(0.000) = 0.000$

• For State $s_2$ ($r=0$):

  • Action $a_2$: $0.2(0) + 0.8(0) = 0.000$
  • Action $a_3$: $0.2(0) + 0.8(0) = 0.000$ $\implies u^1(s_2) = 0 + 0.5(0.000) = 0.000$

• For State $s_3$ ($r=1$):

  • Action $a_4$: $1.0(0) = 0.000$
  • Action $a_3$: $1.0(0) = 0.000$ $\implies u^1(s_3) = 1 + 0.5(0.000) = 1.000$

• For State $s_4$ ($r=0$):

  • Action $a_1$: $0.1(0) + 0.9(0) = 0.000$
  • Action $a_4$: $0.2(0) + 0.8(0) = 0.000$ $\implies u^1(s_4) = 0 + 0.5(0.000) = 0.000$

Iteration $t = 2$

Update formula: $u^2(s) = r(s) + 0.5 \max_{a} \sum_{s'} T(s, a, s') u^1(s')$

• For State $s_1$ ($r=0$):

  • Action $a_1$: $0.2 u^1(s_1) + 0.8 u^1(s_2) = 0.2(0) + 0.8(0) = 0.000$
  • Action $a_2$: $0.2 u^1(s_1) + 0.8 u^1(s_4) = 0.2(0) + 0.8(0) = 0.000$ $\implies u^2(s_1) = 0 + 0.5(0.000) = 0.000$

• For State $s_2$ ($r=0$):

  • Action $a_2$: $0.2 u^1(s_2) + 0.8 u^1(s_3) = 0.2(0) + 0.8(1.000) = 0.800$ $\leftarrow \text{Max}$
  • Action $a_3$: $0.2 u^1(s_2) + 0.8 u^1(s_1) = 0.2(0) + 0.8(0) = 0.000$ $\implies u^2(s_2) = 0 + 0.5(0.800) = 0.400$

• For State $s_3$ ($r=1$):

  • Action $a_4$: $1.0 u^1(s_2) = 1.0(0) = 0.000$
  • Action $a_3$: $1.0 u^1(s_4) = 1.0(0) = 0.000$ $\implies u^2(s_3) = 1 + 0.5(0.000) = 1.000$

• For State $s_4$ ($r=0$):

  • Action $a_1$: $0.1 u^1(s_4) + 0.9 u^1(s_3) = 0.1(0) + 0.9(1.000) = 0.900$ $\leftarrow \text{Max}$
  • Action $a_4$: $0.2 u^1(s_4) + 0.8 u^1(s_1) = 0.2(0) + 0.8(0) = 0.000$ $\implies u^2(s_4) = 0 + 0.5(0.900) = 0.450$

Iteration $t = 3$

Update formula: $u^3(s) = r(s) + 0.5 \max_{a} \sum_{s'} T(s, a, s') u^2(s')$

• For State $s_1$ ($r=0$):

  • Action $a_1$: $0.2(0) + 0.8(0.400) = 0.320$
  • Action $a_2$: $0.2(0) + 0.8(0.450) = 0.360$ $\leftarrow \text{Max}$ $\implies u^3(s_1) = 0 + 0.5(0.360) = 0.180$

• For State $s_2$ ($r=0$):

  • Action $a_2$: $0.2(0.400) + 0.8(1.000) = 0.080 + 0.800 = 0.880$ $\leftarrow \text{Max}$
  • Action $a_3$: $0.2(0.400) + 0.8(0) = 0.080$ $\implies u^3(s_2) = 0 + 0.5(0.880) = 0.440$

• For State $s_3$ ($r=1$):

  • Action $a_4$: $1.0(0.400) = 0.400$
  • Action $a_3$: $1.0(0.450) = 0.450$ $\leftarrow \text{Max}$ $\implies u^3(s_3) = 1 + 0.5(0.450) = 1.225$

• For State $s_4$ ($r=0$):

  • Action $a_1$: $0.1(0.450) + 0.9(1.000) = 0.045 + 0.900 = 0.945$ $\leftarrow \text{Max}$
  • Action $a_4$: $0.2(0.450) + 0.8(0) = 0.090$ $\implies u^3(s_4) = 0 + 0.5(0.945) = 0.473$

Iteration $t = 4$

Update formula: $u^4(s) = r(s) + 0.5 \max_{a} \sum_{s'} T(s, a, s') u^3(s')$

• For State $s_1$ ($r=0$):

  • Action $a_1$: $0.2(0.180) + 0.8(0.440) = 0.036 + 0.352 = 0.388$
  • Action $a_2$: $0.2(0.180) + 0.8(0.473) = 0.036 + 0.378 = 0.414$ $\leftarrow \text{Max}$ $\implies u^4(s_1) = 0 + 0.5(0.414) = 0.207$

• For State $s_2$ ($r=0$):

  • Action $a_2$: $0.2(0.440) + 0.8(1.225) = 0.088 + 0.980 = 1.068$ $\leftarrow \text{Max}$
  • Action $a_3$: $0.2(0.440) + 0.8(0.180) = 0.088 + 0.144 = 0.232$ $\implies u^4(s_2) = 0 + 0.5(1.068) = 0.534$

• For State $s_3$ ($r=1$):

  • Action $a_4$: $1.0(0.440) = 0.440$
  • Action $a_3$: $1.0(0.473) = 0.473$ $\leftarrow \text{Max}$ $\implies u^4(s_3) = 1 + 0.5(0.473) = 1.236$

• For State $s_4$ ($r=0$):

  • Action $a_1$: $0.1(0.473) + 0.9(1.225) = 0.0473 + 1.1025 = 1.150$ $\leftarrow \text{Max}$
  • Action $a_4$: $0.2(0.473) + 0.8(0.180) = 0.0946 + 0.1440 = 0.239$ $\implies u^4(s_4) = 0 + 0.5(1.150) = 0.575$

Summary Value Iteration Matrix Table

Extracted Optimal Policy ($\pi^*(s)$)

Evaluating $\arg\max_{a} \sum_{s'} T(s, a, s') u^4(s')$ at each state gives the optimal policy:

• $\pi^*(s_1) = \arg\max \{ a_1: 0.388, \mathbf{a_2: 0.414} \} = a_2$
• $\pi^*(s_2) = \arg\max \{ \mathbf{a_2: 1.068}, a_3: 0.232 \} = a_2$
• $\pi^*(s_3) = \arg\max \{ a_4: 0.440, \mathbf{a_3: 0.473} \} = a_3$
• $\pi^*(s_4) = \arg\max \{ \mathbf{a_1: 1.150}, a_4: 0.239 \} = a_1$

$\pi^*(s_1) = a_2, \quad \pi^*(s_2) = a_2, \quad \pi^*(s_3) = a_3, \quad \pi^*(s_4) = a_1$

Multiagent Markov Decision Processes (MMDPs)

When an environment contains multiple interacting agents, single-agent MDP definitions must be extended:

1. Naive Simplification (Environment Embedding): Fold all other agents' behaviors into the environment transition function $T(s, a, s')$, assuming other agents are non-adaptive background elements. Drawback: Rarely works because other agents adapt their strategies over time, violating the fixed transition function requirement of MDPs.
2. Joint Action MDPs (Better Method): Extend transitions to take a Joint Action Vector $\vec{a} = (a_1, a_2, \dots, a_n)$, where each element represents the action of agent $i$: $T(s, \vec{a}, s')$
3. Reward Allocation Strategies:
   • Equal Division: Split collective system rewards equally among all agents.
   • Marginal Contribution: Assign rewards proportional to each agent's individual contribution to the total system payoff.

Reinforcement Learning Taxonomy & Trade-offs

If environmental dynamics $T(s, a, s')$ and reward function $r(s)$ are unknown, the agent must use Reinforcement Learning (RL).

Key RL Trade-offs

On-Policy vs. Off-Policy Reinforcement Learning

A critical distinction in model-free RL is how the agent handles experience generation versus policy optimization:

• Behavior Policy ($\mu$ or $\pi_b$): The policy used by the agent to interact with the environment, select actions, and collect experience tuples $(s, a, r, s')$. This policy often includes exploration mechanisms (e.g., $\epsilon$-greedy).
• Target Policy ($\pi$ or $\pi_t$): The policy that the agent is evaluating and attempting to optimize into the optimal strategy $\pi^*$.

1. On-Policy Learning (e.g., SARSA)

In On-Policy methods, the target policy is identical to the behavior policy ($\pi_t = \pi_b$). The agent learns the value of the policy it is actively executing. $\text{SARSA Update: } Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma Q(s', a') - Q(s, a) \right]$ where $a'$ is the actual next action chosen by the current behavior policy in state $s'$.

• Characteristics: Conservative and safe. If the behavior policy makes random exploratory mistakes near dangerous states, SARSA lowers the Q-value of those states to reflect the risk of exploration.

2. Off-Policy Learning (e.g., Q-Learning)

In Off-Policy methods, the target policy is independent of the behavior policy ($\pi_t \neq \pi_b$). The agent learns the optimal target policy (greedy action selection) while using a different, exploratory behavior policy to gather data. $\text{Q-Learning Update: } Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$

• Characteristics: Evaluates the best possible next action $\max_{a'} Q(s', a')$, regardless of which action the behavior policy actually selects next. This allows learning optimal control directly from historical logs, random exploration, or offline data.

Q-Learning (Off-Policy Model-Free RL)

Q-learning is an off-policy, model-free, value-based algorithm. The "Q" stands for Quality—representing how valuable taking a specific action is in maximizing long-term cumulative rewards.

The Q-Learning Update Rule

For experience tuple $(s, a, r, s')$: $Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$

where:

• $\alpha \in (0, 1]$ is the Learning Rate.
• $\gamma \in [0, 1]$ is the Discount Factor.
• $r + \gamma \max_{a'} Q(s', a') - Q(s, a)$ is the Temporal Difference (TD) Error.

Concrete 3x3 Grid World Q-Learning Example

Consider a $3 \times 3$ grid world navigation problem with 9 discrete states $S = \{(1,1), (1,2), \dots, (3,3)\}$ and 4 movement actions $A = \{\text{Left}, \text{Right}, \text{Up}, \text{Down}\}$.

Environment Specification

• State Space (9 states): Row-column coordinates $(x, y)$ where $x \in \{1, 2, 3\}$ (row) and $y \in \{1, 2, 3\}$ (column).
• Action Space (4 actions): $\{\text{Left}, \text{Right}, \text{Up}, \text{Down}\}$.
• Special States & Rewards:
  • Goal State $(1, 3)$: Immediate reward $r = +5$ (Terminal).
  • Danger State $(2, 2)$: Immediate penalty $r = -10$.
  • Clear State $(1, 1)$: Neutral reward $r = +0$.
  • Start State $(3, 2)$: Initial position of agent.
• Q-Table Matrix Size: $9 \text{ states} \times 4 \text{ actions} = 36$ state-action entries.

Initial Q-Table (All Values Initialized to 0)

[!NOTE] State-Action Entry Interpretation The table cell at row $(3, 2)$ and column $\text{Up}$ stores $Q((3, 2), \text{Up})$, which represents the agent's estimated long-term reward for taking action $\text{Up}$ when standing at state $(3, 2)$.

Step-by-Step Q-Learning Execution Trace ($\alpha = 0.5$, $\gamma = 0.9$)

Step 1: Moving Up into Danger from Start $(3,2)$

1. Current State: $s = (3, 2)$
2. Selected Action: $a = \text{Up}$
3. Next State: $s' = (2, 2)$ (Danger Cell)
4. Observed Reward: $r = -10$
5. Calculate Max Future Value: $\max_{a'} Q((2,2), a') = 0$ (all Q-values initially 0)
6. Temporal Difference Error: $\text{TD Error} = r + \gamma \max_{a'} Q(s', a') - Q(s, a) = -10 + 0.9(0) - 0 = -10$
7. Q-Table Update: $Q((3,2), \text{Up}) \leftarrow Q((3,2), \text{Up}) + \alpha \cdot \text{TD Error} = 0 + 0.5(-10) = -5.0$

Step 2: Reaching Goal from $(2,3)$

1. Current State: $s = (2, 3)$
2. Selected Action: $a = \text{Up}$
3. Next State: $s' = (1, 3)$ (Goal Cell)
4. Observed Reward: $r = +5$
5. Calculate Max Future Value: $\max_{a'} Q((1,3), a') = 0$
6. Temporal Difference Error: $\text{TD Error} = 5 + 0.9(0) - 0 = +5$
7. Q-Table Update: $Q((2,3), \text{Up}) \leftarrow 0 + 0.5(+5) = +2.5$

Step 3: Backward Propagation of Value from $(3,3)$

1. Current State: $s = (3, 3)$
2. Selected Action: $a = \text{Up}$
3. Next State: $s' = (2, 3)$
4. Observed Reward: $r = 0$
5. Calculate Max Future Value: $\max_{a'} Q((2,3), a') = Q((2,3), \text{Up}) = +2.5$
6. Temporal Difference Error: $\text{TD Error} = 0 + 0.9(2.5) - 0 = +2.25$
7. Q-Table Update: $Q((3,3), \text{Up}) \leftarrow 0 + 0.5(2.25) = +1.125$

Updated Q-Table (After Steps 1–3)

Real-World Off-Policy Applications

• Robot Maze Exploration: A robot uses a completely random exploration policy (behavior policy) to explore a maze, while using recorded experience buffer tuples to train a goal-directed optimal policy (target policy).
• Advertisement Recommendation Systems: E-commerce systems monitor random user browsing logs to learn an optimal ad targeting strategy off-policy without degrading live user experience.

Exploration vs. Exploitation ($\epsilon$-Greedy Policy)

To balance trying new actions with selecting known high-value actions, the agent chooses actions during training using an $\epsilon$-greedy decision rule: Generate a uniform random number $p \in [0, 1]$ at each step: $\pi(a \mid s) = \begin{cases} \text{Random action } a \in A & \text{if } p < \epsilon \quad (\text{Exploration}) \\ \arg\max_{a} Q(s, a) & \text{if } p \ge \epsilon \quad (\text{Exploitation}) \end{cases}$