Rank-1 Approximation of Inverse Fisher for Natural Policy Gradients in Deep Reinforcement Learning
Authors: Yingxiao Huo
Satya Prakash Dash
Radu Stoican
Samuel Kaski
Mingfei Sun
Venue: Accepted by TMLR ()

Abstract: Natural gradients have been long studied in deep reinforcement learning due to its fast convergence properties and covariant weight updates. 
However, computing natural gradients requires inversion of Fisher Information Matrix (FIM) at each iteration, which is computationally prohibitive in nature. 
In this paper, we present an efficient and scalable natural policy optimization technique which leverages a rank-1 approximation to full inverse-FIM. 
We theoretically show that under certain conditions, rank-1 approximation to inverse-FIM converges faster than policy gradients and under some condition, enjoys the same sample complexity as stochastic policy gradient methods.
We benchmark our method on a diverse set of environments and show that our methods achieve superior performance than standard trust-region and actor-critic baselines.

Published in Transactions on Machine Learning Research (02/2026)
Rank-1 Approximation of Inverse Fisher for Natural Policy Gradients in Deep Reinforcement Learning
Yingxiao Huo
Department of Computer Science The University of Manchester
Satya Prakash Dash
Deportment of Computer Science The University of Manchester
Radu Stoican"
muduestoican@mmnchhseera...k
Department of Compuler Science The Universily of Manchester
Samuel Kaski
swmuel.uakkiiimanccheeettr..
Department of Computer Science The University of Manchester
Aolto University
Mingfei Sunt
winngfes.ssu@@mmanccssserr......
Department of Computer Science The University of Manchester
Reviewed on OpenReview: ottpe:///penreeveeu. net/ forum? ko8Kn7156
"Equal contribution;
'Corresponding author
Abstract
Natural gradients have long been studied in deep reinforcement learning due to their fast convergence properties and covariant weight updates. However, computing natural gradi- ents requires inversion of the Fisher Information Matrix (FIM) at each iteration, which computationally prohibitive in nature. Tn this paper, we present efficient and scal- able natural policy optimization technique that leverages rank-1 approximation to full Inverse-FIM. We theoretically show that under certain conditions, a rank-1 approximation to inverse-FIM converges faster than policy gradients and, under some conditions, enjoys the same sample complexity as stochastic policy gradient methods. We benchmark our mothod on diverse set of envirouments and show that achieves superior performance to standard actor-critic and trust-region baselines.
1 Introduction
Policy gradient methods (Sutton et al. 1999 have emerged of the most prominent candidates for modern reinforcement learning (RL). Specifically, they have widespread adoption in deep RL, where they incorporate differentiable policy parametrization and function approximators to help policy gradient methods scale and learn robust controllers for higl-dimensional state spaces (Arulkumaran et. al. 2017 Wang et al.) 2022). Despite this, fundamental limitation of policy gradients is that RL objectives tend highly non-concave nature. Consequently, algorithms based on standard gradient descent, such as REINFORCE (Williams 1992), are prone to getting stuck at sub-optimal local minima when training high- dimensional policies. This is due the gradient giving only the direction in which policy's parameters

---

Published in Transactions on Machine Learning Research (02/2026)
should be optimized, without indicating the size of the optimization step (Martens 2020
Step size selection
is, therefore, non-trivial. Small steps lead to stable but slow and sample-inefficiet training. On the contrary, large steps can cause unstable updates. This is particularly dangerous in RL, as unstable policies collect poor data, making it difficult for the agent to recover and escape local optima (yan Hoeswijk 2022
One approach to reduce this sub-optimality and achieve stable training with large steps is to incorporate the geometry of the loss manifold into account and thus consider natural gradients (Amari) 1998). Specifically, when applied to policy gradient RI, where policies are modeled as probability distributions, the Fisher infor- mation matrix (FIM) is used to precondition the policy gradients, which gives rise to natural policy gradient (NPG) methods (Kakade) 2001 Bagnell & Schneider 2003 Peters et al., 2005). NPG algorithms are of interest because they generally tend to converge faster and have superior performance compared to their standard policy gradient counterparts (Grondman et al. 2012). More recently, NPGs established the roots of some of the most popular RI. algorithms used practice, including Trust Region Policy Optimization (TRPO) (Schulman et al. 2015a), Proximal Policy Optimization (PPO) (Schulman et al. 2017). Further- more, the study of NPG methods is also motivated by their success in real-world applications (Richter al.
2006
Su et al. 2019
One of the main drawbacks of NPG algorithms is the high cost of computing and inverting the FIM. Storage is also an important concern, as for a parameterized policy, the FIM is a square matrix with dimensions equal to the number of parameters. Naturally, this issue becomes especially limiting when policies are parameterized by deep neural networks. In practice, NPG algorithms usually avoid computing the inverse Fisher directly and instead rely on approximations. A simple option to only consider the diagonal elements of the FIM [Becker & Lecun 1989 LeCun et al.) (002),, leading to efficient inversion and low storage requirements. A more sophisticated approach is K-FAC (Martens & Grosse 2015), which uses Kronecker products to approximate the FIM efficiently. As an alternative to the true FIM, the empirical FIM can be computed from samples, which is especially convenient when the required underlying probability distributions are unknown (Schraudolph] 2002). Hessian-frec methods give a less direct approach to using the FIM without ever explicilly compuling or storing it [Martens] 2010). As an example, TRPO avoids computing the FIM, calculating the Fisher-vector product directly instead. Despite the extensive literature on the subject, choosing the right way of approximating natural gradients is usually not straightforward. This choice often involves trade-off between computational efficiency and approximation accuracy.
The goal of this work is to bridge the theoretical convergence properties of NPG with a practical, fast, and computationally feasible approach to invert FIM for high-dimensional reinforcement learning tasks. In this work, we use the empirical FIM as an alternative to the FIM and incorporate the Sherman-Morrison formula for efficient inversions. We propose a rank-1 approximation to avoid explicit matrix operations, keeping the time complexity at (dd for a policy parameterized by a vector 0 of dimension d, without the need for inner loops like conjugate gradient, thus balancing computational cost and accuracy of curvature information.
The main contributions are listed below:
1. We provide fast and efficient way to compute the inverse FIM, which can be computed in O(d) complexity rather than Old²) for naive inversion of FIM.
2. We thcorctically show that under cortain conditions, our NPG approximation using the empiri- cal FIM and Shernon-Morrion formula enjoys global convergence when using log-linear function approximators.
3. We also prove that the error induced in the policy update due to this rank-1 approximation is bounded and reduces with the increase in iterations.
4. We propose a novel policy gradient algorithm using this update: Sherman-Morrison Actor Critic (SMAC). We show that SMAC achieves faster convergence in diverse OpenAl Gym tasks (classic control and MuJoCo environments (Todorov et al.) 2012)), compared to vanilla policy gradient, Adam, and trust-region methods that use Conjugate Gradient solvers to approximate the direction of natural policy gradient.
2

---

