REVIEW 4 major objections 5 minor 28 references
Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs
T0 review · 4 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read This paper claims a regret-minimization algorithm for two-dimensional CDF-dependent rewards with O~(T^{7/10}) regret, breaking the previous O~(T^{3/4}) barrier.
desk verdict A genuine T^{7/10} advance for 2D CDF bandits, but the proof as written has a fixable sign-of-g gap in the grid-to-continuum step and some corrupted formulas that need cleanup before it can be trusted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The induced graph R(G): two grid points are connected if an L-shaped path between them (horizontal segment plus vertical segment) lies entirely inside the surviving grid G. Its independence number α(R) is the complexity measure that replaces the number of arms in the regret bound. The second phase estimates CDF differences F(y)-F(x) for edges of R(G) by decomposing arbitrary intervals into O(log K) dyadic sub-intervals and using an index-based binary search that never queries outside G; this costs O~(log^2 K / ε^3 + K/ε^2) samples, independent of the graph size. The third phase is a UCB variant for feedback graphs with ε-misspecified rewards, achieving regret O~(√(α(R)T)+εT).
What would settle it
Search over 1-Lipschitz functions g and step-CDF distributions D for a pair where max_{x∈[0,1]^2} g(x)F(x) exceeds max_{y∈GU(1/ε)} g(y)F(y) by a constant independent of ε while ε→0; if such a pair exists, the discretization error is Ω(T) and the stated T^{7/10} bound cannot hold for the algorithm, which only queries grid points. A concrete candidate is a point-mass distribution at a non-grid location with g negative just above the atom and F jumping from 0 to 1 there.
Extended reading notes
Core claim
The core discovery is a reduction showing that, in two dimensions, the regret for these CDF-dependent rewards is governed not by the size of the grid but by the independence number of a graph induced by the set of candidate optima. The algorithm first prunes the uniform grid with a coarse CDF estimate, then estimates pairwise CDF differences along edges of the induced graph using an index-based dyadic binary search that works on incomplete grids, and finally runs a UCB-style bandit algorithm that treats each graph edge as a slightly biased reward observation. Balancing the pruning precision Δ=T^{-2/10} and the relative-learning accuracy ε=T^{-3/10} yields the O~(T^{7/10}) regret. The proof a
Load-bearing premise
The proof assumes that every continuum point x is well represented by a grid point y≥x with g(y)F(y) ≥ g(x)F(x) - O(ε); this inequality is not proven and can fail when g is negative at points with upward CDF jumps, so the claimed O~(T^{7/10}) regret against the true maximum over [0,1]^2 depends on a step that needs either a sign case analysis or a regularity assumption on the distribution.
Editorial extensions
If this is right
- If the theorem is correct, fixed-price profit maximization in repeated bilateral trade inherits the O~(T^{7/10}) regret rate, improving the previous O~(T^{3/4}).
- The result disproves the conjecture that explore-then-commit is optimal for every dimension d≥2 for this class of CDF-based objectives.
- The ε-misspecified feedback graph model gives a general regret bound O~(√(α(R)T)+εT), which may apply to any problem where edge relations between arms are known only approximately.
- The sample complexity of relative learning on incomplete grids is O~(log^2 K/ε^3 + K/ε^2), nearly matching the full-grid uniform learning rate, suggesting incomplete-grid structure is not a fundamental obstacle in two dimensions.
Reading between the lines
- The discretization step in Section 7 bounds the gap between grid and continuum optima with an inequality that is asserted without proof and can fail when g takes negative values; a sign-aware argument or an atomless/positive-optimum assumption would be needed to make the T^{7/10} guarantee fully rigorous as stated.
- If the relative-learning phase extends to arbitrary dimensions, a plausible extrapolation is that d-dimensional CDF regret could drop below T^{(d+1)/(d+2)} for fixed d, though the paper does not establish this.
- The index-based dyadic decomposition for arbitrary intervals may be useful outside this paper, for instance in estimating differences of monotone functions on incomplete domains in other online learning problems.
- A concrete testable extension is to run the algorithm with a sign-of-g correction in the discretization bound on synthetic distributions with negative Lipschitz rewards; if the grid-versus-continuum gap grows linearly, the reported rate would fail for those instances.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online learning of bi-dimensional CDF-dependent rewards r(x)=g(x) P_{X~D}(X≤x) over [0,1]^2, where g is a known 1-Lipschitz function and the learner receives one bit I(X_t≤x_t) per round. The main result (Theorem 3.1) is an algorithm with regret ~O(T^{7/10}), improving over the previous ~O(T^{3/4}) bound. The algorithm proceeds in three phases: coarse pruning by uniform CDF approximation on a grid, relative CDF learning on an incomplete grid via a new index-based binary search, and a UCB-style algorithm for bandits with feedback graphs and ε-misspecified rewards. Corollary 3.2 transfers the rate to profit maximization in repeated bilateral trade with fixed prices. The proof relies on a companion sample-complexity result [CLM26] and balances the discretization error, the two learning phases, and the misspecified-feedback-graph regret.
Significance. If the result is correct, it is a genuine advance: it provides the first improvement below ~O(T^{3/4}) for a two-dimensional CDF-based regret-minimization problem, partially lifting the curse of dimensionality and giving a new fixed-price bilateral-trade bound. The techniques are also of independent interest: relative estimation on incomplete grids and a bandit-with-feedback-graph analysis with biased reward estimates are plausible reusable tools. The paper is honest about its dependence on [CLM26], though this makes the present contribution conditional on the companion paper. At this stage, several load-bearing steps are either insufficiently proven or corrupted in presentation, so the claimed rate is not yet established as written.
major comments (4)
- [Section 7, 'Bounding the Discretizations Error'] The proof asserts that for every x there is a grid point y≥x with ||y-x||_1≤2ε and g(y)F(y) ≥ g(y)F(x) ≥ g(x)F(x)-2ε. The first inequality requires g(y)≥0: since F(y)≥F(x), the inequality reverses for g(y)<0 (e.g., g(y)=-0.2, F(x)=0, F(y)=1). The paper allows g to take values in [-1,1], so the stated O(Tε) approximation-error bound is unproved. This term is essential: with ε=T^{-3/10} it contributes T^{7/10}. A sign-based argument (choose y≤x when g(x)<0, or impose an atomless/positive-optimum assumption) may repair the bound, but it is absent. Please also clarify whether the approximating point is in GU(1/ε) or in the pruned graph G.
- [Section 5, Lemma 5.1 and Appendix A] Lemma 5.1 is the foundation of the relative-learning procedure RLS, yet its statement is corrupted: property 1 reads '≤ ϵ2 ⌟roo⟪⟪op...' and property 2 contains '⋁ w_{i+1}=w_j'; the proof in Appendix A says it is 'substantially analogous' and repeats the same broken symbols. Since the index-based binary search on an incomplete grid is a claimed new technique and Lemma 5.1 directly determines the query count and approximation accuracy of Phase 2, the reader cannot verify the chain. Please provide a clean statement and a complete proof, including the precise dependence on K, ε, and δ.
- [Appendix B, Theorem 6.1] The proof of the claimed ~O(√(α(R)T)+Tε) regret for bandits with ε-misspecified rewards is only sketched. The key displayed chain in the proof of Theorem 6.1 passes through inequalities without justifying which terms are dropped or how the union bound over t and i is applied; the final step invokes 'the same analysis' as [LTW20]. Because this theorem is the basis of Corollary 6.2 and the paper explicitly presents the ε-misspecified extension as a contribution, the proof needs to be written out. At minimum, one needs a clean statement of the clean event, the event that the confidence intervals hold, and the argument showing how the independence number α(R) bounds the regret.
- [Section 6, Corollary 6.2] The reduction to the misspecified feedback-graph model assumes rewards in [0,1] and maps f_{x,y}:[0,1]→[0,1], but f_{x,y}(o)=(o+D(x;y))g(y) can be negative when g(y)<0, and D(x;y) itself can be negative for an L-shaped edge. The sentence 'we can recover an instance with positive rewards by a simple normalization' is not sufficient: please give the explicit shift/scale and verify that the misspecification parameter remains O~(ε) after normalization. This matters because the paper's theorem allows g with arbitrary sign.
minor comments (5)
- [Throughout] The manuscript contains multiple corrupted mathematical expressions and LaTeX artifacts (e.g., '⌟roo⟪⟪op', '⋁', '⌟⟨rro⟪⟪⟩r⟪'), especially in Section 5 and Appendix B. These must be fixed in a clean version; as written they make parts of the paper unreadable.
- [Section 7] In the proof of Theorem 3.1, the phrase 'it exists a y∈G, y≥x' should specify whether G is the original uniform grid GU(1/ε) or the final pruned graph G; the proof of the approximation error refers to the grid optimum, so the notation should be consistent.
- [Algorithm 4, line 16] The stopping condition in BinS-Rec mixes ε and the confidence term in a way that is not immediately coherent with Lemma 5.1; please align the displayed constants with the lemma's claimed bounds.
- [Section 5.4, Lemma 5.4] The sample complexity is stated as ~O(log K/ε^3 + K/ε^2); with K=1/ε this is ~O(1/ε^3), but the two terms have different origins. It would help to state explicitly which term comes from the O(K) calls to BinS and which from the dyadic decomposition, since the R2 bound in Section 7 uses only the first term.
- [Section 4, Algorithm 2] The restriction of GOPT to points with g≥0 in lines 4-6 is asserted to be safe in Lemma 4.2, but the argument is compressed. A short explanation of why the true grid optimum remains in the restricted set would improve readability.
Circularity Check
No circular reduction found; the T^{7/10} derivation is a genuine construction, though it depends on the authors' companion CDF-estimation result and contains a non-circular sign gap in the grid-approximation step.
full rationale
The derivation chain is not circular. The algorithm is a three-phase construction: Phase 1 invokes the uniform CDF estimator of the same authors' companion paper [CLM26] as a black box (Theorem 2.3); Phase 2 gives a new relative-difference estimator (RLS, Algorithms 3-7); Phase 3 analyzes a new misspecified-feedback-graph bandit (Theorem 6.1). The tuning parameters Delta and epsilon are chosen by balancing the regret expression (Delta = T^{-2/10}, epsilon = T^{-3/10}), not by fitting to data. The main issue found is in Section 7: the inequality g(y)F(y) >= g(y)F(x) >= g(x)F(x)-2epsilon for a grid point y>=x uses g(y)>=0, which is not guaranteed for arbitrary g in [-1,1] on the full grid; for negative g, F(y)>=F(x) reverses the first inequality. This is a mathematical correctness gap in the continuum-vs-grid comparison, not circularity: the conclusion is not equivalent to an input, and no fitted value is relabeled as a prediction. The paper's reliance on [CLM26] is a dependency, and since that work is an unpublished same-author preprint it is not independent verification in the machine-checked sense; however, dependency is not circularity. Theorem 6.1's proof is deferred to Appendix B, which is present but textually garbled; that is a presentation/verification weakness, not a circular step.
Assumptions & free parameters
free parameters (2)
- Delta (coarse pruning precision) =
T^{-1/5}
- epsilon (relative learning accuracy / grid resolution) =
T^{-3/10}
assumptions (4)
- domain assumption UniformCDF sample-complexity theorem (Theorem 2.3 from [CLM26])
- domain assumption Estimate rectangle estimator (Lemma 2.2 from [CLM26])
- domain assumption F is a CDF and g is 1-Lipschitz on [0,1]^2
- standard math Azuma-Hoeffding and union-bound concentration
Cite this review
Pith. "Pith review of Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs." pith.science (2026). https://pith.science/paper/4T62CWAP
@misc{pith2026260720258,
author = {Pith},
title = {Pith review of: Breaking the $T^3/4$ Barrier for Regret Minimization With Bi-Dimensional CDFs},
year = {2026},
howpublished = {\url{https://pith.science/paper/4T62CWAP}},
note = {Machine review of arXiv:2607.20258}
}
abstract
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 $\Omega(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.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
The Thirteenth International Conference on Learning Representations , year=
Feature-Based Online Bilateral Trade , author=. The Thirteenth International Conference on Learning Representations , year=
-
[2]
Advances in Neural Information Processing Systems , volume=
Fair online bilateral trade , author=. Advances in Neural Information Processing Systems , volume=
-
[3]
2026 , booktitle=
Nonparametric Contextual Online Bilateral Trade , author=. 2026 , booktitle=
2026
-
[4]
arXiv preprint arXiv:2602.12903 , year=
Contextual Online Bilateral Trade , author=. arXiv preprint arXiv:2602.12903 , year=
-
[5]
arXiv preprint arXiv:2504.04349 , year=
Tight regret bounds for fixed-price bilateral trade , author=. arXiv preprint arXiv:2504.04349 , year=
-
[6]
Journal of economic theory , volume=
Efficient mechanisms for bilateral trading , author=. Journal of economic theory , volume=. 1983 , publisher=
1983
-
[7]
arXiv preprint arXiv:2605.12664 , year=
Profit Maximization in Bilateral Trade against a Smooth Adversary , author=. arXiv preprint arXiv:2605.12664 , year=
-
[8]
arXiv preprint arXiv:2602.10868 , year=
The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms , author=. arXiv preprint arXiv:2602.10868 , year=
Show all 28 references
-
[9]
44th Annual IEEE Symposium on Foundations of Computer Science, 2003
The value of knowing a demand curve: Bounds on regret for online posted-price auctions , author=. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. , pages=. 2003 , organization=
2003
-
[10]
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=
Pricing query complexity of revenue maximization , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=
2023
-
[11]
Advances in Neural Information Processing Systems , volume=
Online optimization in X-armed bandits , author=. Advances in Neural Information Processing Systems , volume=
-
[12]
Advances in Neural Information Processing Systems , volume=
Multi-armed bandits on implicit metric spaces , author=. Advances in Neural Information Processing Systems , volume=
-
[13]
arXiv preprint arXiv:2507.11419 , year=
Better Regret Rates in Bilateral Trade via Sublinear Budget Violation , author=. arXiv preprint arXiv:2507.11419 , year=
-
[14]
Statistics & Probability Letters , volume=
On the tight constant in the multivariate Dvoretzky--Kiefer--Wolfowitz inequality , author=. Statistics & Probability Letters , volume=. 2021 , publisher=
2021
-
[15]
The Annals of Mathematical Statistics , pages=
Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator , author=. The Annals of Mathematical Statistics , pages=. 1956 , publisher=
1956
-
[16]
The annals of Probability , pages=
The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality , author=. The annals of Probability , pages=. 1990 , publisher=
1990
-
[17]
Journal of the ACM (JACM) , volume=
Bandits and experts in metric spaces , author=. Journal of the ACM (JACM) , volume=. 2019 , publisher=
2019
-
[18]
2019 , publisher=
Probability: theory and examples , author=. 2019 , publisher=
2019
-
[19]
The Thirty Sixth Annual Conference on Learning Theory , pages=
Repeated bilateral trade against a smoothed adversary , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=
2023
-
[20]
Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=
No-regret learning in bilateral trade via global budget balance , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=
-
[21]
Artificial Intelligence , volume=
An -regret analysis of adversarial bilateral trade , author=. Artificial Intelligence , volume=. 2024 , publisher=
2024
-
[22]
Proceedings of the 22nd ACM Conference on Economics and Computation , pages=
A regret analysis of bilateral trade , author=. Proceedings of the 22nd ACM Conference on Economics and Computation , pages=
-
[23]
arXiv preprint arXiv:2503.01529 , year=
Online Two-Sided Markets: Many Buyers Enhance Learning , author=. arXiv preprint arXiv:2503.01529 , year=
-
[24]
Proceedings of the 25th ACM Conference on Economics and Computation , pages=
Learning to Maximize Gains From Trade in Small Markets , author=. Proceedings of the 25th ACM Conference on Economics and Computation , pages=
-
[25]
Proceedings of the 25th ACM Conference on Economics and Computation , pages=
Selling joint ads: A regret minimization perspective , author=. Proceedings of the 25th ACM Conference on Economics and Computation , pages=. 2024 , doi=
2024
-
[26]
arXiv preprint arXiv:2509.22563 , year=
Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade , author=. arXiv preprint arXiv:2509.22563 , year=
-
[27]
Algorithmic Learning Theory , pages=
Feedback graph regret bounds for Thompson sampling and UCB , author=. Algorithmic Learning Theory , pages=. 2020 , organization=
2020
-
[28]
Mathematics of Operations Research , volume=
Bilateral trade: A regret minimization perspective , author=. Mathematics of Operations Research , volume=. 2024 , publisher=
2024
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.