The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle
Thompson sampling (TS) has attracted a lot of interest in the bandit area. It was introduced in the 1930s but has not been theoretically proven until recent years. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example (Wang and Chen, 2018) has shown the failure of TS to learn with an approximation oracle. However, this oracle is uncommon and is designed only for a specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which is a common (approximation) oracle with theoretical guarantees to solve many (offline) combinatorial optimization problems. We provide a problem-dependent regret lower bound of order $\Omega(\log T/\Delta^2)$ to quantify the hardness of TS to solve CMAB problems with greedy oracle, where $T$ is the time horizon and $\Delta$ is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with a common approximation oracle and break the misconception that TS cannot work with approximation oracles.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationOpen-Ended Question AnsweringThompson SamplingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
We investigate stochastic combinatorial multi-armed bandit with semi-bandit feedback (CMAB). In CMAB, the question of the existence of an efficient policy with an optimal asymptotic regret (up to a factor poly-logarithmi…
Thompson SamplingFirst-Order Bayesian Regret Analysis of Thompson Sampling
We address online combinatorial optimization when the player has a prior over the adversary's sequence of losses. In this framework, Russo and Van Roy proposed an information-theoretic analysis of Thompson Sampling based…
Combinatorial OptimizationThompson SamplingAnalysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access …
Thompson SamplingThompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We …
Thompson SamplingA Contextual Combinatorial Semi-Bandit Approach to Network Bottleneck Identification
Bottleneck identification is a challenging task in network analysis, especially when the network is not fully specified. To address this task, we develop a unified online learning framework based on combinatorial semi-ba…
Multi-Armed BanditsThompson Sampling