Optimal No-Regret Learning for One-Sided Lipschitz Functions

Inspired by applications in pricing and contract design, we study the maximization of onesided 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.