Beyond Softmax and Entropy: Convergence Rates of Policy Gradients with $\boldsymbol{f}$-SoftArgmax Parameterization $\&$ Coupled Regularization
Authors: Safwan Labbi
Daniil Tiapkin
Paul Mangold
Eric Moulines
Venue: ICLR 2026 Poster (2026)
Keywords: policy gradient methods
reinforcement learning theory
f-divergence
Tsallis entropy
Shannon entropy
Primary area: reinforcement learning
TL;DR: We introduce $f$-softargmax parametrization for policy gradients in RL and show that it improves convergence guarantees.

Abstract: Policy gradient methods are known to be highly sensitive to the choice of policy parameterization. In particular, the widely used softmax parameterization can induce ill-conditioned optimization landscapes and lead to exponentially slow convergence. Although this can be mitigated by preconditioning, this solution is often computationally expensive. Instead, we propose replacing the softmax with an alternative family of policy parameterizations based on the generalized $f$-$\textit{softargmax}$.
We further advocate coupling this parameterization with a regularizer induced by the same $f$-divergence, which improves the optimization landscape and ensures that the resulting regularized objective satisfies a Polyak--Łojasiewicz inequality. Leveraging this structure, we establish the $\textit{first explicit non-asymptotic last-iterate convergence guarantees}$ for stochastic policy gradient methods for finite MDPs $\textit{without any form of preconditioning}$. We also derive sample-complexity bounds for the unregularized problem and show that $f$-PG, with Tsallis divergences achieves $\textit{polynomial sample complexity}$ in contrast to the exponential complexity incurred by the standard softmax parameterization.

Published as a conference paper at ICLR 2026
BEYOND SOFTMAX AND ENTROPY: CONVERGENCE RATES OF POLICY GRADIENTS WITH f-SOFTARGMAX PARAMETERIZATION & COUPLED REGULARIZATION
Safwan Labbi', Daniil Tiapkin' Paul Mangold', Eric Moulines
CMAР, CNRS, École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France
2 Université Paris-Saclay, CNRS, LMO, 91405, Orsay, France
3 Mohamed bin Zayed University of Artificial Intelligence, UAE
4 LREE EPITA, 94270 Le Kremlin Ctemlin-Bicétre, France
(safwan. labbi, daniil. tiapkin, paul peul.mannggieeeellytemmllleee edu eric m.c...m moul nes ac.ae
ABSTRACT
Policy gradient methods are known to be highly sensitive to the choice of pol- icy parameterization. In particular, the widely used softmax parameterization can induce ill-conditioned optimization landscapes and lead to exponentially slow convergence. Although this be mitigated by preconditioning, this solution is often computationally expensive. Instead, we propose replacing the softmax with an alternative family policy parameterizations based on the generalized f-softargmax. We further advocate coupling this parameterization with reg- ularizer induced by the same f-divergence, which improves the optimization landscape and ensures that the resulting regularized objective satisfies Polyak- Lojasiewicz inequality. Leveraging this structure, we establish the first explicit non-asymptotic last-iterate convergence guarantees for stochastic policy gradient methods for finite MDPs without any form of preconditioning. We also derive sample-complextne bounds for the unregularized problem and show that f-PC with Tsallis divergences achieves polynomial sample complexity in contrast to the exponential complexity incurred by the standard softmax parameterization.
Figure 1: Regularized value landscapes (with temperature À = 1) for one- state, two-action MDP: softmax with tropy (left) with a-Tsallis regularization (right, a = 0.1). The value of the classical cou- pling Entropy-Softnat than for our proposed coupling Tsallis- Tsallis. Using the latter removes flat cas that are far from the solution, allow- ing policy gradient methods to escape the gravitational pull.
a-Tsallis SoftArgmax
is much flatter
300
300
-00
8%
-30
30
30
(a) Softmax/ Entropy Regularization
(b) 0. 1-Tsaallis SeftArgmax/ / Tsallis Regularization
INTRODUCTION
Policy gradient methods are cornerstone of modern reinforcement learning (RL) and underpin many of its most notable successes. Algorithms such as Trust-Region Policy Optimization (TRPO; Schulman et al., 2015) and Proximal Policy Optimization (PPO; Schulman et al., 2017) have demon- strated strong empirical performance across a wide range of domains (Berner et al., 2019; Akkaya et al., 2019). Despite these successes, it has become increasingly clear that the performance and convergence behavior of policy gradient methods are highly sensitive to seemingly low-level design choices, among which the choice of policy parameterization plays central role (Hsu et al., 2020).

---

Published as a conference paper at ICLR 2026
Table I: Comparison of the performance of scalable (1) policy gradient methods with global conver-
gence guarantees on the unregularized objective.
Configuration
Stochastic
Last iterate
Explicit Rates (8)
Parameterization. Regularization.
Mei (2020b)
softmax
X
x
Mei al. (2020a)
Transforrm
X
x
X
Zhang et al. (2021)
softmax
Log-Barrier
X
(4)
puly
Liu et al. (2025)
Hadamard
x
x
X
Ours (Corollary 4.6)
softmax
Entropy
exp
Ours (Corollary 4.7) f, fo-softargmaxx
a-Tsallis
24)
poly
(1) We refer by scalability to policy gradient methods that do not use any form of preconditionning: (2) refers the parameterization induced by using the a- a-Tsallis divergence generator (see Table 2); (3) Explicit rates
means an explicit dependency on all problem parameters and not on intractable quantities: (4) puly indicates
an explicit convergence rate with explicit polynomial dependency on all problem parameters; (5)
exp indicates
an explicit convergence rate with exponential dependence on at least one parameter.
In discrete control scenarios, the default choice is the softmax parameterization, typically coupled with entropy regularization. While ubiquitous, several recent results have revealed fundamental lim- itations of softmax- policy gradient methods (Mei et al., 2020a; Li al., 2023). In particular, in the absence of regularization, the softmax parameterization can induce extremely flat regions in the optimization landscape, leading to an unavoidable exponential lower bound on the rate of con- vergence (Li al., 2023). Although entropy regularization is sometimes introduced in an attempt to mitigate this issue, no polynomial convergence guarantees are currently known in this setting. Even with entropy regularization, the landscape remains flat (see Figure la for illustration). These ob- servations motivate treating the policy parameterization itself as a design choice: rather than varying the regularizer within softmax, ask whether moving beyond softmax fundamentally improve the conditioning of policy gradient methods.
In this paper, we follow the line of work of (Mei al., 2020a; Liu et al., 2025) and propose new flexible family of alternative parameterizations induced by divergence generators (denoted f in the following). which we refer to as f- f-softargmax parameterizatiins. We regularize the objective with the corresponding f-divergence, and we refer to this as coupled paramettrization-rggulaazzzzz pair (i.e., the same generator f induces both the parameterization and the regularizer). This view- point generalizes the classical softmax-entro regularized by Shannon entropy. Similar constructions have recently shown theoretical and prac- tical benefits for supervised learning (Blondel et al., 2020; Roulet et al., 2025), but remain largely unexplored in reinforcement learning. This takes policy gradient methods beyond the softmax and its coupled entropy regularization, yielding a better conditioned optimization landscape (see Fig- ure 1b). In particular, we show that when these parameterizations are coupled with the regularizer induced by the corresponding f f-divergence, policy gradient methods enjoy improved convergence rates. Remarkably, for the Tsallis divergence, this leads to convergence rates exponentially faster compared to the softmax-entropp pairing.
pairing, in which the policy is both induced and
Formally, we study the f-regularized value function under the f-softargmax parameterization. We show that satisfies non-uniform Lojasiewicz inequality and monotonicity property. This mono- tonicity allows us to restrict the optimization to regions that are easy to project onto and in which the Lojasiewiez coefficient uniformly lower bounded, resulting in the uniform inequality over the region of interest. Building on these observations. we establish global last- iterate convergence guarantees for stochastic policy gradient methods in the tabular setting, with fully explicit constants. To the best of our knowledge, these are the first guarantees of this type for policy gradient methods, even with entropy regularization and softmax parameterization, that do not rely preconditioning ization- regularizaationtiooonnn pair (softmax entropy) the resulting uniform -ojjssswwaiii constant is exponentially small in the problem parameters, recovering known exponential convergence rates (Ding et al., 2025; Labbi et al., 2026). In contrast, for Tsallis divergence generators, this constant scales only polynomially,
exponentially large batch sizes. For the KL-induced parameter-
reffecttin reflecting substantially better-condittoned optimization landscape. Addi-
2

---

Published as a conference paper at ICLR 2026
tionally, analysis shows that moving beyond the antropy-softmat pairing yields better trade-off between regularization bias and sample complexity. In particular, Tsallis-type couplings yield poly- nomial last-iterate convergence guarantees even for the unregularized objective, improving upon the worst-case guarantees known for the standard softmax (see Table 1).
Overall, our contributions threefold:
We introduce f-softargmax policy parameterizations and study the regularity of the associated f- regularized value function as a function of the policy parameters. We show that it smooth, satisfies non-uniform Lojasiewicz incquality, and, by exploiting monotonicity property, admits uniform bound on a Solyykk-Ljasiewiee constant on a region of interest that is casy to project onto.
We prove global last-iterate convergence guarantees for stochastic tabular policy gradient, with fully explicit sample complexity bounds that apply to both regularized and unregularized objectives.
We demonstrate that alternative couplings beyond entropy-sofie softmax lead improved sample com- plexity for unregularized problem both theoretically and empirically. In particular, the Tsallis coupling yields polynomial dependencies on problem parameters, resulting in an exponential im- provement over softmax, and provides additional flexibility for practical adaptation.
The paper is organized as follows. Section 2 introduces the necessary background. Section 3 presents the /-softargmax parameterization and the properties of the f-regularized value under this parameterization. Convergence rates for policy gradient are established in Section 4, and numerical experiments are reported Section 5.
Related work. (Policy grudient methods.) ) Global convergence guarantees are known to hold for unregularized policy gradient methods with deterministic gradients, achieving sublinear rates with constant step-sizes (Mei et al., 2020b; Liu et al., 2024). However, the convergence rates of softmax- based policy gradient methods is exponential in the problem parameters (Mei et al., 2020a; Li et al., 2023). Two strategies were proposed to mitigate this issue: first, preconditioning. most notably through natural policy gradient methods (Kakade, 2001), which can alleviate ill-conditioning. but scales poorly larger problems due the nature of the updates. Second, log-barrier regularization (Zhang et al., 2021), which yields polynomial rates but has no last iterate convergence guarantees and is unstable in practice. In contrast, our approach avoids preconditioning altogether and there- fore retains the scalability of standard policy gradient methods, while providing explicit polynomial convergence guarantees for the last iterate.
(Alteraativ Parameterizations) Alternatives to softmax have been proposed and studied in opti- mization (Martins & Astudillo, 2016; Peters et al., 2019; Roulet al., 2025). RL, the study of alternative parameterizations is still in its early stages. The escort transform of Mei et al. (2020a) avoids exponential slowdowns in deterministic settings, but its guarantees rely on increasing step- sizes and do not extend to stochastic gradients. The Hadamard parameterization (Liu et al., 2025) yields local linear convergence in deterministic regimes, but without explicit constants. In this work, propose more flexible family of parameterizations that can adapt various problems and pro- vide explicit guarantees in the stochastic setting.
BACKGROUND
Reinforcement learning. Consider discounted Markov decision process M A,, Pr,,p)
with finite state and action spaces S and A, discount factor 7 E (0, 1), transition kernel P: x P(S), bounded reward function r: S [0, 1]. and initial distribution p. The value of a policy
:: S + P(A) is defined by
(8)
E
Σ + (r((s,)))
(1)
where So = 8, A. ~ T(-1S)), and S.+1 P(-|S, At). For E P(S), we define U (p) E, (s)) For any म. we define a corresponding discounted occupancy measure
=
(7(s) =
(11)(S))
t=0
Parameterizations on the simplex. Following Roulet et al. (2025), we study a family of parame- terizations of the simplex based divergence generators. For given generator f: (0, oo) - IR.
3

---

