ORUCB Algorithm: How to Correct Expert Answers and Reduce Costs in Online Learning

Why Imperfect Experts Are Still Worth Consulting

In machine learning's learning-to-defer paradigm, a system often needs to choose between making its own prediction and consulting an external expert. Traditional approaches assume that an expert's answer is either accepted as-is or discarded entirely. But reality is more nuanced: an imprecise expert can still provide valuable information once their answers have been appropriately corrected.

This paper published on arXiv (arXiv:2610.07084) offers a compelling perspective — A Query Is Not a Commitment. Before paying for an expert's answer, the learner must not only choose which expert to consult, but also pre-specify a correction function to apply after receiving the response. This mechanism treats the expert as a calibratable information source rather than a final authority.

The Core Challenge: Dual Contamination of the Loss Signal

The real difficulty in this setting is that the observed loss signal is jointly contaminated by two factors: the expert's inherent quality and the correction function that hasn't yet been fully learned. In other words, when the system makes frequent errors early on, it's hard to tell whether the fault lies with the expert's answer quality or with an undertrained correction function.

This creates a subtle trap: high early error rates may cause the router to prematurely abandon certain experts whose answers would have delivered high value once the correction function matured. This problem — "missing long-term value due to early misjudgment" — is an amplified version of the classic exploration-exploitation trade-off in online learning.

The exploration-exploitation trade-off is a foundational problem in reinforcement learning and online learning: a system must balance "exploiting" options known to work well against "exploring" options whose potential is uncertain. Over-exploitation leads to local optima; over-exploration wastes resources. In this paper's setting, the tension is further amplified: an expert's true value depends on the quality of the learned correction function, which itself requires sufficient query data to converge. If the router reduces queries to a particular expert due to high early error rates, the correction function lacks training data and error rates remain elevated — creating a self-reinforcing negative feedback loop. This is precisely why a dedicated exploration mechanism that is aware of correction errors is needed, rather than simply applying a standard multi-armed bandit algorithm.

ORUCB: Fusing Shared and Expert-Specific Responses

The proposed algorithm is called ORUCB, and its design rests on two key components:

Pooling Polynomial Responses

ORUCB pools shared responses and expert-specific responses through polynomial modeling. This means the algorithm can capture correction patterns common to all experts while retaining personalized adjustments for each expert individually — improving learning efficiency when data is scarce.

Confidence-Weighted Risk Regression with Exploration Calibration

The algorithm establishes an upper bound on the cumulative response learning error and uses this bound to calibrate both confidence-weighted risk regression and the exploration strategy. As a result, when the router decides "which answer to purchase," it actively accounts for the fact that the correction function is still being learned, avoiding myopic decisions driven by temporary high errors.

Learning to defer is an important research direction in human-AI collaboration systems. The central question is: when should a machine act autonomously, and when should it hand off decisions to a human expert or external system? Traditional learning-to-defer frameworks typically treat experts as reliable "black boxes" — either fully trusting their output or discarding it entirely. This paper's innovation lies in breaking that binary assumption by introducing the concept of a "calibratable expert": instead of using the expert's answer directly, it serves as a raw signal that is processed through a learned correction function before use. This framework better reflects real-world scenarios — for example, the outputs of large language models often require post-processing, and human annotators' judgments may contain systematic biases. Both can be viewed as information sources that need calibration.

Theoretical Guarantees and Applicability

Under a set of assumptions — including bounded residuals and divergences, a fixed feasible model for optimal responses, and linear models for free-query risk and optimal-query risk — ORUCB achieves a high-probability pseudo-regret bound of $O(\sqrt{T}\log(T+1))$ over $T$ rounds.

This guarantee is notably robust:

• It allows singular answer distributions
• It tolerates misspecified shared response models
• Its optimality is defined relative to a bounded response class

In other words, even when the model specification deviates from reality, the algorithm still provides a provable performance lower bound — a property of significant practical importance for deployment.

Pseudo-regret is a core metric for evaluating online learning algorithms, defined as the expected difference between the algorithm's cumulative loss and the cumulative loss of the best policy known in hindsight. Unlike "regret," pseudo-regret targets the expected loss of the optimal policy rather than the worst-case actual loss, making it more amenable to theoretical analysis. A bound of $O(\sqrt{T}\log(T+1))$ means that as the number of rounds $T$ grows, the average additional loss per round approaches zero, and the algorithm's long-term performance converges to the optimum. This order of magnitude is close to the best possible theoretical guarantee under no parametric assumptions — the lower bound for the standard multi-armed bandit problem is $O(\sqrt{T})$, and the additional $\log(T+1)$ factor in this paper stems from the added complexity of simultaneously learning the correction function.

Experimental Results

The study validated the approach on four test data streams. Results show that the chosen cubic polynomial policy outperforms seven baselines that deploy uncorrected expert answers directly, in terms of total cost including query fees.

The experiments also conduct comparisons along two dimensions:

• Against a common correction learner, examining differences in routing decisions
• Across six pricing scenarios, measuring the relationship between cost and query rate

These comparisons demonstrate that pre-specifying a correction function and incorporating correction error into routing decisions yields meaningful economic benefits — particularly when each query carries a fee.

Significance and Takeaways

The contribution of this work lies in redefining how expert answers are used in human-machine collaboration. In many practical systems — such as calling paid APIs, consulting human annotators, or querying external models — every query has a cost, and expert answers are rarely perfect.

The framework provided by ORUCB shows that rather than simply trusting or discarding experts, the better approach is to systematically correct their outputs while remaining fully aware during decision-making that this correction is itself still being learned. This provides both a theoretical foundation and a practical path toward building more economical and robust learning-to-defer systems.