Pith. sign in

REVIEW 3 major objections 5 minor 65 references

Contextual bandits that use model correlations and noisy ML surrogate rewards can route LLMs with less exploration, and a decoupled mixer stays as safe as ordinary bandits when the surrogates fail.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 00:59 UTC pith:5T2JZXZ4

load-bearing objection Solid combination of graph feedback and noisy surrogates for LLM routing, with a clean best-of-both-worlds meta-algorithm; the theory is careful, the experiments are consistent, and the main soft spot is that ε_n is assumed rather than measured. the 3 major comments →

arxiv 2607.09015 v1 pith:5T2JZXZ4 submitted 2026-07-10 cs.LG cs.AI

Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing

Ajay Narayanan Sridhar , Ronak Singh , Mehrdad Mahdavi , Vijaykrishnan Narayanan This is my paper
classification cs.LG cs.AI
keywords contextual banditsLLM routingsurrogate rewardsgraph feedbackregret boundsmodel selectionexpert aggregation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Choosing which large language model to call for each query is a contextual bandit: only the chosen model’s accuracy and cost are observed, and the best choice depends on the query. Standard methods treat models as independent and ignore offline predictors, so they explore too much. This paper shows that context-dependent correlations among models, together with machine-learning surrogate rewards for a small set of related unplayed models, can cut the effective number of arms from K down to roughly K over (m+1). A coupled algorithm pools true and surrogate rewards into one predictor and gains speed when surrogates are reliable; a decoupled meta-algorithm keeps a pure bandit expert and a surrogate-aware expert and mixes their policies adaptively. The decoupled design recovers ordinary bandit regret in the worst case and inherits the improved rate when surrogates are informative, which the routing-benchmark experiments confirm through lower cumulative regret and better accuracy–cost trade-offs.

Core claim

In contextual bandits with context-dependent inter-arm correlations and ML surrogate rewards for graph neighbors of the chosen arm, a decoupled prediction-mixing algorithm achieves best-of-both-worlds regret: it matches standard reward-only contextual-bandit rates when surrogates are useless or misspecified, and improves by a factor that scales with the number of surrogate observations when those surrogates are sufficiently accurate.

What carries the argument

CABS-D (Correlation-Aware Bandits with Surrogates Decoupled): an adaptive expert-aggregation master that treats a standard bandit-feedback learner and the coupled graph-feedback learner CABS-C as two experts, mixes their policies with second-order exponential weights, and thereby obtains the minimum of the two regret bounds.

Load-bearing premise

Every surrogate reward equals the true expected reward of that model plus a fixed per-model bias plus noise whose size never exceeds a known bound; if the offline predictor is badly wrong, the promised speed-up vanishes.

What would settle it

On the same LLM-routing benchmarks, replace the reward oracle with a deliberately high-noise or systematically biased predictor and check whether CABS-D’s cumulative regret remains comparable to ordinary LinUCB/SquareCB while CABS-C degrades; if CABS-D also degrades below the ordinary bandit baseline, the robustness claim fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Online LLM routers can safely incorporate offline ML predictors without risking worse-than-bandit performance when those predictors are misspecified.
  • When inter-model correlations are strong and surrogates are accurate, sample complexity of routing scales with effective arm count K/(m+1) rather than K.
  • Accuracy–cost Pareto frontiers for dynamic routing improve over both static routers and standard online bandit baselines under realistic single-reward feedback.
  • The same best-of-both-worlds template applies to any multi-option selection problem that supplies graph-structured side information and proxy rewards.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same decoupled mixing pattern could protect other systems that rely on cheap proxy labels—recommendation, A/B testing, or multi-treatment trials—against proxy misspecification.
  • If the affinity graph itself must be learned online rather than supplied by an oracle, the extra estimation cost may partially cancel the claimed m-factor gain.
  • Clipping cost-aware utility to [0,1] can hide regimes where very expensive models dominate, so reported Pareto gains may shrink under unbounded cost penalties.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies contextual bandits with context-dependent inter-arm correlations and ML-generated surrogate rewards, motivated by LLM routing under accuracy–cost trade-offs. It proposes CABS-C, which debiases and pools true and surrogate rewards under a graph-feedback exploration rule, and CABS-D, which treats a standard bandit expert (SquareCB) and CABS-C as experts and mixes them with adaptive Hedge-style weights. Under realizability, a regression oracle, strong observability, and a fixed-bias plus bounded-noise surrogate model (Assumption 4.4), CABS-C obtains Õ(√(α T Reg_Sq(T)) + ε_n √(α K T)) regret, while CABS-D obtains a best-of-both-worlds bound matching the minimum of ordinary contextual-bandit and surrogate-aware rates (Theorem 4.9, Corollary 4.10). Experiments on RouterBench, SPROUT, and Open LLM Leaderboard v2 report improved utility and lower relative cumulative regret versus LinUCB/LinTS/ε-greedy and competitive performance against static routers across cost regimes.

Significance. If the results hold as stated, the contribution is a clean and practically relevant bridge between graph-feedback contextual bandits and auxiliary ML predictors, with an explicit robustness mechanism (prediction mixing) that recovers standard rates under surrogate misspecification. The linear m-feedback specialization, reducing effective action dependence from K to K/(m+1) when ε_n is small, is a useful interpolation between bandit and full-information feedback. Strengths include fully written regret proofs in Appendix F (martingale concentration, independence-number arguments, IX estimators, meta-regret decomposition), a best-of-both-worlds meta-algorithm with explicit overhead terms, and multi-benchmark LLM routing experiments with full-feedback oracles and static baselines. The work is of interest to both bandit theory and systems-oriented LLM serving.

major comments (3)
  1. [§4.1–4.2, Assumption 4.4, Corollary 4.10, Lemma F.4] Corollary 4.10 and the discussion after Corollary 4.8 make the improved rate contingent on ε_n = Õ(√(d/K)) so that the surrogate term does not dominate. Assumption 4.4 and Lemma F.4 make this dependence explicit via the observation-noise piece of E[B_T]. The manuscript never reports an empirical estimate of residual surrogate error (or post-debias |s − r| / |ξ|) for the trained Reward Oracle on RouterBench, SPROUT, or Open LLM LB v2. Without that check, Tables 1–2 and Figures 2–3 cannot be attributed to the theoretically claimed noise regime versus affinity-graph structure, meta-Hedge overhead, or other implementation choices. Please add a measurement of ε_n (or a proxy residual after Algorithm 1’s running-average debias) and discuss whether the observed gains fall in the regime where the first term of the min dominates.
  2. [Algorithm 1, Theorem 4.7, Theorem F.9, Appendix D] Theorem 4.7 and Lemmas F.5–F.8 analyze a deterministic feedback graph with independence number ≤ α, while Algorithm 1 (lines 5–6) samples a stochastic affinity graph G_t with A_t,(i,j)=1 w.p. σ((1−R_t,(i,j))/2). The passage from random graphs to a fixed α (and to the m-regular transitive specialization α=K/(m+1) in Theorem F.9) is not justified. Either extend the analysis to expected independence number / concentration of the sampled graph, or state that theory applies only after conditioning on a realized strongly observable graph and clarify how m is controlled in experiments (IQR pruning in Appendix D further sparsifies neighbors).
  3. [Algorithm 1 lines 11–12, Lemma F.4, Lemma F.7] The bias estimator in Algorithm 1 (line 12) updates ˆb with (s_t,j − x_t^⊤ ˆθ_t,j). Early rounds confound fixed bias b_j with regression error Δ_τ,j, which is exactly the regression-propagation term bounded in Lemma F.7. The paper should either (i) delay bias updates until ˆθ is stable, (ii) analyze the joint estimation error more carefully under misspecification of b_j as time-varying, or (iii) ablate bias estimation off vs on in the routing experiments. As written, the de-biasing step that underpins robustness of CABS-C is only partially supported by the analysis and not validated empirically.
