Using $\alpha$ to control the convergence rate

Decreasing the parameter $\alpha$ causes the noise influence to decrease, but on the other hand the convergence is slower. Usually we will use $\alpha$-values such that: $\lim_{i \rightarrow \infty} \alpha_{i} = 0$.

Let us look at one Typical Example:

• Let V be a random variable dependent of the parameter r.
• There exists a probability function : P(V|r)
• A function g(r,V)

We would like to solve : E_V[g(r,V)]=r, where the expectation regards p(V|r).

We can write iterations of the form :

$r_{n+1} \leftarrow (1-\alpha)r_{n}+\alpha E[g(r_{n},V)].$

Computing the expected value can be complicated, but if P(V|r) is known and can be simulated or sampled, we can get samples ${\tilde{V}}$ and use them to evaluate E_V[g(r,V)]. For example we can sample $\tilde{V_{1}},...,\tilde{V_{k}}$ and compute $\frac{1}{k}\sum_{i=1}^{k} g(r_{n},\tilde{V_{i}})$ as the observed average.

If K is large, then the average will be close to its expected value E_V[g(r,V)] and in such a case we should expect a similar behaviour. The other extrem is the case of k=1 (one sample), $\tilde{V_{n}}$ .

$r_{n+1} \leftarrow (1-\alpha_{n})r_{n}+\alpha_{n} g(r_{n},\tilde{V_{n}})$ where $\tilde{V_{n}}$ is distributed by p(v|r).

This algorithm is called the Robbins-Morro algorithm . The iterations can be written as:

$r_{n+1} \leftarrow (1-\alpha_{n})r_{n} + \alpha_{n} [E(g(r,V) + g(r,\tilde{V}) - E(g(r,V)]$

where we can define :
Hr_n = E[g(r_n,V)],
$W_{n} = g(r,\tilde{V}) - E(g(r,V)$. (and E[W_n] = 0 by definition of ${\tilde{V}}$)
This implies that for each $s\in S$ we have,

$r_{n+1}(s) \leftarrow (1-\alpha_{n})r_{n}(s) + \alpha_{n}(s) [(Hr_{n})(s) + % W_{n}(s)]$.