實現SARSA算法和對應的強化學習智能體

• SARSA（State-Action-Reward-State-Action）是一種強化學習算法，主要用于估計給定策略下的最優狀態-動作價值函數（QQ 函數）。它是一種在軌策略（on-policy）算法，意味著它使用當前策略來選擇動作。

如何實現SARSA算法（狀態-行動-獎勵-狀態-行動）

以及如何使用SARSA開發和訓練智能體

SARSA可以應用與無模型種子問題，并對未知馬爾科夫決策過程MDP的價值函數進行優化。

前期準備

import numpy as np
import random

實現步驟

使用一個函數實現SARSA學習算法的更新

并使用$?$-greedy的探索策略。

兩者結合就可以得到一個在給定的強化學習環境中工作的完整智能體。

1. 定義一個實現SARSA算法的函數，并用0初始化狀態-動作價值

   def sarsa(env, max_episodes):grid_action_values = np.zeros((len(env.distinct_states), env.action_space.n))
   

2. 根據環境的配置更新目標狀態和炸彈狀態的價值

   grid_action_values[env.goal_state] = 1
   grid_action_values[env.bomb_state] = -1
   

3. 定義折扣因子gamma和學習率超參數$\alpha$ 。同樣創建一個別名q表示grid_action_values

   gamma = 0.99  # discounting factor
   alpha = 0.01  # learning rate
   # q: state-action-value function
   q = grid_action_values
   

4. 實現外部循環

   for episode in range(max_episodes):step_num = 1done = Falsestate = env.reset()action = greedy_policy(q[state], 1)
   

5. 實現內循環，其中包括SARSA學習的更新步驟

   while not done:next_state, reward, done = env.step(action)step_num += 1decayed_epsilon = gamma ** step_num  # Doesn't have to be gammanext_action = greedy_policy(q[next_state], decayed_epsilon)q[state][action] += alpha * (reward + gamma * q[next_state][next_action] - q[state][action])state = next_stateaction = next_action
   

   1. 初始化：選擇一個初始狀態 $S$ 和在該狀態下執行的動作 $A$。
   2. 循環直到結束：
      • 執行動作 $A$，觀察獎勵 $R$ 和下一個狀態 $S^{\prime }$。
      • 使用策略選擇在狀態 $S^{\prime }$ 下要執行的動作 $A^{\prime }$。
        在數學語言中，這些步驟可以表示為：
        $$\begin{gathered} S^{\prime },R,\text{done}=\text{env.step}(A) \\ \text{step\_num}+=1 \\ ?={\gamma }^{\text{step\_num}} \\ {A}^{\prime }=\text{greedy\_policy}(Q(S^{\prime }),?) \end{gathered}$$
   3. 更新 Q 值：
      • 更新 Q 值 $Q(S,A)$ 使用以下公式：
        $Q(S,A)\leftarrow Q(S,A)+\alpha \left[R+\gamma Q(S^{\prime },A^{\prime })?Q(S,A)\right]$
        其中：
      • $\alpha$ 是學習率。
      • $\gamma$ 是折扣因子。
      • $Q(S^{\prime },A^{\prime })$ 是在狀態 $S^{\prime }$ 下執行動作 $A^{\prime }$ 的 Q 值。
   4. 轉移到下一個狀態和動作：
      • 將當前狀態 $S$ 更新為下一個狀態 $S^{\prime }$。
      • 將當前動作 $A$ 更新為下一個動作 $A^{\prime }$。
        在數學語言中，這些步驟可以表示為：
        $$\begin{gathered} S=S^{\prime } \\ A=A^{\prime } \end{gathered}$$
   5. 重復步驟 2-4，直到達到終止狀態（done 為 True）。

6. 在SARSA的最后一步，可視化狀態-動作價值函數

   visualize_grid_action_values(grid_action_values)
   

7. 實現智能體要使用的$?$-greedy策略 greedy_policy()

   def greedy_policy(q_values, epsilon):"""Epsilon-greedy policy """if random.random() >= epsilon:return np.argmax(q_values)else:return random.randint(0, 3)
   

   • if random.random() >= epsilon:：這里，random.random() 生成一個0到1之間的隨機浮點數。如果這個隨機數大于或等于 epsilon，那么執行 if 分支中的代碼。
     • return np.argmax(q_values)：如果條件為真，函數返回 q_values 數組中最大值的索引。這個索引代表了具有最高Q值的動作，也就是我們基于當前知識認為的最佳動作。
   • else:：如果 random.random() 生成的隨機數小于 epsilon，則執行 else 分支中的代碼。
     • return random.randint(0, 3)：在這種情況下，函數返回一個從0到3（包含0和3）的隨機整數，代表隨機選擇的動作。這表明在 epsilon-greedy 策略中，有一定概率（由 epsilon 決定）我們會選擇一個隨機動作而不是最佳動作，以鼓勵探索環境。

8. 實現__main__函數并運行SARSA算法

   if __name__ == "__main__":max_episodes = 4000env = GridworldV2Env(step_cost=-0.1, max_ep_length=30)sarsa(env, max_episodes)
   

   

