Optimal No-Regret Learning for One-Sided Lipschitz Functions
Paul Duetting, Guru Guruganesh, Jon Schneider, Joshua Ruizhi Wang
Abstract
Inspired by applications in pricing and contract design, we study the maximization of one-sided Lipschitz functions, which only provide the (weaker) guarantee that they do not grow too quickly in one direction. We show that it is possible to learn a maximizer for such a function while incurring $O(\log \log T)$ total regret (with a universal constant independent of the number of discontinuities / complexity of the function). This regret bound is asymptotically optimal in $T$ due to a lower bound of Kleinberg and Leighton. By applying this algorithm, we show that one can sell digital goods to multiple buyers and learn the optimal linear contract in the principal-agent setting while incurring at most $O(\log \log T)$ regret.
BibTeX
@inproceedings{icml2023_optimalnoregretl,
title = {Optimal No-Regret Learning for One-Sided Lipschitz Functions},
author = {Paul Duetting and Guru Guruganesh and Jon Schneider and Joshua Ruizhi Wang},
booktitle = {ICML 2023},
year = {2023}
}