Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration

Consider a robot that resides in a partitioned environment with a finite number of states. To capture uncertainty in the robot motion and the workspace, we model the interaction of the robot with the environment as a Markov Decision Process (MDP) of unknown structure, which is defined as follows.

For instance, Assumption II.3 implies that obstacles and regions of interest in the environment are static. This assumption can be relaxed using probabilistically labeled MDPs as in [8].

The robot is responsible for accomplishing a task expressed as an LTL formula, such as sequencing, coverage, surveillance, data gathering or connectivity tasks [41, 42, 43, 44, 45, 46, 47]. LTL is a formal language that comprises a set of atomic propositions $\mathcal{AP}$, the Boolean operators, i.e., conjunction $\wedge$ and negation $\neg$, and two temporal operators, next $\bigcirc$ and until $\cup$. LTL formulas over a set $\mathcal{AP}$ can be constructed based on the following grammar: $\phi::=\text{true}~{}|~{}\pi~{}|~{}\phi_{1}\wedge\phi_{2}~{}|~{}\neg\phi~{}|~{}\bigcirc\phi~{}|~{}\phi_{1}~{}\cup~{}\phi_{2},$ where $\pi\in\mathcal{AP}$. The other Boolean and temporal operators, e.g., always $\square$, have their standard syntax and meaning [3]. An infinite word $w$ over the alphabet $2^{\mathcal{AP}}$ is defined as an infinite sequence $w=\pi_{0}\pi_{1}\pi_{2}\dots\in(2^{\mathcal{AP}})^{\omega}$, where $\omega$ denotes infinite repetition and $\pi_{t}\in 2^{\mathcal{AP}}$, $\forall t\in\mathbb{N}$. The language $\left\{w\in(2^{\mathcal{AP}})^{\omega}|w\models\phi\right\}$ is defined as the set of words that satisfy the LTL formula $\phi$, where $\models\subseteq(2^{\mathcal{AP}})^{\omega}\times\phi$ is the satisfaction relation [3]. In what follows, we consider atomic propositions of the form $\pi^{i}$ that are true if the robot is in state $x_{i}\in{\mathcal{X}}$ and false otherwise.

Any LTL formula can be translated into a Deterministic Rabin Automaton (DRA) defined as follows.

An infinite run $\rho_{D}=q_{D}^{0}q_{D}^{1}\dots q_{D}^{t}\dots$ of $D$ over an infinite word $w=\sigma_{0}\sigma_{1}\sigma_{2}\dots$, where $\sigma_{t}\in\Sigma$, $\forall t\in\mathbb{N}$, is an infinite sequence of DRA states $q_{D}^{t}$, $\forall t\in\mathbb{N}$, such that $\delta(q_{D}^{t},\sigma_{t})=q_{D}^{t+1}$. An infinite run $\rho_{D}$ is called accepting if there exists at least one pair $({\mathcal{G}}_{i},{\mathcal{B}}_{i})$ such that $\texttt{Inf}(\rho_{D})\cap{\mathcal{G}}_{i}\neq\varnothing$ and $\texttt{Inf}(\rho_{D})\cap{\mathcal{B}}_{i}=\varnothing$, where $\texttt{Inf}(\rho_{D})$ represents the set of states that appear in $\rho_{D}$ infinitely often; see also Ex. II.5.

Given the MDP $\mathfrak{M}$ and the DRA $\mathfrak{D}$, we define the product MDP (PMDP) $\mathfrak{P}=\mathfrak{M}\times\mathfrak{D}$ as follows.

Given any policy $\boldsymbol{\mu}:{\mathcal{S}}\rightarrow{\mathcal{A}}_{\mathfrak{P}}$ for $\mathfrak{P}$, we define an infinite run $\rho_{\mathfrak{P}}^{\boldsymbol{\mu}}$ of $\mathfrak{P}$ to be an infinite sequence of states of $\mathfrak{P}$, i.e., $\rho_{\mathfrak{P}}^{\boldsymbol{\mu}}=s_{0}s_{1}s_{2}\dots$, where $P_{\mathfrak{P}}(s_{t},\boldsymbol{\mu}(s_{t}),s_{t+1})>0$. By definition of the accepting condition of the DRA $\mathfrak{D}$, an infinite run $\rho_{\mathfrak{P}}^{\boldsymbol{\mu}}$ is accepting if there exists at least one pair $i\in\{1,\dots,f\}$ such that $\texttt{Inf}(\rho_{\mathfrak{P}}^{\boldsymbol{\mu}})\cap{\mathcal{G}}^{\mathfrak{P}}_{i}\neq\emptyset$, and $\texttt{Inf}(\rho_{\mathfrak{P}}^{\boldsymbol{\mu}})\cap{\mathcal{B}}^{\mathfrak{P}}_{i}=\emptyset$.

