When Combinatorial Thompson Sampling meets Approximation Regret
Nov 28, 2022
Speakers
Pierre Perrault
Speaker · 0 followers
About
We study the behavior of the Combinatorial Thompson Sampling policy (CTS) for combinatorial multi-armed bandit problems (CMAB), within an approximation regret setting. Although CTS has attracted a lot of interest, it has a drawback that other usual CMAB policies do not have when considering non-exact oracles: for some oracles, CTS has a poor approximation regret (scaling linearly with the time horizon T) [Wang and Chen, 2018]. A study is then necessary to discriminate the oracles on which CTS could learn. This study was started by Kong et al. [2021]: they gave the first approximation regret analysis of CTS for the greedy oracle, obtaining an upper bound of order 𝒪(log(T)/Δ^2), where Δ is some minimal reward gap. In this paper, our objective is to push this study further than the simple case of the greedy oracle. We provide the first 𝒪(log(T)/Δ) approximation regret upper bound for CTS, obtained under a specific condition on the approximation oracle, allowing a reduction to the exact oracle analysis. We thus term this condition Reduce2Exact, and observe that it is satisfied in many concrete examples. In particular, it can be extended to the probabilistically triggered arms setting, thus capturing even more problems, such as online influence maximization.We study the behavior of the Combinatorial Thompson Sampling policy (CTS) for combinatorial multi-armed bandit problems (CMAB), within an approximation regret setting. Although CTS has attracted a lot of interest, it has a drawback that other usual CMAB policies do not have when considering non-exact oracles: for some oracles, CTS has a poor approximation regret (scaling linearly with the time horizon T) [Wang and Chen, 2018]. A study is then necessary to discriminate the oracles on which CTS co…
Organizer
NeurIPS 2022
Account · 962 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Sparse Probabilistic Circuits via Pruning and Growing
Watch later
Meihua Dang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective
Watch later
Rongzhe Wei, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Alternating Mirror Descent for Constrained Min-Max Games
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Harmonizing the Object Recognition Strategies of Deep Neural Networks with Humans
Watch later
Thomas Fel, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
CLUTR: Curriculum Learning via Unsupervised Task Representation Learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Geospatial Distribution Shifts in Ecology: Mapping the Urban Forest
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%