Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards
Authors: Xuan-Bach Le
Dominik Wagner
Leon Witzman
Alexander Rabinovich
Luke Ong
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
LTL
limit average rewards
translation
Primary area: reinforcement_learning

Abstract: Linear temporal logic (LTL) and, more generally, $\omega$-regular objectives are alternatives to the traditional discount sum and average reward objectives in reinforcement learning (RL), offering the advantage of greater comprehensibility and hence explainability. In this work, we study the relationship between these objectives. Our main result is that each RL problem for $\omega$-regular objectives can be reduced to a limit-average reward problem in an optimality-preserving fashion, via (finite-memory) reward machines. Furthermore, we demonstrate the efficacy of this approach by showing that optimal policies for limit-average problems can be found asymptotically by solving a sequence of discount-sum problems approximately. Consequently, we resolve an open problem: optimal policies for LTL and $\omega$-regular objectives can be learned asymptotically.

Reinforcement Learning with LTL and w-Regular Objectives via Optimality-Preservvv Translation to Average Rewards
Xuan-Bach Le
Dominik Wagner
Leon Witzman Alexander Rabinovich" Luke Ong'
NTU Singapore
TTel Aviv University
{bach. 1e, dominik. wagner, www.nlleeeonn/.... ongu edu. sg
witz0001 Ce. ntu. attu.edu.sg. rabinoa@tauex. tau. ac.
Abstract
Linear temporal logic (LTL) and, more generally, w-regular objectives are alterna- tives to the traditional discount sum and average reward objectives in reinforcement learning (RL), offering the advantage of greater comprehensibility and hence ex- plainability. In this work, we study the relationship between these objectives. Our main result is that each RL problem for w-regullar objectives can be reduced a limit-average reward problem in an optimality-preservin memory) reward machines. Furthermore, we demonstrate the efficacy of this approach by showing that optimal policies for limit-average problems can be found asymptotically by solving a sequence of discount-sum problems approximately. Consequently, we resolve open problem: optimal policies for LTL and w-regular objectives can learned asymptotically.
fashion, via (finite-
Introduction
Reinforcement learning (RL) is machine learning paradigm whereby an agent aims to accomplish task in a generally unknown environment [37]. Traditionally, tasks are specified via scalar reward signal obtained continuously through interactions with the environment. These rewards are aggregated over entire trajectories either through averaging or by summing the exponentially decayed rewards. However, in many applications, there are no reward signals that can naturally be extracted from the environment. Moreover, reward signals that supplied by the user are prone error in that the chosen low-level rewards often fail to accurately capture high-level objectives. Generally, policies derived from local rewards-based specifications hard to understand because it is difficult to express or explain their global intent.
As remedy, it has been proposed to specify tasks using formulas in Linear Temporal Logic (LTL) 41 30 9 38 15 [4] or w-regular languages more generally [30]. In this framework, the aim is to maximise the probability of satisfying a logical specification. LTL precisely express wide range of high-level behavioural properties such as liveness (infinitely often P), safety (always P), stability (eventually always P), and priority (P then then T).
Motivated by this, growing body literature study learning algorithms for RL with LTL and w-regular objectives (e.g. [1 [15
30 7 32 20 21 [6]). However, to the best of our knowledge, all of these approaches may fail to learn provably optimal policies without prior knowledge of generally unknown parameter such the optimal e-return mixing time [1 or the e-recurrence time [30]
These authors contributed equally to this work.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

which depend on the (unavailable) transition probabilities of the MDP. Moreover, it is known that neither LTL nor (limit) average reward objectives are PAC (probably approximately correct) learnable [2 Consequently, approximately optimal policies can only possibly be found asymptotically but not in bounded time.
In this work, we pursue a different strategy; rather than solving the RL problem directly, we study optimality- translations [2] from w-regular objectives to more traditional rewards, in particular, limit-average rewards. This method offers a significant advantage: it enables the learning of optimal policies for w-regular objectives by solving a single more standard problem, for which we can leverage existing off-the-shelf algorithms (e.g. [26 15 30). In this way, all future advances in both theory and practice- for these much more widely studied problems carry over directly, whilst still enjoying significantly more explainable and comprehensible specifications. It is well-known that such translation from I.TI. to discounted rewards is impossible 2]. Intuitively, this because
the latter cannot capture infinite horizon tasks such as reachability or safety 22 42 19. Hence, we
instead investigate translations to limit-average rewards in this paper.
Contributions
We study reinforcement learning of w-regular and LTL objectives in Markov decision processes (MDPs) with unknown probability transitions, translations to limit-average reward objectives and learning algorithms for the latter. In detail:
1. We prove negative result (Proposition 4
in general it is not possible to translate w-regular objectives limit average objectives an aptimality-preservinn manner if rewards are memoryless (i.e., independent of previously performed actions, sometimes called history- free or Markovian).
2. On the other hand, our main result (Theorem 12) resolves Open Problem I in [2]: such an optimality- preeeering translation is possible if the reward assignment may use finite memory
as formalised by reward machines [23] 24
3. To underpin the efficacy of our reduction approach, we provide the first convergence proof (Theorem 16) of an RL. algorithm (Algorithm [ for average rewards. To the best of our knowledge (and as indicated by (3),, this is the first proof without assumptions on the induced Markov chains. In particular, the result applies to multichain MDPs, which our translation generally produces, with unknown probability transitions. Consequently, we also resolve Open Problem 4 of 2 RL for w-regular and LTL objectives can be learned in the limit (Theorem) 18
We start by reviewing the problem setup in Section 2 Motivated by the impossibility result for simple reward functions, we define reward machines (Section 33. In Section 4 we build intuition for the proof of our main result in Section [ Thereafter, we demonstrate that RL with limit-average, w-regular and LTL objectives can be learned asymptotically (Section G). Finally, we review related work and conclude in Section 7
Outline.
Background
Recall that Markov Decision Process (MDP) is tuple M (8, so, P) where S is a finite
set of states, so E S is the initial state, A is the finite set of actions and P : S x A x - [o. 1]
is the probability transition function such that Exs P(s, 5')
for every E S and E A.
MDPs may be graphically represented; see e.g. Fig. la We let Runs (S, A) = S x (A x S)* and Runs( (S, A) = (S x A) denote the set of finite runs and the set of infinite runs in M respectively.
A policy π: : Runsa (S, A) + D(A) maps finite runs to distributions over actions. We let IT(S, A) denote the set of all such policies. A policy æ is memoryless if TT (T ... ...) =8%62/ ... s,m) for all finite runs $000 sy and sha6.... ... S'm such that 8n = s',- For each MDP M and policy π, there a natural induced probability measure D&M on its runs
The desirability of policies for a given MDP M can be expressed as a function J II(S, A) + R. Much of the RL literature focuses discounted-sum JM and limit-average reward objectives JEh..
Formally, for some c, 8 > 0 is impossible to learn e-approximately optimal policies with probability 1 - 8 in finite time.

---

b
start
50
$1
{p}
{p}
start
40
q1
92
(a) An MDP where all transitions occur with probability 1, M(5, s1) {p} and the rest are labeled with 0.
(b) A DRA, where F
{(fg) }, 0)), for the objective visit the petrol station p exactly once.
Figure 1: Examples of an MDP and DRA.
which lift reward function R: A S R for single transitions to runs p 80008141 ... as follows:
TRe = E DD
Σ 7/
T (T) == lim inf p- DM
Ti
(-000
1=0
1=0
where 7; = R(si, ai s1+1) and yy E (0, 1) is the discount factor.
w-RReglarr Objectives. w-regular objectives (which subsume LTL objectives) are an alternative to these traditional objectives. Henceforth, fix an alphabet AP and label function S X 2AP for transitions, where 2x is the power set of set X. Each run
8y00$1 @1 ... induces sequence of labels X(p) ((sg. an, $1) 11)A(s1, 01, $2) .... Thus, for set S (2-P)" of "desirable" label sequences we can consider the probability of run's 's labels being in that set: F PPDDA (A(p) E L].
For instance, an autonomous may want to "visit petrol station exactly once" to conserve resources (e.g. time or petrol). Consider the MDP in Fig. Ia where the state 81 represents a petrol station. We let AP {p} (p for petrol), X(so, b, $1 {p}, and the rest are labeled with 0. The desirable label sequences are (A1A2 for exactly one N, A; = {p}}.
Example 1.
In this work, we focus on which are w-regular languages. is well known that w-regular languages precisely the languages recognised by Deterministic Rabin Automata (DRA) (2 29
Definition 2. A DRA is tuple A = (Q,24P -0. 8, F) where Q is finite state set, 2 is the alphabet, Qo E Q is the initial state, 5 Q x 2AP + Q is the transition function, and F {(A1, R.),..., (An, R,)), where Ai, R2 C. Q. is the accepting condition. Let p E (24P)a be an infinite run and InfS(p) the set of states visited infinitely often by p. We say P is accepted by A if there exists some (A, R&) F such that p visits some state in A; infinitely often whilst visiting every state in R₁ finitely often, i.e. InfS(p) O A; # @ and InfS(p) O RR = 0.
For example, the objective in Example may be represented by the DRA in Fig. 1b
Thus, the desirability of is the probability of generating accepting sequence in the DRA A:
(T) == PP-DA (X()) is accepted by the automaton A]
(I)
Remarks. The class of w-regular languages subsumes languages expressed by Linear Temporal Logic (LTL, see e.g. [4] Ch. 5]), a logical framework which e.g. reachability (eventually P. P), safety (always P. P) and reach-avoid (eventually P whilst avoiding Q, (-Q) 2 P) properties can be expressed concisely and intuitively. The specification our running Example visit the petrol station exactly once can be expressed the LTL formula (-p) U (p O--)). where OQ denotes "Q holds at the next step". Furthermore, our label function X, which maps transitions to labels, is more general than other definitions (e-g. [4 15 30) instead mapping states labels. As result, we are able to articulate properties that involve actions, such as "to reach the state while avoiding taking the action a".
Optimality- -rreeervity- Specification Translations. Rather than solving the problem of synthe- sising optimal policies for Eq. (I) directly, we are interested in reducing it to more traditional RL
3

---

problems and applying off offtthe-shelf RL algorithms to find optimal policies. To achieve this, the reduction needs to be optimality preserving
Definition 3 ((2). An optimality-peexevinng specification translation from w-regular objectives to limit-average rewards is a computable function mapping each tuple (S, A, X, A) R.S.A.A..))
policies maximising JR also maximise JAM where R (A.A.)
for every MDP M = (S, A, sp. P), label function À S x A x 5 - 2-4P and DRA A.
We stress that since the probability transition function P is generally not known, the specification translation may not depend on
3 Negative Result and Reward Machines
Reward functions emit rewards purely based on the transition being taken without being able to take the past into account. On the other hand, DRAs have finite memory. Therefore, there cannot generally be optimality-preseriing preserving translations from w-regular objectives to limit average rewards provided by reward functions:
Proposition 4. There is an MDP M and an w-regular language L for which it is impossible to find S- such that every IRmm optimmal policy of M also maximises the probability of membership in L.
a reward function R S x A
Remarkably, this rules out optimality-preserving specification translations even if transition probabili- ties are fully knowr
Proof. Consider the deterministic MDP in Fig. and the objective of Example I "to visit $1 exactly once" expressed by the DRA A in Fig. lb Assume towards contradiction there exists reward function R: S x A x 5 - lR such that optimal policies w.r.t. TRhh maximise acceptance by A. Note that every policy x¹ maximising acceptance by the DRA induces run 80(a8)) "bs bsg (asp) for some n N, and JA((T) Now, consider the policy и always selecting action a with probability 1. As the run induced by i is (a(s))) deduce that JMM (Tr) 0 and JM (T) R( a, 50) J&hs (T*), which is contradiction since is not J -optimal.
1. Thus, its limit-average reward is J&h (x*) = R. a, 80).
Since simple reward functions lack the expressiveness to capture w-regular objectives, we employ generalisation, reward machines 23 24), whereby rewards may also depend on an internal state:
Definition A reward machine (RM) states, E U is the initial state, 8, U x (S A x S) + R is the reward function, and S, : (S A S) U is the update function.
tuple (U, up, dus 8+) where U is finite set of
Intuitively, a RM R utilises the current transition to update its states through d, and assigns the rewards through 5,.. For example, Fig. 2a depicts reward machine for the MDP of Fig. la where the states count the number of visits to $1 (0 times, once, more than once).
Let Sp0031 ... be an infinite run. Since 5n is deterministic, it induces sequence ug of states R, where e (8s, Ges 8141) and u;+1 5u (ui, ex). The limit-average reward policy m is defined as:
J = lim inf EOWDA t-000
1 +
Σ
8, es)
It is seen that limit-average optimal policies n" for the MDP in Fig. la and the RM in Fig. 2a eventually select action b exactly once state so to achieve M
In the following two sections, we present general translation from w-regular languages to limit-
average reward machines, and we show that our translation is optimality-preserrae preserving (Theorem 12)
"This definition makes sense both for the case of reward functions R.S.A.A.4)) S A x Lt and reward machines (introduced the subsequent section).
'I Appendix A we show another negative result (Proposition even for a strict subset of w-regular specifications such translations impossible.

---

b
(su, a, 80)/0
(#0, a, 80)/ /
+/0
start
880 Qo
80 F1
80x 92)
b
(so, b, 81)/0
(a0, b, 81)/0
b"
b
start
M1
U2
81, [81, 91
81, 92)
(81, b, so)/0
(s1, b, su)/O
(b) Product MDP for Fig. where all transitions have prohability and FM = {({(so q1), (11, 0)}-
(a) reward machine for the objective of visiting petrol station exactly once. (The rewards are given following "!".)
Figure A reward machine and the product MDP for the running Example
Remarks. Our definition of RM is more general than the one presented in 23 where 8 A U + [S x A x S + IR and 8 : U x 2 - U. Note that (6 8,) can be reduced to (6 6,) by expanding the state space of the RM to include the previous state and utilising the inverse label function -- It is worth pointing out that Theorem 12 does not contradict a negative result in 2 regarding the non-existence of limit-average reward machines (where only the label of transitions is provided to 6, and 8,).
translation from LTT. constraints to abstract
4 Warm-Up: Transitions with Positive Probability are Known
To help the reader gain intuition about our construction, we first explore the situation where the support {(s, s') E S x A x $ P(s, s') > 0} of the MDP's transition function is known. Crucially, we do not assume that the magnitude of these (non-zero) probabilities are known. Subsequently, in Section 5 we fully eliminate this assumption.
This assumption allows to draw connections between our problem and familiar scenario in probabilistic model checking 44 Ch. 10], where the acceptance problem for w-regular objectives can be transformed into a reachability problem. Intuitively, our reward machine monitors the state of the DRA and provides reward 1 if the MDP and the DRA are in certain "good" states (0 otherwise).
For the rest of this section, we fix MDP without transition function (S, A, so), transitions C 5 x A S, label function À S A + 2-AP and a DRA A = (Q, 2AP, 90. 8, F). Our aim is to find reward machine R such that for every transition function P compatible with E (formally: E = {(s, o, s') P(s, a, 8') > 0)), optimal policies for limit-average rewards are also optimal for the acceptance probability of the DRA A.
of possible
4.1 Product MDP and End Components
First, we form the product MDP M & (e.g. 41 15D, which synchronises the dynamics of the MDP M with the DRA A. Formally, M @ A (V, A, vo. A, FM) where V = x Q is the set of states, is the set of actions, up (8p, Qo) the initial state. The transition probability function
A V x A x V + [0, satisfies A(v, a, v²)
P(s, s') given that FM = {(4,, R²),
(s. (s.g). v' (s',4"),
and 8(q, \(s, a, 8)))
q- The accepting condition
(,),((1) (A', RC ..... where
A = S x A, R = S x R, and (A, R,) E F. A run (So. 00000000000000 is accepted by M & A there exists some (A), RR) E FM such that InfV n AG o and InfV n R2 = where InfV the set of states (s, v) in the product MDP visited infinitely often by p.
Note that product MDPs have characteristics of both MDPs and DRAs which neither possesses in isolation: transitions are generally probabilistic and there is notation of acceptance of runs. For example, the product MDP for Fig. [is shown in Fig. 2b Due to the deterministic nature of the DRA A. every run in M gives rise to a unique run p in M X A. Crucially, for every policy x.
P PP-DA (p is accepted by A] I p Jp is accepted by A @ A]
(2)
We make use of well-known almost-sure characterisation of accepting runs via the notion of accepting end components:
5

---

Definition 6. An end component (EC) of M @ A AV,V, vo, A, FM) is pair (T, Act) where T S V and Act
2 satisfies the following conditions
1. For every v E T and a E Ac((v), we have EVEr Al,, v²) = 1, and
2. The graph (T, Act) is strongly connected, where Act of iff A (v,a,,) > 0 for some a E Act(u).
(T, Act) is accepting EC (AEC) if A' + 0 and T'n R = 0 for some (Ai, Rt) E FM-
Intuitively, an EC is a strongly connected sub-MDP. For instance, for the product MDP in Fig. 2b there are five end components, ({(5o, (so, qu) J {a}), (f(so: 91)), (s0. (1) + {a] (5(50:90 (200022))
92) }. (30, 92) + {at), (1(50, (2)) (5o, 92) + {b}) and ({(50, 92) (80, 92) + {a,b}) 6)). (((s0: 21 } (50: 91 + {a}} its only accepting end component.
turns out that, almost surely, run is accepted iff it enters an accepting end component and never leaves it M. Therefore, natural idea for reward machine is use its state to keep track of the state 9 E Q the DRA is and give reward to transitions (s, a, s') if (s, q) is in some AEC (and O otherwise). Unfortunately, this approach falls short since the AEC may contain con-accepting ECs, thus assigning maximal reward to sub-optimal policies f As a remedy, we introduce notion of minimal AEC, and ensure that only runs eventually committing limit-average reward of 1.
such minimal AEC get
Definition 7. An AEC (T, Act) an accepting simple EC (ASEC) if Act(v)) = -1 for every v E T.
Let C1 = (Ti, Act1), ..... ......,G, C,, (Tn, Act,,) be collection of ASECs covering all states in ASECs, ie. (s,g) is in some ASEC then (s, q) E Ti U... U Tn. In particular, n S | x Q] is sufficient.
We can prove that every AEC contains ASEC (see Lemma 20 in Appendix B). Consequently, Lemma 8. Almost surely, if p is accepted by A then p8 reaches state in some ASEC C, of M & A.
4.2 Reward Machine and Correctness
Next, ensure that runs eventually commit to one such ASEC we introduce the following notational shorthand: for (s,4) E Ti U...U let C(n.g) = (T(s.) (ct().)) be the C, with minimal i containing (s, q). i.e. C(s.g) == Cumn(1siSml(e.))e..
Intuitively, we give reward of if (s, q) is in one of the C,....,C, However, once an action is performed which deviates from Act(s.q) no rewards are given thereafter, thus resulting in limit average reward of
A state in the reward machine has the form q E Q, keeping track of the state in the DRA, or P, which a sink state signifying that in a state Ci...., . Cn we have previously deviated from Act( Finally, we are ready to formally define the reward machine R = R(S.AAX.A) exhibiting our specifi- cation translation as (Q UQUR (1), 4o 8n, 5,), where
uf= or ((s Ti U... UT, and & (st us)
(u,
8(u, ((s,a, otherwise
1 u 1 and (s, u) E Ti U.T
(s, = to otherwise
For our running example, this construction essentially yields the reward machine in Fig. 2a (with some inconsequential modifications cf. Fig. in Appendix (B).
Theorem 9. For all transition probability functions P with support E, policies maximising the limit-average reward w.r.t R also maximise the acceptance probability of the DRA A.
This result follows immediately from the following (the full proof is presented in Appendix B):
'To illustrate this point, consider the product MDP ((so, $1 (a, b). P. F) where P(so, b,) P(so, a, s1) P(si, a, so) = 1 and F {[{s1), 0)), ie. the objective visit sı infinitely often.

---

Lemma 10. Let P be probability transition function with support E and M = P).
1. For every policy n, Ihis (T) S (T).
2. For every policy there exists some policy n' satisfying ( S (Rmna'T)) (TT).
By construction, every run receiving a limit-average reward of 1, must have entered some ASEC C, and never left it. Furthermore, almost surely all states are visited infinitely often and the run is accepted by definition of accepting ECs.
Proof sketch. 1.
2. By Lemma 8 almost surely, run is only accepted if enters some C. We set n' to be the policy agreeing with и until reaching one of the CI,...,C C, and henceforth following the action ge) (St, qt), where q is the state of the DRA at step t, yielding a guaranteed limit-average reward of for the run by construction.
Remark 11. Our construction considers collection of ASECs covering all states in ASECs. Whilst does not necessarily require listing all possible ASECs but only (up to) one ASEC per state, is unclear whether this can be obtained in polynomial time. In Appendix B.I we present an alternative (yet more complicated) construction which has polynomial time complexity.
Main Result
In this section, we generalise the approach of the preceding section to prove our main result: Theorem 12. There exists prreserityy-reeevvingg translation from w-regular languages to limit- average reward machines.
Again, we fix an MDP without transition function (S, (,)), a label function À S A - 2-AP and DRA A = (Q. 2AP 6, F). Note that the ASECs of product MDP are uniquely determined by the non-zero probability transitions. Thus, for each set of transitions E S (S x Q) x A (S Q). we let CF (Ti, Act,) ..... C (Tn, Act,,) denote collection of ASECs covering all states in ASECs w.r.t. the MDPs which the set of non-zero probability transitions Then, for each set E and state (s, q) E T U... T,E we let (5.9) (T(=.)) Act be the ASEC C. that contains (s, q) in which the index i minimal.
Our reward machine R R(S.A.A.4) extends the ideas from the preceding section. Importantly, we keep track of the set of transitions E taken so far and assign rewards according to our current knowledge about the graph of the product MDP. Therefore, we propose employing states of the form (g, f. E), where E Q keeps track of the state of the DRA. f E {T. is a status flag and E (S Q) A (S x Q) memorises the transitions in the product MDP encountered thus far.
Intuitively. we set the flag to chosen action deviates from Act (x.)) (s, q). We can recover from by discovering new transitions. Besides, we give reward if f = T and (s, g) is in one of the CF ,.....,, C, (and 0 otherwise).
we are in MDP state s, (s, q) is in one of the Cf ....... C, and the
The status flag is required since discovering new transitions will change the structure of (accepting simple) end components. Hence, differently from the preceding section, it is not sufficient to have a single sink state.
The initial state of our reward machine ug = (go, T,0) and we formally define the update and reward functions as follows:
1 F) (L,1,E)
if f = and e e E
if f = T T. E E TF U... and
8,((g, (s.,,,,))
E (ct otherwise
(d, TV,TTEU(e)
{ if T T, ETP U... otherwise
where o' = 8(q, A(s, s')) and e = (lg, s), a, (g', s')).
"To achieve the same number of ASECs add duplicates. If there ASECs can set 2] := =0.
7

---

Example 13. For our running example (see Example 1 and Fig. D initially no transitions are known (hence no ASECs). Therefore, all transitions receive reward O. Once action a has been performed in state in the MDP M and (q1: S. E)) in the reward machine R, we have discovered the ASEC ({(s0: 91) 91)); (so, (8):()) + {a}) and a reward of is given henceforth unless action is selected eventually. In that case, we leave the ASEC and we will not discover further ASECs since there is only one. From here, it is not possible to return to state gi in the DRA and henceforth only reward 0 will be obtained.
Theorem i2 is proven by demonstrating an extension of Lemma 10 (see Appendix C
Lemma 14. Suppose M = (S, so, so, P) is an arbitrary MDP.
1. For every policy n, JR (T) S (T).
2. For every policy n, there exists some policy n' satisfying (TT S (T')
(TT).
Note that Lemmal 14 immediately proves that the reduction is not only optimality preserving (Theo- rem 12 but also robust: every e-approximately limit-average optimal policy is also e-approximately optimal w.r.t. JAM This observation is important because exactly optimal policies for the limit average problem may be hard to find.
Intuitively, to see part of Lemma 1e we note: If average reward of 1 is obtained for run, the reward machine believes, based on the partial observation of the product MDP, that the run ends up in ASEC. Almost surely, we eventually discover all possible transitions involving the same state-action pairs as this ASEC and therefore this must also be an ASEC w.r.t. the true, unknown product MDP. For part 2, we modify the policy π similarly as in Lemma I0 by selecting actions Act(s;, q:) once having entered an ASEC C = Act) w.r.t the true, unknown product MDP
6 Convergence for Limit Average, w- w-Regular and LTL Objectives
Thanks to the described translation, advances (in both theory and practice) in the study of RL with average rewards carry over to RL with w-regular and LTT. objectives. In this section, we show that it is possible to learn optimal policies for limit average rewards in the limit. Hence, we resolve an open problem 2 : also RL with w-regular and LTL objectives can also be learned in the limit.
We start with the case of simple reward functions R : S x A x S + R. Recently [8 Theorem 4.2] have shown that discount optimal policies for sufficiently high discount factor THE [0,1) are also limit average optimal 7 This result alone not enough to demonstrate Theorem 16 since - is generally not known and in finite time might only obtain approximately limit average optimal policies.
Our approach is to reduce RL with average rewards to a sequence of discount sum problems with increasingly high discount factor, which are solved with increasingly high accuracy. Our crucial insight is that eventually the approximately optimal solutions to the discounted problems will also be limit average optimal (see Appendix for proof):
Lemma 15. Suppose Tik / EN > and suppose each Tik is a memoryless policy. Then there exists Kn such that for all K 3 k 2 ko, Tik is limit average optimal, where K is the set of k E P satisfying JR (mx) 2 JRM (m) ))) Ck for all memoryless policies n.
Our proof harnesses yet another notion of optimality: policy π is Blackwell optimal (cf. [6] and (22, Sec. 8.1]) if there exists F E (0, 1) such that π is 7-discount optimal for all 7 S 7 < 1. is well-known that memoryless Blackwell optimal policies always exist 6 [8] and they are also
limit-average optimal 22 [8].
Thanks to the PAC (probably approximately correct) learnability of RL with discounted rewards 26 36), there exists an algorithm Discounted which receives as inputs a simulator for M, as well as 7,6 and 6, and with probability 1 5 returns an c-ottmall memoryless policy for discount factor y. In view of Lemma 15 our approach is to run the PAC algorithm for discount-sum RL for increasingly large discount factors and increasingly low 8 and c (Algorithm
'BB The modified policy depends on the true, unknown support of the probability transition function; we only claim the existence of such a policy.
Recall (see e.g. [22] Sec. 8. that for any policy E 11, lim, -n) J. - (1T)
8

---

Algorithm RL for limit average rewards
Require: simulator for M, R
for k E N do
+ Discounted M, R, 1-111111 1 1/k, 1/k. 1/k2)
end for
6%.
Theorem 16. RL with average reward functions can be learned in the limit by Algorithm almost surely there exists Ko E N such that is limit-ave average optimal for k 2 Ko-
Proof. Using the definition for K of Lemma 15 of iterations where the PAC-MDP algorithm succeeds,
E (
K)J S
Σ
P/PAC-MDP fails in iteration k] S
Σ
6N
Σ REN
00
1:2
KEN
KEN
The claim follows immediately with Lemma
15
Next, we turn the more general case of reward machines. 22 24 reward machines can be learned by learning optimal policies for the modified MDP which additionally tracks the state the reward machine in and assigns rewards accordingly. We conclude once:
observe that optimal policies for
Corollary 17. RL with average reward machines can be learned in the limit.
Finally, harnessing Theorem 12 we resolve Open Problem 4 of 2
Theorem 18. RL with w-regular and LTL objectives can be learned in the limit.
Discussion.
Algorithm I makes independent calls to black box algorithms for discount sum rewards.
Many such algorithms with PAC guarantees are model based (e.g. [26] (3)) and sample from the MDP to obtain suitable approximations of the transition probabilities. Thus, Algorithm [ can be improved in practice by re-using approximations obtained in earlier iterations and refining them.
7 Related Work and Conclusion
The connection between acceptance of w-regular languages in the product MDP and AECs is well- known in the field of probabilistic model checking [4] 12]. As an alternative to DRAs 41 14 32).
Limit Deterministic Büchi Automata (35 have been employed express w-regular languages for RL.
38 7
10
20 21)
A pioncering work on RL for w-regular rewards is 41). which expresses w-regular objectives using Deterministic Rabin Automata. Similar RL approaches for w-regular objectives can also be found in [14 38 10 [5]. The authors of [15 30 approach RL for w-regular objectives directly by studying the reachability of AECs in the product MDP and developing variants the R-MAX algorithm [8] to find optimal policies. However, these approaches require prior knowledge of the MDP, such as the structure of the MDP, the optimal e-return mixing time [1), or the e-recurrence time (30]
Various studies have explored reductions of w-regular objectives to discounted rewards, and sub- sequently applicd Q-lcarning and its variants for learning optimal policies 77] 32 20 2n [6). In
similar spirit, [39 present translation from LTL objectives to eventual discounted rewards, where only strictly positive rewards are discounted. These translations are generally not optimality preserv- ing unless the discount factor is selected in suitable way. Again, this is impossible without prior knowledge of the exact probability transition functions in the MDP.
25 propose translation to limit-average rewards for w-regular specifications which are also absolute liveness properties. (In particular, optimal policies satisfy such specifications with either probability 0 or 1.) Their translation is pppemality-preserving provided the MDP is communicating and the magnitute of penalty rewards in their construction are chosen sufficiently large (which requires knowledge of the MDP).

---

Furthermore, whilst there are numerous convergent RL algorithms for average rewards for unichain or communicating MDPs (e.g. 8 +
I7
33
40) ) unknown whether such an algorithm
exists for general multichain MDPs with guaranteed convergence property. In fact, negative result in 22 shows that there no PAC (probably approximately correct) algorithm for L.TI. objectives and limit-average rewards when the MDP transition probabilities are unknown.
8 have proposed an algorithm with PAC guarantees provided e-return mixing times are known. They informally argue that for fixed sub-optimality tolerance e, this assumption can be lifted by guessing increasingly large candidates for the e-return mixing time. This yields e-approximately optimal policies in the limit. However, it is not clear how to asymptotically obtain exactly optimal policies as this would require simultaneously decreasing and increasing guesses for the e-return mixing time (which depends on e).
Conclusion. We have presented an citimallty--reservinn translation from w-regular objectives to limit-average rewards furnished by reward machines. As a consequence, off-the-shelf RL algorithms for average rewards can be employed in conjunction with our translation to learn policies for w-regular objectives. Furthermore, we have developed an algorithm asympiotically learning provably optimal policies for limit-average rewards. Hence, also optimal policies for w w-regular and LTL objectives can be learned in the limit. Our results provide affirmative answers to two open problems in [2].
Limitations. We focus on MDPs with finite state and action sets and assume states are fully observable. The assumption of Section that the support of the MDP's probability transition function known is eliminated in Section [S] Whilst the size of our general translation-thh first optimality- preserving translation-a is exponential, the additional knowledge in Section 3 enables a construction of the reward machine of the same size as the DRA expressing the objective. Hence, we conjecture that this size is minimal relative to the DRA specification. Since RL with average rewards is not PAC learnable, we cannot possibly provide finite-time complexity guarantees of our Algorithm
Acknowledgments and Disclosure of Funding
This research is supported by the National Research Foundation, Singapore, under its RSS Scheme (NRFRSS2022-009).
References
[1] Luca Alfaro. Formal Verification of Probabilistic Systems. Phd thesis, Stanford University, Stanford, CA, USA, 1998.
[2] Rajeev Alur, Suguman Bansal, Osbert Bastani, and Kishor Jothimurugan. A framework for transforming specifications in reinforcement learning. In Jean-François Raskin, Krishnendu Chatterjee, Laurent Doyen, and Rupak Majumdar, editors, Principles of Systems Design: Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, pages 604 624, Cham, 2022. Springer Nature Switzerland.
[3] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008
[4] Christel Baier and Joost-Picter Katoen. Principles of Model Checking. The MIT Press, 2008
[5] Hugo Bazille, Blaise Genest, Cyrille Jégourel, and Jun Sun. Global PAC bounds for learning discrete time Markov chains. In Shuvendu K. Lahiri and Chao Wang, editors, Computer Aided Verification 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21-24, 2020, Proceedings, Part II, volume 12225 of Lecture Notes in Computer Science, pages 304-326. Springer, 2020.
[6] David Blackwell. Discrete Dynamic Programming. The Annals of Mathematical Statisties, 33(2):719 726, 1962.
'These assumptions generally fail for our setting, where in view of Corollary 17 MDP states also track the states of the reward machine. For instance, in the reward machine in Fig. Zalit impossible to reach uj from u2.
10

---

[7] Alper Kamil Bozkurt, Yu Wang. Michael M. Zavlanos, and Miroslav Pajic. Control synthesis from Linear Temporal Logic specifications using model-free reinforcement learning. 2020 IFEE International Conference on Robotics and Automation (ICRA), pages 10349-10355, 2019.
[8] Ronen I. Brafman and Moshe Tennenholtz. R-max- A general polynomial time algorithm for near-optimal reinforcement learning J. Mach. Learn. Res., 3(null):213-233 mar 2003.
[9] Tomáš Brázdil, Krishnendu Chatterjee, Martin Chmelik, Vojtéch Forejt. Jan Křetínskýý Marta Kwiatkowska, David Parker, and Mateusz Ujma. Verification of Markov Decision Processes using learning algorithms. In Automated Technology for Verification and Analysis: 12th Inter- national Symposium, ATVA 2014, Sydney, NSW, Australia, November 3-7, 2014, Proceedings 12. pages 98 114. Springer, 2014.
[10] Mingyu Cai, Shaoping Xiao, Zhijun Li, and Zhen Kan. Optimal probabilistic motion planning with potential infeasible LTL constraints. IEEE Transactions on Automatic Control, 68 1):301- 3 116, 2023.
[11] Krishnendu Chatterjee and Monika Henzinger. Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algoritiums, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1318-1336. SIAM, 2011.
[12] Luca de Alfaro. Computing minimum and maximum reachability times in probabilistic systems. In Jos C. M. Bacten and Sjouke Mauw, editors. CONCUR 99 Concurrency Theory, pages 66-81, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
[13] Vektor Dewanto, George Dunn, Ali Eshragh, Marcus Gallagher, and Fred Roosta. Average- reward model-free reinforcement learning: A systematic review and literature mapping, 2021.
[14] Xuchu Ding, Stephen L. Smith, Calin Belta, and Daniela Rus. Optimal control of Markov Decision Processes with Linear Temporal Logic constraints. IEEE Transactions Automatic Control, 59(5): 1257, 2014.
[15] Jie Fu and Ufuk Topcu. Probably approximately correct MDP learning and control with Temporal Logic constraints. In Dieter Fox, Lydia E. Kavraki, and Hanna Kurniawati, editors, Robotics: Science and Systems X, University of California, Berkeley, USA, July 12-16, 2014, 2014.
[16] Qitong Gao, Davood Hajinezhad, Yan Zhang, Yiannis Kantaros, and Michael M. Zavlanos. Re- duced variance deep reinforcement learning with Temporal Logic specifications. In Proceedings of the 10th ACM/IÉEE International Conference on Cyber-Physical Systems, ICCPS '19 page 237-248, New York, NY, USA, 2019. Association for Computing Machinery.
[17] Abhijit Gosavi. Reinforcement learning for long-run average cost. European Journal of Operational Research, 155(3):654-677 2004. Traffic and Transportation Systems Analysis.
[18] Julien Grand-Clément and Marek Petrik. Reducing Blackwell and average optimality to discounted MDPs via the Blackwell discount factor. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Infor- mation Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[19] Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. Omega-regular objectives in model-free reinforcement learning. In Tomá Vojnar and Lijun Zhang, editors, Tools and Algorithms for the Construction and Analysis of Systems, pages 395-412, Cham, 2019. Springer International Publishing.
[20] Hosein Hasanbeig. Daniel Kroening, and Alessandro Abate. Certified reinforcement learning with logic guidance. Artificial Intelligence, 322: 103949, 2023.
[21] Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep reinforcement learning with Temporal Logics. In Nathalie Bertrand and Nils Jansen, editors, Formal Modeling and Analysis of Timed Systems, pages 1-22, Cham, 2020. Springer International Publishing.
11

---

[22] Arie Hordijk and Alexander A. Yushkevich, Blackwell Optimality, pages 231-267, Springer US, Boston, MA, 2002.
[23]
Rodrigo Toro Icarte. Reward Machines. Phd thesis, University of Toronto, 03 2022.
[24] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2107-2116. PMLR, 10-15 Jul 2018.
[25] Milad Kazemi, Mateo Perez, Fabio Somenzi, Sadegh Soudjani, Ashutosh Trivedi, and Al- varo Velasquez. Translating omega-regular specifications to average objectives for model-free reinforcement learning. In Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, and Matthew E. Taylor, editors, 2/st International Conference on Autonomous Agents and Mul- liagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022, pages 732-741. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
[26] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning 49:209-233 222992222222000 2002.
[27] Bakhadyr Khoussainov and Anil Nerode. Automata Theory and its Applications. Birkhäuser
Boston, Boston, MA, 2001.
[28] Achim Klenke. Probability Theory: Comprehensive Course. Universitext. Springer London,
2014.
[29] Dexter Kozen. Theory of Computation. Springer, London, 2006.
[30] Mateo Perez, Fabio Somenzi, and Ashutosh Trivedi. A PAC learning algorithm for LTL and omega-regular objectives in MDPs. Proceedings of the AAAI Conference on Artificial Intelligence, 38(19):11510-21511 2024.
[31] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994.
[32] Dorsa Sadigh, Eric S. Kim, Samuel Coogan, S. Shankar Sastry, and Sanjit A. Seshia. A learning based approach to control synthesis of Markov Decision Processes for Linear Temporal Logic specifications. In 53rd IEEE Conference on Decision and Control. pages 1091-1096, 2014.
[33] Anton Schwartz. A reinforcement learning method for maximizing undiscounted rewards. In International Conference on Machine Learning, 1993.
[34] Daqian Shao and Marta Kwiatkowska. Sample efficient model-free reinforcement learning from LTL specifications with optimality guarantees. IJCAI International Joint Conference on Artificial Intelligence, 2023-Augus:4 410-4uuu::1100118 2023.
[35] Salomon Sickert, Javier Esparza, Stefan Jaax, and Jan Křetínský. Limit-deterministic Büchi au- tomata for Linear Temporal Logic. In Swarat Chaudhuri and Azadeh Farzan, editors, Computer Aided Verification, pages 31 312-332, Cham, 2016. Springer International Publishing.
[36] Alexander I.. Strehl, Lihong Li, and Michael I.. Littman. Reinforcement learning in finite MDPs: PAC analysis. J. Mach. Learn. Res., 10:2413-2444 2009.
[37] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018
[38] Cameron Voloshin, Hoang Le, Swarat Chaudhuri, and Yisong Yue. Policy optimization with Linear Temporal Logic constraints. Advances in Neural Information Processing Systems, 35:17690-17702, 2022.
[39] Cameron Voloshin, Abhinav Verma, and Yisong Yue. Eventual discounting Temporal Logic counterfactual experience replay. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 35137-35150, PMLR, 2023.
12

---

[40] 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 on Machine Learning, ICML. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 10653-10662. PMIR, 2021.
[41] Eric M. Wolff, Ufuk Topcu, and Richard M. Murray. Robust control uncertain Markov Decision Processes with Temporal Logic specifications. In 2012 IEEE 51 IEEE Conference on Decision and Control (CDC), pages 3372-3379, 2012.
[42] Cambridge Yang. Michael L. Littman, and Michael Carbin. On the (in)tractabilityy of rein- forcement learning for LTL objectives. IJCAI International Joint Conference on Artificial Intelligence, pages 3650-3658, 2022.
[43] Shangdong Yang, Yang Gao, Bo An, Hao Wang, and Xingguo Chen. Efficient average reward reinforcement learning using constant shifting values. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), 2016.
13

---

b/p2
b/1
p2
start
90
b/1
53
0
{c)
a/pı
a/1
P1
{c}
start
q0
q1
81 S a/l
$2 a/1
(a) An MDP M where A(s1, 81) and the labeled with 0.
X(83,b,80)
{ch.
(h) A DRA A for the objective of visiting 81 83 infinitely often where F {(f 8)).
Figure 3: Counter-example for prefix-independent objectives.
A Supplementary Materials for Section 3
Recall that a w-regular language L prefix-independet for every infinite label sequence (24P)", we have L iff w' E L for every suffix w' of w. We prove that there is optimality-preserving preserving translation for reward functions regardless of whether is ireii--independent not. The prefix-dependent case was given in Section 3 Here focus the other case:
Proposition 19. There exists tuple (S, A, 80, A) and prefix-independent w-regular language L for which it is impossible to find a reward function R. S x A x S + such that for every probability transition P, let M = (S, A, 80, P, P.A). then every Re Rots-ottimal policy of M is also L-optimal (i.e. maximizing the probability of membership in T.).
Proof. Our proof technique based the fact that we can modify the transition probability function. Consider the MDP in Fig. 3a where the objective is to visit either 83 infinitely often. It can be checked that the DRA in Fig. 3b captures the given objective and the language accepted by A is trefix-independen
There are only two deterministic memoryless policies: T, which consistently selects action a, and и2, which consistently selects action For the sake of contradiction, let's assume the existence of reward function R. that preserves optimality for every transition probability function P. Pick P1 and P2 0. Then JA (TT)
and J (Tz2 =0, which implies that (TAA(()) > J. (T2) = R( b, so).
Ti is A-optimal whereas 12 not. Thus R(s1, a, 81) Now, assume P2 E (0, Accordingly, we have TRu. (TT) 2 p1 Rs1 a, $1) and we can deduce that (e.g. by solving the linear equation system described in [3 $8.2.3)) Re (T2)
R(su, b, so) 1-pa (R(so, b, 8s) + R( b, su)). As result: 2-P2
2-P2
lim (m)) 2 R(si,a,81) > b,80) = lim JAM (T2) p1
pa-1
Consequently, if P1, P2 are sufficiently large then J&an (TI) > J.h (T2). However, this contradicts to the fact that T2 is A-optimal and Tj not, since J (T2) = > J (MT). Hence, there is no such reward function R.
B Supplementary Materials for Section 4
Lemma 20. Every AEC contains an ASEC.
Proof. Consider an AEC C = (T, Act) MA. will prove this by using induction on the number of actions in C, denoted as size(C)) : E.er Act((s) > 1. For the base case where size(C) = 1, it can be deduced that C consists of only one accepting state with self-loop. Therefore, itself an ASEC.
14

---

Now, let's assume that size(C) k + 2. If C is already an ASEC, then we are done. Otherwise, there exists a state s E such that AAt(s)) finite path 808101
Since is strongly connected. there exists &p where &p is an accepting state and all the states .1,.... 8n are different from 8. Let a' (s)( such that a' * a. We construct new ABC C' = (T', Act') by first removing a' from (st(s) and then removing all the states that are no longer reachable from along with their associated transitions. It is important to note that after the removal, sp E ' since we can reach sp from without taking the action a'. (Besides, the graph is still strongly connected.) Since size S k, we can apply the induction hypothesis to conclude that contains an ASEC, thus completing the proof.
Lemma 8. Almost surely, if is accepted by A then pae reaches state in some ASEC C, of M & A.
To proof this result, we recall a well-known result in probabilistic model checking that with probability of one (wpo), every P of the policy π eventually stays in one of the ECs of MA and visits every transition in that EC infinitely often. To state this formally, we define for any run p = Sp00s1
InfSA(p) == {(s, a) E S x A Ki E N s; = s A = a}} = xo}
the set of state-action-pall -aiis occurring infinitely often in p. Furthermore, a state-action set SSXA defines a sub-MDP sub(x) = (T, Act), where
T = fs S (s. E x for some E A}
Act(s) {a (s, E
Lemma 21
[12) ) P PADDMMA (sb((TBS(P) is an end component) 1.
For the sake of self-containeddess,, we recall the proof of 12
Proof. We start with two more definitions: for any sub-MDP (T, Act) [, let
sa (T, Act) == {(ss a) E T x A E Act(s)) be the set of state-action pairs (s, a) such that a enabled in 8. Finally, let Q(T.Act) == (p E Runs(S, A) [n(SAAp) sa(T,Act)
be the set of runs such that action a is taken infinitely often in state & iff E T and Act(s). Note that the (T.,eett) constitute a partition of Runs(S, A).
Therefore, it suffices to establish for any sub-MDP (T,, Act), (T, Act) is an end-component or Plp E ((TTAct)] 0.
Let (T, Act) be arbitrary sub-MDP. First, suppose there exist E T and E Act(l) such that p Exe A(t, a, t') < 1. By definition each ((T,Aet)) takes action in state infinitely often. Hence, not only Plp E ((T.Aat)] s p* for all & N but also Plp E (cT.A
Thus, we assume that for all T and Act(t), EvEr A(t, a, t') 1. If (T..Act 0 then clearly Plp ((TTAct)] follows. Otherwise, take any p = syapa1 ... E (TT,Aet), and let t E T be arbitrary. We show that there exists a connecting path in (T, Art), which implies that (T, Act) is an end component.
Evidently, there exists an index in such that all state-action pairs occur infinitely often in p. i.e.
{ dio), (s1o+1, +1) ..) InfSA(p)
Thus, for all é io, E T and E Act(s;), and for all i' > 2 ig. there is path from to Sy in (T. A.t). Finally, it suffices to note that clearly for some i' > i iu. 8; and sy t'.
Proof of Lemma g By Lemma 21 almost surely sub(InfSA(p) is an accepting end component. Clearly, o is only accepted by the product MDP if this end component is an accepting EC. By Lemma 20 this AEC contains an ASEC. Therefore, by definition of sub(In(SA(p)), p almost surely in particular enters some ASEC. Finally, since the C1,..., Cn cover all states ASECs, p almost surely enters some C.
D
15

---

(so, a, 8o)/0
(So, so3/1
+/O
#/0
(so, b, $1)/0
(so. b, 81)/1
start
qo
q1
q2
(s1, b, su
(s1, b, so)/O
Figure 4: Reward machine yielded by our construction in Section 4 for the running example.
Before turning the proof of Lemma 10 let I Rime (p) lim in Li=0 y; denote the limit-
average reward of a run p. Note that, for any run p. JRm (p) {0, 13. Thus, by the dominated convergence theorem 128 Cor. 6.26].
Pp PANDA [T (p) = 1] = EppDea [J (p)] = lim inf E EANDAM
= TRume (T)
1-000
x
(3)
Lemma 10. Let P be a probability transition functioon with support E and M = (S, A, so, P).
1. For every policy x, Thm & (M))..
2. For every policy x. there exists some policy n' satisfying (M(T) S (Rnn(TT)
Proof.
only if o enters a C, and never leaves it. (00h might have entered other C₁'s earlier but then those necessarily need to overlap with yet another Cs such that < k < to avoid being trapped in state 1, resulting in TRhn (p) 1. Furthermore, this C, can only overlap with C, if < j. Otherwise, the reward machine would have enforced transitioning to Cj.)
1. For any run p. Timm
Since C2 is an ASEC, e accepted by the product MDP M A. Hence, by Eqs. and
T J.M PANDAM [J 1] s PANDAM oo accepted by M A] (T)
2. Let be arbitrary. For sydg... let qi be the state of the DRA in step Define x' to follow и until reaching & such that (8t, qt) T1 U... UT, Henceforth, we select the (unique) action guaranteeing to stay in the C, with minimal including the current state, i.e. Aclig (4, u). Formally
nt' rsoos ... 94) ( ... s1) (ct( (9::gg) q:)
if (St, q)) U...UUTT otherwise
Note that whenever a run ~ DM follows the modified policy and its induced run p reaches some ASEC C, then J&M (p) Thus,
ppDDA Sp reaches some C,] I Ep-Dy JT (p)] Jahn (T')
Furthermore, by Lemma 8 almost surely. every induced run p accepted by the product MDP must reach some C.. Consequently, by Eq. (2).
JM (T) = F Po-DAa @ is accepted by M & A]
< pDDD pp reaches some C.)
P-DDy sp reaches some C.) < (1())²)
In the penultimate step, we have exploited the fact that π and nL' agree until reaching the first C,.
I
We slightly abuse notation in the "otherwise" case and denote by Act q:) the distribution selecting the state in the singleton set Act(o ge) with probability 1.
16

---

B.1 Efficient Construction
We consider a different collection Ci..... Cn of ASECs:
Suppose .i...., C₁ is a collection of ABCs (not necessarily simple ones) con- taining all states in AECs. Then we consider ASECs CI...., Cn such that C, is contained in C,
The definition of the reward machine in Section 4.2 and the extension in Section 5 do not need be changed. Next, we argue the following:
1. This collection can be obtained efficiently (in time polynomial in the size of the MDP and DRA).
2. Lemma 10 and hence the correctness result (Theorem 9 still hold.
For 1. it is well-known that collection of maximal AECs (covering all states in AECs) can be found efficiently using graph algorithms [ Alg. 3.1], [5 I1 and 4 Alg. 47 and Lemma 10.125]. Subsequently. Lemma can be used to obtain ASEC contained in each of them. In particular, note that the proof of Lemma 20 immeeditelly gives rise to an efficient algorithm. (Briefly, we iteratively remove actions and states whilst querying reachability properties.)
For 2., the first part of Lemma TO clearly still holds. For the second, we modify policy h as follows: select action on the shortest path to
Once, enters maximal accepting end component the respective ASEC C, inside C₁ Once we enter one of the C, we follow the actions specified by the ASEC as before. Observe that the probability that under an AEC is entered is the same as the probability that one the C, is entered under the modified policy. The lemma, hence Theorem 9 follow.
C Supplementary Materials for Section 5
su, Lemma 14. Suppose M = AS, Su, P) is an arbitrary MDP.
1. For every policy n, IR'e ( S (T).
2. For every policy x. there exists some policy n' satisfying (M) S JRma (Rma(T') (T').
Proof.
1. For run p. let Ep be the set of transitions encountered in the product MDP. Note that TRL (p) = 1 only if n enters some c,Pe and never leaves it. (pºt might have entered other CfPs s earlier for E C Ep.)
With probability 1, Ep contains all the transitions present in cf the actual MDP. (NB possible transitions outside of c,eh might be missing from Ep.) In particular, with probability 1, cfe is also an ASEC for the true unknown MDP and p is accepted by the product MDP M % A. Consequently, using Eq. ( again,
JRL. P Pp-DA [T (p) = 1] < P PADD o accepted by M & A| = JMA-AMA (T))
2. Let æ be arbitrary. We modify æ to n' as follows: until reaching an ASEC C = (T, Act) w.r.t. the true, unknowr 10 set of transitions E* follow æ. Henceforth, select action
We claim that whenever p DMM follows the modified policy n' and e reaches some ASEC in the true product MDP, Rin (R)
(p)
To see this, suppose p D.M is such that for some minimal to N, (St, Aho) IF U ...". Let C (T, Act) == CF
Define E, to be the transitions encountered up step t E N, i.. E, [((Sk, qk), 0k. (sk+1.9k+1)) 0 < k < t}. Then almost surely for some minimal t 2 to.
NB The modified policy depends the true, unknown b"; we only claim the existence of such policy.
17

---

E, contains all transitions in C, and no further transitions will be encountered, i.e. for all
t' 2 t. E. E, Define E ;= E,. Note that for all ((s.g), q), a, (s',q)) E such that (8,g) ET. Act(s, = {a}. (This is because upon entering the ASEC C we immediately switch to following the action dictated by Act. Thus, we avoid "accidentally" discovering other ASECs w.r.t. the partial knowledge of the product MDP's graph, which might other- wise force us to perform actions leaving C.) Consequently, there cannot be another ASEC C' (T', Act') w.r.t. E overlapping with C, i.e. T n T * (. Therefore, for all (s. q) E C. E (..)) Act. Consequently, Ticr (p) 1.
Thus,
PP PA-DAy 10 reaches some ASEC in true product MDP/ & E Bp-Day [J (p)] = T (x¹)
Consequently,
(x) = P Dyr Ip is accepted by MM @ A|]
S P DM (pe reaches some ASEC in true product MDP)
P p-Dxy [p reaches some ASEC in true product MDP) S TRME(
In the penultimate step we have exploited that π and n' agree until reaching some ASEC in product MDP.
D Supplementary Materials for Section 6
Let lI be the set of all memoryless policies and II be the set all limit-average optimal policies. Besides, let w* Joh. (T") the limit average reward of any optimal n" II"
Lemma 15 is proven completely analagously to the following (where =N):
Lemma 22. Suppose "/k / 1, c ' 0 and each is memoryless policy satisfying JR (mx) 2
JRY (T) Ek for all E II. Then there exists Ko such that for all k 2 Ku, Tak is limit average optimal.
Proof. We define A = min JR (T) - w > 0. Recall (see e.g. policy æ E II,
22 Sec. 8.1]) that for any
lim (1 - 7) J (T) TT 7/1
(5)
Since II is finite, due to Eq. (5) there exists % such that
A
(T) - (1 7) 7) ( $
(6)
for all π E II and 7 E [no, 1). Let n² be memoryless Blackwell optimal policy (which exists due to 6 18) ). Note that
W = (TTA)(TT)
(7)
and there exists 7 E [0, 1) such that
JAM (TT) 2 J (T)
(8)
for all 7 E [7, 1) and II. Moreover, there clearly exists ko such that c S A/4 and 7/ 2 70
for all k 2 ko-
Therefore, for any h 2 knn
JTM M (Tx) JAM (T*) A
[ (Tx) w² S (1 7w)
Eqs. 6 and 7
A
< (1 - 7w) + 2
premise and Eq.
8
4
A
3
Consequently, by definition of A, T& E II"
18

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main results mentioned in the abstract and introduction Proposition| and Theorems I2
16 and 18
They accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification: Full proof' are presented in the appendices and results are cross-referenced. At the beginning of Section | we assume knowledge of the support of the MDP's proba- bility transition function for presentational purposes. This assumption is fully removed in Section 5
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeedSuuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
21

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "mx37azhzJM", "reviewer": "Reviewer_VjJR", "summary": "This paper considers the problem of reducing temporal logic objectives to limit-average reward problems which enable using reinforcement learning to compute policies. The key contributions are an explicit construction and analysis for the setting where the MDPs transition support is known, followed by a relaxation which drops this assumption. The key theorems then provide a characterization of the optimality preserving nature of the reduction.", "questions": "See weaknesses.", "limitations": "Limitations section in paper is satisfactory.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The constructions and theorems are to my knowledge novel and sound. Further, the target problem of LTL policy synthesis in the model free setting is important and relevant to the Neurips audience.\n\nParticularly interesting is the adaptive relaxation of the transition support knowledge. Further lemma 13's robustness implications further speak to the potential.", "weaknesses": "My primaries concerns for this paper are the (lack of) relation to prior work and the lack of empirical validation, even on a toy problem.\n\nIn particular, this works goal and conclusions seem very similar to [1] which also shows a non-markovian reduction policy learning which seems to also be optimal policy preserving with high probability and seems to apply to a larger problem space.\n\n[1] Eventual Discounting Temporal Logic Counterfactual Experience Replay, 2023\n\nIf this relationship can be clarified, I could raise my rating.\n\nMy other nitpick is with the novelty of section 3. My understanding is that this result is known, for example [2].\n\n[2] On the Expressivity of Markov Reward, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We will take their suggestions into account when revising the paper. In particular, we will clarify the relation to the additional references as detailed below.\n\n# Translation to Eventual Discounted Rewards [1]\n\n> In particular, this work's goal and conclusions seem very similar to [1] which also shows a non-markovian reduction policy learning which seems to also be optimal policy preserving with high probability and seems to apply to a larger problem space.\n\nVoloshin et al. [1] present a translation from LTL objectives to eventual discounted rewards, where only strictly positive rewards are discounted. (In particular, they do not consider average rewards.) \nTheir main result (Thm. 4.2) is that \n$$p-p’\\leq 2\\log(1/\\gamma)\\cdot m &emsp;&emsp; (*)$$\nwhere\n- $\\gamma$ is the discount factor,\n- $p$ is the optimal probability of LTL satisfaction,\n- $p’$ is the probability of LTL satisfaction by the policy maximising eventual $\\gamma$-discounted rewards, and\n- $m:=\\sup_\\pi O_\\pi$ is a constant which depends on the probabilities in the MDP. \n\nThis provides a bound on the *sub-optimality* w.r.t. LTL satisfaction of optimal policies for the eventual discounted problem for a given discount factor.\n\nBesides, Cor. 4.5 (of [1]) concludes that for a given error-tolerance $\\epsilon$ a discount factor can be chosen guaranteeing a sub-optimality bound (*) above of $\\epsilon$, ***provided $m$ is known***. However, a priori, the constant $m$ is not available without knowledge of the MDP. \nAs such, this paper does not provide an optimality preserving translation which works regardless of unknown parameters of the MDP. Thus, it falls in a similar category as the approaches mentioned in ll. 335-9 in our discussion of related work.\n\n# Expressivity of Markov Reward\n\n> My other nitpick is with the novelty of section 3. My understanding is that this result is known, for example [2,3]\n\n[2,3] study MDPs with discounted rewards and three types of task specifications: (i) a set of acceptable policies, (ii) a partial ordering on policies, and (iii) a partial ordering on runs.\nWhilst their paper is concerned with the limited expressivity of reward functions, it neither covers LTL nor average rewards. \nIn particular, we do not think that our Proposition 4 is stated (or follows from the results) in [2,3]. They acknowledge this by stating the following when briefly mentioning LTL task specifications: “​​A natural direction for future work broadens our analysis to include these kinds of tasks.”\n\n(Task specification (iii)—imposing a partial ordering on runs—is most closely related to LTL tasks. However, their framework enables the expression of far richer preferences. In particular, the task designer can distinguish all traces and is not constrained by the limited expressivity of LTL. This naturally makes finding a suitable reward function even significantly harder.)\n\n[1] Cameron Voloshin, Abhinav Verma, Yisong Yue: Eventual Discounting Temporal Logic Counterfactual Experience Replay. ICML 2023.\n\n[2] David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, Satinder Singh: On the Expressivity of Markov Reward (Extended Abstract). IJCAI 2022\n\n[3] David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, Satinder Singh: On the Expressivity of Markov Reward. NeurIPS 2021", "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": "", "extra_scores": {}}, {"review_id": "1S6NvACYrF", "reviewer": "Reviewer_FqP1", "summary": "This paper tackle several open problems in the field of specification driven learning using Reinforcement Learning (RL) algorithms. It proves that $\\omega$-regular objectives can be translated in an optimality preserving manner to limit-average reward MDPs. A PAC-MDP convergence proof for limit-average reward MDPs is introduced as well.", "questions": "1. How does the choice between Limit Deterministic Büchi Automatas (LDBAs) and DRAs to express $\\omega$-regular languages affect the results [2]?\n2. Although [1] does not consider the PAC-MDP setting, how relevant is their proof of convergence w.r.t. the results in the paper?\n3. Minor typos\n    1.  L131 everyone → every\n    2. L156 $\\delta_d$ ->  $\\delta_u$ ?\n    3. L289 “sequence of discount sum”\n\nReferences:\n\n[1] Learning and Planning in Average-Reward Markov Decision Processes, Wan et al, ICML 2021\n\n[2] From LTL to your favourite deterministic automaton, Kretínsky et al, \nIn CAV (1), volume 10981 of Lecture Notes in Computer\nScience, pages 567–577. Springer, 2018.", "limitations": "The cost of running these transformations is not discussed (empirically or otherwise).", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper reads well and presents a clear and logical progression towards the main results.", "weaknesses": "The claim of the first proof of convergence for average reward MDPs may need to be further evaluated [1].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and we will take their suggestions into account when revising the paper. We proceed to address the questions raised by the reviewer.\n\n\n# Choice of DRAs vs. LDBAs\n\n> How does the choice between Limit Deterministic Büchi Automata (LDBAs) and DRAs to express \\Omega-regular languages affect the results? \n\nOur construction of the reward machine relies on the representation of $\\omega$-regular languages by DRAs (particularly their determinism). We do not know if there is an *efficient* reduction from LDBAs to limit-average reward machines. Note the presence of non-deterministic transitions in LDBAs, whereas reward machines are inherently deterministic. We will investigate if an efficient reduction from LDBAs to limit-average reward machines is possible avoiding the blow-up incurred from translating LDBAs to DRAs.\n\n\n\t\n# Novelty of convergence for limit-average objectives \n\n> Although [1] does not consider the PAC-MDP setting, how relevant is their proof of convergence w.r.t. the results in the paper?\n\nWan et al. [1] require the following (communicating) assumption: “For every pair of states, there exists a policy that transitions from one to the other in a finite number of steps with non-zero probability.”\n\nThis assumption generally fails for our setting, where in view of our Cor. 16, MDP states also track the states of the reward machine. For instance, in the reward machine in Fig. 2(a), it is impossible to reach $u_1$ from $u_2$.\n\nTherefore, the paper [1] does not undermine the novelty of our approach for general MDPs.\n\nWe will add the reference to the list of similar works discussed in l. 341.\n\n[1] Wan et al.: Learning and Planning in Average-Reward Markov Decision Processes, ICML 2021\n\n[2] Kretínsky et al: Rabinizer 4: From LTL to your favourite deterministic automaton, CAV 2018.", "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": "", "extra_scores": {}}, {"review_id": "h8TWfDmjhE", "reviewer": "Reviewer_eqsH", "summary": "The paper studies the link between reinforcement learning with $\\omega$-regular objectives to reinforcement learning with limit-average reward. It is shown that one cannot reduce RL with $omega$-regular objectives to RL with limit-average objectives by only replacing the reward function (Proposition 4), but that it is possible if one considers rewards given by finite-memory reward machines (Theorem 11), which is the main result of the paper. It is also shown that RL with limit-average rewards can be learned in the limit, thus implying that RL with omega-regular objectives can also be learned in the limit (Theorem 17).", "questions": "I do not have any questions", "limitations": "The authors addressed the limitations of their work in the Limitations section at the end.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is original in the sense that it provides theoretical tools for a new approach for RL with $\\omega$-regular objectives by reducing it to the well-known case of limit-average rewards. This allows to apply the many approaches designed originally for the case of limit-average rewards to $\\omega$-regular objectives. The idea of approaching RL with $\\omega$-regular objectives by analyzing the end components of the product MDP with a DRA or LDBA representing the objective might not be new, but the way it is precisely used with accepting simple components and reward machines is new and original to the best of my knowledge. I would judge the paper of high quality as it is well presented, the proofs are sound as far as I could check, and the context of the results is very well explained. The paper is easy to read and its more technical concepts are explained in a simple manner (Section 4 is a good addition in that sense). The results of the paper solves open problems given in [1], and contribute to building a theoretical framework for transforming specifications in RL, which is right now underdeveloped with many open questions, and was a work begun in [1]. Moreover, even though no practical applications of the results are presented, it is not unreasonable to expect that the main result might be directly applied in the case of finite MDPs with the support of the actions known. Therefore, the results are of high significance to the community.\n\n[1]: Rajeev Alur, Suguman Bansal, Osbert Bastani, and Kishor Jothimurugan. A framework for transforming specifications in reinforcement learning. In Jean-François Raskin, Krishnendu Chatterjee, Laurent Doyen, and Rupak Majumdar, editors, Principles of Systems Design: Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, pages 604–624, Cham, 2022. Springer Nature Switzerland.", "weaknesses": "I do not think that the paper has any obvious weaknesses, but it could be improved by either providing a polynomial construction for the reduction from $\\omega$-regular objectives to limit-average ones in the case where the probabilities of the MDP are unknown or providing a negative result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. \n\nWe agree with the reviewer that investigating the possibility of a polynomial translation for the general case (where the transitions with positive probability are not known) is a very interesting future direction.", "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": "", "extra_scores": {}}, {"review_id": "xNSc9wqbFN", "reviewer": "Reviewer_EhuA", "summary": "The authors present a theoretical framework for learning $\\omega$-regular properties in unknown MDPs through average reward optimization (via an \"optimality preserving\" approach). \nCompared to previous work, the approach allows for multi-chain MDP. \nThe idea is to formalize the property through a deterministic Rabin automaton, construct an auxiliary model (a product MDP) that encodes the state space and the transitions of this automaton into those of the original MDP, and incorporate the resulting model into a reward machine.\nRewards are then generated according to the current knowledge of the underlying graph of the product MDP. \nThe reward machine can be constructed on the fly, which enables its optimization through RL. \nFinally, the authors show that optimizing the discounted return objective boils down to (i) optimizing the average reward objective, which in turn implies (ii) the optimality preserving learning of the $\\omega$-regular property.\nFinally, convergence guarantees are proved through a sequential algorithm making calls to any PAC-MDP algorithm for discounted return, eventually decreasing the error and confidence terms to 0 as the algorithm progresses.", "questions": "-  Is listing all minimal ECs not equivalent to listing all the possible deterministic policies in a maximal end component? If that's the case, even though the memory of the reward machine need not be too large due to the coverage sufficiency, detecting them might be costly and in the worst case exponential. I believe this question should be addressed and at least discussed in the main text.\n- Section 5 is a bit ambiguous to me. In particular, I don't understand how Lemma 13 applies without fixing the set of visited transitions $E$. By looking at the Appendix, I understand that either the set $E$ is fixed, or it changes over time steps, i.e., the set is defined as $E_t$ for $t \\geq 0$. If this is the case, then the reward machine $\\mathcal{R}$ should take this time step into account in its definition, and I expect to see this in the main text. Could you please clarify?\n- Could you please clarify what happens if the current algorithm believes to act in an EC (according to $E$) that is actually _not_ an EC? For instance, what happens if a region of the system is detected at the current time step as being an EC that has a *very* small probability of being left?\n- Do you have any insights on how to design a *practical* algorithm that preserves the theoretical guarantees in the limit?\n\n### Remarks and suggestions\n- In Section 6, I was confused because I did not understand why considering a discounted return objective is relevant for the average return. I had to check in the appendix to see the reference, mentioning that when the discount $\\gamma$ goes to one, $(1 - \\gamma) \\mathcal{J}\\_{\\mathcal{R}^{\\gamma}}$ coincides with $\\mathcal{J}\\_{\\mathcal{R}^{\\text{avg}}}$. This should be explicitly stated in the main text!\n- line 131: everyone => every?\n- for the reference that LTL is not PAC-learnable, I would also cite [1]\n- line 177: it seems that you used $R_i$ for denoting the sets of states visited finitely often and then suddenly switched to $B_i$.\n\n[1] Hugo Bazille, Blaise Genest, Cyrille Jégourel, Jun Sun: Global PAC Bounds for Learning Discrete Time Markov Chains. CAV (2) 2020: 304-326", "limitations": "Limitations have been addressed and further discussed in the conclusion.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors answer questions that were left open: (i) learning $\\omega$-regular properties through a limit average reward objective in an optimality-preserving way is not possible with Markovian rewards, (ii) this is in contrast made possible by using finite-spaces reward machines, and (iii) in RL, one can design such an algorithm that converges in the limit. \nOverall, the paper is well-written and the proof sketches in the main text effectively allow the reader to grasp the main ideas of the proofs presented in the appendix.", "weaknesses": "First, although the paper is quite well written, I think that for somebody unfamiliar with all the concepts presented, the paper might be difficult to follow. For instance, the authors build upon accepting end components to detect when the specification is satisfied. However, the authors do not mention or discuss the reason why it is possible to do that in practice. Specifically, I would expect the authors to mention that identifying ECs can be done through purely graph algorithms, which makes them affordable to consider in this context.\n\nSecond, I found that the authors do not really take into account practical considerations in the proposed approach. For instance, there is no mention of how to detect minimal ECs. I mention other issues that I believe should be clarified in the \"Questions\" section.\n\nFinally, there is no evaluation. I understand that this is intentional due to the theoretical nature of the paper. However, after reading the text, I am eager to know if the approach works in practice, as learning to satisfy LTL specifications is an ongoing challenge in RL. Furthermore, Algorithm 1 is an (unrealizable) theoretical algorithm but I would have loved to see a discussion or remark on how to implement such an algorithm in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We will take their suggestions into account when revising the paper. In particular, we will use the additional page for the camera-ready version to elaborate on practical aspects and the construction in Sec. 5.\nNext, we address the reviewer’s questions (numbered 1-4).\n\n# Practical Aspects: Constructing the Reward Machine (Question 1)\nASECs yield (partial) deterministic policies. Our construction considers a collection of ASECs covering all states in ASECs (l. 205). It does not necessarily require listing all possible ASECs but only (up to) one ASEC per state. It is unclear whether this can be obtained in polynomial time but the focus of our submission was primarily simplicity of presentation and clarity of the optimality-preserving translation. In the following, we present a slightly modified construction which is *efficient*. We will give a brief account in the revision.\n\nWe consider a different collection $\\mathcal C_1,\\ldots,C_n$ of ASECs:\n> Suppose $\\mathcal C’_1,\\ldots,\\mathcal C’_n$ is a collection of AECs (not necessarily simple ones) containing all states in AECs. Then we consider ASECs $\\mathcal C_1,\\ldots,C_n$ such that $\\mathcal C_i$ is contained in $\\mathcal C’_i$.\n\nThe definition of the reward machine in Sec. 4.2 and the extension in Sec. 5 do not need to be changed. Next, we argue the following:\n1. This collection can be obtained efficiently (in time polynomial in the size of the MDP and DRA).\n2. Lemma 10 and hence the correctness result (Thm. 10) still hold.\n\nFor 1. it is well-known that a collection $\\mathcal C’_1,\\ldots,\\mathcal C’_n$ of maximal AECs (covering all states in AECs) can be found efficiently using graph algorithms [1, Alg. 3.1], [2,3] and [4, Alg. 47 and Lemma 10.125].\nSubsequently, Lemma 19 can be used to obtain an ASEC contained in each of them. In particular, note that the proof of Lemma 19 immediately gives rise to an efficient algorithm. (Briefly, we iteratively remove actions and states whilst querying reachability properties.)\n\nFor 2., the first part of Lemma 10 clearly still holds. For the second, we modify policy $\\pi$ as follows: Once, $\\pi$ enters a maximal accepting end component we select an action on the shortest path to the respective ASEC $\\mathcal C_i$ inside $\\mathcal C_i’$. Once we enter one of the $\\mathcal C_i$ we follow the actions specified by the ASEC as before. Observe that the probability that under $\\pi$ an AEC is entered is the same as the probability that one of the $\\mathcal C_i$ is entered under the modified policy. The lemma, hence Thm. 10, follow.\n\n[1] Luca Alfaro. Formal Verification of Probabilistic Systems. PhD thesis, 1998\n\n[2] Fu & Topcu. Probably approximately correct MDP learning and control with Temporal Logic constraints. 2014\n\n[3] Chatterjee & Henzinger, “Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification”, 2011\n\n[4] Baier & Katoen. Principles of Model Checking. 2008\n\t\n# Construction in Sec. 5 (Question 2/3)\nIntuitively, in Sec. 5 we can eliminate knowledge of the transitions with positive probability because for a run we almost surely see enough transitions of the true product MDP to determine whether it reaches and stays in an AEC.\nThis is due to the well-known result that with probability 1, the states and actions occurring infinitely often in runs constitute an end component (not necessarily an accepting one) w.r.t. the true MDP (Lemma 20). Moreover, for accepting runs this EC must clearly be accepting.\n\nTherefore, our reward machine tracks the set $E$ of transitions in the product MDP encountered earlier in a run as part of its state, and $E$ is used to assign rewards, which enforce staying in one of the dedicated ASEC relative to the current knowledge $E$. Whenever a new transition is seen, the RM resets the status flag and we will need to follow one of the ASECs w.r.t. the updated $E$. Importantly, in the setting of limit-average rewards, initial “missteps” do not affect the total reward.\n\n## Question 2\nFurther to the above explanations, we illustrate the evolvement of the $E$-component of the RM’s state over time:\nInitially, this $E$-component of the state is $\\emptyset$. Over time, as new transitions are observed in a run, $E$ grows monotonically. Since the MDP is finite, at some time step all transitions in a run have been seen and $E$ does not grow further. \n\nThe reward machine in Sec. 5 does take the current $E$ into account and rewards transitions based on the dedicated ASECs w.r.t. $E$. (Note the superscripts in the definition following l. 257.) There is no need to consider the number $t$ of the time step.\n\n## Question 3\nSuppose we follow one of the dedicated ASECs w.r.t. the transitions observed in the past (and hence receive rewards of 1). If this is not ASEC w.r.t. the true product MDP there exists a transition leaving it. As argued above, almost surely it will eventually be taken. (This may take a while if it has very small probability.)\nThereafter, the reward machine acts according to the updated set of possible transitions. The rewards obtained thus far do not affect the overall limit-average reward.\n\n# Practical Algorithm with Convergence Guarantee (Question 4)\nAlgorithm 1 can be improved in practice by exploiting the internals of the RL-algorithm ```Discounted``` with PAC-guarantees and running it incrementally. For example, the model-based approaches of [5,6] first sample a sufficiently good approximation of the MDP’s transition probabilities before planning optimal policies on it. Instead of discarding earlier samples on the next invocation of ```Discounted```, we can simply determine how many additional samples are required to achieve the more stringent guarantees for the updated parameters.\n\n[5] Kearns & Singh. Near-optimal reinforcement learning in polynomial time. 2002\n\n[6] Strehl et al. Reinforcement learning in finite MDPs: PAC analysis. 2009", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: There is common agreement that the paper is making a novel and solid theoretical contribution to the RL area. The reviewers raised several issues that the authors should work to clarify in the final paper.
Decision: Accept (poster)