Off Policy Average Reward Actor Critic with Deterministic Policy Search
Authors: Naman Saxena
Subhojyoti Khastagir
Shishir N Y
Shalabh Bhatnagar
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
actor critic algorithm
deterministic policy
off-policy
target network
average reward
finite time analysis
convergence
three time scale stochastic approximation
DeepMind control suite

Abstract: The average reward criterion is relatively less explored as most existing works in the Reinforcement Learning literature consider the discounted reward criterion. There are few recent works that present on-policy average reward actor-critic algorithms, but average reward off-policy actor-critic is relatively less explored. In this paper, we present both on-policy and off-policy deterministic policy gradient theorems for the average reward performance criterion. Using these theorems, we also present an Average Reward Off-Policy Deep Deterministic Policy Gradient (ARO-DDPG) Algorithm. We show a finite time analysis of the resulting three-timescale stochastic approximation scheme and obtain an $\epsilon$-optimal stationary policy with a sample complexity of $\Omega(\epsilon^{-2.5})$. We compare the average reward performance of our proposed algorithm and observe better empirical performance compared to state-of-the-art on-policy average reward actor-critic algorithms over MuJoCo based environments. 

Under review as a conference paper at ICLR 2023
OFF-POLICY AVERAGE REWARD ACTOR-CRITIC WITH DETERMINISTIC POLICY SEARCH
Anonymous authors Paper under double-bling review
ABSTRACT
The average reward criterion is relatively less explored most existing works in the Reinforcement Learning literature consider the discounted reward criterion. There are few recent works that present on-policy average reward actor-critic algorithms, but average reward off-policy actor-critic is relatively less explored. In this paper, we present both on-policy and off-policy deterministic policy gradient theorems for the average reward performance criterion. Using these theorems, we also present an Average Reward Off-Policy Deep Deterministic Policy Gradient (ARÓ-DDPG) Algorithm. We show finite time analysis of the resulting three- timescale stochastic approximation scheme with linear function approximator and obtain e-optimal stationary policy with sample complexity of 9 -255). We compare the average reward performance of our proposed algorithm and observe better empirical performance compared to mate-of-the of-th-rr-tr art on-policy average reward actor-critic algorithms over MuJoCo based environments.
INTRODUCTION
The reinforcement learning (RL) paradigm has shown significant promise for finding solutions to decision making problems that rely on a reward-based feedback from the environment. Here one mostly concerned with the long-term reward acquired by the algorithm. the case of infinite horizon problems, the discounted reward criterion has largely been studied because of its simplicity. Major recent development in the context of RL in continuous state-action spaces has considered the discounted reward criterion (Schulman et al. 2015 2017 Lillicrp et al. 2016 Haarnoja et al.) (2018) 8). However, there are very few works which focus on the average reward performance criterion in the continuous state-action setting (Zhang & Ross 202 Ma et al. 2021).
The average reward criterion has started receiving attention recent times and there are papers that discuss the benefits of using this criterion over the discounted reward (Dewanto & Gallagher 2021 Naik et al. 2019). One of the reasons being, average reward criteria only considers recurrent states and it happens to be the most selective optimization criterion in recurrent Markov Decision Processes (MDPs) according to n-discount optimality criterion. Please refer Mahadevan (1996) for more details on n-discount optimality criterion. Further, optimization in average reward setting is not dependent on the initial state distribution. Moreover, the discrepancy between the objective function and the
evaluation metric, that exists for discounted reward setting, is resolved by opting for the average reward criterion. We encourage the readers to go through Dewanto Dewanto & Gallagher (202 Naik et al. (2019) for better understanding of the benefits mentioned.
There are very few algorithms in literature that optimize the average reward and all of them happen be on on-policy algorithms (Zhang Ross [021]] Ma et 202T). has been demonstrated several times that on-policy algorithms are less sample efficient than off-policy algorithms Lillicrap et al. (2016); Haarnoja et al. (2018); Fujimoto et al.) (20T8) for the discounted reward criterion. In this paper try to find whether the same is true for the average reward criterion. We try to overcome the research gap in development of off-policy average reward algorithms for continuous state and action spaces by proposing Average Reward Off-Policy Deep Deterministic Policy Gradient (ARO-DDPG) Algorithm.
The policy evaluation step in the case of the average reward algorithm is equivalent to finding the solution to the Poisson equation (i.e., the Bellman equation for a given policy). Poisson equation, because of its form, does not admit unique solution but only solutions that are unique up to constant

---

