{"id":"8cf6c6df-428a-433c-9032-6f126489ef35","arxiv_id":"2411.12042","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Softmax policy mirror ascent is a normalization-free mirror ascent on logits that converges linearly in tabular MDPs and linearly to a neighborhood with function approximation.","lead":"This paper refines a known policy optimization update by removing a normalization step and proves that the resulting method converges linearly in simple settings, matching natural policy gradient. It also provides a function-approximation variant with convex inner problems and reports competitive performance on Atari and MuJoCo benchmarks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2 applies Bellman γ-contraction pointwise; the step is invalid, and Theorem 3's J-gap recursion depends on that pointwise form, so the FA linear-convergence claim is not supported as written.","rationale":"Good-faith reading: the paper proposes a clean algorithm, and the tabular linear-rate result is plausible; Theorem 2's sup-norm conclusion can likely be recovered from a sup-norm contraction. The C_t positivity issue is disclosed by the authors and empirically checked, so the reader's CONDITIONAL verdict is reasonable. However, the proof as written contains an unacknowledged invalid step in a central lemma. The Bellman operator's γ-contraction is in sup norm, not pointwise, and the two-state example shows the pointwise version is false even under C_t>0. Because Theorem 3's proof uses the pointwise form to take expectations, the function-approximation linear-convergence guarantee is not currently supported. This is a correctness risk in the paper's second main contribution, independent of the empirical simulations. I do not see fraud or intentional overclaim; the issue is a proof gap. The appropriate verdict remains CONDITIONAL: accept only if the authors supply a correct pointwise argument or revise Theorem 3's statement/rate and disclose the additional dependence. This does not change the reader's verdict, hence UNCHANGED.","tokens_in":27018,"tokens_out":27130,"duration_ms":259889,"concrete_test":"Independently re-derive Lemma 2 and verify the pointwise inequality T V*(s)-T v(s) ≤ γ(V*(s)-v(s)) on the two-state MDP above, where it fails; then check whether Theorem 3's proof can be completed using only the valid sup-norm contraction. If the resulting recurrence is on ||V*-V^{π_t}||∞ rather than J(π*)-J(π_t), the stated rate does not follow without an additional distribution-mismatch factor or a revised statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 2 (Appendix B.1), after deriving V*(s)-V^{π_{t+1}}(s) ≤ η C_t (T V*(s)-T V^{π_t}(s)) + (1-η C_t)(V*(s)-V^{π_t}(s)), the proof bounds T V*(s)-T V^{π_t}(s) ≤ γ (V*(s)-V^{π_t}(s)) with the justification 'T is a γ contraction map'. This is not a pointwise property: T is a γ-contraction in the sup norm, so the valid bound is γ ||V*-V^{π_t}||∞. The pointwise inequality fails even when C_t>0; e.g., in a two-state MDP with γ=0.5, π_t(s1)=a1, and π_t(a2|s2)=0.1, one has V*(s1)=2, V^{π_t}(s1)=1.1, and T V*(s1)-T V^{π_t}(s1)=0.9 > 0.5·0.9 = γ(V*(s1)-V^{π_t}(s1)). Theorem 2 may survive via a sup-norm contraction, but Theorem 3's proof invokes Lemma 2 pointwise before taking expectation over ρ; without a pointwise contraction, the recursion on J(π*)-J(π_t) is not established. This gap is independent of the acknowledged C_t positivity issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Softmax Policy Mirror Ascent (SPMA), a refinement of the policy mirror ascent method of Vaswani et al. [2021] that removes the normalization across actions and yields the linear-in-advantage update π_{t+1}(a|s) = π_t(a|s)(1 + η A^{π_t}(s,a)). The main theoretical claims are: (i) linear convergence for multi-armed bandits (Theorem 1) and a gap-dependent super-linear rate (Theorem 4); (ii) linear convergence in tabular MDPs with a constant step-size, with contraction factor α_t = 1 − η C_t(1−γ) where C_t := min_s {π_t(ã_t(s)|s) Δ_t(s)} (Theorem 2), matching NPG's rate without a distribution-mismatch term; (iii) an extension to function approximation (Algorithm 1) in which the per-iteration surrogate is a weighted softmax classification problem, convex for log-linear policies, with linear convergence to a neighborhood of the optimal value (Theorem 3, with an inexact-advantage version in Theorem 5); and (iv) experiments on tabular MDPs, MuJoCo, and Atari showing SPMA comparable to or better than MDPO, PPO, and TRPO. The proof of Theorem 2 rests on a lower bound C_t > 0 that the paper does not prove and only verifies empirically after excluding terminal states; the proofs of Theorems 3 and 5 rest on a pointwise application of the Bellman contraction that is not valid.","tokens_in":27317,"tokens_out":51118,"duration_ms":425637,"significance":"If fully supported, the results would be a solid contribution: a single algorithm family that matches NPG's tabular linear rate, avoids compatible function approximation in the log-linear FA regime, needs only convex softmax-classification subproblems per iteration, and shows strong benchmark performance without ad-hoc modification. The bandit results Theorems 1 and 4 are clean and appear correct, with elementary verifiable proofs. The paper is unusually transparent: it flags the unproved C_t > 0 condition in Section 3.3, documents in Appendix C.3 exactly where it fails (FrozenLake terminal states), suggests the appropriate fix, and releases code; the empirical protocol (multiple seeds, ablations on the inner-loop steps m, disclosure of hyper-parameter tuning) is reasonable. However, two load-bearing gaps remain: the unproved positivity of C_t, which makes Theorem 2's rate vacuous on MDPs with absorbing or tied-action states as stated, and an invalid pointwise contraction step in Lemma 2, which breaks the J-gap recursion in Theorems 3 and 5 as written. Both are fixable within the paper's scope, but they must be addressed for the advertised claims to hold.","major_comments":[{"comment":"The final step of the proof of Lemma 2 bounds T V*(s) − T V^{π_t}(s) ≤ γ (V*(s) − V^{π_t}(s)) with the justification 'T is a γ-contraction map'. This is invalid: T is a γ-contraction in the sup norm, which gives only T V*(s) − T V^{π_t}(s) ≤ γ ||V* − V^{π_t}||_∞, and the pointwise bound is false in general. A concrete failure with C_t > 0 and γ = 1/2: in a two-state MDP where at state s2 the two actions give rewards 1 and 0 and self-loop, and at s1 both actions lead to s2 with rewards 0.1 and 0, take π_t(a1|s1) close to 1 and π_t(a1|s2) = 0.1. Then V*(s2) = 2, V^{π_t}(s2) = 0.2, V*(s1) = 1.1, V^{π_t}(s1) = 0.2, while T V*(s1) − T V^{π_t}(s1) = 0.9 > 0.45 = γ (V*(s1) − V^{π_t}(s1)). This concern lands. For Theorem 2 the conclusion survives a repair: since C_t ≤ 1/(1−γ) and η < 1−γ imply 1 − η C_t > 0, taking the sup-norm in the displayed inequality before the contraction step gives ||V* − V^{π_{t+1}}||_∞ ≤ (1 − η C_t + η C_t γ)||V* − V^{π_t}||_∞ = α_t ||V* − V^{π_t}||_∞, so the tabular theorem is salvageable and its step-size condition remains sufficient. The FA theorems are not: the proofs of Theorems 3 and 5 apply Lemma 2 (respectively Lemma 3) per state and then take the expectation over ρ, so the claimed recursion J(π*) − J(π_{t+1}) ≤ α_t (J(π*) − J(π_t)) + β is not established. A repaired FA argument would need to bound E_ρ[T V* − T V^{π_t}] ≤ γ ||V* − V^{π_t}||_∞ ≤ (γ/ρ_min)(J(π*) − J(π_t)), which inserts ρ_min into the contraction coefficient (and, in the stated form, requires ρ_min > γ), or the theorem must be weakened to an initial sup-norm gap.","section":"Appendix B.1, Lemma 2 (used by Theorems 2, 3, and 5)"},{"comment":"The linear rate rests on C_t := min_s {π_t(ã_t(s)|s) Δ_t(s)} being strictly positive at every iteration; whenever C_t = 0 the contraction factor α_t equals 1 and no linear rate follows. The paper states that proving this 'is challenging' and defers to Appendix C.3, where C_t(s) = 0 is reported at the terminal states of FrozenLake (goal and holes, where Δ_t(s) = 0), so min_s over all states gives C_t = 0 for that MDP. As stated, Theorem 2 is therefore not supported for MDPs with absorbing terminal states or with states where two or more actions attain the maximum Q-value, and the remark that 'For rewards in (0,1), C_t(1−γ) is in (0,1) and depends on the initialization' is not justified (C_t(1−γ) ≤ 1 always, but positivity requires Δ_t(s) > 0 at every state). I agree with the fix suggested by the authors — restrict the theorem to states with Δ_t(s) > 0, or make C_t ≥ C_min > 0 an explicit assumption as in the cited related work (Liu et al. [2024, Thm 5.4]; Mei et al. [2021a, Lem 10]) — but the advertised exponential improvement over (accelerated) SPG and the match with NPG's rate depend on this condition, so the theorem needs a formal amendment rather than an empirical check. Note also that the step-size condition η < min{1−γ, 1/(C_t(1−γ))} depends on t; the 'constant step-size' statement implicitly requires a uniform lower bound on C_t across t.","section":"Section 3.3 / Theorem 2; Appendix C.3"},{"comment":"The bound on E1 := J(π_{t+1/2}) − J(π_{t+1}) is missing the 1/(1−γ) prefactor of the performance-difference lemma: the displayed chain starts with E1 = Σ_s d^{π_{t+1/2}}(s)⟨Q^{π_{t+1}}(s,·), π_{t+1/2}(·|s) − π_{t+1}(·|s)⟩, but the value-difference lemma (used with the prefactor explicit in Eq. (12) of Lemma 2) requires an additional factor 1/(1−γ). The subsequent inequalities consume one factor 1/(1−γ) for ||Q^{π_{t+1}}||_∞ ≤ 1/(1−γ) and one for the swap ρ ↦ d^{π_t}, so no factor accounts for the lemma prefactor; the stated β = √2/((1−γ)^2 ρ_min)√(ϵ_stat + ϵ_bias) therefore appears to be too small by a factor 1/(1−γ) (i.e., β should be √2/((1−γ)^3 ρ_min)√(ϵ_stat + ϵ_bias)). This does not affect the linear-rate claim, but the neighborhood constants in Theorems 3 and 5 are quantitatively wrong as written and must be corrected when the FA proof is repaired.","section":"Appendix B.2 / B.3, proofs of Theorems 3 and 5"}],"minor_comments":[{"comment":"The citation 'Liu et al., 1906' in the introduction and the matching reference entry (year 1906) are wrong; the paper is from 2019 (arXiv:1906.10306).","section":"Introduction; References"},{"comment":"The gap-dependent step-size η_{a,a'} = 1/|Δ(a,a')| is undefined when two arms have equal reward; the statement needs an assumption of distinct arm rewards or a convention (e.g., sign(0) = 0 with an arbitrary finite η).","section":"Appendix A.1, Theorem 4"},{"comment":"The definition Δ_min := min_{a ≠ a*} Δ(a*, a) makes the rate vacuous when several arms are optimal (Δ_min = 0); the theorem should either assume the optimal arm is unique or define Δ_min over strictly suboptimal arms.","section":"Section 3.1, Theorem 1"},{"comment":"The claim that the MDPO surrogate is non-convex 'even when using a tabular softmax parameterization' needs justification: for a fixed target distribution q, KL(h(z) || q) is convex in the logits z, so the displayed MDPO surrogate is convex in the parameters in the tabular (and log-linear) case; the convexity contrast with SPMA should be restated correctly.","section":"Section 4.1, MDPO comparison"},{"comment":"Typos such as 'sicne' for 'since' and inconsistent sub/superscript rendering (e.g., 'Ct' vs 'C_t', 'πt+1/2' vs 'π_{t+1/2}', 'Ã' vs 'ã') make several displays hard to follow; the appendix needs a proofread pass.","section":"Appendices B.2/B.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the journal's scope and I see no citation-pattern or novelty-disclosure concerns: the paper builds openly on Vaswani et al. [2021, 2024] and the self-citation rate is proportionate. My recommendation of major_revision is driven entirely by the technical gaps described in the major comments — the invalid pointwise contraction step (Lemma 2), the unproved C_t > 0 condition, and the β-scaling error — none of which suggests any lack of good faith, since the paper itself acknowledges the C_t issue and proposes the right fix. I would ask the authors to repair Lemma 2 into a sup-norm statement, re-derive the FA recursion (accepting a ρ_min-dependent contraction coefficient or an initial sup-norm gap), amend Theorem 2's statement to exclude states without a positive gap (or add C_t ≥ C_min as a formal assumption), and correct the β constants, then send for a further round of review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read 2411.12042. The core contribution is worth taking seriously: SPMA is a clean normalization-free restatement of the mirror ascent in logits from Vaswani et al., and the paper gives it constant-step-size linear convergence in tabular MDPs, a super-linear bandit rate, and a convex softmax classification surrogate for log-linear FA. Those are real additions, and the empirical work is honest enough to show TRPO-constrained beating SPMA on MuJoCo, even though the abstract overstates the comparison.\n\nThe soft spot is in the proof machinery, and it is load-bearing. Lemma 2 applies Bellman contraction pointwise: from δ_{t+1}(s) ≤ η C_t (T V*(s) − T V^{π_t}(s)) + (1−η C_t) δ_t(s), they bound T V*(s) − T V^{π_t}(s) ≤ γ δ_t(s) on the strength of 'T is a γ contraction map.' That inequality is false pointwise; T contracts in sup norm only. Your stress-test example is correct. The good news is Theorem 2 can be repaired by taking sup norms, which still yields ||δ_{t+1}||∞ ≤ α_t ||δ_t||∞. The bad news is Theorem 3 is not repairable that way: it needs the pointwise bound to take expectation over ρ and get the J-gap recursion with α_t on the J-gap. With only sup-norm control you get J-gap ≤ α_t ||δ_t||∞ + β, not the stated recursion. So the FA linear-convergence claim is not supported by the current proof.\n\nThe other known soft spot is C_t. The paper is upfront that C_t > 0 is only empirically verified, after excluding terminal states where the gap is zero. That should be baked into the theorem statements (as the authors themselves suggest in Appendix C.3), and the current statement is technically false without the exclusion.\n\nNet: this is a useful algorithm paper with a fixable gap in Theorem 2 and a serious gap in Theorem 3. The tabular result and the convex-surrogate observation should survive contact with referees. The FA proof needs a new argument or a weakened claim. I'd send it to review, with a request for major revision on the contraction step and the C_t qualification.","headline":"Solid, useful algorithm paper, but the FA convergence theorem relies on an invalid pointwise contraction step; Theorem 2 is repairable, Theorem 3 is not as written.","tokens_in":27854,"tokens_out":5561,"would_cite":true,"duration_ms":48321,"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":"A normalization-free softmax policy update converges linearly to the optimal policy in tabular MDPs, matching natural policy gradient, and needs only convex softmax classification under function approximation.","keywords":["softmax policy mirror ascent","policy gradient methods","natural policy gradient","linear convergence","mirror ascent","function approximation","log-linear policy","reinforcement learning"],"falsifier":"Run SPMA with exact gradients on a small tabular MDP such as FrozenLake and record both $C_t$ and the per-iteration contraction ratio $\\|V^{\\pi^*} - V^{\\pi_{t+1}}\\|_\\infty / \\|V^{\\pi^*} - V^{\\pi_t}\\|_\\infty$. Absorbing states where $Q^{\\pi_t}(s,a) = 0$ for all actions give $\\Delta_t(s) = 0$, hence $C_t = 0$ and $\\alpha_t = 1$; if the value error at those states ever dominates the $\\ell^\\infty$ norm, the uniform contraction stated in Theorem 2 cannot hold as written, and one can observe directly whether the ratio stays below $\\max_t \\alpha_t$.","tokens_in":26826,"feed_emoji":"📈","tokens_out":16135,"duration_ms":120793,"temperature":0.7,"pith_summary":"This paper tries to establish that a very simple policy update — multiplying each action's probability by one plus the step-size times its advantage, an update that stays a valid probability distribution without any normalization — converges to the optimal policy at a linear rate, the same rate that natural policy gradient achieves. The update, called SPMA, is mirror ascent in the space of logits with the log-sum-exp mirror map, and unlike NPG it needs no normalization across actions and no compatible function approximation when moving to large state-action spaces. If the theorems hold, a theoretically grounded policy gradient method becomes practical: each iteration reduces to a convex softmax classification problem, and experiments on MuJoCo and Atari show it matching or beating PPO, TRPO, and MDPO. The reason a reader should care is that linear convergence with a constant step-size closes part of the gap between RL theory, where accelerated softmax gradient methods only reach sublinear rates, and the algorithms deployed in practice.","feed_headline":"Softmax mirror ascent matches natural gradient's linear rate","feed_subtitle":"A policy update that is provably as fast as natural policy gradient, yet simple enough to run on Atari.","key_machinery":"The load-bearing object is the state-weighted log-sum-exp mirror map $\\Phi(z) = \\sum_s d^{\\pi_t}(s) \\ln(\\sum_a \\exp(z(s,a)))$; because $\\nabla\\Phi$ is exactly the softmax policy, the mirror-ascent update in logit space becomes a linear update on probabilities, $\\pi_{t+1}(a|s) = \\pi_t(a|s)(1 + \\eta A^{\\pi_t}(s,a))$, so no normalization across actions is needed. The contraction argument rests on Lemma 1, the inequality $\\sum_a \\pi_t(a|s)[A^{\\pi_t}(s,a)]^2 \\geq C_t \\max_a A^{\\pi_t}(s,a)$, where $C_t := \\min_s\\{\\pi_t(\\tilde{a}_t(s)|s)\\,\\Delta_t(s)\\}$ multiplies the probability mass on the greedy action by the action-value gap $\\Delta_t(s)$; the step-size condition $\\eta < 1/(C_t(1-\\gamma))$ keeps the contraction factor below one. In the function-approximation setting the same machinery becomes Algorithm 1: an unprojected tabular target $\\pi_{t+1/2}(\\cdot|s) = h(f_{\\theta_t}(s,\\cdot))(1 + \\eta A^{\\pi_t}(s,\\cdot))$, followed by a Bregman projection onto the realizable policy class that minimizes a weighted KL surrogate, which for log-linear policies is a smooth convex softmax classification problem solved by inner-loop gradient steps.","core_discovery":"On the paper's own terms, the discovery is a convergence theorem for a multiplicative policy update. Starting from the log-sum-exp mirror map $\\Phi(z) = \\sum_s d^{\\pi_t}(s) \\ln(\\sum_a \\exp(z(s,a)))$, whose gradient maps logits to the softmax policy itself, the mirror-ascent step becomes, per state, $\\pi_{t+1}(a|s) = \\pi_t(a|s)(1 + \\eta A^{\\pi_t}(s,a))$, which is a valid probability vector for $\\eta \\leq 1-\\gamma$ without any normalization. Theorem 2 states that with $\\eta < \\min\\{1-\\gamma, 1/(C_t(1-\\gamma))\\}$, the value error contracts as $\\|V^{\\pi^*} - V^{\\pi_T}\\|_\\infty \\leq (\\prod_{t=0}^{T-1} \\alpha_t) \\|V^{\\pi^*} - V^{\\pi_0}\\|_\\infty$ with $\\alpha_t = 1 - \\eta C_t(1-\\gamma)$, a linear rate matching NPG with a constant step-size and carrying no dependence on the distribution-mismatch ratio that can be exponentially large in other analyses. Theorem 3 extends the same contraction to function approximation: SPMA converges linearly to a neighborhood of the optimal value, where the neighborhood size is set by the excess risk $\\epsilon_{\\text{stat}}$ of solving the sampled surrogate, the policy-class bias $\\epsilon_{\\text{bias}}$, and, when advantages are estimated, the critic error. For log-linear policies the per-iteration subproblem is a convex softmax classification into $A$ classes, in contrast to MDPO's non-convex surrogate and NPG's compatible-function-approximation requirement.","pith_inferences":["Because the contraction factor $\\alpha_t$ depends on $C_t$ — the greedy action's probability times the action-value gap — an adaptive step-size rule that estimates $C_t$ on the fly and sets $\\eta$ accordingly is a natural testable extension; the paper flags adaptive step sizes as future work.","The bandit super-linear result suggests a gap-dependent step-size schedule could push tabular MDP convergence past the linear rate, although the paper does not make that claim.","Theorem 3's linear-to-a-neighborhood guarantee is stated in expectation over the starting distribution $\\rho$, while the tabular bound is uniform over states; a natural open direction implied by the analysis is whether uniform state-wise convergence returns once the bias and excess-risk terms vanish.","The experiments' finding that a conjugate-gradient trust-region solver degrades on CNN-based Atari actors while the KL-regularized log-ratio surrogate does not is evidence that the surrogate form, not just the trust region, drives robustness across representations; this goes beyond what the theorems establish."],"forward_implications":["In tabular MDPs, SPMA with a constant step-size converges at rate $O((\\eta C (1-\\gamma))^{-1} \\ln(1/\\epsilon))$, matching NPG's linear rate and beating constant step-size softmax policy gradient's $\\Theta(1/\\epsilon)$ and Nesterov-accelerated SPG's $O(1/\\sqrt{\\epsilon})$.","The tabular bound has no dependence on the distribution-mismatch ratio $\\|d^{\\pi^*}/\\rho\\|_\\infty$ that can be exponentially large in the state-space size, unlike adaptive step-size SPG analyses.","For log-linear policies, SPMA needs no compatible function approximation: each iteration is a convex softmax classification problem, whereas NPG extensions require solving a compatible-critic quadratic surrogate and MDPO's surrogate is non-convex even in the tabular case.","Under the excess-risk, bias, and exploration assumptions, SPMA with function approximation converges linearly to a neighborhood of the optimal value, and the neighborhood shrinks as samples and inner-loop steps increase.","In the multi-armed bandit case SPMA achieves linear convergence with any constant $\\eta \\leq 1$, and a gap-dependent step-size variant achieves a global super-linear rate."],"supporting_citations":[{"why":"introduces the surrogate-based policy update in the dual space of logits that SPMA refines by removing the normalization across actions.","marker":"Vaswani et al. [2021]"},{"why":"supplies the identity that the Bregman divergence of the weighted log-sum-exp mirror map is a weighted KL divergence between policies, the basis of the SPMA surrogate.","marker":"Vaswani et al. [2024, Lemma 11]"},{"why":"defines the natural policy gradient update, the tabular benchmark that SPMA matches and that in this setting is policy mirror ascent.","marker":"[Kakade, 2001]"},{"why":"provides the best-known linear convergence rate for NPG with constant step-size (their Theorem 5.4), the benchmark Theorem 2 matches and improves on in gap dependence.","marker":"[Liu et al., 2024]"},{"why":"establishes the $\\Theta(1/\\epsilon)$ rate for constant step-size softmax policy gradient that SPMA's logarithmic rate improves on.","marker":"[Mei et al., 2020]"},{"why":"proves the $O(1/\\sqrt{\\epsilon})$ rate for Nesterov-accelerated softmax policy gradient, the next comparison point SPMA beats.","marker":"[Chen et al., 2023]"},{"why":"supplies the theory of NPG with compatible function approximation, the log-linear policy analysis, and the procedure for sampling states from $d^{\\pi_t}$ used in Algorithm 1.","marker":"[Agarwal et al., 2021]"},{"why":"introduces MDPO, the practical NPG generalization whose non-convex surrogate is contrasted with SPMA's convex softmax classification subproblem.","marker":"[Tomar et al., 2020]"},{"why":"gives the policy gradient theorem used to express $\\nabla_z J(z_t)$ as $d^{\\pi_t}(s)\\pi_t(a|s)A^{\\pi_t}(s,a)$ in the SPMA update.","marker":"[Sutton et al., 1999]"}],"fun_headline_variants":["SPMA matches NPG's linear rate with simpler steps","Softmax mirror ascent: fast convergence without normalization","SPMA provably linear-converges, no compatible FA needed","Policy update: NPG-speed convergence, simpler assumptions","SPMA: linear convergence to optimal value, no normalization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the linear rate to hold, every state must keep some probability mass on its best action and a nonzero gap between best and second-best actions at every iteration, so that $C_t = \\min_s\\{\\pi_t(\\tilde{a}_t(s)|s)\\Delta_t(s)\\}$ stays strictly positive; the paper assumes this rather than proving it, and the appendix checks it numerically only after excluding terminal states where the gap is zero.","fun_headline_variants_meta":{"raw":{"variants":["SPMA matches NPG's linear rate with simpler steps","Softmax mirror ascent: fast convergence without normalization","SPMA provably linear-converges, no compatible FA needed","Policy update: NPG-speed convergence, simpler assumptions","SPMA: linear convergence to optimal value, no normalization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1588,"prompt_tokens":1139,"completion_tokens":449,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":755,"completion_tokens_details":{"reasoning_tokens":369}},"tokens_in":755,"tokens_out":449,"duration_ms":4905,"temperature":1.0,"reasoning_tokens":369,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:58:35.138840+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SPMA with exact gradients on a small tabular MDP such as FrozenLake and record both $C_t$ and the per-iteration contraction ratio $\\|V^{\\pi^*} - V^{\\pi_{t+1}}\\|_\\infty / \\|V^{\\pi^*} - V^{\\pi_t}\\|_\\infty$. Absorbing states where $Q^{\\pi_t}(s,a) = 0$ for all actions give $\\Delta_t(s) = 0$, hence $C_t = 0$ and $\\alpha_t = 1$; if the value error at those states ever dominates the $\\ell^\\infty$ norm, the uniform contraction stated in Theorem 2 cannot hold as written, and one can observe directly whether the ratio stays below $\\max_t \\alpha_t$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the identity that the Bregman divergence of the weighted log-sum-exp mirror map is a weighted KL divergence between policies, the basis of the SPMA surrogate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines the natural policy gradient update, the tabular benchmark that SPMA matches and that in this setting is policy mirror ascent."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes the $\\Theta(1/\\epsilon)$ rate for constant step-size softmax policy gradient that SPMA's logarithmic rate improves on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves the $O(1/\\sqrt{\\epsilon})$ rate for Nesterov-accelerated softmax policy gradient, the next comparison point SPMA beats."},{"cited_title":"M., Lee, J","cited_arxiv_id":null,"evidence_quote":"supplies the theory of NPG with compatible function approximation, the log-linear policy analysis, and the procedure for sampling states from $d^{\\pi_t}$ used in Algorithm 1."}],"review_version":1}