*$\dagger$*$\dagger$affiliationtext: Department of Industrial Engineering and Decision Analytics*$\dagger$*$\dagger$affiliationtext: The Hong Kong University of Science and Technology

#  Minimax Optimality in Contextual Dynamic Pricing with General Valuation
Models

Xueping Gong  Jiheng Zhang

###### Abstract

Dynamic pricing, the practice of adjusting prices based on contextual factors,
has gained significant attention due to its impact on revenue maximization. In
this paper, we address the contextual dynamic pricing problem, which involves
pricing decisions based on observable product features and customer
characteristics. We propose a novel algorithm that achieves improved regret
bounds while minimizing assumptions about the problem. Our algorithm
discretizes the unknown noise distribution and combines the upper confidence
bounds with a layered data partitioning technique to effectively regulate
regret in each episode. These techniques effectively control the regret
associated with pricing decisions, leading to the minimax optimality.
Specifically, our algorithm achieves a regret upper bound of
$\tilde{\mathcal{O}}(\rho_{\mathcal{V}}^{\frac{1}{3}}(\delta)T^{\frac{2}{3}})$,
where $\rho_{\mathcal{V}}(\delta)$ represents the estimation error of the
valuation function. Importantly, this bound matches the lower bound up to
logarithmic terms, demonstrating the minimax optimality of our approach.
Furthermore, our method extends beyond linear valuation models commonly used
in dynamic pricing by considering general function spaces. We simplify the
estimation process by reducing it to general offline regression oracles,
making implementation more straightforward.

##  1 Introduction

The contextual dynamic pricing problem involves setting real-time prices for
products or services based on contextual factors like product details and
customer characteristics. It has received significant attention in the
literature due to its practical applications and its impact on revenue
maximization. For a comprehensive review of the literature on dynamic pricing,
we refer readers to [8], and for specific applications, Saharan et al. [20]
provide valuable insights.

Recent works have particularly focused on feature-based (or contextual)
pricing models, which consider observable product features to determine both
the market value of a product and the pricing strategy [9, 4, 5]. These models
account for product heterogeneity and enable personalized pricing. However,
designing low-regret policies in this setting presents several challenges.
Firstly, the demand curve continuously shifts due to changes in covariates
over time. Secondly, the shape of the demand curve is often unknown due to the
lack of information on the market noise distribution, which may not follow a
specific parametric form. Consequently, solving the dynamic pricing problem
requires precise estimation of the demand function across a wide range of
prices, diverging from non-contextual dynamic pricing and non-parametric
bandit problems, where estimation around a single maximum is sufficient. Thus,
the contextual dynamic pricing problem presents unique challenges and
potentially leads to higher regret compared to its non-contextual counterpart.

Despite extensive research on the contextual dynamic pricing problem, previous
findings suffer from either strong assumptions that restrict their
applicability or sub-optimal regret bounds. In our work, we aim to address
both limitations by achieving improved regret bounds while minimizing
assumptions about the problem.

To tackle the problem, we employs an explore-then-UCB approach and propose an
epoch-based learning framework. Initially, we conduct a pure exploration phase
to gather samples for learning the true valuation function. Subsequently, an
UCB (Upper Confidence Bound) phase is executed to set a suitable price based
on the evaluation estimator. During the UCB phase, we discretize the domain of
the unknown distribution function into equal-length intervals to effectively
handle the challenge posed by its inherent uncertainty. Notably, this
discretization process leads to a linear bandit structure, enabling the
development of upper confidence bounds that robustly account for estimation
errors and biases arising from valuation estimation. To further leverage the
distinctive structure of this linear bandit, we employ a layered data
partitioning technique to effectively regulate regret in each episode. The
adaptive nature of this technique eliminates the need for a Lipschitz
constant, enhancing the flexibility and practicality of our approach. Lastly,
we carefully select an appropriate number of discretization intervals to
strike a balance between the regret arising from the discrete-part and
continuous-part of the problem, ultimately achieving the minimax optimality of
this challenging problem.

In this work, we propose Algorithm 1, a novel algorithm capable of handling a
general valuation function space and nonparametric noise distribution. Our
algorithm achieves a regret upper bound of
$\tilde{\mathcal{O}}(\rho^{\frac{1}{3}}_{\mathcal{V}}(\delta)T^{\frac{2}{3}})$,
where $\rho_{\mathcal{V}}(\delta)$ is related with the estimation error of the
valuation function. Notably, our method relies solely on the widely adopted
Lipschitz continuity assumption found in the literature [9, 13, 17, 6, 7],
without assuming second-order smoothness around the optimal price or
uniqueness of the optimal price, which are commonly assumed in contextual
pricing literature. Importantly, our regret bound matches the lower bound up
to logarithmic terms, as demonstrated in [24].

When applied to linear valuation models with $d_{0}$-dimensional covariates,
our results yield $\tilde{\mathcal{O}}(d_{0}^{\frac{1}{3}}T^{\frac{2}{3}})$
regrets. This represents an improvement over the existing regret bound of Luo
et al. [17], which reports $\tilde{\mathcal{O}}(d_{0}^{2}T^{\frac{2}{3}})$
with the second-order smoothness assumption, and
$\tilde{\mathcal{O}}(d_{0}T^{\frac{3}{4}})$ without this assumption.
Furthermore, compared to the results of Fan et al. [9], which reported a
regret bound of $\tilde{\mathcal{O}}(d_{0}^{\frac{5}{7}}T^{\frac{5}{7}})$
under both conditions, our approach achieves a lower order in $T$ while
relaxing the assumptions. Notably, our method extends beyond linear models by
considering general function spaces and reducing the estimation to general
offline regression oracles, allowing for natural incorporation of sparsity,
reproducing kernel Hilbert spaces, and other general function spaces.

We also explore scenarios where the distribution function $F$ is known, the
valuation can be observed, and a more powerful classification oracle exists.
In the first case, our assumptions are comparable to [13], as we extend their
linear valuation model to a general valuation model. In the second case, we
demonstrate how the regret can be improved to
$\tilde{\mathcal{O}}(T^{\frac{3}{5}})$ with the additional second-order
smoothness assumption. This upper bound matches the lower bound in [16] where
only censored feedback can be observed. If only the censored feedback can be
observed but powerful classification oracles in 5.3 exist, we show that our
method can stull improve the upper bounds
$\tilde{\mathcal{O}}(T^{\frac{2}{3}\vee(1-\alpha)})$ reported in [16, 17] to
$\tilde{\mathcal{O}}(T^{\frac{3}{5}\vee(1-\alpha)})$.

###  1.1 Related work

Dynamic pricing. Dynamic pricing has been an active area of research, driven
by advancements in data technology and the increasing availability of customer
information. Initial research focused on non-contextual dynamic pricing
without covariates [3, 4]. For example, Wang et al. [23] employed the UCB
approach with local-bin approximations, achieving an
$\tilde{\mathcal{O}}(T^{(m+1)/(2m+1)})$ regret for $m$-th smooth demand
functions and establishing a matching lower bound. However, these approaches
did not incorporate covariates into pricing policies, making our model
fundamentally distinct.

In the domain of dynamic pricing with covariates, the linear customer
valuation model has been widely adopted. Javanmard and Nazerzadeh [13] studied
this model assuming known noise distribution, but their methods were limited
when the noise distribution was unknown or not log-concave. In contrast,
Golrezaei et al. [12] considered an ambiguity set for the noise distribution,
achieving a regret of $\tilde{\mathcal{O}}(T^{2/3})$ compared to a robust
benchmark. However, their approach faced challenges with ambiguity sets
encompassing infinite distributions. Our proposed model addresses the general
case of an unknown noise distribution and establishes regret bounds by
comparing against the true optimal policy. Chen et al. [5] explored
nonparametric aspects of the unknown demand function, using adaptive binning
of the covariate space to achieve a regret of
$\tilde{\mathcal{O}}(T^{\frac{d_{0}+2}{d_{0}+4}})$. Notably, our method
outperforms theirs when $d_{0}\geq 2$. Under the Cox proportional hazards (PH)
model, Choi et al. [7] introduced the CoxCP algorithm, which demonstrated a
regret of $\tilde{\mathcal{O}}(T^{2/3})$. However, their approach relied on
the separability of the unknown linear structure and noise distribution in the
PH model, making it unsuitable for our pricing model where these components
are entangled. Recent work by Xu and Wang [24] proposed an adaptive pricing
policy with $\tilde{\mathcal{O}}(T^{\frac{3}{4}})$ regret for adversarial
contexts and bounded noise distributions. Our method improves the regret to
$\tilde{\mathcal{O}}(T^{\frac{2}{3}})$ under Lipschitz noise distribution,
while maintaining computational efficiency compared to the exponential
computations required by the EXP4-based policy in Xu and Wang [24].

Other related studies [17, 16, 9] share similarities with our work in terms of
settings, but differ in their assumptions about the smoothness of the noise
distribution. For example, Luo et al. [16] proposed an epoch-based algorithm
with regret bounds of $\tilde{\mathcal{O}}(d_{0}^{2}T^{\frac{2}{3}})$ and
$\tilde{\mathcal{O}}(d_{0}T^{\frac{3}{4}})$ under different smoothness
assumptions. Fan et al. [9] considered $m$-th differentiable distributions and
achieved a regret of $\tilde{\mathcal{O}}((d_{0}T)^{\frac{2m+1}{4m-1}})$ using
the Nadaraya-Watson kernel regression estimator. In comparison, our method
achieves $\tilde{\mathcal{O}}(d_{0}^{\frac{1}{3}}T^{\frac{2}{3}})$ regrets
when applied to linear valuation models, demonstrating minimax optimality
while relying on minimal assumptions.

Contextual bandit. Our pricing policy shares connections with bandit
algorithms [14, 11, 1, 22, 2], which aim to balance exploration and
exploitation in decision-making. Specifically, our approach relates to the
concept of misspecified linear bandits [2, 16] within the context of dynamic
pricing. Unlike traditional bandit algorithms, dynamic pricing requires
consideration of both estimation variance and the bias resulting from linear
parameter perturbation. Notably, we have discovered an intriguing finding that
by leveraging the unique structure of the dynamic pricing problem, we can
achieve a more precise and improved regret bound compared to directly applying
complex existing algorithms designed for misspecified linear bandits. This
improvement is mainly attributed to the fact that the bias encountered in each
round is consistent across all prices (actions). While previous research has
explored bandit algorithms and misspecified linear bandits, our work extends
these concepts to the dynamic pricing domain, incorporating the specific
characteristics and demands of pricing decisions. This underscores the
importance of leveraging the distinctive structure and attributes of the
pricing context in order to achieve superior performance.

Notations. Throughout the paper, we use the following notations. For any
positive integer $n$, we denote the set $\\{1,2,\cdots,n\\}$ as $[n]$. The
cardinality of a set $A$ is denoted by $|A|$. We use $\mathbf{I}_{\\{E\\}}$ to
represent the indicator function of the event $E$. Specifically,
$\mathbf{I}_{\\{E\\}}$ takes the value $1$ if $E$ happens, and $0$ otherwise.
For norms, we utilize the notation $\|\cdot\|_{p}$ where $1\leq p\leq\infty$
to denote the $\ell_{p}$ norm. Throughout the analysis, the notation
$\tilde{\mathcal{O}}$ is employed to hide the dependence on absolute constants
and logarithmic terms. It allows us to focus on the dominant behavior of the
quantities involved.

##  2 Basic Setting

In the context of contextual dynamic pricing, a potential customer arrives at
the platform during each round $t\in[T]$, and the seller observes a covariate
$x_{t}\in\mathbb{R}^{d_{0}}$ representing the product features and customer
characteristics. Upon observing $x_{t}$, the customer’s valuation of the
product, denoted as $v_{t}=v^{*}(x_{t})+\epsilon_{t}$, is determined by a
linear function of $v^{*}(x_{t})$ and a market noise term $\epsilon_{t}$. The
value function $v^{*}$ belongs to the function space $\mathcal{V}$, and the
noise terms $\\{\epsilon_{t}\\}_{t\in[T]}$ are independently and identically
drawn from an unknown zero-mean distribution $F$.

