Dynamic Pricing and Advertising with Demand Learning

arXiv:2304.14385 · cs.GT, cs.LG · Submitted 2026-08-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Dynamic Pricing and Advertising with Demand Learning".

Jane: The paper was written by Shipra Agrawal, Yiding Feng and Wei Tang from Columbia University and Hong Kong University of Science and Technology and The Chinese University of Hong Kong.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back, everyone. Today we're digging into a fresh arXiv paper called "Dynamic Pricing and Advertising with Demand Learning." Jane, I've got to say, just the title alone got me curious.

Jane: Oh, absolutely, Tom. It's one of those papers that combines two things we usually think about separately. You have pricing, which is the classic seller question, and then you have advertising, which is how you shape what customers believe about the product.

Tom: Right, and the key twist here is that the seller doesn't just set a price. She also gets to choose how much information to reveal about the product's quality. That's the advertising part.

Jane: Exactly. And the authors — Shipra Agrawal from Columbia, Yiding Feng from HKUST, and Wei Tang from CUHK — they're asking two big questions. First, how much can advertising actually help a seller's revenue? And second, if you don't know your customers' demand, how do you learn it while also optimizing both price and advertising?

Tom: So it's not just a static model. They're thinking about a seller who's interacting with customers over time, learning as she goes.

Jane: Precisely. And the really elegant part is how they model advertising. They borrow from something called Bayesian persuasion. The seller observes the product quality, but the customers don't. So the seller can design a signal — an ad — that partially reveals that quality.

Tom: And the customers update their beliefs based on that signal. So if the seller says "this car has great fuel efficiency," the customer updates their belief about the car's overall quality.

Jane: That's the idea. And the seller can be clever about it. She doesn't have to reveal everything or nothing. She can choose any information policy in between.

Tom: Which brings us to their first big result. They define something called the "value of advertising" — the revenue gap between using advertising and not using it.

Jane: And the answer is surprisingly clean. For a broad class of valuation functions, advertising can at most double your revenue. And that bound is tight — they construct an example where you actually approach that doubling.

Tom: So advertising is powerful, but it's not magic. It can double your money, but not more than that.

Jane: Right. And that's a useful benchmark for any seller thinking about whether to invest in advertising at all. If the cost of advertising exceeds the potential gain, you know it's not worth it.

Tom: I love that they give you a concrete number. It's not vague — it's a factor of two.

Jane: And then they move to the harder question. What if you don't know your demand function? That's where the learning part comes in, and that's what we'll dig into next.

Tom: Can't wait. Let's take a quick break and come back to the learning algorithm.

Summary: Tom: We're back with "Dynamic Pricing and Advertising with Demand Learning." Jane, last segment we talked about the value of advertising being capped at two times revenue. Now let's get into the learning problem.

Jane: So the setup is this. The seller knows the product quality, but she doesn't know the distribution of customer types. Each customer has a private type that affects how much they value the product. The seller has to learn that distribution from purchase responses.

Tom: And she's doing this over time, round after round, trying to maximize total revenue.

Jane: Exactly. And the challenge is that the seller's decision space is huge. She's choosing a price and an advertising strategy, and the advertising strategy is essentially a distribution over posterior beliefs. That's an infinite-dimensional object.

Tom: So you can't just apply standard multi-armed bandit techniques. The arms aren't discrete.

Jane: Right. And there's another subtlety. They don't assume any smoothness or Lipschitz property on the demand function. That's a big deal because most learning algorithms rely on some kind of continuity to extrapolate from observed points.

Tom: So how do they get around that?

Jane: They use a model-based approach. They discretize the type space — the space of customer types — and they estimate the demand function at those discrete points. Then they use those estimates to construct an upper confidence bound on the revenue function.

Tom: And then they optimize over that upper confidence bound. That's the classic optimistic approach.

Jane: Exactly. But the clever part is how they choose the discretization. They can't just use a uniform grid, because the feasibility of advertising strategies is very sensitive to the support of the posterior distribution.

Tom: Can you give me an example of why a uniform grid fails?

Jane: Sure. Imagine the valuation is additive — customer value equals type plus quality. Then the critical type for a given price and posterior mean is just price minus that mean. If you discretize prices and types on a uniform grid, you need the posterior means to also land on that grid. But the prior distribution over qualities might not allow that.

