Approachability in unknown games: Online learning meets multi-objective optimization
Approachability in unknown games: Online learning meets multi-objective optimization
复制标题
未知游戏中的平易近人性：在线学习遇到多目标优化
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Gilles Stoltz
中科院分区：
文献类型：
--
作者：
Shie Mannor;Vianney Perchet;Gilles Stoltz
在可接近性的标准设置中，有两个球员和一个目标集。玩家重复玩一个已知的向量值博弈，其中第一个玩家希望平均向量值收益收敛到目标集，而另一个玩家试图将其排除在目标集之外。本着在线学习的精神，我们重新审视了这一设置，并不假设第一个玩家知道游戏结构：她在每一轮都会收到一个任意向量值的奖励向量。她希望在事后观察到平均收益的情况下，接近可能的最小(“最佳”)集合。标准设置的这种扩展甚至在原始目标设置不可接近时也有影响，并且当不明显地应该采用其哪个扩展时也是如此。我们表明，一般而言，不可能达到事后制定的最佳目标，并提出可实现的、但雄心勃勃的替代目标。我们进一步提出了实现这些目标的具体战略。我们的方法不需要投影到目标集合上，并且相当于在每集执行的标量后悔最小化算法之间进行切换。考虑了在样本路径约束下的全局费用最小化和可达性方面的应用。
In the standard setting of approachability there are two players and a target set. The players play repeatedly a known vector-valued game where the first player wants to have the average vector-valued payoff converge to the target set which the other player tries to exclude it from this set. We revisit this setting in the spirit of online learning and do not assume that the first player knows the game structure: she receives an arbitrary vector-valued reward vector at every round. She wishes to approach the smallest ("best") possible set given the observed average payoffs in hindsight. This extension of the standard setting has implications even when the original target set is not approachable and when it is not obvious which expansion of it should be approached instead. We show that it is impossible, in general, to approach the best target set in hindsight and propose achievable though ambitious alternative goals. We further propose a concrete strategy to approach these goals. Our method does not require projection onto a target set and amounts to switching between scalar regret minimization algorithms that are performed in episodes. Applications to global cost minimization and to approachability under sample path constraints are considered.