If the customer’s valuation $v_{t}$ exceeds the seller’s set price $p_{t}$, a
sale occurs, resulting in the seller collecting a revenue of $p_{t}$. However,
if $v_{t}$ is lower than $p_{t}$, the customer leaves without making a
purchase, and the seller does not receive any revenue. We denote the
occurrence of a sale as $y_{t}=\mathbf{I}_{\\{v_{t}\geq p_{t}\\}}$, which can
be modeled as a Bernoulli random variable with a parameter of
$1-F(p_{t}-v^{*}(x_{t}))$. Consequently, the reward from the sale is given by
$r_{t}=p_{t}y_{t}$. The triplet $(x_{t},p_{t},y_{t})$ captures the information
pertaining to the pricing procedure at time $t$.

Given the customer choice model and the covariate $x$, the expected reward of
setting a price $p$ can be expressed as $p(1-F(p-v^{*}(x)))$. The optimal
price $p^{*}(x)$ is defined as the price that maximizes $p(1-F(p-v^{*}(x)))$.
In the dynamic pricing process, the seller dynamically sets prices and
observes binary feedbacks to collect instant revenues while gathering
information to estimate $v^{*}$ and $F$. Apparently, learning $v^{*}$ and $F$
gives the seller much more information to estimate the market value of a new
product given its feature covariates. On the other hand, the seller also wants
to always give optimized price so as to maximize the expected revenue. It is
necessary to have a good policy that strikes a balance between exploration
(collecting additional information for better future revenues) and
exploitation (utilizing current knowledge for immediate revenues based on the
learned model).

The regret at time $t$ is defined as the loss in reward resulting from setting
the price $p_{t}$ compared to the optimal price $p^{*}(x_{t})$. The cumulative
regret over the horizon of $T$ periods, denoted as $Reg(T)$, is given by the
expression:

$Reg(T)=\sum_{t=1}^{T}p^{*}(x_{t})(1-F(p^{*}(x_{t})-v^{*}(x_{t})))-p_{t}(1-F(p_{t}-v^{*}(x_{t}))).$

To evaluate the performance, we consider the expected cumulative regret
$\mathbb{E}[Reg(T)]$, which takes into account the randomness of the
covariates and the potential randomness of the pricing policy. The goal of our
contextual dynamic pricing is to decide the price $p_{t}$ for covariate
$x_{t}$ at time $t$, by utilizing all historical data
$\\{(x_{s},p_{s},y_{s}),s\in[t-1]\\}$, in order to minimize the expected
cumulative regret.

######  Assumption 2.1 (Bounded Valuation)

For each round $t$, the customers’ valuations $v^{*}(x_{t})\in[0,B]$ for a
known constant $B$.

In 2.1, a known upper bound is considered for the customers’ valuations, which
is a reasonable assumption for real-life products. It is worth noting that
this assumption also implies the existence of a known upper bound $B$ for the
optimal prices. Moving forward, we introduce the Lipschitz condition in 2.2,
which is widely discussed in the literature [17, 16, 5]. 2.2 is satisfied by
$F$ with bounded derivative as considered in [5, 9, 13], but fits for a
broader class of $F$.

######  Assumption 2.2 (Lipschitz Continuity)

The noise distribution $F$ is Lipschitz continuous with a positive constant
$L$, i.e., $|F(x)-F(y)|\leq L|x-y|,\forall x,y\in\mathbb{R}$.

##  3 Algorithm Design

In this section, we present a distribution-free pricing policy designed to
address the contextual dynamic pricing problem in the presence of unknown
$v^{*}$ and unknown $F$. To tackle this challenge, we propose an episode-based
learning framework, outlined in Algorithm 1, consisting of three phases: a
pure exploration phase, an estimation phase, and a UCB phase. Given the lack
of prior knowledge regarding the horizon length $T$, we employ the doubling
trick to partition the horizon into episodes. This technique eliminates the
requirement of knowing $T$ and allows us to dynamically adapt our pricing
strategy. Furthermore, our algorithmic construction ensures that the size of
candidate prices remains bounded within each episode. The boundedness property
is essential for controlling regret and achieving minimax optimality, ensuring
that our pricing policy performs well under uncertainty. The episode-based
learning framework allows us to adaptively refine our pricing strategy as
additional data is gathered and improved estimations of $v^{*}$ and $F$ are
obtained. By partitioning the horizon into episodes, our approach enables
iterative improvement of the pricing policy, leading to near-optimal
performance.

Algorithm 1 Distribution-Free Dynamic Pricing Algorithm

1:price upper bound $B$, function space $\mathcal{V}$, confidence parameter
$\delta$

2:Let $k^{*}=\lceil 3\log_{2}\ln(|\mathcal{V}|\delta)\rceil$

3:$//$ warm up

4:for round $t=1,2,\cdots,2^{k^{*}-1}$ do

5: Observe context $x_{t}$

6: Set a price $p_{t}$ uniformly from $(0,B)$

7: Observe the feedback $y_{t}$

8:for episode $k=k^{*},k^{*}+1,\cdots$ do

9: Set the length of the $k$-th episode as $\ell_{k}=2^{k-1}$

10: Set the length of the exploration phase at $k$-th episode as
$T^{e}_{k}=\lceil\ell_{k}^{{\frac{2}{3}}}\ln^{\frac{1}{3}}(|\mathcal{V}|/\delta)\rceil$

11: $//$ exploration phase

12: for round $t=2^{k-1}+1,\cdots,2^{k-1}+T^{e}_{k}$ do

13: Observe context $x_{t}$

14: Set a price $p_{t}$ uniformly from $(0,B)$

15: Observe the feedback $y_{t}$

16: $//$ estimation phase

17: Find the estimator
$\hat{v}_{k}=\mathop{\arg\min}_{v\in\mathcal{V}}\sum_{t=2^{k-1}+1}^{2^{k-1}+T^{e}_{k}}(v(x_{t})-By_{t})^{2}$
by the Offline Least Square Oracle

18: $//$ UCB phase

19: Set the length $T_{k}=\ell_{k}-T^{e}_{k}$

20: Set the discretization number $d_{k}=\lceil T_{k}^{{\frac{1}{3}}}\rceil$

21: for $t=2^{k-1}+T^{e}_{k}+1,\cdots,2^{k}$ do

22: Apply the UCB-LDP on the coming sequential contexts $x_{t}$ with the
estimator $\hat{v}_{k}$, the discretization number $d_{k}$, the length $T_{k}$
and the bound $B$

Estimation. To overcome the challenge of not directly observing the valuation
$v_{t}$ in the dynamic pricing problem, we leverage a key property. During
each episode, we employ a uniform random policy $p_{t}\sim Unif(0,B)$ to
generate data for estimating the true value $v^{*}$. This approach results in
a linear regression structure that incorporates the signal of $v^{*}$.
Specifically, we have the following relationship:

$\mathbb{E}[By_{t}|x_{t}]=B\mathbb{E}[\mathbb{E}[\mathbf{I}_{\\{p_{t}\leq
v^{*}(x_{t})+\epsilon_{t}\\}}|x_{t},\epsilon_{t}]|x_{t}]=B\mathbb{E}\Big{[}\frac{v^{*}(x_{t})+\epsilon_{t}}{B}\Big{|}x_{t}\Big{]}=v^{*}(x_{t})$

This property allows us to decouple the estimation of $v^{*}$ from the unknown
distribution $F$, providing a means to estimate $v^{*}$ independently. To
achieve the minimax optimality, we set the exploration phase length
$T^{e}_{k}=\lceil\ell_{k}^{\frac{2}{3}}\ln^{\frac{1}{3}}(|\mathcal{V}|/\delta)\rceil$.
This choice ensures minimax optimality in terms of $T$ and $|\mathcal{V}|$. To
ensure that the exploration phase length does not exceed $\ell_{k}$, we
uniformly set prices for the rounds before the episode $k^{*}=\lceil
3\log_{2}\ln(|\mathcal{V}|/\delta)\rceil$.

Initially, we focus on the case where the function space is finite, i.e.,
$|\mathcal{V}|<\infty$. The expected estimation error for this case is
presented in Lemma 3.1. However, it is worth noting that our results can be
extended to infinite function spaces using standard learning tools such as
metric entropy. By applying these techniques, our proposed approach can handle
more general scenarios. In Section 5, we further extend our results to general
offline regression oracles and classification oracles, broadening the
applicability of our findings. By addressing these broader problem domains, we
demonstrate the versatility and relevance of our proposed methodology in a
wider range of applications.

###### Remark 3.1

In Algorithm 1, we estimate the valuation function $v^{*}$ using only the
samples collected in the current episode $k$. However, we can also leverage
all the previously data obtained from the exploration phases. Despite this
possibility, incorporating the previous data does not change the final regret
order, as the sample size is of order
$\mathcal{O}(\ell_{k}^{{\frac{2}{3}}}\ln^{\frac{1}{3}}(|\mathcal{V}|/\delta))$.
To maintain clarity, we choose to feed the data to the offline oracle only in
episode $k$ to obtain $\hat{v}_{k}$. This approach ensures that the estimation
process remains focused on the current episode, enhancing the readability of
our algorithm.

###### Lemma 3.1

The estimator $\hat{v}_{k}$ satisfies

$\mathbb{E}[(\hat{v}_{k}(x)-v^{*}(x))^{2}]\leq\frac{18B\log\left(|\mathcal{V}|\log_{2}(T_{k}^{e})/\delta\right)}{T_{k}^{e}}$

with probability at least $1-\delta$.

Proof.  Consider the data collected at the episode $k$. Then for any round $t$
satisfying $\ell_{k}<t\leq\ell_{k}+T_{k}^{e}$ and any $v\in\mathcal{V}$, we
denote the random variable

$Z_{t}=({v}(x_{t})-By_{t})^{2}-({v}^{*}(x_{t})-By_{t})^{2}.$

Furthermore, we have

$\displaystyle\mathbb{E}[Z_{t}]$
$\displaystyle=\mathbb{E}[({v}_{k}(x_{t})-By_{t})^{2}-(By_{t}-{v}^{*}(x_{t}))^{2}]$
$\displaystyle=\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))({v}(x_{t})+{v}^{*}(x_{t})-2By_{t})]$
$\displaystyle=\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))\mathbb{E}_{y_{t}}[({v}(x_{t})+{v}^{*}(x_{t})-2By_{t})|x_{t}]]$
$\displaystyle=\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))^{2}].$

Therefore, we obtain

$\displaystyle Var(Z_{t})$ $\displaystyle\leq\mathbb{E}[Z_{t}^{2}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))^{2}({v}(x_{t})+{v}^{*}(x_{t})-2By_{t})^{2}]$
$\displaystyle\leq$ $\displaystyle
4B\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))^{2}]$ $\displaystyle=$ $\displaystyle
16B^{2}\mathbb{E}[Z_{t}].$

From Freedman’s inequality, we have

$\displaystyle\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}\mathbb{E}[Z_{t}]-\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}Z_{t}$
$\displaystyle\leq$ $\displaystyle
4\sqrt{\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}Var(Z_{t})\ln(1/\delta)}+2B\ln(1/\delta)$
$\displaystyle\leq$ $\displaystyle
16B\sqrt{\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}\mathbb{E}[Z_{t}]\ln(1/\delta)}+2B\ln(1/\delta).$

with probability at least $1-\delta\log_{2}(T_{k}^{e})$. The last inequality
is due to the boundedness of $y_{t}$. Solving
$\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}\mathbb{E}[Z_{t}]$ from the above
inequality yields

