这篇论文改进了二维CDF学习的遗憾界，从T^{3/4}降到T^{7/10}，还能用在双边贸易优化上，挺有理论价值的。
本文研究二维空间上CDF相关目标的遗憾最小化问题。算法实现了O~(T^{7/10})的遗憾界，优于此前O~(T^{3/4})的最好结果。该结果部分缓解了维度灾难，但与Ω(T^{2/3})的下界仍有差距。其技巧可应用于重复双边贸易利润最大化问题，获得相同遗憾界。
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\sim\mathcal{D}}(X\le x), \] over $[0,1]^2$, where $g$ is a known Lipschitz function and $\mathcal{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\sim\mathcal{D}$. We design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$, improving over the previous best-known bound of $\widetilde{\mathcal{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{\mathcal{O}}(T^{7/10})$ regret bound for profit maximization in repeated bilateral trade with fixed prices.