Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms
Authors: Yashaswini Murthy
Mehrdad Moharrami
R. Srikant
Venue: NeurIPS 2023 poster (2023)
Keywords: Average Reward MDPs
Reinforcement Learning Theory
Approximate Policy Iteration
Policy Based Methods
Performance Bounds
TL;DR: Performance bounds of RL algorithms which can be cast as various approximate policy iteration frameworks in the context of average reward MDPs.

Abstract: Many policy-based reinforcement learning (RL) algorithms can be viewed as instantiations of approximate policy iteration (PI), i.e., where policy improvement and policy evaluation are both performed approximately. In applications where the average reward objective is the meaningful performance metric, often discounted reward formulations are used with the discount factor being close to $1,$ which is equivalent to making the expected horizon very large. However, the corresponding theoretical bounds for error performance scale with the square of the horizon. Thus, even after dividing the total reward by the length of the horizon, the corresponding performance bounds for average reward problems go to infinity. Therefore, an open problem has been to obtain meaningful performance bounds for approximate PI and RL algorithms for the average-reward setting.  In this paper, we solve this open problem by obtaining the first non-trivial finite time error bounds for average-reward MDPs which go to zero in the limit as policy evaluation and policy improvement errors go to zero.

Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms
Yashaswini Murthy
Mehrdad Moharrami
Electrical and Computer Engineering
Electrical and Computer Engineering University of Illinois Urbana- Trbana-Champaige
University of Illinois Oabana-Champaighh
Urbana, IL 61801 ymurthy2@illinois... edu
Urbana, IL 61801
@ccharmi@@llinee edu
R. Srikant
Electrical and Computer Engineering University Illinois Chaamaagn
Urbana, IL 61801 rsrikant@illing www.etiiiiiiiiiiiiiii
Abstract
Many policy-based reinforcement learning (RL) algorithms can be viewed as instantiations of approximate policy iteration (PI), i.e., where policy improvement and policy evaluation are both performed approximately. In applications where the average reward objective is the meaningful performance metric. discounted reward formulations are often used with the discount factor being close to 1, which is equivalent to making the expected horizon very large. However, the corresponding theoretical bounds for error performance scale with the square of the horizon. Thus, even after dividing the total reward by the length of the horizon, the corresponding performance bounds for average reward problems go infinity. Therefore, an open problem has been to obtain meaningful performance bounds for approximate PI and RL algorithms for the average-reward setting, In this paper, solve this open problem by obtaining the first finite-time error bounds for average-reward MDPs, and show that the asymptotic error goes to zero in the limit as policy evaluation and policy improvement errors go to zero.
Introduction
Reinforcement Learning algorithms can broadly classified into value-based methods and policy- based methods. In the case of discounted-rec reward Markov Decision Processes (MDPs), value-based methods such Q-learning (WD92 Ts994
MJS93 SBI8 BT%)), fitted value iteration [MS08] and target network Q-learning [CCM22 can be viewed as approximately solving the fixed point of the Bellman optimality equation find the value function and an approximately optimal control policy. In other words value iteration is approximately implemented for discounted reward MDPs policy-gradien methods [2KLM2I], a gradient step is used to improve the policy, somewhat similar to the policy improvement step in policy iteration for discounted-reward MDPs. recent paper (CM22), it has been shown that many policy-based methods for discounted- reward MDPs can be viewed as special cases of approximate policy iteration. The classical results on approximate policy iteration [BT%6] assume that the error in the policy evaluation and improvement steps are constant, independent of the iteration. The key idea in (CM22) is to show that a simple modification of the proof in [BT%) can be used to allow for iteration- -ereadeenndeeedeentt policy evaluation and improvement errors, which is then used to make the connection to policy- -based methods. Our
[erll [Brr12 2 [Put14].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

goal in this paper is to derive similar results for average-reward problems. Average-reward problems [ВВВО WNS2I ZWSW2I Mah96 YB09 Gos04 Sin94] are, in some sense, harder to study than their discounted- reward counterparts. We now discuss why this is so by recalling the error bounds for discounted-rrwarr problems and examining them in an appropriate limit to study their applicability to average-reward problems.
The fundamental result on approximate policy iteration for discounted reward MDPs which allows the connection to policy-based methods is the following (BT96]:
lip |1 J 8--000
1o00 I H2 + 2ao),
where a is the discount factor, Ho 1/(L a), J is the optimal value function, Jug is the value function associated with the policy obtained after & itcrations of approximate policy iteration, e is the policy improvement eπrоr, and ò is the policy evaluation error. Thus, as e, + 0, recover the result that standard policy iteration converges. On the other hand, to understand whether the above bound is useful to study average-reward problems, we write Equation ①
1
lim sup
1pp, - J2 S Ha(e 208). k-+00 Ha
Under mild conditions [Berl] Ros14], it is well known that each element of the value function vector approaches the average-reward for each fixed policy and for the optimal policy, the limit -> Hence, the left-hand side of the above equation is an approximation to the error in approximate policy iteration for average-reward MDPs; the right-hand side which gives an upper bound on this error blows up to infinity, i.e., when - 1. Thus, unlike in the discounted-reward case, the above bound fails to even recover the well-known convergence of standard policy iteration average-reward case in the limit e, 8 + 0 (since we have to let + before letting e, 8 - 0 However, mentioned in [T9,), is also well known that approximate policy iteration performs much better than the bound suggests. The main goal of our paper is to resolve this discrepancy between theory and practice.
1.1 Contributions
It is well known that the error bound for discounted-reward approximate policy iteration is tight for unichain MDPs [TT%)]. Thus, it is impossible to improve upon the bound in general. However, as will be explained in a later section, it is easy to convert most reasonable unichain MDPs to MDPs where every stationary policy results in an irreducible Markov chain with an arbitrarily small loss of reward. So the natural question to ask is whether the bound can be dramatically improved for MDPs where every stationary policy results in an irreducible Markov chain. To the best of our knowledge, no such bound was available in the prior literature.
Our main contributions are as follows:
Under the assumption that every stationary policy induces an irreducible Markov chain, we first perform a Schweitzer transformation of the MDP [Sch7]] and obtain finite-time error bounds for average-reward approximate policy iteration.
Using the above finite-time error bounds, we prove an error bound of the form
lim sup J J S f(c, R=
for average-reward approximate policy iteration for a function f such that f(e, + 0 in the limit as d + O. Note that this is in sharp contrast to the result that one can obtain from the discounted-reward analysis where the error bound blows up infinity when applied to discount factors approaching 1, which is the appropriate limit to convert discounted-reward problems to average- problems.
The main difficulty in obtaining the above bound when compared to the discounted- -eward case is the lack of infinity- -nom contraction property for the Bellman operator in the average- reward case. In most analysis of average-reward problems, this difficulty circumvented by the use of contaccont property [Put14]. However, the span contraction property is insufficient for our purpose and therefore, we use a technique due to [Vaw80] for the study of different algorithm called modified policy iteration in [Put14].

---

Next, we extend the above analysis to obtain Unite-iteration error bounds for the case where the policy evaluation and improvement errors can potentially vary from iteration iteration. Further, we allow these errors to be random (as would be the case, for example, when one uses TD learning for policy evaluation and soft policy improvement) and obtain expected error bounds on approximate policy iteration after a finite number of iterations.
Our eπrоr bounds are in form such that one can then apply them to many policy-based RL algorithms, i.e. we can simply plug in error bounds for specific policy evaluation or policy improvement algorithms. We illustrate the applicability of the results to several different policy-bast based RL methods (softmax update, greedy update and mirror descent update) studied in the literature [MXSS20, BT96 AYBB + 19, AKLM21].
While the main focus of our paper is on offline learning, we provide connections to regret bounds for online learning in average-reward MDPS as in [AYBB + 19 LYAYS2I]
1.2
Related Work
Our work in this paper is most closely related to the work in [CM22]. The main contribution there was to recognize that extension of the approximate policy iteration results in [BT96] can be used to derive finite-time error bounds for many RL-based algorithms. The idea of considering iteration-dependent policy evaluation and improvement bounds was also used to study policy iteration with function approximation in discounted-rewart MDPs in [WLLS2T]. Our contribution here is to derive the first error bound for approximate policy iteration for average-reward MDPs and then write it in a form which can be applied to policy-based RL methods for average-reward TD learning. known error bounds existed in prior literature for average-reward
To the best of our knowledge, approximate policy iteration due to the fact that the corresponding bounds for discounted MDPs increase proportional to the square of length of the horizon. Thus, in the limit as the horizon increases to infinity, we have essentially reduced the dependence of the error from the square of the length of the horizon to linear in the length of the horizon.
RL algorithms have not been studied as extensively for the average-reward case as they are for discounted-rewwe reward MDPs. There is recent work [ZZM21] average-reward TD-learning which leverage to illustrate the applicability of our results. There are also asymptotic convergence results for policy gradient and actor-critic methods for average-reward MDPs [TVR99 KT99 BSGLO9 MMT(0]. However, these results only prove convergence to a stationary point and there are no global convergence results. The original paper natural policy gradient (NPG) is written for average-reward MDPs, but the extensive performance analysis of NPG in subsequent work such as [KLM21]] seems to only consider the discounted-reward case. Recent work [AYBB* 19 LYAYS2I] considers mirror descent in average reward RL but do not provide performance results for other RL algorithms. later section, we compare our results [AYBB* 19 of mirror descent- -type policy updates
LYAYS21 in the special case
2 Model and Preliminaries
2.1 Average Reward Formulation
We consider the class of infinite horizon MDPs with finite state space S, finite action space A, and transition kernel P. where [S] = n and |A| = m. Let AA denote the probability simplex over actions. We consider the class of randomized policies II {u S - AAJ. so that policy μ assigns a probability vector over actions to each state. Given policy μs, the transition kernel for the underlying Markov process is denoted by P : S + S, where (s((s(s)) (s) = EoeA EoeAM(a|s)P(( ((aas))P(s'(s) a) is the probability of moving to state s' E S from & E S upon taking action ju()) E A. Associated with each state-action pair (s, a), is a one-step reward which is denoted by ra((s) == Ea-a(e) a).
Let Jj E IR be the average reward associated with the policy P E 11, i.c. J is defined as:
Ep (Ei' Ta(#:)
Jn lim 100
Here the expectation is taken with respect to the measure P associated with the policy μ.. Let h R2 be the relative value function associated with the policy μ. Defining 1 12d to be the
3

---

vector of all ones, the pair (J hn)) satisfies the following average reward Bellman equation:
J,1 by = ru hp
Ty E I denote the stationary distribution associated with the kernel Pp. Let P 1T E Rax
denote the matrix whose rows are -.. Using I.p = PP jo we get the following characterization of the average reward by multiplying both sides of Equation (2) with Pp- J,1 "
Let J := max Ju the optimal average reward. From standard MDP theory, there exists h" R", for which the pair (J" ,h²) satisfies the following Bellman optimality equation:
(J","")
J'1 + h
max T + h.,h""
pell
Let jt" be the optimizing policy in Equation Then, similar reasoning shows that J pM
The goal of dynamic programming and reinforcement learning is to determine this optimal average reward J and its corresponding optimal policy μ². Policy iteration is one of the most widely used dynamic programming algorithms for this purpose. It consists two steps: (i) evaluation of the value function associated with a policy, and (ii) determining greedy policy with respect to this evaluation. There are primarily two challenges that arise when applying such an algorithm: (i) high memory and time complexity when the state space is too large, and (īi) the unknown transition probability kernel that governs the dynamics of the MDP.
When the state space is too large, it may be computationally infeasible to perform policy iteration exactly. Existing literature suggests that approximate policy iteration in the context of discounted reward MDPs yields good performance. However, such algorithm has not been studied in the context of average reward MDPs. fact, the results obtained for the discounted reward MDPs yield vacuous performance bounds for average reward MDPs given the standard relationship between discounted reward and average reward MDPs. We explore this further in Section 2.2
2.2 Relationship to the Discounted Reward MDP
To provide some background, we first discuss the approximate policy iteration algorithm in the context of discounted reward MDPs. Let [0. 1) denote the discount factor. The discounted reward associated with deterministic policy μ E II starting from some state S is denoted JØ (s) and is defined as:
oc Σ
J = Epp
(a'r(s:.
su
The value function J E In is the unique fixed point of the Bellman operator T R" R associated with the policy which is defined as T = Ta + alP,,. For each state E S, let (s) denote the optimal discounted reward, i.e., (s) = max Ja (s). Similarly, J E I the unique fixed point of the optimality Bellman operator T : R" R", which is defined as J = max (rp + al JJ.. Algorithm is Approximate Policy Iteration for the discounted
reward MDP:
Algorithm Approximate Policy Iteration: Discounted Reward
Require Jg E RI"
for k 0, 0,1,2.... do
1. Compute # IT such that || To Jellon Se D Approximate Policy Improvement
2. Choose JK+1 such that || J Juk. 1110 5
b Approximate Policy Evaluation
where J JAz47 T J Juzen
end for
Theorem 2.1. Let μy be the sequence of policies generated from the upproximate policy iteration algorithm (Algorithm 77. Then the performance error is bounded as:
E + 2x8
lim sup 1p
11 S
(1-00 a)
R-
Proof. The proof of this theorem can be found in Berl

---

From literature [Ros14 1,
we know that the average reward Jn associated with any policy is related its discounted reward f (s) counterpart as follows:
J - lim (1 as)
Note that the above relation is independent of the state E S, as the average reward does not depend on the initial state. Multiplying Equation (4) with (1 - a), and letting a - 1, still yields an approximation performance bound with (1 a:) in the denominator. This term blows up to infinity as + 1. Note that this bound is known to be tight under unichain Markov structure of the probability transition kernel [Berll. However, in practice it is observed that approximate policy iteration works well in the average reward MDP case although these theoretical bounds are not representative of this performance. To the best of our knowledge, iteration performance bound, when the policies induce an irreducible Markov chain. We bridge this gap between theory and practice by providing theoretical analysis of approximate policy iteration in the average reward MDP setting, with non trivial performance bounds.
are unaware of an average reward approximate policy
3 Approximate Policy Iteration for Average Reward
crucial component of the proof of convergence of approximate policy iteration in the context of discounted reward MDPs is the contraction due to the discount factor which is absent in the average reward setting (since a = 1). To get some source of contraction, we have to make some assumptions on the MDP.
Assumption 3.1. We make the following assumptions:
(a) Every deterministic policy μ E II induces an irreducible Markov Chain Py..
(b) For all policies, the diagonal elements of the probability transition matrix are positive, i.e. the Markov chain stays in the same state with non-zero probability.
Assumption (a) need not be satisfied by all MDPs. However, in order to satisfy this assumption, we consider a modified MDP where at every time step with probability E, an action is chosen from the set of all possible actions with equal probability. Simultancously, with probability 1 - E, choose an action dictated by some policy. The problem then to choose this policy optimally. For most MDPs of interest, this small modification will satisfy assumption with small (e)) loss in performance. It is straightforward to show the O(e) loss, but we include the proof in the appendix for completeness. Assumption (b) is without loss of generality in the following sense: there exists simple transformation which essentially leaves the MDP unchanged but ensures that this assumption is satisfied. This transformation known as the aperiodicity transformation or Schweitzer transformation was introduced in [Sch7]]. For more details, the reader is referred to the appendix. In the remainder of this paper, we assume that all MDPs are transformed accordingly to ensure the assumptions are satisfied. One consequence of Assumption (b) is the following lemma which will be useful us later.
Lemma 3.2. There exists a y O such that, for any policy μ E IT,
min
(i) 2 Y
iES
where n. is stationary distribution over states associated with the policy μ.
Proof. This lemma has been proved in a more general sense in the context of deterministic policies in [Vdw8)]. Since the aperiodicity transformation ensures non-zero probability of staying in the same state, the expected return times are bounded and the lemma holds true for randomized policies as well.
Prior to presenting the algorithm, consider the following definitions. The werage-rewarr Bellman operator T, R.n - Rn corresponding to a policy μ is defined as T = rn + p,, The average- reward optimal Bellman operator T R + R² is defined as Th = max ry + h, The value function h, associated with policy μ satisfies the Bellman Equation (2) with single step reward ry and the transition kernel Py. Note that hy is unique up to additive constant.
5

---

Solving for (Ju, (y) using Equation involves setting the value function for some fixed state x" as 0 (since this reduces the system from being underdetermined to one with unique solution). Further, the value function My can be alternatively expressed as the limm-x di hho for any ho R as is the case with discounted reward MDPs. However, unlike the discounted reward Bellman Equation, there is no discount factor a < preventing the value function from exploding to infinity. Hence, we consider value function computed using the relative Bellman operator T defined
Tuh = rp + h. - -aaa---(=="=1111) (1P,)))) (1")1.
We now state the algorithm for Approximate Policy Iteration for Average Reward MDPs.
3.1 Approximate Policy Iteration Algorithm for Average Reward MDPs
Algorithm 2 Approximate Policy Iteration: Average Reward
1: Require hig E R.
2: for k = 0, 2....... do
3: 1. Compute ux+1 E such that || poz, telll Se
Approx. Policy Improvement > Approx. Policy Evaluation
4: 2. Compute h such that [ - hypzt 00 S
5:
where hpui1 limmm
Tm lk
pk41
6: end for
3.2 Performance bounds for Average Reward Approximate Policy Iteration
We are now ready present the main result of this work.
Theorem 3.3. Let J be the optimal average reward of MDP that satisfies Assumption 3.1 The sequence of policies μ.k. generated by Algorithm P and their associated average rewards Jum. satisfy the following bound:
11 (1-(1-2)*) 7
(J"-J
(E +) 28) (1 71 (J" min (Tho
ho) (i) +
upproxciaation error
initial condition error
Interpretation of the Bound: Since 0 < 1, k 0o, the error due to initial condition ho drops to zero. The approximation eтгог consists of two components, e and 6. Here, e represents the approximation error due to suboptimal policy and represents the approximation error associated with evaluating the value function corresponding reward associated with the policies obtained as a consequence of the algorithm is captured in the following corollary.
policy. The limiting behavior of the average
Corollary 3.4. The asymptotic performance of the policies obtained from Algorithm 2 satisfies:
lim lim (J" Jux)5 (1 +) 7)c+))222 28
k-+00
Note that the asymptotic bound in Equation (5) is in a very similar form as the asymptotic performance bound for the discounted reward MDP Equation (4) where 7 plays the role of (1 a)² However, when and got to zero, this bound also goes to zero which is not the case if we try to approximate average-reward problems by using the results for discounted-rewan problems in the limit where the horizon goes to infinity.
4 Application to Reinforcement Learning
Approximate policy iteration is closely related to RL. In general, approximate policy improvement and approximate policy evaluation in Algorithm 2 are executed through approximations to policy improvement (such as greedy update, mirror descent, softmax) and TD learning for value function approximation. First, present generic framework to analyze policy-based RL algorithms by

---

building upon the theory presented in the last section. For this purpose, we define the state-action relative value function Q (instead of the relative state value function h as before) evaluate policy. Let T denote the Bellman operator with respect to Q and policy l where QT) a) = r(s, a) + (Q, Q) (s, a), where Qu((s, I a) = pua' (s') (s) [ a). The relative state action value function corresponding to policy j represented by Q₂ and is the solution to the following Bellman equation: J,, (s, a) = r(s, a) + E E.A Qu (8', al|s, a Qu'('', a²), for all state action pairs (s, a) (S. We present generic policy-based algorithm for average-reward problem below.
Algorithm 3 Generic Policy Based Algorithm: Q-function Average Reward
Require Qo R (||AA
for k 0, 0.1...... do
1. Determine M4++1 II function of Qx using a possibly random policy improvement step
2. Compute Qh-1 as approximation to Que41 using (state, action, reward) samples from trajectory generated by policy Pk++1 end for
Note that the error in Steps (policy improvement) and 2 (policy evaluation) of the above algorithm could be random. Thus, the analysis for Theorem 3.3 has be adapted Algorithm 3 expected deviation from optimality characterized in the lemma below.
The resulting
Lemma 4.1.
Let μs and Qs be the sequence of policies and relative state-action value function iterates generated by Algorithm 3
For all lo E .,,...T, have:
J
min (TQQu Qk) (8.0) s (1 -7) (J- min (x.a)
(8, (8,
(s.a)
Q Qk-il xx +2| -Qullooo
where
min pE (x.0)E8xA
as) > 00
and Q7 is a matrix with identical rows corresponding to the invariant distribution of Qu-
Iteratively applying Lemma yields the following proposition for generic policy-based algorithm.
Proposition 4.2. For any T 0, the iterates of Algorithm 3 satisfy
T-1
S (1- J" - min (T Qo) (1) +2 Σ (1->)
(1-))' B[I
Initial condition
Policy evaluation error
T-1
7)
E
T
PT+1- Aaa-----------
|||||| +E ||
T pT+1 Qr - T9QT
Policy improvement crror
We now illustrate the applicability of the above result to specific RL algorithms. More specifi- cally, we characterize finite time performance bounds when state-action relative value functions are learnt through TD-Learning [ZMM21), while several different update rules are employed for policy improvement.
4.1 Performance bounds for RL algorithms
For every iteration of Algorithm 3 is necessary to observe trajectories length 7 in order to learn the state action value function associated with any policy. Using linear function approximations for value functions, the error in policy evaluation at iteration k in Algorithm 3 can be expressed in the following form:
||Qx Quxllo | 1lo) + 11Qus
60 Il
(6)
7

---

where D E R|SIAA)xd corresponds to the feature vector matrix and 0 E R is the parameter vector. Further, 0g is the parameter vector obtained as result of the TD learning algorithm. The projection of Qua onto the span of Φ is given by 40 The last term in Equation (6) corresponds to the function approximation error which depends on the span of the feature matrix V. We denote this error term by d0 The error due to TD learning (first term in Equation (6) is denoted by ŌTD, k- Assuming (sa A [] a) ll2 < 1. and | au lle is bounded uniformly in k. [ZZM2[] shows that there exists C' > 0 such that the length of the sample trajectory and ŌTD,E are related as follows:
C'
E [0TD,1 = VF
Let co = -J" -J* (TºQo- Qo) Qo) (i)) be the error due to initial condition and 8n = max, do. be the maximum function approximation error across all iterations. Then we obtain the following performance bounds when TD learning is used for policy evaluation.
Corollary 4.3. (Greedy policy update) Let ä(s) = argmax Qs(s, d'). Let > 0 be such that the sequence of policies in Algorithm 3 corresponding to all state action pairs (s, a) are obtained using the following algorithm, which we call the greedy policy update.
if + a(s)
(bb+(aass) = 31A
(8)
3. ifa ä(s),
L = max,es, aEA (Qx(s, a)). Using TD Learning with linear value function approximation for kEl...
policy evaluation, we get the following time performance bound:
1 +
2n
C 2
2
2
E
s (1-7)
80
(9)
B
Corollary 4.4. (Softmax policy update) Let 3 > 0 be such that the sequences of policies in Algo- rithun 3 corresponding all state action pairs (s, a) are obtained using the following algorithm, which we call the softmax policy update.
exp (3Qu(s,a)
Pi++ (als) Enee exp (3.((s(')))
(10)
Using TD Learning with linear value function approximation for policy evaluation, get the following finite time performance bound:
E -pr=n] (1 +
(1+2) log ((AA)
(30
2
30
CT VF
(11)
B
Corollary 4.5. (Mirror descent update) Let 3 >> 0 be such that the sequences of policies in Algo- rithm 3 corresponding to all state action pairs (s, a) are obtained using the following algorithm, which call the mirror descent policy update.
[k+i(a)s))
()) x (g(aas) exp( a)}-
(12)
Let minke1 T pu (s)]s) where a" (s) is the optimal action at state s. Using TD Learning SES with linear value function approximation for policy evaluation, we get the following finite time performance bound:
E J S (1- (1+2) log 78
2
+
00 + v=)
(13)
Remark 4.6. The following remarks are in order:
In each of the above performance bounds, there is an inevitable constant error (ōp) due to function approximation. If the value function lies in the class of functions chosen, then this error will be zero.
The error due to policy update (characterized by 3) can be made arbitrarily small by choosing 3 large. However, choosing a large 3 may increase C' due to the fact that C' is function of the mixing time of each policy, which is affected by the choice of B. However, C' cannot be arbitrarily large due Assumption (a).
The error due to the initial condition decays exponentially fast but the rate of decay can be slow because y can be very small. In this regard, it is interesting to compare our work with
the results in (AYBB 19 LYAYS2I]. We do so in the next subsection.
8

---

4.2
Comparison with [AYBB 19 LYAYS21
Our model for approximate policy iteration is intended to be a general framework to study policy- based RI. algorithms. A specific class of such algorithms has been studied in [AYBB* 19 LY)Y where regret bounds are presented for a mirror descent like algorithm referred to as POLITEX. Although our model is intended for offline algorithms, it is possible to adapt the techniques in LYAYS2I to obtain regret bounds for our model as well.
[AYBB 19
Let (5t, 0+) be the reward obtained at time t. Let K be the total number of time units for which Algorithm 3 is executed. Hence = TT, where T is the length of the sample trajectory for every
iteration of policy evaluation. The regret, defined as R(K) = =iE (J+ r((e, 0e)) can be further decomposed as:
R(K) EJ- Jpn) + (Jpc r(s,, ae).
(14)
The first term i.e., ( is referred the pseudo regret (K)(K). The second term essentially bounding the average value from its estimate and can be bounded using a martingale analysis identical to [AYBB 19, LYAYS2I). Here, we focus on obtaining an upper bound on the pseudo regret with mirror descent update and TD learning. The pseudo regret can be further decomposed as:
Rps (K) = Σ (J" Jp.).
For the mirror descent policy update in Corollary
4.5 we get the following regret bound
1 + log
(1)
2 2(5
Rps
(K)
Σ
(11-))²a
30 + vF)
(15)
73
?
1=1
Let B /T, then the above regret can be expressed as:
Kcs vF
Rps (K)(K))
< 7 TCp + 2K +
Optimizing for the regret yields 0(K3) and the following pseudo regret upper bound,
Rps(K) $ 2Koo + co
(16)
We now compare our regret bounds to the ones in L Since all of the bounds will have inevitable error (5o) due to function approximation, the comparison is with respect to the other terms in the regret bound.
We get a better order-wise bound on the regret compare to [AYBB which obtains a bound of ((33/4). However, they have better constants which are in terms of mixing-tima coefficients rather than in terms of 7.
LYAYS21 gets better regret bound (O(VK)) than us.
The results in AYBB 19 LYAYS21] use Monte Carlo policy evaluation, which allows for a closed- form expression for the value function estimate. The structure of the closed-form expressions allows them to exploit the fact that the policy varies slowly from one iteration to the next (which is specific to the mirror descent policy update) and hence 7 does not appear their analysis. However, the Monte Carlo policy evaluation algorithms use matrix inversion which is often too expensive to implement in practice unlike the TD learning algorithm
our analysis which is widely used. Nevertheless, ideas in [ABB 19 [YAYS21] provide a motivation to investigate whether one can extend their analysis to more general policy evaluation and policy improvement algorithms. This an interesting topic for future research.

---

Conclusions
We present general framework for analyzing policy-based reinforcement learning algorithms for average-reward MDPs. Our main contribution is to obtain performance bounds without using the natural source contraction available discounted reward formulations. We apply our general framework to several well-known RL algorithms to obtain finite-time error bounds on the average reward. We conclude with a comparative regret analysis and an outline of possible future work.
References
[ABB01] Jinane Abounadi, Dimitri Bertsekas, and Vivek S Borkar. Learning algorithms for markov decision processes with average cost. SIAM Journal Control and Optimiza- tion, (133)681-696 2001.
[AKLM21] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1) (:(())443))) ):4431-4500 2021.
[AYBB 19] Yasin Abbasi-Yadkori. Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. International Conference Machine Learning, pages 3692-3702. PMLR, 2019.
[Berl1] Dimitri P Bertsekas. Dynamic programming and optimal control 3rd edition, volume Belmoni, MA: Athena Scientific, 2011.
[Ber12] Dimitri Bertsekas. Dynamic programning and optimal control: Volume I, volume 1. Athena scientific, 2012.
[BSGL09] Shalabh Bhatnagar, Richard S Sutttnn, Mohammad Ghavamzadeh, and Mark Lee. Natural actor cetor-critic algorithms. Automatica, 45(11):2471-248) 2009.
[BT96] Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scien- tific, 1996.
[CCM22] Zaiwei Chen, John Paul Clarke, and Siva Theja Maguluri. Target network and truncation overcome the deadly triad in q-learning. arXiv preprint arXiv:2203.0263 2022.
[CM22] Zaiwei Chen and Siva Theja Maguluri. Sample complexity of policy-based methods un- der off off-policy sampling and linear function approximation. International Conference on Artificial Intelligence and Statistics, pages 11 11195-11221 1214. PMLR, 2022.
[Gos04] Abhijit Gosavi. Reinforcement learning for long-run average cost. European journal of operational research, (5533)65546744 2004.
[JS993] Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic programming algorithms. Advances in neural information processing systems, 6, 1993.
[KT99] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances neural informa- tion processing systems, 12, 1999.
[LYAYS21] Nevena Lazic, Dong Yin, Yasin Abbasi-Yadia Yadkori, and Csaba Szepesvari. Improved regret bound and experience replay in regularized policy iteration. In International Conference on Machine Learning, pages 6032-6042. PMLR, 2021.
[Mah96] Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Recent advances in reinforcement Learning, pages 159-195. 1996.
[MMT00] Peter Marbach, Oliver Mihatsch, and John N Tsitsiklis. Call admission control and routing in integrated services networks using neuro-dynamic programming. IEEE Journal selected areas in communications, 18(2):197-208, 2000.
10

---

[MS08] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5). 2008.
[MXS500] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference Machine Learning, pages 6820 6829. PMLR, 2020.
[Put14] Martin L Puterman, Markov decision processes: discrete stochastic dynamic program- ming. John Wiley & Sons, 2014.
[Ros14] Sheldon M Ross, Introduction to stochastic dynamic programming. Academic press. 2014.
[SB18] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[Sch71] Paul J Schweitzer. Iterative solution of the functional equations of undiscounted markov renewal programming. Journal of Mathematical Analysis and Applications. 34(3):495-501, 1971.
[Sin94] Satinder P Singh. Reinforcement learning algorithms for werage-payooff markovian decision processes. In AAAI, volume 94, pages 700-705, 1994.
[Tsi94] John N Tsitsiklis. Asynchronous stochastic approximation and q-learning. Machine learning, 16:185-202 1994.
[TVR99] John N Tsitsiklis and Benjamin Van Roy. Average cost temporal-differenn learning. Automatica, 35(11):1199-1888 1999.
[Vdw80] Van der Wal. Successive approximations for average reward markov games. Interna- tional Journal of Game Theory, 91)::13-24 1980.
[WD92] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292 1992.
[WLLS21] Anna Winnicki, Joseph Lubars, Michael Livesay, and R Srikant. The role of lookahead and approximate policy evaluation in reinforcement learning with linear value function approximation. arXiv preprint arXiv:2109 109.:29999 2021.
[WNS21] Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and planning in average-reward markov decision processes. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10653-10662. PMLR, 18-24 Jul 2021.
[YB09] Huizhen Yu and Dimitri P Bertsekas. Convergence results for some temporal difference methods based on least squares. IEEE Transactions Automatic Control, 54(7):5515- 1531, 2009.
[ZWSW21] Shangtong Zhang, Yi Wan, Richard S Sutton, and Shimon Whiteson. Average-reward off-policy policy evaluation with function approximation. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12578-12588. PMLR, 18-24 Jul 2021.
[77M21] Sheng Zhang, Zhe Zhang, and Siva Theja Maguluri. Finite sample analysis of average- reward td learning and q-learning. Advances in Neural Information Processing Systems, 34:1230-1242 2021.


Reviews:
[{"review_id": "JfSgOFqwcW", "reviewer": "Reviewer_WTrY", "summary": "The paper \"Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms\" tries to solve the open problem of obtaining meaningful performance bounds for approximate policy iteration algorithms for the average reward setting. If one tries to use the bounds for PI from discounted reward setting and set the discount factor equal to one to obtain the average reward setting, due to the horizon dependence, the bounds tend to infinity. While this is so, it is well known that API performs better in practice than this bound suggests. This paper tries to bridge this gap between theory and practice. It first obtains finite time error bounds for average reward approximate policy iteration. Then, it extends to obtain finite-iteration error bounds for the case where the errors can vary over iterations. Later, it illustrates the use of these results for various policy-based RL methods.", "questions": "Please provide clarifications to the questions above.", "limitations": "Yes, the authors have addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Directly using the bounds for PI from discounted reward setting by setting the discount factor equal to 1 and obtaining the average reward setting, the bounds tend to infinity. This is due to the horizon dependence.  From the literature, it is well known that API performs well in practice, in contrast to what this bound suggests. This paper tries to bridge this gap between theory and practice by presenting meaningful performance bounds for approximate policy iteration algorithms for the average reward setting.\n\n2. Their bounds show that the error goes to zero, unlike the transformation of bounds from discounted to average reward.\n\n3. The motivation is clear and the paper is very well written.\n\n4. Obtained performance bounds for various RL based methods by plugging the above bounds.", "weaknesses": "1. In the performance bounds for RL based methods, the errors don't seem to be small. They all depend on $\\gamma$, which can make them worse. (This is discussed in remark 4.6, but I don't understand the use of these results if this is the case, please clarify this).\n\n2. In section 4.2, the regret of an online algorithm is discussed. In equation $16$, the regret is of the linear order, while the earlier work has $\\sqrt{K}$ dependence. Moreover, this bound depends upon $\\gamma$. Then again, what is the use of these performance bounds?\n\nA minor issue:\n\n$\\gamma$ is not clear or defined before Theorem 3.3. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and their comments. Please find our response to the weaknesses below:\n\n1. Our results state that in the limit when the function approximation error goes to zero, the learned policy's performance approaches the performance of the optimal policy. Such a result was previously non existent in prior literature on average reward MDPs, except in a very special case considered in [AYBB+19, LYAYS21]. We will comment on [AYBB+19] in this bullet and will comment on [LYAYS21] in the next bullet.  In the context of mirror descent with modified LSPE [AYBB+19] provide with $O(K^{3/4})$ regret bounds which are independent of $\\gamma$ since they leverage properties specific to mirror descent. If we were to use mirror-descent-specific properties like in their paper, we can get the same $\\gamma$ independent result with the same regret bound as in paper even for TD learning. However, our result improves on the regret bound by obtaining $O(K^{2/3})$ regret but a dependence on $\\gamma$. Which bound is better depends on the relative sizes of $K$ and $\\gamma.$ Beyond mirror descent, it appears unlikely that we can remove the dependence of $\\gamma$ since it appears even in the analysis of modified policy iteration for average-reward MDPs when the probability transition matrix and rewards are known. \n\n2. Both the regret in our paper and [LYAYS21] have a linear component due to function approximation error, see Equation 7 in [AYBB+19] and Assumption 6.1 in [LYAYS21]. The $\\sqrt{K}$ result in [LYAYS21] is the $\\\\textbf{additional}$ error beyond the function approximation. Our corresponding bound is $O(K^{2/3}).$ However, it should be noted that the result in [LYAYS21] is for Monte Carlo policy evaluation which is infeasible in practice (for example, due to the need to collect and store large trajectories and the need for a very large matrix inversion) while our result is for TD-learning, which is widely used. The correct comparison of our result would be to the result in [AYBB+19]; in comparison to this paper, we have improved the regret from $O(K^{3/4})$ to $O(K^{2/3}).$  \n\nMinor Issue: $\\gamma$ has been defined in Lemma 3.2 prior to Theorem 3.3. We will add a reference to the definition of $\\gamma$ in Theorem 3.3 as well.\n"}, {"review_id": "5nUjjt66mB", "reviewer": "Reviewer_z18A", "summary": "This paper studies the convergence of approximate policy iteration for the average reward setting. First, finite suboptimality bounds are provided for average reward approximate policy iteration under suitable ergodicity properties of the set of policy-induced Markov chains. Next, these results are extended to Q-iteration-type algorithms, building a bridge to reinforcement learning methods. Finally, using this bridge, corresponding bounds are provided for a variety of existing policy iteration-based reinforcement learning methods, including greedy policy updates, softmax policy updates, and mirror descent updates.", "questions": "* How can the approximate policy evaluation and improvement oracles be instantiated in practice?\n* Did the careful bounding mentioned in lines 119-125 of the appendix consist solely of manipulations of inequalities and algebraic expressions? Or was there some key, interesting insight or innovative application of some unlooked-for technique required?", "limitations": "Aside from the weaknesses and questions above, the authors have addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is well-written, it builds the necessary technical background thoroughly but concisely, its contributions and results are clearly stated, and it addresses a longstanding open issue in classical policy iteration methods for average-reward MDPs. The overall plan of the paper is to rigorously establish a connection between average-reward approximate policy iteration methods and policy iteration-based average-reward reinforcement learning methods, inspired by the work [Z. Chen & S. T. Maguluri, _Sample complexity of policy-based methods under off-policy sampling and linear function approximation_. AISTATS, 2022], which achieved this for the discounted setting. In the present work, this is achieved largely via an analysis based on [J. Van der Wal,  _Successive approximations for average reward Markov games_. International Journal of Game Theory, 1980], but suitably modified to handle the presence of approximation errors in the policy recovery and policy evaluation steps. I did not check the appendix in detail, but the general thrust of the arguments appears to makes sense. The work has a somewhat \"classical\" flavor, as access to the transition dynamics, rewards, and approximate policy improvement and evaluation oracles appears to be assumed in the algorithms and analysis, but it should nonetheless be of interest to the theoretical RL community, especially those interested in RL policy iteration and policy evaluation underpinnings.", "weaknesses": "My main concerns are the following:\n* The apparent access to transition dynamics, rewards, and approximate policy improvement and evaluation oracles will likely appear unreasonable to those unfamiliar with, e.g., [D. Bertsekas & J. N. Tsitsiklis, _Neuro-dynamic programming._ 1996]. For this reason, a discussion of how the approximate policy improvement and approximate policy evaluation steps can be carried out in practice would help allay this concerns and strengthen the paper.\n* The key innovation and insight in the analysis remains somewhat unclear. Lines 119-125 in the appendix mention that the analysis of [Van der Wal, 1980] must be modified by carefully bounding the errors arising from approximate policy evaluation and improvement, but it is still unclear what the magnitude of the effort was and whether any specific, innovative techniques were used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and their comments. Please find our response to the weaknesses/questions below:\n\n1. Section 4 deals with how RL algorithms implement approximate PI. Approximate PI by itself should not viewed as an algorithm. The main novelty of the paper is show how one can analyze many practically implementable RL algorithms as instantiations of approximate PI. Therefore, analyzing approximate PI provides a path to analyzing policy-based algorithms, which is the main message of the paper. Specifically, we do not require access to transition dynamics, rewards, and approximate policy improvement and evaluation oracles because we are not directly implementing approximate PI. We are only showing that many RL algorithms naturally fit into this framework and these algorithms do not require access to approximate policy evaluating or approximate policy improving oracles.\n\n2. The idea behind relating consecutive iterates of the algorithms was inspired by Van der Wal [1980], however the rest of the analysis is mathematically different. Since Van der Wal studies modified policy iteration, there is no explicit notion of error in the policy improvement or policy evaluation steps. However, such errors are introduced in RL algorithms and therefore, to study RL algorithms, we have to study approximate policy iteration rather than modified policy iteration. As a result, it is important to make sure that the errors do not propagate from one iteration to another. In fact, this is the reason that the analysis for the discounted case fails to yield a non-trivial bound for average-reward problems in the limit the discount factor goes to one. The novelty in our analysis is to carefully bound the propagation of the error. We invite the reviewer to compare the steps of analysis in pages 9-11 of Van der Wal and our analysis in the proof of Theorem 3.3 to see the differences. Additionally, we note that the only prior works that were able to get sublinear regret were [AYBB+19] and [LYAYS21]. However, they were not able to analyze practical policy evaluation techniques such as TD-learning and other policy improvement algorithms (such as greedy update and softmax update) because of the fact that they were exploiting a connection to learning from experts. We believe that introducing the technique of Van der Wal [1980] to study RL algorithms (which to the best of our knowledge has never been done before) is a significant novelty in itself. Recognizing that the technique applies more broadly to RL algorithms (and not just to planning problems which was Van der Wal's motivation) is innovative application of a previously unknown technique to study RL algorithms."}, {"review_id": "dd05YwuIio", "reviewer": "Reviewer_h7bf", "summary": "This paper obtains performance bounds for policy iteration in the average reward setting, where instead of the usual discontinued factor formulation, the limiting ratio between total reward divided by time is used as a performance metric, which is a commonly used metric in the regret-based literature.The paper explains why obtaining such bounds has been difficult, and utilizes novel techniques and shows how we can obtain the bound.", "questions": "I am not familiar with RL theory and do not have the necessary background to ask questions on the topic. ", "limitations": "The authors have adequately addressed the limitations. ", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The technical claims seem sound, and the need for this bound in the average setting is well motivated. \n- The authors do a good job of explaining why it has been difficult to use commonly used techniques for analyzing performance bounds for PI. ", "weaknesses": "- It would be nice if the authors could mention meaningful problems that minimize for the average setting instead of the discounted setting. In other words, the author's mathematical contribution is well conveyed, but it would be good to motivate why we should care about the average setting in the first place despite the difficulty of analyzing them. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and their comments. Average reward RL formulations capture settings where long term rewards are considered more valuable than short term. Some of these applications include queuing network control, scheduling jobs during cloud computing, robot planning and control and communications networks. We are happy to include these applications in the paper. "}, {"review_id": "L6SCWNn2WO", "reviewer": "Reviewer_KNuh", "summary": "This paper focuses on finite-sample convergence analysis for average-reward reinforcement learning. The authors firstly propose finite-time  error bounds for approximate policy iteration. The major technique ingredient is performing Schweitzer transformation to the MDP. By this transformation, the stationary distribution of any policy could cover the state-space uniformly with a condition number $\\gamma>0$. Therefore some contraction arguments in the analysis for discounted MDP could be applied.", "questions": "1. In line 18 in the appendix, why $\\hat{V}_{\\mu}$ is bounded? And what is the exact bound? In general, $\\hat{V}$ could be large if the mixing time of the MDP is large. Do you need $\\mathrm{sp}(h^*)$ to bound $\\hat{V}_{\\mu}$?\n\n", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors firstly achieve a finite-time error bounds for approximation policy iteration in average-reward RL with using Schweitzer transformation;\n\n2. The authors also present a more refined analysis with respect to time-varying policy evaluation and improvement errors. Some extensions on practical algorithms (e.g, greedy and softmax) are established.", "weaknesses": "My major concern is about the technical novelty. The authors main contribution is to generalize the finite-time error analysis for $\\alpha$-discounted MDP to the average-reward MDP, and the major technique is using the Schweitzer transformation, which I think is roughly equivalent to  learning $\\lambda_1 \\mathbf{I}+\\lambda_2 \\bar{P}+(1-\\lambda_1-\\lambda_2)P$ instead of learning $P$ for some proper $\\lambda_1,\\lambda_2\\in (0,1)$, where $\\bar{P}$ is the averaged transition model over all actions, and $P$ is the true transition model. In this way, the contraction arguments could work directly.  \n\nI have learned similar arguments before in literature on online regret minimization for average-reward MDP (e.g. [Wei, 2020], [Wang, 2022]), where $\\lambda_1 \\mathbf{I}+(1-\\lambda_1)P$ is considered instead of the original transition model $P$. Moreover, [Wang, 2022] described the relationship between near-optimal policies for $\\alpha$-discounted MDP and that for average-reward MDP. More precisely, it was proven that an $\\epsilon$-optimal policy for $\\alpha$-discounted MDP is at least $\\epsilon+(1-\\alpha)\\mathrm{sp}(h^*)$-optimal for the average-reward MDP as long as the MDP is weak-communicating. Here $\\mathrm{sp}(h^*) = 2\\min_{x\\in \\mathbb{R}}\\|h^* - r\\cdot \\textbf{1}\\|_{\\infty}$. \n\nOne can also show that $\\|V^*_{\\alpha}-\\min_{s}V^*_{\\alpha}(s) \\textbf{1} - h^*+\\min_{s}h^*(s)\\cdot \\textbf{1}\\|\\leq O((1-\\alpha)D\\mathrm{sp}(h^*))$ , where $V^*_{\\alpha}$ is the optimal value function for the $\\alpha$-discounted MDP and $D$ is the diameter of the MDP.  \nIn this work, the authors introduce another term $\\bar{P}$ into the transition model to make the MDP irreducible for any policy. But I do not think it is a good choice since the mixing time could be exponentially large, which might make $1/\\lambda$ is exponentially large. \n\n\nReferences:\n\n[Wei, 2020] Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes\n\n[Wang, 2022] Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review, comments and references. We will add them to the paper and discuss why they do not apply to our problem. In response to the reviewer's comments, we provide the following remarks: \n\n1. The Schweitzer transformation is not enough to show contraction. We are just using it to ensure aperiodicity. However, this alone does not provide a source of contraction in the proof of average-reward MDPs. In fact, there is no source of contraction as far we know, and our proof only shows that the minimum of the value function contracts. The maximum does not, which is why the proof is complicated. In particular, the span does not contract.\n\n2. The Wei et al and Wang et al papers are for tabular settings. Moreover, Wei et al is for value-based algorithms (i.e., Q-learning) while Wang et al assumes access to a generative model. Specifically, Wang et al assumes $\\mathbb{P}(s'|s,a)$ can be estimated by repeatedly setting the MDP to state $(s,a)$ to observe the next transition. This allows them to estimate the probability transition matrix and solve a planning problem. \n\n3. We agree with the reviewer about the relationship between $V_\\alpha^*$ and $h^*.$ But we are unable to figure out how this helps in getting error bounds for average-reward policy-based RL. Regarding the comment on the mixing time, we are not sure what the reviewer means by saying that the mixing time will be exponentially large; we are not sure exponentially in what quantity.\n\nResponse to Question:\n\n$\\\\mathbb{P}\\_{\\\\rho} \\\\widehat{V}\\_{\\\\mu} - \\\\widehat{V}\\_\\\\mu$ is upper bounded by $\\\\text{span}\\\\{\\\\widehat{V}\\_\\\\mu\\\\}$,  where $\\\\widehat{V}\\_{\\\\mu}$ is the value function associated with the modified probability transition kernel $\\\\widehat{\\\\mathbb{P}}\\_{\\\\mu}$. Since we consider finite state-action spaces, bounded rewards and our modification ensures that all policies induce ergodic Markov chains, the $\\\\text{span}\\\\{\\\\widehat{V}\\_{\\\\mu}\\\\}$ is well defined and bounded. Therefore, we do not need $V\\_{\\\\mu^*}$ (referred to as $h^*$ in the question) to bound $\\\\widehat{V}\\_{\\\\mu}$. \n"}, {"review_id": "6Lbi4snPC9", "reviewer": "Reviewer_qfjY", "summary": "This paper proposed an Approximate Policy Iteration Algorithm for average-reward MDPs, and further extended to RL setting.", "questions": "See above.", "limitations": "It is unclear if the algorithm can be implemented in practice. ", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-written and clear. The approximated PI approach is new and novel; The theoretical results are also comprehensive. ", "weaknesses": "The algorithm seems unclear to me. How do the updates implement (e.g., Lines 3,4 in Alg 2)? \n\nHow does the approach handle the \"contraction\" in the average-reward setting?\n\nOverall, this paper seems a little bit unsurprising to me, the author should highlight the novelty and contribution in the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and comments. Please find our response to the weaknesses below:\n\n1. The approximate policy iteration algorithms in the paper is a framework to study RL algorithms and is not an RL algorithm by itself. One has to then relate them to RL algorithms so that we can use bounds on policy-based RL methods by showing that they are instantiations of approximate PI. Hence the updates in lines 3,4 in Algorithm 2 are a consequence of the particular policy learning and policy improving algorithm employed. The implementation of approximate PI using RL algorithms is discussed in Section 4.\n\n2. Average reward problems generally leverage a span contraction property due to the absence of the discount factor (which acts the source of contraction for discounted reward MDPs). However, the span contraction is not helpful in the setting of the paper, so most of the analysis involved is in circumventing this issue. Instead of contraction, we mainly leverage Lemma 2.1 and Lemma 2.2 in the appendix to deal with the lack of span contraction. Specifically, there is no contraction factor in our problem and the analysis is novel because of this fact.\n\n3. As pointed out by the reviewer, dealing with the lack of span contraction (and the lack contraction due to discount factor) does require novelty and the specific contributions of the paper are itemized on page 2 and 3. The surprising part of the result is evident from the reviewer's previous comment which notes the lack of a contraction factor."}, {"review_id": "EgQtW7V1iM", "reviewer": "Reviewer_M1AZ", "summary": "This paper derives some performance bounds on some approximate policy iteration type algorithms and later considers the application in the context of reinforcement learning. The bounds derived appear correct and meaningful but I have several comments which I will list below.", "questions": "1. In the discussion following (1), the authors try to argue out a bound for average reward problems after stating a bound for the discounted reward problems. Do we really have to do it this way to argue out the problems that might result. Why do we even need to use the bounds for discounted MDPs in the average reward setting?\n\n2. For the equation above (2), the authors would need to assume certain conditions on the underlying Markov chain in order for the limit to exist.\n\n3. Para above Sec 2.2 has incorrect statements. It suggests that algorithms based on approximate DP for average reward MDPs do not exist. The authors should look up references such as [BSGL09] and [KT99] cited their paper. There are several other papers that deal with average reward MDPs and use function approximation in particular.\n\n4. In Algorithm 1, the authors should specify what \\epsilon and \\delta are. Also, in step 2, how do you decide on J_{k+1}? Is there a systematic way of it's selection.\n5. In Theorem 3.3, is \\gamma the same as in Lemma 3.2? Mention also whether \\gamma >0.\n\n6. Second line after Corollary 3.4: Substituting \\gamma = (1-\\alpha)^2 makes the denominator same in (4)-(5) but numerators are quite different. So, not clear what the authors mean by saying \\gamma plays the role of (1-\\alpha)^2.\n\n7. In Lemma 4.1, what is T? Is this the time of episode termination. Also, is T deterministic or random? How is T chosen and what is the effect of T on the performance since it is an important parameter?\n\n8. Is the \\gamma in Lemma 4.1 the same as \\gamma in Lemma 3.2? I guess that is not true because this \\gamma is based on the state-action Markov chain unlike the state-valued chain previously. Why should the invariant distribution of the state-action Markov chain with transition probability matrix Q_\\mu exist?\n\n9. How does the inequality (6) hold? What is Q_k on the LHS and how did it vanish on the RHS?\n\n10. In Corollaries 4.3-4.5, what is the parameter \\tau and is it related to T? One would have expected the inequalities in these results to go to 0 as T goes to infinity, but that is not happening. Why does this problem arise and so how meaningful are the presented bounds in these corollaries?\n\n11. In (15), the RHS is multiplied by \\tau which was not the case earlier (see line below (14)). This makes the role of \\tau confusing?\n\n*********\nThe following comments are post the rebuttal from the authors.\n\n1. I am again looking at the paper. For one, things are not well presented at all. For instance, Algorithm 3 does not involve a theta_k parameter but in (6), the terms \\theta_k, \\theta^*_{\\mu_k} appear on the RHS saying that Algorithm 3 gives this. The authors begin by talking of approximate policy iteration and then say in the case of RL, the terms \\theta_k etc appear and there is no algorithm given for the update of the theta_k.\n\n2. The authors say that they are able to prove convergence to global optima even with function approximation but it's not clear how? In Remark 4.6, they mention that there is an error due to function approximation which is also the case with other algorithms in the literature that use function approximation. \n\n3. Also, the authors say they show asymptotic convergence. Is the convergence shown in the almost sure sense? If so, where is that result? Also, somewhere they said that [ZZM21] showed the bound in (7) assuming that \\theta^*_{\\mu_k} are uniformly bounded. It is not stated if the authors also assume this bound. Also, what about a bound on the \\theta_k sequence itself? Do you not require to prove stability of your stochastic iterate before claiming asymptotic convergence? \n\n4. Assumption 3.1a clearly is too strong because it is only for the case of deterministic policies. Following 3.1a, the authors say that they consider instead a modified policy where with some positive probability, they select an action uniformly at random and with the remaining probability, they select actions as per a deterministic policy. Clearly, this is not a deterministic policy. Then the assumption makes no sense. I find this whole thing a rather strange argument.\n\n5. Assumption 3.1b also requires a special structure on the Markov chain which may not always be the case - that the diagonal elements in the probability matrix have non-zero entries under every policy. This is also the reason why experiments are important. The authors can easily demonstrate in a future version of their work whether such unrealistic assumptions are needed even for empirical studies.\n*****\n\nThe authors have been able to convince me that theirs is a good contribution. I am therefore revising my score.\n", "limitations": "I have already listed my comments above. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper derives some performance bounds on some approximate policy iteration type algorithms and later considers the application in the context of reinforcement learning. The bounds derived appear correct and meaningful but I have several comments which I will list below.", "weaknesses": "One of the weaknesses is a lack of discussion on previous bounds that are available in the context of average reward problems.\nA central class of algorithms in the RL literature based on the policy iteration method have been the actor-critic algorithms.\n I would have preferred a thorough comparison and discussion on the significance of the bounds that the authors derive and how different are these from the bounds obtained for the actor-critic schemes.\n\nA second weakness is of the lack of any experimentation. That would have certainly added value to the paper even though the primary focus of the authors has been to derive some bounds for the algorithms.\n\nA third weakness is the lack of a comprehensive analysis of asymptotic convergence for these algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and comments. Please find our response to the weaknesses:\n\n1. Prior work such as [KT99] and [BSGL09] are mostly based on the analysis of policy gradient (PG). Since PG typically only converges to a local minimum, they only provide local convergence results. Moreover, even the local convergence results are only asymptotic in nature and do not have finite-time bounds. To the best of our knowledge, the only works close to our paper are [AYBB+19] and [LYAYS21], where they analyze a specific form of actor critic algorithm (mirror descent based). Section 4.2 provides a comparison of the bounds in our paper with the performance bounds in [AYBB+19] and [LYAYS21]. Specifically, we point out that in the case of the most widely used algorithm for policy evaluation, i.e., TD-learning, our approach via approximate PI improves the regret bounds from $O(T^{3/4})$ to $O(T^{2/3}).$\n\n2. Since the aim of the paper was to provide finite time performance bounds for a general class of actor-critic algorithms, we did not think experiments would have contributed towards this goal. \n\n3. Section 4 deals with performance bounds for RL algorithms. There by letting the number of iterations go to infinity, one immediately gets asymptotic performance bounds. As is typically the case in RL algorithms, the asymptotic error can only be made to go to zero if the feature vectors are rich enough to make the function approximation error go to zero. For example, in Corollary 4.3, Equation (9), the asymptotic error can be seen to be small if the function approximation error $\\bar{\\delta_0}=0$ and $\\beta\\to\\infty$. We provide finite-time bounds because they are more realistic (and the asymptotic error can be recovered from them by letting $T\\to\\infty$) and they provide insight into the tradeoffs involved in choosing various parameters. For example, making $\\beta$ large may increase $C$ as can be seen from [ZZM21]. However, under our assumptions, $C$ will be bounded and so, one cannot see its impact by looking at asymptotic expressions alone.\n\nResponse to questions:\n\n1. The point of the discussion was to illustrate the difficulty in getting bounds for the average reward case. In particular, as $\\alpha\\to1,$ it is well known that one can recover average-reward results from discounted reward results. The discussion points out that this relationship fails to provide a meaningful result in the case of avg reward approximate PI.\n\n2. The ergodicity assumption (Assumption 3.1) in the paper ensures that this limit exists. \n\n3. We agree with the reviewer, but note some important differences between prior work and ours. As mentioned before, the references [KT99] and [BSGL09] only provide convergence to a local optimum and the results are asymptotic in nature, i.e., no finite-time performance bounds. And the algorithms studied there are only gradient-based algorithms. On the other hand, our goal is to provide a unified framework for studying many algorithms, and to obtain finite-time performance bounds.\n\n4. $\\epsilon$ and $\\delta$ are the upper bounds on the policy improvement and policy evaluation errors respectively (as indicated in Algorithm 1). $J_{k+1}$ is determined based on the policy learning algorithm utilized. We note that approximate PI is a framework to study RL algorithms and is not an RL algorithm by itself. One has to then relate them to RL algorithms so that we can use bounds on policy-based RL methods by showing that they are instantiations of approximate PI.\n\n5. The two $\\gamma$'s are identical. Lines 191 and 209 both indicate that $\\gamma>0$.\n\n6. Even though the constants in the numerator of Equation 4 and 5 are different, the growth rate of the RHS in $\\epsilon$ and $\\delta$ is the same. In particular, both grow linearly with policy improvement and policy approximation errors.\n\n7. $T$ represents the number of iterations of Algorithm 3. The results in Lemma 4.1,  Proposition 4.2 and Corollaries 4.3-4.5 hold for any $T$. $T$ is any deterministic integer. The lemma, the proposition and the corollaries provide finite-time performance guarantees as a function of $T.$ In Section 4.2, we further provide regret bounds in terms of the total number of samples used, which is $T$ multiplied by the number of time steps in each policy evaluation step.\n\n8. $\\gamma$ in Lemma 4.1 is defined within the same lemma and it isn't the same as the one in Lemma 3.2. Since we are considering randomized policies and under the ergodicity assumption 3.1, the invariant distribution across state-action pairs do exist. We refer the reviewer to the Appendix on Discussion on Assumption for more details.\n\n9. $Q_k$ is the approximation to the state-action value function $Q_{\\mu_k}$ (defined in Algorithm 3). Since $Q_k$ is learnt through TD learning with linear function approximation, $Q_k=\\Phi\\theta_k$. Inequality 6 decomposes the evaluation error into function approximation error and estimation error. For more details refer lines 247-256.\n\n10. $\\tau$ is the length of the sample trajectory utilized for evaluating a policy. It is defined in the first sentence of Section 4.1, $\\tau$ and $T$ are independent of another. For every iteration of Algorithm 3, the learning step 2 involves generating a trajectory of length $\\tau.$ The RHS of the corollaries will not go to 0 as $T$ tends to infinity, since the approximation errors in policy evaluation may not go to 0. Similar to corollary 3.4, the asymptotic bounds in corollaries 4.3-4.5 do not go to zero as long as the approximation errors are finite. This is standard in RL theory. However, we note that the errors will go to zero if the feature space is rich enough to represent the value functions and if we choose $\\beta$ to be sufficiently large.\n\n11. For the purpose of regret analysis it is necessary to consider the total time units, which here happens to be $T\\tau$ (since for every iteration of Algorithm 3, a sample trajectory of length $\\tau$ is generated)."}]

Author rebuttal:

Meta-review: This paper contributes important advancements to the convergence theory of policy iteration in average-reward MDPs by introducing novel game-theoretic techniques. Moreover, the authors have substantively addressed all concerns by the reviewers who voted to reject the paper with high confidence, except for one who failed to reply to the discussion period completely. I recommend this paper be accepted.
Decision: Accept (poster)