$\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}\mathbb{E}[Z_{t}]\leq{18B\ln(1/\delta)}+\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}Z_{t}.$

By a union bound, with probability at least
$1-|\mathcal{V}|\log_{2}(T_{k}^{e})\delta$,

$\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))^{2}]\leq\frac{18B\ln(1/\delta)}{T_{k}^{e}}+\frac{1}{T_{k}^{e}}\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}Z_{t}.$

Then from the algorithmic construction, we know
$\sum_{t=\ell_{k}+1}^{\ell_{k}+T_{k}^{e}}Z_{t}\leq 0$ for $\hat{v}_{k}$. We
immediately obtain that

$\mathbb{E}[({v}(x_{t})-{v}^{*}(x_{t}))^{2}]\leq\frac{18B\ln(1/\delta)}{T_{k}^{e}}$

holds with probability at least $1-|\mathcal{V}|\log_{2}(T_{k}^{e})\delta$.

$\square$

Algorithm 2 Upper Confidence Bound with Layered Data Partitioning (UCB-LDP)

1:the estimator $\hat{v}$, the discretization number $d$, the length $T$ and
the bound $B$

2:Cut the $F$-learning interval
$[-\|\hat{v}\|_{\infty},B+\|\hat{v}\|_{\infty}]$ into $d$ same-length sub-
intervals with their midpoints denoted as $m_{1},\cdots,m_{d}$

3:Set $S=\lceil\ln T\rceil$, $\Psi_{t}^{s}=\emptyset$ for $s\in[S]$

4:for round $t=1,2,\cdots,T$ do

5: Observe the context $x_{t}$

6: Let $s=1$ and
$\mathcal{A}_{1}=\\{j\in[d_{k}]|m_{j}+\hat{v}(x_{t})\in(0,B)\\}$

7: repeat

8: Compute
$\mathcal{D}_{t-1,s}^{j}=\\{\tau\in\Psi_{t}^{s}|m_{j}+\hat{v}(x_{\tau})=p_{\tau}\\}$
for all $j\in[d]$

9: For all $j\in[d]$, compute the average of $1-F(m_{j})$ as
$w^{j}_{t,s}=\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}y_{\tau}}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}$

10: For all $j\in[d]$, compute the radius of $1-F(m_{j})$ as
$r^{j}_{t,s}=\min\left\\{\sqrt{\frac{\log(Td/\delta)}{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}},1\right\\}$

11: if $r_{t,s}^{j}\leq 1/\sqrt{T}$ for all $j\in\mathcal{A}_{s}$ then

12: Choose the index
$j_{t}=\mathop{\arg\max}_{j\in\mathcal{A}_{s}}(m_{j}+\hat{v}(x_{t}))(w^{j}_{t,s}+r_{t,s}^{j})$

13: Update the round collection $\Psi_{t+1}^{\sigma}=\Psi_{t}^{\sigma}$ for
all $\sigma\in[S]$

14: $//$ step (a)

15: else if $(m_{j}+\hat{v}(x_{t}))r^{j}_{t,s}\leq B2^{-s}$ for all
$j\in\mathcal{A}_{s}$ then

16: Let
$\mathcal{A}_{s+1}=\\{j\in\mathcal{A}_{s}|(m_{j}+\hat{v}(x_{t}))(w^{j}_{t,s}+r_{t,s}^{j})\geq\max\limits_{j^{\prime}\in\mathcal{A}_{s}}(m_{j^{\prime}}+\hat{v}(x_{t}))(w^{j^{\prime}}_{t,s}+r_{t,s}^{j^{\prime}})-B2^{1-s}\\}$

17: Let $s\leftarrow s+1$

18: $//$ step (b)

19: else

20: Choose $j_{t}$ such that $(m_{j}+\hat{v}(x_{t}))r_{t,s}^{j}>B2^{-s}$

21: Update $\Psi_{t+1}^{s}=\Psi_{t}^{s}\cup\\{t\\}$

22: until An index $j_{t}$ is found

23: Set the price $p_{t}=m_{j_{t}}+\hat{v}(x_{t})$

Discretization for F-Learning. During the UCB phase in episode $k$, we utilize
the regression estimator $\hat{v}_{k}$ to drive a UCB procedure that strikes a
balance between $F$-learning and revenue maximization. To explore potential
optimal prices $p\in(0,B)$ efficiently, we focus our attention on the
$F$-values within the range of $p-\hat{v}_{k}(x)$. Specifically, we restrict
our $F$-learning to the interval
$[-\|\hat{v}_{k}\|_{\infty},B+\|\hat{v}_{k}\|_{\infty}]$ by discretizing it
into $d_{k}$ sub-intervals and concentrating our learning on the $d_{k}$
midpoints $\\{m_{j}\\}_{j\in[d_{k}]}$. This approach, in contrast to [5, 9]
where the entire cumulative distribution function $F$ is estimated, simplifies
the estimation task by focusing on a limited number of $F$ values. This
discretization approach allows for a mutually reinforcing process between the
discretized price selection and the accumulation of knowledge in $F$ at these
specific points, creating a closed loop of improvement.

After discretization, Luo et al. [17] formulate the inner UCB as a perturbed
linear bandit problem, with
$\xi^{*}=(1-F(m_{1}),1-F(m_{2}),\cdots,1-F(m_{d_{k}}))$ as the parameter for
this perturbed linear bandit. The action takes the form
$(0,0,\cdots,p_{t},\cdots,0)$, with a single non-zero element
$p_{t}=m_{j}+\hat{v}_{k}(x_{t})$ at the $j$-th position. Although the
$\xi^{*}$ parameter is perturbed in each round, its magnitude can be
controlled due to 2.2 and the estimation error of $\hat{v}_{k}$. While Luo et
al. [17] employ the elliptical potential lemma from [1] to address this
problem, the formulation fails to fully exploit the special structure of the
dynamic pricing problem and can be optimized further to achieve a suboptimal
regret order.

A crucial observation is that the number of actions in a given episode is
bounded by $d_{k}$. Existing literature, such as [15, 2], has demonstrated
that in linear contextual bandit problems, the elliptical potential lemma is
unnecessary. They have shown that the regret bound can be reduced to
$\mathcal{O}(\sqrt{d_{k}T_{k}\log^{3}(KT_{k})})$ when dealing with time-
varying action sets with bounded size $K$.

However, the methods proposed in [15, 2] cannot be directly applied to our
current setting. One key challenge arises from the normalized parameters. If
we were to normalize $\xi^{*}$, an additional $\sqrt{d_{k}}$ term would still
arise. However, we can take advantage of the fact that the action vector has
only one non-zero component and satisfies
$|(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}))|\leq B$. This observation allows us
to focus on the UCB for each component individually, rather than considering
the entire parameter vector. By doing so, we can exploit the $\ell_{\infty}$
estimation error for linear parameters, which excludes the extra
$\sqrt{d_{k}}$ term compared to the $\ell_{2}$ norm. Therefore, we can apply
the Azuma’s inequality rather than the elliptical potential lemma to obtain
concentration bounds. To obtain statistical dependence, we apply the layered
data partitioning technique in our algorithmic construction.

The second challenge we face is related to the perturbation of $\xi^{*}$. This
perturbation introduces misspecification errors in the reformulated linear
bandit, resulting in a complex construction of the UCB. When considering the
price $p_{t}$ and covariate $x_{t}$, $\mathbb{E}[y_{t}]$ is equal to
$1-F(m_{j}+\hat{v}_{k}(x_{t})-v^{*}(x_{t}))$, which is only approximately
equal to $\xi_{j}^{*}$ rather than an exact equality. It is evident, as
indicated in 2.2, that estimation errors of $\hat{v}_{k}$ can propagate into
misspecification errors. This assumption implies that the perturbation is
proportional to the estimation error. If the estimator $\hat{v}_{k}$ is
accurate, then $\xi^{*}$ remains unperturbed, and the problem reduces to a
classic linear bandit. However, a poorer estimator implies a larger
perturbation, increasing the difficulty in solving the perturbed linear bandit
problem and potentially leading to a larger regret as shown in Theorem 4.1.

Layered Data Partitioning. In each time period $t$, we begin by constructing
the candidate action set
$\mathcal{A}_{1}=\\{j\in[d_{k}]|m_{j}+\hat{v}_{k}(x_{t})\in(0,B)\\}$. Instead
of utilizing all the data collected prior to time $t$ for an ordinary least
squares estimator for $\xi^{*}$, we divide the preceding time periods into
disjoint layers indexed by $s\in[S]$, such that
$\cup_{s\in[S]}\Psi_{t}^{s}=[t-1]$. At time $t$, we sequentially visit the
layers $s\in[S]$ and, within each layer, calculate the upper confidence bound
for each $\xi^{*}_{j}$ using data collected exclusively during the periods in
$\Psi_{t}^{s}$. From OLS estimator for $\xi^{*}$, we know that the estimator
for $\xi_{j}^{*}$ is

$w^{j}_{t,s}=\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}y_{\tau}}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}},$

where $\mathcal{D}_{t-1,s}^{j}$ contains the rounds that select the index
corresponding to $1-F(m_{j})$. To determine the radius for $\xi^{*}_{j}$, we
design the following expression:
$r^{j}_{t,s}=\min\left\\{\sqrt{\frac{\log(T_{k}d_{k}/\delta)}{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}},1\right\\}.$
If $\mathcal{D}_{t-1,s}^{j}$ is empty, indicating no corresponding rounds were
selected, the UCB for that index is set to infinity.

The UCB property described in Lemma 3.2 is highly intuitive. The first term
captures the variance resulting from the randomness of $y_{t}$ given $x_{t}$
and $p_{t}$, while the second term represents the bias stemming from the
estimation of $\hat{v}_{k}$. As the UCB phase progresses, the variance
gradually diminishes, and the bias caused by estimation errors tends to
approach zero with each subsequent episode. With an increasing number of
samples of $x_{t}$ and $y_{t}$, our constructed $w_{t,s}^{j}$ becomes
increasingly accurate and converges to $\xi^{*}_{j}$. It is important to note
that our constructed UCB does not involve the bias term. This allows us to
eliminate the need for knowledge of the Lipschitz constant. The reason behind
this is that we compare the UCB values on both sides, and the bias term is the
same for all indices. Therefore, we can deduct the bias term at both sides in
Step (a) of the algorithm and the Lipschitz term is implicitly absorbed in the
adaptive term $B2^{1-s}$. This advantage of our algorithm eliminates the need
for explicit knowledge of the Lipschitz constant.

###### Lemma 3.2

Consider the episode $k$, any round $t$ in the episode $k$ and any layer $s$
in the round $t$. Then for each $j\in[d_{k}]$, we have

$|\xi_{j}^{*}-w_{t,s}^{j}|\leq
r_{t,s}^{j}+\frac{L\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}},$

with probability at least $1-\delta/(d_{k}T_{k})$.

Proof.  Due to statistical independence of samples indexed in $\Psi_{t}^{s}$,
we have
$\mathbb{E}[y_{\tau}|x_{\tau}]=1-F(m_{j}+\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau}))$
for ${\tau}\in\mathcal{D}_{t-1}^{s}$. Then we apply the Azuma’s inequality to
$\frac{p_{\tau}^{2}y_{\tau}}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}$.
We can obtain

$\mathbb{P}\left(\Big{|}w_{t,s}^{j}-\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}\mathbb{E}[y_{\tau}|x_{\tau}]}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\Big{|}\geq\frac{\sqrt{\ln(T_{k}d_{k}/\delta)\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{4}}}{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\right)\leq\frac{\delta}{d_{k}T_{k}}$

Thanks to the Cauchy-Schwarz inequality, we have

$\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{4}\leq\left(\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}\right)^{2}.$

Hence, we obtain

