Bayesian dithering for learning: Asymptotically optimal policies in dynamic pricing

Problem of incomplete learning

To achieve the maximum possible revenue, the seller would ideally learn the underlying demand model at some finite period and choose the optimal price from then on. Unfortunately, this is not possible due to demand uncertainty, and worse still, the seller may never learn the underlying demand model for some products, which is the problem of incomplete learning. We discuss how incomplete learning occurs in our setting.

For a product i, suppose there exists a price vector

p ̂ $\hat{p}$

ρ i ( p ̂ , β ) = ρ ̂ $\rho ^i(\hat{p}, \beta )=\hat{\rho }$

β ∈ Θ i $\beta \in \Theta ^i$

ρ ̂ $\hat{\rho }$

p t = p ̂ $p_t =\hat{p}$

Π t i = Π t − 1 i $\Pi _t^i=\Pi _{t-1}^i$

p t + 1 = π t + 1 ( Π t i ) = π t ( Π t − 1 i ) = p ̂ $p_{t+1}=\pi _{t+1}(\Pi _t^i)=\pi _t(\Pi _{t-1}^i)=\hat{p}$

s > t $s>t$

p ̂ $\hat{p}$

3

j ≠ i $j\ne i$

Π t j ≠ Π t − 1 j $\Pi _t^j \ne \Pi _{t-1}^j$

p ̂ $\hat{p}$

OPEN IN VIEWER

FIGURE 1

Examples of two demand models. Note: In Panel (a), each curve corresponds to a potential demand model. There are three intersection points between the two demand models, and their projection in the one‐dimensional price space is a set of three discrete points. In Panel (b), each demand model depends on prices of the two products. Their intersection includes an uncountable number of intersection points. As shown in gray, the projection of the intersection points in the two‐dimensional price space is a collection of three curves.

Now consider a price vector

p ∼ $\tilde{p}$

ρ i ( p ∼ , β 1 ) = ρ i ( p ∼ , β 2 ) $\rho ^i(\tilde{p}, \beta _1)=\rho ^i(\tilde{p}, \beta _2)$

β 1 , β 2 ∈ Θ i $\beta _1, \beta _2 \in \Theta ^i$

ρ i ( · , β 1 ) $\rho ^i(\cdot , \beta _1)$

ρ i ( · , β 2 ) $\rho ^i(\cdot , \beta _2)$

β 3 ∈ Θ i $\beta _3\in \Theta ^i$

ρ i ( p ∼ , β 3 ) ≠ ρ i ( p ∼ , β 1 ) $\rho ^i(\tilde{p}, \beta _3)\ne \rho ^i(\tilde{p}, \beta _1)$

ρ i ( p ∼ , β 3 ) ≠ ρ i ( p ∼ , β 2 ) $\rho ^i(\tilde{p}, \beta _3)\ne \rho ^i(\tilde{p}, \beta _2)$

p ∼ $\tilde{p}$

ρ i ( · , β 3 ) $\rho ^i(\cdot , \beta _3)$

ρ i ( · , β 1 ) , ρ i ( · , β 2 ) $\rho ^i(\cdot , \beta _1), \rho ^i(\cdot , \beta _2)$

p t = p ∼ $p_t=\tilde{p}$

Π t i ≠ Π t − 1 i $\Pi _t^i\ne \Pi _{t-1}^i$

p ∼ $\tilde{p}$

In contrast to a confounding price, we call a price

p ∈ P $p\in \mathcal {P}$

ρ i ( p , β 1 ) ≠ ρ i ( p , β 2 ) $\rho ^i(p, \beta _1)\ne \rho ^i(p, \beta _2)$

The problem of incomplete learning is more nuanced than our discussion above. If p is discriminative, but

ρ i ( p , β 1 ) $\rho ^i(p, \beta _1)$

ρ i ( p , β 2 ) $\rho ^i(p, \beta _2)$

β 1 , β 2 ∈ Θ i $\beta _1, \beta _2\in \Theta ^i$

Before formally introducing dithering policies, we present an assumption essential for learning. As stated below, we assume throughout the paper that demand models are sufficiently distinct. More specifically, we assume that the underlying demand model

ρ i ( · , θ 0 i ) $\rho ^i(\cdot , \theta _0^i)$

ρ i ( · , θ i ) $\rho ^i(\cdot , \theta ^i)$

Assumption 1

For any product

i ∈ { 1 , … , I } $i\in \lbrace 1, \ldots , I\rbrace$

, we make the following assumptions: (a)

For any

p ∈ P $p\in \mathcal {P}$

and any

θ i ∈ Θ i $\theta ^i\in \Theta ^i$

, if

ρ i ( p , θ i ) = ρ i ( p , θ 0 i ) $\rho ^i(p, \theta ^i) = \rho ^i(p, \theta ^i_0)$

and

θ i ≠ θ 0 i $\theta ^i\ne \theta _0^i$

, then

∂ ∂ p ρ i ( p , θ i ) ≠ ∂ ∂ p ρ i ( p , θ 0 i ) . \begin{equation} \frac{\partial }{\partial p} \rho ^i(p, \theta ^i) \ne \frac{\partial }{\partial p} \rho ^i\big(p, \theta ^i_0\big) . \end{equation}

4

(b)

When

Θ i $\Theta ^i$

is compact and convex, assume that for any

p ∈ P $p \in \mathcal {P}$

and any unit vector

v ∈ R N $v\in \mathbb R^N$

, if

∂ ∂ θ ρ i ( p , θ 0 i ) · v = 0 $\frac{\partial }{\partial \theta } \rho ^i(p, \theta ^i_0) \cdot v = 0$

, then

∂ ∂ p ∂ ∂ θ ρ i ( p , θ 0 i ) · v ≠ 0 , \begin{equation} \frac{\partial }{\partial p}{\left(\frac{\partial }{\partial \theta } \rho ^i\big(p, \theta ^i_0\big) \cdot v\right)} \ne {\bf 0} , \end{equation}

5

where 0 is the zero vector in

R I $\mathbb R^I$

.

