Bandit online optimization over permutahedron
Bandit online optimization over permutahedron
复制标题
置换面体的 Bandit 在线优化
DOI：
10.1007/978-3-319-11662-4_16
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Eiji Takimoto
中科院分区：
文献类型：
--
作者：
Nir Ailon;Kohei Hatano;Eiji Takimoto
置换多面体是顶点集由向量(π(1)，…)组成的凸多面体，π(N))对{1，π上的所有排列(双射)…，n}。我们研究盗贼博弈，其中，在每一步t，一个对手选择一个隐藏的权重向量S t，一个玩家选择置换面体的一个顶点πt，并且遭受∑i=1 nπt(I)S t(I)的瞬时损失。我们用两种不同的方法来研究这个问题。在这两种方法中，我们假定S t是排多面体对偶的多面体中的一点。Cesa-Bianci等人(2012年)的组合频带算法保证T步后的遗憾为O(n，T，，n)。不幸的是，CombBand在每一步都需要n乘n矩阵的永久计算，这是一个#P-Hard问题。在O(N 10)的不切实际的运行时间内可以近似永久数，并且附加了对所寻求的精度的严重的反多项式依赖。在第一种方法中，我们提供了一个略差的遗憾O(n3/2T)算法，但每步的时间复杂度为O(N3)。技术上的贡献是对Plackett-Luce噪声分类过程的“伪损失”的方差的一个界，它是通过建立一个3参数指数的3乘3有理函数族的正半正定性而获得的。在第二种方法中，我们在Bubeck等人(S，2012年)的OSMD方法的基础上，提出并分析了一种新的置换面体投影和分解技术。第二个算法的运行时间和后悔保证类似于我们的第一个算法，模数线搜索过程，我们无法分析其运行时间。有趣的是，这两种方法完全不同。这项工作的主要公开问题是，对于这两个问题，是否存在一个同时具有O(NT)最优遗憾和O(N3)运行时间的强盗算法，或者在两种性能指标之间存在内在的折衷。
The permutahedron is the convex polytope with vertex set consisting of the vectors (π (1),…, π (n)) for all permutations (bijections) π over {1,…, n}. We study a bandit game in which, at each step t, an adversary chooses a hidden weight vector s t, a player chooses a vertex π t of the permutahedron and suffers an observed instantaneous loss of∑ i= 1 n π t (i) s t (i). We study the problem in two different approaches. In the two approaches, we assume that s t is a point in the polytope dual to the permutahedron. Algorithm CombBand of Cesa-Bianchi et al.(2012) guarantees a regret of O (n T log n) after T steps. Unfortunately, CombBand requires at each step an n-by-n matrix permanent computation, a# P-hard problem. Approximating the permanent is possible in the impractical running time of O (n 10), with an additional heavy inverse-polynomial dependence on the sought accuracy. In the first approach, we provide an algorithm of slightly worse regret O (n 3/2 T) but with more realistic time complexity O (n 3) per step. The technical contribution is a bound on the variance of the Plackett–Luce noisy sorting process's ‘pseudo loss’, obtained by establishing positive semi-definiteness of a family of 3-by-3 matrices of rational functions in exponents of 3 parameters. In the second approach, we present and analyze an algorithm based on Bubeck et al.'s (2012) OSMD approach with a novel projection and decomposition technique for the permutahedron. The second algorithm's running time and regret guarantees are similar to our first algorithm, modulo a numerical line search procedure the running time of which we have not been able to analyze. It is interesting that the two approaches are totally different. The main open problem from this work is whether there exists a bandit algorithm for this problem with both optimal regret of O (n T) and running time of O (n 3) for either regime, or there is an inherent tradeoff between the two performance measures.