Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the combinatorial multi-armed bandit (CMAB) problem in a setting where exactly solving the corresponding offline optimization problem is not feasible (due to its computational hardness) and the learning agent only has access to a greedy oracle which approximately solves the offline optimization problem. In this framework, the paper analyzes the behavior of a natural variant of the Thompson sampling algorithm called Combinatorial Thompson sampling (CTS). The paper first gives an algorithm-dependent and problem-dependent lower bound showing that CTS faces a fundamental limit, then provides an almost matching upper bound.
main_review: The paper is well-written. The research question is well-motivated and practically relevant (as greedy algorithms are common choices for approximately solving hard combinatorial optimization problems). While a similar research question has already been studied in Lin et al. [22], the framework considered in that paper is different from the framework studied in this paper , and the two papers focus on different types of algorithms (UCB vs. Thompson sampling). The results of this paper seem to be technically correct.

I have the following questions/concerns:
1. The lower bound is algorithm-dependent, which means that it only holds for the CTS algorithm. While this result does provide interesting insights on the behavior of CTS, a natural question is whether such a fundamental limit also exists for other algorithms. In other words, I feel that an information-theoretic lower bound could greatly improve the quality of the paper and provide more insights on the proposed framework.
2. Currently, the algorithm uses a Beta prior (to obtain the upper bound), but the lower bound is shown for the Gaussian prior. This seems like a limitation. Can the authors provide matching upper and lower bounds for the same prior, or provide some explanations on deriving upper and lower bounds using different priors is not an issue?
2. A main insight of this paper is that using TS-type algorithms to solve CMAB with a greedy oracle may necessarily lead to a larger regret bound (with worse dependence on the reward gap) compared with the regret bounds obtained by using exact oracles. I note that the paper considers the worst-case regret. Can the authors provide some insights on whether such phenomena still exist when the Bayesian regret is considered? I note that the current lower bound does not directly imply a Bayesian regret lower bound (as the constructed instance is not "Gaussian").
limitations_and_societal_impact: I discussed some questions/concerns in my review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes the performance of Thompson sampling for combinatorial multi-armed bandit problems where using an exact oracle is not feasible. While it is known that, in general, Thompson sampling cannot achieve sublinear regret with an arbitrary $\alpha$-approximation oracle, the paper instead focuses on *greedy oracles* and shows that achieving $O(\log T/\Delta^2)$ is possible with a greedy oracle.
main_review: Although most applications of CMAB require using greedy oracles, almost all analyses of TS under the CMAB setting consider exact oracles. This paper is first to show theoretically that TS is still a viable algorithm for such CMAB applications, which is a highly valuable contribution.

In Theorem 2, authors show an upper bound of $O(\log T/\Delta^2)$ for TS with a greedy oracle. While upper bounds of the form $O(\log T/\Delta)$ are more common in the bandit literature, Theorem 1 shows that this bound is actually tight with respect to $\Delta$. However, Theorem 1 does not actually reveal anything regarding the hardness of optimizing greedy regret while the paper is phrased like it does. It is still not clear whether $O(\log T/\Delta^2)$ is the best possible greedy regret achievable by *any* algorithm, or a UCB-based algorithm can still achieve $O(\log T/\Delta)$ greedy regret. As authors have already pointed out in their paper, when a greedy oracle also happens to be an $\alpha$-approximation oracle, the greedy regret would be larger than the $\alpha$-approximation regret, meaning existing upper bounds on  the $\alpha$-approximation regret of UCB-based algorithms do not answer this question. Conversely, knowing TS with a greedy oracle can achieve $O(\log T/\Delta^2)$ greedy regret does not imply it can also achieve $O(\log T/\Delta)$ $\alpha$-approximation regret, when the greedy oracle also happens to be an $\alpha$-approximation oracle.

Having said that, I still believe a tight upper bound on the greedy regret of TS for CMAB is still a significant enough contribution on its own. Until this paper, whether TS with a greedy oracle is even effective in solving CMAB problems was unknown theoretically. Now, the new question is whether TS with a greedy oracle is as effective as UCB-based algorithms, which is probably outside the scope of this paper.

