acceptodds
Under review as a conference paper at ICLR 2027

Delegate-UCB: Regret-Audit Tradeoffs in Online Human-AI Delegation

Abstract

Organizations adopting AI must learn which tasks to automate, yet the evidence needed to make that decision can itself be costly. We study online delegation in established human–AI teams, where human assignments provide routine performance feedback but independent assessments of AI outputs require paid audits. Notably, an audit can evaluate an AI candidate even when a human performs the task, allowing the organization to learn about future automation without changing current execution. We formulate this problem as a contextual bandit with fixed human and AI capabilities and prove that every no-audit policy suffers linear worst-case regret. We propose Delegate-UCB, which combines optimistic allocation with uncertainty-driven audits and targets human-route audits using overlapping human-AI confidence intervals. Under a noisy linear-residual model over rounds, it achieves expected total regret, including audit costs, matching the minimax horizon dependence asymptotically for fixed problem parameters. A known positive lower bound on the machine's suboptimality gap improves the upper bound to . With a fixed organizational tolerance , the same algorithm instead achieves polylogarithmic -insensitive regret, with explicit dependence on tolerance and audit cost. Both refinements are obtained by adjusting the audit threshold to the required precision. A two-context construction further demonstrates the value of audit placement: human-route audits acquire information early enough to prevent subsequent routing errors. We examine these audit settings through controlled experiments, showing how audit placement and precision affect the balance between routing regret and review cost. We further evaluate Delegate-UCB in a matched-horizon ImageNet16H replay and show that Delegate-UCB can reduce total regret relative to other benchmark auditing strategies.

Primary area:
learning theory
Keywords:
Human-AI Delegation, Multi-armed Bandit, Organization Learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_cKpoOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online delegation between multiple human options and an AI automation option. The authors model this as a linear contextual bandit problem, where each arm corresponds to a human or to the AI, and each arm has a known cost. Unlike the usual bandit setting, where the reward is observed after every pull, the AI arm has no inherent cost and its reward is not observed by default. Instead, the learner can pay a cost to audit the AI’s output and observe its reward (and may do so even when not playing the arm). The paper presents an algorithm for this setting along with a mainly theoretical regret analysis, and it includes some numerical experiments.

Critical strengths
  1. The setting is timely. Delegation between humans and AI systems is a relevant question, and I agree with the high-level observation that using machine outputs is entangled with the need to audit them. Allocating work in human-AI pipelines while accounting for the cost of oversight is a practical problem, so a well-posed model of it could be of broad interest. The theory seems reasonable, though I did not check the appendix, and the paper includes numerical experiments.
Critical weaknesses
  1. The paper is poorly presented. The introduction is jumbled, the contributions are stated in technical terms before the model is made precise, and the paper uses terminology which is unfamiliar and not grounded in the literature. If a reader cannot easily understand the setting, it is not possible to assess its novelty relative to the large bandit literature, or follow the results.
  2. The value of developing theory for this specific setting is not clear. The model makes several asymmetric and specific choices (see the questions below), and it is not clear whether the algorithm and analysis depend on them. Some of the results are trivial. Theorem 1 follows directly from the setting: if no reward is observed for one arm, then clearly never auditing it leads to bad outcomes.
Questions for authors

Clarifications:

  1. Relation to existing bandit models: Which bandit models in the literature are most closely related to this one, and what makes this setting significant or difficult in comparison? By the end of the introduction, it is still unclear to me what the intellectual interest and novelty of the setting and contribution are relative to the large bandit literature. The selection of related work is reasonable, but the paper is missing a clear discussion of how the models/algorithms in these works connect to this paper. Which ones does the current model extend, and which share similar algorithmic or analytical approaches?

  2. Specificity of the setting. The technical setting is oddly asymmetric. The reward from humans is always observed by default, so the fixed costs for humans implicitly include a mandatory audit. For the AI, no reward is observed unless an audit is opted into, and the AI can be audited at any point. Why can't we do the same for the human options? I.e., pay a cost to audit their output without using it, or pay an additional cost to obtain less noisy labels of quality even from humans? A model with multiple agents, each with potentially different skills, costs and audit costs, would include the single-AI setting as a special case. Would the algorithm or analysis be so different for a generalized setting? A generalized setting which includes these options seems better to develop theory and algorithms for (then the current analysis would follow as a special case).

  3. Theorem 2. If I substitute the definition of Δ_B into the inequalities in Theorem 2, the expression seems to be missing a factor of 1/4. Is this a typo?