Tom: So you could end up with no feasible advertising strategies at all.

Jane: Exactly. So instead, they construct the discretized type space by including points of the form κ(p, ω) for every discretized price and every quality. That ensures that for any feasible advertising strategy, the induced critical types land in the discretized set.

Tom: That's a clever construction. It's like building the grid around the structure of the problem.

Jane: And with that, they get a regret bound of O(T(two/three) (m log T)(one/three)), where m is the number of product qualities. That matches the known lower bound for dynamic pricing without advertising, so it's essentially optimal in terms of T.

Tom: So learning the advertising strategy doesn't add any extra cost in terms of the time horizon, as long as m is constant.

Jane: That's the key insight. The learning cost is the same as just learning the price, which is remarkable.

Tom: And they also have improved results for additive valuations. We'll get into those next.

Jane: We will. And I think those results are where things get really interesting for practical applications.

Improvements: Tom: We're still with "Dynamic Pricing and Advertising with Demand Learning." Jane, you mentioned improved results for additive valuations. What are those?

Jane: So when the valuation function is additive — customer value equals type plus quality — they get two improvements. First, if the quality space is equally spaced, like zero one or one two three the regret bound improves to O(T(two/three) (log T)(one/three)) when m is small, and O(sqrt(mT log T)) when m is large.

Tom: So for small m, you drop the dependence on m entirely.

Jane: Exactly. And for large m, the regret grows like the square root of m times T, which is much better than the general bound.

Tom: And what about the second improvement?

Jane: For arbitrary quality spaces — even continuous ones — they have a modified algorithm that achieves O(T(three/four) (log T)(one/four)) regret, independent of m.

Tom: That's a big deal. It means even if you have a huge or continuous quality space, you can still learn efficiently.

Jane: The idea is to pool nearby qualities into a smaller set. They show that this pooling doesn't lose too much revenue, and then they run the original algorithm on the reduced instance.

Tom: So it's a pre-processing step that makes the problem tractable.

Jane: Right. And the key assumption they need is that the critical type function is Lipschitz in the posterior mean. That's a mild assumption that additive valuations satisfy.

Tom: Now, Lu, you're our AI researcher. What do you make of these results?

Lu: I think the most exciting part is that they've essentially shown that advertising doesn't make the learning problem harder. That's counterintuitive — you'd think adding a whole new decision dimension would slow you down.

Jane: It does seem that way. But their discretization scheme is so well-tailored to the problem structure that the learning cost doesn't grow.

Lu: And the value of advertising result — the factor of two — that's a clean theoretical result that could have practical implications for how companies think about their advertising budgets.

Meng: From an engineering standpoint, I'm curious about the computational cost. They mention a polynomial-time algorithm for solving the optimization problem at each round. But is that practical for real-time pricing?

Jane: That's a good question. The optimization is over a discretized space, and they show it can be solved in polynomial time. But the constant factors might be large. For a small number of qualities and a reasonable discretization, it should be feasible.

Meng: And the numerical experiments they run — they compare against baselines like no-information advertising and full-information advertising. Their algorithm significantly outperforms both.

Jane: Right, and also against explore-then-commit baselines. Their algorithm consistently wins, especially as the time horizon grows.

Tom: So it's not just theory — it works in practice too.

Jane: It does. And that's a nice combination to have.

Conclusion: Tom: We're wrapping up our discussion of "Dynamic Pricing and Advertising with Demand Learning." Jane, give us the final takeaway.

Jane: The big picture is that this paper gives us a complete framework for thinking about pricing and advertising together. On the theory side, they show advertising can at most double revenue. On the learning side, they provide an algorithm that achieves near-optimal regret without assuming smoothness of demand.

Tom: And the key insight is that learning advertising doesn't cost you extra in terms of regret.

Jane: Exactly. That's the headline result. For a constant number of qualities, the regret matches the lower bound for standard dynamic pricing.

Lu: I'd add that the discretization scheme is the real technical contribution. It's carefully constructed to preserve feasibility of advertising strategies, which is the main obstacle.

Meng: And the numerical results show it's not just a theoretical curiosity. It actually outperforms simpler baselines in practice.

