{"id":"43af1e90-ef28-475a-b8b8-bc32a08e59d9","arxiv_id":"2605.28276","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Committed Q-learning converges almost surely to the optimal memoryless policy in deterministic-observation POMDPs whenever the environment is rewire-robust, a condition strictly weaker than q⋆-realizability.","lead":"The paper introduces a variant of Q-learning that only changes its action distribution when the observed feature changes, and proves it converges to the optimal reactive policy in certain partially observable environments under a condition called rewire-robustness, which is weaker than the standard q⋆-realizability assumption. A smart generalist might read it because it offers a principled explanation for why a simple commitment heuristic can succeed where ordinary Q-learning","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The final transfer from the algorithm's limit to optimality in E is exactly π-rewire-robustness (Def. 5.5), a policy-dependent condition that can fail for full-support behavior policies; the theorem's 'optimal in E' claim is therefore not established for arbitrary π.","rationale":"The reader's weakest assumption correctly identifies π-rewire-robustness as the crucial transfer step. My reading of the proof chain confirms that the convergence result (Lemma 5.2) is about the π-MDP, and the step to optimality in E is exactly Definition 5.5. The paper's stronger rewire-robustness condition would avoid the issue by quantifying over all rewirings, but the theorem also advertises the weaker π-rewire-robustness as a sufficient condition, and that condition is environment-policy coupled and nearly the conclusion itself. This does not invalidate the core convergence argument or the strict weakening relative to q⋆-realizability; it narrows the scope of the optimality guarantee and justifies the CONDITIONAL verdict rather than ACCEPT. No change to the reader's verdict is needed.","tokens_in":27584,"tokens_out":19296,"duration_ms":188842,"concrete_test":"Take the environment E of Fig. 4a and choose a full-support behavior policy π such that the stationary entrance distribution σ_z into the aggregated feature z is concentrated on the state that makes the π-rewiring prefer the action that is suboptimal in E. Construct \\bar E_π exactly as in Def. 5.3, solve the Bellman fixed point (2) by value iteration, and compare argmax_ω Q⋆(z,ω) with the E-optimal reactive policy. If they differ, π-rewire-robustness fails and the theorem's condition (e) is doing the load-bearing work.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5.2 proves a.s. convergence of Q_t to the fixed point of the Bellman operator of the π-MDP \\hat M_π (Eq. 2), not of the original environment E. Lemma 4.4 then identifies \\hatπ⋆ as an optimal reactive policy of the π-rewiring \\bar E_π. The only bridge from \\bar E_π back to E is Definition 5.5: 'any optimal reactive policy in \\bar E_π is also optimal in E'. This is not a consequence of Assumptions 3.1–3.3; it is an extra condition that depends on the exploration policy π. The paper's own example (Fig. 4a) illustrates the obstruction: no single feature value can induce an optimal greedy policy, and for such environments there exist full-support behavior policies for which the π-rewiring's optimal policy is not E-optimal. Lemma B.6 proves the property is genuinely policy-dependent, since it exhibits an E that is not rewire-robust yet is π-rewire-robust for one particular π. Consequently, for a user who chooses π without checking π-rewire-robustness, the headline guarantee 'converges to the optimal reactive policy' does not follow; only optimality in \\bar E_π follows. This is the load-bearing soft spot of the theorem, not a flaw in the convergence machinery itself.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies reactive policy learning in finite POMDPs with deterministic observations (hard state aggregation). It proposes Committed Q-learning, a variant of Q-learning in which the behavior policy samples a new option only when the observed feature changes, and it proves almost-sure convergence of the iterates to a fixed point Q⋆ satisfying the Bellman optimality equation of an auxiliary 'π-MDP' derived from the stationary distribution of the behavior policy. The main theorem (Theorem 3.5) states that, under properness, full-support exploration, and step-size assumptions, the greedy policy with respect to Q⋆ is optimal in the original environment E provided E satisfies one of several conditions: generalized rewire-robustness, quasi-Markovness, q⋆-realizability, rewire-robustness, or π-rewire-robustness. The paper introduces quasi-Markov environments and entrance-value theory, and argues that rewire-robustness is strictly weaker than q⋆-realizability.","tokens_in":27971,"tokens_out":8969,"duration_ms":82765,"significance":"If the result holds, it is a meaningful theoretical advance for reactive RL under state aggregation: it replaces the strong q⋆-realizability assumption with a weaker, geometrically motivated condition, and it provides a clean analysis of the limit point of a simple Q-learning variant using modern stochastic approximation tools. The quasi-Markov/entrance-value lemmas are elegant and the convergence proof is rigorous. The paper also ships reproducible code. The main weakness is that the most general optimality condition, π-rewire-robustness, is policy-dependent and is structurally close to the conclusion: it asserts that optimal policies of the behavior-policy-induced rewiring are optimal in E. Thus the practical force of the 'optimal in E' guarantee for arbitrary full-support exploration policies is limited, and the abstract overstates the generality of the result unless this is carefully qualified.","major_comments":[{"comment":"The final transfer from convergence to optimality in E for general environments is exactly π-rewire-robustness. Definition 5.5 asserts that every optimal reactive policy in the behavior-policy-dependent rewiring ̅E_π is optimal in E. Since Lemma 4.4 already shows that the algorithm's limit ̂π⋆ is optimal in ̅E_π, this assumption supplies the conclusion almost verbatim. It is not a property of E alone, it depends on π, and it can fail even under full-support exploration (Fig. 4a). When it fails, the limit is only optimal in ̅E_π. The manuscript should prominently separate the convergence result from the optimality transfer, and the abstract's 'converges to the optimal reactive policy' should be qualified to the π-rewiring unless a policy-independent condition such as rewire-robustness is assumed.","section":"Theorem 3.5, Definition 5.5"},{"comment":"The convergence theorem establishes that Q_t converges to the fixed point of the Bellman operator of the π-MDP, not of the original environment E. The subsequent optimality claim in E is therefore gated by the additional structural assumptions. This is not a mathematical error, but the presentation can mislead: after reading the abstract and Theorem 3.5, a reader may believe that the algorithm provably finds an optimal reactive policy for any environment satisfying only Assumptions 3.1–3.3. The distinction between convergence to an optimal policy of ̅E_π and optimality in E should be made much more explicit in the introduction and theorem statement.","section":"Section 5, Lemma 5.2"},{"comment":"The claim that π-rewire-robustness is 'strictly weaker' than q⋆-realizability is correct only in the logical sense that there exists a pair (E, π) for which it holds while q⋆-realizability fails. It does not provide a practical way to choose π or to verify the property without already knowing optimal policies. Since the algorithm's behavior policy is part of the input, the weakest assumption in Theorem 3.5 is therefore not a verifiable property of the environment alone. The paper should state this limitation explicitly when discussing the implications of Theorem 3.5 and the 'strictly weaker' claim in the abstract.","section":"Lemma B.6, Section 5"}],"minor_comments":[{"comment":"In the display after 'From this, we get', the first term uses (T_ω)_{x,x_-} when the preceding line has (T'_{ω_-})_{x,x_-}. The notation should be made consistent, e.g., by defining T_ω as the restriction of the extended kernel to nonterminal states, to avoid confusion.","section":"Appendix C, Lemma 5.1 proof"},{"comment":"Typo: 'corrdior' should read 'corridor'.","section":"Proposition B.3"},{"comment":"The parenthetical '(or if non-committed)' is ambiguous. The paper analyzes only the committed variant; clarify that the non-committed variant is not covered by the convergence proof.","section":"Algorithm 1, Line 9"},{"comment":"The statement about step sizes α_t = τ1/(t+τ2)^β with β∈(0.5,1] says 'if we make the additional assumption that the Markov chain (ξ_t) is aperiodic', but no formal assumption of aperiodicity appears in the main text. Either add it or remove the remark.","section":"Remark after Assumption 3.3"}],"recommendation":"major_revision","confidential_remarks":"The convergence machinery and the quasi-Markov/entrance-value analysis are sound and constitute a real contribution. The concern about π-rewire-robustness is not fatal to the paper's core convergence theorem, but it is a load-bearing caveat for the optimality claim in general environments and it affects how the result should be advertised. I recommend major revision with the expectation that the authors clarify the status of π-rewire-robustness and qualify the abstract, after which the paper could be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth your time. It does something concrete: it introduces Committed Q-learning, a small modification of Q-learning where the behavior policy keeps its option until the feature changes, and proves almost-sure convergence to a Q⋆. The interesting part is that the limiting object is not the usual Q⋆ but the optimal action-value function of a 'π-MDP' induced by the behavior policy. The quasi-Markov framework and the Bayesian disaggregation matrix are clean and genuinely useful for reasoning about hard state aggregation. The corridor example is a legitimate counterexample to q⋆-realizability being necessary, and the claim that rewire-robustness is strictly weaker is supported by the examples and lemmas.\n\nThe main proof chain—Lemma 5.2 convergence to the π-MDP fixed point, Lemma 5.4 bridging to the stationary distribution, Lemma 4.4 optimality in the π-rewiring—is coherent as far as I can tell. I found the same minor typo in the Lemma 5.1 proof (T_ω instead of T_ω in one display).\n\nThe soft spot is real and it is load-bearing: the final step from 'optimal in the π-rewiring' to 'optimal in the original environment' is exactly Definition 5.5, π-rewire-robustness. This condition depends on the behavior policy and is not a property of the environment alone. The paper's own Fig. 4a shows an environment where no single feature value can induce an optimal greedy policy, and Lemma B.6 shows an environment that is not rewire-robust but is π-rewire-robust for one particular π. So for a user who picks a natural exploration policy without checking the condition, the theorem does not deliver optimality in E; it only delivers optimality in the π-rewiring. The paper is honest about this, and the convergence machinery is not the problem, but it does narrow the headline claim. The Bellman risk appendix is underdeveloped but peripheral. The code has no commit hash, which is a minor reproducibility annoyance.\n\nWho is this for? Researchers working on theory of RL with state aggregation or deterministic-observation POMDPs. It deserves a serious referee: the framework and the negative results are worth engaging even if the optimality guarantee is narrower than the abstract suggests. I would not desk-reject it. I'd send it to a reviewer who knows the q⋆-realizability literature. In revision, the π-rewire-robustness framing should be front and center, and the paper should be clearer about what is guaranteed without it.\n\nRecommendation: engage, with the expectation that the central claim needs to be stated more carefully.","headline":"A genuine weakening of q⋆-realizability for reactive Q-learning, with a clean convergence proof—but the last step to 'optimal in E' is gated by a condition that nearly assumes the conclusion.","tokens_in":28482,"tokens_out":3184,"would_cite":true,"duration_ms":27880,"reading_group":"yes","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 introduces Committed Q-learning, a one-line variant of Q-learning that provably converges almost surely to an optimal reactive policy in finite partially observable environments with deterministic observations, under a new condit","keywords":["reinforcement learning","partial observability","state aggregation","reactive policies","Q-learning","rewire-robustness","quasi-Markov environment","convergence"],"falsifier":"Run Committed Q-learning on a finite deterministic-observation environment that is rewire-robust, using a fully supported behavior policy and harmonic step sizes, and test whether the greedy policy of the limit is optimal in the original environment; the theorem predicts optimality in every such case, so one counterexample refutes it. The paper's own Fig. 4a is the mirror image: rewire-robustness fails there, the greedy limit is not optimal in the original environment, and no single per-feature value can make the required look-ahead inequalities hold simultaneously.","tokens_in":27456,"feed_emoji":"🎯","tokens_out":11072,"duration_ms":103111,"temperature":0.7,"pith_summary":"The paper asks what minimal condition lets a reinforcement-learning agent that only sees aggregated features learn the best reactive policy—a policy that maps the current feature to an action distribution without memory. It proposes Committed Q-learning, in which the behavior policy commits to one option while the observed feature stays fixed and only resamples when the feature changes. The paper proves the Q-iterates converge almost surely, and that when the environment is rewire-robust, the greedy policy of the limit is optimal in the original environment. Rewire-robustness is strictly weaker than q⋆-realizability, the assumption used by earlier convergence results, so environments like the corridor, where prior theory gave no guarantee, are now covered. The practical message is that simple state aggregation need not break value-based reinforcement learning if the learner commits at the feature level.","feed_headline":"Feature-level commitment makes Q-learning provably optimal","feed_subtitle":"It needs a strictly weaker condition than prior theory—more aggregated environments become learnable.","key_machinery":"The central machinery is the π-rewiring and its aggregate MDP. Given the behavior policy's stationary distribution, each feature is assigned an average 'entrance distribution' over the states inside it; the π-rewiring replaces all entries into a feature by this average, making the environment quasi-Markov while leaving intra-feature dynamics untouched. The aggregate MDP on features—whose transition kernel is μ(z′|z,ω), the stationary probability of moving between features under the behavior policy—is exactly what Committed Q-learning effectively solves. The 'entrance value' lemma then shows that in quasi-Markov environments the aggregate value function equals the entrance-average of the true","core_discovery":"The central claim is that Q-learning fails under hard state aggregation not because of partial observability per se, but because the learner keeps resampling actions inside a feature, so its updates average together states that need different values. In a quasi-Markov environment—one where each feature has a unique entrance-state distribution—the correct value to attach to a feature is the average value of its entrance states, and the greedy policy derived from that value solves the original problem. Committed Q-learning is engineered so that its effective transition kernel is exactly that of an aggregate Markov decision process on features: the π-rewiring of the environment under the behavi","pith_inferences":["The commitment rule effectively converts a partially observable problem into a feature-level MDP whose dynamics depend on the exploration policy; this suggests a general recipe for value-based RL under any fixed feature map: choose carefully when to reset the action, not just which updates to make.","Rewire-robustness can in principle be probed from data: estimate entrance distributions from the replay buffer under the behavior policy, construct the corresponding π-rewiring, and compare optimal policies of the rewiring with rollouts in the original environment—when they disagree, the transfer guarantee is void.","The hierarchy of conditions points to a natural research target: find the weakest structural property between rewire-robustness and π-rewire-robustness that is verifiable from the environment alone, which would make the transfer step checkable before deployment.","The paper's open question of approximate rewire-robustness is the natural next step: if one defines the suboptimality gap of the worst rewiring, a small gap should yield a near-optimality bound analogous to existing results for approximate q⋆-realizability."],"forward_implications":["The corridor environment and similar aggregated environments that violate q⋆-realizability now have a provably convergent Q-learning variant; the paper's simulations show Committed Q-learning reaches the optimal policy where regular Q-learning does not.","The paper establishes a strict hierarchy of sufficient conditions—q⋆-realizability implies generalized rewire-robustness, which implies rewire-robustness, which implies π-rewire-robustness, and quasi-Markovness also implies rewire-robustness—so the class of environments with convergence guarantees is strictly larger than before.","If the greedy policy of the limit is unique, the π-rewire-robustness condition becomes both necessary and sufficient for the recovered policy to be optimal in the original environment.","The Bellman risk, unlike the classical Bellman error, is learnable: it can be estimated purely from observed features and rewards, so the objective the algorithm implicitly solves is one an agent can estimate in practice.","The T-maze with a memory-based feature mapping is rewire-robust, so the result extends beyond toy corridors to a classic memory-dependent partially observable problem."],"fun_headline_variants":["Commit to the bit: Q-learning that provably works in aggregated worlds","Feature commitment fixes Q-learning's partial observability flaw","Provable Q-learning for hard state aggregation via action commitment","Quasi-Markov trick makes reactive Q-learning provably optimal","Stop resampling, start converging: Committed Q-learning"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"For non-quasi-Markov environments, the proof must assume that solving the algorithm's effective, behavior-policy-dependent surrogate problem also solves the original environment; this 'π-rewire-robustness' premise can fail, and when it does, the learned policy is only optimal in the surrogate.","fun_headline_variants_meta":{"raw":{"variants":["Commit to the bit: Q-learning that provably works in aggregated worlds","Feature commitment fixes Q-learning's partial observability flaw","Provable Q-learning for hard state aggregation via action commitment","Quasi-Markov trick makes reactive Q-learning provably optimal","Stop resampling, start converging: Committed Q-learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000163,"raw_usage":{"total_tokens":1036,"prompt_tokens":657,"completion_tokens":379,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":401,"completion_tokens_details":{"reasoning_tokens":308}},"tokens_in":401,"tokens_out":379,"duration_ms":4133,"temperature":1.0,"reasoning_tokens":308,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T02:13:56.434423+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Committed Q-learning on a finite deterministic-observation environment that is rewire-robust, using a fully supported behavior policy and harmonic step sizes, and test whether the greedy policy of the limit is optimal in the original environment; the theorem predicts optimality in every such case, so one counterexample refutes it. The paper's own Fig. 4a is the mirror image: rewire-robustness fails there, the greedy limit is not optimal in the original environment, and no single per-feature value can make the required look-ahead inequalities hold simultaneously.","supporting_citations":[],"review_version":2}