📊 statistics

Online Price Competition under Generalized Linear Demands

This paper proposes a novel decentralized pricing policy, PML-GLUCB, for sequential online price competition among $N$ sellers with generalized linear demands, achieving optimal $\widetilde{O}(\sqrt{T})$ regret without requiring coordinated exploration phases while accommodating unknown parameters and both binary and real-valued demand observations.

Original authors: Daniele Bracale, Moulinath Banerjee, Cong Shi, Yuekai Sun

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Daniele Bracale, Moulinath Banerjee, Cong Shi, Yuekai Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling marketplace where N different vendors are selling similar (but slightly different) products. Every day, they have to decide: What price should I charge today?

If they charge too much, customers go elsewhere. If they charge too little, they leave money on the table. But here's the catch: what one vendor charges affects everyone else. If Vendor A drops their price, Vendor B might lose customers, forcing Vendor B to react. It's a constant, high-stakes game of "chicken" played with price tags.

This paper introduces a new strategy for these vendors to learn how to price their goods perfectly over time, even when they don't know exactly how their customers think or how their rivals will react.

Here is the breakdown of their solution, explained simply:

1. The Problem: The "Guessing Game"

In the past, researchers tried to solve this by telling vendors to play a specific game first: "For the first 100 days, just pick random prices to see what happens. Then, for the rest of the time, use what you learned."

The authors say this is bad advice for the real world.

Why? In a real market, you can't just "experiment" with random prices for months. You'll go out of business. Also, you don't know how long to experiment.
The Reality: Vendors only see their own sales. They never see how many items their rivals sold or how much money rivals made. They only see the rivals' prices. It's like playing poker where you can see everyone's cards on the table, but you can't see their chips or their final score.

2. The Solution: "The Optimistic Learner"

The authors propose a new algorithm called PML-GLUCB. Think of it as a vendor who is optimistic but cautious.

Instead of a separate "learning phase," this vendor learns while they are selling. Here is how it works:

The "Best Guess" (Penalized MLE): Every day, the vendor looks at their history of sales and prices. They use a mathematical formula to make their best guess about how sensitive customers are to price changes.
The "Optimistic Twist" (UCB): Since they aren't 100% sure of their guess, they add a "safety buffer." They assume the best-case scenario for their unknowns.
- Analogy: Imagine you are guessing the weight of a mystery box. You know it's between 10 and 20 lbs. To be safe, you assume it's 20 lbs. If you're wrong, you lose a little; if you're right, you win big. The algorithm picks the price that looks like the winner in this optimistic scenario.
The Result: This "optimism" forces the vendor to try different prices naturally. They explore new prices because they are curious if those prices might be even better than they think. No separate "experimentation phase" is needed.

3. The "Generalized" Magic

Previous models assumed that demand (how many people buy) changes in a straight line (e.g., "If price goes up $1, sales drop 10%").

This paper says: "Real life isn't a straight line."

Sometimes a small price drop causes a huge surge in sales.
Sometimes a price hike doesn't hurt sales at all until it hits a "tipping point."
Sometimes sales are just "Yes/No" (binary), and sometimes they are exact numbers (continuous).

The new algorithm handles all of these shapes (curves, lines, yes/no) at once. It's like a Swiss Army knife for pricing, whereas old models were just a single screwdriver.

4. The Outcome: Winning the Game

The paper proves that if every vendor uses this "Optimistic Learner" strategy:

They learn fast: Their total "lost money" (regret) compared to a perfect oracle grows very slowly (specifically, proportional to the square root of time). This is the best possible speed known for these types of problems.
The Market Stabilizes: Even though everyone is learning on their own, the prices they set eventually settle down to a stable point (called a Nash Equilibrium).
- Analogy: Imagine a crowded dance floor. Everyone is trying to find the best spot to dance without bumping into others. Even though no one is directing the dance, they eventually find a rhythm where everyone is happy and no one wants to move. That's the Nash Equilibrium.

Summary

The paper solves a tricky problem: How do competing businesses learn to price their products perfectly without talking to each other, without seeing each other's sales, and without wasting time on a separate "practice" round?

They did it by creating a smart algorithm that is optimistic about the unknown, allowing the business to learn and earn simultaneously, while handling complex, non-linear customer behaviors that older models couldn't understand.

Technical Summary: Online Price Competition under Generalized Linear Demands

Problem Formulation
The paper addresses the problem of sequential price competition among $N$ sellers operating over a finite time horizon $T$ . Unlike traditional monopolistic settings or prior competitive models that assume linear demand, this work considers a generalized linear (single-index) demand framework. For each seller $i$ , the expected demand is modeled as:
$\lambda_i(p) = \mu_i(\langle \theta_{i,0}, p \rangle) = \mu_i(-\beta_{i,0}p_i + \langle \gamma_{i,0}, p_{-i} \rangle)$
where:

