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

arXiv:2607.20258v1 Announce Type: new Abstract: We study regret minimization for learning CDF-related objectives of the form [ g(x)dotP_{XsimD}(Xle 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 I(X_tle x_t), where X_tsimD. 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 Omega(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.

Source: arXiv cs.LG | 2026-07-23