2.4 Tracking NonStionary Problem

If we want our $Q_k(a)$ not to be too influenced by the past, we can change our StepSize by a static value. Let's define StepSize as $\alpha$

$\begin{align} Q_{k+1} &= Q_k + \alpha[R_k - Q_k]\\ &= \alpha R_k + (1 - \alpha)Q_k\\ &= \dotsi\\ &= (1 - \alpha)^k Q_1 + \sum_{i=1}^{k} \alpha (1 - \alpha)^{k-1} R_i \end{align}$

We call this a weighted average because the sum of the weights is : $\begin{align} (1 - \alpha)^k + \sum_{i=1}^{k} \alpha (1-\alpha)^{k-i} = 1 \end{align}$

This is called and exponential, recency-weighted average. Sometimes it is convenient to vart the step-size parameter from step to step.

A well-known result in stochastic approximation theory gives us the conditions required to assure convergence with probability 1.

$\begin{align} \sum_{k=1}^{\infty} \alpha_k(a) = \infty \end{align}$ and $\begin{align} \sum_{k=1}^{\infty} \alpha^2_k(a) < \infty \end{align}$

The first condition is required to guarantees that the steps are large enough to eventually overcome any initial conditions or random fluctuations. The second condition guarantees that eventually the steps become small enough to assure convergence