Assignment 1

Course: Reinforcement Learning (MEL7118/MCL775)

• This assignment will not be graded. That said, we encourage you to work through the
problems diligently, as they are designed to support your understanding of the material.
Completing this assignment will help you stay engaged with the course content and make it
easier to keep pace with the course.

• Feel free to discuss the problems with your peers, but ensure that the solutions you work out
are your own.

• While tools such as ChatGPT can assist with answering these questions, the true purpose of
this assignment is to develop your own understanding. By thinking critically, struggling with
ideas, and revisiting your notes and textbook, you build the insight that leads to genuine
learning.

1. Show that if a function is continuous limk→∞ f (xk ) = f (limk→∞ xk ).

2. In Lecture 2, we derived the closed form solution for the value function under a fixed policy
µ as
Vµ = (I − γPµ )−1 rµ ,
where Pµ is the state transition probability matrix and 0 ≤ γ < 1.
Prove that the matrix inverse (I − γPµ )−1 always exists for all 0 ≤ γ < 1.
Hint: Use the Gershgorin Circle Theorem and the fact that Pµ is a stochastic matrix.

3. Consider the value function

" ∞
#
X
t
Vπ (s) = Epπ γ r(st , at , st+1 ) s0 = s ,
t=0

where at = π(st ) for a known deterministic policy π : S → A, and γ ∈ (0, 1). We know that
Vπ (s) satisfies the following recursive Bellman equation
X X
Vπ (s) = p(s′ | s, a) r(s, a, s′ ) + γ p(s′ | s, a) Vπ (s′ )
s′ ∈S s′ ∈S
| {z }
=:[T π (Vπ )](s)

where T π : R|S| → R|S| is a map as defined above. Show that T π is a contraction map.

1
4. Consider the problem setup as above, only this time the policy is stochastic, i.e., π : A × S →
[0, 1]. Derive the corresponding recursive Bellman equation from scratch. [Hint: The
equation will be as below]
X X X X
Vπ (s) = π(a | s) p(s′ | s, a) r(s, a, s′ ) + γ π(a | s) p(s′ | s, a) Vπ (s′ )
a∈A s′ ∈S a∈A s′ ∈S
| {z }
=:[T̃ π (Vπ )](s)

Show that the map T̃ π : R|S| → R|S| corresponding to the above recursion is also a contraction
map.

5. Recall the Bellman optimality operator defined as T in lecture 3

" #
X
(T J)(s) := max r(s, a) + γ p(s′ | s, a) J(s′ ) , ∀s ∈ S.
a∈A
s′ ∈S

(a) Show that if V ≤ W , then T (V ) ≤ T (W ).

(b) Show that T (V + c1|S| )(s) = (T V )(s) + γc1.
(c) Show that T is a continuous map

6. Let M = ⟨S, A, P, R, γ⟩ be an MDP. We showed that for every policy π : S → A and state
s ∈ S, the following recursion holds
X  
′ ′ ′
Vπ (s) = p(s |s, π(s)) r(s, π(s), s ) + γVπ (s ) .
s′ ∈S

Consider four variations in our definitions or assumptions regarding the input MDP M
and policy π. In each case, write down the Bellman equations after making appropriate
modifications.

(a) The reward function R does not depend on the next state s′ ; it is given to you as
R : S × A → R.
(b) The reward function R depends only on the next state s′ ; it is given to you as R : S → R.
(c) The underlying MDP M is deterministic. Hence, the transition function T is given as
T : S × A → S, such that T (s, a) is the next state s′ ∈ S for s ∈ S, a ∈ A.
(d) The policy π is stochastic: for s ∈ S, a ∈ A, π(s, a) denotes the probability with which
the policy takes action a from state s.

2
7. Recall that in the lecture 2 we stated the following result: Let T : Rn → Rn be an operator.
ˆ J˜ ∈ Rn ,
Suppose there exists a constant α ∈ (0, 1) such that for all J,
ˆ − T (J)∥
∥T (J) ˜ ≤ α ∥Jˆ − J∥.
˜

Then T is called a contraction mapping. Moreover, T admits a unique fixed point J ∗ satisfying

J ∗ = T (J ∗ ),

and this fixed point can be computed via the fixed-point iteration

Jk+1 = T (Jk ), with lim Jk = J ∗ ,

k→∞

for any initial J0 ∈ Rn .

(a) Show that the sequence {Jk }∞

k=0 generated by the iteration Jk+1 = T (Jk ) converges to
∗
J .
(b) Prove that T has a unique fixed point.