$\displaystyle\mathbb{P}\left(\Big{|}w_{t,s}^{j}-\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}\mathbb{E}[y_{\tau}|x_{\tau}]}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\Big{|}\geq
r_{t,s}^{j}\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left(\Big{|}w_{t,s}^{j}-\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}\mathbb{E}[y_{\tau}|x_{\tau}]}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\Big{|}\geq\frac{\sqrt{\ln(T_{k}d_{k}/\delta)\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{4}}}{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\right)$
$\displaystyle\leq$ $\displaystyle\frac{\delta}{d_{k}T_{k}}.$

From 2.2, we can obtain

$\left|\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}(\xi^{*}_{j}-\mathbb{E}[y_{\tau}|x_{\tau}])}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\right|\leq\frac{L\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}},$

so by the triangular inequality, we find

$\displaystyle\mathbb{P}\left(\Big{|}w_{t,s}^{j}-\xi_{j}^{*}\Big{|}\geq
r_{t,s}^{j}+\frac{L\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\right)$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left(\Big{|}w_{t,s}^{j}-\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}\mathbb{E}[y_{t}|x_{t}]}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\Big{|}+\Big{|}\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}(\xi^{*}_{j}-\mathbb{E}[y_{t}|x_{t}])}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\Big{|}\geq
r_{t,s}^{j}+\frac{L\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\right)$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left(\Big{|}w_{t,s}^{j}-\frac{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}\mathbb{E}[y_{t}|x_{t}]}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}\Big{|}\geq
r_{t,s}^{j}\right)$ $\displaystyle\leq$
$\displaystyle\frac{\delta}{d_{k}T_{k}}.$

$\square$

The algorithm commences with $s=1$, corresponding to the widest confidence
bands, and incrementally increases $s$, while simultaneously eliminating sub-
optimal prices using OLS estimates from $\Psi_{t}^{s}$. This procedure is
meticulously designed to ensure that the “stopping layer” $s^{\prime}$
determined at time $t$ solely depends on $\\{\Psi_{t}^{s}\\}_{s\leq
s^{\prime}}$, effectively decoupling the statistical correlation in OLS
estimates. The validity of this property has been formally stated and proven
in [15, 2].

Based on Lemma 3.2, we construct a high-probability event

$\Gamma_{k}=\left\\{|\xi_{j}^{*}-w_{t,s}^{j}|\leq
r_{t,s}^{j}+\frac{L\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}},\forall
t,\forall s,\forall j\right\\}.$

Then by the union bound, we have

$\mathbb{P}(\overline{\Gamma_{k}})\leq\frac{\delta}{d_{k}T_{k}}\times
T_{k}\times d_{k}\times S=\delta S.$

For brevity, we denote
$\eta_{t,s}^{j}=\frac{L\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}$.
Since $x_{t}$ is i.i.d. sampled from a fixed distribution, we know that
$\mathbb{E}_{x}[\eta_{t,s}^{j}]=L\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]$.

Recall that the index of the discrete best price is
$j_{t}^{*}=\mathop{\arg\max}_{j\in[d_{k}]}(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}+\hat{v}_{k}(x_{t})-v^{*}(x_{t})))$.
We define the discrete best price at the layer $s$ as

$j_{t,s}^{*}=\mathop{\arg\max}_{j\in\mathcal{A}_{s}}(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}+\hat{v}_{k}(x_{t})-v^{*}(x_{t}))).$

For simplicity, we introduce the revenue function

$rev_{t}(p)=p(1-F(p-v^{*}(x_{t}))).$

In [2], their algorithm ensures $j^{*}_{t,s}=j^{*}_{t}$, as the optimal action
will not be eliminated when their constructed high-probability event holds. In
contrast, due to the misspecification error being proportional to
$BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]$ when transitioning to a new
layer, the revenue between prices indexed by $j_{t,s}^{*}$ and $j_{t}^{*}$ is
naturally proportional to $s-1$. Combining the above discussion, we proceed to
prove the following lemma.

###### Lemma 3.3

Given the event $\Gamma_{k}$, then for each round $t$ in the episode $k$ and
each layer $s$ in the round $t$, we have

$\mathbb{E}_{x_{t}}[rev_{t}(m_{j_{t}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))]\leq
4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](s-1).$

Proof.  We prove this lemma by induction on $s$. For $s=1$, the lemma holds
naturally as $\mathcal{A}_{1}=[d_{k}]$ and thus $j_{t}^{*}=j_{t,s}^{*}$.
Assume that the bound holds in the layer $s$. It is sufficient to show that
$\mathbb{E}_{x_{t}}[rev_{t}(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{j_{t,s+1}^{*}}+\hat{v}_{k}(x_{t}))]\leq
2BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]$. If $j_{t,s}^{*}=j_{t,s+1}$, the
desired bound holds. Hence we assume that
$j_{t,s+1}\notin\mathcal{A}_{t,s+1}$. Let
$\hat{j}_{t,s}:=\mathop{\arg\max}_{j\in\mathcal{A}_{s}}(w_{t,s}^{j}+r_{t,s}^{j})$
be the index with the highest UCB in $\mathcal{A}_{s}$. From Step (a) we know
$\hat{j}_{t,s}\in\mathcal{A}_{s+1}.$ Then we have

$\displaystyle
rev_{t}(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{j_{t,s+1}^{*}}+\hat{v}_{k}(x_{t}))$
$\displaystyle\leq$ $\displaystyle
rev_{t}(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))$
$\displaystyle\leq$
$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(1-F(m_{j_{t,s}^{*}}))-(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))(1-F(m_{{\hat{j}_{t,s}}}))+2BL|\hat{v}_{k}(x_{t})-v^{*}(x_{t})|.$

From the definition to $\Gamma_{k}$, we know that

$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(1-F(m_{j_{t,s}^{*}}))-(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))(1-F(m_{j_{\hat{j}_{t,s}}}))$
$\displaystyle\leq$
$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(w_{t,s}^{j_{t,s}^{*}}+r_{t,s}^{j_{t,s}^{*}})-(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))(w_{t,s}^{\hat{j}_{t,s}}-r_{t,s}^{\hat{j}_{t,s}})$
$\displaystyle\quad\quad+\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}}+\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{\hat{j}_{t,s}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{\hat{j}_{t,s}}}p_{\tau}^{2}}$
$\displaystyle=$
$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(w_{t,s}^{j_{t,s}^{*}}+r_{t,s}^{j_{t,s}^{*}})-(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))(w_{t,s}^{\hat{j}_{t,s}}+r_{t,s}^{\hat{j}_{t,s}})+2r_{t,s}^{\hat{j}_{t,s}}(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))$
$\displaystyle\quad\quad+\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}}+\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{\hat{j}_{t,s}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{\hat{j}_{t,s}}}p_{\tau}^{2}}$

From algorithmic construction (step (b)), we know
$(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))r_{t,s}^{\hat{j}_{t,s}}\leq B2^{-s}.$
Since $\hat{j}_{t,s}\notin\mathcal{A}_{s}$, the step (a) yields

$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(w_{t,s}^{j_{t,s}^{*}}+r_{t,s}^{j_{t,s}^{*}})-(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))(w_{t,s}^{\hat{j}_{t,s}}+r_{t,s}^{\hat{j}_{t,s}})$
$\displaystyle>$ $\displaystyle B2^{1-s}$ $\displaystyle\geq$ $\displaystyle
2(m_{\hat{j}_{t,s}}+\hat{v}_{k}(x_{t}))r_{t,s}^{\hat{j}_{t,s}}.$

Combing all inequalities above, we obtain

$\displaystyle
rev_{t}(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{j_{t,s+1}^{*}}+\hat{v}_{k}(x_{t}))$
$\displaystyle\leq$ $\displaystyle
2BL|\hat{v}_{k}(x_{t})-v^{*}(x_{t})|+\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}}+\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{\hat{j}_{t,s}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{\hat{j}_{t,s}}}p_{\tau}^{2}}.$

Taking expectation with respect to all referred $x_{\tau}$ yields the desired
inequality.

$\square$

Now, we can effectively control the regret within layer $s$ using
$j^{*}_{t,s}$ as the benchmark. The upper bound in Lemma 3.4 can be divided
into two components: the variance and the bias. As we increase the value of
$s$, the variance decreases exponentially, while the bias only increases
linearly. Therefore, having a larger value of $s$ is advantageous for online
learning.

###### Lemma 3.4

Given the event $\Gamma_{k}$, then for each round $t$ in the episode $k$ and
each layer $s$ in the round $t$, we have

$\displaystyle\mathbb{E}[(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(1-F(m_{j_{t,s}^{*}}))-(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}))]$
$\displaystyle\leq$ $\displaystyle 4B\cdot
2^{-s}+2BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](s-1),\forall
j\in\mathcal{A}_{s}.$

Proof.  Step (a) shows that

$(m_{j}+\hat{v}(x_{t}))(w^{j}_{t,s}+r_{t,s}^{j})\geq(m_{j_{t,s}^{*}}+\hat{v}(x_{t}))(w^{j_{t,s}^{*}}_{t,s-1}+r_{t,s-1}^{j_{t,s}^{*}})-B2^{2-s}.$

Step (b) implies that $(m_{j}+\hat{v}(x_{t}))r_{t,s-1}^{j}\leq B2^{1-s}$ for
all $j\in\mathcal{A}_{s-1}$. Combing two inequalities we obtain

$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}(x_{t}))(w^{j_{t,s}^{*}}_{t,s-1}+r_{t,s-1}^{j_{t,s}^{*}})-(m_{j}+\hat{v}(x_{t}))(w^{j}_{t,s-1}-r_{t,s-1}^{j})$
$\displaystyle\leq$ $\displaystyle
2(m_{j}+\hat{v}(x_{t}))r_{t,s-1}^{j}+B2^{2-s}$ $\displaystyle\leq$
$\displaystyle 4B2^{1-s}.$

Therefore, from the definition of $\Gamma_{k}$ we have

$\displaystyle 4B2^{1-s}$ $\displaystyle\geq$
$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}(x_{t}))(w^{j_{t,s}^{*}}_{t,s-1}+r_{t,s-1}^{j_{t,s}^{*}})-(m_{j}+\hat{v}(x_{t}))(w^{j}_{t,s-1}-r_{t,s-1}^{j})$
$\displaystyle\geq$
$\displaystyle(m_{j_{t,s}^{*}}+\hat{v}(x_{t}))(1-F(m_{j_{t,s}^{*}}))-(m_{j}+\hat{v}(x_{t}))(1-F(m_{j}))$
$\displaystyle\quad\quad-\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t,s}^{*}}}p_{\tau}^{2}}-\frac{BL\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}|\hat{v}_{k}(x_{\tau})-v^{*}(x_{\tau})|}{\sum_{\tau\in\mathcal{D}_{t-1,s}^{j}}p_{\tau}^{2}}.$

Taking expectation over all referred $x_{\tau}$ yields the desired inequality.

$\square$

Based on Lemma 3.3 and Lemma 3.4, it is straightforward to derive the upper
bound of the discrete-part regrets for prices in the layer $s$.

###### Lemma 3.5

Given the event $\Gamma_{k}$, for every round $t$ in the episode $k$, we have

$\mathbb{E}_{x_{t}}[rev_{t}(m_{j_{t}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{j}+\hat{v}_{k}(x_{t}))]\leq
4B\cdot 2^{-s}+4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](3s-2).$

for all $j\in\mathcal{A}_{s}$.

Proof.  It follows from 2.2 and Lemma 3.4 that

