Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

# 1 Introduction
Source: [https://arxiv.org/html/2607.02891](https://arxiv.org/html/2607.02891)
\\OneAndAHalfSpacedXI\\EquationsNumberedThrough\\TheoremsNumberedThrough\\ECRepeatTheorems

\\RUNAUTHOR

Author\\RUNTITLENon\-stationary Linear Bandits via Misspecification Reductions

\\TITLE

Dynamic Regret for Non\-Stationary Linear Bandits via Misspecification Reductions

\\ARTICLEAUTHORS\\AUTHOR

Zihao Hu1,3, Yuan Yao1, Jiheng Zhang1,3, and Zhengyuan Zhou2\\AFFDepartment of Mathematics, The Hong Kong University of Science and Technology1 Stern School of Business, New York University2 Department of IEDA, The Hong Kong University of Science and Technology3 \\EMAIL\{zihaohu, yuany, jiheng\}@ust\.hk, zz26@stern\.nyu\.edu

\\ABSTRACT

Many online decision\-making problems involve both round\-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve\. Motivated by these applications, we study non\-stationary linear bandits with round\-specific feasible decision sets\. Existing methods that obtain the optimalO~​\(T2/3​PT1/3\)\\widetilde\{O\}\(T^\{2/3\}P\_\{T\}^\{1/3\}\)dependence, wherePTP\_\{T\}is the path length of the reward\-parameter sequence, impose an orthogonal\-structure assumption on round\-specific decision sets, which can be restrictive in contextual applications\. We address this gap through a unified misspecification\-reduction viewpoint: after partitioning the horizon into blocks, we relate each block’s dynamic regret to regret against a fixed\-parameter linear bandit benchmark, with the within\-block parameter drift entering as bounded misspecification\. Restarting algorithms with misspecification\-dependent regret guarantees then yields the optimalT2/3​PT1/3T^\{2/3\}P\_\{T\}^\{1/3\}dynamic\-regret dependence for both linear bandits with general compact decision sets andKK\-armed contextual linear bandits\.

\\KEYWORDS

non\-stationary online learning, linear bandits, dynamic regret

Many online decision\-making problems, such as online ad display and contextual treatment assignment, involve choosing among actions represented by feature vectors that can include both the current context and action\-specific information\. In these applications, feasible actions are naturally round\-specific: they depend on the current user or patient and, in ad display, on the ad impressions currently available\. Linear bandits\(Abbasi\-Yadkoriet al\.,[2011](https://arxiv.org/html/2607.02891#bib.bib1); Chuet al\.,[2011](https://arxiv.org/html/2607.02891#bib.bib22)\)provide a standard model for such problems: each feasible decision is represented by a feature vector, and its expected reward is modeled as the inner product between this feature vector and an unknown parameter vector\. The standard performance measure for a policy is regret, which compares the policy’s cumulative reward with that of a benchmark\. In the classical stationary model, the unknown parameter is fixed, and this benchmark selects the best feasible decision under the fixed parameter at each round\.

In many applications, however, the relationship between actions and expected rewards may drift over time: user preferences may evolve, market conditions may shift, and patient responses to treatments may change\. This concern has motivated a broad literature on non\-stationary stochastic optimization and non\-stationary bandit learning\(Besbes and Zeevi,[2011](https://arxiv.org/html/2607.02891#bib.bib4); Besbeset al\.,[2015](https://arxiv.org/html/2607.02891#bib.bib5); Keskin and Zeevi,[2017](https://arxiv.org/html/2607.02891#bib.bib11); Chenet al\.,[2019](https://arxiv.org/html/2607.02891#bib.bib6); Cheunget al\.,[2022](https://arxiv.org/html/2607.02891#bib.bib7); Wang,[2025](https://arxiv.org/html/2607.02891#bib.bib27)\)\. The non\-stationary linear bandit model captures such drift by allowing the reward parameter to change across rounds\. Formally, consider an online decision\-making problem overTTrounds: at each roundtt, the learner observes a feasible decision set𝒜t⊆ℝd\\mathcal\{A\}\_\{t\}\\subseteq\\mathbb\{R\}^\{d\}, chooses an actionat∈𝒜ta\_\{t\}\\in\\mathcal\{A\}\_\{t\}, and receives a reward with conditional mean⟨at,θt⟩\\langle a\_\{t\},\\theta\_\{t\}\\rangle, whereθt\\theta\_\{t\}is the current reward parameter\. FollowingCheunget al\.\([2022](https://arxiv.org/html/2607.02891#bib.bib7)\), the non\-stationarity of a problem instance is measured by the path length of the reward\-parameter sequence,PT:=∑t=1T−1‖θt\+1−θt‖2P\_\{T\}:=\\sum\_\{t=1\}^\{T\-1\}\\\|\\theta\_\{t\+1\}\-\\theta\_\{t\}\\\|\_\{2\}\. For a policyπ\\pi, withata\_\{t\}denoting its round\-ttaction, define the dynamic regret

RegT⁡\(π\):=𝔼​∑t=1T\[maxa∈𝒜t⁡⟨a,θt⟩−⟨at,θt⟩\],\\operatorname\{Reg\}\_\{T\}\(\\pi\):=\\mathbb\{E\}\\sum\_\{t=1\}^\{T\}\\left\[\\max\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\langle a,\\theta\_\{t\}\\rangle\-\\langle a\_\{t\},\\theta\_\{t\}\\rangle\\right\],which compares the learner’s expected reward at each round with that of the best feasible action under the current parameter\. The goal is to achieve small dynamic regret whenPTP\_\{T\}is moderate\.

Several works study non\-stationary linear bandits under path\-length constraint\(Russacet al\.,[2019](https://arxiv.org/html/2607.02891#bib.bib15); Cheunget al\.,[2022](https://arxiv.org/html/2607.02891#bib.bib7); Zhaoet al\.,[2021](https://arxiv.org/html/2607.02891#bib.bib20); Wanget al\.,[2025](https://arxiv.org/html/2607.02891#bib.bib18)\)\. However, existing rate\-optimal approaches for non\-stationary linear bandits do not fully cover the case of round\-specific feasible decision sets\.Cheunget al\.\([2022](https://arxiv.org/html/2607.02891#bib.bib7)\)obtain theO~​\(T2/3​PT1/3\)\\widetilde\{O\}\(T^\{2/3\}P\_\{T\}^\{1/3\}\)upper bound in this regime by requiring all feasible actions to lie on a fixed set of orthogonal directions, and establish the correspondingΩ​\(T2/3​PT1/3\)\\Omega\(T^\{2/3\}P\_\{T\}^\{1/3\}\)lower bound\. The orthogonal\-direction assumption can be restrictive in contextual applications, where users, ad opportunities, and patient\-treatment pairs are often described by context\-dependent attributes, leading to feature vectors with shared structure rather than scalar multiples of fixed orthogonal basis directions\. This restriction leaves open the problem of achieving the optimalT2/3​PT1/3T^\{2/3\}P\_\{T\}^\{1/3\}dynamic\-regret dependence for non\-stationary linear bandits with general round\-specific feasible decision sets\(Zhaoet al\.,[2021](https://arxiv.org/html/2607.02891#bib.bib20); Wanget al\.,[2025](https://arxiv.org/html/2607.02891#bib.bib18)\)\.

Our contributions\.We show that the optimalT2/3​PT1/3T^\{2/3\}P\_\{T\}^\{1/3\}dynamic\-regret dependence can be achieved for round\-specific decision sets without the orthogonal\-direction assumption\. We prove this in two settings: general compact decision sets andKK\-armed contextual linear bandits\.

The key idea is a local misspecification reduction: parameter drift within each block is treated as model misspecification, so the desired dynamic\-regret rate follows from blockwise regret guarantees that*adapt*to the misspecification level\. The reduction is based on the following blockwise bound\. On a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}, usingθτ\\theta\_\{\\tau\}as the block comparator gives

supt∈ℐsupa∈𝒜t\|⟨a,θt−θτ⟩\|≤L​Pℐ,\\sup\_\{t\\in\\mathcal\{I\}\}\\sup\_\{a\\in\\mathcal\{A\}\_\{t\}\}\|\\langle a,\\theta\_\{t\}\-\\theta\_\{\\tau\}\\rangle\|\\leq LP\_\{\\mathcal\{I\}\},whereLLupper bounds the norms of feasible actions andPℐP\_\{\\mathcal\{I\}\}denotes the path length of the parameter sequence restricted to blockℐ\\mathcal\{I\}\. In general, if a block comparatorθ¯\\bar\{\\theta\}has uniform error at mostε\\varepsilononℐ\\mathcal\{I\}, dynamic regret on the block is bounded by two terms: regret against the blockwise fixed\-parameter benchmark induced byθ¯\\bar\{\\theta\}, and an approximation termO​\(n​ε\)O\(n\\varepsilon\)\. The first term is precisely the regret of a misspecified linear bandit on the block, with misspecification levelε\\varepsilon\. Consequently, a guarantee of orderO~​\(n\+n​ε\)\\widetilde\{O\}\(\\sqrt\{n\}\+n\\varepsilon\)yields the block dynamic\-regret boundO~​\(n\+n​L​Pℐ\)\\widetilde\{O\}\(\\sqrt\{n\}\+nLP\_\{\\mathcal\{I\}\}\)after takingε=L​Pℐ\\varepsilon=LP\_\{\\mathcal\{I\}\}\. Restarting on blocks of lengthΔ\\Deltaand summing over blocks gives the tradeoffO~​\(T/Δ\+Δ​PT\)\\widetilde\{O\}\(T/\\sqrt\{\\Delta\}\+\\Delta P\_\{T\}\)\. Choosing the optimalΔ\\Deltagives theO~​\(T2/3​PT1/3\)\\widetilde\{O\}\(T^\{2/3\}P\_\{T\}^\{1/3\}\)dependence\.

We obtain the following guarantees in two settings:

- •General compact decision sets\.For linear bandits with general compact, adaptive non\-anticipating decision sets and an oblivious parameter path, Theorem[3\.4](https://arxiv.org/html/2607.02891#S3.Thmtheorem4)shows that a restarted CORRAL aggregation of SquareCB\.Lin\+ bases\(Fosteret al\.,[2020](https://arxiv.org/html/2607.02891#bib.bib21)\)achieves the expected dynamic\-regret bound O~​\(d​T\+L1/3​d5/6​T2/3​PT1/3\)\.\\widetilde\{O\}\\\!\\left\(d\\sqrt\{T\}\+L^\{1/3\}d^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}\\right\)\.Thus the method attains the optimalT2/3​PT1/3T^\{2/3\}P\_\{T\}^\{1/3\}dynamic\-regret dependence, matching the lower\-bound dependence ofCheunget al\.\([2022](https://arxiv.org/html/2607.02891#bib.bib7)\)while allowing general round\-specific compact action sets beyond the orthogonal\-direction structure\.
- •KK\-armed contextual linear bandits\.ForKK\-armed contextual linear bandits under an oblivious adversary, withΛK:=1\+log⁡K\\Lambda\_\{K\}:=1\+\\log K, Theorem[4\.3](https://arxiv.org/html/2607.02891#S4.Thmtheorem3)shows that restarting SupLinUCB\(Chuet al\.,[2011](https://arxiv.org/html/2607.02891#bib.bib22)\)achieves the expected dynamic\-regret bound O~​\(d​T​ΛK\+d​ΛK5/6​T2/3​PT1/3\)\.\\widetilde\{O\}\\\!\\left\(\\sqrt\{dT\}\\,\\Lambda\_\{K\}\+\\sqrt\{d\}\\,\\Lambda\_\{K\}^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}\\right\)\.This again matches the optimal dependence onTTandPTP\_\{T\}, as certified by Proposition[4\.5](https://arxiv.org/html/2607.02891#S4.Thmtheorem5)\.

Unlike the original SquareCB\.Lin\+ misspecification guarantee ofFosteret al\.\([2020](https://arxiv.org/html/2607.02891#bib.bib21)\), which considers oblivious sequences, our setting allows adaptive non\-anticipating decision sets\. This requires an additional conditional argument\. On each block, the comparator and misspecification radius are fixed before the within\-block randomization\. Consequently, the misspecification\-dependent terms remain predictable, and the SquareCB\.Lin\+ base and CORRAL master guarantees can be invoked conditionally\. IfPTP\_\{T\}is unknown, a Bandit\-over\-Bandit layer can remove this tuning at the usual parameter\-free cost\(Cheunget al\.,[2022](https://arxiv.org/html/2607.02891#bib.bib7); Zhaoet al\.,[2021](https://arxiv.org/html/2607.02891#bib.bib20)\)\.

Related work and positioning\.Restarting, sliding\-window, and weighted\-estimation methods are common tools for non\-stationary bandits\(Besbeset al\.,[2015](https://arxiv.org/html/2607.02891#bib.bib5); Russacet al\.,[2019](https://arxiv.org/html/2607.02891#bib.bib15); Cheunget al\.,[2022](https://arxiv.org/html/2607.02891#bib.bib7); Zhaoet al\.,[2021](https://arxiv.org/html/2607.02891#bib.bib20); Wanget al\.,[2025](https://arxiv.org/html/2607.02891#bib.bib18)\)\. For non\-stationary linear bandits, recent work identifies a gap between simple forgetting analyses and theT2/3​PT1/3T^\{2/3\}P\_\{T\}^\{1/3\}lower bound when feasible sets are round\-specific\(Zhaoet al\.,[2021](https://arxiv.org/html/2607.02891#bib.bib20)\)\. Our work addresses this gap: round\-specific feasible sets can be handled directly by reducing within\-block parameter drift to bounded linear misspecification\. The proof is built on this connection between non\-stationary linear bandits and misspecified linear bandits, using misspecification\-adaptive linear\-bandit guarantees\(Fosteret al\.,[2020](https://arxiv.org/html/2607.02891#bib.bib21); Takemuraet al\.,[2021](https://arxiv.org/html/2607.02891#bib.bib24)\)to remove the orthogonal\-structure assumption on round\-specific action sets\.

Organization\.The rest of the manuscript is organized as follows\. Section[2](https://arxiv.org/html/2607.02891#S2)introduces the model and block notation\. Section[3](https://arxiv.org/html/2607.02891#S3)proves the dynamic\-regret guarantee for general linear bandits with adaptive non\-anticipating decision sets\. Section[4](https://arxiv.org/html/2607.02891#S4)develops restarted SupLinUCB and its dynamic\-regret guarantee forKK\-armed contextual linear bandits\. Section[5](https://arxiv.org/html/2607.02891#S5)concludes this manuscript\.

## 2Problem Setting

We consider a non\-stationary contextual linear bandit overTTrounds\. At each roundtt, the learner observes a nonempty feasible decision set𝒜t⊆ℝd\\mathcal\{A\}\_\{t\}\\subseteq\\mathbb\{R\}^\{d\}\. We identify each feasible action with its feature vector\. The learner selects an actionat∈𝒜ta\_\{t\}\\in\\mathcal\{A\}\_\{t\}and observes a scalar rewardrt=rt​\(at\)r\_\{t\}=r\_\{t\}\(a\_\{t\}\)\. There is an unknown parameter sequenceθ1,…,θT∈ℝd\\theta\_\{1\},\\ldots,\\theta\_\{T\}\\in\\mathbb\{R\}^\{d\}, and the conditional mean reward is linear:μt​\(a\)=⟨a,θt⟩\\mu\_\{t\}\(a\)=\\langle a,\\theta\_\{t\}\\ranglefora∈𝒜ta\\in\\mathcal\{A\}\_\{t\}\. When a norm boundSSon the parameters is imposed, we writeΘ:=\{θ∈ℝd:‖θ‖2≤S\}\\Theta:=\\\{\\theta\\in\\mathbb\{R\}^\{d\}:\\\|\\theta\\\|\_\{2\}\\leq S\\\}; in theKK\-armed setting below we use the same notation withS=1S=1\.

*Histories\.*Letℋt−1\\mathcal\{H\}\_\{t\-1\}denote the interaction history through the end of roundt−1t\-1\. When adaptive decision sets are allowed, we also write𝒢t\\mathcal\{G\}\_\{t\}for the round\-ttσ\\sigma\-field after the current decision set and the learner’s action distribution have been determined, but before the action is sampled and before the reward noise is realized\.

\{assumption\}

\[Sub\-Gaussian reward noise\] For the played actionata\_\{t\}, writeξt:=rt​\(at\)−μt​\(at\)\\xi\_\{t\}:=r\_\{t\}\(a\_\{t\}\)\-\\mu\_\{t\}\(a\_\{t\}\)\. Conditional on the pre\-reward information, includingata\_\{t\}, the noise is mean zero andRR\-sub\-Gaussian for a universal constantRR\.

\{assumption\}

\[Path length\] The parameter sequence has path lengthPT:=∑t=1T−1‖θt\+1−θt‖2P\_\{T\}:=\\sum\_\{t=1\}^\{T\-1\}\\\|\\theta\_\{t\+1\}\-\\theta\_\{t\}\\\|\_\{2\}\.

*Dynamic regret\.*For a policyπ\\pi, letata\_\{t\}be the action selected byπ\\piat roundtt, and letat⋆a\_\{t\}^\{\\star\}be an optimal action at roundtt, i\.e\.,at⋆∈\\argmaxa∈𝒜t​μt​\(a\)=\\argmaxa∈𝒜t​⟨a,θt⟩a\_\{t\}^\{\\star\}\\in\\argmax\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\mu\_\{t\}\(a\)=\\argmax\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\langle a,\\theta\_\{t\}\\rangle\. The expected dynamic regret ofπ\\piis

RegT⁡\(π\):=𝔼​\[∑t=1T\(⟨at⋆,θt⟩−⟨at,θt⟩\)\]\.\\operatorname\{Reg\}\_\{T\}\(\\pi\):=\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\left\(\\langle a\_\{t\}^\{\\star\},\\theta\_\{t\}\\rangle\-\\langle a\_\{t\},\\theta\_\{t\}\\rangle\\right\)\\right\]\.When the policy or algorithm is clear from context, we writeRegT\\operatorname\{Reg\}\_\{T\}forRegT⁡\(π\)\\operatorname\{Reg\}\_\{T\}\(\\pi\)\.

*KK\-armed contextual specialization\.*TheKK\-armed contextual linear\-bandit setting considered byChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)is the special case𝒜t=\{xt​\(i\):i∈\[K\]\}\\mathcal\{A\}\_\{t\}=\\\{x\_\{t\}\(i\):i\\in\[K\]\\\}\. The learner choosesit∈\[K\]i\_\{t\}\\in\[K\], equivalentlyat=xt​\(it\)a\_\{t\}=x\_\{t\}\(i\_\{t\}\), andμt​\(i\):=μt​\(xt​\(i\)\)\\mu\_\{t\}\(i\):=\\mu\_\{t\}\(x\_\{t\}\(i\)\)\.

*Block notation\.*For an intervalℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}, write𝔼τ\[⋅\]:=𝔼\[⋅∣ℋτ−1\]\\mathbb\{E\}\_\{\\tau\}\[\\cdot\]:=\\mathbb\{E\}\[\\cdot\\mid\\mathcal\{H\}\_\{\\tau\-1\}\], whereℋτ−1\\mathcal\{H\}\_\{\\tau\-1\}is the history before the block starts\. The dynamic regret on blockℐ\\mathcal\{I\}isReg⁡\(ℐ\):=∑t∈ℐ\(⟨at⋆,θt⟩−⟨at,θt⟩\)\\operatorname\{Reg\}\(\\mathcal\{I\}\):=\\sum\_\{t\\in\\mathcal\{I\}\}\\left\(\\langle a\_\{t\}^\{\\star\},\\theta\_\{t\}\\rangle\-\\langle a\_\{t\},\\theta\_\{t\}\\rangle\\right\)\.

###### Definition 2\.1

For a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}and a comparatorθ∈Θ\\theta\\in\\Theta, define

εℐ​\(θ\):=supt∈ℐsupa∈𝒜t\|⟨a,θt⟩−⟨a,θ⟩\|\.\\varepsilon\_\{\\mathcal\{I\}\}\(\\theta\):=\\sup\_\{t\\in\\mathcal\{I\}\}\\sup\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\left\|\\langle a,\\theta\_\{t\}\\rangle\-\\langle a,\\theta\\rangle\\right\|\.Definition[2\.1](https://arxiv.org/html/2607.02891#S2.Thmtheorem1)makes precise the sense in which a non\-stationary linear bandit can be viewed locally as a misspecified stationary linear bandit\. When the comparator is clear from context, we writeεℐ\\varepsilon\_\{\\mathcal\{I\}\}\.

## 3General Linear Bandits with Adaptive Non\-Anticipating Decision Sets

In this section we consider the setting in which the parameter path\(θt\)t=1T\(\\theta\_\{t\}\)\_\{t=1\}^\{T\}is fixed before interaction begins and is independent of the learner’s randomization and reward noise\. The decision sets, however, may be adaptive but non\-anticipating: at each roundtt,𝒜t\\mathcal\{A\}\_\{t\}may depend onℋt−1\\mathcal\{H\}\_\{t\-1\}, but it is fixed before any current\-round learner randomization is drawn and before the reward noise is realized\. Equivalently, after𝒜t\\mathcal\{A\}\_\{t\}and the learner’s action distribution have been determined,𝒢t\\mathcal\{G\}\_\{t\}contains these quantities but not the round\-ttaction sample\. The technical point, relative to the oblivious\-sequence analysis inFosteret al\.\([2020](https://arxiv.org/html/2607.02891#bib.bib21)\), is that our block proof is written conditionally on this round\-ttσ\\sigma\-field, which allows adaptively generated decision sets\.

Allowing such adaptivity is important in operational problems where the feasible actions at a round are shaped by past decisions, resource states, and observed feedback\. Online ad display provides one example\. For a given impression, ad eligibility may depend on past serving decisions through frequency caps, exposure limits, campaign pacing or delivery constraints, and advertiser\-side resource availability\. It may also depend on feedback observed before the current impression, such as past clicks, conversions, negative feedback, or other engagement signals\. Thus the model allows the feasible action set to respond to the learner’s previous actions and observations, while requiring it to be fixed before the current reward realization\.

\{assumption\}

\[Bounded rewards and parameters for the adaptive reduction\] The action vectors and parameters satisfy‖a‖2≤L\\\|a\\\|\_\{2\}\\leq Lfor alla∈𝒜ta\\in\\mathcal\{A\}\_\{t\}and‖θt‖2≤S\\\|\\theta\_\{t\}\\\|\_\{2\}\\leq Sfor allt∈\[T\]t\\in\[T\]\. Moreover, for every roundttand feasible actiona∈𝒜ta\\in\\mathcal\{A\}\_\{t\}, the potential reward satisfies0≤rt​\(a\)≤10\\leq r\_\{t\}\(a\)\\leq 1a\.s\.

Unbounded conditionally sub\-Gaussian rewards can be clipped and rescaled, incurring only standard logarithmic factors\. Thus, we state the formal results under bounded rewards\.

\{assumption\}

\[Fixed block comparator and fixed radius upper bound\] On blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}, before the learner’s first within\-block randomization, there exist quantitiesθℐ⋆∈Θ\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\in\\Thetaandε¯ℐ≥0\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\geq 0, unknown to the learner but fixed, such thatεℐ​\(θℐ⋆\)≤ε¯ℐ\\varepsilon\_\{\\mathcal\{I\}\}\(\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\)\\leq\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}almost surely\. In the path\-length application below, this assumption is satisfied by takingθℐ⋆=θτ\\theta\_\{\\mathcal\{I\}\}^\{\\star\}=\\theta\_\{\\tau\}andε¯ℐ=L​Pℐ\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}=LP\_\{\\mathcal\{I\}\}, since the parameter path is fixed before interaction begins\.

*Algorithmic idea\.*Following the restarting viewpoint ofBesbeset al\.\([2015](https://arxiv.org/html/2607.02891#bib.bib5)\), the algorithm partitions the horizon into blocks and restarts a CORRAL master\(Agarwalet al\.,[2017](https://arxiv.org/html/2607.02891#bib.bib2); Fosteret al\.,[2020](https://arxiv.org/html/2607.02891#bib.bib21)\)over SquareCB\.Lin\+ bases\. The CORRAL layer randomizes over base learners and competes with the best base learner in hindsight, up to its aggregation cost\. In our use of CORRAL, the bases are indexed by a geometric grid of candidate misspecification levels\. On each block, the unknown parameter drift acts as an unknown misspecification level, and the grid contains a candidate within a constant factor of this level\.

Input:Horizon

TT, block length

Δ\\Delta, dimension

dd, radius cap

Bε=2​L​SB\_\{\\varepsilon\}=2LS, square\-loss regret bound

Regsq⁡\(Δ\)\\operatorname\{Reg\}\_\{\\rm sq\}\(\\Delta\)
Output:Actions

ata\_\{t\}
1

2Partition time into blocks

ℐ\\mathcal\{I\}of length

Δ\\Delta;

3

4foreach*blockℐ\\mathcal\{I\}*do

5Initialize a geometric grid

\{εm′\}m=1M⊆\[1/\|ℐ\|,Bε\]\\\{\\varepsilon^\{\\prime\}\_\{m\}\\\}\_\{m=1\}^\{M\}\\subseteq\[1/\|\\mathcal\{I\}\|,B\_\{\\varepsilon\}\]with endpoints

BεB\_\{\\varepsilon\}and

1/\|ℐ\|1/\|\\mathcal\{I\}\|, up to a factor two;

6Initialize a hedged\-FTRL/CORRAL\-style master over

MMbase learners;

7Initialize

MMbase learners, each a SquareCB\.Lin\+ instance;

8

9for*t∈ℐt\\in\\mathcal\{I\}*do

10Observe

𝒜t\\mathcal\{A\}\_\{t\};

11Master samples

Mt∼qtM\_\{t\}\\sim q\_\{t\};

12Set

ρt,Mt=1minτ≤r≤t⁡qr,Mt\\rho\_\{t,M\_\{t\}\}=\\frac\{1\}\{\\min\_\{\\tau\\leq r\\leq t\}q\_\{r,M\_\{t\}\}\};

13Base learner

MtM\_\{t\}sets

γt,Mt=min⁡\{dεMt′,d​Δρt,Mt​Regsq⁡\(Δ\)\}\\gamma\_\{t,M\_\{t\}\}=\\min\\left\\\{\\frac\{\\sqrt\{d\}\}\{\\varepsilon^\{\\prime\}\_\{M\_\{t\}\}\},\\sqrt\{\\frac\{d\\Delta\}\{\\rho\_\{t,M\_\{t\}\}\\operatorname\{Reg\}\_\{\\rm sq\}\(\\Delta\)\}\}\\right\\\};

14Set oracle weight

wt=γt,Mtqt,Mtw\_\{t\}=\\frac\{\\gamma\_\{t,M\_\{t\}\}\}\{q\_\{t,M\_\{t\}\}\};

15Query the weighted regression oracle of base

MtM\_\{t\}, implemented via the randomized weighted\-update reduction\(Fosteret al\.,[2020](https://arxiv.org/html/2607.02891#bib.bib21)\), to obtain

β^t,Mt\\widehat\{\\beta\}\_\{t,M\_\{t\}\};

16Set

pt,Mt∈logdet​\-​barrier⁡\(β^t,Mt,γt,Mt;𝒜t\)p\_\{t,M\_\{t\}\}\\in\\operatorname\{logdet\\text\{\-\}barrier\}\\bigl\(\\widehat\{\\beta\}\_\{t,M\_\{t\}\},\\gamma\_\{t,M\_\{t\}\};\\mathcal\{A\}\_\{t\}\\bigr\);

17Sample

at∼pt,Mta\_\{t\}\\sim p\_\{t,M\_\{t\}\};

18Play

ata\_\{t\}, observe reward

rtr\_\{t\}, and set

ℓt=−rt\\ell\_\{t\}=\-r\_\{t\};

19Update the weighted oracle of base

MtM\_\{t\}with

\(wt,at,ℓt\)\(w\_\{t\},a\_\{t\},\\ell\_\{t\}\);

20Update the master using the shifted observed loss

ℓt\+1=1−rt\\ell\_\{t\}\+1=1\-r\_\{t\}of base

MtM\_\{t\};

21

22

Algorithm 1Restarted misspecification\-adaptive linear banditWe now describe the grid, oracle interface, and sampling rule used in Algorithm[1](https://arxiv.org/html/2607.02891#algorithm1)\. On a block of lengthnn, letBε:=2​L​SB\_\{\\varepsilon\}:=2LSand use a geometric grid\{εm′\}m=1M⊆\[1/n,Bε\]\\\{\\varepsilon^\{\\prime\}\_\{m\}\\\}\_\{m=1\}^\{M\}\\subseteq\[1/n,B\_\{\\varepsilon\}\], with largest pointBεB\_\{\\varepsilon\}, smallest point1/n1/n, and common ratio two\. For basemm, set the exploration parameter

γt,m=min⁡\{dεm′,d​nρt,m​Regsq⁡\(n\)\}\.\\gamma\_\{t,m\}=\\min\\left\\\{\\frac\{\\sqrt\{d\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\},\\sqrt\{\\frac\{dn\}\{\\rho\_\{t,m\}\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\}\\right\\\}\.Although Algorithm[1](https://arxiv.org/html/2607.02891#algorithm1)invokes a weighted square\-loss oracle, the randomized reduction ofFosteret al\.\([2020](https://arxiv.org/html/2607.02891#bib.bib21)\)allows this interface to be implemented using an unweighted online square\-loss regression oracle\. For the bounded linear square\-loss class considered here, the online Newton step ofHazanet al\.\([2007](https://arxiv.org/html/2607.02891#bib.bib26)\)givesRegsq⁡\(n\)=O~​\(d\)\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)=\\widetilde\{O\}\(d\)\.

For the SquareCB\.Lin\+ sampling rule, letΔ​\(𝒜\)\\Delta\(\\mathcal\{A\}\)be the set of distributions on𝒜\\mathcal\{A\}, and forp∈Δ​\(𝒜\)p\\in\\Delta\(\\mathcal\{A\}\)writea¯p:=𝔼a∼p​\[a\]\\bar\{a\}\_\{p\}:=\\mathbb\{E\}\_\{a\\sim p\}\[a\]andHp:=𝔼a∼p​\[a​a⊤\]H\_\{p\}:=\\mathbb\{E\}\_\{a\\sim p\}\[aa^\{\\top\}\]\. Given\(β^,γ,𝒜\)\(\\widehat\{\\beta\},\\gamma,\\mathcal\{A\}\), the base chooses any minimizer of

\\argminp∈Δ​\(𝒜\)​\{⟨a¯p,β^⟩−γ−1​log​det\(Hp−a¯p​a¯p⊤\)\}\.\\displaystyle\\argmin\_\{p\\in\\Delta\(\\mathcal\{A\}\)\}\\Bigl\\\{\\langle\\bar\{a\}\_\{p\},\\widehat\{\\beta\}\\rangle\-\\gamma^\{\-1\}\\log\\det\(H\_\{p\}\-\\bar\{a\}\_\{p\}\\bar\{a\}\_\{p\}^\{\\top\}\)\\Bigr\\\}\.\(1\)We writelogdet​\-​barrier⁡\(β^,γ;𝒜\)\\operatorname\{logdet\\text\{\-\}barrier\}\(\\widehat\{\\beta\},\\gamma;\\mathcal\{A\}\)for this set of minimizers\.

At roundtt, the master samples an indexMt∼qtM\_\{t\}\\sim q\_\{t\}and follows base learnerMtM\_\{t\}\. LetZt,m:=𝟏​\{Mt=m\}Z\_\{t,m\}:=\\mathbf\{1\}\\\{M\_\{t\}=m\\\}\. On a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}, defineρt,m:=1/minτ≤r≤t⁡qr,m\\rho\_\{t,m\}:=1/\\min\_\{\\tau\\leq r\\leq t\}q\_\{r,m\}andρℐ,m:=maxt∈ℐ⁡ρt,m\\rho\_\{\\mathcal\{I\},m\}:=\\max\_\{t\\in\\mathcal\{I\}\}\\rho\_\{t,m\}\. The master outputs an interior distribution, soqt,m\>0q\_\{t,m\}\>0\. If basemmis selected, its oracle weight iswt,m:=γt,m/qt,mw\_\{t,m\}:=\\gamma\_\{t,m\}/q\_\{t,m\}\. Each basemmproposes an action distributionpt,mp\_\{t,m\}\. The selected base therefore proposespt,Mtp\_\{t,M\_\{t\}\}, and the learner samplesat∼pt,Mta\_\{t\}\\sim p\_\{t,M\_\{t\}\}\.

Lemma[3\.1](https://arxiv.org/html/2607.02891#S3.Thmtheorem1)gives the block regret guarantee for Algorithm[1](https://arxiv.org/html/2607.02891#algorithm1)under the fixed\-radius misspecification condition above\.

###### Lemma 3\.1

Assume Assumptions[2](https://arxiv.org/html/2607.02891#S2),[3](https://arxiv.org/html/2607.02891#S3)and[3](https://arxiv.org/html/2607.02891#S3)hold on blockℐ\\mathcal\{I\}\. Run Algorithm[1](https://arxiv.org/html/2607.02891#algorithm1)freshly onℐ\\mathcal\{I\}, using observed lossℓt=−rt​\(at\)\\ell\_\{t\}=\-r\_\{t\}\(a\_\{t\}\)and updating the master with the shifted lossℓt\+1\\ell\_\{t\}\+1\. Assume the unweighted square\-loss oracle has regretRegsq⁡\(n\)\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)on length\-nnadaptive non\-anticipating sequences\. Then

𝔼τ​\[Reg⁡\(ℐ\)\]≤O~​\(d​n​Regsq⁡\(n\)\+d​n​ε¯ℐ\)\.\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\+\\sqrt\{d\}\\,n\\,\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\right\)\.In particular, online Newton step givesRegsq⁡\(n\)=O~​\(d\)\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)=\\widetilde\{O\}\(d\), and hence

𝔼τ​\[Reg⁡\(ℐ\)\]≤O~​\(d​n\+d​n​ε¯ℐ\)\.\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]\\leq\\widetilde\{O\}\\\!\\left\(d\\sqrt\{n\}\+\\sqrt\{d\}\\,n\\,\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\right\)\.

###### Proof 3\.2

Proof of Lemma[3\.1](https://arxiv.org/html/2607.02891#S3.Thmtheorem1)\. Let𝒢t\\mathcal\{G\}\_\{t\}be the round\-ttσ\\sigma\-field defined above\. Letℓt=−rt​\(at\)\\ell\_\{t\}=\-r\_\{t\}\(a\_\{t\}\)denote the observed loss supplied to the selected base\. The master receives the shifted lossℓt\+1=1−rt​\(at\)\\ell\_\{t\}\+1=1\-r\_\{t\}\(a\_\{t\}\)\. Under the mean\-loss conventionLt​\(a\)=−⟨a,θt⟩L\_\{t\}\(a\)=\-\\langle a,\\theta\_\{t\}\\rangle, we have𝔼​\[ℓt∣𝒢t,Mt,at\]=Lt​\(at\)\\mathbb\{E\}\[\\ell\_\{t\}\\mid\\mathcal\{G\}\_\{t\},M\_\{t\},a\_\{t\}\]=L\_\{t\}\(a\_\{t\}\)\. Thenat⋆∈\\argmaxa∈𝒜t​⟨a,θt⟩=\\argmina∈𝒜t​Lt​\(a\)a\_\{t\}^\{\\star\}\\in\\argmax\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\langle a,\\theta\_\{t\}\\rangle=\\argmin\_\{a\\in\\mathcal\{A\}\_\{t\}\}L\_\{t\}\(a\), and therefore

Lt​\(at\)−Lt​\(at⋆\)=⟨at⋆,θt⟩−⟨at,θt⟩\.L\_\{t\}\(a\_\{t\}\)\-L\_\{t\}\(a\_\{t\}^\{\\star\}\)=\\langle a\_\{t\}^\{\\star\},\\theta\_\{t\}\\rangle\-\\langle a\_\{t\},\\theta\_\{t\}\\rangle\.Thus the reward\-regret on the block is exactly the loss\-regret for the lossesLtL\_\{t\}\.

We condition onℱℐ\\mathcal\{F\}\_\{\\mathcal\{I\}\}, theσ\\sigma\-field just before the first within\-block randomization\. Under Assumption[3](https://arxiv.org/html/2607.02891#S3), the comparatorθℐ⋆\\theta\_\{\\mathcal\{I\}\}^\{\\star\}is fixed under this conditioning\. Putβℐ⋆:=−θℐ⋆\\beta\_\{\\mathcal\{I\}\}^\{\\star\}:=\-\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\. Then, for everyt∈ℐt\\in\\mathcal\{I\},

supa∈𝒜t\|Lt​\(a\)−⟨a,βℐ⋆⟩\|\\displaystyle\\sup\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\left\|L\_\{t\}\(a\)\-\\langle a,\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\right\|\(2\)=\\displaystyle=supa∈𝒜t\|⟨a,θt⟩−⟨a,θℐ⋆⟩\|≤ε¯ℐ\.\\displaystyle\\sup\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\left\|\\langle a,\\theta\_\{t\}\\rangle\-\\langle a,\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\right\|\\leq\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\.The proof follows the structure of the oblivious\-sequence argument ofFosteret al\.\([2020](https://arxiv.org/html/2607.02891#bib.bib21)\), with the sequence\-level comparator and misspecification radius replaced by the fixed block pair\(βℐ⋆,ε¯ℐ\)\(\\beta\_\{\\mathcal\{I\}\}^\{\\star\},\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\)\. For eacht∈ℐt\\in\\mathcal\{I\}, the residual

et​\(a\):=Lt​\(a\)−⟨a,βℐ⋆⟩e\_\{t\}\(a\):=L\_\{t\}\(a\)\-\\langle a,\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangleis𝒢t\\mathcal\{G\}\_\{t\}\-measurable as a function ofa∈𝒜ta\\in\\mathcal\{A\}\_\{t\}\. Moreover,supa∈𝒜t\|et​\(a\)\|≤ε¯ℐ\\sup\_\{a\\in\\mathcal\{A\}\_\{t\}\}\|e\_\{t\}\(a\)\|\\leq\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\.

The learner’s regret under CORRAL decomposes into two parts: master regret and base regret\. The base\-regret term for basemmtakes the following importance\-weighted form:

RegImpm⁡\(ℐ\):=𝔼τ​\[∑t∈ℐZt,mqt,m​\(Lt​\(at\)−Lt​\(at⋆\)\)\]\.\\operatorname\{Reg\}\_\{\\rm Imp\}^\{m\}\(\\mathcal\{I\}\):=\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\frac\{Z\_\{t,m\}\}\{q\_\{t,m\}\}\\bigl\(L\_\{t\}\(a\_\{t\}\)\-L\_\{t\}\(a\_\{t\}^\{\\star\}\)\\bigr\)\\right\]\.HereZt,m/qt,mZ\_\{t,m\}/q\_\{t,m\}is the importance weight that makes the selected rounds for basemman unbiased conditional estimate of the loss\-regret of the counterfactual actions proposed by that base\.

For every bounded random functionϕt\\phi\_\{t\}on𝒜t\\mathcal\{A\}\_\{t\}whose values are𝒢t\\mathcal\{G\}\_\{t\}\-measurable,

𝔼\[Zt,mqt,mϕt\(at\)\|𝒢t\]=𝔼a∼pt,m\[ϕt\(a\)\]\.\\mathbb\{E\}\\\!\\left\[\\frac\{Z\_\{t,m\}\}\{q\_\{t,m\}\}\\phi\_\{t\}\(a\_\{t\}\)\\,\\middle\|\\,\\mathcal\{G\}\_\{t\}\\right\]=\\mathbb\{E\}\_\{a\\sim p\_\{t,m\}\}\[\\phi\_\{t\}\(a\)\]\.\(3\)Becauseβℐ⋆\\beta\_\{\\mathcal\{I\}\}^\{\\star\}andε¯ℐ\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}are fixed under the block conditioning, the residual\-dependent functions used below are𝒢t\\mathcal\{G\}\_\{t\}\-measurable, so \([3](https://arxiv.org/html/2607.02891#S3.E3)\) applies\.

Letat∘∈\\argmina∈𝒜t​⟨a,βℐ⋆⟩a\_\{t\}^\{\\circ\}\\in\\argmin\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\langle a,\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\ranglebe an action optimal under the fixed block comparator\. We use deterministic tie\-breaking so thatat∘a\_\{t\}^\{\\circ\}is𝒢t\\mathcal\{G\}\_\{t\}\-measurable\. Next we present the key conversion step: it upper bounds instantaneous dynamic regret against the true roundwise optimum by instantaneous static regret under the fixed block model, plus the block misspecification penalty\. By the block misspecification bound,

Lt​\(at\)−Lt​\(at⋆\)\\displaystyle L\_\{t\}\(a\_\{t\}\)\-L\_\{t\}\(a\_\{t\}^\{\\star\}\)≤⟨at,βℐ⋆⟩−⟨at⋆,βℐ⋆⟩\+2​ε¯ℐ\\displaystyle\\leq\\langle a\_\{t\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\-\\langle a\_\{t\}^\{\\star\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}≤⟨at−at∘,βℐ⋆⟩\+2​ε¯ℐ\.\\displaystyle\\leq\\langle a\_\{t\}\-a\_\{t\}^\{\\circ\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\.For a distributionppon𝒜t\\mathcal\{A\}\_\{t\}, writea¯p:=𝔼a∼p​\[a\]\\bar\{a\}\_\{p\}:=\\mathbb\{E\}\_\{a\\sim p\}\[a\]\. Thusa¯pt,m\\bar\{a\}\_\{p\_\{t,m\}\}is the mean action proposed by basemmat roundtt\. Therefore

RegImpm⁡\(ℐ\)\\displaystyle\\operatorname\{Reg\}\_\{\\rm Imp\}^\{m\}\(\\mathcal\{I\}\)≤𝔼τ​\[∑t∈ℐZt,mqt,m​⟨at−at∘,βℐ⋆⟩\]\+2​ε¯ℐ​n\\displaystyle\\leq\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\frac\{Z\_\{t,m\}\}\{q\_\{t,m\}\}\\langle a\_\{t\}\-a\_\{t\}^\{\\circ\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\right\]\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n=𝔼τ​\[∑t∈ℐ⟨a¯pt,m−at∘,βℐ⋆⟩\]\+2​ε¯ℐ​n\.\\displaystyle=\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\langle\\bar\{a\}\_\{p\_\{t,m\}\}\-a\_\{t\}^\{\\circ\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\right\]\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n\.The equality uses \([3](https://arxiv.org/html/2607.02891#S3.E3)\) withϕt​\(a\)=⟨a−at∘,βℐ⋆⟩\\phi\_\{t\}\(a\)=\\langle a\-a\_\{t\}^\{\\circ\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangleandϕt≡1\\phi\_\{t\}\\equiv 1\. Applying \([3](https://arxiv.org/html/2607.02891#S3.E3)\) withϕt≡1\\phi\_\{t\}\\equiv 1gives𝔼​\[Zt,m/qt,m∣𝒢t\]=1\\mathbb\{E\}\[Z\_\{t,m\}/q\_\{t,m\}\\mid\\mathcal\{G\}\_\{t\}\]=1, so the additive misspecification term is bounded by2​ε¯ℐ​n2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n\.

The base uses

γt,m=min⁡\{dεm′,d​nρt,m​Regsq⁡\(n\)\}\.\\gamma\_\{t,m\}=\\min\\left\\\{\\frac\{\\sqrt\{d\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\},\\sqrt\{\\frac\{dn\}\{\\rho\_\{t,m\}\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\}\\right\\\}\.Letβ^t,m\\widehat\{\\beta\}\_\{t,m\}be the𝒢t\\mathcal\{G\}\_\{t\}\-measurable prediction made by basemm’s square\-loss oracle at roundtt\. Thus⟨a,β^t,m⟩\\langle a,\\widehat\{\\beta\}\_\{t,m\}\\rangleis the base’s predicted loss for actionaa\. By Lemma[6\.2](https://arxiv.org/html/2607.02891#S6.Thmtheorem2), applied conditionally on𝒢t\\mathcal\{G\}\_\{t\}, we have

⟨a¯pt,m−at∘,βℐ⋆⟩\\displaystyle\\langle\\bar\{a\}\_\{p\_\{t,m\}\}\-a\_\{t\}^\{\\circ\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle≤\\displaystyle\\leqdγt,m\+γt,m4​‖β^t,m−βℐ⋆‖𝔼a∼pt,m​\[a​a⊤\]2\.\\displaystyle\\frac\{d\}\{\\gamma\_\{t,m\}\}\+\\frac\{\\gamma\_\{t,m\}\}\{4\}\\\|\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\\|\_\{\\mathbb\{E\}\_\{a\\sim p\_\{t,m\}\}\[aa^\{\\top\}\]\}^\{2\}\.Letvt,m:=β^t,m−βℐ⋆v\_\{t,m\}:=\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\. The norm term is a second moment under the action distribution proposed by basemm:

‖vt,m‖𝔼a∼pt,m​\[a​a⊤\]2=𝔼a∼pt,m​\[⟨a,vt,m⟩2\]\.\\\|v\_\{t,m\}\\\|\_\{\\mathbb\{E\}\_\{a\\sim p\_\{t,m\}\}\[aa^\{\\top\}\]\}^\{2\}=\\mathbb\{E\}\_\{a\\sim p\_\{t,m\}\}\\\!\\left\[\\langle a,v\_\{t,m\}\\rangle^\{2\}\\right\]\.Applying \([3](https://arxiv.org/html/2607.02891#S3.E3)\) withϕt​\(a\)=γt,m​⟨a,vt,m⟩2\\phi\_\{t\}\(a\)=\\gamma\_\{t,m\}\\langle a,v\_\{t,m\}\\rangle^\{2\}, and then summing overt∈ℐt\\in\\mathcal\{I\}, rewrites this distributional second moment as the importance\-weighted realized square term

Dℐ,m:=𝔼τ​\[∑t∈ℐZt,mqt,m​γt,m​⟨at,β^t,m−βℐ⋆⟩2\]\.D\_\{\\mathcal\{I\},m\}:=\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\frac\{Z\_\{t,m\}\}\{q\_\{t,m\}\}\\gamma\_\{t,m\}\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle^\{2\}\\right\]\.Then

RegImpm⁡\(ℐ\)≤∑t∈ℐ𝔼τ​\[dγt,m\]\+14​Dℐ,m\+2​ε¯ℐ​n\.\\operatorname\{Reg\}\_\{\\rm Imp\}^\{m\}\(\\mathcal\{I\}\)\\leq\\sum\_\{t\\in\\mathcal\{I\}\}\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\frac\{d\}\{\\gamma\_\{t,m\}\}\\right\]\+\\frac\{1\}\{4\}D\_\{\\mathcal\{I\},m\}\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n\.\(4\)
It remains to relateDℐ,mD\_\{\\mathcal\{I\},m\}to weighted square\-loss regret\. The oracle weight conditional on selecting basemmiswt,m=γt,m/qt,mw\_\{t,m\}=\\gamma\_\{t,m\}/q\_\{t,m\}\. Equivalently, the effective weight for the length\-nnblock sequence is

ωt,m:=Zt,m​γt,mqt,m\.\\omega\_\{t,m\}:=\\frac\{Z\_\{t,m\}\\gamma\_\{t,m\}\}\{q\_\{t,m\}\}\.On every round for which base learnermmis selected,

⟨at,β^t,m−βℐ⋆⟩2\\displaystyle\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle^\{2\}\(5\)=\\displaystyle=\(⟨at,β^t,m⟩−ℓt\)2−\(⟨at,βℐ⋆⟩−ℓt\)2\\displaystyle\(\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\\rangle\-\\ell\_\{t\}\)^\{2\}\-\(\\langle a\_\{t\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\-\\ell\_\{t\}\)^\{2\}\+2​\(ℓt−⟨at,βℐ⋆⟩\)​⟨at,β^t,m−βℐ⋆⟩\.\\displaystyle\\quad\+2\\bigl\(\\ell\_\{t\}\-\\langle a\_\{t\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\bigr\)\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\.The weighted\-update reduction ofFosteret al\.\([2020](https://arxiv.org/html/2607.02891#bib.bib21)\), applied to the underlying unweighted square\-loss oracle, gives

𝔼τ​\[∑t∈ℐωt,m​\(\(⟨at,β^t,m⟩−ℓt\)2−\(⟨at,βℐ⋆⟩−ℓt\)2\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\omega\_\{t,m\}\\left\(\(\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\\rangle\-\\ell\_\{t\}\)^\{2\}\-\(\\langle a\_\{t\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\-\\ell\_\{t\}\)^\{2\}\\right\)\\right\]\(6\)≤𝔼τ​\[maxt∈ℐ⁡γt,mqt,m\]​Regsq⁡\(n\)\.\\displaystyle\\qquad\\leq\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\max\_\{t\\in\\mathcal\{I\}\}\\frac\{\\gamma\_\{t,m\}\}\{q\_\{t,m\}\}\\right\]\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\.For the remaining cross\-term, writeet​\(a\):=Lt​\(a\)−⟨a,βℐ⋆⟩e\_\{t\}\(a\):=L\_\{t\}\(a\)\-\\langle a,\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\. Since𝔼​\[ℓt∣𝒢t,Mt,at\]=Lt​\(at\)\\mathbb\{E\}\[\\ell\_\{t\}\\mid\\mathcal\{G\}\_\{t\},M\_\{t\},a\_\{t\}\]=L\_\{t\}\(a\_\{t\}\), the stochastic noise part vanishes by the tower property\. Hence

2​𝔼τ​\[∑t∈ℐωt,m​\(ℓt−⟨at,βℐ⋆⟩\)​⟨at,β^t,m−βℐ⋆⟩\]\\displaystyle 2\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\omega\_\{t,m\}\\bigl\(\\ell\_\{t\}\-\\langle a\_\{t\},\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\bigr\)\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\right\]\(7\)=\\displaystyle=2​𝔼τ​\[∑t∈ℐωt,m​et​\(at\)​⟨at,β^t,m−βℐ⋆⟩\]\\displaystyle 2\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\omega\_\{t,m\}e\_\{t\}\(a\_\{t\}\)\\langle a\_\{t\},\\widehat\{\\beta\}\_\{t,m\}\-\\beta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\\right\]≤\\displaystyle\\leq2​𝔼τ​\[∑t∈ℐωt,m​et​\(at\)2\]\+12​Dℐ,m,\\displaystyle 2\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\omega\_\{t,m\}e\_\{t\}\(a\_\{t\}\)^\{2\}\\right\]\+\\frac\{1\}\{2\}D\_\{\\mathcal\{I\},m\},where the last step uses2​u​v≤2​u2\+12​v22uv\\leq 2u^\{2\}\+\\frac\{1\}\{2\}v^\{2\}\. The first term is controlled pointwise by the block misspecification:

𝔼τ​\[∑t∈ℐωt,m​et​\(at\)2\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\omega\_\{t,m\}e\_\{t\}\(a\_\{t\}\)^\{2\}\\right\]\(8\)=\\displaystyle=𝔼τ​\[∑t∈ℐγt,m​𝔼a∼pt,m​\[et​\(a\)2\]\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\gamma\_\{t,m\}\\mathbb\{E\}\_\{a\\sim p\_\{t,m\}\}\[e\_\{t\}\(a\)^\{2\}\]\\right\]≤\\displaystyle\\leq𝔼τ​\[∑t∈ℐγt,m​ε¯ℐ2\]≤n​dεm′​ε¯ℐ2\.\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\gamma\_\{t,m\}\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\\right\]\\leq n\\frac\{\\sqrt\{d\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\}\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\.Combining \([5](https://arxiv.org/html/2607.02891#S3.E5)\), \([6](https://arxiv.org/html/2607.02891#S3.E6)\), \([7](https://arxiv.org/html/2607.02891#S3.E7)\), and \([8](https://arxiv.org/html/2607.02891#S3.E8)\), and then isolatingDℐ,mD\_\{\\mathcal\{I\},m\}, yields

Dℐ,m≤2​𝔼τ​\[maxt∈ℐ⁡γt,mqt,m\]​Regsq⁡\(n\)\+4​n​dεm′​ε¯ℐ2\.D\_\{\\mathcal\{I\},m\}\\leq 2\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\max\_\{t\\in\\mathcal\{I\}\}\\frac\{\\gamma\_\{t,m\}\}\{q\_\{t,m\}\}\\right\]\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\+4n\\frac\{\\sqrt\{d\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\}\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\.\(9\)Substituting \([9](https://arxiv.org/html/2607.02891#S3.E9)\) into \([4](https://arxiv.org/html/2607.02891#S3.E4)\) gives

RegImpm⁡\(ℐ\)\\displaystyle\\operatorname\{Reg\}\_\{\\rm Imp\}^\{m\}\(\\mathcal\{I\}\)≤\\displaystyle\\leq∑t∈ℐ𝔼τ​\[dγt,m\]\+12​𝔼τ​\[maxt∈ℐ⁡γt,mqt,m\]​Regsq⁡\(n\)\\displaystyle\\sum\_\{t\\in\\mathcal\{I\}\}\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\frac\{d\}\{\\gamma\_\{t,m\}\}\\right\]\+\\frac\{1\}\{2\}\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\max\_\{t\\in\\mathcal\{I\}\}\\frac\{\\gamma\_\{t,m\}\}\{q\_\{t,m\}\}\\right\]\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\+n​dεm′​ε¯ℐ2\+2​ε¯ℐ​n\.\\displaystyle\\qquad\+n\\frac\{\\sqrt\{d\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\}\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n\.Since

1γt,m≤εm′d\+ρℐ,m​Regsq⁡\(n\)d​n,\\frac\{1\}\{\\gamma\_\{t,m\}\}\\leq\\frac\{\\varepsilon^\{\\prime\}\_\{m\}\}\{\\sqrt\{d\}\}\+\\sqrt\{\\frac\{\\rho\_\{\\mathcal\{I\},m\}\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\{dn\}\},we have

∑t∈ℐ𝔼τ​\[dγt,m\]\\displaystyle\\sum\_\{t\\in\\mathcal\{I\}\}\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\frac\{d\}\{\\gamma\_\{t,m\}\}\\right\]≤\\displaystyle\\leqεm′​n​d\+𝔼τ​\[ρℐ,m\]​d​n​Regsq⁡\(n\)\.\\displaystyle\\varepsilon^\{\\prime\}\_\{m\}n\\sqrt\{d\}\+\\mathbb\{E\}\_\{\\tau\}\[\\sqrt\{\\rho\_\{\\mathcal\{I\},m\}\}\]\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\.Moreover,

maxt∈ℐ⁡γt,mqt,m≤maxt∈ℐ⁡γt,m​ρt,m≤ρℐ,m​d​nRegsq⁡\(n\)\.\\max\_\{t\\in\\mathcal\{I\}\}\\frac\{\\gamma\_\{t,m\}\}\{q\_\{t,m\}\}\\leq\\max\_\{t\\in\\mathcal\{I\}\}\\gamma\_\{t,m\}\\rho\_\{t,m\}\\leq\\sqrt\{\\frac\{\\rho\_\{\\mathcal\{I\},m\}dn\}\{\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\}\.Therefore

RegImpm⁡\(ℐ\)\\displaystyle\\operatorname\{Reg\}\_\{\\rm Imp\}^\{m\}\(\\mathcal\{I\}\)≤32​𝔼τ​\[ρℐ,m\]​d​n​Regsq⁡\(n\)\\displaystyle\\leq\\frac\{3\}\{2\}\\mathbb\{E\}\_\{\\tau\}\[\\sqrt\{\\rho\_\{\\mathcal\{I\},m\}\}\]\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\+\(εm′\+ε¯ℐ2εm′\)​n​d\+2​ε¯ℐ​n\.\\displaystyle\\qquad\+\\left\(\\varepsilon^\{\\prime\}\_\{m\}\+\\frac\{\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\}\\right\)n\\sqrt\{d\}\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n\.It remains to combine the base guarantee with the master guarantee\. For each base learnermm, letat,ma\_\{t,m\}denote the action drawn frompt,mp\_\{t,m\}at timett\. The master is updated with the shifted observed lossℓt\+1\\ell\_\{t\}\+1, becauseℓt=−rt​\(at\)\\ell\_\{t\}=\-r\_\{t\}\(a\_\{t\}\)may be negative whereas the master guarantee \(Lemma[6\.1](https://arxiv.org/html/2607.02891#S6.Thmtheorem1)\) requires nonnegative bounded losses\. After conditioning on𝒢t\\mathcal\{G\}\_\{t\}, the mean shifted loss associated with base learnermmis𝔼a∼pt,m​\[Lt​\(a\)\+1\]\\mathbb\{E\}\_\{a\\sim p\_\{t,m\}\}\[L\_\{t\}\(a\)\+1\]\. The same shift is applied to every base learner, so it cancels in the master regret comparison\. For any fixed basemm,

𝔼τ​\[Reg⁡\(ℐ\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]=\\displaystyle=𝔼τ​\[∑t∈ℐ\(Lt​\(at\)−Lt​\(at⋆\)\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\bigl\(L\_\{t\}\(a\_\{t\}\)\-L\_\{t\}\(a\_\{t\}^\{\\star\}\)\\bigr\)\\right\]=\\displaystyle=𝔼τ​\[∑t∈ℐ\(\(Lt​\(at\)\+1\)−\(Lt​\(at,m\)\+1\)\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\bigl\(\(L\_\{t\}\(a\_\{t\}\)\+1\)\-\(L\_\{t\}\(a\_\{t,m\}\)\+1\)\\bigr\)\\right\]\+RegImpm⁡\(ℐ\)\.\\displaystyle\+\\operatorname\{Reg\}\_\{\\rm Imp\}^\{m\}\(\\mathcal\{I\}\)\.The equality follows from \([3](https://arxiv.org/html/2607.02891#S3.E3)\):

𝔼τ​\[Lt​\(at,m\)\+1\]=𝔼τ​\[Zt,mqt,m​\(Lt​\(at\)\+1\)\]\.\\mathbb\{E\}\_\{\\tau\}\[L\_\{t\}\(a\_\{t,m\}\)\+1\]=\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\frac\{Z\_\{t,m\}\}\{q\_\{t,m\}\}\\bigl\(L\_\{t\}\(a\_\{t\}\)\+1\\bigr\)\\right\]\.
Apply Lemma[6\.1](https://arxiv.org/html/2607.02891#S6.Thmtheorem1)to the shifted master lossesL~t,m=Lt​\(at,m\)\+1∈\[0,1\]⊂\[0,2\]\\tilde\{L\}\_\{t,m\}=L\_\{t\}\(a\_\{t,m\}\)\+1\\in\[0,1\]\\subset\[0,2\], we have

𝔼τ​\[∑t∈ℐ\(Lt​\(at\)−Lt​\(at,m\)\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\bigl\(L\_\{t\}\(a\_\{t\}\)\-L\_\{t\}\(a\_\{t,m\}\)\\bigr\)\\right\]≤\\displaystyle\\leqO~​\(d​n​Regsq⁡\(n\)\)\\displaystyle\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\\right\)−32​𝔼τ​\[ρℐ,m\]​d​n​Regsq⁡\(n\)\.\\displaystyle\-\\frac\{3\}\{2\}\\mathbb\{E\}\_\{\\tau\}\[\\sqrt\{\\rho\_\{\\mathcal\{I\},m\}\}\]\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\.Adding the preceding base bound cancels theρℐ,m\\rho\_\{\\mathcal\{I\},m\}\-dependent terms:

𝔼τ​\[Reg⁡\(ℐ\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]≤O~​\(d​n​Regsq⁡\(n\)\)\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\\right\)\+\(εm′\+ε¯ℐ2εm′\)​n​d\+2​ε¯ℐ​n\.\\displaystyle\\qquad\+\\left\(\\varepsilon^\{\\prime\}\_\{m\}\+\\frac\{\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\}\{\\varepsilon^\{\\prime\}\_\{m\}\}\\right\)n\\sqrt\{d\}\+2\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}n\.
Finally choose the analysis grid pointm⋆m^\{\\star\}using the fixed upper boundε¯ℐ\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\. Such a point always exists because the geometric grid covers\[1/n,Bε\]\[1/n,B\_\{\\varepsilon\}\]up to a factor two and has1/n1/nas its smallest point\. Ifε¯ℐ≥1/n\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\geq 1/n, the grid construction givesm⋆m^\{\\star\}such thatεm⋆′≤ε¯ℐ≤2​εm⋆′\\varepsilon^\{\\prime\}\_\{m^\{\\star\}\}\\leq\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\leq 2\\varepsilon^\{\\prime\}\_\{m^\{\\star\}\}\. Becauseε¯ℐ\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}is fixed under the block conditioning, this is a fixed comparator base for the master and base lemmas\. Moreover,

εm⋆′\+ε¯ℐ2εm⋆′≤3​ε¯ℐ\.\\varepsilon^\{\\prime\}\_\{m^\{\\star\}\}\+\\frac\{\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}^\{2\}\}\{\\varepsilon^\{\\prime\}\_\{m^\{\\star\}\}\}\\leq 3\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\.Ifε¯ℐ<1/n\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}<1/n, choose the smallest grid pointεm⋆′=1/n\\varepsilon^\{\\prime\}\_\{m^\{\\star\}\}=1/n\. The resulting additiveO​\(d\)O\(\\sqrt\{d\}\)term is absorbed by the leading term\. Hence

𝔼τ​\[Reg⁡\(ℐ\)\]≤O~​\(d​n​Regsq⁡\(n\)\+d​n​ε¯ℐ\)\.\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\+\\sqrt\{d\}\\,n\\,\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\right\)\.With online Newton step for the bounded linear square\-loss class,Regsq⁡\(n\)=O~​\(d\)\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)=\\widetilde\{O\}\(d\), and therefore

𝔼τ​\[Reg⁡\(ℐ\)\]≤O~​\(d​n\+d​n​ε¯ℐ\)\.\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]\\leq\\widetilde\{O\}\\\!\\left\(d\\sqrt\{n\}\+\\sqrt\{d\}\\,n\\,\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\}\\right\)\.

Theorem[3\.4](https://arxiv.org/html/2607.02891#S3.Thmtheorem4)converts the block guarantee of Lemma[3\.1](https://arxiv.org/html/2607.02891#S3.Thmtheorem1)into a dynamic\-regret bound for non\-stationary linear bandits with general compact decision sets, using the restarted corralled SquareCB\.Lin\+ algorithm\.

###### Theorem 3\.4

Suppose Assumptions[2](https://arxiv.org/html/2607.02891#S2)and[3](https://arxiv.org/html/2607.02891#S3)hold\. Suppose the parameter path\(θt\)t=1T\(\\theta\_\{t\}\)\_\{t=1\}^\{T\}is fixed before interaction begins, has known path lengthPTP\_\{T\}, and is independent of the learner’s randomization\. The decision sets may be adaptive but non\-anticipating\. Run Algorithm[1](https://arxiv.org/html/2607.02891#algorithm1)with block length

Δ=⌈min⁡\{T,max⁡\{1,\(d​TL​PT\)2/3\}\}⌉\.\\Delta=\\left\\lceil\\min\\left\\\{T,\\max\\left\\\{1,\\left\(\\frac\{\\sqrt\{d\}\\,T\}\{LP\_\{T\}\}\\right\)^\{2/3\}\\right\\\}\\right\\\}\\right\\rceil\.Here\(d​T/\(L​PT\)\)2/3\(\\sqrt\{d\}\\,T/\(LP\_\{T\}\)\)^\{2/3\}is interpreted as\+∞\+\\inftywhenPT=0P\_\{T\}=0\. Then

RegT≤O~​\(d​T\+L1/3​d5/6​T2/3​PT1/3\)\.\\operatorname\{Reg\}\_\{T\}\\leq\\widetilde\{O\}\\\!\\left\(d\\sqrt\{T\}\+L^\{1/3\}d^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}\\right\)\.

###### Proof 3\.5

Proof of Theorem[3\.4](https://arxiv.org/html/2607.02891#S3.Thmtheorem4)\. Letℐi=\{τi,…,τi\+ni−1\}\\mathcal\{I\}\_\{i\}=\\\{\\tau\_\{i\},\\ldots,\\tau\_\{i\}\+n\_\{i\}\-1\\\}, withni:=\|ℐi\|≤Δn\_\{i\}:=\|\\mathcal\{I\}\_\{i\}\|\\leq\\Delta, denote the restarted blocks\. The last block may haveni<Δn\_\{i\}<\\Delta\. For each block, set

Pℐi:=∑s=τi\+1τi\+ni−1∥θs−θs−1∥2\.P\_\{\\mathcal\{I\}\_\{i\}\}:=\\sum\_\{s=\\tau\_\{i\}\+1\}^\{\\tau\_\{i\}\+n\_\{i\}\-1\}\\\|\\theta\_\{s\}\-\\theta\_\{s\-1\}\\\|\_\{2\}\.Choosing the block anchorθℐi⋆=θτi\\theta\_\{\\mathcal\{I\}\_\{i\}\}^\{\\star\}=\\theta\_\{\\tau\_\{i\}\}, define the fixed analysis radius

ε¯ℐi:=min⁡\{L​Pℐi,Bε\},Bε:=2​L​S\.\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\_\{i\}\}:=\\min\\\{LP\_\{\\mathcal\{I\}\_\{i\}\},B\_\{\\varepsilon\}\\\},\\qquad B\_\{\\varepsilon\}:=2LS\.Because the parameter path is oblivious,PℐiP\_\{\\mathcal\{I\}\_\{i\}\}, and henceε¯ℐi\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\_\{i\}\}, is fixed before the block\. Moreover, for everyt∈ℐit\\in\\mathcal\{I\}\_\{i\}anda∈𝒜ta\\in\\mathcal\{A\}\_\{t\},

\|⟨a,θt−θτi⟩\|≤L​‖θt−θτi‖2≤L​Pℐi,\|\\langle a,\\theta\_\{t\}\-\\theta\_\{\\tau\_\{i\}\}\\rangle\|\\leq L\\\|\\theta\_\{t\}\-\\theta\_\{\\tau\_\{i\}\}\\\|\_\{2\}\\leq LP\_\{\\mathcal\{I\}\_\{i\}\},and also

\|⟨a,θt−θτi⟩\|≤L​\(‖θt‖2\+‖θτi‖2\)≤Bε\.\|\\langle a,\\theta\_\{t\}\-\\theta\_\{\\tau\_\{i\}\}\\rangle\|\\leq L\(\\\|\\theta\_\{t\}\\\|\_\{2\}\+\\\|\\theta\_\{\\tau\_\{i\}\}\\\|\_\{2\}\)\\leq B\_\{\\varepsilon\}\.Thus Assumption[3](https://arxiv.org/html/2607.02891#S3)holds withε¯ℐi\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\_\{i\}\}\. Applying Lemma[3\.1](https://arxiv.org/html/2607.02891#S3.Thmtheorem1)to this restarted block, together withRegsq⁡\(ni\)=O~​\(d\)\\operatorname\{Reg\}\_\{\\rm sq\}\(n\_\{i\}\)=\\widetilde\{O\}\(d\), gives

𝔼τi​\[Reg⁡\(ℐi\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\_\{i\}\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\_\{i\}\)\]≤O~​\(d​ni\+d​ni​ε¯ℐi\)\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(d\\sqrt\{n\_\{i\}\}\+\\sqrt\{d\}\\,n\_\{i\}\\,\\bar\{\\varepsilon\}\_\{\\mathcal\{I\}\_\{i\}\}\\right\)≤O~​\(d​Δ\+L​d​Δ​Pℐi\)\.\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(d\\sqrt\{\\Delta\}\+L\\sqrt\{d\}\\,\\Delta\\,P\_\{\\mathcal\{I\}\_\{i\}\}\\right\)\.LetNNbe the number of restarted blocks in the partition\. Taking expectations and summing over blocks gives

RegT\\displaystyle\\operatorname\{Reg\}\_\{T\}≤O~​\(N​d​Δ\+L​d​Δ​∑i=1NPℐi\)\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(Nd\\sqrt\{\\Delta\}\+L\\sqrt\{d\}\\,\\Delta\\sum\_\{i=1\}^\{N\}P\_\{\\mathcal\{I\}\_\{i\}\}\\right\)≤O~​\(d​TΔ\+L​d​Δ​PT\)\.\\displaystyle\\leq\\widetilde\{O\}\\\!\\left\(\\frac\{dT\}\{\\sqrt\{\\Delta\}\}\+L\\sqrt\{d\}\\,\\Delta P\_\{T\}\\right\)\.Here we usedN≤T/Δ\+1≤2​T/ΔN\\leq T/\\Delta\+1\\leq 2T/\\Deltaand∑iPℐi≤PT\\sum\_\{i\}P\_\{\\mathcal\{I\}\_\{i\}\}\\leq P\_\{T\}\.

IfPT=0P\_\{T\}=0, the theorem setsΔ=T\\Delta=T, and the preceding bound gives

RegT≤O~​\(d​T\)\.\\operatorname\{Reg\}\_\{T\}\\leq\\widetilde\{O\}\(d\\sqrt\{T\}\)\.IfPT\>0P\_\{T\}\>0, let

Δ⋆:=\(d​TL​PT\)2/3\.\\Delta\_\{\\star\}:=\\left\(\\frac\{\\sqrt\{d\}\\,T\}\{LP\_\{T\}\}\\right\)^\{2/3\}\.IfΔ⋆\>T\\Delta\_\{\\star\}\>T, usingΔ=T\\Delta=TgivesRegT≤O~​\(d​T\)\\operatorname\{Reg\}\_\{T\}\\leq\\widetilde\{O\}\(d\\sqrt\{T\}\)\. IfΔ⋆<1\\Delta\_\{\\star\}<1, thenL​PT\>d​TLP\_\{T\}\>\\sqrt\{d\}\\,Timplies thatL1/3​d5/6​T2/3​PT1/3L^\{1/3\}d^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}is at least orderTTford≥1d\\geq 1, so we use the trivial bounded\-regret boundRegT≤T\\operatorname\{Reg\}\_\{T\}\\leq T\. Hence in all cases

RegT≤O~​\(d​T\+L1/3​d5/6​T2/3​PT1/3\)\.\\operatorname\{Reg\}\_\{T\}\\leq\\widetilde\{O\}\\\!\\left\(d\\sqrt\{T\}\+L^\{1/3\}d^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}\\right\)\.

## 4K\-Armed Contextual Linear Bandits with an Oblivious Adversary

In this section we consider theKK\-armed contextual linear\-bandit specialization under an oblivious adversary, where𝒜t=\{xt​\(i\):i∈\[K\]\}\\mathcal\{A\}\_\{t\}=\\\{x\_\{t\}\(i\):i\\in\[K\]\\\}at each round\. In this setting, the restarted SupLinUCB algorithm can be analyzed directly\. This uses the observation ofTakemuraet al\.\([2021](https://arxiv.org/html/2607.02891#bib.bib24)\)that SupLinUCB satisfies a misspecification\-adaptive regret bound\.Because the standard SupLinUCB analysis relies on the stagewise independence property under contexts fixed before the learner’s randomization, our SupLinUCB guarantee inherits the same oblivious\-adversary assumption\.On each block, parameter drift induces a uniform misspecification term, and the confidence/elimination analysis absorbs this perturbation without a CORRAL master\. The logarithmic dependence on the number of arms enters through the quantityΛK:=1\+log⁡K\\Lambda\_\{K\}:=1\+\\log K, which we use throughout this section\.\{assumption\}\[Oblivious block comparator\] The sequence\(𝒜t,θt\)t=1T\(\\mathcal\{A\}\_\{t\},\\theta\_\{t\}\)\_\{t=1\}^\{T\}is fixed before the learner’s randomization\. For each blockℐ\\mathcal\{I\}, choose a comparatorθℐ⋆∈Θ\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\in\\Theta, possibly as a function of the fixed block sequence, and setεℐ:=εℐ​\(θℐ⋆\)\\varepsilon\_\{\\mathcal\{I\}\}:=\\varepsilon\_\{\\mathcal\{I\}\}\(\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\)\.

We use the standard SupLinUCB algorithm ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22), Algorithm 3\), run freshly on each restarted block\. On a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}, set the number of stages toS=⌈log2⁡n⌉S=\\lceil\\log\_\{2\}n\\rceil, initialize all stage sample setsΨτℓ=∅\\Psi\_\{\\tau\}^\{\\ell\}=\\emptyset, and useα=max⁡\{1,12​log⁡\(2​n​K/δ\)\}\\alpha=\\max\\\{1,\\sqrt\{\\frac\{1\}\{2\}\\log\(2nK/\\delta\)\}\\\}\.HereΨtℓ\\Psi\_\{t\}^\{\\ell\}denotes the set of rounds in the current block that have been assigned to stageℓ\\ellbefore roundtt\. In particular,Ψτ\+nℓ\\Psi\_\{\\tau\+n\}^\{\\ell\}is the final stage\-ℓ\\ellsample set for the block\.The stage notationA^ℓ​\(t\)\\widehat\{A\}\_\{\\ell\}\(t\),AtℓA\_\{t\}^\{\\ell\},st,aℓs\_\{t,a\}^\{\\ell\}, andwt,aℓw\_\{t,a\}^\{\\ell\}is as inChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)and is specified in Lemma[6\.3](https://arxiv.org/html/2607.02891#S6.Thmtheorem3)\.At a high level, SupLinUCB maintains stage\-specific sample sets, repeatedly refines the active arm set using upper\-confidence comparisons, and either stops when all surviving arms have small widths or explores an arm with large stage\-ℓ\\ellwidth\.Lemma[4\.1](https://arxiv.org/html/2607.02891#S4.Thmtheorem1)gives the block regret guarantee for restarted SupLinUCB under uniform block misspecification\.

###### Lemma 4\.1

Fix a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}and suppose Assumption[4](https://arxiv.org/html/2607.02891#S4)holds onℐ\\mathcal\{I\}\. Assume that Assumption[2](https://arxiv.org/html/2607.02891#S2)holds,𝒜t=\{xt​\(i\):i∈\[K\]\}\\mathcal\{A\}\_\{t\}=\\\{x\_\{t\}\(i\):i\\in\[K\]\\\},‖a‖2≤1\\\|a\\\|\_\{2\}\\leq 1for alla∈𝒜ta\\in\\mathcal\{A\}\_\{t\}, and‖θℐ⋆‖2≤1\\\|\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\\|\_\{2\}\\leq 1\. Run SupLinUCB freshly onℐ\\mathcal\{I\}with confidence parameterα=max⁡\{1,12​log⁡\(2​n​K/δ\)\}\\alpha=\\max\\\{1,\\sqrt\{\\frac\{1\}\{2\}\\log\(2nK/\\delta\)\}\\\}\. Then, with probability at least1−δ1\-\\delta, conditional onℋτ−1\\mathcal\{H\}\_\{\\tau\-1\},

Reg⁡\(ℐ\)≤O~​\(d​n​ΛK\+εℐ​n​d​ΛK\),\\operatorname\{Reg\}\(\\mathcal\{I\}\)\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\}\\,\\Lambda\_\{K\}\+\\varepsilon\_\{\\mathcal\{I\}\}n\\sqrt\{d\\Lambda\_\{K\}\}\\right\),whereO~​\(⋅\)\\widetilde\{O\}\(\\cdot\)hides polylogarithmic factors inn,d,1/δn,d,1/\\delta, but not inKK\. Consequently, if per\-round regret is bounded by a universal constant, choosingδ=1/n\\delta=1/ngives

𝔼τ​\[Reg⁡\(ℐ\)\]≤O~​\(d​n​ΛK\+εℐ​n​d​ΛK\)\.\\mathbb\{E\}\_\{\\tau\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\)\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\}\\,\\Lambda\_\{K\}\+\\varepsilon\_\{\\mathcal\{I\}\}n\\sqrt\{d\\Lambda\_\{K\}\}\\right\)\.

###### Proof 4\.2

Proof of Lemma[4\.1](https://arxiv.org/html/2607.02891#S4.Thmtheorem1)\. Condition onℋτ−1\\mathcal\{H\}\_\{\\tau\-1\}\. Under Assumption[4](https://arxiv.org/html/2607.02891#S4), writeμt​\(a\)=⟨a,θℐ⋆⟩\+ϵt​\(a\)\\mu\_\{t\}\(a\)=\\langle a,\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\+\\epsilon\_\{t\}\(a\), where\|ϵt​\(a\)\|≤εℐ\|\\epsilon\_\{t\}\(a\)\|\\leq\\varepsilon\_\{\\mathcal\{I\}\}\.After conditioning, the block comparator, the contextual action sets, and the residual functionsϵt​\(⋅\)\\epsilon\_\{t\}\(\\cdot\)are fixed before the within\-block randomization of SupLinUCB\.Thus, relative to the fixed comparatorθℐ⋆\\theta\_\{\\mathcal\{I\}\}^\{\\star\}, the block is a realizable contextual linear bandit with an additive misspecification term that is deterministic after conditioning and uniformly bounded byεℐ\\varepsilon\_\{\\mathcal\{I\}\}\.This is the point at which the oblivious block assumption is used: the misspecification residuals may vary acrossttandaa, but they do not adapt to the current randomized action or reward noise\.By Lemma[6\.3](https://arxiv.org/html/2607.02891#S6.Thmtheorem3), on an event of conditional probability at least1−δ1\-\\delta, all SupLinUCB confidence and elimination comparisons satisfy the usual realizable bounds with an additional perturbation

Δℐ=C​εℐ​α​d\.\\Delta\_\{\\mathcal\{I\}\}=C\\varepsilon\_\{\\mathcal\{I\}\}\\alpha\\sqrt\{d\}\.Hence the subsequent argument can follow the original SupLinUCB exploration/elimination counting proof, with each comparison paying an additionalO​\(Δℐ\)O\(\\Delta\_\{\\mathcal\{I\}\}\)error\.SupLinUCB either explores at some stageℓ\\ell, in which case the played round is added to the stage\-ℓ\\ellsample set, or it stops confidently and plays from the surviving active set\. Letℰℓ\\mathcal\{E\}\_\{\\ell\}be the set of rounds on which the algorithm explores at stageℓ\\ell, and let𝒯conf\\mathcal\{T\}\_\{\\rm conf\}be the set of confident\-stopping rounds\. These sets partitionℐ\\mathcal\{I\}:each round either explores at exactly one stage or stops confidently, so every round is counted once\.Moreover,ℰℓ=Ψτ\+nℓ\\mathcal\{E\}\_\{\\ell\}=\\Psi\_\{\\tau\+n\}^\{\\ell\}, since the restarted algorithm initializesΨτℓ=∅\\Psi\_\{\\tau\}^\{\\ell\}=\\emptysetand adds a round toΨℓ\\Psi^\{\\ell\}exactly when it explores at stageℓ\\ell\. On an exploration round inℰℓ\\mathcal\{E\}\_\{\\ell\}, the active\-set part of Lemma[6\.3](https://arxiv.org/html/2607.02891#S6.Thmtheorem3)bounds the instantaneous regret byC​2−ℓ\+C​S​ΔℐC2^\{\-\\ell\}\+CS\\Delta\_\{\\mathcal\{I\}\}\. On a confident\-stopping round, the same lemma givesC​n−1/2\+C​S​ΔℐCn^\{\-1/2\}\+CS\\Delta\_\{\\mathcal\{I\}\}\. Summing these two bounds over the partition gives

Reg⁡\(ℐ\)\\displaystyle\\operatorname\{Reg\}\(\\mathcal\{I\}\)≤∑ℓ=1S\|ℰℓ\|​\(C​2−ℓ\+C​S​Δℐ\)\+\|𝒯conf\|​\(C​n−1/2\+C​S​Δℐ\)\\displaystyle\\leq\\sum\_\{\\ell=1\}^\{S\}\|\\mathcal\{E\}\_\{\\ell\}\|\\bigl\(C2^\{\-\\ell\}\+CS\\Delta\_\{\\mathcal\{I\}\}\\bigr\)\+\|\\mathcal\{T\}\_\{\\rm conf\}\|\\bigl\(Cn^\{\-1/2\}\+CS\\Delta\_\{\\mathcal\{I\}\}\\bigr\)≤C​∑ℓ=1S2−ℓ​\|ℰℓ\|\+C​n\+C​S​Δℐ​n,\\displaystyle\\leq C\\sum\_\{\\ell=1\}^\{S\}2^\{\-\\ell\}\|\\mathcal\{E\}\_\{\\ell\}\|\+C\\sqrt\{n\}\+CS\\Delta\_\{\\mathcal\{I\}\}n,where the second inequality uses\|𝒯conf\|≤n\|\\mathcal\{T\}\_\{\\rm conf\}\|\\leq nand∑ℓ=1S\|ℰℓ\|\+\|𝒯conf\|=n\\sum\_\{\\ell=1\}^\{S\}\|\\mathcal\{E\}\_\{\\ell\}\|\+\|\\mathcal\{T\}\_\{\\rm conf\}\|=n\. Sinceℰℓ=Ψτ\+nℓ\\mathcal\{E\}\_\{\\ell\}=\\Psi\_\{\\tau\+n\}^\{\\ell\}, this yields

Reg⁡\(ℐ\)\\displaystyle\\operatorname\{Reg\}\(\\mathcal\{I\}\)≤C​∑ℓ=1S2−ℓ​\|Ψτ\+nℓ\|\+C​n\+C​S​Δℐ​n\.\\displaystyle\\leq C\\sum\_\{\\ell=1\}^\{S\}2^\{\-\\ell\}\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\+C\\sqrt\{n\}\+CS\\Delta\_\{\\mathcal\{I\}\}n\.HereS=⌈log2⁡n⌉S=\\lceil\\log\_\{2\}n\\rceil\. Lemma 6 ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)gives

\|Ψτ\+nℓ\|≤5⋅2ℓ​\(1\+α2\)​d​\|Ψτ\+nℓ\|\.\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\\leq 5\\cdot 2^\{\\ell\}\(1\+\\alpha^\{2\}\)\\sqrt\{d\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\}\.This invocation is unaffected by misspecification because Lemma 6 ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)is a deterministic counting bound for the stage\-ℓ\\ellsample set, based on the elliptical\-potential argument and the rule that a round is added toΨℓ\\Psi^\{\\ell\}only when its stage\-ℓ\\ellwidth is large\. It does not rely on the linear reward model being well specified, nor on the confidence intervals being valid for the true rewards\.Multiplying this display by2−ℓ2^\{\-\\ell\}and summing over stages gives

∑ℓ=1S2−ℓ​\|Ψτ\+nℓ\|≤C​\(1\+α2\)​d​∑ℓ=1S\|Ψτ\+nℓ\|\.\\sum\_\{\\ell=1\}^\{S\}2^\{\-\\ell\}\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\\leq C\(1\+\\alpha^\{2\}\)\\sqrt\{d\}\\sum\_\{\\ell=1\}^\{S\}\\sqrt\{\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\}\.Since the stage sample sets are disjoint and contain at mostnnrounds, Cauchy–Schwarz gives

∑ℓ=1S\|Ψτ\+nℓ\|≤S​∑ℓ=1S\|Ψτ\+nℓ\|≤S​n\.\\sum\_\{\\ell=1\}^\{S\}\\sqrt\{\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\}\\leq\\sqrt\{S\\sum\_\{\\ell=1\}^\{S\}\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\}\\leq\\sqrt\{Sn\}\.Therefore,

∑ℓ=1S2−ℓ​\|Ψτ\+nℓ\|≤C​\(1\+α2\)​d​S​n\.\\sum\_\{\\ell=1\}^\{S\}2^\{\-\\ell\}\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\\leq C\(1\+\\alpha^\{2\}\)\\sqrt\{dSn\}\.UsingS=O​\(log⁡n\)S=O\(\\log n\),α2=O​\(log⁡\(n​K/δ\)\)\\alpha^\{2\}=O\(\\log\(nK/\\delta\)\), andΔℐ=C​εℐ​α​d\\Delta\_\{\\mathcal\{I\}\}=C\\varepsilon\_\{\\mathcal\{I\}\}\\alpha\\sqrt\{d\}, we obtain

Reg⁡\(ℐ\)≤O~​\(d​n​ΛK\+εℐ​n​d​ΛK\)\\operatorname\{Reg\}\(\\mathcal\{I\}\)\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\}\\,\\Lambda\_\{K\}\+\\varepsilon\_\{\\mathcal\{I\}\}n\\sqrt\{d\\Lambda\_\{K\}\}\\right\)with conditional probability at least1−δ1\-\\delta\. Takingδ=1/n\\delta=1/nand using bounded per\-round regret gives the conditional expectation bound\.

Theorem[4\.3](https://arxiv.org/html/2607.02891#S4.Thmtheorem3)converts the SupLinUCB block guarantee into a known\-path\-length dynamic regret bound for theKK\-armed contextual case\.

###### Theorem 4\.3

Consider theKK\-armed contextual linear\-bandit setting under Assumptions[2](https://arxiv.org/html/2607.02891#S2),[2](https://arxiv.org/html/2607.02891#S2), and[4](https://arxiv.org/html/2607.02891#S4), with𝒜t=\{xt​\(i\):i∈\[K\]\}\\mathcal\{A\}\_\{t\}=\\\{x\_\{t\}\(i\):i\\in\[K\]\\\},‖a‖2≤1\\\|a\\\|\_\{2\}\\leq 1, and‖θt‖2≤1\\\|\\theta\_\{t\}\\\|\_\{2\}\\leq 1\. Run SupLinUCB independently on consecutive blocks of length

Δ=⌈min⁡\{T,max⁡\{1,\(ΛK​TPT\)2/3\}\}⌉,\\Delta=\\left\\lceil\\min\\left\\\{T,\\max\\left\\\{1,\\left\(\\frac\{\\sqrt\{\\Lambda\_\{K\}\}\\,T\}\{P\_\{T\}\}\\right\)^\{2/3\}\\right\\\}\\right\\\}\\right\\rceil,where\(ΛK​T/PT\)2/3\(\\sqrt\{\\Lambda\_\{K\}\}T/P\_\{T\}\)^\{2/3\}is interpreted as\+∞\+\\inftywhenPT=0P\_\{T\}=0\. Then

RegT≤O~​\(d​T​ΛK\+d​ΛK5/6​T2/3​PT1/3\),\\operatorname\{Reg\}\_\{T\}\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dT\}\\,\\Lambda\_\{K\}\+\\sqrt\{d\}\\,\\Lambda\_\{K\}^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}\\right\),whereO~​\(⋅\)\\widetilde\{O\}\(\\cdot\)hides polylogarithmic factors inT,dT,d, but not inKK\.

###### Proof 4\.4

Proof of Theorem[4\.3](https://arxiv.org/html/2607.02891#S4.Thmtheorem3)\. On each blockℐi=\{τi,…,τi\+ni−1\}\\mathcal\{I\}\_\{i\}=\\\{\\tau\_\{i\},\\ldots,\\tau\_\{i\}\+n\_\{i\}\-1\\\}, the anchorθℐi⋆=θτi\\theta\_\{\\mathcal\{I\}\_\{i\}\}^\{\\star\}=\\theta\_\{\\tau\_\{i\}\}givesεℐi≤Pℐi\\varepsilon\_\{\\mathcal\{I\}\_\{i\}\}\\leq P\_\{\\mathcal\{I\}\_\{i\}\}, wherePℐi:=∑s=τi\+1τi\+ni−1‖θs−θs−1‖2P\_\{\\mathcal\{I\}\_\{i\}\}:=\\sum\_\{s=\\tau\_\{i\}\+1\}^\{\\tau\_\{i\}\+n\_\{i\}\-1\}\\\|\\theta\_\{s\}\-\\theta\_\{s\-1\}\\\|\_\{2\}\. The norm bounds also give‖θℐi⋆‖2≤1\\\|\\theta\_\{\\mathcal\{I\}\_\{i\}\}^\{\\star\}\\\|\_\{2\}\\leq 1and uniformly bounded per\-round regret\. Lemma[4\.1](https://arxiv.org/html/2607.02891#S4.Thmtheorem1)therefore gives

𝔼τi​\[Reg⁡\(ℐi\)\]≤O~​\(d​ni​ΛK\+d​ΛK​ni​Pℐi\)\.\\mathbb\{E\}\_\{\\tau\_\{i\}\}\[\\operatorname\{Reg\}\(\\mathcal\{I\}\_\{i\}\)\]\\leq\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\_\{i\}\}\\,\\Lambda\_\{K\}\+\\sqrt\{d\\Lambda\_\{K\}\}\\,n\_\{i\}P\_\{\\mathcal\{I\}\_\{i\}\}\\right\)\.Summing over the restarted blocks gives the tradeoff

RegT≤O~​\(d​ΛK​TΔ\+d​ΛK​Δ​PT\)\.\\operatorname\{Reg\}\_\{T\}\\leq\\widetilde\{O\}\\\!\\left\(\\frac\{\\sqrt\{d\}\\,\\Lambda\_\{K\}T\}\{\\sqrt\{\\Delta\}\}\+\\sqrt\{d\\Lambda\_\{K\}\}\\,\\Delta P\_\{T\}\\right\)\.Optimizing this display with the chosenΔ\\Deltagives the stated bound\. The endpoint casesΔ=T\\Delta=TandΔ=1\\Delta=1are handled as in Theorem[3\.4](https://arxiv.org/html/2607.02891#S3.Thmtheorem4)\.

The following proposition records a lower bound for non\-stationaryKK\-armed contextual linear bandits\. A proof sketch is deferred to Appendix[7](https://arxiv.org/html/2607.02891#S7)\.

###### Proposition 4\.5

ConsiderKK\-armed contextual linear bandits withK≥2K\\geq 2actions per round,‖xt,a‖2≤1\\\|x\_\{t,a\}\\\|\_\{2\}\\leq 1,‖θt‖2≤1\\\|\\theta\_\{t\}\\\|\_\{2\}\\leq 1, and path\-length∑t=1T−1‖θt\+1−θt‖2≤PT\\sum\_\{t=1\}^\{T\-1\}\\\|\\theta\_\{t\+1\}\-\\theta\_\{t\}\\\|\_\{2\}\\leq P\_\{T\}\. LetΓd,K\\Gamma\_\{d,K\}be the maximum of\(d​min⁡\{K,d\}\)1/6\(d\\min\\\{K,d\\\}\)^\{1/6\}and\(min⁡\{d,⌊log2⁡K⌋\}\)2/3\(\\min\\\{d,\\lfloor\\log\_\{2\}K\\rfloor\\\}\)^\{2/3\}\. Then the minimax dynamic regret is at leastΩ​\(d​T∨PT1/3​T2/3​Γd,K\)\\Omega\(\\sqrt\{dT\}\\vee P\_\{T\}^\{1/3\}T^\{2/3\}\\Gamma\_\{d,K\}\)\. The lower bound holds for obliviously chosen contexts and parameter sequences\.

Proposition[4\.5](https://arxiv.org/html/2607.02891#S4.Thmtheorem5)shows that the restarted SupLinUCB bound is optimal in its dependence onTTandPTP\_\{T\}\. The remaining gap is in the dimension/action\-set dependence: the upper bound has non\-stationary coefficientd​ΛK5/6\\sqrt\{d\}\\,\\Lambda\_\{K\}^\{5/6\}, whereas the lower bound givesΓd,K\\Gamma\_\{d,K\}\. We leave closing this dimension/action\-set dependence gap for future work\.

## 5Conclusion

We studied non\-stationary linear bandits with round\-specific decision sets through a misspecification\-reduction viewpoint, deriving dynamic\-regret guarantees with optimal dependence onTTandPTP\_\{T\}for both general linear bandits andKK\-armed contextual linear bandits\.

Two important questions remain open\. First, the general linear\-bandit guaranteeO~​\(d5/6​T2/3​PT1/3\)\\widetilde\{O\}\(d^\{5/6\}T^\{2/3\}P\_\{T\}^\{1/3\}\)has a factorO~​\(d1/6\)\\widetilde\{O\}\(d^\{1/6\}\)gap relative to theΩ​\(d2/3​T2/3​PT1/3\)\\Omega\(d^\{2/3\}T^\{2/3\}P\_\{T\}^\{1/3\}\)lower bound ofCheunget al\.\([2022](https://arxiv.org/html/2607.02891#bib.bib7)\)\. Closing this dimension gap is an important theoretical question\. Second, for non\-stationary linear bandits with general compact decision sets, it remains unclear whether the CORRAL\-style aggregation layer is necessary, or whether one can design a single base algorithm that adapts directly to the unknown block misspecification level, in the spirit of adaptive guarantees such asHuet al\.\([2025](https://arxiv.org/html/2607.02891#bib.bib25)\)\.

## Acknowledgements

We thank Feng Ruan, Yinyu Ye, Hongfan Wu, and Peng Zhao for helpful discussions at different stages of this work\.

## References

- Improved algorithms for linear stochastic bandits\.InAdvances in Neural Information Processing Systems,Vol\.24,pp\. 2312–2320\.Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p1.1)\.
- A\. Agarwal, H\. Luo, B\. Neyshabur, and R\. E\. Schapire \(2017\)Corralling a band of bandit algorithms\.InProceedings of the Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.65,pp\. 12–38\.Cited by:[§3](https://arxiv.org/html/2607.02891#S3.p6.1)\.
- O\. Besbes, Y\. Gur, and A\. Zeevi \(2015\)Non\-stationary stochastic optimization\.Operations Research63\(5\),pp\. 1227–1244\.External Links:[Document](https://dx.doi.org/10.1287/opre.2015.1408)Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p2.10),[§1](https://arxiv.org/html/2607.02891#S1.p8.1),[§3](https://arxiv.org/html/2607.02891#S3.p6.1)\.
- O\. Besbes and A\. Zeevi \(2011\)On the minimax complexity of pricing in a changing environment\.Operations Research59\(1\),pp\. 66–79\.External Links:[Document](https://dx.doi.org/10.1287/opre.1100.0867)Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p2.10)\.
- X\. Chen, Y\. Wang, and Y\. Wang \(2019\)Technical note—nonstationary stochastic optimization underLp,qL\_\{p,q\}\-variation measures\.Operations Research67\(6\),pp\. 1752–1765\.External Links:[Document](https://dx.doi.org/10.1287/opre.2019.1843)Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p2.10)\.
- W\. C\. Cheung, D\. Simchi\-Levi, and R\. Zhu \(2022\)Hedging the drift: learning to optimize under nonstationarity\.Management Science68\(3\),pp\. 1696–1713\.External Links:[Document](https://dx.doi.org/10.1287/mnsc.2021.4024)Cited by:[1st item](https://arxiv.org/html/2607.02891#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2607.02891#S1.p2.10),[§1](https://arxiv.org/html/2607.02891#S1.p3.3),[§1](https://arxiv.org/html/2607.02891#S1.p7.1),[§1](https://arxiv.org/html/2607.02891#S1.p8.1),[§5](https://arxiv.org/html/2607.02891#S5.p2.3)\.
- 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:[2nd item](https://arxiv.org/html/2607.02891#S1.I1.i2.p1.3),[§1](https://arxiv.org/html/2607.02891#S1.p1.1),[§2](https://arxiv.org/html/2607.02891#S2.p6.6),[Proof 4\.2](https://arxiv.org/html/2607.02891#S4.Thmtheorem2.p1.27.1),[Proof 4\.2](https://arxiv.org/html/2607.02891#S4.Thmtheorem2.p1.31.4),[§4](https://arxiv.org/html/2607.02891#S4.p2.14),[Proof 6\.4](https://arxiv.org/html/2607.02891#S6.Thmtheorem4.p1.1.1),[Proof 6\.4](https://arxiv.org/html/2607.02891#S6.Thmtheorem4.p3.10.2),[Proof 6\.4](https://arxiv.org/html/2607.02891#S6.Thmtheorem4.p4.4.4),[§7](https://arxiv.org/html/2607.02891#S7.p1.6),[§7](https://arxiv.org/html/2607.02891#S7.p2.3)\.
- V\. Dani, T\. P\. Hayes, and S\. M\. Kakade \(2008\)Stochastic linear optimization under bandit feedback\.InProceedings of the 21st Annual Conference on Learning Theory,pp\. 355–366\.Cited by:[§7](https://arxiv.org/html/2607.02891#S7.p3.6)\.
- D\. J\. Foster, C\. Gentile, M\. Mohri, and J\. Zimmert \(2020\)Adapting to misspecification in contextual bandits\.Advances in Neural Information Processing Systems33,pp\. 11478–11489\.Cited by:[1st item](https://arxiv.org/html/2607.02891#S1.I1.i1.p1.2),[§1](https://arxiv.org/html/2607.02891#S1.p7.1),[§1](https://arxiv.org/html/2607.02891#S1.p8.1),[Proof 3\.2](https://arxiv.org/html/2607.02891#S3.Thmtheorem2.p2.7.2),[Proof 3\.2](https://arxiv.org/html/2607.02891#S3.Thmtheorem2.p7.20.1),[Remark 3\.3](https://arxiv.org/html/2607.02891#S3.Thmtheorem3.p1.1.1),[§3](https://arxiv.org/html/2607.02891#S3.p1.9),[§3](https://arxiv.org/html/2607.02891#S3.p6.1),[§3](https://arxiv.org/html/2607.02891#S3.p7.7),[Lemma 6\.1](https://arxiv.org/html/2607.02891#S6.Thmtheorem1),[Lemma 6\.1](https://arxiv.org/html/2607.02891#S6.Thmtheorem1.p1.5.5),[Lemma 6\.2](https://arxiv.org/html/2607.02891#S6.Thmtheorem2),[15](https://arxiv.org/html/2607.02891#algorithm1.23.23)\.
- E\. Hazan, A\. Agarwal, and S\. Kale \(2007\)Logarithmic regret algorithms for online convex optimization\.Machine Learning69\(2–3\),pp\. 169–192\.Cited by:[§3](https://arxiv.org/html/2607.02891#S3.p7.7)\.
- Z\. Hu, X\. Fan, Y\. Yao, J\. Zhang, and Z\. Zhou \(2025\)Learning to bid in non\-stationary repeated first\-price auctions\.arXiv preprint arXiv:2501\.13358\.Cited by:[§5](https://arxiv.org/html/2607.02891#S5.p2.3)\.
- N\. B\. Keskin and A\. Zeevi \(2017\)Chasing demand: learning and earning in a changing environment\.Mathematics of Operations Research42\(2\),pp\. 277–307\.External Links:[Document](https://dx.doi.org/10.1287/moor.2016.0807)Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p2.10)\.
- T\. Lattimore and C\. Szepesvári \(2020\)Bandit algorithms\.Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/9781108571401)Cited by:[§7](https://arxiv.org/html/2607.02891#S7.p3.6)\.
- Y\. Russac, C\. Vernade, and O\. Cappé \(2019\)Weighted linear bandits for non\-stationary environments\.InAdvances in Neural Information Processing Systems,Vol\.32,pp\. 12040–12049\.Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p3.3),[§1](https://arxiv.org/html/2607.02891#S1.p8.1)\.
- K\. Takemura, S\. Ito, D\. Hatano, H\. Sumita, T\. Fukunaga, N\. Kakimura, and K\. Kawarabayashi \(2021\)A parameter\-free algorithm for misspecified linear contextual bandits\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 3367–3375\.Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p8.1),[§4](https://arxiv.org/html/2607.02891#S4.p1.7)\.
- J\. Wang, P\. Zhao, and Z\. Zhou \(2025\)Revisiting weighted strategy for non\-stationary parametric bandits and mdps\.IEEE Transactions on Information Theory\.Note:AcceptedCited by:[§1](https://arxiv.org/html/2607.02891#S1.p3.3),[§1](https://arxiv.org/html/2607.02891#S1.p8.1)\.
- Y\. Wang \(2025\)On adaptivity in nonstationary stochastic optimization with bandit feedback\.Operations Research73\(2\),pp\. 819–828\.Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p2.10)\.
- P\. Zhao, L\. Zhang, Y\. Jiang, and Z\. Zhou \(2021\)A simple approach for non\-stationary linear bandits\.arXiv preprint arXiv:2103\.05324\.Cited by:[§1](https://arxiv.org/html/2607.02891#S1.p3.3),[§1](https://arxiv.org/html/2607.02891#S1.p7.1),[§1](https://arxiv.org/html/2607.02891#S1.p8.1)\.

\{APPENDICES\}

## 6Technical Lemmas

###### Lemma 6\.1\(Fosteret al\.[2020](https://arxiv.org/html/2607.02891#bib.bib21)\)

Consider a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}withMMbase learners and master lossesL~t,m∈\[0,2\]\\tilde\{L\}\_\{t,m\}\\in\[0,2\]\. Suppose the master runs the\(1/2,32​d​n​Regsq⁡\(n\)\)\\left\(1/2,\\frac\{3\}\{2\}\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\\right\)\-hedged Tsallis\-INF algorithm ofFosteret al\.\([2020](https://arxiv.org/html/2607.02891#bib.bib21)\)on this block\. Then, for every fixed basem∈\[M\]m\\in\[M\], the master regret is bounded by

𝔼τ​\[∑t∈ℐ\(L~t,Mt−L~t,m\)\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\!\\left\[\\sum\_\{t\\in\\mathcal\{I\}\}\\bigl\(\\tilde\{L\}\_\{t,M\_\{t\}\}\-\\tilde\{L\}\_\{t,m\}\\bigr\)\\right\]≤\\displaystyle\\leqO~​\(d​n​Regsq⁡\(n\)\)\\displaystyle\\widetilde\{O\}\\\!\\left\(\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\\right\)−32​𝔼τ​\[ρℐ,m\]​d​n​Regsq⁡\(n\)\.\\displaystyle\\quad\-\\frac\{3\}\{2\}\\mathbb\{E\}\_\{\\tau\}\[\\sqrt\{\\rho\_\{\\mathcal\{I\},m\}\}\]\\sqrt\{dn\\,\\operatorname\{Reg\}\_\{\\rm sq\}\(n\)\}\.

###### Lemma 6\.2\(Fosteret al\.[2020](https://arxiv.org/html/2607.02891#bib.bib21)\)

Let𝒜⊂ℝd\\mathcal\{A\}\\subset\\mathbb\{R\}^\{d\},γ\>0\\gamma\>0, andβ^∈ℝd\\widehat\{\\beta\}\\in\\mathbb\{R\}^\{d\}\. Forp∈Δ​\(𝒜\)p\\in\\Delta\(\\mathcal\{A\}\), writea¯p:=𝔼a∼p​\[a\]\\bar\{a\}\_\{p\}:=\\mathbb\{E\}\_\{a\\sim p\}\[a\]andHp:=𝔼a∼p​\[a​a⊤\]H\_\{p\}:=\\mathbb\{E\}\_\{a\\sim p\}\[aa^\{\\top\}\]\. Letppbe any member oflogdet​\-​barrier⁡\(β^,γ;𝒜\)\\operatorname\{logdet\\text\{\-\}barrier\}\(\\widehat\{\\beta\},\\gamma;\\mathcal\{A\}\), as defined in \([1](https://arxiv.org/html/2607.02891#S3.E1)\)\. Then, for everya⋆∈𝒜a^\{\\star\}\\in\\mathcal\{A\}and everyβ∈ℝd\\beta\\in\\mathbb\{R\}^\{d\},

⟨a¯p−a⋆,β⟩≤\\displaystyle\\langle\\bar\{a\}\_\{p\}\-a^\{\\star\},\\beta\\rangle\\leqdim\(𝒜\)γ\+γ4​‖β^−β‖Hp2\\displaystyle\\frac\{\\dim\(\\mathcal\{A\}\)\}\{\\gamma\}\+\\frac\{\\gamma\}\{4\}\\\|\\widehat\{\\beta\}\-\\beta\\\|\_\{H\_\{p\}\}^\{2\}≤\\displaystyle\\leqdγ\+γ4​‖β^−β‖Hp2\.\\displaystyle\\frac\{d\}\{\\gamma\}\+\\frac\{\\gamma\}\{4\}\\\|\\widehat\{\\beta\}\-\\beta\\\|\_\{H\_\{p\}\}^\{2\}\.

###### Lemma 6\.3\(Perturbed SupLinUCB facts\)

Fix a blockℐ=\{τ,…,τ\+n−1\}\\mathcal\{I\}=\\\{\\tau,\\ldots,\\tau\+n\-1\\\}and condition onℋτ−1\\mathcal\{H\}\_\{\\tau\-1\}\. Suppose Assumption[4](https://arxiv.org/html/2607.02891#S4)holds, and writeμt​\(a\)=⟨a,θℐ⋆⟩\+ϵt​\(a\)\\mu\_\{t\}\(a\)=\\langle a,\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\+\\epsilon\_\{t\}\(a\), where\|ϵt​\(a\)\|≤εℐ\|\\epsilon\_\{t\}\(a\)\|\\leq\\varepsilon\_\{\\mathcal\{I\}\}\. Let SupLinUCB be run freshly onℐ\\mathcal\{I\}\. Then, conditional onℋτ−1\\mathcal\{H\}\_\{\\tau\-1\}, with probability at least1−δ1\-\\delta, the following two statements hold simultaneously, with the stagewise notation defined in the proof\. First, whenever the algorithm uses the stage\-ℓ\\ellscoresr^t,aℓ\+wt,aℓ\\hat\{r\}\_\{t,a\}^\{\\ell\}\+w\_\{t,a\}^\{\\ell\}either to select an arm confidently or to eliminate arms, the following bound holds for every active arm involved:

\|r^t,aℓ−μt​\(a\)\|≤2​wt,aℓ\+Δℐ,Δℐ:=C​εℐ​α​d\.\|\\hat\{r\}\_\{t,a\}^\{\\ell\}\-\\mu\_\{t\}\(a\)\|\\leq 2w\_\{t,a\}^\{\\ell\}\+\\Delta\_\{\\mathcal\{I\}\},\\qquad\\Delta\_\{\\mathcal\{I\}\}:=C\\varepsilon\_\{\\mathcal\{I\}\}\\alpha\\sqrt\{d\}\.\(10\)Second, for every roundt∈ℐt\\in\\mathcal\{I\}and every stageℓ\\ellreached on that round,

μt​\(at⋆\)−μt​\(a\)≤C​2−ℓ\+C​ℓ​Δℐ,a∈A^ℓ​\(t\)\.\\mu\_\{t\}\(a\_\{t\}^\{\\star\}\)\-\\mu\_\{t\}\(a\)\\leq C2^\{\-\\ell\}\+C\\ell\\Delta\_\{\\mathcal\{I\}\},\\qquad a\\in\\widehat\{A\}\_\{\\ell\}\(t\)\.\(11\)Moreover, on a confident stopping round,

μt​\(at⋆\)−μt​\(at\)≤C​n−1/2\+C​S​Δℐ\.\\mu\_\{t\}\(a\_\{t\}^\{\\star\}\)\-\\mu\_\{t\}\(a\_\{t\}\)\\leq Cn^\{\-1/2\}\+CS\\Delta\_\{\\mathcal\{I\}\}\.\(12\)HereS:=⌈log2⁡n⌉S:=\\lceil\\log\_\{2\}n\\rceil\.

###### Proof 6\.4

Proof of Lemma[6\.3](https://arxiv.org/html/2607.02891#S6.Thmtheorem3)\. Under Assumption[4](https://arxiv.org/html/2607.02891#S4), the block sequence is fixed before the learner’s randomization\. Therefore the original SupLinUCB construction satisfies the stagewise independence property established in Lemma 4 ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)\. We use this property below\.

LetS=⌈log2⁡n⌉S=\\lceil\\log\_\{2\}n\\rceil\. For each stageℓ∈\[S\]\\ell\\in\[S\], letΨtℓ\\Psi\_\{t\}^\{\\ell\}collect the stage\-ℓ\\ellsamples from the current block available before roundtt\. Define

Atℓ=Id\+∑ρ∈Ψtℓaρ​aρ⊤,st,aℓ=a⊤​\(Atℓ\)−1​a\.A\_\{t\}^\{\\ell\}=I\_\{d\}\+\\sum\_\{\\rho\\in\\Psi\_\{t\}^\{\\ell\}\}a\_\{\\rho\}a\_\{\\rho\}^\{\\top\},\\qquad s\_\{t,a\}^\{\\ell\}=\\sqrt\{a^\{\\top\}\(A\_\{t\}^\{\\ell\}\)^\{\-1\}a\}\.Setwt,aℓ:=α​st,aℓw\_\{t,a\}^\{\\ell\}:=\\alpha s\_\{t,a\}^\{\\ell\}\. Let

θ^tℓ=\(Atℓ\)−1​∑ρ∈Ψtℓaρ​rρ,r^t,aℓ=⟨a,θ^tℓ⟩\.\\widehat\{\\theta\}\_\{t\}^\{\\ell\}=\(A\_\{t\}^\{\\ell\}\)^\{\-1\}\\sum\_\{\\rho\\in\\Psi\_\{t\}^\{\\ell\}\}a\_\{\\rho\}r\_\{\\rho\},\\qquad\\hat\{r\}\_\{t,a\}^\{\\ell\}=\\langle a,\\widehat\{\\theta\}\_\{t\}^\{\\ell\}\\rangle\.LetA^ℓ​\(t\)\\widehat\{A\}\_\{\\ell\}\(t\)be the active arm set when roundttreaches stageℓ\\ell, and letat⋆∈\\argmaxa∈𝒜t​μt​\(a\)a\_\{t\}^\{\\star\}\\in\\argmax\_\{a\\in\\mathcal\{A\}\_\{t\}\}\\mu\_\{t\}\(a\)\.

The rest of the proof is the standard SupLinUCB proof with two deterministic misspecification terms\. For a fixed stageℓ\\ell, letDtℓD\_\{t\}^\{\\ell\}be the design matrix formed by the samples inΨtℓ\\Psi\_\{t\}^\{\\ell\}\. Since

rρ=⟨aρ,θℐ⋆⟩\+ϵρ​\(aρ\)\+ηρ,r\_\{\\rho\}=\\langle a\_\{\\rho\},\\theta\_\{\\mathcal\{I\}\}^\{\\star\}\\rangle\+\\epsilon\_\{\\rho\}\(a\_\{\\rho\}\)\+\\eta\_\{\\rho\},whereϵ=\(ϵρ​\(aρ\)\)ρ∈Ψtℓ\\epsilon=\(\\epsilon\_\{\\rho\}\(a\_\{\\rho\}\)\)\_\{\\rho\\in\\Psi\_\{t\}^\{\\ell\}\}denotes the vector of signed misspecification residuals\. The usual BaseLinUCB decomposition gives the realizable confidence term\(α\+1\)​st,aℓ\(\\alpha\+1\)s\_\{t,a\}^\{\\ell\}\. Sincewt,aℓ=α​st,aℓw\_\{t,a\}^\{\\ell\}=\\alpha s\_\{t,a\}^\{\\ell\}andα≥1\\alpha\\geq 1, this term is at most2​wt,aℓ2w\_\{t,a\}^\{\\ell\}\. Hence

\|r^t,aℓ−μt​\(a\)\|\\displaystyle\|\\hat\{r\}\_\{t,a\}^\{\\ell\}\-\\mu\_\{t\}\(a\)\|≤2​wt,aℓ\+\|a⊤​\(Atℓ\)−1​\(Dtℓ\)⊤​ϵ\|\+εℐ\\displaystyle\\leq 2w\_\{t,a\}^\{\\ell\}\+\\left\|a^\{\\top\}\(A\_\{t\}^\{\\ell\}\)^\{\-1\}\(D\_\{t\}^\{\\ell\}\)^\{\\top\}\\epsilon\\right\|\+\\varepsilon\_\{\\mathcal\{I\}\}≤2​wt,aℓ\+εℐ​\|Ψtℓ\|​st,aℓ\+εℐ\.\\displaystyle\\leq 2w\_\{t,a\}^\{\\ell\}\+\\varepsilon\_\{\\mathcal\{I\}\}\\sqrt\{\|\\Psi\_\{t\}^\{\\ell\}\|\}\\,s\_\{t,a\}^\{\\ell\}\+\\varepsilon\_\{\\mathcal\{I\}\}\.The first term is the standard confidence term inChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)\. The last two terms are the misspecification contributions\. The finalεℐ\\varepsilon\_\{\\mathcal\{I\}\}term will be absorbed intoΔℐ\\Delta\_\{\\mathcal\{I\}\}\. By Lemma 6 ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\),

\|Ψτ\+nℓ\|≤5⋅2ℓ​\(1\+α2\)​d\.\\sqrt\{\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\}\\leq 5\\cdot 2^\{\\ell\}\(1\+\\alpha^\{2\}\)\\sqrt\{d\}\.Whenever the algorithm performs a stage\-ℓ\\ellelimination comparison,wt,aℓ≤2−ℓw\_\{t,a\}^\{\\ell\}\\leq 2^\{\-\\ell\}for all active arms, and hence

st,aℓ≤2−ℓα\.s\_\{t,a\}^\{\\ell\}\\leq\\frac\{2^\{\-\\ell\}\}\{\\alpha\}\.By definition of the stage sample sets,Ψtℓ⊆Ψτ\+nℓ\\Psi\_\{t\}^\{\\ell\}\\subseteq\\Psi\_\{\\tau\+n\}^\{\\ell\}for allt≤τ\+nt\\leq\\tau\+n\. Therefore

\|Ψtℓ\|​st,aℓ≤\|Ψτ\+nℓ\|​2−ℓα≤5​1\+α2α​d≤10​α​d\.\\sqrt\{\|\\Psi\_\{t\}^\{\\ell\}\|\}\\,s\_\{t,a\}^\{\\ell\}\\leq\\sqrt\{\|\\Psi\_\{\\tau\+n\}^\{\\ell\}\|\}\\frac\{2^\{\-\\ell\}\}\{\\alpha\}\\leq 5\\frac\{1\+\\alpha^\{2\}\}\{\\alpha\}\\sqrt\{d\}\\leq 10\\alpha\\sqrt\{d\}\.The confident\-stopping case is analogous, usingwt,aℓ≤n−1/2w\_\{t,a\}^\{\\ell\}\\leq n^\{\-1/2\}\. Therefore the confidence inequality becomes

\|r^t,aℓ−μt​\(a\)\|≤2​wt,aℓ\+Δℐ,Δℐ=C​εℐ​α​d\.\|\\hat\{r\}\_\{t,a\}^\{\\ell\}\-\\mu\_\{t\}\(a\)\|\\leq 2w\_\{t,a\}^\{\\ell\}\+\\Delta\_\{\\mathcal\{I\}\},\\qquad\\Delta\_\{\\mathcal\{I\}\}=C\\varepsilon\_\{\\mathcal\{I\}\}\\alpha\\sqrt\{d\}\.
It remains to justify the active\-set statement\. The argument follows the active\-set induction in Lemma 5 ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\), except that each use of the realizable confidence event is replaced by the perturbed confidence bound \([10](https://arxiv.org/html/2607.02891#S6.E10)\), adding anO​\(Δℐ\)O\(\\Delta\_\{\\mathcal\{I\}\}\)error per stage\. Suppose stageℓ\\ellperforms an elimination step, so all active arms havewt,aℓ≤2−ℓw\_\{t,a\}^\{\\ell\}\\leq 2^\{\-\\ell\}\. For any two active armsa,ba,b, the perturbed confidence bound implies

μt​\(b\)−μt​\(a\)\\displaystyle\\mu\_\{t\}\(b\)\-\\mu\_\{t\}\(a\)≤\\displaystyle\\leq\(r^t,bℓ\+wt,bℓ\)−\(r^t,aℓ\+wt,aℓ\)\+C​2−ℓ\+C​Δℐ\.\\displaystyle\\bigl\(\\hat\{r\}\_\{t,b\}^\{\\ell\}\+w\_\{t,b\}^\{\\ell\}\\bigr\)\-\\bigl\(\\hat\{r\}\_\{t,a\}^\{\\ell\}\+w\_\{t,a\}^\{\\ell\}\\bigr\)\+C2^\{\-\\ell\}\+C\\Delta\_\{\\mathcal\{I\}\}\.Thus, ifaasurvives the elimination test, then its true mean is below the best active benchmark by at mostC​2−ℓ\+C​ΔℐC2^\{\-\\ell\}\+C\\Delta\_\{\\mathcal\{I\}\}\. Inductively, take the optimal arm as the benchmark as long as it remains active\. If it is eliminated, replace it by the surviving arm whose empirical upper confidence value caused the elimination\. Each stage can increase the benchmark’s suboptimality by onlyO​\(Δℐ\)O\(\\Delta\_\{\\mathcal\{I\}\}\), so afterℓ\\ellstages every active arm satisfies \([11](https://arxiv.org/html/2607.02891#S6.E11)\)\. There are at mostS=⌈log2⁡n⌉S=\\lceil\\log\_\{2\}n\\rceilstages\. On a confident stopping round all active arms have width at mostn−1/2n^\{\-1/2\}, and comparing the selected arm with the same benchmark gives \([12](https://arxiv.org/html/2607.02891#S6.E12)\)\.

## 7Proof Sketch of Proposition[4\.5](https://arxiv.org/html/2607.02891#S4.Thmtheorem5)

The stationary termΩ​\(d​T\)\\Omega\(\\sqrt\{dT\}\)is theKK\-armed contextual linear\-bandit lower bound ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22)\)\. For the non\-stationary term, split the horizon into lower\-bound epochs of lengthHH\. In each epoch, instantiate an independent stationaryKK\-armed hard instance\. We assumePT\>0P\_\{T\}\>0\. WhenPT=0P\_\{T\}=0, the stationary term already gives the stated bound\.

For one construction, use a grouping argument in the spirit of the stationary lower bound ofChuet al\.\([2011](https://arxiv.org/html/2607.02891#bib.bib22), Section 6\)\. Letm:=min⁡\{K,d\}m:=\\min\\\{K,d\\\}\. The per\-epoch regret and the between\-epoch parameter displacement must be calibrated together: the gap size is chosen at the standard indistinguishability scale used in the stationary lower bound\. With this calibration, the construction gives per\-epoch regretΩ​\(d​H\)\\Omega\(\\sqrt\{dH\}\)and between\-epoch displacement of orderd/m​Hd/\\sqrt\{mH\}\. Thus the path\-length budget is respected whenever

TH​dm​H≤c​PT\\frac\{T\}\{H\}\\frac\{d\}\{\\sqrt\{mH\}\}\\leq cP\_\{T\}for a sufficiently small universal constantc\>0c\>0\. Choose

H=⌈C​\(d​Tm​PT\)2/3⌉H=\\left\\lceil C\\left\(\\frac\{dT\}\{\\sqrt\{m\}\\,P\_\{T\}\}\\right\)^\{2/3\}\\right\\rceilfor a sufficiently large universal constantC\>0C\>0\. Then the total regret over the epochs is at least

TH​d​H≥c′​\(d​m\)1/6​PT1/3​T2/3\\frac\{T\}\{H\}\\sqrt\{dH\}\\geq c^\{\\prime\}\(dm\)^\{1/6\}P\_\{T\}^\{1/3\}T^\{2/3\}for a universal constantc′\>0c^\{\\prime\}\>0\.

For the hypercube construction, letr:=min⁡\{d,⌊log2⁡K⌋\}r:=\\min\\\{d,\\lfloor\\log\_\{2\}K\\rfloor\\\}and use the finite action set\{v/r:v∈\{±1\}r\}\\\{v/\\sqrt\{r\}:v\\in\\\{\\pm 1\\\}^\{r\}\\\}embedded inℝd\\mathbb\{R\}^\{d\}\. By the standardΩ​\(r​H\)\\Omega\(r\\sqrt\{H\}\)lower bound forrr\-dimensional stochastic linear bandits with rich action sets\(Daniet al\.,[2008](https://arxiv.org/html/2607.02891#bib.bib23); Lattimore and Szepesvári,[2020](https://arxiv.org/html/2607.02891#bib.bib12)\), this hypercube instance has stationary epoch regretΩ​\(r​H\)\\Omega\(r\\sqrt\{H\}\)\. The path\-length budget is respected whenever

TH​rH≤c​PT\.\\frac\{T\}\{H\}\\frac\{r\}\{\\sqrt\{H\}\}\\leq cP\_\{T\}\.Choosing

H=⌈C​\(r​TPT\)2/3⌉H=\\left\\lceil C\\left\(\\frac\{rT\}\{P\_\{T\}\}\\right\)^\{2/3\}\\right\\rceiltherefore gives total regret at least

TH​r​H≥c′′​r2/3​PT1/3​T2/3\\frac\{T\}\{H\}r\\sqrt\{H\}\\geq c^\{\\prime\\prime\}r^\{2/3\}P\_\{T\}^\{1/3\}T^\{2/3\}for a universal constantc′′\>0c^\{\\prime\\prime\}\>0\. Taking the larger of the two constructions gives the claimed bound\.