Bellman Equation
上一章[[强化学习入门]]

例子

• 如何选择最好的策略？如何描述？使用平均的return来表示
• 如何计算return？可以使用递归计算方式，即当前state得到的return依赖于其他state的return
  • Bootstrapping：从自己出发不断迭代得到的结果
  • $v=r+\gamma Pv$，将该述公式求解可以得到deterministic的bellman公式

状态价值State Value

• 状态价值：$$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$这是基于某个具体状态s得到的value，并且是由策略$\pi$决定的，其中$G_t$是每个路径的return
• return是在某一状态s下针对单个trajectory所求，state value是从某状态s出发的多个trajectory（若存在）得到的return的期望。

推导Bellman Equation

贝尔曼公式是用于计算状态价值的。
以下是比较简化的推导，可以不看，只看结论

针对一个随机的trajectory，可以求$G_t$，$$G_t=R_{t+1}+\gamma G_{t+1}$$
所以状态价值可以推导为
$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[G_t|S_t=s]\\ & =\mathbb{E}[R_{t+1}|S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]\end{array}$$
下面分析两个expectation，
第一个expectation代表immediate rewards的均值$$\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$$ 第二个expectation代表future rewards的均值$$\begin{array}{rl}\mathbb{E}[G_{t+1}|S_t=s]& =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }|s)\\ & =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|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|s)\end{array}$$第二行用到了Markov的无记忆性

最终可推导出bellman公式为$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}{v}_{\pi }(s^{\prime })\sum _{a}p(s^{\prime }|s,a)\pi (a|s)\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r+\gamma \sum _a\pi (a|s)\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }|s,a)\\ & =\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }|s,a)],\forall s\in S\end{array}$$bellman公式是一个公式集合（最后的$\forall$表示对状态空间的所有状态成立），表达了每个$v_{\pi }(s)$和所有其他state$s^{\prime }$的$v_{\pi }(s^{\prime })$之间的关系，可以使 用线性方程组求解得到每个state的状态价值。

Bellman Equation的矩阵-向量形式

实际就是对bellman公式的扩展改写为$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$的形式，再将每个状态都列出则得到一个线性方程组的矩阵形式。

Bellman Equation的求解

基于一个既定的policy，评价其state value称为policy evaluation，即评价一个policy的好坏。

1. 很明显可以直接得到闭式解$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$，但是计算消耗大，在state space较大时不适用
2. 迭代求解：先随机初始化一个$v_0$，使用$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$的形式进行迭代，当$k\to \infty$时，$v_k$将收敛到定值$v_{\pi }$。

Action Value

概念

在某状态下采取某action时得到的return的期望$q_{\pi }(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$.

1. 由此可以推出state value为$v_{\pi }(s)={\sum }_a\pi (a|s)q_{\pi }(s,a)$。从这一公式可以看出知道某一状态的action value可以求平均得到该状态的state value。
2. 与上面推导出的bellman 公式比较可以得出$$q_{\pi }(s,a)=\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }|s,a)$$从公式中可以看出只要知道每个状态的state value，就可以求出相应state下采取某一action的action value。

用途

action value的用处就是判断某一状态下采取哪个action最优。

计算

先计算state value，再计算action value；或者直接计算action value
下一章[[贝尔曼最优公式]]