On Convergence of Average-Reward Off-Policy Control Algorithms in Weakly-Communicating MDPs
Authors: Yi Wan
Richard S. Sutton
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Average-Reward
Off-Policy
Convergence

Abstract: We show two average-reward off-policy control algorithms, Differential Q Learning (Wan, Naik, \& Sutton 2021a) and RVI Q Learning (Abounadi Bertsekas \& Borkar 2001), converge in weakly-communicating MDPs. Weakly-communicating MDPs are the most general class of MDPs that a learning algorithm with a single stream of experience can guarantee obtaining a policy achieving optimal reward rate. The original convergence proofs of the two algorithms require that all optimal policies induce unichains, which is not necessarily true for weakly-communicating MDPs. To the best of our knowledge, our results are the first showing average-reward off-policy control algorithms converge in weakly-communicating MDPs. As a direct extension, we show that average-reward options algorithms introduced by (Wan, Naik, \& Sutton 2021b) converge if the Semi-MDP induced by options is weakly-communicating. 

Under review as a conference paper at ICLR 2023
ON CONVERGENCE OF AVERAGE-REWARD OFF- POLICY CONTROL ALGORITTMS IN WEAKLY- COMMUNICATING MDPS
Anonymous authors Paper under double-blind review
ABSTRACT
We show two average-reward off-policy control algorithms, Differential Q Learning (Wan, Naik, Sutton 2021a) and RVI Q Learning (Abounadi Bertsekas & Borkar 2001), converge in weakly-communice are the most general class of MDPs that a learning algorithm with a single stream of experience can guarantee obtaining a policy achieving optimal reward rate. The original convergence proofs of the two algorithms require that all optimal policies induce unichains, which is not necessarily To the best of our knowledge, our results are the first showing average-reward off-policy control algorithms converge in weakly- coally-commuiicaiin MDPs. As a direct extension, we show that average-reward options algorithms introduced by (Wan, Naik, & Sutton 2021b) converge if the Semi-MDP induced by options is weakly-commuuicating
MDPs. Weamli-communicating MDPs
for seally-commuiicatin MDPs.
INTRODUCTION
Modern reinforcement learning algorithms are designed to maximize the agent's goal in either the episodic setting or the continuing setting. both settings, there is an agent continually interacting with its world, which is usually assumed to be Markov Decision Process (MDP). In episodic problems, there a special terminal state and set of start states. If the agent reaches the terminal state, it will be reset terminal state, and the agent will never be reset by the world. For continuing problems, two commonly considered objectives are the discounted objective and the average-reward objective. The discount factor in the discounted objective has been observed to be deprecated in the function approximation control setting, suggesting that the average-rewan objective might be more suitable for continuing problems.
of the start states. Continuing problems different in that there is no
In this paper, we consider off off-policy control algorithms for the average-reward objective. These algorithms learn policy that achieves the best possible average-reward rate, using data generated by some other policy that the agent may not have control Designing convergent off-policy algorithms for the average-reward objective is challenging. While there are several off-police learning algorithms in the literature, the only known convergent algorithms are SSP Q-learning and RVI Q-learning, both by Abounadi, Bertsekas, & Borkar (2001), the algorithm by Ren & Krogh (2001), and Differential Q-learning by Wan, Naik, & Sutton (2021a). Others either do not have convergence proofs (Schwartz 1993; Singh 1994; Bertsekas & Tsitsiklis 1996; Das 1999), or have incorrect proofs (Yang 2016; Gosavi 2004).
The algorithm by Ren & Krogh (2001) requires knowledge of properties of the MDP which typically known. The convergence of SSP Q-learning is limited in MDPs with a state being recurrent under all policies. The convergence of the RVI Q-learning algorithm (Abounadi et al. 2001) was developed for unichain MDPs, which just means that the Markov chain induced by any stationary policy is unichain The convergence of Differential Q-learning (Wan al. 2021a) requires a weaker
See Appendix in Wan et al. (2021a) un) for discussion about Yang's proof and Appendix of this paper for a discussion about Gosavi's proof.
A Markov chain is unichain if there is only one recurrent class in Markov chain, plus possibly empty set of transient states.

---

