# Efficient algorithm to obtain near optimal policies for an MDP

Given a discrete, finite Markov Decision Process (MDP) with its usual parameters $$(S, A, T, R, \gamma)$$, it is possible to obtain the optimal policy $$\pi^{*}$$ and the optimal value function $$V^{*}$$ through one of many planning methods (policy iteration, value iteration or solving a linear program).

I am interested in obtaining a random near-optimal policy $$\pi$$, with the value function associated with the policy given by $$V^{\pi}$$, such that $$\epsilon_1 < ||V^{*} - V^{\pi}||_{\infty} < \epsilon_2$$

I wish to know an efficient way of achieving this goal. A possible approach is to generate random policies and then to use the given MDP model to evaluate these policies and verify that they satisfy the criteria.

If only an upper bound were needed, the idea that near optimal value functions induce near optimal policies could be used, that is, we can show that, if $$||V - V^{*}||_{\infty} < \epsilon, \quad \epsilon > 0$$ and if $$\pi$$ is the policy that is greedy with respect to the value function $$V$$, then $$||V^{\pi} - V^{*}||_{\infty} < \frac{2\gamma\epsilon}{1 - \gamma}$$ So by picking a suitable $$\epsilon$$ for the given $$\gamma$$, we can be sure of any upper bound $$\epsilon_2$$.

However, I would also like that the policy $$\pi$$ not be "too good", hence the requirement for a lower bound.

Any inputs regarding an efficient solution or reasons for the lack thereof are welcome.

• Seems like this will not be possible in the general case. Consider a MDP with a single action. It is not possible find a policy that does worse than taking that one action always, so there is no solution for your query any $\epsilon_1 > 0$. Mar 19 at 10:02
• @mikkola thanks for your comment. It was a nice way of seeing the issue here. From a practical implementation point of view, I ran policy iteration on the inverse MDP (R replaced by -R) to obtain a policy that will be "at least as bad" instead of the "at least as good" set procedure mentioned above (A paper by Singh. et al) Mar 22 at 5:41