Partial Monitoring-Classification, Regret Bounds, and Algorithms
Partial Monitoring-Classification, Regret Bounds, and Algorithms
复制标题
DOI：
10.1287/moor.2014.0663
复制
发表时间：
2014-11-01
影响因子：
1.7
通讯作者：
Szepesvari, Csaba
中科院分区：
文献类型：
--
作者：
Bartok, Gabor;Foster, Dean P.;Szepesvari, Csaba
在部分监控游戏中，学习者反复选择一个动作，环境以一个结果作出反应，然后学习者遭受损失并收到反馈信号，这两者都是动作和结果的固定函数。学习者的目标是将他的后悔降到最低，这是他累积的总损失和事后看来最好的固定动作的总损失之间的差异。本文刻画了具有有限多个动作和结果的部分监控对策的极小极大遗憾。结果表明，这类博弈的最小最大遗憾要么为零，要么为T-1/2，T-2/3，或者T为常数和对数因子。我们提供了计算高效的学习算法，对于任何游戏，都可以在对数因子内实现最小最大遗憾。除了极小极大遗憾的界限之外，如果我们假设结果是在I.I.D.中产生的。时尚，我们证明了个人对预期遗憾的上限。
In a partial monitoring game, the learner repeatedly chooses an action, the environment responds with an outcome, and then the learner suffers a loss and receives a feedback signal, both of which are fixed functions of the action and the outcome. The goal of the learner is to minimize his regret, which is the difference between his total cumulative loss and the total loss of the best fixed action in hindsight. In this paper we characterize the minimax regret of any partial monitoring game with finitely many actions and outcomes. It turns out that the minimax regret of any such game is either zero or scales as T-1/2, T-2/3, or T up to constants and logarithmic factors. We provide computationally efficient learning algorithms that achieve the minimax regret within a logarithmic factor for any game. In addition to the bounds on the minimax regret, if we assume that the outcomes are generated in an i.i.d. fashion, we prove individual upper bounds on the expected regret.