强化学习的数学原理-02贝尔曼公式

目录

• Motivating examples
• state value
• Bellman equation
• Matrix-vector form
• Action value
• summary

Motivating examples

一个核心概念：state value

一个基本的工具：Bellman equation

为什么return是重要的？

return可以用来评估policy

下面计算3个例子

计算return的方法:

第一种方法:(by definition|通过定义)

用\(v_i\)表示从\(s_i\)开始得到的return

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

第二种方法:

\[\begin{align*} v_1 &= r_1 + \gamma r_2 + \gamma^2 r_3 + ... \\&= r_1 + \gamma(r_2 + \gamma r_3 + ...) \\ &= r_1 + \gamma v_2 \end{align*} \]

其他式子依次类推

上面的式子从直观上讲,就是从\(s_1\)跳到\(s_2\)

然后可以发现return之间彼此依赖,一个return会依赖于其他return,这种想法是Bootstrapping

上面的式子是有循环依赖的,如何解决上面的式子.

先把上面的式子写成矩阵形式

然后再把上面的式子写成一个更简化的形式就是:

\[\begin{align*} \bm{v} &= \bm{r} + \gamma \bm{P} \bm{v} \\\bm{v}(\bm{I} - \gamma \bm{P}) &= \bm{r} \\\bm{v} &= \bm{r}{(\bm{I} - \gamma \bm{P})}^{-1} \\\end{align*} \]

于是就求出了v

\[\bm{v} = \bm{r} + \gamma \bm{P} \bm{v} \]

这个就是贝尔曼公式,只不过是对于确定问题的.

state value

\[S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \]

• \(t,t+1\):指的是具体的时刻
• \(S_t\):指的是t时刻的状态
• \(A_t\):在t时刻采取的action
• \(R_{t+1}\):在采取\(A_t\)后得到的reward
• \(S_{t+1}\):在采取\(A_t\)转移到的状态

上面的\(R_{t+1}\)也可以写成\(R_t\),但一般写成\(R_{t+1}\),理解其含义即可.

注意上面的\(S_{t+1},A_t,R_{t+1}\)都是大写,这表示这些变量都是随机变量(random varibles),我们可以对这些随机变量做一些操作如:期望(Expection)

所有这些跳跃都是由\(probability distributions\)

• \(S_t \rightarrow A_t\)是由\(\pi(A_t=a|S_t=s)\)
• \(S_t,A_t \rightarrow R_{t+1}\)是由\(p(R_{t+1}=r|S_t=s,A_t=a)\)
• \(S_t,A_t \rightarrow S_{t+1}\)是由\(p(S_{t+1}=s^{'}|S_t=s,A_t=a)\)

把上面单步的操作推广就可以得到多步的操作(multi-step trajectory)

\[S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \xrightarrow{A_{t+1}} R_{t+2}, S_{t+2} \xrightarrow{A_{t+2}} R_{t+3}, ... \]

上面的trajectory可以求discounted return

\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + ... \]

• $ \gamma \in [0,1)$ 是一个折扣率
• \(G_t是一个随机变量,因为R_{t},R_{t+1}\)是随机变量

在有了上面的铺垫之后就可定义\(state \quad value\)了

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

state value实际上就是对\(G_t\)求期望,state value全称是叫state value function

• 对于state value,他是s的函数
• state value是策略的函数,可以这样写\(v(s,\pi)和v_{\pi}(s)\)是等价的,为了简单起见用后面的形式

return和state value的区别,return是针对单个tragectory而言的,而state是针对多个trajectory而言的,如果从一个状态出发可以得到多个trajectory那么return和state value是有区别的,如果从一个状态出发得到的trajectory是确定的,那么return和state value是没有区别的.

Bellman equation

上面说了\(state \quad value\)的定义,下面就是要说明如何计算\(state \quad value\),计算\(state value\)的工具就是贝尔曼公式

用一句话描述贝尔曼公式的话就是它描述了不同状态的\(state \quad value\)之间的关系

首先考虑一个trajectory

\[S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \xrightarrow{A_{t+1}} R_{t+2}, S_{t+2} \xrightarrow{A_{t+2}} R_{t+3}, ... \]

然后可以计算\(G_t\)

\[\begin{align*} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + ... \\&= R_{t+1} + \gamma G_{t+1} \end{align*} \]

下面是state value的定义

\[\begin{align*} 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{align*} \]

下面就是分别分析这两部分,计算出这两部分的形式,于是就能得到贝尔曼公式.

首先分析计算第一部分:

\[\begin{align*} \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{align*} \]

第一部分就是能得到的immediate reward的期望(expectation)

然后分析计算第二项

\[\begin{align*}\mathbb{E}[G_t+1 \mid S_t = s] &= \sum_{s^{'}} \mathbb{E}[G_{t+1} \mid S_t = s, S_{t+1} = s^{'}] p(s^{'} \mid s) \\&= \sum_{s^{'}} \mathbb{E}[G_{t+1} \mid S_{t+1} = s^{'}] p(s^{'} \mid s) \\&= \sum_{s^{'}} v_{\pi}(s^{'})p(s^{'} \mid s) \\&= \sum_{s^{'}} v_{\pi} \sum_a p(s^{'} \mid s, a) \pi(s \mid a) \end{align*} \]

第二项是future rewards的期望(expectation)
$ \mathbb{E}[G_{t+1} \mid S_t = s, S_{t+1} = s^{'}] = \mathbb{E}[G_{t+1} \mid S_{t+1} = s^{'}] $是因为马尔可夫无记忆性(memoryless markov property)

于是就可以给出贝尔曼公式的定义:

\[\begin{align*} 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(s \mid a) \sum_r p(r | s, a)r + \gamma \sum_a \pi(a \mid s) \sum_{s^{'}}p(s^{'} \mid s, a) v_{\pi}(s^{'}) \\&= \sum_a \pi(a \mid s) \left[ \sum_r p(r | s, a)r + \gamma \sum_{s^{'}}p(s^{'} \mid s, a) v_{\pi}(s^{'}) \right] , \forall s \in S\end{align*}\]

上面公式中的一些重要的点

• 上面的公式就是贝尔曼公式,它实际上描述了不同状态的state value之间的关系
• 上面的式子实际上包含两项,一个是immediate reward term,另一部分是future reward term
• 另外上面的式子注意最后的部分,并非是一个式子,而是对于状态空间中所有的状态都成立的 \(\forall s \in S\)
• state value \(v_{\pi}(s), v_{\pi}(s^{'})都是需要进行计算的,可以通过Bootstrapping来计算\)
• \(\pi (a \mid s)\)这个就是policy,这是被给出的,所以贝尔曼公式是依赖于policy的,把这个state value计算出来实际上这件事情叫做policy evaluation
• \(p(s^{'} \mid s, a), p(r, \mid s, a)\)叫dynamic model或者叫environment model.然后会根据是否知道这个dynamic model分为两种算法,不知道model的算法就是model free reinforcement learning算法

Matrix-vector form

当我们已经有了一个贝尔曼公式之后,后面的就是需要考虑如何求解这个bellman equation

Action value

summary