Published in Transactions on Machine Learning Research (02/2026)
2
Related Work
Gradient descent updates all the parameters of a model equally, meaning that weights are considered to be inside a Euclidean space. However, the loss function of the model actually induces a Riemannian manifold space. Therefore, the size of a gradient step does not reflect the true scale of change of the model's loss. Consequently, standard gradient descent methods are highly sensitive to the choice of step size. To avoid this issue, Amari first framed gradient- gradient descent. algorithm, which uses the update direction F(0)-1V)((() with the FIM F(0) and objective (() (Amari 1998.. Here, the FIM is covariant measure of the amount of information contained in the parameters (Amari 1998). Kakado extended this idea to reinforcement learning and coined the natural policy gradient (NPG) algorithm (Kakade 2001). However, the computational cost associated with calculating the FIM, especially in models with a. large number of parameters, can be prohibitively expensive. Therefore, practical implementations of natural gradients rely on approximations instead. We thus summarize the related work on these approximations as follows.
learning on a Riemannian manifold, introducing the natural
Kronecker-factored Approximate Curvature Block-diagonal approximations to the natural gradient,
such K-FAC (Martens & Grosse 2015) and subsequent refinements (Zhang al. 2023 Ren & Goldfarb,
2021 Bahamou et al. 2023 Benzing 2022), have been widely adopted due to their computational efficiency.
Related variants have also been developed for reinforcement learning (Wu et al. 2017
Hessian-Free Methods Hessian-free optimization (Martens 2010 another method for computing natu- ral gradients, has seen widespread use in reinforcement learning, particularly due to its superior performance in TRPO [Schulman et al.) 2015a). This approach employs the conjugate gradient (CG) method solve the associated linear system, thereby avoiding explicitly storing FIM, keeping memory usage comparable to single seward-backwald pass. However, CG requires several additional reduces computational efficiency. In addition, due to the limited precision of CG estimation, practitioners usually perform an extra KL-based line search to adapt the step size (Schulman et al. 2015a).
backwad passos, which
Empirical Fisher Information The empirical Fisher (EF) estimates the Fisher information matrix by replacing the exact expectation over gradient outer products with the outer product of the gradients com- puted from individual samples (Yang et al., 2022). However, the empirical Fisher's simple estimate has been frequently criticized for deviating significantly from the true Fisher, and its limitations have been analyzed in many studies (Martens 2020 Kunstner et al. 2019). Nevertheless, its very low computational cost has enabled broad range of successful applications [Roux et al. 2007 Ren & Goldfarb 2019 Wu et al. 2024) Compared with the extensive use of K-FAC and Hessian-free methods in RL, the EF approach remains under-explored and is seldom applied in this domain.
3 Preliminaries
Markov decision process (MDP) We consider an MDP state space S, action space A, transition kernel P(s'|s [s, a), bounded reward function r A + [-R, R). and discount factor y E 10. We also consider a stochastic policy (a(ass) with parameters E R that induces a trajectory distribution TT(T,) over 72 (sh. ab st .....
R, with a continuous or discrete
Performance objective and policy gradient Under the standard actor-critic framework, the RL ob- jective is given by the expected discounted return of mp:
8c Σ r' r(s)
j(0) = E Eywaa
(1)
To maximize Eq. 1 the advantage actor-critic (A2C) (Mnih et al.
2016) algorithm uses an advantage function
A(s, a) Q(s a) V(s), defined through the critic's state-value and oction-value functions
V V(s) EySAY [Gr 8t =]] Q(8, a) Erano [Ge 8t 8, az a]
3

---

Published in Transactions on Machine Learning Research (02/2026)
where G₁ = =I=0 1'r ((S4)); Following the policy gradient theorem, the A2C gradient is then given by
(0) E EETWT
Vo Tog A(s,, ai).
Fisher information matrix and Natural Policy Gradient For the exponential-family policy To(- {s), the natural Riemannian metric in parameter space can be expressed in terms of state visitation distribution induced by the same policy ae s) as
F. (0) (a)))())s) Ve log (a Va log (a(s))
The invariant FIM (0) can be obtained by averaging over the state visitation distribution leading to the natural gradient update
gh+1 0¹ - Fo(0h) = -E
(F, [0)].
where 7 is the step size and de represents the state visitation distribution under a policy Ty and initial state distribution p:
8
8 (s) (1 - 7) E ExO
7 P((:
80, To) + 7p(s))
Empirical Fisher information Replacing the expectation in F(0) with sample average over one single trajectory = a gives the empirical Fisher approximation
N Σ ve log ne (a.ls:)) [og
F()) = N
Sherman-Morrison formula The Sherman-Morrison Morrison formula efficiently computes the inverse of a matrix after a "rank-1 update" has been applied to it, provided that the inverse of the original matrix was already known (Sherman & Morrison, 1950). Suppose X E Raxx is an invertible square matrix and u, v E R are column vectors. Then X uuv is invertible iff
1 1+ 1+ X
0.
In this case, the Sherman-Morrison formula allows the computation of the inverse
(X + To X-1 X uv
- -1
(3)
I X-1u
If X-1 already known, this matrix inversion formula can bypass computing the inverse (X + un T directly, avoiding the cubic scaling with the dimension of X. Instcad, the update only requires three vector operations, which scale linearly with the dimension of X. This update can use the full power of current GPU hardware platforms, since computing vector operations avoids the time-intensive matrix inversion processes. Methods such as Singular Value Decomposition (SVD), which decomposes a matrix into its singular values and vectors, and LU decomposition, which factors a matrix into a lower triangular matrix (T.) and an upper triangular matrix (U), are much slower than the simple operations used in our approach.
be heavily parallelized. At the same time, it
For the rest of the paper, we abbreviate the actual FIM 8h F(O*) as F and the estimate of batch fok for notational convenience.

---

Published in Transactions on Machine Learning Research (02/2026)
Sherman-Morrison for computing the inverse Fisher The Sherman-Morrison formula be used to incrementally build the inverse of the EF (Fh)-1 at step k by reusing the previous estimate (Fi-1)-1 (Singh & Alistarh
2020
(F ge
( + V log (alaas)Vo log n (a) [
g
(F (F Ve lo To (a log (a(s)) (FRR)))- gt.
(
Vo ma (F*-1) Vo log no (a|s)
Other approaches compute fresh EF at cach iteration gradient
Wu et al. 2024 which is used in the natural
A (AI + Vo log lolloll)mms log (a(as))
where À > 0 is a fixed damping coefficient.
4 NPG Approximation
We adopt matrix-free free scheme for approximating the FIM to reduce memory and computational cost. At each step, we form a local empirical Fisher from the current batch, add a damping term X, and apply the Shorman-Morrison formula to compute the inverre-vector product F(0)=1a directly, where g is the policy gradient. This approach requires (d) memory.
This formulation captures the local curvature of the loss landscape using only the current gradient direction. The damping term ensures numerical stability and prevents the update direction from being overly sensitive to individual gradients. Compared to the exact FIM, this method strikes balance between computational efficiency and curvature-infrrmed updates.
4.1 Matrix-Free Update
The time and space complexity of explicitly computing and storing the FIM is O(d).. So, maintaining a previous estimate (f+-1)-1 and applying (f<t)-1g can be infeasible for large-scale models. In this work, we instead use the Sherman-Morrison and the policy gradient.
Morrison formula to directly compute the product of the inverse empirical Fisher
We consider one-sample empirical Fisher with damping, take (Sk, ax) d (5) (a 8), that is, one state-action pair visited when rolling out Tok
F AI + (+ AI + Vo log ma (axlss, Vo log Tgy (ax (Qx]88)]
Applying the Sherman-Morre Morrison formula then yields:
(f (AI + Vo log Ton (a V log Ton
(a Ton Va log Th (a s*) V, log To (*
()
I
x
Vo log nu ) Vo log gan (at))))
Fb
x
X2 Tr)
(4)
Multiplying the inverse Fisher by the gradient gives the natural policy gradient update direction
Vo log Tas (a" * Va log Tgn (T* g²
Ad, = 1 (g
(5)
X2 + AV log a (a )*) Ve log Taa (a (a*1s*)
Vo log Ta* (ak (5* ) A(s, a) is the one-sample policy gradient update direction, A(s, a) is the advan- tage estimate and 7 is the step size.
where n* =
This update involves only a matrix vector operation and vector outer product, making its time and memory complexity comparable to that of first-order methods, such stochastic policy gradient.
5

---

Published in Transactions on Machine Learning Research (02/2026)
4.2 Convergence Analysis
We take inspiration from the global convergence guarantees provided by Agarwal et al. (2021) and follow-up work by Liu et al. (2022), which improved the global convergence results. To prove the global convergence, we take a standard Lipschitz policy assumption (Assumption 3 and average performance difference bounds (Lemma 8 from Liu et al. (2022)) and Lemma 2 We provide a theoretical analysis showing that the Sherman Morriison rank-1 approximation to the inverse Fisher achieves global convergence. Under strong convexity assumptions (already taken in Kakade (2001); Peters et al. (2005)) of the FIM, we show that the average performance between the Sherman-Morrison update and the optimal policy x' can be bounded in terms of the the variance of policy gradient estimator (a²), discount factor (7), the error in the Advantage estimate induced by the neural approximator (Ebias) and the Lipschitz constant of the policy gradient (LJ). We defer the proof to the appendix, and state the final theorem here.
Theorem 1. If we take the stochastic Sherman- Sherman-Morrion Morrison policy update in Equation and take nf = Al."" K ==0 <=0 (a-T N= N ) and H = (ogg( (1--7))) Then, have
K B[J(0*) S 1 + E.
1
Vetios
J(x*)
K
k=
In lotal, stochastic PG samples Ô advanlage function, and is an arbilrary precision level and Ô hides all the logarillmic fuctors.
trajeclories, where Ehios is the approzimation ervor from the
Our proof relies on the fact that performance bound given by Lemma 3 Liu et al. 2022] and we prove that this result holds with sample complexity of KN (T-T))))) where N is the number of trajectories per update and K is the number of updates. This shows that to get an accurate policy, one needs (222) samples, and when the horizon H and number of samples N are large enough, then can be reduced to arbitrary precision. We would like to point out that the non-degeneracy compatible function approximator [Assumption 4 are standard assumptions in stationary convergence of PG adapted by Agarwal al. (2021) and can be realized by gaussian and softmax parametrized policies (See Section B.2 Liu al. [2022] and Section 8 of Ding et al. (2022) for further discussion). For compat function approximation the value of Ebios be arbitrarily small for neural approximators (Wang et al,
FIM [Assumption / and
2019) and is exactly zero for softmax parametrized policies (Ding et al. 2022). Detailed derivations can be
found in Appendix 2
Note that, the obtained bound stems from average regret to the global optimum and rocently Yuan et al. (2022) have obtained (3) bound on the condition when the approximator error is negligible, or Ebias 0, but with a finite Ebius the authors have recovered a bound of Ö(==*), similar ours.
4.3 A Toy Problem
= 0; r +1
a= 0: r +2
a a= 1==0
x x= 0
I =
1;
Figure 1: An example two-state MDP where each state ø has two control actions, one which self-transition with reward +1 or +2) and another control that transitions the initial state to the other state with zero reward).
We adopt a classical weinforeement-eerriie MDP problem, been used by Kakade 2001 & Bagnell & Schneider 2003) with two states (0, 1) and two discrete actions a E {0, 1). The policy is parameterized

---

Published in Transactions on Machine Learning Research (02/2026)
by vector 0 180,01],, where each component governs independent Bernoulli distribution actions. Let the probability of taking action
0 in state x be
1 e Ta x 1) cº1
Ta 0)
(6)
(7)
where Ap scales the first policy parameter and is used to lest scaling invariance. Assume that the agent starts at state 0, then the objective function of the the MDP can be expressed as
((0) To a 0 0) + 2(1 (a 0 0)) ae 0 = 1).
(8)
Note that, for converged policy the agent shall transit to state 1 and remain there and the final return shall be +2 which is the the action of self transitioning at state x = 1. So start from writing the analytic policy gradient vector,
To - m0) - 2
VeJ(0)-
(9)
-2(1 TT) (1-11111))) mT)
and the FIM can be calculated as:
22 To(1 mo)
0
F(O)
(10)
1 - mi)
Then NPG update direction can be evaluated as
2TT
ÔNPG = P(00) =
Ap
(11)
2(1 - TT0)
This direction eliminates the dependence on the arbitrary scaling Ap, making it invariant under smooth reparameterizations of as shown by Bagnell & Schneider (2003).
Now the SM update direction in this setting can be evaluated as
1 7
F(O)
dSM~
VeJ(O)
(12)
X+Tr(F(0))
X3 m =1) 2
Ap To - -To - -2TT)
X2 + X { no no) + ग (1 )]
(13)
2 2 (1- TT)
(-2(1-To)m TO) TT)) X2 + > 1233 no( Tp) (1 11)
where is the damping factor. This type of approximation although looks highly nonlinear but we can carefully lune À and make the update less sensitive Ap-
As shown in Fig 2 the plot in the left panel update the trajectories in the log-odds space for all damping settings AÇ E f0.75, 1.0, 2.0), Compared with the PG updates, the SM updates follow direction much closer to that of NPG and maintain a step size more consistent. And PG updates deviate significantly as changes, showing its sensitivity to parameter scaling. The plot in the right panel shows the returns over iterations, where SM update achieves faster and more stable improvement than PG and approaches the same final performance as NPG. Therefore, the SM update preserves the geometric characteristics of the NPG while being more computational efficient. in high-dinensional cases.

---

