Tutorial on Discounted Cost MDPs

E1 277: Reinforcement Learning (Spring 2026)

Department of CSA, IISc

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

Question 1

An energetic salesman works every day of the week. He can work in only one of two towns
A and B each day. If he works in town A he receives expected reward rA , and if he works in
town B he receives reward rB . Changing towns between two consecutive days incurs a cost c.
Assume
c > rA > rB , α < 1,
where α is the discount factor.

a Show that for α sufficiently small, the optimal policy is to stay in the town he starts in,
and that for α sufficiently close to 1, the optimal policy is to move to town A (if not
starting there) and stay in A for all subsequent times.
b Solve the problem for c = 3, rA = 2, rB = 1, and α = 0.9 using policy iteration.

Question 2

A manufacturer at each time period receives an order for her product with probability p, and
receives no order with probability 1 − p. At any period, she has a choice of processing all the
pending orders in a batch, or process no order at all. The cost per pending order in any period
is c > 0, and the setup cost to process the pending orders is K > 0. She aims to find an optimal
processing policy that minimizes, in expectation, the infinite horizon discounted cumulative
cost, with a discount factor α ∈ (0, 1). The setting has a constraint that the maximum number
of orders that can be pending is n. Answer the following:

a Letting the number of pending orders as the state, write down the Bellman equation for
this problem.
b Let J ∗ denote the optimal cost vector. Show that J ∗ (i) is monotonically non-decreasing
in i. Using this fact, show that a threshold-based policy is optimal.
c Show that if policy iteration algorithm is initialized with a threshold policy, every subse-
quently generated policy will be a threshold policy.

Tutorial on Discounted MDPs – E1 277: Reinforcement Learning (Spring 2026)

Question 3

Consider an dicounted-cost MDP (S, A, R, P, γ) with a given, fixed policy π. We define Mπ (s)
as the second moment of the discounted return when starting from state s and following policy
π:
 !2 
∞
X
Mπ (s) = Eπ  γ t r(st , at ) s0 = s .
t=0

In addition, recall that

"∞ #
X
t
Jπ (s) = Eπ γ r(st , at ) s0 = s .
t=0

a Write an expression in vector form for Mπ that is dependent on Jπ and Mπ .

b Given that Jπ is fixed, is the operator you obtained a contraction? If the answer is positive,
prove it. If not, convincingly show why or provide a counterexample.

c Given that Jπ is fixed, suggest an iterative algorithm for learning Mπ and prove its con-
vergence.

Question 4

Let us explore a modified definition of the value function in the context of a Markov Decision
Process (MDP), defined by the tuple (S, A, P, r, γ), where:

• S is the state space,

• A is the action space,

• P (s′ | s, a) is the transition probability from state s to state s′ under action a,

• r(s, a, s′ ) is the reward received when transitioning from s to s′ via action a,

• γ ∈ [0, 1) is the discount factor.

Typically, the value function for a policy π is defined as the expected discounted cumulative
reward: "∞ #
X
Jπ (s) = Eπ γ t rt s0 = s .
t=0

We now consider an alternative definition that incorporates an additional cost term, reflecting
scenarios where actions or states incur penalties beyond the immediate reward structure.

Tutorial on Discounted MDPs – E1 277: Reinforcement Learning (Spring 2026)

Modified Value Function Definition

Consider an MDP where, in addition to receiving rewards, the agent incurs a cost c(s, a) when
taking action a in state s. Define the modified value function for a policy π as:
"∞ #
X
t


Jπ (s) = Eπ γ rt − λ c(st , at ) s0 = s ,
t=0

where:

• rt = r(st , at , st+1 ) is the reward at time t,

• c(st , at ) is a known (non-negative) cost function,

• λ ≥ 0 is a parameter controlling the trade-off between maximizing rewards and minimizing

costs,

• the expectation Eπ is taken over trajectories induced by policy π, where π(a|s) is the
probability of taking action a in state s.

This modification can represent practical scenarios such as penalizing resource consumption,
energy usage, or undesirable actions, making it a meaningful extension of the standard frame-
work.

a (Derive the Bellman Equation) Using the modified value function defined above,
derive the Bellman equation for Jπ (s). Your equation should express Jπ (s) in terms of
the immediate reward, the cost, and the value of the next state s′ . Show all steps clearly,
considering the recursive nature of the value function.

b (Propose a Bellman-Type Operator) For the optimal value function

J ∗ (s) = max Jπ (s)

π

under this modified definition, suggest a Bellman-type operator T . The operator should
map a value function J to a new value function T V , facilitating the computation of J ∗
(e.g., via value iteration). Define the operator explicitly and explain why it is suitable.

c (Analyze the Impact) Discuss how this modified value function might affect the optimal
policy compared to the standard definition (where λ = 0). How might the parameter λ
influence the agent’s decision-making? Provide a brief qualitative analysis

Question 5

Let J¯ : S → R be any bounded function on S and consider the value iteration method with a
starting function J : S → R of the form
¯ +r
J(x) = J(x) x∈S

