We consider (stochastic) softmax policy gradient (PG) methods for bandits and tabular Markov decision processes (MDPs). While the PG objective is non-concave, recent research has used the objective's smoothness and gradient domination properties to achieve convergence to an optimal policy. However, these theoretical results require setting the algorithm parameters according to unknown problem-dependent quantities (e.g. the optimal action or the true reward vector in a bandit problem). To address this issue, we borrow ideas from the optimization literature to design practical, principled PG methods in both the exact and stochastic settings. In the exact setting, we employ an Armijo line-search to set the step-size for softmax PG and empirically demonstrate a linear convergence rate. In the stochastic setting, we utilize exponentially decreasing step-sizes, and characterize the convergence rate of the resulting algorithm. We show that the proposed algorithm offers similar theoretical guarantees as the state-of-the art results, but does not require the knowledge of oracle-like quantities. For the multi-armed bandit setting, our techniques result in a theoretically-principled PG algorithm that does not require explicit exploration, the knowledge of the reward gap, the reward distributions, or the noise. Finally, we empirically compare the proposed methods to PG approaches that require oracle knowledge, and demonstrate competitive performance.

§ INTRODUCTION

Policy gradient (PG) methods have played a vital role in the achievements of deep reinforcement learning (RL) [Sutton et al., 1999, Schulman et al., 2017]. Recent theoretical research [Agarwal et al., 2021, Mei et al., 2020, Mei et al., 2021, Bhandari & Russo, 2021, Lan, 2023, Shani et al., 2020] have analyzed PG methods in simplified settings, exploiting the objective's properties to guarantee global convergence to an optimal policy. We focus on softmax policy gradient methods that parameterize the policy using the softmax function, and consider the tabular parameterization for which the number of parameters scales with the number of states and actions. For this class of methods, recent studies have established global convergence rates in both the exact [Mei et al., 2020, Mei et al., 2021, Agarwal et al., 2021] and stochastic (inexact) settings [Mei et al., 2021, Mei et al., 2022, Mei et al., 2023, Yuan et al., 2022].

Specifically, in the exact setting where the rewards and transition probabilities are known, Agarwal et al., 2021 proved that softmax PG can attain asymptotic convergence to an optimal policy despite the non-concave nature of the PG objective. Mei et al., 2020 improve this result and quantify the rate of convergence, proving that softmax PG requires $\gO(\nicefrac{1}{\eps})$ iterations to converge to an $\epsilon$-optimal policy.
Furthermore, in concurrent work, Liu et al., 2024 prove that a fast $\gO(\log \nicefrac{1}{\eps})$ rate can be achieved when using a constant step-size.
On the other hand, when using the tabular parameterization in the exact setting, natural policy gradient (NPG) [Kakade, 2001] and geometry-aware normalized policy gradient (GNPG) [Mei et al., 2021] have been shown to achieve a linear convergence [Bhandari & Russo, 2021, Cen et al., 2022, Lan, 2023, Xiao, 2022] matching policy iteration.

In the stochastic setting where the rewards and transition probabilities are unknown and algorithms require sampling from the environment, [Zhang et al., 2020] first proved that REINFORCE [Williams, 1992, Sutton et al., 1999] converges to a first-order stationary point at an $\tilde{\gO}(\nicefrac{1}{\eps^2})$ rate. Mei et al., 2021, Mei et al., 2022 analyzed the convergence of stochastic softmax PG, proving that it requires $\gO(\nicefrac{1}{\eps^2})$ iterations to converge to an $\eps$-optimal policy. However, the resulting algorithm requires the full gradient (which in turn requires the knowledge of the environment) to set algorithm parameters, making it impractical in the stochastic setting. Similarly, Yuan et al., 2022 proved that stochastic softmax PG converges to an optimal policy at a slower $\tilde{\gO}(\nicefrac{1}{\eps^3})$ rate. However, this result requires knowledge of the optimal action making it vacuous. More recently, Mei et al., 2023 analyzed stochastic Softmax PG in the multi-armed bandit setting and proved that it converges to the optimal arm at an $\gO(\nicefrac{1}{\eps})$ rate. Unfortunately, the algorithm requires knowledge of the reward gap which is typically unknown for bandit problems.

Consequently, while the above convergence results are notable, the methods that stem from them are impractical. The impracticality arises from the methods' dependence on oracle-like knowledge of the environment, which includes factors such as the optimal action [Yuan et al., 2022], reward gap [Mei et al., 2023] and even access to the full gradient [Mei et al., 2021] in stochastic settings. The need for this oracle-like knowledge renders these methods ineffective because they assume access to information sufficient to derive an optimal policy. In this paper, our objective is to design practical softmax PG methods while retaining theoretical convergence guarantees to the optimal policy. We believe that this is an important first step towards developing practical but theoretically-principled PG methods in the general function approximation setting. To this end, we make the following contributions.

Contribution 1: In <ref>, we first consider the exact setting as a test bed for softmax PG. In this setting, theoretical step-sizes that enable convergence to the optimal policy are often too conservative in practice. We present a practical approach by employing an Armijo line-search [Armijo, 1966] to set the step-size for softmax PG. Armijo line-search enables adaptation to the local smoothness of the objective which results in larger step-sizes and improved empirical performance. We prove that in the worst-case, the resulting method achieves a theoretical convergence rate of $\gO(\nicefrac{1}{\eps})$, and we empirically demonstrate linear convergence matching GNPG.

Contribution 2: In Section <ref>, we consider the stochastic setting for which previous theoretical approaches relied on various oracle-like quantities to choose the step-size [Yuan et al., 2022, Mei et al., 2021, Mei et al., 2023]. To design a practical softmax PG algorithm that can adapt to the stochasticity, we utilize exponentially decreasing step-sizes [Li et al., 2021]. The resulting algorithm matches the $\tilde{\gO}(\nicefrac{1}{\eps^3})$ rate of Yuan et al., 2022 without the knowledge of oracle-like information. In order to attain faster convergence, we use the strong growth condition (SGC) [Schmidt & Roux, 2013, Vaswani et al., 2019] similar to Mei et al., 2023. We prove that the same algorithm with exponentially decreasing step-sizes is robust to unknown problem-dependent constants and can interpolate between the fast $\tilde{\gO}(\nicefrac{1}{\eps})$ and slow $\tilde{\gO}(\nicefrac{1}{\eps^3})$ rate.

Contribution 3: Finally, in <ref>, we experimentally benchmark the proposed algorithms in the bandit setting. Our empirical results indicate that the proposed algorithms have comparable performance as baselines that require oracle-like knowledge.

