# Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs

arXiv: https://arxiv.org/abs/2607.20258 · HTML: https://mlsanity.com/paper/2607.20258/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 24 references that are in the map.
- First posted on arXiv 22 Jul 2026.

## Builds on (most cited first, 20 of 20)

- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Better Regret Rates in Bilateral Trade via Sublinear Budget Violation](https://mlsanity.com/paper/2507.11419/) (2025)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Learning to Maximize Gains From Trade in Small Markets](https://mlsanity.com/paper/2401.11596/) (2024)
- [Feature-Based Online Bilateral Trade](https://mlsanity.com/paper/2405.18183/) (2024)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Online Two-Sided Markets: Many Buyers Enhance Learning](https://mlsanity.com/paper/2503.01529/) (2025)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [Tight Regret Bounds for Fixed-Price Bilateral Trade](https://mlsanity.com/paper/2504.04349/) (2025)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (2026)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)

## Abstract (arXiv)

We study regret minimization for learning CDF-related objectives of the form [ g(x)·mathbbPX~D(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~D. 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 Omega(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.