LRL-4: Markov Decision Processes (MDPs) - The Math Foundation

Okay, let's solidify our understanding of Reinforcement Learning with Chapter 4: Markov Decision Processes (MDPs) - The Math Foundation. We've been building intuition with analogies and examples. Now, we'll introduce the formal mathematical framework that underpins much of RL theory and algorithms: Markov Decision Processes (MDPs). Think of MDPs as providing the precise rules and language for describing RL problems.

Chapter 4: Markov Decision Processes (MDPs) - The Math Foundation

In this chapter, we'll formalize the environment and the agent's interaction using the concept of Markov Decision Processes (MDPs). MDPs provide a mathematical framework for modeling sequential decision-making in situations where outcomes are partly random and partly under the control of a decision-maker (our agent). We'll also introduce the crucial Bellman Equations, which are fundamental for understanding and calculating value functions in MDPs.

1. Introduction to Markov Property: "Memoryless" Systems

Before diving into MDPs, we need to understand the Markov Property. It's a key assumption in MDPs and simplifies things significantly.

• Markov Property (Informal): A system has the Markov property if the future state depends only on the current state, and not on the past history of states. In simpler terms, "the present state is all you need to know to predict the future." The past history is irrelevant once you know the current state. It's "memoryless" in the sense that the system doesn't need to remember the entire history.

