Learning Reward Machines through Preference Queries over Sequences
Eric Hsiung Joydeep Biswas Swarat Chaudhuri
Reward machines have shown great promise at capturing non-Markovian reward
functions for learning tasks that involve complex action sequencing. However,
no algorithm currently exists for learning reward machines with realistic weak
feedback in the form of preferences. We contribute REMAP, a novel algorithm for
learning reward machines from preferences, with correctness and termination
guarantees. REMAP introduces preference queries in place of membership queries
in the L* algorithm, and leverages a symbolic observation table along with
unification and constraint solving to narrow the hypothesis reward machine
search space. In addition to the proofs of correctness and termination for
REMAP, we present empirical evidence measuring correctness: how frequently the
resulting reward machine is isomorphic under a consistent yet inexact teacher,
and the regret between the ground truth and learned reward machines.