where r is some scalar. Show that (T k J)(x) + ck and (T k J)(x) + c̄k can be represented in-
α
dependent of r for all x ∈ S. Where, ck = 1−α mini=1,...,n [(T k J)(i) − (T k−1 J)(i)], c̄k =
α k k−1 J)(i)].
1−α maxi=1,...,n [(T J)(i) − (T

Tutorial on Discounted MDPs – E1 277: Reinforcement Learning (Spring 2026)

Question 6

The version of value iteration method that starts with an arbitrary function J : S → R and
generates recursively F J, F 2 J, ..., where F is the mapping given by
P
g(i, u) + α j̸=i pij (u)J(j)
F J(i) = minu∈U (i)
1 − αpii (u)

Show that (F k J)(i) → J ∗ (i) as k → ∞.

Question 7

Consider the solution of the system J = F J, where F : Rn → Rn is the mapping

F J = h + QJ

h is a given vector in Rn , and Q is an n × n matrix. Consider the generic rank-one correction

iteration JM J, where M : Rn → Rn is the mapping

M J = F J + γz

and
(d − z)′ (F J − J)
z = Qd, γ=
∥d − z∥2
Consider the iteration x := M (x) defined by above equations:

a The mapping M (x) can be written as

M (x) = g + Rx,

where
z(d − z)′ h
g =h+ ,
∥d − z∥2
and
z(d − z)′ (Q − I)
R=Q+ .
∥d − z∥2

Furthermore,
Rd = 0.

b Let λ1 , . . . , λn be the eigenvalues of Q, and assume that d is an eigenvector corresponding

to λ1 . Then for all k and x we have

Rk = RQk−1 , M k (x) = M F k−1 (x) .

Question 8

Let S be a set and B(S) be the set of all bounded real-valued functions on S. Let T : B(S) →
B(S) be a mapping with the following two properties:

1. T J ≤ T J ′ for all J, J ′ ∈ B(S) with J ≤ J ′ .

Tutorial on Discounted MDPs – E1 277: Reinforcement Learning (Spring 2026)

 2. For every scalar r ̸= 0 and all x ∈ S.

(T (J + re))(x) − (T J)(x)
α1 ≤ ≤ α2
r
where α1 , α2 are two scalars with 0 ≤ α1 ≤ α2 < 1.

a Show that T is a contraction mapping on B(S), and hence for every J ∈ B(S) we have

lim (T k J)(x) = J ∗ (x), x ∈ S,

k→∞

where J ∗ is the unique fixed point of T in B(S).

b Show that fo all J ∈ B(S), x ∈ S and k = 1, 2, ..,

(T k J)(x) + ck ≤ (T k+1 J)(x) + ck+1 ≤ J ∗ (x) ≤ (T k+1 J)(x) + c̄k+1 ≤ (T k J)(x) + c̄k

where for all k

n α α1 o
1
ck = min minx∈S [(T k J)(x)−(T k−1 J)(x)], minx∈S [(T k J)(x)−(T k−1 J)(x)]
1 − α1 1 − α1
n α α2 o
1
c̄k = max maxx∈S [(T k J)(x)−(T k−1 J)(x)], maxx∈S [(T k J)(x)−(T k−1 J)(x)]
1 − α1 1 − α2

Question 9

Recall the following standard primal and dual Linear Programming (LP) formulations:

min b⊤ x subject to Ax ≥ c,

and its dual:

max c⊤ y subject to A⊤ y ≤ b, y ≥ 0.

Consider an MDP defined by the tuple (S, A, P, r, ρ, γ), with the discounted-return criterion
over an infinite time horizon: "∞ #
X
t
Jπ = Eπ,ρ γ r(st , at ) ,
t=0

where Eπ,ρ is the expectation over trajectories induced by policy π with initial state distribution
s0 ∼ ρ. Our goal is to find the optimal value function:

J ∗ = max Jπ .
π

Recall that for a fixed policy, the value function can be found by solving:
X
J(s) = r(s, a) + γ P (s′ |s, π(s)) J(s′ ), ∀s ∈ S.
s′ ∈S

a (Primal LP Formulation)
Write the primal LP for the optimization problem, where the primal variables are the
state values.

Tutorial on Discounted MDPs – E1 277: Reinforcement Learning (Spring 2026)

b (Dual LP Formulation)
Write the dual LP for this problem, where the dual variables correspond to the discounted
state-action visitation frequencies. Suppose we want to solve the MDP while ensuring that
the resulting solution policy is close to a given stationary policy µ(a|s) (which is generally
stochastic). Specifically, for some ϵ > 0, impose the constraint:

∀s ∈ S : max |π(a|s) − µ(a|s)| ≤ ϵ.

a∈A

c (Non-Determinism of the Optimal Policy)

Show, either by example or by a convincing argument, that under this constraint the
optimal policy is not necessarily deterministic. (An example with multiple optimal deter-
ministic policies is not acceptable.)

d (Dual LP With Policy Closeness Constraint)

Rewrite the dual LP to incorporate the new constraint. Your formulation should include
non-linear functions.

e (Size of the New Primal LP)

Determine how many variables and how many constraints the modified primal LP will
contain.

f (Policy Iteration Algorithm)

Propose a policy iteration algorithm based on this new formulation.

g (Convergence)
Show that the proposed policy iteration algorithm converges in a finite number of steps
to the optimal policy.

Tutorial on Discounted MDPs – E1 277: Reinforcement Learning (Spring 2026)