Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs

We study regret minimization for learning CDF-related objectives of the form [ g(x)\cdot\mathbb{P}_{X\simD}(X\le 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 x_t and observes the binary feedback \mathbb{I}(X_t\le x_t), where X_t\simD. We design an algorithm achieving regret \widetilde{O}(T^{7/10}), improving over the previous best-known bound of \widetilde{O}(T^{3/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 Ω(T^{2/3}) lower bound. As an application, our techniques yield the same \widetilde{O}(T^{7/10}) regret bound for profit maximization in repeated bilateral trade with fixed prices.