Suggestions:

  1. The ordering of the introduction is jumbled. For example, introducing the notation c_R at this point is out of place. Lacking citations, there is no indication of how this problem is studied in related work. As presented, I am not sure the motivation for the specific model is reasonable, and grounding it in the literature would help.

  2. The contributions listed in the introduction are too technical for that stage of the paper, since the details of the model are not yet precise. I suggest stating them in plainer terms and making the novelty relative to the bandit literature explicit.

  3. MixUCB (Su et al., 2025) also seems related and should perhaps be included.

  4. The terminology around residuals is confusing ("predictable pretrained machine score"). Only the reward is being calibrated or learned from feedback, but the idea of residuals makes it sound like the machine itself might be improving over time. Why does it matter to already have a score and learn a residual from that score, and how is this really different from an unknown score overall?

  5. The boldface "comparative advantage" paragraph is oddly placed, and I don't see what purpose it serves. Is the header supposed to apply to the assumptions below it?

  6. The notation I_ν(Δ) is confusing. Does ν take the values + and −, or +1 and −1? Also, why is the argument sometimes Δ and sometimes γ?

  7. Corollary 1 uses terms like "level is interior" and "radius does not bind," and I don't know what these mean. More generally, the paper should define its terminology or use standard terms from the literature.

  8. The description of the experiments is not written in a very clear style and should be revised. Furthermore, the numbers in the table show a lot of overlap in the bootstrapped confidence intervals, so it is not clear what the takeaway is. The table is also hard to read, and I think a plot with visual error bars would make the comparison more obvious.

5 comments
AuthorsOpenReview ↗

Response to Reviewer cKpo (1/3) — Model and contribution

We sincerely thank the reviewers for their time and constructive feedback. Below, we provide detailed responses to the reviewers’ comments. We have also submitted a revised PDF that adds radiology and medical coding examples, clarifies the link to prior bandit work, and explains when early AI audits help.

Thank you for asking how our feedback structure relates to existing bandit models and how the analysis would change if other handlers could also be audited.

Which bandit models are closest, and what changes here? A standard linear contextual bandit observes a reward from the chosen arm. Tucker et al. (2023) allow the learner to pay to observe that arm's reward. Our learner chooses who handles the task and separately decides whether to buy a quality assessment of the AI candidate. A human assignment can therefore generate two observations on the same task: routine feedback about the human who handled it and a paid score for the unused AI output. We use standard linear-bandit confidence bounds for routing, and the worst-case T2/3T^{2/3} horizon exponent is shared with Tucker et al. MixUCB (Su et al., 2025) uses uncertainty to decide when to ask an expert for an action or reward predictions. In our setting, the audit scores a fixed AI output and leaves the current handler in place.

The separate feedback channel lets the learner acquire information about AI quality before assigning a task to AI. In Proposition 2, both policies initially give the tasks to a human. Those early tasks are more informative about the same AI quality parameter that matters for the later tasks. In the noiseless example in Table 2 (Appendix A.3), with the same optimistic router and threshold, Delegate-UCB buys two early audits and avoids later misrouting. Machine-only buys four audits on later tasks that it initially sends to the inferior AI. At 0.05 per audit, the total regrets are 0.10 and 1.40, respectively. Both rules satisfy the same worst-case upper bounds. The benefit in this example comes from the order and informativeness of the tasks. In general, the avoided routing loss must cover any net increase in audit costs.

