320
E. M. Hahn et al.
5.2 GFM Automata and Reinforcement Learning
SLDBAs have been used in [12] for model-free reinforcement learning of ω-regular
objectives. While the B¨ uchi acceptance condition allows for a faithful translation of
the objective to a scalar reward, the agent has to learn how to control the automaton’s
nondeterministic choices; that is, the agent has to learn when the SLDBA should cross
from the initial component to the accepting component to produce a successful run of a
behavior that satisfies the given objective.
Any GFM automaton with a B¨ uchi acceptance condition can be used instead of
an SLDBA in the approach of [12]. While in many cases SLDBAs work well, GFM
automata that are not limit-deterministic may provide a significant advantage.
Early during training, the agent relies on uniform random choices to discover policies that lead to successful episodes. This includes randomly resolving the automaton
nondeterminism. If random choices are unlikely to produce successful runs of the automaton in case of behaviors that should be accepted, learning is hampered because
good behaviors are not rewarded. Therefore, GFM automata that are more likely to
accept under random choices will result in the agent learning more quickly. We have
found the following properties of GFM automata to affect the agent’s learning ability.
Low branching degree. A low branching degree presents the agent with fewer alternatives, reducing the expected number of trials before the agent finds a good combination
of choices. Consider an MDP and an automaton that require a specific sequence of k
nondeterministic choices in order for the automaton to accept. If at each choice there
are b equiprobable options, the correct sequence is obtained with probability b
−k .
Cautiousness. An automaton that enables fewer nondeterministic choices for the same
finite input word gives the agent fewer chances to choose wrong. The slim automata
construction has the interesting property of “collecting hints of acceptance” before a
nondeterministic choice is enabled because S
has to be nonempty for a γ 2,1 transition
to be present and that requires going through at least one accepting transition.
Forgiveness. Mistakes made in resolving nondeterminism may be irrecoverable. This
is often true of SLDBAs meant for model checking, in which jumps are made to select
a subformula to be eventually satisfied. However, general GFM automata, thanks also
to their less constrained structure, may be constructed to “forgive mistakes” by giving
more chances of picking a successful run.
Figure 5 compares a typical SLDBA to an automaton that is not limit-deterministic
and is not produced by the breakpoint construction, but is proved GFM by AEC simulation. This latter automaton has a nondeterministic choice in state q 0 on letter x ∧ ¬y
that can be made an unbounded number of times. The agent may choose q 1 repeatedly
even if eventually F G x is false and G F y is true. With the SLDBA, on the other hand,
there is no room for error.
A Case Study. We compared the effectiveness in learning to control a cart-pole model
of three automata for the property
(F G x) ∨ (G F y)
∧ G safe. The safety component
of the objective is to keep the pole balanced and the cart on the track. The left two thirds
of the track alternate between x and y at each step. The right third is always labeled y,
but in order to reach it, the cart has to cross a barrier, with probability 1/3 of failing.
The three automata are an SLDBA (4 states), a slim automaton (8 states), and a
handcrafted forgiving automaton (4 states) similar to the one of Fig. 5.
E. M. Hahn et al.
5.2 GFM Automata and Reinforcement Learning
SLDBAs have been used in [12] for model-free reinforcement learning of ω-regular
objectives. While the B¨ uchi acceptance condition allows for a faithful translation of
the objective to a scalar reward, the agent has to learn how to control the automaton’s
nondeterministic choices; that is, the agent has to learn when the SLDBA should cross
from the initial component to the accepting component to produce a successful run of a
behavior that satisfies the given objective.
Any GFM automaton with a B¨ uchi acceptance condition can be used instead of
an SLDBA in the approach of [12]. While in many cases SLDBAs work well, GFM
automata that are not limit-deterministic may provide a significant advantage.
Early during training, the agent relies on uniform random choices to discover policies that lead to successful episodes. This includes randomly resolving the automaton
nondeterminism. If random choices are unlikely to produce successful runs of the automaton in case of behaviors that should be accepted, learning is hampered because
good behaviors are not rewarded. Therefore, GFM automata that are more likely to
accept under random choices will result in the agent learning more quickly. We have
found the following properties of GFM automata to affect the agent’s learning ability.
Low branching degree. A low branching degree presents the agent with fewer alternatives, reducing the expected number of trials before the agent finds a good combination
of choices. Consider an MDP and an automaton that require a specific sequence of k
nondeterministic choices in order for the automaton to accept. If at each choice there
are b equiprobable options, the correct sequence is obtained with probability b
−k .
Cautiousness. An automaton that enables fewer nondeterministic choices for the same
finite input word gives the agent fewer chances to choose wrong. The slim automata
construction has the interesting property of “collecting hints of acceptance” before a
nondeterministic choice is enabled because S
has to be nonempty for a γ 2,1 transition
to be present and that requires going through at least one accepting transition.
Forgiveness. Mistakes made in resolving nondeterminism may be irrecoverable. This
is often true of SLDBAs meant for model checking, in which jumps are made to select
a subformula to be eventually satisfied. However, general GFM automata, thanks also
to their less constrained structure, may be constructed to “forgive mistakes” by giving
more chances of picking a successful run.
Figure 5 compares a typical SLDBA to an automaton that is not limit-deterministic
and is not produced by the breakpoint construction, but is proved GFM by AEC simulation. This latter automaton has a nondeterministic choice in state q 0 on letter x ∧ ¬y
that can be made an unbounded number of times. The agent may choose q 1 repeatedly
even if eventually F G x is false and G F y is true. With the SLDBA, on the other hand,
there is no room for error.
A Case Study. We compared the effectiveness in learning to control a cart-pole model
of three automata for the property
(F G x) ∨ (G F y)
∧ G safe. The safety component
of the objective is to keep the pole balanced and the cart on the track. The left two thirds
of the track alternate between x and y at each step. The right third is always labeled y,
but in order to reach it, the cart has to cross a barrier, with probability 1/3 of failing.
The three automata are an SLDBA (4 states), a slim automaton (8 states), and a
handcrafted forgiving automaton (4 states) similar to the one of Fig. 5.