$p$ is the vector of prices set by all sellers simultaneously.
$\mu_i$ is a known, strictly increasing link function (e.g., logistic for binary outcomes, identity for linear).
$\theta_{i,0}$ is an unknown parameter vector containing the seller's own-price sensitivity ( $-\beta_{i,0}$ ) and competitors' price sensitivities ( $\gamma_{i,0}$ ).
The demand observations $y_i(t)$ follow a canonical exponential family distribution conditioned on prices.

Information Structure and Constraints
The setting is characterized by a specific information asymmetry distinct from standard Multi-Agent Reinforcement Learning (MARL):

Partial Observability: Each seller observes only their own realized demand (or revenue) and the prices set by all rivals. They do not observe competitors' realized demands or revenues.
Simultaneous Moves: Sellers choose prices simultaneously. Consequently, a seller observes the context (rivals' prices $p_{-i}$ ) only after choosing their own action $p_i$ , creating a timing asymmetry that precludes standard contextual bandit analyses where context is observed before action selection.
No Coordination: The policy must be fully decentralized; sellers cannot coordinate exploration phases.

Methodology: PML-GLUCB
The authors propose PML-GLUCB (Penalized Maximum Likelihood Generalized Linear Upper Confidence Bound), a decentralized algorithm that eliminates the need for a front-loaded, coordinated exploration phase. The method operates as follows:

Penalized Maximum Likelihood Estimation (PMLE): At each round $t$ , seller $i$ updates their estimate of $\theta_{i,0}$ by maximizing a penalized log-likelihood function based on historical data $(p(s), y_i(s))_{s < t}$ . To ensure the estimator remains within the bounded parameter space $\Theta_i$ , a projection step is applied if the raw PMLE exceeds the norm bound.
Optimistic Pricing (UCB): Instead of a pure "explore-then-commit" strategy, the algorithm employs an Upper Confidence Bound (UCB) approach. The seller constructs an optimistic estimate of the revenue function by adding a confidence bonus to the estimated revenue. The bonus is derived from a concentration inequality tailored to the generalized linear model, utilizing an elliptical potential bound adapted for simultaneous moves.
Best-Response Update: The seller selects the price $p_i(t)$ that maximizes this optimistic revenue function given the observed prices of competitors from the previous round (or current round depending on the specific update timing in the algorithm, though the text emphasizes observing $p_{-i}$ after choosing $p_i$ in the general setting, the algorithm uses $p(t-1)_{-i}$ for the decision at $t$ ).

Key Contributions

Front-Loaded Exploration-Free Learning: The paper introduces a policy that learns and optimizes simultaneously without requiring an explicit initial phase of i.i.d. random pricing. This addresses practical limitations where "experimenting with prices" is often infeasible and avoids dependence on unknown problem-specific constants required to determine exploration length in prior works.
Generalization of Demand Models: The framework strictly generalizes existing linear demand models to include a broad class of nonlinear, monotone single-index models. It unifies the analysis of both binary demand (purchase/no-purchase) and continuous demand observations under a single theoretical umbrella.
Novel Concentration Tools: Due to the simultaneous-move nature of the game, standard elliptical potential lemmas (which assume exogenous context) cannot be directly applied. The authors derive a new elliptical-type bound (Lemma C.2) suitable for settings where the context (rivals' prices) is endogenous and observed with a delay relative to the action.

Results

Regret Bound: Relative to a dynamic benchmark (the best response to the sequence of rivals' prices in hindsight), each seller achieves a regret bound of:
$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$
This matches the optimal $\tilde{O}(\sqrt{T})$ rate known for linear competitive pricing, up to logarithmic factors and a dependence on the number of sellers $N$ .
Convergence to Equilibrium: The algorithm ensures that the average squared deviation of the price vector from the Nash Equilibrium (NE) price vector $p^*$ decays as:
$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$
This indicates that regret-optimal play keeps the market close to the Nash equilibrium on average.
Computational Complexity: The algorithm is computationally tractable, with a per-round complexity of $O(N^2)$ per seller (dominated by matrix updates and vector products), making it scalable for moderate $N$ .

Significance and Claims
The paper claims that PML-GLUCB is order-optimal (minimax optimal up to logarithmic factors) in the generalized linear setting. By removing the requirement for coordinated exploration, the method aligns more closely with realistic market conditions where firms act independently and cannot pre-commit to exploration schedules. The work bridges the gap between theoretical demand learning and practical implementation in competitive environments with nonlinear demand structures.

The authors note that while the $\sqrt{T}$ dependence is optimal, the $N^2$ dependence on the number of sellers remains an open question regarding its tightness. Furthermore, the paper acknowledges that while the average deviation from equilibrium is controlled, pointwise convergence of the price sequence to the NE is not guaranteed without an initial i.i.d. exploration phase, consistent with broader literature on adaptive bandit algorithms.