

![0_image_0.png](0_image_0.png)

policy π **is given by:**

$${\mathcal{V}}_{\pi}(\mathbf{x})=E_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R\left(\mathbf{X}^{(t)},\pi(\mathbf{X}^{(t)})\right)\right]\mathbf{X}^{(0)}=\mathbf{x}\right],$$

where X(t)is a random variable representing the state of the system after t **steps. In our**
running example, the value function represents how much money the SysAdmin expects to collect if she starts acting according to π when the network is at state x**. The value function**
for a fixed policy is the fixed point of a set of linear equations **that define the value of a** state in terms of the value of its possible successor states. **More formally, we define:**
Definition 2.2 The DP operator, Tπ, for a stationary policy π is:

$${\mathcal{T}}_{\pi}{\mathcal{V}}(\mathbf{x})=R(\mathbf{x},\pi(\mathbf{x}))+\gamma\sum_{\mathbf{x}^{\prime}}P(\mathbf{x}^{\prime}\mid\mathbf{x},\pi(\mathbf{x})){\mathcal{V}}(\mathbf{x}^{\prime}).$$
$$e y\ \pi,\ {\mathcal V}_{\pi},\ i s\ t h e$$

The value function of policy π, Vπ, is the fixed point of the Tπ **operator:** Vπ = TπVπ.

The optimal value function V
∗ **describes the optimal value the agent can achieve for**
each starting state. V
∗is also defined by a set of non-linear equations. In this case, the value of a state must be the maximal expected value achievable by any policy starting at that state. More precisely, we define:
Definition 2.3 The **Bellman operator**, T
∗**, is:**

$${\mathcal{T}}^{*}{\mathcal{V}}({\mathbf{x}})=\operatorname*{max}_{a}[R({\mathbf{x}},a)+\gamma\sum_{{\mathbf{x}}^{\prime}}P({\mathbf{x}}^{\prime}\mid{\mathbf{x}},a){\mathcal{V}}({\mathbf{x}}^{\prime})].$$
_The optimal value function $\mathcal{V}^{*}$ is the fixed point of $\mathcal{T}^{*}\colon\mathcal{V}^{*}=\mathcal{T}^{*}\mathcal{V}^{*}$._
For any value function V**, we can define the policy obtained by acting greedily relative**
to V**. In other words, at each state, the agent takes the action that maximizes the one-step**