Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.
Dynamic Pricing with Adversarially-Censored Demands
abstractWe study an online dynamic pricing problem where the potential demand at each time period $t=1,2,\ldots, T$ is stochastic and dependent on the price. However, a perishable inventory is imposed at the beginning of each time $t$, censoring the potential demand if it exceeds the inventory level. To address this problem, we introduce a pricing algorithm based on the optimistic estimates of derivatives. We show that our algorithm achieves $\tilde{O}(\sqrt{T})$ optimal regret even with adversarial inventory series. Our findings advance the state-of-the-art in online decision-making problems with censored feedback, offering a theoretically optimal solution against adversarial observations.
Introduction
The problem of dynamic pricing, where the seller proposes and adjusts their prices over time, has been studied since the seminal work of cournot1897researches. The crux to pricing is to balance the profit of sales per unit with the quantity of sales. Therefore, it is imperative for the seller to learn customers' demand as a function of price (commonly known as the demand curve) on the fly. However, the demand can often be obfuscated by the observed quantity of sales, especially when censored by inventory stockouts. Such instances severely impede the seller from learning the underlying demand distributions, thereby hindering our pursuit of the optimal price.
Existing literature has devoted considerable effort to the intersection of pricing and inventory decisions. Such works often consider scenarios with indirectly observable lost demands keskin2022data, recoverable leftover demands chen2019coordinating, or controllable inventory level chen2023optimal. However, these assumptions do not always align with the realities faced in various common business environments. To illustrate, we present two pertinent examples:
example[Performance Tickets]
Imagine that we manage a touring company that arranges a series of performances featuring a renowned artist across various cities. Each venue has a different seating capacity, which substantially affects how we set ticket prices. If the price is too high, it may deter attendance, leading to lower revenue. On the other hand, setting it too low could mean that tickets sell out quickly, leaving many potential attendees unable to purchase them. We do not know exactly how many people attempt to buy tickets and fail. Moreover, because the performances are unique, there is no assurance that those who miss out on one show will choose or be able to attend another. This variability in venue size across different locations requires us to continually adapt our pricing strategy. With more adaptive prices, we can maximize both attendance and revenue while accommodating unpredictable changes in seat availability.
example[Fruit Retails]
Sweetsop (Annona squamosa, or so-called “sugar apple”) is a particularly-perishable tropical fruit, typically lasting only 2 to 4 days crane2005sugar. Suppose we manage a local fruit shop and have partnered with a nearby farm for the supply of sweetsops during the harvest season. Due to their perishable nature, we receive sweetsops as soon as they are ripe and picked from the farm every day. This irregular supply means that some days we might receive a large quantity while getting very few on other days. We must quickly sell these fruits before they spoil, yet managing the price becomes challenging. If we exhaust our inventory ahead of time, customers will turn to other fruit shops for purchase instead of waiting for our next restock.
Products in the two instances above have the following properties:
enumerate• Inventory levels are determined by natural factors, and are arbitrarily given for different individual time periods.
• Products are perishable and only salable within a single time period.
Problem Overview
In this work, we study a dynamic pricing problem where the products possess these properties. The problem model is defined as follows. At each time $t=1,2,\ldots, T$, we firstly propose a price $p_t$, and then a price-dependent potential demand occurs as $d_t$. However, we might have no access to $d_t$ as it is censored by an adversarial inventory level $\gamma_t$. Instead, we observe a censored demand $D_t = \min\{\gamma_t, d_t\}$ and receive the revenue $r_t$ as a reward at $t$. Our goal is to approach the optimal price $p_t^*$ at every time $t$, thereby maximizing the cumulative revenue.
\fbox{\parbox{0.95\textwidth}{Dynamic pricing with adversarial inventory constraint. For $t=1,2,...,T:$
enumerate[leftmargin=*,align=left]
{0pt}
• The seller (we) receives $\gamma_t$ identical products.
• The seller proposes a price $p_t\geq0$.
• The customers generate an invisible potential demand $d_t\geq 0$, dependent on $p_t$.
• The market reveals an inventory-censored demand $D_t=\min\{\gamma_t, d_t\}$.
• The seller gets a reward $r_t = p_t\cdot D_t$.
• All unsold products perish before $t+1$.
}
}
\paragraph{The notion of “adversarial” inventory.} We characterize this problem as having adversarially-chosen inventory levels, though our setting differs from classical adversarial bandits or online convex optimization. Here, an adversary may pre-commit to an arbitrary inventory sequence $\{\gamma_t\}_{t=1}^T$, while the underlying demand noise remains stochastic---a hybrid model that combines adversarial contexts with stochastic outcomes, following the convention of “adversarial features” in online learning cohen2020feature_journal, liu2021optimal. Since inventory $\gamma_t$ is revealed at the beginning of round $t$, we can define per-round optimal prices $p_t^*$. This leads to a stronger regret benchmark: we compete against this sequence of optimal actions $\{p_t^*\}_{t=1}^T$ rather than the best fixed decision in hindsight typical of standard adversarial settings. This distinction is crucial as the inventory levels create a non-stationary optimization landscape where optimal prices vary dramatically across periods.
Summary of Contributions
We consider the problem setting shown above and assume that the potential demand $d_t=a-bp_t+N_t$ is linear and noisy. Here $a, b\in\mathbb{R}^+$ are fixed unknown parameters and $N_t$ is an unknown and i.i.d. (independently and identically distributed) noise with zero mean. Under this premise, the key to obtaining the optimal price is to accurately learn the expected reward function $r(p)$, which is equivalent to learning the linear parameters $[a,b]$ and the noise distribution. We are faced with three principal challenges:
enumerate• The absence of unbiased observations of the potential demand or its derivatives with respect to $p$, which prevents us from estimating $[a,b]$ directly.
• The dependence of the optimal prices on the noise distribution, which is assumed to be unknown and partially censored.
• The arbitrariness of the inventory levels, leading to non-stationary and highly-differentiated optimal prices $\{p_t^*\}$ over time.
In this paper, we introduce an algorithm that employs innovative techniques to resolve the aforementioned challenges. Firstly, we devise a pure-exploration phase that bypasses the censoring effect and obtains an unbiased estimator of $\frac1{b}$ (which leads to $\hat b$ and $\hat a$ as a consequence). Secondly, we maintain estimates of the noise CDF $F(x)$ and $\int F(x)dx$ over a series of discrete $x$'s, as well as the confidence bounds of each estimate. Thirdly, we design an optimistic strategy, C20CB as “Closest-To-Zero Confidence Bound”, that proposes the price $p_t$ whose reward derivative $r'_t(p_t)$ is probably $0$ or closest to $0$ among a set of discretized prices. As we keep updating the estimates of $r'_t(\cdot)$ with shrinking error bar, we asymptotically approach the optimal price $p^*_t$ since $r'_t(p_t^*)=0$ for any $t=1,2,\ldots, T$.
\paragraph{Novelty.} To the best of our knowledge, we are the first to study the online dynamic pricing problem under adversarial inventory levels. Our C20CB algorithm attains an optimal $\tilde{O}(\sqrt{T})$ regret guarantee with high probability. The methodologies we develop are crucial to our algorithmic design, and are potentially advancing a variety of online decision-making scenarios with censored feedback.
Paper Structure
The rest of this paper is organized as follows. We discuss related works in (ref), and then describe the problem setting in (ref). We propose our main algorithm C20CB in (ref) and analyze its regret guarantee in (ref). We further discuss potential extensions in (ref), followed by a brief conclusion in (ref).
Related Works
Here we discuss the closest related works on dynamic pricing, inventory constraints, and network revenue management. For a broader introduction of related literature, please refer to (ref).
\paragraph{Data-driven dynamic pricing.}
Dynamic pricing for identical products is a well-established research area, starting with kleinberg2003value and continuing through seminal works by besbes2009dynamic, broder2012dynamic, wang2014close, wang2021multimodal. The standard approach involves learning a demand curve from price-sensitive demand arriving in real-time, aiming to approximate the optimal price. kleinberg2003value provided algorithms with regret bounds of $O(T^{\frac23})$ and $O(\sqrt{T})$ for arbitrary and infinitely smooth demand curves, respectively. wang2021multimodal refined this further, offering an $O(T^{\frac{k+1}{2k+1}})$ regret for $k$-times continuously differentiable demand curves. This line of inquiry is also intricately linked to the multi-armed bandit problems lai1985asymptotically, auer2002nonstochastic and continuum-armed bandits kleinberg2004nearly, where each action taken reveals a reward without insight into the foregone rewards of other actions.
\paragraph{Pricing with inventory concerns.}
Dynamic pricing problems begin to incorporate inventory constraints with besbes2009dynamic, which assumed a fixed initial stock available at the start of the selling period. They introduced near-optimal algorithms for both parametric and non-parametric demand distributions, operating under the assumption that the inventory is non-replenishable and non-perishable. wang2014close adopted a comparable framework but allowed customers arrivals to follow a Poisson process. In these earlier works, the actual demand is fully disclosed until the inventory is depleted. Subsequent research allows inventory replenishment, with the seller's decisions encompassing both pricing and restocking at each time interval. chen2019coordinating proposed a demand model subject to additive / multiple noise and developed a policy that achieved $O(\sqrt{T})$ regret. More recent studies chen2020data, keskin2022data explored the pricing of perishable goods where the unsold inventory will expire. However, the uncensored demand is observable as assumed in both works. Specifically, chen2020data allowed recouping backlogged demand, albeit at a cost, and introduced an algorithm with optimal regret. keskin2022data focused on the cases where both fulfilled demands and lost sales were observable.
chenbx2021nonparametric and their subsequent work, chen2023optimal, are the closest works to ours as they adopt similar problem settings: In their works, the demand is censored by the inventory level and any leftover inventory or lost sales disappear at the end of each period. With the assumption of concave reward functions and the restriction of at most $m$ price changes, chenbx2021nonparametric proposed MLE-based algorithms that attain a regret of $\tilde{O}(T^{\frac1{m+1}})$ in the well-separated case and $\tilde{O}(T^{\frac12+\epsilon})$ for some $\epsilon=o(1)$ as $T\rightarrow\infty$ in the general case. Under similar assumptions (except infinite-order smoothness), chen2023optimal developed a reward-difference estimator, with which they not only enhanced the prior result for concave reward functions to $\tilde{O}(\sqrt{T})$ but also obtained a general $\tilde{O}(T^{2/3})$ regret for non-concave reward functions. Our problem model mirrors their difficulty, as we also lack access to both the uncensored demand and its gradient. However, they allowed the sellers to determine inventory levels with sufficient flexibility, hence better balancing the information revealed by the censored demand and the reward from (price, inventory) decisions. On the other hand, we assume that the inventory level at each time period is provided adversarially by nature, which could impede us from learning the optimal price in the worst-case scenarios. Furthermore, due to the non-stationarity of inventory levels in our setting, the optimal price $p_t^*$ deviates over time. Given this, the search-based methods adopted in chen2023optimal are no longer applicable to our problem.
\paragraph{Network Revenue Management (NRM).} NRM talluri2006theory studies pricing and allocation of shared resources in a network. In the settings of besbes2012blind and subsequent works simchi2019blind, miao2024demand, marginal observations for each product can induce adversarial supply due to cross-product resource occupation. We also consider adversarial inventories, but focus on addressing demand censoring and reducing regret via online learning. perakis2010robust likewise used regret and considered censoring in demand data, but their minimax/maximin regret definitions differ from ours, and censoring is mainly used in empirical validation rather than for theoretical solutions. Representative NRM works include gallego1994optimal on dynamic pricing with stochastic demand, establishing structural monotonicity and asymptotic optimality of simple policies; talluri1998analysis showing bid-price controls are near-optimal in large capacities but not strictly optimal; and meissner2012network addressing overbooking with product-specific no-shows via a randomized LP.
Problem Setup
We have defined the problem setting in (ref). To further clarify the scope of our methodology, we make the following very first assumption before introducing further concepts.
assumption[Linear Demand]
Assume the potential demand $d_t=d_t(p):=a-bp+N_t$ is linear and noisy. Denote $d(p):=a-bp$ as the expected potential demand function. Denote $D_t(p):=\min\{\gamma_t, d_t(p)\}$ as the censored demand function.
A linear demand model has been widely used in pricing literature, including lobo2003pricing,van2012models,broder2012dynamic,cohen2021simple. We highlight two primary reasons: (1) According to besbes2015surprising, linear demand allows the prices to converge to the true optimum even under mismatching scenarios. (2) As shown in keskin2014dynamic, the same analysis can be applied to Generalized Linear Model (GLM), which has enhanced capability of capturing the real-world demands (see e.g. bu2022context,wang2021dynamic).
Definitions
Here we define some key quantities that are involved in the algorithm design and analysis. Firstly, we define distributional functions of the noise $N_t$.
definition[Distributional Functions]
For $N_t$ as the demand noise, denote $F(x)$ as its cumulative distribution function (CDF), $x\in\mathbb{R}$. Also, denote the following $G(x)$ as the integrated CDF:
\begin{equation}
G(x):=\int_{-\infty}^x F(\omega)d\omega, x\in\mathbb{R}
\end{equation}
We will make more assumptions on the noise distribution later. Notice that we do not assume the existence of PDF for $N_t$. However, if there exists its PDF in specific cases, we will adopt $f(x)$ as a notation. Then, we define the revenue function and the regret.
definition[Revenue Function]
Denote $r_t(p)$ as the expected revenue function of price $p$, satisfying
\begin{equation}
r_t(p) := p\cdot\mathbb{E}_{N_t}[D_t(p)|\gamma_t], p\geq 0.
\end{equation}
Also, denote $p_t^*:=\mathop{\mathrm{argmax}}_{p}r_t(p)$ as the optimal price at time $t$.
definition[Regret]
Denote
\begin{equation}
Regret:= \sum_{t=1}^T r_t(p_t^*)-r_t(p_t)
\end{equation}
as the cumulative regret (or regret) of the price sequence $\{p_t\}_{t=1}^T$.
The definition of regret inherits from the tradition of online learning, capturing the performance difference between the algorithm-in-use and the best benchmark that an omniscient oracle can achieve (which knows everything except the realization of noise).
Assumptions
Firstly, we assume boundaries for parameters and price.
assumption[Boundedness]
There exist known finite constants $a_{\max}, b_{\min}, b_{ \max}, \gamma_{\min},$ and $ c >0$ such that $0<a\leq a_{\max}$, $0<b_{\min}\leq b\leq b_{\max}$, $\gamma_t\geq\gamma_{\min}$, $N_t\in[-c, c]$. Also, we restrict the proposed price $p_t$ at any $t=1,2,\ldots, T$ satisfies $0\leq p_t\leq p_{\max}$ with a known finite constant $p_{\max}>0$.
The assumption of boundedness on $a, b$ and price is natural as it defines the scope of instances. We justify the assumption of noise with bounded support $[-c, c]$ from two aspects: (1) The upper bound exists without loss of generality due to the existence of inventory-censoring effect. (2) The lower bound exists as we avoid negative demand. Secondly, we make assumptions on the noise distribution.
assumption[Noise Distribution]
Each $N_t$ is drawn from an unknown independent and identical distribution (i.i.d.) satisfying $\mathbb{E}[N_t] = 0$. The CDF $F(x)$ is $L_F$-Lipschitz. Also, according to (ref), we have $F(-c)=0, F(c)=1$.
Thirdly, we make assumptions on the inequality relationships among parameters:
assumption[Inequalities of Parameters]
The parameters and constants involved in the problem setting satisfy the following conditions:
\begin{table}[h]
\begin{tabular}{|l|l|l|ll}
\cline{1-3}
& Assumption & Explanation & & \\ \cline{1-3}
(1)\ & $a-c > \gamma_t, \forall t\in[T]$ & \begin{tabular}[c]{@l@}The demand at $p=0$ is completely censored by any inventory level,\\ since customers will rush to buy until completely out-of-stock.\end{tabular} & & \\ \cline{1-3}
(2)\ & $\gamma_t > 2c, \forall t\in[T]$ & \begin{tabular}[c]{@l@}Inventory level should exceed the width of the noise support.\\ Otherwise we can reshape the noise by capping $N_t$ at $\gamma_t-a+bp_{\max}$.\end{tabular} & & \\ \cline{1-3}
(3)\ & $a-b p_{\max} - c > 0$ & Demands must be positive. & & \\ \cline{1-3}
(4)\ & $\gamma_{\min} > a_{\max} -b_{\min} p_{\max} + c$ & \begin{tabular}[c]{@l@}Demands at $p_t=p_{\max}$ must be uncensored.\\ We denote $\gamma_0:=a_{\max} -b_{\min} p_{\max} + c$ for further use.\end{tabular} & & \\ \cline{1-3}
(5)\ & $p_{\max}\geq \frac{a}{2b}$ & Optimal price must be included in $[0, p_{\max}]$ without loss of generality. & & \\ \cline{1-3}
\end{tabular}
\end{table}
Each assumption in (ref) is justified by an explanation followed. We make Item (3) to avoid simultaneously upper-and lower-censoring effect, which is beyond the scope of this work and considered as an extension. It is worth mentioning that for those boundedness parameters (e.g. $a_{\max}, b_{\max}, c, \gamma_{\min}$), we have to know their exact values, while we only require the existence of $a, b$ without knowing them. Finally, for the benefit of regret analysis, we assume that the time horizon $T$ is sufficiently large, such that its polynomial will not confound any constant or coefficient.
assumption[Large $T$]
For any constant $r=O(1)$, time horizon $T$ is larger than any polynomial of parameters, i.e. $T>\Omega\left((\frac{a_{\max}b_{\max}cp_{\max}}{b_{\min}\gamma_{\min}})^r\right)$.
Algorithm Design
In this section, we present our core algorithm,C20CB (see (ref)), which stands for a Closest-To-Zero Confidence Bound strategy that proposes asymptotically optimal prices over differentiated inventory levels and censoring effects.
algorithm[algorithm omitted — 2,131 chars of source]
comment\begin{algorithm}[htbp]
\caption{C20CB:Closest-To-Zero Confidence Bound}
\begin{algorithmic}[1]
\STATE { Input}: {Parameters $a_{\max}, b_{\min}, b_{\max}, p_{\max}, c$ and self-derived quantities $\tau, \gamma_0, C_a, C_b, C_F, C_G, C_N, C_{\tau}$.}
\STATE STAGE 1: Pure Exploration
\FOR{ $t=1,2,\ldots, \tau$}
\STATE Sample and propose a price $p_t\sim U[0, p_{\max}]$ uniformly at random.
\STATE Observe demand $D_t$, and indicators $e_{i,t}$ as defined in (ref) for $i=1,2,3$.
\ENDFOR
\STATE Estimate
\begin{equation}
\begin{aligned}
\hat b = & \frac1{4p_{\max}\cdot\frac1{\tau}\sum_{t=1}^\tau\frac{e_{1,t}-e_{2,t}}{\gamma_t - \gamma_0}}\\
\hat a = & \frac1{\tau}\sum_{t=1}^{\tau}( \hat b p_{\max}e_{3,t} + \frac{3\gamma_t+\gamma_0}4).
\end{aligned}
\end{equation}
\STATE STAGE 2: Optimistic Acting
\STATE Denote $\Delta := (C_a + C_b\cdot p_{\max})\cdot\frac1{\sqrt{\tau}}$.
\STATE Define $M:=\lfloor\frac{c}{2\Delta}\rfloor$ and $w_k:=2k\Delta, k=-M, -M+1, \ldots, -1,0,1,\ldots,M$.
\FOR{$t=1,2,\ldots, 2M+1$}
\STATE Let $k_t:=-M-1+t$ and propose $p_t=\frac{w_{k_t}-(\gamma_t-\hat a)}{\hat b}$.
\STATE Observe $D_t$ and $\mathds{1}_t:=\mathds{1}[D_t<\gamma_t]$.
\STATE Initialize $F_{k_t}\leftarrow \mathds{1}_t, N_{k_t}\leftarrow 1, G_{k_t}\leftarrow D_t-\gamma_t + c, \Delta_{k_t}\leftarrow C_F\cdot b_{\max}p_{\max} + C_G + C_b\cdot\frac1{\sqrt{\tau}}$.
\ENDFOR
\FOR {$t=1,2,\ldots, T-\tau-(2M+1)$}
\IF{$\gamma_t\geq\frac{\hat a + C_a\cdot\frac1{\sqrt{\tau}}}2 + c$}
\STATE Propose $p_t = \frac{\hat a}{2\hat b}$ and continue to $t+1$ (without recording feedback).
\ENDIF
\STATE Initialize $k_t \leftarrow M$ as the arm to inspect, $\rho_t\leftarrow +\infty$ as the smallest absolute value of the derivative estimates we have observed in Time Period $t$ so far.
\FOR{$k=M, M-1, \ldots, -M+1, -M$}
\STATE Denote $p_{k, t}:=\frac{w_k-(\gamma_t-\hat a)}{\hat b}$ and $\hat r_{k,t}:=\gamma_0 - c + G_k - \hat b \cdot p_{k,t}\cdot F_k$.
\IF {$\hat r_{k, t} - \Delta_{k}\leq 0 \leq \hat r_{k, t} + \Delta_{k}$}
\STATE Update $k_t\leftarrow k, \rho_t\leftarrow 0$, and Break.
\ENDIF
\STATE Let $\rho_{k, t}:=\min\{|\hat r_{k, t} - \Delta_{k}|, |\hat r_{k, t} + \Delta_{k}|\}$ as the smallest absolute derivative estimate of arm $k$.
\IF {$\rho_{k, t} < \rho_t$}
\STATE Update $\rho_t\leftarrow\rho_{k, t}$ and $k_t\leftarrow k$.
\ENDIF
\ENDFOR
\IF{$\hat r_{k, t}-\Delta_k>0, \forall k=-M, -M+1, \ldots, M-1, M$}
\STATE Propose $p_t=\frac{\hat a}{2 \hat b}.$
\ELSE
\STATE Propose $p_t = p_{k_t, t}$.
\ENDIF
\STATE Observe $D_t$ and $\mathds{1}_t=\mathds{1}[D_t < \gamma_t]$.
\STATE Update
\begin{equation}
F_{k_t}\leftarrow\frac{N_{k_t} F_{k_t} + \mathds{1}_t}{N_{k_t}+1},\ G_{k_t}\leftarrow\frac{N_{k_t} G_{k_t} + D_t - \gamma_t + c}{N_{k_t}+1},\ \Delta_{k_t}\leftarrow \frac{C_N}{\sqrt{N_{k_t}+1}} + \frac{C_{\tau}}{\sqrt{\tau}}
\end{equation}
\STATE Update $N_{k_t}\leftarrow N_{k_t} + 1$.
\ENDFOR
\end{algorithmic}
\end{algorithm}
comment\begin{algorithm}[t]
\SetAlgoNoLine
\KwIn{Node $\alpha$'s ID ($ID_{\alpha}$), and node $\alpha$'s
neighbors' IDs within two communication hops.}
\KwOut{The frequency number ($FreNum_{\alpha}$) node $\alpha$ gets assigned.}
$index$ = 0; $FreNum_{\alpha}$ = -1\;
\Repeat{$FreNum_{\alpha} > -1$}{
$Rnd_{\alpha}$ = Random($ID_{\alpha}$, $index$)\;
$Found$ = $TRUE$\;
\For{each node $\beta$ in $\alpha$'s two communication hops
}{
$Rnd_{\beta}$ = Random($ID_{\beta}$, $index$)\;
\If{($Rnd_{\alpha} < Rnd_{\beta}$) or ($Rnd_{\alpha}$ ==
$Rnd_{\beta}$ and $ID_{\alpha} < ID_{\beta}$)\;
}{
$Found$ = $FALSE$; break\;
}
}
\eIf{$Found$}{
$FreNum_{\alpha}$ = $index$\;
}{
$index$ ++\;
}
}
\caption{Frequency Number Computation}
\end{algorithm}
Algorithm Design Overview
Our algorithm has two stages:
enumerate• { STAGE 1: Exploration}: During the first $\tau=\sqrt{T}$ rounds, the seller (we) proposes uniformly random prices in the range of $[0, p_{\max}]$. By the end of STAGE 1, we obtain $\hat{a}$ and $\hat{b}$ as plug-in estimators of $a$ and $b$ in the following stage.
• { STAGE 2: Optimistic Decision}: We estimate the derivatives of the revenue function at discretized prices $\{p_{k,t}\}$'s. For each $p_{k,t}$, we not only estimate $r'_t(p_{k,t})$ but also maintain an error bar of that estimate. At each time $t$, we propose the price whose corresponding error bar covers $0$ or closest to $0$ if no covering exists.
(ref) exhibits several advantageous properties. It is suitable for processing streaming data as the constructions of $\hat a, \hat b, \hat r'_t(\cdot)$ are updated incrementally with each new observation (including $e_{i,t}, D_t, \mathds{1}_t$) without the need of revisiting any historical data. Additionally, it consumes $\tilde{O}(T^{\frac54})$ time complexity and $O(T^{\frac14})$ extra space, which are plausible for large $T$. A potential risk of computation might arise on the calculation of $\hat b$, where $\sum_{t=1}^{\tau}e_{1,t}-e_{2,t}$ can be 0 with a small but nonzero probability. Although this event does not undermine the high-probability regret guarantee, it might still be harmful to the computational system for numerical experiments. To mitigate this incident in practice, we may either extend STAGE 1 until one non-zero $e_{1,t}-e_{2,t}=1$ is observed, or restart STAGE 1 at $t=\tau$.
algorithm[algorithm omitted — 847 chars of source]
algorithm[algorithm omitted — 605 chars of source]
algorithm[algorithm omitted — 1,316 chars of source]
figure[figure omitted — 548 chars of source]
Pure-Exploration to Estimate Parameters from Biased Observations
As shown in (ref), we incorporate a uniform exploration phase to estimate $a$ and $b$, bypassing the obstacle caused by demand censoring. This approach is supported by the following insight: When $Y$ is a uniformly distributed random variable within a closed interval $[L,R]$, and $X$ is another random variable, independent to $Y$ and also distributed within $[L,R]$, we have:
equation[equation omitted — 184 chars of source]
Here the second step uses the Law of Total Expectation. (ref) indicates that we can derive an unbiased estimator of $\mathbb{E}[X]$ through $\mathds{1}[Y\geq X]$ even in the absence of any direct observation of $X$. Looking back to our algorithm, denote $\gamma_{i, t}:=\frac{i\gamma_t + (4-i)\gamma_0}4, i=1,2,3$ as the three quarter points of $\gamma_t$ for $t=1,2,\ldots, T$, and define
equation[equation omitted — 154 chars of source]
When $p_t\sim U[0, p_{\max}]$, we have
equation[equation omitted — 302 chars of source]
The last equality comes from $\mathbb{E}[N_t]=0$. By deploying different $\gamma_{i, t}$ at $i=1,2,3$, we can estimate $a$ and $b$ through the observations of $e_{i,t}$ according to (ref), effectively circumventing the censoring effect. A similar technique has been used by fan2021policy to construct an unbiased estimator of valuation instead of the demand, as we are concerned. However, their application of uniform exploration might be sub-optimal as they adopt an exploration-then-exploitation design. In contrast, our algorithm uses this uniform exploration merely as a trigger of further learning. Our tight regret bound indicates that uniform exploration can still contribute to an optimal algorithm for a broad range of online learning instances.
Optimistic Strategy to Balance Derivatives Estimates v.s. Loss
With $\hat a$ and $\hat b$ established, we have an estimate of the underlying linear demand $d_t(p)=a-bp$. However, we are still unaware of the noise distribution, which is crucial for the current optimal price, since the inventory level $\gamma_t$ partially censors the noise.
In order to balance the learning of noise distribution versus the loss of proposing sub-optimal prices, we apply an optimistic strategy in STAGE 2. Usually, an “optimistic strategy” chooses actions as if the best-case scenario within its current confidence region holds, thereby encouraging exploration of potentially rewarding options while still balancing risk.
STAGE 2 involves the following components:
enumerate[label=(\roman*)]
• We discretize the $[-c,c]$ domain of noise CDF $F(\cdot)$ and its integration $G(\cdot)$ into small intervals of length $2\Delta$, with $\Delta=O(\frac1{T^{1/4}})$. At the center of interval $k$ (which is $2k\Delta$) for each $k=-M, -M+1, \ldots, M$ (with $M:=\lfloor\frac{c}{2\Delta}\rfloor$), we maintain independent estimates of $F$ and $G$, including their expectations and high-confidence error bars.
• At each time $t$, we construct a set of discrete prices $\{p_{k,t}\}_{k=-M}^{M}$ such that the quantity $\gamma_t-\hat a+\hat bp_{k,t}$ matches the center of Interval $k$. Given this, we further construct an estimate of each $r'_t(p_{k,t})$ with plug-in estimators $\hat a, \hat b$ and discrete estimators of $F$ and $G$ for the specific Interval $k$. The estimate includes its expectation and error bar (see (ref)).
• Since the optimal price $p_t^*$ satisfies $r'_t(p_t^*)=0$, we identify the discrete price $p_{k,t}$ where the derivative estimate is “possibly $0$” or “closest to $0$”. To make this, we design (ref) as a component of C20CB and illustrate the process in (ref), which includes the following three cases:
\begin{enumerate}[label=(\alph*)]
• If there exists some $p_{k,t}$ such that the corresponding error bar (of its derivative estimate) contains $0$, we propose the largest price satisfying this condition.
• If there is no $p_{k,t}$ whose corresponding error bar contains $0$ (but there exists an error bar below $0$), we propose the price whose error bound is closest to $0$.
• If all error bars are above $0$, indicating that the reward function is monotonically increasing over the “censoring area”, we propose $p_t=\frac{\hat a}{2\hat b}$ to exploit the non-censoring optimal price $\frac{a}{2b}$. In this case, we do not need to record any observations nor to update any parameter/estimate.
\end{enumerate}
• After proposing the price $p_{k_t, t}$ and observing feedback $D_t$ and $\mathds{1}_t$, we update the estimates of $F(\cdot)$ and $G(\cdot)$ for Interval $k_t$ in which $\gamma_t-\hat a+\hat bp_{k_t,t}$ exists.
In a nutshell, we maintain estimates and error bars of $F(\cdot)$ and $G(\cdot)$ at discrete points $2k\Delta$, and map each $2k\Delta$ to a corresponding price $p_{k,t}$ once an inventory $\gamma_t$ occurs. Then we propose the price whose derivative estimate $\hat r_{k,t}\pm\Delta_k$ is closest-to-zero among all $k$. Finally, we update the estimates with observations.
Here we provide an intuition of the optimality: On the one hand, the width of the interval can tolerate the error of mapping from $2k\Delta$ to $p_{k,t}$, and the Lipschitzness of $F$ and $G$ ensures that our estimate within each small interval is roughly correct. On the other hand, we can show that the closest-to-zero derivative estimate implies a closest-to-$p_t^*$ price according to some locally strong convexity in the neighborhood of $p_t^*$. As we have smoothness on the regret function, we suffer a quadratic loss at $(T\cdot\frac1{T^{1/4}})^2=O(\sqrt{T})$ cumulatively, which balances the loss of STAGE 1 that costs $O(\tau)=O(\sqrt{T})$ as well. For a rigorous regret analysis, we kindly refer the readers to (ref).
{
\paragraph{Technical Highlights.}
This work is the first to introduce optimism on the derivatives and achieve optimal regret in an adversarial online learning problem. In contrast, existing works either develop optimistic algorithms on the reward (or loss) function as the original UCB strategy lai1985asymptotically, or instead use unbiased stochastic gradients and conduct first-order methods for online optimization hazan2019introduction.}
Regret Analysis
In this section, we analyze the cumulative regret of our algorithm and show a $\tilde{O}(\sqrt{T})$ regret guarantee with high probability. Here we only display key lemmas and proof sketches, and we leave all of the proof details to (ref).
We first state our main theorem.
theorem[Regret]
Let $\tau={\sqrt{T}}$ in (ref). For any adversarial $\{\gamma_t\}_{t=1}^T$ input sequence, C20CB suffers at most $\tilde{O}\left(\sqrt{T}\cdot\log\frac{T}{\delta}\right)$ regret, with probability $\Pr\geq 1-\delta$.
proofIn order to prove (ref), we have to show the following three components:
\begin{enumerate}
• The reward function $r_t(p)$ is unimodal. Also, $r_t(p)$ is smooth at $p_t^*$, and is strongly concave on a neighborhood of $p_t^*$.
• The estimation error of $a$ and $b$ are bounded by $O(\frac1{T^{1/4}})$ at the end of STAGE 1.
• The price whose derivative estimate has the closest-to-zero confidence bound is asymptotically close to $p_t^*$.
\end{enumerate}
In the following, we present each corresponding lemma regarding to the roadmap above.
\begin{lemma}[Revenue Function $r_t(p)$]
For the expected revenue function $r_t(p)$ defined in (ref), the following properties hold:
\begin{enumerate}
• We have
\begin{equation}
\begin{aligned}
r_t(p) & = p(\gamma_t-c+G(c)-G(\gamma_t-a+bp))\\
r'_t(p) & = \gamma_t-c+G(c)-G(\gamma_t-a+bp)-bp\cdot F(\gamma_t-a+bp).
\end{aligned}
\end{equation}
• There exists a constant $L_r>0$ such that $r'(p)$ is $L_r$-Lipschitz.
• $r'(p)$ is monotonically non-increasing.
• $r_t(p)$ is unimodal: There exists a unique $p_t^*\in[0, \frac{a}{b}]$ such that $r'_t(p_t^*)=0$, and $r_t(p)$ monotonically increase in $[0, p_t^*]$ and decrease in $[p_t^*, \frac{a}{b}]$. Notice that $\frac{a}{b} > p_{\max}$ according to (ref).
• $r_t(p)$ is smooth at $p_t^*$: There exists a constant $C_s >0$ such that $r_t(p_t^*)-r_t(p)\leq C_s(p_t^*-p)^2, \forall p\in[0, p_{\max}]$.
• $r_t(p)$ is locally strongly concave: There exist $\epsilon_t>0$ and $C_{\epsilon}>0$ such that $\forall p_1, p_2\in[p_t^*-\epsilon_t, p_t^*+\epsilon_t]$ we have $|r'_t(p_1)-r'_t(p_2)|\geq C_{\epsilon}\cdot|p_1-p_2|$.
• There exists a constant $C_v>0$ such that for any $t\in[T]$ and $p\in(p_t^*-\epsilon_t, p_t^*+\epsilon_t)$, we have $|r_t(p_t^*)-r_t(p)|\leq C_v\cdot(r'_t(p))^2$.
\end{enumerate}
\end{lemma}
\begin{proof}[sketch]
Property 1 is from integration by parts. Property 2 is proved by the Lipschitzness of $F(x)$. Property 3 is from the monotonicity of $F(x)$. Property 4 can be proved by two steps: (4.1) The existence of $p_t^*\in[0,\frac{a}{b}]$ by $r_t'(0)>0$ and $r_t'(\frac{a}{b})<0$; (4.2) The uniqueness of $p_t^*$ by contradiction. Properties 5 and 6 are mainly from the Lipschitzness of $r'_t(p)$. Property 7 comes from $r'_t(p_t^*) = 0$ and the strong concavity (Property 6). Please kindly check (ref) as a detailed proof of (ref). \qed
\end{proof}
The properties of $r_t(p)$ and $r'_t(p)$ enable us to upper bound the cost of estimation error and decision bias. In the following, we propose a lemma that serves as a milestone of estimation error upper bounds.
\begin{lemma}[Estimation Error of $a$ and $b$]
For any $\eta>0, \delta>0$, with probability $\Pr\geq 1-2\eta\delta$, we have
\begin{equation}
\begin{aligned}
|\hat b - b| \leq& C_b\cdot\frac1{\sqrt{\tau}}, \quad
|\hat a - a| \leq C_a\cdot\frac1{\sqrt\tau},
\end{aligned}
\end{equation}
where $C_a:=p_{\max}(C_b + b_{\max}\cdot\sqrt{\frac12\log\frac{2}{\eta\delta}})$ and $C_b:=\frac{8b_{\max}^2}{\gamma_{\min}-\gamma_0}\cdot\sqrt{\frac12\log\frac{2}{\eta\delta}}$.
\end{lemma}
\begin{proof}[sketch]
The key observation to prove this lemma lies in the expectation of each $e_{i,t}$ that indicates whether the demand exceeds certain level under uniformly distributed prices. According to Law of Total Expectation, for any $\gamma \in[\gamma_{\min}, \gamma_t]$ at any time $t\leq\tau$ in STAGE 1, we have
\begin{equation}
\begin{aligned}
\mathbb{E}[\mathds{1}[D_t\geq \gamma]]=&\mathbb{E}_{N_t}[\mathbb{E}_{p_t}[a-bp_t+N_t\geq \gamma|N_t]]\\
=&\mathbb{E}_{N_t}[\mathbb{E}_{p_t}[p_t\leq\frac{a-\gamma+N_t}{b}|N_t]]\\
=&\mathbb{E}_{N_t}[\frac{a-\gamma+N_t}{b\cdot p_{\max}}]=\frac{a-\gamma}{bp_{\max}}.
\end{aligned}
\end{equation}
With this property, we may construct method-of-moment estimates from $e_{i,t}$ in STAGE 1, which eliminate the influence of noise distribution and achieve an unbiased estimator of $\frac1b$ (and therefore $\hat b$ asymptotically).
With $\hat b$ serving as a plug-in estimator, we later achieve $\hat a$. We obtain the error bounds by applying Hoeffding's Inequalities. \qed
\end{proof}
We defer the detailed proof of (ref) to (ref). With the help of (ref), we may upper bound the estimation error of $r'_t(p)$ at discrete prices. The error bound is displayed as the following lemma.
\begin{lemma}[Estimation Error of $r'_t(p_{k, t})$]
There exists constants $C_N>0, C_{\tau}>0$ such that for any $t\in[T], k\in\{-M, -M+1, \ldots, M\}$, with probability $\Pr\geq 1-6\eta\delta$ we have
\begin{equation}
|r'_t(p_{k,t})-\hat r_{k,t}|\leq C_N\cdot\frac1{\sqrt{N_k(t)}} + C_\tau\cdot\frac1{\sqrt{\tau}} = \Delta_k(t).
\end{equation}
Here $N_k(t)$ and $\Delta_k(t)$ denotes the value of $N_k\text{ and }\Delta_k$ at the beginning of time period $t$.
\end{lemma}
\begin{proof}[sketch]
Denote $N_k(t), F_k(t)$ and $G_k(t)$ as the value of $N_k, F_k$ and $G_k$ at the beginning of time $t$. From Algorithm 1, we have $|\hat r_{k,t} - r'_t(p_{k,t})|\leq|G_k(t)-(G(c)-G(\gamma_t-a+bp_{k,t}))|+p_{k,t}|\hat bF_k-bF(\gamma_t-a+bp_{k,t})|$, and we may separately upper bound each of these two differences.
\begin{enumerate}
• For the term on $G$, we may split the quantity $|G_k(t)-(G(c)-G(\gamma_t-a+bp_{k,t}))|$ into three terms:
\begin{enumerate}[label=(\roman*)]
• $|G_k(t) - \mathbb{E}[G_k(t)]|$ as concentration, which is bounded by Hoeffding's inequality.
• $|\mathbb{E}[G_k(t)] - (G(c) - G(2k\Delta))|$ as the $G_k$ deviation within each “bin” of estimation (whose center is $w_k = 2k\Delta$). By definition of $G_k(t)$, we have $\mathbb{E}[G_k(t)] = \frac1{N_k(t)}\sum_{s=1}^{t-1}\mathds{1}[k_s==k](G(c) - G(\gamma_s-a+bp_{k_s,s}))$, and therefore we have
\begin{equation}
\begin{aligned}
&|\mathbb{E}[G_k(t)] - (G(c) - G(2k\Delta))|\\
\leq&\frac1{N_k(t)}\sum_{s<t: k_s==k}|G(\gamma_s-a+bp_{k_s,s})-G(2k\Delta)|\\
\leq& O(|\hat{a}-a| + |\hat b - b|).
\end{aligned}
\end{equation}
The last line is by Lipschitzness of $G(x)$.
• $|G(2k\Delta) - G(\gamma_t - a + bp_{k,t})|$, which is similar to the last step of (ii) above.
\end{enumerate}
• For the term on $F$, we may split the quantity $|\hat bF_k-bF(\gamma_t-a+bp_{k,t})|$ into four terms:
\begin{enumerate}[label=(\roman*)]
• $|\hat b F_k(t) - b F_k(t)|\leq |\hat b - b|$ by the nature of $F_k(t)\leq 1$, and further bounded by (ref).
• $|F_k(t) - \mathbb{E}[F_k(t)]|$, (iii) $|\mathbb{E}[F_k(t)] - F(2k\Delta)|$, and (iv) $|F(2k\Delta) - F(\gamma_t - a + bp_{k,t})|$, are bounded in the same way presented above for $G$ respectively.
\end{enumerate}
By plugging in the estimation error from (ref), we prove the present lemma. \qed
\end{enumerate}
\end{proof}
Please refer to (ref) as a rigorous proof of (ref). Given this lemma, the derivatives of each discrete price $p_{k,t}$ is truthfully reflected by their corresponding error bound. Therefore, we intuitively see that the closest-to-zero confidence bound represents the closest-to-$p_t^*$ discrete price. We formulate this intuition as the following lemma:
\begin{lemma}[Closest-To-Zero Confidence To Performance]
Denote $\Delta_k(t)$ as the value of $\Delta_k$ at the beginning of period $t$. There exists two constants $N_0>0, N_1>0$ such that for any $t=1,2,\ldots, T$ in STAGE 2, either of the following events occurs with high probability.
\begin{enumerate}
• When $\exists k\in\{-M, -M+1, \ldots, M\}$ such that the Number $k$ confidence bound satisfies $\hat{r}_{k,t}-\Delta_k(t)\leq 0 \leq \hat{r}_{k,t}+\Delta_k(t)$, and also $N_k(t)>N_0$, then we have $p_{k, t}\in[p_t^*-\epsilon_t, p_t^*+\epsilon_t]$. Furthermore, there exists constant $C_{in}$ such that $r_t(p_t^*)-r_t(p_{k,t})\leq C_{in}(\frac1{N_k(t)} + \frac1{\tau})$.
• When there exists no confidence bound that contains $0$, i.e. either $\hat{r}_{k,t}-\Delta_k(t)>0$ or $\hat{r}_{k,t}+\Delta_k(t)<0, \forall k\in\{-M, -M+1, \ldots, M-1, M\}$ (happens at least for one $k$), and also $N_k(t)>N_1$, then we have
\begin{equation}
\inf_{k}\min\{|\hat{r}_{k,t}-\Delta_k(t)|, |\hat{r}_{k,t}+\Delta_k(t)|\}\leq C_{\kappa}\cdot\frac1{\sqrt{\tau}},
\end{equation}
(where $C_{\kappa}=\frac{L_r(C_a + C_b\cdot p_{\max})}{2b_{\min}}$) and $p_{k, t}\in[p_t^*-\epsilon_t, p_t^*+\epsilon_t]$. Furthermore, there exists constant $C_{out}$ such that $r_t(p_t^*)-r_t(p_{k,t})\leq C_{out}(\frac1{N_k(t)} + \frac1{\tau})$.
\end{enumerate}
\end{lemma}
\begin{proof}[sketch]
The intuition to prove (ref) is twofold:
\begin{enumerate}
• When an error bar contains $0$, the true derivative of the corresponding price is close to $0$ within the distance of its error bound. By applying (ref) Property (7), we may upper bound the performance loss with the square of its derivatives, which is further upper bounded by the square of error bound.
• When no error bar contains $0$, there exists an adjacent pair of prices whose error bars are separated by $y=0$. On the one hand, their derivatives difference is upper bounded due to the Lipschitzness of $r'_t(p)$. On the other hand, the same derivatives difference is lower bounded by the closest-to-zero confidence bound. Therefore, the gap between $y=0$ and the closest-to-zero confidence bound should be very small, and we still have a comparably small $|r'_t(p_t)|$ if $p_t$ possesses that confidence bound. As a consequence, we have similar upper bound on the performance loss comparing with Case (1), up to constant coefficients. \qed
\end{enumerate}
\end{proof}
The detailed proof of (ref) is presented in (ref). Finally, we have a lemma that upper bounds the regret of proposing $p_t=\frac{\hat a}{2\hat b}$ under special conditions.
\begin{lemma}[Proposing $\frac{\hat a}{2\hat b}$]
When $\gamma_t>\frac{\hat a + C_a\cdot\frac1{\sqrt{\tau}}}2+c$ and when $\hat r_{k,t}-\Delta_k(t)>0, \forall k=-M, -M+1,\ldots, M$, we have $p_t^*=\frac{a}{2b}$ and there exists a constant $C_{non}$ such that
\begin{equation}
\begin{aligned}
r_t(\frac{a}{2b})-r_t(\frac{\hat a}{2\hat b}) \leq C_{non}\frac1{\tau}.
\end{aligned}
\end{equation}
\end{lemma}
The intuition of (ref) is that $\frac{a}{2b}$ is the optimal price without censoring, and we only need to show that either the optimal price or $\frac{a}{2b}$ is not censored (which are equivalent as the revenue function is unimodal). We defer its proof to (ref). This lemma serves as the last puzzle of the proof. With all lemmas above, we upper bound the overall regret as follows:
\begin{equation}
\begin{aligned}
Regret=\sum_{t=1}^T r_t(p_t^*) - r_t(p)
&\leq \tau\cdot a_{\max} p_{\max} + (2M+1)(1+N_0+N_1)\cdot a_{\max} p_{\max}\\
&\quad + \sum_{t=1}^T (\max\{C_{in}, C_{out}\})(\frac1{N_{k_t}(t)} + \frac1{\tau}) +\sum_{t=1}^T C_{non}\cdot\frac1{\tau}\\
( let \tau=\sqrt{T})\rightarrow\quad&=\tilde{O}(\sqrt{T} + T^{\frac14} + \sum_{t=1}^T\frac1{N_{k_t}(t)} + \frac{T}{\tau})\\
&=\tilde{O}(\sqrt{T} + \sum_{k=1}^{2M+1}\sum_{i_k=1}^{N_{k_t}(T)}\frac1{i_k})\\
&=\tilde{O}(\sqrt{T} + T^{\frac14}\log T) = \tilde{O}(\sqrt{T}).\\
\end{aligned}
\end{equation}
Here the first two rows are a decomposition of STAGE 1 (for $\tau$ rounds), STAGE 2 Initialization (for $2M+1$ rounds), STAGE 2 Case (a) and (b) (proposing $p_t=p_{k_t}$, (ref)) and STAGE 2 Case (c) (proposing $p_t = \frac{\hat a}{2\hat b}$, (ref)). The fourth row is by re-classification of $\frac1{N_{k_t}(t)}$ according to $k$, which leads to a summation over harmonic series (since each $N_{k_t}(t)$ increases by 1 for the same class $k_t=k$). By applying a union bound, (ref) holds with probability $$\Pr\geq 1-2\eta\delta - 6\eta\delta\cdot T(2M+1) \geq 1- 20\frac{c}{2(C_a+C_b\cdot p_{\max})}T^{5/4}\cdot \eta\delta.$$
Here the first part comes from (ref), and the second part comes from (ref) for any $t\in[T]$ and $k\in\{-M, \ldots, M\}$. Let $\eta:=\frac{C_a + C_b\cdot p_{\max}}{10c\cdot T^{5/4}}$, and we show that (ref) holds. \qed
remarkThis $\tilde{O}(\sqrt{T})$ regret upper bound is near-optimal up to $\log{T}$ factors, as it matches the $\Omega(\sqrt{T})$ information-theoretic lower bound proposed by broder2012dynamic for a no-censoring problem setting with linear noisy demand.
Discussions
Here we provide some insights on the current limitations and potential extension of this work to a broader field of research.
\paragraph{Extensions to Non-linear Demand Curve.}
In this work, we adopt a linear-and-noisy model for the potential demands, which is standard in dynamic pricing literature. Also, we utilize the unimodal property brought by this linear demand model, even after the censoring effect is imposed. If we generalize our methodologies to nonlinear demand functions, we have to carefully distinguish between potential local optima and saddle points that may also cause $r'_t(p)=0$ for some sub-optimal $p$. We conjecture an $\Omega(T^{\frac{m+1}{2m+1}})$ lower bound in that case, where $m$ is the order of smoothness. It is worth investigating whether the censoring effect will introduce new local optimals or swipe off existing ones in multimodal settings.
\paragraph{Generalization to Unbounded Noises.}
We assume the noise is bounded in a constant-width range. From the analysis in (ref), we know that the threshold of learning the optimal price in our problem setting is still the estimation of parameters. Therefore, this boundedness assumption streamlines the pure-exploration phase, facilitates the estimation of the parameters $b$ and $a$, and scales down the cumulative regret. While our methods and results can be extended to unbounded $O(\frac1{\log T})$-subGaussian noises by simple truncation, challenges remain for handling generic unbounded noises. Moreover, the problem can be more sophisticated with dual-censoring, both from above by inventory--as we have discussed-- and from below by $0$, especially when considering unbounded noises.
\paragraph{Extensions to Non-Lipschitz Noise CDF.} In this work, we assume the noise CDF as a Lipschitz function as many pricing-related works did fan2021policy, tullii2024improved. This assumption enables the local smoothness at $p_t^*$ and leads to a quadratic loss. However, this prevents us from applying our algorithm to non-Lipschitz settings, which even includes the noise-free setting. In fact, although we believe that a better regret rate exists for the noise-free setting, we have to state that the hardness of the problem is completely different with Lipschitz noises versus without it. Although a Lipschitz noise makes the observation “more blur”, it also makes the revenue curve “more smooth”. We would like to present an analog example from the feature-based dynamic pricing problem: When the Gaussian noise $\mathcal{N}(0, \sigma^2)$ is either negligible (with $\sigma<\frac1T$, see cohen2020feature_journal) or super significant (with $\sigma>1$, see xu2021logarithmic), the minimax regret is $O(\log T)$. However, existing works can only achieve $O(\sqrt{T})$ regret when $\sigma\in[\frac1T, 1]$. We look forward to future research on our problem setting once getting rid of the Lipschitzness assumption.
\paragraph{Extensions to Contextual Pricing.}
In this work, we assume $a$ and $b$ are static, which may not hold in many real scenarios. (ref) serves as a good instance, showcasing significant fluctuations in popularity across different performances. A reasonable extension of our work would be modeling $a$ and $b$ as contextual parameters. Similar modelings have been adopt by wang2021dynamic and ban2021personalized in the realm of personalized pricing research.
\paragraph{Societal Impacts.}
Our research primarily addresses a non-contextual pricing model that does not incorporate personal or group-specific data, thereby adhering to conventional fairness standards relating to temporal, group, demand and utility discrepancies as outlined by cohen2022price and chen2023utility. However, the non-stationarity of inventory levels could result in varying fulfillment rate over time, i.e. the proportions of satisfied demands at $\{p_t^*\}$'s might be different for $t=1,2,\ldots, T$. This raises concern regarding unfairness in fulfillment rate spiliotopoulou2022fairness, particularly for products of significant social and individual importance.
Conclusions
In this paper, we studied the online pricing problem with adversarial inventory constraints imposed over time series. We introduced an optimistic strategy and a C20CB algorithm that is capable of approaching the optimal prices from inventory-censored demands. Our algorithm achieves a regret guarantee of $\tilde{O}(\sqrt{T})$ with high probability, which is information-theoretically optimal. To the best of our knowledge, we are the first to address this adversarial-inventory pricing problem, and our results indicate that the demand-censoring effect does not substantially increase the hardness of pricing in terms of minimax regret.
Acknowledgement
Jianyu Xu started this work as a Ph.D. student at University of California, Santa Barbara. Xi Chen would like to thank the support from NSF via the Grant IIS-1845444.