Published in Transactions on Machine Learning Research (02/2026)
Palicy updates in log adds space
Return over time
1.8
log- ug-oddss logieta O)y 1ih--11la---m
6-
Expected netum)(R)
4-
1.4
Alpha-- As
4- 0.75
A--
NPG
1000
log-odds [0gmitam00-==00mmm--11-01-11
lteration
Figure 2: Results on toy MDP problem: Left side plot represents the log-odds plot for state r = 0 in x-axis and state x y-axis and the right side plot shows the returns over iteration for PG, NPG and SM updates for different Ap (0.75, 1.0, 2.0} cocfficient in policy paramotrization. Note that, the least intense lines represent PG direction, medium NPG and maximum deep lines represent SM update direction.
4.4 SM-ActorCritic
We plug our approximation into a standard A2C algorithm. Let тæ be the policy (actor) and Vo the value network (critic), with paramelers 0 and é, respectively. At each iteration, we collect T transition luples and compute the generalized advantage estimator [Schulman et al, 2015b GAE) with a fixed ÂGAE E [0,
8, = + Vo(8++1) Vo(ss),
(14)
T-1-r
A
Σ
(TdGAE)' 8:41-
(15)
The critic is then trained by minimizing the mean squared error over the batch:
T-1 Σ RR - vo(st)) 1=
(o) T
using the Adam optimizer with learning rate of a, where R. A, Vo(se) is the Monte-Carlo return larget. The actor is updated by single natural policy gradient step obtained from the matrix-free free Fisher inverse. Since our method is based on Sherman-Morrion formula, we call the resulting algorithm Sherman-Morrison Actor-Critic (SMAC), which is detailed in Algorithm
5 Experimental Setup
To evaluate the performance of our proposed approach, SMAC, we provide experiments several environ- ments and compare against. four baselines. We begin with three simple control environments, before moving to six MuloCo tasks (Toooro et al. 2012). For all experiments, used the Gymnasium framework Towers et al. 2024
We implement SMAC on lop of the A2C algorithm. In all environments, we evaluate SMAC against three baselines. To measure the benefits of using our NPG approximator, we consider an algorithm that similar SMAC in all aspects, except that it uses first-order updates instead of natural gradients. This is equivalent A2C with a simple stochastic gradient descent (SGD) optimizer, which we denote AC-SGD, To ensure fair comparison to vanilla A2C, also compare against the AC-Adam baseline, where A2C is trained
8

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm SM-ActorCritic
input: steps per update T, step size y,, damping À initialise 8, Φ
3: for iteration A: = 0, 1... do
4: rollout T steps, store (s a², r")
5: compute advantages Au with GAE
6: for all samples do
7:
ge +- Vplog To (o (als)A(s,a))
8: gh+1 + 0h + o7 Fx ge with equation 5 end for
10: update critic: @h+1 Φ v E. CR vo(s)))²
11:
end for
using the more complex Adam optimizer. We also test SMAC against other NPG approximators. The AC- CG baseline uses the conjugale gradient algorithm to directly compute the NPG during the A2C update, without ever computing storing the Fisher information matrix itself, similarly to TRPO (Schulman et al. 2015a). Finally, the second NPG approximator uses the Kronecker-factored approximate curvature (Martens) & Grosse 2015 KFAC). Our implementation, AC-KFAC, follows the application of KFAC to actor-critic algorithms as proposed by Wu et al. (2017), but omits the trust region.
SMAC and all the baselines we compare against compute advantages using the GAE. This is because GAE handles the bias-variance trade-off better than the simpler advantage estimator used by A2C, and has been shown to be effective in high-dimensional continuous control (Schulman et al. 2015b).
For each of the five algorithms in each environment, we train five models using different random seeds. The results reported throughout training are averaged over these seeds, with standard deviations included. We evaluate agent performance using (undiscounted) returns, averaged across episodes. Besides the maximum average returns achioved, we are also interested in convergence spood.
Furthermore, also track the average log-probabilities of the actions taken. We treat these measure of the agents' confidence in their actions. We therefore expect well-performing policy to become more deterministic, achieving both higher log-probabilities and higher returns. On the contrary, we can also diagnose overconfident policies, where an increase in fog-probabilities does not correlate to an increase in returns. The agent may therefore prematurely converge to an overly deterministic sub-optimal policy, which is likely to hinder exploration and thus future improvements. We report the probbbbbasilities measured in the supplementary material.
In all environments, episodes have horizon of 1000 timesteps. To increase the readability of the plots, group timesteps into 100 bins with no overlap and report the average of each bin. We apply additional smoothing by computing an exponentially weighted mean over the bins, with a smoothing factor of 0.1. The average performances and standard deviations we report are then computed from these binned and smoothed results. However, for the sake of completeness, we also plot the raw, unbinnod, and unsmoothed results in the supplementary material.
5.1 Practical Method
The matrix-free updates operate on a single trajectory sample, Although the per-step cost only Od), when applying this per-sample scheme to full batch of size b, the update must be exccuted times, so the effective time complexity for the batch becomes O(bd), so the computational cost can be high to update a whole batch.
9

---

