Next: Event-learning with a background Up: -MDPs: Learning in Varying Previous: Sampling from Near-identical Distributions

Stochastic Processes with Non-diminishing Perturbations

In this appendix we prove the lemma required by the proof of Theorem 3.3:

Lemma C.1   Let be an arbitrary set, , and consider the sequence

where , there exists a bound such that with probability one, and for all . Assume that for all , uniformly in w.p.1 and w.p.1. Then w.p.1.

Proof. We will prove that for each there exists an index such that

 (15)

Fix arbitrarily. Furthermore fix a sequence of numbers ( ) to be chosen later.

Let and . Then

Thus, we have that . Now define . Since , . Consequently, if , then holds for all , as well. From now on, we will assume that .

Let . Since , the process

with estimates the process from above: holds for all . The process converges to w.p.1 uniformly over , so

w.p.1. Since , there exists an index , for which if then with probability . The proof goes on by induction: assume that up to some index we have found indices such that when then

 (16)

holds with probability . Now let us restrict ourselves to those events for which inequality (16) holds. Then we see that the process

bounds from above from the index . The process converges to w.p.1 uniformly over , so the above argument can be repeated to obtain an index such that (16) holds for with probability .

Since , and . So there exists an index for which . Then inequality (15) can be satisfied by setting so that holds and letting .

Next: Event-learning with a background Up: -MDPs: Learning in Varying Previous: Sampling from Near-identical Distributions