REVIEW 3 major objections 4 minor 8 references
Commit to the Bit: Reactive Reinforcement Learning Done Right
T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read 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
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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
What would settle it
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.
Extended reading notes
Core claim
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
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Theorem 3.5, Definition 5.5] 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 5, Lemma 5.2] 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.
- [Lemma B.6, Section 5] 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.
minor comments (4)
- [Appendix C, Lemma 5.1 proof] 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.
- [Proposition B.3] Typo: 'corrdior' should read 'corridor'.
- [Algorithm 1, Line 9] 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.
- [Remark after Assumption 3.3] 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.
Circularity Check
No significant circularity: convergence is derived via external stochastic-approximation theorems, and the transfer to E is an explicitly stated assumption rather than a hidden restatement of the conclusion.
full rationale
The derivation chain is self-contained up to the stated conditional. Lemma 5.2 proves almost-sure convergence of Q_t to a Q* satisfying Eq. (2) using Theorem A.1 (Liu et al. 2025) and Theorem A.2 (Borkar & Soumyanatha 1997), neither of which is a self-citation nor presupposes optimality in E. Lemma 5.4 then identifies the kernel in Eq. (2) with the transition kernel of the constructed π-MDP, and Lemma 4.4 transfers optimality to the quasi-Markov π-rewiring \bar E_π. The final step from \bar E_π back to E is gated by an explicitly labeled assumption: either rewire-robustness (Definition 3.7), an environment-only universal property over all rewirings, or π-rewire-robustness (Definition 5.5), which the paper explicitly says is needed to guarantee optimality. Definition 5.5 is admittedly close to the desired conclusion and Lemma B.6 shows it is policy-dependent, so the universal optimality guarantee for arbitrary π is not established; however, this is a scope/assumption limitation, not a circular derivation. The paper does not fit a parameter and rename it as a prediction, and the self-citations present are not load-bearing. Hence no circular step.
Assumptions & free parameters
free parameters (2)
- step-size constants τ1, τ2 =
unspecified positive constants
- corridor experiment schedules ε_t and α_t =
ε0=0.1, ε1000=0.01; α0=0.1, α1000=0.01
assumptions (7)
- domain assumption All policies are proper, meaning every episode terminates with probability 1 from any initial state.
- domain assumption The behavior policy π has full support: π(ω|z) > 0 for all features z and options ω.
- standard math Step sizes are of the form α_t = τ1/(t+τ2) with τ1, τ2 > 0.
- domain assumption A finite option set Ω ⊂ ΔU is fixed, and all features are reachable under the behavior policy.
- standard math Borkar–Meyn ODE method extended to Markovian noise (Liu et al. 2025, Corollary 8).
- standard math Borkar & Soumyanatha (1997) Theorem 3.1: a max-norm nonexpansive operator with a unique fixed point makes the ODE θ̇ = Fθ − θ globally asymptotically stable.
- domain assumption For the optimality guarantee, the environment satisfies rewire-robustness or one of the chain-sufficient conditions (quasi-Markov, q⋆-realizable, rewire-robust, π-rewire-robust).
invented entities (2)
-
Quasi-Markov environment and entrance matrix Σ
-
Rewiring / π-rewiring and rewire-robustness
Cite this review
Pith. "Pith review of Commit to the Bit: Reactive Reinforcement Learning Done Right." pith.science (2026). https://pith.science/paper/LZMIL3YM
@misc{pith2026260528276,
author = {Pith},
title = {Pith review of: Commit to the Bit: Reactive Reinforcement Learning Done Right},
year = {2026},
howpublished = {\url{https://pith.science/paper/LZMIL3YM}},
note = {Machine review of arXiv:2605.28276}
}
abstract
Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, Committed Q-learning, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call rewire-robustness. This assumption is strictly weaker than the $q_\star$-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of quasi-Markov environments.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
The Markov chain (ξt) is irreducible and thus has a unique stationary distributionµ∈∆ Ξ
-
[2]
The step sizes are of the form αt = τ1 t+τ2 for some constantsτ 1, τ2 >0
-
[3]
There exist measurable functions H∞ :R d ×Ξ→R d and b: Ξ→R d such that, for any θ∈R d, ξ∈Ξ , and c≥1, H(cθ, ξ)−cH ∞(θ, ξ) =b(ξ)
-
[4]
Moreover, both h(θ) .=E µH(θ, ξ)andh ∞(θ) .=E µH∞(θ, ξ) are well-defined and finite
There exists a Lipschitz constant L≥0 such that, for anyθ, θ′ ∈R d andξ∈Ξ, ∥H(θ, ξ)−H(θ ′, ξ)∥ ≤L∥θ−θ′∥and ∥H∞(θ, ξ)−H∞(θ′, ξ)∥ ≤L∥θ−θ′∥, where ∥·∥ denotes the maximum norm. Moreover, both h(θ) .=E µH(θ, ξ)andh ∞(θ) .=E µH∞(θ, ξ) are well-defined and finite
-
[5]
learnable
Let hc(θ) .=h(cθ)/c for all θ∈R d and c≥1 . Then, hc →h ∞ uniformly on any compact subset of Rd as c→ ∞. The ordinary differential equation (ODE) ˙θ(t) =h ∞ θ(t) has 0 as its globally asymptotically stable equilibrium. Then, if θ⋆ ∈R d is the globally asymptotically stable equi- librium of the ODE ˙θ(t) =h θ(t) , the iteratesθ t of(3)converge almost surel...
2025
-
[1994]
S.A First Look at Rigorous Probability Theory
5 Rosenthal, J. S.A First Look at Rigorous Probability Theory. World Scientific Publishing Company, second edition,
-
[2006]
J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V ., Lanctot, M., et al
15 Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V ., Lanctot, M., et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016. LINK. 1 Singh, S., Jaakkola, T., and Jordan, M. Reinforcement learn- ing with soft state aggr...
2016
-
[2024]
Reinforcement learning with long short-term memory
14 Bakker, B. Reinforcement learning with long short-term memory. InAdvances in Neural Information Processing Systems, volume 14, 2001. LINK. 9 Barto, A. G., Sutton, R. S., and Anderson, C. W. Neuronlike adaptive elements that can solve difficult learning control problems.IEEE Transactions on Systems, Man, and Cybernetics, 13(5):834–846, 1983. LINK. 8 Ber...
arXiv 2001
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.