minor comments (5)
  1. [§3–4, Appendix F] Notation switches between rewards and losses (ℓ=1−r) across Algorithms 1–3 and Appendix F; a short consistent convention statement would help.
  2. [Figure 1] Figure 1 is referenced early but the roles of AO/RO/RS are only fully specified later; a one-sentence caption expansion would improve readability.
  3. [§6] Computational complexity O(K³+RS) is discussed in §6; please report wall-clock per-round times for CABS-D vs LinUCB on the largest K (Open LLM LB v2, K=18) to ground the claim that surrogate overhead is negligible (0.22 ms) relative to the convex solve.
  4. [Appendix E.1, Table 7] Table 7 (Open LLM LB v2 CABS-C vs CABS-D) shows smaller gaps than Table 1; briefly discuss dataset heterogeneity as a possible cause.
  5. [§1, §4.1] Typos / polish: “be utilizing” → “by utilizing” (§4.1); “assurrogate” spacing in the introduction; ensure arXiv ID and citation formatting are consistent.

Circularity Check

0 steps flagged

No significant circularity: regret bounds are derived from stated assumptions via standard online-learning inequalities; empirical gains are measured on held-out splits against independent baselines.

full rationale

The paper's central claims (Theorems 4.7/4.9, Corollaries 4.8/4.10) are asymptotic regret upper bounds obtained by decomposing expected regret into an optimization term, regression-oracle regret, and a bias/noise term under Assumptions 4.1–4.5, then applying Cauchy–Schwarz, Azuma–Hoeffding, graph independence-number bounds (Lemma F.6 from Alon et al.), and adaptive Hedge-style master analysis. None of these steps defines the target quantity in terms of itself, renames a fitted constant as a prediction, or rests on a uniqueness theorem or ansatz imported only from the present authors. Citations for SquareCB, SquareCB-G/UG, AdaHedge/Corral, and NeuralUCB are to external prior work and are used as algorithmic building blocks with explicit adaptations (surrogate de-biasing, prediction mixing), not as self-justifying uniqueness results. Offline RO/AO training on train splits and evaluation on test splits is ordinary supervised pretraining plus online bandit evaluation; it does not make the online regret statements true by construction. The skeptic concern that ε_n is assumed rather than measured on the benchmarks is a theory–experiment linkage / correctness gap, not a circular reduction of the derivation. Score 0 with empty steps is therefore the honest finding.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 3 invented entities

The central regret claims rest on five explicit assumptions (realizability, regression oracle, strong observability, bounded surrogate noise, minimum probability) plus the existence of two oracles (affinity and reward) whose quality is summarized by ε_n and the independence number α. Free parameters control exploration and cost sensitivity; the algorithms themselves are the main invented objects.

free parameters (4)
  • γ (exploration / regularization)
    Tuned in theory to √(α T / Reg_Sq) and set to 4 in linear experiments; directly balances the optimization term against regression regret.
  • ρ (cost-sensitivity)
    Swept over {0…1000} to define low/medium/high regimes; the utility r = y − ρ c is clipped to [0,1] and is the quantity optimized by every method.
  • ε (minimum probability floor)
    Assumption 4.5 forces p_t,i ≥ ε by mixing with uniform mass; appears in all logarithmic factors of the noise bounds.
  • ε_n (surrogate noise bound)
    Upper bound on |ξ_t,i| in Assumption 4.4; the improved rates require ε_n = Õ(√(d/K)), otherwise the surrogate term dominates.
axioms (5)
  • domain assumption Realizability: there exists f* in F such that E[r_t,i | x_t] = f*(x_t,i) for all t,i (Assumption 4.1).
    Standard for SquareCB-style analyses; if the true reward is not in the function class the regression oracle bound fails.
  • domain assumption Regression oracle guarantee: cumulative squared error of RS is at most Reg_Sq(T) (Assumption 4.2).
    Abstracts the online regression subroutine; linear case uses Vovk-Azoury-Warmuth with known d log(T/d) bound.
  • domain assumption Strong observability of the feedback graph (self-loops plus independence number α) (Assumption 4.3).
    Needed for the graph-theoretic lemmas that replace K by α in the regret.
  • ad hoc to paper Surrogate model st,i = f*(xt,i) + bi + ξt,i with |ξ| ≤ ε_n and E[ξ]=0 (Assumption 4.4).
    Encodes the quality of the offline ML predictor; the paper’s improved rates are conditional on this bound being small.
  • standard math Minimum selection probability p_t,i ≥ ε for all arms (Assumption 4.5).
    Technical device to keep importance weights bounded; achieved by mixing with uniform.