(Analogy: Think about flipping a fair coin repeatedly. The outcome of the next flip (Heads or Tails) depends only on the fairness of the coin itself, not on whether you got Heads or Tails in the previous flips. Each coin flip is independent of the past, given the coin's properties. This is analogous to the Markov Property).

• Markov Property (Formal): A state S_t has the Markov property if:

  • P(S_t+1 | S_t) = P(S_t+1 | S_t, S_t-1, ..., S₀)

  (Equation: Markov Property)

  • This equation means that the probability of transitioning to the next state S_t+1 depends only on the current state S_t, and is independent of all previous states S_t-1, ..., S₀.

Why is Markov Property Important in RL?

• Simplifies Modeling: It makes it much easier to model and analyze the environment. We don't need to keep track of the entire history; we only need to consider the current state.
• Enables Efficient Algorithms: Many RL algorithms rely on the Markov property to be computationally feasible. It allows us to use dynamic programming and other techniques to solve for optimal policies and value functions.

Assumption in RL: In standard Reinforcement Learning, we often assume that the environment can be modeled as a Markov system, or at least approximated as one. We design our state representation to capture all relevant information so that the Markov property holds (or is approximately true).

2. What is a Markov Decision Process (MDP)? Components of an MDP.

A Markov Decision Process (MDP) is a mathematical framework for modeling sequential decision-making in stochastic environments where the Markov property holds. It's a tuple consisting of five key elements:

• (S, A, P, R, γ)

  (Tuple: Components of an MDP)

  Let's break down each component:

  1. S: Set of States (State Space): We've already discussed states in Chapter 2. S is the set of all possible states the environment can be in. It can be finite or infinite.

     • S = {s₁, s₂, ..., s_N} (for a finite state space with N states)

  2. A: Set of Actions (Action Space): We've also talked about actions. A is the set of all possible actions the agent can take. It can also be finite or infinite, and can depend on the current state (i.e., A(s) can be the set of actions available in state s).

     • A = {a₁, a₂, ..., a_M} (for a finite action space with M actions)

  3. P: Transition Probabilities (or Transition Function): This is new and crucial for MDPs. P defines the dynamics of the environment. It specifies the probability of transitioning from one state to another when taking a particular action.

     • P(s' | s, a) = P(S_t+1 = s' | S_t = s, A_t = a)

     (Equation: Transition Probability)

     • P(s' | s, a) is the probability of transitioning to state s' at time t+1, given that the agent is in state s at time t and takes action a at time t.
     • This is a probability distribution over possible next states s', for each state-action pair (s, a).
     • Because of the Markov property, this transition probability only depends on the current state s and action a, not on past history.

     (Example: Imagine a simple grid world. If you are in state 's' (grid cell) and take action 'Move Right', there might be an 80% probability of actually moving to the right cell (s'), a 10% probability of slipping and moving up, and a 10% probability of slipping and moving down. These probabilities P(s'|s, 'Move Right') for all possible next states s' define the transition dynamics for the 'Move Right' action in state 's').

  4. R: Reward Function: We've discussed rewards before. R specifies the reward the agent receives after transitioning to a new state. There are different ways to define the reward function:

     • R(s, a, s'): Reward received when transitioning from state s to state s' after taking action a.
     • R(s, a): Expected reward received after taking action a in state s.
     • R(s'): Reward received upon entering state s'.

     For simplicity, we'll often use R(s, a, s') or R(s, a). The reward function defines the immediate feedback the agent gets from the environment.

     (Example: In the grid world, R(s, a, s') might be -1 for every move (to encourage efficient paths), except when you transition into a goal state, where R(s, a, s_goal) = +10).

  5. γ: Discount Factor: We introduced the discount factor in Chapter 2. γ is a value between 0 and 1 (0 ≤ γ ≤ 1) that determines how much the agent values future rewards compared to immediate rewards.

     • γ is used to calculate the discounted return.
     • γ = 0: Agent only cares about immediate rewards.
     • γ close to 1: Agent values future rewards almost as much as immediate rewards (long-sighted agent).
     • In episodic tasks, γ is often set to 1 if the episode is guaranteed to terminate. In continuing tasks, γ is typically less than 1 to ensure that the total discounted reward is finite.

3. Visualizing MDPs: State Transition Diagrams

We can visualize MDPs using state transition diagrams. These diagrams are helpful for understanding the structure of the MDP, especially for small, finite MDPs.

• Nodes: Represent states (s ∈ S).
• Edges (Arrows): Represent transitions between states.
• Labels on Edges: Indicate the action (a ∈ A) that causes the transition and the transition probability P(s' | s, a). Sometimes, the reward R(s, a, s') is also shown.

(Example: Simple Grid World MDP Diagram)

Let's imagine a very simple 2-state MDP: State 1 (S1) and State 2 (S2). Let's say we have two actions: Action A and Action B.

(Diagram: 2-State MDP Transition Diagram)

       Action A (prob=0.8, R=-1)      Action B (prob=0.6, R=+5)
    S1 -------------------------> S2  <------------------------- S1
       Action B (prob=0.2, R=-1)      Action A (prob=0.4, R=+5)
       ^                                                        |
       |                                                        v
       | Action A (prob=0.5, R=0)      Action B (prob=0.7, R=0)
    S2 -------------------------> S2  <------------------------- S2
       Action B (prob=0.5, R=0)      Action A (prob=0.3, R=0)

• From S1:
  • Taking Action A: 80% chance to go to S2 (reward -1), 20% chance to stay in S1 (reward -1).
  • Taking Action B: 60% chance to go to S2 (reward +5), 40% chance to stay in S1 (reward +5).
• From S2:
  • Taking Action A: 50% chance to stay in S2 (reward 0), 50% chance to go to S1 (reward 0).
  • Taking Action B: 70% chance to stay in S2 (reward 0), 30% chance to go to S1 (reward 0).

4. The Goal in MDPs: Finding Optimal Policies (Revisited)

In the context of MDPs, the goal of Reinforcement Learning remains the same: to find an optimal policy π that maximizes the expected cumulative reward (discounted return).

• Policy in MDPs: A policy π is a mapping from states to probabilities of actions, π(a|s).

• Optimal Policy π_*: A policy π is optimal if for all states s and all policies *π',

  • V^π(s) ≥ V^π'(s)*

  (Equation: Definition of Optimal Policy)

  • This means that the optimal policy π achieves a state value function V^π(s) that is greater than or equal to the state value function V^π'(s) for any other policy π' in all states s*.

5. Bellman Equations: The Heart of Value Functions in MDPs (Intuitive Introduction)

Bellman Equations are a set of equations that define the relationship between the value of a state (or state-action pair) and the values of its successor states. They are fundamental to solving MDPs and understanding value functions.

• Bellman Expectation Equation for State Value Function (V^π):

  • V^π(s) = E_π [R_t+1 + γV^π(S_t+1) | S_t = s]

  (Equation: Bellman Expectation Equation for V^π)

  • Intuition: The value of a state s under policy π is equal to the expected immediate reward you get from state s, plus the discounted expected value of the next state S_t+1, when you follow policy π.

  • Breakdown:

    • E_π [ ... | S_t = s]: Expected value, given that we start in state s and follow policy π.
    • R_t+1: Immediate reward received after taking an action from state s.
    • γV^π(S_t+1): Discounted value of the next state S_t+1.

  • Expanding the Expectation: We can expand this equation using the definition of expectation and transition probabilities:

    • V^π(s) = ∑_a∈A π(a|s) ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV^π(s')]

    (Expanded Bellman Expectation Equation for V^π)

    • This form explicitly shows the policy π(a|s) (probability of choosing action a in state s), transition probabilities P(s'|s, a), rewards R(s, a, s'), and the recursive nature of the equation (V^π(s) is defined in terms of V^π(s')).

• Bellman Expectation Equation for Action Value Function (Q^π):

  • Q^π(s, a) = E_π [R_t+1 + γQ^π(S_t+1, A_t+1) | S_t = s, A_t = a]

  (Equation: Bellman Expectation Equation for Q^π)

  • Intuition: The value of taking action a in state s and following policy π afterwards is equal to the expected immediate reward you get, plus the discounted expected value of the next state S_t+1 and the next action A_t+1 (chosen according to policy π in state S_t+1), when you continue to follow policy π.

  • Expanding the Expectation:

    • Q^π(s, a) = ∑_s'∈S P(s'|s, a) [R(s, a, s') + γ ∑_a'∈A π(a'|s') Q^π(s', a')]

    (Expanded Bellman Expectation Equation for Q^π)

    • This form shows the transition probabilities P(s'|s, a), rewards R(s, a, s'), policy π(a'|s'), and the recursive definition of Q^π.

Bellman Optimality Equations (Brief Introduction - More in Chapter 5):

Just as there are Bellman Expectation Equations for any policy π, there are also Bellman Optimality Equations that hold specifically for the optimal value functions V(s) and Q(s, a).

• Bellman Optimality Equation for State Value Function (V^*):

  • V(s) = max_a∈A E [R_t+1 + γV(S_t+1) | S_t = s, A_t = a]

  (Equation: Bellman Optimality Equation for V^*)

  • V(s) = max_a∈A ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV(s')] (Expanded form)

  • Intuition: The optimal value of a state s is the maximum expected return you can get by choosing the best action a in state s, and then acting optimally from the next state S_t+1 onwards. It's "choose the action that maximizes your future value."

• Bellman Optimality Equation for Action Value Function (Q^*):

  • Q(s, a) = E [R_t+1 + γ max_a'∈A Q(S_t+1, a') | S_t = s, A_t = a]

  (Equation: Bellman Optimality Equation for Q^*)

  • Q(s, a) = ∑_s'∈S P(s'|s, a) [R(s, a, s') + γ max_a'∈A Q(s', a')] (Expanded form)

  • Intuition: The optimal Q-value for a state-action pair (s, a) is the expected immediate reward plus the discounted maximum Q-value achievable from the next state S_t+1. After taking action a in state s, you want to choose the best possible action a' in the next state S_t+1 to maximize your future reward.

Significance of Bellman Equations:

• Basis for Computation: Bellman equations provide a recursive relationship that can be used to compute value functions. They are the foundation for many algorithms to solve MDPs, such as Dynamic Programming, Value Iteration, and Policy Iteration (which we will discuss in Chapter 5).
• Understanding Optimal Policies: Bellman Optimality Equations characterize optimal value functions and optimal policies. They tell us what it means for a policy to be optimal and how optimal values are related to each other.

In Summary (Chapter 4):

We've now laid the mathematical foundation for Reinforcement Learning using Markov Decision Processes (MDPs). We've covered:

• Markov Property: The "memoryless" property that simplifies modeling.
• MDP Components (S, A, P, R, γ): Defining states, actions, transitions, rewards, and discount factor.
• State Transition Diagrams: Visualizing MDPs.
• Goal in MDPs: Finding optimal policies to maximize cumulative reward.
• Bellman Expectation Equations (V^π, Q^π): Defining value functions recursively.
• Bellman Optimality Equations (V, Q): Introducing the equations for optimal value functions (briefly).

In the next chapter, we will explore Dynamic Programming methods, which use Bellman equations to solve MDPs in cases where we have complete knowledge of the environment (i.e., we know the transition probabilities and reward function). This will give us our first set of algorithms for finding optimal policies and value functions in Reinforcement Learning!