強化學習 2 Markov Decision Process 馬可夫決策過程
本文作為Prof David Silver的增強學習公開課筆記而存在
本文博客鏈接
Markov Processes 馬爾科夫過程
Introduction 導論
Introduction to MDPs 馬爾科夫過程導論
幾乎所有的強化學習問題都可以被轉化成為馬爾科夫過程. 我本人實際上對此深表贊同. 我甚至認為這個巨大的世界是符合馬爾科夫性的. 所謂馬爾科夫性, 是說"某一狀態信息包含了所有相關的歷史, 也就是說觀測到的狀態內容完整地決定了決策的需要的特徵". 換句話說, 這個世界是沒有記憶的. 下一刻會發生什麼只取決於上一刻. 與此相對的, 我認為人類不符合馬爾科夫性. 比如說, 因為你的記憶, 你不太可能去再和前任成為情侶.
馬爾科夫決策過程形式化地描述了強化學習的環境. 這個環境對於我們的主體是完全可觀測的. 即使對於半可觀測問題, 它們仍然能被轉化成為馬爾科夫過程. 所以, 為了更好的研究強化學習, 更好地了解馬爾科夫過程是有必要的. 如果我們能夠解決馬爾科夫問題, 我們將能夠解決所有強化學習問題.
Markov Properties 馬爾科夫性
State Transition Matrix 狀態轉移矩陣
對於馬爾科夫過程, 我們把從狀態$s$到狀態$s"$的概率定義為
$$ P= P[S= s" S_t = s] $$
其中這個大寫的$S$是一個參數. 它可以被解讀為"t+1"時刻的狀態是誰.
如果我們考慮所有狀態之間的轉化, 我們可以把這所有的轉化寫成一個概率矩陣.
Markov Chains 馬爾科夫鏈
馬爾科夫過程是一個無記憶的隨機過程, 也就是說, 一個隨機的具有馬爾科夫性的序列$S, S, ...$.
我們只需要兩個東西就能定義一個馬爾科夫過程. 一個是包含所有可能的狀態的集合$S$, 另外一個是一個狀態轉移矩陣$P$. 總之, . 請注意, 狀態集合$S$是有限的. 因此, 我本人認為馬爾科夫模型和現實世界有所不同. 現實世界的狀態不應該是無限的嗎?
下圖表示了一個馬爾科夫過程的例子.
[2]
一個樣本(sample)是一系列的狀態. 比如, 這個系列可以是"上課, 逛臉書, 逛臉書, 上第二節課, 睡覺". 但請注意, 這個系列必須是有效的, 比如這個系列不可能包含第一節課和第三節課緊挨著.
Markov Reward Processes 馬爾科夫獎勵過程
Markov Reward Process (MRP)
馬爾科夫獎勵過程在馬爾科夫過程的基礎上增加了獎勵$R$和衰減係數$gamma$. 總之, . 其中, $R$是在時刻t狀態下, 下一刻獲得的獎勵的期望. 形式化地,
$$ Rs = E[RS_t = s] $$
請注意, 獎勵函數是下一刻立即會得到的獎勵. 我們不考慮長期的獎勵.
衰減係數$gamma$是一個在$[0, 1]$之間的實數. 我們接下來會解釋衰減係數的用途.
Return 回報
對於回報, 我們會考慮長期的收益. 我們定義回報$G_t$為從$t$時刻開始以後的每一個時刻的獎勵之和 [1]. 形式化地,
[2]
請注意, 這個公式有無限多項. 另外, 回報的計算不涉及期望. 這是因為回報計算的是一個特定的系列. 這個系列是確定的, 裡面沒有任何變數.
雖然這個公式有無限多項. 但是, 我們有終止狀態, 所以對於回報的計算應該不會無限展開.
我們用衰減係數$gamma$來衡量未來的獎勵在當前被重視的程度. 形式化地, 在$k+1$時刻的獎勵於當下所體現出的價值是$gamma^k R$. $gamma$越接近1, 我們就越看重將來的獎勵(有遠見).
Why discount? 為什麼設置衰減係數
所以, 我們的預測可能是錯的. 所以, $gamma$表示我們並不完全相信我們的預測, 從來給我們留點後路.
Value Function 價值函數
價值函數給出了在某一狀態的長期價值. 換句話說, 狀態$s$所的回報的期望. 我們偏好給予我們更多總的獎勵的狀態. 形式化地,
$$ v(s) = E[G_t S_t = s] $$
Bellman Equation 貝爾曼等式
Bellman Equation for MRPs MRP中的貝爾曼等式
價值函數包含兩個部分:
我們將價值函數的定義寫成另外一種形式:
[2]
請注意, 回報的期望等於回報的期望的期望.
這個公式非常好, 因為$gamma v(S_)$就是下個時刻的狀態的價值. 所以, 我們有以下這個圖. 我們如果需要計算狀態$s$的價值, 只要加上它的獎勵, 和它能夠到達的狀態的價值, 但需要乘以每個能夠到達的價值的到達概率, 以及要注意衰減係數. 但很酷的一點是, 我們只用考慮一步就能到達的狀態. 這不是一個遞歸過程.
So we can think this as a one-step look-ahead tree.
[2]
Bellman Equation in Matrix Form 矩陣形式的貝爾曼等式
Solving in $O(n^3)$ is not practical.
Solving the Bellman Equation 解貝爾曼等式
之前我們討論過了, 每個狀態更新後的價值等同於及時的獎勵加上鄰居狀態加權後的價值. 形式化地,
$$ v = R + gamma P v \ v = (1 - gamma P)^{-1} R $$
注: 矩陣乘法真是個好東西. 利用矩陣乘法, 我們一步就能更新所有狀態的價值.
該計算的複雜度為$O(n^3)$, $n$為狀態數量. 因此, 當$n$變得很大時, 用該方法求解不太現實. 所以我們使用迭代法. 常用的迭代方法有: 動態規劃Dynamic Programming, 蒙特卡洛評估Monte-Carlo evaluation, 時序差分學習Temporal-Difference [1].
Markov Decision Processes 馬爾科夫決策過程
MDP
Markov Decision Process 馬爾科夫決策過程
在馬爾科夫獎勵過程的基礎上, 我們引入一個有限的行為集合$A$. 這一點概念非常重要. 因為強化學習會真正使用這個過程. 所以我將在此把完整概念貼出來.
我們說馬爾科夫決策過程包含這五個元素.
[2]
請注意, 我們的$P$和$R$現在不止取決於狀態, 還取決於行為. 我們接下來會給出一個具體的例子. 當學生選擇去酒吧時, 環境決定學生接下來到哪個狀態. 換句話說, 學生雖然可以完全自主的選擇其行為, 但接下來到達的狀態有時還是由環境決定.
此外獲得的及時獎勵也取決於你當下的行為. 這很好理解, 比如在考試前如果選擇通宵玩兒遊戲應該就會獲得很差的及時獎勵.
[2]
Policies 策略
策略$pi$是在給定狀態下的對於行為的分布. 形式化地,
$$ pi(as)=P[A_t = a S_t = s] $$
策略定義了一個主體在某個狀態下所能夠做出的所有行為以及它們的概率大小. 並且策略只和當前狀態有關, 和歷史無關(馬爾科夫性). 為了簡單起見, 我們的策略不隨著時間的變化而變化.
通過策略, 我們能將馬爾科夫決策過程和馬爾科夫過程以及馬爾科夫獎勵過程聯繫在一起. 這挺好理解的, 因為這相當於你沒有了自由意志, 不主動做任何行為, 聽天由命.
具體地, 對於一個馬爾科夫決策過程$M = $和一個策略$pi$, 狀態序列$S_1, S_2, ...$是一個馬爾科夫過程. 同理, 狀態和獎勵序列$S_1, R_2, S_2, R_3, ...$是一個馬爾科夫獎勵過程. 形式化地,
[2]
通俗地說, 從狀態$s$到狀態$s"$的概率是一系列概率之和. 這一系列概率中的每一個元素是一個能夠導致從狀態$s$到狀態$s"$的行為, 乘以這個行為在$s$下的概率(加權). 馬爾科夫獎勵過程與此類似.
作者瞎寫: 蓋亞??? 如果沒有自由意志的話, 環境沒有辦法改變自身. 所以它需要生物來改變它的馬爾科夫狀態?
Value Function 價值函數
馬爾科夫決策過程的行為竊以為是模擬自由意志. 在有自由意志的時候, 我們是無法計算期望的. 但如果我們確定了策略, 我們沒有了自由, 就可以計算期望了.
具體來說, MDP的狀態價值函數$v_{pi}(s)$是在狀態$s$對於策略$pi$的回報期望. 形式化地,
$$ v{pi}(s) = E{pi}[GS= s] $$
類似地, 我們有行為價值函數, 是在狀態$s$對於策略$pi$, 行為$a$的回報期望. 形式化地,
$$ q{pi}(s, a) = E{pi}[G_t S_t = s, A_t = a] $$
我們在這裡給出一個具體地例子, 如下圖. 我們來解釋那個7.4是怎麼來的. 我們有兩個選擇, 學習或者去酒吧.
學習的回報: 10 去酒吧的回報: 1 + 0.2(-1.3) + 2.70.4 + 0.4 * 7.4 + 1 = 4.78. +1為即刻獎勵.
所以, 那個狀態的價值為: 0.510 + 0.54.78 = 7.39.
[2]
Bellman Expectation Equation 貝爾曼期望方程
$$ v{pi} = R^{pi} + gamma P^{pi} v$$
可以解得
$$ v_{pi} = (I - gamma P^{pi})^{-1} R^{pi} $$
這個等式的意思是說, 我們的過程達到了一個平衡狀態, 不會再有變化. 換句話說, 這就是我們最終會得到的回報.
像我們之前講的, 這樣會使複雜度很高. 所以我們接下來會給出更好的方法.
Optimal Value Function 最優價值函數
這是強化學習最重要的一部分. 如果我們能夠找到這個函數, 那麼我們幾乎就可以躺贏了.
最優狀態價值函數(optimal state-value function)是在所有的策略產生的狀態價值函數中, 我們選擇使狀態s價值最大的策略; 在選擇這種策略的情況下, 這個函數返回這個狀態s的價值. 類似地, 最優行為價值函數$q_{*}(s, a)$是在所有的策略產生的行為價值函數中, 我們選擇使狀態s, 行為a價值最大的策略; 在選擇這種策略的情況下, 這個函數返回這個狀態s在行為a下的價值. 形式化地,
[2]
換句話說, 這個函數在某種意義上衡量了"能力的上限". 換句話說, 使用渾身解數所能夠達到的價值是多少.
Optimal Policy 最優策略
最優策略是使得MDP在使用這個策略時, 每一個狀態的價值都比使用其他策略時要高. 形式化地,
[2]
我們有一些很好的定理, 但沒有被證明.
第二個定理很好證明. 如果存在兩個最優策略, 他們在狀態s, s"導致了不同的價值. 那麼根據定義, 導致價值更高的那個策略才應該是唯一的最優價值.
第一個定理給出形式化地證明有點麻煩(但我覺得不困難, 如果您有興趣, 完全可以做), 但挺好理解的的. 因為價值是一個考慮到未來回報的一個量. 相當於我們是先知, 我們知道做這一步在未來會有巨大價值. 因為我一開始擔心會有一些最優策略, 在某些狀態的價值會低於其他策略, 但最終會變得很好. 後來我發現我錯了, 因為在那些之前的狀態, 計算價值的時候也會考慮到最終的回報. 我們考慮的是價值, 而不是收穫. 反證的話, 假設我們存在這麼些狀態, 使得最優策略在這些狀態的價值低於其他策略. 那也就是說我們在這些狀態沒有選擇最終會獲得最大價值的策略. 這不符合做事情的自私的邏輯.
第三個定理我也可以理解. 一開始, 我有點擔心會不會有一些行為表現很差, 使得有些最優策略在這些行為表現的很差, 但對於更好的行為表現的更好. 我們只需要把走到這些差行為的概率設置成0就好了. 反正我們考慮的是狀態的價值, 而不是某個行為的價值. 但我後來意識到策略是一個分布.
Finding an Optimal Policy 尋找最優策略
我們可以通過最大化最優行為價值函數來尋找最優策略. 如下圖所示.
[2]
這樣的話策略的分布就很有意思了. 分布裡面應該就不是1就是0.
Bellman Optimality Equation 貝爾曼最優方程
Bellman Optimality Equation for $v_{*}$
其實這東西挺好理解的. 和前面那個貝爾曼期望方程沒啥差別. 只是前面是算期望的, 這個是算最大值的. 我在這裡給一個例子. 求解這東西是非線性的. 我們在將來會學一些更好的迭代方式.
[2]
Extensions to MDPs
References
[1]葉. 強, "《強化學習》第二講 馬爾科夫決策過程", 知乎, 2018. [Online]. Available: https://zhuanlan.zhihu.com/p/28084942. [Accessed: 31- Jan- 2018].
[2]D. Silver, "RL Course by David Silver - Lecture 2: Markov Decision Process", YouTube, 2018. [Online]. Available: https://youtu.be/lfHX2hHRMVQ. [Accessed: 31- Jan- 2018].
TAG:全球大搜羅 |