We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine them with the minimax theorem to derive minimax regret bounds for various partial monitoring settings. The highlight is a clean analysis of `non-degenerate easy' and `hard' finite partial monitoring, with new regret bounds that are independent of arbitrarily large game-dependent constants. The power of the generalised machinery is further demonstrated by proving that the minimax regret for k-armed adversarial bandits is at most sqrt{2kn}, improving on existing results by a factor of 2. Finally, we provide a simple analysis of the cops and robbers game, also improving best known constants.

本研究证明了一个新的minimax定理，将贝叶斯最坏情况遗憾和没有对手信号或决策的minimax遗憾联系起来。进而推广Russo和Van Roy (2016)的信息论工具，证明了多种部分监视设置的minimax遗憾边界。其中最突出的是对'非退化简单'和'困难'有限部分监控的清晰分析，提供了独立于任意大的游戏相关常数的新遗憾约束。该研究还通过证明对于k武装对手贝叶斯遗憾最多为sqrt{2kn}，提高了现有成果2倍的minimax遗憾界，进一步展示了推广机器的能力。最后，我们提供了警察和流氓游戏的简单分析，也提高了最好已知的常数。

基于信息论的部分监控极小后悔策略