Assumption 1 guarantees that parameters can be learned by pricing properly. As discussed above, any confounding price may cause the problem of incomplete learning, and intuitively, the underlying demand model should differ from any other demand model around the confounding prices so that it is possible to tell the difference between the two. This is guaranteed by Assumption 1(a). When the parameter is close to the underlying parameter θ₀, the two corresponding demand models are close by continuity. It is harder to learn around their intersection, especially when the demand model is “flat” at θ₀. Assumption 1(b) ensures that as prices vary, the demand model can become steeper at θ₀. This implies that by perturbing the price, we can gather sufficient information and avoid incomplete learning at the intersection point. Assumption 1 is a technical assumption. We note that the assumption is satisfied by a wide range of parametric demand models commonly used in the pricing literature, such as the linear demand model

{ a − b · p : a ∈ R + , b ∈ R + I } $\lbrace a-b\cdot p:a\in \mathbb R_+, b\in \mathbb R_+^I\rbrace$

{ e a − b · p 1 + e a − b · p : a ∈ R + , b ∈ R + I } $\lbrace \frac{e^{a-b\cdot p}}{1+e^{a-b\cdot p}}:a\in \mathbb R_+, b\in \mathbb R_+^I\rbrace$

p ∈ R + I $p\in \mathbb R_+^I$

ρ i ( p , θ ) = ( θ 1 + θ 2 ) p $\rho ^i(p,\theta )=(\theta ^1+\theta ^2)p$

p ∈ R + $p\in \mathbb R_+$

( θ 1 + θ 2 ) $(\theta ^1+\theta ^2)$

Another typical assumption in the literature is the existence of k exploration prices such that if these prices are chosen in k consecutive periods, the corresponding distributions are different under any pair of different parameters (see, e.g., Broder & Rusmevichientong, 2012). This implies that the k exploration prices should be informative for any pair of models, yet any pair of demand models can be close or even overlap around the confounding prices. In that regard, Assumption 1 seems to be more restricted. Nevertheless, the exploration prices need to be identified in advance, which may be impractical since the number k can be large. For example, the linear model of I products requires

k ≥ I + 1 $k\ge I+1$

Dithering policies

The myopic policy has been widely used in practice due to its simplicity (Morel et al., 2003). Since the problem of incomplete learning may occur under the myopic policy (Section 2.1), we modify it and propose dithering policies that achieve asymptotically optimal performance.

We start by introducing the MBP. For a seller who has beliefs

Π = ( Π 1 , … , Π I ) $\Pi =(\Pi ^1, \ldots , \Pi ^I)$

p = ( p 1 , … , p I ) ∈ P $p=(p^1,\ldots ,p^I)\in \mathcal {P}$

r ( p , Π ) : = ∑ i = 1 I ∫ θ i ∈ Θ i p i ρ i ( p , θ i ) d Π i ( θ i ) . \begin{equation} r(p,{\Pi}):=\sum _{i=1}^I\int_{{\theta}^i\in {{\Theta}}^i}{p}^i{\rho}^i(p,{\theta}^i)\mathrm{d}{\Pi}^i({\theta}^i). \end{equation}

6

φ ( Π ) = ( φ 1 ( Π ) , … , φ I ( Π ) ) $\varphi (\Pi )=(\varphi ^1(\Pi ),\ldots ,\varphi ^I(\Pi ))$

φ ( Π ) ∈ arg max { r ( p , Π ) : p ∈ P } . \begin{equation} \varphi (\Pi ) \in \arg \max \lbrace r(p,\Pi ): p\in \mathcal {P}\rbrace . \end{equation}

7

φ ( Π ) $\varphi (\Pi )$

P $\mathcal {P}$

P $\mathcal {P}$

P $\mathcal {P}$

We apply the dithering approach to modify the MBP. The idea is that by adding a perturbation to the myopic price, we can avoid confounding prices and gather sufficient information for learning with a high probability. More specifically, Bayesian dithering offers a chance to learn from a set of prices rather than a single one whenever making a pricing decision. As long as the set of confounding prices has measure zero in the price space, there is a high chance to choose a price that yields a sufficiently large gap between any pair of demand models, which helps tell them apart. For example, consider the example of two demand models for a single product in Figure 1a. Every time, the dithering policy chooses randomly from an interval of prices rather than a single price, and the seller can gather information from the difference between two demand models in a region. Whether it contains confounding prices or not, learning from a region offers a high chance of sufficient price exploration. Similarly, we can consider the example with two products in Figure 1b. There are an uncountable number of intersection points between two demand models of a product. However, if we choose from an interval of prices for each product, our choice provides sufficient information for demand learning with high probability.

In this paper, we consider a policy

π = ( π t ) t ∈ N $\pi =(\pi _t)_{t\in \mathbb {N}}$

ε t $\varepsilon _t$

p t = π t ( Π t − 1 ) = φ ( Π t − 1 ) + ε t $p_t=\pi _t(\Pi _{t-1})=\varphi (\Pi _{t-1})+\varepsilon _t$

Π t − 1 ( · ) $\Pi _{t-1}(\cdot )$

ε t $\varepsilon _t$

[ − b t , b t ] I $[-b_t, b_t]^I$

ε t ∼ U [ − b t , b t ] I $\varepsilon _t \sim \mathcal {U}[-b_t, b_t]^I$

{ b t } t ∈ N $\lbrace b_t\rbrace _{t\in \mathbb {N}}$

t → ∞ $t\rightarrow \infty$

P $\mathcal {P}$

P ∼ $\widetilde{\mathcal {P}}$

P $\mathcal {P}$

P $\mathcal {P}$

bd ( P ∼ ) $\mathrm{bd}(\widetilde{\mathcal {P}})$

P ∼ $\widetilde{\mathcal {P}}$

d 0 : = inf x ∈ P , y ∈ bd ( P ∼ ) ∥ x − y ∥ $d_0 := \inf _{x\in \mathcal {P}, y\in \mathrm{bd}(\widetilde{\mathcal {P}})} \Vert x-y\Vert$

P ∼ $\widetilde{\mathcal {P}}$

d 0 > 0 $d_0>0$

P ∼ $\widetilde{\mathcal {P}}$

