Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-24T03:47:13.200Z
Answers.Text: why the limit given by applying the bellman optimal operator is the value function of the optimal policy?
Answers.UserDisplayName: piero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-02T05:35:01.930Z
Answers.Text: @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.
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-02T06:05:06.260Z
Answers.Text: Actually the domains of T is $\mathbb{R}^{S \times A} \rightarrow \mathbb{R}^{S \times A}$  where S = state space, A = action space.
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-10T04:57:41.727Z
Answers.LastActivityDate: 2020-08-12T17:40:35.970Z
Answers.LastEditDate: 2020-08-12T17:40:35.970Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-10T22:59:47.587Z
Comments.Text: 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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-14T19:34:46.973Z
Comments.Text: 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).
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><terminology><math><bellman-equations><bellman-operators>
Title: What is the Bellman operator in reinforcement learning?
UserDisplayName: nbro
ThreadText: # 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**: @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.  
  > **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.  
  
  ---
  
  