Proof of extended supermartingale convergence theorem There is a supermartingale convergence theorem which is often cited in texts which use Stochastic Approximation Theory and Reinforcement Learning, in particular the famous book "Neuro-dynamic Programming" the theorem is:
"Let $Y_t, X_t, Z_t, t = 1,2,3,....$ be three sequences of random variables and let $\mathcal{F_t}$ be sets of random variables such that $\mathcal{F_t} \subset \mathcal{F_{t+1}}$ for all t, suppose that:
(a) The random variables $Y_t, X_t, Z_t$ are nonnegative and are functions of the random variables in $\mathcal{F}_t$
(b) For each $t$ we have $E[Y_{t+1}|\mathcal{F_t}] \leq Y_t - X_t +Z_t$
(c) $\sum_{t=0}^\infty Z_t \lt \infty$ 
Then:
$\sum_{t=0}^{\infty}X_t \lt \infty $ and there exists a nonnegative random variable $Y$ such that $Y_t \rightarrow Y$ with probability 1."
The problem is, I can't find any proofs of this anywhere. Most texts on probability theory prove the standard Martingale Convergence Theorem but I feel this is a big step from that.
Can anyone direct me to a source which proves the above or write out a proof from the standard convergence theorem?  
 A: Here's one approach. 
First notice that 
$$
R_t: = Y_{t} + \sum_{i=1}^{t-1} X_i - \sum_{i=1}^{t-1} Z_i
$$
is a supermartingale, since
$$
R_{t+1} - R_t = Y_{t+1} - Y_t + X_t - Z_t, 
$$
giving
$$
E(R_{t+1} - R_t | \mathcal{F}_t) = E (Y_{t+1} | \mathcal{F}_t) - Y_t + X_t - Z_t 
$$
which is less than or equal to $0$ with probability $1$, by (b). 
Now, we don't have a fixed lower bound for the supermartingale $R$, so we can't apply the convergence theorem directly. 
However, for any $a>0$, consider the stopping time
$$
\tau_a = \inf\{t: \sum_{i=1}^t Z_i>a\},
$$
with $\tau_a=\infty$ if $\sum_{i=1}^t Z_i\leq a$ for all $t$.
We can define
$$
R^{(a)}(t):=R(t\wedge \tau_a)=
\begin{cases}
R_t&\text{ if }t<\tau_a\\
R_{\tau_a}&\text{ if }t\geq \tau_a
\end{cases}.
$$
$R^{(a)}$ is also a supermartingale for any $a$, and $R^{(a)}(t)$ is bounded below by $-a$. 
So by the martingale convergence theorem, for any given $a$, $R^{(a)}(t)$ converges to some finite limit with probability $1$. By countable additivity, 
we get that with probability $1$, $R^{(a)}(t)$ converges to a finite limit for all $a\in\mathbb{Z}$. 
But if $\sum_{i=0}^\infty Z_i<\infty$, 
which from (c) we assume happens with probability $1$, then for all large enough $a\in\mathbb{Z}$,
we have $\tau_a=\infty$, and so $R^{(a)}(t)=R(t)$ 
for all $t$. Since we know $R^{(a)}(t)$ converges, we also get that $R(t)$ converges.
Finally, since $R(t)$ converges and $\sum_{i=0}^{t-1} Z_i$ converges, we also have that $Y_t+\sum_{i=1}^{t-1} X_i$ converges. Since $\sum_{i=1}^{t-1} X_i$ is non-decreasing in $t$, and $Y_t$ is non-negative for all $t$, the only way this can happen is if $Y_t$ and $\sum_{i=1}^{t-1} X_i$ both converge, as required. 
A: As far as I know this statement was first proved by Robbins and Siegmund in their paper "A convergence theorem for non negative almost supermartingales and some applications" from 1971.