Under review as a conference paper at ICLR 2023
term. Further, the policy evaluation step in this case consists of finding not just the Differential Q-value function but also the average reward. Thus, because of the required estimation of two quantities instead of one, the role of the optimization algorithm and the target network increases here. Therefore we implement the proposed ARO-DDPG algorithm by using target network and by carefully selecting the optimization algorithm.
The following are the broad contributions of our paper:
We provide both on-policy and off off-policy deterministic policy gradient theorems for the average reward performance metric.
We present our Average Reward Off-Policy Deep Deterministic Policy Gradient (ARO- DDPG) algorithm.
We perform non-asymplotic convergence analysis and provide a finite time analysis of our three timescale stochastic approximation based actor-critic algorithm using a linear function approximator.
We show the results of implementations using our algorithm with other state-of ofett---tte algorithms in the literature.
The rest of the paper is structured follows: In Section MDP framework, the basic setting as well as the policy gradient algorithm. Section presents the deterministic policy gradient theorem and algorithm. Section Satiionn]thee 4henn presents the main theoretical results related to the finite time analysis. Section 5 presents the experimental results. In Section 6 we discuss other related work and Section ( presents the conclusions. The detailed proofs for the finite time analysis are available in the Appendix.
present the preliminaries the
2 PRELIMINARIES
Consider a Markov Decision Process (MDP) M = AS, where S C IR" is the (continuous) state space, A 1 is the (continuous) action space, R: x A + denotes the reward function with R(s, a) being the reward obtained under state and action a. Further, P(-Is, a) denotes the
state transition function defined as S x + pu.), where μ : B(S) + [0, 1] probability measure. Deterministic policy æ is defined as x + A.In the above, B(S) represents the Borel sigma algebra on S. Stochastic policy n, is defined as n, + p²(.), where μ ((A) + [0, 1] and ((A) is the Borel sigma algebra A.
Assumption 1. The Markov process obtained under any policy π is ergodic.
Assumption necessary to ensure existence of steady state distribution of Markov process.
2.1 DISCOUNTED REWARD MDPS
In discounted reward MDPs, discounting is controlled by y E (0, 1). The following performance metric optimized with respect to the policy:
"RR(s / (s)
ET
(1)
Here, Po is the initial state distribution and V is the value function. Vs(s) denotes the long term reward acquired when starting in the state s.
VTT(s)) E [R((Rs,, a.) +
2.2 AVERAGE REWARD MDPs
The performance metric in the case of average reward MDPs is the long-run average reward p(x) defined as follows:
p(T) lim
R(st, ax)l = (s)
(3)
N +000
t=0
2

---

Under review as a conference paper at ICLR 2023
where Rº (s) - R(s, T (s)). The limit in the first equality in equation exists because of Assumption I The quantity d= (s) in the second equality in equation corresponds the steady state probability
of the Markov process being in state E S and it exists and is unique given и from Assumption as well.
Väyy is the differential value function corresponding to the policy and is defined in (4) Further, the differential Q-value or action-value function Qdiff is defined in
Väs (()) = ET
R(sk, ax) p(T))ss,)
(4)
k=
( ET
R(sk. az) p(T))
(5)
k
Lemma There exists a unique constant k(= p())) which satisfies the following equation for differential value function Vais
((t) = (R( k + (ārr((8422158)
(6)
Proof. See appendix for the proof.
2.3 POLICY GRADIENT THEOREM
Unlike in Q-learning where we try to find the optimal Q-value function and then infer the policy from it, the policy gradient theorem (Sutton et al., 1999 Silver et al.) [2014] Degris et al. (012) allows us directly optimize the performance metric via its gradient with respect the policy parameters. Q-learning can be visualized to be value iteration scheme while an algorithm based on the policy gradient theorem can be seen as mimicking policy iteration. [Sutton al. (1999) provided the policy gradient theorem for on-policy optimization of both the discounted reward and the average reward algorithms, see respectively.
[ wn(( / Von, (als, (s, da
Von(m)
Vop(T) / d' (s) / (alss da ds.
(8)
In " denotes the long term discounted state visitation probability density which is defined equation 9 while (s) lim, P (s) is the steady state probability density on states. p denotes the transition probability kernel for the Markov chain induced by policy æ and P. is the state distribution at instant given by (10).
wn (1 (1-7)
Σn PP)
(9)
(=0
t-1
(s) = Sxs...
(o()))
II k=
pa (St+1l$6) dag. ds:-1-
(10)
The policy gradient theorem in Sutton et al. (1999) is only valid for on-policy algorithms. Degris al. 2012) proposed an approximate off-policy policy gradient theorem for stochastic policies, where dl stands for the steady state density function corresponding to the policy μ..
Von(T) [ dd)(s) (als(a)s a) da ds.
(11)
Silver et al.
2014) came up with the deterministic policy gradient theorem, 12 which eventually led to the development of very successful Deep Deterministic Policy Gradient (DDPG) (Lillicrap
al. 2016) algorithm and Twin Delayed DDPG (TD3) algorithm (Fujimoto et al. 2018
Von(T) = / w (s) (s, (s,,a)lan(s) (o)
(12)

---

Under review as a conference paper at ICLR 2023
3 PROPOSED AVERAGE REWARD ALGORITHM
We now propose the deterministic policy gradient theorem for the average reward criterion. The policy gradient estimator has to derived separately for both the on-policy and off-policy settings. Obtaining the on-policy deterministic policy gradient estimator is straight forward but dealing with the off- policy gradient estimates involves an approximate gradient (Degris et al. 2012).
3.1 ON-POLICY POLICY GRADIENT THEOREM
We cannot directly use the second equality of (3) derive the policy gradient theorem because of the inability to take the derivative of steady state density function. Therefore one needs to use (6) to obtain the average reward deterministic policy gradient theorem.
Theorem 1. The gradient of p(TT) with respect policy parameter is given as follows:
Vop(T) d (s) (55 (oT(s, ds.
(13)
Proof. See appendix for the proof.
3.2 COMPATIBLE FUNCTION APPROXIMATION
The result in this section is mostly inspired from Silver et al. (2014). Recall that Q a) is the 'true' differential Q-value of the state-action tuple (8, under the parameterized policy Now let ( a) denote the approximate differential Q-value of the (s, a)-tuple when function approximation with parameter used. Lemma says that when the function approximator satisfies
a compatibility condition (cf. (14 ), then the gradient expression [3] also satisfied by Qäs in place of Quiss.
Lemma 2. Assume that the differential Q-value function satisfies the following:
1.V V V Vurrr = (s,(s,0).
(14)
Differential Q-value function parameter w = w optimizes the following error function:
1 / d= S(0, w) 2
-ar VaQiis (ssss)))eeeee ()) ds.
(15)
Then,
I ( (am==))))) (s ds d= (s) (or(s, ds. (16)
Further, the case when linear function approximator used, we obtain
VaQāys(s,a) a) (s
(17)
Proof. See the appendix for a proof.
An important implication of lemma 2 also is that the dimension the matrix on the left hand side and the right hand side of (14) should be the same. Hence the dimensions of the parameters 0 (used in the parameterized policy) and w (used to approximate the differential Q-value function) are the same. Lemma (anmma]shows shows that the compatible function approximation theorem has the same form in the average reward setting as the discounted reward setting.
3.3 OFF-POLICY POLICY GRADIENT THEOREM
In order to derive off- polico policy gradient theorem it not possible to use the direction adopted by Degris al. (2012) for off off-policy stochastic policy gradient theorem for the discounted reward setting. We first mention our proposed approximate off- off-policy deterministic policy gradient theorem and then explain why some alternatives would not have worked.
4

---

Under review as a conference paper at ICLR 2023
Assumption 2. For the Markov chain obtained from the policy let (().)) be the transition kernel and 5 the steady state measure. Then there exists a > 0 and E (0,1) such that
(11ss, Σ an Vs E.
Assumption states that Markov chain generated by a policy я follows uniform ergodicity property. This assumption is necessary to get an upper bound the total variation norm of steady state probability distribution of two policies. This assumption used in Lemma [2] which turn is used for Theorem 2
Theorem 2. The approximate gradient of the average reward p(T)) with respect the policy parameter is given by the following expression:
Vep(T)= 1 ad a)la=>)) (o
(18)
Further, the approximation error is E n)) = [[oo((T) - where μ represents the behaviour policy. & satisfies
E(T, 1)) S - 1
(19)
Here, Z = 2 C(Log a + L, with Le being the Lipchitz constant for the transition probability density function (Assumption 9. Constants a and k. are from Assumption 2 m is the
dimension of action space, and C max, VaQ (5, VoT(s, 0)l
Proof. See the appendix for a proof.
Theorem 2 suggests that the approximation error in the gradient increases as the difference between the target policy æ and the behaviour policy f increases.
3.4 OFF-POLICY ALTERNATIVES
In this section we will talk about what alternatives could be thought of in place of what is suggested in section 3.3 and why those alternatives would not work.
One can possibly take inspiration from Degris al. (2012) and define an objective function, p(T)), as in (20). which is a naive off off-policy version of
Preceu (TT) ds)
(20)
If, however, we take the derivative of (new defined above, we get the policy update rule as in (1).
V Opnnew (T) = (s) (0 (8,
(21)
The update rule (T only considers the reward function and not the transition dynamics of the MDP. (18,, the derivative of the objective function includes the differential Q Q-value function which encapsulates both the information of the reward function and the transition dynamics of the MDP and hence is valid derivative.
2. A lot of work the off-policy setting relies on importance sampling ratios. Recently a few works devised method to estimate the steady state probability density ratio of the target and behavior policies (Zhang et al.) 2020aa b) Liu et al., 2018 Nachum et al. 2201)) The ratio of steady state densities could be used for deterministie policy optimization but there are certain issues which prohibit its usage, see
Vep(T) / d
a)la= (8,
(22)
Here, T(s) is the steady state probability density ratio defined as d (s) (s). In order to calculate 7s8) need information about (I(a)s), p(als) and P(s' a)). We need the ratio
5

---

Under review as a conference paper at ICLR 2023
a(als)/u(a(s) and for deterministic policies the ratio would be 6(a rT(s//((a mu(s)) where 6(.) is the Dirac-Deles function:
if a = (u(s)
8(a - x())
8(a (s)))
00
if = i(s)
(23)
otherwise.
From 23 it clear that the ratio 8(a π ()/( - uus)) will be undefined for almost all actions a A. Thus, we cannot use this ratio for deterministic policies. Otherwise, we need P(s'|s, x (a)) and P(s'|s, u(a)). It is possible sampling from the Markov process generated by the policy but obtaining this information about P(s'|s, (a)) is impossible in the off- aff-policy setting data from is assumed to be simply unavailable.
get the information about P(s'ls, uıa)) by
3.5 ACTOR-CRITIE UPDATE RULE
Assumption an Be, and Itt are the step sizes for critic, target estimator, and actor parameter updates respectively.
Ca
C3 (1+ t)u
C
04
(1 11+1
t)o
3r
Tt (1+t)*
Here, Ca, C.,C,.C. Cr > and 0 o
< u
< v
1. 0g at the fastest timescale, 3, is at slower
timescale and "tt is at the slowest timescale.
The critic and average reward parameters are estimated using the TD(O) update rule but use target estimators. We using target estimators ensure stability of the iterates of the algorithm. Let {s; 04, $11=0 denote the batch of sampled data from the replay buffer.
C/ = Σ
R(s; (4) - Pr - Quigy ad) + min(Q (5 j E (1,2)
(24)
<7
R(s;;a)) Pt min(Qui ( min(Q ( (54, 0t))
2
(25)
Equation 24 and 25 are the bellman error for differential Q-value function approximator and average reward estimator respectively. Note here we are using double Q-value function approximator.
wit1 w V
E.Et Et
i (1,2)
(26)
Pe+1 = Pt
02
V
(27)
The bellman errors 24 used update Q-value function approximator parameters wi using 26 and the bellman average in 25 is used to update average reward estimator Pt using
24 (aminnQQii Qai (st, a))a=x(ss) VoT(s;, 0.)
(28)
O2+1 = 0, +
Σ
(29)
Actor update is performed using theorem Actor parameter, 0,, updated using empirical estimate 28 of the gradient in [8
w +1 w + B:(w wi) i i (1,2)
(30)
P++1 = Pt + 3,(pt+1 - pt)
(31)
O.11 = 0, + 3,(0+11 - -0)
(32)
used to update the target Q-value function approximator wi. target average reward estimator P: and target actor parameter 0,,
Equation 30 30-22 32

---

Under review as a conference paper at ICLR 2023
4 FINITE TIME ANALYSIS
In this section we present the finite time analysis of the on-policy and off-policy average reward actor critic algorithm with linear function approximators, First we mention the assumptions taken to perform the finite time analysis followed by the main results.
Assumption
x (s) o(s, π (s)) denotes the feature vector of state and satisfies [|0 S 1.
The assumption above is just taken for the sake of convenience.
Assumption 5. The reward function is uniformly bounded, viz., R² C. <0.
Assumption is required to make sure that the average reward objective function is bounded from above.
Assumption 6. (8, is Lipchitz continuous w.r. to a. Thus, Yw [[
(2) s Lalla1 a2ll-
Continuity of approximate Q-value function w.r.t action is enforced using Assumption 6 Without the continuity property approximate differential Q-values will not generalize for unseen action values.
Assumption Parameterised policy т (8, 0) Lipchitz continuous w.r. 0. Thus, (1=(0,01) S (s)022)
1= 02ll-
Assumption 7 is a common regularity assumption for convergence of actor. It can be found in Wu al. (2020), Xiong al. (2022) and Zou al. (2019).
Assumption 8. The state feature mapping (Ø (s) o(s, m())) defined for policy with parameter 9 is Lipschitz continuous w.r. 0. Thus, max, | (s) - x² S Loll0 02ll.
Continuity of state action feature w.r.t action required to ensure generalisation of Q-values to unseen action values. Using this continuity of state action feature with Assumption 7 we can satisfy Assumption
4.1 ON -OLLCCY ANALYSIS
In this section present the theorem for finite time analysis of the on-policy version of the algorithm with linear function approximator and target estimator for the critic and average reward.
Theorem The on on-policy average reward actor critic algorithm (Algorithm 2 obtains an e-accurate
optimal point with sample complexity of Die 2.5). We obtain
Ell o
1
min
E
+ O(L),
70.4
$ O(1.
Proof. See the appendix for a proof.
We want to reach as close as possible value of f such that [|Vop(0)]l 0, which indicates we have found a local maxima. O(1) term is present in the bound because of using linear function approximation and will not reduce as time increases. However, if the O term is small enough, the bound in Theorem 3 shows that as T increases, the algorithm will get close to the local maxima of the objective function 3. A similar (1)) term is present in (Xiong et al. 2022 Xiong et al. claims the term will be small upon using neural network for critic.
4.2 OFF-POLICY ANALYSIS
In this section we present the theorem for finite time analysis of off-policy version of the algorithm with linear function approximator and target estimator for the critic and average reward.
The off off-policy average reward actor critic algorithu (Algorithm 3 with behavior policy obtains an e-accurate optimal point with sample complexity of (0(c-22.5 2.5). Here 9,, refers to the behavior policy parameter and 0, refers to the target current policy parameter. We obtain
Theorem 4.
7

---

Under review as a conference paper at ICLR 2023
min USIST-1 P( 0 70.4
+ 0(1) O(W3)
s (() + O(W3)
where We == max 100 0cll
Proof. See the appendix for a proof.
The significance of finding a bound on Vop(Oe)l is same explained above for Theorem 3. The error bound in the off- policy algorithm has an extra term O(W3). The extra term denotes the error induced because of not using the samples from the current policy for performing updates. W3 will be small when replay buffer used because replay buffer contains data from policies similar to current policy. This explains why Theorem 2 can be used with replay buffer.
5 EXPERIMENTAL RESULTS
We conducted experiments on six different environments using the DeepMind control suite (Tassa jet al., 2018) and found the performance of ARO-DDPG be superior than the other algorithms. the environments selected are infinite horizon tasks. Maximum reward per time step is 1.None of the tasks have goal reaching nature. We performed all the experiments using different seeds. We show here performance comparisons with two state-of-the the-thh-rrt algorithms: the Average Reward TRPO (ATRPO) (Zhang & Ross 202T) and the Average Policy Optimization (APO) (Ma et al. 2021) respectively. In general for the average reward performance, the literature. We implemented the ATRPO algorithm using the instructions available in the original paper. We used the original hyper-parameters suggested by the author for ATRPO.
many algorithms available in
Cheetah-
Finger-Spin
Cartpole-
ARD DOPG
ARO-DDPG
APO
ATRPO
Average Reward
3.-
ATMPO
ATRPO
APO
04
0.0
03
Fish-Upright
Humanoid-Walk
Walker-Walk
ARO-DOPG DDPG
ATRPO
144
NRO-ODRG
33
AM
ATR
APO
13
APO
ATRPO
8.1
02
04
Environment Steps (in millions)
Figure 1: Comparison of performance of different average reward algorithms
For our proposed algorithm we trained the agent for million time steps and evaluated the agent after every 5,000 time steps in the concerned environment. The length of each episode for the training phase was taken to be 1,000 and for the evaluation phase was taken to be 10,000. The reason compare the long term average reward
for taking longer episode length for evaluation phase performance of the algorithms. We also tried using episode length of 10,000 for training phase and found that to be giving poor average reward performance. We do not reset the agent if it lands in
8

---

Under review as a conference paper at ICLR 2023
state before completing 10,000 steps from where it is unable to escape of its own, while continuing to give a penalty for the remaining length of the episode. That way the cost of failure is very high. updated the actor after performing fixed number of environment steps. We
While training updated the critic neural network with more frequency as compared to the actor neural network. We used target actor and critic networks along with target estimator of the average reward parameter for stability while using bootstrapping updates. We updated the target network using polyak averaging. We tried to enforce multiple timescales in our algorithm by using different update frequency for actor, critic and polyak averaging for target networks. We also borrowed the double Q-network trick from Fujimoto et al. (2018). Complete information regarding the set of hyper-panee param-prrseeters used is provided in the appendix.
6 RELATED WORK
Actor-Crite algorithms for average reward performance criterion is much less studied compared to discounted reward performance criterion. One of the earliest works on the average reward criterion is Mahadevan (T996). In this paper, Mahadevan compares the performance of R-learning with that of Q-lcarming and concludes that fine tuning is required to get better results from R-Icarning. R-learning the average reward version of Q-learning. Later in 1999] Sutton et al. derived the policy gradient theorem for both discounted and average reward criteria (Sutton et al. 1999), which formed the bedrock for development of the average reward actor-critic algorithms. The first proof of asymptotic convergence of average reward actor-critic algorithms with function approximation appeared in Konda & Tsitsiklis (2003). In 2007 Bhatnagar et al.) proposed incremental natural policy gradient algorithms for the average reward setting and provided the asymptotic convergence proof of these.
Recently, Wan et al.] presented a Differential Q-learning algorithm and claimed that their algorithm able to find the exact differential value function without an offset. Further, Wan et al. provided an extension of the options framework from the discounted setting to the average reward setting and demonstrated the performance of the algorithm in the Four-Room domain task. One of the major contributions in off-policy policy evaluation is made by Zyaang et al. (2021a). Here /Zhang et al., gave convergent off-policy evaluation scheme inspired from the gradient temporal difference learning algorithms but involving a primal-dual formulation making the policy evaluation step feasible for neural network implementation. Zhhnn et al. (2021b) provided another convergent off-policy evaluation algorithm using target network and l2 lerrgulaariaatonn In our work we use the same policy evaluation update.
Our work in this paper is actually an extension of the work of Silver et al. 2014) from the discounted to the average reward setting. In Xiong et al.) (2022), a finite time analysis for deterministic policy gradient algorithm was done for the discounted reward setting. We performed the finite time analysis for the average reward deterministic policy gradient algorithm and particular obtain the same sample complexity for our algorithm as reported by Wu et al. (2020) for stochastic policies.
7 CONCLUSION AND FUTURE WORK
In this paper we presented deterministic policy gradient theorem for both on-policy and off-policy settings. We then proposed the Average Reward Off-policy Deep Deterministic Policy Gradient(ARRC DDPG) algorithm using neural network and replay buffer for high dimensional MuJoCo based environments. We observed superior performance of ARO-DDPG over existing average reward algorithms (ATRPO and PPO). At the end we provided a finite time analysis for the on-policy and off-policy algorithms obtained from the proposed policy gradient theorem and obtained sample complexity of 22(e (225). Lastly to extend the current line of work, one could try using natural gradient descent based update rule for deterministic policy. Further in the current work we tried optimizing the average reward performance (gain optimality). In the literature, optimizing the differential value function for all the states is mentioned as part of achieving Blackwell optimality. Hence actor-critic algorithms could be designed that not only optimize average reward performance but also differential value function (bias optimality).

---

Under review as a conference paper at ICLR 2023
REFERENCES
Dimitri Bertsekas. Convergence of discretization procedures in dynamic programming. IEEE Transactions on Automatic Control, 20(3)415-419, 1975.
Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton. Incremental natural actor-critic algorithms. Advances in neural information processing systems, 20, 2007.
V. S. Borkar and S. P. Meyn. The o.d.e. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimizaation 38())4447-469 2000. doi: 10.1 10.11377/0363301199333666
URL /tt.t//e:///aaaoorr////////////0
Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48, Springer, 2009.
CHEE-S Chow and John N Tsitsiklis. An optimal one-way multigrid algorithm for discrete-time stochastic control. IEEE transactions on automatic control, 36(8):898 1991.
Thomas Degris, Martha White, and Richard S. Sutton. Linear off-policy actor-critic. In Proceedings of the 29th International Conference on Machine Learning. ICML 2012, Edinburgh, Scotland, UK. June 26 - July 1, 2012. ieml.cc/ / Omnipress, 2012. URL htttt:://ccm..cc2011.. p 26
Vektor Dewanto and Marcus Gallagher. Examining average and discounted reward optimality criteria in reinforcement learning. CoRR, abs/2107.01348, 2021. URL /ttpss///rxxxv.o/////bbb
2107.01348
Francois Dufour and Tomas Prieto-Rumeau. Approximation of average cost markov decision processes using empirical distributions and concentration inequalities. Stochastics An International Journal of Probability and Stochastic Processes, 87(2):273-30) 2015.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. ICML 2018, Stockholmsmässsan, Stockholm, Sweden, July 10- 15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1582-1530 PMLR, 2018. URL http:://pppoeecnnnss...rrrrsssss wwtp:///offooooooooooooooooooooo ha.html
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Ma- chine Learning, ICML 2018, Stockholmsmüsssun Stockholm, Sweden, July 10-15, 2018, vol- ume 80 of Proceedings of Machine Learning Research, pp. 1856-1865. PMLR, 2018. URL http:://prooeealngg........
v80/haarno ja1..hhmmllllll.....
Vijay R Konda and John N Tsitsiklis. Onactor-critic algorithms. SIAM journal on Control and Optimization, 42(4): 143-1166, 2003.
Chandrashekar Lakshminarayanan and Shalabh Bhatnagar. A stability criterion for two timescale stochastic approximation schemes. Automatica, 79:108-114, 2017.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:/ http:///xxxvirrr//// abs 1509.02971
Qiang Liu, Lihong Li, Ziyang Tang. and Dengyong Zhou. Breaking the curse of hori- zon: Infinite-horizon off-policy estimation. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi. and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 5361 2018. URL https: /tt.o///oo/////pp..........oo... 22 htt.safffesssttt122--aatttttttta
10

---

Under review as a conference paper at ICLR 2023
Xiaoteng Ma, Xiaohang Tang, Li Xia, Jun Yang. and Qianchuan Zhao. Average-reware reinforce- ment learning with trust region methods. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference Artificial Intelligence. IJCAI 2021. Virtual Event / Montreal, Canada, 19-27 August 2021, pp. 2797-2803. ircai.org, 2021. doi: 10.24963//jcai 2021/385. URL
Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Mach. Learn., 22(1-3)):599-195 1996. doi: 10.1033/A:01188640655555 URL https
A Yu Mitrophanov. Sensitivity and convergence of uniformly ergodic markov chains. Journal of Applied Probability, 42(4)::003--011 2005.
Ofrr Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' AAché-Buc, Emily B. Fox, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 32: Annual Conference Neural Informa- tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 1at0019/ahhhh
pp. 2315 2325, 2019. URL https: /tt.ttss///prrrccc......oo 2E52242110E33337722222222222 wtw.raaa55552-Atttctttt
Abhishek Naik, Roshan Shariff, Niko Yasui, and Richard S. Sutton. Discounted reinforce- ment learning is not an optimization problem. CoRR, abs/1910.02140, 2019. URL http:
John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, and Pieter Abbeel. Trust region policy optimization. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML'CCM.... 15, pp. 1889-1897. JMLR.org, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017.
wttp:///..xxv.oo///// abs.or/gg//////ooooo///.a///s.ee abs 1707.06347
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra. and Martin A. Ried- miller. Deterministic policy gradient algorithms. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pp. 387-395. JMLR.org, 2014. URL URLhttp! /022//iili silver14.htm.
Richard S. Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Sara A. Solla, Todd K. Leen, and Klaus- Müller (eds.), Advances in Neural Information Processing Systems 12, [NIPS Conference, Denver, Colorado, USA, November 29 December 4, 1999), pp. 1057-1063. The MIT Press, 1999. URL http:
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq. Timothy P. Lillicrap, and Martin A. Riedmiller. Deepmind control suite. CoRR, hts//801,00069 2018.
abs/ Abs//181.00690
Yi Wan, Abhishek Naik, and Rich Sutton. Average-reward learning and planning with options. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 22758-22766 Curran As- sociates, Inc., 2021a. URL Pappp. Paper.ppf 7058E544673778 7caas//6e77777eeeeeeee33333aaoo3
Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and planning in average-reward markov decision processes. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10653- -06622. PMLR, 18-24 Jul 2021b. URL (ttpppap.s/pppoceeeeegggnnggeees wan21 a.html

---

Under review as a conference paper at ICLR 2023
Yue Frank Wu, Weitong ZHANG, Pan Xu, and Quanquan Gu. A finite-time analysis of two time- scale actor-critic methods. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (cvaanc in Neural Information Processing Systems, volume 33, pp. 17617-17628. Curran Associates, Inc., 2020. httpttss:: http://ss/pppoeeeeeneeeeeeeeeeee 6c355559255572244441447777701000
Huaqing Xiong, Tengyu Xu, Lin Zhao, Yingbin Liang, and Wei Zhang, Deterministic policy gradient: Convergence analysis. In The 38th Conference on Uncertaint in Artificial Intelligence, 2022.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline esti-
mation of stationary values. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL https:
//openrevis www.net/forum? d=Hkx cnVFFB
Shangtong Zhang, Bo Liu, and Shimon Whiteson. Gradientdice: Rethinking generalized offline esti- mation stationary values. In Proceedings of the 37th International Conference on Machine Learn- ing, ICML, 2020, 13-18 18 July 2020, Virtual Event, volume 119 of Proceedings of Muchine Learn- ing Research, pp. 11194-11999 11203. PMLR, 2020b. URL http:/ /prcoped ing.ml m...m...po r.press/ v119/ 2hang20r.htmm
Shangtong Zhang, Yi Wan, Richard S Sutton, and Shimon Whiteson. Average-reward off-policy policy evaluation with function approximation. In International Conference on Machine Learning, pp. 12578-12588. PMLR, 2021a.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network. In International Conference Machine Learning, pp. 12621-12631. PMLR, 2021b.
Yiming Zhang and Keith W. Ross. On-policy deep reinforcement learning for the average- reward criterion. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Interna- tional Conference on Machine Learning, ICML 2021, 18-24 July 2021. Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12535-12545. PMLR, 2021. URL http://prroceddings
r.press/ v1 39/ zhang2lg.ngnm
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buu, Emily Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8665-8677 2019. URL /ttp::/s/ppppoeeeeeaarar/a//////
A APPENDIX
A.1
ADDITIONAL ASSUMPTIONS, PROOFS OF LEMMAS AND THEOREMS
We make the following additional assumptions.
Assumption 9. The transition probubility density function for policy with parameter 0 is Lipschitz continuous w.r. 0. Thus, max | (s' pma (s'{s) < Lell0, 02]].
The above assumption is a standard assumption in theoretical studies in literature. Reference for those assumptions can be found in Xiong et al. (2022) Bertsekas (1975): Chow & Tsitsiklis (1991)
and Dufour & Prieto- Rumeau (2015).
Assumption 10. The reward function for policy x with parameter 0 is Lipschitz continuuus w.r. 0.
Thus, max,, R (a) R*)( S L, 10, O2ll-
The above assumption can be satified by using a well defined reward function ensure Lipchitz continuity of reward function w.r.t action and then evoking Assumption 7
Assumption 11. The initial value of target estimators is bounded. Thus, || |I $ C.,, and || - (Cr 2Cw).
12

---

Under review as a conference paper at ICLR 2023
Assumption 11 is used to enforce the stability of the iterates of target estimators.
Assumption 12. Let A(O) = f (s) Pa (s))s)) (s') ds' - x0 (s)) ds. Amin is the lower bound on the minimum eigenvalue of A()) for all values of 0.
The assumption above is used in Lemmaf6to prove the Lipchitz continuity of optimal critic parameter w" for particular value of policy parameter with respect to B. Assumption 13. Let A' (0)
(s')s))"" ds' - ds. A is the d' ( (s) PT
upper bound on maximum eigenvalue of (A) (2) for all values of
Assumption 13 is used to prove the negative definiteness of the matrix Ag (defined in Assumption 12 Lemma
Assumption 14. Let Hi = ( ( ds. Xmin is the lower bound on the minimum eigenvalues of Ho for all values of 6.
The above assumption is used in Lemma 13 to make sure Hg invertible and optimal critic parameter w. according to compatible function approximation lemma (Lemma 2 can be obtained. Similar assumption is present in (Xiong et al. 2022).
Assumption 15. Let (0)) d' (Ø" (s)(J ("((sss) ds' ozt (s)) ds. X is the upper bound on maximum eigenvalue of (A (0) A ( for behaviour policy μ and all values of O.
Assumption 15 is used to prove the negative definiteness of the matrix Ag (defined in Lemma 15 in Lemma 16
Lemma 1. There exists a unique constant k(= plz:) which satisfies the following equation for differential value function Vaiss:
Viits(()) = E. [R((Rs), az) - k + V (
Proof.
(x1) = ((11) - +
Vār) - ps (8 dss+1 (((5, -
T-1 E (V -
T-1
Σ
R(st, x(s)) ((66))) KT
Integrating w.r.t the stationary distribution d" of policy क
Σ l d" (st) (V))((()) (v))(vv))) - / p (s
(Se4 drcr1) de;
T Σ
d'
KT
T-1
(/ d' (si)) ds) - d ((((1))) ($(1))))))))))))) ds(+1)
Σ
($1+1)
0=
T-1
= Σ
dt (si) (())) ds: - KT
1=
(Js dt (st) dis ( ds. -ss d= ( Vā. (155(1441 dect1) = 0.
Note:
13

---

Under review as a conference paper at ICLR 2023
1 T-1
= k
df (()))) ds.
T
t=0
k lim
d= ((s, dec
T+x
A p(T))
(using
3
Theorem 1. The gradient of p(TT) with respect to the policy parameter 0 is given as follows:
Vop(T) d" (a VoT ds.
Proof. Using Lemma]
(8)) = R(s,, ((+)) p(T) / ps (8c41150)) ( d8t+1
(si t($))) = R(s,, (st)) p( + / pd ((a dssi
Differentiating w.r.t 0, we obtain
(8 = ((+)) Vop(a)
+ (L P d
v. Vali(s VoT(S:)
- Vop(T))
+ / (.P"( Vo ((42)) ds
+ p
ds-1
Note: Vep(T) = V. df (s)
=0
(e = (s VoT(s)) - Vep(TT
+ $ [ d811-
Integrating w.r.t stationary distribution d= d'(()) of policy m:
| d' (5,
(s)
Vop(T)
+ (F((s)) / (
dres1 ds..
Note: [g (s)P d= (s'). Thus,
Vop(T)= = / d' (st) V (t VoT
d'((s)
+
8= (s V ( ds
[
14

---

Under review as a conference paper at ICLR 2023
Vop(T) = [ (s (esVaaaygls, (la=x()))) Vor(s)
Lemma 2. Assume that the differential Q-value finctiin
satisfies the following:
1.
V Va (5, (s,
2. The differential Q-value function parameter = w", optimizes the following error function:
1 2 / di (s)ss (s))IVo (
((0,
ds.
Then,
= /
(oTTs,) ds.
5
Further,
V. (aQāff(s,a) Vo (for linear function approximator).
Proof. Let s)) V (8, V (8,55((,,))a=iii
<(0,w) d' (s)())(0 w, 8) TE w, ds.
Differentiating w.r. the critic parameter w, we obtain:
Vmn((0,w) = d' ( w, s)E w. ds
{ d" VoQuif a)la=x(s)) (Valies (V a)la=>(s)
VaQWi a) =))==)(s) ds 0.
Letting w (s, (oT(s), we obtain
| (s) (oo or = /
[ (o
Let consider the case of linear function approximator with parameter w, i.e., Qū (s, (())) 6= (s, Tw.
We know from above,
V V P (() VoT(s)
(A.1)
Vari" (3, a=n(s) (oT(s).
Thus,
Qar (s, (s))
Voliir(s, a)la=x(s) Va0 (ss,,)) "= [=))))))))
v.lur ()(==)()) VoT(s) (using A.1
15

---

Under review as a conference paper at ICLR 2023
Theorem 2. The approximate gradient of the average reward p()) with respect the policy parameter is given by the following expression:
Vep(T) -s f (a Vor(s, ds.
Further, the approximation error is ETT, ( where μ represents the behaviour policy. & satisfies
- Vep(
{( S - -0 11
Here, Z = 2 C([log a + L; with L, being the Lipchitz constant for the transition
probability density function (Assumption Constants a and k. are from Assumption 2 m the dimension of action space, and C max, Va Vasrss ( (88,0))a=nts) Vot(s, 0)ll-
Proof.
(TT. [Vop((T) Vop(T)]
d' (5) Vorts))
(8,0)) Vom dsl
dd (d -d' (s) Q (s.0)===11 (oT
C 1dt (s) ds.
5
Here, C = max, V (V (s)0)) VoT(S, 0]|. Thus,
E(T, S CLall0 0n1| = - - -0"1l (using Lemma
Here, = = 2 a =1 + 1/K)
Lemma 3.
Let the cunulative ervor of on on-policy actor be ET-1 El(Vop(0))l and cumulative error of critic be Ei El|Aw,l? 0, and wa are the actor and linear critic parameter at time t BoBund on the cumulative error of on-policy actor proven using cumulative error of critic as follows:
C. C-Tw-1 E Vep()))) <
1 T
4
30
E Awill? 3C
C2
C
M
C.L.GH
Here, C, is the upper bound on rewards (Assumption 5) Csp, are constants used for step size "ie
(Assumption [VoT(s)]] Cx (Assumption 7). Aw, w. wi, max, ||li w., |l. w the optimal critic parameter according to Lemma 2 wi is the optimal parameters given by TD(0) algorithm corresponding to policy parameter 0. Constant Cw; defined in Lemma 73 L the
coefficient used in smoothness condition of the non convex function p(0). Constant Gg is defined in Lemma the size of batch of samples used update parameters.
Proof. By L-L,, L-moooothhess of non-convex function have:
LJ El - Bpl1..
E[p(0 2 E[p(0.) E(Vop(())) - 01) 2
(A.2)
16

---

Under review as a conference paper at ICLR 2023
Now,
h(Br, 01)
M Σ
1 al
0e4 - 01) = 7VV h(B, wt. B1))
(..))(op(O.), Wr, 0z) Vap(O:)) +7 (A.3)
From
A.3
have
E ((V) h Be, Wr, 0.) Vop(O:)) 2 - F Vo))))1) - 1 FlIA(B,, we, 01) Vop(Ot))
(.:xTy 2 2/ |1v11//2)
(A.4)
From A.4
(iI we 02) Vop(0.)12
= -E]]h(Be (B, Wr, 02) - 11 Br, wi 02) + (B,,, wi,0,) - lB,,, wi 01) + h(B,, wi 0z) - Var(0,))1
S 33(ElIn( Br, Wx, 02) 1(B,, w 0.)1 !
+ hElhBBBBB (B, i 01) h(Be, w 00)1 2
+ F (Be, / 02) Vop(O,)
(A.5)
From A.5
(B,, wi, 06) h(B,, 0,)11
" (s.. (al=mton) (oT()E)))
V VaQui (st,i, (looaaa)l
= M
10
==
Here, by compatible function approximation lemma
V Va (s: Vot(s)Tw.
El|M(B., wt, 0.) lb,,, wt 0.)11 =El E'l Σ
- wr)l
1=0
< C w
is similar as I:
Ellh(Br, ;,) h(Br, w 00)1 < CfE w
$ C+72
By compatible function
approximation lemma
2
Vep(O.)
S ((sss((())) (0..)
Twi ds = FTh Bz, w²,,, 0.)
* By lemma 4 (iiong et al. 2022). if E|8 Y, || 11, || S Cy then,
M-1 1
C2 M
E
Σ M
Y, Y
$
1=0
17

---

Under review as a conference paper at ICLR 2023
Using above two bullet points:
4
E ( w 02)
Vop(Ot))
M
4C
M
Combining 2.2 and 3 and using A.5
40
Ellh(B Wi, 0.) Vop(0:))1 530 w]l1 +
(A.6)
M
Using A.6 in A.44
(B), wr, w,, Vop(O.)) 2 -- V
(A.7)
3
(Blluu - will + + +
402 M
w.
)
2
Using A.7
in A.3
01) 2 "t E1l Vep(O:)11
E(Vap(0)),0c41
2
(A.8)
3%
402
0+ Wi
w/'l
72
Using A.8 in A.2 :
E[p(0(+1)] -E((()))
E[p(0,)]
Yt E Vep
L,
E 1 - 0ul1
2
2
3 3/ CA [u - will 7² +
1C2 wc
2
M
[]]o)p(0))1 =lpp(0 - 30 |w, will3)
402 + +32
Ly (using lemmal
2 E[p(0++1) E(p((0) 1
E 22)(2))
71
3C (Ellw) - -w;l13
(A.9)
4C2 M
30 (-² +
w.
L
(using lemma 7
From equation A.9
18

---

Under review as a conference paper at ICLR 2023
I:
2
E(p(0++1)] Elp(0.)) = Σ
1
)
1
Flp(O.))
Elp(0o)]
Elo(Or))
7t
71
Ya
-1-1
1=
1=
-11
1
Elo(Oo)]
2
Σ
Fl(((.))]
7t
2
Σ
1
1
+ +70
)
Cr
71
2-11
00
2C,
2C
---1
C
2:
T
T-1 3C W2 - =,,11 = Σ
30 Awx
t=
4:
T-1
Σ
Lr
L,G.C -
T
(:
T-1 Σ
di
-
1 lo
0
1-
Using - 4 and dividing equation A.9 by T:
T-1
1
Vep(bil1
C. <2
CTT--1
+ 30
E Aw, | +
+0 +
4 M
co.
T 1=U
C
1=0
T-
Lemma 4. Let the cumulative error of linear critic be EI-EEAAA and cumulative ervor of
average reward estimator be Ei= El |p:ll. We and Pt are linear critic parameter and average reward estimator time respectively. Bound on the cunulative evror of critic is proven using cumulative error of average reward estimator as follows:
20 To-1
CyCaT-o+
Σ E
AW,,
52
$
T
XC,
1 1-0
Iou (1
T (11(01)) (2()))
1/2
2(C, 2(Cr+3CC)) +3Cw)
2
2 X2
E
Apil
L=0
Here, Aw; wi, = Pi. wi and p are the optimal parameters given by TD(O)
algorithm corresponding to policy parameter 0r. Can a are constants and 7tt, 04 are step-sizes defined in Assumption 3 well S Ci (Algorithm 2 step 8), C, is the upper bound on rewards (Assumption L2
5y. Constant Go is defined in Lemma C Algorithm 2 and n >> Xalt where Xall defined in Lemma the 12- -regularisationn coefficient from from
max, I2 G2 + C2
X C. = 2C, + (4 + 7) is
of
11 X is defined in Lemma 17 Teg is defined in Lemma 6
19

---

Under review as a conference paper at ICLR 2023
Proof.
M-
W++1 = wt + 0tt M
Σ
R (8t.s) -p + (66,))) (81,)) Twxe (81,)) 0x
W141
wi+1 17 3
+ wi
wi+1 !
M-1 1
1
+ at M
1tth (st,a) - 0i + 00 (51,)) Ww - (s-()) (r (5t,)) axppur 2
M-1
1
(pi ps) 6 (st,))
+ 0
M
1=0
M-1
1
Σ
(p: 0:
0" (st,a) 4
a
M
(A.10)
From equation A.I0
M
Rd (st,s) P2 + oz (s(,,) (st(s,,) " (sL,) 17wb
M
1 M-1
R ($t,)) - P2. + (s(.;)) - (0)() us) 00 (s 170l
M
M-1
+
0² ($1,))0 (d,, - we)
M
i=0
M-1
Σ
1x (st,))* ( T
we) + g( Be. wx, 01) g(we, 0c)
M K=0
+ g(w,, 0,) g 0i)
(A.11)
Let g(B,, Wt, 0i) = M EMO R2 (se.)) (o
- pi ( + 1 1 (0"()))
M Σ
s= (st.))) -n!)
nn) w/
Let g(we, 0²) == d(s, n (0)) )o (3) (r)) pt + (6) ds'
(s) -00 ds
Using equation A. in equation A.10
11+1 w/+1 =w; - w + w w
M
+ a M
1
Σ
(pi - -
1=0
M-1
1
at
Σ
(pr p=) (stx)
M
1 M-1
Σ
8 (st,)) ( (T wi)
04
M
(r We, 0.) g(w, 0:)) + +az We, 0₂) g( [ 0,))
20

---

Under review as a conference paper at ICLR 2023
M-1
Let,
f(Br, wr, 01) = M
Σ (0i - (st,)
==0
M-1
Σ (pr (x))²((8.)))
M
o= (8t,)) (btx))))((((,)) (1 1000--ws). wx)
M
g (B,, we: 01) [w 0z)
+ g(wr, 0₂) g( w; 0t)
1
11 = I1(w; - w/) + (w) - wit1) + of w;
0,, 01)
||wc w 112 + |w1 wi+1ll
afllf wT: 02
+ 2(Aur, wi wi+ 1) + 20 (Awi, f( (Be, wr 01))
+ 20r(w] - wi+1 B.e, wi, 0t)
E| 0111 - w1+1112 < B|| Awy + 2F| wi - wi+1ll?
+ 2a f wT: 02)l
+ 2E Aew. wi wi+1)
+ 20, 20,EE(A BEEEE(AW, Wt, [B,, Wt, 0z))
Aug 2E w7 w
1
+ 2a [[Be, Wz, 0.) 1
+ 2E Awi, wi w(+1)
+ 20, E(A'::
1
Σ
(0t (st.)
(A.12)
M
M-1
+ 20, E(Amr;
Σ
(Pr - (st.)) 5
M
.-11
+ 2a, E(Aw::
Σ
8- (s (s T w:)) 6
M
2=
+ 20, E B(w,, g Br, we 02) g(w: 8,))
+ 20, E(Aur, AWw.tgww.e gwn, O1) g(u, 0.))
From equation A.12
E [w wi+1 11 < 12 0.1 (using lemma 6
< L2 Gg (using lemma 7
2:
BB, wo, 0.)
M
=El 1
Σ
(RT (9t,)) P: (5(.))) (T) (s(.)) mwoll2
M
M
< B(1
Σ (st.)) - pe + (5(..) (wr.) (st,)) + wlwlw/11
M
21

---

Under review as a conference paper at ICLR 2023
Here,
1 (s)ll < (Assumption
R (s) S C, (Assumption 5
||we|| v Cw (Algorithm step 8)
|pt| I C, 2C (lemma 8
|| I C (lemma 9
| S C, 20 (lemma 10
M-
11(11 (st.s) Pt + 0= (6(,)) o (8"..), (w)))) (sr,))l + rl/w.ll) ==0
B(C, C, + 2C + 2C + n2)
B(Cs)2 (Oss 2C, + (1+
3
B(Awr, ut - B||Aw,|l || - -witll
L. Aw:ll |10++1 Oell
(using Lemma b
M
M
B (Awr, M
Σ
- - (sr,))) (--))((().))))))
Awr o= (s.a)))t px)]
M
1=0
M
< EE
||
pt)1
M
El Awe
|1lp: pel
E
Awc
||
5
M
M
B A
Σ
(pr P.) (st,)) = E
(er o= (srr))) Pi)l
M
M
1=0
E2
|| (sc,))) -Pel
M
E1 Awv. Ilpe
pell
< E [ill + [p:1)
Awx/1]2(C, + 2Cw) (using Lemma g 10
6
M 1
1 M-1
1
E(A E(Awi Wii
M (st,)) (1T wx)) A|
Σ
Σ
x (st.))
(St.)) w.)l
M
E Aw,
[7, 1e-wwy well
< 2,, E||Aw/]l (using algorithm 2
D:
[ Awr, Be, we, 02) - g(w,, 0.))) = E((Aw, Elg( Br, we, 0c) g(we, 0.) Awx)) Note: Elg( w., 0.) g(w,, 0:) 0
Hence, [A g (B, Wz, 0,) g(w,, 0t)) = 0
22

---

Under review as a conference paper at ICLR 2023
8
BKw,, g(rr, 01) -[(w],01)
A(O;) d (s, (s,00(00 (s) (6)))))000 (s') (s) n/)ds
b(tt) d" (s. 02)r" (s)ø"(s)ds
g(w, 01) gww 0t) b(0,) + A(O,)ur - 6(0.) A(O,)w)
A(O:) WE wi)
Now,
g(wr 01) g(w] Ba) = E( A(0r)
E[Aw? A(0:)
- AE| Awell
(Lemmaa
Combining I
8 into equation A.12
W wit1 11 s (1 2Aa, ) w || 22 + +2,203
+ 2L A W/ 8:41 - - 2a,B| Apd
40 A w/
[2C C,) + 4a, Awill
E||l Aws [3] E 1w 2T G + 202
21 7 Go Awx|| + 20 Aw. pp
(C, + 3C Aw:/l
EE Awrel
(EE) Awee 112
EE| /ew+++ 112)
2Aoz
Dun
G3 01 (²33)
Lmu It
GubllAwa!l
X
E Aww Awpl
2 (Cr + 3C (BI..,)
x
T- 1
Wil 1 <
[E) Awwl
El
2doz
1=0
Lu Pt
G3
+ 2
C
2
Cte
Lw 7t
Go Awa
(A.13)
ai
B|JAw/llAAp
A
(C, + 33 A1w 5
23

---

Under review as a conference paper at ICLR 2023
From equation A.13
T-1
(E
[B|
BI
12)
1
1
E||
E||Awil1
1
E
A Awrrl 11)
2A
at
21
04-1
aT-1
1
Σ
1
+
2X
04
04-1
0n
40
C To
Co
(::0)
21
XCa
(1 + t)a
2:
2 2
T-1
2
C3
m
3t
G7 +
c3
ai
L 't at
G +
a
at
X
1=
I2
π G2 +
C/
max a:
)a
T-1
CgCa ri-o (C2 = x
I
2 G
C.
Σ
Cjas =
max
+
1- o
ai
3:
T-1
Σ
Lu Yt Awwll
Lu Go
T-1
Tt E
Awell ||
x at
A
a't
1=0
Lu
(El)aw)l))) 3
S (Using Cauchy Schwartz inequality)
Go
Σ
1/
Lu Go
Awyl Awa1lp) Ip) 3
Σ
E Σ 1=
S
at
(Using Jensen's 's inequality)
4
1 T-1
Σ
1 B V
1 (E|L (²)
T-1
1/2
T-1
(B (1))).1)3)
A
T
$
<
B||Aw1112)
(Σ
T Pp)))
1
1=0
1=
5
2(C, + 30ww)
2(C, + +3Cw))
El BllAw/l1 5
E Aw, 12)
(Σ
A
2(Cr + +30
T
IE| Aww 112) 7/2
7
A
24

---

Under review as a conference paper at ICLR 2023
Combining !
5
into equation A.13
20
E Aue 12 =
1
+ 1-0 0
T
CC
t=0
Go
T-1
2
T-1
Σ
+
A
T
T
T-1
T-1 G
1
Σ
1| |1?)
+
A
T
t=
2(C, + +3
T-1
Σ
B
T
Let,
1 Σ
M(T) T t=
B1 1
1 N(T) T Σ
M(T) < K1 + 12 + M(T)
20 - CoCar-a
K1
XCo
1-o
K2 = Gu
1 T-1
2
+3Cw)
X
T 1=0
K3 = X
K2 M(T) - 2
K3
K2 K3
V M(T) - M(T)/N(T)) +
-
(T)
2
2
2
2
+
K2)² 2
+
K3
(N(T))
2
< +
K2) 2
+
2 +
K3
(NTT)
2
+2
K₂ K3
((T
2
2
2
2
2
- (VM(T)-
K₂
Ky
((T))
< < +
Kg
+
K3
N(T))
2
2
2
2
K2
K3
Kg
K3
VM(T)-
(N(T) < VKi
VN(T)
2
2
VM(T) S KK + K2 + K3 N(T)
= M(T) S 2( v K, + K2) + 22
+
1 H
2 52
(1
20 XCo
T +
CoCaT-o + Ga
7
1 T-1
1/2
+
2(C, + 3C
2
x
A
1=0
2 1 T
X² T Σ 1
t=
25

---

Under review as a conference paper at ICLR 2023
Let the cumulaatiee ervor of linear critic be El and cumulative ervor of average reward estimator be Ei= Bpp we and Pt are linear critic parameter and average reward estimator at time respectively. Bound on the cumulative error of average reward estimator is proven using cumulative error of critic as follows:
Lemma 5.
T E
2(C, + +2cw)
C.CaT
Pdp 2 S
$2(1
T 1=0
Co
T-1
)
7/2
2
+ Lg
Σ
(
+ 40
T
t=0
T-1
+
E1
Aw,ll 1?
Here, Ap. = Pt- Pr. Aw,, - wT. W; and pt are the optimal parameters given by TD(O)
algorithm corresponding to policy parameter Or. Ca. a are constants and it, 04 are step-sizes defined Assumption 3 |wwlll S Cw (Algorithm 2 step 8), C, is the upper bound on rewards (Assumption 5)
Constant Gg defined in Lemma
C2 Lg maxt 2 +4(C, + )0 Ly is Lipchitz constant
defined in Lemma 14
Proof.
M-1
Σ
R ((t)) - Pr + (s(,) (T,,,))
Pci1 P: at M
Pr+1 Pi+1
P: Pi p
Pi+1
M 1-
+ at M
1
Σ
R (81,)) - Pc + (5" - (8(,))
k=
= P: 15
+ p
-Pi+1
M-1
1
Σ
n8
(8t,)) - + ('',,' (sr.))
+ 0t M i=0
+ (p - Pt)
Pt+ P(
P: 0i P -Pt+1
( Pt)
M Σ
1
10 (5(.)) 00 (sLL)) -wi- w.))
00
1 M-1
+ 01
M Σ
(R (81,)) - 05 + + (51,,) - 40 (s
P: 04 Pi-
-Pi+1
(p pi)
M-1
M Σ (0" (st.)) o (m.))
04
+ a: (I(B, wt. 0.) I(wr 0.))
+ a: (I(wr 02) I(w 0z))
26

---

Under review as a conference paper at ICLR 2023
Here,
1( (t) (1) M-1
MM
Σ
R (5t,s) - pt + x0 (s),,) x" (s.(),))T)))
I(wr,0a) 0z)
d= (s. R (5) - p(=(((.)) + + (s)(s) ds
58
i( Pt, Wt, 01) (pi Pi)
M-1
Σ (5(.)) - (st,))) wi)
+ (((Be, We, 0r) - [[urt, 0())
+ (Nw,, 01) [[w 8.))
|| 112
|| Pr arl(B,, We, Pt. 02)l
= -|Ap/ll? + llpi - Pitall? + a (BB Wo Pc. 0,)11
+ + Pi: - Pi-1)
+ +2, pr, (Br, W/, Pc: 0,))
+ 20 (pi - pi+1, 1( Br, Pt, We, 0t))
< |1 A +211p: - Pi+1 + (a We Pc: 0.)l
+ 2(Apt. pi: - Pi-
+ 2a (Apr, (Be, Wh: Pt: 0,))
E||ApH11 1 $ ppt 112 + |E -it+1ll 11
+ 2a [ [BB,, Wt: Pt, 02) 2
+ 2T Apt. P3 pi+1)
3
+ B2, Apr)
4
(A.14)
M-1
1
+ Ba,B(APt, Pt.
Σ
(0
(5 6= (st,,)) -w,)) 5
M
1=0
+ 20, ((B,, Wt, 8,) I(wi, 0,))
+ 2a, I(w,, 0,) I(w[ 0,))
From equation A.14
B 1p++111 1 0ell2 14)
2
E| [BB, Pr, Wr, 0.)1
E
1
RRT (st,s) pr - (0"(s),) o (s())))) 10)) (s()))))
M
M-1
IC, +2 + +2Cw)) 2
Σ
1=0
= 4(C, + 2C2)2
3:
EI E(Apr 0f -142)) < Ap pp -
< L E Appl 1 0el1
4
E(Ap, Ap) - App
27

---

Under review as a conference paper at ICLR 2023
5
M-
ptpp
T - (8)))) wi))
M
E
Σ
1100 o= (*tx)))) well A
M
1=0
S 40
O
E(Apt. (B,, Wi, 01) - [[wr, 0.)) = BB,,, wr, 0.) - -(wr,,:)) 0p)l Note: B[[ B,, Wt, 02) - -[(wr,,))))) Pp]
E(Ap,, [B,, Wt, 0.) I(wes 01)) = 0
7:
E [A,p, H(re, 02) I(wi 0()))
E[(A,r, (3))
((()))((v)))) (we - wi
S BI(00 (s') - 00 (8), (m)
- |Apel]
Apel)
Combining 1 7 into equation A.14
B B| 112 <
10l 2
00.- - 0.112
+ 80, + 2C 2 |0 0.1
+ C, 4a, Appl
T
T- 1
Σ
E 12
Σ
E|I P-P---EA ElJAp++1
1
20y
1221
G + -An,(C, + -2Cx)²)
2
a1
(A.15)
Tip Cx
Go + 4C B|Apel 3
2|||
Awc App
From equation A.15
T-1
1
Apt - P1
1 113)
ElAp!
12 + a0
E_AApp!
2
E Ap
2
04
ar11
QT
t=0
1=)
T-1
$
Σ
ar-1)
1
1(C, 2Cw,)
au
1=0
2(C, + 2C2)
T
Ca
28

