Thompson Sampling for Combinatorial Network Optimization in Unknown Environments

Alihan Hüyük, Cem TekinIEEE/ACM Trans. Networking 2019 · DOI · OpenReview

TL;DR

This paper introduces Combinatorial Thompson Sampling (CTS), a novel Bayesian algorithm for making sequential decisions in complex network optimization problems where the environment's behavior is unknown. CTS achieves strong theoretical regret bounds and demonstrates superior performance over existing methods in simulations across various networking applications.

What Problem Does This Paper Address?

Many real-world problems, such as optimizing ad campaigns, recommending products, or managing network resources, involve selecting the best action from a vast number of possibilities. While these problems can be solved efficiently if the environment's stochasticity is known, this is rarely the case in practice. This paper tackles the challenge of making optimal sequential decisions in these unknown environments. Specifically, it focuses on a generalized version of the combinatorial multi-armed bandit problem, where selecting a "super arm" (a set of base actions) probabilistically triggers a subset of base arms, and the reward depends on these triggered arms. The core difficulty lies in balancing exploration (learning about the unknown environment) and exploitation (using current knowledge to maximize rewards) to achieve the best long-term performance.

Methods

The paper proposes Combinatorial Thompson Sampling (CTS), a Bayesian algorithm that maintains a posterior distribution over the expected outcomes of each base arm. In each round, CTS samples from these posteriors to form an estimate of the expected rewards and then uses an "exact computation oracle" to select the super arm that appears optimal based on these samples. The observed feedback from the triggered base arms is then used to update the posterior distributions.

The theoretical analysis of CTS focuses on deriving regret bounds under different assumptions about the reward function's continuity and the triggering probabilities. Key assumptions include:

  • Lipschitz continuity: The expected reward changes smoothly with the expected base arm outcomes.
  • Triggering Probability Modulated (TPM) Lipschitz continuity: A stricter form of continuity that leads to better bounds.
  • Monotonicity: The expected reward increases with the expected outcomes of base arms.

The paper also analyzes the performance of CTS in scenarios with strictly positive triggering probabilities, which simplifies the exploration challenge.

Datasets

The paper does not introduce new datasets. Instead, it uses established datasets and synthetic data generation for its simulations:

  • MovieLens dataset: Used for the probabilistic maximum coverage bandit experiments.
  • Facebook network dataset: Used for influence maximization bandit experiments.
  • Synthetic data: Generated for cascading bandit problems and other scenarios to test specific theoretical assumptions.

Key Insights and Ideas

  • Thompson Sampling shines in unknown environments: The paper strongly advocates for Thompson Sampling's effectiveness in complex, unknown environments, outperforming UCB-based methods in their simulations.
  • Bayesian approach handles probabilistic triggers well: The use of a Beta posterior for base arm outcomes is shown to be particularly effective for problems with probabilistic triggering, outperforming Gaussian posteriors in some cases.
  • Regret bounds depend critically on assumptions: The paper demonstrates how different assumptions about the reward function's properties (Lipschitz continuity, TPM Lipschitz continuity) and triggering probabilities lead to significantly different theoretical regret bounds.
  • Exploration-exploitation trade-off is key: The theoretical analysis explicitly quantifies how CTS balances learning about the environment (exploration) with maximizing immediate rewards (exploitation) to achieve near-optimal long-term performance.
  • The "oracle" is crucial: The theoretical guarantees rely on the availability of an exact computation oracle. However, the paper also shows that CTS performs well in practice even when using an approximation oracle.

Key Results

The paper presents several theoretical regret bounds for CTS:

  • Lipschitz Continuity: Achieves $O(\sum_{i=1}^m \log T / (p_i \Delta_i))$ regret and $O(\max\{E[m\sqrt{T\log T}/p^*], E[m^2/p^*]\})$ Bayesian regret.
  • TPM Lipschitz Continuity: Achieves $O(\max\{m\sqrt{T\log T}, m^2\})$ Bayesian regret, notably independent of triggering probabilities.
  • Strictly Positive Triggering Probabilities: Achieves $O(1/p^* \log(1/p^*))$ regret, independent of the time horizon.

Numerically, CTS consistently outperformed competing algorithms (primarily UCB-based methods like CUCB) by a significant margin (often an order of magnitude) in simulations for:

  • Cascading bandits: Regret was up to 20 times lower than CUCB.
  • Probabilistic maximum coverage bandits: Regret was up to 11 times lower than CUCB.
  • Influence maximization bandits: Regret was up to 6 times lower than CUCB, even when using approximation oracles.

Limitations and Future Work

  • Reliance on an Exact Oracle: The theoretical guarantees for some bounds assume access to an exact computation oracle, which might be computationally expensive or unavailable in practice. The paper notes that CTS still performs well with approximation oracles, suggesting this is a practical robustness.
  • Assumptions on Reward Function: The regret bounds are derived under specific assumptions about the reward function's continuity (Lipschitz, TPM Lipschitz). The performance in scenarios violating these assumptions is not explicitly studied.
  • Lower Bound Gap: For the case of strictly positive triggering probabilities, the derived regret bound $O(1/p^* \log(1/p^*))$ does not match a known lower bound of $O(\log(1/p^*))$ for a simpler setting. The authors suggest this gap might be due to the more general reward model considered in their work.
  • Future Work: The paper implicitly suggests exploring scenarios with approximate oracles more deeply, investigating performance under weaker continuity assumptions, and potentially closing the gap to the theoretical lower bound for certain settings.

Summary updated

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^*}],\mathbb{E}[m^2/p^*]\})$ 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^*$ 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^*\log(1/p^*))$ 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.
BibTeX
@article{huyuk2019thompson,
  author = {Alihan Hüyük and Cem Tekin},
  title = {{Thompson Sampling for Combinatorial Network Optimization in Unknown Environments}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2019},
  doi = {10.1109/tnet.2020.3025904},
}
Figure