Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

# Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions
Source: [https://arxiv.org/html/2608.26755](https://arxiv.org/html/2608.26755)
Aldo PacchianoAffiliation:Boston UniversityAffiliation:Broad Institute of MIT and Harvard

###### Abstract

Contextual bandits are a standard framework for sequential decision\-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems\. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences\. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost\. Most existing safety\-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold\. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes\. We study contextual bandits with one\-dimensional continuous actions and stage\-wise high\-probability constraints on the realized cost\. We propose High\-Probability Constrained UCB, an optimistic\-pessimistic algorithm that explores for reward while conservatively estimating the safe action set\. For linear reward and cost models, we prove a tight𝒪~​\(d​T\)\\tilde\{\{\\mathcal\{O\}\}\}\(d\\sqrt\{T\}\)regret bound, and we extend the analysis to general function classes using the eluder dimension\. Experiments show that enforcing realized\-cost safety substantially reduces violations compared with expected\-cost constrained baselines\.

## 1Introduction

Bandit algorithms\[thompson1933likelihood,auer2002using,lattimore2020bandit\]have been applied across a wide range of domains, including reinforcement learning with human feedback \(RLHF\)\[christiano2017deep,xie2024exploratory\], clinical trials\[matsuura2022optimal,lee2020contextual,aziz2021multi,villar2015multi,bastani2020online\], recommendation systems\[wang2022context\], dynamic pricing\[mueller2019low\], large language models\[bouneffouf2024tutorial\], and fair allocation\[procaccia2024honor\]; see\[bouneffouf2019survey\]for a broader overview\. In these domains, a learner interacts sequentially with an unknown environment, aiming to learn from observations while maximizing cumulative reward through its decisions\. Recently, there has been increasing interest in contextual bandits\[foster2023foundations,lattimore2020bandit\], where the learner observes a context before selecting an action from a potentially large or continuous action space\.

Within this general framework, constrained bandit algorithms are particularly relevant when applications involve resource limitations or safety requirements\[dai2023safe,wachi2020safe\]\. Such constraints can take different forms, including budget\-type constraints as in knapsack bandits\[badanidiyuru2018bandits\], fairness constraints\[joseph2016fairness\], and models with simultaneous reward and cost signals\[amani2019linear,pacchiano2021stochastic,pacchiano2024contextual\]\. The latter formulation is especially natural in applications such as advertising and drug administration, where decisions must balance utility against risk\. In drug dosage problems, for example, treatments generate an efficacy signal, interpreted as reward, and a toxicity signal, interpreted as cost; the goal is to maximize therapeutic benefit while ensuring that toxicity remains below a prescribed thresholdτ\\tau, as in Phase II clinical trials\. For example, related work by\[lee2020contextual\]considers a binary reward–cost model that enforces constraints on the average cost over time\.

While cumulative or averaged cost control is sufficient in some applications, many safety\-critical settings require stage\-wise constraints, namely control of the cost at each time step\. To address this requirement, researchers have studied the well\-established safe linear bandit problem\[hutchinson2024directional,pacchiano2024contextual,moradipari2019safe\], in which, at each roundtt, the selected action generates both a reward signalrt∈ℝr\_\{t\}\\in\\mathbb\{R\}and a cost signalct∈ℝc\_\{t\}\\in\\mathbb\{R\}\. The objective is to maximize expected cumulative reward while ensuring that the expected cost remains below a known safety thresholdτ\\tauat every round, with this constraint holding with high probability\.

Guarantees on the expected value of the cost signal are natural in homoscedastic models, where the level of noise is not affected by the chosen action\. However, in applications such as autonomous driving, robotic control, and drug treatment, the variability of the outcome may itself depend on the action level\. For example, a faster robotic motion may lead to a wider distribution of possible next positions due to friction or sensor noise, a larger velocity in autonomous driving may be less predictable than a smaller one, and the effect of a drug may vary across dosage levels\[kpeglo2021identification\]\. In such heteroscedastic settings, satisfying a constraint only in expectation does not preclude catastrophic outcomes at individual rounds\. This motivates algorithms that control the realized cost signal itself at each time step, rather than only its expectation\. With this motivation, we consider the following question\.

Is it possible to design constrained low\-regret algorithms that control realized cost at every round with high probability?

In this work, we address this question in a heteroscedastic reward–cost model with one\-dimensional continuous actions\[amani2019linear,pacchiano2024contextual,majzoubi2020efficient\]\. Our goal is to control the realized cost signalCtC\_\{t\}at each time step by requiring it to satisfy the constraintℙ⁡\(Ct≤τ\)≥1−δ\\mathbb\{P\}\(C\_\{t\}\\leq\\tau\)\\geq 1\-\\delta, whereδ\>0\\delta\>0is a user\-specified confidence parameter\. As in prior work, the resulting guarantee accounts for both the noise in the cost observations and the internal randomization of the algorithm\.

To achieve this objective, we propose aUCB\-likealgorithm termedHigh Probability Constrained UCB\. Our method is based on theOptimism in the Face of Uncertainty\(OFUL\) principle\[auer2002using,abbasi2011improved\]and does not require prior knowledge of an initial safe action, in contrast to several existing approaches\[pacchiano2024contextual\]\. The algorithm applies in both stochastic and adversarial contextual settings, under the standard assumption of sub\-Gaussian noise for both reward and cost signals\. Under this assumption, we construct a high\-probability constraint event that ensures the realized cost remains below the safety threshold at every round\.

We show that the proposed algorithm achieves aTT\-round regret bound of order𝒪~​\(d​T\)\\tilde\{\\mathcal\{O\}\}\(d\\sqrt\{T\}\), which is minimax optimal in its dependence on both the dimensionddand the time horizonTTfor linear bandits\[lattimore2020bandit\]\. In addition, we empirically validate the performance of our approach on both synthetic and real\-world datasets\. Finally, we extend our analysis to settings with non\-linear reward and cost functions, characterizing the regret in terms of the eluder dimension\[russo2013eluder\], a complexity measure for general function classes\.

The main contributions of this work are as follows:

- •We introduce a safety framework for reward–cost constrained bandits in a heteroscedastic setting with one\-dimensional continuous actions\.
- •We derive algorithms with tight regret guarantees for both linear and non\-linear reward and cost models\.
- •We validate our method on both synthetic and real\-world datasets, showing the importance of high\-probability realized\-cost guarantees in heteroscedastic settings\.

## 2Model and Problem Formulation

Notation\.We use the following notation throughout the paper\. For vectorsx,y∈ℝdx,y\\in\\mathbb\{R\}^\{d\}, we write⟨x,y⟩=x⊤​y\\langle x,y\\rangle=x^\{\\top\}yand⟨x,y⟩𝐀=x⊤​𝐀​y\\langle x,y\\rangle\_\{\\mathbf\{A\}\}=x^\{\\top\}\\mathbf\{A\}yfor the standard and weighted inner products, respectively, where𝐀∈ℝd×d\\mathbf\{A\}\\in\\mathbb\{R\}^\{d\\times d\}is positive definite\. Similarly, we define‖x‖2=⟨x,x⟩\\left\\lVert x\\right\\rVert\_\{2\}=\\sqrt\{\\langle x,x\\rangle\}and‖x‖𝐀=⟨x,x⟩𝐀\\left\\lVert x\\right\\rVert\_\{\\mathbf\{A\}\}=\\sqrt\{\\langle x,x\\rangle\_\{\\mathbf\{A\}\}\}as theℓ2\\ell\_\{2\}and weightedℓ2\\ell\_\{2\}norms ofxx\. We denote the indicator function by𝟏​\{⋅\}\\mathbf\{1\}\\\{\\cdot\\\}\. Upper\-case letters denote random variables, e\.g\.,XX, and lower\-case letters denote their realizations, e\.g\.,X=xX=x\. We write\[T\]=\{1,…,T\}\[T\]=\\\{1,\\ldots,T\\\}\. Finally,𝒪~\\widetilde\{\\mathcal\{O\}\}denotes big\-𝒪\\mathcal\{O\}notation up to logarithmic factors\.

Inspired by bandit algorithms for adaptive dosage allocation\[matsuura2022optimal,lee2020contextual,aziz2021multi\], we consider the following formulation of actions, rewards, and costs\. At each roundt∈\[T\]t\\in\[T\], the learner observes add\-dimensional context vectorXt∈ℝdX\_\{t\}\\in\\mathbb\{R\}^\{d\}, which may represent structured measurements, such as medical test results, or an embedding of unstructured information, such as text descriptions generated by a language model\[baheri2023llms\]\. We impose no distributional assumptions onXtX\_\{t\}; the contexts may be generated either stochastically or adversarially\. The learner then selects a one\-dimensional continuous actionαt∈\[0,1\]\\alpha\_\{t\}\\in\[0,1\]\[majzoubi2020efficient\], which can be viewed as a continuous generalization of a finite set of dosage levels\. The environment generates reward and cost signals according to

Rt\\displaystyle R\_\{t\}:=g⁡\(αt\)⋅\(r⁡\(Xt\)\+ξtr\),\\displaystyle:=g\(\\alpha\_\{t\}\)\\cdot\\left\(r\(X\_\{t\}\)\+\\xi\_\{t\}^\{r\}\\right\),\(1\)Ct\\displaystyle C\_\{t\}:=g⁡\(αt\)⋅\(c⁡\(Xt\)\+ξtc\),\\displaystyle:=g\(\\alpha\_\{t\}\)\\cdot\\left\(c\(X\_\{t\}\)\+\\xi\_\{t\}^\{c\}\\right\),\(2\)whereξtr\\xi\_\{t\}^\{r\}andξtc\\xi\_\{t\}^\{c\}are sub\-Gaussian noise terms, andr⁡\(Xt\)r\(X\_\{t\}\)andc⁡\(Xt\)c\(X\_\{t\}\)denote the underlying reward and cost functions\. The functiong:\[0,1\]→\[0,1\]g:\[0,1\]\\to\[0,1\]is known and strictly increasing, withg⁡\(0\)=0g\(0\)=0andg⁡\(1\)=1g\(1\)=1\. In dosage applications,ggcan be interpreted as a covariate\-independent dose\-response curve, such as a population\-level efficacy or toxicity profile that can be estimated from prior studies\.111A natural extension is to allow distinct dosage\-response functions for the reward and cost, denoted bygr​\(⋅\)g\_\{r\}\(\\cdot\)andgc​\(⋅\)g\_\{c\}\(\\cdot\), respectively\. While this extension is practically relevant, it introduces no additional theoretical difficulty, so we use a common functiong⁡\(⋅\)g\(\\cdot\)to simplify the notation\.The normalizationg⁡\(1\)=1g\(1\)=1is without loss of generality, since any constant scale can be absorbed into the reward and cost functions\. This formulation allows for nearly flat regions that model saturation or diminishing returns, while preserving invertibility\. In dosage\-like applications, efficacy and toxicity are commonly assumed to increase with the dosage level; see\[aziz2021multi,lee2020contextual,le2009dose\]and references therein\. In the linear setting, we assumer⁡\(Xt\)=⟨Xt,θ∗⟩r\(X\_\{t\}\)=\\langle X\_\{t\},\\theta^\{\*\}\\rangleandc⁡\(Xt\)=⟨Xt,μ∗⟩c\(X\_\{t\}\)=\\langle X\_\{t\},\\mu^\{\*\}\\ranglefor unknown parametersθ∗,μ∗∈ℝd\\theta^\{\*\},\\mu^\{\*\}\\in\\mathbb\{R\}^\{d\}\. In more general settings, we require only thatr⁡\(Xt\)r\(X\_\{t\}\)andc⁡\(Xt\)c\(X\_\{t\}\)are bounded\. The interaction protocol is summarized in[Figure1](https://arxiv.org/html/2608.26755#S2.F1)\.

To illustrate the linear case, consider a medical treatment scenario in which the contextXt∈ℝdX\_\{t\}\\in\\mathbb\{R\}^\{d\}represents a patient feature vector encoding medical attributes such as blood pressure, oxygen saturation, or laboratory test results\. In this model, there exist unknown parametersθ⋆,μ⋆∈ℝd\\theta^\{\\star\},\\mu^\{\\star\}\\in\\mathbb\{R\}^\{d\}such that

Rt\\displaystyle R\_\{t\}=g⁡\(αt\)⋅\(⟨Xt,θ⋆⟩\+ξtr\),\\displaystyle=g\(\\alpha\_\{t\}\)\\cdot\\left\(\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\+\\xi\_\{t\}^\{r\}\\right\),Ct\\displaystyle C\_\{t\}=g⁡\(αt\)⋅\(⟨Xt,μ⋆⟩\+ξtc\)\.\\displaystyle=g\(\\alpha\_\{t\}\)\\cdot\\left\(\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\+\\xi\_\{t\}^\{c\}\\right\)\.The vectorθ⋆\\theta^\{\\star\}characterizes how patient\-specific features influence treatment efficacy: a positive inner product⟨Xt,θ⋆⟩\\langle X\_\{t\},\\theta^\{\\star\}\\rangleindicates high expected benefit from treatment\. Similarly, the vectorμ⋆\\mu^\{\\star\}captures how the same features relate to adverse effects or toxicity, with larger values of⟨Xt,μ⋆⟩\\langle X\_\{t\},\\mu^\{\\star\}\\rangleindicating increased risk of side effects\. The noise termsξtr\\xi\_\{t\}^\{r\}andξtc\\xi\_\{t\}^\{c\}represent stochastic variability not captured by the linear model, such as unobserved physiological factors or measurement errors\.

The actionαt∈\[0,1\]\\alpha\_\{t\}\\in\[0,1\]represents the administered dosage level\. Through the known response functiongg, the dosage scales both the reward and cost signals, allowing the learner to trade off efficacy against toxicity\. For instance, a patient with elevated inflammatory markers, corresponding to a high value of⟨Xt,θ⋆⟩\\langle X\_\{t\},\\theta^\{\\star\}\\rangle, may benefit substantially from treatment\. However, if the same patient exhibits impaired kidney function, corresponding to a high value of⟨Xt,μ⋆⟩\\langle X\_\{t\},\\mu^\{\\star\}\\rangle, a reduced dosage may be preferable to mitigate adverse outcomes\. This formulation is consistent with standard monotonicity assumptions on efficacy–toxicity dose\-response curves\[wages2011dose,le2009dose\], whereby increasing the dose tends to increase both therapeutic and toxic effects\.

The same action\-dependent scaling also makes the model heteroscedastic\. Indeed, the variability of the observed reward and cost depends on the selected dosage throughg⁡\(αt\)g\(\\alpha\_\{t\}\)\. This captures the fact that aggressive treatments may lead to less predictable responses\[rawlins1974variability\]\. In this sense, the model allows for stochastic departures from deterministic monotonicity, such as saturation or instability in biological responses\.

As a result, the learner must select actionsαt\\alpha\_\{t\}not only to maximize expected cumulative reward, but also to control the variability induced by the treatment\. Our model belongs to the broader class of heteroscedastic bandits\[xu2023noise,mukherjee2024speed,weltz2023experimental,hsieh2019stay\], in which the noise distribution may depend on both the current context and the chosen action\. In more general formulations, the noise variance or sub\-Gaussian parameter may scale as a quadratic formϕ​\(Xt,At\)⊤​Σ⋆​ϕ​\(Xt,At\)\\phi\(X\_\{t\},A\_\{t\}\)^\{\\top\}\\Sigma^\{\\star\}\\phi\(X\_\{t\},A\_\{t\}\), whereϕ⁡\(⋅,⋅\):𝒳×𝒜→ℝd\\phi\(\\cdot,\\cdot\):\{\\mathcal\{X\}\}\\times\{\\mathcal\{A\}\}\\to\\mathbb\{R\}^\{d\}denotes a joint context–action embedding andΣ⋆\\Sigma^\{\\star\}is an unknown positive definite matrix\. While our model adopts a simpler structure, it captures monotone dose\-response behavior commonly observed in reward–cost systems and remains interpretable, a property that is particularly valuable in medical decision\-making contexts\.

Figure 1:Safe Bandit protocol\.### 2\.1Assumptions

Before presenting our analysis and results, we state the assumptions used throughout the paper\. These assumptions are standard in the literature on constrained contextual bandits; see\[hutchinson2024directional,pacchiano2024contextual,moradipari2019safe\]and references therein\.

###### Assumption 2\.1\(Sub\-Gaussian noise\)\.

For allt∈\[T\]t\\in\[T\], the reward and cost noise random variablesξtr\\xi\_\{t\}^\{r\}andξtc\\xi\_\{t\}^\{c\}are conditionally sub\-Gaussian\. That is, for allλ∈ℝ\\lambda\\in\\mathbb\{R\}, there exist constantsκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1),κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\>0\\kappa\_\{\\ref\{Cr\}\},\\kappa\_\{\\ref\{Cc\}\}\>0such that

𝔼⁡\[ξtr∣ℋt−1\]=0,𝔼⁡\[exp⁡\(λ​ξtr\)∣ℋt−1\]≤exp⁡\(λ2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2/2\),\\displaystyle\\mathbb\{E\}\[\\xi\_\{t\}^\{r\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=0,\\qquad\\mathbb\{E\}\[\\exp\(\\lambda\\xi\_\{t\}^\{r\}\)\\mid\\mathcal\{H\}\_\{t\-1\}\]\\leq\\exp\(\\lambda^\{2\}\\kappa\_\{\\ref\{Cr\}\}^\{2\}/2\),𝔼⁡\[ξtc∣ℋt−1\]=0,𝔼⁡\[exp⁡\(λ​ξtc\)∣ℋt−1\]≤exp⁡\(λ2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2/2\),\\displaystyle\\mathbb\{E\}\[\\xi\_\{t\}^\{c\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=0,\\qquad\\mathbb\{E\}\[\\exp\(\\lambda\\xi\_\{t\}^\{c\}\)\\mid\\mathcal\{H\}\_\{t\-1\}\]\\leq\\exp\(\\lambda^\{2\}\\kappa\_\{\\ref\{Cc\}\}^\{2\}/2\),whereℋt:=σ⁡\(X1,α1,R1,C1,…,Xt,αt,Rt,Ct\)\.\\mathcal\{H\}\_\{t\}:=\\sigma\\\!\\left\(X\_\{1\},\\alpha\_\{1\},R\_\{1\},C\_\{1\},\\ldots,X\_\{t\},\\alpha\_\{t\},R\_\{t\},C\_\{t\}\\right\)\.is the filtration containing the history up to the end of roundtt\.

###### Assumption 2\.2\(Bounded parameters\)\.

There exists a known constantκ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)\>0\\kappa\_\{\\ref\{S\}\}\>0such that‖θ⋆‖2≤κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)\\\|\\theta^\{\\star\}\\\|\_\{2\}\\leq\\kappa\_\{\\ref\{S\}\}and‖μ⋆‖2≤κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)\\\|\\mu^\{\\star\}\\\|\_\{2\}\\leq\\kappa\_\{\\ref\{S\}\}\.

###### Assumption 2\.3\(Bounded contexts\)\.

Theℓ2\\ell\_\{2\}\-norms of all contexts are bounded by a known constantκ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\>0\\kappa\_\{\\ref\{L\}\}\>0, i\.e\.,

maxt∈\[T\]⁡‖Xt‖2≤κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\.\\max\_\{t\\in\[T\]\}\\;\\\|X\_\{t\}\\\|\_\{2\}\\leq\\kappa\_\{\\ref\{L\}\}\.

###### Assumption 2\.4\(Positive toxicity threshold\)\.

The toxicity threshold satisfiesτ\>0\\tau\>0\.

### 2\.2Constraint Formulation

The learner’s goal is to maximize expected cumulative reward overTTrounds,

𝔼⁡\[∑t=1Tg⁡\(αt\)​⟨Xt,θ⋆⟩\],\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}g\(\\alpha\_\{t\}\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\right\],while ensuring that the realized cost remains below a known safety threshold with high probability\. Our algorithm takes as input a confidence levelδ\\delta, which controls the probability of violating the constraint due to stochastic fluctuations in the cost signal\. Thus, unlike formulations that constrain only the expected cost, our safety requirement depends explicitly on the tail behavior of the realized cost\.

If the noise distribution were fully known, for instance Gaussian with known variance, one could potentially enforce the constraint directly using the corresponding quantiles\. In our setting, however, the noise distribution is unknown and we assume only a sub\-Gaussian upper bound\. We therefore rely on distribution\-free high\-probability bounds and formulate the following sufficient condition\.

###### Lemma 1\.

If the selected actionαt\\alpha\_\{t\}satisfies

g⁡\(αt\)​\(⟨Xt,μ⋆⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\)≤τ,g\(\\alpha\_\{t\}\)\\left\(\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\tfrac\{1\}\{\\delta\}\\right\)\}\\right\)\\leq\\tau,thenℙ⁡\(Ct≤τ∣ℋt\)≥1−δ\\mathbb\{P\}\(C\_\{t\}\\leq\\tau\\mid\\mathcal\{H\}\_\{t\}\)\\geq 1\-\\delta\.

The proof is provided in[SectionA\.1](https://arxiv.org/html/2608.26755#A1.SS1)and follows directly from a concentration inequality for sub\-Gaussian random variables; see\[lattimore2020bandit\], Chapter 5, or\[vershynin2018high\], Chapter 2\.

The key difference from standard expected\-cost formulations is conceptual rather than merely algebraic: the constraint is imposed on the realized cost, and the confidence parameterδ\\deltaspecifies the tolerated probability of an unsafe realization\. In our action\-scaled heteroscedastic model, the selected action controls both the mean cost and the magnitude of the cost fluctuations, making this realized\-cost requirement a meaningful decision constraint\.

Accordingly, we define the feasible action set at roundttas

𝒜tf​\(δ\):=\{α∈\[0,1\]:g⁡\(α\)​\(⟨Xt,μ⋆⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\)≤τ\}\.\\mathcal\{A\}^\{f\}\_\{t\}\(\\delta\):=\\left\\\{\\alpha\\in\[0,1\]:g\(\\alpha\)\\left\(\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\tfrac\{1\}\{\\delta\}\\right\)\}\\right\)\\leq\\tau\\right\\\}\.\(3\)Any actionαt∈𝒜tf​\(δ\)\\alpha\_\{t\}\\in\\mathcal\{A\}^\{f\}\_\{t\}\(\\delta\)ensures thatℙ⁡\(Ct≤τ∣ℋt\)≥1−δ\\mathbb\{P\}\(C\_\{t\}\\leq\\tau\\mid\\mathcal\{H\}\_\{t\}\)\\geq 1\-\\delta\.

Given the feasible action set, let

αt⋆∈arg⁡maxα∈𝒜tf​\(δ\)⁡g⁡\(α\)​r​\(Xt\)\\alpha\_\{t\}^\{\\star\}\\in\\arg\\max\_\{\\alpha\\in\\mathcal\{A\}^\{f\}\_\{t\}\(\\delta\)\}g\(\\alpha\)r\(X\_\{t\}\)denote an optimal feasible action at roundtt\.222In prior work on contextual bandits with stage\-wise safety constraints\[pacchiano2024contextual,amani2019linear\], the learner’s performance is typically measured relative to the optimal safe action\. This choice of comparator reflects the requirement that the safety constraint be satisfied at every round with high probability; accordingly, the resulting regret guarantees are also stated with high probability\.We measure the learner’s performance through theTT\-round constrained pseudo\-regret

ℛ𝒞​\(T\):=∑t=1T\[g⁡\(αt⋆\)​r​\(Xt\)−g⁡\(αt\)​r​\(Xt\)\]\.\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\):=\\sum\_\{t=1\}^\{T\}\\left\[g\(\\alpha\_\{t\}^\{\\star\}\)r\(X\_\{t\}\)\-g\(\\alpha\_\{t\}\)r\(X\_\{t\}\)\\right\]\.\(4\)
Our algorithm guarantees that the selected action belongs to an estimated subset of𝒜tf​\(δ\)\\mathcal\{A\}^\{f\}\_\{t\}\(\\delta\)with probability at least1−δ′1\-\\delta^\{\\prime\}, whereδ′\\delta^\{\\prime\}is the confidence level associated with estimatingμ⋆\\mu^\{\\star\}\. We keepδ\\deltaandδ′\\delta^\{\\prime\}separate to distinguish two sources of uncertainty: the randomness of the realized cost, governed by the noiseξtc\\xi\_\{t\}^\{c\}, and the statistical uncertainty in the estimate ofμ⋆\\mu^\{\\star\}, governed by the observed historyℋt\\mathcal\{H\}\_\{t\}\. One may combine these events by a union bound, but we state them separately to make the two roles explicit\.

We now address safety in the initial round, where no observations are available to estimateθ⋆\\theta^\{\\star\}orμ⋆\\mu^\{\\star\}\. In contrast to prior work\[pacchiano2024contextual,moradipari2019safe\], our model does not require prior knowledge of an initially safe action\. Becauseτ\>0\\tau\>0andg⁡\(0\)=0g\(0\)=0, the zero action is always safe\. Moreover, using the boundedness assumptions onμ⋆\\mu^\{\\star\}andXtX\_\{t\}, we can characterize a nontrivial initial safe interval\. Specifically, since⟨X1,μ⋆⟩≤κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\\langle X\_\{1\},\\mu^\{\\star\}\\rangle\\leq\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}by Cauchy–Schwarz, any action satisfying

g⁡\(α1\)≤τκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\.g\(\\alpha\_\{1\}\)\\leq\\frac\{\\tau\}\{\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\tfrac\{1\}\{\\delta\}\\right\)\}\+\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\.\(5\)is safe\. Equivalently, sinceggis strictly increasing, an initial safe interval is given by

𝒜1f​\(δ\)=\[0,g−1​\(min⁡\{g⁡\(1\),τκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\}\)\]\.\\mathcal\{A\}^\{f\}\_\{1\}\(\\delta\)=\\left\[0,g^\{\-1\}\\left\(\\min\\left\\\{g\(1\),\\frac\{\\tau\}\{\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\tfrac\{1\}\{\\delta\}\\right\)\}\+\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\\right\\\}\\right\)\\right\]\.

## 3Proposed Algorithm

Our algorithm follows the principle of optimism in the face of uncertainty for the reward signal, while using pessimistic estimates for the cost signal\. This asymmetric treatment encourages exploration for reward maximization while maintaining conservative estimates of the safe action set\.

At each round, we construct two regularized least\-squares estimators, one forθ⋆\\theta^\{\\star\}and one forμ⋆\\mu^\{\\star\}\. For a regularization parameterλ\>0\\lambda\>0, define the regularized covariance matrix at roundttas

Σt=λ​I\+∑s<tg⁡\(αs\)\>0Xs​Xs⊤\.\\Sigma\_\{t\}=\\lambda I\+\\sum\_\{\\begin\{subarray\}\{c\}s<t\\\\ g\(\\alpha\_\{s\}\)\>0\\end\{subarray\}\}X\_\{s\}X\_\{s\}^\{\\top\}\.\(6\)Our theoretical analysis holds for any fixed constantλ\>0\\lambda\>0; in our experiments, we setλ=1\\lambda=1\. Using[Equation6](https://arxiv.org/html/2608.26755#S3.E6), we define

θ^t=Σt−1​∑s<tg⁡\(αs\)\>0Rsg⁡\(αs\)​Xs,μ^t=Σt−1​∑s<tg⁡\(αs\)\>0Csg⁡\(αs\)​Xs\.\\hat\{\\theta\}\_\{t\}=\\Sigma\_\{t\}^\{\-1\}\\sum\_\{\\begin\{subarray\}\{c\}s<t\\\\ g\(\\alpha\_\{s\}\)\>0\\end\{subarray\}\}\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}X\_\{s\},\\qquad\\hat\{\\mu\}\_\{t\}=\\Sigma\_\{t\}^\{\-1\}\\sum\_\{\\begin\{subarray\}\{c\}s<t\\\\ g\(\\alpha\_\{s\}\)\>0\\end\{subarray\}\}\\frac\{C\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}X\_\{s\}\.\(7\)Since

Rsg⁡\(αs\)=⟨Xs,θ⋆⟩\+ξsr,Csg⁡\(αs\)=⟨Xs,μ⋆⟩\+ξsc,\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\langle X\_\{s\},\\theta^\{\\star\}\\rangle\+\\xi\_\{s\}^\{r\},\\qquad\\frac\{C\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\langle X\_\{s\},\\mu^\{\\star\}\\rangle\+\\xi\_\{s\}^\{c\},the transformed observations follow the standard linear regression model wheneverg⁡\(αs\)\>0g\(\\alpha\_\{s\}\)\>0\. Rounds withg⁡\(αs\)=0g\(\\alpha\_\{s\}\)=0provide no information about the unknown parameters and are therefore excluded\.

To construct a UCB\-style algorithm, we define high\-probability confidence sets centered atθ^t\\hat\{\\theta\}\_\{t\}andμ^t\\hat\{\\mu\}\_\{t\}\. These sets bound the estimation error with respect to the true parametersθ⋆\\theta^\{\\star\}andμ⋆\\mu^\{\\star\}and follow from standard self\-normalized concentration inequalities\. Let

N⁡\(t\)=\|\{1≤s<t:g⁡\(αs\)\>0\}\|N\(t\)=\\left\|\\\{1\\leq s<t:g\(\\alpha\_\{s\}\)\>0\\\}\\right\|denote the number of informative samples collected before roundtt\.

###### Theorem 1\(Theorem 2 inabbasi2011improved\)\.

For fixedδ′∈\(0,1\)\\delta^\{\\prime\}\\in\(0,1\), define

βtr​\(δ′,d\)\\displaystyle\\beta\_\{t\}^\{r\}\(\\delta^\{\\prime\},d\)=κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​d​log⁡\(1\+N⁡\(t\)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)2/λδ′\)\+λ​κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1),\\displaystyle=\\kappa\_\{\\ref\{Cr\}\}\\sqrt\{d\\log\\left\(\\frac\{1\+N\(t\)\\kappa\_\{\\ref\{L\}\}^\{2\}/\\lambda\}\{\\delta^\{\\prime\}\}\\right\)\}\+\\sqrt\{\\lambda\}\\kappa\_\{\\ref\{S\}\},βtc​\(δ′,d\)\\displaystyle\\beta\_\{t\}^\{c\}\(\\delta^\{\\prime\},d\)=κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​d​log⁡\(1\+N⁡\(t\)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)2/λδ′\)\+λ​κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)\.\\displaystyle=\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{d\\log\\left\(\\frac\{1\+N\(t\)\\kappa\_\{\\ref\{L\}\}^\{2\}/\\lambda\}\{\\delta^\{\\prime\}\}\\right\)\}\+\\sqrt\{\\lambda\}\\kappa\_\{\\ref\{S\}\}\.Then, with probability at least1−δ′1\-\\delta^\{\\prime\},

‖θ^t−θ⋆‖Σt≤βtr​\(δ′,d\),‖μ^t−μ⋆‖Σt≤βtc​\(δ′,d\)\.\\\|\\hat\{\\theta\}\_\{t\}\-\\theta^\{\\star\}\\\|\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{r\}\(\\delta^\{\\prime\},d\),\\qquad\\\|\\hat\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\\|\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{c\}\(\\delta^\{\\prime\},d\)\.

We use[Theorem1](https://arxiv.org/html/2608.26755#Thmthm1)to define the confidence ellipsoids

𝒞tr​\(δ′\)=\{θ∈ℝd:‖θ−θ^t‖Σt≤βtr​\(δ′,d\)\},𝒞tc​\(δ′\)=\{μ∈ℝd:‖μ−μ^t‖Σt≤βtc​\(δ′,d\)\}\.\\begin\{split\}\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)&=\\left\\\{\\theta\\in\\mathbb\{R\}^\{d\}:\\\|\\theta\-\\hat\{\\theta\}\_\{t\}\\\|\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{r\}\(\\delta^\{\\prime\},d\)\\right\\\},\\\\ \\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)&=\\left\\\{\\mu\\in\\mathbb\{R\}^\{d\}:\\\|\\mu\-\\hat\{\\mu\}\_\{t\}\\\|\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{c\}\(\\delta^\{\\prime\},d\)\\right\\\}\.\\end\{split\}\(8\)When clear from context, we omit the dependence ofβtr\\beta\_\{t\}^\{r\}andβtc\\beta\_\{t\}^\{c\}onδ′\\delta^\{\\prime\}anddd\. By a union bound, the eventsθ⋆∈𝒞tr\\theta^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{r\}andμ⋆∈𝒞tc\\mu^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{c\}hold with probability at least1−2​δ′1\-2\\delta^\{\\prime\}\.

We choose an optimistic estimate of the reward parameter by solving

θ~t∈arg⁡maxθ∈𝒞tr​⟨Xt,θ⟩\.\\tilde\{\\theta\}\_\{t\}\\in\\arg\\max\_\{\\theta\\in\\mathcal\{C\}\_\{t\}^\{r\}\}\\langle X\_\{t\},\\theta\\rangle\.\(9\)This is a linear optimization problem over an ellipsoid and admits a closed\-form solution from the KKT conditions\[boyd2004convex\]; see[AppendixC](https://arxiv.org/html/2608.26755#A3)for details\.

For the cost parameter, we take the opposite approach\. We select a pessimistic estimateμ~t\\tilde\{\\mu\}\_\{t\}that yields a conservative estimate of the feasible action set\. Since the feasible set is an interval in\[0,1\]\[0,1\], this amounts to choosing the parameter in the confidence set that makes the upper endpoint of the safe interval as small as possible\. This optimistic–pessimistic principle underlies[Algorithm1](https://arxiv.org/html/2608.26755#alg1)\.

We have stated the algorithm using the sub\-Gaussian parametersκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cr\}\}andκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cc\}\}\. If these parameters are unknown, they can be replaced by valid upper confidence estimates or upper bounds using standard techniques\. In particular, the confidence intervals of\[jun2024noise\]can be incorporated without changing the structure of the algorithm\. Moreover, when reward and cost observations are almost surely bounded, a sub\-Gaussian upper bound follows directly from standard concentration results\[vershynin2018high\]\.

