5

There is a supermartingale convergence theorem which is often cited in texts which use Stochastic Approximation Theory and Reinforcement Learning, 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?

maxical
  • 571
  • 2
    Condition $c$ is : $\sum Z_t < \infty$ a.s. ,right? – Sarvesh Ravichandran Iyer Apr 18 '20 at 03:53
  • 1
    I have not seen a similar statement any where and I attempted a proof and failed. But I like the question, +1. Having said that, we should first prove this with as strong conditions as possible, and then loosen it. – Sarvesh Ravichandran Iyer Apr 18 '20 at 07:04
  • Yes, the proof is cited in a rather famous book called "Neuro-dynamic programming" in the chapter on stochastic iterative algorithms. Ironically it cites Ash and another probability book, but neither contain this theorem. – maxical Apr 18 '20 at 10:16
  • @астонвіллаолофмэллбэрг so I had an idea, there is a theorem about the convergence of super-martingales where the $-X_t$ is missing. Since the negative sign only reduces the martingale it can be removed right? And so that result should show convergence. What's left is showing $ \sum X_t \lt \infty$ But this should be easy right? since $Y_t$ converges to a R.V we must have the sum be less than $\infty$ right? https://math.stackexchange.com/questions/2843848/prove-a-s-convergence-of-x-n-n-satisfying-ex-n1-mid-f-n-leq-x-ny-n – maxical Apr 19 '20 at 01:02
  • 1
    I thought of doing something similar, but in order to apply that, we'd need the $Z_t$ to be integrable - is that supposed to be an assumption of your theorem? Otherwise I think that should work fine. – Nate Eldredge Apr 19 '20 at 01:27
  • There isn't a discussion on it but I figure that's a reasonable assumption. – maxical Apr 19 '20 at 01:31
  • Yes I think your argument makes sense. Let us try to make it rigorous. – Sarvesh Ravichandran Iyer Apr 19 '20 at 03:28

0 Answers0