Answers.Body: <p>What you could do is to trigger environment termination when rat either:  </p>
  
  <ol>
  <li>steps into the trap  </li>
  <li>picks both cheese pieces  </li>
  </ol>
  
  <p>The problem with such setup is that, when the rat picks a single piece, it would move one step to the side, and then it would come back to the same cheese spot so it would keep exploiting the same spot indefinitely. </p>
  
  <p>The solution to that would be to simply remove the cheese piece once the rat picks it up, so that it can't exploit it indefinitely. </p>
  
  <p>Sadly, another problem would arise which is partial observability: Markov property wouldn't be fulfilled because the current action wouldn't depend on the current state solely, it would be important whether cheese piece was picked before or not. </p>
  
  <p>The solution to that would be to make environment fully observable. You could accomplish that by expanding the amount of information about your current state. Before, only your position on the grid was important, but now you would also add state features that tell you whether cheese piece at specific position was picked or not. You would basically add a flag for each cheese piece that has value of 1 if piece was picked, or value of 0 if it wasn't. That way you could remove cheese piece it rat picks it, and you would still have full information. </p>
  
  <p>I believe this setup would work.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-24T17:09:06.503Z
Answers.Text: thanks for the answer. would I still model the two squares with cheese as terminal states?
Answers.UserDisplayName: cmplx96
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-25T12:04:52.910Z
Answers.Text: yes, both can be terminal states
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-19T20:30:18.177Z
Answers.LastActivityDate: 2019-02-20T18:33:53.733Z
Answers.LastEditDate: 2019-02-20T18:33:53.733Z
Answers.UserDisplayName: Brale
Body: <p>I am working through the famous RL textbook by Sutton &amp; Barto. Currently, I am on the <a href="http://www.incompleteideas.net/book/ebook/node44.html" rel="nofollow noreferrer">value iteration chapter</a>. To gain better understanding, I coded up a small example, inspired by <a href="http://www.incompleteideas.net/book/ebook/node41.html" rel="nofollow noreferrer">this article</a>.</p>
  
  <p>The problem is the following</p>
  
  <blockquote>
    <p>There is a rat (R) in a grid. Every square is accessible. The goal is to find the cheese (C). However, there is also a trap (T). The game is over whenever the rat either find the cheese or is trapped (these are my terminal states). </p>
  </blockquote>
  
  <p><a href="https://i.sstatic.net/8CqfK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8CqfK.png" alt=""></a></p>
  
  <p>The rat can move up, down, left, and right (always by one square). </p>
  
  <p>I modeled the reward as follows:</p>
  
  <pre><code>-1 for every step
  5 for finding the cheese
  -5 for getting trapped
  </code></pre>
  
  <p>I used value iteration for this and it worked out quite nice.</p>
  
  <p>However, now I would like to add another cheese to the equation. In order to win the game, the rat has to collect <em>both</em> cheese pieces.</p>
  
  <p><a href="https://i.sstatic.net/nAlf9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nAlf9.png" alt=""></a></p>
  
  <p>I am unsure how to model this scenario. I don't think it will work when I use both cheese squares and the trap square as terminal states, with rewards for both cheese squares.</p>
  
  <p>How can I model this scenario? Should I somehow combine the two cheese states into one?</p>
  
Tags: <reinforcement-learning><sutton-barto><value-iteration>
Title: How do I apply the value iteration algorithm when there are two goal states?
UserDisplayName: cmplx96
ThreadText: # How do I apply the value iteration algorithm when there are two goal states?
  
  (Asked by: username_0 on 2019-02-19)
  
  I am working through the famous RL textbook by Sutton & Barto. Currently, I am on the [value iteration chapter](http://www.incompleteideas.net/book/ebook/node44.html). To gain better understanding, I coded up a small example, inspired by [this article](http://www.incompleteideas.net/book/ebook/node41.html).
  
  The problem is the following
  
  > There is a rat (R) in a grid. Every square is accessible. The goal is to find the cheese (C). However, there is also a trap (T). The game is over whenever the rat either find the cheese or is trapped (these are my terminal states).
  
  [![](https://i.sstatic.net/8CqfK.png)](https://i.sstatic.net/8CqfK.png)
  
  The rat can move up, down, left, and right (always by one square).
  
  I modeled the reward as follows:
  
  ```
  -1 for every step
  5 for finding the cheese
  -5 for getting trapped
  
  ```
  
  I used value iteration for this and it worked out quite nice.
  
  However, now I would like to add another cheese to the equation. In order to win the game, the rat has to collect *both* cheese pieces.
  
  [![](https://i.sstatic.net/nAlf9.png)](https://i.sstatic.net/nAlf9.png)
  
  I am unsure how to model this scenario. I don't think it will work when I use both cheese squares and the trap square as terminal states, with rewards for both cheese squares.
  
  How can I model this scenario? Should I somehow combine the two cheese states into one?
  
  **Tags:** reinforcement-learning, sutton-barto, value-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-19. Score: 3 | Accepted answer
  
  What you could do is to trigger environment termination when rat either:
  
  1. steps into the trap
  2. picks both cheese pieces
  
  The problem with such setup is that, when the rat picks a single piece, it would move one step to the side, and then it would come back to the same cheese spot so it would keep exploiting the same spot indefinitely.
  
  The solution to that would be to simply remove the cheese piece once the rat picks it up, so that it can't exploit it indefinitely.
  
  Sadly, another problem would arise which is partial observability: Markov property wouldn't be fulfilled because the current action wouldn't depend on the current state solely, it would be important whether cheese piece was picked before or not.
  
  The solution to that would be to make environment fully observable. You could accomplish that by expanding the amount of information about your current state. Before, only your position on the grid was important, but now you would also add state features that tell you whether cheese piece at specific position was picked or not. You would basically add a flag for each cheese piece that has value of 1 if piece was picked, or value of 0 if it wasn't. That way you could remove cheese piece it rat picks it, and you would still have full information.
  
  I believe this setup would work.
  
  > **Comments:**
  > **username_0**: thanks for the answer. would I still model the two squares with cheese as terminal states?  
  > **username_1**: yes, both can be terminal states  
  
  ---
  
  