This paper proposes a method for efficient training of Q-function for continuous-state Markov Decision Processes (MDP), such that the traces of the resulting policies satisfy a Linear Temporal Logic (LTL) property. LTL, a modal logic, can express a wide range of time-dependent logical properties including safety and liveness. We convert the LTL property into a limit deterministic Buchi automaton with which a synchronized product MDP is constructed. The control policy is then synthesised by a reinforcement learning algorithm assuming that no prior knowledge is available from the MDP. The proposed method is evaluated in a numerical study to test the quality of the generated control policy and is compared against conventional methods for policy synthesis such as MDP abstraction (Voronoi quantizer) and approximate dynamic programming (fitted value iteration). Markov Decision Processes (MDPs) are extensively used as a family of stochastic processes in automatic control, computer science, economics, etc. to model sequential decision-making problems. Reinforcement Learning (RL) is a machine learning algorithm that is widely used to train an agent to interact with an MDP when the stochastic behaviour of the MDP is initially unknown. However, conventional RL is mostly focused on problems in which MDP states and actions are finite. Nonetheless, many interesting real-world tasks, require actions to be taken in response to high-dimensional or real-valued sensory inputs BID5 . For example, consider the problem of drone control in which the drone state is represented as its Euclidean position (x, y, z) ∈ R 3 .Apart from state space discretisation and then running vanilla RL on the abstracted MDP, an alternative solution is to use an approximation function which is achieved via regression over the set of samples. At a given state, this function is able to estimate the value of the expected reward. Therefore , in continuous-state RL, this approximation replaces conventional RL state-action-reward look-up table which is used in finite-state MDPs. A number of methods are available to approximate the expected reward, e.g. CMACs BID34 , kernel-based modelling BID22 , tree-based regression BID7 , basis functions BID3 , etc. Among these methods, neural networks offer great promise in reward modelling due to their ability to approximate any non-linear function BID13 . There exist numerous successful applications of neural networks in RL for infinite or large-state space MDPs, e.g. Deep Q-networks BID19 , TD-Gammon BID36 , Asynchronous Deep RL BID20 , Neural Fitted Q-iteration BID26 , CACLA BID39 .In this paper , we propose to employ feedforward networks (multi-layer perceptrons) to synthesise a control policy for infinite-state MDPs such that the generated traces satisfy a Linear Temporal Logic (LTL) property. LTL allows to specify complex mission tasks in a rich time-dependent formal language. By employing LTL we are able to express complex high-level control objectives that are hard to express and achieve for other methods from vanilla RL BID35 BID31 to more recent developments such as Policy Sketching BID1 . Examples include liveness and cyclic properties, where the agent is required to make progress while concurrently executing components, to take turns in critical sections or to execute a sequence of tasks periodically. The purpose of this work is to show that the proposed architecture efficiently performs and is compatible with RL algorithms that are core of recent developments in the community.Unfortunately, in the domain of continuous-state MDPs, to the best of our knowledge, no research has been done to enable RL to generate policies according to full LTL properties. On the other hand, the problem of control synthesis in finite-state MDPs for temporal logic has been considered in a number of works. In BID41 , the property of interest is an LTL property, which is converted to a Deterministic Rabin Automaton (DRA). A modified Dynamic Programming (DP) algorithm is then proposed to maximise the worst-case probability of satisfying the specification over all transition probabilities. Notice that in this work the MDP must be known a priori. BID8 and BID2 assume that the given MDP has unknown transition probabilities and build a Probably Approximately Correct MDP (PAC MDP), which is producted with the logical property after conversion to DRA. The goal is to calculate the value function for each state such that the value is within an error bound of the actual state value where the value is the probability of satisfying the given LTL property. The PAC MDP is generated via an RL-like algorithm and standard value iteration is applied to calculate the values of states.Moving away from full LTL logic, scLTL is proposed for mission specification, with which a linear programming solver is used to find optimal policies. The concept of shielding is employed in BID0 to synthesise a reactive system that ensures that the agent stays safe during and after learning. However, unlike our focus on full LTL expressivity , BID0 adopted the safety fragment of LTL as the specification language. This approach is closely related to teacher-guided RL BID37 , since a shield can be considered as a teacher, which provides safe actions only if absolutely necessary. The generated policy always needs the shield to be online, as the shield maps every unsafe action to a safe action. Almost all other approaches in safe RL either rely on ergodicity of the underlying MDP, e.g. (Moldovan & Abbeel, 2012) , which guarantees that any state is reachable from any other state, or they rely on initial or partial knowledge about the MDP, e.g. BID32 and BID17 ). This paper proposes LCNFQ, a method to train Q-function in a continuous-state MDP such that the resulting traces satisfy a logical property. The proposed algorithm uses hybrid modes to automatically switch between neural nets when it is necessary. LCNFQ is successfully tested in a numerical example to verify its performance. e. s i+1 belongs to the smallest Borel set B such that P (B|s i , a i ) = 1 (or in a discrete MDP, P (s i+1 |s i , a i ) > 0). We might also denote ρ as s 0 .. to emphasize that ρ starts from s 0 .Definition A.2 (Stationary Policy) A stationary (randomized) policy Pol : S × A → [0, 1] is a mapping from each state s ∈ S, and action a ∈ A to the probability of taking action a in state s. A deterministic policy is a degenerate case of a randomized policy which outputs a single action at a given state, that is ∀s ∈ S, ∃a ∈ A, Pol (s, a) = 1.In an MDP M, we define a function R : S × A → R + 0 that denotes the immediate scalar bounded reward received by the agent from the environment after performing action a ∈ A in state s ∈ S.Definition A.3 (Expected (Infinite-Horizon) Discounted Reward) For a policy Pol on an MDP M, the expected discounted reward is defined as BID35 : DISPLAYFORM0 where E Pol [·] denotes the expected value given that the agent follows policy Pol , γ ∈ [0, 1) is a discount factor and s 0 , ..., s n is the sequence of states generated by policy Pol up to time step n. Definition A.4 (Optimal Policy) Optimal policy Pol * is defined as follows: DISPLAYFORM1 where D is the set of all stationary deterministic policies over the state space S.
As safety is becoming a critical notion in machine learning we believe that this work can act as a foundation for a number of research directions such as safety-aware learning algorithms.
{"src": "scitldr-AIC_train", "paper_id": "ryxMjoRcYm"}