Published in Transactions on Machine Learning Research (02/2026)
AC-SGD
AC-Adam
AC-CG
AC-KFAC
SMAC (Ours)
Acrobot
86.2 + 4.7
88.4 + 5.7
-93.3 + 11.6
-170.7 16.5
-94.1 + 17.0
Cartpole
962.3 + 38.5
989.5 + 14.1
977.9 = 34.4
331.4 + 142.3
973.4 + 49.5
Pendulum
2216 + 678
5731 + 272
190 + 23
-1161 + 15
2226 + 1138
Half Cheetah
-1672 10.6
-646 9.7
1766 864
513 + 50.3
2936 946
Hopper
180.5
303.8 + 23.9
172.7 10.9
305.0 33.6
331.2 20.9
Swimmer
3.0
17.3
23.8 = 1.7
24.2 2.5
28.5 - 1.4
Walker
213.4 + 36.9
79.3 + 58.7
229.8 + 38.3
83.7 + 72.9
204.1 + 58.0
Humanoid
4539 + 171
3105 + 345
3175 + 1445
260.8 + 11.15
4625 + 274
Pusher
433.6 +: 41.6
568.3 +: 16.4
-41.0 + 35.6
1086.3 + 16.2
400. 2 + 31.5
Table 1: Average returns per episode, mcasured the end of training, for cach task in both classic control and MuJoCo environments. All results are averaged over 5 seeds (+ standard deviations).
Hast Cheetsn V5
Hopper VS
Swimmer VS
-130
SMAG-tarch
AC-300
-03
400
20
-007
Stops
3005s
Blopo
Figure 3: Effect of Batch Size.
To investigate this trade-off, we evaluate alternative that uses the average gradient of log- Nog-probability over all sampled state-action transitions in the batch:
B E vo log (a 8))-
B
Where B denotes the total number of state-action pairs collected in the batch. The regularized empirical Fisher then becomes
F = XI (
This is a rank-one moment approximation that assumes vectors in batch have small angular variance. The bias can be written explicitly:
E F Cou(f) 2
B
F underestimates F by positive semidefinite term that shrinks gradients concentrate as B grows. and the update direction of SMAC is given by
7ht (
g++1 gr - g
X2 + T
Results Fig. 3 compares the single-sample and batch-mean variants on Mujoco HalfCheetah and Hopper. Using B = 1000 reduces the overall optimization time by roughly 80% while achieving returns that remain close the singlo-sample bascline and clearly outperform the standard A2C optimized with SGD. Therefore, further balance computational resources and performance, implement the version with batch size of 1000 in all subsequent experiments.
10

---

Published in Transactions on Machine Learning Research (02/2026)
5.2 Effect of damping coefficient X
We the EF F XI + ch (TE)T with À 0. After applying the Sherman-Morrison formula, its inverse has the closed form
e (e
(AI ( X
(
It scales directions unevenly, components perpendicular to l are reduced by a factor 1 while the component along& l is reduced by x=
Pepper 93
Swmmer
Waller 95
X0
250-
30-
19800
1200
13:30
300.0 7300
Figure 4: Effect of different
Results. We evaluate SMAC three Mujoco tasks, compare three damping coeffcient value À e 10.1, 14,11,10, 10). Overall, the results agree with our analysis: too large À slows learning, too small À can make the tradeoff on average. The choices in practice
update noisy, and a moderate À gives the best stability- are more complex, for example, the choice of À is coupled with the learning rate because both scale the step, so balance is needed. A leasible path is to use a small damping coefficient to keep the EF term close to its undamped form, and then apply normalization so the update magnitude is preserved.
5.3 Effect of previous estimate EF
Hopper va
Setmerr V3
Wather
350-
mmm mm
10
38
Figure 5: Previous EF used vs. Ours
Using the previous EF not only increases the memory and time complexity to O(d), but introduces lag bias: after cach update the policy and state distribution change, so the old EF reflects the old distribution and can mis-scale directions when curvature changes quickly. In this experiments we used a mixed estimator F = 3F + (1 3) (et)T with a fixed 0.5 to limit reliance on the old EF. Results show that on Swimmer it gives faster carly improvement but remains less stable, while on Hopper and Walker learns more slowly with larger variance. Therefore, if the KL change strictly constrained, using the previous estimate FF is still feasible, and the choice of 8 should depend on the rate of policy change.
11

---

Published in Transactions on Machine Learning Research (02/2026)
Acrobot V1
Cartpole
Penduluum
1000
-207
-00
AC-SGD
AC-Adam
AC-CG
AC-FFC
-1002
SMAC (Ours)
0.20
0.25
350
0.75
3400
123
1.0
1.75
2,00
0.0
0.5
1/0
1.5 Steps
2.0
25
3.9
Steps
Steps
Figure 6: Results on three classic control tasks. We report the average return per episode. All results are first grouped into bins and smoothed, and then averaged over 5 random seeds, with shaded areas showing standard deviation.
6 Results
We provide the final performance achieved by training each of the five algorithms on each of the nine tasks. The results in Table [ show that method, SMAC, can achieve competitive results in two of the three simple control lasks. More importantly, the benefits of SMAC appear to increase in more complex environments, such as MuJoCo, where SMAC outperforms the other baselines in terms of final returns in all but one task. A more in-depth analysis of these results, with a special focus on convergence rate, is given in this section.
6.1 Classic Control
In the classic control environment, our method, SMAC, reaches a high initial average return faster than the baselines on two of the tasks, as shown in Fig. (see Fig. for raw results). This, however, comes at the cost of additional variance across seeds. The overall performance of SMAC is also competitive in those two tasks.
In Acrobot, SMAC only requires 40000 timesteps to pass the average return threshold of 4400. This is faster than AC-Adam, AC-SGD, AC-CG, and AC-KFAC, which require 70%, 35%, 50% and 235% more timesteps, respectively. This accelerated learning is, however, followed by unstable training until approximately 125000 timesteps. Despite this, SMAC stabilizes and converges, reaching final performance of -94.1 + 6.3, which is similar to three of the baselines, and higher than AC-KFAC.
A similar behavior can be observed in Cartpole. SMAC agents achieve 75% of the maximum return possible 87000 timesteps, slightly faster than AC-CG, which needs approximately 10% more timesteps. AC-Adam and AC-SGD even slower, requiring 28% and 62% more timesteps, respectively, reach the same threshold. At the same time, the average performance of AC-KFAC never improves above 40% of the optimal policy's 's return. SMAC becomes more unstable after this initial period, but stabilizes and reaches competitive performance of 973.4 + 29.8 by the end of training.
In contrast, in the last environment, Pendulum, our method fails outperform AC-GG in terms of con- vergence speed and overall performance. AC-CG requires only 1.5 million timesteps to match the final performance of SMAC, indicating that proposed approximation of the FIM can struggle to improve learning in some environments. Moreover, SMAC is also outperformed by AC-KFAC, which quickly finds good policy but then stops learning. However, SMAC still achieves final return of 2226 + 859, out- performing AC-Adam and matching AC-SGD, with the former also displaying much slower and unstable learning.
As proposed in Sec. 5 the validity of our results also confirmed by the action log-probabilitics recorded (Fig. 10p. In Acrobot and Cartpole, the two tasks in which SMAC performs competitively, the log-probabilities converge faster than those of the baseline methods. Together with the increase in performance achieved by
12

---

Published in Transactions on Machine Learning Research (02/2026)
Cheetah
Swimmer
Walker
AC-SGD
250-
AC-Adam
AC-CG
20
SMAC (Ours)
150
Averape
350
106
166
Hopper VS
Humnanodd
Pusher
352
5000
-500-
1000
-1520
192
1000
100
-2000
52
04
Steps
Steps
266
Figure Results on six MuJoCo tasks. We report the average return per episode. All results are first grouped into bins and smoothed, and then averaged over 5 random seeds, with shaded areas showing standard deviation.
SMAC in these lasks, this may indicate that our agents can rapidly become confident in their policies when taking actions that yield increasingly higher returns. At the same time, in Pendulum, the log-probabilities of SMAC match those of AC-SGD and are bounded above by AC-CG. This could indicate that our method becomes overconfident in its actions too early, finally leading to a sub-optimal policy.
6.2 MuJoCo
In the more complex MuJoCo environment, we have found that throughout training, our method, SMAC, consistently outperforms or matches the bascline algorithms in terms of performance in 5 out of 6 tasks, as shown in Fig. (see Fig. for raw results). In the sixth lask, SMAC still achieves comparable results.
SMAC shows improvements over existing methods in Half Cheetah, where it achieves an average return of 2936 + 946, surpassing the next-best algorithm, AC-CG, by over 1100 points. While it learns more slowly for the first 2 million timesteps, SMAC ultimately matches the final performance of AC-CG after only 3.4 million timesteps, which represents just 68% of the training budget. It then continues to improve, while AC-CG plateaus. This superior performance comes at the cost of lower stability, with both SMAC and AC-CG being much more unstable than AC-KFAC, and the simpler AC-Adam and AC-SGD.
Similar trends can be observed in Hopper, where SMAC achieves the final performance of AC-Adam using almost. three limes fewer timesteps. Our method achieves final average return of 331.2 29.77, outperforming the second-best performances of AC-Adam and AC-KFAC by approximately 30 points. The stability of SMAC appears to be comparable to that of AC-Adam, higher than that of AC-KFAC, but lower than that of the other two baselines.
Likewise, in Swimer, SMAC consistently outperforms the second-best best baselines, with final average return of 28.5 0.8, which approximately points higher than those of AC-CG and AC-KFAC. Morcover, it learns the fastest, matching the peak performance of AC-CG almost twice as fast. The stability of SMAC is also greater than that of AC-SGD, AC-CG, and AC-KFAC, and competitive with that of AC-Adam.
13

---

Published in Transactions on Machine Learning Research (02/2026)
In Walker, our method learns faster than the baselines in the first 60% of the timesteps. While its final performance of 204.1 + 87.9 is lower than those of AC-CG and AC-SGD, which achieve 229.8 + 23.9 and 213.4 + 42.9, respectively, SMAC reaches the threshold of 115 (half of the final return of AC-CG) in only 410000 timesteps, while AC-CG itself needs 39% more. Additionally, our approach outperforms AC-Adam and AC-KFAC in both average return and stability.
For the Humanoid environment, SMAC achieves the top final performance of 4625 + 277 average return, followed closely by AC-SGD with 4539 = 110. It greatly outperforms AC-Adam and AC-CG in terms of both final returns and final stability, with only AC-SGD and AC-KFAC being more stable. However, the performance of AC-KFAC is much lower than that of any of the other algorithms. While AC-SGD is slightly faster than our method, SMAC still learns much faster than AC-Adam and AC-CG, matching their final performance after using just 59% of the total allocated training budget.
In Pusher, the performance of SMAC closely follows that of AC-SGD, slightly outperforming the latter with final average return of -088.2 = 32.2. Our method is also more sample efficient, passing the -441 return threshold (final performance of AC-CG) 21% faster than AC-OG and 9% faster than AC-SGD. While all agents stabilize by the end of training, only AC-Adam and AC-KFAC end up being more stable than SMAC, with AC-SGD having the highest standard deviation.
Finally, we turn our attention to the average log-probabilities of the actions taken during training (Fig. 11 as proposed in Sec. 3 The increase in log-probabilities shown by SMAC is stable and correlates with the increase in average returns given in Fig. 7 This may indicate that the policy quickly becomes confident in the actions it chooses, without becoming overconfident. Note that the log-probabilities of our method converge the fastest in 2 out of 6 tasks. While the log-probabilities of AC-CG converge first in Humanoid and Pusher, this does not lead to better performance. On the contrary, in the former task, AC-CG agents become overconfident in their sub-optimal actions. While in Half Cheetah the converge first, SMAC ultimately achieves a higher confidence in its actions, which matches its superior final performance. A similar trend appears in Walker, with AC-KFAC converging the fastest, but to a sub-optimal policy. The slow convergence of the other two agents' log-probabilities in most tasks may indicate uncertainty in their actions, even when their performance matches that of SMAC.
of AC-CG
7 Conclusion
In this work, we introduced a simple yet effective rank-1 approximation to the Natural Policy Gradient in the Actor-Critic framework. By using a regularized Empirical Fisher matrix and the Sherman- Morrison formula, we enable scalable and efficient natural policy gradient updates with only O(d) complexity. We theoretically prove the convergence properties of this approximation and integrate it into the standard Actor- Critic algorithm to demonstrate its practical utility. Experimental results on classic control and MuJoCo tasks show that our method achieves both fast and stable convergence in most environments, outperforms methods such Advantage Actor-Critic and conjugate gradient in TRPO in several environments, offering promising alternative for elficient NPG approximations.
Broader Impact
Reinforcement learning is now used in many domains, from fine-tuning language models to controlling systems such as power grids or data centres, and this broad use can bring both benefits and risks. It can improve efficiency, safety, and energy use, but it can also amplify existing biases support decision systems that have harmful social or economic effects. Our work focuses only on the optimisation aspect: study how to solve a given policy optimisation problem faster, so that fixed objective is reached in fewer gradient steps. If the training data for language models or the environment model for control tasks reflects real-world dynamics and values accurately, a more efficient optimiser can produce better policies with less computation and a smaller training carbon footprint. At the same time, any negative socictal impact would mainly arise from biased, incomplete, or misaligned data, objectives, and reward designs, rather than from the particular optimization method used.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Acknowledgment
SPD was funded by the Dean's Doctoral Scholarship at the University of Manchester. SK acknowledges funding from the UKRI Turing AT World-Leading Researcher Fellowship (EP/W RBP//W0277//). MS acknowledges funding from AT Hub in Generative Models by Enginecring & Physical Sciences Research Council (EPSRC) with Funding Body Ref: EP/Y028805/1.
Code availability
Our code is publicly at
References
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 (98):1-76, 2021. URL http::/p///all.looo////ptt//////
html
Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Comput., 10(2):251 276, 1998. doi: 10.116/008997688000777788 URL
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforcement learning: A brief survey. TEFE signal processing magozine, 34(6):26-33 38, 2017.
J. Andrew Bagnell and Jeff Schneider. Covariant policy search. In Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI'03, pp. 1019 1024, San Francisco, CA, USA, 2003. Morgan Kaufmann Publishers Inc.
Achraf Bahamou, Donald Goldfarb, and Yi Ren. A mini-block fisher method for deep neural networks. Tn Francisco J. R. Ruiz, Jennifer G. Dy, and Jan-Willen van de Meent (eds.), International Conference Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, volume 206 of Proceedings of Machine Learning Research, pp. 9191-9220. PMLR, 2023. URL httpttt//pprocceednngg mlr. mlr.press/ press/v206. bttp///aaaammaaa..mmmmm html
Jonathan Baxter and Peter L. Bartlett. Infinite-horizon policy-gradient estimation. Artif. Intell. Res., 15: 319-350, 2001. doi: 10.1613/JAIR.SD URL http::///01..rrg//0.611333
806
Suzanna Becker and Yann Lecun. Improving the convergence of back-propagation learning with second-order methods. In Proceedings of the 1988 Connectionist Models Summer School, 01 1989.
Frederik Benzing. Gradient descent neurons and its link to approximate second-order optimization. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Bullimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp- 1817-1853. PMLR, 2022. URL https: //proceedings .ww.inng..m......mmm.m.........m wwwpppeeeeeeeeeeeeeeeeeeeeee btwpr///22//eiin222.... html
Yuhao Ding, Junzi Zhang, and Javad Lavaci. On the global optimum convergence of momentum-baser policy gradient. In International Conference on Arlificial Intelligence and Slatistics, pp. 1910 1934. PMLR, 2022.
Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actor-critic rein- forcement learning: Standard and natural policy gradients. IEEE Transactions Systems, Man, and Cybernetics, part C' (applications and revieus), 12911112911 2012.
Sham M. Kakade. A natural policy gradient. In Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (eds.), Advances in Neural Information Processing Systems 14 [Neural Information Pro- cessing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canadaj, pp. 1531-1538, MIT Press, 2001. URL 4B35abe48d38ecf1944666 htt.:eeeeeeec4444699966699900 aateeaabccs1104443eebaatttaaat Abstract html
15

---

Published in Transactions on Machine Learning Research (02/2026)
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical fisher approximation for natural gradient descent. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'cché Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancowver, BC, Canada, pp. 4158 4169, 2019. URL htttps://proceedngg hash /t/.////555799440441111111...... Abstrrtctttttttttttttmmm
Yann LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9 50. Springer, 2002.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (varianco-reducee)) policy gradient and natural policy gradient methods. CoRR, abs/2211.07937,, 2022. doi: 10.48550/ ARX./.2211..22111 07937. URL https://doi.... .tw.doi..og///oooooooooooo org/ 10////11../0
James Martens. Deep learning via hessian-free optimization. In Johannes Fürnkranz and Thorsten Joachims (eds.), Proceedingg of the 27th International Conference on Machine Learning (ICML-10), June 21-24,
2010, Haifa, Israel, pp. 735-742. Omnipress, 2010. URL httpss///omm..ccCoffeeeeeeeeee 458.pdf
James Martens. New insights and perspectives on the natural gradient method. J. Mach. Learn. Res., 21: 146:1-146:76, 2020. URL. https:// /ttpp//////ppppp/////////1//2 html
James Martens and Roger B. Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and
Conference Proceedings, pp. 2408 2417. JMLR.org, 2015. URL http://proceedinng mlr, ptt....reesv3/ martens 15. html
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national conference on machine learning, pp.
PmLR, 2016.
Jan Peters, Sethu Vijayakunar, and Stefan Schaal, Natural actor-critic. In European Conference on Machine Learning, pp. 280 280-291. 291. Springer, 2005.
Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Adaptive step-size for policy gradient meth- ods. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.). Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural In- formation Processing Systems 2013. Proceedings of a meeling held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 1391 1402, 2013. URL https://proceedngs..u neurips...u.......e.. wttpp//wwccppccccee/////// /c/p/ppr/2013/
Yi Ren and Donald Goldfarb. Efficient subsampled gauss-newton and natural gradient methods for training neural networks. CoRR, abs/1906. abs/1996.003353, 2019. URL http://arxiv, htt//bbs/19006 02353
Yi Ren and Donald Goldfarb. Tensor normal training for deep learning models. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Newral Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 26040 26052, 2021. URL ptstps://proceedingg Abstract cnntrract.ttlll .htll
heurips.cc/papeee http///p00000000aaaaaaaaa222e000
Silvia Richter, Douglas Aberdeen, and Jin Yu. Natural actor-critic for road traffic optimisation. Advances in neural information processing systems, 19, 2006.
Nicolas Le Roux, Pierre-Antoine Manzagol, and Yoshua Bengio. Topmoumoute online natural gradient algorithm. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis (ods.), Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-Firss Annual Conference on Neu- val Information Processing Systems, Vancouver, Brilish Columbia, Canada, December 3-6, 2007, pp-
16

---

Published in Transactions on Machine Learning Research (02/2026)
849 856. Curran Associates, Inc., 2007. URL #561400aaaa/16333550ccr 102 Abstractt................a.tat html
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 14(7):1723 1738, 2002.
John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy optimization. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Confer- ence on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1889-1897. JMg,. 2015a. URL http://proceeddnnss mlr pae...resssv////
schulman15.htm
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continnous control using generalized advantage estimation. arXiv preprint XXx:15066002435 2015b.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithıns. XrXiv preprinl Xrv: 1es11777.0033 00347, 2017.
Jack Sherman and Winifred J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Annals of Mathematical Statistics, 21(1):124 127, 1950. doi: 20.214/aomss 1177729893.
Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 39: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virlual, 2020. /ttpstts::/ proceedings.nourips..cco hocceddlg...oorrss..../////////p http:///ww//cccceee2ee6o00000000 www.:tttttasttttttttt.ac..
Zhiqiang Su, Meng Zhou, Fangfang Han, Yiwu Zhu, Dalci Song, and Tingting Guo. Attitude control of underwater glider combined reinforcement learning with active disturbance rejection control. Journal of Marine Science and Technology, 24(3):686-700 2019.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller (eds.), A Advances in Neurol Information Processing Systems, volume 12. MIT Press, 1999. URL httpp::/prooeeddnngs .dff
files/
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026 5033. IEEE, 2012. doi: 1..109//RRO..202..663
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXis preprint arXiv:2407.17032 2024.
Wouter JA van Heeswijk. Natural policy gradients in reinforcement learning explained. arXie preprint arXiv:2209.0188 2022.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global opti- mality and rates of convergence. arXiv preprint arXiw:1909.01150. 2019.
Xu Wang, Sen Wang, Xingxing Liang, Dawei Zhao, Jincai Huang, Xin Xu, Bin Dai, and Qiguang Miao. Deep reinforcement learning: A survey. IEFF. Transactions on Neural Networks and Learning Systems, 35(4):5064-5078, 2022.
Ronald Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229 256, 1992.
17

---

Published in Transactions on Machine Learning Research (02/2026)
Xiaodong Wu, Wenyi Yu, Chao Zhang, and Philip C. Woodland. An improved empirical fisher approximation for natural gradient descent. In Amir Globersons, Lester Mackey, Danielle Belgrave, A Angela. Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NewrIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. htt./attp://ppperss. nips wwwppippppppp.eeeeeeeee cc/paper ftles//aperr2022//ma 22000500aaaadd0/7333444400-----0
Yuhuai Wu, Elman Mansimov, Roger B. Grosse, Shun Liao, and Jimmy Ba.. Scalable trust-region method for deep reinforcement learning using kronocken-factored approximation. In Isabelle Guyon, Ulriee von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, V. N. Vishwanathan, and Roman Garneu (eds.); Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5279 5288, 2017. URL httpss/t::/ proceedings.meuree newrips wwtpppppe//eaeee/eeee 2017 http:////...412200aaaa11111111.0 wwwtract.ttttttoeo..tteaaet .tmll
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduuced policy gradient. In Amir Globerson and Ricardo Silva (eds.), Procerdings of the Thirly-Fijth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pp. 541-551. AUAI Press, 2019. URL http: http://proceedings.
mlr. v1 v115/xu20e wwwuaaa.hmm..
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In International Conference on Learning Representations, 2020. URL https://openreries:
net/forrumIdd=:JJIIIBBB.
Minghan Yang, Dong Xu, Zaiwen Wen, Mengyun Chen, and Pengxiang Xu. Sketch-based empirical natural gradient methods for deep learning. J. Sei. Comput. 92(3):94, 2022. doi: 10.0007/$10011--0--0011111
URL https://doi.org org/orgg/// 100000000 1070100000001-------11111-
Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In Gustan Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Stalistics, volume 151 of Proceedings of Machine Learning Research, pp. 3332-3380. PMLR, 28-30 Mar 2022. URL attps://proceedingg. mlr press/ v151/yuan2aa.htt html
Lin Zhang, Shaohuai Shi, and Bo Li. Eva: Practical second-order optimization with kronecker-vectorized approximation. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL httpss//openrerreeennet//e Mic8V96Voy
Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama. Analysis and improvement of policy gradient estimation. Nearal Networks, 26:118 129, 2012. doi: 10.1016/..NUUNET. 2011.099.05. URL attpps///oot http://ti..og/1...11110100 1111100..1111// neunet. 2011
20wamet.2011..... 09.005
18

---

Published in Transactions on Machine Learning Research (02/2026)
A
Appendix
A.1 Notations.
Let 7 (0,1) 1) be the discount, r: r:8x A [-R, is the reward function, and H NU (oo} the horizon.
Define the truncated objective
Σ
7
a+)
J(0) J
(16)
For each trajectory 7" (su, Lss,,0.... ao.............................. 8H-1, 0n-1 sampled under no, let g(T (0) denote singlo-trajectory
unbiased estimator of the truncated policy gradient:
E[g(T" [0]] = (O)
(17)
H-1 9(7 10) Σ
7' G. Vo to (s)
(18)
1=
A.2 Assumptions
Assumption 1. Let g(tg)))))) be an unbiased single-trajectory estimator of J() Assume there crists such that for all 0,
E || 10) -E(((" [0]]]]] s
Assumption The Pisher Information matrix induced by the policy uo is Posilive Defovile and salisfies
F(0) = Bandjo Banay (oolog no Vo logogn) mo & upI
(19)
Assumption 3. The policy gradient estimales are bounded by a consland G 2 O and the change in policy gradient at different timestep are bounded by the change in policy parametrization weights. So,
Vv log Tell G
(20)
V log ne, - Ve log S M 110 021l
(21)
Assumption 4. Transferrable Compatible Function Approzimmato: When approsimate the Ad- vantage function using the policy ma it induces transfer error defined Ebias which is zero for softmar parametrization and is very small for dense neural policy class.
Ly (u 0) = E(s.a)=vr (AT (1- (11 Vo log (a((s))) Ebias
(22)
where v² (s, d (s) (5) is the slate-aclion distribution induced by optimal policy x" and w argmin,, Teyça (wn: 0) is obtained vio the full natural policy gradient direction at the parametrization 0. Remark 1. Regarding F(O), we know from Assumptions 1 and 2 that
Prla & F(0) & G² La for any 0 E Rd.
Remark 2. Now we can get an upper bound to the second term of Equation using Remark
as:
G
5
Aa + XTr FK)
X2 + X
19

---

Published in Transactions on Machine Learning Research (02/2026)
Remark 3. Assumption 1 treats o² constant upper bound the variance of the truncated policy gradient eslimator, although in general Var(g(7H ()) may depend on the horizon H. More precisely, for each finite H we write
Var (ar [0)) = on.
For likelihood--aan ratio estimators such REINFORCE, cristing analyses show that o²H can grow with H, but remains finite under smooth Gaussian policies with bounded rewards and features (Zhao et al.) 2012 Pirotta et ol. 2013: Bazter & Bartlett 2001). In our proof we use a finâte truncated horizon and define
o < oc. 1SHSHmax
sup
This form of bounded-oariance assumption is standard in recent convergence analyses of policy gradient methods
Liu et al. 2022 Xu et al. 2020 2019
A.3 Helper Lemmas
We will establish some helper lemma to prove the global convergence of Sherman-Morrison policy update.
Lemma 1.
Liu et al. 2022 In the stochastic PG update, have
g 1 (8o)
(3 + L)T)) da
B (0*)
(23)
2 Luus
7
In total, stochastic PG samples O (|-سحズー
trajectories.
Lemma 2. Liu el al. 2022) Let J(0), (0) are L, L-mmoolth, where Ly = (1-7)² + 2G
MR
(1-7)² and
H+1 + 7 1-7 (1- (1-7)2 7H
(0) -J(O) < GR
Lemma 3.
Liu el al.
2022
Let = = be the exact NPG updale direction at 0k Then,
have
1
EEbia
1
J(
Σ
J(O))
Banay [KL (TT
(m (TT)ss) (-1ss))
K
nパK
h=0
(24)
G K-1
Mn
K
+
w
I 1|
K
2K
km
A 0
A.4 Global Convergence of SM Update
Let take : the update direction of Sherman-Morrison. To this end, need to upper bound K- w wfll ||. J Ek-1 ||,*1|,, and 1 Bandy [KL (I* (T (-Is))], where w FF
K-1
is the exact NPG update direction at gh
Bounding 1 EK-1 w wtll
20

---

Published in Transactions on Machine Learning Research (02/2026)
We know from Jensen's incquality that (Billu?** +1 w 11) s <Billu?t! = so,
K-
[| 20 - -w |1] 2
1
K
[Billz* 2+ [11) 2
(25)
1|Il2* - w
K-1
2 K
Bl|| vJ(0")1 +
Σ
B
]((*)((0*) - -w,\1²]
K
K
k=
k=
Let
N
g"
glt
H 10%),
N
be the PG direction and
1
F
w
x
9
X2 +
XTr
be the weight update from the Iitomman-Morrisee update then we have from Lemma 2 and Remark and Assumption 3 that
K-
BiIl
K
k=
1
E
Σ E
g VJ(OS)
22 + (Tr(FF))
1 K-1
Σ
E
(g)
(Ot))
(g
-
- (VJ(0t)- (Bb)(
K
X2 + (TT(Fk)
K=
(26)
1 J. (0t)
V.J' JJJ (Bt)
X2 + XTr (K)
0²
G2
H +
2
RR
+
2211
N
X²
X2 + AHF
1 1-7
(1 7)22
1
G²
K-1
|+
B|ll V l (at>
\H1
Furthermore, Assumption 2 tells us that
E||l ((( - 13
= = Fー - 11
2
+ μr
(27)
2
(1+1 7
<
1 +
2B
(1+)) R² (1-7 (1-2) (1-
22H
μp
21

---

Published in Transactions on Machine Learning Research (02/2026)
Combining equation 26 and equation 27 with equation 25 gives
K- 1
B Billw w0th
w 11
K
K=0
+
G
+ R
H H+1
+
?
72H
1+
1+
2
(28)
N
X2
X2 + AUF
11
(1 7)2
PF
+ 4
1 (1 1
1
2
+
1
+
G²
1
K-1
R
V
0.5
PF
X
X
App
K
k=0
And recall from equation 23
that
K
J
1 (0a)
(3 + I. T,, o²
E
K
2 L,n
Let us take 1) 45.5' 1.
Then we get
(J (H)())
30 N
E
V (0%)))
K
In addition, let H, N, and K satisfy
1 8 )2 2 R2
HH
1-7 + (1 - 7)2
7
2
722 1+ 1
3 3G
402
3
4
102
+3 3311+ (1+ 1 )
N
(29)
( (5))
-
((1
+1+ + x
G²
K>
1 2
3 (3G
Then, have
K
Ell l1 - w
E
(30)
K 0=
Bounding 1
EK-1 l
22

---

Published in Transactions on Machine Learning Research (02/2026)
We have from equation 26 and equation 23 that
E
1|
K
F
E
x + XT (FK) 9²
Σ
E
1 |
A. (ot))
F
(g*
V.J (JJ"((")) + 2 V. (0)
22
(Fk
k=
fk.
(O+)
X2
(Tr(Fk)
0²
G
1
G
2 2
+
+2
+
Elll V 1H (0*) )|2]
N
12
X2 + Xpr
X
X2
+
\pp
16 0²
1
G²
32L t
(80)
1
N
12
X2
AUF
K
A2
X2
ALF
Where to get to the last inequality we have taken 1) = 42j - and applied Lemia
16no²
1
G²
13
x=+
N
(31)
32L,
(JH (12 +
G2
x=+ApF
K
2
we arrive
K-1 1
Σ k=
B
w
k
E $1
(32)
K
3
Bounding 1/ Londy" [KL (-Is)
Tga (-1s))].
By taking
3E B
[KL (n* (lgg) (-1s))
K
(33)
m
we have
B Bandy' [KT (TT)s( (=g0)] = 6
(34)
nK
3
From equation 29
H ++1 1
+ 7 2 22 < C
(35)
1-7 (1-7)²
for some constant Co that does not depend on H or E.
For all H 2 0
23

---

Published in Transactions on Machine Learning Research (02/2026)
H ++1 7
H + (1-
C(H++1)
+
1-7 (1 7)2
1 1-y
(1-7)²
for constant C 2 1 that depends only 7. Substituting this into Equation 35 gives
HH + 1)3 S C2(1 - 7)
(36)
for constant C2 independent of H and E. Since the prefactor grows polynomially in H while 22 decays geometrically,
7 2H S c
for some constant Cj independent of H. Taking logarithm on both side yields
H = (1og (1-)) (10 (1-7)----))
(37)
The lower bounds on N in equation 29 and equation 31 have the form
N oza² (I (1+ ++)+
G²
E-2
MF
for a constant C2 that absorbs numerical factors. Since the expression parentheses is independent of e, we have
o²
N o
(38)
The lower bounds on K collected from equation
29
eq equation
31 and equation 33 can be written as
K 2 es (I)(J"**-J"((())) + Exnay [KL (TT (-Is) Too
- J
(TT0( (-1s))) E-
for constant C3 depending only on (1 (1-7)-1 and the model parameters. Since both terms in parentheses scale as ((11-7)-)) We have
K = 0
(39)
(1
202
In summary, we require N K and H to satisfy equation
29 equation 31 and equation 33
which lcads to
N
K k=O
(log(( - 7) 1))
(1 22
By combining equation
30 equation
32 equation and equation 24 we can conclude that
34
K-1
J(
1
J(gk) <
Ebias
+ E.
K
km
In total, stochastic Sherman-Morrison Policy gradient requires to sample KN KN= KN=Ol N0N000000 o²
(
trajectories.
24

---

Published in Transactions on Machine Learning Research (02/2026)
A.5 Detailed Derivation of the Toy Problem
The policy is parameterized by vector 0 = =00.0 0,), with independent Bernoulli distribution:
To = = 0) = 1
(40)
1 + e>,%
Ta = x 1) 1 eee
(41)
where Ap scales the first policy parameter and is used to test scaling invariance. If we assume that the agent starts at the state x = 0 then the objective (expected return) in this simplified setting is
((0) = T = 0 x = + 2(1 (a = 0 = 0)) Te(a = 0 1).
(42)
The policy gradient theorem states:
(0) = Ez,a Vo (o) ((r
(43)
For the Bernoulli parameterization and noting that the policy function resembles sigmoid activation function the derivative of the log peg-polic can be simplified as
Ap To)
if = 0, a 0
7n
if x a
Ve log (a(a
(44)
-(1 - XT)
if x 1, a 0
n
if x 1, ==
where To = =æ(a= 0 = 0) and Ii = (a = 0 = 1). Using the rewards in the environment, one can
derive the analytic policy gradient vector
- To(1 - To)(1 - 2TT1)
VeJ(0)-
(45)
22 TO)T (1 - m1)
The geometry of the policy manifold is captured by the FIM and as the states are independent of cach other we can wrile the per state FIM as,
Fx Easn(- Vo. log Ta(alo = i) Vo, log mo = i)"]
(46)
For State (x = 0): The Score functions for a E {0, can expressed as:
log (a = 0 x = 0) -Ap(1 TO),
log To = 1 x = 0) AnTo
(47)
20,
20,
25

---

Published in Transactions on Machine Learning Research (02/2026)
Hence,
Foo Tol -ol-Ap(1 ]0 + (1 Top
(48)
= >2 - mo)² + (1 - )
(49)
X2 mo)((1 - mo) mol
(50)
13 nu)-
(51)
Similarly for state (x 1): The Score functions for a E {0, 13 ca be expressed as:
log To = 0 x == 1) = -(1 - Ti),
log To = 1 x = 1) m
(52)
001
001
Hence,
Fn = f1=m/-(11 - nı m1) + (1 - m1 mm)
(53)
T1 (1 m +(1 ))
(54)
TT (1 - 11)[(1 m1) + ml
(55)
Ti m1(1= m
(56)
Owing to independence between states, F(0) diagonal:
A Tu(1 To)
0
F(O) =
(57)
0
(1 11)
Then the NPG update direction is obtained by preconditioning the gradient with the inverse Fisher matrix,
- (11 2n
θNPG - VoJ(()-
Xpp
(58)
2(11 T00)
To reduce computation while preserving approximate invariance, the SM approach uses a low-rank inverse metric F-1 defined in terms of damping factor and exact FIM F(0) capturing dominant curvature dircction,
1 N
F(O) TrFF(F(())
p-1
(59)
A X+
(60)
Hence the resulting SM update direction be written
26

---

Published in Transactions on Machine Learning Research (02/2026)
SSM F-1 VBJ(0)
(61)
F(O)
VoJ(O)
(62)
À
x Tr(F(0))
1
VoJ(O)- F(0)VoJ(()
(63)
X
A+Tr(F(O))
2 m 21 2
(->p To - - 2TT1)
X + X { To To) + (1 ))
(64)
1 (-2 1 (1 n.
2 2 2
T0)
x + 2 13 To
To) 11 11)
A.6 Additional Results
3030
-200
-2000
-405
-3000
-000
AC-SGD
-800
AC-CG
-0000
ACKFAC
-7000
SMAC (Ours)
0.35
0.50
2.00
1.2
3.75 2.00
1.2
305
Steps
Steps
Steps
Figure 8: Raw results on three classic control tasks. These correspond to the results reported in Fig. but without bimning or smoothing.
SGD
AC-Adlam
330
3530
AC-EFAC
2654
3000
-3000
-2500
Hopper VS
Humanoid
Pusher VS
405
0000
10000
255-
330
300
3000
0.5
0.2
0.5
1,3
3
0.
055
1,0
155
2.0
355
3.0
Steps
Steps
Steps
Figure 9: Results on six MuJoCo tasks. These correspond to the results reported in Fig. binning or smoothing.
7 but without
27

---

Published in Transactions on Machine Learning Research (02/2026)
Cartpole
AC-SG
-22
AC-Adam
-12
Lorg
-3.--
AC KFAC
(Qurs)
0.50
-16
-10-
3.00
0.55
0.50
1.00
155
1.50
1.35
2.00
0.5
35
2.0
Stegss
Steps
Steps
Figure 10: Average pog-probabilities of the actions taken on three classic control tasks. All results are averaged over 5 random seeds, with shaded areas showing standard deviation.
Avtragg Action Log Proaaiiites
32
-35-
SGD
-14-
AC-Adam
CG
-15-
10.0
-16
SMAC (Ours)
11.5
00
0.2
0.4
0.8
10
0.0
0.4
0.
104
10
Hopper
Humanoid VS
Pusher V5
-10
Log
-45-
-25
-35
-50
-20
-25
0.5
0.0
0.5
1.5
2.0
Steps
Steps
Steps
Figure 11: Average log- bog-probabilities of the actions taken on six MuJoCo tasks. All results are averaged over random seeds, with shaded areas showing standard deviation.
A.7
We consider the following typer-parametenn
(actor): step size for the policy-network update.
(critic): learning rate for the value network, optimized with Adam.
T: number of environment steps collected before each parameter update.
y: reward discount factor.
AGAE: trace-decay parameter used by Generalized Advantage Estimation when computing the ad- vantage values 4,-
A: damping factor used the matrix-free Sherman-Morrison approximation of the empirical Fisher.
We tune five of these on each environment. We omit tuning as preliminary runs have shown that performance is not highly correlated with its value. We select values for (critic) from the interval [1
28

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm
(actor)
X {10- 10
SMAC
5x10 10
10
,,10
1,101,11
AC-Adam
[xx10-
AC-SGD
[5x10-9,5x01
AC-CG
1xx10",9x10""
AC-KFAC
[1x10- 9x010-
Table 2: Hyper-parameee values evaluated during tuning. Additionally, for cach algorithm, select values for (critic) from [1x10-5, 1Ix10-9,xx103 5x10-$), for from (0.9, 0.95, 0.99), and for λGaR from {0.8, 0.9, 0.95, 0.99). See Table 5 for additional details on tuning hyperparameters specific to AC-KFAC.
Environment
Algorithm
" (actor)
a (critic)
T
7
AGAB
SMAC
5x10-3
1 10
1000
0.99
0.9
0.1
AC-Adam
6x10-4
1x 10-3
1000
0.99
0.9
Acrobot
AC SGD
2x10
1x10
1000
0.99
0.9
AC-CG
6x10-1
1x10
1000
0.99
0.9
AC-KFAC
1x10-2
1x10-3
1000
0.99
SMAC
5x10-3
1x10-3
1000
0.99
0.9
0.1
AC-A
7x10-
1x10
1000
0.99
0.9
Cartpole
AC-SGD
7x10-a
1X10
1000
0.99
0.9
AC-CG
8x
1x10
1000
0.99
AC-KFAC
1x10-3 3
1x10-3
1000
0.99
SMAC
6x10-3
1x10
1000
0.99
0.9
0.1
AC Adam
7x10
1X10
1000
0.99
0.9
Pendulum
AC-SGD
5x
1x10
1000
0.99
0.9
AC-CG
3x10-2
1x10-3
1000
0.99
AC-KFAC
Table 3: Training hyper-parameters for the classic control environments.
for 7 from the set {0.9, 0.95, 0.99), and for AGAE from the set {0.8, 0.85, 0.9,0..5,0.999 For the rest of the hyper-parameters, we select values according Tables 2 and The goal is find hyper- parameter configurations that maximize the return averaged the last 100 epochs, for each environment and algorithm.
We find that learning rates have the highest impact on performance. On the contrary, = 0.99 and XGAE 0.9 perform well in all environments. For each environment and algorithm, we select the hyper-parameter configuration that performs best, and then use to generate the results in Sec. G These configurations are shown in Tables 3 and (and Table for AC-KFAC). For typer-parameters specific AC-KFAC, we found damping of 10 factor decay of 0.99, KL clipping value of 10-3 and an update frequency of 1 iteration to perform well in all environments except the ones specified in Table
29

---

Published in Transactions on Machine Learning Research (02/2026)
Environment
Algorithm
7 (actor)
a (critic)
T
?
λGAE
SMAC
8x10-
6 10
1000
0.99
0.9
0.01
AC-Adam
5x10-5
6 10
1000
0.99
0.9
Half Cheetah
AC-SGD
1x10-1
9x 1x10-4
1000
0.99
0.9
AC CG
9x10
8x10-
1000
0.99
0.9
AC-KFAC
1x10-5
1x10-1
1000
0.99
0.9
SMAC
1x10-2
1x10
1000
0.99
0.9
1.0
AC-Adam
1x10-4
1x10-
1000
0.99
0.9
Hopper
AC-SGD
1x10-3
1x10-
1000
0.99
0.9
AC-CG
1x10
1x10
1000
0.99
0.9
AC-KFAC
SMAC
3x10-2
1x10
1000
0.99
0.9
1.0
AC-Adam
1x10-4
1x10-4
1000
0.99
0.9
Swimmer
AC SGD
1x10
1x10-4
1000
0.99
0.9
AC-CG
1x10-2
1x10
1000
0.99
0.9
AC-KFAC
1x10-2
1x10-
1000
0.99
0.9
SMAC
3x10-2
1x10
1000
0.99
0.9
1.0
AC-Adam
1x10-5
1x10-5
1000
0.99
0.9
Walker
AC SGD
1x10
1x10
1000
0.99
0.9
AC-CG
1x10-2
1x10
1000
0.99
0.9
AC-KFAC
1x10-3
1x10-4
1000
0.99
SMAC
1x10-4
1x10-3
1000
0.99
0.9
0.01
AC Adam
3x10-4
1x10
1000
0.99
0.9
Humanoid
SGD
1x10
1x10
1000
0.99
0.9
AC-CG
9x10-1
1x10-
1000
0.99
0.9
AC-KFAC
SMAC
1.5x10-3
1x10
1000
0.99
0.9
0.01
AC Adam
2.5x10-8
1x10
1000
0.99
0.9
Pusher
AC-SGD
1x10-1
1x10-3
1000
0.99
0.9
AC-CG
9x10-1
1x10-5
1000
0.99
0.9
AC-KFAC
1x10-2
1x10-3
1000
0.99
Table 4: Training hyper-parameters for the MuJoCo environments.
30

---

Published in Transactions on Machine Learning Research (02/2026)
Hyper-parameter
Tuning values
Environment
Final value
Damping
1x 10
Pendulum
1 x 10-2
Humanoid
1.5 10
Decay factor
(0.85, 0.9, 0.95, 0.99, 1.0)
Pendulum
0.85
Humanoid
0.9
KL clip
5 5x100 1.3x10-x1""
Pendulum
2.5 x 10
Humanoid
4 x 10-3
Update frequency
[1,2,4,8, 16,
Pendulum
16
Humanoid
64
Table 5: Jlype-ppraamete values evaluated when tuning AC-KFAC on each environment. We include the values we select for the Pendulum and Humanoid environments. All other environments 1 x 10-3 damping, 0.99 factor decay, 1 x 10-3 KL clip, and 1 update frequency. These tuning values and final values complement Tables 2 and 4
31


Reviews:
[{"review_id": "ZVcp0HK2iP", "reviewer": "Reviewer_snXP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study natural gradient policies (NPG) in reinforcement learning (RL). Computing the inverse Fisher Information Matrix (FIM) is a major bottleneck in natural gradient methods, particularly in deep RL. While various approximations exist (e.g., diagonal, K-FAC, Hessian-free), the authors propose a rank-1 approximation based on the Sherman–Morrison formula, which reduces computational complexity to $O(d)$, where $d$ is the number of model parameters. Under certain regularity assumptions on the policy, they establish a convergence guarantee (Theorem 1) that provides a sample-complexity bound of $O(\\epsilon^{-4})$ for achieving an optimality gap less than the sum of two terms: one based on the approximation error of the advantage function and another for the desired precision level.\n\nEmpirically, the proposed SM-ActorCritic (SMAC) algorithm is compared to baseline methods using A2C with SGD, Adam, and conjugate gradient (CG) optimizers. Experiments on MuJoCo and classic control tasks show that SMAC achieves competitive or superior performance in several environments.\n\n**Strengths**\n\n- Fast, theoretically motivated rank-1 natural gradient approximation with $O(d)$ complexity.\n\n- Convergence guarantee under regularity assumptions on the policy.\n\n- Improved efficiency and competitive empirical performance across diverse RL benchmarks.\n\n**Weaknesses**\n\n- No direct comparison to other established natural-gradient approximations (e.g., K-FAC, empirical Fisher variants) in theory or experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical claims are consistent with prior analyses (e.g., Xu et al., 2020). Theorem 1 would benefit from explicitly restating key assumptions (e.g., Lipschitz smoothness and other assumptions in Xu et al., 2020) within the theorem statement. Empirical evidence aligns with the motivation, though broader baselines would strengthen the experimental part.", "audience_yn": "Yes", "audience_explanation": "I think NPG methods remain important in RL for stability and potential sample efficiency. The method directly addresses the computational barrier of FIM inversion in deep models. Therefore, the paper might be interesting to some TMLR readers focused on optimization and theoretical RL.", "requested_changes": "- Comparison with prior NPG approximations: Please expand empirical/theoretical comparisons with established methods (e.g., K-FAC, empirical Fisher variants, Hessian-free/TRPO). Moreover, please consider adding a comparison table of computational and theoretical properties and at least one experiment, including K-FAC or TRPO. This will better position SMAC compared to the existing approaches.\n\n- Improving Theorem 1: Please include key assumptions (Lipschitz smoothness,...) within the theorem statement. Moreover, please report sample complexity in terms of the number of state–action pairs (not just trajectories). Since the horizon $H$ depends on $\\epsilon$, multiplying by $H$ is needed.\n\n- Numerical validation: In Table 1 (Half-Cheetah), other algorithms show large negative returns while SMAC is strongly positive. Please verify numbers.\n\n\n- Your $O(\\epsilon^{-4})$ bound is looser than the $\\tilde{O}(\\epsilon^{-3})$ bound reported for stochastic policy gradient (Yuan et al., 2021). Please discuss whether this gap stems from the rank-1 approximation, or proof technique/assumptions.\n\nRui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. arXiv preprint arXiv:2107.11433, 2021.", "broader_impact_concerns": "To me, there are no major ethical concerns specific to this work. The paper focuses on algorithmic and theoretical advances in reinforcement learning optimization.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rTDV3PRSUy", "reviewer": "Reviewer_D2Gk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents an approach to obtain an approximation of the inverse Fisher information matrix with cost linear to the number of policy parameters. The technique is implemented in a policy gradient method and evaluated on several control tasks. In addition, a theoretical convergence analysis is provided.", "claims_and_evidence_yn": "No", "claims_explanation": "A theoretical analysis is provided, although some details are not clear to me due to presentation issues. For instance, the bound \\epsilon_bias, defined in the second assumption (see appendix), hides terms that depend both on the transition function of the MDP and the expressivity of the critic approximator, which can be large and may not really be controllable in practice. For this reason, while the algorithm may converge, but its limit may be far from the optimal point. In addition, the analysis seems to largely rely on previous results (all the helper lemmas in the appendix). The authors should provide a more detailed discussion on those points.\n\nI think some important information about the experiments is missing to fully appreciate the experimental evaluation:\n- How were the hyperparameters chosen for all the methods?\n- Could the authors explain in more details why the computation costs can be very high (2nd sentence in Section 5.1)?\n- Could the authors provide some explanations or conjectures about which type of environments/tasks the proposed algorithm would be expected to work well or not?", "audience_yn": "Yes", "audience_explanation": "To the best of my knowledge, the application of the Sherman-Morrison formula to obtain an approximation of the inverse Fisher information matrix is novel in the context of natural policy gradient method.", "requested_changes": "A more precise discussion of the theoretical analysis should be provided. Otherwise, it feels completely disconnected from the empirical evaluation. Would it be possible to design some experiments, possibly in toy domains, to verify the obtained bounds?\n\nThe missing information about the experiments (see above) should be provided.\n\nAlthough the exposition is generally quite clear, the paper in its current version is hard to read due to notational and formatting issues (see below). I suggest the authors to improve the exposition to make it more pedagogical. Currently, some explanation or definition are not provided in the main paper, and the reader needs to search for them (for example in the appendix). \n\nNotation issues:\n\tThe MDP model is introduced as episodic, but equations are provided in the infinite horizon case.\n\tAll notations should be explained the first time they appear.\n\tThe subscript in the definition of the value function V and Q are undefined and not needed.\n\tThe expectation over episodes in (2) should be over states.\n\tThe terms in the equation for the empirical Fisher information don't have any subscript i.\n\nFormatting issues:\nThe citations that are not part of a sentence should be changed from \"Authors (year)\" to \"(Authors, year)\"", "broader_impact_concerns": "I think such discussion is not needed for this kind of paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3SUd5gMVoB", "reviewer": "Reviewer_Hkmz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a rank 1 monte carlo approximation of the inverse fisher, in an attempt to follow natural gradients in policy approximation for deep RL. The main idea is to use the Sherman-Morrison formula to calculate the inverse of required for the inverse fisher, which can be done because the rank 1 monte carlo approximation is simply a cross product of the gradients of the log policy. This is, of course, much more efficient than directly calculating the matrix inverse. The core of the paper is a theorem showing convergence of the method, under some basic assumptions, along with experimental validation.\n\n## Strengths\nIn my view, the strengths of the paper are threefold. First, it is well written and organized—by and large it is a pleasure to read. Second, the idea of using the Sherman Morrison formula to approximate the inverse fisher is an elegant idea—I’m almost surprised it hadn’t been done yet! Third, it is great to have both theoretical verification of convergence for the method and the empirical work together, making a much stronger contribution than either of the two alone.\n\n## Weaknesses\n1. There are some choices in the paper that seem to be poorly justified given their importance\n2. There are some issues in the math and proof that, while I expect they do not invalidate the proof, make it unnecessarily difficult to parse and thus need to be addressed. For example, parts of the proof are poorly explained, there seem to be (minor) errors in a number of places, and, most notably, there are quantities and certain uses of notation that are not properly defined\n3. I am concerned about the measures of variance that are being plotted in the figures. What are the error bars? Is the data smoothed before calculating them?", "claims_and_evidence_yn": "No", "claims_explanation": "There are some issues around exposition in the proof, and, potentially, around the standard deviations in the plots that require attention before I can answer yes to this question. See sections \"weakness 2\" and \"weakness 3\" in the requested changes section for concrete examples.", "audience_yn": "Yes", "audience_explanation": "Given that the paper is about policy gradient estimation, if the requested changes section can be addressed then I think the paper could be of interest to large subsets of the RL community", "requested_changes": "I have organized the requested changes into sections based on the three main weaknesses and then unrelated edits (‘misc edits’). I have added “**C**” at the end of changes that I view as critical for my review, and “**S**” after ones that I view more as suggestions.\n\n## Weakness 1\n- Section 4.1 (last equation page 4, and text above it): could you explain why you use the identity and damping coefficient instead of using the previous estimate of the FIM here, or simply setting $\\lambda = 0$? Some justification would be great. **C**\n- Section 4.1 (last equation page 4, and text above it): it would be nice to include some study of how the algorithm works when the previous estimate is reused, and how varying $\\lambda$ affects learning. **S**\n- Figure 1: it would be nice to discuss a little bit why the batched version performs worse than the original version. I assume because of bias introduced through the averaging of the vector before taking the cross product? **S**\n- Second equation section 5.1: $\\bar{l}^k$ is a sample mean, and thus the “approximation” being made is that the expected value of the cross product of $l^k$ with itself can be written as the cross product of the expected values. Presumably this would require that $l^k$ is statistically independent of itself which is of course not the case. Could the authors provide a sentence or two mentioning this assumption, providing some justification, and then, at least in brief, explaining the bias introduced? **C**\n- Last paragraph of results section: what is the justification for plotting log probabilities? Is this done in the literature? It would be good to provide some justification and, if precedent exists, some references.\nHow were hyperparameters selected?\n\n## Weakness 2\n- Equation 2: the expected value on the RHS is over the trajectory, which should make the expectation not depend on state, but the LHS writes $F_s$ as a function of $s$. Why is this? Presumably $s$ is the initial state? If so, should this expression include a sum over time? **C**\n- First equation on page 4: the sum is just a single sum over trajectories, but shouldn’t this be a double sum over trajectories, $i$, and time within a given trajectory, $t$, with $a$ and $s$ depending on both? **C**\n- First equation in section 4.1 (on the top line of the equation RHS): I think $\\hat{F}^{k-1}$ should be $(\\hat{F}^{k-1})^{-1}$ **C**\n- Section 4.1 (last equation page 4): $\\lambda$ is not defined as a damping coefficient until rather later. Should ideally define right after the equation **S**\n- First equation page 5: if the superscript $k$ denotes the learning iteration then it would make sense to index the $\\theta$ values in the RHS of this equation with $k$. Also, it is weird to write $F^k(\\theta)$ on the RHS if $F$ depends on $k$ only through $\\theta$, and also it is inconsistent with the rest of this part of the paper to write $F$ explicitly as a function of $\\theta$ **S**\n- First equation page 5: from which point in the trajectory are $a$ and $s$ sampled in this equation? **C**\n- After Equation 5 and in Algorithm 1: the advantage function is included in the gradient after equation 5 but it is missing in line 7 of Algorithm 1.\n- Theorem 1 statement: It would be good to add the assumptions mentioned above Theorem 1 into the italic part of the theorem statement or, at the very least, organize the assumptions cleanly in the preceding paragraph and then write “under the assumptions listed above…” in the Theorem statement **S**\n- Theorem 1 statement: the variables $L_J$, $\\varepsilon_{bias}$, and $\\sigma^2$ are in the statement of Theorem 1 are not defined—please fix! **C**\n- Theorem 1 statement: it would also be good to define $K$, $N$, and $H$ either right after or before the Theorem statement **S**\n- Algorithm 1 line 10: missing time indices on $R^k$ and value function.\n- First equation in section 5.1: if I am not mistaken, $a$ and $s$ should be indexed by both $i$ and $t$, and there should be a double sum over the indices, right? **C**\n- Last equation on page 7: $\\Delta\\theta^k$ is written $w^k$ in the proof (in the appendix), right? It would be great to make the notation consistent **C**\n- Assumption 3: could you provide more context about this assumption? When is it true? When does it not hold? Can you reference other works that use the assumption and/or study it? What does $L$ represent intuitively? **C**\n- Equation 11: is the first equality in this equation a definition? If so, perhaps use $\\equiv$. **S**\n- Equation 11: what is $\\nu$? Please define **C**\n- Helper Lemmas: the following are not defined: $L_J$ (note that it might be better to choose a different letter given the use of $L$ in assumption 3), $J^H$, $R$, $\\sigma$. Please define these. **C**\n- Lemmas: please reference specific proposition/lemma/theorem numbers in the original papers for each of the referenced lemmas **S**\n- Lemma 1: I don't think this is used in the proof? If so, please remove **C**.\n- Lemma 3: why is $g^k$ defined here and then not used in the equation? Perhaps this should be $\\nabla J^H$? If so, please correct throughout the paper to make notation consistent **C**\n- Lemmas 2, 3: I could not find these results in the referenced papers. Could you point them out to me? Thanks **C**\n- Lemma 4: it seems that the notation $F_\\phi$ is used here but not in the following section (the subscript $\\phi$ is dropped). Please make consistent **C**\n- Section A.3: it is written: “we know from Jensen’s inequality and [EQUATION]”, but the equation just shows a particular case of Jensen’s inequality. This redundancy can be removed, or replaced with something else that was used in the derivation **C**\n- Line 4 of Equation 14: missing $||^2$ on RHS **C**\n- Top of page 16: I’m not sure that it is actually Lemma 3 and Assumption 2 that are used here. Maybe Lemma 2 and remark 2?? **C**\n- Equation 15 \\sigma^2 not defined **C**\n- Equation 15: it seems that the inequality $(x+y)^2 \\leq 2x^2 + 2y^2$ was used twice here; perhaps there is a factor of $2$ missing somewhere? **S**\n- Second last equation on page 16: $H_{,\\star}$ should be $H_{\\star}$ I think **S**\n- Last equation on page 16: missing $16L_J$ on RHS **C**\n- $\\sigma^2$ is treated as a constant but I’m a little concerned that it might depend on $H$, and potentially $N$. Could you provide some insight here? **C**\n- Page 18: it is written: “In summary, we require $N$ and $K$ to satisfy equation 18, equation 20, and equation 22, which leads to…”. I think I would also reference $H$ having to satisfy Equation 18 in this sentence **S**\n- Page 18, second last equation: would you please show the derivations for the conditions on $H$, $N$, and $K$, in the second last equation? **C**\n\n## Weakness 3\n- Figures: are the shaded regions in the figures the true standard deviations of the learning trajectories, or are they the standard deviations after applying the binning and smoothing protocol mentioned right before section 5.1? If the latter case is true, it would be nice to plot the unsmoothed, unbinned data in the supplementary. Also, it would be great to explain this information about visualizing variance in the figure caption. **C**\n\n## Misc. Edits\n- 5th line after Equation 3: I don’t entirely think the sentence needs to start with “Specifically, …”. I believe this could be deleted for more concise writing. **S**\n- Table 1: I assume what is displayed are means $\\pm$ standard deviations, but it would be great to make this explicit in the table caption **C**\n- On page 7 it is mentioned: “To better handle continuous control problems, SMAC and all the baselines we compare against compute advantages using the GAE”. Could you elaborate on this please?\n- 5.1 title (and again later in the appendix): why is the effect of batch side labeled as an “ablation”? This seems like a weird wording choice—perhaps reword? **S**\n- In the last paragraph of the results section it is written: “Finally, we turn our attention to the average log-probabilities of the actions taken during training”, but no figure is referenced (I believe the figure being discussed is in the appendix?). It would be good to reference the correct figure here.\n- Equation 8: it could be nice to define the matrix inequality used here **S**", "broader_impact_concerns": "Given the increasing use of RL methods for not only societally beneficial but also damaging applications, it would be nice to discuss some of the negative applications and what might need to be done to mitigate them", "additional_comments": "Note that my knowledge of current research is more focused on deep learning than RL, so I cannot easily comment on how the current paper fits into the broader literature. Please take this into account when considering my review.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)