algorithmic

# Towards Provable Log Density Policy Gradient

Pulkit Katdare
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>Anant A. Joshi∗
Department of Mechanical Engineering
University of Illinois at Urbana-Champaign Katherine Driggs-Campbell
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
Equal contribution.

###### Abstract

Policy gradient methods are a vital ingredient behind the success of modern
reinforcement learning. Modern policy gradient methods, although successful,
introduce a residual error in gradient estimation. In this work, we argue that
this residual term is significant and correcting for it could potentially
improve sample-complexity of reinforcement learning methods. To that end, we
propose log density gradient to estimate the policy gradient, which corrects
for this residual error term. Log density gradient method computes policy
gradient by utilising the state-action discounted distributional formulation.
We first present the equations needed to exactly find the log density gradient
for a tabular Markov Decision Processes (MDPs). For more complex environments,
we propose a temporal difference (TD) method that approximates log density
gradient by utilizing backward on-policy samples. Since backward sampling from
a Markov chain is highly restrictive we also propose a min-max optimization
that can approximate log density gradient using just on-policy samples. We
also prove uniqueness, and convergence under linear function approximation,
for this min-max optimization. Finally, we show that the sample complexity of
our min-max optimization to be of the order of $m^{-1/2}$, where $m$ is the
number of on-policy samples. We also demonstrate a proof-of-concept for our
log density gradient method on gridworld environment, and observe that our
method is able to improve upon the classical policy gradient method by a clear
margin, thus indicating a promising novel direction to develop reinforcement
learning algorithms that require fewer samples.

##  1 Introduction

Policy gradient (PG) methods are a vital ingredient behind the success of
modern reinforcement learning (Silver et al., 2017; John Schulman et al.,
2023; Haarnoja et al., ; Kakade, 2001). The success of PG methods stems from
their simplicity and compatibility with neural network-based function
approximations (Sutton et al., 1999; Baxter & Bartlett, 2001). Although modern
policy gradient methods like PPO and TRPO, have achieved excellent results in
various on-policy tasks (Schulman et al., 2017; 2015), they require extensive
hyper-parameter tuning. Additionally, it has been shown by Ilyas et al. (2020)
that the estimation error between policy gradient estimated by the methods
like PPO and the true policy gradient increases significantly during the
training process. Classical policy gradient methods typically approximate
gradient of the policy using Q-function estimated with discount factor
strictly less than 1, which leads to a error in gradient estimation (Morimura
et al., 2010). In this paper, we demonstrate that this error in indeed
significant, in Figure 1. We propose a novel algorithm to correct for this
error which could potentially lead to a sample efficient reinforcement
learning, thus enabling their deployment over a wide variety of complex
scenarios. We call our method log density gradient. Our approach is based on
the average state-action stationary distribution formulation of reinforcement
learning, which allows for the estimation of policy gradient as a
multiplication of the log density gradient and the reward function (Nachum et
al., 2019; Uehara et al., ). This separation results in an improved
correlation with the true policy gradient and requires fewer hyperparameters.
We show that our method is consistent with the classical policy gradient
theorem (Sutton, 1988) and also prove convergence properties and sample
complexity.

Our main contributions are as follows. 1. A novel method to exactly calculate
policy gradient by using the average state-action discounted formulation of a
reinforcement learning problem. We will also show that policy gradient
estimated in this manner will correct for the residual error (as shown in
Figure 1) usually seen in practical application of classical policy gradient
methods. 2. A model-free Temporal Difference (TD) method for approximating
policy gradient. We provide proof of contraction as well as convergence.
However, there is a major drawback that it requires samples from the backward
Markov chain (described in detail in the paper) which motivates the next
contribution. 3. A min-max optimization which yields the gradient of log
density, and a model free TD method to implement it, with proof of
convergence. We additionally show sample complexity of the order $O(m^{-1/2})$
for the projected version of the proposed TD method, where $m$ is the number
of on-policy samples. Our method is competitive with the sample complexity of
classical vanilla policy gradient methods (Yuan et al., 2022).

Section 2 starts with problem formulation and motivation behind this paper.
Section 3, discusses prior work in policy gradient methods, temporal
difference methods, and min-max problems in off-policy evaluation. Our main
contributions are discussed in detail starting from Section 4 which starts
with rigorously defining log density gradient. Additionally we also propose a
TD approach to estimate log density gradient under strict reversibility
assumptions, and we describe the issue caused by this assumption. In section
5, to overcome this issue to propose a min-max variant that allows us to
estimate log density gradient algorithm using empirical samples. We finally
demonstrate a proof-of-concept of our algorithm in Section 6 which shows that
log density gradient can be potentially sample efficient as compared to
classical policy gradient methods.

##  2 Background and Motivation

Notation: we let $(\cdot)^{T}$ denote matrix transpose, and let $e$ represent
the vector of ones, the size of which would be clear from context.

We define Markov Decision Process (MDP) as a 6-tuple of
$({\mathcal{S}},\mathcal{A},\mathcal{P},r,\gamma,d_{0})$. Here,
${\mathcal{S}}$ is a finite state space of the MDP, $\mathcal{A}$ is a finite
action space, $\mathcal{P}$ is the transition probability matrix, $r$ is the
reward function and $d_{0}$ is the initial distribution. The reinforcement
learning problems is optimise for a policy
$\pi:{\mathcal{S}}\rightarrow\Delta(\mathcal{A})$ that maximizes
$J_{\gamma}(\pi)$, defined as

$\displaystyle J_{\gamma}(\pi)$
$\displaystyle:=(1-\gamma)\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}\sim
d_{0},a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t})],\,\text{
for }\gamma\in[0,1)$ $\displaystyle J_{1}(\pi)$
$\displaystyle:=\lim_{\mathcal{T}\rightarrow\infty}\mathbb{E}[\frac{1}{\mathcal{T}}\sum_{t=0}^{\mathcal{T}}\gamma^{t}r(s_{t},a_{t}),s_{0}\sim
d_{0},a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t})],\,\text{
for }\gamma=1,$

where $\gamma\in[0,1]$ is the discounting factor which accounts for the impact
of future rewards in present decision making. When $\gamma=1$, $J_{1}(\pi)$
the scenario is called the average reward formulation. Most practical problems
in reinforcement learning typically aim to solve for an optimal policy
$\pi^{*}=\arg\max_{\pi}J_{1}(\pi)$. Modern reinforcement learning methods aim
to parameterise policy with a set of parameters $\theta\in\mathbb{R}^{n}$,
where $n$ is the dimensions of the parameter space. We refer to such
paremterisation as $\pi_{\theta}$. This kind of parameterisation enables us
search for optimal set of parameters $\theta^{*}$ instead of a search over
${\mathcal{S}}\times\mathcal{A}$ which in practice could be very large. We
define

$\displaystyle\theta^{*}:=\operatorname*{arg\,max}_{\theta\in\mathbb{R}^{n}}J_{1}(\pi_{\theta}).$

The Q-function $Q^{\pi_{\theta}}_{\gamma}$ is commonly used function used to
describe the performance of an RL agent. Q-function calculates the long term
(discounted) rewards accumulated by an agent following a fixed policy
$\pi_{\theta}$ while starting from a state $s\in{\mathcal{S}}$ and taking an
action $a\in\mathcal{A}$

$\displaystyle Q_{\gamma}^{\pi_{\theta}}(s,a)$
$\displaystyle:=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a,a_{t}\sim\pi_{\theta}(\cdot|s_{t}),s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t})]$
(1a)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[Q_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})]$
(1b)

Where, equation 1b is called the Bellman Equation. Bellman equation is
popularly used to estimate the Q-function using just empirical data collected
on the MDP. Q-function approximation methods typically use $\gamma<1$ for
stable estimation of the Q-function. We also similarly define value function
$V^{\pi_{\theta}}_{\gamma}(s)=\mathbb{E}_{a\sim\pi_{\theta}(\cdot|s)}[Q^{\pi_{\theta}}_{\gamma}(s,a)]$.

Modern RL algorithms generally solve for $\theta^{*}$ by estimating the
gradient of policy performance $J_{\gamma}(\pi_{\theta})$ with respect to
policy parameters $\theta$. This is also commonly referred to as the policy
gradient theorem $\nabla_{\theta}J_{1}(\pi_{\theta})$ (Sutton et al., 1999)
which says

$\displaystyle\nabla_{\theta}J_{\gamma}(\pi_{\theta})=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[Q^{\pi_{\theta}}_{\gamma}(s,a)\cdot\nabla_{\theta}\log{\pi_{\theta}}(a|s)],\quad\gamma\in[0,1].$
(2)

Here, $d^{\pi_{\theta}}_{\gamma}$ is the average state-action discounted
stationary distribution, which is defined as the cumulative sum of discounted
state-action occupancy across the time horizon.

$\displaystyle d_{\gamma}^{\pi_{\theta}}(s,a)$
$\displaystyle:=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s,a_{t}=a|s_{0}\sim
d_{0},a_{t}\sim\pi_{\theta}(s_{t}),s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t}),\gamma<1)$
(3a) $\displaystyle d_{1}^{\pi_{\theta}}(s,a)$
$\displaystyle:=\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{t=0}^{T}\mathbb{P}(s_{t}=s,a_{t}=a|s_{0}\sim
d_{0},a_{t}\sim\pi_{\theta}(s_{t}),s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t}),\gamma=1).$
(3b)

In this paper we make a standard assumption that the Markov chain induced by
policy $\pi_{\theta}$ is ergodic. In particular, this implies that
$d_{\gamma}^{\pi_{\theta}}(s,a)>0$ for all state action pairs $(s,a)$
(Puterman, 2014). In scenarios where we are trying to optimize for
$J_{1}(\pi)$, estimating the policy gradient becomes difficult. This is
because the Bellman equation cannot be used to estimate Q-function for
$\gamma=1$. As a compromise policy gradient for average reward scenarios are
instead approximated by calculating the Q-function for a discounting factor
$\gamma<1$, but close to 1, and using that estimate in the policy gradient
equation 2

$\displaystyle\hat{\nabla}_{\theta}J_{1}(\pi_{\theta})$
$\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{1}}[{Q^{\pi_{\theta}}_{1}(s,a)}\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)],$
(4a) $\displaystyle\approx\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{1}}[{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}Q^{\pi_{\theta}}_{\gamma}(s,a)}\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)],\quad\gamma<1.$
(4b)

In this paper we argue that the policy gradient calculated in this manner
induces a significant residual error, which keeps on compounding as the
reinforcement learning training proceeds even leading to a sub optimal
solution. The following equation, derived in Proposition 2 characterizes that
error,

