How do I apply the value iteration algorithm when there are two goal states?

Question

I am working through the famous RL textbook by Sutton & Barto. Currently, I am on the value iteration chapter. To gain better understanding, I coded up a small example, inspired by this article.

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).

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.

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?

Answer 1

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.