Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs

We study regret minimization for learning CDF-related objectives of the form [ g(x)·mathbbPX~D(X≤ x), ] over [0,1]2, where g is a known Lipschitz function and D is an unknown distribution. At each round t, the learner selects a point xt and observes the binary feedback mathbbI(Xt≤ xt), where Xt~D. We design an algorithm achieving regret widetildeO(T7/10), improving over the previous best-known bound of widetildeO(T3/4) and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the Omega(T2/3) lower bound. As an application, our techniques yield the same widetildeO(T7/10) regret bound for profit maximization in repeated bilateral trade with fixed prices.