Introduction
In the realm of e-commerce, "posted pricing"—the fixed prices encountered on platforms like Amazon or airline booking sites—is the gold standard. Algorithmic pricing often relies on online learning to discover optimal prices over time, aiming for vanishing regret. This means that as time progresses, the gap between the algorithm's total revenue and the revenue of the best fixed pricing strategy chosen in hindsight becomes negligible.
However, a fundamental disconnect exists between traditional online learning models and real-world commerce: most existing algorithms assume the system is stateless, implying an infinite supply of items. In reality, pricing is inherently stateful. Selling the last available flight ticket today eliminates the possibility of selling it tomorrow. This inventory depletion creates long-term dependencies where a single pricing decision can compromise future revenue potential. Standard online learning fails in these scenarios because an adversary can trick the algorithm into a "state trap," depleting resources early so it cannot capitalize on high-value buyers later.
This NeurIPS 2020 paper tackles this challenge, providing the first framework for stateful posted pricing that achieves vanishing regret in adversarial settings.
Overcoming the "State Trap" Paradox
In adversarial settings, an algorithm cannot simply "learn" the best state. The authors mathematically prove that without additional structural assumptions, achieving vanishing regret in a stateful system is impossible. To bridge this gap, the paper introduces several novel theoretical constructs designed to navigate dynamic, adversarial environments.
Dynamic Deterministic MDPs and DRACC
The authors generalize the classic Markov Decision Process (MDP) to an adversarial setting, creating the Dynamic Deterministic MDP (Dd-MDP). In this model, rewards and state transitions are chosen by an adversary and revealed only after the decision-maker acts. To ground this in practical scenarios, they introduce DRACC (Dynamic Resource Allocation with Capacity Constraints), a general model that captures various stateful applications, such as online job scheduling or matching buyers to sellers on a dynamic graph.
The Chasability Condition
The paper's core breakthrough is the introduction of a structural property called chasability. A system is considered "chasable" if there exists an oracle capable of simulating any target policy starting from any initial state with only a small, bounded loss. This insight acts as a buffer: the algorithm does not need to perfectly match the optimal policy's state at all times. Instead, it only needs the ability to "re-align" its inventory levels without incurring catastrophic revenue losses.
To prove that DRACC is chasable, the authors utilize a potential function based on the difference between the algorithm's inventory and the target policy's inventory. By occasionally posting "high prices" (effectively all-1 price vectors), the algorithm can halt sales, allowing its inventory to "catch up" to a desired target level.
The Chasing and Switching (C&S) Algorithm
Leveraging chasability, the authors reduce the complex stateful Dd-MDP problem to a well-studied stateless problem: Online Learning with Switching Costs. Their C&S algorithm treats different pricing policies as "arms" in a multi-armed bandit framework. When the algorithm identifies a better-performing policy and decides to switch, it invokes the chasing oracle to transition the current inventory state to match the new policy's state.
Key Results and Theoretical Guarantees
As a theoretical paper focused on mathematical proofs and algorithmic design, the study does not rely on empirical datasets. Instead, the authors rigorously prove the performance of their algorithm across all possible adversarial sequences of buyer valuations.
- Vanishing Regret: The proposed Learning-Based Posted Pricing (LBPP) mechanism successfully achieves sublinear regret. Specifically, for $k_t$-demand valuations (where users desire up to $k$ items), the regret is bounded by $O(T^{3/4})$.
- Near-Optimality: The authors establish that for certain classes of problems, these regret bounds are near-optimal, indicating that no other algorithm can significantly outperform their approach in an adversarial environment.
- Broad Generality: The framework extends beyond simple pricing, successfully covering complex applications like online job scheduling, which previously lacked vanishing-regret guarantees in adversarial settings.
Limitations and Future Directions
While the paper presents a significant theoretical leap, the authors note several limitations that pave the way for future research:
- Inventory Dependence: The regret bounds scale with the total capacity ($C$) and the number of active resources ($W$). As these parameters grow, the cost of "chasing" increases, potentially reducing efficiency for massive-scale inventories.
- Deterministic Transitions: The current model assumes deterministic transitions (e.g., selling an item decreases inventory by exactly one). Extending this framework to handle stochastic transitions, where a sale's occurrence is probabilistic, remains a complex open challenge.
- Computational Complexity: Achieving low regret requires simulating many candidate policies ($\Gamma$) in parallel. If the set of policies is exceptionally large, this parallel simulation could become computationally prohibitive.
Summary updated