Under review as a conference paper at ICLR 2023
assumption all optimal policies being unichain. is clear that RVI Q-learning also converges under this assumption with a small modification of its proof. It is not rare that an optimal policy induces multiple recurrent classes. For example, consider the MDP at the bottom of Figure 1. If an optimal policy induces multiple recurrent classes, the proofs of RVT Q-learning and Differential Q-learning would not go through. Technically, this is because both two proofs require that the uniqueness of the solution for the action-value function up to an additive constant in the average-reward optimality equation.
A more general class of MDPs, called weakly-communicating MDPs, is not limited in the number of recurrent classes under the optimal policy. In these MDPs, all policies may induce multiple recurrent classes. The only assumption is that, except for a set of states that are transient under every policy, all states are reachable from every other state in a finite number of steps with non-zero probability. It has been observed that the set of veakll-commmuiccting MDPs is the most general set of MDPs such that there exists learning algorithm that can, using a single stream of experience, guarantee to identify a policy that achieves the optimal average reward rate in the MDP (Barlett & Tewari 2009).
In this paper, we show convergence of RVI Q-learning and Differential Q-learning in weakly- communicating MDPs, without requiring any additional assumptions compared with their original convergence results. Two key steps in our proof are 1) showing that the solution sets of the two algorithms non-empty, closed, bounded, and connected, and 2) showing that 0 is the unique solution for the Bellman optimality equation when all rewards are O. With these two results, we use asynchronous stochastic approximation results by Borkar (2009) to show convergence the solution sets. As a direct extension of the above results, we also show the convergence of two algorithms that extend the Differential Q-learning algorithm to the options framework, introduced by Wan et al. (2021b), if the Semi-MDP induced by the MDP and the set of options is weakly-communicating
PRELIMINARIES
unichain under every policy
Consider finite Markov decision process, defined by the tuple M- - (S, A, R,P), where S is a set of states, A is a set of actions, R is a set of rewards, and p : x
CO
R x S x A + [0, 1] is the dynamics of the environment. Every time steps f the agent observes the state the MDP action A, E A using some policy b: A S + [0, 1]. then receives from the environment reward Re+1 R and the next state S S, and so on. The transition dynamics are defined as p(8'.r s. s. = Pr(S.41 = s', 2,
unichain under every optimal policy
S, S and chooses
r S. s, A₁ a)
O cominiccmmmnic
for all s E S,a E A, and r E R. Denote the set of stationary Markov policies IT.
Examples of three different types of MDPs. In each of the three MDPs, there are two states marked by two circles respectively. There are two actions solid and dashed, both causing deterministic effects. Top: The MDP is unichain under every stationary policy. Middle: There are two deterministic op- timal policies, moving to state or going back and forth between state and state 2. Other optimal stationary policies are mixtures of these two deterministic poli- cies. All optimal policies are unichain. Down: There are three deterministic op- timal policies: moving to state 1, mov- ing to state 2. and staying the current state. Other optimal stationary policies are mixtures of these two deterministic policies. The policy of staying at the cur- rent state induces two recurrent classes.
Figure 1:
The reward rate of policy æ starting from given start state s can be defined as:
n Σ
r(T, 5) - lim 100000 1
E S. 8, A0t-1 л). (1)
Given an arbitrary MDP, the agent may not even be able to visit all states and would therefore miss the chance of learning, for every state s, a policy that achieves the op- timal reward rate sup, r(T, s) and the agent can at most learn an optimal policy for set of states, in which every state is reachable from every other state. Such a set of states is often called communicating. Formally speaking, we say set of states communicating, if there exists a pol- icy such that moving from either one state in the set to the other one in the set in finite number of steps has positive probability. If the entire state space is communicating, say MDP communicating. Wealfy-communicatnn
2

---