The analysis also distinguishes two reasons an organization may need fewer audits. If the AI is worse than the best human by a known minimum margin whenever it is suboptimal, calibration to that precision is enough to rule out further mistakes on unaudited AI routes on the confidence event. This gives a O~(T)\widetilde O(\sqrt T) upper bound on ordinary total regret for fixed problem parameters. If the organization instead accepts a shortfall of up to ϵ\epsilon on each task, the bound is polylogarithmic for fixed ϵ>0\epsilon>0 under the corresponding objective, which charges only routing loss beyond ϵ\epsilon and still counts all audit costs.

AuthorsOpenReview ↗

Response to Reviewer cKpo (2/3) — Feedback and audit options

Why does the workflow treat human and AI feedback differently? We study AI adoption in workflows that already assess human work. In our model, the cost of routine human assessment is included in cjc_j. Documented organizational workflows motivate this feedback asymmetry. In professional translation, Translated reports that reviewers and project managers provide quality feedback on each human translation job. After delivery, quality and professionalism scores inform subsequent translator selection through its T-Rank system. Thus, evaluating human work and updating assessments of individual translators are already embedded in the production process. Translated production process · T-Rank In healthcare, an attending radiologist had to score a resident's preliminary report before sign-off. In medical coding, HRS reviewed every case coded by new coders or coders newly assigned to a client until they met an accuracy target, then switched to sampling. For AI outputs, however, the ChestLink manual describes periodic review of a sample of autonomous chest radiograph reports. In a company announcement, Savista reported that its separate coding deployment with Minset moved from full review to an ongoing 10% audit sample.

When AI is introduced into an established human workflow, the question is whether the organization wants to evaluate every AI output. Reviewing every AI output can reduce the economic and operational benefits of automation if review is costly. We therefore study selective auditing. The organization can use the same rubric and pays an additional cRc_R for each AI assessment, regardless of who handles the task.

What would change if every handler had its own audit options? A broader model could let the learner pay to evaluate an unselected human or obtain a more precise score for the human who handled the case. If those are additional options and routine feedback remains available, the current policy is still feasible and can retain its guarantee by using the original feedback channels. To exploit the new options, the acquisition rule would have to choose which candidate to assess and which type of feedback to buy. If AI assignments also yield routine scores, the learner gains an additional source of feedback. If routine human assessments become optional, the proof changes. It bounds cumulative human-routing loss by summing confidence widths along assignments that each update the selected human's estimate. A new analysis must control loss on human assignments without feedback and account for the cost of human assessments.

Changes in the revision. Section 1 illustrates routine human assessment and selective AI review using separate radiology and medical coding workflows. Section 1.1 explains that Tucker et al. study paid feedback from the chosen arm and that MixUCB queries an expert for an action or reward predictions. Our audit can score the AI candidate when a human is assigned, with the current handler staying in place. Section 4.1 identifies the shared worst-case upper bounds and explains the benefit of early feedback in the two-block example.

AuthorsOpenReview ↗

Response to Reviewer cKpo (3/3) — Theory, exposition, and experiments

Thank you for checking the constants and notation and for suggesting a clearer way to present the replay comparisons.

Theorems 1–2 and the 1/41/4 factor. Theorem 1 is an indistinguishability argument. With zero audits, an AI that is better than the human and an AI that is worse can produce the same observed history, even when the human's utility is known. Theorem 2 quantifies how much routing loss remains when feedback is available but limited. Its expected audit budget BB applies in each of the two instances. Let u=σ/B+1u=\sigma/\sqrt{B+1}, where σ\sigma is the audit noise standard deviation and SS bounds the residual magnitude. The substitution is

=\frac{3T}{8}\min\\{S,u/4\\} \ge \frac{3T}{32}\min\\{S,u\\}.$$ The last step uses $\min\\{S,u/4\\}\ge\min\\{S,u\\}/4$, so $3/32$ includes the factor in question. In $\mathcal I_\nu(\Delta)$, $\nu\in\\{-1,+1\\}$ is the sign of the AI residual and $\Delta>0$ is its magnitude. Theorem 1 uses $\gamma$ for the magnitude in the no-audit pair, and Theorem 2 uses $\Delta_B$ for the budget-dependent magnitude. **What do the conditions in Corollary 1 mean?** The corollary balances a routing-loss lower-bound term that falls as $\sigma T/\sqrt{B+1}$ in this regime against an audit-cost term that grows as $c_R B$. Balancing the two terms gives an audit count on the order of $b=(\sigma T/c_R)^{2/3}$. For example, $1\le b\le T$ puts that scale within the feasible range of audit counts. The condition $S\ge\sigma/\sqrt b$ ensures that the model permits residuals large enough to construct the hard instances at that scale. **What does the pretrained score contribute?** The baseline $b_0(x)$ is an input available before the decision. For example, if a classifier reports 0.90 confidence on tasks where its true accuracy is 0.75, the mean residual is −0.15. The model assumes that the correction is linear in the task features. The baseline can itself be nonlinear, so the resulting mean quality $b_0(x)+x^\top w^\star$ need not be linear. Audits update the organization's estimate of the fixed classifier's performance. In Section 2, “predictable” means the score is available before routing and auditing. Setting $b_0=0$ gives direct estimation of linear mean quality. **Introduction and terminology.** Section 1 uses examples from radiology and medical coding to explain how the workflow determines which scores are observed. The two decisions are who handles the current task and whether to pay $c_R$ for an AI assessment. Our theory quantifies how much AI feedback the organization needs to buy to reduce routing errors. In Section 2, “comparative advantage” means that the preferred handler can change across tasks as the human–AI utility difference changes. **What does the replay show?** The evaluation replays recorded ImageNet16H data. On each of 50 seeds, the policies share task order and potential human feedback. We compare total regret, the sum of routing loss and audit spending, using paired differences. In the 960-round replay, Delegate-UCB minus Machine-only is −1.94 [−2.56, −1.32] at an audit price of 0.01 and −1.25 [−2.17, −0.35] at 0.05. These are pointwise 95% paired bootstrap intervals. At 0.20, Front-N (audit the first $N$ tasks) has the lowest observed mean at 960 rounds. The paired differences versus Machine-only and Front-N are +0.23 [−0.95, 1.42] and +2.14 [−0.15, 4.51], respectively, with Delegate-UCB first in both differences. Both paired intervals at 960 rounds and an audit price of 0.20 include zero. At 3,840 rounds, Machine-only has the lowest observed mean at 0.20. Thank you for suggesting error bars. Table 1 reports the policy means with intervals for both horizons, and Appendix D.3 gives the 960-round paired intervals for comparisons between policies.
Reviewer_FJ26OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies the setting of human-AI online delegation where an organization decides which agent deals with which task and whether to purchase expensive feedback about the AI’s performance. They first write the problem as a contextual bandit problem where human assignments give feedback and the quality of machines is assessed through audits. The authors show that the policies without the audits result in a Ω(T2/3)\Omega(T^{2/3}) minimax lower bound when all the audit costs are included. They also propose Delegate-UCB which is an algorithm that selects both assignments and the audits, where the latter is done through uncertainty of the machine. Finally, the authors also give some experiments and detailed ablation studies, including the ImageNet16H offline replay which evaluates different elements such as costs of audit and routing regret.

Critical strengths

The paper is well motivated, i.e., through the writing, where it is clear in terms of differentiating the task assignment and the acquiring of information. This then allows machine outputs to be audited even if humans can perform the task which enables a productive mechanism for learning without changing decisions. The bounds are also clearly explained in terms of giving a characterization of the learning cost of effective delegation policies.

Critical weaknesses

It’s unclear whether Delegate-UCB is actually a useful algorithm empirically, especially in the Imagenet16H replay case. Also it seems that Delegate-UCB does not even get the lowest mean regret at the highest audit price. Most of the experiments also assume a linear residual model and the nonlinear misspecification evaluation shows that it performs worse than random auditing or machine only case. Another concern is that the regret guarantees only hold for simple machine only auditing, so it is unclear whether there is any benefit of auditing human assigned tasks. It would be useful to have a general explanation of when the strategy improves regret or efficiency of auditing. See questions for additional concerns.

