.png){kind=icon}
Return
Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2020.3025904.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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(Sigma(m)(i=1/2) log T/(p(i)Delta(i))) regret and O(max{E[m root T log T/p*], 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 root 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.
Keywords:
Optimization
Bayes methods
Probabilistic logic
IEEE transactions
Heuristic algorithms
Resource management
Approximation algorithms
Combinatorial network optimization
multi-armed bandits
Thompson sampling
regret bounds
online learning
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K
Organization
Cited Papers
ShareSaveShareSaveCorrection: Clinical Applicability and Cutoff Values for an Unstructured Neuropsychological Assessment Protocol for Older Adults with Low Formal Education.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAIShareSaveShareSaveShareSaveShareSave
View more