Under review as a conference paper at ICLR 2023
MDPs generalizes over communicating MDPs. In communicannii MDPs, in addition to closed communicating set of states, there is a possibly empty set of states that are under every policy.
For communicmmuni MDPs, there exists a unique optimal reward rate тR, which does not depend on the start state. We say a policy is optimal if it achieves r. regardless of the start state. The goal of an off-policy control algorithm is to learn an optimal policy from the stream of experience ...,,,; St, Ar, R S1+1.... generated by a behavior policy that is not necessarily the same as the agent's learned policy. Both RVI Q-Jearning and Differential Q-learning achieve this goal by solving i and q in the optimality equation:
((s a) = Σ p(s'.r l s, (r. F maxq(sss VsE
is known that v. is the unique solution of and any greedy policy w.r.t. any solution of q is an optimal policy. In addition, shifting any solution of q by any constant vector results in the other solution of Finally, unlike in unichain MDPs (or MDPs where all optimal policies are unichain) where all solutions are different by some constant vector, in reakly-communicating MDPs, solutions of q may have multiple degrees of freedom. That is, if g1, 92 are both solutions of q, it is possible that Qi # 92 + ce, V c E R, where e denotes the all-one vector.
If the agent has set of options. it may choose to execute these options. Each option o in O has two components: the option's policy x" A x - [0. 1). and the termination probability 3 S -> [o, 1]. For simplicity, for any E S,0 O we use x x(a 8, o) to denote xa s) and (s,, o) to denote (s). If the agent executes option at state 8, the option's 's policy is followed, until the option terminates. Let L be the set of all possible lengths of options and R be the set of all possible cumulative rewards. Note that L and R are possibly countably infinite. Let p(s', r. | 88, 0) be, when executing option o starting from state s, the probability of terminating at state s', with cumulative reward r and length I. Formally, for any s, s' ES,0E Orr E R, E L, P can be defined recursively in the following way:
p(s', 8, Σ
M(a 8, 0,
Σ p(5 s,a)
3,
1)+ i -( f. 8,)],
(3)
where I is an indicator function.
An MDP M and a set of options O results in an Semi-MDP (SMDP) M = (8,0,
If the agent chooses options using meta-policy (pooiiyyover-optiions)) : OxS - [0, 1] and execute these options, denote ... Sn. Ôn, Ro Sx+1, ... as the sequence of option transitions. For this SMDP, the reward rate of given start state can be defined , (IT, s) = lim Ex EEE R&
So = sl/t. r(n, s) = lim E, ドΣ= Rg S. = ET L, S. = s]. Both limits exist and equivalent (Puterman's 's (1994) propositions 11 11.4.1) under the following assumption:
Assumption For each option o E O, when executing the option, there is non-zero probability of terminating the option after at most |S] stages, regardless of the initial states.
Proposition 1. Under Assumption 1, the expected value as well as the variance of the execution time and cumulative reward of every option at every state exist and are finite.
We say an SMDP is commuiitimmniii if the MDP with state space S, action space O, reward space R. and transition function Σ, 8, o) weakly-communicatingg Just like the MDP setting, if the SMDP is reakly-communication the optimal reward rate f. = sup r r(T, s). where il denotes the set of stationary Markov meta- peta--ooiiies, does not depend on the start state s. In addition, the solutions of q may not be different for a constant. Given MDP and set of options, the goal of the off policy control problem is to find a policy that achieves f.. Inter-option Differential Q-learning achieves this goal by solving the optimality equation for SMDPs (Puterman 1994):
((8,0) = Σ p(s',,, r,, 8, o) F- max q()),')))
(4)
s'.
where g and F denote estimates of the option-value function and the reward rate respectively. Just like the MDP setting, f has f., as its unique solution and solutions of may not be different by a constant vector.
3

---