工作原理

SARSA是一種基于時序差分學習的在軌策略（on-policy）控制算法。

本節使用SARSA算法估計最優狀態-動作價值。SARSA算法與Q學習非常相似。

在每次迭代中，SARSA算法都會根據當前的狀態和動作來更新價值表，目標是找到每個狀態下的最優策略。通過這種方式，算法可以學習如何在給定的環境中取得最佳的行動策略。

總結一下，SARSA 算法的核心在于它在更新 Q 值時考慮了下一個狀態 $S^{\prime }$ 和下一個動作 $A^{\prime }$，而不是像 Q-Learning 那樣考慮在下一個狀態 $S^{\prime }$ 下所有可能動作的最大 Q 值。這使得 SARSA 是一種同策略（on-policy）方法，因為它使用當前策略來選擇下一個動作 $A^{\prime }$。

Initialize $Q(s,a),?s\in \mathcal{S},a\in \mathcal{A}(s)$, arbitrarily, and $Q(terminal?state,?)=0$
Repeat (for each episode):
$\mathrm{Initialize}S$
Choose $A$ from $S$ using policy derived from $Q$ (e.g., $?$-greedy)
Repeat (for each step of episode):
$\mathrm{Take}\mathrm{action}A,\mathrm{observe}R,S^{\prime }$
Choose $A^{\prime }$ from $S^{\prime }$ using policy derived from $Q$ (e.g., $?$-greedy)
$Q(S,A)\leftarrow Q(S,A)+\alpha \left[R+\gamma Q(S^{\prime },A^{\prime })?Q(S,A)\right]$
$\dot{S}\leftarrow S^{\prime };$ $A\leftarrow A^{\prime };$ until $S$ is terminal

初始化

• $Q(s,a)$ 初始化：對于所有狀態 $s$ 和在狀態 $s$ 下可采取的動作 $a$，$Q$ 函數被任意初始化。$Q$ 函數表示在特定狀態 $s$ 下采取動作 $a$ 的期望回報。
• 終端狀態 $Q$ 值：對于終端狀態，所有動作的 $Q$ 值設為0，因為終端狀態之后沒有進一步的獎勵。

算法流程

1. 重復（每個劇集）：

   • 對于每個劇集（episode），算法會進行以下步驟。
   • 初始化狀態 $S$：選擇一個初始狀態 $S$。

2. 選擇動作 $A$：

   • 根據當前的 $Q$ 函數（例如使用 $?$-貪婪策略）從狀態 $S$ 中選擇一個動作 $A$。

3. 重復（每個劇集的每一步）：

   • 采取動作并觀察：執行動作 $A$，觀察獲得的獎勵 $R$ 和下一個狀態 $S^{\prime }$。
   • 選擇下一個動作 $A^{\prime }$：在新的狀態 $S^{\prime }$ 下，使用基于 $Q$ 函數的策略（如 $?$-貪婪）選擇下一個動作 $A^{\prime }$。

4. 更新 $Q$ 函數：

   • 使用以下公式更新 $Q$ 函數：
     $$Q(S,A)\leftarrow Q(S,A)+\alpha \left[R+\gamma Q(S^{\prime },A^{\prime })?Q(S,A)\right]$$

   • 其中，$\alpha$ 是學習率，$\gamma$ 是折扣因子。

5. 更新狀態和動作：

   • 將 $S^{\prime }$ 更新為新的當前狀態 $S$。
   • 將 $A^{\prime }$ 更新為新的當前動作 $A$。
   • 這個過程一直重復，直到 $S$ 成為終端狀態。

構建基于Q學習的智能體

Q 學習可以應用于無模型的強化學習問題。它支持離軌（off-policy）學習，為使用其他策略或其他智能體收集經驗的問題提供了實用的解決方案。

本節將構造一個可工作的強化學習智能體，使用Q學習算法生成狀態-價值函數

前期準備

impoet numpy as np
import random

實現步驟

用一個函數實現Q學習算法，并使用$?$-greedy的探索策略。

1. 定義一個實現Q學習算法的函數，并用0初始化狀態-動作價值

   def q_learning(env, max_episodes):grid_action_values = np.zeros((len(env.distinct_states), env.action_space.n))
   

2. 根據環境的配置更新目標狀態和炸彈狀態的值

   grid_action_values[env.goal_state] = 1
   grid_action_values[env.bomb_state] = -1
   

3. 定義折扣因子gamma 和學習率超參數 alpha 。同樣創建一個別名q表示grid_action_values

   gamma = 0.99  # discounting factor
   alpha = 0.01  # learning rate
   # q: state-action-value function
   q = grid_action_values
   

4. 實現外部循環

   for episode in range(max_episodes):step_num = 1done = Falsestate = env.reset()
   

