Optimal No-Regret Learning for One-Sided Lipschitz Functions
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.
Cite
Text
Duetting et al. "Optimal No-Regret Learning for One-Sided Lipschitz Functions." International Conference on Machine Learning, 2023.Markdown
[Duetting et al. "Optimal No-Regret Learning for One-Sided Lipschitz Functions." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/duetting2023icml-optimal/)BibTeX
@inproceedings{duetting2023icml-optimal,
title = {{Optimal No-Regret Learning for One-Sided Lipschitz Functions}},
author = {Duetting, Paul and Guruganesh, Guru and Schneider, Jon and Wang, Joshua Ruizhi},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {8836-8850},
volume = {202},
url = {https://mlanthology.org/icml/2023/duetting2023icml-optimal/}
}