{"id":"4d43d99f-a2f4-4198-83ed-0c615771e61c","arxiv_id":"2509.03790","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":6,"one_line_summary":"PAMC recovers sparse rewards via policy-weighted low-rank matrix completion and abstains when uncertain, but the provided manuscript lacks its proofs and full data.","lead":"PAMC is a reinforcement learning method that fills in missing rewards by assuming the reward table is mostly low rank plus a few spikes, weighted by how often each state-action pair is visited. The paper claims large sample-efficiency gains, but its core proofs are deferred to a missing appendix and the experimental results are sparse.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central recovery guarantee assumes known sampling propensities; Algorithm 1 estimates them from a non-stationary policy, and no error bound links estimated IPW weights to the oracle guarantee.","rationale":"The reader's weakest assumption identifies the positivity/overlap condition (Lemma 1), which is clearly acknowledged and indeed load-bearing. My concern extends that: even when overlap holds, the theorem requires exact knowledge of p_sa, while the algorithm estimates these weights from a moving target. The paper gives no consistency or sensitivity analysis for the estimated propensities, so the central IPW-based guarantee may not apply to the implemented method. This does not move the verdict away from the reader's REJECT; if anything, it adds a specific technical route to the same conclusion. The paper does provide a clear conceptual framework and a plausible adaptation of robust PCP to RL, so the contribution may be salvageable in a longer version, but as presented the central claim is insufficiently supported.","tokens_in":11048,"tokens_out":6617,"duration_ms":72289,"concrete_test":"Re-run the synthetic MNAR recovery experiment (Section 4.3) in two configurations: (a) oracle propensities as assumed in Theorem 2, and (b) propensities estimated from finite behavior-policy samples, e.g., empirical frequencies with Laplace smoothing computed from batches of size n=100, 1000, 10000. Plot ||Lhat - L*||_F versus meff for both configurations. If the estimated-propensity curve does not converge to the oracle curve at a comparable rate, or exhibits a non-vanishing bias, then Theorem 2 does not transfer to Algorithm 1 and the central claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 bounds the error of a weighted robust PCP estimator under the assumption that policy-aware sampling probabilities p_sa are known constants in [p, p], truncated below by εp. But in the actual PAMC loop (Algorithm 1, line 7), p_sa are estimated from a replay buffer filled by an evolving behavior policy. The buffer is a mixture of many past policies, so a single 'behavior policy estimate' is at best an approximation. IPW is known to be sensitive to propensity misspecification: even modest errors in estimated propensities can introduce bias in the weighted estimator, and the stated bound contains no term for propensity-estimation error or variance. The Limitations section acknowledges deterministic policies (κ=0), but not the finite-sample estimation of propensities under a non-stationary logging policy. Consequently, the central claim that PAMC provably recovers low-rank rewards under MNAR sampling is not established for the implemented algorithm; it is only established for an oracle that knows p_sa. This is load-bearing because the entire 'policy-aware' correction, and the resulting regret bound (Theorem 3), depend on these weights being correct.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes Policy-Aware Matrix Completion (PAMC) for sparse-reward RL. The reward matrix is modeled as L*+S*+E (low-rank + sparse + noise), and a weighted robust principal component analysis estimator is used with inverse-propensity weights to correct for MNAR sampling. The paper claims an impossibility lower bound for general rewards (Theorem 1), a recovery guarantee (Theorem 2), a visitation-weighted error-to-regret bound (Theorem 3), a sample-complexity bound (Theorem 4), and an IPW consistency lemma (Lemma 1). It also reports empirical gains on Atari-26, DM Control, MetaWorld MT50, D4RL, and preference-based RL, with confidence-based abstention. The main theoretical results are stated with proofs deferred to an appendix that is not present; the algorithm's propensity estimates are not covered by the oracle recovery theorem; and the empirical tables do not support the abstract's breadth.","tokens_in":11337,"tokens_out":6837,"duration_ms":72612,"significance":"If the recovery and regret guarantees held as stated, the paper would provide a useful bridge between matrix completion theory and sparse-reward RL, and the idea of confidence-gated abstention is a sensible safety mechanism. The paper also includes a candid Limitations section and stress-test diagnostics. However, the results are not verifiable as submitted: core proofs are missing, the main theorem assumes known sampling propensities while the algorithm estimates them, Theorem 1's proof sketch appears inconsistent, and the empirical support is narrower than claimed. The contribution is therefore not yet established.","major_comments":[{"comment":"The main recovery and sample-complexity bounds are stated without proof. Appendix A contains only implementation details and Algorithm 1, not the promised derivations. The statement of Theorem 2 also has unclear dependencies: m_eff is defined as a sum of inverse propensities, so the displayed error appears to shrink as sampling probabilities become small, which is opposite to the usual missing-data intuition; a precise derivation is needed. Without the missing proofs, the central polynomial-sample-complexity claim cannot be evaluated.","section":"§3.2, Theorems 2 and 4"},{"comment":"The proof sketch does not support the stated lower bound Ω(|S||A|/(pε²)). The coupon-collector argument gives a 1/p dependence for identifying the nonzero reward pair, with no ε² mechanism. Moreover, the reward family R^{(i,j)} sets the nonzero reward to ε/(1−γ), while the theorem refers to functions differing by ε in expected return; under discounting these differ by a factor that is not specified. The impossibility result, which motivates the structural assumption, is therefore not established.","section":"§3.2, Theorem 1"},{"comment":"Theorem 2 assumes policy-aware sampling probabilities p_sa are known constants in [p,_p_], truncated below by ε_p. In the actual PAMC loop, Algorithm 1 line 7 estimates propensities from a replay buffer filled by an evolving behavior policy. No error bound relates these estimated IPW weights to the oracle weights, and IPW is known to be sensitive to propensity misspecification. Consequently, the recovery guarantee does not apply to the implemented algorithm, and the regret bound in Theorem 3 inherits this gap.","section":"§3.2 and Algorithm 1 (lines 6–8)"},{"comment":"As stated, the bound J(π*)−J(π_PAMC) ≤ C∥R̂−R∥_W + Õ(√log(1/δ)/n) is an error-transport inequality: if the completion error under the optimal policy's visitation is small, the policy is good. The weighted norm ∥·∥_W is not defined, n is not specified, and no account is taken of the gating/abstention mechanism or of optimization/exploration error in the policy update. This does not constitute the 'novel sample complexity' result claimed in the introduction.","section":"§3.4, Theorem 3"},{"comment":"The abstract claims improvements over DrQ-v2, DreamerV3, Agent57, T-REX/D-REX, and PrefPPO across five benchmark families, but Table 2 reports only DrQ-v2, DreamerV3, and PrefPPO. Agent57 and T-REX/D-REX are not tabulated, and no results are shown for MetaWorld MT50 or D4RL despite textual claims. The single Atari 'HNS' aggregate lacks per-game breakdowns or significance tests. The empirical evidence is not sufficient for the breadth asserted.","section":"§4.2, Table 2 and abstract"}],"minor_comments":[{"comment":"The weighted objective writes ∥L∥,W with an odd comma; this should be ∥L∥_*,W or another explicitly defined weighted norm.","section":"§3.2"},{"comment":"The left panel's x-axis label reads 'Overlap Inverse (1/)' but the text says the quantity is 1/√κ. Please make the label explicit and consistent.","section":"Figure 6"},{"comment":"Several formatting issues: baseline rows use '—' for SVD time/overhead, and the 'A100 Hours' column is concatenated in places (e.g., '≈18PAMC'). Clarify the units and align the entries.","section":"Table 1"},{"comment":"The protocol says 'all methods are granted the same number of environment interactions,' but Table 2 reports 'compute-normalized' comparisons. Please clarify whether the comparison controls environment steps, optimizer steps, wall-clock time, or all of these.","section":"§4.1"},{"comment":"The paper says code will be released; if it is available, provide a link or anonymized artifact in the manuscript. Also the statement 'all experiments were run with 5 random seeds' is not reflected in the reported confidence intervals for all tables.","section":"Reproducibility"}],"recommendation":"reject","confidential_remarks":"The paper is ambitious and the high-level direction—connecting matrix completion theory with sparse-reward RL—is worth pursuing. However, the manuscript as submitted is not ready for publication: the main proofs are deferred to an appendix that does not exist, Theorem 1's proof sketch contains an internal inconsistency, the recovery theorem applies only to an oracle with known propensities while the algorithm estimates them, and the empirical claims exceed what the tables show. These are not merely presentation issues; they undermine the central 'provable PAMC' narrative. I recommend rejection, but I would encourage the authors to resubmit after supplying full proofs, tightening the theoretical statements, and providing the complete experimental results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You asked about arXiv:2509.03790. Here's my take: the core idea is genuinely interesting, and the specific combination in PAMC—policy-aware IPW for MNAR matrix completion, low-rank plus sparse reward structure, and confidence-based abstention in an RL loop—is new as far as I can tell. The question it poses about what reward structure enables efficient sparse-reward learning is a good one, and the limitations section is honest about several failure modes (deterministic policies, high-rank rewards, the Humanoid negative result). That counts for something. But on reading, the gaps are serious and the stress-test note is on target. Theorem 2 assumes the sampling propensities p_sa are known constants in [p, p], truncated below by epsilon_p. Algorithm 1, line 7, estimates those propensities from a replay buffer filled by a non-stationary behavior policy. The paper offers no error bound connecting the estimated IPW weights to the oracle recovery guarantee. IPW is known to be brittle under propensity misspecification, and with a changing policy the buffer is a mixture of policies—so this is not a minor technical detail. It means the main recovery theorem, as stated, does not apply to the implemented method. The Limitations section mentions deterministic policies but not propensity estimation error under non-stationarity. The theoretical core is also hard to check: the proofs for Theorems 2–4 and Lemma 1 are deferred to a missing appendix. Theorem 1's proof sketch leaves the epsilon^2 dependence under-justified. Empirically, the abstract promises broad gains across Atari-26, DM Control, MetaWorld, D4RL, and preference-based RL, but Table 2 only shows three baselines and a handful of numbers; several named baselines (Agent57, T-REX/D-REX) don't appear in the table. The figures are partly conceptual. The reproducibility section says code will be released, but no code is shipped. The reader's skeptical verdict is fair. What's good: the framing is coherent, the algorithm design is sensible, and the authors clearly know the relevant literature. The idea could mature into a solid paper if the proofs appear in a full version and the gap between the oracle theory and the practical propensity estimation gets closed. Who is this for? Someone working on RL theory or reward modeling who wants a fresh angle on sparse-reward structure might get value from the setup, but they should treat all results as preliminary. I would not cite it in its current form. For peer review, I would not desk reject it—the idea deserves referee time, and a good referee could push the authors to supply the missing proofs and address the propensity-estimation problem. But acceptance would be premature.","headline":"The paper's conceptual framing is new and worth a conversation, but the current manuscript's theoretical and empirical claims are not verifiable as written.","tokens_in":744,"tokens_out":902,"would_cite":false,"duration_ms":34596,"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 sparse-reward RL becomes tractable when reward functions have approximate low-rank plus sparse structure, and that a policy-aware matrix-completion estimator with confidence-gated abstention is how to exploit it.","keywords":["sparse-reward reinforcement learning","matrix completion","low-rank structure","missing not at random","inverse propensity weighting","confidence-gated abstention","sample complexity","reward learning"],"falsifier":"Run PAMC on a small tabular MDP whose reward matrix is exactly low-rank, but use a behavior policy that assigns zero probability to one state-action pair in the optimal policy's support (so κ = 0). The theorem predicts the inverse-propensity weights diverge and recovery error is uncontrolled; measuring whether the estimated rewards stay accurate or the confidence gate abstains would directly test the positivity assumption.","tokens_in":10951,"feed_emoji":"🧩","tokens_out":6691,"duration_ms":69238,"temperature":0.7,"pith_summary":"The paper sets out to show that the sample complexity of sparse-reward reinforcement learning is governed by structure in the reward function, not merely by the sparsity of feedback. It proposes Policy-Aware Matrix Completion (PAMC), which treats the unknown reward function as a matrix, assumes an approximate low-rank plus sparse decomposition, and recovers it from biased, policy-induced observations using inverse-propensity weighting. The paper proves this reduces the sample complexity from the general lower bound to polynomial, and ties completion quality directly to policy regret through a visitation-weighted bound. It also argues that a confidence-gated abstention mechanism lets the method degrade gracefully when assumptions fail. If these claims hold, sparse-reward RL shifts from a uniform exploration problem to a structured learning problem.","feed_headline":"Policy-aware completion makes sparse-reward RL polynomial","feed_subtitle":"Treating rewards as low-rank matrices under biased sampling yields recovery guarantees and safe abstention when assumptions break.","key_machinery":"The central object is the reward matrix R ∈ R^{|S|×|A|}, decomposed as R = L* + S* + E. The mechanism is policy-aware weighted matrix completion: inverse-propensity weights W_{sa} = 1/max(p_{sa}, ε_p) correct for missing-not-at-random sampling; a weighted nuclear norm plus weighted ℓ1 objective jointly recovers the low-rank component and the sparse component; and a calibrated confidence map C(s,a) gates which completed rewards the policy is allowed to trust, triggering abstention and an exploration bonus when intervals are wide.","core_discovery":"The paper establishes that the sparse-reward problem is not uniformly hard: under a general reward model, any learner needs Ω(|S||A|/p) samples, but if the true reward matrix can be written as a low-rank component plus a sparse component plus noise, recovery becomes polynomial. Concretely, Theorem 2 claims that a weighted robust principal-component pursuit estimator recovers the low-rank reward with error scaling as σ sqrt(r(|S|+|A|)/m_eff) plus a sparse-noise term, where m_eff is an inverse-propensity-weighted effective sample size. Theorem 3 then converts completion error into a policy regret bound under a visitation-weighted norm. The paper further claims that when assumptions weaken—high","pith_inferences":["If the central claim is right, environment designers could deliberately shape rewards to keep the reward matrix low-rank, making sparse feedback dramatically easier to learn from.","The confidence-gated abstention principle is not specific to matrix completion; attaching it to other learned predictors in the RL loop—dynamics models, value estimators, preference models—would be a natural test of the paper's general safety mechanism.","The theory suggests a practical pre-deployment check: estimate the singular-value spectrum of the reward matrix from a small uniform sample; if the effective rank is high, PAMC's guarantees do not apply and exploration baselines should remain in charge.","Because inverse-propensity weights become unstable when propensities are tiny, swapping them for a doubly robust estimator (which the paper mentions only in passing) could relax the positivity assumption and deserves a direct empirical comparison."],"forward_implications":["If rewards are approximately low-rank plus sparse, reward recovery needs only polynomial samples in the effective sample size m_eff rather than Ω(|S||A|/p).","Policy regret is bounded by a visitation-weighted completion error, so improving completion under the optimal policy's reachable state-action distribution directly improves control performance.","When assumptions are violated, PAMC widens confidence intervals and abstains, degrading gracefully to exploration instead of catastrophically imposing wrong rewards.","The framework extends beyond rewards: low-rank successor features can be completed in the same way, and non-stationary rewards with bounded drift are handled by the same adaptive abstention mechanism.","On Atari-26, DM Control, MetaWorld, D4RL, and preference-based benchmarks, adding PAMC to strong baselines improves sample efficiency under compute-normalized comparisons."],"supporting_citations":[{"why":"Supplies the low-rank matrix-completion recovery guarantee that PAMC's weighted completion objective extends to the biased-sampling RL setting.","marker":"(Candès & Recht, 2009)"},{"why":"Gives the nuclear-norm minimization guarantees used for the low-rank recovery bounds.","marker":"(Recht et al., 2010)"},{"why":"One of the regret analyses whose structure the visitation-weighted error-to-regret bound builds on.","marker":"(Jin et al., 2018)"},{"why":"Provides the uniform PAC-regret framework used to translate reward-completion error into policy regret.","marker":"(Dann et al., 2017)"},{"why":"Supplies minimax regret bounds for RL against which the PAMC regret comparison is measured.","marker":"(Azar et al., 2017)"},{"why":"PPO is the policy-optimization backbone in the outer loop that consumes the completed rewards.","marker":"(Schulman et al., 2017)"}],"fun_headline_variants":["Sparse rewards? Exploit low-rank structure for polynomial efficiency","Reward matrices: low-rank + sparse makes RL tractable","Matrix completion unlocks polynomial sparse-reward RL","When rewards are low-rank, sparse-RL becomes polynomial"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The guarantees require that the behavior policy has positive probability of visiting every state-action pair that the optimal policy would use; if exploration is deterministic or near-deterministic, the inverse-propensity weights become unstable and the recovery bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Sparse rewards? Exploit low-rank structure for polynomial efficiency","Reward matrices: low-rank + sparse makes RL tractable","Matrix completion unlocks polynomial sparse-reward RL","When rewards are low-rank, sparse-RL becomes polynomial"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000157,"raw_usage":{"total_tokens":1065,"prompt_tokens":757,"completion_tokens":308,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":242}},"tokens_in":501,"tokens_out":308,"duration_ms":3453,"temperature":1.0,"reasoning_tokens":242,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T10:39:47.262716+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PAMC on a small tabular MDP whose reward matrix is exactly low-rank, but use a behavior policy that assigns zero probability to one state-action pair in the optimal policy's support (so κ = 0). The theorem predicts the inverse-propensity weights diverge and recovery error is uncontrolled; measuring whether the estimated rewards stay accurate or the confidence gate abstains would directly test the positivity assumption.","supporting_citations":[{"cited_title":"Exact matrix completion via convex optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the low-rank matrix-completion recovery guarantee that PAMC's weighted completion objective extends to the biased-sampling RL setting."},{"cited_title":"Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization","cited_arxiv_id":null,"evidence_quote":"Gives the nuclear-norm minimization guarantees used for the low-rank recovery bounds."},{"cited_title":"Is q-learning provably efficient? In Advances in neural information processing systems, pp.\\ 4863--4873, 2018","cited_arxiv_id":null,"evidence_quote":"One of the regret analyses whose structure the visitation-weighted error-to-regret bound builds on."},{"cited_title":"Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Provides the uniform PAC-regret framework used to translate reward-completion error into policy regret."},{"cited_title":"Minimax regret bounds for reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Supplies minimax regret bounds for RL against which the PAMC regret comparison is measured."}],"review_version":1}