The question already has some answer. But I am still finding it quite unclear (also does $\pi(s)$ here mean $q(s,a)$ ?):

enter image description here

The few things I do not understand are:

  • Why the difference between 2 iterations if we are acting greedily in each of them? As per many sources 'Value Iteration' does not have an explicit policy, but here we can see the policy is to act greedily to current $v(s)$
  • What exactly does Policy Improvement mean? Are we acting greedily only at a particular state at a particular iteration OR once we act greedily on a particular state we keep on acting greedily on that state and other states are added iteratively until in all states we act greedily?
  • We can intuitively understand that acting greedily w.r.t $v(s)$ will lead to $v^*(s)$ eventually, but does using Policy Iteration eventually lead to $v^*(s)$?

NOTE: I have been thinking of all the algorithms in context of Gridworld, but if you think there is a better example to illustrate the difference you are welcome.

  • $\begingroup$ What is $q(s)$? Maybe you meant $q(s, a)$? Furthermore, by the "2 iterations" you mean the iterations in both inner boxes? You're asking too many question in the same post, IMHO. I would split these questions in separate posts. $\endgroup$ – nbro Mar 6 '19 at 15:54
  • $\begingroup$ @nbro I could but it would destroy the context. $\endgroup$ – DuttaA Mar 6 '19 at 15:59
  • $\begingroup$ You can add the context to each of your different posts. To make each question more useful (because some people might just have the first or the second doubt, e.g.), then you should split these questions. If there is context you need to add to each of the questions, you should do it. I will answer just to your first question here. $\endgroup$ – nbro Mar 6 '19 at 16:36

$\pi(s)$ does not mean $q(s,a)$ here. $\pi(s)$ is a policy that represents probability distribution over action space for a specific state. $q(s,a)$ is a state-action pair value function that tells us how much reward do we expect to get by taking action $a$ in state $s$ onwards.

For the value iteration on the right side with this update formula:

$v(s) \leftarrow \max_\limits{a} \sum_\limits{s'}p(s'\mid s, a)[r(s, a, s') + \gamma v(s')]$

we have an implicit greedy deterministic policy that updates value of state $s$ based on the greedy action that gives us the biggest expected return. When the value iteration converges to its values based on greedy behaviour after $n$ iterations we can get the explicit optimal policy with:

$\pi(s) = \arg \max_\limits{a} \sum_\limits{s'} p(s'\mid s, a)[r(s, a, s') + \gamma v(s')]$

here we are basically saying that the action that has highest expected reward for state $s$ will have probability of 1, and all other actions in action space will have probability of 0

For the policy evaluation on the left side with this update formula:

$v(s) \leftarrow \sum_\limits{s'}p(s'\mid s, \pi(s))[r(s, \pi(s), s') + \gamma v(s')]$

we have an explicit policy $\pi$ that is not greedy in general case in the beginning. That policy is usually randomly initialized so the actions that it takes will not be greedy, it means we can start with policy that takes some pretty bad actions. It also does not need to be deterministic but I guess in this case it is. Here we are updating value of state $s$ according to the current policy $\pi$.
After policy evaluation step ran for $n$ iterations we start with the policy improvement step:

$\pi(s) = \arg \max_\limits{a} \sum_\limits{s'} p(s'\mid s, a)[r(s, a, s') + \gamma v(s')]$

here we are greedily updating our policy based on the values of states that we got through policy evaluation step. It is guaranteed that our policy will improve but it is not guaranteed that our policy will be optimal after only one policy improvement step. After improvement step we do the evaluation step for new improved policy and after that we again do the improvement step and so on until we converge to the optimal policy

| improve this answer | |
  • $\begingroup$ Using mathematical formulas is a good starting point for explaining reinforcement learning. It makes clear, that the subject is an engineering discipline and allows the calculate the reward of a policy in absolute numbers. $\endgroup$ – Manuel Rodriguez Mar 6 '19 at 20:33
  • $\begingroup$ Just a few questions...1.) Is.policy improvement term correct..It should be better to call it value improvement owing to what's going on and 2.) When we cat greedily do we act w.r.t all states or only a single state in a single iteration? $\endgroup$ – DuttaA Mar 7 '19 at 2:46
  • $\begingroup$ policy improvement step uses argmax operator to get the action in the action space that has the highest value for a specific state $s$. It would be more correct to have $\pi(a\mid s)$ that has probability for each action in action space in state $s$ but since the policy is greedy, all actions but one will have probability of 0 so we can simply remember that greedy action instead of struggling with remembering probabilities for each action. So policy improvement is correct because we are not improving values but rather remembering actions that have highest value, that is improving policy. $\endgroup$ – Brale Mar 7 '19 at 9:42
  • $\begingroup$ for the second question, in this case, we are traversing over every state $s$ in state space $S$, but we are acting greedily in each that specific state $s$ separately. $\endgroup$ – Brale Mar 7 '19 at 9:44
  • $\begingroup$ Hi! Another doubt, you said 'here we are greedily updating our policy based on the values of states that we got through policy evaluation step. It is guaranteed that our policy will improve but it is not guaranteed that our policy will be optimal after only one policy improvement step.' Does this policy improvement schem fix what is the action we will take? example in Gridworld: Say going right has highest reward so we will go right always (makes probability 1) or does it fix the type of action we will take (greedy ) does not matter if the direction changes (in policy eval step) as long as $\endgroup$ – DuttaA May 12 '19 at 10:32

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.