Contribution 4: In <ref>, we study the use of entropy regularization for PG methods in both the exact and stochastic settings. Entropy regularization has been successfully used in RL [Haarnoja et al., 2018, Hiraoka et al., 2022]. It has been found to smooth the objective function, enabling PG methods to escape flat regions and allowing the use of larger step-sizes [Ahmed et al., 2019]. Although entropy regularization allows for faster convergence, it results in convergence to a biased policy. We introduce a practical multi-stage algorithm that iteratively reduces the entropy regularization and converges to the optimal policy. The resulting algorithm does not require the knowledge of any problem dependent constants such as the reward gap like in prior work [Mei et al., 2020]. We analyze the convergence of the resulting algorithm in the exact (<ref>) and stochastic (<ref>) settings.

§ PROBLEM SETUP & BACKGROUND

An infinite-horizon discounted Markov decision process (MDP) [Puterman, 2014]
is defined by tuple $\parens*{\gS, \gA, \gP, r, \rho, \gamma}$, where $\gS$ is the set of states, $\gA$ is the set of actions, $\gP : \gS \times \gA \rightarrow \Delta_{\gS}$ is the transition probability function, $\rho \in \Delta_{\gS}$ is the initial state distribution, $r : \gS \times \gA \rightarrow [0, 1]$ is the reward function, and $\gamma \in [0, 1)$ is the discount factor. We will only consider tabular MDPs, assuming that the state and action spaces are finite and define $S := |\gS|$ and $A := |\gA|$. For policy $\pi$, the action-value function $Q^{\pi} : \gS \times \gA \rightarrow \R$ is defined as: $Q^{\pi}(s, a) := \E\bracks*{\sum_{t=0}^\infty \gamma^t r(s_t, a_t)}$, with $s_0 = s$, $a_0 = a$ and for $t \geq 1$, $s_{t+1} \sim p(\cdot | s_t, a_t)$ and $a_{t+1} \sim \pi(\cdot | s_t)$. The corresponding value function $V^{\pi}: \gS \rightarrow \R$ is defined such that $V^{\pi}(s) = \E_{a \sim \pi(\cdot | s)}[Q^{\pi}(s, a)]$. The advantage function $A^{\pi}: \gS \times \gA \rightarrow \R$ is defined such that $A^{\pi}(s, a) := Q^{\pi}(s, a) - V^{\pi}(s)$. The discounted state visitation distribution is denoted by $d^{\pi}_{s_0} \in \Delta_\gS$ and is defined such that $d^{\pi}_{s_0} := (1 - \gamma) \sum_{t=0}^\infty \gamma^t \Pr[s_t = s \, | s_0, \pi]$ where $\Pr[s_t = s \, | s_0, \pi]$ denotes the probability of visiting state $s$ at time $t$ under policy $\pi$. Given a class of feasible policies $\Pi$, the policy optimization objective is: $\max_{\pi \in \Pi} J(\pi) := \E_{s \sim \rho}[V^{\pi}(s)]$. For brevity, we define $V^{\pi}(\rho) := \E_{s \sim \rho}[V^{\pi}(s)]$. We denote the optimal policy as $\pistar = \argmax_{\pi \in \Pi} J(\pi)$. Throughout this paper, we will consider both the general MDP setting and the bandits setting. For the bandit setting, $S = 1$ and $\gamma = 1$, and the corresponding objective is to find a policy that maximizes $\E[\langle \pi, r \rangle]$ where the expectation is over the stochastic rewards.

In this work, we consider policies with a softmax tabular parameterization, i.e. for parameters $\theta \in \R^{S \times A}$, the set $\Pi$ consists of policies $\pitheta: \gS \rightarrow \Delta_{\gA}$ parameterized using the softmax function such that $\pitheta(a | s) = \nicefrac{\exp(\theta(s, a))}{\sum_{a' \in \gA}\exp(\theta(s, a'))}$. Such a tabular parameterization has been recently used to study the theoretical properties of policy gradient methods [Agarwal et al., 2021, Mei et al., 2020].
Throughout, we will present our results considering $f(\theta)$ as an abstract objective with specific properties, and when required, instantiate it in the general MDP or bandits setting.
In the general MDP setting, $f(\theta) := V^{\pitheta}(\rho)$, while in the bandits setting, $f(\theta) :=  \E[\langle \pitheta, r \rangle]$. With this abstraction, we hope that our results can be easily generalized to other settings such as constrained MDPs [Altman, 2021] or convex MDPs [Zahavy et al., 2021, Zhang et al., 2020]. Next, we specify the properties of $f$ that will be used to analyze the convergence of PG methods.

Setting          $f(\theta)$       $[\nabla f(\theta)]_{s, a}$      $L$      $L_1$      $\nu$     $C(\theta)$
Bandits     $\langle \pitheta, r \rangle$     $\pitheta(a) \, [r(a) - \dpd{\pitheta, r}]$     $5/2$      $3$      $\frac{\sqrt{2}}{\Delta^*}$      $\pitheta(a^*)$
MDP      $V^{\pitheta}(\rho)$     $\frac{d^{\pitheta}(s) \, \pitheta(a | s) \, A^{\pitheta}(s, a)}{1 - \gamma}$      $\frac{8}{(1 - \gamma)^3}$      $\bracks*{3 + \frac{2 \, C_\infty - (1 - \gamma)}{(1 -\gamma) \gamma}} \, \sqrt{S}$      $\frac{\sqrt{2}}{(1- \gamma) \, \Delta^*}$     $\frac{\min_s \pitheta(a^*(s) | s)}{\sqrt{S} \, \supnorm{\frac{d^{\pi^*}_\rho}  {d^{\pitheta}_\rho}}}$

Function and gradient expressions, (non)-uniform smoothness, non-uniform and reversed Łojasiewciz properties for bandits and general tabular MDPs with $\xi = 0$ [Mei et al., 2020].
Here, $a^*$ is index of the optimal arm in the bandit problem , $C_\infty := \max_\pi \supnorm{\frac{d^\pi_\rho}{\rho}}$ is the distribution mismatch ratio [Agarwal et al., 2021], and $\Delta^* := \min_{s} Q^*(s, a^*(s)) - \max_{a(s) \neq a^*(s)}Q^*(s, a(s))$ is the reward gap corresponding to the optimal policy.

First, we note that $f$ is a non-concave function for both bandits and general MDPs <cit.>. However, in both cases, it is twice-differentiable and $L$-smooth, i.e. for all $\theta$, there exists a constant $L \in (0, \infty)$, $\nabla^2 f(\theta) \preceq L I_d$. Since this property holds for all $\theta$ and $L$ is a constant independent of $\theta$, we refer to this as uniform smoothness. For both bandits and general MDPs, $f$ also satisfies a notion of non-uniform smoothness, i.e. for all $\theta$, there exists a $L_{1} \in (0, \infty)$ such that $\nabla^2 f(\theta) \preceq L_1 \, \norm{\nabla f(\theta)} I_d$. Intuitively, non-uniform smoothness states that the landscape is flatter closer to a stationary point $\tilde{\theta}$, meaning that as $\theta \rightarrow \tilde{\theta}$, $\nabla^2 f(\theta) \rightarrow \mathbf{0}$, i.e. the Hessian becomes degenerate. Together, the uniform and non-uniform smoothness properties are related to the $(L_0, L_1)$ smoothness used to study the optimization of transformer models [Zhang et al., 2019].

Since the rewards are bounded, $f(\theta)$ is upper-bounded by a value $f^* := \max_{\theta} f(\theta)$. Furthermore, $f$ satisfies a non-uniform Łojasiewciz condition, i.e. for all $\theta$, there exists a $C(\theta) \in (0, \infty)$ and $\xi \in [0, 1]$ such that $\norm{\grad{\theta}}_2 \geq C(\theta) \, \abs{f^* - f(\theta)}^{1 - \xi}$ [Mei et al., 2020]. For the special case where $C(\theta)$ is an absolute constant and $\xi = \nicefrac{1}{2}$, this condition matches the well studied Polyak Łojasiewciz (PŁ) condition [Polyak, 1963, Karimi et al., 2016]. The Łojasiewciz condition states that every stationary point $\tilde{\theta}$ (s.t. $\nabla f(\tilde{\theta}) = 0$) is also a global maximum s.t. $f(\tilde{\theta}) = f^*$. This condition enables the convergence of local ascent methods such as PG to an optimal solution $\theta^* := \argmax_\theta f(\theta)$ despite the problem's non-concavity [Karimi et al., 2016, Mei et al., 2020, Agarwal et al., 2021].
Finally, $f$ satisfies a reversed Łojasiewciz condition, i.e for all $\theta$, there exists a $\nu > 0$ such that $\norm{\grad{\thetat}} \leq \nu \, (f^* - f(\theta))$ [Mei et al., 2020]. This condition bounds how quickly progress can be made near the optimal solution. <ref> summarizes both the uniform and non-uniform smoothness and Łojasiewciz properties for bandits and general MDPs. Similar to Mei et al., 2020, we assume a uniform starting state distribution, i.e. $\forall s \in \gS$, $\rho(s) = \nicefrac{1}{S}$ and hence $C_\infty \leq \frac{1}{\min_s \rho(s)} < \infty$. This is a common assumption in the policy gradient literature that obviates the need for exploration in the general MDP setting and allows us to exclusively focus on the optimization aspects. We note that for both these settings, the optimal policy is deterministic [Puterman, 2014] i.e. in the general MDP setting, for each state $s \in \gS$, there is an action $a^*(s) \in \gA$ such that $\pistar(a^*(s)|s) = 1$ and for all $a \neq a^*(s)$, $\pistar(a|s) = 0$. This implies that when using the softmax tabular parameterization, $\theta^*(s, a^*(s)) \rightarrow \infty$ and for all $a \neq a^*(s)$, $\theta^*(s, a) \rightarrow -\infty$. This property is similar to that for logistic regression for classification on linearly separable data [Ji & Telgarsky, 2018].

Given the above properties of $f$, in the next section, we study the convergence of PG methods in the exact setting where the rewards and transition probabilities are known.

§ POLICY GRADIENT IN THE EXACT SETTING

We first consider the exact setting where the rewards and transition probabilities are known. The exact setting has been used as a test bed to study the convergence properties of policy gradient methods [Bhandari & Russo, 2021, Agarwal et al., 2021, Mei et al., 2020]. Softmax policy gradient (softmax PG) uses gradient ascent to iteratively maximize $f(\theta)$ i.e. at iteration $t \in [T]$, softmax PG uses a step-size of $\etat$ and has the following update:
(Softmax PG, True Gradient)
$\thetatt = \thetat + \etat \grad{\thetat}$.

Refer to <ref> for the gradient expressions in both bandits and general MDP cases. The knowledge of the rewards and transition probabilities in the exact setting enables the computation of the full gradient. In this setting, Mei et al., 2020 prove that softmax PG converges to an optimal solution at an $\gO(\nicefrac{1}{T})$ rate, implying that the algorithm requires $\gO(\nicefrac{1}{\eps})$ iterations to guarantee that $f^* - f(\theta_{T+1}) \leq \epsilon$. From an policy optimization perspective, this implies that softmax PG can return a stochastic policy whose value function is $\eps$ close to the optimal policy's value function. In order to achieve this convergence, Mei et al., 2020 requires using a constant step-size $\etat = \eta = \nicefrac{1}{L}$. Furthermore, for any $\etat \in (0, 1]$, <cit.> proves an $\Omega(\nicefrac{1}{\eps})$ lower-bound showing that this rate is tight.

In most scenarios, we can only obtain a loose upper-bound on the smoothness $L$. This over-estimation of $L$ implies that the resulting step-size is typically smaller than necessary, often resulting in worse empirical performance.  In practice, when doing gradient ascent with access to the exact gradient, it is standard to employ a line-search [Armijo, 1966, 26] to adaptively set the step-size in each iteration. This results in faster empirical convergence while requiring minimal tuning, and preserving the rate of convergence. Hence, we propose to use a backtracking Armijo line-search [Armijo, 1966] to adaptively set the step-size for softmax PG.

At every iteration $t$, backtracking Armijo line-search starts from an initial guess for the step-size ($\eta_{\mathrm{max}}$) and backtracks until the Armijo condition is satisfied. The procedure thus returns the largest step-size $\etat$ such that following condition is satisfied:

\begin{align}
f(\thetat + \eta_t \grad{\thetat}) \geq f(\thetat) + h \etat \normsq{\grad{\thetat}} \,, \; \; \; \text{(Armijo condition)}
\label{eq:armijo}
\end{align}

where $h \in (0, 1)$ is a hyper-parameter. For smooth functions, the backtracking procedure is guaranteed to terminate and return a step-size $\etat$ that satisfies $\etat \geq \min \braces*{\nicefrac{2(1-h)}{L}, \eta_{\mathrm{max}}}$. Hence, Armijo line-search guarantees improvement in the function value (ensuring monotonic improvement at each iteration $t$) and selects a step-size larger than the $\nicefrac{1}{L}$ step-size used in Mei et al., 2020. Moreover, the line-search can adapt to the local smoothness around $\thetat$ (which can be much smaller than the global smoothness) without explicitly specifying or computing an upper-bound on it.

The following theorem shows that using the Armijo line-search preserves the theoretical $\gO(\nicefrac{1}{T})$ convergence rate.
Assuming $f$ is (i) $L$-smooth, (ii) satisfies the non-uniform Łojasiewciz condition with $\xi = 0$, and (iii) $\mu := \inf_{t \geq 1} [C(\thetat)]^2 > 0$, using <ref>, Armijo line-search to set the step-size converges as:

\begin{equation}\label{eq:linesearch_ascent}
f^* - f(\theta_{T+1}) \leq \max \braces*{\frac{L}{2\,h\,(1-h)}, \frac{1}{h\,\eta_{\mathrm{max}}}} \, \frac{1}{\mu \, T}
\end{equation}

where $h \in (0, 1)$ and $\eta_{\max}$ is the upper-bound on the step-size.

