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

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.

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$$.

• thanks for the answer. I totally understand where I was going wrong now--probably just overthinking it. I upvoted your answer, but included my own answer with the full system of equations written out. Thanks for taking the time to post. Jul 20 at 16:07

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}$$