Our goal is to compute a policy for the PMDP that maximizes the satisfaction probability $\mathbb{P}(\boldsymbol{\mu}\models\phi~{}|~{}s_{0})$ of an LTL-encoded task $\phi$. A formal definition of this probability can be found in [3, 48, 49]. To this end, we first adopt existing reward functions $R:{\mathcal{S}}\times{\mathcal{A}}_{\mathfrak{P}}\times{\mathcal{S}}\rightarrow\mathbb{R}$ defined based on the accepting condition of the PMDP as e.g., in [6]. Then, our goal is to compute a policy $\boldsymbol{\mu}^{*}$ that maximizes the expected accumulated return, i.e., $\boldsymbol{\mu}^{*}(s)=\arg\max\limits_{\boldsymbol{\mu}\in\mathcal{D}}~{}{U}^{\boldsymbol{\mu}}(s)$, where $\mathcal{D}$ is the set of all stationary deterministic policies over $\mathcal{S}$, and

In (1), $\mathbb{E}^{\boldsymbol{\mu}}[\cdot]$ denotes the expected value given that the PMDP follows the policy $\boldsymbol{\mu}$ [50], $0\leq\gamma<1$ is the discount factor, and $s_{0},...,s_{t}$ is the sequence of states generated by $\boldsymbol{\mu}$ up to time $t$, initialized at $s_{0}$. Since the PMDP has a finite state/action space and $\gamma<1$, there exists a stationary deterministic optimal policy $\boldsymbol{\mu}^{*}$ [50]. The reward function $R$ and the discount factor $\gamma$ should be designed so that maximization of (1) is equivalent to maximization of the satisfaction probability. Efforts towards this direction are presented e.g., in [6, 8] while provably correct rewards and discount factors for PMDPs constructed using LDBA, instead of DRA, are proposed in [9, 14, 16]. However, as discussed in Section I, due to sparsity of these rewards, these methods are sample-inefficient. This is the main challenge that this paper aims to address.

First, the LTL task $\phi$ is converted into a DRA; see Definition II.4 [line 2, Alg. 1]. Then, we define a distance-like function over the DRA state-space that measures how ’far’ the robot is from accomplishing the assigned LTL tasks [line 3, Alg. 1]. In other words, this function returns how far any given DRA state is from the sets of accepting states ${\mathcal{G}}_{i}$. To define this function, first, we remove from the DRA all infeasible transitions that cannot be physically enabled. To define infeasible transitions, we first define feasible symbols as follows [33]; see Fig. 1.

Then, we prune the DRA by removing infeasible DRA transitions defined as follows:

Next, we define a function $d:{\mathcal{Q}}_{D}\times{\mathcal{Q}}_{D}\rightarrow\mathbb{N}$ that returns the minimum number of feasible DRA transitions required to reach a state $q_{D}^{\prime}\in{\mathcal{Q}}_{D}$ starting from a state $q_{D}\in{\mathcal{Q}}_{D}$. Particularly, we define this function as follows [33, 35]:

where $SP_{q_{D},q_{D}^{\prime}}$ denotes the shortest path (in terms of hops) in the pruned DRA from $q_{D}$ to $q_{D}^{\prime}$ and $|SP_{q_{D},q_{D}^{\prime}}|$ stands for its cost (number of hops). Note that if $d(q_{D}^{0},q_{D})=\infty$, for all $q_{D}\in{\mathcal{G}}_{i}$ and for all $i\in\{1,\dots,n\}$, then the LTL formula can not be satisfied since the in the pruning process, only the DRA transitions that are impossible to enable are removed. Next, using (2), we define the following distance function:¹¹1Observe that, unlike [36, 51], $d_{F}(q_{D},{\mathcal{F}})$ may not be equal to $0$ even if $q_{D}\in{\mathcal{G}}_{i}$. The latter may happen if $q_{D}$ does not have a feasible self-loop.

In words, (3) measures the distance from any DRA state $q_{D}$ to the set of accepting pairs, i.e., the distance to the closest DRA state $q_{D}^{G}$ that belongs to $\cup_{i\in\{1,\dots,f\}}{\mathcal{G}}_{i}$; see also Fig. 1.

In this section, we present the proposed accelerated RL algorithm for LTL control synthesis [lines 4-20, Alg. 1]. The output of the proposed algorithm is a stationary deterministic policy $\boldsymbol{\mu}^{*}$ for $\mathfrak{P}$ maximizing (1). To construct $\boldsymbol{\mu}^{*}$, we employ episodic Q-learning (QL). Similar to standard QL, starting from an initial PMDP state, we define learning episodes over which the robot picks actions as per a stationary and stochastic control policy $\boldsymbol{\mu}:{\mathcal{S}}\times{\mathcal{A}}_{\mathfrak{P}}\rightarrow[0,1]$ that eventually converges to $\boldsymbol{\mu}^{*}$ [lines 4-5, Alg. 1]. Each episode terminates after a user-specified number of time steps $\tau$ or if the robot reaches a deadlock PMDP state, i.e., a state with no outgoing transitions [lines 7-20, Alg. 1]. Notice that the hyper-parameter $\tau$ should be selected to be large enough to ensure that the agent learns how to repetitively visit the accepting states [9, 8, 13]. The RL algorithm terminates once an action value function $Q^{\boldsymbol{\mu}}(s,a)$ has converged. This action value function is defined as the expected return for taking action $a$ when at state $s$ and then following policy $\boldsymbol{\mu}$ [52], i.e.,

We have that $U^{\boldsymbol{\mu}}(s)=\max_{a\in\mathcal{A}_{\mathfrak{P}}(s)}Q^{\boldsymbol{\mu}}(s,a)$ [52]. The action-value function $Q^{\boldsymbol{\mu}}(s,a)$ can be initialized arbitrarily.

During any learning episode the following process is repeated until the episode terminates. First, given the PMDP state $s_{t}$ at the current time step $t$, initialized as $s_{t}=s_{0}$ [line 9, Alg. 1], an action $a_{t}$ is selected as per a policy $\boldsymbol{\mu}$ [line 11, Alg. 1]; the detailed definition of $\boldsymbol{\mu}$ will be given later. The selected action is executed yielding the next state ${s}_{t+1}=(x_{t+1},q_{t+1})$, and a reward $R({s}_{t},a_{t},{s}_{t+1})$. For instance, the reward function $R$ can be constructed as in [6] defined as follows:

In (5), we have that $r_{{\mathcal{G}}}>0$, for all $i\in\{1,\dots,f\}$, and $r_{d}<r_{{\mathcal{B}}}<r_{0}\leq 0$. This reward function motivates the robot to satisfy the PMDP accepting condition, i.e., to visit the states ${\mathcal{G}}_{j}^{\mathfrak{P}}$ as often as possible and minimize the number of times it visits ${\mathcal{B}}_{i}^{\mathfrak{P}}$ and deadlock states while following the shortest possible path; deadlock states are visited when the LTL task is violated, e.g., when collision with an obstacle occurs.

Given the new state ${s}_{t+1}$, the MDP model of the robot is updated. In particular, every time an MDP transition is enabled, the corresponding transition probability is updated. Let $\hat{P}(x_{t},a_{t},x_{t+1})$ denote the estimated MDP transition probability from state $x_{t}\in{\mathcal{X}}$ to state $x_{t+1}\in{\mathcal{X}}$, when an action $a$ is taken. These estimated MDP transition probabilities are initialized so that $\hat{P}(x,a,x^{\prime})=0$, for all combinations of states and actions, and they are continuously updated at every time step $t$ of each episode as [lines 13-15]:

where (i) $n:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{N}$ is a function that returns the number of times action $a$ has been taken at an MDP state $x$ and (ii) $c:\mathcal{X}\times\mathcal{A}\times{\mathcal{X}}\rightarrow\mathbb{N}$ is a function that returns the number of times an MDP state $x^{\prime}$ has been visited after taking action $a$ at a state $x$. Note that as $n(x,a)\to\infty$ the estimated transition probabilities $\hat{P}(x,a,x^{\prime})$ converge asymptotically to the true transition probabilities $P(x,a,x^{\prime})$, for all transitions.

Next, the action value function is updated as follows [52] [line 17, Alg. 1] :

where $n_{\mathfrak{P}}:\mathcal{S}\times\mathcal{A}_{\mathfrak{P}}\rightarrow\mathbb{N}$ counts the number of times that action $a$ has been taken at the PMDP state $s$. Once the action value function is updated, the current PMDP state is updated as $s_{t}=s_{t+1}$, the time step $t$ is increased by one, and the policy $\boldsymbol{\mu}$ gets updated [lines 18-20, Alg. 1].

As a policy $\boldsymbol{\mu}$, we propose an extension of the $\epsilon$-greedy policy, called $(\epsilon,\delta)$-greedy policy, that selects an action $a$ at an PMDP state $s$ by using the learned action-value function $Q^{\boldsymbol{\mu}}(s,a)$ and the continuously learned transition probabilities $\hat{P}(x,a,x^{\prime})$. Formally, the $(\epsilon,\delta)$-greedy policy $\boldsymbol{\mu}$ is defined as

where $\delta_{b},\delta_{e}\in[0,1]$ and $\epsilon=\delta_{b}+\delta_{e}\in[0,1]$. In words, according to this policy, (i) with probability $1-\epsilon$, the greedy action $a^{*}=\operatornamewithlimits{argmax}_{a\in\mathcal{A}_{\mathfrak{P}}}Q(s,a)$ is taken (as in the standard $\epsilon$-greedy policy); and (ii) an exploratory action is selected with probability $\epsilon=\delta_{b}+\delta_{e}$. The exploration strategy is defined as follows: (ii.1) with probability $\delta_{e}$ a random action $a$ is selected (random exploration); and (ii.2) with probability $\delta_{b}$ the action, denoted by $a_{b}$, that is most likely to drive the robot towards an accepting product state in ${\mathcal{G}}_{i}^{\mathfrak{P}}$ is taken (biased exploration). The action $a_{b}$ will be defined formally in Section III-C. As in standard QL, $\epsilon$ should asymptotically converge to $0$ while ensuring that eventually all actions have been applied infinitely often at all states. This ensures that $\boldsymbol{\mu}$ asymptotically converges to the optimal greedy policy

where $Q^{*}$ is the optimal action value function; see Sec. IV-A. We note that $Q^{\boldsymbol{\mu}^{*}}(s,\boldsymbol{\mu}^{*}(s))=U^{\boldsymbol{\mu}^{*}}(s)=V^{*}({s})$, where $V^{*}({s})$ is the optimal value function that could have been computed if the MDP was fully known [52, 53]. Given $\epsilon$, selection of the parameters $\delta_{e}$ and $\delta_{b}$ is discussed in Sec. IV.

Next, we describe the design of the biased action $a_{b}$ in (8). First, we need to introduce the following definitions; see Fig. 2. Let $s_{t}=(x_{t},q_{t})$ denote the current PMDP state at the current learning episode and time step $t$ of Algorithm 1. Let ${\mathcal{Q}}_{\text{goal}}(q_{t})\subset{\mathcal{Q}}$ be a set that collects all DRA states that are one-hop reachable from $q_{t}$ in the pruned DRA and they are closer to the accepting DRA states than $q_{t}$ is, as per (3). Formally, ${\mathcal{Q}}_{\text{goal}}(q_{t})$ is defined as follows:

Also, let ${\mathcal{X}}_{\text{goal}}(q_{t})\subseteq{\mathcal{X}}$ be a set of MDP states, denoted by $x_{\text{goal}}$, that if the robot eventually reaches, then transition from $s_{t}$ to a product state $s_{\text{goal}}=[x_{\text{goal}},q_{\text{goal}}]$ will occur, where $q_{\text{goal}}\in{\mathcal{Q}}_{\text{goal}}(q_{t})$; see also Ex. III.6. Formally, ${\mathcal{X}}_{\text{goal}}(q_{t})$ is defined as follows:

Next, we view the continuously learned MDP as a weighted directed graph ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},w)$ where the set ${\mathcal{V}}$ is the set of MDP states, ${\mathcal{E}}$ is the set of edges, and $w:{\mathcal{E}}\rightarrow\mathbb{R}_{+}$ is function assigning weights to each edge. Specifically, an edge from the node (MDP state) $x$ to $x^{\prime}$ exists if there exists at least one action $a\in{\mathcal{A}}(x)$ such that $\hat{P}(x,a,x^{\prime})>0$. Hereafter, we assign a weight equal to $1$ to each edge; see also Remarks III.4-III.5. We denote the cost of the shortest path from $x$ to $x^{\prime}$ by $J_{x,x^{\prime}}$. Next, we define the cost of the shortest path connecting a state $x$ to the set ${\mathcal{X}}_{\text{goal}}$ as follows:

Let $J$ be the total number of paths from $x$ to ${\mathcal{X}}_{\text{goal}}$, where their length (i.e., number of hops) is $J_{x,{\mathcal{X}}_{\text{goal}}}$. We denote such a path by $p_{j}^{t}$, $j\in{\mathcal{J}}:=\{1,\dots,J\}$, and the $e$-th MDP state in this path by $p_{j}^{t}(e)$. Then, among all the paths $p_{j}^{t}$, we compute the one with the minimum uncertainty-based cost $C(p_{j}^{t})$; see Fig. 2. We define this cost as

where the maximization is over all actions $a\in{\mathcal{A}}(p_{j}^{t}(e))$. We denote by $p^{*}$ the path with the minimum cost $C(p_{j}^{t})$, i.e., $p^{*}=p_{j^{*}}^{t}$, where $j^{*}=\operatornamewithlimits{argmax}_{j}C(p_{j}^{t})$. Thus, we have that:

Once $p^{*}$ is constructed, the action $a_{b}$ is defined as follows:

where $x_{b}=p^{*}(2)$; see Fig. 2. In words, $a_{b}$ is the action with the highest probability of allowing the system to reach the state $p^{*}(2)$, i.e., to move along the best path $p^{*}$. Observe that computation of the biased action does not depend on the employed reward structure nor on perfectly learning all MDP transition probabilities.

In Proposition IV.1, the equality $U^{\boldsymbol{\mu^{\prime}}}(s)=U^{\boldsymbol{\mu}}(s)$, $\forall s\in{\mathcal{S}}$, holds if $\boldsymbol{\mu}=\boldsymbol{\mu}^{\prime}=\boldsymbol{\mu}^{*}$, where $\boldsymbol{\mu}^{*}$ is the optimal policy [52].

In this section, we demonstrate the myopic benefit of the biased exploration; the proofs can be found in Appendix B. To formally describe it we introduce first the following definitions. Let $s_{t}=(x_{t},q_{t})$ be the PMDP state at the current time step $t$ of an RL episode of Algorithm 1. Also, let ${\mathcal{R}}(x_{t})\subseteq{\mathcal{X}}$ denote a set collecting all MDP states that can be reached within one hop from $x_{t}$, i.e.,

Then, we can define the set ${\mathcal{X}}_{\text{closer}}$ that collects all MDP states that are one hop reachable from $x_{t}$ and they are closer to ${\mathcal{X}}_{\text{goal}}(x_{t})$ than $x_{t}$ is, i.e.,

The following result shows that the probability of $x_{t+1}\in{\mathcal{X}}_{\text{closer}}(x_{t})$ is higher when biased exploration is employed.

Next, we provide a ‘weaker’ result which, however, does not require the strong requirement of (18). The following result shows that the probability that the next state $x_{t+1}$ will be equal to $x_{b}\in{\mathcal{X}}_{\text{closer}}$ (as opposed to any state in ${\mathcal{X}}_{\text{closer}}$ in Prop. IV.2) is greater when bias is introduced in the exploration phase.

In this section, we demonstrate the non-myopic effect of the biased exploration; the proofs can be found in Appendix C. To present our main results, we need to introduce the following definitions. Let $s_{t}=(x_{t},q_{t})$ be the current PMDP state. Also, let $t^{*}=J_{x_{t},{\mathcal{X}}_{\text{goal}}}$ denote the length (i.e., the number of hops/MDP transitions) of the paths $p_{j}^{t}$. Recall that all paths $p_{j}^{t}$, $j\in{\mathcal{J}}$, share the same length, in terms of number of hops, by construction. Second, we define a function $\beta:{\mathcal{J}}\rightarrow[0,1]$ that maps every path $p_{j}^{t}$, $j\in{\mathcal{J}}$, into $[0,1]$ as follows: