BE Bellman Equation

Bellman Equation

Derivation

Consider a random trajectory:

$$S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}\stackrel{A_{t+1}}{\to }{R}_{t+2},S_{t+2}\stackrel{A_{t+2}}{\to }{R}_{t+3},\dots$$

The return $G_t$ can be written as:

$$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots ,\\ & =R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\dots ),\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$

Then state value will be:

$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[G_t\mid S_t=s],\\ & =\mathbb{E}[R_{t+1}+\gamma G_{t+1}\mid S_t=s],\\ & =\mathbb{E}[R_{t+1}\mid S_t=s]+\gamma \mathbb{E}[G_{t+1}\mid S_t=s]\end{array}$$

• the $\mathbb{E}$ is the mean of immediate rewards
• the $\mathbb{E}$ is the mean of future rewards

First we calculate the first term $\mathbb{E}$:

$$\begin{array}{rl}\mathbb{E}[R_{t+1}\mid S_t=s]& =\sum _a\pi (a\mid s)\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a],\\ & =\sum _a\pi (a\mid s)\sum _{r}p(r\mid s,a)r\end{array}$$

• the $\mathbb{E}$ consider all the reward $r$ it will get when take such action $a$ at state $s$

Then we calculate the second term $\mathbb{E}$:

$$\begin{array}{rl}\mathbb{E}[G_{t+1}\mid S_t=s]& =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}\mid S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }|s),\\ & =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}\mid S_{t+1}=s^{\prime }]p(s^{\prime }|s),\\ & =\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }|s),\\ & =\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })\sum _{a}p(s^{\prime }|s,a)\pi (a\mid s),\\ & =\sum _{s^{\prime }}\sum _a\pi (a\mid s)p(s^{\prime }|s,a)v_{\pi }(s^{\prime }),\\ & =\sum _{s^{\prime }}\sum _a\pi (a\mid s)p(s^{\prime }|s,a)v_{\pi }(s^{\prime }),\\ & =\sum _a\pi (a\mid s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime }).\end{array}$$

• the $\mathbb{E}$ consider the markov memoryless property here
• the $p(s^{\prime }|s)$ consider all the case of action here, so it can expand like this
• the ${\sum }_a\pi (a\mid s)$ is inrelevant with ${\sum }_{s^{\prime }}$ so we exchange their order here

Therefore we have:

$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[R_{t+1}\mid S_t=s]+\gamma \mathbb{E}[G_{t+1}\mid S_t=s],\\ & =\sum _a\pi (a\mid s)\sum _{r}p(r\mid s,a)r+\gamma \sum _a\pi (a\mid s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime }),\\ & =\sum _a\pi (a\mid s)\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\right],\forall s\in \mathcal{S}.\end{array}$$

• $v_{\pi }(s)$ and $v_{\pi }(s^{\prime })$ are state values to be caculated. Bootstrapping!
• $\pi (a\mid s)$ are given policy. Solving this equation is called policy evaluation.
• $p(r\mid s,a)r$ and $p(s^{\prime }|s,a)$ represent the dynamic model.

假设我们不知道这个dynamic model我们也依然可以求出state value，这就是model-free的算法

Exercise

• write out the Bellman equations for each state
• solve the state values

$$\begin{array}{rl}{v}_{\pi }(s_1)& =0.5[-1+\gamma v_{\pi }(s_2)]+0.5[0+\gamma v_{\pi }(s_3)]\\ v_{\pi }(s_2)& =1+\gamma v_{\pi }(s_4)\\ v_{\pi }(s_3)& =1+\gamma v_{\pi }(s_4)\\ v_{\pi }(s_4)& =1+\gamma v_{\pi }(s_4)\end{array}$$

Solve the above quations from the last to the first:

$$\begin{array}{rl}{v}_{\pi }(s_4)& =\frac{1}{1-\gamma }\\ v_{\pi }(s_3)& =\frac{1}{1-\gamma }\\ v_{\pi }(s_2)& =\frac{1}{1-\gamma }\\ v_{\pi }(s_1)& =-0.5+\frac{\gamma }{1-\gamma }\end{array}$$

Matrix-vector form

Recall that:

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _a\pi (a\mid s)\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\right],\\ & =\sum _a\pi (a\mid s)\sum _{r}p(r\mid s,a)r+\gamma \sum _a\pi (a\mid s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime }),\\ & =r_{\pi }(s)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s)v_{\pi }(s^{\prime }).\end{array}$$

• $r_{\pi }(s)=\mathbb{E}[R_{t+1}\mid S_t=s]$
• the second term of this formula recalls the third line of this derivation

Bellman Equation拆解成三条式子来记忆

$$\begin{array}{rl}{v}_{\pi }(s)& =r_{\pi }(s)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s)v_{\pi }(s^{\prime })\\ r_{\pi }(s)& \triangleq \sum _a\pi (a|s)\sum _{r}p(r|s,a)r\\ p_{\pi }(s^{\prime }|s)& \triangleq \sum _a\pi (a|s)p(s^{\prime }|s,a)\end{array}$$

Matrix form:

$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

where

• $v_{\pi }=[v_{\pi }(s_1),v_{\pi }(s_2),\dots ,v_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• $r_{\pi }=[r_{\pi }(s_1),r_{\pi }(s_2),\dots ,r_{\pi }(s_n){]}^T\in {\mathbb{R}}^n$
• $P_{\pi }\in {\mathbb{R}}^{n\times n}$, where $[P_{\pi }{]}_{ij}=p_{\pi }(s_j\mid s_i)={\sum }_a\pi (a\mid s_i)p(s_j\mid s_i,a)$
  • also called state transition matrix

$r_{\pi }(s)$ 和 $P_{\pi }$ 的表达式可以写成矩阵形式吗？

See Probability&Matrix.

Solve the state values

Why to solve state value

• Given a policy, finding out the corresponding state value is called $\text{policy evaluation}$. It is fundermental problem in RL. It is the foundation to find better policies.
• It is important to understand how to solve the Bellman equation.

• The closed-form solution:

$$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

• The iterative solution to approx the fix point

$$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$$

For detail, see Proof.