一、馬爾可夫決策過程

狀態轉移概率：用$p[s_{t+1},r_t|s_t,a_t]$表示在狀態$s_t$選擇動作$a_t$時，轉移到狀態$s_{t+1}$，得到獎勵$r_t$的概率。
狀態轉移概率是具有馬爾可夫性質的，系統下一時刻的狀態僅有當前時刻的狀態決定，不依賴于以往任何狀態。

馬爾可夫決策過程的四元組：$(S,A,P,R)$。加上折扣因子$\gamma$組成五元組。

概率函數：$P[s_{t+1},r_t|s_t,a_t]$
獎勵函數：$R[s_t,a_t]$
若知道概率函數和獎勵函數，則馬爾可夫決策過程就是已知的，可以通過策略迭代和價值迭代找到最佳策略。換句話說，如果知道環境的狀態轉移概率和獎勵函數，則環境就是已知的，可以用這兩個函數來描述環境。這種情況下的算法為有模型算法。

如果環境未知，則是免模型算法。

免模型強化學習方法沒有獲取環境的狀態轉移和獎勵函數，而是讓智能體與環境進行交互，采集大量的軌跡，從軌跡中獲取信息改進策略。

二、Q表格

如下圖所示，Q表格的行為所有狀態，列為所有動作。最開始Q表格全部初始化為0。當交互足夠多時，可以估算出每一個狀態下，每個動作的平均總獎勵，更新Q表格。

強化：指可以用下一個狀態的價值更新當前狀態的價值，即自舉。

每走一步更新一次Q表格，用下一個狀態的Q值更新當前狀態的Q值，這種單步更新的方法稱為時序差分方法（TD，Temporal Difference）。

三、免模型預測

在免模型狀態下，可以通過蒙特卡洛方法和時序差分方法估計某個給定策略的價值。

1. 蒙特卡洛策略評估

是基于采樣的方法，給定策略$\pi$，讓智能體與環境交互，得到很多軌跡。每個軌跡都有回報：
$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+?$$則某一個策略對應狀態的價值，可以用所有軌跡的回報的平均值表示：
$$V_{\pi }(s)={\mathbb{E}}_{\tau ～\pi }[G_t|s_t=s]$$蒙特卡洛仿真指：可以采樣大量的軌跡，計算所有軌跡的真實回報，計算平均值。
其使用經驗平均回報的方法進行估計，因此不需要狀態轉移函數和獎勵函數，也不需要自舉。
蒙特卡洛只能用在有終止的馬爾可夫決策過程中。

寫成增量式蒙特卡洛：
$$\begin{gathered} N(s_t)\leftarrow N(s_t)+1 \\ V(s_t)\leftarrow V(s_t)+\frac{1}{N(s_t)}\left(G_t?V(s_t)\right) \end{gathered}$$把$\frac{1}{N(s_t)}$看成學習率$\alpha$，則
$$V(s_t)\leftarrow V(s_t)+\alpha \left(G_t?V(s_t)\right)$$

1) 動態規劃方法和蒙特卡洛方法的差異

動態規劃中使用了自舉的思想，即基于之前估計的量來估計一個量。同時使用了貝爾曼期望備份，通過上一時刻的$V_{i?1}(s^{\prime })$來更新當前時刻的$V_i(s)$，即
$$V_i(s)\leftarrow \sum _{a\in A}\pi (a|s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }|s,a\right)V_{i?1}(s^{\prime })\right)$$ 不停迭代后可以收斂。
貝爾曼期望備份有2層加和，內部和與外部和，計算兩次期望，得到一個更新。

蒙特卡洛通過一個回合的經驗平均回報來進行更新
$$V(s_t)\leftarrow V(s_t)+\alpha \left(G_{i,t}?V(s_t)\right)$$蒙特卡洛方法得到的軌跡是已經決定的，采取的動作也是決定的，只更新該軌跡上的所有狀態，與該軌跡無關的狀態都不進行更新。

蒙特卡洛適用于環境未知的情況，動態規劃是有模型的方法；
蒙特卡洛只需要更新一條軌跡的狀態，動態規劃需要更新所有狀態。

2. 時序差分

是介于蒙特卡洛和動態規劃之間的方法，免模型，可以從不完整的回合中學習，并結合了自舉的思想。

