A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback
A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback
复制标题
DOI：
10.48550/arxiv.2301.13326
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
G. Nie;Yididiya Y. Nadew;Yanhui Zhu;V. Aggarwal;Christopher J. Quinn
中科院分区：
文献类型：
--
作者：
G. Nie;Yididiya Y. Nadew;Yanhui Zhu;V. Aggarwal;Christopher J. Quinn
我们调查的问题，随机组合多武装土匪的学习者只能获得土匪反馈和奖励函数可以是非线性的。我们提供了一个一般的框架，使离散离线近似算法适应次线性$\alpha$-后悔方法，只需要强盗反馈，实现$\mathcal{O}\left（T^\frac{2}{3}\log（T）^\frac{1}{3}\right）$期望的累积$\alpha$-后悔依赖于地平线$T$。该框架只要求离线算法对函数求值中的小错误具有鲁棒性。自适应过程甚至不需要离线近似算法的显式知识-离线算法可以用作黑盒子程序。为了证明所提出的框架的效用，所提出的框架适用于不同的应用程序在子模块最大化。新的CMAB算法的子模块最大化与背包约束优于一个完整的强盗方法开发的对抗性设置在实验中与现实世界的数据。
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 a black box subroutine. To demonstrate the utility of the proposed framework, the proposed framework is applied to diverse applications in submodular maximization. The new CMAB algorithms for submodular maximization with knapsack constraints outperform a full-bandit method developed for the adversarial setting in experiments with real-world data.