On the Linear Convergence of Policy Gradient under Hadamard Parameterization
1]Jiacai Liu
2]Jinchi Chen
1]Ke Wei
[1]School of Data Science, Fudan University, Shanghai, China.
[2]School of Mathematics, East China University of Science and Technology, Shanghai, China.

The convergence of deterministic policy gradient  under the Hadamard parametrization is studied in the tabular setting and the  global linear convergence of the algorithm is established. To this end, we first show that the error decreases at an $O(\frac{1}{k})$ rate for all the iterations. Based on this result, we further show that the algorithm has a faster local linear convergence rate after $k_0$ iterations, where $k_0$ is a constant that only depends on the MDP problem and the  step size. Overall, the algorithm displays a linear convergence rate for all the iterations with a   loose constant  than that for the local linear convergence rate.

Keywords. Policy gradient, Hadamard parameterization, linear convergence

§ INTRODUCTION

Reinforcement learning (RL) is a type of machine learning technique for solving sequential decision problems and has recently achieved great success in many areas, such as games [18, 23, 4, 26], robotics [8, 13, 16] and various other real applications [1, 7, 17]. Typically, RL can be modeled as a Markov decision process (MDP) represented by a tuple $\mathcal{M} \left(\calS ,\calA ,P,r,\gamma ,\mu \right)$, where $\calS$ is the state space, $\calA$ denotes the action space, $P(s'|s,a)$ is the transition probability or density from state $s$ to state $s'$ under action $a$, $r: \calS \times \calA \times \calS \rightarrow \mathbb{R}$ is the reward function, $\gamma \in [0,1)$ is the discounted factor  and $\mu$ is the probability distribution of the initial state $s_0$. Here we restrict our attention to the tabular setting where $\calS$ and $\calA$ are finite, i.e., $|\calS|<\infty$ and $|\calA|<\infty$.
Let $\Delta(\calA)$ be the probability simplex over the set $\calA$,
defined as

\begin{align}
\Delta \left( \calA \right) =\left\{ \theta \in \mathbb{R} ^{|\calA |}: \theta _i\ge 0,\sum_{i=1}^{|\calA |}{\theta _i}=1 \right\}.
\end{align}

Given a stationary policy $\pi:\calS\rightarrow \Delta(\calA)$, the state value function at  $s\in\calS$ and the state-action value function at $(s,a)\in\calS\times \calA$ are defined as

\begin{align}
V^{\pi}\left( s \right) &:=\mathbb{E} \left\{ \sum_{t=0}^{\infty}{\gamma ^tr\left( s_t,a_t,s_{t+1} \right)}|s_0=s,\pi \right\},
\label{value function} \\
Q^{\pi}\left( s,a \right) &:=\mathbb{E} \left\{ \sum_{t=0}^{\infty}{\gamma ^tr\left( s_t,a_t,s_{t+1} \right)}|s_0=s,a_0=a,\pi \right\}.
\label{Q function}
\end{align}

Overall, the goal of RL is to a find a policy that maximizes the weighted average of the state values under the initial distribution $\mu$, namely to solve

\begin{align}
\underset{\pi}{\max}\,V^{\pi}\left( \mu \right). \label{objective}
\end{align}

Here $
V^{\pi}\left( \rho \right) :=\mathbb{E} _{s\sim \rho}\left\{ V^{\pi}\left( s \right) \right\}$ for any $\rho \in \Delta(\calS)$.

Overall, there are two typical categories of RL algorithms. Value-based methods, such as value iteration [19], Q-learning [27] and DQN [18], seek the optimal policy based on the idea of fixed point iteration or approximate dynamic programming. In contrast, policy-based methods, including policy gradient [19], TRPO [20] and PPO [21] reformulate (<ref>) as an optimization problem based on  differentiable parameterized policies and then solve the problem by optimization methods.

In this work, we focus on the policy optimization based methods [28, 25, 12].
Using a differentiable parameterized  policy $\pi_\theta$ where $\theta \in \R^d $, (<ref>) can be written as a finite dimensional optimization problem:

\begin{align}
\underset{\theta \in \mathbb{R} ^d}{\max}\,V^{\pi _{\theta}}\left( \mu \right) .
\label{PG Objective}
\end{align}

Policy gradient (PG) is a first order method for solving (<ref>).

Besides, natural policy gradient (NPG) [10] is an important variant  of PG,  which can be viewed as a preconditioned first order method [3]. Moreover, it is shown that the NPG method can be cast as a special case of the policy mirror ascent method [22].

§.§ Main contribution and related work

There are different parameterizations for policy-based methods, including the direct simplex parameterization:

\begin{align}
\pi _{\theta}\left( a|s \right) =\theta _{s,a} \quad \text{s.t.}\quad \sum_{a\in \calA}{\theta _{s,a}}=1,
\label{simplex}
\end{align}

and the softmax parameterization:

\begin{align}
\pi _{\theta}\left( a|s \right) =\frac{\exp \left\{ \theta_{s,a} \right\}}{\sum_{a\in \calA}{\exp \left\{ \theta_{s,a} \right\}}}.
\label{softmax}
\end{align}

In this paper we consider the Hadamard parameterization:

\begin{align}
\label{Hadamard Policy}
\pi_{\theta}(\cdot|s) = \theta_s \odot \theta_s\quad \text{s.t.} \quad \theta_s\in\S^{|\calA|-1},
\end{align}

where $\odot$ represents the Hadamard product,

$\theta _s=\begin{bmatrix}\theta _{s,1}&\cdots &\theta _{s,|\calA |}\end{bmatrix}^\tran\in \R^{|\calA |}$ and  $\S^{|\calA|-1} = \left\{ \theta \in \R^{|\calA|}: \left\| \theta \right\|_2=1 \right\}$ denotes the unit sphere.

The main contribution of this paper is the establishment of the global linear convergence of the deterministic policy gradient method under the Hadamard parametrization. To the best of our knowledge, this is the first work that studies  the method under the Hadamard parametrization and establishes its linear convergence. That being said, the convergence of deterministic policy gradient and natural policy gradient under the simplex and softmax parameterizations has received many investigations in the literature. Below we give a short summary towards this line of research, with related results being summarized in Table <ref>.

Convergence of PG
For PG with a constant step size, the best known convergence rate is $O(\frac{1}{k})$ for both the simplex and softmax parameterizations [29, 15]. Moreover, it has been further shown in [15] that the convergence rate of PG with a constant step size suffers from an $\Omega \left( \frac{1}{k} \right)$ lower bound for the softmax parameterization.

With exact line search, the authors in [5] show that PG under the simplex parametrization has a linear convergence rate.
Different methods have been proposed to improve the convergence of PG under the softmax parameterization.
For instance, by introducing entropy regularization into the objective function, the authors in [15]  show that PG with a constant step size can have a linear convergence rate.
Apart from entropy regularization, it is shown in [14]  that PG with adaptive step sizes based on the geometric information can also achieve linear convergence.

Convergence  of NPG
Recently, a series of works show that  the NPG methods under the softmax parameterization enjoy a global linear  convergence rate [11, 5, 6]. In particular, it is shown in [5, 11]  that the NPG methods can achieve linear convergence  with a constant step size, exact line search or adaptive step sizes.  Moreover, the authors in [6] show that NPG with the entropy regularization has a linear convergence rate globally and  a super-linear convergence rate locally.

Summary of current results on the convergence of PG and NPG. In the table, ER is short for entropy regularization (also explicitly illustrated in the “regularized” column), and “global” means whether the algorithm converges to the optimal values.

Algorithm         Convergence rate     Global     Linear     Regularized     Step size

PG + simplex ([29])      $O(\frac{1}{k})$                          constant

PG + softmax  ([15])     $O(\frac{1}{k})$                  constant

PG + softmax  ([14])       $O(e^{-c\cdot k})$                  adaptive

PG + softmax + ER ([15])            $O(e^{-c\cdot k})$                       constant

PG + Hadamard (ours)         $O((1-\rho(\kappa,\gamma))^k)$                   constant

NPG + softmax  ([11])      $O\left( e^{-k\left( 1-\frac{1}{\lambda}\eta \right) \Delta} \right)$                           constant

NPG + softmax  ([5])      $O\left( \left( \frac{1+\gamma}{2} \right) ^k \right)$                           adaptive

NPG + softmax + ER ([6])            $O\left(\left( 1-\eta \tau \right) ^k \right)$                            constant

§.§ More Notations and Organization

Advantage function.
Recalling the definitions of the state value function (<ref>) and the state-action value function (<ref>), the advantage function of a policy $\pi$ is defined as

\begin{align*}
A^{\pi}\left( s,a \right) :=Q^{\pi}\left( s,a \right) -V^{\pi}\left( s \right).
\end{align*}

The advantage function $A^\pi(s,a)$ measures how well a single action is  compared with the current  policy $\pi$.

State visitation probability.  The discounted state visitation probability from any initial state $s_0 \in \calS$ is defined as

\begin{align*}
d_{s_0}^{\pi}\left( s \right) :=\left( 1-\gamma \right) \mathbb{E} \left\{ \sum_{t=0}^{\infty}{\gamma ^t\mathbf{1} [ s_t=s ]}|s_0,\pi \right\},
\end{align*}

where $\mathbf{1}[\cdot]$ is the indicator function. Moreover, define $d_{\rho}^{\pi}\left( s \right) :=\mathbb{E} _{s_0\sim \rho}\left\{ d_{s_0}^{\pi}\left( s \right) \right\}$ for any $\rho \in \Delta(\mathcal{S})$. A direct computation yields that

\begin{align}
d_{\rho}^{\pi}\left( s \right) \ge \left( 1-\gamma \right) \mathbb{E} _{s_0\sim \rho}\{\mathbf{1}[s_0=s] \}\ge \left( 1-\gamma \right) \min_{s\in \mathcal{S}} \,\rho (s)\quad \mbox{for any policy } \pi.
\label{d_eq}
\end{align}

Optimal values and optimal policies. The optimal values are defined as the supremum over the all possible polices, i.e.,

\begin{align}
V^*\left( s \right) :=\underset{\pi}{\mathrm{sup}}\,V^{\pi}\left( s \right),\quad Q^*\left( s,a \right) :=\underset{\pi}{\mathrm{sup}}\,Q^{\pi}\left( s,a \right),
\end{align}

If a policy $\pi^*$ satisfies $\mathrm{supp(}\pi ^*(\cdot |s))\subseteq \,\underset{a \in \calA}{\text{argmax}}\,\,Q^*\left( s,a \right)$ for any state $s\in \calS$, then it maximizes the state value function at all states simultaneously,

V^{\pi^*}\left( s \right) =V^*\left( s \right),\quad \forall s\in \calS.

Such policies are also referred to as the optimal policies. Here, we use $\text{supp}(\cdot)$ to denote the support set of any probability distribution.

Other useful notations in the proofs.
Given a state $s \in \calS$, we use $\calA_s^\ast$ to denote the set of optimal actions at state $s$,

\begin{align*}
\calA_s^\ast = \arg\max_{a\in\calA} Q^\ast(s,a).
\end{align*}

Given a policy $\pi$,
we use $b_s^\pi$ to denote the probability of $\pi$ on non-optimal actions at state $s$,

\begin{align*}
b_s^{\pi} = \sum_{a\notin \calA_s^{\ast}} \pi(a|s).
\end{align*}

When $\calA^*_s \ne \calA$, we also define the following two quantities:

\begin{align}
\widehat{V}^*\left( s \right) :=\underset{a\notin \calA _{s}^{*}}{\min}\,Q^*\left( s,a \right) ,\quad \widetilde{V}^*\left( s \right) :=\underset{a\notin \calA _{s}^{*}}{\max}\,Q^*\left( s,a \right).
\end{align}

The well-known Bellman optimality equation states that

\begin{align*}
V^*\left( s \right) =\underset{a\in \mathcal{A}}{\max}\,Q^*\left( s,a \right).
\end{align*}

Thus for any $\rho \in \Delta(\calA)$ that supported on $\calA \setminus \calA^*_s$ , it can be verified that

\begin{align*}
\widehat{V}^
\ast\left( s \right) \le \mathbb{E} _{a'\sim \rho}\left\{ Q^*\left( s,a' \right) \right\} \le \widetilde{V}^\ast\left( s \right).
\end{align*}

When $\calA ^\ast_s = \calA$, we let $\widehat{V}^\ast(s)= 0$ and $\widetilde{V}^\ast(s) = V^*(s)$.

The rest of this paper is organized as follows. In Section <ref>, we derive the expression of the PG algorithm under the Hadamard parametrization, and the main theoretical results are provided in Section <ref>. In Section <ref>, we introduce  an equivalent expression of the algorithm based on normalized Hadamard parametrization which does not require explicit projection onto the unit sphere. The proofs of the convergence results are provided in Section <ref> while the proofs of the useful lemmas are deferred to Section <ref>. Finally, we conclude this paper with a short discussion in Section <ref>.

§ MAIN RESULTS

§.§ Algorithm

Recall that  in the definition of the Hadamard parameterization (see (<ref>)), the vector $\theta_s$ for every state $s \in \calS$ is restricted to the unit sphere $\mathbb{S}^{|\calA|-1}$.  Thus the Riemannian gradient ascent algorithm can be used to solve the corresponding policy optimization problem.   To compute the Riemannian gradient, we can first compute the Euclidean gradient  and then projection it onto the tangent space. Let $g^E =[
(g_{1}^E)^\tran,\cdots, (g_{|\calS|}^E)^\tran
]^\tran\in\R^{|\calS|\cdot |\calA|}$,

where $g_s^E:=\nabla _{\theta _s}V^{\pi _{\theta}}\left( \mu \right) \in \mathbb{R} ^{|\calA |}$ is the Euclidean gradient with respect to parameter $\theta_s$, and let $g_{s,a}^E$ be the $a$-th entry of $g_s^E$. According to the policy gradient theorem [24], the Euclidean gradient of the objective (<ref>) associated with any policy $\pi$ is given by

\begin{align*}
\frac{\partial V^{\pi}\left( \mu \right)}{\partial \pi \left( a|s \right)}=\frac{1}{1-\gamma}d_{\mu}^{\pi}\left( s \right) Q^{\pi}\left( s,a \right).
\end{align*}

Then it follows from the chain rule that

\begin{align*}
%\label{Remannian Gradient}
g_{s,a}^E=\frac{\partial V^{\pi _{\theta}}\left( \mu \right)}{\partial \theta _{s,a}}=\frac{\partial V^{\pi _{\theta}}\left( \mu \right)}{\partial \pi _{\theta}\left( a|s \right)}\cdot \frac{\partial \pi _{\theta}\left( a|s \right)}{\partial \theta _{s,a}}=\frac{2\theta _{s,a}}{1-\gamma}d_{\mu}^{\pi _{\theta}}\left( s \right) Q^{\pi}\left( s,a \right).
\end{align*}

Noting that the tangent space of $\mathbb{S}^{|\calA|-1}$  at each $\theta_s$ is given by

\begin{align*}
T_{\theta _s}\mathbb{S} ^{|\calA |-1}=\left\{ y\in \mathbb{R} ^{|\calA |}: \left< y,\theta _s \right> =0 \right\},
\end{align*}

the projection of $g^E_s$ onto $T_{\theta _s}\mathbb{S} ^{|\calA |-1}$ (i.e., the Riemannian gradient, denoted $g_s$) is given by

\begin{align*}
g_s = (I-\theta_s\theta_s^\tran)g^E_s.
\end{align*}

Elementwisely, we have

\begin{align*}
%\label{Remannian Gradient}
g_{s,a} &= g_{s,a}^E-\theta_{s,a}(\theta_s^\tran g_s^E)\\
&=\frac{2\theta _{s,a}}{1-\gamma}d_{\mu}^{\pi _{\theta}}\left( s \right) Q^{\pi}\left( s,a \right)-\theta_{s,a}\sum_{a'}\frac{2\theta _{s,a'}^2}{1-\gamma}d_{\mu}^{\pi _{\theta}}\left( s \right) Q^{\pi}\left( s,a' \right)\\
&=\frac{2\theta _{s,a}}{1-\gamma}d_{\mu}^{\pi _{\theta}}\left( s \right)\left(Q^\pi(s,a)-\sum_{a'}\theta_{s,a'}^2Q^\pi(s,a')\right)\\
&=\frac{2\theta _{s,a}}{1-\gamma}d_{\mu}^{\pi _{\theta}}A^\pi(s,a).\numberthis\label{Remannian Gradient}
\end{align*}

After updating $\theta_s$ towards the Riemannian gradient ascent direction, an additional normalization step is needed to ensure that the new estimate will be on the unit sphere. More precisely, letting $\eta$ be the step size, the basic update can be written as

\begin{align}
\theta _s\gets \frac{\theta _s+\eta g_s}{\left\| \theta _s+\eta g_s \right\| _2}.
\label{original update rule}
\end{align}

Substituting the expression of $g_{s,a}$ into  (<ref>) yields that

\begin{align}
\theta _{s,a}\gets \frac{\theta _{s,a}\left( 1+\frac{2\eta d_{\mu}^{\pi}\left( s \right)}{1-\gamma}A^{\pi}\left( s,a \right) \right)}{\sqrt{1+\frac{4\eta ^2\left( d_{\mu}^{\pi}\left( s \right) \right) ^2}{\left( 1-\gamma \right) ^2}\mathbb{E} _{a'\sim \pi \left( \cdot |s \right)}\left\{ \left( A^{\pi}\left( s,a' \right) \right) ^2 \right\}}}.
\label{update rule}
\end{align}

The complete description of the algorithm is presented in Algorithm <ref>, where we simplify the notations $d^{\pi_{\theta^{k}}}_\mu$, $V^{\pi_{\theta^{k}}}$, $Q^{\pi_{\theta^{k}}}$, $A^{\pi_{\theta^{k}}}$,$\pi_{\theta^{k}}$ to $d^{k}_\mu$, $V^{k}$, $Q^{k}$, $A^{k}$, $\pi^{k}$, respectively.
Note that all the  entries of the initial parameters $\theta^0$ must be non-zeros, otherwise the parameters will not be updated.

Deterministic Policy Gradient Under Hadamard Parametrization
step size $\eta > 0$, initial parameters $\{\theta^{0}_{s,a} \ne 0: s \in \calS, a\in \calA\}$

Compute the policy probabilities:
\pi _{s,a}^{k}=\left( \theta _{s,a}^{k} \right) ^2, ~\forall s\in \calS ,a\in \calA.

Compute $d^{k}_\mu$ and $A^{k}$ and update the parameter:

\begin{align}
\theta _{s,a}^{k+1}=\frac{\theta _{s,a}^{k}\left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a \right) \right)}{\sqrt{1+\frac{4\eta ^2\left( d_{\mu}^{k}\left( s \right) \right) ^2}{\left( 1-\gamma \right) ^2}\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ \left( A^k\left( s,a' \right) \right) ^2 \right\}}}, \quad \forall s\in \calS ,a\in \calA;
\end{align}

or equivalently, update the policy:

\begin{align}
\pi ^{k+1}(a|s)=\frac{\pi ^k\left( a|s \right) \left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a \right) \right) ^2}{1+\frac{4\eta ^2\left( d_{\mu}^{k}\left( s \right) \right) ^2}{\left( 1-\gamma \right) ^2}\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ \left( A^k\left( s,a' \right) \right) ^2 \right\}}.
\end{align}

§.§ Theoretical results

In this section, we provide the convergence results for Algorithm <ref>
under standard assumptions. In Theorem <ref>, the global convergence of the algorithm is established. Theorem <ref> shows that the state value error decreases at an $O(\frac{1}{k})$ rate for all the iterations. Furthermore, we show that in Theorem <ref> that the algorithm enjoys a linear convergence rate after $k_0$ iterations and overall  displays a global linear convergence.

[Bounded Reward]
$r(s,a)\in[0,1],\forall (s,a).$

[Sufficient Exploration]
$\tilde{\mu}:=\underset{s\in \calS}{\min}\,\mu \left( s \right) >0$.

The existing global convergence results of the PG methods relies heavily on this assumption.
Whether gradient ascent will globally converge if this condition is not met remains an open problem  [2]. When this condition is met, it follows from (<ref>) that the state visitation probability $d^\pi_\mu(s)$ is strictly positive for any $s \in \calS$.

There exists at least one state that has non-optimal actions, i.e., $\widetilde{S} \ne \emptyset$, where $\widetilde{S}=\{s \in \calS:\calA^*_s \ne \calA\}$ denotes the set of states that have non-optimal actions. Otherwise, it is trivial that any policy is an optimal policy.

For any constant step size  $\eta = \frac{(1-\gamma)^2}{4}\kappa$ with $\kappa \in (0,1)$ and the initial parameters $\theta^0$ such that $
\theta _{s,a}^{0} \ne 0 $ for all $(s,a)$ pairs, the value functions of the  policies generated by Algorithm <ref>  converge  globally to $V^\ast(\rho)$ for any $\rho \in \Delta(\calS)$, i.e.,

\begin{align}
\underset{k\rightarrow \infty}{\lim}\,\,V^{k}\left( \rho \right) =V^*\left( \rho \right).
\end{align}

Under the  conditions of Theorem <ref>, the value functions of the  policies generated by Algorithm <ref> converge to the optimal value with a sublinear rate,

\begin{align}
V^*\left( \mu \right) -V^{k}\left( \mu \right) \le \frac{g\left( \kappa ,\lambda \right) ^{-1}}{k},
\label{SublinearRate}
\end{align}

where $
g\left( \kappa ,\lambda \right) =\frac{3\kappa \tilde{\mu}^2\left( 1-\gamma ^4 \right) \lambda}{4+\kappa ^2}$ and $\lambda$ is a strictly positive constant (see Lemma <ref>).

Under the  conditions of Theorem <ref>, we have the following results:

(a) For any $k\ge k_0(\kappa,\gamma)$, the value functions of the  policies generated by Algorithm <ref> converge locally at  a linear rate,

\begin{align*}
V^*\left( \mu \right) -V^k\left( \mu \right) \le c(\kappa,\gamma) \cdot \left( 1-\rho \left( \kappa ,\gamma \right) \right) ^{k-k_0\left( \kappa ,\gamma \right)},
\end{align*}

* $
\rho \left( \kappa ,\gamma \right) =\frac{\left( 1-\gamma \right) ^2\kappa \tilde{\mu}}{4+\kappa ^2}\cdot \left( 1-\underset{s\in \mathcal{S}}{\max}\,\,b_{s}^{\frac{k_0(\kappa,\gamma)}{2}} \right) \cdot M_1\left( \kappa ,\gamma \right) $,

* $c(\kappa,\gamma) = \frac{\underset{s\in \mathcal{S}}{\max}\left( V^*\left( s \right) -\widehat{V}^*\left( s \right) \right) \underset{s\in \mathcal{S}}{\max}\,\,b_{s}^{k_0\left( \kappa ,\gamma \right)}}{1-\gamma}$,

* $
M_1\left( \kappa ,\gamma \right) =
\underset{s\in \widetilde{S}}{\min}\,\,\left( V^*\left( s \right) -\widetilde{V}^*\left( s \right) \right) \cdot \left( 1-\frac{\kappa}{2}+\frac{\kappa \left( 1-\gamma \right) ^2\tilde{\mu}}{4}\cdot \underset{s\in \calS}{\min}\left\{ V^\ast\left( s \right) +\widehat{V}^\ast\left( s \right) \right\} \right) $,

* $
k_0\left( \kappa ,\gamma \right) =\frac{8\gamma g\left( \kappa ,\gamma \right) ^{-1}}{\tilde{\mu}M_1\left( \kappa ,\gamma \right)}$.

(b) The upper bound established in (a) holds for all $k\ge0$ with

\begin{align*}
c\left( \kappa ,\gamma \right) =\frac{\underset{s\in \mathcal{S}}{\max}\left( V^*\left( s \right) -\widehat{V}^*\left( s \right) \right)}{1-\gamma} .
\end{align*}

Thus, Algorithm <ref> shows a linear convergence globally.

As can be seen in the proof, the establishment of the upper bound in Theorem <ref> (a) relies on Theorem <ref> to  determine the threshold  $k_0\left( \kappa ,\gamma \right)$.

§.§ Equivalent algorithm without spherical constraint

Deterministic Policy Gradient Under Normalized Hadamard Parametrization

step size $\eta > 0$, initial parameters $\{\theta^{0}_{s,a} \ne 0 : s \in \calS, a\in \calA\}$

Compute the policy probabilities:

\begin{align*}
\forall s\in \calS ,a\in \calA :\,\pi _{s,a}^{k}=\frac{\left( \theta _{s,a}^{k} \right) ^2}{\left\| \theta _{s}^{k} \right\| _{2}^{2}}.
\end{align*}

Compute the exact gradient of $\mathcal{L} _k\left( \theta \right)$ in (<ref>) using (<ref>).

Update the parameter:

\begin{align*}
\theta _{k+1}=\theta _k+ \eta \cdot \nabla _{\theta}\mathcal{L} _k\left( \theta \right) |_{\theta =\theta _k}.
\end{align*}

Note that it requires explicit normalization to satisfy the spherical constraint in Algorithm <ref>, which is not flexible when using function approximation. In this section, we are about to show that Algorithm <ref> is equivalent to an algorithm that does not require parameter normalization. To this end, first define the normalized Hadamard parametrization  as

\begin{align}
\pi _{\theta}\left( a|s \right) =\frac{(\theta _{s,a})^2}{\left\| \theta _s \right\|^2_2}, \quad\theta _s\in \mathbb{R} ^{|\calA |}\setminus \left\{ \mathbf{0} \right\}.
\label{normalized hadamard}
\end{align}

In the $k$-th iteration, the algorithm optimizes following objective function:

\begin{align}\label{eq:tmp_ke01}
\mathcal{L} _k\left( \theta \right) :=\frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\mu}^{k}}\{ \left\| \theta _{s}^{k} \right\| _{2}^{2} \cdot \mathbb{E} _{a\sim \pi _{\theta}}\{ A^k\left( s,a \right) \} \},
\end{align}

and a gradient ascent step is conducted  with a constant step size $\eta$,

\begin{align}
\theta _{k+1}=\theta _k+ \eta \cdot \nabla _{\theta}\mathcal{L} _k\left( \theta \right) |_{\theta =\theta _k}.
\label{normalized hadamard update rule}
\end{align}

For any $s\in \calS$, a direct computation yields that

\begin{align}
\left. \frac{\partial \mathcal{L} _k\left( \theta \right)}{\partial \theta _{s,a}} \right|_{\theta =\theta ^k}&=\sum_{a'\in \mathcal{A}}{\left. \frac{\partial \mathcal{L} _k\left( \theta \right)}{\partial \pi \left( a'|s \right)} \right|_{\theta =\theta ^k}\cdot \left. \frac{\partial \pi \left( a'|s \right)}{\partial \theta _{s,a}} \right|}_{\theta =\theta ^k} \notag
\\
\quad         &=\sum_{a'\in \mathcal{A}}{\frac{\left\| \theta _{s}^{k} \right\| _{2}^{2}d_{\mu}^{k}\left( s \right) A^k\left( s,a' \right)}{1-\gamma}\cdot \frac{2\theta _{s,a}^{k}}{\left\| \theta _{s}^{k} \right\| _{2}^{4}}\left( \mathbf{1}\left[ a=a' \right] \left\| \theta _{s}^{k} \right\| _{2}^{2}-\left( \theta _{s,a'}^{k} \right) ^2 \right)} \notag
\\
\quad         &=\frac{2d_{\mu}^{k}\left( s \right)}{1-\gamma}\frac{\theta _{s,a}^{k}}{\left\| \theta _s \right\| _{2}^{2}}\left( A^k\left( s,a \right) \left\| \theta _{s}^{k} \right\| _{2}^{2}-\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ A^k\left( s,a' \right) \right\} \right) \notag
\\
\quad         &=\frac{2d_{\mu}^{k}\left( s \right)}{1-\gamma}\cdot \theta _{s,a}^{k}\cdot A^k\left( s,a \right).
\label{normalized hadamard gradient}
\end{align}

The complete procedure is summarized in Algorithm <ref>.
Since the normalized Hadamard parametrization is not defined when $\theta_s = \textbf{0}$ , one must ensure that $ \left\| \theta _{s}^{k} \right\| _{2}^{2} \ne 0$ for all iterations and $\forall s \in \calS$. However, this is not an issue if $\left\| \theta _{s}^{0} \right\| _{2}^{2} \ne 0$ since

\begin{align*}
\left\|\theta _{s}^{k+1} \right\| _2=\left\| \begin{array}{c}
\theta _{s}^{k}+\eta \cdot \left. \nabla _{\theta _s}\mathcal{L} _k\left( \theta \right) \right|_{\theta =\theta _k}\\
\end{array} \right\| _2\overset{\left( a \right)}{=}\sqrt{\left\| \theta _{s}^{k} \right\| _{2}^{2}+\eta ^2\left\| \left. \nabla _{\theta _s}\mathcal{L} _k\left( \theta \right) \right|_{\theta =\theta _k} \right\| _{2}^{2}}\ge \left\| \theta _{s}^{k} \right\| _2,
\end{align*}

where step (a) is due to (<ref>).

Next we show that Algorithm <ref> and Algorithm <ref> are equivalent to each other in the policy domain provided the initial policies are the same. First,

it is easy to see that

\begin{align}
\left< \left. \nabla _{\theta _s}\mathcal{L} _k\left( \theta \right) \right|_{\theta =\theta ^k},\theta _{s}^{k} \right> =\sum_{a\in \mathcal{A}}{\frac{2d_{\mu}^{k}\left( s \right)}{1-\gamma}\left( \theta _{s,a}^{k} \right) ^2A^k\left( s,a \right)}=\frac{2d_{\mu}^{\pi}\left( s \right)}{1-\gamma}\left\| \theta _{s}^{k} \right\| _{2}^{2}\mathbb{E} _{a\sim \pi ^k\left( \cdot |s \right)}\left\{ A^k\left( s,a \right) \right\} =0.
\label{normalized hadamard gradient is orthogonal}
\end{align}

Plugging (<ref>), (<ref>) and (<ref>) into (<ref>) yields that

\begin{align*}
\pi ^{k+1}(a|s)&=\left( \frac{\theta _{s,a}^{k+1}}{\left\| \theta _{s}^{k+1} \right\|_2} \right) ^2
\\
&=\frac{\left( \theta _{s,a}^{k}+\left. \eta \cdot \frac{\partial \mathcal{L} _k\left( \theta \right)}{\partial \theta _{s,a}} \right|_{\theta =\theta ^k} \right) ^2}{\left\| \theta _{s}^{k}+\left. \eta \cdot \nabla _{\theta _s}\mathcal{L} _k\left( \theta \right) \right|_{\theta =\theta ^k} \right\| _{2}^{2}}
\\
&=\frac{\left( \theta _{s,a}^{k}\left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a \right) \right) \right) ^2}{\sum_{a'}{\left( \theta _{s,a'}^{k} \right) ^2\left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a' \right) \right) ^2}}
\\
&=\frac{\frac{\left( \theta _{s,a}^{k} \right) ^2}{\left\| \theta _{s}^{k} \right\| _{2}^{2}}\cdot \left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a \right) \right) ^2}{\sum_{a'}{\frac{\left( \theta _{s,a'}^{k} \right) ^2}{\left\| \theta _{s}^{k} \right\| _{2}^{2}}\left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a' \right) \right) ^2}}
\\
&=\frac{\pi ^k\left( a|s \right) \left( 1+\frac{2\eta d_{\mu}^{k}\left( s \right)}{1-\gamma}A^k\left( s,a \right) \right) ^2}{1+\frac{4\eta ^2\left( d_{\mu}^{k}\left( s \right) \right) ^2}{\left( 1-\gamma \right) ^2}\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ \left( A^k\left( s,a' \right) \right) ^2 \right\}},
\end{align*}

which is the same as the policy update in Algorithm <ref>. Therefore, both algorithms output the same polices at all the iterations if using the same initial policy $\pi^{0}$.

§.§ Numerical simulations on MAB

In this section, we empirically compare Algorithm <ref> with the PG and NPG methods under the softmax parametrization on multi-armed bandit problems (MAB).
MAB is a special case of RL problem which only has one single state and $K$ actions (arms). In MAB, the objective function is

\begin{align*}
\underset{\pi _{\theta}}{\max}\,\mathbb{E} _{a\sim \pi _{\theta}}\{ r\left( a \right)\},
\end{align*}

where $r(a)$ is the reward of executing action $a$. For ease of presentation, some auxiliary notations are introduced.
We use $\pi_\theta(a)$ to denote the probability of choosing the action $a$, use $\theta_a$ to denote the parameter for the action $a$, and use $A ^ \pi\left( a \right) :=r\left( a \right) -\mathbb{E} _{a'\sim \pi(\cdot) }\left\{ r\left( a' \right) \right\}$ to denote the advantage function. We also simplify $\pi_{\theta_k} $ and $A^{\pi_{\theta_k}}$ to $\pi^k$ and $A^k$, respectively.  For this particular problem, the update rules of the algorithms are

* PG under Hadamard parametrization:

\begin{align*}
\theta _{a}^{k+1}=\frac{\theta _{a}^{k}\left( 1+2\eta \cdot A^k\left( a \right) \right)}{\sqrt{1+4\eta ^2\mathbb{E} _{a'\sim \pi^k}\left\{ \left( A^k\left( a' \right) \right) ^2 \right\}}}, \quad\forall a\in \left[ K \right],
\end{align*}

