For a MDP (Markov Decision Process) is there an easy way to convert a non-deterministic optimal policy into a deterministic optimal policy?
The trivial way will take $O(|\mathcal{A}|^{|\mathcal{S}|}$) iterations and hence should be ignored. Here $\mathcal{A}$ denotes the set of actions, and $\mathcal{S}$ the set of states
My guess is you are talking about finite MDPs. There deterministic strategies are optimal, and any deterministic optimal strategy satisfies $$ \phi(x) \in \operatorname{Argmax}_{a\in A(x)} Q^*(x,a). $$ Similarly, any non-deterministic strategy must satisfy $$ \pi(\operatorname{Argmax}_{a\in A(x)} Q^*(x,a)|x) = 1 $$ Thus, if you have some optimal $\pi$, then you can construct an optimal $\phi$ by iterating over $x\in X$, and picking $\phi(x)$ to be any $a$ with a property $\pi(a|x) > 0$. Depending on how $\pi$ was stored, your speed varies. For example, if $\pi$ was stored as a sparse matrix of a list-type, picking the first element for every $x$ suffices - that would be linear in $\mathrm{card}(X)$.
