2
$\begingroup$

I am practicing the Bellman equation on Grid world examples and in this scenario, there are numbered grid squares where the agent can choose to terminate and collect the reward equal to the amount inside the numbered square or they can choose to not do this and just move to the state grid square.

Since this is a determinisitc grid, I have utilised the following Bellman equation: $$V(s) = max_a(R(s,a)+\gamma V(s'))$$

Where $\gamma=0.5$ and any movement reward is $0$, since this will allow the agent to have a balance of thinking long-term and short-term.

I am trying to understand how you would determine whether it is better for the agent to terminate at the state with the number $3$ or to continue to the state with a number $4$ to collect the more reward? I have determined and marked (X) the terminal states, where with my current calculations, I feel the agent should exit.

enter image description here

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hi Krellex, I have rolled back the image edit as the new image stops looking line an MDP to me. By losing the arrows and the crosses, there is no indication of the actions. By losing the separate reward numbers, there is no indication of reward, only a list of values. In general, there is no need to "fix" parts of the question when you receive an answer that corrects something in it. You can and should make edits that when someone adds a comment asking you to clarify something, However, it should be avoided when there is an answer which refers to that part of your question. $\endgroup$
    – Neil Slater
    Apr 17, 2022 at 8:23
  • $\begingroup$ @NeilSlater Ah ok! Thanks for changing it back. I thought my edit might have made it clearer, but you're right, the older one was much clearer. Thanks for the update. $\endgroup$
    – Krellex
    Apr 17, 2022 at 8:32
  • $\begingroup$ By the way, your diagram happens to show an entirely self-consistent policy and matching state values. That is, all the values are correct given the policy shown by the arrows and crosses. The only thing "wrong" about it is that the policy is not the optimal one that you were looking for - in just one state. Which is what your question was about, so that's fine. $\endgroup$
    – Neil Slater
    Apr 17, 2022 at 8:40
  • $\begingroup$ @NeilSlater I have implemented the changes for State 3 so it's optimal. I have also updated state (1,3) to exit at state (2,3) to collect a reward of 2 since this would be the most optimal movement since it returns the highest value from all actions given a discount value of $\gamma=0.5$ I think that would be correct for that state also? $\endgroup$
    – Krellex
    Apr 17, 2022 at 8:48
  • $\begingroup$ For state at (2,3) with exit value of 2, you have a choice. Both moving up towards (4,3) for an eventual reward of 8 and taking the immediate exit for reward of 2 have a value of 2. In ties for maximum return, then both actions are optimal. I suspect the grid world has been deliberately set up to show that as a discussion point. $\endgroup$
    – Neil Slater
    Apr 17, 2022 at 9:03

1 Answer 1

Reset to default
3
$\begingroup$

I am trying to understand how you would determine whether it is better for the agent to terminate at the state with the number 3 or to continue to the state with a number 4 to collect the more reward?

Which is better is determined by looking at the expected return from either choice, with higher expected returns being better.

The return from travelling one time step to the "4 on exit" state, is 2 as you have shown, due to discounting. That is assuming the 4 is gained by taking a separate "exit" action once in that position. That is, there is no combined "move and exit" action that only takes one time step - whether or not such actions exist in this environment makes a large change to your example and what will be optimal, so it is really important to be clear about that.

The return from exiting immediately in the "3 on exit" state is 3.

3 is larger than 2, so if the agent finds itself in the "3 on exit" state, then it should exit immediately to get the best expected return.

Possibly what might be making this harder to understand is the role that discounting takes. Sometimes it appears to be used to "fix" infinite rewards from continuing environments. However, discounting is part of the definition of return, and it changes what counts as optimal. With a low discount factor, such as $0.5$, then it can be optimal to take a lower reward sooner as opposed to a larger reward later. The value of the discount factor allows to make that comparison exactly.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the reply! From a numbered square, if the agent wants they can exit to a terminal state X which will give them a reward equal to the number in the square. You are right, there is no combined move and exit. So we can either move or exit. Given this, we would then exit at state 3? The state before state 3 will then become $(3+0.5(3))?$ Where $R = 3, \gamma=0.5 , V' = 3$ $\endgroup$
    – Krellex
    Apr 16, 2022 at 9:05
  • 1
    $\begingroup$ @Krellex You already have the value of the state below the "3 on exit" state correct. An agent in that state acting optimally would travel up, gaining 0 immediate reward and arriving in the state "3 on exit" which has a value of 3. So $V^*(s) = 0 + 0.5(3) = 1.5$. We can tell that is optimal in this simple environment as there is no chain of moves that could possibly gain a higher return than 1.5 from that location (in more complex environments you won't be able to see that so clearly) $\endgroup$
    – Neil Slater
    Apr 16, 2022 at 9:07
  • $\begingroup$ Thanks so much for this clear explanation, really helped me understand! $\endgroup$
    – Krellex
    Apr 16, 2022 at 9:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .