Fast Rates for Bandit PAC Multiclass Classification

We thank the reviewer for the time and effort. Please see our comment below to the specified questions.

• “Line 177: What is J_{x,y}?”

This is a typo and should be replaced by $r_{x,y}$, this will be fixed in the final version. Thanks for catching!

• “Could the procedure allows for a better dependency with respect to $K$?”

We believe that the polynomial dependence on $K$ in the regret bound could be reduced, but we are currently unsure how exactly this can be done and what is the correct optimal dependence.

We thank the reviewer for the time and effort. Please see our comment below to the specified weaknesses and questions.

• “...This means that if K is relative large, you mind end up doing worse than the previous bounds which limits the scope of impact of this work.”

You are correct in that our current bounds improve upon previous results in regimes where $K$ is not too large relative to $1 / \epsilon$. However, we believe that removing polynomial dependencies in $K$ from the main $1/\epsilon^2$ term is a crucial and significant step towards a comprehensive understanding of the bandit multiclass problem.

• “What would be a scenario where this bound performs better than the previous work, although theoretically this is better?”

Since this is a purely theoretical study, we do not focus on empirical scenarios in which our algorithm may outperform existing ones. Our results formally show that if we aim to find an $\epsilon$-optimal policy where $\epsilon \ll 1 / K^4$, then our suggested algorithm uses considerably less samples than known algorithms which require $K / \epsilon^2$ samples.

We thank the reviewer for the time and effort. Please see our comment below to the specified questions.

• “What are the known lower bounds (if any) in the bandit agnostic PAC setting? Is a poly factor of 𝐾 unavoidable?”

We can prove a simple lower bound of $K / \epsilon + 1 / \epsilon^2$ for bandit multiclass classification as follows: The $1 / \epsilon^2$ term arises from a standard argument for two labels with probabilities $1/2 + \epsilon$ and $1/2 - \epsilon$ (this is the full information lower bound). The $K / \epsilon$ lower bound holds for an instance with two examples $x_1$ and $x_2$ and $K$ labels, where the probability of sampling $x_1$ is $2 \epsilon$ and $x_2$ has probability $1-2 \epsilon$ (each example has a unique unknown correct label). A PAC learner for this instance must correctly predict the label of $x_1$, and to do that it needs at least $\Omega(K)$ samples of $x_1$, which takes a total of $\Omega(K / \epsilon)$ samples. We believe that the polynomial dependence on $K$ in our upper bound can be further improved to decrease the gap from the lower bound described above, but we are unsure how this can be done with our current techniques.

• “...Do you have any insight on what the right characterization of bandit PAC learnability might be in this case?”

Good question. Yes, there is a relatively simple characterization: a class H is learnable if and only if the following holds: (i) it has finite Natarajan dimension, (ii) there is a finite bound $K$ such that for every point $x$, the set {$h(x) : h \in H$} has at most $K$ distinct labels. Item (i) is clearly necessary, and it is relatively simple to prove that Item (ii) is necessary (it is necessary already for learnability in the realizable-case). For sufficiency, note that if Item (ii) holds then the class $H$ is effectively equivalent to a class over $K$ labels in total and therefore can be learned when its Natarajan dimension is finite, as follows from Theorem 2 in our work. We will add this to the final version of our paper, thanks for pointing this out!

We thank the reviewer for the time and effort. Please see our comment below to the specified weaknesses and questions.

• “...Can this be improved? Perhaps with a computationally inefficient algorithm?”

We believe that the sample complexity (specifically, the polynomial dependence on $K$) could be reduced even with a computationally efficient algorithm, but we are not sure how to do that with our current approach.

• “The paper claims to resolve an open problem from Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011)...”

Specifically, we refer to the paragraph titled “The price of bandit information in the batch model” in section 4 of Daniely et al. (2011), where the authors note that “...it would be interesting to find a more tight characterization of the sample complexity in the bandit setting” while observing that the known multiplicative gap was linear (up to log factors) with the size of the label space. Since our results establish a sample complexity bound that matches (up to log factors) the full information bound for small values of $\epsilon$, we view our results as a resolution of this question.

