We study an online linear programming (OLP) problem under a random input model in which the columns of the constraint matrix along with the corresponding coefficients in the objective function are independently and identically drawn from an unknown distribution and revealed sequentially over time. Virtually all existing online algorithms were based on learning the dual optimal solutions/prices of the linear programs (LPs), and their analyses were focused on the aggregate objective value and solving the packing LP, where all coefficients in the constraint matrix and objective are nonnegative. However, two major open questions were as follows. (i) Does the set of LP optimal dual prices learned in the existing algorithms converge to those of the “offline” LP? (ii) Could the results be extended to general LP problems where the coefficients can be either positive or negative? We resolve these two questions by establishing convergence results for the dual prices under moderate regularity conditions for general LP problems. Specifically, we identify an equivalent form of the dual problem that relates the dual LP with a sample average approximation to a stochastic program. Furthermore, we propose a new type of OLP algorithm, action-history-dependent learning algorithm, which improves the previous algorithm performances by taking into account the past input data and the past decisions/actions. We derive an [ ] regret bound (under a locally strong convexity and smoothness condition) for the proposed algorithm, against the [ ] bound for typical dual-price learning algorithms, where n is the number of decision variables. Numerical experiments demonstrate the effectiveness of the proposed algorithm and the action-history-dependent design.
We consider a general online stochastic optimization problem with multiple resource constraints over a horizon of finite time periods. In each time period, a reward function and multiple cost functions are revealed, and the decision maker needs to specify an action from a convex and compact action set to collect the reward and consume the resources. Each cost function corresponds to the consumption of one resource. The reward function and the cost functions of each time period are drawn from an unknown distribution, which is nonstationary across time. The objective of the decision maker is to maximize the cumulative reward subject to the resource constraints. This formulation captures a wide range of applications including online linear programming and network revenue management, among others. In this paper, we consider two settings: (i) a data-driven setting where the true distribution is unknown but a prior estimate (possibly inaccurate) is available and (ii) an uninformative setting where the true distribution is completely unknown. We propose a unified Wasserstein distance–based measure to quantify the inaccuracy of the prior estimate in setting (i) and the nonstationarity of the environment in setting (ii). We show that the proposed measure leads to a necessary and sufficient condition for the attainability of a sublinear regret in both settings. For setting (i), we propose an informative gradient descent algorithm. The algorithm takes a primal-dual perspective, and it integrates the prior information of the underlying distributions into an online gradient descent procedure in the dual space. The algorithm also naturally extends to the uninformative setting (ii). Under both settings, we show the corresponding algorithm achieves a regret of optimal order. We illustrate the algorithm’s performance through numerical experiments. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2020.03850 .
Bounded Regret for LP-Based Revenue-Management Problems In “An Improved Analysis of LP-Based Control for Revenue Management,” Chen, Li, and Ye study a class of quantity-based network revenue-management problems. The authors consider a stochastic setting where all the orders are i.i.d. sampled and the customers are of finite type. They focus on the classic LP-based adaptive algorithm and consider regret as the performance measure. They found that when the underlying LP is nondegenerate, the algorithm achieves a problem-dependent regret upper bound that is independent of the horizon/number of time periods T; when the underlying LP is degenerate, the algorithm achieves a tight regret upper bound that scales on the order of T log(T) and matches the lower bound up to a logarithmic order.
A merchant dynamically sets prices in each time period when selling a product over a finite time horizon with a given initial inventory. The merchant utilizes new external information that is observed at the beginning of each time period, whereas the demand function—how the external information and the price jointly impact that single-period demand distribution—is unknown. The merchant’s decision, setting price dynamically, serves dual roles to learn the unknown demand function and to balance inventory with an ultimate objective to maximize the expected cumulative revenue. The main objective of this work is to characterize and provide a full spectrum of relations between the order of optimal expected cumulative revenue achieved in three decision-making regimes: the merchant’s online decision-making regime, a clairvoyant regime with complete knowledge about the demand function, and a deterministic regime in which all the uncertainties are relaxed to the expectations. In the analyses, we derive an unconstrained representation of the optimality gap for generic constrained online learning problems, which renders tractable lower and upper bounds for the expected revenue achieved by dynamic pricing algorithms between different regimes. This analytical framework also inspires the design of two dual-based dynamic pricing algorithms for the clairvoyant and online regimes. This paper was accepted by Hamid Nazerzadeh, data science. Supplemental Material: The online appendix and data are available at https://doi.org/10.1287/mnsc.2023.4963 .
The study On Dynamic Pricing with Covariates introduces novel methods for setting prices when key market factors, or covariates, vary over time. Although most existing literature assumes these factors follow a fixed distribution, the authors show such assumptions are unnecessary for achieving near-optimal pricing strategies. They provide new pricing algorithms with upper regret bounds that match lower regret bounds (up to a logarithmic factor)—even when covariates exhibit no fixed statistical pattern. In particular, the analysis underscores how these algorithms can efficiently adapt to changing market conditions, enabling businesses to continuously optimize their pricing strategies. In addition, the paper extends these results to a constrained scenario with limited, nonreplenishable inventory, unveiling how a variation metric quantifies the effect of temporal shifts in covariates on pricing performance. Numerical experiments validate the practicality of these algorithms. By relaxing common statistical assumptions, this research offers a more flexible approach for data-driven dynamic pricing solutions.