Number of states in taxi environment (Dietterich 2000)

Question

Dietterich, who introduced the taxi environment (see p. 9), states the following: In total there “are 500 [distinct] possible states: 25 squares, 5 locations for the passenger (counting the four starting locations and the taxi), and 4 destinations” (Dietterich, 2000, p. 9).

However, in my opinion there are only 25 (grid) * 4 (locations) * 2 (passenger in car) = 200 different states, because for the agent it should be the same task to go to a certain point, regardless of whether it's on its way to pick up or to drop-off. Only the action at the destination is different which would be stored binary (passenger in car or not)

Why does Dietterich come up with 500 states?

Answer 1

This is more of a combinatorics than AI question but regradless, the full state information for the environment is:

$(taxi \space position, passenger \space position, destination \space position)$

There are 25 possible taxi positions, 5 passenger positions and 4 destination positions making it $25 \cdot 5 \cdot 4 = 500$, so the paper is correct.

You are also correct but you divided 1 objective into 2 objectives and you have 2 separate policies, a pickup policy and a dropoff policy. So your state information would be for each policy:

$(taxi \space position, destination \space position)$

There are 25 possible taxi positions and 4 possible destination positions making it $25 \cdot 4 = 100$. You have 2 policies so you have $200$ states.

EDIT

Actually in the second case, I think you could get away with only 1 policy where you would simply change the destination position once you pick up the passenger so you dont need 2 separate policies and you would have only $100$ states

Answer 2

This . . .

because for the agent it should be the same task to go to a certain point, regardless of whether it's on its way to pick up or to drop-off

. . . might seem logical/intuitive to a person understanding the task, but it is not mathematically correct. The agent cannot "merge" states because they involve the same behaviour. It must count differences in state as the combinations are presented. Critically, heading towards the passenger location or heading towards the goal location are not in any way similar to the agent, unless you manipulate the state to make them so*.

Eventually the taxi will learn very similar navigation behaviour for picking up and dropping off a passenger. However, using a basic RL agent it learns these very much separately, and must re-learn the navigation rules independently for each combination of passenger and goal location.

An agent that learned navigation within the environment, and then combined it into different tasks might be an example of hierarchical reinforcement learning, transfer learning, or curriculum learning. These are more sophisticated learning approaches, but it is quite interesting that even very basic RL problems can demonstrate a use for higher level abstractions. Most agents used on the taxi problem don't do this though, as 500 states is really very easy to "brute force" using the simplest algorithms.

---

* You could modify the state representation to rationalise the task and make it have less states, similar to your suggestion. For instance, have one "target" location which could either be pickup or drop off, and a boolean "carrying passenger" state component. That would indeed reduce the number of states. However, that has involved you as the problem designer simplifying the problem to make it easier for the agent. Given that this is a toy problem designed as a benchmark to see how different agents perform, by doing that you subvert the purpose of the environment. If you were creating an agent to work on a harder real world problem though, it might be a very good idea to look for symmetries and ways to simplify state representation which would speed up learning.