MC example

Example of Monte-Carlo

Flip a coin:

The result is denoted as a random variable X

• head X=1
• tail X=-1

The aim is to compute estimation $\mathbb{E}(X)$

With model (model-based)

suppose the probabilistic model is known as

$$p(X=1)=0.5,p(X=-1)=0.5$$

then by definition

$$\begin{array}{rl}\mathbb{E}(X)& =\sum _{x}x\cdot p(X=x)\\ & =1\cdot p(X=1)+(-1)\cdot p(X=-1)=0\end{array}$$

distribution怎么才能知道呢

对于这种概率分布的方法我们是没有办法去知道精确的现实世界中的真实分布的，只能是模拟的抛硬币，然后统计结果，然后估计出来的。

Without model (model-free)

idea: sample and average

• flip the coin $N$ times, and then calculate the average of the results
• suppose we get a sample sequence $\{x_1,x_2,\dots ,x_N\}$, then the estimation of $\mathbb{E}(X)$ is

$$\hat{\mathbb{E}}(X)\approx \bar{x}=\frac{1}{N}\sum _{i=1}^N{x}_i$$

this is the idea of $\text{Monte Carlo}$ estimation

Monte Carlo准确吗

由于是随机的，所以是不准确的，但是随着$N$的增大，$\hat{\mathbb{E}}(X)$会越来越接近$\mathbb{E}(X)$

Law of large numbers

For a random variable $X$, suppose $\{x_j{\}}_{j=1}^N$ is some i.i.d. samples from $X$, then let $\bar{x}=\frac{1}{N}{\sum }_{j=1}^N{x}_j$ be the average of the samples, then

$$\begin{array}{rl}\mathbb{E}(\bar{x})& =\mathbb{E}(X)\\ \mathrm{Var}(\bar{x})& =\frac{\mathrm{Var}(X)}{N}\end{array}$$

• For detail, see Proof

为什么要用i.i.d.的样本

i.i.d. (independent and identically distributed) 独立同分布的样本是为了保证样本的独立性，如果样本之间有关联，那么就会导致估计的不准确

Summary

• MC estimation refers to a broad class of techniques that use repeated random sampling to solve approximation problems
• MC estimation is a model-free method, not require the model

为什么我们那么关心所谓的mean estimation $\mathbb{E}$

因为前面所推出的Bellman equation或者是vi还是pi的算法中所设计的state value和action value都是以expectaion的形式给出的，记得我们之前都是要通过两个分布$p(s^{\prime },r|s,a)$和$p(s^{\prime }|s,a)$来计算的，但是现在我们学了这张之后就可以通过MC来估计出来了，所以这个是非常重要的。(just sample and average)