{ ρ i ( · ) } i = 1 I $\lbrace \rho ^i(\cdot )\rbrace _{i=1}^I$

P ∼ $\widetilde{\mathcal {P}}$

P ∼ ∖ P $\widetilde{\mathcal {P}}\setminus \mathcal {P}$

The choice of dithering levels

{ b t } $\lbrace b_t\rbrace$

{ b t } $\lbrace b_t\rbrace$

As a variant of the widely used myopic policy, the dithering policy is easy to implement and computationally efficient. Our dithering policy is an example of a randomized policy, which, in the context of dynamic pricing, can have practical benefits. For example, a policy that randomizes markdowns over time, compared to a state‐contingent policy, benefits retailers when online customers monitor the timing of purchase to obtain discounts (as shown in Moon et al., 2018). Similarly, the dithering approach makes it harder for monitoring and should be useful for pricing in the presence of strategic customers. Another property of the dithering policy is that price jumps vanish over time. In practice, this is desirable, as price fluctuation may affect customers' reference price or hurt the seller's reputation, which induces more uncertainty in demand and makes it harder to learn. We note that this property is also satisfied by the myopic policy, but it does not hold in many machine learning algorithms such as the ε‐greedy algorithm (see Auer et al., 2002). In particular, while the ε‐greedy algorithm does induce convergence of the posterior beliefs, jumps in the price sequence persist over time. We further illustrate this property by plotting the price paths under the myopic, ε‐greedy, and dithering policies, which can be found in Appendix A.2 in the Supporting Information.

Comparison with other policies

Before we proceed to the theoretical analysis, we compare our dithering policy with several typical policies studied in the literature and test their numerical performance in two examples. 1.

MBP. As a baseline, we consider the MBP, which is widely used in practice (Morel et al., 2003). As discussed in Section 2.1, since it is a policy of pure exploitation, it may lead to the problem of incomplete learning and incur a considerable regret.

2.

TS. A well‐known algorithm is TS, which has been shown to achieve a matching upper bound of order

log T $\log T$

in the classic MAB problem (Agrawal & Goyal, 2012) and applied in many dynamic pricing problems (see, e.g., Ferreira et al., 2018). While the dithering policy actively “tunes” its parameters to learn, TS explores in a passive way. In particular, it estimates the parameter by a sample from the current belief and chooses the corresponding optimal price. By sampling over the parameter space, TS also chooses a random price, but the passive way of learning may incur an extra regret when active exploration is not needed (as we shall see in Figure 2b).

3.

FMBP. The flexibly constrained variant of the MBP (FMBP) is introduced in Harrison et al. (2012). It chooses the best‐guess price outside a predetermined interval of the confounding price with size

2 ε t $2\epsilon _t$

in period t. This requires solving a (nonconvex) constrained maximization in each period. One can implement this by projecting the myopic price onto the boundary if it is within a neighborhood of a confounding price and following the myopic price otherwise. We note that FMBP is designed and analyzed for the discriminative case, where the interval size should be set as

ε t = ε 1 t − α $\epsilon _t=\epsilon _1 t^{-\alpha }$

for

α ∈ ( 0 , 1 4 ) $\alpha \in (0, \frac{1}{4})$

and a small

ε 1 > 0 $\epsilon _1>0$

to achieve a constant regret. We can extend it to the finite parameter case and tune the constants α and ε₁ for a good performance. For the continuous parameter case and the multiproduct problem, however, there can be an uncountable number of confounding prices, rendering it impractical to identify those prices and rule out their neighborhoods.

4.

Controlled variance policy (CVP). The CVP is proposed in den Boer and Zwart (2014). To guarantee sufficient price exploration, it excludes a taboo interval centered at the average price and solves for the best price based on the maximum quasi‐likelihood estimate (MQLE). The taboo interval is designed with size

2 t + 1 t [ ( t + 1 ) ℓ t + 1 − t ℓ t ] $2\sqrt {\frac{t+1}{t}[(t+1)\ell _{t+1}-t\ell _t]}$

such that the variance of prices is lower bounded by

ℓ t = c t α − 1 $\ell _t=c t^{\alpha -1}$

for some constants

c > 0 $c>0$

and

α ∈ ( 0 , 1 ) $\alpha \in (0,1)$

. They tune the constants and analyze the theoretical performance of CVP for the generalized linear model, where the two unknown parameters are from a connected set similar to our continuous parameter case.

The CVP can be adapted to our Bernoulli‐demand setting with a linear form of selling probabilities, but the interval size should be adjusted when the parameter set is finite. For example, we adjust the lower bound as

ℓ t = c t log t $\ell _t=\frac{c}{t}\log t$

for the finite parameter case, otherwise the cumulative regret would be of a higher order than

log T $\log T$

. (This is because the cumulative regret under CVP is proportional to

∑ t = 1 T ( p t − p 0 ∗ ) 2 = ∑ t = 1 T ( p t − p ¯ T ) 2 + T ( p ¯ T − p 0 ∗ ) 2 ≥ ∑ t = 1 T ( p t − p ¯ T ) 2 ≥ ℓ T = c T α $\sum _{t=1}^T (p_t-p^*_0)^2= \sum _{t=1}^T (p_t-\bar{p}_T)^2+T(\bar{p}_T-p^*_0)^2\ge \sum _{t=1}^T (p_t-\bar{p}_T)^2\ge \ell _T= c T^\alpha$

, where

p ¯ T $\bar{p}_T$

is the average price.) Similarly, for the discriminative case, the lower bound should be adjusted as

ℓ t = c t $\ell _t=\frac{c}{t}$

to achieve a constant regret. Indeed, the size of the taboo interval would then become 0, and the CVP policy reduces to the greedy policy (Greedy) that chooses the optimal price under the “most likely” demand model, which corresponds to the parameter with the highest likelihood. We conjecture that the CVP policy with the above choices of the interval size would achieve matching upper bounds for the finite parameter case, but more work is needed to prove the theoretical performance. Besides, extending it to multiple products is not straightforward since the price variations should be guaranteed in different directions of the high‐dimensional price space (see the discussion in Keskin & Zeevi, 2014). We also note that CVP may need to solve a constrained maximization problem in each period, which is nonconvex in general. To avoid the potential computational issue, one can compute the myopic price based on the current estimate and project it onto the boundary of the taboo interval if it is outside the interval.

