<p>The notation I'll be using is from <a href="https://web.archive.org/web/20171118120953/http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf" rel="noreferrer">two</a> <a href="https://web.archive.org/web/20181127083007/http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/DP.pdf" rel="noreferrer">different</a> lectures by David Silver and is also informed by <a href="http://chercheurs.lille.inria.fr/%7Eghavamza/RL-EC-Lille/Lecture3.pdf" rel="noreferrer">these slides</a>.</p>
<p>The expected Bellman equation is
<span class="math-container">$$v_\pi(s) = \sum_{a\in \cal{A}} \pi(a|s) \left(\cal{R}_s^a + \gamma\sum_{s' \in \cal{S}} \cal{P}_{ss'}^a v_\pi(s')\right) \tag 1$$</span></p>
<p>If we let
<span class="math-container">$$\cal{P}_{ss'}^\pi = \sum\limits_{a \in \cal{A}} \pi(a|s)\cal{P}_{ss'}^a \tag 2$$</span>
and
<span class="math-container">$$\cal{R}_{s}^\pi = \sum\limits_{a \in \cal{A}} \pi(a|s)\cal{R}_{s}^a \tag 3$$</span>
then we can rewrite <span class="math-container">$(1)$</span> as</p>
<p><span class="math-container">$$v_\pi(s) = \cal{R}_s^\pi + \gamma\sum_{s' \in \cal{S}} \cal{P}_{ss'}^\pi v_\pi(s') \tag 4$$</span></p>
<p>This can be written in matrix form</p>
<p><span class="math-container">$$\left.
\begin{bmatrix}
v_\pi(1) \\
\vdots \\
v_\pi(n)
\end{bmatrix}=
\begin{bmatrix}
\cal{R}_1^\pi \\
\vdots \\
\cal{R}_n^\pi
\end{bmatrix}
+\gamma
\begin{bmatrix}
\cal{P}_{11}^\pi &amp; \dots &amp; \cal{P}_{1n}^\pi\\
\vdots &amp; \ddots &amp; \vdots\\
\cal{P}_{n1}^\pi &amp; \dots &amp; \cal{P}_{nn}^\pi
\end{bmatrix}
\begin{bmatrix}
v_\pi(1) \\
\vdots \\
v_\pi(n)
\end{bmatrix}
\right. \tag 5$$</span></p>
<p>Or, more compactly,</p>
<p><span class="math-container">$$v_\pi = \cal{R}^\pi + \gamma \cal{P}^\pi v_\pi \tag 6$$</span></p>
<p>Notice that both sides of <span class="math-container">$(6)$</span> are <span class="math-container">$n$</span>-dimensional vectors. Here <span class="math-container">$n=|\cal{S}|$</span> is the size of the state space. We can then define an operator <span class="math-container">$\cal{T}^\pi:\mathbb{R}^n\to\mathbb{R}^n$</span> as</p>
<p><span class="math-container">$$\cal{T^\pi}(v) = \cal{R}^\pi + \gamma \cal{P}^\pi v \tag 7$$</span></p>
<p>for any <span class="math-container">$v\in \mathbb{R}^n$</span>. This is the expected Bellman operator.</p>
<p>Similarly, you can rewrite the Bellman optimality equation</p>
<p><span class="math-container">$$v_*(s) = \max_{a\in\cal{A}} \left(\cal{R}_s^a + \gamma\sum_{s' \in \cal{S}} \cal{P}_{ss'}^a v_*(s')\right) \tag 8$$</span></p>
<p>as the Bellman optimality operator</p>
<p><span class="math-container">$$\cal{T^*}(v) = \max_{a\in\cal{A}} \left(\cal{R}^a + \gamma \cal{P}^a v\right) \tag 9$$</span></p>
<p>The Bellman operators are &quot;operators&quot; in that they are mappings from one point to another within the vector space of state values, <span class="math-container">$\mathbb{R}^n$</span>.</p>
<p>Rewriting the Bellman equations as operators is useful for proving that certain dynamic programming algorithms (e.g. policy iteration, value iteration) converge to a unique fixed point. This usefulness comes in the form of a body of existing work in operator theory, which allows us to make use of special properties of the Bellman operators.</p>
<p>Specifically, the fact that the Bellman operators are <a href="https://en.wikipedia.org/wiki/Contraction_%28operator_theory%29" rel="noreferrer">contractions</a> gives the useful results that, for any policy <span class="math-container">$\pi$</span> and any initial vector <span class="math-container">$v$</span>,</p>
<p><span class="math-container">$$\lim_{k\to\infty}(\cal{T}^\pi)^k v = v_\pi \tag{10}$$</span></p>
<p><span class="math-container">$$\lim_{k\to\infty}(\cal{T}^*)^k v = v_* \tag{11}$$</span></p>
<p>where <span class="math-container">$v_\pi$</span> is the value of policy <span class="math-container">$\pi$</span> and <span class="math-container">$v_*$</span> is the value of an optimal policy <span class="math-container">$\pi^*$</span>. The proof is due to the <a href="https://en.wikipedia.org/wiki/Banach_fixed-point_theorem" rel="noreferrer">contraction mapping theorem</a>.</p>

CC BY-SA 4.0
2023-09-24T03:47:13.200Z
why the limit given by applying the bellman optimal operator is the value function of the optimal policy?
piero
CC BY-SA 4.0
2023-12-02T05:35:01.930Z
@piero:  good question.  The operator T acts on the Value function V(s) which is itself a function over states.  The operator T acting on V gives the V of the *next* state.  If T keeps acting on an initial V ad infinitum, then it gives the V of the "final state", which is the end value of the entire policy.
Yan King Yin
CC BY-SA 4.0
2023-12-02T06:05:06.260Z
Actually the domains of T is $\mathbb{R}^{S \times A} \rightarrow \mathbb{R}^{S \times A}$  where S = state space, A = action space.
Yan King Yin
CC BY-SA 4.0
2019-03-10T04:57:41.727Z
2020-08-12T17:40:35.970Z
2020-08-12T17:40:35.970Z
Philip Raeisghasem
<p>In mathematics, the word <a href="https://en.wikipedia.org/wiki/Operator_(mathematics)" rel="noreferrer">operator</a> can refer to several distinct but related concepts. An operator can be defined as a function between two vector spaces, it can be defined as a function where the domain and the codomain are the same, or it can be defined as a function from functions (which are vectors) to other functions (for example, the <a href="https://en.wikipedia.org/wiki/Differential_operator" rel="noreferrer">differential operator</a>), that is, a high-order function (if you are familiar with functional programming).</p>
<ul>
<li>What is the <em>Bellman operator</em> in reinforcement learning (RL)?</li>
<li>Why do we even need it?</li>
<li>How is the Bellman operator related to the Bellman equations in RL?</li>
</ul>

CC BY-SA 4.0
2019-03-10T22:59:47.587Z
A few papers related to this topic are _[Feature-Based Methods for Large Scale Dynamic Programming](http://www.mit.edu/people/jnt/Papers/J060-96-bvr-feature.pdf)_ (by John N. Tsitsiklis and  Benjamin Van Roy, 1996), _[An Analysis of Temporal-Difference Learning with Function Approximation](http://www.mit.edu/~jnt/Papers/J063-97-bvr-td.pdf)_ (by John N. Tsitsiklis and  Benjamin Van Roy, 1997) and _[Least-Squares Policy Iteration](http://www.jmlr.org/papers/volume4/lagoudakis03a/lagoudakis03a.pdf)_ (by Michail G. Lagoudakis and Ronald Parr, 2003).
nbro
CC BY-SA 4.0
2019-03-14T19:34:46.973Z
A few more related papers that I found are [Generalized Markov Decision Processes: Dynamic-programming and Reinforcement-learning Algorithms](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1316&rep=rep1&type=pdf) (by Csaba Szepesvári and Michael L. Littman, 1997) and [$\epsilon$-MDPs: Learning in Varying Environments](http://www.jmlr.org/papers/volume3/szita02a/szita02a.pdf) (by István Szita, Bálint Takács, András Lörincz, 2002).
nbro
<reinforcement-learning><terminology><math><bellman-equations><bellman-operators>
What is the Bellman operator in reinforcement learning?
nbro
# What is the Bellman operator in reinforcement learning?

(Asked by: username_0 on 2019-03-06)

In mathematics, the word [operator](https://en.wikipedia.org/wiki/Operator_(mathematics)) can refer to several distinct but related concepts. An operator can be defined as a function between two vector spaces, it can be defined as a function where the domain and the codomain are the same, or it can be defined as a function from functions (which are vectors) to other functions (for example, the [differential operator](https://en.wikipedia.org/wiki/Differential_operator)), that is, a high-order function (if you are familiar with functional programming).

* What is the *Bellman operator* in reinforcement learning (RL)?
* Why do we even need it?
* How is the Bellman operator related to the Bellman equations in RL?

**Tags:** reinforcement-learning, terminology, math, bellman-equations, bellman-operators

> **Comments:**
> **username_0**: A few papers related to this topic are _[Feature-Based Methods for Large Scale Dynamic Programming](http://www.mit.edu/people/jnt/Papers/J060-96-bvr-feature.pdf)_ (by John N. Tsitsiklis and  Benjamin Van Roy, 1996), _[An Analysis of Temporal-Difference Learning with Function Approximation](http://www.mit.edu/~jnt/Papers/J063-97-bvr-td.pdf)_ (by John N. Tsitsiklis and  Benjamin Van Roy, 1997) and _[Least-Squares Policy Iteration](http://www.jmlr.org/papers/volume4/lagoudakis03a/lagoudakis03a.pdf)_ (by Michail G. Lagoudakis and Ronald Parr, 2003).  
> **username_0**: A few more related papers that I found are [Generalized Markov Decision Processes: Dynamic-programming and Reinforcement-learning Algorithms](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1316&rep=rep1&type=pdf) (by Csaba Szepesvári and Michael L. Littman, 1997) and [$\epsilon$-MDPs: Learning in Varying Environments](http://www.jmlr.org/papers/volume3/szita02a/szita02a.pdf) (by István Szita, Bálint Takács, András Lörincz, 2002).  

---

## 1 answers

### Answer by username_1 on 2019-03-10. Score: 32 | Accepted answer

The notation I'll be using is from [two](https://web.archive.org/web/20171118120953/http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf) [different](https://web.archive.org/web/20181127083007/http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/DP.pdf) lectures by David Silver and is also informed by [these slides](http://chercheurs.lille.inria.fr/%7Eghavamza/RL-EC-Lille/Lecture3.pdf).

The expected Bellman equation is
$$v\_\pi(s) = \sum\_{a\in \cal{A}} \pi(a|s) \left(\cal{R}\_s^a + \gamma\sum\_{s' \in \cal{S}} \cal{P}\_{ss'}^a v\_\pi(s')\right) \tag 1$$

If we let
$$\cal{P}\_{ss'}^\pi = \sum\limits\_{a \in \cal{A}} \pi(a|s)\cal{P}\_{ss'}^a \tag 2$$
and
$$\cal{R}\_{s}^\pi = \sum\limits\_{a \in \cal{A}} \pi(a|s)\cal{R}\_{s}^a \tag 3$$
then we can rewrite $(1)$ as

$$v\_\pi(s) = \cal{R}\_s^\pi + \gamma\sum\_{s' \in \cal{S}} \cal{P}\_{ss'}^\pi v\_\pi(s') \tag 4$$

This can be written in matrix form

$$\left.
\begin{bmatrix}
v\_\pi(1) \\
\vdots \\
v\_\pi(n)
\end{bmatrix}=
\begin{bmatrix}
\cal{R}\_1^\pi \\
\vdots \\
\cal{R}\_n^\pi
\end{bmatrix}
+\gamma
\begin{bmatrix}
\cal{P}\_{11}^\pi & \dots & \cal{P}\_{1n}^\pi\\
\vdots & \ddots & \vdots\\
\cal{P}\_{n1}^\pi & \dots & \cal{P}\_{nn}^\pi
\end{bmatrix}
\begin{bmatrix}
v\_\pi(1) \\
\vdots \\
v\_\pi(n)
\end{bmatrix}
\right. \tag 5$$

Or, more compactly,

$$v\_\pi = \cal{R}^\pi + \gamma \cal{P}^\pi v\_\pi \tag 6$$

Notice that both sides of $(6)$ are $n$-dimensional vectors. Here $n=|\cal{S}|$ is the size of the state space. We can then define an operator $\cal{T}^\pi:\mathbb{R}^n\to\mathbb{R}^n$ as

$$\cal{T^\pi}(v) = \cal{R}^\pi + \gamma \cal{P}^\pi v \tag 7$$

for any $v\in \mathbb{R}^n$. This is the expected Bellman operator.

Similarly, you can rewrite the Bellman optimality equation

$$v\_\*(s) = \max\_{a\in\cal{A}} \left(\cal{R}\_s^a + \gamma\sum\_{s' \in \cal{S}} \cal{P}\_{ss'}^a v\_\*(s')\right) \tag 8$$

as the Bellman optimality operator

$$\cal{T^\*}(v) = \max\_{a\in\cal{A}} \left(\cal{R}^a + \gamma \cal{P}^a v\right) \tag 9$$

The Bellman operators are "operators" in that they are mappings from one point to another within the vector space of state values, $\mathbb{R}^n$.

Rewriting the Bellman equations as operators is useful for proving that certain dynamic programming algorithms (e.g. policy iteration, value iteration) converge to a unique fixed point. This usefulness comes in the form of a body of existing work in operator theory, which allows us to make use of special properties of the Bellman operators.

Specifically, the fact that the Bellman operators are [contractions](https://en.wikipedia.org/wiki/Contraction_%28operator_theory%29) gives the useful results that, for any policy $\pi$ and any initial vector $v$,

$$\lim\_{k\to\infty}(\cal{T}^\pi)^k v = v\_\pi \tag{10}$$

$$\lim\_{k\to\infty}(\cal{T}^\*)^k v = v\_\* \tag{11}$$

where $v\_\pi$ is the value of policy $\pi$ and $v\_\*$ is the value of an optimal policy $\pi^\*$. The proof is due to the [contraction mapping theorem](https://en.wikipedia.org/wiki/Banach_fixed-point_theorem).

> **Comments:**
> **username_2**: why the limit given by applying the bellman optimal operator is the value function of the optimal policy?  
> **username_3**: @username_2:  good question.  The operator T acts on the Value function V(s) which is itself a function over states.  The operator T acting on V gives the V of the *next* state.  If T keeps acting on an initial V ad infinitum, then it gives the V of the "final state", which is the end value of the entire policy.  
> **username_3**: Actually the domains of T is $\mathbb{R}^{S \times A} \rightarrow \mathbb{R}^{S \times A}$  where S = state space, A = action space.  

---

