# Calculating Value State matrix for a finite MDP without limit condition

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.

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.
• In this example you don't need any matrix algebra. The authors use matrix to represent the game board, each cell in the board corresponds to a state, there are 25 states in total. Bellman equation $(3.14)$ provides a linear system of 25 equations with 25 unknown values. Solve this linear system will get you the result. Apr 20, 2020 at 19:46