Search papers, labs, and topics across Lattice.
This paper advances the field of regret minimization by introducing an algorithm that achieves a regret bound of \(\widetilde{\mathcal{O}}(T^{7/10})\) for learning cumulative distribution function (CDF)-related objectives over a bi-dimensional space. This improvement surpasses the previous best-known bound of \(\widetilde{\mathcal{O}}(T^{3/4})\), indicating that while the curse of dimensionality can be mitigated, a gap remains with the established lower bound of \(\Omega(T^{2/3})\). Additionally, the techniques developed are applicable to profit maximization in repeated bilateral trade scenarios, demonstrating their versatility and impact on practical applications.
Achieving a regret bound of \(\widetilde{\mathcal{O}}(T^{7/10})\) breaks the previous barrier and challenges assumptions about the curse of dimensionality in regret minimization.
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.
