@inproceedings{1a5c64bb7bb94f8dac13db3dfa4df2f6,
title = "A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics",
abstract = "We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed family of factored MDPs with linear rewards whose optimal policies and value functions simply cannot be represented succinctly in any standard parametric form. Previous hardness results indicated that computing good policies from the MDP parameters was difficult, but left open the possibility of succinct function approximation for any fixed factored MDP. Our result applies even to policies which yield a polynomially poor approximation to the optimal value, and highlights interesting connections with the complexity class of Arthur-Merlin games.",
author = "Eric Allender and Sanjeev Arora and Michael Kearns and Cristopher Moore and Alexander Russell",
note = "Publisher Copyright: {\textcopyright} NIPS 2002: Proceedings of the 15th International Conference on Neural Information Processing Systems. All rights reserved.; 15th International Conference on Neural Information Processing Systems, NIPS 2002 ; Conference date: 09-12-2002 Through 14-12-2002",
year = "2002",
language = "English (US)",
series = "NIPS 2002: Proceedings of the 15th International Conference on Neural Information Processing Systems",
publisher = "MIT Press Journals",
pages = "431--437",
editor = "Suzanna Becker and Sebastian Thrun and Klaus Obermayer",
booktitle = "NIPS 2002",
address = "United States",
}