While assumptions (i) and (ii) are satisfied for both the general MDP and bandit settings, we need to ensure that assumption (iii) also holds. In order to guarantee that $\mu := \inf_{t \geq 1} [C(\thetat)]^2 > 0$, we first note that this property holds for a constant step-size $\etat = \eta = \nicefrac{1}{L}$ <cit.>. We note that the proof can be extended to any varying step-size sequence that guarantees ascent ($f(\thetatt) \geq f(\thetat)$) in every iteration. When using the Armijo line-search to set the step-size, this condition is satisfied by definition, thus guaranteeing that $\mu > 0$.

The Armijo line-search in <ref> takes advantage of the objective's uniform smoothness in order to attain an $\gO(\nicefrac{1}{T})$ convergence. In our initial experiments, we observe that for most iterations, the maximum step-size $\eta_{\max}$ satisfies the Armijo condition, and is hence returned by the line-search procedure. By using a sufficiently large $\eta_{\max}$ or by progressively increasing the maximum step-size as a function of $t$, the resulting algorithm converges at a linear rate. Intuitively, this happens because the objective satisfies a non-uniform smoothness property and the optimization landscape becomes flatter as the gradient norm decreases closer to the solution. This enables the use of larger step-sizes than those allowed by <ref>. In order to explicitly take advantage of the non-uniform smoothness property, we design a line-search on the log of the suboptimality. Formally, we design the following line-search condition:

\begin{equation}\label{eq:trans_line_search}
\ln(f^* - f(\thetat + \etat \, \grad{\thetat})) \leq  \ln(f^* - f(\thetat)) - h \etat \frac{\normsq{\grad{\thetat}}}{f^* - f(\tht)},
\quad \text{(Armijo condition for log-loss)}.
\end{equation}

From <ref>, we can guarantee that the backtracking line-search procedure terminates and returns $\etat \geq \min\braces*{\eta_{\max}, \frac{2(1-h)}{L_1 \, \nu \, [f^* - f(\tht)]}}$ (refer to <ref> for the values of $L_1$ and $\nu$). Hence, the resulting line-search accepts step-sizes proportional to $\frac{1}{f^* - f(\tht)}$ and as the optimization progresses, larger step-sizes can be used.

The following theorem (proved in <ref>) characterizes the rate of convergence of softmax PG when using the Armijo condition for the log-loss in <ref>.
Assuming $f$ is (i) $L_1$ non-uniform smooth, (ii) satisfies the non-uniform Łojasiewciz condition with $\xi = 0$, (iii) $\mu := \inf_{t \geq 1}[C(\thetat)]^2 > 0$, (iv) $f$ satisfies a reversed Łojasiewciz condition, i.e. for all $\theta$, $\norm{\grad{\theta}} \leq \nu \, (f^* - f(\theta))$ for $\nu > 0$, for a given $\eps \in (0, 1)$ using <ref> with backtracking line-search using the Armijo condition for the log-loss defined in <ref> to set the step-size and $\eta_{\max} = \nicefrac{C}{\eps}$ results in the following convergence: if $f^* - f(\thetat) > \eps$ for all $t \in [1, T]$, then,

\begin{equation}
f^* - f(\theta_{T+1}) \leq [f^* - f(\theta_1)] \, \exp\parens*{-\min\left\{C \, h, \frac{2\,h\,(1-h)}{L_1 \, \nu}\right\} \, \mu \, T}
\label{eq:armijo-log-loss}
\end{equation}

where $C > 0$ and $h \in (0, 1)$ are hyper-parameters. Otherwise $\min_{t \in [1, T]} f^* - f(\tht) \leq \eps$.

We compare softmax PG that (i) uses a step-size that satisfies the Armijo condition in <ref> (denoted as ), (ii) uses a step-sizes that satisfies the Armijo condition on the log-loss in <ref> () to GNPG (). For the backtracking line-search, we use $\eta_{\max} = \frac{1}{\eps}$ with $\eps = 10^{-8}$ and $h=0.5$. We evaluate the algorithms in the bandits setting with $A = 10$ of varying difficulty based on their minimum reward gap $\underset{\bar{}}{\Delta} := \min_{a^* \neq a} r(a^*) - r(a)$. The easy, medium and hard environments correspond to $\underset{\bar{}}{\Delta} = 0.2, 0.1, 0.05$ respectively. The figure plots the average and 95% confidence interval of 50 random mean reward vectors. We observe that  is comparable to  while  can better exploit the non-uniform property of $f$ enabling convergence to the target $\eps$ after a single iteration.

For sufficiently large $\eta_{\max}$, the above algorithm achieves $\gO(\log\nicefrac{1}{\eps})$ rate.
By setting $\eta_{\max} = \nicefrac{C}{\eps}$ where $C > 0$, the backtracking line-search is guaranteed to use large step-sizes of $\gO(\nicefrac{1}{\eps})$ in each iteration.
By explicitly exploiting the non-uniform property of $f$, larger step-sizes can immediately be used when compared to <ref>. Unfortunately, implementing the Armijo condition on the log-loss requires the knowledge of $f^*$. This requirement is similar to the Polyak step-size [Polyak, 1987] used in numerical optimization. For future work, we hope to remove this dependence of $f^*$ to make the new Armijo condition on the log-loss practical.

The geometry-aware normalized policy gradient (GNPG) approach introduced in Mei et al., 2021 also explicitly exploits this non-uniform smoothness and exhibits a convergence rate of $\mathcal{O}(\log \nicefrac{1}{\eps})$. However, in the general MDP setting, GNPG requires the knowledge of unknown constants such as the concentrability coefficient $C_\infty := \max_\pi \supnorm{d^\pi_\rho / \rho}$ to determine the step-size, making it impractical. In contrast, softmax PG with
backtracking line-search does not require such information but can still exploit the non-uniform smoothness to achieve fast convergence towards the optimal policy. In <ref>, we compare softmax PG with step-sizes that satisfies the Armijo condition in <ref> and Armijo condition on the log-loss in <ref> to GNPG and attain a similar linear convergence. Furthermore in <ref>, we compare the wall-clock time of the compared methods to justify the performance gains when employing a line-search.

In the next section, we study the more realistic stochastic setting where the rewards and transition probabilities are unknown. Although GNPG and NPG can obtain faster convergence rates in the exact setting, they are not guaranteed to converge to the optimal policy in the stochastic setting [Mei et al., 2021]. This is because these methods are aggressive and can quickly commit to sub-optimal actions. Consequently, we restrict ourselves to softmax PG in the stochastic setting.

§ POLICY GRADIENT IN THE STOCHASTIC SETTING

