We investigate the problem of stochastic, combinatorial multi-armed bandits where the learner only has access to bandit feedback and the reward function can be non-linear. We provide a general framework for adapting discrete offline approximation algorithms into sublinear $\alpha$-regret methods that only require bandit feedback, achieving $\mathcal{O}\left(T^\frac{2}{3}\log(T)^\frac{1}{3}\right)$ expected cumulative $\alpha$-regret dependence on the horizon $T$. The framework only requires the offline algorithms to be robust to small errors in function evaluation. The adaptation procedure does not even require explicit knowledge of the offline approximation algorithm -- the offline algorithm can be used as black box subroutine. To demonstrate the utility of the proposed framework, the proposed framework is applied to multiple problems in submodular maximization, adapting approximation algorithms for cardinality and for knapsack constraints. The new CMAB algorithms for knapsack constraints outperform a full-bandit method developed for the adversarial setting in experiments with real-world data.
翻译:我们在学习者只能获得土匪反馈而且奖励功能可以是非线性功能的情况下,调查多武装的盗匪问题。我们为将离散离线近似算法调整为亚线性$\alpha$-regret 方法提供了一个总框架,这些方法只要求土匪反馈,达到$\mathcal{O ⁇ left(T ⁇ frac{2 ⁇ 3 ⁇ log(T) ⁇ frac{1 ⁇ 3 ⁇ right),预期对地平线的累积依赖$\alpha$-regret$$l$T$。这个框架只要求离线性算法在功能评价中对小错误具有强势性。适应程序甚至不要求明确了解离线性近似算算法 -- 离线性算法可以用作黑盒子路程。为了证明拟议框架的效用,拟议框架适用于亚调最大化、为基度和Knappsack限制而调整近似算法的多重问题。这个框架只要求离线性算法在功能评估中对全波形数据进行试验。