在我最近研究的stochastic bandit問題中，假設(shè)每個arm得到的reward是服從一個特定的分布，最后需要研究的regret函數(shù)與分布的均值相關(guān)穿撮，因此如何從目前得到的reward信息來估計真實(shí)的均值在這個研究中是一個很基本的問題。具體可以參見我之前的一篇文章[機(jī)器學(xué)習(xí)－bandit問題簡介]。當(dāng)然普遍來講谷异，對于均值的準(zhǔn)確有效估計是一個很基本的問題，在各種stochastic問題中都有它的身影锦聊。
在本篇文章中歹嘹，我們主要考慮n個獨(dú)立同分布的隨機(jī)變量的值與實(shí)際的均值μ之間的關(guān)系。
收斂性
首先是最著名的[中心極限定理, wikipedia]和[大數(shù)定律, wikipedia]孔庭，它們奠定了統(tǒng)計估計的基礎(chǔ)尺上。
這三個定理非常著名，本科的概率論課程都會講到圆到，它們奠定了了樣本均值最終會收斂到實(shí)際均值的理論基礎(chǔ)怎抛，有了這樣的理論保證，我們才可以用足夠多次的重復(fù)實(shí)驗(yàn)來估計實(shí)際均值芽淡。但是這三個定理更多地停留在理論層面上马绝，并沒有提到在“多少次”的重復(fù)之后，樣本均值可以“在什么程度上”逼近實(shí)際均值挣菲，對我們的實(shí)際應(yīng)用并不能產(chǎn)生具體的指導(dǎo)意義富稻。
估計的界
在這個[重對數(shù)定律, wikipedia]的敘述中掷邦，要求隨機(jī)變量的均值為0，方差為1唉窃，但根據(jù)中心極限定理耙饰，可以很容易地將此定理拓展到一般的情況。從大數(shù)定律中我們得到Sn/n幾乎處處收斂為0纹份，依概率收斂為0苟跪，即Sn的界為o(n)，而這個定理告訴我們Sn的階比√n要大蔓涧，即Sn/√n不收斂到0件已。
這個就是著名的[Markov不等式, wikipedia]，它如此著名是因?yàn)槎ɡ肀旧韺﹄S機(jī)變量沒有太多的要求元暴，但又可以得到一個基本的估計篷扩，簡單地說，它如此著名就是因?yàn)樗糜密哉怠５窃诙ɡ碇幸箅S機(jī)變量是正的鉴未，拓展到一般情況，有它的一個著名推論[Chebyshev不等式, wikipedia]鸠姨。
這三個定理在一定程度上都可以用來刻畫樣本均值和實(shí)際均值差的界限铜秆。但是第一個定理和收斂性中的討論一樣，同樣沒有告訴我們收斂程度和次數(shù)n之間的關(guān)系讶迁。而切比雪夫不等式的使用中涉及到方差连茧，但是很多時候我們是沒有方差的信息的，而且切比雪夫不等式給出的界略粗糙巍糯，有時候應(yīng)用乏力啸驯。
Chernoff-Hoeffding Bound
其中最后的結(jié)果交換樣本均值與實(shí)際均值的順序也成立。之所以用這個定理[wikipedia]做標(biāo)題實(shí)在是因?yàn)樗糜昧怂盥停趲缀跛衧tochastic bandit regret的估計中都能見到它的身影罚斗。原因就在于它不需要方差的信息，而且收斂的程度可以用n顯式表達(dá)宅楞，唯一的限制就是隨機(jī)變量的值是有界的惰聂，而在bandit問題中無界的reward是無法考慮的，所以自然滿足咱筛。
當(dāng)分布滿足一些額外的條件時，例如sub-Gaussion杆故，可以由凸分析得到一些其他的估計迅箩，這些下次再談。
