Blackwell's approachability is a framework where two players, the Decision Maker and the Environment, play a repeated game with vector-valued payoffs. The goal of the Decision Maker is to make the average payoff converge to a given set called the target. When this is indeed possible, simple algorithms which guarantee the convergence are known. This abstract tool was successfully used for the construction of optimal strategies in various repeated games, but also found several applications in online learning. By extending an approach proposed by (Abernethy et al., 2011), we construct and analyze a class of Follow the Regularized Leader algorithms (FTRL) for Blackwell's approachability which are able to minimize not only the Euclidean distance to the target set (as it is often the case in the context of Blackwell's approachability) but a wide range of distance-like quantities. This flexibility enables us to apply these algorithms to closely minimize the quantity of interest in various online learning problems. In particular, for regret minimization with $\ell_p$ global costs, we obtain the first bounds with explicit dependence in $p$ and the dimension $d$.

翻译：Blackwell的可接近性是一个框架,让两个角色,即决策者和环境,用矢量估值的回报来玩一个重复游戏。决策者的目标是让平均回报集中到一个称为目标的组合中。如果这是可能的,则可以知道能够保证趋同的简单算法。这个抽象工具被成功地用于在多次游戏中构建最佳战略,但在网上学习中也发现了一些应用。通过推广由(Abernethy等人,2011年)提议的方法,我们建造和分析了一组跟踪Blackwell正规化领导算法(FTRL)的可接近性(FTRL),不仅能够最大限度地减少Euclidean与目标集的距离(在Blackwell的可接近性情况下经常是这样),而且能够有广泛的距离。这种灵活性使我们能够应用这些算法,以密切减少各种在线学习问题中的兴趣数量。特别是,为将全球成本的美元减到最低,我们获得了以美元和美元这一维值为明确依赖度的首层。