Omega-Regular Decision Processes

Authors

  • Ernst Moritz Hahn University of Twente
  • Mateo Perez University of Colorado Boulder
  • Sven Schewe University of Liverpool
  • Fabio Somenzi University of Colorado Boulder
  • Ashutosh Trivedi University of Colorado Boulder
  • Dominik Wojtczak University of Liverpool

DOI:

https://doi.org/10.1609/aaai.v38i19.30105

Keywords:

General

Abstract

Regular decision processes (RDPs) are a subclass of non-Markovian decision processes where the transition and reward functions are guarded by some regular property of the past (a lookback). While RDPs enable intuitive and succinct representation of non-Markovian decision processes, their expressive power coincides with finite-state Markov decision processes (MDPs). We introduce omega-regular decision processes (ODPs) where the non-Markovian aspect of the transition and reward functions are extended to an omega-regular lookahead over the system evolution. Semantically, these lookaheads can be considered as promises made by the decision maker or the learning agent about her future behavior. In particular, we assume that, if the promised lookaheads are not met, then the payoff to the decision maker is falsum (least desirable payoff), overriding any rewards collected by the decision maker. We enable optimization and learning for ODPs under the discounted-reward objective by reducing them to lexicographic optimization and learning over finite MDPs. We present experimental results demonstrating the effectiveness of the proposed reduction.
AAAI-24 / IAAI-24 / EAAI-24 Proceedings Cover

Downloads

Published

2024-03-24

How to Cite

Hahn, E. M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., & Wojtczak, D. (2024). Omega-Regular Decision Processes. Proceedings of the AAAI Conference on Artificial Intelligence, 38(19), 21125-21133. https://doi.org/10.1609/aaai.v38i19.30105

Issue

Vol. 38 No. 19: AAAI-24 Special Track Safe, Robust and Responsible AI Track

Section

AAAI Technical Track on Safe, Robust and Responsible AI Track