Algorithm 1High Probability Constrained UCB1:Constraint threshold

τ\>0\\tau\>0, safety parameter

δ\\delta, confidence parameter

δ′\\delta^\{\\prime\}, sub\-Gaussianity constants

κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1),κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cr\}\},\\kappa\_\{\\ref\{Cc\}\}
2:

α1←g−1​\(min⁡\{1,τκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1/δ\)\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\}\)\\alpha\_\{1\}\\leftarrow g^\{\-1\}\\\!\\left\(\\min\\left\\\{1,\\frac\{\\tau\}\{\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\(1/\\delta\)\}\+\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\\right\\\}\\right\)
3:Select action

α1\\alpha\_\{1\}and store

\(X1,R1,C1\)\(X\_\{1\},R\_\{1\},C\_\{1\}\)
4:for

t=2,3,…,Tt=2,3,\\ldots,Tdo

5:Compute

θ^t,μ^t\\hat\{\\theta\}\_\{t\},\\hat\{\\mu\}\_\{t\}according to \([7](https://arxiv.org/html/2608.26755#S3.E7)\)\.

6:Use

μ^t\\hat\{\\mu\}\_\{t\}to solve \([10](https://arxiv.org/html/2608.26755#S3.E10)\) and compute

𝒜^tf\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}using \([12](https://arxiv.org/html/2608.26755#S3.E12)\)\.

7:Use

θ^t\\hat\{\\theta\}\_\{t\}to solve \([9](https://arxiv.org/html/2608.26755#S3.E9)\) and compute

θ~t\\tilde\{\\theta\}\_\{t\}\.

8:Compute

αt∈arg⁡maxα∈𝒜^tf⁡g⁡\(α\)​⟨Xt,θ~t⟩\.\\alpha\_\{t\}\\in\\arg\\max\_\{\\alpha\\in\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}\}g\(\\alpha\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle\.
9:Select action

αt\\alpha\_\{t\}\.

10:if

g⁡\(αt\)\>0g\(\\alpha\_\{t\}\)\>0then

11:Store

\(Xt,Rt,Ct\)\(X\_\{t\},R\_\{t\},C\_\{t\}\)\.

12:endif

13:endfor

### 3\.1Construction of the Estimated Feasible Set

The estimated feasible set𝒜^tf\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}is constructed from a pessimistic estimate of the cost parameter\. First, we compute the least\-squares estimatorμ^t\\hat\{\\mu\}\_\{t\}, which defines a confidence ellipsoid that containsμ⋆\\mu^\{\\star\}with high probability\. Among all parameters in this ellipsoid, we choose the one that makes the safe action set most conservative\.

More precisely, we construct a surrogate feasible set𝒜^tf\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}such that

ℙ⁡\(𝒜^tf⊆𝒜tf\)≥1−δ′\\mathbb\{P\}\\\!\\left\(\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}\\subseteq\\mathcal\{A\}^\{f\}\_\{t\}\\right\)\\geq 1\-\\delta^\{\\prime\}for alltt\. We computeμ^t\\hat\{\\mu\}\_\{t\}according to \([7](https://arxiv.org/html/2608.26755#S3.E7)\) and solve the following optimization problem:

max𝜇\\displaystyle\\underset\{\\mu\}\{\\max\}⟨Xt,μ⟩\\displaystyle\\langle X\_\{t\},\\mu\\rangle\(10\)subject to\\displaystyle\\text\{subject to\}‖μ−μ^t‖Σt≤βtc,\\displaystyle\\\|\\mu\-\\hat\{\\mu\}\_\{t\}\\\|\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{c\},⟨Xt,μ⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)≥0\.\\displaystyle\\langle X\_\{t\},\\mu\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\\geq 0\.The last constraint ensures that the denominator defining the safe upper endpoint is nonnegative\. Let

𝒦\(μ^t\)t=\{μ∈ℝd:∥μ−μ^t∥Σt≤βtc,⟨Xt,μ⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2​log⁡\(1δ\)≥0\}\.\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}=\\left\\\{\\mu\\in\\mathbb\{R\}^\{d\}:\\\|\\mu\-\\hat\{\\mu\}\_\{t\}\\\|\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{c\},\\;\\langle X\_\{t\},\\mu\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\\geq 0\\right\\\}\.\(11\)If𝒦​\(μ^t\)t≠∅\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}\\neq\\emptyset, let

μ~t∈arg⁡maxμ∈𝒦​\(μ^t\)t​⟨Xt,μ⟩\.\\tilde\{\\mu\}\_\{t\}\\in\\arg\\max\_\{\\mu\\in\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}\}\\langle X\_\{t\},\\mu\\rangle\.We then define the estimated feasible set as

𝒜^tf​\(δ\)=\{\[0,1\],if​𝒦​\(μ^t\)t=∅,\[0,g−1​\(min⁡\{1,τ⟨Xt,μ~t⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\}\)\],if​𝒦​\(μ^t\)t≠∅\.\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}\(\\delta\)=\\begin\{cases\}\[0,1\],&\\text\{if \}\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}=\\emptyset,\\\\\[5\.0pt\] \\left\[0,g^\{\-1\}\\\!\\left\(\\min\\left\\\{1,\\dfrac\{\\tau\}\{\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\}\\right\\\}\\right\)\\right\],&\\text\{if \}\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}\\neq\\emptyset\.\\end\{cases\}\(12\)
Combining[Theorem1](https://arxiv.org/html/2608.26755#Thmthm1)with the pessimistic construction above yields the following guarantee; its proof is provided in the supplementary material\.

###### Lemma 2\.

For allt∈\[T\]t\\in\[T\],

ℙ⁡\(𝒜^tf​\(δ\)⊆𝒜tf​\(δ\)∣ℋt\)≥1−δ′\.\\mathbb\{P\}\\left\(\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}\(\\delta\)\\subseteq\\mathcal\{A\}^\{f\}\_\{t\}\(\\delta\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\geq 1\-\\delta^\{\\prime\}\.

## 4The “Good Event”

A common analysis technique in multi\-armed bandit algorithms is to condition on a high\-probability “good event\.” We define this event as the conjunction of the concentration and feasibility guarantees required by our algorithm\. Specifically, letε\\varepsilondenote the intersection of the following sub\-events:

- •εθ=\{θ⋆∈𝒞tr,∀t∈\[T\]\}\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\theta\}=\\\{\\theta^\{\\star\}\\in\{\\mathcal\{C\}\}^\{r\}\_\{t\},\\ \\forall t\\in\[T\]\\\}\.
- •εμ=\{μ⋆∈𝒞tc,∀t∈\[T\]\}\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mu\}=\\\{\\mu^\{\\star\}\\in\{\\mathcal\{C\}\}^\{c\}\_\{t\},\\ \\forall t\\in\[T\]\\\}\.
- •εA=\{𝒜^tf\(δ\)⊆𝒜tf\(δ\),∀t∈\[T\]\}\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{A\}=\\\{\\hat\{\\mathcal\{A\}\}^\{f\}\_\{t\}\(\\delta\)\\subseteq\\mathcal\{A\}^\{f\}\_\{t\}\(\\delta\),\\ \\forall t\\in\[T\]\\\}\.

The first two events ensure that the confidence sets forθ⋆\\theta^\{\\star\}andμ⋆\\mu^\{\\star\}contain the true parameters, as established in[Theorem1](https://arxiv.org/html/2608.26755#Thmthm1)\. The third event ensures that the estimated feasible action set is contained in the true feasible action set at every round\.

###### Lemma 3\.

Letε=εθ∩εμ∩εA\\scalebox\{1\.5\}\{$\\varepsilon$\}=\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\theta\}\\cap\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mu\}\\cap\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{A\}\. Then,

ℙ⁡\(ε\)≥1−3​δ′\.\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\)\\geq 1\-3\\delta^\{\\prime\}\.

## 5Regret Analysis – Linear Case

