Silver-Slides Chapter 2 - 强化学习之马尔科夫决策过程 Markov Decision Process（MDP）

Markov Processes

MDP被用来描述强化学习的可完全观测的环境。几乎所有的强化学习问题可以用MDP来描述，Optimal control primarily deals with continuous MDPs. Partially observable problems can be converted into MDPs. Bandits are MDPs with one state.

Markov性质：未来只和现在有关，和过去无关，也就是现在的状态捕捉到过去状态的所有信息。

Markov Process(MP)/Markov Chain由状态集合和和状态转移概率矩阵组成，即⟨S,P⟩$⟨\mathcal{S},\mathcal{P}⟩$

Markov Reward Processes

Markov reward process(MRP) 带有值的马尔科夫链。也就是在原来的基础上，每个状态多了一个对应的值，以及多了一个用于计算reward时的discount factor折扣因子γ$\gamma$ ，即⟨S,P,R,γ⟩$⟨\mathcal{S},\mathcal{P},\mathcal{R},\gamma ⟩$

• value function: 表示状态s的长期收益，即

• Bellman Equation

  value function可以被分解成两部分，immediate reward Rt+1$R_{t+1}$ 和discounted value of successor state γv(St+1)$\gamma v(S_{t+1})$ .
  

  v(s)=E[Gt|St=s]=E[Rt+1+γRt+2+γ2Rt+3+...|St=s]=E[Rt+1+γ(Rt+2+γRt+3+...)|St=s]=E[Rt+1+γGt+1|St=s]=E[Rt+1+γv(St+1)|St=s](3)(4)(5)(6)(7)$$\begin{array}{}\text{(3)}& v(s)& =\mathbb{E}[G_t|S_t=s]\text{(4)}& & =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...|S_t=s]\text{(5)}& & =\mathbb{E}[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...)|S_t=s]\text{(6)}& & =\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\text{(7)}& & =\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]\end{array}$$
  
  本来是要计算对之后所有时刻的reward的求和，现在只要利用下个时刻状态的value function即可。

  将上式的期望写具体得到：（Pss′${\mathcal{P}}_{s{s}^{\prime }}$ 是状态转移概率）
  

  v(s)=Rt+1+γ∑s′∈SPss′v(s′)$$v(s)=R_{t+1}+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}v(s^{\prime })$$
  
  写成矩阵：
  
  v=R+Pv$$v=\mathcal{R}+\mathcal{P}v$$
  
  即：
  
  ⎡⎣⎢⎢v(1)⋮v(n)⎤⎦⎥⎥=⎡⎣⎢⎢R1⋮Rn⎤⎦⎥⎥+γ⎡⎣⎢⎢P11⋮Pn1⋯⋯P1nPnn⎤⎦⎥⎥⎡⎣⎢⎢v(1)⋮v(n)⎤⎦⎥⎥(8)$$\begin{array}{}\text{(8)}& \left[\begin{array}{c}v(1)\\ ⋮\\ v(n)\end{array}\right]=\left[\begin{array}{c}{\mathcal{R}}_1\\ ⋮\\ {\mathcal{R}}_n\end{array}\right]+\gamma \left[\begin{array}{ccc}{\mathcal{P}}_{11}& \cdots & {\mathcal{P}}_{1n}\\ ⋮\\ {\mathcal{P}}_{n1}& \cdots & {\mathcal{P}}_{nn}\end{array}\right]\left[\begin{array}{c}v(1)\\ ⋮\\ v(n)\end{array}\right]\end{array}$$
  
  为了求得，可以解上述的等式：
  
  v=(1−γP)−1R$$v=(1-\gamma \mathcal{P}{)}^{-1}\mathcal{R}$$
  
  但求逆的复杂度为o(n^3)，太高，对大规模MRPs有一些迭代方法可以求解，如，Dynamic programming，Monte-Carlo evaluation，Temporal-Difference learning.

  ​

Markov Decision Processes

Markov Decision Processes(MDP) 是带有决策的MRP，即在MRP上上多了采取行动，即⟨S,A,P,R,γ⟩$⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$ ，It is an environment in which all states are Markov.

带来的变化就是：MDP考虑了动作，即系统下个状态不仅和当前的状态有关，也和当前采取的动作有关。有一点要注意的是：在某个状态执行完某个动作后，不一定是到达一个固定的状态，还可能有多种可能性，如下图所示：

定义：

举个例子（0.2,0.4,0.4那里执行动作后有多个状态，其他的为一个状态）

• Policy

  策略是在状态给定的情况下行动的分布，即π(a|s)=P[At=a|St=s]$\pi (a|s)=\mathbb{P}[A_t=a|S_t=s]$

  注意：

  1. 策略完全定义了agent的行为
  2. MDP的策略取决于当前状态，而不是history，也就是与时间无关，是静态的，At=π(⋅|St),∀t>0$A_t=\pi (\cdot |S_t),\mathrm{\forall }t>0$
  3. 给定Policy，那么MDP包含了MRP和MP

  

  需要注意的是，在这里，概率转移矩阵的元素需要经过计算，s->s’的转移概率为采取所有能到s’的行动a，对Pass′${\mathcal{P}}_{s{s}^{\prime }}^a$ 加权求和。

• Value Function

  MDP的value function有两个，state-value function和action-value function

  • state-value function

  是从状态s开始，然后采取策略π$\pi$ 的期望收益，即vπ(s)=Eπ[Gt|St=s]$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$

  • action-value function

  是从状态s开始、采取行动a后，然后采取策略π$\pi$ 的期望收益，即qπ(s,a)=Eπ[Gt|St=s,At=a]$q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$

• Bellman Expectation Equation

  和MRP一样，value function可以被分解成两个部分：

  在状态s采取行动a会有reward: Ras${\mathcal{R}}_s^a$

  

  • state-value function
    
    vπ(s)=Eπ[Gt|St=s]=Eπ[Rt+1+γvπ(St+1)|St=s]=∑a∈Aπ(a|s)⟮Ras+γ∑s′∈SPass′vπ(s′)⟯(89)(90)(91)$$\begin{array}{}\text{(89)}& v_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t|S_t=s]\text{(90)}& & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]\text{(91)}& & =\sum _{a\in A}\pi (a|s)⟮{\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })⟯\end{array}$$
    
    其中最后一步，
    

  先对每个动作求回报，再将这些动作的回报求和。

  • action-value function
    

    qπ(s,a)=Eπ[Gt|St=s,At=a]=Eπ[Rt+1+γqπ(St+1,At+1)|St=s,At=a]=Ras+γ∑s′∈SPass′∑a′∈Aπ(a′|s′)qπ(s′,a′)(92)(93)(94)$$\begin{array}{}\text{(92)}& q_{\pi }(s,a)& ={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]\text{(93)}& & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|S_t=s,A_t=a]\text{(94)}& & ={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}^a\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime })\end{array}$$
    
    

  • 两者相互转化：
    

  • 写成矩阵：
    

    vπ=Rπ+γPπvπ$$v_{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{v}_{\pi }$$
    
    解得：
    
    vπ=(1−γPπ)−1Rπ$$v_{\pi }=(1-\gamma {\mathcal{P}}^{\pi }{)}^{-1}{\mathcal{R}}^{\pi }$$

• Optimal Value Function

  最优价值函数是关于策略的，即所以策略中使其最大的就是最优价值函数。

  

  我们解决MDP就是为了得到价值函数的最大值。

• Optimal Policy

  

  • 定理：

    1. 对任何MDP存在一个最优策略π∗${\pi }_{\ast }$
    2. 所有最优策略都能达到最优价值函数，即vπ∗(s)=v∗(s)$v_{{\pi }_{\ast }}(s)=v_{\ast }(s)$
    3. 所有最优策略都能达到最优动作价值函数，即qπ∗(s,a)=q∗(s,a)$q_{{\pi }_{\ast }}(s,a)=q_{\ast }(s,a)$

  • 寻找最优策略

  就是找使每个action-value function最大的action

  

• Bellman Optimality Equation

  

  • state-value function
    

    v∗(s)=maxaq∗(s,a)=maxaRas+γ∑s′∈SPass′v∗(s′)(95)(96)$$\begin{array}{}\text{(95)}& v_{\ast }(s)& =\underset{a}{max}{q}_{\ast }(s,a)\text{(96)}& & =\underset{a}{max}{\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })\end{array}$$

  • action-value function
    

    q∗(s,a)=maxaRas+γ∑s′∈SPass′v∗(s′)=maxaRas+γ∑s′∈SPass′maxa′q∗(s′,a′)(97)(98)$$\begin{array}{}\text{(97)}& q_{\ast }(s,a)& =\underset{a}{max}{\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })\text{(98)}& & =\underset{a}{max}{\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}^a\underset{a^{\prime }}{max}{q}_{\ast }(s^{\prime },a^{\prime })\end{array}$$

  Bellman Optimality Equation是非线性的，一般没有解析解。

  解决办法有：Value Iteration、Policy Iteration、Q-learning、Sarsa

  ​

Extensions to MDPs

• Infinite and continuous MDPs

  • Countably infinite state and/or action spaces
    Straightforward

  • Continuous state and/or action spaces

  Closed form for linear quadratic model (LQR)

  • Continuous time

  Requires partial differential equations
  Hamilton-Jacobi-Bellman (HJB) equation
  Limiting case of Bellman equation as time-step ->0

• Partially observable MDPs(POMDPs)

  

• Undiscounted, average reward MDPs

  …