  We consider dynamic pricing with covariates under a generalized linear demand
model: a seller can dynamically adjust the price of a product over a horizon of
$T$ time periods, and at each time period $t$, the demand of the product is
jointly determined by the price and an observable covariate vector
$x_t\in\mathbb{R}^d$ through a generalized linear model with unknown
co-efficients. Most of the existing literature assumes the covariate vectors
$x_t$'s are independently and identically distributed (i.i.d.); the few papers
that relax this assumption either sacrifice model generality or yield
sub-optimal regret bounds. In this paper, we show that UCB and Thompson
sampling-based pricing algorithms can achieve an $O(d\sqrt{T}\log T)$ regret
upper bound without assuming any statistical structure on the covariates $x_t$.
Our upper bound on the regret matches the lower bound up to logarithmic
factors. We thus show that (i) the i.i.d. assumption is not necessary for
obtaining low regret, and (ii) the regret bound can be independent of the
(inverse) minimum eigenvalue of the covariance matrix of the $x_t$'s, a
quantity present in previous bounds. Moreover, we consider a constrained
setting of the dynamic pricing problem where there is a limited and
unreplenishable inventory and we develop theoretical results that relate the
best achievable algorithm performance to a variation measure with respect to
the temporal distribution shift of the covariates. We also discuss conditions
under which a better regret is achievable and demonstrate the proposed
algorithms' performance with numerical experiments.