OPEN IN VIEWER

FIGURE 2

Average relative regret under different policies. Note: Each curve depicts the average relative regret of a policy over 10⁴ sample paths. In Panel (a), we plot

Δ ( T ) $\Delta (T)$

versus T over 2000 periods. In Panel (b), we plot

Δ ( T ) $\Delta (T)$

versus

log 10 ( T ) $\log _{10}(T)$

over 10⁴ periods (the first 50 periods are omitted). Details of the examples and tuning parameters are provided in Appendix A.3 in the Supporting Information.

Now we compare the numerical performance of these policies. We first adopt the numerical example tested in Harrison et al. (2012), where FMBP can achieve a constant regret. Indeed, this example belongs to the discriminative case in which all optimal prices are discriminative, and a constant regret can also be achieved by a modified version of dithering (as we shall see in Section 3.3). In Figure 2b we plot the average relative regret, defined as

Δ ( · ) : = 1 2 [ Δ 0 π ( · ) r 0 ∗ + Δ 1 π ( · ) r 1 ∗ ] $\Delta (\cdot ):=\frac{1}{2} [\frac{\Delta _0^\pi (\cdot )}{r_0^*}+\frac{\Delta _1^\pi (\cdot )}{r_1^*}]$

Δ m π ( · ) $\Delta _m^\pi (\cdot )$

r m ∗ $r_m^*$

ρ m ( · ) $\rho _m(\cdot )$

We then extend to the finite parameter case, where the optimal price of a potential demand model can be confounding and the best achievable regret is of order

log T $\log T$

log T $\log T$

The numerical results shown in Figure 2 suggest that dithering performs close to FMBP for the discriminative case and TS for the finite parameter case, which have been shown to be asymptotically optimal for their corresponding case. In the following section, we will justify its good numerical performance for both cases. Furthermore, we will show that with carefully chosen dithering levels, our policy yields a matching regret upper bound for the continuous parameter case.

A structural property of dithering

We first derive a structural property of the demand model when we apply the dithering approach. This result shows how dithering activates learning, which we will use to establish an upper bound on the rate of learning under the dithering policy. Lemma 1

Let θ₀ be the underlying parameter, and let

ε t $\varepsilon _t$

[ − b t , b t ] $[-b_t, b_t]$

b 0 > 0 $b_0>0$

κ > 0 $\kappa >0$

b t ∈ ( 0 , b 0 ) $b_t\in (0, b_0)$

8

The intuition behind the proof is that since any pair of demand models

ρ ( · , θ ) $\rho (\cdot , \theta )$

ρ ( · , θ 0 ) $\rho (\cdot , \theta _0)$

| ρ ( p , θ ) − ρ ( p , θ 0 ) | ∥ θ − θ 0 ∥ $\frac{|\rho (p, \theta )-\rho (p, \theta _0)|}{\Vert \theta -\theta _0\Vert }$

c > 0 $c>0$

κ > 0 $\kappa >0$

( p , θ ) ∈ P × Θ $(p, \theta )\in \mathcal {P}\times \Theta$

9

ρ ( · , θ ) $\rho (\cdot , \theta )$

ρ ( · , θ 0 ) $\rho (\cdot , \theta _0)$

b t $b_t$

ρ ( · , θ ) − ρ ( · , θ 0 ) $\rho (\cdot , \theta )-\rho (\cdot ,\theta _0)$

Assumption 1 implies that the underlying demand model differs from any other model at their intersection. Based on the assumption, Lemma 1 shows the role of dithering in our policy: The perturbation guarantees that the mean relative difference between the underlying model and any other model is bounded away from zero, which implies that we can always gather some information about the underlying demand model and avoid incomplete learning. Moreover, the amount of information we gather depends on the dithering level, so we need to carefully tune it to strike a balance between learning and earning. In the following subsections, we will apply the structural property of dithering and tune the dithering level to bound the regret, when the parameter set is finite (the finite parameter and discriminative cases) and when it is compact and convex (the continuous parameter case).

The finite parameter case: An

O ( log T ) $O(\log T)$

upper bound on regret

We now consider the finite parameter case, in which there are a finite number of potential parameters. We denote the parameter set by

Θ = { θ 0 , θ 1 , … , θ M } ⊂ R N $\Theta =\lbrace \theta _0, \theta _1, \ldots , \theta _M\rbrace \subset \mathbb R^N$

Π t ( θ m ) $\Pi _t(\theta _m)$

θ m $\theta _m$

m ∈ { 0 , 1 , … , M } $m\in \lbrace 0, 1, \ldots , M\rbrace$

Π 0 ( θ 0 ) $\Pi _0(\theta _0)$

O ( log T ) $O(\log T)$

Ω ( log T ) $\Omega (\log T)$

To bound the regret from above, we show that by dithering properly, we can gather sufficient information in each period and learn the parameter at a reasonably fast rate. As we learn over time, the posterior distribution assigns more mass to the true value θ₀, and the myopic price based on the posterior gets closer to the optimal price. This implies that the revenue loss from the myopic decision decreases to zero. Since the dithering level shrinks over time, the cost of dithering also decreases to zero. Thus, the one‐period regret under the dithering policy, which attributes to both the myopic decision and dithering, will eventually shrink to zero. Moreover, if the dithering level is suitably chosen, the cumulative regret can be bounded above by a term of order

log T $\log T$

Based on the idea above, we now formally establish the

O ( log T ) $O(\log T)$

θ ≠ θ 0 $\theta \ne \theta _0$

Π t ( θ 0 ) $\Pi _t(\theta _0)$

E 0 π [ 1 − Π t ( θ 0 ) ] $\mathbb E_0^\pi [1-\Pi _t(\theta _0)]$

10

R t ( θ , θ 0 ) $R_t(\theta , \theta _0)$

( X 1 , … , X t ) $(X_1, \ldots , X_t)$