Questions for authors
  • Just to clarify the significance of having this auditing rule, are there more general conditions under which we get a provable improvement in regret for auditing tasks that are human assigned? Do we get decreased regret under these conditions? It would help position the proposed auditing strategy as actually a better method instead of just another alternative.
  • In the nonlinear misspecification settings, it seems that having auditing strategies that are simpler do better than Delegate-UCB. Exactly what type of task distribution where we will see that audits that are human routed will be beneficial?
3 comments
AuthorsOpenReview ↗

Response to Reviewer FJ26

We sincerely thank the reviewers for their time and constructive feedback. Below, we provide detailed responses to the reviewers’ comments. We have also submitted a revised PDF that adds radiology and medical coding examples, clarifies the link to prior bandit work, and explains when early AI audits help.

Thank you for asking when human-route audits improve total regret and for pointing out the mixed results at high audit prices and under model misspecification.

When a human handles a task, the audit scores the AI's candidate output for that same task. The human still handles the task, and the organization pays cRc_R for the AI score. At a common uncertainty threshold, both policies use the same optimistic routing rule and audit AI-routed tasks at or above the threshold. Delegate-UCB can also buy the AI score on a human-routed task when AI uncertainty reaches that threshold and the confidence intervals overlap.

When does getting that score early pay off? Early audits help when early tasks reveal how the AI will perform on later tasks that Machine-only would otherwise misroute, and the avoided routing loss exceeds any net increase in audit spending. For example, the early score can reveal that the AI is worse than the human on those later tasks. Delegate-UCB can then send them to the human while Machine-only still overestimates the AI and sends them to AI. Each avoided misassignment saves the utility gap between the two handlers. If the early score tells us little about later tasks, it may save little routing loss.

A provable case. In Proposition 2, both policies assign the initial block to a human. The early tasks are more informative about a shared AI quality parameter than the later tasks. Delegate-UCB uses two early audits to establish that the human is also better on the later tasks. Machine-only enters the second block without AI feedback and initially routes those tasks to AI. In the noiseless example (Table 2 in Appendix A.3), Delegate-UCB buys 2 audits and has zero routing loss. Machine-only buys 4 audits and incurs 1.20 in routing loss. At 0.05 per audit, their total regrets are 0.10 and 1.40, respectively. Both policies satisfy the same worst-case upper bounds because the analysis requires audits on AI routes at or above the threshold and allows audits on either route at that precision. The improvement in Proposition 2 concerns the particular task sequences in the construction.

For policies that never audit, Theorem 1 gives a linear worst-case lower bound. The T2/3T^{2/3} minimax lower bound in Corollary 1 applies when paid audits are available and their costs enter total regret, under the stated parameter conditions.

What the experiments show. With Gaussian assessment noise of standard deviation 0.03, the two-block example still favored Delegate-UCB in mean total regret (0.110 versus 1.883 for Machine-only). Permuting the same tasks narrowed that gap (0.484 versus 1.876). In a separate fine-threshold experiment, Delegate-UCB had lower mean routing loss (0.20 versus 8.22) but bought many more audits (583.86 versus 75.18), so at 0.05 per audit it had higher mean total regret (29.39 versus 11.98). Holding those policies and trajectories fixed, the routing savings cover the extra audits below a price of about 0.0158. Under strong nonlinear misspecification, where the omitted component was as large as the linear residual in standard deviation, mean total regret was 26.61 for Delegate-UCB, 24.12 for Machine-only, and 24.68 for full-budget random auditing.

ImageNet16H replay. At 960 rounds, Delegate-UCB's total regret minus Machine-only's was −1.94 [−2.56, −1.32] at an audit price of 0.01, −1.25 [−2.17, −0.35] at 0.05, and +0.23 [−0.95, 1.42] at 0.20. Brackets give pointwise 95% paired bootstrap intervals. At the highest price, Front-N (which audits the first NN tasks) had the lowest observed mean at 960 rounds and Machine-only at 3,840 rounds. The 960-round difference between Delegate-UCB and Front-N was +2.14 [−0.15, 4.51].

