I'm trying to understand a proof in Puterman'05 (Markov Decision Processes: Discrete Stochastic Systems). My question is within Theorem 6.9.1 pertaining to the equivalence of solutions to the primal (MDP) LP and the dual LP. The Dual Linear Program has the constraint (Equation 6.9.2):

$$\sum_{a\in A_j} x(j,a) - \sum_{s\in S}\sum_{a\in A_s} \lambda p(j\mid s,a)x(s,a)=\alpha(j),$$


  • $S$ set of all states.
  • $A_s$ set of actions available in state $s$.
  • $x_d(s,a)$ is an occupancy measure for a policy reaching state s and taking action a following the stationary decision-rules/policy $d$.
  • $\lambda$ discount factor.
  • $p(s'\mid s, a)$ is the MDP's transition dynamics.
  • $\alpha$ is the initial state distribution, and $\alpha(s)$ is the probability of starting in state $s$.

My question has to do with the proof that establishes this constraint (Equation 6.9.5). The proof is as follows:

Clearly $x_d \geq 0$. Let $\delta(j|k)$ denote the $(k,j)$th element of $I$. Then $$\begin{align} \sum_s\sum_a \lambda p(j\mid s,a)x_d(s, a) \\ &=\sum_s \sum_a\lambda p(j\mid s, a)\sum_{k\in S}\alpha(k)\sum_{n=1}^{\infty}\lambda^{n-1} P^{d^\infty}(X_n=s,Y_n=a\mid X_1=k) \\ &=\sum_k\alpha(k)\left[ \sum_{n=1}^{\infty} \lambda^n P^{d^\infty} (X_{n+1}=j\mid X_1 = k)\right]\\ &=\sum_k\alpha(k)\left[ \sum_{n=1}^{\infty} \lambda^{n-1} P^{d^\infty} (X_n=j\mid X_1 = k) - \delta(j\mid k)\right] \\ &=\sum_{a}x(j,a) - \alpha(j)\end{align}$$ establishing (6.9.2).

Question: Could someone explain the intuition behind the transition between lines 3 and 4? In particular, how $\delta$ is constructed and why that reduces the exponent of $\lambda$.

My current institutions say it has something to do with the fact that line 3 does not account for starting in state $j$ (and thus if you are in state $j$ you need not discount the occupancy probability); however, I cannot follow the decomposition of the terms with this train of thought.


1 Answer 1


It is just $$\sum_{n=1}^\infty a_n = \sum_{n=0}^\infty a_n - a_0 = \sum_{n=1}^\infty a_{n-1} - a_0,$$ where $$a_n=\lambda^n P^{d^\infty}(X_{n+1}=j\mid X_1=k).$$ In particular $$a_0=\lambda^0 P^{d^\infty}(X_1=j\mid X_1=k) = [j=k] = \begin{cases}1 &\text{if $j=k$}\\0 &\text{otherwise} \end{cases}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.