* PG under softmax parametrization:

\begin{align*}
\theta _{a}^{k+1}=\theta _{a}^{k}+\eta \cdot \pi ^k\left( a \right) \cdot A^k\left( a \right),  \quad\forall a\in \left[ K \right],
\end{align*}

* NPG under softmax parametrization:

\begin{align*}
\theta _{a}^{k+1}=\theta _{a}^{k}+\eta \cdot A^k\left( a \right), \quad\forall a\in \left[ K \right].
\end{align*}

We set $\eta=0.4$, as suggested in [15] for PG under the softmax parametrization  and test  four different values of $K$. For each $K$, 10 random problem instances are tested where we initialize $\left\{ r\left( a \right) :a\in \left[ K \right] \right\}$ via uniform sampling. The plots of mean and deviation of state value errors against the number of iterations are shown in Figure <ref> in a logarithm scale. It can be observed that on average PG under Hadamard parameterization shows a better performance.

Mean and deviation of value errors (in logarithm)  for different $K$ over 10 random instances.

§ PROOFS

We first list several useful lemmas. The first one is the  performance difference lemma whose proof can be found in  [9] and the proofs of the other lemmas are deferred to Section <ref>.

For any two policy $\pi_1, \pi_2$, and any $\rho \in \Delta(\calS)$, one has

\begin{align*}
V^{\pi_1}(\rho) - V^{\pi_2}(\rho) =\frac{1}{1-\gamma} \E[s\sim d_{\rho}^{\pi_1}]{ \E[a \sim \pi_1(\cdot|s)]{A^{\pi_2}(s,a)} }.
\end{align*}

For any policy $\pi$ and $\rho \in \Delta(\calS)$,

\begin{align}
V^{\ast}(\rho )-V^{\pi}(\rho )\le \frac{\underset{s}{\max}\left\{ V^*\left( s \right) -\widehat{V}^*\left( s \right) \right\}}{1-\gamma}\cdot \mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ b_{s}^{\pi} \right\}.
\end{align}

Consider the policy $\pi^k$ generated by Algorithm <ref>. Suppose $\eta = \frac{(1-\gamma)^2\kappa}{4}$ for $\kappa \in (0,1)$. Then for any $\rho \in \Delta(\calS)$, one has

\begin{align*}
V^{k+1}(\rho )-V^k(\rho )\ge \frac{3\kappa \tilde{\mu}\left( 1-\gamma \right) ^2}{4+\kappa ^2} \cdot \underset{s\in \mathrm{supp}\left( \rho \right)}{\min}\left\{ \rho \left( s \right) \right\} \cdot \sum_{s\in \mathrm{supp}\left( \rho \right)}{\sum_{a \in \calA}{\pi ^k}(a|s)(A^k(s,a))^2}\ge 0.
\end{align*}

In particular when $\rho = \mu$,

\begin{align}
V^{k+1}(\mu )-V^k(\mu )\ge \frac{3\kappa \tilde{\mu}^2\left( 1-\gamma \right) ^2}{4+\kappa ^2}\sum_s{\sum_a{\pi ^k}(a|s)(A^k(s,a))^2}\ge 0.
\end{align}

Consider the policy $\pi^k$ generated by Algorithm <ref>. One has

\begin{align}
\pi^{k+1}(a|s) - \pi^k(a|s) =\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left( A^k(s,a) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left(  (A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}\right)\right). %\label{eq13}
\end{align}

For any $s \in \calS$, the sequence $\{b_s^k\}_{k\geq k_0}$ generated by Algorithm <ref> satisfies

\begin{align*}
b_{s}^{k}-b_{s}^{k+1}\ge \frac{2\eta d_{\mu}^{k}(s)}{1-\gamma}\cdot \frac{\min\mathrm{(}1-b_{s}^{k},b_{s}^{k})}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot \left( M_1(\kappa ,\gamma )-4\gamma \max_{s \in \calS} (V^{\ast}(s)-V^k(s)) \right),
\end{align*}

where $M_1(\kappa,\gamma):= \underset{s\in \widetilde{S}}{\min}\,\,\left( V^*\left( s \right) -\widetilde{V}^*\left( s \right) \right)  \left( 1-\frac{\kappa}{2}+\frac{(1-\gamma )^2\kappa \tilde{\mu}}{4}\cdot \underset{s\in\calS}{\min} \left( V^{\ast}(s)+\widehat{V}^\ast(s) \right) \right) > 0$.

Suppose $\pi^0(a|s)>0$ for all $s\in\calS, a\in\calA$. Then $\forall s,a,k$, one has $\pi^k(a|s) >0$. Moreover,

\begin{align}
\label{eqLambda}
\lambda:=\inf_{k\geq 0} \left\{ \min_{s\in\calS} (1-b_s^k) \right\} >0.
\end{align}

§.§ Proof of Theorem <ref>

Firstly, we prove that the sequence $\{V^k(\rho)\}_k$ is convergent for any  $\rho \in \Delta(\calS)$. Lemma <ref> implies that $\{V^k(\rho)\}_k$ is nondecreasing. Since $V^k(\rho)$ is upper bounded, we conclude that $\{V^k(\rho)\}$ is convergent. Similarly, we can also prove that the sequence $\{Q^k(s,a)\}_k$ is convergent for any $(s,a)$. Specifically, one has

\begin{align*}
Q^{k+1}(s,a) = r(s,a) + \E[s'\sim P(\cdot|s,a)]{V^{k+1}(s')}\geq r(s,a) +  \E[s'\sim P(\cdot|s,a)]{V^{k}(s')} = Q^k(s,a),
\end{align*}

where the inequality  is due to the fact that $V^k(\rho)$ is nondecreasing with $\rho=P(\cdot|s,a)$. Since $Q^k(s,a)$ is upper bounded for any $(s,a)$, it implies that the sequence is convergent. Define

\begin{align*}
V^{\infty}(\rho) &= \lim_{k\rightarrow +\infty} V^k(\rho),\\
Q^{\infty}(s,a)  &=\lim_{k\rightarrow +\infty} Q^{k}(s,a).
\end{align*}

Moreover, define

\begin{align*}
A^{\infty}(s,a)=\lim_{k\rightarrow +\infty}A^k(s,a) = \lim_{k\rightarrow +\infty}Q^{k}(s,a) -\lim_{k\rightarrow +\infty} V^k(s).
\end{align*}

We  will show that

\begin{align}
\label{aux1}
A^{\infty}(s,a) \leq 0
\end{align}

for any $(s,a)$. According to Lemma <ref>, we have

\begin{align*}
V^{k+1}(\mu) - V^{k}(\mu )\geq  \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}   \sum_s  \sum_a \pi^{k}(a|s) (A^{k}(s,a))^2\geq 0.
\end{align*}

Taking a limit on both sides yields that

\begin{align*}
0=\lim_{k\rightarrow +\infty} V^{k+1}(\mu) - V^{k}(\mu ) \geq \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )} \lim_{k\rightarrow +\infty}  \sum_s  \sum_a \pi^{k}(a|s) (A^{k}(s,a))^2\geq 0,
\end{align*}

which implies that

\begin{align}
\label{aux2}
\lim_{k\rightarrow +\infty} \E[a\sim \pi^k(\cdot|s)]{(A^{k}(s,a))^2}=0
\end{align}

