Many microeconomic models involve optimizing a piecewise linear function, such as in contract design, posted-price auctions, and first-price auctions. When key parameters are unknown and stochastic, the task becomes learning to optimize an unknown piecewise linear reward function. This is typically cast as an online learning problem, where the goal is to minimize regret relative to the best fixed decision in hindsight. This paper introduces a general online learning framework that offers a unified approach to tackle regret minimization for piecewise linear rewards, under a suitable monotonicity assumption. We design a learning algorithm that attains a regret of [EQUATION], where n is the number of "pieces" of the reward function and T is the number of rounds. This result is tight when n is small relative to T, specifically when n ≤ T1/3. Our algorithm solves two open problems in the literature on learning in microeconomic settings. First, it shows that the state-of-the-art Õ(T2/3) regret bound for learning optimal linear contracts is not tight when the number of agent actions is small relative to T. Second, our algorithm demonstrates that in the problem of learning to set prices in posted-price auctions, it is possible to attain optimal instance-independent regret bounds.
Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond
F. Bacchiocchi;M. Castiglioni;A. Marchesi;N. Gatti
2025-01-01
Abstract
Many microeconomic models involve optimizing a piecewise linear function, such as in contract design, posted-price auctions, and first-price auctions. When key parameters are unknown and stochastic, the task becomes learning to optimize an unknown piecewise linear reward function. This is typically cast as an online learning problem, where the goal is to minimize regret relative to the best fixed decision in hindsight. This paper introduces a general online learning framework that offers a unified approach to tackle regret minimization for piecewise linear rewards, under a suitable monotonicity assumption. We design a learning algorithm that attains a regret of [EQUATION], where n is the number of "pieces" of the reward function and T is the number of rounds. This result is tight when n is small relative to T, specifically when n ≤ T1/3. Our algorithm solves two open problems in the literature on learning in microeconomic settings. First, it shows that the state-of-the-art Õ(T2/3) regret bound for learning optimal linear contracts is not tight when the number of agent actions is small relative to T. Second, our algorithm demonstrates that in the problem of learning to set prices in posted-price auctions, it is possible to attain optimal instance-independent regret bounds.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.



