##Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards
????????在一個(gè)多重賭博機(jī)的匪徒（MAB）問(wèn)題中溢豆，賭徒需要在每一場(chǎng)比賽中選擇一個(gè)K手臂芦疏，每個(gè)手臂的特點(diǎn)是未知的獎(jiǎng)勵(lì)分配壳贪。獎(jiǎng)勵(lì)的實(shí)現(xiàn)只有在選擇一只手臂時(shí)才被觀察到端圈，并且賭徒的目標(biāo)是在某個(gè)給定的T期范圍內(nèi)使他的累計(jì)預(yù)期收益最大化。為此隙笆，賭徒需要獲得武器（探索）的信息吐限，同時(shí)優(yōu)化即時(shí)獎(jiǎng)勵(lì)（開(kāi)發(fā)）;由于這種交易而支付的價(jià)格通常被稱為遺憾，主要的問(wèn)題是這個(gè)價(jià)格是多少可以作為地平線長(zhǎng)度T的函數(shù)漂坏。當(dāng)獎(jiǎng)勵(lì)分配沒(méi)有改變時(shí)，已經(jīng)廣泛地研究了這個(gè)問(wèn)題時(shí)間;這個(gè)假設(shè)支持對(duì)遺憾的銳利表征媒至，但在實(shí)際環(huán)境中經(jīng)常被違反顶别。在本文中，我們關(guān)注的是一個(gè)MAB公式拒啰，它允許在廣泛的時(shí)間不確定性的獎(jiǎng)勵(lì)筋夏，同時(shí)仍然保持?jǐn)?shù)學(xué)的易處理性。我們通過(guò)建立可允許的獎(jiǎng)勵(lì)\變化的程度和最小可實(shí)現(xiàn)的遺憾之間的直接聯(lián)系图呢，來(lái)充分描述這類人與生物圈問(wèn)題的（遺憾）復(fù)雜性条篷。我們的分析將兩個(gè)相當(dāng)不相同的文獻(xiàn)之間的關(guān)系：對(duì)抗和隨機(jī)的MAB框架。
MAB簡(jiǎn)介：
????????典型的情況是：賭博機(jī)有不止一個(gè)推臂蛤织，每個(gè)推臂的收益滿足一定的統(tǒng)計(jì)分布赴叹，當(dāng)賭徒推動(dòng)其中一個(gè)推臂時(shí)，便能獲得一定的報(bào)酬指蚜。明顯乞巧，這個(gè)報(bào)酬是從推臂的相關(guān)分布派生的一個(gè)隨機(jī)變量，而賭徒在最初無(wú)法得知推臂的報(bào)酬的分布情況摊鸡。賭徒的目的是獲得最大的收益绽媒。由于每次試驗(yàn)只能選擇其中一個(gè)推臂，若賭徒選擇其中某個(gè)推臂的次數(shù)達(dá)到一定值免猾，那么就可以得出該推臂報(bào)酬對(duì)應(yīng)的統(tǒng)計(jì)分布情況是辕。同時(shí)，如果賭徒只使用其中某一個(gè)或者某幾個(gè)推臂猎提，那么他就減少了使用新的推臂的機(jī)會(huì)获三，而這些推臂以一定的概率可能具有更高的報(bào)酬。那么賭徒面臨的問(wèn)題是：選擇已知報(bào)酬均值最高的推臂锨苏，來(lái)獲得較高的報(bào)酬疙教，或選擇其他未知分布的推臂，以謀求獲得可能存在的更高的報(bào)酬伞租。這是選擇已知推臂或未知推臂的兩難問(wèn)題贞谓。
????????該問(wèn)題由Robbins最早提出，它將多臂賭博機(jī)看做一個(gè)Agent的統(tǒng)計(jì)決策模型葵诈，將探索與利用的兩難問(wèn)題變?yōu)锳gent在最優(yōu)化決策的同時(shí)提升知識(shí)裸弦。
