# 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?

## 1 Answer

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.

• Thanks, excellent! After a little digging one other alternative way is to reference a super-martingale convergence theorem for the sum missing the $-X_t$ term to get convergence and then this forces the $\sum X_t$ to be finite A.S. – FourierFlux Apr 19 '20 at 7:10