0
$\begingroup$

I am studying Stochastic Dynamic Programming using Sheldon Ross's book, "Introduction to Stochastic Dynamic Programming." In the book, Ross defines a dynamic programming algorithm to minimize cost for unbounded costs per stage problems, and it's represented as follows:

Let $V_0(i) = 0$, and for $n > 0$, $$V_n(i) = min_a(C(i,a) + Σ_j P_{i,j}(a)V_{n-1}(j)),$$ where $C(i,a) \geq 0$ for every $i$.

The book claims that $V_n(i) \leq V_{n+1}(i)$, where $V_{n}(i)$ represents the minimal expected cost for an n-stage problem starting in $i$. The key observation here is that all costs are nonnegative, implying that $V_n(i)$ must be less than $V_{n+1}(i)$.

I've been trying to prove this inequality using mathematical induction, but I've hit a roadblock in my efforts.

Base Case ($n = 0$): For $n = 0$, we have: $V_0(i) = 0$ (given). Now, we need to prove that $V_0(i) \leq V_1(i)$. $V_1(i) = min_a(C(i,a) + ∑_j P_{i,j}(a) V_0(j))$ Since $V_0(j) = 0$ for all $j$, we can simplify this to: $V_1(i) = min_a(C(i,a))$.

This is a minimum value over a set of non-negative values. Since $C(i,a)$ is non-negative for all $i$ and $a$, the minimum value can only be zero or a positive value. Therefore, $V_1(i)$ is either 0 or a positive value. So, in the base case, $V_0(i) \leq V_1(i)$.

Inductive Hypothesis: Assume that for some arbitrary $n$, $V_n(i) \leq V_{n+1}(i)$.

Inductive Step: We want to show that $V_{n+1}(i) \leq V_{n+2}(i)$. We can use the formula for $V_{n+1}(i)$: $V_{n+1}(i) = min_a(C(i,a) + ∑_j P_{i,j}(a)V_n(j))$

I'm looking for assistance in completing the proof by induction.

$\endgroup$

1 Answer 1

2
$\begingroup$

How about something like this?

Assume that the statement is true for all values of $n \le K$, and that $C_i(a)$, $P_{i,j}(a)$ are positive functions of $a$. Then

\begin{eqnarray*} V_{K+1}(i) & = & \min_a \left\{C_i(a) + \sum_j P_{i,j}(a) V_{K}(j)\right\} \\ & \ge & \min_a \left\{C_i(a) + \sum_j P_{i,j}(a) V_{K-1} (j) \right\} \\ & = & V_K (i) \end{eqnarray*}

The second line follows from the induction hypothesis, and the third from the definition.

$\endgroup$

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.