Dynamic Pricing and Learning with Bayesian Persuasion
Authors: Shipra Agrawal
Yiding Feng
Wei Tang
Venue: NeurIPS 2023 poster (2023)
Keywords: dynamic pricing
information design
regret minimization

Abstract: We consider a novel dynamic pricing and learning setting where in addition to setting prices of products in sequential rounds, the seller also ex-ante commits to ‘advertising schemes’. That is, in the beginning of each round the seller can decide what kind of signal they will provide to the buyer about the product’s quality upon realization. Using the popular Bayesian persuasion framework to model the effect of these signals on the buyers’ valuation and purchase responses, we formulate the problem of finding an optimal design of the advertising scheme along with a pricing scheme that maximizes the seller’s expected revenue. Without any apriori knowledge of the buyers’ demand function, our goal is to design an online algorithm that can use past purchase responses to adaptively learn the optimal pricing and advertising strategy. We study the regret of the algorithm when compared to the optimal clairvoyant price and advertising
scheme. 

Our main result is a computationally efficient online algorithm that achieves an $O(T^{2/3}(m \log T )^{1/3})$ regret bound when the valuation function is linear in the product quality. Here $m$ is the cardinality of the discrete product quality domain and $T$ is the time horizon. This result requires some natural monotonicity and Lipschitz assumptions on the valuation function, but no Lipschitz or smoothness assumption on the buyers’ demand function. For constant $m$, our result matches the regret lower bound for dynamic pricing within logarithmic factors, which is a special case of our problem. We also obtain several improved results for the widely considered special case of additive valuations, including an $\tilde{O}(T^{2/3})$ regret bound independent of $m$ when $m\le T^{1/3}$.

