Consider the domain shown in Figure 13.1. There are six states the agent could be in, labeled $s_0,\mathrm{\dots },s_5$. The agent has four actions: $upR$, $upC$, $left$, $right$. That is all the agent knows before it starts. It does not know how the states are configured, what the actions do, or how rewards are earned.

Figure 13.1 shows the configuration of the six states. Suppose the actions work as follows:

right

The agent moves to the right in states $s_0$ ,$s_2$, and $s_4$, with a reward of 0 and stays still in the other states, with a reward of $-1$.

left

The agent moves one state to the left in states $s_1$, $s_3$, and $s_5$, with a reward of 0. In state $s_0$, it stays in state $s_0$ and has a reward of $-1$. In state $s_2$, it has a reward of $-100$ and stays in state $s_2$. In state $s_4$, it receives a reward of $10$ and moves to state $s_0$.

upC

(for “up carefully”) The agent goes up, except in states $s_4$ and $s_5$, where the agent crashes and stays still. It receives a reward of $-1$, except when it crashes, in which case there is a reward of $-2$.

upR

(for “up risky”) With a probability of $0.8$ it acts like $upC$, except the reward is $-1$ when it crashes, and 0 otherwise. With probability $0.1$ it acts as a $left$, and with probability $0.1$ it acts as a $right$.

There is a discounted reward with a discount of $\gamma =0.9$. This can be translated as having a 0.1 chance of the agent leaving the game at any step, or as a way to encode that the agent prefers immediate rewards over future rewards.

The agent should try to go left from $s_4$ as often as possible, to collect the reward of $+10$. Getting from $s_0$ to $s_4$, it can go past a dangerous cliff at $s_2$ where there is a risk of falling off the cliff and getting a large negative reward, or going the longer and safer way around. Initially, it does not know this, but this is what it needs to learn.

Figure 13.2 shows the domain of a more complex game. There are 25 grid locations the agent could be in. A prize could be on one of the corners, or there could be no prize. When the agent lands on a prize, it receives a reward of $10$ and the prize disappears. When there is no prize, for each time step there is a probability that a prize appears on any one of the corners. Monsters can appear at any time on one of the locations marked $M$. The agent gets damaged if a monster appears on the square the agent is on. If the agent is already damaged, it receives a reward of $-10$. The agent can get repaired (so it is no longer damaged) by visiting the repair station marked $R$.

In this example, the state consists of four components: , where $X$ is the $X$-coordinate of the agent, $Y$ is the $Y$-coordinate of the agent, $D$ is Boolean and is true when the agent is damaged, and $P$ is the position of the prize ($P=0$ if there is no prize, $P=i$ if there is a prize at position $P_i$). Because the monsters are transient – knowing whether a monster appeared at a time does not provide any information about the future – it is not necessary to include them as part of the state. There are therefore $5\ast 5\ast 2\ast 5=250$ states. The environment is fully observable, so the agent knows what state it is in. The agent does not know the meaning of the states; it doesn’t know about the four components and it has no idea initially about being damaged or what a prize is.

The agent has four actions: $up$, $down$, $left$, and $right$. These move the agent one step – usually one step in the direction indicated by the name, but sometimes in one of the other directions. If the agent crashes into an outside wall or one of the interior walls (the thick lines near the location $R$), it remains where is was and receives a reward of $-1$.

The agent does not know any of the story given here. It just knows there are 250 states and four actions, which state it is in at each time, and what reward was received at each time.

This game is simple, but it is surprisingly difficult to write a good controller for it. There are implementations available on the book’s website that you can play with and modify. Try to write a controller by hand for it; it is possible to write a controller that accumulates a reward of about 500 for each 1000 steps. This game is also difficult to learn, because visiting $R$ is seemingly useless until the agent eventually learns that being damaged is bad, and that visiting $R$ makes it not damaged. It must stumble on this while trying to collect the prizes. The states where there is no prize available do not last very long. Moreover, it has to learn this without being given the concept of damaged; all it knows, initially, is that there are 250 states and four actions.