The overall objective of this research is to make it possible to build machine learning systems that robustly improve their planning performance with experience in complex real-world domains. The current machine learning techniques are not adequate for this purpose because their language of representation is not expressive enough to capture the knowledge needed to be effective in these domains. This work will study the relationship between the language of representation of the learned knowledge and the computational tradeoffs involved in learning and planning in that language. We also propose to enhance the capabilities of current techniques by developing learning and planning methods for more expressive representations.