$\displaystyle\nabla_{\theta}J_{1}(\pi_{\theta})$
$\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{1}}[\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{Q^{\pi_{\theta}}_{\gamma}(s,a)}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)}]+\underbrace{(1-\gamma)\mathbb{E}_{(s,a)\sim
d_{1}^{\pi_{\theta}}}[\nabla_{\theta}\log d_{1}^{\pi_{\theta}}(s)\cdot
V^{\pi_{\theta}}_{\gamma}(s)]}_{\text{{Residual Error}}}$ (5)

inline]plots for justifying the significance of the residual error In this
paper, we prove that this residual error is significant. What more, we also
propose another method to exactly obtain the policy gradient, which we call as
the log density gradient. Our estimation of log density gradient utilises
average state-action discounted distributional formulation of a reinforcement
learning problem which re-states $J_{\gamma}(\pi)$ as expectation under
$d^{\pi_{\theta}}_{\gamma}$ (Nachum et al., 2019; Uehara et al., ) as

$\displaystyle J_{\gamma}(\pi)=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[r(s,a)].$

Under this formulation, policy gradient can similarly be obtained as

$\displaystyle\nabla_{\theta}J_{\gamma}(\pi)=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}(s,a)\cdot r(s,a)].$ (6)

We refer to $\nabla_{\theta}\log d^{\pi_{\theta}}_{\gamma}$ as the log density
gradient. A key advantage of log density gradient is that it would allow us to
approximate policy gradient for average reward scenarios in a provable manner.
In this work, we show that log density gradient can be approximated even under
average reward scenarios ($\gamma=1$). To that end, we first propose a model
based approach to approximate the log density gradient for tabular scenarios.
Under reversibility assumptions we then show that this log density gradient
can also be approximated using TD method. Since reversibility assumption is
highly restrictive, we finally propose a min-max version of log density
gradient which allows to approximate $\nabla_{\theta}\log d^{\pi_{\theta}}$
using empirical samples. Our experimental further show that this manner of
policy gradient estimation can potentially make reinforcement learning sample
efficient, thus helping them scale.

##  3 Related Work

In this section we will discuss existing studies in policy gradient methods
including the framework of log density gradient first introduced by Morimura
et al. (2010). We also briefly discuss density ratio learning methods which
have been very popular in off-policy evaluation. A short discussion on
Temporal Difference (TD) learning methods may be found in Appendix 8.1.

###  3.1 Policy Gradient Methods

Policy gradient methods are a widely studied topic in reinforcement learning.
One of the earliest works in this area proposed a closed-form solution for
evaluating policy gradients called the policy gradient theorem (Sutton et al.,
1999). Initially implementations for policy gradient methods used episodic
estimates to update policy parameters (Williams, 1992) and GPOMDP (Baxter &
Bartlett, 2001). Unfortunately this way of implementing policy gradient
suffered from high variance, thus inhibiting scalability to large problem
spaces (Schulman et al., 2016). To address this problem actor-critic methods
approximate the Q-function or advantage function using an additional neural
network, which are then used to update the policy (Mnih et al., 2016; Schulman
et al., 2016). Furthermore policy gradient methods were even designed to make
them compatible with deterministic policies (Lillicrap et al., 2016; Silver et
al., 2014). Recently Trust region methods, such as Trust Region Policy
Optimization (TRPO) Schulman et al. (2015) and Proximal Policy Optimization
(PPO) Schulman et al. (2017), update policies while ensuring monotonic
performance improvement. In this work, we argue that although these methods
have been successful, their practical implementation still ignores a residual
error, correcting for which may increase sample efficiency of policy gradient
methods. To the best of our knowledge, Log density gradient has only been
discussed in Morimura et al. (2010). Here, the authors propose a TD method to
estimate log density gradient for average reward scenarios by using reversible
backward Markov chain. In this work, we re-introduce the idea of log density
gradient but for a general discounting factor $\gamma\in[0,1]$, as opposed to
the case of $\gamma=1$ considered in Morimura et al. (2010). We also show that
this method of estimating the log density gradient is unique and tends to
converge under linear function approximations. We further propose a min-max
version of estimating log density gradient by utilizing Fenchel duality. We
also prove that this min-max algorithm converges to a unique solution under
linear function approximation assumption.

Figure 1: For the average reward scenario, performance of classical policy
gradient (red) algorithm as compared to log density gradient (green) algorithm
over a $n\times n$ gridworld environment, for $n=5,10$. We observe that log
density gradient algorithm consistently converges to better policy
performance. Theoretical calculated solutions are used for implementation.

###  3.2 Density Ratio Learning

Off-policy evaluation estimates the performance of a target policy $\pi$ using
an offline dataset generated by a behavior policy $\mu$ (Voloshin et al.,
2019; Katdare et al., ). This is done by estimating the average state-action
density ratio $\frac{d^{\pi}_{\gamma}}{d^{\mu}}$, which allows approximation
of the target policy’s performance. In this work, we are primarily interested
in the DICE class of off-policy evaluation algorithms (Zhang et al., 2020b;
Nachum et al., 2019; Zhang et al., 2020a). These algorithms typically
approximate the divergence (for some $f-$divergence of their choice) between
the two distributions $d^{\pi}$ and $d^{\mu}$ in their convex dual form,
eliminating the need to obtain samples from $d^{\pi}$, which results in a min-
max form optimization problem. Inspired by the DICE class of algorithms we too
propose a min-max form of estimating the log density gradient. We show that
such a method of estimating log density gradient converges to the true policy
under linear function approximations assumptions. We also show that the sample
complexity of such an estimator is of the order $(n^{-1/2})$, with $n$ being
the number of on-policy samples.

##  4 Log Density Gradient

In this section, we introduce log density gradient and further show that
classical policy gradient typically ignores a residual error which may be
significant. We then propose a TD version of our log density gradient method
that estimates the policy gradient without a need to account for this error.

###  4.1 Model Based Log Density Gradient

The log density gradient method attempts to estimate the gradient of log of
average state-action discounted stationery distribution
$d^{\pi_{\theta}}_{\gamma}$. We start by observing that
$d_{\gamma}^{\pi_{\theta}}$ satisfies an identity called the Bellman flow
equation Liu et al. (2018).

######  Lemma 1.

The average state-action density distribution satisfies the following identity
for all $\gamma\in[0,1]$,

$\displaystyle d_{\gamma}^{\pi_{\theta}}(s^{\prime})$
$\displaystyle=(1-\gamma)d_{0}(s^{\prime})+\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)$
(7)

We prove this result in the appendix 8.3. Note that this equation is similar
to the Bellman equation but in a backward manner, which means, we need samples
from the backward conditional distribution (defined rigorously in Section
4.2). It can also be understood as a form of flow conservation, wherein the
flow out of state $s^{\prime}$ (LHS) would be equal to the flow into
$s^{\prime}$ (RHS).

######  Lemma 2.

For all $\gamma\in[0,1]$ the solution to the following optimisation is unique
and equal to $d_{\gamma}^{\pi_{\theta}}$.

$\displaystyle\operatorname*{arg\,min}_{w:{\mathcal{S}}\rightarrow\mathbb{R}}$
$\displaystyle\sum_{s^{\prime}}\left(w(s^{\prime})-(1-\gamma)d_{0}(s^{\prime})+\gamma\sum_{s,a}w(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)\right)^{2}+\frac{\lambda}{2}(\sum_{s}w(s)-1)^{2}$
(8)

Detailed proof can be found in the appendix 8.4. Intuitively speaking, the
term $\frac{\lambda}{2}(\sum_{s}w(s)-1)^{2}$ is redundant for $\gamma<1$. It
becomes useful for $\gamma=1$ to ensure uniqueness. Although it is hard to
estimate a closed form solution for $\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}$, it is still possible to estimate it numerically.
Using equation 7 we can similarly calculate an equivalent identity for
$\nabla_{\theta}\log d_{\gamma}^{\pi_{\theta}}$

$\displaystyle d_{\gamma}^{\pi_{\theta}}(s^{\prime})\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s^{\prime})$
$\displaystyle=\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a).$ (9)

Multiplying both sides by $\pi_{\theta}(a^{\prime}|s^{\prime})$ and recalling
that
$d_{\gamma}^{\pi_{\theta}}(s,a)=d_{\gamma}^{\pi_{\theta}}(s)\pi_{\theta}(a|s)$,
we obtain

$\displaystyle
d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})(\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})-\nabla_{\theta}\log\pi(a^{\prime}|s^{\prime}))=\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})$
(10)

Similar to Lemma 2 we can estimate $\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}$ by solving for the equation 10 above. To that end,
we propose the following optimization (where $\lambda>0$ is a fixed
regularizer)

$\displaystyle\min_{w:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{n}}\bigg{\\{}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d_{\gamma}^{\pi_{\theta}}}\|\nu(s^{\prime},a^{\prime})\|^{2}+\frac{\lambda}{2}\Big{\|}E_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[w(s^{\prime},a^{\prime})]\Big{\|}^{2}\bigg{\\}}$
(11)
$\displaystyle\nu(s^{\prime},a^{\prime}):=d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})(w(s^{\prime},a^{\prime})-\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime}))-\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})w(s,a)$

######  Lemma 3.

The solution to equation 11 is unique and equal to $\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}$ for all $\gamma\in[0,1]$.

We describe the proof for this Lemma in the appendix 8.5. It is worth noting
that, the constraint $\frac{\lambda}{2}\|E_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[w(s^{\prime},a^{\prime})]\|^{2}$ is only useful for
$\gamma=1$. The proof follows from the fact that the solution to the equation
11 can be written in a linear form $A\cdot w=b$ and showing that A is
invertible. It is worth reiterating that, once we have an estimate
$\nabla_{\theta}\log d_{\gamma}^{\pi_{\theta}}$, we can use this estimate to
approximate the policy gradient using equation 6. We will now recall two
important properties of log density gradient.

######  Proposition 1.

The policy gradient method as mentioned in equation 6 is exactly equal to the
classical policy gradient (Sutton et al., 1999) as mentioned in equation 2.

Detailed proof for this proposition can be found in Appendix 8.2. In essence
this means that log density gradient calculates the same policy gradient but
using a different formulation. We show next that this formulation allows us to
correct for the residual error in policy approximation which is typically
ignored in many actor-critic implementations of policy gradient methods.

######  Proposition 2.

The following identity, stated in equation 5, is true

$\displaystyle\nabla_{\theta}J_{1}(\pi_{\theta})$
$\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{1}}[\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{Q^{\pi_{\theta}}_{\gamma}(s,a)}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)}]+\underbrace{(1-\gamma)\mathbb{E}_{(s,a)\sim
d_{1}^{\pi_{\theta}}}[\nabla_{\theta}\log d_{1}^{\pi_{\theta}}(s)\cdot
V^{\pi_{\theta}}_{\gamma}(s)]}_{\text{{Residual Error}}}$

###### Proof.

