Bandits with Abstention under Expert Advice

Thank you for your time and effort in reviewing our paper.

The results obtained are not easily comparable to existing ones in the literature.

Our results can be, for example, compared to EXP4 (see reply below) and SpecialistEXP (see e.g., our reply to reviewer Edre). In both cases we achieve at least the same bounds and in many cases achieve significantly better bounds. We will improve our exposition and a add a more thorough discussion and in the final version.

For instance, in the case of regret minimization with expert advice, such as the analysis of the EXP4 algorithm, regret is typically defined with respect to the best fixed expert in hindsight. The fact that the authors develop guarantees with respect to the best combination of experts (where this combination is not necessarily convex, since the set of vectors , and as defined in line 123 is not the set of convex weights) can be very confusing for the reader. The authors discuss comparisons with the guarantees of the EXP4 algorithm and state that "The EXP4 bound essentially replaces the term in our bound by $\rho(u)/u$" in line 138. However, it is unclear how this translates in terms of worst-case guarantees. This part clearly needs a thorough discussion to be convincing.

You are right in that both the reward of our algorithm and that of Exp4 are measured with respect to a linear combination of experts and for Exp4 that linear combination is required to be convex (i.e. the weights have to sum up to $1$). Typically the weights of our linear combination sum to some value $S$ far greater than $1$ (and never less than $1$). Hence (as the regret term limits to $0$) our reward is $S$ times that of Exp4. We will add this discussion to the paper for clarity.
The fact that “Exp4 bound essentially replaces the term in our bound by $\rho(u)/|u|_1$” is because Exp4 plays with the weight vector $u$ normalized at each time step and therefore operates in a stricter space.

The results obtained are not easily comparable to existing ones in the literature. [...] Additionally, it is not clear how this work compares to previous research on online learning with abstention. How do your results compare to [1]?

[1] Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Proc. COLT, pages 3030–3048, 2020.

We note that, to the best of our knowledge, there are no previous results on adversarial contextual bandits with the abstention option. The main novelty of the paper lies in merging the abstention action with confidence-rated predictors. This allows us to extend our result to (adversarial) contextual bandits with the abstention option. We introduce the first cumulative reward bounds on confidence-rated experts and we investigate contextual bandits as a potential application. Note that the cumulative reward bound we obtain is not achievable by previous work on confidence rated experts as they scale the regret by the confidence of the best expert in hindsight. We discuss previous results on online learning with abstention in the main body, but the previously considered settings are different from the ones we consider. Moreover, previous methods cannot be directly applied to confidence-rated predictors. Specifically, our results cannot be directly compared to [1], as their learning setting is different; it is a full information (in contrast to our bandit setting) binary classification problem.

Thank you for your time and effort in reviewing our paper.

Weakness 1: This algorithm is not as efficient as Exp4.

Given that the numerical precision of our machine is bounded, our algorithm has exactly the same $\mathcal{O}(EK)$ efficiency as Exp4. See the additional result presented in the general rebuttal for our time complexity (equal to that of Exp4 up to logarithmic factors) when the precision is unbounded.

Weakness 2: In the algorithm, they mentioned using interval bisection to find $\\lambda$, but the regret upper bound does not include the approximating error of interval bisection.

