4
$\begingroup$

Regarding Value Iteration of Dynamic Programming(reinforcement learning) in grid world, the value updation of each state is given by:
enter image description here


Now Suppose i am in say box (3,2). I can go to (4,2)(up) (3,3)(right) and (1,3)(left) and none of these are my final state so i get a reward of -0.1 for going in each of the states. The present value of all states are 0. The probability of going north is 0.8, and going left/right is 0.1 each. So since going left/right gives me more reward(as reward*probability will be negative) i go left or right. Is this the mechanism. Am I correct? But In the formula there is a summation term given. So I basically cannot understand this formula. Can anyone explain me with an example?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The probabilities you describe refer only to the go-north action. It means that if you want to go north, you have 80% chance of actually going north and 20% of going left or right, making the problem more difficult (non-deterministic). This rule applies to every direction. Also, the formula does not tell which action to chose, just how to update the values. In order to select an action, assuming a greedy-policy, you'd select the one with the highest expected value ($V(s')$).

The formula says to sum the values for all possible outcomes from the best action. So, supposing go-north is indeed the best action, you have:

$$.8 * (-.1 + 0) + .1 * (-.1 + 0) + .1 * (-.1 + 0) = -.1$$

But let us suppose that you still don't know which is the best action and want to select one greedily. Then you must compute the sum for each possible action (north, south, east, west). Your example has all values set to 0 and the same reward and so is not very interesting. Let's say you have a +1 reward to east (-0.1 for the remaining directions) and that south already has V(s) = 0.5 (0 for the remaining states). Then you compute the value for each action (let $\gamma = 1$, since it is a user-adjusted parameter):

  • North: $.8 * (-.1 + 0) + .1 * (-.1 + 0) + .1 * (1 + 0) = -.08 - .01 + .1 = .01$
  • South: $.8 * (-.1 + .5) + .1 * (-.1 + 0) + .1 * (1 + 0) = 0.32 - .01 + .1 = .41$
  • East: $.8 * (1 + 0) + .1 * (-.1 + 0) + .1 * (-.1 + .5) = .8 - .01 + .04 = .83$
  • West: $.8 * (-.1 + 0) + .1 * (-.1 + 0) + .1 * (-.1 + .5) = -.08 - .01 + .04 = -.05$

So you would update your policy to go East from the current state, and update the current state value to 0.83.

Improve this answer
$\endgroup$
2
  • $\begingroup$ another question, in most of the grid world problem one state has a high valued number written on it,like +100. Is that the reward or the value of that state $\endgroup$
    – girl101
    Aug 7, 2015 at 8:48
  • $\begingroup$ It is the reward, which is fixed for the problem. The value is learned, it is an estimate of accumulated future rewards going from that state. $\endgroup$
    – rcpinto
    Aug 7, 2015 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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