目录
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