{"id":"fd2b491d-14ee-42a3-9741-7ac72d5ae65c","arxiv_id":"2505.12037","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"An LP-based RL algorithm that identifies a small optimal basis and then resolves the corresponding linear equations adaptively, achieving an instance-dependent ~O(1/N) suboptimality gap for favorable instances.","lead":"The paper proposes a new LP-based reinforcement learning algorithm with linear function approximation that re-solves a reduced linear program as new data arrives, proving an instance-dependent ~O(1/N) suboptimality gap. It is worth reading because it promises a large sample-complexity improvement over the previous O(1/sqrt(N)) worst-case bound for favorable problem instances.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's J* selection is internally inconsistent with Lemma 1: it returns basic slack (inactive) constraints, so Eq. (8)/(15) is not the optimal-basis system the analysis uses.","rationale":"Good-faith reading: the paper's intended contribution is an instance-dependent O(1/N) gap for LP-based RL with linear function approximation, built on basis identification plus resolving. The most load-bearing condition for that claim is that Algorithm 1 really identifies the optimal basis used in Lemma 1, and that the resolving steps solve the corresponding square linear system. That condition fails as written because of the B/N mix-up. This is independent of the reader's point about infinite state spaces and is more severe: even for the finite RLP, the algorithm in the pseudocode is not the algorithm the theorems analyze. The tiny LP test above settles it in one step. The numerical section does not independently validate the basis-selection step; it uses the output to define the benchmark 'optimal basis,' so it inherits the same ambiguity. With J* corrected to nonbasic slacks, the finite-RLP analysis (Theorems 2-4) appears plausible and the CONDITIONAL verdict is appropriate; the paper needs a corrected pseudocode plus the Corollary 1 fix. I therefore do not move the reader's verdict, but for a different primary reason.","tokens_in":26092,"tokens_out":13458,"duration_ms":138364,"concrete_test":"Run Algorithm 1 on the tiny LP max x s.t. x ≤ 1, x ≤ 2, x ≥ 0, and print the output sets. The optimal basis is {x, s_2} (s_2 = slack of constraint 2), so line 17 returns J* = {2}; Lemma 1 requires J* = {1}, the nonbasic slack. Substituting the returned J* into (8) gives x = 2 instead of the optimal x = 1. A second check: replace line 17 by J* = N ∩ {indices of slack variables} and rerun the Mountain Car experiment (Section 6); if the reported convergence curves change materially, the published Algorithm 1 was not the algorithm being analyzed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 line 17 sets J* = B ∩ {indices of slack variables s}. In the standard-form LP (7) with Ax + s = c, these are the basic slacks, i.e., typically inactive constraints with s_j > 0. Lemma 1 and its proof (Appendix B) instead require J* to be the nonbasic slacks, the active constraints satisfying A_{J*,I*} x^*_{I*} = c_{J*}. For a basic slack j, A_j x^* = c_j - s_j < c_j, so the defining equation (8) is generally false, and |B∩s| = K - |I*|, which equals |I*| only in the special case K = 2|I*|. In the Mountain Car RLP K = 12,000 and |I*| ≤ 25, so the J* returned by Algorithm 1 would have roughly 11,975 elements, making the square d2×d2 system (15)/(16) used by Algorithm 2 and Theorem 3 ill-posed. Thus the pseudocode does not implement the analyzed algorithm; the theoretical guarantees are for a different (correct) choice of J*. This is an internal inconsistency in the core construction, not merely an overclaim to infinite state-action spaces. Even after correcting this, the reader's concern about unsampled ALP constraints in Corollary 1 would remain, since Theorem 1 bounds only objective values, not constraint violations outside K.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an LP-based reinforcement learning algorithm with linear function approximation. It first proposes Algorithm 1 to identify an optimal basis of an empirical ALP/RLP, reducing the number of constraints from K to d2 <= d1 using O(K log(1/epsilon)/Delta^2) samples (Theorem 2). It then proposes Algorithm 2, a resolving scheme that repeatedly solves the d2-by-d2 linear system corresponding to the identified basis, and proves in Theorems 3 and 4 an instance-dependent sample complexity of the form O(K log(1/epsilon)/Delta^2 + d2^2(1+||A_{J*,I*}||_inf)/sigma^2 * log(1/epsilon)/epsilon) for approximating the LP value and satisfying the sampled constraints. Corollary 1 claims an extension to large or infinite state-action spaces with O(((d2^2/sigma^2)+1/Delta^2) log^2(1/epsilon)/epsilon) samples. Numerical experiments on a Mountain Car task compare the resolving algorithm with direct LP solving and DQN.","tokens_in":26350,"tokens_out":9864,"duration_ms":98348,"significance":"If the technical gaps identified below are repaired, this would be a meaningful contribution: it is one of the few LP-based RL algorithms with an instance-dependent bound, and the idea of resolving a fixed optimal basis rather than the whole LP relaxes uniqueness and non-degeneracy conditions common in online LP. The manuscript provides detailed appendices, including perturbation analysis of the linear systems, a martingale concentration argument for the resolving scheme, and a constraint-violation bound for the complement of the identified basis; these substantially support the finite-RLP claims. The numerical study is clearly presented and demonstrates practical convergence behavior. At present, however, the central guarantee is proved for the reduced LP, while the abstract and Corollary 1 claim an RL guarantee for large or infinite state-action spaces; the bridge between these two statements is load-bearing and not supplied.","major_comments":[{"comment":"Algorithm 1, line 17, sets J* = B intersect {indices of slack variables s}, i.e., the basic slack variables of the simplex tableau. In the standard-form LP (7), a basic slack variable corresponds to an inactive constraint with A_j x^* < c_j, whereas Lemma 1 (Eq. (8)) and the subsequent analysis require J* to be the set of active (nonbasic slack) constraints satisfying A_{J*,I*} x^*_{I*} = c_{J*}. Consequently Eq. (15)/(16) in Section 4 is not the system satisfied by the returned J*; in the Mountain Car RLP (K = 12,000, |I*| <= 25) the returned J* would contain roughly 11,975 indices, making the d2-by-d2 linear system in Algorithm 2 ill-posed. The pseudocode as written therefore does not implement the algorithm whose guarantees are proved; the appendices appear to analyze the complementary choice J* = (indices of nonbasic slacks). This must be corrected before Theorems 2-4 can be attributed to Algorithm 1 and Algorithm 2.","section":"Section 3.1, Algorithm 1, line 17"},{"comment":"The extension to large or infinite state-action spaces is not justified. Theorem 1 (De Farias and Van Roy 2004) bounds only the objective gap |V_ALP - V_RLP|; it says nothing about whether a solution that approximately satisfies the K sampled constraints also approximately satisfies the omitted constraints in (S x A)\\K. Theorem 4's guarantee A \\bar{x} - c <= epsilon is for the K constraints of the RLP, and Appendix F only extends violations to J*^c within that same finite constraint set. Without a bound on violations of unsampled constraints, the value-function approximation error for the original ALP is uncontrolled, so the abstract's claim of an instance-dependent ~O(1/N) suboptimality gap for RL does not follow. Corollary 1 should either be restricted to the RLP, or an additional uniform-convergence/coverage condition over S x A should be stated and used.","section":"Section 5, Corollary 1, with Section 2.2 and Theorem 1"},{"comment":"The abstract states that the algorithm enjoys an instance-dependent ~O(1/N) suboptimality gap for RL. What Theorem 4 actually proves is a bound on the LP objective gap V_ALP - r^T \\bar{x} and on constraint violations for the RLP, not a bound on V^pi - V^* for a policy derived from \\bar{x}. Converting an approximately optimal and approximately feasible approximate LP solution into a policy with a suboptimality gap requires additional steps, such as a greedy policy with respect to \\Phi \\bar{x}, and no policy-extraction argument or associated error bound appears. The guarantee should be described as a value-function approximation error for the ALP/RLP, or the policy-extraction step should be supplied.","section":"Abstract and Section 5, Theorem 4"},{"comment":"Theorem 1 is quoted as sampling K independently from S x A, but no sampling distribution is specified. The validity of the constraint-sampling approximation, the resulting definition of Delta, and the constants in Corollary 1 all depend on this distribution (e.g., state-relevance weights or a coverage condition). Without specifying the distribution and any implied concentrability/coverage constants, the corollary's sample-complexity expression is not well defined. The authors should state the distribution used for K and account for it in the statements of Theorem 2 and Corollary 1.","section":"Section 2.2, Theorem 1, and Corollary 1"}],"minor_comments":[{"comment":"The cost function is written as c : S x A -> D[0,1]; the 'D' appears to be a typo and should be c : S x A -> [0,1].","section":"Section 2"},{"comment":"The theorem statement says 'where the parameters Delta with Delta defined in (12) and sigma defined in (22)', but the displayed bound (23) contains no Delta; clarify that Delta enters only through the regime N >= N0 from Theorem 2 and through the basis-identification probability.","section":"Section 5, Theorem 3"},{"comment":"The proof says 'noting that x*_{I*} > 0' before applying complementary slackness. This is an implicit non-degeneracy assumption; if zero basic variables are allowed, the argument should be stated in terms of the signs of the basic variables and the complementary-slackness conditions rather than an unqualified strict positivity.","section":"Appendix D, proof of Lemma 2"},{"comment":"The text says r_epsilon is a pre-specified range and Figure 2 uses r_epsilon = 40, 80, but the state/action discretization has 40, 60, and 5 parts; the relationship between the noise radius and these index units should be clarified to avoid confusion.","section":"Section 6.1 and Figure 2"}],"recommendation":"major_revision","confidential_remarks":"This is a borderline case. The finite-RLP analysis is detailed and the resolving idea is interesting, but the published abstract and the pseudocode currently promise more than the proofs deliver. I recommend major revision with the expectation that the authors fix the J* selection inconsistency, restrict or re-prove the infinite-state claim in Corollary 1, and soften the abstract so that the suboptimality-gap language refers to the LP/RLP objective unless a policy-extraction argument is added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's core idea is worth engaging: they adapt the resolving-on-a-fixed-basis trick from tabular CMDPs to LP-based RL with linear function approximation, and the finite-RLP sample complexity (O(K log(1/ε)/Δ^2 + d2^2(1+||A||_∞)/σ^2 · log(1/ε)/ε)) is a real improvement over O(1/ε^2) for favorable instances. The appendix is detailed, and the dependence on the LP's own gap Δ and conditioning σ is not circular—those are instance parameters from the underlying LP, not fitted to data. The basis-reduction idea (Algorithm 1) and the resolving scheme (Algorithm 2) are sensible adaptations, and the Mountain Car experiments show the approach works in practice, though without error bars.\n\nBut the paper as written has a load-bearing internal inconsistency. Algorithm 1 line 17 sets J* to B ∩ {slack indices}, i.e., the basic slacks—the inactive constraints where s_j > 0. Lemma 1 and all theorems that follow require J* to be the nonbasic slacks: the active constraints satisfying A_{J*,I*} x^*_{I*} = c_{J*}. For a basic slack j, A_j x^* = c_j − s_j < c_j, so equation (8) is generally false. Worse, |B ∩ {slacks}| = K − |I*|, which only equals |I*| when K = 2|I*|; in the Mountain Car RLP, K = 12,000 and |I*| ≤ 25, so Algorithm 1 would return roughly 11,975 constraints, making the square d2×d2 system in Algorithm 2 and Theorem 3 ill-posed. The pseudocode does not implement the analyzed algorithm. This is fixable—change line 17 to J* = N ∩ {slack indices}—but it must be fixed for the theorems to cover the actual algorithm.\n\nThe other gaps are the ones the reader flagged: Corollary 1 extends to infinite state-action spaces without controlling violation of unsampled ALP constraints (Theorem 1 bounds only objective values), and the suboptimality gap is relative to V^ALP, not the true MDP value, so the abstract's \"~O(1/N) suboptimality gap\" overstates what is proven. The experiments lack error bars and full baseline details, but that is minor by comparison.\n\nNet: the finite-RLP core is plausible and worth preserving, but the advertised RL guarantee needs revision and additional proof. A serious referee should engage; the issues are correctable in principle, and the resolving-on-fixed-basis technique could be useful to the community.","headline":"The resolving-on-a-fixed-basis idea is a real step forward for LP-based RL, but the pseudocode as written does not implement the analyzed algorithm: J* in Algorithm 1 is the set of inactive basic slacks, not the active constraints Lemma 1 requires.","tokens_in":26907,"tokens_out":4087,"would_cite":false,"duration_ms":40207,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","90C05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims an RL algorithm that re-solves a small identified LP basis as data arrive attains an instance-dependent ~O(1/N) suboptimality gap, tightening the prior O(1/√N) worst case on favorable instances.","keywords":["reinforcement learning","linear function approximation","approximate linear programming","constraint sampling","online linear programming","optimal basis identification","instance-dependent sample complexity","Markov decision processes"],"falsifier":"Run Algorithm 2 on a continuous-state MDP (for example Mountain Car) with a fixed set $K$ of sampled constraints, then evaluate the returned weight vector on a fresh held-out set $K'$ of state–action constraints that were never used in training. If the maximum violation on $K'$ stays bounded away from zero while the violation on $K$ converges to zero, or if the violation on $K'$ grows as $K'$ is enlarged, then Theorem 4 holds for the reduced LP but Corollary 1 does not deliver the promised guarantee for the RL problem itself, and the implied policy's gap to the optimal value would fail to shrink like $1/N$.","tokens_in":25824,"feed_emoji":"📉","tokens_out":21773,"duration_ms":185544,"temperature":0.7,"pith_summary":"This paper aims to establish that the linear-programming route to reinforcement learning with linear function approximation need not pay the worst-case $O(1/\\sqrt{N})$ suboptimality gap of earlier LP-based methods. Its algorithm first pinpoints the small optimal basis of the value LP — at most as many constraints as basis functions, regardless of the state–action space size — and then, as each new batch of transition samples arrives, re-solves only the linear equations of that basis while adaptively correcting the right-hand side, so that constraint violations self-correct. The paper proves an instance-dependent bound: for instances whose gap parameter $\\Delta$ and basis conditioning $\\sigma$ are favorable, the output after $N$ samples has $\\tilde{O}(1/N)$ suboptimality, equivalent to $O(1/\\varepsilon)$ sample complexity instead of $O(1/\\varepsilon^2)$. The Mountain Car experiments illustrate the mechanism, shrinking an LP with 12,000 constraints to 25 and reaching roughly 92.5% task success. The proven guarantees concern the reduced LP, and the final bridge back to the original RL problem relies on a constraint-sampling theorem from prior work.","feed_headline":"LP re-solving turns RL's 1/√N sample gap into 1/N on good instances","feed_subtitle":"By re-solving only the binding constraints of the value LP, the method hits a 1/N gap where prior work gave 1/√N.","key_machinery":"The load-bearing object is the optimal basis $(I^*, J^*)$ of the value LP: Lemma 1 shows some optimal weight vector is supported on at most $d_2 \\le d_1$ coordinates and is the unique solution of the square system $A_{J^*,I^*} x_{I^*} = c_{J^*}$, so all other constraints and variables are irrelevant at the optimum. Algorithm 1 identifies the basis from an estimated matrix using the simplex method, and Theorem 2 shows $O(K \\log(1/\\varepsilon)/\\Delta^2)$ samples suffice to identify the true optimal basis with high probability. Algorithm 2 then solves only that system each round, with right-hand side $c^n_{J^*}/(N-n+1)$, queries the generative model on the $J^*$ constraints, and updates $c^{n+1} = c^n - A^n x^n$, which drives the scaled slack process $\\tilde{c}_{(s,a)}(n)$ back toward $c$ instead of letting violations accumulate. A sub-martingale concentration argument with a stopping time $\\tau$ shows this process stays near $c$ long enough that $E[N-\\tau] = O((d_2^2/\\sigma^2) \\log N)$, and the duality identity of Lemma 2 converts that final drift into both the objective gap and the per-constraint violations.","core_discovery":"The central claim is an instance-dependent sample-complexity theorem for the LP formulation of RL with linear function approximation. Theorem 4 states that Algorithm 2 returns, within $O(K \\log(1/\\varepsilon)/\\Delta^2 + d_2^2(1 + \\lVert A_{J^*,I^*} \\rVert_\\infty)/\\sigma^2 \\cdot \\log(1/\\varepsilon)/\\varepsilon)$ samples, a weight vector $\\bar{x}_N$ with $V^{\\mathrm{ALP}} - r^\\top \\bar{x}_N \\le \\varepsilon$ and $A \\bar{x}_N - c \\le \\varepsilon$ for every constraint of the LP, where $K$ is the constraint count, $d_2 \\le d_1$ is the size of the optimal basis, $\\Delta$ is the smallest gap between the optimal basic solution and any other (non-optimal or infeasible) basic solution, and $\\sigma$ is the smallest eigenvalue magnitude of the optimal-basis matrix $A_{J^*,I^*}$. When $\\Delta$ and $\\sigma$ are bounded away from zero, this is an $O(1/\\varepsilon)$ sample complexity, i.e. an instance-dependent $\\tilde{O}(1/N)$ suboptimality gap, improving on the $O(1/\\sqrt{N})$ worst-case gap previously established for LP-based RL. The theorem also bounds constraint violations on every constraint of the LP, a benefit the authors attribute to working with the identified optimal basis.","pith_inferences":["The paper's feasibility guarantee is only for the sampled constraints; lifting it to the full ALP would likely require a margin or Lipschitz condition on the constraint functions, a checkable property of the basis and feature map, and would turn Corollary 1 into a genuine end-to-end $O(1/\\varepsilon)$ policy guarantee.","The same resolving-while-fixed-basis scheme should transfer to other online LP settings (bandits with knapsacks, network revenue management) where earlier logarithmic-regret results required non-degeneracy; the sub-martingale argument could plausibly yield $O(1/\\varepsilon)$ guarantees there as well.","The bound predicts a specific degradation: instances with a nearly tied second-best basis (small $\\Delta$) or an ill-conditioned basis matrix (small $\\sigma$) should need visibly more samples; a computational study that varies $\\Delta$ and $\\sigma$ across random MDPs would test whether the claimed instance-dependence is real.","The success-rate advantage over DQN at small sample counts hints that LP-resolving is data-frugal when function approximation must be learned from few transitions; a second benchmark would show whether the $1/N$ rate holds beyond this single continuous-control example."],"forward_implications":["On favorable instances (fixed $\\Delta$ and $\\sigma$), the sample complexity to reach $\\varepsilon$ suboptimality drops from $O(1/\\varepsilon^2)$ to $O(1/\\varepsilon)$, i.e. an $\\tilde{O}(1/N)$ suboptimality gap after $N$ samples.","The number of LP constraints and variables that must be learned is at most the number of basis functions, independent of the state–action space size; in the Mountain Car experiment the RLP shrinks from 12,000 constraints to 25.","The guarantee needs no unique optimal basis (non-degeneracy), because the algorithm commits to one identified basis and re-solves only it.","Constraint violations are controlled on every constraint of the reduced LP, not only the binding ones, through the non-singularity of $A_{J^*,I^*}$.","Empirically the resolving policy reaches about 92.5% success on Mountain Car, roughly 40 points above a non-resolving LP baseline, and matches DQN while using fewer samples in the small-sample regime."],"supporting_citations":[{"why":"Supplies the ALP formulation (5) and the perturbed-LP value bound used in the proof of Theorem 2's Claim 1.","marker":"De Farias and Van Roy (2003)"},{"why":"Supplies Theorem 1, the constraint-sampling bound on $|V^{ALP} - V^{RLP}|$ that Corollary 1 uses to fix the number of sampled constraints K.","marker":"De Farias and Van Roy (2004)"},{"why":"The prior LP-based RL method whose worst-case $O(1/\\sqrt{N})$ suboptimality gap is the baseline the paper improves on favorable instances.","marker":"Ozdaglar et al. (2023)"},{"why":"The dual-convergence and resolving analysis for online LP that Algorithm 2's adaptive re-solving adapts.","marker":"Li and Ye (2022)"},{"why":"The resolving-while-sticking-to-one-optimal-basis scheme, previously for tabular constrained MDPs, extended here to function approximation.","marker":"Jiang and Ye (2024)"},{"why":"Relaxes the unique-optimal-basis (non-degeneracy) condition in online LP, which the fixed-basis resolving design relies on.","marker":"Jiang et al. (2025)"},{"why":"The perturbation bounds for linear systems used in the proofs of Theorem 2 and Lemma 3 to turn estimation error into basis and weight error.","marker":"Higham (2002)"},{"why":"The polynomial-time optimal-basis identification method that underlies Algorithm 3 in the appendix.","marker":"Vavasis and Ye (1996)"},{"why":"Shows the simplex method is strongly polynomial for fixed-discount MDP LPs, supporting the choice of Algorithm 1 as efficient.","marker":"Ye (2011)"}],"fun_headline_variants":["Adaptive LP resolving gives RL instance-dependent 1/N sample gap","Instance-dependent RL: LP resolving beats worst-case 1/√N","LP-based RL with adaptive resolving: instance-dependent 1/N gap","Adaptive LP re-solving: RL's 1/N gap on favorable instances, 1/√N worst-case"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the sampled constraints of the reduced LP stand in for the full value LP: an earlier constraint-sampling theorem bounds the value gap between the two LPs, but nothing in this paper shows the returned weights also satisfy the unsampled constraints, so the promised $O(1/N)$ gap to the true optimal policy is, strictly, a guarantee about the reduced LP.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive LP resolving gives RL instance-dependent 1/N sample gap","Instance-dependent RL: LP resolving beats worst-case 1/√N","LP-based RL with adaptive resolving: instance-dependent 1/N gap","Adaptive LP re-solving: RL's 1/N gap on favorable instances, 1/√N worst-case"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00117,"raw_usage":{"total_tokens":4883,"prompt_tokens":1035,"completion_tokens":3848,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":3762}},"tokens_in":651,"tokens_out":3848,"duration_ms":26376,"temperature":1.0,"reasoning_tokens":3762,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:44:27.165362+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a continuous-state MDP (for example Mountain Car) with a fixed set $K$ of sampled constraints, then evaluate the returned weight vector on a fresh held-out set $K'$ of state–action constraints that were never used in training. If the maximum violation on $K'$ stays bounded away from zero while the violation on $K$ converges to zero, or if the violation on $K'$ grows as $K'$ is enlarged, then Theorem 4 holds for the reduced LP but Corollary 1 does not deliver the promised guarantee for the RL problem itself, and the implied policy's gap to the optimal value would fail to shrink like $1/N$.","supporting_citations":[],"review_version":1}