From the definition of log density gradient equation 6 we have
$\nabla_{\theta}J_{1}(\pi_{\theta})=\mathbb{E}_{(s,a)\sim
d_{1}^{\pi_{\theta}}}[\nabla_{\theta}\log d_{1}^{\pi_{\theta}}(s,a)\cdot
r(s,a)]$. Let $\gamma<1$, and we use the Bellman equation 1b to obtain

$\displaystyle\nabla_{\theta}J_{1}(\pi_{\theta})$
$\displaystyle=\mathbb{E}_{(s,a)\sim d_{1}^{\pi_{\theta}}}[\nabla_{\theta}\log
d_{1}^{\pi_{\theta}}(s,a)\cdot(Q^{\pi_{\theta}}_{\gamma}(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}[V^{\pi_{\theta}}_{\gamma}(s^{\prime})])]$
(12a) $\displaystyle=\mathbb{E}_{(s,a)\sim
d_{1}^{\pi_{\theta}}}[(\nabla_{\theta}\log
d_{1}^{\pi_{\theta}}(s)+\nabla_{\theta}\log{\pi_{\theta}}(a|s))\cdot(Q^{\pi_{\theta}}_{\gamma}(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}[V^{\pi_{\theta}}_{\gamma}(s^{\prime})])]$
(12b) $\displaystyle=\mathbb{E}_{(s,a)\sim
d_{1}^{\pi_{\theta}}}[Q^{\pi_{\theta}}_{\gamma}(s,a)\cdot\nabla_{\theta}\log\pi_{\theta}(a|s)]+(1-\gamma)\mathbb{E}_{s\sim
d_{1}^{\pi_{\theta}}}[\nabla_{\theta}\log d_{1}^{\pi_{\theta}}(s,a)\cdot
V^{\pi_{\theta}}(s)]$ (12c) Here, we go from equation 12a to 12b by utilizing
$\nabla_{\theta}\log d^{\pi_{\theta}}_{\gamma}(s,a)=\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}(s)+\nabla_{\theta}\log\pi_{\theta}(a|s)$. We finally
go from 12b to 12c by using a key identity of log density gradient equation
10.

using identity for log density gradient as shown in the equation 9. Note that
the first term in equation 12b is the practical instantiation of classical
policy gradient theorem, while the second term $(1-\gamma)\mathbb{E}_{s\sim
d^{\pi_{\theta}}_{1}}[\nabla_{\theta}\log d^{\pi_{\theta}}_{1}(s)\cdot
V^{\pi_{\theta}}_{\gamma}(s)]$ being the residual error. This completes the
proof. ∎

Actor-Critic implementation of policy gradient methods first approximate the
Q-function using a discounting factor $\gamma$ strictly less than 1 and then
approximate the policy gradient $\nabla_{\theta}J_{1}(\pi_{\theta})$ using
equation 4b. This leads to a residual error in policy gradient approximation
as shown in Proposition 2. We believe that correcting for this gradient
estimation can potentially make policy gradient algorithms sample efficient
and scalable to complex problems.

Although the solution to equation equation 11 is unique, solving it requires
access the transition matrix $\mathcal{P}$ which is impractical for complex
environments. Additionally, the log density gradient estimation also becomes
computationally infeasible with exponential scaling of state-action. We thus
propose a temporal difference approach to estimate log density gradient from
empirical data next .

###  4.2 Temporal Difference Log Density Gradient

To propose an update equation for temporal difference (TD) method, we first
begin with re-arranging few terms in equation 10 for log density gradient.

$\displaystyle\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})=\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime})+\gamma\sum_{s,a}\frac{d^{\pi_{\theta}}_{\gamma}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})}{d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})}\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}(s,a)$

We define the backward distribution of $(s,a)$ given $(s^{\prime},a^{\prime})$
as

$\displaystyle\mathcal{P}_{b}(s,a|s^{\prime},a^{\prime})\coloneqq\frac{d^{\pi_{\theta}}_{\gamma}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})}{d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})}=\frac{d^{\pi_{\theta}}_{\gamma}(s,a)\mathcal{P}^{\pi_{\theta}}(s^{\prime},a^{\prime}|s,a)}{d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})}$

which is a consequence of Bayes’ rule. The summation therefore becomes an
expectation under $\mathcal{P}_{b}$. The log density gradient is therefore
said to follow a backward recursion and it requires samples from backward
conditional probability $\mathcal{P}_{b}$ to estimate log density
gradient111Although for $\gamma=1$ we can use samples from $\mathcal{P}$ as
well (Morimura et al., 2010) . We first generalize algorithm of Morimura et
al. (2010), who do it only for $\gamma=1$, to estimate log density gradient
$w$ for all discounting factor $\gamma\in[0,1]$ in form of a temporal
difference (TD(0)) method where our update equation is

$\displaystyle w(s^{\prime},a^{\prime})\leftarrow
w(s^{\prime},a^{\prime})+\alpha[\gamma
w(s,a)+g(s^{\prime},a^{\prime})-w(s^{\prime},a^{\prime})]$ (13)

with $(s^{\prime},a^{\prime})\sim
d_{\gamma}^{\pi_{\theta}},(s,a)\sim\mathcal{P}_{b}(\cdot|s^{\prime},a^{\prime})$
and
$g(s^{\prime},a^{\prime}):=\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime})$.
Define operator $Y_{\gamma}$ to capture the behaviour of update rule equation
13 after taking expectation,

$\displaystyle(Y_{\gamma}\cdot
w)(s^{\prime},a^{\prime}):=\gamma\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[w(s,a)|(s^{\prime},a^{\prime})]+g(s^{\prime},a^{\prime}).$

We can write this in matrix form as follows,

$\displaystyle Y_{\gamma}\cdot W=\gamma
D_{\pi_{\theta}}^{-1}\mathcal{P}_{\pi_{\theta}}^{\top}{D_{\pi_{\theta}}}W+G$
(14)

where, $W\in\mathbb{R}^{|{\mathcal{S}}|\cdot|\mathcal{A}|\times n}$ is the
matrix with every row corresponding to $w(s,a)$ for each state-action pair
$(s,a)$. Similarly, $G\in\mathbb{R}^{|{\mathcal{S}}|\cdot|\mathcal{A}|\times
n}$ has its rows as $\nabla_{\theta}\log\pi_{\theta}$ for each state-action
pair. Let
$\mathcal{P}_{\pi_{\theta}},{D_{\pi_{\theta}}}\in\mathbb{R}^{|{\mathcal{S}}|\cdot|\mathcal{A}|\times|{\mathcal{S}}|\cdot|\mathcal{A}|}$
where
$(\mathcal{P}_{\pi_{\theta}})_{((s,a),(s^{\prime},a^{\prime}))}=\mathbb{P}^{\pi_{\theta}}(s^{\prime},a^{\prime}|s,a)$
and ${D_{\pi_{\theta}}}$ is a diagonal matrix whose every element correspond
to $d_{\gamma}^{\pi_{\theta}}$ for each state-action pair. We use this matrix
form for the operator $Y_{\gamma}$ in the proof of the following lemma.

######  Lemma 4.

Let $w_{0}\in\Delta({\mathcal{S}},\mathcal{A})$ be an arbitrary initial guess.
Let $w_{k}=Y_{\gamma}\cdot w_{k-1}$ for all natural numbers $k\geq 1$. For
$\gamma\in[0,1)$, the operator $Y_{\gamma}$ is a contraction, and
$\\{w_{k}\\}_{k\geq 0}$ converges to a unique fixed point $\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}$.

Detailed proof of Lemma 4 can be found in Appendix 8.6. Extension of Lemma 4
to linear function approximation, and proof of convergence for the same, can
be found in the Appendix 8.7. Although TD methods are known to converge, they
still suffer from two problems. One, the access to samples from backward
conditional probability. Two, scalability to large problem spaces. We attempt
to solve both of these problems in the next section where we propose a min-max
optimization procedure for estimating the log density gradient.

##  5 Min-Max Log Density Gradient

In this section, we propose another approach for evaluating the log density
gradient which uses the min-max form for optimization which does not need
samples from the backward distribution. Min-max optimizations also allow us to
use a large variety of function classes like neural networks to estimate log
density gradient.

Let us return to the loss function that we initially propose in equation 11.
Classical machine learning algorithms typically require loss function in the
form of an expectation under a distribution. These kind of algorithms are
often called as Empiricial Risk Minimization, which allows us to approximate
the loss using samples from that distribution. Consider a modified form of the
optimization proposed in equation 11 (the modification is that
$\delta(s^{\prime},a^{\prime})$ is divided by
$d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})$ where the ergodicity
assumption ensures this operation is well defined),

$\displaystyle\operatorname*{arg\,min}_{w\in\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{n}}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d_{\gamma}^{\pi_{\theta}}}\left[\left\|\frac{\nu(s^{\prime},a^{\prime})}{d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})}\right\|^{2}\right]+\frac{\lambda}{2}\|\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[w(s,a)]\|^{2}$ (15)
$\displaystyle\nu(s^{\prime},a^{\prime}):=d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})(w(s^{\prime},a^{\prime})-\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime}))-\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi(a^{\prime}|s^{\prime})w(s,a)$

The denominator term $d^{\pi_{\theta}}_{\gamma}$ is added to simplify the
final optimization, which we shall see soon. We also add the term
$\frac{\lambda}{2}\|\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[w(s,a)]\|^{2}$ to satisfy one of the properties of
the gradient of log density $\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a)]=0$.

It is worth noting that equation 15 is just a re-weighting of equation 11 with
the $\frac{1}{d^{\pi_{\theta}}_{\gamma}(s,a)}$. This implies that the optimal
solution for the both the equation is the same because the minimum value for
both the optimization can only be reached when $w(s,a)=\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}(s,a)$. By exploiting the Fenchel-duality, we can re-
write this optimization in the minimax form (Rockafellar, 2015; Zhang et al.,
2020b).

$\displaystyle\arg\min_{w:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}}\max_{f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d},\tau\in\mathbb{R}^{d}}L_{\gamma}(w,f,\tau):=\bigg{\\{}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d_{\gamma}^{\pi_{\theta}}}[f(s^{\prime},a^{\prime})\cdot
w(s^{\prime},a^{\prime})]$
$\displaystyle-\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d_{\gamma}^{\pi_{\theta}}}[f(s^{\prime},a^{\prime})\cdot\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime})]-\gamma\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[f(s^{\prime},a^{\prime})]\cdot
w(s,a)]$ $\displaystyle-\frac{1}{2}\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[\|f(s^{\prime},a^{\prime})\|^{2}]+\lambda(\tau\cdot\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[w(s,a)]-\frac{1}{2}\|\tau\|^{2})\bigg{\\}}$ (16)

In many cases searching over all set of functions is not possible, hence we
search over tractable function classes $\mathcal{W},\mathcal{F}$ and the aim
is to approximate

$\displaystyle\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}\approx\arg\min_{w\in\mathcal{W}}\max_{f\in\mathcal{F},\tau\in\mathbb{R}^{n}}L_{\gamma}(w,f,\tau).$

Such a practical consideration allows us to use different types of function
approximators like linear function approximation, neural networks, and
reproducible kernel Hilbert spaces (RKHS). We will now provide an update rule
to solve equation 16 under linear function approximation. For that we choose a
feature map $\Phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d}$ and
parameters $\alpha,\beta\in\mathbb{R}^{d\times n}$ that need to be learnt, so
that we can approximate the optima of equation 16, $w^{*}(s,a)$ and
$f^{*}(s,a)$ with $\alpha^{T}\Phi(s,a)$, and $\beta^{T}\Phi(s,a)$
respectively, for each state action pair $(s,a)$. The update rule is

$\displaystyle\delta_{t}=\Phi_{t}\Phi_{t}^{T}-\gamma\Phi_{t}(\Phi_{t}^{\prime})^{T}$
(17a)
$\displaystyle\alpha_{t+1}^{T}=\alpha_{t}^{T}-\varepsilon_{t}(\beta^{T}\delta_{t}+\lambda(\tau\Phi_{t}^{T}))$
(17b)
$\displaystyle\beta_{t+1}^{T}=\beta_{t}^{T}+\varepsilon_{t}(\alpha_{t}^{T}\delta_{t}-g_{t}\Phi_{t}^{T}-\beta_{t}^{T}\Phi_{t}\Phi_{t}^{T})$
(17c)
$\displaystyle\tau_{t+1}=\tau_{t}+\varepsilon_{t}(\lambda(\alpha_{t}^{T}\Phi_{t}-\tau_{t}))$
(17d)

where, $\Phi_{t}:=\Phi(s_{t},a_{t})$ is the feature encountered at time $t$,
$g_{t}:=\nabla_{\theta}\log\pi_{\theta}(a_{t}|s_{t})$, and
$\Phi_{t}^{\prime}:=\Phi_{t}(s_{t}^{\prime},a_{t}^{\prime})$ for
$(s_{t},a_{t})\sim
d^{\pi_{\theta}}_{\gamma},s_{t}^{\prime}\sim\mathcal{P}(\cdot|s_{t},a_{t}),a_{t}^{\prime}\sim\pi_{\theta}(a_{t}^{\prime}|s_{t}^{\prime})$.
We first re-write the updates in equation 17 in form of
$d_{t}=[\alpha_{t},\beta_{t},\tau_{t}^{T}]$ so that the updates can be written
in matrix form $d_{t+1}=d_{t}+\varepsilon_{t}(G_{t+1}d_{t}+h_{t+1})$, where,
$G_{t+1},h_{t+1}$ are as follows,

$\displaystyle G_{t+1}$
$\displaystyle:=\begin{bmatrix}0&-A_{t}&-\lambda\Phi_{t}\\\ A_{t}&-C_{t}&0\\\
\lambda\Phi_{t}^{T}&0&-\lambda\end{bmatrix},\quad h_{t+1}:=\begin{bmatrix}0\\\
-B_{t}\\\ 0\end{bmatrix}$

and
$A_{t}:=(\Phi_{t}\Phi_{t}^{T}-\gamma\Phi_{t}(\Phi_{t}^{\prime})^{T}),B_{t}:=\Phi
g_{t}^{T},C_{t}:=\Phi_{t}\Phi_{t}^{T}$. We can calculate the expectation for
each of these matrices as follows,

$\displaystyle
G:=\mathbb{E}_{p}[G_{t+1}]=\begin{bmatrix}0&-A&-\lambda\Psi{D_{\pi_{\theta}}}e\\\
A&C&0\\\ \lambda e^{T}{D_{\pi_{\theta}}}\Psi^{T}&0&-\lambda\end{bmatrix},\quad
h:=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[h_{t+1}]=\begin{bmatrix}0\\\ -B\\\ 0\end{bmatrix}$

Here, each column of $\Psi\in\mathbb{R}^{|\mathcal{S}|\cdot|\mathcal{A}|\times
n}$ is the feature vector $\Phi(s,a)$, for each
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $e\in\mathbb{R}^{n}$ is a vector of
1’s at every element. We can similarly write
$A=\Psi{D_{\pi_{\theta}}}(I-\gamma
P_{\pi_{\theta}})\Psi^{T},B=\Psi{D_{\pi_{\theta}}}G^{T},C=\Psi{D_{\pi_{\theta}}}\Psi^{T}$
and $E_{p}[\cdot]:=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}},s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[\cdot]$.
We can now prove the convergence of linear function approximation under the
following key assumptions.

######  Assumption 1.

  1. 1.

The matrix $\Psi$ has linearly independent columns.

  2. 2.

The matrix $A$ is non-singular or the regularizer $\lambda>0$.

  3. 3.

The feature matrix $\Phi$ has uniformly bounded second moments.

######  Theorem 1.

Under the assumptions 1, the update equation 17 converges in probability to a
unique solution. That is, $\lim_{t\rightarrow\infty}d_{t}=G^{-1}h$ in
probability.

The detailed proof is provided in Appendix 8.8. The proof is similar to (Zhang
et al., 2020b, Theorem 2) and invokes theorem 2.2 Borkar & Meyn (2000).

We provide a sample complexity analysis for a projected version of the update
rule equation 17. To that end, we propose Algorithm 1 called the Projected Log
Density Gradient. We choose closed, bounded and convex sets
$X\subset\mathbb{R}^{d\times n},Y\subset\mathbb{R}^{d\times
n},Z\subset\mathbb{R}^{1\times n}$ and define a projection operator
$\Pi_{X},\Pi_{Y},\Pi_{Z}$ that project our variables
$\alpha_{t},\beta_{t},\tau_{t}$ onto $X,Y,Z$ respectively. Moreover, we choose
a learning rate $\\{\varepsilon_{t}\\}_{t=1}^{m}$ where we run the algorithm
for $m$ steps. The details of the choice of learning rate are found in
Appendix 8.9.

######  Theorem 2.

Under assumptions 1 for $(\bar{\alpha},\bar{\beta},\bar{\tau})$ obtained from
Algorithm 1 after $m$ steps, the optimality gap
$\epsilon_{g}(\bar{\alpha}\bar{\beta},\bar{\tau})$ (defined below) is bounded
with probability $1-\delta$ as follows,

$\displaystyle\epsilon_{g}(\bar{\alpha},\bar{\beta},\bar{\tau}):=\max_{(\beta,\tau)\in{Y\times
Z}}L(\bar{\alpha},\beta,\tau)-\min_{\alpha\in
X}L(\alpha,\bar{\beta},\bar{\tau})\leq
C_{0}\sqrt{\frac{5}{m}}(8+2\log\frac{2}{\delta})\text{ w.p. }1-\delta$

where, $C_{0}$ is a constant which is a function of the sets $X,Y,Z$, and the
second moment of $\Phi$.

We present the proof of this result in appendix 8.9. This result essentially
shows us that the upper-bound for log density gradient estimation requires
$O(\frac{1}{\sqrt{m}})$ (where $m$ is the number of steps the algorithm runs
for) samples to learn an accurate estimation.

Algorithm 1 Projected Log Density Gradient

1: for $t=1,2,...,m$ do:

2: $\delta_{t}=\Phi_{t}\Phi_{t}^{T}-\gamma\Phi_{t}(\Phi_{t}^{\prime})^{T}$

3:
$\alpha_{t+1}^{T}=\Pi_{X}(\alpha_{t}^{T}-\varepsilon_{t}(\beta^{T}\delta_{t}+\lambda(\tau\Phi_{t}^{T})))$

4:
$\beta_{t+1}^{T}=\Pi_{Y}(\beta_{t}^{T}+\varepsilon_{t}(\alpha_{t}^{T}\delta_{t}-g_{t}\Phi_{t}^{T}-\beta_{t}^{T}\Phi_{t}\Phi_{t}^{T}))$

5:
$\tau_{t+1}=\Pi_{Z}(\tau_{t}+\varepsilon_{t}(\lambda(\alpha_{t}^{T}\Phi_{t}-\tau_{t})))$

6: Return $\bar{\alpha}$, $\bar{\beta}$, $\bar{\tau}$Where,
$\bar{\alpha}=\frac{\sum_{i=1}^{n}\varepsilon_{i}\alpha_{i}}{\sum_{i=0}^{n}\varepsilon_{i}}$,
$\bar{\beta}=\frac{\sum_{i=1}^{n}\varepsilon_{i}\beta_{i}}{\sum_{i=0}^{n}\varepsilon_{i}}$,
$\bar{\tau}=\frac{\sum_{i=1}^{n}\varepsilon_{i}\tau_{i}}{\sum_{i=0}^{n}\varepsilon_{i}}$

##  6 Experiments

In this section, we present a proof of concept for our log density gradient
estimation on two sets of environments $5\times 5$ and $3\times 3$ gridworld
environment (Towers et al., 2023). For the gridworld experiments, we
approximate log density gradient by using linear function approximation. Here,
the features are
$\phi:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R^{|\mathcal{S}|\cdot|\mathcal{A}|}}$
such that it maps every state to the corresponding standard basis vector. Our
results for $5\times 5$ are in Figure 2 and for $3\times 3$ in Appendix
LABEL:app:num-fig Figure 3.

We compare our algorithm against 3 different baselines. The first is
theoretical log density gradient as described in Lemma 3. The second baseline
implements REINFORCE algorithm, which is the practical rendition of the policy
gradient theorem (Williams, 1992). The third is theoretical policy gradient
method which exactly computes the classical policy gradient theorem, as in
equation 4b (Sutton et al., 1999).

We observe in that both log density gradient approaches are more sample
efficient than both policy gradient approaches. This is because policy
gradient methods approximate the gradient for average reward scenarios
($\gamma=1$) by estimating a Q-function for a discounting factor less than 1.
Moreover, we observe that our method tends to outperform REINFORCE with much
reduced variance. Our approach is always very close in performance to the
theoretical log density gradient which serves to validate correctness of our
algorithm. In $5\times 5$ gridworld we also observe our algorithm to
outperforms theoretical log density gradient. This is because, theoretical log
density gradient suffers from some numerical computation issues arising from
average reward scenarios.

Figure 2: For $5\times 5$ gridworld, comparison of Log Density Gradient
algorithms (in light green) as compared to REINFORCE (light red), theoretical
policy gradient (gray) and theoretical log density gradient (blue). We observe
that our empirical algorithm comfortably outperforms the other baselines.
Figure 3: For $3\times 3$ gridworld, comparison of Log Density Gradient
algorithms (in light green) as compared to REINFORCE (light red), theoretical
policy gradient (gray) and theoretical log density gradient (blue). We observe
that our empirical algorithm comfortably outperforms the other baselines.

##  7 Conclusion and Future Work

We present log density gradient algorithm that estimates policy gradient using
state-action discounted formulation of a reinforcement learning problem. We
observe that policy gradient estimated in this manner, corrects for a residual
error common in many reinforcement learning tasks. We show that with a known
model, we can exactly calculate the gradient of the log density by solving two
sets of linear equations. We further propose a TD(0) algorithm to implement
the same, but it needs samples from the backward Markov chain, which becomes
too restrictive. Therefore, we propose a min-max optimization that estimates
log density gradient using just on-policy samples. We not only prove
theoretical properties like convergence and uniqueness but also experimentally
demonstrate that our method is sample efficient as compared to classical
policy gradient methods like REINFORCE. This approach looks promising, and
further studies of log density gradient will focus on scaling their
performance to complex tasks.

## References

  * Baxter & Bartlett (2001) Baxter, J. and Bartlett, P. L.  Infinite-horizon policy-gradient estimation.  _J. Artif. Int. Res._ , 2001.

  * Borkar & Meyn (2000) Borkar, V. S. and Meyn, S. P.  The o.d. e. method for convergence of stochastic approximation and reinforcement learning.  2000\.
  * Boyan (1999) Boyan, J. A.  Least-squares temporal difference learning.  In _ICML_ , pp. 49–56, 1999.
  * Bradtke & Barto (1996) Bradtke, S. J. and Barto, A. G.  Linear least-squares algorithms for temporal difference learning.  _Mach. Learn._ , 1996.
  * Gelada & Bellemare (2019) Gelada, C. and Bellemare, M. G.  Off-policy deep reinforcement learning by bootstrapping the covariate shift.  In _The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI_ , 2019.
  * (6) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018_.
  * Hallak & Mannor (2017) Hallak, A. and Mannor, S.  Consistent on-line off-policy evaluation.  In _Proceedings of the 34th International Conference on Machine Learning, ICML 2017_ , 2017.
  * Ilyas et al. (2020) Ilyas, A., Engstrom, L., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., and Madry, A.  A closer look at deep policy gradients.  In _8th International Conference on Learning Representations, ICLR 2020_ , 2020.
  * John Schulman et al. (2023) John Schulman, Barret Zoph, C. K. et al.  Chatgpt: Optimizing language models for dialogue, 2023.
  * Kakade (2001) Kakade, S. M.  A natural policy gradient.  In Dietterich, T. G., Becker, S., and Ghahramani, Z. (eds.), _Advances in Neural Information Processing Systems 14_ , 2001.
  * (11) Katdare, P., Liu, S., and Campbell, K. D.  Off environment evaluation using convex risk minimization.  In _2022 International Conference on Robotics and Automation, ICRA 2022_.
  * Lillicrap et al. (2016) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  In _4th International Conference on Learning Representations, ICLR_ , 2016.
  * (13) Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., and Petrik, M.  Finite-sample analysis of proximal gradient TD algorithms.  In Meila, M. and Heskes, T. (eds.), _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI 2015_.
  * Liu et al. (2018) Liu, Q., Li, L., Tang, Z., and Zhou, D.  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In _Advances in Neural Information Processing Systems 31_ , 2018.
  * Maei (2011) Maei, H. R.  Gradient temporal-difference learning algorithms.  In _Ph.D thesis_ , 2011.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T. P., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _Proceedings of the 33nd International Conference on Machine Learning, ICML_ , 2016.
  * Morimura et al. (2010) Morimura, T., Uchibe, E., Yoshimoto, J., Peters, J., and Doya, K.  Derivatives of logarithmic stationary distributions for policy gradient reinforcement learning.  _Neural Comput._ , 2010.
  * Nachum et al. (2019) Nachum, O., Chow, Y., Dai, B., and Li, L.  Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Nemirovski et al. (2009) Nemirovski, A., Juditsky, A. B., Lan, G., and Shapiro, A.  Robust stochastic approximation approach to stochastic programming.  _SIAM J. Optim._ , 2009.
  * Puterman (2014) Puterman, M. L.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley and Sons. 2014.
  * Robbins & Monro (1951) Robbins, H. and Monro, S.  A Stochastic Approximation Method.  _The Annals of Mathematical Statistics_ , 22(3):400 – 407, 1951.  doi: 10.1214/aoms/1177729586.  URL https://doi.org/10.1214/aoms/1177729586.
  * Rockafellar (2015) Rockafellar, R. T.  _Convex Analysis_.  Princeton University Press, 2015.
  * Schulman et al. (2015) Schulman, J., Levine, S., Moritz, P., Jordan, M. I., and Abbeel, P.  Trust region policy optimization.  _CoRR_ , abs/1502.05477, 2015.  URL http://arxiv.org/abs/1502.05477.
  * Schulman et al. (2016) Schulman, J., Moritz, P., Levine, S., Jordan, M. I., and Abbeel, P.  High-dimensional continuous control using generalized advantage estimation.  In _4th International Conference on Learning Representations, ICLR_ , 2016.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _CoRR_ , abs/1707.06347, 2017.  URL http://arxiv.org/abs/1707.06347.
  * Silver et al. (2014) Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. A.  Deterministic policy gradient algorithms.  In _Proceedings of the 31th International Conference on Machine Learning, ICML_ , 2014.
  * Silver et al. (2017) Silver, D., Schrittwieser, J., Simonyan, K., and thers.  Mastering the game of go without human knowledge.  _Nat._ , 2017.
  * Sutton (1988) Sutton, R. S.  Learning to predict by the methods of temporal differences.  _Mach. Learn._ , 1988.
  * Sutton et al. (1999) Sutton, R. S., McAllester, D. A., Singh, S., and Mansour, Y.  Policy gradient methods for reinforcement learning with function approximation.  In _Advances in Neural Information Processing Systems_ , 1999.
  * Tesauro (1992) Tesauro, G.  Practical issues in temporal difference learning.  _Mach. Learn._ , 1992.
  * Towers et al. (2023) Towers, M., Terry, J. K., Kwiatkowski, A., Balis, J. U., Cola, G. d., Deleu, T., Goulão, M., Kallinteris, A., KG, A., Krimmel, M., Perez-Vicente, R., Pierré, A., Schulhoff, S., Tai, J. J., Shen, A. T. J., and Younis, O. G.  Gymnasium, March 2023.  URL https://zenodo.org/record/8127025.
  * (32) Uehara, M., Huang, J., and Jiang, N.  Minimax weight and q-function learning for off-policy evaluation.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020_.
  * Voloshin et al. (2019) Voloshin, C., Le, H. M., Jiang, N., and Yue, Y.  Empirical study of off-policy policy evaluation for reinforcement learning.  2019\.
  * Williams (1992) Williams, R. J.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Mach. Learn._ , 1992.
  * Yuan et al. (2022) Yuan, R., Gower, R. M., and Lazaric, A.  A general sample complexity analysis of vanilla policy gradient.  In _International Conference on Artificial Intelligence and Statistics, AISTATS 2022_ , Proceedings of Machine Learning Research, 2022.
  * Zhang et al. (2020a) Zhang, R., Dai, B., Li, L., and Schuurmans, D.  Gendice: Generalized offline estimation of stationary values.  _CoRR_ , abs/2002.09072, 2020a.  URL https://arxiv.org/abs/2002.09072.
  * Zhang et al. (2020b) Zhang, S., Liu, B., and Whiteson, S.  Gradientdice: Rethinking generalized offline estimation of stationary values.  _CoRR_ , abs/2001.11113, 2020b.  URL https://arxiv.org/abs/2001.11113.

##  8 Appendix

###  8.1 Additional Literature Review - Temporal Difference Methods

Temporal difference (TD) learning involves improving predictions through
bootstrapping the current estimation. Early TD methods were mainly used to
estimate the value function $V^{\pi_{\theta}}$, which used a semi-gradient
update rule to improve value function prediction (Sutton, 1988). More advanced
TD methods incorporate prior traces (TD($\lambda$)) in a discounted manner
(Tesauro, 1992). Since many reinforcement learning methods are not tabular,
Linear TD methods were also proposed that uses this methodology to learn
parameters that approximate the value function (Bradtke & Barto, 1996; Boyan,
1999). Recently, TD methods have been effectively used to approximate
Advantage function (Mnih et al., 2016), density ratio function (Gelada &
Bellemare, 2019; Hallak & Mannor, 2017; Gelada & Bellemare, 2019) and off-
policy value estimation (Maei, 2011).In this work, we will observe that the
log density gradient has a recursive form that cannot be approximated using a
closed form solution. We will then propose a TD(0) methods to estimate the log
density gradient using on-policy samples.

###  8.2 Proof of Proposition 1

###### Proof.

We begin with policy gradient calculated using log density gradient, equation
6)

$\displaystyle\nabla_{\theta}J_{\gamma}(\pi_{\theta})=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a)r(s,a)]$

We recall from Bellman equation, 1b that
$r(s,a)=Q^{\pi_{\theta}}_{\gamma}-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[Q^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})]$,
hence

$\displaystyle\nabla_{\theta}J_{\gamma}(\pi_{\theta})=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a)(Q_{\gamma}^{\pi_{\theta}}(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})}[Q_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})])$

We recover the policy gradient theorem in equation 2 by first multiplying
equation 10 by $Q^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})$

$\displaystyle
d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})(\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})-\nabla_{\theta}\log\pi(a^{\prime}|s^{\prime}))Q^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})$
$\displaystyle=\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})Q^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})$

and then re-arranging terms with $\nabla_{\theta}\log d^{\pi}_{\gamma}$ on the
left hand side and the remaining terms on the right hand side. We can then sum
these terms to get equation 2

$\displaystyle\nabla_{\theta}J_{\gamma}(\pi_{\theta})$
$\displaystyle=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}(s,a)(Q_{\gamma}^{\pi_{\theta}}(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})}[Q_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})])$
$\displaystyle=\mathbb{E}_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[Q^{\pi_{\theta}}_{\gamma}(s,a)\nabla_{\theta}\log\pi(a|s)]$

This completes the proof. ∎

###  8.3 Proof of Lemma 1

###### Proof.

Recall the definition of $d_{\gamma}^{\pi_{\theta}}$ from equation 3

$\displaystyle
d_{\gamma}^{\pi_{\theta}}(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s|s_{0}\sim
d_{0},a_{t}\sim\pi_{\theta}(s_{t}),s_{t+1}\sim\mathcal{P}(s_{t},a_{t}))$

We see that for a given state $s^{\prime}\in{\mathcal{S}}$ the occupancy of an
agent at time $t$ and $t+1$ are related as follows,

$\displaystyle\mathbb{P}(s_{t+1}=s^{\prime})=\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}\mathbb{P}(s_{t}=s)\cdot\pi_{\theta}(a|s)\cdot\mathcal{P}(s^{\prime}|s,a)$

If we multiply both sides by $\gamma^{t+1}$ and sum them up from $t=0$ to
$\infty$. We get the following form,

$\displaystyle\sum_{t=0}^{\infty}\gamma^{t+1}\mathbb{P}(s_{t+1}=s^{\prime})$
$\displaystyle=\gamma\sum_{t=0}^{\infty}\gamma^{t}\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}\mathbb{P}(s_{t}=s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)$
$\displaystyle=\gamma\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)$
$\displaystyle=\frac{\gamma}{1-\gamma}\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}d_{\gamma}^{\pi_{\theta}}(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)$

We go from the first equation to the second by exchanging the summation signs
and from the second to the third by using the definition of
$\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s)=d_{\gamma}^{\pi_{\theta}}$.
We add $\mathbb{P}(s_{0}=s^{\prime})$ on both sides, which is nothing but the
set of initial states $d_{0}(s^{\prime})$, to get

$\displaystyle\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s^{\prime})=d_{0}(s^{\prime})+\frac{\gamma}{1-\gamma}\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}d_{\gamma}^{\pi_{\theta}}(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)$
$\displaystyle\implies\frac{1}{1-\gamma}d_{\gamma}^{\pi_{\theta}}(s^{\prime})=d_{0}(s^{\prime})+\frac{\gamma}{1-\gamma}\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}d_{\gamma}^{\pi_{\theta}}(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)$
$\displaystyle\implies
d_{\gamma}^{\pi_{\theta}}(s^{\prime})=(1-\gamma)d_{0}(s^{\prime})+\gamma\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}d_{\gamma}^{\pi_{\theta}}(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)$

where we used

$\displaystyle\sum_{t=0}^{\infty}\gamma^{t+1}\mathbb{P}(s_{t+1}=s^{\prime})+d_{0}(s^{\prime})=\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s^{\prime})=\frac{1}{1-\gamma}d_{\gamma}^{\pi_{\theta}}(s^{\prime}).$

This completes the proof. ∎

###  8.4 Proof of Lemma 2

###### Proof.

Recall the optimization 8

$\displaystyle\operatorname*{arg\,min}_{w:{\mathcal{S}}\rightarrow\mathbb{R}}\sum_{s^{\prime}}\Large(w(s^{\prime})-(1-\gamma)d_{0}(s^{\prime})+\gamma\sum_{s,a}w(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)\Large)^{2}+\frac{\lambda}{2}(\sum_{s}w(s)-1)^{2}$

It is worth noting that the optimization has two quadratic terms. Thus, the
lowest value that they can take is only when
$w(s^{\prime})-(1-\gamma)d_{0}(s^{\prime})+\gamma\sum_{s,a}w(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)=0$
and $\sum_{s}w(s)=1$. For the next part of the proof, we will handle them
case-by-case.

Case 1. $\gamma<1$

Recall that the first term of the optimization equation 8 goes to zero only
when equation 7 (reproduced below) is satisfied

$\displaystyle
w(s^{\prime})=(1-\gamma)d_{0}(s^{\prime})+\gamma\sum_{s\in{\mathcal{S}},a\in\mathcal{A}}w(s)\pi_{\theta}(a|s)\mathcal{P}(s^{\prime}|s,a)\quad\text{
for all }s^{\prime}\in{\mathcal{S}}.$

Now all that remains to be proven is the uniqueness aspect of this form. To
that end, we first write the above set of equations in a matrix form

$\displaystyle W=(1-\gamma)D_{0}+\gamma\mathcal{P}_{\pi_{\theta}}^{T}W,$ (18)

where
$W=(w(s_{1}),w(s_{2}),.....,w({s_{|{\mathcal{S}}|}}))\in\mathbb{R}^{|{\mathcal{S}}|}$,
$\mathcal{P}_{\pi_{\theta}},{D_{\pi_{\theta}}}\in\mathbb{R}^{|{\mathcal{S}}|\times|{\mathcal{S}}|}$
where
$(\mathcal{P}_{\pi_{\theta}})_{(s,s^{\prime})}=\mathbb{P}^{\pi_{\theta}}(s^{\prime}|s)$
and ${D_{\pi_{\theta}}}$ is a diagonal matrix whose every element correspond
to $d_{0}$. It is easy to see from this form here that the row sum of this
matrix is 1. We can simply re-write the above equation as follows,

$\displaystyle(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}}^{T})W=(1-\gamma)D_{0}$

$I_{|{\mathcal{S}}|}$ is the identity matrix of size $|{\mathcal{S}}|$. It now
remains to prove that
$(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}}^{T})$ is invertible. We
propose the following Lemma which proves the same result.

######  Lemma 5.

For $\gamma<1$, The matrix
$(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}}^{T})$ is invertible.

###### Proof.

It is generally easier to prove that the transpose of this matrix is
invertible. Consider $x\in\mathbb{R}^{|{\mathcal{S}}|}$ is a non-zero vector.
We will now prove that
$(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}})x$ is non-zero. To see
that observe the infinty norm as follows,

$\displaystyle\|(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}})x\|_{\infty}$
$\displaystyle\geq\|x\|_{\infty}-\gamma\|\mathcal{P}^{\pi_{\theta}}x\|_{\infty}$
$\displaystyle\geq(1-\gamma)\|x\|_{\infty}>0$

We get the first equation from the triangular inequality. We get the second
equation from the fact that the row sum of the matrix
$\mathcal{P}_{\pi_{\theta}}$ is 1. Thus, $\|\mathcal{P}_{\pi_{\theta}}\cdot
x\|_{\infty}\leq\|x\|_{\infty}$. This implies that
$(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}}^{T})$ is invertible.
This completes the proof. ∎

Since the matrix $(I_{|{\mathcal{S}}|}-\gamma\mathcal{P}_{\pi_{\theta}}^{T})$
is invertible the solution is equal to $d^{\pi_{\theta}}_{\gamma}$. The
solution also satisfies the constraint
$\sum_{s}w(s)=\sum_{s}d^{\pi_{\theta}}(s)=1$. This completes the proof for the
first case.

Case 2. $\gamma=1$
For $\gamma=1$ we need to solve

$\displaystyle(I-\mathcal{P}_{\pi_{\theta}}^{T})W=0$

The proof now follows from (Zhang et al., 2020b, Theorem 1). Here we invoke
Perron-Frobenius theorem which says the dimension of the left eigenspace
of$\mathcal{P}_{\pi_{\theta}}$ corresponding to eigevalue 1 is one-
dimensional. Since $d^{\pi_{\theta}}_{1}$ belongs in that set,the solution of
these set of equations as $W=\alpha d^{\pi_{\theta}}_{1}$. It is worth noting
that only $\alpha=1$ satisfies the second constraint which is
$\sum_{s}w(s)=1$. This completes the proof. ∎

###  8.5 Proof of Lemma 3

This proof is very similar to proof of Lemma 2.

###### Proof.

Let us restate the optimization problem in Lemma 3 (equation 11):

$\displaystyle\min_{w:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{n}}\bigg{\\{}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d_{\gamma}^{\pi_{\theta}}}\|\nu(s^{\prime},a^{\prime})\|^{2}+\frac{\lambda}{2}\Big{\|}E_{(s,a)\sim
d^{\pi_{\theta}}_{\gamma}}[w(s^{\prime},a^{\prime})]\Big{\|}^{2}\bigg{\\}}$
$\displaystyle\nu(s^{\prime},a^{\prime}):=d_{\gamma}^{\pi_{\theta}}(s^{\prime},a^{\prime})(w(s^{\prime},a^{\prime})-\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime}))-\gamma\sum_{s,a}d_{\gamma}^{\pi_{\theta}}(s,a)\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})w(s,a)$

We note that it has two quadratic terms. As in Lemma 2, this loss function can
only go to zero if and only if both the quadratic terms turn out to be zero.
This implies that

$\displaystyle\nu(s^{\prime},a^{\prime})=0\,\text{ for all
}(s^{\prime},a^{\prime})\in{\mathcal{S}}\times\mathcal{A}\quad\text{ and
}\quad\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi_{\theta}}_{\gamma}}[w(s^{\prime},a^{\prime})]=0.$

We take two cases.

Case 1. $\gamma<1$

Similar to Lemma 2, for a finite state-action space we can re-write equation
11 in a linear form

$\displaystyle(I_{|{\mathcal{S}}|\times|\mathcal{A}|}-\gamma\mathcal{P}_{\pi_{\theta}}^{T})\,D_{\pi_{\theta}}\,W=D_{\pi_{\theta}}\,G$
(19)

where, $W\in\mathbb{R}^{|{\mathcal{S}}|\cdot|\mathcal{A}|\times n}$ is the
matrix with every row corresponding to $w(s,a)$ for each state-action pair
$(s,a)$. Similarly, $G\in\mathbb{R}^{|{\mathcal{S}}|\cdot|\mathcal{A}|\times
n}$ has its rows as $\nabla_{\theta}\log\pi_{\theta}$ for each state-action
pair. Let
$\mathcal{P}_{\pi_{\theta}},{D_{\pi_{\theta}}}\in\mathbb{R}^{|{\mathcal{S}}|\cdot|\mathcal{A}|\times|{\mathcal{S}}|\cdot|\mathcal{A}|}$
where
$(\mathcal{P}_{\pi_{\theta}})_{((s,a),(s^{\prime},a^{\prime}))}=\mathbb{P}^{\pi_{\theta}}(s^{\prime},a^{\prime}|s,a)$
and ${D_{\pi_{\theta}}}$ is a diagonal matrix whose every element correspond
to $d_{\gamma}^{\pi_{\theta}}$ for each state-action pair. The ergodicity
assumption implies that $D_{\pi_{\theta}}$ is invertible. Additionally, we
also proved in Lemma 5 in Section 8.4 that
$(I-\gamma\mathcal{P}_{\pi_{\theta}}^{T})$ is invertible. This ensures that
the solution of equation 19 is unique and equal to the log density gradient.
Since, log density gradient always satisfies the constraint
$\mathbb{E}_{(s,a)\sim d^{\pi_{\theta}}_{\gamma}}[\nabla_{\theta}\log
d^{\pi_{\theta}}(s,a)]=0$, the second constraint becomes redundant. This
completes the proof.

Case 2. $\gamma=1$

For $\gamma=1$ we have the following set of equations

$\displaystyle(I_{|{\mathcal{S}}|\times|\mathcal{A}|}-\mathcal{P}_{\pi_{\theta}}^{T})\,D_{\pi_{\theta}}\,W=D_{\pi_{\theta}}\,G\quad\text{
and }\quad e^{T}D_{\pi_{\theta}}W=0.$

Let us look at the equations column by column. The matrix
$(I_{|{\mathcal{S}}|\times|\mathcal{A}|}-\mathcal{P}_{\pi_{\theta}}^{T})$ is
not invertible since the vector $d_{1}^{\pi_{\theta}}$ is in its nullspace.
Since $\nabla_{\theta}\log d^{\pi_{\theta}}_{1}$ satisfies the first equation,
every column can be written as $\nabla_{\theta}\log
d^{\pi_{\theta}}_{\gamma}+v$ where $v$ is any vector in the span of
$\\{d_{1}^{\pi_{\theta}}\\}$. This implies that
$D_{\pi_{\theta}}v=\mathcal{P}_{\pi_{\theta}}^{T}D_{\pi_{\theta}}v$. invoking
Perron-Frobenius theorem as in Lemma 8.4, we see that $v$ lies in the span of
$\\{d_{1}^{\pi_{\theta}}\\}$. We complete the proof by trying to satisfy the
second constraint $e^{T}D_{\pi_{\theta}}v=0$ which gives us $v=0$. This
completes the proof. ∎

###  8.6 Proof of Lemma 4

###### Proof.

We will prove contraction first for $\gamma\in[0,1)$.

Proof of Contraction: To prove contraction, we will show that given any
arbitrary functions
$U,V:{\mathcal{S}}\times\mathcal{A}\rightarrow\mathbb{R}^{n}$, their
difference under the L1 norm of the distribution $d^{\pi_{\theta}}_{\gamma}$
is a contraction.

$\displaystyle\sum_{s^{\prime},a^{\prime}}d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})|Y_{\gamma}\cdot
U(s^{\prime},a^{\prime})-Y_{\gamma}\cdot V(s^{\prime},a^{\prime})|$
$\displaystyle=\sum_{s^{\prime},a^{\prime}}d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})|\gamma\sum_{s,a}d^{\pi_{\theta}}_{\gamma}(s,a)(U(s,a)-V(s,a))\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})|$
$\displaystyle\leq\gamma\sum_{s^{\prime},a^{\prime}}d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})\sum_{s,a}d^{\pi_{\theta}}_{\gamma}(s,a)|U(s,a)-V(s,a)|\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})$
$\displaystyle\leq\gamma\sum_{s,a}d^{\pi_{\theta}}_{\gamma}(s,a)\sum_{s^{\prime},a^{\prime}}d^{\pi_{\theta}}_{\gamma}(s^{\prime},a^{\prime})\
|U(s,a)-V(s,a)|\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})$
$\displaystyle\leq\gamma\sum_{s,a}d^{\pi_{\theta}}_{\gamma}(s,a)\sum_{s^{\prime},a^{\prime}}\
|U(s,a)-V(s,a)|\mathcal{P}(s^{\prime}|s,a)\pi_{\theta}(a^{\prime}|s^{\prime})$
$\displaystyle\leq\gamma\sum_{s,a}d^{\pi_{\theta}}_{\gamma}(s,a)|U(s,a)-V(s,a)|=\gamma\|U-V\|_{1}^{d^{\pi_{\theta}}_{\gamma}}.$

This completes the proof. The contraction property is useful in proving
uniqueness and convergence which we prove next.

Case 1. $\gamma<1$

Let $Y_{\gamma}^{k}$ denote that $Y_{\gamma}$ has been composed with itself
$k$ times. We are interested in what happens when
$\lim_{k\rightarrow\infty}Y_{\gamma}^{k}$.

$\displaystyle
Y_{\gamma}^{k}C_{0}=\gamma^{k}D_{\pi_{\theta}}^{-1}(\mathcal{P}_{\pi_{\theta}}^{T})^{k}D_{\pi_{\theta}}C_{0}+\sum_{t=0}^{k-1}\gamma^{t}D_{\pi_{\theta}}^{-1}(\mathcal{P}_{\pi_{\theta}}^{T})^{t}D_{\pi_{\theta}}G$

Noting that $\mathcal{P}_{\pi_{\theta}}$ is a transition probability matrix so
every element is bounded above by 1, and since $\gamma<1$, we get that
$\lim_{k\rightarrow\infty}\gamma^{k}D_{\pi_{\theta}}(\mathcal{P}_{\pi_{\theta}}^{T})^{k}D_{\pi_{\theta}}C_{0}=0$.
Focusing on the other terms as $k\rightarrow\infty$ we get the following,

$\displaystyle\lim_{k\rightarrow\infty}$
$\displaystyle\sum_{t=0}^{k-1}\gamma^{t}D_{\pi_{\theta}}^{-1}(\mathcal{P}_{\pi_{\theta}}^{T})^{t}D_{\pi_{\theta}}G=D_{\pi_{\theta}}^{-1}(I-\gamma\mathcal{P}_{\pi_{\theta}}^{T})^{-1}D_{\pi_{\theta}}G$

From equation 19 we see that
$\lim_{k\to\infty}Y_{\gamma}^{k}C_{0}=\nabla_{\theta}\log
d_{\gamma}^{\pi_{\theta}}$ which completes the proof. ∎

###  8.7 Additional Details Linear-TD

inline]how do you know the limit exists? it follows from Lemma above right?
inline]combine lemma 4 and 5 For large problem spaces, it is difficult to
learn $w(s^{\prime},a^{\prime})$ for all the state-action spaces. In that
case, we use linear function approximation, see for example, Gelada &
Bellemare (2019); Hallak & Mannor (2017). We choose a feature map
$\Phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d}$ and
$\zeta\in\mathbb{R}^{d\times n}$ are the linear parameters that we wish to
learn. We want to approximate $w(s,a)$ as $\zeta^{T}\Phi(s,a)$ for each state
action pair $(s,a)$. inline]where is $\Psi$? The TD(0) algorithm with linear
function approximation has the following update

$\displaystyle\zeta_{k+1}^{T}\leftarrow\zeta_{k}^{T}+\alpha_{k}(\gamma\zeta_{k}^{T}\Phi(s_{k},a_{k})+g(s_{k}^{\prime},a_{k}^{\prime})-\zeta_{k}^{T}\Phi(s_{k}^{\prime},a_{k}^{\prime}))\Phi(s_{k}^{\prime},a_{k}^{\prime})^{T},$
(20)

where $(s_{k},a_{k})\sim
d_{\gamma}^{\pi_{\theta}},s_{k}^{\prime}\sim\mathcal{P}(\cdot|s_{k},a_{k}),a_{k}^{\prime}\sim\pi_{\theta}(\cdot|s_{k}^{\prime})$
and $\alpha_{k}$ is the learning rate. To prove convergence, re-write equation
20 in the following linear form,

$\displaystyle\zeta_{k+1}=\zeta_{k}+\alpha_{k}(A_{k+1}\zeta_{k}+g_{k+1})$

where,
$A_{k}:=\gamma\Phi(s_{k}^{\prime},a_{k}^{\prime})(\Phi(s_{k},a_{k})^{T}-\Phi(s_{k}^{\prime},a_{k}^{\prime})^{T}),g_{k}:=\Phi(s_{k}^{\prime},a_{k}^{\prime})(\nabla_{\theta}\log\pi_{\theta}(a_{k}^{\prime}|s_{k}^{\prime}))^{T}$.
inline]new variable for $g$, and write the grad log pi term as g to avoid
confusion We further define,

$\displaystyle A$
$\displaystyle:=\gamma\mathbb{E}[\Phi(s^{\prime},a^{\prime})(\Phi(s,a)^{T}-\Phi(s^{\prime},a^{\prime})^{T})\,|\,(s,a)\sim
d_{\gamma}^{\pi_{\theta}},s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})],$
$\displaystyle g$
$\displaystyle:=\mathbb{E}[\Phi(s^{\prime},a^{\prime})(\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime}))^{T}\,|\,(s,a)\sim
d_{\gamma}^{\pi_{\theta}},s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})]$

To prove the convergence of this linear TD update rule, we make a few standard
assumptions.

######  Assumption 2.

  1. 1.

The matrix $\Psi$ has linearly independent rows.

  2. 2.

The matrix $A$ is non-singular.

  3. 3.

The feature matrix $\Phi$ has uniformly bounded second moments.

######  Theorem 3.

Under Assumption 2 and the fact that the learning rate satisfies the Robbins
Monroe condition Robbins & Monro (1951) then the TD update equation 20
converges in probability to the solution

$\displaystyle\lim_{k\rightarrow\infty}\zeta_{k}=-A^{-1}b$

inline]1. "the fact that learning rate…"? has it been assumed before? maybe we
could add it as another assumption after the three previous ones. 2. what is
$b$
Answer Makes sense.. Can do this

###### Proof.

The proof follows similar to (Zhang et al., 2020b, Theorem 2) which invokes
(Borkar & Meyn, 2000, Theorem 2.2). We first re-write the updated equation in
the following form

$\displaystyle\zeta_{k+1}=\zeta_{k}+\alpha_{k}(A\zeta_{k}+g+(A_{k+1}-A)\zeta_{k}+(g_{k+1}-g)).$

The proof follows almost equivalently from (Zhang et al., 2020b, Theorem 2)
since the assumptions are the same. The above equation has separated the
update into the deterministic part, $h(\zeta_{k}):=A\zeta_{k}+g$ and the
Martingale part, $M_{k+1}:=(A_{k}-A)\zeta_{k}+(g_{k}-g)$. To apply this
theorem, we now need to show that the function $h(\zeta)$ is asymptomatically
stable. For stability, we will now show that the matrix $A$ has all negative
Eigenvalues. Consider any unit eigenvector $x$. We will now try to evaluate
$x^{T}Ax$.

$\displaystyle x^{T}Ax$ $\displaystyle=x^{T}\,\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[-\Phi(s,a)\Phi(s,a)^{T}+\gamma\Phi(s,a)\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[\Phi(s^{\prime},a^{\prime})]]\,x$
$\displaystyle=-\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[x^{T}\Phi(s,a)\Phi(s,a)^{T}x]+\gamma[x^{T}\Phi(s,a)\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[\Phi(s^{\prime},a^{\prime})]]$

Using Cauchy-Shwartz inequality on the second term. We now get the following,

$\displaystyle x^{T}Ax\leq-(1-\gamma)\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[x^{T}\Phi(s,a)\Phi(s,a)^{T}x]\leq 0$

Since $A$ is non-singular (Assumption 2), the eigenvalues cannot be zero.
Thus, the eigenvalues for this problem are strictly negative. This guarantees
asymptotic stability of $h(\zeta)$ and completes the proof. ∎

###  8.8 Proof of Theorem 1

###### Proof.

The proof follows similar to to (Zhang et al., 2020b, Theorem 2) which invokes
(Borkar & Meyn, 2000, Theorem 2.2). We first re-write the updates in equation
17 in matrix form as $d_{t+1}=d_{t}+\varepsilon_{t}(G_{t+1}d_{t}+h_{t+1})$
with $d_{t}:=[\alpha_{t},\beta_{t},\tau_{t}^{T}]$ and $G_{t+1},h_{t+1}$ are as
follows,