( p 1 , … , p t ) $(p_1, \ldots , p_t)$

R t ( θ , θ 0 ) $R_t(\theta , \theta _0)$

θ = θ 0 $\theta = \theta _0$

R t ( θ , θ 0 ) = 1 $R_t(\theta , \theta _0)=1$

t ≥ 1 $t\ge 1$

θ ≠ θ 0 $\theta \ne \theta _0$

R t ( θ , θ 0 ) $R_t(\theta , \theta _0)$

E 0 π [ R t ( θ , θ 0 ) ] $\mathbb E^\pi _0 [ \sqrt {R_t(\theta , \theta _0)} ]$

Lemma 2

Let π be a dithering policy, and let b₀ be the positive constant defined in Lemma 1. Then, there exists a constant

c r > 0 $c_r>0$

such that for any decreasing sequence

{ b t } $\lbrace b_t\rbrace$

with

b 1 ∈ ( 0 , b 0 ) $b_1\in (0, b_0)$

, the likelihood ratio satisfies

E 0 π R t ( θ , θ 0 ) ≤ exp − c r θ − θ 0 2 ∑ k = 1 t b k 2 , ∀ t ≥ 1 . \begin{align} {\mathbb{E}}_0^{\pi}\left[\sqrt{R_t(\theta ,{\theta}_0)}\right]\le \exp \left(-c_r{\left\|\theta -{\theta}_0\right\|}^2\sum _{k=1}^t{b}_k^2\right),\forall t\ge 1. \end{align}

11

Lemma 2 says that the likelihood ratio associated with

θ ≠ θ 0 $\theta \ne \theta _0$

∑ k = 1 t b k 2 $\sum _{k=1}^t b_k^2$

p t $p_t$

Using Lemma 2, we can bound the rate of learning

E 0 π [ 1 − Π t ( θ 0 ) ] $\mathbb E_0^\pi [1-\Pi _t(\theta _0)]$

Theorem 1 Rate of Learning for the Finite Parameter Case

Let π be a dithering policy, and let b₀ be the positive constant defined in Lemma 1. There exist constants

c Π > 0 $c_\Pi >0$

and

c 0 < ∞ $c_0<\infty$

such that for any decreasing sequence

{ b t } $\lbrace b_t\rbrace$

with

b 1 ∈ ( 0 , b 0 ) $b_1\in (0, b_0)$

,

E 0 π 1 − Π t ( θ 0 ) ≤ c 0 exp − c Π ∑ k = 1 t b k 2 , ∀ t ≥ 1 . \begin{equation} {\mathbb{E}}_0^{\pi}\left[1-{\Pi}_t({\theta}_0)\right]\le c_0\exp \left(-c_{\Pi}\sum _{k=1}^t{b}_k^2\right),\forall t\ge 1. \end{equation}

12

Theorem 1 presents the relationship between dithering levels and the rate of learning: A larger amount of dithering leads to a faster rate of learning, and the rate depends exponentially on the cumulative amount of dithering. Intuitively, dithering enables us to choose prices sufficiently far from the confounding prices with a high probability, which provides sufficient information to learn the underlying demand model. The proof comes from the observation that the posterior belief on θ₀ is small only when the likelihood ratio for some

θ ≠ θ 0 $\theta \ne \theta _0$

We note that constants

c Π $c_\Pi$

We then make use of the rate of learning to establish an upper bound on the regret

Δ 0 π ( T ) $\Delta _0^\pi (T)$

E 0 π r 0 * − r 0 ( p t ) ≤ c 1 E 0 π ( φ ( Π t − 1 ) − p 0 * ) 2 + E 0 π ε t 2 , \begin{align} {\mathbb{E}}_0^{\pi}\left[r_0^{\ast}-r_0(p_t)\right]\le c_1\left({\mathbb{E}}_0^{\pi}\left[(\varphi ({\Pi}_{t-1})-p_0^{\ast})^2\right]+{\mathbb{E}}_0^{\pi}\left[{\varepsilon}_t^2\right]\right), \end{align}

13

c 1 ∈ ( 0 , ∞ ) $c_1\in (0, \infty )$

Theorem 2 Regret Bound for the Finite Parameter Case

For any

b > 1 c Π $b > \frac{1}{\sqrt {c_\Pi }}$

, let

b t = b t + t 0 $b_t = \frac{b}{\sqrt {t+t_0}}$

for all

t ≥ 1 $t\ge 1$

, where

t 0 ≥ 0 $t_0\ge 0$

is a constant such that

b 1 < b 0 $b_1<b_0$

, and

c Π $c_\Pi$

and b₀ are defined in Theorem 1 and Lemma 1, respectively. Then, for a dithering policy π with dithering levels

{ b t } $\lbrace b_t\rbrace$

, there exist finite constants C₁ and C₂ such that

Δ 0 π ( T ) ≤ C 1 log T + C 2 $\Delta _0^\pi (T) \le C_1\log T+C_2$

for any

T ≥ 1 $T\ge 1$

.

The choice of dithering levels

{ b t } $\lbrace b_t\rbrace$

{ b t } $\lbrace b_t\rbrace$

c Π $c_\Pi$

[ ρ min , ρ max ] $[\rho _{\min }, \rho _{\max }]$

{ b t } $\lbrace b_t\rbrace$

b t = b 1 t $b_t=\frac{b_1}{\sqrt {t}}$

t ≥ 1 $t\ge 1$

O ( log T ) $O(\log T)$

Under our policy, dithering enables us to avoid incomplete learning, but it also induces a revenue loss, which is the cost of learning. This cost can be reduced if we know in advance that the optimal prices of all potential demand models are discriminative, as discussed in the next subsection.

The discriminative case: A constant regret bound

Now we consider a special case of the finite parameter case, in which we know in advance that the optimal price of any demand model is discriminative. We call it the discriminative case. The parameter set is

Θ = { θ 0 , θ 1 , … , θ M } $\Theta = \lbrace \theta _0, \theta _1, \ldots , \theta _M\rbrace$

p m ∗ $p_m^*$

θ m ∈ Θ $\theta _m\in \Theta$