8. Recall the modified policy iteration algorithm . Its proof of convergence was divided into 3
cases. For the last case T V0 ̸≥ V0 , we constructed a corresponding V̂0 for which T V̂0 ≥ V̂0 ,
and claimed that starting at V̂0 or V0 will produce the same set of policies. In fact, we proved
it for the first iteration, i.e., we showed that π̂1 = π1 . The objective of this problem is to
generalize the proof done in class and show that π̂k = πk for any k.
9. Consider the value function V (s) defined as
"∞ #
X
V (s) = max Epπ γ k r(sk , π(sk ), sk+1 ) s0 = s .
π
k=0

We know that V (s) satisfies the following recursive Bellman equation,

" #
X
V (s) = max r(s, a) + γ p(s′ | s, a)V (s′ ) .
a∈A
s′ ∈S

From above, we defined the Q-function, also known as the state-action value function, which
satisfies the following recursive equation
X
Q(s, a) = r(s, a) + γ p(s′ | s, a) max
′
Q(s′ , a′ )
a ∈A
s′ ∈S
| {z }
=: [TQ (Q)](s,a)

Show that TQ : S × A → R is a contraction map.

3
 ′
10. Consider a Markov Decision Process M = ⟨S, A, T , R, γ⟩. Let V0 : S → R be an initial
estimate of the optimal value function V ∗ . This estimate is iteratively updated as (Value
Iteration):
Vt+1 = T (Vt ), t = 0, 1, 2, . . . ,
where T denotes the Bellman optimality operator.
Our goal is to design a practical stopping criterion for Value Iteration. Let ∥ · ∥∞ denote
the max norm. For a given tolerance ϵ > 0, we wish to guarantee that the computed value
function Vu satisfies
∥Vu − V ∗ ∥∞ ≤ ϵ.

Since the optimal value function V ∗ is unknown, it cannot be used directly in the stopping
rule. Show that it is sufficient to terminate the algorithm when

ϵ(1 − γ)
∥Vu − Vu−1 ∥∞ ≤ ,
γ
and then return Vu as the final approximation.
You may use the following facts:

(a) The Bellman optimality operator T is a contraction mapping with contraction factor γ.
(b) For any functions X, Y : S → R, the max norm satisfies the triangle inequality:

∥X + Y ∥∞ ≤ ∥X∥∞ + ∥Y ∥∞ .

11. Consider an MDP with a set of n ≥ 2 states S = {1, 2, . . . , n}, and a set of three actions
A = {0, 1, 2}. There is cycle dependence among the states in the MDP, in the sense that
each state s has a “previous” state prev(s) and a “next” state next(s), defined by
( (
n, if s = 1, s + 1, if 1 ≤ s ≤ n − 1,
prev(s) = next(s) =
s − 1, if 2 ≤ s ≤ n, 1, if s = n.

From each state s, the only possible transitions are to s itself, to prev(s), or to next(s). In
particular:

• Action 0 takes the agent from state s to either s or prev(s) with equal probability.
• Action 1 takes the agent from state s to s, prev(s), or next(s) with equal probability.
• Action 2 takes the agent from state s to either s or next(s) with equal probability.

4
 The reward for any transition is fully determined by the action: the reward is 0 from action
0, 1 from action 1, and 2 from action 2. The discount factor is γ = 54 .
Work out the optimal value function V ∗ and an optimal policy π ∗ for the given MDP; observe
that both quantities are n-dimensional. Since there are 3n policies (and n is a variable), you
cannot possibly evaluate all policies. Begin with your intuition to propose the solution;
thereafter, use the structure of the MDP to provide formal justification that what you claim
to be V ∗ is indeed the optimal value function and that what you claim to be π ∗ is indeed an
optimal policy. You can reuse any result that has been proven in class.

12. Coding Problem: Consider the Gridworld in the Example 4.1 of Sutton and Barto (https:
//[Link]/class/psych209/Readings/[Link]). The
example clearly defines the state space, action space, rewards, and transition probabilities.
It does not say anything about the discount factor γ, so you can consider that to be 0.98.
Create a Jupyter notebook that consists of the following code snippets.

(a) Use value iteration method to determine the optimal policy for the above MDP. Print
the optimal policy as well as the optimal value function.
(b) Use policy iteration method to determine the optimal policy for the above MDP. Print
the optimal policy as well as the optimal value function.
(c) Use modified policy iteration method to determine the optimal policy for the above
MDP. Print the optimal policy as well as the optimal value function. You are free to
choose any value of mk in your code.
(d) In the context of the above MDP, rank the different algorithms (VI, PI, and MPI) in
terms of the computational expense? Explain the plausible causes for your observations.