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:
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?
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.
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.
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!
