Answers.Body: <p>First of all, we assume that we have a <strong>finite MDP</strong>, i.e. the set of states <span class="math-container">$\mathcal{S}$</span>, the set of actions <span class="math-container">$\mathcal{A}$</span> and the set of rewards <span class="math-container">$\mathcal{R}$</span> all have a finite number of elements (I didn't think about how the explanations below would extend to other cases, but I suspect you will need differential equations).</p>
  <p>For simplicity, let's only consider the value function <span class="math-container">$v$</span> (as opposed to the state-action value function <span class="math-container">$q(s, a)$</span>, but this also applies to <span class="math-container">$q$</span>). The value function <span class="math-container">$v$</span> is defined for <strong>all states</strong>, i.e. it's a function of the form <span class="math-container">$v : \mathcal{S} \rightarrow \mathbb{R}$</span> or, with an alternative notation, <span class="math-container">$v(s), \forall s \in \mathcal{S}$</span>. So, we can define this function as a vector <span class="math-container">$\mathbf{v}$</span> of dimension <span class="math-container">$|\mathcal{S}| = n$</span>, i.e. <span class="math-container">$\mathbf{v} \in \mathbb{R}^{|\mathcal{S}|}$</span>, where the <span class="math-container">$i$</span>th element contains the value of the <span class="math-container">$i$</span>th state (so we need a function that maps states to indices of this vector, but this is trivial).</p>
  <p>The fact that you can represent the value function, in this finite MDP, as a vector should already suggest that you can find this value function by solving a linear system of equations.</p>
  <p>However, let me show that by starting with the definition of the value function you also provided</p>
  <p><span class="math-container">\begin{align}
  v_{\pi}(s) 
  &amp;= 
  \sum_{a} \pi(a\rvert s) \sum_{s^{\prime}}\sum_{r} p(s^{\prime}, r \rvert s,a)[r + \gamma v_{\pi}(s^{\prime})] \label{1}\tag{1}, \; \forall s \in \mathcal{S}
  \end{align}</span>
  which can be expanded as follows
  <span class="math-container">\begin{align}
  v_{\pi}(s) 
  &amp;= 
  \sum_{a} \pi(a\rvert s) \sum_{s^{\prime}}\sum_{r} \left[p(s^{\prime}, r \rvert s,a)r + \gamma p(s^{\prime}, r \rvert s,a) v_{\pi}(s^{\prime}) \right] \\
  &amp;= 
  \sum_{a} \pi(a\rvert s)  \left[ \sum_{r} \underbrace{\sum_{s^{\prime}} p(s^{\prime}, r \rvert s,a)}_{\text{Marginalization of }p \text{ over } s'}r + \gamma \sum_{s^{\prime}} \underbrace{\sum_{r} p(s^{\prime}, r \rvert s,a) }_{\text{Marginalization of }p \text{ over } r} v_{\pi}(s^{\prime}) \right]\\
  &amp;= 
  \sum_{a} \pi(a\rvert s)  \left[ \sum_{r} p(r \rvert s, a)r  + \gamma \sum_{s^{\prime}}p(s^{\prime} \rvert s,a) v_{\pi}(s^{\prime}) \right] \\
  &amp;= 
  \sum_{a} \pi(a\rvert s)  \left[ r(s, a)  + \gamma \sum_{s^{\prime}}p(s^{\prime} \rvert s,a) v_{\pi}(s^{\prime}) \right] \label{2}\tag{2}, \; \forall s \in \mathcal{S}
  \end{align}</span>
  where</p>
  <ul>
  <li><span class="math-container">$\sum_{r} p(r \rvert s, a)r = r(s, a)$</span> (see <a href="https://ai.stackexchange.com/a/24511/2444">this</a>).</li>
  <li><span class="math-container">$\sum_{s^{\prime}}p(s^{\prime}, r \rvert s,a) = p(r \rvert s, a)$</span> (<a href="https://en.wikipedia.org/wiki/Marginal_distribution" rel="nofollow noreferrer">marginalization</a>)</li>
  <li><span class="math-container">$\sum_{r} p(s^{\prime}, r \rvert s,a) =p(s^{\prime} \rvert s,a) $</span> (marginalization)</li>
  </ul>
  <p>In this form, as in equation \ref{2}, the value function can also be written in a different notation</p>
  <p><span class="math-container">\begin{align}
  v_{\pi}(s) 
  &amp;= 
  \sum_{a} \pi(a\rvert s)  \left[ R_{s}^a  + \gamma \sum_{s^{\prime}}P_{ss'}^a v_{\pi}(s^{\prime}) \right] \label{3}\tag{3}, \; \forall s \in \mathcal{S}
  \end{align}</span>
  where</p>
  <ul>
  <li><span class="math-container">$R_{s}^a = r(s, a)$</span></li>
  <li><span class="math-container">$P_{ss'}^a = p(s^{\prime} \rvert s,a)$</span></li>
  </ul>
  <p>We can still write equation \ref{3} in a &quot;simpler&quot; form as follows
  <span class="math-container">\begin{align}
  v_{\pi}(s) 
  &amp;= 
  \sum_{a} \pi(a\rvert s) R_{s}^a  + \gamma \sum_{s^{\prime}} \sum_{a} \pi(a\rvert s) P_{ss'}^a v_{\pi}(s^{\prime}) \\
  &amp;=
  R_{s}^\pi + \gamma \sum_{s^{\prime}} P_{ss'}^\pi v_{\pi}(s^{\prime}) 
  \label{4}\tag{4}, \; \forall s \in \mathcal{S}
  \end{align}</span>
  where</p>
  <ul>
  <li><span class="math-container">$\sum_{a} \pi(a\rvert s) R_{s}^a = R_{s}^\pi$</span></li>
  <li><span class="math-container">$\sum_{a}  \pi(a\rvert s) P_{ss'}^a = P_{ss'}^\pi$</span></li>
  </ul>
  <p>We can write the definition of the value function in \ref{4} in matrix form for all states <span class="math-container">$s \in \mathcal{S}$</span> as follows</p>
  <p><span class="math-container">\begin{align}
  \begin{bmatrix}
  v_\pi(1) \\
  \vdots \\
  v_\pi(n)
  \end{bmatrix}=
  \begin{bmatrix}
  {R}_1^\pi \\
  \vdots \\
  {R}_n^\pi
  \end{bmatrix}
  +\gamma
  \begin{bmatrix}
  {P}_{11}^\pi &amp; \dots &amp; {P}_{1n}^\pi\\
  \vdots &amp; \ddots &amp; \vdots\\
  {P}_{n1}^\pi &amp; \dots &amp; {P}_{nn}^\pi
  \end{bmatrix}
  \begin{bmatrix}
  v_\pi(1) \\
  \vdots \\
  v_\pi(n)
  \end{bmatrix}
  \tag{5}\label{5},
  \end{align}</span>
  which can be written in a more compact form as follows
  <span class="math-container">\begin{align}
  \mathbf{v} = \mathbf{r} + \gamma \mathbf{P}\mathbf{v} \tag{6}\label{6},
  \end{align}</span>
  which is a very compact form of the <a href="https://ai.stackexchange.com/a/11133/2444">Bellman equation</a> (which is a recursive equation: as you can notice, the <span class="math-container">$\mathbf{v}$</span> appears on the left and right of the equals sign) that represents the value function (i.e. the value function can be defined as a recursive equation).</p>
  <p>In equation \ref{5}, the <strong>unknowns</strong> are the <span class="math-container">$|\mathcal{S}| = n$</span> values of the value function <span class="math-container">$v$</span> and there are <span class="math-container">$n$</span> equations, so it should now be clear why we can solve this problem by solving a system of equations. Note that here it's assumed that <span class="math-container">$\pi$</span>, <span class="math-container">$r(s, a)$</span> and <span class="math-container">$p$</span>  are given and known, which, generally, is not the case, that's why we use algorithms like Q-learning.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-07T14:42:27.617Z
Answers.LastActivityDate: 2021-07-07T15:56:40.780Z
Answers.LastEditDate: 2021-07-07T15:56:40.780Z
Answers.UserDisplayName: nbro
Answers.Body: <p>Provided you have a finite number of states and actions, then there will not be an infinite number of terms. Therefore the state and action spaces need to be discrete and finite before the quote from the book applies.</p>
  <blockquote>
  <p>I am having a hard time understanding how one could solve this system of equations.</p>
  </blockquote>
  <p>There are a few techniques for solving simulteneous equations.</p>
  <p>However, what I would probably do is number all the state values from <span class="math-container">$v_1 = v_\pi(s_1)$</span> to <span class="math-container">$v_{N = |\mathcal{S}|} = v_\pi(s_N)$</span>, and write out each line in order:</p>
  <p><span class="math-container">$$v_1 = w_{1,1} v_1 + w_{1,2} v_2 + w_{1,3} v_3 + ... w_{1,N} v_N + r_1$$</span></p>
  <p>Where <span class="math-container">$r_1$</span> is a constant - it is the expected immediate reward when starting from state <span class="math-container">$1$</span>, but that is not important. It is the constant offset value you get from resolving the sum that is not multiplied by any <span class="math-container">$v_i$</span> unknown variable.</p>
  <p>You can discover the values of <span class="math-container">$w_{i,j}$</span> by expanding the sum in the Bellman equation for each state in turn.</p>
  <p>At that point you can build a matrix of the weights, and solve the linear equations <a href="https://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html" rel="nofollow noreferrer">by taking the inverse of the matrix</a>.</p>
  <blockquote>
  <p>[from comments] But if the game has no end then theoretically the sum of expected future rewards should be infinite.</p>
  </blockquote>
  <p>The time series definition of <span class="math-container">$v_{\pi}(s)$</span>:</p>
  <p><span class="math-container">$$v_{\pi}(s) = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s]$$</span></p>
  <p>does not appear in the Bellman equation used to establish the linear equations. This is the main benefit of the Bellman equation, it changes the infinite series view of returns into a set of relations that must hold between the value functions of each state.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-07T12:55:28.227Z
Answers.Text: But if the game has no end then theoretically the sum of expected future rewards should be infinite. I understand the we use a discount factor gamma to make this tractable, but in essence this is essentially an infinite sum? Or am I misunderstanding something?
Answers.UserDisplayName: phil
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-07T13:05:00.477Z
Answers.Text: @phil: The Bellman equation does not have any time series in it. That is the point of it, it relates values over single steps. I will try to add that to the answer later
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-07T11:57:41.087Z
Answers.LastActivityDate: 2021-07-07T20:44:01.360Z
Answers.LastEditDate: 2021-07-07T20:44:01.360Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am following the book &quot;Reinforcement Learning: An Introduction&quot; by Richard Sutton and Andrew Barto, and they give an example of a problem for which the value function can be computed explicitly by solving a system of <span class="math-container">$\lvert S \rvert $</span> equations that have <span class="math-container">$\lvert S \rvert $</span> unknowns. Each of these <span class="math-container">$\lvert S \rvert$</span> equations is given by:</p>
  <p><span class="math-container">$$v_{\pi}(s) = \sum_{a} \pi(a\rvert s) \sum_{s^{\prime}}\sum_{r} p(s^{\prime}, r \rvert s,a)[r + \gamma v_{\pi}(s^{\prime})] $$</span></p>
  <p>I am having a hard time understanding how one could solve this system of equations. It seems to me as if each equation consists of a summation of an infinite amount of terms and therefore one would not be able to analytically solve them. Could anyone offer any intuition as to how this system of equations could be explicitly solved?</p>
  
Tags: <reinforcement-learning><value-functions><bellman-equations><linear-algebra>
Title: How can we find the value function by solving a system of linear equations?
UserDisplayName: phil
ThreadText: # How can we find the value function by solving a system of linear equations?
  
  (Asked by: username_0 on 2021-07-07)
  
  I am following the book "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, and they give an example of a problem for which the value function can be computed explicitly by solving a system of $\lvert S \rvert $ equations that have $\lvert S \rvert $ unknowns. Each of these $\lvert S \rvert$ equations is given by:
  
  $$v\_{\pi}(s) = \sum\_{a} \pi(a\rvert s) \sum\_{s^{\prime}}\sum\_{r} p(s^{\prime}, r \rvert s,a)[r + \gamma v\_{\pi}(s^{\prime})] $$
  
  I am having a hard time understanding how one could solve this system of equations. It seems to me as if each equation consists of a summation of an infinite amount of terms and therefore one would not be able to analytically solve them. Could anyone offer any intuition as to how this system of equations could be explicitly solved?
  
  **Tags:** reinforcement-learning, value-functions, bellman-equations, linear-algebra
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-07-07. Score: 1 | Accepted answer
  
  First of all, we assume that we have a **finite MDP**, i.e. the set of states $\mathcal{S}$, the set of actions $\mathcal{A}$ and the set of rewards $\mathcal{R}$ all have a finite number of elements (I didn't think about how the explanations below would extend to other cases, but I suspect you will need differential equations).
  
  For simplicity, let's only consider the value function $v$ (as opposed to the state-action value function $q(s, a)$, but this also applies to $q$). The value function $v$ is defined for **all states**, i.e. it's a function of the form $v : \mathcal{S} \rightarrow \mathbb{R}$ or, with an alternative notation, $v(s), \forall s \in \mathcal{S}$. So, we can define this function as a vector $\mathbf{v}$ of dimension $|\mathcal{S}| = n$, i.e. $\mathbf{v} \in \mathbb{R}^{|\mathcal{S}|}$, where the $i$th element contains the value of the $i$th state (so we need a function that maps states to indices of this vector, but this is trivial).
  
  The fact that you can represent the value function, in this finite MDP, as a vector should already suggest that you can find this value function by solving a linear system of equations.
  
  However, let me show that by starting with the definition of the value function you also provided
  
  \begin{align}
  v\_{\pi}(s)
  &=
  \sum\_{a} \pi(a\rvert s) \sum\_{s^{\prime}}\sum\_{r} p(s^{\prime}, r \rvert s,a)[r + \gamma v\_{\pi}(s^{\prime})] \label{1}\tag{1}, \; \forall s \in \mathcal{S}
  \end{align}
  which can be expanded as follows
  \begin{align}
  v\_{\pi}(s)
  &=
  \sum\_{a} \pi(a\rvert s) \sum\_{s^{\prime}}\sum\_{r} \left[p(s^{\prime}, r \rvert s,a)r + \gamma p(s^{\prime}, r \rvert s,a) v\_{\pi}(s^{\prime}) \right] \\
  &=
  \sum\_{a} \pi(a\rvert s) \left[ \sum\_{r} \underbrace{\sum\_{s^{\prime}} p(s^{\prime}, r \rvert s,a)}\_{\text{Marginalization of }p \text{ over } s'}r + \gamma \sum\_{s^{\prime}} \underbrace{\sum\_{r} p(s^{\prime}, r \rvert s,a) }\_{\text{Marginalization of }p \text{ over } r} v\_{\pi}(s^{\prime}) \right]\\
  &=
  \sum\_{a} \pi(a\rvert s) \left[ \sum\_{r} p(r \rvert s, a)r + \gamma \sum\_{s^{\prime}}p(s^{\prime} \rvert s,a) v\_{\pi}(s^{\prime}) \right] \\
  &=
  \sum\_{a} \pi(a\rvert s) \left[ r(s, a) + \gamma \sum\_{s^{\prime}}p(s^{\prime} \rvert s,a) v\_{\pi}(s^{\prime}) \right] \label{2}\tag{2}, \; \forall s \in \mathcal{S}
  \end{align}
  where
  
  * $\sum\_{r} p(r \rvert s, a)r = r(s, a)$ (see [this](https://ai.stackexchange.com/a/24511/2444)).
  * $\sum\_{s^{\prime}}p(s^{\prime}, r \rvert s,a) = p(r \rvert s, a)$ ([marginalization](https://en.wikipedia.org/wiki/Marginal_distribution))
  * $\sum\_{r} p(s^{\prime}, r \rvert s,a) =p(s^{\prime} \rvert s,a) $ (marginalization)
  
  In this form, as in equation \ref{2}, the value function can also be written in a different notation
  
  \begin{align}
  v\_{\pi}(s)
  &=
  \sum\_{a} \pi(a\rvert s) \left[ R\_{s}^a + \gamma \sum\_{s^{\prime}}P\_{ss'}^a v\_{\pi}(s^{\prime}) \right] \label{3}\tag{3}, \; \forall s \in \mathcal{S}
  \end{align}
  where
  
  * $R\_{s}^a = r(s, a)$
  * $P\_{ss'}^a = p(s^{\prime} \rvert s,a)$
  
  We can still write equation \ref{3} in a "simpler" form as follows
  \begin{align}
  v\_{\pi}(s)
  &=
  \sum\_{a} \pi(a\rvert s) R\_{s}^a + \gamma \sum\_{s^{\prime}} \sum\_{a} \pi(a\rvert s) P\_{ss'}^a v\_{\pi}(s^{\prime}) \\
  &=
  R\_{s}^\pi + \gamma \sum\_{s^{\prime}} P\_{ss'}^\pi v\_{\pi}(s^{\prime})
  \label{4}\tag{4}, \; \forall s \in \mathcal{S}
  \end{align}
  where
  
  * $\sum\_{a} \pi(a\rvert s) R\_{s}^a = R\_{s}^\pi$
  * $\sum\_{a} \pi(a\rvert s) P\_{ss'}^a = P\_{ss'}^\pi$
  
  We can write the definition of the value function in \ref{4} in matrix form for all states $s \in \mathcal{S}$ as follows
  
  \begin{align}
  \begin{bmatrix}
  v\_\pi(1) \\
  \vdots \\
  v\_\pi(n)
  \end{bmatrix}=
  \begin{bmatrix}
  {R}\_1^\pi \\
  \vdots \\
  {R}\_n^\pi
  \end{bmatrix}
  +\gamma
  \begin{bmatrix}
  {P}\_{11}^\pi & \dots & {P}\_{1n}^\pi\\
  \vdots & \ddots & \vdots\\
  {P}\_{n1}^\pi & \dots & {P}\_{nn}^\pi
  \end{bmatrix}
  \begin{bmatrix}
  v\_\pi(1) \\
  \vdots \\
  v\_\pi(n)
  \end{bmatrix}
  \tag{5}\label{5},
  \end{align}
  which can be written in a more compact form as follows
  \begin{align}
  \mathbf{v} = \mathbf{r} + \gamma \mathbf{P}\mathbf{v} \tag{6}\label{6},
  \end{align}
  which is a very compact form of the [Bellman equation](https://ai.stackexchange.com/a/11133/2444) (which is a recursive equation: as you can notice, the $\mathbf{v}$ appears on the left and right of the equals sign) that represents the value function (i.e. the value function can be defined as a recursive equation).
  
  In equation \ref{5}, the **unknowns** are the $|\mathcal{S}| = n$ values of the value function $v$ and there are $n$ equations, so it should now be clear why we can solve this problem by solving a system of equations. Note that here it's assumed that $\pi$, $r(s, a)$ and $p$ are given and known, which, generally, is not the case, that's why we use algorithms like Q-learning.
  
  
  ---
  
  ### Answer by username_2 on 2021-07-07. Score: 3
  
  Provided you have a finite number of states and actions, then there will not be an infinite number of terms. Therefore the state and action spaces need to be discrete and finite before the quote from the book applies.
  
  > I am having a hard time understanding how one could solve this system of equations.
  
  There are a few techniques for solving simulteneous equations.
  
  However, what I would probably do is number all the state values from $v\_1 = v\_\pi(s\_1)$ to $v\_{N = |\mathcal{S}|} = v\_\pi(s\_N)$, and write out each line in order:
  
  $$v\_1 = w\_{1,1} v\_1 + w\_{1,2} v\_2 + w\_{1,3} v\_3 + ... w\_{1,N} v\_N + r\_1$$
  
  Where $r\_1$ is a constant - it is the expected immediate reward when starting from state $1$, but that is not important. It is the constant offset value you get from resolving the sum that is not multiplied by any $v\_i$ unknown variable.
  
  You can discover the values of $w\_{i,j}$ by expanding the sum in the Bellman equation for each state in turn.
  
  At that point you can build a matrix of the weights, and solve the linear equations [by taking the inverse of the matrix](https://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html).
  
  > [from comments] But if the game has no end then theoretically the sum of expected future rewards should be infinite.
  
  The time series definition of $v\_{\pi}(s)$:
  
  $$v\_{\pi}(s) = \mathbb{E}\_{\pi}[\sum\_{k=0}^{\infty} \gamma^k R\_{t+k+1} | S\_t = s]$$
  
  does not appear in the Bellman equation used to establish the linear equations. This is the main benefit of the Bellman equation, it changes the infinite series view of returns into a set of relations that must hold between the value functions of each state.
  
  > **Comments:**
  > **username_0**: But if the game has no end then theoretically the sum of expected future rewards should be infinite. I understand the we use a discount factor gamma to make this tractable, but in essence this is essentially an infinite sum? Or am I misunderstanding something?  
  > **username_2**: @username_0: The Bellman equation does not have any time series in it. That is the point of it, it relates values over single steps. I will try to add that to the answer later  
  
  ---
  
  