m ∈ { 0 , 1 , … , M } $m\in \lbrace 0, 1, \ldots , M\rbrace$

p m ∗ $p_m^*$

ρ ( p m ∗ , β 1 ) ≠ ρ ( p m ∗ , β 2 ) $\rho (p_m^*, \beta _1)\ne \rho (p_m^*, \beta _2)$

β 1 , β 2 ∈ Θ $\beta _1, \beta _2\in \Theta$

As discussed in Section 2.1, it is difficult to learn from prices around a confounding price, and we add perturbation in each period to increase the chance of learning. Unlike the finite parameter case, there is no need to dither in every period given the prior knowledge that the optimal prices are discriminative. We can dither only when the selected price p is close to one of the confounding prices, which is depicted by the small relative difference

| ρ ( p , θ m ) − ρ ( p , θ n ) | ∥ θ m − θ n ∥ $\frac{|\rho (p, \theta _m)-\rho (p, \theta _n)|}{\Vert \theta _m-\theta _n\Vert }$

θ m $\theta _m$

θ n $\theta _n$

Π t − 1 ( · ) $\Pi _{t-1}(\cdot )$

p t = π t ( Π t − 1 ) $p_t=\pi _t(\Pi _{t-1})$

14

φ ( · ) $\varphi (\cdot )$

We can make use of the results in Section 3.2 to show a constant bound on regret for the modified dithering policy. Intuitively, dithering enables us to learn without getting “stuck,” and after we gather sufficient information, the myopic price should be close to the optimal price with a high probability. Since the optimal price of the underlying demand model is discriminative, prices around the optimal price can provide information for learning, and there is no need to dither if these prices are chosen. Thus, we perform dithering less frequently, which reduces the cost of dithering and yields a constant regret, as formally shown below. Theorem 3 Constant Regret Bound for the Discriminative Case

For any

λ ∈ ( 0 , 1 2 ] $\lambda \in (0, \frac{1}{2}]$

b > 2 c Π $b > \frac{2}{\sqrt {c_\Pi }}$

b t = b ( t + t 0 ) − λ $b_t = b(t+t_0)^{-\lambda }$

t ≥ 1 $t\ge 1$

t 0 ≥ 0 $t_0\ge 0$

b 1 < b 0 $b_1<b_0$

c Π $c_\Pi$

{ b t } $\lbrace b_t\rbrace$

Δ 0 π ( T ) ≤ C $\Delta _0^\pi (T) \le C$

T ≥ 1 $T\ge 1$

The proof is given in Appendix D in the Supporting Information. It takes a similar approach to Theorem 2 for the finite parameter case, but it requires some modifications. As shown in (13), we bound the one‐period regret by the myopic price deviation and the cost of dithering. The difference lies in the estimate of the cost of dithering, which we bound by the rate of learning, rather than the dithering level as in Theorem 2. Under the modified dithering policy in (14), no dithering will be applied after we gather sufficient information, and the cost of dithering, therefore, depends only on the rate of learning. Recall that the myopic price deviation depends on how accurate the estimate is. It follows that the one‐period regret can be bounded above by the rate of learning. Since the same bound on the rate of learning as in Theorem 1 is guaranteed, we can tune the dithering levels to establish a constant bound on regret. Recall that for the finite parameter case, the dithering level

b t $b_t$

t − 1 2 $t^{-\frac{1}{2}}$

b t $b_t$

t − λ $t^{-\lambda }$

λ ∈ ( 0 , 1 2 ] $\lambda \in (0, \frac{1}{2}]$

Theorem 3 relies on the assumption that all optimal prices are discriminative. If the assumption is violated, the optimal price

p m ∗ $p_m^*$

ρ ( · , θ m ) $\rho (\cdot , \theta _m)$

p m ∗ $p_m^*$

p m ∗ $p_m^*$

θ m $\theta _m$

Ω ( log T ) $\Omega (\log T)$

We note that the discriminative case has been studied in Harrison et al. (2012). In particular, they consider the problem with binary demand models and a single uninformative price. They propose a discriminative policy, under which the seller chooses outside an interval of the uninformative price to avoid incomplete learning. The size of the interval controls the balance between learning and earning. They show that by carefully shrinking the size of the interval over time, the discriminative policy can achieve a constant regret bound. This approach can be extended to the finite parameter case. Although they do not show for this case, the discriminative policy can achieve the same performance guarantee as ours if the sizes of the interval are chosen properly. However, this approach cannot be applied directly to the continuous parameter case. Since there is an uncountable number of potential parameters, all prices may be confounding, and it is likely to get stuck in any one of them. Thus, we cannot simply rule out neighbors of these prices. In contrast, the dithering policy can achieve asymptotically optimal performance for the continuous parameter case, as shown in the following subsection.

The continuous parameter case: An

O ( T log T ) $O(\sqrt {T\log T})$

upper bound on regret

Now we consider the continuous parameter case, in which the parameter set Θ is compact and convex. Different from the finite parameter case, the parameter

θ ≠ θ 0 $\theta \ne \theta _0$

Ω ( T ) $\Omega (\sqrt {T})$

O ( T log T ) $O(\sqrt {T\log T})$

We first present assumptions for the continuous parameter case, which are regularity conditions on the prior distribution

Π 0 ( · ) $\Pi _0(\cdot )$

Π 0 ( S ) = 0 $\Pi _0(S)=0$

S ⊂ R N $S\subset \mathbb R^N$

S ∩ Θ = ∅ $S\cap \Theta =\emptyset$

B ( θ , η ) : = { β ∈ R N : ∥ β − θ ∥ < η } $B(\theta , \eta ):= \lbrace \beta \in \mathbb R^N: \Vert \beta -\theta \Vert <\eta \rbrace$

μ ( · ) $\mu (\cdot )$

R N $\mathbb R^N$

Assumption 2 Regularity Conditions

There exist constants

a 1 , a 2 > 0 $a_1, a_2>0$

and

ξ 0 > 0 $\xi _0>0$

such that for any

θ ∈ Θ $\theta \in \Theta$

,

η > 0 $\eta >0$

