A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback
This work addresses a fundamental challenge in online learning for combinatorial optimization under limited feedback, with incremental improvements in algorithm design for specific domains like submodular maximization.
The paper tackles the problem of stochastic combinatorial multi-armed bandits with bandit feedback and non-linear rewards by developing a framework that adapts offline approximation algorithms into sublinear α-regret methods, achieving O(T^(2/3) log(T)^(1/3)) expected cumulative α-regret. It demonstrates utility in submodular maximization applications, outperforming an adversarial full-bandit method on real-world data.
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 $α$-regret methods that only require bandit feedback, achieving $\mathcal{O}\left(T^\frac{2}{3}\log(T)^\frac{1}{3}\right)$ expected cumulative $α$-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.