Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards

Reinforcement learning (RL) is a machine learning paradigm whereby an agent aims to accomplish a task in a generally unknown environment [36]. Traditionally, tasks are specified via a 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 are supplied by the user are prone to error in that the chosen low-level rewards often fail to accurately capture high-level objectives. Generally, policies derived from local rewards-based specifications are hard to understand because it is difficult to express or explain their global intent.

As a remedy, it has been proposed to specify tasks using formulas in Linear Temporal Logic (LTL) [40, 29, 9, 37, 15, 33, 14] or $\omega$-regular languages more generally [29]. In this framework, the aim is to maximise the probability of satisfying a logical specification. LTL can precisely express a wide range of high-level behavioural properties such as liveness (infinitely often $P$), safety (always $P$), stability (eventually always $P$), and priority ($P$ then $Q$ then $T$).

Motivated by this, a growing body of literature study learning algorithms for RL with LTL and $\omega$-regular objectives (e.g. [40, 15, 29, 7, 31, 20, 21, 16]). However, to the best of our knowledge, all of these approaches may fail to learn provably optimal policies without prior knowledge of a generally unknown parameter. Moreover, it is known that neither LTL nor (limit) average reward objectives are PAC (probably approximately correct) learnable [3]. Consequently, approximately optimal policies can only possibly be found asymptotically but not in bounded time. ¹¹1Formally, for some $\epsilon,\delta>0$ it is impossible to learn $\epsilon$-approximately optimal policies with probability $1-\delta$ in finite time. \comm@parse@datecomm@commentloCitation? \comm@parse@datecomm@commentdwThis is immediate from the definition of PAC learnability. What do you want a reference for?

In this work, we pursue a different strategy: rather than solving the RL problem directly, we study optimality-preserving translations [3] from $\omega$-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 $\omega$-regular objectives by solving a single more standard problem, for which we can leverage existing off-the-shelf algorithms (e.g. [25, 15, 29]). 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 a translation from LTL to discounted rewards is impossible [3]. Intuitively, this is because the latter cannot capture infinite horizon tasks such as reachability or safety [3, 41, 19]. Hence, we instead investigate translations to limit-average rewards in this paper.

Recall that a Markov Decision Process (MDP) is a tuple $\mathcal{M}=(S,A,s_{0},P)$ where $S$ is a finite set of states, $s_{0}\in S$ is the initial state, $A$ is the finite set of actions and $P:S\times A\times S\rightarrow[0,1]$ is the probability transition function such that $\sum_{s^{\prime}\in S}P(s,a,s^{\prime})=1$ for every $s\in S$ and $a\in A$. MDPs may be graphically represented; see e.g. Fig. 1(a). We let $\mathrm{Runs}_{\mathrm{fi}}(S,A)=S\times(A\times S)^{*}$ and $\mathrm{Runs}(S,A)=(S\times A)^{\omega}$ denote the set of finite runs and the set of infinite runs in $\mathcal{M}$ respectively.

A policy $\pi:\mathrm{Runs}_{\mathrm{fi}}(S,A)\rightarrow\mathcal{D}(A)$ maps finite runs to distributions over actions. We let $\Pi(S,A)$ denote the set of all such policies. A policy $\pi$ is memoryless if $\pi(s_{0}a_{0}\ldots s_{n})=\pi(s^{\prime}_{0}a^{\prime}_{0}\ldots s^{\prime}_{m})$ for all finite runs $s_{0}a_{0}\ldots s_{n}$ and $s^{\prime}_{0}a^{\prime}_{0}\ldots s^{\prime}_{m}$ such that $s_{n}=s^{\prime}_{m}$. For each MDP $\mathcal{M}$ and policy $\pi$, there is a natural induced probability measure $\mathcal{D}_{\pi}^{\mathcal{M}}$ on its runs.

