论文标题
一种基于渐近最佳潜力的新方法来漂移游戏
A New Approach to Drifting Games, Based on Asymptotically Optimal Potentials
论文作者
论文摘要
我们开发了一种新的方法来推动游戏，这是一类两人游戏，其中包括许多应用程序来增强和在线学习设置。我们的方法涉及（a）通过解决相关的偏微分方程（PDE）来猜测渐近的最佳潜力；然后（b）通过证明最终时间损失上的上限和下限来证明猜测的合理性，它们的差异像时间步长的负能力一样。我们潜在的基于上限的证据是基本的，只需使用泰勒的扩展。我们潜在的基于潜在的下限的证明也是基本的，将泰勒的扩展与概率或组合参数相结合。我们的方法不仅更基本，而且我们提供了新的电位，并得出相应的上限和下限，这些上限和下限在渐近方面相匹配。
We develop a new approach to drifting games, a class of two-person games with many applications to boosting and online learning settings. Our approach involves (a) guessing an asymptotically optimal potential by solving an associated partial differential equation (PDE); then (b) justifying the guess, by proving upper and lower bounds on the final-time loss whose difference scales like a negative power of the number of time steps. The proofs of our potential-based upper bounds are elementary, using little more than Taylor expansion. The proofs of our potential-based lower bounds are also elementary, combining Taylor expansion with probabilistic or combinatorial arguments. Not only is our approach more elementary, but we give new potentials and derive corresponding upper and lower bounds that match each other in the asymptotic regime.
