{"id":"3dca7ee0-c2a5-4a1a-9cfd-ed78d99d0e36","arxiv_id":"2501.13648","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For online inverse linear optimization, the paper proves a regret bound of O(1/Δ²) that is independent of the time horizon, provided the agent's decision problems satisfy a Δ-gap condition.","lead":"This paper shows how to learn a person's hidden preferences from the choices they make, when each choice is the best available option according to those preferences. It proves that if the preferred option is clearly better than the alternatives, a computer can learn the preferences accurately after a bounded number of observations, regardless of how many choices are observed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the gap-dependent bound is internally consistent and the strong Δ-gap assumption is explicit, though its practical reach is untested.","rationale":"The reader's verdict ACCEPT is sound. The strongest claim (Theorem 5.2) is a conditional statement; the proof is algebraically consistent. The weakest point is the Δ-gap condition, same as the reader's weakest assumption. I agree with the reader's assessment that this is the main limitation, but because it is an explicit assumption with discussed sufficiency conditions, it does not warrant changing the verdict. The lack of experiments limits significance but not correctness.","tokens_in":27052,"tokens_out":27119,"duration_ms":210611,"concrete_test":"Run Algorithm 1 on a synthetic sequence of polytopes with a known θ* satisfying the Δ-gap condition (e.g., integral polytopes with unique optimum and Δ=1/E) for T=10^5 and verify that the cumulative total loss stays below the Theorem 5.2 bound and does not grow with T; also compute the empirical Δ to confirm the assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I re-checked Lemma 5.3 and Theorem 5.2. The key inequality in Lemma 5.3 follows because Δ‖y_t−ŷ_t‖ ≤ ⟨θ*−θ_t, y_t−ŷ_t⟩ and ⟨θ*−θ_t, y_t−ŷ_t⟩ ≤ G E/(2^{5/4}√λ), so the squared inner product is controlled by a linear factor; the remaining algebra in Theorem 5.2 is a standard self-bounding argument. The Δ-gap condition (Definition 5.1) is indeed strong: it requires unique optimal solutions and a uniform positive margin over all feasible alternatives, so it fails when θ* lies on a normal-cone boundary or when the agent's problems have multiple optima. However, this is an explicit assumption of the theorem, not a hidden flaw, and Section 5.2 identifies reasonable settings (integral polytopes, interior normal cones) where it holds. No circular reasoning or parameter tuning was found. The only substantive limitation is that the condition's prevalence on real inverse-optimization instances is not demonstrated, which affects significance rather than soundness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the online learning formulation of inverse linear optimization introduced by Bärmann et al. (2017). It first shows that the suboptimality loss coincides with a Fenchel–Young loss whose regularizer is the indicator function of the agent's feasible set, and that the cumulative total loss equals the linearized regret of this loss. This perspective immediately yields the standard O(√T) bound for FTRL and, via online-to-batch conversion, an offline guarantee on the suboptimality loss that does not require the agent's observed choices to be optimal for the true objective. The main new result is the gap-dependent analysis: under the Δ-gap condition of Definition 5.1 and the assumption that the agent always chooses an optimal action, the same FTRL algorithm achieves a cumulative total-loss bound of order E D^3/(λ^{3/2}Δ^2), independent of the time horizon T, through a self-bounding argument that combines the adaptive FTRL regret bound with a squared-residual control derived from the gap condition.","tokens_in":27158,"tokens_out":21286,"duration_ms":194051,"significance":"If the results are correct, the paper provides a clean conceptual unification of inverse linear optimization with Fenchel–Young losses, a genuinely broader offline guarantee, and a novel T-independent regret bound that is obtained from a structural property of the agent's optimization problems rather than from strong convexity of the losses. The proofs are detailed and the constants are explicit; I checked the key steps in Lemma 5.3 and Theorem 5.2 and found no gap. The Δ-gap condition is explicitly strong—it forces a unique optimal solution and a uniform margin over all feasible alternatives—and the paper's discussion in Section 5.2 identifies sufficient conditions rather than claiming empirical universality. This limits the practical reach of the result but does not undermine the conditional theorem. The paper is a solid theoretical contribution appropriate for the journal; the only substantive caveat is that the prevalence of the Δ-gap condition on real inverse-optimization instances is not demonstrated.","major_comments":[],"minor_comments":[{"comment":"In the sentence 'The is nothing but the boundary of normal cones, ...' the word 'The' should be 'This'; the same paragraph contains an ungrammatical fragment and should be rewritten for clarity.","section":"Section 5.2"},{"comment":"The quantifier structure of the definition is awkward: the condition is written as 'for every t ... it holds that ... for y = arg max ...'; please restate it by first letting y_t be an optimal solution for θ*, then quantifying over ŷ ∈ B_t, and add a sentence noting that the condition forces y_t to be the unique optimal solution.","section":"Definition 5.1"},{"comment":"The sufficient conditions for the Δ-gap condition (integral polytopes and normal-cone interiors) are stated in prose and rely on an external lemma; a short formal statement of at least the integral-polytope case, including the resulting value of Δ (e.g., Δ ≥ 1/E), would make the applicability claim easier to verify.","section":"Section 5.2"},{"comment":"The formula for the FTRL step-size β_t is difficult to parse in the typeset version, in particular the placement of the factor 2^{1/4} relative to the square root and the division by λ; please restate it as a single explicit expression in both Algorithm 1 and the proposition.","section":"Proposition 4.1"},{"comment":"The paper would benefit from an explicit acknowledgment that the Δ-gap condition is a strong assumption whose prevalence on real inverse-optimization instances is not demonstrated; the current discussion identifies sufficient conditions but does not quantify how restrictive the uniform margin is.","section":"Section 5.2"}],"recommendation":"minor_revision","confidential_remarks":"This is a theoretically sound paper with no apparent circularity or parameter fitting. The main caveat—the practical reach of the Δ-gap assumption—affects the breadth of the contribution rather than its correctness. I recommend minor revision for presentation improvements only."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read through the paper and the stress-test note, and I agree with the positive verdict. The main result is real: under the Δ-gap condition on the agent's decision problems, the FTRL algorithm in Algorithm 1 achieves a total-loss bound of O(1/Δ²) that does not depend on the horizon T, and the algorithm never needs to know Δ. I checked the key steps — Proposition 3.1 and 3.3, Lemma 5.3, and the self-bounding argument in Theorem 5.2 — and the algebra is consistent. Lemma 5.3, which turns the gap condition into a bound on ‖y_t − ŷ_t‖² by the per-round total loss, is the load-bearing piece, and it works as stated.\n\nThe Fenchel–Young perspective is the right way to see why this goes through: the suboptimality loss is a Fenchel–Young loss with Ω the indicator of the feasible set, and the total loss is exactly the linearized regret. This is not a deep new framework, but it is a useful simplification that makes the existing O(√T) bound and the new gap-dependent bound drop out of standard OCO machinery. The offline guarantee in Theorem 4.3, which removes the agent-optimality assumption, is a small but genuine extension over Bärmann et al. (2020), and the online-to-batch proof is clean.\n\nWhere I am more cautious than the authors: the Δ-gap condition is strong. It requires every agent problem to have a unique optimal solution and a uniform margin between the optimal and all suboptimal alternatives, across all rounds. Section 5.2 gives two plausible settings — integral polytopes with integral c*, and c* in the interior of a normal cone — but these are narrowly structured. The paper does not test the condition on any real inverse-optimization instance, and it gives no lower bound, so the tightness of O(1/Δ²) is open. These are limitations of scope, not hidden flaws; the assumption is stated explicitly and the analysis is honest about what it needs.\n\nThis paper is for readers working on inverse optimization, online learning, or fast rates with structured feedback. It is a serious theoretical contribution that deserves peer review. I would send it out rather than desk-reject, and I expect it to be accepted after the authors clarify the reach of the gap condition and perhaps add a short discussion of lower bounds.\n\nGood to bring to the next group meeting.","headline":"A careful, genuinely novel gap-dependent regret bound for inverse linear optimization, with an honest framing of the strong and untested margin assumption that powers it.","tokens_in":27815,"tokens_out":1796,"would_cite":true,"duration_ms":17502,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-10T15:46:42.502318+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}