# Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients arXiv: https://arxiv.org/abs/2403.19448 ยท HTML: https://mlsanity.com/paper/2403.19448/ ## Key facts - Cited by 5 papers in the map (data through 14 Oct 2026). - Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. - Builds on 32 of its 65 references that are in the map. - First posted on arXiv 28 Mar 2024. ## Placed in - Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/) ## Builds on (most cited first, 30 of 32) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017) - [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019) - [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018) - [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020) - [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017) - [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020) - [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021) - [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019) - [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022) - [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016) - [The Optimal Reward Baseline for Gradient-Based Reinforcement Learning](https://mlsanity.com/paper/1301.2315/) (2013) - [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021) - [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020) - [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022) - [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023) - [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022) - [Hessian Riemannian gradient flows in convex programming](https://mlsanity.com/paper/1811.10331/) (2018) - [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018) - [A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces](https://mlsanity.com/paper/2310.02951/) (2023) - [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022) - [Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation](https://mlsanity.com/paper/2106.04096/) (2021) - [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021) - [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022) - [Invariance Properties of the Natural Gradient in Overparametrised Systems](https://mlsanity.com/paper/2206.15273/) (2022) - [The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs](https://mlsanity.com/paper/2110.07409/) (2021) - [Hessian informed mirror descent](https://mlsanity.com/paper/2106.13477/) (2021) - [A Geometric Embedding Approach to Multiple Games and Multiple Populations](https://mlsanity.com/paper/2401.05918/) (2024) ## Built on by (most cited first, 5 of 5) - [Solving Inverse Problems via Diffusion-Based Priors: An Approximation-Free Ensemble Sampling Approach](https://mlsanity.com/paper/2506.03979/) (2025) - [Embedding Safety into RL: A New Take on Trust Region Methods](https://mlsanity.com/paper/2411.02957/) (2024) - [Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes](https://mlsanity.com/paper/2406.04163/) (2024) - [Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias](https://mlsanity.com/paper/2505.02614/) (2025) - [Policy Gradient for Continuous-Time Robust Markov Decision Processes](https://mlsanity.com/paper/2606.04335/) (2026) ## Abstract (arXiv) Kakade's natural policy gradient method has been studied extensively in recent years, showing linear convergence with and without regularization. We study another natural gradient method based on the Fisher information matrix of the state-action distributions which has received little attention from the theoretical side. Here, the state-action distributions follow the Fisher-Rao gradient flow inside the state-action polytope with respect to a linear potential. Therefore, we study Fisher-Rao gradient flows of linear programs more generally and show linear convergence with a rate that depends on the geometry of the linear program. Equivalently, this yields an estimate on the error induced by entropic regularization of the linear program which improves existing results. We extend these results and show sublinear convergence for perturbed Fisher-Rao gradient flows and natural gradient flows up to an approximation error. In particular, these general results cover the case of state-action natural policy gradients.