Answers.Body: <p>It seems to me that you're thinking about the parameters <em>a</em> and <em>b</em> as being characteristic of the agent that's moving in the environment (therefore determining the final policy), but they are actually a characteristic of the environment.</p>
  <p>Think of a frozen lake. You want to pass the lake but there is a hole five meters in front of you. Let's say you have boots with a rubber sole, so there is no risk to slip while walking (i.e. all transition probabilities =1). What is the optimal policy? Simply moving forward till the hole, goes around it and then forward again. But what if you were wearing wooden clogs instead? Now if you walk forward there is the risk to not be able to stop when you want to (i.e. when you decide to move forward of one step you might fail and keep going forward for several steps, with probability <em>a</em>). How many steps would you wait before moving to the left or to the right to avoid risking to fall into the hole? The optimal policy is obviously different in this second scenario. Think about it, I will not answer in detail about how the parameters affect the final policy because stack exchange is not meant for homework.</p>
  <p>Also, an arbitrary policy is necessary simply because in value iteration you first update the values and only when they converge you infer from then the optimal policy. So you need some arbitrary prior belief about the environment to start update the values.</p>
  <h1>Edit</h1>
  <p>So here's a quick visualisation of the impact of different transition probabilities (the parameters <em>a</em> and <em>b</em> in your assignment) on the optimal policy. I used a different grid to make it easier and more explicit (i.e. you don't even need to calculate the values to see the optimal policy).</p>
  <p>As you can see in the picture below, there are some terminal states in the third column and a goal state which gives a huge reward on top of it. From the starting point on the bottom we want to reach the goal state.</p>
  <p><a href="https://i.sstatic.net/CswSv.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CswSv.jpg" alt="enter image description here" /></a></p>
  <p>We have two cases:</p>
  <blockquote>
  <p><strong>Non stochastic environment</strong></p>
  </blockquote>
  <p>On the left we have the case in which all transition probabilities are 1. In this case the optimal policy is simply going forward till the second row, where the goal state is located, and then move right or left to reach it. The terminal states are not scary at all, in this case we could consider them as walls that we can't cross, but the optimal policy do not reflect any risk of falling in them. This is precisely because the transition probabilities are all 1.</p>
  <blockquote>
  <p><strong>Stochastic environment</strong></p>
  </blockquote>
  <p>On the right we have a different situation. In this case only 3 action have a transition probability of 1: going south, east or west. The transition probability for nord is 0.2 meaning that 80% of the time we will slip and go east instead (I wrote right in the picture meaning east, my bad). What is the impact of this simple change in the environment?</p>
  <p>This time the second column become really dangerous, because if we try to go nord and fail we will end on a terminal state. On the other hand, if we choose another action we will end on a legitimate state, without any risk because the other transition probabilities are 1! Therefore the agent learn that on the left side of the grid the best strategy is to go down and circumnavigate the terminal states from the right, because only in the fourth column we can move north without risk, in fact in those cells even if we try go north and fail we would just hit a wall and we could try again going north the next turn till we will eventually succeed.</p>
  <p>Hope this make sense!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:35:57.497Z
Answers.Text: Thank you for the answer but I still have some doubts like why is my problem similar to the second case of frozen lake you talked about? In my problem, if the agent in state $s$ takes an action $a$ to reach state $s'$, isn't the transition probability simply equal to one/zero? I thought the probabilities given were actually $\pi(a|s)$, which gives the probability of a particular action being chosen when our agent is in a state $s$. And while applying the value iteration update rule, we don't require these probabilities, $$V_{k+1}(s) \leftarrow max_a \sum_{s',r}p(s',r|s,a)[r+\gamma V_k(s')]$$
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:01:15.520Z
Answers.Text: @Carrick From the text I would say that the transition probabilities are (N,S,W,E) = (0.2,0.3,a,b), or at least I don't see any other possible interpretation. So you have to reason in terms of a stochastic environment, and therefore the frozen lake, which is a classic example used to explain stochastic grid world (plenty of many others if you google it, I suggest particularly [this one](https://www.cis.upenn.edu/~cis519/fall2015/lectures/14_ReinforcementLearning.pdf).
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:01:43.240Z
Answers.Text: Also the transition probabilities in the formula are: p(s',r | s,a) i.e. probability of getting reward r of state r' given an action a in state s (and you sum over all the possible outcomes of action a in state s, which are not unique in a stochastic environment)
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:12:13.837Z
Answers.Text: So, you mean the given probabilities in the assignment are actually the transition probabilities, $p(s',r|s,s)$, right? And I can't access the link you shared
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:19:48.060Z
Answers.Text: @Carrick Yes exactly. Here's again the link, hope it works if I paste it without hyperlink https://www.cis.upenn.edu/~cis519/fall2015/lectures/14_ReinforcementLearning.pdf
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:28:13.557Z
Answers.Text: I think there's no problem with the link it's probably just some restriction by my ISP, no clue why tho. But anyway, thank you.
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:34:38.050Z
Answers.Text: One more thing, in the next question it asks me to implement the policy iteration algorithm to find the optimal policy. If I take these probabilities to be the transition probabilities $p(s',r|s,s)$, then I won't have an initial policy $\pi(a|s)$ for policy iteration. Do you think there is an error in the assignment itself too, as I'm starting to believe it?
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:46:04.587Z
Answers.Text: No error, you just need to randomly initialise it. Then through policy improvement it will converge to the optimal one. If you have doubts about value vs policy iteration notice that the only difference  is in the update of the policy, which happens only once for value iteration, and after each value update for policy iteration. This [answer](https://stackoverflow.com/questions/37370015/what-is-the-difference-between-value-iteration-and-policy-iteration) might also help.
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T01:55:56.370Z
Answers.Text: Last thing for now: focus on the fact that a policy is just a mapping between states and actions (e.g. cell1: go right, cell5: go right, cell6: go down, etc.). So you don't need transition probabilities to initialise one. The transition probabilities come into play only in the updating of the values, leading (indirectly) also to a change in the final optimal policy (I think this might be something that's causing you confusion).
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T02:03:23.077Z
Answers.Text: ok. Understood.
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T02:41:50.167Z
Answers.Text: please do check out example 4.1 on page 61 [here.](http://incompleteideas.net/book/bookdraft2017nov5.pdf)
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T12:09:57.960Z
Answers.Text: @Carrick what's about it? Also, it is different from your assignment since the transition probabilities are 1 for all (possible) actions.
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T12:18:47.177Z
Answers.Text: It's exactly the same. They took the policy as an equiprobable one for all the four actions but still the transition probabilities are still taken as 1 and not 0.25 according to the initial policy because the outcomes are purely deterministic and from a given state s if an action a is taken then it's guaranteed to land in an unique state s', hence the transition probability 1
Answers.UserDisplayName: Carrick
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T13:42:21.930Z
Answers.Text: "from a given state s if an action a is taken then it's guaranteed to land in an unique state s', hence the transition probability 1" it's the other way around "Since the transition probabilities are 1, it is guaranteed to land in a unique state s'". They also explicitly state it. "p(6, −1|5, right) = 1, p(7, −1|7, right) = 1, and p(10, r|5, right) = 0 for all r ∈ R." where the last example is needed to specify that you cannot move in diagonal directions (states 10 and 5 form a diagonal). Again, in your assignment you are given transition probabilities which are different from 1.
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T13:46:07.173Z
Answers.Text: Ergo, the answer to the second question is that when the value of a or b is much higher than the other, this will be reflected on the optimal policy, because the agent will start to choose more times the direction (action) in which it is less likely to fail, i.e. the action with the highest transition probability (because the agent learn that even if the reward is maybe lower, the success rate is higher).
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T16:25:06.550Z
Answers.Text: @Carrick I edited the question with a visual example. Hope it helps clarifying the difference between the Sutton and Barto example and your assignment. If not, please let's move to a private chat, we wrote already too many comment for the community standards.
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T17:57:39.457Z
Answers.LastActivityDate: 2020-04-22T16:23:14.560Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>I've been recently given an assignment based on Reinforcement Learning and I'm supposed to implement the value iteration algorithm in a grid environment.</p>
  
  <p>The assignment: </p>
  
  <p><a href="https://i.sstatic.net/GOhkV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GOhkV.png" alt="enter image description here"></a></p>
  
  <p><a href="https://i.sstatic.net/0IuZE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0IuZE.png" alt="enter image description here"></a></p>
  
  <p>My doubt is why do I even need an initial arbitrary policy as given in the parameters (in the assignment) to implement the value iteration algorithm? And so, the change in the values of a and b shouldn't affect the algorithm. Am I correct in my thinking about it?</p>
  
Tags: <reinforcement-learning><policies><value-functions><value-iteration>
Title: Why do I need an initial arbitrary policy to implement value iteration algorithm
UserDisplayName: Carrick
ThreadText: # Why do I need an initial arbitrary policy to implement value iteration algorithm
  
  (Asked by: username_0 on 2020-04-16)
  
  I've been recently given an assignment based on Reinforcement Learning and I'm supposed to implement the value iteration algorithm in a grid environment.
  
  The assignment:
  
  [![enter image description here](https://i.sstatic.net/GOhkV.png)](https://i.sstatic.net/GOhkV.png)
  
  [![enter image description here](https://i.sstatic.net/0IuZE.png)](https://i.sstatic.net/0IuZE.png)
  
  My doubt is why do I even need an initial arbitrary policy as given in the parameters (in the assignment) to implement the value iteration algorithm? And so, the change in the values of a and b shouldn't affect the algorithm. Am I correct in my thinking about it?
  
  **Tags:** reinforcement-learning, policies, value-functions, value-iteration
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-16. Score: 2
  
  It seems to me that you're thinking about the parameters *a* and *b* as being characteristic of the agent that's moving in the environment (therefore determining the final policy), but they are actually a characteristic of the environment.
  
  Think of a frozen lake. You want to pass the lake but there is a hole five meters in front of you. Let's say you have boots with a rubber sole, so there is no risk to slip while walking (i.e. all transition probabilities =1). What is the optimal policy? Simply moving forward till the hole, goes around it and then forward again. But what if you were wearing wooden clogs instead? Now if you walk forward there is the risk to not be able to stop when you want to (i.e. when you decide to move forward of one step you might fail and keep going forward for several steps, with probability *a*). How many steps would you wait before moving to the left or to the right to avoid risking to fall into the hole? The optimal policy is obviously different in this second scenario. Think about it, I will not answer in detail about how the parameters affect the final policy because stack exchange is not meant for homework.
  
  Also, an arbitrary policy is necessary simply because in value iteration you first update the values and only when they converge you infer from then the optimal policy. So you need some arbitrary prior belief about the environment to start update the values.
  
  # Edit
  
  So here's a quick visualisation of the impact of different transition probabilities (the parameters *a* and *b* in your assignment) on the optimal policy. I used a different grid to make it easier and more explicit (i.e. you don't even need to calculate the values to see the optimal policy).
  
  As you can see in the picture below, there are some terminal states in the third column and a goal state which gives a huge reward on top of it. From the starting point on the bottom we want to reach the goal state.
  
  [![enter image description here](https://i.sstatic.net/CswSv.jpg)](https://i.sstatic.net/CswSv.jpg)
  
  We have two cases:
  
  > **Non stochastic environment**
  
  On the left we have the case in which all transition probabilities are 1. In this case the optimal policy is simply going forward till the second row, where the goal state is located, and then move right or left to reach it. The terminal states are not scary at all, in this case we could consider them as walls that we can't cross, but the optimal policy do not reflect any risk of falling in them. This is precisely because the transition probabilities are all 1.
  
  > **Stochastic environment**
  
  On the right we have a different situation. In this case only 3 action have a transition probability of 1: going south, east or west. The transition probability for nord is 0.2 meaning that 80% of the time we will slip and go east instead (I wrote right in the picture meaning east, my bad). What is the impact of this simple change in the environment?
  
  This time the second column become really dangerous, because if we try to go nord and fail we will end on a terminal state. On the other hand, if we choose another action we will end on a legitimate state, without any risk because the other transition probabilities are 1! Therefore the agent learn that on the left side of the grid the best strategy is to go down and circumnavigate the terminal states from the right, because only in the fourth column we can move north without risk, in fact in those cells even if we try go north and fail we would just hit a wall and we could try again going north the next turn till we will eventually succeed.
  
  Hope this make sense!
  
  > **Comments:**
  > **username_0**: Thank you for the answer but I still have some doubts like why is my problem similar to the second case of frozen lake you talked about? In my problem, if the agent in state $s$ takes an action $a$ to reach state $s'$, isn't the transition probability simply equal to one/zero? I thought the probabilities given were actually $\pi(a|s)$, which gives the probability of a particular action being chosen when our agent is in a state $s$. And while applying the value iteration update rule, we don't require these probabilities, $$V_{k+1}(s) \leftarrow max_a \sum_{s',r}p(s',r|s,a)[r+\gamma V_k(s')]$$  
  > **username_1**: @Carrick From the text I would say that the transition probabilities are (N,S,W,E) = (0.2,0.3,a,b), or at least I don't see any other possible interpretation. So you have to reason in terms of a stochastic environment, and therefore the frozen lake, which is a classic example used to explain stochastic grid world (plenty of many others if you google it, I suggest particularly [this one](https://www.cis.upenn.edu/~cis519/fall2015/lectures/14_ReinforcementLearning.pdf).  
  > **username_1**: Also the transition probabilities in the formula are: p(s',r | s,a) i.e. probability of getting reward r of state r' given an action a in state s (and you sum over all the possible outcomes of action a in state s, which are not unique in a stochastic environment)  
  > **username_0**: So, you mean the given probabilities in the assignment are actually the transition probabilities, $p(s',r|s,s)$, right? And I can't access the link you shared  
  > **username_1**: @Carrick Yes exactly. Here's again the link, hope it works if I paste it without hyperlink https://www.cis.upenn.edu/~cis519/fall2015/lectures/14_ReinforcementLearning.pdf  
  > **username_0**: I think there's no problem with the link it's probably just some restriction by my ISP, no clue why tho. But anyway, thank you.  
  > **username_0**: One more thing, in the next question it asks me to implement the policy iteration algorithm to find the optimal policy. If I take these probabilities to be the transition probabilities $p(s',r|s,s)$, then I won't have an initial policy $\pi(a|s)$ for policy iteration. Do you think there is an error in the assignment itself too, as I'm starting to believe it?  
  > **username_1**: No error, you just need to randomly initialise it. Then through policy improvement it will converge to the optimal one. If you have doubts about value vs policy iteration notice that the only difference  is in the update of the policy, which happens only once for value iteration, and after each value update for policy iteration. This [answer](https://stackoverflow.com/questions/37370015/what-is-the-difference-between-value-iteration-and-policy-iteration) might also help.  
  > **username_1**: Last thing for now: focus on the fact that a policy is just a mapping between states and actions (e.g. cell1: go right, cell5: go right, cell6: go down, etc.). So you don't need transition probabilities to initialise one. The transition probabilities come into play only in the updating of the values, leading (indirectly) also to a change in the final optimal policy (I think this might be something that's causing you confusion).  
  > **username_0**: ok. Understood.  
  > **username_0**: please do check out example 4.1 on page 61 [here.](http://incompleteideas.net/book/bookdraft2017nov5.pdf)  
  > **username_1**: @Carrick what's about it? Also, it is different from your assignment since the transition probabilities are 1 for all (possible) actions.  
  > **username_0**: It's exactly the same. They took the policy as an equiprobable one for all the four actions but still the transition probabilities are still taken as 1 and not 0.25 according to the initial policy because the outcomes are purely deterministic and from a given state s if an action a is taken then it's guaranteed to land in an unique state s', hence the transition probability 1  
  > **username_1**: "from a given state s if an action a is taken then it's guaranteed to land in an unique state s', hence the transition probability 1" it's the other way around "Since the transition probabilities are 1, it is guaranteed to land in a unique state s'". They also explicitly state it. "p(6, −1|5, right) = 1, p(7, −1|7, right) = 1, and p(10, r|5, right) = 0 for all r ∈ R." where the last example is needed to specify that you cannot move in diagonal directions (states 10 and 5 form a diagonal). Again, in your assignment you are given transition probabilities which are different from 1.  
  > **username_1**: Ergo, the answer to the second question is that when the value of a or b is much higher than the other, this will be reflected on the optimal policy, because the agent will start to choose more times the direction (action) in which it is less likely to fail, i.e. the action with the highest transition probability (because the agent learn that even if the reward is maybe lower, the success rate is higher).  
  > **username_1**: @Carrick I edited the question with a visual example. Hope it helps clarifying the difference between the Sutton and Barto example and your assignment. If not, please let's move to a private chat, we wrote already too many comment for the community standards.  
  
  ---
  
  