cs.LGMar 3, 2024

Bandit Profit-maximization for Targeted Marketing

Authors: Joon Suk Huh, Ellen Vitercik, Kirthevasan Kandasamy

Organizations: Computer Science Department, UW–Madison · Management Science and Engineering Department, Stanford University · Computer Science Department, Stanford University

Abstract

We study a sequential profit-maximization problem, optimizing for both price and ancillary variables like marketing expenditures. Specifically, we aim to maximize profit over an arbitrary sequence of multiple demand curves, each dependent on a distinct ancillary variable, but sharing the same price. A prototypical example is targeted marketing, where a firm (seller) wishes to sell a product over multiple markets. The firm may invest different marketing expenditures for different markets to optimize customer acquisition, but must maintain the same price across all markets. Moreover, markets may have heterogeneous demand curves, each responding to prices and marketing expenditures differently. The firm's objective is to maximize its gross profit, the total revenue minus marketing costs. Our results are near-optimal algorithms for this class of problems in an adversarial bandit setting, where demand curves are arbitrary non-adaptive sequences, and the firm observes only noisy evaluations of chosen points on the demand curves. For nn demand curves (markets), we prove a regret upper bound of O~(nT3/4)\tilde{O}(nT^{3/4}) and a lower bound of Ω((nT)3/4)Ω((nT)^{3/4}) for monotonic demand curves, and a regret bound of Θ~(nT2/3)\tildeΘ(nT^{2/3}) for demand curves that are monotonic in price and concave in the ancillary variables.

Figures & tables

Explore similar work

Jun 28, 2026

Learning to Bid in Discriminatory Auctions with Budget Constraints

We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus αα times payment, where α∈[0,1]α\in[0,1] is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over TT rounds subject to a total budget BB. The problem is challenging even without budgets: the action space is exponential in MM, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget ρ=BMT<1ρ=\frac{B}{MT}<1, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding ρρ-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.
Oct 17, 2026

No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints

Market makers keep trading efficient by setting bid and ask prices for buyers and sellers. In sequential market making, trades happen independently based on price thresholds, requiring the market maker to maintain balanced, low-risk inventory over T rounds. This paper studies how to maximize revenue with unknown buyer and seller valuations using regret minimization. When the market maker only sees trade success or failure, an algorithm achieves regret and inventory bounds proportional to T to the power of 2/3. When full order book data is available for failed trades, regret and inventory limits improve significantly to the square root of T. We also establish a fundamental trade-off via a lower bound, by proving that tighter round-by-round inventory limits strictly force higher minimum regret.
Jul 27, 2026

On Non-Stationary Dynamic Pricing: Adaptivity and Optimality

We study the contextual dynamic pricing problem under non-stationarity, where a firm sells products to TT sequentially arriving consumers that behave according to an unknown demand model that can change over time. The demand model is assumed to be a generalized linear model (GLM), allowing for a feature vector in Rd\mathbb{R}^d that encodes products and consumer information. To achieve optimal revenue (i.e., least regret), the firm needs to learn and exploit the unknown GLMs while monitoring for potential changes. We propose a multiscale change-point detection based algorithm that achieves a regret of order O~(sTdT∧{VT1/3d1/3T2/3+dT})\widetilde{O}(\sqrt{s_TdT}\wedge\{V_T^{1/3}d^{1/3}T^{2/3}+\sqrt{dT}\}), where sTs_T is the number of piecewise stationary segments and VTV_T is a newly defined notion of design-adjusted variation budget of model parameters. Our algorithm is adaptive and does not require knowing sTs_T or VTV_T. Moreover, to our knowledge, this is the first dynamic pricing algorithm that is adaptive to the nature of changes and achieves the best-of-both-worlds rate, thus closing a long-standing gap in the literature. We remark that, due to the varying contexts, existing works in the adaptive non-stationary bandit literature cannot be applied to achieve optimality for contextual dynamic pricing. The regret is further accompanied with a newly constructed minimax lower bound, confirming the optimality of our algorithm (up to logarithmic factors). Extensive numerical experiments are conducted to illustrate the efficiency and robustness of the proposed algorithm in non-stationary dynamic pricing.