Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

# Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
Source: [https://arxiv.org/html/2608.11383](https://arxiv.org/html/2608.11383)
###### Abstract

We study new algorithms for Contextual Bandits with Knapsack\. In these problems, there are finitely many types of customers, products, and resources\. Each product is made from a fixed combination of resources, and resources have finite capacity\. A decision maker must assign each arriving customer one out of a set of multiple possible products\. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term\. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function\. We propose a natural and simple extension of the Upper\-Confidence\-Bound \(UCB\) family of algorithms and apply re\-optimization techniques\. We show that by taking advantage of re\-optimization, our algorithm achieves an average regret ofO⁡\(\(ln⁡T\)3T\)O\(\\frac\{\(\\ln T\)^\{3\}\}\{T\}\)whereTTis the horizon length\. Our bound significantly reduces theO⁡\(1T\)O\(\\frac\{1\}\{\\sqrt\{T\}\}\)bound in the literature for closely related dynamic\-pricing problems that are based on re\-optimization\.

Keywords:Revenue Management; Approximation Algorithms; Machine Learning; Regret analysis \.

## 1Introduction

Digital platforms increasingly act as central matchmakers between heterogeneous demand and capacity\-constrained supply\. Consider a ride\-hailing platform or an online advertising exchange: each day, the platform must assign millions of requests \(e\.g\., riders, impressions\) to a limited pool of resources \(e\.g\., driver hours, advertiser budgets\)\. The platform must make these assignment decisions in real time, yet the revenue generated by each match is rarely known in advance\. Instead, it depends on complex, unobserved interactions between user characteristics and product attributes, forcing the platform to learn these values on the fly\.

Crucially, every assignment consumes scarce resources\. The platform cannot blindly explore highly uncertain matches simply to learn their value, because allocating a limited resource to a suboptimal request today prevents its use for a highly profitable opportunity tomorrow\. This creates an inherently coupled exploration\-exploitation tradeoff tightly bound by physical or financial capacities: the platform must learn the value of different matches while meticulously pacing its limited resources over the entire time horizon\.

The Contextual Bandits with Knapsacks \(CBwK\) framework provides a natural mathematical abstraction for this “learning\-while\-allocating” challenge\([Badanidiyuru et al\. 2018](https://arxiv.org/html/2608.11383#bib.bib9),[Agrawal and Devanur 2016](https://arxiv.org/html/2608.11383#bib.bib3)\)\. In a standard CBwK model, the decision maker observes a context, selects an action, and subsequently receives both a stochastic reward and a stochastic consumption of resources\. While theoretically expressive, classical CBwK algorithms often assume that resource consumptions are entirely unknown and drawn from general distributions\. This requires computationally heavy estimation techniques that struggle to meet the millisecond\-level latency requirements of modern platforms\. In reality, platform operators typically know exactly how much budget an impression will deduct, or how much capacity a specific task will require, at the exact moment of allocation\.

Motivated by this operational reality, we focus on a structured, highly practical variation of the problem: a contextual bandit setting where the resource consumption of each action is fixed and known, but the rewards remain an unknown linear function of the contexts\. The objective is to jointly learn the mean reward function and make online assignment decisions to minimize expected revenue loss relative to an optimal full\-information policy\. Customers arriving at the platform act as the contexts, while the assignable products or services serve as the arms\.

To solve this, we bridge bandit learning with classical network revenue management by proposing a UCB\-guided linear programming \(LP\) re\-solving heuristic\. By periodically re\-optimizing a fluid LP that is updated with the upper confidence bounds of the unknown reward parameters, our algorithm explicitly captures the opportunity cost of capacity via time\-varying dual shadow prices\.

This approach contributes to the existing literature in two primary ways\. First, by exploiting the specific structure of known consumptions paired with unknown linear rewards, we develop an algorithm that is computationally tractable and tailored for high\-frequency resource allocation\. Second, we provide rigorous theoretical guarantees for this re\-solving approach\. We prove that our algorithm achieves an average regret ofO⁡\(ln3⁡\(T\)T\)O\(\\frac\{\\ln^\{3\}\(T\)\}\{T\}\), whereTTis the horizon length\. This fast rate significantly improves upon theO⁡\(1T\)O\(\\frac\{1\}\{\\sqrt\{T\}\}\)orO⁡\(ln⁡\(T\)T\)O\(\\sqrt\{\\frac\{\\ln\(T\)\}\{T\}\}\)bounds prevalent in the existing CBwK and dynamic\-pricing literature\. To put this theoretical contribution into perspective, Table[1](https://arxiv.org/html/2608.11383#S1.T1)summarizes how our structural assumptions and algorithmic design compare to related bounds in the CBwK literature\.

Table 1:Comparison of regret bounds in the CBwK literature under proportional capacity scaling\.
## 2Literature Review

Our problem setup and algorithmic design connect several active streams of research in operations research and computer science, specifically multi\-armed bandits, contextual learning, and network revenue management\.

### 2\.1Bandits and Contextual Learning

The fundamental conflict between taking actions for immediate payoff versus long\-term informational gain is formalized in the multi\-armed bandits \(MAB\) literature\([Thompson 1933](https://arxiv.org/html/2608.11383#bib.bib35),[Whittle 2018](https://arxiv.org/html/2608.11383#bib.bib37),[Jones 1989](https://arxiv.org/html/2608.11383#bib.bib24),[Mahajan and Teneketzis 2008](https://arxiv.org/html/2608.11383#bib.bib28)\)\.[Slivkins 2019](https://arxiv.org/html/2608.11383#bib.bib32)provides a comprehensive overview of this vast field\.

To model the relationship between observed contexts and outcomes, the contextual bandits \(CB\) literature typically divides into agnostic and realizability\-based approaches\. Agnostic models avoid assumptions about the underlying context\-outcome relationship, attempting instead to compete with the best policy in a given class\([Auer 2003](https://arxiv.org/html/2608.11383#bib.bib7),[Dudik et al\. 2011](https://arxiv.org/html/2608.11383#bib.bib15),[Agrawal and Devanur 2014](https://arxiv.org/html/2608.11383#bib.bib2)\)\. However, these approaches often require complex cost\-sensitive classification oracles to maintain computational efficiency\([Li et al\. 2010](https://arxiv.org/html/2608.11383#bib.bib27)\)\. Alternatively, realizability\-based approaches assume the outcome distribution follows a known function class\. When this relationship is linear, optimal regret bounds can be achieved using UCB\-type algorithms\([Abbasi\-Yadkori et al\. 2011](https://arxiv.org/html/2608.11383#bib.bib1),[Chu et al\. 2011](https://arxiv.org/html/2608.11383#bib.bib14)\)\. While fundamental, these standard CB models abstract away the budget and capacity constraints that are critical to physical and financial operations\.

### 2\.2Contextual Bandits with Knapsacks \(CBwK\)

To capture the presence of finite resources,[Badanidiyuru et al\. 2018](https://arxiv.org/html/2608.11383#bib.bib9)introduced the bandits with knapsacks \(BwK\) framework, which has since been applied to dynamic pricing\([Besbes and Zeevi 2012](https://arxiv.org/html/2608.11383#bib.bib11)\), the Adwords problem\([Mehta et al\. 2007](https://arxiv.org/html/2608.11383#bib.bib29)\), and display advertising\([Edwards and Leslie 2020](https://arxiv.org/html/2608.11383#bib.bib16)\)\.

Extending BwK to include contextual information naturally led to the CBwK framework\. In the agnostic setting, researchers have generalized classical techniques to accommodate knapsack constraints\([Badanidiyuru et al\. 2014](https://arxiv.org/html/2608.11383#bib.bib10),[Agrawal et al\. 2016](https://arxiv.org/html/2608.11383#bib.bib4)\)\. Yet, as[Agrawal and Devanur 2016](https://arxiv.org/html/2608.11383#bib.bib3)demonstrate, relying on classification oracles in an agnostic CBwK setting can be NP\-hard even for linear cases\. Consequently, significant focus has shifted to linear realizability assumptions\. By leveraging confidence ellipsoids,[Agrawal and Devanur 2016](https://arxiv.org/html/2608.11383#bib.bib3)developed near\-optimal algorithms for stochastic linear CBwK, while[Slivkins and Foster 2022](https://arxiv.org/html/2608.11383#bib.bib33)recently extended these ideas to smoothed contextual settings where contexts are subject to Gaussian perturbation\.

Other works provide bounds tailored to different operational assumptions\. For example,[Flajolet and Jaillet 2015](https://arxiv.org/html/2608.11383#bib.bib18)prove regret bounds that are logarithmic in the horizon but exponential in the number of resources, while[Immorlica et al\. 2019](https://arxiv.org/html/2608.11383#bib.bib21)establish anO⁡\(ln⁡T\)O\(\\ln T\)competitive ratio under adversarial arrivals\. For dynamic pricing with unknown demand functions,[Ferreira et al\. 2018](https://arxiv.org/html/2608.11383#bib.bib17)analyze a Thompson sampling\-based algorithm yielding anO⁡\(T\)O\(\\sqrt\{T\}\)average regret\. In contrast to these settings, the primary learning target in our model is the reward distribution, structured linearly over contexts, which allows us to achieve much faster convergence rates by exploiting known resource consumption matrices\.

### 2\.3Network Revenue Management and Re\-Solving Heuristics

From an operations perspective, our setting is a direct extension of the network revenue management \(NRM\) problem\([Gallego and van Ryzin 1994](https://arxiv.org/html/2608.11383#bib.bib19),[Gallego and van Ryzin 1997](https://arxiv.org/html/2608.11383#bib.bib20)\)\. NRM typically models dynamic resource allocation under capacity constraints, scaled asymptotically by a factor ofTTto represent growing market sizes with constant resource scarcity\([Talluri and Ryzin 2004](https://arxiv.org/html/2608.11383#bib.bib34)\)\.

Because exact solutions suffer from the curse of dimensionality, a widely used heuristic is the deterministic linear programming \(DLP\) approximation, which replaces stochastic arrivals with their expectations\. Under this scaling, static DLP\-based policies suffer anO⁡\(T\)O\(\\sqrt\{T\}\)revenue loss\([Gallego and van Ryzin 1994](https://arxiv.org/html/2608.11383#bib.bib19)\)\. To incorporate information revealed over time and address stochastic drift, practitioners often re\-optimize the DLP periodically using remaining capacities\.[Reiman and Wang 2008](https://arxiv.org/html/2608.11383#bib.bib31)show that a single endogenously timed re\-solving step using probabilistic allocation drops the revenue loss too⁡\(T\)o\(\\sqrt\{T\}\)\. Further,[Jasin and Kumar 2012](https://arxiv.org/html/2608.11383#bib.bib23)prove that frequent, periodic re\-solving yields anO⁡\(1\)O\(1\)revenue loss when demand distributions are fully known\. When demand must be learned,[Jasin 2014](https://arxiv.org/html/2608.11383#bib.bib22)and[Chen and Ross 2014](https://arxiv.org/html/2608.11383#bib.bib12)propose re\-solving algorithms withO⁡\(ln⁡T\)O\(\\ln\{T\}\)revenue loss\.

Our work also touches upon online knapsack and secretary problems\([Kleywegt and Papastavrou 1998](https://arxiv.org/html/2608.11383#bib.bib26),[Kleinberg 2005](https://arxiv.org/html/2608.11383#bib.bib25),[Babaioff et al\. 2007](https://arxiv.org/html/2608.11383#bib.bib8),[Arlotto and Gurvich 2019](https://arxiv.org/html/2608.11383#bib.bib5),[Arlotto and Xie 2020](https://arxiv.org/html/2608.11383#bib.bib6)\)\. Notably,[Vera et al\. 2021](https://arxiv.org/html/2608.11383#bib.bib36)recently developed a re\-optimization framework for single\-resource stochastic allocation, achievingO⁡\(1T\)O\(\\frac\{1\}\{T\}\)regret for online probing andO⁡\(ln⁡\(T\)T\)O\(\\frac\{\\ln\(T\)\}\{T\}\)for distribution\-agnostic knapsacks\. Our approach extends this operational philosophy—frequent, LP\-based re\-optimization—into the multi\-resource contextual bandit environment, demonstrating that maintaining tight pacing control via shadow prices is critical for overcoming the standardT\\sqrt\{T\}exploration penalty\.

### 2\.4Paper Organization

The paper is organized as follows\. After the introduction and literature review in §[1](https://arxiv.org/html/2608.11383#S1), we describe our model and settings in §[3](https://arxiv.org/html/2608.11383#S3)\. In §[4](https://arxiv.org/html/2608.11383#S4), we introduce the re\-optimization idea and propose a re\-solving based online learning algorithms\. Furthermore, in §[4\.3](https://arxiv.org/html/2608.11383#S4.SS3)we also establish an LP optimization as an benchmark for any online algorithms\. In §[5](https://arxiv.org/html/2608.11383#S5), we explain why our main ideas work well by introducing an expected capacity deviation analysis\. Then in §[6](https://arxiv.org/html/2608.11383#S6), we analyze and bound the regret for our reoptimization algorithm\. In §[7](https://arxiv.org/html/2608.11383#S7), we conduct a numerical to highlight the significance of re\-solving in guaranteeing logarithmic bound performance\. Finally, the paper concludes in §[8](https://arxiv.org/html/2608.11383#S8), and all the proofs can be found in the appendix\.

## 3Model

Consider a finite horizon indexed bytt,t=1,2,…,Tt=1,2,\\ldots,T\. There is a finite set of*resources*indexed byk=1,…,Kk=1,\\ldots,Kthat are not replenished over the horizon\. Each resourcekkhas a capacity ofBkB\_\{k\},k=1,…,Kk=1,\\ldots,K\. All the resources are known at time11\.

There is a finite set of*products*indexed byj=0,1,…​Jj=0,1,\\ldots Jthat are offered\. Each productjjcan be described by a size\-JJvector of featuresYjY\_\{j\},j=1,…,Jj=1,\\ldots,J\. We assume that‖Yj‖≤1\|\|Y\_\{j\}\|\|\\leq 1,j=1,…,Jj=1,\\ldots,J\. We denote the set of all such feature vectors by𝒴\\mathcal\{Y\}\. LetYYbe a matrix whose columns are all theJJfeature vectors\. We assume that the products can be made instantaneously from the resources\. Each productjjrequires a fixed amountaj​ka\_\{jk\}of resourcekk,j=1,…,Jj=1,\\ldots,J,k=1,…,Kk=1,\\ldots,K\.

There areIIcustomer types\. In each periodtt, there is a known probabilityλi\\lambda\_\{i\}that a customer of typeiiwill arrive,i=1,…,Ii=1,\\ldots,I\. We assume that there is at most one arrival in each period\. Each customeriiis described by a size\-IIvector of featuresXiX\_\{i\},i=1,…,Ii=1,\\ldots,I\. We denote the set of all such feature vectors by𝒳\\mathcal\{X\}\. Each customeriican be satisfied with any of the productsjj,j=1,…,Jj=1,\\ldots,J,i=1,…,Ii=1,\\ldots,I\. When a customeriiis assigned to a productjj, a reward ofXiT​A​Yj\+ξX\_\{i\}^\{T\}AY\_\{j\}\+\\xiis generated, whereAAis an unknownI×JI\\times Jmatrix, andξ\\xiis a zero\-mean random variable bounded by11, with variance at mostσ\\sigma\. If a customer is rejected, then we can assume that the customer is assigned to a resource with infinite capacity and feature vector00\. LetXXbe a matrix whose rows are all theIIfeature vectors\. We assume that the rank ofXXisIIand the rank ofYYisJJ\. This assumption is without loss of generality\. LetU=\(X​A\)TU=\(XA\)^\{T\}\. We normalizeUUsuch that each column‖Ui‖≤1\|\|U\_\{i\}\|\|\\leq 1and henceUi​Yj≤1U\_\{i\}Y\_\{j\}\\leq 1for alli=1,…,Ii=1,\\ldots,I,j=1,…,Jj=1,\\ldots,J\.

### 3\.1Summary of notation

- •XXis anI×II\\times Imatrix specifying the features of theIIcustomer types\.
- •YYis anJ×JJ\\times Jmatrix specifying the features of theJJproduct types\.
- •λi\\lambda\_\{i\}is the probability of having customeriiarrive in any given period andλ¯\\bar\{\\lambda\}ismax⁡\(λ1,λ2,⋯,λI\)\\max\(\\lambda\_\{1\},\\lambda\_\{2\},\\cdots,\\lambda\_\{I\}\)\.
- •AAis an unknownM×NM\\times Nmatrix that relates customer and product features to rewards\.
- •aj​ka\_\{jk\}is the amount of resourcekkrequired by productjjandCCismaxj,k⁡aj​k\\max\\limits\_\{j,k\}\{a\_\{jk\}\}\.
- •UUis\(X​A\)T\(XA\)^\{T\}\. Theii\-th column ofUUisUiU\_\{i\}, which is uniformly bounded byN0N\_\{0\}\.
- •U^i​t\\hat\{U\}\_\{it\}is our estimator forUiU\_\{i\}in periodtt\.
- •Mi​tM\_\{it\}is aJ×JJ\\times Jmatrix used to estimateUiU\_\{i\}in periodtt\.
- •i⁡\(t\)i\(t\)the type of the customer arriving in periodtt\.
- •j⁡\(t\)j\(t\)the type of the product assigned to the customer arriving in periodtt\.
- •rt=ξt\+Ui⁡\(t\)T​Yj⁡\(t\)r\_\{t\}=\\xi\_\{t\}\+U\_\{i\(t\)\}^\{T\}Y\_\{j\(t\)\}is the reward earned in periodttfor assigning the customeri⁡\(t\)i\(t\)to the productj⁡\(t\)j\(t\)\.
- •C​Bi​t\{CB\}\_\{it\}is a confidence ball maintained around the estimatorU^i​t\\hat\{U\}\_\{it\}ofUiU\_\{i\}in periodtt\.
- •βt\\beta\_\{t\}is the radius of the confidence intervalC​Bi​t\{CB\}\_\{it\}maintained around the estimatorU^i​t\\hat\{U\}\_\{it\}ofUiU\_\{i\}in periodtt\.
- •BkB\_\{k\}is total capacity of resourcekk, andBBis the vector ofB=\(B1,B2,⋯,BK\)B=\(B\_\{1\},B\_\{2\},\\cdots,B\_\{K\}\)\.
- •bk=BkTb\_\{k\}=\\frac\{B\_\{k\}\}\{T\}is average capacity of resourcekkin each period, andb=\(b1,b2,⋯,bK\)b=\(b\_\{1\},b\_\{2\},\\cdots,b\_\{K\}\)\.
- •bk​tb\_\{kt\}is the amount of capacity of resourcekkthat algorithmO​NONallocates to periodtt\.
- •x∗x^\{\*\}is a solution to \([16](https://arxiv.org/html/2608.11383#S4.E16)\) that assigns customers to products in expectation, with perfect knowledge of the reward function\.
- •DDis the feasible region of \([16](https://arxiv.org/html/2608.11383#S4.E16)\), which corresponds to vectorbb\.
- •Δ\\Deltais the minimum optimality gap for any sub\-optimal extreme point for \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\.
- •xtx\_\{t\}is an optimal solution to an approximation \([5](https://arxiv.org/html/2608.11383#S4.E5)\) at timettof \([16](https://arxiv.org/html/2608.11383#S4.E16)\) using a learned reward estimate\.
- •xt∗x^\{\*\}\_\{t\}is an optimal solution to a variant \([25](https://arxiv.org/html/2608.11383#S5.E25)\) at timettof \([16](https://arxiv.org/html/2608.11383#S4.E16)\) using the true reward function\.
- •DtD\_\{t\}is the feasible region of \([5](https://arxiv.org/html/2608.11383#S4.E5)\) and \([25](https://arxiv.org/html/2608.11383#S5.E25)\), which corresponds to capacity vectorbtb\_\{t\}\.
- •ϵk​t\\epsilon\_\{kt\}: the deviation from average of the capacity of resourcekkthat is used in periodtt\.

### 3\.2Stochastic formulation and optimal policy

LetBk​tB\_\{kt\}denote the remaining capacity of resourcekkat the beginning of periodttunder control policy\. Recall that the beginning of periodtt, the arriving customer, if any, reveals her typei⁡\(t\)i\(t\)\. The decision maker must assign the customer to a productj⁡\(t\)j\(t\)or reject the customer \(or equivalently, assign the customer to the null productj⁡\(t\)=0j\(t\)=0\)\. A*feasible policy*is a non\-anticipatory policy that always assigns a customer to a product with sufficient resources in every periodtt\. LetΠ\\Pidenote the set of feasible policies\.

###### Definition 1\.

For a particular realized assignment path\{\(i⁡\(s\),j⁡\(s\)\),s=1,2,⋯,T\}\\\{\(i\(s\),j\(s\)\),s=1,2,\\cdots,T\\\}, the reward earned under this path is defined as

TRp​a​t​h=∑s=1T\(Ui⁡\(s\)T​Yj⁡\(s\)\+ξs\)\.\\displaystyle\\textrm\{TR\}^\{path\}=\\sum\\limits\_\{s=1\}^\{T\}\(U\_\{i\(s\)\}^\{T\}Y\_\{j\(s\)\}\+\\xi\_\{s\}\)\.

For any policyπ∈Π\\pi\\in\\Pi, the expected Total Revenue \(TR\) earned underπ\\piis the expected sum over all possible assignment path\{\(i⁡\(s\),jπ​\(s\)\),s=1,2,⋯,T\}\\\{\(i\(s\),j^\{\\pi\}\(s\)\),s=1,2,\\cdots,T\\\}\. That is

TRπ=𝔼​∑s=1TUi⁡\(s\)T​Yjπ​\(s\)\.\\displaystyle\\textrm\{TR\}^\{\\pi\}=\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{T\}U\_\{i\(s\)\}^\{T\}Y\_\{j^\{\\pi\}\(s\)\}\.\(1\)The stochastic formulation of the problem is given by

TRo​p​t=\\displaystyle\\textrm\{TR\}^\{opt\}=maxπ∈Π⁡𝔼​∑s=1TUi⁡\(s\)T​Yj⁡\(s\)\\displaystyle\\max\\limits\_\{\\pi\\in\\Pi\}\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{T\}U\_\{i\(s\)\}^\{T\}Y\_\{j\(s\)\}\(2\)s\.t\.∑s=1T∑j=1Jaj​k𝟏\{j\(s\)=j\}≤Bka\.s\.,∀k∈\[1,K\]\.\\displaystyle\\sum\\limits\_\{s=1\}^\{T\}\\sum\\limits\_\{j=1\}^\{J\}a\_\{jk\}\\mathbf\{1\}\_\{\\\{\{j\(s\)=j\}\\\}\}\\leq B\_\{k\}\\mbox\{ a\.s\.\},\\forall k\\in\[1,K\]\.Note that the constraints must hold almost surely, i\.e\., with probability 1\.

In theory,TRo​p​t\\textrm\{TR\}^\{opt\}can be obtained by using dynamic programming\. Unfortunately, the well\-known curse of dimensionality makes computing the exact solution for this dynamic program intractable\.

## 4Policy and Benchmark

We will describe precisely our policy and benchmark\. We start by summarizing the main ideas of the policy\.

### 4\.1Summary of main ideas

Our approach is to gradually learn the columns of the matrixU=\(X​A\)TU=\(XA\)^\{T\}, which we denote asU1,U2,⋯,UIU\_\{1\},U\_\{2\},\\cdots,U\_\{I\}\. In the caseI=1I=1, a reasonable estimate of true vectorUiU\_\{i\}can be constructed by minimizing the squared loss function∑s=1t\(rs−U1​Yj⁡\(s\)\)2\\sum\\limits\_\{s=1\}^\{t\}\(r\_\{s\}\-U\_\{1\}Y\_\{j\(s\)\}\)^\{2\}, wherersr\_\{s\}is the reward collected atss\. In this case, if we define theJ×JJ\\times JmatrixMtM\_\{t\}asMt=∑s=1tYj⁡\(s\)​Yj⁡\(s\)TM\_\{t\}=\\sum\\limits\_\{s=1\}^\{t\}Y\_\{j\(s\)\}Y\_\{j\(s\)\}^\{T\}, then the estimator is given by

U^=Mt−1​∑s=1trs​Yj⁡\(s\)\.\\displaystyle\\hat\{U\}=M\_\{t\}^\{\-1\}\\sum\\limits\_\{s=1\}^\{t\}r\_\{s\}Y\_\{j\(s\)\}\.In the caseI\>1I\>1, we similarly useJ×JJ\\times JmatricesMi​t=∑s=1t𝟏\{i\(s\)=i\}Yj⁡\(s\)Yj⁡\(s\)TM\_\{it\}=\\sum\\limits\_\{s=1\}^\{t\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}Y\_\{j\(s\)\}Y\_\{j\(s\)\}^\{T\}to estimateUiU\_\{i\}at timett,i=1,…,Ii=1,\\ldots,I,t=1,…,Tt=1,\\ldots,T\.

First, we define the following22\-norm for each matrixMi​tM\_\{it\}:

‖u‖2,Mi​t=uT​Mi​t​u\.\\displaystyle\\\|u\\\|\_\{2,M\_\{it\}\}=\\sqrt\{u^\{T\}M\_\{it\}u\}\.We will maintain an estimateU^i​t\\hat\{U\}\_\{it\}ofUiU\_\{i\}in periodtt,i=1,…,Ii=1,\\ldots,I,t=1,…,Tt=1,\\ldots,T\. Let

βt=max⁡\{21​J​ln⁡\(t\)​ln⁡\(I​t2/δ\),\(1\.5​ln⁡\(I​t2/δ\)\)2\},\\displaystyle\\beta\_\{t\}=\\max\\\{21J\\ln\(t\)\\ln\(It^\{2\}/\\delta\),\(1\.5\\ln\(It^\{2\}/\\delta\)\)^\{2\}\\\},\(3\)whereδ\\deltais the parameter to control the estimate accuracy which will be determined later\. Define a confidence ball of radiusβt\\beta\_\{t\}aroundU^i​t\\hat\{U\}\_\{it\}as follows:

CBi​t\\displaystyle\\textrm\{CB\}\_\{it\}=\\displaystyle=\{v:‖v−U^i​t‖2,Mi​t≤βt\},∀i∈\[1,I\],\\displaystyle\\\{v:\\\|v\-\\hat\{U\}\_\{it\}\\\|\_\{2,M\_\{it\}\}\\leq\\beta\_\{t\}\\\},\\quad\\forall i\\in\[1,I\],\(4\)CBt\\displaystyle\\textrm\{CB\}\_\{t\}=\\displaystyle=∏i=1ICBi​t\.\\displaystyle\\prod\\limits\_\{i=1\}^\{I\}\\textrm\{CB\}\_\{it\}\.In our analysis, we will show that, with our choice ofβt\\beta\_\{t\},UUalways remains insideCBt\\textrm\{CB\}\_\{t\}with high probability, fort=1,…,Tt=1,\\ldots,T\.

Our algorithm uses the following ideas\. We plan to use an average amount of capacity in each period\. This average is the total capacity divided by the number of periods\. In each period, based on our estimate of the unknown parameter, we solve an LP specific to that period, to allocate customers to resources\. We use upper confidence bounds to deal with uncertainty in this assignment that arise from lack of knowledge about the unknown parameters\. We use the average capacity to constrain this assignment\. We then make the necessary assignment if any for an arriving customer, observe the realized reward, and perform a least\-squares update of our parameters\. The algorithm is a re\-solving algorithm because the LPs that are solved in different periods are identical to each other, except for the amount of uncertainty surrounding the unknown parameters\.

### 4\.2Online AlgorithmO​NON

1. 1\.Initialization: Setbk​1=BkTb\_\{k1\}=\\frac\{B\_\{k\}\}\{T\},Mi​1=IJ×JM\_\{i1\}=I\_\{J\\times J\}andU^i​1=0\\hat\{U\}\_\{i1\}=0,i=1,2,⋯,Ii=1,2,\\cdots,I,k=1,…,Kk=1,\\ldots,K\.
2. 2\.Fort=1t=1toTT: C​Bi​t\\displaystyle\{CB\}\_\{it\}=\\displaystyle=\{v:‖v−U^i​t‖2,Mi​t≤βt\},∀i∈\[1,I\],\\displaystyle\\\{v:\\\|v\-\\hat\{U\}\_\{it\}\\\|\_\{2,M\_\{it\}\}\\leq\\beta\_\{t\}\\\},\\quad\\forall i\\in\[1,I\],C​Bt\\displaystyle\{CB\}\_\{t\}=\\displaystyle=∏i=1IC​Bi​t\.\\displaystyle\\prod\\limits\_\{i=1\}^\{I\}\{CB\}\_\{it\}\.
3. 3\.In each periodtt, solve the following optimization problem to obtain probabilitiesxtx\_\{t\}: xt=arg​maxx∈Dt⁡maxV∈CBt​∑i,jxij​ViT​Yj,\\displaystyle x\_\{t\}=\\argmax\\limits\_\{x\\in D\_\{t\}\}\\max\\limits\_\{V\\in\{CB\}\_\{t\}\}\\sum\_\{i,j\}x\_\{ij\}V\_\{i\}^\{T\}Y\_\{j\},\(5\)where Dt=\{x\|∑i=1I∑j=1Jxi​jaj​k≤bk​t,∀k∈\[1,K\];∑jxi​j≤λi,∀i∈\[1,I\];x≥0\}\\displaystyle D\_\{t\}=\\\{x\\ \|\\ \\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq b\_\{kt\},\\ \\forall k\\in\[1,K\];\\ \\sum\\limits\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\ \\forall i\\in\[1,I\];\\ x\\geq 0\\\}is the feasible region\. The inner “max” means that we choose the best potential reward based on all the possible vectors inC​Bt\{CB\}\_\{t\}\. Note that this program is referred to in the literature as a*bilinear program*\([Peleg and Meir 2008](https://arxiv.org/html/2608.11383#bib.bib30)\)\. Such programs can be solved by standard techniques\.
4. 4\.Use the solutionxtx\_\{t\}to assign the customer attt, if any, to a resource\. More precisely, if the customer is of typeii,i=1,…,Ii=1,\\ldots,I, then assign the customer to each productjjwith probabilityxi​j​tλi\\frac\{x\_\{ijt\}\}\{\\lambda\_\{i\}\},j=1,…,Jj=1,\\ldots,J\. If there are insufficient resources to make the assigned product, then reject the customer \(or equivalently, assign the customer to a null resource\)\. The result of the assignment is a realization\(i⁡\(t\),j⁡\(t\)\)\(i\(t\),j\(t\)\)based onxtx\_\{t\}\. That is, the customer atttof typei⁡\(t\)i\(t\)is assigned to productj⁡\(t\)j\(t\)\.
5. 5\.Define a random variabledk​td\_\{kt\}, whose mean equals tobk​tb\_\{kt\}, to represent the realized usage of each resourcekkin periodtt, via dk​t\\displaystyle d\_\{kt\}=\\displaystyle=\{aj⁡\(t\)​k,∀k∈\[1,K\],if there is an arrival att,0,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}a\_\{j\(t\)k\},\\quad\\forall k\\in\[1,K\],\\quad\\mbox\{if there is an arrival at $t$\},\\\\ 0,\\quad o\.w\.\\end\{array\}\\right\.
6. 6\.Update the capacity allocated to periodt\+1t\+1via bk​t\+1=bk​t−\(dk​t−bk​t\)T−t,∀k∈\[1,K\]\.\\displaystyle b\_\{kt\+1\}=b\_\{kt\}\-\\frac\{\(d\_\{kt\}\-b\_\{kt\}\)\}\{T\-t\},\\quad\\forall k\\in\[1,K\]\.\(9\)
7. 7\.Collect the rewardrt=ξt\+Ui⁡\(t\)T​Yj⁡\(t\)r\_\{t\}=\\xi\_\{t\}\+U\_\{i\(t\)\}^\{T\}Y\_\{j\(t\)\}and update the estimatorU^i​t\+1\\hat\{U\}\_\{it\+1\}and matrixMi​t\+1M\_\{it\+1\}via Mi​t\+1\\displaystyle M\_\{it\+1\}=\\displaystyle=\{Mi​t\+Yj⁡\(t\)​Yj⁡\(t\)T,i=i⁡\(t\),Mi​t,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}M\_\{it\}\+Y\_\{j\(t\)\}Y\_\{j\(t\)\}^\{T\},\\quad i=i\(t\),\\\\ M\_\{it\},\\quad o\.w\.\\end\{array\}\\right\.U^i​t\+1\\displaystyle\\hat\{U\}\_\{it\+1\}=\\displaystyle=\{Mi​t\+1−1∑s=1trsYj⁡\(s\)𝟏\{i\(s\)=i\},i=i\(t\),U^i​t,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}M\_\{it\+1\}^\{\-1\}\\sum\\limits\_\{s=1\}^\{t\}r\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\},\\quad i=i\(t\),\\\\ \\hat\{U\}\_\{it\},\\quad o\.w\.\\end\{array\}\\right\.Under this updating rule, we have U^i​t=Mi​t−1∑s=1t−1rsYj⁡\(s\)𝟏\{i\(s\)=i\}=Mi​t−1\(Mi​t−1U^i​t−1\+rt−1Yj⁡\(t−1\)𝟏\{i\(t−1\)=i\}\)\\displaystyle\\hat\{U\}\_\{it\}=M\_\{it\}^\{\-1\}\\sum\\limits\_\{s=1\}^\{t\-1\}r\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}=M\_\{it\}^\{\-1\}\(M\_\{it\-1\}\\hat\{U\}\_\{it\-1\}\+r\_\{t\-1\}Y\_\{j\(t\-1\)\}\\mathbf\{1\}\_\{\\\{\{i\(t\-1\)=i\}\\\}\}\)fort∈\[1,T\]t\\in\[1,T\]\.

### 4\.3Benchmark

We will use as benchmark an optimal solution to the following optimization problem

x∗=arg​maxx∈D∑i=1I∑j=1JxijUiTYj,\\displaystyle x^\{\*\}=\\argmax\\limits\_\{x\\in D\}\\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\},\(16\)where

D=\{x\|∑i=1I∑j=1Jxi​jaj​k≤BkT,∀k∈\[1,K\];∑j=1Jxi​j≤λi,∀i∈\[1,I\];x≥0\}\.\\displaystyle D=\\\{x\\ \|\\ \\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq\\frac\{B\_\{k\}\}\{T\},\\ \\forall k\\in\[1,K\];\\ \\sum\\limits\_\{j=1\}^\{J\}x\_\{ij\}\\leq\\lambda\_\{i\},\\ \\forall i\\in\[1,I\];\\ x\\geq 0\\\}\.Note that sinceUUis unknown, the solutionx∗x^\{\*\}is unknown\. The key differences betweenx∗x^\{\*\}andxt′x^\{\\prime\}\_\{t\}, which is used by our online algorithm, are that \(i\) the former is constrained by the true average capacity, namelyB/TB/T, while the latter is constrained by the actual average remaining capacity; and \(ii\) the former is defined by the true reward parameters, namelyUiT​Yj\{U\_\{i\}\}^\{T\}Y\_\{j\}, while the latter is defined by an upper bound on the estimated reward parameters\.

Alternatively, the above problem can be written as

max\\displaystyle\\max∑i=1I∑j=1Jxi​j​UiT​Yj,\\displaystyle\\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\},\(17\)subject to∑i=1I∑j=1Jxi​j​aj​k≤BkT,∀k∈\[1,K\],\\displaystyle\\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq\\frac\{B\_\{k\}\}\{T\},\\quad\\forall k\\in\[1,K\],\(18\)∑j=1Jxi​j≤λi,∀i∈\[1,I\],\\displaystyle\\sum\_\{j=1\}^\{J\}x\_\{ij\}\\leq\\lambda\_\{i\},\\quad\\forall i\\in\[1,I\],x≥0\.\\displaystyle x\\geq 0\.We make the following key assumption about \([16](https://arxiv.org/html/2608.11383#S4.E16)\), which will enable us to quantify the regret of the online algorithm:

###### Assumption 1\.

There is a unique dual optimal solution to \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. Moreover, the variables\(μ1∗,⋯,μK∗\)\(\\mu^\{\*\}\_\{1\},\\cdots,\\mu^\{\*\}\_\{K\}\)corresponding to the capacity constraints \([18](https://arxiv.org/html/2608.11383#S4.Ex12)\) in this solution are strictly positive\.

The above assumption is similar to those made in[Jasin 2014](https://arxiv.org/html/2608.11383#bib.bib22)and[Chen et al\. 2018](https://arxiv.org/html/2608.11383#bib.bib13)\. These works study price control for network revenue management, where the objective function is the revenue rater⁡\(λ\)=λ​p​\(λ\)r\(\\lambda\)=\\lambda p\(\\lambda\)\. Assuming the convexity ofr⁡\(⋅\)r\(\\cdot\)and the linearity of constraints, the resulting deterministic optimization problem becomes a convex programming problem\. The assumption imposed by both of these papers is that the optimal vector of dual variables corresponding to the capacity constraints be strictly positive\. Remark:[Jasin 2014](https://arxiv.org/html/2608.11383#bib.bib22)lists two types of assumption\. The first type is strict positivity of the dual variables, as we have assumed\. The second type is a condition A5 that requires that the static pricepDp\_\{D\}be neither as low nor so high, so thatλD\\lambda^\{D\}lies in a proper interior of a strict positive region\. The latter assumption is just as strict, as does not happen in general in our model, since our optimal vectorxt∗x^\{\*\}\_\{t\}might have some zero components\.

The optimization problem \([16](https://arxiv.org/html/2608.11383#S4.E16)\) provides us with a performance benchmark in the following sense\.

###### Proposition 1\.

Fix an optimal solutionx∗x^\{\*\}of \([16](https://arxiv.org/html/2608.11383#S4.E16)\), which is an extreme point\. Let

Ru=∑i,jxi​j∗​UiT​Yj\.\\displaystyle R^\{u\}=\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\.Then the average reward per period of any online algorithm is bounded above byRuR^\{u\}, and the total reward over the horizon byRu​TR^\{u\}T\.

###### Proof of Proposition[1](https://arxiv.org/html/2608.11383#Thmproposition1):

LetO​F​FOFFbe an offline algorithm that knows a priori all demand arrivals, as well asUUandYY, and makes optimal decisions given this information\. On any sample pathω\\omega, where the total number of arrivals over the horizon of typeiiisΛi​\(ω\)\\Lambda\_\{i\}\(\\omega\), with𝔼⁡\[Λi​\(ω\)\]=T​λi\\mathbb\{E\}\[\\Lambda\_\{i\}\(\\omega\)\]=T\\lambda\_\{i\},O​F​FOFFmakes decisionsxt​\(ω\)x\_\{t\}\(\\omega\)in each periodtt, to optimize

max\\displaystyle\\max∑i,j∑t=1Txi​j​t​\(ω\)​UiT​Yj,\\displaystyle\\sum\_\{i,j\}\\sum\_\{t=1\}^\{T\}x\_\{ijt\}\(\\omega\)\{U\_\{i\}\}^\{T\}Y\_\{j\},\(19\)subject to∑i=1I∑j=1J∑t=1Txi​j​t​\(ω\)​aj​k≤Bk,∀k∈\[1,K\],\\displaystyle\\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}\\sum\_\{t=1\}^\{T\}x\_\{ijt\}\(\\omega\)a\_\{jk\}\\leq B\_\{k\},\\quad\\forall k\\in\[1,K\],∑t=1T∑j=1Jxi​j​t​\(ω\)≤Λi​\(ω\),∀i∈\[1,I\],\\displaystyle\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{J\}x\_\{ijt\}\(\\omega\)\\leq\\Lambda\_\{i\}\(\\omega\),\\quad\\forall i\\in\[1,I\],xt​\(ω\)≥0\.\\displaystyle x\_\{t\}\(\\omega\)\\geq 0\.Letx⁡\(ω\)=∑t=1Txt​\(ω\)Tx\(\\omega\)=\\frac\{\\sum\\limits\_\{t=1\}^\{T\}x\_\{t\}\(\\omega\)\}\{T\}\. Equivalently,O​F​FOFFmaximizes

max\\displaystyle\\max∑i,jxi​j​\(ω\)​UiT​Yj,\\displaystyle\\sum\_\{i,j\}x\_\{ij\}\(\\omega\)\{U\_\{i\}\}^\{T\}Y\_\{j\},\(20\)subject to∑i=1I∑j=1Jxi​j​\(ω\)​aj​k≤BkT,∀k∈\[1,K\],\\displaystyle\\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\(\\omega\)a\_\{jk\}\\leq\\frac\{B\_\{k\}\}\{T\},\\quad\\forall k\\in\[1,K\],∑j=1Jxi​j​\(ω\)≤Λi​\(ω\)/T,∀i∈\[1,I\],\\displaystyle\\sum\_\{j=1\}^\{J\}x\_\{ij\}\(\\omega\)\\leq\\Lambda\_\{i\}\(\\omega\)/T,\\quad\\forall i\\in\[1,I\],x⁡\(ω\)≥0\.\\displaystyle x\(\\omega\)\\geq 0\.Thus,𝔼⁡\[x⁡\(ω\)\]\\mathbb\{E\}\[x\(\\omega\)\]is feasible for the constraint of \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. It follows that

𝔼⁡\[∑i,jxi​j​\(ω\)​UiT​Yj\]=∑i,j𝔼⁡\[xi​j​\(ω\)\]​UiT​Yj\\displaystyle\\mathbb\{E\}\[\\sum\_\{i,j\}x\_\{ij\}\(\\omega\)\{U\_\{i\}\}^\{T\}Y\_\{j\}\]=\\sum\_\{i,j\}\\mathbb\{E\}\[x\_\{ij\}\(\\omega\)\]\{U\_\{i\}\}^\{T\}Y\_\{j\}is no more than the optimal value of \([16](https://arxiv.org/html/2608.11383#S4.E16)\), which isRuR^\{u\}\. We conclude that no online algorithm can earn more thanRuR^\{u\}in expectation in each period on average, orRu​TR^\{u\}Tover the entire horizon\. ∎

## 5Deviation from ideal capacity usage

### 5\.1re\-optimization on the perturbation ofbb

Recall \([16](https://arxiv.org/html/2608.11383#S4.E16)\), which defines the benchmark solutionx∗x^\{\*\}\. In general, we cannot solve \([16](https://arxiv.org/html/2608.11383#S4.E16)\) because we do not have access toUU\. Even if we did, the solution would not be useful because the randomness in demand will cause our capacity to deviate in a random manner\. Nevertheless, we can adjust our use of capacity to match that of \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. More precisely, we will approximate the feasible regionDDof \([16](https://arxiv.org/html/2608.11383#S4.E16)\), which is defined by the capacity levelB/TB/T, with a regionsDtD\_\{t\}, which is defined by the average actual capacity remaining attt,t=1,…,Tt=1,\\ldots,T\.

In the following variant of problem \([16](https://arxiv.org/html/2608.11383#S4.E16)\), we think ofb′=\(b1′,b2′,⋯,bK′\)b^\{\\prime\}=\(b^\{\\prime\}\_\{1\},b^\{\\prime\}\_\{2\},\\cdots,b^\{\\prime\}\_\{K\}\)as a perturbation to the ideal average capacityB/TB/T\. Consider the solution when we changeB/TB/Ttob′b^\{\\prime\}:

x′=arg​maxx∈D′∑i=1I∑j=1JxijUiTYj,\\displaystyle x^\{\\prime\}=\\argmax\\limits\_\{x\\in D^\{\\prime\}\}\\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\},\(21\)where,

D′=\{x\|∑i=1I∑j=1Jxi​jaj​k≤bk′,∀k∈\[1,K\];∑j=1Jxi​j≤λi,∀i∈\[1,I\];x∗≥0\}\.\\displaystyle D^\{\\prime\}=\\\{x\\ \|\\ \\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq b^\{\\prime\}\_\{k\},\\ \\forall k\\in\[1,K\];\\ \\sum\\limits\_\{j=1\}^\{J\}x\_\{ij\}\\leq\\lambda\_\{i\},\\ \\forall i\\in\[1,I\];\\ x^\{\*\}\\geq 0\\\}\.Or alternatively,

max\\displaystyle\\max∑i=1I∑j=1Jxi​j​UiT​Yj,\\displaystyle\\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\},\(22\)subject to∑ixi​j​aj​k≤bk′,∀k∈\[1,K\],\\displaystyle\\sum\\limits\_\{i\}x\_\{ij\}a\_\{jk\}\\leq b^\{\\prime\}\_\{k\},\\quad\\forall k\\in\[1,K\],\(23\)∑jxi​j≤λi,∀i∈\[1,I\],\\displaystyle\\sum\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\quad\\forall i\\in\[1,I\],x≥0\.\\displaystyle x\\geq 0\.Define the expected rewardR⁡\(b′\)R\(b^\{\\prime\}\), which is a function of the capacityb′b^\{\\prime\}, as the optimal value of \([21](https://arxiv.org/html/2608.11383#S5.E21)\)\.

A direct consequence of Assumption 1 is that∂R∂Bk′​\(BT\)=μk∗\\frac\{\\partial R\}\{\\partial B^\{\\prime\}\_\{k\}\}\(\\frac\{B\}\{T\}\)=\\mu^\{\*\}\_\{k\}fork=1,2,⋯,Kk=1,2,\\cdots,K\. Furthermore, we have the following proposition\.

###### Proposition 2\.

LetΔ\>0\\Delta\>0be the minimum optimality gap for all sub\-optimal extreme points of \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. Then there exists a constantϵ\\epsilonsuch that if‖b′−BT‖∞≤ϵ\\\|b^\{\\prime\}\-\\frac\{B\}\{T\}\\\|\_\{\\infty\}\\leq\\epsilon, then the followings hold:

- i\)∂R∂bk′=μk∗\\frac\{\\partial R\}\{\\partial b^\{\\prime\}\_\{k\}\}=\\mu^\{\*\}\_\{k\}fork=1,2,⋯,Kk=1,2,\\cdots,K\.
- ii\)There is a unique optimal solution to \([21](https://arxiv.org/html/2608.11383#S5.E21)\)\.
- iii\)For any extreme point ofD′D^\{\\prime\}that is sub\-optimal for \([21](https://arxiv.org/html/2608.11383#S5.E21)\), the expected reward at the point is at leastΔ3\\frac\{\\Delta\}\{3\}smaller thanR⁡\(b′\)R\(b^\{\\prime\}\)\.
- iv\)For any optimal solutionx∗x^\{\*\}to \([16](https://arxiv.org/html/2608.11383#S4.E16)\), there exists aI​J×KIJ\\times K\-matrixQQ, such thatx′=x∗\+Q⁡\(b′−BT\)x^\{\\prime\}=x^\{\*\}\+Q\(b^\{\\prime\}\-\\frac\{B\}\{T\}\)is an optimal extreme point of \([21](https://arxiv.org/html/2608.11383#S5.E21)\)\.

###### Proof of Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2):

Since \([16](https://arxiv.org/html/2608.11383#S4.E16)\) has a unique dual\-optimal solutionμ∗\\mu^\{\*\}, andb′b^\{\\prime\}is a small perturbation ofB/TB/T, for sufficiently smallϵ\\epsilon,μ∗\\mu^\{\*\}remains dual\-optimal for \([21](https://arxiv.org/html/2608.11383#S5.E21)\)\. Thus, \(i\) and \(ii\) follow\.

To see \(iii\), let\(μ∗,λ∗\)\(\\mu^\{\*\},\\lambda^\{\*\}\)be the optimal dual solution to \([16](https://arxiv.org/html/2608.11383#S4.E16)\) and \([21](https://arxiv.org/html/2608.11383#S5.E21)\)\. Letr=UT​Yr=U^\{T\}Y\. Chooseϵ\\epsilonsufficiently small such that whenever‖b′−B/T‖∞<ϵ\\\|b^\{\\prime\}\-B/T\\\|\_\{\\infty\}<\\epsilon,

rT​W−1​\(b′−B/T\)≤Δ/3r^\{T\}W^\{\-1\}\(b^\{\\prime\}\-B/T\)\\leq\\Delta/3for all primal basesWWof\([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. Note that \([16](https://arxiv.org/html/2608.11383#S4.E16)\) and \([21](https://arxiv.org/html/2608.11383#S5.E21)\) share the same set of primal bases\. LetW∗W^\{\*\}andW′W^\{\\prime\}be the primal bases corresponding toxxandx′x^\{\\prime\}, respectively\. Then, sincerT​W∗−1​B/T=R⁡\(B/T\)r^\{T\}W^\{\*\-1\}B/T=R\(B/T\), we conclude thatrT​W∗−1​b′r^\{T\}W^\{\*\-1\}b^\{\\prime\}is withinΔ/3\\Delta/3ofR⁡\(b′\)R\(b^\{\\prime\}\), i\.e\.,

\|rT​W′−1​b′−rT​W∗−1​b\|<Δ/3\.\|r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\-r^\{T\}W^\{\*\-1\}b\|<\\Delta/3\.Letx′′x^\{\\prime\\prime\}be any suboptimal extreme point of \([21](https://arxiv.org/html/2608.11383#S5.E21)\) and letW′′W^\{\\prime\\prime\}be its corresponding basis\. Suppose thatrT​\(x′−x′′\)<Δ/3r^\{T\}\(x^\{\\prime\}\-x^\{\\prime\\prime\}\)<\\Delta/3\. Then

rTW∗−1b−rTW′′−1b\\displaystyle r^\{T\}W^\{\*\-1\}b\-r^\{T\}W^\{\\prime\\prime\-1\}b=\\displaystyle=\(rTW∗−1b−rTW′−1b′\)\+\(rTW′−1b′−rTW′′−1b′\)\\displaystyle\(r^\{T\}W^\{\*\-1\}b\-r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\)\+\(r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\-r^\{T\}W^\{\\prime\\prime\-1\}b^\{\\prime\}\)\(24\)\+\(rTW′′−1b′−rTW′′−1b\)\\displaystyle\+\(r^\{T\}W^\{\\prime\\prime\-1\}b^\{\\prime\}\-r^\{T\}W^\{\\prime\\prime\-1\}b\)<\\displaystyle<Δ/3\+Δ/3\+Δ/3\\displaystyle\\Delta/3\+\\Delta/3\+\\Delta/3=\\displaystyle=Δ\.\\displaystyle\\Delta\.In other words,W′′−1bW^\{\\prime\\prime\-1\}bis an extreme point with objective withinΔ\\Deltaof optimality for \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. This contradicts the definition ofΔ\\Delta\.

To see \(iv\), notice that in \([24](https://arxiv.org/html/2608.11383#S5.Ex28)\), asϵ→0\\epsilon\\rightarrow 0, the left\-hand side must remain bounded below byΔ\\Delta, yetrT​W∗−1​b−rT​W′−1​b′→0r^\{T\}W^\{\*\-1\}b\-r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\\rightarrow 0, andrTW′′−1b′−rTW′′−1b→0r^\{T\}W^\{\\prime\\prime\-1\}b^\{\\prime\}\-r^\{T\}W^\{\\prime\\prime\-1\}b\\rightarrow 0\. Thus,rTW′−1b′−rTW′′−1b′r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\-r^\{T\}W^\{\\prime\\prime\-1\}b^\{\\prime\}must be bounded below by a positive numberδ\\delta\. Thus, for sufficiently smallϵ\\epsilon,\|rTW∗−1b′−rTW′−1b′\|≤\|rTW∗−1b′−rTW∗−1b\|\+\|rTW∗−1b−rTW′−1b′\|≤rTW′−1b′−rTW′′−1b′\|r^\{T\}W^\{\*\-1\}b^\{\\prime\}\-r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\|\\leq\|r^\{T\}W^\{\*\-1\}b^\{\\prime\}\-r^\{T\}W^\{\*\-1\}b\|\+\|r^\{T\}W^\{\*\-1\}b\-r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\|\\leq r^\{T\}W^\{\\prime\-1\}b^\{\\prime\}\-r^\{T\}W^\{\\prime\\prime\-1\}b^\{\\prime\}, for any suboptimalx′′=W′′−1b′x^\{\\prime\\prime\}=W^\{\\prime\\prime\-1\}b^\{\\prime\}\. It follows thatW∗−1​b′W^\{\*\-1\}b^\{\\prime\}must be optimal for \([21](https://arxiv.org/html/2608.11383#S5.E21)\), orx′=W∗−1​b′x^\{\\prime\}=W^\{\*\-1\}b^\{\\prime\}\. In other words,

x−x′=W∗−1​b−W∗−1​b′=W∗−1​\(b−b′\)\.\\displaystyle x\-x^\{\\prime\}=W^\{\*\-1\}b\-W^\{\*\-1\}b^\{\\prime\}=W^\{\*\-1\}\(b\-b^\{\\prime\}\)\.Thus, \(iv\) follows by takingQ=W∗−1Q=W^\{\*\-1\}\. ∎

The following lemma shows how large we can chooseϵ\\epsilonin Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2)\.

###### Lemma 1\.

Theϵ\\epsilonin Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2)is at least in the order ofΘ⁡\(Δ\)\\Theta\(\\Delta\)\. To be precise,ϵ\\epsiloncan be chosen at least atΔK​Cμ\\frac\{\\Delta\}\{KC\_\{\\mu\}\}, whereCμ=maxk⁡\{mini,j⁡\{UiT​Yjaj​k\}\}C\_\{\\mu\}=\\max\\limits\_\{k\}\\\{\\min\\limits\_\{i,j\}\\\{\\frac\{U\_\{i\}^\{T\}Y\_\{j\}\}\{a\_\{jk\}\}\\\}\\\}\.

In our online algorithmO​NON, the updated capacity vector\(b1​t,b2​t,…,bk​t\)\(b\_\{1t\},b\_\{2t\},\\ldots,b\_\{kt\}\)from the last periodt−1t\-1, will define the feasible regionDtD\_\{t\}in the re\-optimization \([5](https://arxiv.org/html/2608.11383#S4.E5)\)\. In order to apply Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2)inDtD\_\{t\}, we have the following definition\.

###### Definition 2\.

Fixing theϵ=ΔK​Cμ\\epsilon=\\frac\{\\Delta\}\{KC\_\{\\mu\}\}in Lemma[1](https://arxiv.org/html/2608.11383#Thmlemma1)and Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2), and we call the regionDtD\_\{t\}in \([5](https://arxiv.org/html/2608.11383#S4.E5)\) is*well\-approximated*if the actual average remaining capacity is sufficiently close to the ideal average, i\.e\.,\|bk​t−Bk¯T\|≤ϵ,∀k∈\[1,K\]\.\|b\_\{kt\}\-\\frac\{\\bar\{B\_\{k\}\}\}\{T\}\|\\leq\\epsilon,\\forall k\\in\[1,K\]\.

We denotext∗x^\{\*\}\_\{t\}as the optimal solution in the feasible regionDtD\_\{t\}at timettin the following way\.

x∗t=arg​maxx∈Dt∑i,jxijUiTYj,\\displaystyle x^\{\*\}\_\{t\}=\\argmax\\limits\_\{x\\in D\_\{t\}\}\\sum\_\{i,j\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\},\(25\)whereDt=\{x\|∑i∑jxi​jai​k≤bk​t,∀k∈\[1,K\];∑jxi​j≤λi,∀i∈\[1,I\];x≥0\}D\_\{t\}=\\\{x\|\\sum\\limits\_\{i\}\\sum\\limits\_\{j\}x\_\{ij\}a\_\{ik\}\\leq b\_\{kt\},\\forall k\\in\[1,K\];\\sum\\limits\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\forall i\\in\[1,I\];x\\geq 0\\\}\. Then whenDtD\_\{t\}is well\-approximated, the assumptions of Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2)apply, and we can claim that each optimal solution to \([25](https://arxiv.org/html/2608.11383#S5.E25)\) has a unique corresponding solution to \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. Without loss of generality, we fix an optimal solutionx∗x^\{\*\}to \([16](https://arxiv.org/html/2608.11383#S4.E16)\)\. WhenDtD\_\{t\}is well\-approximated, each optimal solution to \([25](https://arxiv.org/html/2608.11383#S5.E25)\) has the closed\-formxt∗=x∗\+Q⁡\(b′−BT\)x^\{\*\}\_\{t\}=x^\{\*\}\+Q\(b^\{\\prime\}\-\\frac\{B\}\{T\}\)\. We also know that for other extreme points to \([25](https://arxiv.org/html/2608.11383#S5.E25)\), the optimality gap is either zero or at leastΔ3\\frac\{\\Delta\}\{3\}\.

### 5\.2Expected reward in re\-optimization

Note that the updating ofbbin Online AlgorithmO​NONis

bk​t\+1=bk​t−dk​t−bk​tT−t\.\\displaystyle b\_\{kt\+1\}=b\_\{kt\}\-\\frac\{d\_\{kt\}\-b\_\{kt\}\}\{T\-t\}\.By induction, we can conclude that

bk​t\+1=BkT−∑s=1tdk​s−bk​sT−s\.b\_\{kt\+1\}=\\frac\{B\_\{k\}\}\{T\}\-\\sum\\limits\_\{s=1\}^\{t\}\\frac\{d\_\{ks\}\-b\_\{ks\}\}\{T\-s\}\.
Let

ηk​t=bk​t\+1−BkT=∑s=1tdk​s−bk​sT−s\\eta\_\{kt\}=b\_\{kt\+1\}\-\\frac\{B\_\{k\}\}\{T\}=\\sum\\limits\_\{s=1\}^\{t\}\\frac\{d\_\{ks\}\-b\_\{ks\}\}\{T\-s\}be the deviation inbbin each period andηk​t\\eta\_\{kt\}are martingales\. Recall theϵ\\epsilonin Lemma[1](https://arxiv.org/html/2608.11383#Thmlemma1)and define

τ:=inf\{t\|∃k∈\[1,K\]​s\.t\.​ηk​t\>ϵ\}\.\\displaystyle\\tau:=\\inf\\\{t\\ \|\\ \\exists k\\in\[1,K\]\\ \\textrm\{ s\.t\. \}\\eta\_\{kt\}\>\\epsilon\\\}\.\(26\)Thenτ\\tauis a stopping time\. Letρ0=∑i,jxi​j∗​UiT​Yj=Ru\\rho\_\{0\}=\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}=R^\{u\}be the optimal average reward and

ρt\+1=\{∑i,jxi​j​t∗​UiT​Yj,∀t∈\[1,τ−1\],ρt,∀t∈\[τ,T\]\.\\rho\_\{t\+1\}=\\left\\\{\\begin\{array\}\[\]\{ll\}\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\},&\\forall t\\in\[1,\\tau\-1\],\\\\ \\rho\_\{t\},&\\quad\\forall t\\in\[\\tau,T\]\.\\end\{array\}\\right\.\(27\)It’s easy to see thatρt\\rho\_\{t\}equals the reward under applying policyxt∗x^\{\*\}\_\{t\}with constraintDtD\_\{t\}before the stopping timeτ\\tauand remains same afterτ\\tau\. That meansρt\\rho\_\{t\}can be written as the form of∑i,jxi​j​UiT​Yj\\sum\\limits\_\{i,j\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}for alltt\. Note thatUiT​Yj≤1\{U\_\{i\}\}^\{T\}Y\_\{j\}\\leq 1hence we have a uniform bound11onρt\\rho\_\{t\}for alltt\.

By Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2), we can fix an optimal solutionx∗x^\{\*\}and a corresponding matrixQQsuch that ifDtD\_\{t\}is well\-approximated, then the optimal solution to \([25](https://arxiv.org/html/2608.11383#S5.E25)\) has the formxt∗=x∗\+Q​ηtx^\{\*\}\_\{t\}=x^\{\*\}\+Q\\eta\_\{t\}, whereηt=\(η1​t,η2​t,⋯,ηK​t\)\\eta\_\{t\}=\(\\eta\_\{1t\},\\eta\_\{2t\},\\cdots,\\eta\_\{Kt\}\)\. Building on this fact,ρt\+1=∑i,jxi​j​t∗​UiT​Yj=Ru\+∑i,j\(Q​ηt\)i​j​UiT​Yj\\rho\_\{t\+1\}=\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}=R^\{u\}\+\\sum\\limits\_\{i,j\}\(Q\\eta\_\{t\}\)\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\. Since\{ηk​t,t=1,2,⋯\}\\\{\\eta\_\{kt\},t=1,2,\\cdots\\\}are martingales for allk=1,…,Kk=1,\\ldots,K,\{ρt,t=1,2,⋯\}\\\{\\rho\_\{t\},t=1,2,\\cdots\\\}are also martingales, which leads to the following proposition\.

###### Proposition 3\.

For any stopping timeτ′\\tau^\{\\prime\},𝔼​ρτ′=Ru\\mathbb\{E\}\\rho\_\{\\tau^\{\\prime\}\}=R^\{u\}\. It follows that∑s=1Tρs=Ru​T\\sum\\limits\_\{s=1\}^\{T\}\\rho\_\{s\}=R^\{u\}T\.

## 6Regret of the Online Algorithm

In this section, we will analyze the regret of the online algorithm\. The main theorem of this paper is stated below\.

###### Theorem 1\.

The regret of the online algorithmO​NONis at most1\+I\+K3​C2​Cμ2Δ2\+K3​C2​Cμ2Δ2​ln⁡\(T\)\+252​I​J2Δ​ln3⁡\(T\)1\+I\+\\frac\{K^\{3\}C^\{2\}C\_\{\\mu\}^\{2\}\}\{\\Delta^\{2\}\}\+\\frac\{K^\{3\}C^\{2\}C\_\{\\mu\}^\{2\}\}\{\\Delta^\{2\}\}\\ln\(T\)\+\\frac\{252IJ^\{2\}\}\{\\Delta\}\\ln^\{3\}\(T\)\.

To analyze the regret, We first define a pseudo regret as the difference in the expected reward between the ideal solutionxt∗x\_\{t\}^\{\*\}and the approximate solutionxtx\_\{t\}in each periodtt\. Actually, the pseudo regret is only coming from the deviation inbb\.

### 6\.1Bounding the total regret by deviation

###### Definition 3\.

Define the pseudo regretgtg\_\{t\}in each periodttas

gt\\displaystyle g\_\{t\}=∑i,j\(xt∗\)i​j​UiT​Yj−∑i,j\(xt\)i​j​UiT​Yj\\displaystyle=\\sum\\limits\_\{i,j\}\(x\_\{t\}^\{\*\}\)\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}\(x\_\{t\}\)\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}=∑i,jxi​j​t∗​UiT​Yj−∑i,jxi​j​t​UiT​Yj\.\\displaystyle=\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\.

Note that the pseudo regretgtg\_\{t\}is the difference in expected reward in periodttbetween the ideal solutionxt∗x\_\{t\}^\{\*\}and the approximate solutionxtx\_\{t\}, both coming from the feasible regionDtD\_\{t\}\. By the definition ofτ\\tauin \([27](https://arxiv.org/html/2608.11383#S5.E27)\), after the stopping timeτ\\tau, the optimal solution to \([25](https://arxiv.org/html/2608.11383#S5.E25)\) atτ\\tauisxi​j​τ∗x^\{\*\}\_\{ij\\tau\}\. Soρτ=∑i,jxi​j​τ∗​UiT​Yj≤∑i,jxi​j​τ∗=1\\rho\_\{\\tau\}=\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ij\\tau\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\\leq\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ij\\tau\}=1, andρt=ρτ≤1\\rho\_\{t\}=\\rho\_\{\\tau\}\\leq 1, for allt\>τt\>\\tau\. Before the stopping timet≤τt\\leq\\tau,DtD\_\{t\}is well\-approximated\. Now depending ont≤τt\\leq\\tauort\>τt\>\\tau, we can bound the regret in the following proposition\.

###### Proposition 4\.

The regret of the online algorithmO​NONis bounded by𝔼​∑s=1τgs\+𝔼⁡\[T−τ\]\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}g\_\{s\}\+\\mathbb\{E\}\[T\-\\tau\]\.

###### Proof of Proposition[4](https://arxiv.org/html/2608.11383#Thmproposition4):

As noted in Proposition[1](https://arxiv.org/html/2608.11383#Thmproposition1), the optimal reward of any algorithm is bounded byRu​TR^\{u\}T\. Then the difference in rewards between the online policyO​NONand an optimal policy is bounded above by

Ru​T−𝔼​∑s=1T∑i,jxi​j​t​UiT​Yj\\displaystyle R^\{u\}T\-\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{T\}\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}≤\\displaystyle\\leq𝔼​∑s=1Tρs−𝔼​∑s=1τ∑i,jxi​j​t​UiT​Yj\\displaystyle\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{T\}\\rho\_\{s\}\-\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}=\\displaystyle=𝔼​∑s=1τρs−𝔼​∑s=1τ∑i,jxi​j​t​UiT​Yj\+𝔼​∑τ\+1Tρs\\displaystyle\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}\\rho\_\{s\}\-\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\+\\mathbb\{E\}\\sum\\limits\_\{\\tau\+1\}^\{T\}\\rho\_\{s\}≤\\displaystyle\\leq𝔼​∑s=1τ\(∑i,jxi​j∗​UiT​Yj−∑i,jxi​j​t​UiT​Yj\)\+𝔼​∑τ\+1Tρs\\displaystyle\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}\(\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\)\+\\mathbb\{E\}\\sum\\limits\_\{\\tau\+1\}^\{T\}\\rho\_\{s\}≤\\displaystyle\\leq𝔼​∑s=1τgs\+𝔼⁡\[T−τ\]\.\\displaystyle\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}g\_\{s\}\+\\mathbb\{E\}\[T\-\\tau\]\.∎

Then in the following two subsections[6\.2](https://arxiv.org/html/2608.11383#S6.SS2)and[6\.3](https://arxiv.org/html/2608.11383#S6.SS3), we will bound each term in Proposition[4](https://arxiv.org/html/2608.11383#Thmproposition4), respectively\.

### 6\.2Regret on the estimator ofUU

The following proposition states that ifUUis inCBt\\textrm\{CB\}\_\{t\}, then the difference in reward for each product is also small at timett\.

###### Proposition 5\.

IfU∈CBtU\\in\\textrm\{CB\}\_\{t\}, then\|\(U^i​t−Ui\)T​Y\|≤βt​YT​Mi​t−1​Y\|\(\\hat\{U\}\_\{it\}\-U\_\{i\}\)^\{T\}Y\|\\leq\\sqrt\{\\beta\_\{t\}Y^\{T\}M\_\{it\}^\{\-1\}Y\}for any vectorYY,i=1,…,Ii=1,\\ldots,I,t=1,…,Tt=1,\\ldots,T\.

###### Proof of Proposition[5](https://arxiv.org/html/2608.11383#Thmproposition5):

In this proof, we omit the superscriptiifor simplicity\.

\|\(U^t−U\)T​Y\|\\displaystyle\|\(\\hat\{U\}\_\{t\}\-U\)^\{T\}Y\|=\\displaystyle=\|\(U^t−U\)TMt1/2Mt−1/2Y\|\\displaystyle\|\(\\hat\{U\}\_\{t\}\-U\)^\{T\}M\_\{t\}^\{1/2\}M\_\{t\}^\{\-1/2\}Y\|=\\displaystyle=\|\(Mt1/2\(U^t−U\)\)TMt−1/2Y\|\\displaystyle\|\(M\_\{t\}^\{1/2\}\(\\hat\{U\}\_\{t\}\-U\)\)^\{T\}M\_\{t\}^\{\-1/2\}Y\|≤\\displaystyle\\leq\|\|\(Mt1/2\(U^t−U\)\)T\|\|⋅\|\|Mt−1/2Y\|\|\\displaystyle\|\|\(M\_\{t\}^\{1/2\}\(\\hat\{U\}\_\{t\}\-U\)\)^\{T\}\|\|\\cdot\|\|M\_\{t\}^\{\-1/2\}Y\|\|≤\\displaystyle\\leqβt​YT​Mt−1​Y\.\\displaystyle\\sqrt\{\\beta\_\{t\}Y^\{T\}M\_\{t\}^\{\-1\}Y\}\.SinceUUis inCBt\\textrm\{CB\}\_\{t\}, the last line holds\. ∎

Then, the following proposition shows that the pseudo regretgtg\_\{t\}can be bounded by a function of the decisionxtx\_\{t\}alone\.

###### Proposition 6\.

IfU∈CBtU\\in\\textrm\{CB\}\_\{t\}, the incremental regretgtg\_\{t\}satisfies

gt≤2​∑i,jxi​j​t​βt​min⁡\(YjT​Mi​t−1​Yj,1\)\.\\displaystyle g\_\{t\}\\leq 2\\sum\\limits\_\{i,j\}x\_\{ijt\}\\sqrt\{\\beta\_\{t\}\}\\min\(\\sqrt\{Y\_\{j\}^\{T\}M\_\{it\}^\{\-1\}Y\_\{j\}\},1\)\.

###### Proof of Proposition[6](https://arxiv.org/html/2608.11383#Thmproposition6):

LetV^\\hat\{V\}be the inner maximizer of \([5](https://arxiv.org/html/2608.11383#S4.E5)\) in periodtt\. ThenV^i∈CBi​t,i=1,2,⋯,I\\hat\{V\}\_\{i\}\\in\\textrm\{CB\}\_\{it\},i=1,2,\\cdots,I\. We have

∑i,jxi​j​t∗​UiT​Yj≤∑i,jxi​j​t​V^iT​Yj\.\\displaystyle\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\\leq\\sum\\limits\_\{i,j\}x\_\{ijt\}\\hat\{V\}\_\{i\}^\{T\}Y\_\{j\}\.Moreover,

∑i,jxi​j​t∗​UiT​Yj−∑i,jxi​j​t​UiT​Yj\\displaystyle\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}≤\\displaystyle\\leq∑i,jxi​j​t​V^iT​Yj−∑i,jxi​j​t​UiT​Yj\\displaystyle\\sum\\limits\_\{i,j\}x\_\{ijt\}\{\\hat\{V\}\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}=\\displaystyle=∑i,jxi​j​t​V^iT​Yj−∑i,jxi​j​t​U^i​tT​Yj\\displaystyle\\sum\\limits\_\{i,j\}x\_\{ijt\}\{\\hat\{V\}\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\\hat\{U\}\_\{it\}^\{T\}Y\_\{j\}\+∑i,jxi​j​tU^i​tTYj−∑i,jxi​j​tUiTYj\\displaystyle\+\\sum\\limits\_\{i,j\}x\_\{ijt\}\\hat\{U\}\_\{it\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}≤\\displaystyle\\leq∑i,jxi​j​t​\|V^i−U^i​t\|T​Yj\+∑i,jxi​j​t​\|U^i​t−Ui\|T​Yj\\displaystyle\\sum\\limits\_\{i,j\}x\_\{ijt\}\|\\hat\{V\}\_\{i\}\-\\hat\{U\}\_\{it\}\|^\{T\}Y\_\{j\}\+\\sum\\limits\_\{i,j\}x\_\{ijt\}\|\\hat\{U\}\_\{it\}\-\{U\_\{i\}\}\|^\{T\}Y\_\{j\}≤\\displaystyle\\leq2​∑i,jxi​j​t​βt​YjT​Mi​t−1​Yj\.\\displaystyle 2\\sum\\limits\_\{i,j\}x\_\{ijt\}\\sqrt\{\\beta\_\{t\}\}\\sqrt\{Y\_\{j\}^\{T\}M\_\{it\}^\{\-1\}Y\_\{j\}\}\.SinceUiU\_\{i\}andV^i\\hat\{V\}\_\{i\}are inC​Bt\{CB\}\_\{t\}, the last inequality holds\.

Note thatgt=∑i,jxi​j​t∗​UiT​Yj−∑i,jxi​j​t​UiT​Yj≤∑i,j\(\|xi​j​t∗\|\+\|xi​j​t\|\)​\|UiT​Yj\|≤∑i,j\(xi​j​t∗\+xi​j​t\)≤2​βtg\_\{t\}=\\sum\\limits\_\{i,j\}x^\{\*\}\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\-\\sum\\limits\_\{i,j\}x\_\{ijt\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\\leq\\sum\\limits\_\{i,j\}\(\|x^\{\*\}\_\{ijt\}\|\+\|x\_\{ijt\}\|\)\|\{U\_\{i\}\}^\{T\}Y\_\{j\}\|\\leq\\sum\\limits\_\{i,j\}\(x^\{\*\}\_\{ijt\}\+x\_\{ijt\}\)\\leq 2\\sqrt\{\\beta\_\{t\}\}\. By the inequality proved in the previous paragraph, the incremental regretgtg\_\{t\}in each periodttis bounded by

gt≤2​βt​∑i,jxi​j​t​min⁡\(YjT​Mi​t−1​Yj,1\)\.\\displaystyle g\_\{t\}\\leq 2\\sqrt\{\\beta\_\{t\}\}\\sum\\limits\_\{i,j\}x\_\{ijt\}\\min\(\\sqrt\{Y\_\{j\}^\{T\}M\_\{it\}^\{\-1\}Y\_\{j\}\},1\)\.∎

The updating rules \([7](https://arxiv.org/html/2608.11383#S4.EGx13)\) and \([7](https://arxiv.org/html/2608.11383#S4.EGx13)\) reveal howMi​tM\_\{it\}evolves over time, and we have the following two lemmas which give bounds ondet\(Mi​t\)\\det\(M\_\{it\}\)and∑gt2\\sum g\_\{t\}^\{2\}\.

###### Lemma 2\.

For alli=1,…,Ii=1,\\ldots,Iandt=1,…,Tt=1,\\ldots,T,det\(Mi​t\)≤tJ\\det\(M\_\{it\}\)\\leq t^\{J\}\.

###### Lemma 3\.

If∀s∈\[1,t\],U∈CBs\\forall s\\in\[1,t\],U\\in\\textrm\{CB\}\_\{s\}, then∑s=1tgs2≤83​βt​I​J​ln⁡\(t\)\\sum\\limits\_\{s=1\}^\{t\}g\_\{s\}^\{2\}\\leq\\frac\{8\}\{3\}\\beta\_\{t\}IJ\\ln\(t\)\.

By Proposition[2](https://arxiv.org/html/2608.11383#Thmproposition2), at each periodss, eithergs=0g\_\{s\}=0orgs≥Δ3g\_\{s\}\\geq\\frac\{\\Delta\}\{3\}, assuming that all regionsDsD\_\{s\}are well\-approximated\. Thus,∑s=1tΔ​gs≤3​∑s=1tgs2≤12​βt​I​J​ln⁡\(t\)\\sum\\limits\_\{s=1\}^\{t\}\\Delta g\_\{s\}\\leq 3\\sum\\limits\_\{s=1\}^\{t\}g\_\{s\}^\{2\}\\leq 12\\beta\_\{t\}IJ\\ln\(t\)\. Thus, we have the following proposition which bounds the first term of the regret in Proposition[4](https://arxiv.org/html/2608.11383#Thmproposition4)\.

###### Proposition 7\.

If eachDsD\_\{s\}is well\-approximated andU∈CBs,∀1≤s≤tU\\in\\textrm\{CB\}\_\{s\},\\forall 1\\leq s\\leq t, then∑s=1tgs≤12​I​J​βt​ln⁡\(t\)Δ\\sum\\limits\_\{s=1\}^\{t\}g\_\{s\}\\leq\\frac\{12IJ\\beta\_\{t\}\\ln\(t\)\}\{\\Delta\}\.

### 6\.3Regret in resolving

Recall\{ηk​t\}\\\{\\eta\_\{kt\}\\\}is a martingale for eachk=1,…,Kk=1,\\ldots,K\. Therefore, by Kolmogorov’s inequality, we have

Pr⁡\(max1≤s≤t⁡\|ηk​s\|≥ϵ\)≤1ϵ2​Var​\(ηk​t\)≤C2ϵ2​∑s=1t1\(T−s\)2,\\displaystyle\\Pr\(\\max\\limits\_\{1\\leq s\\leq t\}\|\\eta\_\{ks\}\|\\geq\\epsilon\)\\leq\\frac\{1\}\{\\epsilon^\{2\}\}\\mathrm\{Var\}\(\\eta\_\{kt\}\)\\leq\\frac\{C^\{2\}\}\{\\epsilon^\{2\}\}\\sum\\limits\_\{s=1\}^\{t\}\\frac\{1\}\{\(T\-s\)^\{2\}\},\(28\)whereC:=max1≤j≤J,k=1,…,Kaj​kC:=\\max\\limits\_\{1\\leq j\\leq J,\\ k=1,\\ldots,K\}\{a\_\{jk\}\}is a upper bound of the variance ofdk​t−bk​td\_\{kt\}\-b\_\{kt\}for anyttandkk\. Then

Pr⁡\(τ≤t\)≤∑k=1KPr⁡\(max1≤s≤t⁡\|ηk​s\|≥ϵ\)≤K​C2ϵ2​∑s=1t1\(T−s\)2\.\\displaystyle\\Pr\(\\tau\\leq t\)\\leq\\sum\\limits\_\{k=1\}^\{K\}\\Pr\(\\max\\limits\_\{1\\leq s\\leq t\}\|\\eta\_\{ks\}\|\\geq\\epsilon\)\\leq\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\\sum\\limits\_\{s=1\}^\{t\}\\frac\{1\}\{\(T\-s\)^\{2\}\}\.\(29\)Hence, the expected number of periods remaining after the stopping periodτ\\taucan be bounded in the following proposition\.

###### Proposition 8\.

𝔼⁡\[T−τ\]≤1\+K​C2ϵ2\+K​C2ϵ2​ln⁡\(T\)\\mathbb\{E\}\[T\-\\tau\]\\leq 1\+\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\+\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\\ln\(T\)\.

###### Proof of Proposition[8](https://arxiv.org/html/2608.11383#Thmproposition8):

We can rewrite the expectedτ\\tauas

𝔼⁡\[τ\]\\displaystyle\\mathbb\{E\}\[\\tau\]=\\displaystyle=∑t=1TPr⁡\(τ≥t\)\\displaystyle\\sum\\limits\_\{t=1\}^\{T\}\\Pr\(\\tau\\geq t\)=\\displaystyle=T−∑t=1TPr⁡\(τ<t\)\\displaystyle T\-\\sum\\limits\_\{t=1\}^\{T\}\\Pr\(\\tau<t\)=\\displaystyle=T−1−∑t=1T−1Pr⁡\(τ<t\)\.\\displaystyle T\-1\-\\sum\\limits\_\{t=1\}^\{T\-1\}\\Pr\(\\tau<t\)\.In other words,

𝔼⁡\[T−τ\]\\displaystyle\\mathbb\{E\}\[T\-\\tau\]≤\\displaystyle\\leq1\+∑t=1T−1Pr⁡\(τ<t\)\\displaystyle 1\+\\sum\\limits\_\{t=1\}^\{T\-1\}\\Pr\(\\tau<t\)≤\\displaystyle\\leq1\+∑t=1T−1K​C2ϵ2​∑s=1t1\(T−s\)2\\displaystyle 1\+\\sum\\limits\_\{t=1\}^\{T\-1\}\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\\sum\\limits\_\{s=1\}^\{t\}\\frac\{1\}\{\(T\-s\)^\{2\}\}=\\displaystyle=1\+K​C2ϵ2​∑t=1T−1T−t\(T−t\)2\\displaystyle 1\+\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\\sum\\limits\_\{t=1\}^\{T\-1\}\\frac\{T\-t\}\{\(T\-t\)^\{2\}\}=\\displaystyle=1\+K​C2ϵ2​∑t=1T−11t\\displaystyle 1\+\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\\sum\\limits\_\{t=1\}^\{T\-1\}\\frac\{1\}\{t\}≤\\displaystyle\\leq1\+K​C2ϵ2\+K​C2ϵ2​ln⁡\(T\),\\displaystyle 1\+\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\+\\frac\{KC^\{2\}\}\{\\epsilon^\{2\}\}\\ln\(T\),where the first inequality comes from \([29](https://arxiv.org/html/2608.11383#S6.E29)\)\. ∎

### 6\.4Concentration ofUU

In this subsection, we show that with high probability, the true parameterUUis inCBt\\textrm\{CB\}\_\{t\}for allt=1,…,Tt=1,\\ldots,T, which is the following proposition\.

###### Proposition 9\.

With the choice ofβt\\beta\_\{t\}, we have thatPr\(U∈CBt,∀t=1,…,T\)≥1−δ\\Pr\(U\\in\\textrm\{CB\}\_\{t\},\\ \\forall t=1,\\ldots,T\)\\geq 1\-\\delta\.

In order to prove Proposition[9](https://arxiv.org/html/2608.11383#Thmproposition9), we definezi​t=Mi​t​\(U^i​t−Ui\)z\_\{it\}=M\_\{it\}\(\\hat\{U\}\_\{it\}\-U\_\{i\}\)\. Note that‖U^i​t−Ui‖2,Mi​t=‖zi​t‖2,Mi​t−1\\\|\\hat\{U\}\_\{it\}\-U\_\{i\}\\\|\_\{2,M\_\{it\}\}=\\\|z\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}, henceU∈CBtU\\in\\textrm\{CB\}\_\{t\}is equivalent to‖zi​t‖2,Mi​t−1≤βt\\\|z\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\\leq\\beta\_\{t\}\.

###### Lemma 4\.

zi​t=∑s=1tξsYj⁡\(t\)𝟏\{i\(s\)=i\}−Ui\.\\displaystyle z\_\{it\}=\\sum\\limits\_\{s=1\}^\{t\}\\xi\_\{s\}Y\_\{j\(t\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\-U\_\{i\}\.

LetSi​t=∑s=1tξsYj⁡\(s\)𝟏\{i\(s\)=i\}S\_\{it\}=\\sum\\limits\_\{s=1\}^\{t\}\\xi\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}, thenzi​t=Si​t−Uiz\_\{it\}=S\_\{it\}\-U\_\{i\}\. Recall thatξt\\xi\_\{t\}is a zero\-mean random variable bounded in\[−1,1\]\[\-1,1\], henceSi​tS\_\{it\}is a martingale\. In our analysis, we use the following lemma to show that with high probability the martingaleSi​tS\_\{it\}stays close to zero, due to[Abbasi\-Yadkori et al\. 2011](https://arxiv.org/html/2608.11383#bib.bib1)\.

###### Lemma 5\.

For anyδ\>0\\delta\>0, with probability at least1−δ1\-\\delta, for allt≥1t\\geq 1\.

‖Si​t‖2,Mi​t−1≤2​log⁡\(det\(Mi​t\)1/2δ\)\\displaystyle\\\|S\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\\leq\\sqrt\{2\\log\(\\frac\{\\det\(M\_\{it\}\)^\{1/2\}\}\{\\delta\}\)\}

###### Proof of Lemma[5](https://arxiv.org/html/2608.11383#Thmlemma5):

Note thatMi​1=IJ×JM\_\{i1\}=I\_\{J\\times J\}andξt\\xi\_\{t\}is bounded in\[−1,1\]\[\-1,1\], by applying and settingR=1R=1in Theorem 1 of[Abbasi\-Yadkori et al\. 2011](https://arxiv.org/html/2608.11383#bib.bib1), we get the desired result\. ∎

By Lemma[2](https://arxiv.org/html/2608.11383#Thmlemma2), we have thatdet\(Mi​t\)≤tJ\\det\(M\_\{it\}\)\\leq t^\{J\}, and hence‖Si​t‖2,Mi​t−1≤log⁡\(tJδ2\)\\\|S\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\\leq\\sqrt\{\\log\(\\frac\{t^\{J\}\}\{\\delta^\{2\}\}\)\}\. Noticing that‖Ui‖2,Mi​t−1≤‖Ui‖2,M0−1=‖Ui‖≤1\\\|U\_\{i\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\\leq\\\|U\_\{i\}\\\|\_\{2,M\_\{0\}^\{\-1\}\}=\\\|U\_\{i\}\\\|\\leq 1and using the triangle inequality, we can bound‖zi​t‖2,Mi​t−1\\\|z\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}by‖Si​t‖2,Mi​t−1\+‖Ui‖2,Mi​t−1≤log⁡\(tJδ2\)\+1\\\|S\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\+\\\|U\_\{i\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\\leq\\sqrt\{\\log\(\\frac\{t^\{J\}\}\{\\delta^\{2\}\}\)\}\+1\. This leads to‖zi​t‖2,Mi​t−1≤βt\\\|z\_\{it\}\\\|\_\{2,M\_\{it\}^\{\-1\}\}\\leq\\beta\_\{t\}which completes the proof of Proposition[9](https://arxiv.org/html/2608.11383#Thmproposition9)\. Now we are ready to prove Theorem[1](https://arxiv.org/html/2608.11383#Thmtheorem1)\.

###### Proof of Theorem[1](https://arxiv.org/html/2608.11383#Thmtheorem1):

Define eventS∗=𝟏\{U∈CBt,∀t=1,…,T\}S^\{\*\}=\\mathbf\{1\}\_\{\\\{\{U\\in\\textrm\{CB\}\_\{t\},\\ \\forall t=1,\\ldots,T\}\\\}\}of having the trueUUin each of our Confidence BallsCBt\\textrm\{CB\}\_\{t\},t=1,…,Tt=1,\\ldots,T\. Conditioning onS∗S^\{\*\}and applying Proposition[7](https://arxiv.org/html/2608.11383#Thmproposition7), we have

𝔼​∑s=1τgs\\displaystyle\\mathbb\{E\}\\sum\\limits\_\{s=1\}^\{\\tau\}g\_\{s\}=\\displaystyle=Pr⁡\(S∗=1\)​𝔼​\[∑s=1τgs\|S∗=1\]\+Pr⁡\(S∗=0\)​𝔼​\[∑s=1τgs\|S∗=0\]\\displaystyle\\Pr\(S^\{\*\}=1\)\\mathbb\{E\}\\left\[\\sum\\limits\_\{s=1\}^\{\\tau\}g\_\{s\}\|S^\{\*\}=1\\right\]\+\\Pr\(S^\{\*\}=0\)\\mathbb\{E\}\\left\[\\sum\\limits\_\{s=1\}^\{\\tau\}g\_\{s\}\|S^\{\*\}=0\\right\]≤\\displaystyle\\leq\(1−δ\)​12​I​J​βT​ln⁡\(T\)Δ\+δ​T≤252​I​J2Δ​ln3⁡\(T\)\+I,\\displaystyle\(1\-\\delta\)\\frac\{12IJ\\beta\_\{T\}\\ln\(T\)\}\{\\Delta\}\+\\delta T\\leq\\frac\{252IJ^\{2\}\}\{\\Delta\}\\ln^\{3\}\(T\)\+I,where the last two inequalities are from takingδ=IT\\delta=\\frac\{I\}\{T\}in Proposition[9](https://arxiv.org/html/2608.11383#Thmproposition9)and \([3](https://arxiv.org/html/2608.11383#S4.E3)\)\. Plugging theϵ=ΔK​Cμ\\epsilon=\\frac\{\\Delta\}\{KC\_\{\\mu\}\}in Lemma[1](https://arxiv.org/html/2608.11383#Thmlemma1)into Proposition[8](https://arxiv.org/html/2608.11383#Thmproposition8), then𝔼⁡\[T−τ\]\\mathbb\{E\}\[T\-\\tau\]can be bounded by1\+K3​C2​Cμ2Δ2\+K3​C2​Cμ2Δ2​ln⁡\(T\)1\+\\frac\{K^\{3\}C^\{2\}C\_\{\\mu\}^\{2\}\}\{\\Delta^\{2\}\}\+\\frac\{K^\{3\}C^\{2\}C\_\{\\mu\}^\{2\}\}\{\\Delta^\{2\}\}\\ln\(T\)\. And by Proposition[4](https://arxiv.org/html/2608.11383#Thmproposition4), we can show that regret of the online algorithmO​NONis at most1\+I\+K3​C2​Cμ2Δ2\+K3​C2​Cμ2Δ2​ln⁡\(T\)\+252​I​J2Δ​ln3⁡\(T\)1\+I\+\\frac\{K^\{3\}C^\{2\}C\_\{\\mu\}^\{2\}\}\{\\Delta^\{2\}\}\+\\frac\{K^\{3\}C^\{2\}C\_\{\\mu\}^\{2\}\}\{\\Delta^\{2\}\}\\ln\(T\)\+\\frac\{252IJ^\{2\}\}\{\\Delta\}\\ln^\{3\}\(T\)\. ∎

## 7Numerical Experiments

we consider a network revenue management problem with multiple resources\. There are33types of customers and55types of products, and44types of resources \(I=3,J=5,K=4I=3,\\ J=5,\\ K=4\)\. The customer features are of dimension33and are independently drawn from the uniform distribution on interval\[0,1\]\[0,1\]\. The product features are of dimension55and are independently drawn from the uniform distribution on interval\[0,1\]\[0,1\]\. Set the arrival ratesμi=1\\mu\_\{i\}=1,i=1,…,Ii=1,\\ldots,I, the arrivals of different classes are independent and the capacity of the resources areT∗bT\*b, where the vector of the average capacities per unit time is given byb=\(1,1,1,1\)b=\(1,1,1,1\)\. The coefficientsaj​ka\_\{jk\},j=1,…,5;k=1,…,4j=1,\\ldots,5;k=1,\\ldots,4, form the bill\-of\-materials matrix as follows:

\[10100010111100000001\]\\begin\{bmatrix\}1&0&1&0&0\\\\ 0&1&0&1&1\\\\ 1&1&0&0&0\\\\ 0&0&0&0&1\\end\{bmatrix\}And for the payoff matrixAA, we consider two cases:

A=\[1036124571831015\]​and​A=\[1549234571831015\]A=\\begin\{bmatrix\}10&3&6&1&2\\\\ 4&5&7&1&8\\\\ 3&1&0&1&5\\end\{bmatrix\}\\textbf\{ and \}A=\\begin\{bmatrix\}15&4&9&2&3\\\\ 4&5&7&1&8\\\\ 3&1&0&1&5\\end\{bmatrix\}
We compare three following algorithms based on different learning and optimization schemes\. The horizon length isT=10000T=10000periods\. Each problem instance is simulated10001000times\.

1. 1\.Algorithm Re\-UCB: The proposed algorithmO​NON\.
2. 2\.Algorithm UCB: Online updating without re\-solving \(see Algorithm in Appendix[B](https://arxiv.org/html/2608.11383#A2)\)\.
3. 3\.Algorithm Re\-SEP: Separated learning and exploitation with re\-solving \(see Algorithm in Appendix[C](https://arxiv.org/html/2608.11383#A3)\)\.
4. 4\.Algorithm SEP: Separated learning and exploitation without re\-solving \(see Algorithm in Appendix[D](https://arxiv.org/html/2608.11383#A4)\)\.

The performance metric is expected regret compared to the optimal reward, and the results are showed in Figure[1](https://arxiv.org/html/2608.11383#S7.F1)\.

000\.20\.20\.40\.40\.60\.60\.80\.811⋅104\\cdot 10^\{4\}005050100100150150200200250250TTTotal Revenue Lossr2=2,r1=1r\_\{2\}=2,r\_\{1\}=1Re\-UCBUCBRe\-SEPSEP

000\.20\.20\.40\.40\.60\.60\.80\.811⋅104\\cdot 10^\{4\}00200200400400TTr2=5,r1=1r\_\{2\}=5,r\_\{1\}=1

000\.20\.20\.40\.40\.60\.60\.80\.811⋅104\\cdot 10^\{4\}224466TTAverage Revenue Lossr2=2,r1=1r\_\{2\}=2,r\_\{1\}=1

000\.20\.20\.40\.40\.60\.60\.80\.811⋅104\\cdot 10^\{4\}5510101515TTr2=5,r1=1r\_\{2\}=5,r\_\{1\}=1

991010111112121313005050100100150150200200250250ln⁡T\\ln TTotal Revenue Lossr2=2,r1=1r\_\{2\}=2,r\_\{1\}=1

99101011111212131300200200400400ln⁡T\\ln Tr2=5,r1=1r\_\{2\}=5,r\_\{1\}=1

Figure 1:The expected loss under different algorithmsWe make the following observations:

1. 1\.The total expected loss under the reoptimization policy grows sublinearly with the horizon lengthTT, and appears to scale approximately logarithmically\. Although the theoretical upper bound isO⁡\(ln3⁡T\)O\(\\ln^\{3\}T\), the numerical results suggest a much milder growth rate, close to linear inln⁡T\\ln T\. This is further supported by the approximately linear relationship observed between the expected loss andln⁡T\\ln Tacross all tested instances\. These findings indicate that the policy effectively mitigates the accumulation of errors over time, in contrast to classical heuristics where the loss typically scales on the order ofT\\sqrt\{T\}\.
2. 2\.The average loss per period decreases steadily asTTincreases and converges to zero\. Moreover, this qualitative behavior remains stable across different parameter settings and horizon lengths\. This confirms that the policy is asymptotically optimal on a per\-period basis and highlights the robustness of the algorithm\. The result reflects the diminishing impact of learning errors as more observations are collected and incorporated into the reoptimization process\.
3. 3\.The results demonstrate that reoptimization plays a critical role in controlling capacity allocation, while the learning component governs the residual loss\. Continuous reoptimization prevents the buildup of capacity mismatch, and the remaining loss is primarily due to estimation uncertainty\. This explains why the total loss grows only logarithmically rather than at a polynomial rate\.

## 8Concluding Remarks

In this work, we develop a new class of reoptimization\-based algorithms for Contextual Bandits with Knapsack \(CBwK\), a fundamental model for sequential decision\-making under resource constraints\. By integrating upper\-confidence\-bound \(UCB\) learning with dynamically updated capacity allocation, our approach provides a simple and implementable framework that effectively balances exploration and exploitation in environments with heterogeneous customers, products, and limited resources\. A key innovation of our method is the use of repeated reoptimization to continually recalibrate decisions to the remaining capacity, which enables the algorithm to adapt to stochastic arrivals and noisy rewards while maintaining feasibility at every step\.

Our theoretical contribution is the derivation of an average regret bound ofO⁡\(\(ln⁡T\)3T\)O\(\\frac\{\(\\ln T\)^\{3\}\}\{T\}\)which significantly improves upon theO⁡\(1T\)O\(\\frac\{1\}\{\\sqrt\{T\}\}\)rates that characterize prior reoptimization\-based methods in related dynamic\-pricing and resource\-allocation settings\. This demonstrates the power of reoptimization not only as a heuristic—as often used in practice—but also as a tool that can be rigorously analyzed to achieve provably near\-optimal performance\. Our numerical experiments further highlight the importance of re\-solving: algorithms without reoptimization or with separated learning phases perform substantially worse, validating the structural advantages of our online reoptimization design\.

There are several directions for future work that we think would be valuable\. First, extending our reoptimization methodology to nonlinear reward structures, nonparametric models, or contextual bandits with richer action spaces may broaden its applicability\. Second, mathematical generality is indeed limited by Assumption 1\. Unfortunately, the techniques in this paper do not allow us to relax this assumption\. We leave this challenging extension to future work\.

## References

- Abbasi\-Yadkori et al\. \(2011\)Abbasi\-Yadkori, Y\., D\. Pál, and C\. Szepesvári \(2011\)\.Improved algorithms for linear stochastic bandits\.NIPS’11 Proceedings of the 24th International Conference on Neural Information Processing Systems, 2312–2320\.
- Agrawal and Devanur \(2014\)Agrawal, S\. and N\. R\. Devanur \(2014\)\.Bandits with concave rewards and convex knapsacks\.EC ’14 Proceedings of the fifteenth ACM conference on Economics and computation, 989–1006\.
- Agrawal and Devanur \(2016\)Agrawal, S\. and N\. R\. Devanur \(2016\)\.Linear contextual bandits with knapsacks\.NIPS’16 Proceedings of the 30th International Conference on Neural Information Processing Systems, 3458–3467\.
- Agrawal et al\. \(2016\)Agrawal, S\., N\. R\. Devanur, and L\. Li \(2016\)\.An effcient algorithm for contextual bandits with knapsacks, and an extension to concave objectives\.29th Annual Conference on Learning Theory49, 4–19\.
- Arlotto and Gurvich \(2019\)Arlotto, A\. and I\. Gurvich \(2019\)\.Uniformly bounded regret in the multi\-secretary problem\.Stochastic Systems9\(3\), 231–260\.
- Arlotto and Xie \(2020\)Arlotto, A\. and X\. Xie \(2020\)\.Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards\.Stochastic Systems10\(2\), 99–191\.
- Auer \(2003\)Auer, P\. \(2003\)\.Using confidence bounds for exploitation\-exploration trade\-offs\.The Journal of Machine Learning Research3\(3\), 397–422\.
- Babaioff et al\. \(2007\)Babaioff, M\., N\. Immorlica, D\. Kempe, and R\. Kleinberg \(2007\)\.A knapsack secretary problem with applications\.InProceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization\. Algorithms and Techniques, APPROX ’07/RANDOM ’07, Berlin, Heidelberg, pp\. 16–28\. Springer\-Verlag\.
- Badanidiyuru et al\. \(2018\)Badanidiyuru, A\., R\. Kleinberg, and A\. Slivkins \(2018, March\)\.Bandits with knapsacks\.J\. ACM65\(3\)\.
- Badanidiyuru et al\. \(2014\)Badanidiyuru, A\., J\. Langford, and A\. Slivkins \(2014\)\.Resourceful contextual bandits\.Proceedings of The 27th Conference on Learning Theory35, 1109–1134\.
- Besbes and Zeevi \(2012\)Besbes, O\. and A\. Zeevi \(2012, November\)\.Blind network revenue management\.60\(6\), 1537–1550\.
- Chen and Ross \(2014\)Chen, K\. and S\. M\. Ross \(2014\)\.An adaptive stochastic knapsack problem\.European Journal of Operational Research239\(3\), 625–635\.
- Chen et al\. \(2018\)Chen, Q\., S\. Jasin, and I\. Duenyas \(2018\)\.A nonparametric self\-adjusting control for joint learning and optimization of multi\-product pricing with finite resource capacity\.Mathematics of Operations Research, forthcoming\.
- Chu et al\. \(2011\)Chu, W\., L\. Li, L\. Reyzin, and R\. E\. Schapire \(2011\)\.Contextual bandits with linear payoff functions\.Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics15, 208–214\.
- Dudik et al\. \(2011\)Dudik, M\., D\. Hsu, S\. Kale, N\. Karampatziakis, J\. Langford, L\. Reyzin, and T\. Zhang \(2011\)\.Efficient optimal learning for contextual bandits\.InProceedings of the Twenty\-Seventh Conference on Uncertainty in Artificial Intelligence, UAI’11, Arlington, Virginia, USA, pp\. 169–178\. AUAI Press\.
- Edwards and Leslie \(2020\)Edwards, J\. A\. and D\. S\. Leslie \(2020\)\.Selecting multiple web adverts: A contextual multi\-armed bandit with state uncertainty\.Journal of the Operational Research Society71\(1\), 100–116\.
- Ferreira et al\. \(2018\)Ferreira, K\. J\., D\. Simchi\-levi, and H\. Wang \(2018\)\.Online network revenue management using thompson sampling\.Oper\. Res\.66\(6\), 1586–1602\.
- Flajolet and Jaillet \(2015\)Flajolet, A\. and P\. Jaillet \(2015\)\.Logarithmic regret bounds for bandits with knapsacks\.https://arxiv\.org/abs/1510\.01800\.
- Gallego and van Ryzin \(1994\)Gallego, G\. and G\. van Ryzin \(1994, August\)\.Optimal dynamic pricing of inventories with stochastic demand over finite horizons\.Manage\. Sci\.40\(8\), 999–1020\.
- Gallego and van Ryzin \(1997\)Gallego, G\. and G\. van Ryzin \(1997, February\)\.A multiproduct dynamic pricing problem and its applications to network yield management\.Oper\. Res\.45\(1\), 24–41\.
- Immorlica et al\. \(2019\)Immorlica, N\., K\. A\. Sankararaman, R\. Schapire, and A\. Slivkins \(2019\)\.Adversarial bandits with knapsacks\.2019 IEEE 60th Annual Symposium on Foundations of Computer Science \(FOCS\), DOI: 10\.1109/FOCS\.2019\.00022\.
- Jasin \(2014\)Jasin, S\. \(2014\)\.Reoptimization and self\-adjusting price control for network revenue management\.Oper\. Res\.62\(5\), 1168–1178\.
- Jasin and Kumar \(2012\)Jasin, S\. and S\. Kumar \(2012\)\.A re\-solving heuristic with bounded revenue loss for network revenue management with customer choice\.Mathematics of Operations Research37\(2\), 313–345\.
- Jones \(1989\)Jones, P\. W\. \(1989\)\.Multi\-armed bandit allocation indices\.Journal of the Operational Research Society40\(12\), 1158–1159\.
- Kleinberg \(2005\)Kleinberg, R\. \(2005\)\.A multiple\-choice secretary algorithm with applications to online auctions\.InProceedings of the Sixteenth Annual ACM\-SIAM Symposium on Discrete Algorithms, SODA ’05, USA, pp\. 630–631\. Society for Industrial and Applied Mathematics\.
- Kleywegt and Papastavrou \(1998\)Kleywegt, A\. J\. and J\. D\. Papastavrou \(1998, January\)\.The dynamic and stochastic knapsack problem\.Oper\. Res\.46\(1\), 17–35\.
- Li et al\. \(2010\)Li, L\., W\. Chu, J\. Langford, and R\. E\. Schapire \(2010\)\.A contextual\-bandit approach to personalized news article recommendation\.WWW’10 Proceedings of the 19th international conference on World wide web, 661–670\.
- Mahajan and Teneketzis \(2008\)Mahajan, A\. and D\. Teneketzis \(2008\)\.Multi\-Armed Bandit Problems, pp\. 121–151\.Boston, MA: Springer US\.
- Mehta et al\. \(2007\)Mehta, A\., A\. Saberi, U\. Vazirani, and V\. Vazirani \(2007, October\)\.Adwords and generalized online matching\.J\. ACM54\(5\), 22–es\.
- Peleg and Meir \(2008\)Peleg, D\. and R\. Meir \(2008\)\.A bilinear formulation for vector sparsity optimization\.Signal Processing88\(2\), 375–389\.
- Reiman and Wang \(2008\)Reiman, M\. I\. and Q\. Wang \(2008\)\.An asymptotically optimal policy for a quantity\-based network revenue management problem\.Mathematics of Operations Research33\(2\), 257–282\.
- Slivkins \(2019\)Slivkins, A\. \(2019, November\)\.Introduction to multi\-armed bandits\.Found\. Trends Mach\. Learn\.12\(1–2\), 1–286\.
- Slivkins and Foster \(2022\)Slivkins, A\. and D\. J\. Foster \(2022\)\.Efficient contextual bandits with knapsacks via regression\.arXiv preprint arXiv:2211\.07484\.
- Talluri and Ryzin \(2004\)Talluri, K\. T\. and G\. J\. V\. Ryzin \(2004\)\.The Theory and Practice of Revenue Management\.New York: Springer\-Verlag\.
- Thompson \(1933\)Thompson, W\. R\. \(1933, 12\)\.On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3\-4\), 285–294\.
- Vera et al\. \(2021\)Vera, A\., S\. Banerjee, and I\. Gurvich \(2021, May\)\.Online allocation and pricing: Constant regret via bellman inequalities\.Oper\. Res\.69\(3\), 821–840\.
- Whittle \(2018\)Whittle, P\. \(2018, 12\)\.Multi\-armed bandits and the gittins index\.Journal of the Royal Statistical Society: Series B \(Methodological\)42\(2\), 143–149\.

## Appendix AProofs

###### Proof of Theorem 1:

Recall the LP of \(10\) and \(15\) in the following,

min\\displaystyle\\min−∑i=1I∑j=1Jxi​jUiTYj,\\displaystyle\-\\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\},subject to∑ixi​jaj​k≤bk,k=1,…,K,\\displaystyle\\sum\\limits\_\{i\}x\_\{ij\}a\_\{jk\}\\leq b\_\{k\},\\quad k=1,\\ldots,K,∑jxi​j≤λi,i=1,…,I,\\displaystyle\\sum\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\quad i=1,\\ldots,I,x≥0\.\\displaystyle x\\geq 0\.The Lagrangian functions of them are

L\(μ,λ,x\)=−∑i=1I∑j=1Jxi​jUiTYj\+∑k=1Kμk\(∑ixi​jaj​k−bk\)\+∑i=1I\(∑jxi​j−λi\),\\displaystyle L\(\\mu,\\lambda,x\)=\-\\sum\\limits\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}\{U\_\{i\}\}^\{T\}Y\_\{j\}\+\\sum\\limits\_\{k=1\}^\{K\}\\mu\_\{k\}\(\\sum\\limits\_\{i\}x\_\{ij\}a\_\{jk\}\-b\_\{k\}\)\+\\sum\\limits\_\{i=1\}^\{I\}\(\\sum\_\{j\}x\_\{ij\}\-\\lambda\_\{i\}\),withμ,λ,x≥0\.\\mu,\\lambda,x\\geq 0\.Reordering in terms ofxi​jx\_\{ij\}inL⁡\(μ,λ,x\)L\(\\mu,\\lambda,x\)derives that−UiT​Yj\+∑k=1Kμk​aj​k\+λi≤0\-\{U\_\{i\}\}^\{T\}Y\_\{j\}\+\\sum\\limits\_\{k=1\}^\{K\}\\mu\_\{k\}a\_\{jk\}\+\\lambda\_\{i\}\\leq 0for anyxi​jx\_\{ij\}\. So we kaveμk≤UiT​Yjaj​k\\mu\_\{k\}\\leq\\frac\{\{U\_\{i\}\}^\{T\}Y\_\{j\}\}\{a\_\{jk\}\}for anyxi​jx\_\{ij\}\. thusμk≤UiT​Yjaj​k\\mu\_\{k\}\\leq\\frac\{U\_\{i\}^\{T\}Y\_\{j\}\}\{a\_\{jk\}\}\. LetCμ=maxk⁡\{mini,j⁡\{UiT​Yjaj​k\}\}C\_\{\\mu\}=\\max\\limits\_\{k\}\\\{\\min\\limits\_\{i,j\}\\\{\\frac\{U\_\{i\}^\{T\}Y\_\{j\}\}\{a\_\{jk\}\}\\\}\\\}, thenCμC\_\{\\mu\}is an constant upper bound for eachμk\\mu\_\{k\}under anyb′b^\{\\prime\}satisfying‖b′−B/T‖∞<ϵ\\\|b^\{\\prime\}\-B/T\\\|\_\{\\infty\}<\\epsilon\. Noting thatμ=rT​W−1\\mu=r^\{T\}W^\{\-1\}, so whenever‖b′−B/T‖∞<ϵ\\\|b^\{\\prime\}\-B/T\\\|\_\{\\infty\}<\\epsilon, we have thatrT​W−1​\(b′−B/T\)=μ⁡\(b′−B/T\)≤k​cμ​ϵr^\{T\}W^\{\-1\}\(b^\{\\prime\}\-B/T\)=\\mu\(b^\{\\prime\}\-B/T\)\\leq kc\_\{\\mu\}\\epsilon\. This shows that theϵ\\epsiloncan be chosen at least atΔk​Cμ\\frac\{\\Delta\}\{kC\_\{\\mu\}\}, which is in order ofΘ⁡\(Δ\)\\Theta\(\\Delta\)\. ∎

###### Definition 4\.

We definewi​tw\_\{it\}in the below to bound the pseudo regret of a type\-iicustomer arriving in periodtt, i\.e\.,

wi​t=\{Yj⁡\(t\)T​Mi⁡\(t\)​t−1​Yj⁡\(t\),i=i⁡\(t\),0,o\.w\.\\displaystyle w\_\{it\}=\\left\\\{\\begin\{array\}\[\]\{ll\}\\sqrt\{Y\_\{j\(t\)\}^\{T\}M\_\{i\(t\)t\}^\{\-1\}Y\_\{j\(t\)\}\},&i=i\(t\),\\\\ 0,&o\.w\.\\end\{array\}\\right\.

###### Corollary 1\.

For alli=1,…,Ii=1,\\ldots,Iandt=1,…,Tt=1,\\ldots,T,det\(Mi​t\+1\)=∏s=1t\(1\+wi​s2\)\\det\(M\_\{it\+1\}\)=\\prod\\limits\_\{s=1\}^\{t\}\(1\+w\_\{is\}^\{2\}\)\.

###### Proof of Corollray 1:

In this proof, we omit the superscriptiifor simplicity\. We useYt=Yj⁡\(t\)Y\_\{t\}=Y\_\{j\(t\)\}for short\. By \(8\), we have

det\(Mt\+1\)\\displaystyle\\det\(M\_\{t\+1\}\)=\\displaystyle=det\(Mt\+Yt​YtT\)\\displaystyle\\det\(M\_\{t\}\+Y\_\{t\}Y\_\{t\}^\{T\}\)=\\displaystyle=det\(Mt1/2\(I\+Mt−1/2YtYtTMt−1/2\)Mt1/2\)\\displaystyle\\det\(M\_\{t\}^\{1/2\}\(I\+M\_\{t\}^\{\-1/2\}Y\_\{t\}Y\_\{t\}^\{T\}M\_\{t\}^\{\-1/2\}\)M\_\{t\}^\{1/2\}\)=\\displaystyle=det\(Mt\)det\(I\+Mt−1/2Yt\(YtMt−1/2\)T\)\\displaystyle\\det\(M\_\{t\}\)\\det\(I\+M\_\{t\}^\{\-1/2\}Y\_\{t\}\(Y\_\{t\}M\_\{t\}^\{\-1/2\}\)^\{T\}\)=\\displaystyle=det\(Mt\)​det\(I\+vt​vtT\),\\displaystyle\\det\(M\_\{t\}\)\\det\(I\+v\_\{t\}v\_\{t\}^\{T\}\),wherevt=Mt−1/2Ytv\_\{t\}=M\_\{t\}^\{\-1/2\}Y\_\{t\}\. Note that1\+wt21\+w\_\{t\}^\{2\}is a eigenvalue ofI\+vt​vtTI\+v\_\{t\}v\_\{t\}^\{T\}, since

\(I\+vt​vtT\)​vt=vt\+vt​\(vtT​vt\)=vt​\(1\+YtT​Mt−1​Yt\)=\(1\+wt2\)​vt\.\\displaystyle\(I\+v\_\{t\}v\_\{t\}^\{T\}\)v\_\{t\}=v\_\{t\}\+v\_\{t\}\(v\_\{t\}^\{T\}v\_\{t\}\)=v\_\{t\}\(1\+Y\_\{t\}^\{T\}M\_\{t\}^\{\-1\}Y\_\{t\}\)=\(1\+w\_\{t\}^\{2\}\)v\_\{t\}\.Sincevt​vtTv\_\{t\}v^\{T\}\_\{t\}is a rank\-one matrix, all the other eigenvalues ofI\+vt​vtTI\+v\_\{t\}v\_\{t\}^\{T\}equal11\. It follows thatdet\(I\+vt​vtT\)=1\+wt2\\det\(I\+v\_\{t\}v\_\{t\}^\{T\}\)=1\+w\_\{t\}^\{2\}\. Recalling thatM1M\_\{1\}is the identity matrix, the result follows by induction\. ∎

###### Proof of Theorem 2:

In this proof, we omit the superscriptiifor simplicity\. Also, we will useYt=Yj⁡\(t\)Y\_\{t\}=Y\_\{j\(t\)\}for short\.

Tr⁡\(Mt\)\\displaystyle\\mathrm\{Tr\}\(M\_\{t\}\)=\\displaystyle=Tr⁡\(I\+∑s<tYs​YsT\)\\displaystyle\\mathrm\{Tr\}\(I\+\\sum\\limits\_\{s<t\}Y\_\{s\}Y\_\{s\}^\{T\}\)=\\displaystyle=Tr⁡\(I\)\+∑s<tTr⁡\(Ys​YsT\)\\displaystyle\\mathrm\{Tr\}\(I\)\+\\sum\\limits\_\{s<t\}\\mathrm\{Tr\}\(Y\_\{s\}Y\_\{s\}^\{T\}\)=\\displaystyle=J\+∑s<t‖Ys‖2\\displaystyle J\+\\sum\\limits\_\{s<t\}\|\|Y\_\{s\}\|\|\_\{2\}≤\\displaystyle\\leqJ​t\.\\displaystyle Jt\.The trace ofMtM\_\{t\}equals the sum of the eigenvalues ofMtM\_\{t\}\. Note thatMtM\_\{t\}is always positive definite, and hence its eigenvalues are all positive\. Subject to these constraints,det\(Mt\)\\det\(M\_\{t\}\)is maximized when all the eigenvalues are equal\. In this case,det\(Mt\)\\det\(M\_\{t\}\)is at mosttJt^\{J\}\. ∎

###### Proof of Theorem 3:

Note that wheny≤1y\\leq 1, we have thaty≤2​ln⁡\(1\+y\)y\\leq 2\\ln\(1\+y\)\. Hence,min⁡\(wi​j​s2,1\)≤2​ln⁡\(1\+wi​j​s2\)\\min\(w\_\{ijs\}^\{2\},1\)\\leq 2\\ln\(1\+w\_\{ijs\}^\{2\}\)which induces that

∑s=1t∑i,jxi​j​s​min⁡\(wi​j​s2,1\)\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}\\sum\\limits\_\{i,j\}x\_\{ijs\}\\min\(w\_\{ijs\}^\{2\},1\)≤\\displaystyle\\leq2​∑s=1t∑i,jxi​j​s​ln⁡\(1\+wi​j​s2\)\\displaystyle 2\\sum\\limits\_\{s=1\}^\{t\}\\sum\\limits\_\{i,j\}x\_\{ijs\}\\ln\(1\+w\_\{ijs\}^\{2\}\)=\\displaystyle=2​𝔼​∑i=1Iln⁡\(det\(Mi​t\)\)\\displaystyle 2\\mathbb\{E\}\\sum\\limits\_\{i=1\}^\{I\}\\ln\(\\det\(M\_\{it\}\)\)≤\\displaystyle\\leq2​I​J​ln⁡\(t\),\\displaystyle 2IJ\\ln\(t\),the second line uses Corollray 1 and the last inequality uses Lemma 2\.

By the Cauchy\-Schwartz inequality and Proposition 6, we have that

gs2≤\(2​βs​∑i,jxi​j​s​min⁡\(wi​j​t,1\)\)2≤4​βs​\(∑i,jxi​j​s​min⁡\(wi​j​s2,1\)\)\.\\displaystyle g\_\{s\}^\{2\}\\leq\(2\\sqrt\{\\beta\_\{s\}\}\\sum\\limits\_\{i,j\}x\_\{ijs\}\\min\(w\_\{ijt\},1\)\)^\{2\}\\leq 4\\beta\_\{s\}\(\\sum\\limits\_\{i,j\}x\_\{ijs\}\\min\(w\_\{ijs\}^\{2\},1\)\)\.Then

∑s=1tgs2\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}g\_\{s\}^\{2\}≤\\displaystyle\\leq∑s=1t4​βs​\(∑i,jxi​j​s​min⁡\(wi​j​s2,1\)\)\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}4\\beta\_\{s\}\(\\sum\\limits\_\{i,j\}x\_\{ijs\}\\min\(w\_\{ijs\}^\{2\},1\)\)≤\\displaystyle\\leq4​βt​∑s=1t∑i,jxi​j​s​min⁡\(wi​j​s2,1\)\\displaystyle 4\\beta\_\{t\}\\sum\\limits\_\{s=1\}^\{t\}\\sum\\limits\_\{i,j\}x\_\{ijs\}\\min\(w\_\{ijs\}^\{2\},1\)≤\\displaystyle\\leq4​βt​I​J​ln⁡\(t\)\.\\displaystyle 4\\beta\_\{t\}IJ\\ln\(t\)\.∎

###### Proof of Theorem 4:

By the updating rule \(9\) andξt=rt−UiT​Yj⁡\(t\)\\xi\_\{t\}=r\_\{t\}\-\{U\_\{i\}\}^\{T\}Y\_\{j\(t\)\}, we have that

zi​t\\displaystyle z\_\{it\}=\\displaystyle=Mi​t​\(U^i​t−Ui\)\\displaystyle M\_\{it\}\(\\hat\{U\}\_\{it\}\-U\_\{i\}\)=\\displaystyle=Mi​t\(Mi​t−1∑s=1trsYj⁡\(s\)𝟏\{i\(s\)=i\}−Ui\)\\displaystyle M\_\{it\}\(M\_\{it\}^\{\-1\}\\sum\\limits\_\{s=1\}^\{t\}r\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\-U\_\{i\}\)=\\displaystyle=∑s=1trsYj⁡\(s\)𝟏\{i\(s\)=i\}−Mi​tUi\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}r\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\-M\_\{it\}U\_\{i\}=\\displaystyle=∑s=1trsYj⁡\(s\)𝟏\{i\(s\)=i\}−\(I\+∑s=1tYj⁡\(s\)Yj⁡\(s\)T𝟏\{i\(s\)=i\}\)Ui\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}r\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\-\(I\+\\sum\\limits\_\{s=1\}^\{t\}Y\_\{j\(s\)\}Y\_\{j\(s\)\}^\{T\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\)U\_\{i\}=\\displaystyle=∑s=1t\(rs−UiTYj⁡\(s\)\)Yj⁡\(s\)𝟏\{i\(s\)=i\}−Ui\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}\(r\_\{s\}\-\{U\_\{i\}\}^\{T\}Y\_\{j\(s\)\}\)Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\-U\_\{i\}=\\displaystyle=∑s=1tξsYj⁡\(s\)𝟏\{i\(s\)=i\}−Ui\.\\displaystyle\\sum\\limits\_\{s=1\}^\{t\}\\xi\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\}\-U\_\{i\}\.∎

## Appendix BOnline Updating without re\-solving \(UCB\) Algorithm

- •Initialization: Setbk=BkTb\_\{k\}=\\frac\{B\_\{k\}\}\{T\},Mi​1=IJ×JM\_\{i1\}=I\_\{J\\times J\}andU^i​1=0\\hat\{U\}\_\{i1\}=0,i=1,2,⋯,Ii=1,2,\\cdots,I,k=1,…,Kk=1,\\ldots,K\.
- •Fort=1t=1toTT: CBi​t\\displaystyle\\textrm\{CB\}\_\{it\}=\\displaystyle=\{v:‖v−U^i​t‖2,Mi​t≤βt\},∀i∈\[1,I\],\\displaystyle\\\{v:\\\|v\-\\hat\{U\}\_\{it\}\\\|\_\{2,M\_\{it\}\}\\leq\\sqrt\{\\beta\_\{t\}\}\\\},\\quad\\forall i\\in\[1,I\],CBt\\displaystyle\\textrm\{CB\}\_\{t\}=\\displaystyle=∏i=1ICBi​t\.\\displaystyle\\prod\\limits\_\{i=1\}^\{I\}\\textrm\{CB\}\_\{it\}\.Note thatCBt\\textrm\{CB\}\_\{t\}is the product ofIIintervals\.
- •In each periodtt, solve the following optimization problem to obtain probabilitiesxt∗x^\{\*\}\_\{t\}\. xt∗=arg​maxx∈Dt⁡maxV∈CBt​∑i,jxij​ViT​Yj,\\displaystyle x^\{\*\}\_\{t\}=\\argmax\\limits\_\{x\\in D\_\{t\}\}\\max\\limits\_\{V\\in\\textrm\{CB\}\_\{t\}\}\\sum\_\{i,j\}x\_\{ij\}V\_\{i\}^\{T\}Y\_\{j\},where, Dt=\{x\|∑i=1I∑j=1Jxi​jaj​k≤bk,∀k∈\[1,K\];∑jxi​j≤λi,∀i∈\[1,I\];x∗≥0\}\\displaystyle D\_\{t\}=\\\{x\\ \|\\ \\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq b\_\{k\},\\ \\forall k\\in\[1,K\];\\ \\sum\\limits\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\ \\forall i\\in\[1,I\];\\ x^\{\*\}\\geq 0\\\}is the feasible region\. The inner “max” means that we choose the best potential reward based on all the possible vectors inCBt\\textrm\{CB\}\_\{t\}\.
- •Use the solutionxt∗x^\{\*\}\_\{t\}to assign the customer attt, if any, to a resource and collect the rewardrtr\_\{t\}\.
- •Update the estimatorU^i​t\+1\\hat\{U\}\_\{it\+1\}and matrixMi​t\+1M\_\{it\+1\}via Mi​t\+1\\displaystyle M\_\{it\+1\}=\\displaystyle=\{Mi​t\+Yj⁡\(t\)​Yj⁡\(t\)T,i=i⁡\(t\),Mi​t,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}M\_\{it\}\+Y\_\{j\(t\)\}Y\_\{j\(t\)\}^\{T\},\\quad i=i\(t\),\\\\ M\_\{it\},\\quad\\mbox\{o\.w\.\}\\end\{array\}\\right\.U^i​t\+1\\displaystyle\\hat\{U\}\_\{it\+1\}=\\displaystyle=\{Mi​t\+1−1∑s=1trsYj⁡\(s\)𝟏\{i\(s\)=i\},i=i\(t\),U^i​t,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}M\_\{it\+1\}^\{\-1\}\\sum\\limits\_\{s=1\}^\{t\}r\_\{s\}Y\_\{j\(s\)\}\\mathbf\{1\}\_\{\\\{\{i\(s\)=i\}\\\}\},\\quad i=i\(t\),\\\\ \\hat\{U\}\_\{it\},\\quad o\.w\.\\end\{array\}\\right\.

## Appendix CSeparated learning and exploitation with re\-solving \(Re\-SEP\) algorithm

In this algorithm we have two stage: the exploration stage and the exploitation stage\. LetLLbe the length of the exploration stage and we will choose a properLLlater\.

- •Stage 1 \(Exploration\) 1. 1\.Assign exploration match: assign theii\-th type customer to resource from11toJJsequentially and periodically\. 2. 2\.SetU^i=0\\hat\{U\}\_\{i\}=0andMi=IJ×JM\_\{i\}=I\_\{J\\times J\}fori=1,…,Ii=1,\\ldots,I\. 3. 3\.Fort=1t=1toLL, do: Collect rewardrtr\_\{t\}, and update the estimatorU^i\\hat\{U\}\_\{i\}and matrixMiM\_\{i\}as U^i\\displaystyle\\hat\{U\}\_\{i\}=\\displaystyle=\{\(Mi\+Yj⁡\(t\)​Yj⁡\(t\)T\)−1​\(Mi​U^i\+rt​Yj⁡\(t\)\),i=i⁡\(t\),U^i,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}\(M\_\{i\}\+Y\_\{j\(t\)\}Y\_\{j\(t\)\}^\{T\}\)^\{\-1\}\(M\_\{i\}\\hat\{U\}\_\{i\}\+r\_\{t\}Y\_\{j\(t\)\}\),\\quad i=i\(t\),\\\\ \\hat\{U\}\_\{i\},\\quad\\mbox\{o\.w\.\}\\end\{array\}\\right\.Mi\\displaystyle M\_\{i\}=\\displaystyle=\{Mi\+Yj⁡\(t\)​Yj⁡\(t\)T,i=i⁡\(t\),Mi,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}M\_\{i\}\+Y\_\{j\(t\)\}Y\_\{j\(t\)\}^\{T\},\\quad i=i\(t\),\\\\ M\_\{i\},\\quad\\mbox\{o\.w\.\}\\end\{array\}\\right\.
- •Stage 2 \(Exploitation\) 1. 1\.Count each amountbkb\_\{k\}of type\-kkof resource used in Stage 1 and reset the averagebk​L=Bk−bkT−Lb\_\{kL\}=\\frac\{B\_\{k\}\-b\_\{k\}\}\{T\-L\}fork=1,…,Kk=1,\\ldots,K\. 2. 2\.Fort=L\+1t=L\+1toTT, do: 1. \(a\)Solve the following optimization problem to obtain probabilitiesxt∗x^\{\*\}\_\{t\}in periodtt x∗t=arg​maxx∈Dt∑i,jxijU^iTYj,\\displaystyle x^\{\*\}\_\{t\}=\\argmax\\limits\_\{x\\in D\_\{t\}\}\\sum\_\{i,j\}x\_\{ij\}\\hat\{U\}\_\{i\}^\{T\}Y\_\{j\},where,Dt=\{x\|∑i=1I∑j=1Jxi​jaj​k≤bk​t,∀k∈\[1,K\];∑jxi​j≤λi,∀i∈\[1,I\];x≥0\}D\_\{t\}=\\\{x\\ \|\\ \\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq b\_\{kt\},\\ \\forall k\\in\[1,K\];\\ \\sum\\limits\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\ \\forall i\\in\[1,I\];\\ x\\geq 0\\\}is the feasible region\. 2. \(b\)Update the capacity allocated to periodt\+1t\+1, bk​t\+1=bk​t−\(dk​t−bk​t\)T−t,∀k∈\[1,K\]\.\\displaystyle b\_\{kt\+1\}=b\_\{kt\}\-\\frac\{\(d\_\{kt\}\-b\_\{kt\}\)\}\{T\-t\},\\quad\\forall k\\in\[1,K\]\. 3. \(c\)Use the solutionxt∗x^\{\*\}\_\{t\}to assign the customer attt, if any, to a resource and get rewardrtr\_\{t\}\.

The above algorithm give you a total rewardR=∑t=1TrtR=\\sum\\limits\_\{t=1\}^\{T\}r\_\{t\}based on the realization of solutionxt∗x^\{\*\}\_\{t\}\. According to[Chen et al\. 2018](https://arxiv.org/html/2608.11383#bib.bib13), an optimal tuning parameter forLLis to setL=k​TL=\\sqrt\{kT\}, wherekkis a fixed number\.

## Appendix DSeparated learning and exploitation without re\-solving \(SEP\) algorithm

In this algorithm we have two stage: the exploration stage and the exploitation stage\. LetLLbe the length of the exploration stage and we will choose a properLLlater\.

- •Stage 1 \(Exploration\) 1. 1\.Assign exploration match: assign theii\-th type customer to resource from11toJJsequentially and periodically\. 2. 2\.SetU^i=0\\hat\{U\}\_\{i\}=0andMi=IJ×JM\_\{i\}=I\_\{J\\times J\}fori=1,…,Ii=1,\\ldots,I\. 3. 3\.Fort=1t=1toLL, do: Collect rewardrtr\_\{t\}, and update the estimatorU^i\\hat\{U\}\_\{i\}and matrixMiM\_\{i\}as U^i\\displaystyle\\hat\{U\}\_\{i\}=\\displaystyle=\{\(Mi\+Yj⁡\(t\)​Yj⁡\(t\)T\)−1​\(Mi​U^i\+rt​Yj⁡\(t\)\),i=i⁡\(t\),U^i,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}\(M\_\{i\}\+Y\_\{j\(t\)\}Y\_\{j\(t\)\}^\{T\}\)^\{\-1\}\(M\_\{i\}\\hat\{U\}\_\{i\}\+r\_\{t\}Y\_\{j\(t\)\}\),\\quad i=i\(t\),\\\\ \\hat\{U\}\_\{i\},\\quad\\mbox\{o\.w\.\}\\end\{array\}\\right\.Mi\\displaystyle M\_\{i\}=\\displaystyle=\{Mi\+Yj⁡\(t\)​Yj⁡\(t\)T,i=i⁡\(t\),Mi,o\.w\.\\displaystyle\\left\\\{\\begin\{array\}\[\]\{ll\}M\_\{i\}\+Y\_\{j\(t\)\}Y\_\{j\(t\)\}^\{T\},\\quad i=i\(t\),\\\\ M\_\{i\},\\quad\\mbox\{o\.w\.\}\\end\{array\}\\right\.
- •Stage 2 \(Exploitation\) 1. 1\.Count each amountbkb\_\{k\}of type\-kkof resource used in Stage 1 and reset the averagebk​L=Bk−bkT−Lb\_\{kL\}=\\frac\{B\_\{k\}\-b\_\{k\}\}\{T\-L\}fork=1,…,Kk=1,\\ldots,K\. 2. 2\.Fort=L\+1t=L\+1, solve the following optimization problem to obtain probabilitiesx∗x^\{\*\} x∗=arg​maxx∈Dt∑i,jxijU^iTYj,\\displaystyle x^\{\*\}=\\argmax\\limits\_\{x\\in D\_\{t\}\}\\sum\_\{i,j\}x\_\{ij\}\\hat\{U\}\_\{i\}^\{T\}Y\_\{j\},where,D=\{x\|∑i=1I∑j=1Jxi​jaj​k≤bk​L,∀k∈\[1,K\];∑jxi​j≤λi,∀i∈\[1,I\];x≥0\}D=\\\{x\\ \|\\ \\sum\_\{i=1\}^\{I\}\\sum\_\{j=1\}^\{J\}x\_\{ij\}a\_\{jk\}\\leq b\_\{kL\},\\ \\forall k\\in\[1,K\];\\ \\sum\\limits\_\{j\}x\_\{ij\}\\leq\\lambda\_\{i\},\\ \\forall i\\in\[1,I\];\\ x\\geq 0\\\}is the feasible region\. 3. 3\.Use the solutionx∗x^\{\*\}to assign the customer attt, if any, to a resource and get rewardrtr\_\{t\}\.

We still chooseL=k​TL=\\sqrt\{kT\}, wherekkis a fixed number\.