Towards Provable Log Density Policy Gradient
Authors: Pulkit Katdare
Anant A Joshi
Katherine Rose Driggs-Campbell
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (10/2024)
Towards Provable Log Density Policy Gradient
Pulkit Katdare
University of Illinois at Sebana-Champaigg
Anant A. Joshi University of Illinois at Urbana-Champaige
Katherine Driggs Campbel
University of Illinois at Jrbana-Champaln
Reviewed OpenReview: http:s//ppparere....ee///d//dddp
Abstract
Policy gradient methods are a vital ingredient behind the success of modern reinforcement learning. Modern policy gradient methods, although successful, introduce residual error in gradient estimation. In this work, we argue that this residual term is significant and correcting for it could potentially improve sample-complextty of reinforcement learning methods. To that end, 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 stale-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 Markov chain is highly restrictive also propose min-max optimization that can approximate log density gradient using just on on-policy samples. We also prove uniqueness, and convergence under lincar 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 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 able to improve upon the classical policy gradient method by 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. Classically in reinforcement learning, two types of problems are well known and well studied: discounted reward and average reward, see for example Sution & Barto (2018). It is well known that for the discounted reward scenario, the Bellman operator is a contraction, and solving the Bellman straightforward numerical procodure. However, the same contraction property fails hold for the average reward scenario. Therefore, classical policy gradient methods typically approximate gradient of the policy using Q-function estimated with discount factor strictly less than 1, which leads to
equation iteratively

---

