Thompson Sampling for Combinatorial Network Optimization in Unknown Environments

Abstract

Influence maximization, adaptive routing, and dynamic spectrum allocation all require choosing the right action from a large set of alternatives. Thanks to the advances in combinatorial optimization, these and many similar problems can be efficiently solved given an environment with known stochasticity. In this paper, we take this one step further and focus on combinatorial optimization in unknown environments. We consider a very general learning framework called combinatorial multi-armed bandit with probabilistically triggered arms and a very powerful Bayesian algorithm called Combinatorial Thompson Sampling (CTS). Under the semi-bandit feedback model and assuming access to an oracle without knowing the expected base arm outcomes beforehand, we show that when the expected reward is Lipschitz continuous in the expected base arm outcomes CTS achieves $O({\sum }_{i=1}^m\log T/(p_i{\Delta }_i))$ regret and $O(\max \{\mathbb{E}[m\sqrt{T\log T/p^{\ast }}],\mathbb{E}[m^2/p^{\ast }]\})$ Bayesian regret, where $m$ denotes the number of base arms, $p_i$ and ${\Delta }_i$ denote the minimum non-zero triggering probability and the minimum suboptimality gap of base arm $i$ respectively, $T$ denotes the time horizon, and $p^{\ast }$ denotes the overall minimum non-zero triggering probability. We also show that when the expected reward satisfies the triggering probability modulated Lipschitz continuity, CTS achieves $O(\max \{m\sqrt{T\log T},m^2\})$ Bayesian regret, and when triggering probabilities are non-zero for all base arms, CTS achieves $O(1/p^{\ast }\log (1/p^{\ast }))$ regret independent of the time horizon. Finally, we numerically compare CTS with algorithms based on upper confidence bounds in several networking problems and show that CTS outperforms these algorithms by at least an order of magnitude in majority of the cases.

14 pages, 3 figures. Accepted for publication in the IEEE/ACM Transactions on Networking. arXiv admin note: text overlap with arXiv:1809.02707

References in corpus (12)

• Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
• Cascading Bandits: Learning to Rank in the Cascade Model
• Thompson Sampling for Combinatorial Semi-Bandits
• Context-Aware Hierarchical Online Learning for Performance Maximization in Mobile Crowdsourcing
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• Combinatorial Semi-Bandits with Knapsacks
• Top-k Combinatorial Bandits with Full-Bandit Feedback
• Information Directed Sampling for Stochastic Bandits with Graph Feedback
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• Bandits with Side Observations: Bounded vs. Logarithmic Regret
• Stochastic Online Learning with Probabilistic Graph Feedback
• Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms: A Case with Bounded Regret

Cited by in corpus (3)

• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Online Competitive Influence Maximization
• Online Influence Maximization: Concept and Algorithm