Dynamic Pricing and Learning with Bayesian Persuasion
Shipra Agrawal Columbia University sa3305@columbia, edu
Yiding Feng University of Chicago yidingfengbuchicago.o edu
Wei Tang
Columbia University wt23590columbia edu
Abstract
We consider a novel dynamic pricing and learning setting where in addition setting prices of products in sequential rounds, the seller also ex-ante commits to "advertising schemes'. That in the beginning of each round the seller can decide what kind of signal they will provide to the buyer about the product's 's quality upon realization. Using the popular Bayesian persuasion framework to model the effect of these signals on the buyers' valuation and purchase responses, we formulate the problem of finding an optimal design of the advertising scheme along with a pricing scheme that maximizes the seller's expected revenue. Without any apriori knowledge of the buyers' demand function, our goal to design an online algo- rithm that can use past purchase responses to adaptively learn the optimal pricing and advertising strategy. We study the regret of the algorithm when compared to the optimal clairvoyant price and advertising scheme.
Our main result is computationally efficient online algorithm that achieves an ( log To) 1/s) regret bound when the valuation function is linear in the product quality. Here m the cardinality the discrete product quality domain and T is the time horizon. This result requires some natural monotonicity and Lipschitz assumptions on the valuation function, but no Lipschitz or smoothness assumption the buyers' demand function. For constant m, result matches the regret lower bound for dynamic pricing within logarithmic factors, which is special of our problem. We also obtain several improved results for the widely considered special of additive valuations, including an Ô (T%/a) re- gret bound independent of m when m S T1/3
Introduction
Dynamic pricing is a key strategy in revenue management that allows sellers to anticipate and influ- ence demand in order to maximize revenue and/or utility. When the customer valuation and demand response for a product is apriori unknown, price variation can also be used to observe and learn the demand function in order adaptively optimize price and revenue over time. This learning and optimization problem has been a focus of much recent literature that uses exploration-exploiaatee and multi-armed bandit techniques with dynamic pricing algorithms (e.g.,
2 16 41
In practice, there another important tool available to sellers in the form of advertising, using which the sellers can inform and shape customers' valuations of product. It has been theoretically 53 54 and empirically [5 49) shown that advertisements can serve as a credible signal of the quality characteristics of the advertised product. Sellers use advertising to provide partial information about a product in order to better position the product in the market and potentially increase eustomers' chances of purchasing the product. For example, common strategy to drive
A full version of this work is
http://awwwivv..rg/////////// 14385
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

subscriptions, online newspapers may use "teaser" that selectively includes previews of some news articles that are likely to entice readers to subscribe for access to the full story; in the online used-car market, the dealer can advertise the used car by emphasizing different aspects of the car, such as fuel sfficieney/millggeunnqquu features, or selectively disclose history-report information from reputable third parties, catering to specific buyer interests; a film distributor may advertise the movie by selectively showing footage from the film.
However, advertising must be carefully designed to achieve the desired gains. At one glance up- selling or inflating the product quality by selectively disclosing only favorable information might appear as profitable advertising strategy. But such strategies carry the disadvantage of not being very effective in modifying customer beliefs as customers may not trust that the provided informa- tion accurately reflects the product's true quality. Also, the design of the advertising strategy needs to interact with the design of the pricing strategy and account for the demand function. For example, to sell highly-priced products or under heavy competition/low demand, the customer may need to be convinced of a good match through more information and thorough insights about the product characteristics. On the other hand, in markets with high demand or for very low-priced goods, the seller may get away with revealing very little information. An extreme example of this phenomenon is the concept of mystery deal boxes sold by some retailers like Amazon/Woot where the customers are not even made aware of the exact contents of the low-cost box that they are purchasing P
In this paper, we use Bayesian persuasion framework (39 to model the effect of an advertising strategy on customers' beliefs about product quality and consequently their purchase decisions. Our novel formulation combines the Bayesian persuasion model with dynamic pricing and learning in order to quantify the tradeoffs between the design of the pricing and advertising strategies and their combined impact on the revenue outcomes. Without any apriori knowledge of the demand function, our goal is to design an online algorithm that can use past customer responses to adaptively learn a joint pricing and advertising strategy that maximizes the seller's 's revenue.
Bayesian persuasion is a popular framework for information design with several different settings EN I0] We consider a Bayesian persuasion model where the
considered in the literature [39 RC sender (seller) ex-ante commits to an information policy (advertising strategy) that prescribes the distribution of signals the sender will provide to the receiver (buyer) on observing the true state of the world (product quality). The receiver, on observing the sender's signal, uses Bayes' rule to form a posterior on the state of the world. The receiver's action (purchase decision) then optimizes their expected utility under this posterior.
Problem formulation. Specifically, our dynamic pricing and advertising problem is formulated as follows. There are T sequential and discrete rounds. In each round, fresh product is offered by the seller, with a public prior distribution À on the product quality w E Q C [o, 1]. At the beginning of each round f, before observing the realized quality of the tth product, the seller commits to a price Pa E [0, U] and an advertising strategy de, where (o(w)) prescribes the distribution of signal a e Σ where Σ is an arbitrary signaling space given the realized product quality w E Ω.
A buyer arrives in each round t with private type 9g generated i.i.d. from a distribution with CDR F()) and suppor o = [o, 1]. The CDF F(-) (or equivalently the demand function D(.) è 1- 1()) fixed but unknown to the seller. For a buyer of type 0 E O, the valuation of a product with product quality w is given by function v(0,w).
The th product quality We ~ À is then realized and observed by the seller. The buyer cannot observe the realized product quality, but only a signal o, ~ (x(1(w))) provided by the seller. The buyer uses this signal along with the prior X to formulate a Bayesian posterior distribution on the product quality 2e (wloo) (a (W) A(w). The buyer then purchases the product if and only if the expected valuation under this posterior Euwnpi (-lor) [n[O,, w)] is greater than or equal to the price pt- We denote the buyer decision at time by ae E {0, 1} with a, = 1 denoting purchase.
Remark 1.1. We consider the setting where buyers use only the prior distribution and signal in the current round, and not the signals in the past rounds, to make their decisions. This is motivated by
For example, when selling the opaque products, the precise product features or characteristics are hidden from the customers [3]]
*Our results can be generalized to the setting where θ is any compact interval [0, 0] S ctt, or unbounded (see Remark 2.3
2

---

the fact that at each round, the buyer is facing fresh product, whose quality is drawn independently across time. Thus, previous signals do not carry information about the current product. Fresh products with independent qualities are common in many real-world applications such as second- hand markets, mystery boxes sold by Amazon/Woot, etc. This similar problem structure has also been studied in the online/sequential Bayesian persuasion literature with repeated interactions of sender and receivers, for example, see (61 2 25
33
58 15
A summary of the game timeline is as follows: at E (7). (1) the seller commits to a price Pt E [0, U) and an advertising strategy Φ:: (2) a buyer t with private type 0₂ ~ F arrives; (3) a product with quality ~ À is realized; the seller sends signal Ø; ~ dx(-(us) to the buyer; (4) the buyer formulates Bayesian posterior He (w]oo)) and the buyer purchases the product (denoted by d, = 1) to generate revenue Pr if and only if her expected value exceeds the price, i.e., (w--ue--oo) [o((0, w)] 2 Pt.
Our goal design an online learning algorithm that sequentially chooses the price and advertising strategy Pt, Ør in each round t based on the buyers' responses in the previous rounds, in order to op- timize total expected revenue over a time horizon T without apriori knowledge of the distribution F. Let Rev(pe, Φb) _ Espp de: Pt, di] denote the expected revenue time under the price Pt and ad- vertising strategy Φt. Here the expectation is over realizations of customer type 0g ~ F, product quality Wy À and advertising signal o; ()(-Ww)). Note that since product quality and types are i.idd across time, for any given Pt p, tz = Φ. the expected per-round revenue Rev(p, Φ) does not depend on time. Thus a static price and advertising strategy maximizes total expected revenue over the time horizon T. Therefore, we can measure the performance of an algorithm in terms of regret that compares the total expected revenue of the algorithm to that of the best static pricing and advertising strategy. We define
T
(T) & max Rev(p, Φ) p.d
Σ
Rev(pe, o+)
Our contributions. In this work, we present a computationally efficient online pricing and advertis-
ing algorithm that achieves an O (I* T) bound on the regret in time T. where m = [ the cardinality of the (discrete) product quality space. Importantly, we achieve this result without any assumptions like Lipschitz smoothness on the demand function D(-) 11 F(.). However, our results require certain assumptions on the valuation function. Following the literature, we make the common assumption that the function v00, ((),w) is linear in the product quality w. Furthermore, we assume the following monotonicity and Lipschitz properties on the valuation function. Assumption 1. Buyer's valuation function v((;)) ) satisfies:
la Fix any buyer type 0. function v(0, w) non-decreasing w.r.. quality w. lb Fix any quality w. function v(0,w) w) is increasing and 1-Lipschit w.r.t. type O.
Such assumptions are in fact common in literature and natural many economic situations where the valuation of a product increases with the product quality and buyer's type (paying ability/need). Existing literature on Bayesian persuasion/dynamie pricing often makes even stronger assumptions about the receiver's utility function. For example, both the additive functions ((0,w) = 0 + w [ef. are línear in w and satisfy
35 45 27
and the multiplicative functions v00, w) = Ow + [cf.] I Our main result is then summarized follows:
Assumption
Theorem 1.1. For any type CDF F, given a valuation function v(f,ww that is linear in product quality w and satisfies Assumption 1
Algorithm 1 with parameter ε O((mlogTTpp ///)//// has an expected regret ofO (TT) (m log 7)). Here, m. is the cardinality of the discrete quality space Q.
Furthermore, we obtain several improved results for the widely considered special case of additive valuations, i.c., for v(0,w) = + w. See Appendix B for the formal statements and analysis.
1. (Theorem B.1
Consider discrete sets Ω that are 'equally-spaced', e.g., Ω = (0. or Ω = [m]. Given such product quality space and additive valuation function, we show that the regret of Algorithm bounded by O (log //) when m < (T/logT)* //a, and by O(ym'l log T') for larger m.
'Here Lipschitz constant is for exposition simplicity, an arbitrary Lipschitz constant L can be treated similarly.
3

---

2. (Theorem B.2) For any arbitrary (discrete or continuous) product quality space Ω2 given additive valuation functions, we have a slightly modified algorithm (see Algorithm in Appendix C with an expected regret of ( (log" ()' independent of m.
When the valuation function v(., () is L-Lipschitz w.n.t type 0, our regret bound in Theorem I.1 would become O (Lm To ) and the regret bound for arbitrary space Q would become (( (L (T) 3t).
We might compare our results to the best regret bounds available for the well-studied dynamic pricing and learning problem with unlimited supply 43 R. which is special case of our problem the product quality is deterministic, i.e., m = 1, and the advertising scheme reveals no information and thus has no impact on the buyer's purchase decision. For the dynamic pricing problem lower bound of ((T*/s) on regret known + Therefore the dependence on T' in our results cannot be improved. In fact, our result matches this lower bound in the case of binary or constant size quality
space, which are common settings in information design literature 39 R 57
High-level descriptions of the proposed algorithm and challenges. Our problem can be viewed as very high dimensional combinatorial multi-armed bandit problem, where each arm is pair of a price and a feasible advertising strategy: the set of feasible advertising strategies being the set of all possible conditional distributions {o(-lw), E {2} over signal space E. As first step towards obtaining a more tractable setting, we present an equivalent reformulation of the problem which uses the observation that advertising affects the buyer's decision only via the posterior distribution over quality. By the linearity of valuation function .(..)) over product quality w, seller's choice of advertising strategy in every round can be further simplified to selecting distribution over posterior means that is subject to a feasibility constraint.
From here, the seller's 's decision space now becomes two-dimensional (a price and distribution of posterior means). Viewing seller's expected revenue as an unknown (nonlinear) function over this two-dimensional decision space, one may consider applying algorithms in contextual bandits or Lipschitz bandits to get sublinear regrets, e.g.. O(T poly(m)) regret for two-dimensional decision space if there exists a Lipschitz property of reward function relative to seller's 's decision space. How- ever, it is unclear whether one establish such Lipschitz property given that do not assume Lipschitzness or smoothness on demand function and we have complex constraints on the feasibility 'model-based approach':
of advertising space. Instead, in our algorithm purchase responses to explore the demand function over the (discretized) type space and jointly learn the optimal advertising and pricing. To explore the demand function over the one-dimensional (discretized) type space, we propose a novel discretization scheme such that it enables near-optimal price and advertising strategy even without Lipschitzness or smoothness assumption and with the complex fcasibility constraint on the advertising space. These treatments lead us to the optimal O(T"/= //) regret.
use buyers'
Related work. Our work is related to several streams of research. Below we briefly review the some of these connections.
In our setting, the seller can utilize her information advantage to design an advertisement to signal the product quality the buyer. There is a long line of research in the literature, from both empirical and theoretical perspective, dedicated to study how to use advertisement as signal to steer buyers' In our problem, we follow the literature 59 [also see the recent surveys by 30 38 IO,, where the seller can commit to an information policy that can strategically disclose product infor- mation to the buyer so that to influence buyer's 's belief about the product quality. Similar formulation for advertising has also appeared
evaluations of advertised goods (53 54 42 52 37
40
in information design, a.k.a., Bayesian persuasion
28 Our work differs from these works in several ways. First, the seller's offline problem in our setting is joint pricing and advertising problem. Second, we focus on an online setting where the seller has no apriori knowledge of the demand function and has to use past buyers" purchase responses to adaptively learn optimal pricing and advertising strategy.
19 32 34
Our problem shares similarity to the problem on sale of information in economics and computer
science literature 7 26 20 48 59 4 25) In particular, similar to the problem on sale of information, the seller, in our setting, also commits to design an information structure to reveal information about the realized state to the decision maker (i.e., buyer); and the buyer, in our setting,

---

then makes the payment based on the declared information structure, not for specific realizations of the seller's informative signals 20 48
However, different from these works, the seller in our setting is selling product with some inherent value and not just information. The valuation of the product can be shaped by providing information. This gives new interesting tradeoffs between information and revenue in our problem that are absent in the settings where only information is being sold. Moreover, in most literature of selling information, the buyers' type distribution is usually assumed to be known. We consider more practical data-driven setting where the underlying buyers' type distribution (demand function) is apriori unknown to the seller and needs to be learnt from observations.
Facing unknown buyer's preference (i.e., buyer's 's private type), the seller's dynamic advertising prob- lem also relates to the growing line of work in information design on relaxing one fundamental assumption the canonical Bayesian persuasion model the sender perfectly knows receiver's preference. The present paper joins the recent increased interests on using online learning approach to study the regret minimization when the sender repeatedly interacts with receivers 23 24
6
351
without knowing receivers' preferences. Moreover, work also conceptually relates to research
on Bayesian exploration in multi-armed bandit 46 5
50
36
which also studies an online set-
ting where one player can utilize her information advantage persuade another player to take the desired action. Our work departs from this line of work in terms of both the setting and the appli- cation domain. Particularly, the above works typically consider online setting on how to learn optimal signaling scheme whereas in our setting the optimal policy is joint pricing and signaling (advertising) scheme.
When there is no uncertainty in the product quality, the seller's problem in our setting reduces to standard dynamic pricing and learning problem with unknown non- con-paraeetric demand function
16 41 & However, given any non-trivial product quality space and prior distributions, in our problem, in addition to price, the seller needs to choose non-trivial advertising strategy in order to maximize revenue. This makes the seller's decision space high dimensional and (as we discuss in the next section) introduces significant complexities and difficulties so that the typical techniques (like uniform or adaptive discretization) used in pricing and continuous/comminnttrill multi-armed bandit literature cannot be directly applied.
43
Algorithm Design
In this section, present our main algorithm for the dynamic pricing and advertising problem. In we present an equivalent reformulation for tractable advertising strategies, then in subsection 2.2 we discuss many important challenges even after this simplification, and finally, in
subsection 2.T
subsection
we present our algorithm.
2.1 An equivalent reformulation for tractable advertising strategies
Recall that in every round, the buyer sees the offered price pt and advertising strategy & that specifies the distributions over signals dx (-lw) A that the seller will send for each possible value w of the realized product quality. After the product quality We is realized, the buyer sees a signal G, (=(w)) from the seller's declared advertising strategy. The buyer uses this signal along with the prior À to form a Bayesian posterior (-(ae) E A on the product quality. The Bayesian rational buyer then takes the action d; {0, 1}, based expected utility maximization. In particular, have = 1 if (- [o(0,, w)] 2 Ps and a₂ = 0 otherwise.
From the decision formula above, it is clear that the choice of advertising strategy affects the buyer t's decision only through the realized posterior (e(-)))). Consequently, the seller's choice of ad- vertising strategy in time t can be reduced to selecting distribution over posteriors μr, Seller's s choice can in fact be further simplified in the case where the buyer's valuation function is linear in the product quality since in that case we have
Eweps [v(0,, w)] v(Or, E Buwn = (61,,g))
where qe is the realized posterior mean qe _ Ew-nn | [w]. Here di E [0, 1] since w Ω C [0. 1]. Therefore the buyer purchases (a, 1) if and only if v vOO,, 9t) 2 Pt. As a result, we can reduce the seller's 's advertising in round to the choice of distribution (pdf) pc(-) A over posterior means.
5

---

However, the choice of Pt must be restricted to only feasible distributions of posterior means, that is, all possible distributions over posterior means that can be induced by any advertising scheme given the prior X. It is well known that the distribution over posterior means is feasible if and only if the mean-preserving contraction of the prior [7 6 This condition can be equivalently written in terms of Bayes-consi condition 39 on the conditional means p(-lw:, w E Ω. For simplicity of exposition, we consider discrete quality space Q {W1,.... Wm S [0, 1], where 0 @ < W2 ... < Wm 1 and distribution p over posterior means feasible one can construct set of conditional distributions (ps)ie[m) satisfying the following soyes-consistency condition, and vice versa 339
|St] is the cardinality of the quality space. Then,
Eie(m) {.P:(g)a; q. Vy E supp(p).
(BC)
Eigim Xepi(g)
Throughout this paper, we use the collection of distributions (pi)iE(m) satisfying (BC) a convenient way to construct feasible distributions over posterior means: p(g) = =, P=(g\>,
condition as
With the above observations, we can without loss of generality assume that seller's 's advertising strategy to directly choose distribution Pt over the posterior means that satisfies (BC without considering the design of the underlying signaling scheme {,(a[w),
We summarize the a price E [0, U] and an advertising strategy P: (PLx)iE(m) satisfying (BC); (2) a buyer t with realized; a posterior mean gr Pt is realized; (4) the buyer observes the posterior mean q:: the buyer purchases the product (a, 1) to generate revenue pt only if o(f,, qt) 2 Pt- Note that the seller knows the form of the buyer's valuation function v. Moreover, the seller observes the realized product quality wi. the realized posterior mean qr, and the buyer's purchase decision ag. but does not know type CDF F (i.e., the demand function D) and the realized buyer type 0,.
equivalent game timeline as follows: t E [7]. (1) the seller commits to
private type 0g F arrives; (3) product with quality wt
Revenue and regret. Given the new formulation, terms of the choices of Pt. t = I....,T. We define the following function s(p, q), which we refer to as the critical type for given price p and posterior mean q-
also rewrite the revenue and regret in
Definition 2.1 (Critical type). For any p E [0, U] and E [0, 1]. define function s((;-) as K k(p, ④) A
min E θ v(8.)) g) 2 p].
Now under Assumption 1b due the monotonicity of the valuation function in buyer's type, we have that given any p. g, [v q) 2 p] = 10 2 x(p, q)]. Therefore, the buyer t will purchase the product if and only if 0: 2 <(pe Qc)
Therefore, given the price, advertising = Pt = and prior distribution X, the expected revenue in any round given by 51
Rev(p, p) -= Ip 10 > x +)) - >>> (()))(((2).))ddg
Let the seller's online policy offer price pt and advertising P: time I, where Pt, Pr can depend on the history of observations/events up to time I. Then expected regret defined in Section | can be equivalently written as
Regret TRev(p", p²)
Σ E[[ev(pe, pc)]
Here, the expectation taken with respect to any randomness in the algorithm's choice of pt, Pes and .p" (pî )e{() are defined the best price and advertising strategy for a given F (and k(,,,) -) which is determined by F). Given the expression for Rev(p, p) derived above, these can be characterized by the following optimization program
p. p"
arg max Rev(p. p) P.P
Eie(m \pp((a)
(PoPT)
Exe(m) Aspi(g) =q, q [0 A A i [m].
s.t.
where the first constraint is due to BC).
'Here, we slightly abuse the notation to redefine Rev function of price and instead of price and & detined earlier.

---

2.2 Algorithm design: challenges and ideas
Challenge: high-ding diah-dimensional continuous decision space. In the last section, we obtained a con- siderable simplification of the problem by reducing the seller's advertising strategy in every round t to a distribution Pt ( over posterior means satisfying the (BC) condition. However, the decision space (a.k.a space of arms) still remains high dimensional and therefore a naive application of (uniform adaptive) discretization-bass bandit techniques, e.g. from Lipschitz bandit literature 56. would not achieve the desired results.
exploring over one-dimesnional type space. Our algorithm uses 'model-based approach" instead, where we use buyer purchase responses to develop (upper con- fidence bound) estimates of the demand model D(0) 1 - F()) on the points of a discretized type space S C O. We then use these upper confidence bounds to construct a seocewise-consten function that is an upper confidence bound (UCB) for the demand function D. Then, in each round we solve for the optimal price and advertising strategy by solving an optimization problem similar to PoPT but with the UCB demand function.
Algorithm design idea:
demand
Challenge: efficient discretization of type space. The challenge then is to design discretization scheme for the type space such that we have a) efficient learning, i.e., the discretized space can be efficiently explored to accurately estimate the demand function on those points, and b) Lipschitz property, i.e., the optimal revenue with the UCB estimate of demand function is close to the true optimal revenue as long as the estimation error on the discretized space is small.
There are two main difficulties in achieving this: (1) Lack of any amoothhess/Lipsshhhe assumption on CDF F. (2) Sensitivity of the coyessconni condition (BC). To see these difficulties, recall that given a price Pt and realized posterior mean 4t. the t buyer's purchase decision is given by a- 100 2 x(pe. [e]] thus the seller can obtain demand function estimate at point k(Pe: qt). With- out any smoothness or Lipschitz property of demand function, estimates of demand function cannot be extrapolated accurately to other points. This means that in our revenue optimization problem (estimated version of POPT). we need to find price and advertising strategy that we can only use estimates of demand function on discretized type space, say S C O. However, if we restrict to a discretized type space S, then the support of posterior mean distributions (a.k.a advertising strategy) must be restricted to the points y such that the corresponding critical types k(p, 4) are in the set S.
Unfortunately, the BC condition makes the set of fcasible advertising strategies very sensitive to their support. In particular, if we use uniform-gre siffform-riddd based discretization (which commonly used in previous dynamic pricing literature such as 43 S), it is easy to construct examples of prior distribution and valuation function such that there are no or very few feasible advertising strategies with the corresponding restricted support.
Example 2.2. Consider additive valuation function, i.e., v(0, w) + and thus to(p. q) = p- q. Consider quality space Ω = {w), )i(3)). Given small E, consider a uniform-grid based discretization 1}. If we also use a price p that is from uniform- grid
for the type space S, ie.. S = 80,8,28, based discretized price space, i.e.. p ke for some k E N then to ensure k(p, q) S, the support of advertising strategy (i.e., the distribution of the posterior means) must also be restricted within the set S. However, if the prior distribution X has negligible probabilities on qualities W1, Wa, and quality We & S. then we cannot construct any posterior distribution with the mean in the set S. Therefore, there does not exist any feasible advertising strategy.
Note that this difficulty cannot be fixed by simply modifying the discretized rype space to S SUΩ, because even then we would need to construct an advertising such that k(p, x(p,9)=1 pp=-p- q E S SUΩ Ω in the grid for all p. That would need that the support of the strategy (iee., posterior means q) is restricted to be in (ke- WikkeNt sE[3]; such posterior means again may not be achieved here.
Algorithm design idea: novel discretization scheme. Our algorithm employs a carefully-designe canlity-and-price pricedddeddeeennnn discretization scheme. The above example shows that we cannot uni- formly discretize price and type using e-grids, as we may not have any feasible advertising strategy under such discretization. And furthermore, it also shows that this difficulty cannot be fixed by sim- ply adding the m points in quality space to the discretized type space S. Instead, in our discretization scheme, we first uniformly discretize the price space to e-grid P. Then to construct a discretized
7

---

type space S, in addition to the points on an E-grid over [0. 1], we also include points {k(p, w)} for every price p P and quality E Ω2 This gives us discretized type space S of size mU We claim that our construction ensures that there exist near-optimal price and advertising strategy with support in the discretized type space S. The proof of this claim requires a careful rounding argument, which forms one of the main technical ingredients for our regret analysis in Section S
2.3 Details of the proposed algorithm
Our dynamic pricing and advertising algorithm jointly discretizes the price space and type space using the following quality and and-arice-dpeeeeee price-dependent discretiztion scheme: given parameter e, we define the following set:
P - (e, 2e,,,
S a e 1 - U ((<(WW) pE
At time f, we restrict the price and advertising strategies (pt. Pt) to the set of (p.p= (pr ke(m) such that p E P, and given price p, each conditional distribution p; has restricted support 2p defined as Op - {q: x(p.g) q) E S}. Given the price and advertising Pt, Pt, let the realized posterior mean at time be q: ~ Pt. and let the corresponding critical type be x2 & k(Pt, 9t) E [0, 1]. Then, note that the above restrictions price and advertising strategies guarantee that 24 S.
Next, compute the offered price and advertising strategy round t, we optimize an upper confi- dence bound on the revenue function that we develop using upper confidence bounds (xr),, E of the demand function computed as follows. For every type x S, let (M(x) denote the set of time rounds before time & that the induced critical type is exactly 2, and let N2(2) be the number of S.
such time rounds. That is, (2r e (T < t: k(pr, 9r) 2} No [N)
Recall that buyer's purchase decision follows a, 1 2 <(pr, 9+)) We estimate the demand
function at x as: De(x)) & EreN, a, We can now define the following UCB index: N((x)
16 Ni(x')
M(*) ( A1, EES (3) Ni(x')
DUCB(())
min D1(x') of VrSa:''a Sx
Then, for any pair of discretized price p E P and advertising strategy with discretized support for that price p = (pi A Gr,i E [m]], we define the following seller's revenue estimates:
Σ >1 J. ((l (s(p, 4))d4
UCB Rev,
(p. -
RE m
Above is well-defined since by definition k(p, q) E S for each such (p, q) E 2p. Finally, we let Pt, Pt. be the optimal solution to the following optimization problem:
(pts Pa) arg max Rev, UCB (p.p)
p.p
(PUCB)
Eigim) Aape(g)
s.t. PEP; Σigin) (pp:(g) = q. q Op: P E 2 ie [m]
We summarize our algorithm as Algorithm The main computational bottleneck of Algorithm to solve the high- -igeniimesso program puCB at each time Z (S] + As we illustrate in Proposition 2. there exists an efficient method to optimally solve this program. The proof of this result utilizes the monotoncity of the function DUCB
Proposition 2.1 (Adopted from (1)). Let be the discretization parameter for the P defined in There exists a polynomial time (in (S(U/s) algorithm that can solve the program PUCB
Proof. Since function DUCB is monotone with discontinuities at the points in the set Se when we fix price p E P, the function DUCB (x(p,-)) is also monotone with discontinuities at the points in 2p = {g: k(p, q) =.- Given a prior X, optimizing monotone function with discontinuities over all feasible advertising strategies induced from the prior subject to the constraint where the support of advertising strategies must be in the set 2, has been studied in 4 21 It has been shown that there
8

---

Algorithm 1: Algorithm for Dynamic Pricing and Advertising with Demand Learning.
Input:
Discretization parameter E.
2 For the first |S] rounds, for each E S, offer a price p with no information advertising s.t. // No information advertising provides completely uninformative signal the distribution o(-lw) signals does not depend on the realized quality w
= (w]lw)
for each round t |S| + [S] + 2....., do
For all z S, compute DUCB(2) (2) as defined in
Offer the price Pt and an advertising Pr. computed as an optimal solution to program PUCB
/* Pt,Ps satisfies x(pe,g) E for every q supp(p:).
Observe realized posterior mean Gt ~ Pt and buyer's purchase decision at E {0, 13.
Update (e)) ZES"
exists polynomial (w.r.t the number of discontinuities) algorithm based on convex programming that can find an optimal advertising strategy (see Proposition 2 in 4.. Thus. an exhaustively search over the discretized price space P can lead an optimal solution the program PUCB
We conclude this section with the following remark on the extension to unbounded type support.
Remark 2.3. Our algorithm and analysis can be extended to the case with unbounded type support (e.g., θ [0, ).)). In particular, since the price bounded by [0, U). and the quality is bounded within [0, 1]. by the monotoncity of the valuation function, vunctinon,unntionn, we know the critical types k(p, q) induced by any possible p E [0, U] and q E [0, is bounded within [r<(0. 1), xUU 0)]. Thus, an instance with unbounded type support is equivalent to an instance with bounded type support [ı<(0, 1), scUU, 0)].
3 Regret Analysis: Proof Overview of Theorem 1.1
In this section, we present our main regret bound for Algorithm as stated in Theorem Specifically, we show that for any type CDF F, given a valuation function v(0,w) that lin- ear in product quality
and satisfies Assumption & e log, T (2)), has an expected regret of O (s log t/.. Importantly, for this result we do not assume any smoothness or Lipschitz properties of distribution F.
our algorithm (Algorithm with parameter
For this result, we consider arbitrary but discrete quality space Ω of cardinality m. Later in Ap- pendix B we show improved regret bounds for the case of additive valuations and equally-spaced quality space (see Theorem B. and also extend to arbitrary large and continuous quality spaces (see Theorem B.2
Proof outline. Recall that in every round t, Algorithm D sets the price pr and advertising strategy Pe as optimal solution of program pucB that approximates the benchmark PoPT in two ways. Firstly, it restricts the price and support of advertising strategy to be in a discretized space P x (Qp. E P). Secondly, it approximates the true demand function with an upper bound DUCR Our proof consists of two main steps that bound the errors due to each of the above approximations. Due to the space limit, all missing proofs in this section are deferred to Appendix A
Step 1: bounding the discretization error using a rounding argument (see Appendix A.I To separate the discretization error from the error due to demand function estimation, we consider an intermediate optimization problem (in Appendix A.1) obtained on replacing the UCB de- mand function D with the true demand function D (while keeping the discretized space for
p). Let 7" be an optimal solution of program P We show that the revenue Rev(ž", is sufficiently close (within 2s) to the optimal revenue Rev(p",p"), This bound is obtained using careful rounding argument: we show that the optimal price p² and the optimal advertising p* can be rounded to new price p and new advertising p that satisfy
(i) feasibility (Lemma A.4 p¹ E P. supp(pt) C supp (Qpt))p))))) and

---

(ii) revenue guarantee (Lemma A.5
Rev(pt Dev(p'.p') 2 Rev(p",p") ,-') -c2.
Step 2: bounding estimation error and establishing optimism (see Appendix A.3
Next, we show that the UCB estimates of the demand function D (x), E S converge to the true demand function D with high probability, along with concentration bounds on the gap between the true and estimated function (Lemma A.7). This allows us to show that
(i) Revenue optimism (Lemma A we show that the algorithm's 's revenue estimates are (al- most) optimistic, i.e., Rev, (pr, 2 Rev(i""
Z Rev(p", p²)) 2E.
(ïi Revenue approximation (Lemma A.99 we show that the optimistic revenue estimates are close to the true revenue in round 6, with the gap between the two being inversely proportional to the number of observations, in particular, Rev, (pt.Pt) - Rev(pe:P) Pt) S
5prEgrre |log (1/(((
Finally, in Appendix A.7 we put it all together to bound the regret as stated in Theorem I. first use the above observations show that regret over each round be roughly bounded as
We
2:7 + Ep.E [Vlog /logT//N((<((ppg g)}} Then, using the constraint Exes Nr(x)) S T, we show that in the worst case, total regret over time T is bounded by O VIS/T log T). The theorem is then obtained by substituting |S| = (m/)) and optimizing
4 Conclusions and Future Direction
In this work, we use foundational information design framework, Bayesian persuasion, to model the effect of an advertising strategy customers' beliefs about product quality and consequently their purchase decisions. Our formulation combines the Bayesian persuasion model with dynamic pricing and learning to quantify the tradeoff's between the design of the pricing and advertising strategies and their combined impact on the revenue outcomes. Without any apriori knowledge of the demand function, we show that there exists efficient online policy that has the regret ( log 7)3/3) for a finite state space with cardinality This result implies that when the number of the states m is a constant, there almost no additional learning regret for the seller to additionally learn the optimal advertising compared to the dynamic pricing (without advertising) for non-parametric demand learning problem. There are interesting future directions from this work. First, in our current formulation, buyers' valuation is linear w.r.t the product states. It would be interesting to explore whether our results could be generalized to more general valuation function. Secondly, in our setting, buyer with i.i.d private type arrives each time round, and leaves the market no matter what the purchase decision is. However, in practice, buyers may strategize their purchase time for more favorable price strategic buyers and achieve efficient demand learning is another interesting future direction.
2 20 60
How to model the advertising effect with
Acknowledgements
We thank the anonymous reviewers for the helpful comments. This work was supported in part by grants 6-2020-13917 from Alfred P. Sloan Foundation and NSF CAREER award 1846792.
References
[1] Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. coaiie-tt--offience-see conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9. PMLR, 2012.
[2] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. Advances in Neural Information Processing Systems, 26, 2013.
[3] Itai Arieli and Yakov Babichenko. Private bayesian persuasion. Journal of Economic Theory, 182:185-22 117, 2019.
[4] Itai Arieli, Yakov Babichenko, Rann Smorodinsky, and Takuro Yamashita. Optimal persuasion via bi-pooling. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 641-641. 2020.
10

---

[5] Pak Hung Au and Keicchi Kawai. Competitive information disclosure by multiple senders. Games and Economic Behavior, 119:56-78,, 2020.
[6] Jobert Aumann, Michael Maschler, and Richard Stearns. Repeated games with incomplete information. MIT press, 1995.
[7] Moshe Babaioff, Robert Kleinberg, and Renato Paes Leme. Optimal mechanisms for selling information. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 92-109, 2012.
[8] Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg, and Aleksandrs Slivkins. Dynamic pric- ing with limited supply. 3(1), 2015.
[9] Dirk Bergemann and Alessandro Bonatti. Selling cookies. American Economic Journal: Mi- croeconomics, 7(3):259-99) 94, 2015.
[10] Dirk Bergemann and Stephen Morris. Information design: A unified perspective. Journal of Economic Literature, 57(1):44-95, 2019.
[11] Dirk Bergemann, Alessandro Bonatti, and Alex Smolin. The design and price of information. American economic review, 108(1):1-48, 2018.
[12] Dirk Bergemann, Yang Cai, Grigoris Velegkas, and Mingfei Zhao. Is selling complete infor- mation (approximately) optimal? arXiv preprint arXiv:2202.09013, 2022.
[13] Dirk Bergemann, Tibor Heumann, and Stephen Morris. Screening with persuasion. arXiv preprint arXiv:22/2.03360, 2022.
[14] Dirk Bergemann, Tibor Heumann, Stephen Morris, Constantine Sorokin, and Eyal Winter. Optimal information disclosure in auctions. American Economic Review: Insights, 2022.
[15] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online bayesian persuasion. In International Conference on Machine Learning, pages 2164-2183. PMLR, 2023.
[16] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 57(6): 1407-1100, 2009.
[17] David A Blackwell and Meyer A Girshick. Theory of games and statistical decisions. Courier Corporation, 1979.
[18] Alessandro Bonatti, Munther Dahleh, Thibaut Horel, and Amir Nouripour. Selling information in competitive environments. arXiv preprint arXiv:2202.08780 2022.
[19] Peter Bro Miltersen and Or Sheffet. Send mixed signals: earn more, work less. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 234-247, 2012.
[20] Yang Cai and Grigoris Velegkas. How to sell information optimally: An algorithmic study. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference, volume 185, 2021.
[21] Ozan Candogan. Persuasion in networks: Public signals and k-cores. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 133-134, 2019.
[22] Ozan Candogan and Philipp Strack. Optimal disclosure of information to a privately informed receiver. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 263-263, 2021.
[23] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian per- suasion. Advances in Neural Information Processing Systems, 33, 2020.
[24] Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online bayesian persuasion. In International Conference on Machine Learning, pages 1314-1323.
PMLR, 2021.
11

---

[25] Yanlin Chen and Jun Zhang. Signalling by bayesian persuasion and pricing strategy. The Economic Journal, 1306628);77--007, 2020.
[26] Yiling Chen, Haifeng Xu, and Shuran Zheng. Selling information through consulting. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2412-2431. SIAM, 2020.
[27] Davide Crapis, Bar Ifrach, Costis Maglaras, and Marco Scarsini. Monopoly pricing in the presence of social learning. Management Science, 63 ((11)):5566-608 2017.
[28) Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu. Competitive information design for pandora's ' box. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 353-381. SIAM, 2023.
[29] Alexey Drutsa. Optimal non-parametric learning in repeated contextual auctions with strategic buyer. In International Conference on Machine Learning, pages 2668-2677. PMLR, 2020.
[30] Shaddin Dughmi. Algorithmic information structure design: a survey. ACM SIGecom Ex-
changes, 15(2):2-24, 2017.
[31] Adam Elmachtoub and Michael Hamilton. Management Science, 67(6):4686 2021.
The power of opaque products in pricing-
[32] Yuval Emek, Michal Feldman, Iftah Gamzu, Renato PaesLeme, and Moshe Tennenholtz. Sig- naling schemes for revenue maximization. ACM Transactions on Economics and Computation (TEAC), 2(2):1-19, 2014.
[33] Yiding Feng, Wei Tang, and Haifeng Xu. Online bayesian recommendation with regret. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 818-819, 2022.
[34] Ilwoo Hwang, Kyungmin Kim, and Raphael Boleslavsky. Competitive advertising and pricing. 2019.
[35] Bar Ifrach, Costis Maglaras, Marco Scarsini, and Anna Zseleva. Bayesian social learning from consumer reviews. Operations Research, 120-):1209-1221 2019.
[36] Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing exploration with selective data disclosure. Proceedings of the 21st ACM Conference on Economics and Computation, pages 647-648, 2020.
[37] Kenneth Judd and Michael Riordan. Price and quality new product monopoly. The Review of Economic Studies, 61(4):773-789, 1994.
[38] Emir Kamenica. Bayesian persuasion and information design. Annual Review of Economics, 11:249-211 202, 2019.
[39] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2500-2155 2011.
[40] Kei Kawai, Ken Onishi, and Kosuke Uetake. Signaling in online credit markets. Journal of Political Economy, 0000600000000, 2022.
[41] N Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymp- totically optimal semi-myopic policies. Operations research, 124) 2014.
[42] Richard E Kihlstrom and Michael H Riordan. Advertising as signal. Journal of Political Economy, 9273):427-450 1984.
[43] Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds regret for online posted-price auctions. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594-605. IEEE, 2003,
12

---

[44] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681-690 2008.
bandits in metric spaces. In
[45] Anton Kolotilin, Tymofiy Mylovanov, Andriy Zapechelnyuk, and Ming Li. Persuasion of privately informed receiver. Econometrica, 85(6):1949-1964 2017.
[46] Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "wisdom of the crowd". Journal of Political Economy, 122(5):988-100 2014.
[47] Yingkai Li. Selling data an agent with endogenous information. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 664-665, 2022.
[48] Shuze Liu, Weiran Shen, and Haifeng Xu. Optimal pricing of information. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 693-693, 2021.
[49] Puneet Manchanda, Jean-Pierre Dubé, Khim Yong Goh, and Pradeep K Chintagunta. The effect of banner advertising internet purchasing. Journal of Marketing Research, 43(1):
98 98-108, 2006.
[50] Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatibee bandit exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Com- putation, pages 565-582, 2015.
[51] Yishay Mansour, Alex Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian explo- ration: Incentivizing exploration bayesian games. Operations Research, 70(2): 105- 2022.
[52] Paul Milgrom and John Roberts. Price and advertising signals of product quality. Journal of political economy, 94(4):796-821 1986.
[53] Phillip Nelson. Information and consumer behavior. Journal of political economy, 78(2):
311-329, 1970.
[54] Phillip Nelson. Advertising information. Journal of political economy, 8244)7729-75 1974.
[55] Navdeep S Sahni and Harikesh S Nair. Does advertising serve as a signal? evidence from field experiment mobile search. The Review of Economic Studies, 87(3):1529-15644 2020.
[56] Aleksandrs Slivkins. Contextual bandits with similarity information. Proceedings of the 24th annual Conference On Learning Theory, pages 679-702. JMLR Workshop and Confer- ence Proceedings, 2011.
[57] Wei Tang and Chien-Ju Ho. On the bayesian rational assumption in information design. In Proceedings of the AAAI Conference Human Computation and Crowdsourcinng volume 9, pages 120-130, 2021.
[58) Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient rein- forcement learning. In Proceedings of the 23th ACM Conference on Economics and Computa- tion, 2022.
[59] Shuran Zheng and Yiling Chen. Optimal advertising for information products. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 888-906, 2021.
[60] Anton Zhiyanov and Alexey Drutsa. Bisection- pricing for repeated contextual tions against strategic buyer. In International Conference on Machine Learning, pages 14469- 11480. PMLR, 2020.
[61] You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to persuade the fly: Robustness against ignorance. In Proceedings of the 22nd ACM Conference on Economics and Computa- lion, pages 927-928, 2021.
13


Reviews:
[{"review_id": "EGmt3ljcfw", "reviewer": "Reviewer_kmXq", "summary": "In this work, the authors study a novel setup of repeated posted-price auctions, where a single seller deals with a single myopic buyer (or, equiv, iid new buyer in each round). In each round, a new good is offered and has characteristics that affect buyer valuation (so, goods are not equal between rounds). The novelty of the setup consists in introducing a new interaction step, where the seller reveals characteristics of each good through some signals that might improve perception of the buyer. The buyer is aware of this step, which is referred to as advertising (due to analogy with cases in practice).\nSo, in each round the seller submits two inputs (price, advertising signal), while the buyer reacts by a decision: accept or reject the price for this good. \n\nThe authors clearly argue why this setup differs from earlier considered ones (either price-only, or advertising-only). They provide a novel algorithm (which is announced in advance. before the game) and prove that this algorithm has regret upper bound which is slightly above the lower bound by the factor of log T (for the setup without advertising).", "questions": "A. Setting questions and other matter stuff:\n\n1. Line 70 about definition of Omega: Any extentions to multidimentional \\Omega?\n\n2. Footnote 3: “ This is motivated by the fact that at each round, the buyer is facing a fresh product, whose quality is drawn independently across time.” I would add that this is not just because of it. But, also because, in each round, we consider a fresh buyer (myopic to the other rounds). This setting might be changed even in the case of different products. For instance, see settings with a single buyer that makes strategic decisions to optimize his/her utility over all rounds in the cases of different products: [Zhiyanov2020, Drutsa2020] (by the way, these works are extensions of the work [39] Kleinberg et al 2003 you are citing).\nSo, I would suggest upgrading your footnote by adding these thoughts and probably indicate some future work about injecting the strategic buyer in your setting.\n\n3. Lines 96-97 “and a static price and advertising strategy maximizes total expected revenue over the time horizon T” Hard to parse this sentence. It sounds like, static (p, \\phi) are the best solutions over all possible ({p_t} , {\\phi_t}). The authors seem to state that these are the best among static p_t, \\phi_t. If yes, please reformulate the sentence to be clearer\n\n4. Formula after Line 99: \nOver what is expectation taken right after the \\Sum sign? It looks like all randomness is under the hood of Rev()..\nOr, ... do we expect mixed (non-pure) strategies of the Seller?\n\n5. Line 102 “of the (discrete) product quality space.” What will be when \\Omega is not discrete? E.g., continuous?\n\n6. Footnote 4 “ arbitrary Lipschitz constant can be treated similarly.” It would be nice to understand how this constant participates in the upper bound .. E.g. in workds [Mao2018, Drutsa2020], it plays some notable role and shows severe dependance on the degree of Lipschitz assumption. Is it true in your case?\n\n7. Algorithm 1. Line 5. “ computed as an optimal solution to program P^{UCB}.” What are the costs for finding optimal solution in P_t^{UCB}? Overall, it would be nice to clearly address complexity of the algorithm in a separate paragraph in the text with discussions. \n\n\nB. Presentation/wording issues:\n\n1. Lines 14-17. It is written “the valuation function is linear in the product quality” and “This result requires some natural monotonicity and Lipschitz assumptions on the valuation function…”. It is unclear: linear valuation is Lipschitz by definition... Or result is about non-parametric valuation.. ?\nLater, in the main text, I found that valuation depends on 2 parameters, where properties on linearity and Lipschitz are on different parameters. I suggest rewriting Line 17 to make it clearer from abstract. \n\n2. Structure of the paper. I suggest to improve structure of the work. At least\n- By splitting Inroduction in separate Sections: Intro, Problem formulation (statement)\n- By adding conclusion\n\n3. Line 70 “with a public prior distribution \\lambda on.. ” Hard to parse. Only in Line 78, I've got that lambda is ex-ante for the whole game play (before round 1). \n\n4. Lines 81-82: “if the expected valuation” Why is this the reasonable way to decide? I mean this way to transform quality distribution to a number for comparison with price? Maybe, Median, Moda, Quantiles are better? \nIs it because Buyer maximizes some utility? If yes, what is the utility in this case?\nLater I found the answer in Lines 215-217. However, I'd suggest improving the text in Page2 by adding the info that the setting is about Bayesian rational buyer\n\n5. Line 287: “we can only use estimates of demand function on a discretized type space, say S” Hard to read. Please, simplify. \n\n6. Algorithm 1. Line 2 “any no”. I do not understand \"any no\". \n\n7. Lines 353-358 (and many other earlier): Text here repeats earlier stated (several times) assumptions and reference of results to Appendices. \nIt is better to save space and show more details on proofs, limitations, computational complexity, and conclusions...\n\n\nC. Minor issues:\n- Lines 19-20 “the regret lower bound for dynamic pricing within logarithmic factors, which is a special case of our problem.” Wording: hard to parse what is the special case: factor or pricing. Please, rewrite\n- Line 167: “the these” -> “these”?\n- No line counts between Lines 217-218\n- Line 286: “to solve to find” -> “to find”?\n\n\n\nLITERATURE: \n[Mao2018] Mao,  Leme, and Schneider “Contextual pricing for lipschitz buyers” NeurIPS 2018.\n[Zhiyanov2020] Zhiyanov and Drutsa \"Bisection-based pricing for repeated contextual auctions against strategic buyer.\" ICML  2020.\n[Drutsa2020] Drutsa \"Optimal non-parametric learning in repeated contextual auctions with strategic buyer.\" ICML 2020.\n\n\n\n\n========\n\nAFTER REBUTTAL\nI thank the authors for answering several questions from my list. I hope that the answers will be reflected and fully addressed in the new revision of the work - including those questions that remain without comments from the authors.", "limitations": "No. I would suggest adding a paragraph about computational complexity analysis.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- novel setup in the area of repeated auctions with plenty opportunity for future work\n- new algorithm with theoretical guarantees \n- easy understandable basic ideas behind the proofs", "weaknesses": "- presentation (a lot of space for improvement)\n- some questions to setup and setting\n- lack of analysis and discussion of proposed algorithm (computational complexity, limitations in practice, ...)\n(see “Questions” for details)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, we will incorporate your comments and presentation suggestions in the revision, and also adequately discuss the relevance to the pointed literature. We below respond the important questions:\n\n**Weakness 3 and Q7 (Complexity of the algorithm):**\nWe kindly remind the reviewer that we indeed mention the complexity of our algorithm (please see Line 340-342 right below the Algorithm 1). In particular, it can be shown that the empirical program $P_t^{\\text{UCB}}$ is a convex program where the Bayes-constraints can be reformulated as convex constraints (Arieli, Itai, et al. EC’20, Candogan EC’19), thus an efficient algorithmic solution exists to solve $P_t^{\\text{UCB}}$. We make this argument more formally in Proposition A.1 (due to space limit, we put it in the appendix). We will move it to the main text in the revision.\n\n**Q5:** In Line 102, the regret bound $O(T^{2/3}(m\\log T)^{1/3})$ holds for discrete state space where $m$ is the number of states. For continuous state space, we have regret $\\tilde{O}(T^{3/4})$ (please see Line 125-127 and our Theorem C.2). \n\n**Q6 (Lipschitz constant):** With the Lipschitz constant $L$ of the value function $|v(\\theta_1, \\omega)-v(\\theta_2, \\omega)|\\le L|\\theta_1-\\theta_2|$, our regret bound will be $\\tilde{O}(T^{2/3}(Lm)^{1/3})$ for discrete state space, and be $\\tilde{O}(L^{1/4}T^{3/4})$ for continuous state space. We will clarify it in the revision. "}, {"review_id": "qr10WlaQ0p", "reviewer": "Reviewer_78HV", "summary": "The paper extends the traditional dynamic pricing model (e.g. Kleinberg and Leighton) to also include product quality. In each period, we get both a random type of the buyer as well as a random quality of the product. The seller can employ an advertising strategy, which is a mapping from product quality to a signal, which must be decided in each step before the signal is realized. To be more precise, in each period:\n* buyer type is drawn $\\theta_t \\sim F$\n* seller decides on a signaling scheme mapping item quality $\\omega$ to a signal $\\sigma$\n* seller also decides on a price $p_t$ for the product\n* item quality $\\omega \\sim \\lambda$ is realized. Signal $\\sigma$ is computed and sent to the buyer:\n* buyer decides to purchase if $\\mathbb{E}[\\theta, \\omega) \\mid \\sigma] \\geq p_t$\n\n\nThe seller knows all parameters of the model except $F$;. The goal of the seller is to learn $F$ and compete against the algorithm that knows $F$ and chooses the prices and advertising strategies optimally in each period. Naive MAB approaches are too high dimensional, so the authors use the following clever idea: define the threshold type $\\kappa(p_t, \\rho_t)$ which is the threshold specifying above which types they buy. Now, If we choose the signaling scheme carefully we can observe whether $\\theta$ was above or below $\\kappa(p_t, \\rho_t)$. with that, we can build an estimate of $F$. The question now becomes discretizing the prices and advertising strategies appropriately. Once the estimate is built, we use the UCB estimates to solve a program and allocate according to that.\n\nThe algorithm has $O(T^{2/3})$ regret due to two effects: (i) price discretization; (ii) explore and exploit.", "questions": "See my comments in the last box.", "limitations": "No concerns.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Interesting model mixing persuasion and pricing. This is a nice and natural extension of the pricing model.\n\n* There is a clever idea: instead of discretizing in the space of signals, we discretize prices and estimate $F$ directly.\n\n* The results match the lower bound of Kleinberg-Leighton. On that, the authors should probably discuss more why the Kleinberg-Leighton lower bound applies to this problem. I imagine their setting corresponds to known quality, so we don’t need to signal anything. I recommend saying this explicitly.\n", "weaknesses": "* In terms of motivation, it is unclear that we change the advertising so fast. Typically it takes a few iterations with the signaling scheme for a buyer to learn the mapping from signals to actions. Now that the buyer is seeing a new one in each period, I don't see how this would translate to a practical situation. \n\n\n* Mention \"linear\" in Assumption 1a to make it clear. From reading assumption 1, I was under the impression that we were just assuming $v$ to be monotone on $\\omega$. Btw: I think you mean \"affine\" instead of linear. The function $v(\\theta, \\omega) = \\theta + \\omega$ is not linear (in the usual definition of linear)\n\n* I think Explore-then-Exploit are underwhelming in terms of ML algorithms. You can always learn the parameters in an explore phase and just optimize. There are non-trivial many aspects of the error analysis, but in terms of algorithmic techniques, I found it to be limited.\n\n* The paper gets too long to get to the actual algorithm with many discussions that could be done much faster. For example, teh entire discussion in Section 2.1 is the Splitting Lemma of Aumann-Maschler.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, we will incorporate your comments and presentation suggestions in the revision. We below mainly address the technique comment:\n\n**Weakness 3 (Why not Explore-then-Exploit algorithm):**\n\nWe believe the regret achievable by any \"Explore-then-Exploit\" algorithm is $\\tilde{O}(T^{3/4}m^{1/4})$, which is suboptimal compared to our algorithm’s regret $\\tilde{O}(T^{2/3}m^{1/3})$. The suboptimality of \"Explore-then-Exploit\" can be demonstrated as follows:\n1. **In exploration phase**: By fixing a pre-specified discretized type space $\\mathcal{S}$ and choosing different prices with no-information advertising, we can obtain estimates for the demand function on points in $\\mathcal{S}$. If we can have a reasonably good estimate for the demand function $D$ on the points in $\\mathcal{S}$, then we can construct an approximately-optimal pricing and advertising strategy, and use it in exploitation phase. The per-round regret in this phase is constant, with a total of $|\\mathcal{S}|\\cdot \\frac{\\log T}{\\varepsilon^2}$ rounds (by Hoeffding inequality) to obtain $\\varepsilon$-accurate estimated demand, i.e., $|D^{\\text{estimated}}(x) - D(x)|\\le\\varepsilon, \\forall x\\in\\mathcal{S}$;\n2. **In exploitation phase**: To get an $\\varepsilon$-approximate optimal pricing and advertising strategy using the estimated demand, we can construct the set $\\mathcal{S}$ as proposed in the paper, yielding $|\\mathcal{S}|=\\frac{m}{\\varepsilon}$.\n\nThus, the total regrets is: $\\frac{m}{\\varepsilon}\\cdot \\frac{\\log T}{\\varepsilon^2} + \\varepsilon \\cdot \\left(T - \\frac{m}{\\varepsilon}\\cdot\\frac{\\log T}{\\varepsilon^2}\\right)=\\tilde{O}(T^{3/4}m^{1/4})$ with optimizing $\\varepsilon = (m/T)^{1/4}$. "}, {"review_id": "AS3dnlItGo", "reviewer": "Reviewer_mNn4", "summary": "The authors consider an online single product dynamic pricing product, where a buyer's purchase decision is not only influenced by the offered price from the selling, but also depends on the advertising strategy used by the seller. The authors formalized the latter via the model of Bayesian persuasion framework, which is a well establish model in the economic literature (to the best of my knowledge). In the only problem, the seller is uncertain about the type distribution of a customer, but the seller knows the probability distribution on the quality of a product (which is a random variable). The authors' main results is the design and analysis of a UCB algorithm, where the authors crucially use a mild assumption on the customer's utility to reduce the size of decision variables on the advertising strategy. The regret  bound derived is nearly tight (module a factor of $m^{1/3}$, where $m$ is the number of possible quality. )", "questions": "(1) Can the authors explicit confirm if the seller possesses the knowledge on $\\mu_t$, the posterior distribution of time $t$ customer's perceived quality conditional on an advertisement strategy? Just to double confirm my understanding, in the reduction from selecting $\\sigma_t$ to the selection of $\\rho_t$ which is a uni-variate probability distribution, the reduction involves considering the mean of a mixture of different $\\mu_t$ distribution. Thus, in order to arrive with the desired $\\rho_t$, we need to have the correct mixture, which involves knowing $\\mu_t$. Can I please check if my understanding above is correct?\n\n(2) Can the author improve the dependence on $T$ if we have a discrete set of (say $K$) prices?\n\n(3) If my understanding in Question (1) is correct, could there be a way to extend the framework to the case when $\\mu_t$ is stationary across time but not known to the seller, or is there a $\\Omega(T)$ regret lower bound due to the insufficiency in the information in the outcome?\n\n", "limitations": "There is no negative societal impact, this is a theoretical work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The setting and the algorithm design, analysis seem novel, and this is the first piece of work on online revenue mgmt with Bayesian persuasion to my knowledge. \n\n- Despite the complexity of the set up and the algorithm, the authors provide enough intuitions for readers to understand the content, and I feel that the proposed work could inspire further interest in other pricing problems. \n\n- The whole algorithm framework is well crafted such that the tightness on $T$ is achieved. ", "weaknesses": "- If I understand the model set up correctly (please also see Question (1) in \"Questions\"), the seller seems to need to know $\\mu_t$ that relates to the time t customer's perception on a product's quality given the seller's advertising strategy. This assumption could appear a bit strong, since in most online pricing setting the learning agent should be uncertain about a customer's purchase characteristics.\n\n- I find the modeling assumption on the product quality being random a little strange. Putting myself as a seller who can observe the quality of a product before an action, it could seem natural for myself to sell products of high quality first (let say if I see a low quality product, then I will just forgo it, and repeat until I can find a high quality product for the customer) in order to yield a higher revenue? If the seller could not observe the quality of a product, I do find modeling the unseen quality as a random variable reasonable.\n\n- There is a looseness in $m$, but I regard it as a minor weakness given the complexity of the problem.\n\n- There is a lack of numerical results, which could yield some immediate intuitions. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, we will incorporate your comments in the revision. We below respond the questions as follows:\n\n**Q1 and Q3 (The seller’s knowledge of buyer’s posterior belief $\\mu_t$):**\nThe reviewer is correct that the seller knows the (realized) buyer's posterior belief $\\mu_t$. We would like to clarify that this knowledge isn't assumed but derived. Specifically, in our setting, seller designs the signaling scheme and can observe the realized signal $\\sigma_t$, and the incoming buyer shares the same prior distribution with the seller (i.e., the prior does not depend on buyer’s private type). Thus, the seller can infer the buyer’s Bayesian posterior belief $\\mu_t$ upon realizing a signal $\\sigma_t$. We appreciate the reviewer's insight and will make it more clear in our revision. \n      \n\n**Weakness 2 (Modeling assumption on random quality):**\nWe are not sure if we completely understand reviewer’s comment. We would like to clarify that it is a priori unknown whether a product quality is particularly low or high as the buyer’s valuation also depends on buyer’s private type, which is unknown to the seller, e.g., a seemingly ”low“ quality product could still lead to a high valuation if buyer’s type is sufficiently high, and thus the seller can still sell this ”low“ quality product. Please let us know if the above response do not answer the question, and we will be happy to offer more clarifications.\n           \n\n**Q2 (Potential improvement for $K$ prices):**\nIf the seller only has $K$ prices, we think that the regret bound cannot be immediately improved based on our current analysis. The challenge is as follows: even though the seller has only $K$ prices, the seller’s problem is still a continuous-armed bandit problem due to the rich space of the possible advertising strategies (thus a carefully designed discretization over type space is still needed), we will add discussions in the revision."}, {"review_id": "l9rLcyLZ5u", "reviewer": "Reviewer_khHp", "summary": "This work focuses on advertising and selling markets under the Bayesian persuasion framework. On the one hand, this paper models the effect of the advertisement strategy on customers’ beliefs and purchase decisions. On the other hand, the authors also address the problem of online learning the optimal advertisement strategy via learning the buyers’ type distribution and show $O(T^{2/3} m^{1/3})$ regret for discrete quality space and $O(T^{3/4})$ regret for arbitrary quality space. ", "questions": "1. Are the regret bounds of $O(T^{2/3})$ and $O(T^{3/4})$ tight for discrete and continuous quality spaces, respectively?\n2. Is there a deeper understanding of the optimization program P_opt? Can it provide insights into the phenomenon where revealing more or less information about the product can sometimes lead to increased revenue?", "limitations": "No concerns here.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem and model discussed in this paper are intriguing, and the authors devise a novel quality-and-price-dependent discretization scheme for proving the learning result. Notably, the learning process only necessitates observations of the buyers' purchase decisions, eliminating the need for explicit knowledge of their individual types. This work may be of interest to the community. ", "weaknesses": "Is the value function required to be linear in $\\omega$? I notice that using $q$ for simplification relies on this linearity assumption. Additionally, in order to determine the critical type, the seller would typically need prior knowledge of the buyers' value function, which may not always be feasible. Is it possible to relax this requirement within this framework?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, we will incorporate your comments in the revision. We start with addressing the technique comment:\n\n**Q1 (Tightness of $O(T^{2/3})$ and $O(T^{3/4})$ for discrete and continuous quality spaces):**\nOur regret $O(T^{2/3})$ for discrete quality space is tight, please see the discussions from Line 129-132. However, we do not have a matching lower bound for continuous quality space, and we leave it as an interesting future work direction. \n\n**Weakness (assumptions):**\nIn current work, we assume the buyer’s value is linear w.r.t the quality. This assumption is widely-adopted in current literature and is also natural in many economic applications (see Line 114 for references). We believe that the assumption on requiring knowing valuation function can be relaxed by further using certain bandit learning techniques. Fully relaxing these assumptions is an interesting technical direction for future work. \n      \n\n**Q2 (Understanding program P_opt):**\nWe have some examples showing that partial information revealing can indeed increase the seller’s revenue. In particular, we can derive closed-form characterization for the optimal pricing and advertising strategy, and use it to show some qualitatively results under some canonical instances (e.g., binary quality, log-concave type distributions). However, we currently do not have closed-form characterization regarding program $P_\\text{opt}$ for general instances. We will add discussions in the revision. "}, {"review_id": "fjDSgGouQb", "reviewer": "Reviewer_p9NT", "summary": "The paper studies a dynamic pricing model augmented by advertisement campaigns. The problem is framed in a Bayesian persuasion framework, where the authors focus on the online learning version of the model in which the agent is not aware of buyer the demand function from which its types are drawn.", "questions": "1) would revelation like principle hold in this context? Could the space of signals be made binary as the action set or not? A brief discussion on this would be interesting for the BP readers.\n2) The types in this problem are stochastic. What if they would be drawn by an adversary? Most of the online BP literature studies the adversarial problem.\n3) the authors cite a T^{2/3} lower bound for the dynamic pricing problem. I guess that the your extended model reduces to the standard DP model when the utilities are zero sum and thus the sender commits to uniformly random signalling schemes and thus the posterior would be equal to the prior. Am I correct? If so, I would like to be convinced that zero sum utilities between seller and buyer can be achieved in your model. Moreover more recent UB for the online BP problem with adversarial types have been found, and guarantee a sqrt(T) regret. The work I’m referencing is [Bernasconi, Martino, et al. \"Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion.\" (2023).] which I think should be discussed.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper studies an interesting model of dynamic pricing, which leans on the Bayesian persuasion framework. Due to the continuity/size of the action space, standard techniques cannot be applied and the results presented seems technically interesting.\nMoreover the paper is mostly clear and easy to follow and does a good job at motivating the model.", "weaknesses": "I found the description of the discretisation (line 308) a bit hard to follow. A little bit more intuitive discussion on this would be appreciated  for this part.\nSee the question on the lower bound in the Question section of the review\nIf convinced on this point I’m willing to revise my score", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, we will incorporate your comments and presentation suggestions in the revision. We will respond the questions as follows:\n\n**Q1 (Revelation principle on binary signals):**\nIf buyer’s type were fixed, then binary-signal would indeed suffice, as known from previous literature. However, in our model where a buyer's private type is randomly drawn from a distribution, binary-signal does not suffice to achieve optimal advertising in this Bayesian setting. We can show that the gap between the revenue using the binary-signal and the optimal revenue can be large. \n\nAs shown in KG-AER’11, when the receiver (i.e, buyer) has private information (i.e., type), the revelation principle claims that there exists a mechanism that the receiver will find it optimal to truthfully reveal their private type to the sender, and then the sender will issue a binary signal to the receiver (given receiver has binary action). Notably, under this mechanism, the buyer will firstly report her private type, which is not the model considered in this work. \n\nThank you for the suggestion, and we will provide further clarity on this point in our revision.\n        \n\n**Q2 (Adversary buyer valuations):**\nIn this work, we focus on stochastic setting. Though this is beyond the scope of current paper, we agree with the reviewer that adversary valuation is certainly an interesting direction to explore in future work.\n\n**Q3 (Lower bound and whether zero sum utilities between seller and buyer):**\nThe lower bound $\\Omega(T^{2/3})$ holds since our setting can recover the standard dynamic pricing problem (Kleinberg and Leighton, FOCS’03) when the prior distribution of the product quality is a point mass, i.e., the product quality is known to both players. In that case, the seller only needs to decide the price, and any signaling scheme does not affect the outcome. Therefore, the seller’s problem is a pure DP with a regret lower bound $\\Omega(T^{2/3})$. \n\nWe are not sure if we understand what reviewer is referring to as “zero sum utilities”. As in dynamic pricing, in our setting we are optimizing only the seller’s objective which is the revenue function. Buyer is responding by maximizing the valuation function, which depends only on private type (as in dynamic pricing) when the product quality is fixed (i.e. when prior distribution is a point mass). Thus, the connection of our model to the zero-sum game is unclear. Please let us know if the above response do not answer the question, and we will be happy to offer more clarifications.\n\nThank you for pointing to that reference, we will discuss its relevance in the revision.  "}]

Author rebuttal:

Meta-review: The reviewing team was in agreement positive about this paper. All reviewers liked the contribution of the paper, and made some comments about improving the presentation which I believe can be implemented for a final version. I also liked that the paper's upper bound for the discrete case is *tight* to O(T^{2/3}), despite the fact that this can be achieved by an explore-then-commit algorithm.
Decision: Accept (poster)