Dynamic Programming (DP)

1. Introduction
Dynamic Programming is a method used to solve complex problems by breaking them
into smaller subproblems and solving each subproblem only once.
In Reinforcement Learning, DP is used to compute optimal policies and value functions
when the model of the environment is known.
REIFORCEMENT LEARNING
DP is mainly used in Markov Decision Processes (MDP).
2. Markov Decision Process (MDP)
Dynamic Programming works on Markov Decision Processes.
An MDP consists of:
1. States (S) – possible situations of the agent
2. Actions (A) – choices available to the agent
3. Transition probability (P) – probability of moving to the next state
4. Reward (R) – feedback received after taking an action
5. Policy (π) – strategy followed by the agent
Goal:
Find an optimal policy π* that maximizes expected reward.

3. Bellman Equation
Dynamic Programming is based on the Bellman Equation.
The Bellman equation expresses the value of a state in terms of future values.
State Value Function
V π (s)=∑ π (a ∣ s) ∑ P(¿ s , r ∣ s , a)[r+ γ V π (s )]¿
' '
'
a s ,r

Where:
 V π (s)= value of state
 γ = discount factor
 r = reward
'
 P(s , r ∣ s , a) = probability of next state and reward
This equation is the foundation of Dynamic Programming.

4. Key Dynamic Programming Methods

According to Sutton & Barto, DP mainly includes four methods:
REIFORCEMENT LEARNING
1. Policy Evaluation
2. Policy Improvement
3. Policy Iteration
4. Value Iteration
Policy Evaluation (Prediction)
Policy Evaluation is a Dynamic Programming method used to compute the value
function for a given policy. It determines how good a policy is by calculating the expected
return from each state when the agent follows that policy.
REIFORCEMENT LEARNING

1. Definition
Policy Evaluation estimates the state-value function V π (s)for a given policy π .
 State-value function represents the expected cumulative reward starting from state
sand following policy π .
V π (s)=E π [Gt ∣ S t=s ]
where
 V π (s)= value of state sunder policy π
 Gt = total expected future reward

2. Bellman Expectation Equation

Policy evaluation is based on the Bellman Expectation Equation.
V π ( s)=∑ π ( a ∣ s) ∑ P( ¿ s , r ∣ s , a)[r+ γ V π ( s )]¿
' '
'
a s ,r

Where
 π (a ∣ s)→ probability of selecting action a in state s
'
 P(s , r ∣ s , a) → probability of next state s' and reward r
 γ → discount factor (0 ≤ γ ≤ 1)
'
 V π (s )→ value of next state
This equation states that the value of a state equals the expected reward plus the
discounted value of the next state.
3. Iterative Policy Evaluation
Since the exact value is difficult to compute directly, iterative updates are used.
Initial value:
V 0 (s)=0
Update rule:
V k +1 (s )=∑ π (a ∣ s) ∑ P(¿ s ,r ∣ s , a)[r + γ V k ( s )]¿
' '
'
a s ,r

The process continues until the values converge.

4. Algorithm Steps
1. Initialize V (s)arbitrarily for all states.
2. Repeat:
o For each state s:
V ( s) ← ∑ π ( a ∣s ) ∑ P( ¿ s , r ∣s , a)[r + γV (s )]¿
' '
'
a s ,r

3. Stop when the change in value becomes very small.

Result: Value function for the given policy.

5. Simple Example
Consider a grid-world environment.
If the policy always moves right, policy evaluation calculates:
 Expected rewards
 Value of each state
After several iterations, each state receives a value representing its long-term reward.

6. Characteristics
 Used when the policy is fixed
 Computes state values
 Requires a complete model of the environment
 Works on Markov Decision Processes (MDP)

7. Role in Dynamic Programming

Policy Evaluation is the first step of Policy Iteration.
Process:
Policy Evaluation → Policy Improvement → Optimal Policy
This iterative interaction eventually produces the optimal policy.
REIFORCEMENT LEARNING

8. Advantages
 Accurate estimation of state values
 Converges to correct value function
 Foundation for many RL algorithms

9. Limitations
 Requires knowledge of transition probabilities
 Computationally expensive for large state spaces
Policy Improvement
Policy Improvement is a Dynamic Programming method used to improve an existing
policy by choosing better actions based on the current value function. It updates the
policy so that it yields higher expected rewards.

1. Definition
Policy Improvement is the process of modifying a policy to obtain a better policy using the
value function obtained from Policy Evaluation.
Idea:
If the current policy is not optimal, we can choose actions that lead to higher value states.

