LRL-6: Monte Carlo Methods - Learning from Episodes

Okay, let's move on to Chapter 6: Monte Carlo Methods - Learning from Episodes. In the previous chapter, we explored Dynamic Programming, which is powerful but requires a complete model of the environment. Now, we're going to take a step towards more practical Reinforcement Learning methods that can learn directly from experience, without needing a perfect model. This is where Monte Carlo (MC) Methods come into play.

Chapter 6: Monte Carlo Methods - Learning from Episodes

In this chapter, we'll introduce Monte Carlo (MC) Methods, a class of Reinforcement Learning algorithms that learn directly from episodes of experience. Unlike Dynamic Programming, Monte Carlo methods are model-free, meaning they do not require complete knowledge of the environment's transition probabilities and reward function. They learn by averaging sample returns from complete episodes. This makes them more flexible and applicable to problems where building a full environment model is difficult or impossible.

1. Introduction to Monte Carlo Methods: Learning from Experience

• What are Monte Carlo Methods? In general, Monte Carlo methods are computational algorithms that rely on repeated random sampling to obtain numerical results. They are often used in physical and mathematical problems and are particularly useful when it's hard or impossible to compute an exact result with a deterministic algorithm.

  (Analogy: Estimating the value of π (pi) using Monte Carlo) Imagine you draw a square and inscribe a circle inside it. If you randomly throw darts at the square, the ratio of darts that land inside the circle to the total number of darts thrown will approximate the ratio of the circle's area to the square's area, which is related to π. By throwing a large number of darts (random sampling), you can get a good estimate of π without needing to calculate it analytically.

  (Image: Dart throwing analogy for Monte Carlo estimation of Pi)

• Monte Carlo Methods in RL: Learning from Episodes: In Reinforcement Learning, Monte Carlo methods use episodes of experience to learn value functions and optimal policies. An episode is a complete sequence of states, actions, and rewards, from a starting state to a terminal state.

  • Key Idea: Instead of using a model to predict future states and rewards (like DP), MC methods wait until the end of an episode and then use the actual returns observed during that episode to update value function estimates.

• Model-Free Learning: Monte Carlo methods are model-free. They learn directly from raw experience without explicitly estimating transition probabilities P(s'|s, a) or the reward function R(s, a, s'). All they need is the ability to generate or have access to episodes of interaction with the environment.

• Applicable to Episodic Tasks: Classical Monte Carlo methods, as we'll discuss in this chapter, are primarily designed for episodic tasks, where interaction naturally breaks down into episodes that eventually terminate. For continuing tasks, modifications are needed (which we may touch upon later).

• Advantages of Monte Carlo Methods:

  • No Model Required: Don't need to know P(s'|s, a) and R(s, a, s'). Learn directly from experience.
  • Can Learn from Actual or Simulated Experience: Can be used with real-world interaction or in simulations.
  • Conceptually Simple: Relatively easy to understand and implement.

• Disadvantages of Monte Carlo Methods:

  • Only Works for Episodic Tasks (in basic form): Requires complete episodes to update value functions.
  • High Variance: Returns can be quite variable from one episode to another, leading to high variance in value function estimates.
  • Inefficient: Can be slow to learn, especially if episodes are long and rewards are sparse.

2. Episodes, Returns, and Sample Averages

Let's revisit some key concepts in the context of Monte Carlo methods.

• Episode: As we defined earlier, an episode is a sequence of states, actions, and rewards that starts from an initial state and ends in a terminal state.

  • Episode = S₀, A₀, R₁, S₁, A₁, R₂, S₂, ..., S_T-1, A_T-1, R_T, S_T (Terminal State)

  (Sequence of states, actions, rewards in an episode)

• Return (G_t): The return G_t is the total discounted reward from time step t onwards in an episode. For an episode that terminates at time T, the return at time t is:

  • G_t = R_t+1 + γR_t+2 + ... + γ^T-t-1R_T

  (Equation: Return in an Episode)

  • In Monte Carlo methods, we use the actual return observed in an episode to update value function estimates.

• Sample Average: Monte Carlo methods estimate value functions by averaging the returns observed in many episodes. For example, to estimate the value of a state s, we can:

  1. Run many episodes, starting from (or visiting) state s.
  2. For each episode where state s is visited, record the return G_t starting from the first time s is visited in that episode.
  3. Average all these recorded returns. This sample average is an estimate of V^π(s).

  (Analogy: Estimating the average height of students in a university using sampling) If you want to estimate the average height of all students in a large university, you could randomly sample a group of students, measure their heights, and calculate the average height of the sample. As you increase the sample size, the sample average will get closer to the true average height of all students. Monte Carlo methods use a similar idea for estimating value functions, using episodes as samples.

3. Monte Carlo Policy Evaluation: Estimating V^π(s)

Let's focus on using Monte Carlo methods to estimate the state value function V^π(s) for a given policy π. We want to learn V^π(s) for all states s.

Two Main Approaches for Monte Carlo Policy Evaluation:

• First-Visit Monte Carlo (FVMC): For each episode, we only consider the first time each state is visited in that episode to calculate returns and update value estimates.

  • For each episode:
    • For each state s visited in the episode:
      • If s is the first time visited in this episode:
        • Calculate the return G_t starting from the time of first visit to s.
        • Append G_t to a list of returns for state s.
        • Update V^π(s) to be the average of all returns in the list for s.

• Every-Visit Monte Carlo (EVMC): For each episode, we consider all visits to each state in that episode to calculate returns and update value estimates.

  • For each episode:
    • For each state s visited in the episode (every time it's visited):
      • Calculate the return G_t starting from the time of visit to s.
      • Append G_t to a list of returns for state s.
      • Update V^π(s) to be the average of all returns in the list for s.

Which is Better: First-Visit or Every-Visit?

• For estimating V^π(s), both FVMC and EVMC converge to the true V^π(s) as the number of episodes increases (under certain conditions).
• FVMC is often slightly preferred theoretically because it's easier to analyze mathematically. However, in practice, the difference between them is often small, and EVMC might be more computationally efficient in some cases as it uses more data from each episode.

Algorithm: Monte Carlo Policy Evaluation (First-Visit)

Algorithm: Monte Carlo Policy Evaluation (First-Visit)

Input: Policy π, MDP environment (for generating episodes)
Output: Estimated state value function V<sup>π</sup>

Initialize:
    V<sup>π</sup>(s) = 0 for all s ∈ S  (Value estimates)
    Returns(s) = empty list for all s ∈ S (List to store returns for each state)

Loop (for each episode):
    Generate an episode following policy π:  S<sub>0</sub>, A<sub>0</sub>, R<sub>1</sub>, S<sub>1</sub>, A<sub>1</sub>, R<sub>2</sub>, S<sub>2</sub>, ..., S<sub>T</sub>
    States_in_episode = list of states visited in the episode
    For each state s in States_in_episode:
        If s is the first visit in the episode:
            Find the return G for the episode starting from the first visit to s
            Append G to Returns(s)
            V<sup>π</sup>(s) = average(Returns(s))  (Update value estimate using sample average)

Return: V<sup>π</sup>

Example: Imagine a simple grid world game. You have a policy (e.g., move randomly). You run episodes of this game. For each episode, you record the sequence of states and rewards. To estimate V^π(s) for a particular state s, you look at all episodes where state s was visited. For each such episode, you calculate the return from the first visit to s until the end of the episode. Then, you average these returns across all episodes to get your estimate of V^π(s). You repeat this for all states to get the complete value function V^π.

(Image: Example of an episode in a grid world, highlighting first visits to states and returns)

4. Monte Carlo Control: Learning Optimal Policies

Now, let's move to the more exciting part: using Monte Carlo methods for control, i.e., finding an optimal policy. We want to learn a policy π that maximizes the expected return.

We can use the idea of Generalized Policy Iteration (GPI), which we saw with Dynamic Programming, but now using Monte Carlo methods for policy evaluation and improvement.

Monte Carlo Control - GPI Approach:

1. Initialization: Start with an arbitrary policy π (e.g., random policy).
2. Policy Evaluation: Estimate the action value function Q^π(s, a) for the current policy π using Monte Carlo policy evaluation (we need to estimate Q^π now because we want to improve policy action by action).
3. Policy Improvement: Improve the policy π by making it greedy with respect to the estimated Q^π(s, a). For each state s, choose the action a that maximizes Q^π(s, a). This gives us a new, improved policy π'.
4. Repeat: Go back to step 2 with the new policy π'. Repeat until the policy converges (no more improvement).

Estimating Q^π(s, a) using Monte Carlo:

To perform policy evaluation for control, we need to estimate the action value function Q^π(s, a), not just V^π(s). We can do this using Monte Carlo methods in a similar way as we estimated V^π(s).

• For each episode:
  • For each state-action pair (s, a) visited in the episode:
    • Calculate the return G_t starting from the first time (s, a) is visited in the episode (or every time for every-visit MC).
    • Average these returns across episodes to estimate Q^π(s, a).

Policy Improvement using Q^π(s, a):

Once we have an estimate of Q^π(s, a), we can improve the policy by making it greedy. For each state s, the new policy π'(s) chooses the action that maximizes Q^π(s, a):

• π'(s) = argmax_a∈A Q^π(s, a)

(Equation: Greedy Policy Improvement using Q-function)

The Problem of Exploration:

A major challenge with greedy policy improvement in Monte Carlo control is exploration. If we always act greedily based on our current Q-value estimates, we might get stuck in a suboptimal policy. We need to explore other actions, especially in the early stages of learning, to discover better strategies.

ε-greedy Exploration:

A simple and effective way to encourage exploration is to use an ε-greedy policy.

• With probability 1 - ε (e.g., 90%), choose the greedy action (action with the highest estimated Q-value): a_greedy = argmax_a∈A Q(s, a).
• With probability ε (e.g., 10%), choose an action randomly from all available actions (uniform distribution).

(Diagram: ε-greedy action selection)

                                    /--- Greedy Action (argmax Q(s,a))   (Probability 1 - ε)
Current State (s)  --->  ε-greedy Policy  ---
                                    \--- Random Action (from all actions) (Probability ε)

By using an ε-greedy policy, we ensure that the agent explores different actions with some probability, while still exploiting its current knowledge by choosing greedy actions most of the time. As learning progresses, we can gradually decrease ε over time (e.g., from 0.1 to 0.01 to 0.001, etc.) to reduce exploration and focus more on exploitation.

On-Policy Monte Carlo Control (for ε-greedy policies):

Putting it all together, we get the On-Policy Monte Carlo Control algorithm for ε-greedy policies. It's called "on-policy" because we evaluate and improve the same policy that is used to generate episodes (the ε-greedy policy).

Algorithm: On-Policy Monte Carlo Control (for ε-greedy)

Algorithm: On-Policy Monte Carlo Control (for ε-greedy)

Input: MDP environment (for generating episodes), small ε > 0
Output: Optimal policy π<sub>*</sub> and optimal action value function Q<sub>*</sub> (approximations)

Initialize:
    Q(s, a) = 0 for all s ∈ S, a ∈ A  (Action value estimates)
    Returns(s, a) = empty list for all s ∈ S, a ∈ A (List to store returns for each state-action pair)
    π(s) = ε-greedy policy based on Q(s, a) for all s ∈ S (Initial policy, e.g., random policy)

Loop (for each episode):
    Generate an episode using policy π:  S<sub>0</sub>, A<sub>0</sub>, R<sub>1</sub>, S<sub>1</sub>, A<sub>1</sub>, R<sub>2</sub>, S<sub>2</sub>, ..., S<sub>T</sub>
    State_Action_Pairs_in_episode = list of (state, action) pairs visited in the episode
    For each (state s, action a) in State_Action_Pairs_in_episode:
        If (s, a) is the first visit in the episode:
            Find the return G for the episode starting from the first visit to (s, a)
            Append G to Returns(s, a)
            Q(s, a) = average(Returns(s, a))

    Policy Improvement:
    For each state s ∈ S:
        a<sub>greedy</sub> = argmax<sub>a∈A</sub> Q(s, a)
        For each action a ∈ A:
            If a = a<sub>greedy</sub>:
                π(a|s) = 1 - ε + ε/|A(s)|  (Probability for greedy action)
            Else:
                π(a|s) = ε/|A(s)|         (Probability for other actions)

Return: π (Optimal policy approximation) and Q (Optimal action value function approximation Q<sub>*</sub>)

5. Exploration vs. Exploitation in Monte Carlo Methods (Revisited)

• Essential Trade-off: Exploration vs. exploitation is a fundamental dilemma in Reinforcement Learning. We need to explore the environment to discover good actions and policies, but we also need to exploit our current knowledge to maximize rewards.
• ε-greedy as a Simple Exploration Strategy: ε-greedy is a basic but effective way to balance exploration and exploitation. It ensures some level of exploration by randomly choosing actions with probability ε, while primarily exploiting the best-known actions.
• Importance of Sufficient Exploration: For Monte Carlo control (and RL in general) to find optimal policies, it's crucial to have sufficient exploration, especially in the early stages of learning. Without enough exploration, the agent might converge to a suboptimal policy.
• Other Exploration Strategies: Besides ε-greedy, there are more sophisticated exploration strategies, such as Upper Confidence Bound (UCB), Thompson Sampling, and others, which can be more efficient in certain scenarios. We might explore some of these later.

6. Limitations and Advantages of Monte Carlo Methods (Summary)

Advantages of Monte Carlo Methods:

• Model-Free: Don't require a model of the environment (transition probabilities, reward function).
• Learn Directly from Experience: Can learn from actual interaction with the environment or from simulated episodes.
• Conceptually Simple and Easy to Implement: Straightforward algorithms.
• Can be Used for Simulation or Real-World Problems: Flexible in terms of application.
• Less Sensitive to Markov Assumption Violation: Can work reasonably well even if the Markov property is not strictly satisfied (though performance may degrade).

Limitations of Monte Carlo Methods:

• Only for Episodic Tasks (in basic form): Requires complete episodes. Not directly applicable to continuing tasks without modifications.
• High Variance: Returns can be noisy, leading to high variance in value function estimates. This can slow down learning and require many episodes to converge.
• Inefficient: Can be slow, especially for long episodes or when rewards are sparse and infrequent.
• Requires Episodes to Terminate: Need to wait until the end of an episode to update value functions. Cannot learn online or in real-time within an episode.

When to Use Monte Carlo Methods:

Monte Carlo methods are suitable when:

• The problem is naturally episodic (games, tasks with clear termination).
• A model of the environment is unavailable or difficult to obtain.
• You can generate or have access to episodes of experience (real or simulated).
• You can tolerate high variance and potentially slower learning.

What's Next?

In the next chapter, we'll explore Temporal Difference (TD) Learning. TD learning is another class of model-free RL methods, but unlike Monte Carlo methods, TD learning can learn from incomplete episodes and can be applied to both episodic and continuing tasks. TD learning is a cornerstone of modern Reinforcement Learning and offers a powerful and more efficient way to learn from experience. We will see how TD learning overcomes some of the limitations of Monte Carlo methods.