Bandits with Abstention under Expert Advice

Summary

This paper considers the problem of prediction with expert advice in the bandit feedback setting with the possibility of abstention. The game is sequential: where in each round the each of $E$ experts gives a distribution over $K+1$ actions/arms. One of these actions represents abstention, yielding a reward of 0, while the remaining $K$ actions have rewards in $[-1,1]$ and are set by an oblivious adversary. The contributions of this paper include a procedure called confidence-rated bandits with abstention (CBA), which is an adaptation of the well-known exponential weighted scheme. The authors present guarantees in the form of an upper bound on the expected cumulative regret. Additionally, they explore applications of the resulting algorithm in various other problems.

Strengths

The problem under consideration is both interesting and practically relevant, as the ability for a prediction strategy to abstain is crucial in many scenarios, particularly when the risk of making poor decisions is high. Additionally, accounting for the context is a significant and pertinent feature of modern applications.

Weaknesses

Overall, I find this paper unclear and difficult to read. The results obtained are not easily comparable to existing ones in the literature. 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 $u \in \mathcal{V}$, and $\mathcal{V}$ 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 $\rho(u)$ 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. Additionally, it is not clear how this work compares to previous research on online learning with abstention.

Questions

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.

Rating

4

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

See weaknesses section.

Summary

This paper investigates the problem of prediction with expert advice in contextual adversarial bandits, introducing the CBA (Confidence-rated Bandits with Abstentions) algorithm, they apply CBA to adversarial contextual bandits and achieve near-optimal upper regret bound.

Strengths

The CBA in adversarial contextual bandits achieves near-optimal upper regret bound.

Weaknesses

Weakness 1: This algorithm is not as efficient as Exp4. 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.

Questions

Q1: Why not consider the reward of the abstention action to be non-negative instead of zero? Q2: What is the novelty in the proofs?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The algorithm is not as efficient as Exp4 and the upper bound does not include the approximation error of $\lambda$.

Summary

The paper considers the problem of prediction advice under the bandit framework. There are $K$ arms plus a special $(K+1)$0-th arm, which always incurs the gain of 0; this arm may be interpreted as the action of abstaining. The learner outputs a distribution over $K+1$ handles and earns the scalar product gain. In other terms, the learner outputs a vector of $K$ non-negative components summing to a number between 0 and 1; the sum can be though of as the measure of its confidence. For this setup, the problem of prediction with expert advice is considered and a bound is obtained. There are two terms in the regret, one involves KL-divergence (there is a class of prediction with expert advice bounds of this kind) and the other has the form $O(\eta KT)$. It is seemingly linear, but $\eta$ can be tuned to get sublinear growth. The result has been applied to the framework with side information $x_t$. Each expert is associated with a pair $(B,k)$. Whenever $x_t\in B$, the expert bets everything on arm $k$ and is abstaining otherwise. The main result of the paper is applied to this scenario with finitely many experts based on disjoint balls and a matching lower bound is obtained. The case where $B$s are balls in a metric space is considered separately.

Strengths

I think this is a very interesting result in prediction with expert advice.

Weaknesses

No obvious weaknesses.

Questions

None

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

Yes.

Summary

This paper first considers the problem of bandits with expert advice, allowing the learner to abstain in any round. It introduces an algorithm, CBA, based on mirror descent, which can achieve a better cumulative regret bound in comparison with EXP4. The algorithm is then applied to adversarial contextual bandits, where the learner abstains in rounds where the given context is not covered by any expert. The paper provides upper and lower bounds on the cumulative reward, and details a more computationally-efficient implementation for settings where the contexts have inherent structure.

Strengths

- Online learning with abstention is an interesting and relevant problem for the community, and the extension of CBA to adversarial contextual bandits with abstention seems novel. - The paper presents reward bounds for both the bandits with expert advice problem and the adversarial contextual bandit problem. These bounds can improve upon those of existing algorithms. A lower bound is also provided for the latter setting. - The experiments offer some insights into the construction of basis functions for contextual bandits with abstention.

Weaknesses

- The paper can be quite difficult to follow at times. For instance, in Section 5, the discussion about covering foreground and background classes seems very abrupt. I understand this is mentioned in the introduction, but since the problem settings are formally introduced until later, the initial discussion is also confusing. In addition, the purpose of the experiments remains somewhat unclear to me -- they are not properly discussed, and there is this sudden change of theme from learning in bandits with abstentions to constructing basis functions for various graphs. I also find the contextualization relative to prior work somewhat inadequate -- there are not enough details about the SpecialistExp algorithm to make the comparison concrete (lines 215 - 223). See also questions below. - The improvement of CBA over EXP4 is somewhat vague and seems to largely depend on the set of experts. It would be nice if some concrete examples are provided. - There is an $\mathcal{O}(\ln |\mathcal{B}|)$ gap between the upper and lower bounds in Section 5, which is substantial as $|\mathcal{B}|$ can be exponential in the size of the set of contexts. - 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.

Questions

- 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? - In Corollary 5.1, can $M$ be any number in $\mathbb{N}$ for the sequence of basis elements to be disjoint? - How are the corresponding actions $b_j$ chosen? - In Section 5, what are the specific benefits of allowing the learner to abstain?

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

2

Limitations

It would be nice if the authors include a separate section/paragraph that discuss the limitations in detail.