2. Basic Idea
Suppose we already computed the state value function V π (s).
Now we select the action that maximizes the expected return.
π (s )=arg ⁡max ⁡∑ P(¿ s , r ∣ s , a) [r + γ V π ( s )]¿
' ' '

a s ' ,r

Where:
'
 π (s )= improved policy
'
 P(s , r ∣ s , a) = transition probability
 r = reward
  γ = discount factor
This means:
Choose the action that gives the maximum expected reward.

3. Policy Improvement Theorem

The Policy Improvement Theorem states:
If for every state
'
Q π (s , π ( s))≥ V π (s)
then the new policy π ' is better than or equal to the old policy π .
REIFORCEMENT LEARNING
This guarantees that policy improvement always produces a better or equal policy.

4. Algorithm Steps
1. Start with policy π
2. Perform Policy Evaluation to compute V π (s)
3. Improve policy using greedy method
'
π (s )=arg ⁡max ⁡Qπ (s , a)
a

4. If policy changes → repeat evaluation

5. If policy does not change → optimal policy reached

5. Greedy Policy Improvement

A greedy policy selects the action with the highest value.
'
π (s )=arg ⁡max ⁡Q π (s , a)
a

This is called greedy improvement.

6. Example
Consider a grid environment.
Current policy:
Move randomly.
After policy evaluation we obtain state values.
Now we choose the direction with highest value:
Example:
State Best Action
S1 Right
S2 Up
S3 Left
Thus a new improved policy is created.

7. Policy Improvement in Dynamic Programming

Policy Improvement is used together with Policy Evaluation.
The process is called Policy Iteration.
Steps:
1. Evaluate policy
2. Improve policy
3. Repeat
¿
Eventually the algorithm converges to optimal policy π .

8. Advantages
 Improves policy systematically
 Guarantees better policy
 Converges to optimal solution

9. Limitations
 Requires environment model
 Computationally expensive for large state spaces
Policy Iteration
Policy Iteration is a Dynamic Programming algorithm used to find the optimal policy in a
Markov Decision Process (MDP).
It works by alternating between Policy Evaluation and Policy Improvement until the
policy becomes optimal.

1. Definition
Policy Iteration is a method that repeatedly evaluates a policy and improves it until no
further improvement is possible.
 ¿
The result is the optimal policy π .

2. Main Idea
Policy Iteration consists of two main steps:
1. Policy Evaluation
Compute the value function for the current policy.
2. Policy Improvement
Update the policy by choosing actions that maximize expected rewards.
These two steps are repeated until the policy stops changing.

3. Policy Iteration Algorithm

Step 1: Initialize Policy
Choose an arbitrary policy π .

Step 2: Policy Evaluation

Calculate the value function V π (s):

V π ( s)=∑ π ( a ∣ s) ∑ P( ¿ s , r ∣ s , a)[r+ γ V π ( s )]¿

' '
'
a s ,r

Repeat until the value function converges.

Step 3: Policy Improvement

Update the policy using:
π (s )=arg ⁡max ⁡∑ P(¿ s , r ∣ s , a)[r + γ V π (s )]¿
' ' '
a s ,r
'

This selects the best action for each state.

Step 4: Check Convergence

 If π ' =π → Optimal policy found
 Otherwise → Set π=π ' and repeat the process

4. Pseudocode
5. Example
Consider a grid world problem.
Initial policy:
Move randomly.
After policy evaluation, we obtain state values.
Policy improvement selects the best direction:
State Best Action
S1 Right
S2 Up
S3 Left
The process repeats until the best policy is obtained.

6. Characteristics
 Works with Markov Decision Processes
 Requires complete knowledge of the environment
 Guarantees optimal solution

7. Advantages
✔ Finds optimal policy
✔ Guaranteed convergence
✔ Conceptually simple
8. Limitations
✖ High computational cost
✖ Requires model of environment
✖ Not suitable for very large state spaces

9. Relationship with Other Methods

Method Purpose
Policy Evaluation Computes value of policy
Policy Improvement Updates policy
Policy Iteration Combines both steps
Value Iteration Faster version of policy iteration
Value Iteration
Value Iteration is a Dynamic Programming algorithm used to compute the optimal value
function and optimal policy in a Markov Decision Process (MDP). It simplifies policy
iteration by combining policy evaluation and policy improvement into a single step.

1. Definition
Value Iteration is an algorithm that iteratively updates the value of each state using the
Bellman Optimality Equation until the optimal value function is obtained.
Once the optimal value function is known, the optimal policy can be derived easily.

2. Bellman Optimality Equation

Value Iteration is based on the Bellman Optimality Equation.
V k +1 (s )=max ⁡∑ P(¿ s ,r ∣ s , a)[r + γ V k ( s )]¿
' '

a s' , r

Where:
 V (s)→ value of state
 a → action
'
 P(s , r ∣ s , a) → transition probability
 r → reward
 γ → discount factor
This equation selects the maximum expected reward over all actions.

3. Algorithm Steps
 1. Initialize value function for all states.
V (s)=0
2. Repeat for each state s:
V ( s)=max ⁡∑ P( ¿ s , r ∣ s , a)[r+ γV (s )]¿
' '

a s ' ,r

3. Continue updating until the change in values becomes very small.

4. Extract the optimal policy:
π (s)=arg ⁡max ⁡∑ P(¿ s ,r ∣ s , a)[r +γV ( s )]¿
¿ ' '
a s ,r'

4. Pseudocode

5. Example
Consider a grid world environment.
Steps:
1. Initialize state values.
2. Update values repeatedly using Bellman optimality.
3. Values gradually propagate from goal states.
Example result:
State Value
S1 10
S2 8
S3 6
Best actions are then selected for each state.

6. Difference Between Policy Iteration and Value Iteration

Feature Policy Iteration Value Iteration
Steps Two steps Single step
Policy evaluation Full evaluation Partial evaluation
Speed Slower Faster
Computation More iterations Fewer iterations

7. Advantages
✔ Faster than policy iteration
✔ Simple algorithm
✔ Guarantees optimal policy

8. Limitations
✖ Requires full model of environment
✖ High computational cost for large state spaces
Monte Carlo (MC) for Model-Free Prediction and Control
Monte Carlo methods are a class of reinforcement learning algorithms used to estimate
value functions and improve policies based on sampled experiences. Unlike Dynamic
Programming, MC methods do not require knowledge of the environment model, making
them model-free methods.

1. Model-Free Learning
In many real-world problems, the transition probabilities of the environment are
unknown.
Model-free methods learn directly from experience or episodes.
Monte Carlo methods estimate values by averaging the returns observed after visiting
states or taking actions.
REIFORCEMENT LEARNING

2. Key Idea of Monte Carlo Methods

Monte Carlo methods learn by sampling complete episodes.
An episode is a sequence:
S0 , A 0 , R 1 , S1 , A 1 , R2 , … , S T
The return Gt is the total future reward:
2
Gt =Rt +1 +γ R t+2 + γ Rt +3 +…
Monte Carlo methods estimate the value of a state by averaging these returns.

3. Monte Carlo Prediction

Monte Carlo prediction is used to estimate the value function for a given policy.
State Value Estimation
V (s)=average of returns following state s
Steps:
1. Generate episodes using policy π
2. Observe returns after visiting each state
3. Update value function using the average return

First-Visit Monte Carlo

Updates value only the first time a state appears in an episode.
Total returns from first visits
V (s)=
Number of first visits

Every-Visit Monte Carlo

Updates value every time the state appears in the episode.

4. Monte Carlo Control

Monte Carlo control is used to find the optimal policy.
It estimates action-value function Q(s , a)instead of state value.
Q(s , a)=average return after taking action a in state s

5. Exploring Starts Method

To ensure all state-action pairs are explored:
 Episodes start with random state-action pairs
Steps:
1. Initialize arbitrary policy
2. Generate episodes
 3. Estimate Q(s , a)
4. Improve policy greedily
π (s)=arg ⁡max ⁡Q(s , a)
a

6. ε-Greedy Policy (Practical Approach)

Instead of exploring starts, an ε-greedy strategy is used.
 With probability 1−ε → choose best action
 With probability ε → choose random action
This balances:
• Exploration
• Exploitation

7. Monte Carlo Control Algorithm

Steps:
1. Initialize Q(s , a)arbitrarily
2. Generate episode using ε-greedy policy
3. Calculate returns
4. Update action-value function
5. Improve policy
Repeat until policy converges.

8. Advantages of Monte Carlo Methods

✔ Model-free learning
✔ Easy to implement
✔ Works well for episodic tasks
✔ No need for transition probabilities

9. Limitations
✖ Requires complete episodes
✖ High variance in returns
✖ Slow learning in long episodes

10. Applications in AI/ML

Monte Carlo methods are used in:
  Game playing AI
 Robotics learning
 Recommendation systems
 Autonomous decision making
