Specification-Guided Reinforcement Learning

Markov decision processes.  The environment is modeled as a Markov decision process (MDP). Figure 1a shows an MDP with states $S=\{s_0,s_1,s_2,s_3\}$ and actions $A=\{a_1,a_2\}$. Actions cause state transitions according to transition probabilities $T : S\times A\times S\to [0,1]$. For example, $a_1$ from $s_0$ leads to $s_1$ or $s_3$ with equal probability. The initial state distribution $\eta$ describes the distribution of states the system initializes in. Here, $\eta$ is the dirac distribution at $s_0$—that is, with $\eta \left(s_o\right)=1$. Mathematically, an MDP $M$ is a tuple consisting of these four components^a—that is, $M=(S,A,T,\eta )$. An infinite run of the MDP is an infinite sequence of state-action pairs describing the evolution of the system over time. A possible infinite run in Figure 1a is $\rho =s_0\stackrel{a_2}{\to }{s}_2\stackrel{a_1}{\to }{s}_1\stackrel{a_2}{\to }{s}_1\stackrel{a_2}{\to }\cdots$ in which the agent reaches $s_1$ from $s_0$ via $s_2$. Similarly, a finite run of length $H$ describes the evolution of the system for $H$ time steps—for example, $\rho =s_0\stackrel{a_2}{\to }{s}_2\stackrel{a_1}{\to }{s}_1\stackrel{a_2}{\to }{s}_1\stackrel{a_2}{\to }{s}_1$ is a finite run of length 4.

In RL, $T$ is a priori unknown, and the agent must learn about the environment by taking actions and observing transitions. In Figure 1a, if the agent repeatedly takes action $a_1$ in state $s_0$, it observes that the system transitions to $s_1$ approximately half the time. The goal is to learn a policy $\pi : S\to A$ mapping states to actions. This policy induces a distribution over runs, generated by sampling an initial state from $\eta$, and iteratively using $\pi$ to select actions and sample next states from $T$. We denote the distribution over infinite runs as $D^{\pi }$ and over finite $H$-length runs as $D_H^{\pi }$.

Reward functions.  Traditionally, tasks in RL are specified using a reward function $r : S\times A\to R$ that assigns rewards for state-action pairs. For example, to reach $s_1$ in Figure 1a, we might set $r(s,a)=1(s=s_1)$, which assigns a reward of 1 if $s=s_1$ and 0 otherwise. For a run $\rho$, this naturally generates a reward sequence (e.g., $0,1,1,\dots$ for a run reaching $s_1$ in one step). For an infinite horizon, RL algorithms typically maximize the expected value of the discounted-sum reward $J\left(\pi \right)=E\left[{\sum }_{t=0}^{\infty }{\gamma }^t{r}_t\right]$ where the random variable $r_t$ denotes the reward obtained at time $t$, and discount factor $0<\gamma <1$ indicates the rate of diminishing returns. In Figure 1a, under the reward function $r(s,a)=1(s=s_1)$, the policy ${\pi }_1$ that chooses action $a_1$ in state $s_0$ will achieve a discounted-sum reward of $0+\gamma +{\gamma }^2+\cdots =\gamma /(1–\gamma )$ with probability 0.5 (when it reaches $s_1$) and 0 with probability 0.5 (when it reaches $s_3$). Hence, $J\left({\pi }_1\right)=\gamma /\left(2(1–\gamma )\right)$. However, the policy ${\pi }_2$ that chooses action $a_2$ in $s_0$ leads to a discounted-sum reward of $0+\cdots +0+{\gamma }^{k+2}+{\gamma }^{k+3}+\cdots ={\gamma }^{k+2}/(1–\gamma )$ if $s_1$ is reached in exactly $k+2$ steps which occurs with probability^b ${(1–\epsilon )}^k\epsilon$. Thus, the expected discounted-sum reward^c is $\epsilon {\gamma }^2/(1–\gamma )·{\sum }_{k=0}^{\infty }{(1–\epsilon )}^k{\gamma }^k=\epsilon {\gamma }^2/\left[(1–\gamma )(1+\gamma \epsilon –\gamma )\right]$. If, instead, given a finite horizon $H$, then RL algorithms maximize the expected reward $J_H\left(\pi \right)=E\left[{\sum }_{t=0}^{H–1}{r}_t\right]$. Finally, the goal of RL is to learn an optimal policy ${\pi }^{*}$ that maximizes $J\left(\pi \right)$ (or $J_H\left(\pi \right)$); we let $J^{*}={sup}_{\pi }J\left(\pi \right)$ (or $J^{*}={sup}_{\pi }{J}_H\left(\pi \right)$) denote the best possible value.

Logical specifications.  A specification $\phi$ is a logical formula encoding whether a finite or infinite run of the MDP solves the desired task. For example, the task of reaching $s_1$ can be encoded by the specification $\phi =\mathrm{Eventually}{s}_1$. A run that starts in $s_0$ and transitions immediately to $s_3$ will never reach $s_1$, and therefore will not satisfy $\phi$. Logical specifications can be straightforwardly composed to express more complex tasks; for instance, the task of sequentially visiting two locations $l_1$ and $l_2$ can be simply expressed as $\mathrm{Eventually}{l}_1$; $\mathrm{Eventually}{l}_2$. The meaning of a specification is given by the semantics function (denoted $〚\phi 〛$) that maps a run $\rho$ to $\{0,1\}$ indicating whether or not the run satisfies $\phi$. The objective of specification-guided RL is to learn a policy that maximizes the probability of achieving the task—that is, $J^{\phi }\left(\pi \right)=E_{\rho \sim D^{\pi }}\left[〚\phi 〛\left(\rho \right)\right]$. In Fig 1a, the policy ${\pi }_1$ that chooses action $a_1$ in $s_0$ assigns a probability of 0.5 to each of the two infinite runs it produces (one that visits $s_1$ and the other than does not), so $J^{\phi }\left({\pi }_1\right)=0.5$. On the other hand, the policy ${\pi }_2$ that chooses action $a_2$ in $s_0$ results in infinitely many trajectories but all of these trajectories eventually visit $s_1$ given $\epsilon >0$. Thus, $J^{\phi }\left({\pi }_2\right)=1$. Clearly, ${\pi }_2$ is optimal.

Reductions to Discounted Rewards.  A natural approach to solving an infinite-horizon specification $\phi$ is to first compile it into a reward function $r_{\phi }$ and then apply standard RL algorithms for discounted rewards that come with guarantees and have state-of-the-art implementations readily available. However, recent work² has proven that without knowledge of the environment model, there are specifications for which no discounted reward function $r$ exists (for any discount factor $\gamma$) such that the policies maximizing $r$ will also maximize the probability of satisfying $\phi$. This impossibility result has profound implications: There are specifications that simply cannot be solved by the strategy of reduction to reward functions. This result arises due to a fundamental mismatch between how discounted rewards and logical specifications measure task completion—discounted rewards inherently care about when the task is completed since future rewards are time-discounted, whereas logical specifications such as $\mathrm{Eventually}{s}_1$ care only about the task eventually being completed.

This mismatch is illustrated by the specification $\mathrm{Eventually}{s}_1$ and the reward function $r(s,a)=1(s=s_1)$ in Figure 1a. Recall that the policy ${\pi }_2$ which takes action $a_2$ in state $s_0$ is optimal with regard to $\mathrm{Eventually}{s}_1$. However, this policy can be made suboptimal with regard to $r(s,a)=1(s=s_1)$ for any discount factor $\gamma$ by choosing an appropriate value of $\epsilon$.

