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.
