7
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Apr 19, 2020 at 7:10
1
$\begingroup$

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.

$\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.