Regret-Free Reinforcement Learning for LTL Specifications

Rupak Majumdar, Mahmoud Salamati, Sadegh SoudjaniarXiv 2024 · OpenReview

Abstract

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.

Introduction

In traditional Reinforcement Learning (RL), the primary objective is typically to maximize a scalar reward signal. While effective for many tasks, this paradigm struggles to capture the complex, multi-stage requirements often found in robotics and safety-critical systems. For instance, a robot might need to satisfy a specification such as: "Visit the charging station every 10 minutes, avoid the wet floor, and only enter the lab if the light is green." Such requirements are naturally expressed using Linear Temporal Logic (LTL).

While existing research has demonstrated methods for learning policies that satisfy LTL specifications, most current approaches offer only asymptotic guarantees. This means they ensure convergence to an optimal policy in the limit of infinite time but provide no bounds on the "regret" or performance loss incurred during the learning process. This paper introduces ZeroReg, the first algorithm to provide finite-time, regret-free performance guarantees for LTL specifications in environments with unknown dynamics.

The ZeroReg Framework

The primary challenge in applying standard regret-minimization techniques (like UCRL2) to LTL tasks is that the resulting "product" system—formed by combining the system's MDP with the LTL specification's automaton—is often non-communicating. In such systems, an agent can enter "dead-end" states where the task can no longer be completed (e.g., by violating a safety property). Standard algorithms assume the agent can always navigate between any two states, an assumption that fails in LTL scenarios.

ZeroReg addresses these challenges through a modular architecture that reduces general LTL synthesis to a series of reach-avoid problems.

The ZeroReg architecture, showing the integration of graph identification and regret-free policy synthesis.

The framework relies on three core components:

  1. Optimism in the Face of Uncertainty: The agent maintains an interval MDP (iMDP), which represents a range of plausible transition probabilities based on observed data. By acting "optimistically"—choosing the most favorable transitions within these ranges—the agent naturally balances exploration and exploitation.
  2. Episode-Specific Deadlines ($H_k$): To handle the risk of getting stuck in non-communicating states, ZeroReg introduces a deadline for each episode. If the agent fails to reach a goal or terminal state by the deadline, the episode is terminated. This mechanism allows the algorithm to bound the number of "slow" episodes, which is critical for proving sublinear regret.
  3. Graph Identification: Before solving the full LTL task, the agent must identify which states are connected. The GraphLearn algorithm performs this structure identification, requiring only a known lower bound on non-zero transition probabilities ($p_{min}$).

Theoretical Guarantees

The central contribution of this work is the proof that ZeroReg achieves a regret bound of $O(\sqrt{K})$, where $K$ is the number of episodes. This sublinear growth indicates that the average regret per episode vanishes as the agent gains more experience, a "gold standard" in online learning.

The proof hinges on showing that the number of episodes that exceed the deadline $H_k$ grows sublinearly. By setting $H_k$ to grow logarithmically with the number of episodes, the authors ensure that the agent eventually learns enough about the environment to avoid "slow" behavior, effectively navigating the non-communicating structure of the LTL-constrained MDP.

Experimental Evaluation

The algorithm was evaluated in a stochastic Gridworld environment, a standard benchmark for formal methods in RL. The task involved a reach-avoid specification ($\phi = \neg \text{Avoid } \mathcal{U} \text{ Goal}$), requiring the agent to navigate from a starting point to a target cell while avoiding obstacles. The dynamics were stochastic, with a 10% chance of movement failure.

In head-to-head comparisons with the state-of-the-art $\omega$-PAC algorithm, ZeroReg demonstrated significantly faster convergence. Unlike PAC algorithms that wait for large batches of data before updating, ZeroReg updates its model and policy after every episode. This incremental update strategy leads to much higher sample efficiency, with empirical normalized regret dropping toward zero within the first few hundred episodes.

Conclusion and Future Work

ZeroReg provides the first finite-time performance guarantees for reinforcement learning under complex LTL specifications. By combining optimistic planning with episode deadlines and graph identification, it overcomes the hurdles posed by non-communicating state spaces.

However, several challenges remain. The current requirement for a known $p_{min}$ can be restrictive if the minimum transition probability is extremely small or unknown. Furthermore, extending these "regret-free" guarantees to continuous state spaces and handling the exponential complexity of large LTL formulas are key areas for future research.

Summary updated

Abstract

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.
BibTeX
@misc{majumdar2024regret,
  author = {Rupak Majumdar and Mahmoud Salamati and Sadegh Soudjani},
  title = {{Regret-Free Reinforcement Learning for LTL Specifications}},
  year = {2024},
  eprint = {2411.12019},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.12019},
}
Figure