強化學習（五）：Model Free Example

動態規劃的局限

用動態規劃求解最優策略是基於agent完全了解MDP（馬爾科夫決策過程）的基礎之上，但是這個方法往往在現實中無法使用：

• agent並不處於上帝視角，只是了解一些或者完全不了解所處的環境（MDP）
• MDP的狀態空間和動作空間過於龐大，以至於人腦或者內存無法記下

迷宮

• 黑色方塊和黃色圓圈是terminal狀態
• 走到黑色方塊扣2分，走到黃色圓圈加100分；除此以外的移動都扣1分
• 假設紅色方塊agent每次從左上角出發，並且只知道可以上下左右移動

現在要找到一種演算法，使得agent能通過歷史的episode找到通向黃色圓圈的最短路徑。

Monte Carlo Control

注意事項：

• 在實現epsilon greedy選擇隨機策略時，加上動作的價值是否相同的判斷。

class MonteCarloAgent(object): def choose(self, state): self._initialize_state(state) actions = self.value_q[state] if random.random() < self.epsilon or _all_equal(actions): # 注意這裡 return random.choice(range(self.act_n)) else: m = max(actions.itervalues()) for k, v in actions.iteritems(): if v == m: return k

這是因為在演算法初始化的時候，各個動作的價值往往設成0，所以在epsilon greedy選擇最優策略的時候，只會選擇同一個策略。而monte carlo又是回合制學習，這將會減緩它的收斂速度。

使用monte carlo control走迷宮，效果如下：

橫軸為回合數，縱軸為平均回報。

Sarsa和Sarsa Lambda

上圖為Sarsa的演算法，Sarsa Lambda可參見圖。

注意事項：

• 在實現Sarsa的學習代碼的時候，並沒有採用固定的學習率 ，而是使用了Monte Carlo Control中的每個狀態動作的探索次數的倒數。

self.value_q[state][action] += error / self.value_n[state][action]

這是因為Sarsa走迷宮的收斂速度相對較快，隨著每個狀態動作的探索次數的增加，將減少對它的學習。

• 在實現Sarsa Lambda的學習代碼的時候，為了防止分母為0，對每個狀態動作的探索次數取倒數的時候，加上1e-6。

self.value_q[s][a] += self.eligibility_trace[s][a] * error / (self.value_n[s][a] + 1e-6)

Sarsa演算法比較保守，它會先預估下一步所使用的策略，再進行學習。使用Sarsa走迷宮，效果如下：

使用Sarsa Lambda走迷宮，效果如下：

Q Learning

注意事項：

• 在實現Q Learning中的學習代碼的時候，使用固定的學習率 。

self.value_q[state][action] += error * self.learning_rate

這是因為Q Learning走迷宮的收斂速度相對較慢，這樣及時每個狀態動作的探索次數的增加，也不會減少對它的學習。

Q Learning演算法比較激進。使用Q Learning走迷宮，效果如下：

參數

• 除了上述學習率 ，還有一個類似的參數 ，表示agent探索的概率。可以使用annealing的辦法，讓agent慢慢減少探索的次數。
• 打折率 表示未來回報對於當下的重要程度。
• 對迷宮設置不同reward，意義是不同的。比如若一般移動由扣1分改成不扣分，則agent的目標變成了到達黃色圓圈，而不需要最快。

總結

本文比較了四種Model Free的演算法：Monte Carlo Control，Sarsa，Sarsa Lambda，Q Learning。

本文代碼位於model free example。

參考

• Model-Free Control
• 莫煩|強化學習

推薦閱讀：