Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Fast Convergence of Softmax Policy Mirror Ascent

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2411.12042 v2 pith:E246QXTC submitted 2024-11-18 cs.LG cs.AIcs.RO

Reza Asad , Reza Babanezhad , Issam Laradji , Nicolas Le Roux , Sharan Vaswani This is my paper · ORCID
classification cs.LGcs.AIcs.RO
keywords softmaxpolicymirrorascentgradientmethodsnaturallinearconvergencefunctionapproximationlog-linearreinforcementlearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Appendix B.1, Lemma 2 (used by Theorems 2, 3, and 5)] 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.
  2. [Section 3.3 / Theorem 2; Appendix C.3] 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.
  3. [Appendix B.2 / B.3, proofs of Theorems 3 and 5] 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.
minor comments (5)
  1. [Introduction; References] 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).
  2. [Appendix A.1, Theorem 4] 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 η).
  3. [Section 3.1, Theorem 1] 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.
  4. [Section 4.1, MDPO comparison] 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.
  5. [Appendices B.2/B.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proofs are self-contained derivations; self-citations are lineage, not load-bearing.

full rationale

The central convergence claims (Theorems 2 and 3) are derived from the SPMA update, the value-difference lemma, Lemma 1's inequality, and standard Bellman operator arguments; none of these equations is defined in terms of the error being bounded. The contraction factor α_t = 1 − η C_t(1−γ) is expressed through C_t, a policy-dependent gap constant; the paper explicitly states that proving C_t > 0 is challenging and verifies it empirically in Appendix C.3, excluding terminal states where Δ_t(s) = 0. That is a support gap, not a circular reduction: the theorem gives a conditional bound in terms of C_t and does not fit C_t to the target suboptimality. Theorem 3 is a perturbation of the tabular recursion, with the projection/sampling error E1 bounded by the assumed excess risk and bias (Assumptions 1 and 2) appearing additively in the final neighbourhood; this is a stability argument, not an import of the conclusion. The log-sum-exp mirror map and the Bregman identity are taken from the authors' prior work (Vaswani et al. [2021, 2024]), but these are elementary, parameter-free identities and algorithm lineage, not uniqueness theorems, and the linear-convergence analysis itself is carried out in this paper. The pointwise γ-contraction step in Lemma 2 flagged by a skeptical reading is a mathematical correctness concern, not a reduction of a result to its own inputs; it does not constitute circularity. Accordingly, no specific circular step can be quoted.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

All assumptions are visible and mostly standard; the uncharged assumption with the largest weight is the positivity of C_t, which is load-bearing and only empirically checked.

free parameters (2)
  • outer-loop step-size η = grid-searched over {0.3,0.5,0.7,0.9,1.0}, selected by best AUC
    The theorems allow any η below a policy-dependent threshold, but the reported experiments tune η per environment by area under the curve, so the empirical comparisons include hyperparameter selection.
  • inner-loop optimization steps m = 5 in main experiments, 10 and 15 in ablations
    Number of gradient steps on the surrogate loss; empirical performance improves with m on MuJoCo, so the headline results depend on this choice.
assumptions (6)
  • domain assumption C_t > 0 for all iterations t
    Needed for α_t < 1; not proved, only empirically verified in Appendix C.3 after excluding terminal states.
  • domain assumption Assumption 1: excess risk |ℓ̃_t(θ_{t+1}) - min ℓ̃_t(θ)| ≤ ϵ_stat
    Assumed for all t in Theorem 3; standard but unverified for neural policies.
  • domain assumption Assumption 2: bias min_θ ℓ̃_t(θ) ≤ ϵ_bias
    Assumes the model class can represent a near-optimal surrogate; for neural nets this is an assumption about representation power.
  • domain assumption Assumption 3: exploration ρ(s) ≥ ρ_min > 0 for all states
    Full-support initial distribution; standard but restrictive for large state spaces.
  • domain assumption Assumptions 4 and 5: valid and bounded approximation error for the critic
    Used in Theorem 5 for the inexact-advantage extension; assumes the critic error is uniformly bounded by ϵ_approx.
  • standard math Bellman optimality operator T is a γ-contraction in sup norm
    Used in Lemma 2 and the FA proofs to bound T V* - T Vπt by γ(V* - Vπt). Standard background for discounted MDPs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Convergence of Softmax Policy Mirror Ascent." pith.science (2026). https://pith.science/paper/E246QXTC

@misc{pith2026241112042,
  author       = {Pith},
  title        = {Pith review of: Fast Convergence of Softmax Policy Mirror Ascent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E246QXTC}},
  note         = {Machine review of arXiv:2411.12042}
}
read the original abstract

