How to setup the Bellman Equation as a linear system of equation

Question

I was watching a video on Reinforcement Learning by Andrew Ng, and at about minute 23 of the video he mentions that we can represent the Bellman equation as a linear system of equations. I am talking about the Hamilton-Jacobi-Bellman equation, used for discrete control problems or discrete reinforcement learning problems.

The equation as he posts it is:

$$ V^\pi(s) = R(s) + \gamma\sum_{s`}P_{s,\pi(s)}V^\pi(s`) $$

$V^\pi(s)$ represents the "value" at state $s$. So the idea is simple enough. But I was not clear on how to really represent this as a system of equation. I have a notion of this, but I was hoping that someone could help fill in the correct answer.

So in the linear system, the $V^\pi(s)$ is the unknown. A linear system looks like $Ku = f$. Now, I know that in some Markov Decision Process, I have a probability of the subsequent states $s'$ given the action $a$ that is chosen. So if the policy indicates go "North", then I have an 80% chance of going north, with a 10% chance of going East, and a 10% chance of going West. That is the reason for the probability.

Now for convenience I will write $v_1, v_2$, instead of $V^\pi(s_1), V^\pi(s_2),...$. The biggest point of confusion is how to handle the immediate reward $R(v_i)$. I would basically have a system like the following, (I left out the $\gamma$ just to simplify the notation).

$$ -v_1 + 0.8v_2 + 0.1v_3 + 0.1v_4 + 0 + 0 + ... + R(v_1) = 0 \\ 0.8v_1 - v_2 + 0.1v_3 + 0 + 0.1v_5 + ... + R(v_2) = 0 \\ ... $$

So I could express this as a system with a vector of $[v_1, v_2, ..., v_n]$, and a matrix of coefficients like :

$$ \begin{bmatrix} -1 & 0.8 & 0.1 & 0.1 & 0 & 0 & 0 & ... \\ 0.8 & -1 & 0.1 & 0 & 0.1 & 0 & 0 & ... \\ \vdots \\ \end{bmatrix} * \begin{bmatrix} v_1 \\ v_2 \\ \vdots \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ \end{bmatrix} $$

Or is the reward $R(v_1) = v_1$ in which case I would have 0's on the diagonal of the coefficient matrix.

Again, Ng did not write this out completely, so I am just trying to figure it out. I think I am just about there, but missing the last 10 percent.

Answer 1

I found the full answer in a video by David Silver. The idea is easy enough.

The underlying matrix equation is

$$ v = R^\pi + \gamma P^\pi_{s, s'} v $$

Where $v$ is the value function, $R^\pi$ is the immediate reward under policy $\pi$, $\gamma$ is the discount factor, and $P^\pi_{s, s'}$ is the transition matrix.

I can write out the system of equations as below. For the sake of convenience, I omit the $\pi$ and the $\{s, s'\}$ subscripts.

$$ \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix} = \begin{bmatrix} R_1 \\ R_2 \\ \vdots \\ R_n \end{bmatrix} + \gamma \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1n} \\ p_{21} & p_{22} & \cdots & p_{2n} \\ \vdots \\ p_{n1} & \cdots & \cdots & p_{nn} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix} $$

I can solve the matrix equation with some simple linear algebra:

$$ \begin{align*} v &= R + \gamma P v \\ v - \gamma P v &= R \\ (I - \gamma P)v &= R \\ v &= (I - \gamma P)^{-1}R \end{align*} $$

Now of course this solution involves inverting a matrix and that is not easy to do except in very small cases. So we can use iterative methods to solve for $v$. But iterative methods just alter the above equation such that.

$$ v^{k+1} = R^\pi + \gamma P^\pi_{s, s'} v^{k} $$

Answer 2

It seems that you confused yourself about this a bit too much. Lets start from the beggining:

First, we want to note that in Bellman's equations, the rewards $R(v)$ are defined as the expected value of the immediate reward (since it could be a random variable). That is, $R(s):=\mathbb{E}[R_{immediate}(s,\pi(s))]$. The important part to note here, is that $R(s)$ is some known constant!. Our variables in this system, as you said, are the $V^\pi (s)$ for all states $s$. So, for every such state $s$ we have one linear equation, that is described by bellman's equation: The equations depend linearly on the values $V(s')$. Combine the equations together (put them as a system of equations), and viola! You will get a system of linear equations!

You don't really need to express that as a matrix multiplication to know its linear, but if you still want to: We will treat the states as indices that range between 1 and $n$ (the number of total states). Now, start from replacing $V(s)$ with a variable $x_s$ you solve for. Then, write the $$P[\text{next state is }s'\mid \text{ we are in }s\text{ and do action }\pi(s)]$$ As $A_{s,s'}$. Then, write $R(s)$ as $b_s$, and rewrite the system as a matrix multiplication system: $Ax=b$.