Skip to main content
1 of 2
Tryer
  • 121
  • 2

Existence of infinite horizon values in dynamic programming

I am working through the book "Foundations of Stochastic Inventory Theory".

One of the results in the book is Theorem 11.2. The background to this theorem is as follows.

Given finite state space $\mathcal{S}=\{1,2,...,S\}$, policy (which provides a mapping of what action to take in each state $s$ in teach time period $t$:) $\mathcal{\pi}=\{\pi_1,\pi_2,...,\pi_t,...\}$, and a value space $\mathbb{R}^S$. Then, to obtain period $t$'s value function, $v_t(\pi)$ (which is an $S$ vector of reals), we can solve the following recursion:

$$v_t(\pi)=H(\pi_t)v_{t+1}(\pi) $$

In plain language, this means that given an $S$ vector of period $t+1$'s values of being in different states, the value of starting in different states in period $t$ can be obtained by applying operator $H(\pi_t)$ to the next period's values. It is known that $H(\pi_t)$ is an affine map and is also a contracting operator. That is, given a suitable metric, for all $t$, $d(H(\pi_t)u,H(\pi_t)v)<d(u,v)$. As a result, it is known that a unique fixed point exists.

Now, the theorem states:

The infinite horizon values exist for every policy: $v_t(\pi)$ exists and is finite for every $t$.

However, it is not clear to me how this can be established. What the fixed point result seems to state is that for arbitrary $\epsilon>0$, and an arbitrary value function $v$, there exists a sufficiently large index $M$ such that if we have $v_M:=v\in \mathbb{R}^S$, we can recursively obtain $v_{M-1}=H(\pi_{M-1})v_M$, and then sequentially iteratively obtain previous time period's value function until we get $v_0$ and this $v_0$ is going to be $\epsilon$-close to the fixed point in metric $d()$.

This theorem, however, seems to want one to prove the result in the other direction, beginning from a particular $t$ and then going to $t+1, t+2,...$. Any pointers would be appreciated.

Tryer
  • 121
  • 2