1. 簡介

• 馬爾可夫決策過程正式地描述了強化學習的環境
• 其中環境是完全可觀測的
• 即當前狀態完全表征了這個過程
• 幾乎所有的強化學習問題都可以形式化為馬爾可夫決策過程，例如：
  • 最優控制主要處理連續的馬爾可夫決策過程
  • 部分可觀察的問題可以轉化為馬爾可夫決策過程
  • 賭場問題是具有單一狀態的馬爾可夫決策過程

2. 馬爾科夫性（Markov property）

當一個隨機過程在給定現在狀態及所有過去狀態情況下，其未來狀態的條件概率分布僅依賴于當前狀態；換句話說，在給定現在狀態時，它與過去狀態（即該過程的歷史路徑）是條件獨立的，那么此隨機過程即具有馬爾可夫性質。具有馬爾可夫性質的過程通常稱之為馬爾可夫過程。

用式子來表示：

$$P[S_{t+1}|S_t]=P[S_{t+1}|S_1,?,S_t]$$

或者：

$${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s]$$

狀態轉移矩陣 $\mathcal{P}$ 定義了從 $s$ 的所有狀態到所有后繼狀態 $s^{\prime }$ 的轉移概率，每一行的和都是1

3. 馬爾可夫過程（Markov Process）

馬爾科夫過程是一個無記憶的隨機過程，比如一系列遵循馬爾科夫性的隨機狀態 $S_1,S_2,?$

定義：馬爾可夫過程（也稱為馬爾可夫鏈）是一個元組 $?S,\mathcal{P}?$，其中：

• $S$ 是一個有限的狀態集合
• $\mathcal{P}$ 是一個狀態轉移矩陣，${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s]$

例子：學生馬爾可夫鏈

這個馬爾科夫鏈從 $S_1=C1$ 開始，$S_1,S_2,?,S_T$ 舉例如下：

$C1,C2,C3,Pass,Sleep$
$C1,FB,FB,C1,C2,Sleep$
$C1,C2,C3,Pub,C2,C3,Pass,Sleep$
$C1,FB,FB,C1,C2,C3,Pub,C1,FB,FB,FB,C1,C2,C3,Pub,C2,Sleep$

學生馬爾可夫鏈的轉移矩陣：

4. 馬爾可夫獎勵過程（Markov Reward Process）

馬爾可夫獎勵過程是一個元組 $?S,\mathcal{P},\mathcal{R},\gamma ?$

• $S$ 是一個有限的狀態集合
• $\mathcal{P}$ 是一個狀態轉移矩陣，${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s]$
• $\mathcal{R}$ 是一個獎勵函數，${\mathcal{R}}_s=\mathbb{E}[R_{t+1}|S_t=s]$
• $\gamma$ 是一個折扣系數，$\gamma \in [0,1]$

例子：學生馬爾可夫獎勵過程（Student MRP）

$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+?={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$ 代表收獲（return)，是一個MDP中從某一個狀態 $S_t$ 開始采樣直到終止狀態時所有獎勵的有衰減的和。

其中：

• 折扣系數（或者叫衰減系數）$\gamma \in [0,1]$ 是未來獎勵的當下價值
• 在 $k+1$ 個時間步后獲得獎勵的價值為 ${\gamma }^{k}R$
• 即時獎勵的價值高于延遲獎勵:
  • $\gamma$ 接近0會導致“近視”評估
  • $\gamma$ 接近1會導致“遠視”評估

大多數馬爾可夫獎勵和決策過程是帶有折扣的。為什么？

• 數學上折扣獎勵更方便
• 避免循環馬爾可夫過程中出現無限回報
• 對未來的不確定性可能無法完全表示
• 如果獎勵是金錢，即時獎勵可能比延遲獎勵賺取更多利息
• 動物/人類行為表現出對即時獎勵的偏好
• 有時可以使用不帶折扣的馬爾可夫獎勵過程（即$\gamma =1$），比如所有的序列都一定會終止

例子：Student MRP Returns

初始狀態為 $S_1=C1$，$\gamma =\frac{1}{2}$

$$G_1=R_2+\gamma R_3+?+{\gamma }^{T?2}{R}_T$$

$\gamma =0$ 時學生MRP的狀態價值函數：

$\gamma =0.9$ 時學生MRP的狀態價值函數：

$\gamma =1$ 時學生MRP的狀態價值函數：

馬爾科夫獎勵過程的貝爾曼方程

狀態價值函數可以被分解為兩部分：

• 即時獎勵 $R_{t+1}$
• 后續狀態的折扣價值 $\gamma v(S_{t+1})$

$$\begin{array}{rl}v(s)& =\mathbb{E}[G_t\mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\dots )\mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})\mid S_t=s]\end{array}$$

馬爾科夫獎勵過程（MRPs）的貝爾曼方程：

$$v(s)=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1}|S_t=s)]$$

$$v(s)={\mathcal{R}}_s+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}v(s^{\prime })$$

例子：Student MRP的貝爾曼方程

這里的 $\gamma =1$，并且已經知道了Pub的狀態價值為0.8，Pass的狀態價值為10

貝爾曼方程的矩陣形式：

$$v=\mathcal{R}+\gamma \mathcal{P}v$$

其中 $v$ 是每個狀態都有一個對應元素的列向量：

求解貝爾曼方程：

貝爾曼方程是一個線性方程，可以被直接求解：

$$\begin{array}{rl}v& =\mathcal{R}+\gamma \mathcal{P}v\\ (I?\gamma \mathcal{P})v& =\mathcal{R}\\ v& =(I?\gamma \mathcal{P}{)}^{?1}\mathcal{R}\end{array}$$

對于n個狀態的計算復雜度為 $O(n^3)$

因為計算復雜度比較大，直接求解只可能在小規模的馬爾科夫獎勵過程中實現，在大規模馬爾科夫獎勵過程中可以使用很多迭代的方法，比如：

• 動態規劃（Dynamic Programming）
• 蒙特卡洛法（Monte-Carlo evaluation）
• 時序差分法（Temporal-Difference）

5. 馬爾科夫決策過程 Markov Decision Process

馬爾科夫決策過程（MDP）就是帶有決策的馬爾科夫獎勵過程（MRP），它是一個所有狀態都符合馬爾科夫性質的環境。

馬爾科夫決策過程是一個元組 $?\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ?$

• $\mathcal{S}$是一個有限的狀態集合
• $\mathcal{A}$ 是一個有限的動作集合
• $\mathcal{P}$ 是一個狀態轉移概率矩陣，${\mathcal{P}}_{s{s}^{\prime }}^a=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s,A_t=a]$
• $\mathcal{R}$ 是一個獎勵函數，$\mathcal{R}=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]$
• $\gamma$ 是一個折扣率，$\gamma \in [0,1]$

例子：學生馬爾科夫決策過程

策略$\pi$是給定狀態下動作的概率分布

$$\pi (a|s)=\mathbb{P}[A_t=a|S_t=s]$$

• 策略完全定義了一個agent的行為
• MDP的策略只依賴當前狀態（不依賴歷史狀態）
• 比如，策略是靜態的，與時間無關，$A_t～\pi (?\mid S_t),?t>0$

給定一個MDP $?\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ?$ 和一個策略 $\pi$，狀態序列 $S_1,S_2,?$ 是一個馬爾科夫過程 $?\mathcal{S},{\mathcal{P}}^{\pi }?$，狀態和獎勵序列 $S_1,R_2,S_2,?$ 是一個馬爾科夫獎勵過程 $?\mathcal{S},{\mathcal{P}}^{\pi },{\mathcal{R}}^{\pi },\gamma ?$，則有：

$${\mathcal{P}}_{s,s^{\prime }}^{\pi }=\sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{P}}_{s{s}^{\prime }}^a$$

$${\mathcal{R}}_s^{\pi }=\sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{R}}_s^a$$

價值函數：

一個MDP的狀態價值函數 $v_{\pi }(s)$ 是從狀態 $s$ 開始依據策略 $\pi$ 的收獲（$G_t$）的期望：

$$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

動作價值函數 $q_{\pi }(s,a)$ 是是從狀態 $s$ 開始依據策略 $\pi$ 采取動作 $a$ 的期望：

$$q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$$

例子：Student MDP的狀態價值函數

Bellman期望方程 Bellman Expectation Equation

MDP下的狀態價值函數和動作價值函數與MRP下的價值函數類似，可以改用下一時刻狀態價值函數或動作價值函數來表達，具體方程如下：

$$v_{\pi }(s)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s\right]$$

$$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a\right]$$

根據動作價值函數 $q_{\pi }(s,a)$ 和狀態價值函數 $v_{\pi }(s)$ 的定義，我們很容易得到他們之間的轉化關系公式：

利用上貝爾曼方程，我們也很容易用狀態價值函數表示動作價值函數
，即：

當然，也可以做一層推算：

例子：Student MDP的貝爾曼期望方程

圖中計算Pass的狀態價值所用方程：

$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)\left({\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })\right)$$

因為不是從Pub來推理Pass，而是從Pub的上一層 Class 1，Class 2和Class 3來推理，所以不用知道Pub的狀態價值就可以計算。同理因為Sleep沒有上一層，所以只需要用它的獎勵就可以計算Pass的價值。

貝爾曼期望方程的矩陣形式：

Bellman期望方程可以用誘導MRP簡潔地表示：

$$v_{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{v}_{\pi }$$

可以直接求解：

$$v_{\pi }=(I?\gamma {\mathcal{P}}^{\pi }{)}^{?1}{\mathcal{R}}^{\pi }$$

6. 最優價值函數

定義：

最優狀態價值函數 $v_{?}(s)$ 指的是在所有策略產生的狀態價值函數中，使狀態s價值最大的那個函數：

$$v_{?}(s)=\underset{\pi }{\max }{v}_{\pi }(s)$$

最優動作價值函數 $q_{?}(s,a)$ 指的是在所有策略產生的動作價值函數中，使狀態動作對$?s,a?$價值最大的那個函數：

$$q_{?}(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)$$

最優價值函數明確了MDP的最優可能表現，當我們知道了最優價值函數，也就知道了每個狀態的最優價值，這時便認為這個MDP得到了解決。

例子：Student MDP的最優價值函數

例子：Student MDP的最優動作價值函數

最優策略

定義策略的部分排序：

$$\pi \ge {\pi }^{\prime }\text{if}{v}_{\pi }(s)\ge v_{{\pi }^{\prime }}(s),?s$$

定理：

對于任意馬爾可夫決策過程（Markov Decision Process, MDP）：

• 存在一個最優策略 ${\pi }_{?}$，它優于或等于所有其他策略，即 ${\pi }_{?}\ge \pi ,?\pi$
• 所有最優策略都能達到最優狀態價值函數，即 $v_{{\pi }_{?}}(s)=v_{?}(s)$
• 所有最優策略都能達到最優動作-價值函數，即 $q_{\pi }?(s,a)=q_{?}(s,a)$

尋找最優策略

可以通過最大化最優行為價值函數來找到最優策略：

$${\pi }_{?}(a|s)=?\begin{array}{ll}1& \text{if?}a=\underset{a\in \mathcal{A}}{\mathrm{argmax}}{q}_{?}(s,a)\\ 0& \text{otherwise}\end{array}$$

• 對于任何MDP問題，總存在一個確定性的最優策略；
• 如果我們得到了最優動作價值函數 $q_{?}(s,a)$，則表明我們已經找到了最優策略。

例子：Student MDP的最優策略

$v_{?}$的貝爾曼最優方程

最優值函數通過貝爾曼最優方程遞歸關聯

$Q_{?}$的貝爾曼最優方程

$v_{?}$的貝爾曼最優方程（2）

$Q_{?}$的貝爾曼最優方程（2）

例子：Student MDP的貝爾曼最優方程

求解貝爾曼最優方程：

爾曼最優方程是非線性的，（一般情況下）沒有封閉解，但有許多迭代求解方法來解決：價值迭代（Value Iteration）、策略迭代（Policy Iteration）、Q學習（Q-learning）、Sarsa等

還有一些馬爾可夫決策過程（MDPs）的擴展，比如：

• 無限和連續的馬爾可夫決策過程（Infinite and continuous MDPs）
• 部分可觀測的馬爾可夫決策過程（Partially observable MDPs）
• 無折扣、平均獎勵的馬爾可夫決策過程（Undiscounted, average reward MDPs）

這里不做一一講解