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),$$
where:
- $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.
