Average Reward Reinforcement Learning with Monotonic Policy Improvement
Authors: Yiming Zhang
Keith W. Ross
Venue:  (2021)
Keywords: Reinforcement Learning
Deep Reinforcement Learning
Average Reward
Policy Optimization
Model Free RL

Abstract: In continuing control tasks, an agent’s average reward per time step is a more natural performance measure compared to the commonly used discounting framework since it can better capture an agent’s long-term behavior. We derive a novel lower bound on the difference of the long-term average reward for two policies.  The lower bound depends on the average divergence between the policies and on the so-called Kemeny constant, which measures to what degree the unichain Markov chains associated with the policies are well-connected. We also show that previous work based on the discounted return (Schulman et al., 2015; Achiam et al., 2017) results in a non-meaningful lower bound in the average reward setting. Based on our lower bound, we develop an iterative procedure which produces a sequence of monotonically improved policies for the average reward criterion. When combined with Deep Reinforcement Learning (DRL) methods, the procedure leads to scalable and efficient algorithms for maximizing the agent’s average reward performance.Empirically we demonstrate the effectiveness of our method on continuing control tasks and show how discounting can lead to unsatisfactory performance.

Under review as a conference paper at ICLR 2021
AVERAGE REWARD REINFORCEMENT LEARNING WITH MONOTONIC POLICY IMPROVEMENT
Anonymous authors Paper under double-bling review
ABSTRACT
In continuing control tasks, an agent's 's average reward per time step is more natural performance measure compared to the commonly used discounting framework since it can better capture an agent's 's long-term behavior. We derive novel lower bound on the difference of the long-term average reward for two policies. The lower bound depends on the average divergence between the policies and on the so-called Kemeny constant, which measures to what degree the unichain Markov chains associated with the policies are well-connected. We also show that previous work based on the discounted return (Schulman et al. 2015 AAchiam et al. 2017) results in non-meaningful lower bound in the average reward setting. Based on our lower bound, we develop an iterative procedure which produces a sequence of monotonically improved policies for the average reward criterion. When combined with Deep Reinforcement Learning (DRL) methods, the procedure leads to scalable and efficient algorithms for maximizing the agent's average reward performance. Empirically we demonstrate the effectiveness of our method on continuing control tasks and show how discounting can lead to unsatisfactory performance.
INTRODUCTION
The goal of Reinforcement Learning (RL) build agents that can learn nigh-performing behaviors through trdd--and- interactions with the environment. Broadly speaking, modern RL tackles two kinds of problems: episodic tasks and continuing tasks. In episodic tasks, the egent-envirooment interaction can be broken into separate distinct episodes, and the performance of the agent is simply the sum of the rewards accrued within an episode. Examples episodic tasks include training an agent to learn to play Go (Silver et al. 2016 2018) or Atari video games (Mnih et al. 2013). where the episode terminates when the game ends. In continuing tasks, such as controlling robots with long operating lifespans (Peters& & Schaal 2008 Schulman et al.) 2015 Haarnoja al. 2018), there is no natural separation of episodes and the agent-environment interaction continues indefinitely. The performance of an agent in continuing task is more difficult to quantify since for bounded reward functions, the total sum of rewards is typically infinite.
One way of making the long-term reward objective meaningful for continuing tasks is to apply discounting, i.e., we maximize the discounted sum of rewards ro + 7r1 + 7 + ... for some discount factor 7 E (0, 1). This guaranteed be finite for any bounded reward function. However the discounted objective biases the optimal policy to choose actions that lead to high near-term performance rather than to high long-term performance. Such an objective
while useful in certain applications is not appropriate when the goal is optimize long-term behavior. As argued in Chapter 10 SStton & Barto (0118) and in Naik al. (2019), a more natural objective is use the average reward received by an agent over every time-step. While the average reward setting has been extensively studied the classical Markov Decision Process literature (Howard) 1960 Blalkwell 1962. Veinott 1966 Bertsekas et al.) [195), it is much less commonly used in reinforcement learning. An important open question is whether recent advances RL for the discounted reward criterion can be naturally generalized to the average reward setting.
One major source of difficulty with modern DRL algorithms lies in controlling the step-size for policy updates. In order have better control over step-sizes, [Schulman et al. (2015) constructed lower bound on the difference between the expected discounted return for two arbitrary policies т and n'. The bound is function of the divergence between these policies and the discount factor.

---

Under review as a conference paper at ICLR 2021
Schulman et al. (2015) showed that iteratively maximizing this lower bound generates sequence of monotonically improved policies in terms of their discounted return.
In this paper, first show that the policy improvement theorem from Schulman et al. (2015) results in a non-mcaningful bound in the average reward case. We then derive a novel result which lower bounds the difference of the average rewards based on the divergence of the policies. The bound depends on the average divergence between the policies and on the so-called Kemeny constant, which measures what degree the unichain Markov chains associated with the policies are well- connected. We show that iteratively maximizing this lower bound guarantees monotonic average reward policy improvement. Similar to the discounted case, the problem of maximizing the lower bound can be approximated with DRL algorithms which can be optimized using samples collected in the environment. We describe in detail two such algorithms: Average Reward TRPO (ATRPO) and Average Cost CPO (ACPO), which are average reward versions of algorithms based on the discounted criterion (Schulman et al.) 2015] Achiam et al. 2017). Using the MuloCo simulated robotic benchmark, we carry out extensive experiments with the ATRPO algorithm and show that is more effective than their discounted counterparts for these continuing control tasks. To our knowledge, this is one of the first paper to address DRL using the long-term average reward criterion.
2 PRELIMINARIES
Consider a Markov Decision Process (MDP) (Sutton & Barto 2018) (S,A,P,r, where the state space S and action space A are assumed
finite. The transition probability denoted by P: x A x S + [0, 1]. the bounded reward function r S x A + [rmin maxx), and μ S + [o. 1] the initial state distribution. Let ग = ( (a]s) 8 E S.a E AA} be a stationary policy, and the set of all stationary policies. Here we discuss the two objective formulations for continuing control
tasks: the average reward approach and discounted reward approach.
Average Reward Approach
In this paper, we will focus exclusively on unichain MDPs, which is when the Markov chain corresponding to every policy contains only one recurrent class and finite but possibly empty set of transient states. The average reward objective is defined as:
N-1 r(st, an)
p(T) = lim N
E
Σ 0
E [r(s
N
Here (s) Nim E P(se s) lime-+o0 P(s: s/ is the stationary state distribution under policy π,, T = (so, ap..... )) is a sample trajectory. We use J ~ π to indicate that the trajectory is sampled from policy म, i.e. so nl, at (-(ss)), and 8:41 P(-Is,, at). In the unichain case, the average reward p(TT) is state-independent for any policy n (Bertsekas et al. 1995).
We express the sverage-rewarts value function as (T) == ETTN
Ero(r(ss
p(T))
30 =
and action-value function as (T = Erag Ego ai) - 50 = s, ap a) We
define the average reward advantage function as A AT (s,a) = (s, V V*(s).
Discounted Reward Approach For some discount factor 7 E (0, 1), the discounted reward objective defined as
(T( = E
Σ
rrr oe) =
E smid
(2)
THUT
am"
Er P(s s|x) is known as the future discounted state visitation distribution under policy Note that unlike the average reward objective, the discounted objective depends on the initial state distribution J.. can be easily shown that (s) - d=(s) for all s as
where
7 y-1 The discounted value function is defined as V (s) = E
E az)
Su and
discounted recion-value function (5(s. = ETar De0 7'r(st, at)
Su s0 = a Finally,
the discounted advantage function functiion is defined as A7( = (s) -V)(s).
2

---

Under review as a conference paper at ICLR 2021
It is well-known that lim,--1 (1 (x) p())). implying that the discounted and average reward objectives are equivalent in the limit as y approaches (Blackwell 1962). We will further discuss the relationship between the discounted and average reward value functions in the supplementary materials and prove that lim,->1 (x, a) = A (s, a) (see Corollary A.I
3 MONTONICALLY IMPROVEMENT GUARANTEES FOR DISCOUNTED RL
In many modern RL literature (Schulman et al. 2015 2017 Abdolmalcki et al. 2018 Vuong et al. 2019). algorithms iteratively update policies within local region, i.e., at iteration k we find policy Th+1 by maximizing Py (TT) within some region (TT, T s å for some divergence measure D. This approach allows us to control the step-size of each update using different choices of and 6 which can lead to better sample efficiency (Peters & Schaal 2008). Schulman et al. (2015) derived a policy improvement bound based on a specific choice of D:
(T((T4+1) (T() 2
E
[A (A, (s, C' max((rr(Tee) || [T)[s]]
soudag am
[a]ss]] is the total variation divergence for policies I and T', and C' is some constant which does not depend on the divergence term Drv. SShhuman et al. (013)) showed that by choosing Tk+11 such that the right hand side of (3) is maximized, we are
where (Iv(T' = IT (als)
guaranteed have P, (TK+1) 2 (Tx))) This provided the theoretical foundation for entire class of scalable policy optimization algorithms based on efficiently maximizing the right-hand-side of (3)
(Schulman al. 2015 2017; Wu al. 20177 Abdolmalcki al. 2018 Vuong al. 2019).
A natural question arises here is whether the iterative procedure described by Schulman et al. (2015) also guarantees improvement w.r.t. the average reward. Since the discounted and average reward objectives are equivalent when y + 1, one may assume that we can also lower bound the policy performance difference of the average reward objective by letting y + for the bounds in (Schulman it al. (2015). Unfortunately this results in non meaningful bound. We will demonstrate this through a similar policy improvement bound from Achiam et al. 2017) based on the average divergence but similar argument can be made for the original bound from Schulman et al. (2015) (see supplementary material for proof and discussion).
Proposition 1. Consider the following bound from Achiam et al. 2017
(x,)(²)) S py(=') - pT(T)) - D (T')
where
(alss)
276, E [Div('' [>|]]
D n, (I²) 1 1-
E swidy and
T<(as)) A3(),
(1 (1- 7) andy
and 6, = max, Bawny (A7 a)]. We have:
lim (1 - (1->) n.7 (T') (T') = to0
(5)
7-11
Since lim.,-1(1 (1) - (m) p( -( Proposition 1 says becomes trivial when used on the average reward. This result is discouraging as it shows that the policy improvement guarantee from (Shhulman et al. (2015) does not appear to generalize to the average reward setting, In the next section, we will derive an alternative policy improvement bound for the average reward objective which can be used to generate monotonically improved policies w.r.t. the average reward.
MAIN RESULTS
4.1 AVERAGE REWARD POLICY IMPROVEMENT THEOREM
Let dx E R be the probability column vector whose components (s), Pa E [ be the
transition matrix under policy я whose (s, component (=(sss) = E. P(s'ls, a))(a)s) and
Pt limr-ao pl be the limiting distribution for the transition matrix. We use I|-I|, p denote the
3

---

Under review as a conference paper at ICLR 2021
operator norm of matrix. In particular ||-1|1 and I1-1 are the maximum absolute column sum and maximum absolute row sum of a matrix respectively (Horn & Johnson 2012).
Suppose have new policy N' obtained via some update rule from the current policy Similar to the discounted case, we would like to measure their performance difference p(x') p(TT) using an expression which depends identity shows that p(x')= p(TT) can be expressed using the advantange function of æ.
and some divergence metric between the two policies. The following
Lemma 1. For any two stochastic policies and T':
p(T') p(T))
lim +0
E TIVE
Σ A (s,
(AT sodde
(6)
Lemma T is the an extension of the well-known policy difference lemma from Kakade & Langford (2002 to the average reward case. A similar result was proved by Neu al. (2010) Even- Dar et al. 2009). For completeness, We will provide a proof based on the Bellman equation as well simpler alternative proof in the supplementary material. Note that this expression depends samples drawn from n². However we can show through the following lemma that when de and dz are "close," " we can evaluate the expression (6) using samples from dg (see supplementary material for proof).
Lemma 2. For any two stochastic policies and n', the following bound holds:
E (s, -seri))- dx)) S p(m') p(T) < E (s, + 2eDrv(dr dx) (7)
sndd art
where c == max, E [a)a) a]]l-
Lemma 2 shows us how policy improvement related to the stationary distribution underlying each policy. In order study how policy improvement is connected to changes in the actual policies themselves, we need to analyze the relationship between changes in the policies and changes in stationary distributions. It turns out that the sensitivity of the stationary distributions in relation the policies is related to the structure of the underlying Markov chain.
Let M E S|S[ be the mean first passage time matrix whose elements Md (s, s') the expected number of steps it takes to reach state s' from under policy æ. The matrix (s, s') can be calculated via (Theorem 4.4.7 of Kemeny & Snell (1600))
(s, s') -
2" EZZ D
(8)
where === = P1- is known as the fundamental matrix of the Markov chain Kemeny & Snell 1960). E is a square matrix consisting of all ones. The subscript 'dg' for some square matrix A refers to diagonal matrix whose elements the diagonals of A. D* E ( is diagonal matrix whose elements are (d)x()). One important property of mean first passage time is that given some policy n:
Σ (s((s))((ssss')
=
is constant independent of the starting state 8. This result is known as the random target lemma (Aldous & Fill 1995). The constant RM is sometimes referred as Kemeny's 's constant (Grinstead & Snell 2012). This constant can be interpreted as the mean number of steps it takes to get to any goal state weighted by the seeady-distribution of the goal states. This weighted mean does not depend on the starting state, mentioned just above. The constant uses single number to summarize how "well-comnected"" a Markov chain is. can also be shown that x= = trace(22 (raace("))ae (Grinstead & Snell 2012). We then have the following result which connects the sensitivity of the stationary distribution to changes to the policy.
Lemma 3. The divergence between the stationary distributions dx and dur can be upper bounded by the average divergence between policies π and ni' as follows:
Drv(dw || dr) S (K= 1) E Drv((T' []]]]]
(10)
soud.
4

---

Under review as a conference paper at ICLR 2021
We wish to point out here that AAchiam et al. (2017) showed similar result to Lemma 3 in the discounted case where the change in dæ,y can be bounded in terms of the change in policy up to a multiplicative constant which only depends
the discount factor. In the discounted case, this is possible since a discounted MDP is like finite-horizon MDP problem; in fact, it can be shown to he equivalent to a related finite horizon problem (Proposition 5.3.1, Puterman (1994)) The discount factor can be used to control the effective horizon where larger discount factors correspond to longer horizons. In fact, can be easily shown that the multiplicttive factor from Achiam al.) (2017) goes to infinity average reward setting, the sensitivity of the stationary distribution with respect to the policy can vary depending on the chain structure and long-term behavior of the underlying Markov chain. This means that it is only natural that the multiplicative constant Lemma depends on the transition matrix.
- 1, meaning that the bound is not useful for long horizon problems. In the
This result is also highly intuitive, For very "well-connected" Markov chains where an agent can easily and quickly get to any state, this constant is relatively small and the stationary distributions are not sensitive to small changes in policy. On the other hand, for Markov chains that are "weakly connected," where on average, it can take long time to get to some recurrent state in the state space, the factor become very large. In this case small changes in the policy can have large impact on the resulting stationary distributions.
The following theorem connects the average reward performance of two policies and their average divergence.
Theorem 1. For any two stochastic policies ग and nτ, the following bounds hold:
x' ra(als)
p( p( <
E snad a
A A a)
+ 2 gnde
E
[Drv(T') [>]]]]
(11)
π (als)
xt (als)
p( p(x)) 2
E
A a)
26 andd
E
[Div(T'
|| [s]
(12)
soud
π (als)
where { (NeT' max, Eawn (AT a)).
Then rewrite the expectation for As a) as an expectation w.r.t. π using importance sampling gives us the desired bound.
Proof. Combine the bounds from Lemma 2 and Lemma
The right-hand-side of the bounds in Theorem | are guaranteed be finite. Similar to the discounted case, the multiplicative factor & provides a theoretical guidance on the step-sizes for policy updates (Schulman et al. 2015). The bound in Theorem Tis given in terms of the TV divergence, however the KL divergence is more commonly used in practice. [Vuong et al. (2019) compared various divergence measures and showed that the KL has superior empirical performance. The relationship between the TV divergence and KI. divergence is given by Pinsker's 's inequality (Taybakov] 2008), which says that We can then show that
for any two distributions p and q: Drv(p || 4) S DDL (pll4) /2.
E (Drv(T' srdd
m) [+]]
E [V DKL (T' [2 < Srdd
E [DKL (I' [<]]]//
(13)
where the second inequality comes from Jensen's inequality. that the bounds in Theorem still hold when Eynd, DDV((T'
The inequality in (3) shows T)[s]] is substituted with
/ /Band [Kx (x' (+)
4.2 APPROXIMATE POLICY ITERATION
One direct consequence of Theorem I is that iteratively maximizing the right-hand-side of 12) generates monotonically improving sequence of policies w.n.t. the average reward objective. Algorithm I gives an approximate policy iteration algorithm that produces such a sequence of policies.
Proposition 2. Given an initial policy To. Algorithm ? is guaranteed to generate a sequence of policies Ti, T such that p(TTO) S p(T)) S p(T2)
Proof. At iteration k, E, Eandey ar Equation 14p and Theorem ((Tx+1) p(TT) 0.
.aaTTIAA [A (s, a) = 0, Egnday [DLL (TT (T)) [s]] = 0 for Tg. By
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Approximate Policy lteration for Average Reward Objective
Initialize: T0
1: for k = 1, do
2: Policy evaluation step: evaluate A (s, for all s, a.
3: Policy improvement step:
T = argmiax
E [A* -E)
E onder
[KiL (T](TT)) [s]]
(14)
srudey
where & = (N= 1) max, Bawn (A**(s
However, Algorithm|] T difficult implement in practice since requires exact knowledge of the advantage function and transition matrix. Furthermore, calculating the term & is impractical for high dimensional problems. In the next section, we will introduce a sample-based algorithm which approximates the update rule given in Equation (14)
5 PRACTICAL APPLICATIONS
As we have noted in the previous section, Algorithm I is not practical for problems with large state and action spaces and thus cannot be naïvely applied directly. In this section, we will discuss how Algorithm|] 1 and Theorem can be used in practice to create algorithms which can effectively solve high dimensional DRL problems. In the Appendix C used to solve DRL problems with safety constraints.
dpplieddireetly..
we will also discuss how Theorem T can be
5.1 AVERAGE REWARD TRUST REGION POLICY OPTIMIZATION
For DRL problems, it is common to consider some parameterized policy class IT. S TT. Our goal is devise computationally tractable version of Algorithm for policies in Πe, i.e., given a policy Te, at iteration k. how do we obtain the best possible TBx41? ? We can rewrite the unconstrained optimization problem in (I4) as constrained problem:
maximize mellla
E goudegs arwty
[ATH (s, a)]
s.t. DKI. || Too) 28
(15)
[s]]. The constraint set {To E Ill DKL ( ) S 8} is called the trust region set. This problem can be regarded as an average reward variant of TRPO from Schulman al.j (2015). Note that the advantage function in (15) the average reward advantage function introduced in Section [ When we set T8 to be the optimal solution to (15).
where DKL (TT || moa) B a
[DKL (Te Te.)
To.+1 can shown to have the following performance guarantee:
Let Tezt1 be the optimal solution to (15) for some Te, Ill. The policy performance difference between 7o and no, can be lower bounded by
Proposition 3.
((TrrL)) p(Tee) 2 - 22 28
(16)
where g = (x. Tx 1) max, Ba A (s)
Proof. Since (Te,
To. O, TH is feasible solution. The objective value is 0 for T and (13) where the average KL bounded by 6.
The bound follows from 12
Several algorithms have been proposed for efficiently solving the discounted version of 15 Schul man et al. (2015) and Wu et al. (2017) converts (15) into convex problem via Taylor approximations; another approach is to first solve (15) in the nonparametric policy space and then project the result back into the parameter space (Abdolmaleki et al. 2018 Vuong et al., 2019). These algorithms can be adapted for the average reward case and are theoretically justified via Theorem and Proposition
3 One notable difference compared to the discounted case is the estimation of the critic, as discussed
the next section and in the Appendix

---

Under review as a conference paper at ICLR 2021
5.2 IMPLEMENTATION
In this section, we discuss how the average reward version of the TRPO algorithm (Schulman et al. 2013) which will refer as ATRPO can be implemented in practice. A provides a basic outline of the ATRPO algorithm.
Algorithm 2 Average Reward TRPO (ATRPO)
Initialize: Policy parameters Og. value net parameters do. learning rate a.
1: for k == 0, 1, 2. do
2: Collect sample trajectory {st, ot, St41, t == I,...,N from the environment using ne.-
3: Calculate sample average reward of Toe via N 21=1 Tt.
4: for t 2. N do
5:
Get target Vilaget - Vol (8t+1)
6:
Get advantage estimate A(se, 0z) r2 - p p+ Vol (86+1) Voa (8t)
7:
Update critic by
Φx+1 Φx aV [V)((
where
1 Σ VoL Viaree [(0x) 2
8:
Use A(st, an) to update 0% using TRPO policy update (Schulman et al. 2015).
The major difference between the TRPO algorithm and the ATRPO algorithm is how the target for the critic and the advantage function are calculated. Importantly, simply letting - 1 in TRPO does not lead to Algorithm 2 This subtle but important difference leads to a significant improvement in sample efficiency, shown in the section experimental results.
In Algorithm 2, for illustrative purposes, we use the average reward one-step bootstrapped estimate for the target of the critic and the advantage function. In practice, instead use average reward version of the Generalized Advantage Estimator (GAE) from Schulman et al. (2016). In short, GAE uses tunable eligibility trace parameter À to act as trade-off between the Monte Carlo estimate and the bootstrapped estimate. In the Appendix D we provide more detail on how GAE can be generalized to the average reward case.
RELATED WORK
Dynamic programming algorithms for finding the optimal average reward policies have been well- studied (Howard, 1960, Blackwell 1962. Veinott 1966). In contrary to our method which based on like
the policy gradient approach, several Q-learning like algorithms for problems with unknown dynamics
have been proposed, such as R-Learning (Schwartz) 1993), RVI Q-Learning (Abounadi et al. [000]] and CSV-Learnin (Yang et al.) 2016). Mahadevan (1996) conducted a thorough empirical analysis of the R- R-Learning algorithm. We note that much of the previous work on average reward RL focuses on the tabular setting without function approximations, and the theoretical properties of many of these Q-learning- based algorithm are not well understood (in particular R-learning). More recently. POLITEX updates policies using a Boltzmann distribution over the sum of action-valus function estimates of the previous policies (Abbasi- Yadkori et al. (219)) and Wei et al.] (2020) introduced a model-free algorithm for optimizing the average reward of rreakly-communicatinn MDPs. Both methods are shown to have theoretical guarantees under the tabular setting.
For policy gradient methods, Baxter Bartlett 2001) showed that if 1/(1 - -7) large compared to the mixing time of the Markov Chain induced by the MDP, then the gradient of p., (T)( accurately approximate the gradient of p(T). Kakade (2001) extended upon this result and provided an error bound on using optimal discounted policy to maximize the average reward. In contrast, our work directly deals with using policy gradient methods for the average reward objective and provides theoretical guidance the optimal step size for each policy update.
Policy improvement bounds have been extensively explored in the discounted case. The results from Schulman et al. (2015) is extension of Kakade & Langford (2002) which restricted the policy class
7

---

Under review as a conference paper at ICLR 2021
to mixture of policies. Pirottaa et al. (2013) also proposed an alternative generalization to Kakade & Langford (2002). /Achiam et al. (2017) improved upon Schulman et al. (2015) by replacing the maximum divergence with the average divergence.
7 EXPERIMENTS
Recently, DRL algorithms such as TRPO have proven to be successful for episodic high- digh-niimenionall tasks. In our experiments, we wish study whether for continuing-contrr tasks, the policy trained with ATRPO can out-perform the policies trained with TRPO with different discount factors.
Our design goal for the experiments to simulate continuing-come tasks where the agent can interact with the environment indefinitll. We consider three tasks (Ant, HalfCheetah, and Humanoid) from the MuJoCo physical simulator (Todorov al., 2012) implemented in the OpenAl gym (Brockman) al.] 2016). The natural goal is to train the agents the standard MuJoCo tasks are episodic tasks which terminate when the agent falls. We convert these tasks into continuing control tasks via the following: when the agent falls, the agent incurs a large cost for falling, but then continues the trajectory from a random start state. We use these continuing-control tasks for both training and evaluation for both ATRPO and TRPO. More details on the environment can be found in Appendix
fast possible without falling. However
One point wish emphasize regarding the experiments is that even though the MuJoCo benchmark is commonly trained using the discounted objective (see e.g. |Schulman et al. (0015). Wu et al. (2017), Schulman al. Abdolmalkkl et al. (2018), [Vung al. (2019)) it is always evaluated using the undiscounted objective. This is because the undiscounted objective more naturally describes the goals of the MuJoCo agents (e.g.. an agent's ' performance w.r.t. the reward signal should be equally important at time step 1000 as it is at time step 1). In the case of TRPO (and similarly many other DRL algorithms), discounting used during training often for mathematical and computational convenience. Prior to our work, there has been no theoretical or empirical evidence to support applying trust region methods to the average reward. In this section, we demonstrate that when the actual objective want to evaluate is undiscounted, discounting, as is commonly done, is unnecessary and may lead to suboptimal performance.
HallCheelah--4
Humanoid-v3
10
Average Reward
1.5
1.0
0.5
3
6
10
6
8
10
Million Samples
-0-
ATRPO -dr-
TRPO = 0.90)
-9- TRPO (y 0.95)
TRPO (y = 0.99)
-+- TRPO (y = 0.999) - TRPO (y 0.9999)
Figure 1: Learning curves comparing ATRPO and TRPO with different discount factors. The solid lines represent the average reward of trajectories of fixed length of 10,000 time steps averaged over the last 50 trajectories. The results are averaged over 10 random seeds and the shaded region represents one standard deviation.
During training, we collect one trajectory of a fixed length of 10,000 using the current policy ! We then use this data to update the critic and policy networks (see Algorithm 2). This gives us a new policy and critic which we then use to repeat the above process. In Figure [ we plot the
In the original OpenAl gym version of MuloCo, episode lengths are capped at 1000 (see lat / thub. com/ openai / /gym/b//// oalooo///es.... httttterrrgm//ee////// init -.py). .py). We removed this cap to allow for arbitrarily long time horizons.
8

---

Under review as a conference paper at ICLR 2021
training curves of ATRPO and of TRPO for different discount factors. Detailed specifications and hyperparameter settings can be found in Appendix
Figure D shows that ATRPO improves performance by 5.0%, 32.8%, 7% HalfCheetah, Ant and Humanoid respectively over TRPO with its best discount factors. One point worth noting is that increasing the discount factor does not necessarily lead to better performance of TRPO. A larger discount factor in principle enables the algorithm to seek a policy that performs well for the average-reward criterion. But, unfortunately. larger discount factor can also increase the variance of the gradient estimator (Zhao et al. 2 Schulman et al. 2016) and degrade generalization (Amil al. 2020p. Moreover, algorithms with discounting become unstable as y 1 Naik et al. 2019). The discount factor therefore serves as hyperparameter which can be tuned to improve performance.
This is supported by the observation that the optimal discount factor is different for each environment (0.999, 0.99, 0.95 for HalfCheetah, Ant, and Humanoid respectively), where choosing suboptimal discount factor can have significant consequences. (For Ant and Humanoid, the optimal discount factor is 33.9% and 65.6% better than the second best discount factor.) We have shown here that using the average reward criterion not only delivers superior performance but also obviates the need to tune the discount factor.
To further support our conclusion, we will also compare ATRPO and TRPO using an alternative evaluation protocol. In this protocol, after every million samples of training we run 10 separate evaluation trajectories of fixed length 10,000 time steps using the current policy with no exploration. The random seeds used for evaluation different from those used in training. Figure 2 shows the average reward of these trajectories, Once again ATRPO provides superior performance.
HallCheetah--33
Ant-y3
Humanold-vv
Million Samplis
-
ATRPO
TRPO 1y=00 0.93)
-9- TRPO (y 0.95)
TRPO (y 0.99)
- TRPO (y 0. 989)
- TRPO (y= 2.9999)
Figure 2: Comparing performance evaluation trajectories of length 10,000. For each random seed used in training, we use different unseen random seed to run 10 test trajectories after every I million samples of training. The solid line is averaged over these unseen random seeds. The shaded area is one standard deviation.
8 CONCLUSION
In this paper, we introduced novel policy improvement bound for the average reward criterion. The bound based on the average divergence between two policies and Kemeny's constant. We showed that previous existing policy improvement bounds for the discounted case results in non-meaningful bound for the average reward objective. Our work provided the theoretical justification and the means to generalize the popular trust-region based algorithms to the average reward setting. We demonstrated through series of experiments that our method is highly effective on high-dimensional continuing control tasks. In particular, we showed that when the natural objective of the task is undiscounted, discounting can lead to suboptimal behavior. To the best of our knowledge, we are one of the first to address how DRL methods can be used learn undiscounted continuing control tasks with large state and action spaces.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. International Conference on Machine Learning, pp. 3692-3702, 2019.
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posterion policy optimisation. International Conference on Learning Representation (ICLR), 2018.
Jinane Abounadi, D Bertsekas, and Vivek S Borkar. Learning algorithms for markov decision processes with average cost. SIAM Journal on Control and Optimization, 40(3):681-698, 2001.
Joshua Achiam. UC Berkeley CS 285 (Fall 2017). Advanced Policy Gradients,
2017. URL: http:::tttttlleeeeeeee lecture_ ___avvaade_____ pdf Last visited on 2020/05/24.
wew.eley..e........ edu/ http://ppp.cooue-aaa//a111100000
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 22-31. JMLR. org, 2017.
David Aldous and James Fill. Reversible markov chains and random walks on graphs, 1995.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Ron Amit, Ron Meir, and Kamil Ciosek. Discount factor as a regularizer reinforcement learning. In International conference machine learning, 2020.
Jonathan Baxter and Peter L Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1,2. Athena scientific Belmont, MA, 1995.
David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pp. 719-726, 1962.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Grace E Cho and Carl D Meyer. Comparison of perturbation bounds for the stationary distribution of markov chain. Linear Algebra and its Applications, 331(1-3):337-150 2001.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, (4(3):726-736. 2009.
Charles Miller Grinstead and James Laurie Snell. Introduction probability. American Mathematical Soc., 2012.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. International Conference on Machine Learning (ICML), 2018
Roger A Homn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Ronald A Howard. Dynamic programming and markov processes. John Wiley, 1960.
Jeffrey Hunter. Stationary distributions and mean first passage times of perturbed markov chains.
Linear Algebra and its Applications, 410:217-243, 2005.
Sham Kakade. Optimizing average reward using discounted rewards. In International Conference on Computational Learning Theory, pp. 605-615. Springer, 2001.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference Machine Learning, volume 2, pp. 267-274, 2002.
10

---

Under review as a conference paper at ICLR 2021
L.C.M. Kallenberg. Linear Programminng and Finite Markovian Control Problems. Centrum Voor Wiskunde en Informatica, 1983.
J.G. Kemeny and I.J. Snell. Finite Markov Chains. Van Nostrand, New Jersey, 1960.
Erich I. Lehmann and George Casella. Theory of point estimation. Springer Science & Business Media, 2006.
Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 22(1-3):159-113 1996.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. NIPS Deep Learning Workshop. 2013.
Abhishek Naik, Roshan Shariff, Niko Yasui, and Richard S Sutton, Discounted reinforcement learning is not optimization problem. NeurlPS Optimization Foundations for Reinforcement Learning Workshop, 2019.
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems, pp. 1804-1812, 2010.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural networks, 21(4):682-697, 2008
Matteo Pirotta, Marcello Restelli, Alessio Pecorino, and Daniele Calandriello. Safe policy iteration. In International Conference on Machine Learning, pp. 307-315, 2013.
Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John
Wiley & Sons, 1994.
Keith W Ross. Constrained markov decision processes with queueing applications. Dissertation Abstracts International Purt Science and Engineering(DISS. ABST. INT. PT. B- SCI. ENG.J. 46(4), 1985.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. International Conference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Anton Schwartz. A reinforcement learning method for maximizing undiscounted rewards. In Proceedings of the tenth international conference on machine learning, volume 298, pp. 298-305, 1993.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Thomas Hubert, Julian Schritwieser,, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances neural information processing systems, pp. 1057-1063, 2000.
11

---

Under review as a conference paper at ICLR 2021
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. International Conference on Learning Representation (ICLR), 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 TEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, IEEE, 2012.
Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008.
Arthur Veinott. On finding optimal policies in discrete dynamic programming with no discounting. The Annals of Mathematical Statistics, 57(5):1224-1223 1966.
Quan Vuong, Yiming Zhang, and Keith W Ross. Supervised policy update for deep reinforcement learning. In International Conference on Learning Representation (ICLR), 2019.
Chen-Yo Yu Wei, Mehdi Jafarnia-Jahrom,, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning infinite-horizon average-reward markov decision processes. In International conference on machine learning, 2020.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using kronecker- factorred approximation. Advances in neural information processing systems (NIPS), pp. 5285-5294, 2017.
Shangdong Yang, Yang Gao, Bo An, Hao Wang, and Xingguo Chen. Efficient average reward reinforcement learning using constant shifting values. In AAAI, pp. 2258-2264, 2016.
Yiming Zhang, Quan Vuong, and Keith Ross. First order constrained optimization in policy space. Advances in Neural Information Processing Systems, 33, 2020.
Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama. Analysis and improvement of policy gradient estimation. In Advances in Neural Information Processing Systems, pp. 262-270. 2011.
12


Reviews:
[{"review_id": "i5ZGejNafA", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper advocates for the use of the average reward objective in long horizon, continual reinforcement learning settings, and it examines whether a limiting argument for the discount is sufficient for extending theoretical results from the discounted setting to the average-reward setting. In the case of policy optimization, the paper shows the monotonic improvement bound from Schulman et al. (2015) becomes vacuous as gamma approaches one. The rest of the paper presents theory to support a new, non-vacuous bound, which leads to a new algorithm analogous to TRPO (A-TRPO). The paper additionally shows how their main theorem can be applied to constrained MDPs in Section  5.2. Empirical results are provided in three MuJoCo domains modified to provide non-episodic experience.      \n\nI found many strengths in the paper. For one, it was enjoyable to read and fairly well organized. The authors presented their ideas clearly, and they appeared logically-connected throughout the paper.\n\nThe paper is also well motivated. Continual reinforcement is a broad area of open research where new advancements stand to improve the generality of our current AI/ML systems. In that setting, the average reward objective for MDPs seems most natural. But despite the existence of average-reward RL algorithms, many of them are not well theoretically well understood (e.g. R Learning). And as the authors bring up, it is not known if more current theoretical results about policy optimization apply to the average-reward setting. \n\nThere are few minor issues I have with the presentation, and some questions I have regarding the experimental results. Pending a satisfactory response to these issues, which I describe below, this paper could be ready for publication.\n\nAlthough the results of Section 5.2 seem useful for those interested in constrained decision making processes, they also seem fairly anecdotal in relation to the paper’s main claims and for what the main paper presents. The claims supported with substantial empirical evidence only use A-TRPO.  The A-CPO results have been tucked away in the appendix.  I suggest the authors remove this material, since the A-TRPO results are sufficient to support your main claims, and considering the constrained MDP setting in addition to average reward and discounted is too much for the length of a conference paper\n\nSection 7 presents empirical data showing the performance of the proposed algorithm (A-TRPO) and compares it to TRPO with different discount factors. The presented results seem positive: suggesting that A-TRPO finds useful policies within the considered data regime. However, this section is terse, and so I have a few questions for the authors:\n\nI’m not yet convinced the evaluation is entirely sound. The performance of an average reward agent is compared to discounted agents using their respective returns averaged over the last 1000 steps of their 100 most recent trajectories. I take issue with this approach for several reasons:\n\n1. It is not clear that it has a meaningful connection to the average-reward criterion. Why not use the average reward, which is what the paper advocates for as the natural metric in continual settings?\n2. Restricting the evaluation to the last 1000 steps, or trajectories of length 1000, (authors please specify) biases the outcome against discounted agents whose effective horizon is 1000 or greater. These agents are trained to maximize cumulative reward on horizons greater than or equal to 1000, but then they are evaluated on horizons less than that.\n3. In a continual setting, there is no separate evaluation phase; learning continues indefinitely. Therefore, it seems more appropriate to report the reward averaged over a horizon where sufficient mixing has occurred, rather than report offline evaluation performance.\n\nIt is not immediately clear to me that the modifications to MuJoCo result in a well posed continual learning problem. Can the authors please clarify if the maximum episode length cap was removed for training?  Can they also clarify exactly how the start states were sampled? Are there any aspects that change or remain the same between falling down and restarting? A complete characterization of the factors of variation would be helpful here.\n\nI do not have a good sense for what data is being plotted in Figures 1 and 2. The data seems to vary between the plot markers. So my question is: what do the plot markers represent? Has this data been smoothed at all? If so, then can you please provide more details so we can understand how the data was processed.\n\nThe paper does a good job of positioning its contribution with respect to prior work throughout the text. Though it wouldn’t hurt to expand the Related Work section so it reads less like a list of facts. The goal would be to help readers understand the contribution by comparing and contrasting it with what others have done.\n\nIt would be helpful to include a video showing the execution of the policy as it is being learned. This would allow reviewers to verify if the learned average-reward polices are actually useful, and they do not simply achieve better evaluation metrics than the presented baselines. \n\nThe questions identified in the beginning of Section 7 could be more specific. For example: “Which performance criterion is more suitable for continuing control tasks?”. This question strikes me as something that has been answered in the affirmative throughout the long history of average-reward and infinite horizon discounted MDPs. This is also mentioned in two references you provide (Sutton & Barto, and Naik et al. 2019). Could you be more specific about what you are trying to address here, how this is different than what others have shown, and about how Question 2 is different from Question 3.\n\nMany of the theoretical results cite a set of class notes (Achiam 2017). I suggest the authors remove this citation and reproduce the results needed for their arguments in the appendix. This provides a way for those to be peer reviewed and for future work to reliably cite them.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QNBgOGqeQRx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper identifies an important problem: policy optimization in undiscounted continuing tasks. This is indeed important since the discounting factor may not be appropriate in certain applications such as health care or robotics. I feel the main contribution of this paper is Theorem 1, an average reward version of the monotone improvement theorem. Naively applying the discounted version results in a trivial bound.\n\nMy concern is about the algorithm (13) that is almost the same as TRPO, with a bit straightforward extension on the estimation for the advantage function. In the constrained form, the KL radius is viewed as a tuning parameter but in the regulaized version (12), the \\xi involves a complicated form involving true P to guarantee the monotone improvement. This does not make very much senses to do this approximation. Note that in TRPO, there is no true P involved. \n\nA large body of policy optimization works that focus on average-reward is perhaps missing. 1. Online Markov Decision Processes. (2009). 2. Online markov decision processes under bandit feedback (2010). Those two assumes the P is known but the average reward performance difference lemma has been explicitly derived in those two. More recently, \"POLITEX: Regret Bounds for Policy Iteration Using Expert Prediction\" considered a fully RL setting and average-reward setting with guarantee. \n\n====================\nThanks the authors' response. Based on the originality of Theorem 1, I increase my score by 1 but still a bit worry about the sufficient algorithmic contribution beyond TRPO. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CqjY64E8pIL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a practically feasible algorithm for the average reward setting in RL. The key idea is to propose a lower bound policy improvement objective, for the average reward setting compared to the more popular and general discounted reward setting. This work follows directly from previous impactful works on policy gradients with trust region optimization (TRPO) and shows why previous approaches cannot be directly applied for the average reward criterion. This is a significant contribution in RL research, for the average reward performance criterion, and opens doors for future works in this direction that might be impactful to the community. Overall this is a good paper. There are few major and minor concerns I have about the contribution, mostly from an algorithmic point of view, which are described in details below. \n\nOverall comments : \n- This work provides monotonic performance improvement guarantees, by deriving a lower bound policy improvement criterion for the average reward setting. It is well known, even though less significantly realized that the existing policy improvement theorem for the discounted reward setting leads to a trivial bound for the average performance criterion. This work builds from that and derives a novel result which can bound the average reward performance objectives based on the divergence between two policies, as mostly done in a lot of policy optimization algorithms (e.g TRPO and many variants building from TRPO). \n- Additionally, the authors propose a constrained optimization variant of their algorithm, building from the CPO algorithm (Achiam et al) and shows that the average reward criterion can also be used for policy optimization under cost constraints. \n- The paper is well written and easy to follow, with the key theoretical contributions clearly defined. It builds from the well known proposition from Achiam et al., for the upper and lower bounds for the performance difference lemma (Proposition 1). Lemmas 1-3 are known results, adapted for the average reward setting, including the performance difference lemma for the average reward objective. \n- The key result is shown in theorem 1, which bounds the performance difference based on the average reward criterion, but reduces to the divergence between policies only. Equations 9 and 10 are extensions from Achiam et al., adapted for this setting, with the typical assumption that the changes in occupancy measures between $\\pi'$ and $\\pi$ are insignificant. This is a standard assumption, assuming minimal state distribution shift between the two policies, as typically done in TRPO, CPO and variants. \n- Experimentally this work nicely demonstrates the significance of the average reward criterion in continuous control tasks, which are adapted for a continuing setting, instead of the typical episodic setting with reset states. Under this modification, the authors compare to TRPO and CPO with different discount factors in the continuing environment, and shows the significance of optimizing the average reward lower bound objective. The authors do not compare to other well known policy gradient baselines, which I believe is fine in this case; since the key contribution is to propose an algorithm applicable for continuing environments - and modifications on top of their ATRPO algorithm can be made, as required, to compare to other well known existing baselines. Even though the experimental results are less exhaustive, I think this is not too of a problem, compared to the significant algorithmic contribution this paper introduces. \n\nFew issues and comments for improvement : \nI think the major drawback or clarity this paper requires is to describe their algorithmic steps more clearly. At first glance, there are few issues which seems unavoidable, and it would be better if the authors can clarify on these. These are as follows : \n- Lemma 3 bounds the divergence between stationary distributions in terms of the divergence between policies. This result is adapted, as shown in appendix, following from Achiam et al., and is known from other papers that such divergence between stationary distributions can be bounded. Lemma 3, equation 8 shows that this bound depends on the l-infinity norm between the transitions under the policies. Proof of Lemma 3 is easy to follow. My major concern is how is this term in equation 8 dealt with in the overall algorithm?\n- Theorem 1 following from the stated lemmas, depends on this, as highlighted in the $\\epsilon$ term and in Algorithm 1 (equation 12). It seems that the assumption that the stationary distributions between \\pi' and \\pi are close in this case is less justified in the average reward setting compared to the discounted setting. Can the authors comment on this? In the discounted setting, the normalized occupancy measures between two policies can perhaps be assumed to remain close, as done in TRPO. However, does the same hold for stationary distributions? If so, why would that be? I think this is a major assumption. \n- I do see why in the overall algorithm, this assumption is made; since otherwise finding the sensitivity of stationary distributions w.r.t changes in policy parameters might be difficult to compute; but theoretically, it would be better if authors can comment on it. \n- Section 5.1 outlines the key algorithm and steps. Equation 13 shows the overall objective with KL constraints, which at first glance, is almost equivalent to the discounted reward setting. However, as pointed out later, the advantage function takes account of the average reward, and the overall algorithm can be naturally extended from TRPO and CPO. However, I think it would be better if the authors comment on the above issues, and how is the overall algorithm implemented. In appendix C, there are discussions on the critic estimate, if this was to be extended in an actor-critic setup with lambda returns - however, appendix C does not really give anything meaningful as expected. It seems that the overall difference is in equation 33, where the target is now modified with the average reward. This makes the algorithmic contribution clean, but I wonder how is this implemented in practice. The target now requires computation of the average reward, for every s,a pairs? This seems to be a bottleneck, and comes to the major drawback for the average performance criterion anyway? How is this avoidable?\n- Overall, I think the algorithmic implementation of this is not clearly explained. It seems there are major steps ommited in the overall description of the algorithm - and this is partly also because the authors propose ATRPO and ACPO algorithms, which are two different contributions itself. I think it would be better if the key algorithmic idea and implementation details are rather included in the main text, so that the significance of the work can be better highlighted; and perhaps the extensions with cost constraints can be moved to the appendix.\n\nSummary : I think overall this is a good paper, with some clarities that are still required from the authors. This is a good contribution, extending existing impactful works from the discounted reward setting to the average reward setting. The authors propose theoretical justifications as well as a practically feasible algorithm. If the authors can clarify some of the major concerns I have, given my understanding is correct, I am willing to further increase the score. However, as it is, I would recommend marginal acceptance, and open to discussions with other reviewers and authors to clearly understand the significance of the work. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "2-PBaDQdRNt", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "***Summary***\nThe paper proposes an extension of the performance improvement bound, introduced for the first time by Kakade & Langford (2002), to the case of average reward performance index instead of discounted return. The paper starts with a theoretical contribution in which all the steps of the original derivation are adapted for the new setting, leading to a new performance improvement bound. Then, this theoretical achievement is employed to derive the corresponding adaptation of TRPO (called Average Reward TRPO) and CPO (called Average Cost CPO). Finally, an experimental evaluation on some Mujoco domains is provided.\n\n***Major***\n- (About the fundamental matrix) The main difference between the performance improvement bound for the discounted return and the one presented in this paper is the constant that multiplies the expected total-variation divergence between the policies. While for the discounted case, this constant is a function of the discount factor and of the maximum advantage, in the average reward case it depends on the maximum advantage as well and on the norm of the fundamental matrix of the Markov chain. The authors clarify that this matrix is guaranteed to exist for regular chains. However, the value of its norm, although finite, can be very large. From a practical perspective, this has limited implications as the objective that is actually optimized translates the penalization into a constraint, ignoring this constant. Nevertheless, it would be interesting if the authors could elaborate more on the properties of this matrix, maybe providing some bounds of its norm, if possible, in terms of more manageable quantities.\n- (Organization) I have some concerns about Section 5.2. First, the change of perspective from rewards to costs might not favor the clarity of the paper. Second, concerning Average Cost CPO, no experiments are reported in the main paper but in the appendix only. Moving also Section 5.2 to the appendix and reserve more space for the proofs of the theoretical results in the main paper might improve the organization.\n- (Experiments) I have some concerns about the interpretation of the experimental results, especially on how ATRPO is compared to TRPO. The two algorithms are designed to optimize different objective functions: the average reward and the discounted return, respectively. The plots that are shown in Figures 1 and 2 report the \"Return\", which I assume to be the undiscounted sum of the rewards over 1000 and 10000 steps respectively. I am wondering whether drawing conclusions based on this performance index is meaningful. Indeed, optimizing the undiscounted sum of the rewards is closer to optimizing the average reward rather than the discounted return and I am not surprised that ATRPO outperforms TRPO. Can the authors elaborate on this point and explain why they think that the comparison is fair?\n\n***Minor***\n- In Section 2, the paper requires that the state and action spaces are finite. Is this assumption really necessary to derive the presented results? In the experimental evaluation section, the algorithms are tested on the Mujoco suite that is made of continuous state-action environments.\n- Equations (9), (10), (12) sometimes the state below the expectation is bold.\n\n***Overall***\nI think that the paper can be considered incremental compared to TRPO and, more in general, to the papers that study the performance improvement bounds in the discounted setting.  Moreover, I have some concerns about the interpretation of the experimental results. Therefore, my current evaluation is borderline.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an extension of the monotonic policy improvement approach to the average reward case.
Although the reviewers acknowledge that this work has merits (well written, clearly organized, well-motivated, technically sound) the reviewers have raised several concerns, which have been only partially addressed by the authors' responses. In particular, Reviewer4 is still concerned about the discrepancy between the theorem and the implemented algorithm, and the proposed simplification used in the implementation boils down to an algorithm that is very similar to TRPO, thus making the contribution quite incremental as also stressed by Reviewer1. Furthermore, I share the concerns raised about the fairness of comparing algorithms that optimize different objective functions.
I suggest the authors take into serious consideration the suggestions provided by the reviewers in order to produce an improved version of their work.
The paper is borderline and I think that it needs another round of fresh reviews before being ready for publication. 
Decision: Reject