and

0 < ξ ≤ ξ 0 $0<\xi \le \xi _0$

, the prior distribution satisfies

15

Assumption 2 is common in the Bayesian statistics literature. For example, it is satisfied by any continuous probability distribution whose density function is strictly positive at θ₀. It rules out the “unlearnable” case where an infinite prior density is assigned to some

θ ≠ θ 0 $\theta \ne \theta _0$

We now introduce how we establish the regret bound. As shown in (13), the one‐period regret can be bounded above by the myopic price deviation and the cost of dithering. As we add perturbation to prices and gather sufficient information for learning, our posterior distribution tends to concentrate on the true value θ₀. Then the myopic price gets closer to the optimal price, which leads to a decreasing revenue loss from the myopic decision. We can bound the myopic price deviation by how fast the posterior distribution shrinks to θ₀. The approach so far is the same as the finite parameter case, but we need to formalize this idea in the context of a continuous posterior distribution. In particular, the rate of learning is now captured by

E 0 π [ 1 − Π t ( B ( θ 0 , η ) ) ] $\mathbb E_0^\pi [1-\Pi _t(B(\theta _0, \eta ))]$

B ( θ 0 , η ) $B(\theta _0, \eta )$

{ b t } $\lbrace b_t\rbrace$

The idea is similar to the finite parameter case, but the proof is not a straightforward extension. The main difference lies in the analysis of the rate of learning. For the finite parameter case, we can simply estimate the posterior distribution on each potential parameter

θ ≠ θ 0 $\theta \ne \theta _0$

R t ( θ , θ 0 ) $R_t(\theta , \theta _0)$

E 0 π [ 1 − Π t ( θ 0 ) ] $\mathbb E_0^\pi [1-\Pi _t(\theta _0)]$

Θ ∖ B ( θ 0 , η ) $\Theta \setminus B(\theta _0, \eta )$

Θ ∖ B ( θ 0 , η ) $\Theta \setminus B(\theta _0, \eta )$

E 0 π [ 1 − Π t ( B ( θ 0 , η ) ) ] $\mathbb E_0^\pi [1-\Pi _t(B(\theta _0, \eta ))]$

B ( θ , δ ) $B(\theta ,\delta )$

16

Π t ( B ( θ , δ ) ) $\Pi _t(B(\theta , \delta ))$

θ 0 ∉ B ( θ , δ ) $\theta _0\notin B(\theta , \delta )$

B ( θ , δ ) $B(\theta , \delta )$

R t ( θ , θ 0 ) $R_t(\theta , \theta _0)$

E 0 π [ Π t ( B ( θ , δ ) ) ] $\mathbb E_0^\pi [\Pi _t(B(\theta , \delta ))]$

B ( θ , δ ) $B(\theta , \delta )$

B ( θ 0 , η ) $B(\theta _0, \eta )$

Given the regularity conditions and the idea stated above, we proceed with the main steps of the proof. Since there is an uncountable number of parameters, the analysis of a single parameter in Lemma 2 is insufficient to bound the rate of learning. We need to extend the lemma to analyze the likelihood ratios on a small ball. More specifically, given a small ball

B ( θ , δ ) $B(\theta , \delta )$

R ¯ t ( θ , δ ) : = ∫ B ( θ , δ ) R t ( β , θ 0 ) d Π 0 ( β ) ∫ B ( θ , δ ) d Π 0 ( β ) . \begin{equation} {\bar{R}}_t(\theta ,\delta ):=\frac{\int_{B(\theta ,\delta )}{R}_t(\beta ,{\theta}_0)\mathrm{d}{\Pi}_0(\beta )}{\int_{B(\theta ,\delta )}\mathrm{d}{\Pi}_0(\beta )}. \end{equation}

17

R ¯ t ( θ , δ ) $\bar{R}_t(\theta , \delta )$

B ( θ , δ ) $B(\theta , \delta )$

R t ( θ , θ 0 ) $R_t(\theta , \theta _0)$

E 0 π [ R t ( θ , θ 0 ) ] $\mathbb E^\pi _0 [ \sqrt {R_t(\theta , \theta _0)} ]$

R ¯ t ( θ , δ ) $\bar{R}_t(\theta , \delta )$

E 0 π [ R ¯ t ( θ , δ ) ] $\mathbb E^\pi _0 [ \sqrt {\bar{R}_t(\theta , \delta )} ]$

E 0 π [ R ¯ t ( θ , δ ) ] $\mathbb E^\pi _0 [ \sqrt {\bar{R}_t(\theta , \delta )} ]$

Lemma 3

Let π be a dithering policy, and let b₀ be the positive constant defined in Lemma 1. Then, there exist constants

δ 0 > 0 $\delta _0>0$

and

c ¯ r > 0 $\bar{c}_r>0$

such that for any decreasing sequence

{ b t } $\lbrace b_t\rbrace$

with

b 1 ∈ ( 0 , b 0 ) $b_1\in (0, b_0)$

and any open ball

B ( θ , δ ) $B(\theta ,\delta )$

, the local average likelihood ratio defined in (17) satisfies

18

The approach we take to prove Lemma 3 is similar to Lemma 2, except that we need to deal with a small ball

B ( θ , δ ) $B(\theta , \delta )$

Based on the analysis of the local average likelihood ratio, we can estimate the posterior distribution on any small open ball that does not contain θ₀. For any

η > 0 $\eta >0$

Θ ∖ B ( θ 0 , η ) $\Theta \setminus B(\theta _0, \eta )$

E 0 π [ 1 − Π t ( B ( θ 0 , η ) ) ] $\mathbb E_0^\pi [ 1-\Pi _t(B(\theta _0, \eta )) ]$

Theorem 4 Rate of Learning for the Continuous Parameter Case

Let π be a dithering policy. There exists a finite constant

c ¯ 0 $\bar{c}_0$

such that for any decreasing sequence

{ b t } $\lbrace b_t\rbrace$

with

b 1 ∈ ( 0 , b 0 ) $b_1\in (0, b_0)$

and any

η > 0 $\eta >0$

,

19

where b₀ and