The desirability of policies for a given MDP $\mathcal{M}$ can be expressed as a function $\mathcal{J}:\Pi(S,A)\to\mathbb{R}$. Much of the RL literature focuses on discounted-sum $\mathcal{J}^{\mathcal{M}}_{\mathcal{R}^{\gamma}}$ and limit-average reward objectives $\mathcal{J}^{\mathcal{M}}_{\mathcal{R}^{\textrm{avg}}}$, which lift a reward function $\mathcal{R}:S\times A\times S\to\mathbb{R}$ for single transitions to runs $\rho=s_{0}a_{0}s_{1}a_{1}\ldots$ as follows:

where $r_{i}=\mathcal{R}(s_{i},a_{i},s_{i+1})$ and $\gamma\in(0,1)$ is the discount factor.

Reward functions emit rewards purely based on the transition being taken without being able to take the past into account, whilst DRAs have finite memory. Therefore, there cannot generally be optimality-preserving translations from $\omega$-regular objectives to limit average rewards provided by reward functions:

Remarkably, this rules out optimality-preserving specification translations even if transition probabilities are fully known³³3In Appendix A we show another negative result (Proposition 19): even for a strict subset of $\omega$-regular specifications such translations are impossible..

Since simple reward functions lack the expressiveness to capture $\omega$-regular objectives, we employ a generalisation, reward machines [23, 24], whereby rewards may also depend on an internal state:

Intuitively, a RM $\mathcal{R}$ utilises the current transition to update its states through $\delta_{u}$ and assigns the rewards through $\delta_{r}$. For example, Fig. 2(a) depicts a reward machine for the MDP of Fig. 1(a), where the states count the number of visits to $s_{1}$ (0 times, once, more than once).

Let $\rho=s_{0}a_{0}s_{1}\cdots$ be an infinite run. Since $\delta_{u}$ is deterministic, it induces a sequence $u_{0}u_{1}\ldots$ of states in $\mathcal{R}$, where $e_{i}=(s_{i},a_{i},s_{i+1})$ and $u_{i+1}=\delta_{u}(u_{i},e_{i})$. The limit-average reward of a policy $\pi$ is defined as:

It is seen that limit-average optimal policies $\pi^{*}$ for the MDP in Fig. 1(a) and the RM in Fig. 2(a) eventually select action $b$ exactly once in state $s_{0}$ to achieve $\mathcal{J}^{\mathcal{M}}_{\mathcal{R}^{\textrm{avg}}}(\pi^{*})=1$.

In the following two sections, we present a general translation from $\omega$-regular languages to limit-average reward machines, and we show that our translation is optimality-preserving (Theorem 12).

