In this talk I will describe recent progress in developing problem solving architectures that learn from interactions with external environments. Previous work in planning and problem solving has often ignored the special constraints and uncertainties that arise from interacting with a real environment. In addition, learning was seen as an add-on that could be ignored until the planning system was complete. Similarly, most learning work has been carried out in simulated domains, or at least in domains where interaction with an environment is mininized. Recently, several systems have been developed that attempt to integrate learning and problem solving while interacting with an external environment.