We took the assumption that the degree of precision was bounded (the interval bisection method requires $\mathcal{O}(\ln(P))$ steps where $P$ is the precision. Thanks to your question, we attached a proof in the general rebuttal that removes this assumption. When the magnitudes of the components of the comparator u are bounded by some arbitrary value Z (which will typically be very small) we can achieve a time complexity of $\mathcal{O}(EK+E\ln(EZT))$ whilst only adding an additive factor of 1 (which can be made arbitrarily small) to the regret.

Q1: Why not consider the reward of the abstention action to be non-negative instead of zero?

We can have any range $[-a,b]$ with any $a,b > 0$ and the reward of the abstention action can be any fixed constant. This can be achieved by scaling and translating the reward (on any trial) when received - bringing it into the constraints of our paper (hence Thm 3.1 still applies but the regret term is scaled by some constant in $\mathcal{O}(a+b)$). Such a scaling approach is standard in online learning.

Q2: What is the novelty in the proofs?

Our proof borrows ideas from the analysis of mirror descent, EXP3, and the method of Lagrange multipliers (also with unbounded precision (see general comment)) . However, we note that the main novelty of our work was the realization that making such a modification to mirror descent would lead to true reward bounds for confidence-rated predictors. We note that mirror descent itself would not work as the constraint set is not known until after the last trial (and, even if it was known, computing the projections would be computationally hard).

Thanks for the very encouraging feedback!

Thank you for your time and effort in reviewing our paper.

[...] $\log|B|$ gap and $|B|$ can be exponential in the number of contexts $N$.

While the comment is true, $|B|$ can indeed be as large as $2^N$ in principle, such a large basis set would defy its purpose (as an inductive prior on the shape of the clusters). All the basis sets we consider have size $|N|^2$, thus, the $\log|B|$ gap is just logarithmic in $N$. Generally, we think of $B$ as a set of “simple” stereotypical sets, which, for example, can be quantified by assuming $B$ has finite VC-dimension. In that case $\log|B|=\mathcal{O}(\mathrm{vc}(B)\log N)$ the dependence is still logarithmic in $N$ by the Sauer lemma.

[...] there is this sudden change of theme from learning in bandits with abstentions to constructing basis functions for various graphs [...] There seems to be a lack of discussion on the intuition behind why CBA should be applied for adversarial contextual bandits with abstention in this particular way.

A natural application of experts, and therefore confidence-rated experts, is adversarial contextual bandits with a finite context space. In this setting, it is quite common in the literature (e.g., [1], [2]) to consider a graph structure over the contexts. Therefore, we decided to study a practical application of confidence-rated experts, where the experts, in our case, are the basis elements we introduce. We will improve the exposition here in the final version.

[1] Cesa-Bianchi et al. "A gang of bandits." NeurIPS 2013.

[2] Wu, Qingyun, et al. "Contextual bandits in a collaborative environment." SIGIR 2016.

[...] there are not enough details about the SpecialistExp algorithm to make the comparison concrete (lines 215 - 223). See also questions below.

We shall add the regret bound of SpecialistExp to the paper. The difference is that while our regret is $\mathcal{O}(\sqrt{MKT\ln(N)})$ where $M$ is the number of disjoint basis elements that exactly cover each of the foreground (non-abstention) classes, the regret of SpecialistExp is $\mathcal{O}(\sqrt{M’KT\ln(N)})$ where $M’$ is the number of disjoint basis elements that cover each of the classes (including the background/abstention class). As depicted in Figure 1, $M’$ can be much larger than $M$.

In Section 5, what are the specific benefits of allowing the learner to abstain?

The benefits of the abstention action are clear when dealing with contexts (and therefore nodes in graph-structured contexts) that do not have a behavior that reflects the inductive bias. In Figure 1 of the provided example, you can think of any point in white as being colored in any possible way, but we would need a ball that covers any of these points as in SpecialistsEXP. Therefore, abstaining avoids having to deal with points that present “unnatural” behavior with respect to our inductive bias.

Following Theorem 3.1, can you provide a concrete example where $||u||_1=|E|$. The example given in the footnote seems to require all other experts to have confidence 0 in the round where the expert has confidence 1. What conditions need to be imposed on the set of experts?

Assuming each expert has confidence 1 on at least one trial (otherwise $||u||_1$ could be much higher) then $|E|$ is the maximum possible value of $||u||_1$. The condition for having such a value of $||u||_1$ is that the sum of the confidences of all experts are, on any trial, no greater than $1$. Such a $u$ is not that interesting - we place equal weight on each expert - but it was introduced in order to show just how high $||u||_1$ can be, so that the potential degree of improvement over Exp4 is huge. Things are much more interesting at slightly lower values of $||u||_1$.

In Corollary 5.1, $M$ can be any number $\mathbb{N}$ in for the sequence of basis elements to be disjoint?

$M$ corresponds to the number of basis elements in the comparator. Hence, as we assume the basis elements to be disjoint in Corollary 5.1., $M$ is only restricted by the size of the number of contexts $|\mathcal{X}|$ and the size of the basis $|\mathcal{B}|$. We will clarify this in the final version.

How are the corresponding actions $b_j$ chosen?

The $b_j$ are simply the actions in the comparator sequence. The result holds for an arbitrary such sequence.