---

Under review as a conference paper at ICLR 2023
2:
1e G2
2 max + 4(C + 20n)))
4or 2C,x) 2Cin)))))
Gg 2
S
at
at
d + 4(C, + 20
C,a.. (C, = G max
of
CoCaTi-o
3:
T-1
Lg
"t +
= Σ
Go Ctt
El|Ap:ll + 40
Σ Blll
az
tt 2
T-
E| Ep 1p) 'T
S Go
Σ
Σ
+ +AC
(using cauchy schwarz inequality)
4
2
B|| Am; Appl S 2(
Σ E Awe 13)
Σ
R P))
t-
(using cauchy schwarz incquality)
Combining 1
4
into equation A.15
1 T
T
2(C, + 20 PTO-1
C.CaT
p.12
E
+
Ca
1-0
T-1 Σ
)
2)
1/2
+ To
Σ
R App
T
ai
T
1=0
1=
1
1B pp. +
+ 4C
T
(
T-1
+2
E
E
1=0
1 M(T) + 1 N(T) T
Σ
pl|App11
M(T) S K1 + K2v M(T) + K3v M(T)
Here,
Ki 2(C, + 2C2)
C.C.T-
Co
1 1-0
1 T
2
1/2
K₂ = LoGo
+ 4C
T 1=0
a4
K3 2
29

---

Under review as a conference paper at ICLR 2023
From Lemma 4
we know that
M(T) 5(T) + + 2K3N(T)
Hence,
21
-20w) To-1 C.CaT-o
Σ R p 5
Ca
1 T
+ G,
+ +4Cw)
T
T-1
+ 8 T
Theorem 3. The on-policy average reward actor critic algorithm obtain e-accurate optimal point with sample complexity M(E -2.).
E V Vop(B:)]1 = 0 1
min
+ 011)
0
70.4
min
E Vop(0:)) se+
Proof. Using lemma 4 and lemma we obtain,
T
20
C C.Ca + Go 1
T-1
m))
1/2
2(C,, + 30rr)
T t=0
Ell Awwll
< 2
(
AC
" 1 +
1-0
X
1=0 04
+
A
(
12(C, 12(C,++20u)) +2Cw) Ta-l C.CaT + LyGo
{
T-11
Σ
7t (2)
1/2
+ 4C
2
x2
Ca
1-0
T
ai
16 T-1
El Aw! 1
X²T t=
2X²
202 2o-oo- CoCap-o
A mz 1| <
x2 16 (1
ACC
1-0
+ L Go
T-1
1
1/2
+
2(C, + 3C,w)
2
!
att
A
1=0
(A.16)
4
(V'
2(C + 2Cw))
-T--1 C.CaT-o
X 16 (V
C.
1 1-0
+ Lo
Σ
T-1
it
1/2
+ 400m
2
T
1=0
From equation A.16
I:
2(v---
2
5 1- 2( - a)
a
C.
(1 + ++)2(0-o)
Σ 1+r
1
T 1
T1-v
<
dl
10
30

---

Under review as a conference paper at ICLR 2023
(V
2
CoCap-o +
LuGo (1
T-1
1/2 2 )2)
2(C, + +3Cw)
+
ACa
1-0
A
1=0
20 ACa
To- coCaT-+ LoGo
T-2(v-o)
1/2
2(C, + +3Cw) 2
1-0
A
1 2( - 0)
20 T + C CaCaT T +
T Lb)
2
2((C, + +30w) 2)
33
1 2(1 0)) +
ACa
(a + + c)² < <3 +b² + +))
1
0
0
0
T2(1-0} 0(1)
T--0
T
(similar to I):
2(C,, + 2Cw )2
To-1
C.CaT-a + Go
T
Σ
())
1/2
4C
Co
1 1-o
1=
1
1
+0
+0
+ 0(1)
TI-0
To
T2(6-07
Combining 1 and 2
T
1
1
Aw;
12
+
+
+ +0(1)
(A.17)
T1-0
T
Using lemma and equation A.17
E ol)p))))) 0
1
1
+0
1
+
T1
T
T
T
+
+0(1)
72(v-0)
1
1
1
min E 0StST-1
Vop 0
O
O
+
0
T1-8
To
71-0
To
+ [2(0-o)
+ 0(1)
1 T-1
( min E Vop(be11
Σ
[)P(())))
1=0
By setting 3/5 and 2/5, we obtain:
min 0SEST
E
Vop( 0
+ +11
70.4
1
o
Se
70.4
Hence, the sample complexity of on-policy average reward actor-critic algorithm is (2(6-2.5)
1
31

---

Under review as a conference paper at ICLR 2023
Lemma 6.
The optimal critic parameter w(O,)* a function of actor parameter 8, is Lipchitz continuous with constant Lu- Note: wi := w(())'
||w wi+1ll S Lw110 0zll
Proof. 7j is the 12-regllarisation coefficient from Algorithm 2 and 1j > Xmaz. where Amear is defined in Lemma [1] Because of carefully setting the value of A(O,) negative definite. Thus, for on-policy TD(O) with 12-regularization and target estimators, the following condition holds true for optimal critic parameter w.:
EI(R (s) pi) (s) (o* - (s)) n/)
b(O,) = E[(R"* (8) ())) (s)
A(O,) == (s) (8')) x² (x)) -
b(0) + A(O,)w; =0 wi - A(00))-8(00))
1 wi+1ll = ||A(0.) (()))))(((0)-000 A(0 - 1(0++1)
$ ||A(0)) - 6(0)) 1(0(+1))1((())) ((())) + A(0++1) - (((()) - A(0(+1)) (((+411)
S (1A(0,) - - A(0++1) 11](0)) !
+ [|A(0=+1)
((6(0)) (16(() b(0++1)11
(A.18)
From equation A.18
D:
A(0+=)) -| -((00- [|A(0.) A(0 =11A((())))))
(A.19)
< ||A(0,) "11 (|A())) A(0++1)ll ||A(0++1)
From equation A.19
Here, Ní and represents the policy with parameter 0,-1 and 6g respectively.
||A(0.) A(0++1)ll $11 (o)0 (1 (1 (d10)) (8) -x' (8)) 7/)) ds
f [1001000)( (s)) - 171) ds|l
$11| / (0) (((11))))))))))0 (s)
(
1
(5) 11| (670 - (s)( (s)) ds|l 2
(A.20)
From equation A.20
32

---

Under review as a conference paper at ICLR 2023
①:
f dr' (s) (s)( (d'ls)o (s) ds)) ds - / d' (1)( (5 (P) ds') ds|l
11 ( (d(lsss) (s') dsll
+11 +1
PT)00 (s)) dsll +11 / / (8'ls) (6 ds') ds|l
+11 / (s))
(' (8') (5')) ds ds
I Lall0141 0ell
(lemma 12
+ Lol 00+1 0ell
(assumption
+ 1111e 0ell
(assumption 9
+ L 10 Bell
(assumption
f de' (s)( (s)( / pa (s'ls) (5') ds')) ds ( dspl
< (La + Le + 2L 110011 6.1l
(A.21)
From equation A.20
f (()66)(91( f (s)(0 (s)(o" (s)(a" (s))T) ds|
$ (dT(s) d' (s)) dsll
+|1 xt (s)( (s)) (s)) ds|l
(A.22)
+|| +1I (s) ()) x5 (s)) dsl
< (Ia+ 2T. 0,l
Using equation A.21 and equation A.22 in equation A.20
[|A(0,) A(O < (2La + 44 + L.)110++1 021l
(A.23)
From equation A.18
33

---

Under review as a conference paper at ICLR 2023
2:
[bb(,)) b(0++1)ll = &' ()) ()) (1) (s) - d (f) pi) (s) dsll
$ / & (1) (s) ( (1))
+11 / ( (s) / (ss))pt))
$ $11 / (s) (s) dsl ds|l
+11 (1)) (8) dall
+1 (())) (6) 0= (s) dsll
+1| / (x) d= (t))pi+10 (8) dsll
+ 11 (s)(((()+ p=) (s) ds|l
+ d'())pp(0") (8) - o= (s) ds
SCLo|l0ut1 011l
(Assumption
Lemma 12
+ 1,110141 0ell
(Assumption 10
+ C,LLp1111 0ell
(Assumptionf
Assumption
X
+ C,LLll0441 0.ll
( (Assumption
Lemma 12
1p110-11 - 0.ll
(Lemma 14
+ LoLl11044 Bell
(Assumption Assumption
[b((,)) b(0++1) S (2L.C, + L. + I, + [p)100++11 - 0.1l
(A.24)
Using equation A.19
equation
A.23
and equation A.24 in equation A.18;
1|00 - - w S A(0++))-111 ||44 [b((,) - M(++1))l
$ | ||
[IA ||600))
[16(0,11
+ +1IA(0++1) [b(()) b(0++))l
< (2La+ 4L. + 410) || | 0ell
C2I,C Lg L, A()))((0+1)) |0 0el
Note:
[|b(8.)] fI. (3) (s))T) ds|l C, (Using Assumption 5
From Assumption 12 Amnn is the lower bound on eigen values of A(6) for all
:.Ilw, wi+1ll $ C2 4Ls + L1) X2 (2 + L + L, + Lp)
110 Gell
11:- 0.1l
Amin
< -.w110c4 - 02ll -021
34

---

Under review as a conference paper at ICLR 2023
where,
Leg Cr 4Lg + Le) + (2LaC, 20 Lop + Lpp
X
Xmin
Lemma 7. Last is the approximate differential Q-value function parameterized by w. Then there exist a constant Gg. independent of policy parameter such that:
Va ()) VoT(()) Go
Proof.
[[ Qhis (s, a2)1l & Lollai - a2ll (Assumption 6
V (s) S Lo
(A.25)
V Valdiss a) (-= - Lo
(s, 01) T(s, 02)11 I Lx 02ll (Assumption
(A.26)
V $ L
Using equation A.25 and equation A.26
M-1
V 00
M
i=
M-1
M (000a
T Go
Lemma 8. The average reward estimate Pt bounded.
Vt 0 lpel S C, + 2C
Here, Ou is the upper bound on critic parameter we (Algorithm 2 step 8), Cp is the upper bound on rewards (Assumption 5).
Proof.
PPl $ C, + 20
(Assumption II
For t= 1:
P1 Po + 0pp
R (80.)) + oz (5b, - o (88.0
- pa)
M
1=0
M-1
- =1-00)p0 + om
Σ
RE + (56. x= (s0.:)
M
1=0
M-1
|pd| $ (1 ap)|pol + avll(
1
Σ
R (s0.s) + + ( - o= (su.s) mo)
M
1=0
M-1
<(1 ao)oo)/ + au
Σ
(su,)) (10 |1:00|| + (s0.))))) [|@ol]]
M
1=0
S (1 (o) + 20ww + (C, - 2Cw) = (C, + 2Cww)
(Assumption II
35

---

Under review as a conference paper at ICLR 2023
Therefore the bound hold for t= 1. Let the bound hold for t = k. We will prove that the bound will also hold for k+1
M-1
Pk+1 = Pk + 0.k
Σ
Ra (sk.s) + + (bE,)) Tx - (su.s) - pk
M
M
- ap- + +
Σ
R7 (s..)) + + (64,,) x² (5*.))))
M
i=0
M-1
|Pt+1| S -xx))pk + ax
Σ
R (8k,,) + o0 (+p,)) x0 (sk,,))
M
(1 -ww)Pkl + az
1
Σ
18 (8k,)) +
|v0x|| + (*x,a)l |
M
1=0
S (C, + 2C + (C, + 2C = (C, + 2C
The bound hold for == k+1 as well. Hence by the principle of mathematical induction :
Vt > 0 1pel S C. + 2C
Lemma 9. The norm of target critic estimator We is bounded
Vt 0 [[ S C.,
Here, Cw is the upper bound on critic parameter wa (Algorithm) 2
step 8).
Proof. For t=l:
11 (1 8)) + B
||=]| || < (1 Bool + Bollwill
| || < (1 - Co + +. (Assumption I1
|[i|| < C..
The bound hold for t=1. Let the bound hold for t = k. We will prove that the bound will also hold for k+1
Th+1 = (1 - 8x) + BL
| || (1 3x)] ox Bal[wk+1ll
[0++|l < (1 3x ) B. (Assumption I1]
[0o+1ll $ C
The bound hold for == k+1 well. Hence by the principle of mathematical induction
Vt
||we|| S C.p
Lemma 10. The norm of target average reward estimator Pe is bounded > 0 || S C, + 2C,..
Here, Cpp the upper bound on critic parameter we (Algorithm 2 step 8), C2 is the upper bound on rewards (Assumption 5).
36

---

Under review as a conference paper at ICLR 2023
Proof. For t=1:
P1 = (1 80 + 90P1
| _ (1 Bo)l + Bollp1ll
| & (1 Bo)(C, + 2Cw Bo(C, + 20w)
(Assumption 11
|il S C, nC,
The bound hold for t=1. Let the bound hold for = k. We will prove that the bound will also hold for k+1
Pk+1 3x)px 3&PR+1
/b++1| $ (1 Fx + 3x
|p++||| (1 (C, + 2...) + Ba(C, 2Cw)) (Assumption
| S C. + 20
The bound hold for = k+1 as well. Hence by the principle mathematical induction :
Vt > 0 l| S C, + 2C
Lemma 11. The A(0) matrix defined below negative definite for all values 0 (0 the policy parameter).
A(O) f f (T))(( (s))
(s)) 171)
Vx x AT - >> 0
y is the 12-reuularisation coefficient from Algorithm 2 and > All proof below.
maz where Nali is defined in the
Proof. Let:
A' - dd (())((())) ("((sss) o A(O) +
(A.27)
Here, 1) is the 12-regularization coefficient from Algorithm 2
x A')(0) =xT A'(O)) + A'(0)
- Amaz (0)
A'(O)T + A'
Here.
is symmetric matrix and Aman (0) is the maximum eigen value of the
2 T' + A((0)
Using Aall from Assumption 13:
2
x7 A0)x < X olt ||=||
x (A'(0) Ql)x x 5 all
1/]12111
x A(0)z & (Noll 1)|1=11 (using A.37
Here, if we take 17 Xall then can set À 17 xall
Yr x A(0)x < -111211, A>0
37

---

Under review as a conference paper at ICLR 2023
()))) Lemma 12. Let 01 and fg be the policy parameter for n' and respectively. d (:) and d' (-) be the stationary state distribution for n' and a respectively. Here, Drv denotes the total variation distance between two probability distribution function. We have:
/ ldt (8) d' (s) ds = 2Drv (d o Lall01 82ll
Here, La = 2m+ (flog, a a1 1/K)Lr. Le is the Lipchitz constant for the transition probability density fianction (Assumption state space.
is the dimension of 9 Constants a and k. are from Assumption 2
Proof.
(s) - 2dr (d")""")))""""""")""r" 2D22 (p1,
f fI0
Let Hi and #2 be the stationary state probability measure for n' and respectively. Then have:
du1 = d=' (s) du2 = d= (s) ds
Using the result of Theorem 3.1 of Mitrophanov (2005):
(D 12) s 2(1lgg a -1 + I| K2ll
(A.28)
where K2 and K2 are probability transition kernel for markov chain induced by policy x' and m
From equation A.28
||1 Kell sup 11 lrv=l / ((ds))()((1s))) - Ke(-1s))
11 I 9(d))(( k2(-1s))llrv s sup
// (())(K) (3)dsss)))(ss)))(((a)a))
iis /// f(s')(P' (8'1s) (s'(s)s) p (s
sup
// | 1(F P
sup iiis
PT PT
s L.|101 - 021l / / g(ds) / ds'
2" 11 62ll
Ki K2ll S 2mh Le 021l
(A.29)
From equation A.28 and equation A.29
f 1dt (s) d'((s) ds 2D (d' dd'') <<>> 2 ((o=1 a a1 1 Lol10 - 0z
La 10 - 021l
38

---

Under review as a conference paper at ICLR 2023
Lemma 13. The optimal critic parameter w according to compatible function approximation Lemma ( is bounded by constant Cwz.
|| & Ow;
Proof. From Lemma
/ d=
Vop(T)
(F)) (o
([ ds
(IVon(s. 0))
Here,
Ho =
Vop(T)) Haw,
Wº = Hp Vep(TT
|| < |H4 [[]((l]]
By using Assumption 14
the lower bound minimum eigenvalue of Ha for all 0 is Xini and using
Assumption 6 and
La Cw; X
|| S
Lemma 14. The average reward performance metric, defined in ((=)(o(0)) is Lipchitz continuous wrl to the policy (actor) parameter 0.
Ilp(0,) - p(82)ll s 1, 021l
Proof. Let and Og be the policy parameters of policy n' and n.
[lp(8)) p(f2)l ||((TT) p(T)I1
= 1| | o' (s) (s) / d d'((s) (s) dsll
< |1 (dr (x) (s)) (s) dall + || d'ss)(( -s)-1" (s)) dsll
s Lal 01 B2ll (Lemma
+ Lr 02ll (Assumption 10
< (Ia + [, 02ll 1.p 021 (Ia + I,p = I.p)
Lemma 15. The optimal critic parameter w(O.)* as a function of actor parameter 6g is Lipchitz continuous with constant Lv off off-policy case. Note: wi w(O:)" μ is the behaviour policy.
|! witil Tu 0.l1
39

---

Under review as a conference paper at ICLR 2023
Proof. 17 is the 12-rgularisation coefficient from Algorithm and X Xmaz. where X is defined in Lemma 16 Because of carefully setting the value of 77 A(O)) is negative definite. Thus, for on-policy (D()) with 12regularization and target estimators, the following condition holds true for optimal critic parameter wt::
((( (s) (6") (s)) n/)w;]
6(0,) = - 11)
A(O,) = (s) (s))
:. b(O)) + A(0,), = = w = - A(00)-
Expectation above is with respect stationary state distribution d' of policy μ.. Please note the abuse of notation here, A(0,) is actually same as A (0,) of Lemma 16
|| WT w1+1l || ||A(0.) - ((0)) A(0(+1) b(0++1)ll 6(08+12))
< [|A(0))) (00) A(0c+1)- + +((0++1)~b000, - A(0++))-
- [|A(0)) -1 A(0(+1) -11 [|6(,)] 1
+ 1|A(0++1) 11 [16(0,)
- (16(0)) 1(0++1))
(A.30)
From equation A.30
[|A(0.)
A(0,)- A(0))
(A.31)
< ||A(0)) (AA(0))~11111 ((.).) A(0++1)ll ||A(0++1)
From equation A.31
Here, n'' and represents the policy with parameter 0.+1 and 0, respectively and be the behaviour policy.
[|A(0.) - A(0++1)ll S =1 dF) (1)) (*(((11)))) o (s)) 1/1) ds
(s)) f (M(11))0)))))) - n!) dsll
$ ( (S) (1(( ds
ff (
1
$ f (1 (') ())))
(6)) dsll 2
(A.32)
From equation A.32
40

---

Under review as a conference paper at ICLR 2023
I:
f d' (s)(0= (0) P"(''l))0" (6) dd (0())000) ("(('ss)0"(s)) ds d) ds|l
3 11 1 (d) ((()) P"(311)0 ("(d))))()))))))) (6')do) dall
+11 d'(s)( --0 ( P*(S'(s)0 ds) dsll
+ f [d(()) (s'(ss
P" PP (s') ds da|l +1l ʃ d'(s)) ("(('ls)(0='(( 0- ((')) d ds
< L0l10/+1 0.ll
(Assumption 8
+ 0011 0el
(Assumption 8
f d' (s) (6)( pM (s'(ss)@ (s)) ds - ff d=(s)(0 (=(("ls)00"s") ds') ds|l
$ 200110141 - 0cll
(A.33)
From equation A.32
f (()(() / (5)((())) (a) (s)) ds|l
$ d's))( 0² (x))(( ds|
(A.34)
+11 (s)(
(s)(d (s)
0" (s)) dsll
< 2T. 2T..1 - Oell
Using equation A.33
and equation A.34 in equation A.32
[[A())) - A(0+t))ll S (4Ts + 1.)10041 - -0ell
(A.35)
From equation A.30
41

---

Under review as a conference paper at ICLR 2023
2:
[lb(0.) b(0++1)ll 111 / d' (PA (6) f ('(s)((()))
pi) (s) ds
< 11 d (+)) (s) - (3))) (
dall
+11 11 / (3))) (s) ( (s)
$11 / (8)) - Rd (s)) (s)
+11 / (s) (8) ds)
ds|
+11 / (1)(401 - 0=)0= (8) ds|
+ 11 / (')))i( (s) 0² (s) dsl
S 00 - 0:ll (Assumption 5
Op 0ell
(Lemmal 14
CoLo |1:411 0ell
(Assumption
[bb(0,) b(0 - (2C,L + Lp)110++1 -0el
(A.36)
Using equation A.31
equation A.35 and equation A.36 equation /A.30
||00 -17--141 w141ll S - ([(00)) |1000
(16(,)) - ((0+1))
$ -|A0 [|4(0=+1~)111 116(0))1
A(#++))l
-
+ [[A((+=))-|| b(0+
$ 4[01[A(0))-11]]((0++==11111 [[(())] |/ 0.ll
(2C, - A(0+) | 0:11
Note:
[[b(:)]] = fI (s) (z) (s)) ds|l S C. (Assumption) 5
Let Amin is the lower bound on eigen values of A()) for all 0.
C4LL)
5. "|/] wit1 <
110 Hell
X2 min
(2C, Loo + Lop) |10c+1 Gell
+
Amin
< L. Le Dell
where,
4Cp
C.
L. =
+
2 Amin
Lemma 16. The A (0) matrix defined below is negative definite for all values of 0 (0 is the policy parameter). 0P is the policy parameter for behaviour policy p.
A / dd (s)( (=
- (s)) -n1) ds
42

---

Under review as a conference paper at ICLR 2023
Va x 50)x X> 0
n is the 12-regularisation coefficient from Algorithm and rj > Xmazi where Xmaz is defined in the proof below.
Proof. Let:
(05r(00) (0)== (0)=
-f)) Ab,,(0) +nl (A.37)
Here, 17 is the 12-regularization coefficient from Algorithm 2
x A (00xz = xT (Aots (0)T + A 40rr((0)
)0x (00)
S Xman (0)1|=||2
A (0)T + A (0rr((0)) is symmetric matrix and Xmaz (0) is the maximum eigen value of
Here,
2
Al off (0)T (0)T + A' A
the
Using xail from Assumption 15
2
xJ '(0) S xmaz ||=1|
2T (A (6) n/)x S (x 17) |= x (0)x : S (x - 1 (using A.37
Here, if we take 7) Xmax then can set =1 Xmax-
Yx I A (0) s -A||=|12 A>0
Let the cumulative error of off-policy actor be Et-1 El(Vop(0:))1 and cumulative error of critic be ET-1 Elj Awel1. 6g and w. are the actor and linear critic parameter at time t. Au is the policy parameter for behavior policy μ. Bound on the cumulative error of off-policy actor with behaviour policy y is proven using cumulative error of critic as:
Lemma 17.
E V
Cr Cr + 60*
Σ
E E|Aww
+ 6C 4
c
T
C
M
t=0
1=0
+ Cb T-
Z T-1 T-v +
Ell0a - 8¹112
Here, C, is the upper bound on rewards (Assumption 3 Cz.. v are constants used for step size Tt. (Assumption [V)z( S CT (Assumption 7 Aut w. w r max; |! w.aal w is the optimal critic parameter according to Lemme w. is the optimal parameters given by TD(O) algorithm corresponding to policy parameter U. Constant Cwz is defined in Lemma 13 La is the coefficient used in smoothness condition of the non convex function p(0). Constant Ge is defined in Lemma 7 is the size of batch of samples used to update parameters. 2 C([log, a + 1/K) L with L1 being the Lipchitz constant for the transition probability density function (Assumption 9.. Constants a and K are from Assumption 2 m is the dimension of
state space, and C max, V. VoQaigf(8 (1)0)aannt a))a=n(s) V Fm (8, 0)||-
43

---

Under review as a conference paper at ICLR 2023
Proof.
T-1 -
B| (
E| Vop(O)) Vop(o.) Vop(0.)11
T
B1 Vop(O.)] + + Σ
Bl| (op(o.) Vop(0.)]1
T
Using Theorem and Lemma
E E (0))))) 4 Cr + 60
T-1
4 + 602 +
M %
Cg
C. Ch.
2 T-1
+ 2
T- +
Σ
El10" 1-12
--
T t=0
Theorem 4. The off-policy average reward actor critic algoritium (Algorithm 3) with behavior policy μ obtains an e-accurate optimal point with sample complexity of 9 2.5). Here 9, refers to the behavior policy parameter and 0, refers to the target or current policy parameter. We obtain
Bo (0001 ( (010
min 0StST-1
(T...)
56+ + O(W3)
where Wo max 100, 0rll-
Proof. Lemma and Lemma 5 will hold in the case of off-policy update. Lemma 4 will require Lemma 15 instead of Lemma 6
Using Lemma 4 and Lemma 5 and using the procedure followed in Theorem to obtain asymptotic notations, we have:
Σ E A
+ +0
+ +0 (2((-0)) + +0(1)
1
(A.38)
T
T1-o
Tia
t
Using Lemma and equation A.38
1
min 0S1ST-1
E Vop(0)) = 0 T1-v
+ +
+
0
+ +0
T"
T-
T
+ 0 T2(u-o)
+ 0(1)
Z
E
A
8
T
t=0
By setting 3/5 and 2//5, we obtain:
44

---

Under review as a conference paper at ICLR 2023
2 T-1
min 05157-1
V (ep( 0
+ 0(1 +
Σ
E110" 1-1
70.4
T
1=0
+ +(11) (11)+2M 2N
70.4
+ 01) +
7
Further,
<.
70.4
Hence, the sample complexity of off-policy average reward actor-critic algorithm is S2(E -25)).
A.2 BOUNDEDNESS CRITIC PARAMETER
In this section prove the critic parameter used in Algorithm
2 and 3 is bounded even without is a compact convex set.
using projection operator c. defined as I'c,, R² + B, where B C IR
Let policy is parameterized by 0.
For simplicity of proof we are assuming the batch size M to be 1. Critic parameter wy I s (s) E I and Pt is scalar. Let the update rules used for critic parameter and average reward estimator be as follows:
To) ))))))(())))))))))))())) - crper W++1 = Wi Ot (st) - Pt 0- (5() (st)
P+11 = Pt + at R (st) - Pr + oz (s)) Te - o (31s;)
(A.39)
W++1 T. B:(ww+11 1(+1)
Pit1 = Pt + (e(p11 - P(t1)
Let us define [wa P.]T and 2, (w, TelT. 0 is vector in R and To is an identity matrix in R(++1)x(k+)) with In [k] 0 (assuming indexing starts from 0).
W++1
Wt Pt.
15 (8x)
tF (0)))) (s{)) (5( o (st)
(8t)
Wr
=
+ ai
RdT (st)
+
Pc+1
-c
10= (s=))(ossss)))))) (St)T
0
we
1/10
[w:
(A.40)
1
Pt
Pt.
W141
We
w1++1
W//
)
+ 3e
=
Po+1
Pr.
Pc+1
Pt
[st(
(=)(s)
-s)(ss)
Here, Rd (st)
(T(ss), (s)
and Bo(s:)
(s())) 07 (st)
0
Tot (8)))))))))))))) (st)T
0
2++1 = + ax RR (st) ) + As(s,, s)) (Bo(st) + +TTo))))) ž+1 = 2, + 3r (2++1 - 2,)
(A.41)
Now, we will use the extension of stability criteria for iterates given Borkar & Meyn (000) to two timescale stochastic approximation scheme (lakshminarayanan & Bhatnagar 2017 show the
45

---

Under review as a conference paper at ICLR 2023
boundedness of the critic parameter and average reward estimator together. Let write A.4 in the standard form of stochastic approximation scheme.
2++1 2t + az (h(22,, 2z) + Mi+1)
Let, Rg (st dsc. A (s)) Is PK (s(lss)))sss 8.) dsl det, BΦ Ig d= (s:) Here,
h(2,,2) 21) -/5 d' (s)) + -BB(s) nI) dsg
=Ry + AgE - (Bs n/)
M1+1 = (8)())) Ag(s;; 8,)2, (Bo(s)) + 71000= M(z1, zi)
E+1 = & + 3: (. x) + M2+ + c(n))
Here,
g 2) =\(z)) 2t
MHn =0
X(2) =BB + nTTo)) (Rg AgE,)
(n) = X(E)
X(z)) is the unique globally asymptotically stable equilibrium point of the ODE 1 used here has no relation to usage of X in any other section of the paper. Using Lemma of Chapter 6 of (Borkar 2009), we have Ze+1 X(x)) 0. Hence e(n) o(1). Therefore we can use the conclusion of Lakshminarayanan & Bhatnagar 2017).
h(=(t), 2). A
We will now satisfy condition A1 till condition A5 of (Lakshminarayanan & Bhatnagar 2017) prove the boundedness of the critic parameter:
Condition A1:
[1(2, 21) 1(22, 22)1 |A - 52) (Bs 1/00(21 z2)ll
< | 1 ||B + 7/ollll= - =2|
< max(1|All) [B 1//ol)) =ell +|||| 22ll)
[a] -2|l + ||||= zal) (L. max(1)Aplll BB + r7Tol1) (A.42)
Therefore, h(z, is Lipchitz continuous with constant 4n.
119(21, 21) ( Æ2)1 [I((B, + n/o 1) 22)1
[I((B, + Ab 1)ll(a E2ll Lgll31 - -2ll (Lg = II(BB, -/oo) I)II
(A.43)
Therefore, 0(2,2) 2) is Lipchitz continuous with constant Lg.
Using A.42 A.42 and A.43 condition Al is satisfied.
Condition A2: Let us define an increasing sequence of -ffilds {Fi} as {zm Em, M m: M m S t).
B[M [F] (s)) + As(s,, 5)) (Bo(se) + nTo h121, [.]
dt (st) (s.) + As s/) (Bo(se) + m)lo)2z) dsc h(z,, 2x)
0
46

---

Under review as a conference paper at ICLR 2023
E =0
Hence, {Mi} and {.M martingale difference sequence.
|| (()) Rsp) + (Ap(si, st) Ao)a (Bo(st) - (2( 12 <(([) R + (s st)) - Bs(ss)) - ki(1 + || + 11
Here, K1 max R (( # (B(((() and follows from Assumption 4 and
We have, || [3] < (1]|||==|] and 1 < K2[1+||<|| 2
K2 be any positive constant. Hence condition A2 is satisfied.
Condition A3:
Co We have, Σ, at = Ee (1+2)
oc, 3. = E. (1+2) oc and +
E. (1 (IttF= on step sizes.
) (I+1]=]
C3 )²) < cc. We can carefully set the value of a and u to satisfy the conditions
Condition A4:
h2(2, = Mcz,cz)
R5. ccAae - c(Bs + nTTo)
hc(2,2)=
R% + cA -c(Bs + +Too=z
lim hc(2,2)
lim G-
00000
= -Ag (B + n10)zz
Let us define (2,, 2)) = Agã - (B, + 1,) The ODE =(1) = 11x (z(1),z) has unique
globally asymptotically stable equilibrium point (z) = (B, + nToo) -1 Ag (Bs + m/o) is
positive definite matrix. Let C Is d= (st)Ø² (st)Ø" (8t) ds.
Co + ml O)
0
BB + nTo
1 07 [w]
Co nl
TwT
p|
=TC(C' + nI)w + p²
0r
1
p
If in is strictly greater than negative of the minimum eigenvalue of C then,
0
Co
nd
0
w
TwT
pl
0
OT
1
P
(A.44)
ww
TwT
p) [B
nto]
p
Hence, for 7) (Cm)(CCo) 0, Bg To is positive definite matrix. Therefore, the ODE a(t) == hoo (2(t), 2) has unique globally asymptotically stable equilibrium point (3) and Aoe (0) Condition A4 is satisfied.
Condition A5:
47

---

Under review as a conference paper at ICLR 2023
9.(3) = g(cAoo (2), cτ)
9c(3) (Bg + n/1) 1111))))(( (18 + cA.Z) -c
C
(A.45)
(Be + mlo))
(R5 + +CA22) cz
lim (c(3)
lim -00
0-000
c
= (Bs + n10) -1 AAZ =
Let us define Soo == ((B, +11oo= A₂. f)a. The ODE a(1) - 900 (#(()) has origin as its unique l globally asymptotically stable equilibrium if (Bg + mHo) -LA, is positive definite matrix.
||- refers to L2-norm. A, are the eigenvalues of the matrix Cz. Let assume the following:
1 )) 1) = 1I + 1110)=111 -1 |
max(1, max( 8
A; +
11 +
A <
||x||][[B, + 140) -111 |=|| < ||0||
(A.46)
|| + 1To) - Aaz| ||0||
xT (B, + - < |
xT(I - (Be 1/16 Ag)x > 0
Hence, if max(1, (xxx((x)11)) TT then 7 7- (Bg -1 is positive definite matrix. There- fore, the ODE 5(() 9ox (E()) has origin as its unique globally asymptotically stable. Condition A5 satisfied.
Let us the consider the ODE =tt) = h(2(t), Here, M(=(t), z) = Rg + Agz- - (B, + T) 2 As earlier, for 11 Amii (Ca) > 0, B, + n/oo is positive definite matrix. Therefore, the ODE ²(t) = h( h(2(t), 2) has a unique globally asymptotically stable equilibrium point X(2) (Bo - (To))- Rg + A.
Conditions Al to A5 are satisfied, therefore sup, || < oo, which implies iterates are bounded. Hence critic parameter W; is bounded.
48

---

Under review as a conference paper at ICLR 2023
B ALGORITHM AND HYPERPARAMETERS
B.1 (OFF-POLICY) ARO-DDPG PRACTICAL ALGORITHM
Algorithm (Off-Policy) ARO-DDPG Practical Algorithm
Initialize actor parameter and critic parameters W1, Wt Initiliie actor target parameter + B Initialize critic target parameters w1 Wi, W12 W2- Initialize average reward parameter p.
Initialize target average reward parameter - p. Initialize Replay buffer ()
Sy env.reset()
2: while < total steps do
3: 0, = ((+) + e {E denotes the noise]
4: S1+1 P(-|st, a,) and
R(s, ax)
5: Store {st, a2, $1+1} in the Replay Buffer
6: if % evel_freq == 0 then
7:
Evaluate(agent)
8: end if
9:
if % Prtticuupdat, freq = 0 then
Update critic according end if
11:
if % actor cittorrupdtt___e freq
then
13:
Update actor according to Update target estimators according to (30 end if
15:
16:
if $1+11 terminal then
17:
env.reset))
18: else
19: S: st+1
20:
end if
21:
end while
B.2 FINITE TIME ANALYSIS ALGORIIHM
Here present the algorithm with linear function approximator for which finite time analysis was done. B, denotes the batch of tuple of the form {8;, a; $ sampled from the buffer at timestep t. Ic., is a projection operator defined as Ic... : R - B, where B(c IR) is a compact convex set. Here, the critic parameter R
49

---

Under review as a conference paper at ICLR 2023
Algorithm 2 On-policy AR-DPG with Linear FA
Initialize actor parameter and critic parameters Initialize actor target parameter 0 - 0. Initialize critic target parameters w - I.intiillie average reward parameter p
Initialize target average reward parameter p + Initialize buffer = {}
I: t t= 0, 80 env.reset))
2: while total steps do
3: = (s,) + {e is the noise)
4: S1+1 (())s,,a,) az) and rt = R(s;,ai at)
5: Store {st,, (1+1),111))+.. in the Buffer
6: if % critic_update site__udate__eeee = then
7:
Sample B, {5, ai $ from the Replay Buffer
8:
W++1 Icc
W0z + M
at M-
DM11
[ (s:) Pr 0z (s,) (s)) 10f1----68 (s:) (st) au7ww
at M- ( Ps + 0= (5{) - (ss
9:
Pt-1 P +
M
10:
W++1 = Wr + Be(wr+1 - W++1)
Pr-1 P: (p -Pt+))
12:
O1+1 0: + Ht
M Li=o VaQ (88, a) (s=)( VoT(8:)
13:
buffer ()
end if
15:
if
$1+1 is terminal then
16: 8; = env.reset()
17:
else
18:
= 81+1
19:
end if
20:
end while
Algorithm 3 Off-policy AR-DPG with Linear FA Initialize actor parameter and critic parameters w Initialize actor target parameter > 8 and Initialize critic target parameters Initialize average reward parameter and Initialize target average reward parameter p - p is the behavior policy Initialize Replay buffer = (}
1: t = 0, 80 = env.reset()
2: while < total steps do
3: a; = (((s) + {E is the noise]
4: $1+1 P(-Ist, a:) and
R(s,, a.)
5: Store {st, at $141 } in the Replay Buffer
6: Sample R, = (si, 04,4, /1--1 from the Replay Buffer
W++1 = Ie.. w. + att M- (R. Pe + ot (s() - 6" (s (5.)) aypurr)
7:
M
at ΣMO1 (s,(s)) + (5)) 6= (s:)
8:
Pt+1 Pt- M
9:
1+ = W; + B [W W141)
P P. Be(Pt+1 - -P++1)
O+4 + Nt EM- VaQii (8ts a)l==((ss))) VOT(s:)
M
12:
if 8t411 is terminal then
13:
S; env.reset()
14: else
15:
= 88+1
16: end if
17:
end while
50

---

Under review as a conference paper at ICLR 2023
B.3 HYPERPARAMETERS
Hyperparameter
Value
Buffer Size
le6
Total Environment Steps
le6
Batch size
256
Evaluation Frequency
5000
Training Episode Length
1000
Evaluation Episode Length
10000
Activation Function
ReLU
Learning rate Actor
3e-4
Learning rate Critic
3e-4
Learning rate Average reward parameter
3e-4
No. of Hidden Layers
2
No. of Nodes in Hidden Layer
128
Update frequency
10 steps
No. of Critic updates
10
No. of Actor updates
5
Polyak averaging constant
0.995
51


Reviews:
[{"review_id": "rSsfaqMCdG", "reviewer": "Reviewer_Fu5H", "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": "This paper extends the deterministic policy gradient algorithm to the average reward case and introduces an average reward version of DDPG. Finite-time analysis of linear function approximator version of the algorithm is also shown for both the on-policy and off-policy case. Empirically, the new algorithm is shown to outperform other on-policy average reward algorithms.", "summary_of_the_review": "Overall, I think this paper does make an important contribution to the field but some important issues still need to be addressed, especially in the experiment section. As of now I am setting my score to borderline reject but I am open to changing my score upon a satisfactory response from the authors. I look forward to hearing back from the authors.", "strength_and_weaknesses": "Average-reward RL has only started gaining attention in the last 2-3 years and this work fills an important gap in that it provides a practical off-policy deep reinforcement learning algorithm that shows potential in high dimensional continuing control tasks. My detailed comments are below:\n- The methods introduced in the paper can be seen as an average-reward extension to [1] and [2]. Intuitively, especially for off-policy settings, the deterministic policy gradient approach is probably easier to use and analyze. I also liked Section 3.4 where the authors provided comparisons to alternatives.\n- One comment/question I have is regarding the step size. One thing that has always been tricky with average reward algorithm is the choice of learning rate since we need both the Q function and the average reward rho converge, this essentially gives us a multi-time scale problem which are notoriously hard to tune and can have complicated requirements in terms of their step size choice (an example is the proof for differential Q learning found in [3]. I was also quite surprised that in the practical algorithm, the authors used the same step size for the actor, critic, and average reward and the resulting algorithm actually works quite well.\n- For the experiments, it seems that in the original papers for the two baselines used in the paper (ATRPO, PPO), both papers used OpenAI gym instead of DM control for their experimentation work. So it is unclear whether the original implementation/settings for the baselines would work just as well on DM control. I wonder if the authors accounted for this in their experiment work.\n- Also concerning the choice of baselines, I wonder how your algorithm performs against discounted DDPG/SAC? That is, empirically, is there any evidence that the average reward algorithm outperforms the discounted version? Since it has been pretty well-known that off-policy algorithms generally perform better in terms of sample efficiency compared to on-policy algorithms, the results in the experiments are not surprising. I’m curious how your algorithm performs when compared to other off-policy methods.\n- Another question I have concerning the experiments is the update frequency of the actor/critic/average reward value. You mentioned in the experiment section that you update the critic network with more frequency, however in the hyperparameter section the update frequency is listed as 10, is this the frequency for the actor or critic or the average reward? More importantly, could you comment on the different update frequency since this issue did not seem to come up in the theoretical analysis. Also related to my previous point concerning step sizes, some comments on the update frequency of the average reward would be much appreciated.\n\n[1] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin A. Riedmiller. Deterministic Policy Gradient Algorithms. ICML 2014\n\n[2] Thomas Degris, Martha White, and Richard S. Sutton. Linear Off-policy Actor-Critic. ICML 2012\n\n[3] Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and Planning in Average-Reward Markov Decision Processes. ICML 2021\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cFOBWF21CTT", "reviewer": "Reviewer_SgUA", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper develops both on-policy and off-policy deterministic policy gradient theorems under the average reward setting; here, the off-policy theorem only gives an approximated form of the gradient but shows the error between the approximated gradient and the true gradient is bounded. Based on the theorems, the paper proposes an on-policy average reward policy gradient algorithm which defeats the other two average reward policy gradient algorithms in both learning speed and final performance. Meanwhile, the paper derives upper bounds for the smallest expected square norm of the gradients in linear on-policy and off-policy algorithms, respectively.", "summary_of_the_review": "The paper may not be ready for publication and needs rewriting.", "strength_and_weaknesses": "Strength: The paper makes a good progression from theory to practice. It has enough novel contributions and provides convincing experiment results.\n\nWeakness: The paper is not clearly written and has a few mismatched mathematical notations. Furthermore, the theorems of non-asymptotic bounds have unstated assumptions and conditions. The proof is also hard to follow. Also, the bounds do not directly describe the properties of algorithms; the regret bound or the bound on the optimality of the policy would be better.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bepS3r5mU1", "reviewer": "Reviewer_eTNK", "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": "The paper presents deterministic policy gradient theorems (both on- and off-policy) for the average reward setting. The paper then presents an Average Reward actor-critic algorithm based on DDPG (ARO-DDPG). A finite-sample analysis is conducted, and the algorithm is demonstrated empirically on several environments.", "summary_of_the_review": "Despite liking the proposed algorithm, I must recommend rejection due to the concerns listed above, the experiments in particular. If the authors can address my concerns satisfactorily, I would be willing to recommend acceptance.\n\n**Update:** The authors have addressed some—but not all—of my concerns, and I am increasing my score and recommendation in response.", "strength_and_weaknesses": "**Strengths:**\n+ The proposed approximate off-policy policy gradient for continuous states and deterministic policies is an intriguing solution to a difficult problem.\n+ The paper is written fairly clearly.\n+ The proposed algorithm performs well in the experiments.\n\n**Potential Weaknesses/Questions/Things to improve:**\n- Spelling mistake in the title of the paper (\"DETERMINSITIC\").\n- \"In the case of recurrent Markov Decision Processes (MDPs), average reward happens to be the most selective optimization criterion.\" What does \"most selective\" mean in this sentence?\n- \"Moreover, an obvious discrepancy between the objective function and the evaluation metric, that exists for discounted reward setting, is resolved by opting for the average reward criterion.\" What discrepancy is the paper referring to?\n- It's generally good to comment on the assumptions made just after making them. Are they necessary or just for convenience? If necessary, why? For example, Assumption 3 can always be made true by normalizing the feature vectors, and is therefore just for convenience, whereas Assumption 1 seems necessary for the steady-state visit distribution to be well-defined.\n- \"$P_t^\\pi$ is the state distribution at instant t given by (9).\" This should say Equation 10, right?\n- Is Equation 9 correct? I've only seen the discounted state visit distribution defined as $\\frac{1}{\\sum_{t=0}^\\infty \\gamma^t} \\sum_{t=0}^\\infty \\gamma^t P^\\pi_t(s) = (1-\\gamma) \\sum_{t=0}^\\infty \\gamma^t P^\\pi_t(s)$, because the denominator is a geometric series that converges to $\\frac{1}{1-\\gamma}$. Where did the $\\frac{1}{\\gamma}$ term come from?\n- It would be good to comment further on the extra error term $\\mathcal{O}(N_\\theta^2)$ due to off-policy sampling. What situations could cause it to be small or large? Does it increase over time as the learned target policy deviates more and more from the behaviour policy?\n- What are the shaded regions in the plots? Confidence intervals?\n- The plots do not use colourblind-friendly colours. Consider removing the legend and instead using labels and arrows to show which line corresponds to each algorithm. Doing so would greatly reduce the reliance on colour to determine the performance of each algorithm.\n- The paper only reports experiment hyper-parameters, but does not describe how they were chosen. Which values were checked for each of the methods? Do all of the methods use the same hyper-parameter settings (this is not good)? Are the chosen hyper-parameters representative of algorithm performance? Without conducting a grid search for each method, it's difficult to draw conclusions about the relative performance of each algorithm, and the experiments are more like demonstrations than rigorous comparisons.\n\n**Minor comments/suggestions:**\n- There seems to be a lot of vertical space near the equations on pages 2 and 3. Is \"\\allowdisplaybreaks[4]\" in the preamble of the LaTeX file?\n- It would be clearer to move equations 24-32 inside of Algorithm 1 instead of referring to them, and would save a lot of space.\n- It would be good to clarify that the definition of the policy in Section 2 is for deterministic policies.\n- It looks like $\\rho^\\pi(s)$ is used for discounted state visit distribution and $\\rho(\\pi)$ is used for average reward. Using $\\rho$ for both makes the notation more confusing for the reader than it needs to be.\n- The policy gradient theorem from Degris et al. (2012) is only valid for the tabular case. When using function approximation, the true off-policy policy gradient is given by Imani et al. (2018). However, the emphatic weightings rely on importance sampling, which as stated in Section 3.4 will not work with deterministic policies in continuous state spaces. The proposed approximate off-policy policy gradient expression is an interesting alternative.\n\n**References:**\n- Imani, E., Graves, E., & White, M. (2018). An off-policy policy gradient theorem using emphatic weightings. Advances in Neural Information Processing Systems, 31.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_d3tRqOMRuS", "reviewer": "Reviewer_nHrk", "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": "The paper introduces an off-policy deterministic policy gradient for the average reward setting. The authors follow a standard approach, first deriving the policy gradient, then finding a class of compatible value function approximators, and finally providing a finite time analysis for the on-policy and off-policy cases. Alternative approaches for deriving the off-policy policy gradient are proposed, with an explanation of why they could be less appealing to follow. Finally, an experimental comparison with existing on-policy actor-critic algorithms based on the average reward shows that the proposed method performs well. This confirms that off-policy algorithms might be more sample efficient than on-policy algorithms also in the average reward setting.", "summary_of_the_review": "The paper introduces an average reward off-policy deterministic policy gradient algorithm. While the theory is sound and significant, the authors should improve the quality of the writing in order to explain better the importance of their results. Some concerns about the experiments need to be addressed before acceptance.\n\n-----------------------------------\nEdit: Updating my score after author's response", "strength_and_weaknesses": "\nStrengths:\n\n- The average reward problem is pretty unexplored, and to my knowledge this is the first work properly formalizing this setting for deterministic policies\n- The theoretical results mostly follow in a straightforward way from previous work, and most of them are exactly how one would expect them. Nevertheless, it is important to have a good reference for such results, like it is in this paper.\n- All the assumptions are well stated before each main result\n\n\nWeaknesses:\n\n- (major) The paper would benefit from some rewriting. The theory sometimes lacks a proper explanation. For instance, the results of Theorem 3 and 4 are not even commented on. Why should we care about these results? Are they surprising? For a theoretical paper like this, it is important to convey the result to the reader properly.\n- Parts of the paper could be better organized. Sometimes definitions appear a bit after quantities are used for the first time (See Lemma 1 and then Eq. 5). The long list of equations (24)->(32) should be rewritten in a more organized way.\n\n- Target estimators in Eq. 24 appear without any justification\n\n- In the experimental results the authors reimplemented the baselines and used the original hyperparameters reported in the baseline papers. This seems pretty unfair, as it is well-known that slightly different implementations can have very different experimental results. Since the authors tuned their hyperparameters, but not the baselines, how can we consider the experiments fair?\n\nMinor:\n\n- There are too many repetitions of \"came up with\" throughout the paper\n- In Eq 12 should there be $d^{\\mu}$ instead of $\\rho^{\\pi}$?\n\nOther questions:\n\n- Some proofs in the Appendix use a projector operator. Is the operator used in the implementation?\n- Could the authors clarify why Eq. 21 is not a good off-policy objective? It was not clear to me from the explanation given in the paper.\n- Assumption 2 is stated without comments. Could the authors explain it in the paper? \n- What happens if the training phase is 1000 and the evaluation phase is 1000? How does the proposed method compare to the baseline in this case?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SwkBGxoQpGQ", "reviewer": "Reviewer_xGda", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "The paper extends the canonical deterministic policy gradient from the discounted setting to the average reward setting. Finite sample analysis is provided.", "summary_of_the_review": "See above", "strength_and_weaknesses": "Strength:\nThe idea is straightforward and seems doable\n\nWeaknesses:\nThe presentation is very confusing so I cannot evaluate the correctness of the proofs at all. \nFor example, in Algorithm 2, the critic is a state value function. However, in the update of the actor, it uses the **ground truth** action value function. How can we get the ground truth action value function? Moreover, in line 8 in Algorithm 2, there is projection in updating the critic. In the analysis of the critic, the first equation in page 19, the projection, however, disappears. \n\nOverall, this work combines several existing ideas and I generally believe such a combination should work. But there are many details that need to be taken care of, which the authors fail. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject