Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach
The key to reconciling the polynomial-time intractability of many machine
learning tasks in the worst case with the surprising solvability of these tasks
by heuristic algorithms in practice seems to be exploiting restrictions on
real-world data sets. One approach to investigating such restrictions is to
analyze why heuristics perform well under restrictions. A complementary
approach would be to systematically determine under which sets of restrictions
efficient and reliable machine learning algorithms do and do not exist. In this
paper, we show how such a systematic exploration of algorithmic options can be
done using parameterized complexity analysis, As an illustrative example, we
give the first parameterized complexity analysis of batch and incremental
policy inference under Learning from Demonstration (LfD). Relative to a basic
model of LfD, we show that none of our problems can be solved efficiently
either in general or relative to a number of (often simultaneous) restrictions
on environments, demonstrations, and policies. We also give the first known
restrictions under which efficient solvability is possible and discuss the
implications of our solvability and unsolvability results for both our basic
model of LfD and more complex models of LfD used in practice.