invented entities (3)
  • CABS-C (coupled reward-mixing algorithm) no independent evidence
    purpose: Pools debiased true and surrogate rewards into a single regression model guided by a context-dependent feedback graph.
    Core algorithmic contribution; regret scales with K/(m+1) when surrogates are good.
  • CABS-D (decoupled prediction-mixing meta-algorithm) no independent evidence
    purpose: Maintains SquareCB and CABS-C as experts and mixes them with adaptive Hedge-style weights to obtain best-of-both-worlds regret.
    Provides the robustness guarantee that is the paper’s main theoretical selling point.
  • Affinity Oracle (AO) and Reward Oracle (RO) no independent evidence
    purpose: Produce the context-dependent correlation matrix / graph and the surrogate reward vector, respectively.
    Black-box interfaces that turn offline data into the side information the algorithms consume; implemented as MLP heads on mDeBERTa embeddings.

pith-pipeline@v1.1.0-grok45 · 42533 in / 3378 out tokens · 41039 ms · 2026-07-13T00:59:00.475770+00:00 · methodology

0 comments
read the original abstract

We study contextual bandit problems with correlated arms and access to surrogate reward signals produced by a machine learning model, motivated by applications such as large language model (LLM) routing. Unlike classical contextual bandits that rely solely on bandit feedback and assume conditional independence across arms, our setting allows context-dependent inter-arm correlations and auxiliary reward information that may be noisy or misspecified. We propose algorithms that leverage such surrogate rewards through two complementary designs. A coupled reward-mixing approach pools true and surrogate rewards to accelerate learning when surrogate signals are reliable, while a decoupled prediction-mixing approach maintains separate estimators for bandit feedback and surrogate rewards and adaptively combines their predictions. This decoupling yields robustness to surrogate misspecification, recovering regret guarantees comparable to reward-only bandit methods in the worst case, while achieving improved regret when surrogate predictions are sufficiently informative. We provide theoretical regret analyses for both approaches and evaluate them on LLM routing benchmarks under varying accuracy versus cost trade-offs. The results demonstrate improved sample efficiency and consistently better accuracy-cost trade-offs compared to standard contextual bandit baselines and strong static routing methods.

Figures

Figures reproduced from arXiv: 2607.09015 by Ajay Narayanan Sridhar, Mehrdad Mahdavi, Ronak Singh, Vijaykrishnan Narayanan.

