{"id":"b074f6d0-5d6b-4dd8-b9a8-eba8cc086ad8","arxiv_id":"2607.20258","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new three-phase algorithm achieves O~(T^{7/10}) regret for two-dimensional Lipschitz CDF-dependent rewards, improving on the previous O~(T^{3/4}).","lead":"The paper gives a new algorithm for an online learning problem where an agent chooses points in a square and sees only whether an unknown random point lies below the chosen point. The algorithm's regret scales like T^{7/10}, beating the previous T^{3/4} best for this class and improving profit-maximization bounds in repeated bilateral trade.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"§7 discretization bound asserts g(y)F(y)≥g(x)F(x)−2ε for y≥x; this fails when g(y)<0, so the O(Tε) approximation error is unproven for general g∈[−1,1], leaving the T^{7/10} guarantee against the continuum optimum unsubstantiated.","rationale":"The reader identified the §7 discretization step as the weakest assumption, and I agree: it is the only place where a specific algebraic inequality is false for allowed inputs. The chain g(y)F(y) ≥ g(y)F(x) is valid only when g(y)≥0; since the theorem allows arbitrary sign of g and the comparison is to the full grid, the O(Tε) approximation-error term is not proven. This is load-bearing because it is one of four terms in the final regret decomposition, and a failure here would break the T^{7/10} rate. However, preliminary analysis suggests the actual discretization error may still be O(ε) with a more careful sign-based argument (e.g., choose a grid point below x when g is negative), so this is a fixable proof gap rather than a demonstrated counterexample. I also note that Theorem 6.1's proof is deferred to an appendix with garbled formulas and only a standard-analysis citation; this is a second major gap, but the reader already flagged it in the rationale. Since the manuscript is not currently rigorous but the central claim may be salvageable, the CONDITIONAL verdict remains appropriate; I would not reject or accept outright.","tokens_in":24088,"tokens_out":25711,"duration_ms":209109,"concrete_test":"Numerically compute Δ(ε)=max_{x∈[0,1]²} g(x)F(x)−max_{y∈GU(1/ε)} g(y)F(y) for g(x)=1−2x₁ and D=0.5δ_{(0,0)}+0.5δ_{(a,a)} with a=(m+0.5)ε for m=0,…,⌊1/(2ε)⌋, ε=2^{−k}, k=5..12. If Δ(ε)=O(ε) for all such a, the approximation-error bound is likely true and only the proof needs fixing; if Δ(ε)/ε→∞, Theorem 3.1's guarantee is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3.1 bounds the continuum-vs-grid approximation error by 2Tε using: for every x there is a grid point y≥x with ∥y−x∥₁≤2ε and g(y)F(y) ≥ g(y)F(x) ≥ g(x)F(x)−2ε. The first inequality requires g(y)≥0; for g(y)<0, monotonicity of F reverses it (e.g., g(y)=−0.2, F(x)=0, F(y)=1). The paper's Algorithm 2 prunes GOPT to nonnegative g when possible, but the discretization comparison in §7 is to the full grid GU(1/ε), so it must hold for arbitrary sign of g. As written, the O(Tε) approximation-error term is not established; if the true error were Ω(T), the T^{7/10} rate would collapse. A sign-based fix (choose a grid point below x when g is negative, or use an atomless/positive-optimum assumption) may salvage it, but it is absent. Also, Theorem 6.1's proof is deferred to a garbled Appendix B, further weakening the chain.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24386,"tokens_out":8590,"duration_ms":77317,"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":[{"comment":"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":"Section 7, 'Bounding the Discretizations Error'"},{"comment":"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 δ.","section":"Section 5, Lemma 5.1 and Appendix A"},{"comment":"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":"Appendix B, Theorem 6.1"},{"comment":"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.","section":"Section 6, Corollary 6.2"}],"minor_comments":[{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 7"},{"comment":"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":"Algorithm 4, line 16"},{"comment":"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":"Section 5.4, Lemma 5.4"},{"comment":"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.","section":"Section 4, Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's main claim depends on the companion paper [CLM26]; if that paper is not available to the referees in its final form, Theorems 2.3 and the proof of Lemma 5.1 cannot be fully checked. The sign-of-g discretization gap is the most serious technical issue, but it appears fixable within the manuscript's scope. I would encourage a careful revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real rate improvement — T^{7/10} for two-dimensional CDF-based objectives and for fixed-price bilateral trade profit maximization — and the techniques are new: the dyadic decomposition for arbitrary intervals, the index-based binary search on incomplete grids, and the epsilon-misspecified feedback-graph model. The high-level plan is coherent, and the paper is honest that it does not close the gap to the T^{2/3} lower bound. I believe the claim is probably true, but the current text does not fully prove it.\n\nThe best parts are the dyadic decomposition in Lemma 5.3 and the misspecified feedback-graph framework in Section 6. Those are clean contributions that could be useful beyond this paper. Lemma 4.4's connectivity argument is also plausible, and the authors correctly handle the sign of g there — which makes the Section 7 slip more surprising.\n\nThe main soft spot is the discretization error bound. The proof asserts that for every x in the continuum there is a grid point y >= x with ||y-x||_1 <= 2epsilon and then claims g(y)F(y) >= g(y)F(x) >= g(x)F(x) - 2epsilon. The first inequality requires g(y) >= 0; for negative g it reverses, since F(y) >= F(x). The stress-test is right: as written, the O(T epsilon) approximation error is unproven, and if that term were actually linear in T the T^{7/10} rate would collapse. The fix is straightforward — choose y >= x when g is nonnegative and y <= x when g is negative — but it is absent. This is a genuine gap that must be repaired.\n\nThere are also presentation problems. Lemma 5.1's statement is visibly corrupted with stray symbols, and Appendix B (proof of Theorem 6.1) is garbled too. I could not verify Lemma 5.1 or Theorem 6.1 from the text. The deferral to the UCB-N analysis of Lykouris et al. is reasonable in spirit, but the details need to be readable.\n\nThe dependence on the companion paper [CLM26] is a dependency, not circular reasoning. The uniform CDF estimation theorem is the foundation, and the same authors wrote it; the present paper does not reproduce its proof. That is worth noting but not disqualifying.\n\nBottom line: the result deserves peer review. A serious referee should ask for a corrected discretization argument (ideally with the sign case spelled out), clean restatements of Lemma 5.1 and Appendix B, and a bit more detail in the Phase 3 analysis. I would not desk-reject this; I would send it out with a request for revision.","headline":"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.","tokens_in":24885,"tokens_out":3682,"would_cite":true,"duration_ms":34316,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["regret minimization","cumulative distribution functions","Lipschitz bandits","feedback graphs","bilateral trade","fixed-price mechanisms","online learning","sample complexity"],"falsifier":"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.","tokens_in":23963,"feed_emoji":"📉","tokens_out":10931,"duration_ms":104856,"temperature":0.7,"pith_summary":"The paper aims to break the O~(T^{3/4}) regret barrier for learning reward functions of the form r(x)=g(x)P(X≤x) over [0,1]^2, where g is a known Lipschitz function and the learner receives only one bit per round, I(X_t≤x_t). It constructs a three-phase algorithm and proves regret O~(T^{7/10}), improving on the previous best and showing the curse of dimensionality is not fully inherent for CDF-based objectives in two dimensions. The same bound transfers to profit maximization in repeated bilateral trade with fixed prices. The central move is to replace uniform CDF learning over a full grid with relative learning of CDF differences on a sparse but well-connected incomplete grid, combined with a UCB algorithm on a feedback graph with slightly biased reward estimates.","feed_headline":"Two-dimensional CDF regret falls from T^{3/4} to T^{7/10}","feed_subtitle":"Three-phase algorithm learns CDF rewards from one bit per round and beats the old T^{3/4} rate.","key_machinery":"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).","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["2D CDF regret falls from T^{3/4} to T^{7/10}","CDF learning breaks T^{3/4} bound in 2D","New regret bound T^{7/10} for 2D CDF objectives","T^{7/10} regret achieved for 2D CDF learning"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["2D CDF regret falls from T^{3/4} to T^{7/10}","CDF learning breaks T^{3/4} bound in 2D","New regret bound T^{7/10} for 2D CDF objectives","T^{7/10} regret achieved for 2D CDF learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000418,"raw_usage":{"total_tokens":1986,"prompt_tokens":737,"completion_tokens":1249,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":1160}},"tokens_in":481,"tokens_out":1249,"duration_ms":12074,"temperature":1.0,"reasoning_tokens":1160,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T10:22:17.039766+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}