iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 24
0
AI & Data

強化學習系列 第 24

強化學習筆記 Day 24

前言

昨天說到強化學習中 TD Learning 方法下,有分為 on-policy 與 off-policy 演算法。在說明 on-policy 與 off-policy 的差別後,我們入兩個演算法的名稱 ─ SARSA 與 Q-Learning,今天我們要先實作 SARSA。

另外昨天的文章有做修正,是關於 SARSA 是 step-update 還是 episode-update 的問題。昨天提到 1994 年 Rummery 與 Niranjan 提出的 SARSA 原型是 episode-update,但在他們的原文中,我並沒有看相關的討論。之後會再去看 Wilson 的原文,不過因為不確定的關係,所以先做修正。

實作 SARSA

今天要實作的 SARSA,這邊分為五個函數處理,分別為

  • 模擬環境中運行 (SimProc)
  • 決定動作 (GetAction)
  • 更新價值函數 (ValueUpdate)
  • 顯示目前最佳策略 (PrintGreedyPolicy)
  • 主程式 (main)

其中 GetAction 用來方便執行 https://chart.googleapis.com/chart?cht=tx&chl=%5Cepsilon - greedy;PrintGreedyPolicy 用於呈現各狀態的最佳動作。因為沒有太多特殊內容,因此下方不特別貼出來說明。若有執行的需求,可以到 GitHub 獲得完整程式碼。

SimProc

負責處理在單一 episode 中遇到的所有事情,包含取得狀態、決定動作、取得回饋、更新價值、判斷是否結束...等過程,程式碼如下:

def SimProc(action_value, reward, trans_mat, steps, gamma, alpha, epsilon):
    # initialize setting
    record = []
    state = np.random.randint(1,15)
    action = GetAction(action_value, epsilon, state)
    for step in range(steps):
        # get next infromation
        next_state = np.argmax(trans_mat[:,state,action])
        next_action = GetAction(action_value, epsilon, next_state)
        record.append([state, action, reward[next_state], next_state, next_action])
        # update action value
        action_value[state, action] = ValueUpdate(action_value, record[step], alpha, gamma)
        # update for next step
        state = next_state
        action = next_action
        if state == 0 or state == 15:
            break
    return action_value

這裡需要特別注意的是,在 record 中有紀錄 next_action,並用於更新動作價值。

註 1 :可以明天與 Q-Learning 比較
註 2 :SARSA 是 State-Action-Reward-State-Action 的開頭縮寫,表示該演算法使用這些參數更新。

ValueUpdate

負責處理動作價值的更新,是 SARSA 與 Q-Learning 區別的核心部分,程式碼如下:

def ValueUpdate(action_value, record, alpha, gamma):
    state = record[0]
    action = record[1]
    reward = record[2]
    next_state = record[3]
    next_action = record[4]
    now_value = action_value[state, action]
    update_value = alpha*(reward + gamma*action_value[next_state, next_action] - now_value)
    value = now_value + update_value
    return value

請特別注意變數 update_value,這邊我們使用「下一步狀態」和「下一步動作」的動作價值,更新動作價值。

註 1 :可以明天與 Q-Learning 比較

main

這個設定 GridWorld 環境參數、演算法參數、移動次數,詳細內容如下:

def main(Episodes):
    # Environment setting
    ActionValue = np.zeros([16,4])
    Reward = np.full(16, -1)
    Reward[0] = 0
    Reward[-1] = 0
    TransMat = np.load('./gridworld/T.npy')
    # parameters setting
    Gamma = 0.99
    Steps = 50
    Alpha = 0.05

    # Execute
    for episode in range(Episodes):
        Epsilon = 1/(episode+1)
        ActionValue = SimProc(ActionValue, Reward, TransMat, Steps, Gamma, Alpha, Epsilon)
        PrintGreedyPolicy(episode, ActionValue)
        #time.sleep(1)

關於環境的設定與之前沒有差異,演算法的部分有兩點要注意

  • 新增一個演算法 alpha,用來決定每次動作價值要更新多少
  • epsilon 改用 1/(episode+1),一樣會浮動,但浮動的狀態比之前的設定更劇烈 (參考書上設定)。

註 1 :Python 的數列起始於 0,因此在計算時寫成 (episode+1)
註 2 :如果想要有迭代更新的感覺,一樣可以把最後一行 '#time.sleep(1)' 前面的 '#' 去除

執行結果

以下為執行 1000 episodes 的策略結果

============================================================
[Greedy Policy]
Episode: 1000
[['*' '<' '<' 'v']
 ['^' '^' '>' 'v']
 ['^' '<' '>' 'v']
 ['^' '>' '>' '*']]
============================================================

算是一個很完美的結果,明天 Q-Learning 表現會如何呢?


上一篇
強化學習筆記 Day 23
下一篇
強化學習筆記 Day 25
系列文
強化學習30

尚未有邦友留言

立即登入留言