Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing

2026-07-10 · Source: Artificial Intelligence · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

A new study introduces algorithms for contextual bandit problems with correlated arms and noisy surrogate reward signals, specifically motivated by Large Language Model (LLM) routing applications. Unlike traditional contextual bandits that assume conditional independence, this research accounts for context-dependent inter-arm correlations and leverages auxiliary, potentially misspecified, ML-generated reward information. Two approaches are proposed: a coupled reward-mixing method that combines true and surrogate rewards for faster learning when surrogates are reliable, and a decoupled prediction-mixing method that maintains separate estimators for robustness against surrogate misspecification. The decoupled approach achieves regret guarantees comparable to reward-only bandit methods in worst-case scenarios, while significantly improving regret when surrogate predictions are informative. Theoretical regret analyses are provided, and evaluations on LLM routing benchmarks demonstrate improved sample efficiency and superior accuracy-cost trade-offs compared to standard contextual bandit baselines and static routing methods.

Key takeaway

For AI Engineers designing LLM routing systems, this research offers a path to significantly improve efficiency and robustness. If you are currently using static routing or basic contextual bandits, consider implementing correlation-aware algorithms with surrogate rewards. Your systems could achieve better accuracy-cost trade-offs and higher sample efficiency, especially by adopting the decoupled prediction-mixing approach to mitigate risks from noisy or misspecified surrogate signals.

Key insights

Contextual bandits for LLM routing can leverage correlated arms and noisy surrogate rewards for improved efficiency and robustness.

Principles

• Inter-arm correlations can be modeled in contextual bandits.
• Surrogate rewards accelerate learning when reliable.
• Decoupling estimators enhances robustness to misspecified surrogates.

Method

The proposed method involves either pooling true and surrogate rewards (coupled reward-mixing) or maintaining separate estimators for bandit feedback and surrogate predictions, then adaptively combining them (decoupled prediction-mixing).

In practice

• Apply decoupled prediction-mixing for robust LLM routing.
• Use surrogate rewards to improve sample efficiency in bandit problems.
• Evaluate accuracy-cost trade-offs in dynamic routing systems.

Topics

• Contextual Bandits
• LLM Routing
• Surrogate Rewards
• Machine Learning Algorithms
• Sample Efficiency
• Accuracy-Cost Trade-offs

Best for: NLP Engineer, Research Scientist, AI Scientist, Machine Learning Engineer, AI Engineer

Related on AIssential

• Calibration-Gated LLM Pseudo-Observations for Online Contextual Bandits — LLM pseudo-observations can reduce cold-start regret in contextual bandits, but prompt design is critical.
• The Sample Complexity of Multiclass and Sparse Contextual Bandits — Algorithms achieve optimal sample complexity for s-sparse contextual bandits, closing a significant gap in prior work.
• Representation over Routing: Overcoming Surrogate Hacking in Multi-Timescale PPO — Decoupling multi-timescale signals in Actor-Critic RL prevents surrogate hacking and myopic degeneration, improving long-term planning.
• Information-Directed Sampling for Causal Bandits — Causal bandits with non-manipulable variables can leverage shared causal mechanisms for improved information-directed sampling and regret bounds.
• Chain of Uncertain Rewards with Large Language Models for Reinforcement Learning — CoUR uses LLMs, uncertainty quantification, and decoupled Bayesian optimization to create more efficient and robust RL reward functions.
• Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy — COF algorithm minimizes MAB-CS cost and quality regret by cost-ordered evaluation and sample aggregation.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Artificial Intelligence.