Tutorial on Monte Carlo Methods, Q & TD

Learning and Martingales

E1 277: Reinforcement Learning (Spring 2026)

Department of CSA, IISc

Instructor: Prof. Shalabh Bhatnagar
Indian Institute of Science (IISc)

Monte Carlo Methods

Question 1

Problem Statement. Consider a discounted reward Markov Decision Process (MDP) with
state space
S = {a, b, c, d, e}.
You are given the following sequences of states and rewards obtained across two episodes.
Compute the value function for all states using Monte Carlo on-policy policy evaluation for
both the first-visit and every-visit methods. Assume the initial value estimates for all states
are zero, and the discount factor is
γ = 0.90.

Episode 1
a, 1, b, 2, a, 1, c, 4, b, 3, d, 5, e, 7

Episode 2
d, 4, c, 1, b, 0, e, 3, a, 5, d, 1, a, 3

Question 2

PT , r T

PS , r S S T

Figure 1: 2-state Abstract Markov Chain

Tutorial on Monte Carlo Methods, Q & TD Learning and Martingales – E1 277:

Reinforcement Learning (Spring 2026)
Any arbitrary arbitrary undiscounted absorbing Markov chains can be reduced to a two-state
abstracted Markov chain. Consider markov chain as shown in 1. Here T is a terminal state.
Let rS , rT be random rewards associated with transitions S → S and S → T respectively. You
can assume, RS = E[rS ], V[rS ] = E[rS − RS ]2 , RT = E[rT ] and V[rT ] = E[rT − RT ]2 .
Let {x} stand for the paired random sequence ({S}, {r}).
The first-visit Monte Carlo estimate for V (s) after one trial, {x} is

V1F (s) = f ({x}) = rS1 + rS2 + ... + rSk + rT

where k is the random number of revisits to state S, rSi is random reward in S, and rT is the
random total reward received after the last. visit to state S. For all i, E[rS ] = Rs .
The every-visit Monte Carlo estimate for one trial, denoted by {x}, is

tnum ({x}) rS + 2rS2 + ... + krSk + (k + 1)rT

V1E (s) = t({x}) = = 1
k+1 k+1
where k is the random number of revisits to state S in the sequence {x}. Every visit to state S
effectively starts another trial. Therefore, the rewards that occur between the i-th and (i + 1)-st
visits to state s are included i times in the estimate. These formulae are defined in this way
due to reduction to abstract MDP.

a Determine biases for estimated value functions for First-Visit as well Every-Visit
Monte Carlo for single trial. Then compare between these two methods.

b Determine variances for estimated value functions for the same for single trial. Compare
the variances for these two methods.

Off Policy

Question 3

You and your friend are roaming in fair. So in fiar both of you come to stall of magician,
your friends wants to play this game, game is simple magician gives choices there n choices
C1 , C2 , C3 , ..., Cn and need to select one and take reward Rs. Ri and N is number of chances
given, your friend wants to foil game of magician by identifying best choice. He knows only to
select any choice randomly, wants your help to identify best choice.

a Device algorithm or procedure for your friend in order to find best choice.

b Suppose there 3 choices he gets in rewards and choices : C1 Rs. 2.5, C3 Rs. 7, C2 Rs. 6, C1 Rs. 0, C2 Rs. 3,
C3 Rs. 2. Can you predict best choice by using your algorithm or procedure?

Q and TD Learning

Question 4

Tutorial on Monte Carlo Methods, Q & TD Learning and Martingales – E1 277:

Reinforcement Learning (Spring 2026)
 A
B C D
E

Figure 2: Gridworld

Suppose following (s, a, s′ , R(s, a, s′ )) transitions and rewards are observed:

(B, East, C, 2), (C, South, E, 4) , (C, East, A, 6), (B, East, C, 2) The initial value of each
state is 0. Let γ = 1 and α = 0.5.

a What are the learned values for each state from TD learning after all four observations?

b These are the two formulations for TD-learning:

Vπ (s) ← (1 − α)Vπ (s) + α(R + Vπ (s′ ))

Vπ (s) ← Vπ (s) + α(R + Vπ (s′ ) − Vπ (s))

Mathematically, these two equations are equivalent. However, they represent two con-
ceptually different ways of understanding TD value updates. How could we intuitively
explain each of these equations?

c What are the learned Q-values from Q-learning after all four observations? Use the same
α = 0.5, γ = 1 as before.

Question 5

Show that using ε-greedy, the SARSA algorithm converges to Q∗,ε , and
2εγVmax
∥Q∗,ε − Q∗ ∥∞ ≤ .
1−γ

Where Vmax = R1−γmax

, Rmax is upper bound on reward on can get. This SARSA needs to be
taken in discounted MDP setting and it is of maximization problem.

Question 6

Recall Gradient Search algorithm discussed in class. Now in applying TD(0) algorithm rather
than complicated V (.), it can be relaxed using approximate parameterized class of functions
{fθ : X → R : θ ∈ Rd }. Take assumptions used while gradient search.

a Consider fθ (.) = ⟨θ, Φ(.)⟩, where feature vectors {Φ(x) ∈ Rd : x ∈ X} with supx∈X ∥Φ(x)∥2 ≤
1. Derive update rule for approximated value function. You can take V (.) ≈ fθ (.) if re-
quired where ever and some well known equations you can use.

b Can you comment on convergence part of it ?

Tutorial on Monte Carlo Methods, Q & TD Learning and Martingales – E1 277:

Reinforcement Learning (Spring 2026)
Question 7

Consider an MDP with n states and m actions (per state). Let π be an arbitrary policy. We
define the n-step (fixed policy) Bellman operator

Tπn : Rn → Rn

as follows:
n−1
def
X
Tπn v = γ t (Pπ )t rπ + γ n (Pπ )n v,
t=0
where
rπ ∈ Rn , Pπ ∈ Rn×n
are the reward vector and transition matrix under policy π, respectively.
Next, define the TD(λ) operator
Tπλ : Rn → Rn
as
∞
X
Tπλ v = (1 − λ) λt Tπt v = (I − γλPπ )−1 rπ + γ(1 − λ)Pπ v


t=0

= v + (I − γλPπ )−1 rπ + γPπ v − v .

def
Prove that Tπλ v is a ξλ = γ(1−λ)1−γλ contraction in the d-weighted L2 norm, and determine
fixed point. Let dT = dT Pπ be the stationary distribution of Pπ . (Hint:
(by proving) its P
(I − γλPπ )−1 = ∞ t t
t=0 (γλ) (Pπ ) .)

Question 8

Recall Double Q Learning from class, similar to it we will define,

At each time step t of the algorithm we observe st , choose an action at , and observe the next
state st+1 . We then choose which table to update by drawing a random variable xt+1 :
(
A, with probability 0.5,
xt+1 =
B, with probability 0.5,

independent of all other variables in the problem.

If xt+1 = A, we set
a∗ = arg max QA
t (st+1 , a),
a

and update QA (st , at ) according to

 
∗
QA
t+1 (s t , at ) = QA
t (s t , at ) + α t (s t , at ) r(st , at ) + γQB
t (s t+1 , a ) − Q A
t (s t , at ) .

Otherwise, if xt+1 = B, we set

b∗ = arg max QB
t (st+1 , a),
a

and update QB (st , at ):

 
∗
QB B A B
t+1 (st , at ) = Qt (st , at ) + αt (st , at ) r(st , at ) + γQt (st+1 , b ) − Qt (st , at ) .

Tutorial on Monte Carlo Methods, Q & TD Learning and Martingales – E1 277:

Reinforcement Learning (Spring 2026)
When updating QA , all elements in QB remain unchanged, and vice versa. Additionally, similar
to regular Q-learning, we update only the entry of the chosen table (A or B) corresponding to
the current state–action pair (st , at ), and leave all other table entries unchanged. Let Ft denote
the history of the process until time t, i.e.,

Ft = s0 , a0 , QA B A B A B

0 , Q0 , x0 , s1 , a1 , Q1 , Q1 , x1 , . . . , st , at , Qt , Qt , xt .

a Show that the update for QB

t can be written as

QB B B


t+1 (st , at ) = (1 − αt (st , at )) Qt (st , at ) + αt (st , at ) HQt + ωt + ct ,

where ωt is a martingale-difference noise term, H is a contraction operator, and

∗ ∗
ct = γQA B
t (st+1 , b ) − γQt (st+1 , b ).

b Let
∆t (s, a) = QB A
t (s, a) − Qt (s, a).

Write down ∆t+1 (s, a) explicitly as function of ∆t (st , at ), xt+1 and other required terms.

c We define
∗ ∗
gt = E QA B
 
t (st+1 , b ) − Qt (st+1 , a ) Ft .

Show that

E[∆t+1 (st , at ) | Ft ] = (1 − 0.5 αt (st , at )) ∆t (st , at ) + 0.5 γ αt (st , at ) gt .

d Prove that |gt | ≤ ∥∆t ∥∞

e Show that the update of ∆t can be written as

∆t+1 (st , at ) = (1 − 0.5 αt (st , at )) ∆t (st , at ) + 0.5 αt (st , at ) Ht′ + ηt ,

(25)

where
E[Ht′ | Ft ] ≤ γ ∥∆t ∥∞ ,
and ηt is a martingale-difference term.

Question 9

Recall SARSA algorithm been taught in the class and Q-learning convernce also has been done,
can you prove convergence of SARSA ? This SARSA needs to be taken in SSP setting and
minimization problem.

Martingales

Question 10

Let {ξj }j≥1 be i.i.d. random variables with common distribution

P(ξi = +1) = p, P(ξi = −1) = q := 1 − p.

Tutorial on Monte Carlo Methods, Q & TD Learning and Martingales – E1 277:

Reinforcement Learning (Spring 2026)
Let
Fn = σ(ξj : 1 ≤ j ≤ n), n≥0
be their natural filtration, and define
n
X
Sn := ξj , n ≥ 0.
j=1

a Prove that  Sn

q
Mn :=
p
is an (Fn )n≥0 -martingale.

b For λ > 0, determine a constant C = C(λ) such that

Znλ := C n λSn

is an (Fn )n≥0 -martingale.

Question 11

If B1 ⊂ B2 ⊂ B and E[X 2 ] < ∞, then

E[(X − E[X|B2 ])2 ] ≤ E[(X − E[X|B1 ])2 ]

Tutorial on Monte Carlo Methods, Q & TD Learning and Martingales – E1 277:

Reinforcement Learning (Spring 2026)