強化學習-Q-Learning算法

1. 前言

Q-Learning算法也是時序差分算法的一種，和我們前面介紹的SARAS不同的是，SARSA算法遵從了互動序列，根據目前的真實行動進行價值估計；Q-Learning算法沒有遵循互動序列，而是在目前時刻選擇了使價值最大的行動。

2. Q-Learning

Q-Learning算法在計算目前時刻的行動-狀态價值\(q_t(s_t,a_t)\)時選擇了目前狀态使價值最大的行動\(max_aq_{t-1}(s_{t})\)。

Q-Learning的疊代公式在SARAS的基礎上進行了一些修改，如下：

\[q_{t}(s_{t},a_{t}) = q_{t-1}(s_{t-1},a_{t-1}) + \frac{1}{N}(r_t + \gamma*max_aq_{t-1}(s_t) - q_{t-1}(s_{t-1},a_{t-1}))

\]

3. Q-Learning代碼實作

Q-Learning公式和SARAS的公式十分相像，是以政策提升依然沒有變化，政策評估有一點微小的修改(完整代碼GitHub)。

def q_learn_eval(self, agent, env):
    state = env.reset()
    prev_state = -1
    prev_act = -1
    while True:
        act = agent.play(state, self.epsilon)
        next_state, reward, terminate, _ = env.step(act)
        if prev_act != -1:
            # qlearning的疊代公式
            return_val = reward + agent.gamma * (0 if terminate else np.max(agent.value_q[state, :]))
            agent.value_n[prev_state][prev_act] += 1
            agent.value_q[prev_state][prev_act] += (return_val - agent.value_q[prev_state][prev_act]) / agent.value_n[prev_state][prev_act]

        prev_act = act
        prev_state = state
        state = next_state

        if terminate:
            break
           

4. SARAS和Q-Learning比較

SARSA算法和Q-Learning算法在公式上的不同，實際上這兩種算法代表了兩種政策評估的方式，分别是On-Policy和Off-Policy。

• On-Policy：對值函數的更新是完全依據互動序列進行的，我們在計算時認為價值可以直接使用采樣的序列估計得到。
• Off-Policy：更新值函數時并不完全遵循互動序列，而是選擇來自其他政策的互動序列的子部分替換了原本的互動序列。從算法的思想上來說，Q-Learning的思想更複雜，它結合了子部分的最優價值，更像是結合了價值疊代的更新算法，希望每一次都使用前面疊代積累的最優結果進行更新。

5. 總結

對于Q-Learning和SARSA這樣的時序差分算法，對于小型的強化學習問題是非常靈活有效的，但是在大資料時代，異常複雜的狀态和可選動作，使Q-Learning和SARSA要維護的Q表異常的大，甚至遠遠超出記憶體，這限制了時序差分算法的應用場景。在深度學習興起後，基于深度學習的強化學習開始占主導地位，是以從下一篇開始我們開始讨論深度強化學習的模組化思路。