Module 4
Model-Free Prediction & Control
Content
• Monte Carlo Methods & Monte Carlo prediction,
• First-visit vs every-visit MC,
• Monte Carlo control,
• Exploring Starts, Off-policy MC & importance sampling,
• Temporal Difference Methods: TD(0) prediction,
• SARSA (on-policy control),
• Qlearning (off-policy control),
• Expected SARSA, Advanced TD
• Methods, n-step bootstrapping,
• Eligibility traces
Model-Free Learning in Reinforcement
Learning
• Problem in Markov Decision Process (MDP):
• Transition probabilities are known
• Reward function is known
• But what if Transition probabilities and Rewards are not know
• Environment dynamics are unknown.
• Then use Model Free Learning
• No knowledge of environment dynamics
• Learns through interaction with environment
• Does not require:
• Transition probabilities
• Reward model
Model-Free Learning in Reinforcement
Learning
• We learn directly from experience:
Observe: State, Action, Reward, & Update: Value function
• Goal here is to Estimate Value Function V(s) even when MDP
is unknown and assume policy is given.
• To solve this issue two approaches:
• Monte Carlo Method - Learns from complete episodes
• Temporal Difference Method- Learns step-by-step (bootstrapping)
• No model required, learning is based on trial and error and it
works in real-world unknown environments
Model-Free Prediction & Control
• Monte Carlo methods learn directly from episodes of experience.
• An “episode” is a series of states, actions, and rewards that ends in
a terminal state, just like a day of weather.
• Model-free methods do NOT require knowledge of environment
dynamics
• No transition probabilities
• No reward function model
• Learns directly from interaction.
• Agent learns by:
• Trial and error
• Observing rewards
Aspect MDP (Markov Decision Process) Monte Carlo Method
Mathematical framework for
Definition Learning method used in RL
decision-making
Type Model-based concept Model-free technique
Requires full environment model
Knowledge Required No knowledge of model required
(transition probabilities, rewards)
Solves the problem
Purpose Defines the problem
(prediction/control)
States, actions, transition
Input Episodes of experience
probabilities, rewards
Learning Style Planning using known model Learning from experience
Dependency Depends on environment dynamics Independent of environment model
Update Method Uses Bellman equations Uses average of returns
Timing of Learning Can compute without interaction Requires full episode completion
Learning value of states from
Example Gridworld with known probabilities
gameplay
Monte Carlo (MC)
• The Monte Carlo (MC) method in reinforcement learning is a
technique used to estimate value functions and learn optimal
policies based on complete episodes of experience.
• It learns from actual rewards obtained after the episode ends, rather
than predicting step-by-step.
• Monte Carlo methods:
• Wait until the end of an episode
• Compute the total return (cumulative reward)
• Use this return to update value estimates
Learning is based on real outcomes, not approximations.
Monte Carlo
• Monte Carlo computes return (G) using:
Experience-based learning and goal is to estimate value function of a policy
Monte Carlo Example
Suppose an agent moves through states and receives rewards only at the
end.
State A → State B → State C → Terminal
Rewards: 0 0 +10
Step 1: Calculate Return
Using Monte Carlo, we wait until the episode ends and then compute
return G:
From State C: G=10
From State B: G=0+10=10
From State A: G=0+0+10=10
Monte Carlo Example
• Step 2: Update Value Function
State Return (G) Updated Value V(s)
A 10 10
B 10 10
C 10 10
• Step 3: Second Episode (When the agent reaches State C, it receives a reward
of +6 (instead of +10 in the first episode))
State A → State B → State C → Terminal
Rewards: 0 0 +6
Monte Carlo Example
Updated Values (Average):
State Previous New Return Updated V(s)
A 10 6 (10+6)/2 = 8
B 10 6 8
C 10 6 8
Monte Carlo funs full episode, calculate total reward, & updates values
by averaging returns from multiple episodes
Points to remember
• Monte Carlo learning is based on multiple episodes, and:
• Each episode can have different rewards
• These differences may occur due to:
• Environment randomness
• Different actions taken
• Noise or uncertainty
• Monte Carlo uses real observed rewards from each episode
• Different episodes have different rewards therefore better learning
through averaging.
Q&A
• Are rewards given by the environment????
• Does Monte Carlo Calculate reward???
• Does it uses reward only to compute returns???
• Are reward created by MC or it is simply observed reward???
Monte Carlo Prediction
• Monte Carlo Prediction is a method used to estimate the value
function V(s) of a given policy by averaging returns from complete
episodes.
Generate episodes using a policy
Calculate return 𝐺G for each state
Update value as the average of returns
• Temporal Difference Methods: TD(0) prediction, SARSA (on-policy
control) , Q Learning (off-policy control)
• Advanced TD Methods
• n-step bootstrapping
• Eligibility traces TD(λ).
Introduction to Temporal Difference Learning
• TD Learning is a combination of:
• Monte Carlo (MC) → learns from complete episodes
• Dynamic Programming (DP) → uses bootstrapping
• Learn directly from raw experience without a model. TD does not
require a model of the environment
• Learning happens step-by-step during interaction.
• Temporal Difference (TD) Learning is a model-free reinforcement
learning method used by algorithms like Q-learning to iteratively learn
state value functions (V(s)) or state-action value functions (Q(s,a))
How TD Learning Combines Monte Carlo and
Dynamic Programming
• Monte Carlo (MC)
• Learns from actual returns after full episodes.
• Update happens only at the end.
• Model-free, but:
• High variance
• Not suitable for continuing tasks
• Dynamic Programming (DP)
• Learns using a known model of environment.
• Uses bootstrapping (updates based on estimated values).
• Updates can happen at every step, but:
• Requires transition probabilities and rewards
Temporal Difference (TD)
• It learn by updating estimates using Current reward & Estimated future value.
• TD Update Rule
Where:
• V(s): Value of current state
• r: Immediate reward
• γ: Discount factor
• s′: Next state
• α: Learning rate
• V(s`): Current estimate of next state’s value (this is bootstrapping: itself an estimate)
• Bootstrapping in RL means learning from estimates of future returns instead of waiting for
actual returns
TD Error
• Measures difference between: Predicted value vs Actual observed
value.
• Helps in correcting predictions.
Where Bootstrapping is Used?
• Temporal Difference (TD) Learning (e.g., TD(0))
• SARSA
• Q-Learning
• Actor-Critic methods
Feature Bootstrapping (TD) Monte Carlo
Update timing After each step After full episode
Uses estimates? ✅ Yes ❌ No
Speed Faster Slower
Variance Lower Higher
Bias Higher Lower
Features of TD Learning
• Model-free (no need for transition probabilities)
• Learns online (step-by-step updates)
• Uses bootstrapping (
• Works in both episodic and continuing tasks
TD(0) Prediction
• Simplest TD method
• Updates value after each step
Why TD is Powerful?
• Learns Step-by-Step: No need to wait until episode ends
(unlike MC)
• Works in Continuing Tasks: Suitable for real-world problems
like robotics, trading, etc.
• Lower Variance than MC: Uses estimates instead of full
returns
• No Model Needed (Unlike DP): Practical for unknown
environments
Remember..
• MC: Wait till the end, then learn from the full story.
• DP: Use the model to predict everything.
• TD: Learn on the go using partial information.
• TD makes a prediction, checks it against the next step
outcome, and corrects itself immediately.
SARSA (On-Policy Control)
• State-Action-Reward-State-Action
• On-policy method → learns value of the policy being followed
• Updates Q-values using current action
• Where
• Q(St,At): Current estimate of the action-value (expected return) for taking action At in state St
• Rt+1: The immediate reward received after taking action 𝐴𝑡
• Q(St+1,At+1): The estimated value of the next state-action pair following the current policy.
• [Rt+1+γQ(St+1,At+1)]: Called the TD Target an estimate of the return.
• [Rt+1+γQ(St+1,At+1)−Q(St,At)]: Called the TD Error → measures how wrong the current estimate
is.
SARSA Algorithm
• Initialize 𝑄(𝑠,𝑎)
• Choose action using policy (e.g., ε-greedy)
• For each step:
• Take action 𝐴, observe R,S′
• Choose next action A′
• Update:
SARSA Characteristics
• On-policy → follows exploration strategy
• Safer learning (accounts for exploration)
• Slower convergence than Q-learning
• Example:
• Uses ε-greedy policy
• If agent explores, its update includes that exploratory action
• Leads to more cautious policy
Q-Learning (Off-Policy Control)
• Off-policy method
• Learns optimal policy regardless of current behavior
• Uses greedy action for update