Published in Transactions on Machine Learning Research (10/2024)
-500
Average Rewards
-1500
-2000
Classical Policy Gradient (10x
Log Density Gradient (10 10)
Classical Policy Gradient
Log Density Gradient x35
125
150
175
Episodes
Figure 1: For the average reward scenario, performance of classical policy gradient (blue) algorithm compared to log density gradient (green) algorithm over a x n gridworld environment, for = 5, 10. We observe that log density gradient algorithm consistently converges to better policy performance. Theoretical calculated solutions are used for implementation.
error in gradient ostimation (Morimura et al., 2010). In this paper, we empirically demonstrate that this error in indeed significant, see for instance, Figure 1. We further propose a novel algorithm to estimate policy gradient that corrects for this residual error, which could potentially lead sample efficient reinforcement learning, thus enabling their deployment over wide variety of complex scenarios. We call our method, log density gradient. We show that log density gradient method can be used to estimate the policy gradient for all values of discounting factor including the average reward scenario. Log density gradient method 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 gradient of log density and the reward function (Nachum et al., 2019; Uehara et al.). This separation results an improved correlation with the true policy gradient and requires fewer hyperparameters. We show that method is consistent with the classical policy gradient thcorem (Sutton, 1988) and also prove convergence propertics and sample complexity.
Our main contributions are follows. 1. A novel method to provebly calculate policy gradient by using the average state-action discounted formulation for all values of the discounting factor. We will show that policy gradient estimated in this manner for average reward scenario will correct for the residual error in policy gradient estimation, which is widely ignored in empirical implereenaations of policy gradients (as shown Figure 1). 2. A model-free Temporal Difference (TD) method for approximating policy gradient. We provide proof of contraction well convergence. However, there is 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 for all values of the discounting factor including the average reward scenario and model free TD method to implement it, with proof of convergence, We also show that this min-max optimization has closed form solution under linear function class assumptions, thus enabling their practical use with linear MDP problems (Zhang al., 2022). We additionally show sample complexity of the order 0mm-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, discusscs prior work in policy gradient methods, temporal difference methods, and min-max problems in off-policy evaluation and compares our work with existing works to situate our paper in the literature. Our main contributions are discussed in detail starting from Scction which starts with rigorously defining log density gradient. Additionally we also propose TD approach to estimate log density gradient under strict reversibility assumptions, and describe the issue caused by this assumption. In section 6, to overcome this issue to
2

---

Published in Transactions on Machine Learning Research (10/2024)
propose min-max variant that allows us to estimate log density gradient algorithm using empirical samples. We finally demonstrate proof-of-concept of our algorithm in Section 7 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 (.) 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 6-tuple of (8, P,r, do). Here, S finite state space of the MDP, A is finite action space, P the transition probability matrix, is the reward function and da is the initial distribution. The reinforcement learning problems is optimise for a policy : S - A(A) that maximizes (T),, defined as
(x( = (1
y (r(s) ~ do, ~ (441 ~ P(yss,, a:). for y E (0.
t=
Ji(
lim E T
Σ r'r(st, 00), 80 do, a x(-15)); 8141 8141
P(-1s,,a))) for y 1,
where y |0, 1] is the discounting factor which accounts for the impact of future rewards present decision making. When y = 1, (TT the scenario is called the average reward formulation. Most practical problems in reinforcement lcarning typically aim to solve for an optimal policy x¹ arg max, J1 (S) Figure Haarnoja el al.). Modern reinforcement learning methods aim to parameterise policy with set of parameters 0 e R", where is the dimensions of the parameter space, We refer to such paremterisation as Ta. This kind of paramoterisation enables us search for optimal set of parameters 8" instead of a search over S x which in practice could be very large. We define
8" : arg max J1 (TO).
BER"
The Q-function Q is commonly used function used to describe the performance of an RL agent. Q-function calculates the long term (discounted) rewards accumulated by agent following fixed policy while starting from a state s E S and taking an action a E A
(5, = E
rr a:)) = 3,00 = a. ~ Te(- 81+1 ~ P(. ac)
(Ia)
1=
= = a) +
(s','')
(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 < for stable estimation of the Q-function. We also similarly define value function (i*((s) = Ba (-1>) 1077 (s,
Modern RL algorithus generally solve for 0 by estimating the gradient of policy performance (mg)) with respect policy parameters This also commonly referred as the policy gradient thcorem VoJi(m)) (Sutton al., 1999) which says
(a))(TT)) = (a.a)=a7 1Q,0 (s, a) V log (a(ss)) 7 E [0,
(2)
Here, d is the average state-action discounted stationary distribution, which is defined the cumulative sum of discounted state-action occupancy across the time horizon.
(s, == (1 (1-2)
PP =, also ~ do. ~ To(st). s211 ~ ((-)s,,0)),7
(3a)
t=0
T
(s, = lim
((s 0, = also do ar To(s)). 8111 P(-Ise, at), = 1).
(3b)
T-
1=
3

---

Published in Transactions on Machine Learning Research (10/2024)
In this paper make a standard assumption that the Markov chain induced by policy a is ergodic. In particular, this implies that d (8, a) > 0 for all state action pairs (s,a) (Puterman, 2014). In scenarios where we are trying to optimize for (I),,, estimating the policy gradient becomes difficult. This is because the Bellman equation cannot be used to estimate Q-function for γ = 1. As a compromise policy gradient for average reward scenarios are instead approximated by calculating the Q-function for a discounting factor y < 1, but close to 1, and using that estimate the policy gradient equation
VeJI (Te) = =E (s.a)) -d 1QT (8, a) Va Io
(4a)
(s.))ddd 10 (8, a) Vo log ma(a)))], 7 <
(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 characterizes that error,
VoJI(TT) = (o (s, Vo log [o(ass] + +1 - (1) (o log log (8) V (s)
(5)
Residual Error
In this paper, we prove that this rosidual crror is significant. What morc, we also propose another mothod to exactly obtain the policy gradient, for all values of the discounting factor including 7 = which we call as the log density gradient. Our estimation of log density gradient utilises average state-action discounted distributional formulation of reinforcement learning problem which re-states (x) expectation under
d (Nachum et al., 2019; Uchara al.)
Jn (T) = E (s.))=a7 (s).
Under this formulation, policy gradient similarly be obtained using log derivative trick as follows,
VoJy(T) (eaa)_a Ve log "f (s, a) rss,
We refer to Vo log d 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 (7 = 1).
3 Survey of Related Work and Comparison
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-polic evaluation. A short discussion on Temporal Difference (TD) learning methods may be found in Appendix 9.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 are also designed to be 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) have been introduced which update policies while ensuring monotonic performance improvement. To the best of our knowledge, Log density gradient has only been
Literature survey:
4

---

Published in Transactions on Machine Learning Research (10/2024)
discussed in Morimura et al. (2010) in which a TD method to estimate log density gradient for average reward scenarios by using reversible backward Markov chain is proposed.
Comparison: In our paper, we re-introduce the idea of log density gradient introduced by Morimura et al. (2010) for estimating gradient in the average reward scenario. Morimura et al. (2010) was also the first work to find out the residual error in policy gradient approximation (Proposition 2). Additionally, this work proposes estimating log density gradient specifically for average reward scenarios (? 1) using TD update, with additional extensions for linear function approximation.
Our work not only fixes many technical gaps evident in the theory of log density gradient as proposed by Morimura et al. (2010) but also builds on them to make log density gradient practical. We first define log density gradient (equation 10) over a range of discounting factor E [0, IJ, which also includes the average reward scenario. Using Lemma 2 and 3 we then prove mathematical conditions under which the log density gradient is unique and can be exactly calculated. We further use this relation to propose a TD form of updates (equation 14) for log density gradient estimation for all values of discounting factor 7 E [0, 1] against the average reward scenario proposed by Morimura et al. (2010). In Lemma 4 we further prove that these TD updates converge to unique solution for all values of discounting factor Y except 1. Thus, effectively demonstrating that TD-updates proposed by Morimura et al. (2010) does not converge to the true log density gradient, further limiting their use for large scale problems. Additionally, to make log density gradient estimation viable for practical problems, we propose a min-max optimization approach (equation 17) that allows us to estimate log density gradient using empirical samples. We also demonstrate that under linear function approximation settings, this min-max max optimization not only has a closed form but also converges to unique solution (Theorem 1). Under weighted updates, as proposed in algorithm 1 we also show bound sample complexity of log density gradient estimation of the order of O
3.2 Density Ratio Learning
Literature survey: Off-policy evaluation estimates the performance of a target policy a using an offline dataset generated by a behavior policy (Voloshin et al., 2019; Katdare et al.). This is done by estimating d_ the average state-action density ratio z which allows approximation of the target policy's performance. In this work, we are primarily intcrested 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 fddivergence of their choice) between the two distributions d" and de in their convex dual form, eliminating the need to obtain samples from d=,, which results in 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.
Comparison:
4 Roadmap
Before we begin the technical exposition we would like to give high level idea of the building blocks involved, and how each step connects to the next.
To that end, we finally propose a min-max version of log density gradient which allows to approximate Vo log t 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.
In Section 5, we first propose model based approach to approximate the log density gradient for tabular scenarios. To that end, we propose an optimisation problem, the solution to which is the log density gradient. Then we prove some properties about the solution of the optimisation problem, in particular. Next we suggest, a temporal difference type method to solve the optimisation problem using samples from the controlled Markov chain. We prove certain uniqueness and convergence propertics about the solution obtained from the TD method. However, the TD method works under a very restrctive assumption: it requires backward samples from the Markov chain. To cireumvent this assumption we proceed to the next section.
5

---

Published in Transactions on Machine Learning Research (10/2024)
In Section 6, we first convert the original optimisation problem into min-max problem using Fenchel duality. Then we propose a TD-type algorithm to solve the min-max problem. This new TD algorithm needs only samples from the forward Markov chain, and subverts the need for backward samples of the previous algorithm. We conclude the section by proving results about the solution of the TD algorithm, and introducing a function approximation framework for the TD method (with proofs of convergence).
5 Log Density Gradient
In this section, we introduce log density gradient approach policy gradient estimation. By deriving the gradient of log density, we demonstrate that traditional policy gradient methods are not well-suited at approximating policy gradient through average reward scenarios. The log density gradient approach addresses this limitation, allowing us to estimate both the average reward and discounted reward formulations. We first propose a model-based approach to log density gradient estimation which relies on Bellman-type recursion to exactly calculate policy gradient. We then extend this to a Temporal difference (TD) version of policy gradient estimation which will allow us to estimate gradient only using on-policy samples.
5.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.a We start by observing that di satisfies an identity called the Bellman flow equation Liu et al. (2018); Nachum et al. (2019).
Lemma 1. The average state-action density distribution di satisfies the Bellman flow equation V(s, a, s') S AxAxS,
+ E(((s.))(()sss Vy [0.1]
A detailed proof for the same can be found in the Appendix 9.3. Note that the Bellmam flow equation equation similar to the classical Bellman contraction except that is reversed. Unlike the classical Bellman contraction, the Bellman flow equation shows us the relationship of the next state s' with previous state-action pair (s, a). In that sense, the Bellman flow equation is reversed and requires samples from reversed MDP to estimate dF, accurately. In the following Lemma, present an optimisation problem, the solution of which is same as the solution of equation 7. This optimisation problem will be used in later development.
Lemma 2. Choose an arbitrary but fixed X > 0. For all y E [0, 1] the solution to the following optimisation is unique and equal to d=e
1 w(s') - w(s')-(1- -1--))do(s)) + +7 > ((()))oaas)PP(5155 + 2 w(s) 1)
arg min S
Detailed proof can be found in the appendíx 9.4. Intuitively speaking, the term 2/2 E, w(s) 1)2 is redundant for 1, and only becomes useful for average reward scenarios wherein y thus holping ensure uniqueness.
Recall that we are interested in estimating the log density gradient, which is the gradient of the log of density with the policy parameters Ve log di Similar to the Bellman flow equation equation 7, the log density gradicnt also follows a similar recursion which can be obtained by taking the gradient of the Bellman flow equation with respect to the policy parameters as follows:
da (8') log d: (s') = Σ (s.))))))1
(s,
(9)
8,0
Multiplying both sides by no (a'ls')) and recalling that d: (s, di (s) obtain
(5 d'V log (s', - Vo log (og'(('ls')) = > Σ
che (s, a log d: ()ss (P (10)
8,a

---

Published in Transactions on Machine Learning Research (10/2024)
Furthermore, if we have exact knowledge of the transition matrix P, we can exactly calculate the log density gradient by solving for the following optimization problem
{ (io lu(s' 2 ar A
min
+ 2 Floasmapoou (u(sss a'>)]
(11)
vis', = d. (s'
V lol' 5'))~> -2 Σ
Lemma 3. For X >>0 O, the solution to equation 11 is unique and equal to V Volog do for all y E [0.
We describe the proof for this Lemma in the appendix 9.5. Note that the constraint 2 E as [wo(s', d')]l² is redundant for 7 < 1 and only becomes useful for average reward scenarios 1. For a finite state and action space, the proof follows from the fact that the optimal solution to equation 11 requires solving for a linear equation A w = The remaining part of the proof demonstrates that this matrix A invertible for Vy [0, 1]. It worth reiterating that, once we have an estimate Vo log d 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 recalled from equation 6
VoJ,(T) = ((s Vo log di (s, a) r(s,
is exactly equal to the classical policy gradient (Sutton et al., 1999) recalled from equation 2
VaJy((a) = (, 1Q70 (s, a) Vy lo(sss))))),, 7 E [0,
Detailed proof for this proposition can be found in Appendix 9.2. essence this results shows us that log density gradient approach policy gradient estimates the exact same gradient but using a different formulation. Additionally log density gradient formulation allows us to estimate policy gradient for average reward formulations. It is well known that, the classical policy gradient theorem is in-sufficient to estimate gradient for average reward scenarios. This is because the Bellman equation for reward case (r = 1) is not contraction, making it harder to approximate Q-function using neural networks. As a compromise, reinforcement lcarning practioners typically approximate policy gradient for average reward scenario using a discounting factor slightly less than and use that to update policy. Our next result shows that such a way to approximating policy gradient ignores a residual error, which is not necessarily small. Correcting for this residual error, can not improve policy gradient estimation but also potentially help improve sample complexity of reinforcement learning algorithms.
Proposition 2. The following identity (recalled from equation 5) is true
VOJI(TT)) = ((s 10.7 (8,"(8,)) (8,a).Vo. log mo(a]s)] + -1-77 ()- (s.)) Vo oo (8) V.Te (a)
Residual Ervor
Proof. From the definition of log density gradient equation 6 we have VoJI(TO) = B(e,a)ma Vo log di (s.a). r(s, a)]. Let 7 1, and we use the Bellman equation 1b to obtain
VoJi(To) B( Vo log T (s, a) (Q (s. a) 7B, -P (s')))
(12a)
( to (V, log d (s) + V log To (als)) (0 (s, a) - -. [s,)) (s')))
(12b)
B.isa)aa 1Q7 (s, a) V log (alss)
F) gm [ log ui (s, V=*
(12c)
Here, we go from equation 12a to 12b by utilizing V, log d (s, a) V log d:. (s) + Vo log (a(ss) We finally go from 12b to 12c by using a key identity of log density gradient equation 10.
Note that the first term in equation 12b is the practical instantiation of classical policy gradient theorem, while the second term (1 - 7) s | v log of (s) ViT (s)] being the residual error. This completes the proof.
7

---

Published in Transactions on Machine Learning Research (10/2024)
To recap, in this section, propose Bellman-like relationship for the log density gradient, which further allows estimate the gradient using simple but known optimization. Next, we propose a Temporal difference (TD) type method to estimate log density gradient using samples.
5.2 Temporal Difference Log Density Gradient
In this section, we begin to estimate log density gradient algorithm using just on-policy samples. To that end, first step, we propose temporal difference approach to log density gradient estimation. We refer to our method as TD(0) method. To get update equation for TD(0) method, consider ro-arranged version of equation 10 for log density gradient,
Σ d= (s, a) (s) V log dh. (s,
Vo log d:o (s' a') Volog +
(13)
dr.(('','')
As mentioned carlier, this recursion is backwards as compared to the Bellman contraction. In order to see that, we will first define the backwards distribution Ps S x A + ASS, such that
Pa(s,als',a') (ss..a)P(s(ss.))T(())
d ds, (s.,)) (s'aa'ss,)) di (8'
This backwards distribution Ps estimates the probability the previous state (s, a) given the next state (s',a') The mathematical form of the backwards distribution thus, consoquence of Bayes' rule. The summation in equation 13 therefore becomes an expectation under Pb
Vo log de a') = Ve log (a'''s) + (P d:, (s,
The log density gradient is therefore said to follow backward recursion and it requires samples from backward conditionn ional probability Py to estimate log density gradient?. Assuming that we have samples from this backward distribution Po we now propose TD updates to estimate log density gradient w for all discounting factor 7 E 10,
w(s',a') + w(s',a' a') + alrw(s, g(s's w(s's,a a')},
(14)
with (s',a') d: (s, Po(-Is',a') and g(s' a') == Ve Te It is worth noting that this TD(0) update is generalization of Morimura et al. (2010), who only propose these updates for average reward scenario (7 1).
Next we define an operator Y, to capture the behaviour of the update rule equation 14 after taking expectation as,
(Y, w)( = 3= ( (w(s g(8(.
We can write this in matrix form as follows,
Y W = -W m5 DT, W +G
(15)
where, E |lS)-IA||x is the matrix with every row corresponding to w/ss a) for each state-action pair (s, a). Similarly, Ge R SI-Aaxnn has its rows as Vo log n for each state-action pair. Let Pry, Dr, E TR. (ISS)-AA where (Psa) ())) = (s', a'|s, a) and Dxo is a diagonal matrix whose every element correspond to d for each stato-action pair. We use this matrix form for the operator Y, in the proof of the following lemma.
Lemma 4. Let we E A) be an arbitrary initial guess. Let we = Y, W for all natural numbers k: > 1. For y [0, 1), the operator Y, contraction, and {wx]a20 converges
unique fixed point Va log di
There a family of TD methods which incorporate prior traces in discounted manner called TD(A) (Tesauro, 1992). 2 Althhuuhh 7 we use samples from P as well (Morimura al., 2010)
8

---

Published in Transactions on Machine Learning Research (10/2024)
Detailed proof of Lemma 4 can be found in Appendix 9.6. The key idea behind this Lemma is to show that successive application of the above mentioned TD updates will help us estimate the log density gradient accurately. In-fact we also show that these TD updates are contraction, thus effectively ensuring convergence. Extension of Lemma 4 to linear function approximation, and proof convergence for the same, can be found in the Appendix 9.7.
Although TD methods are known 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 propose min-max optimization procedure for estimating the log density gradient.
6 Min-Max Log Density Gradient
In this section, we propose min-max optimization approach to evaluate log density gradient for all values of the discounting factor including the average reward scenario (7 1). Doing so removes the need for samples from backward distribution, which was limiting scalability of log density gradient method described in the previous section. Min-max optimizations also allow to use large variety of function classes like neural
networks to approximate log density gradient.
Let us return to the loss function that we initially propose in equation 11. Classical machine learning algorithms usually posit loss function as Empiricial Risk Minimization (ERM), which allows us to approximate the loss using samples from that distribution. In order to bring our key optimization in an ERM form, consider a modified form of the optimization proposed in equation 11 (the modification is that 8(5', a') is divided by dz 16',00 a') where the ergodicity assumption ensures this operation well defined),
|| - u(s) a')
12]
A
arg min wESXA-22"
d (s', a²)
(16)
2
= v(s'a')= = de (s', a d')(((sss'
Vo log To (a(a's))) - ((
The denominator term d5 is added to ensure that the final optimization form can be written in form of an expectation, which we shall see soon. This allows us to use samples to approximate our optimization function. We also add the regularization term )11l [w[ss, a)]ll which allows us to estimate log density gradient even for all values of the discounting factor including average reward scenarios (7 ===]] 1).
Since, equation equation 16 is re-weighting of equation 11 with the (dT (s, (s,a)) a))- the optimal solution for the both the equation is the same, thus ensuring uniqueness of the optimization.
By exploiting the Fenchel-duality, we can re-write this optimization in the minimax form (Rockafellar, 2015; Zhang et al., 2020b) as follows,
(w, = { ( If(s', a') w(s'
arg
min uxSx A-d f:SxA -. FERU
max
(s' a''dd' [fs'' a') Vo log (a(''ss)) - 7Th (a,amad [ (aa)) (f)) w(s,a)
2 F(na)ad70 ||| a' 13) + X(T E B(na))aaa (wos, a)l 2 [1113)
(17)
In many cases scarching over all function mappings S x A Rd is not possible, hence scarch over smaller and more tractable function classes W, F and the aim is to approximate
Vo log d ~ arg min max (,W,f,r)
wEW fEF,
Such a practical consideration allows us to use different types of function approximators like linear function approximation, neural networks, and reprodueible kernel Hilbert spaces (RKHS).
9

---

Published in Transactions on Machine Learning Research (10/2024)
In the remainder of this section, will focus linear function approximation, and provide an update rule to solve equation 17 under linear function approximation. For that we choose a feature map Φ S x A + Rd and parameters at 3 E _dx= that need to be learnt, so that we can approximate the optima of equation 17, w (s, a) and f* a) with a ((s a), and 5T a) respectively, for each state action pair (s. a). The update rule
6, 2, 1 (4))
(18a)
af+1 = at - E5( be + ()T
(18b)
B Bi + exla dt 9: - B $
(18c)
T++1 = To E((((a 41 Tz))
(18d)
where, t; ((s,, 01) is the feature encountered at time t, 9t Vo log (a(al)s)), and 0/ == L2 a() for (8t, uz) ~ d of P(-lse, ae), no (a(a)s/)) We first re-write the updates in equation 18 in form of de = (o,, 8e 7/ that the updates can be written in matrix form d de e, GGGr+1d hxt1), where, Gi+1, h are as follows,
0
A
-XP;
0
G ==
A,
Ct
0
hx+1 ==
B
\
0
-
and A; = ( - (0,)), B₁ = D97 C. == D. matrices as follows,
We can calculate the expectation for each of these
0
A
A D
G=
A
C
0
h = IE (2.) [h++1]
- B 0
de D
T
0
-
Here, each column of V E R|SH-AA) x is the feature vector (s, for cach (s,a) SxA and IR" is vector of I's at every element. We can similarly write A = Dr, (I yPa, ) == GD,,, DD, De and Ey[1 = E (x.a)>dd" = We can now prove the convergence of linear function approximation under the following key assumptions.
Assumption 1. 1. The matriz & has linearly independent columns.
2. The matrix A is non-singular or the vegularizer X >> 0.
3. The feature matrir has uniformly bounded second moments.
Theorem Under the assumptions 1, the update equation 18 converges in probability to unique solution. That is, lim de G in probability.
The detailed proof is provided in Appendix 9.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 18. To that end, we propose Algorithm called the Projected Log Density Gradient. We choose closed, bounded and convex sets X C pdxx Y C Rdxx Z C R xx and define projection operator IIx, Ily, Ill that project our variables Sc, Te onto X, Y. 7 respectively. Moreover, we choose a learning rate ) where we run the algorithm for m steps. The details of the choice of learning rate are found in Appendix 9.9.
Theorem 2. Under assumptions for (a, 3, obtained from Algorithm 1 after m steps, the optimality gap () 5) (defined below) is bounded with probability 8 as follows,
2 - min L(a, 3,7) s Coy (8 2log 8 w.p. 1- aex
5
3,7) = max
(B,T)EY x2
where, Co is a constant which is a function of the sets X, Y,Y, Z, and the second moment of T.
We present the proof of this result in appendix 9.9. This result essentially shows that the upper-boure for log density gradient estimation requires 0 (()))) (where m is the number of steps the algorithm runs for) samples to learn accurate estimation.
10

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 1 Projected Log Density Gradient
1: for t = 1,2..... m do:
2: ó = 2, - ,,,
3: a++1 = [Ix (a, - Ex( 5e de +()
4: Bi+1 Ily 18y + t dt - g. - Bf ()
T+11 [ ( Dt- T()))
Return a, 7
Where, a 1--0 51
3
1-0 61
Algorithm 2 Linear Log Density Gradient
1: for t= 1,2..... m do:
2: a" = arg ain Bax (w. f,T) (equation 17)
(TT) E (aa))aFF (Vo log of (8,
(g.a).rlo . r((,,)]
4: Return 0
7
Experiments
In this section, we present a proof of concept for our log density gradient estimation on two sets of environments 5 x 5 and 3 x 3 gridworld environment (Towers et al., 2023). For the gridworld experiments, we approximate log density gradient by using linear function approximation (Algorithm 2). Here, the features are ø S + RISI-AA such that it maps every state to the corresponding standard basis vector. Our results for 5 are in Figure 2 and for 3 in Figure
We compare algorithm against 3 different baselines. The first is thcoretical log density gradient 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 (r 1) by estimating Q-function for 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 thelretical log density gradient which serves to validate correctness of our algorithm. In 5 x 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.
8 Conclusion and Future Work
We present log density gradient algorithm that estimates policy gradient using state-action discounted formulation of 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 needs samples from the backward Markov chain, which becomes too restrictive. Therefore, 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.
propose min-max optimization that estimates log
Limitations: Currently most of our experimental results require Lincar function approximation to estimate log density gradient. This because under linear function approximation conditions, our min-max optimization equation 17 becomes quadratic program and thus has closed form solution. To scale log density gradient.
11

---

Published in Transactions on Machine Learning Research (10/2024)
Log Density (ours)
Theoretical Log Density
Policy
200
175
Average Timesteps
150
Average Rewards
400
-600
-100
25-
-1800
0 25 50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Episodes
Epsiodes
Figure 2: For x 5 gridworld, comparison of Log Density Gradient algorithms (in light green) as compared to REINFORCE (light red), thcoretical policy gradient (gray) and theoretical log density gradient (bluc). We observe that our empirical algorithu comfortably outperforms the other baselines.
Min Max Log Gradient (ours)
Theoretical Gradient
REINFORCE
Thcoretical Gradient
30
120
-50
Average Timesteps
100
20
Average Rewards
-100
10
-150
40
-20
20
250
330
-10
60
120
140
20
80
100
120
140
Episodes
Epsiodes
Figure 3: For x 3 gridworld, comparison Log Density Gradient algorithms (in light green) as compared REINFORCE (light red), theoretical policy gradient (gray) and theoretical log density gradient (blue). We observe that our empirical algorithm comfortably outperforms the other baselines.
algorithms complex cases requires evaluating high quality features which will also allow us estimate gradient accurately Zhang et al. (2022).
12

---

Published in Transactions on Machine Learning Research (10/2024)
References
Baxter, J. and Bartlett, P. L. Infinite-horizon policy-gradient estimation. J. Artif. Int. Res., 2001.
Borkar, V. and Meyn, S. P. The o.d. e. method for convergence of stochastic approximation and reinforcement learning. 2000.
Boyan, J. A. Least-squares temporal difference learning, In ICML, pp. 49 56, 1999.
Bradtke, S. J. and Barto, A. G. Linear least-squares algorithms for temporal difference learning. Mach. Learn., 1996.
Gelada, C. and Bellemare, M. G. Off-policy deep reinforcement learning by bootstrapping the covariate shift. The Thirly- Third AAAI Conference on Artificial Intelligence, AAAI, 2019.
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, A. and Mannor, S. Consistent. on-line off-policy evaluation. In Proceedings of the 34th International Conference Machine Learning, ICML 2017, 2017.
Tyas, A., Engstrom, L.,, Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L.,, and Madry, A. A closer look doep policy gradients. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
John Schulman, Barret Zoph, C. K. et al. Chatgpt: Optimizing language models for dialogue, 2023.
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.
Katdare, P., Liu, S., and Campbell, K. D. Off environment evaluation using convex risk minimization. 2022 International Conference on Robolics and Automation, ICRA 2022.
Lillicrap, T. P., Hunt, 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.
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-Pirss Conference Uncertainty in Artificial Intelligence, UAI 2015.
Liu, Q., Li, L., Tang, Z., and Zhou, D. Breaking the curse of horizon: Infinitohhoizon off- off-policy estimation. In Advances in Neural Information Processing Systems 31, 2018.
Maci, H. R. Gradient cemporal-difference learning algorithms. In Ph.D thesis, 2011.
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillierap, 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, T., Uchibe, E., Yoshimoto, J., Peters, J., and Doya, K. Derivatives of logarithmic stationary distributions for policy gradient reinforcement learning. Neural Comput., 2010.
Nachum, O., Chow, Y., Dai, B., and Li, L. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems 32, 2019.
Nemirovski, A., Juditsky, A. B., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 2009.
Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons. 2014.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Robbins, H. and Monro, S. A Stochastic Approximation Method. The Annals of Mathematical Statistica, 22 (3):400- 407, 1951. doi: 00.1214/0mms/117772955 URL https://doi. /tg//....1444/mmm/7777755556
Rockafellar, R. T. Conver Analysis. Princeton University Press, 2015.
Schulman, J., Levine, S., Moritz, P., Jordan, M. I., and Abbecl, P. Trust region policy optimization. CoRR, abs/1502.054477, 2015. URL http://arxiv.or//bbbee 1507.05477.
Schulman, J., Moritz, P., Levine, S., Jordan, M. I,, and Abbeel, P. High-dimensional continuous control using generalized advantage estimation. In 4th International Conference Learning Representations, ICLR, 2016.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. CoRR, abs/ 00//1707.004477 2017. URL http://arxis www.vorrg/gaooo org/abb//1777.06547.
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, D., Schrittwieser, J., Simonyan, K., and thers. Mastering the game of go without human knowledge. Nat., 2017.
Sutton, R. S. Learning to predict by the methods of temporal differences. Mach. Learn., 1988.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http://Ancomplleteideee hwtpsecktteeeeeeeeeeeeoeee hatpbooookhhheooooooooooo book- 2nd. html.
Sutton, R. S., McAllester, D. A., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Aduances in Neural Information Processing Systems, 1999.
Tesauro, G. Practical issues in temporal difference learning. Mach. Learn., 1992.
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-Vite Vicente, R., Pierré, A., Schulhoff, S., Tai, J. J., Shen, A. T. J., and Younis, O. G. Gymnasium, March 2023. URL https: //eeodo..oooo///e///////oo//o... hetg/eccord/8127000
Uehara, M., Huang, J., and Jiang, N. Minimax weight and q-function learning for off- off-policy evaluation. In Proceedings of the 97th International Conference on Machine Learning, ICML 2020.
Voloshin, C., Le, H. M., Jiang, N., and Yue, Y. Empirical study of off off-policy policy evaluation for reinforcement learning. 2019.
Williams, R. J. Simple statistical cradient-following algorithms for connectionist reinforcement learning. Mach. Learn., 1992.
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, Procoodings of Machine Learning Research, 2022.
Zhang, R., Dai, B., Li, L., and Schuurmans, D. Gendice: Generalized offline estimation of stationary values. CoRR, abs/2000 22002009072 2020a. URL
Zhang, S., Liu, B., and Whiteson, S. Gradientdice: Rethinking generalized offline estimation of stationary values. CoRR, abs/2001.111111 2020b. URL https://arxiv.orgg abs///1....00/./ http:///rr......r/a///.//000.0 11113.
Zhang, T., Ren, T., Yang, M., Gonzalez, J., Schuurmans, D., and Dai, B. Making linear mdps practical via contrastive representation learning. In International Conference on Machine Learning, ICML, Proceedings Machine Learning Research, 2022.
14


Reviews:
[{"review_id": "l7yrmqiEtr", "reviewer": "Reviewer_MfXw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper presents a theoretically grounded approach to policy gradient estimation in reinforcement learning. This paper further consolidate the theoretical foundation of the Morimura's method (log density gradient method). The log density gradient is so different from classical policy gradient and does not suffer from the residual error in classical policy gradient that it worth more attention of the community.\n\nThe min-max optimization formulation is particularly noteworthy as it overcomes the limitation of requiring backward Markov chain samples, making the method more practical for real-world applications.\n\nWeakness:\n\n1. This writing of mathematical equations and theorem statement should be improved for its rigorousness. For examples: In the definition of operator $Y_\\gamma$ between Eq 13 and 14, $(s, a)$ should be sampled from the backward MC. The textual part of Proposition 1 and Proposition 2 should be written in a more formal language, and it should be self-contained: i.e. no \"mentioned in Eq. x\". \n\n2. This paper should have a complete policy updating algorithm psedu-code or description. In the current version, after Section 3, the whole problems seems becoming how to estimate log density gradient. After solving that, the paper need to go back discuss what's the policy gradient and update rule, what's the effect of using an approximation of the log density gradient in the policy gradient.\n\n3. The paper should discuss more limitation of the log density gradient methods in comparison with classical PG. For example, the TD method of log density gradient updates a d-dimensional vector function, where d is the number of policy parameter. Standard TD (to estimate the Q(s,a) in PG theorem) only need to update a real-valued function. For modern NN, d is huge. This is a significant concern of the scalability of the method.\n\n4. The experimental domain is a 5x5 grid world.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper re-introduces a the method called \"log density gradient\" in Morimura 2010 for estimating policy gradients in reinforcement learning, based on the gradient of log density. The authors show that the Morimura's method corrects for a residual error term that is often ignored in classical policy gradient implementations. The author derived the log density gradient in discounting setting, and a new optimization method to estimate the gradient of log density without sampling from backward Markov chain. Theoretical analysis is provided, proving convergence and uniqueness properties of the min-max optimization, as well as sample complexity bounds. These are novel contribution and is not included in the Morimura paper.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the three request in the weakness 1-3.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DhmiJRhKlx", "reviewer": "Reviewer_5zdo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work has a comprehensive summary of the existing literature.\n2. I am not an expert in this area and hence I didn't check the proof in Appendix in detail, but all the arguments look sound to me.\n\nWeaknesses:\n1. I feel the presentation of this work could be improved.\n1.1 There are some typos, e.g.: in page one \"we empirically demonstrate that this error 'in' indeed significant\"; in page 5, there is no verb in the sentence \"Thus, effectively demonstrating that TD-updates...\"\n1.2 Some parts are confusing and hard to understand: e.g. in page 5 sentence \"Thus, effectively demonstrating that TD-updates...\", I don't understand why your proof (converging to a unique solution) could showcase the drawback of the method from Morimura. Will this result indicate the drawback of your methods as well?\n2. I feel the baseline in your experimental results is a little bit too weak. It would be better to compare your method with some modern policy gradient based algorithms but not just REINFORCE which is about 30 years old. And real-world datasets should also be used in your experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper uses the log density gradient idea to correct for the residual error in policy gradient estimation. And then a model-free TD based method is used to approximate the policy gradient with some theoretical guarantee. To overcome the practical inefficiency issue, this work further implements the min-max optimization idea that works under the on-policy samples and present some theoretical results under the linear function class assumption, which enables their method to work for the linear MDP problems. Empirical results are presented to validate the high efficiency of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I feel that given the existing literature in Morimura et al. and Zhang et al., it may not be fair to state you \"propose\" the log density gradient and \"propose\" the min-max optimization, since your methods are adapted from the existing works. \n2. It would be better to summarize the min-max optimization methods in the existing literature, e.g. Zhang et al.. Since your method also adapts this idea.\n3. Including a recent baseline or adding some real experiments can make the experimental results stronger.\n4. How difficult it is to extend from the average reward scenario to the general case over a range of discounting factor $\\gamma \\in [0,1]$? What are the major challenges in this extension? Please briefly explain this issue in your work.\n5. A brief explanation on Assumption 1 is necessary.\n6. TD($\\lambda$) is not explained in the main paper (but in appendix) but TD(0) is used in the conclusion. Please briefly explain this notation before using it.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yu9aWEMrO2", "reviewer": "Reviewer_LKDn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe authors present a thorough derivation of both the problems with existing approaches, and their solution. By providing both a population version, a sample based estimation approach and a sample complexity bound, they cover a good set of interesting questions relating to a novel approach.\n\nAs far as I can tell, all proofs are correct (although see the following).\n\nWeaknesses:\nThe exposition and presentation of the paper makes following the core derivations and results hard. The proofs in the appendix do not all restate the statements which are being proven, and equations across the paper are referenced requiring a reader to jump back and forth a lot. Furthermore, derivation steps could be shown with more detail, reconstructing some of the steps has taken me a non-trivial amount of time. The authors also at several points refer to proofs in other papers. I would prefer if the authors either restated results from other papers they are using explicitly, or rewrite the proofs in full here. The paper should be readable by itself as much as possible.\n\nOne concrete example for unclear exposition is the introduction of Lemma 2: the role of $w(s)$ is not explicitly stated in the leadup to the lemma, nor after. This means the reader has to intuit by themselves what the purpose of its introduction is. Overall, I would encourage the authors to thoroughly rework the expository text for the mathematical results. I first assumed the role is simply to approximate $d^\\pi$, but later the same variable is used to approximate the gradient of $d^\\pi$, so it is simply used as the \"variable to learn\" in each lemma?\n\nIn the text after Lemma 2, the exposition jumps back to the term $\\nabla d$ without any transition or even a paragraph break. This is related to the previous problem. From context I reconstructed that the authors intended to present to successive lemmas about the learnability of $d$ and $\\nabla d$ respectively, but this was not stated clearly.\n\nThe experiments are very small scale, with tiny grid worlds. It would be interesting to see if the sample complexity shown by the authors is sufficient to scale up to slightly more complex problems, like larger gridworlds, standard testing benchmarks such as cliffwalk, chainwalk, garnets, or maybe mountain car.\nIn the same spirit: as the authors motivated their sample based approach by highlighting how it enables function approximation, I think it would be a good idea to show small results with function approximation, such as tiling features over gridworlds. While they claim that they use function approximation, they are using one-hot features per state-action pair, which is basically equivalent to a tabular method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a novel technique for estimating the policy gradient in the case of an average reward scenario. Existing techniques rely on $\\gamma < 1$ to obtain an algorithm, but as previous work has shown, this results in a biased gradient when using a $Q_\\gamma$ function to estimate the average reward policy gradient.\n\nThe paper presents both a full estimate based on the backwards state transition probability and a more application friendly sample based version. Finally, the efficacy of the approach is verified in a small scale grid world experiment.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Nice to have: In their introduction, the authors imply that most RL work is interested in the average reward formulation. I believe that this claim is slightly too strong and can lead to confusion: the policy gradient is (as far as I know) not biased if the goal is indeed to optimize for a discounted return (although almost no algorithm that is in practical use uses the discounted state visitation distribution, so I agree with the authors here that there is are come non-trivial oversights). The authors are correct that previous work has not been careful in differentiating between the goal stated in the respective works and those optimized by the presented algorithms, but I would argue that both optimizing for a discounted or average reward scenario is a valid goal. I would encourage the authors here to clarify the introduction to highlight under what conditions the policy gradients are biased.\n\nNice to have:\n(slightly) larger experiment with actual function approximation\n\nVery good to have:\nThe paper has quite a few typos and grammatical errors, another editorial pass would be good.\n\nCritical:\nRework and expand the explanation of the method, the purpose of introduction for each step in the derivations, etc. I am currently rating the paper as having no \"accurate, convincing and clear evidence\" not because I have serious doubts about the correctness of the derivations, but because I believe that the writing can and should be seriously improved before acceptance. I want to stress that I believe that the contribution is both valuable and correct (as far as I can tell) and I commend the authors for their work but simply not really easily accessible in its current form.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors already improved the organization following the reviewers suggestions in the revised version. 

Please change the color of the revised component to normal.
Decision: Accept (poster)