3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ Can't you just follow a greedy policy in this case? AFAIK, optimal non-deterministic policy is any probability measure on maximal set of the value function, so picking just any point there would suffice. $\endgroup$
    – SBF
    Commented Apr 21, 2016 at 16:01
  • $\begingroup$ @Ilya Greedy policy updation takes exponential number of iterations(as above)worst case. Can you please explain the words: " so picking just any point there would suffice" to get a deterministic policy ? $\endgroup$
    – aroyc
    Commented Apr 21, 2016 at 18:58

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .