Module 2
CSE3011 Reinforcement Learning
Credit Structure : 2-2-3
Module 2 : Monte-Carlo (MC) methods
Topics : Monte Carlo methods, prediction and control tasks, Monte Carlo
prediction: algorithm, types of MC prediction, examples, incremental mean
updates, Monte Carlo Control: algorithm, on-policy MC control, MC with
epsilon-greedy policy, off-policy MC control. Limitations of MC method.
2
• LO1 : Understand MC method
• LO2 : Understand 2 types of RL tasks : prediction and control
• LO3 : Understand the advantages of MC over DP methods
• LO4: Understand the different types of MC prediction
• LO5: Apply MC prediction to train an agent to play the blackjack
game
• LO6: Understand the different types of MC control
• LO7: Apply MC control to train an agent to play the blackjack game
Introduction
• Model-free methods do not require the model dynamics of the
environment to compute the value and Q functions in order to find
the optimal policy.
• One such popular model-free method is the Monte Carlo (MC)
method.
• The Monte Carlo method is a statistical technique used to find an
approximate solution through sampling.
Introduction
• For instance, the Monte Carlo method approximates the
expectation of a random variable by sampling, and when the
sample size is greater, the approximation will be better.
• Let's suppose we have a random variable X and say we need to
compute the expected value of X; that is E(X), then we can
compute it by taking the sum of the values of X multiplied by their
respective probabilities as follows:
Introduction
• MC method, estimates the expected value of X by just sampling the
values of X for some N times and compute the average value of X as
the expected value of X as follows:
• When N is larger the approximation will be better.
• Thus, with the Monte Carlo method, we can approximate the
solution through sampling and our approximation will be better
when the sample size is large.
Introduction
In reinforcement learning, we perform two important tasks, and
they are:
• The prediction task
• The control task
Prediction Task
• The prediction tasks, take a policy 𝜋 as an input and evaluate
this policy, i,e to determine whether the policy is good or bad.
• If the agent obtains a good return using the given policy then we
can say that the policy is good.
• Thus, to evaluate the given policy, we need to understand what is
the return the agent would obtain if it uses the given policy.
• To obtain the return, we predict the value function or Q
function using the given policy.
• Hence, the policy is evaluated by predicting the value function or Q
function using the given policy.
• The value function of a state gives the expected return starting
from state s following the policy π.
• So, by predicting the value function following the policy π, we can
understand what is the expected return the agent will obtain in
each state if it uses the given policy π.
• If the return is good then the policy π is also good.
• The Q function of a state-action pair gives the expected return
starting from state s and an action a following the policy π.
• So, by predicting the Q-function by following the policy π, we can
understand what is the expected return the agent will obtain in
each state-action pair if it uses the given policy π.
• If the return is good then the policy π is also good.
• Prediction methods do not change the given policy.
Control Task
• Unlike the prediction task, in the control task, we will not be given
any policy as an input. In the control task, our goal is to find the
optimal policy.
• So, we will start off by initializing a random policy and we try to
find the optimal policy iteratively.
• That is, we try to find an optimal policy that gives the maximum
return.
Monte Carlo Prediction
• First, let's recap the definition of the value function of a state,
• The value function or the value of the state s is the expected return
the agent would obtain starting from the state s and following the
policy 𝜋.
• It can be expressed as:
Monte Carlo Prediction
• But, in the Monte Carlo prediction method, the value of a state is
calculated by sampling the episodes(trajectories) following the
input policy π for N times.
• take the average return of a state across the sampled N episodes
instead of taking the expected return.
Grid world environment example
Our goal is to reach the state I from
the state A without visiting the
shaded states, and the agent
receives +1 reward when it visits
the unshaded states and -1 reward
when it visits the shaded states:
Grid world environment example
• Let's say we have a stochastic policy 𝜋. Let's suppose, in state A, our
stochastic policy 𝜋 selects action down 80% of time and action
right 20% of the time, and it selects action right in states D and E
and action down in states B and F 100% of the time.
• First, we generate an episode 𝜏1 using our given stochastic
policy 𝜋 as Figure shows:
Grid world environment example
Grid world environment example
Grid world environment example
Grid world environment example
The value of a state can be approximated by computing the average
return of the state across some N episodes (trajectories):
Monte Carlo Prediction
• In the Monte Carlo prediction method, to predict the value of a
state (value function) using the given input policy 𝜋,
• we generate some N episodes using the given policy and
• then we compute the value of a state as the average return of the state
across these N episodes.
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
MC prediction algorithm
Types of MC prediction
• First-visit Monte Carlo
• Every-visit Monte Carlo
First-visit Monte Carlo
• In the first-visit Monte Carlo method, if the same state is visited
again in the same episode, we don't compute the return for that
state again.
• For example, consider a case where an agent is playing snake and
ladder. If the agent lands on a snake, then there is a good chance
that the agent will return to a state that it had visited earlier.
• So, when the agent revisits the same state, we don't compute the
return for that state for the second time.
First-visit Monte Carlo Algorithm
First-visit Monte Carlo Algorithm
Every-visit Monte Carlo Algorithm
Here, we compute the return every time a state is visited in the
episode.
The algorithm of every-visit Monte Carlo is the same as the one we
saw earlier at the beginning of this section and it is as follows:
1. Let total_return(s) be the sum of the return of a state across
several episodes and N(s) be the counter, that is, the number of
times a state is visited across several episodes. Initialize
total_return(s) and N(s) as zero for all the states. The policy 𝜋 is
given as input
Every-visit Monte Carlo Algorithm
Remember that the only difference between the first-visit MC
and every-visit MC methods is that in the first-visit MC method,
we compute the return for a state only for its first time of
occurrence in the episode but in the every-visit MC method, the
return of the state is computed every time the state is visited in an
episode.
Blackjack game with MC prediction
• Blackjack also known as 21 is a popular card game.
• It has a player and a dealer.
• Goal of the player is
• to have a collection of cards that sum upto 21
or
• Have a larger value than the sum of the dealer’s cards but not exceeding
21.
• If one of the above two criteria is true, then the player ‘wins’ or the
dealer ‘wins’.
• Value of cards J, K, and Q is 10.
• Value of Ace can be 1 or 11, depending on the player’s choice
during the game.
• Value of rest of the cards is their face value, ex, value of card 2 is 2
• There can be many players at a time but only one dealer.
• All players compete with only the dealer, not within them.
• Consider a case with one player(which is ourself) and one dealer.
• Player performs one of the actions :
• hit --- get one more card.
• Stand ---- don’t need any more cards, but request the dealer to show their
cards.
• Initially both player and dealer are given 2 cards
• Both cards of the player are face up (visible to the dealer)
• Only one of the dealer’s card is face up (visible to the player) and
the other is face down.
• Let’s see the different cases of the game :
• The player wins
• The player loses
• The player goes bust
• Usable ace
• Non-usable ace
Different cases of the game
• Case 1: when the player wins the game
• The player’s
card value is
already large
20,
• Hence the
player ‘stands’
• The player’s sum is greater than
the dealer’s and also doesn’t
exceed 21, hence the player wins.
• Case 2: when the player loses the game
•
• Assume the
player is
optimistic that
the dealer’s
value cannot
exceed 13,
• Hence the
player ‘stands’
• The dealer’s value is greater
then the player’s value but
doesn’t exceed 21.
• Hence the player loses
• Assume the new card is 10
• Case 3: when the player goes bust • Now the player’s value is 18
• If the player again performs
‘hit’ greedily to get a new card,
• Assume the next card is a Q
• Players total value is only 8.
• Hence the player performs
‘hit’ to get a new card.
• The player’s sum is now 28, which
exceeds 21.
• This is a bust and the player
losses.
• Case 4: Usable Ace:
• Player performs ‘hit’
• Gets an Ace
• Decides the value of
the Ace as 11
• Case 5: Unusable Ace
• Player performs
‘hit’
• Gets an Ace
• Player has to
use the value of
the Ace as 1
• Player performs
‘stand’
• Dealer’s second
card face up.
Assume it is K
• So player loses
• Case 6: game is a draw
If both the player and the dealer's sum of cards value is the same,
say 20, then the game is called a draw.
Incremental mean updates
• In both first-visit MC and every-visit MC, we estimate the value of a
state as an average (arithmetic mean) return of the state across
several episodes as shown as follows:
Incremental mean updates
• Instead of using the arithmetic mean to approximate the value of
the state, we can also use the incremental mean, and it is
expressed as:
Incremental mean updates
• Consider our environment as non-stationary. In that case, we don't
have to take the return of the state from all the episodes and
compute the average.
• As the environment is non-stationary we can ignore returns from
earlier episodes and use only the returns from the latest episodes
for computing the average. Thus, we can compute the value of the
state using the incremental mean as shown as follows:
Incremental mean updates
MC prediction (Q function)
• We generate several episodes using the given policy 𝜋,
• Then, we calculate the total_return(s, a), the sum of the return of
the state-action pair across several episodes.
• We calculate N(s, a), the number of times the state-action pair is
visited across several episodes.
• Then we compute the Q function or Q value as the average return
of the state-action pair as shown as follows:
MC prediction (Q function)
Say we have two states s0 and s1 and we have two possible actions
0 and 1.
Now, we compute total_return(s, a) and N(s, a).
Let's say our table after computation looks like Table 4.4:
MC prediction (Q function)
• Thus, we can compute the Q value for all state-action pairs as:
MC prediction (Q function) algorithm
The algorithm for predicting the Q function using the Monte Carlo
method is as follows.
1. Let total_return(s, a) be the sum of the return of a state-action
pair across several episodes and N(s, a) be the number of times a
state-action pair is visited across several episodes.
Initialize total_return(s, a) and N(s, a) for all state-action pairs to
zero.
The policy 𝜋 is given as input
MC prediction (Q function) algorithm
MC prediction of the Q function
• We have two types of MC— first-visit MC and every-visit MC.
• In first-visit MC, we compute the return of the state-action pair
only for the first time the state-action pair is visited in the episode
• In every-visit MC we compute the return of the state-action pair
every time the state-action pair is visited in the episode.
Incremental mean
We can compute the Q value using the incremental mean as shown
as follows:
Monte Carlo control
• In the control task, our goal is to find the optimal policy.
• Unlike the prediction task, here, we will not be given any policy as
an input.
• we will begin by initializing a random policy, and then we try to
find the optimal policy iteratively.
• An optimal policy is that which gives the maximum return.
• if we have a Q function, then we can extract policy by selecting an
action in each state that has the maximum Q value as the following
shows:
• From the new Q function, we extract a new policy. We repeat these
steps iteratively until we find the optimal policy.
Monte Carlo control
• Iteration 1: Let be the random policy
• Step 1.1 : Use to generate an episode
Step 1.2 : Find by taking the average return of the state-action pair.
Step 1.3: From extract a new policy . This will not be an optimal policy.
Hence need one more iteration.
• Iteration 2: Use the new policy , got from the previous iteration.
Step 1.1 : Use to generate an episode
Step 1.2 : Find by taking the average return of the state-action pair.
Step 1.3: From extract a new policy . If this policy is optimal, then stop,
else, generate one more iteration.
Monte Carlo control
MC control algorithm
• Once we have the Q function, we extract a new policy by selecting
an action in each state that has the maximum Q value.
• In the next iteration, we use the extracted new policy to generate
an episode and compute the new Q function (Q value) as the
average return of the state-action pair.
• We repeat these steps for many iterations to find the optimal
policy.
MC control algorithm
• One more thing, we need to observe that just as we learned in the
first-visit MC prediction method, here,
• we compute the return of the state-action pair only for the first
time a state-action pair is visited in the episode
MC control algorithmic steps
MC control algorithmic steps
5. If this new policy is optimal, then stop. Else repeat step 2,3 and 4 using this new
policy.
MC Control methods
• On-policy control—In the on-policy control method, the agent
behaves using one policy and also tries to improve that same
policy.
• That is, we generate episodes using one policy and also improve
the same policy iteratively to find the optimal policy.
• For instance, the MC control method, which we just learned above,
can be called on-policy MC control as we are generating episodes
using a policy 𝜋, and we also try to improve the same policy 𝜋 on
every iteration to compute the optimal policy.
MC Control methods
• Off-policy control—In the off-policy control method, the agent
behaves using one policy and tries to improve a different policy 𝜋.
• That is, in the off-policy method, we generate episodes using one
policy and we try to improve the different policy iteratively to find
the optimal policy.
on-policy Monte Carlo control
There are two types of on-policy Monte Carlo control methods:
• Monte Carlo exploring starts
• Monte Carlo with the epsilon-greedy policy
Monte Carlo with the epsilon-greedy policy
• So, now the question is whether the agent should explore all the
other actions in the state and select the best action as the one that
has the maximum Q value
or
• exploit the best action out of already-explored actions. This is
called an exploration-exploitation dilemma.
• The agent must decide whether to exploit the current best-known
policy or explore new policies to improve its performance
Exploration-Exploitation dilemma
• The exploration-exploitation dilemma is a problem that can be
encountered in most of the data driven decision making process
when there exists some kind of feedback loop between data
gathering and decisions making
• They are two possible behaviors when facing a decision making
problem that both have pros and cons.
• exploitation consists of taking the decision assumed to be
optimal with respect to the data observed so far.
• This « safe » approach tries to avoid bad decisions as much as
possible but also prevents from discovering potential better
decisions.
• exploration consists of not taking the decision that seems to
be optimal, based on the fact that observed data are not
sufficient to truly identify the best option.
• This is a more « risky » approach and can sometimes lead to poor
decisions
• but also makes it possible to discover better ones, if there exists
any.
Examples
• restaurant selection: going to your favourite restaurant
(exploitation) or trying an unknown restaurant (exploration)
• movies recommendation: recommending the user’s best rated
movie type (exploitation) or trying another movie type
(exploration)
• oil drilling: drilling at the best known location (exploitation) or
trying a new location (exploration)
• clinical trials: using the best known treatment (exploitation) or
trying a new experimental one (exploration)
Monte Carlo with the epsilon-greedy policy
• To avoid this dilemma, we introduce a new policy called the
epsilon-greedy policy.
• Here, all actions are tried with a non-zero probability (epsilon).
With a probability epsilon, we explore different actions randomly
and with a probability 1-epsilon, we choose an action that has the
maximum Q value.
• That is, with a probability epsilon, we select a random action
(exploration) and with a probability 1-epsilon we select the best
action (exploitation).
Monte Carlo with the epsilon-greedy policy
• In the epsilon-greedy policy, if we set the value of epsilon to 0, then
it becomes a greedy policy (only exploitation).
• when we set the value of epsilon to 1, then we will always end up
doing only the exploration.
• So, the value of epsilon has to be chosen optimally between 0 and
1.
Monte Carlo with the epsilon-greedy policy
• Say we set epsilon = 0.5; then we will generate a random number
from the uniform distribution and if the random number is less
than epsilon (0.5), then we select a random action (exploration).
• if the random number is greater than or equal to epsilon then we
select the best action, that is, the action that has the maximum Q
value (exploitation).
Monte Carlo with the epsilon-greedy policy
MC control algorithm with the epsilon-greedy policy
MC control algorithm with the epsilon-greedy policy
MC control algorithm with the epsilon-greedy policy
policy 𝜋 and also we try to improve the same policy 𝜋 in every iteration
As we can observe, in every iteration, we generate the episode using the
to compute the optimal policy.
Off-policy Monte Carlo control
• Off-policy Monte Carlo is another interesting Monte Carlo control
method. In the off-policy method, we use two policies called the
behavior policy and the target policy. As the name suggests, we
behave (generate episodes) using the behavior policy and we try
to improve the other policy called the target policy.
Off-policy Monte Carlo control
In the on-policy method, we generate an episode using the policy 𝜋
and we improve the same policy 𝜋 iteratively to find the optimal
policy.
But in the off-policy method, we generate an episode using a policy
called the behavior policy b and we try to iteratively improve a
different policy called the target policy 𝜋.
Off-policy Monte Carlo control algorithm
Off-policy Monte Carlo control algorithm
MC limitation
• Issue with the Monte Carlo method is that it is applicable only to
episodic tasks. We learned that in the Monte Carlo method, we
compute the value of the state by taking the average return of the
state and the return is the sum of rewards of the episode.
• But when there is no episode, that is, if our task is a continuous
task (non-episodic task), then we cannot apply the Monte Carlo
method.