Tom: So who should care about this?

Jane: Anyone running an online marketplace, a subscription service, or a platform where you can control what customers see about your product. The framework gives you a principled way to decide how much to reveal and at what price.

Lalam: And from a cultural perspective, this work highlights how information itself is a strategic resource. Sellers who understand how to shape beliefs can create more value for themselves, but the factor-of-two bound shows there are limits. That's a healthy reminder that transparency and revenue can coexist.

Tom: Well said. This paper is a solid contribution to both the information design and dynamic pricing literatures.

Jane: It is. And we're excited to see what these authors do next. That's all for "Dynamic Pricing and Advertising with Demand Learning." Thanks for listening, and we'll see you at the next paper.

Tom: Take care, everyone.

Shipra Agrawal, Yiding Feng, Wei Tang

Columbia University · Hong Kong University of Science and Technology · The Chinese University of Hong Kong

cs.GT, cs.LG

Submitted: 2026-08-15

Updated: 2026-08-18

Comments: Added new results, including a new section for detailed analysis of value of advertising, a section for numerical results. Also rewrite the introduction and setting section

License: http://creativecommons.org/publicdomain/zero/1.0/

Importance score: 73/100

The gist: This paper introduces a novel pricing and advertising framework where a seller sets product prices and designs flexible advertising schemes to influence customers' valuations.

Key concepts

Value of Advertising: This is defined as the revenue gap between using advertising and not using it. The paper shows that for many valuation functions, advertising can increase revenue by at most a factor of two, which serves as a benchmark for investment decisions.
Learning Demand Distribution: The seller does not know the distribution of customer types that affect their demand. The seller must learn this distribution over time by observing purchase responses to optimize both price and advertising simultaneously.
Discretization Scheme: Since the decision space is too large for standard methods, the authors discretize the type space. They construct this grid by including points related to price and quality to ensure that any feasible advertising strategy results in critical types landing on these discrete points.

Terminology

Regret — 85× in this paper · explained in 3 episodes
Benchmark — 4× in this paper · explained in 2 episodes
Consistency — 4× in this paper · explained in 3 episodes
Adam — 2× in this paper · explained in 2 episodes
Contextual Bandits — 2× in this paper · explained in 3 episodes
Core — 2× in this paper · explained in 2 episodes
Information Asymmetry — 2× in this paper · explained in 2 episodes
Bayesian Inference — 1× in this paper · explained in 5 episodes
Decoupling — 1× in this paper · explained in 2 episodes
Theoretical Guarantees — 1× in this paper · explained in 2 episodes

Summary

This paper introduces a novel pricing and advertising framework where a seller sets product prices and designs flexible advertising schemes to influence customers' valuations. The framework models advertising as an information policy that signals product quality to customers, who then form Bayesian posterior beliefs and make purchase decisions based on expected utility. The paper investigates two main questions: (1) the value of advertising—the extent to which advertising can enhance a seller's revenue—and (2) how a seller can adaptively learn and optimize both pricing and advertising strategies without prior knowledge of the demand function.

For the first question, the paper defines the value of advertising as the revenue gap between using advertising versus not advertising. The main result is a tight characterization: the universal value of advertising is exactly 2, meaning advertising can at most double the seller's expected revenue for any prior distribution of product qualities and any type distribution. This bound is shown to be tight via a constructed instance. The proof involves decomposing optimal revenue under advertising into two components, each bounded by revenue from a no-information advertising strategy, and using an equal-revenue distribution for the lower bound.

For the second question, the paper studies the seller's dynamic pricing and advertising problem with demand uncertainty. The main result is a computationally efficient online algorithm (Algorithm 1) that achieves an optimal regret rate of O(T(2/3) (m log T)(1/3)), where m is the cardinality of the discrete product quality domain and T is the time horizon. This result requires mild regularity assumptions on the valuation function (monotonicity in quality and type, and Lipschitz continuity in type) but no Lipschitz or smoothness assumptions on the demand function. The regret lower bound of Ω(T(2/3)) from Kleinberg and Leighton (2003) validates the optimality of this algorithm with respect to time dependence.

The algorithm uses a model-based approach with a novel instance-dependent non-uniform discretization scheme. It discretizes the price space and type space using a quality-and-price-based scheme, where the type space includes points κ(p, ω) for every price p in the discretized price set and quality ω in the quality space. This ensures feasibility of advertising strategies and enables near-optimal pricing and advertising without relying on smoothness assumptions. The algorithm maintains upper confidence bound (UCB) estimates of the demand function on the discretized type space and solves an optimization problem to select price and advertising strategy each round.

The paper also obtains improved results for the special case of additive valuations (v(θ, ω) = θ + ω). For equally-spaced quality domains (e.g., 0,1 or [m]), Algorithm 1 achieves regret O(T(2/3) (log T)(1/3)) when m ≤ (T/log T)(1/3), and O(√(mT log T)) for larger m. For arbitrary discrete or continuous quality spaces, a modified algorithm (Algorithm 3) achieves expected regret O(T(3/4) (log T)(1/4)) independent of m.

Numerical experiments compare the proposed algorithm against baselines including no-information advertising, full-information advertising, and explore-then-commit algorithms. Results show the proposed algorithm significantly outperforms these baselines in both cumulative and relative regret across two settings with additive valuations.

Key technical contributions include: (1) a rounding procedure (Procedure 2) that bounds discretization error, showing the optimal price and advertising can be rounded to a feasible discretized strategy with revenue loss at most 2ε; (2) concentration bounds for demand estimates using self-normalized martingale tail inequalities; (3) proofs of revenue optimism and approximation for the UCB-based optimization; and (4) a reduction technique for large quality spaces by pooling close qualities.

Improvements for AI systems

Based on the paper, here are specific improvements I can make to AI systems, particularly in the areas of pricing, advertising, and online learning:

Improvement: I can build an AI system that jointly optimizes price and advertising strategy in real-time, without requiring prior knowledge of customer demand.

What it can do:

Adaptive learning: The system learns customer type distributions (willingness-to-pay) from purchase responses, using the paper's Algorithm 1 with a regret bound of O(T(2/3)(m log T)(1/3)).
Optimal advertising design: It automatically designs advertising schemes (information policies) that selectively disclose product quality information to maximize revenue, rather than relying on fixed strategies like full disclosure or no disclosure.
Non-parametric demand handling: It works without assuming smoothness or Lipschitz properties of the demand function, making it robust to arbitrary customer behaviors.
Efficient exploration: Uses a novel quality-and-price-dependent discretization scheme (Section 4.2) that avoids the pitfalls of uniform grids, ensuring feasible advertising strategies exist even with complex quality spaces.

Specific capability: Given a product with quality space Ω (e.g., 0,1 for binary quality) and unknown customer type distribution F, the system can:

Set prices from a discretized set P = ε, 2ε,..., U
Choose posterior mean distributions ρ that satisfy Bayes-consistency conditions
Achieve near-optimal revenue (within 2ε of optimal) after learning

These improvements enable AI systems to make smarter, more profitable decisions in real-world pricing and advertising scenarios, with rigorous theoretical guarantees on performance.

Abstract

We consider a novel pricing and advertising framework, where a seller not only sets product price but also designs flexible 'advertising schemes' to influence customers' valuation of the product. We impose no structural restriction on the seller's feasible advertising strategies and allow her to advertise the product by disclosing or concealing any information. Following the literature in information design, this fully flexible advertising can be modeled as the seller being able to choose any information policy that signals the product quality/characteristic to the customers. Customers observe the advertising signal and infer a Bayesian belief over the products. We aim to investigate two questions in this work: (1) What is the value of advertising? To what extent can advertising enhance a seller's revenue? (2) Without any apriori knowledge of the customers' demand function, how can a seller adaptively learn and optimize both pricing and advertising strategies using past purchase responses? To study the first question, we introduce and study the value of advertising - a revenue gap between using advertising vs not advertising, and we provide a crisp tight characterization for this notion for a broad family of problems. For the second question, we study the seller's dynamic pricing and advertising problem with demand uncertainty. Our main result for this question is a computationally efficient online algorithm that achieves an optimal O(T 2/3(m T) 1/3) regret rate 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 mild regularity assumptions on the valuation function, but no Lipschitz or smoothness assumption on the customers' demand function. We also obtain several improved results for the widely considered special case of additive valuations.