Published as a conference paper at ICLR 2026
Table 2: Example of classical divergence generators f included in our framework and their associ- ated f-softargmax operators.
Name KL
f(u)
(r Mar))
log (u 1) (w ar + 1)/afa u log(u)) (u log(
Meat (xc[ee)e(((()))eeceeaeo (oa(() exp(x(()))
Tsallis (0 < a < 1)
Mrrr(a) (1 + (a ())((()))()))))))) ()) (or((a) exp(2(x((a) pt))
exp(2(a((a) (1) Here pa and μa are normalization factors that ensures that the weights [xp]/(2eep((((((a)) pa)))
Bensen-Shannon
1.
strictly convex with f(1) O, and reference distribution & with support, we define f-softmax(z, q) == max (EP(A)
{(1, x) -D (vllg))
fssotarggax((;; q) == arg max {(,,z) - D'((vl))) MEP(A)
where D' (pllg) is the f-divergence between p and q (see Csiszár, 1967, or Appendix A). Since D' (pllg) is strictly convex in its first argument on the simplex, the output of the f-softargmax operator is well defined and unique, as it corresponds to the arg max of a strictly concave function over a compact set. This construction recovers the classical softmax as special case and yields rich family of alternative parameterizations (see Table 2). Computing f-softargmax reduces to solving a mie-dimesiiona root-finding problem, which can be done efficiently by dichotomy; see Roulet et al. (2025) and Lemma B. for details.
f-regularized value functions. Given a reference policy Tref, temperature 2 0, and a divergence generator f, the f-regularized value function of defined by
of (s) = ET E A)) (x(1(())
key result (Geist al., 2019) that the optimal regularized value (s) == max, (s). together with optimal policy n.. admits closed-form Bellman characterization:
(s)) = max
vEP(A) (1,, - A D' (v][=rot(||s)))
(2)
nd (+1s) arg max (V, (8,-)) (v(oTror(())))) DEP(A)
where (ss) +P
3 COUPLING PARAMETERIZATION & REGULARIZATION
We introduce a new class of policy parameterizations for reinforcement learning, which we refer to as I-8oftargmax policies. Let कeef denote full- cull-support reference policy. For E RISI[A), we define the f-softargmax policy by
TÓ (-|s) == (ooftargmax(f(s;.. (-e()) Vs S.
(4)
This parameterization can be directly used within unregularized policy gradient methods (see Ap- pendix G). However, in practice, unregularized methods tend over-exploit and converge prema- turely to suboptimal policies. This suggests that the choice of parameterization should be guided by the geometry of suitably regularized objective, rather than considered in isolation.
To understand which regularization is naturally associated with the f-softargmax family, we exam- ine the structure of the f-regularized problem (3). The optimal policy of this problem admits the following representation:
of (-1s) f-softargmaattt (g!(s, )//,, (
In particular, we choose logits of (s. = (s(s).)AA + b(s), where b: S + is an arbitrary state-dependent baseline, then the f-softargmax mapping exactly recovers the optimal f-regularized policy, i.e., m/. = =5.
4

---

Published as a conference paper at ICLR 2026
This shows that the f-softargmax parameterization is not arbitrary: it precisely matched to the ge- ometry of the frregularized problem. Under this parameterization, learning the policy is equivalent to learning the regularized optimal Q-function, and the associated f-divergence regularizer arises naturally from the variational characterization of the optimal policy.
To further formalize the benefits of such coupling, now establish the smoothness, well Polyak-E.ojasiewiez inequality, of the /-regularized value with coupled parameterization vg = v m
We derive these properties under the following two assumptions on and Tref-
Assumption P P(Tref). There exists number Tref > 0 such that min(s.a) (rof(als) > Tref-
Assumption (TTe). The generator function f satisfies:
(i) fü is bounded, strictly convex on [0; 1/Tret). f(1)=0, and f is thrice differentiable on (0, 1/ret) (i) limato+ f'(u)= -- and lim (f(()/ (u)) <o;
(ii) there exists wy E [1, X0), and Kf E (0), such that for any u E [0; 1/ /ret). we have (/) S wy, and If (""( (1)21 kyj
(iv) there existsey E (0, 1] such that f" decreases on [0: and foru /rre)/ ff
These conditions met by broad class of commonly used divergence generators, like the KL, Tsallis with < 1, and Jensen-Shanner Shannon (see Appendix F).
Remark 3.1 Tsallis divergences with
violate condition (ūi): since (0) finite, the induced
policies are sparse, leading to non-smooth parameterizations.
Under P (Tef and y (Tret), we can define the weights (als) and the sum (s). defined as
1
(als)
wx( = E Tree (s) aeA (als) (rer(s)))))))
(als)) (s(()) ("( (allss//mmm((lll)))
(5)
which will play a central role in our analysis. In the KL divergence case, we recover simple expres- sions w/ (als) = Ty (als) and (s((s) 1. Using the notations in (5), express the gradient of the regularized value.
Lemma 3.2. Assume that, for some Tzel 0, f and Feef satisfy A (Tret) and P (Teet) For any E S, we have
(v)(p) = (1-7)-1 (s 2 00(s,.)
[o6(s.)) -20(s,000))))
where for any vector u RIAI, (u) == diag(w) (u) uu qº := r PPby and ds)(s) == 0%d (s).
Next, we introduce three quantities that that arise naturally in the expression of the Hessian of (p)
Σ (als) (vilaa/ dy d= (((la)//aaalab)))
D' (e((((TT)((11s)) (6)
max Yf (#p)ESXP(AAaEE)
(s.))ESP((A)
min (S.))S)P((A)
EaEA Ted(als) > (irlaa/Fnerlass))
Since they are bounded under (Tret) and P W.t)) we can establish the smoothness of w/ (p).
Theorem 3.3. Assume A (Tei)) and P(Tret) for some Tref
0. For any 0 RI
2 (p)ll2 I Lg with
W [W + X- (w7d, + (nydd + +yz) + ws + 2x18s)
L= o
31
We refer to Appendix B.4 for a proof and a complete expression of L.y We now introduce the classical exploration assumption (Mei al., 2020a;b; Agarwal et al., 2021).
Assumption Ap. The coefficient Pain == min.es p(s) of the initial distribution satisfies Pmnin >> 0.
Next, we derive Non-Uniform Lojasiewicz. inequality.
5

---

Published as a conference paper at ICLR 2026
Theorem 3.4. Assume that, for some Tzef 0, A (Tret) and P P(Trre) hold. Assume in addition that the initial distribution p satisfies Ap. Then, it holds that
(V) 2 (o)
with (y(00) : X(1 - P) (5)/w mins,a (
We prove this theorem in Appendix C. To highlight the main steps of the proof, we give sketch of the proof in the bandits setting, where the state space a singleton.
Sketch of the proof in the bandits case. The proof consists of two steps: (1) we bound the sub-
optimality gap by the distance between the logit and the rescaled reward: (2) then link it to the gradient of the function.
Step 1: By (2), the optimal regularized value is equal to v. x f-softmax(r/A, Reat). Next, since (D((m)) (TT) [|Tt))). and v/g (TT.. AD
f-softmax(B. Tret (Tgg -D gap rewrite as
D' (#g) (eet)) the the suboptimality
v 1 X f-softmax( A. Tret) (Th +ADD (T/ (
= => f-softmax( Free f-softmax (0, Tret) - (Tb X x-10 -]]
Combining T = [-softmax Tret), and that for a E IR, Esoftmax(0 + a1 Tref) =
f-softmax (,, Tet) + a yields
v v/ X {|E-softmax( mrdd f-softmax(( 0 K3J ((e)
(V f-softmmax(( - K/ 114 Teet), r/> - K/ 11/1,1
where we have defined K/- = (r/A- 0, |/4/ //. Defining C/ = r/> - 0 - K₁ |l, and using second-order Taylor expansion of the function f-softmax(-)) between, we obtain
v vf = (C)) T V f-softmax, (E)C)
(8)
for some & on the segment joining + K 1 |A| and r/A. Next, by Lemma B.5, it holds that || [=softmax(E]]] 2wy, which implies v v/ I >w
Step 2: Using Lemma 3.2. we have Veg = W/ H(w (ww() [r ^0). Next, applying Lemma 23 of Mei
al. (2020b) (see Lemma I.4) gives
| 2 2 w/ min w 11 Ss min w/ llc/
aeA
aEA
where by Lemma B.6, we have w Cy. Combining the two bounds concludes the proof
For softmax parameterization coupled with entropy regularization, we retrieve property outlined by Mei et al. (2020b). However, their proof is highly specific to the entropy-softmax pairing case and cannot be extended to general f f-divergences. because it relies in an essential way on the logarithm's special properties. Indeed, their proof require rewriting the soft sub-optimality gap o (p) - dg Xl (p)
as Eves (ss) (-15'(-1s)) (/ which is not possible for general f. Our proof is more natural, as it simply relies on Taylor expansion to obtain the inequality (8).
From Non-Unifonee Uniform Lojasiewiez to folyak-Lojasiewicz To obtain a Polyak-Laa Lojasiewicz bound, need to bound the coefficient (0) uniformly. To this end, we restrict the optimization to smaller subspace, eliminating policies for which the regularization is too large. Given a policy π and 0 < < T2et/2, /2, we define the projection-like operator U, for every (s, a) E S x A,
if IT (Tnr)))
(a(sss)ss)= T(als) by (s), ((als),
if (s), otherwise,
where we define by (s)= EDEAT(S) Free (b|s)T - (b|s). a (x) = arg max ma (T(lss))mmmmmm where ties in the arg max are resolved arbitrary, and
(5 : fa A, k(a Tre (als) S <T/2]

---

Published as a conference paper at ICLR 2026
Algorithm J-SoffArgmax Policy Gradient
1: Initialization: Learning rate O, initial parameter 0o, divergence generator f. batch size B.
2: for /00 to T 1 do
3: Collect Z (5t,0:11-11 A4, 1.0:H-11:0 B-1 using m/.
4: Compute the gradient 82, (6,) using (11)
5: Update Oc+1 = Trx (0: + 187, (0+)
6:
Return Of
This operator prevents policies from becoming "too deterministic": if the probability of any action gets too close to zero, increased above threshold that depends on and Tyef. For a proper choice of applying this operator on policy returns a policy with higher regularized value.
Theorem 3.5. Assume that, for some Tie > 0, and Tret satisfy A (Tret) and P (Teee) and that p satisfies Ap. Let
TA T>=min(U")1>(
16 16+87Ad
(-4)())))) 2
XII "omin
Penin
Then, for any policy a and for गे = UTx (T),, it holds that 4 (p) 2 of (p) and that H(als) 2 Trf
Since Ur operates in the space of policies, we lift it the parameter space by defining operator Tr such that for IISIIAI, we have Tf.s U6 (see Appendix for an explicit construction). Finally, we show that with the choice of threshold from Theorem 3.5, we can give uniform lower bound of μ on the set of restricted logits. This shows how the non-uniform Lojasiewiez inequality is upgraded to Polyak-Lojasiewice condition: it suffices to restrict the search to paramelers that encode non non-degenerate policies, since such policies are provably suboptimal.
Corollary 3.6. Assume that, for some Wrof
0, f and Tref satisfy A y (Tret) and P(Trnt) and that where Tx is defined in Theorem 3.5.
satisfies A. If S (T-7)-Puin min( [y
|(()5)1 11" (
Under this condition, it holds that inf puy (Tx 2 E. where
4, 1 X(1 - 7) m ((
)² /// PPmm) Pminn
16 16-88
where f* is a convex conjugate of f.
CONVERGENCE ANALYSIS OF f fPG
In this section, we aim optimize the f-regularized value under f-softargmax parameterization.
max (0) : =r',[()}}}
OEB
The f-PG algorithm. We introduce f-PG (Algorithm 1), an f-SoftArgmax policy gradient method with coupled regularization. dependent truncated trajectories of length I from ((z;-)) defined for single truncated trajectory
each iteration of f-PG, the agent samples a batch of in-
2 (sh, N= HH1 (S x A)" by D(T; 2) = ((oo) 111 P(s)/9n-1.0h-1)TT(( (h-1) (s))
Then, the agent performs the update
0++1 Tr, (0: 8/, (0.) t
(10)
where 7) >> 0 is a learning rate, Tr, R [S + R|S||A|| is the projection like operator defined in Sec- tion 3, and 82. (0.) is REINFORCE- estimator (Williams, 1992) Vuy, (p) that uses a batch of
B independent trajectories Z+ ~ [v(0.)] @B For a batch of trajectories (60: ab B-1 this estimator is defined
00:1-106600
#-1
log TO (a s/) " (r ab) X (p))))
{0 B
(1I)
00
6=0
A=U
8=0
where (/ a r a
AD (T (lee) (s and (s(s) | is defined by
(0()))(.m))=11(( (s) (blss) وااااا
( A(s S
acA

---

Published as a conference paper at ICLR 2026
Remark 4.1 (Connection with (Lazy) Mirror Descent.) We stress that f-PG is fundamentalty dif- ferent from mirror descent. Let ((T))= Ese D (T(- (er mirror descent iterations are
( + V (p)l==m T4+1 arg min ( (V((#(4),, -m+1))> (12)
where P(A)|S) is policy. Demoting 02 (++) one obtains updates that semble (10) (without Tra), with one key difference: the gradient in (12) is taken with re- spect the policy whereas in (10) it computed w.t. the "dual" parameter 0 (in the mir- for descent terminology). Moreover, the update (12) can be expressed as, by the chain rule, 01+1 02 nl l V (0c), which have an additional preconditioning term given by the inverse of the policy Jacobian. See Appendix H for more details.
Next, we bound the bias and variance of the gradient estimator proof provided in Appendix E.1).
Lemma 4.2. Assume that, for some Tref 0, f satisfy A (Tref) For any ||SIIAA we have
lg (0)
av5(e)
12 33, Ez [lg [1ll (0) (0)12) S ?
de
where Z ~ [v(0)) and where
of
12
w w W A
By
2x 2 (1-7}² w/ 12+2Ad +
Convergence analysis. We now present our main result for this section, which gives conver- gence rate for f-PG with explicit constants for the regularized problem. This result is based on the regularity properties of the regularized value function, which developed in Section
Theorem 4.3. Assume that, for some Tret > O, f and Teet satisfy A ((Trct) and P(Tret), and that satisfies a- Fix 1 1/(2T.), and X and Tx in Corollary 3.6. Then, for any t 0, the iterates of fPG satisfy
E B[A S (1
Do
Bp, 1
with A, = ()( v/ (p), and o and 37 from Corollary 3.6 and Lemma 4.2 respectively.
We provide a proof of this result in Appendix E.2. A crucial feature of this theorem is that it is explicit, all the terms that appear can be expressed using rrblen-dependent constants. This allows us to derive the following sample complexity result for optimizing the regularized value.
Corollary 4.4. Let 0 and H S (1 7)² 1og(1/u,), and 1 S , ,eBu, o Under assumptions of Theorem 4.3, the final iterate of JPG satisfies Blu (p) w/ (p)) S E with
log (166))
TS max
L
Importantly, Corollary 4.4 shows that f-G achieves convergence rates comparable to stochastic gradient ascent in the strongly convex regime: O( log(1/e)) in the low-variance setting, with con- dition number x > 0, and (((1/e) log(/e)) in general.
Convergence for unregularized objective. A natural question is then how to compare different choices of regularizers, since each method optimizes a distinct regularized objective. By appropri- ately tuning the temperature X, we recover the final sample complexity bound for the unregularized problem. We give a precise statement and proof of this result in Corollary E.
( -, Define oj min(1/dr. 1/ys, , 1), and set X = (1 (1- (1-4) Cj. Under assumptions of Theorem 4.3, the final iterate of PPG satisfies (p) vay (p)) with
Corollary 4.5. Let < 6 < (1 - Pmino min() (.))))1,1
TS (f*)"( (c,(112))' )-
((vf(p) -v2(001)
log
B(1 - p2 Frel
Punin
6
H log ( 1/2,), and S a with a = (1 (1- and =({()))) "c) 3 2re 2 where f is convex conjugate of
(( Pmii )2
8

---

Published as a conference paper at ICLR 2026
This corollary shows that the convergence rate to the unregularized optimum is primarily controlled by the asymptotic behaviour of (f*)". As the target precision E + 0, divergences for which (f*)" grows faster yield better conditioning, which in turn results in faster convergence.
Sample complexity for specific choices of f. We now provide a more complete interpretation of these results by stating sample complexity bounds for specific choices of f.
Corollary 4.6 (Complexity for Softmax- -Entropy). Let be the Kullback-
divergence gener- ator. Let > O. Under the choice of 1) X, H. Tx, and T of Corollary 4.5, the final iterate of fPG
[log(Taa)]]
achieves Elv.(p) -er -.r(()) (p)] S in TBH E <"(1-))'
exp( ((1-7)
samples.
This corollary shows that the number of samples required by the softmax policy gradient method is exponential in 1 1/(1 - 7). This is in line with recent work on vanilla softmax policy gradient, which demonstrated that the number of steps
least exponential in 1/(1 7) (Li et al., 2023).
Corollary 4.7 (Complexity for a-Tsallis SoftArgmax with a-Tsallis regularization). Let be the divergence generator for a E (0, 1) (see Table 2 for its expression). Let é O. Under the choice of 7, X, H, Tai and T of Corollary 4.5, the last iterate of f fPG achieves Efu,(p) - (p) S e in number of samples
Craidr--reesieRRee
(1 - a+) log((ore cta((1 - -2) P Tref 4+7(1-0) (1+ Eaa Pmiin
[rog(Tret)
44 4-
TBH S
We give detailed versions and prove these corollaries in Appendix F. These corollaries show that Tsallis SoftArgmax parameterization with coupled regularisation allows for faster learning, reducing the dependency (1-7)-1 from exponential in Corollary 4.6 to polynomial in Corollary 4.7. Next, we approximate the choice of a that achieves the fastest convergence (according to our bounds).
Corollary 4.8. Assume the conditions of Corollary 4.7 hold. The value of a that minimizes the (//loo((/)) (1/))) More-
sample complexity in Corollary 4.7 is given by a (c) (olo(/)))))) +o (1 (1/log(1) over, for sufficiently small, choosing a = a<) yields a sample complexity -12 poly(11((1 7), 1/mmnn 1/ Tref) up logarithmic factors.
These results show that the best choice of a is not = 0 nor a 1, but depends on the desired precision level. This corroborates results from the bandit literature (Zimmert Seldin, 2021), and gives strong evidence that T'sallisSSftArgmmal with coupled regularization has the potential to ac- celerate RL algorithms. It also highlights the strength of our framework: one can choose, among multiple parameterizations, the one that is best suited for the problem at hand.
5 EXPERIMENTS
In this section, demonstrate the generalizability of our framework by showing that our class of parameterizations, with its coupled regularization, can be readily integrated into modern on-policy reinforcement learning algorithms. For this purpose, introduce and evaluate a-Tsalll alllis РPO, a simple yet principled extension of Proximal Policy Optimization (PPO; Schulman et al. 2017)'. Our approach is obtained by replacing both the policy parameterization and the entropy regular- ization in PPO with their Tsallis counterparts (see Appendix J for full experimental details). We compare the performance a-Ts a-Tsallis PPO against the standard PPO baseline (Schulman al., 2017) on two families of enviromments that we describe below. Our code is available on GitHub: https: : / / gigthub..c.m www./o///mabb/ee.a
fwan htt///frrguuaae www--isdppplooooo wwweeccyyrriaaie
Noisy CartPole (Osband et al., 2020). This environment is variant of the classic CartPole control task in which additive noise is injected into the reward signal. The underlying dynamics is unchanged: at each time step, the agent applies left or right force to cart in order to keep an inverted pendulum balanced, receiving a base reward of +1 each step the pole remains upright, and the episode terminates when stability is lost or after a time limit. However, the reward returned by the environment perturbed as it = Tt + a &,, & ~ (0, 1), where o > controls the noise level. This preserves the dynamics and optimal policy, but increases the variance of observed returns.
Additional experiments on the exact F-P algorithm are provided in Appendix J.

---

Published as a conference paper at ICLR 2026
Avaragn 1s0urm
Average return
Average zeturn
Avergee zeturn
400.0
300.0
200.0
200.0
200.0
200.0
0.0
0.0
1.0
0.0
0.5
15
2.0
1.0
0.0
0.5
15 (X109)
20
Steps (x:10f)
Stegs (x109)
Stegis (X10
Steps
(a) Standard Carpooo
(b) Noisy Carppole o² = 0.5
Noisy Cartpolc, 0²
2.0
(d) Noisy Carpolee a² 10.0
--salllss
0.3-Balis PPO
0.5-Ballis PPO
0.7-Ballis PPO
0.9-Ballis
PPO (baseline)
Average reture
1.0
Average patuen
1.-
1.0-
Average setura
0.8-
0.8
0.8.
0.5
Average
0.5
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.0
Steps (X101)
Stops (x10f)
Steps (x(31)
Stops (x (x10f)
(c) Deepsea, Size 20
(f) Deepsen, Size
Despeen, Size 40
(h) Deepsen, Size 50
Learning curves for Noisy CartPole (top row) and DeepSea (bottom row) under different choices of the Tsallis parameter For Noisy CartPole, we report the standard un- noised CartPole environment (a) and reward-noisy variants with increasing noise levels (b-d). For DeepSea, we consider grid sizes L E {20, 30, 40, 50} (e-h). Each curve corresponds to the best temperature and step-size for given a and shaded regions indicate + one standard error over 25 seeds. On Noisy CartFole, values < 1 consistently improve performance over the PPO baseline in the standard and low-noise settings, with the gap increasing as the reward noise grows. On DeepSea, the improvement over the PPO baseline becomes more pronounced with increasing L, where a = 0.7 achieves the highest returns and the fastest learning.
Figure 2:
DeepSea (Osband et al., 2019). DeepSea is an RL environment designed to study deep explo- ration under sparse rewards. The environment is directed grid of size L L. The agent starts in the top-left corner (0, 0) and, at each step, moves downward while choosing between two actions that shift agent's 's position either left or right. Thus, each episode lasts exactly L steps and corresponds to selecting binary action sequence of length L. which defines unique path through the grid. Only a single trajectory. the one that selects the hidden correct (right) action at every depth reaches the rewarding terminal state at (1-1, 1). However, selecting the right action is not free: every time the agent moves right, it incurs a small movement cost 0.01 L.
Problem-adaptive couplings yield better performance. Figure 2 illustrates that no single choice of a is uniformly optimal, and that different tasks favor different couplings of parameterization and regularization. On Noiss, sy CartPole, the standard setting (Figure 2a) and the mildly noisy variant (Figure 2b) show a small but but systematic advantage for a < over the PPO baseline, which becomes more pronounced as the reward noise increases (Figures 2c and 2d). By contrast, on DeepSea, where performance depends on discovering single sparse-reward trajectory, the hardest instances (Figures 2g and 2h) favor an intermediate value a 0.7. These observations suggest that highly noisy environments and deep exploration problems may benefit from different regions of the Tsallis family, supporting the need for tunable parameterization-rrgllaazzz
pair.
CONCLUSION
We proposed a new class of policy parameterizations based on operators induced by f-divergences. Equipped with matching fddivergence regularizer, this framework generalizes the classical soft- max-entropy pairing and allows flexible alternative parameterizations. Using Tsallis divergence instead of Shannon entropy, showed that the resulting algorithm yields polynomial, rather than exponential, convergence guarantees for the unregularized RL problem. Empirically, this choice leads to improved performance in exploration-heavy and noisy environments. An important direc- tion for future work is to extend these guarantees for adversarial MDPs, where Tsallis regularization has already proven effective in the bandit setting (Zimmert& & Seldin, 2021).
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We would like to thank Vincent Roulet for a fruitful discussion on Mirror Descent and for providing the implementation of f-softargmax operators in JAX. The work of S. Labbi, and P. Mangold has been supported by Technology Innovation Institute (TII), project Fed2Learn. The work of D. Diaiknnin has been supported by the Paris fle-de-France Région in the framework DIM AI4IDE. The work of E. Moulines has been partly funded by the European Union (ERC-2022-SYL WED2-SYG-OCEAN-OOOO 1601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Jourmal of Machine Learning Research, 22(98))1-76, 2021. URL http: /tte:p::/mmma wttppappes/v///1see.e.
html.
Ilge Akkaya, Marein Andrychowicz, Maciek Chociej. Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's 's cube with robot hand. arXiv preprint arXiv:1910..m 13, 2019.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 19Xiv:1912.06668 2019.
Mathieu Blondel, André' F.T. Martins, and Vlad Nieulae. Learning with fenchel-young losses. Jour- nal of Machine Learning Research, 21(35):1-63 2020. URL http: jmlr. org / wwtp.ppprspp...spp/eeee. v21/19 021 html.
Sébastien Bubeck al. Convex optimization: Algorithms and complexity. Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Foundations and
Imre Csiszár. On information-yye typp measure of difference of probability distributions and indirect observations. Studia Sci. Math. Hungar, 2:299-318, 1967.
John M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathe-
matics, 14(4),641-644 1966. doi: 10.1137/011405, URL https: http:////ei...og.../..o 0114053.
Yuhao Ding, Junzi Zhang, Hyunin Lee, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. IEEE Transactions on Automatic Control, pp. 1-16, 2025.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized Markov decision processes. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2160-2169. PMLR, 09-15 Jun 2019. URL https: httpas:/pprroooo http///oocedggg////// nggs. mml.. press /veas//97/00 / iigggeistti 9a html.
Jean-Baptiste Hiriant-Urruty and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Chloe Ching-You Yun Hsu, Celestine Mendler-Dünneer, and Moritz Hardt. Revisiting design choices in proximal policy optimization. arXiv preprint arXiv:2009. 10897, 2020.
Anatoli Juditsky, Joon Kwon, and éric Moulines. Unifying mirror descent and dual averaging. Mathematical Programming, 199(1):793-830 May 2023. ISSN 1436-4646. doi: 10.1007/ s10107-022-01850-33 URL
Sham M Kakade. A natural policy gradient. In T. Dietterich, S. Becker, and Z. Ghahra- mani (eds.), Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001. URL http::::/ppocceddnggs.... www.wiinw.........s..ew.w. wwwppppprpppppppppppppppppppp..e htpppppee_.iiee/ppeee//000 fi Ba3

---

Published as a conference paper at ICLR 2026
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Safwan Labbi, Paul Mangold, Daniil Tiapkin, and Eric Moulines. On global convergence rates for federated softmax policy gradient under heterogeneous environments. In The 29th International Conference on Artificial Intelligence and Statistics, 2026. URL https:/ /ttps///ppeeeeiie... net/Eorum? indiiiddaa APAq9U
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. Softmax policy gradient methods can take ex- ponential time to converge. Mathematical Programming, 201(1):707-802, Sep 2023. ISSN 1436-4646. doi: 00100077111107-022--19266 021-077-222-1920---
URL https: /ttp///ciii/ http://ai...or///////// 0000/000000/
Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions Information Theory, 52(10):4394 4412, 2006.
Jiacai Liu, Wenye Li, and Ke Wei. Elementary analysis of policy gradient methods, 2024. URL
/ /ttp//aavvvv//.///////eee//..avl org/ abs 2404 03372.
Jiacai Liu, Jinchi Chen, and Ke Wei. On the linear convergence of policy gradient under hadamard parameterization. Information and Inference: A Journal of the IMA, 14( (4(1)aaaa0003, 2025.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference chine Learning Research, pp. 1614-1623, New York, New York, USA, 20-22 Jun 2016. PMLR. URL httpt::p///........ http:://rroceee ngs 8 ml p.w.spsssssee.... v ht/artaainnss 16..66666 html.
Machine Learning, volume 48 of Proceedings of Ma-
Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvari. and Dale Schuurmans. Escap- ing the gravitational pull softmax. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1130-21140. Curran Associates, Inc., 2020a. URL https: httt:///toooooccc////et///ceccee neur cc/paper_ -ap07--appr.... pdf.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6820-6829, PMLR, 13-18 Jul 2020b. URL https:::: www.htttss./roceeeiiingg proceedingss..... ml r.l.. press / v 9 me 20b.htmm html.
Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 3462-3471. PMLR, 10-15 Jul 2018. URL https: pwoceedo wtt.sss....pr.ssreemm mensch188 8a. html.
Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course, volume 87 of Ap- plied Optimization. Springer Science & Business Media, 2004. doi: 10007/978-1-4419-8888
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Programming, 120(1):221-259 Aug 2009. ISSN 1436-4646,
doi: 10.10077/111007-007740444444 URL https:
///oi. www.eoogggoo... 1007 000000///1100000 s10107 000-0000-0000
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 62, 2019.
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020. URL https: : /pwpreviieweeeeee////ee net forum? Eterygf-ksYor
12

---

Published as a conference paper at ICLR 2026
Ben Peters, Vlad Niculae, and André F. T. Martins. Sparse sequence se-ceuce----equence models. In Anna Korhonen, David Traum, and Lluís Märquez (eds.), Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics. pp. 1504-1519, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 1 1146. URL https: //aclantholog www.hholoo...oooooo. org. 11////19911////
Martin L. Puterman. Discounted Markov Decision Problems, chapter 6, pp. 142-276. John Wiley and Sons, Ltd. 1994. ISBN 9780470316887.
doi: https:/ddi.org/10..100 1002/ 9780470316888.cc66 URL. https:/ on ine wewrriinllbbrrrr..e 1002/978047050 11e116887..chcc.
Alfréd Rényi On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of stafistics, volume 4, pp. 547-562. University of California Press, 1961.
Vincent Roulet, Tianlin Liu, Nino Vieillard, Michael Eli Sander, and Mathieu Blondel. Loss func- tions and operators generated by f-divergences. In Forty-second International Conference on Machine Learning. 2025. URL https: /ttp://////pereieee.e. wetriiewwee////eeeeem http::/weee/eettteeeeeeee Soorummid-VVYYPP-A.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning. volume of Proceedings of Machine Learning Research, pp- 1889-1897, Lille, France, 07-09 Jul 2015. PMLR. URL https: /ttpas//ppccceeieegeeee mlr. press/val vv37
15.15..hmmmm htmll
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv:1707.06344 2017.
Ronald J. Williams. Simple statistical gralient algorithms for connectionist reinforce- ment learning. Machine Learning, 8(3):229-256 May 1992. ISSN 1573-0565. doi: 10. BF00992696. URL wwt.tttt/////tt //oii.///ooi.. org/ 10. wtt.://///.././....////.////.//1 0ww.00////000666666
Lin Xiao. Dual averaging method for regularized stochastic learning and online optimiza- tion. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009. URL https://proceeste neurips watpssscc/ppee paaper_files/paprr/222 2
paf..r.df.
Junzi Zhang, Jongho Kim, Brendan O'Donoghue, and Stephen Boyd. Sample efficient rein- forcement learning with reinforce. Proceedings of the AAAI Conference Artificial Intel- ligence, 35(12):1088--0899 May 2021. doi: 10.16099anai.v35112..777 aaai htta::/t.........eee.e.///aaaaar
URL https:
Julian Zimmert and Yevgeny Seldin. inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1 19,,,,4449999 2021. URL http: / jmmrr. otg/papprs/w22// 9- 9-119---3.. 3. html.
13

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
A Notations
14
B Smoothness of the objective
16
B.1 Properties of the soft-f-argmax
B.2 Specification to the f f-divergence generators Table ................................
20
Derivatives of the policy
22
B.4 Smoothness of Objective
................................
23
Non-Uniform Lojasiewicz inequality
28
C.I. Lower Bounding the norm of the iiee............................
29
C.2 Bounding the Suboptimality Gap
30
Monotome Improvement Operators
31
E Convergence analysis of Stochastic Policy Gradient
35
E.1
Bounding the bias and variance of the stochastic estimator
35
E.2 Sample complexity of Stochastic f-PG
40
E.3 Guarantees the non-regularized problem
43
F Application to common f fidieergences
45
F1
Kullback-Leibler
45
F2
a-Tsallis
50
G Discussion unregularized Policy Gradient with f-SoftArgmax Parameterization
57
Links with Mirror Descent
Technical Lemmas
J Experiments
61
J.1 Uncoupling the parameterization and the regularization
61
J.2 Tabular experiments
61
J.3 Full description the deepRL experiments
62
A NOTATIONS
f-Divergence. Let (0, R be a strictly convex generator with f(1) 0. Its adjoint
(or reverse generator) is [+(u) == u f(1/u) u 0, which convex, strictly convex if f is, and satisfies fi (1) O. Boundary conventions are f(0) = lim f(u) [-00,oo) and (0)
limujo fi( = limyto f(t)/t (-o0, For p.q E P(A) over finite A, the f f-divergence is
('(pllg) = Σ
+
Σ
p(a),
(13)
=))
with conventions: (()) if ((a) p(p = 0, and 0 p(a) = g(a)= = 0 (Rényi, 1961; Csiszár, 1967: Liese & Vajda, 2006). f d-vvergeeness satisfy D' (pllg) E [0, oo], are jointly convex (Csiszár, 1967), vanish iff p g, and are not symmetric (D (pllg) D' (xllg)).
14

---

Published as a conference paper at ICLR 2026
Symbols
Meaning
Definition
State space
Section 2
Action space
Section 2
Discount factor
Section 2
Transition kernel
Scction 2
Reward function Policy
Section 2
Section 2
Tref
Reference policy used the regularization problem
Section 2
Divergence generator
Section 2
Temperature of the regularization
Section 2
Initial state distribution
Section 2
Ky
Upper bound on (x: f"
y Fref
Upper bound on fxx="(
Trof
d
Upper bound on set of divergences
Upper bound on a quantity that depends on f" and f Lower hound on a quantity that depends on f"
(6)
Cr
(7)
8
Value function a policy æ Regularized Value function of policy Transition kernel induced by policy m Regularized Q- Q-function of policy
(1)
of
(42)
Pa 47
Section
(47)
d
discounted state visitation of policy
(48)
Parameter of policy (element of ||
Section 3
mg
The soft- f-argmax policy associated with
(4)
w
A matrix of size xAA such that for any E S, w/ (-1s) )) E P(A)
(5)
(alss
shorthand notation for f'(mg (4)]) shorthand notation for (" (a)
(35)
(als)
(36)
So (als)
short hand notation for f"T( (a [s)s) (a)o)))(a)s))
(37)
W
function of fo (-1x)
(38)
(s)
A function of f-1ss) and f% (-1s)
(38)
T
Number of iterations performed by f-2G Stochastic estimator of the gradient at 0 Truncation horizon in f-FG
Algorithm 1
# (0)
(11)
Algorithm
82 (0)
Stochastic estimator of the gradient at 0
(11)
By
Bias of the stochastic estimator at 0 Variance of the stochastic estimator at 0 Local smoothness of the objective at
Lemma 4.2
dj
Lemma 4.2
Theorem 3.3
P(A) D' (pllg)
Set of probability measures over A f-divergence between two probability measures and
Section 2 (13)
Distribution of the state-action sequence. The state-action sequence At)c0 defines stochastic process on the canonical space (S AYN, For any initial state sp E S, we denote by pat the law of this process. That is, for any E N and any subset B C (S x A)".
n-1
pT B Σ
Σ
1 1 (s0, ao),................... ..... (8n-1, 1))
II
n (as|s;) ((s4+118s;;;) 1=0
(aD EE (S1--)F--))ES--
with the convention 8o is the given initial state. We denote by E the corresponding expectation operator. In particular, the state sequence (s:)12 defines a Markov reward process (Section 2. 1.6 in Puterman (1994)) with transition kernel
(s (s)
Σ P(s' ((a))(aa)
Norms.
For x Idd, we define the norms
1/2
d
d
|0olo0 = max |xd
||
= Σ
|xa
||0||| =
bxy
12
ie ()......d))
15

---

Published as a conference paper at ICLR 2026
For d x d matrix M, we denote by ||M and ||M]| respectively the max now sum, and the
spectral norm:
| sup [| ||0] sup
Ma ||M]] sup(1
||
iE().....))
240
(14)
Recall that, for any a E R M & || |/ and || S |
Functional and matrix forms. For notational convenience, we also view as (IS) ((AI) |S|
matrix with entries (s..a).s' P(s' s, s. Similarly, of is vector of size |S and q vector of size [S] [A]. Finally, we identify the parameter 0 E RxxA with its matrix representation 0 RRSS|A indexed by (s,a) switch between functional and matrix views.
A. This slight abuse of notation allows us conveniently
B SMOOTHNESS OF THE OBJECTIVE
In this section, establish the smoothness of the regularized value function vig == v (p) with respect to the parameter 0. As first step, we show that the policy Th is smooth under suitable assumptions on the divergence generator and compute its first and second derivatives. To do so, we start by studying the properties of the sort-f-argmax operator and then apply the obtained results to derive properties of the policy T/.
B. PROPERTIES OF THE SOFT- AARGMAX
In this Section, compute the derivative of v (.) == f-softargmax(z, Mset) and x-softmax(() f-softmax(z, Mret), where
{ (v. - D (ullutct)
[-softmax Miet) = max
(15)
(EP(A)
The function x-softmax(-) is the Fenchel-Legendre transform of D' (ret, and the results in this section are therefore standard results from convex analysis, statements of which can be found in various forms in Hiriart-Urruty & Lemaréchal (2004); Mensch & Blondel (2018); Geist et al. (2019); Roulet et al. (2025).
In this section, we fix reference probability distribution Vref E P(A) such that for any E A, we have (a) Ve for some min.EA Vree(a) > V/rel O. For given x E RlAA,, we define
c (+) = f-softargmax(r, Vetl) = arg max (v, 2) D' (v(llseet) MEP(A)
(16)
The following result is a simplified version of (Roulet et al., 2025, Proposition 1). For the sake of completeness, we provide full proof.
Lemma B.1. Assume that is strictly convex on 1/urg) differentiable on (0,1/Vrg)) with lim (u) -00, for some Und 0. Let Viet be policy such that minaeA Mret(a) Wref- For any & E Rl- and E A, we have < (a). Moreover, for all BIAI there exists a unique Ph E Ie (x), where
Iyng = (maaxx()) (L(V/)))) maxx((a) f'))),
(17)
aeA
aeA
such that
va(a) Uset (a) (a) -wo)
(18)
Moreover, Par E T.. is the unique root of the equation
F(z,p): Σ ((a -
for μ E Lum(
(19)
16

---

Published as a conference paper at ICLR 2026
Proof. Under the stated assumption, the map f is strictly increasing (0, 1/Peel, hence injective; therefore it invertible onto its image. Moreover,
Dom (Lr'T-)) f ((0, 1/ (-o0, (L(L/vtt)
(20)
which is interval and the function [ is strictly increasing.
Fix E A. and (a,b) E Ax A. Recall from (16) the definition of the sart-f-argmax,
o = arg max (v,a) (V(()erret)
vEP(A)
This is a strictly concave optimization problem over the probability simplex P(A) so admits a unique maximizer. We now characterize the maximizer via the KKT conditions. Introduce multi- pliers E R for the equality constraint ECEA v/c) = 1, and for every с E A, X(c) E R+ for the non-negativity constraints vcc) 2 O. The Lagrangian reads
LV, p. (M())BEA))
Ev(c)
v()) x(c) D' (ullutet) + 1011-111
Σ Ev(o)
- - E (c))((c)
CEA
CEA
cEA
By the differentiabilityy of f, differentiating the Lagrangian with respect to v/aa) gives
àL
x(a) - 5 ((r(()) ( x(a)
v(aa
(21)
Ōv(a)
At the optimum (vf, Ma, (Ax(c)cCAA), the KKT conditions yield:
vc(() (c) 0,
Vc E A,
(22)
[df(c) (1(((e) (veelc)) Mr (x(c) 0,
x(c) 5'
V.EA.
(23)
Under the stated assumptions, lim f'(x) -oc. Hence, if vf 0 for some c, the station-
arity condition (23) cannot hold with finite multipliers. Therefore vd (c) > 0 for all e E A, which by (22) implies (c) 0. Thus, for each c AA the stationarity condition reduces to
mof (c)
x(c) 8'
= Mr
(24)
(ror(c)
Note also that (24) also implies that for all a E A, x(aa- - Mx. E Dom(f'), which implies, using (20) that m æz(a) (11//e)) I Ma. Together with (24), this shows (18). Note that Hh is root of (19), since using (18),
Meet (2(() -M)) Σ (a)== 1.
aEA
Because [f'-1 is strictly increasing on (-oo, ('(L for each E RIAI, the function + F(x, μ4) (see (19)) is strictly decreasing on (-o0, f' (1/2(ar)) Strict monotonicity gives the unique- ness Mu- Note finally that if μ > maxoeA (a) - (1), then s(a) < f(1). and since [f']-1 is strictly increasing, [f'] (x(a) p)) 1. showing that F(z, p) < 0. which concludes the proof.
L
Remark B.2 Let f: (0, be a strictly convex and differentiable on (0, r), Dom( = (0, and I' is strictly increasing and continuous on (0,t), r). Let limız->o f'(x: E [0000, +00) and 3 = lim fx(x) E (-00, too). Then o ((0,T)) = (a, 8), i.e., f (0, + (a, 3) is strictly increasing bijection (hence admits a continuous inverse [f] (a, 3) - (0, r)). Define the convex conjugate of f,
f(y))= sup (zy-f(a) =E(0,T)
(25)
The two following properties hold,
(i) For every y E (a, 3), , the supremum is aftained unique point x: (f))-
17

---

Published as a conference paper at ICLR 2026
(ii) Dom f() S [a, 3] (with the convention that infinite endpoint is excluded). Specifically,
Dom f*) (a, 5) = (a, and f") +00 for y & [a,, B). At an endpoint y = a (resp.
y 3), if finite, f() 1o f(()) (resp. lim (yx -- f())), so (a) (resp.
(3)) is finite iff the corresponding one-sided limit is finite.
On the open interval (ax, B), the function I" is differentiable and
E (a, B),
We retrieve the statement in Proposition 1 of Roulet al. (2025) by replacing [f by (f*Y. In most examples, there is no need to resort to the convex conjugate to compute the inverse. Lemma B.3. Assume, in addition Lemma I.I, that f is two-times continuously differentiable (0, Vng. Then, the function I + pa is continuously differentiable on IR (R) and for all a E A,
①
F (x. F(c, Ue = Ox(a) (x(aa)
(26)
Proof. The function (z) H)) + F(x, (u) is two-times continuously differentiable on the open set U == ((,,))
x x ZERA ER E [x)( c RlAi x R. Let zo E RIAI Since [f] 1 is strictly
increasing,
F(. ux) = E Unor(a) -"([f")- M2n)) > 0.
1
0p
aEA
Hence, we may apply the implicit function theorem, which shows that there exists open neigh- borhood Vzo and unique function x + Mr on Vz such that for all Va F(x, Ux) = 0 and (26) holds.
We now introduce some compact notations that will be used throughout the sequel. For any a E A. define the first three derivatives of evaluated at the probability ratio og (a)//re((())
2ff (a)
v (a)
v (a)
fa(a) =
(a(a)== = l"
fz" = f"
(27)
(a)o((a)
(ror(a))
Vrro((a)
In addition, we introduce the quantities
(a) aEA (a
ws
(28)
Importantly, f is strictly convex, its second derivative is strictly positive, making the preceding quantity well-defined. For any E A, we also define the following normalized weights
(a wf(() WT fa(()
(29)
Lemma B.4. Assume A (Vrg). Then the soft-f-argun vf is twice continuously differentiable with respect x. Moreover, for any E BlA, and (a, b) A?, we have
1 @v) = Is(a) wf(() wf(a)
W dx(b)
In addition, for any (a, b, E A3, the second derivative satisfies
(v) W! dz(b)ax(c) = (1(a)1c(a) f" (a)
f"" (b) f" (b)
wg(a) + 1 w/ (/ wb
faa
f" (a)
(a)
1o(a) wf(() (e(c)
+ +o(()) we(a)
M" (a)
f (a)
(b)
f (c)
- wg(aa w((() (((c)
(a)
(c)
(d)
-wf(a) - - w (c)
12 (d)
18

---

Published as a conference paper at ICLR 2026
Proof. Fix x E RlA and b,)) E A². Define
F( Σ
(or(aa]["T Ux)
aEA
First derivative.
Importantly, using Lemma B.1 we have that
F(x; pz)
Differentiating the previous identity with respect to r(b), yields
@F(;:
0pL
Σ (a) aEA
[I((a) 0x(bb)
0x(b)
(-(((--1(((a) uw))
where we used that the derivative of [s']1 is 1/ Next, using from Lemma B.1 that off (a) (a)[[a]-)(x(((() (x)) yields
OF(r; @x(b)
1 fa)
aps
Σ
(ree(a)
1s(a) ar(b)
aEA
where (a) is defined in (27). This implies
Opc @x(b)
w w/(()
(30)
where (b) defined (29). Now that we have computed the derivative of the normalization factor Mas we can compute the derivative of the policy. Starting from Lemma B.I, we have that
(a) tiee (a(( mx)
Differentiating the previous identity with respect to z(b), yields
ōvf(a) (a) @x(b) (a)
(x) = (a)
0jt
lo(a)
[1b(a) w/
=
(a)
where in the last identity, we used the expression of the derivative of μı given in (30). Finally, using the definition of W/ given in (28) gives
Ov! (a) 0x(b)
= Is(a) Uver(a) Uvet Uvet (b) 1
(31)
(a
fa(() (b( W
Second derivative that it holds that
From (31), we aim differentiate once with respect sr(c). First, note
(a)
p (a) dvf(a) 1c(a) frd (a)
Vrot(c) (ce 5 (a) f (a) ft (c)
(32)
dx(c) (a) @x(C)
(a)
w
aw!
(d) (d)
()er(c) (c)
Vrer(c) (d) (d)
(33)
dx(c)
deA (d)z dx(C)
(c)
WJ
1 (d) {" (c)
dEA
Now computing the second derivative of of gives
@uf(a) Is(a) Miee(a) (a)
(a) Ox(c) + (rer(a)Pre(())
1 (a)
(x(b)ax(c)
(a W! dx(c) aw!
(U (b) Vool(a)ure(
(f) W! dx(c) (a(a)f((b) (W!)2 dr(c)
Plugging in (32), and (33) in the preceding inequality yields
dvfa) 1,(a) (a)r(a) (x(())r(c)
pd (a)
(eer(c) (a) (a) (c) W
1.(a)
fa
F (a)
19

---

Published as a conference paper at ICLR 2026
Trer
P (a)
Prot(c) (a)
[a(a)
W
_ (a)
(a) (c) W
(ror(a)TToF(Q (b)
1
20 (b)
Urer(c) (b) 1
(b)
W!
f (b)
(b) f2 (c) W
(rer(a))rer(b)
1
(ier(c) (c)
Σ (d) (d)
(2)
(W
(e)
W
(d) (c)
dEA
which concludes the proof.
The following lemma links the gradients f-softmax and f-softargmax operators. Lemma B.S. Assume A (V(n)) For any x E [IAI, it holds that
0 [-softmax(x, Ueet)
@ f-softmax (2, Pret)]
f-softargmax(1, veet) and
<2w>
dr
Ox
2
Proof. For any x A and v E P(A), define
(z, = (v, - D' (v(lptee)
(34)
Fix b E A and note that
Th (2.1)) 0r(b)
v(b)
holds that f-softmax(x)) maX h (xx, v). As h is continuous in its two variables, P(AA)
a compact set, and for every x E TR. RR!,A,, the function h (x, :) admits a unique optimizer in ((A).
then by Danskin's theorem (Lemma I.5)
f-softmax(x, Vret)
Oh (x, v" (x)) v² vx(x) where 2² v*() arg max he (x,
(x)
dx
vEP(A)
Finally, using that
v (x) = f-softargmax(z, Mret)
establishes the first identity of the lemma. Using the fact that for any matrix A E Raxd, we have ||All2 I Σ Ei= laty], implies
02 f-softmax(x, Vrct)]
duf (a) (z)(b)
ΣΣ W w
$
Ox
READEA
REAbEA
where in the last equality, we used Lemma B.4. Finally, applying the triangle inequality establishes the second claim of the lemma.
B.2 SPECIFICATION THE DDIVERGGECCE GENERATORS OF TABLE 2
We now specify the particular forms that these quantities take under three choices of the function f: the KL divergence generator[/fwv
log u), the --siszár-Cresssi--Raal divergence generator for 0 < a < 1, and the Hellinger divergence generator
KL case (f u log u). Since f'(u) log + 1, (")) 1/u, and (f)-1()) exp(y 1), the soft-f operators specialize follows (with base measure Vsof P(A)):
Mror(a) exp(x(())
x (a) = ( - px) EdeA (boe(b) exp(x(b))
a a
where the normalizer
Pr. -1+ log
Vret (b) exp(x(b)))
PEA
20

---

Published as a conference paper at ICLR 2026
The associated softmax function is the log prrrptatiioon
x1-softmax(1r, Vret) = log
Σ aEA
(a) exp(ala)))
For the curvature quantities in (28) since f" L0 (a)) (a)
KL (a)
-1 Urer(a)
=
(ree(a)
(a)
we obtain
W #
(eet(a)
Σ
AL (a)=1 =1
(a)
a aEA
aEA
and the corresponding normalized weights are
(ree(a) {a(
w (a)
1/2 (a),
a A
Wh
Tsallis-o case (0 < a < 1), Let f(u) = 2a au + a - 1
so that
a(a - 1)
('(w) u ua-1-1 ("(u) u =
(V'-'(w) = [1 [1+(a= (ax 1)y] n-t
The s operators specialize (with base measure Vzef E P(A)) to
(a) = (a((a) p2)) (re((a) [1 (a ()((()) 11x) 1/(--1))
a E A,
where Ms is the unique normalizer satisfying the constraint
Σ (a) [1 + (ax - ()((a)) - kx) =1
aEd
with the domain condition 1 + (a - ()(a(a) (1x) 0 all
The associated softmax is rs-softmax Prot) = Mx
1 Σ Prof(a) [1 + (ax ()(((a) - [xm) 1=)]
+
a
aEd
For the curvature quantities in (29), set
(z(a) = 1/ (a)
= [1 + (a- 1)((()) - am
(a)
Since f" (uz(a)) = ux (a)=22 we have
WTS- (a) Σ (ror(a) [1+ (a- ()(x(a) - ur)] (2-a)(a-))) aEA (a)
aEd
and the corresponding normalized weights are, for a E A,
(arr(a) [1 + (a - 1) - [x))] (2- (2))((a1))))
1 Meer(a) W [a((a
w (a)
Ecen (r) [1 + (a - ()(x(c) - pz)) (2 (2-0)/(o-1)
Jensen-Shannon. Let f(u) (ulog(u) - -uu+1 1++1) log( + ). In this case, we have
1
2u
exp(2u)
f((u) 2
log
f"(u) 2u(u+1) (fT 2 exp((2))
uu+1
The JS-softargmax operator specialize (with base measure Vie E P(A)) to (x)(((((()) - pz)) Js (a) vrer(a) (o - mn) = Vice(a) 2 exp (2x(2) -2²))²
a E A
where 22 is the unique normalizer satisfying the constraint
(tar(a) ) ) 1z)
exp(2(x(a) p&))
Σ
1,
exp(2(x(a) -
aeA
21

---

Published as a conference paper at ICLR 2026
B.3 DERIVATIVES OF THE POLICY
Next, we exploit the expression of the derivatives of the soft-f-argmax derived in Lemma B.4 to compute the first and second derivatives of the policy. We begin by extending the notations defined in (27), (28), and (29) to encompass a dependence on the state. For any pair (8,0) a) E S x A, define the first three derivatives of f evaluated at the likelihood ratio Tt (als)) [Trr(
Tg (als)
folals) fols.)(a) =f
(35)
(als)
(als) = [ala,)(a)= f"
(36)
(Ter(als))
T6 (als)
5 (a|s) == )0(s,)(a) l"
(37)
Tref (a [a]s))
In addition, for every & E S we introduce the quantities
Wh(+) = W (((,))
Σ Tror (als)
and
()(s)
[als(
[a(a [[b(a|b)]
(38)
(als)
aEA
For every (s,a) E S x A, we define the normalized weights
Tre((als) (als)) = (s((s) f (als)
(39)
The following lemma provides bounds several key quantities that will appear in the appendix. Lemma B.6. Assume that, for some Tret > O, f and Tyet satisfy A (Tret) and P(Tzet), respectively. For any parameter A E RISI|AA,, it holds that
wa(als)
|woll 1 wy. ||8
Syr,
max ma (1) S sd, (x, Th (als)
max
S wg
#ES
Proof. The proof follows from the definition of the different quantities and A (Tret)
Using Lemma B.4, we get the following expression for the derivatives of the policy.
Corollary B.7. Assume that, for some Tref > 0, f and urot satisfy A (Tret) and P(Tret), respec- tively. Then the policy m/f is twice continuously differentiable with respect 0. Additionally, for all E (RIIIA and SS, there exists a unique pa(8) E R such that for any a E A, we have
(als)) Trer(als) (0(s,a) -Ho(s))
(40)
For any s E S. the 0 + po(s) continuously differentiable. For any s + 8. 0/00(s', ())))))))))
=
and
0po(s) w-(()s) [-((ss)
00(s.-)
Moreover, for any 0 E (RSIA AI, S, and (a, b) E A A. we have
1 (al(s)s) 1s(a) wf(als) wr(alls)((bbl)
(s( a0(s,))
In addition, for any (a, b, c) E A3, the second derivative satisfies
On (als)
f (als) (a)
4 (b]s)
w/ (als) + (b( (als) (b(ss) 8% (b|s)²
()(() 00(s, ())0(scc)
(a
f (als)
+ + + w/ (bls)) fM (a|s)
+1(a))
(cls) (cls
f (als)
f/ (als)
22

---

Published as a conference paper at ICLR 2026
fd (als) (a|s))
(bls)
fH (cls)
wo(als) (blss) w/(clo)
(b)s)
So (c]s)
16" (dls)
+ w wbbb)s) we(cls)
(dls)
5% (d|s)
dEA
Lemma B.8. Assume that, for some Tref > 0, f and Teat satisfy A (Tret) and P(Tzet), respectively. Then, holds that
0mg (als) 00(s,b)
0 (a|s) (als)
Σ
S 8ky (s)
00(s, b))((s.c)
(a.
(0.6,
Proof. Using the expression of the derivative of the policy provided Corollary B.7, we have by the triangle inequality
Dng (als) (0(s,b) b)
(o(ls) w6(bls) -
BEA
BEAA
where we used that
Σ
Io(a) - (bbb)s) 2(1 - (o(a)s))
(41)
BEA
Hence, we have
O (als) (8 b)
Σ
<2w
(0,
Fix E A. By using the expression of the second derivative of the policy provided in Corollary B.7 combined with the triangle inequality and (41), we get
θ (T 80(s, ())0
fld (als) (a(s) 4 (a(s)
1 (b)s)
w/(s(s))
Σ
w/ (b]s).
8 (b]s)
(b.0)EAR
bee
Next combining A (Tref) Jand (41), obtain
82 Jz (als)
S ())(()) wa(a)s)
(0 b)00()0000000 c)
Ab
Finally, summing over the actions concludes the proof.
B.4 SMOOTHNESS OF OBJECTIVE
Firstly, we recall that the regularized value satisfies the following fixed-point equation Geist et al. (2019):
(s) Σ T(als)r(s,)) - A (T((ss)) +
Σ
aEA
(xx
(42)
In order to prove the smoothness of the objective, we will prove that the all the second-order di- rectional derivatives are bounded. Denote 0., 0 + aru where R and RISIAA By Equation (42), for any E it holds that
w/ (s) c. M(a)r
(43)
where (a) is a matrix of S defined by
M(a)= (Id Po..) -
23

---

Published as a conference paper at ICLR 2026
and where rd., and Pa., are defined in Section 2. Taking the derivative of (43) with respect to yields
du e_ (s)
yc, M(a) Poo,
da M(a), +c. M() ore
da
da
Taking the derivative of the preceding equation with respect gives
82v' (s)
PP..
M(a) ooo. M(a)re.
P La
da² = 27 M(a)
+
M(a)re
da Pe.. M(a) da da
da 0rg +e,MM(M
8r, Pa
+ 2 (a)
(44)
In order to control the second-orde directional derivative of the regularised value function, we establish first several properties of the quantities that appear the preceding equality.
Lemma B.9. Assume that, for some Tref > 0, f and Tree satisfy A (Tret) and P (TTert), respectively. We have
OP
8
max (s)) ||l|22
aa
a==
Similarly, we have
Pe.
S Sky max ( (s)3 |||]
8a
1=000
Proof. Bounding the first-order directional derivative. The derivative with respect is
OPa
(als)
Σ
(8'1s,a))
da
da
8,5
aEA
a=0
Fix E S. Because T/. (als) depends only on 0(s, :), by the chain rule
Omg (a|s)
T.g (als) a0(s,))
@ (als) 00(s.))
Σ
u(s
|lu(s,
da
a=0
aeA
where in the last inequality we used CaauchySccwaal inequality and the fact that the L norm dominates the L2 norm. Now using Lemma B.8, we get that
O (als)
Σ
[|u(s, )l1 s 211u1l12 W/((s)
(0(s.))
aEA
Bounding the second-order directional derivative. Similarly, taking the second derivative with respect yields
8PP a Ja
Pay (als) Pa
Σ aEd
P(s'(s,))
N,S"
Fix E S. It holds that
8 mg_ (als)
PT (a g20(s,.)
02 v (a ss)
Σ AEA
Σ
u(s u(s,))
S Σ
|u(s, >l1
Ja
020(s
aeAA
A.A
where in the last inequality, we used the Cauchy-Schward inequality and the definition of the matrix operator norm. Additionally, using that for any matrix A Rdxd we have
|
ai.il
combined with Lemma B.8, we get that
8 n (als)
Σ
8 (lluss, -)1. max Ws((s)
aa
a
a=0
which concludes the proof.
24

---

Published as a conference paper at ICLR 2026
Lemma B.10. Assume that, for some 'ref > and niet satisfy A (Tref) and ((Ttet)) respectively. Then, the regularized reward satisfies
l| 11+ A
Amax D' (Tg) (+1s)]]
SSS
Additionally, have that
0.. Da
max (W + +Xx((s)) luull
and that
8r1 o
4422kg + A) w)((s) BANy (o(()] 1lull3
S max SES
Proof. The bound on ||r/l is immediate. Bounding the first derivative. holds that
0r
or((s)
(r)
Org (s) (0(s)))
da
Pu
max
00
u)
max
a0(s,-)
u(s, +))
max
|
Computing the derivative of (s) with respect to 0(s, b) yields
(s)
(al()
(als) (als) 00 b) (als(
00(s,)) ((s, a)
(0(
aEA
Plugging in the expression of the derivative of the policy of Corollary B.7 in the preceding identity yields
(5)(s) (bls(
[ror(bls) fb(b(s) (b(s)
(ale (Ter(s)))) r(s,a)
b(s
Σ
(0(,))) (bls))
S [[( w)((s)
Trer (s) (bl))) falals)
(45)
(s((s) aEA
((()s)
Taking the absolute value, applying the triangle inequality, and using that the rewards are bounded by 1 gives
(s) a0(s,)) b)
+ (
PE
Bounding the second derivative.
It holds that
02r
2 (s)
8 (s)
80 da
||0122
max SES
max #ES
da²
@0(s,
where in the last inequality, we used the Cauchy- inequality and the definition of the matrix operator norm.. We now compute the second derivative of (s). Starting from (45), we get
pr(((s)
Trot((ls)
St" (b|s)
(c)((c))) (b|s)
(b)
fd (bls) f (c|s) (s) r(s,b)
80(s,b)000 b))
(b)s)
f (bls)
(b)r(((s)
f (b]s)
(cles ) (b|s)
+ A
(b)
(b)s²
f (bls)
f (b|s) fd (cls) (s(()
-> [A(MAC) Feef (6|s)
(bor J (cls)
ln(e)
(b(s)
(b (57
W (s)
25

---

Published as a conference paper at ICLR 2026
Tee (a 8) (bls)
a(s,a)
Le(a) f (als)
Tret(c (a|s)
(a (6
(b))
(s(
S0 (a|s)
f0 (a|s) (cls) (s)
Tarr(a To a(s,a)
(b) 1 (b|s)
[rer(c)s)[ (b]s)
(b)))
(s)
(b(s)
f/ (bls) f0 (cls) ()())
aEA
Tree(ass a(s.a)
Tret(clss (c|s)
(r) (d (d]s)
((( (3)
(c(ss
(s) (dls)) f (c|s)
(bss)) f((b)s
Tror(c(s) (c(s)
Tee ff" (d|s)
(bla)) (3)
(c)33
(s( (dls) f (c|s) deA
oEA
(b(s) f8(bss)
le(a) S0" (als)
(rar(cls) (als)
1
f/(a)s)3f (bls) (s)
f8 (als)
fd (als) fl (cls) W)(()
Trer(als) (b())s)
f (b|s)
Trer(c)s)fF" (bls) 1
(b)
aEA [ (s)
Hd (b|s)
S (b|s) l (c|s) (s
(asr( 1 aEA (als) (+)
Trat (b[s)
res (b)a) ( (cls)
1x(c)
f (b(s)
(b))) (c(s) w%(())
Taking the absolute value, applying the triangle inequality, using that under A (Tret). for all æ E R+, we have (x) Ny,, and using that the rewards are bounded by 1 gives
0 (s)
ΣΣ
S 88n, Ws(() SAK (9(() (s)
08(s (),0(s.c)
A A
which concludes the proof.
Lemma B.11. Assume that, for some &eef > 0, f and Tret satisfy A (Tret) and P(Tret) respectively. Then, for any E IRIS [AI and u E RIS||AI
Polg() 002
(0)
S
Σ
(1 7)3 |lul12
where E (1,2,3), ( ( , (8). are defined as
10 = 4(kk, + A) |W// + SAKs Y
(0) 87 w/
kk (kg(1+ Amx S8S
D (TTd (mee
|//
+ +>|lx!l
(0) = 8,² / w/b |
(1 A max
D' (T(()
#ES
Proof. By construction, we get
82 S2
(s)
Pug (s)
u
4
002
da²
a=0
Using (44), we get that
(s)
P
0P,
<
27 M(0)
((0)
M(
da² a=0
da
da
a=0
a=
(A)
26

---

Published as a conference paper at ICLR 2026
Pe
0Pg 90
Or
+
7e
(()
(
+
2ye (
(
Fa
da a=
da
a=0
(B)
8
+
M
Pa
(D)
We now bound each of these terms separately
Bounding (A). First note that, for any vector I E IR and R, have
|M( S 1- |10|
(46)
This yields
OPo. Zx
OPo.
27² 73
@oo. 0a
|2
(A) s 2>
(()
(0)
M(O0r
11
acx
a==
a=0
a=
By using again (46), Lemma B.9, and Lemma B.10 get
8-2 max, (W/ (5))² |uul12
(A)
(1 À max D' (1
(1 7)3
sE8
Bounding (B). Using (46), Lemma B.9, and Lemma B.10 we get
po.
(B) S (1 7)2
Pa
8y
< - >) / max W (s)) 2 {1 + A max D' (Fea))
SES
Bounding (C). Similarly, using (46), Lemma B.9, and Lemma B.10 we get
CC v 7-
8y
max (W/ (8)) max (W(()) + (x)( |l012
SES
#ES
Bounding (D). Using (46), Lemma B.9, and Lemma B.10 we get
8rr iu
(D) < 1
1 7 max 4(2kg A) W)((s) + SAN, Yd(s) |lul|2
aa
a=0
The proof is completed by collecting these upper bounds.
Theorem B.12. Assume that, for some Tree > I and neee satisfy A and P ((Toft) respec- tively. Then for any 0, 0' E [R[S||A|, it holds that
( (p) (p)
< L 110 012
b/ (p) v6(c)
0 0)
00
where
Ly:= Swy (1w, 7)k,)
2r2 21 - 7) Imyds + +yr++ - 7)² ( + 2xy
+4X
(1 7)3
71
Proof. Fix any vector u E RIS|A| and E TRISiAAl_Usinn Lemma B.11, 11,1 it holds that
Rwg(s)
3 (0) Σ
x. (0)
u S
i=1 (1 - 7)' ||ul|2
002
27

---

Published as a conference paper at ICLR 2026
where for i E (1, L , (0), are defined
(0) 4 + A) |/ + SAKs x
(0) 8y w
[ D' (Tg (mer
[ 00
+ +2|lx(1
20
#E8
L (0) 8y²² /w (1 Amax D' D' (Tg (-[s)[[=ee((||s)
sES
Using Lemma B.6 combined with Lemma 1.1 concludes the proof.
C NON-UNIFORM LOJASIEWICZ INEQUALITY
Firstly, define respectively df and dg as the regularized Q-function and discounted state visitation associated with the policy of i.e.
a)) = r)(, +y Σ
P()((s,a)o((5))
(47)
s'ES
d)(() (1- Σ
? p'p
(48)
The goal of this section is to prove that the global objective satisfies non-uniform Lojasiewicz inequality, ie we aim to show the following theorem
Theorem C.1. Assume that, for some oe > and Tuet satisfy A y (Tret) and P(Trett respectively. Assume in addition that the initial distribution satisfy Ap. Then, it holds that
(p)
2 ()((0) (v((p) - -v)(o))
00
2
where
(0) X(1 P) 2
min (a,a)E8xA
(a(s)
w/
One of the main challenges in establishing such an inequality lies in connecting global information (the suboptimality gap) local information (the gradient norm). Recall from Section 2 that if
((s,a) a) =
Va E A.
then Th mn. This observation highlights that, under this parameterization and regularization, the key quantity is the closeness between and /\. Formally, we will show that both the sub- optimality gap and the gradient norm can be upper and lower bounded, respectively, by a quantity proportional to [[],,))]l,, where we define
(s) = (s, -)2 - 0(s.)) -
(s) LAP
(49)
(s) = (/((s))/AA 0(s,.), 1[A)
(50)
LAI
Note that cf is the projection of (s. ((s. onto the subspace orthogonal to 1[A]-
The proof proceeds in three steps:
1. Derive an explicit expression for the gradient of the objective and establish lower bound in terms of |C/ ||-
2. Upper bound the suboptimality gap by quantity directly related to ||c/
3. Combine these two bounds to identify the corresponding non-uniform PL. coefficient.
We now detail each step in turn.
28

---

Published as a conference paper at ICLR 2026
C.I LOWER BOUNDING THE NORM OF THE GRADIENT
Before deriving lower bound on the norm of the gradient, we start by deriving an expression for the latter.
Lemma C.2. Assume that, for some Tref > 0, f and Trof satisfy A (Trof) and P Frof) respectively.
For any 8 E S and b E A, we have
1 Ool(o) (s) (s) (0(b))) 1-7 wh((ls)
(6l6,,6) 20(s.))
Σ
wo((ass) ((lo,,a))0((;;))
aEA
Proof. Fix 8 E S and b A. Additionally fix any Using (42), have
(3(3) Σ (((3)))((3 - AD'(TT (+33) (-13)) +
Σ Σ
x3(a(3))((333a))))
REA
REAS'ES
Deriving the preceding recursion with respect 0(s, yields
(3)
(a (3)
r(5,a) - x/"
+7 Σ (()(8
(0(s,b) aEA
(8(sb) b)
Teaf (ale)
R'ES
Z(3)
05 (0(s)))
ΣΣ
((3333)
aEAF'ES
Using the definition of the regularized Q-function and writing the preceding recursion in vector form yields
(.(())
Z(-) + 7P (.)(.)
(0(
(0(s,b)
which implies
(.)
de((p) -ld-
(0(s,
50(s, b)
Next, using the definition of the discounted state visitation (48) and the regularized Q-function (47) implies
(p)(P)
3 (als')
To (alss)))
)
Σ dg'ss))
(6(55,a)~N0 -1
(51)
(0(
1-
a0(s.b)
(rer(als)
SEES
aEA
Org(als) Using that EaEA 00(s,b)
(Tl(a) a0((.b)
0 and that for # s', we have
yields
0u)(p)
1
(s(s)
(als)
(((s,a)-(( >/"
[a(a)s)
suo(s)
(0(
1
(0(s.b)
Troo is)
aEd
where ua(s) is defined in Corollary B.7 and satisfies for any A
8(s,a) - 8 Td((als) (ae((a
(4(())
Thus, we obtain
(06(0) = 1 00(s.b) b) ()(s) Σ aEA
0T (d((s,a) -
00(s,b)
Finally, plugging in the expression of the derivative of the policy derived in Corollary B.7 in the previous equality concludes the proof.
29

---

Published as a conference paper at ICLR 2026
Using the previous lemma, prove the following lower bound for the norm of the gradient.
Lemma C.3. Assume that, for some Tref > 0, and Toot satisfy A (Tyef) and P (yert) respectively.
Assume in addition that the initial distribution p satisfy Ap. We have
du du 00
2 X² min
min (s.))ExxA
(w)(als)?)
min m ( Σ [Ico(s)ll
SES
EES
Proof. It holds that
Or (p)
Ou (p)
00
=
00(s,
2 .SS
Fix 8 E Using Lemma C.2, we observe that
@w) (s) 00(s.)) = 1-7 (-ws() (gb(s.))) 20(s,))
dg(s)
((((s,))2((s,,)))
where for any vector a RIAI, we define H(u) diag(u) uu Thus, we get that
(p)(p)
1-
= dg(ss) (+ss( (s6(s 10 -
W (s) (0(s.))
(s)
H (16 (11s) (s 1/A 0(., (s) (g |1,
(using [u)]AA and (50))
2 (s) min w/ (a|s) (16o (where (s) is defined in (49) and using Lemma 1.4)
aEA
Finally, using (s) (1 ())(s) and A, concludes the proof.
C.2 BOUNDING THE SUBOPTIMALITY GAP
The first step is to connect the suboptimality gap to information localized at 8. This is achieved via the performance difference lemma for the regularized value function yields (see Lemma I.3)
(p) - Adp
Σ SES
(s)
Σ
(als)
(g()
(=
(s) A
(52)
aEA
(A(*))
Fix S. Using the definition of the regularized value functions and Q-functions combined with Equation (42), we have
(x) = (T1s) -AD (-1s)
This implies A(s) (s A2(s) As(ss where
A (s) (m(((ss)) - (
A2(s) (m) (Ter)
(53)
As(s) (m(((1s), 0s ))
Using (4) and (15), combined with (s) [softmax (s, A,, Fret (-18)) and the fact that A2(s) f-softmax(0(s,) :), (-s))) gives
A( (s) < f-softmax ( (s, 1//,, Tror(-1s) - Esoftmax (0(s, n (-r((- - As(s) (54)
Esoftmax(y/ (s, ) Tror( [softtmax (s)1(a))
(T (-Is), (s. )/A - 0(s,) -) (/(ss)1A))
where in the last equality we used that, for any x E IR |A| and E R,
f-xoftmax( llla Tree (+1s)) f-oftmma mertm (re((-ls)) +
30

---

Published as a conference paper at ICLR 2026
The structure of (A(s) closely resembles that of a first-order Taylor expansion as by Lemma B.5, we have that
2 (f (rnn)))) fssotarggmxx(((s.))) Trat (-18) (8(s.-)
(11s)
(55)
Lemma C.4. Assume A, (Teel. ). It holds that
v((p) v0(()) -
A
(1lW Σ (b)
sup BERISTIA
#ES
Proof. In this proof, we denote by 9s (x) = f-softmax(2) x. Teet (-er(1(s) (-1s)). Combining (52) and (54) yields
v.(p) - e2((() v 1-7 Σ d Bs)
(56)
aES
where we have defined
((s) = (s, (s. )/A) 110))-9.. 9. (0(s..) (s)1 (
1/2 0(s.-) (s){AAA)))
Next, by Lemma B.5, it holds that
dys (3))
(-1s)
Oz
Ia (
Standard one- one-dimensional Taylor theorem with Lagrange remainder shows that there exists E IR| which belongs to the segment between ((s,)) + Ko(s)la and d' (s, +)/ such that
B(s) } 8g (x))
(f).
Ox
Using the bound on the spectral norm of the Hessian of gs derived in Lemma B.5, we obtain
B(s) 7/2 Oz
8g (x)
(6 -
0 8'g (x)
[| wz((s [s)
Oz²
Finally, bounding the discounted state visitation measure (56) by and plugging in the preceding bound on Bss) concludes the proof.
The proof of Theorem C.1 follows immediately from Lemma C.3, Lemma C.4, Lemma B.6, and (7).
D MONOTONE IMPROVEMENT OPERATORS
A key challenge in analyzing stochastic policy gradient methods is that the Lojasiewicz inequality depends and degenerates whenever the probability of an action becomes small. The goal of this section is therefore show the existence of operator IMP/ with two crucial properties: (i) for any policy, applying this operator produces a new policy with higher objective value, and (ii) every policy generated by this operator assigns least a fixed minimum probability every action. The main idea is to build the improvement operator such that it slightly augments the smallest probability weights, such that for any state action pair (s, a) E S A the probability ratio π <aa|s) (ess Tree (a ss) stays above a certain threshold. We will show below that this procedure improves the global objec- tive while keeping the probabilities uniformly bounded away from when the threshold properly chosen. Let Tref 0 be such that A ((Ter) and P(Tret) hold. For any policy æ, state E S. T Kyel/ /2, we respectively define AT (s)), and a (s) as
(s) = {a E A. A.T(( ( (als) T/2}
( = arg max((T(a))) ( (a]s))
aed
31

---

Published as a conference paper at ICLR 2026
where the arg max is chosen random in the case of ties. Note that the definition of ensures that (s) does not belong to the set Ar (s) as
. (aas)
max a ref T (als)
21 1
Finally, we define the improvement operator follows:
Ur P(A))
P(A)s
(57)
Ur (T)),
where for every (s.a) E Sxx A,
(rer(als))
if if S (rer(a (T/
Ur (T)((ss))
x(als) Σ
(Tree(bls)) - (b(s)), if = m
(EAA((s)
x(aas):
otherwise.
The operator U, builds (al)s) by (statewise) raising each (s) (a ),, substract- ing the total added mass from the single action ( and leaving other actions unchanged. If (s) 0, for all E S, then IMP (m) Note that mass conservation is immediate from the definition and the fact that T Tref Non-negativity of Ut (m removed mass is
(s)[s) follows because the
Σ (E)
ST
Σ (re ST rEAT(a)
( Since (ammax())) Z Tref (mmax (m)ax)))]s)) 2 Tref, and t S Trof 22, we get that Uy (a)xx (5)[s) 2 T 7/2. This in particular shows that (TT(T)
policy. As by A ( -C, we consider [f']-1 f [ret]] + R.4 the inverse of f and define
have l f'(x)
TA min (15--) (I--' X(1 77)2
16 + &yyAyy
IFT (-1 (-4 f
2 1
Tref
(58)
The following lemma establishes the crucial improvement property when
T>- o (Tref) and P(Tret) respectively.
Lemma D.1. Assume that, for some Trel > O. f and Tret satisfy A Assume in addition that the initial distribution satisfies Ap. For any policy x. holds that
Uu (z) (p) v4 (4(
Additionally, for any policy n, we have that
Ur (T)(s)) 2 Tief
Proof. Set arbitrary policy m. For avoiding heavy notations, will, through this proof, denote
by A = A% We consider the case where there is & E S such that (s) * (alternatively Ur (T) = ग, which makes the previous incquality immediately valid). Define = Ur (T). The following applies
) (ale(a
a(als)
(p) xf(p) (s)
Σ
#(als)r(s,a) (ator(
BES
aEA
(aass) (alr)
Σ (s)
a(als)r(s,a) -ATse(al(s))
#ES
acA a(als)r(s,a) Amte(als))
A(als) Trat (alo)
Σ (s) (s))
(
Σ (s) Σ (F(als) (aals))((s.a)
+
#ES
aEA
32

---

Published as a conference paper at ICLR 2026
[
[(als) Tref (a
a Traf (ar
Σ #ES
(5)))
Σ
Trat (alr
aEA
(1II)
We now lower-bound each of the three terms separately.
Bounding (I). Using Lemma 1.2, we have
a(als)
(1) 2 - | d51l,
Σ
H(als)r(s,a) - (Tre((a|s)
max $ES
(ror(als))
.E
2 1 7 sES
7 sup
||+(-1)) T-115)]|
sup 3ES
+ A ( Tro(()s)))
27
TA max -
Σ (E)
(rlr(a
sup sup PEP(A) SES
1 1 AD (v|]
#ES
where in the last inequality we used that (because we increase the probability of the actions in A by Ta and remove the total added mass from the probability of ( (s))
sup
[|+(+|s) x-11s)11 .
2 max
Σ (EA
Tret(als)
j aa
#
Bounding (II). Using the triangle inequality yields
(II) 2 - sup [+|s)) (-1+))| 2 2 max
Σ 4g(3(s
(ret(als)
SES
sES
Bounding (III). All the state-action pairs on which the original π allocates the same probability then the policy मे are equal to 0 in (III) allowing to simplify this term
T(als)
(a|s)
IIII =
Teer (a|s)
f
Fret Free(a (als)
Tref (als)
#ES
T T(als))
T{(as))
(s)
(als)
f
Tree(a
(als)
SES
(E)
(s) + 0sd Tror (max (+)1s) [
π (a (s)(s)
[a (s)(s)
Tree a (8)[8)
-
Trrof (attax (8)]{)
#ES
Since f is convex, for all E [0; 1//ret f(u) f(v) 2 f'(v)(u - -v), we have
(III)
(T(als) - ((als))
(since म (re (als) Tx)
Tiee
SES
(s)
न a(a (s)(s)
+ (s) # 0)d (s) [T (T) (s)
Traf (a TT
(5){s)
#ES
Next, using that ih (a (8){s) Tref aax (s][s)
aa (8)(s) T>
T(amaax Trot /2
1 1
2
Tref aaa (s)[s)
Tred (ma (8){s)
2 2
combined with the monotonicity of f and the fact that π (a ( (s)(s) [
(s)(s) 0 yields
I 2 (s)
Σ
(T(als) - (())s)) (since (aals)/ Trer (cls) = TX)
SES
(EAT())
33

---

Published as a conference paper at ICLR 2026
π (mmaxx (s)(s)
+ Σ ((A)()) 2))d(()))) (m(
(a (5)[b)] l
Trre (1 (8) (8){s)
#ES
Additionally, since
S x (8))s)))) # m (8)88)
Σ
(T(al)) - - SA
Σ
Tree(als)
(EAA())
aEAF(ss)
implies
(IIT) 2
2 Σ (1)) #0)
Σ
mnor(als) Tad((TN)
SES
(EAA(s)
45 (s)
Σ Tret(als) TJ (1/2)
(eEAE(>)
Σ (5)) * #0)
Σ Troe(als) Taf (Tx) (Ta)
(EEA
where in the last inequality, used that ('( - (1/221) Hence, by using Ap, we can lower bound this term as follows
III
2 7 (1 (1-7)
min (ps)) max
Σ Tra((als) raf(Tx))
aEA)(s)
Collecting these lower bounds and using that
16 + 8y
('(T)) S X(1 - 22
concludes the proof.
Finally, we define the operator that maps each policy to one corresponding parameter
M II R SI1A1
by
x(a ((<(a] (o) (² 5( s(1 Free(a (s) - p ((quall))))
v(s,a) (59)
Finally, we define the improvement operator on the logitspace as
T- = M ott
The following lemma shows that A successfully recovers parameter that gives the policy and that T. improves the value of the objective when T>.
Lemma D.2. Assume that, for some Trel > 0, f and &eet satisfy A ((Teet) and P( respectively. Assume in addition that the initial distribution satisfies Ap. For any policy holds that
1 (m)
=
Additionally.fo for any 0 E [RSSAA and (s,a) ES x A. we have that
(0) 2 vf mt (0) 2 Tref TA
Proof. The proof follows immediately from a combination of equality (40) in Corollary B.7, (59), and Lemma D.I.
34

---

Published as a conference paper at ICLR 2026
E CONVERGENCE ANALYSIS OF STOCHASTIC POLICY GRADIENT
In this section, aim to derive under (Trat) and A, non-asymptotic convergence rates for F-P.. First, we establish a bound on the bias and variance of the REINFORCE estimator defined in (11).
E.1 BOUNDING THE BIAS AND VARIANCE OF THE STOCHASTIC ESTIMATOR
First, recall the expression of the stochastic estimator of the gradient
R-1H-1
Olog ot (ael (E) 7"t ""((s,, an)
(0)
00
t=
(60)
B H
log oo (ar (8)
B-1 H-1
7 DJ
Σ
Σ
F
-
B
00
b=0 1=
8=0
6=0
h=0
where: (50: H.
B-1 E (8 A.. and we recall that for any S, (s is vector
of size |S| |A| defined
के (bls)
(a(ss)
= (s')) L ()())
Σ
wo(aas))
Teast (b|s)
Tras (a
aEA
and where W/o Yo and w/ are defined in (38) and (39). Finally, define the expected gradient estimator as
g (())) = Ez-patajs
gz (0)
(61)
Before bounding the bias and the variance, we give explicit expression of the derivative of the log probability that appears in the expression of our stochastic gradient estimator. We also provide a bound on the derivative of the log probabilities and on the matrix F (s) for any state s E
Lemma E.1. Assume that, for some Tref 0, satisfy A (Tret). For any A RISIAAI, (s. S x A2, have
@ Olog T6 (als) (8) 00(s',0
(s(()) To (als)
Io(a) wo(als) [s(aa))(als) wolals) w/
Additionally, we have that
@ Olog m/ (als)
2 ( (als)
|| s 2
00
Proof. The proof follows from the log- derivaavvte trick and the expression of the derivative of the policy provided in Corollary B.7.
Next, establish REINFORCE formula for the gradient of the objective. Lemma E.2. Assume that, for some Tref 0. satisfy A b (Tret). It holds that
dw)(p)
Oog T (AA Sz) 7 An)
E
(0(s,))
(0(s,
1= 0=
oog T/
(Ap)Se) (0(s,)) b)
AI
D (NTÓ (-1S:)) atan (-
ビ=
(S.) w/(() w/ (bls) f'( nb(6bs)
(ols)) T6 (alss)
A
Σ
Tree Trer(a (s)
aeA
35

---

Published as a conference paper at ICLR 2026
Proof. Fix a parameter 8 E R|SIIAI, horizon T, and divergence generator f. For any truncated
trajectory& (st: 40) E (S A)", we define its probability as
T-1
(0; (f (o)
II
(s st- 1.-1..00 (
and the regularized return
(2) Σ (1()) #rat(ae((e))
T-1
o( T6 (aols)) )) Teed (aols))))))
(62)
To (aylst)
The finite-horizon objective is
(
R( =E(SXA)?
E
Fix (8.b) E S x A. Differentiating this unite-horizon objective gives
())
0vf(0:2) 2) b0(s)))
2R (
Σ
R (2)+
Σ
(0:
(63)
(0(
00 (s,
=E(SXA)T
=E(SXA)7
(A)
(B)
We now treat these two terms separately.
Term (A). Using the log-derivative trick and the fact that the only terms that depend on 0 in of (0; z) are the ones that depend the policy itself, obtain
(0; vf 2) a0(s,b)
T- Olog mh (a (t)
(64)
00(s,))
Plugging expressions (62) and (64) in (A) then gives
T-IT-1
llg Té (ar s2) y¹ (1(st, ar) - Tree(arlse) (i))
TH ( (re
(A) = Σ (0:22)
ΣΣ
00(s,b)
Tof (arls))))
=E(SXA))
1=0 2=
Now observe that for l t. the of the log- iog-gradient derivatives over (S A)T is 0. Therefore (A) reduces to
T-1
aog má (aelse) (r(st, - Trof(ar(s)) {( Thd (a((lss)) 00(s,b)
(A) = Σ (1
)) (65)
(a((()))) (ag
=E(SXA)²
1 O
Term (B).
Taking the derivative of (62), we have
OR 00(s,b)
T-1
Ond (arlst) (rer())) 00(s,b) TH (ar [s))
f( of (oclss)
(aels)) l' 1/ (arloe)
Teee (aelss))):)
(0(s,)) 6) To (arls))
t=
Summing over 2 E (S A)T and using the der-dvviva trick gives
(B)= = Σ (0:2) =E(SxA)T
T-1
log T/ (aelse)
(eel(s)) f( TH (atl(1)) To (anl(t))
] (66)
00(s,b)
(urlx)) Neat (a, (8))
Teet (a)lss))
Plugging the expressions (65) and (66) (63) gives
(J) = E
T-1
aog T (Ac(Se)
nd ((SS. Ad) - Teat (Ar(S)) f
(Ar(st)) =
)
ΣΣ
00(s,b)
(0(s,))
m/ (A,(S,)
(re(()
t=
0=
36

---

Published as a conference paper at ICLR 2026
log T (Ac(St)
Tre((Ac f me (ArlSt)
Te (Ac(Se)
(A,(S))))
+ AE
(0(s,b) b)
Teat (A,(Sr)
Tor (A, (A, (S:)
t=
The previous term can be rewritten as
(1)
alog TT (Ac)Se)
E 22mu
/r(SS:: Ar)
(0(b)
00(s,10 b)
Olog To (ArlSa)
Teaat (A.]S))
(A((S))
- -mu
7
00(s,b)
To (Ac(Se)
(Ae)S))
a log TT! (ArlSt) (0(s)))
T/ (Ar(S))
2f
Tref A AA
Next, apply the tower property by taking the conditional expectation with respect to G: o (So, Ao....,S, St) on the second expectation and using Lemma E.1 in the third expectation, gives
(0) 00(s.)) b)
llog ThÉ (Ar)Se) 7'r(S,, Ar)
E
00(s,b)
T
① Olog my (AelSe)
AE
D (T (115:)
00(s,b) b)
W w (b)..) o SA)
TH (A.(s)) Tref (A, (A,
- AE
(S.)
[I(A,)) - (A) f
Applying the tower property again by taking the conditional expectation with respect to Gr in the third expectation gives
0.4(0)
log Th (Ar)S))
E
r'r(S,, Ar)
80(s,))
a0(,,))
1=0
2=
2 log o/ Sc)
XE
D (Tr) (-15:)1 Toot (-15,)
@0(s,b)
TH (b|s:) Tref (b|S.)
(a (St)
- AE
/1. (S,) (S) f
Σ w/ (a))))
Tree S.))
aEA
Taking T + too and applying the dominated convergence theorem concludes the proof.
The following lemma establishes bound the variance and bias of the stochastic estimator.
Lemma E.3. Assume that, for some Fref > O, f satisfy A (Tret). There exists a constant 3, 2
such that, for any parameter 0 RIS|A we have
( 00
g (0)
S 3
where By is an upper bound on the bias defined as
By = 21 (H 1)
21 W/ [2 2Xd, + X(1 7)
where w is defined in A (Mret) and dy, and y are defined in (6).
Proof. Using the expression of the gradient truncated at H from (60) and (61), of the true gradient from Lemma E.2, and the triangle inequality, we have
O0)(o) 00
i log m (At Se) r(St. A1)
g (0)
E
00
t=
0=
37

---

Published as a conference paper at ICLR 2026
a log v/ (Ac]Se)
Σ
Ep"
D' (To (I (es())))
+ 2 t=
+
00
[=H t=
Next, applying Lemma E.1 combined with the triangle inequality yields
(p)
2 W/ w/ (Ac(Se)
g (0)
Ep
|r(Se, A011
00
my (Ar(Se)
2
H
E=0
00 t-1
2 W//r (Se) (Ac(Se) D' (T/f (-18:) (err)))))))
Xy Ep
To (Ac(Se)
t=
t=0
00
Ep
2 (s))
We define the following filtration, for 1 2 0,
G. = (So. An...., S:)
Next, applying the tower property of the conditional expectation by conditioning on Ge, bounding the reward and the divergence respectively by I, and max,es (A))EP(A) D' (M|] (-Is)) and using that w/ (-1s) E P(A) for any E S yields
(p)
g (0)
< 2
00
t= 0==
06 t-1 + 2X
00
W
D' ('(((ITred(((5))) + 2A 22
Σ
W/
sup 0o (EN))))P(A)
H=
t=H
Finally, using that
x 1)
H HT (1 (1-
8 Σ
rtt s 2 H H+1
Σ
Σt's
(1 71-
t=#
combined with Lemma B.6 completes the proof.
Lemma E.4. Assume that, for some Wref > 0. satisfy A b (Tret). For any 0 E RIS|IAA it holds that
of
1 60/0 [
Bz-1u101ea
B
where we have defined
12
of
[ + 12 2 + -1
(1 - 7)
and where wy. dj, and y are defined in y (Tret) and (6).
Proof. Firstly, define for & = (sh, an) MH E (S A)"
ue(()= d log T/ (ae)se)
H-1
n"t "r an)
00
H-14- 1-1
a Bog (aelst)) nn D (T//
11-
x
Σ "F/ (sw)
00
h=0
2=
h=0
Importantly, for a given 7 ~ [ denoting by 7 (7o. ...., ZB-1), it holds that
{0(
1
Σ
uz, (0),
and g¹ (0) = BE [u> (0))
B
b=
38

---

Published as a conference paper at ICLR 2026
Using that the variables (Zu..... ZB-1) are independent and identically distributed, get
E Ez~
g [e( - 8 (0)
2 2
7 uz, (0) g
B-1
(0)
1
B
||us(()) (0) g (0)
B
$ B B
||us (0)
(67)
where in the last inequality, we used that the second moment of a random variable dominates its variance. Next, using Jensen's inequality combined with the convexity of the square function, we have
H- Σ h= Ž=
alog TO (Ag(Se)
E Em)w(0)
[1
= 3
7f / /r(Sh, An)
00
H-1A-1 Olog T/ (Ar)Se)
+ 13A2Ro3ana
nn D (ISS (-1ah)
00
8=
H-1
-3X2 Bg
Σ
7 (Sn)
(Sa)
Applying the triangle inequality and the fact that the reward and the divergence are positive yields
H--1
Ō TO (ec
27
EIaU(O) [0))
S (3B
r(Sh: An)
00
A= 2mm
H-14-1
Olog To (Ap
27
+ 33
Σ 7b
D (m (I5W
09
H-1
27
+ +3X (3
Σx xt
|
h=
Combining Lemma E. and the fact that the reward is bounded between and gives 27
H H-1 h
h/2 A/2 W (5() w/ (AclSe)
Ex ||ug (0)11 < 3BIme(()
Σ
75d (Ar SS))
A= 2=
H-1A-1
W (St) (SE)
(/
D' ('(ulIzec((ss) 27
+3X Es)(())
Σ
2////2 7 1/2
sup (sI))SSP((A)
m/6 (Ac(Se))
1= 8=0
27 )
Σ 2 1/2 1/2 wwll |v6(lo)
+3X2 Esmr(0)
Next, applying the Cauchy-Schward Schwarz inequality gives
H--1
H-1 h
W5 )
B [11x((0]]]] < 3BI~v(0)
(ΣΣ h=0
ΣΣ
Σ A= P=
Th (Ae(ss)))
1-1k-1
(S0)2 w/ Wo Se)
31 337
Σ
4
sup (eW))SXP(A)
D (((()(
T/f (Ae)
h=0 t=D
H-1
H-1
)
+ 3. PE
Σ
47
Σ
1 1|
h=0
h=0
39

---

Published as a conference paper at ICLR 2026
We define the following filtration, for t 2 0,
G. (So, Au....,. St).
Next, applying the tower property of the conditional expectation by conditioning 9., and using that w/ (-1s) E ((A) for any E S yields
wg(ass) Ta(a)s)
11-1
2
Es-((()
[10x
S 12 W
max (S.A)
Σ N=U
*
*(h+1)
w (a(a)))
#1-1
2
+ +12x²
W//
(D((u])TTo((((1)))
Σ
7
max (x.
sup (AN))SSP((A)
To (a|s)
h=0
H-1
2
+ 12X
1/
Σ 7h h=0
Next using
H-1
H-1
H-1 () (1 71-
Σ
ΣT'
Σ
? r (1 7]-
1
and plugging in the obtained bound in (67), combined with Lemma B.6 concludes the proof.
E.2 SAMPLE COMPLEXITY OF STOCHASTIC f-PG
We now derive convergence rates for f-PG. First, we define the following quantity, which will be the plyaak-Lojasiewiez constant of our function the optimization space, where policies guaranteed not to be too ill-conditioned, i.e., all their entries are larger than the TA defined in (58),
A(1 - P)pmmn
re
min ZELTA.
("(x)-
(68)
w
As we will prove in this subsection, this quantity represents lower bound of the non-uniform Eojasiewiez coefficient along the trajectory. In the following lemma, we give simpler lower bound of b provided that À is not too large.
Lemma E.5. Assume that, for some neet > 0, and Nee satisfy A (TTett and P(Tzet) respectively. Assume in addition that the initial distribution satisfies A, and that satisfies
4
4
X
min
7)2 pmin
[G
|
Toat
In this case, it holds that
X(1 P) S
Teet ( (- (- X(1 - 2
16 16 8:2d,
w/
Additionally X A < 1/d,, then holds that
X(1 7) S
2 (- (-x(1 X(1 7
e > w/
Reet
First note that the first condition on À implies that TA < tt. with iy defined in ( and thus
Proof.
min
40

---

Published as a conference paper at ICLR 2026
Additionally, the second and third conditions on À guarantee that the minimum of Tx in (58) is attained in the first term, that
a 107-1 (- 1-''''
16 1 ByAd
A(1 7)
Finally, we recall that the convex conjugate of the divergence generator defined in (25) satisfies, for any y E (-o0, f
((*) 1"(M"--
Thus, obtain that (T( (f+) ((*)"( 16t88Ads ya which concludes the proof.
In the following, we define the filtration adapted to the iterates of fPG as
Ft σ Zx E (O,..,,
The following theorem gives convergence rates of f-PG.
Theorem E.6. Assume that, for some Trel > 0. f and Teef satisfy A , (Trel) and ((T respectively. Assume addition that the initial distribution p satisfies Ap. Fix S I/2L5. a given temperature X, and consider the iterates (0.) of the algorithm fPG.. It holds almost surely that
inf ju (0.) 2 K 120
(69)
Additionally, for any 2 0 have that
Emon 6,3
v (p) E of (p)] S (1- - (o))) - (p) +
+
Buy
Proof. Recall that for any E [T]. we have that
0₂ Tra (0:)
Hence, by Lemma D.2, for any t [T] it holds that
m 2 TATrel
Combining the previous inequality with the expression of the coefficient μy provided in Theo- rem C.I proves the first statement of the lemma. Next, using Theorem B.12 gives
1/L,, 2
c. (p) 2 v/, (p) + 2n (p), 82, (0:)
52 (0))
Next, taking the conditional expectation with respect to F, and adding and subtracting Vel, (p) in the dot product gives
E
1 0sts (p)
2 v0)( 2n
Vog. [0]
2 (0), (0.) Vuyy
(K1)
T
82. (0 || F
(70)
E
2
(K2)
We now bound each of these terms separately.
Bounding K,. Using the Cauchy-Schward Schwyrz inequality, yields
2n (v (p), g/ (0.) - Vv'd (e)) 2 22 Vod (p) | 18 (0.) (0000)0vvrgll -vr
--2.1 1/2 Verh (p) 17 1/3
where in the last inequality we used Lemma E.3. Next, using Young's 's inequality gives
2 (VV (0). (0.)) Vor, (0)) z - Vig. ( - 1133
(71)
41

---

Published as a conference paper at ICLR 2026
Bounding Kg.
Using the convexity of the square function with Jensen's inequality gives
2
(o)+ 1| (0.) - Ze(ee) + zz - (0) + Vuy, (p)
E
2
(1)
Fi
EE
Fr
2
$ 33, + Velg (p) 2 +
303
(72)
B
where we used Lemma E.3 and Lemma E.4. Plugging in the bounds (71) on K and (72) on K₂ in (70) gives
E J (0) 2 v0), Vol, (p)
|=) /
1-+++-++ 31
2 83
3/
Vud. (0)
31f² 3 I.
2B
Taking the expectation with respect to all the stochasticity, multiplying both sides by -1, and adding v. (p) gives
(p) E Vo.., [0)] S (p( E (rbe (p)
7
37L1
Vug. (o)l
2
(1 37 L1
3rd L
+
87 +
2
2B
Next using Theorem C.I combined with (69) yields
v((o) - E Vo (0)) s (1- nu, (1- 3//1
)) (v((o) - (B(6))-B(od,())) (v)((o)))
2
+ 2n + 311
2B
where we used /2 S 1. Finally, using that 1) S 1/2L, to bound 1 - , 2 and unrolling the recursion concludes the proof.
Next, we provide the sample complexity of f-P for solving the f-regularized objective.
Corollary E.7. Assume that, for some Tref 0, and weef satisfy A (Tret) and P ((Tee) respec- lively. Assume in addition that the initial distribution p satisfies Apr Fix any e 0 and > 0. Setting
H (1 - 7)2
4
+ log
1
CL (1 - 7) 42242 + x2 12(1-1)333 27(1-))8811
216w3
(73)
1-
and
1 eBu
17 S min
(74)
2L, 1807
and
4 T> - max
1807 2L5, BBu
3(vl(p) w/ (o))
log
(75)
4
guarantees that
v - E Ju (p) sc.
Proof. As 17 S 1/2L,, then by using Theorem E.6, it holds that
onu
6,83
(p E 1 (p)] s 21- (vf()))((((()))) v/2 (p)) +
+
Bu
P
(0)
(V)
(W)
Next, we aim to show that under our conditions on T, H, and 17, each of these terms smaller than c/3.
42

---

Published as a conference paper at ICLR 2026
Bounding V. We start with the term V, which gives condition the step-size. In particular, setting
cBp "/ S
180
guarantees that V e/3, which, together with v S f/(, gives the condition (74).
Bounding U. In order to ensure that U is smaller then e/3, we need 'I' to satisfy
e
T
log
(f(( (p)
which, combined with the inequality log(1 +x) S for > -1, ensures that U is smaller than e/3, and the condition (75) follows from (74).
Bounding W. Using Lemma E.3 and Jensen's inequality, it holds that
W 4- HH 1) R (1 7) w [12 + 12 + 3 - ~)
Next, we remark that for any a have ay 2H (H 1)2 S e/3 for
H 2 1
1 1 log (())
4
3a
Taking
Ey ( 12 12X +31 ))3} gives W e/3, provided that (73)
holds.
E.3 GUARANTHES ON THE NON-REGULARIZED PROBLEM
A key criterion for evaluating the quality of reinforcement learning algorithm is its sample effi- ciency in solving the original, unregularized objective. To this end, we recall a result from Geist al. (2019), which establishes connection between regularized and unregularized value functions, and further characterizes the performance of the optimal f-regularized policy when evaluated in the original unregularized MDP.
Lemma E.8 (Proposition 3 and Theorem 2 of Geist et al. (2019)). For any policy n, and state E S
holds that
Xd₃
- (s) S 1-7
Additionally, denote by o! the optimal regularized policy. For any state 8 E S, It holds that
(s) Va! - Adg
The following theorem gives the convergence rate for the non-regularised problem.
Theorem E.9. Assume that, for some nref > and neet satisfy A (Tref) and P(Tret) respectively. Assume in addition that the initial distribution satisfies A Fix < 1/2L5, a given lemperature X, and consider the iterates (0)2 of the algorithm fPG.. For any > 0 have that
(p)) + ono?
6,32
2Xd,
I.. (v)(p) - vo (p)) S (1 - (n. - w/, (p))
+
+
By
4
1 1-
Proof. The proof holds from Theorem E.6 and Lemma E.8.
Finally, we give the sample complexity of f-PG to solve the unregularised problem.
43

---

Published as a conference paper at ICLR 2026
Corollary E.10. Assume that, for some Reel 0. f and Eeet satisfy A (TTet) and P P(Tre!) respec- rively. Assume in addition that the initial distribution satisfies Ap. Consider any constant > such that
of S min
de (g''v
Fix any (1-7)-1 ><> 0 such that
16
4
4
and set X (1 (1-7)e
Pmii
min (IP(5)) |r()
|
4 cs
(76)
Define
96
2
E(c) = log ((v)(p) - (o))
d(c)= d(c)= Lec((1 7)3 Pmin
(77)
e
Additionally, define the three following constants which depend only on f as
16w of cj
3456w
c/2) = , (nwy + (1 - 7})g)
ci
(78)
570s
Setting
297
H 2 (1 7)2 +
log ed(c) 7)
1 y-y
pmn Fzel
and
(1- 2d(()(1 - Bp (2)
min Truf
S min
(79)
cl
and
160|))60 E(E)
c/22)
T2 ed(c)( - 72 roat 2 max
(80)
(1-7)3) (1 - 76 Bp Trot
guarantees that
U. (p) - E [vo, (p)] sc.
Proof. First, note that the conditions (76) on and À guarantee that
A 5 (1 - 7 min 4 (f((()) [((
(
Thus, using Lemma E.5, and the fact that e < - 7)- we have that
X(1 70p-pin S7
-24
nee (
w/
X(1 - 7)? Penin
Plugging in the expression of X from (76) yields the following simplified expression
H EC, (1 - Pmin
-96
4e(1 p Fraf d(e) (81)
Tref (
Aw7
cc)(117)9 Pmin
cf
where d(e) and c(U) defined respectively in (77) and (78), Additionally, combining Lemma E.3,
Lemma E.4 and Theorem B.12 and the expression of À yields
24
69 " H
13w, (w) + (1 (1-11 7))
of 5 (1- 11-7
B1
(1 71- Ws
L,
71
(82)
where used that under y (TTr)), have wy 2 1. Using Theorem E.9 and the fact that A s (1 / we have that
6n07
6,3
(p) - E [voo (p) < (1- 2/0)) vf (p)) +
B
2
(U)
(V*)
(W*)
Next, we aim to show that under our conditions on T, H, and 17, each of these terms smaller than c/6.
44

---

Published as a conference paper at ICLR 2026
Bounding V (82), it holds that
We start with the term V which gives condition the step-size. Using (81) and
144m
576m
V (1 1 7))
(1 (1 EcI 2
96
"0)(1->)' Puii
c)
Ged(e) - 76 Bp F
where of is defined in (78). In particular, setting
n de)(e) - Bp Fref
c
guarantees that V S c/6, which together with the condition 1/(2L,), gives the condition (79).
Bounding U*. In order ensure that U smaller then e/6, we need T to satisfy
log - n/, /4) log
6 (c.( - v/ (p)
which combined with the inequality log(1 x) S for x -1, ensures that V < e/6 and the condition (80) follows from (79).
Bounding W*. Using (82), holds that
367 2H (H + 1)2
w/
41 (1 (1-7)²
Next, using that for any 0, have ar 2 (H 1)² I c/6 for
1
4 6a
H
1-7 max
log
shows that under our condition on H, we have W
e/6.
F APPLICATION TO COMMON /DIVERGENSES
In this section, apply the results of the preceding section to two commonly used f-divergences, which are Kullback-Leibler and a-T'salis.
F.1 BALLBACK-LEIBLAE
Lemma F.1. Assume that, for some Trof f(u) = u log(u) satisfies A (Teet) with
Frof satisfy P( The function defined by
Wy wy=1,
Ky =1, L =11.
Additionally, under the condition that
A (1-7) Pmiu (log(2 Pmmi
(83)
Tzol (2/Tret) +)
we have
8
3 4 log( Tret)
S =1 1, d2 (og((Teet)), Yf 11+111 2 (og((Tee))))) T, (1 - 233
+ 4A
(1 - 7)
By = 27 H (H +1
12
[2+ + 4X| [Teet
07 5 (1 71
[] + X2 (2 + 5 log Tree [²]]
(1 --7
32 16 log (ret)) log(Fret))
1 2 X11 - 7i Frel exp
/9
X(1 - 7)? Pmin
45

---

Published as a conference paper at ICLR 2026
Proof. Firstly, note that have
f(u) log(u) s'(w) - log(u) +1, ("(u)= (")(w) -u-
Satisfying A (Tret) Observe that (i) and (ii) are immediately valid from the expression above of the derivatives of Moreover, we have
1/u =1,
=1
["(u)2
showing that (1i1) of y (Tror) is satisfied with wy = Ki = 1. Finally, as f" strictly decreasing function on + then (in) is valid with if 1.
Bounding the constants. Next, we bound sequentially each the constants that appear in the statement of the lemma. For any S and v E P(A), we have that
(alo(
Σ aEA
Σ aEA
vaa==
v(a)
[alt]
Thus using (7), have that (f 1. It holds that
v(a)
dy =
max (S aEA
Σ
Trer(a|s)f(
[als(als)
v(a)
max (S.))ESP((A)
Σ aEA
v(a) logí
Tref (a
v(a) log(u(a)) v(a) log(
(sp))ESP((A)
which gives dj < - -llg( Next, we have
(rer(als)
lr v(a)
Σ
Ys =
max (A.))ESP((A)
aEA f"
v(a)
Tret(als)
Frce(als]
v(a)
v(a) log
+1
(s)))
(alt(a
11-log(Tro)
+ max NEP(A)
Σ
v(a) log(v(a))
+1+ (ro((Tee)):
where in the last inequality, we used that the entropy of a distribution on AA is bounded by log(1AA) and the fact that Tref S A). Next, using Theorem 1.12 and the bounds above, we have
L, Swy (rw/ (1 x)xx) +4 272 2 7)wy (wyds + x1 7)² [wy + 2x
- 7)3
(1 7)
3 + 4| log((Tor)
41
(1 7)3
(1 - 7)
Using Lemma E.3 gives
"H + +1)
B, (1 71- Wy [2 + 2Ad, X(1 - A(1--)yy]5
[2+ X 44/ log TTet
(1-
Using Lemma E.4 gives
(1 7 (w) + X x
12
<
12
[1+ X2 5 (Tee [))]
(1 - 7)
Next, note that (83), guarantees that we have
4
X <
21 Pinin
min
(''اi)' [((C]] [ Frat
46

---

Published as a conference paper at ICLR 2026
Thus, using Lemma E.5, we have
1(1 - 7)
16 8y
2
Trof ((*)""
1 w9
A(1 - 7)
32 + 16 log(
)
2 A(1 p) re
exp
/9
X(1 - ?)2
where in the last equality, we used that the convex conjugate of f(u) (ug(u) is (*) = exp(U 1) and that exp(-2) 2 1/9.
In the next two corollaries, we apply Corollary E.7 and Corollary E.10 get more explicitly the sample complexity of ʃ-PG with entropy regularization.
Corollary F.2. Assume that, for some 1/4 2 Tref > 0, Reef satisfy P(Trer). Assume in addition that
the initial distribution p satisfies Ap. Fix any (1 - --)) 2 E > O, > 0 and B such that
216 log Trot)] exp 48) log(s,ot)
4
M[1-71"PPmat
A min (11 7) Punin (llggo//gggggg /Tet) + +1:11), B s
eA(1 2 Pinsa
Setting
29160 (ret )²
52] (ogg(Trrt))
H 2 1
log <\(1 - 766 Priin ntze
(84)
X(1 7)3 Prain
and
<BA(1 8)% Pmmin Fret exp
48| (ogg(Teet)]
" S 15552 log (oor)) 1
A(1 p)pimnn
and
559872 (ree)
96] log (reat)
T xBa((1 7) pr Trof"
exp
A(1 - -1)2--7ap P
guarantees that
SE. (p) - E [16 SE.
where f is the Kullback- Leibler divergence generator. Thus, the sample complexity of f fPG to learn an e-solution of the entropy regularized problem is
1 3& (1 7)9 Phin Fzet"
Tre))
(lg((Tre)) X(1 11)727//innn
TBH RJ
exp
Proof. To prove this corollary, we show that the assumptions of Corollary E.7 hold. First, A (Ttet) holds as consequence of Lemma F.1. Then, we show that the condition (73) in Corollary E.7 holds,
216 (1-)
[ 4 dx2dz + X² - >)²y} ):
that is S [T- +
-
log
To this end, we remark
that
4
1
216w?
log
[4 + 4X²d x² 7
(1 -
21
1 1-7
EH/
7)4
5
4
+
1
log
216
[4+ 22 log ( (mTret)
(1 7)2
(1, 7)
4
1
1944 4 + (2 + 6 log log((Teer)') (2)
32 + 16 log(Tret)
<
+
log
(1 7)2
eX(1 p Tret 2
A(1 73 Pmin
1
29160 log (Tee))
52 log Teet)l
<
log
+ X(1 - 7)3 Prnin $ H
cA(1 - 7)55))pp)) 22 Trot
47

---

Published as a conference paper at ICLR 2026
where used the lower bound Ey provided in Lemma F.1 in the second inequality, as well as < and Tref I 1/4 in the last two inequalities. Furthermore, Lemma F.1 with I gives
36 log (Tee))
f - (1 7)3
(85)
96| log((ret))
Tref))
of <
(86)
(1 1 7)
A(1 7) Traf
48 log (eeet
3
exp
(87)
X(1
7)² 2
Using these three bounds on smoothness, variance and
coefficients, we obtain
eBu, min ( 1 2 180;
(1 713
eB\(1 - P
PinnnTef exp
X(1 ((1)))) Prnin
48| log((Tec) (Teer)]
2 min
72 log( (ret)]
15552 log (ret)
eB - 7)// min Tref
48] log Trotf)
exp X(1 ?)? Pmiia
(88)
15552 log( Tref)
where the last identity, we used the fact that < (1 - -) and that
216 log (rg(t)
48) log (Taat)
B
exp
x1(1 "Tet 2
X(1 7)2mmin
This shows that our condition 7) guarantees that the one set in Corollary E.7 is satisfied. Finally using (88) and (87), we have
4
1807 BBu
4 15552 log(Tret) exp
48 log( (Tret)
max
2L
11
6 e.BA(1 7) p2 Tref
A(1 32 P
559872 log (Tret)
96] log( (Tret))
exp
AB - 76 Piiin Tret"
X(1 7)2mmnn
Pinin
which concludes the proof.
Corollary F.3. Assume that, for some Trel E (0, 1/4], Feet satisfy P ((Tret). Assume in addition that the initial distribution satisfies A, and fux f to be the Kullback-Leibler divergence generaton, i.e. f(u) u log(u). Fix any (0, (1 7) such that
16
(1-7)-
(1 7/3 Punin (log (2 TTet) + and set X
(89)
12 log (Teeet)
Additionally set any B such that
1
376| log (Teet)] c(1 7) Pmnin
B < 2 7)3 pmin Teet
exp
(90)
Setting
1 log
llog(
586] log (Feet)] + c(1 - -7) Punin
H 1 1-7
c(1 p) Tree?
and
21 7) Bp min nrot
-576 log (Teet) Prain
< 93312 log( Tree
2 exp c(1
(91)
and
644972544| log (ree)) 1
1152 log Tret)]
((vl( - ( (p)
T> e1 - (11)))8pp p1 Tre!
exp
log
(92)
e(1 7) Pmin
48

---

Published as a conference paper at ICLR 2026
guarantees that
v.(p) Eve, (p)) sc.
Thus, the sample complexity of [-PG, where I is the Kullback-Leibler divergence generalor, to learn an e-solution of the non-regularized problem is
1log [rog(
(ret) <((1 -1)0 7))
TBH
exp
(2 22 Frof
Proof. This result follows from Corollary E.10, whose assumptions we check now. First, note that (89) implies that
16 min
4
4
<
(1 7) Pmin
[(((s))]
[
ree
Additionally, we can rewrite the constants from Corollary E.10 using Lemma F.I, which gives
cf < 48 (og())
cf²) S 48,
(3)
10368 log Rrot)
576 log( Fref)
(93)
d(c) 2 exp
/9.
c(1 - 7)3 3 Pmin
where C cf cf and d(e) are defined in (78) and (77). Next, the condition on H in Corol- lary E.10 holds since
297
4
1
+
log ed(c)(
(1 7)2
I 1-
7)% Fraf
4
1
128304| log (Treef
576 log (Tret)
5
+
1- log
(1 7)2
<(1 7)0 7) Piiin Trof
c(1 7) Pmin
loog (Tret)]
586 log( (Teff) )
$ log
S H
c(1 - 7) P Tret
c(1 - Paunn
Pauin
where in the second to last inequality, used that nze 1 1/4 and that log( (28804)) s 6. Using (93), we have
(1 71-7)3 (dd(e(( - B7) Tref
min
c(2)
c/,3)
(1 71-3)3 <² - 76 Bp p Reef
-576 log (Trof)
2 min
exp
48
93312 log Tref) )
c(1 7) Pmuin
2( - 7) Bp Tref
-576] log( (TeTt))
93312 log( Tref)]
exp
(<(1 7)3 Panin
(94)
where in the last inequality, we used the condition on B introduced in (90). Hence our condition on the siep-size ensures that the one assumed in Corollary E. is satisfied. Next, using (93) and (94) yields
16C ed(e)(1 7) p Puinn Tre!
c (1 (1-7)3 ed(e) 7 B Tree
max
16C
93312 log Tret)]
576 log( Tret))
ed(c)(1- - p22 Fref
e0 - 8 BP PminnTred Tret
exp
6(1 7) Punia
6912| log(Tred (E(e)
93312 log( )
1152 (Trer)))))
e(1 11--) >)2 pm Trof"
22 (11-7) 76 B Trof
exp
c(1 7)3 Pmin
644972544| log Teat)
1152 log Tref
G(v.(() - v/d (p))
exp
log
c3 -
p Tral
Priinreef
4B
<(1 73 Pmin
which proves that under condition T' the assumed by Corollary E.10 is satisfied.
n
49

---

Published as a conference paper at ICLR 2026
F.2 a-TSALLIS
Lemma F.4. Assume that, for some Trof E (0, 1/4], Jref satisfy P(Tror). For any a E (0;1), the functiin So defined by
fa(u) = 4² au + +a-1
a(a 1)
satisfies A (TTee), with
Wy Tyel
Kj = 2nrel a-1 4/=1
Additionally, under the condition that
4
1-a
X
(95)
(1 - 117)2mmin
(Trat/ (Frot/2)n00 2)
have
4 4|log( (Tee
T 16TTee
Tref
2n
log xiet
S ===1 d, 5
yy S 4/ (ogg(
180A
(1 - 7)
a² 7)3
81 = HH +1)
[lgg(Tret)]
12 30-3
16A2
+ 66
of S
log(Tree Tret (2)
(1 7)2
a²
(1 7)
a
16 + 32> log( (eett (Foet)//a 1l/a2
1-2a
4 2 A(1 - 7 20 Punin Tref
expa
X(1 7) Pmnin
Proof. Fix any a E 1) and set / = Sa. Firstly, note that we have
f(u) u au + a-
f'(u) a-
(''(w) = (a 22)
ala -
Satisfying (Fret) Observe that (i) and (ii) are immediately valid from the expression above of the derivatives of Moreover, we have
[F'(() f"(2)²
(w) = =
= la - -2 1aa
a-1 showing that (1ii) of A (Tret), is satisfied with wy = Tref T and Ki = 2T a-1, Finally,as f" is strictly decreasing function R, then (iv) is valid with iy 1. Next, we bound sequentially each the constants that appear in the statement of the lemma.
Bounding Cy. For any E and P(A), using Jensen's inequality we have that
(als(als)
v(a)
2-a
v(a) Tref (a (s)
2-a
Trer(als)
Trer(als)
via)
(als)
AEA
Frot(a|3)
aEA
aEA
Thus using (7), we have that C = 1.
Bounding dy. For any state s E S and E P(A), it holds that
D' (v(((Tre(((())) = ala -
Σ
Tree (als) [( v(a) (res) )
Tre (als)) - (1-
v(a)
aeA
Next, for y E)0; Teet
define the function py: : (a; 1] - R which satisfies
Py(3) = 88 - -By - (1 B) (3) = log(v) -1
It holds that
n (1 a)
Py(a) (1)
sup
p)(()) <
a a BE(a.1]
50

---

Published as a conference paper at ICLR 2026
Applying the previous inequality with y = v(aa/ yields
D' (v]( Tree (als)
- a aEA
1
Σ
1 +
v(a) + v(a)
log( M(a)
) //2aa)/maaclal)22
(als) (al(( Trer(a|s)
log u(a))
(rer(als)) ( v((a)
( (((a)/m
Σ v(a) aEA
aEA
1 + max log( v(a) a aEA
p(a)
Tror(a|s) 8) )
(u(a)/=mr(alss +
Troef Troe(aa (als)
where in the last equality, used that if x 2 1, then log(x) 2 0. Next using that log(v(a)) yields
(' (11)))
Σ aEA
v(aa log(Tror(als)) + max xE[0:1]
[log())<>** +
1
1
2
log (eet
max [og((>) =e[0:1]
a
where in the last inequality, we used that the entropy of probability measure on A is bounded by e-1// /a combined with max(1, log((AA)) S
log |- Next using that max log(<>) & e
log [Tret) gives
log log Tref
log Tref
I
a²
a²
Thus, it holds that
4 llg((Teo))
dy v
a²
Bounding yy. For any policy E P(A) and s E S, we have
Σ aaA
v(a) Traf (als)
v(a)
1
vla)zaa
v(a)
-1
f"
Tzot s)
(a
(ret(a)s)
aEA
Next, define the function By for y e]0;
which satisfies
Tzaf
(3) y
g,((3) = logg)))
holds that
(a) - 9, (1)
< sup
[34( < |log(y) 1ns1 + [log(yy 1921
8E(a.1]
Hence, applying the previous inequality with y = v(a)/ (Te(((a)))))) gives
Tref (a|s)
v(a)
v(a)
Trot (Tr((a(s) (a|s)
REA
[ref(a|s))
x1a)22
log v(a)
Troor (alo) (s)s) ) Lm(o) + log Tals)) )
(mrerlals) v(a)
1-a7
Teof {
TToe (a s)
a
v(a)
1-a
v(a)
Lu(o)Smar(al)) + Σ v(a) log x(a (s) (alr()
v(a) log Ttet(als)
(e)
aeA
aeA
v(a)
Σ v(a) AEA
log
+ 2 log (re!!)
Tree (a|s)
where in the last inequality, we used for the first term that for any u E R, ul.51 < 1 that the entropy of probability distribution on A is bounded by log() the fact that Reef < 1/\AA, Using the same argument again to bound the first term gives
ys < 4 log Teof
51

---

Published as a conference paper at ICLR 2026
Bounding Ly.
Next, using Theorem B.12 and the bound on the constants previously computed,
we have
1 Swy (ywy +1
+ - yau (x + +y1++ - 7)² [/] + 2x
+41
(1 (1-7)3
(1 (1-7)3
16 a-1
Fref 20 2110g (T
(1 (1-1) (1-7)3 1801
a2 11-7)
where in the last inequality, used that Trof < 1/4.
Bounding By. Using Lemma E.3 gives
Bj 2, "H (1+1)
4H +1)
[re(
71- wy [2+ 2 X(1 - >)vs] S
1 + 62
(1 7)2
a
Bounding oyp
Using Lemma E.4 gives
12
12 30-3
16X2 a1
o7 (1 (1-7)*
(w) + X2 W + x2(1 <
1+
log Trof (2)
7)
7)
Bounding , Next, note that as fa an increasing function then Sa Fa S (1(22) S
(4)) (1) 0. Thus, we have ((r) (1/2) I Ifa (Tref/ (2). This proves that (95),
guarantees that
X 4
min ( [F() [ TTot)
(1 7)2 Pmin
Thus, using Lemma E.5, we have
X(1 P) S7
16 87 (-x1- 7) Puni
4
w/ nee "
(96)
Next, recall from proposition of Roulet al. (2025) that
fx (1 (a 1)x) -
for x S - a
a
Thus, we have
(f:)(z) (1 (a 1)z) o- (x)
where we have originally defined cxpa in Section Finally, it holds that (z)) = exp, (x)2
Thus,
16 + 32> log( Tret)//a²
4-20
H 2 X(1 - 7 2-2a Pmin Trel expa
A(1 - 7))
In the next two corollaries, we apply Corollary E.7 and Corollary E. to get more explicitly the sample complexity of fPG with entropy regularization.
Corollary F.S. Assume that, for some 1/4 2 Tref 0, Reef satisfy P P(Trer). Assume in addition that
the initial distribution p satisfies Ap. Fix any (1 7)-1 2 0. E (0, X 0. and B such that
48 (TTee) ]| max(A, 20
4
expa
(1-"1117 (1-7)*
< min
B
(1 7 Pmin
(T a 12
Trof 2 22 p
52

---

Published as a conference paper at ICLR 2026
Setting
(28152 -4--4 loog Tret 1 EAa 7) Pmin Troi
196 log( Tret
H 2 1 log
max(a? .1)2) +
max (a
A)
da 7))
(97)
and
cBX(1 7) a Tref 5- 5-50 Piiin rrot"
48 log (Tett)
1-20 max(A, (axx)) az)
3672 log Tye max ( 2)2
expa
Pmi Aaa2(1
and
14688 log Tref ) max((a aa, ,22,,) A)2
48 log Tref
4a
T2
XBB(1 7) -7 Prain Frat
expa
Aa
Pmin
max(A, a²)
guarantees that
v((()) - E (0
( Sc.
where f = fa the a-Csiszár Cressie Reesiee-Read divergence generator. Thus, the sample complexity of fPG to learn e-solution of the a-Tsallis regularized problem is
|log (rof) ) max(a -6 3)
- (-xa² (~xaP1177) -2) max(), a²)
(ogg(Trot)
4a-8
TBH ~2
expa
eB3 Rrel -Ta Pini Tref
Proof. To prove this corollary, will show that under the conditions of this corollary, the assump- tions of Theorem E.6 holds. Firstly, note that by using Lemma F.4, the assumption A (Tret Jholds. Secondly, using Lemma F.4 note that
4
1
216w7
+
log
[4 d2 + +22 7)
(1 -
7
1
(
- -7)1
216 2a-2
log |log(Fret))?
+
log
+ 321
(1 7/2
f41,
7)2
864 1a-1
[1
32X
log (rat /22)
S (1
+
log
7)2
eA(1 - 7)
prin Trat
1
16 32>>\1 log (Te()
4-20
log
expx
2a - Ptnin
where in the last inequality, we used the lower bound on [4, provided in Lemma F.4. Next using the definition of exp,, (see Section 2) and the fact that À < we have
4
216w? EH4, (1 7)4 [4+ 4x2d3 + 22 - (1
+
log
(1 - 7)
1 y
4
28152
4a-4 (log(TeetTr max(a? (2)
log
(1 ?}²
1 ?
-7)5 Fret
4- 2a 1 log 1+ (1+ a))
48 log(
max(a² 2)
1 - a y
Aaa((1 - Puni
(28152MTef 40-4 log( (ret))
196| log (ret\
log
max(a? x)2 + Aa (1 73 Pmin
max(a? A)
EAaa pp Tret?
where in the last inequality, we used that for x 2 O. we have log(1 + x) S x. This shows that our condition on H guarantees that the one set in Theorem E.9 is satisfied. Next, using again Lemma F.4 observe that
L = 196 Tea 2a 20-2 log (log(Tra) Fret)
204 30- loog Tma)
max(a? (,A)
of 5
max(a? x)2 (98)
a= 7
aA 7)
53

---

Published as a conference paper at ICLR 2026
48| log Tref)
4-2a
y 2 X(1 ?re
2-20 20
Pinin Trel
exp,
max(X, a2)
(99)
(1
Pmii
Hence, we have that
BBy
min
2 1
[a² 7) min(( -2, 2,,-1)
2 min
392 2a log( (og((Tr) TTcf)
<BX(1 7) ") Tref 5a Pinnn re
48) log (Trof) max max(), (N,
1122
3672 log((Too) max(o? ; X)2
expa
Aa2(1 - Pmin
(100)
eBA(1 - 7 " Tz p Pinin Tref
5a
48) log (ree) max max(A, a22) >'a2(1 P
4-2a
expa
(101)
3672 log (ref ) max X)2
where in the last identity, we used the fact that < (1 - -7)- and that
B
1 exPa
(-Xa-(1 - Pmiin
48| (rog)Tot)]
max (A, (2,
2a-4
Krot
P
This shows that our condition 7) guarantees that the in Theorem E.9 satisfied. Finally using (101) and (99), we have
4
1807 eBu,
max
2T.
4
3672 log( Log((Tre Tret) 12 max max(a?,A1))
48| log( Tret)
2a-4
max a²)
,, <BX(1 7)0 Fert 5-50 p Tret
expa
Xa - 7) Pmnin
14688 log Tret) max(a??2))
48| log (oggt)
4a-8
max(),
X²eB(1 7) Thof 7- 7a pa phin rto
expa
Aa
Pmin
which concludes the proof.
Corollary F.6. Assume that, for some Traf E (0, (0.1/4), Neet satisfy P(Tret). Assume in addition that the initial distribution p satisfies A, and fix to be the a-Csiszdr-Creet Cressie-Read divergence generator, t.e.
f(u) fa(u) n au +a-1
a(a - 1)
Fix any E (0, - -. such that
16
(1 - 7)a²
E << (1 7)3 Pmin
(Tref 2) 22a and set X
(102)
16) log TTat
Additionally set any B such that
384| log kras) ea² - 11773/pmmm)
2a-4
B 2a pp p Trei
expa
(103)
Setting
1 199008Tref 4a-2 log(Tred) krer)]
1540| log( (ree)) ea 7) Pmin
H > 1-7
log
caa(1 7)8 p2 Tret²
and
2a2 - 7) pp² min vret
(- 384
(__84) log (Tea²(1 ea - -3)
4-2a
- 13824T log TTee
exp...
(104)
54

---

Published as a conference paper at ICLR 2026
and
12a Tyel 7a-7 1oog (Tet 12 TZ a1 -)8 Pmin Too
384| log (xeet)
4a-3
6(v)(p) - v/2 (p))
oxPa
ca2 [1 -7)² Pmin
Pmin
log
(105)
guarantees that
- -E(
Thus, the sample complexity f-G., where f is thea Saaaa-Csszdrr-resstte Read divergence generator, to learn an e-solution of the non-regularized problem is
Trof 7a-T7 1000-1000mmmmm (og(
(-
(-384 384/ log((ret))
4a-8
TBH =
cta 7) "Pppiin Pinin Tref
exPa
ca? ( Punin
Proof. To prove this corollary, we will show that under the conditions of this corollary, the assump- tions of Theorem E.9 holds. Firstly, note that (102) implies that
16
min (
4
1 (F()))
4
)
== (1 (1- cj
<< (1 111-))ppm Pmin
(1(()))
(
with = a²/ /4/ log( Trat)) l. Additionally, observe using Lemma F.4 that we have
64 20 (ra)l
13824 5a-5
log (Tet
cg s
cf S 16 20-2
c
a²
a²
d(e) expa (- 384 (Teet)
4-20
(106)
caa(1 7))
where 04, c/a)
c and d(e) are defined (78) and (77). Next, observe that
29
4
1
log ed(e)
(1 7)2
1-
7) Piin Tref
4
1
190088Tzef 4a 40-21 (Teet)
log
(1 ?)2
1-7
'ca(11 - p) Tret
4 2a
expo (- ca?211 700
3844|lgg(TTed)
+ 1
log
< 4
1
199008Teel 1a-22 log(Tree)
1536| log (re!!
log
7
ca2 70 rrot"
ca? -7)"*mmi Pmii
where in the last inequality, we used that log(1 + < x for > -1. This shows that our condition on H implies the one assumed in Theorem E.9. Using (106), we have
min (1 (1-7)3 dd(()(( - 7) Bp
Bpinn Tre!
C(2)
c(3)
(1 21
2a²(1 - 7) B Bp
min Tret
384| log( (ref))
4-2a
min
96T 2a-2
13824Tyee 5a-5 log Tref
expa
eaa - 7)3 Pmin
2a 7) Bp2 Trot
384| log (TTTE))
13824TTre 5a 5a-5 log( log(Tror)
expa.
Tea2(( 7) 3mmin
(107)
where in the last inequality, we used the condition on B introduced in (103). Hence our condition on the step-size ensures that the one assumed in Theorem E.9 is satisfied. Next, using (106) and (107) yields
E(E)
ci(2)
c(3)
ed(e)(1 p2 Frof
max
2d(e)(1 76 Bp Froe (1-
55

---

Published as a conference paper at ICLR 2026
e(0) ed(c) 7)2 Tze!
13824 ny 33-3 log(Tree)
Tret )
(-
384| log((ret)
(Tret)
2a-4
2a - 7) BP TuinTeed Tref
oxpa
ea (1 7) Punin
1024 2a-2 21 (ret)) (((c)
13824 3am-5 log (TTet)
384/ (T(et)
4
eXPa
ca?(11 pmin Tzef
ca (1 7) Bp Tref
ca² 7) Piniu
Pmii
12a TTef 7a-7 Tret)
384| (og(()rrr)
6(r2(p) - v (p))
e - 7) Piii Frof" B
exPr
<cx2(1 - 7) Pminn
log
6
which proves that under our condition on ' the one assumed by Theorem E.9 is satisfied.
Corollary E.7. Assume the same condition of Corollary F.6. For any (1 (1-7)-1
and
(0, 1), denote respectively by T(e, at), a)),a), and He,, a)) the thresholds set in Corollary F6 on T, B, and H. to learn an c-solution of the unregularized problem. Addtionnaly, denote by of (c)
the minimizer
( It holds that
a' (()) = 11
2 log(1/c) +o (Tog(1/))
Additionally.or < <e-11, it holds that
log( Tooff 11 22 7)30 p Frot"
(v. v/ (0))
=Ō
log
Proof. We first provide an equivalent of the a that optimises the sample complexity provided in Corollary F.6 and then bound the sample complexity obtained by using this
Finding the best a. Firstly, note that using Corollary F.6, we have
S(e, log (T(e, ((E,))))((a))H((....))
12 mre Ta 7a-7 log( Trat)
=log
eaaa - 78 pinin Tret
+ 4a
384 log( (eg(Trot)]
log
1 (1 - a) (0))
a 1
(cc2(1 7)3 Pinin
((rl(p) (o))
+ log
log
1
190008 4a-2 (rot)
1540 log (Teet))
+ log
log
1 1-
ca2 - 7)0 p Fzet²
ea
7) Pmii
Firstly, observe that for any function k(() which does converge different value from have
S(e, 1/ lllog(1/)) <1
lim c-0
A(E))(E))
which establishes that at (c) + 0. This allows, to rewrite S(e, a) as
8 4a log
1
S(c, a)) = log c4a0
+ ((),c)
a
ca?
where vi(a, <) is defined as
12 neol 7a-7 log (TaE))
((a, e) log
p Troe
4a 8
384/ log (Tret))
)) -log
log 1+ (1 (1)
1
(c 7) 3prin
6(v!(p) (p))
(p))
+ =log
log
56

---

Published as a conference paper at ICLR 2026
ca.²
(19008 4a-2 (rr())
1540) log(
+ log 1-7 log
+ (1 7)4 Pmin
Ea² 72)
Pmin Tref"
Importantly, observe that <)(a, <) is dominated by log(1/c) when (a, - 0 and that
@vb(a,e) =0
da
a log' c0)
Computing the derivative of this function with respect to yields
-6 + (1 a)2
log
{ +
log
14
Ovh(e, a) +
da
a
(1 - a)2
a
a
1
a
da
(108)
-2
+ 4 log ( +o
(109)
a
looo(( log((a))
As
AS(e, a)
Oa
la=at(c)
Then this implies that
a²(e) = 2 log(1/c) +o
(Tog(T/))
Next, we provide a bound on the sample complexity given by this a (e).
Computing the sample complexity. Firstly, note that for < 1/2 and e < 1, we have
T(e, (()
12 _2'1 Tret 7a-7 log Traf 1
384| Log(Trer))
4a-8
6(v1(p) - v/ (p))
6 - 2p) Tref
exPa
ca P
log
c
Tref 7a-7 1a-?| (log(Tret))
Log((Tre))
(8-40)/(1o0)
(6(v)(p) - - -%)(oo)) (p))
log
(110)
c - 12 Phnin Tret*
ca (1))->))2ppp) Prain
11 Next, note that for < 11, we have 2log(1/e] 1/2. Thus, using that 1/(1 a)) < 1 20 yield
(8- (8-1a)/11a)
8 4a
= exp
log
S exp
(C+88) log Ea?
S 2
Ea
1 -1-a
Ea?
Plugging in the previous bound in (110) concludes the proof.
G DISCUSSION ON UNREGULARIZED POLICY GRADIENT WITH F-SOFTARGMAX PARAMETERIZATION
In this section, show that it is possible to derive Non-Uniform Lojasiewicz inequalities the unregularized objective Up(p) := (p) under f-SoftArgmax Parameterization the bandit set-
ting. We expect the analysis to extend the RL setting using similar arguments to those of Mei et al. (2020b;a); Liu et al. (2025).
Theorem G.1. Consider the bandit case, i.e. = Assume that, for some kvel > f and weef satisfy A (Tret) and P(Tret) respectively. We also assume that the function 1/ f is convex and that the initial distribution satisfies Ap. Then, it holds that
wo(a")²
U.(p) - <v)(p)
[Voo(p)122
S5 ve(p) Ux (p) f"
(x( U.
where (z(p)= max (z(p).
TEP(A)S
57

---

Published as a conference paper at ICLR 2026
Proof. Subsequently, drop the dependency on the state for more clarity. Using Lemma C.2 (with y and [S] 1), for any a E AA, we have
@ve(p) (a) (r(a) Σ (b)r(())) (0(a)
Denote by at any optimal action, and r(aa). We have
Σ -w/(0) 2
Voo(0))12 = E wg(()) (((a) - - w 2 wgb(t))
Using that A(a) = -r(ar(a) 2 and also
vb(a)
1
(a)
W :
Tref (a)
W (m( Tre((a)
("( (b) Trea (b))
bE
yields
Σ (((() w
(())TTTo
f"1(T) (b) /oor
PEA
Let's introduce a distribution 7(a) = ( (a) (1)//////)) 1/EbAA
(bb)Teet (b)). then we have
W (b)
W/ EETT [Ac)] Benry
BEA
Next, we use that a map x + (z) is convex, and thus was have
Bowy 1/( (c) (c) (To 2 1/5" (Eonn [T((c)/TTo((())
ECEA (C)) EceAdh ((c)Trer(C)
= 1/1"
Overall, we have
Σ (b)A()) 2 w/6 (EeEA ((c)Tee(())) ld BEA
Eeca Mlo)s(()) Eoen (Leentoomeet (iotteer())
Finally, using that w $ Sy concludes the proof.
Similarly, Mei al. (2020b); Liu al. (2024; 2025), this łojasiewicz inequality depends on the probability of the optimal action, which is very restrictive. Although extending the analysis of Mei et al. (2020b); Liu et al. (2024: 2025) in the deterministic setting is possible, addressing the stochastic setting for this type of Lojasiewicz inequality appears very challenging, This justifies adding a regularizer to the objective to ensure better inequalities, and on which the minimal coefficient can be lower bounded on the trajectory by leveraging proper projection operator.
H LINKS WITH MIRROR DESCENT
We stress that our proposed method is fundamentally different from mirror descent. Let us define For the functions f that we consider, & is Leg- endre on the positive orthant and separable across states (Bubeck al., 2015). this case, the f-regularized value function v.f (p) can be optimized directly in the policy space via the Lazy Mir- ror Descent algorithm (or dual averaging; see Nesterov (2009); Xiao (2009); Juditsky et al. (2023)) with & mirror map. Denoting by m. the policy at step and म, by the unnormalized policy at step t, the lazy MD updates reads:
mapping (TT) = E.es D' (=(-Is)]]
( = V + V ( TH+1 = arg min By (T Tel))
(111)
*ell
58

---

Published as a conference paper at ICLR 2026
(V π - r²)) is the corresponding Bregman divergence. Since & is separable over states, the Bregman projection can be written wise 1++1(+]s) f-softargmax ()(*++)((s, +), (-er(-
where II = P(A))8) is policy space and (=(((/=)) = (T))
((x')
By denoting 0, = v (T). one obtains updates that resemble those of (10) (after the removal of 7), with one important difference: the gradient in (111) is taken with respect to the policy whereas in (10) is computed w.r.t the "dual" parameter (in the MD terminology). Even more important, the update (111) can be expressed as, by the chain rule
0+t 0: + 1j
Om 88
Vo.)((8.),
0=0+
which have an additional preconditioning term given by the inverse of the policy Jacobian.
A crucial feature of (10) is that it performs gradient ascent in the "dual" space directly. This algorithm can be extended in the non-tabular setting directly, by parameterizing the function (s, a), allowing extensions to deep RL. This is in contrast with Lazy-MD methods (Nesterov, 2009; Xiao, 2009; Juditsky et al., 2023), due to preconditioning, which cannot be expressed as direct parameter- space gradient steps. This remark has several important implications, which we leave for future work.
I TECHNICAL LEMMAS
Lemma 1.1 (Lemma 1.2.3 in Nesterov (2004)). Let f IRd + R. be twice continuously differen- tiable. Suppose there exists L 2 0 such that for all x E B. and v E IRd,
a [()) S L||o|[?.
Then f has an L-Lipschitz continuous gradient (i.e., is L-smooth); in particular,
[V vx(x)] S Dlly- ==]] f1ly-
and
f(v) 2 f(x) (Vf(z))) x) 1/2 lI - x||
for all x, E Rd. Lemma I.2. Consider any two policies ne 1,2. holds that
1 1 ||, 1-
7 sup || (-1s) 12(11s)11 SES
Proof. Let start from the definition of flow conservation constraints for the discounted state visi- tation (Puterman, 1994), for i E 2}, we have
tt (s) = (1 - 7)p(s) + Σ Pa (s)
Then, we have
Σ 2 (s)
dz
(s)
Σ Σ ()) P(sss (()s
(8) (s',0))
P(s a') (2) (a'lss (5)
,'aa'
Pssls' (')m d (6') -5 d))(
.a'
< suu (-1s) (-1ss) + Σ 1d (s') d. (8')
SES
which concludes the proof.
Lemma 1.3 (Performance Difference Lemma), holds that
(p( (p) - Σ ded (s)
Σ
- (x))(()()))((((((()))))))))))()) (re((s))))))(((s)) - us)
59

---

Published as a conference paper at ICLR 2026
10
-10
-30
-30
(a) Softmax / Entropy Regularization
(b) Softmax /
(c) 0. I-Taaliis SoftArgmax Entropy Regularization
(d) 0. I-Txallis SoftArgmax /
0.1-Tsallis Regularization
0.1-alpha Tsallis Regularization
Figure 3: Regularized value landscapes for a one-state, two-action MDP (rewards 0, 1) for different coupling between parameterizations and regularizations.
Proof. Fix 0 RISI and any state E S. It holds that (s - u (s) Σ [=((a))o(((s.0)-
Σ ==((al))6((s,a) aEA
aEA
AD (f (+)(())))
Σ (a|ss) (6((,,))))(($.0)) + Σ (als)) v6 (a(s)) (b(),a)
aEA
AD' (m! (-1s) +
7 Σ (als) Σ P(s'ss.a) (1'))') - (/6( + Σ
(T(ss) To (als)) (8)))))
AEA
aEA
AD' (TT (-1s) [|]][ [+s(()))s) + AD ( (-1s)[]=Te((-Is))
where the last equality, we used the definition of the regularized Q-function (2). Expanding the recursion yields
(s) (s) 1
Edj(s)
Σ - 96 (5()5,a)
S'ES
LEEA
Σ (s')
AD (1()5))(( AD (D (
7 EES
Σ (5')
SES
LEEA
Teet (to())) -
(s's
Σ
SES
LAA
which concludes the proof.
Lemma I.4 (Lemma 23 of Mei al. (2020b) Lef क E P(A). Denote H(T) diig((T) π: For any vector E IRA
H(TT) (x- (x,, 1daid
IAI 111) 1
|
(x, 1|A1)
> min aEA
1
A
Lemma 1.5 (Danskin 1966). Let 7 C R be compact and let Φ TR 2 - TR. be continuous. Define
f(x) max Ó(I 2), zE2
Zo(x) arg max arg (12, 2). ZEZ
Assume that for each fixed E Z, the map + 0(x, is differentiable. If Zo(z) = =z} and Φ(I, ) differentiable at x, then is differentiable at with
0f(x) dr
0Φ(x,2 2) dr
60

---

Published as a conference paper at ICLR 2026
10.0
Average return
Average return
Average roturn
6.0
4.0
5.0
0.0
0.0
5000
10000 15000 20000
5000 10000 15000 20000
0
5000 10000 15000 20000
Iteration
Iteration t
Iteration
(a) &Chain,
(b) NChain, Size
(c) KChain. Size
1.0
PGG, 0.1
Average return
Averag return
IPG, 0.3
fGG, a 0.5
0.5
0.5
PPG, = 0.7
IPG, a 0.9
Softmax Entropy
0.0
0.0
log barrier
Escort-transtem
5000 10000 15000 20000 Iteration
5000 10000 15000 20000 Iteration
Hadamard
(d) Deepses, Size 10
(e) Deepses, Size 15
Figure 4: Average return function of training iterations on NChain (top row: sizes 10, 15, 20) and DeepSea (bottom row: sizes 10, 15). For f-PG, we report the best configuration for each divergence parameter or; for all other methods, we report best-performing configuration over their respective hyperparameters. Curves show the mean performance over 15 independent seeds, with shaded regions indicating one standard deviation.
J EXPERIMENTS
J.1 UNCOUPLING THE PARAMETERIZATION THE REGULARIZATION
Figure compares the regularized value landscapes induced by different couplings between policy parameterizations and regularizers. Both Softmax / Entropy Regularization (Figure 3a) and Softmax / 0.1-Tsallis Regularization (Figure 3b) produce highly ill ill-conditioned objectives, characterized by wide flat plateaus separated by extremely sharp ridges. These geometries create large regions with vanishing gradients together with nearly singular directions, which are known to slow down and destabilize policy-gradient methods. Switching to the Tsallis SoftArgmax parameterization already improves the situation: under Entropy Regularization (Figure 3c), the flat directions are reduced and the basin around the optimum becomes more pronounced. However, the most favorable geometry is obtained when Tsallis SoftArgmax is coupled with Tsallis regularization (Figure 3d). In this matched Tsallss-Tsallis regime, the landscape becomes smooth, strongly curved, and well- conditioned, with a single broad basin leading to the optimum and no spurious flat regions or steep barriers. This alignment between the geometry induced by the parameterization and that of the regularizer yields an almost quadratic objective in logits, explaining why the Tsallis-Tsallis coupling provides the best convergence behavior.
J.2 TABULAR EXPERIMENTS
We evaluate the empirical performance of f-PG equipped with a-Tsallis regularization, with the goal of assessing how our coupled lines summarized in Table 2. All methods are evaluated on the unregularized return objective, and report learning curves as function of training iterations. For each value of the Tsallis parameter a, we tune both the temperature parameter À and the step-size 17 over the grid
framework compares to the base-
À E 310-3, 10-2 10-1 1.0).
7 E 410-4, 1 10-3).
For the baseline methods, analogously select the best-performing configuration over their respec- tive hyperparameter grids. All curves are averaged over 15 independent random seeds, and shaded regions indicate one standard deviation.
61

---

Published as a conference paper at ICLR 2026
NChain and DeepSea. We consider two canonical tabular exploration benchmarks. NChain js long- horizon chain environment in which the agent must repeatedly move in one direction to reach terminal state with a large +1 reward. while small immediate reward equal to +-001 is available for moving in the opposite direction. As the chain length increases, the probability of discovering the optimal policy decays exponentially unless sufficient structured exploration is induced. The DeepSea environment, described in Section 5, is a two-dimensional sparse-reward navigation task in which the agent must follow precise sequence of actions reach a distant rewarding state. Both environments therefore test the ability of policy-gradien method to propagate credit over long horizons and through sparse feedback.
Results. Figure 4 reports learning curves on both environments. On NChain (top row, Figures 4a to 4c), the standard softmax softmax-entropp entropy policy gradient baseline performs competitively for the small- est instance (Size 10), but its performance degrades markedly as the chain length increases. In particular, for Size 15 substantial performance gap opens up, and for Size 20 softmax converges slowly and remains far from optimal. In contrast, f-PG with a < 1 achieves substantially higher returns and converges much faster for intermediate horizons, most notably for Size 1,5 where a clear performance gap with the softmax
policy gradient emerges. For the longest chain (Size 20), Tsallis regularization continues to outperform the other baselines but exhibits a similarly slow convergence trend to softmax softmax-entropy, entropy, reflecting the difficulty of the problem at this scale. Moreover, alternative regularization schemes fail completely on the longest NChain of size 20. Additionally, Escort policy gradients and Hadamard parameterizations plateau at very low re- turns across all chain lengths, indicating the need for additional exploration.
A similar pattern is observed in DeepSea (bottom row, Figures 4d and 4e). For Size 10, Tsallis- regularized policies perform on par with the softmax-cntropp baseline and in some cases converge faster. For the more challenging Size 15 instance, Tsallis policies with < 1 remain competitive. In this environment, f-PG dominates all other baselines, which fail to make meaningful progress toward high-retum policies.
Although no single Tsallis parameter a < is uniformly optimal across all problem sizes, clear and robust trend emerges across both NChain and DeepSea: for every environment, there exists an a < that strictly outperforms all alternative schemes and matches or exceeds the performance of distmmxxentroppy These results corroborate the observations of Section and confirm that jointly tailoring the policy parameterization and the regularization to the structure of the problem leads to improved empirical performance.
J.3 FULL DESCRIPTION OF THE DEEPRL EXPERIMENTS
We provide here full description of the a-Tsallis PPO algorithm and the experimental setup of Section
Algorithm description. a-Tsallis PPO follows the same overall algorithmic structure as stan- dard PPC, with only minor modifications: the softmax policy parameterization and entropy regular- ization are replaced by their Tsallis o-softargmax and Tsallis a-regularization counterparts. Specif- ically, the policy network outputs unnormalised action logits, which are mapped to probability distribution via the Tsallis a-softargmax instead of a usual softmax (see Section 3). At each interac- tion step, we compute the Tsallis divergence between the current policy and the uniform distribution over actions using the same coefficient o, and subtract X D expression of fa) from the received reward.?. 2 All other components, including the clipped surrogate objective, value loss, and advantage normalization, remain unchanged.
(see Table for the
Training pipeline. At each update, we collect trajectories from 16 parallel environments for 32 steps, followed by 16 epochs of PPO optimisation over 4 minibatches. We use discounting factor
"This regularized reward is used in the computation advantages and value targets for the DeepSea environment. The reason is that adding entropy to the rewards turns out to be critical for the method's final performance, since the original softmax-PPP fails even in DeepSea of size 20. Notice that it contrasts with an original PPO that adds entropy regularization only to a loss function and not to reward. For Noisy Ca rpole, e, we use standard implementation of PPO haseline.
62

---

Published as a conference paper at ICLR 2026
y 0.99 and GAE À = 0.95, and apply gradient clipping at norm 0.5. Both actor and critic are two- layer multilayer perceptrons with 64 hidden units and tanh activations. Optimization is performed using Adam (Kingma, 2014), and we perform grid search over
E {10-9, 10-2, 10-1, 1.0),
E {10-*, 3 x 10 10 10-3)
Each configuration is evaluated across 25 seeds. Episode returns are aggregated per configuration and reported as mean standard error. For each a, select the configuration that produces the highest last reward on average.
63


Reviews:
[{"review_id": "MFsshywhv6", "reviewer": "Reviewer_q88P", "summary": "This submission derives fast rates (i.e., $\\tilde{O}(\\epsilon^{-1})$) for learning against the $f$-divergence regularized objective in discounted MDPs, which is achieved in a batch-online manner. In the algorithm design, the *log-linear policy with a reference model $\\pi^\\text{ref}$* under KL-regularization is extended to the so-called \"coupled parametrization\" in this submission. Finally, the submission claims a separation result between Tsallis-entropy regularization and entropy regularization by comparing *two upper bounds*.", "questions": "N/A", "limitations": "", "rating": null, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "- This is the first work deriving fast rates $\\tilde{O}(\\epsilon^{-1})$ for learning w.r.t. divergence-regularized objectives in the discounted settting.\n- The proofs are correct.", "weaknesses": "> **To AC: the reviewer is willing and ready to further discuss about this submission with AC or even SAC if needed.**\n\n- Every time $[f']^{-1}$ appears in this submission, it is **mathematically wrong**: because, for example, chi-square divergence is already nice enough, but the $a \\mapsto \\max\\{0, a\\}$ (also appears as ReLU in the lierature) in the Lemma G.2 of [10] already certificates that it is not possible to simply subsume the solution to this constrained optimization problem using $[f']^{-1}(\\cdot)$ and the complementary slackness condition might need to be tackled in a case-by-case way.\n\n- The smoothness property (i.e., the Hessian spectrum upper bound) is trivial and does not even deserve a theorem, i.e., Theorem 4.3, because it is well known that the Fenchel conjugate of a $\\alpha$-strongly-convex function is $\\alpha^{-1}$-smooth (under very mild qualitative regularity conditions); which is nearly exactly the case for the regularized objective with equation (9) as the parametrization\n- The artificial assumptions from Line 201 to Line 210 are far from enlighting and even **known to be** highly unnecessary for important cases like reverse-KL regularization and chi-square divergence regularization: \n  1. to be concrete, the reviewer **strongly disagrees** with Line 215-216 (the sentence around \"which prevents\") because the analysis of learning w.r.t. the reverse-KL-regularized objectives have become sharp (in terms of the dependency on $\\epsilon$, i.e., $\\tilde{O}(\\epsilon^{-1})$) for contextual bandits and episodic MDPs in the hybrid setting [6, 1], for contextual bandits in the offline setting [9,7], and for both contextual bandits and episodic MDPs in the online setting [8].\n  2. Even without Assumption P, and even in the pure offline setting without exploration, the analysis of learning against many divergence regularized objectives is doable, as manifested in the [7]\n- The term \"coupled parametrization\" is confusing because it is just an extension of the \"log-linear policy *with a reference policy*\" to the general $f$-divergence setting, see, e.g., Definition 1.1 in [1]\n- The PL condition, i.e., the \"essentially strongly concave\" property of the regularized objective **should not appear as a brandly new contribution** in this submission because it has been presented in a more minimalist setting in the offline contextual bandits setting in [7]\n\n\n- If the authors do plan to claim the separaion between Tsallis regularization and vanlla entropy regularization for learning against the unregularized objective at the end of Section 5, they should not compare two upper bounds.\n- The study of learning w.r.t. divergence-regularized value functions and objectives dates back to a long line a previous effors **no later than** [2, 3], at least in the episodic MDP setting. And **divergence-regularized performance difference lemma** appeared **no latter than** Section 5 in [8] and Lemma 3 in [5]\n  - If the authors do consider their analysis is totally unrelated to the divergence-regularized performance difference lemma (or the so-called soft peformance difference lemma) in the literature, they should justify it **technically instead of secretly**.\n  - Also, the **divergence-regularied Bellman operator** has been illustrated in detail in both [3] and [5], which is certainly not a \"newly introduced\" concept in this submission.\n- The reviewer does not want to claim that the authors are **plagiarizing or rephrasing previous works in a more involved way**, but the authors should respect the previous efforts in the theory community in a decent way.\n  - If the authors do consider the discounted setting in this submission is fundamentally different from the finite-horizon episodic MDP settings or the contextual bandit settings considered in [1-10] in the literature and does not plan to discuss the relation between this submission and any of [1-10], they should justify it **technically instead of secretly**.\n  - **To AC: the reviewer is willing to discuss about this point if necessary.**\n\n\nReferences\n\n[1] Foster, Dylan J., Zakaria Mhammedi, and Dhruv Rohatgi. \"Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration.\" arXiv preprint arXiv:2503.07453 (2025).\n\n\n[2] Xiong, Wei, et al. \"Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint.\" arXiv preprint arXiv:2312.11456 (2023).\n\n[3] Xie, Tengyang, et al. \"Exploratory preference optimization: Harnessing implicit q*-approximation for sample-efficient rlhf.\" arXiv preprint arXiv:2405.21046 (2024).\n\n[4] Huang, Jiawei, et al. \"Can rlhf be more efficient with imperfect reward models? a policy coverage perspective.\" arXiv preprint arXiv:2502.19255 (2025).\n\n[5] Yuan, Yurun, et al. \"Trajectory Bellman Residual Minimization: A Simple Value-Based Method for LLM Reasoning.\" arXiv preprint arXiv:2505.15311 (2025).\n\n\n[6] Zhao, Heyang, et al. \"Sharp analysis for kl-regularized contextual bandits and rlhf.\" arXiv preprint arXiv:2411.04625 (2024).\n\n[7] Zhao, Qingyue, et al. \"Towards a Sharp Analysis of Offline Policy Learning for $ f $-Divergence-Regularized Contextual Bandits.\" arXiv preprint arXiv:2502.06051 (2025).\n\n[8] Zhao, Heyang, et al. \"Logarithmic regret for online kl-regularized reinforcement learning.\" arXiv preprint arXiv:2502.07460 (2025).\n\n\n[9] Aminian, Gholamali, et al. \"Theoretical Analysis of KL-regularized RLHF with Multiple Reference Models.\" arXiv preprint arXiv:2502.01203 (2025).\n\n\n[10] Huang, Audrey, et al. \"Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment.\" arXiv preprint arXiv:2503.21878 (2025).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "B2TF3wqP1d", "reviewer": "Reviewer_s4Jk", "summary": "This paper extends the entropy regularized softmax PG in Mei et al. 2020b to the a general regularization based on the coupled parameterization. Convergence guarantees are also established.", "questions": "* In Mei et al. 2020b, there are exists sublinear convergence result for the non-regularized softmax PG. As far as I can see, the authors only extend the regularized counterpart. Is it right? Even though the sample complexity can be obtained for the non-reguarlized case by choosing the parameter carefully, the sublinear convergence result in the exact setting for the non-regularized case cannot be obtained from the linear result for the regularized case. Isn't it?\n* A major theoretical contribution claimed by the authors is that there is no problem dependent hidden in the convergence rate. Is it fully due to the projection operator or also relies the the particular divergence? Will it also be helpful for removing the constant in the sublinear convergence of the non-regularized softmax PG?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Extension of entropy regularized softmax PG.", "weaknesses": "* Presentation can be improved. In particular, more discussion of the theoretical results will be helpful for the reader to get a better understanding since there are quite a lot of parameters involved. \n* More numerical experiments can be conducted, even though the authors argue that the goal is to verify the effectiveness of Tsallis divergence. It is known that (entropy regularized) softmax PG is highly inefficient compared to (entropy regularized) NPG due to that the appearance of the policy in the exponential term may cause a mislead. I am wondering whether the new algorithm based on Tsallis divergence will be efficient than NPG or not. At least, tests for the exact setting can be conducted. \n* References are missing. For example in \"Elementary analysis of policy gradient methods\" by Liu et al 2024, it is shown that softmax PG (without regularization) can achieve sublinear convergence for ANY constant step size though the problem dependent constant still exists.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "UkvLFum5y9", "reviewer": "Reviewer_zseX", "summary": "This paper proposes generalization of entropy regularized policy gradient methods using f-divergences, as well as corresponding parameterizations.\n\nThe authors shows global convergence results the proposed methods, as well as experimental results to verify the theoretical findings.", "questions": "1. I am wondering how the methods perform when the interest is to obtain the unregularized optimal value/policy. I can imagine the operator to avoid small probability could fail (since it is unavoidable to get close to deterministic policies in that case). Does your method provide better iteration/sample complexity?\n\n2. The authors mentioned that entropy and Tsallis, which are two important existing regularization, can be recovered by the f-divergences. Are there any new regularization which can perform better than existing ones (or the other way those two are the best possible)?\n\n3. It is claimed that for the PL inequality, \"our proof, based on the properties of Fenchel-Legendre conjugation, is much simpler\". After checking it seems to me the key ideas of smoothness and PL inequality proofs are largely similar to existing proofs in entropy regularized proofs, especially the lower bounding of policy gradient using Eq. (52) and $H(w_\\theta)$, and upper bounding the suboptimality gap by Eq. (51). Could you elaborate how Fenchel-Legendre conjugation makes your proofs much simpler (my understanding is that this helps proving upper bounding suboptimality gap in general f-divergences)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Generalizing the entropy regularizer to f-divergences is a reasonable idea.\n2. The projection operator to avoid deterministic policies is useful.", "weaknesses": "1. The work seems to be generalizing and recovering existing work (entropy, Tsallis). It seems this work is not suggesting some new regularization which is better performing than existing ones.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "24yxMJvnX9", "reviewer": "Reviewer_ri98", "summary": "The authors propose a general f-regularized policy gradient method with coupled parametrization, which generalizes the popular KL regularization with softmax parametrization. Theoretically, they demonstrate global convergence and show an improved trade-off between sample complexity and regularization bias compared to the classical entropy-softmax combination.", "questions": "- What are the main factors limiting the proposed algorithm from being evaluated on a broader set of environments, such as Atari?\n- How does this approach compare to prior work [1] showing that Mirror Descent, with different choices of mirror map and optimization space (e.g., logits or policy), can lead to novel regularized policy gradient objectives?\n\n[1] Vaswani, S., Bachem, O., Totaro, S., Müller, R., Garg, S., Geist, M., Machado, M.C., Castro, P.S. and Roux, N.L., 2021. A general class of surrogate functions for stable and efficient reinforcement learning. arXiv preprint arXiv:2108.05828.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors propose a general framework for studying policy gradient methods in f-divergence-regularized RL with coupled parametrization, providing strong theoretical guarantees.", "weaknesses": "- The experiments are conducted on a 5×5 GridWorld, which limits the generalizability of the proposed policy gradient method.\n- Apart from the theoretical contributions, which I do not feel qualified to fully assess, it is unclear to me what practical advantage the proposed algorithm offers compared to using KL regularization with softmax parametrization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)