We remind the definition of theTT\-round constrained pseudo\-regret as defined in[Equation4](https://arxiv.org/html/2608.26755#S2.E4)\. In the linear setting, the expected reward obtained by actionαt\\alpha\_\{t\}isg⁡\(αt\)​⟨Xt,θ⋆⟩g\(\\alpha\_\{t\}\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\. We therefore define

ℛ𝒞​\(T\)=∑t=1T\(r∗​\(Xt\)−rt\),\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=\\sum\_\{t=1\}^\{T\}\\left\(r^\{\*\}\(X\_\{t\}\)\-r\_\{t\}\\right\),\(13\)where

r∗​\(Xt\)=maxα∈𝒜tf⁡g⁡\(α\)​⟨Xt,θ⋆⟩r^\{\*\}\(X\_\{t\}\)=\\max\_\{\\alpha\\in\\mathcal\{A\}^\{f\}\_\{t\}\}g\(\\alpha\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangledenotes the optimal feasible reward at roundtt, and

rt=g⁡\(αt\)​⟨Xt,θ⋆⟩r\_\{t\}=g\(\\alpha\_\{t\}\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangleis the expected reward obtained by the algorithm\.

Sinceggis strictly increasing, the optimal feasible action depends on the sign of⟨Xt,θ⋆⟩\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\. If⟨Xt,θ⋆⟩≥0\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\geq 0, the optimal action is the largest feasible action\. If⟨Xt,θ⋆⟩<0\\langle X\_\{t\},\\theta^\{\\star\}\\rangle<0, the optimal action isαt=0\\alpha\_\{t\}=0\. Letαt⋆\\alpha\_\{t\}^\{\\star\}denote an optimal feasible action at roundtt\.

Then

ℛ𝒞​\(T\)\\displaystyle\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=∑t=1Tmaxα∈𝒜tf⁡g⁡\(α\)​⟨Xt,θ⋆⟩−g⁡\(αt\)​⟨Xt,θ⋆⟩\\displaystyle=\\sum\_\{t=1\}^\{T\}\\max\_\{\\alpha\\in\\mathcal\{A\}^\{f\}\_\{t\}\}g\(\\alpha\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\-g\(\\alpha\_\{t\}\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\(14\)=∑t=1T\(g⁡\(αt⋆\)−g⁡\(αt\)\)​⟨Xt,θ⋆⟩\.\\displaystyle=\\sum\_\{t=1\}^\{T\}\\left\(g\(\\alpha\_\{t\}^\{\\star\}\)\-g\(\\alpha\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\.
We adopt a regret decomposition similar to those commonly used in the literature on constrained linear bandits\[amani2019linear,pacchiano2021stochastic,pacchiano2024contextual\]\. Define the auxiliary feasible action

α~t∈arg⁡maxα∈𝒜tf⁡g⁡\(α\)​⟨Xt,θ~t⟩,\\tilde\{\\alpha\}\_\{t\}\\in\\arg\\max\_\{\\alpha\\in\\mathcal\{A\}^\{f\}\_\{t\}\}g\(\\alpha\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle,\(15\)whereθ~t\\tilde\{\\theta\}\_\{t\}is the optimistic reward parameter defined in[Equation9](https://arxiv.org/html/2608.26755#S3.E9)\. Using this definition, we decompose the regret as

ℛ𝒞​\(T\)\\displaystyle\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=∑t=1T\(g⁡\(αt⋆\)−g⁡\(αt\)\)​⟨Xt,θ⋆⟩\\displaystyle=\\sum\_\{t=1\}^\{T\}\\left\(g\(\\alpha\_\{t\}^\{\\star\}\)\-g\(\\alpha\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\(16\)=∑t=1T\(g⁡\(αt⋆\)−g⁡\(α~t\)\)​⟨Xt,θ⋆⟩Term 1: cost of estimatingθ⋆\\displaystyle=\\sum\_\{t=1\}^\{T\}\\underset\{\\text\{Term 1: cost of estimating $\\theta^\{\\star\}$\}\}\{\\left\(g\(\\alpha\_\{t\}^\{\\star\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\}\+∑t=1T\(g⁡\(α~t\)−g⁡\(αt\)\)​⟨Xt,θ⋆⟩Term 2: cost of estimatingμ⋆\.\\displaystyle\+\\sum\_\{t=1\}^\{T\}\\underset\{\\text\{Term 2: cost of estimating $\\mu^\{\\star\}$\}\}\{\\left\(g\(\\tilde\{\\alpha\}\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\}\.
### 5\.1Analysis of the Regret

###### Lemma 4\.

For allt∈\[T\]t\\in\[T\], on the eventεθ\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\theta\}, the first term in the regret decomposition satisfies

\(g⁡\(αt⋆\)−g⁡\(α~t\)\)​⟨Xt,θ⋆⟩≤g⁡\(α~t\)​⟨Xt,θ~t−θ⋆⟩\.\\left\(g\(\\alpha\_\{t\}^\{\\star\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\leq g\(\\tilde\{\\alpha\}\_\{t\}\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\-\\theta^\{\\star\}\\rangle\.

The proof is provided in the supplementary material\. This bound is the analogue of the standard optimism argument for linear bandits\[abbasi2011improved\], applied to the transformed action valueg⁡\(α\)g\(\\alpha\)\. The main additional step is to control the second term, which captures the loss due to using a conservative estimate of the feasible action set\.

###### Lemma 5\.

For allt∈\[T\]t\\in\[T\], on the eventεμ\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mu\}, the second term in the regret decomposition satisfies

\(g⁡\(α~t\)−g⁡\(αt\)\)​⟨Xt,θ⋆⟩≤κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)⋅⟨Xt,μ~t−μ⋆⟩τ\.\\left\(g\(\\tilde\{\\alpha\}\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\leq\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\\cdot\\frac\{\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\rangle\}\{\\tau\}\.

By combining[Lemma4](https://arxiv.org/html/2608.26755#Thmlemma4)and[Lemma5](https://arxiv.org/html/2608.26755#Thmlemma5)with the regret decomposition in[Equation16](https://arxiv.org/html/2608.26755#S5.E16), we obtain the following bound\.

###### Theorem 2\.

With probability at least1−δ′1\-\\delta^\{\\prime\}, the regret of the High Probability Constrained UCB algorithm satisfies

ℛ𝒞​\(T\)=𝒪​\(CLOSE\\displaystyle\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=\{\\mathcal\{O\}\}\\\!\\Bigl\(\(1\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)τ\)⋅max⁡\{βTr​\(δ′,d\),βTc​\(δ′,d\)\}\\displaystyle\\Bigl\(1\+\\tfrac\{\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\{\\tau\}\\Bigr\)\\cdot\\max\\\{\\beta^\{r\}\_\{T\}\(\\delta^\{\\prime\},d\),\\beta^\{c\}\_\{T\}\(\\delta^\{\\prime\},d\)\\\}×d​T​log⁡\(1\+T​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)2d\)\)\.\\displaystyle\\times\\sqrt\{dT\\log\\\!\\left\(1\+\\tfrac\{T\\kappa\_\{\\ref\{L\}\}^\{2\}\}\{d\}\\right\)\}\\Bigr\)\.

All proofs are deferred to the supplementary material\. Notably, the bound does not depend onδ\\delta, since the benchmark is the clairvoyant policy that knowsθ⋆\\theta^\{\\star\}andμ⋆\\mu^\{\\star\}but must satisfy the same realized\-cost constraint as the learner\.

## 6Non\-linear Rewards and Costs

We now extend the analysis beyond linear reward and cost models\. Instead of assuming that the reward and cost functions are linear in unknown parameters, we consider general function classes and express the regret bound in terms of theeluder dimension\[russo2013eluder\]\.

At each roundtt, the learner observes a contextXtX\_\{t\}and selects an actionαt∈\[0,1\]\\alpha\_\{t\}\\in\[0,1\]\. The reward and cost signals are given by

Rt=g⁡\(αt\)​\(θ⋆​\(Xt\)\+ξtr\),Ct=g⁡\(αt\)​\(μ⋆​\(Xt\)\+ξtc\),R\_\{t\}=g\(\\alpha\_\{t\}\)\\left\(\\theta^\{\\star\}\(X\_\{t\}\)\+\\xi\_\{t\}^\{r\}\\right\),\\qquad C\_\{t\}=g\(\\alpha\_\{t\}\)\\left\(\\mu^\{\\star\}\(X\_\{t\}\)\+\\xi\_\{t\}^\{c\}\\right\),whereθ⋆∈ℱr\\theta^\{\\star\}\\in\{\\mathcal\{F\}\}^\{r\}andμ⋆∈ℱc\\mu^\{\\star\}\\in\{\\mathcal\{F\}\}^\{c\}are the unknown mean reward and cost functions, respectively\. The function classesℱr\{\\mathcal\{F\}\}^\{r\}andℱc\{\\mathcal\{F\}\}^\{c\}are known to the learner\. We assume that all functions in these classes are bounded in\[−1,1\]\[\-1,1\]\. This relaxes the common normalization to\[0,1\]\[0,1\]; the important property for the analysis is boundedness\. As in the linear case, the noise variablesξtr\\xi\_\{t\}^\{r\}andξtc\\xi\_\{t\}^\{c\}are conditionally sub\-Gaussian\.

The realized\-cost feasible action set at roundttis

𝒜tf​\(Xt\)=\{α∈\[0,1\]:g⁡\(α\)​\(μ⋆​\(Xt\)\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\)≤τ\}\.\\mathcal\{A\}\_\{t\}^\{f\}\(X\_\{t\}\)=\\left\\\{\\alpha\\in\[0,1\]:g\(\\alpha\)\\left\(\\mu^\{\\star\}\(X\_\{t\}\)\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\\right\)\\leq\\tau\\right\\\}\.\(17\)The agent selects actions from an estimated subset of this feasible set\.

For a subsetℱ~⊆ℱ\\widetilde\{\{\\mathcal\{F\}\}\}\\subseteq\{\\mathcal\{F\}\}, we define its width at a contextXXas

wℱ~​\(X\)=supf¯,f¯∈ℱ~\(f¯​\(X\)−f¯​\(X\)\)\.w\_\{\\widetilde\{\{\\mathcal\{F\}\}\}\}\(X\)=\\sup\_\{\\underline\{f\},\\overline\{f\}\\in\\widetilde\{\{\\mathcal\{F\}\}\}\}\\left\(\\overline\{f\}\(X\)\-\\underline\{f\}\(X\)\\right\)\.\(18\)This quantity measures the uncertainty of the function class at the current context and plays the same role as confidence widths in the linear analysis\.

TheTT\-round constrained pseudo\-regret is

ℛ⁡\(T\)=∑t=1T\[g⁡\(αt⋆\)​θ⋆​\(Xt\)−g⁡\(αt\)​θ⋆​\(Xt\)\],\\mathcal\{R\}\(T\)=\\sum\_\{t=1\}^\{T\}\\left\[g\(\\alpha\_\{t\}^\{\\star\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\right\],\(19\)where

αt⋆∈arg⁡maxα∈𝒜tf​\(Xt\)⁡g⁡\(α\)​θ⋆​\(Xt\)\\alpha\_\{t\}^\{\\star\}\\in\\arg\\max\_\{\\alpha\\in\\mathcal\{A\}\_\{t\}^\{f\}\(X\_\{t\}\)\}g\(\\alpha\)\\theta^\{\\star\}\(X\_\{t\}\)is the optimal feasible action at roundtt\.

We define the dataset available at the beginning of roundttas

𝒟t=\{\(Xs,Rsg⁡\(αs\),Csg⁡\(αs\)\):s⁡<t,g⁡\(αs\)\>​0\}\.\\mathcal\{D\}\_\{t\}=\\left\\\{\\left\(X\_\{s\},\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\},\\frac\{C\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}\\right\):s<t,\\ g\(\\alpha\_\{s\}\)\>0\\right\\\}\.Thus, wheneverg⁡\(αs\)\>0g\(\\alpha\_\{s\}\)\>0,

Rsg⁡\(αs\)=θ⋆​\(Xs\)\+ξsr,Csg⁡\(αs\)=μ⋆​\(Xs\)\+ξsc\.\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\theta^\{\\star\}\(X\_\{s\}\)\+\\xi\_\{s\}^\{r\},\\qquad\\frac\{C\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\mu^\{\\star\}\(X\_\{s\}\)\+\\xi\_\{s\}^\{c\}\.Rounds withg⁡\(αs\)=0g\(\\alpha\_\{s\}\)=0provide no information about the unknown functions and are excluded\. For any functionff, let

‖f‖𝒟t=∑\(Xs,⋅,⋅\)∈𝒟tf2​\(Xs\)\\left\\lVert f\\right\\rVert\_\{\\mathcal\{D\}\_\{t\}\}=\\sqrt\{\\sum\_\{\(X\_\{s\},\\cdot,\\cdot\)\\in\\mathcal\{D\}\_\{t\}\}f^\{2\}\(X\_\{s\}\)\}denote the empirical norm induced by the observed contexts\.

At each round, we construct least\-squares estimatesθ^t\\hat\{\\theta\}\_\{t\}andμ^t\\hat\{\\mu\}\_\{t\}over the classesℱr\{\\mathcal\{F\}\}^\{r\}andℱc\{\\mathcal\{F\}\}^\{c\}using the transformed observations in𝒟t\\mathcal\{D\}\_\{t\}\. We then define the confidence sets

𝒞tr​\(δ′\)\\displaystyle\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)=\{θ∈ℱr:‖θ−θ^t‖𝒟t2≤ρr​\(t,δ′\)\},\\displaystyle=\\left\\\{\\theta\\in\{\\mathcal\{F\}\}^\{r\}:\\left\\lVert\\theta\-\\hat\{\\theta\}\_\{t\}\\right\\rVert\_\{\\mathcal\{D\}\_\{t\}\}^\{2\}\\leq\\rho^\{r\}\(t,\\delta^\{\\prime\}\)\\right\\\},\(20\)𝒞tc​\(δ′\)\\displaystyle\\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)=\{μ∈ℱc:‖μ−μ^t‖𝒟t2≤ρc​\(t,δ′\)\}\.\\displaystyle=\\left\\\{\\mu\\in\{\\mathcal\{F\}\}^\{c\}:\\left\\lVert\\mu\-\\hat\{\\mu\}\_\{t\}\\right\\rVert\_\{\\mathcal\{D\}\_\{t\}\}^\{2\}\\leq\\rho^\{c\}\(t,\\delta^\{\\prime\}\)\\right\\\}\.\(21\)For finite function classes, one may take

ρr​\(t,δ′\)=8​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2​log⁡\(\|ℱr\|δ′\),ρc​\(t,δ′\)=8​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2​log⁡\(\|ℱc\|δ′\)\.\\rho^\{r\}\(t,\\delta^\{\\prime\}\)=8\\kappa\_\{\\ref\{Cr\}\}^\{2\}\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{r\}\|\}\{\\delta^\{\\prime\}\}\\right\),\\qquad\\rho^\{c\}\(t,\\delta^\{\\prime\}\)=8\\kappa\_\{\\ref\{Cc\}\}^\{2\}\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{c\}\|\}\{\\delta^\{\\prime\}\}\\right\)\.More generally, the regret bound below is stated in terms of the corresponding confidence radii and eluder dimensions\.

To construct the estimated feasible action set, we choose the most conservative cost function in the confidence set at the current context\. Specifically, we solve

maxμ∈ℱc\\displaystyle\\underset\{\\mu\\in\{\\mathcal\{F\}\}^\{c\}\}\{\\max\}μ⁡\(Xt\)\\displaystyle\\mu\(X\_\{t\}\)\(22\)subject to\\displaystyle\\text\{subject to\}μ∈𝒞tc​\(δ′\),\\displaystyle\\mu\\in\\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\),μ⁡\(Xt\)\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)≥0\.\\displaystyle\\mu\(X\_\{t\}\)\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\\geq 0\.If this optimization problem has no feasible solution, we set

𝒜^tf=\[0,1\]\.\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}=\[0,1\]\.Otherwise, letμ~t\\tilde\{\\mu\}\_\{t\}denote a solution of \([22](https://arxiv.org/html/2608.26755#S6.E22)\)\. The estimated feasible set is then

𝒜^tf=\[0,g−1​\(min⁡\{1,τμ~t​\(Xt\)\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\}\)\]\.\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}=\\left\[0,g^\{\-1\}\\left\(\\min\\left\\\{1,\\frac\{\\tau\}\{\\tilde\{\\mu\}\_\{t\}\(X\_\{t\}\)\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\}\\right\\\}\\right\)\\right\]\.\(23\)
For the reward function, we use optimism and select

θ~t​\(Xt\)=maxθ∈𝒞tr​\(δ′\)⁡θ⁡\(Xt\)\.\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)=\\max\_\{\\theta\\in\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)\}\\theta\(X\_\{t\}\)\.The action is then chosen as

αt∈arg⁡maxα∈𝒜^tf⁡g⁡\(α\)​θ~t​\(Xt\)\.\\alpha\_\{t\}\\in\\arg\\max\_\{\\alpha\\in\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\}g\(\\alpha\)\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)\.Sinceggis strictly increasing, this optimization reduces to selecting the largest action in𝒜^tf\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}wheneverθ~t​\(Xt\)≥0\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)\\geq 0, and selectingαt=0\\alpha\_\{t\}=0otherwise\.

Algorithm 2Non\-Linear High Probability Constrained UCB1:Constraint threshold

τ\>0\\tau\>0, safety parameter

δ\\delta, confidence parameter

δ′\\delta^\{\\prime\}, sub\-Gaussianity constants

κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1),κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cr\}\},\\kappa\_\{\\ref\{Cc\}\}
2:

α1←g−1​\(min⁡\{1,τκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1/δ\)\+1\}\)\\alpha\_\{1\}\\leftarrow g^\{\-1\}\\\!\\left\(\\min\\left\\\{1,\\frac\{\\tau\}\{\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\(1/\\delta\)\}\+1\}\\right\\\}\\right\)
3:Select action

α1\\alpha\_\{1\}and store

\(X1,R1,C1\)\(X\_\{1\},R\_\{1\},C\_\{1\}\)
4:for

t=2,3,…,Tt=2,3,\\ldots,Tdo

5:Compute

θ^t,μ^t\\hat\{\\theta\}\_\{t\},\\hat\{\\mu\}\_\{t\}using least\-squares estimators over

ℱr\{\\mathcal\{F\}\}^\{r\}and

ℱc\{\\mathcal\{F\}\}^\{c\}\.

6:Construct

𝒞tr​\(δ′\)\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)and

𝒞tc​\(δ′\)\\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)using \([20](https://arxiv.org/html/2608.26755#S6.E20)\)\.

7:Compute

𝒜^tf\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}using \([22](https://arxiv.org/html/2608.26755#S6.E22)\) and \([23](https://arxiv.org/html/2608.26755#S6.E23)\)\.

8:Compute

θ~t​\(Xt\)=maxθ∈𝒞tr​\(δ′\)⁡θ⁡\(Xt\)\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)=\\max\_\{\\theta\\in\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)\}\\theta\(X\_\{t\}\)\.

9:Compute

αt∈arg⁡maxα∈𝒜^tf⁡g⁡\(α\)​θ~t​\(Xt\)\.\\alpha\_\{t\}\\in\\arg\\max\_\{\\alpha\\in\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\}g\(\\alpha\)\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)\.
10:Select action

αt\\alpha\_\{t\}\.

11:if

g⁡\(αt\)\>0g\(\\alpha\_\{t\}\)\>0then

12:Store

\(Xt,Rt,Ct\)\(X\_\{t\},R\_\{t\},C\_\{t\}\)\.

13:endif

14:endfor

Letdeluderrd^\{r\}\_\{\\mathrm\{eluder\}\}anddeludercd^\{c\}\_\{\\mathrm\{eluder\}\}denote the eluder dimensions of the reward and cost function classes, respectively\. The following theorem gives the regret guarantee for the non\-linear setting\.

###### Theorem 3\.

With probability at least1−δ′1\-\\delta^\{\\prime\}, the regret of the Non\-Linear High Probability Constrained UCB algorithm satisfies

ℛ⁡\(T\)=𝒪⁡\(CLOSE\\displaystyle\\mathcal\{R\}\(T\)=\\mathcal\{O\}\\Big\(deluderr​T​ρr​\(T,δ′/3\)\\displaystyle\\sqrt\{d^\{r\}\_\{\\mathrm\{eluder\}\}T\\rho^\{r\}\(T,\\delta^\{\\prime\}/3\)\}OPEN\+1τ​deluderc​T​ρc​\(T,δ′/3\)\)\.\\displaystyle\+\\frac\{1\}\{\\tau\}\\sqrt\{d^\{c\}\_\{\\mathrm\{eluder\}\}T\\rho^\{c\}\(T,\\delta^\{\\prime\}/3\)\}\\Big\)\.

## 7Experimental Results

We evaluate the performance of[Algorithm1](https://arxiv.org/html/2608.26755#alg1)on both synthetic and real\-world datasets\. A natural application of our algorithm is dosage selection, where the action corresponds to the administered treatment level\. However, access to large\-scale medical datasets with rich patient context is limited, and we leave a thorough empirical study in clinical settings for future work\. Instead, we assess the performance of our method on the[NASA Li\-ion Battery Aging Datasets](https://data.nasa.gov/dataset/li-ion-battery-aging-datasets)\. In this setting, we interpret the current level as the dosage, the voltage change as the reward, and the temperature as the cost\.

We first report in[Table1](https://arxiv.org/html/2608.26755#S7.T1)the violation ratio ofHPUCBand compare it with a baseline algorithm that enforces the cost constraint only in expectation, as in\[pacchiano2024contextual\]\. We observe thatHPUCBachieves a violation ratio of0\.02%0\.02\\%, whereas the expected\-cost baseline exhibits violation rates between12%12\\%and23%23\\%\. Such violation rates are undesirable in safety\-critical applications, where individual unsafe outcomes may be unacceptable\.

We begin with synthetic experiments\. We generateθ∗\\theta^\{\*\}andμ∗\\mu^\{\*\}by sampling from add\-dimensional standard normal distribution and normalizing them to unit norm\. ContextsXtX\_\{t\}are generated similarly from a multivariate normal distribution and normalized\. We consider dimensionsd∈\{5,10\}d\\in\\\{5,10\\\}and multiple threshold valuesτ\\tau, and run each configuration for10410^\{4\}rounds over 5 random seeds\. In the linear case, we use the closed\-form solutions derived for[Equations9](https://arxiv.org/html/2608.26755#S3.E9)and[10](https://arxiv.org/html/2608.26755#S3.E10), avoiding the need to solve convex programs at each round\. The total running time across all seeds is below two minutes for all thresholds\. All experiments were run on a MacBook Air with an Apple M3 chip and 24 GB RAM using the JAX framework\. The dominant computational cost comes from Cholesky decompositions, which scale as𝒪⁡\(d3\)\{\\mathcal\{O\}\}\(d^\{3\}\)\. JAX substantially accelerates these linear algebra operations, especially when executed on a GPU\. This becomes particularly relevant in the real\-world experiment, where the feature dimension is 2048\.

Table 1:Comparison of HP\-UCB and On\-Expectation across different values ofτ\\tau, with 95% confidence intervals\.In[Figure2](https://arxiv.org/html/2608.26755#S7.F2), we report representative learning curves ford∈\{5,10\}d\\in\\\{5,10\\\}with thresholdτ=0\.5\\tau=0\.5\. We compare our algorithm with a variant ofε\\varepsilon\-Greedy that plays the safe actionα1\\alpha\_\{1\}, as defined in[Equation5](https://arxiv.org/html/2608.26755#S2.E5), with probabilityε\\varepsilon, and otherwise follows the policy of[Algorithm1](https://arxiv.org/html/2608.26755#alg1)\. The main advantage of this variant is its lower computational cost, especially in higher dimensions, while still collecting approximatelyε​T\\varepsilon Tinformative samples that help tighten its confidence intervals\. Empirically, we find thatε=0\.5\\varepsilon=0\.5provides a favorable trade\-off between computational efficiency and statistical performance, achieving comparable regret while avoiding dependence onTTin the parameter tuning\.

A direct comparison with the method of\[pacchiano2024contextual\]is not entirely appropriate, as their algorithm enforces the cost constraint only in expectation, whereas our setting requires high\-probability constraint satisfaction for the realized cost\. As shown in[Table1](https://arxiv.org/html/2608.26755#S7.T1), this difference leads to substantially higher violation rates for the expected\-cost baseline\.

\(a\)d=5d=5,τ=0\.5\\tau=0\.5\(b\)d=10d=10,τ=0\.5\\tau=0\.5
Figure 2:Synthetic experiments comparingHPUCBandε\\varepsilon\-Greedy forτ=0\.5\\tau=0\.5\.We now describe the experimental setup for the[NASA Li\-ion Battery Aging Datasets](https://data.nasa.gov/dataset/li-ion-battery-aging-datasets)\. The dataset contains measurements from four types of batteries \(RW9, RW10, RW11, RW12\) operating under both charging and discharging modes, across a range of current levels\. For each cycle, the dataset records the voltage change, temperature, textual metadata describing the operating conditions, and a time series corresponding to the duration of the cycle\.

To construct contextual features, we use embeddings generated by the language model Gemma\[team2024gemma\]\. At each round, the input to the language model consists of all available information from the previous five time steps, formatted as a JSON object\. The resulting embedding vector has dimension 2048 and serves as the contextXtX\_\{t\}\.

To satisfy the realizability assumption and obtain ground\-truth parametersθ∗\\theta^\{\*\}andμ∗\\mu^\{\*\}, we split the dataset into four parts and use approximately half of the data, about 100k samples with dimension2048\+32048\+3, to perform a least\-squares fit\. The fitted parameters are then treated as the true underlying model, and we evaluate the performance of[Algorithm1](https://arxiv.org/html/2608.26755#alg1)on the remaining portion of the dataset\.

Due to the high dimensionality of the problem, all real\-world experiments were conducted on a compute cluster equipped with an NVIDIA L40 GPU\. The total running time was approximately 30 minutes forHPUCBand about two minutes for the baseline algorithm, which has access to the true reward and cost parameters\. We report the cumulative regret ofHPUCBandε\\varepsilon\-Greedy for threshold valuesτ∈\{0\.1,0\.2\}\\tau\\in\\\{0\.1,0\.2\\\}\.

\(a\)τ=0\.1\\tau=0\.1\(b\)τ=0\.2\\tau=0\.2
Figure 3:NASA Li\-ion Battery Aging Dataset experiments for different safety thresholds\.Finally, we note that the guarantees of our algorithm hold for arbitrary context sequencesXtX\_\{t\}, including both stochastic and adversarial settings\. This property makes the proposed approach particularly appealing for applications such as battery charging and control problems, where an explicit dynamical model of the system may be unavailable or difficult to specify\. In such scenarios, our algorithm provides a principled way to perform safe decision\-making directly from observed data\.

## 8Conclusions

We studied contextual bandits with continuous actions under stage\-wise high\-probability constraints on the realized cost, motivated by applications in which the variability of the outcome depends on the selected action\. We introduced an optimistic–pessimistic algorithm that balances reward exploration with conservative estimation of the feasible action set, and established regret guarantees for both linear and general reward–cost models\. Our experimental results further illustrate the importance of accounting for heteroscedasticity when safety is imposed on realized, rather than expected, costs\.

Several directions remain open\. An important extension is to consider more general forms of heteroscedasticity beyond the action\-scaled structure studied here, as well as Bayesian approaches to the same realized\-cost constrained problem\. Another promising direction is a more extensive empirical evaluation in safety\-critical real\-world applications, particularly adaptive clinical dosage selection\.

## References

Appendix

###### Contents

1. [1Introduction](https://arxiv.org/html/2608.26755#S1)
2. [2Model and Problem Formulation](https://arxiv.org/html/2608.26755#S2)1. [2\.1Assumptions](https://arxiv.org/html/2608.26755#S2.SS1) 2. [2\.2Constraint Formulation](https://arxiv.org/html/2608.26755#S2.SS2)
3. [3Proposed Algorithm](https://arxiv.org/html/2608.26755#S3)1. [3\.1Construction of the Estimated Feasible Set](https://arxiv.org/html/2608.26755#S3.SS1)
4. [4The “Good Event”](https://arxiv.org/html/2608.26755#S4)
5. [5Regret Analysis – Linear Case](https://arxiv.org/html/2608.26755#S5)1. [5\.1Analysis of the Regret](https://arxiv.org/html/2608.26755#S5.SS1)
6. [6Non\-linear Rewards and Costs](https://arxiv.org/html/2608.26755#S6)
7. [7Experimental Results](https://arxiv.org/html/2608.26755#S7)
8. [8Conclusions](https://arxiv.org/html/2608.26755#S8)
9. [References](https://arxiv.org/html/2608.26755#bib)
10. [AConstraint Formulation](https://arxiv.org/html/2608.26755#A1)1. [A\.1Proof of](https://arxiv.org/html/2608.26755#A1.SS1) 2. [A\.2Proof of](https://arxiv.org/html/2608.26755#A1.SS2)
11. [BGood Event](https://arxiv.org/html/2608.26755#A2)1. [B\.1Proof of](https://arxiv.org/html/2608.26755#A2.SS1)
12. [CAnalytical Solutions toand](https://arxiv.org/html/2608.26755#A3)
13. [DRegret Analysis – Linear Case](https://arxiv.org/html/2608.26755#A4)1. [D\.1Proof of](https://arxiv.org/html/2608.26755#A4.SS1) 2. [D\.2Proof of](https://arxiv.org/html/2608.26755#A4.SS2) 3. [D\.3Proof of](https://arxiv.org/html/2608.26755#A4.SS3)
14. [ENon\-linear Rewards and Costs](https://arxiv.org/html/2608.26755#A5)1. [E\.1Concentration for Non\-linear Least Squares](https://arxiv.org/html/2608.26755#A5.SS1) 2. [E\.2Non\-linear Regret Analysis](https://arxiv.org/html/2608.26755#A5.SS2) 3. [E\.3Proof of](https://arxiv.org/html/2608.26755#A5.SS3)

## Appendix AConstraint Formulation

### A\.1Proof of[Lemma1](https://arxiv.org/html/2608.26755#Thmlemma1)

By[Assumption2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1), the cost noiseξtc\\xi\_\{t\}^\{c\}is conditionallyκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cc\}\}\-sub\-Gaussian given the historyℋt\\mathcal\{H\}\_\{t\}\. Letzt:=g⁡\(αt\)z\_\{t\}:=g\(\\alpha\_\{t\}\)\. Ifzt=0z\_\{t\}=0, thenCt=0C\_\{t\}=0, and sinceτ\>0\\tau\>0the constraint is satisfied trivially\. We therefore consider the casezt\>0z\_\{t\}\>0\.

###### Theorem 4\(Sub\-Gaussian concentration bounds – Theorem 5\.3 in\[lattimore2020bandit\]\)\.

IfXXisσ\\sigma\-sub\-Gaussian, then for anyϵ\>0\\epsilon\>0,

ℙ⁡\(X≥ϵ\)≤exp⁡\(−ϵ22​σ2\)\.\\mathbb\{P\}\(X\\geq\\epsilon\)\\leq\\exp\\left\(\-\\frac\{\\epsilon^\{2\}\}\{2\\sigma^\{2\}\}\\right\)\.

See[1](https://arxiv.org/html/2608.26755#Thmlemma1)

###### Proof\.

Since

Ct=zt​\(⟨Xt,μ⋆⟩\+ξtc\),C\_\{t\}=z\_\{t\}\\left\(\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\+\\xi\_\{t\}^\{c\}\\right\),we have

Ct−zt​⟨Xt,μ⋆⟩zt=ξtc\.\\frac\{C\_\{t\}\-z\_\{t\}\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\}\{z\_\{t\}\}=\\xi\_\{t\}^\{c\}\.Thus, conditional onℋt\\mathcal\{H\}\_\{t\},

ℙ⁡\(Ct≥τ∣ℋt\)\\displaystyle\\mathbb\{P\}\(C\_\{t\}\\geq\\tau\\mid\\mathcal\{H\}\_\{t\}\)=ℙ⁡\(ξtc≥τ−zt​⟨Xt,μ⋆⟩zt\|ℋt\)\\displaystyle=\\mathbb\{P\}\\left\(\\xi\_\{t\}^\{c\}\\geq\\frac\{\\tau\-z\_\{t\}\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\}\{z\_\{t\}\}\\,\\middle\|\\,\\mathcal\{H\}\_\{t\}\\right\)≤exp⁡\(−\(τ−zt​⟨Xt,μ⋆⟩zt\)22​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2\),\\displaystyle\\leq\\exp\\left\(\-\\frac\{\\left\(\\dfrac\{\\tau\-z\_\{t\}\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\}\{z\_\{t\}\}\\right\)^\{2\}\}\{2\\kappa\_\{\\ref\{Cc\}\}^\{2\}\}\\right\),where the last step follows from[Theorem4](https://arxiv.org/html/2608.26755#Thmthm4)\. Therefore, it is sufficient to require

κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)≤τ−zt​⟨Xt,μ⋆⟩zt,\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\\leq\\frac\{\\tau\-z\_\{t\}\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\}\{z\_\{t\}\},which is equivalent to

g⁡\(αt\)​\(⟨Xt,μ⋆⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\)≤τ\.g\(\\alpha\_\{t\}\)\\left\(\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\\right\)\\leq\\tau\.Under this condition,ℙ⁡\(Ct≤τ∣ℋt\)≥1−δ\\mathbb\{P\}\(C\_\{t\}\\leq\\tau\\mid\\mathcal\{H\}\_\{t\}\)\\geq 1\-\\delta\. ∎

### A\.2Proof of[Lemma2](https://arxiv.org/html/2608.26755#Thmlemma2)

See[2](https://arxiv.org/html/2608.26755#Thmlemma2)

###### Proof\.

Let

Bt​\(μ\):=⟨Xt,μ⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\.B\_\{t\}\(\\mu\):=\\langle X\_\{t\},\\mu\\rangle\+\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\.On the event\{μ⋆∈𝒞tc\(δ′\)\}\\\{\\mu^\{\\star\}\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)\\\}, which holds with probability at least1−δ′1\-\\delta^\{\\prime\}by[Theorem1](https://arxiv.org/html/2608.26755#Thmthm1), we show that

𝒜^tf​\(δ\)⊆𝒜tf​\(δ\)\.\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\(\\delta\)\\subseteq\\mathcal\{A\}\_\{t\}^\{f\}\(\\delta\)\.
We consider two cases\.

Case 1:𝒦​\(μ^t\)t=∅\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}=\\emptyset\.Sinceμ⋆∈𝒞tc​\(δ′\)\\mu^\{\\star\}\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\), the only way the feasible set of[Equation10](https://arxiv.org/html/2608.26755#S3.E10)can be empty is if

Bt​\(μ⋆\)<0\.B\_\{t\}\(\\mu^\{\\star\}\)<0\.Then for everyα∈\[0,1\]\\alpha\\in\[0,1\],

g⁡\(α\)​Bt​\(μ⋆\)≤0≤τ\.g\(\\alpha\)B\_\{t\}\(\\mu^\{\\star\}\)\\leq 0\\leq\\tau\.Hence𝒜tf​\(δ\)=\[0,1\]\\mathcal\{A\}\_\{t\}^\{f\}\(\\delta\)=\[0,1\]\. By construction,𝒜^tf​\(δ\)=\[0,1\]\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\(\\delta\)=\[0,1\]as well, so the inclusion holds\.

Case 2:𝒦​\(μ^t\)t≠∅\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}\\neq\\emptyset\.Letμ~t\\tilde\{\\mu\}\_\{t\}be the solution of[Equation10](https://arxiv.org/html/2608.26755#S3.E10)\. IfBt​\(μ⋆\)<0B\_\{t\}\(\\mu^\{\\star\}\)<0, then again𝒜tf​\(δ\)=\[0,1\]\\mathcal\{A\}\_\{t\}^\{f\}\(\\delta\)=\[0,1\], and the inclusion is immediate\.

It remains to consider the caseBt​\(μ⋆\)≥0B\_\{t\}\(\\mu^\{\\star\}\)\\geq 0\. Sinceμ⋆∈𝒦​\(μ^t\)t\\mu^\{\\star\}\\in\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}andμ~t\\tilde\{\\mu\}\_\{t\}maximizes⟨Xt,μ⟩\\langle X\_\{t\},\\mu\\rangleover𝒦​\(μ^t\)t\\mathcal\{K\}\\left\(\\hat\{\\mu\}\_\{t\}\\right\)\_\{t\}, we have

⟨Xt,μ⋆⟩≤⟨Xt,μ~t⟩,\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\\leq\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\\rangle,and therefore

Bt​\(μ⋆\)≤Bt​\(μ~t\)\.B\_\{t\}\(\\mu^\{\\star\}\)\\leq B\_\{t\}\(\\tilde\{\\mu\}\_\{t\}\)\.Now take anyα∈𝒜^tf​\(δ\)\\alpha\\in\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\(\\delta\)\. By definition,

g⁡\(α\)​Bt​\(μ~t\)≤τ\.g\(\\alpha\)B\_\{t\}\(\\tilde\{\\mu\}\_\{t\}\)\\leq\\tau\.Sinceg⁡\(α\)≥0g\(\\alpha\)\\geq 0andBt​\(μ⋆\)≤Bt​\(μ~t\)B\_\{t\}\(\\mu^\{\\star\}\)\\leq B\_\{t\}\(\\tilde\{\\mu\}\_\{t\}\), it follows that

g⁡\(α\)​Bt​\(μ⋆\)≤τ\.g\(\\alpha\)B\_\{t\}\(\\mu^\{\\star\}\)\\leq\\tau\.Thusα∈𝒜tf​\(δ\)\\alpha\\in\\mathcal\{A\}\_\{t\}^\{f\}\(\\delta\)\. Therefore,

𝒜^tf​\(δ\)⊆𝒜tf​\(δ\)\.\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\(\\delta\)\\subseteq\\mathcal\{A\}\_\{t\}^\{f\}\(\\delta\)\.Conditioning on\{μ⋆∈𝒞tc\(δ′\)\}\\\{\\mu^\{\\star\}\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)\\\}gives the desired probability bound\. ∎

## Appendix BGood Event

### B\.1Proof of[Lemma3](https://arxiv.org/html/2608.26755#Thmlemma3)

See[3](https://arxiv.org/html/2608.26755#Thmlemma3)

###### Proof\.

We prove that each component of the good event holds with probability at least1−δ′1\-\\delta^\{\\prime\}, and then apply a union bound\. By[Theorem1](https://arxiv.org/html/2608.26755#Thmthm1),

ℙ⁡\(εθ\)≥1−δ′,ℙ⁡\(εμ\)≥1−δ′\.\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\theta\}\)\\geq 1\-\\delta^\{\\prime\},\\qquad\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mu\}\)\\geq 1\-\\delta^\{\\prime\}\.Moreover,[Lemma2](https://arxiv.org/html/2608.26755#Thmlemma2)gives

ℙ⁡\(εA\)≥1−δ′\.\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{A\}\)\\geq 1\-\\delta^\{\\prime\}\.Therefore,

ℙ⁡\(ε\)=ℙ⁡\(εθ∩εμ∩εA\)≥1−3​δ′,\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\)=\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\theta\}\\cap\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mu\}\\cap\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{A\}\)\\geq 1\-3\\delta^\{\\prime\},as claimed\. ∎

## Appendix CAnalytical Solutions to[Equations9](https://arxiv.org/html/2608.26755#S3.E9)and[10](https://arxiv.org/html/2608.26755#S3.E10)

In this section, we derive closed\-form solutions to[Equations9](https://arxiv.org/html/2608.26755#S3.E9)and[10](https://arxiv.org/html/2608.26755#S3.E10)in the linear case using the Karush–Kuhn–Tucker \(KKT\) conditions\[boyd2004convex\]\. This avoids solving a convex program at each round and substantially reduces the computational cost of the algorithm\.

###### Lemma 6\(Linear maximization over an ellipsoid\)\.

Letc∈ℝdc\\in\\mathbb\{R\}^\{d\}withc≠0c\\neq 0, letΣ∈ℝd×d\\Sigma\\in\\mathbb\{R\}^\{d\\times d\}be symmetric positive definite, and letβ\>0\\beta\>0\. Consider

maxx∈ℝd⁡⟨c,x⟩subject tox⊤​Σ​x≤β2\.\\max\_\{x\\in\\mathbb\{R\}^\{d\}\}\\ \\langle c,x\\rangle\\quad\\text\{subject to\}\\quad x^\{\\top\}\\Sigma x\\leq\\beta^\{2\}\.Then the unique optimal solution is

x⋆=β​Σ−1​c‖c‖Σ−1,x^\{\\star\}=\\beta\\,\\frac\{\\Sigma^\{\-1\}c\}\{\\left\\lVert c\\right\\rVert\_\{\\Sigma^\{\-1\}\}\},and the optimal value is

maxx⊤​Σ​x≤β2⁡⟨c,x⟩=β​‖c‖Σ−1\.\\max\_\{x^\{\\top\}\\Sigma x\\leq\\beta^\{2\}\}\\langle c,x\\rangle=\\beta\\left\\lVert c\\right\\rVert\_\{\\Sigma^\{\-1\}\}\.

###### Proof\.

SinceΣ≻0\\Sigma\\succ 0, the feasible set is nonempty, compact, and convex\. The objective is continuous and linear, so an optimum exists\. The KKT conditions are necessary and sufficient because Slater’s condition holds\. The Lagrangian is

ℒ⁡\(x,λ\)=⟨c,x⟩−λ⁡\(x⊤​Σ​x−β2\),λ≥0\.\\mathcal\{L\}\(x,\\lambda\)=\\langle c,x\\rangle\-\\lambda\(x^\{\\top\}\\Sigma x\-\\beta^\{2\}\),\\qquad\\lambda\\geq 0\.Stationarity gives

c−2​λ​Σ​x=0,hencex=12​λ​Σ−1​c\.c\-2\\lambda\\Sigma x=0,\\qquad\\text\{hence\}\\qquad x=\\frac\{1\}\{2\\lambda\}\\Sigma^\{\-1\}c\.Sincec≠0c\\neq 0, the optimum lies on the boundary, sox⊤​Σ​x=β2x^\{\\top\}\\Sigma x=\\beta^\{2\}\. Substituting the expression forxxgives

β2=14​λ2​c⊤​Σ−1​c\.\\beta^\{2\}=\\frac\{1\}\{4\\lambda^\{2\}\}c^\{\\top\}\\Sigma^\{\-1\}c\.Thus

λ=12​β​c⊤​Σ−1​c\.\\lambda=\\frac\{1\}\{2\\beta\}\\sqrt\{c^\{\\top\}\\Sigma^\{\-1\}c\}\.Substituting back yields

x⋆=β​Σ−1​cc⊤​Σ−1​c=β​Σ−1​c‖c‖Σ−1\.x^\{\\star\}=\\beta\\frac\{\\Sigma^\{\-1\}c\}\{\\sqrt\{c^\{\\top\}\\Sigma^\{\-1\}c\}\}=\\beta\\frac\{\\Sigma^\{\-1\}c\}\{\\left\\lVert c\\right\\rVert\_\{\\Sigma^\{\-1\}\}\}\.The optimal value follows immediately\. Uniqueness follows from strict convexity of the ellipsoid boundary in the direction of the nonzero linear functional\. ∎

###### Proposition 1\(Closed form forθ~t\\tilde\{\\theta\}\_\{t\}\)\.

The solution of[Equation9](https://arxiv.org/html/2608.26755#S3.E9)is uniquely given by

θ~t=θ^t\+βtr​\(δ′,d\)​Σt−1​Xt‖Xt‖Σt−1\.\\tilde\{\\theta\}\_\{t\}=\\hat\{\\theta\}\_\{t\}\+\\beta\_\{t\}^\{r\}\(\\delta^\{\\prime\},d\)\\frac\{\\Sigma\_\{t\}^\{\-1\}X\_\{t\}\}\{\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\}\.Moreover,

maxθ∈𝒞tr​\(δ′\)⁡⟨Xt,θ⟩=⟨Xt,θ^t⟩\+βtr​\(δ′,d\)​‖Xt‖Σt−1\.\\max\_\{\\theta\\in\{\\mathcal\{C\}\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)\}\\langle X\_\{t\},\\theta\\rangle=\\langle X\_\{t\},\\hat\{\\theta\}\_\{t\}\\rangle\+\\beta\_\{t\}^\{r\}\(\\delta^\{\\prime\},d\)\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\.

###### Proof\.

Apply[Lemma6](https://arxiv.org/html/2608.26755#Thmlemma6)withc=Xtc=X\_\{t\}andx=θ−θ^tx=\\theta\-\\hat\{\\theta\}\_\{t\}\. ∎

###### Proposition 2\(Closed form forμ~t\\tilde\{\\mu\}\_\{t\}\)\.

The solution of

maxμ∈𝒞tc​\(δ′\)⁡⟨Xt,μ⟩\\max\_\{\\mu\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)\}\\langle X\_\{t\},\\mu\\rangleis uniquely given by

μ~t=μ^t\+βtc​\(δ′,d\)​Σt−1​Xt‖Xt‖Σt−1\.\\tilde\{\\mu\}\_\{t\}=\\hat\{\\mu\}\_\{t\}\+\\beta\_\{t\}^\{c\}\(\\delta^\{\\prime\},d\)\\frac\{\\Sigma\_\{t\}^\{\-1\}X\_\{t\}\}\{\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\}\.Moreover,

maxμ∈𝒞tc​\(δ′\)⁡⟨Xt,μ⟩=⟨Xt,μ^t⟩\+βtc​\(δ′,d\)​‖Xt‖Σt−1\.\\max\_\{\\mu\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)\}\\langle X\_\{t\},\\mu\\rangle=\\langle X\_\{t\},\\hat\{\\mu\}\_\{t\}\\rangle\+\\beta\_\{t\}^\{c\}\(\\delta^\{\\prime\},d\)\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\.

###### Proof\.

Apply[Lemma6](https://arxiv.org/html/2608.26755#Thmlemma6)withc=Xtc=X\_\{t\}andx=μ−μ^tx=\\mu\-\\hat\{\\mu\}\_\{t\}\. ∎

###### Lemma 7\(Feasibility of the pessimistic cost program\)\.

Let

𝒞tc=\{μ∈ℝd:‖μ−μ^t‖Σt≤βtc\},\{\\mathcal\{C\}\}\_\{t\}^\{c\}=\\left\\\{\\mu\\in\\mathbb\{R\}^\{d\}:\\left\\lVert\\mu\-\\hat\{\\mu\}\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}\}\\leq\\beta\_\{t\}^\{c\}\\right\\\},and define

bδ=κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\)\.b\_\{\\delta\}=\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\}\.Consider

maxμ∈𝒞tc⁡⟨Xt,μ⟩subject to⟨Xt,μ⟩\+bδ≥0\.\\max\_\{\\mu\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\}\\langle X\_\{t\},\\mu\\rangle\\qquad\\text\{subject to\}\\qquad\\langle X\_\{t\},\\mu\\rangle\+b\_\{\\delta\}\\geq 0\.Let

v¯t=maxμ∈𝒞tc⁡⟨Xt,μ⟩=⟨Xt,μ^t⟩\+βtc​‖Xt‖Σt−1\.\\bar\{v\}\_\{t\}=\\max\_\{\\mu\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\}\}\\langle X\_\{t\},\\mu\\rangle=\\langle X\_\{t\},\\hat\{\\mu\}\_\{t\}\\rangle\+\\beta\_\{t\}^\{c\}\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\.Then the program is infeasible if and only ifv¯t\+bδ<0\\bar\{v\}\_\{t\}\+b\_\{\\delta\}<0\. Ifv¯t\+bδ≥0\\bar\{v\}\_\{t\}\+b\_\{\\delta\}\\geq 0, then the unconstrained maximizer over𝒞tc\{\\mathcal\{C\}\}\_\{t\}^\{c\}is feasible and is also the optimizer of the constrained problem\.

###### Proof\.

Ifv¯t\+bδ<0\\bar\{v\}\_\{t\}\+b\_\{\\delta\}<0, then for everyμ∈𝒞tc\\mu\\in\{\\mathcal\{C\}\}\_\{t\}^\{c\},

⟨Xt,μ⟩\+bδ≤v¯t\+bδ<0\.\\langle X\_\{t\},\\mu\\rangle\+b\_\{\\delta\}\\leq\\bar\{v\}\_\{t\}\+b\_\{\\delta\}<0\.Thus the constraint cannot be satisfied, and the program is infeasible\.

Ifv¯t\+bδ≥0\\bar\{v\}\_\{t\}\+b\_\{\\delta\}\\geq 0, then the unconstrained maximizer satisfies the additional constraint\. Since it already maximizes⟨Xt,μ⟩\\langle X\_\{t\},\\mu\\rangleover the larger set𝒞tc\{\\mathcal\{C\}\}\_\{t\}^\{c\}, it also maximizes the same objective over the constrained feasible subset\. ∎

## Appendix DRegret Analysis – Linear Case

As shown in[Section5](https://arxiv.org/html/2608.26755#S5), we decompose the regret into two terms: the cost of estimatingθ⋆\\theta^\{\\star\}and the cost of estimatingμ⋆\\mu^\{\\star\}\. We now bound these terms in terms of the problem parameters\.

### D\.1Proof of[Lemma4](https://arxiv.org/html/2608.26755#Thmlemma4)

See[4](https://arxiv.org/html/2608.26755#Thmlemma4)

###### Proof\.

Condition on the eventεθ\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\theta\}, so thatθ⋆∈𝒞tr\\theta^\{\\star\}\\in\{\\mathcal\{C\}\}\_\{t\}^\{r\}for allt∈\[T\]t\\in\[T\]\. Sinceg⁡\(αt⋆\)≥0g\(\\alpha\_\{t\}^\{\\star\}\)\\geq 0, we have

g⁡\(αt⋆\)​⟨Xt,θ⋆⟩\\displaystyle g\(\\alpha\_\{t\}^\{\\star\}\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle≤maxθ∈𝒞tr⁡g⁡\(αt⋆\)​⟨Xt,θ⟩\\displaystyle\\leq\\max\_\{\\theta\\in\{\\mathcal\{C\}\}\_\{t\}^\{r\}\}g\(\\alpha\_\{t\}^\{\\star\}\)\\langle X\_\{t\},\\theta\\rangle≤maxα∈𝒜tf⁡maxθ∈𝒞tr⁡g⁡\(α\)​⟨Xt,θ⟩\\displaystyle\\leq\\max\_\{\\alpha\\in\\mathcal\{A\}\_\{t\}^\{f\}\}\\max\_\{\\theta\\in\{\\mathcal\{C\}\}\_\{t\}^\{r\}\}g\(\\alpha\)\\langle X\_\{t\},\\theta\\rangle=maxα∈𝒜tf⁡g⁡\(α\)​⟨Xt,θ~t⟩\\displaystyle=\\max\_\{\\alpha\\in\\mathcal\{A\}\_\{t\}^\{f\}\}g\(\\alpha\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle=g⁡\(α~t\)​⟨Xt,θ~t⟩\.\\displaystyle=g\(\\tilde\{\\alpha\}\_\{t\}\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle\.Therefore,

\(g⁡\(αt⋆\)−g⁡\(α~t\)\)​⟨Xt,θ⋆⟩≤g⁡\(α~t\)​⟨Xt,θ~t−θ⋆⟩\.\\left\(g\(\\alpha\_\{t\}^\{\\star\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\leq g\(\\tilde\{\\alpha\}\_\{t\}\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\-\\theta^\{\\star\}\\rangle\.∎

### D\.2Proof of[Lemma5](https://arxiv.org/html/2608.26755#Thmlemma5)

See[5](https://arxiv.org/html/2608.26755#Thmlemma5)

###### Proof\.

Let

bδ=κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\),Bt⋆=⟨Xt,μ⋆⟩\+bδ,B~t=⟨Xt,μ~t⟩\+bδ\.b\_\{\\delta\}=\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\},\\qquad B\_\{t\}^\{\\star\}=\\langle X\_\{t\},\\mu^\{\\star\}\\rangle\+b\_\{\\delta\},\\qquad\\widetilde\{B\}\_\{t\}=\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\\rangle\+b\_\{\\delta\}\.On the eventεμ\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mu\}, the pessimistic construction gives

Bt⋆≤B~tB\_\{t\}^\{\\star\}\\leq\\widetilde\{B\}\_\{t\}wheneverBt⋆≥0B\_\{t\}^\{\\star\}\\geq 0\. IfBt⋆<0B\_\{t\}^\{\\star\}<0, then the true feasible set is all of\[0,1\]\[0,1\]\.

Sinceggis strictly increasing, maximizing

g⁡\(α\)​⟨Xt,θ~t⟩g\(\\alpha\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangleover an interval is equivalent to choosing the largest feasible action when⟨Xt,θ~t⟩≥0\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle\\geq 0, and choosingα=0\\alpha=0otherwise\. If⟨Xt,θ~t⟩<0\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle<0, then bothα~t\\tilde\{\\alpha\}\_\{t\}andαt\\alpha\_\{t\}are zero, and the claim is immediate\.

Assume now that⟨Xt,θ~t⟩≥0\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\\rangle\\geq 0\. Define the effective actions

z~t:=g⁡\(α~t\),zt:=g⁡\(αt\)\.\\tilde\{z\}\_\{t\}:=g\(\\tilde\{\\alpha\}\_\{t\}\),\\qquad z\_\{t\}:=g\(\\alpha\_\{t\}\)\.The true and estimated feasible sets in the effective action variable are intervals with upper endpoints

z¯t⋆=\{1,Bt⋆≤0,min⁡\{1,τBt⋆\},Bt⋆\>0,\\bar\{z\}\_\{t\}^\{\\star\}=\\begin\{cases\}1,&B\_\{t\}^\{\\star\}\\leq 0,\\\\\[2\.5pt\] \\min\\left\\\{1,\\dfrac\{\\tau\}\{B\_\{t\}^\{\\star\}\}\\right\\\},&B\_\{t\}^\{\\star\}\>0,\\end\{cases\}and

z^t=\{1,B~t≤0,min⁡\{1,τB~t\},B~t\>0\.\\widehat\{z\}\_\{t\}=\\begin\{cases\}1,&\\widetilde\{B\}\_\{t\}\\leq 0,\\\\\[2\.5pt\] \\min\\left\\\{1,\\dfrac\{\\tau\}\{\\widetilde\{B\}\_\{t\}\}\\right\\\},&\\widetilde\{B\}\_\{t\}\>0\.\\end\{cases\}Thus,

z~t=z¯t⋆,zt=z^t\.\\tilde\{z\}\_\{t\}=\\bar\{z\}\_\{t\}^\{\\star\},\\qquad z\_\{t\}=\\widehat\{z\}\_\{t\}\.
We claim that

z¯t⋆−z^t≤B~t−Bt⋆τ=⟨Xt,μ~t−μ⋆⟩τ\.\\bar\{z\}\_\{t\}^\{\\star\}\-\\widehat\{z\}\_\{t\}\\leq\\frac\{\\widetilde\{B\}\_\{t\}\-B\_\{t\}^\{\\star\}\}\{\\tau\}=\\frac\{\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\rangle\}\{\\tau\}\.
IfBt⋆≤0B\_\{t\}^\{\\star\}\\leq 0, thenz¯t⋆=1\\bar\{z\}\_\{t\}^\{\\star\}=1\. Ifz^t=1\\widehat\{z\}\_\{t\}=1, the claim is trivial\. Otherwise,z^t=τ/B~t\\widehat\{z\}\_\{t\}=\\tau/\\widetilde\{B\}\_\{t\}, which impliesB~t≥τ\\widetilde\{B\}\_\{t\}\\geq\\tau\. Then

1−τB~t=B~t−τB~t≤B~t−Bt⋆τ,1\-\\frac\{\\tau\}\{\\widetilde\{B\}\_\{t\}\}=\\frac\{\\widetilde\{B\}\_\{t\}\-\\tau\}\{\\widetilde\{B\}\_\{t\}\}\\leq\\frac\{\\widetilde\{B\}\_\{t\}\-B\_\{t\}^\{\\star\}\}\{\\tau\},where we usedBt⋆≤0≤τB\_\{t\}^\{\\star\}\\leq 0\\leq\\tauandB~t≥τ\\widetilde\{B\}\_\{t\}\\geq\\tau\.

IfBt⋆\>0B\_\{t\}^\{\\star\}\>0, then by pessimismBt⋆≤B~tB\_\{t\}^\{\\star\}\\leq\\widetilde\{B\}\_\{t\}\. If either upper endpoint equals11, the desired inequality is immediate\. Otherwise,

z¯t⋆−z^t=τBt⋆−τB~t=τ⁡\(B~t−Bt⋆\)Bt⋆​B~t\.\\bar\{z\}\_\{t\}^\{\\star\}\-\\widehat\{z\}\_\{t\}=\\frac\{\\tau\}\{B\_\{t\}^\{\\star\}\}\-\\frac\{\\tau\}\{\\widetilde\{B\}\_\{t\}\}=\\frac\{\\tau\(\\widetilde\{B\}\_\{t\}\-B\_\{t\}^\{\\star\}\)\}\{B\_\{t\}^\{\\star\}\\widetilde\{B\}\_\{t\}\}\.In this subcase both upper endpoints are strictly below11, henceBt⋆≥τB\_\{t\}^\{\\star\}\\geq\\tauandB~t≥τ\\widetilde\{B\}\_\{t\}\\geq\\tau\. Therefore,

z¯t⋆−z^t≤B~t−Bt⋆τ\.\\bar\{z\}\_\{t\}^\{\\star\}\-\\widehat\{z\}\_\{t\}\\leq\\frac\{\\widetilde\{B\}\_\{t\}\-B\_\{t\}^\{\\star\}\}\{\\tau\}\.
Combining the cases gives

g⁡\(α~t\)−g⁡\(αt\)≤⟨Xt,μ~t−μ⋆⟩τ\.g\(\\tilde\{\\alpha\}\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\leq\\frac\{\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\rangle\}\{\\tau\}\.By Cauchy–Schwarz and[Assumptions2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)and[2\.3](https://arxiv.org/html/2608.26755#S2.Thmassum3),

⟨Xt,θ⋆⟩≤‖Xt‖2​‖θ⋆‖2≤κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)\.\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\leq\\left\\lVert X\_\{t\}\\right\\rVert\_\{2\}\\left\\lVert\\theta^\{\\star\}\\right\\rVert\_\{2\}\\leq\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\.Thus,

\(g⁡\(α~t\)−g⁡\(αt\)\)​⟨Xt,θ⋆⟩≤κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)⋅⟨Xt,μ~t−μ⋆⟩τ\.\\left\(g\(\\tilde\{\\alpha\}\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\\leq\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\\cdot\\frac\{\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\rangle\}\{\\tau\}\.∎

### D\.3Proof of[Theorem2](https://arxiv.org/html/2608.26755#Thmthm2)

As usual in linear bandit analysis, we use the elliptic potential lemma\. The only difference is that our algorithm collects informative samples only in rounds for whichg⁡\(αt\)\>0g\(\\alpha\_\{t\}\)\>0\. Since the number of such rounds is at mostTT, the standard bound applies\.

###### Lemma 8\(Elliptic potential lemma\)\.

LetX1,…,XN⁡\(T\)X\_\{1\},\\ldots,X\_\{N\(T\)\}be the contexts collected by[Algorithm1](https://arxiv.org/html/2608.26755#alg1)in rounds withg⁡\(αt\)\>0g\(\\alpha\_\{t\}\)\>0\. For any regularization parameter0<λ<10<\\lambda<1,

∑t=1T‖Xt‖Σt−12≤d​log⁡\(1\+T​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)2d\)\.\\sum\_\{t=1\}^\{T\}\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}^\{2\}\\leq d\\log\\left\(1\+\\frac\{T\\kappa\_\{\\ref\{L\}\}^\{2\}\}\{d\}\\right\)\.

By Cauchy–Schwarz,

∑t=1T‖Xt‖Σt−1≤d​T​log⁡\(1\+T​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)2d\)\.\\sum\_\{t=1\}^\{T\}\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\\leq\\sqrt\{dT\\log\\left\(1\+\\frac\{T\\kappa\_\{\\ref\{L\}\}^\{2\}\}\{d\}\\right\)\}\.
See[2](https://arxiv.org/html/2608.26755#Thmthm2)

###### Proof\.

On the good event,

ℛ𝒞​\(T\)\\displaystyle\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=∑t=1T\(g⁡\(αt⋆\)−g⁡\(α~t\)\)​⟨Xt,θ⋆⟩\+∑t=1T\(g⁡\(α~t\)−g⁡\(αt\)\)​⟨Xt,θ⋆⟩\\displaystyle=\\sum\_\{t=1\}^\{T\}\\left\(g\(\\alpha\_\{t\}^\{\\star\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle\+\\sum\_\{t=1\}^\{T\}\\left\(g\(\\tilde\{\\alpha\}\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\right\)\\langle X\_\{t\},\\theta^\{\\star\}\\rangle≤∑t=1Tg⁡\(α~t\)​⟨Xt,θ~t−θ⋆⟩\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)τ​∑t=1T⟨Xt,μ~t−μ⋆⟩\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}g\(\\tilde\{\\alpha\}\_\{t\}\)\\langle X\_\{t\},\\tilde\{\\theta\}\_\{t\}\-\\theta^\{\\star\}\\rangle\+\\frac\{\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\{\\tau\}\\sum\_\{t=1\}^\{T\}\\langle X\_\{t\},\\tilde\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\rangle≤∑t=1Tg⁡\(α~t\)​‖Xt‖Σt−1​‖θ~t−θ⋆‖Σt\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)τ​∑t=1T‖Xt‖Σt−1​‖μ~t−μ⋆‖Σt\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}g\(\\tilde\{\\alpha\}\_\{t\}\)\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\\left\\lVert\\tilde\{\\theta\}\_\{t\}\-\\theta^\{\\star\}\\right\\rVert\_\{\\Sigma\_\{t\}\}\+\\frac\{\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\{\\tau\}\\sum\_\{t=1\}^\{T\}\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\\left\\lVert\\tilde\{\\mu\}\_\{t\}\-\\mu^\{\\star\}\\right\\rVert\_\{\\Sigma\_\{t\}\}≤2​∑t=1Tβtr​\(δ′/3,d\)​‖Xt‖Σt−1\+2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)τ​∑t=1Tβtc​\(δ′/3,d\)​‖Xt‖Σt−1\\displaystyle\\leq 2\\sum\_\{t=1\}^\{T\}\\beta\_\{t\}^\{r\}\(\\delta^\{\\prime\}/3,d\)\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}\+\\frac\{2\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\{\\tau\}\\sum\_\{t=1\}^\{T\}\\beta\_\{t\}^\{c\}\(\\delta^\{\\prime\}/3,d\)\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}≤2​\(1\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)τ\)​max⁡\{βTr​\(δ′/3,d\),βTc​\(δ′/3,d\)\}​∑t=1T‖Xt‖Σt−1\\displaystyle\\leq 2\\left\(1\+\\frac\{\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\{\\tau\}\\right\)\\max\\\{\\beta\_\{T\}^\{r\}\(\\delta^\{\\prime\}/3,d\),\\beta\_\{T\}^\{c\}\(\\delta^\{\\prime\}/3,d\)\\\}\\sum\_\{t=1\}^\{T\}\\left\\lVert X\_\{t\}\\right\\rVert\_\{\\Sigma\_\{t\}^\{\-1\}\}≤2​\(1\+κ[2\.1](https://arxiv.org/html/2608.26755#S2.Thmassum1)​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)τ\)​max⁡\{βTr​\(δ′/3,d\),βTc​\(δ′/3,d\)\}​d​T​log⁡\(1\+T​κ[2\.2](https://arxiv.org/html/2608.26755#S2.Thmassum2)2d\)\.\\displaystyle\\leq 2\\left\(1\+\\frac\{\\kappa\_\{\\ref\{S\}\}\\kappa\_\{\\ref\{L\}\}\}\{\\tau\}\\right\)\\max\\\{\\beta\_\{T\}^\{r\}\(\\delta^\{\\prime\}/3,d\),\\beta\_\{T\}^\{c\}\(\\delta^\{\\prime\}/3,d\)\\\}\\sqrt\{dT\\log\\left\(1\+\\frac\{T\\kappa\_\{\\ref\{L\}\}^\{2\}\}\{d\}\\right\)\}\.In the third inequality, we usedg⁡\(α~t\)≤1g\(\\tilde\{\\alpha\}\_\{t\}\)\\leq 1and the fact that bothθ~t,θ⋆\\tilde\{\\theta\}\_\{t\},\\theta^\{\\star\}andμ~t,μ⋆\\tilde\{\\mu\}\_\{t\},\\mu^\{\\star\}lie in their corresponding confidence sets\. ∎

## Appendix ENon\-linear Rewards and Costs

### E\.1Concentration for Non\-linear Least Squares

For the non\-linear case, define the informative set

𝒮t=\{s≤t:g⁡\(αs\)\>0\}\.\{\\mathcal\{S\}\}\_\{t\}=\\\{s\\leq t:g\(\\alpha\_\{s\}\)\>0\\\}\.The least\-squares estimators are

θ^t:=arg​minθ∈ℱr∑s∈𝒮t−1\(θ\(Xs\)−Rsg⁡\(αs\)\)2,\\hat\{\\theta\}\_\{t\}:=\\argmin\_\{\\theta\\in\{\\mathcal\{F\}\}^\{r\}\}\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\left\(\\theta\(X\_\{s\}\)\-\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}\\right\)^\{2\},\(24\)and

μ^t:=arg​minμ∈ℱc∑s∈𝒮t−1\(μ\(Xs\)−Csg⁡\(αs\)\)2\.\\hat\{\\mu\}\_\{t\}:=\\argmin\_\{\\mu\\in\{\\mathcal\{F\}\}^\{c\}\}\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\left\(\\mu\(X\_\{s\}\)\-\\frac\{C\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}\\right\)^\{2\}\.\(25\)Wheneverg⁡\(αs\)\>0g\(\\alpha\_\{s\}\)\>0,

Rsg⁡\(αs\)=θ⋆​\(Xs\)\+ξsr,Csg⁡\(αs\)=μ⋆​\(Xs\)\+ξsc\.\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\theta^\{\\star\}\(X\_\{s\}\)\+\\xi\_\{s\}^\{r\},\\qquad\\frac\{C\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\mu^\{\\star\}\(X\_\{s\}\)\+\\xi\_\{s\}^\{c\}\.Thus, after normalization byg⁡\(αs\)g\(\\alpha\_\{s\}\), the regression observations have the same conditionally sub\-Gaussian noise as in the original model\.

For any functionff, define

‖f‖𝒟t=∑s∈𝒮t−1f2​\(Xs\)\.\\left\\lVert f\\right\\rVert\_\{\\mathcal\{D\}\_\{t\}\}=\\sqrt\{\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}f^\{2\}\(X\_\{s\}\)\}\.The confidence sets are

𝒞tr​\(δ′\)\\displaystyle\\mathcal\{C\}^\{r\}\_\{t\}\(\\delta^\{\\prime\}\)=\{θ∈ℱr:‖θ−θ^t‖𝒟t2≤ρr​\(t,δ′\)\},\\displaystyle=\\left\\\{\\theta\\in\{\\mathcal\{F\}\}^\{r\}:\\left\\lVert\\theta\-\\hat\{\\theta\}\_\{t\}\\right\\rVert\_\{\\mathcal\{D\}\_\{t\}\}^\{2\}\\leq\\rho^\{r\}\(t,\\delta^\{\\prime\}\)\\right\\\},\(26\)𝒞tc​\(δ′\)\\displaystyle\\mathcal\{C\}^\{c\}\_\{t\}\(\\delta^\{\\prime\}\)=\{μ∈ℱc:‖μ−μ^t‖𝒟t2≤ρc​\(t,δ′\)\}\.\\displaystyle=\\left\\\{\\mu\\in\{\\mathcal\{F\}\}^\{c\}:\\left\\lVert\\mu\-\\hat\{\\mu\}\_\{t\}\\right\\rVert\_\{\\mathcal\{D\}\_\{t\}\}^\{2\}\\leq\\rho^\{c\}\(t,\\delta^\{\\prime\}\)\\right\\\}\.\(27\)For finite function classes, we take

ρr​\(t,δ′\)=8​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2​log⁡\(\|ℱr\|δ′\),ρc​\(t,δ′\)=8​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2​log⁡\(\|ℱc\|δ′\)\.\\rho^\{r\}\(t,\\delta^\{\\prime\}\)=8\\kappa\_\{\\ref\{Cr\}\}^\{2\}\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{r\}\|\}\{\\delta^\{\\prime\}\}\\right\),\\qquad\\rho^\{c\}\(t,\\delta^\{\\prime\}\)=8\\kappa\_\{\\ref\{Cc\}\}^\{2\}\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{c\}\|\}\{\\delta^\{\\prime\}\}\\right\)\.
###### Lemma 9\.

For any sequence of real\-valued random variables\(Zt\)t≤T\(Z\_\{t\}\)\_\{t\\leq T\}adapted to a filtration\(ℱt\)t≤T\(\\mathcal\{F\}\_\{t\}\)\_\{t\\leq T\}, it holds with probability at least1−δ1\-\\deltathat, for allT′≤TT^\{\\prime\}\\leq T,

∑t=1T′Zt≤∑t=1T′log⁡\(𝔼t−1​\[eZt\]\)\+log⁡\(δ−1\),\\sum\_\{t=1\}^\{T^\{\\prime\}\}Z\_\{t\}\\leq\\sum\_\{t=1\}^\{T^\{\\prime\}\}\\log\\left\(\\mathbb\{E\}\_\{t\-1\}\\left\[e^\{Z\_\{t\}\}\\right\]\\right\)\+\\log\(\\delta^\{\-1\}\),where𝔼t−1\[⋅\]=𝔼\[⋅∣ℱt−1\]\\mathbb\{E\}\_\{t\-1\}\[\\cdot\]=\\mathbb\{E\}\[\\cdot\\mid\\mathcal\{F\}\_\{t\-1\}\]\.

###### Proof\.

Define

Mτ=exp⁡\(∑t=1τZt−∑t=1τlog⁡\(𝔼t−1​\[eZt\]\)\)\.M\_\{\\tau\}=\\exp\\left\(\\sum\_\{t=1\}^\{\\tau\}Z\_\{t\}\-\\sum\_\{t=1\}^\{\\tau\}\\log\\left\(\\mathbb\{E\}\_\{t\-1\}\\left\[e^\{Z\_\{t\}\}\\right\]\\right\)\\right\)\.Then\(Mτ\)τ≤T\(M\_\{\\tau\}\)\_\{\\tau\\leq T\}is a nonnegative martingale withM0=1M\_\{0\}=1\. Ville’s inequality gives

ℙ\(∃τ≤T:Mτ\>1δ\)≤δ\.\\mathbb\{P\}\\left\(\\exists\\tau\\leq T:M\_\{\\tau\}\>\\frac\{1\}\{\\delta\}\\right\)\\leq\\delta\.Taking logarithms and complements yields the claim\. ∎

###### Proposition 3\.

For any fixedη∈ℝ\\eta\\in\\mathbb\{R\}, with probability at least1−δ1\-\\delta, for allθ∈ℱr\\theta\\in\{\\mathcal\{F\}\}^\{r\}and allT′≤TT^\{\\prime\}\\leq T,

η​∑t=1T′ξtr​\(θ⋆​\(Xt\)−θ⁡\(Xt\)\)≤η2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)22​∑t=1T′\(θ⋆​\(Xt\)−θ⁡\(Xt\)\)2\+log⁡\(\|ℱr\|δ\)\.\\eta\\sum\_\{t=1\}^\{T^\{\\prime\}\}\\xi\_\{t\}^\{r\}\\left\(\\theta^\{\\star\}\(X\_\{t\}\)\-\\theta\(X\_\{t\}\)\\right\)\\leq\\frac\{\\eta^\{2\}\\kappa\_\{\\ref\{Cr\}\}^\{2\}\}\{2\}\\sum\_\{t=1\}^\{T^\{\\prime\}\}\\left\(\\theta^\{\\star\}\(X\_\{t\}\)\-\\theta\(X\_\{t\}\)\\right\)^\{2\}\+\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{r\}\|\}\{\\delta\}\\right\)\.Similarly, with probability at least1−δ1\-\\delta, for allμ∈ℱc\\mu\\in\{\\mathcal\{F\}\}^\{c\}and allT′≤TT^\{\\prime\}\\leq T,

η​∑t=1T′ξtc​\(μ⋆​\(Xt\)−μ⁡\(Xt\)\)≤η2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)22​∑t=1T′\(μ⋆​\(Xt\)−μ⁡\(Xt\)\)2\+log⁡\(\|ℱc\|δ\)\.\\eta\\sum\_\{t=1\}^\{T^\{\\prime\}\}\\xi\_\{t\}^\{c\}\\left\(\\mu^\{\\star\}\(X\_\{t\}\)\-\\mu\(X\_\{t\}\)\\right\)\\leq\\frac\{\\eta^\{2\}\\kappa\_\{\\ref\{Cc\}\}^\{2\}\}\{2\}\\sum\_\{t=1\}^\{T^\{\\prime\}\}\\left\(\\mu^\{\\star\}\(X\_\{t\}\)\-\\mu\(X\_\{t\}\)\\right\)^\{2\}\+\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{c\}\|\}\{\\delta\}\\right\)\.

###### Proof\.

Fixθ∈ℱr\\theta\\in\{\\mathcal\{F\}\}^\{r\}and apply[Lemma9](https://arxiv.org/html/2608.26755#Thmlemma9)with

Zt=η​ξtr​\(θ⋆​\(Xt\)−θ⁡\(Xt\)\)\.Z\_\{t\}=\\eta\\xi\_\{t\}^\{r\}\\left\(\\theta^\{\\star\}\(X\_\{t\}\)\-\\theta\(X\_\{t\}\)\\right\)\.By conditional sub\-Gaussianity,

log⁡𝔼t−1​\[eZt\]≤η2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)22​\(θ⋆​\(Xt\)−θ⁡\(Xt\)\)2\.\\log\\mathbb\{E\}\_\{t\-1\}\\left\[e^\{Z\_\{t\}\}\\right\]\\leq\\frac\{\\eta^\{2\}\\kappa\_\{\\ref\{Cr\}\}^\{2\}\}\{2\}\\left\(\\theta^\{\\star\}\(X\_\{t\}\)\-\\theta\(X\_\{t\}\)\\right\)^\{2\}\.Thus, for this fixedθ\\theta, the desired inequality holds with probability at least1−δ1\-\\delta\. A union bound overθ∈ℱr\\theta\\in\{\\mathcal\{F\}\}^\{r\}gives the stated reward result\. The cost result is identical, replacingθ\\thetabyμ\\muandκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cr\}\}byκ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)\\kappa\_\{\\ref\{Cc\}\}\. ∎

###### Lemma 10\(Concentration for non\-linear rewards and costs\)\.

Letδ′∈\(0,1\)\\delta^\{\\prime\}\\in\(0,1\)\. With probability at least1−2​δ′1\-2\\delta^\{\\prime\}, for allt≤Tt\\leq T,

θ⋆∈𝒞tr​\(δ′\),μ⋆∈𝒞tc​\(δ′\)\.\\theta^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\),\\qquad\\mu^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)\.

###### Proof\.

We prove the reward statement; the cost statement is identical\. By the definition ofθ^t\\hat\{\\theta\}\_\{t\}as a least\-squares estimator,

∑s∈𝒮t−1\(θ^t​\(Xs\)−Rsg⁡\(αs\)\)2≤∑s∈𝒮t−1\(θ⋆​\(Xs\)−Rsg⁡\(αs\)\)2\.\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\left\(\\hat\{\\theta\}\_\{t\}\(X\_\{s\}\)\-\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}\\right\)^\{2\}\\leq\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\left\(\\theta^\{\\star\}\(X\_\{s\}\)\-\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}\\right\)^\{2\}\.Since

Rsg⁡\(αs\)=θ⋆​\(Xs\)\+ξsr,\\frac\{R\_\{s\}\}\{g\(\\alpha\_\{s\}\)\}=\\theta^\{\\star\}\(X\_\{s\}\)\+\\xi\_\{s\}^\{r\},this implies

∑s∈𝒮t−1\(θ^t​\(Xs\)−θ⋆​\(Xs\)\)2≤2​∑s∈𝒮t−1ξsr​\(θ^t​\(Xs\)−θ⋆​\(Xs\)\)\.\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\left\(\\hat\{\\theta\}\_\{t\}\(X\_\{s\}\)\-\\theta^\{\\star\}\(X\_\{s\}\)\\right\)^\{2\}\\leq 2\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\xi\_\{s\}^\{r\}\\left\(\\hat\{\\theta\}\_\{t\}\(X\_\{s\}\)\-\\theta^\{\\star\}\(X\_\{s\}\)\\right\)\.Applying[Proposition3](https://arxiv.org/html/2608.26755#Thmproposition3)withθ=θ^t\\theta=\\hat\{\\theta\}\_\{t\}and choosingη=1/\(2​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2\)\\eta=1/\(2\\kappa\_\{\\ref\{Cr\}\}^\{2\}\)yields

∑s∈𝒮t−1\(θ^t​\(Xs\)−θ⋆​\(Xs\)\)2≤8​κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)2​log⁡\(\|ℱr\|δ′\)\.\\sum\_\{s\\in\{\\mathcal\{S\}\}\_\{t\-1\}\}\\left\(\\hat\{\\theta\}\_\{t\}\(X\_\{s\}\)\-\\theta^\{\\star\}\(X\_\{s\}\)\\right\)^\{2\}\\leq 8\\kappa\_\{\\ref\{Cr\}\}^\{2\}\\log\\left\(\\frac\{\|\{\\mathcal\{F\}\}^\{r\}\|\}\{\\delta^\{\\prime\}\}\\right\)\.Thusθ⋆∈𝒞tr​\(δ′\)\\theta^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\)\. The same argument givesμ⋆∈𝒞tc​\(δ′\)\\mu^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\)\. A union bound gives probability at least1−2​δ′1\-2\\delta^\{\\prime\}\. ∎

### E\.2Non\-linear Regret Analysis

Define the nonlinear good event

εnl:=\{θ⋆∈𝒞tr\(δ′\),μ⋆∈𝒞tc\(δ′\),𝒜^tf⊆𝒜tf,∀t∈\[T\]\}\.\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mathrm\{nl\}\}:=\\left\\\{\\theta^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{r\}\(\\delta^\{\\prime\}\),\\;\\mu^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{c\}\(\\delta^\{\\prime\}\),\\;\\hat\{\\mathcal\{A\}\}\_\{t\}^\{f\}\\subseteq\\mathcal\{A\}\_\{t\}^\{f\},\\;\\forall t\\in\[T\]\\right\\\}\.By the preceding concentration result and the same feasible\-set argument as in[Lemma2](https://arxiv.org/html/2608.26755#Thmlemma2),

ℙ⁡\(εnl\)≥1−3​δ′\.\\mathbb\{P\}\(\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mathrm\{nl\}\}\)\\geq 1\-3\\delta^\{\\prime\}\.
For a subsetℱ~⊆ℱ\\widetilde\{\{\\mathcal\{F\}\}\}\\subseteq\{\\mathcal\{F\}\}, recall the confidence width

wℱ~​\(X\)=supf¯,f¯∈ℱ~\(f¯​\(X\)−f¯​\(X\)\)\.w\_\{\\widetilde\{\{\\mathcal\{F\}\}\}\}\(X\)=\\sup\_\{\\underline\{f\},\\overline\{f\}\\in\\widetilde\{\{\\mathcal\{F\}\}\}\}\\left\(\\overline\{f\}\(X\)\-\\underline\{f\}\(X\)\\right\)\.
###### Lemma 11\.

Under the nonlinear good eventεnl\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mathrm\{nl\}\},