Monte Carlo Prediction
Monte Carlo Prediction is a reinforcement learning method used to estimate the value
function of a given policy by using sample episodes of experience. It is called model-free
because it does not require knowledge of the environment's transition probabilities or reward
function.

1. Definition
Monte Carlo Prediction is used to estimate the state-value function V π (s)for a given policy
π by averaging the returns observed after visiting each state.
V π (s)=E π [Gt ∣ S t=s ]
Where:
 V π (s)= value of state sunder policy π
 Gt = total future reward (return)

 St = state at time t

2. Return in Monte Carlo Methods

The return Gt is defined as the cumulative discounted reward:
2 T−t −1
Gt =Rt +1 +γ R t+2 + γ Rt +3 +⋯+γ RT
Where:
 R = reward received
 γ = discount factor (0 ≤ γ ≤ 1)
 T = terminal time step

3. Basic Idea
Monte Carlo methods learn from complete episodes.
Process:
1. Generate an episode using policy π
2. Observe the return after each state
3. Update the estimated value of that state
 4. Repeat for many episodes
The value of a state becomes the average return obtained from that state.

4. First-Visit Monte Carlo

In this method, the value of a state is updated only the first time the state appears in an
episode.
Sum of returns from first visits
V (s)=
Number of first visits
Advantages:
 Simple
 Less correlation in updates

5. Every-Visit Monte Carlo

In this approach, the value of a state is updated every time the state occurs in an episode.
Sum of returns from all visits
V (s)=
Number of visits
Advantages:
 Uses more data
 Faster learning in many cases

6. Monte Carlo Prediction Algorithm

1. Initialize V (s)arbitrarily.
2. Generate an episode following policy π .
3. For each state sin the episode:
o Calculate return Gt .
o Update value function.
V (s) ←V ( s)+α [Gt −V (s )]
Where:
 α = learning rate.

7. Example
Consider an agent moving in a grid world.
If the agent follows policy π and visits state s:
Episode returns observed:
Episode Return
1 5
2 7
3 6
Estimated value:
5+7+ 6
V (s)= =6
3
Thus the estimated value of state sis 6.

8. Advantages
 Model-free learning
 Easy to implement
 Works well in episodic tasks
 No need for transition probabilities

9. Limitations
 Requires complete episodes
 Learning can be slow
 High variance in returns
Monte Carlo Estimation of Action Values
Monte Carlo methods can be used to estimate action-value functions in reinforcement
learning. The action-value function represents the expected return obtained by taking a
specific action in a given state and following a policy thereafter.

1. Definition
The action-value function is denoted as:
Q π (s , a)
It represents the expected return when the agent takes action a in state sand follows
policy π afterward.
Q π (s , a)=E π [Gt ∣ S t=s , A t=a]
Where:
 s= state
  a = action
 Gt = return (total future reward)

2. Return in Monte Carlo Methods

The return is calculated as the sum of discounted rewards:
2
Gt =Rt +1 +γ R t+2 + γ Rt +3 +…
Where:
 R = reward received
 γ = discount factor

3. Monte Carlo Estimation

The action value is estimated by averaging the returns obtained after taking action a in
state s.
Sum of returns from (s , a)
Q(s , a)=
Number of visits of (s , a)
Steps:
1. Generate episodes using a policy.
2. Observe the state–action pairs encountered.
3. Calculate the return after each occurrence.
4. Update the estimated value of Q(s , a)by averaging the returns.

4. First-Visit Monte Carlo for Action Values

In this method, the action-value estimate is updated only for the first occurrence of the
state–action pair in an episode.
Sum of returns from first visits
Q(s , a)=
Number of first visits
Advantages:
 Reduces correlation between updates.

5. Every-Visit Monte Carlo

In this approach, the action-value estimate is updated every time the state–action pair
appears in an episode.
Sum of returns from all visits
Q(s , a)=
Total visits
Advantages:
 Uses more data for estimation.

6. Algorithm Steps
1. Initialize Q(s , a)arbitrarily.
2. Generate an episode using policy π .
3. For each state–action pair in the episode:
o Calculate return Gt .
o Update the action-value estimate.
Q(s , a)←Q(s , a)+α [Gt−Q(s , a)]
Where:
 α = learning rate.

7. Example
Suppose an agent performs action Right in state S1.
Observed returns:
Episode Return
1 8
2 10
3 9
Estimated action value:
8+10+9
Q(S 1 ,¿)= =9
3