My only concern is about Section 6.2, extending the analysis in Theorem 2 to the multiple-solution case. It is true that $S_g$ always being the solution with the minimum reward would be the worst case *if* we were to evaluate performance in terms of actual regret measured with respect to the actual optimal solution. When considering the greedy regret instead, if we assume $S_g$ is always the minimum reward solution, then we would also be measuring performance with respect to $\arg\min_{S\in\sigma_K} r(S,\mu)$. This is not necessarily the case when the regret is the largest (for instance when $S_g$ is such that $S_g=\arg\max_{S\in\sigma_K} r(S,\mu)$ and $S_g=\arg\min_{S\in\sigma_K} r(S,\theta)$ for all $\theta\neq\mu$, the greedy regret would be larger). However, I think the same analysis in Section 6.2 should also be possible for any deterministic function $f$ such that $S_g=f(\sigma_K)$.
limitations_and_societal_impact: One limitation that might be mentioned could be the fact that it is still an open question whether $O(\log T/\Delta^2)$ is the best greedy regret achievable by *any* algorithm (including UCB-based algorithms not just TS with a greedy oracle).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the performance of Thompson-Sampling (TS) when applied to combinatorial multi-armed bandit (CMAB) problems with semi-bandit feedback. It is well known that the combinatorial TS (CTS) algorithm might suffer from linear regret when the combinatorial maximization is solved using an approximation oracle [30]. In this work, the authors apply CTS with a specific family of combinatorial maximization oracles – greedy oracles. They analyze the greedy regret of CTS (which compares the played actions to the greedy solution of the combinatorial problem) and derive regret upper bounds of $O(\log T/\Delta^2)$, where $\Delta$ is a suboptimality gap. They also provide a matching lower bound for CTS on a specific small-scale problem.
main_review: In my opinion, the paper has two notable contributions: first, CMAB papers usually analyze the approximation regret, which compares the played actions to $(1-1/e)OPT$ (in the case of greedy oracles). In contrast, the derived bounds compare the played action to the best greedy action, which is always better than $(1-1/e)OPT$. Therefore, the provided guarantees are stronger than the standard CMAB guarantees. To the best of my knowledge, the only paper that derives such guarantees is [22], where the algorithm is intractable. Therefore, a notable contribution of this paper is in analyzing a tractable algorithm (CTS) for this performance criterion. This kind of guarantee adds an ‘oracle-problem dependent’ flavor, i.e., compares to the performance of the oracle on the specific problem and not its worst-case guarantees.

The second contribution of this work is that the authors prove these guarantees to CTS. In particular, it shows that the linear regret lower bounds of [30] do not hold for any approximation oracle and breaks the misconception that CTS cannot be used with approximation oracles.

On the other hand, there are a few issues with this work. First, I believe that the lower bound doesn’t hold specifically to TS and that similar arguments should allow deriving lower bound to any (reasonable) algorithm (and I would love to read some discussion about the implications of the lower bound in [22] – if it holds in your setting, what is the contribution in Theorem 1?). In particular, I think that the lower bound stems from the comparison to the best greedy solution (and the fact that its value is nonsmooth - arbitrarily small changes might lead to constant difference), and not to the approximate-optimal value $(1-1/e)OPT$. Notably, the ‘problematic’ action $(u_3,u_4)$ is better than the $(1-1/e)OPT)$ (and is actually even better than the approximation ratio of $0.75\cdot OPT$ for $K=2$). Thus, the inverse-dependence in the squared gaps might be the result of the criterion, rather than the algorithm. This is not discussed in the paper and creates the (possibly wrong) impression that TS-based algorithms are inherently worse than UCB-based algorithms for CMABs. In some sense, I am not convinced that the ‘story’ of the paper is the hardness of TS in the standard CMAB setting (with approximation regret), but rather a positive result on the greedy regret. I think this might be an interesting alternative story, but it requires drastic changes in the paper.

As a side effect, I think that the lower bound is weaker than it should be (namely, hold for any consistent algorithm). In addition, the lower bound is proven on a small-scale problem. Therefore, it does not allow understanding the right dependence in problem-constants. 

Another issue is the specific combination of TS with a greedy oracle. As I see it, the main advantage of TS in CMAB problems is that it allows working with non monotone reward functions. As far as I know, greedy oracles have provable guarantees mainly (only?) for monotone (and submodular) combinatorial functions. Therefore, even though this is probably the most common family of oracles, the results do not allow using one of the greatest advantages of TS in this setting.