• “Can the techniques developed in this paper be used in more general bandit settings to yield improved bounds?”

In the more general contextual bandit setup where there is no presumed structure on the reward functions, the best sample complexity achievable is of the form $K / \epsilon^2$ which can be obtained by the trivial algorithm which pulls actions uniformly at random and returns the policy with the best empirical reward. For the online objective of regret minimization, we believe that variants of our approach can be used to obtain the optimal $\sqrt{KT}$ regret in contextual bandits with a computationally efficient algorithm which is perhaps simpler than the previous approaches of Dudik et al. (2011) and Agrawal et al. (2014), but we did not attempt to work this out in full detail.

• “The $J_{x,y}(h)$ after Eq (3) must be $r_{x,y}(h)$.”

You are correct, this is a typo that will be fixed in the final version. Thanks for catching!

• “It appears to me that your technical approach is quite similar to that of [12]. Can the authors comment on the similarities and differences with that work?”

The work of [12] considers the more general contextual bandit setting with the online objective of regret minimization. Their approach essentially amounts to adaptively computing low-variance sampling distributions which also induce high estimated reward in order to minimize regret over time. Our approach is similar in the sense that we also aim to compute a low-variance sampling distribution with which to estimate rewards of hypotheses, but in the setting we consider there is a special structure on the rewards (namely, a “sparse” one-hot structure) which allows us to compute such a low-variance distribution in time complexity that is polynomial in $K$, and then use it to estimate the rewards of all hypotheses uniformly with only $K / \epsilon + 1 / \epsilon^2$ samples. This approach would not work for regret minimization, since the initial phase alone would incur linear regret. We also add that our algorithm makes use of a stochastic Frank-Wolfe procedure in order to efficiently compute the low-variance sampling distribution, an approach which highly differs from the optimization scheme employed in each round in [12].

Thank you for the response. I maintain my current rating, favoring the acceptance of the paper.

We thank the reviewer for the time and effort. Please see our comment below to the specified weaknesses and questions.

• “...it would be nice for the authors to discuss how future works could reduce the degree of the poly dependence upon $K$.”

We believe that the polynomial dependence on $K$ could be reduced, but we are currently not sure how this can be done with our current techniques. One possibility is to employ an adaptive approach which combines estimated reward maximization together with lowering the variance of the sampling distribution over time. We will incorporate a short discussion in the revision, thanks for this suggestion.

• “It would also be nice to have more discussion when comparing to contextual bandits…”

The vast majority of previous works on contextual bandits study the online objective of regret minimization. Our setting of bandit PAC multiclass classification most closely resembles a contextual bandit setup with a different objective of finding a nearly optimal policy with as few samples as possible.

• “I believe the paper would benefit from a conclusion and perspectives on future work in the main text.”

Agreed - we will add a conclusion section in the revision, incorporating a discussion of the two points you suggested earlier.

• “Do the authors think there is a relation to contextual bandits in the PAC setting e.g. "Instance-optimal PAC Algorithms for Contextual Bandits" Li et al. ?”

Thank you for bringing this paper into our attention; we will make sure to cite and discuss it in subsequent versions of our paper. The work of Li et al. considers the PAC variant of contextual bandits, where no structural assumptions are made apriori on the reward functions. In this setting, they prove instance dependent sample complexity bounds, from which worst-case bounds of the form $\approx K / \epsilon^2$ can be inferred. To our understanding, there is no direct relation between instance dependent bounds and the single-label classification setting which we consider, as even for the simple case of multi-armed bandits, the standard sample complexity bound of the form $\sum_i (1 / \Delta_i)$ does not suffice to obtain an improved result for sparse rewards. To obtain adaptivity to sparsity, the bounds must actually be variance-dependent (rather than gap-dependent), which to our understanding is not addressed in the work of Li et al.

• “Have the authors considered instance dependent bounds, specifically for a finite hypothesis class?”

We have not previously considered instance-dependent (that is, gap-dependent) sample complexity bounds, as obtaining improved instance-independent bounds, regardless of sparsity, is in itself a highly nontrivial problem. Obtaining such bounds in the multiclass setting is a fantastic question for future research.