Since it is not possible to compute the full gradient without the knowledge of rewards or transition probabilities, we use softmax PG with stochastic (inexact) gradients. In <ref>, we construct stochastic gradients that are unbiased and have bounded variance. We design a stochastic softmax PG algorithm that uses exponentially decreasing step-sizes similar to [Li et al., 2021, Vaswani et al., 2022]. In <ref>, we prove that the resulting algorithm can obtain convergence rates comparable to the state-of-the-art, but do not require oracle-like knowledge of the environment. Finally, in <ref>, we exploit the fact that the variance in the stochastic gradients decreases as the algorithm approaches a stationary point, and prove that the same stochastic softmax PG algorithm can obtain a faster convergence rate.

§.§ Stochastic Softmax Policy Gradient

For illustrative purposes, we focus on the bandit setting in the main paper. In the stochastic multi-armed bandit setting [Lattimore & Szepesvári, 2020], each action (arm) has an underlying unknown reward distribution. In every iteration $t$, the algorithm chooses an action to pull and receives a stochastic reward sampled from the distribution of the corresponding arm. The stochastic softmax PG algorithm maintains a distribution $\pit \in \Delta_{\gA}$ over the actions. In each iteration $t \in [1, T]$, the algorithm samples an action $a_t \sim \pit$ and receives reward $R_t \sim P_{a_t}$ where $P_{a_t}$ is the reward distribution of arm $a_t$. The reward $R_t$ is used to construct the on-policy importance sampling (IS) reward estimate $\hat{r}_t(a) = \frac{\indicator{a_t = a}}{\pit(a)} \, R_t$ for each $a \in \gA$. The IS reward estimate is then used to form the stochastic gradient $\hgrad{\tht}$ such that $\hgrad{\tht}(a) = \pit(a) [\hat{r}_t(a) - \langle \pit, \hat{r}_t \rangle]$. <cit.> shows that the resulting stochastic gradients are (i) unbiased i.e.
$\E[\hgrad{\theta}] = \grad{\theta}$ and have (ii) bounded variance i.e. $\E\normsq{\hgrad{\theta} - \grad{\theta}} \leq \sigma^2$. Similarly, we can construct gradient estimators that are unbiased and have bounded variance for general MDPs (refer to <ref>). The resulting stochastic softmax PG algorithm has the following update:
(Stochastic Softmax PG, Importance Sampling)
$\thetatt = \thetat + \etat \hgrad{\thetat}$.

We note that this update has also been used in Yuan et al., 2022, Mei et al., 2021 that attain global convergence to the optimal solution in both the bandit and general MDP settings. However, in order to prove theoretical convergence, Yuan et al., 2022 use the knowledge of $\mu := \inf_{t \geq 1} [C(\thetat)]^2$ when setting the step-size. However, in both the bandit and general MDP settings (see <ref> for details) $C(\theta)$ and consequently $\mu$ depends on the optimal action. This makes the resulting algorithm impractical. On the other hand, Mei et al., 2021 require the full gradient to set the step-size and obtain global convergence. Since the full gradient is not available in the stochastic setting, it is not practical to use their algorithm.

To alleviate these issues, we make use of exponentially decaying step-sizes [Li et al., 2021, Vaswani et al., 2022] that have been previously used for stochastic gradient descent (SGD) when minimizing smooth non-convex functions satisfying the PŁ-inequality [Polyak, 1963, Karimi et al., 2016]. In this setting, the benefit of exponentially decaying step-sizes is that they can achieve (up to poly-logarithmic terms) the best known convergence rates without the knowledge of $\sigma^2$ or $\mu$. In particular, given the knowledge of $T$, the step-sizes in iteration $t$ is set as: $\eta_t = \eta_0 \, \alpha^t$  where $\eta_0$ is the initial step-size, $\alpha = \left(\frac{\beta}{T}\right)^\frac{1}{T}$ and $\beta \geq 1$. Although $\beta$ is a hyperparameter, we emphasize that it does not depend on any problem-dependent constants. We leverage these step-sizes for designing a stochastic softmax PG algorithm and characterize its convergence in the next section.

§.§ Theoretical Convergence

By using the proof techniques from Yuan et al., 2022 and Li et al., 2021, we prove the following theorem in <ref>.

Assuming $f$ is (i) $L$-smooth, (ii) satisfies the non-uniform Łojasiewciz condition with $\xi = 0$, (iii) $\mu := \inf_{t \geq 1} [C(\thetat)]^2 > 0$, for a given $\eps \in (0,1)$, using <ref> with (a) unbiased stochastic gradients whose variance is bounded by $\sigma^2$ and (b) exponentially decreasing step-sizes $\eta_t = \eta_0 \, \alpha^t$  where $\eta_0 = \frac{1}{L}$ and $\alpha = \left(\frac{\beta}{T}\right)^\frac{1}{T}$, $\beta \geq 1$ results in the following convergence:  if $\E[f^* - f(\thetat)] > \eps$ for all $t \in [1, T]$, then,

\begin{align}
\E[f^* - f(\theta_{T+1})] &\leq [f^* - f(\theta_1)] \,C_1 \, \exp \parens*{-\frac{\alpha \, \eps \,  T}{\kappa \ln(\nicefrac{T}{\beta})}}  + \frac{ \, C_1 \, C_2}{2 \, L}  \frac{\ln^2\parens*{\frac{T}{\beta}}\sigma^2}{ \eps^2 \, T}
\end{align}

where $\kappa := \frac{2 \, L}{\mu}$, $C_1 := \exp \parens*{\frac{2 \beta}{\kappa \ln(\nicefrac{T}{\beta})}}$ and $C_2 := \frac{4 \kappa^2}{e^2 \alpha^2}$.
Otherwise, $\min_{t \in [1, T]} \E[f^* - f(\thetat)] \leq \eps$.

In order to ensure that assumption (iii) holds, let us consider the bandit setting where $C(\theta) = \pitheta(a^*)$. To guarantee that $\mu := \inf_{t \geq 1} [C(\thetat)]^2 > 0$, we ensure that $\pi_{\theta_0}(a^*) > 0$ and $T$ is finite. Since $T$ is finite and $\theta_0$, $\etat$ and the stochastic gradients are bounded (refer to <ref> in <ref>), no parameter including $\theta(a^*)$ can diverge to $-\infty$, guaranteeing that $\pitheta(a^*) > 0$.

To determine the resulting convergence rate, let us first analyze the case when $\sigma^2 = 0$. In this case, given a target $\eps$, we set $T = \gO(\nicefrac{1}{\eps}\, \log(\nicefrac{1}{\eps}))$ iterations to make the first term $\gO(\eps)$. On the other hand, when $\sigma^2 > 0$ and the second term of $\tilde{\gO}\parens*{\nicefrac{\sigma^2}{\eps^2 T}}$ dominates, we set $T = \tilde{\gO}(\nicefrac{1}{\eps^3})$ iterations to make the second term $\gO(\eps)$. Putting both cases together, in order to make the sub-optimality $\gO(\eps)$, we can set $T = \max\{\tilde{\gO}\parens*{\nicefrac{1}{\eps}, \nicefrac{\sigma^2}{\eps^{3}}}\}$. This convergence rate matches that in Yuan et al., 2022 without requiring the knowledge of $\mu$. We emphasize that the above convergence rate holds without the knowledge of any oracle-like information.