To help the reader gain intuition about our construction, we first explore the situation where the support $\{(s,a,s^{\prime})\in S\times A\times S\mid P(s,a,s^{\prime})>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 us to draw connections between our problem and a familiar scenario in probabilistic model checking [5, Ch. 10], where the acceptance problem for $\omega$-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 an MDP without transition function $(S,A,s_{0})$, a set of possible transitions $E\subseteq S\times A\times S$, a label function $\lambda:S\times A\times S\to 2^{\mathcal{AP}}$ and a DRA $\mathcal{A}=(Q,2^{\mathcal{AP}},q_{0},\delta,F)$. Our aim is to find a reward machine $\mathcal{R}$ such that for every transition function $P$ compatible with $E$ (formally: $E=\{(s,a,s^{\prime})\mid P(s,a,s^{\prime})>0\}$), optimal policies for limit-average rewards are also optimal for the acceptance probability of the DRA $\mathcal{A}$.

In this section, we generalise the approach of the preceding section to prove our main result:

Again, we fix an MDP without transition function $(S,A,s_{0})$, a label function $\lambda:S\times A\times S\to 2^{\mathcal{AP}}$ and a DRA $\mathcal{A}=(Q,2^{\mathcal{AP}},q_{0},\delta,F)$. Note that the ASECs of a product MDP are uniquely determined by the non-zero probability transitions. Thus, for each set of transitions $E\subseteq(S\times Q)\times A\times(S\times Q)$, we let $\mathcal{C}^{E}_{1}=(T_{1},\operatorname{Act}_{1}),\ldots,\mathcal{C}^{E}_{n}=(T_{n},\operatorname{Act}_{n})$ denote a collection of ASECs covering all states in ASECs w.r.t. the MDPs in which $E$ is the set of non-zero probability transitions.⁵⁵5To achieve the same number $n$ of ASECs we can add duplicates. If there are no ASECs we can set $T_{i}:=\emptyset$. Then, for each set $E$ and state $(s,q)\in T^{E}_{1}\cup\cdots\cup T^{E}_{n}$, we let $\mathcal{C}_{(s,q)}^{E}=(T_{(s,q)}^{E},\operatorname{Act}_{(s,q)}^{E})$ be the ASEC $\mathcal{C}_{i}^{E}$ that contains $(s,q)$ in which the index $i$ is minimal.

Our reward machine $\mathcal{R}=\mathcal{R}_{(S,A,\lambda,\mathcal{A})}$ 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 $(q,f,E)$, where $q\in Q$ keeps track of the state of the DRA, $f\in\{\top,\bot\}$ is a status flag and $E\subseteq(S\times Q)\times A\times(S\times Q)$ memorises the transitions in the product MDP encountered thus far.

Intuitively, we set the flag to $\bot$ if we are in MDP state $s$, $(s,q)$ is in one of the $\mathcal{C}_{1}^{E},\ldots,\mathcal{C}_{n}^{E}$ and the chosen action deviates from $\operatorname{Act}_{(s,q)}^{E}(s,q)$. We can recover from $\bot$ by discovering new transitions. Besides, we give reward $1$ if $f=\top$ and $(s,q)$ is in one of the $\mathcal{C}_{1}^{E},\ldots,\mathcal{C}_{n}^{E}$ (and $0$ otherwise).

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 is $u_{0}:=(q_{0},\top,\emptyset)$ and we formally define the update and reward functions as follows:

where $q^{\prime}:=\delta(q,\lambda(s,a,s^{\prime}))$ and $e:=((q,s),a,(q^{\prime},s^{\prime}))$.

Theorem 12 is proven by demonstrating an extension of Lemma 10 (see Appendix C):

Note that Lemma 14 immediately proves that the reduction is not only optimality preserving (Theorem 12) but also robust: every $\epsilon$-approximately limit-average optimal policy is also $\epsilon$-approximately optimal w.r.t. $\mathcal{J}^{\mathcal{M}}_{\mathcal{A}}$. This observation is important because exactly optimal policies for the limit average problem may be hard to find.

Intuitively, to see part 1 of Lemma 14 we note: If an average reward of $1$ is obtained for a run, the reward machine believes, based on the partial observation of the product MDP, that the run ends up in an 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 $\pi$ similarly as in Lemma 10 by selecting actions $\operatorname{Act}(s_{t},q_{t})$ once having entered an ASEC $\mathcal{C}=(T,\operatorname{Act})$ w.r.t. the true, unknown product MDP.⁶⁶6NB The modified policy depends on the true, unknown support of the Probability transition function; we only claim the existence of such a policy.

Thanks to the described translation, advances (in both theory and practice) in the study of RL with average rewards carry over to RL with $\omega$-regular and LTL 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 [3]: also RL with $\omega$-regular and LTL objectives can also be learned in the limit.

We start with the case of simple reward functions $\mathcal{R}:S\times A\times S\to\mathbb{R}$. Recently, [18] have shown that discount optimal policies for sufficiently high discount factor $\overline{\gamma}\in[0,1)$ are also limit average optimal. This is not enough to demonstrate Theorem 16 since $\overline{\gamma}$ is generally not known and in finite time we might only obtain approximately limit average optimal policies.

Our approach is to reduce RL with average rewards to a sequence of discount sum \changed[dw]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 D for a proof):