8. Importance
Monte Carlo estimation of action values is important because:
 It helps estimate optimal actions
 Used in Monte Carlo control algorithms
 Forms the basis for policy improvement

9. Advantages
 Model-free method
  Simple concept
 Works well for episodic tasks

10. Limitations
 Requires complete episodes
 High variance in returns
 Slow convergence in long tasks
Monte Carlo Control
Monte Carlo Control is a reinforcement learning method used to find the optimal policy by
estimating action-value functions from sampled episodes. It is a model-free method,
meaning it does not require knowledge of transition probabilities or reward functions.

1. Definition
¿
Monte Carlo Control aims to learn the optimal policy π by estimating the action-value
function Q(s , a)using returns obtained from episodes.
Q π (s , a)=E π [Gt ∣ S t=s , A t=a]
Where:
 s= state
 a = action
 Gt = return (total future reward)

The optimal policy is obtained by selecting the action with the maximum action value.
π (s)=arg ⁡max ⁡Q(s , a)
a

2. Basic Idea
Monte Carlo Control works through two main processes:
1. Estimate action values Q(s , a)from episodes.
2. Improve the policy by selecting actions with the highest value.
This process continues until the policy converges to the optimal policy.

3. Exploring Starts Method

To ensure that all state–action pairs are explored, Monte Carlo Control uses Exploring Starts
(ES).
In this method:
  Each episode begins with a random state–action pair.
 This guarantees that all actions will eventually be tried.
Steps:
1. Initialize Q(s , a)arbitrarily.
2. Generate an episode starting from a random state–action pair.
3. Compute returns.
4. Update Q(s , a).
5. Improve policy using greedy action selection.

4. Monte Carlo Control Algorithm (Exploring Starts)

1. Initialize policy π arbitrarily.
2. Initialize action-value function Q(s , a).
3. Generate episodes using the current policy.
4. For each state–action pair in the episode:
o Calculate return Gt .
o Update Q(s , a)by averaging returns.
5. Improve the policy:
π (s)=arg ⁡max ⁡Q(s , a)
a

6. Repeat until the policy stabilizes.

5. ε-Greedy Monte Carlo Control

In practice, Exploring Starts is difficult to implement, so ε-greedy policies are used.
An ε-greedy policy works as follows:
 With probability 1−ε , choose the best action.
 With probability ε , choose a random action.
This ensures a balance between:
 Exploration (trying new actions)
 Exploitation (choosing best known action)

6. Algorithm Steps (ε-Greedy)

1. Initialize Q(s , a)arbitrarily.
 2. Generate an episode using ε-greedy policy.
3. Compute returns.
4. Update action-value estimates.
5. Improve policy using greedy selection.
Repeat until convergence.

7. Example
Suppose an agent is learning in a grid world.
State: S1
Possible actions:
Action Average Return
Up 5
Right 8
Left 6
The policy will choose Right, since it has the highest value.

8. Advantages
 Model-free method
 Works well in episodic tasks
 Easy to understand and implement

9. Limitations
 Requires complete episodes
 Learning can be slow
 High variance in return estimates
Monte Carlo Control without Exploring Starts
Monte Carlo Control without Exploring Starts is a reinforcement learning method used to
learn the optimal policy without assuming that every episode begins with a random
state–action pair. Instead of exploring starts, it uses ε-greedy policies to ensure
exploration of all actions.

1. Introduction
In Monte Carlo Control with Exploring Starts, the algorithm assumes that every state–action
pair can be chosen as the starting point of an episode.
However, in many practical situations this assumption is not realistic. Therefore, Monte
Carlo Control without exploring starts uses stochastic policies such as ε-greedy policies to
ensure sufficient exploration.

2. ε-Greedy Policy
An ε-greedy policy selects actions as follows:
 With probability 1−ε , choose the action with the highest estimated value.
 With probability ε , choose a random action.
This ensures that every action has a non-zero probability of being selected.

