Research map / Reinforcement learning / MDPs and planning

Omega-Regular Decision Processes

AAAI 2024 · Reinforcement learning › MDPs and planning · approach: Robust MDP policy gradient · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces omega-regular decision processes, extending regular decision processes with omega-regular lookahead promises, and reduces optimal discounted-reward learning for them to lexicographic optimization over finite MDPs via a good-for-MDP rank-based complementation of UCAs.

Problem

Non-Markovian decision processes whose rewards and transitions depend on regular past (lookback) and on future behavior promises; optimal discounted reward computation and learning for such processes, which RDPs alone cannot express beyond finite MDPs.

Approach

Extends RDPs with omega-regular lookaheads (promises about future behavior, payoff bottom if unmet) and reduces them to finite MDPs by building a good-for-MDP NBA that checks all collected promises, using rank-based complementation of UCAs.

Key results

• Complementation succeeded in 99.47% of 10000 random formulas under a 600 s timeout.
• Mean complement size was 48,367 states before pruning, reduced to a mean of 7.03 states after all optimizations (lumpa).
• The grid-world case study with the lexicographic RL algorithm took about 20 minutes on an Intel i7-8750H.

Measured effects reported in the paper

Surprising findings

• Strongly limit-deterministic NBAs need not be good-for-MDP, shown by a counterexample.
• Some ODPs have no optimal strategy: the optimal Büchi-discounted value can be approached but no finite or infinite memory strategy attains it.

Limitations

• Complexity is EXPTIME-hard in the size of the UCA and 2EXPTIME-hard for LTL, so the reduction can blow up.
• Experiments are small: random formulas and one grid-world case study.

Experimental setup

Datasets: randomly generated LTL formulas (Spot randltl, 10000 formulas, 4 atomic propositions)

Benchmarks: randomly generated LTL formulas converted with ltl2tgba

Metrics: number of automaton states after complementation and optimiz runtime in seconds success rate within timeout

Builds on: regular decision processes reward machines good-for-MDP automata rank-based complementation lexicographic RL over omega-regular and discounted objectives

Closest papers by meaning

• Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.88)
• A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · similarity 0.87)
• Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs (NeurIPS 2025 · similarity 0.86)
• Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards (NeurIPS 2024 · similarity 0.86)
• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.86)
• Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · similarity 0.86)