Online Decision Deferral under Budget Constraints

Authors: Mirabel Reid, Tom Sühr, Claire Vernade, Samira Samadi
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Online Learning, Human-AI Collaboration

Abstract:
Machine Learning (ML) models are increasingly used to support or substitute decision making. In applications where skilled experts are a limited resource, it is crucial to reduce their burden and automate decisions when the performance of an ML model is at least of equal quality. 
However, models are often pre-trained and fixed, while tasks arrive sequentially and their distribution may shift. In that case, the respective performance of the decision makers may change, and the deferral algorithm must remain adaptive. We propose a contextual bandit model of this online decision making problem. Our framework includes budget constraints and different types of partial feedback models. Beyond the theoretical guarantees of our algorithm, we propose efficient extensions that achieve remarkable performance on real-world datasets.

Decision: reject
Reviewer scores: 3, 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1730368988580

thread_type:
official_review

<thread_object>
creator: reviewer_a7cx

<content>
summary:
This paper introduces a new online decision-making problem that includes budget constraints and different types of feedbacks. The authors formalize this problem into a contextual bandit setting and propose a new algorithm for generalized linear rewards. They show that the algorithm achieves a near-optimal regret bound. They also validate its effectiveness with empirical results on real-world datasets.

strengths:
a. The authors consider an interesting and practical problem that is well-motivated.

b. The paper provides both theoretical analysis and experimental results for the proposed algorithm. The regret bound of the algorithm is near-optimal under certain conditions. Experiments are conducted on both synthetic and real datasets, and the proposed algorithms outperform the baselines.

c. The presentation is clear and easy to follow.

weaknesses:
a. The proposed algorithm and analysis largely build on the work of Agrawal and Devanur (2016), which addresses a similar problem. Although the authors claim that they extend the algorithm to generalized linear rewards, it is unclear what specific challenges this extension presents and whether it requires new techniques.

b. The theoretical results only hold when the budget $B$ is relatively large, $B \geq d^{1/2} T^{3/4}$. This requirement may limit the applicability of the algorithm in scenarios with a limited budget.

c. The neural linear algorithm is a straightforward extension of Algorithm 1, treating the neural network’s embedding as the context. And there is no theoretical guarantees for the neural linear algorithm.

d. In the experiments, the authors only consider scenarios where $B$ is at least $0.25T$, which is a relatively large budget when $T$ is large. Results for smaller values of $B$ would be helpful to further validate the algorithm's performance.

questions:
a. Is it possible to obtain a theoretical guarantee (even if suboptimal) when $B$ is relatively small?

b. What is the challenge in extending the work of Agrawal and Devanur (2016) to your setting?

c. What are the empirical results of the proposed algorithm when $B < 0.25T$, such as $0.1T$?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730705405842

thread_type:
official_review

<thread_object>
creator: reviewer_moqa

<content>
summary:
The paper proposes using the framework of Bandits with Knapsacks to choose a model's prediction or to defer to a skilled expert, where the expert is the limited resource available to the meta learner.

strengths:
None

weaknesses:
The paper has limited novelty and contribution.

1. The paper simply uses the an existing framework (Bandits with Knapsacks [Badanidiyuru et al., 2018], [Agrawal and Devanur, 2016]) to choose between a model's prediction or to defer to a skilled expert.
2. Limited contribution:
- The regret guarantee provided is a straightforward combination of the linear contextual bandit with knapsack guarantee [Agrawal and Devanur, 2016] with the generalized linear bandit analysis from  of [Li et al. (2017)], with the bulk of proof in the appendix filled with re-statments of specific Lemmas and Corollaries from [Agrawal and Devanur, 2016] and [Li et al. (2017)].

- The experiments are very limited. Section-5.1 is synthetic, while section 5.2 provides results for two different problems: 1) 0-1 Knapsack problem, that chooses between human solutions to the 0-1 knapsack problem and the solution to a greedy algorithm. This does not align with the original desription of distribution shift leading to decline in ML model's prediction accuracy. 2) ImageNet: chooses between a pretrained model and human prediction. Although this aligns with the original problem set-up, the evaluation is shallow and limited.

3. Some missing references on further developments in Bandits with Knapsacks:

- https://arxiv.org/abs/2211.07484v6

- https://arxiv.org/abs/2210.11834

- https://proceedings.mlr.press/v162/sivakumar22a.html

- https://proceedings.mlr.press/v238/deb24a

questions:
- Could the authors specify the contributions if any, beyond a simple combination of [Agrawal and Devanur, 2016] and [Li et al. (2017)] and the limited empirical evaluation on the ImageNet dataset?

- There have been several new developments in the Neural Bandits literature since Riquelme et al. (2018) (see [1], [2] and [3]). Why have the authors not used these frameworks instead?

[1] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 11492–11502. PMLR, 2020.

