.png){kind=icon}
返回
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}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
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总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.6
论文数:
4.4K
被引数:
9.5K
机构
引用论文
分享收藏Correction: Clinical Applicability and Cutoff Values for an Unstructured Neuropsychological Assessment Protocol for Older Adults with Low Formal Education.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAI分享收藏Combinatorial Network Optimization With Unknown Variables: Multi-Armed Bandits With Linear Rewards and Individual Observations具有未知变量的组合网络优化: 具有线性奖励和个人观察的多臂土匪
PREAI
分享收藏
查看更多内容