1
$\begingroup$

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

Figure from book

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): Value state 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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yes, I understand that s why Bellman equation is relevant, but i guess i cant wrap my head around the math. Could you solve one cell of the value matrix ? $\endgroup$
    – SirPeople
    Apr 20, 2020 at 19:40
  • $\begingroup$ 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. $\endgroup$ Apr 20, 2020 at 19:46
  • $\begingroup$ ah, i got it know, it was just not productive to show that it just applied 3.14 for each s and a within the MDP process. Thanks $\endgroup$
    – SirPeople
    Apr 21, 2020 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.