Spoken dialog systems present a classic example of planning under uncertainty. In a spoken dialog system, a computer is trying to help a person accomplish something, using spoken language as the communication medium. A key challenge is that speech recognition errors are ubiquitous and impossible to detect reliably, so the state of the conversation can never be known with certainty. Another challenge is that people do not behave deterministically. Despite these challenges, the system must choose actions to make progress to a long term goal. As such, decision theory presents an attractive approach to building spoken dialog systems. Initial work on "toy" dialog systems validated benefits, but also found that straightforward formulations could not scale to real-world problems. Subsequent work by a number of research teams has shown how to scale to industrial-scale systems, how to incorporate high-fidelity user simulations, and how to synthesize commercial development practices with automatic optimization. This talk traces the evolution of this application of planning under uncertainty, comments on progress toward use in industry, and suggests future avenues of research relevant to researchers interested in planning under uncertainty.