强化学习经典算法笔记——推导贝尔曼方程

  在写强化学习经典算法笔记(一)：价值迭代算法Value Iteration和强化学习经典算法笔记(二)：策略迭代算法Policy Iteration的时候，感觉关键的部分——为什么要这样进行值（策略）迭代，没有讲清楚，概念有点模糊，所以感觉有必要重新关注一下Bellman Equation的来龙去脉，也是加强自己对这一块内容的理解。

相关概念

  在介绍贝尔曼方程之前，必须对几个概念有所了解，下面我们一一介绍。

• 策略函数，Policy Function
• 状态价值函数，State Value Function
• 状态动作价值函数，State-action Value Function

策略函数 Policy Function

  策略常表示为$\pi(s):\ S\rightarrow A$π(s): S→A，函数的输入是一个状态$s$s，输出状态$s$s下应该采取的动作 $a$a 。策略函数的最优化是强化学习算法的核心任务。

状态价值函数 State Value Function

  策略$\pi(s)$π(s)的优劣可以用状态价值函数来评价。常简称为Value Function，即价值函数。

  Value Function的意义是，当处于状态$s_t$st​时，从下一个状态$s_{t+1}$st+1​开始，直至一个Episode结束，都按照策略$\pi(s)$π(s)与env进行交互，将从$s_{t+1}$st+1​到$s_{\infin}$s∞​过程中得到的reward累加起来，取其期望值作为状态$s_t$st​的价值。即
$V^{\pi}(s)=E_{\pi}[R_t\ |\ s_t=s]$Vπ(s)=Eπ​[Rt​ ∣ st​=s]
因为$R_t=\sum_{k=0}^{\infin} \gamma^k\ r_{t+k+1}$Rt​=∑k=0∞​γk rt+k+1​ ，其中$r_{t+1}$rt+1​表示从$s_t$st​转移到$s_{t+1}$st+1​时的回报。
$V^{\pi}(s)=E_{\pi}[\sum_{k=0}^{\infin}\gamma^k\ r_{t+k+1}\ |\ s_t=s]$Vπ(s)=Eπ​[k=0∑∞​γk rt+k+1​ ∣ st​=s]

  直观来看，一个状态的价值是从这个状态开始，依照某种策略，继续与环境进行交互而得到的总的回报。因此可以说Value Function受两个变量的控制，一个是状态$s$s，从不同的状态出发，得到的分数有可能一样，有可能不一样。另一个就是策略函数Policy Function，Value Function一定是建立在某个策略上做出的评价，处于同一个状态$s$s时，依照策略$\pi_1(s)$π1​(s)玩下去的得分高于$\pi_2(s)$π2​(s)，我们就可以说，$\pi_1$π1​优于$\pi_2$π2​。

  另外需要注意，Value的定义是取累计回报的期望值，因为环境的不确定，进行N个episode的实验，得到N个$s_{t+1}$st+1​到$s_{\infin}$s∞​的累计汇报$R_t$Rt​，这N个值不可能完全一样，因此可以将$R_t$Rt​建模为一个随机变量，并取$E[R_t]$E[Rt​]作为状态$s_t$st​的比较可靠的评价。

状态动作价值函数 State-action Value Function

  状态动作价值函数一般称为Q值函数——Q Function。相比于Value Function是对状态的评估，Q Function是对（状态-动作对） 的评估。

  Q值的定义是，给定一个状态$s_t$st​，采取动作$a_t$at​后，按照某一策略$\pi(s)$π(s)与环境继续进行交互，得到的累计汇报的期望值。
$Q^{\pi}(s,a)=E_{\pi}[R_t\ |\ s_t=s,a_t=a]$Qπ(s,a)=Eπ​[Rt​ ∣ st​=s,at​=a]
即
$Q^{\pi}(s,a) = E_{\pi}[\sum_{k=0}^{\infin}\gamma^k\ r_{t+k+1}\ |\ s_t=s,a_t=a]$Qπ(s,a)=Eπ​[k=0∑∞​γk rt+k+1​ ∣ st​=s,at​=a]
  Q函数对状态的评价更细化，精确到了每一个动作上。通过Q函数，可以确定在每个状态时应该采取什么动作。

Bellman Equation

  贝尔曼方程用于求解MDP问题，也就是找到最优策略及其对应的价值函数。最优价值函数是在每一个状态上，其值 $\ge$≥ 其他价值函数在该状态的值 的价值函数。
$V^*(s) = max_{\pi}V^{\pi}(s)$V∗(s)=maxπ​Vπ(s)

  从另一个角度看，在状态$s$s取最优的价值$V^*(s)$V∗(s)，也就意味着，在状态$s$s，依照最优Q函数，采取最优的动作$a$a，得到的价值$Q*(s,a)$Q∗(s,a)
$V^*(s)=max_a Q^*(s,a)$V∗(s)=maxa​Q∗(s,a)
  我们先给出价值函数的贝尔曼方程，它表示的是当前状态和下一个状态之间的递归关系。
$V^{\pi}(s)=\sum_a \pi(s,a)\sum_{s'}p_{ss'}^a[R_{ss'}^{a}+\gamma V^{\pi}(s')]$Vπ(s)=a∑​π(s,a)s′∑​pss′a​[Rss′a​+γVπ(s′)]

  相应地，我们给出基于Q函数的贝尔曼方程。
$Q^{\pi}(s,a) = \sum_{s'} P_{ss'}^a[R_{ss'}^a+\gamma \sum_{a'}Q^{\pi}(s',a')]$Qπ(s,a)=s′∑​Pss′a​[Rss′a​+γa′∑​Qπ(s′,a′)]

  其中，$P_{ss'}^a$Pss′a​是前后状态之间的转移概率，$R_{ss'}^a$Rss′a​是采取动作$a$a，从$s$s转移到$s'$s′，环境反馈的reward。

  利用上面的V和Q的关系，得到
$V^*(s) = max_a\sum_{s'}P_{ss'}^a[R_{ss'}^a+\gamma \sum_{a'}Q^{\pi}(s',a')]$V∗(s)=maxa​s′∑​Pss′a​[Rss′a​+γa′∑​Qπ(s′,a′)]

  上式称为Bellman最优性方程，通过解这个方程，可以得到最优策略。而强化学习经典算法笔记(一)：价值迭代算法Value Iteration和强化学习经典算法笔记(二)：策略迭代算法Policy Iteration中的关键一步，正是上面这个式子的实现（只缺了max）。

for next_sr in env.P[state][action]: 
	# 在当前state和action的情况下，把可能转移的状态遍历一遍 
	# next_sr = (0.3333333333333333, 8, 0.0 , False) 
	# next_sr = (状态转移概率, 下一个状态,得到reward的概率,游戏是否结束) 
	trans_prob, next_state, reward_prob, _ = next_sr 
	
	# 下一状态t的动作状态价值 = 转移到t状态的概率 × （ env反馈的reward + γ × t状态的当前价值 ）
	next_states_rewards.append((trans_prob * (reward_prob + gamma * updated_value_table[next_state]))) 

贝尔曼方程的推导

  先前定义的转移概率$P_{ss'}^a$Pss′a​可以展开写成一个条件概率
$P_{ss'}^a=P(s_{t+1}=s'\ |\ s_t=s,a_t=a)\quad ①$Pss′a​=P(st+1​=s′ ∣ st​=s,at​=a)①

  再看$R_{ss'}^a$Rss′a​，$R_{ss'}^a$Rss′a​是从$s_t$st​状态转移到$s_{t+1}$st+1​状态的回报概率。（应该是一个介于0和1之间的值）
$R_{ss'}^a = E(R_{t+1}\ |\ s_t=s,s_{t+1}=s',a_t=a) \quad ②$Rss′a​=E(Rt+1​ ∣ st​=s,st+1​=s′,at​=a)②
即
$R_{ss'}^a = \gamma E_{\pi}[\sum_{k=0}^{\infin}\gamma^kr_{t+k+2}\ |\ s_{t+1}=s'] \quad ③$Rss′a​=γEπ​[k=0∑∞​γkrt+k+2​ ∣ st+1​=s′]③
  但是从②式推导③式的过程我不是很理解。因为$R_t=r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots$Rt​=rt+1​+γrt+2​+γ2rt+3​+⋯，所以
$R_{t+1} = r_{t+2}+\gamma r_{t+3}+\gamma^2r_{t+4}+\cdots= \sum_{k=0}^{\infin}\gamma^kr_{t+k+2}$Rt+1​=rt+2​+γrt+3​+γ2rt+4​+⋯=∑k=0∞​γkrt+k+2​，将这个式子带入②式，和③式之间还是差着$\gamma$γ倍。

  
  

  我们再来看状态函数的定义：
$V^{\pi}(s)=E_{\pi}[R_t|s_t=s]$Vπ(s)=Eπ​[Rt​∣st​=s]
$V^{\pi}(s)=E_{\pi}[r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots|s_t=s]$Vπ(s)=Eπ​[rt+1​+γrt+2​+γ2rt+3​+⋯∣st​=s]

  把第一项提出来，之后的项写成求和的形式，就可以看成是前后两项求期望。一项是从$s_t$st​跳转到$s_{t+1}$st+1​，得到当前回报 $r_{t+1}$rt+1​；第二项是按照策略$\pi(s)$π(s)继续走下去得到的累计回报$\sum_{k=0}^{\infin}\gamma^kr_{t+k+2}$∑k=0∞​γkrt+k+2​。
$V^{\pi}(s) = E_{\pi}[r_{t+1}+\gamma\sum_{k=0}^{\infin}\gamma^kr_{t+k+2}|s_t=s]\quad ④$Vπ(s)=Eπ​[rt+1​+γk=0∑∞​γkrt+k+2​∣st​=s]④

  

  把第一项拿出来，因为我们知道从$s_t$st​跳转到$s_{t+1}$st+1​，有多个可能的动作以及对应的转移概率和回报概率，将其展开，就是下式，式中的$s'$s′表示下一状态，$\sum_{s'}$∑s′​表示遍历状态$s$s的所有可能的下一状态。
$E_{\pi}[r_{t+1}|s_t=s]=\sum_a\pi(s,a)\sum_{s'}P_{ss'}^aR_{ss'}^a \quad ⑤$Eπ​[rt+1​∣st​=s]=a∑​π(s,a)s′∑​Pss′a​Rss′a​⑤
  把②式带入⑤式右边，得
$\sum_a\pi(s,a)\sum_{s'}p_{ss'}^a\gamma E_{\pi}[\sum_{k=0}^{\infin}\gamma^kr_{t+k+2}\ |\ s_{t+1}=s']\quad ⑥$a∑​π(s,a)s′∑​pss′a​γEπ​[k=0∑∞​γkrt+k+2​ ∣ st+1​=s′]⑥
  
  再看第二项 $E_{\pi}[\gamma \sum_{k=0}^{\infin}\gamma^kr_{t+k+2}|s_t=s]$Eπ​[γ∑k=0∞​γkrt+k+2​∣st​=s]，表示状态$s_t$st​的后2个状态（$s_{t+2}$st+2​）开始的累计回报，所以应该遍历各个可能的$s_{t+1}$st+1​状态。

$E_{\pi}[\gamma \sum_{k=0}^{\infin}\gamma^k r_{t+k+2}|s_t=s]=\sum_a\pi(s,a)\sum_{s'}P_{ss'}^a\gamma E_{\pi}[\sum_{k=0}^{\infin}\gamma^kr_{t+k+2}|s_{t+1}=s'] \quad ⑦$Eπ​[γk=0∑∞​γkrt+k+2​∣st​=s]=a∑​π(s,a)s′∑​Pss′a​γEπ​[k=0∑∞​γkrt+k+2​∣st+1​=s′]⑦
  把上面⑥⑦两式加起来，
$V^{\pi}(s)=\sum_a\pi(s,a)\sum_{s'}P_{ss'}^a[R_{ss'}^a+\gamma E_{\pi}[ \sum_{k=0}^{\infin}\gamma^kr_{t+k+2}|s_{t+1}=s']]\quad ⑧$Vπ(s)=a∑​π(s,a)s′∑​Pss′a​[Rss′a​+γEπ​[k=0∑∞​γkrt+k+2​∣st+1​=s′]]⑧

  把$E_{\pi}[ \sum_{k=0}^{\infin}\gamma^kr_{t+k+2}|s_{t+1}=s']$Eπ​[∑k=0∞​γkrt+k+2​∣st+1​=s′]写成$V^{\pi}(s')$Vπ(s′)，即下一状态的价值函数，则上式化简为Value函数的贝尔曼方程
$V^{\pi}(s)=\sum_a\pi(s,a)\sum_{s'}P_{ss'}^a[R_{ss'}^a+\gamma V^{\pi}(s')] \quad ⑨$Vπ(s)=a∑​π(s,a)s′∑​Pss′a​[Rss′a​+γVπ(s′)]⑨
  类似的，可以推出Q函数的贝尔曼方程
$Q^{\pi}(s,a)=\sum_{s'}P_{ss'}^a[R_{ss'}^a+\gamma \sum_{a'}Q^{\pi}(s',a')] \quad ⑩$Qπ(s,a)=s′∑​Pss′a​[Rss′a​+γa′∑​Qπ(s′,a′)]⑩