$\displaystyle\mathbb{E}_{x_{t}}[rev_{t}(m_{j_{t}^{*}}+\hat{v}_{k}(x_{t}))-rev_{t}(m_{j}+\hat{v}_{k}(x_{t}))]$
$\displaystyle\leq$ $\displaystyle
4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](s-1)+\mathbb{E}_{x_{t}}[(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(1-F(m_{j_{t,s}^{*}}))-rev_{t}(m_{j}+\hat{v}_{k}(x_{t}))]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{x_{t}}[(m_{j_{t,s}^{*}}+\hat{v}_{k}(x_{t}))(1-F(m_{j_{t,s}^{*}}))-(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}))]+2BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x_{k})|](2s-1)$
$\displaystyle\leq$ $\displaystyle 4B\cdot
2^{-s}+2BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](3s-2).$

$\square$

##  4 Regret Analysis

In this section, we analyze the regret of our proposed Algorithm 1. We begin
with analyzing a single episode in Algorithm 1 and then extend it to the
entire horizon.

###  4.1 Upper bounds

From the initial pure exploration phase, we obtain an estimator $\hat{v}_{k}$.
As this estimator guides the UCB procedure, it is important to understand how
the estimation error affects the regret in the UCB phase. A lower error rate
in the estimation is expected to result in less regret. However, achieving a
lower error rate requires a longer exploration phase, which leads to more
regret. Therefore, in addition to the “inner” balance between revenue
maximization and $F$-learning in the UCB phase, there exists an “outer”
balance between the regret in the exploration phase and the regret in the UCB
phase, both related to learning $v^{*}$.

For the round $t$ at the episode $k$, define
${j}_{t}^{*}:=\mathop{\arg\max}_{j\in[d_{k}]}(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}+\hat{v}_{k}(x_{t})-v^{*}(x_{t})))$.
By defining the discrete best prices as
$\tilde{p}_{t}^{*}=m_{j_{t}^{*}}+\hat{v}(x_{t})$, the time $t$ regret can be
decomposed as

$\underbrace{\tilde{p}_{t}^{*}(1-F(\tilde{p}_{t}^{*}-{v}^{*}(x_{t})))-{p}_{t}(1-F({p}_{t}-{v}^{*}(x_{t})))}_{\mathcal{R}_{t}^{1}}+\underbrace{{p}_{t}^{*}(1-F({p}_{t}^{*}-{v}^{*}(x_{t})))-\tilde{p}^{*}_{t}(1-F(\tilde{p}^{*}_{t}-{v}^{*}(x_{t})))}_{\mathcal{R}_{t}^{2}}.$

We refer $\sum_{t=1}^{T}\mathcal{R}_{t}^{1}$ and
$\sum_{t=1}^{T}\mathcal{R}_{t}^{2}$ as the discrete-part and continuous-part
regrets. We first analyze the regret for the inner UCB algorithm. To bound the
discrete-part regret of the inner UCB algorithm, we prove the following
theorem.

###### Lemma 4.1

Under 2.1 and 2.2, the expected regret of the discrete-part satisfies

$\mathbb{E}[\sum_{t=1}^{T}\mathcal{R}_{t}^{1}]\leq\sum_{k=1}^{\lceil\log_{2}T\rceil}\left(8B\sqrt{d_{k}T_{k}\log(T_{k}d_{k}/\delta)\ln
T_{k}}+12BL\ln^{\frac{1}{3}}(|\mathcal{V}|\log
T/\delta)\ell_{k}^{\frac{2}{3}}\log\ell_{k}\right).$

with probability at least $1-\delta$.

Proof.  We consider the episode $k$. Let $\Psi_{0}$ be the set of rounds for
which an alternative is chosen when $r_{t,s}^{j}\leq 1/\sqrt{T_{k}}$. Since
$2^{-S}\leq 1/\sqrt{T_{k}}$, we have
$\Psi_{0}\cup\cup_{s\in[S]}\Psi^{s}_{T_{k}+1}=[T_{k}]$.

Recall
${j}_{t}^{*}:=\mathop{\arg\max}_{j\in[d_{k}]}(m_{j}+\hat{v}_{k}(x_{t}))(1-F(m_{j}+\hat{v}_{k}(x_{t})-v^{*}(x_{t})))$
and we define the discrete empirical best price as
$\tilde{p}_{t}^{*}=m_{{j}_{t}^{*}}+\hat{v}_{k}(x_{t})$. We first bound the
regret $\mathbb{E}[\sum_{t=2^{k-1}+T_{k}^{e}+1}^{2^{k}}\mathcal{R}_{t}^{1}]$
at the episode $k$ as following:

$\displaystyle\mathbb{E}[\sum_{t=2^{k-1}+T_{k}^{e}+1}^{2^{k}}\mathcal{R}_{t}^{1}]=$
$\displaystyle\sum_{t=2^{k-1}+T_{k}^{e}+1}^{2^{k}}\mathbb{E}\left[\tilde{p}_{t}^{*}(1-F(\tilde{p}_{t}^{*}-{v}^{*}(x_{t})))-{p}_{t}(1-F({p}_{t}-{v}^{*}(x_{t})))\right]$
$\displaystyle=$
$\displaystyle\sum_{t=2^{k-1}+T_{k}^{e}+1}^{2^{k}}\mathbb{E}\Big{[}rev_{t}(\tilde{p}^{*}_{t})-rev_{t}({p}_{t})\Big{]}$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{S}\sum_{t\in\Psi_{T_{k}+1}^{s}}\mathbb{E}\Big{[}rev_{t}(\tilde{p}^{*}_{t})-rev_{t}({p}_{t})\Big{]}$
$\displaystyle\leq$ $\displaystyle\sum_{s=1}^{S}4B\cdot
2^{-s}|\Psi_{T_{k}+1}^{s}|+4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](3s-2)|\Psi_{T_{k}+1}^{s}|,$

where the last inequality is due to Lemma 3.5.

From Lemma B.2, we have

$|\Psi_{T_{k}+1}^{s}|\leq
2^{s}\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}.$

Putting it back yields

$\displaystyle\sum_{s=1}^{S}4B\cdot
2^{-s}|\Psi_{T_{k}+1}^{s}|+4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|](3s-2)|\Psi_{T_{k}+1}^{s}|$
$\displaystyle\leq$
$\displaystyle\sum_{s=1}^{S}4B\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}+4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]\sum_{s=1}^{S}(3s-2)|\Psi_{T_{k}+1}^{s}|$
$\displaystyle\leq$ $\displaystyle
4B\sqrt{2d_{k}\log(T_{k}d_{k}/\delta)S\sum_{s=1}^{S}|\Psi_{T_{k}+1}^{s}|}+4BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]\cdot
3T_{k}\log T_{k}$ $\displaystyle\leq$ $\displaystyle
8B\sqrt{d_{k}T_{k}\log(T_{k}d_{k}/\delta)\ln
T_{k}}+12BL\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]T_{k}\log T_{k}.$

The second inequality is the Cauchy-Schwarz inequality.

Notice that $T_{k}\leq\ell_{k}$ and

$\mathbb{E}_{x}[|\hat{v}_{k}(x)-v^{*}(x)|]\leq\sqrt{\mathbb{E}_{x}[(\hat{v}_{k}(x)-v^{*}(x))^{2}]}\leq\ln^{\frac{1}{3}}(|\mathcal{V}|\log
T/\delta)\ell_{k}^{-\frac{1}{3}}.$

due to Lemma 3.1. We obtain the desired result by summing over all episodes.

$\square$

In Lemma 4.1, the first term saves an additional $\sqrt{d_{k}}$ compared to
the regret bounds presented in [16]. This term captures the impact of
uncertainty in estimating the values of points on $F$ and its influence on the
regret bounds. It signifies the importance of accurately estimating the
underlying distribution and how uncertainty in these estimates affects the
regret. The second term in Lemma 4.1 arises from the transformation of
baselines in the linear bandit problems. It highlights the connection between
the estimation error of $\hat{v}_{k}$ and the resulting regret bounds. The
presence of this component illustrates how inaccuracies in estimating the
baselines can influence the regret in the UCB phase. Essentially, it indicates
that a higher level of estimation accuracy leads to a lower regret in the UCB
phase.

We then delve into the analysis of the continuous-part of regret, denoted as
$\sum_{t=1}^{T}\mathcal{R}_{t}^{2}$. A denser discretization, achieved by
increasing the number of price points, leads to a reduction in continuous-part
regret. This is because a finer grid of prices brings the discrete best price
closer to the overall best price. Due to algorithmic construction, the
continuous-part regret can be bounded by
$\mathcal{O}(\frac{\ell_{k}}{d_{k}})$. However, it is important to note that a
larger value of $d_{k}$ results in higher discrete-part regret, as indicated
by Lemma 4.1. This is due to the increased number of candidate prices and the
resulting complexity in the search process. Therefore, it is necessary to find
an appropriate value of $d_{k}$ that optimally balances the discrete-part and
continuous-part regrets. One approach to achieving this balance is to scale
$d_{k}$ with $T_{k}^{\frac{1}{3}}$, which allows for effective regulation of
the trade-off between the discrete-part and continuous-part regret.

###### Lemma 4.2

Under 2.1, the expected regret of the continuous-part satisfies

$\mathbb{E}[\sum_{t=1}^{T}\mathcal{R}_{t}^{2}]\leq\sum_{k=1}^{\lceil\log_{2}T\rceil}\frac{4BT_{k}}{d_{k}}.$

Proof.  We consider the continuous-part regret at each round $t$ in the
episode $k$. It admits the form

$p_{t}^{*}(1-F(p_{t}^{*}-v^{*}(x_{t})))-\tilde{p}_{t}^{*}(1-F(\tilde{p}_{t}^{*}-v^{*}(x_{t}))),$

where $p_{t}^{*}$ is the overall best price and $\tilde{p}_{t}^{*}$ is the
discrete best price among the candidate set.

Denote $\dot{p}_{t}=\max\\{0,\max_{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq
p_{t}^{*}}(m_{j}+\hat{v}_{k}(x_{t}))\\}$. Then we discuss case by case.

  1. 1.

$\\{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq p_{t}^{*}\\}=\emptyset$. Then we
have $\dot{p}_{t}=0$ and

$p_{t}^{*}\leq
m_{1}+\hat{v}_{k}(x_{t})\leq-\|\hat{v}_{k}\|_{\infty}+\frac{B+2\|\hat{v}_{k}\|_{\infty}}{2d_{k}}+\|\hat{v}_{k}\|_{\infty}\leq\frac{B+2\|\hat{v}_{k}\|_{\infty}}{2d_{k}}\leq\frac{3B}{2d_{k}}.$

Therefore, we have $0\leq p_{t}^{*}-\dot{p}_{t}\leq\frac{3B}{2d_{k}}$.

  2. 2.

$\\{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq p_{t}^{*}\\}\neq\emptyset$ and
$\max_{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq
p_{t}^{*}}(m_{j}+\hat{v}_{k}(x_{t}))<m_{d_{k}}+\hat{v}_{k}(x_{t})$. Then we
have $\max_{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq
p_{t}^{*}}(m_{j}+\hat{v}_{k}(x_{t}))\leq\dot{p}_{t}\leq\max_{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq
p_{t}^{*}}(m_{j}+\hat{v}_{k}(x_{t}))+\frac{3B}{2d_{k}}$. Namely, we have
$0\leq p_{t}^{*}-\dot{p}_{t}\leq\frac{3B}{2d_{k}}.$

  3. 3.

$\\{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq p_{t}^{*}\\}\neq\emptyset$ and
$\max_{j\in[d_{k}],m_{j}+\hat{v}_{k}(x_{t})\leq
p_{t}^{*}}(m_{j}+\hat{v}_{k}(x_{t}))=m_{d_{k}}+\hat{v}_{k}(x_{t})$. Since
$m_{d_{k}}+\hat{v}_{k}(x_{t})\geq
B+\hat{v}_{k}(x_{t})-\frac{3B}{2d_{k}}-\|\hat{v}_{k}\|_{\infty}\geq
B-\frac{3B}{2d_{k}}$, then we have $B-\frac{3B}{2d_{k}}\leq
m_{d_{k}}+\hat{v}_{k}(x_{t})\leq p_{t}^{*}\leq B$. Therefore we have
$p_{t}^{*}-\dot{p}_{t}\leq\frac{3B}{2d_{k}}$.

From above discussion, we conclude that $0\leq
p_{t}^{*}-\dot{p}_{t}\leq\frac{3B}{2d_{k}}$. Hence we have

$\displaystyle
p_{t}^{*}(1-F(p_{t}^{*}-v^{*}(x_{t})))-\dot{p}_{t}^{*}(1-F(\dot{p}_{t}^{*}-v^{*}(x_{t})))$
$\displaystyle\leq$ $\displaystyle
p_{t}^{*}(1-F(\dot{p}_{t}-v^{*}(x_{t})))-\dot{p}_{t}^{*}(1-F(\dot{p}_{t}^{*}-v^{*}(x_{t})))$
$\displaystyle\leq$
$\displaystyle(p_{t}^{*}-\dot{p}_{t})(1-F(\dot{p}_{t}-v^{*}(x_{t})))$
$\displaystyle\leq$ $\displaystyle\frac{3B}{2d_{k}}.$

We first sum over all rounds in the episode $k$ and then sum over all
episodes. We can obtain the desired results.

$\square$

Combining all previous lemmas, we are capable of proving the following
theorem, showcasing the $\mathcal{O}(T^{\frac{2}{3}})$ regret upper bound.

###### Theorem 4.1

Under 2.1 and 2.2, the expected regret satisfies

$\mathbb{E}[Reg(T)]=\mathcal{O}(BT^{\frac{2}{3}}\log^{\frac{1}{3}}(|\mathcal{V}|/\delta)\log^{\frac{3}{2}}T)$

with probability at least $1-\delta$.

Proof.  Since the price $p_{t}$ is bounded by $B$, then the regret caused by
the exploration phase is

$\sum_{k=1}^{\lceil\log_{2}T\rceil}BT_{k}^{e}\leq
B\sum_{k=1}^{\lceil\log_{2}T\rceil}\ell_{k}^{\frac{2}{3}}\ln^{\frac{1}{3}}(|\mathcal{V}|/\delta)\leq
BT^{\frac{2}{3}}\ln^{\frac{1}{3}}(|\mathcal{V}|/\delta)\log T.$

The warm-up phase cause at most $B2^{k^{*}}\leq B\ln^{3}|\mathcal{V}|$ regret.

We then combine the results in Lemma 4.1 and Lemma 4.2 and obtain

$\mathbb{E}[Reg(T)]\leq\sum_{k=1}^{\lceil\log_{2}T\rceil}\left(\sqrt{d_{k}T_{k}\log(d_{k}\ell_{k}/\delta)\ln
T_{k}}+BL\ln^{\frac{1}{3}}(|\mathcal{V}|\log
T/\delta)\ell_{k}^{\frac{2}{3}}\log\ell_{k}+\frac{3BT_{k}}{2d_{k}}\right)$

Since $d_{k}=\lceil T_{k}^{1/3}\rceil$, we have

$\mathbb{E}[Reg(T)]\leq
3T^{\frac{2}{3}}\sqrt{\log(T^{\frac{4}{3}}/\delta)}(1+\log
T)+B(L+1)T^{\frac{2}{3}}\log^{\frac{1}{3}}(|\mathcal{V}|\log T/\delta)\log
T+B\ln^{3}|\mathcal{V}|.$

$\square$

Lower bound. Xu and Wang [24] demonstrated that under the Lipschitz continuity
condition, any policy will result in a regret of at least
$\Omega(T^{\frac{2}{3}})$. This finding establishes the minimax optimality of
our algorithm, up to logarithmic terms. However, there remains a gap of order
$|\mathcal{V}|$ in terms of exploration, which is an area for future research.
The Lipschitz continuity assumption is crucial as it enables us to control the
misspecification error in the regret analysis.

Without the Lipschitz condition, Xu and Wang [24] proposed an algorithm with a
regret bound of $\mathcal{O}(T^{\frac{3}{4}})$. In their work, they discretize
the linear parameter space and distribution space to form the policy space,
reducing the original problem into an EXP4 agent. Although they discretize the
distribution in a similar way to us, they still consider finding a good
distribution within the given set, resulting in a policy space of size
$\mathcal{O}(2^{d_{k}})$. In contrast, for setting a suitable price, we only
need to evaluate at $d_{k}$ points. This observation effectively reduces the
search space from $\mathcal{O}(2^{d_{k}})$ to $\mathcal{O}(d_{k})$, leading to
exponential decrease in both regret and time complexity.

However, it is currently unknown whether their bound is tight in the absence
of the Lipschitz continuity assumption. Further investigation is required to
explore the tightness of the regret bound without the Lipschitz assumption.

##  5 Discussion

In this section, we explore several extensions and improvements to the
existing framework, aiming to enhance our understanding of the theoretical
results and their applications.

General offline regression oracle. To simplify the discussion on the
estimation process, we consider a natural approach of reducing it to the
general offline regression oracle. This approach involves an offline
regression oracle associated with $\mathcal{V}$. The offline regression oracle
is a procedure that generates a predictor based on the input data.

###### Assumption 5.1

The general offline regression oracle takes $n$ samples of the form
$(x_{i},y_{i})$, independently and identically drawn according to a fixed
distribution such that $\mathbb{E}[By_{i}|x_{i}]=v^{*}(x_{i})$ for
$v^{*}\in\mathcal{V}$. It returns a predictor $\hat{v}\in\mathcal{V}$ which
satisfies that for any $\delta>0$

$\mathbb{E}_{x}[(\hat{v}(x)-v^{*}(x))^{2}]\leq\frac{\rho_{\mathcal{V}}(\delta)}{n}.$

holds with probability at least $1-\delta$.

This assumption describes the estimation accuracy in statistical learning
tasks. The quantity $\rho_{\mathcal{V}}(\delta)$ in 5.1 reflects the
properties of the function space $\mathcal{V}$ and decreases as $\delta$
decreases. Moreover, the function $\frac{\rho_{\mathcal{V}}(\delta)}{n}$
serves as an upper bound on the squared $L^{2}$ distance between the true
value $v^{*}$ and the estimated value $\hat{v}$ in expectation. Under
realizability assumption (i.e., $v^{*}\in\mathcal{V}$), this squared distance
corresponds to the estimation error of $\hat{v}$. Characterizing sharp bounds
on the estimation error and developing efficient algorithms to achieve such
bounds are fundamental tasks in the field of statistical learning.

The choice of function class $\mathcal{V}$ is flexible and can encompass
various parametric or nonparametric models, including Lipschitz function
classes, reproducing kernel Hilbert spaces, and neural networks. To achieve
optimal regret in the contextual dynamic pricing problem, it is crucial to
have a computationally-efficient and statistically-optimal offline regression
oracle tailored to the chosen function class $\mathcal{V}$.

Furthermore, we can extend the results under a general estimation assumption
through a simple corollary. By replacing the quantity
$\ln(|\mathcal{V}|/\delta)$ with $\rho_{\mathcal{V}}(\delta)$ in the
algorithmic steps and proofs, we obtain an extended bound on the expected
regret. For completeness, we present new Algorithm 4 in Appendix.
Specifically, under the assumptions of boundedness, Lipschitz continuity, and
the availability of an offline regression oracle (2.1, 2.2, and 5.1), the
expected regret satisfies
$\mathbb{E}[Reg(T)]=\mathcal{O}(BT^{\frac{2}{3}}\rho_{\mathcal{V}}^{\frac{1}{3}}(\delta)\log^{\frac{3}{2}}T)$
with a probability of at least $1-\delta$.

###### Corollary 5.1

Under 2.1, 2.2 and 5.1, the expected regret of Algorithm 4 satisfies

$\mathbb{E}[Reg(T)]=\mathcal{O}(BT^{\frac{2}{3}}\rho^{\frac{1}{3}}_{\mathcal{V}}(\delta)\log^{\frac{3}{2}}T)$

with probability at least $1-\delta$.

To demonstrate the versatility of the corollary, we can consider specific
cases of function spaces and examine their corresponding bounds on
$\rho_{\mathcal{V}}(\delta)$.

  * •

Finite function space: From Lemma 3.1 we know that the bound
$\rho_{\mathcal{V}}(\delta)=\mathcal{O}\left({\log(|\mathcal{V}|/\delta)}\right)$
for finite function spaces $\mathcal{V}$. This result is particularly
noteworthy as it matches the lower bound of
$\Omega\left(\frac{\log(|\mathcal{V}|)}{n}\right)$ provided by minimax theory
in empirical estimation [10]. The tightness of the method is thus established
and we have presented this special case in Theorem 4.1.

  * •

Linear function space: Linear valuation models have been widely employed in
various dynamic pricing works [9, 17, 24]. Classical analysis techniques
applied to linear regression yield guarantees of
$\rho_{\mathcal{V}}(\delta)=\mathcal{O}\left({d_{0}\log(\delta^{-1})}\right)$
for linear parameters. The tightness of this upper bound has been demonstrated
through empirical minimax theorem [10]. Furthermore, linear regression
techniques can be extended to incorporate sparsity [13] or utilize reproducing
kernel Hilbert spaces [21, 18]. In the context of sparsity, under certain
regularity conditions, we have
$\rho_{\mathcal{V}}(\delta)=\mathcal{O}\left(s_{0}\log(\delta^{-1})\right)$,
where $s_{0}$ is the sparsity parameter.

Linear valuation model. To demonstrate the versatility of our approach, we
provide examples within the widely investigated linear valuation model, which
has been extensively studied in dynamic pricing literature [17, 24, 9, 13,
12]. These examples highlight the adaptability of our method across various
settings, resulting in improved regret orders compared to existing works.

In the linear valuation model, the function space
$\mathcal{V}=\\{\theta^{\top}x:\|\theta\|_{2}\leq 1\\}$ satisfies 5.1 with an
estimation error bound
$\rho_{\mathcal{V}}(\delta)=\mathcal{O}(d_{0}\log(1/\delta))$ under certain
regularity conditions. Recall that we use $d_{0}$ to denote the dimension of
covariates. By imposing a Lipschitz condition, we conclude that Algorithm 1
achieves a regret order of
$\tilde{\mathcal{O}}(d_{0}^{\frac{1}{3}}T^{\frac{2}{3}})$ in the linear
valuation model. Importantly, this regret order represents a significant
improvement over the previously reported order of
$\tilde{\mathcal{O}}(d_{0}T^{\frac{3}{4}})$ in [17] and [24]. Furthermore,
when combined with the lower bound results in [24], our method achieves
minimax optimality, effectively bridging the gap in the previous literature.

Additionally, our approach naturally extends to the case of high-dimensional
covariates with sparsity $s_{0}$. Under mild conditions, Oh et al. [19]
utilizes Lasso regression to obtain an estimator with
$\rho_{\mathcal{V}}(\delta)=\mathcal{O}(s_{0}\log(d_{0}/\delta))$, while
Javanmard and Nazerzadeh [13] employs the regularized maximum likelihood
method, resulting in a similar estimator error. Leveraging sparsity, we are
able to improve the upper bound on regret to
$\tilde{\mathcal{O}}(s_{0}^{\frac{1}{3}}T^{\frac{2}{3}})$.

Interestingly, Luo et al. [16] leverage 5.2 of the revenue functions to
achieve regret of $\tilde{\mathcal{O}}(d_{0}T^{\frac{2}{3}})$. This assumption
assumes second-order smoothness of the expected revenue functions around the
optimal prices and has also been imposed in [17, 6, 16]. In fact, as reported
by [16], dynamic pricing problems satisfying both 2.2 and 5.2 have a regret
lower bound of at least $\Omega(T^{\frac{3}{5}})$. This indicates that the
assumption of second-order smoothness is non-trivial, as it indeed reduces the
difficulty of dynamic pricing problems.

Furthermore, it is worth noting that the assumption of bounded second
derivatives of $F$ also satisfies 5.2. In contrast, for revenue functions with
bounded second derivatives in Fan et al. [9], their method incurs a regret
upper bound of $\mathcal{O}(T^{\frac{5}{7}})$, which is worse than the
performance achieved by our method. This difference in performance can be
attributed to the approach used in Fan et al. [9], which requires estimating
$F^{\prime}$ to determine the price at each round. This estimation introduces
additional error compared to our method, where we only need to estimate the
values of specific points on $F$.

######  Assumption 5.2 (Second-order Smoothness)

Define the general expected revenue functions associated with the noise
distribution $F$ as $rev_{q}(p)=p(1-F(p-q))$. There exists a positive constant
$C$ such that for any $x\in\mathcal{X}$ and $q=v^{*}(x)$, we have
$rev_{q}(p^{*}(x))-rev_{q}(p)\leq C(p^{*}(x)-p)^{2}$.

Knowledge of $F$. In the case where the distribution $F$ is fully known to
sellers, Javanmard and Nazerzadeh [13] investigate this scenario and propose
an algorithm with a regret of $\mathcal{O}(d_{0}\log T)$ under smoothness
conditions for $F$. They demonstrate that if the positive-definiteness of the
covariance matrix does not hold, an alternative method with a regret of
$\mathcal{O}(\sqrt{T\log d_{0}})$ can be employed. The knowledge of $F$ plays
a crucial role in significantly reducing regret. Building upon the algorithm
proposed in [13] and leveraging the assumption of an offline oracle (5.1), we
modify the algorithm in [13] and present our own method in Algorithm 3. The
regret analysis of our method is provided in the following corollary.

###### Corollary 5.2

Under 2.1, A.1, A.2 and 5.1, the expected regret of Algorithm 3 satisfies

$\mathbb{E}[Reg(T)]=\mathcal{O}(\rho_{\mathcal{V}}(\delta)\log T).$

with probability at least $1-\delta$.

Proof.  Given the estimator $\hat{v}_{k}$ using data collected in the previous
episode, $p_{t}$ is only determined by $x_{t}$. Therefore, we know that the
data collected in one episode is i.i.d. due to the i.i.d. nature of
covariates. Thanks to A.1, we apply the Taylor’s expansion at $p_{t}^{*}$ to
$rev_{t}(p_{t})$:

$rev_{t}(p_{t}^{*})-rev_{t}(p_{t})\leq C(p_{t}^{*}-p_{t})^{2},$

where $C=\max_{p}|rev_{t}^{\prime\prime}(p)|$. Using first order conditions,
for the optimal posted price $p_{t}^{*}$, we obtain

$p_{t}^{*}=\frac{1-F(p_{t}^{*}-v^{*}(x_{t}))}{F^{\prime}(p_{t}^{*}-v^{*}(x_{t}))}.$

Since $1-F$ is log-concave, the hazard function
$v\to\frac{F^{\prime}(v)}{1-F(v)}$ is increasing, which implies
$\phi(v)=v-\frac{1-F(v)}{F^{\prime}(v)}$ is strictly increasing. Note that

$\phi(p_{t}^{*}-v^{*}(x_{t}))=p_{t}^{*}-v^{*}(x_{t})-\frac{1-F(p_{t}^{*}-v^{*}(x_{t}))}{F^{\prime}(p_{t}^{*}-v^{*}(x_{t}))}=-v^{*}(x_{t})$

Define $g(v)=v+\phi^{-1}(-v)$ and we know that

$g(v^{*}(x_{t}))=v^{*}(x_{t})+\phi^{-1}(-v^{*}(x_{t}))=p_{t}^{*}.$

Similarly, since $p_{t}$ maximizes $p(1-F(p-\hat{v}_{k}(x_{t})))$, we know
that $g(\hat{v}_{k}(x_{t}))=p_{t}$. From lemma 15 in [13], we know $g$ is
1-Lipschitz and thus we have

$|g(v^{*}(x_{t}))-g(\hat{v}_{k}(x_{t}))|\leq|v^{*}(x_{t})-\hat{v}(x_{t})|.$

Therefore, we have

$rev_{t}(p_{t}^{*})-rev_{t}(p_{t})\leq C(p_{t}^{*}-p_{t})^{2}\leq
C|v^{*}(x_{t})-\hat{v}(x_{t})|^{2}.$

Due to 5.1, we obtain

$\mathbb{E}[rev_{t}(p_{t}^{*})-rev_{t}(p_{t})]\leq\frac{C\rho_{\mathcal{V}}(\delta)}{2^{k-1}}.$

Summing over all rounds in all episodes yields

$\mathbb{E}[Reg(T)]\leq\sum_{k=1}^{\lceil\log
T\rceil}\sum_{t=2^{k-1}}^{2^{k}}\mathbb{E}[rev_{t}(p_{t}^{*})-rev_{t}(p_{t})]\leq
3C\rho_{\mathcal{V}}(\delta)\log T.$

$\square$

Knowledge of $v_{t}$. In many realistic applications, the seller can directly
observe the valuation $v_{t}$ of customers after pricing, for example, through
bidding. Having access to such information simplifies the algorithm design and
eliminates the need for an exploration phase. Hence, we consider the setting
where the valuation of customers can be observed after setting the price
$p_{t}$ and observe the feedback $y_{t}$ at the round $t$. By removing the
exploration phase, we can straightforwardly modify Algorithm 1 by
incorporating the tuple $(x_{t},v_{t})$ instead of $(x_{t},y_{t})$ into the
offline oracles. Remarkably, the regret of the new algorithm remains
$\mathcal{O}(BT^{\frac{2}{3}}\rho^{\frac{1}{3}}_{\mathcal{V}}(\delta)\log^{\frac{3}{2}}T)$.
However, with the knowledge of $v_{t}$, we can improve upon the regret bound
under 5.2. Intuitively, this modification adjusts the continuous-part regret
to $\mathcal{O}(\frac{T_{k}}{d_{k}^{2}})$ in the episode $k$.

###### Corollary 5.3

Under 2.1, 5.2 and 5.1, the expected regret of Algorithm 5 satisfies

$\mathbb{E}[Reg(T)]=\mathcal{O}(T^{\frac{3}{5}}\log
T+\sqrt{\rho_{\mathcal{V}}(\delta)T}).$

with probability at least $1-\delta$.

This bound matches the lower bound $\Omega(T^{\frac{3}{5}})$ reported in [17,
16]. However, since the model in [17, 16] only allows obtaining censored
demand data, it is not clear whether the seller can achieve lower regrets when
it can observe customers’ valuations. In the next discussion, we will
demonstrate how to remove the requirement of valuation knowledge by relying on
classification oracles.

Classification oracle. To estimate the unknown value function $v^{*}$, we
introduce a method that utilizes all the data $(x_{t},p_{t},y_{t})$ from the
previous $(k-1)$-th episode. This allows us to obtain an estimate
$\hat{v}_{k}$ that can be used for pricing in the $k$-th episode. Since
$y_{t}$ is binary and determined by $x_{t}$ and $p_{t}$ through
$\mathbb{P}(y_{t}=1)=1-F(p_{t}-v^{*}(x_{t}))$, we can establish the following
relationships:

$\left\\{\begin{array}[]{rcl}\mathbb{P}(y_{t}=1)>\frac{1}{2},\text{ if
}F^{-1}(\frac{1}{2})+v^{*}(x_{t})-p_{t}>0;\\\
\mathbb{P}(y_{t}=1)=\frac{1}{2},\text{ if
}F^{-1}(\frac{1}{2})+v^{*}(x_{t})-p_{t}=0;\\\
\mathbb{P}(y_{t}=1)<\frac{1}{2},\text{ if
}F^{-1}(\frac{1}{2})+v^{*}(x_{t})-p_{t}<0.\\\ \end{array}\right.$

This allows us to transform the estimation procedure into a classification
problem. By applying a classification oracle, we can obtain a predictor
$\hat{v}\in\mathcal{V}$ that approximates $v^{*}$. The classification oracle
provides a decision boundary based on the unknown function $v^{*}$.

###### Assumption 5.3

Given $n$ samples of the form $(x_{i},p_{i},y_{i})$, the classification oracle
returns a predictor $\hat{v}\in\mathcal{V}$. For any $\delta>0$, with
probability at least $1-\delta$, we have

$\mathbb{E}_{x}[(\hat{v}(x)-v^{*}(x))^{2}]\leq\frac{\rho_{\mathcal{V}}(\delta)}{n^{\alpha}}$

for some positive $\alpha$.

In the work of Luo et al. [17], a linear classification method is applied to
the adaptive data from the previous episode to obtain a linear parameter
estimator. They demonstrate that in the linear valuation model, 5.3 is
satisfied with $\alpha\geq 1$. However, for a general function space, it
remains unknown whether we can design a suitable classification oracle that
meets the required conditions. Typically, classification oracles are
criticized due to the lack of theoretical guarantees for estimation accuracy.

Under Lipschitz condition only, the upper bound for the contextual dynamic
problem remains
$\tilde{\mathcal{O}}(\rho_{\mathcal{V}}(\delta)^{\frac{1}{3}}T^{\frac{2}{3}})$.
However, by incorporating the additional assumption of second-order smoothness
(5.2), we can enhance the performance of the previous work [17]. Based on 5.3
and 5.2, we can derive the following corollary:

###### Corollary 5.4

Under 2.1, 5.2 and 5.3, the expected regret of modifed Algorithm 4 satisfies

$\mathbb{E}[Reg(T)]=\mathcal{O}(T^{\frac{3}{5}}\log
T+\sqrt{\rho_{\mathcal{V}}(\delta)}T^{1-\frac{\alpha}{2}}).$

with probability at least $1-\delta$.

It is worth noting that to achieve minimax optimality, it only requires
$\alpha\geq\frac{4}{5}$, which is slightly less than $1$. If we specify
$\mathcal{V}$ to be a linear function space and employ logistic regression to
estimate the unknown parameters, we can improve upon the results in [17] and
match the lower bound $\Omega(T^{\frac{3}{5}})$ reported in [16].

##  6 Conclusion

In conclusion, we propose a novel algorithm for contextual dynamic pricing
that achieves improved regret bounds while minimizing assumptions. Our
algorithm combines an explore-then-UCB approach with layered data
partitioning, achieving a regret upper bound of
$\tilde{\mathcal{O}}(\rho_{\mathcal{V}}^{\frac{1}{3}}(\delta)T^{\frac{2}{3}})$.
It extends beyond linear valuation models, simplifies estimation through
offline regression oracles, and demonstrates improved performance compared to
existing approaches. Our algorithm provides a comprehensive solution to the
contextual dynamic pricing problem with minimax optimality and practical
applicability.

Future research directions for the contextual dynamic pricing problem can
focus on the following aspects. Firstly, investigating the regret lower bound
without assuming Lipschitz continuity of the noise distribution $F$ would
provide a deeper understanding of the problem’s difficulty. Although Xu and
Wang [24] demonstrated a regret upper bound of
$\tilde{\mathcal{O}}(T^{\frac{3}{4}})$, it is conjectured that the lower bound
remains $\Omega(T^{\frac{3}{4}})$ when the Lipschitz continuity assumption is
relaxed.

Secondly, exploring the leading term in the regret bound in terms of function
spaces is an important direction for future research. It is still unknown
whether our achieved regret bound of
$\tilde{\mathcal{O}}(d_{0}^{\frac{1}{3}}T^{\frac{2}{3}})$ is optimal with
respect to the covariate dimension $d_{0}$. Further investigation in this area
would provide insights into the relationship between regret and function space
complexity.

Lastly, improving regret upper bounds for smoother distributions represents a
promising future direction. By incorporating additional second-order
smoothness conditions, it is possible to enhance the regret upper bound to
$\tilde{\mathcal{O}}(T^{\frac{3}{5}})$. Exploring this avenue further would
contribute to a deeper understanding of the impact of distribution smoothness
on regret performance.

## References

  * Abbasi-Yadkori et al. [2011] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Auer [2002] P. Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Besbes and Zeevi [2015] O. Besbes and A. Zeevi.  On the (surprising) sufficiency of linear models for dynamic pricing with demand learning.  _Management Science_ , 61(4):723–739, 2015.
  * Cesa-Bianchi et al. [2019] N. Cesa-Bianchi, T. Cesari, and V. Perchet.  Dynamic pricing with finitely many unknown valuations.  In _Algorithmic Learning Theory_ , pages 247–273. PMLR, 2019.
  * Chen et al. [2024] E. Chen, X. Chen, L. Gao, and J. Li.  Dynamic contextual pricing with doubly non-parametric random utility models.  _arXiv preprint arXiv:2405.06866_ , 2024.
  * Chen and Gallego [2021] N. Chen and G. Gallego.  Nonparametric pricing analytics with customer covariates.  _Operations Research_ , 69(3):974–984, 2021.
  * Choi et al. [2023] Y.-G. Choi, G.-S. Kim, C. Yunseo, W. Cho, M. C. Paik, and M.-h. Oh.  Semi-parametric contextual pricing algorithm using cox proportional hazards model.  In _International Conference on Machine Learning_ , pages 5771–5786. PMLR, 2023.
  * Den Boer [2015] A. V. Den Boer.  Dynamic pricing and learning: historical origins, current research, and new directions.  _Surveys in operations research and management science_ , 20(1):1–18, 2015.
  * Fan et al. [2024] J. Fan, Y. Guo, and M. Yu.  Policy optimization using semiparametric models for dynamic pricing.  _Journal of the American Statistical Association_ , 119(545):552–564, 2024.
  * Fan [1953] K. Fan.  Minimax theorems.  _Proceedings of the National Academy of Sciences of the United States of America_ , 39(1):42, 1953.
  * Foster and Rakhlin [2020] D. Foster and A. Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 3199–3210. PMLR, 2020.
  * Golrezaei et al. [2019] N. Golrezaei, A. Javanmard, and V. Mirrokni.  Dynamic incentive-aware learning: Robust pricing in contextual auctions.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Javanmard and Nazerzadeh [2019] A. Javanmard and H. Nazerzadeh.  Dynamic pricing in high-dimensions.  _Journal of Machine Learning Research_ , 20(9):1–49, 2019.
  * Lattimore and Szepesvári [2020] T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Li et al. [2019] Y. Li, Y. Wang, and Y. Zhou.  Nearly minimax-optimal regret for linearly parameterized bandits.  In _Conference on Learning Theory_ , pages 2173–2174. PMLR, 2019\.
  * Luo et al. [2022] Y. Luo, W. W. Sun, and Y. Liu.  Contextual dynamic pricing with unknown noise: Explore-then-ucb strategy and improved regrets.  _Advances in Neural Information Processing Systems_ , 35:37445–37457, 2022.
  * Luo et al. [2024] Y. Luo, W. W. Sun, and Y. Liu.  Distribution-free contextual dynamic pricing.  _Mathematics of Operations Research_ , 49(1):599–618, 2024.
  * Mendelson and Neeman [2010] S. Mendelson and J. Neeman.  Regularization in kernel learning.  _The Annals of Statistics_ , 38(1):526–565, 2010\.
  * Oh et al. [2021] M.-h. Oh, G. Iyengar, and A. Zeevi.  Sparsity-agnostic lasso bandit.  In _International Conference on Machine Learning_ , pages 8271–8280. PMLR, 2021.
  * Saharan et al. [2020] S. Saharan, S. Bawa, and N. Kumar.  Dynamic pricing techniques for intelligent transportation system in smart cities: A systematic review.  _Computer Communications_ , 150:603–625, 2020.
  * Steinwart et al. [2009] I. Steinwart, D. R. Hush, C. Scovel, et al.  Optimal rates for regularized least squares regression.  In _COLT_ , pages 79–93, 2009.
  * Takemura et al. [2021] K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga, N. Kakimura, and K.-i. Kawarabayashi.  A parameter-free algorithm for misspecified linear contextual bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3367–3375. PMLR, 2021.
  * Wang et al. [2021] Y. Wang, B. Chen, and D. Simchi-Levi.  Multimodal dynamic pricing.  _Management Science_ , 67(10):6136–6152, 2021\.
  * Xu and Wang [2022] J. Xu and Y.-X. Wang.  Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise.  In _International Conference on Artificial Intelligence and Statistics_ , pages 9643–9662. PMLR, 2022.

##  Appendix A Algorithms

Algorithm 3 Distribution-Dependent Dynamic Pricing Algorithm

1:price upper bound $B$, distribution $F$, confidence parameter $\delta$

2:for episode $k=1,2,\cdots$ do

3: Find the estimator $\hat{v}_{k}$ by the Offline Regression Oracle with the
dataset $\\{(x_{t},y_{t})\\}_{t=2^{k-2}+1}^{2^{k-1}}$ (For $k=1$, set
$\hat{v}_{k}=0$)

4: for round $t=2^{k-1}+1,\cdots,2^{k}$ do

5: Observe context $x_{t}$

6: Set a price $p_{t}=\mathop{\arg\max}_{p}p(1-F(p-\hat{v}_{k}(x_{t})))$

7: Observe the feedback $y_{t}$

######  Assumption A.1 (Differentiablity)

The noise distribution $F$ is twice continuously differentiable.

######  Assumption A.2 (Concavity)

The function $F$ and $1-F$ is log-concave.

Algorithm 4 Distribution-Free Dynamic Pricing Algorithm with General Offline
Regression Oracle

1:price upper bound $B$, estimation parameter $\rho_{\mathcal{V}}(\delta)$

2:Let $k^{*}=\lceil 3\log_{2}\rho_{\mathcal{V}}(\delta)\rceil$

3:$//$ warm up

4:for round $t=1,2,\cdots,2^{k^{*}-1}$ do

5: Observe context $x_{t}$

6: Set a price $p_{t}$ uniformly from $(0,B)$

7: Observe the feedback $y_{t}$

8:for episode $k=k^{*},k^{*}+1,\cdots$ do

9: Set the length of the $k$-th episode as $\ell_{k}=2^{k-1}$

10: Set the length of the exploration phase at $k$-th episode as
$T^{e}_{k}=\lceil\ell_{k}^{{\frac{2}{3}}}\rho_{\mathcal{V}}(\delta)\rceil$

11: $//$ exploration phase

12: for round $t=2^{k-1}+1,\cdots,2^{k-1}+T^{e}_{k}$ do

13: Observe context $x_{t}$

14: Set a price $p_{t}$ uniformly from $(0,B)$

15: Observe the feedback $y_{t}$

16: $//$ estimation phase

17: Find the estimator $\hat{v}_{k}$ by the General Offline Regression Oracle

18: $//$ UCB phase

19: Set the length $T_{k}=\ell_{k}-T^{e}_{k}$

20: Set the discretization number $d_{k}=\lceil T_{k}^{{\frac{1}{3}}}\rceil$

21: for $t=2^{k-1}+T^{e}_{k}+1,\cdots,2^{k}$ do

22: Apply the UCB-LDP on the coming sequential contexts $x_{t}$ with the
estimator $\hat{v}_{k}$, the discretization number $d_{k}$, the length $T_{k}$
and the bound $B$

Algorithm 5 Distribution-Free Dynamic Pricing Algorithm with General Offline
Regression Oracle and Observable Valuation

1:price upper bound $B$, estimation parameter $\rho_{\mathcal{V}}(\delta)$

2:for episode $k=1,2,\cdots$ do

3: Feed the collected data in the previous episode to the General Offline
Regression Oracle and obtain an estimator $\hat{v}_{k}$

4: Set the length $T_{k}=2^{k-1}$

5: Set the discretization number $d_{k}=\lceil T_{k}^{{\frac{1}{5}}}\rceil$

6: for $t=2^{k-1}+1,\cdots,2^{k}$ do

7: Apply the UCB-LDP on the coming sequential contexts $x_{t}$ with the
estimator $\hat{v}_{k}$, the discretization number $d_{k}$, the length $T_{k}$
and the bound $B$

##  Appendix B Proofs

###### Lemma B.1

Assuming $|\Psi_{T_{k}+1}^{s}|\geq 2$, we have

$\sum_{t\in\Psi_{T_{k}+1}^{s}}p_{t}r_{t,s}^{j_{t}}\leq
B\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}.$

Proof.  We have

$\sum_{t\in\Psi_{T_{k}+1}^{s}}p_{t}r_{t,s}^{j_{t}}=\sqrt{\log(T_{k}d_{k}/\delta)}\sum_{t\in\Psi_{T_{k}+1}^{s}}\frac{p_{t}}{\sqrt{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t}}p_{\tau}^{2}}}}.$

It suffices to bound the term
$\sum_{t\in\Psi_{T_{k}+1}^{s}}\frac{p_{t}}{\sqrt{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t}}p_{\tau}^{2}}}}$.
Notice that

$\displaystyle\sum_{t\in\Psi_{T_{k}+1}^{s}}\frac{p_{t}}{\sqrt{2\sum_{\tau\in\mathcal{D}_{t-1,s}^{j_{t}}p_{\tau}^{2}}}}$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{d_{k}}\sum_{t\in\mathcal{D}_{T_{k}}^{j}}\frac{p_{t}}{\sqrt{2\sum_{\tau\in\mathcal{D}_{t-1}^{j}}p_{\tau}^{2}}}$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{d_{k}}\sqrt{2\sum_{t\in\mathcal{D}_{T_{k}}^{j}}p_{t}^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{2d_{k}\sum_{j=1}^{d_{k}}\sum_{t\in\mathcal{D}_{T_{k}}^{j}}p_{t}^{2}}$
$\displaystyle\leq$ $\displaystyle B\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|}.$

Therefore, we conclude that

$\sum_{t\in\Psi_{T_{k}+1}^{s}}p_{t}r_{t,s}^{j_{t}}\leq
B\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}.$

$\square$

###### Lemma B.2

For all $s$, we have

$|\Psi_{T_{k}+1}^{s}|\leq
2^{s}\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}.$

Proof.  From Step (b), we know that

$\sum_{t\in\Psi_{T_{k}+1}^{s}}p_{t}r_{t,s}^{j_{t}}\geq
B2^{-s}|\Psi_{T_{k}+1}^{s}|.$

By Lemma B.1, we obtain

$\sum_{t\in\Psi_{T_{k}+1}^{s}}p_{t}r_{t,s}^{j_{t}}\leq
B\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}.$

Therefore, combing above inequalities, we have

$|\Psi_{T_{k}+1}^{s}|\leq
2^{s}\sqrt{2d_{k}|\Psi_{T_{k}+1}^{s}|\log(T_{k}d_{k}/\delta)}.$

$\square$

##  Appendix C Related Material

######  Lemma C.1 (Azuma’s Inequality)

Let $X_{1},\cdots,X_{n}$ be random variables with $|X_{\tau}|\leq a_{\tau}$
for some $a_{\tau}>0,\tau\in[n]$. Then

$\mathbb{P}\left(\Big{|}\sum_{\tau=1}^{n}X_{\tau}-\sum_{\tau=1}^{n}\mathbb{E}[X_{\tau}|X_{1},\cdots,X_{\tau-1}]\Big{|}\geq
2\sqrt{\ln(2/\delta)\sum_{\tau=1}^{n}a_{\tau}^{2}}\right)\leq\delta.$