∑t=1T\[g⁡\(αt⋆\)​θ⋆​\(Xt\)−g⁡\(α~t\)​θ⋆​\(Xt\)\]≤∑t=1Tw𝒞tr​\(Xt\)\.\\sum\_\{t=1\}^\{T\}\\left\[g\(\\alpha\_\{t\}^\{\\star\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\right\]\\leq\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}^\{r\}\}\(X\_\{t\}\)\.

###### Proof\.

For eachtt, sinceθ⋆∈𝒞tr\\theta^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{r\}andg⁡\(αt⋆\)≥0g\(\\alpha\_\{t\}^\{\\star\}\)\\geq 0,

g⁡\(αt⋆\)​θ⋆​\(Xt\)\\displaystyle g\(\\alpha\_\{t\}^\{\\star\}\)\\theta^\{\\star\}\(X\_\{t\}\)≤maxθ∈𝒞tr⁡g⁡\(αt⋆\)​θ​\(Xt\)\\displaystyle\\leq\\max\_\{\\theta\\in\\mathcal\{C\}\_\{t\}^\{r\}\}g\(\\alpha\_\{t\}^\{\\star\}\)\\theta\(X\_\{t\}\)≤maxα∈𝒜tf⁡maxθ∈𝒞tr⁡g⁡\(α\)​θ​\(Xt\)\\displaystyle\\leq\\max\_\{\\alpha\\in\\mathcal\{A\}\_\{t\}^\{f\}\}\\max\_\{\\theta\\in\\mathcal\{C\}\_\{t\}^\{r\}\}g\(\\alpha\)\\theta\(X\_\{t\}\)=g⁡\(α~t\)​θ~t​\(Xt\)\.\\displaystyle=g\(\\tilde\{\\alpha\}\_\{t\}\)\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)\.Therefore,

