Calculating Value State matrix for a finite MDP without limit condition

Question

In the book "Reinforcement Learning" From Andrew Sutton and Barto there is an example given for the Bellman equations:

Figure 3.2 (left) shows a rectangular gridworld representation of a simple finite MDP. The cells of the grid correspond to the states of the environment. At each cell, four actions are possible: north, south, east, and west, which deterministically cause the agent to move one cell in the respective direction on the grid. Actions that would take the agent o↵ the grid leave its location unchanged, but also result in a reward of .1. Other actions result in a reward of 0, except those that move the agent out of the special states A and B. From state A, all four actions yield a reward of +10 and take the agent to A0. From state B, all actions yield a reward of +5 and take the agent to B0

Then it continues:

Suppose the agent selects all four actions with equal probability in all states. Figure 3.2 (right) shows the value function, v⇡, for this policy, for the discounted reward case with gamma = 0.9. This value function was computed by solving the system of linear equations (3.14). Notice the negative values near the lower edge; these are the result of the high probability of hitting the edge of the grid there under the random policy.

3.14 equation being (so the state-value bellman equation):

I just wonder, without knowing when the task ends, how can we calculate the given matrix on figure 3.2? And with that gamma, it will need a lot of iterations until we can ignore it. Just trying to wrap my head around how to calculate each cell or if there is something I am ignoring.

Answer 1

The task doesn't end.

In RL terms, "value" at state $s$ means the weighted sum of all future rewards when starting from state $s$ and following policy $\pi$. In this example the states will transit infinitely times.

Of course it's impossible to iterate infinitely times to calculate the value, that's why the Bellman equation $(3.14)$ is so important, because Bellman discovers that the values (the wieghted sum of all future rewords) of different states satisfy a relation stated by $(3.14)$, which is basically a system of linear equations of the values.

So to calculate the values of the states, instead of iterating infinite times and accumulating the rewords for each state, you can simply solve the linear system and the result is there.