We study adaptive combinatorial maximization, which is a core challenge in
machine learning, with applications in active learning as well as many other
domains. We study the Bayesian setting, and consider the objectives of
maximization under a cardinality constraint and minimum cost coverage. We
provide new comprehensive approximation guarantees that subsume previous
results, as well as considerably strengthen them. Our approximation guarantees
simultaneously support the maximal gain ratio as well as near-submodular
utility functions, and include both maximization under a cardinality constraint
and a minimum cost coverage guarantee. In addition, we provided an
approximation guarantee for a modified prior, which is crucial for obtaining
active learning guarantees that do not depend on the smallest probability in
the prior. Moreover, we discover a new parameter of adaptive selection
policies, which we term the "maximal gain ratio". We show that this parameter
is strictly less restrictive than the greedy approximation parameter that has
been used in previous approximation guarantees, and show that it can be used to
provide stronger approximation guarantees than previous results. In particular,
we show that the maximal gain ratio is never larger than the greedy
approximation factor of a policy, and that it can be considerably smaller. This
provides a new insight into the properties that make a policy useful for
adaptive combinatorial maximization.

我们研究了自适应组合最大化问题，在机器学习中是一个核心挑战，并应用于主动学习以及其他许多领域。我们研究贝叶斯设置下，考虑最大化目标在基数约束和最小成本覆盖下。我们提供了新的综合近似保证，包括之前的结果，并且更加加强了它们。我们的近似保证同时支持最大增益比以及接近次模效用函数，包括了在基数约束和最小成本覆盖下的最大化保证。此外，我们对一种修改后的先验提供了近似保证，这对于获得独立于先验最小概率的主动学习保证至关重要。此外，我们发现了一种自适应选择策略的新参数，称之为 “最大增益比”。我们展示了这个参数比之前近似保证中使用的贪婪近似参数要更加宽松，并展示了它可以提供比之前结果更强的近似保证。特别地，我们展示了最大增益比永远不会大于策略的贪婪近似因子，并且它可以大为缩小。这为自适应组合最大化中有用的策略特性提供了新的见解。

自适应组合最大化：超过近似贪心策略

Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies

We consider the fixed-confidence best arm identification (FC-BAI) problem in
the Bayesian Setting. This problem aims to find the arm of the largest mean
with a fixed confidence level when the bandit model has been sampled from the
known prior. Most studies on the FC-BAI problem have been conducted in the
frequentist setting, where the bandit model is predetermined before the game
starts. We show that the traditional FC-BAI algorithms studied in the
frequentist setting, such as track-and-stop and top-two algorithms, result in
arbitrary suboptimal performances in the Bayesian setting. We also prove a
lower bound of the expected number of samples in the Bayesian setting and
introduce a variant of successive elimination that has a matching performance
with the lower bound up to a logarithmic factor. Simulations verify the
theoretical results.

在贝叶斯设置下，我们研究了固定置信度最佳臂识别问题。我们证明了传统的 FC-BAI 算法在贝叶斯设置下会导致任意次优的性能，并且介绍了一种连续淘汰的变体，其性能与下界匹配，仅有一个对数因子的差距。模拟实验验证了理论结果。