Changes in the revision. Section 4.1 now states that Machine-only satisfies the same worst-case upper bounds. It clarifies what the audit scores when a human handles the task and how an early AI score can prevent later misrouting, using Proposition 2 in Appendix A.3. Appendix C.11 gives the ordering and audit-price comparisons, Appendix C.7 gives the nonlinear sensitivity study, and Appendix D.3 gives the 960-round paired replay results.

Thank you for your detailed response but I am still concerned about applicability of this and the underlying assumptions, so I will keep myself score.

Thank you for taking the time to read our response and share your feedback.

Reviewer_ZcfbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper considers a setting where tasks can be assigned to human or AI. The quality of human work can be observed without cost, while additional auditing is needed to observe the quality of AI work. For each tasks, there are two decision making problem: Assign the task to human or AI? Buy additional auditing or not? The authors point out that although the task is assigned to human, the organization may still buy AI auditing to accumulate information for future routing. Based on this, the authors propose Delegate-UCB, a method based on optimistic routing and selective auditing. In the linear model setting, the author prove a regret upper bound for proposed method and it significantly better than the no auditing methods. In the experiment on dataset ImageNet16H, the authors further demonstrate the effectiveness of the proposed method.

Critical strengths

The idea itself is intuitive, the task assigned to human could be a good chance to learn the performance of AI.

Critical weaknesses

The key setting in the paper is the quality of human work can be observed without cost, while the quality of AI is needed to be auditing. There are some explanation in the paper, e.g. Page 1 line 46-50, Page 3 remark 1. But I do not think it is sufficient. A unresolved problem is why not just using the same rubrics to evaluate AI performance. I think there should be at least one concrete example.

Questions for authors
  1. Could the author help me understand the setting in the real word? See Weaknesses for details.
3 comments
AuthorsOpenReview ↗

Response to Reviewer Zcfb

We sincerely thank the reviewers for their time and constructive feedback. Below, we provide detailed responses to the reviewers’ comments. We have also submitted a revised PDF that adds radiology and medical coding examples, clarifies the link to prior bandit work, and explains when early AI audits help.

W1. Human work appears to be assessed at no cost, while assessing AI output requires an audit.

We would like to clarify how assessment costs enter our model. We study an organization introducing AI into an established human workflow. Each human assignment already yields a routine score. In our model, the human assignment cost cjc_j covers the assessment already built into the workflow. The feedback asymmetry is motivated by documented organizational workflows. In professional translation, Translated reports that reviewers and project managers provide quality feedback on each human translation job. After delivery, quality and professionalism scores inform subsequent translator selection through its T-Rank system. Thus, evaluating human work and updating assessments of individual translators are already embedded in the production process. Translated production process · T-Rank When AI is introduced, the question is whether the organization wants to evaluate every AI output. Reviewing every AI output can reduce the economic and operational benefits of automation if review is costly. We therefore study selective auditing. The organization can use the same rubric and pays an additional cRc_R for each AI assessment, regardless of who handles the task.

Changes in the revision. Section 1 illustrates when review is routine and when it is selective. At Hospital Italiano de Buenos Aires, an attending had to score a resident's preliminary report before signing the final report. In medical coding, HRS reviewed every case coded by new coders or coders newly assigned to a client until they met an accuracy target, then switched to sampling.

For AI outputs, the ChestLink manual describes periodic review of a sample of autonomous chest radiograph reports. In a company announcement, Savista reported that its separate coding deployment with Minset moved from full review to an ongoing 10% audit sample. Diaz and Ulla (2019) · ChestLink user manual, Sections 3.2–3.3 · Journal of AHIMA roundtable (2016) · Savista announcement (2026)

Thanks you for the clarification and the example. It partially solve my concern. However, I still feel the setting is quite limited in real world. Overall, I decide to keep my score.

Thank you for taking the time to read our response and share your feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.