for any state $s\in\calS$. We will use proof by contradiction to show that $A^\infty(s,a)\leq 0$ for any state $s$ and any action $a$. Suppose that there exists a state-action pair $(s,a)$ such that $A^\infty(s,a)>0$.
According to Lemma <ref>, it can be seen that the sign of $\pi^{k+1}(a|s) - \pi^k(a|s)$ only depends on the term

\begin{align*}
I_{s,a}^k:= A^k(s,a) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left(  (A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}\right)
\end{align*}

and we have

\begin{align*}
\liminf_{k\rightarrow +\infty}\,\,I_{s,a}^{k} &\ge \liminf_{k\rightarrow +\infty}\,\,A^k(s,a)+\eta \tilde{\mu}\,\liminf_{k\rightarrow +\infty}\left( (A^k(s,a))^2-\mathbb{E} _{a'\sim \pi ^k(\cdot |s)}(A^k(s,a'))^2 \right)
\\
\quad            &=A^{\left( \infty \right)}\left( s,a \right) +\eta \tilde{\mu}\,(A^{\left( \infty \right)}(s,a))^2
\\
\quad            &>A^{\left( \infty \right)}\left( s,a \right),
\end{align*}

where the second line follows from (<ref>) and (<ref>). Thus it implies that there exists a constant $N_0$ such that

\begin{align*}
I_{s,a}^k > \frac{A^\infty(s,a)}{2} > 0
\end{align*}

for any $k\geq N_0$ and $\{\pi^k\}_{k\geq N_0}$ is a nondecreasing sequence. Since $\pi^{N_0}(a|s)>0$ (see the first claim of Lemma <ref>), we have

\begin{align*}
\lim_{k\rightarrow +\infty} \pi^k(a|s) >0 \text{ and } \lim_{k\rightarrow +\infty} \left( \pi^k(a|s)(A^k(s,a))^2 \right) >0,
\end{align*}

which contradicts with (<ref>). Therefore, $A^{\infty}(s,a)\leq 0$ for any $(s,a)$. Finally, we show that $V^{\infty}(\rho) = V^\ast(\rho)$. Using Lemma <ref>, we have

\begin{align*}
V^\ast(\rho) - V^k(\rho) = \frac{1}{1-\gamma}\sum_{s\in \calS} d_{\rho}^\ast(s) \sum_{a\in\calA}\pi^\ast(a|s) A^k(s,a).
\end{align*}

Taking  a limit on both sides yields that

\begin{align*}
V^\ast(\rho) - \lim_{k\rightarrow +\infty} V^k(\rho) = \frac{1}{1-\gamma}\sum_{s\in \calS} d_{\rho}^\ast(s) \sum_{a\in\calA}\lim_{k\rightarrow +\infty}\pi^\ast(a|s) A^k(s,a)\leq 0,
\end{align*}

where the inequality  is due to $A^{\infty}(s,a)\leq 0$.

§.§ Proof of Theorem <ref>

First define the auxiliary policy supported on $\calA_s^*$ as follows:

\begin{align*}
\psi^k(\cdot|s) = \begin{cases}
\frac{\pi^k \left( \cdot |s \right)}{1-b_{s}^{k}}\mathbf{1}\left[ \cdot \in \mathcal{A} _{s}^{*} \right],\mbox{ if }b_s^k\neq 1,\\
\mbox{any distribution supported on }\calA_s^*,&\mbox{ if }b_s^k=1.
\end{cases}
\end{align*}

It is clear that $\pi^k(a|s)=(1-b_s^k)\psi^k(a|s)$ for $a\in\calA_s^*$.
since $\text{supp}(\psi^k) \subseteq \calA^*_s$, one can verify that $\psi^k$ is an optimal policy. Actually, by the performance difference lemma,

\begin{align*}
V^{\psi^k}(\mu) - V^\ast(\mu) =\frac{1}{1-\gamma}\E[s\sim d_{\mu}^{\psi^k}]{\sum_{a\in\calA_s^\ast} \psi^k(a|s) A^\ast(s,a) }=0,\numberthis\label{eq 5}
\end{align*}

where the last line is due to $A^\ast(s,a)=0$ for any $a\in\calA_s^\ast$.
A direct computation yields that

\begin{align*}
V^{k+1}(\mu) - V^{k}(\mu ) &\stackrel{(a)}{\geq} \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}   \sum_s  \sum_a \pi^{k}(a|s) (A^{k}(s,a))^2\\
&\geq \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}   \sum_s d_{\mu}^{\psi^k}(s) \sum_a \pi^{k}(a|s) (A^{k}(s,a))^2\\
&=\frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}   \sum_s d_{\mu}^{\psi^k}(s) \left( \sum_{a\in\calA_s^\ast} \pi^{k}(a|s) (A^{k}(s,a))^2 + \sum_{a\notin\calA_s^\ast} \pi^{k}(a|s) (A^{k}(s,a))^2 \right)\\
&\geq \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}   \sum_s d_{\mu}^{\psi^k}(s)   \sum_{a\in\calA_s^\ast} \pi^{k}(a|s) (A^{k}(s,a))^2 \\
&=\frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}   \sum_s d_{\mu}^{\psi^k}(s) (1-b_s^k)  \sum_{a\in\calA } \psi^k(a|s) (A^{k}(s,a))^2 \\
&\geq \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 }{ (4+ \kappa^2 )}  \left( \min_s (1-b_s^k)\right)  \sum_s d_{\mu}^{\psi^k}(s)  \sum_{a\in\calA } \psi^k(a|s) (A^{k}(s,a))^2 \\
&\stackrel{(b)}{\geq}\frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 \lambda }{ (4+ \kappa^2 )}  \sum_s d_{\mu}^{\psi^k}(s)  \sum_{a\in\calA } \psi^k(a|s) (A^{k}(s,a))^2\\
&\stackrel{(c)}{\geq} \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^2 \lambda }{ (4+ \kappa^2 )}  \left(\sum_s d_{\mu}^{\psi^k}(s)  \sum_{a\in\calA } \psi^k(a|s) |A^{k}(s,a)| \right)^2, \numberthis\label{eq46a}
\end{align*}

where step (a) is due to Lemma <ref>, step (b) follows from Lemma <ref>, and step (c) is due to Jensen's inequality. On the other hand, we have

\begin{align*}
V^\ast(\mu) - V^k(\mu) &\stackrel{(a)}{=} V^{\psi^k}(\mu) - V^k(\mu)\\
&\stackrel{(b)}{=} \frac{1}{1-\gamma}\E[s\sim d_{\mu}^{\psi^k}]{\E[a\sim \psi^k]{A^k(s,a)}}\\
&\leq \frac{1}{1-\gamma}\E[s\sim d_{\mu}^{\psi^k}]{\E[a\sim \psi^k]{ \left| A^k(s,a) \right| }},\numberthis \label{eq46b}
\end{align*}

where step (a) is due to (<ref>), step (b) is due to the performance difference lemma. Combining (<ref>) and (<ref>) together, we have

\begin{align*}
V^{k+1}(\mu) - V^{k}(\mu )  &\geq \frac{3\kappa \tilde{\mu}^2  (1-\gamma)^4\lambda }{ 4+ \kappa^2 }  \left(V^\ast(\mu) - V^k(\mu)  \right)^2\\
:&=g(\kappa,\lambda)  \left(V^\ast(\mu) - V^k(\mu)  \right)^2.
\end{align*}

Let $\delta_k = V^\ast(\mu) - V^k(\mu)$. It can be seen that

\begin{align*}
\delta_k - \delta_{k+1} = V^{k+1}(\mu) - V^k(\mu) \geq g(\kappa,\lambda)   \delta_k^2,
\end{align*}

which is equivalent to

\begin{align}
\delta_{k+1} \leq  \delta_k - g(\kappa,\lambda)\delta_k^2.
\label{error_relationship}
\end{align}

By Assumption <ref> and Lemma <ref>, there exist a state $s \in \widetilde{S}$ and $a \notin \calA^*_s$ such that $\pi^k(a|s) > 0 \,\, \forall k \ge 0$ which results in $b^k_s >0$ for all $k \ge 0$. Combined with Assumption <ref> and Lemma <ref>, one can conclude $\delta_k >0$ for all $k \ge 0$. Thus (<ref>) is equivalent to

\begin{align*}
\frac{\delta _k-\delta _{k+1}}{\delta _{k}^{2}}\ge g\left( \kappa ,\lambda \right).
\end{align*}

By Lemma <ref>, the sequence $\{\delta_k\}_{k \ge 0}$ is nonincreasing. Thus

\begin{align*}
\frac{1}{\delta _{k+1}}-\frac{1}{\delta _k}=\frac{\delta _k-\delta _{k+1}}{\delta _{k+1}\delta _k}\ge \frac{\delta _k-\delta _{k+1}}{\delta _{k}^{2}}\ge g\left( \kappa ,\lambda \right),
\end{align*}

\begin{align*}
\delta _k=\frac{1}{\frac{1}{\delta _k}}=\frac{1}{\frac{1}{\delta _0}+\sum_{j=0}^{k-1}{\left( \frac{1}{\delta _{j+1}}-\frac{1}{\delta _j} \right)}}\le \frac{1}{\sum_{j=0}^{k-1}{g\left( \kappa ,\lambda \right)}}=\frac{g\left( \kappa ,\lambda \right) ^{-1}}{k},
\end{align*}

which completes the proof.

§.§ Proof of Theorem <ref>

Applying Lemma <ref> yields that

\begin{align*}
V^\ast(\mu) - V^k(\mu) &\leq \frac{\max_{s\in\calS}\left(V^\ast(s) -\widehat{V}^\ast(s)\right)  }{1-\gamma}\E[s\sim d_{\mu}^k]{b_s^k}.\numberthis\label{eqMain1}
\end{align*}

By Lemma <ref>,

\begin{align*}
b_{s}^{k}-b_{s}^{k+1}&\ge \frac{2\eta d_{\mu}^{k}(s)}{1-\gamma}\cdot \frac{\min \left\{ 1-b_{s}^{k},b_{s}^{k} \right\}}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot \left( M_1\left( \kappa ,\gamma \right) -4\gamma \underset{s\in \mathcal{S}}{\max}\,\,\left( V^*\left( s \right) -V^k\left( s \right) \right) \right)
\\
\,\,           &\overset{\left( a \right)}{\ge}\frac{2\eta d_{\mu }^{k}(s)}{1-\gamma}\cdot \frac{\left( 1-b_{s}^{k} \right) \cdot b_{s}^{k}}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot \left( M_1\left( \kappa ,\gamma \right) -4\gamma \underset{s\in \mathcal{S}}{\max}\,\,\left( V^*\left( s \right) -V^k\left( s \right) \right) \right)
\\
\,\,           &\overset{\left( b \right)}{\ge}\frac{2\eta d_{\mu }^{k}(s)}{1-\gamma}\cdot \frac{\left( 1-b_{s}^{k} \right) \cdot b_{s}^{k}}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot \left( M_1\left( \kappa ,\gamma \right) -\frac{4\gamma g\left( \kappa ,\lambda \right) ^{-1}}{k\tilde{\mu}} \right),
\end{align*}

where step (a) is due to $\min \left\{ 1-b_{s}^{k},b_{s}^{k} \right\} \ge (1-b^k_s)\cdot b^k_s$, step (b) is due to Theorem <ref>,

\begin{align}
\underset{s\in \mathcal{S}}{\max}\,\,\left( V^*\left( s \right) -V^k\left( s \right) \right) \le \frac{\sum_{s\in \mathcal{S}}{\mu \left( s \right) \left( V^*\left( s \right) -V^k\left( s \right) \right)}}{\tilde{\mu}}=\frac{V^*\left( \mu \right) -V^k\left( \mu \right)}{\tilde{\mu}}\le \frac{g\left( \kappa ,\lambda \right) ^{-1}}{k\tilde{\mu}}\label{max_error_bound}.
\end{align}

It can be seen that when

\begin{align*}
\frac{g\left( \kappa ,\lambda \right) ^{-1}}{k\tilde{\mu}}\le \frac{M_1\left( \kappa ,\gamma \right)}{4\gamma},
\end{align*}

which is equivalent to $k\geq \frac{k_0(\kappa,\gamma)}{2}:= \frac{4\gamma g(\kappa, \lambda)^{-1}}{\tilde{\mu}M_1(\kappa, \gamma)}$,
$\{b_s^k\}_{k\geq \frac{k_0(\kappa,\gamma)}{2}}$ is nonincreasing. Moreover, when $k \ge k_0(\kappa,\gamma)$,

\begin{align*}
b_{s}^{k}-b_{s}^{k+1} &\ge \frac{2\eta d_{\mu s}^{k}}{1-\gamma}\cdot \frac{\left( 1-b_{s}^{k} \right) \cdot b_{s}^{k}}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot \left( M_1\left( \kappa ,\gamma \right) -\frac{M_1\left( \kappa ,\gamma \right)}{2} \right)
\\
\,\,           &\ge \frac{\eta d_{\mu s}^{k}}{1-\gamma}\cdot \frac{\left( 1-b_{s}^{k} \right) \cdot b_{s}^{k}}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot M_1\left( \kappa ,\gamma \right)
\\
\,\,           &\ge \eta \tilde{\mu} \cdot \frac{\left( 1-\underset{s\in \mathcal{S}}{\max}\,\,b_{s}^{\frac{k_0(\kappa,\gamma)}{2}} \right) \cdot b_{s}^{k}}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}\cdot M_1\left( \kappa ,\gamma \right).
\numberthis \label{g0}
\end{align*}

In addition, it is shown in (<ref>) that

\begin{align*}
1+\eta^2 \twonorm{\vg_s^k}^2 \leq 1+\frac{\kappa^2}{4}. %\numberthis \label{g}
\end{align*}