c ¯ r $\bar{c}_r$

are defined in Lemma 1 and Lemma 3, respectively.

Theorem 4 shows that with a substantial amount of dithering, the posterior distribution over a small neighborhood of the underlying parameter converges to 1 in expectation, and the rate of learning decreases exponentially in the total level of dithering. The bound on the rate of learning is of a higher order (with respect to t) than the one for the finite parameter case (Theorem 1), which indicates the challenge in learning for the continuous parameter case. Theorem 4 also describes how the posterior distributes given a sequence of dithering levels: The posterior distribution tends to concentrate on the true value θ₀, and its tails decay exponentially fast. As the small ball we analyze shrinks (i.e., η decreases), the upper bound increases since it is hard to tell apart θ₀ from its neighbors. We note that the constant

c ¯ 0 $\bar{c}_0$

( t η b t ) N 2 $(\frac{t}{\eta b_t})^{\frac{N}{2}}$

The main idea of the proof is as follows. Since

E 0 π [ R ¯ t ( θ , δ ) ] $\mathbb E^\pi _0 [ \sqrt {\bar{R}_t(\theta , \delta )} ]$

B ( θ , δ ) $B(\theta , \delta )$

B ( θ , δ ) $B(\theta , \delta )$

B ( θ , δ ) $B(\theta , \delta )$

Θ ∖ B ( θ 0 , η ) $\Theta \setminus B(\theta _0, \eta )$

Θ ∖ B ( θ 0 , η ) $\Theta \setminus B(\theta _0, \eta )$

{ b k } k = 1 t $\lbrace b_k\rbrace _{k=1}^t$

Banjević and Kim (2019) also use discretization and bound the numerator and denominator separately to analyze the posterior under TS in a stochastic control problem. They consider the posterior over the Hellinger neighborhood (the neighborhood with respect to the Hellinger distance) and assume that the Hellinger distance between the likelihood functions of any two different parameters can be bounded away from 0. The Hellinger distance is not applicable in our setting since it is possible that the Hellinger distance between the likelihood functions of two different parameters is zero under some action (price). Thus, we consider the natural neighborhood (with respect to the L²‐norm) in the real space

R N $\mathbb R^N$

As shown in (13), the one‐period regret can be bounded above by the myopic price deviation and the cost of dithering. As we gather information over time, the posterior distribution tends to concentrate on the underlying parameter θ₀, and the myopic price deviates less from the optimal price. Thus, we want to bound the myopic price deviation by the rate of learning to derive the regret bound. For the finite parameter case in Section 3.2, this can be achieved by applying the Implicit Function Theorem. However, now we need to deal with a continuous posterior distribution, for which the Implicit Function Theorem cannot be applied directly. We then introduce a property of the myopic policy, which bounds the myopic price deviation by the mean square error (MSE) of the posterior estimate. Lemma 4

There exists a constant

c φ ∈ ( 0 , ∞ ) $c_\varphi \in (0, \infty )$

Π t $\Pi _t$

t ≥ 1 $t\ge 1$

E 0 π ( φ ( Π t ) − p 0 * ) 2 ≤ c φ E 0 π ∫ Θ θ − θ 0 2 d Π t ( θ ) . \begin{equation} {\mathbb{E}}_0^{\pi}\left[(\varphi ({\Pi}_t)-p_0^{\ast})^2\right]\le c_{\varphi}{\mathbb{E}}_0^{\pi}\left[\int_{{\Theta}}{\left\|\theta -{\theta}_0\right\|}^2\mathrm{d}{\Pi}_t(\theta )\right]. \end{equation}

20

We now apply Lemma 4 and Theorem 4 to derive the regret bound under the dithering policy. The posterior converges to θ₀ at a faster rate as the total dithering level increases, but at the same time, dithering too much incurs a large revenue loss. This captures the tension between exploration and exploitation. By choosing a proper sequence of dithering levels, we can balance the trade‐off and further establish a regret bound of order

T log T $\sqrt {T\log T}$

Theorem 5 Regret Bound for the Continuous Parameter Case

For any

b ∈ ( 0 , b 0 ) $b\in (0, b_0)$

, let

b t = b ( log ( t + 1 ) t ) 1 4 $b_t = b (\frac{\log (t+1)}{t})^{\frac{1}{4}}$

. Then, for a dithering policy π with dithering levels

{ b t } $\lbrace b_t\rbrace$

, there exist finite constants

C ¯ 1 $\bar{C}_1$

and

C ¯ 2 $\bar{C}_2$

such that

Δ 0 π ( T ) ≤ C ¯ 1 T log T + C ¯ 2 $\Delta _0^\pi (T) \le \bar{C}_1 \sqrt {T \log T} + \bar{C}_2$

for any

T ≥ 1 $T\ge 1$

.

The proof of Theorem 5 is given in Appendix E in the Supporting Information. The high‐level idea shares some similarities as Theorem 2. Recall that the one‐period regret can be bounded above by two parts, the revenue loss from the myopic price and the cost of dithering. Lemma 4 shows that the revenue loss from the myopic decision based on

Π t ( · ) $\Pi _t(\cdot )$

η t > 0 $\eta _t>0$

Θ ∖ B ( θ 0 , η t ) $\Theta \setminus B(\theta _0, \eta _t)$

∥ θ − θ 0 ∥ ≤ η t $\Vert \theta -\theta _0\Vert \le \eta _t$

θ ∈ B ( θ 0 , η t ) $\theta \in B(\theta _0, \eta _t)$

O ( η t 2 + ( t η t b t ) N 2 exp ( − c ¯ r 4 η t 2 ∑ k = 1 t b k 2 ) ) $O(\eta _t^2+ (\frac{t}{\eta _t b_t})^{\frac{N}{2}} \exp (- \frac{\bar{c}_r}{4} \eta _t^2 \sum _{k=1}^t b_k^2 ))$

η t $\eta _t$

{ b t } $\lbrace b_t\rbrace$

{ η t } $\lbrace \eta _t\rbrace$

log t t $\sqrt {\frac{\log t}{t}}$

O ( T log T ) $O(\sqrt {T\log T})$