Stochastic optimal control theory is a principled approach to compute optimal actions with delayed rewards. The use of this approach in AI and machine learning has been limited due to the computational intractabilities. In this talk, I introduce a class of control problems where the intractabilities appear as the computation of a partition sum, as in a statistical mechanical system. This opens the possibility to study phase transitions and to apply exisiting approximation methods such as BP and the variational method to optimal control theory. The talk gives a gentle introduction into control theory and illustrates these new phenomena with a number of examples.