# Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 16 Mar 2023.

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

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [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)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Mungojerrie: Reinforcement Learning of Linear-Time Objectives](https://mlsanity.com/paper/2106.09161/) (2021)
- [Learning-based Bounded Synthesis for Semi-MDPs with LTL Specifications](https://mlsanity.com/paper/2204.04383/) (2022)

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

- [About Time: Model-free Reinforcement Learning with Timed Reward Machines](https://mlsanity.com/paper/2512.17637/) (2025)

## Abstract (arXiv)

Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time and stochastic environments. When the stochastic evolution of the environment is only available via sampling, model-free reinforcement learning (RL) is the algorithm-of-choice to compute optimal decision sequence. RL, on the other hand, requires the learning objective to be encoded as scalar reward signals. Since doing such translations manually is both tedious and error-prone, a number of techniques have been proposed to translate high-level objectives (expressed in logic or automata formalism) to scalar rewards for discrete-time Markov decision processes (MDPs). Unfortunately, no automatic translation exists for CTMDPs. We consider CTMDP environments against the learning objectives expressed as omega-regular languages. Omega-regular languages generalize regular languages to infinite-horizon specifications and can express properties given in popular linear-time logic LTL. To accommodate the dense-time nature of CTMDPs, we consider two different semantics of omega-regular objectives: 1) satisfaction semantics where the goal of the learner is to maximize the probability of spending positive time in the good states, and 2) expectation semantics where the goal of the learner is to optimize the long-run expected average time spent in the ``good states" of the automaton. We present an approach enabling correct translation to scalar reward signals that can be readily used by off-the-shelf RL algorithms for CTMDPs. We demonstrate the effectiveness of the proposed algorithms by evaluating it on some popular CTMDP benchmarks with omega-regular objectives.