{"id":"d1780005-1d0d-4711-99e1-60df6cf36856","arxiv_id":"2507.13834","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"SGPO prunes trajectory states via a submodularity graph, then runs a policy gradient update, but its claimed constant-factor guarantee is not proven and conflicts with the paper's inapproximability theorem.","lead":"This paper proposes SGPO, a reinforcement learning algorithm that prunes the state space of a trajectory using a submodularity graph before applying a policy gradient update. The authors claim a provably approximate solution and report higher rewards than a baseline on four environments, but the proof of the guarantee is absent and contradicts the paper's own hardness theorem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SGPO's pruning step (Alg. 1, lines 11-20) is never shown to preserve the Theorem 3 gradient estimator, and the claimed constant-factor guarantee is asserted without proof despite Theorem 2.","rationale":"The reader's weakest-assumption diagnosis is correct and is the decisive technical gap: Algorithm 1's pruning has no proven relationship to the policy-gradient estimator, so the algorithm's theoretical status is a heuristic. I checked the derivations in Section 3 and found no result establishing unbiasedness or bounded error for the pruned estimator. The final claim in Section 5 is also unsupported and appears to contradict Theorem 2 unless extra assumptions are supplied, but no such assumptions are stated. This is a correctness risk, not merely a presentation issue. The paper does contain a genuine attempt at a REINFORCE-style derivation and a plausible connection to pruned submodularity graphs, but these do not bridge the pruning gap. A concrete experiment comparing full and pruned gradient estimates would settle whether the pruning is benign in practice; the analytical gap alone justifies the existing REJECT verdict.","tokens_in":11982,"tokens_out":6964,"duration_ms":86622,"concrete_test":"Run a controlled experiment on the discrete graph-based environment: collect a fixed set of trajectories with a trained pi_theta, then compute (a) the exact Theorem 3 estimate using all H time steps and (b) the Algorithm 1 estimate using only states in V' after pruning with c=8. Compare the two estimates (cosine similarity and L2 difference) over 100 independent trajectory batches. If the estimates do not converge to the same vector as batch size grows, the pruning step biases the gradient and no approximation guarantee can follow. In parallel, attempt to derive the Section 5 constant-factor claim from the stated assumptions; if no derivation exists, the claim should be removed or formally proven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that SGPO gives a provably approximate solution, but the only theoretical bridge between the algorithm and Theorem 3 is missing. Theorem 3 (Eq. 9) is an identity for full trajectories tau drawn from f(tau; pi_theta): it sums score terms over every time step i=0,...,H-1. Algorithm 1 instead builds K (line 20) only from states that survive the submodularity-graph pruning; time steps whose states are pruned have their score terms dropped. No lemma, importance weight, or bias bound connects the pruned estimator to grad_theta J(pi_theta), so the update in Eq. 4 is a heuristic even if Theorem 3 is correct. This is not a minor gap: in policy gradient methods, dropping terms is generically biased because E[grad log pi_theta(a_i|s_i) Q_i] is nonzero for surviving terms. The concluding claim of a constant-factor approximation 'under simplified assumptions' is likewise unsupported: no such theorem appears, and Theorem 2 states constant-factor approximation is impossible for general SubRL. The assumptions under which the guarantee would hold are never stated or connected to the pruning rule.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies reinforcement learning with a submodular reward function and proposes an algorithm, SGPO, that prunes states using a pruned submodularity graph, then applies a policy gradient update on the remaining states. The authors claim a performance guarantee, give a complexity analysis, and report experiments on continuous and discrete environments comparing SGPO to SubPO. The central advertised result, however, is a constant-factor approximation guarantee that appears only in the concluding section without proof, and the algorithm's pruning step is never shown to preserve the gradient signal used in the update.","tokens_in":12195,"tokens_out":4547,"duration_ms":53978,"significance":"If the central claims were supported, the paper would contribute a scalable method for submodular RL with a provable approximation ratio, a problem class that has received little attention. The experimental comparison with SubPO and the use of a pruning technique from submodular maximization are potentially useful. However, the load-bearing theoretical statements are either unproved or in tension with the paper's own Theorem 2, and the algorithmic modification relative to standard policy gradient is not justified. As it stands, SGPO is presented as a heuristic with an unsupported guarantee, so the significance of the claimed contribution is not established.","major_comments":[{"comment":"No result connects the pruned set V' to the gradient estimator in Theorem 3. Theorem 3 (Eq. 9) is derived for full trajectories τ drawn from f(τ;π_θ), with a sum over every time step i=0,...,H-1. Algorithm 1 constructs K (line 20) only from states that survive the submodularity-graph pruning, so time steps whose states are pruned lose their score terms. The paper does not provide an unbiasedness proof, an importance-weighting scheme, or a bias bound relating the pruned estimator to ∇_θ J(π_θ). Consequently, the parameter update in Eq. 4 is a heuristic unless this gap is filled.","section":"Section 3, Algorithm 1 (lines 11-20) and Theorem 3 (Eq. 9)"},{"comment":"The sentence 'We show that the proposed SGPO will achieve a constant factor approximation guarantee under the simplified assumptions' is not supported by any theorem or proof in the manuscript, and the 'simplified assumptions' are never stated. Moreover, Theorem 2 asserts that no polynomial-time algorithm can guarantee a constant-factor approximation for general SubRL; without an explicit articulation of which assumptions are relaxed and how they circumvent Theorem 2, the claimed guarantee is both unproved and in direct tension with the paper's own inapproximability result.","section":"Section 5, Concluding Remarks"},{"comment":"The proof of Theorem 2 is not a rigorous reduction. It states a reduction from Group Steiner Tree to Submodular Orienteering and then to SubRL, but it does not specify the Submodular MDP states, actions, transition probabilities, or horizon in a way that makes the optimal policy value correspond to the optimal SOP walk. In particular, the SubRL formulation has time-augmented states (S = V × H) and stochastic transitions, while the claimed equivalence uses a deterministic walk with a budget constraint; no argument shows that maximizing the expected submodular reward over policies equals maximizing the set function over feasible walks. As stated, the theorem is unsubstantiated, and its interaction with the concluding constant-factor guarantee is never resolved.","section":"Section 3, Theorem 2"},{"comment":"The transition from Eq. (20) to Eq. (22) drops the marginal-gain terms with j < i without stating the standard conditional-zero-expectation argument. That argument, which relies on the future action a_i being independent of past rewards conditioned on the prefix, is not given; without it the equality in Eq. (22) is not immediate. Additionally, the definition of R(τ) over trajectories that include actions is inconsistent with the formal definition R: 2^S → R for S = V × H, since a trajectory contains action symbols. These issues affect the correctness of the gradient estimator as presented, although they might be fixable with added assumptions and a standard derivation.","section":"Section 3, Theorem 3 proof (Eqs. 20-22)"}],"minor_comments":[{"comment":"The abstract and introduction state that the proposed approach 'provides a provably approximate solution,' but no theorem in the paper actually proves an approximation guarantee for SGPO; this wording should be revised to match the proven content.","section":"Abstract and Section 1"},{"comment":"The notation in line 15, w_{U,v} ← min_{u∈U} [R(v|u) − R(u|V \\ {u})], uses R(v|u) without defining the marginal gain notation for a set function R; the standard notation Δ(v|u) = R(u ∪ {v}) − R(u) should be introduced earlier.","section":"Section 3, Algorithm 1 description"},{"comment":"In the complexity paragraph, 'To store the edges of the graph, it will take O(n^2) time' should read 'O(n^2) space,' and the expression O(H(sm) · H(sm) · H(n)) is not defined; the symbols H, s, m, and n are overloaded with the horizon H and the state/action dimensions, making the analysis hard to follow.","section":"Section 3, Complexity Analysis"},{"comment":"Some equations in Table 1, such as the GP(M) objective T(τ) = Σ_s w_s − λ Σ_s N_s, are ambiguous about the index of summation, and Figure 1 has multiple panels labeled (k) and (ℓ) that are not all referenced in the text, which complicates interpreting the reported results.","section":"Section 4, Table 1 and Figure 1"},{"comment":"The paper repeatedly uses 'R' both for the reward function and for the set of rewards stored in Algorithm 1 (line 7), which is confusing; a different symbol, such as W or Q, would clarify the presentation.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The manuscript's main advertised contribution is a provable approximation guarantee that is neither stated as a formal theorem nor connected to the algorithm's pruning rule, and the inapproximability result in Theorem 2 appears to conflict with the concluding claim. Given that the central theoretical claims are either unproved or potentially inconsistent, the paper is not ready for publication in its current form. The empirical comparison against SubPO may be of some interest, but it is not sufficient to compensate for the lack of a sound theoretical backbone."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper combines a pruned submodularity graph (Zhou et al.) with a policy gradient update for submodular RL. That combination is new, I think, but the advertised payoff—a provable approximation guarantee—is nowhere on the page. The conclusion says SGPO achieves a constant-factor guarantee 'under simplified assumptions,' yet no such theorem appears and Theorem 2 states constant-factor approximation is impossible for the general problem. So either the assumptions are doing all the work and need to be stated and proven, or the claim is false.\n\nWhat it does well: the idea of using the pruning graph to reduce the state space in a submodular MDP is a reasonable engineering move and is grounded in existing literature [31]. Theorem 2, the inapproximability result for submodular RL, is a useful negative result to have, even if the proof is only sketched. Theorem 3 is a standard REINFORCE-style identity; for Markovian policies the reward-to-go form is fine because dropped past-reward terms have zero expectation. The experiments, while limited to one baseline, at least cover both continuous and discrete environments and show SGPO consistently above SubPO in the reported numbers.\n\nNow the soft spots, in order of severity. First, the missing link between the pruning rule and the gradient estimator. Algorithm 1 drops states with small divergence w_{U,v} and builds the update set K only from survivors. Theorem 3's estimator sums score terms over all time steps of a full trajectory; using only surviving steps changes the estimate, and no bias bound or importance correction is given. That is a real gap: in policy gradients, omitting score terms is generically biased. So as written, SGPO is a heuristic, not a provable method. Second, the constant-factor claim. It appears only in the conclusion, with no statement of the assumptions and no proof; this is not a small omission. Third, the experiments have no error bars, no code or data, and only one baseline; Figures are hard to read. Hyperparameters r=c=8 are stated but not studied. Fourth, the writing and notation are rough (e.g., space complexity typed as 'O(n2) time', missing symbols, inconsistent use of V and Z). These are fixable but add up.\n\nWho is this for? Someone already working on submodular RL who wants a quick heuristic for state pruning might find the empirical comparison mildly interesting. It is not yet at the standard of a research preprint claiming a proof.\n\nMy recommendation: don't send this to peer review in its current form. The core claim is unproven, the algorithm lacks a correctness argument, and the empirical work is too thin. If the authors add a real theorem about the pruning bias (or a counterexample showing where it fails) and clean up the claims and experiments, the idea could be worth another look.","headline":"New combination, but the core promise is unproven: the pruning step never connects to the gradient estimator, and the constant-factor guarantee is asserted without proof and collides with the paper's own inapproximability theorem.","tokens_in":12749,"tokens_out":6758,"would_cite":false,"duration_ms":71121,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A pruned submodularity graph lets policy-gradient reinforcement learning handle submodular rewards at scale, the paper argues.","keywords":["submodular reward","reinforcement learning","policy gradient","pruned submodularity graph","state space reduction","diminishing returns","submodular function maximization"],"falsifier":"Run SGPO on one of the tested environments with pruning disabled and with increasing pruning aggressiveness $c$, then compare the expected return and the angle between the pruned and full-trajectory gradient estimates; if the difference grows without bound as $c$ increases, the pruning premise fails. Concretely, if the cosine similarity between $\\nabla_\\theta J$ computed on the full state set and on the pruned set $V'$ falls below 0.9 across epochs, the pruned gradient is not a faithful surrogate.","tokens_in":11739,"feed_emoji":"🧩","tokens_out":7334,"duration_ms":80712,"temperature":0.7,"pith_summary":"The paper tries to extend reinforcement learning from additive rewards to submodular rewards, where the law of diminishing returns governs the objective. It proposes SGPO, a policy-gradient method that builds a weighted submodularity graph over visited states and prunes the states with the smallest divergence scores before estimating the gradient. The intended payoff is a scalable optimizer that still yields an approximate optimal policy, with a claimed constant-factor guarantee under simplified assumptions. Experiments across continuous and discrete environments report that SGPO collects more reward than an existing submodular RL baseline and shows smoother policy and critic loss curves.","feed_headline":"Pruned states yield higher rewards in submodular RL","feed_subtitle":"A graph-based pruning rule cuts state space and outperforms an existing submodular RL baseline in four environments.","key_machinery":"The submodularity graph is a weighted directed graph on the set of visited states, with edge weight $w_{uv} = F(v\\mid u) - F(u\\mid V\\setminus\\{u\\})$ measuring how much value $v$ can add beyond what $u$ already contributes. Each state's divergence from a sampled set $U$ is $w_{U,v} = \\min_{u\\in U} w_{uv}$, and states with the smallest divergence are pruned as redundant. The argument is carried by the interaction between this pruning loop and the policy-gradient estimator of Theorem 3, which expresses $\\nabla_\\theta J(\\pi_\\theta)$ as an expectation over trajectories of $\\sum_{i=0}^{H-1} \\nabla_\\theta \\log \\pi_\\theta(a_i\\mid s_i)\\bigl(\\sum_{j=i}^{H-1} R(s_{j+1}\\mid \\tau_{0:j}) + R(s_0)\\bigr)$.","core_discovery":"The paper asserts that states visited during a submodular RL episode can be treated as a ground set, organized into a submodularity graph, and aggressively pruned without losing the information needed for policy improvement. The remaining states feed a policy-gradient estimator, derived in Theorem 3, that rewrites the submodular trajectory reward as a telescoping sum of marginal gains. SGPO then performs regularized gradient ascent on this estimate. The paper further asserts that this pruning makes the time and space cost manageable while preserving approximation quality, claiming a constant-factor approximation under simplified assumptions; its Theorem 2 simultaneously states that no polynomial-time algorithm can achieve a constant factor on general instances, where only logarithmic approximation is possible.","pith_inferences":["Editorial inference: the constant-factor statement in Section 5 and Theorem 2's logarithmic hardness bound are compatible only if the simplified assumptions exclude the hard instances; spelling out those assumptions would turn the pruning rule from an empirical recipe into a provable method.","Editorial inference: the divergence score could be reused outside submodular RL, for example to choose which transitions to store in a replay buffer or which states to use for value-function regression in standard RL pipelines.","Editorial inference: a natural stress test is to run SGPO on a submodular maximization instance with a known optimal solution and compare the achieved return against the $(1-1/e)$ greedy benchmark; the paper does not report such a calibration."],"forward_implications":["If the pruning premise holds, submodular objectives such as coverage, informative path planning, and entropy maximization become practical targets for policy-gradient RL at state-space sizes where full-trajectory evaluation is too costly.","The stated time bound $O(N n^4 s^2 m^2)$ and space bound $O(n^2)$ imply that the computational bottleneck is the graph construction and gradient estimator, not the number of states that survive pruning.","If the simplified-assumption constant-factor claim is correct, there is a class of submodular MDPs on which SGPO comes within a fixed multiplicative factor of the optimal policy, despite the general problem being logarithmically inapproximable.","The smoother policy- and critic-loss curves reported for SGPO suggest that pruning also acts as a variance-reduction mechanism during training, not merely as a computational shortcut."],"supporting_citations":[{"why":"Introduces pruned submodularity graphs, the construction that SGPO's state-pruning loop adapts to reinforcement learning.","marker":"[31]"},{"why":"Formulates submodular reinforcement learning and supplies the baseline algorithm and the orienteering-style reduction used for comparison.","marker":"[23]"},{"why":"Establishes the $(1-1/e)$ greedy approximation for submodular maximization that motivates the paper's approximation analysis.","marker":"[22]"},{"why":"Provides the Group Steiner Tree inapproximability bound used in Theorem 2 to show logarithmic hardness for the general SubRL problem.","marker":"[9]"}],"fun_headline_variants":["Pruned state graph yields better submodular RL rewards","State pruning lifts rewards in submodular RL","Submodular RL tamed by pruned state graph","Graph pruning scales submodular RL with higher rewards"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the assumption that states with the smallest divergence score carry little policy-gradient information, so discarding them does not distort the gradient estimate used to update the policy.","fun_headline_variants_meta":{"raw":{"variants":["Pruned state graph yields better submodular RL rewards","State pruning lifts rewards in submodular RL","Submodular RL tamed by pruned state graph","Graph pruning scales submodular RL with higher rewards"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000315,"raw_usage":{"total_tokens":1763,"prompt_tokens":899,"completion_tokens":864,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":800}},"tokens_in":515,"tokens_out":864,"duration_ms":10269,"temperature":1.0,"reasoning_tokens":800,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:16:03.437377+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SGPO on one of the tested environments with pruning disabled and with increasing pruning aggressiveness $c$, then compare the expected return and the angle between the pruned and full-trajectory gradient estimates; if the difference grows without bound as $c$ increases, the pruning premise fails. Concretely, if the cosine similarity between $\\nabla_\\theta J$ computed on the full state set and on the pruned set $V'$ falls below 0.9 across epochs, the pruned gradient is not a faithful surrogate.","supporting_citations":[{"cited_title":"In: Artificial Intelligence and Statistics","cited_arxiv_id":null,"evidence_quote":"Introduces pruned submodularity graphs, the construction that SGPO's state-pruning loop adapts to reinforcement learning."},{"cited_title":"Submodular Reinforcement Learning","cited_arxiv_id":"2307.13372","evidence_quote":"Formulates submodular reinforcement learning and supplies the baseline algorithm and the orienteering-style reduction used for comparison."},{"cited_title":"Mathematical programming14, 265–294 (1978)","cited_arxiv_id":null,"evidence_quote":"Establishes the $(1-1/e)$ greedy approximation for submodular maximization that motivates the paper's approximation analysis."},{"cited_title":"Journal of Algorithms37(1), 66–84 (2000)","cited_arxiv_id":null,"evidence_quote":"Provides the Group Steiner Tree inapproximability bound used in Theorem 2 to show logarithmic hardness for the general SubRL problem."}],"review_version":1}