Figure 1
Figure 1. Figure 1: Overview of the LLM routing task and the proposed CABS-C/CABS-D online learning pipeline. The [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Accuracy vs cost Pareto Frontier curves across datasets on Linear Online models. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Relative Cumulative regrets with respect to LinUCB for other linear online learning methods on Open [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Relative Cumulative regrets with respect to LinUCB for other linear online learning methods on [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Accuracy vs cost Pareto Frontier curves across datasets on Neural Online Learning models. [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Relative Cumulative regrets with respect to NeuralUCB for other neural online learning methods on [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

65 extracted references · 7 linked inside Pith

  1. [1]

    Corralling a band of bandit algorithms

    Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. InConference on Learning Theory, pages 12–38. PMLR, 2017

    2017

  2. [2]

    Analysis of thompson sampling for the multi-armed bandit problem

    Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39–1. JMLR Workshop and Conference Proceedings, 2012

    2012

  3. [3]

    Thompson sampling for contextual bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In30th International Conference on Machine Learning (ICML), 2013

    2013

  4. [4]

    Online learning with feedback graphs: Beyond bandits

    Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. InConference on Learning Theory, pages 23–35. PMLR, 2015

    2015

  5. [5]

    Non- stochastic multi-armed bandits with graph-structured feedback, 2014

    Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Non- stochastic multi-armed bandits with graph-structured feedback, 2014

    2014

  6. [6]

    Finite-time analysis of the multiarmed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235–256, 2002

    2002

  7. [7]

    The nonstochastic multiarmed bandit problem.SIAM journal on computing, 32(1):48–77, 2002

    Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem.SIAM journal on computing, 32(1):48–77, 2002

    2002

  8. [8]

    Relative loss bounds for on-line density estimation with the exponential family of distributions.Machine learning, 43(3):211–246, 2001

    Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions.Machine learning, 43(3):211–246, 2001

    2001

  9. [9]

    New results on the independence number

    Yair Caro. New results on the independence number. Technical report, Technical Report, Tel-Aviv University, 1979

    1979

  10. [10]

    Understanding bandits with graph feedback.Advances in Neural Information Processing Systems, 34:24659–24669, 2021

    Houshuang Chen, Shuai Li, Chihao Zhang, et al. Understanding bandits with graph feedback.Advances in Neural Information Processing Systems, 34:24659–24669, 2021

    2021

  11. [11]

    Frugalgpt: How to use large language models while reducing cost and improving performance.Transactions on Machine Learning Research, 2024

    Lingjiao Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance.Transactions on Machine Learning Research, 2024. 13

    2024

  12. [12]

    Routerdc: Query-based router by dual contrastive learning for assembling large language models.Advances in Neural Information Processing Systems, 37:66305–66328, 2024

    Shuhao Chen, Weisen Jiang, Baijiong Lin, James Kwok, and Yu Zhang. Routerdc: Query-based router by dual contrastive learning for assembling large language models.Advances in Neural Information Processing Systems, 37:66305–66328, 2024

    2024

  13. [13]

    Leveraging (biased) information: Multi-armed bandits with offline data

    Wang Chi Cheung and Lixing Lyu. Leveraging (biased) information: Multi-armed bandits with offline data. InForty-first International Conference on Machine Learning, 2024

    2024

  14. [14]

    Llm routing with dueling feedback.arXiv preprint arXiv:2510.00841, 2025

    Chao-Kai Chiang, Takashi Ishida, and Masashi Sugiyama. Llm routing with dueling feedback.arXiv preprint arXiv:2510.00841, 2025

    arXiv 2025

  15. [15]

    Contextual bandits with linear payoff functions

    Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011

    2011

  16. [16]

    Cost-effective online multi-llm selection with versatile reward models.arXiv preprint arXiv:2405.16587, 2024

    Xiangxiang Dai, Jin Li, Xutong Liu, Anqi Yu, and John Lui. Cost-effective online multi-llm selection with versatile reward models.arXiv preprint arXiv:2405.16587, 2024

    Pith/arXiv arXiv 2024

  17. [17]

    Adaptive hedge.Advances in Neural Information Processing Systems, 24, 2011

    Tim Erven, Wouter M Koolen, Steven Rooij, and Peter Grünwald. Adaptive hedge.Advances in Neural Information Processing Systems, 24, 2011

    2011

  18. [18]

    Graphrouter: A graph-based router for llm selections.arXiv preprint arXiv:2410.03834, 2024

    Tao Feng, Yanzhen Shen, and Jiaxuan You. Graphrouter: A graph-based router for llm selections.arXiv preprint arXiv:2410.03834, 2024

    Pith/arXiv arXiv 2024

  19. [19]

    Beyond ucb: Optimal and efficient contextual bandits with regression oracles

    Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. InInternational conference on machine learning, pages 3199–3210. PMLR, 2020

    2020

  20. [20]

    The statistical complexity of interactive decision making.arXiv preprint arXiv:2112.13487, 2021

    Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making.arXiv preprint arXiv:2112.13487, 2021

    Pith/arXiv arXiv 2021

  21. [21]

    Openllmleaderboard v2.https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard, 2024

    ClémentineFourrier, NathanHabib, AlinaLozovskaya, KonradSzafer, andThomasWolf. Openllmleaderboard v2.https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard, 2024

    2024

  22. [22]

    A decision-theoretic generalization of on-line learning and an application to boosting.Journal of computer and system sciences, 55(1):119–139, 1997

    Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting.Journal of computer and system sciences, 55(1):119–139, 1997

    1997

  23. [23]

    Gemini 1.5 pro model overview.https://ai.google.dev/gemini-api/docs/models/gemini,

    Google AI. Gemini 1.5 pro model overview.https://ai.google.dev/gemini-api/docs/models/gemini,

  24. [24]

    Accessed: 2025-05-10

    2025

  25. [25]

    Deberta: Decoding-enhanced bert with disentangled attention

    Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. InInternational Conference on Learning Representations, 2021

    2021

  26. [26]

    Routerbench: A benchmark for multi-llm routing system, 2024

    Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang, Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shriyash Kaustubh Upadhyay. Routerbench: A benchmark for multi-llm routing system, 2024

    2024

  27. [27]

    Thriftllm: On cost-effective selection of large language models for classification queries, 2025

    Keke Huang, Yimin Shi, Dujian Ding, Yifei Li, Yang Fei, Laks Lakshmanan, and Xiaokui Xiao. Thriftllm: On cost-effective selection of large language models for classification queries, 2025

    2025

  28. [28]

    all-MiniLM-L6-v2: Sentence transformer embedding model

    Hugging Face. all-MiniLM-L6-v2: Sentence transformer embedding model. https://huggingface.co/ sentence-transformers/all-MiniLM-L6-v2, 2025. Accessed: 2026-02-15

    2025

  29. [29]

    Hugging face models.https://huggingface.co/models, 2025

    Hugging Face. Hugging face models.https://huggingface.co/models, 2025. Accessed: 2025-05-10

    2025

  30. [30]

    Multi-armed bandits with machine learning-generated surrogate rewards.arXiv preprint arXiv:2506.16658, 2025

    Wenlong Ji, Yihan Pan, Ruihao Zhu, and Lihua Lei. Multi-armed bandits with machine learning-generated surrogate rewards.arXiv preprint arXiv:2506.16658, 2025

    Pith/arXiv arXiv 2025

  31. [31]

    Llm-blender: Ensembling large language models with pairwise ranking and generative fusion, 2023

    Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. Llm-blender: Ensembling large language models with pairwise ranking and generative fusion, 2023. 14

    2023

  32. [32]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesvári.Bandit algorithms. Cambridge University Press, 2020

    2020

  33. [33]

    A contextual-bandit approach to personalized news article recommendation

    Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. InProceedings of the 19th international conference on World wide web, pages 661–670, 2010

    2010

  34. [34]

    Llm bandit: Cost-efficient llm generation via preference-conditioned dynamic routing, 2025

    Yang Li. Llm bandit: Cost-efficient llm generation via preference-conditioned dynamic routing, 2025

    2025

  35. [35]

    From bandits to experts: On the value of side-observations.Advances in Neural Information Processing Systems, 24, 2011

    Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations.Advances in Neural Information Processing Systems, 24, 2011

    2011

  36. [36]

    Efficient and robust algorithms for adversarial linear contextual bandits

    Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. InConference on Learning Theory, pages 3049–3068. PMLR, 2020

    2020

  37. [37]

    Nguyen, Thinh Dao, Duy C

    Quang H. Nguyen, Thinh Dao, Duy C. Hoang, Juliette Decugis, Saurav Manchanda, Nitesh V. Chawla, and Khoa D. Doan. Metallm: A high-performant and cost-efficient dynamic framework for wrapping llms, 2025

    2025

  38. [38]

    Routellm: Learning to route llms from preference data

    Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, M Waleed Kadous, and Ion Stoica. Routellm: Learning to route llms from preference data. InThe Thirteenth International Conference on Learning Representations, 2025

    2025

  39. [39]

    Chatgpt.https://chat.openai.com/chat, 2025

    OpenAI. Chatgpt.https://chat.openai.com/chat, 2025. Accessed: 2025-05-10

    2025

  40. [40]

    Cambridge university press, 2014

    Shai Shalev-Shwartz and Shai Ben-David.Understanding machine learning: From theory to algorithms. Cambridge university press, 2014

    2014

  41. [41]

    Improving predictive inference under covariate shift by weighting the log-likelihood function.Journal of statistical planning and inference, 90(2):227–244, 2000

    Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function.Journal of statistical planning and inference, 90(2):227–244, 2000

    2000

  42. [42]

    Carrot: A cost aware rate optimal router.arXiv preprint arXiv:2502.03261, 2025

    Seamus Somerstep, Felipe Maia Polo, Allysson Flavio Melo de Oliveira, Prattyush Mangal, Mírian Silva, Onkar Bhardwaj, Mikhail Yurochkin, and Subha Maity. Carrot: A cost aware rate optimal router.arXiv preprint arXiv:2502.03261, 2025

    Pith/arXiv arXiv 2025

  43. [43]

    Tensoropera router: A multi-model router for efficient llm inference, 2024

    Dimitris Stripelis, Zijian Hu, Jipeng Zhang, Zhaozhuo Xu, Alay Dilipbhai Shah, Han Jin, Yuhang Yao, Salman Avestimehr, and Chaoyang He. Tensoropera router: A multi-model router for efficient llm inference, 2024

    2024

  44. [44]

    MIT press, 2012

    Masashi Sugiyama and Motoaki Kawanabe.Machine learning in non-stationary environments: Introduction to covariate shift adaptation. MIT press, 2012

    2012

  45. [45]

    Finite-time analysis of kernelised contextual bandits.arXiv preprint arXiv:1309.6869, 2013

    Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits.arXiv preprint arXiv:1309.6869, 2013

    Pith/arXiv arXiv 2013

  46. [46]

    Springer science & business media, 2013

    Vladimir Vapnik.The nature of statistical learning theory. Springer science & business media, 2013

    2013

  47. [47]

    Exploiting correlated auxiliary feedback in parameterized bandits.Advances in Neural Information Processing Systems, 36:4430–4451, 2023

    Arun Verma, Zhongxiang Dai, Yao Shu, and Bryan Kian Hsiang Low. Exploiting correlated auxiliary feedback in parameterized bandits.Advances in Neural Information Processing Systems, 36:4430–4451, 2023

    2023

  48. [48]

    Competitive on-line linear regression.Advances in Neural Information Processing Systems, 10, 1997

    Volodya Vovk. Competitive on-line linear regression.Advances in Neural Information Processing Systems, 10, 1997

    1997

  49. [49]

    Mixllm: Dynamic routing in mixed large language models, 2025

    Xinyuan Wang, Yanchi Liu, Wei Cheng, Xujiang Zhao, Zhengzhang Chen, Wenchao Yu, Yanjie Fu, and Haifeng Chen. Mixllm: Dynamic routing in mixed large language models, 2025

    2025

  50. [50]

    A lower bound on the stability number of a simple graph, 1981

    Victor K Wei. A lower bound on the stability number of a simple graph, 1981

    1981

  51. [51]

    Learning to route llms from bandit feedback: One policy, many trade-offs.arXiv preprint arXiv:2510.07429, 2025

    Wang Wei, Tiankai Yang, Hongjie Chen, Yue Zhao, Franck Dernoncourt, Ryan A Rossi, and Hoda Eldardiry. Learning to route llms from bandit feedback: One policy, many trade-offs.arXiv preprint arXiv:2510.07429, 2025. 15

    arXiv 2025

  52. [52]

    Open release of grok-1.https://x.ai/blog/grok-os, 2024

    xAI. Open release of grok-1.https://x.ai/blog/grok-os, 2024. Accessed: 2025-05-10

    2024

  53. [53]

    Contextual linear bandits with delay as payoff, 2025

    Mengxiao Zhang, Yingfei Wang, and Haipeng Luo. Contextual linear bandits with delay as payoff, 2025

    2025

  54. [54]

    Efficient contextual bandits with uninformed feedback graphs.arXiv preprint arXiv:2402.08127, 2024

    Mengxiao Zhang, Yuheng Zhang, Haipeng Luo, and Paul Mineiro. Efficient contextual bandits with uninformed feedback graphs.arXiv preprint arXiv:2402.08127, 2024

    Pith/arXiv arXiv 2024

  55. [55]

    Practical contextual bandits with feedback graphs.Advances in Neural Information Processing Systems, 36:30592–30617, 2023

    Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical contextual bandits with feedback graphs.Advances in Neural Information Processing Systems, 36:30592–30617, 2023

    2023

  56. [56]

    Morley Mao

    Zesen Zhao, Shuowei Jin, and Z. Morley Mao. Eagle: Efficient training-free router for multi-llm inference, 2024

    2024

  57. [57]

    trilemma

    Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International conference on machine learning, pages 11492–11502. PMLR, 2020. 16 Appendix The appendix is organized as follows, •In Appendix A we discuss additional related works •In Appendix B we expand on the baselines that are used in our experiments. •In ...

    arXiv 2020

  58. [58]

    In particular for the linear case, we geteO q dKTlog T d

    Baseline: Contextual BanditIn Subsection F.1, we first present a classical contextual bandit with regret bound eO q KTReg Sq(T) . In particular for the linear case, we geteO q dKTlog T d

  59. [59]

    When feedback graphGt has independence number no greater thanα, the regret satisfies eO q αTReg Sq(T) +ε n √ αKT

    Correlation-Aware Bandits with Surrogates — Coupled (CABS-C).We next analyze our proposed graph-feedback algorithm with noisy surrogate rewards in Subsection F.2. When feedback graphGt has independence number no greater thanα, the regret satisfies eO q αTReg Sq(T) +ε n √ αKT . In particular, for the linear case, when exactlym surrogate rewards are observe...

  60. [60]

    We state the modified algorithm that works on rewards instead of losses in Algorithm 3

    Correlation-Aware Bandits with Surrogates — Decoupled (CABS-D)Finally, in Subsection F.3 we establish the regret bound for the proposed prediction-mixing algorithm, a meta-bandit algorithm with two arms ((1) and (2) above) with regret bounded by min of them, eO min nq KTReg Sq(T), q αTReg Sq(T) +ε n √ αKT o For the linear case, when exactlymsurrogate rewa...

  61. [61]

    Lower Bound:By the Caro-Wei Theorem [9, 49], for any graph with vertex degreesd(k), the independence number is bounded by: α(Gt)≥ X k∈V 1 d(k) + 1 = KX k=1 1 m+ 1 = K m+ 1 (11)

  62. [62]

    Upper Bound:An independent set can contain at most one vertex from any clique. SinceV is partitioned into exactly K m+1 disjoint cliques, the size of the maximum independent set is bounded by the number of cliques: α(Gt)≤ K m+ 1 (12) Combining inequalities in Equations 11 and 12, we conclude thatα(Gt) = K m+1. Deriving Corollary 4.8.Corollary 4.8 follows ...

  63. [63]

    We proceed similarly forˆℓt,(2,g) (graph experts)

    (Optimistic Bias) For every meta expert(m, g)in roundtand conditioned onF t−1, we have E h ˆℓt,(m,g) | F t−1 i ≤ X i pt,m,iℓt,i Proof.We begin by showing this is true forˆℓt,(1,g) (bandit experts): E h ˆℓt,(1,g) | F t−1 i = X i qt,i qt,i +γ (g) pt,m,i ℓt,i ≤ X i pt,1,iℓt,i. We proceed similarly forˆℓt,(2,g) (graph experts). We begin by rewriting the estim...

  64. [64]

    (Uniform Bound) For every meta expert(m, g)in roundt, we may bound the value ofˆℓt,(m,g) as ˆℓt,(m,g) ≤ 1 γ(g) Proof.For both ˆℓt,(1,g) and ˆℓt,(2,g), the numerators are at most1and denominators are at leastγ(g)

  65. [65]

    TX t=1 2X m=1 LX g=1 µt,(m,g) ˆℓt,(m,g) # −E   min m∈{1,2} g∈[L] TX s=1 ˆℓt,(m,g)   ≤E lnM ηT +E

    (Second Moment Bounds) For every bandit meta expert(1, g)in round t and conditioned onFt−1, we may say E h ˆℓ2 t,(1,g) | F t−1 i ≤ KX i=1 pt,1,i qt,i +γ (g) . Likewise, for every graph meta expert(2, g)in roundtand conditioned onF t−1, we may say E h ˆℓ2 t,(2,g) | F t−1 i ≤ KX i=1 pt,2,iP j:At,(j,i)=1 qt,j +γ (g) 36 Proof.We begin by showing this is true ...