If there is an optimal policy, there is a deterministic optimal policy. Here is a sketch of the argument:
Start with an optimal policy within the class of deterministic optimal policies. By the one-deviation-principle, you only have to check whether you can gain by randomizing after a certain history of the process. If you randomize over two actions that do not lead to the same payoff, you could gain by putting more weight on the action with a higher payoff. So all actions will give you the same payoff and you might as well choose a deterministic one. Now a standard result says that in MDPs, such a history dependent strategy can not improve on all Markovian strategies. Therefore, an optimal, deterministic Markovian strategy exist.