[2] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representation (ICLR), 2021.

[3] Rohan Deb, Yikun Ban, Shiliang Zuo, Jingrui He, and Arindam Banerjee. Contextual bandits with online neural regression. In The Twelfth International Conference on Learning Representations.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730970022506

thread_type:
official_review

<thread_object>
creator: reviewer_ykhm

<content>
summary:
This paper studies an online decision-making problem with a human expert. The authors phrase the problem as a contextual bandit problem, where a deferral learner needs to choose whether to use an ML model or a human expert to obtain the reward. The authors propose an algorithm to solve this problem based on a UCB-like algorithm and characterize its regret guarantees. The authors further extend their algorithm using neural networks to handle complicated datasets.

strengths:
1. The problem formulation and the algorithm design seem to be novel and of practical interest. 
2. Theoretical regret guarantees are provided for the proposed algorithms.

weaknesses:
1. Considering optimal static policy seems to be limited as it can be far from the true dynamic optimal policy. Would it be possible or how difficult it is to extend the current regret analysis in the paper to handle dynamic regret which uses the dynamic optimal policy as benchmark?
2. The regret analysis seems to be straightforward extensions from existing works on UCB-based algorithms for bandit problems as the authors mentioned in Section~4.
3. There is no regret guarantee for the neural linear algorithm provided in the paper. Could you at least explain the specific challenges in deriving such guarantees for this approach?

questions:
1.	In line~163, what is the distribution D there?
2.	Does Algorithm~1 work for the full information setting or the bandit information setting? Please clarify how the algorithm design differs when full information or bandit information is considered.  It would be good to discuss the implications of using the algorithm in each setting, and how this choice affects the algorithm's performance or implementation.
3.	In general full information online learning algorithm typically yields smaller regret (e.g., algorithms for online convex optimization Hazan9 & Levy NIPS 2014). Could you explain why this is not the case for the algorithm studied in this paper?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731480339423

thread_type:
official_review

<thread_object>
creator: reviewer_xyma

<content>
summary:
The manuscript introduces a framework for online learning-to-defer under constrained budget for the human expert.

strengths:
The topic of the manuscript originates from a practical problem.

weaknesses:
The original contribution of the paper is hard to justify as it is largely based on the work of Agrawal and Devanur (2016).

questions:
See the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732559749536

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Clarification: This is not a conventional "Bandit paper"

comment:
Dear reviewers, 

Thank you for your feedback. We will respond to specific concerns but we would like to stress one simple point: this is not a conventional "bandit paper" in the sense that our contribution is NOT to design and analyse a bandit algorithm. In fact, in Introduction, the last paragraph specifically does NOT list this as a contribution because we always refer to existing literature and existing results in Section 4 (Algorithm). As such, your comments on "lack of novelty"(*) of our method and analysis are CORRECT, but they often and sadly sidetrack the main contribution which is to give a purpose and a concrete application to these good existing algorithms. This application is in Machine Learning with Human in the Loop, the main topic of our paper.

Bandit algorithms with Knapsack constraints have been extensively studied (we will add citations suggested by Rev. MoQa) from a theoretical or algorithm-design perspective. On the other hand, the literature on (Online) Learning to Defer (see our Related Work, first 2 paragraphs), has not considered the problem of learning under potentially partial information. Rather than proposing a new algorithm, we show how to efficiently apply existing good ones to a hard and novel problem, and we demonstrate their efficiencies on several new experiments including new and original datasets. We believe that we always explicitly refer to the relevant papers whenever we quote theoretical results and we explicitly write: "The regret guarantees (Corollary4.3 below) combine the proof of Agrawal and Devanur(2016) with results on unconstrained generalized linear bandits (Filippietal.,2010;Lietal.,2017)". 

It is not obvious, however, that such online deferral algorithm would work on real data, beyond the theoretical setting of these papers. Our paper is the first to show that one can indeed make them work in practice and the community lacks even benchmarks to test ideas. 
We illustrate them on novel benchmarks including recently published datasets. These findings are novel. 

We hope this clarifies the main contribution. We will make sure to reflect this discussion in the main paper. 

Best wishes,
The authors

(*) See in particular
Rev, a7cX: a,b,c
Rev MoQa: 1,2
Rev. ykhm: 2
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers point out that the paper does not have algorithmic novelty. The authors clarify that this is the case, and the main point of novelty is to run an existing algorithm on a publicly available dataset. As such, there doesn't seem to be much disagreement between the two parties on the technical merit. My judgment ultimately rests on the fit: the authors should consider submitting the paper to a more practice-oriented venue (icml and neurips would likely be difficult). A good choice can be MSOM practice based research competition (see https://pubsonline.informs.org/page/msom/practice-based-research-competition) as well as the various tracks of the journal MSOM. The authors will likely have an easier time there.