# Learning Optimal Strategies for Temporal Tasks in Stochastic Games

arXiv: https://arxiv.org/abs/2102.04307 · HTML: https://mlsanity.com/paper/2102.04307/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 85 references that are in the map.
- First posted on arXiv 8 Feb 2021.

## Builds on (most cited first, 23 of 23)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research](https://mlsanity.com/paper/1802.09464/) (2018)
- [Controlling Overestimation Bias with Truncated Mixture of Continuous Distributional Quantile Critics](https://mlsanity.com/paper/2005.04269/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Reinforcement Learning with Probabilistic Guarantees for Autonomous Driving](https://mlsanity.com/paper/1904.07189/) (2019)
- [Reinforcement Learning of Control Policy for Linear Temporal Logic Specifications Using Limit-Deterministic Generalized B"uchi Automata](https://mlsanity.com/paper/2001.04669/) (2020)
- [Model-Free Reinforcement Learning for Stochastic Games with Linear Temporal Logic Objectives](https://mlsanity.com/paper/2010.01050/) (2020)
- [Symbolic control of stochastic systems via approximately bisimilar finite abstractions](https://mlsanity.com/paper/1302.3868/) (2013)
- [From LTL and Limit-Deterministic B"uchi Automata to Deterministic Parity Automata](https://mlsanity.com/paper/1701.06103/) (2017)
- [Temporal Logic Control for Stochastic Linear Systems using Abstraction Refinement of Probabilistic Games](https://mlsanity.com/paper/1410.5387/) (2014)
- [Secure Planning Against Stealthy Attacks via Model-Free Reinforcement Learning](https://mlsanity.com/paper/2011.01882/) (2020)
- [Formal Methods for Adaptive Control of Dynamical Systems](https://mlsanity.com/paper/1703.07704/) (2017)
- [Security-Aware Synthesis Using Delayed-Action Games](https://mlsanity.com/paper/1902.04618/) (2019)
- [Optimal Secure Control with Linear Temporal Logic Constraints](https://mlsanity.com/paper/1907.07556/) (2019)

## Built on by (most cited first, 3 of 3)

- [DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL](https://mlsanity.com/paper/2410.04631/) (2024)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [Reward Machines for Signal Temporal Logic](https://mlsanity.com/paper/2608.13625/) (2026)

## Abstract (arXiv)

Synthesis from linear temporal logic (LTL) specifications provides assured controllers for systems operating in stochastic and potentially adversarial environments. Automatic synthesis tools, however, require a model of the environment to construct controllers. In this work, we introduce a model-free reinforcement learning (RL) approach to derive controllers from given LTL specifications even when the environment is completely unknown. We model the problem as a stochastic game (SG) between the controller and the adversarial environment; we then learn optimal control strategies that maximize the probability of satisfying the LTL specifications against the worst-case environment behavior. We first construct a product game using the deterministic parity automaton (DPA) translated from the given LTL specification. By deriving distinct rewards and discount factors from the acceptance condition of the DPA, we reduce the maximization of the worst-case probability of satisfying the LTL specification into the maximization of a discounted reward objective in the product game; this enables the use of model-free RL algorithms to learn an optimal controller strategy. To deal with the common scalability problems when the number of sets defining the acceptance condition of the DPA (usually referred as colors), is large, we propose a lazy color generation method where distinct rewards and discount factors are utilized only when needed, and an approximate method where the controller eventually focuses on only one color. In several case studies, we show that our approach is scalable to a wide range of LTL formulas, significantly outperforming existing methods for learning controllers from LTL specifications in SGs.