{
ε
1−ε + , if a=a¿
∣ A(s)∣
π (a ∣ s)=
ε
, otherwise
∣ A(s)∣

Where:
¿
 a = action with the highest value
 ∣ A (s )∣= number of possible actions

3. Action-Value Function
The algorithm estimates the action-value function Q(s , a).
Q(s , a)=E [G t ∣ S t =s , A t=a]
Where:
 Gt = return obtained after taking action a in state s.

4. Algorithm Steps
1. Initialize Q(s , a)arbitrarily.
2. Initialize policy π as ε-greedy with respect to Q .
3. Generate an episode using policy π .
4. For each state–action pair in the episode:
o Compute return Gt .
o Update the action-value estimate.
Q(s , a)←Q(s , a)+α [Gt−Q(s , a)]
 5. Improve the policy using ε-greedy selection.
6. Repeat until the policy converges.

5. Example
Suppose an agent is in state Swith three possible actions:
Action Estimated Value
Up 5
Right 8
Left 6
If ε = 0.1:
 90% probability → choose Right
 10% probability → choose a random action
This allows the agent to explore other actions while mostly choosing the best one.

6. Advantages
 Does not require exploring starts.
 Ensures continuous exploration.
 More practical for real-world problems.

7. Limitations
 Requires many episodes for convergence.
 High variance in return estimates.
 Performance depends on the choice of ε.
Off-Policy Prediction via Importance Sampling
Off-policy prediction is a reinforcement learning method used to estimate the value of a
target policy using data generated by another policy called the behavior policy.
Importance sampling is used to correct the difference between these two policies.

1. Introduction
In reinforcement learning, sometimes the policy used to generate data (behavior policy) is
different from the policy we want to evaluate (target policy).
 Target policy (π) → policy we want to evaluate
 Behavior policy (b) → policy used to generate episodes
This situation is called off-policy learning.

2. Importance Sampling
Importance sampling is a technique used to adjust the probability of samples generated
from one distribution so that they can estimate another distribution.
In reinforcement learning, it is used to reweight returns generated by the behavior policy
so that they reflect the target policy.

3. Importance Sampling Ratio

The importance sampling ratio is defined as:
π ( A t ∣ St ) π ( At +1 ∣ St +1) π ( AT −1 ∣ ST −1)
ρt :T −1= ⋅ ⋯
b ( A t ∣ St ) b( A t +1 ∣ St +1 ) b( A T−1 ∣ S T−1 )
Where:
 π = target policy
 b = behavior policy
 At = action at time t

 St = state at time t

This ratio corrects the difference between the two policies.

4. Off-Policy Monte Carlo Prediction

The value of a state under the target policy can be estimated as:
V (s)=E b [ ρt : T−1 Gt ]
Where:
 Gt = return

 ρ = importance sampling ratio

5. Types of Importance Sampling

Two main types are used in reinforcement learning.
1. Ordinary Importance Sampling
N
1
V (s)= ∑ρG
N i=1 i i
Characteristics:
  Unbiased estimator
 High variance

2. Weighted Importance Sampling

N

∑ ρi G i
V (s)= i=1N
∑ ρi
i=1

Characteristics:
 Lower variance
 Slightly biased

6. Algorithm Steps
1. Generate episodes using behavior policy b .
2. Compute the return Gt .
3. Calculate importance sampling ratio ρ .
4. Update value estimate:
V (s)←V (s)+α (ρ Gt −V (s))
5. Repeat for many episodes.

7. Advantages
 Can learn about one policy while following another.
 Allows safe learning from exploratory behavior.
 Useful when direct evaluation of the target policy is difficult.

8. Limitations
 High variance in estimates.
 Requires probability of both policies.
 Learning can be unstable if policies differ greatly.

9. Applications
Off-policy prediction is used in:
  Reinforcement learning algorithms
 Robotics learning
 Game AI
 Recommendation systems
Incremental Implementation
Incremental Implementation is a technique used in reinforcement learning to update value
estimates step by step as new data arrives, instead of storing all previous returns. It is
commonly used in Monte Carlo methods to efficiently estimate value functions.

1. Introduction
In basic Monte Carlo methods, the value of a state is calculated by averaging all observed
returns.
Sum of returns
V (s)=
Number of visits
However, storing all returns requires large memory and computational resources.
Incremental implementation solves this problem by updating the value estimate after each
new return.

2. Incremental Mean Formula

Suppose after n−1returns, the estimated value is V n−1.
When a new return Gnis observed, the value is updated as:
1
V n=V n−1+ (Gn−V n−1)
n
Where:
 V n= updated value estimate

 Gn= new return

 n = number of visits
This formula allows updating the average without storing previous returns.

3. General Incremental Update Rule

In reinforcement learning, the update rule is often written as:
V (s)←V (s)+α (G−V (s ))
Where:
 V (s)= current value estimate
  G = observed return
 α = learning rate
The learning rate controls how much the estimate changes after each update.

4. Algorithm Steps
1. Initialize value function V (s)arbitrarily.
2. Generate an episode using a policy.
3. Observe the return G for each state.
4. Update value estimate using:
V (s) ←V ( s)+α (G−V (s ))
5. Repeat for multiple episodes.

5. Example
Suppose the value estimate for a state is:
V (s)=6
New observed return:
G=8
Learning rate:
α =0.2
Update:
V (s)=6 +0.2(8−6)V (s)=6 +0.4=6.4

The value estimate moves closer to the new return.

6. Advantages
 Requires less memory
 Efficient computation
 Suitable for online learning
 Can update values immediately

7. Limitations
 Sensitive to learning rate selection
  Convergence may be slower in some cases

8. Applications
Incremental implementation is used in:
 Monte Carlo prediction
 Temporal Difference learning
 Online reinforcement learning systems
Off-Policy Monte Carlo Control
Off-policy Monte Carlo control is a reinforcement learning method used to learn the optimal
policy while generating episodes using a different policy. It allows learning about a target
policy while following a behavior policy. This method uses importance sampling to correct
the difference between these policies.
REIFORCEMENT LEARNING

1. Introduction
In reinforcement learning, two types of policies are used:
 Target Policy (π) → the policy we want to learn or evaluate.
 Behavior Policy (b) → the policy used to generate episodes.
Off-policy methods allow the agent to learn the optimal policy even when the data comes
from another policy.

2. Action-Value Function
Off-policy Monte Carlo control estimates the action-value function Q(s , a).
Q π (s , a)=E π [Gt ∣ S t=s , A t=a]
Where:
 s= state
 a = action
 Gt = return (total future reward)

The optimal policy is obtained by choosing the action with the highest value.
π (s)=arg ⁡max ⁡Q(s , a)
a

3. Importance Sampling
Because the episode is generated using the behavior policy, the returns must be adjusted to
reflect the target policy.
This is done using importance sampling.
T −1
π ( A k ∣ Sk)
ρt :T −1=∏
k=t b( A k ∣ S k )
Where:
 π = target policy
 b = behavior policy
 A k= action taken

 Sk = state

This ratio corrects the probability difference between the two policies.

4. Algorithm Steps
1. Initialize action-value function Q(s , a).
2. Initialize target policy π as greedy with respect to Q .
3. Generate an episode using behavior policy b .
4. For each state-action pair in the episode:
o Compute return Gt .
o Compute importance sampling ratio ρ .
o Update action-value estimate:
Q(s , a)←Q(s , a)+α (ρ Gt −Q(s , a))
5. Improve target policy:
π (s)=arg ⁡max ⁡Q(s , a)
a

6. Repeat until convergence.

5. Behavior Policy
The behavior policy must ensure sufficient exploration.
Usually an ε-greedy policy is used.
 With probability 1−ε → choose best action
 With probability ε → choose random action
This guarantees that all actions are explored.
6. Advantages
 Can learn optimal policy from exploratory behavior
 Allows learning while following another policy
 Useful in real-world reinforcement learning tasks

7. Limitations
 Importance sampling can produce high variance
 Learning may be slow for long episodes

8. Applications
Off-policy Monte Carlo control is used in:
 Reinforcement learning algorithms
 Game AI
 Robotics learning
 Autonomous decision making
Model Questions (Module 4 – Reinforcement Learning)

Question 1
Consider the following Q[S,A] table
State 1 State 2
Action 1 1.5 2.5
Action 2 4 3
Assume the discount factor γ =0.5and learning rate α =0.1.
After the experience (s, a, r, s') = (1, 1, 5, 2), update the Q-value using Q-learning.
Answer
Q-learning update rule:
'
Q(s , a)=Q(s , a)+ α [r + γ max ⁡ Q(s , a)−Q(s , a)]
a

Given

Q(1 , 1)=1.5max a⁡Q(2 , a)=max ⁡(2.5 , 3)=3

Substitute values:

Q(1 , 1)=1.5+0.1[5+0.5(3)−1.5]¿ 1.5+0.1 [5+1.5−1.5]¿ 1.5+0.1(5)¿ 1.5+0.5Q(1 , 1)=2.0

Updated value:
Q(1 , 1)=2.0

Question 2
Consider the same Q[S,A] table
State 1 State 2
Action 1 1.5 2.5
Action 2 4 3
Assume γ = 0.5, α = 0.1.
After the experience
¿
update the value using SARSA.
Answer
SARSA update rule:
' '
Q( s , a)=Q( s , a)+ α [r + γQ( s , a )−Q(s , a)]
Given

Q(1 , 1)=1.5Q(2 , 1)=2.5

Substitute:

Q(1 , 1)=1.5+0.1[5+0.5(2.5)−1.5]¿ 1.5+0.1 [5+1.25−1.5]¿ 1.5+0.1(4.75)¿ 1.5+0.475

Q(1 , 1)=1.975
Updated value:
Q(1 , 1)=1.975

Question 3
For Q-learning to converge we must correctly manage the exploration vs exploitation
tradeoff. What property must the exploration strategy satisfy?
Answer
The exploration strategy must satisfy the GLIE condition (Greedy in the Limit with
Infinite Exploration).
This means:
1. Every state–action pair must be visited infinitely often.
2. The policy must become greedy in the limit.
Example method:
ε-greedy exploration where
ε →0
as the number of episodes increases.
This ensures:
 Sufficient exploration initially
 Optimal policy convergence eventually.

Question 4
What is the difference between Q-learning and SARSA?
Answer
Feature Q-learning SARSA
Type Off-policy On-policy
Update uses Maximum future Q value Actual action taken
' ' '
Formula r + γ max ⁡a Q(s , a) r + γQ( s , a )

Exploration Independent of policy Depends on policy

Q-learning learns the optimal policy directly, while SARSA learns the policy being
followed.

Question 5
List any three advantages of Monte Carlo methods over Dynamic Programming.
Answer
1. Does not require a model of the environment.
2. Learns directly from experience.
3. Easy to implement for complex problems.

Question 6
Why do Monte Carlo methods require episodic tasks?
Answer
Monte Carlo methods estimate value functions using the return Gt which is the sum of
rewards until the terminal state.
Gt =Rt +1 +γ R t+2 + …
Since the return is calculated after the episode ends, Monte Carlo methods require complete
episodes.

Question 7
Explain Incremental Implementation in Monte Carlo methods.
Answer
Instead of storing all returns, value estimates can be updated incrementally:
V (s)=V (s)+ α(G−V (s))
Advantages:
 Saves memory
 Allows online learning
 Efficient for large problems

Question 8
Explain Off-policy Monte Carlo Control.
Answer
Off-policy Monte Carlo Control learns the optimal policy while following a different
behavior policy.
It uses importance sampling to correct the difference between policies.
Importance sampling ratio:
T −1
π ( Ak ∣ Sk )
ρ=∏
k=t b( A k ∣ S k )
Where
 π = target policy
 b = behavior policy.
Model Questions (Similar Pattern)

Question 1
Consider the following Q[S,A] table
State 1 State 2
Action 1 2 3
Action 2 4 5
Assume the discount factor γ =0.6and step size α =0.2.
After the experience
¿
1. Which value in the Q-table will be updated?
2. Compute the new Q-value using Q-learning.
b) Explain why Q-learning is called an off-policy algorithm.

Question 2
Consider the following Q[S,A] table
State 1 State 2
Action 1 1 2
Action 2 3 4
Assume
γ =0.7 , α=0.1
After the experience
¿
1. Update the Q-value using the SARSA algorithm.
b) Explain the difference between on-policy and off-policy learning.