The previous result assumes that the variance $\sigma^2$ is constant w.r.t. $\theta$. However, it has been observed that the noise depends on $\theta$, and decreases as the algorithm gets closer to a stationary point and the policy become more deterministic. Next, we leverage this property to prove faster rates.

§.§.§ Faster Rates

In the bandit setting, Mei et al., 2023 formalize the above intuition, and prove that the stochastic gradient $\hgrad{\theta}$ satisfies the strong growth condition (SGC) [Schmidt & Roux, 2013, Vaswani et al., 2019] implying that
$\E \normsq{\hgrad{\theta}}  \leq \varrho \norm{\grad{\theta}}$ for a problem-dependent $\varrho > 1$. This implies that the variance decreases as the algorithm approaches a stationary point and $\norm{\nabla f(\theta)} \rightarrow 0$. For the bandit setting, using <ref> and the knowledge of $\varrho$ to set the step-size, Mei et al., 2023 can attain a faster $\gO(\nicefrac{1}{\eps})$ convergence rate. We generalize the above SGC result to the general MDP setting in <ref> (proved in <ref>).
Using <ref>, we have for all $\theta$, $\E\normsq{\hgrad{\theta}} \leq \varrho \norm{\grad{\theta}}_2$,
where $\varrho := \frac{8  \, A^{3/2}}{\Delta^2}$ in the bandit setting with $\Delta := \min_{a \neq a'}\abs{r(a) - r(a')}$
$\varrho =  \frac{4 \, A^{3/2} \, S^{1/2}}{(1 - \gamma)^4 \, \Delta^2}$ in the tabular MDP setting.
with $\Delta := \min_s \min_{a \neq a'} \abs{Q^{\pitheta}(s, a) - Q^{\pitheta}(s, a')}$.

However, in the bandit setting, $\varrho$ depends on the unknown reward gap $\Delta := \min_{a \neq a'} \abs{r(a) - r(a')}$ and we prove that this dependence is necessary (<ref> in <ref>). This makes the resulting algorithm ineffective in most practical cases. Hence, we aim to develop a practical algorithm that can automatically adapt to $\varrho$ and result in a faster convergence. In <ref> proved in <ref>, we show that the same stochastic softmax PG algorithm (with exponentially decreasing step-sizes) can attain such fast convergence. In addition to the properties in <ref>, we exploit the function's non-uniform smoothness, the SGC and the boundedness of stochastic gradients to prove this result.

Assuming $f$ is (i) $L_1$ non-uniform smooth , i.e. $\norm{\nabla^2 f(\theta)} \leq L_1 \norm{\grad{\theta}}$, (ii) satisfies the non-uniform Łojasiewciz condition with $\xi = 0$, (iii) $\mu :=  \inf_{t \geq 1} [C(\thetat)]^2 > 0$, given $\eps \in (0, 1)$, using <ref> with unbiased stochastic gradients that are (a) bounded, i.e. $\norm{\hgrad{\theta}} \leq B$ and satisfy the strong growth condition with constant $\varrho$ and (b) exponentially decreasing step-sizes s.t. $\eta_0 < \frac{1}{L_1^2 B}$, has the following convergence: if $\E[f^* - f(\thetat)] > \eps$ for all $t \in [1, T]$, then,

\begin{align}
\E[f^* - f(\theta_{T+1})] &\leq [f^* - f(\theta_1)] \, C_1 \, \exp\left(-\frac{\alpha \, \eps \, T}{\kappa \, \ln(T)} \right) +  \frac{C_2 \, \sum_{t=1}^{T_0 - 1} \E[f^* - f(\thetat)]}{\eps^2 \, T^2}
\end{align}

where $\kappa := \frac{2}{\mu \, \eta_0}$, $C_1 := \exp\parens*{\frac{2 \beta}{\kappa \ln(\nicefrac{T}{\beta})}}$, $C_2 := \exp\parens*{\frac{2\beta}{\kappa \ln(\nicefrac{T}{\beta})}} \frac{16 \varrho L \kappa^2}{e^2 \alpha^2} \ln^2(\nicefrac{T}{\beta})$, $T_0 := T\, \max \left\{\frac{\ln(\varrho \eta_0)}{\ln(\nicefrac{T}{\beta})}, 0 \right\}$. Otherwise, ${\min_{t \in [1, T]} \E[f^* - f(\thetat)] \leq \eps}$.

Similar to <ref>, assumption (iii) is true when $\pi_{\theta_0}(a^*) > 0$ and $T$ is finite. In <ref> (proved in <ref>), we prove that the stochastic gradients are bounded in both the bandit and MDP settings. In the above result, $T_0$ represents the iteration when the step-size is small enough to take advantage of the SGC. Given the knowledge of $\varrho$, we can set set $\eta_0 \leq \nicefrac{1}{\varrho}$ in which case $T_0 = 0$. In this case, setting $T = \tilde{\gO}(\nicefrac{1}{\eps})$ iterations enables us to obtain a “fast” $\gO(\nicefrac{1}{\eps})$ rate. Since $\varrho$ is unknown in general, setting $\eta_0$ to be large can result in $T_0 = \gO(T)$ in the worst case. In this case, the second term of order $\tilde{\gO}(\nicefrac{1}{\eps^2 T})$ dominates. In this case, setting $T = \gO(\nicefrac{1}{\eps^3})$ iterations results in a “slow” $\tilde{\gO}\parens*{\nicefrac{1}{\eps^3}}$ rate. Hence, the resulting algorithm is robust to $\varrho$ and depending on how $\eta_0$ is set, it can interpolate between the “slow” and “fast” rates.

Below, we instantiate <ref> in the bandit setting.
In the bandit setting, given $\eps \in (0, 1)$, using <ref> with exponentially decreasing step-sizes $\eta_t = \eta_0 \, \alpha^t$, $\alpha = \left(\frac{\beta}{T}\right)^\frac{1}{T}$, $\beta \geq 1$ and $\eta_0 \leq \frac{1}{18}$
results in the following convergence: if $\E[(\pistar - \pi_{\thetat})^\top r] \geq \eps$ for all $t \in [1, T]$, then,

\begin{equation}
\E[(\pistar - \pi_{\theta_{T+1}})^\top r] \leq
[(\pistar - \pi_{\theta_{1}})^\top r]
\,C_1 \, \exp \parens*{-\frac{\alpha \, \eps \,  T}{\kappa \ln(\nicefrac{T}{\beta})}}  +   \frac{C_2 \, \sum_{t=1}^{T_0 - 1} \E[(\pistar - \pi_{\thetat})^\top r]}{ \eps^2 \, T}
\end{equation}