Finally, the requirement that $\epsilon\lesssim \Delta$, combined with a term of $\epsilon^{-6}$ (or even a higher power) might lead to a terrible problem-independent bound – can you comment on that?

Clarity/writing: in general, the paper is well written and I didn’t see any critical issues.

Comparison to previous works: I find it hard to compare the resulting bounds to previous works, as the gaps are differently defined. One interesting thing that got my attention is that the bound does not directly depend on K, in contrast to the ‘classical’ bounds of [7]. Such a dependence is unavoidable in the approximation regret for linear reward functions [Kveton et. Al, 2015], but in general, varies between reward functions and does not exist in the PMC problem [Merlis and Mannor, 2019]. Do you think that it stems from the different regret definition, gap definition, the maximization over $k$, or maybe from the dominating effect of $1/\Delta^2$ (instead of $1/\Delta$)? 
In general, I would love to see a more thorough comparison of the bounds to previous work (including the lower bounds of [22] that I already mentioned and their upper bounds).

Other comments:
- The set of all possible actions seems a bit nonstandard – can you say something about its relation to standard sets (e.g., it contains the uniform matroid, but what about other matroids/standard sets?)
- In multiple places, there are references to the OIM and PMC problems. First, I think that many readers would require some additional explanation on the problems (and maybe writing explicit reward functions). Moreover, even though OIM is mentioned numerous times, the authors only actually work with the PMC problem. Also, to the best of my knowledge, OIM usually requires probabilistically triggered arms. Thus, for clarity’s sake, I think it would be beneficial to either only write on PMC problems or give a more concrete example of a different instance of OIM.

Minor comments:
- Line 26: either ‘which is equivalent to’ or ‘or equivalently,’.
- Line 194: maximize -> minimize.
- Line 198-199 consider rephrasing – maybe ‘When greedy...’ -> ‘We say that greedy...’?
- Line 267: ‘we hope to use its...’ -> ‘use their....’

References:
- Kveton, Branislav, et al. "Tight regret bounds for stochastic combinatorial semi-bandits." Artificial Intelligence and Statistics. PMLR, 2015.
- Merlis, Nadav, and Shie Mannor. "Batch-size independent regret bounds for the combinatorial multi-armed bandit problem." Conference on Learning Theory. PMLR, 2019.

############

I thank the authors for the response, clarifications and corrections. In light of the response, I am inclined towards accepting the paper.

limitations_and_societal_impact: Some limitations were described in the paper. However, I already mentioned a few possible missing ones - the fact that the results are limited to greedy oracles (and therefore, monotone reward functions) and the possible bad behavior of problem-independent bounds.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a setting where Thompson Sampling with greedy approximation oracles is applied to combinatorial semi-bandit. The main contribution is to theoretically reveal how the suboptimality of greedy oracles can affect Thompson sampling in the worst case. Specifically, the greedy regret is shown to be lower bounded by $\Omega(\log T / \Delta^2)$. The authors also prove an almost matching upper bound. 

--- After rebuttal ---

I appreciate the authors' kind response. Having read all the responses and review comments, I've found that the result is more significant than I thought. Therefore, I increased my score to 6.  
main_review: This paper addresses an interesting theoretical question and presents nice results: a regret lower bound together with an almost matching upper bound. The results are interesting, and the paper is well written. However, I have two concerns, as detailed below. 

1. I'm not fully convinced that it is de facto standard to use greedy approximation oracles in each round of combinatorial semi-bandit. For example, most online submodular maximization algorithms do not simply use offline greedy oracles; they are tailored to the online setting. Therefore, I cannot see how significant the hardness result is, which focuses only on the case with greedy oracles (In my opinion, the hardness result would be stronger if lower bounds are obtained for general cases where offline oracles with certain approximation guarantees are available). 

2. The original definition of the greedy regret in [22] does not have $\max(\ast, 0)$. It seems that making the instantaneous regret in each $t$-th round non-negative makes it easier to prove the hardness result. Is it possible to obtain the lower bound for the original greedy regret without $\max(\ast, 0)$?
limitations_and_societal_impact: The limitations are described. The paper seems to have no negative societal impacts.
review_title: null

Meta-review: The reviewers generally appreciate the upper bound results in this paper.  Although the lower bound appears to be a bit weak, it is nevertheless a useful complement to the upper bounds. 
Decision: Accept (Poster)