PaperlayerView exact revision on arXiv

Source-linked AI summary

Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications

Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, Calin Belta

arXiv:1609.07409v1eess.SY

TL;DR

The paper addresses STL policy learning when stochastic transition dynamics are unknown and standard Q-learning cannot directly optimize STL satisfaction objectives. It remodels trajectories and approximates the objectives into reward sums, obtaining bounded approximations and better robustness-based simulation policies after equal training.

  • Problem

    The central gap is that STL synthesis with unknown stochastic dynamics requires optimizing satisfaction probability or expected robustness, neither of which has standard Q-learning reward-sum form.

  • Method

    The method builds a τ-MDP from τ-length trajectories and uses log-sum-exp objective approximations so Q-learning can optimize immediate-reward sums.

  • Results

    Theorem 4.2 provides performance bounds showing approximate policies can be sufficiently close to original solutions for suitable approximation parameters.

  • Takeaways & Limitations

    After the same training, expected-robustness maximization produced better policies than satisfaction-probability maximization in the reported case studies.

Abstract

from arXiv · show

This paper addresses the problem of learning optimal policies for satisfying signal temporal logic (STL) specifications by agents with unknown stochastic dynamics. The system is modeled as a Markov decision process, in which the states represent partitions of a continuous space and the transition probabilities are unknown. We formulate two synthesis problems where the desired STL specification is enforced by maximizing the probability of satisfaction, and the expected robustness degree, that is, a measure quantifying the quality of satisfaction. We discuss that Q-learning is not directly applicable to these problems because, based on the quantitative semantics of STL, the probability of satisfaction and expected robustness degree are not in the standard objective form of Q-learning. To resolve this issue, we propose an approximation of STL synthesis problems that can be solved via Q-learning, and we derive some performance bounds for the policies obtained by the approximate approach. The performance of the proposed method is demonstrated via simulations.

I. INTRODUCTION

The paper studies STL control for unknown stochastic systems, targeting both satisfaction probability and expected robustness. It explains why standard Q-learning does not directly fit these objectives and motivates an approximation-based solution.

  • STL specifies rich, time-sensitive tasks involving physical bounds and time intervals, while robustness degree quantifies how strongly a signal satisfies a formula.
  • The paper formulates synthesis problems that maximize either the probability of STL satisfaction or the expected robustness degree.
  • STL satisfaction can depend on trajectory history, so the paper defines a τ-MDP whose states encode τ-step system histories.
  • Standard Q-learning is not directly applicable because STL satisfaction probability and expected robustness are not objectives expressed as sums of immediate rewards.
  • The paper approximates these objectives so Q-learning can solve the resulting synthesis problems, derives performance bounds, and evaluates the approach in simulations.
  • The example specification requires visiting regions A and B every 3 minutes over a 10-minute horizon using globally repeated eventually operators.

A. System Model

The system is modeled as an MDP over discretized continuous state space with motion primitives, but its transition probabilities are unknown. The synthesis objectives maximize satisfaction probability or expected robustness.

  • The MDP consists of a partition-based state space, finite motion primitives, probabilistic transitions, and a reward function.
  • Each motion primitive moves the system between adjacent discretized states, and trajectories record the resulting sequence over discrete time steps.
  • The paper assumes the MDP model is available but the transition probability function is unknown during interaction with the system.
  • The two synthesis problems optimize either the probability that the trajectory satisfies Φ or its expected robustness degree.

IV. CONTROL SYNTHESIS VIA Q-LEARNING

The control-synthesis section uses reinforcement learning for unknown stochastic dynamics, identifies the mismatch between the paper’s objectives and standard Q-learning, and introduces approximation as the remedy.

  • The paper uses Q-learning to design control policies through trial-and-error interaction with environments whose stochastic dynamics are unknown.

A. Q-learning

Q-learning learns an optimal policy for a finite MDP by updating action values from observed rewards and selecting actions that maximize the learned Q-function.

  • Q-learning is a model-free method for finding an optimal policy in a finite MDP.
  • Its objective is to maximize expected discounted reward, with the optimal state value equal to the maximum action value.
  • The algorithm repeatedly selects an action, observes the next state and reward, and updates the corresponding Q-value.
  • Under repeated exploration of every state-action pair and appropriately decaying learning rates, Q converges to Q* with probability 1.

B. Q-learning and Formal Synthesis

Direct Q-learning cannot solve the STL synthesis problems because optimal actions depend on trajectory history and the objectives lack immediate rewards. Satisfaction and robustness are evaluated over complete horizons rather than standard cumulative reward forms.

  • Optimal action selection can depend on whether relevant events occurred earlier, not solely on the current state.For F[0,T]ψ, the preferred action at the same state may differ near the horizon versus at its beginning.
  • STL satisfaction and robustness are undefined for partial trajectories shorter than the formula horizon T.Thus, an action does not generally produce an immediate reward suitable for ordinary Q-learning updates.
  • The probability-of-satisfaction and expected-robustness objectives therefore do not have Q-learning’s standard reward-sum form.The mismatch follows from both the horizon-wide evaluation and STL’s quantitative semantics.

C. Proposed Approach

The proposed approach augments states with finite trajectory history and transforms STL objectives into immediate-reward approximations. Q-learning then applies to the resulting τ-MDP, with explicit approximation and convergence guarantees plus a β–γ trade-off.

  • State augmentation: The method constructs a τ-MDP whose states encode the current state together with the most recent τ−1 states.Each τ-state represents a τ-horizon path, with shorter initial paths padded by ε.
  • State augmentation: The history length τ is computed from the horizon of the STL subformula, and τ = 1 when the specification has no nested temporal operators.In that case, the τ-MDP coincides with the original MDP.
  • Objective reformulation: The reformulated objectives use τ-state robustness values to express satisfaction and robustness over the mission trajectory.This removes the remaining mission horizon from policy design after trajectory history has been incorporated into the state.
  • Objective reformulation: Log-sum-exp approximates maximum or minimum robustness terms so the objectives can be represented as sums of immediate rewards.Increasing β improves the approximation accuracy, while the transformed rewards support Q-learning.
  • Guarantees: Q-learning applies to the approximate Problems 1A and 2A on the τ-MDP, and its Q-values converge to the optimal Q-function with probability 1.The result assumes a finite MDP and the specified update rule.
  • Guarantees: The approximate policies can differ from the original optima by at most 1/β log(T −τ + 2) in performance.This bound applies to both approximate probability-of-satisfaction and expected-robustness formulations.
  • Guarantees: Choosing γ close to 1 and β arbitrarily large reduces the approximation gap, but larger β increases rewards and can slow Q-learning convergence.The discount-extension result preserves the same design trade-off.

V. SIMULATION RESULTS

The simulations model motion uncertainty probabilistically for a single agent in a discretized environment.

  • Each feasible motion primitive follows the intended blue-arrow direction with probability 0.93 and a red-arrow alternative with probability 0.023.Infeasible actions leave the agent in its current state.
  • Figure 3 depicts the intended action as a blue arrow and motion uncertainty as red arrows.

A. Case Study 1: Reachability

Case Study 1 evaluates reachability of a desired region under an STL specification requiring eventual visitation within a finite interval. The learned policies achieve very high or certain satisfaction probability, while robustness optimization favors deeper visits within the region.

  • Reachability: The experiment starts the agent at s0 = (1.5,1.5) in the environment shown in Figure 4.
  • Reachability: The STL formula requires the agent to eventually visit the desired region within [0,7].The desired region is defined by x > 4∧y > 4.
  • Reachability: After 1700 training episodes, policies π∗ 1A and π∗ 2A were used to generate 1000 trajectories.Each problem required approximately 1 minute of training.
  • Reachability: Φ1 is satisfied with very high probability under π∗ 1A and with probability 1 under π∗ 2A.The expected-robustness policy tends to reach the deepest state in the desired region.

B. Case Study 2: Repeated Satisfiability

Case Study 2 tests repeated visitation of two regions over time. Probability-of-satisfaction and expected-robustness objectives produce different performances because robustness rewards trajectories that nearly satisfy the repeated task.

  • Repeated Satisfiability: The STL formula requires visiting regions A and B within every two-second interval throughout [0,12].Region A and region B are defined by separate rectangular state constraints.
  • Repeated Satisfiability: The case study uses |Σ| = 16 and |Στ| = 6762, with 2000 training episodes and 500 generated trajectories.Training took approximately 6 minutes for each problem.
  • Repeated Satisfiability: The two optimization objectives yield different performances in this repeated-satisfiability case.For nearly satisfying trajectories, probability maximization assigns the same overall reward to slightly and strongly violating τ-states, whereas robustness gives partial credit.
  • Repeated Satisfiability: Figure 5 presents the initial state and sample trajectories generated by π∗ 1A and π∗ 2A.
  • Repeated Satisfiability: Robustness-based Q-learning performs a directed search toward satisfying policies, while probability-based learning effectively searches until it encounters satisfaction.When satisfying policies are rare, probability-based learning may take longer to converge.

VI. CONCLUSIONS AND FUTURE WORK

The paper approximates two STL synthesis objectives so they can be optimized with Q-learning for unknown stochastic MDPs. The simulations demonstrate the approach, and the authors identify complexity reduction and multi-agent extensions as future work.

  • The paper addresses maximizing satisfaction probability and expected robustness degree for STL tasks in MDPs with unknown transition probabilities.
  • The proposed approach remodels the system as a τ-MDP and approximates both objectives as sums of rewards.Each τ-MDP state corresponds to a τ-length trajectory, with τ computed from the STL formula.
  • The resulting policies can be sufficiently close to the original-problem policies when the approximation parameter is selected properly.
  • After the same number of training episodes, expected-robustness maximization performed better than satisfaction-probability maximization in the reported case studies.
  • Future work includes complexity reduction for faster convergence and extension to multi-agent systems.
Loading 1609.07409v1…