where $\kappa := \frac{2}{\mu \, \eta_0}$, $C_1 := \exp\parens*{\frac{2 \beta}{\kappa \ln(\nicefrac{T}{\beta})}}$, $C_2 := \exp\parens*{\frac{2\beta}{\kappa \ln(\nicefrac{T}{\beta})}} \frac{32 \varrho \kappa^2}{5 \, e^2 \alpha^2} \ln^2(\nicefrac{T}{\beta})$, $T_0 := T\, \max \left\{\frac{\ln(4 \varrho \eta_0)}{\ln(\nicefrac{T}{\beta})}, 0 \right\}$, $\rho = \frac{8 \, A^{3/2}}{\Delta^2}$ and $\mu = \inf_{t \geq 1} [\pit(a^*)]^2$. Otherwise, ${\min_{t \in [1, T]} \E[(\pistar - \pit)^\top r] \leq \eps}$.

In the multi-armed bandit setting, using stochastic softmax PG with exponentially decreasing step-sizes allows for implicit automatic exploration without requiring the knowledge of any problem-dependent constants such as the reward gap. Unlike [Mei et al., 2023], we note that the above result does not imply asymptotic convergence to the optimal arm. This difference stems from the fact that Mei et al., 2023 uses a constant step-size, while the above result requires a decreasing step-size that asymptotically goes to zero. Compared to the standard algorithms for multi-armed bandits such as upper confidence bound (UCB) [Auer et al., 2002] which requires the knowledge of the noise magnitude to design confidence intervals or Thompson sampling (TS) [Agrawal & Goyal, 2012] which requires knowledge of the reward distribution, stochastic softmax PG does not require such information.

In the next section, we empirically validate our theoretical results and compare the proposed methods to prior algorithms in the bandits setting.

§ EXPERIMENTAL EVALUATION

Expected sub-optimality gap across various environments.  and  is comparable to  and  without using any oracle-like knowledge of the environment.

We evaluate the methods in multi-armed bandit environments with $A = 10$.
For each environment, we compare the various algorithms on the basis of their expected sub-optimality gap $\E[(\pistar - \pit)^\top r]$. For each instance of an environment, we run an algorithm $5$ times to account for the stochasicity of each algorithm. We plot the average and 95% confidence interval of the expected sub-optimality gap across $25$ instances over $T=10^6$ iterations. For each run, the initial policy is uniform, i.e. $\pi_{\theta_0}(a) = \nicefrac{1}{A}$ for all $a \in \gA$.

Environment Details:
Each environment's underlying reward distribution is either a Bernoulli, Gaussian, or Beta distribution with a fixed  mean reward vector $r \in \R^A$ and support $[0, 1]$. The difficulty of the environment is determined by the maximum reward gap $\bar{\Delta} := \min_{a^* \neq a} r(a^*) - r(a)$. In easy environments $\bar{\Delta} = 0.5$ and in the hard environments $\bar{\Delta} = 0.1$. For each environment, $r$ is randomly generated for each run.

Methods: We compare stochastic softmax PG with exponentially decreasing step-size () to prior work that uses the full gradient () [Mei et al., 2021] and the reward gap () [Mei et al., 2023] when setting the step-size. For , we select $\beta = 1$ and $\eta_0 = \frac{1}{18}$ for all experiments. For  and , we use the corresponding theoretical step-size
of $\etat = \frac{\Delta^2}{(40) \, 10^{\nicefrac{3}{2}}}$ and $\etat = \frac{1}{12} \, \left\|\frac{d \dpd{\pi_{\theta_t}, r}}{d \thetat}\right\|$.

From our initial experiments, we observed that  slows down and stops making progress due to the long time horizon. To counteract this measure, we additionally try a “doubling trick” (). This is a common trick when adapting algorithms that depend on a fixed number of iterations [Auer et al., 1995, Hazan & Kale, 2014].
With the “doubling trick”, we first start with a smaller $T_0 << T$ time horizon when setting the step-size. After $T_0$ iterations, we restart the step-size and double the length of the next step-size schedule i.e $T_1 = 2 \, T_0$. For  we select $\beta=1$, $\eta_0 = \frac{1}{18}$ and $T_0 = 5,000$ for all environments.

Results: From <ref>, we conclude that  and  are comparable to  and  across environments. While  has the best theoretical convergence rate, its step-size is proportional to the reward gap. When the reward gap is small, so is the resulting step-size which results in its poor empirical performance.
Furthermore, while  and  do not rely on any hyper-parameters to set the corresponding step-size, both methods require the require knowledge of the mean reward vector $r$. Hence, the optimal policy can immediately be recovered when correctly setting the step-size.
Any attempts in employing a grid-search to estimate $\Delta$ or $\left\|\frac{d \dpd{\pi_{\theta_t},  r}}{d \thetat}\right\|$ would be gratuitous since any convergence guarantee to the optimal policy would be lost. In contract, while  requires a hyper-parameter to be chosen, it's choice does not impact the resulting theoretical guarantee.

§ DISCUSSION

We designed (stochastic) softmax policy gradient (PG) methods for bandits and tabular Markov decision processes (MDPs). Throughout, we demonstrated that the proposed methods offer similar theoretical guarantees as the state-of-the art results, but do not require the knowledge of oracle-like quantities. Concretely, in the exact setting, we empirically demonstrated that using softmax PG with Armijo line-search to set the step-size is competitive to GNPG without requiring knowledge of the concentrability coefficient to set the step-size. In the stochastic setting, we used exponentially decreasing step-sizes and showed that the resulting algorithm is robust to problem-dependent constants and can interpolate between slow and fast rates. For future work, we plan to investigate how $(L_0, L_1)$-smoothness could be exploited to use larger learning rates resulting in better empirical performance.
Additionally, we hope to analyze the convergence rate when using the “doubling trick” with exponentially decreasing step-sizes.
Finally, we aim to generalize our results to support complex (non)-linear policy parameterization.

[Agarwal et al., 2021]
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.
On the theory of policy gradient methods: Optimality, approximation,
and distribution shift.
J. Mach. Learn. Res., 220 (98):0 1–76, 2021.

[Agrawal & Goyal, 2012]
Shipra Agrawal and Navin Goyal.
Analysis of thompson sampling for the multi-armed bandit problem.
In Conference on learning theory, pp.  39–1. JMLR Workshop
and Conference Proceedings, 2012.

[Ahmed et al., 2019]
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans.
Understanding the impact of entropy on policy optimization.
In International conference on machine learning, pp.  151–160. PMLR, 2019.

[Altman, 2021]
Eitan Altman.
Constrained Markov decision processes.
Routledge, 2021.

[Armijo, 1966]
Larry Armijo.
Minimization of functions having Lipschitz continuous first partial
Pacific Journal of Mathematics, 160 (1):0 1 –
3, 1966.

[Auer et al., 1995]
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.
Gambling in a rigged casino: The adversarial multi-armed bandit
In Proceedings of IEEE 36th annual foundations of computer
science, pp.  322–331. IEEE, 1995.

[Auer et al., 2002]
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
Machine learning, 47:0 235–256, 2002.

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

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

