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 算法，提供了与策略集能力相关的新后悔上界，并且改进了相关的专家建议问题。此外，针对线性赌博反馈，我们还证明了一种不可能利用策略之间的相似性的下界，并且提供了一个与策略集的信息半径相关的全信息变种的后悔上界。