Recent work shows some promising directions under additional assumptions. For instance, Bozkurt et al.⁴ and Hahn et al.⁹ have shown that any LTL specification can be reduced to discounted rewards with an appropriate discount factor that depends on the MDP transitions. More recently, Alur et al.³ have studied the use of discounted LTL, which naturally prioritizes near-term events over distant ones, allowing a direct reduction to discounted rewards.

Theoretical guarantees.  Even if it is impossible to compile logical specification to discounted-sum rewards, we may still hope that we can devise algorithms that directly learn policies to solve infinite-horizon specifications. Our next result shows that the answer remains negative. To formalize this result, we extend the probably approximately correct (PAC) framework²¹ to specification-guided RL. Given a confidence level $\delta >0$ and an error tolerance $\epsilon >0$, an RL algorithm is said to be PAC if after sampling a sufficient number of transitions (as a function of $n,m,\delta ,\epsilon$) in an MDP with $n$ states and $m$ actions, the probability that the learned policy $\pi$ is $\epsilon$-close to optimal (i.e., $J^{*}–J\left(\pi \right)\le \epsilon$) is at least $1–\delta$. Note that the required sample size does not depend on the transition probabilities, allowing agents to determine termination without knowing the true environment dynamics.

While algorithms with PAC guarantees exist for discounted-sum rewards, surprisingly, they are impossible for even simple reachability specifications, such as $\mathrm{Eventually}g$ (where $g$ is a goal state). To understand why, consider the MDP shown in Figure 1b and the specification $\mathrm{Eventually}{s}_1$. When $p_1=1$ and $p_2<1$, the optimal policy chooses action $a_2$ in state $s_0$ since the probability of eventually reaching $s_1$ from $s_2$ is 1, whereas the probability of reaching $s_1$ from $s_0$ is 0 if the agent chooses action $a_1$ in state $s_0$. Similarly, when $p_1<1$ and $p_2=1$, the optimal action at state $s_0$ is $a_1$. Note that altering the transition probabilities slightly can significantly impact the optimal policy. For example, if $p_1=1$ and $p_2=1–x$ for an infinitesimally small $x$, altering the values to $p_1^{\prime }=p_1–x=1–x$ and $p_2^{\prime }=p_2+x=1$ causes the optimal action at $s_0$ to change from $a_2$ to $a_1$. Furthermore, an optimal policy in the original MDP (with $p_1=1$) that reaches $s_1$ with probability 1 will attain a zero probability of reaching $s_1$ in the new MDP. This example illustrates that the specification $\mathrm{Eventually}{s}_1$ is not robust—small changes to the MDP can drastically affect the corresponding optimal policy. In contrast, discounted-sum rewards are robust in the sense that altering the transition probabilities by a small amount only impacts the value $J\left(\pi \right)$ of a policy $\pi$ by a small amount (more precisely, $J\left(\pi \right)$ is a continuous function of the MDP transitions and rewards).

This lack of robustness is the reason PAC algorithms do not exist for specifications. For the sake of contradiction, suppose there is an RL algorithm with a PAC guarantee for $\mathrm{Eventually}{s}_1$. We can run this algorithm for the above two scenarios with slightly different transition probabilities and the same values of $\delta >0.9$ and $\epsilon <1$. Then, for a sufficiently small $x$, it is highly likely that the RL algorithm will see the same samples from the two different MDPs. Thus, the RL algorithm will output the same policy $\pi$, meaning it must attain a zero probability of reaching $s_1$ in one of the two MDPs. As a result, $J^{*}–J\left(\pi \right)=1>\epsilon$ for that MDP, which is a contradiction to the PAC property.

Furthermore, Yang et al.²³ show that PAC guarantees are possible only for finitary specifications (a specification $\phi$ is finitary if there exists a fixed $H$ such that we can decide whether or not an infinite run $\rho =(s_0,s_1,\dots )$ of the system satisfies $\phi$ by only looking at the first $H$ steps). PAC algorithms also exist under additional assumptions—for example, if a lower bound on all non-zero transition probabilities of the MDP is given.⁸

The SPECTRL language.  SPECTRL is a simple specification language that lets users encode tasks such as the ones we discussed in the context of robot navigation.¹⁵ Its syntax is given by the grammar

where $p\subset S$ is a predicate representing a subset of the states. In our warehouse example, the region $X\subseteq S=R^2$ corresponds to such a predicate. Next, $\mathrm{Eventually}p$ denotes eventually (within $H$ steps) reaching a state $s\in p$, and $\phi \mathrm{Ensuring}p$ denotes performing $\phi$ while remaining in the “safe” set $p$ at every step. Furthermore, sequencing ${\phi }_1;{\phi }_2$ denotes first performing ${\phi }_1$ and then ${\phi }_2$, and disjunction ${\phi }_1\vee {\phi }_2$ gives the agent the choice of either performing ${\phi }_1$ or ${\phi }_2$.

In our warehouse example, the task of visiting $X$ while avoiding the obstacle region $O$ (union of all regions marked in red) can be encoded in SPECTRL as ${\phi }_1=(\mathrm{Eventually}X\mathrm{Ensuring}\neg O)$, where $\neg O=SO$ denotes the set of all states that do not belong in $O$. The task of visiting $X$ first and then returning to $A$ before visiting $E$ can be encoded as ${\phi }_2=(\mathrm{Eventually}X;\mathrm{Eventually}A;\mathrm{Eventually}E)$. Finally, ${\phi }_3=((\mathrm{Eventually}X\vee \mathrm{Eventually}E);\mathrm{Eventually}C)\mathrm{Ensuring}\neg O$ specifies that the robot must first visit either $X$ or $E$ and then visit $C$, all while avoiding $O$.

A specification-guided RL algorithm.  Early work on specification-guided RL focused on compiling the specification to a reward function,^15,18,22 including techniques for reward shaping and handling non-Markovian specifications. One effective strategy for reward shaping is to use quantitative semantics for LTL specifications, which assign numerical values to runs of the system that capture how “robustly” the specification is satisfied (while ensuring runs that satisfy the specification are assigned higher values compared to those that do not). To handle history-dependent tasks, one approach is to alter the state space to include relevant information about the history—for example, as a finite state machine called a reward machine.¹² However, some tasks can be challenging to learn with these approaches since even with reward shaping, RL algorithms tend to be myopic, focusing on immediate rewards over long-term ones. Consider our example specification ${\phi }_3$; a typical reward function implementing this task would provide similar rewards for visiting $X$ and $E$, since these two cannot be distinguished without understanding the structure of the MDP. In the MDP, there is no direct way to reach $C$ from $E$, so in fact $X$ is preferable to $E$. Thus, if by chance an RL algorithm learns to solve the initial subtask $\mathrm{Eventually}X\vee \mathrm{Eventually}E$ by visiting $E$ instead of $X$, then it might struggle to reach $C$.

We describe a more recent specification-guided RL algorithm based on SPECTRL called Dijkstra guided RL (DIRL)¹⁶ that addresses this issue by leveraging the structure of the specification in conjunction with knowledge about the MDP gained during training. DIRL consists of two components: using Dijkstra’s algorithm to search for a high-level sequence of subtasks to perform (a.k.a. planning), and using traditional RL algorithms to learn to perform subtasks (a.k.a. learning). The planning component involves computing a shortest path in a directed graph in which edges represent subtasks. The learning component involves, for each subtask, constructing a reward function and using an off-the-shelf RL algorithm to learn a policy to maximize the expected sum of rewards. Instead of performing learning and then planning, DIRL interleaves the two, incorporating information obtained during learning into planning and vice versa.