dimml < and Assumption 3. Let [+] denote the integer part of (-), for (0, 1), sup, on 1 uniformly in E [x, 1]. Under review as a conference paper at ICLR 2023
Intra-option Lefferential-leemiinn finds optimal policy by solving the intra-option optimality equation.
(8, = Σ T(a 8,0) E - u(( VsE8,0E0, (5)
where
u (6( = (1- ()) 0(( max q(s o').
(6)
The following proposition shows that the set of solutions of equation 5 is the same with that of equation 4.
Proposition 2. Any solution of equation 4 is also a solution of equation 5 and vice versa.
3 CONVERGENCE RESULTS
In this section, we present the convergence theory of Differential Q-Learning RVI Q-Learning in weakly-communicattngg MDPs and that of the two option extensions of Differential Q-Learning in
SMDPs. Empirical results verifying the convergence of the two MDP algorithms are presented in Appendix B.
Differential Q-learning updates table of estimates Qi : A + R as follows:
QSt1(S; A.) Qs,S, A,) + au(t,S,,A,) Q a) (s, V v, a + S,, Ar,
where vtt, As) is the number of times S,, A, has been visited before time step t, (v(t,S;.AA) is step-size sequence, and 8, the temporal-difference (TD) error, is:
5 = R - R. + max Q, Qr,s,,A)).
(8)
where Rg a scalar estimate of r., updated by:
Ret1 Rr nap(,,...)..
and 1) is a positive constant.
We now present the convergence theorem of Differential Q-learning. We first state the required assumptions, which are also required by the original convergence proof of Differential Q-Learning by Wan et al. (2021a).
Assumption 2. For all n 2 0, an > E on oo, and En a < oc.
lymi
2nzo an
Assumption 4. There exists such that
(n, n+1
fiminf 200
2 A.
a.s., for all 3 E S,a E A. Furthermore, for all x min (m > n: exists a.s. for all 8,8' E ES, a, A.
0. let N(n, x)) / (Fu(N (kmu(aaddaa)
m Ekant1 as 2 x}, the limit lim,- Ek=u(n,s,a) ass)
(N..)))))))
Osk
Theorem If M is communicating and Assumptions 1-4 hold, the Differential Q-learning algorithm (Equations 7-9) converges, almost surely, R₂ to T., Qe to the set of solutions of equation 2 and
T. - Ro Ro= =1
Σ ((s 8,a
-ooos,
(10)
5.a
and r( 8) to r., for all E S, where ni is any greedy policy w.r.l. Q+.
4

---

Under review as a conference paper at ICLR 2023
Remark: If the MDP is communictmmm that is, it contains transient states, the agent eventually reaches the closed communicating state and never returns to the transient states. Elements in Qn that associated with the closed communicating set converge to set that depends on the values of Q and R when the MDP reaches the closed communicating set for the first time. Other elements in Qn would only be visited for finite number of times and not be guaranteed to converge to their correct values by any learning algorithms. Other conclusions of the theorem remain unchanged. This observation on weakly-communice
MDPs apply also to Theorems 2-4.
The update rules of RVI Q-Learning are
Qu+1(S,, At) Qs, A.) A. Ar)
(11)
Q4+1(8, = Q+(s,a), a), A 8, + S Ac:
where
8,(S,, A.) = R4+1 - s(Q.) + max Qr +1 Qc(Ss,
(12)
and f S x A E satisfying the following assumption.
Assumption 1) L-Lipschitz, 2) there exists a positive scalar s.t. f(e) u and f(x + ce)= f() + cu, 3) f(xx)= cf(x).
Theorem 2. If . is communicating and Assumptions 1-5 hold, then the RVI Q-Learning algorithm (Equations 1 12- converges, almost surely, R2 to Ta, Qt to the set of solutions of equation 2 and
T= = f(q),
(13)
and r( 8) to r., for all 8 E S, where Te is any greedy policy w.r.l. Q₁-
Now consider option extensions of Differential Q-Learning. Given an SMDP = (S, R. P). inter-option Differential Q learning maintains estimates of option values, and, inspired by Schweitzer (1971), update estimates using scaled TD errors:
Qu+1(Sn, Ô.) = (S,, Ôn) + Sn. /eaen//Lnnnn (n Ōn).
(14)
Qn-1 = Qx, o), & 88002 # Sm, Ón Rn+1 = Rm + n7 n 8n
(Sn, Ôn).
(15)
where v(n, Sm, Ô,)) is the number of visits before stage n, Ln(.,) .) comes from additional vector of estimates L : S x O + R that approximates the expected lengths of state-option pairs, updated from experience by:
L (S.. O,) = (S,. Ó,)) + Puin.S.. o,), L, (S,,, On)),
(16)
where {Bn) an another step-size sequence. The TD-error 8, in equation 14 and equation 15 8n - R. - Ln, Rn, + max Qn ($,+1. (S, Ów).
(17)
Theorem 3. If M is communicating. Assumptions 1-4 hold, except for using v(n, 8, 8,0) instead of vtt, 8, a). and that & 3n, 1, Σn 3n oc, and En &% < 6o, inter-option Differential Q-learning (Equations 14-17) converges, almost surely, Qn the set of solutions of equation and
f. Ro = =nn 2 q(s,o)
_v((s,))
(18)
8,0
6.0
Rn to P., and r(Tn, 8) to f. where n. is a greedy policy w.r.t. Q..
Intra-option Differential Q learning also maintain estimates of option-values. However, instead of updating the estimates using option transitions, it updates for all options using each action transition.
Qu+1SS o) = Qe(S,, svitt.s..
VoEO,
(19)
Q++1(8,0) = Q)(s,)), V
Ret1 = Rí + Σ (u((s...))),((000((.)))
(20)
where is step-size sequence, po(0) ((..)S..)) (.A
is the importance sampling ratio, and:
(0) Re41
R. + u Q: (S++1, o) - Qi(St,o),
(21)
where is defined in equation 6.
5

---

Under review as a conference paper at ICLR 2023
Theorem 4. If M is communicating, Assumptions 1-4 hold, except for using s(t,s, instead of v(t, 8, a). intra-opticn Differential Q-learning (Equations 19-21) converges, almost surely, Qt to the set of solutions of equation 4 and equation 18, R2 to f.. and ( to f. where n, is a greedy policy w.r. Qt-
4 CHARACTERIZATION OF THE SOLUTION SET
In this section, we characterize the sets that the algorithms described the above section converges to. This section plays key role in showing their convergence.
We consider the set solutions the SMDP optimality equation and
C c= c=)(q))
(22)
where f S O - R satisfies Assumption 5, c is an arbitrary real. Denote this set Qx.. It is clear that equation generalizes equation and equation 22 generalizes equation 10, equation 13, and equation 18. And thus the characterization of Qx applies sets that action/option values in the aforementioned algorithms are claimed to converge to in Theorem 1-Theorem 4.
It is known that if the SMDP is weakly-communicating equation 4 has P. as its unique solution for F. For q, it has been shown by Schweitzer & Federgruen (1978) (we will refer this work for multiple times and thus set of solutions for in equation 4 is closed, unbounded, connected, and possibly non-convex. The next theorem characterizes 2.
shorthand 'S&F' for simplicity from on) in their Theorem 4.2 that the
Theorem 5. If the SMDP is
and 1) is Lipschitz. and 2) there exists some u + such that f(x + ce) = f(x) + cu, V E I. eoo is non-empty, closed, bounded, connected, and possibly non-convex.
Before presenting the proof, first note that our convergence proof does not rely on the convexity property and delay the proof of non-convexity Appendix A.5.
Proof. First, 20 is non-empty. To see this point, note that for any solution of q in equation 2, Q. q. + ce also a solution for any E R and thus there must be a c such that equation 22 holds because f(x ce) fx) + for any x,
Q.o closed because the set of solutions of in equation 4 is closed by S&F, the set of solutions of q in equation 22 is closed because / is Lipschitz, and the intersection of two closed sets is closed.
Boundedness
We now show that Qx is bounded. To this end, it is enough show that the solution set of in
u(s) = max Σ p(s rr, ( (r - If_ + vssE
(23)
c c= c= + Pv),
(24)
where is any constant, and
F(s,0) = Eiss', r, s,0)(r 1f.)
s'.d.
P(),0,8) = Eiss'rr (8,0)
v.
bounded. Denote this set as V.o Once we show V.o is bounded, Qxc also bounded because each solution for q can be obtained from solution for with linear operation:
((8,0) 0) = Σ p(s', r,l 8, (r - IF v())), VsES,0E0.
(25)
In order to show boundedness, we need the following two lemmas, which slightly modify Theorem 4.1 and 5.1 by S&F. To this end, need first introduce some definitions.

---

Under review as a conference paper at ICLR 2023
For any π E II, P.. denotes the [S] x [S] transition probability matrix under policy я. That is,
(s = Σ < s)p(s' (
(26)
a,r.
Define Pr to be the limiting matrix of PRo, which is the Cesaro limit of the sequence {P+
p lim
P
(27)
12 100
Because S is finite, the Cesaro limit exists and P is a stochastic matrix (has row sums equal to 1).
Let (s) = Co.e.. To s)p(s', r s, s,0)1. And let the fundamental matrix Zn = (I p
p=-)-1=11 -1+im En=,," (P p.)). Let b(e, T) = [r- - L, P - o). and II, denote
the set of optimal meta-policies.
The following two lemmas are the similar to Theorem 4.1 (c) and Theorem 5.1 in S&F, except that 1) the 'max' operates over the set of all optimal policies, instead of the set of all deterministic optimal policies as in Theorem 4.1 (c), and 2) we consider the set of while S&F considers general multi-chain SMDPs. The proofs are also essentially the same. For completeness, we provide the proofs for these two lemmas in Sections A.3-A.4.
SMDPs
Lemma 1. If the SMDP is weakly- weakkly-oommniicatnng v is a solution of equation 23 if and only if ((x) = max (7 - 1-)))= P (s
(28)
FEn.
where îi, denotes the set of optimal meta-policies.
Define Ry as the set of recurrent states for P (i.e., R2 = {s P (s, 0}). Let R, - E Rr for some policy [T.). S&F shows that there exists policy क E Î. such that R. Ra. Let ((T) be the number of recurrent classes for P and let = (T). Denote the set of recurrent classes of Px as {Rea 1, ,n, The following lemma shows that the solution set of equation 23 has n, degrees of freedom.
Lemma If the SMDP is ceak)y-commmnicatingg suppose v and v + x are both solutions of equation 23, then there exists constants y1, "*. ,Un. such that
xrs)) Va. i E Ria:
1....,
(29)
rrs) = max b(, sefl
+ Σ
Σ (s) s'ER.o
ya. s SE S,R.
(30)
B=1
ya 2 Zzb(U.
+
Σ
Σ S'ER,
poe pro (8,5))
y8, a= n.,8 8 Roo, E f.
(31)
8=1
}. note that there must exist policy π (B) such that R.g is the only one recurrent class under 7t (5). To see this point, note that the SMDP is veakly-communicatingg and thus we can modify π to obtain new policy such that all states except for those in R.g are transient. Such policy satisfies our requirement.
For any 3 E {1,
Applying this observation and Lemma 2, for any V, we have for any given 3 E (1.....n.),
ya 2 max oE R... (( +
Σ
poe Pr(os (s, ('
S'ER.g
max eE
y3s va= 1, .
The first term maX b(U, T TB)) is a constant given v and π (.). Therefore we see that, for any other solution + of equation 23, if yo is arbitrarily large then ya a 1.... n, should also be arbitrarily large. This would violate the Lipschitz assumption on f. To see this point, let
f(e) = f(F Pu).
(32)
7

---

Under review as a conference paper at ICLR 2023
Let L be the Lipschitz constant of f. L is also the Lipschitz constant of f because P is stochastic matrix and is thus a non-expansion. Fix 11 E V. and choose a 82 E V0 de- note ||uı 82|1- Choose sufficiently large d > 0 such that ad
||e, de 22ll L L + de 02 dell Lm, where 02 = 02 + de. Because f(vi + de) f(vi) + sd, [(e] + de) f((z)] [((1) + kd - f(02)) kd L |l0 + de 02/1, which violates the Lipschitz assumption. Because the choice of 3 arbitrary, Voo upper bounded.
In addition, because the choice of is arbitrary, have for any a E fI,...,,7 n
2 max max BE (........ sER
+ U/
Yo is chosen be arbitrarily small then y should also be arbitrarily small for all [ 8= =1 1,... n, but again this is not allowed due to equation 24 for the same reason. Therefore ya V a E {l,.... nn, can not be arbitrarily small. Thus Voc is lower bounded. Combining the upper bound and lower bound, >o is bounded. Therefore Coo is also bounded.
Connectedness
We now show that 2x is connected. To this end, again it is enough to show that V. is connected.
Define function that maps from any v E V to a solution in V/ Specifically, fix c, let g - Voc with (v)) v ze, where æ is the solution of f(r + xe) and f is defined in equation 32. Note that x is unique given v because f(v + xe) = f(v) + e and x (c f(v))/K.
We now show that g is Lipschitz continuous. Consider any U1 0/ E V. Let 2 12 satisfy + IIC g(v)) and 02 + T2E = g(v2) respectively. Again æ 22 are unique given 11, 02. Note that
f(11 + zıe) - f(v2 + xie)
= f((1 + +z1e) f(12 + xze) + 21 22
c c c+ 11 22
= x2
| 52l
|f(u) x1e) [122 + me))
S L |lu1 + I1 - 0/2 æıel
L |lu u2ll
(1a(v1) - g(v2)) || = ||u + rie - 0/2 xzell < || - ozll + | xzell = (L|S) + [|u v2ll-
Therefore g is Lipschitz continuous with Lipschitz constant L|S] + 1.
Finally, because V is connected and the image of any continuous function on a connected set is connected, g(V) is connected. Note that every point in g(V) belongs to Voo by definition. Every point in Vxo is also a point in g(V). To see this point, pick any x E Vos we can see that x E V and that g(x)
Therefore V.o g(V) is connected.
Given that Voe is connected, Qox should also be connected because Qoo is a linear transformation of Voo (see Equation 25).
The other result we will need to use to show convergence of the four algorithms introduced in the previous section is the following one. With this result, the stability of the algorithms can be established using the result by Borkar and Meyn (2000) (see also, Section 3.2 by Borkar 2009).
Lemma 3. If an SMDP is seeakly-commmicattiin and all rewards are 0. 0 is the only element in Q.c-
Proof. Given a communcacmmiii SMDP, by Lemma 1, any solution of the state-value optimality equation equation 23 satisfies
(ss) 2 Σ
(8)8))) R, E fT
R'
8

---

Under review as a conference paper at ICLR 2023
where R. is defined right after Lemma 1. Also, because all rewards are 0, R. is the closed communi- cating class and IT. IT contains all stationary policies.
solution of equation 23. Now pick arbitrary policy π I.. Consider every recurrent class C' under Pr,, we have V 8 E C, (s( 2 Exec di (s')). where de denotes the stationary distribution of π in the recurrent class C. Sum both sides over s weighted by de (s')e,
Denote
E. ( (s)v. 2 E. de (s) Evec ( (s')) Ev de (a
Because l.h.s. r.h.s.
we have U4 (s) = EoEE (s')o Therefore v, (s) = U. s, s' E C.
Now for any 8, E R. there must exists E II, Ni such that there is a path from to 8' and a path from to 8, because 8, are in the same communicating class. Therefore s, are in the same recurrent class under Ps. Thus we conclude that v. (s')'). Therefore V s E R. (s(s) = U. (s').. The transient states values are uniquely determined by values of states in R.. Thus the solution set of v in the value optimality equation equation 23 is also unique up some additive constant.
The solution set of the option- option-value optimality equation equation 4 is also unique up to some additive constant. To see this point, let o(s) max. q(8, o), then equation 4 transforms to the state-value optimality equation. Therefore the solution of q in equation 4 satisfies that max, q(:; o) is unique up to an additive constant. Let be solution, 01) = (s, 02), V E S, 01, O2 E A because s, E S,05 O:
(s,0)) = Ems', 8,0) ma (s',o')
max q. (8, o'
Together with equation 22, the solution of q is uniquely determined. To that is the unique solution of q. we can just verify that 0 is a solution of q in equation 2 and equation 22. The lemma is proved.
PROOF SKETCH OF THEOREM 1-THEOREM 4
In this section, we sketch the proof of Theorem 1-Theorem 4. It has been shown that all four algorithms introduced above are special cases of the General RVI algorithm (Wan et al. 2021a,b). They also showed that General RVI Q converges under an assumption that is not satisfied for weakly-communicating MDPs/SMDPs. In order to show convergence for weakly-communicaung MDPs/SMDPs, we replace this assumption with three weaker assumptions that are satisfied for these MDPs/SMDPs. All other assumptions are the same as those used by Wan al. (2021a,b) and can be verified for all four algorithms using their arguments. We present General RVI Q and prove its convergence with the three new assumptions in Appendix A.6. The next step of the proof would be verifying the three new assumptions when casting General RVI Q to each of the four algorithms. This should be straightforward given our Theorem 5 and Lemma 3. We delay this part to Appendix A.7. With the three assumptions hold we have the conclusion part of the convergence theorem of General RVI Q holds for each of the four algorithms. The convergence of the reward rates of greedy policies w.r.t. the action/option-valll values follows the convergence of these values and is shown in Appendix A.8.
6 CONCLUSIONS
In this paper, we provide, for the first time, convergence results of off-policy average-reward control algorithms in weakly-communicating MDPs, which are known to be the most general class of MDPs in which it is possible that a learning algorithm can guarantee obtaining an optimal policy. Specifically, show two existing algorithms, RVI Q-learning and Differrntial Q-learning converge in seeakly-communicating MDPs. As an extension, we also showed two off ofl-colicy average-reward options learning algorithms converge if the SMDP induced by the options is weakly-communicating.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Abounadi, J., Bertsekas, D., Borkar, (2001). Learning Algorithms for Markov Decision
Processes with Average Cost. SIAM Journal on Control and Optimization.
Bertsekas, D. P. (2007). Dynamic Programming and Optimal Control third edition, volume II. Athena Scientific.
Bertsekas, D. P., Tsitsiklis, J. N. (1996). Neuro-dynamic Programming. Athena Scientific.
Borkar, V. S. (1998). Asynchronous Stochastic Approximations. SIAM Journal on Control and Optimization.
Borkar, V. S. (2009). Stochastic Approximation: A Dynamical Systems Viewpoint. Springer.
Das, T. K., Gosavi, A., Mahadevan, S. Marchalleck, N. (1999). Solving semi-Markov decision
problems using average reward reinforcement learning. Management Science.
Gosavi, A. (2004). Reinforcement learning for long-run average cost. European Journal of Opera- tional Research.
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.
Ren, Z., Krogh, B. H. (2001), Adaptive control of Markov chains with average cost. IEEE Transac- tions on Automatic Control.
Schwartz, A. (1993). A reinforcement learning method for maximizing undiscounted rewards. In Proceedings of the International Conference Machine Learning.
Schweitzer, P. J. (1971). Iterative solution of the functional equations of undiscounted Markov renewal programming. Journal of Mathematical Analysis and Applications.
Schweitzer, P. J., & Federgruen, A. (1978). The Functional Equations of Undiscounted Markov Renewal Programming. Mathematics of Operations Research.
Singh, P. (1994). Reinforcement learning algorithms for werage-payole Markovian decision processes. In Proceedings of the AAAI Conference Artificial Intelligence.
Sutton, R. S., Precup, D., Singh, S. (1999). Between MDPs and Semi-MDPs: Framework for Temporal Abstraction in Reinforcement Learning. Artificial Intelligence.
Sutton, R. S., Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press.
Wan, Y., Naik, A., Sutton, R. S. (2021a). Learning and Planning in Reward Markov Decision Processes. International Conference on Machine Learning.
Wan, Y., Naik, A., Sutton, R. S. (2021b). Average-Rewart Reward Learning and Planning with Options. Conference on Neural Information Processing Systems.
10


Reviews:
[{"review_id": "q1rmsw8Wpt", "reviewer": "Reviewer_fj9u", "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": "This paper studies the convergence of off-policy algorithms, which learn a policy that optimizes the average-reward rate using data generated by some other non-controlled policy, for weakly-communicating MDPs, the most general set of MDPs that allow for a learning algorithm that can find under experience a policy of optimal average reward rate. In these MDPs, policies may induce multiple recurrent classes, while some states are transient, while others are reachable from any other state within finite steps. The paper presents results that prove convergence for two learning algorithms, RVI Q-learning and Differential Q-learning, in such MDPs, in a more general setting than has been shown so far. ", "summary_of_the_review": "The achievement of the paper relies on two steps: first, showing that solution sets are non-empty, closed, bounded, and connected; then showing that 0 is the solution to the Bellman equation under rewards 0. Utilizing previous work by Borkar, the convergence results follows. The result goes beyond previous work in that those previous proofs required that all optimal policies induce unichains, which is not always the case in a weakly-communicating MDP. The results are theoretically sound. A discussion on the practical relevance and empirical performance would strengthen the paper.", "strength_and_weaknesses": "Strength:\nExtension of convergence results under fewer assumptions.\n\nWeakness:\nLack of empirical demonstration of performance gains.", "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": "nR8OCx_IRDj", "reviewer": "Reviewer_9oBN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper examines the convergence properties of existing RL algorithms for the average reward setting when the MDP satisfies a weaker-than-standard assumption on state visitation.  It requires only weak communication, which means that a subset of states is communicating while others may be transient.  For average-reward methods in particular this in introduces technical challenges because the Q-value function is no longer uniquely defined (up to a constant).  The main result is a proof that 4 algorithms known to converge under stronger assumptions also converge in the weakly-communicating setting.  ", "summary_of_the_review": "My scores are based on the current draft of the paper with is hard to follow and lacks specificity about the contribution.  I would be much more positively disposed to a substantial rewrite which successfully addresses these issues.", "strength_and_weaknesses": "Describing the strengths of this paper is a bit challenging, in part because I find it lacking in clarity (see below).  There are several things I think I (might) like about the paper, but I am uncertain about how much I like any of them:\n\n1) Extension of prior convergence results to the weakly-communicating setting.  Greater generality is certainly nice from a theoretical perspective, but how much should I care about this result?  The introduction asserts that “it is not rare that an optimal policy introduces multiple recurrent classes”, which would certainly make the extension quite relevant, but the only evidence presented for it seems to be the toy example from Figure 1 and a single citation to Bartlett & Tewari 2009 which is about the generality of this class rather than its importance.  More broadly, the paper is missing any discussion of prior work on weakly-communicating MDPs.\n\n2) Novelty of the technical analysis.  I’m a bit confused because the pitch of the paper is around the weakly communicating setting but Theorem 1 talks about the communicating setting with remark 1 saying weakly-communicating is a minor extension there as well in Theorems 2-4 (which are stated the same way).  From the sketch in 5 and taking a look at the appendix I see that the proof strategy uses the largely the same assumptions as Wan et al. (2021a,b) but replaces their assumption A.8 with new assumptions 9-11.  My guess as to why things are stated the way that they are is that these variant assumptions necessitate some changes to the proof for the communicating case, but as a benefit more easily extend to the weakly-communicating case.  I’m not clear how much a technical delta this represents, as the proofs in the appendix reference the Wan et al. proofs heavily.  I could be convinced (and in fact it seems likely) that there are some non-trivial ideas here, but the paper would need to clearly explain what they are.\n\nThis lack of clarity in both the overall exposition and in particular for the articulation of the contribution is the main weakness of the paper.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Vzna1xLMN3", "reviewer": "Reviewer_8rbg", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 studies the performance of differential Q-learning and RVI Q-learning for average-reward weak-communicating MDP.  Main contribution: the authors show that with proper learning rates, the two algorithms converges to the optimal q function (or bias function) assuming that each state-action (state-option) are sufficiently visited.", "summary_of_the_review": "Currently, the paper does not reach the bar of ICLR in my opinion. My score is 3 and I am willing to increase the score if the author can prove under a weaker assumption. And it would also interesting to find the sufficient and necessary conditions for the trajectory $(S_t,A_t)$ $(t\\geq 1)$ to make the two algorithms converge (assume that the learning rates are properly chosen).", "strength_and_weaknesses": "Strength: Compared to (Wan et. al., 2021a), the proposed analysis works for general weak-communicating MDPs.\n\nWeakness: \n1) The assumptions are too strong to make the theoretical results significant. In particular, in Assumption 4 the authors assume a general coverage ratio for the offline dataset, while in related offline RL papers (e.g., Jin et. al.), it is sufficient to assume a coverage ratio with respect to a optimal policy.\n\n2) The paper is not self-contained. For example, the full proof of Theorem 1 is not presented. I understand that the proof might be very similar to that in (Wan et. al.), but I still suggest the authors to present the full proof or the high-level ideas.\n\nReference: Is Pessimism Provably Efficient for Offline RL (Jin et. al.)", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject