Variance-Adaptive Algorithm for Probabilistic Maximum Coverage Bandits with General Feedback
Authors:
- 17 May 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-10
Abstract
Probabilistic maximum coverage (PMC) is an important problem that can model many network applications, including mobile crowdsensing, network content delivery, and dynamic channel allocation, where an operator chooses nodes in a graph that can probabilistically cover other nodes. In this paper, we study PMC under the online learning context: the PMC bandit. For PMC bandit where network parameters are not known a priori, the decision maker needs to learn the unknown parameters and the goal is to maximize the total rewards from the covered nodes. Though PMC bandit has been studied previously, the existing model and its corresponding algorithm can be significantly improved. First, we propose the PMC-G bandit whose feedback model generalizes existing semi-bandit feedback, allowing PMC bandit to model applications like online content delivery and online dynamic channel allocation. Next, we improve the existing combinatorial upper confidence bound (CUCB) algorithm by introducing the variance-adaptive algorithm, i.e., the VA-CUCB algorithm. We prove that VA-CUCB can achieve strictly better regret bounds, which improves CUCB by a factor of $\tilde O(K)$, where K is the number of nodes selected in each round. Finally, experiments show our superior performance compared with benchmark algorithms on synthetic and real-world datasets.
Keywords
This publication has 20 references indexed in Scilit:
- Take-Away TV: Recharging Work Commutes With Predictive Preloading of Catch-Up TV ContentIEEE Journal on Selected Areas in Communications, 2016
- Taming the Uncertainty: Budget Limited Robust Crowdsensing Through Online LearningIEEE/ACM Transactions on Networking, 2015
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Exploration–exploitation tradeoff using variance estimates in multi-armed banditsTheoretical Computer Science, 2009
- Content Delivery Networks: State of the Art, Insights, and Imperatives2008
- A Probabilistic Coverage Protocol for Wireless Sensor Networks2007
- Maximizing the spread of influence through a social network2003
- Approximation Algorithms for NP-Hard ProblemsACM SIGACT News, 1997
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952