3
$\begingroup$

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.

$\endgroup$
  • $\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 at 15:54
  • $\begingroup$ @nbro I could but it would destroy the context. $\endgroup$ – DuttaA Mar 6 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 at 16:36
  • $\begingroup$ I will have to downvote this question because it is unclear what you are asking (in the first question). Once you clarify your questions, I will remove my downvote, so I suggest you edit your post to clarify this question. Furthermore, I really suggest that you ask just one question per post. $\endgroup$ – nbro Mar 6 at 16:43
2
$\begingroup$

$\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

$\endgroup$
  • $\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 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 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 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 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 at 10:32
0
$\begingroup$

To understand the difference between policy iteration and value iteration we must go a step backward and focus first on the control problem itself. In the gridworld domain a robot should reach a goal. For doing so, there are two different principle available: Model free control, which is sometimes called policy iteration. The idea is, to test out different behaviors in the state-action space similar to a genetic algorithm. The other option is, to use model based control which is equal to system identification. Here is the idea, that before the robot can make a decision he needs first an understanding of the state space. Model based control is similar to what a chess engine is doing, it has a model of the game and searches in the gametree.

It remains the question open what value iteration is. It is the same as an q-value update. The parameter in the q-matrix are changed and as a result the robot's behavior will become different. But let us make the point. Before it is possible to talk about value iteration vs policy iteration there is a need to determine if a forward model of the domain is available or not. If the robot is able to predict future states of the system and answer what if questions, than a model is used and vice versa. If it is clear, about which kind of control technique we are speaking, it is possible to analyze in detail how a certain policy is working.

$\endgroup$
  • $\begingroup$ You're not really addressing any of the OP's questions. Also, I think it is not necessary to talk about model-free and model-based control to explain the difference between PI and VI, given that both are model-based control algorithms. Anyway, in the context of RL, you should avoid using the term "robot" (because a robot is associated with robotics and a robot in robotics does not always use RL). In RL, we usually refer to what you call robot as the "agent". $\endgroup$ – nbro Mar 6 at 17:05
  • $\begingroup$ An agent is a module in a blackboard system. While a robot is equal to an Artificial Intelligence which can replace a human operator. In some of the weaker papers about Reinforcement Learning, this distinction is not made clear enough. The answer to the problem is to educate the authors and take care of the details. $\endgroup$ – Manuel Rodriguez Mar 6 at 19:24

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.