目的：對某個給定的策略$\pi$，在線計算出七價值函數$V_{\pi }$，即一步一步的算。最簡單的算法是一步時序差分，即TD(0)。每往前走一步，就做一步自舉，用得到的估計回報$r_{t+1}+\gamma V(s_{t+1})$來更新上一時刻的$V(s_t)$：
$$V(s_t)\leftarrow V(s_t)+\alpha \left(r_{t+1}+\gamma V(s_{t+1})?V(s_t)\right)$$其中估計回報$r_{t+1}+\gamma V(s_{t+1})$稱為時序差分目標，是帶衰減的未來獎勵的總和。

時序差分目標由2部分組成：

1. 走了某一步之后得到的實際獎勵$r_{t+1}$；
2. 利用自舉方法，通過之前的估計來估計$V(s_{t+1})$，且加了折扣因子$\gamma$。

時序差分目標之所以是估計，有2個原因：

1. 時序差分方法對期望值進行采樣；
2. 時序差分方法使用當前的估計的V，而不是真實的$V_{\pi }$。

2.1 時序差分誤差

$$\delta =r_{t+1}+\gamma V(s_{t+1})?V(s_t)$$類比增量式蒙特卡洛：
$$V(s_t)\leftarrow V(s_t)+\alpha \left(G_{i,t}?V(s_t)\right)$$這里的$G_{i,t}$即為$r_{t+1}+\gamma V(s_{t+1})$，$G_{i,t}?V(s_t)$即為$\delta =r_{t+1}+\gamma V(s_{t+1})?V(s_t)$。在蒙特卡洛里，$G_{i,t}$是實際得到的值，因為它已經把一條軌跡跑完了。而時序差分不等軌跡結束，往前走一步，就可以更新價值函數。時序差分只執行一步，狀態的值就更新。蒙特卡洛方法全部執行完之后，到了終止狀態之后，再更新它的值。

對比：

1. 時序差分可以在線學習，每走一步就更新，效率高。蒙特卡洛要等游戲結束才能學習。
2. 時序差分可以從不完整序列上進行學習，蒙特卡洛只能從完整序列上學習。
3. 時序差分可以再連續的環境下（沒有終止）進行學習，蒙特卡洛只能在有終止的情況下學習。
4. 時序差分李永樂馬爾科夫性質，在馬爾可夫環境下有更好的學習效率。蒙特卡洛沒有假設具有該性質。

2.2 時序差分方法的推廣

往前走一步為TD(0)，可以調整步數，變成n步時序差分。如TD(2)即為往前走2步，利用2步得到的回報，使用自舉來更新狀態的價值。因此可以通過調整步數，來調整算法所需要的實際獎勵和自舉。
$$\begin{array}{rl}n=1(TD)G_t^{(1)}& =r_{t+1}+\gamma V(s_{t+1})\\ n=2G_t^{(2)}& =r_{t+1}+\gamma r_{t+2}+{\gamma }^{2}V(s_{t+2})\\ ?& \\ n=\infty (MC)G_t^{\infty }& =r_{t+1}+\gamma r_{t+2}+?+{\gamma }^{T?t?1}{r}_T\end{array}$$當$n=\infty$時，則整個游戲結束后再進行更新，時序差分就變成了蒙特卡洛。

以上為時序差分目標。得到時序差分目標之后，用增量式學習的方法更新狀態的價值：
$$V(s_t)\leftarrow V(s_t)+\alpha \left(G_t^n?V(s_t)\right)$$

3. 自舉與采樣

自舉是指更新時使用了估計。
蒙特卡洛沒有使用自舉，它根據實際的回報進行更新，沒有估計。動態規劃和時序差分使用了自舉。

采樣是指更新時通過采樣得到一個期望。
蒙特卡洛是純采樣的方法。動態規劃沒有采樣，根據貝爾曼期望方程進行更新狀態價值。時序差分使用了采樣，時序差分目標$G$由2部分組成，采樣與自舉。

• 動態規劃：直接計算期望，把所有相關狀態都加和
  $$V(s_t)\leftarrow {\mathbb{E}}_{\pi }[r_{t+1}+\gamma V(s_{t+1})]$$
  

• 蒙特卡洛：在當前狀態下，采取一條支路，在該路徑上更新，即更新該路徑上的所有狀態
  $$V(s_t)\leftarrow V(s_t)+\alpha (G_t?V(s_t))$$
  

• 時序差分：從當前狀態開始，往前走1步，關注局部的步驟
  $$TD(0):V(s_t)\leftarrow V(s_t{)}_{\alpha }\left(r_{t+1}+\gamma V(s_{t+1})?V(s_t)\right)$$
  
  如果時序差分進行廣度的更新，就變成了動態規劃；
  如果時序差分需要深度的更新，就變成了蒙特卡洛。