Body: <p>Given a discrete, finite Markov Decision Process (MDP) with its usual parameters <span class="math-container">$(S, A, T, R, \gamma)$</span>, it is possible to obtain the optimal policy <span class="math-container">$\pi^{*}$</span> and the optimal value function <span class="math-container">$V^{*}$</span> through one of many planning methods (policy iteration, value iteration or solving a linear program).</p>
  
  <p>I am interested in obtaining a random near-optimal policy <span class="math-container">$\pi$</span>, with the value function associated with the policy given by <span class="math-container">$V^{\pi}$</span>, such that
  <span class="math-container">$$ \epsilon_1 &lt; ||V^{*} - V^{\pi}||_{\infty} &lt; \epsilon_2$$</span></p>
  
  <p>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.</p>
  
  <p>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
  <span class="math-container">$$||V - V^{*}||_{\infty} &lt; \epsilon, \quad \epsilon &gt; 0$$</span>
  and if <span class="math-container">$\pi$</span> is the policy that is greedy with respect to the value function <span class="math-container">$V$</span>, then
  <span class="math-container">$$ ||V^{\pi} - V^{*}||_{\infty} &lt; \frac{2\gamma\epsilon}{1 - \gamma}$$</span>
  So by picking a suitable <span class="math-container">$\epsilon$</span> for the given <span class="math-container">$\gamma$</span>, we can be sure of any upper bound <span class="math-container">$\epsilon_2$</span>. </p>
  
  <p>However, I would also like that the policy <span class="math-container">$\pi$</span> not be "too good", hence the requirement for a lower bound. </p>
  
  <p>Any inputs regarding an efficient solution or reasons for the lack thereof are welcome.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-19T10:02:23.203Z
Comments.Text: 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$.
Comments.UserDisplayName: mikkola
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-22T05:41:59.180Z
Comments.Text: @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)
Comments.UserDisplayName: ijuneja
Tags: <reinforcement-learning><markov-decision-process>
Title: Efficient algorithm to obtain near optimal policies for an MDP
UserDisplayName: ijuneja
ThreadText: # Efficient algorithm to obtain near optimal policies for an MDP
  
  (Asked by: username_0 on 2020-04-03)
  
  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.
  
  **Tags:** reinforcement-learning, markov-decision-process
  > **Comments:**
  > **username_1**: 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$.  
  > **username_0**: @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)  
  
  ---
  
  ## 0 answers
  
  