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

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 $T$ rounds, it achieves $\tilde{O}(T^{2/3})$ 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 $\tilde{O}(\sqrt{T})$. 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.