Plugging it and $\eta = \frac{(1-\gamma)^2\kappa}{4}$ into (<ref>) yields that

\begin{align*}
b_{s}^{k}-b_{s}^{k+1}&\ge \frac{\left( 1-\gamma \right) ^2\kappa \tilde{\mu}}{4+\kappa ^2}\cdot \left( 1-\underset{s\in \mathcal{S}}{\max}\,\,b_{s}^{\frac{k_0(\kappa,\gamma)}{2}} \right) \cdot M_1\left( \kappa ,\gamma \right) \cdot b_{s}^{k}
\\
\,\,           &:=\rho \left( \kappa ,\gamma \right)\cdot b_{s}^{k}. \numberthis \label{b_rho}
\end{align*}

It's trivial to verify that $\rho(\kappa,\gamma)>0$. Next we will show that $\rho(\kappa,\gamma)<1$.
Recall the definition of $M_1(\kappa,\gamma)$,

\begin{align*}
M_1\left( \kappa ,\gamma \right) &=\underset{s\in \widetilde{S}}{\min}\,\,\left( V^*\left( s \right) -\widetilde{V}^*\left( s \right) \right) \cdot \left( 1-\frac{\kappa}{2}+\frac{\kappa \left( 1-\gamma \right) ^2\tilde{\mu}}{4}\cdot \underset{s\in S}{\min}\left\{ V^{\ast}\left( s \right) +\widehat{V}^*\left( s \right) \right\} \right)
\\
\,\,          &\le \frac{1}{1-\gamma}\cdot \left( 1-\frac{\kappa}{2}+\frac{\kappa \left( 1-\gamma \right) ^2\tilde{\mu}}{4}\cdot \frac{2}{1-\gamma} \right)
\\
\,\,          &<\frac{1}{1-\gamma}\cdot \left( 1-\frac{\kappa}{2}+\frac{\left( 1-\gamma \right)}{2}\kappa \right)
\\
\,\,          &=\frac{1}{1-\gamma}\cdot \left( 1-\frac{\gamma}{2}\kappa \right)
\\
\,\,          &\le\frac{1}{1-\gamma}.
\numberthis \label{uppder bound of M1}
\end{align*}

Plugging (<ref>) into $\rho(\kappa,\gamma)$ yields that,

\begin{align*}
\rho \left( \kappa ,\gamma \right) <\frac{\left( 1-\gamma \right) ^2\kappa \tilde{\mu}}{4+\kappa ^2}\left( 1-\underset{s\in \mathcal{S}}{\max}\,\,b_{s}^{\frac{k_0(\kappa,\gamma)}{2}} \right) \cdot \frac{1}{1-\gamma}<\frac{1-\gamma}{4}<1.
\end{align*}

By (<ref>),we have

\begin{align}
b_{s}^{k}\le (1-\rho (\kappa ,\gamma ))^{k-k_0(\kappa,\gamma)}b_{s}^{k_0(\kappa,\gamma)}\le (1-\rho (\kappa ,\gamma ))^{k-k_0(\kappa,\gamma)}\cdot \underset{s\in \mathcal{S}}{\max}\,\,b_{s}^{k_0(\kappa,\gamma)}
\label{main_result_for_b},
\end{align}

for all $k\geq k_0(\kappa,\gamma)$ and $s\in \calS$. Combined (<ref>) and (<ref>), the proof for (a) is completed.  For $0\leq k\leq k_0(\kappa,\gamma)$, it can be seen that

\begin{align*}
(1-\rho(\kappa,\gamma))^{k-k_0(\kappa,\gamma)} \geq 1 >b_s^k.
\end{align*}

Thus we have

\begin{align}
\label{eqb}
b_{s}^{k}\le (1-\rho (\kappa ,\gamma ))^{k-k_0(\kappa,\gamma)},
\end{align}

for all $k\geq 0$. Plugging (<ref>) into (<ref>) , the proof of (b) is completed.

§ PROOFS OF TECHNICAL LEMMAS

§.§ Proof of Lemma <ref>

For a policy $\pi$, recall that $b_s^{\pi} = \sum_{a\notin \calA_s^{\ast}} \pi(a|s)$. Define

\begin{align*}
\xi^\pi(\cdot|s) = \begin{cases}
\frac{\pi \left( \cdot |s \right)}{b_{s}^{\pi}}\mathbf{1}\left[ \cdot \notin \mathcal{A} _{s}^{*} \right],&\mbox{if }b_s^\pi\neq 0,\\
\mbox{any distribution }, &\mbox{if }b_s^\pi=0.
\end{cases}
\end{align*}

Then it is clear that $\pi(a|s)=\xi(a|s)b_s^\pi$ for $a\notin \mathcal{A} _{s}^{*}$.
A direct calculation yields that

\begin{align*}
V^{\ast}(\rho )-V^{\pi}(\rho )&=-\left( V^{\pi}(\rho )-V^{\ast}(\rho ) \right)
\\
&\overset{(a)}{=}-\frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{\pi}}\mathbb{E} _{a\sim \pi \left( \cdot |s \right)}\left[ A^{\ast}(s,a) \right]
\\
&\overset{(b)}{=}-\frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ \sum_{a\notin \calA _{s}^{\ast}}{\pi}(a|s)A^{\ast}(s,a) \right\}
\\
&=\frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ \sum_{a\notin \calA _{s}^{\ast}}{\pi}(a|s)\left( V^{\ast}(s)-Q^{\ast}(s,a) \right) \right\}
\\
=\frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ V^*\left( s \right) \sum_{a\notin \calA _{s}^{*}}{\pi \left( a|s \right)}-\sum_{a\notin \calA _{s}^{*}}{\pi \left( a|s \right) Q^{\ast}(s,a)} \right\}
\\
&{=}\frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ \left( V^*\left( s \right) -\mathbb{E} _{a\sim \xi ^{\pi}\left( \cdot |s \right)}\{ Q^{\ast}(s,a) \right\}) b_{s}^{\pi} \right\}
\\
&{\le} \frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ \left( V^*\left( s \right) -\widehat{V}^*\left( s \right) \right) b_{s}^{\pi} \right\}
\\
&\le \frac{\underset{s}{\max}\left\{ V^*\left( s \right) -\widehat{V}^*\left( s \right) \right\}}{1-\gamma}\cdot \mathbb{E} _{s\sim d_{\rho}^{\pi}}\left\{ b_{s}^{\pi} \right\},
\end{align*}

where step (a) follows from Lemma <ref>, step (b) is due to the fact that $A^\ast(s,a)=0$ for any $a\in\calA_s^\ast$, and $\widehat{V}^*\left( s \right) :=\underset{a\notin \calA _{s}^{*}}{\min}\,Q^*\left( s,a \right)$, as defined in Section <ref> (when $\calA=\calA_s^*$, $\widehat{V}^*\left( s \right)$ is understood as 0).

§.§ Proof of Lemma <ref>

Notice that

\begin{align*}
\pi^{k+1}(a|s) &= (\theta_{s,a}^{k+1} )^2\\
&=\frac{\left( \theta_{s,a}^k + \eta g_{s,a}^k \right)^2}{\twonorm{\vtheta_s^k + \eta \vg_s^k}^2}\\
&=\frac{\left( \theta_{s,a}^k + \eta g_{s,a}^k \right)^2}{\twonorm{\vtheta_s^k}^2 + \eta^2 \twonorm{\vg_s^k}^2}\\
&=\theta_{s,a}^k  \frac{\left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2}{\twonorm{\vtheta_s^k}^2 + \eta^2 \twonorm{\vg_s^k}^2}\\
&=\pi^k(a|s)\cdot \frac{\left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2}{ 1+ \eta^2 \twonorm{\vg_s^k}^2}, \numberthis\label{eq 6}
\end{align*}

where the third line is due to $\la \vtheta_s^k, \vg_s^k\ra= 0$ and the last line is due to $\twonorm{\vtheta_s^k}=1$.

\begin{align*}
\sum_a{\pi ^{k+1}}(a|s)A^k(s,a)=\frac{\sum_a{\pi ^k}(a|s)\cdot \left( 1+\eta g_{s,a}^{k}/\theta _{s,a}^{k} \right) ^2\cdot A^k(s,a)}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}.\numberthis \label{eq 1}
\end{align*}

A direct computation yields that

\begin{align*}
\sum_a{\pi ^k}(a|s)\cdot \left( 1+\eta g_{s,a}^{k}/\theta _{s,a}^{k} \right) ^2\cdot A^k(s,a)&=\sum_a{\pi ^k}(a|s)\left( 1+\frac{2\eta}{1-\gamma}d_{\mu}^{k}(s)A^k(s,a) \right) ^2A^k(s,a)
\\
&=\sum_a{\pi ^k}(a|s)\left( 1+\frac{4\eta}{1-\gamma}d_{\mu}^{k}(s)A^k(s,a)+\left( \frac{2\eta}{1-\gamma}d_{\mu}^{k}(s)A^k(s,a) \right) ^2 \right) A^k(s,a)
\\
&=\sum_a{\pi ^k}(a|s)\left( \frac{4\eta}{1-\gamma}d_{\mu}^{k}(s)A^k(s,a)+\left( \frac{2\eta}{1-\gamma}d_{\mu}^{\pi _{\theta}}(s)A^k(s,a) \right) ^2 \right) A^k(s,a)
\\
&=\sum_a{\pi ^k}(a|s)\left( \frac{4\eta}{1-\gamma}d_{\mu}^{k}(s)+\left( \frac{2\eta}{1-\gamma}d_{\mu}^{k}(s) \right) ^2A^k(s,a) \right) (A^k(s,a))^2
\\
&=\frac{4\eta}{1-\gamma}d_{\mu}^{k}(s)\sum_a{\pi ^k}(a|s)\left( 1+\frac{\eta d_{\mu}^{k}(s)}{1-\gamma}A^k(s,a) \right) (A^k(s,a))^2
\\
&\overset{\left( a \right)}{\ge}\frac{4\eta}{1-\gamma}d_{\mu}^{k}(s)\sum_a{\pi ^k}(a|s)\frac{3}{4}(A^k(s,a))^2
\\
&=\frac{3\eta d_{\mu}^{k}(s)}{1-\gamma}\sum_a{\pi ^k}(a|s)(A^k(s,a))^2,\numberthis \label{eq 2}
\end{align*}

where step (a) is due to the following fact, $\eta=\frac{(1-\gamma)^2 \kappa}{4}, \kappa \in(0,1)$ and

\begin{align*}
1+\frac{\eta d_{\mu}^{k}(s)}{1-\gamma}A^k(s,a)&\ge 1-\frac{\eta d_{\mu}^{k}(s)}{1-\gamma}\cdot \frac{1}{1-\gamma}
\\
&\ge 1-\frac{\eta}{(1-\gamma )^2}
\\
&=1-\frac{1}{(1-\gamma )^2}\frac{(1-\gamma )^2\kappa}{4}
\\
\\
\end{align*}

Plugging (<ref>) into (<ref>) yields that

\begin{align*}
\sum_a{\pi ^{k+1}}(a|s)A^k(s,a)\ge \frac{3\eta d_{\mu}^{k}(s)}{1-\gamma}\cdot \frac{\sum_a{\pi ^k}(a|s)(A^k(s,a))^2}{1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}}. \numberthis \label{eq 3}
\end{align*}

Moreover, it can be seen that

\begin{align*}
1+\eta ^2\left\| g_{s}^{k} \right\| _{2}^{2}&=1+\eta ^2\sum_a{(}g_{s,a}^{k})^2
\\
&=1+\eta ^2\sum_a{\left( \frac{2}{1-\gamma}d_{\mu}^{k}(s)\cdot \theta_{s,a}^k\cdot A^k(s,a) \right) ^2}
\\
&=1+\eta ^2\cdot \left( \frac{2}{1-\gamma}d_{\mu}^{k}(s) \right) ^2\sum_a{\left( \theta _{s,a}^{k} \right) ^2}\left( A^k(s,a) \right) ^2
\\
&\le 1+\eta ^2\cdot \left( \frac{2}{1-\gamma}d_{\mu}^{k}(s) \right) ^2\sum_a{\pi ^k}\left( a|s \right) \frac{1}{(1-\gamma )^2}
\\
&=1+\eta ^2\cdot \left( \frac{2}{1-\gamma}d_{\mu}^{k}(s) \right) ^2\frac{1}{(1-\gamma )^2}
\\
&\le 1+\eta ^2\cdot \left( \frac{2}{1-\gamma} \right) ^2\frac{1}{(1-\gamma )^2}
\\
&=1+\frac{(1-\gamma )^4\kappa ^2}{16}\cdot \frac{4}{(1-\gamma )^4}
\\
&=1+\frac{\kappa ^2}{4}. \numberthis \label{eq 4}
\end{align*}

Plugging (<ref>) into (<ref>) yields that

\begin{align*}
\sum_a{\pi ^{k+1}}(a|s)A^k(s,a)&\ge \frac{3\eta d_{\mu}^{k}(s)}{\left( 1-\gamma \right) \left( 1+\frac{\kappa ^2}{4} \right)}\cdot \sum_a{\pi ^k}(a|s)(A^k(s,a))^2
\\
\quad                           &\overset{\left( a \right)}{\ge}\frac{3\eta \tilde{\mu}}{1+\frac{\kappa ^2}{4}}\cdot \sum_a{\pi ^k}(a|s)(A^k(s,a))^2
\\
\quad                           &\overset{\left( b \right)}{=}\frac{3\kappa\tilde{\mu}\left( 1-\gamma \right) ^2}{4+\kappa}\cdot \sum_a{\pi ^k}(a|s)(A^k(s,a))^2, \numberthis \label{SingleStateImprove}
\end{align*}

where step (a) is due to the fact that

\begin{align}
\label{eqD}
d^{k+1}_{\mu}(s) \geq (1-\gamma) \mu(s)\geq (1-\gamma)\min_s \mu(s)=(1-\gamma)\tilde{\mu},
\end{align}

and step (b) is due to  $
\eta =\frac{\left( 1-\gamma \right) ^2\kappa}{4}$. Moreover, by Lemma <ref>, for any  $\rho$,

\begin{align*}
V^{k+1}(\rho )-V^k(\rho )&=\frac{1}{1-\gamma}\sum_s{
d_{\rho}^{k+1}\left( s \right) \sum_a{\pi ^{k+1}\left( a|s \right) A^k\left( s,a \right)}.
}  \numberthis \label{improvement_on_rho}
\end{align*}

Plugging (<ref>) into (<ref>) yields that

\begin{align*}
V^{k+1}(\rho )-V^k(\rho )&\ge \frac{1}{1-\gamma}\mathbb{E} _{s\sim d_{\rho}^{k+1}}\left\{ \frac{3\kappa \tilde{\mu}\left( 1-\gamma \right) ^2}{4+\kappa^2}\cdot \sum_a{\pi ^k}(a|s)(A^k(s,a))^2 \right\}
\\
\quad                      &=\frac{3\kappa \tilde{\mu}\left( 1-\gamma \right)}{4+\kappa^2}\sum_s{d_{\rho}^{k+1}\left( s \right) \sum_a{\pi ^k}(a|s)(A^k(s,a))^2}
\\
\quad                      &\ge \frac{3\kappa \tilde{\mu}\left( 1-\gamma \right)}{4+\kappa^2}\sum_{s\in \mathrm{supp}\left( \rho \right)}{d_{\rho}^{k+1}\left( s \right) \sum_a{\pi ^k}(a|s)(A^k(s,a))^2}
\\
\quad                      &\ge \frac{3\kappa \tilde{\mu}\left( 1-\gamma \right) ^2}{4+\kappa^2}\underset{s\in \mathrm{supp}\left( \rho \right)}{\min}\left\{ \tilde{\rho}\left( s \right) \right\} \sum_{s\in \mathrm{supp}\left( \rho \right)}{\sum_a{\pi ^k}(a|s)(A^k(s,a))^2},
\end{align*}

which completes the proof.

§.§ Proof of Lemma <ref>

A straightforward calculation yields that

\begin{align*}
\pi^{k+1}(a|s) - \pi^k(a|s) &\stackrel{(a)}{=} \pi^k(a|s)\cdot \left( \frac{\left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2}{ 1+ \eta^2 \twonorm{\vg_s^k}^2} -1 \right)\\
&= \pi^k(a|s)\cdot \left( \frac{\left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2 - 1 - \eta^2 \twonorm{\vg_s^k}^2}{ 1+ \eta^2 \twonorm{\vg_s^k}^2} \right)\\
&\stackrel{(b)}{=}\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left( A^k(s,a) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left(  (A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}\right)\right),
\end{align*}

where step (a) is due to (<ref>) and step (b) is due to

\begin{align*}
\left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2 - 1 - \eta^2 \twonorm{\vg_s^k}^2 &= 2\eta \frac{ g_{s,a}^k }{\theta_{s,a}^k }  + \eta^2 \left( \frac{ g_{s,a}^k }{\theta_{s,a}^k }\right)^2 - \eta^2 \sum_{a'\in\calA} (g_{s,a'}^k)^2\\
&=2\eta \cdot  \frac{2d_{\mu}^{k}(s) \cdot  A^{k}(s,a) }{1-\gamma} + \eta^2 \left( \frac{2d_{\mu}^{k}(s) \cdot  A^{k}(s,a) }{1-\gamma}\right)^2 - \eta^2 \sum_{a'\in\calA} (\theta_{s,a'}^k)^2\left( \frac{2d_{\mu}^{k}(s) \cdot  A^{k}(s,a') }{1-\gamma}\right)^2\\
&= \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left( A^k(s,a) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left(  (A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}\right)\right). %\numberthis \label{eq12}
\end{align*}

§.§ Proof of Lemma <ref>

Since if $s\notin\widetilde{S}$ (i.e. there does not exist non-optimal actions at $s$), $b_s^k=b_s^{k+1}=0$ and the lemma holds trivially, we will restrict our attention to $s\in\widetilde{S}$. In this case, by the first claim of Lemma <ref>  (whose proof does not rely on Lemma <ref>), we always have $0<b_s^k<1$. To prepare for the proof, we define the two auxiliary policies associated with $\pi^k$ as follows:

\begin{align*}
\begin{cases}
\psi^k\left( \cdot |s \right) =\frac{\pi^k \left( \cdot |s \right)}{1-b_{s}^{k}}\mathbf{1}\left[ \cdot \in \mathcal{A} _{s}^{*} \right],\\
\xi^k\left( \cdot |s \right) =\frac{\pi^k \left( \cdot |s \right)}{b_{s}^{k}}\mathbf{1}\left[ \cdot \notin \mathcal{A} _{s}^{*} \right].\\
\end{cases}
\end{align*}

It follows immediately that $\pi^k(\cdot|s)=(1-b_s^k)\psi^k(\cdot|s)+b_s^k\xi^k(\cdot|s)$.

By the definition of $b_s^k$, we have

\begin{align*}
b_s^k - b_s^{k+1} &=\sum_{a\notin\calA_s^\ast} \left( \pi^k(a|s) - \pi^{k+1}(a|s) \right)\\
&=\sum_{a\in\calA_s^\ast} \left( \pi^{k+1}(a|s) - \pi^k(a|s)  \right).
\end{align*}

By Lemma <ref>, one has

\begin{align}
\label{diff pi}
\pi^{k+1}(a|s) - \pi^k(a|s) &=\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left( A^k(s,a) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left(  (A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}\right)\right).
\end{align}

Below we will derive the expressions for $A^k(s,a)$ and $(A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}$ based on $b^k_s$.

* Derivation of  $A^k(s,a)$.

Let $\delta_s^k = V^\ast(s) - V^k(s)$ for any $s\in\calS$. Then one has

\begin{align*}
Q^k(s,a) &=\E[s'\sim P(\cdot|s,a)]{ r(s,a) + \gamma V^k(s')} \\
&=\E[s'\sim P(\cdot|s,a)]{ r(s,a) + \gamma V^\ast(s') + \gamma\left( V^k(s') - V^\ast(s') \right)} \\
&=\E[s'\sim P(\cdot|s,a)]{ r(s,a) + \gamma V^\ast(s') - \gamma \delta_{s'}^k} \\
&=Q^\ast(s,a) - \gamma  \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} ,\numberthis\label{eq Q}\\
V^k(s)&=\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ Q^k(s,a') \right\}
\\
\quad       &=\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ Q^{\ast}(s,a') \right\} -\gamma \mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right) ,s'\sim P\left( \cdot |s,a' \right)}\left\{ \delta _{s'}^{k} \right\}
\\
\quad       &\overset{\left( a \right)}{=}\left( 1-b_{s}^{k} \right) \mathbb{E} _{a'\sim \psi ^k\left( \cdot |s \right)}\left\{ Q^{\ast}\left( s,a' \right) \right\} +b_{s}^{k}\mathbb{E} _{a'\sim \xi ^k\left( \cdot |s \right)}\left\{ Q^{\ast}\left( s,a' \right) \right\} -\gamma \mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right) ,s'\sim P\left( \cdot |s,a' \right)}\left\{ \delta _{s'}^{k} \right\}
\\
\quad       &\overset{\left( b \right)}{=}\left( 1-b_{s}^{k} \right) V^*\left( s \right) +b_{s}^{k}\mathbb{E} _{a'\sim \xi ^k\left( \cdot |s \right)}\left\{ Q^{\ast}\left( s,a' \right) \right\} -\gamma \mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right) ,s'\sim P\left( \cdot |s,a' \right)}\left\{ \delta _{s'}^{k} \right\}
\\
\quad       :&\overset{\left( c \right)}{=}\left( 1-b_{s}^{k} \right) V^*\left( s \right) +b_{s}^{k}\cdot e_{s}^{k}-\gamma \mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right) ,s'\sim P\left( \cdot |s,a' \right)}\left\{ \delta _{s'}^{k} \right\}
\\
\quad       &=V^*\left( s \right) - b_{s}^{k}\left( V^*\left( s \right) -e_{s}^{k} \right) -\gamma \mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right) ,s'\sim P\left( \cdot |s,a' \right)}\left\{ \delta _{s'}^{k} \right\}, \numberthis\label{eq V}
\end{align*}

where we have used the definition $b_s^k = \sum_{a\notin \calA_s^\ast} \pi^k(a|s)$, step (a) follows from the definitions of $\psi^k$ and $\xi^k$, step (b) holds since $Q^\ast(s,a') = V^\ast(s)$ for any $a\in\calA_s^\ast$ and $\text{supp}(\psi^k(\cdot|s)) \in \calA^*_s$, and we define $e_s^k = \E[a' \sim \xi^k(\cdot|s)]{Q^\ast(s,a')}$ in  step (c). Therefore, we have

\begin{align*}
A^{k}(s,a) &= Q^k(s,a) - V^k(s)\\
&=Q^\ast(s,a) - \gamma  \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}  - \left(V^\ast(s) - b_s^k (V^\ast(s) - e_s^k) - \gamma  \E[s'\sim P(\cdot|s,a'), a'\sim\pi^k(\cdot|s)]{ \delta_{s'}^k}  \right)\\
&=A^\ast(s,a) + b_s^k (V^\ast(s) - e_s^k) +\underbrace{ \gamma  \left( \E[a'\sim\pi^k(\cdot|s),s'\sim P(\cdot|s,a')]{ \delta_{s'}^k}  - \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}   \right) }_{\ell_{s,a}^k}\\
:&=A^\ast(s,a) + b_s^k (V^\ast(s) - e_s^k) + \ell_{s,a}^k.
\end{align*}

Furthermore, for any $a\in\calA_s^\ast$, one has

\begin{align}
\label{eq 10}
A^{k}(s,a) =b_s^k (V^\ast(s) - e_s^k) + \ell_{s,a}^k.
\end{align}

By the definition of $\ell_{s,a}^k$, it can be seen that

\begin{align*}
\E[a\sim \pi^k(\cdot|s)]{\ell_{s,a}^k} &=\gamma   \E[a\sim \pi^k(\cdot|s)]{ \left( \E[s'\sim P(\cdot|s,a'), a'\sim\pi^k(\cdot|s)]{ \delta_{s'}^k}  - \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}   \right)  }\\
&=\gamma   \E[a\sim \pi^k(\cdot|s)]{ \left( \E[s'\sim P(\cdot|s)]{ \delta_{s'}^k}  - \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}   \right)  }\\
\end{align*}

* Derivation of $(A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}$.

A direct computation yields that

\begin{align*}
&(A^k(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^k(s,a'))^2 }\\
&= \left( Q^k(s,a) - V^k(s) \right)^2 - \E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a') - V^k(s) \right)^2}\\
&= \left( Q^k(s,a)  \right)^2 - 2 Q^k(s,a) \cdot V^k(s) + \left(V^k(s)\right)^2 -  \E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 - 2 Q^k(s,a') \cdot V^k(s) + \left(V^k(s)\right)^2}\\
&= \left( Q^k(s,a)  \right)^2 - 2 Q^k(s,a) \cdot V^k(s) + \left(V^k(s)\right)^2 -  \E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 }\\
&\quad + 2 \E[a'\sim \pi^k(\cdot|s)]{Q^k(s,a') }\cdot V^k(s)- \left(V^k(s)\right)^2\\
&= \left( Q^k(s,a)  \right)^2 -\E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 }- 2 Q^k(s,a) \cdot V^k(s) + 2 (V^k(s))^2\\
&= \left( Q^k(s,a)  \right)^2 -\E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 }- 2 \left( Q^k(s,a)- V^k(s)\right) \cdot V^k(s) \\
&= \left( Q^k(s,a)  \right)^2 -\E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 }- 2A^k(s,a)\cdot V^k(s). \numberthis\label{eq 7}
\end{align*}

For the first term in (<ref>), using (<ref>) yields that

\begin{align*}
&\left( Q^k(s,a)  \right)^2 -\E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 } \\
&= \left(Q^\ast(s,a) - \gamma  \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} \right)^2 - \E[a'\sim \pi^k(\cdot|s)]{\left(Q^\ast(s,a') - \gamma  \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}\right)^2}\\
&=\left(Q^\ast(s,a) \right)^2 - \E[a'\sim \pi^k(\cdot|s)]{\left(Q^\ast(s,a')  \right)^2}\\
&\quad + \gamma^2 \left( \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} \right)^2 -  \gamma^2\E[a'\sim \pi^k(\cdot|s)]{\left( \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}\right)^2}\\
&\quad + 2\gamma \E[a'\sim \pi^k(\cdot|s)]{ Q^\ast(s,a') \cdot \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} } - 2\gamma Q^\ast(s,a) \cdot \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}\\
:&=\left(Q^\ast(s,a) \right)^2 - \E[a'\sim \pi^k(\cdot|s)]{\left(Q^\ast(s,a')  \right)^2} + \tilde{\ell}_{s,a}^k. \numberthis \label{eq 8}
\end{align*}

By the definitions of $\psi^k$ and $\xi^k$, one has

