在我最近研究的stochastic bandit问题中，假设每个arm得到的reward是服从一个特定的分布，最后需要研究的regret函数与分布的均值相关，因此如何从目前得到的reward信息来估计真实的均值在这个研究中是一个很基本的问题。具体可以参见我之前的一篇文章[机器学习－bandit问题简介]。当然普遍来讲，对于均值的准确有效估计是一个很基本的问题，在各种stochastic问题中都有它的身影。
在本篇文章中，我们主要考虑n个独立同分布的随机变量的值与实际的均值µ之间的关系。
收敛性
首先是最著名的[中心极限定理, wikipedia]和[大数定律, wikipedia]，它们奠定了统计估计的基础。
这三个定理非常著名，本科的概率论课程都会讲到，它们奠定了了样本均值最终会收敛到实际均值的理论基础，有了这样的理论保证，我们才可以用足够多次的重复实验来估计实际均值。但是这三个定理更多地停留在理论层面上，并没有提到在“多少次”的重复之后，样本均值可以“在什么程度上”逼近实际均值，对我们的实际应用并不能产生具体的指导意义。
估计的界
在这个[重对数定律, wikipedia]的叙述中，要求随机变量的均值为0，方差为1，但根据中心极限定理，可以很容易地将此定理拓展到一般的情况。从大数定律中我们得到Sn/n几乎处处收敛为0，依概率收敛为0，即Sn的界为o(n)，而这个定理告诉我们Sn的阶比√n要大，即Sn/√n不收敛到0。
这个就是著名的[Markov不等式, wikipedia]，它如此著名是因为定理本身对随机变量没有太多的要求，但又可以得到一个基本的估计，简单地说，它如此著名就是因为它好用。但是在定理中要求随机变量是正的，拓展到一般情况，有它的一个著名推论[Chebyshev不等式, wikipedia]。
这三个定理在一定程度上都可以用来刻画样本均值和实际均值差的界限。但是第一个定理和收敛性中的讨论一样，同样没有告诉我们收敛程度和次数n之间的关系。而切比雪夫不等式的使用中涉及到方差，但是很多时候我们是没有方差的信息的，而且切比雪夫不等式给出的界略粗糙，有时候应用乏力。
Chernoff-Hoeffding Bound
其中最后的结果交换样本均值与实际均值的顺序也成立。之所以用这个定理[wikipedia]做标题实在是因为它太好用了，在几乎所有stochastic bandit regret的估计中都能见到它的身影。原因就在于它不需要方差的信息，而且收敛的程度可以用n显式表达，唯一的限制就是随机变量的值是有界的，而在bandit问题中无界的reward是无法考虑的，所以自然满足。
当分布满足一些额外的条件时，例如sub-Gaussion，可以由凸分析得到一些其他的估计，这些下次再谈。