Our proof harnesses yet another notion of optimality: a policy $\pi$ is Blackwell optimal (cf. [6] and [22, Sec. 8.1]) if there exists $\overline{\gamma}\in(0,1)$ such that $\pi$ is $\gamma$-discount optimal for all $\overline{\gamma}\leq\gamma<1$. It is well-known that memoryless Blackwell optimal strategies always exist [6, 18] and they are also limit-average optimal [22, 18].

Thanks to the PAC (probably approximately correct) learnability of RL with discounted rewards [25, 35], there exists an algorithm Discounted which receives as inputs a simulator for $\mathcal{M}$, $\mathcal{R}$ as well as $\gamma,\epsilon$ and $\delta$, and with probability $1-\delta$ returns an $\epsilon$-optimal memoryless policy for discount factor $\gamma$. In view of Lemma 15, our approach is to run the PAC algorithm for discount-sum RL for increasingly large discount factors $\gamma$ and increasingly low $\delta$ and $\epsilon$ (Algorithm 1).

Next, we turn to the more general case of reward machines. [23, 24] observe that optimal policies for reward machines can be learned by learning optimal policies for the modified MDP which additionally tracks the state the reward machine is in and assigns rewards accordingly. We conclude at once:

Finally, harnessing Theorem 12 we resolve Open Problem 4 of [3]:

The connection between acceptance of $\omega$-regular languages in the product MDP and AECs is well-known in the field of probabilistic model checking [5, 12]. As an alternative to DRAs [40, 14, 31], Limit Deterministic Büchi Automata [34] have been employed to express $\omega$-regular languages for RL [37, 7, 10, 20, 21].

A pioneering work on RL for $\omega$-regular rewards is [40], which expresses $\omega$-regular objectives using Deterministic Rabin Automata. Similar RL approaches for $\omega$-regular objectives can also be found in [14, 37, 10, 15]. The authors of [15, 29] approach RL for $\omega$-regular objectives directly by studying the reachability of AECs in the product MDP and developing variants of 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 $\epsilon$-return mixing time [15], or the $\epsilon$-recurrence time [29].

Various studies have explored reductions of $\omega$-regular objectives to discounted rewards, and subsequently applied Q-learning and its variants for learning optimal policies [7, 31, 20, 21, 16]. \changed[dw]In a similar spirit, [38] present a translation from LTL objectives to eventual discounted rewards, where only strictly positive rewards are discounted. These translations are generally not optimality preserving unless the discount factor is selected in a suitable way. Again, this is impossible without prior knowledge of the exact probability transition functions in the MDP.

Furthermore, whilst there are numerous convergent RL algorithms for average rewards for unichain \changed[dw]or communitcating⁷⁷7These 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. 2(a) it is impossible to reach $u_{1}$ from $u_{2}$. MDPs (e.g. [8, 42, 17, 32, 4, 39]), it is unknown whether such an algorithm exists for general multichain MDPs with a guaranteed convergence property. In fact, a negative result in [3] shows that there is no PAC (probably approximately correct) algorithm for LTL objectives and limit-average rewards when the MDP transition probabilities are unknown.

[8] have proposed an algorithm with PAC guarantees provided $\epsilon$-return mixing times are known. They informally argue that for fixed sub-optimality tolerance $\epsilon$, this assumption can be lifted by guessing increasingly large candidates for the $\epsilon$-return mixing time. This yields $\epsilon$-approximately optimal policies in the limit. However, it is not clear how to asymptotically obtain exactly optimal policies as this would require simultaneously decreasing $\epsilon$ and increasing guesses for the $\epsilon$-return mixing time (which depends on $\epsilon$).

This research is supported by the National Research Foundation, Singapore, under its RSS Scheme (NRFRSS2022-009).