MAB问题

##Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards

        在一个多重赌博机的匪徒（MAB）问题中，赌徒需要在每一场比赛中选择一个K手臂，每个手臂的特点是未知的奖励分配。奖励的实现只有在选择一只手臂时才被观察到，并且赌徒的目标是在某个给定的T期范围内使他的累计预期收益最大化。为此，赌徒需要获得武器（探索）的信息，同时优化即时奖励（开发）;由于这种交易而支付的价格通常被称为遗憾，主要的问题是这个价格是多少可以作为地平线长度T的函数。当奖励分配没有改变时，已经广泛地研究了这个问题时间;这个假设支持对遗憾的锐利表征，但在实际环境中经常被违反。在本文中，我们关注的是一个MAB公式，它允许在广泛的时间不确定性的奖励，同时仍然保持数学的易处理性。我们通过建立可允许的奖励\变化的程度和最小可实现的遗憾之间的直接联系，来充分描述这类人与生物圈问题的（遗憾）复杂性。我们的分析将两个相当不相同的文献之间的关系：对抗和随机的MAB框架。

MAB简介：

        典型的情况是：赌博机有不止一个推臂，每个推臂的收益满足一定的统计分布，当赌徒推动其中一个推臂时，便能获得一定的报酬。明显，这个报酬是从推臂的相关分布派生的一个随机变量，而赌徒在最初无法得知推臂的报酬的分布情况。赌徒的目的是获得最大的收益。由于每次试验只能选择其中一个推臂，若赌徒选择其中某个推臂的次数达到一定值，那么就可以得出该推臂报酬对应的统计分布情况。同时，如果赌徒只使用其中某一个或者某几个推臂，那么他就减少了使用新的推臂的机会，而这些推臂以一定的概率可能具有更高的报酬。那么赌徒面临的问题是：选择已知报酬均值最高的推臂，来获得较高的报酬，或选择其他未知分布的推臂，以谋求获得可能存在的更高的报酬。这是选择已知推臂或未知推臂的两难问题。

        该问题由Robbins最早提出，它将多臂赌博机看做一个Agent的统计决策模型，将探索与利用的两难问题变为Agent在最优化决策的同时提升知识。