Abstract
Recently, the online matching problem has attracted much attention due to its wide application on real-world decision-making scenarios. In stationary environments, by adopting the stochastic user arrival model, existing methods are proposed to learn dual optimal prices and are shown to achieve a fast regret bound. However, the stochastic model is no longer a proper assumption when the environment is changing, leading to an optimistic method that may suffer poor performance. In this paper, we study the online matching problem in dynamic environments in which the dual optimal prices are allowed to vary over time. We bound the dynamic regret of online matching problem by the sum of two quantities, including a regret of online max-min problem and a dynamic regret of online convex optimization (OCO) problem. Then we propose a novel online approach named Primal-Dual Online Algorithm (PDOA) to minimize both quantities. In particular, PDOA adopts the primal-dual framework by optimizing dual prices with the online gradient descent (OGD) algorithm to eliminate the online max-min problem's regret. Moreover, it maintains a set of OGD experts and combines them via an expert-tracking algorithm, which gives a sublinear dynamic regret bound for the OCO problem. We show that PDOA achieves an $O(K \sqrt{T(1+P_T)})$ dynamic regret where $K$ is the number of resources, $T$ is the number of iterations and $P_T$ is the path-length of any potential dual price sequence that reflects the dynamic environment. Finally, experiments on real applications exhibit the superiority of our approach.
Introduction
In the fast-paced world of e-commerce, matching the right item to the right user is a high-stakes game. Whether it’s displaying an ad or allocating limited inventory, decisions must be made instantly. Traditionally, algorithms assume the world is "stationary"—that user behavior today looks like user behavior yesterday. However, in real-world applications, trends shift, flash sales occur, and environments are inherently dynamic.
Existing solutions often rely on stochastic models, assuming users are drawn from a fixed probability distribution. In these "quiet" environments, algorithms learn a set of optimal "dual prices" for resources and maintain them. However, if the environment is dynamic—meaning the optimal prices change over time—these stationary algorithms fail. They either react too slowly or become overly optimistic, leading to depleted budgets or missed opportunities.
Methodology: The Primal-Dual Online Algorithm (PDOA)
To address these challenges, we propose the Primal-Dual Online Algorithm (PDOA). PDOA operates on a primal-dual framework and decomposes dynamic regret into two manageable parts:
- Online Max-Min Regret: Handled by a standard primal-dual approach.
- Online Convex Optimization (OCO) Regret: Addressed through a multi-expert meta-algorithm.
Because the optimal rate of adaptation to a changing environment is unknown, PDOA manages a set of Online Gradient Descent (OGD) Experts. Each expert runs an OGD instance with a different step size (learning rate). Some experts are "fast," reacting quickly to changes, while others are "slow," providing stability during quiet periods. The meta-algorithm combines the advice of these experts using a weighted majority scheme based on a linear surrogate loss. This approach ensures that all experts can be updated using the same gradient calculation, significantly reducing computational overhead.
Experimental Evaluation
The algorithm was tested on two massive, real-world datasets sampled from Alibaba’s platforms, representing five days of traffic:
- Dataset 1 (International Retail): Focused on "task completion"—ensuring a specific number of purchases for items in local warehouses to guarantee delivery speed.
- Dataset 2 (E-commerce Grocery): Focused on fresh food sales, aiming to maximize Gross Merchandise Volume (GMV) while minimizing inventory loss.
As shown in the figure above, conversion rates and prices fluctuate significantly over time, highlighting the non-stationary nature of the environment that PDOA is designed to navigate.
Results
The results from Alibaba production data demonstrate the superiority of PDOA over standard baselines.
Key findings include:
- Retail Application: PDOA completed 11.7% more tasks than standard OGD. While a "Greedy" approach might sell more items, it fails to meet the specific delivery-speed tasks that PDOA successfully balanced.
- Grocery Application: PDOA increased total GMV by 9.5% and reduced inventory loss by 3.3% compared to OGD.
- Robustness: Unlike OGD, which showed high variance in performance depending on the day, PDOA remained stable across all five days of testing, proving its ability to handle different types of environmental drift.
Conclusion
PDOA achieves a sublinear dynamic regret bound of $O(K \sqrt{T(1+P_T)})$, where $P_T$ (path-length) quantifies environmental volatility. By maintaining a committee of experts with diverse learning rates, the algorithm avoids the "stability-plasticity dilemma," effectively adapting to market shifts without sacrificing performance during stable periods. Future work will explore handling unknown iteration counts and further optimizing computational efficiency.
Summary updated