5. 實現內循環，其中包括Q學習的更新。此外對$?$-greedy策略使用$?$進行衰減

   while not done:decayed_epsilon = 1 * gamma ** step_num  # Doesn't have to be gammaaction = greedy_policy(q[state], decayed_epsilon)next_state, reward, done = env.step(action)# Q-Learning updategrid_action_values[state][action] += alpha * (reward + gamma * max(q[next_state]) - q[state][action])step_num += 1state = next_state
   

   在 Q-Learning 算法中，Q 值的更新可以用以下數學公式表示：
   設 $Q(s,a)$ 表示在狀態 $s$ 下執行動作 $a$ 的 Q 值。在時間步 $t$ 時，智能體觀察到狀態 $S_t$，執行動作 $A_t$，然后到達新狀態 $S_{t+1}$ 并獲得獎勵 $R_{t+1}$。Q 值的更新公式為：
   $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })?Q(S_t,A_t)]$
   其中：

   • $\alpha$ 是學習率，取值在 0 到 1 之間，決定了新信息對舊信息的覆蓋程度。
   • $\gamma$ 是折扣因子，取值在 0 到 1 之間，用于平衡即時獎勵和未來獎勵。
   • ${\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$ 表示在狀態 $S_{t+1}$ 下所有可能動作的 Q 值中的最大值。
   • $R_{t+1}$ 是在時間步 $t+1$ 收到的獎勵。
     這個公式表示，Q 值的更新等于當前 Q 值加上一個學習率 $\alpha$ 乘以獎勵 $R_{t+1}$ 和折扣后的未來最大 Q 值 $\gamma {\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$ 與當前 Q 值 $Q(S_t,A_t)$ 之差。這個差值稱為 TD 誤差（Temporal-Difference error），它衡量了基于當前估計的 Q 值和基于實際經驗的新估計之間的差異。

6. 最后一步，對狀態-動作價值函數進行可視化

   visualize_grid_action_values(grid_action_values)
   

7. 實現智能體要使用的$?$-greedy策略

   def greedy_policy(q_values, epsilon):"""Epsilon-greedy policy """if random.random() >= epsilon:return np.argmax(q_values)else:return random.randint(0, 3)
   

8. 實現__main__函數，并運行Q學習算法

   if __name__ == "__main__":max_episodes = 4000env = GridworldV2Env(step_cost=-0.1, max_ep_length=30)q_learning(env, max_episodes)
   

工作原理

Q學習算法中涉及Q值的更新，總結為：$Q[s,a]=Q[s,a]+\lambda ?(r+\gamma ?ma{x}_{a^{\prime }}(Q[s^{\prime },a^{\prime }])?Q[s,a])$

$Q[s,a]$ 是當前狀態s和動作q的Q函數值

$ma{x}_{a^{\prime }}(Q[s^{\prime },a^{\prime }])$ 用于從下一步可能的Q值中選擇最大值

兩者的主要區別

• 策略依賴性：SARSA 使用當前策略來選擇下一個動作，而 Q 學習不依賴當前策略來更新 Q 值。
• 探索與利用：SARSA 的探索和利用是同步進行的，而 Q 學習在更新時完全依賴于最大 Q 值，可能會更傾向于探索。
• 穩定性：SARSA 更穩定，因為它直接依賴于當前策略。Q 學習可能會因為其貪婪性質而在某些情況下導致不穩定的學習過程。

SARSA算法比Q學習算法具有更好的收斂性，因此它更適合在線學習或再真實系統上學習。

Q學習更適合于模擬環境或真實系統上資源（如時間/金錢）不太昂貴的情況下訓練。

SARSA 算法的收斂性：

• 同策略更新：SARSA 使用當前策略來選擇下一個動作，這意味著它的更新是基于當前策略的動作后果。因此，它的學習過程與實際策略緊密相關，導致學習過程更加穩定。
• 逐步學習：SARSA 在每個時間步都進行學習，而不是只依賴于最終的獎勵。這種逐步的學習方式有助于避免由于過分依賴未來獎勵估計而產生的潛在不穩定性和偏差。
• 避免過估計：由于 SARSA 在更新 Q 值時考慮了下一個動作的 Q 值，而不是最大 Q 值，它不太可能產生過估計（overestimation）問題，這在 Q 學習中是一個常見問題。

SARSA 適合在線學習和真實系統：

• 在線學習：在線學習要求算法能夠從實時數據中快速且穩定地學習。SARSA 的穩定收斂性使其更適合于這種場景，因為它能夠確保策略的持續改進而不會出現劇烈波動。
• 真實系統：在真實系統中，錯誤的決策可能帶來嚴重的后果。SARSA 的穩定性有助于減少這種風險，因為它不太可能因為過度探索而導致災難性的決策。

Q 學習算法的適用性：

• 探索性：Q 學習算法通過在每個時間步選擇最大化未來獎勵的動作來進行學習，這可能導致算法進行更多的探索。這種探索性在資源充足的情況下是有益的，因為它有助于快速發現最優策略。
• 模擬環境：在模擬環境中，錯誤的決策不會帶來實際損失，因此 Q 學習的探索性可以被充分利用，以快速找到最優解。
• 資源成本：Q 學習可能需要更多的迭代和探索來達到收斂，這在時間和計算資源上可能比較昂貴。在資源受限的情況下，Q 學習可能不是最佳選擇。