Robbing the bandit: less regret in online geometric optimization against an adaptive adversary
Robbing the bandit: less regret in online geometric optimization against an adaptive adversary
复制标题
抢劫强盗：在针对自适应对手的在线几何优化中减少遗憾
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Thomas P. Hayes
中科院分区：
文献类型：
--
作者：
Varsha Dani;Thomas P. Hayes
我们考虑“在线匪徒几何优化”，这是一个在很大程度上未知且不断变化的环境中迭代决策的问题。目的是最大程度地减少“遗憾”，定义为在线决策程序的实际损失与事后最佳单一决策的差异之间的区别。 “几何优化”是指众所周知的多武器匪徒问题的概括，其中决策空间是RD的某些有界子集，对手仅限于线性损耗函数，遗憾的界限应取决于维度d，dimensionality d，而不是可能的决策总数。 “匪徒”是指算法仅在每回合中被告知损失的设置，而不是整个损失功能。 o（poly（d）T3/4）。我们简化并改善了他们对该算法的分析以获得遗憾o（poly（poly（d d）T2/3））。我们还证明，对于大量全信息在线优化问题，对自适应对手的最佳遗憾是相同的与非自适应对手有关。
We consider "online bandit geometric optimization," a problem of iterated decision making in a largely unknown and constantly changing environment. The goal is to minimize "regret," defined as the difference between the actual loss of an online decision-making procedure and that of the best single decision in hindsight. "Geometric optimization" refers to a generalization of the well-known multi-armed bandit problem, in which the decision space is some bounded subset of Rd, the adversary is restricted to linear loss functions, and regret bounds should depend on the dimensionality d, rather than the total number of possible decisions. "Bandit" refers to the setting in which the algorithm is only told its loss on each round, rather than the entire loss function.McMahan and Blum [10] presented the best known algorithm in this setting, and proved that its expected additive regret is O(poly(d)T3/4). We simplify and improve their analysis of this algorithm to obtain regret O(poly(d)T2/3).We also prove that, for a large class of full-information online optimization problems, the optimal regret against an adaptive adversary is the same as against a non-adaptive adversary.