Figure 2a provides an overview of the algorithm. First, DIRL automatically constructs an abstract graph $G_{\phi }=(V,E)$ representing the high-level structure in the given SPECTRL specification.^d For our example specification ${\phi }_3$, the corresponding abstract graph constructed by DIRL is shown in Figure 2b. Each vertex represents a set of states in the MDP. In this example, the abstract graph has four vertices representing the four regions of our warehouse environment. Each directed edge represents a reachability subtask—namely, the subtask of reaching the set of states represented by the target vertex. For instance, the edge from $A$ to $X$ denotes the subtask of reaching $X$ from $A$. Each edge is optionally labeled with a path constraint—that is, all edges are labeled with the constraint of avoiding the red obstacle regions. Our example graph has two paths from $A$ to $C$ representing the two ways of solving ${\phi }_3$: (i) first go to $X$ and then go to $C$, or (ii) first go to $E$ and then go to $C$. If the agent learns how to perform each subtask along a path in this graph, then the agent can perform the sequence of subtasks dictated by this path to achieve its objective. Thus, the overall problem reduces to two sub-problems corresponding to the two components of DIRL: (i) computing the “best” path in $G_{\phi }$ from the initial vertex $v_0$ to a goal vertex $v_g$ (achieved using Dijkstra’s algorithm^e), and (ii) learning to perform the subtask corresponding to each edge in that path (achieved using RL).

To apply Dijkstra’s algorithm to compute the “best” path, we need to associate a cost to each edge in the graph; ideally, this assignment should ensure that the resulting shortest path corresponds to the high-level plan most likely to solve $\phi$. For intuition, suppose that the probability of completing a subtask corresponding to an edge $e=u\to v\in E$ is independent of the starting state (that is, the specific state in the set of states represented by $u$), and that the agent has already learned how to complete the subtask corresponding to each edge in the graph. Then, letting $p_e$ be the probability of completing the subtask corresponding to edge $e$, we can define the cost of $e$ to be $c_e=–log\left(p_e\right)$. Given a path $e_1,e_2,\dots ,e_{\ell }$, the probability of successfully completing all corresponding subtasks in order is ${\prod }_{i=1}^{\ell }{p}_{e_i}=exp\left({\sum }_{i=1}^{\ell }log\left(p_{e_i}\right)\right)$. Thus, minimizing the sum of edge costs (that is, computing the shortest path) is equivalent to maximizing the probability of completing $\phi$.

This strategy could be implemented by first running learning for each subtask, and then running Djikstra’s algorithm, with no feedback between the two. In practice, this approach does not work because our assumption that $p_e$ is independent of the starting state does not hold. DIRL uses two ideas to address this issue. First, note we do not need the cost of all edges a priori. Thus, DIRL can estimate edge costs lazily—that is, it estimates the cost $c_e$ of edge $e$ only when it is needed by Dijkstra’s algorithm. Whenever an edge cost needs to be estimated, DIRL constructs a (non-sparse) reward function for the corresponding subtask (using quantitative semantics), uses an off-the-shelf RL algorithm to train a policy to perform that subtask and then estimates $p_e$ using simulations.

Second, a key property of Dijkstra’s algorithm is that when the cost of an edge $e=u\to v$ is needed, it has already computed the shortest path from $v_0$ to $u$; this also implies that DIRL has learned policies to solve subtasks for edges in this path. Thus, we can simulate the environment using these policies to obtain samples of states in $u$ (assuming the agent successfully completes the path). This approach not only provides a way to sample initial states for training a subtask policy for $e$, but this distribution of initial states corresponds to the distribution of states encountered when using the learned subtask policy if the final path computed by DIRL contains $e$.

DIRL has been shown to scale well to complex specifications, including realistic applications such as robotic Pick-and-Place environments, where it outperforms prior approaches while requiring fewer than $4\times {10}^5$ samples. Figures 3b–3e show learning curves of DIRL for some complex specifications in the warehouse environment. Recent work has expanded SPECTRL-based approaches to multi-agent scenarios^7,17 and learning verified policies.^13,25