g⁡\(αt⋆\)​θ⋆​\(Xt\)−g⁡\(α~t\)​θ⋆​\(Xt\)≤g⁡\(α~t\)​\(θ~t​\(Xt\)−θ⋆​\(Xt\)\)\.g\(\\alpha\_\{t\}^\{\\star\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\leq g\(\\tilde\{\\alpha\}\_\{t\}\)\\left\(\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)\-\\theta^\{\\star\}\(X\_\{t\}\)\\right\)\.Sinceg⁡\(α~t\)≤1g\(\\tilde\{\\alpha\}\_\{t\}\)\\leq 1and bothθ~t,θ⋆∈𝒞tr\\tilde\{\\theta\}\_\{t\},\\theta^\{\\star\}\\in\\mathcal\{C\}\_\{t\}^\{r\},

g⁡\(α~t\)​\(θ~t​\(Xt\)−θ⋆​\(Xt\)\)≤w𝒞tr​\(Xt\)\.g\(\\tilde\{\\alpha\}\_\{t\}\)\\left\(\\tilde\{\\theta\}\_\{t\}\(X\_\{t\}\)\-\\theta^\{\\star\}\(X\_\{t\}\)\\right\)\\leq w\_\{\\mathcal\{C\}\_\{t\}^\{r\}\}\(X\_\{t\}\)\.Summing overttproves the claim\. ∎

###### Lemma 12\.

Under the nonlinear good eventεnl\\scalebox\{1\.5\}\{$\\varepsilon$\}\_\{\\mathrm\{nl\}\},

∑t=1T\[g⁡\(α~t\)​θ⋆​\(Xt\)−g⁡\(αt\)​θ⋆​\(Xt\)\]≤1τ​∑t=1Tw𝒞tc​\(Xt\)\.\\sum\_\{t=1\}^\{T\}\\left\[g\(\\tilde\{\\alpha\}\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\right\]\\leq\\frac\{1\}\{\\tau\}\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}^\{c\}\}\(X\_\{t\}\)\.

