TY - GEN
T1 - A note on the representational incompatibility of function approximation and factored dynamics
AU - Allender, Eric
AU - Arora, Sanjeev
AU - Kearns, Michael
AU - Moore, Cristopher
AU - Russell, Alexander
PY - 2003/1/1
Y1 - 2003/1/1
N2 - 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 & 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.
AB - 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 & 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.
UR - http://www.scopus.com/inward/record.url?scp=84898975623&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84898975623&partnerID=8YFLogxK
M3 - Conference contribution
SN - 0262025507
SN - 9780262025508
T3 - Advances in Neural Information Processing Systems
BT - Advances in Neural Information Processing Systems 15 - Proceedings of the 2002 Conference, NIPS 2002
PB - Neural information processing systems foundation
T2 - 16th Annual Neural Information Processing Systems Conference, NIPS 2002
Y2 - 9 December 2002 through 14 December 2002
ER -