This work addresses the mediator feedback problem, a bandit game where the
decision set consists of a number of policies, each associated with a
probability distribution over a common space of outcomes. Upon choosing a
policy, the learner observes an outcome sampled from its distribution and
incurs the loss assigned to this outcome in the present round. We introduce the
policy set capacity as an information-theoretic measure for the complexity of
the policy set. Adopting the classical EXP4 algorithm, we provide new regret
bounds depending on the policy set capacity in both the adversarial and the
stochastic settings. For a selection of policy set families, we prove
nearly-matching lower bounds, scaling similarly with the capacity. We also
consider the case when the policies' distributions can vary between rounds,
thus addressing the related bandits with expert advice problem, which we
improve upon its prior results. Additionally, we prove a lower bound showing
that exploiting the similarity between the policies is not possible in general
under linear bandit feedback. Finally, for a full-information variant, we
provide a regret bound scaling with the information radius of the policy set.

这项研究针对中介反馈问题，提出了一个信息论度量，称为策略集能力，用于衡量策略集的复杂性。研究在对抗性和随机性环境中采用了经典的 EXP4 算法，提供了与策略集能力相关的新后悔上界，并且改进了相关的专家建议问题。此外，针对线性赌博反馈，我们还证明了一种不可能利用策略之间的相似性的下界，并且提供了一个与策略集的信息半径相关的全信息变种的后悔上界。

具备调解者反馈的赌博机信息容量遗憾界限

Information Capacity Regret Bounds for Bandits with Mediator Feedback

The permutahedron is the convex polytope with vertex set consisting of the
vectors $(\pi(1),\dots, \pi(n))$ for all permutations (bijections) $\pi$ over
$\{1,\dots, n\}$. We study a bandit game in which, at each step $t$, an
adversary chooses a hidden weight weight vector $s_t$, a player chooses a
vertex $\pi_t$ of the permutahedron and suffers an observed loss of
$\sum_{i=1}^n \pi(i) s_t(i)$.
A previous algorithm CombBand of Cesa-Bianchi et al (2009) guarantees a
regret of $O(n\sqrt{T \log n})$ for a time horizon of $T$. Unfortunately,
CombBand requires at each step an $n$-by-$n$ matrix permanent approximation to
within improved accuracy as $T$ grows, resulting in a total running time that
is super linear in $T$, making it impractical for large time horizons.
We provide an algorithm of regret $O(n^{3/2}\sqrt{T})$ with total time
complexity $O(n^3T)$. The ideas are a combination of CombBand and a recent
algorithm by Ailon (2013) for online optimization over the permutahedron in the
full information setting. The technical core is a bound on the variance of the
Plackett-Luce noisy sorting process's "pseudo loss". The bound is obtained by
establishing positive semi-definiteness of a family of 3-by-3 matrices
generated from rational functions of exponentials of 3 parameters.

本文研究了一个基于凸多面体的赌博游戏，并提出了一种算法，它结合了 2013 年 Ailon 的最新算法和 2009 年 Cesa-Bianchi et al 的算法，以实现在线优化，总时间复杂度为 O（n^3T），其中 n 是顶点数和 T 是时间区间，这算法能够使遗憾达到 O (n^（3/2）* 根号 T)。