# 馬爾可夫決策過程 筆記
通常我們要使用強化學習去解決實際問題, 第一次試把實際問題抽象成馬爾可夫決策過程

### 馬爾可夫過程
**隨機過程** 意指隨時間變化的隨機狀態, 我們使用St表示時間在t時的狀態, 將所有可能的狀態組合在一起, 即為集合S
在某時刻t的狀態St取決於時刻t之前的狀態
假設我們已知一段歷史狀態(S1,...,St)時, 下一個時間的狀態為St+1的機率可以表示成

若某時刻的狀態使取決於上一時刻的狀態時, 隨機過程被稱為具有 **馬爾可夫性質**, 剛剛提到的機率即可表示成, 但是這不代表隨機過程就和過去完全沒關係, 因為實際上時刻t與t-1有關係, 這樣過去的狀態可以被傳遞到未來, 這麼做是為了簡化計算, 不需要再統整所有歷史狀態

**馬爾可夫過程**指有馬爾可夫性質的隨機過程, 也稱**馬爾可夫鍊**(markov chain), 通常使用一個有限數量的狀態集合S和一個**狀態轉移矩陣**P來描述一個馬爾可夫過程
其中意思為從狀態Si轉移到Sj的機率, 此矩陣的每一行總和必須為1, 若有狀態不會再轉移到其他狀態, 稱之為**終止狀態**

## 馬爾可夫獎勵過程

若我們在馬爾可夫過程的基礎上加上**獎勵函數**r和**折扣因子**γ, 即可得**馬爾可夫獎勵過程**, 其中折扣因子的存在是為了讓長期利益具有一定的不確定性, 畢竟我們更在乎短期獎勵, 其值為[0,1), 若γ越接近0, 表示我們更在乎短期獎勵

有了這四個元素, 我們可以簡單地得到t=0到時間t的累積回報的公式
Gt為所有獎勵之和

對於一個狀態的期望回報被稱為這個狀態的**價值**(value), 所有狀態的價值組成了**價值函數**, 其實很好理解, 就是輸入一個狀態後, 輸出該狀態的價值. 記做
對於最後一個等式, Rt為時間t的即時獎勵, 所以此等式的意義為, 在狀態s下, 智能體期望總回報是Rt加上 下一個狀態St+1的期望總回報γV(St+1)組成, 智能體在學習的過程中必須最大化V(s), 我們把這兩項分開記做
其中p(s' | s)為從狀態s轉移到下一個狀態s'的機率
此公式也稱為**貝爾曼方程**(Bellman qeuation)
另外我們可以把貝爾曼方程改寫成矩陣形式, 如下
因此如果我們要求解 V 可以再次改寫成
根據這個公式, 可看出時間複雜度為O(n^3), 所以對於求解較大規模的馬爾可夫獎勵過程的價值函數, 通常會使用**動態規劃**、**蒙特卡洛方法**、**時序分差**