\begin{align*}
\mathbb{E} _{a'\sim \pi ^k\left( \cdot |s \right)}\left\{ \left( Q^{\ast}(s,a') \right) ^2 \right\} &=\left( 1-b_{s}^{k} \right) \mathbb{E} _{a'\sim \psi ^k\left( \cdot |s \right)}\left\{ \left( Q^{\ast}(s,a') \right) ^2 \right\} +b_{s}^{k} \cdot \mathbb{E} _{a'\sim \xi ^k\left( \cdot |s \right)}\left\{ \left( Q^{\ast}(s,a') \right) ^2 \right\}
\\
\quad                             &\overset{(a)}{:=}\left( 1-b_{s}^{k} \right) \mathbb{E} _{a'\sim \psi ^k\left( \cdot |s \right)}\left\{ \left( V^*\left( s \right) \right) ^2 \right\} +b_{s}^{k}\cdot \left( d_{s}^{k} \right) ^2
\\
\quad                              &=\left( 1-b_{s}^{k} \right) \left( V^*\left( s \right) \right) ^2+b_{s}^{k}\cdot \left( d_{s}^{k} \right)^2,\numberthis \label{eq 9}
\end{align*}

where we define $
d_{s}^{k}:=\sqrt{\mathbb{E} _{a'\sim \xi ^k\left( \cdot |s \right)}\left\{ \left( Q^{\ast}(s,a') \right) ^2 \right\}}$ in step (a).
Plugging (<ref>) and (<ref>) into (<ref>) yields that for any $(s,a)$,

\begin{align*}
&(A^k(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^k(s,a'))^2 }\\
&= \left( Q^k(s,a)  \right)^2 -\E[a'\sim \pi^k(\cdot|s)]{\left( Q^k(s,a')  \right)^2 }- 2A^k(s,a)\cdot V^k(s)\\
&= \left(Q^\ast(s,a) \right)^2 - \E[a'\sim \pi^k(\cdot|s)]{\left(Q^\ast(s,a')  \right)^2} + \tilde{\ell}_{s,a}^k - 2A^k(s,a)\cdot V^k(s)\\
&=\left(Q^\ast(s,a) \right)^2 - (1-b_s^k) \left(V^\ast(s)  \right)^2 - b_s^k\cdot (d_s^k)^2 + \tilde{\ell}_{s,a}^k - 2A^k(s,a)\cdot V^k(s)\\
&= \left(Q^\ast(s,a) \right)^2 -  \left(V^\ast(s)  \right)^2 + b_s^k\cdot\left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right)+ \tilde{\ell}_{s,a}^k - 2A^k(s,a)\cdot V^k(s).
\end{align*}

Moreover, for any $a\in\calA_s^\ast$, one has

\begin{align}
\label{eq 11}
&(A^k(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^k(s,a'))^2 } \notag\\
&=b_s^k\cdot\left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right)+ \tilde{\ell}_{s,a}^k - 2A^k(s,a)\cdot V^k(s)\notag\\
&= b_s^k\cdot\left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right)+ \tilde{\ell}_{s,a}^k - 2\left(  b_s^k (V^\ast(s) - e_s^k) + \ell_{s,a}^k\right) \cdot V^k(s)\notag\\
&=b_s^k\cdot\left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2 - 2  (V^\ast(s) - e_s^k) \cdot V^k(s) \right)+ \tilde{\ell}_{s,a}^k - 2 \ell_{s,a}^k \cdot V^k(s).
\end{align}

Plugging (<ref>) and (<ref>) into (<ref>) yields that

\begin{align*}
&\pi^{k+1}(a|s) - \pi^k(a|s) \\
&=\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left( A^k(s,a) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left(  (A^{k}(s,a))^2 - \E[a'\sim \pi^k(\cdot|s)]{(A^{k}(s,a'))^2}\right)\right)\\
&= \frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left( b_s^k (V^\ast(s) - e_s^k) + \ell_{s,a}^k \right)\\
&\quad +   \frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot\frac{4\eta d_{\mu}^k(s)}{1-\gamma} \cdot \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left( b_s^k\cdot\left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2 - 2  (V^\ast(s) - e_s^k) \cdot V^k(s) \right)+ \tilde{\ell}_{s,a}^k - 2 \ell_{s,a}^k \cdot V^k(s)\right) \\
&= \frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot\frac{4\eta d_{\mu}^k(s)}{1-\gamma}  \cdot  b_s^k (V^\ast(s) - e_s^k)  - \frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot\frac{4\eta d_{\mu}^k(s)}{1-\gamma} \frac{\eta d_{\mu}^k(s)}{1-\gamma} \cdot b_s^k\cdot 2  (V^\ast(s) - e_s^k) \cdot V^k(s) \\
&\quad +\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \cdot \ell_{s,a}^k +  \frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot\frac{4\eta d_{\mu}^k(s)}{1-\gamma} \frac{\eta d_{\mu}^k(s)}{1-\gamma} \left( b_s^k\cdot\left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right)+ \tilde{\ell}_{s,a}^k - 2 \ell_{s,a}^k \cdot V^k(s)\right) \\
&=\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot\frac{4\eta d_{\mu}^k(s)}{1-\gamma}  \cdot  b_s^k \cdot \left[ (V^\ast(s) - e_s^k)  \left( 1 - \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s)\right) + \frac{\eta d_{\mu}^k(s)}{1-\gamma}  \left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right) \right]\\
&\quad + \frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot \frac{4\eta d_{\mu}^k(s)}{1-\gamma} \left[ \ell_{s,a}^k \left(1- \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s) \right) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \cdot \tilde{\ell}_{s,a}^k  \right]\\
:&=\frac{ \pi^k(a|s) }{1+ \eta^2 \twonorm{\vg_s^k}^2} \cdot\frac{4\eta d_{\mu}^k(s)}{1-\gamma}  \cdot  \left( b_s^k \cdot z_s^k +  \phi_{s,a}^k \right)
\end{align*}

for any $a\in\calA_s^\ast$. Thus,

\begin{align*}
b_s^k - b_s^{k+1} &=\sum_{a\in\calA_s^\ast} \left( \pi^{k+1}(a|s) - \pi^k(a|s)  \right)\\
&=\frac{4\eta d_{\mu}^k(s)}{1-\gamma}  \cdot  \frac{1}{1+ \eta^2 \twonorm{\vg_s^k}^2} \sum_{a\in\calA_s^\ast} \pi^k(a|s) \left( b_s^k \cdot z_s^k +  \phi_{s,a}^k \right) \\
&=\frac{4\eta d_{\mu}^k(s)}{1-\gamma}  \cdot  \frac{1}{1+ \eta^2 \twonorm{\vg_s^k}^2} \left( (1-b_s^k)b_s^k \cdot z_s^k + \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right).\numberthis\label{eqB}
\end{align*}

Next we will show

\begin{align*}
T_s:&= (1-b_s^k)b_s^k \cdot z_s^k + \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \\
&\geq  (1-b_s^k)b_s^k \cdot z_s^k - \left| \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right|.\numberthis\label{eqT}
\end{align*}

Recall the definitions of $\phi_{s,a}^k,  \ell_{s,a}^k , \tilde{\ell}_{s,a}^k$:

\begin{align*}
\phi_{s,a}^k &= \ell_{s,a}^k \left(1- \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s) \right) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \cdot \tilde{\ell}_{s,a}^k,\\
\ell_{s,a}^k &=\gamma  \left( \E[s'\sim P(\cdot|s,a'), a'\sim\pi^k(\cdot|s)]{ \delta_{s'}^k}  - \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}   \right),\\
\tilde{\ell}_{s,a}^k &= \gamma^2 \left( \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} \right)^2 -  \gamma^2\E[a'\sim \pi^k(\cdot|s)]{\left( \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}\right)^2}\\
&\quad + 2\gamma \E[a'\sim \pi^k(\cdot|s)]{ Q^\ast(s,a') \cdot \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} } - 2\gamma Q^\ast(s,a) \cdot \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}.
\end{align*}

We have

\begin{align*}
\sum_{a\in\calA} \pi^k(a|s) \ell_{s,a}^k  &= 0,\\
\sum_{a\in\calA} \pi^k(a|s) \tilde{\ell}_{s,a}^k&=0,\\
\sum_{a\in\calA} \pi^k(a|s)  \phi_{s,a}^k  &=0.
\end{align*}

It follows that

\begin{align*}
\left| \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right| &\leq  \sum_{a\in\calA_s^\ast} \pi^k(a|s)   \left| \phi_{s,a}^k \right|\leq \sum_{a\in\calA_s^\ast} \pi^k(a|s)   \cdot \max_{s,a}\left| \phi_{s,a}^k \right| =(1-b_s^k)  \max_{s,a}\left| \phi_{s,a}^k \right|
\end{align*}

\begin{align*}
\left| \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right| & =\left| \sum_{a\in\calA}\pi^k(a|s)  \phi_{s,a}^k -  \sum_{a\notin\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right| \\
&=\left| \sum_{a\notin\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right| \\
&\leq b_s^k \cdot \max_{s,a}\left| \phi_{s,a}^k \right| . \numberthis \label{eqPhi}
\end{align*}

Combining them together yields that

\begin{align}
\label{eq14}
\left| \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right|  \leq \min(b_s^k, 1-b_s^k)\cdot \max_{s,a}\left|\phi_{s,a}^k \right| .
\end{align}

On the other hand, one has

\begin{align}
\label{eq15}
(1-b_s^k)\cdot b_s^k &=\min(1-b_s^k, b_s^k)\cdot\max (1-b_s^k, b_s^k)\\
&\geq \frac{1}{2}\min(1-b_s^k, b_s^k),
\end{align}

where the second line is due to the fact that $\max(1-x,x)\geq 1/2$ for any $x\in[0,1]$. Plugging (<ref>) and (<ref>) into (<ref>) yields that

\begin{align*}
T_s&\geq  (1-b_s^k)b_s^k \cdot z_s^k - \left| \sum_{a\in\calA_s^\ast} \pi^k(a|s)  \phi_{s,a}^k \right|\\
&\geq \min(1-b_s^k, b_s^k)\left( \frac{z_s^k}{2} -\max_{s,a}\left|\phi_{s,a}^k \right|  \right). \numberthis\label{eqT2}
\end{align*}

In what follows, we will control $z_s^k$ and $|\phi_{s,a}^k |$, respectively.

* Bounding $z_s^k$.

Recall the definition of

\begin{align*}
z_s^k &= (V^\ast(s) - e_s^k)  \left( 1 - \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s)\right) + \frac{\eta d_{\mu}^k(s)}{1-\gamma}  \left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right).
\end{align*}

We bound each term on the right side separately.

* Bounding $V^\ast(s) - e_s^k$. By the definitions of $e_s^k,d_s^k$ and the Jensen inequality, one has

\begin{align*}
\widehat{V}^*(s) \le e_s^k & = \E[a' \sim \xi^k(\cdot|s)]{Q^*(s,a')}
\le \sqrt{\mathbb{E} _{a'\sim \xi ^k\left( \cdot |s \right)}\left\{ \left( Q^{\ast}(s,a') \right) ^2 \right\}}=d_{s}^{k}
\le  \widetilde{V}^*(s),
\end{align*}

which implies that  $V^\ast(s) - e_s^k \ge V^\ast(s) - d_s^k \ge V^\ast(s) - \widetilde{V}^*(s) > 0$.

* Bounding $1 - \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s)$. A direct computation yields that

\begin{align*}
1 - \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s)& \geq  1 - \frac{2}{1-\gamma}\cdot \frac{(1-\gamma)^2\kappa}{4}\cdot \frac{1}{1-\gamma} =1-\frac{\kappa}{2},
\end{align*}

where we have used the facts  $V^k(s)\leq \frac{1}{1-\gamma}, d_{\mu}^k(s)\leq 1$, and $\eta = \frac{(1-\gamma)^2 \kappa}{4}$.

* Bounding $ \frac{\eta d_{\mu}^k(s)}{1-\gamma}$. One has

\begin{align*}
\frac{\eta d_{\mu}^k(s)}{1-\gamma} &\geq \frac{1}{1-\gamma}\cdot \frac{(1-\gamma)^2\kappa}{4}\cdot (1-\gamma)\tilde{\mu} =\frac{(1-\gamma)^2\kappa\tilde{\mu} }{4}.
\end{align*}

Combining them together, we have

\begin{align*}
z_s^k &= (V^\ast(s) - e_s^k)  \left( 1 - \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s)\right) + \frac{\eta d_{\mu}^k(s)}{1-\gamma}  \left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right)\\
&\geq (V^\ast(s) - d_s^k)  \left( 1 - \frac{\kappa}{2}\right) + \frac{(1-\gamma)^2\kappa\tilde{\mu} }{4}\cdot \left(  \left(V^\ast(s)  \right)^2  - (d_s^k)^2  \right)\\
&= (V^\ast(s) - d_s^k)  \left(  1 - \frac{\kappa}{2} + \frac{(1-\gamma)^2\kappa\tilde{\mu} }{4}\cdot \left( V^\ast(s) + d_s^k \right) \right)\\
&\geq (V^\ast(s) - \widetilde{V}^\ast(s)) \left(  1 - \frac{\kappa}{2} + \frac{(1-\gamma)^2\kappa\tilde{\mu} }{4}\cdot \left( V^\ast(s) + d_s^k \right) \right)
\\
&\ge \underset{s\in \widetilde{S}}{\min}\,\,\left( V^*\left( s \right) -\widetilde{V}^*\left( s \right) \right)  \left( 1-\frac{\kappa}{2}+\frac{(1-\gamma )^2\kappa \tilde{\mu}}{4}\cdot \left( V^{\ast}(s)+\widehat{V}^\ast(s) \right) \right)
\\
&\ge \underset{s\in \widetilde{S}}{\min}\,\,\left( V^*\left( s \right) -\widetilde{V}^*\left( s \right) \right)  \left( 1-\frac{\kappa}{2}+\frac{(1-\gamma )^2\kappa \tilde{\mu}}{4}\cdot \min_{s\in\calS} \left( V^{\ast}(s)+\widehat{V}^\ast(s) \right) \right)
\\
&:= M_1(\kappa,\gamma)     \numberthis \label{eqM}
\end{align*}

