On a Unified Framework for Approachability with Full or Partial Monitoring

• 成果类型: Article
• 署名作者: Perchet, Vianney; Quincampoix, Marc
• 署名单位: Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite; Universite Paris Cite; Universite de Bretagne Occidentale; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0686
• 发表日期: 2015
• 页码: 596-610
• 关键词: differential-games; KNOWLEDGE; regret

摘要

We represent any repeated game with partial monitoring as an abstract repeated game with full monitoring where outcomes are probability measures, to be interpreted as the maximal information the players can obtain in the original game. One of our objectives is to define and generalize Blackwell's approachability theory in this space of probability measures. We characterize approachable sets with, as usual, a simple and complete formulation for convex sets. Translated back into the original games with partial monitoring, these results provide the first necessary and sufficient approachability condition. As there is not a unique way to define averages of probability measures, we also investigate the case of displacement interpolation. We obtain similar results along with rates of convergence.