Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing

# Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing
Source: [https://arxiv.org/html/2607.09015](https://arxiv.org/html/2607.09015)
Ajay Narayanan Sridhar, Ronak Singh, Mehrdad Mahdavi, Vijaykrishnan Narayanan The Pennsylvania State University \{afs6372,rjs7006,mzm616,vxn9\}@psu\.edu

###### 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\.

## 1Introduction

The rapid proliferation of Large Language Models \(LLMs\) has made it increasingly challenging for end\-users to keep track of advancements and optimally select models for their specific needs\. Presently, numerous proprietary LLM providers exist\[[38](https://arxiv.org/html/2607.09015#bib.bib22),[23](https://arxiv.org/html/2607.09015#bib.bib23),[51](https://arxiv.org/html/2607.09015#bib.bib24)\], and thousands more are openly available through repositories such as Hugging Face\[[28](https://arxiv.org/html/2607.09015#bib.bib21)\]\. This abundance creates a practical systems problem: for a given query, which model should be called? The answer is rarely the most accurate model, since inference incurs nontrivial cost \(e\.g\., pricing, latency, compute\)\. In many applications, the objective is an*accuracy–cost trade\-off*: a slightly less accurate model may be preferable if it is significantly cheaper or faster, and the optimal choice varies with context\.

Existing unified interfaces address this challenge through model cascading\[[11](https://arxiv.org/html/2607.09015#bib.bib25),[26](https://arxiv.org/html/2607.09015#bib.bib26)\], ensembling\[[30](https://arxiv.org/html/2607.09015#bib.bib28)\], and routing\[[36](https://arxiv.org/html/2607.09015#bib.bib10),[37](https://arxiv.org/html/2607.09015#bib.bib20),[55](https://arxiv.org/html/2607.09015#bib.bib27),[42](https://arxiv.org/html/2607.09015#bib.bib29),[33](https://arxiv.org/html/2607.09015#bib.bib30)\]\. We focus on routing: selecting one model per query to maximize user\-defined utility\. A common reduction models LLM routing as a*contextual multi\-armed bandit*, where each LLM is treated as a conditionally independent arm given the incoming query context, and only the selected arm’s reward is observed, requiring costly exploration\. In thedd\-dimensional linear setting, where the context is represented by add\-dimensional embedding and each arm’s expected reward is assumed to be a linear function of this embedding, standard methods achieve regretRS=O​\(d​K​T​log⁡\(T/d\)\)R\_\{S\}=~O\(\\sqrt\{dKT\\log\(T/d\)\}\)\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]givenKKarms \(LLMs\) forTTstream of queries, where regret is the cumulative loss relative to the best context\-dependent action\. However, this conditional\-independence abstraction is often too coarse: models exhibit query\-dependent correlations due to shared pretraining data, alignment pipelines, and architectures\. Exploiting such correlations can reduce uncertainty about unplayed arms and lower the effective exploration burden\.

LLM routing also provides a source of side information largely absent from standard bandit settings: offline performance data\. Benchmarks or historical logs can train machine learning \(ML\) predictors that map query contexts to per\-arm reward estimates\. During online routing, these estimates can serve as*surrogate rewards*for unplayed arms\. Although surrogate rewards may be biased or noisy, they can still reveal relative arm quality\. The key challenge is to exploit surrogate rewards when helpful without over\-trusting them when misspecified\. This motivates our central research question:

> *Can we design contextual bandit algorithms that systematically exploit both context\-dependent inter\-model correlations and auxiliary ML\-predicted surrogate rewards to accelerate learning, while remaining robust to surrogate misspecification?*

To address this question, we study contextual bandits with*correlation\-aware*graph feedback and auxiliary*surrogate rewards*\. Each round, the learner observes the query context and context\-dependent side information about inter\-arm relationships, which are used to form a feedback graph that identifies a small set of additional arms whose feedback is most informative given the chosen arm\. After selecting an arm and observing its realized reward, the learner additionally receives ML\-predicted surrogate rewards for the arms in this graph\-selected set, providing partial multi\-arm side information beyond the chosen arm\. We first propose a coupled*reward\-mixing*approach,Correlation\-Aware Bandits with Surrogates Coupled\(CABS\-C\), which builds on graph\-feedback variants of SquareCB\[[54](https://arxiv.org/html/2607.09015#bib.bib11),[53](https://arxiv.org/html/2607.09015#bib.bib45)\]by pooling de\-biased true rewards with surrogate rewards to fit a single contextual model\. This coupling effectively increases the number of informative observations per round, improving the exploration factor fromKKtoK/\(m\+1\)K/\(m\+1\), wheremmis the number of additional arms for which surrogate rewards are revealed each round\. The price of coupling these observations is an added sensitivity to surrogate error\. For linear bandits, we show the regret scales asRC=O~​\(d​K​T​log⁡\(T/d\)/\(m\+1\)\+εn​T​K2/\(m\+1\)\)R\_\{C\}=\\widetilde\{O\}\\\!\\left\(\\sqrt\{dKT\\log\(T/d\)/\(m\+1\)\}\+\\varepsilon\_\{n\}\\sqrt\{TK^\{2\}/\(m\+1\)\}\\right\), whereεn\\varepsilon\_\{n\}quantifies the worst\-case magnitude of surrogate noise/misspecification \(see Assumption[4\.4](https://arxiv.org/html/2607.09015#S4.Thmtheorem4)\)\. The preceding regret bound makes the trade\-off explicit: accurate surrogates reduce the effective exploration burden, while large surrogate error can dominate and make tight coupling brittle\.

Motivated by this robustness issue, we propose a decoupled*prediction\-mixing*strategy,Correlation\-Aware Bandits with Surrogates Decoupled\(CABS\-D\), that treats \(i\) a reward\-only contextual bandit; and \(ii\) a correlation\-aware \(surrogates induced graph feedback\) bandit \(CABS\-C\) as two experts and combines them using an adaptive expert\-aggregation master, in the spirit of adaptive Hedge methods\[[1](https://arxiv.org/html/2607.09015#bib.bib87),[17](https://arxiv.org/html/2607.09015#bib.bib84)\]\. The resulting meta\-bandit promises a best\-of\-both\-worlds guarantee,RD=O​\(min⁡\{RS,RC\}\)R\_\{D\}=O\\\!\\left\(\\min\\left\\\{R\_\{S\},R\_\{C\}\\right\\\}\\right\), allowing us to match the standard contextual bandit rate \(plus mild overhead\) in the worst case while inheriting correlation\-driven gains when surrogate feedback is reliable\. We evaluate our LLM routing approaches, observing improved sample efficiency and better accuracy–cost trade\-offs compared to online bandit and static baselines\.

##### Contributions

In summary, our contributions are:

- •We introduce*correlation\-aware contextual bandits with surrogate rewards*, where context\-dependent inter\-arm relationship signals induce a graph\-feedback structure and an auxiliary predictor provides surrogate rewards for graph\-specified arms beyond the true reward observed for the chosen arm\.
- •We propose CABS\-C \(coupled*reward mixing*\) and CABS\-D \(decoupled*prediction mixing*\), clarifying when tight coupling is beneficial and when decoupling is necessary for robustness\.
- •We establish regret bounds that explicitly separate correlation\-driven gains \(reduced effective exploration\) from surrogate noise/misspecification, including a best\-of\-both\-worlds guarantee for CABS\-D that matches standard contextual bandits in the worst case, while simultaneously achieving an improved regret that scales inversely with the number of surrogate rewards under mild conditions\.
- •We evaluate our methods on LLM routing benchmarks and demonstrate improved sample efficiency and stronger accuracy–cost trade\-offs relative to online bandit baselines and static routing policies\.

Ultimately, these results demonstrate that leveraging predicted surrogate rewards offers a powerful framework for LLM routing, yielding substantial regret reductions\. Specifically, our approach effectively interpolates between the full\-information and bandit settings, with the performance gains smoothly scaling based on the quality of the surrogate rewards and correlation among LLMs\. This finding may be of independent interest beyond the specific setting considered here\.

## 2Related Work

In this section, we discuss the works most directly related to our approach and highlight the key distinctions from our method\. A more comprehensive overview of the multi\-armed bandit and LLM routing literature, including detailed comparisons of regret bounds and theoretical guarantees, is deferred to Appendix[A](https://arxiv.org/html/2607.09015#A1)\.

##### Contextual Bandits, Graph Feedback, and Expert Aggregation\.

Our work builds on contextual bandits such as SquareCB\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\], LinearUCB\[[15](https://arxiv.org/html/2607.09015#bib.bib17)\], and NeuralUCB\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\], and is closest to contextual bandits with graph feedback\[[53](https://arxiv.org/html/2607.09015#bib.bib45),[54](https://arxiv.org/html/2607.09015#bib.bib11)\]\. Unlike SquareCB\-G\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\], which observes*true*rewards for graph neighbors, and SquareCB\-UG\[[53](https://arxiv.org/html/2607.09015#bib.bib45)\], which learns an unknown graph after action selection, we observe true reward only for the selected arm and receive*surrogate*rewards from a context\-dependent graph known before action selection\. CABS\-D is related to Hedge/AdaHedge\-style expert aggregation\[[22](https://arxiv.org/html/2607.09015#bib.bib85),[17](https://arxiv.org/html/2607.09015#bib.bib84)\]and Corral\-style bandit masters\[[1](https://arxiv.org/html/2607.09015#bib.bib87)\], but adapts specifically between standard bandit feedback and surrogate graph feedback\. Auxiliary\-feedback methods\[[13](https://arxiv.org/html/2607.09015#bib.bib76),[46](https://arxiv.org/html/2607.09015#bib.bib77),[29](https://arxiv.org/html/2607.09015#bib.bib78)\]use external signals mainly to improve estimates for the*played*arm, whereas we propagate surrogate feedback across multiple arms\. See\[[31](https://arxiv.org/html/2607.09015#bib.bib2)\]and Appendix[A](https://arxiv.org/html/2607.09015#A1)for a broader overview\.

##### LLM routing\.

LLM routing selects a model for each query under quality, cost, or latency constraints\. Prior work includes offline routers trained from preference or performance data\[[37](https://arxiv.org/html/2607.09015#bib.bib20),[55](https://arxiv.org/html/2607.09015#bib.bib27),[42](https://arxiv.org/html/2607.09015#bib.bib29),[12](https://arxiv.org/html/2607.09015#bib.bib15),[18](https://arxiv.org/html/2607.09015#bib.bib71),[41](https://arxiv.org/html/2607.09015#bib.bib48)\], benchmarks for cost–performance routing\[[25](https://arxiv.org/html/2607.09015#bib.bib16),[41](https://arxiv.org/html/2607.09015#bib.bib48)\], and online routing methods based on contextual bandits or dueling bandits\[[36](https://arxiv.org/html/2607.09015#bib.bib10),[33](https://arxiv.org/html/2607.09015#bib.bib30),[48](https://arxiv.org/html/2607.09015#bib.bib31),[50](https://arxiv.org/html/2607.09015#bib.bib69),[16](https://arxiv.org/html/2607.09015#bib.bib70),[14](https://arxiv.org/html/2607.09015#bib.bib1)\]\. Existing online routing strategies largely do not*explicitly*model intrinsic correlations among LLMs \(beyond implicit representation sharing\), which can limit sample\-efficiency when model behaviors are strongly related\. Addressing this gap, our correlation\-aware routing framework exploits context\-dependent inter\-arm relationships and integrates auxiliary surrogate signals while remaining robust to surrogate misspecification, yielding improved routing utility across cost regimes\.

![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/llm_routing_task.png)Figure 1:Overview of the LLM routing task and the proposed CABS\-C/CABS\-D online learning pipeline\. The router selects an LLM under cost sensitivity parameterρ\\rho, whileAO,RO, andRSdenote the affinity oracle, reward oracle, and regression solver used by the CABS\-C/CABS\-D algorithms\.

## 3Problem Setting

We consider an online LLM routing problem setting operating over a finite horizon ofTTdiscrete rounds, indexed byt∈\[T\]:=\{1,2,…,T\}t\\in\[T\]:=\\\{1,2,\\ldots,T\\\}\. The router \(learner\) has access to a fixed pool ofKKdistinct LLMs \(arms\), denoted by the set𝒦=\[K\]:=\{1,2,…,K\}\\mathcal\{K\}=\[K\]:=\\\{1,2,\\ldots,K\\\}\. At each roundt∈\[T\]t\\in\[T\], the learner observes a prompt and its context embedding vector𝒙t∈𝒳⊆ℝd\\bm\{x\}\_\{t\}\\in\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}, where𝒳\\mathcal\{X\}is a bounded context space, and must select an LLMit∈\[K\]i\_\{t\}\\in\[K\]to process the prompt\. The selected model,iti\_\{t\}, produces an outcome𝒐t\\bm\{o\}\_\{t\}and incurs a cost\-aware rewardrt,it​\(𝒙t\)r\_\{t,i\_\{t\}\}\(\\bm\{x\}\_\{t\}\); when convenient, we writert,itr\_\{t,i\_\{t\}\}and define the corresponding lossℓt,it=1−rt,it\\ell\_\{t,i\_\{t\}\}=1\-r\_\{t,i\_\{t\}\}\. The reward typically captures generation quality \(e\.g\., accuracy, helpfulness\) and trades off it against operational constraints \(e\.g\., latency, token cost\)\. We explicitly bound the reward and loss to the\[0,1\]\[0,1\]interval, which is standard and necessary for regret analysis\. Figure[1](https://arxiv.org/html/2607.09015#S2.F1)provides an overview of this LLM routing task and the proposed CABS\-C/CABS\-D online learning pipeline\.

To exploit query\-dependent correlations among LLMs and auxiliary reward predictions from offline data, we formulate LLM routing as a correlation\-aware contextual bandit with surrogate rewards\. At each roundtt, in addition to𝒙t\\bm\{x\}\_\{t\}, the learner observes inter\-arm side information from an affinity oracle \(AO\), represented either as a correlation matrix𝑹t∈ℝK×K\\bm\{R\}\_\{t\}\\in\\mathbb\{R\}^\{K\\times K\}or as a time\-varying, context\-dependent directed feedback graphGtG\_\{t\}over\[K\]\[K\]with adjacency matrix𝑨t∈\{0,1\}K×K\\bm\{A\}\_\{t\}\\in\\\{0,1\\\}^\{K\\times K\}, whereAt,\(i,j\)=1A\_\{t,\(i,j\)\}=1indicates an edge from armiito armjj\. By default,At,\(i,i\)=1A\_\{t,\(i,i\)\}=1for alli∈\[K\]i\\in\[K\]\. The side information among LLMs quantifies how performance scales across different models for a specific context\.

Upon selecting armiti\_\{t\}, the learner observes the true realized reward only for the chosen armiti\_\{t\}\. However, for other armsj≠itj\\neq i\_\{t\}specified by the feedback graph, the learner receives surrogate rewardsst,js\_\{t,j\}from a reward oracle \(RO\)\. The surrogate rewards predicted by theROact as a proxy estimate derived from offline data or cross\-model evaluation functions\. The conditional bias or variance of the surrogate rewardst,js\_\{t,j\}relative to the true underlying rewardrt,jr\_\{t,j\}is assumed to be bounded\.

Similar to\[[20](https://arxiv.org/html/2607.09015#bib.bib4),[54](https://arxiv.org/html/2607.09015#bib.bib11)\], we assume that the learner has access to a regression solver \(RS\) that is invoked at each roundttto update arm models from historical input–output data\. The𝖱𝖲\\mathsf\{RS\}serves as an abstract optimization primitive that handles the algorithmic complexity of empirical risk minimization and can efficiently compute a predictor from a predefined function classℱ\\mathcal\{F\}\(such as linear models or deep neural networks\)\. Formally, given a sequence of context\-dependent importance weightswτ,j≥0w\_\{\\tau,j\}\\geq 0, the𝖱𝖲\\mathsf\{RS\}processes the accumulated feedback history up to the previous round to solve a weighted empirical risk minimization problem for each armi∈\[K\]i\\in\[K\]to update its model:

f^t,i=arg⁡minf∈ℱ​∑τ=1t−1wτ,i​\(f​\(𝒙τ,i\)−r^τ,i\)2\+ℛ​\(f\)\\hat\{f\}\_\{t,i\}=\\arg\\min\_\{f\\in\\mathcal\{F\}\}\\sum\_\{\\tau=1\}^\{t\-1\}w\_\{\\tau,i\}\\left\(f\(\\bm\{x\}\_\{\\tau\},i\)\-\\hat\{r\}\_\{\\tau,i\}\\right\)^\{2\}\+\\mathcal\{R\}\(f\)
wherer^τ,i\\hat\{r\}\_\{\\tau,i\}represents the importance\-weighted estimate at roundτ\\taucomputed based on true or surrogate rewards \(equal tor^τ,iτ=rτ,iτ/pτ,iτ\\hat\{r\}\_\{\\tau,i\_\{\\tau\}\}=r\_\{\\tau,i\_\{\\tau\}\}/p\_\{\\tau,i\_\{\\tau\}\}ifi=iτi=i\_\{\\tau\}, andr^τ,j=\(sτ,j−b^τ,j\)/\(𝑨τ,\(:,j\)⊤​𝒑t\)\\hat\{r\}\_\{\\tau,j\}=\(s\_\{\\tau,j\}\-\\hat\{b\}\_\{\\tau,j\}\)/\(\\bm\{A\}\_\{\\tau,\(:,j\)\}^\{\\top\}\\bm\{p\}\_\{t\}\)ifiiis revealed by the feedback graphGτG\_\{\\tau\}\), withrτ,iτr\_\{\\tau,i\_\{\\tau\}\}being the true observed reward,sτ,is\_\{\\tau,i\}being the proxy surrogate reward with estimated biasb^τ,j\\hat\{b\}\_\{\\tau,j\}, andpτ,iτp\_\{\\tau,i\_\{\\tau\}\}being the probability of selecting armiiat roundτ\\tau\. Here,ℛ​\(f\)\\mathcal\{R\}\(f\)is an optional regularization term \(e\.g\.,ℓ2\\ell\_\{2\}penalty\) used to prevent overfitting in high\-dimensional context spaces\. The learner’s objective is to minimize the cumulative regret overTTrounds\. The optimal arm at roundttis defined as the arm that maximizes the true reward for the given context:it⋆=arg⁡maxi∈\[K\]⁡𝔼​\[rt,i​\(𝒙t\)\]i\_\{t\}^\{\\star\}=\\arg\\max\_\{i\\in\[K\]\}\\mathbb\{E\}\\left\[r\_\{t,i\}\(\\bm\{x\}\_\{t\}\)\\right\]\. The cumulative regretReg​\(T\)\\mathrm\{Reg\}\(T\)is given byReg​\(T\)=∑t=1T𝔼​\[rt,it⋆​\(𝒙t\)\]−𝔼​\[rt,it​\(𝒙t\)\]\\mathrm\{Reg\}\(T\)=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[r\_\{t,i\_\{t\}^\{\\star\}\}\(\\bm\{x\}\_\{t\}\)\\right\]\-\\mathbb\{E\}\\left\[r\_\{t,i\_\{t\}\}\(\\bm\{x\}\_\{t\}\)\\right\], which we use to measure the performance of online routing algorithm\.

## 4The Proposed Algorithms

In this section, we propose two algorithms for contextual bandits with surrogate rewards and correlated arms\. We first introduce a reward\-mixing method, CABS\-C, that learns from both true rewards and de\-biased surrogate feedback\. We then introduce a prediction\-mixing method, CABS\-D, that dynamically integrates predictions from CABS\-C with those from a standard bandit\-feedback method \(SquareCB\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]or LinUCB\[[32](https://arxiv.org/html/2607.09015#bib.bib34)\]\) to achieve best\-of\-both\-worlds regret guarantees\.

Algorithm 1Correlation\-Aware Bandits with Surrogates Coupled \(CABS\-C\)1:Input:Number of rounds

TT, regularization parameter

γ\\gamma\.

2:Oracles:Reward oracle

RO:𝒳×\[K\]×ℝ\+→ℝ\+K\\text\{\{RO\}\}:\\mathcal\{X\}\\times\[K\]\\times\\mathbb\{R\}\_\{\+\}\\rightarrow\\mathbb\{R\}\_\{\+\}^\{K\}, affinity oracle

AO:𝒳→ℝK×K\\text\{\{AO\}\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}^\{K\\times K\}, regression solver

RS:𝒳→ℝK×d\\text\{\{RS\}\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}^\{K\\times d\}
3:Initialize:

n0,i=0n\_\{0,i\}=0and

b^0,j=0\\hat\{b\}\_\{0,j\}=0for all

i∈\[K\]i\\in\[K\]
4:for

t=1t=1to

TTdo

5:Receive context

𝒙t\\bm\{x\}\_\{t\}and corresponding correlation matrix

𝑹t\\bm\{R\}\_\{t\}from

AO​\(𝒙t\)\\text\{\{AO\}\}\(\\bm\{x\}\_\{t\}\)\.

6:Generate affinity graph

GtG\_\{t\}with adjacency matrix

𝑨t\\bm\{A\}\_\{t\}:

At,\(i,j\)=1A\_\{t,\(i,j\)\}=1w\.p\.

σ​\(\(1−Rt,\(i,j\)\)/2\)\\sigma\(\(1\-R\_\{t,\(i,j\)\}\)/2\)
7:Obtain an estimator

𝜽^t,i:ℝd\\hat\{\\bm\{\\theta\}\}\_\{t,i\}:\\mathbb\{R\}^\{d\}for all

i∈\[K\]i\\in\[K\]from

RS​\(𝒙t\)\\text\{\{RS\}\}\(\\bm\{x\}\_\{t\}\)
8:Set

𝒑t=arg​min𝒑∈Δ​\(\[K\]\)⁡ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\\bm\{p\}\_\{t\}=\\operatorname\*\{arg\\,min\}\_\{\\bm\{p\}\\in\\Delta\(\[K\]\)\}\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\), where

ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)is defined as follows,

:=supi∗∈\[K\]𝜽∗∈ℝK×d𝔼i∼𝒑​\[𝒙t⊤​𝜽i∗∗−𝒙t⊤​𝜽i∗−γ4​∑k:At,\(i,k\)=1𝔼​\[At,\(i,k\)\]​\(𝒙t⊤​𝜽k∗−𝒙t⊤​𝜽^t,k\)2\]\\displaystyle:=\\sup\_\{\\begin\{subarray\}\{c\}i^\{\*\}\\in\[K\]\\\\ \\bm\{\\theta\}^\{\*\}\\in\\mathbb\{R\}^\{K\\times d\}\\end\{subarray\}\}\\hskip 5\.0pt\\mathbb\{E\}\_\{i\\sim\\bm\{p\}\}\\left\[\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i^\{\*\}\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\-\\frac\{\\gamma\}\{4\}\\sum\_\{k:A\_\{t,\(i,k\)\}=1\}\\mathbb\{E\}\[A\_\{t,\(i,k\)\}\]\(\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{k\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,k\}\)^\{2\}\\right\]
9:Sample action

it∼𝒑ti\_\{t\}\\sim\\bm\{p\}\_\{t\}and receive true reward

rt,itr\_\{t,i\_\{t\}\}\.

10:Observe surrogate rewards

st,js\_\{t,j\}from

RO​\(𝒙t,it,rt,it\)\\text\{\{RO\}\}\(\\bm\{x\}\_\{t\},i\_\{t\},r\_\{t,i\_\{t\}\}\)for all

j∈𝒩t​\(it\)j\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\), where

𝒩t​\(it\)\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)is all arms in the neighborhood of arm

iti\_\{t\}\(including

iti\_\{t\}\) according to

GtG\_\{t\}
11:Construct de\-biased surrogate rewards

s~t,j=st,j−b^t,j\\tilde\{s\}\_\{t,j\}=s\_\{t,j\}\-\\hat\{b\}\_\{t,j\}for all

j∈𝒩t​\(it\)j\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)
12:Update the bias estimator for all

j∈𝒩t​\(it\)j\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)by setting

nt\+1,j←nt,j\+1n\_\{t\+1,j\}\\leftarrow n\_\{t,j\}\+1and

b^t\+1,j←\(1−1nt\+1,j\)​b^t,j\+1nt\+1,j​\(st,j−𝒙t⊤​𝜽^t,j\)\.\\hat\{b\}\_\{t\+1,j\}\\leftarrow\\left\(1\-\\frac\{1\}\{n\_\{t\+1,j\}\}\\right\)\\hat\{b\}\_\{t,j\}\+\\frac\{1\}\{n\_\{t\+1,j\}\}\\bigl\(s\_\{t,j\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,j\}\\bigr\)\.
13:Keep parameters the same for unobserved arms:

nt\+1,k=nt,k,b^t\+1,k=b^t,kn\_\{t\+1,k\}=n\_\{t,k\},\\hat\{b\}\_\{t\+1,k\}=\\hat\{b\}\_\{t,k\}for

k∉𝒩t​\(it\)k\\notin\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)\.

14:Set importance\-weighted estimate for chosen arm:

r^t,it=rt,it/pt,it\\hat\{r\}\_\{t,i\_\{t\}\}=r\_\{t,i\_\{t\}\}/p\_\{t,i\_\{t\}\}\.

15:Set importance\-weighted estimates for surrogates:

r^t,j=s~t,j/\(𝑨t,\(:,j\)⊤​𝒑t\)\\hat\{r\}\_\{t,j\}=\\tilde\{s\}\_\{t,j\}/\(\\bm\{A\}\_\{t,\(:,j\)\}^\{\\top\}\\bm\{p\}\_\{t\}\)∀j∈𝒩t​\(it\)∖\{it\}\.\\forall j\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)\\setminus\\\{i\_\{t\}\\\}\.
16:Feed the tuples

\{\(𝒙t,r^t,j\)\}j∈𝒩t​\(it\)\\\{\(\\bm\{x\}\_\{t\},\\hat\{r\}\_\{t,j\}\)\\\}\_\{j\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)\}to the oracleRS

17:endfor

### 4\.1A coupled algorithm with provable regret bound

We first propose*Correlation\-Aware Bandits with Surrogates Coupled*\(CABS\-C\), detailed in Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\. CABS\-C builds on graph\-feedback variants\[[54](https://arxiv.org/html/2607.09015#bib.bib11),[53](https://arxiv.org/html/2607.09015#bib.bib45)\]of SquareCB by using the feedback graph to guide exploration, but adapts this framework to the surrogate\-feedback setting\. Specifically, CABS\-C de\-biases surrogate rewards from correlated arms and pools them with the selected arm’s true reward to train a single reward model\. Each arm is modeled as a functionffwhich could be linearly parametrized by𝜽^i,i∈\[K\]\\hat\{\\bm\{\\theta\}\}\_\{i\},i\\in\[K\]or implemented as a neural net\. At roundtt, the algorithm observes context𝒙t\\bm\{x\}\_\{t\}and an affinity matrix𝑹t\\bm\{R\}\_\{t\}, samples a stochastic feedback graphGtG\_\{t\}with adjacency matrix𝑨t\\bm\{A\}\_\{t\}, and obtains reward estimates from the regression solverRS\. The action distribution𝒑t∈Δ​\(\[K\]\)\\bm\{p\}\_\{t\}\\in\\Delta\(\[K\]\), whereΔ​\(\[K\]\)\\Delta\(\[K\]\)is\(K−1\)\(K\-1\)\-dimensional simplex, is then computed by solving a optimization problem \(Line[8](https://arxiv.org/html/2607.09015#algx1.l8)\), which chooses an arm by balancing low immediate regret with high information gain from the feedback graph\. Unlike a standard contextual bandit rule, which only trades off reward and uncertainty for the selected arm, this step explicitly accounts for additional side observations revealed through graph neighbors; thus, it may select an arm that is slightly suboptimal in immediate reward if it yields more informative feedback overall\. The parameterγ\\gammacontrols this trade\-off\.

After sampling an armiti\_\{t\}according to𝒑t\\bm\{p\}\_\{t\}, the learner observes its true reward and receives surrogate rewards\{st,j\}\\\{s\_\{t,j\}\\\}for graph neighbors𝒩t​\(it\):=\{j∈\[K\]:At,\(it,j\)=1\}\\mathcal\{N\}\_\{t\}\(i\_\{t\}\):=\\\{j\\in\[K\]:A\_\{t,\(i\_\{t\},j\)\}=1\\\}, where eachst,j∈\[0,1\]s\_\{t,j\}\\in\[0,1\]is produced by the reward oracleRO\. CABS\-C then de\-biases the surrogate feedback, constructs importance\-weighted reward estimates, and updatesRS\. Thus, CABS\-C interpolates between bandit and full\-information learning by using context\-dependent graph structure to propagate imperfect surrogate feedback beyond the selected arm\. While graph\-based side observations and surrogate feedback have each been studied independently in prior work, CABS\-C jointly addresses both in a single correlation\-aware bandit framework\.

We now turn to establishing the regret bound for the algorithm\. Before, we state the assumptions in our setting below\.

###### Assumption 4\.1\(Realizability\)\.

Following\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\], we assume the expected*true rewards*are realizable, i\.e\. there existsf⋆∈ℱf^\{\\star\}\\in\\mathcal\{F\}such that,𝔼​\[rt,i∣𝒙t\]=f⋆​\(𝒙t,i\),∀t∈\[T\],i∈\[K\]\.\\mathbb\{E\}\[r\_\{t,i\}\\mid\\bm\{x\}\_\{t\}\]=f^\{\\star\}\(\\bm\{x\}\_\{t\},i\),\\;\\;\\forall t\\in\[T\],\\,i\\in\[K\]\.

When we work with losses, we use the conventionℓt,i=1−rt,i\\ell\_\{t,i\}=1\-r\_\{t,i\}, in which case the same realizability condition holds for losses as well \(up to an affine transformation of the function class\)\. In our work, we consider parametric function classes of the formfθ​\(𝒙,i\)f\_\{\\theta\}\(\\bm\{x\},i\), whereθ\\thetadenotes model parameters\. In the linear contextual bandit special case,fθ​\(𝒙,i\)=𝒙⊤​𝜽if\_\{\\theta\}\(\\bm\{x\},i\)=\\bm\{x\}^\{\\top\}\\bm\{\\theta\}\_\{i\}, whereas more generallyfθf\_\{\\theta\}may be a neural network or other nonlinear predictor\.

###### Assumption 4\.2\(Regression Oracle\)\.

Following\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\], we assume the regression oracleRSguarantees that for any sequence\{\(𝒙t,r^t,j\)\}j∈𝒪t,t∈\[T\]\\\{\(\\bm\{x\}\_\{t\},\\hat\{r\}\_\{t,j\}\)\\\}\_\{j\\in\\mathcal\{O\}\_\{t\},t\\in\[T\]\}in which𝒪t⊆\[K\]\\mathcal\{O\}\_\{t\}\\subseteq\[K\], the oracle produces a functionf^t\\hat\{f\}\_\{t\}such that∑t=1T∑i∈𝒪t\(f⋆​\(𝒙t,i\)−f^t​\(𝒙t,i\)\)2≤RegSq​\(T\)\\sum\_\{t=1\}^\{T\}\\sum\_\{i\\in\\mathcal\{O\}\_\{t\}\}\\big\(f^\{\\star\}\(\\bm\{x\}\_\{t\},i\)\-\\hat\{f\}\_\{t\}\(\\bm\{x\}\_\{t\},i\)\\big\)^\{2\}\\leq\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\.

Note that this assumption holds for any function class\. In our analysis, we stick to linear functions, i\.e,f^t​\(𝒙t,i\)=𝒙t⊤​𝜽^t,i\\hat\{f\}\_\{t\}\(\\bm\{x\}\_\{t\},i\)=\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}andf⋆​\(𝒙t,i\)=𝒙t⊤​𝜽i∗f^\{\\star\}\(\\bm\{x\}\_\{t\},i\)=\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\.

###### Assumption 4\.3\(Strong Observability\)\.

For a directed graphGt=\(\[K\],E\)G\_\{t\}=\(\[K\],E\), a nodeiiis observable if\{j∈\[K\];At,\(j,i\)=1\}≠∅\\\{j\\in\[K\];\\;\{A\}\_\{t,\(j,i\)\}=1\\\}\\neq\\emptyset\. An observable node,iiis strongly observable if eitheri∈\{j∈\[K\];At,\(j,i\)=1\}i\\in\\\{j\\in\[K\];\\;\{A\}\_\{t,\(j,i\)\}=1\\\}or\{j∈\[K\];At,\(j,i\)=1\}=\[K\]∖\{i\}\\\{j\\in\[K\];\\;\{A\}\_\{t,\(j,i\)\}=1\\\}=\[K\]\\setminus\\\{i\\\}\. If all nodesi∈\[K\]i\\in\[K\]are strongly observable, then the graphGtG\_\{t\}is strongly observable and has independence numberα\\alpha\.

Following\[[5](https://arxiv.org/html/2607.09015#bib.bib64)\], since we assume that pulling an arm always reveals its own loss, we satisfyi∈\{j∈\[K\];At,\(j,i\)=1\}i\\in\\\{j\\in\[K\];\\;\{A\}\_\{t,\(j,i\)\}=1\\\}, making the graph strongly observable\.

###### Assumption 4\.4\(ML Side Observation Model\)\.

For every observed armi∈𝒩t​\(it\)i\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\), the surrogate reward isst,i=f⋆​\(𝒙t,i\)\+bi\+ξt,is\_\{t,i\}=f^\{\\star\}\(\\bm\{x\}\_\{t\},i\)\+b\_\{i\}\+\\xi\_\{t,i\}, wherebi∈ℝb\_\{i\}\\in\\mathbb\{R\}is a fixed arm\-dependent bias andξt,i\\xi\_\{t,i\}is a zero\-mean noise term satisfying𝔼​\[ξt,i∣ℱt−1,𝒙t\]=0\\mathbb\{E\}\[\\xi\_\{t,i\}\\mid\\mathcal\{F\}\_\{t\-1\},\\bm\{x\}\_\{t\}\]=0and\|ξt,i\|≤εn\|\\xi\_\{t,i\}\|\\leq\\varepsilon\_\{n\}\.

Here filtrationℱt\\mathcal\{F\}\_\{t\}denotes the information available up to timett, andεn\\varepsilon\_\{n\}bounds the surrogate noise across rounds and observed arms\. Intuitively,bib\_\{i\}captures systematic surrogate over\- or under\-estimation for armii, while largerεn\\varepsilon\_\{n\}corresponds to noisier and less informative side observations\.

###### Assumption 4\.5\(Minimum Probability\)\.

Following\[[4](https://arxiv.org/html/2607.09015#bib.bib61)\], we make the assumption thatpt,i≥ϵp\_\{t,i\}\\geq\\epsilonfor all\(t,i\)\(t,i\), wherept,ip\_\{t,i\}indicates the probability of selecting armiiat roundtt\. This can be achieved by mixing𝒑t\\bm\{p\}\_\{t\}with a uniform mass\. Note that thisϵ\\epsilonis distinct from theεn\\varepsilon\_\{n\}quantity from Assumption[4\.4](https://arxiv.org/html/2607.09015#S4.Thmtheorem4)

Using the above assumptions, we introduce a lemma for concentrating the noise term of surrogate rewards, and then we introduce a theorem and accompanying corollary for bounding the expected regret of Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\. The proofs are deferred to Appendix[F\.2](https://arxiv.org/html/2607.09015#A6.SS2)\.

###### Lemma 4\.6\.

Suppose the feedback graphGtG\_\{t\}is deterministic with independence number no more thanα\\alpha\. Then, for allδ\>0\\delta\>0, with probability1−δ1\-\\deltaAlgorithm[1](https://arxiv.org/html/2607.09015#alg1)guarantees that

∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|≤εn​2​α​K​T​ln⁡\(2​K​Tδ\)​ln⁡\(4​Kα​ϵ\)​\(1\+ln⁡T\)\.\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|\\;\\leq\\;\\varepsilon\_\{n\}\\,\\sqrt\{2\\alpha KT\\ln\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\(1\+\\ln T\)\}\.\(1\)

###### Theorem 4\.7\.

Suppose that the feedback graphGtG\_\{t\}is strongly observable, and has independence number no greater thanα\\alpha\. Under Assumptions[4\.1](https://arxiv.org/html/2607.09015#S4.Thmtheorem1)–[4\.2](https://arxiv.org/html/2607.09015#S4.Thmtheorem2), with probability at least1−δ1\-\\delta, Algorithm[1](https://arxiv.org/html/2607.09015#alg1)guarantees that,𝔼​\[RegT\]≤O~​\(α​T​RegSq​\(T\)\+εn​α​K​T\)\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\,\\sqrt\{\\alpha KT\}\\ \\right\)\.

For anmm\-feedback graph, where each round revealsmmsurrogate rewards, Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7)yields the following linear\-oracle specialization\.

###### Corollary 4\.8\(Linear oracle withmm\-feedback\)\.

Assume that we have a linear oracle and we observe surrogate rewards formmarms per round\. Then with probability at least1−δ1\-\\deltaCABS\-C guarantees

𝔼​\[RegT\]≤O~​\(d​Km\+1​T​log⁡\(Td\)\+εn​K2m\+1​T\)\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{d\\frac\{K\}\{m\+1\}T\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\\;\+\\;\\varepsilon\_\{n\}\\sqrt\{\\frac\{K^\{2\}\}\{m\+1\}T\}\\right\)

Brief discussion of bias and noise\.If we ensure thatεn=O​\(1/K\)\\varepsilon\_\{n\}=O\(1/\\sqrt\{K\}\), we recover the same asymptotic regret \(up to polylogs\) as the standard contextual bandit with graph feedback setting,O~​\(α​T​RegSq​\(T\)\)\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\\right\)\. If the bias and noise are well\-behaved \(each arm’s respective biasbib\_\{i\}remains relatively constant or changes gradually and noise is small and truly subgaussian\), then CABS\-C can utilize surrogate rewards to significantly improve the rate of learning \(the additional information from the surrogate rewards reduces variance\)\. However, if bias is difficult to estimate or if the magnitude of the subgaussian noise is large, then the surrogate rewards available to CABS\-C may hinder its ability to learn \(inconsistent surrogate rewards can potentially increase variance\)\.

On boundingεn\\bm\{\\varepsilon\_\{n\}\}\.We note that the ML reward predictor \(RO\), trained offline from a fixed mixture of LLMs, enjoys standard ERM generalization guarantees only with respect to the training distribution\[[45](https://arxiv.org/html/2607.09015#bib.bib82),[39](https://arxiv.org/html/2607.09015#bib.bib81)\]\. Generalization to unseen contexts reduces to a covariate shift problem\[[40](https://arxiv.org/html/2607.09015#bib.bib80),[43](https://arxiv.org/html/2607.09015#bib.bib79)\], and fundamentally depends on support overlap or structural invariance assumptions on the underlying data\-generating process\. In the next section, we propose an algorithm that is robust to such noise, while retaining the aforementioned regret bound whenεn\\varepsilon\_\{n\}is small\.

Cost\-informed utility\.To capture the accuracy–cost trade\-off inherent in practical LLM deployment, we define a cost\-aware utility:rt,it=yt,it−ρ​ct,itr\_\{t,i\_\{t\}\}=y\_\{t,i\_\{t\}\}\-\\rho\\,c\_\{t,i\_\{t\}\}, whereyt,it∈\[0,1\]y\_\{t,i\_\{t\}\}\\in\[0,1\]denotes the accuracy score obtained by using LLMiti\_\{t\}to answer query𝒙t\\bm\{x\}\_\{t\}, andct,it≥0c\_\{t,i\_\{t\}\}\\geq 0is the associated inference cost\. The parameterρ≥0\\rho\\geq 0controls cost sensitivity: larger values favor cheaper models, while smaller values prioritize accuracy\. We additionally clip the utility to\[0,1\]\[0,1\]to enforce bounded rewards\.

From linear to neural bandits\.While we focus on linear models for clarity of exposition and analysis, our approach extends naturally to nonlinear reward models\. In particular, following the machinery \(Neural Tangent Kernel matrix analysis\) adapted in NeuralUCB\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\], the linear predictor𝒙t⊤​𝜽∗i\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta^\{\*\}\}\_\{i\}can be replaced by a neural network with uncertainty estimated via its last\-layer features\. At this point, we empirically adapt our method to neural bandits based estimators and show their performance in Section[5](https://arxiv.org/html/2607.09015#S5), but note that our regret analysis can be extend to this setting be utilizing the machinery developed in\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\]\.

### 4\.2A decoupled method with optimal regret

Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7)shows that surrogate rewards can substantially improve regret for CABS\-C algorithm, but can also degrade performance when their bias or noise is poorly controlled\. This is a consequence of*reward mixing*: CABS\-C combines true and surrogate rewards at the observation level and trains a single model on the pooled feedback\. To obtain robustness to unreliable surrogate rewards, we instead consider a*prediction\-mixing*strategy, where different feedback mechanisms are handled by separate learners and combined only at the decision level\.

We introduce*Correlation\-Aware Bandits with Surrogates Decoupled*\(CABS\-D\), shown in Algorithm[2](https://arxiv.org/html/2607.09015#alg2)\. CABS\-D maintains two stateful experts: a standard bandit\-feedback expert and the surrogate\-aware graph\-feedback expert CABS\-C from Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\. In our theoretical analysis, the standard expert is SquareCB, described in Appendix[F\.1](https://arxiv.org/html/2607.09015#A6.SS1)\. At each round, the experts output policies𝒑t,1\\bm\{p\}\_\{t,1\}and𝒑t,2\\bm\{p\}\_\{t,2\}, which are mixed into𝒒t\\bm\{q\}\_\{t\}using adaptive exponential weights over meta\-copies\(m,g\)\(m,g\), in the spirit of Hedge/AdaHedge\-style aggregation\[[17](https://arxiv.org/html/2607.09015#bib.bib84)\]\. After samplingit∼𝒒ti\_\{t\}\\sim\\bm\{q\}\_\{t\}, SquareCB receives only the selected arm’s true reward, while CABS\-C also receives surrogate rewards from the sampled feedback graph\. The meta\-weights are updated using importance\-weighted loss estimates and an adaptive second\-order learning rate, allowing CABS\-D to track the better feedback mechanism without knowing whether surrogates are reliable\. Thus, CABS\-D retains standard bandit robustness while exploiting informative surrogate feedback\. We now state its regret bound\.

Algorithm 2Correlation\-Aware Bandits with Surrogates Decoupled \(CABS\-D\)1:Input:

TTRounds; geometric grid

Γ=\{γ\(1\),…,γ\(L\)\}\\Gamma=\\\{\\gamma^\{\(1\)\},\\dots,\\gamma^\{\(L\)\}\\\}with

γ\(g\+1\)=2​γ\(g\)\\gamma^\{\(g\+1\)\}=2\\gamma^\{\(g\)\}; set

M=2​LM=2L
2:Oracles:Reward oracle

RO:𝒳×\[K\]×ℝ\+→ℝ\+K\\text\{\{RO\}\}:\\mathcal\{X\}\\times\[K\]\\times\\mathbb\{R\}\_\{\+\}\\rightarrow\\mathbb\{R\}\_\{\+\}^\{K\}, affinity oracle

AO:𝒳→ℝK×K\\text\{\{AO\}\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}^\{K\\times K\}
3:Experts:

m∈\{1,2\}m\\in\\\{1,2\\\}: SquareCB bandit\-feedback

\(m=1\)\(m=1\); CABS\-C graph\-feedback

\(m=2\)\(m=2\)
4:Initialize:For every meta\-copy

\(m,g\)\(m,g\)set weight

w1,\(m,g\)=1w\_\{1,\(m,g\)\}=1, and

Δ0=0\\Delta\_\{0\}=0
5:for

t=1t=1to

TTdo

6:Receive context

𝒙t\\bm\{x\}\_\{t\}and corresponding correlation matrix

𝑹t\\bm\{R\}\_\{t\}from

AO​\(𝒙t\)\\text\{\{AO\}\}\(\\bm\{x\}\_\{t\}\)\.

7:Generate affinity graph

GtG\_\{t\}with adjacency matrix

𝑨t\\bm\{A\}\_\{t\}:

At,\(i,j\)=1A\_\{t,\(i,j\)\}=1w\.p\.

σ​\(\(1−Rt,\(i,j\)\)/2\)\\sigma\(\(1\-R\_\{t,\(i,j\)\}\)/2\)
8:Receive policy

𝒑t,1←SquareCB​\(𝒙t\)\\bm\{p\}\_\{t,1\}\\leftarrow\\mathrm\{SquareCB\}\(\\bm\{x\}\_\{t\}\), policy

𝒑t,2←CABS​\-​C​\(𝒙t\)\\bm\{p\}\_\{t,2\}\\leftarrow\\mathrm\{CABS\\text\{\-\}C\}\(\\bm\{x\}\_\{t\}\)
9:Compute meta\-probabilities and the global mixture policy:

μt,\(m,g\)=wt,\(m,g\)∑m′=12∑g′=1Lwt,\(m′,g′\),qt,i=∑m=12∑g=1Lμt,\(m,g\)​pt,m,i,i∈\[K\]\.\\mu\_\{t,\(m,g\)\}=\\frac\{w\_\{t,\(m,g\)\}\}\{\\sum\_\{m^\{\\prime\}=1\}^\{2\}\\sum\_\{g^\{\\prime\}=1\}^\{L\}w\_\{t,\(m^\{\\prime\},g^\{\\prime\}\)\}\},\\qquad q\_\{t,i\}=\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}p\_\{t,m,i\},\\quad i\\in\[K\]\.
10:Sample action

it∼𝒒ti\_\{t\}\\sim\\bm\{q\}\_\{t\}and receive true reward

rt,itr\_\{t,i\_\{t\}\}\.

11:Observe surrogate rewards,

\{st,i\}\\\{s\_\{t,i\}\\\}←RO​\(𝒙t,it,rt,it\)\\leftarrow\\text\{\{RO\}\}\(\\bm\{x\}\_\{t\},i\_\{t\},r\_\{t,i\_\{t\}\}\)∀i∈𝒩t​\(it\)=\{j:At,\(it,j\)=1\}\\forall i\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)=\\\{j:A\_\{t,\(i\_\{t\},j\)\}=1\\\}\.

12:Send

\(𝒙t,it,rt,it\)\(\\bm\{x\}\_\{t\},i\_\{t\},r\_\{t,i\_\{t\}\}\)to SquareCB and

\(𝒙t,it,rt,it,\{st,i\}\)\\left\(\\bm\{x\}\_\{t\},i\_\{t\},r\_\{t,i\_\{t\}\},\\\{s\_\{t,i\}\\\}\\right\)to CABS\-C for policy updates\.

13:Define losses

ℓt,it=1−rt,it\\ell\_\{t,i\_\{t\}\}=1\-r\_\{t,i\_\{t\}\}and

ℓt,i=1−st,i\\ell\_\{t,i\}=1\-s\_\{t,i\}for all

i∈𝒩t​\(it\)i\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)
14:For each copy

\(m,g\)\(m,g\)with parameter

γ\(g\)\\gamma^\{\(g\)\}, compute

ℓ^t,\(1,g\)=ℓt,it​pt,1,itqt,it\+γ\(g\),ℓ^t,\(2,g\)=∑i∈𝒩t​\(it\)ℓt,i​pt,2,i∑j:At,\(j,i\)=1qt,j\+γ\(g\)\.\\hat\{\\ell\}\_\{t,\(1,g\)\}=\\frac\{\\ell\_\{t,i\_\{t\}\}p\_\{t,1,i\_\{t\}\}\}\{q\_\{t,i\_\{t\}\}\+\\gamma^\{\(g\)\}\},\\qquad\\hat\{\\ell\}\_\{t,\(2,g\)\}=\\sum\_\{i\\in\\mathcal\{N\}\_\{t\}\(i\_\{t\}\)\}\\frac\{\\ell\_\{t,i\}p\_\{t,2,i\}\}\{\\sum\_\{j:A\_\{t,\(j,i\)\}=1\}q\_\{t,j\}\+\\gamma^\{\(g\)\}\}\.
15:Set

γmin=ming∈\[L\]⁡γ\(g\),ηt=min⁡\{γmin,ln⁡M1\+Δt−1\}\.\\gamma\_\{\\min\}=\\min\_\{g\\in\[L\]\}\\gamma^\{\(g\)\},\\qquad\\eta\_\{t\}=\\min\\left\\\{\\gamma\_\{\\min\},\\sqrt\{\\frac\{\\ln M\}\{1\+\\Delta\_\{t\-1\}\}\}\\right\\\}\.
16:Compute the second\-order term

VtV\_\{t\}and update

Δt\\Delta\_\{t\}:

Vt=∑m=12∑g=1Lμt,\(m,g\)​\(ℓ^t,\(m,g\)\)2,Δt=Δt−1\+Vt\.V\_\{t\}=\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\left\(\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\)^\{2\},\\qquad\\Delta\_\{t\}=\\Delta\_\{t\-1\}\+V\_\{t\}\.
17:Update each meta\-copy weight:

wt\+1,\(m,g\)=wt,\(m,g\)​exp⁡\(−ηt​ℓ^t,\(m,g\)\)\.w\_\{t\+1,\(m,g\)\}=w\_\{t,\(m,g\)\}\\exp\\\!\\left\(\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\)\.
18:endfor

###### Theorem 4\.9\(Meta guarantee, two\-expert; constants explicit\)\.

Let there beM=2M=2experts: one bandit\-feedback expert, SquareCB and one graph\-feedback expert, CABS\-C \(tuned for known independence numberα\\alpha\)\. Assume losses lie in\[0,1\]\[0,1\]\. Then Algorithm[2](https://arxiv.org/html/2607.09015#alg2)satisfies,𝔼​\[RegT\]≤O​\(min⁡\{R1\+Γ1,R2\+Γ2\}\),\\mathbb\{E\}\\\!\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]\\leq O\\\!\\left\(\\min\\left\\\{R\_\{1\}\+\\Gamma\_\{1\},\\;R\_\{2\}\+\\Gamma\_\{2\}\\right\\\}\\right\),whereΓ1=ln⁡\(K​T​ln⁡T\)​K​T​ln⁡M​ln⁡T\\Gamma\_\{1\}=\\ln\\\!\\left\(KT\\ln T\\right\)\\sqrt\{KT\\ln M\\ln T\}andΓ2=ln⁡\(α​T​ln⁡\(T/α​ϵ\)​ln⁡T\)​α​T​ln⁡\(T/α​ϵ\)​ln⁡M​ln⁡T\\Gamma\_\{2\}=\\ln\\\!\\left\(\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln T\\right\)\\sqrt\{\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln M\\ln T\}\. HereR1R\_\{1\}is the regret of the bandit expert andR2R\_\{2\}the regret of the graph expert\. UsingR1=O~​\(K​T​RegSq​\(T\)\)R\_\{1\}=\\widetilde\{O\}\(\\sqrt\{KT\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\)andR2=O~​\(α​T​RegSq​\(T\)\+α​K​T​εn\)R\_\{2\}=\\widetilde\{O\}\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\sqrt\{\\alpha KT\}\\,\\varepsilon\_\{n\}\), we obtain the regret bound \(absorbing polylogs\)

𝔼​\[RegT\]=O~​\(min⁡\{K​T​RegSq​\(T\),α​T​RegSq​\(T\)\+εn​α​K​T\}\)\.\\mathbb\{E\}\\\!\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]=\\widetilde\{O\}\\Big\(\\min\\\{\\sqrt\{KT\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\},\\;\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\alpha KT\}\\,\\\}\\Big\)\.

The proof can be found in Appendix[F\.3](https://arxiv.org/html/2607.09015#A6.SS3)\. While the theorem establishes a general regret guarantee for the algorithm, the following corollary shows that surrogate rewards strictly improve the regret bound\.

###### Corollary 4\.10\(Linear oracle withmm\-feedback\)\.

Assume that we have a linear oracle and we observe surrogate rewards formmarms per round\. Then CABS\-D guarantees

𝔼​\[RegT\]≤O~​\(min⁡\{d​Km\+1​T​log⁡\(Td\)\+εn​K2m\+1​T,d​K​T​log⁡\(Td\)\}\)\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\widetilde\{O\}\\\!\\left\(\\min\\left\\\{\\sqrt\{d\\frac\{K\}\{m\+1\}T\\log\\\!\\left\(\\frac\{T\}\{d\}\\right\)\}\\;\+\\;\\varepsilon\_\{n\}\\allowbreak\\sqrt\{\\frac\{K^\{2\}\}\{m\+1\}T\},\\;\\sqrt\{dKT\\log\\\!\\left\(\\frac\{T\}\{d\}\\right\)\}\\right\\\}\\right\)\.

In a standard linear contextual bandit setting \(which corresponds to having no extra surrogate feedback, orm=0m=0\), the typical optimal expected regret bound overTTrounds is𝔼​\[RegT\]≤O~​\(d​K​T\)\\mathbb\{E\}\[\\text\{Reg\}\_\{T\}\]\\leq\\widetilde\{O\}\\left\(\\sqrt\{dKT\}\\right\)\. This baseline matches the second term inside themin⁡\{⋅\}\\min\\\{\\cdot\\\}operator of the regret in corollary\. Because the overall bound is a minimum between two strategies, the algorithm guarantees performance that is at least as good as the vanilla baseline, but can be significantly better depending on the value ofmmand the noiseεn\\varepsilon\_\{n\}\. Specifically, for small enoughεn\\varepsilon\_\{n\}and as long asm\>0m\>0, the first term inside the minimum takes effect where the second term in the sum vanishes\. We note that the first term in summand remains the dominant factor, as long asεn\\varepsilon\_\{n\}satisfies the conditionεn<O~​\(d/K\)\\varepsilon\_\{n\}<\\tilde\{O\}\(\\sqrt\{\{d\}/\{K\}\}\), which can be easily satisfied by training the offline surrogate model with enough samples\. In this case, the regret is entirely dominated byO~​\(d​\(Km\+1\)​T\)\\widetilde\{O\}\\left\(\\sqrt\{d\\left\(\\frac\{K\}\{m\+1\}\\right\)T\}\\right\), yielding a significant improvement over the vanillaO~​\(d​K​T\)\\widetilde\{O\}\\left\(\\sqrt\{dKT\}\\right\)bound as the effective action\-space dependence drops fromKKtoK/\(m\+1\)\{K\}/\(\{m\+1\}\)\. This significantly shrinks both the primary exploration term and the noise propagation term, allowing the algorithm to learn the underlying linear reward structure much faster than standard bandit feedback would allow\.

## 5Experiments

In this section, we conduct experiments to answer four research questions:

- \(RQ1\):How do coupled reward mixing \(CABS\-C\) and decoupled prediction mixing \(CABS\-D\) compare across cost sensitivities?
- \(RQ2\):Which routing method achieves the highest utility across cost regimes and datasets?
- \(RQ3\):Do correlation\-aware surrogate\-reward methods improve the accuracy–cost Pareto frontier relative to standard online bandit baselines?
- \(RQ4\):Do surrogate rewards accelerate online learning, as measured by reduced cumulative regret over time?

Table 1:Average utility \(higher is better\) and average regret \(lower is better\) across cost regimes on the SPROUT and RouterBench datasets\.![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/Accuracy_vs_Cost-Linear-OPEN_LLM_LB_V2.png)\(a\)
![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/Accuracy_vs_Cost-Linear-ROUTERBENCH.png)\(b\)
![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/Accuracy_vs_Cost-Linear-SPROUT.png)\(c\)

Figure 2:Accuracy vs cost Pareto Frontier curves across datasets on Linear Online models\.### 5\.1Experimental Setup

##### Datasets\.

We evaluate on three LLM routing benchmarks: RouterBench\[[25](https://arxiv.org/html/2607.09015#bib.bib16)\], SPROUT\[[41](https://arxiv.org/html/2607.09015#bib.bib48)\], and Open LLM Leaderboard v2\[[21](https://arxiv.org/html/2607.09015#bib.bib59)\]\. Dataset details and splits are deferred to Appendix[C](https://arxiv.org/html/2607.09015#A3)\.

##### Baselines\.

We compare against standard online contextual bandit algorithms, including LinUCB\[[15](https://arxiv.org/html/2607.09015#bib.bib17)\], LinTS\[[3](https://arxiv.org/html/2607.09015#bib.bib50)\], andϵ\\epsilon\-greedy\. In the LLM routing setting, observing rewards for unplayed arms is generally unrealistic, as only the selected model is executed\. Accordingly, we primarily evaluate methods under bandit feedback \(single observed reward per round\)\. For reference, we additionally report hypothetical full\-feedback variants \(LinUCB/NeuralUCB with full feedback\) as information upper bounds\. We also include strong supervised routing baselines, such as RoBERTa/CARROT\[[41](https://arxiv.org/html/2607.09015#bib.bib48)\]and kNN\-based routers\[[25](https://arxiv.org/html/2607.09015#bib.bib16)\], as well as random selection and single\-model baselines\.

##### Metrics\.

We report relative cumulative regret and average utility over time\. Specifically, the relative cumulative regret of an online learner ‘alg’ is defined with respect to ‘o​l​golg’ asRalg​\(t\)−Rolg​\(t\)R\_\{\\textit\{alg\}\}\(t\)\-R\_\{\\text\{olg\}\}\(t\), whereRalg​\(t\)R\_\{\\textit\{alg\}\}\(t\)denotes the cumulative regret at timett\. In addition, we summarize test accuracy and average per\-query cost, and characterize accuracy–cost trade\-offs via the accuracy–cost Pareto frontier by sweeping the cost\-sensitivity parameter for each method\.

##### Setup\.

We study LLM routing under varying accuracy and cost trade\-offs by sweeping the cost\-sensitivity parameter overρ∈\{0,50,…,1000\}\\rho\\in\\\{0,50,\\ldots,1000\\\}, which we group into three cost regimes: low cost sensitivity corresponds to small values ofρ\\rho\(≤300\\leq 300\) where accuracy dominates, medium cost sensitivity \(300<ρ<800300<\\rho<800\) represents a balanced trade\-off, and high cost sensitivity \(ρ≥800\\rho\\geq 800\) corresponds to large values ofρ\\rhowhere cost dominates\. For correlation\-aware methods, the Reward Oracle \(RO\) imputes surrogate utilities for graph\-neighbor arms, while the Affinity Oracle \(AO\) constructs the context\-dependent feedback graph from predicted inter\-arm similarity\. Both are lightweight MLP heads on top of mDeBERTaV3\-base query embeddings\[[24](https://arxiv.org/html/2607.09015#bib.bib36)\]\. Refer to Appendix[D](https://arxiv.org/html/2607.09015#A4)for implementation details\.

### 5\.2Reward Mixing vs Prediction Mixing \(RQ1\)

Table[1](https://arxiv.org/html/2607.09015#S5.T1)compares the coupled \(CABS\-C\) and decoupled \(CABS\-D\) variants by reporting average utility \(higher is better\) and average regret \(lower is better\) across three cost regimes in SPROUT and RouterBench dataset \(see Appendix[E](https://arxiv.org/html/2607.09015#A5)for Open LLM LB V2 dataset\)\. Across all regimes, CABS\-D, i\.e, model mixing, consistently improves utility and reduces regret relative to CABS\-C, indicating that*decoupling*reward learning from surrogate learning yields a more reliable use of surrogate signals\. This is aligned with our theory: while coupling can amplify surrogate noise or bias, the decoupled construction can exploit informative surrogate predictions early while falling back to reward\-based learning as data accumulates\. Based on these results, we use CABS\-D as the default instantiation in the remainder of our experiments\.

![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/open_llm_lb_v2_regimes_relcumreg.png)Figure 3:Relative Cumulative regrets with respect to LinUCB for other linear online learning methods on Open LLM Leaderboard V2 dataset across low, medium and high cost regimes\.Table 2:Utilities across cost regimes and datasets
### 5\.3Utility across cost regimes \(RQ2\)

Table[2](https://arxiv.org/html/2607.09015#S5.T2)reports average utility \(higher is better\) across three routing benchmarks under Low/Mid/High cost\-sensitivity regimes\. Across all datasets and regimes, CABS\-D is the strongest*implementable*method: either its linear or neural instantiation attains the best non\-oracle utility across cost regimes\. Relative to standard online bandit baselines, CABS\-D yields consistent gains \(≈8%\\approx 8\\%on Open LLM Leaderboard v2,≈3%\\approx 3\\%on RouterBench, and≈1%\\approx 1\\%on SPROUT\), with the largest improvements on the more heterogeneous Open LLM Leaderboard v2 \(≈15%,9%,7%\\approx 15\\%,9\\%,7\\%in the Low/Mid/High regimes\)\. On RouterBench and SPROUT, CABS\-D continues to dominate online baselines and remains competitive with strong static routers \(CARROT/KNN\), showing that online correlation\-aware learning can match or exceed fixed routers while adapting to the target cost regime\. Full\-feedback variants provide an information upper bound, but CABS\-D closes a substantial portion of this gap under realistic bandit feedback\.

### 5\.4Accuracy vs Cost Trade\-off \(RQ3\)

Figure[2](https://arxiv.org/html/2607.09015#S5.F2)shows the trade\-off between accuracy and average per\-query cost on Open LLM Leaderboard v2, RouterBench, and SPROUT\. Each curve traces a routing policy as the cost\-sensitivity parameterρ\\rhovaries∈\[0,1000\]\\in\[0,1000\]\. Across all datasets, CABS\-D consistently improve the accuracy versus cost Pareto frontier compared to standard online bandit baselines\. In particular, CABS\-D achieves higher accuracy at comparable cost levels \(or equivalently lower cost for a given accuracy\) relative to LinUCB, LinTS, andϵ\\epsilon\-greedy\. While full\-feedback variants provide an optimistic upper bound, CABS\-D substantially narrows this gap under realistic bandit feedback, answering RQ3 affirmatively\.

### 5\.5Learning dynamics \(RQ4\)

Figure[3](https://arxiv.org/html/2607.09015#S5.F3)reports relative cumulative regret over time normalized with respect to LinUCB, across low, mid, and high cost\-sensitivity regimes for Open LLM Leaderboard V2\. Across all regimes, CABS\-D consistently achieves lower cumulative regret than standard bandit baselines including LinUCB, LinTS, andϵ\\epsilon\-greedy\. The improvement is most pronounced in the mid\-cost regime, where the routing objective requires balancing accuracy and cost, and surrogate rewards provide the greatest benefit\. Notably, the regret gap emerges early and persists throughout the horizon, indicating that surrogate rewards accelerate online learning rather than merely improving asymptotic performance\.

## 6Discussions

We discuss the main trade\-offs between coupled and decoupled use of surrogate rewards, the computational cost of the proposed algorithms, and practical deployment considerations for LLM routing\.

##### Comparison of Coupled and Decoupled Approaches:

CABS\-C and CABS\-D differ primarily in how tightly they integrate surrogate feedback with true bandit feedback\. CABS\-C follows a coupled strategy: after debiasing surrogate rewards and applying importance weighting, it feeds both true and surrogate observations into a common regression oracle\. This coupling can improve sample efficiency when the surrogate rewards are informative, since each round provides feedback for multiple correlated arms\. However, because the two feedback sources update the same predictor, persistent surrogate bias or high surrogate noise can still affect the learned model, even when importance weighting partially controls the contribution of each observation\. CABS\-D addresses this limitation by maintaining separate learners for the standard bandit\-feedback signal and the surrogate\-aware feedback signal, and then adaptively mixing their induced policies\. As a result, when surrogate rewards are useful, CABS\-D can exploit them for faster learning; when they are uninformative or too noisy, it can fall back on the standard contextual bandit expert and retain the corresponding regret guaranteeO~​\(K​T,RegSq​\(T\)\)\\widetilde\{O\}\(\\sqrt\{KT,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\)\.

##### Computational Complexity:

This robustness comes with only a modest additional computational cost\. CABS\-C has complexityO​\(K3\+RS\)O\(K^\{3\}\+\\text\{RS\}\), while CABS\-D hasO​\(K3\+K​ln⁡T\+RS\)O\(K^\{3\}\+K\\ln T\+\\text\{RS\}\)\. TheK3K^\{3\}term comes from the optimization in line 8 of Algorithm[1](https://arxiv.org/html/2607.09015#alg1), and the extraK​ln⁡TK\\ln Tterm in CABS\-D comes from the dyadic grid in Algorithm[2](https://arxiv.org/html/2607.09015#alg2)\. For a linear oracle,O​\(RS\)=O​\(K​d\+d2\)O\(\\text\{RS\}\)=O\(Kd\+d^\{2\}\)\. In contrast, standard linear bandit methods such as LinUCB/LinTS are typically dominated by matrix operations cubic in the feature dimensiondd,O​\(K​d3\)O\(Kd^\{3\}\)\. Therefore, CABS\-C and CABS\-D may be preferable in settings with largeddor more general nonlinear function classes, whereas their stronger dependence onKKcan make them less attractive when the number of actions is very large\.

##### Surrogate Reward Prediction Overheads:

Beyond the learner update, the additional cost of producing surrogate rewards is small in our implementation\. The reward oracle is a 2\-layer MLP that reuses the context embeddings already computed for the bandit, together with the chosen arm embedding and observed reward\. In batch\-size\-1 measurements, embedding generation takes 12\.32 ms on average, while surrogate prediction itself takes only 0\.22 ms on average\. Thus, the incremental overhead from surrogate prediction beyond the encoder is negligible\.

##### Extending Utility:

Our current utility objective can already capture latency when latency is embedded in the cost term, for example through a deployment\-specific cost that combines monetary price, compute, and response time\. More explicitly, one can extend the utility asrt,a=s​\(𝐱t,a\)−ρ​c​\(𝐱t,a\)−ρ1​l​\(𝐱t,a\),r\_\{t,a\}=s\(\\mathbf\{x\}\_\{t\},a\)\-\\rho\\,c\(\\mathbf\{x\}\_\{t\},a\)\-\\rho\_\{1\}\\,l\(\\mathbf\{x\}\_\{t\},a\),wheres​\(𝐱t,a\)s\(\\mathbf\{x\}\_\{t\},a\)is the accuracy score,c​\(𝐱t,a\)c\(\\mathbf\{x\}\_\{t\},a\)is the monetary cost, andl​\(𝐱t,a\)l\(\\mathbf\{x\}\_\{t\},a\)is the latency of armaafor context𝐱t\\mathbf\{x\}\_\{t\}\. Another promising direction is to combine our framework with delayed\-feedback bandits\[[52](https://arxiv.org/html/2607.09015#bib.bib75)\], which could model latency more directly\.

## 7Conclusion

We introduce a framework for contextual bandits with correlated arms and noisy surrogate rewards, motivated by LLM routing settings where true rewards are expensive or stochastic but cheaper proxy signals are available\. We propose two complementary algorithms for leveraging these signals: a coupled reward\-mixing method that pools true and surrogate feedback, and a decoupled prediction\-mixing method that maintains separate learners for bandit\-only feedback and bandit\-plus\-surrogate feedback before adaptively combining their policies\. Our regret analysis clarifies when tight coupling is beneficial and when decoupling is needed for robustness\. Experiments on LLM routing benchmarks demonstrate that correlation\-aware surrogate integration significantly improves sample efficiency and achieves superior accuracy–cost trade\-offs compared to existing baselines, validating both the theoretical and practical benefits of the proposed framework\.

## Acknowledgment

This material is based upon work supported by the National Science Foundation \(NSF\) under Grant Number 2318101\. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author\(s\) and do not necessarily reflect the views of the National Science Foundation\.

## References

- \[1\]\(2017\)Corralling a band of bandit algorithms\.InConference on Learning Theory,pp\. 12–38\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p5.1),[§1](https://arxiv.org/html/2607.09015#S1.p5.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1)\.
- \[2\]S\. Agrawal and N\. Goyal\(2012\)Analysis of thompson sampling for the multi\-armed bandit problem\.InConference on learning theory,pp\. 39–1\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p1.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.2.2.2.2)\.
- \[3\]S\. Agrawal and N\. Goyal\(2013\)Thompson sampling for contextual bandits with linear payoffs\.In30th International Conference on Machine Learning \(ICML\),Cited by:[3rd item](https://arxiv.org/html/2607.09015#A2.I1.i3.p1.1.1),[Table 8](https://arxiv.org/html/2607.09015#A5.T8.4.1.4.4.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px2.p1.1),[Table 2](https://arxiv.org/html/2607.09015#S5.T2.4.1.7.7.1)\.
- \[4\]N\. Alon, N\. Cesa\-Bianchi, O\. Dekel, and T\. Koren\(2015\)Online learning with feedback graphs: beyond bandits\.InConference on Learning Theory,pp\. 23–35\.Cited by:[§F\.2\.1](https://arxiv.org/html/2607.09015#A6.SS2.SSS1.Px1.p2.1),[Lemma F\.5](https://arxiv.org/html/2607.09015#A6.Thmtheorem5.3.p3.13.1),[Lemma F\.6](https://arxiv.org/html/2607.09015#A6.Thmtheorem6.1.p1.1.1),[Assumption 4\.5](https://arxiv.org/html/2607.09015#S4.Thmtheorem5.p1.8)\.
- \[5\]N\. Alon, N\. Cesa\-Bianchi, C\. Gentile, S\. Mannor, Y\. Mansour, and O\. Shamir\(2014\)Nonstochastic multi\-armed bandits with graph\-structured feedback\.External Links:1409\.8428,[Link](https://arxiv.org/abs/1409.8428)Cited by:[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p5.1)\.
- \[6\]P\. Auer, N\. Cesa\-Bianchi, and P\. Fischer\(2002\)Finite\-time analysis of the multiarmed bandit problem\.Machine learning47\(2\),pp\. 235–256\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p1.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.1.1.1.2.1)\.
- \[7\]P\. Auer, N\. Cesa\-Bianchi, Y\. Freund, and R\. E\. Schapire\(2002\)The nonstochastic multiarmed bandit problem\.SIAM journal on computing32\(1\),pp\. 48–77\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p1.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.3.3.3.2)\.
- \[8\]K\. S\. Azoury and M\. K\. Warmuth\(2001\)Relative loss bounds for on\-line density estimation with the exponential family of distributions\.Machine learning43\(3\),pp\. 211–246\.Cited by:[Corollary F\.2](https://arxiv.org/html/2607.09015#A6.Thmtheorem2.p1.7.7)\.
- \[9\]Y\. Caro\(1979\)New results on the independence number\.Technical reportTechnical Report, Tel\-Aviv University\.Cited by:[item 1](https://arxiv.org/html/2607.09015#A6.I2.i1.p1.1)\.
- \[10\]H\. Chen, S\. Li, C\. Zhang,et al\.\(2021\)Understanding bandits with graph feedback\.Advances in Neural Information Processing Systems34,pp\. 24659–24669\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p3.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.6.6.6.2.1)\.
- \[11\]L\. Chen, M\. Zaharia, and J\. Zou\(2024\)FrugalGPT: how to use large language models while reducing cost and improving performance\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p2.5)\.
- \[12\]S\. Chen, W\. Jiang, B\. Lin, J\. Kwok, and Y\. Zhang\(2024\)Routerdc: query\-based router by dual contrastive learning for assembling large language models\.Advances in Neural Information Processing Systems37,pp\. 66305–66328\.Cited by:[2nd item](https://arxiv.org/html/2607.09015#A1.I1.i2.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[13\]W\. C\. Cheung and L\. Lyu\(2024\)Leveraging \(biased\) information: multi\-armed bandits with offline data\.InForty\-first International Conference on Machine Learning,Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p4.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1)\.
- \[14\]C\. Chiang, T\. Ishida, and M\. Sugiyama\(2025\)LLM routing with dueling feedback\.arXiv preprint arXiv:2510\.00841\.Cited by:[12nd item](https://arxiv.org/html/2607.09015#A1.I1.i12.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[15\]W\. Chu, L\. Li, L\. Reyzin, and R\. Schapire\(2011\)Contextual bandits with linear payoff functions\.InProceedings of the fourteenth international conference on artificial intelligence and statistics,pp\. 208–214\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p2.1),[1st item](https://arxiv.org/html/2607.09015#A2.I1.i1.p1.1.1),[2nd item](https://arxiv.org/html/2607.09015#A2.I1.i2.p1.1.1),[Table 8](https://arxiv.org/html/2607.09015#A5.T8.4.1.5.5.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px2.p1.1),[Table 2](https://arxiv.org/html/2607.09015#S5.T2.4.1.8.8.1)\.
- \[16\]X\. Dai, J\. Li, X\. Liu, A\. Yu, and J\. Lui\(2024\)Cost\-effective online multi\-llm selection with versatile reward models\.arXiv preprint arXiv:2405\.16587\.Cited by:[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[17\]T\. Erven, W\. M\. Koolen, S\. Rooij, and P\. Grünwald\(2011\)Adaptive hedge\.Advances in Neural Information Processing Systems24\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p5.1),[§1](https://arxiv.org/html/2607.09015#S1.p5.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1),[§4\.2](https://arxiv.org/html/2607.09015#S4.SS2.p2.5)\.
- \[18\]T\. Feng, Y\. Shen, and J\. You\(2024\)Graphrouter: a graph\-based router for llm selections\.arXiv preprint arXiv:2410\.03834\.Cited by:[7th item](https://arxiv.org/html/2607.09015#A1.I1.i7.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[19\]D\. J\. Foster, S\. M\. Kakade, J\. Qian, and A\. Rakhlin\(2021\)The statistical complexity of interactive decision making\.arXiv preprint arXiv:2112\.13487\.Cited by:[Table 3](https://arxiv.org/html/2607.09015#A1.T3.4.4.4.2),[Lemma F\.3](https://arxiv.org/html/2607.09015#A6.Thmtheorem3.1.p1.1.1)\.
- \[20\]D\. Foster and A\. Rakhlin\(2020\)Beyond ucb: optimal and efficient contextual bandits with regression oracles\.InInternational conference on machine learning,pp\. 3199–3210\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p2.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.8.8.8.2),[§F\.1](https://arxiv.org/html/2607.09015#A6.SS1.p1.1),[§F\.2\.2](https://arxiv.org/html/2607.09015#A6.SS2.SSS2.Px1.p1.2),[§F\.3\.1](https://arxiv.org/html/2607.09015#A6.SS3.SSS1.Px2.p1.2),[Theorem F\.1](https://arxiv.org/html/2607.09015#A6.Thmtheorem1),[§1](https://arxiv.org/html/2607.09015#S1.p2.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2607.09015#S3.p4.6),[Assumption 4\.1](https://arxiv.org/html/2607.09015#S4.Thmtheorem1.p1.2),[§4](https://arxiv.org/html/2607.09015#S4.p1.1),[Algorithm 3](https://arxiv.org/html/2607.09015#alg3)\.
- \[21\]C\. Fourrier, N\. Habib, A\. Lozovskaya, K\. Szafer, and T\. Wolf\(2024\)Open llm leaderboard v2\.Hugging Face\.Note:[https://huggingface\.co/spaces/open\-llm\-leaderboard/open\_llm\_leaderboard](https://huggingface.co/spaces/open-llm-leaderboard/open_llm_leaderboard)Cited by:[3rd item](https://arxiv.org/html/2607.09015#A3.I1.i3.p1.1),[§E\.1](https://arxiv.org/html/2607.09015#A5.SS1.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px1.p1.1)\.
- \[22\]Y\. Freund and R\. E\. Schapire\(1997\)A decision\-theoretic generalization of on\-line learning and an application to boosting\.Journal of computer and system sciences55\(1\),pp\. 119–139\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p5.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1)\.
- \[23\]Google AI\(2024\)Gemini 1\.5 pro model overview\.Note:[https://ai\.google\.dev/gemini\-api/docs/models/gemini](https://ai.google.dev/gemini-api/docs/models/gemini)Accessed: 2025\-05\-10Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p1.1)\.
- \[24\]P\. He, X\. Liu, J\. Gao, and W\. Chen\(2021\)DEBERTA: decoding\-enhanced bert with disentangled attention\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=XPZIaotutsD)Cited by:[Appendix D](https://arxiv.org/html/2607.09015#A4.SS0.SSS0.Px1.p1.1),[§E\.2](https://arxiv.org/html/2607.09015#A5.SS2.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px4.p1.6)\.
- \[25\]Q\. J\. Hu, J\. Bieker, X\. Li, N\. Jiang, B\. Keigwin, G\. Ranganath, K\. Keutzer, and S\. K\. Upadhyay\(2024\)RouterBench: a benchmark for multi\-llm routing system\.External Links:2403\.12031,[Link](https://arxiv.org/abs/2403.12031)Cited by:[1st item](https://arxiv.org/html/2607.09015#A1.I1.i1.p1.1),[2nd item](https://arxiv.org/html/2607.09015#A2.I2.i2.p1.2.1),[1st item](https://arxiv.org/html/2607.09015#A3.I1.i1.p1.1),[§E\.1](https://arxiv.org/html/2607.09015#A5.SS1.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px2.p1.1),[Table 2](https://arxiv.org/html/2607.09015#S5.T2.4.1.4.4.1)\.
- \[26\]K\. Huang, Y\. Shi, D\. Ding, Y\. Li, Y\. Fei, L\. Lakshmanan, and X\. Xiao\(2025\)ThriftLLM: on cost\-effective selection of large language models for classification queries\.External Links:2501\.04901,[Link](https://arxiv.org/abs/2501.04901)Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p2.5)\.
- \[27\]Hugging Face\(2025\)all\-MiniLM\-L6\-v2: sentence transformer embedding model\.Note:[https://huggingface\.co/sentence\-transformers/all\-MiniLM\-L6\-v2](https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2)Accessed: 2026\-02\-15Cited by:[§E\.2](https://arxiv.org/html/2607.09015#A5.SS2.p1.1),[Table 8](https://arxiv.org/html/2607.09015#A5.T8),[Table 8](https://arxiv.org/html/2607.09015#A5.T8.3.2)\.
- \[28\]Hugging Face\(2025\)Hugging face models\.Note:[https://huggingface\.co/models](https://huggingface.co/models)Accessed: 2025\-05\-10Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p1.1)\.
- \[29\]W\. Ji, Y\. Pan, R\. Zhu, and L\. Lei\(2025\)Multi\-armed bandits with machine learning\-generated surrogate rewards\.arXiv preprint arXiv:2506\.16658\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p4.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1)\.
- \[30\]D\. Jiang, X\. Ren, and B\. Y\. Lin\(2023\)LLM\-blender: ensembling large language models with pairwise ranking and generative fusion\.External Links:2306\.02561,[Link](https://arxiv.org/abs/2306.02561)Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p2.5)\.
- \[31\]T\. Lattimore and C\. Szepesvári\(2020\)Bandit algorithms\.Cambridge University Press\.Cited by:[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1)\.
- \[32\]L\. Li, W\. Chu, J\. Langford, and R\. E\. Schapire\(2010\)A contextual\-bandit approach to personalized news article recommendation\.InProceedings of the 19th international conference on World wide web,pp\. 661–670\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p2.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.8.8.8.2),[§4](https://arxiv.org/html/2607.09015#S4.p1.1)\.
- \[33\]Y\. Li\(2025\)LLM bandit: cost\-efficient llm generation via preference\-conditioned dynamic routing\.External Links:2502\.02743,[Link](https://arxiv.org/abs/2502.02743)Cited by:[9th item](https://arxiv.org/html/2607.09015#A1.I1.i9.p1.1),[§1](https://arxiv.org/html/2607.09015#S1.p2.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[34\]S\. Mannor and O\. Shamir\(2011\)From bandits to experts: on the value of side\-observations\.Advances in Neural Information Processing Systems24\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p3.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.5.5.5.2.1)\.
- \[35\]G\. Neu and J\. Olkhovskaya\(2020\)Efficient and robust algorithms for adversarial linear contextual bandits\.InConference on Learning Theory,pp\. 3049–3068\.Cited by:[Table 3](https://arxiv.org/html/2607.09015#A1.T3.13.13.13.2.1)\.
- \[36\]Q\. H\. Nguyen, T\. Dao, D\. C\. Hoang, J\. Decugis, S\. Manchanda, N\. V\. Chawla, and K\. D\. Doan\(2025\)MetaLLM: a high\-performant and cost\-efficient dynamic framework for wrapping llms\.External Links:2407\.10834,[Link](https://arxiv.org/abs/2407.10834)Cited by:[8th item](https://arxiv.org/html/2607.09015#A1.I1.i8.p1.1),[1st item](https://arxiv.org/html/2607.09015#A2.I1.i1.p1.1.1),[§1](https://arxiv.org/html/2607.09015#S1.p2.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[37\]I\. Ong, A\. Almahairi, V\. Wu, W\. Chiang, T\. Wu, J\. E\. Gonzalez, M\. W\. Kadous, and I\. Stoica\(2025\)RouteLLM: learning to route llms from preference data\.InThe Thirteenth International Conference on Learning Representations,Cited by:[4th item](https://arxiv.org/html/2607.09015#A1.I1.i4.p1.1),[§1](https://arxiv.org/html/2607.09015#S1.p2.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[38\]OpenAI\(2025\)ChatGPT\.Note:[https://chat\.openai\.com/chat](https://chat.openai.com/chat)Accessed: 2025\-05\-10Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p1.1)\.
- \[39\]S\. Shalev\-Shwartz and S\. Ben\-David\(2014\)Understanding machine learning: from theory to algorithms\.Cambridge university press\.Cited by:[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p10.2)\.
- \[40\]H\. Shimodaira\(2000\)Improving predictive inference under covariate shift by weighting the log\-likelihood function\.Journal of statistical planning and inference90\(2\),pp\. 227–244\.Cited by:[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p10.2)\.
- \[41\]S\. Somerstep, F\. M\. Polo, A\. F\. M\. de Oliveira, P\. Mangal, M\. Silva, O\. Bhardwaj, M\. Yurochkin, and S\. Maity\(2025\)Carrot: a cost aware rate optimal router\.arXiv preprint arXiv:2502\.03261\.Cited by:[3rd item](https://arxiv.org/html/2607.09015#A1.I1.i3.p1.1),[1st item](https://arxiv.org/html/2607.09015#A2.I2.i1.p1.1.1),[2nd item](https://arxiv.org/html/2607.09015#A3.I1.i2.p1.1),[§E\.1](https://arxiv.org/html/2607.09015#A5.SS1.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2607.09015#S5.SS1.SSS0.Px2.p1.1),[Table 2](https://arxiv.org/html/2607.09015#S5.T2.4.1.3.3.1)\.
- \[42\]D\. Stripelis, Z\. Hu, J\. Zhang, Z\. Xu, A\. D\. Shah, H\. Jin, Y\. Yao, S\. Avestimehr, and C\. He\(2024\)TensorOpera router: a multi\-model router for efficient llm inference\.External Links:2408\.12320,[Link](https://arxiv.org/abs/2408.12320)Cited by:[6th item](https://arxiv.org/html/2607.09015#A1.I1.i6.p1.1),[§1](https://arxiv.org/html/2607.09015#S1.p2.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[43\]M\. Sugiyama and M\. Kawanabe\(2012\)Machine learning in non\-stationary environments: introduction to covariate shift adaptation\.MIT press\.Cited by:[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p10.2)\.
- \[44\]M\. Valko, N\. Korda, R\. Munos, I\. Flaounas, and N\. Cristianini\(2013\)Finite\-time analysis of kernelised contextual bandits\.arXiv preprint arXiv:1309\.6869\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p2.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.9.9.9.2.1)\.
- \[45\]V\. Vapnik\(2013\)The nature of statistical learning theory\.Springer science & business media\.Cited by:[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p10.2)\.
- \[46\]A\. Verma, Z\. Dai, Y\. Shu, and B\. K\. H\. Low\(2023\)Exploiting correlated auxiliary feedback in parameterized bandits\.Advances in Neural Information Processing Systems36,pp\. 4430–4451\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p4.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1)\.
- \[47\]V\. Vovk\(1997\)Competitive on\-line linear regression\.Advances in Neural Information Processing Systems10\.Cited by:[Corollary F\.2](https://arxiv.org/html/2607.09015#A6.Thmtheorem2.p1.7.7)\.
- \[48\]X\. Wang, Y\. Liu, W\. Cheng, X\. Zhao, Z\. Chen, W\. Yu, Y\. Fu, and H\. Chen\(2025\)MixLLM: dynamic routing in mixed large language models\.External Links:2502\.18482,[Link](https://arxiv.org/abs/2502.18482)Cited by:[10th item](https://arxiv.org/html/2607.09015#A1.I1.i10.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[49\]V\. K\. Wei\(1981\)A lower bound on the stability number of a simple graph\.Bell Laboratories Technical Memorandum Murray Hill, NJ, USA\.Cited by:[item 1](https://arxiv.org/html/2607.09015#A6.I2.i1.p1.1)\.
- \[50\]W\. Wei, T\. Yang, H\. Chen, Y\. Zhao, F\. Dernoncourt, R\. A\. Rossi, and H\. Eldardiry\(2025\)Learning to route llms from bandit feedback: one policy, many trade\-offs\.arXiv preprint arXiv:2510\.07429\.Cited by:[11st item](https://arxiv.org/html/2607.09015#A1.I1.i11.p1.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[51\]xAI\(2024\)Open release of grok\-1\.Note:[https://x\.ai/blog/grok\-os](https://x.ai/blog/grok-os)Accessed: 2025\-05\-10Cited by:[§1](https://arxiv.org/html/2607.09015#S1.p1.1)\.
- \[52\]M\. Zhang, Y\. Wang, and H\. Luo\(2025\)Contextual linear bandits with delay as payoff\.External Links:2502\.12528,[Link](https://arxiv.org/abs/2502.12528)Cited by:[§6](https://arxiv.org/html/2607.09015#S6.SS0.SSS0.Px4.p1.6)\.
- \[53\]M\. Zhang, Y\. Zhang, H\. Luo, and P\. Mineiro\(2024\)Efficient contextual bandits with uninformed feedback graphs\.arXiv preprint arXiv:2402\.08127\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p3.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.17.17.17.2.1),[§1](https://arxiv.org/html/2607.09015#S1.p4.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p1.11)\.
- \[54\]M\. Zhang, Y\. Zhang, O\. Vrousgou, H\. Luo, and P\. Mineiro\(2023\)Practical contextual bandits with feedback graphs\.Advances in Neural Information Processing Systems36,pp\. 30592–30617\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p3.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.14.14.14.2.1),[Appendix D](https://arxiv.org/html/2607.09015#A4.SS0.SSS0.Px2.p1.3),[Appendix D](https://arxiv.org/html/2607.09015#A4.SS0.SSS0.Px2.p2.13),[Theorem D\.1](https://arxiv.org/html/2607.09015#A4.Thmtheorem1),[Lemma F\.5](https://arxiv.org/html/2607.09015#A6.Thmtheorem5.1.p1.1.1),[§1](https://arxiv.org/html/2607.09015#S1.p4.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2607.09015#S3.p4.6),[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p1.11),[Assumption 4\.2](https://arxiv.org/html/2607.09015#S4.Thmtheorem2.p1.4)\.
- \[55\]Z\. Zhao, S\. Jin, and Z\. M\. Mao\(2024\)Eagle: efficient training\-free router for multi\-llm inference\.External Links:2409\.15518,[Link](https://arxiv.org/abs/2409.15518)Cited by:[5th item](https://arxiv.org/html/2607.09015#A1.I1.i5.p1.1),[§1](https://arxiv.org/html/2607.09015#S1.p2.5),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px2.p1.1)\.
- \[56\]D\. Zhou, L\. Li, and Q\. Gu\(2020\)Neural contextual bandits with ucb\-based exploration\.InInternational conference on machine learning,pp\. 11492–11502\.Cited by:[§A\.1](https://arxiv.org/html/2607.09015#A1.SS1.p2.1),[Table 3](https://arxiv.org/html/2607.09015#A1.T3.11.11.11.2.1),[5th item](https://arxiv.org/html/2607.09015#A2.I1.i5.p1.1.1),[6th item](https://arxiv.org/html/2607.09015#A2.I1.i6.p1.1.1),[Table 8](https://arxiv.org/html/2607.09015#A5.T8.4.1.6.6.1),[§2](https://arxiv.org/html/2607.09015#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2607.09015#S4.SS1.p12.1),[Table 2](https://arxiv.org/html/2607.09015#S5.T2.4.1.9.9.1)\.

## Appendix

The appendix is organized as follows,

- •In Appendix[A](https://arxiv.org/html/2607.09015#A1)we discuss additional related works
- •In Appendix[B](https://arxiv.org/html/2607.09015#A2)we expand on the baselines that are used in our experiments\.
- •In Appendix[C](https://arxiv.org/html/2607.09015#A3), we expand on the LLM routing datasets\.
- •In Appendix[D](https://arxiv.org/html/2607.09015#A4), implementation details are discussed\.
- •In Appendix[E](https://arxiv.org/html/2607.09015#A5), we present additional experiments and results\.
- •In Appendix[F](https://arxiv.org/html/2607.09015#A6), we present the proofs for CABS\-C and CABS\-D algorithms\.

## Appendix AAdditional Related Works

### A\.1Multi\-Armed Bandits \(MAB\)

Classical stochastic bandits study decision\-making with partial feedback and no context\. UCB\-type methods\[[6](https://arxiv.org/html/2607.09015#bib.bib39)\]use optimism under uncertainty, while Thompson sampling\[[2](https://arxiv.org/html/2607.09015#bib.bib40)\]samples actions from a posterior distribution\. Adversarial algorithms such as Exp3\[[7](https://arxiv.org/html/2607.09015#bib.bib6)\]provide guarantees without stochastic reward assumptions\. These methods form the basis for exploration–exploitation trade\-offs but do not capture query\-dependent model selection\.

Contextual bandits incorporate side information into the decision rule\. Linear methods such as LinUCB\[[32](https://arxiv.org/html/2607.09015#bib.bib34),[15](https://arxiv.org/html/2607.09015#bib.bib17)\]assume rewards are linear in context features, while KernelUCB\[[44](https://arxiv.org/html/2607.09015#bib.bib42)\]and NeuralUCB\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\]model nonlinear reward functions\. More generally, SquareCB\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]reduces contextual bandit learning to online regression by using a reward predictor to construct exploration probabilities, providing a flexible oracle\-based template beyond linear models\. These methods are natural baselines for LLM routing, but typically observe feedback only for the selected arm and do not explicitly exploit inter\-arm relationships\.

Bandits with graph feedback study settings where playing one arm reveals additional observations from neighboring arms\. Earlier work considers non\-contextual graph\-feedback models\[[34](https://arxiv.org/html/2607.09015#bib.bib46),[10](https://arxiv.org/html/2607.09015#bib.bib47)\], while SquareCB\-G\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\]and SquareCB\-UG\[[53](https://arxiv.org/html/2607.09015#bib.bib45)\]extend this idea to contextual settings\. SquareCB\-G assumes graph\-structured observations of true rewards, whereas SquareCB\-UG handles graphs that are not known before action selection\. Our setting differs because the graph is context\-dependent and available before action selection, while additional observations are potentially noisy/misspecified surrogate rewards rather than true rewards\.

Auxiliary\-feedback bandits use external predictors or side observations to improve learning\. MIN\-UCB\[[13](https://arxiv.org/html/2607.09015#bib.bib76)\], OFUL\-AF\[[46](https://arxiv.org/html/2607.09015#bib.bib77)\], and MLA\-UCB\[[29](https://arxiv.org/html/2607.09015#bib.bib78)\]are representative examples\. These methods typically use auxiliary information to improve reward estimation for the played arm or to regularize learning\. Our setting instead uses context\-dependent graph structure to decide which unplayed arms receive surrogate feedback, requiring robustness to surrogate noise and bias\.

Expert\-aggregation methods provide another relevant perspective for our decoupled algorithm\. Hedge and multiplicative\-weight algorithms aggregate expert predictions with regret guarantees against the best fixed expert in hindsight\[[22](https://arxiv.org/html/2607.09015#bib.bib85)\], while adaptive variants such as AdaHedge tune the learning rate online based on observed losses\[[17](https://arxiv.org/html/2607.09015#bib.bib84)\]\. Related master algorithms, such as Corral\[[1](https://arxiv.org/html/2607.09015#bib.bib87)\], combine multiple bandit algorithms and compete with the best base learner under partial feedback\. CABS\-D follows this meta\-algorithmic view, but the experts correspond to different feedback mechanisms: standard bandit feedback and correlation\-aware surrogate graph feedback\.

Table[3](https://arxiv.org/html/2607.09015#A1.T3)summarizes representative bandit settings, feedback models, and regret rates\. We report worst\-case order bounds, hiding polylogarithmic factors inO~​\(⋅\)\\widetilde\{O\}\(\\cdot\), under standard assumptions; some algorithms admit sharper gap\-dependent bounds, which we omit for brevity\.

Table 3:Representative bandit settings, feedback models, and regret bounds\.Algorithm\(s\)ClassificationFeedbackRegret BoundNon\-Contextual SettingUCB1\[[6](https://arxiv.org/html/2607.09015#bib.bib39)\]Stochastic Non\-ContextualPartialO​\(K​T​log⁡T\)O\\\!\\left\(\\sqrt\{KT\\log T\}\\right\)Thompson Sampling\[[2](https://arxiv.org/html/2607.09015#bib.bib40)\]Stochastic Non\-ContextualPartialO​\(\(∑i:μi<μ∗1Δi2\)2​log⁡T\)O\\\!\\left\(\\left\(\\sum\_\{i:\\mu\_\{i\}<\\mu^\{\*\}\}\\frac\{1\}\{\\Delta\_\{i\}^\{2\}\}\\right\)^\{2\}\\log T\\right\)\*problem\-dependent boundExp3\[[7](https://arxiv.org/html/2607.09015#bib.bib6)\]Adversarial Non\-ContextualPartialO​\(K​T​log⁡K\)O\(\\sqrt\{KT\\log K\}\)E2D\[[19](https://arxiv.org/html/2607.09015#bib.bib44)\]Stochastic Non\-ContextualPartialO​\(K​T​log⁡K\)O\(\\sqrt\{KT\\log K\}\)ELP\[[34](https://arxiv.org/html/2607.09015#bib.bib46)\]Graph FeedbackPartial/FullO~​\(log⁡\(k\)​∑t=1Tαt\)\\widetilde\{O\}\(\\sqrt\{\\log\(k\)\\sum\_\{t=1\}^\{T\}\\alpha\_\{t\}\}\)Stochastic Non\-ContextualOSMD\[[10](https://arxiv.org/html/2607.09015#bib.bib47)\]Graph FeedbackPartial/FullO​\(\(δ∗​log⁡\(k\)\)13​T23\)O\\\!\\left\(\\left\(\\delta^\{\*\}\\log\(k\)\\right\)^\{\\frac\{1\}\{3\}\}T^\{\\frac\{2\}\{3\}\}\\right\)Stochastic Non\-Contextualδ∗\\delta^\{\*\}is packing numberContextual SettingLinUCB\[[32](https://arxiv.org/html/2607.09015#bib.bib34)\]& SquareCB\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]Stochastic Contextual \(Linear\)PartialO~​\(K​d​T\)\\widetilde\{O\}\\\!\\left\(\\sqrt\{KdT\}\\right\)KernelUCB\[[44](https://arxiv.org/html/2607.09015#bib.bib42)\]Stochastic Contextual \(Non\-Linear\)PartialO~​\(d~​T\)\\widetilde\{O\}\(\\widetilde\{d\}\\sqrt\{T\}\)\(d~\\tilde\{d\}be the effective dimension\)NeuralUCB\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\]Stochastic Contextual \(Non\-Linear\)PartialO~​\(d~​T\)\\widetilde\{O\}\(\\widetilde\{d\}\\sqrt\{T\}\)\(d~\\tilde\{d\}be the effective dimension\)RealLinExp3\[[35](https://arxiv.org/html/2607.09015#bib.bib43)\]Adversarial Contextual \(Linear\)PartialO~​\(K​d​T\)\\widetilde\{O\}\(\\sqrt\{KdT\}\)Square\-CB\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\]Informed Graph FeedbackPartial/FullO~​\(α​T​R​e​gs​q\)\\widetilde\{O\}\(\\sqrt\{\\alpha TReg\_\{sq\}\}\)Stochastic Contextual \(Non\-Linear\)\(R​e​gs​qReg\_\{sq\}= bound of regression oracle\)\(α\\alpha= independence number\)SquareCB\-UG\[[53](https://arxiv.org/html/2607.09015#bib.bib45)\]Uninformed Graph FeedbackPartial/FullO~​\(α​T​max⁡\(R​e​gs​q,R​e​gl​o​g\)\)\\widetilde\{O\}\(\\sqrt\{\\alpha T\\max\\left\(Reg\_\{sq\},Reg\_\{log\}\\right\)\}\)Stochastic Contextual \(Non\-Linear\)\(R​e​gs​qReg\_\{sq\}= bound of regression oracle\)\(R​e​gl​o​gReg\_\{log\}= bound of graph oracle\)\(α\\alpha= independence number\)

### A\.2LLM Routing

Here we give a high level overview of selected LLM routing methods,

- •RouterBench\[[25](https://arxiv.org/html/2607.09015#bib.bib16)\]introduces a standardized benchmark/dataset and evaluation protocol for multi\-LLM routers under explicit cost–performance trade\-offs, enabling apples\-to\-apples comparison across routing strategies\.
- •RouterDC\[[12](https://arxiv.org/html/2607.09015#bib.bib15)\]proposes a query\-based router trained via dual contrastive learning, aligning query embeddings with top\-performing LLM embeddings \(and separating from poorly performing ones\) using sample–LLM and sample–sample contrastive losses to improve routing stability and robustness\.
- •CARROT / SPROUT\[[41](https://arxiv.org/html/2607.09015#bib.bib48)\]propose a cost\-aware router based on estimating model cost/performance, and introduce the SPROUT dataset to evaluate routing over a wide query distribution and modern model pools\.
- •RouteLLM\[[37](https://arxiv.org/html/2607.09015#bib.bib20)\]trains a router from preference supervision to decide between cheaper and stronger LLMs, targeting cost savings at fixed quality levels and demonstrating transfer across model pairs\.
- •Eagle\[[55](https://arxiv.org/html/2607.09015#bib.bib27)\]proposes a training\-free router that uses ELO\-style ranking \(global and local\) to efficiently update routing decisions, aiming at scalable online serving without heavy retraining\.
- •TensorOpera / TO\-Router\[[42](https://arxiv.org/html/2607.09015#bib.bib29)\]studies multi\-model orchestration as a system problem and routes queries to expert LLMs to improve the throughput–cost–quality “trilemma” in practical deployments\.
- •GraphRouter\[[18](https://arxiv.org/html/2607.09015#bib.bib71)\]models query–task–LLM interactions as a heterogeneous graph and performs edge/attribute prediction to recommend an LLM, emphasizing generalization to new LLMs via relational inductive bias\.
- •MetaLLM\[[36](https://arxiv.org/html/2607.09015#bib.bib10)\]frames routing as a contextual bandit and learns an online selection policy from partial feedback to improve cost\-efficiency on targeted tasks \(e\.g\., classification / MCQ\)\.
- •LLM Bandit\[[33](https://arxiv.org/html/2607.09015#bib.bib30)\]formulates LLM selection as a bandit problem with preference\-conditioned routing, allowing users to specify trade\-offs at inference while learning under partial\-feedback constraints\.
- •MixLLM\[[48](https://arxiv.org/html/2607.09015#bib.bib31)\]extends contextual\-bandit routing to dynamic objectives \(quality/cost/latency\) with continual learning and changing model pools, using lightweight predictors plus a meta decision module\.
- •BaRP\[[50](https://arxiv.org/html/2607.09015#bib.bib69)\]trains routers to align with the deployment partial\-feedback setting while conditioning on a user preference vector, enabling a single learned policy to realize multiple cost–quality trade\-offs at test time\.
- •LLM Routing with Dueling Feedback\[[14](https://arxiv.org/html/2607.09015#bib.bib1)\]treats routing as contextual dueling bandits and learns from pairwise preferences between two candidate model outputs, using CCFT representations and FGTS\.CDB for online learning\.

## Appendix BBaselines

- •LinUCB\[[15](https://arxiv.org/html/2607.09015#bib.bib17)\]/ MetaLLM\[[36](https://arxiv.org/html/2607.09015#bib.bib10)\]: the standard linear upper\-confidence bound algorithm, which selects the arm with the highest optimistic estimate of the linear reward\.
- •LinUCB\[[15](https://arxiv.org/html/2607.09015#bib.bib17)\]\+ Full Feedback: an oracle variant of LinUCB that observes the full reward vector for all arms at every round, rather than only the reward of the chosen arm\. This baseline is not implementable in practice but provides a strong upper bound on what is achievable with linear models\.
- •LinTS\[[3](https://arxiv.org/html/2607.09015#bib.bib50)\]: Linear Thompson sampling with a Gaussian posterior over the regression parameters\.
- •Epsilon Greedy: a linear regression model updated online together with anϵ\\epsilon\-greedy exploration policy\.
- •NeuralUCB\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\]: a neural contextual bandit algorithm that uses a neural network reward predictor and an upper\-confidence bonus based on the network’s linearized features \(e\.g\., via the last\-layer/NTK approximation\), selecting the arm with the highest optimistic predicted reward\.
- •NeuralUCB\[[56](https://arxiv.org/html/2607.09015#bib.bib3)\]\+ Full\-Feedback: an oracle variant of NeuralUCB that observes the full reward vector for all arms at each round and updates the neural predictor using all arms’ rewards, providing an upper bound on what is achievable with neural reward models under full information\.

All online learning baselines use exactly the same feature representation as CABS\-C/CABS\-D and differ only in their exploration strategy and feedback model\. We additionally compare against*static*routers that do not adapt during test time:

- •CARROT\[[41](https://arxiv.org/html/2607.09015#bib.bib48)\]\(RoBERTa\): we adapt the current SOTA CARROT router to our utility objective\. Instead of predicting the probability of success, we fine\-tune a RoBERTa encoder as a regressor to predict, for each \(query, model\) pair, both the correctness reward and the cost\. At test time, the router selects the model with the largest predicted utility,r^t,it=y^t,it−ρ⋅c^t,it\\hat\{r\}\_\{t,i\_\{t\}\}=\\hat\{y\}\_\{t,i\_\{t\}\}\-\\rho\\cdot\\hat\{c\}\_\{t,i\_\{t\}\}\.
- •KNN \(RouterBench\[[25](https://arxiv.org/html/2607.09015#bib.bib16)\]\): a non\-parametric router operating on text embeddings\. For each test query, we retrieve thek=3k=3nearest training queries \(in embedding space\) for each candidate model and estimate reward and cost by averaging over their observed outcomes\. The chosen model maximizes the estimated utilityr^t,it\\hat\{r\}\_\{t,i\_\{t\}\}\.
- •Random Selection: For each query, this method randomly selects an arm from the K possible arms\.
- •Finally, we report the performance of individual LLMs used by the benchmarks as static baselines that always route to a single model\. This highlights the benefit of routing compared to selecting a single fixed model\.

## Appendix CDataset Details

- •RouterBench\[[25](https://arxiv.org/html/2607.09015#bib.bib16)\]contains roughly 35k text queries spanning 8 reasoning, coding, and commonsense datasets, with responses from 11 LLMs annotated using GPT\-4 LLM\-as\-judge binary correctness and token\-based cost\. We randomly split the dataset into 70% train, 10% validation, and 20% test\.
- •SPROUT\[[41](https://arxiv.org/html/2607.09015#bib.bib48)\]contains roughly 44k queries drawn from six reasoning datasets, with responses from 15 LLMs annotated with cost and numeric correctness scores using LLama 3\.1 70B LLM\-as\-judge\. We use the default train/val/test split\.
- •Open LLM Leaderboard v2\[[21](https://arxiv.org/html/2607.09015#bib.bib59)\]provides responses from 18 contemporary LLMs for routing evaluation\. The scores are generated using exact match\-based accuracy\. We randomly split the dataset into 70% train, 10% validation, and 20% test\.

We also show the average performance of each LLMs in the three LLM Routing datasets \(Table[4](https://arxiv.org/html/2607.09015#A3.T4), Table[5](https://arxiv.org/html/2607.09015#A3.T5)and Table[6](https://arxiv.org/html/2607.09015#A3.T6)\)\.

Table 4:Average performance and cost for models in OpenLLM Leaderboard V2 datasetTable 5:Average performance and cost for models in SPROUT datasetTable 6:Average performance and cost for models in RouterBench dataset
## Appendix DImplementation Details

All experiments are conducted on a machine equipped with 1xNVIDIA H100 GPU \(80 GB\)\. For all linear online learning methods, we set the regularization parameter toλ=10\\lambda=10andγ=4\\gamma=4whenever applicable\. For neural online learning methods, we set regularization parameter toλ=0\.001\\lambda=0\.001and the hidden dimension to 64, with learning rate of0\.0010\.001\. Reported results for all online learning methods are averaged over 10 independent trials to account for randomness in data ordering\. Forε\\varepsilon\-greedy, we use the decay schedule,ϵt=max⁡\(ϵmin,ϵ01\+decay⋅t\)\\epsilon\_\{t\}=\\max\\\!\\left\(\\epsilon\_\{\\min\},\\frac\{\\epsilon\_\{0\}\}\{1\+\\text\{decay\}\\cdot t\}\\right\), tuneϵ0∈\{1\.0,0\.5,0\.2,0\.1\}\\epsilon\_\{0\}\\in\\\{1\.0,0\.5,0\.2,0\.1\\\}per dataset, and fixdecay=0\.001\\text\{decay\}=0\.001andϵmin=0\.01\\epsilon\_\{\\min\}=0\.01\. For LinUCB/NeuralUCB with full feedback, we update using the ground\-truth rewards of all arms at each round; since all rewards are observed, we set the exploration parameter to zero\.

##### Affinity and Reward Oracles\.

We implement the*Reward Oracle*\(RO\) and*Affinity Oracle*\(AO\) using a lightweight multi\-head network on top of query embeddings𝒙t\\bm\{x\}\_\{t\}\. Each query is encoded once, using mDeBERTaV3\-base\[[24](https://arxiv.org/html/2607.09015#bib.bib36)\]in our experiments, and passed to small MLP\-style heads \(using Tanh/GELU/ReLU nonlinearities with normalization/dropout\)\. The framework is otherwise encoder\-agnostic\.

TheROpredicts the accuracy and cost components separately and combines them into the cost\-informed utilityrt,j=yt,j−ρ​ct,jr\_\{t,j\}=y\_\{t,j\}\-\\rho c\_\{t,j\}\. For query embedding𝒙t\\bm\{x\}\_\{t\}and anchor armiti\_\{t\}, we define the accuracy deltaδt,j​\(it\)=yt,j−yt,it\\delta\_\{t,j\}\(i\_\{t\}\)=y\_\{t,j\}\-y\_\{t,i\_\{t\}\}for allj∈\[K\]j\\in\[K\]\. A correlation\-aware propagation head predictsδ^t,j​\(it\)=g​\(𝒙t,it,yt,it\)\\widehat\{\\delta\}\_\{t,j\}\(i\_\{t\}\)=g\(\\bm\{x\}\_\{t\},i\_\{t\},y\_\{t,i\_\{t\}\}\), yielding surrogate accuraciesy~t,j=yt,it\+δ^t,j​\(it\)\\tilde\{y\}\_\{t,j\}=y\_\{t,i\_\{t\}\}\+\\widehat\{\\delta\}\_\{t,j\}\(i\_\{t\}\)after observingyt,ity\_\{t,i\_\{t\}\}\. In parallel, a cost head predictsc^t,j=h​\(𝒙t,j\)\\widehat\{c\}\_\{t,j\}=h\(\\bm\{x\}\_\{t\},j\)\(trained with MSE onzz\-scored costs\), and the two are combined asst,j=y~t,j−ρ​c^t,js\_\{t,j\}=\\tilde\{y\}\_\{t,j\}\-\\rho\\widehat\{c\}\_\{t,j\}\. These surrogate utilities are then filtered to generate additional feedback for correlation\-aware updates\.

TheAOis constructed from a context\-only accuracy prediction head, which outputs per\-arm scoresy¯t,j\\bar\{y\}\_\{t,j\}for allj∈\[K\]j\\in\[K\]\. Since estimating a true context\-conditional arm correlation matrix would require repeated joint observations for the same query, we instead use the proxyRt,\(i,j\)=1−2​\|y¯t,i−y¯t,j\|R\_\{t,\(i,j\)\}=1\-2\|\\bar\{y\}\_\{t,i\}\-\\bar\{y\}\_\{t,j\}\|, which is high for arms predicted to behave similarly and low, possibly negative, for arms predicted to differ sharply\. This proxy defines the feedback graph used by our correlation\-aware methods, although our algorithms and theory allow any context\-dependent choice of𝑹t\\bm\{R\}\_\{t\}\. To enforce self loops, we setRt,\(i,i\)=−∞R\_\{t,\(i,i\)\}=\-\\infty\.

In addition to the cost, propagation, and context\-only accuracy heads, the network includes a bandit feature head that maps𝒙t\\bm\{x\}\_\{t\}to a 128\-dimensional representation for downstream bandit algorithms\. The heads are trained offline using Adam with learning rate10−410^\{\-4\}, MSE for cost prediction, andL1L\_\{1\}/Huber\-style losses for accuracy prediction and propagation\. Since we sweep large cost sensitivities up toρ=1000\\rho=1000, we feed the learner a bounded utility signalr¯t,it=clip​\(rt,it,0,1\)\\bar\{r\}\_\{t,i\_\{t\}\}=\\mathrm\{clip\}\(r\_\{t,i\_\{t\}\},0,1\)for numerical stability\. Finally, althoughROcan produce surrogate utilities for all graph\-neighbor arms, we only incorporate pseudo\-observations for a pruned subset selected by an IQR rule on predicted delta magnitudes, retaining armjjonly if\|δ^t,j\|\>Q3\+κ​IQR\|\\widehat\{\\delta\}\_\{t,j\}\|\>Q\_\{3\}\+\\kappa\\,\\mathrm\{IQR\}withκ=1\.5\\kappa=1\.5\. This acts as a conservative sparsification guard without changing the underlying feedback model\.

##### Efficient Computation of𝒑t\\bm\{p\}\_\{t\}\(Line 8 of Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\):

Line 8 of Algorithm[1](https://arxiv.org/html/2607.09015#alg1)requires solving for the sampling distribution𝒑t∈Δ​\(K\)\\bm\{p\}\_\{t\}\\in\\Delta\(K\)that minimizes the objectiveϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)\. Rather than optimizing this objective in its original form, we follow the convex reformulation of\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\], which converts the problem into an equivalent convex program over\(𝒑,z\)\(\\bm\{p\},z\)that can be solved efficiently with standard solvers at each round, as stated in the following theorem\.

###### Theorem D\.1\(Theorem 3\.6\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\]\)\.

Solvingarg⁡min𝐩∈Δ​\(K\)⁡dec¯γ​\(𝐩;𝐟^,𝐱,𝐆\)\\arg\\min\_\{\\bm\{p\}\\in\\Delta\(K\)\}\\overline\{\\mathrm\{dec\}\}\_\{\\gamma\}\(\\bm\{p\};\\hat\{\\bm\{f\}\},\\bm\{x\},\\bm\{G\}\)is equivalent to solving the following convex optimization problem:

min𝒑∈Δ​\(K\),z\\displaystyle\\min\_\{\\bm\{p\}\\in\\Delta\(K\),\\,z\}𝒑⊤​𝒇^\+z\\displaystyle\\bm\{p\}^\{\\top\}\\hat\{\\bm\{f\}\}\+z\(5\)s\.t\.∀a∈\[K\]:1γ​‖𝒑−𝒆a‖diag​\(𝑮⊤​𝒑\)−12≤f^​\(𝒙,a\)\+z,\\displaystyle\\forall a\\in\[K\]:\\frac\{1\}\{\\gamma\}\\left\\\|\\bm\{p\}\-\\bm\{e\}\_\{a\}\\right\\\|^\{2\}\_\{\\mathrm\{diag\}\(\\bm\{G\}^\{\\top\}\\bm\{p\}\)^\{\-1\}\}\\leq\\hat\{f\}\(\\bm\{x\},a\)\+z,𝑮⊤​𝒑≻𝟎,\\displaystyle\\bm\{G\}^\{\\top\}\\bm\{p\}\\succ\\bm\{0\},where𝐟^\\hat\{\\bm\{f\}\}is shorthand for𝐟^​\(𝐱,⋅\)∈ℝK\\hat\{\\bm\{f\}\}\(\\bm\{x\},\\cdot\)\\in\\mathbb\{R\}^\{K\},𝐞a\\bm\{e\}\_\{a\}is theaa\-th standard basis vector,≻\\succdenotes element\-wise strict positivity, andz∈ℝz\\in\\mathbb\{R\}is an auxiliary slack variable\.

We refer readers to\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\]for the proof\. Although Theorem[D\.1](https://arxiv.org/html/2607.09015#A4.Thmtheorem1)is stated in terms of loss scoresf^​\(𝒙t,j\)\\hat\{f\}\(\\bm\{x\}\_\{t\},j\), our bandit models produce reward predictionsr^t,j∈\[0,1\]\\hat\{r\}\_\{t,j\}\\in\[0,1\]\. We therefore apply the theorem with the transformation,f^​\(𝒙t,j\)=1−r^t,j\\hat\{f\}\(\\bm\{x\}\_\{t\},j\)\\;=\\;1\-\\hat\{r\}\_\{t,j\}\. In particular, in the linear caser^t,j=𝒙t⊤​𝜽^t,j\\hat\{r\}\_\{t,j\}=\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,j\}, while in the neural caser^t,j=f𝜽^t​\(𝒙t,j\)\\hat\{r\}\_\{t,j\}=f\_\{\\hat\{\\bm\{\\theta\}\}\_\{t\}\}\(\\bm\{x\}\_\{t\},j\)denotes the prediction of the corresponding neural reward model\. Thus,𝒇^​\(𝒙t,⋅\)∈ℝK\\hat\{\\bm\{f\}\}\(\\bm\{x\}\_\{t\},\\cdot\)\\in\\mathbb\{R\}^\{K\}is obtained component\-wise from𝒓^t​\(𝒙t,⋅\)∈ℝK\\hat\{\\bm\{r\}\}\_\{t\}\(\\bm\{x\}\_\{t\},\\cdot\)\\in\\mathbb\{R\}^\{K\}via𝒇^t=𝟏−𝒓^t\\hat\{\\bm\{f\}\}\_\{t\}=\\mathbf\{1\}\-\\hat\{\\bm\{r\}\}\_\{t\}\. Since𝒑∈Δ​\(K\)\\bm\{p\}\\in\\Delta\(K\)implies𝒑⊤​𝟏=1\\bm\{p\}^\{\\top\}\\mathbf\{1\}=1, this substitution only changes the objective by an additive constant \(absorbed into the slack variablezz\) and leaves the optimizer𝒑t\\bm\{p\}\_\{t\}unchanged\. We use Theorem[D\.1](https://arxiv.org/html/2607.09015#A4.Thmtheorem1)to compute𝒑t=arg⁡min𝒑∈Δ​\(K\)⁡ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\\bm\{p\}\_\{t\}=\\arg\\min\_\{\\bm\{p\}\\in\\Delta\(K\)\}\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)in Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\.

## Appendix EAdditional Graphs and Results

### E\.1Reward Mixing vs Prediction Mixing \(CABS\-C vs CABS\-D\)

Table[7](https://arxiv.org/html/2607.09015#A5.T7)presents the same ablation study on Open LLM LB V2\[[21](https://arxiv.org/html/2607.09015#bib.bib59)\]\. The overall pattern is consistent with the findings on RouterBench\[[25](https://arxiv.org/html/2607.09015#bib.bib16)\]and SPROUT\[[41](https://arxiv.org/html/2607.09015#bib.bib48)\]as shown in Section[5\.2](https://arxiv.org/html/2607.09015#S5.SS2)\. Across most cost regimes, the decoupled variant \(CABS\-D\) achieves comparable or improved utility relative to the coupled variant \(CABS\-C\), and generally attains lower regret in the linear setting\. On Open LLM LB V2, the differences are smaller but remain directionally similar, with CABS\-D typically matching or slightly outperforming CABS\-C\. Overall, these results support the conclusion drawn in the main text that decoupling reward learning from surrogate prediction provides a stable and effective alternative to direct reward mixing\.

Table 7:Average utility \(higher the better\) and Average Regret \(lower the better\) across cost regimes on Open LLM LB V2 datasetTable 8:Utilities across cost regimes and datasets using all\-MiniLM\-L6\-v2\[[27](https://arxiv.org/html/2607.09015#bib.bib72)\]embeddings\.
### E\.2Encoder Robustness

We repeat our experiments with a second, widely used text embedding model \(all\-MiniLM\-L6\-v2\[[27](https://arxiv.org/html/2607.09015#bib.bib72)\]\) in addition to mDeBERTaV3\-base\[[24](https://arxiv.org/html/2607.09015#bib.bib36)\]\. Across datasets, method rankings and improvements over bandit baselines with respect to utility is consistent \(see Table[8](https://arxiv.org/html/2607.09015#A5.T8)\), indicating that our conclusions do not depend on a specific encoder choice\. Absolute utilities shift slightly, with the largest change on RouterBench in the high\-cost regime; notably, the full\-feedback upper bound decreases similarly, suggesting the shift is driven by representation\-limited separability rather than algorithmic instability\.

### E\.3Learning Dynamics & Accuracy vs Cost Trade\-offs

Figure[4](https://arxiv.org/html/2607.09015#A5.F4)extends the learning\-dynamics analysis of Section[5\.5](https://arxiv.org/html/2607.09015#S5.SS5)to RouterBench and SPROUT, reporting relative cumulative regret normalized by LinUCB across low \(ρ≤300\\rho\\leq 300\), mid \(300<ρ<800300<\\rho<800\), and high \(ρ≥800\\rho\\geq 800\) cost regimes\. Consistent with the Open LLM Leaderboard v2 results in the main text, CABS\-D achieves uniformly lower relative cumulative regret than standard bandit baselines in most regimes, and the separation typically appears early in the horizon, indicating faster learning from surrogate feedback rather than solely an asymptotic gain\. The trends are especially stable in the mid\-cost regime, where the objective most strongly couples accuracy and cost and thus benefits from exploiting inter\-arm correlations\. As expected, full\-feedback variants remain an optimistic upper bound and provide a reference for the achievable regret reduction under complete feedback\. Further, Figure[6](https://arxiv.org/html/2607.09015#A5.F6)shows relative cumulative regret graphs for Neural variants where we observe similar trends as that of linear variants\.

Figure[5](https://arxiv.org/html/2607.09015#A5.F5)provides the analogous accuracy–cost Pareto frontiers for neural online\-learning variants\. The qualitative behavior mirrors the linear case: correlation\-aware surrogate methods shift the frontier outward, achieving higher accuracy at comparable cost or reducing cost for a fixed accuracy, with the largest advantages occurring in regimes where cost sensitivity meaningfully constrains the policy\.

\(a\) RouterBench![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/routerbench_regimes_relcumreg.png)

\(b\) SPROUT![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/sprout_regimes_relcumreg.png)

Figure 4:Relative Cumulative regrets with respect to LinUCB for other linear online learning methods on RouterBench \(top\) and SPROUT \(bottom\) dataset\.![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/Accuracy_vs_Cost-Neural-OPEN_LLM_LB_V2.png)\(a\)
![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/Accuracy_vs_Cost-Neural-ROUTERBENCH.png)\(b\)
![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/Accuracy_vs_Cost-Neural-SPROUT.png)\(c\)

Figure 5:Accuracy vs cost Pareto Frontier curves across datasets on Neural Online Learning models\.\(a\) Open LLM Leaderboard v2![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/open_llm_lb_v2_neural_regimes_relcumreg.png)\(b\) RouterBench![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/routerbench_neural_regimes_relcumreg.png)\(c\) SPROUT![Refer to caption](https://arxiv.org/html/2607.09015v1/new_variant_figs/sprout_neural_regimes_relcumreg.png)

Figure 6:Relative Cumulative regrets with respect to NeuralUCB for other neural online learning methods on Open LLM Leaderboard V2 dataset \(top\), RouterBench \(middle\) and SPROUT \(bottom\)\.

## Appendix FThe Technical Proofs

For clarity, we decompose the analysis of regret of proposed algorithms into three components, which progressively build toward our final guarantee\. In particular, for the ease of reading, we split our algorithmic analysis into three parts as follows:

1. 1\.Baseline: Contextual BanditIn Subsection[F\.1](https://arxiv.org/html/2607.09015#A6.SS1), we first present a classical contextual bandit with regret boundO~​\(K​T​RegSq​\(T\)\)\\widetilde\{O\}\\\!\\left\(\\sqrt\{KT\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\\right\)\. In particular for the linear case, we getO~​\(d​K​T​log⁡\(Td\)\)\\widetilde\{O\}\\\!\\left\(\\sqrt\{dKT\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\\right\)\.
2. 2\.Correlation\-Aware Bandits with Surrogates — Coupled \(CABS\-C\)\.We next analyze our proposed graph\-feedback algorithm with noisy surrogate rewards in Subsection[F\.2](https://arxiv.org/html/2607.09015#A6.SS2)\. When feedback graphGtG\_\{t\}has independence number no greater thanα\\alpha, the regret satisfies O~​\(α​T​RegSq​\(T\)\+εn​α​K​T\)\.\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\alpha KT\}\\right\)\.In particular, for the linear case, when exactlymmsurrogate rewards are observed each round, this becomes O~​\(d​Km\+1​T​log⁡\(Td\)\+εn​K2m\+1​T\)\.\\widetilde\{O\}\\\!\\left\(\\sqrt\{d\\frac\{K\}\{m\+1\}T\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\frac\{K^\{2\}\}\{m\+1\}T\}\\right\)\.demonstrating a significant improvement by scale of roughly1/m1/mas long as the noise from ML\-predicted rewardsεn\\varepsilon\_\{n\}is well\-bounded\.
3. 3\.Correlation\-Aware Bandits with Surrogates — Decoupled \(CABS\-D\)Finally, in Subsection[F\.3](https://arxiv.org/html/2607.09015#A6.SS3)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, O~​\(min⁡\{K​T​RegSq​\(T\),α​T​RegSq​\(T\)\+εn​α​K​T\}\)\\widetilde\{O\}\\\!\\left\(\\min\\left\\\{\\sqrt\{KT\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\},\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\alpha KT\}\\right\\\}\\right\)For the linear case, when exactlymmsurrogate rewards are observed each round, this becomes O~​\(min⁡\{d​K​T​log⁡\(Td\),d​Km\+1​T​log⁡\(Td\)\+εn​K2m\+1​T\}\)\\widetilde\{O\}\\\!\\left\(\\min\\left\\\{\\sqrt\{dKT\\log\\left\(\\frac\{T\}\{d\}\\right\)\},\\sqrt\{d\\frac\{K\}\{m\+1\}T\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\frac\{K^\{2\}\}\{m\+1\}T\}\\right\\\}\\right\)

### F\.1Contextual bandits Regret Bounds

Algorithm 3SquareCB \(Reward Form; adapted from\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]\)1:Parameters:learning rate

γ\>0\\gamma\>0, exploration parameter

μ\>0\\mu\>0
2:Input:online regression oracleRSproducing predictors

f^t\\hat\{f\}\_\{t\}
3:for

t=1,…,Tt=1,\\dots,Tdo

4:Receive context

𝒙t\\bm\{x\}\_\{t\}
5:// Compute oracle’s reward predictions

6:foreach arm

i∈\[K\]i\\in\[K\]do

7:

r^t,i←f^t​\(𝒙t,i\)\\hat\{r\}\_\{t,i\}\\leftarrow\\hat\{f\}\_\{t\}\(\\bm\{x\}\_\{t\},i\)
8:endfor

9:

bt←arg⁡maxi∈\[K\]⁡r^t,ib\_\{t\}\\leftarrow\\arg\\max\_\{i\\in\[K\]\}\\hat\{r\}\_\{t,i\}
10:foreach arm

i∈\[K\]∖\{bt\}i\\in\[K\]\\setminus\\\{b\_\{t\}\\\}do

11:

pt,i←1μ\+γ​\(r^t,bt−r^t,i\)p\_\{t,i\}\\leftarrow\\frac\{1\}\{\\mu\+\\gamma\\big\(\\hat\{r\}\_\{t,b\_\{t\}\}\-\\hat\{r\}\_\{t,i\}\\big\)\}
12:endfor

13:

pt,bt←1−∑i≠btpt,ip\_\{t,b\_\{t\}\}\\leftarrow 1\-\\sum\_\{i\\neq b\_\{t\}\}p\_\{t,i\}
14:Sample

it∼𝒑ti\_\{t\}\\sim\\bm\{p\}\_\{t\}and observe reward

rt,itr\_\{t,i\_\{t\}\}
15:UpdateRSwith example

\{\(𝒙t,rt,it\)\}\\big\\\{\(\\bm\{x\}\_\{t\},r\_\{t,i\_\{t\}\}\)\\big\\\}
16:endfor

We begin with the SquareCB\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]algorithm, which reduces contextual bandits to online regression\. We state the modified algorithm that works on rewards instead of losses in Algorithm[3](https://arxiv.org/html/2607.09015#alg3)\. We provide its regret guarantee for completeness and refer the reader to\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]for the proof\.

###### Theorem F\.1\(Theorem 1\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\]\)\.

Suppose Assumption[4\.2](https://arxiv.org/html/2607.09015#S4.Thmtheorem2)holds\. Then for anyδ\>0\\delta\>0, by settingμ=K\\mu=Kandγ=K​T/\(RegSq​\(T\)\+log⁡\(2​δ−1\)\)\\gamma=\\sqrt\{KT/\\left\(\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\+\\log\(2\\delta^\{\-1\}\)\\right\)\},SquareCBguarantees that with probability at least1−δ1\-\\delta,

RegCB​\(T\)≤4​K​T⋅RegSq​\(T\)\+8​K​T​log⁡\(2​δ−1\)=O~​\(K​T​RegSq​\(T\)\)\.\\mathrm\{Reg\}\_\{\\mathrm\{CB\}\}\(T\)\\leq 4\\sqrt\{KT\\cdot\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+8\\sqrt\{KT\\log\(2\\delta^\{\-1\}\)\}=\\widetilde\{O\}\\\!\\left\(\\sqrt\{KT\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\\right\)\.\(8\)

###### Corollary F\.2\(Linear Regression Oracle\)\.

Suppose the regression oracle is linear, i\.e\.,f^​\(𝐱t,it\)=𝐱t⊤​𝛉it\\hat\{f\}\(\\bm\{x\}\_\{t\},i\_\{t\}\)=\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}\_\{i\_\{t\}\}, where𝐱t∈ℝd\\bm\{x\}\_\{t\}\\in\\mathbb\{R\}^\{d\}with‖𝐱‖2≤1\\\|\\bm\{x\}\\\|\_\{2\}\\leq 1and𝛉it∈ℝd\\bm\{\\theta\}\_\{i\_\{t\}\}\\in\\mathbb\{R\}^\{d\}with‖𝛉it‖2≤1\\\|\\bm\{\\theta\}\_\{i\_\{t\}\}\\\|\_\{2\}\\leq 1\. ChoosingSqAlgas the Vovk–Azoury–Warmuth forecaster\[[47](https://arxiv.org/html/2607.09015#bib.bib73),[8](https://arxiv.org/html/2607.09015#bib.bib74)\], which satisfiesRegSq​\(T\)≤d​log⁡\(Td\)\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\\leq d\\log\\left\(\\frac\{T\}\{d\}\\right\), Theorem[F\.1](https://arxiv.org/html/2607.09015#A6.Thmtheorem1)implies

RegCB​\(T\)≤4​d​K​T​log⁡\(Td\)\+8​K​T​log⁡\(2​δ−1\)=O~​\(d​K​T​log⁡\(Td\)\)\.\\mathrm\{Reg\}\_\{\\mathrm\{CB\}\}\(T\)\\leq 4\\sqrt\{dKT\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\+8\\sqrt\{KT\\log\(2\\delta^\{\-1\}\)\}=\\widetilde\{O\}\\\!\\left\(\\sqrt\{dKT\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\\right\)\.

### F\.2Correlation Aware Bandits with Surrogates Coupled \(CABS\-C\)

In this section, we present algorithmic analysis for Contextual Bandits with Noisy Graph Feedback with regret bound depending on a noise factor,O~​\(α​T​RegSq​\(T\)\+εn​α​K​T\)\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\alpha KT\}\\right\)\. In our main paper, we present this as Correlation Aware Bandits with Surrogates Coupled \(CABS\-C\), Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\. We include here all intermediate lemmas and derivations to ensure completeness and reproducibility of the analysis\.

#### F\.2\.1High Level Proof Sketch

The proof of Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7)proceeds in three main steps\. First, we decompose the total expected regret into an algorithmic optimization term \(sometimes referred to as thenon\-bias term\), the cumulative regret of the regression oracleRegSq​\(T\)\\mathrm\{Reg\_\{Sq\}\}\(T\), and an expected bias term𝔼​\[ℬT\]\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]that accounts for the misspecification of the surrogate rewards\. Next, we further decompose this expected bias term into two distinct components: a regression\-propagation error and an observation noise term\. We continue by systematically bounding each piece of this decomposition: the optimization term is bounded using a minimax argument over the action probabilities, the regression\-propagation error is bounded using the Cauchy\-Schwarz inequality and properties of harmonic sums, and the observation noise is bounded using the Azuma\-Hoeffding inequality applied to the bounded martingale difference sequence\. Combining these individual bounds and tuning the learning rate parameterγ=α​T/R​e​gS​q​\(T\)\\gamma=\\sqrt\{\\alpha T/Reg\_\{Sq\}\(T\)\}to balance the components yields the final stated regret bound ofO~​\(α​T​R​e​gS​q​\(T\)\+ϵn​α​K​T\)\\tilde\{O\}\(\\sqrt\{\\alpha T~Reg\_\{Sq\}\(T\)\}\+\\epsilon\_\{n\}\\sqrt\{\\alpha KT\}\)\.

Regret Bound for Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\(CABS\-C\)

##### Notation

Let

nt,jn\_\{t,j\}be the number of times arm

jjhas been observed up to \(and including\) round

tt, and

𝒯t​\(j\)=\{τ≤t:𝒜τ,\(iτ,j\)=1\}\\mathcal\{T\}\_\{t\}\(j\)=\\\{\\tau\\leq t:\\mathcal\{A\}\_\{\\tau,\(i\_\{\\tau\},j\)\}=1\\\}\. Finally denote

Δτ,j:=\|𝒙τ⊤​𝜽^τ,k−𝒙τ⊤​𝜽k∗\|\\Delta\_\{\\tau,j\}:=\|\\bm\{x\}\_\{\\tau\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{\\tau,k\}\-\\bm\{x\}\_\{\\tau\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{k\}\|\.

To prove Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7), we first introduce the following auxiliary lemmas regarding the regret and bias decomposition\. We continue by introducing lemmas to individually bound each term of the decomposition\. Finally, we combine the results of all these lemmas in the final proof of Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7)\.

###### Lemma F\.3\(Regret Decomposition\)\.

For anyγ\>0\\gamma\>0, we may decompose the regret of Algorithm[1](https://arxiv.org/html/2607.09015#alg1)as the following:

𝔼​\[RegT\]≤T⋅ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\+γ4​RegSq​\(T\)\+𝔼​\[ℬT\]\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\;\\leq\\;T\\cdot\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)\\;\+\\;\\frac\{\\gamma\}\{4\}\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\\;\+\\;\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\.\(2\)
###### Proof\.

This follows from the decomposition in Theorem 3\.3 of\[[19](https://arxiv.org/html/2607.09015#bib.bib44)\], plus an additive bias term to account for potential misspecification of surrogate rewards ∎

###### Lemma F\.4\(Bias Decomposition\)\.

Given the regret decomposition provided in Equation[2](https://arxiv.org/html/2607.09015#A6.E2), we may decompose the expected bias term𝔼​\[ℬT\]\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]of Algorithm[1](https://arxiv.org/html/2607.09015#alg1)as

𝔼​\[ℬT\]=∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]\+∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|,\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]=\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\+\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|,wherewt,j=pt,j𝐀t,\(:,j\)⊤​𝐩t\.w\_\{t,j\}=\\frac\{p\_\{t,j\}\}\{\\bm\{A\}\_\{t,\(:,j\)\}^\{\\top\}\\bm\{p\}\_\{t\}\}\.The first term corresponds to what we term the regression\-propagation error, and the second term captures the contribution of observation noise\.

###### Proof\.

The term𝔼​\[ℬT\]\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]captures the expected cumulative regret induced by bias in the surrogate reward estimates\. Let us begin by defininget,j:=\|bj−b^t,j\|e\_\{t,j\}:=\|b\_\{j\}\-\\hat\{b\}\_\{t,j\}\|, wherebjb\_\{j\}is the true bias of armjj, andb^t,j\\hat\{b\}\_\{t,j\}is the estimated bias of armjjat roundtt\. We may state the cumulative regret as

𝔼​\[ℬT\]=∑t=1T𝔼​\[∑j:At,\(it,j\)=1et,j\]\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]=\\sum\_\{t=1\}^\{T\}\\,\\mathbb\{E\}\\left\[\\sum\_\{j:A\_\{t,\(i\_\{t\},j\)\}=1\}e\_\{t,j\}\\right\]At roundtt, the instantaneous contribution of bias to the regret is

\[∑j:At,\(it,j\)=1et,j\]=∑j=1Kpt,j𝑨t,\(:,j\)⊤​𝒑t​et,j\\left\[\\sum\_\{j:A\_\{t,\(i\_\{t\},j\)\}=1\}e\_\{t,j\}\\right\]=\\sum\_\{j=1\}^\{K\}\\frac\{p\_\{t,j\}\}\{\\bm\{A\}\_\{t,\(:,j\)\}^\{\\top\}\\bm\{p\}\_\{t\}\}\\,e\_\{t,j\}We use the definition ofwt,jw\_\{t,j\}to rewrite this as

𝔼​\[ℬT\]:=∑t=1T∑j=1Kwt,j​et,j\.\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\\;:=\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}w\_\{t,j\}\\,e\_\{t,j\}\.We now make explicit the structure ofet,je\_\{t,j\}\. Recall that the bias estimateb^t,j\\hat\{b\}\_\{t,j\}is maintained as a running average over past observations of armjj\. By definition of the running average from Algorithm[1](https://arxiv.org/html/2607.09015#alg1),

b^t,j=1nt,j​∑τ∈𝒯t​\(j\)\(sτ,j−𝒙τ⊤​𝜽^τ,j\)\.\\hat\{b\}\_\{t,j\}\\;=\\;\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\left\(s\_\{\\tau,j\}\-\\bm\{x\}\_\{\\tau\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{\\tau,j\}\\right\)\.Substituting the reward model

sτ,j=𝒙τ⊤​𝜽j∗\+bj\+ξτ,j,s\_\{\\tau,j\}\\;=\\;\\bm\{x\}\_\{\\tau\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{j\}\+b\_\{j\}\+\\xi\_\{\\tau,j\},we obtain

b^t,j=bj\+1nt,j​∑τ∈𝒯t​\(j\)\(𝒙t⊤​𝜽^τ,j−𝒙τ⊤​𝜽j∗\)\+1nt,j​∑τ∈𝒯t​\(j\)ξτ,j\.\\hat\{b\}\_\{t,j\}=b\_\{j\}\+\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\left\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{\\tau,j\}\-\\bm\{x\}\_\{\\tau\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{j\}\\right\)\+\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\.Plugging this into the definition ofet,je\_\{t,j\}yields

et,j\\displaystyle e\_\{t,j\}=\|1nt,j​∑τ∈𝒯t​\(j\)\(𝒙t⊤​𝜽^τ,j−𝒙τ⊤​𝜽j∗\)\+1nt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\displaystyle=\\left\|\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\left\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{\\tau,j\}\-\\bm\{x\}\_\{\\tau\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{j\}\\right\)\+\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|≤\|1nt,j​∑τ∈𝒯t​\(j\)\(𝒙t⊤​𝜽^τ,j−𝒙τ⊤​𝜽j∗\)\|\+\|1nt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\displaystyle\\leq\\left\|\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\left\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{\\tau,j\}\-\\bm\{x\}\_\{\\tau\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{j\}\\right\)\\right\|\+\\left\|\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|Recall,

Δτ,j:=\|𝒙t⊤​𝜽^τ,j−𝒙τ⊤​𝜽j∗\|,\\Delta\_\{\\tau,j\}:=\|\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{\\tau,j\}\-\\bm\{x\}\_\{\\tau\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{j\}\|,After plugging this into our previous equation and summing over all roundsTT, this can be written compactly as

𝔼​\[ℬT\]≤∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]\+∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|,\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\\leq\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\+\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|,
∎

###### Lemma F\.5\(Bounding the Non\-Bias Terms\)\.

Suppose the feedback graphGtG\_\{t\}is deterministic with independence number no more thanα\\alpha\. Then Algorithm[1](https://arxiv.org/html/2607.09015#alg1)guarantees that

ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)≤O​\(α​log⁡\(K​γ\)γ\)\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)\\leq O\\\!\\left\(\\frac\{\\alpha\\log\(K\\gamma\)\}\{\\gamma\}\\right\)
###### Proof\.

The following proof primarily follows from\[[54](https://arxiv.org/html/2607.09015#bib.bib11)\]\(Theorem 3\.2\)\. We include a summarized version below for completeness\. Let us first rewriteϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)in terms of losses:

ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\):=supi∗∈\[K\]𝜽∗∈ℝ\+K×d𝔼i∼p​\[𝒙t⊤​𝜽i∗−𝒙t⊤​𝜽i∗∗−γ4​∑k:At,\(i,k\)=1𝔼​\[At,\(i,k\)\]​\(𝒙t⊤​𝜽^t,k−𝒙t⊤​𝜽k∗\)2\]\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\):=\\sup\_\{\\begin\{subarray\}\{c\}i^\{\*\}\\in\[K\]\\\\ \\bm\{\\theta\}^\{\*\}\\in\\mathbb\{R\}\_\{\+\}^\{K\\times d\}\\end\{subarray\}\}\\hskip 5\.0pt\\mathbb\{E\}\_\{i\\sim p\}\\left\[\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i^\{\*\}\}\-\\frac\{\\gamma\}\{4\}\\sum\_\{k:A\_\{t,\(i,k\)\}=1\}\\mathbb\{E\}\[A\_\{t,\(i,k\)\}\]\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,k\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{k\}\)^\{2\}\\right\]Direct calculation shows that for alli∗∈\[K\]i^\{\*\}\\in\[K\],

𝔼i∼p​\[𝒙t⊤​𝜽i∗−𝒙t⊤​𝜽i∗∗−γ4​∑k:At,\(i,k\)=1𝔼​\[At,\(i,k\)\]​\(𝒙t⊤​𝜽^t,k−𝒙t⊤​𝜽k∗\)2\]\\displaystyle\\mathbb\{E\}\_\{i\\sim p\}\\left\[\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i^\{\*\}\}\-\\frac\{\\gamma\}\{4\}\\sum\_\{k:A\_\{t,\(i,k\)\}=1\}\\mathbb\{E\}\[A\_\{t,\(i,k\)\}\]\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,k\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{k\}\)^\{2\}\\right\]=∑i=1Kpt,i​𝒙t⊤​𝜽i∗−𝒙t⊤​𝜽i∗∗−γ4​∑i=1K∑k:At,\(k,i\)=1pt,k​\(𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽i∗\)2\\displaystyle=\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i^\{\*\}\}\-\\frac\{\\gamma\}\{4\}\\sum\_\{i=1\}^\{K\}\\sum\_\{k:A\_\{t,\(k,i\)\}=1\}\\,p\_\{t,k\}\\,\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\)^\{2\}
We can take the gradient overf∗​\(𝒙t,⋅\)=𝒙t⊤​𝜽⋅∗f^\{\*\}\(\\bm\{x\}\_\{t\},\\cdot\)=\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{\\cdot\}to get

supf∗∈\(𝒳×\[K\]→ℝ\)\[∑i=1Kpt,i​𝒙t⊤​𝜽i∗−𝒙t⊤​𝜽i∗∗−γ4​∑i=1K∑k:At,\(k,i\)=1pt,k​\(𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽i∗\)2\]\\displaystyle\\sup\_\{f^\{\*\}\\in\(\\mathcal\{X\}\\times\[K\]\\rightarrow\\mathbb\{R\}\)\}\\left\[\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i^\{\*\}\}\-\\frac\{\\gamma\}\{4\}\\sum\_\{i=1\}^\{K\}\\sum\_\{k:A\_\{t,\(k,i\)\}=1\}\\,p\_\{t,k\}\\,\(\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\bm\{\\theta\}^\{\*\}\_\{i\}\)^\{2\}\\right\]=∑i=1Kpt,i​𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽^t,i∗\+1γ​‖𝒑t−𝒆i∗‖diag​\(𝑾t\)−12\\displaystyle=\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i^\{\*\}\}\+\\frac\{1\}\{\\gamma\}\\\|\\bm\{p\}\_\{t\}\-\\bm\{e\}\_\{i^\{\*\}\}\\\|\_\{\\mathrm\{diag\}\(\\bm\{W\}\_\{t\}\)^\{\-1\}\}^\{2\}WhereWt,i=∑k:At,\(k,i\)=1pt,kW\_\{t,i\}=\\sum\_\{k:A\_\{t,\(k,i\)\}=1\}\\,p\_\{t,k\}\. Next, let us consider the following minimax form over𝒑t∈Δ​\(\[K\]\)\\bm\{p\}\_\{t\}\\in\\Delta\(\[K\]\)andi∗∈\[K\]i^\{\*\}\\in\[K\]:

inf𝒑t∈Δ​\(\[K\]\)supi∗∈\[K\]\{∑i=1Kpt,i​𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽^t,i∗\+1γ‖𝒑t−𝒆i∗∥diag​\(𝑾t\)−12\}\\displaystyle\\inf\_\{\\bm\{p\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\sup\_\{i^\{\*\}\\in\[K\]\}\\,\\left\\\{\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i^\{\*\}\}\+\\frac\{1\}\{\\gamma\}\\\|\\bm\{p\}\_\{t\}\-\\bm\{e\}\_\{i^\{\*\}\}\\\|\_\{\\mathrm\{diag\}\(\\bm\{W\}\_\{t\}\)^\{\-1\}\}^\{2\}\\right\\\}=min𝒑t∈Δ​\(\[K\]\)⁡maxi∗∈\[K\]⁡\{∑i=1Kpt,i​𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽^t,i∗\+1γ​∑i≠i∗pt,i2Wt,i\+1γ​\(1−pt,i∗\)2γ​Wt,i\}\\displaystyle=\\min\_\{\\bm\{p\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\max\_\{i^\{\*\}\\in\[K\]\}\\,\\left\\\{\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i^\{\*\}\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i\\neq i^\{\*\}\}\\frac\{p\_\{t,i\}^\{2\}\}\{W\_\{t,i\}\}\+\\frac\{1\}\{\\gamma\}\\frac\{\(1\-p\_\{t,i^\{\*\}\}\)^\{2\}\}\{\\gamma\\,W\_\{t,i\}\}\\right\\\}\(3\)=max𝒒t∈ΔK⁡min𝒑t∈ΔK⁡\{∑i=1Kpt,i​𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽^t,i∗\+1γ​∑i=1Kpt,i2​\(1−qt,i\)Wt,i\+∑i=1Kqt,i​\(1−pt,i\)2γ​Wt,i\}\\displaystyle=\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\_\{K\}\}\\,\\min\_\{\\bm\{p\}\_\{t\}\\in\\Delta\_\{K\}\}\\,\\left\\\{\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i^\{\*\}\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,i\}^\{2\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}\+\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\(1\-p\_\{t,i\}\)^\{2\}\}\{\\gamma\\,W\_\{t,i\}\}\\right\\\}where the last inequality is due to the fact that Equation \([3](https://arxiv.org/html/2607.09015#A6.E3)\) is convex inp∈Δ​\(\[K\]\)p\\in\\Delta\(\[K\]\)and Sion’s minimax theorem\. Choosept,i=\(1−1γ\)​qt,i\+1γ​Kp\_\{t,i\}=\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,i\}\+\\frac\{1\}\{\\gamma K\}for alli∈\[K\]i\\in\[K\]\. Due to Assumption[4\.3](https://arxiv.org/html/2607.09015#S4.Thmtheorem3), all nodes in the feedback graphGtG\_\{t\}have a self\-loop\. This allows us to upper bound the quantity as

=max𝒒t∈Δ​\(\[K\]\)⁡min𝒑t∈ΔK⁡\{∑i=1Kpt,i​𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽^t,i∗\+1γ​∑i=1Kpt,i2​\(1−qt,i\)Wt,i\+∑i=1Kqt,i​\(1−pt,i\)2γ​Wt,i\}\\displaystyle=\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\min\_\{\\bm\{p\}\_\{t\}\\in\\Delta\_\{K\}\}\\,\\left\\\{\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i^\{\*\}\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,i\}^\{2\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}\+\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\(1\-p\_\{t,i\}\)^\{2\}\}\{\\gamma\\,W\_\{t,i\}\}\\right\\\}≤max𝒒t∈Δ​\(\[K\]\)⁡\{2γ\+1γ​∑i=1K\(\(1−1γqt,i\+1γ​K\)2\(1−qt,i\)\+qt,i\(1−\(1−1γ\)qt,i−1γ​K\)2Wt,i\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\left\\\{\\frac\{2\}\{\\gamma\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{\\left\(\(1\-\\frac\{1\}\{\\gamma\}q\_\{t,i\}\+\\frac\{1\}\{\\gamma K\}\\right\)^\{2\}\(1\-q\_\{t,i\}\)\+q\_\{t,i\}\\left\(1\-\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,i\}\-\\frac\{1\}\{\\gamma K\}\\right\)^\{2\}\}\{W\_\{t,i\}\}\\right\\\}≤max𝒒t∈Δ​\(\[K\]\)⁡\{2γ\+1γ​∑i=1K2​\(\(1−1γ\)2​qt,i2\+1γ2​K2\)​\(1−qt,i\)\+qt,i​\(1−\(1−1γ\)​qt,i\)2Wt,i\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\left\\\{\\frac\{2\}\{\\gamma\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{2\\left\(\(1\-\\frac\{1\}\{\\gamma\}\)^\{2\}q\_\{t,i\}^\{2\}\+\\frac\{1\}\{\\gamma^\{2\}K^\{2\}\}\\right\)\(1\-q\_\{t,i\}\)\+q\_\{t,i\}\\left\(1\-\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,i\}\\right\)^\{2\}\}\{W\_\{t,i\}\}\\right\\\}≤max𝒒t∈Δ​\(\[K\]\)⁡\{2γ\+2γ2\+1γ​∑i=1K2​qt,i2​\(1−qt,i\)\+2​qt,i​\(1−qt,i\)2\+2​qt,i3γ2Wt,i\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\left\\\{\\frac\{2\}\{\\gamma\}\+\\frac\{2\}\{\\gamma^\{2\}\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{2q\_\{t,i\}^\{2\}\(1\-q\_\{t,i\}\)\+2q\_\{t,i\}\(1\-q\_\{t,i\}\)^\{2\}\+\\frac\{2q\_\{t,i\}^\{3\}\}\{\\gamma^\{2\}\}\}\{W\_\{t,i\}\}\\right\\\}SinceWt,i=∑k:At,\(k,i\)=1pt,k≥1γ​KW\_\{t,i\}=\\sum\_\{k:A\_\{t,\(k,i\)\}=1\}\\,p\_\{t,k\}\\,\\geq\\frac\{1\}\{\\gamma K\}for alli∈\[K\]i\\in\[K\]We can further bound this by saying

≤max𝒒t∈Δ​\(\[K\]\)⁡\{2γ\+2γ2\+1γ​∑i=1K2​qt,i2​\(1−qt,i\)\+2​qt,i​\(1−qt,i\)2\+2​qt,i3γ2Wt,i\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\left\\\{\\frac\{2\}\{\\gamma\}\+\\frac\{2\}\{\\gamma^\{2\}\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{2q\_\{t,i\}^\{2\}\(1\-q\_\{t,i\}\)\+2q\_\{t,i\}\(1\-q\_\{t,i\}\)^\{2\}\+\\frac\{2q\_\{t,i\}^\{3\}\}\{\\gamma^\{2\}\}\}\{W\_\{t,i\}\}\\right\\\}≤max𝒒t∈Δ​\(\[K\]\)⁡\{2γ\+2γ2\+2γ​∑i=1Kqt,i​\(1−qt,i\)Wt,i\+2γ3​∑i=1Kqt,i3Wt,i\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\left\\\{\\frac\{2\}\{\\gamma\}\+\\frac\{2\}\{\\gamma^\{2\}\}\+\\frac\{2\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}\+\\frac\{2\}\{\\gamma^\{3\}\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}^\{3\}\}\{W\_\{t,i\}\}\\right\\\}≤max𝒒t∈Δ​\(\[K\]\)⁡\{2γ\+2γ2\+2γ​∑i=1Kqt,i​\(1−qt,i\)Wt,i\+2γ3​∑i=1Kqt,i2\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\left\\\{\\frac\{2\}\{\\gamma\}\+\\frac\{2\}\{\\gamma^\{2\}\}\+\\frac\{2\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}\+\\frac\{2\}\{\\gamma^\{3\}\}\\sum\_\{i=1\}^\{K\}q\_\{t,i\}^\{2\}\\right\\\}≤max𝒒t∈ΔK⁡\{8γ\+2γ​∑i=1Kqt,i​\(1−qt,i\)Wt,i\}\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\_\{K\}\}\\,\\left\\\{\\frac\{8\}\{\\gamma\}\+\\frac\{2\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}\\right\\\}Next, we will bound2​qt,i​\(1−qt,i\)Wt,i\\frac\{2q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}for eachi∈\[K\]i\\in\[K\]\. Since we know that all nodes have self\-loops in our feedback graph,we know that

∑i=1K2​qt,i​\(1−qt,i\)Wt,i\\displaystyle\\sum\_\{i=1\}^\{K\}\\frac\{2q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}≤∑i=1K2​qt,i​\(1−qt,i\)∑j:At,\(j,i\)\(\(1−1γ\)​qt,j\+1γ​K\)\\displaystyle\\leq\\sum\_\{i=1\}^\{K\}\\frac\{2q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{\\sum\_\{j:A\_\{t,\(j,i\)\}\}\(\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,j\}\+\\frac\{1\}\{\\gamma K\}\)\}≤γγ−1​∑i=1K2​\(\(1−1γ\)​qt,i\+1γ​K\)​\(1−qt,i\)∑j:At,\(j,i\)\(\(1−1γ\)​qt,j\+1γ​K\)\\displaystyle\\leq\\frac\{\\gamma\}\{\\gamma\-1\}\\sum\_\{i=1\}^\{K\}\\frac\{2\(\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,i\}\+\\frac\{1\}\{\\gamma K\}\)\(1\-q\_\{t,i\}\)\}\{\\sum\_\{j:A\_\{t,\(j,i\)\}\}\(\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,j\}\+\\frac\{1\}\{\\gamma K\}\)\}≤4​∑i=1K\(\(1−1γ\)​qt,i\+1γ​K\)∑j:At,\(j,i\)\(\(1−1γ\)​qt,j\+1γ​K\)≤O​\(α​log⁡\(K​γ\)\)\\displaystyle\\leq 4\\sum\_\{i=1\}^\{K\}\\frac\{\(\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,i\}\+\\frac\{1\}\{\\gamma K\}\)\}\{\\sum\_\{j:A\_\{t,\(j,i\)\}\}\(\(1\-\\frac\{1\}\{\\gamma\}\)q\_\{t,j\}\+\\frac\{1\}\{\\gamma K\}\)\}\\leq O\\\!\\left\(\\alpha\\log\(K\\gamma\)\\right\)The last inequality is due to Lemma 5 from\[[4](https://arxiv.org/html/2607.09015#bib.bib61)\]\. Combining all of the above inequalities, we get

inf𝒑t∈Δ​\(\[K\]\)supi∗∈\[K\]\{∑i=1Kpt,i​𝒙t⊤​𝜽^t,i−𝒙t⊤​𝜽^t,i∗\+1γ‖𝒑t−𝒆i∗∥diag​\(𝑾t\)−12\}\\displaystyle\\inf\_\{\\bm\{p\}\_\{t\}\\in\\Delta\(\[K\]\)\}\\,\\sup\_\{i^\{\*\}\\in\[K\]\}\\,\\left\\\{\\sum\_\{i=1\}^\{K\}p\_\{t,i\}\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i\}\-\\bm\{x\}\_\{t\}^\{\\top\}\\hat\{\\bm\{\\theta\}\}\_\{t,i^\{\*\}\}\+\\frac\{1\}\{\\gamma\}\\\|\\bm\{p\}\_\{t\}\-\\bm\{e\}\_\{i^\{\*\}\}\\\|\_\{\\mathrm\{diag\}\(\\bm\{W\}\_\{t\}\)^\{\-1\}\}^\{2\}\\right\\\}≤max𝒒t∈ΔK⁡\{8γ\+2γ​∑i=1Kqt,i​\(1−qt,i\)Wt,i\}≤O​\(α​log⁡\(K​γ\)γ\)\\displaystyle\\leq\\max\_\{\\bm\{q\}\_\{t\}\\in\\Delta\_\{K\}\}\\,\\left\\\{\\frac\{8\}\{\\gamma\}\+\\frac\{2\}\{\\gamma\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\(1\-q\_\{t,i\}\)\}\{W\_\{t,i\}\}\\right\\\}\\leq O\\\!\\left\(\\frac\{\\alpha\\log\(K\\gamma\)\}\{\\gamma\}\\right\)∎

Before introducing the lemmas to bound the noise terms of our regret decomposition, we introduce the following useful graph\-theoretic result, which follows from\[[4](https://arxiv.org/html/2607.09015#bib.bib61)\]\.

###### Lemma F\.6\(A Useful Graph\-Theoretic Property\)\.

LetGtG\_\{t\}be a directed graph with verticesi∈\[K\]i\\in\[K\], in whichAt,\(i,i\)=1A\_\{t,\(i,i\)\}=1for all vertices\. Assign eachi∈\[K\]i\\in\[K\]a positive weightpt,ip\_\{t,i\}such that∑i∈\[K\]pt,i≤1\\sum\_\{i\\in\[K\]\}p\_\{t,i\}\\leq 1andpt,i≥ϵp\_\{t,i\}\\geq\\epsilonfor alli∈\[K\]i\\in\[K\]\. Then

∑i=1Kpt,i𝑨t,\(:,i\)⊤​𝒑t≤α⋅ln⁡\(4​Kα​ϵ\),\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,i\}\}\{\\bm\{A\}\_\{t,\(:,i\)\}^\{\\top\}\\bm\{p\}\_\{t\}\}\\;\\leq\\;\\alpha\\cdot\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\),whereα\\alphais the independence number ofGtG\_\{t\}\.

###### Proof\.

This follows from Lemma 5 of\[[4](https://arxiv.org/html/2607.09015#bib.bib61)\]\. ∎

###### Lemma F\.7\(Bounding the Regression\-Propagation Error\)\.

Suppose the feedback graphGtG\_\{t\}is deterministic with independence number no more thanα\\alpha\. Then Algorithm[1](https://arxiv.org/html/2607.09015#alg1)guarantees that the regression\-propagation error term of the bias may be bounded as

∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]≤α​ln⁡\(4​K/α​ϵ\)​\(1\+ln⁡T\)​T​RegSq​\(T\)\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\\leq\\sqrt\{\\alpha\\,\\ln\(4K/\\alpha\\epsilon\)\\,\(1\+\\ln T\)\\,T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}
###### Proof\.

We begin by applying the Cauchy–Schwarz inequality to the regression\-propagation error term and performing algebraic manipulation:

∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]\\displaystyle\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]≤∑t=1T∑j=1Kwt,j⋅∑t=1T∑j=1Kwt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j2\\displaystyle\\leq\\sqrt\{\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}w\_\{t,j\}\}\\cdot\\sqrt\{\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}^\{2\}\}≤α​T​ln⁡\(4​Kα​ϵ\)⋅∑t=1T∑j=1Kwt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j2\\displaystyle\\leq\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}^\{2\}\}\(4\)where Equation[4](https://arxiv.org/html/2607.09015#A6.E4)is due to applying Lemma[F\.6](https://arxiv.org/html/2607.09015#A6.Thmtheorem6)to the first term and assumingpt,i≥ϵp\_\{t,i\}\\geq\\epsilonfor allii\(Assumption[4\.5](https://arxiv.org/html/2607.09015#S4.Thmtheorem5)\)\.

Next we swap sums in the second term to group by the regression error

Δτ,j2\\Delta\_\{\\tau,j\}^\{2\}\. To do so, we must re\-index the summations\. We temporarily definetj,mt\_\{j,m\}as the round in which the learner observes armjjfor themm\-th time\. After re\-indexing we getα​T​ln⁡\(4​Kα​ϵ\)⋅∑j=1K∑m=2nT,jwtj,m,jm−1​∑u=1m−1Δtj,u,j2\\displaystyle\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\sum\_\{j=1\}^\{K\}\\sum\_\{m=2\}^\{n\_\{T,j\}\}\\frac\{w\_\{t\_\{j,m\},j\}\}\{m\-1\}\\sum\_\{u=1\}^\{m\-1\}\\Delta\_\{t\_\{j,u\},j\}^\{2\}\}=α​T​ln⁡\(4​Kα​ϵ\)⋅∑j=1K∑u=1nT,j−1Δtj,u,j2​∑m=u\+1nT,jwtj,m,jm−1\\displaystyle=\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\sum\_\{j=1\}^\{K\}\\sum\_\{u=1\}^\{n\_\{T,j\}\-1\}\\Delta\_\{t\_\{j,u\},j\}^\{2\}\\sum\_\{m=u\+1\}^\{n\_\{T,j\}\}\\frac\{w\_\{t\_\{j,m\},j\}\}\{m\-1\}\}\(5\)≤α​T​ln⁡\(4​Kα​ϵ\)⋅∑j=1K∑u=1nT,j−1Δtj,u,j2​∑m=1nT,j1m\\displaystyle\\leq\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\sum\_\{j=1\}^\{K\}\\sum\_\{u=1\}^\{n\_\{T,j\}\-1\}\\Delta\_\{t\_\{j,u\},j\}^\{2\}\\sum\_\{m=1\}^\{n\_\{T,j\}\}\\frac\{1\}\{m\}\}≤α​T​ln⁡\(4​Kα​ϵ\)⋅∑j=1K∑u=1nT,j−1Δtj,u,j2⋅\(1\+ln⁡T\)\\displaystyle\\leq\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\sum\_\{j=1\}^\{K\}\\sum\_\{u=1\}^\{n\_\{T,j\}\-1\}\\Delta\_\{t\_\{j,u\},j\}^\{2\}\\cdot\(1\+\\ln T\)\}\(6\)≤α​T​ln⁡\(4​Kα​ϵ\)⋅∑j=1K∑t=1TΔt,j2⋅\(1\+ln⁡T\)\\displaystyle\\leq\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\sum\_\{j=1\}^\{K\}\\sum\_\{t=1\}^\{T\}\\Delta\_\{t,j\}^\{2\}\\cdot\(1\+\\ln T\)\}≤α​T​ln⁡\(4​Kα​ϵ\)⋅RegSq​\(T\)⋅\(1\+ln⁡T\),\\displaystyle\\leq\\sqrt\{\\alpha\\,T\\;\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\cdot\\sqrt\{\\mathrm\{Reg\_\{Sq\}\}\(T\)\\cdot\(1\+\\ln T\)\},\(7\)where Equation[5](https://arxiv.org/html/2607.09015#A6.E5)is due to swapping sums, and Equation[6](https://arxiv.org/html/2607.09015#A6.E6)is due to the following fact about harmonic sums: For any armj,j,the sum, over its observation indicesm=1,…,nT,jm=1,\\dots,n\_\{T,j\}, of1/m1/msatisfies

∑m=1nT,j1m≤1\+ln⁡nT,j≤1\+ln⁡T\.\\sum\_\{m=1\}^\{n\_\{T,j\}\}\\frac\{1\}\{m\}\\leq 1\+\\ln n\_\{T,j\}\\leq 1\+\\ln T\.We can combine the terms in Equation[7](https://arxiv.org/html/2607.09015#A6.E7)to finally get

∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]≤α​T​ln⁡\(4​K/α​ϵ\)​\(1\+ln⁡T\)​RegSq​\(T\)\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\\leq\\sqrt\{\\alpha T\\,\\ln\(4K/\\alpha\\epsilon\)\\,\(1\+\\ln T\)\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}∎

###### Lemma F\.8\(Bounding the Observation Noise\)\.

Suppose the feedback graphGtG\_\{t\}is deterministic with independence number no more thanα\\alpha\. Then, for allδ\>0\\delta\>0, with probability1−δ1\-\\deltaAlgorithm[1](https://arxiv.org/html/2607.09015#alg1)guarantees that the observation noise term of the bias may be bounded as

∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|≤εn​2​α​K​T​ln⁡\(2​K​Tδ\)​ln⁡\(4​Kα​ϵ\)​\(1\+ln⁡T\)\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\alpha KT\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\(1\+\\ln T\)\}
###### Proof\.

We begin by bounding the term

\|1nt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\left\|\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|We do so by fixing a specific armjjand considering the sequence of noise terms observed for this arm\. Letkkindex the observations of armjj, such thatζk\\zeta\_\{k\}is the noise of thekk\-th observation\. The sequence of partial sumsSm=∑k=1mζkS\_\{m\}=\\sum\_\{k=1\}^\{m\}\\zeta\_\{k\}forms a martingale with respect to the filtration of observation events, satisfying the bounded difference property:

\|Sm−Sm−1\|=\|ζm\|≤εn\.\|S\_\{m\}\-S\_\{m\-1\}\|=\|\\zeta\_\{m\}\|\\leq\\varepsilon\_\{n\}\.We apply the Azuma\-Hoeffding inequality\. For anym≥1m\\geq 1and anyλ\>0\\lambda\>0:

ℙ​\(\|Sm\|≥λ\)≤2​exp⁡\(−λ22​∑k=1m\(εn\)2\)=2​exp⁡\(−λ22​m​εn2\)\.\\mathbb\{P\}\\left\(\|S\_\{m\}\|\\geq\\lambda\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{\\lambda^\{2\}\}\{2\\sum\_\{k=1\}^\{m\}\(\\varepsilon\_\{n\}\)^\{2\}\}\\right\)=2\\exp\\\!\\left\(\-\\frac\{\\lambda^\{2\}\}\{2m\\varepsilon\_\{n\}^\{2\}\}\\right\)\.We seek a bound that holds with high probability1−δ′1\-\\delta^\{\\prime\}\. Setting the right\-hand side toδ′\\delta^\{\\prime\}and solving forλ\\lambda:

2​exp⁡\(−λ22​m​εn2\)\\displaystyle 2\\exp\\\!\\left\(\-\\frac\{\\lambda^\{2\}\}\{2m\\varepsilon\_\{n\}^\{2\}\}\\right\)=δ′\\displaystyle=\\delta^\{\\prime\}−λ22​m​εn2\\displaystyle\-\\frac\{\\lambda^\{2\}\}\{2m\\varepsilon\_\{n\}^\{2\}\}=ln⁡\(δ′/2\)\\displaystyle=\\ln\(\\delta^\{\\prime\}/2\)λ\\displaystyle\\lambda=2​m​εn2​ln⁡\(2/δ′\)\.\\displaystyle=\\sqrt\{2m\\varepsilon\_\{n\}^\{2\}\\ln\(2/\\delta^\{\\prime\}\)\}\.SubstitutingSm=nt,j⋅1nt,j​∑τ∈𝒯t​\(j\)ξτ,jS\_\{m\}=n\_\{t,j\}\\cdot\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\(wherem=nt,jm=n\_\{t,j\}\) and dividing bynt,jn\_\{t,j\}:

ℙ​\(\|1nt,j​∑τ∈𝒯t​\(j\)ξτ,j\|≥εn​2​ln⁡\(2/δ′\)nt,j\)≤δ′\.\\mathbb\{P\}\\left\(\\left\|\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|\\geq\\varepsilon\_\{n\}\\sqrt\{\\frac\{2\\ln\(2/\\delta^\{\\prime\}\)\}\{n\_\{t,j\}\}\}\\right\)\\leq\\delta^\{\\prime\}\.To ensure this bound holds simultaneously for all roundst∈\[T\]t\\in\[T\]and all armsj∈\[K\]j\\in\[K\], we apply a Union Bound over theK​TKTpossible events\. We set the individual failure probability toδ′=δ/\(K​T\)\\delta^\{\\prime\}=\\delta/\(KT\)\. Substitutingδ′\\delta^\{\\prime\}into the bound:

\|1nt,j​∑τ∈𝒯t​\(j\)ξτ,j\|≤εn​2​ln⁡\(2​K​T/δ\)nt,j\.\\left\|\\frac\{1\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|\\leq\\varepsilon\_\{n\}\\sqrt\{\\frac\{2\\ln\(2KT/\\delta\)\}\{n\_\{t,j\}\}\}\.We may plug this quantity back into the observation noise term to get

∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\displaystyle\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|≤εn​2​ln⁡\(2​K​Tδ\)​∑t=1T∑j=1Kwt,jnt,j\\displaystyle\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\}\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\frac\{w\_\{t,j\}\}\{\\sqrt\{n\_\{t,j\}\}\}≤εn​2​ln⁡\(2​K​Tδ\)​\(∑t=1T∑j=1Kwt,j\)​\(∑t=1T∑j=1Kwt,jnt,j\)\\displaystyle\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\}\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}w\_\{t,j\}\\right\)\}\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\right\)\}\(8\)≤εn​2​ln⁡\(2​K​Tδ\)​α​T​ln⁡\(4​Kα​ϵ\)​\(∑t=1T∑j=1Kwt,jnt,j\)\\displaystyle\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\}\\sqrt\{\\alpha T\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\right\)\}\(9\)≤εn​2​ln⁡\(2​K​Tδ\)​α​T​ln⁡\(4​Kα​ϵ\)​∑j=1K\(1\+ln⁡T\)\\displaystyle\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\}\\sqrt\{\\alpha T\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\sqrt\{\\sum\_\{j=1\}^\{K\}\(1\+\\ln T\)\}\(10\)≤εn​2​ln⁡\(2​K​Tδ\)​α​T​ln⁡\(4​Kα​ϵ\)​K​\(1\+ln⁡T\),\\displaystyle\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\}\\sqrt\{\\alpha T\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\}\\sqrt\{K\(1\+\\ln T\)\},where Equation[8](https://arxiv.org/html/2607.09015#A6.E8)is due to applying the Cauchy\-Shwarz inequality, Equation[9](https://arxiv.org/html/2607.09015#A6.E9)is due to the same application of Lemma[F\.6](https://arxiv.org/html/2607.09015#A6.Thmtheorem6)as Equation[4](https://arxiv.org/html/2607.09015#A6.E4), and Equation[10](https://arxiv.org/html/2607.09015#A6.E10)is due to applying the same fact about harmonic sums used in Equation[6](https://arxiv.org/html/2607.09015#A6.E6)\. Combining these terms yields \(with probability at least1−δ1\-\\delta\):

∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|≤εn​2​α​K​T​ln⁡\(2​K​Tδ\)​ln⁡\(4​Kα​ϵ\)​\(1\+ln⁡T\)\.\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|\\leq\\varepsilon\_\{n\}\\sqrt\{\{2\\alpha KT\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\(1\+\\ln T\)\}\.∎

##### Proof of Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7)\.

We now utilize the preceding lemmas to prove that under the assumptions outlined in Section[4\.1](https://arxiv.org/html/2607.09015#S4.SS1), if the feedback graphGtG\_\{t\}is deterministic with independence number no more thanα\\alpha\. Then, with probability1−δ1\-\\delta, Algorithm[1](https://arxiv.org/html/2607.09015#alg1)with choiceγ=max⁡\{4,α​T/RegSq​\(T\)\}\\gamma=\\max\\left\\\{4,\\sqrt\{\\alpha T/\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\\right\\\}guarantees that

𝔼​\[RegT\]≤O~​\(α​T​RegSq​\(T\)\+εn​α​K​T\)\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\,\\sqrt\{\\alpha KT\}\\ \\right\)\.
###### Proof\.

Combining the results of Lemmas[F\.3](https://arxiv.org/html/2607.09015#A6.Thmtheorem3)and[F\.4](https://arxiv.org/html/2607.09015#A6.Thmtheorem4), we get the full regret decomposition of Algorithm[1](https://arxiv.org/html/2607.09015#alg1):

𝔼​\[RegT\]≤\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leqT⋅ϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\+γ4​RegSq​\(T\)\\displaystyle\\;T\\cdot\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)\\;\+\\;\\frac\{\\gamma\}\{4\}\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\+∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]\+∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\displaystyle\\;\+\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\\;\+\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|We may plug in the result of Lemma[F\.5](https://arxiv.org/html/2607.09015#A6.Thmtheorem5)intoϕ​\(𝒑;𝜽^t,𝒙t,𝑨t\)\\phi\(\\bm\{p\};\\hat\{\\bm\{\\theta\}\}\_\{t\},\\bm\{x\}\_\{t\},\\bm\{A\}\_\{t\}\)to get

𝔼​\[RegT\]≤\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leqO​\(α​T​log⁡\(K​γ\)γ\)\+γ4​RegSq​\(T\)\\displaystyle\\;O\\\!\\left\(\\frac\{\\alpha T\\log\(K\\gamma\)\}\{\\gamma\}\\right\)\\;\+\\;\\frac\{\\gamma\}\{4\}\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\+∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]\+∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\displaystyle\\;\+\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\\;\+\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|
We selectγ=α​T/RegSq​\(T\)\\gamma=\\sqrt\{\\alpha T/\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\(for stability we must ensure thatγ≥4\\gamma\\geq 4\) and combine the first two terms of the decomposition to get \(absorbing polylog factors\)

𝔼​\[RegT\]≤\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leqO~​\(α​T​RegSq​\(T\)\)\+∑t=1T∑j=1K\[wt,jnt,j​∑τ∈𝒯t​\(j\)Δτ,j\]\+∑t=1T∑j=1K\|wt,jnt,j​∑τ∈𝒯t​\(j\)ξτ,j\|\\displaystyle\\;\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\\right\)\\;\+\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\[\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\Delta\_\{\\tau,j\}\\right\]\\;\+\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{K\}\\left\|\\frac\{w\_\{t,j\}\}\{n\_\{t,j\}\}\\sum\_\{\\tau\\in\\mathcal\{T\}\_\{t\}\(j\)\}\\xi\_\{\\tau,j\}\\right\|Applying the results of Lemmas[F\.7](https://arxiv.org/html/2607.09015#A6.Thmtheorem7)and[F\.8](https://arxiv.org/html/2607.09015#A6.Thmtheorem8)we get

𝔼​\[RegT\]≤\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leqO~​\(α​T​RegSq​\(T\)\)\+α​T​ln⁡\(4​K/α​ϵ\)​\(1\+ln⁡T\)​RegSq​\(T\)\\displaystyle\\;\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\\right\)\\;\+\\;\\sqrt\{\\alpha T\\,\\ln\(4K/\\alpha\\epsilon\)\\,\(1\+\\ln T\)\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+εn​2​α​K​T​ln⁡\(2​K​Tδ\)​ln⁡\(4​Kα​ϵ\)​\(1\+ln⁡T\)\.\\displaystyle\\;\+\\;\\varepsilon\_\{n\}\\sqrt\{\{2\\alpha KT\\ln\\\!\\left\(\\frac\{2KT\}\{\\delta\}\\right\)\}\\ln\\\!\\left\(\\frac\{4K\}\{\\alpha\\epsilon\}\\right\)\(1\+\\ln T\)\}\.combining the final two terms and once again absorbing polylog factors, we get

𝔼​\[RegT\]≤O~​\(α​T​RegSq​\(T\)\+εn​α​K​T\)\.\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)\}\+\\varepsilon\_\{n\}\\,\\sqrt\{\\alpha KT\}\\ \\right\)\.∎

#### F\.2\.2Bounds formm\-Transitive Feedback Graphs

For completeness, we now state a theorem relating the independence numberα\\alphaof the feedback graphGtG\_\{t\}with a constant number of additional armsmmobserved at each round\. This result enables us to tighten existing regret bounds for both standard and contextual bandits by a factor of roughly1/m1/\\sqrt\{m\}, quantifying the direct benefit of the auxiliary feedback\.

###### Theorem F\.9\(Independence Number for Transitivemm\-Regular Feedback\)\.

Consider a bandit setting withKKarms where the feedback graphGtG\_\{t\}is transitive andmm\-regular \(i\.e\., each vertex has out\-degreemm\)\. Under these conditions,GtG\_\{t\}decomposes intoK/\(m\+1\)K/\(m\+1\)disjoint cliques of sizem\+1m\+1, and its independence number is:

α​\(Gt\)=Km\+1\\alpha\(G\_\{t\}\)=\\frac\{K\}\{m\+1\}

###### Proof\.

LetGt=\(V,E\)G\_\{t\}=\(V,E\)be the feedback graph\. By the assumption of transitivity, if\(u,v\)∈E\(u,v\)\\in Eand\(v,w\)∈E\(v,w\)\\in E, then\(u,w\)∈E\(u,w\)\\in E\. In the context of an undirected or bi\-directed feedback graph, transitivity implies that the graph is a disjoint union of cliques\. SinceGtG\_\{t\}ismm\-regular, each vertex belongs to a clique of size exactlym\+1m\+1\. Consequently, the vertex setVVis partitioned intoNNdisjoint cliques\{C1,C2,…,CN\}\\\{C\_\{1\},C\_\{2\},\\dots,C\_\{N\}\\\}, where:

N=\|V\|m\+1=Km\+1N=\\frac\{\|V\|\}\{m\+1\}=\\frac\{K\}\{m\+1\}To determine the independence numberα​\(Gt\)\\alpha\(G\_\{t\}\), we observe the following:

1. 1\.Lower Bound:By the Caro\-Wei Theorem\[[9](https://arxiv.org/html/2607.09015#bib.bib65),[49](https://arxiv.org/html/2607.09015#bib.bib66)\], for any graph with vertex degreesd​\(k\)d\(k\), the independence number is bounded by: α​\(Gt\)≥∑k∈V1d​\(k\)\+1=∑k=1K1m\+1=Km\+1\\alpha\(G\_\{t\}\)\\geq\\sum\_\{k\\in V\}\\frac\{1\}\{d\(k\)\+1\}=\\sum\_\{k=1\}^\{K\}\\frac\{1\}\{m\+1\}=\\frac\{K\}\{m\+1\}\(11\)
2. 2\.Upper Bound:An independent set can contain at most one vertex from any clique\. SinceVVis partitioned into exactlyKm\+1\\frac\{K\}\{m\+1\}disjoint cliques, the size of the maximum independent set is bounded by the number of cliques: α​\(Gt\)≤Km\+1\\alpha\(G\_\{t\}\)\\leq\\frac\{K\}\{m\+1\}\(12\)

Combining inequalities in Equations[11](https://arxiv.org/html/2607.09015#A6.E11)and[12](https://arxiv.org/html/2607.09015#A6.E12), we conclude thatα​\(Gt\)=Km\+1\\alpha\(G\_\{t\}\)=\\frac\{K\}\{m\+1\}\. ∎

##### Deriving Corollary[4\.8](https://arxiv.org/html/2607.09015#S4.Thmtheorem8)\.

Corollary[4\.8](https://arxiv.org/html/2607.09015#S4.Thmtheorem8)follows by substitutingα=Km\+1\\alpha=\\frac\{K\}\{m\+1\}from Theorem[F\.9](https://arxiv.org/html/2607.09015#A6.Thmtheorem9)into the general regret bound of Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7), and applying the standard square\-loss regret bound for linear regression oracles\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\],RegSq​\(T\)=O​\(d​log⁡\(Td\)\)\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)=O\(d\\log\\left\(\\frac\{T\}\{d\}\\right\)\)\.

### F\.3Correlation Aware Bandits with Surrogates Decoupled \(CABS\-D\)

We now present a meta bandit algorithm that achieves the minimum regret of the above two sections, i\.e,O~\(min\{d​K​T​log⁡\(Td\),d​Km\+1​T​log⁡\(Td\)\+εnK2m\+1​T\)\\widetilde\{O\}\\Big\(\\min\\\{\\sqrt\{dKT\\log\\left\(\\frac\{T\}\{d\}\\right\)\},\\sqrt\{d\\frac\{K\}\{m\+1\}T\\log\\left\(\\frac\{T\}\{d\}\\right\)\}\+\\varepsilon\_\{n\}\\sqrt\{\\frac\{K^\{2\}\}\{m\+1\}T\}\\Big\)\. In our main section, we present this as CABS\-D \(Algorithm[2](https://arxiv.org/html/2607.09015#alg2)\)\. We start by presenting the Algorithm[2](https://arxiv.org/html/2607.09015#alg2)for Correlation\-Aware Bandits with Surrogates Decoupled \(CABS\-D\) and then prove the regret bound of it\.

#### F\.3\.1High Level Proof Sketch

The proof of Theorem[2](https://arxiv.org/html/2607.09015#alg2)establishes a best\-of\-both\-worlds guarantee by analyzing CABS\-D as an aggregation of two base experts: a bandit\-feedback expert, SquareCB \(Algorithm[3](https://arxiv.org/html/2607.09015#alg3)\) and a graph\-feedback expert, CABS\-C \(Algorithm[1](https://arxiv.org/html/2607.09015#alg1)\), each instantiated over a geometric grid of learning rates to formM=2​LM=2Lmeta\-copies\. The analysis proceeds by first establishing the optimistic bias, uniform boundedness, and second\-moment properties of the Implicit eXploration \(IX\) loss estimators utilized by both experts\. Next, we decompose the total expected regret into the regret of the best\-performing base expert \(RmR\_\{m\}\), an additive bias term, and a meta\-learning overhead term\. By bounding the second\-order variance terms independently for the regimes where either the bandit or graph expert dominates, and demonstrating that the geometric grid contains an optimal scaling parameterγ\(g\)\\gamma^\{\(g\)\}for each respective regime, we show that the aggregation overhead is tightly controlled\. Consequently, the total expected regret asymptotically matches the minimum regret of either the pure bandit or correlation\-aware surrogate expert, yieldingO~​\(min⁡\{K​T​RegS​q​\(T\),α​T​RegS​q​\(T\)\+ϵn​α​K​T\}\)\\tilde\{O\}\\left\(\\min\\\{\\sqrt\{KT\\text\{Reg\}\_\{Sq\}\(T\)\},\\sqrt\{\\alpha T\\text\{Reg\}\_\{Sq\}\(T\)\}\+\\epsilon\_\{n\}\\sqrt\{\\alpha KT\}\\\}\\right\)\.

Regret Bound for Algorithm[2](https://arxiv.org/html/2607.09015#alg2)\(CABS\-D\)

Overview and setup\.We follow the same algorithmic structure as in Algorithm[2](https://arxiv.org/html/2607.09015#alg2)\(geometric gridded

γ\\gammaper base expert\)\. For clarity we restate the essential components and set the notation used throughout the proof\. Note that we utilize losses in the following analysis\. There are 2*base*experts \(bandit\-style \(

m=1m=1\) and graph\-style \(

m=2m=2\)\)\. Each base expert

m∈\{1,2\}m\\in\\\{1,2\\\}is instantiated with a geometric grid of

LLparameter values

Γ=\{γ\(1\),…,γ\(L\)\}\\Gamma=\\\{\\gamma^\{\(1\)\},\\dots,\\gamma^\{\(L\)\}\\\}, with dyadic spacing

γ\(g\+1\)=2​γ\(g\)\\gamma^\{\(g\+1\)\}=2\\gamma^\{\(g\)\}\(or any constant ratio

\>1\>1\)\. Each pair

\(m,g\)\(m,g\)is a distinct*meta\-copy*\. The total number of meta\-copies is

M=2​LM\\;=\\;2L\.

To prove Theorem[4\.9](https://arxiv.org/html/2607.09015#S4.Thmtheorem9), we first introduce the following auxiliary lemma regarding the properties of the Implicit eXploration \(IX\) estimators\. We continue by introducing auxiliary lemmas regarding the regret decomposition and bounding second\-order terms\. We combine and utilize the results of these lemmas in the final proof of Theorem[4\.9](https://arxiv.org/html/2607.09015#S4.Thmtheorem9)\.

###### Lemma F\.10\(Properties of IX Estimators\)\.

Letℓ^t,\(1,g\)\\hat\{\\ell\}\_\{t,\(1,g\)\}andℓ^t,\(2,g\)\\hat\{\\ell\}\_\{t,\(2,g\)\}be the IX estimators defined in Algorithm[2](https://arxiv.org/html/2607.09015#alg2)\. Then, the following properties are true:

1. 1\.\(Optimistic Bias\) For every meta expert\(m,g\)\(m,g\)in roundttand conditioned onℱt−1\\mathcal\{F\}\_\{t\-1\}, we have 𝔼​\[ℓ^t,\(m,g\)∣ℱt−1\]≤∑ipt,m,i​ℓt,i\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(m,g\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\leq\\sum\_\{i\}p\_\{t,m,i\}\\ell\_\{t,i\} ###### Proof\. We begin by showing this is true forℓ^t,\(1,g\)\\hat\{\\ell\}\_\{t,\(1,g\)\}\(bandit experts\): 𝔼​\[ℓ^t,\(1,g\)∣ℱt−1\]=∑iqt,iqt,i\+γ\(g\)​pt,m,i​ℓt,i≤∑ipt,1,i​ℓt,i\.\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(1,g\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\;=\\;\\sum\_\{i\}\\frac\{q\_\{t,i\}\}\{q\_\{t,i\}\+\\gamma^\{\(g\)\}\}\\,p\_\{t,m,i\}\\,\\ell\_\{t,i\}\\leq\\sum\_\{i\}p\_\{t,1,i\}\\ell\_\{t,i\}\.We proceed similarly forℓ^t,\(2,g\)\\hat\{\\ell\}\_\{t,\(2,g\)\}\(graph experts\)\. We begin by rewriting the estimator as: 𝔼​\[ℓ^t,\(2,g\)∣ℱt−1\]\\displaystyle\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(2,g\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]=∑k=1Kqt,k​\[∑i=1Kℓt,i​pt,2,i∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)⋅𝕀​\{At,\(k,i\)=1\}\]\\displaystyle\\;=\\;\\sum\_\{k=1\}^\{K\}q\_\{t,k\}\\left\[\\sum\_\{i=1\}^\{K\}\\frac\{\\ell\_\{t,i\}\\,p\_\{t,2,i\}\}\{\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(j,i\)\}=1\\\}\+\\gamma^\{\(g\)\}\}\\cdot\\mathbb\{I\}\\\!\\left\\\{\{A\}\_\{t,\(k,i\)\}=1\\right\\\}\\right\]=∑i=1Kℓt,i​pt,2,i∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)⋅∑k=1Kqt,k​𝕀​\{At,\(k,i\)=1\}\\displaystyle\\;=\\;\\sum\_\{i=1\}^\{K\}\\frac\{\\ell\_\{t,i\}\\,p\_\{t,2,i\}\}\{\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(j,i\)\}=1\\\}\+\\gamma^\{\(g\)\}\}\\cdot\\sum\_\{k=1\}^\{K\}q\_\{t,k\}\\,\\mathbb\{I\}\\\!\\left\\\{\{A\}\_\{t,\(k,i\)\}=1\\right\\\}≤∑i=1Kℓt,i​pt,2,i,\\displaystyle\\;\\leq\\;\\sum\_\{i=1\}^\{K\}\\ell\_\{t,i\}\\,p\_\{t,2,i\},where the last step is due to∑k=1Kqt,k​𝕀​\{At,\(k,i\)=1\}∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)≤1\\frac\{\\sum\_\{k=1\}^\{K\}q\_\{t,k\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(k,i\)\}=1\\\}\}\{\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(j,i\)\}=1\\\}\+\\gamma^\{\(g\)\}\}\\leq 1\. ∎
2. 2\.\(Uniform Bound\) For every meta expert\(m,g\)\(m,g\)in roundtt, we may bound the value ofℓ^t,\(m,g\)\\hat\{\\ell\}\_\{t,\(m,g\)\}as ℓ^t,\(m,g\)≤1γ\(g\)\\hat\{\\ell\}\_\{t,\(m,g\)\}\\leq\\frac\{1\}\{\\gamma^\{\(g\)\}\} ###### Proof\. For bothℓ^t,\(1,g\)\\hat\{\\ell\}\_\{t,\(1,g\)\}andℓ^t,\(2,g\)\\hat\{\\ell\}\_\{t,\(2,g\)\}, the numerators are at most11and denominators are at leastγ\(g\)\\gamma^\{\(g\)\}\. ∎
3. 3\.\(Second Moment Bounds\) For every bandit meta expert\(1,g\)\(1,g\)in roundttand conditioned onℱt−1\\mathcal\{F\}\_\{t\-1\}, we may say 𝔼​\[ℓ^t,\(1,g\)2∣ℱt−1\]≤∑i=1Kpt,1,iqt,i\+γ\(g\)\.\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(1,g\)\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\leq\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,1,i\}\}\{q\_\{t,i\}\+\\gamma^\{\(g\)\}\}\.Likewise, for every graph meta expert\(2,g\)\(2,g\)in roundttand conditioned onℱt−1\\mathcal\{F\}\_\{t\-1\}, we may say 𝔼​\[ℓ^t,\(2,g\)2∣ℱt−1\]≤∑i=1Kpt,2,i∑j:At,\(j,i\)=1qt,j\+γ\(g\)\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(2,g\)\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\leq\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,2,i\}\}\{\\sum\_\{j:\{A\}\_\{t,\(j,i\)\}=1\}q\_\{t,j\}\+\\gamma^\{\(g\)\}\} ###### Proof\. We begin by showing this is true forℓ^t,\(1,g\)\\hat\{\\ell\}\_\{t,\(1,g\)\}\(bandit experts\): 𝔼​\[ℓ^t,\(1,g\)2∣ℱt−1\]=∑i=1Kqt,i​\(ℓt,i​pt,1,iq​\(a\)\+γ\(g\)\)2≤∑i=1K\(pt,1,i\)2qt,i\+γ\(g\)≤∑i=1Kpt,1,iqt,i\+γ\(g\)\\displaystyle\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(1,g\)\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]=\\sum\_\{i=1\}^\{K\}q\_\{t,i\}\\left\(\\frac\{\\ell\_\{t,i\\,\}p\_\{t,1,i\}\}\{q\(a\)\+\\gamma^\{\(g\)\}\}\\right\)^\{2\}\\leq\\sum\_\{i=1\}^\{K\}\\frac\{\(p\_\{t,1,i\}\)^\{2\}\}\{q\_\{t,i\}\+\\gamma^\{\(g\)\}\}\\leq\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,1,i\}\}\{q\_\{t,i\}\+\\gamma^\{\(g\)\}\}We proceed similarly forℓ^t,\(2,g\)\\hat\{\\ell\}\_\{t,\(2,g\)\}\(graph experts\)\. We once again rewrite the estimator as: 𝔼​\[ℓ^t,\(2,g\)2∣ℱt−1\]\\displaystyle\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(2,g\)\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]=∑k=1Kqt,k​\(∑i=1Kℓt,i​pt,2,i∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)⋅𝕀​\{At,\(k,i\)=1\}\)2\\displaystyle=\\sum\_\{k=1\}^\{K\}q\_\{t,k\}\\left\(\\sum\_\{i=1\}^\{K\}\\frac\{\\ell\_\{t,i\}\\,p\_\{t,2,i\}\}\{\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(j,i\)\}=1\\\}\+\\gamma^\{\(g\)\}\}\\cdot\\mathbb\{I\}\\\{\{A\}\_\{t,\(k,i\)\}=1\\\}\\right\)^\{2\}≤∑k=1Kqt,k​∑i=1K\(pt,2,i\)2​\(ℓt,i​𝕀​\{At,\(k,i\)=1\}∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)\)2\\displaystyle\\leq\\sum\_\{k=1\}^\{K\}q\_\{t,k\}\\sum\_\{i=1\}^\{K\}\(p\_\{t,2,i\}\)^\{2\}\\left\(\\frac\{\\ell\_\{t,i\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(k,i\)\}=1\\\}\}\{\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(j,i\)\}=1\\\}\+\\gamma^\{\(g\)\}\}\\right\)^\{2\}≤∑i=1Kℓt,i2​pt,2,i2\(∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)\)2​∑k=1Kqt,k​𝕀​\{At,\(k,i\)=1\}\\displaystyle\\leq\\sum\_\{i=1\}^\{K\}\\frac\{\\ell\_\{t,i\}^\{2\}\\,p\_\{t,2,i\}^\{2\}\}\{\(\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\{\{A\}\_\{t,\(j,i\)\}=1\\\}\+\\gamma^\{\(g\)\}\)^\{2\}\}\\sum\_\{k=1\}^\{K\}q\_\{t,k\}\\,\\mathbb\{I\}\\\!\\left\\\{\{A\}\_\{t,\(k,i\)\}=1\\right\\\}≤∑i=1Kℓt,i2​pt,2,i2∑j=1Kqt,j​𝕀​\{At,\(j,i\)=1\}\+γ\(g\)\\displaystyle\\leq\\sum\_\{i=1\}^\{K\}\\frac\{\\ell\_\{t,i\}^\{2\}\\,p\_\{t,2,i\}^\{2\}\}\{\\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\,\\mathbb\{I\}\\\!\\left\\\{\{A\}\_\{t,\(j,i\)\}=1\\right\\\}\+\\gamma^\{\(g\)\}\}≤∑i=1Kpt,2,i∑j:At,\(j,i\)=1qt,j\+γ\(g\)\\displaystyle\\leq\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,2,i\}\}\{\\sum\_\{j:\{A\}\_\{t,\(j,i\)\}=1\}q\_\{t,j\}\+\\gamma^\{\(g\)\}\}∎

###### Lemma F\.11\(Regret Decomposition\)\.

We may decompose the regret of Algorithm[2](https://arxiv.org/html/2607.09015#alg2)as the following:

𝔼​\[RegT\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]≤minm∈\{1,2\}⁡Rm\+𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\+𝔼​\[ℬT\],\\displaystyle\\leq\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}R\_\{m\}\+\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\+\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\],whereRmR\_\{m\}indicates the expected regret of expertmm,ℬT\\mathcal\{B\}\_\{T\}is an additive term to account for estimation bias\.

###### Proof\.

We begin by defining the weightswt,\(m,g\)w\_\{t,\(m,g\)\}for each meta expert\(m,g\)\(m,g\)\. We additionally recall:

wt\+1,\(m,g\)=wt,\(m,g\)​e−ηt​ℓ^t,\(m,g\),Wt\+1=∑m=12∑g=1Lwt,\(m,g\)​e−ηt​ℓ^t,\(m,g\)\.\\displaystyle w\_\{t\+1,\(m,g\)\}=w\_\{t,\(m,g\)\}\\,e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\},\\qquad W\_\{t\+1\}=\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}w\_\{t,\(m,g\)\}e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\}\.Thus

Wt\+1Wt=∑m=12∑g=1Lμt,\(m,g\)​e−ηt​ℓ^t,\(m,g\)\\displaystyle\\frac\{W\_\{t\+1\}\}\{W\_\{t\}\}=\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\,e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\}We take logs on both sides of the inequality and sum over allt=1,…,Tt=1,\\dots,T\. Simplifying the resulting telescoping series we get

ln⁡WT\+1W1\\displaystyle\\ln\\frac\{W\_\{T\+1\}\}\{W\_\{1\}\}=∑t=1Tln⁡\(∑m=12∑g=1Lμt,\(m,g\)​e−ηt​ℓ^t,\(m,g\)\)\\displaystyle=\\sum\_\{t=1\}^\{T\}\\ln\\\!\\left\(\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\}\\right\)ln⁡W1WT\+1\\displaystyle\\ln\\frac\{W\_\{1\}\}\{W\_\{T\+1\}\}=∑t=1T−ln⁡\(∑m=12∑g=1Lμt,\(m,g\)​e−ηt​ℓ^t,\(m,g\)\)\\displaystyle=\\sum\_\{t=1\}^\{T\}\-\\ln\\\!\\left\(\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\}\\right\)\(13\)Applyinge−x≤1−x\+x2/2e^\{\-x\}\\leq 1\-x\+\{x^\{2\}\}/\{2\}, we may say

∑m=12∑g=1Lμt,\(m,g\)​e−ηt​ℓ^t,\(m,g\)\\displaystyle\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\}≤1−ηt​∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\+ηt22​∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)2\.\\displaystyle\\leq 1\-\\eta\_\{t\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\+\\frac\{\\eta\_\{t\}^\{2\}\}\{2\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}^\{2\}\.Applying the inequality−ln⁡\(1\+x\)≥−x\-\\ln\(1\+x\)\\geq\-x, we get

−ln⁡\(∑m=12∑g=1Lμt,\(m,g\)​e−ηt​ℓ^t,\(m,g\)\)\\displaystyle\-\\ln\\\!\\left\(\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}e^\{\-\\eta\_\{t\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\}\\right\)≥ηt​∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\+ηt22​Vt\.\\displaystyle\\geq\\eta\_\{t\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\+\\frac\{\\eta\_\{t\}^\{2\}\}\{2\}V\_\{t\}\.\(14\)We may upper bound the quantityln⁡W1WT\+1\\ln\\frac\{W\_\{1\}\}\{W\_\{T\+1\}\}using the knowledge thatW1=MW\_\{1\}=Mand WT\+1≥exp⁡\(−minm,g​∑s=1Tηs​ℓ^s,\(m,g\)\)W\_\{T\+1\}\\geq\\exp\\\!\\left\(\-\\min\_\{m,g\}\\sum\_\{s=1\}^\{T\}\\eta\_\{s\}\\hat\{\\ell\}\_\{s,\(m,g\)\}\\right\):

ln⁡W1WT\+1\\displaystyle\\ln\\frac\{W\_\{1\}\}\{W\_\{T\+1\}\}≤ln⁡M\+minm∈\{1,2\}g∈\[L\]​∑s=1Tηs​ℓ^s,\(m,g\)\\displaystyle\\leq\\ln M\+\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\eta\_\{s\}\\hat\{\\ell\}\_\{s,\(m,g\)\}\(15\)Plugging Equations[14](https://arxiv.org/html/2607.09015#A6.E14)and[15](https://arxiv.org/html/2607.09015#A6.E15)into Equation[13](https://arxiv.org/html/2607.09015#A6.E13)yields

∑t=1Tηt​∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\+∑t=1Tηt22​Vt\\displaystyle\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\+\\sum\_\{t=1\}^\{T\}\\frac\{\\eta\_\{t\}^\{2\}\}\{2\}V\_\{t\}≤ln⁡M\+minm∈\{1,2\}g∈\[L\]​∑s=1Tηs​ℓ^s,\(m,g\)\\displaystyle\\leq\\ln M\+\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\eta\_\{s\}\\hat\{\\ell\}\_\{s,\(m,g\)\}∑t=1Tηt​∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)−minm∈\{1,2\}g∈\[L\]​∑s=1Tηs​ℓ^s,\(m,g\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\-\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\eta\_\{s\}\\hat\{\\ell\}\_\{s,\(m,g\)\}≤ln⁡M\+∑t=1Tηt22​Vt\\displaystyle\\leq\\ln M\+\\sum\_\{t=1\}^\{T\}\\frac\{\\eta\_\{t\}^\{2\}\}\{2\}V\_\{t\}\(16\)Since we choosentn\_\{t\}to be non\-increasing intt\(sinceΔt\\Delta\_\{t\}from Algorithm[2](https://arxiv.org/html/2607.09015#alg2)is non\-decreasing\), we haveηt≥ηT\\eta\_\{t\}\\geq\\eta\_\{T\}\. Therefore, we can say

∑t=1Tηt​∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)−minm∈\{1,2\}g∈\[L\]​∑s=1Tηs​ℓ^t,\(m,g\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\-\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\eta\_\{s\}\\hat\{\\ell\}\_\{t,\(m,g\)\}≤ηT​\(∑t=1T∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)−minm∈\{1,2\}g∈\[L\]​∑s=1Tℓ^t,\(m,g\)\)\\displaystyle\\leq\\eta\_\{T\}\\left\(\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\-\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\)\(17\)Combining Equation[17](https://arxiv.org/html/2607.09015#A6.E17)with Equation[16](https://arxiv.org/html/2607.09015#A6.E16)and dividing byηT\\eta\_\{T\}gives us themaster inequality:

∑t=1T∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)−minm∈\{1,2\}g∈\[L\]​∑s=1Tℓ^t,\(m,g\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\-\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\hat\{\\ell\}\_\{t,\(m,g\)\}≤ln⁡MηT\+12​ηT​∑t=1Tηt2​Vt\\displaystyle\\leq\\frac\{\\ln M\}\{\\eta\_\{T\}\}\+\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\(18\)We may take expectation over the master inequality to obtain

𝔼​\[∑t=1T∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\]−𝔼​\[minm∈\{1,2\}g∈\[L\]​∑s=1Tℓ^t,\(m,g\)\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]\-\\mathbb\{E\}\\left\[\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]≤𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\.\\displaystyle\\leq\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\.\(19\)The first term on the left\-hand side of the inequality is theweighted sum of loss estimators\. We relate this weighted sum to theactual observed lossby decomposing the expected cumulative observed loss𝔼​\[∑t=1Tℓt,it\]\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\ell\_\{t,i\_\{t\}\}\\right\]into𝔼​\[∑t=1T∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\]\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]and an additive expected bias term𝔼​\[ℬT\]\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]:

𝔼​\[∑t=1Tℓt,it\]=𝔼​\[∑t=1T∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\]\+𝔼​\[ℬT\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\ell\_\{t,i\_\{t\}\}\\right\]=\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]\+\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\(20\)Substituting Equation[20](https://arxiv.org/html/2607.09015#A6.E20)into Equation[19](https://arxiv.org/html/2607.09015#A6.E19),

𝔼​\[∑t=1Tℓt,it\]−𝔼​\[ℬT\]−𝔼​\[minm∈\{1,2\}g∈\[L\]​∑s=1Tℓ^t,\(m,g\)\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\ell\_\{t,i\_\{t\}\}\\right\]\-\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\-\\mathbb\{E\}\\left\[\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]≤𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]𝔼​\[∑t=1Tℓt,it\]−L∗−𝔼​\[ℬT\]−\(𝔼​\[minm∈\{1,2\}g∈\[L\]​∑s=1Tℓ^t,\(m,g\)\]−L∗\)\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\ell\_\{t,i\_\{t\}\}\\right\]\-L^\{\*\}\-\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\-\\left\(\\mathbb\{E\}\\left\[\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\\\ g\\in\[L\]\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]\-L^\{\*\}\\right\)≤𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]𝔼​\[∑t=1Tℓt,it\]−L∗−𝔼​\[ℬT\]−\(𝔼​\[minm∈\{1,2\}​∑s=1T∑i=1Kpt,m,i​ℓt,i\]−L∗\)\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\ell\_\{t,i\_\{t\}\}\\right\]\-L^\{\*\}\-\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\-\\left\(\\mathbb\{E\}\\left\[\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}\\sum\_\{s=1\}^\{T\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\\right\]\-L^\{\*\}\\right\)≤𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\(21\)𝔼​\[RegT\]−𝔼​\[ℬT\]−minm∈\{1,2\}⁡Rm\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]\-\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\-\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}R\_\{m\}≤𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\.\\displaystyle\\leq\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\.WhereL∗L^\{\*\}is the loss from following the optimal policy\. Equation[21](https://arxiv.org/html/2607.09015#A6.E21)is due to applying theoptimistic biasproperty from Lemma[F\.10](https://arxiv.org/html/2607.09015#A6.Thmtheorem10)\. Rearranging terms gives us the final regret decomposition

𝔼​\[RegT\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]≤minm∈\{1,2\}⁡Rm\+𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\+𝔼​\[ℬT\]\.\\displaystyle\\leq\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}R\_\{m\}\+\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\+\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\.∎

###### Lemma F\.12\(Bounding Second\-Order Terms\)\.

Suppose that the feedback graphGtG\_\{t\}associated with the graph feedback expert \(m=1m=1\) is strongly observable, and has independence number no greater thanα\\alpha\. If we assume the geometric grid ofγ\\gamma\-values is of sizeL=ln⁡TL=\\ln Tand thatqt,i≥ϵq\_\{t,i\}\\geq\\epsilon, we may boundVtV\_\{t\}independently for each expert such that

𝔼​\[Vt\]≤∑m=12∑g=1L∑i=1K\(qt,iQt,m,i\+γ\(g\)\)≤\{2​K​ln⁡T,if​m=1​dominates2​α​ln⁡\(4​Tα​ϵ\)​ln⁡\(T\),if​m=2​dominates,\\displaystyle\\mathbb\{E\}\\left\[V\_\{t\}\\right\]\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)\\leq\\begin\{cases\}2K\\ln T,&\\mathrm\{if\}\\;m=1\\;\\mathrm\{dominates\}\\\\ 2\\alpha\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln\\\!\\left\(T\\right\),&\\mathrm\{if\}\\;m=2\\;\\mathrm\{dominates\}\\end\{cases\},\(22\)where

Qt,m,i=\{qt,i,if​m=1∑j=1Kqt,j⋅𝕀​\{At,\(j,i\)=1\},if​m=2\.\\displaystyle Q\_\{t,m,i\}=\\begin\{cases\}q\_\{t,i\},&\\textrm\{if\}\\;m=1\\\\ \\sum\_\{j=1\}^\{K\}q\_\{t,j\}\\cdot\\mathbb\{I\}\\\{A\_\{t,\(j,i\)\}=1\\\},&\\textrm\{if\}\\;m=2\\end\{cases\}\.
###### Proof\.

We begin by proving the statement for whenm=1m=1\(bandit feedback expert\) dominates\. Specifically, in this case we assume the regret of expertm=1m=1consistently out\-performs that of expertm=2m=2, thus the𝔼​\[Vt\]\\mathbb\{E\}\[V\_\{t\}\]term associated withm=1m=1dominates\. We begin with the definition ofVtV\_\{t\}with fixedm=1m=1

𝔼​\[Vt\]\\displaystyle\\mathbb\{E\}\\left\[V\_\{t\}\\right\]=∑m=12∑g=1Lμt,\(1,g\)​𝔼​\[ℓ^t,\(1,g\)2\]\\displaystyle=\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(1,g\)\}\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(1,g\)\}^\{2\}\\right\]≤∑m=12∑g=1Lμt,\(1,g\)​∑i=1Kpt,1,iqt,i\+γ\(g\)\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(1,g\)\}\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,1,i\}\}\{q\_\{t,i\}\+\\gamma^\{\(g\)\}\}≤∑m=12∑g=1L∑i=1Kqt,iqt,i\+γ\(g\)\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\}\{q\_\{t,i\}\+\\gamma^\{\(g\)\}\}\(23\)≤∑m=12∑g=1L∑i=1K1\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\sum\_\{i=1\}^\{K\}1≤2​K​ln⁡T,\\displaystyle\\leq 2K\\ln T,where Equation[23](https://arxiv.org/html/2607.09015#A6.E23)is a result of applying the definition ofqt,iq\_\{t,i\}\. We continue by proving the statement for whenm=2m=2\(graph feedback dominates\)\. Using a similar line of reasoning to the case whenm=1m=1dominates, we begin with the definition ofVtV\_\{t\}with fixedm=2m=2

𝔼​\[Vt\]\\displaystyle\\mathbb\{E\}\\left\[V\_\{t\}\\right\]=∑m=12∑g=1Lμt,\(2,g\)​𝔼​\[ℓ^t,\(2,g\)2\]\\displaystyle=\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(2,g\)\}\\mathbb\{E\}\\left\[\\hat\{\\ell\}\_\{t,\(2,g\)\}^\{2\}\\right\]≤∑m=12∑g=1Lμt,\(2,g\)​∑i=1Kpt,2,i∑j:At,\(j,i\)=1qt,j\+γ\(g\)\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(2,g\)\}\\sum\_\{i=1\}^\{K\}\\frac\{p\_\{t,2,i\}\}\{\\sum\_\{j:\{A\}\_\{t,\(j,i\)\}=1\}q\_\{t,j\}\+\\gamma^\{\(g\)\}\}≤∑m=12∑g=1L∑i=1Kqt,i∑j:At,\(j,i\)=1qt,j\+γ\(g\)\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\}\{\\sum\_\{j:\{A\}\_\{t,\(j,i\)\}=1\}q\_\{t,j\}\+\\gamma^\{\(g\)\}\}\(24\)≤∑m=12∑g=1L∑i=1Kqt,i∑j:At,\(j,i\)=1qt,j\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\sum\_\{i=1\}^\{K\}\\frac\{q\_\{t,i\}\}\{\\sum\_\{j:\{A\}\_\{t,\(j,i\)\}=1\}q\_\{t,j\}\}≤∑m=12∑g=1L∑i=1Kα​ln⁡\(4​Tα​ϵ\)\\displaystyle\\leq\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\sum\_\{i=1\}^\{K\}\\alpha\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\(25\)≤2​α​ln⁡\(4​Tα​ϵ\)​ln⁡\(T\),\\displaystyle\\leq 2\\alpha\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln\\\!\\left\(T\\right\),where Equation[24](https://arxiv.org/html/2607.09015#A6.E24)is a result of applying the definition ofqt,iq\_\{t,i\}, and Equation[25](https://arxiv.org/html/2607.09015#A6.E25)is due to Lemma[F\.6](https://arxiv.org/html/2607.09015#A6.Thmtheorem6)\. ∎

##### Proof of Theorem[4\.9](https://arxiv.org/html/2607.09015#S4.Thmtheorem9)\.

We now use the preceding lemmas to prove that if there areM=2M=2experts: one bandit\-feedback expert and one graph\-feedback expert \(tuned for known independence numberα\\alpha\), then Algorithm[2](https://arxiv.org/html/2607.09015#alg2)satisfies

𝔼​\[RegSq​\(T\)\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\_\{Sq\}\}\(T\)\\right\]≤O​\(min⁡\{R1\+ln⁡\(K​T​ln⁡T\)​K​T​ln⁡M​ln⁡T,R2\+ln⁡\(α​T​ln⁡\(T/α​ϵ\)​ln⁡T\)​α​T​ln⁡\(T/α​ϵ\)​ln⁡M​ln⁡T\}\)\\displaystyle\\leq O\\\!\\left\(\\min\\left\\\{R\_\{1\}\+\\ln\\\!\\left\(KT\\ln T\\right\)\\sqrt\{KT\\ln M\\ln T\},\\right\.\\right\.\\left\.\\left\.R\_\{2\}\+\\ln\\\!\\left\(\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln T\\right\)\\sqrt\{\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln M\\ln T\}\\right\\\}\\right\)
UsingR1=O~​\(K​T​RegSq​\(T\)\)R\_\{1\}=\\widetilde\{O\}\(\\sqrt\{KT\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\)from Theorem[F\.1](https://arxiv.org/html/2607.09015#A6.Thmtheorem1)andR2=O~​\(α​T​RegSq​\(T\)\+α​K​T​εn\)R\_\{2\}=\\widetilde\{O\}\(\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\sqrt\{\\alpha KT\}\\,\\varepsilon\_\{n\}\)from Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7), we obtain the regret bound

O~​\(min⁡\{K​T​RegSq​\(T\),α​T​RegSq​\(T\)\+α​K​T​εn\}\)\.\\widetilde\{O\}\\\!\\left\(\\min\\\{\\sqrt\{KT\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\},\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\sqrt\{\\alpha KT\}\\,\\varepsilon\_\{n\}\\\}\\right\)\.
###### Proof\.

We restate the decomposition derived in Lemma[F\.11](https://arxiv.org/html/2607.09015#A6.Thmtheorem11),

𝔼​\[RegT\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]≤minm∈\{1,2\}⁡Rm\+𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\+𝔼​\[ℬT\]\.\\displaystyle\\leq\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}R\_\{m\}\+\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\+\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\.\(26\)We begin by bounding𝔼​\[ℬT\]\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]\. Rearranging Equation[20](https://arxiv.org/html/2607.09015#A6.E20)we get

𝔼​\[ℬT\]\\displaystyle\\mathbb\{E\}\[\\mathcal\{B\}\_\{T\}\]=𝔼​\[∑t=1Tℓt,it\]−𝔼​\[∑t=1T∑m=12∑g=1Lμt,\(m,g\)​ℓ^t,\(m,g\)\]\\displaystyle\\;=\\;\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\ell\_\{t,i\_\{t\}\}\\right\]\-\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\hat\{\\ell\}\_\{t,\(m,g\)\}\\right\]=∑t=1T∑i=1Kqt,i​ℓt,i−∑t=1T∑m=12∑g=1Lμt,\(m,g\)​∑i=1Kpt,m,i​ℓt,i​Qt,m,iQt,m,i\+γ\(g\)\\displaystyle\\;=\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{K\}q\_\{t,i\}\\ell\_\{t,i\}\-\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\\frac\{Q\_\{t,m,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\(27\)We may further expand Equation[27](https://arxiv.org/html/2607.09015#A6.E27):

∑t=1T∑i=1Kqt,i​ℓt,i−∑t=1T∑m=12∑g=1Lμt,\(m,g\)​∑i=1Kpt,m,i​ℓt,i​Qt,m,iQt,m,i\+γ\(g\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{K\}q\_\{t,i\}\\ell\_\{t,i\}\-\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\\frac\{Q\_\{t,m,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}=∑t=1T∑m=12∑g=1Lμt,\(m,g\)​∑i=1Kpt,m,i​ℓt,i−∑t=1T∑m=12∑g=1Lμt,\(m,g\)​∑i=1Kpt,m,i​ℓt,i​Qt,m,iQt,m,i\+γ\(g\)\\displaystyle\\;=\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\-\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\\frac\{Q\_\{t,m,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}=∑t=1T∑m=12∑g=1Lμt,\(m,g\)​∑i=1Kpt,m,i​ℓt,i​\(1−Qt,m,iQt,m,i\+γ\(g\)\)\\displaystyle\\;=\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\\left\(1\-\\frac\{Q\_\{t,m,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)=∑t=1T∑m=12∑g=1Lμt,\(m,g\)​∑i=1Kpt,m,i​ℓt,i​\(γ\(g\)Qt,m,i\+γ\(g\)\)\\displaystyle\\;=\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\sum\_\{i=1\}^\{K\}p\_\{t,m,i\}\\ell\_\{t,i\}\\left\(\\frac\{\\gamma^\{\(g\)\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)≤∑t=1T∑m=12∑g=1Lμt,\(m,g\)​γ\(g\)​∑i=1K\(pt,m,iQt,m,i\+γ\(g\)\)\\displaystyle\\;\\leq\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\mu\_\{t,\(m,g\)\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{p\_\{t,m,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)≤∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,m,i\+γ\(g\)\)\\displaystyle\\;\\leq\\;\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)\(28\)Next, we bound𝔼​\[ln⁡MηT\]\+𝔼​\[12​ηT​∑t=1Tηt2​Vt\]\\mathbb\{E\}\\left\[\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\right\]\+\\mathbb\{E\}\\left\[\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}\\right\]\.

ln⁡MηT\+12​ηT​∑t=1Tηt2​Vt\\displaystyle\\frac\{\\ln M\}\{\\eta\_\{T\}\}\+\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}^\{2\}V\_\{t\}=ln⁡MηT\+12​ηT​∑t=1Tln⁡M1\+Δt−1​Vt\\displaystyle=\\frac\{\\ln M\}\{\\eta\_\{T\}\}\+\\frac\{1\}\{2\\eta\_\{T\}\}\\sum\_\{t=1\}^\{T\}\\frac\{\\ln M\}\{1\+\\Delta\_\{t\-1\}\}V\_\{t\}=ln⁡MηT​\(1\+12​∑t=1TVt1\+Δt−1\)\\displaystyle=\\frac\{\\ln M\}\{\\eta\_\{T\}\}\\left\(1\+\\frac\{1\}\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{V\_\{t\}\}\{1\+\\Delta\_\{t\-1\}\}\\right\)=ln⁡M​1\+ΔT−1​\(1\+12​∑t=1TVt1\+Δt−1\)\\displaystyle=\\sqrt\{\\ln M\}\\sqrt\{1\+\\Delta\_\{T\-1\}\}\\left\(1\+\\frac\{1\}\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{V\_\{t\}\}\{1\+\\Delta\_\{t\-1\}\}\\right\)≤ln⁡M​1\+ΔT−1​\(1\+∑t=1TVtΔt\)\\displaystyle\\leq\\sqrt\{\\ln M\}\\sqrt\{1\+\\Delta\_\{T\-1\}\}\\left\(1\+\\sum\_\{t=1\}^\{T\}\\frac\{V\_\{t\}\}\{\\Delta\_\{t\}\}\\right\)\(29\)≤ln⁡M​1\+ΔT−1​\(1\+∑t=1TVt∑s=1tVs\)\\displaystyle\\leq\\sqrt\{\\ln M\}\\sqrt\{1\+\\Delta\_\{T\-1\}\}\\left\(1\+\\sum\_\{t=1\}^\{T\}\\frac\{V\_\{t\}\}\{\\sum\_\{s=1\}^\{t\}V\_\{s\}\}\\right\)≤ln⁡M​1\+ΔT−1​\(2\+ln⁡\(∑t=1TVt\)\)\\displaystyle\\leq\\sqrt\{\\ln M\}\\sqrt\{1\+\\Delta\_\{T\-1\}\}\\left\(2\+\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}V\_\{t\}\\right\)\\right\)\(30\)≤ln⁡M​1\+ΔT−1​\(2\+ln⁡\(ΔT\)\)\\displaystyle\\leq\\sqrt\{\\ln M\}\\sqrt\{1\+\\Delta\_\{T\-1\}\}\\left\(2\+\\ln\\\!\\left\(\\Delta\_\{T\}\\right\)\\right\)≤ln⁡\(ΔT\)​ln⁡M\+2​ln⁡M\+ln⁡\(ΔT\)​ΔT−1​ln⁡M\+2​ΔT−1​ln⁡M\\displaystyle\\leq\\ln\(\\Delta\_\{T\}\)\\sqrt\{\\ln M\}\+2\\sqrt\{\\ln M\}\+\\ln\(\\Delta\_\{T\}\)\\sqrt\{\\Delta\_\{T\-1\}\\ln M\}\+2\\sqrt\{\\Delta\_\{T\-1\}\\ln M\}≤ln⁡\(ΔT\)​ΔT−1​ln⁡M\+c1,\\displaystyle\\leq\\ln\(\\Delta\_\{T\}\)\\sqrt\{\\Delta\_\{T\-1\}\\ln M\}\+c\_\{1\},\(31\)where Equation[29](https://arxiv.org/html/2607.09015#A6.E29)is due toΔt=Vt\+Δt−1≤1\+Δt−1\\Delta\_\{t\}=V\_\{t\}\+\\Delta\_\{t\-1\}\\leq 1\+\\Delta\_\{t\-1\}, and Equation[30](https://arxiv.org/html/2607.09015#A6.E30)is due to the following fact:∑t=1Txt∑s=1txs≤1\+ln⁡\(∑t=1Txt\)\\sum\_\{t=1\}^\{T\}\\frac\{x\_\{t\}\}\{\\sum\_\{s=1\}^\{t\}x\_\{s\}\}\\leq 1\+\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}x\_\{t\}\\right\)\. For cleaner notation, in the Equation[31](https://arxiv.org/html/2607.09015#A6.E31)we absorb all dominated terms into the constantc1c\_\{1\}\. We continue by plugging Equation[31](https://arxiv.org/html/2607.09015#A6.E31)and Equation[28](https://arxiv.org/html/2607.09015#A6.E28)into Equation[26](https://arxiv.org/html/2607.09015#A6.E26)to get

𝔼​\[RegT\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\}\_\{T\}\\right\]≤minm∈\{1,2\}⁡Rm\+𝔼​\[ln⁡\(ΔT\)\]​𝔼​\[ΔT−1\]​ln⁡M\+∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,m,i\+γ\(g\)\)\+c1\\displaystyle\\leq\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}R\_\{m\}\+\\mathbb\{E\}\[\\ln\(\\Delta\_\{T\}\)\]\\sqrt\{\\mathbb\{E\}\[\\Delta\_\{T\-1\}\]\\ln M\}\+\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)\+c\_\{1\}≤minm∈\{1,2\}⁡Rm\+ln⁡\(∑t=1TVt\)​\(∑t=1T−1Vt\)​ln⁡M\+∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,m,i\+γ\(g\)\)\+c1⏟CABS\-D overhead\\displaystyle\\leq\\min\_\{\\begin\{subarray\}\{c\}m\\in\\\{1,2\\\}\\end\{subarray\}\}R\_\{m\}\+\\underbrace\{\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}V\_\{t\}\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}V\_\{t\}\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,m,i\}\+\\gamma^\{\(g\)\}\}\\right\)\+c\_\{1\}\}\_\{\\text\{CABS\-D overhead\}\}\(32\)Since the regret contributions of both experts cannot be simultaneously large, according to the first term if

R1≤R2R\_\{1\}\\leq R\_\{2\}then the analysis ensures that terms associated with

R2R\_\{2\}do not accumulate \(the same applies if

R1≥R2R\_\{1\}\\geq R\_\{2\}\)\. This allows us to divide the analysis of theCABS\-D overheadinto two cases: 1\) where

m=1m=1\(bandit feedback\) is the best expert, and 2\) where

m=2m=2\(graph feedback\) is the best expert\. We begin by examining the first case:

When

m=1m=1:

ln⁡\(∑t=1TVt\)​\(∑t=1T−1Vt\)​ln⁡M\+∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,1,i\+γ\(g\)\)\+c1\\displaystyle\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}V\_\{t\}\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}V\_\{t\}\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,1,i\}\+\\gamma^\{\(g\)\}\}\\right\)\+c\_\{1\}≤ln⁡\(∑t=1T2​K​ln⁡T\)​\(∑t=1T−12​K​ln⁡T\)​ln⁡M\+∑t=1T2​K​∑g=1Lγ\(g\)\+c1\\displaystyle\\leq\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}2K\\ln T\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}2K\\ln T\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}2K\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\+c\_\{1\}\(33\)≤ln⁡\(2​K​T​ln⁡T\)​2​K​\(T−1\)​ln⁡M​ln⁡T\+2​K​T​∑g=1Lγ\(g\)\+c1,\\displaystyle\\leq\\ln\\\!\\left\(2KT\\ln T\\right\)\\sqrt\{2K\(T\-1\)\\ln M\\ln T\}\+2KT\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\+c\_\{1\},where Equation[33](https://arxiv.org/html/2607.09015#A6.E33)is due to Lemma[F\.12](https://arxiv.org/html/2607.09015#A6.Thmtheorem12)\. Recall that the algorithm aggregates a set of experts parameterized by a geometric gridΓ\\Gamma\. By the properties of CABS\-D \(Lemma[F\.11](https://arxiv.org/html/2607.09015#A6.Thmtheorem11)\), the total regret is bounded by the regret of the best fixed expert in the grid, plus an additive expert\-dependent overhead\. Therefore, we bound the regret by choosing the specificγ\(g\)∈Γ\\gamma^\{\(g\)\}\\in\\Gammathat minimizes the bound for the specific feedback structure\. BecauseΓ\\Gammais a dyadic grid of sizeL=ln⁡TL=\\ln T, for any optimal tuning parameterγ∗\\gamma^\{\*\}, there exists a grid pointγ\(g\)\\gamma^\{\(g\)\}such thatγ\(g\)≈γ∗\\gamma^\{\(g\)\}\\approx\\gamma^\{\*\}up to a small constant factor\. Whenγ\(g\)=1K​T\\gamma^\{\(g\)\}=\\frac\{1\}\{\\sqrt\{KT\}\}, we get

ln⁡\(∑t=1TVt\)​\(∑t=1T−1Vt\)​ln⁡M\+∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,1,i\+γ\(g\)\)\+c1\\displaystyle\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}V\_\{t\}\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}V\_\{t\}\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,1,i\}\+\\gamma^\{\(g\)\}\}\\right\)\+c\_\{1\}≤ln⁡\(2​K​T​ln⁡T\)​2​K​\(T−1\)​ln⁡M​ln⁡T\+2​ln⁡T​K​T\+c1\\displaystyle\\leq\\ln\\\!\\left\(2KT\\ln T\\right\)\\sqrt\{2K\(T\-1\)\\ln M\\ln T\}\+2\\ln T\\sqrt\{KT\}\+c\_\{1\}≤O​\(ln⁡\(K​T​ln⁡T\)​K​T​ln⁡M​ln⁡T\),\\displaystyle\\leq O\\\!\\left\(\\ln\\\!\\left\(KT\\ln T\\right\)\\sqrt\{KT\\ln M\\ln T\}\\right\),\(34\)Similarly, whenm=2m=2:

ln⁡\(∑t=1TVt\)​\(∑t=1T−1Vt\)​ln⁡M\+∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,2,i\+γ\(g\)\)\+c1\\displaystyle\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}V\_\{t\}\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}V\_\{t\}\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,2,i\}\+\\gamma^\{\(g\)\}\}\\right\)\+c\_\{1\}≤ln⁡\(∑t=1T2​α​ln⁡\(4​Tα​ϵ\)​ln⁡T\)​\(∑t=1T−12​α​ln⁡\(4​Tα​ϵ\)​ln⁡T\)​ln⁡M\+∑t=1T2​α​ln⁡\(4​Tα​ϵ\)​∑g=1Lγ\(g\)\+c1\\displaystyle\\leq\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}2\\alpha\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln T\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}2\\alpha\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln T\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}2\\alpha\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\+c\_\{1\}≤ln⁡\(2​α​T​ln⁡\(4​Tα​ϵ\)​ln⁡T\)​\(2​α​\(T−1\)​ln⁡\(4​Tα​ϵ\)​ln⁡T​ln⁡M\)\+2​α​T​ln⁡\(4​Tα​ϵ\)​∑g=1Lγ\(g\)\+c1\.\\displaystyle\\leq\\ln\\\!\\left\(2\\alpha T\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln T\\right\)\\sqrt\{\\left\(2\\alpha\(T\-1\)\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln T\\ln M\\right\)\}\+2\\alpha T\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\+c\_\{1\}\.By settingγ\(g\)=1α​T\\gamma^\{\(g\)\}=\\frac\{1\}\{\\sqrt\{\\alpha T\}\}, we get

ln⁡\(∑t=1TVt\)​\(∑t=1T−1Vt\)​ln⁡M\+∑t=1T∑m=12∑g=1Lγ\(g\)​∑i=1K\(qt,iQt,2,i\+γ\(g\)\)\+c1\\displaystyle\\ln\\\!\\left\(\\sum\_\{t=1\}^\{T\}V\_\{t\}\\right\)\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\-1\}V\_\{t\}\\right\)\\ln M\}\+\\sum\_\{t=1\}^\{T\}\\sum\_\{m=1\}^\{2\}\\sum\_\{g=1\}^\{L\}\\,\\gamma^\{\(g\)\}\\sum\_\{i=1\}^\{K\}\\left\(\\frac\{q\_\{t,i\}\}\{Q\_\{t,2,i\}\+\\gamma^\{\(g\)\}\}\\right\)\+c\_\{1\}≤ln⁡\(2​α​T​ln⁡\(4​Tα​ϵ\)​ln⁡T\)​\(2​α​\(T−1\)​ln⁡\(4​Tα​ϵ\)​ln⁡M​ln⁡T\)\+2​α​T​ln⁡\(4​Tα​ϵ\)​ln⁡T\+c1\\displaystyle\\leq\\ln\\\!\\left\(2\\alpha T\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln T\\right\)\\sqrt\{\\left\(2\\alpha\(T\-1\)\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln M\\ln T\\right\)\}\+2\\sqrt\{\\alpha T\}\\ln\\\!\\left\(\\frac\{4T\}\{\\alpha\\epsilon\}\\right\)\\ln T\+c\_\{1\}≤O​\(ln⁡\(α​T​ln⁡\(T/α​ϵ\)​ln⁡T\)​α​T​ln⁡\(T/α​ϵ\)​ln⁡M​ln⁡T\)\.\\displaystyle\\leq O\\\!\\left\(\\ln\\\!\\left\(\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln T\\right\)\\sqrt\{\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln M\\ln T\}\\right\)\.\(35\)Combining the two cases \(from Equations[34](https://arxiv.org/html/2607.09015#A6.E34)and[35](https://arxiv.org/html/2607.09015#A6.E35)\) and plugging them into Equation[32](https://arxiv.org/html/2607.09015#A6.E32)yields

𝔼​\[RegSq​\(T\)\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Reg\_\{Sq\}\}\(T\)\\right\]≤O\(min\{R1\+ln\(KTlnT\)K​T​ln⁡M​ln⁡T,\\displaystyle\\leq O\\\!\\left\(\\min\\left\\\{R\_\{1\}\+\\ln\\\!\\left\(KT\\ln T\\right\)\\sqrt\{KT\\ln M\\ln T\},\\right\.\\right\.R2\+ln\(αTln\(T/αϵ\)lnT\)α​T​ln⁡\(T/α​ϵ\)​ln⁡M​ln⁡T\}\)\\displaystyle\\quad\\left\.\\left\.R\_\{2\}\+\\ln\\\!\\left\(\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln T\\right\)\\sqrt\{\\alpha T\\ln\(T/\\alpha\\epsilon\)\\ln M\\ln T\}\\right\\\}\\right\)If we use Theorem[F\.1](https://arxiv.org/html/2607.09015#A6.Thmtheorem1)to obtainR1R\_\{1\}\(the regret of the bandit feedback expert\) and we use Theorem[4\.7](https://arxiv.org/html/2607.09015#S4.Thmtheorem7)to obtainR2R\_\{2\}\(the regret of the graph feedback expert\), we may plug them in to obtain \(after absorbing polylogs\)

𝔼​\[RegT\]\\displaystyle\\mathbb\{E\}\[\\mathrm\{Reg\}\_\{T\}\]≤O~​\(min⁡\{K​T​RegSq​\(T\)\+K​T,α​T​RegSq​\(T\)\+α​K​T​εn\+α​T\}\)\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(\\min\\left\\\{\\sqrt\{KT\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\sqrt\{KT\},\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\sqrt\{\\alpha KT\}\\,\\varepsilon\_\{n\}\+\\sqrt\{\\alpha T\}\\right\\\}\\right\)≤O~​\(min⁡\{K​T​RegSq​\(T\),α​T​RegSq​\(T\)\+α​K​T​εn\}\)\.\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(\\min\\\{\\sqrt\{KT\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\},\\sqrt\{\\alpha T\\,\\mathrm\{Reg\_\{Sq\}\}\(T\)\}\+\\sqrt\{\\alpha KT\}\\,\\varepsilon\_\{n\}\\\}\\right\)\.\(36\)∎

##### Deriving Corollary[4\.10](https://arxiv.org/html/2607.09015#S4.Thmtheorem10)\.

Corollary[4\.10](https://arxiv.org/html/2607.09015#S4.Thmtheorem10)follows by substitutingα=Km\+1\\alpha=\\frac\{K\}\{m\+1\}from Theorem[F\.9](https://arxiv.org/html/2607.09015#A6.Thmtheorem9)into the general regret bound of Theorem[4\.9](https://arxiv.org/html/2607.09015#S4.Thmtheorem9), and applying the standard square\-loss regret bound for linear regression oracles\[[20](https://arxiv.org/html/2607.09015#bib.bib4)\],RegSq​\(T\)=O​\(d​log⁡\(Td\)\)\\mathrm\{Reg\}\_\{\\mathrm\{Sq\}\}\(T\)=O\(d\\log\\left\(\\frac\{T\}\{d\}\\right\)\)\.