Mean Estimation Algorithms

Sources:

1. Shiyu Zhao. Chapter 5: Monte Carlo Methods. Mathematical Foundations of Reinforcement Learning
2. Shiyu Zhao. Chapter 6: Stochastic Approximation. Mathematical Foundations of Reinforcement Learning

Mean estimation: compute $\mathbb{E}[X]$ using $\left\{x_k\right\}$ $$w_{k+1}=w_k-\frac{1}{k}(w_k-x_k)$$

Mean estimation problem

Consider a random variable $X$ that can take values from a finite set of real numbers denoted as $\mathcal{X}$, suppose that our task is to calculate the mean or expected value¹ of $X$, i.e., $\mathbb{E}[X]$.

Two approaches can be used to calculate $\mathbb{E}[X]$.

Model based case

The first approach is model-based. Here, the model refers to the probability distribution of $X$. If the model is known, then the mean can be directly calculated based on the definition of the expected value: $$\begin{array}{}\text{(1)}& \mathbb{E}[X]=\sum _{x\in \mathcal{X}}p(x)x\end{array}$$

Model free case

The second approach is model-free. When the probability distribution (i.e., the model) of $X$ is unknown, suppose that we have some samples $\{x_1,x_2,\dots ,x_n\}$ of $X$. Then, the mean can be approximated as $$\begin{array}{}\text{(2)}& \mathbb{E}[X]\approx \overline{x}\triangleq \frac{1}{n}\sum _{j=1}^n{x}_j.\end{array}$$

When $n$ is small, this approximation may not be accurate. However, as $n$ increases, the approximation becomes increasingly accurate. When $n\to \mathrm{\infty }$, we have $\overline{x}\to \mathbb{E}[X]$.

This is guaranteed by the law of large numbers (L.L.N.): the average of a large number of samples is close to the expected value.

This is called the Monte Carlo method.

Law of large numbers

For a random variable $X$, suppose that ${\left\{x_i\right\}}_{i=1}^n$ are some i.i.d. samples. Let $\overline{x}=$ $\frac{1}{n}\sum _{i=1}^n{x}_i$ be the average of the samples. Then, $$\begin{array}{rl}\mathbb{E}[\overline{x}]& =\mathbb{E}[X],\\ \mathrm{var}[\overline{x}]& =\frac{1}{n}\mathrm{var}[X].\end{array}$$

The above two equations indicate that $\overline{x}$ is an unbiased estimate of $\mathbb{E}[X]$, and its variance decreases to zero as $n$ increases to infinity.

The proof is given below.

First, $\mathbb{E}[\overline{x}]=\mathbb{E}\left[\sum _{i=1}^n{x}_i/n\right]=\sum _{i=1}^n\mathbb{E}\left[x_i\right]/n=\mathbb{E}[X]$, where the last equability is due to the fact that the samples are identically distributed (that is, $\mathbb{E}\left[x_i\right]=\mathbb{E}[X]$ ).

Second, $$\mathrm{var}(\overline{x})=\mathrm{var}\left[\sum _{i=1}^n{x}_i/n\right]=\sum _{i=1}^n\mathrm{var}\left[x_i\right]/n^2=(n\cdot \mathrm{var}[X])/n^2=\mathrm{var}[X]/n,$$ where the second equality is due to the fact that the samples are independent, and the third equability is a result of the samples being identically distributed (that is, $\mathrm{var}\left[x_i\right]=\mathrm{var}[X]$).

Iterative mean estimation

There are two methods to compute equation $\text{(2)}$. The first method is non-incremental method, we have to collect all the samples first and then calculates the average. If the number of samples is large, we may have to wait for a long time until all of the samples are collected.

Alternatively, we can take the second method. It is called iterative mean estimation and is incremental. Specifically, suppose that $$w_{k+1}\triangleq \frac{1}{k}\sum _{i=1}^k{x}_i,k=1,2,\dots$$ and hence, $$w_k=\frac{1}{k-1}\sum _{i=1}^{k-1}{x}_i,k=2,3,\dots$$

By its definition, we know $w_{k+1}=\overline{x}\approx \mathbb{E}[X]$ and $w_{k+1}\to \mathbb{E}[X]$. Meanwhile, $w_{k+1}$ can be expressed in terms of $w_k$ as $$w_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i=\frac{1}{k}(\sum _{i=1}^{k-1}{x}_i+x_k)=\frac{1}{k}((k-1)w_k+x_k)=w_k-\frac{1}{k}(w_k-x_k).$$ Therefore, we obtain the following incremental algorithm: $$\begin{array}{}\text{(3)}& w_{k+1}=w_k-\frac{1}{k}(w_k-x_k).\end{array}$$

This algorithm can be used to calculate the mean $\overline{x}$ in an incremental manner. It can be verified that $$\begin{array}{rl}{w}_1& =x_1,\\ w_2& =w_1-\frac{1}{1}(w_1-x_1)=x_1,\\ w_3& =w_2-\frac{1}{2}(w_2-x_2)=x_1-\frac{1}{2}(x_1-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}$$

The advantage of $\text{(3)}$ is that the average can be immediately calculated every time we receive a sample. This average can be used to approximate $\overline{x}$ and hence $\mathbb{E}[X]$.

Furthermore, consider an algorithm with a more general expression: $$w_{k+1}=w_k-{\alpha }_k(w_k-x_k).$$

It is the same as $\text{(3)}$ except that the coefficient $1/k$ is replaced by ${\alpha }_k>0$. Since the expression of ${\alpha }_k$ is not given, we are not able to obtain the explicit expression of $w_k$ as in $\text{(???)}$. However, we will show in the next articlethat, if $\left\{{\alpha }_k\right\}$ satisfies some mild conditions, $w_k\to \mathbb{E}[X]$ as $k\to \mathrm{\infty }$. This illustrates that the iterative mean estimation is a special form of RM algorithm.

---

1. In this RL serie, we use the terms expected value, mean, and average interchangeably.↩︎