Desirable properties of the infinite histories of a finite-state Markov decision process are specified in terms of a finite number of events represented as omega-regular sets. An infinite history of the process produces a reward which depends on the properties it satisfies. The authors investigate the existence of optimal policies and provide algorithms for the construction of such policies.