Lecture 10.2: MDPs and Reinforcement Learning

Markov Decision Processes (MDPs)

A Markov Decision Process (MDP) provides a mathematical framework for modeling decision-making in environments where outcomes are partly random and partly under the control of an agent.

It relies on the Markov Property: The future state depends only on the current state and action, not on the history of prior states (Memoryless). $P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)$

An MDP is defined by:

1. States ($S$): The set of all possible environmental states.
2. Actions ($A$): The set of all possible actions.
3. Transition Model ($T(s, a, s')$): The probability $P(s' \mid s, a)$ of transitioning to state $s'$ after taking action $a$ in state $s$.
4. Reward Function ($R(s)$): The immediate reward received for being in state $s$.

---

The Bellman Equation

To balance immediate rewards with future rewards, we discount future rewards using a Discount Factor ($\gamma \in [0, 1]$). The utility of a state $U(s)$ is captured by the Bellman Equation: $U(s) = R(s) + \gamma \max_{a \in A} \sum_{s'} T(s, a, s') U(s')$

This equation states that the long-term utility of a state is its immediate reward plus the discounted expected utility of the next state, assuming the agent acts optimally.

---

The Value Iteration Algorithm

Because the Bellman equation contains a $\max$ operator, it is non-linear and cannot be solved directly with linear algebra. Instead, we use Value Iteration, an iterative dynamic programming algorithm:

1. Initialize state utilities arbitrarily: $U_0(s) = 0$ for all $s$.
2. In each iteration $k+1$, update the utilities of all states simultaneously using the Bellman Update Equation:

$U_{k+1}(s) \leftarrow R(s) + \gamma \max_{a \in A} \sum_{s'} T(s, a, s') U_k(s')$

3. Repeat until the maximum change in utility across all states is less than a stopping threshold:

$\max_{s \in S} |U_{k+1}(s) - U_k(s)| < \epsilon \frac{1 - \gamma}{\gamma}$

Upon convergence, the optimal policy $\pi^*$ is extracted by choosing the action that maximizes the expected utility: $\pi^*(s) = \arg\max_{a \in A} \sum_{s'} T(s, a, s') U(s')$

---

Reinforcement Learning (RL)

If the transition probabilities $T(s, a, s')$ and reward function $R(s)$ are unknown, the agent cannot use Value Iteration. Instead, it must learn through trial-and-error using Reinforcement Learning.

Classifications of RL Algorithms

1. Model-Based vs. Model-Free

• Model-Based RL: The agent attempts to learn the transition function $T$ and reward function $R$ from experience, and then uses a planning algorithm (like Value Iteration) to find the optimal policy.
• Model-Free RL: The agent learns the value of actions directly from experience without ever building an explicit model of the environment's physics.

2. Value-Based vs. Policy-Based

• Value-Based RL: Focuses on learning the value of states or state-action pairs (e.g. Q-values). The policy is implicitly derived (e.g., choose the action with the highest Q-value).
• Policy-Based RL: Represents and optimizes the policy parameters $\pi_\theta(a \mid s)$ directly to maximize expected reward, skipping value estimation entirely.

3. On-Policy vs. Off-Policy

• On-Policy (e.g., SARSA): The agent learns from data gathered by executing the exact policy it is currently optimizing.
• Off-Policy (e.g., Q-Learning): The agent learns the optimal policy (target policy) while acting under a different, exploratory policy (behavior policy, such as taking random movements).

---

Q-Learning

Q-learning is a Model-Free, Off-Policy, Value-Based reinforcement learning algorithm. It estimates the quality of taking a specific action $a$ in a state $s$, denoted as the Q-value $Q(s, a)$.

The Q-Learning Update Equation

The agent updates its Q-values incrementally based on experience tuples $(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, controlling how much new information overwrites old estimates.
• $\gamma \in [0, 1]$ is the Discount Factor, controlling the importance of future rewards.
• $r$ is the immediate reward received in state $s'$ after taking action $a$.
• $\max_{a'} Q(s', a')$ is the estimated optimal future Q-value from the next state $s'$.
• $r + \gamma \max_{a'} Q(s', a') - Q(s, a)$ is the Temporal Difference (TD) Error.

---

Concrete Q-Table Example (Grid World)

Suppose a player navigates a $3 \times 3$ grid world.

• States ($S$): 9 distinct grid cells: $(1,1), (1,2), \dots, (3,3)$.
• Actions ($A$): 4 movements: $\{\text{Up}, \text{Down}, \text{Left}, \text{Right}\}$.

The agent maintains a Q-Table of dimensions $9 \times 4$. Each cell stores the expected future reward for taking that action in that state:

Interpretation: In state $(3,2)$, the highest Q-value is $5.4$ (for action Up). Under a greedy policy, the agent will choose Up as its action.

Action Selection: $\epsilon$-Greedy Policy

To prevent the agent from getting stuck in local optima, we use an $\epsilon$-greedy policy to balance exploration and exploitation:

• With probability $\epsilon$, the agent explores by selecting a random action.
• With probability $1 - \epsilon$, the agent exploits by choosing the action that maximizes the current Q-value: $\arg\max_{a} Q(s, a)$.