* Bounding $|\phi_{s,a}^k |$. By the definition, we have

\begin{align*}
|\phi_{s,a}^k |  &= \left| \ell_{s,a}^k \left(1- \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s) \right) + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \cdot \tilde{\ell}_{s,a}^k \right|\\
&\leq \left| \ell_{s,a}^k \right| \cdot \left|  1- \frac{2\eta d_{\mu}^k(s)}{1-\gamma} \cdot  V^k(s) \right| + \frac{\eta d_{\mu}^k(s)}{1-\gamma} \cdot \left|\tilde{\ell}_{s,a}^k \right|\\
&\leq \left| \ell_{s,a}^k \right| + \frac{\eta}{1-\gamma} \cdot \left|\tilde{\ell}_{s,a}^k \right|.
\end{align*}

We will control $ \left| \ell_{s,a}^k \right| $ and $\left|\tilde{\ell}_{s,a}^k \right|$, respectively.

* Bounding $ \left| \ell_{s,a}^k \right| $. Recall the definition

\begin{align*}
\ell_{s,a}^k =\gamma  \left( \E[s'\sim P(\cdot|s,a'), a'\sim\pi^k(\cdot|s)]{ \delta_{s'}^k}  - \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}   \right) .
\end{align*}

A direct computation yields that

\begin{align*}
\left| \ell_{s,a}^k \right|  &=\gamma \left| \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}  - \E[a'\sim\pi^k(\cdot|s)]{\E[s'\sim P(\cdot|s,a')]{ \delta_{s'}^k} }\right|\\
&\leq \gamma \left| \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}   \right|\\
&\leq \gamma \E[s'\sim P(\cdot|s,a)]{ \left|  \delta_{s'}^k \right|}  \\
&=\gamma \E[s'\sim P(\cdot|s,a)]{ \left|  V^\ast(s') - V^k(s') \right|}  \\
&\leq \gamma\max_s (V^\ast(s) - V^k(s)).
\end{align*}

* Bounding $\left|\tilde{\ell}_{s,a}^k \right|$. Similarly, one has

\begin{align*}
\left|\tilde{\ell}_{s,a}^k \right| &\leq \gamma^2 \left|  \left( \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} \right)^2 - \E[a'\sim \pi^k(\cdot|s)]{\left( \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}\right)^2}\right|\\
&\quad + 2\gamma \left| \E[a'\sim \pi^k(\cdot|s)]{ Q^\ast(s,a') \cdot \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k} } - Q^\ast(s,a) \cdot \E[s'\sim P(\cdot|s,a)]{ \delta_{s'}^k}\right|\\
&\leq \gamma^2 \max_s (V^\ast(s) - V^k(s))^2 + 2\gamma V^\ast(s)\cdot \max_s (V^\ast(s) - V^k(s))\\
&\leq \left( \gamma^2 \cdot \max_s (V^\ast(s) - V^k(s)) +2\gamma \cdot \frac{1}{1-\gamma} \right)\cdot \max_s (V^\ast(s) - V^k(s))\\
&\leq \left( \gamma^2 \cdot \max_s (V^\ast(s) ) +2\gamma \cdot \frac{1}{1-\gamma} \right)\cdot \max_s (V^\ast(s) - V^k(s))\\
&\leq \left( \gamma^2 \cdot \frac{1}{1-\gamma}+2\gamma \cdot \frac{1}{1-\gamma} \right)\cdot \max_s (V^\ast(s) - V^k(s))\\
&\leq \frac{\gamma^2+2\gamma}{1-\gamma}\max_s (V^\ast(s) - V^k(s)).
\end{align*}

Combining them together, we have

\begin{align*}
|\phi_{s,a}^k |  &\leq \left| \ell_{s,a}^k \right| + \frac{\eta}{1-\gamma} \cdot \left|\tilde{\ell}_{s,a}^k \right|\\
&\leq \left( \gamma + \frac{\eta}{1-\gamma}  \frac{ \gamma^2+2\gamma}{1-\gamma} \right)\max_s (V^\ast(s) - V^k(s))\\
&\leq \left( \gamma + \frac{\eta}{1-\gamma}  \frac{ 3\gamma}{1-\gamma} \right)\max_s (V^\ast(s) - V^k(s))\\
&=\left( \gamma + \frac{(1-\gamma)^2\kappa}{4}\frac{1}{1-\gamma}  \frac{ 3\gamma}{1-\gamma} \right)\max_s (V^\ast(s) - V^k(s))\\
&\leq 2\gamma \max_s (V^\ast(s) - V^k(s)).\numberthis\label{eqM2}
\end{align*}

Plugging (<ref>) and (<ref>) into (<ref>) yields that

\begin{align}
T_s&\geq \min(1-b_s^k, b_s^k)\left( \frac{z_s^k}{2} -\max_{s,a}\left|\phi_{s,a}^k \right|  \right)
\label{lower_bound_of_t_for_all_s}
\\
&\geq \min(1-b_s^k, b_s^k)\left( \frac{1}{2} M_1(\kappa,\gamma) -2\gamma \max_s (V^\ast(s) - V^k(s)) \right).  \label{lower_bound_of_t_for_s_in_tilde_S}
\end{align}

Submitting it into (<ref>) completes the proof.

§.§ Proof of Lemma <ref>

Firstly, we show that $1- b_s^k >0$.
Recall that

\begin{align*}
g_{s,a}^k= \frac{2}{1-\gamma} d_{\mu}^{\pi^k}(s)  \theta_{s,a}^k A^{k}(s,a) \text{ and } \vtheta_s^{k+1} = \frac{\vtheta_s^k + \eta \vg_s^k}{\twonorm{\vtheta_s^k + \eta \vg_s^k }}\text{ for }s\in\calS.
\end{align*}

For any state $s\in\calS$, a direct computation yields that

\begin{align*}
\pi^{k+1}(a|s) &= \pi^k(a|s)\cdot \frac{\left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2}{ 1+ \eta^2 \twonorm{\vg_s^k}^2} \\
&= \frac{\pi^k(a|s)}{ 1+ \eta^2 \twonorm{\vg_s^k}^2} \left( 1+ \eta g_{s,a}^k /\theta_{s,a}^k \right)^2\\
&\geq \frac{\pi^k(a|s)}{1+\eta^2 \twonorm{\vg_s^k}^2} \left( 1 + \frac{4\eta}{1-\gamma} d_{\mu}^k(s)    A^{k}(s,a) \right)\\
&\geq \frac{\pi^k(a|s)}{1+\eta^2 \twonorm{\vg_s^k}^2} \left( 1 -\frac{4\eta}{1-\gamma} d_{\mu}^k(s)   \left| A^{k}(s,a)\right| \right)\\
&\stackrel{(a)}{\geq}\frac{\pi^k(a|s)}{1+\eta^2 \twonorm{\vg_s^k}^2} \left( 1 -\frac{4\eta}{(1-\gamma)^2}  \right)\\
&\stackrel{(b)}{=}\frac{\pi^k(a|s)}{1+\eta^2 \twonorm{\vg_s^k}^2} \left( 1 -\kappa \right),
\end{align*}

where step (a) follows from $d_{\mu}^k\leq 1$ and $|A^{k}(s,a)|\leq \frac{1}{1-\gamma}$ and step (b) is due to $\eta = \frac{(1-\gamma)^2\kappa}{4}$. Since $\pi^0(a|s)>0$, it can be seen that $\pi^k(a|s)>0$ for all $k\geq 1$. Thus we have

\begin{align*}
1-b_s^k =1 - \sum_{a\notin \calA_s^\ast} \pi^k(a|s) =  \sum_{a\in \calA_s^\ast} \pi^k(a|s) >0
\end{align*}

for all $k\geq 0$. Moreover, Lemma <ref> implies that the sequence $\{b_s^k\}_{k\geq k_0}$ is nonincreasing when $
\underset{s\in \mathcal{S}}{\max}\left( V^*\left( s \right) -V^k\left( s \right) \right)$ is sufficiently small. Thus by Theorem <ref>, one can conclude that  there exist a constant $k_0$ such that $\{b_s^k\}_{k\geq k_0}$ is nonincreasing for $k\ge k_0$ and thus we have $\lambda := \underset{k\ge0}{\inf} \left\{ \underset{ s\in\calS}{\min} (1-b_s^k) \right\} >0$.

§ DISCUSSION

In this paper, we introduce the Hadamard parametrization into the policy gradient algorithm and the global linear convergence of the algorithm is established in the tabular setting provided the exact gradient can be accessed. Compared with the existing convergence results of the PG and NPG methods, it does not require entropy regularization and adaptive step sizes to achieve linear convergence. For future work, it is interesting to study the convergence of the algorithm in the function approximation setting as well as in random sampling setting.  Additionally, it is shown that the algorithm is equivalent to an algorithm   based on the normalized Hadamard parameterization that does not require  spherical projection, which makes it  flexible to use function approximation. Thus we would also like to investigate the performance of the algorithm or the parameterization in solving  real  RL applications.

[1]
Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen
Lee, Jiaji Li, Daniel R. Melamed, Gal Oshri, Oswaldo Ribas, Siddhartha Sen,
and Alex Slivkins.
Making contextual decisions with low technical debt.
arXiv:1606.03966, 2016.

[2]
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.
Optimality and approximation with policy gradient methods in Markov
decision processes.
In Conference on Learning Theory, pages 64–66, 2020.

[3]
Shun-Ichi Amari.
Natural gradient works efficiently in learning.
Neural computation, 10(2):251–276, 1998.

[4]
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw
Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris
Hesse, et al.
Dota 2 with large scale deep reinforcement learning.
arXiv preprint arXiv:1912.06680, 2019.

[5]
Jalaj Bhandari and Daniel Russo.
On the linear convergence of policy gradient methods for finite
In International Conference on Artificial Intelligence and
Statistics, pages 2386–2394, 2021.

[6]
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi.
Fast global convergence of natural policy gradient methods with
entropy regularization.
Operations Research, 70(4):2563–2578, 2022.

[7]
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and
Ed H Chi.
Top-k off-policy correction for a reinforce recommender system.
In Proceedings of the Twelfth ACM International Conference on
Web Search and Data Mining, pages 456–464, 2019.

[8]
Jemin Hwangbo, Joonho Lee, Alexey Dosovitskiy, Dario Bellicoso, Vassilios
Tsounis, Vladlen Koltun, and Marco Hutter.
Learning agile and dynamic motor skills for legged robots.
Science Robotics, 4, 2019.

[9]
Sham Kakade and John Langford.
Approximately optimal approximate reinforcement learning.
In International Conference on Machine Learning, pages
267–274, 2002.

[10]
Sham M Kakade.
A natural policy gradient.
In Advances in Neural Information Processing Systems, page
1531–1538, 2001.

[11]
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and
Siva Theja Maguluri.
On the linear convergence of natural policy gradient algorithm.
In 2021 60th IEEE Conference on Decision and Control (CDC),
pages 3794–3799, 2021.

[12]
Vijay Konda and John Tsitsiklis.
Actor-critic algorithms.
In Advances in Neural Information Processing Systems, page
1008–1014, 2000.

[13]
Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter.
Learning quadrupedal locomotion over challenging terrain.
Science Robotics, 5(47), 2020.

[14]
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans.
Leveraging non-uniformity in first-order non-convex optimization.
In International Conference on Machine Learning, pages
7555–7564, 2021.

[15]
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans.
On the global convergence rates of softmax policy gradient methods.
In International Conference on Machine Learning, pages
6820–6829, 2020.

[16]
Takahiro Miki, Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun,
and Marco Hutter.
Learning robust perceptive locomotion for quadrupedal robots in the
Science Robotics, 7(62), 2022.

[17]
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim
Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi,
et al.
A graph placement methodology for fast chip design.
Nature, 594(7862):207–212, 2021.

[18]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness,
Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg
Ostrovski, et al.
Human-level control through deep reinforcement learning.
Nature, 518(7540):529–533, 2015.

[19]
Martin L Puterman.
Markov decision processes: discrete stochastic dynamic
John Wiley & Sons, 2014.

[20]
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp
Trust region policy optimization.
In International Conference on Machine Learning, pages
1889–1897, 2015.

[21]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
arXiv preprint arXiv:1707.06347, 2017.

[22]
Lior Shani, Yonathan Efroni, and Shie Mannor.
Adaptive trust region policy optimization: Global convergence and
faster rates for regularized MDPs.
In Proceedings of the AAAI Conference on Artificial
Intelligence, pages 5668–5675, 2020.

[23]
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George
Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda
Panneershelvam, Marc Lanctot, et al.
Mastering the game of go with deep neural networks and tree search.
Nature, 529(7587):484–489, 2016.

[24]
Richard S Sutton and Andrew G Barto.
Reinforcement learning: An introduction.
MIT press, 2018.

[25]
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.
Policy gradient methods for reinforcement learning with function
In Advances in Neural Information Processing Systems, page
1057–1063, 1999.

[26]
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha
Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John
Agapiou, Julian Schrittwieser, et al.
Starcraft II: A new challenge for reinforcement learning.
arXiv preprint arXiv:1708.04782, 2017.

[27]
Christopher J. C. H. Watkins and Peter Dayan.
Machine learning, 8:279–292, 1992.

[28]
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist
reinforcement learning.
Machine learning, 8(3):229–256, 1992.

[29]
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang.
Variational policy gradient method for reinforcement learning with
general utilities.
In Advances in Neural Information Processing Systems, pages
4572–4583, 2020.