$\displaystyle G_{t+1}$
$\displaystyle=\begin{bmatrix}0&-A_{t}&-\lambda\Phi_{t}\\\ A_{t}&-C_{t}&0\\\
\lambda\Phi_{t}^{T}&0&-\lambda\end{bmatrix},\quad h_{t+1}=\begin{bmatrix}0\\\
-B_{t}\\\ 0\end{bmatrix}$

where,
$A_{t}=(\Phi_{t}\Phi_{t}^{T}-\gamma\Phi_{t}(\Phi_{t}^{\prime})^{T}),B_{t}=\Phi
g_{t}^{T},C_{t}=\Phi_{t}\Phi_{t}^{T}$. We can calculate the expectation for
each of these matrices as follows (the expectation is taken over all possible
values of $(s,a)$ distributed as $d_{\gamma}^{\pi_{\theta}}$),

$\displaystyle
G=\mathbb{E}_{p}[G_{t+1}]=\begin{bmatrix}0&-A&-\lambda{D_{\pi_{\theta}}}^{T}\Phi\\\
A&C&0\\\ \lambda\Phi^{T}{D_{\pi_{\theta}}}&0&-\lambda\end{bmatrix},\quad
h=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}}}[h_{t+1}]=\begin{bmatrix}0\\\ -B\\\ 0\end{bmatrix}$

Where,

$\displaystyle A:=\Psi(I-\gamma
P_{\pi_{\theta}}){D_{\pi_{\theta}}}\Psi^{T},\quad
B:=\Psi{D_{\pi_{\theta}}}G^{T},\quad C:=\Psi{D_{\pi_{\theta}}}\Psi,$
$\displaystyle E_{p}[\cdot]:=\mathbb{E}_{(s,a)\sim
d_{\gamma}^{\pi_{\theta}},s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim\pi_{\theta}(\cdot|s^{\prime})}[\cdot]$

where ${D_{\pi_{\theta}}}$ is a diagonal matrix with the diagonal being
$d_{\gamma}^{\pi_{\theta}}$. We will now prove the convergence of the linear
function approximation case. We first separate the deterministic term
$h(d_{t})$ and the stochastic term $M_{t+1}$

$\displaystyle
d_{t+1}=d_{t}+\varepsilon_{t}(\underbrace{Gd_{t}+g}_{h(d_{t})}+\underbrace{(G_{t+1}-G)d_{t}+(g_{t+1}-g))}_{M_{t+1}}$

From here, the proof follows equivalently to (Zhang et al., 2020b, Theorem 2),
with exactly same assumptions. The remaining part of the proof requires us to
show that the function $h(d)$ is symptomatically stable. We show that by
demonstrating that the eigenvalues of the matrix $G$ are strictly negative.
Let $v$ be an arbitrary eigenvector of $G$ corresponding to an arbitrary
eigenvalue $\nu$, then

$\displaystyle\mu$ $\displaystyle=v^{T}Gv$
$\displaystyle=v_{2}^{T}Av_{1}+\lambda
v_{3}^{T}\Phi^{T}{D_{\pi_{\theta}}}v_{1}-v_{1}^{T}Av_{2}-\lambda
v_{1}^{T}\Phi^{T}{D_{\pi_{\theta}}}v_{3}-v_{2}^{T}Cv_{2}-\lambda
v_{3}^{T}v_{3}$ $\displaystyle=-\lambda v_{3}^{T}v_{3}-v_{2}^{T}Cv_{2}\leq 0$

Now, we just need to show that the eigenvalue is not zero. We will prove that
using contradiction. Assume that there exists a $v$ such that $Gv=0$ and
$v\neq 0$. This implies that,

$\displaystyle-Av_{2}-\lambda\Phi^{T}{D_{\pi_{\theta}}}v_{3}=0$ $\displaystyle
Av_{1}=0$ $\displaystyle\lambda{D_{\pi_{\theta}}}^{T}\Phi v_{1}-\lambda
v_{3}=0$

Since $A$ is a non-singular matrix (Assumption 1) we have $v_{1}=0$ which
implies that $v_{3}=0$ from the third equation. This leaves us with $Av_{2}=0$
which leaves us with $v_{2}=0$, which is a contradiction. This finishes the
proof. It now is proven that the eigenvalue is strictly negative. This
completes the proof. ∎

###  8.9 Proof of Theorem 2

###### Proof.

The proof of this Theorem is almost similar to the proof of Zhang et al.
(2020b) except the need to bound different terms. To simplify the proof, we
first lump the maximization and minimization variables together and update
these parameters in matrix form. We call the grouped maximization variables
$y=(\beta,\tau)$ and minimization variable $\alpha$. We re-write Algorithm 1
in matrix form as follows (in Algorithm 2),

Algorithm 2 Projected Log Density Gradient

1: for $i=1,2,...,n$ do:

2: $\alpha_{t+1}=\Pi_{X}(\alpha_{t}-\varepsilon_{t}(G_{1,t}y_{t}))$

3:
$y_{t+1}=\Pi_{Y,Z}(y_{t+1}+\varepsilon_{t}(G_{2,t}\alpha_{t}+G_{3.t}y_{t}+G_{4,t})$

4: Return $\bar{\alpha},\bar{y}$Where,
$\bar{\alpha}=\frac{\sum_{i=1}^{n}\varepsilon_{i}\alpha_{i}}{\sum_{{i=1}}^{n}\varepsilon_{i}}$
,
$\bar{y}=\frac{\sum_{i=1}^{n}\varepsilon_{i}y_{i}}{\sum_{i=1}^{n}\varepsilon_{i}}$

where,

$\displaystyle
G_{1,t}:=\begin{bmatrix}-(\Phi_{t}\Phi_{t}^{T}-\gamma\Phi_{t}\Phi_{t}^{\prime
T})&-\lambda\Phi_{t}\\\ \end{bmatrix}$ $\displaystyle
G_{2,t}:=\begin{bmatrix}\Phi_{t}\Phi_{t}^{T}-\gamma\Phi_{t}\Phi_{t}^{{}^{\prime}T}\\\
\lambda\Phi_{t}^{T}\end{bmatrix},G_{3,t}:=\begin{bmatrix}-\Phi_{t}\Phi_{t}^{T}&0\\\
0&-\lambda\end{bmatrix}$ $\displaystyle
G_{4,t}:=\begin{bmatrix}-\Phi_{t}g_{t}^{T}\\\ 0\end{bmatrix}.$

We also project our variables $\alpha_{t},y_{t}$ on the closed and convex sets
$X\subset\mathbb{R}^{d\times n},Y\subset\mathbb{R}^{d\times
n}\times\mathbb{R}^{1\times n}$. We output the weighted average $\bar{\alpha}$
and $\bar{y}$. Before, proposing a sample complexity bound, we first define
the optimization gap $\epsilon_{g}(\alpha,y)$ as follows,

$\displaystyle\epsilon_{g}(\alpha,y):=\max_{y^{\prime}\in{Y}}L(\alpha,y^{\prime})-\min_{\alpha^{\prime}\in
X}L(\alpha^{\prime},y)$

Note that $\epsilon_{g}(\alpha_{*},y_{*})=0$, where $\alpha_{*},y_{*}$ are the
solutions to the min-max problem. From here, on the proof follow almost
similarly to Zhang et al. (2020b). The proof follows from (Liu et al., ,
Proposition 3) and (Zhang et al., 2020b, Proposition 2), both of which rely on
(Nemirovski et al., 2009, Proposition 3.2) to state the
$O\left(\sqrt{\frac{1}{n}}\right)$ bound. Proposition 3.2 in Nemirovski et al.
(2009) says that set $X,Y,Z$ should be closed, convex and bounded sets, which
is part of our assumption. Our min-max loss function is Lipschitz continuous
and the minimization problem is convex and the maximization problem is
concave. It can also be seen that both the primal and dual form of the
optimization has equal optimal values $\alpha_{*},y_{*}$. We now proceed to
apply the bound proposed by Nemirovski et al. (2009). To that end, we first
need to bound certain terms. We define $D_{\alpha}$ and $D_{Y}$ as follows,

$\displaystyle D_{\alpha}=\max_{x\in X}\|x\|^{2}-\min_{x\in X}\|x\|^{2}$
$\displaystyle D_{Y}=\max_{y\in Y}\|y\|^{2}-\min_{y\in Y}\|Y\|^{2}$

From Assumption 1 which says the second moment of all the features is bounded
we can similarly write the following bound

$\displaystyle\mathbb{E}[\|G_{i,t}-G_{i}\|^{2}]\leq\sigma_{i}^{2}\quad\forall
i\in\\{1,2,3,4\\}.$

Therefore, we obtain bounds for the stochastic sub-gradient
$G_{\alpha}(\alpha,y),G_{Y}(\alpha,y)$ as follows,

$\displaystyle G_{\alpha}(\alpha,y)=G_{1,t}y_{t}$ $\displaystyle
G_{Y}(\alpha,y)=(G_{2.t}\alpha_{t}+G_{3,t}y_{t}+G_{4,t})$

and for their second moment as follows,

$\displaystyle\mathbb{E}[\|G_{\alpha}(\alpha,y)\|^{2}]$
$\displaystyle=\sigma_{1}^{2}D_{Y}^{2}+\sigma_{1}^{2}\|\bar{G}_{1,t}\|^{2}\leq
C_{\alpha}$ $\displaystyle\mathbb{E}[\|G_{Y}(\alpha,y)\|^{2}]$
$\displaystyle=\sigma_{2}^{2}D_{Y}^{2}+\sigma_{2}^{2}\|\bar{G}_{2,t}\|^{2}+\sigma_{3}^{2}D_{Y}^{2}+\sigma_{3}^{2}\|\bar{G}_{3,t}\|^{2}+\sigma_{4}^{2}\|\bar{G}_{4,t}\|^{2}\leq
C_{Y},$

where we used the fact that
$\mathbb{E}[\|x\|^{2}]\leq\mathbb{E}[\|x-\mathbb{E}[x]\|^{2}]+\|\mathbb{E}[x]\|^{2}$.
If we now follow the procedure as proposed by Nemirovski et al. (2009) we can
define $M_{*}$ as follows,

$\displaystyle M_{*}^{2}=2C_{\alpha}^{2}D_{\alpha^{2}}+2C_{Y}^{2}D_{Y}^{2}$

If we fix the learning rate as $\varepsilon_{t}=\frac{c}{M_{*}\sqrt{t}}$ for
any positive constant $c$. We can now bound the optimality gap with
probability at least $1-\delta$ using (Nemirovski et al., 2009, Proposition
3.2)

$\displaystyle\epsilon(\bar{\alpha},\bar{y})\leq\frac{5}{n}(8+2\log\frac{2}{\delta})M_{*}\max\\{c,\frac{1}{c}\\}$

This completes the proof. ∎