###### Proof\.

Fix a roundttand define

bδ=κ[2\.1](https://arxiv.org/html/2608.26755#S2.SS1)​2​log⁡\(1δ\),Bt⋆=μ⋆​\(Xt\)\+bδ,B~t=μ~t​\(Xt\)\+bδ\.b\_\{\\delta\}=\\kappa\_\{\\ref\{Cc\}\}\\sqrt\{2\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\},\\qquad B\_\{t\}^\{\\star\}=\\mu^\{\\star\}\(X\_\{t\}\)\+b\_\{\\delta\},\\qquad\\widetilde\{B\}\_\{t\}=\\tilde\{\\mu\}\_\{t\}\(X\_\{t\}\)\+b\_\{\\delta\}\.By construction of the pessimistic cost estimate and on the good event,

Bt⋆≤B~tB\_\{t\}^\{\\star\}\\leq\\widetilde\{B\}\_\{t\}wheneverBt⋆≥0B\_\{t\}^\{\\star\}\\geq 0\.

If the optimistic reward estimate atXtX\_\{t\}is negative, then bothα~t\\tilde\{\\alpha\}\_\{t\}andαt\\alpha\_\{t\}are zero, and the contribution to regret is nonpositive\. We therefore consider the case where the optimistic reward estimate is nonnegative\. Sinceggis strictly increasing, the selected actions correspond to the largest feasible effective actions\.

Let

z~t=g⁡\(α~t\),zt=g⁡\(αt\)\.\\tilde\{z\}\_\{t\}=g\(\\tilde\{\\alpha\}\_\{t\}\),\\qquad z\_\{t\}=g\(\\alpha\_\{t\}\)\.The true and estimated safe effective\-action upper endpoints are

z¯t⋆=\{1,Bt⋆≤0,min⁡\{1,τBt⋆\},Bt⋆\>0,\\bar\{z\}\_\{t\}^\{\\star\}=\\begin\{cases\}1,&B\_\{t\}^\{\\star\}\\leq 0,\\\\\[2\.5pt\] \\min\\left\\\{1,\\dfrac\{\\tau\}\{B\_\{t\}^\{\\star\}\}\\right\\\},&B\_\{t\}^\{\\star\}\>0,\\end\{cases\}and

z^t=\{1,B~t≤0,min⁡\{1,τB~t\},B~t\>0\.\\widehat\{z\}\_\{t\}=\\begin\{cases\}1,&\\widetilde\{B\}\_\{t\}\\leq 0,\\\\\[2\.5pt\] \\min\\left\\\{1,\\dfrac\{\\tau\}\{\\widetilde\{B\}\_\{t\}\}\\right\\\},&\\widetilde\{B\}\_\{t\}\>0\.\\end\{cases\}Thus,

z~t=z¯t⋆,zt=z^t\.\\tilde\{z\}\_\{t\}=\\bar\{z\}\_\{t\}^\{\\star\},\\qquad z\_\{t\}=\\widehat\{z\}\_\{t\}\.The same endpoint calculation as in[Lemma5](https://arxiv.org/html/2608.26755#Thmlemma5)gives

g⁡\(α~t\)−g⁡\(αt\)=z~t−zt≤B~t−Bt⋆τ=μ~t​\(Xt\)−μ⋆​\(Xt\)τ\.g\(\\tilde\{\\alpha\}\_\{t\}\)\-g\(\\alpha\_\{t\}\)=\\tilde\{z\}\_\{t\}\-z\_\{t\}\\leq\\frac\{\\widetilde\{B\}\_\{t\}\-B\_\{t\}^\{\\star\}\}\{\\tau\}=\\frac\{\\tilde\{\\mu\}\_\{t\}\(X\_\{t\}\)\-\\mu^\{\\star\}\(X\_\{t\}\)\}\{\\tau\}\.Sinceθ⋆​\(Xt\)≤1\\theta^\{\\star\}\(X\_\{t\}\)\\leq 1by boundedness,

g⁡\(α~t\)​θ⋆​\(Xt\)−g⁡\(αt\)​θ⋆​\(Xt\)≤μ~t​\(Xt\)−μ⋆​\(Xt\)τ\.g\(\\tilde\{\\alpha\}\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\leq\\frac\{\\tilde\{\\mu\}\_\{t\}\(X\_\{t\}\)\-\\mu^\{\\star\}\(X\_\{t\}\)\}\{\\tau\}\.Finally, bothμ~t\\tilde\{\\mu\}\_\{t\}andμ⋆\\mu^\{\\star\}belong to𝒞tc\\mathcal\{C\}\_\{t\}^\{c\}on the good event, so

μ~t​\(Xt\)−μ⋆​\(Xt\)≤w𝒞tc​\(Xt\)\.\\tilde\{\\mu\}\_\{t\}\(X\_\{t\}\)\-\\mu^\{\\star\}\(X\_\{t\}\)\\leq w\_\{\\mathcal\{C\}\_\{t\}^\{c\}\}\(X\_\{t\}\)\.Summing overttgives the result\. ∎

###### Lemma 13\(Eluder\-dimension width bound\)\.

Letℱ\\mathcal\{F\}be a function class with eluder dimensiondeluder=deluder​\(ℱ,1/T2\)d\_\{\\mathrm\{eluder\}\}=d\_\{\\mathrm\{eluder\}\}\(\\mathcal\{F\},1/T^\{2\}\), and let𝒞t\\mathcal\{C\}\_\{t\}be confidence sets with radiusρ⁡\(T,δ′\)\\rho\(T,\\delta^\{\\prime\}\)\. Then

∑t=1Tw𝒞t​\(Xt\)=𝒪⁡\(deluder​T​ρ​\(T,δ′\)\)\.\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}\}\(X\_\{t\}\)=\\mathcal\{O\}\\left\(\\sqrt\{d\_\{\\mathrm\{eluder\}\}T\\rho\(T,\\delta^\{\\prime\}\)\}\\right\)\.

### E\.3Proof of[Theorem3](https://arxiv.org/html/2608.26755#Thmthm3)

See[3](https://arxiv.org/html/2608.26755#Thmthm3)

###### Proof\.

Using[Lemmas11](https://arxiv.org/html/2608.26755#Thmlemma11)and[12](https://arxiv.org/html/2608.26755#Thmlemma12), we have

ℛ𝒞​\(T\)\\displaystyle\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=∑t=1T\[g⁡\(αt⋆\)​θ⋆​\(Xt\)−g⁡\(α~t\)​θ⋆​\(Xt\)\]\+∑t=1T\[g⁡\(α~t\)​θ⋆​\(Xt\)−g⁡\(αt\)​θ⋆​\(Xt\)\]\\displaystyle=\\sum\_\{t=1\}^\{T\}\\left\[g\(\\alpha\_\{t\}^\{\\star\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\tilde\{\\alpha\}\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\right\]\+\\sum\_\{t=1\}^\{T\}\\left\[g\(\\tilde\{\\alpha\}\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\-g\(\\alpha\_\{t\}\)\\theta^\{\\star\}\(X\_\{t\}\)\\right\]≤∑t=1Tw𝒞tr​\(Xt\)\+1τ​∑t=1Tw𝒞tc​\(Xt\)\.\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}^\{r\}\}\(X\_\{t\}\)\+\\frac\{1\}\{\\tau\}\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}^\{c\}\}\(X\_\{t\}\)\.Applying[Lemma13](https://arxiv.org/html/2608.26755#Thmlemma13)to the reward and cost confidence classes gives

∑t=1Tw𝒞tr​\(Xt\)=𝒪⁡\(deluderr​T​ρr​\(T,δ′/3\)\),\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}^\{r\}\}\(X\_\{t\}\)=\\mathcal\{O\}\\left\(\\sqrt\{d^\{r\}\_\{\\mathrm\{eluder\}\}T\\rho^\{r\}\(T,\\delta^\{\\prime\}/3\)\}\\right\),and

∑t=1Tw𝒞tc​\(Xt\)=𝒪⁡\(deluderc​T​ρc​\(T,δ′/3\)\)\.\\sum\_\{t=1\}^\{T\}w\_\{\\mathcal\{C\}\_\{t\}^\{c\}\}\(X\_\{t\}\)=\\mathcal\{O\}\\left\(\\sqrt\{d^\{c\}\_\{\\mathrm\{eluder\}\}T\\rho^\{c\}\(T,\\delta^\{\\prime\}/3\)\}\\right\)\.Therefore,

ℛ𝒞​\(T\)=𝒪⁡\(deluderr​T​ρr​\(T,δ′/3\)\+1τ​deluderc​T​ρc​\(T,δ′/3\)\)\.\\mathcal\{R\}\_\{\\mathcal\{C\}\}\(T\)=\\mathcal\{O\}\\left\(\\sqrt\{d^\{r\}\_\{\\mathrm\{eluder\}\}T\\rho^\{r\}\(T,\\delta^\{\\prime\}/3\)\}\+\\frac\{1\}\{\\tau\}\\sqrt\{d^\{c\}\_\{\\mathrm\{eluder\}\}T\\rho^\{c\}\(T,\\delta^\{\\prime\}/3\)\}\\right\)\.∎