Regret-Free Reinforcement Learning for LTL Specifications
Not on the map. Why?
Abstract (arXiv)
Learning to control an unknown dynamical system with respect to high-level temporal specifications is an important problem in control theory. We present the first regret-free online algorithm for learning a controller for linear temporal logic (LTL) specifications for systems with unknown dynamics. We assume that the underlying (unknown) dynamics is modeled by a finite-state and action Markov decision process (MDP). Our core technical result is a regret-free learning algorithm for infinite-horizon reach-avoid problems on MDPs. For general LTL specifications, we show that the synthesis problem can be reduced to a reach-avoid problem once the graph structure is known. Additionally, we provide an algorithm for learning the graph structure, assuming knowledge of a minimum transition probability, which operates independently of the main regret-free algorithm. Our LTL controller synthesis algorithm provides sharp bounds on how close we are to achieving optimal behavior after a finite number of learning episodes. In contrast, previous algorithms for LTL synthesis only provide asymptotic guarantees, which give no insight into the transient performance during the learning phase.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 14 of its 29 references that are in the map. First posted on arXiv 18 Nov 2024.
Builds on
14 of 29 references.
References · 14
- 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
- 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
- 2019Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guaranteescited by 77
- 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 74
- 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 53
- 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
- 2019Certified Reinforcement Learning with Logic Guidancecited by 35
- 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
- 2020Reinforcement Learning Based Temporal Logic Control with Maximum Probabilistic Satisfactioncited by 22
- 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
- 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
- 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
Built on by
Citing papers per year: 2025: 1.
1 paper.