3 minute read

Bellman Equation 贝尔曼公式

## Motivating examples

在已知Policy的情况下计算Return，使用$v_i$代表从位置$s_i$开始的return之和

\[\begin{aligned} v_1 &= r_1 + \gamma r_2 + \gamma^2 r_3 + \dots = r_1 + \gamma v_2 \\ v_2 &= r_2 + \gamma r_3 + \gamma^2 r_4 + \dots = r_2 + \gamma v_3 \\ v_3 &= r_3 + \gamma r_4 + \gamma^2 r_1 + \dots = r_3 + \gamma v_4 \\ v_4 &= r_4 + \gamma r_1 + \gamma^2 r_2 + \dots = r_4 + \gamma v_1 \end{aligned}\]

求解线性方程组： \(\underbrace{ \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix} }_{\mathbf{v}} = \underbrace{ \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} }_{\mathbf{r}} + \begin{bmatrix} \gamma v_2 \\ \gamma v_3 \\ \gamma v_4 \\ \gamma v_1 \end{bmatrix} = \underbrace{ \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} }_{\mathbf{r}} + \gamma \underbrace{ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} }_{\mathbf{P}} \underbrace{ \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \end{bmatrix} }_{\mathbf{v}}\) 得到 \(\mathbf{v} = \mathbf{r} + \gamma \mathbf{Pv}\)

State value

Probabilty distributions

  • 在某状态下执行某动作$S_t \to A_t$ 由 $\pi (A_t = a S_t = s)$决定
  • 在某状态下执行某动作获得某回报的概率$S_t, A_t \to R_{t+1}$由 $p(R_{t+1} = r S_t = s, A_t = a)$决定
  • 在某状态下执行某动作后变为某状态$S_t, A_t \to S_{t+1}$由 $p(S_{t+1} = s’ S_t = s, A_t = a)$决定

Discounted Return

用$G_t$来表示一系列随机动作获得的随机回报的return

\[G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + \dots\]
  • $G_T$是随机变量，因为$R_t$是随机变量

State value

State value是$G_t$的期望值, 即在状态 $s$ 下执行策略（policy） $\pi$获得的return为$ G_t$ 的概率

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

return 和 state value的区别：

  • return是对一条trajectory而言，过程是确定的

  • state value是对一个状态出发的所有trajectory的期望值（平均值），过程会出现随机性

Bellman Equation

考虑一个从$S_t$ 出发的随机的trajectory

\[\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \cdots) \\ &= R_{t+1} + \gamma G_{t+1} \end{aligned}\]

由此可以由定义到的：

\[\begin{aligned} 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{aligned}\]
  1. 第一项：$\mathbb{E}[R_{t+1} \mid S_t = s]$
\[\begin{aligned} \mathbb{E}[R_{t+1}|S_t=s] &= \sum_a \pi(a|s)\mathbb{E}[R_{t+1} |S_t = s, A_t = a] \\ &= \sum_a \pi(a|s)\sum_r p(r|s, a)r \end{aligned}\]
  1. 第二项：$\mathbb{E}[G_{t+1} S_t = s]$
\[\begin{aligned} \mathbb{E}[R_{t+1}|S_t=s] &= \sum_{s'} \mathbb{E}(G_{t+1}|S_t = s, S_{t+1}=s')p(s'|s) \\ &= \sum_{s'} \mathbb{E}(G_{t+1}|S_{t+1}=s')p(s'|s) \\ &= \sum_{s'} v_\pi(s')p(s'|s) \\ &= \sum_{s'} v_\pi(s')\sum_a p(s'|s,a)\pi(a|s) \end{aligned}\]

由此，可以得到Bellman equation： \(\begin{aligned} {\color{red}{v_\pi(s)}} &= \mathbb{E}[R_{t+1}|S_t=s] + \gamma \mathbb{E}[G_{t+1}|S_t=s] \\ &= \underbrace{\sum_a\pi(a|s)\sum_rp(r|s,a)r}_{\text{mean of immediate rewards}} + \underbrace{\gamma \sum_a \pi (a|s) \sum_{s'} p(s'|s,a)v_\pi (s')}_{\text{mean of future rewards}} \\ &= \sum_a \pi (a|s) \left [ \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a) {\color{red}{v_\pi(s')}} \right ] , \forall s \in \mathcal{S} \end{aligned}\)

  • 其中的$v_\pi(s)$ 和$v_\pi (s’)$ 是需要计算的，由多个式子联立求解
  • Bellman equation是依赖于policy $\pi (a s)$的。求解式子被称为policy evaluation，评价其好坏
  • $p(r s,a)$和$p(s’ s,a)$ 代表dynamic model，取决于model是否已知

具体例子见：Bellman equation: Derivation（贝尔曼公式详细推导）最后部分

Matrix- vector form 矩阵向量形式

贝尔曼公式： \({\color{red}{v_\pi(s)}} = \sum_a \pi (a|s) \left [ \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a) {\color{red}{v_\pi(s')}} \right ]\) 重新组合公式，得到 \(v_\pi(s) = r_\pi (s) + \gamma \sum_{s'} p_\pi (s'|s,a) v_\pi(s')\) 其中： \(r_\pi (s) = \sum_a \pi (a|s)\sum_r p(r|s,a)r, \qquad p_\pi (s'|s) = \sum_a\pi (a|s) p(s'|s,a)\) 将所有状态放在一起并给定下标$i=1,2,3,\dots,n$： \(v_\pi(s_i) = r_\pi (s_i) + \gamma \sum_{s_j} p_\pi (s_j|s_i) v_\pi(s_j)\) 再将其写作向量的形式： \(v_\pi = r_\pi + \gamma P_\pi v_\pi\) 其中：

  • $v_\pi = \left [ v_\pi (s_1), \dots, v_\pi (s_n) \right ]^T \in \mathbb{R}^n$

  • $r_\pi = \left [ r_\pi (s_1), \dots, r_\pi (s_n) \right ] ^ T \in \mathbb{R}^n$
  • $P_\pi \in \mathbb{R}^n$，其中，$[P_\pi]{ij} = p\pi (s_j s_i)$

求解方法：

  1. 矩阵求逆，求解线性方程组
  2. 迭代法：任意取$v_0$ ，带入$v_{k+1} = r_\pi + \gamma P_\pi v_k$，可以证明$v_k \to v_\pi, k\to \infty$.

Action Value

Action value指从当前状态$s$出发，执行动作$a$后所得到的return的平均值

\[q_\pi (s,a) = \mathbb{E}[G_t | S_t = s, A_t = a]\]
  • $q_\pi (s,a)$依赖于策略$\pi$

State value 和 Action value 的关系： \(\underbrace{\mathbb{E}(G_t|S_t = s)}_{v_\pi (s)} = \sum_a \underbrace{\mathbb{E}(G_t|S_t = s, A_t = a)}_{q_\pi (s, a)} \pi (a|s)\) 因此： \({\color{red}{v_\pi (s)}} = \sum_a \pi (a|s) {\color{red}{q_\pi (s,a)}}\) 对应Bellman equation，可知： \(v_\pi(s) = \sum_a \pi (a|s) \underbrace{\left [ \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a) v_\pi(s') \right ]}_{\color{red}{q_\pi (s,a)}}\) 因此，可得： \({\color{red}{q_\pi (s,a)}} = \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a) \color{red}{v_\pi(s')}\)

  • 若对于一个状态，知道了所有的action value，求平均即可得到这个状态的state value
  • 若知道了所有状态的state value，即可求出所有的action value

You May Also Enjoy