Question 3
Consider the following Q[S,A] table
State 1 State 2
Action 1 3 4
Action 2 2 5
Assume
γ =0.8 , α=0.1
Experience:
¿
1. Update the Q-value using Q-learning.
b) What is the role of the discount factor γ in reinforcement learning?
Question 4
Consider the following Q[S,A] table
State 1 State 2
Action 1 2 1
Action 2 3 4
Assume
γ =0.5 , α=0.2
Experience:
¿
1. Update the value using SARSA learning rule.
b) What is the exploration vs exploitation tradeoff in reinforcement learning?

Question 5
Consider the following Q[S,A] table
State 1 State 2
Action 1 5 3
Action 2 4 2
Assume
γ =0.4 , α =0.1
Experience:
¿
1. Update the Q-value using Q-learning rule.
b) Explain the ε-greedy policy used for exploration.

Question 6
Explain the following concepts:
a) Policy Iteration and Value Iteration.
b) What are the advantages of Monte Carlo methods over Dynamic Programming?

Question 7
Explain Monte Carlo Prediction and Monte Carlo Control with suitable examples.
Question 8
Explain Off-policy Prediction using Importance Sampling and derive the importance
sampling ratio.

Question 9
Explain Monte Carlo Control without Exploring Starts and describe the ε-greedy policy
improvement strategy.

Question 10
Explain Incremental Implementation in Monte Carlo methods and derive the incremental
update formula.