- 簡介
- 另一個網格世界的例子
- 迭代方法
- 迭代方法策略評估
- 實現 - 迭代方法策略評估
- 迷你項目 part1
- 動作值
- 實現 - 動作值
- 迷你項目 part2
- 策略改進
- 實現 - 策略改進
- 迷你項目 part3
- 策略迭代
- 實現 - 策略迭代
- 迷你項目 part4
- 截斷策略迭代
- 實現 - 截斷策略迭代
- 迷你項目 part5
- 值迭代
- 實現 - 值迭代
- 迷你項目 part6
- 知識檢驗
- 總結
- 在动态规划设置中，智能体完全了解表示环境特性的马尔可夫决策流程 (MDP)。
- 这比强化学习设置简单多了，在强化学习设置中，智能体一开始不知道环境如何决定状态和奖励，必须完全通过互动学习如何选择动作。
- 問題：4個方格，從左上移動，目標是右下，在越快的時間內完成。
- 環境: 左下是大山，只有經過reward就是-3，達到終點reward是5，其餘只要每多走一步reward是-1。
- Step1: 給定一個policy，來決定每個狀態下，agent選擇可能動作的機率。
- 假設是隨機性策略，即agent從一組可能的動作裡，平等的選擇其中一個。
- Step2: 推論對應的狀態值函數。
- 根據貝爾曼方程式，任何時間的狀態值為當下的即時獎勵 + 下個時間的狀態值。
- 解出方程式。
- 我們現在已經知道，如果智能體從該狀態開始，可以獲得的獎勵。
- 實作上，環境很複雜，方程式也對應複雜，不太能直接解方程式，而是要透過迭代方式。
- Step3: 迭代方法
- 隨機猜測每個狀態函數值(假設都是0)
- 改寫貝爾曼方程式，大V表示對函數值的當前猜測，將使用這個規則不斷更新猜測S1的狀態。
- 完成S1~S3的初步猜測。
- Step4: 在重複迭代一次，會發現逐漸趨近step計算出來的結果。
- Iterative Policy Evaluation
- 根據貝爾曼方程式進行迭代。
- pseudo code
- 先隨機猜測(通常都是猜0)。
- 更新每一個state。
- 檢查每個state的變化幅度。
- 關聯性說明
- 對於每一個狀態，智能體都可以選擇任何一個潛在狀態的動作，並進入任何一個潛在的後續狀態。
- 貝爾曼方程式可以幫助我們將父狀態的值與所有潛在後續狀態的值進行關聯。
import numpy as np
# 從"策略"推出"狀態值函數"
def policy_evaluation(env, policy, gamma=1, theta=1e-8):
# 初始化所有狀態(通常都是0)
V = np.zeros(env.nS)
# 對所有狀態不斷進行更新
while True:
# 初始狀態差異的幅度
delta = 0
# 一一開始更新每個狀態
for s in range(env.nS):
Vs = 0
# 取出每個狀態下對應的policy
for a, action_prob in enumerate(policy[s]):
# 將對應的action丟到env，取得env所回饋的資訊
for prob, next_state, reward, done in env.P[s][a]:
# 根據貝爾曼方程式進行迭代
Vs += action_prob * prob * (reward + gamma * V[next_state])
# 更新狀態差異的幅度
delta = max(delta, np.abs(V[s]-Vs))
V[s] = Vs
# 檢查是否已滿足最小差異幅度
if delta < theta:
break
return V- 上面已經從估算策略推出狀態值函數。
- 現在要從上面狀態值函數推出對應的動作值函數。
- 對於更複雜的環境，智能體的每個狀態下所選擇的動作是不確定性的。
# 從"狀態值函數"推出"動作值函數"
def q_from_v(env, V, s, gamma=1):
# 初始化每個動作值
q = np.zeros(env.nA)
# 針對每個可執行的action
for a in range(env.nA):
# 在每個狀態下，每個可執行action的動作值
for prob, next_state, reward, done in env.P[s][a]:
# policy -> V(狀態值) -> q(動作值)
q[a] += prob * (reward + gamma * V[next_state])
return q- Iterativie Policy Evaluation
- 從一個策略找出狀態值函數
- Policy Improvement
- 從狀態值函數找出至少跟當前一樣好的策略
- Iterativie Policy Evaluation 跟 Policy Improvement 整合
- 透過動作值函數來找出進行Policy Improvement
- 定義：怎樣叫做更好的策略
- 就是在任何時間點下，遵循更好的策略的狀態值函數，一定都比原本策略好。
- pseudo code
- 找出每個state下的遵循策略所產生所有對應的動作值。
- 選擇每個state下的最大動作值。
def policy_improvement(env, V, gamma=1):
policy = np.zeros([env.nS, env.nA]) / env.nA
# 對於環境每個state找出所有動作值
for s in range(env.nS):
# 從狀態值推出對應的動作值
q = q_from_v(env, V, s, gamma)
# 建立一個隨機性策略(對於最大的動作值都是採取相同的機率)
best_a = np.argwhere(q==np.max(q)).flatten()
policy[s] = np.sum([np.eye(env.nA)[i] for i in best_a], axis=0)/len(best_a)
return policy- 策略迭代的兩大重點:
- Iterative Policy Evaluation: 利用策略評估來估計策略的值函數，判斷該策略的效果如何。
- Policy Improvement: 利用策略的值函數構建至少比現在好(或等同)的新策略。
- pseudo code
- 對於每個狀態，選擇每個動作的機率皆是相同。
- 使用策略評估來獲得相應的值函數。
- 使用策略改善來獲得至少比現在好(或等同)的新策略。
- 不斷重複這些步驟，使策略沒有任何變化。
import copy
def policy_iteration(env, gamma=1, theta=1e-8):
# 對於每個狀態，選擇每個動作的機率皆是相同
policy = np.ones([env.nS, env.nA]) / env.nA
while True:
# 使用策略評估來獲得相應的值函數
V = policy_evaluation(env, policy, gamma, theta)
# 使用策略改善來獲得至少比現在好(或等同)的新策略
new_policy = policy_improvement(env, V)
# 不斷重複這些步驟，使策略沒有任何變化。
if (new_policy == policy).all():
break;
policy = copy.copy(new_policy)
return policy, V- Truncated Policy Iteration
- 優化:
- 首先，策略評估是一個迭代算法。
- 策略評估完成一輪的迭代次數是根據theta所決定。
- theta越小，所得到的值函數越準確，相對所花費的時間越長。
- 然而真的需要這麼準確的值函數嗎??
- 優化方式: 不需要給theta值，而是直接給定一個絕對的迭代次數。
- 重點: 我們不需要一個完美的值函數才能獲得最佳策略。
- 右邊的值函數雖然不是最佳的值函數，但大致的相對大小都是沒錯，這樣就可以幫助我們決定一個更合的側略了。
def truncated_policy_evaluation(env, policy, V, max_it=1, gamma=1):
# 設定當前迭代次數
num_it = 0
# 不利用theta值，而是直接給定一個絕對的迭代次數來判斷是否需要繼續迭代
while num_it < max_it:
# 對於環境每個state找出所有動作值
for s in range(env.nS):
v = 0
# 從狀態值推出對應的動作值
q = q_from_v(env, V, s, gamma)
# 取出每個狀態下對應policy所選取的動作跟其機率
for a, action_prob in enumerate(policy[s]):
# 根據貝爾曼方程式進行迭代
v += action_prob * q[a]
V[s] = v
num_it += 1
return Vdef truncated_policy_iteration(env, max_it=1, gamma=1, theta=1e-8):
# 初始化所有狀態(通常都是0)
V = np.zeros(env.nS)
# 對於每個狀態，選擇每個動作的機率皆是相同
policy = np.zeros([env.nS, env.nA]) / env.nA
while True:
# 使用策略改善來獲得至少比現在好(或等同)的新策略
policy = policy_improvement(env, V)
old_V = copy.copy(V)
# 使用截断策略评估來更新值函數
V = truncated_policy_evaluation(env, policy, V, max_it, gamma)
# 不斷重複這些步驟，使策略對應的值函數收斂。
if max(abs(V-old_V)) < theta:
break;
return policy, V- 回顧之前兩種不同的迭代方式：
- Policy Iteration: 當值收斂到某種程度才停止迭代。
- Truncated policy iteration: 當達到某個迭代次數才停止迭代。
- Value Iteration: 只執行一次polcy evaluation。
- 優點: 可以簡化計算公式。
- 簡化 step1: 簡化policy improvement
- 簡化 step2: 因為policy improvement完成後，會緊接著下次policy evaluation，直接至換成新的policy
- 簡化 step3: 簡化polcy evaluation公式
- pseudo code
- 先對值函數進行初始猜測。
- 算法循環訪問所有狀態空間。
- 應用更新規則以便更準確猜測值函數。
- 檢查值函數是否逼近收斂。
- 有，則停止
- 沒有，繼續
- 收斂後需要完成最後一步，才能獲得最終值函數所對應的策略。
def value_iteration(env, gamma=1, theta=1e-8):
# 先對值函數進行初始猜測。
V = np.zeros(env.nS)
while True:
delta = 0
# 算法循環訪問所有狀態空間
for s in range(env.nS):
v = V[s]
# 應用更新規則以便更準確猜測值函數
V[s] = max(q_from_v(env, V, s, gamma))
# 檢查值函數是否逼近收斂
delta = max(delta,abs(V[s]-v))
if delta < theta:
break
# 收斂後需要完成最後一步，才能獲得最終值函數所對應的策略
policy = policy_improvement(env, V, gamma)
return policy, V
-
名詞解釋
- 迭代方法
- 迭代策略评估
- 动作值的估值
- 策略改进
- 策略迭代
- 截断策略迭代
- 值迭代