SA example

Example of Stochastic Approximation

Review

Remember Law of large numbers, the mean estimation problem:

• consider a random variable $X$
• suppose that we collected a sequence of i.i.d. samples $\{x_j{\}}_{j=1}^N$ from $X$
• aim is to estimate $\mathbb{E}[X]$
• The expectation of $X$ can be approximated by $$\mathbb{E}[X]\approx \bar{x}=\frac{1}{N}\sum _{j=1}^N{x}_j$$
• the basic idea of Monte Carlo estimation
• ${\lim }_{N\to \infty }\bar{x}=\mathbb{E}[X]$

重申：为什么这么关注mean estimation？

之前已经在这里提过一次，当时是从环境模型的两个概率分布的角度出发（因为我们希望用一些别的什么东西替代环境模型的概率形式，这个东西其实就是$\mathbb{E}$）。其实除了这个角度，我们大部分在强化学习问题中的值比如action values和gradients都是由expectation的形式所定义的。

New question: how to calculate the mean $\bar{x}$?

1. Non-incremental: trivial(平常的), wait until all samples are collected, then calculate the average
   • drawback: cannot get the estimation during the collecting process
2. Incremental: update the average after each sample

Incremental mean estimation

Suppose $w_{k+1}$ is the average of the first $k$ samples

$$w_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i,k=1,2,\dots$$

hence

$$w_k=\frac{1}{k-1}\sum _{i=1}^{k-1}{x}_i,k=2,3,\dots$$

Then we can express $w_{k+1}$ in terms of $w_k$ and $x_k$

$$\begin{array}{rl}{w}_{k+1}& =\frac{1}{k}\sum _{i=1}^k{x}_i\\ & =\frac{1}{k}\left(x_k+\sum _{i=1}^{k-1}{x}_i\right)\\ & =\frac{1}{k}\left(x_k+(k-1)w_k\right)\\ & =w_k-\frac{1}{k}(w_k-x_k)\end{array}$$

Verification:

$$\begin{array}{rl}{w}_2& =x_1\\ w_3& =w_2-\frac{1}{2}(w_2-x_2)=\frac{1}{2}(x_1+x_2)\\ w_4& =w_3-\frac{1}{3}(w_3-x_3)=\frac{1}{3}(x_1+x_2+x_3)\\ ⋮& \\ w_{k+1}& =\frac{1}{k}\sum _{i=1}^k{x}_i\end{array}$$

Remarks:

$$\begin{array}{rl}{w}_{k+1}& =w_k-\frac{1}{k}(w_k-x_k)\\ & =(1-\frac{1}{k})w_k+\frac{1}{k}{x}_k\end{array}$$

• mean estimate can be obtained immediately once a sample is received
• ${\lim }_{k\to \infty }{w}_k=\mathbb{E}[X]$

A more general form(also known as exponential moving average, EMA, used to estimate the mean of a time series, e.g., smoothing stock prices):

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k(w_k-x_k)\\ & ={\alpha }_k{x}_k+(1-{\alpha }_k)w_k\end{array}$$

• where $\frac{1}{k}$ is replaced by ${\alpha }_k$
• if $\{{\alpha }_k\}$ satisify some mild conditions, then ${\lim }_{k\to \infty }{w}_k=\mathbb{E}[X]$
• this algorithm is a special SA algorithm, and also a special SGD algorithm
• in the next lecture, we will see TD have simliar (but more complex) form

EMA和SGD的相似性

确实非常相似，如果将$(w_{k-1}-x_k)$视作梯度的话，如果是batch的形式，和平时我们torch框架中的反向传播就更像了。