Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guarantees
Linear Temporal Logic (LTL) is widely used to specify high-level objectives for system policies, and it is highly desirable for autonomous systems to learn the optimal policy with respect to such specifications. However, learning the optimal policy from LTL specifications is not trivial. We present a model-free Reinforcement Learning (RL) approach that efficiently learns an optimal policy for an unknown stochastic system, modelled using Markov Decision Processes (MDPs). We propose a novel and more general product MDP, reward structure and discounting mechanism that, when applied in conjunction with off-the-shelf model-free RL algorithms, efficiently learn the optimal policy that maximizes the probability of satisfying a given LTL specification with optimality guarantees. We also provide improved theoretical results on choosing the key parameters in RL to ensure optimality. To directly evaluate the learned policy, we adopt probabilistic model checker PRISM to compute the probability of the policy satisfying such specifications. Several experiments on various tabular MDP environments across different LTL tasks demonstrate the improved sample efficiency and optimal policy convergence.
Code (1)
Tasks
reinforcement-learningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality
Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves asymptotic convergence to optimal policies…
Reinforcement LearningProSh: Probabilistic Shielding for Model-free Reinforcement Learning
Safety is a major concern in reinforcement learning (RL): we aim at developing RL systems that not only perform optimally, but are also safe to deploy by providing formal guarantees about their safety. To this end, we in…
Reinforcement LearningRegret-Free Reinforcement Learning for LTL Specifications
Reinforcement learning (RL) is a promising method to learn optimal control policies for systems with unknown dynamics. In particular, synthesizing controllers for safety-critical systems based on high-level specification…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Resilient Constrained Reinforcement Learning
We study a class of constrained reinforcement learning (RL) problems in which multiple constraint specifications are not identified before training. It is challenging to identify appropriate constraint specifications due…
Decision Makingreinforcement-learningReinforcement LearningReinforcement Learning (RL)UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithms
Policy evaluation is an important instrument for the comparison of different algorithms in Reinforcement Learning (RL). Yet even a precise knowledge of the value function $V^{\pi}$ corresponding to a policy $\pi$ does no…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)