The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
48,899 characters
Logarithmic Regret in Feature-based Dynamic Pricing
\maketitle
\begin{abstract}
Feature-based dynamic pricing is an increasingly popular model of setting prices for highly differentiated products with applications in digital marketing, online sales, real estate and so on. The problem was formally studied as an online learning problem \citep{javanmard2019dynamic} where a seller needs to propose prices \emph{on the fly} for a sequence of $T$ products based on their features $x$ while having a small \emph{regret} relative to the best ---``omniscient’’--- pricing strategy she could have come up with in hindsight. We revisit this problem and provide two algorithms (EMLP and ONSP) for stochastic and adversarial feature settings, respectively, and prove the optimal $O(d\log{T})$ regret bounds for both. In comparison, the best existing results are $O\left(\min\left\{\frac{1}{\lambda_{\min}^2}\log{T}, \sqrt{T}\right\}\right)$ and $O(T^{2/3})$ respectively, with $\lambda_{\min}$ being the smallest eigenvalue of $\mathbb{E}[xx^T]$ that could be arbitrarily close to $0$. We also prove an $\Omega(\sqrt{T})$ information-theoretic lower bound for a slightly more general setting, which demonstrates that ``knowing-the-demand-curve'' leads to an exponential improvement in feature-based dynamic pricing.
\bigskip
{\textbf{Keywords}: dynamic pricing, online learning, adversarial features, optimal regret, affine invariant, distribution-free.}
\end{abstract}
\newpage
\tableofcontents
\newpage
\section{Introduction}
\label{sec_introduction}
The problem of pricing — to find a high-and-acceptable price — has been studied since \citet{cournot1897researches}. In order to locate the optimal price that maximizes the revenue, a firm may adjust their prices of products frequently, which inspires the \emph{dynamic pricing} problem. Existing works \citep{kleinberg2003value,broder2012dynamic, chen2013simple, besbes2015surprising} primarily focus on pricing a single product, which usually will not work well in another setting when thousands of new products are being listed every day with no prior experience in selling them. Therefore, we seek methods that approach an acceptable-and-profitable price with only observations on this single product and some historical selling records of other products.
In this work, we consider a ``feature-based dynamic pricing'' problem, which was studied by \citet{amin2014repeated, cohen2020feature_journal, javanmard2019dynamic}. In this problem setting, a sales session (product, customer and other environmental variables) is described by a feature vector, and the customer's \emph{expected} valuation is modeled as a linear function of this feature vector.
\fbox{\parbox{0.97\textwidth}{Feature-based dynamic pricing. For $t=1,2,...,T:$
\small
\noindent
\begin{enumerate}[leftmargin=*,align=left]
\setlength{\itemsep}{0pt}
\item A feature vector $x_t\in\mathbb{R}^{d}$ is revealed that describes a sales session (product, customer and context).
\item The customer valuates the product as $w_t = x_t^{\top}\theta^{*} + N_t$.
\item The seller proposes a price $v_t>0$ concurrently (according to $x_t$ and historical sales records).
\item The transaction is successful if $v_t \leq w_t$, i.e., the seller gets a reward (payment) of $r_t=v_t\cdot\mathbbm{1}(v_t\leq w_t)$.
\end{enumerate}
}
}
Here $T$ is unknown to the seller (and thus can go to infinity), $x_t$'s can be either stochastic (e.g., each sales session is drawn i.i.d.) or adversarial (e.g., the sessions arrive in a strategic sequence), $\theta^{*}\in\mathbb{R}^{d}$ is a fixed parameter for all time periods, $N_t$ is a zero-mean noise, and $\mathbbm{1}_t=\mathbbm{1}(v_t\leq w_t)$ is an indicator that equals $1$ if $v_t\leq w_t$ and $0$ otherwise. In this online-fashioned setting, we only see and sell one product at each time. Also, the feedback is \emph{Boolean Censored}, which means we can only observe $\mathbbm{1}_t$ instead of knowing $w_t$ directly. The best pricing policy for this problem is the one that maximizes the \emph{expected} reward, and the \emph{regret} of a pricing policy is accordingly defined as the difference of expected rewards between this selected policy and the best policy.
\ifbool{compact}{\noindent\textbf{Summary of Results.}}{\paragraph{Summary of Results.}} Our contributions are threefold.
\begin{enumerate}
\item When $x_t$'s are independently and identically distributed (i.i.d.) from an unknown distribution, we propose an ``Epoch-based Max-Likelihood Pricing (EMLP)'' algorithm that guarantees a regret bound at $O(d\log{T})$. The design of EMLP is similar to that of the RMLP algorithm in \citet{javanmard2019dynamic}, but our new analysis improves their regret bound at $O(\sqrt{T})$ when $\mathbb{E}[xx^{\top}]$ is near singular.
\item When $x_t$'s are adversarial, we propose an ``Online-Newton-Step Pricing (ONSP)'' algorithm that achieves $O(d\log{T})$ regret on constant-level noises for the first time, which exponentially improves the best existing result of $O(T^{2/3})$ \citep{cohen2020feature_journal}.\footnote{Previous works \citep{cohen2020feature_journal, krishnamurthy2020contextual} did achieve polylog regrets, but only for negligible noise with $\sigma=O(\frac{1}{T\log{T}})$.}
\item
Our methods that achieve logarithmic regret require knowing the exact distribution of $N_t$ in advance, as is also assumed in \citet{javanmard2019dynamic}.
We prove an $\Omega(\sqrt{T})$ lower bound on the regret if $N_t\sim\mathcal{N}(0,\sigma^2)$ where $\sigma$ is \emph{unknown}, even with $\theta^*$ given and $x_t$ fixed for all $t$.
\end{enumerate}
The $O(\log{T})$ regret of EMLP and ONSP meets the information-theoretical lower bound \citep[Theorem 5,][]{javanmard2019dynamic}. In fact, the bound is optimal even when $w_t$ is revealed to the learner \citep{mourtada2019exact}. From the perspective of characterizing the hardness of dynamic pricing problems, we generalize the classical results on ``The Value of Knowing a Demand Curve'' \citep{kleinberg2003value} by further dividing the random-valuation class with an exponential separation of: (1) $O(\log{T})$ regret for knowing the \emph{demand curve} exactly (even with adversarial features), and (2) $\Omega(\sqrt{T})$ regret for
\emph{almost} knowing the \emph{demand curves} (up to a one-parameter parametric family).
\section{Related Works}
\vspace{-0.5em}
\label{sec_related_works}
In this section, we discuss our results relative to existing works on feature-based dynamic pricing, and highlight the connections and differences to the related settings of contextual bandits and contextual search (for a broader discussion, see Appendix~\ref{appendix_other_related_works}).
\ifbool{compact}{\noindent\textbf{Feature-based Dynamic Pricing.}}{\paragraph{Feature-based Dynamic Pricing.}}
There is a growing body of work on dynamic pricing with linear features \citep{amin2014repeated,qiang2016dynamic,cohen2020feature_journal,javanmard2019dynamic}. Table \ref{table_related_works_and_regret_bounds} summarizes the differences in the settings and results\footnote{We only concern the dependence on $T$ since there are various different assumptions on $d$.}.
\begin{table*}[t]
\centering
\caption{Related Works and Regret Bounds w.r.t. $T$}
\label{table_related_works_and_regret_bounds}
\resizebox{\textwidth}{!}{
\begin{tabular}{|c|c|c|c|p{2.5in}|c|}
\hline
Algorithm & Work & Regret (upper) bound & Feature & Noise \\ \hline
LEAP & \citep{amin2014repeated} & $\tilde{O}(T^{\frac{2}{3}})$ & i.i.d. & Noise-free \\ \hline
EllipsoidPricing & \citep{cohen2020feature_journal} & $O(\log{T})$ & adversarial & Noise-free \\ \hline
EllipsoidEXP4 & \citep{cohen2020feature_journal} & $\tilde{O}(T^{\frac{2}{3}})$ & adversarial & Sub-Gaussian \\ \hline
PricingSearch & \citep{leme2018contextual} & $O(\log\log(T))$ & adversarial & Noise-free \\ \hline
\multirow{2}{*}{RMLP} & \multicolumn{1}{c|}{\multirow{2}{*}{ \citep{javanmard2019dynamic}}} & $O(\log{T}/C_{\min}^2)$$^\dagger$ & \multirow{2}{*}{i.i.d.} & \multirow{2}{*}{\begin{tabular}[c]{@{}l@{}}Log-concave, distribution-known\end{tabular}} \\ \cline{3-3} \cline{6-6}
& \multicolumn{1}{c|}{} & $O(\sqrt{T})$ & & \\ \hline
RMLP-2 & \citep{javanmard2019dynamic} & $O(\sqrt{T})$ & i.i.d. & Known parametric family of log-concave. \\ \hline
ShallowPricing & \citep{cohen2020feature_journal} & \multirow{2}{*}{$O(poly(\log{T}))$} & \multirow{2}{*}{adversarial} & \multirow{2}{*}{Sub-Gaussian, known $\sigma=O(\frac{1}{T\log{T}})$} \\ \cline{1-2}
CorPV & \citep{krishnamurthy2020contextual} & & & \\ \hline
Algorithm 2 (MSPP) & \citep{liu2021optimal} & $O(\log\log(T))$ & adversarial & Noise-free \\ \hline
\textbf{EMLP} & This paper & $O(\log T)$ & i.i.d. & Strictly log-concave, distribution-known \\ \hline
\textbf{ONSP} & This paper & $O(\log{T})$ & adversarial & Strictly log-concave, distribution-known \\ \hline
\end{tabular}}
\footnotesize{$^\dagger$ $C_{\min}$ is the restricted eigenvalue condition. It reduces to the smallest eigenvalue of $\mathbb{E}[xx^{\top}]$ in the low-dimensional case we consider.}\\
\end{table*}
Among these work, our paper directly builds upon \citep{cohen2020feature_journal} and \citep{javanmard2019dynamic}, as we share the same setting of online feature vectors, linear and noisy valuations and Boolean-censored feedback. Relative to the results in \citep{javanmard2019dynamic}, we obtain $O(d\log T)$ regret under weaker assumptions on the sequence of input features --- in both distribution-free stochastic feature setting and the adversarial feature setting.
It is to be noted that \citep{javanmard2019dynamic} also covers the sparse high-dimensional setting, and handles a slightly broader class of demand curves. Relative to \citep{cohen2020feature_journal}, in which the adversarial feature-based dynamic pricing was first studied,
our algorithm ONSP enjoys the optimal $O(d\log T)$ regret when the noise-level is a constant. In comparison, \citet{cohen2020feature_journal} reduces the problem to contextual bandits and applies the (computationally inefficient) ``EXP-4'' algorithm \citep{auer2002nonstochastic} to achieve a $\tilde{O}(T^{2/3})$ regret. The ``bisection'' style-algorithm in both \citet{cohen2020feature_journal} and \citet{krishnamurthy2020contextual} could achieve $\tilde{O}(poly(d) poly\log(T))$ regrets but requires a small-variance subgaussian noise satisfying $\sigma = O(\frac{1}{T\log{T}})$.
\ifbool{compact}{\noindent\textbf{Lower Bounds.}}{\paragraph{Lower Bounds.}} Most existing works focus on the lower regret bounds of non-feature-based models. \citet{kleinberg2003value} divides the problem setting as fixed, random, and adversarial valuations, and then proves each a $\Theta(\log\log{T})$, $\Theta(\sqrt{T})$, and $\Theta(T^{2/3})$ regret, respectively. \citet{broder2012dynamic} further proves a $\Theta(\sqrt{T})$ regret in general parametric valuation models. In this work, we generalize the methods of \citet{broder2012dynamic} to our feature-based setting and further narrow it down to a linear-feature Gaussian-noisy model. As a complement to \citet{kleinberg2003value}, we further separate the exponential regret gap between: (1) $O(\log{T})$ of the hardest (adversarial feature) totally-parametric model, and (2) $\Omega(\sqrt{T})$ of the simplest (fixed known expectation) unknown-$\sigma$ Gaussian model.
\ifbool{compact}{\noindent\textbf{Contextual Bandits.}}{\paragraph{Contextual Bandits.}}
For readers familiar with the online learning literature, our problem can be reduced to a contextual bandits problem \citep{langford2007epoch,agarwal2014taming} by discretizing the prices. But this reduction only results in $O(T^{2/3})$ regret, as it does not capture the special structure of the feedback: \emph{an accepted price indicates the acceptance of all lower prices}, and vise versa. Moreover, when comparing to linear bandits \citep{chu2011contextual}, it is the valuation instead of the expected reward that we assume to be linear.
\ifbool{compact}{\noindent\textbf{Contextual Search.}}{\paragraph{Contextual Search.}}
Feature-based dynamic pricing is also related to the contextual search problem \citep{lobel2018multidimensional, leme2018contextual, liu2021optimal, krishnamurthy2020contextual}, which often involves learning from Boolean feedbacks, sometimes with a ``pricing loss'' and ``noisy'' feedback. These shared jargons make this problem \emph{appearing} very similar to our problem. However, except for the noiseless cases \citep{lobel2018multidimensional, leme2018contextual}, contextual search algorithms, even with ``pricing losses'' and ``Noisy Boolean feedback'' \citep[e.g.,][]{liu2021optimal}, do \emph{not} imply meaningful regret bounds in our problem setup due to several subtle but important differences in the problem settings. Specifically, the noisy-boolean feedback model of \citep{liu2021optimal} is about randomly toggling the ``purchase decision'' determined by the \emph{noiseless} valuation $x^{\top}\theta^*$ with probability $0.5-\epsilon$. This is incompatible to our problem setting where the purchasing decision is determined by a noisy valuation $x^{\top}\theta^* + \text{Noise}$.
Ultimately, in the setting of \citep{liu2021optimal}, the optimal policy alway plays $x^{\top}\theta^*$, but our problem is harder in that we need to exploit the noise and the optimal price could be very different from $x^{\top}\theta^*$. \footnote{As an explicit example, suppose the valuation $x^{\top}\theta^*=0$, then the optimal price must be $>0$ in order to avoid zero return. }
\citet{krishnamurthy2020contextual} also discussed this issue explicitly and considered the more natural noisy Boolean feedback model studied in this paper. Their result, similar to \citet{cohen2020feature_journal}, only achieves a logarithmic regret when the noise on the valuation is vanishing in an $\tilde{O}(1/T)$ rate.
\section{Problem Setup}
\label{sec_preliminary}
\ifbool{compact}{\noindent\textbf{Symbols and Notations.}}{\paragraph{Symbols and Notations.}}
Now we introduce the mathematical symbols and notations involved in the following pages. The game consists of $T$ rounds.
$x_{t}\in \mathbb{R}^d$, $v_{t}\in \mathbb{R}_+$ and $N_{t}\in\mathbb{R}$ denote the feature vector, the proposed price and the noise respectively at round $t=1,2,...,T$.\footnote{In an epoch-design situation, a subscript $(k,t)$ indicates round $t$ of epoch $k$.} We denote the product $u_t:=x_t^{\top}\theta^{*}$ as an \emph{expected valuation}. At each round, we receive a payoff (reward) $r_{t}=v_t\cdot\mathbbm{1}_t$, where the binary variable $\mathbbm{1}_{t}$ indicates whether the price is accepted or not, i.e., $\mathbbm{1}_{t}=\mathbf{1}(v_t\leq w_t)$. As we may estimate $\theta^{*}$ in our algorithms, we denote $\hat{\theta}_t$ as an estimator of $\theta^{*}$, which we will formally define in the algorithms.
Furthermore, we denote some functions that are related to noise distribution: $F(\omega)$ and $f(\omega)$ denote the cumulative distribution function (CDF) and probability density function (PDF) sequentially. We know that $F'(\omega)=f(\omega)$ if we assume differentiability.
To concisely denote all data observed up to round $\tau$ (i.e., feature, price and payoff of all past rounds), we define $hist(\tau)=\{(x_{t}, v_{t}, \mathbbm{1}_{t}) \text{ for }t=1,2,...,\tau\}$. $hist(\tau)$ represents the \emph{transcript} of all observed random variables before round $(\tau+1)$.
We define
\begin{equation}
l_{t}(\theta):=-\mathbbm{1}_t\cdot\log\big(1-F(v_t-x_t^{\top}\theta)\big)-(1-\mathbbm{1}_t)\log\big(F(v_t-x_t^{\top}\theta)\big)
\label{equation_log_likelihood_function}
\end{equation}
as a negative log-likelihood function at round $t$. Also, we define an expected log-likelihood function $L_t(\theta)$:
\begin{equation}
L_t(\theta):=\mathbb{E}_{N_t}[l_t(\theta)|x_t]
\label{equation_expected_log_likelihood}
\end{equation}
Notice that we will later define an $\hat{L}_{k}(\theta)$ which is, however, not an expectation.
\ifbool{compact}{\noindent\textbf{Definitions of Key Quantities.}}{\paragraph{Definitions of Key Quantities.}}
We firstly define an \emph{expected reward} function $g(v,u)$.
\ifbool{twocol}{
\begin{equation}
\begin{aligned}
g(v, u):=&\mathbb{E}[r_t|v_t=v, x_t^{\top}\theta^{*}=u]\\
=&v\cdot P[v\leq x_t^{\top}\theta^{*}+N_t]\\
=&v\cdot(1-F(v-u)).
\end{aligned}
\label{equ_def_gvu}
\end{equation}
}{
\begin{equation}
g(v, u):=\mathbb{E}[r_t|v_t=v, x_t^{\top}\theta^{*}=u]=v\cdot P[v\leq x_t^{\top}\theta^{*}+N_t]=v\cdot(1-F(v-u)).
\label{equ_def_gvu}
\end{equation}
}
This indicates that if the expected valuation is $u$ and the proposed price is $v$, then the (conditionally) expected reward is $g(v,u)$. Now we formally define the \emph{regret} of a policy (algorithm) $\mathcal{A}$ as is promised in Section \ref{sec_introduction}.
\begin{definition}[Regret]
Let $\mathcal{A}: \mathbb{R}^{d}\times\left(\mathbb{R}^{d},\mathbb{R},\{0,1\}\right)^{t-1}\rightarrow\mathbb{R}$ be a policy of pricing, i.e. $\mathcal{A}(x_t, hist(t-1)) = v_t$. The regret of $\mathcal{A}$ is defined as follows.
{\small
\begin{equation}
\begin{aligned}
Reg_{\mathcal{A}}
=&\sum_{t=1}^{T}\max_{v}g(v,x_t^{\top}\theta^{*})-g(\mathcal{A}(x_t,hist(t-1)), x_t^{\top}\theta^{*}).
\end{aligned}
\label{Reg_A}
\end{equation}
}
Here $hist(t-1)$ is the historical records until $(t-1)^{\text{th}}$ round.
\end{definition}
\ifbool{compact}{\noindent\textbf{Summary of Assumptions.}}{\paragraph{Summary of Assumptions.}}
We specify the problem settings by proposing three assumptions.
\begin{assumption}[Known, bounded, strictly log-concave distribution]
The noise $N_t$ is independently and identically sampled from a distribution whose CDF is $F$. Assume that $F\in \mathbb{C}^{2}$ is strictly increasing and that $F$ and $(1-F)$ are strictly log-concave. Also assume that $f$ and $f'$ are bounded, and denote $B_f:=\sup_{\omega\in\mathbb{R}}{f(\omega)}, B_{f'}:=\sup_{\omega\in\mathbb{R}}|f'(\omega)|$ as two constants.
\label{assumption_strictly_log_concave}
\end{assumption}
\begin{assumption}[Bounded convex parameter space]\label{assumption_convex_feature_and_parameter_set}
The true parameter $\theta^{*}\in\mathbb{H}$, where $\mathbb{H}\subseteq\{\theta: ||\theta||_2\leq B_1\}$ is a bounded convex set and $B_1$ is a constant. Assume $\mathbb{H}$ is known to us (but $\theta^*$ is not).
\end{assumption}
\begin{assumption}[Bounded feature space]
\label{assumption_bounded_x_set}
Assume $x_t\in D\subseteq\{x: ||x||_2\leq B_2\}$, $\forall t=1,2,\ldots, T$. Also, $0\leq x^{\top}\theta\leq B, \forall x\in D, \forall\theta\in\mathbb{H}$, where $B=B_1\cdot B_2$ is a constant.
\end{assumption}
Assumption \ref{assumption_convex_feature_and_parameter_set} and \ref{assumption_bounded_x_set} are mild as we can choose $B_1$ and $B_2$ large enough. In Section \ref{subsec_alg_random}, we may add further complement to Assumption \ref{assumption_bounded_x_set} to form a stochastic setting. Assumption \ref{assumption_strictly_log_concave} is stronger since we might not know the exact CDF in practice, but it is still acceptable from an information-theoretic perspective. There are at least three reasons that lead to this assumption: Primarily, this is necessary if we hope to achieve an $O(\log(T))$ regret. We will prove in Section \ref{sec_lower} that an $\Omega(\sqrt{T})$ is unavoidable if we cannot know one parameter exactly. Moreover, the pioneering work of \citet{javanmard2019dynamic} also assumes a known noise distribution with log-concave CDF, and many common distributions are actually strictly log-concave, such as Gaussian and logistic.\footnote{In fact, $F$ and $(1-F)$ are both log-concave if its PDF is log-concave, according to Prekopa's Inequality.} Besides, although we did not present a method to precisely estimate $\sigma$ in this work, it is a reasonable algorithm to replace with a plug-in estimator estimated using historical offline data. As we have shown, not knowing $\sigma$ requires $O(\sqrt{T})$ regret in general, but the lower bound does not rule out the plug-in approach achieving a smaller regret for interesting subclasses of problems in practice.
Finally, we state a lemma and define an argmax function helpful for our algorithm design.
\begin{lemma}[Uniqueness]\label{g_unimodal}
For any $u\geq0$, there exists a unique $v^{*}\geq0$ such that $g(v^{*},u)=\max_{v\in\mathbb{R}}{g}(v,u)$. Thus, we can define a \emph{greedily pricing} function that maximizes the expected reward:
\begin{equation}
J(u):=\mathop{\arg\max}_{v}g(v,u)
\label{def_J}
\end{equation}
\end{lemma}
\vspace{-1em}
Please see the proof of Lemma \ref{g_unimodal} in Appendix \ref{appendix_subsec_proof_lemma_g_unimodal}.
\section{Algorithms}
\label{sec_algorithm}
\vspace{-0.5em}
In this section, we propose two dynamic pricing algorithms: EMLP and ONSP, for stochastic and adversarial features respectively.
\begin{figure}[t]
\begin{minipage}{0.48\textwidth}
\begin{algorithm}[H]
\caption{Epoch-based max-likelihood pricing (EMLP)}
\label{algo_MLP}
\begin{algorithmic}
\STATE {\bfseries Input:} {Convex and bounded set $\mathbb{H}$}
\STATE Observe $x_1$, randomly choose $v_1$ and get $r_1$.
\STATE Solve $\hat{\theta}_1=\arg\min_{\theta\in\mathbb{H}}l_1(\theta)$;
\FOR{$k=1$ {\bfseries to} $\lfloor\log_2{T}\rfloor+1$}
\STATE Set $\tau_k = 2^{k-1}$;
\FOR{$t=1$ {\bfseries to} $\tau_k$ }
\STATE Observe $x_{k,t}$;
\STATE Set price $v_{k,t}=J(x_{k,t}^{\top}\hat{\theta}_{k}) $;
\STATE Receive $r_{k,t} = v_{k_t}\cdot\mathbbm{1}_t$;
\ENDFOR
\STATE Solve: $\hat{\theta}_{k+1}=\arg\min_{\theta\in\mathbb{H}}\hat{L}_{k}(\theta),$ where $\hat{L}_{k}(\theta)=\frac1{\tau_k}\sum_{t=1}^{\tau_k}l_{k,t}(\theta)$.
\ENDFOR
\end{algorithmic}
\end{algorithm}
\end{minipage}
\hfill
\begin{minipage}{0.48\textwidth}
\begin{algorithm}[H]
\caption{Online Newton Step Pricing (ONSP)}
\label{algo_ONSP}
\begin{algorithmic}
\STATE {\bfseries Input:} Convex and bounded set $\mathbb{H}$, $\theta_1$, parameter $\gamma, \epsilon>0$
\STATE Set $A_0=\epsilon\cdot{I_d}$;
\FOR{$t=1$ {\bfseries to} $T$}
\STATE Observe $x_t$;
\STATE Set price $v_t=J(x_t^{\top}\theta_{t})$;
\STATE Receive $r_t=v_t\cdot\mathbbm{1}_t$;
\STATE Set surrogate loss function $l_t(\theta)$;
\STATE Calculate $\nabla_t=\nabla{l}_t(\theta)$;
\STATE Rank-1 update: $A_{t}=A_{t-1}+\nabla_t\nabla_t^{\top}$;
\STATE Newton step: $\hat{\theta}_{t+1} = \theta_t-\frac{1}{\gamma}A_{t}^{-1}\nabla_t$;
\STATE Projection: $\theta_{t+1}=\prod_{\mathbb{H}}^{A_t}(\hat{\theta}_{t+1})$.
\ENDFOR
\end{algorithmic}
\end{algorithm}
\end{minipage}
\vspace{-1em}
\end{figure}
\subsection{Pricing with Distribution-Free Stochastic Features}\label{subsec_alg_random}
\vspace{-0.5em}
\begin{assumption}[Stochastic features]\label{random_iid_xt}
Assume $x_t\sim \mathbb{D}\subseteq D$ are independently identically distributed (i.i.d.) from an unknown distribution, for any $t=1,2,\ldots,T$.
\end{assumption}
The first algorithm, Epoch-based Max-Likelihood Pricing (EMLP) algorithm, is suitable for a stochastic setting defined by Assumption \ref{random_iid_xt}. EMLP proceeds in epochs with each stage doubling the length of the previous epoch. At the end of each epoch, we consolidate the observed data and solve a maximum likelihood estimation problem to learn $\theta$. A max likelihood estimator (MLE) obtained by minimizing
$\hat{L}_{k}(\theta):=\frac{1}{\tau_k}\sum_{t=1}^{\tau_k}l_{k,t}(\theta),$
which is then used in the next epoch as if it is the true parameter vector. In the equation, $k,\tau_k$ denotes the index and length of epoch $k$. The estimator is computed using data in $hist(k)$, which denotes the transcript for epoch $1\sim k$.
The pseudo-code of EMLP is summarized in Algorithm~\ref{algo_MLP}. In the remainder of this section, we discuss the computational efficiency and prove the upper regret bound of $O(d\log{T})$.
\ifbool{compact}{\noindent\textbf{Computational Efficiency.}}{\paragraph{Computational Efficiency.}} {The calculations in EMLP are straightforward except for $\arg\min\hat{L}_k(\theta)$ and $J(u)$.
As $g(v,u)$ is proved unimodal in Lemma \ref{g_unimodal}, we may efficiently calculate $J(u)$ by binary search. We will prove that $l_{k,t}$ is exp-concave (and thus also convex). Therefore, we may apply any off-the-shelf tools for solving convex optimization.}
\ifbool{compact}{\noindent\textbf{MLE and Probit Regression.}}{\paragraph{MLE and Probit Regression.}}
{ A closer inspection reveals that this log-likelihood function corresponds to a probit \citep{aldrich1984linear} or a logit model \citep{wright1995logistic} for Gaussian or logistic noises. See Appendix \ref{appendix_probit_regression}.
}
\ifbool{compact}{\noindent\textbf{Affine Invariance.}}{\paragraph{Affine Invariance.}} {Both optimization problems involved depend only on $x^{\top} \theta$, so if we add any affine transformation to $x$ into $\tilde{x} = Ax$, the agent can instead learn a new parameter of $\tilde{\theta}^{*}=(A^{\top})^{-1}\theta^{*}$ and achieve the same $u_t=x_t^{\top}\theta^{*}$. Also, the regret bound is not affected as the upper bound $B$ over $x^{\top}\theta$ does not change \footnote{Here $A$ is assumed invertible, otherwise the mapping from $\tilde{x}_t$ to $u_t$ does not necessarily exist.}. Therefore, it is only natural that the regret bound does not depend on the distribution $x$, nor the condition numbers of $\mathbb{E}[xx^{\top}]$ (i.e., the ratio of $\lambda_{\max}/\lambda_{\min}$).}
\subsection{Pricing with Adversarial Features}\label{subsec_alg_adversarial}
In this part, we propose an ``Online Newton Step Pricing (ONSP)'' algorithm that deals with adversarial $\{x_t\}$ series and guarantees $O(d\log{T})$ regret. The pseudo-code of ONSP is shown as Algorithm \ref{algo_ONSP}. In each round, it uses the likelihood function as a surrogate loss and applies ``Online Newton Step''(ONS) method to update $\hat{\theta}$. In the next round, it adopts the updated $\hat{\theta}$ and sets a price greedily. In the remainder of this section, we discuss some properties of ONSP and prove the regret bound.
The calculations of ONSP are straightforward. The time complexity of calculating the matrix inverse $A_{t}^{-1}$ is $O(d^3)$, which is fair as $d$ is small. In high-dimensional cases, we may use \emph{Woodbury matrix identity}\footnote{$(A+xx^{\top})^{-1}=A^{-1}-\frac{1}{1+x^{\top}A^{-1}x}A^{-1}x(A^{-1}x)^{\top} .$} to reduce it to $O(d^2)$ as we could get $A^{-1}$ directly from the latest round.
\section{Regret Analysis}
\label{sec_regret}
In this section, we mainly prove the logarithmic regret bounds of EMLP and ONSP corresponding to stochastic and adversarial settings, respectively. Besides, we also prove an $\Omega(\sqrt{T})$ regret bound on fully parametric $F$ with one parameter unknown.
\subsection{\texorpdfstring{$O(d\log{T})$}{Lg} Regret of EMLP}\label{subsec_random_analysis}
In this part, we present the regret analysis of Algorithm \ref{algo_MLP}. First of all, we propose the following theorem as our main result on EMLP.
\begin{theorem}[Overall regret]
With Assumptions \ref{assumption_strictly_log_concave}, \ref{assumption_convex_feature_and_parameter_set}, \ref{assumption_bounded_x_set} and \ref{random_iid_xt}, the expected regret of EMLP can be bounded by:
\begin{equation}
\mathbb{E}[Reg_{\text{EMLP}}]\leq 2C_{s}{d}{\log{T}},
\end{equation}
where $C_{s}$ is a constant that depends only on $F(\omega)$ and is independent to $\mathbb{D}$.
\label{corollary_expected regret bound}
\end{theorem}
The proof of Theorem \ref{corollary_expected regret bound} is sophisticated. For the sake of clarity, we next present an inequality system as a roadmap toward the proof. After this, we formally illustrate each line of it with lemmas.
Since EMLP proposes $J(x_{k,t}^{\top}\hat{\theta}_{k})$ in every round of epoch $k$, we may denote the per-round regret as $Reg_t(\hat{\theta}_{k})$, where:
\begin{equation}
Reg_t(\theta): =g(J(x_t^{\top}\theta^{*}), x_t^{\top}\theta^{*})-g(J(x_t^{\top}\theta), x_t^{\top}\theta^{*}).
\label{eqn_parameter_based_regret}
\end{equation}
Therefore, it is sufficient to prove the following Theorem:
\begin{theorem}[Expected per-round regret] \label{expected regret bound}
For the per-round regret defined in Equation \eqref{eqn_parameter_based_regret}, we have:
\begin{equation*}
\mathbb{E}[Reg_{k,t}(\hat{\theta}_k)]\leq C_{s}\cdot\frac{d}{\tau_k}.
\end{equation*}
\end{theorem}
The proof roadmap of Theorem \ref{expected regret bound} can be written as the following inequality system.
\ifbool{twocol}{
\begin{equation}
\begin{aligned}
\mathbb{E}[Reg_{k,t}(\hat{\theta}_k)]&\leq C\cdot\mathbb{E}[ (\hat{\theta}_k-\theta^{*})^{\top}x_{k,t}x_{k,t}^{\top}(\hat{\theta}_k-\theta^{*})]\\
&\leq\frac{2C}{C_{\text{down}}}\mathbb{E}[L_k(\hat{\theta}_k)-L_k(\theta^{*})]\\
&\leq\frac{2C\cdot C_{\text{exp}}}{C_{\text{down}}^2}\frac{d}{\tau_k}.
\end{aligned}
\label{inequ_sys_reg_mle}
\end{equation}
}{
\begin{equation}
\mathbb{E}[Reg_{k,t}(\hat{\theta}_k)]\leq C\cdot\mathbb{E}[ (\hat{\theta}_k-\theta^{*})^{\top}x_{k,t}x_{k,t}^{\top}(\hat{\theta}_k-\theta^{*})]\leq\frac{2C}{C_{\text{down}}}\mathbb{E}[\hat{L}_k(\hat{\theta}_k)-\hat{L}_k(\theta^{*})]\leq\frac{2C\cdot C_{\text{exp}}}{C_{\text{down}}^2}\frac{d}{\tau_k}.
\label{inequ_sys_reg_mle}
\end{equation}
}
We explain Equation \eqref{inequ_sys_reg_mle} in details. The first inequality comes from the following Lemma \ref{analytical_regret_bound}.
\begin{lemma}[Quadratic regret bound]
We have:
\ifbool{twocol}{
\begin{equation}
Reg_t(\theta)\leq C\cdot (\theta-\theta^{*})^{\top}x_tx_t^{\top}(\theta-\theta^{*}),
\end{equation}$\forall\theta\in\mathbb{H}, \forall x_t\in\mathbb{D}$.
}{
\begin{equation}
Reg_t(\theta)\leq C\cdot (\theta-\theta^{*})^{\top}x_tx_t^{\top}(\theta-\theta^{*}), \forall\theta\in\mathbb{H}, \forall x_t\in\mathbb{D}.
\end{equation}
} Here $C=2B_f+(B+J(0))\cdot B_{f'}.$
\label{analytical_regret_bound}
\end{lemma}
The intuition is that function $g(J(u),u)$ is $2^{nd}$-order-smooth at $(J(u^*), u^*)$. A detailed proof of Lemma \ref{analytical_regret_bound} is in Appendix \ref{appendix_subsec_proof_of_regret_bound}. Note that $C$ is highly dependent on the distribution $F$. After this, we propose Lemma \ref{lemma_quadratic_likelihood_bound} that contributes to the second inequality of Equation \eqref{inequ_sys_reg_mle}.
\begin{lemma}[Quadratic likelihood bound]
For the expected likelihood function $L_t(\theta)$ defined in Equation \eqref{equation_expected_log_likelihood}, we have:
\begin{equation}
L_t(\theta)-L_t(\theta^{*})\geq\frac12 C_{\text{down}}(\theta-\theta^{*})^{\top}x_tx_t^{\top}(\theta-\theta^{*}), \forall \theta\in\mathbb{H}, \forall x\in\mathbb{D},
\label{equation_quadratic_likelihood_bound}
\end{equation}
\begin{equation}
\text{ where }\;\;\;
C_{\text{down}}:=\inf_{\omega\in[-B, B+J(0)]}\min\left\{\frac{\text{d}^2\log(1-F(\omega))}{\text{d}\omega^2}, \frac{\text{d}^2\log(F(\omega))}{\text{d}\omega^2}\right\}>0.
\label{eq__C_down}
\end{equation}
\label{lemma_quadratic_likelihood_bound}
\end{lemma}
\begin{proof}
Since the true parameter always maximizes the expected likelihood function \citep{murphy2012machine}, by Taylor Expansion we have $\nabla L(\theta^{*})=0$, and hence $L_t(\theta)-L_t(\theta^{*}) = \frac{1}{2}(\theta-\theta^{*})^{\top}\nabla^2 L_t(\tilde{\theta})(\theta-\theta^{*})$ for some $\tilde{\theta}=\alpha\theta^{*}+(1-\alpha)\theta$. Therefore, we only need to prove the following lemma:
\begin{lemma}[Strong convexity and Exponential Concavity]\label{strong_convexity}
Suppose $l_{t}(\theta)$ is the negative log-likelihood function in epoch $k$ at time $t$. For any $\theta\in\mathbb{H}, x_{t}\sim\mathbb{D}$, we have:
\ifbool{twocol}{
\begin{equation}
\begin{aligned}
\nabla^2l_{t}(\theta)&\succeq C_{\text{down}} x_{t}x_{t}^{\top}\\
&\succeq \frac{C_{\text{down}}} {C_{\text{exp}}}\nabla l_{t}(\theta)\nabla l_{t}(\theta)^{\top}\succeq 0,
\end{aligned}
\end{equation}
}{
\begin{equation}
\nabla^2l_{t}(\theta)\succeq C_{\text{down}} x_{t}x_{t}^{\top}\succeq \frac{C_{\text{down}}} {C_{\text{exp}}}\nabla l_{t}(\theta)\nabla l_{t}(\theta)^{\top}\succeq 0,
\end{equation}
}
\begin{equation}
\text{ where }\;
C_{\text{exp}}:=\sup_{\omega\in[-B, B+J(0)]}\max\left\{\frac{f(\omega)^2}{F(\omega)^2}, \frac{f(\omega)^2}{(1-F(\omega))^2}\right\}<+\infty.
\label{eqn_def_c_exp}
\end{equation}
\end{lemma}
Proof of Lemma \ref{strong_convexity} is in Appendix \ref{appendix_subsec_proof_of_strong_convexity}. With this lemma, we see that Lemma \ref{lemma_quadratic_likelihood_bound} holds.
\end{proof}
With Lemma \ref{analytical_regret_bound} and Lemma \ref{lemma_quadratic_likelihood_bound}, we can immediately get the following Lemma \ref{theorem_surrogate}.
\begin{lemma}[Surrogate Regret]
The relationship between $Reg(\theta)$ and likelihood function can be shown as follows:
\begin{equation}
Reg_t(\theta)\leq \frac{2\cdot C}{C_{\text{down}}}\left(L_t(\theta)-L_t(\theta^{*})\right),
\label{equation_surrogate}
\end{equation}
$\forall\theta\in\mathbb{H},\forall{x}\in\mathbb{D}$, where $C$ and
$C_{\text{down}}$ are defined in Lemma \ref{analytical_regret_bound} and \ref{lemma_quadratic_likelihood_bound} respectively.
\label{theorem_surrogate}
\end{lemma}
Lemma \ref{theorem_surrogate} enables us to choose the negative log-likelihood function as a surrogate loss. This is not only an important insight of EMLP regret analysis, but also the foundation of ONSP design.
The last inequality of Equation \eqref{inequ_sys_reg_mle} comes from this lemma:
\begin{lemma}[Per-epoch surrogate regret bound]
Denoting $\hat{\theta}_k$ as the estimator coming from epoch $(k-1)$ and being used in epoch $k$, we have:
\begin{equation}
\mathbb{E}_{h}[\hat{L}_k(\hat{\theta}_k)-\hat{L}_k(\theta^{*})]\leq\frac{C_{\text{exp}}}{C_{\text{down}}}\cdot\frac{d}{\tau_k+1}.
\label{d_over_tau_geq_diff_L}
\end{equation}
Here $C_{\text{exp}}$ is defined in Equation \ref{eqn_def_c_exp}, and $\mathbb{E}_h[\cdot] = \mathbb{E}[\cdot|hist(k-1)].$
\label{before_expectation}
\end{lemma}
Proof of Lemma \ref{before_expectation} is partly derived from the work \citet{koren2015fast}, and here we give a proof sketch without specific derivations. A detailed proof lies in Appendix \ref{appendix_subsec_proof_of_uniform_stability}.
\noindent\emph{Proof sketch} of Lemma \ref{before_expectation}. We list the four main points that contribute to the proof:
\begin{itemize}
\topsep-1em
\itemsep0em
\item Notice that $l_{k,t}(\theta)$ is strongly convex w.r.t. a seminorm $x_{k,t}x_{k,t}^{\top}$, we know $\hat{L}_{k}(\theta)$ is also strongly convex w.r.t. $\sum_{t=1}^{\tau_k}x_{k,t}x_{k,t}^{\top}$.
\item For two strongly convex functions $g_1$ and $g_2$, we can upper bound the distance between their arg-minimals (scaled by some norm $||\cdot||$) with the dual norm of $\nabla(g_1-g_2)$.
\item Since a seminorm has no dual norm, we apply two methods to convert it into a norm: (1) separation of parameters and likelihood functions with a ``leave-one-out'' method (to separately take expectations), and (2) separation of the spinning space and the null space.
\item As the dual data-dependent norm offsets the sum of $xx^{\top}$ to a constant, Lemma \ref{before_expectation} holds.
\end{itemize}
We have so far proved Inequality \eqref{inequ_sys_reg_mle} after proving Lemma \ref{analytical_regret_bound}, \ref{lemma_quadratic_likelihood_bound}, \ref{before_expectation}. Therefore, Theorem \ref{expected regret bound} holds.
\subsection{\texorpdfstring{$O(d\log{T})$}{Lg} Regret of ONSP}\label{subsec_adversarial_analysis}
Here we present the regret analysis of Algorithm \ref{algo_ONSP} (ONSP). Firstly, we state the main theorem.
\begin{theorem}\label{theorem_ONSP_main}
With Assumptions \ref{assumption_strictly_log_concave}, \ref{assumption_convex_feature_and_parameter_set}, \ref{assumption_bounded_x_set}, the regret of Algorithm \ref{algo_ONSP} (ONSP) satisfies:
\begin{equation}
Reg_{\text{ONSP}}\leq C_{a}\cdot d\log{T},
\label{equation_ONSP_regret}
\end{equation}
where $C_{a}$ is a function only dependent on $F$.
\end{theorem}
\begin{proof}
Proof of Theorem \ref{theorem_ONSP_main} here is more concise than Section \ref{subsec_random_analysis}, because the important Lemma \ref{strong_convexity} and \ref{theorem_surrogate} have been proved there. From Lemma \ref{theorem_surrogate}, we have:
\begin{equation}
g(J(u_t^*),u_t^{*})-g(J(u_t),u_t^{*})\leq \frac{2\cdot C}{C_{\text{down}}}\cdot\mathbb{E}_{N_t}[l_t(\theta_{t})-l_t(\theta^{*})].
\label{equation_theorem_12}
\end{equation}
With Equation \ref{equation_theorem_12}, we may reduce the regret of likelihood functions as a surrogate regret of pricing. From Lemma \ref{strong_convexity} we see that the log-likelihood function is $\frac{C_{\text{down}}}{C_{\text{exp}}}$-exponentially concave\footnote{A function $f(\mu)$ is $\alpha$-exponentially concave iff $\nabla^2f(\mu)\succeq\alpha\nabla f(\mu)\nabla f(\mu)^{\top}$.}. This enables an application of Online Newton Step method to achieve a logarithmic regret. Therefore, by citing from the \emph{Online Convex Optimization} \citep{hazan2019introduction}, we have the following Lemma.
\begin{lemma}[Online Newton Step] \label{thmons} With parameters $\gamma = \frac{1}{2}\min\{\frac{1}{4GD}, \alpha\}$ and $\epsilon=\frac{1}{\gamma^2D^2}$, and $T>4$ guarantees:
\begin{equation*}
\sup_{\{x_t\}}\left\{\sum_{t=1}^{T}l_t(\theta_{t})-\min_{\theta\in\mathbb{H}}\sum_{t=1}^{T}l_t(\theta)\right\}\leq5\left(\frac{1}{\alpha}+GD\right)d\log T.
\end{equation*}
Here $\alpha = \frac{C_{\text{down}}}{C_{\text{exp}}}$, $D=2\cdot B_1$ and $G=\sqrt{C_{\text{exp}}}\cdot B_2$.
\end{lemma}
With Equation \ref{equation_theorem_12} and Lemma \ref{thmons}, we have:
\begin{equation}
Reg=\sum_{t=1}^{T}\left(g(J(u_t^*),u_t^{*})-\mathbb{E}_{N_1, N_2, \ldots, N_{t-1}}[g(J(u_t),u_t^{*})]\right)\leq\frac{2\cdot C}{C_{\text{down}}}\cdot5\left(\frac{1}{\alpha}+GD\right)d\log T.
\end{equation}
Therefore, we have proved Lemma \ref{theorem_ONSP_main}.
\end{proof}
\subsection{Lower Bound for Unknown Distribution}\label{sec_lower}
In this part, we evaluate Assumption \ref{assumption_strictly_log_concave} and prove that an $\Omega{(\sqrt{T})}$ lower regret bound is unavoidable with even a slight relaxation: a Gaussian noise with unknown $\sigma$. Our proof is inspired by \citet{broder2012dynamic} Theorem 3.1, while our lower bound relies on more specific assumptions (and thus applies to more general cases).
We firstly state Assumption \ref{assumption_fixed_unknown_parameter} covering this part, and then state Theorem \ref{theorem_lower_bound_square_root_t} as a lower bound:
\begin{assumption}
The noise $N_t\sim\mathcal{N}(0,\sigma^2)$ independently, where $0<\sigma\leq 1$ is fixed and \textbf{unknown}.
\label{assumption_fixed_unknown_parameter}
\end{assumption}
\begin{theorem}[Lower bound with unknown $\sigma$]
\label{theorem_lower_bound_square_root_t}
Under Assumption \ref{assumption_convex_feature_and_parameter_set}, \ref{assumption_bounded_x_set}, \ref{random_iid_xt} and \ref{assumption_fixed_unknown_parameter}, for any policy (algorithm) $\Psi: \mathbb{R}^{d}\times\left(\mathbb{R}^{d},\mathbb{R},\{0,1\}\right)^{t-1}\rightarrow\mathbb{R}^{+}$ and any $T>2$, there exists a Gaussian parameter $\sigma\in\mathbb{R}^{+}$, a distribution $\mathbb{D}$ of features and a fixed parameter $\theta^{*}$, such that:
$Reg_{\Psi}\geq{\frac1{24000}}\cdot\sqrt{T}.$
\end{theorem}
\noindent\emph{Remark:} Here we assume $x_t$ to be i.i.d., which also implies the applicability on adversarial features. However, the minimax regret of the stochastic feature setting is $\Theta(\sqrt{T})$ \citep{javanmard2019dynamic}, while existing results have not yet closed the gap in adversarial feature settings.
\noindent\emph{Proof sketch} of Theorem \ref{theorem_lower_bound_square_root_t}. Here we assume a fixed valuation, i.e. $u^{*}=x_t^{\top}\theta^{*}, \forall t=1,2,\ldots$. Equivalently, we assume a fixed feature. The main idea of proof is similar to that in \citet{broder2012dynamic}: we assume $\sigma_1=1, \sigma_2 = 1-T^{-\frac14}$, and we prove that: (1) it is costly for an algorithm to perform well in both cases if the $\sigma$'s are different by a lot, and (2) it is costly for an algorithm to distinguish the two cases if $\sigma$'s are close enough to each other. We put the detailed proof in Appendix \ref{appendix_proof_lower_bound}.
\section{Numerical Result}
\label{sec_num_result}
\begin{figure*}[t]
\centering
\begin{subfigure}[t]{0.48\textwidth}
\centering
\includegraphics[width= \textwidth]{figures/stochastic_plot_over_log_regression_error_bar.pdf}
\caption{Stochastic feature}\label{stochastic_plot}
\end{subfigure}
\quad \begin{subfigure}[t]{0.48\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/adversarial_plot_over_log_regression_error_bar.pdf}
\caption{Adversarial feature}\label{adversarial_plot}
\end{subfigure}
\caption{\small
The regret of EMLP, ONSP and EXP-4 on simulated examples (we only conduct EXP-4 up to $T=2^{12}$ due to its exponential time consuming), with Figure \subref{stochastic_plot} for stochastic features and Figure \subref{adversarial_plot} for adversarial ones. The plots are in log-log scales with all regrets divided by a $\log(t)$ factor to show the convergence. For EXP-4, we discretize the parameter space with $T^{-\frac13}$-size grids, which would incur an $\tilde{O}(T^{\frac23})$ regret according to \citet{cohen2020feature_journal}. We also plot linear fits for some regret curves, where a slope-$\alpha$ line indicates an $O(T^{\alpha})$ regret. Besides, we draw error bars and bands with 0.95 coverage using Wald’s test. The two diagrams reveal that (i) logarithmic regrets of EMLP and ONSP in the stochastic setting, (ii) a nearly-linear regret of EMLP in the adversarial setting, and (iii) $O(T^{\frac23})$ regrets of EXP-4 in both settings.
} \label{fig:plots}
\end{figure*}
In this section, we conduct numerical experiments to validate EMLP and ONSP. In comparison with the existing work, we implement a discretized EXP-4 \citep{auer2002nonstochastic} algorithm for pricing, as is introduced in \citet{cohen2020feature_journal} (in a slightly different setting). We will test these three algorithms in both stochastic and adversarial settings.
Basically, we assume $d=2, B_1=B_2=B=1$ and $N_t\sim\mathcal{N}(0,\sigma^2)$ with $\sigma = 0.25$. In both settings, we conduct EMLP and ONSP for $T=2^{16}$ rounds. For ONSP, we empirically select $\gamma$ and $\epsilon$ that accelerates the convergence, instead of using the values specified in Lemma \ref{thmons}. Since EXP-4 consumes exponential time and requires the knowledge of $T$ in advance to discretize the policy and valuation spaces, we execute EXP-4 for a series of $T=2^k, k=1,2,\ldots, 12$. We repeat every experiment 5 times for each setting and then take an average.
\ifbool{compact}{\noindent\textbf{Stochastic Setting.}}{\paragraph{Stochastic Setting.}} We implement and test EMLP, ONSP and EXP-4 with stochastic $\{x_t\}$'s. The numerical results are shown in Figure \ref{stochastic_plot} on a log-log diagram, with the regrets divided by $\log(t)$. It shows $\log(t)$-convergences on EMLP and ONSP, while EXP-4 is in a $t^{\alpha}$ rate with $\alpha\approx 0.699$.
\ifbool{compact}{\noindent\textbf{Adversarial Setting.}}{\paragraph{Adversarial Setting.}} We implement the three algorithms and test them with an adversarial $\{x_t\}$'s: for the $k$-th epoch, i.e. $t=2^{k-1}, 2^{k-1}+1, \ldots, 2^k-1$, we let $x_t = [1, 0]^{\top}$ if $k\equiv1(\mod2)$ and $x_t=[0,1]^{\top}$ if $k\equiv0(\mod2)$. The numerical results are shown in Figure \ref{adversarial_plot} on a log-log diagram, with the regrets divided by $\log(t)$. The log-log plots of ONSP and EXP-4 are almost the same as those in Figure \ref{stochastic_plot}. However, EMLP shows an almost linear ($t^{\alpha}$ rate with $\alpha\approx 0.912$) regret in this adversarial setting. This is because the adversarial series only trains one dimension of $\theta$ in each epoch, while the other is arbitrarily initialized and does not necessarily converge. However, in the next epoch, the incorrect dimension is exploited. Therefore, a linear regret originates.
\vspace{-0.5em}
\section{Discussion}
\vspace{-0.5em}
\label{sec_discussion}
Here we discuss the coefficients on our regret bounds as a potential extension of future works. In Appendix \ref{appendix_sec_more_discussion} we will discuss more on algorithmic design, problem modeling, and ethic issues.
\ifbool{compact}{\noindent\textbf{Coefficients on Regret Bounds.}}{\paragraph{Coefficients on Regret Bounds.}}
The exact regret bounds of both EMLP and ONSP contain a constant $\frac{C_{\text{exp}}}{C_{\text{down}}}$ that highly depends on the noise CDF $F$ and could be large. A detailed analysis in Appendix \ref{appendix_coefficient} shows that $\frac{C_{\text{exp}}}{C_{\text{down}}}$ is exponentially large w.r.t. $\frac{B}{\sigma}$ (see Equation \ref{equ_down_exp} and Lemma \ref{lemma_lambda}) for Gaussian noise $\mathcal{N}(0, \sigma^2)$, which implies that a smaller noise variance would lead to a (much) larger regret bound. This is very counter-intuitive as a larger noise usually leads to a more sophisticated situation, but similar phenomenons also occur in existing algorithms that are suitable for constant-variance noise, such as RMLP in \citet{javanmard2019dynamic} and OORMLP in \citet{wang2020online}. In fact, it is because a (constantly) large noise would help explore the unknown parameter $\theta^*$ and smoothen the expected regret. In this work, this can be addressed by increasing $T$ since we mainly concern the asymptotic regrets as $T\rightarrow\infty$ with fixed noise distributions. However, we admit that it is indeed a nontrivial issue for finite $T$ and small $\sigma$ situations. There exists a ``ShallowPricing'' method in \citet{cohen2020feature_journal} that can deal with a very-small-variance noise setting (when $\sigma=\tilde{O}(\frac1{T})$) and achieve a logarithmic regret. Specifically, its regret bound would decrease as the noise variance $\sigma$ decreases (but would still not reach $O(\log\log{T})$ as the noise vanishes). We might also apply this method as a preprocess to cut the parameter domain and decrease $\frac{B}{\sigma}$ within logarithmic trials (see \citet{cohen2020feature_journal} Thm. 3), but it is still open whether a $\log(T)$ regret is achievable when $\sigma=\Theta(T^{-\alpha})$ for $\alpha\in(0,1)$.
\section{Conclusion}
\label{sec_conclusion}
In this work, we studied the problem of online feature-based dynamic pricing with a noisy linear valuation in both stochastic and adversarial settings. We proposed a max-likelihood-estimate-based algorithm (EMLP) for stochastic features and an online-Newton-step-based algorithm (ONSP) for adversarial features. Both of them enjoy a regret guarantee of $O(d\log{T})$, which also attains the information-theoretic limit up to a constant factor. Compared with existing works, EMLP gets rid of strong assumptions on the distribution of the feature vectors in the stochastic setting, and ONSP improves the regret bound exponentially from $O(T^{2/3})$ to $O(\log{T})$ in the adversarial setting. We also showed that knowing the noise distribution (or the demand curve) is required to obtain logarithmic regret, where we prove a lower bound of $\Omega(\sqrt{T})$ on the regret for the case when the noise is knowingly Gaussian but with an unknown $\sigma$. In addition, we conducted numerical experiments to empirically validate the scaling of our algorithms. Finally, we discussed the regret dependence on the noise variance, and proposed a subtle open problem for further study.
\section*{Acknowledgments}
The work is partially supported by the Adobe Data Science Award and a start-up grant from the UCSB Department of Computer Science. We appreciate the input from anonymous reviewers and AC as well as a discussion with Akshay Krishnamurthy for clarifying some details of \citet{krishnamurthy2020contextual}.
\bibliographystyle{abbrvnat}
\bibliography{ref_log}
\newpage