[10]
Yuhao Ding, Junzi Zhang, Hyunin Lee, and Javad Lavaei.
Beyond exact gradients: Convergence of stochastic soft-max policy
gradient methods with entropy regularization.

[Haarnoja et al., 2018]
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.
Soft actor-critic: Off-policy maximum entropy deep reinforcement
learning with a stochastic actor.
In International conference on machine learning, pp.  1861–1870. PMLR, 2018.

[Hazan & Kale, 2014]
Elad Hazan and Satyen Kale.
Beyond the regret minimization barrier: optimal algorithms for
stochastic strongly-convex optimization.
The Journal of Machine Learning Research, 150
(1):0 2489–2512, 2014.

[Hiraoka et al., 2022]
Takuya Hiraoka, Takahisa Imagawa, Taisei Hashimoto, Takashi Onishi, and
Yoshimasa Tsuruoka.
Dropout q-functions for doubly efficient reinforcement learning.
In International Conference on Learning Representations, 2022.
URL <https://openreview.net/forum?id=xCVJMsPv3RT>.

[Ji & Telgarsky, 2018]
Ziwei Ji and Matus Telgarsky.
Risk and parameter convergence of logistic regression.
arXiv preprint arXiv:1803.07300, 2018.

[Kakade, 2001]
Sham M Kakade.
A natural policy gradient.
Advances in neural information processing systems, 14, 2001.

[Karimi et al., 2016]
Hamed Karimi, Julie Nutini, and Mark Schmidt.
Linear convergence of gradient and proximal-gradient methods under
the polyak-łojasiewicz condition.
In Machine Learning and Knowledge Discovery in Databases:
European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23,
2016, Proceedings, Part I 16, pp.  795–811. Springer, 2016.

[Lan, 2023]
Guanghui Lan.
Policy mirror descent for reinforcement learning: Linear convergence,
new sampling complexity, and generalized problem classes.
Mathematical programming, 1980 (1):0
1059–1106, 2023.

[Lattimore & Szepesvári, 2020]
Tor Lattimore and Csaba Szepesvári.
Bandit algorithms.
Cambridge University Press, 2020.

[Li et al., 2021]
Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona.
A second look at exponential and cosine step sizes: Simplicity,
adaptivity, and performance.
In International Conference on Machine Learning, pp.  6553–6564. PMLR, 2021.

[Liu et al., 2024]
Jiacai Liu, Wenye Li, and Ke Wei.
Elementary analysis of policy gradient methods.
arXiv preprint arXiv:2404.03372, 2024.

[Mei et al., 2020]
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, pp.  6820–6829. PMLR, 2020.

[Mei et al., 2021]
Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans.
Understanding the effect of stochasticity in policy optimization.
Advances in Neural Information Processing Systems,
34:0 19339–19351, 2021a.

[Mei et al., 2021]
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, pp.  7555–7564. PMLR, 2021b.

[Mei et al., 2022]
Jincheng Mei, Wesley Chung, Valentin Thomas, Bo Dai, Csaba Szepesvari, and Dale
The role of baselines in policy gradient optimization.
Advances in Neural Information Processing Systems,
35:0 17818–17830, 2022.

[Mei et al., 2023]
Jincheng Mei, Zixin Zhong, Bo Dai, Alekh Agarwal, Csaba Szepesvari, and Dale
Stochastic gradient succeeds for bandits.
In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt,
Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th
International Conference on Machine Learning, volume 202 of
Proceedings of Machine Learning Research, pp.  24325–24360. PMLR,
23–29 Jul 2023.
URL <https://proceedings.mlr.press/v202/mei23a.html>.

[26]
Jorge Nocedal and Stephen J Wright.
Numerical optimization.

[Polyak, 1987]
Boris T Polyak.
Introduction to optimization.

[Polyak, 1963]
B.T. Polyak.
Gradient methods for the minimisation of functionals.
USSR Computational Mathematics and Mathematical Physics,
30 (4):0 864–878, 1963.
ISSN 0041-5553.

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

[Schmidt & Roux, 2013]
Mark Schmidt and Nicolas Le Roux.
Fast convergence of stochastic gradient descent under a strong growth
arXiv preprint arXiv:1308.6370, 2013.

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

[Shani et al., 2020]
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, volume 34, pp.  5668–5675, 2020.

[Sutton et al., 1999]
Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour.
Policy gradient methods for reinforcement learning with function
In Proceedings of the 12th International Conference on Neural
Information Processing Systems, NIPS'99, pp.  1057–1063, Cambridge, MA,
USA, 1999a. MIT Press.

[Sutton et al., 1999]
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.
Policy gradient methods for reinforcement learning with function
Advances in neural information processing systems, 12,

[Vaswani et al., 2019]
Sharan Vaswani, Francis Bach, and Mark Schmidt.
Fast and faster convergence of sgd for over-parameterized models and
an accelerated perceptron.
In The 22nd international conference on artificial intelligence
and statistics, pp.  1195–1204. PMLR, 2019.

[Vaswani et al., 2022]
Sharan Vaswani, Benjamin Dubois-Taine, and Reza Babanezhad.
Towards noise-adaptive, problem-adaptive (accelerated) stochastic
gradient descent.
In International Conference on Machine Learning, pp.  22015–22059. PMLR, 2022.

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

[Xiao, 2022]
Lin Xiao.
On the convergence rates of policy gradient methods.
arXiv preprint arXiv:2201.07443, 2022.

[Yuan et al., 2022]
Rui Yuan, Robert M. Gower, and Alessandro Lazaric.
A general sample complexity analysis of vanilla policy gradient,

[Zahavy et al., 2021]
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh.
Reward is enough for convex mdps.
Advances in Neural Information Processing Systems,
34:0 25746–25759, 2021.

[Zhang et al., 2019]
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie.
Why gradient clipping accelerates training: A theoretical
justification for adaptivity.
arXiv preprint arXiv:1905.11881, 2019.

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

[Zhang et al., 2020]
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar.
Global convergence of policy gradient methods to (almost) locally
optimal policies.
SIAM Journal on Control and Optimization, 580
(6):0 3586–3612, 2020b.

§ ORGANIZATION OF THE APPENDIX

<ref> [appendix:defn]Definitions

<ref> [appendix:pg_proofs]Proofs of <ref>

<ref> [appendix:spg_proofs]Proofs of <ref>

<ref> [appendix:entropy]Policy Gradient with Entropy Regularization

<ref> [appendix:pg_entropy]Policy Gradient with Entropy Regularization in the Exact Setting

<ref> [appendix:pg_entropy]Policy Gradient with Entropy Regularization in the Stochastic Setting

<ref> [appendix:pg_entropy_proofs]Proofs of <ref>

<ref> [appendix:spg_entropy_proofs]Proofs of <ref>

<ref> [appendix:experiments]Additional Experiments

<ref> [appendix:extra_lemmas]Extra Lemmas