When omega-regular objectives were first proposed in model-free reinforcement
learning (RL) for controlling MDPs, deterministic Rabin automata were used in
an attempt to provide a direct translation from their transitions to scalar
values. While these translations failed, it has turned out that it is possible
to repair them by using good-for-MDPs (GFM) Büchi automata instead. These are
nondeterministic Büchi automata with a restricted type of nondeterminism,
albeit not as restricted as in good-for-games automata. Indeed, deterministic
Rabin automata have a pretty straightforward translation to such GFM automata,
which is bi-linear in the number of states and pairs. Interestingly, the same
cannot be said for deterministic Streett automata: a translation to
nondeterministic Rabin or Büchi automata comes at an exponential cost, even
without requiring the target automaton to be good-for-MDPs. Do we have to pay
more than that to obtain a good-for-MDP automaton? The surprising answer is
that we have to pay significantly less when we instead expand the good-for-MDP
property to alternating automata: like the nondeterministic GFM automata
obtained from deterministic Rabin automata, the alternating good-for-MDP
automata we produce from deterministic Streett automata are bi-linear in the
the size of the deterministic automaton and its index, and can therefore be
exponentially more succinct than minimal nondeterministic Büchi automata.

本研究发现，当使用好的 MDP Buchi 自动机来代替确定性 Rabin 自动机时，可以更好地将 omega-regular 目标使用于模型无关的强化学习中，并且使用 Streett 自动机所得到的交替好的 MDP 自动机，可以比最小的非确定性 Buchi 自动机更加简洁。