Natural policy gradient (NPG) is a common policy optimization algorithm and can be viewed as mirror ascent in the space of probabilities. Recently, Vaswani et al. [2021] introduced a policy gradient method that corresponds to mirror ascent in the dual space of logits. We refine this algorithm, removing its need for a normalization across actions and analyze the resulting method (referred to as SPMA). For tabular MDPs, we prove that SPMA with a constant step-size matches the linear convergence of NPG and achieves a faster convergence than constant step-size (accelerated) softmax policy gradient. To handle large state-action spaces, we extend SPMA to use a log-linear policy parameterization. Unlike that for NPG, generalizing SPMA to the linear function approximation (FA) setting does not require compatible function approximation. Unlike MDPO, a practical generalization of NPG, SPMA with linear FA only requires solving convex softmax classification problems. We prove that SPMA achieves linear convergence to the neighbourhood of the optimal value function. We extend SPMA to handle non-linear FA and evaluate its empirical performance on the MuJoCo and Atari benchmarks. Our results demonstrate that SPMA consistently achieves similar or better performance compared to MDPO, PPO and TRPO.

Figures

Figures reproduced from arXiv: 2411.12042 by the authors.

Figure 1
Figure 1. On Atari games, where a CNN-based actor network is employed, [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. On MuJoCo control tasks, where a two-layer MLP actor network is used, [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. SPMA matches the performance of NPG and they both outperform SPG [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: SPG (green) is more sensitive to η compared to SPMA and NPG (blue and red) [PITH_FULL_IMAGE:figures/full_fig_p025_4.png]
Figure 5
Figure 5. Figure 5: CW environment: The top row (m = 25) shows that SPMA converges faster than MDPO as d decreases, while the bottom row (m = 50) shows the gap decreases as the number of inner loop optimizations increases [PITH_FULL_IMAGE:figures/full_fig_p026_5.png]
Figure 6
Figure 6. Figure 6: FL environment: The top row (m = 25) and bottom row (m = 50) show that SPMA and MDPO have similar convergence and both outperform SPG. The performance of both SPMA and MDPO improves as d increases (i.e., the bias decreases) and m increases (i.e., the optimization error…
Figure 7
Figure 7. Figure 7: SPMA with softmax tabular policy parametrization: After excluding terminal states, results confirm that Ct is lower-bounded by a positive constant [PITH_FULL_IMAGE:figures/full_fig_p027_7.png]
Figure 8
Figure 8. Figure 8: MuJoCo results for m = 10 (a) and m = 15 (b). As m increases from 5 ( [PITH_FULL_IMAGE:figures/full_fig_p030_8.png]
Figure 9
Figure 9. Figure 9: Atari results for m = 10 (top) and m = 15 (bottom). Increasing m does not necessarily lead to performance improvements [PITH_FULL_IMAGE:figures/full_fig_p031_9.png]
Figure 10
Figure 10. Figure 10: MuJoCo ablation on m: The rows correspond to the Hopper-v4, Walker2d-v4, HalfCheetah-v4, and Ant-v4 environments, respectively. As the number of inner loop optimization steps m increases, SPMA shows improvements in expected reward and becomes comparable to the fine-tu…
Figure 11
Figure 11. Figure 11: Atari ablation on m: The rows correspond to the BeamRider-v4, DemonAttack-v4, Alien-v4, and Amidar-v4 games. We observe that increasing m does not necessarily improve results across methods [PITH_FULL_IMAGE:figures/full_fig_p033_11.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation

    cs.LG 2025-05 conditional novelty 7.0 of 10

    Under explicit feature-ordering conditions, softmax policy gradient with linear function approximation converges to the optimal policy in stochastic bandits even with non-zero approximation error.

Reference graph

Works this paper leans on

47 extracted references · 24 canonical work pages · cited by 1 Pith paper

  1. [1]

    M., Lee, J

    Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res. , 22(98):1--76

    work page 2021

  2. [2]

    and Rebeschini, P

    Alfano, C. and Rebeschini, P. (2022). Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209.15382

    arXiv 2022

  3. [3]

    Armijo, L. (1966). Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics , 16(1):1--3

    1966

  4. [4]

    and Teboulle, M

    Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters , 31(3):167--175

    work page 2003

  5. [5]

    G., Naddaf, Y., Veness, J., and Bowling, M

    Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M. (2013). The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research , 47:253--279

    2013

  6. [6]

    and Russo, D

    Bhandari, J. and Russo, D. (2021). On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics , pages 2386--2394. PMLR

    work page 2021

  7. [7]

    Brockman, G. (2016). Openai gym. arXiv preprint arXiv:1606.01540

    arXiv 2016

  8. [8]

    Bubeck, S. et al. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8(3-4):231--357

    2015

Show all 47 references
  1. [9]

    Cesa-Bianchi, N., Mansour, Y., and Stoltz, G. (2007). Improved second-order bounds for prediction with expert advice. Machine Learning , 66:321--352

    2007

  2. [10]

    Chen, Y.-J., Huang, N.-C., Lee, C.-p., and Hsieh, P.-C. (2023). Accelerated policy gradient: On the convergence rates of the nesterov momentum for reinforcement learning. In Forty-first International Conference on Machine Learning

    2023

  3. [11]

    Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., and Madry, A. (2019). Implementation matters in deep rl: A case study on ppo and trpo. In International conference on learning representations

    2019

  4. [12]

    and Schapire, R

    Freund, Y. and Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences , 55(1):119--139

    1997

  5. [13]

    Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. (2017). Reinforcement learning with deep energy-based policies. In International conference on machine learning , pages 1352--1361. PMLR

    2017

  6. [14]

    Johnson, E., Pike-Burke, C., and Rebeschini, P. (2023). Optimal convergence rate for exact policy mirror descent in discounted markov decision processes. arXiv preprint arXiv:2302.11381

    2023 arXiv

  7. [15]

    Kakade, S. M. (2001). A natural policy gradient. Advances in neural information processing systems , 14

    2001

  8. [16]

    R., Varma, S

    Khodadadian, S., Jhunjhunwala, P. R., Varma, S. M., and Maguluri, S. T. (2021). On the linear convergence of natural policy gradient algorithm. In 2021 60th IEEE Conference on Decision and Control (CDC) , pages 3794--3799. IEEE

    2021

  9. [17]

    Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. In Advances in neural information processing systems , pages 1008--1014

    2000

  10. [18]

    G., de Witt, C

    Kuba, J. G., de Witt, C. S., and Foerster, J. (2022). Mirror learning: A unifying framework of policy optimisation. arXiv preprint arXiv:2201.02373

    2022 arXiv

  11. [19]

    Lan, G. (2023). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming , 198(1):1059--1106

    2023

  12. [20]

    W., Vaswani, S., Babanezhad, R., Schmidt, M., and Roux, N

    Lavington, J. W., Vaswani, S., Babanezhad, R., Schmidt, M., and Roux, N. L. (2023). Target-based surrogates for stochastic optimization. arXiv preprint arXiv:2302.02607

    2023 arXiv

  13. [21]

    Lazi \'c , N., Hao, B., Abbasi-Yadkori, Y., Schuurmans, D., and Szepesv \'a ri, C. (2021). Optimization issues in kl-constrained approximate policy iteration. arXiv preprint arXiv:2102.06234

    2021 arXiv

  14. [22]

    and Ying, Y

    Lei, Y. and Ying, Y. (2021). Sharper generalization bounds for learning with gradient-dominated objective functions. In International Conference on Learning Representations

    2021

  15. [23]

    Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2021). Softmax policy gradient methods can take exponential time to converge. In Conference on Learning Theory , pages 3107--3110. PMLR

    2021

  16. [24]

    Liu, B., Cai, Q., Yang, Z., and Wang, Z. (1906). Neural proximal/trust region policy optimization attains globally optimal policy (2019). arXiv preprint arXiv:1906.10306

    1906 arXiv

  17. [25]

    Liu, C., Zhu, L., and Belkin, M. (2022). Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis , 59:85--116

    2022

  18. [26]

    Liu, J., Li, W., and Wei, K. (2024). Elementary analysis of policy gradient methods. arXiv preprint arXiv:2404.03372

    2024 arXiv

  19. [27]

    Lu, M., Aghaei, M., Raj, A., and Vaswani, S. (2024). Towards principled, practical policy gradient for bandits and tabular mdps. arXiv preprint arXiv:2405.13136

    2024 arXiv

  20. [28]

    Mei, J., Gao, Y., Dai, B., Szepesvari, C., and Schuurmans, D. (2021). Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning , pages 7555--7564. PMLR

    2021

  21. [29]

    Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020). On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning , pages 6820--6829. PMLR

    2020

  22. [30]

    Munos, R. (2005). Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence , volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999

    2005

  23. [31]

    E., Haddadpour, F., Karbasi, A., and Kalogerias, D

    Nikolakakis, K. E., Haddadpour, F., Karbasi, A., and Kalogerias, D. S. (2022). Beyond lipschitz: Sharp generalization and excess risk bounds for full-batch gd. arXiv preprint arXiv:2204.12446

    2022 arXiv

  24. [32]

    Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming . John Wiley & Sons

    2014

  25. [33]

    Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N. (2021). Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research , 22(268):1--8

    2021

  26. [34]

    Schulman, J. (2015). Trust region policy optimization. arXiv preprint arXiv:1502.05477

    2015 arXiv

  27. [35]

    Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. (2015). High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438

    2015 arXiv

  28. [36]

    Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347

    2017 arXiv

  29. [37]

    Shani, L., Efroni, Y., and Mannor, S. (2020). Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 34, pages 5668--5675

    2020

  30. [38]

    Sutton, R. S. (2018). Reinforcement learning: An introduction. A Bradford Book

    2018

  31. [39]

    S., McAllester, D., Singh, S., and Mansour, Y

    Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (1999). Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems , 12

    1999

  32. [40]

    Todorov, E., Erez, T., and Tassa, Y. (2012). Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems , pages 5026--5033. IEEE

    2012

  33. [41]

    Tomar, M., Shani, L., Efroni, Y., and Ghavamzadeh, M. (2020). Mirror descent policy optimization. arXiv preprint arXiv:2005.09814

    2020 arXiv

  34. [42]

    C., Castro, P

    Vaswani, S., Bachem, O., Totaro, S., M \"u ller, R., Garg, S., Geist, M., Machado, M. C., Castro, P. S., and Roux, N. L. (2021). A general class of surrogate functions for stable and efficient reinforcement learning. arXiv preprint arXiv:2108.05828

    2021 arXiv

  35. [43]

    Vaswani, S., Kazemi, A., Babanezhad Harikandeh, R., and Le Roux, N. (2024). Decision-aware actor-critic with function approximation and theoretical guarantees. Advances in Neural Information Processing Systems , 36

    2024

  36. [44]

    Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning , 8(3-4):229--256

    1992

  37. [45]

    Xiao, L. (2022). On the convergence rates of policy gradient methods. Journal of Machine Learning Research , 23(282):1--36

    2022

  38. [46]

    S., Gower, R

    Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., and Xiao, L. (2023). Linear convergence of natural policy gradient methods with log-linear policies. In International Conference on Learning Representations

    2023

  39. [47]

    and Zhang, T

    Zhong, H. and Zhang, T. (2024). A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. Advances in Neural Information Processing Systems , 36

    2024

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.