02 Bellman Equation

• One concept: state value

$$v_{\pi }(s)=\mathbb{E}[G_t\mid S_t=s]$$

• One tool: Bellman equation

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

Bellman Equation(贝尔曼公式)用一句话来描述

实际上就是描述了所有状态的状态值之间的关系。求解贝尔曼公式进而得到一个策略所对应的状态值的一个过程就叫做policy evaluation。

Outline

1. Motivating examples
2. State value
3. Derivation
4. Matrix-vector form
5. Solve the state values
6. Action value
7. Summary

Motivating examples

Calculating return is important to evaluate a policy. Return is the (discounted) sum of the rewards obtained along a trajectory

Let $v_i=v(s_i)$ denote the return obtained starting from $s_i(i=1,2,3,4)$

$$\begin{array}{rl}{v}_1& =r_1+\gamma r_2+{\gamma }^2{r}_3+\dots \\ v_2& =r_2+\gamma r_3+{\gamma }^2{r}_4+\dots \\ v_3& =r_3+\gamma r_4+{\gamma }^2{r}_1+\dots \\ v_4& =r_4+\gamma r_1+{\gamma }^2{r}_2+\dots \end{array}$$

Note that we can write it in this method:

$$\begin{array}{rl}{v}_1& =r_1+\gamma (r_2+\gamma r_3+\dots )=r_1+\gamma v_2\\ v_2& =r_2+\gamma (r_3+\gamma r_4+\dots )=r_2+\gamma v_3\\ v_3& =r_3+\gamma (r_4+\gamma r_1+\dots )=r_3+\gamma v_4\\ v_4& =r_4+\gamma (r_1+\gamma r_2+\dots )=r_4+\gamma v_1\end{array}$$

• The returns rely on each other. Bootstrapping!

Matrix-vector form:

$$\underset{\mathbf{v}}{\underbrace{\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}=\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]+\left[\begin{array}{c}\gamma v_2\\ \gamma v_3\\ \gamma v_4\\ \gamma v_1\end{array}\right]=\underset{\mathbf{r}}{\underbrace{\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]}}+\gamma \underset{\mathbf{P}}{\underbrace{\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]}}\underset{\mathbf{v}}{\underbrace{\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}$$ $$\mathbf{v}=\mathbf{r}+\gamma \mathbf{Pv}$$

Summary

• State value: $v_{\pi }(s)=\mathbb{E}[G_t\mid S_t=s]$
• Action value: $v_{\pi }(s)=\mathbb{E}[G_t\mid S_t=s,A_t=a]$
• The Bellman equation
  • elementwise form:
    • $v_{\pi }(s)={\sum }_a\pi (a\mid s)q_{\pi }(s,a)$
    • $q_{\pi }(s,a)={\sum }_{r}p(r\mid s,a)r+\gamma {\sum }_{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })$
  • matrix form:
    • $v_{\pi }=\pi @q_{\pi }$
    • $q_{\pi }=P_{r}R+\gamma P_s{v}_{\pi }$
  • See All in one
• Closed-form solution and iterative solution.

Later

Policy evaluation, widely used later

next⇒03 Bellman Optimality Equation