Let be an arbitrary state-space and denote by the set of value functions over (i.e., the set of bounded functions), and let be an arbitrary contraction mapping with (unique) fixed point .

Let be a sequence of stochastic operators. The second argument of is intended to modify the first one, in order to get a better approximation of . Formally, let be an arbitrary value function and let . is said to approximate at with probability one over , if uniformly over .

- for all
and all ,
- for all
and all ,
- for all , converges to zero uniformly in as increases; and,
- there exists
such that for all and large enough ,

The proof can be found in [Szepesvári and Littman(1996)]. We cite here the lemma, which is the base of the proof, since our generalization concerns this lemma.

where , with probability one for some , and for all , and w.p.1. Assume that for all , uniformly in w.p.1 and w.p.1. Then converges to 0 w.p.1 as well.