   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