Batch-iFDD for Representation Expansion in Large MDPs
Alborz Geramifard, Thomas Walsh, Nicholas Roy, Jonathan How
Matching pursuit (MP) methods are a promising class of feature construction algorithms for value function approximation. Yet existing MP methods require creating a pool of potential features, mandating expert knowledge or enumeration of a large feature pool, both of which hinder scalability. This paper introduces batch incremental feature dependency discovery (Batch-iFDD) as an MP method that inherits a provable convergence property. Additionally, Batch-iFDD does not require a large pool of features, leading to lower computational complexity. Empirical policy evaluation results across three domains with up to one million states highlight the scalability of Batch-iFDD over the previous state of the art MP algorithm.
PDF Link: /papers/13/p242-geramifard.pdf
AUTHOR = "Alborz Geramifard
and Thomas Walsh and Nicholas Roy and Jonathan How",
TITLE = "Batch-iFDD for Representation Expansion in Large MDPs",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "242--251"