4
$\begingroup$

I am trying to self learn reinforcement learning. At the moment I am focusing on policy and value iteration, and I am finding several problems and doubts.

One of the main doubts is given by the fact that I can't find many diversified examples on how to implement these on python, instead I find always only the classical grid world example.

So, my doubt is: Are policy and value iteration used only in grid world like scenarios, or can be used also in other contexts?

$\endgroup$
2
$\begingroup$

Policy and value iteration both require you to, for each possible transition and each corresponding possible reward at each state, compute a statistic of $r + \gamma V(s')$. In order for this to be tractable, you need for there to be at most finitely many states, actions, possible rewards, and possible transitions at each state. You also need to know the transition model. This is the case in gridworld.

Gridworld is not the only example of an MDP that can be solved with policy or value iteration, but all other examples must have finite (and small enough) state and action spaces. For example, take any MDP with a known model and bounded state and action spaces of fairly low dimension. Then you can approximate the state and action spaces with a finite number of bins, each corresponding to its own " discretized state/action". With smooth enough dynamics and enough bins, you'll be able to solve the MDP with policy/value iteration on the discretized spaces.

In many interesting RL problems though,

  1. You don't know the transition model, and/or
  2. The state space, action space, and/or reward space are too large

In these cases you wouldn't be able to compute the value function exactly, so you can't really do policy/value iteration. However, in most value based RL algorithms, the policy evaluation / policy improvement steps are approximated using sample transitions and function approximators.

$\endgroup$
2
  • $\begingroup$ Sorry, just one comment. Suppose that I am in a scenario in which I want to use value iteration, but I don't have a final state to reach. I would like to have a reward equal to zero if the agent remains in the initial state and a reward of -1 if it moves. I want to find the best state. Can I solve this with value iteration? Thanks. $\endgroup$
    – dcr
    Jun 16 at 9:07
  • $\begingroup$ You should be able to solve that with value iteration if the state and action spaces are finite or can be discretized. $\endgroup$
    – harwiltz
    Jun 16 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.