Contextual Online Pricing with (Biased) Offline Data
Authors: Yixuan Zhang
Ruihao Zhu
Qiaomin Xie
Venue: NeurIPS 2025 poster ()
Keywords: online pricing
offline data
distributional shift
robustness
Primary area: general_machine_learning

Abstract: We study contextual online pricing with biased offline data.  For the scalar price elasticity case, we identify the instance-dependent quantity $\delta^2$ that measures how far the offline data lies from the (unknown) online optimum. We show that the time length $T$, bias bound $V$,  size $N$ and dispersion $\lambda_{\min}(\hat{\Sigma})$ of the offline data, and  $\delta^2$  jointly determine the statistical complexity.  An Optimism‑in‑the‑Face‑of‑Uncertainty (OFU) policy achieves a minimax-optimal, instance-dependent regret bound $\tilde{\mathcal{O}}\big(d\sqrt{T} \wedge (V^2T + \frac{dT }{\lambda_{\min}(\hat{\Sigma}) + (N \wedge T) \delta^2})\big)$.  For general price elasticity, we establish a worst‑case, minimax-optimal rate $\tilde{\mathcal{O}}\big(d\sqrt{T} \wedge (V^2T + \frac{dT }{\lambda_{\min}(\hat{\Sigma})})\big)$ and provide a generalized OFU algorithm that attains it.  When the bias bound $V$ is unknown, we design a robust variant that always guarantees sub‑linear regret and strictly improves on purely online methods whenever the exact bias is small.  These results deliver the first tight regret guarantees for contextual pricing in the presence of biased offline data.  Our techniques also transfer verbatim to stochastic linear bandits with biased offline data, yielding analogous bounds.

Contextual Online Pricing with (Biased) Offline Data
Yixuan Zhang
Ruihao Zhu
Department of Industrial Systems Engineering University of Wisconsin-Madison yzhang25540visc..ed
SC Johnson College of Business Cornell University ruihao zhiiiooolu@coreellll edu
Qiaomin Xie
Department of Industrial & Systems Engineering
University of Wisconsin- qiaomin. wwwamin..ieewwieee wwwwwiseeewee..ooo edu
Abstract
We study contextual online pricing with biased offline data. For the scalar price elas- ticity case, we identify the instance-dependent quantity 52 that measures how far the offline data lies from the (unknown) online optimum. We show that the time length bias bound V, size N and dispersion Amin ( of the offline data, and 8² jointly determine the statistical complexity. An Optimism in-the-Face-ot Uncertainty (OFU) policy achieves a minimax-oon -optimal, instance-dependent regret bound ÓldT A (V²T + Auii (N)+ )). For general price elasticity, we estab-
AT
dT and provide Amin a generalized OFU algorithm that attains it. When the bias bound V unknown, we design robust variant that always guarantees sub-linear regret and strictly improves on purely online methods whenever the exact bias small. These results deliver the first tight regret guarantees for contextual pricing in the presence of bi- ased offline data. Our techniques also transfer verbatim to stochastic linear bandits with biased offline data, yielding analogous bounds.
lish a worst-case, minimax-optimal rate Óld'T (V2T
Introduction
Contextual online pricing [11,2] models the real-world task in which a firm, upon observing customer- specific features, sets a price, observes the resulting demand, and then adjusts future prices to maximize long-term revenue. central challenge here is to continuously balance exploitation-una the current estimated optimal pricing strategy to maximize immediate revenue-witt exploration- testing alternative prices improve those estimates. Importantly, most firms already maintain extensive historical pricing -ata that are free to use and impose opportunity cost on current revenue. Leveraging these logs can shorten the costly exploration phase, reduce the risk of customer churn from sub-optimal prices, and provide valuable information on rare infrequent contexts. Motivated by these observations, recent work [31] introduced the framework of Contextual Online Pricing with Offline Data (C-OPOD) and showed that if the offline data are unbiased-tha is, drawn from the same distribution as the forthcoming online data data- incorporating them enables an online policy outperform purely online learning approaches.
In practice, distributional shifts are ubiquitous. For instance, historical iPhone pricing data often differ from current patterns because of competitor moves, product upgrades, and evolving economic conditions, making the no-shift assumption unrealistic. Recent research therefore starts explore the use of biased offline data. In the degenerate K-armed bandit setting (with no context and finite
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

actions). recent work [10] showed that, given offline data and information of the bias, one can design an algorithm that outperforms the canonical online method and attains matching upper and lower regret bounds.
However, the method and results of [10] do not translate directly to contextual online pricing, where contextual information, a continuous action space, and pricing-specto structure must be accommodated; naive extension incurs sub-optimal regret (see discussions under Theorem 1). To fill this gap, in this work, we formulate and study the Contextual Online Pricing with Biased Offtine Data (CB-OPOD) problem.
1.1 Main contributions
Impossibility Result. We first demonstrate in Corollary that, with access to an offline pricing dataset only, no policy can uniformly outperform the contextual online pricing algorithm in [2] without further information on the discrepancy between the offline and online data distributions.
Algorithm design and analysis. To sidestep the impossibility result, we start by assuming the firm knows a bias bound V on the true distributional shift between the offline and online data distributions. We develop algorithms and regret guarantees for two scenarios: the scalar price-elasticity case that the market-baselle feature is dj -dimensional, while the price-elasticity feature is scalar (d2 = 1), and 2. the general CB-OPOD setting that further permits d2 > 1.
1. For the scalar price elasticity setting, we identify the first instance-dependen quantity 82 that measures how far the offline data lies from the (unknown) optimal price strategy and governs the statistical complexity of CB-OPOD. We propose the Contextual Online Offline Pricing with Optimism (CO3) algorithm with a novel three-ellipsoid constructed confidence set. Our
algorithm achieves a minimax-ope oottiml instance-dependent regret bound Ô (dvVT A (V²T-
J,T Amtn (2)++N where Amin (Σ) measures the dispersion of the offline data and N denotes its sample size. Under certain conditions, this can be tightened to ( Our results also recover the OPOD regret in [7] when V = O while improving the bounds and relaxing the offline data assumptions in [31]. We provide a summary in Table and detailed descriptions in Section 3.
2. For the general CB-OPOD setting, we propose the General Contextual Online-Offline Pricing with Optimism (GCO3) algorithm and establish a minimax-optimal, worst-case regret bound ((1 d2) A (V2T (d)+ This result provides the first guarantee for general (3
CB-OPOD with either biased or unbiased offline data. In addition, our techniques apply directly the stochastic linear bandit setting. thereby subsuming the result for the K K-arm bandit setting [10]. These results are summarized in Table and discussed in details in Sections 4.
Robustness result. If the bias bound V is unknown ahead, we propose the Robust Contextual Online-Offie Pricing with Optimism (RCO3) algorithm for the general CB-OPOD setting. By choosing parameter a E (0, h), RCO3 can achieve regret no larger than ( and also ( regret when Virue is relatively small. To the best of our knowledge, this is the first robust algorithm for CB-OPOD. These findings are summarized in Table and explained in details in Section 4.2.
1.2 Related work
In this section, we provide a brief overview of closely related work and defer a comprehensive discussion to Appendix B.
Online learning with external (biased) information. Online learning with offline information attracts growing attention. [24, 19, 7, 29, 31] show that one can achieve improved regret when utilizing unbiased offline data appropriately. [23, 32, 30, 10, 14] further consider the case where offline data can be biased. Meanwhile, Bayesian methods such as Thompson sampling (TS) can leverage biased offline data construct the prior for online learning, but misspecified priors may lead to regret bounds worse than purely online approaches [20, 16, 26), e.g., an additional ( when the prior is off by which exceeds the bound in Table 1.

---

Setting
Offline data
Bias bound
Regret
[[]
I
V 0
O(VTA A Amn (N)+
T
S [31]
I,
F
V = 0
(divT A (NATIO2
S (Theorem 1)
I
V is known
OdivT' A (V²T+
di
Amin
(2) (NAT)
G (Theorem 3)
I
V is known
( d2) (V2T
(d di+d
Amin
(Theorem 5)
I
V is unknown
+ if V2 ST
Table 1:
Summary of our results and the most related work online pricing with offline data. Here, N denotes Non-contextual online pricing, S denotes Scalar price elasticity, G denotes General contextual online pricing, I denotes Li.d. demand fluctuations and F denotes Fixed pricing policy.
Online pricing. Online pricing has also garnered significant interest. Under linear demand function, [15] and [2] establish @(vT) minimax regret bound in the non-contextual and contextual settings, respectively. Built on these, [7] study the impact of unbiased offline data in the non-contextual setting and [31] extend this to the contextual setting with fixed policy that collects offline data. It is worth noting that in [31], due the fixed policy used to collect offline data, the minimax regret is worsened, and cannot recover the non-contextual result in [7]. This because the fixed policy may limit the offline data dispersion and the regret incorporates the randomness in the offline data. In contrast, we make no such assumptions on the offline data, which allows a tighter minimax regret over all possible offline data, and it also recovers the non-contextual setting [7] when offline data is unbiased.
1.3 Notations
Throughout this paper, we use || denote the Euclidean norm. We use O(-). o(-). and 2(-) to denote upper, tight, and lower bounds on growth rates, respectively; analogously, Ó(), Õ(-), and
((-) further hides the logarithmic factors. We also use A S B, A Σ B and x B to indicate A E O(B), A ((B) and A (B),, respectively. For any a, b E R. denote A = min (a, 6}. Given a matrix M, we let Amin(A)) and Xuaax (M) represent the smallest and largest eigenvalues of M, respectively. We denote Pr arg mejae |x cl for any a, b, R.
2 Problem setup and preliminaries
In this section, we introduce the model of the CB-OPOD problem. We also present an impossibility result that emphasizes the importance of information on the offline data.
Online model. Consider a firm that sells products over horizon of T periods. each period t = 2,2,..... ... T. the firm observes contextual information (c.g.. category. brand, origin, and other attributes) about the incoming product. We denote by I₃ E Rd1 the feature vector affecting baseline demand, and by Yt E de the vector governing price elasticity. We assume that the online feature sequence {21, Y1), (I2, U2),..., (rr.gr)} is independently and identically distributed (i.i.d.) with support set X' x y C Rd. period I, the firm sets a price pt (potentially based on historical data), after which the random demand D, is observed. We adopt the following linear demand model [21, 2, 4]:
D. = a x,
VePt Cr Vt E [T).
where 0, := B.) @t C Id:+dd denotes the unknown demand parameter that lies in a set et, and fal121 is an sequence of independent random demand fluctuations with zero mean and is R -usbuaaussinn. We highlight that linear demand model is both classic [15, 5, 21] and actively studied [2, 4, 25, 18). Moreover, [5] show that semi-myopic policy based on a linear model converges to the optimal policy for an unknown (possibly nonlinear) true model under suitable regularity conditions and attains minimax-optimal regret. Therefore, in this work we focus on the linear demand model (1). Extending our results to general nonlinear models and analyzing model misspecification are left for future work.
3

---

For the demand (1), the first term a. 2, represents the baseline market size, and 3_ represents the price sensitivity. For a fixed parameter = (a, 9) E @e and context (I, v) E X x y, the firm's expected revenue from charging price is given by rp æ, y) = p(a' x + yp). Then, the firm's single-period optimal price and optimal expected revenue defined
(ar, v) = arg max (p, and
rg (1 v)
max re (p, 2.0) p20
920
Next, we introduce the following assumption on the online model.
Assumption 1. For online model, we assume
1. Ot and X' x y are compact sets and there exist positive constants O'aax Smax, 2max and ymax such that ||a|| O'max || S 9max |||||| S Fmax and ||y/| S Ymax for all (a, E O and (x. X x y
2. B [[ and Elyivi are positive definite.
There exist positive constants las Un lø and us such that la S aaxx un and la S -BT S up for all ()) E OT, v) E X y. Consequently, the optimal price satisfies po (2, y) E [1, u) for any (a, B) Ot, where 1 == fu. and a y
ua. 2
2ug
Assumption a standard regularity condition in contextual-pricing studies [2, 4, 18]. In the case d2 1, Assumption further guarantees constant Ymii > 0 such that ly| Ymin for every y.
Offline data model. In practice, the firm does not know the exact values of (a., but has access to pre-existing offline dataset prior to the online learning process. Suppose this dataset consists of N samples {(0, Hn: Pn: Da)]ne[N]] [e[[N] where (fn, 9n) E X x y for all n E [N]] For each [N] the demand realization D, under the historical price pa is generated according to the linear model:
D. a In + 3r OnPn. + En:
where 6 : := E Ot are the unknown offline demand parameters. The fluctuations {&r [N[]]- independent of features and prices ((im: In. Pa)) form sequence of independent, zero-mean R- R-subgaausiann random variables, and are the only source of randomness in the offline dataset. We
use Σ
Σx ΣV
.V
T InP,O TT 0AP2.
to denote the offline Gram matrix.
S.g.r
Ey.
Pricing policies and performance metrics. We consider the design and analysis of pricing policies for firm that does not know the true 6, nor the distribution of the i.i.d. online feature ((1e. helr- At the time f, the firm proposes the price as an output of policy function n. that takes all the historical information by time - and the current feature (xie, yt) as input arguments. That is,
P: (e(((nn In, Pn,
((T,, Us. Ps. D.)) =E[t-1]: Ut, Wt).
We denote II the set of all such policies = (IT, . The set II includes all policies that are feasible for the firm to execute. For any policy æ E II, the regret of n, denoted by R2 Ro (T), is defined as the difference between the optimal expected revenue generated by the clairvoyant policy that knows the exact value of 0, and the expected revenue generated by pricing policy n, i.c.
T
R7. o. (T) =
rō. (I1, re. (pe. Fe, 91)
The expectation is taken with respect to two sources of randomness: 1) the randomness in online features {(x,, 8t) and 2) the randomness from both offline and online fluctuations {ên JuejN] and (ce We treat the offline feature -pice tuples (ê.,, 9n- Pn)) bn))n as deterministic, imposing no distributional assumptions. Consequently, our regret is defined conditional on realized offline data. An unconditional bound can be easily obtained by taking additional expectation over the offline feature-price tuples and applying standard concentration inequalities to the data-dependent terms in our regret bounds.

---

An impossibility result. We first present an impossibility result on the CB-OPOD problem without any information on the bias of the offline data.
Corollary 1 (Impossibility Result). Under Assumption for any policy Il without the prior knowledge the exact bias Virue | 0_11, we have (e (e))et xet Royo. (T) ((VT).
Corollary states that, even with access to offline dataset, any algorithm will face a worst-case scenario where it cannot outperform the purely online algorithm [2] without additional information or constraints on the discrepancy between the offline and online models. practice, bias bound V 2 | - 0x1 can be estimated with robust ML techniques [6] or via cross-validation [9]. Hence the above lower bound is conservative, motivating the study of more practically relevant settings that admit tighter regret guarantees. Corollary follows directly from Theorem 4, so we omit the proof.
3 Scalar price elasticity
In this section, we assume that the firm has access to bias bound prior to the online phase. We focus the setting d2 1. where the price elasticity is scalar. For this setting, make the following assumption on the offline data.
Assumption 2. There exists positive constant > O such that Xuni (Ex,z) c.N.
Assumption 2 implies that the offline market base-demand features are sufficiently well-covered. We remark that Assumption 2 is directly satisfied by choosing = 1 for the OPOD problem [7]. Furthermore, [31] assumes that (an]nE and {xx he(n are i..d., which implies that Assumption holds with high probability. Hence, our Assumption 2 is no stronger than those in [7, 31J.
Importantly, we first define the offline empirical price strategy p(x, y) and introduce the generalized distance 5² between ò(I, y) and the true optimal price strategy Pt. (I,, 3) as follows:
p(x,y) AT AT/U v(x,y) E X and 8² = E...v(((6 y) - pš. (z. v))?),
(3)
where Å : S-15.. = arg min Enn Rn - Unf.)) represents the ordinary squarss estimator that best fits the linear relation A in RJ UnPn in the L2 sense. To the best of our knowledge, our definitions of p(z, y) and 82 are the first to expose the intrinsic connection between contextual offline data and online pricing. In the special case where the problem reduces to OPOD (i.e., context and all features equal 1), p(z,, y) simplifies the classical average price p N- En Pre [7]. Choosing appropriate forms for and 6² is critical; Appendix C.1 provides detailed discussion.
The quantity 82 measures the deviation of the offline data from the (unknown) optimal pricing strategy, and thus plays crucial role in guiding the algorithm's behavior: a small 82 suggests the algorithm can primarily rely on the offline data for exploitation, whereas a large 82 indicates the need for additional online exploration. Since 82 is unknown, adapting to it introduces challenges in both the algorithm design and the regret analysis. We elaborate on these issues in the next subsection.
3.1 The CO3 algorithm: upper and lower regret bounds
Building on the above definitions, we propose the Contextual Online-Offting Pricing with Optimism
(CO3) algorithm, which follows the celebrated Optimism in the Face of Uncertainty (OFU) principle [1]. In contrast to traditional OFU methods and online pricing approaches with unbiased offline data on a single confidence ellipsoid, our CO3 algorithm incorporates the biased offline dataset by constructing confidence set as the intersection of three ellipsoids at time t:
[7, 31], which typically rely
C = dd ||0 &I,N S Wi,N, 110 0. S &. .. ||0 0el1s. S we
(4)
where Σ, is the online Gram matrix, Σ,,N the combined onlinc-offline Gram matrix, and Óe and êr are the corresponding least-squares estimators (see Appendix A). We choose the constants (W.,N, Wy, we) properly to ensure that that 0, E C, with high probability (ef. Lemma 5). Then, the CO3 algorithm proceeds in two stages: (i) an offline test to decide whether to rely on the offline empirical pricing strategy ğ during the online phase; and (ii) otherwise, pricing optimistically with respect to C.
5

---

Algorithm C03 Algorithm
Input: Offline data {(En Pu:Pn: Dn) nE[N regularization parameter X, {(wr, Wr wy 1120 defined in Appendix A with 1/T² and bias bound V.
1: if mingeconet Ex= (f(2n; Bn) pă (an, 0n))2
Manin. Amia (E(ex"]] max (2) and
mas Miros
max(V2 Amin (2) S T/22 then
P evaluating if by itself is enough
2:
Charge P: = Projir ( vc)) for t E (7].
3: else
4:
for 1 1,2, .... do
5:
Observe context vector (t);
6:
if 1 n @t * @ then
7:
Compute (pt, 0.) arg pa p (a (aTx, + Byyp); Charge price p::
8:
> optimism with respect to C,
9:
else Charge Pt- = I;
10: end Observe D.-
11: end for
12:
end if'
We highlight that the three-ellipsoid confidence set Algorithm 1 is designed to capture the best of three worlds. (I) Online safery. The constraint ||0 0el1z. Σ we follows as the classical purely online algorithm, thus guaranteeing regret no larger than Ö(VT). (2) Offline-boosted estimation. The Euclidean condition ||0 - d.. || S vi,,N leverages the offline data to sharpen the estimate of 0.. (3) Aggressive exploitation. Intuitively, a large 82 implies that the offline data lie far from the true optimum, so pricing decisions close to p" simultaneously promote exploration and exploitation. The ellipsoid ||0 ||,,v S Wr,N, paired with the UCB pricing rule (Line of Algorithm 1), allows the algorithm to set prices well away from the offline estimate ý (see Lemma 9), thereby exploiting the market more aggressively when 82 large. Earlier pricing work with unbiased offline data [7, 31]
relies on a single ellipsoid | &..vlls.. I WL,N, which can perform worse than purely online algorithm when the offline data is biased. The work K-armed bandit with biased offline data [10] employs two confidence intervals; however, their technique does not extend to contextual pricing with infinitely many actions and fails to capture the dependence the instance-dependen quantity 8².
With unbiased offline data, [7] showed sharp phase transition governed by 82: (1) when the offline data is highly informative- spriiv--isspciiillll..l 8² S 1//min (Σ) S T-1/22 offline data alone suffice, so online exploration is unnecessary; (2) otherwise, larger 6² boosts both exploration and exploitation. We extend this principle to the biased setting: (i) if the offline data remain informative despite the shift, i.e. 5² < max (X (V², 1/ /mmnn((E) < T-112 then simply deploying the empirical policy ő achieves regret ()² (ii) otherwise, a larger 5² accelerates both exploitation and exploration, leading to lower overall regret. Since 5² is unknown, in order to adapt to the two regimes, we introduce an offline testing phase (Line 1 of Algorithm 1) new for contextual pricing with biased offline data-to determine whether employing P is sufficient. The following theorem provides an upper bound on the regret of Algorithm
Theorem 1. Let æ be Algorithm 1. Under Assumptions I and for any possible 0.) E O x e such that 1,6% 0.11 S and for any 2 1,
O (52T), if S max(V2
Amiin 15 1/22
R7. 8. (T) E
o d1 log T (V2T
Tlgg
D T Tog Amin (N)+(NAT))*
otherwise.
Amin (E)
We first remark that the regret of Algorithm always satisfies 17 R_ (T) E Õ(VT), ensuring that the algorithm is never worse than purely online strategy. Theorem refines the regret guarantee in line with above insights (i) (i)(ii). the offline data is further well conditioned -iaitiioodd--sscificllllllll -specifically when Amii (Σ) x Amax (E), a condition commonly satisfied in price experiments [2, Lemma 1]-the regret scales as TA (V²T+ Amin (N and improves further to ( in special corner
d.
regime. Crucially, smaller bias bounds V and larger dispersion Amin (É) of offline data yield lower

---

regret. In particular, if the bias bound is small with V2 E 1/2), the regret becomes strictly smaller than (T)T) whenever either of the following holds: Amin (2) E 12( indicating strong dispersion that sharpens the estimate of 0.; or (N A T) 8² (((T)), meaning the offline data is sufficient and far from the optimum with a large distance, thus accelerating both exploration and
exploitation. Conversely, when the bias bound large, i.c., V2 E Q((=1/2)) Algorithm I cannot beat the baseline rate O (v
When V = O. Theorem reproduces the OPOD bound of [7] and improves upon the C-OPOD bound of [31]: if N, Amin (2) - 0c, our theorem implies zero regret, whereas [31] yiclds (log" 2 T) at best. We remark that the techniques and results developed for the degenerate K Karrmed bandit [10] do not carry over. Applying their method directly here yields regret term VT (rather than the sharper V²T) and cannot capture the dependence on the key quantity 8², as they fail to exploit the special structure of CB-OPOD. We summarize the main technical challenges and highlights in Appendix C. and provide the full proof in Appendix
Lower bound. To establish lower bound, we first specify the admissible policy class
II = f (6L (81,8))E
Rig,0 o. (T) S Ku (logT)) ^o, for some constant Ko, do
sup
IT contains every policy whose regret uniformly bounded by Ö(VT) over all pairs of offline and online demand parameters. Given offline data, V 2 0 and 8², we define
J = {(0', 8.) E et x @l |10" - 0.1l S V, Ez,y((((2, y) P5 v)) E [(1 - E)6², (1+ + E)
This class contains problem instances with specified bias upper bound V and (approximate) gener- alized distance 8². The following theorem provides a lower bound on the regret for every π E IT,, which incurs some instance in J.
Theorem 2. Under Assumptions and 2, Vx E II and any & E (0,
Ω (82T)
if S max V2
1 SSTTTT111
Am
sup RØ (T) (01.0))ET
E
á (TTVVT++ + Amtn (
T
otherwise,
As discussed under Theorem 1, when the offline data is well conditioned, the lower bound in Theorem 2 matches the upper bound of Theorem up to linear factor in d1. Key technical challenges and highlights are summarised in Appendix C.2 and the full proof appears in Appendix E.
4 General price elasticity
In this section we extend both the algorithmic design and the regret analysis to the general CB-OPOD setting with price elasticity of arbitrary dimension d2 E Z,.
4.1 The GC03 algorithm: upper and lower regret bounds
Building the idea of CO3, propose the General Contextual Online-Offline Pricing with Opti- mism (GCO3) algorithm. Unlike CO3, GCO3 incorporates the biased offline dataset by constructing the confidence set the intersection of only two ellipsoids.
Algorithm 2 GC03 Algorithm
Input: Same input Algorithm 1.
for / = 1, 2..,...77 do
Same procedure the for-loop of Algorithm 1, except for updating C,
f Rdiidd ||0 d. s di,,N 110 0.l1s, S wx
end for
The confidence set C₁ keeps the regret at most Õ(VT) while fully exploiting the offline data to refine the estimate of 0., giving the optimal dependence the bias bound V, the dispersion Amin Am),()).
7

---

and the horizon T. For the general CB-OPOD problem, however, a clean analogue of the instance- dependent distance 8 is still unknown; such quantity may not exist in every online-witd seaiine-wtt-offiiee offti-oflinee setting. In the K Kaarmed bandit case, for example, [10] show that the fundamental difficulty is governed solely by V and term of the same order as Amin (2). Defining appropriate distance metric for richer contextual environments remains an attractive open problem. The following theorem gives upper bound on the regret of Algorithm 2.
Theorem 3. Let be Algorithm 2. Under Assumption for any possible (0,,, 0.) E Ol x such that 110 - 0.11 S V and for any T 2 1, Rig 0_ (T) E ( (d1+dd)))))))) +2)) logT I A (V²T + (di+d, log
Amin (2)
As with Algorithm 1, Algorithm 2 never performs worse than the baseline Ö(VT) rate. Theorem sharpens this statement. If the bias bound is small with V2 E O(T-11/3 and the dispersion strong with Amin (É) E (VVT), the offline data are informative and Algorithm 2 attains regret strictly below Ö(VT). Conversely, when either the bias bound is large, i.e., V2 E (2(T-1/2) or the dispersion is weak, i.e., Amin(() ((VT)) the offline data add little value and the Algorithm 2 cannot improve on ((VT), Theorem 3 is proved by adapting the argument for Theorem 1; see Appendices E. and E.1.2. Because the steps are nearly identical, the proof omitted. Notably, the design of Algorithm 2 and its regret-upper- bound analysis extend seamlessly to the stochastic linear bandit with biased offfine data, thereby recovering the K aammed bandit result of [10]. Further details appear in Appendix I.
0-1l S V). The next Lower bound. Given 2 O, we define J == {0' 0.) Ot et 116:
theorem provides regret lower bound that every policy x E IT must incur on some instance in J.
Theorem 4. Under Assumption 1, VT E II. sup(o,,0.E) RØ 8. (T) E a (VVTA Amin (2)
T
The regret upper bound of GCO3 in Theorem matches the lower bound of Theorem up to a linear factor in dimension (d1 + d2). The full proof appears in Appendix G.
4.2 Robustness
We now consider the setting in which the firm does not know the bias bound V. The objective is to design a policy whose regret is sub-linear for every exact bias Veruey and that beats the Ō benchmark whenever Virne is small. When the offline dispersion is weak, i.c. Amin (Σ) O(VT). Theorem shows that such performance impossible. We therefore focus on the well-conditioned regime in which Amin (É) = O(T9) for some 3 > 5. We next introduce the Robust Contextual Online-Oflline Pricing with Optimism (RC03) algorithm and explain the intuition behind its design.
Algorithm 3 RC03 Algorithm
Input: Test length T and all inputs of Algorithm except the bias bound V.
for t 1, ,, do
T
Charge Pt uniformly from u3;
end for
Calculate 8. = (á', { = do.N and 0, 0r..
if [|Ø] - 0. < 2 where f is defined in Lemma 14 then
Charge P: arg max p- (a' + BT yc)) fort = T I....,T.
else
Run pure online algorithm [2] for t = T" + I....,T. T end if
Algorithm 3 starts with test phase of length T' O(T for some a E (0, f). Choosing a < keeps the test regret O(T') = o(VT), while a > 0 prevents lincar growth of total regret. Prices in this phase are sampled uniformly, producing an estimate of f.. With this estimate we test whether the exact bias satisfies Virue T T if Virue a22), the algorithm switches to pure-online policy; Verue E (T--222, relies on the offline regression estimate Ø and prices accordingly. The next theorem specifies the admissible choices of I" and bounds the regret of Algorithm 3.
8

---

Theorem 5. Given 3 > 1/2, the optimal choices of a is a (max(0,1- 53,2) Let π be the Algorithm 3. Under Assumption 1, for any T 1, and for any possible value of (0", 0.) @l Ol,
(O + d2) do)gTlogT) T), ÖT + T)
if TT=; otherwise.
RØ 90 (T)
Theorem 5 shows that the optimal test length, T (TT), lies in the interval or E (max
9), 2). Within this range there is dominant choice ultimatly it depends risk tolerance. Choosing a smaller reduces regret whenever Virue S 7a-1, but raises the worst-case rate to Ti-a Fixing a, the regret as a function of Viuu exhibits three distinct phases. Phase 1: when Virue 7 the offline data is highly informative and the regret dominated by the T test period. Phase 2: for 7 < V < T the value of the offline data wanes; the regret rises and peaks around Viuuc x T Phase 3: once V true- T the test phase correctly detects the shift and the algorithm reverts to pure-online behaviour, so the regret falls back Ó ((VT). This phase transition is visualised in Figure 1. To the best of our knowledge, Theorem 5 provides the first robust guarantee for CB-OPOD, The proof appears in Appendix H.
Cumulative regrot
T12
-0-
T-
T-2
Exact bias square Viuc
Figure 1: Piecewise regret bound as a function of exact bias square V2
5 Numerical experiments
In this section, we conduct numerical experiments on synthetic data to assess our algorithms, leaving experiments on real data for future work. Specifically, we evaluate CO3 (or GCO3 when d2 > 1) against four baselines: 1) UCB: a pure online UCB policy that ignores the offline data, 2) UCB-Offline: the UCB policy of [7, 31], which forms its single confidence ellipsoid from the combined offline and online data, 3) TS: a pure online Thompson Thompson-sampling sampling policy and 4) TS-Offline: Thompson-sampa sampling with a prior fitted to the offline data.
We randomly generate two online models: general case with d2 5. In both cases the offline data is drawn from market with exact bias Virue OT and dispersion Amin (Ê) (T)) We compare C03/GCO3 against four baselines under two bias-bound settings: a tight bound V = 1.1 Virue and a loose bound V Virue- Every configuration is averaged over 20 independent trials with T = 1000 rounds; shaded bands indicate 2-sigma error bars. Figures 2(a)-(b) reveal several trends. First, UCB-Offline and TS- Offline rely uncritically the biased offline data and accumulate regret faster than the pure-online baselines, illustrating the danger of ignoring distributional shift. Second, when the bias bound is tight (V = 1.1 Virue). CO3/GCO3 decisively outperform every baseline, in line with Theorems and 3. Finally, even under a loose bound (V 10 V.rue). C03/GCO3 track the performance of UCB and incur additional regret, demonstrating the algorithms' "never-worse" safety property.
scalar price elasticity case with d2 1 and 2)
We next evaluate RCO3 in the general setting with d2 5. A single online model is randomly generated and fixed, and ten independent offline datasets are generated, each with dispersion
Amin (\) (T") but different exact biases Vi E ((T5)/5) for offline-on online instance we run RC03 with test phase of length T ((T1/4) (a 1/4) and compare it to the pure-online UCB baseline, repeating each policy 20 times. Figure 2(c) reports the mean cumulative regret at T 5000 with a 2-sigma error bar a function of V Virue- The empirical pattern matches Theorem 5, When V.2 < T 3/4 the offline data is highly informative and RC03
O,...,.. 9. For every

---

outperforms UCB. As the bias increases to the intermediate range T 3/4 2 true ~ 2T-1/4 1/4, the value of the offline data diminishes; the regret of RC03 rises and peaks near V x T where the test phase just able to detect the shift. We highlight that the percentage drop in regret for small bias (Viuee X T/44 is comparable the percentage increase for large bias (T-3/4 V x T
V
though the absolute loss in the latter case is higher. For larger biases (V Virue 2 T-1/2) the test
correctly rejects the offline data and the regret of RC03 returns to the UCB level.
200
UCB
100
RC03
UCB Offine
T5
40
Cummueetvv regyet
600
T5-Offine
125
cM1-1-19b-
60
Comuascvv
100
003-10%..
40
200
200
1000
100
-1.5
-1.0
-0.5
0.0
(a) Scalar elasticity
(b) General elasticity
(c) Robustness of RCO3
Figure 2: Performances of CO3, GCO3, and RC03 compared with baseline algorithms.
6
Conclusion
We study contextual online pricing with biased offline data (CB-OPOD). For the scalar price elas- ticity case, introduce an instance-specifie metric 82 that quantifies the gap between the offline data and the (unknown) online optimal pricing strategy and an optimism- policy attains the instance-optimal regret (ddy A (V2T + Auain (21-(N22)))=) )) For general price elasticity, we
d,T
show that the worst-case minimax rate reduces to ((d + de) + (da+d))) )) and provide matching algorithm. When bias bound V is unknown, sub-linear regret and outperforms purely online policies whenever the true bias is small. Our analysis carries over verbatim to stochastic linear bandits with biased offline data.
introduce robust variant that retains
Future work includes extending to general nonlinear demand models, studying model misspecification, sharpening the dimension dependence in the CB-OPOD lower bound and, more broadly, developing suitable mnstance-speciff distance metric for general online-with-a with-offline learning. Applying our theoretical results to real-world datasets is also promising avenue for future research.
Acknowledgments and Disclosure of Funding
Q. Xie and Y. Zhang are supported in part by National Science Foundation (NSF) grants CNS- 1955997, ECCS-23397777 and ECCS SCCS-2432546.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Gah-Yi Ban and N Bora Keskin. Personalized dynamic pricing with machine learning: High- dimensional features and heterogeneous elasticity. Management Science, 67(9):5549-5568
2021. 1, 2, 5, 6. 8, 14, 15
[3] Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the 2 Annual Conference on Learning Theory-COL. 2008, pages 335-342. Omnipress, 2008.
20
[4] Hamsa Bastani, David Simehi-Levi, and Ruihao Zhu. Meta dynamic pricing: Transfer learning across experiments. Management Science, 6863):1865-1888 1881, 2022. 4
10

---

[5] Omar Besbes and Assaf Zeevi. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science, 61(4):723-739, 2015.
[6] Jose Blanchet, Yang Kang, and Karthyek Murthy, Robust wasserstein profile inference and applications to machine learning. Journal of Applied Probabilityy, 56(3):830-33 2019. 5
[7] Jinzhi Bu, David Simchi-Levi, and Yunzong Xu. Online pricing with offline data: Phase transition and inverse square law. Management Science, 68(12):55688888 2022. 2, 5, 13, 14, 15, 25
[8] Weiqin Chen, Sandipan Mishra, and Santiago Paternain. Domain adaptation for offline rein- forcement learning with limited samples. arXiv preprint arXiv:2408. 12136, 2024, 13
[9] Xinyun Chen, Pengyi Shi, and Shanwen Pu. Data-pooling reinforcement learning for personal- ized healthcare intervention. arXiv preprint arXiv:221 (tf:::22/1009999 1.08998, 2022.
[10] Wang Chi Cheung and Lixing Lyu. Leveraging (biased) information: Multi-armed bandits with offline data. In International Conference on Machine Learning, pages 8286-8309, PMLR, 2024.
2, 6, 7, 8, 13, 14, 41
[11] Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature-basee dynamic pricing, Manage- ment Science, 66(11): ():11) 44443, 2020.
[12] Benjamin Eysenbach, Shreyas Chaudhari, Swapnil Asawa, Sergey Levine, and Ruslan Salakhut- dinov. Off-dynamics reinforcement learning: Training for transfer with domain classifiers. In International Conference on Learning Representations. 13
[13] Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17, 2012. 18
[14] Wenlong Ji, Yihan Pan, Ruihao Zhu, and Lihua Lei. Multi-armed bandits with machine learningggenerteed surrogate rewards. arXiv preprint arXiv:2506. /66588 2025. 2
[15] Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymp- totically optimal semi-myopic policies. Operations research, 6265):1142-1167, 2014. 3,
14
[16] Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta-thompson sampling. In International Conference Machine Learning, pages 5884-5893. PMLR, 2021. 2, 14
[17] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
18, 28. 41
[18] Xiaocheng Li and Zeyu Zheng. Dynamic pricing with external information and inventory constraint. Management Science, 7009):5985-6011, 2024. 3.4
[19] Ye Li, Hong Xie, Yishi Lin, and John CS Lui. Unifying offline causal inference and online bandit learning for data driven decision. In Proceedings of the Web Conference 2021, pages 2291-2303, 2021. 2, 13
[20] Che-Yo Yu Liu and Lihong Li. On the prior sensitivity of thompson sampling. In International Conference on Algorithmic Learning Theory, pages 321-336. Springer, 2016. 2, 14
[21] Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates. arXiv preprint arXiv:1604.000 07463, 2016.
[22] Chengrui Qu Laixi Shi, Kishan Panaganti, Pengcheng You, and Adam Wierman. Hybrid transfer reinforcement learning: Provable sample efficiency from shifted-dynamics data. In International Conference on Artificial Intelligence and Statistics, pages 1054-1062. PMLR, 2025. 13
[23] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference Learning Theory, pages 993-1019, PMLR, 2013. 2, 13

---

[24]
Pannagadatta Shivaswamy and Thorsten Joachims. Multi-armed bandit problems with history. In Artificial intelligence and statisties, pages 1046-1054. PMLR, 2012. 13
[25] David Simchi-Levi and Chonghuan Wang. Pricing experimental design: causal effect, expected revenue and tail risk. In International Conference on Machine Learning, pages 31788-31799.
PMLR, 2023. 3
[26] Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel J Hsu, Thodoris Lykouris, Miro Dudik, and Robert E Schapire. Bayesian decision- makiing under misspecified priors with applications to meta-learning. Advances in neural information processing systems, 34:26382- 26394, 2021. 14
[27] Joel Tropp. An introduction matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2)11-230 2015. 40
[28] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv
preprint arXiv: [01 101 2010. 20
[29] Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. In International Conference Machine Learning, pages 35300-35338, PMLR, 2023,
2, 13
[30] Chen-Ye Yu Wei, Haipeng Luo, and Alekh Agarwal. Taking a hint: How to leverage loss predictors in contextual bandits? In Conference Learning Theory, pages 3583-3634, PMLR, 2020.
13
[31] Chen Wen Sabrina Zhai Advancements in Management Science: Applications to Online Retail, Healthcare, and Non-P non-Profit Fundraising. PhD thesis, Massachusetts Institute of Technology, 2024. 1, 3, 5, 6, 7, 13, 14, 15, 19,32
[32] Chicheng Zhang, Alekh Agarwal, Hal Daumé Iii, John Langford, and Sahand Negahban. Warm-starting contextual bandits: Robustly combining supervised and bandit feedback. In International Conference Machine Learning, pages 7335-7344. PMLR, 2019. 2, 13, 14
12

---

A
Additional notations
This section summarizes the notation used for algorithmic construction and the theoretical analysis.
Scalars
L
a maax + +/maxx
Gram Matrices
Σ3
Al +++ E
JaPalls yorzus
Σn,
Σg +
Estimators
arg minger": {1110)2 + E>=1(D) - -1aa 34 + y(pp))))
arg min {A11011 + Σ (Dn- (a In +3 +3TDDnD)) )nnn))² #E341+12
ON
n=1
Σ (D,- Ia TT = v(p:))
Confidence radius
Vλ. v Valas + mmax + 2log(3/e) + (d1 + d2) (1
11a
We
(di +dol
Vo + B
Amnax (E)V
tL?
Amax(()) +1
2log(6/cc + (d1 d2) log 1+
(d1 + )
Wt,N
V /A+ Amin(E)
+Rvd di d2 RV 2log(6/c)
A+Amin + V. log(6/))++(d +d2) log 1t 112
1d140213
Rvd + Ry 2lo((B/e) 2 y A (X:)
Wt.N
B Additional related work
Online learning with external (biased) informations Online learning problems have attracted significant attention in recent years, and growing body of work explores how external information can improve online learning. One line of research assumes that the external information unbiased, demonstrating that it can yield lower regret than purely online approaches [24, 19, 7, 29, 31). Another line focuses on potentially biased external information, aiming to design algorithms that perform no worse than purely online methods, yet can outperform them when the external information closely aligns with the online model [23, 32, 30, 10].
Among this second line of work, [23, 30] study online learning with (biased) loss predictor, assuming that for each time f, one has access to loss predictor m, for the i.i.d. true loss 4. They measure bias as T EE||m, [|] and show that if this bias grows more slowly than T, the regret can be further reduced. However, with only offline data, it is impossible to generate a predictor whose bias grows more slowly than T, since offline data cannot forecast online fluctuations. Consequently, this approach does not guide us in designing an algorithm that meets the aforementioned goal.
Another line of research focuses on hybrid transfer reinforcement learning. including both empirical work [12] and theoretical work [8, 22]. In the theoretical results, [8] studies offline data containing only transitions (no rewards) from another Markov decision process (MDP), while [22] examines offline data from an MDP with the same reward function but different transitions. Neither scenario reduces setting. Moreover, these works typically focus on bounding Elllg- 9" oo or the sample complexity required to learn an e-optimal policy. In contrast, our work uses regret as the performance metric.
Bayesian policies assume a known prior distribution for unknown parameters and update their beliefs through online observations. making them popular for leveraging offline data in online learning.
13

---

Thompson sampling (TS) is a well-known method of this type. However, prior work [20. 16, 26] demonstrates that a misspecified prior can lead higher regret bounds than those of purely online TS. In particular, [26] shows that TS with misspecified prior of magnitude e can incur an additional (cT99) regret. This exceeds our results Table 1, where the additional regret on the order of OV2T+ + Amin(
and the total regret never grows faster than O(VT).
[32] studies contextual bandits but does not improve on the standard online regret and require restrictive offline log (see also [10, Appendix A.IJ). By extending our Algorithm and analysis to the stochastic linear bandit with biased offline data, we obtain regret upper bounds that subsume the K-armed result of [10]; see Appendix for details.
Online pricing Online pricing has also garnered significant interest in recent years. In this setting, firm is initially uncertain about the parameters of the demand model and uses price experimentation learn them through empirical market responses. [15] establish a @(VT) minimax regret bound for the non-contextual online pricing problem, and [2] extend this result to the contexiual setting. Building on [15], [7] study the regret when the firm also has access an offline dataset from the same market. Subsequently. [31] integrate unbiased offline data with contextual online pricing but assume that the offline data are i.i.d. and generated by a fixed policy. This assumption can be unrealistic when the offline data come from an online pricing algorithm that dynamically adjusts its prices. Moreover, under a fixed pricing policy, they implicitly assume limited dispersion of offline prices and features, resulting in larger minimax regret than ours and preventing them from recovering the non-contextual result of [7].
In contrast, our approach imposes no additional assumptions on the offline data and allows it to come from an entirely different market. We further achieve tighter minimax regret bound, and by setting the valid bias bound V = 0, our framework recovers the non-contextual setting of [7].
C Technical challenges and highlights
In this section we offer detailed technical comparison between our results and the existing analyses of online pricing and argue the technical challenges and highlights our setting. The discussion is organised into two parts: 1) derivation of the regret upper bound and 2) derivation of the regret lower bound.
C.1 Upper bound
A central difficulty in deriving a fine-grained regret upper bound that depends on the generalized distance 82 is identify a valid empirical offline price policy. In OPOD, [7] implicitly set this policy to the sample mean n Σm= Pu, but offered no intuition for its validity. In the CB-OPOD setting that policy is no longer appropriate. We show that valid empirical policy naturally arises as the solution to
N (a I(a En ) = Ei En.
Å = arg min aERd
and the valid empirical offline policy is defined as p(x, v) =
AT AT When the problem reduces to
OPOD (all features equal to 1), this policy simplifies to p(x, y) = ý & Em Pm. pm. recovering the classical choice. Thus (3) reveals the more general structure underlying offline pricing data.
Although our formulation of the distance 8² (3) aligns with that in [31]. our choice of و differs. Specifically, [31] assumes that the offline data are i.i.d. under a single offline pricing policy an assumption that can be unrealistic when data are generated by a dynamically changing online algorithm. In contrast, we define á after collecting the offline data, without imposing further restrictions on how the data are obtained.
The quantities p(r,y) and 5² are central to linking contextual offline data to online pricing per- formance. In particular, Lemma (Appendix D) shows how 82 affects the accuracy of the online parameter estimate. While the statement of Lemma 9 resembles [7, Lemma 2], our proof is funda- mentally different: it accounts for contextual covariates and explicitly captures the dependence on feature dimension.
14

---

Beyond this, although our proof strategy follows the general blueprint of [7], handling high-dimensional covariates together with biased offline data introduces substantial new techni- cal challenges. While [31] also study a contextual setting, they impose restrictive assumptions on the offline data and derive looser upper bound; consequently, most of their arguments do not extend to our more general framework.
C.2 Lower bound
Previous lower-bound proofs for contextual online pricing [2. 31] use the multivariate van Trees inequality with a carefully chosen vector function C(0). To apply the inequality, they inflate the offline feature dimension to I' (or T + NN. destroying the original geometry of the offline Gram matrix and yielding bounds that depend on the dimension while obscuring the effect of offline dispersion, which too conservative. We propose a new construction of C(f) that works without feature augmentation, preserves the true dispersion of the offline Gram matrix, and produces sharper bounds for contextual pricing with biased offline data. How to simultaneously capture the explicit dependence on the ambient dimension remains open and is left for future work.
Furthermore, obtaining the optimal dependence on the bias bound V simuteneously with the optimal dependence on the time T, dispersion Amin (E), generalized distance 8² and offline sample size N is a distinctive contribution of this work and substantially complicates the analysis; see Appendices F and G for details.
D Preliminaries
This section collects several results that are useful throughout the proof.
D.1 Preliminary linear algebra results
To begin with, in this subsection, collect several linear algebra results.
Lemma 1. Given a positive semi-definite matrix M E Rdxd, positive constant X > 0 and an integer E Z, the spectrum of M(M + Aaa) is (AE(A, + >)) where {Mi is the spectrum M.
Proof. Because M is positive semi-definite, there exist an eigen-decomposittion M = QDQ-!. Therefore, have
+ -
=QDD ATa)
D(D + A D is diagonal matrix whose diagonal entries are {A?(A, + 1 Helld) thereby com- pleting the proof of Lemma 1.
Lemma 2. Let A, B Rdd > R. be two quadratic functions of the form
A(x) uA) T UA) + CA, B(x) (x uB) TBB]QQ(== uB) + CB.
where QA QB are positive definite matrixes and cp 2 0. Define AA = arg min, A(x) and TA+B arg min (A(z) + B(x)). Then, we have
Amin (Q 1122 2/ 1/2 B(xa).
A(EA+D) + (( A(TA) >
I Amin (Q 1/2 1/10Q100 1/2
Proof. Because arg min, A(x), FA+B = arg min, (A(x) + B(z)) we have
FΛ and Qa( UA) Q=( wB) = 0.
8 = MA-up up and = JA- 1----g up. Then, the above equalities imply that ( - -)) + Q which further implies that 0 = (QA Qb) -Q Therefore, we have
A(oA+B) B(xA+B) A(æa)
15

---

=(ZA-B uA) QA (EA+B ug) "BB(EA+B - uB) -B4) cB
=(0 =(0-d) 6) T 0B0
Q60 cB
=6 QQQA + QB) cc.
Next, we will find the the largest possible such that the following inequality holds:
(QB(AA ( Q4 <BB)= 0, V
We define M = Q (Q^ + QAQ For two matrices and N, we write M ž N M N is positive semidefinite Then the condition QB (QA + Qa) QA cQp is equivalent to Q!2²² (Qa QB) Q -/2 = cl, which simplifies to ž cl. Therefore, the largest possible largest is Amax (M). Meanwhile, by defining N Q Q PAQB1/
1/22 have QA Q NQ
and QA QB QB (I + N)Q Therefore, we have
M = (7 NT
Because commutes with + N, ie. N( + N) = (I N)N, N and + N are simultaneously diagonalizable, which implies
(NN)
A.(M) = 1 Ax(N)
Because is positive semi deni-defintte, we have
= Amiu (M) = Amin(N)
Amin 1010200
1 Amin (N)
1 + Amin (Q Amin
Q2Q0 11/2
Finally, because en 2 0, we have
A(xA+B) + B(TA+B) - A(rA) -8
Amin (0p 12200
8 QBô +
+ Amin 10-1/220077
Amin (Q 1/2Q40
(8 SUQ +
Amin (Q 1/2 1/2
Amin (Q 1/2Q 112
B(xA),
+ Amin (Q (021/22000000 1/2)
which finishes the proof of Lemma
Lemma 3. Let & E Rdi and y Rdda be random vectors with finite second moments. Assume that
Eirx" ] is invertible. Then
Elyy ] Elya [E[ax 11"
Proof. Let 2 = y Elyx"
EE px T1-1 xx. Notice that
E[=z T =E((v E |yx
] [oxe ] () Elyæ" T ]E T]-1a)
Elyy - EE [yr
E8 [xx E[yy I]
E EE (yx |] 1 "
[ ] )
ac:: [x::r 1 12 []]
Elyy ] Blyr |[ Exyy J--
Because E[2z 1 0, complete the proof of Lemma 3.
16

---

D.2 Preliminary contextual online pricing results
In this subsection, we collect several preliminary lemmas related to online pricing with offline data. All proofs of these lemmas are postponed to the end of this subsection.
First, present three lemmas that apply the general contextual online pricing setting, i... X' x y C Rd x Rd42 with d2 Z+
Lemma 4. Under Assumption for all (z, y) x V.0,8' E Ot, we have
Viax 2 + max u 0 0'
(o y) por (x,
20
Lemma 5. Recall the confidence set C. defined in (4). Under Assumption I, with probability at least 1 8 we have 0. E C. n At for all I. N.
Lemma 6. Consider Algorithm and assume Assumption I holds. Then, for any (0,e 3), the following event occurs for every E [T] with probability at least 1 E.
N Σ
sup ES Rec,net
(aa
a.) 2n ( Bnn
Σ (a an) x (B-3,) yp spa(s)) Fc-1
Kni
(5)
where is any empirical pricing function in period [t] that is (s 1)- measuraael K is an absolute constant, and T/. = (d1 + d2) log + log(t/E).
The remaining lemmas specialize to the scalar price elasticity setting, i.e., d2 =
Lemma 7. Under Assumption I, and with 8 defined in (3), we obtain 8² - 23 H Venax + 2n
Lemma 8. Given the offline data ((in In Pr 3) INE[N]] and any Rdd1 and B E lR, have
N
Ca an + BBOn
Σ
(aTi in AATT2)?
where À is defined in equation (3).
Lemma Suppose 82 2 Assumptions and 2, there exists a positive constant C. such that 0 E C, for each t E [T], two
CK and N8 2 (E), where C 0 is a constant. Under
sequences of events {U,,1 tt [T]] and {U2,2 [T]} hold, where
lgly Sy UA
Uz,1
En.. [(((z, we) pe(er, w)))
CK
U1.2
E.,, [10;
0.11 Amin (Σ) + (N A (t- 1))8²
Lemma 10. Given the offline dataset {IIn Yn, Pn.) li which satisfies Assumption 2, and under Assumption I, we have
2
Max Umxx
Σ (p 2n) Po. (En: 1n.))
Er.y (60x,,((x,,)) Põ. (z, u))
and
Mmin Amin [|xx=")
N
max c, 2xx m + u² 22
Σ (p(Sn) In) ppm)2
Amiu (Σ).
cy2
D.2.1 Proof of Lemma 4
For any v, y E X x y and 0, 0' E Ot, we have
a
T x
TT
1/3T
3
(x u) - (z, y) = 22 TT
2,3TT
2,3 3 y
17

---

T 1B y T 2:3'T
2
a x; y a T x3 y a axx3" y
a x: y
213
|0 - a' T'I|xmaxx UB + 113 - 3 Umax
213
Minax u + maxx u 010 0'll
21
thereby completing the proof of Lemma 4.
D.2.2 Proof of Lemma 5
We prove Lemma 5 by showing that each of the following events holds with probability at least 1- e/3: (1) |10, Ôr, v1lx..x Wr,N. (2) I10, 01,vll S Wi,, n and (3) |10. Ōel1x, S wr. Since event (3) follows directly from [17, Theorem 20.5], we omit its proof and focus on proving events (1)
and (2) in what follows.
(1) |1o_ 01,N I WA with probability at least e/3.
0, 0N, 02 -
Σ
Sn DnPn
1d,
+
St
D.)
YtPt
n=1
1 Σ
02 -Ei,
in
[[
pngn
10 + +(n)
Dt
][[ x7
pioll
10, + Ei)
VnDn
y/Pr
N
Mg,h (00 Ei0 - 0²)) +
Σ
in
Inn + Σ
Ft
EE
(6)
jnPn
YrPt
n=1
Then, we have
02)1ls,N |10- 01,NlLEEN S 1100111x.1 + +112(0, - 02)1l 2,,
+1
Σ
Inn InPr
En
+
Dtt ytPt
EEllx, 1
n=1
s=1
N
S 1110.llvo.t + +11S(0= 0¹ 1.)l
In DnPn
En
It DePe
Cellx,
A/ \vo a + Prax
Amax (
In OnPn
én
Enllvo o,N
St Dipe
cel|z,"
cel
I Amin
VA Amax
n=1
Ti
T2
where the last inequality holds by following Lemma 1 with i: -1 Then, by [17, Theorem 20.3], with probability at least c/6, the term T2 can be bounded as follows:
2 2lo((6/)) + (di + d2) log 11 t2
Zt DePt
cellz, S
(d1 d2)
Next, use the following lemma provide a high probability upper bound of term Tí. Lemma 11 (Theorem 1 in [13]). Let to (Wi...., WN be vector of independent, mean-zero, R- R-subgaussian random variables. Let M E N be a positive semi- semi-defiitte matrix. For any 2
PPwTT Mw Rd (Tr(MM + 2 Tr ( 2|| l|2t)) - exp(-t).
Then, let w = (éi,..., ET and M = A (AAT + - where A E +d2 and An in for every n [N]. Consider the singular value decomposition of A: A = U.VT. T, We
VnPn.
18

---

have
M = A (AAT + +1 A= (VYTUT) [U (IIT + +1) -1) (UXIT)
=V (EE) +11) EV.
Therefore, the nonzero eigenvalues of M are
(M (A(
1sisr.
(A))+
where r & d1 + d2 denotes the rank of and {o)(A) denotes the nonzero singular values of A. Therefore, we have ||Ml|| = max +((A)*
(A) S 1, Tr(M) S r. S d1 + d2 and
Tr(M²) S d1 + d2. Therefore, by Lemma 11 and choosing t = log(6/e). with probability at least 1 - e/6, we have
w Mw
S + +c) (1og(())))
S (Ry d1 d2 R2/llog(//))
Therefore, we have proved that with probability at least e/3,
|10_ - 01,NIlEE,N I AVammax + Pnax
Amaxe EE
11,2
+
+
2 2log(6/e) (d1 + d2) log 11
(di + d2)
A + Amin (E)
Amax (2)
+ RVd1 di + da + RV 2log(6/c) WI,N
(2) 110. N2 S uN,N with probability at least 1 c/3. By equation (6), we have
110_ 01.N11 A11 12 -1-) 12
Σ
in BnPn
+
Dt YrPt
Eell
===
in BnPn
S 111 0.11 11
0.)1 + ||
Enp +
EE|l
Y/Pt
Amax (Ê)V
N
+
in Bnon
En +
Øt yept
cells
A Amin (2)
Amax (2))
V x + Amin (2)
n=1
A A 0 + -inax +V+
In InPn
én Enllvo +
2t VePt
cell2,))
A + Amin (E)
V + Amin ($)
where holds by following Lemma with k 22 Therefore, combining the above upper bounds for the terms Ti and T2, with probability at least 1 - c/3,
2 (lg((6/e) + (di + d2) log (I+
110 - - A Av o + 32
(di (d14
Faxx
+ +V+
X A Amin
V A Amin (Σ)
Ryd1 + du + R RV2log(6// Wr,N
V A + Amin (E)
thereby completing the proof of Lemma 5.
D.2.3 Proof of Lemma 6
The proof of Lemma 6 mirrors the argument in [31, Lemma 2.5] but under weaker assumptions.
Whereas [31] requires all offline covariates {Ln, Bn)]nE(N] to be i.id. and the noise sequence
19

---

feybeet to be almost surely bounded, our analysis imposes neither condition. Consequently. Lemma 6 holds strictly more general setting.
First, we restate the Freedman's 's inequality as follows:
Lemma 12 (Freedman's 's incquality [3]). Suppose Z1, Zz...., Ze is a martingale difference sequence
with | I B for all .t. Then for any & < 1/c². with probability at least - (log2 t) have
Σ km
2
4
Σ
VarlZe Zi, ....... Zi- log
log (1/E) 2B log (1/().
Let Dp(a; V.p) E [D, xz x. Ut V.Pr p;0. = 0) J 3 p. For any (x,
X x V. p [L. u] and 0, E we have
Da(a.u.P) - (o = 1(a - d') x + (3 - B) upl
< 10 0'l V |x + ||y1
- L ||0 ||
where L is defined in Appendix A. The diameter of the demand parameter set O Rd++4, (iam(@t). ,, is definded as
diam(Ot)- sup diam(Ot) S 2/0 o + maax
0
By a standard covering number result for d-dimensional balls [28], the minimum number of points needed to cover a (2d) dimeeennnsi ball of radius
diam(e") with balls of radius 1 is at most 2
(1 + diam Ltt) Consequently, there exists set hn of cardinality at most (1 + diam (et Lt) which satisfies
|||||| < di
1
Ve and 40 E e00 3u E E. 110 all S Lt
2
Lt
For any E (z, y) X x v E [1, u]. take v to be the closest point to Mr, we have
(Do(a, Do. (I, v,P))² (Do(s, 22(D((E, - D.(,,,,))) (2( Do. (x, ) 212 -11 +2(D. - (x.(x.1.))
(.l.,u,))+
- Do. (xx, U.P)
s f
+ +D((.(E..))) - Do, (x. (x.
For each fixed E Eg, let Yo, DD (z,, yo pt) - Do. (r Ve. (r..Vv.P))) p.))² Since
2 2 < (Ldiam(Ol) + 2)² B
|Yreell s 12 - 0.112 < L (ddiam(
& for all [T], we apply Lemma 12. In particular, if [7a] I 1 22, then with probability at least the following holds:
1 - (logz t) |
&
E YY, Fa-1l ΣY
Yu, S
Var (Yo.. [F-1] log (|1/) /E.) + 2 log (12))/E)).
By applying union bound over all E E, in the inequality above, we conclude that, with probability least 1 & loga I, the following holds:
E Yos F.-1] - Σ Y I
Σ Var (Yo.s FF-1]lop ((Ex//E) + 2B² log (|E,) 16x)
20

---

82,0 [Fs-1] log /Ex) + 2B² log (|E+1/5)
t
< 8B
E [Y I Fs-1]llog (1Ee (1E) + + log (/Ex)/E)) Ve E Ex.
This implies
2
8 El Fa-1ll 4B /og (12x)/83)
S 1883 (1E,1/E) + Σ Y v.o
which further implies
68.3 log ((2,) /Et) 2
Σ Yu 2 Σ E (Y, FF-1]] = Σ
(Do (1, Do_ (2. (
Then, with probability at least
Er 5.l0g24 L, for any 0 E O
2
E (Do (z.V.Pa) Do. (I. 1
< 2 Σ E
(Do (I, - Do. (H.V)Pa)) Fa-1]
5=1
2
136B log (|Ex) /Ei) +
Yu, +
(8)
[
s=1
where is the closest point to 0 in Σg. By the definition of C,, for all 0 E C. n nt, we have
Yo,s < 2
Yo.s + +
(Do vt, - Do(ae, yt, Pt)))
s=1
2
< 2
Yo,+ +
(9)
1.'
s=1
Then, by equations (8) and (9), with probability at least 1 - Ee log 1, for any 0 E C. net,
N
2 Σ (a
3.) (2,1)) 2
E
Σ
(a (a-aa)) a.) 4n (3+ (3) BnPm))
+
x x T
F
==1
s=1
N
(a - aw) T In + (B B.) BnPm))
+
E
(De (z, M.P.) - De. (x, v.P)) Fo-1
n=1
N
(a (a==a) a.) T In + (B 3.) Bnbm)
136B² log /E/) + 8 > Yo.
10
n=1
#=1
N (a-a in (3 B.) BnPn)
2
10
Σ Yo,s
136B log (EE,1/E) +
Then, by choosing ?)- 3 we have
E, log t <
t=l
1=2
Therefore, with the definition of C, and Lemma with probability at least 1 E C, for any 0 E C, ntt,
E
(a-a.) a.) T Sn + (33 - 8.) InDm) )²
2 +
Σ
(a o.)) x x x 3.) uP.(z,1)) 2 |
1=1
==1
21

---

<16w + 1-36B2 log ((E+1/5)) + 10
10
$160 + 133BB + d2) log(1 + diam(@") + +lg((t/E)) +
<K(wi, + (d, + d2) log T + log(!/E)),
where K is uniform constant such that the last inequality holds. Therefore, we finish the proof of Lemma 6.
D.2.4 Proof of Lemma' 7
E
y Dz11
8² Ex,,((((,)) -Po (x, (0) = Eny(
Pb. (x, 8))
S--1
Bz
2B
y. 2
)2) + 2u.
By
2.52 max
2
E
--1
2,2
+ 2u²
2 max max
x
y max u2
+ 2u
1z0²
thereby completing the proof Lemma 7.
D.2.5 Proof of Lemma 8
N
N Σ n=l
Σ
(a
En + 30npp))
(atn + -,AAT,,, 2,
n=1
N
N
(UmPn)² - -(A (AT2.)) 2n)) 21
-2,a²
Σ
In BnnPn - -A + B2 Σ
n=l
n=l
(
(AT -(a
(10)
where the last equality holds by the definition of Á. Let v = (i1P1.... )TPN)T R. x = E Nxd and U be the subspace spanned by the columns of X, the term (10) can be reformulated as ( -IIlo Because ||o||| 2 [v)],, we have
N
Σ (aTa, in + 30
Σ
(a TT fn + TTAA 2 O.
thereby completing the proof of Lemma 8.
D.2.6 Proof of Lemma 9
Let Dai == ā. a, and ABt B, - B.. When equation (5) holds, we have
(aa an + AB:rpnn)
(aa x ABIyp Fe-1
< Km
Vt E [T].
(11)
We now prove Lemma 9 by considering the following four cases.
Case 1: A& = 0. By equation (11), we have
K Kmp_1 2 do; Er Ao, + (t - 1) TF(2:0r Ti
22

---

Ami (Ex,e) 1)Amin (B(zr ()) I 1|2
M (cN Amin (E)) + (t- 1)Amin (B(xx")) "D) ||
where the last inequality holds by Assumption 2 and the fact that Σx,r is a principal submatrix of Σ. Then, have
K 1
110 -0.112 = ||aa/l2 v
(12)
(cN V Aminl (2)) + (t Am (B(rx T)
Ami (5) (N (1 - 1)) (F(exx J))
C CiKri-
(13)
Amin (E) (N A (1 11)22
m0ax 4 18
maxx
+2u
where Cj = max Amini
} and the last inequality holds by following Lemma 7.
Then, by inequality (12), we have
Ex Ex,(((((,,)) v) - pe(a, x))3
Bn (0(z, 1) - p" (xr,)))] Ex
(z, (x
pc 8))²
(2max + umaxx 0.11
@ 1
2
6²
2
413
200
1
(Viuax + xmmax u C1 K2n (i) 82
413cN
where holds by Lemma 4 and (ii) holds since the assumption that 8² (Vans ". t 23 Kn,
HoN
Case 2: A, # 0, 2
1x Ar Vanase u²
1 4yfun u² Amina (E) Iex "T
By equation (11) and Lemma 8, we have
Kn 2
Σ Da En. + AB(Aēn) )²
2
+
1
Σ (Da x))
(AST (x,
1)Mmin (10 1xxxx TD) 1|)
2 (cN V Amin (b])] Dar + 3 +
(t 1) u² A
2
|
x2
PiaxXiaxx u²
(t - 1mmin (E|xx
I)Il Darll
2cNN Amin (
|A
2
2
- (t - 1) 2²
A
(cN Amin (E)) Aa,l
(1 (B(rr 1
4
4
where the last inequality holds because Yt 2 / /wotnan Meune 2²
4y Ayma u²2 Amna (3|wx 1)- Then, we have
4K 1 (1 77.
10. 0.112 [1+
+1++)11400
)1laar11
78
(cN V Amin (E)) (1 1))min TE E(xxx'
4Knī (1 + ( 402 à 10 Wirna a² A damin (3|rrx 1) Ay u²
(14)
(cN V Amiin (E)) + (t 1) E 11x00 T]
4K AKn211 (1 + ( (ans Wanee 222 A Ammi (3/oxx 1) 4u uz
Auin (Σ) + (N A (t 1mi [xxx TD
C2KTi
(15)
Amiu (2) + (N A (t 11-1)))82
23

---

where C22
4(1 +
x²
Amin (B|par 4 u²
C). Then, by inequality (14), and proceeding as in
da Vinna
Case 1, we have
1 0²
(Wiaa uaa + xmax 2
C2K
8²
Ex (x,,((((z.)) Pe (((.,)))
2
4/3cN
4
(
Me + t 2 C2
where the last inequality holds since the assumption that 8²
CoeN
Case 3:
A
0,
1y u
and
| A,6rA12 2
Amin 2z ")
(A.,.)
By equation (11) and Lemma 8, we have
8ugu((1 Zugal Da
N
clglymin 1sl
Kop 2
Σ
AaTTa, in + ABrddn))
2 cNVl + AAMI12
SuBu + Zuzu ))
n=1
which implies
110, - -0,11= = 11==(11+00 (1 S CaKiji1
(16)
N8
203K
2C K0 Kn/
Amin (2) + N82
Amin (D) + (N A (t - 1))82
where C33
Sup u((1 augg zuga m
(1+( 4m Menax e
Ammin [2 "D> )) and (i) holds since the assumption
4
that N82 2 Amin ()) Then, by inequality (16), and proceeding as in Case 1, we have
8²
(ymax u + 22 (maxx2)) Knp-1 52
Ex,,(((E,))) (e(2,)))1
Nog
( u tx? 1²) Kn?
where the last inequality holds since the assumption that 82
I.N
Case 4:
A
*
0
2 Vina
4 Auii (F(pz T and | + A3,A8² <
(A3:)).
By optimizing the left hand of inequality (11) with respect to
Suyu((1+ 2ug= )=
Aat, we have
min E K Knp-1 aERd1
Σ (a ABrinin)
Σ (a x (3,
(a Ta E(a
min cER n=1
+ Amin EE 1x
T - 1/25
E [.:0 -1/2)
(a To + (8)))(0,10))
Er..y
1) + Amin
[E] TT
1/25.
1/2) E |x00 7
(Ey.v Dy أ y ) (A
Amin RB (1:0 1/22
B
Bl
1/2)
+ (t 1) + Amin
E E
(āTn I + (2,))(
EE 2xxxxT1
1/2 S
[2:00' 7 1123)
Aminn (E)
Amaxe 15 (1.))²
2(Ey.1
Syy.r $-15 - (AB.)²
Ersy
A x + - v))
(t-1) +
Amia
Amaz (E
cN((2
A x x 2)
2(iy.. - Eد اسكريعةة (1 + (I - 1) 1)xiaxx + c. EZ.y
24

---

2(E0.0 Ey Sy 5 2., (AB.)² + 3 Umin E Biz
Σ (0(x, v) - ps (1., (x)
(t - 1) 1 + ccN
+ cN(L 1)08yymin (A.;)²
lsl
2 (nn - Sy.e E-15 ais 2.y1 x (1,3,)²
Sugu
(t 1)x + +cN
N (S) + cV - 1)02 Vinin
lol
(t-1).mms + c.N Sugu
A
(A3))²
where ā arg mR Ex (a + A3.9.d)) - AA (i) follows from Lemma 2; (ii) is obtained by induction and (iii) holds because E.g Ey S $-1 bryy the the Schur complement of Σx in Σ. Because z+y 2 sAy there exists positive constant C4 such that 2
CyKai-1
| = (1+ (A)B))
Amin (E) + (N A (t 1))62
To provide upper bound on Ez.y (p(z, (z, v) - Pe 7), we have
(AB,) 2 Ba 1( ((-A" x + ypr (z. v))
B2,y((A xA6, B, + A Beupi (z. u))²
En.yl I( - T x + A 3.3pp (x, u)) - En,, [(a, x + A3,A x
@ lgl
Bx.y((-AAn Da,
ao,T x AB,upp (z. v)) Ey, (Aa, x + A xx
2uzu
1p
Ex. Br.ylc 11 1(-A A x + yp" (x, 8)) - (1 +
E y a x+ ABATT
4ugu
2ugu
12) Umin 82
lsl
(1
E ( x + A 2)
4ugu
2ugu
where (i) holds by following the similar argument in 17, EC. and the above inequality implies
Laly - (1 +
lel
Ez,yl (Aa x + A [T)
Ex Ex - (pp(x,,))}] z
Augu
2ugu
(A33)²
lalyming
lel
max Dere + A3,A112 Lalyinin 52
(1 2ugu
Augu
(A
8ugu
where the last ineqaulity holds because
||Ar+ <
-8, Therefore, 1)2
Sugu((
18t Zugu
we have
1
Lgly 82 8y Ug
Ex Ee.y((((a,)) 3) (x, v))
Ez.w ((AT ypr(z, 1))
thereby finishing the proof of Lemma 9.
D.2.7 Proof of Lemma 10
By the definition of f(:;),, we have
N
À S.
a In )²
(p(En Hn) pb, (2n, )n)
On
23300m
1
(A
Σ En
(A
23.
2,3
2
a
1|2
2
2,3
25

---

Nx max
(A
au
) 1axa I(A 2.3
Viuin Amin (TE Fx
2,3.
Nx max
a, α )91
BI(A
Mmnin Amin (x:x1
2
23
No maxe max
<
En, En (f0(,, v) Pě. (x, 1))
Vinin Amin (FE(ax)
Meanwhile, have
N
N
A in
Σ
(f(En:
pn))
pn)
Σ
A + jmPm)²
Un
Vmin n=1
n=1
x=1
Σ (u Tu In + DnDn))
min Vmin wERd,
==1
Recall that Σ= ΣN
T n CnP
inPnin phi
=
Ex. Σng
On one hand, by Assumption
y,
we have
N (u E(" In + BnDr)² < 2N 2N(xmax + u² smaxx 5
2(x + u2 ((fuaax)
min VER41 nml
Amin (r),
On the other hand, we have
E(u in + (nDn)² )2= Eng Eny,a SZ Amin (Ey. Ex St E.
min WER41
Therefore, have
Σ (p(tns 2n) - D2n)² max(1, 2(x 2(x + Vinax) 1=1
N
min (dmin (En, Amin (Ey -e
Veni
max(c, C, 2(x max + u² y2 y Amin (E);
cymmiu
where the last equality holds because Σ.y. Eny --1 Em.yy is the Schur complement of En in the matrix E. Therefore, we complete the proof of Lemma 10.
E Proof of Theorem 1
We first present the Lemma 13 that establishes upper bound for Algorithm I without checking the condition
N
Na maxx V max max(V2 (V2
max (V2 1
min BECo
(p((an Da) - (6n in))) <
and
S T 112 1/2
Vanin Amin [E(xxT))
Amiu Σ
Amin (I)
(17)
and defer the proof of Lemma to the end of this section.
Lemma 13. Let be the Algorithm I without checking the condition (17), for any (0,,0.)
{(0',0) 0) E @t x @t : 110' - A|| < V}, we have
RT (T) EO di T T (V2T di logT
Amax Amax (max(E)))Tlogg) + d,7 log T
Amin
Amin (E) + (NNAAN))))
By Lemma if 0f Co, for any 0 E Co. have
A + 82
/ (672) 67
Rydi + + R log
|10 0.1l 5 2Wa.N A Amin (2)
+V +
A + Amiin (2:)
Nmiin (2)
26

---

which implies that if Amin (E)
(E) 2 VT, there exists constant Lo > 0 such that
110 - 0.112 2 S Lo(V d1 + log T
v0 E Co.
(18)
Amin (2)
Let A be the event (mingec. Σn=1 (f(2;, D -p (2 0.))²
No2 NA
V max V2
(V2
Amnn (2) }1.
Viin Amti (B(zz
We now prove Theorem by consider the following four cases.
Case 1: max Amia (5)
} 2 VT. this case, the condition (17) does not hold. Then, by Lemma
13, the regret is bounded by
dT dT log(T) Amax (E)V log + dog Amin (2)
o dv A +
Amia (E) + (N AT) In this case, if 02 Co. we have
Case 2: 62 max
Am) S VT.
N
min DECO
Σ
(f(ān, mn) - (Bn, 2n)) =
(f(5nn Rn) Pô_ (Ens Bn))2
No Namax
Er, E2,y(((( - p² (a, u))
y Amin (E(x²?])
Nm Mmin Amin [[rx"") max (V2
Amin ($) }.
where the second inequality holds by following Lemma 10. Therefore, if 0, E Co. event A happens. Then, we have
Ro (T) (T) PA()) Σ [rō. (Ir. - ro. (Fe, P.) A] + +P(44)
rō. (Ir, - ro. (Ie, Be. A00
$ T882 +
Case max{V2 ) S VT and 82 2
Mmin Amin (E zz " (V2 di +lg
KN
max M
The constant K
Amin (E)
will be specified later. In this case, if 0, E Co. there exists 0 E Co such that
N
min RECo
Σ
(p(2n, 0n) - Pā( 1n,))
n=1
NN
1
Σ
(p(an Un) p0_ (nn)
Σ
(p/ ((inn Po. (Bns )n
2
n=1
n=l
2y Amin (EIxx" (V2 + di log T
K NN max D
N (V via + x22 x uZ) (1 0.112
Amiu (2)
413
KNx2 max Vmax
d1 log T
NLo 2 + x
2 Ug)
(V3 d1 + log T
(V2
2y Amnin
Amin (E)
4/
Amin (E)
KN max V
di + log T
4y Amnin Sxx
Amiu (Σ)
2x2 Binax
max 122
4y2 Amin [B[cxT])
Xanin (Σ)
where (i) holds by following Lemma 4, (ii) holds because of ineqaulity (18) and the last two
inequalities holds because we choose K = max(5, Lolv u2 + ma 1e Amin (B) [aa""" D).. The above
41 a2 Blaxx
inequality implies event does not happen. Therefore, we have
T
RT. 8. (T) = P(A) Σ
|ră. (It, y1) - ro. ( Br. (t) A + P((A))
rō. (xe, (1) - ro. (Fr, Ve. pc) [4]
27

---

Se'+0 (dVTToogT (V2T+ diTlog
Amax ( + doT'
Amin (2)
Amin (2) (N A T)82
Eo ddVTTogg A (V²T= d doT'og'
Amax VV Tog T + d, log" T
Amiul (2)
Amin (2) + (N A T82
Case 4: max (S5 S VT and max(V² ditlog
} S 82 1
KN maxe Vmax (V2
Amnia (5))
Pmin Anain (3
In this case, have
Amin (S.)
d 4T 8T $ V
Amin (E)
di dogT A + di doTlogT, Amiu (E)
Amax (E) ( log d,
Amin (E) + (N AT62
Therefore, no matter if event A holds not, we have
Ri a. (T) o di dogTl (V²T+ di do T Amin (2))
Amax (E)V?Tlog +, 2, Amin Amin(22) + (N A T762
thereby completing the proof of Theorem I.
E.1
Proof of Lemma 13
E.1.1 Regret is Odd loog'
For any 2 1, suppose 0, E Ct-1, then from the definition of (pe, 0z), we have
rō. (IL, Ur) ro. (xe, Ut, Pa)
pò. (st, y1 (a x. B.yIPö. (I (e)) pe(a, xt + B.y:P.)
S pā It - BeyAPrr) - pe xz + B.y(P.)
I ul| || 10: 0.llve
< 2uw illeelvv
I max/2u, 2u(ua + uwu) (1Aelly;2 11).
where define A, [NT, y:Pe] Rdi+1 and the last equality holds because 10(0,,,,1) s u(ua + uzu) and wr max (1, w. Therefore, have
|Adl A1)
1. (1t,, v1) ro. (21, Mc. Pc) max 2u(ua usu) VT
(di + +11+1 + TI2 (dl 1)A
max 2u( (ua usu) VT
2(d: + 1)
O Vogg
where (i) follows from [17, Lemma 19.4], and we use the same notation L = V x + 2 u² as in
the proof of Lemma 6. Moreover, (ii) holds because we E (V( + log by setting ó = 1/T2. Therefore, we have that the expected regret of Algorithm without checking the condition (17) is
bounded as
T
Blră, (ze, ro. (wx, Mr. Pr)] E OOd, VTlog T) + 2u(u, + upu)
O(d, (olg.))
T2
28

---

E.1.2 Rerget is O (v2T+
+ dog log T Aman (2)
By subsection E.1.1. trivial if Amin (Σ) I T If Amin(()) T2/2 2, for any t 2 1, suppose
0. Ct-1, then from the definition of (pe: 0e), we have
ro, (Iz, ve) ra. (Te, Vt, Pt) Pb. (2e, y1 (a. xs B.y.Po. (2r, pi(a, 21 + B-yeps)
(B.31) (p) (5e: pb. (Tr, we))
@ us (Mmax ug max u )10e 0.12
(19)
We u + mmax
u 1o
d1 log T
O V2
4
Amin (E)
where (i) holds by following Lemma and (ii) holds because Ui,n E OV
+
.dd log
by setting
Auniu (1)
5 = 1/T2. Therefore, we have that the expected regret of Algorithm I without checking the condition
(17) bounded
T
V2T+ + di d T
Σ Elr -((0,,))))
+ 2u(ua + ugu)
Amin (2:)
72
1=1
d log Amin (Σ)
E
V2TlogT +
E.1.3 Regret is O ( (Auma (2 log T+d T (T)
Amia (NNT)))
By subsection E.1.1, it is trivial if Amin (E) (NAT) & T1/2 By subsection E.1.2, trivial if Amin (2E) 2 (N T)82. Therefore, if Ami (N T)O² 2 T1/2 log T and Amin(E) $ (N A T)82, we have Amiu (Σ) S NO² and 8² 2 log
vN Then, by inequality (19) and
applying Lemma 9, for any t 2 1, suppose 0, E C--, we have
T
m
T
Birå, (It, Me) - ra. (Ie, Me, Pt)]
+ 2u2uua + uzu)
Amin (E) + A282
T2
Amax [2) + d1 log
+ 2u(ua + Ugu
Σ
T
1
Amin (Σ) + (N A t)82
T
1=1
where the last inequality holds because n E O(w v) E ( {2)V + di log IfT S N, we have
Amax (2) + di log!
Amax (2)12 + d1 log
O
E
Amin (E) + (N 1)82
t8a
Amax (2) log T + dj (T)
E
5²
Amax (2)V log T + di T log (T)
E
(N A T)
Amax (E) log T + do (o)
Eo
Amin (Σ) + (NA T)82
If 2 N. we have
Amax (2))v2 + d, log
Amax ( + d1 log T
Amax (f))2 + d, log T
EO
+
Amin (2) + (N A t)62
Amin (b) + t82
Amin (Σ) + N
1=
29

---

N
max (2) + di log T
Ammax (mnx(())13 d, log
E
182
Amin (E) No2
Amax V 12 log(N) d1 log ('log(N)
Amax (mm + d, log T
E
+
6²
Amin (8) NN2
Amax V log d, log (T) (N A T)82
E
thereby completing the proof of Lemma 13.
Proof of Theorem 2
For simplicity, we provide the proof under the assumption that
iid L..d (O0, 1) and &n ~
The proof proceeds in two principal steps F.1 and F.2 In the first step F.1, we will show that for any policy т E II, we have
R o. (T) E S (VVVA max 8-2 V- 8 6-2 (N 82 + Amin (2)) 1):
T
T
sup (.)
In the second step F.2, we will show that for any admissible policy æ E I1 if either of the following conditions holds: 1) 22 E 1/3-, or 2) Amin (S) E ((VT) and 8² e OTT-1/2) we have
R6 o. (T) E (2(T)).
sup (02,0)ETT
Therefore, 82 S max
S T-22 we have
Amnin (1))
T
T
R (L,.-JTT
sup
(T) 2 VT
max
8-2 + V-
8-2
+
Amin
E (((TT))
where the first inequality holds because (n A T)8 < T82 S VT.
If 52 > T/2 and 22 s 1/2 we have
1/2,
T
T
R. 0. (T) E l T max
sup (0,0.
2-21
(N A T)82 + Amin
ER(VTAV'T
T
(N (N + Xmia (E)
VV V
S 82 $ 1-2 1/2 we have
Amin(D)
T
T
Ro (T) ES VT
max
sup (EE
V-2
Amin
(Σ)
2 (
T
E En
T A Amin (2)
Therefore, combining all the cases analyzed above completes the proof of Theorem
F.1 Details for step 1
Let H, = EI, .t....,,t-1ll Et-1, 21,............................. 1t ,I...., (t-1) denotes the history before time
1- 1. We define (0',, 0.) J. Then, first apply the multivariate Trees inequality provide part of the lower bound in Theorem 2. Given w E J, H. has the Fisher information matrix:
I" (H+) Eb, 0. (H,,,,
30

---

where
Σ
:
ΣN
S.P. P
Piicet
Σ
0
(H+))
1=1
0
Tz x=1 Pelli
Σi= TiP.y
0
Given prior distribution q(-) for w on subspace W1 C J, which we shall specify later, by applying the multivariate van Trees inequality, we obtain
sup (0.0.)ET
R
w. (T) 2 sup R (T) wEW1
2 8B
B Ei Kpr Pā (2 (0)))
T
LB
B Egg Eip o. (pp - Po. (221, 3e
Eaz, (E, ((w)] 89b, (are. t'e
2
I(g) + B. E, n. (Cww) TI, (He ((w)
1=1
where I(q) Sw;
-ー -k=1 - a
(C)(w))((t)) Desk (Cz(w))(w))) पे dw and C(-) Sw,
12 + 2 is function of w that are waiting to be specified later. In what follows, we will specify the subspace W1, prior g and functions C(.) to achieve part of the desired lower bound.
We consider the subspace W defined as follows:
0.) E 22 0. VV < 0g 0. eV and 0 0 s 00. 0 + ed}
where there always exist 0 and such that W1 S J. We choose the prior q(-) defined on the W1 as follows:
T (3,, (3, Ba)
(T (3, - 3)
(3,--))
96' 0.) 2 18g+1 cos?
cos?
2cV
2cd
t (a',, - anss)
< (evu, - ai)) -ai)
II cos?
cos?
2cV
2c8
In the following, provide lower bounds by choosing 3 different functions C(-).
Step 1.1: If we choose C(w) = (0,0, a., 23²), then the following calculation applics:
E, (AA)) =
EgEg Egg 0. ((a_ x. + 233,,,95)
j=1
< 4u
Σ
B7, a. U(ps pē. (zj, 9;))
#=1
Opá. (xe, Me)
(Bul a. 10 112
Exg.y
(Bg[C(w)
1)2
= Err..n
E E((1);
Ow
2,3.11
1
I(g) E O(11 + + 5 12)
The above three inequalities imply that Ei a. Upr
1
Po. (z,, 1c)) e Ω
Σ
( + + +))) + Σラ= E3 a. [(p; p%. (2z, (6)2)
T
EΩ
8-2 V-2 Σ -
E. Eo,0.
0. 1(er - po. (fre v2)
31

---

Then, by the fact ([31, 18) that
1
min { (Td.
2/ }.
x² +o e for b > 0,C < 0, 0 implies 2
b j.
(20)
22 +
we have
R6 (T) E E VT
T
sup (.J
8-2 V-2
(21)
Step 1.2:
If we choose ((w) = (o., 2/,,, 0o: 2,3,, then the following calculation applies:
Bg 0. IIH
N
0 d4 + 23.))p))²
+
R. Eig a. [[o, 2. + 2B.95P5)
==1
N
<4u
(po. (itis (i) - p2)) + +
Σ
Kag Fig a. [0p pē. (z).
i=1
==1
<8u 2
Σ
(pa. (aiz, Uz) f(3.; 0:)) + 8u3
(p(Ri, 6.)² + 4u
Σ
B.y
8 2..9.... [105 Pē. (z 1))
1=1
1-
SN8² + Amin (8) +
Σ Eg o. Kp, - Po. (I., v;))
where the last inequality holds by Lemma 10. We also have
Exg,
(B,(C(w)T Opg. (Zt, 3t)
1)2 = Exe.y
(Egl a Øe
))²
E 2(1)
and
I(O) E O(11 299
aw
2,3.
The above inequalities imply that
T
Σ
E.
E o. l(p= P8. (Iz, 31)
t=1
EΩ
Σ
O((1 4))++ + Amin (2) +
- 1- 2== By 1_ KPB - p5. (2,, 815 )²
1=1
T
EΩ
8 2 + N82 + Amin (2)+ Σi= Ey [pp P5. (1)33)
Therefore, by the fact (20), we have
R (T) E (VTV (((VVT
T 8-2 + N82 + Amin
sup (0L,-JEE
(22)
Step 1.3: If we choose ((w) = (- 1, -Å, 1), then the following calculation applies:
E, ... IIH
A 2z + 9.b.)² + Σ E. o.
I(-A A x, + ,,
N
2
(p(2). D.) - -p:)2 + y Σ
Ey 0_ 166 Us) p))
j=1
[-1
SAmin ($) +(1 100-19 1)82 + Σ
E. R3 p. ((r, p3. (1),,,))
1=1
32

---

where the last inequality holds by Lemma 10. We also have
Ezcy (B,(C(u)) ppo. (It, M1) 1)2 Exeev
A (Bgg 2,3.1
0_ ztt 1)²
and I(u) E O((1 )
E @Q(I)
aw
23
The above inequalities imply that
T
T
Σ Eg 1p:+ - Pē. (o,, 2c)) En
+ T'82 + *Amin (2i) + E B 0_ 1(:: Pb. (o yc)
Therefore, by the fact (20), we have
RS o. (T) E EVT
T
sup (.).0))E
8-2 + T8² + Amin (E)
(23)
Combining the lower bounds in (22) and (23), we obtain
T
Rig a. (T) E VT (6)
sup
8 + (N T)82 Amin (2)) Amin(())
(24)
F.2 Details for step 2
In this step, we show that if either of the following conditions holds:
1. E 2(4-1/4),00 or
2. Amin (E) E O(V)) and 6² (
then for any admissible policy π E IT, there exists (0', 0.) E Ot x O satisfying |00 01 s V and Ez, (((ar,)) Po. (xr, y)) E (882) such that
VT
R 0_ (T) EΩ
T)
We first define two vectors of offline demand parameters and two vectors of online demand parameters as follows:
0f (a) 0 = (1), 02 = (a B3), 02 = (a2. 32).
We consider PT and PT to be the probability measures induced by a common policy स, with two different sets of demand parameters (0,,8) 01) and (62, 02), respectively. Formally, for each i 1,2,
P. (DI....D... F1........ FT, ......,uT. Di.....
Dr)
N
T
=Px (fI,...,TTT) Py (y)... vr) II o (D. Tā 3. + (irp)) II (De (aTa + BymP:))
where Px (#1...., FT) Py (y1..... VT) denotes the probability measure of online features and is the density function of the standard normal distribution. Therefore, have
Φ(x) V2T
T +
[ - az) xe + (B1 - -2)
27
KL (LT, = Σ [at o4) 2, + (8) 33)BPP
.n
(25)
Step 2.1: When V 1/44,, set
0 82
a2 (1 A)a1, 82 (1 222)31
where 1/2 and (0, 02) satisfies 110 - 01ll S and Ex,y (,pl,,( y) - ph, (z, (),,)))] E 0(8*).
Then, by equation (25), have
2 D
(PT, P5)
rr.
(a xr. + 23 )
0 01
2
33

---

T
2 2A
u3
Σ
180 00 00 [(Dt - Pd, (0t, )1))²
(26)
Then, we define two sequences of intervals 11, and 12. for all t [2] as follows:
A
A
1 = pb. (1e,. 4(1 24)
Po. Ut) + 4(1 2A)
vi E [2]
For any (2,, v) X x V/ we have
A
Al
Po, (z.y) Pb, (2 = 1- 2A Po; (a,
1 24
which implies I,, 12, 0 for every E [T]. Then, we have
r
[1= Po, (12, ue))
Σ Bg (pt ( (oe, (1))))))))
RB; 01 (T) R 02
(T) 2 1/3
Egg
13
Σ (PI (pr 11,1) P2 (pt & 12,1))
16(1 2A)²
A
T
(PF (pt $ 1.)1 + Ps (pr E h.))
16(1
2
A 32(1 24)2 T Teep(--K KL PT))
(27)
By the definition of admissible policy, we have
, (T) + Ri (T) & 2oo To
(28)
Therefore, combining incqualities (26), (27) and (28), we have pd, (J vc))
R1 (T) 2 1/ Σ 00 ((re
l
(PF,
24 uz
Lg log
TT
23 u
64Ko(1 22) (log T)
Then, by setting A E 0 [log ^)
such that
<TA2P
> 1, we have 127 (T)
VT
O (log T)
T
Step 2.2: When V E O(T-1//4, Amin Amin(()) E(VTT) and 62 < 7 1122 we set
1/2
8- = 01
8/2 = 02 02 = --((31 B2) and 82 (1 A),1,
and (0% 01) satisfies Ex.y((((r, - -P,, (z, E O(82). Then, by equation (25), we have
N
T
1
[1a1- az)" xt + (B1 - -22) voP:) )² 27
KL (PT,
<
(al (22) 24 + (B1 - 322) 0:P:
a2)T
+ 2
Σ
E0s00
oy
1=1
t=1
A 2 2
82
A y
32
max Σ
(p: -(0.. +
max
Σ Egg,o, [(5(01,00)
PPo p
2
2
I 2 Amiu (E) T82 + Σ E 01 [60() ye) pi)1|
(29)
Then, we define two sequences of price function classes I1, and Iz,0 for all t E [T] as follows:
22
4 = (pr Xx x + 11, u). Ex, (pt v) - pō, (o,(), 32(1 Aj2 J. Vie E [2].
34

---

For any (x. N' x V, we have
Ez. (P8, (z. v) Pø, (1, w))3) E.ry
01
423 x )
02
2
2/328'
0/.
(01 + AA33)) Tx y
Eu.
2311
2(1 - D)31V
A2
E Bx, 01 x + B1A y2
4(1 -A
B1y
A
Bz (2.p) (vr, v) p(2r,,11)
4(1
A)2
A
E.wyypb Ipo, (z, v)
2
1
Bn U(p (x, -0c,))((a,11 w))99)
4(1
A)2
2
A2
(12
8² 2 8(1 A)2
4(1
A)2
where the last inequality holds because 8² t EE [T]. Then, we have
1
TT-1/2
1/2
which implies I,, O I2,4 for every 2.
2
R0 01 (T) + R% R8g.00 (T)
T
Σ E [Pp - Pō, (Ie, (1))
Σ
Egg 02
(Dc
Pōg (2e, 2i))²}]
T
T
248
Σ
Eig 01.F
ERN (p)( - pb, (z., v)) 21]
+
Bigg F2.
ExN [pee(z, v) - Pāg (z. w)) )
1
(PT (pt $ 111) + Ps (pe & I2,1))
32(1 A)
1
(P (pt 1,t)) PI (pt E h.))))
32(1 A)
A
T Teep(-eppKKK P?)).
(30)
64(1 A)²
Therefore, combining inequalities (29), (30) and (28), have
R0 0, (T') 2 Lg
10 ,1 [pp - po, (or,
KL (PT. PT) T82
Amin (D)
VTA2!11
log
T88
-Amin (2).
128Ko - (log 1)
Then, because < 1/22 1/2 and Amiu (Σ). we can always set A? E O
(log T ^o
such that
VT
VT and Ro 0.00 (T) E l (log To
64Kg(1 2log (4k)(1-2A)-(oggg
Tyo Tya
G Proof of Theorem
The proof of Theorem 4 is similar to that of Theorem 2. Hence, we only highlight the key differences here. For simplicity, we provide the proof under the assumption that
Et i..d.
NOO, 1) and &n i.d.d (0.
Let H, (EI....,EE,EE, E1-1, Z1.... . 11 VI..... Bt-1) denotes the history before time f t-1. We define w = 0.) E J. Then, we first apply the multivariate van Trees inequality to provide part of the lower bound in Theorem 4. Given E J. H, has the Fisher information matrix:
I (He) Eb, 0. I,H,),
35

---

where
Σ N - B Σ Ei= D.
Σ i
P.Pr.. i= Depii.
0
0
0
I(HH)
ma ==
P.P.
J.P.o
E
yip
Given prior distribution q(-) for w subspace W1 C J, which shall specify later, by applying the multivariate van Trees inequality, we obtain
T
Ex, (B,[C(w)
Opó. (xL.. 1)2]
sup Rø (T) 2 sup Røg 0, (T) (8.00))T
44
Dee
I(q) + Ey E3g 0. (C(w) II, H (ww)
wEW1
where I[g) = Sw, jj=
2 Σ Bwj (C)(w)q(w)) Swn (Cx(w)q(w))) q(w) dw and C(-)
2d,
R22d++dd -> 22d is function of that are waiting to be specified later. In what follows, we
provide lower bounds by specifing two different the subspaces W1, priors q and functions C(-) to achieve part of the desired lower bound.
Step
We consider the subspace W1 defined as follows:
{(0'. 0x)
IR 1g2d.+24 +2d2 10 eV 0- S 0g + eV and Ø - cV s 0, S 50+eV]
where there always exist 0 and such that W S J. We choose the prior q(-) defined on the W1 as follows:
d,
π (a', -av,)
( (a..5 a.)
(z) 2d 2dg
IIcos² cos²
cos²
22d +2d
2cV
2cV
de II cos?
π (8%, Bag)
(Be, 3,)
COS?
2cV
2VV
3=1
We choose C(w) = (0, 0, at, 23.), then the following calculation applies:
t-1
Ey o. [C(w) [C(W) [((H)((()
Σ
E 0_ [(a xy +23, vsp,)
< 4u
B.g Rig 8. ((p Pě. (zz, (ejg;;))?
j=1
Opg_ (Jee, M1)
a Øt 1)² 2,1 3/1
Exc.y Mh (E,(C(w))
1)²
= Excm
(Bol233
E E1(1);
Ow
1 12).
I(g) O(11+ +
The above three inequalities imply that
Ei a. Upr Po. (z,, 91)) Ω
Σ
1
O + + E 1,12 [0p Po. (25 M1 w;)))a
T
EΩ
V-2+ DJ
E.g Big 00 lppt
Pš, (xt, Uc)))
which implies
Ro 0. (T) (
sup
R
(0,00)EE
36

---

Step 2: Let 0 = (ā. B) be the eigenvector of Σ corresponding to the eigenvalue (m), normal-
ized so that |101| ||a. 2| 3/1 We define
8 E I(a, â) T)Tx)) x))])²]]== E [(23,,(((23.. - -)²
Because we have no restriction on 8², we focus on the case that the subspace W, defined follows:
Amtn -022 1 STST-1/2 1/2 and consider
((0..0.) E 2d2 | 0. - -V S S02 S 50, EV and 0 -6 S 0. S 0 + ed),
where there always exist 0 and such that Wi S J and q(-) defined on the W1 as follows:
02 x 1/1 We choose the prior
1/2
Amiaa (S)
1
(á; ai)
π (a; ō:)
q("',
II cos
cos²
2d
V
do 8d1
2cV
2cd
d2
n (B. Bi)
π (B: B:)
II cos
cos?
2VV
2
1=1
We choose C(w) (ā. 3, a, 3), then the following calculation applies: E3 9. (C(w) (HH))C((()]
=Amin (5) +
Bg Ey 0. [(a T x. + 3T y;p;)}
<Amin (2) + 4T [1(a - x))x))² + 4u TTT 11(23. - /)TT)) ") + Σ
E 0. 0. [(a Ø3 - 23 y,p,)
j=1
SAmin (2i) + 4T'2 + Sug Σ Ey a. [(pe pd. (32,810)
Ezesh (En(C(u)) Oyg. (2 ve) Ow The above three inequalities imply that
E2(1;; and I(a) ((11 + 0((1+ (19)
E. E7. [(p Pa_ (xe, =1
EN
O(11 4)2) Amin (E) + t8² Ej= Eg Eg 00.00 [(p, Pb. (z), w;))
T
EN
8-2 + Amin (E) - TT82 + Σt
E. Ey 0. lp: - pē. (Ir, (1r1
which implies
R Re. (T) E EV(VT) (0L.0.)ET
T
sup
E
8-2
Amin { T82
Amiu
(Σ)
where the last inequality holds because Amin (S:) bounds obtained in the above steps, we have
S 82
< T-1/2 1/2
Hence, combining the two lower
sup R5 a. (T) DVTAAVVVVV 2 T (0' EET
Amin (Σ) )
thereby completing the proof of Theorem 4.
37

---

H Proof of Theorem
We begin by presenting Lemma 14, which establishes how closely the empirical bias 1|02 0.11 approximates the exact bias 110, 0.1 and defer the proof of Lemma 14 to the end of this section.
Lemma 14. Let {DDn, Tn. Dn Pn.) pn) denote the offline data and {(Dr, Zt. Yt. (t)Pe)] the obser- vations collected during the test phase of Algorithm 3. Under Assumption 1, if = 22(lo T), then with probability at least 3/ we have
|1|0", 0.11 110, - ---1l SS and
A a + maax
Rvdi d2 + RV (3/e)3/c)
Amin (5)
V + Amin (E)
(31)
Av Av amax + Pmax
Rvd1 + d2 + R RR /oggog////
+
+
À + Amin (ET))
VA+ Amin (ETr)
where
ET
Σ x=l
T"
xt Pivll ].
With probability at least
yePt
exp(- T'(a-1) 1)2 Aman Iyy ), we have 321.2
T" 1)2 mmin (Flyy") ))
Amin (ETr)
8
Because < a < 1/2 < 3, with probability at least - exp( (' Amia (Elvv)) D), 321
the quantity f
introduced in Lemma 14 satisfies
d1 + d2 + Vlgg
f SE
(32)
VTa
Fix (0, {) and set T" = T We now prove Theorem 5 by consider the following three cases.
Case Virne 3f. this case, by triangle inequality and Lemma 14, with probability at least 1 37 exp(- ('(-- 1)2 Amnn (Blyy })),
32L²
110 0.11 2 Virue |Virue - 110 - -0.1ll > 2ʃ.
Therefore, we have
Rg: o. (T) Ta (di + d2) d2) T $ (di + V
Case 2: Virne < f. In this case, by triangle inequality and Lemma 14, with probability at least 1 372 exp( (' Amn (B/ya" Ti) I))
321.
||0 0.11 S Virue |Virue - 110, -00--.111
0_11 < 2
Therefore, by inequality (19), have
RS 0, (T) S T + (T - TT Eill'' 1.1
T + T 0 V22 V??me?
$ T + 2 T (dh + d2 log T)
Amin (2)
where the last inequality holds by following inequality (34).
Case 3: f < Verue S 3f. this case, by inequality (32), we have
Ro (T') S max (I + V.2 true V22 T+ T(d1 de log T), ), (d1 + dd)
Amin (E)
38

---

ST + V22 true T T+ + T(d1 + d2 + log 1'
Amin (E)
Combining the three cases above, obtain that for any (0: 2)
o (d1 (d1 + de)vTlogT)
V22 2 9
R o. (T)
O T Vi? T
T(d. +do++o))
otherwise.
Amin (30)
When 321 1, Amim [2]
E (1) and
(d( d2) Ó Vi
T),
if V2 true 2 T
0 (T)
otherwise.
Hence no single value of a E (0, 2) is uniformly optimal: a smaller a yields lower regret when Virue I 7a-1, but increases the worst-case regret to T1-a when Virue (T)
For B ().1) and any E (0, 3). we have
O (d1 +
log (2)gTloggT)
if V2 Viue 2 T-9;
R 0. (T)
VirueT + d2
otherwise.
Amnn (2)
In this regime, choosing a = 1 B is optimal: for any Virues the resulting regret is no greater than that obtained with any a E (0, 1 3).
For B/ E (2. 1) and a E [1 - B, 22) no single choice is strictly preferred, for the same trade-off discussed in the 3 case, and we have
10 (0(() do) ( + Virue)
if true 2T otherwise.
R. (T)
Therefore, we complete the proof of Theorem 5.
H.1 Proof Lemma
1110", 0-1 1 110 - -0.1l S 110- - 0.11
110, 0-1l
For the first term |10%
0.11. with probability at least - c/3.
|10% 8.11 = V
i4 DiP:
(a 5; + ST. U.Dr + (3) Vo,1
$z Uip:
(a 8r + (.TT.pp))
\V 0-
x=
ti &ill DiPs
All All 0.11 + V|Vo
Aml
1118.1
Rvdi + dz + R (logg///
(33)
À + Amin (
VA+ + 2min (Σ)
a + Benx
RVd + + + R
(34)
X Amin (E)
VA+ + Amin (E)
where the last inequality follows from Lemma 11 and the same argument used in the proof of Lemma 5,
Similarly, for fixed {(Ie, Vt, Pt) (eetrr) with probability at least c/3.
AVagua PPaxx
Rydd + de + R R /o2lo////e V + Amin (ETr)
110 10.-0r11 A + Amin (Er.)
39

---

where we define Exe = E(=1
It
peye }. For every [T*, we have
MePr
Amin
(Elp 1
Elpp
| ye
(1ay) ())
(Elp²) Elpol Mmin (u 1)2 Amin (Elyy)) TI)
where (i) holds by following Lemma Also, by the definition of L in Appendix A, for every E [T*) have
] कं Pay. II) S L²,
max
[B
2t M:Pt
Then, by following the matrix Chernoff inequaility [27, Theorem 5.1.1]. with probability at least
1 exp( ("-=1)" Amin (Elg
321
T" Amnn (Elyy J)
Amin ETr) 2
8
thereby completing the proof of Lemma 14.
I Stochastic linear bandit with (biased) offline data
In this section, we outline that how our design of GCO3 and its regret-upper-bound analysis extend seamlessly to stochastic linear bandit with biased offline data.
Firstly, we specify the model of stochastic linear bandit with (biased) offline data problem.
Online model. Consider learner who make decisions over time horizon of T periods. round the learner is given the decision set A, C Rdd from which it chooses an action Ge E A, and receives reward
= 0_ aj T
where 0, Rd denotes the unknown online parameter vector and {me Tr2 is an sequence of independent random noise with zero mean and R Su-suaaausiia..
Offline data model. The learner have access to a pre-existing offline dataset prior to the online learning process. Let this dataset consist of N samples {â, &. he[[N-- For each n E [N), the reward realization &, under the historical action â, is generated according to the linear model
i = 0. ân + âm
where 8 is the unknown offline parameter vector (fn]ne(N) is an sequence of independent random noise with zero mean and R subgaussian. We use 5 = ΣA ānā to denote the offline Gram matrix.
Policies and performance metrics. We consider the design and analysis of policies for decision maker (DM) that does not know the true 0., the time I, the DM proposes the action a; A, as an output of policy function that takes all the historical information by time / 11 and the current feature Ae as input arguments. That is,
a1 =T= ( 2n InEN), ((a,, 2a) (e
We denote II as the set of all such policies (T ......) The set II includes all policies that are feasible for the DM to execute. For any policy æ E II, the regret n, denoted by Ri_e. (T), is defined as the difference between the optimal expected reward generated by the clairvoyant policy that knows the exact value of 0, and the expected reward generated by pricing policy ie..
T
T
T
T
R Ri..00 a. (T)
Σ tm1
max (f., a) a.A,
Σ t=l
24
E
Σ
1
o7)
Σ t=l
40

---

where we define a: = arg a. 0__ a. The expectation is taken with respect to the both offline and online random fluctuations {cn [Cn]nE[N] and (c))E(TT)-
We assume the learner knows a bias bound V satisfying V 2 |10" 0= and impose the standard condition that all online and offline parameter vectors-ar as well as all actions- are uniformly bounded.
Our algorithm constructs at each round t the same confidence set as in Algorithm 2,
C = 0 E R ||e - &1 - Wr.,, 110 -bellx. I wi
and chooses the action a, via the optimistic rule
(ae, 0+) arg max (C) and UCB.(a) max 0' BECx-1
acA:
By Lemma 12, have 0₂ C2 with high probability; hence
a7) & UCB,(a)) & UCB,(a.).
Applying [17, Eq. 19.10], we obtain
Tt = (0., aj az) s (C) (0., uz) s min ||aell ) we (aax|aaa)) ||rl]]
Ti
72
Hence, summing over the Ti terms and invoking [17, Corollary 19.3], we obtain RWr 0_ (T) Ö(dVT).
On the other hand, Lemma 5 gives WN E Ô(V + Vd Amii (5))
Summing these T2 terms we obtain
VdT Aminn (Σ)
, (T) E Ö(VT+
Therefore, we have
VdT
R 8. (T) A
(35)
Amin
Some remarks about the result (35) are in order. For general contextual online pricing with biased offline data, we obtain the regret bound ÖdvT A (V2T Xmia )). Note that the factor (V²
Vd ). in contrast to the stochastic linear bandit. This difference is the square of (V Vamia ($)
Amin (E)
stems from the special structure of the pricing problem, in which the regret can be bounded by the
second moment ||@ 0. 1?: see inequality (19). Finally, up to vd factor, the bound in (35) matches
the minimax- -otiimal regret for the K armed bandit with biased offline data established in [10].
41

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
This paper discusses the limitations of the work performed by the authors.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
42

---

This paper provides the full set of assumptions and complete (and correct) proof for each theoretical result.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: This paper fully discloses all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and conclusions of the paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
43

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
This paper provides open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //wisscc... wwt.cc/pccpppcpuiiaeeee. gwwd////e/////gg /Coaaae//ooSSSbbaaaaa
onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This paper specifies all the training and test details necessary to understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: This paper reports error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
44

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: This paper provides sufficient information on the computer resources needed reproduce the experiments. All experiments can be conducted personal computer.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tprr:////uuiss... hpppulic//ttiisooi/eieeeppp ines?
Answer: [Yes]
Justification: The research conducted in this paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of this work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
45

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
46

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
47

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy btttp::/neeuips... httpr//ps..c/ooofeeeeee//////55/ for what should or should not be described.
48


Reviews:
[{"review_id": "KAIcw1RpHG", "reviewer": "Reviewer_4jmU", "summary": "The work focuses on online pricing in the presence of biased data retrieved from previous offline interactions (not made by a specific algorithm). The authors introduce the setting and the assumptions, and present 3 algorithms to learn online in this setting, exploiting also offline data. One algorithm is for scalar price elasticity, while the others are for general price elasticity. The authors study the regret guarantees of the solutions and provide an experimental validation of their solutions.", "questions": "See weaknesses (and minors).", "limitations": "Yes. The limitations of the work are properly discussed.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths \n- The paper is well-written and structured. It is visible that the authors invested time in the writing phase to properly present their findings in the limited space available.\n- The authors, at every step, discuss what they are presenting, comparing it with the literature.\n- The theoretical analysis is formal and well-performed, and all the results are reasonable given the reviewer's knowledge of the related literature. I haven't checked carefully the theoretical analysis, but it seems to be complete.\n\n### Weaknesses\nI haven't seen any critical points for this work. However, I have some weaknesses to highlight.\n- The authors present all the assumptions in a unique \"block\" (Assumption 1). This assumption should be better discussed to allow the user to understand it properly.\n- The originality of the work is limited.\n- The experimental validation is limited and presented in a very concentrated way. However, given the theoretical character of this work, this experimental validation is sufficient.\n\n### Minors\n\n- References are often imprecise. For example:\n    [9]  -> ICML, \n    [11] -> ICLR,\n    [12] -> ECB, \n    [23] -> Single author,\n    [29] -> ICML.\n- In order to understand the algorithms, the reader has to rely heavily on the pseudocode. The presentation of the algorithms, in my opinion, should be expanded in the camera-ready exploiting the additional page.", "was_revised": true, "final_justification": "I believe that this is a good work overall and I left my overall judge unchanged. However, I was not aware of the work by Bu et al. (2020), which may reduce the impact of the work, as highlighted by the other Reviewers.", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below.\n\n**Comment 1: The authors present all the assumptions in a unique \"block\" (Assumption 1). This assumption should be better discussed to allow the user to understand it properly.**\n\nWe thank the reviewer for this helpful suggestion. Assumption 1 collects the standard conditions used in contextual online pricing (see, e.g., \\[2, 4, 16]). Because of space constraints, we grouped them into a single block. In the revised paper, we will expand the accompanying discussion to provide additional context for Assumption 1.\n\n**Comment 2: The originality of the work is limited.**\n\nWe would like to highlight three main originalities of this work:\n\n1. **Instance‑dependent parameter $\\delta^{2}$.** We introduce the first instance‑dependent quantity, $\\delta^{2}$, for contextual online pricing with offline data—whether biased or unbiased—without making any assumptions about how the offline data are generated. This parameter enables us to derive the first matching instance‑dependent lower and upper regret bounds, which are substantially tighter than existing worst‑case guarantees. The definition of $\\delta^{2}$ appears on page 5 (immediately before Section 3.1), and the techniques used to obtain the matching bounds are detailed in Section 3.1 and Appendix C.\n\n2. **Extension to stochastic linear bandits.** Although this paper centers on contextual online pricing, the techniques and results in Sections 3–4.1 readily extend to stochastic linear bandits with adversarially chosen action sets, as noted in lines 261–263 and detailed in Appendix I.\n\n3. **Robustness without discrepancy information.** To the best of our knowledge, this is the first work to establish theoretical robustness guarantees for online learning with biased offline data when no information is available about the discrepancy between the online environment and the offline sample (see Section 4.2). Although we focus on contextual pricing, our analysis provides a clear blueprint for extending these results to a wider range of online‑learning problems.\n\n\n\nWhile we draw inspiration from earlier studies on contextual online pricing with unbiased offline data [6, 28] and K‑armed bandits with biased offline data [9], the proofs required to achieve the three main originalities above demand several novel techniques.\n\n**Comment 3: The experimental validation is limited and presented in a very concentrated way. However, given the theoretical character of this work, this experimental validation is sufficient.**\n\nWe appreciate the reviewer’s recognition of our theoretical contribution and agree that broader empirical evidence would further strengthen the paper. In the revision, we will extend the numerical study by (i) exploring a wider range of online‑offline scenarios and (ii) examining the sensitivity of our results to the bias bound $V$.\n\n**Comment 4: References are often imprecise. For example: [9] -> ICML, [11] -> ICLR, [12] -> ECB, [23] -> Single author, [29] -> ICML.**\n\nWe thank the reviewer for raising this point. We will correct the imprecise references in the revised manuscript.\n\n**Comment 5: In order to understand the algorithms, the reader has to rely heavily on the pseudocode. The presentation of the algorithms, in my opinion, should be expanded in the camera-ready exploiting the additional page.**\n\nWe thank the reviewer for the excellent suggestion. We will provide additional details and discussions about our algorithms in the revised paper."}, {"review_id": "nMIHXwB7YU", "reviewer": "Reviewer_TipE", "summary": "This paper studies contextual online pricing where a firm must set prices over time while learning customer demand parameters from observed sales. In addition to online data, the firm has access to offline data that may be biased, meaning it comes from a different distribution than the online environment. The authors propose CO3 algorithm for scalar price elasticity, GCO3 algorithm for general elasticity, and RCO3 algorithm for settings where the bias level is unknown. They derive instance-dependent and minimax-optimal regret bounds that explicitly capture the effects of offline data bias, offline data dispersion, and online learning horizon. The paper also establishes matching lower bounds and impossibility results, showing when and how offline data can improve over purely online approaches. The theoretical results are supported by simulation experiments illustrating the performance of the proposed algorithms relative to standard baselines.", "questions": "1) Could the authors clarify the computational cost of their algorithms?\n\n2) Could the authors provide guidance on choosing the length of the test phase in RCO3 and its sensitivity to this choice?\n\n3) The paper assumes i.i.d. contexts over time. Could the authors comment on how their regret guarantees might extend or degrade under temporal dependence or adversarially chosen contexts?", "limitations": "The paper does not address potential negative societal impacts, such as how biased offline data or aggressive pricing strategies could unintentionally amplify unfair pricing or discrimination.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1) The paper provides a rigorous theoretical framework for contextual online pricing with biased offline data.\n\n2) The formulation of the Contextual Bandits for Online Pricing with Offline Data problem and the proposed algorithms are novel. \n\n3) The paper is clearly written and well organized.\n\n4) The paper addresses a practically important problem.\n\nWeaknesses:\n\n1) The paper does not discuss computational aspects of the proposed algorithms.\n\n2) Proposed methods assume the linear demand model is correctly specified, there is no analysis or experimental evaluation of robustness to model misspecification.\n\n3) Proposed methods are not tested on real-world datasets or realistic pricing simulations, where context distributions, noise properties, or demand patterns may not fully match the assumptions.\n\n4) The authors do not explicitly discuss limitations related to real-world deployment.", "was_revised": true, "final_justification": "After reviewing the authors’ rebuttal and comparing their work with Bu et al. (2020), I find that the paper offers meaningful technical novelty. While some assumptions and parameters could be better motivated and the presentation could more clearly highlight the significance of the contributions, I keep my score at 4", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below. \n\nIn what follows, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references with bibliographic information given at the end of this response.\n\n**Comment 1: The paper does not discuss computational aspects of the proposed algorithms.**\n\nWe appreciate the reviewer’s question. The computational complexity of our algorithms indeed merits additional discussion. In Algorithms 1 and 2, we update the policy and parameter estimates by repeatedly solving a quadratically constrained quadratic program (QCQP) (see Line 7 of Algorithm 1). Although efficient QCQP solvers exist \\[g], we still incur $T$ oracle calls over a horizon of length $T$.\n\nAs noted by \\[f], fully adaptive, per-round updates hinder parallelism and limit large-scale deployment. In purely online settings, recent work on $K$-armed bandits \\[a], linear bandits \\[f], and generalized linear bandits \\[e] shows that optimal $O(\\sqrt{T})$ regret can be achieved with only $O(\\log\\log T)$ policy updates. Adapting these ideas to our setting—developing regret-optimal methods that require far fewer QCQP calls—is a promising research direction. We will expand on this avenue in the revised manuscript.\n\n**Comment 2: Proposed methods assume the linear demand model is correctly specified, there is no analysis or experimental evaluation of robustness to model misspecification.**\n\nWe thank the reviewer for this suggestion. Developing algorithms that are robust to model misspecification—for example, those explored in [b, c]—is a popular research direction. We note, however, that even with unbiased offline data, the effects of model misspecification are not yet fully understood. A promising avenue for future work is to establish theoretical guarantees for online pricing when both unbiased offline data and an unknown (potentially misspecified) demand model are present. Investigation of this problem requires new ideas for algorithm design and theoretical analysis, which is beyond the scope of the current paper. We will leave it  as future work and expand this discussion in the revised manuscript.\n\n**Comment 3: Proposed methods are not tested on real-world datasets or realistic pricing simulations, where context distributions, noise properties, or demand patterns may not fully match the assumptions. The authors do not explicitly discuss limitations related to real-world deployment.**\n\nWe thank the reviewer for raising this point. We agree that incorporating real-world data is an important next step. The *CPRM-12-001: On-Line Auto Lending* dataset from Columbia University’s Center for Pricing and Revenue Management—widely used in personalized lending-rate studies \\[2, d]—is a natural choice for our online component. We will perform the experiment with  this (online) dataset and synthetic (offline) data generated by large language models (LLMs), which can closely approximate real-world behaviors. \n\nWe also wish to emphasize that the primary contribution of this paper is a comprehensive theoretical understanding of contextual online pricing with biased offline data. The assumptions on context distributions, noise, and demand patterns are standard in the literature [2] for deriving theoretical results of online pricing, and our simulations serve to validate the theory.\n\n**Comment 4: Could the authors provide guidance on choosing the length of the test phase in RCO3 and its sensitivity to this choice?**\n\nWe thank the reviewer for the question. As Theorem 5 and its discussion show, the test‑phase length is not uniquely optimal; any value within a certain range is admissible. Within this range, a shorter test phase lowers regret when the true bias is small but increases the worst‑case regret. Therefore, the choice ultimately depends on the decision maker’s risk tolerance—balancing a higher worst‑case regret against the potential for better performance when the bias is small. A special case is $\\alpha = 1/2$, where the decision maker does not accept regret exceeding $\\sqrt{T}$; in this scenario, Algorithm 3 matches the performance of a purely online algorithm. We will expand the manuscript to clarify this trade‑off.\n\n**Comment 5: The paper assumes i.i.d. contexts over time. Could the authors comment on how their regret guarantees might extend or degrade under temporal dependence or adversarially chosen contexts?**\n\nWe thank the reviewer for the question. In the scalar price‑elasticity case we assume i.i.d. contexts, which allows us to define the instance‑dependent parameter $\\delta^{2}$ and derive the corresponding instance‑dependent regret bound. For worst‑case regret bounds, however, this assumption is unnecessary; our results still hold when contexts are chosen adversarially. Lines 261–263 and Appendix I already show how our techniques extend to stochastic linear bandits with adversarially selected action sets. We will clarify the role of the i.i.d. assumption in the revised manuscript.\n\n\n**Comment 6: The paper does not address potential negative societal impacts, such as how biased offline data or aggressive pricing strategies could unintentionally amplify unfair pricing or discrimination.**\n\nWe thank the reviewer for raising this important point. Our work is primarily theoretical and focuses on the design and analysis of an online learning algorithm for pricing with biased offline data, with the goal of achieving low regret. As such, we abstract away from specific application domains, and do not make assumptions about user demographics or other sensitive attributes. We also want to emphasize that our algorithm does not rely on access to sensitive features.\n\nThat said, we agree that pricing mechanisms, even when designed with performance guarantees, can have real-world implications on fairness and equity. In future work, it would be valuable to study how such algorithms perform in settings where users belong to different groups, and to examine whether the algorithm's decisions introduce or exacerbate disparities across these groups. We will add a discussion in the revision to acknowledge these concerns and point out directions for fairness-aware extensions of our work.\n\nReferences:\n\n[a] Perchet, Vianney and Rigollet, Philippe and Chassang, Sylvain and Snowberg, Erik. Batched bandit problems. 2016\n\n[b] Besbes, Omar and Zeevi, Assaf. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. 2015.\n\n[c] Nambiar, Mila and Simchi-Levi, David and Wang, He. Dynamic learning and pricing with model misspecification. 2019.\n\n[d] Lei, Yanzhe and Miao, Sentao and Momot, Ruslan. Privacy-preserving personalized revenue management. 2024.\n\n[e] Sawarni, Ayush and Das, Nirjhar and Barman, Siddharth and Sinha, Gaurav. Generalized linear bandits with limited adaptivity. 2024.\n\n[f] Ruan, Yufei and Yang, Jiaqi and Zhou, Yuan. Linear bandits with limited adaptivity and learning distributional optimal design. 2021\n\n[g] Nesterov, Yurii and Nemirovskii, Arkadii. Interior-point polynomial algorithms in convex programming. 1994."}, {"review_id": "57XKZmXDCX", "reviewer": "Reviewer_oYic", "summary": "In this paper, the authors studied the problem of contextual online pricing with offline data which can be biased. Existing work showed that when offline data are unbiased in the sense of coming from the same distribution as the online data, incorporating the offline data to online policy can outperform pure online learning techniques. However, distribution shifts may exist, and it is common for the offline data to be different from the online data. As a result, it would be desirable to study the effect of potentially biased offline data for online learning. In this paper, the authors proposed an Optimism-in-the-Face-of-Uncertainty policy which is shown to be minimax-optimal. Both the scalar price elasticity and the general setting have been considered. Both known and unknown bias bounds have been investigated as well.", "questions": "1.\tIn the case where V is assumed to be known, how sensitive is the algorithm to inaccuracies in V? How strongly does it rely on the precise specification of V?\n2.\tFor the regret bounds for the general case, why N does not appear in the bounds?\n3.\tAlthough linear demand model was previously used in the literature and is the focus for this paper, it is unlikely to hold in practice. Some discussion on nonlinear models and the corresponding implications would be beneficial.\n4.\tFor RCO3 in the numerical study, it appears that the benefit is relatively small for small V yet the damage on regret can be very substantial for larger V. Overall, despite the authors claim robustness, it seems safer to use UCB instead.", "limitations": "The current paper does not have clear discussions on the limitations and potential negative societal impact of their work. More discussions on the feasibility of known V and how to examine the usability of offline data are necessary. The paper does not study real applications.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Online pricing with the offline data is an interesting and worthwhile problem to study. This paper investigates the potential data shifts in terms of biased offline data compared with online data. The regret bounds shed some lights on the impact of offline data for online learning with respect to various factors such as bias bound etc. \nAlthough theoretically insightful, the majority of the paper considers the case of known V. However, in practice, V is likely unknown. Despite there are some developments for the case of unknown V, it is important and necessary for authors to add discussions and explanations on when V can be known in practice. Also, the numerical studies are somewhat limited to two simple simulated settings.", "was_revised": true, "final_justification": "The authors have addressed most of my comments in the rebuttal. However, my concern regarding the linear demand model was not adequately addressed. I am maintaining my current rating of 3.", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below.\n\nIn what follows, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references with bibliographic information given at the end of this response.\n\n**Comment 1: Add discussions and explanations on when V can be known in practice**\n\nWe thank the reviewer for raising this point. We emphasize that $V$ is only a **valid upper bound** on the bias $\\lVert\\theta_*-\\theta_*'\\rVert$; specifically, $V \\ge \\lVert\\theta_*-\\theta_*'\\rVert$. It is **not** intended as an exact estimate, i.e., we do not assume $V = \\lVert\\theta_*-\\theta_*'\\rVert$. In practice, $V$ can be estimated with robust machine‑learning methods \\[5] or through cross‑validation \\[8], as also argued in prior work on K‑armed bandits with biased offline data \\[9]. Setting $V=\\infty$ trivially guarantees validity and recovers the same performance as classical algorithms that ignore offline data (see Sections 3–4.1). However, when a finite upper bound that scales favourably with the time horizon $T$ is available, the regret guarantees in Sections 3–4.1 become sharper. We will expand the discussion that estimating a valid upper bound $V$ is practically feasible.\n\n**Comment 2: In the case where V is assumed to be known, how sensitive is the algorithm to inaccuracies in V? How strongly does it rely on the precise specification of V?**\n\nWe thank the reviewer for the question. As explained in Comment 1, our results in Sections 3–4.1 require only that $V$ be a **valid upper bound** on the true bias $\\lVert\\theta_*-\\theta_*'\\rVert$; such a upper bound can be estimated with robust ML methods or cross‑validation. Theorems 1 and 3 show that regret depends on $V$ and the dependence is solely through how $V$ scales with the time horizon $T$. For example, if $\\lVert\\theta_*-\\theta_*'\\rVert = T^{-5/16}$ and we use the upper bound $V = 1.1\\lVert\\theta_*-\\theta_*'\\rVert>\\lVert\\theta_*-\\theta_*'\\rVert$, then $V$ still scales as $T^{-5/16}$, and our theorems guarantee regret is strictly better than classical algorithms that ignore offline data. Numerical experiments corroborate this: with a tight estimate ($V = 1.1\\lVert\\theta_*-\\theta_*'\\rVert$) we achieve lower regret; and even with a loose estimate ($V = 10\\lVert\\theta_*-\\theta_*'\\rVert$) the regret does not exceed that of a purely online baseline.\n\nWe acknowledge that robust ML methods or cross‑validation can, with small probability, produce an *invalid* estimate of $V$ (i.e., $V < \\lVert\\theta_*-\\theta_*'\\rVert$). In that event, our confidence intervals no longer hold and the regret can become linear in theory. From a practical standpoint, however, it is still valuable to understand how regret behaves when $V$ is underestimated. Accordingly, our revised paper will include additional experiments that test the algorithm’s performance under such misspecifications.\n\n**Comment 3: Although linear demand model was previously used in the literature and is the focus for this paper, it is unlikely to hold in practice. Some discussion on nonlinear models and the corresponding implications would be beneficial.**\n\nWe thank the reviewer for raising this point. Our linear‑model framework extends naturally to a generalized linear model with a known link function $g$: $D=g\\bigl(\\alpha^{\\top}x + (\\beta^{\\top}y)p\\bigr) + \\varepsilon,$ provided that (i) $g$ is differentiable and strictly increasing, and (ii) the minimizer of $\n\\bar D(p)=g\\bigl(\\alpha^{\\top}x+ (\\beta^{\\top}y)p\\bigr)\n$ lies in the interior of the feasible price interval $[l,u]$. These assumptions are standard; see [2,b]. \nThe only change required is to replace the least‑squares estimate with a maximum quasi‑likelihood objective. Because $g$ is differentiable and strictly increasing, it is locally linear, we are confident that our core regret analysis framework can be extended to this setting and achieve comparable results; see [c] for a similar argument and [2] for the full derivation. We will add the discussion in the revised manuscript.\n\n**Comment 4: For RCO3 in the numerical study, it appears that the benefit is relatively small for small V yet the damage on regret can be very substantial for larger V. Overall, despite the authors claim robustness, it seems safer to use UCB instead.**\n\nWe appreciate the reviewer’s observation. We do **not** claim that RCO3 always outperforms UCB. In fact, our impossibility result shows that, without any knowledge of the mismatch between offline and online data distributions, no algorithm can always outperform a purely online baseline such as UCB.\n\nThe robustness section therefore has a different goal: it introduces an algorithm that, *when an upper bias bound $V$ is unavailable*, (i) achieves lower regret than a pure‑online method when the true bias is small, and (ii) still guarantees sublinear regret when the bias is large. Empirically, Figure 2(c) shows that the percentage drop in regret for small bias is comparable to the percentage increase for large bias, even though the absolute loss in the latter case is higher. Theoretically, these robustness results complement Sections 3–4.1—which assume $V$ is known—by providing the first robustness guarantee for contextual online pricing with biased offline data and paving the way for analogous guarantees in broader online‑learning settings that leverage such data.\n\n\n**Comment 5: The current paper does not have clear discussions on the limitations and potential negative societal impact of their work. More discussions on the feasibility of known V and how to examine the usability of offline data are necessary.**\n\nWe appreciate the reviewer’s suggestion. For additional discussion on how a valid upper bound $V$ can be obtained, please see our responses to Comments 1 and 2.\n\n**Usability of offline data**\n\n* **If a valid bound $V$ is available:** We should always incorporate the offline data and use Algorithms 1 or 2. As indicated by Theorems 1 and 3, these algorithms never perform worse than a pure‑online baseline and can outperform it when $V$ is small and the offline data are informative (Sections 3–4.1).\n\n* **If no valid bound $V$ is available:** We can adopt Algorithm 3, selecting the length of the testing phase within the choice set in Theorem 5, according to the decision maker’s risk tolerance. A shorter test phase lowers regret when the true bias is small but increases the worst‑case regret, and vice versa. A special case is $\\alpha = 1/2$, where the decision maker does not accept regret exceeding $\\sqrt{T}$; in this scenario, Algorithm 3 matches the performance of a purely online algorithm.\n\nWe will clarify these guidelines and expand the discussion in the revised manuscript.\n\nFor discussions on potential negative societal impact, our work is primarily theoretical and focuses on the design and analysis of an online learning algorithm for pricing with biased offline data, with the goal of achieving low regret. As such, we abstract away from specific application domains, and do not make assumptions about user demographics or other sensitive attributes. We also want to emphasize that our algorithm does not rely on access to sensitive features.\n\nThat said, we agree that pricing mechanisms, even when designed with performance guarantees, can have real-world implications on fairness and equity. In future work, it would be valuable to study how such algorithms perform in settings where users belong to different groups, and to examine whether the algorithm's decisions introduce or exacerbate disparities across these groups. We will add a discussion in the revision to acknowledge these concerns and point out directions for fairness-aware extensions of our work.\n\n**Comment 6: The paper does not study real applications.**\n\nWe thank the reviewer for raising this point. We agree that incorporating real-world data is an important next step. The *CPRM-12-001: On-Line Auto Lending* dataset from Columbia University’s Center for Pricing and Revenue Management—widely used in personalized lending-rate studies \\[2, d]—is a natural choice for our online component. We will perform the experiment with  this (online) dataset and synthetic (offline) data generated by large language models (LLMs), which can closely approximate real-world behaviors. \n\nWe also would like to emphasize that the primary contribution of this paper is a comprehensive theoretical understanding of contextual online pricing with biased offline data. For a detailed summary of these theoretical contributions and their originality, please refer to our response to Reviewer 4jmU’s Comment 2.\n\nReferences:\n\n[a] Lei, Yanzhe and Miao, Sentao and Momot, Ruslan. Privacy-preserving personalized revenue management. 2024.\n\n[b] Den Boer, Arnoud V and Zwart, Bert. Simultaneously learning and optimizing using controlled variance pricing. 2014.\n\n[c] Keskin, N Bora and Zeevi, Assaf. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. 2014."}, {"review_id": "E1IzPLVblX", "reviewer": "Reviewer_4evj", "summary": "This paper studies the problem of dynamic pricing in the presence of offline data, possibly coming from a different distribution. The model is the following.\n\nThe learner has access to $N$ offline observations $(D_n, x_n, y_n, p_n)_{n\\leq N}$, where $p_n$ is the price corresponding to the $n$-th (offline) transaction, $x_n$ and $y_n$ are contexts describing this transaction, and $D_n$ is the demand level for this sale at the price $p_n$, given by\n$$D_n = x_n^{\\top}\\alpha' + y_n^{\\top}\\beta' + \\epsilon'_n,$$\nwhere $\\epsilon'_n$ is a noise term. Then, at each round $t\\leq T$, the learner observes a context $x_t, y_t$, posts a price $p_t$, and receives a reward\n$$p_tD_t = p_t(x_t^{\\top}\\alpha + y_t^{\\top}\\beta + \\epsilon_t).$$\n\nThe authors propose a mechanism to leverage the previous observations and mimic the offline strategy to maximize the expected cumulative reward. They derive upper bounds on the regret, depending on problem-dependent constants, on the distance between the offline and online parameters $\\alpha', \\beta'$ and $\\alpha, \\beta$, and on the gap between the optimal strategy and the best linear approximation to the offline strategy. They also obtain lower bounds on the regret for this problem and present simulations showcasing their method.", "questions": "Adequately addressed by the authors.", "limitations": "One of the limitations of this work is that the model considered differs significantly from the classical model of dynamic pricing with covariates, which is not properly discussed in the paper.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 1, "strengths_and_weaknesses": "**Strengths**\n\nThis paper studies the well-motivated problem of leveraging prior informations in dynamic pricing problem. This is, in my opinion, a relevant problem as classical bandit technic rely on a lot of exploration, which is problematic in practise.\n\n**Weaknesses** \n\n- *Clarity*: I find the paper’s clarity to be below the standards for NeurIPS. For example, the ideas behind the algorithm are not presented clearly. Among other issues, the fact that $\\widehat{p}$ mimics the pricing strategy $p_n$ instead of estimating the parameter $\\theta'$ is not discussed. The authors present their algorithm as addressing an exploration-exploitation trade-off, when in fact the constraints that the price should be upper and lower bounded, combined with the randomness of the context, imply that all prices yield approximately the same amount of information. Thus, the problem reduces to estimating the parameters of a linear regression model from offline and online data and so all rounds correspond to \"exploitation rounds\". Additionally, the presentation of the theoretical results would benefit from greater clarity; key steps in the proofs are difficult to follow and lack structure.  Moreover, the current version of the paper lacks rigor in certain aspects—for instance, the algorithm does not explicitly define the parameter estimators or the widths of the confidence ellipsoids. These crucial details are only provided in the proof of a lemma in the appendix, which undermines the accessibility and transparency of the method.\n\n- *Rigor*: The authors have addressed my concern regarding an error in the proof of their lower bound. \n\n- *Significance*: The authors study a problem very different from the one classically used in the literature, without justifying it, which may indicate that the contributions are limited. I strongly feel that the discussion of related literature is insufficient. From my (admittedly limited) knowledge of dynamic pricing and dynamic programming, the demand model used in this paper appears to diverge significantly from the classical framework, which typically assumes that each buyer has a private valuation for the good, and demand is binary—equal to 1 if the posted price is below the valuation, and 0 otherwise. This standard model has been extensively studied, and it would be valuable for the authors to more thoroughly engage with this line of work. In particular, it would be helpful to clarify how their setting compares with or generalizes these models. The current treatment, which mainly cites the outdated reference [10]—itself focused primarily on the deterministic case—is not sufficient in my opinion. \n\n- *Originality*: The technical improvement with regards to the previous work [6] in the one dimensional elasticity setting seems incremental at best as the authors study the same model under very similar assumptions, only assuming that the online and offline parameters may be different.In the multi-dimensional elasticity setting, the techniques appear to be standard, and the results are largely expected. Therefore, the technical contributions appear to be of limited significance.", "was_revised": true, "final_justification": "I remain unconvinced by the overall contributions of the paper, which appear rather incremental relative to Bu et al. (2020). In addition, the lack of clarity in both the presentation and the proofs significantly reduces the paper’s impact, making it difficult to extract meaningful conclusions, understand the core challenges of the problem, or extend the proposed proof techniques. Therefore, I still recommend rejection of this paper.", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below.\n\nIn what follows, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references with bibliographic information given at the end of this response.\n\n**Comment 1: The ideas behind the algorithm are not presented clearly and the algorithm does not explicitly define the parameter estimators or the widths of the confidence ellipsoids in the main paper.**\n\nWe thank the reviewer for the suggestion. We do outline the key ideas behind Algorithms 1–3 before presenting their regret bounds in Sections 3 and 4. The intuition for the parameter estimators and confidence‑ellipsoid widths is explained in the main paper; the full mathematical details are deferred to Appendix A due to space constraints. In the revised paper, we will expand the algorithmic details and provide additional discussions to further improve the clarity. \n\n**Comment 2: The fact that $\\widehat{p}$ mimics the pricing strategy $p_n$ instead of estimating the parameter $\\theta'$ is not discussed.**\n\nWe thank the reviewer for this question.  When the offline data are used solely to estimate $\\theta_*'$ and only the bias bound $V$ is known, the squared estimation error of the online parameter $\\theta_*$ cannot, in order, improve beyond  $V^2+ 1/\\lambda_{\\min}(\\hat \\Sigma)$, which yields the worst-case regret bound discussed in the general price-elasticity setting.\n\nIn the scalar price-elasticity case—a key contribution of our work—the regret can be further **tightened** through the instance-dependent parameter $\\delta^{2}$, which measures how far the empirical pricing rule $\\hat p$ departs from the (unknown) optimal policy.  If we understand correctly, the reviewer’s $p_n$ refers to the offline prices $\\hat p_n$.  Our $\\hat p$ mimics these prices in a **structured** way: it is the best-fit linear rule $\\hat p(x,y)=\\hat A^\\top x/y$ over the offline sample, and, when no context is present, reduces to their empirical mean.  Crucially, $\\hat{p}$ is **not** obtained by first estimating $\\theta_*'$ and then selecting the corresponding optimal pricing strategy.\n\n\nThen, The effect of $\\delta^{2}$ (see Lines 184–206) is two-fold:\n\n1. If $\\delta^{2}$ is **large**, allowing online price strategies $p_t$ to diverge from $\\widehat{p}$ accelerates both exploration and exploitation.\n2. If $\\delta^{2}$ is **small**, the online phase should simply adopt $\\widehat{p}$.\n\nThus, $\\widehat{p}$ guides the online strategy either to follow it or to deviate from it. Because $\\delta^{2}$ is unknown, Algorithm 1 first estimates it (Line 1) and then decides whether it is small enough to justify using $\\widehat{p}$ exclusively in the online phase. We will add further intuition about the structure of $\\hat{p}$ in the revised paper.\n\n**Comment 3: There may be a mistake in the proof/statement of the lower bound (Theorem 2)... This would imply a total regret that is at most (poly-)logarithmic in $T$. This error was already present in [6] and [28].**\n\nWe thank the reviewer for this question. We want to point out that our proof and statement of Theorem 2 is **correct**. First, we would like to emphasize that **dynamic pricing with a linear demand model is not a purely exploitative task.** Prior work \\[a] shows that even in the simplest non‑contextual, one‑dimensional setting, $\nD = \\alpha + \\beta \\cdot p + \\varepsilon,\n$ the regret is lower‑bounded by $\\Omega(\\sqrt{T})$.\n\nThe key insight is that prices do **not** provide the same amount of information. In dynamic pricing, the instantaneous regret satisfies $$r_t \\lesssim (p_t - p^*)^{2} \\overset{(1)}{\\lesssim} ||\\theta_{\\*}- \\hat{\\theta}_t ||^2.$$\n\nOn one hand, if $\\lVert\\theta_*-\\hat\\theta_t\\rVert = O(t^{-1/2})$, achieving an instantaneous regret of $O(t^{-1})$ requires that inequality (1) holds—i.e., $p_t$ must be the optimal price with respect to $\\hat\\theta_t$, which implies **no**  exploration should be incorporated. On the other hand, achieving the estimation rate $\\lVert\\hat\\theta_t-\\theta_*\\rVert = O(t^{-1/2})$ demands at least $\\Theta(t)$ exploratory rounds, and effective exploration must use **at least two** prices separated by a fixed gap, incurring $\\Theta(t)$ regret (as in the ILS‑d algorithm \\[a]). Hence, one cannot **simultaneously** maintain a $t^{-1/2}$ estimation error **and** a $t^{-1}$ instantaneous regret for all $1 \\leq t \\leq T$. Prior work on the estimation–regret trade‑off—see, e.g., \\[b]—likewise proves that no algorithm can achieve both the optimal $\\sqrt{T}$ regret and the optimal $1/\\sqrt{T}$ estimation error within $T$ rounds, highlighting the fundamental exploration–exploitation tension in dynamic pricing with a linear demand model.\n\n\n**Comment 4: The presentation of the theoretical results would benefit from greater clarity; key steps in the proofs are difficult to follow and lack structure.**\n\nWe thank the reviewer for the suggestion. In the revised paper, we will expand the discussion accompanying each theoretical result and restructure the proofs.\n\n**Comment 5: The paper tackles a pricing model that deviates from the classical binary‑demand framework without explaining why, raising doubts about the scope of its contributions. The literature review is sparse—relying mainly on the outdated reference \\[10]. The authors should clarify how their setting relates to, or generalizes, these binary‑demand framework.**\n\nWe thank the reviewer for raising this point. We would like to point out that linear‑demand models are long‑standing classics \\[a, e, f] and remain an active research area, as studied by recent work\\[2, 4, b, c, d]. Prior work \\[e] also demonstrates that many non‑linear demand functions can be closely approximated by a linear specification. In the revision, we will expand our discussion to clarify how our framework relates to the binary‑demand literature and highlight the connections between the two approaches. For a detailed account of our contributions, please see our response to Comment 6.\n\n**Comment 6: The technical improvement with regards to the previous work [6] in the one dimensional elasticity setting seems incremental at best as the authors study the same model under very similar assumptions, only assuming that the online and offline parameters may be different.In the multi-dimensional elasticity setting, the techniques appear to be standard, and the results are largely expected. Therefore, the technical contributions appear to be of limited significance.**\n\nWe would like to highlight three principal originalities of this work:\n\n1. **Instance‑dependent parameter $\\delta^{2}$.** We introduce the first instance‑dependent quantity, $\\delta^{2}$, for contextual online pricing with offline data—whether biased or unbiased—without making any assumptions about how the offline data are generated. This parameter enables us to derive the first matching instance‑dependent lower and upper regret bounds, which are substantially tighter than existing worst‑case guarantees. The definition of $\\delta^{2}$ appears on page 5 (immediately before Section 3.1), and the techniques used to obtain the matching bounds are detailed in Section 3.1 and Appendix C.\n\n2. **Extension to stochastic linear bandits.** Although this paper centers on contextual online pricing, the techniques and results in Sections 3–4.1 readily extend to stochastic linear bandits with adversarially chosen action sets, as noted in lines 261–263 and detailed in Appendix I.\n\n3. **Robustness without discrepancy information.** To the best of our knowledge, this is the first work to establish theoretical robustness guarantees for online learning with biased offline data when no information is available about the discrepancy between the online environment and the offline sample (see Section 4.2). Although we focus on contextual pricing, our analysis provides a clear blueprint for extending these results to a wider range of online‑learning problems.\n\n\n\nWhile we draw inspiration from earlier studies on contextual online pricing with unbiased offline data [6, 28] and K‑armed bandits with biased offline data [9], the proofs required to achieve the three principal originalities above demand several novel techniques.\n\n\nReferences:\n\n[a] Keskin, N Bora and Zeevi, Assaf. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. 2014.\n\n[b] Simchi-Levi, David and Wang, Chonghuan. Pricing experimental design: causal effect, expected revenue and tail risk. 2023.\n\n[c] Li, Xiaocheng and Zheng, Zeyu. Dynamic pricing with external information and inventory constraint. 2024.\n\n[d] Ao, Ruicheng and Jiang, Jiashuo and Simchi-Levi, David. Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices. 2025\n\n[e] Besbes, Omar and Zeevi, Assaf. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. 2015.\n\n[f] Qiang, Sheng and Bayati, Mohsen. Dynamic pricing with demand covariates. 2016"}]

Author rebuttal:

Meta-review: This paper tackles the important and practical problem of contextual online pricing when an agent has access to a potentially biased offline dataset. The authors propose algorithms that leverage this offline data to improve online performance, providing minimax-optimal and instance-dependent regret bounds. The reviewers are somewhat divided, with scores ranging from 3 to 5. However, a careful reading of the reviews and the author rebuttal process reveals that this is a technically solid paper with meaningful contributions.

All reviewers agree that the problem setting is well-motivated, timely, and significant. The primary strengths of the paper lie in its theoretical contributions. Reviewers 4jmU and TipE respectively described the analysis as "formal and well-performed" and "rigorous," highlighting the paper's technical depth. 

The main points of contention were:

**Novelty and Incrementality**: Several reviewers (4evj, 4jmU, oYic) initially questioned the paper's novelty, particularly in relation to prior work by Bu et al. (2020). However, in their rebuttal, the authors provided a detailed breakdown of their novel contributions, including the introduction of a new instance-dependent parameter, new proof techniques for handling biased data, and robustness guarantees. This explanation was sufficiently compelling to convince Reviewer TipE of the paper's "meaningful technical novelty." While other reviewers remained concerned, the authors' defense makes a strong case that the work is more than a simple extension of prior art. 

**Technical Correctness**: Reviewer 4evj raised a serious concern about an error in the proof of the lower bound. This point was debated extensively. The authors provided a detailed and rigorous mathematical counter-argument that ultimately convinced the reviewer. 

**Clarity and Presentation**: Reviewer 4evj was critical of the paper's clarity. However, this view was not shared by Reviewer 4jmU ("well-written and structured") or Reviewer TipE ("clearly written and well organized"). The authors have also committed to improving the presentation in the final version.

**Model Misspecification and Experiments**: Reviewers TipE and oYic both raised concerns about the potential model misspecification of the linear demand model. This is a legitimate concern. However, linear demand models are indeed quite common in the dynamic pricing literature. The authors also mentioned that linear demand models have certain robustness in the context of decision-making. That being said, the authors should discuss the issue of model misspecification in the paper. Moreover, the authors should expand the numerical studies using real-world datasets, which will substantially strengthen the final paper.

In summary, this paper addresses a significant problem at the intersection of online learning and revenue management. While the initial reviews raised valid concerns, the authors have successfully addressed the most critical of these. The technical core of the paper has withstood scrutiny, particularly regarding the lower-bound proof. The authors have also made a convincing case for the novelty of their contributions. The work is technically solid and provides valuable insights. Therefore, I recommend acceptance. Meanwhile, I suggest the authors further improve their experiments and the presentation and discuss the issue of model misspecification.
Decision: Accept (poster)