2026/07/22 by Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
#cs.LG
We study regret minimization for learning CDF-related objectives of the form g(x)⋅ℙX\simD(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\simD. 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 Ω(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.