【論文閱讀---深度強化學習打王者榮耀】Parametrized Deep Q-Networks Learning: Reinforcement Learning with Discrete-Continuous Hybrid Action Space
標題 Parametrized Deep Q-Networks Learning: Reinforcement Learning with Discrete-Continuous Hybrid Action Space
論文地址
https:// arxiv.org/abs/1810.0639 4v1
離散連續空間相關實作程式碼
https:// github.com/cycraig/MP-D QN
關鍵點 離散連續空間
這篇網誌是我在21年3月放在CSDN上的，是一個非常好的透過深度強化學習訓練遊戲中的Agent進行對抗的例子。
騰訊的 AI Lab 在這篇文章中提出了P-DQN演算法, 文章關註 Real Time Strategic (RTS) games 中的套用 (discrete-continuous hybrid action space) 中的問題，並且在旗下的王者榮耀遊戲中進行實驗測試。
摘要
目前大多數深度強化學習演算法要求 action space 要麽是離散的 (e.g., Go and Atari) ，要麽是連續的 (e.g. MuJoCo and Torcs) , 為解決 Real Time Strategic (RTS) games 中的套用問題，文章提出了一種可以解決離散連續混合空間中問題的P-DQN演算法。
在計算完整體的參數後，演算法首先從一個 discrete set [K] 中選取一個上層的離散 action , 再選擇一個連續的下層 parameter x_k\in \mathcal{X_k} , 這個 parameter 和先前選擇的離散動作相關。這裏 \mathcal{X_k} 是一個包含所有 k \in [K] 對應的離散集合。 定義動作空間如下：
\mathcal{A} = \{(k, x _k) |x_k\in \mathcal{X_k} \ \rm{for \ all\ } \mathcal{k} \in [K] \} \ \ \ \ (1.1)
該文章的方法可以看成將DQN拓展到混合空間，首先定義了一個 deterministic function ,用於將 state 和每一個 discrete action 對映到 continuous parameter ;文章還定義了一個 action-value function ,用於將 state 和有限的混合動作對映到真實的 values
值得註意的是，下層的 continuous parameter 是可選的，不同的離散 action 之間可以擁有相同的 continuous parameter
Parametrized Deep Q-Networks (P-DQN)
考慮一個擁有(1.1)中 action space \mathcal{A} 的MDP，對於 a \in \mathcal{A} ，有 Q(s, a) = Q(s, k, x_k) 。定義在 t 時刻選擇的離散動作為 k_t ，關聯的 continuous parameter 為 x_{k_t} ，現在 Bellman equation 變成:
Q(s_t, k, x_k) = \mathop{\mathbb{E}}\limits_{r_t, s_{t+1}}[ r_t + \gamma \ \mathop{\rm{max}}\limits_{k \in [K]} \mathop{\rm{sup}}\limits_{x_k \in \mathcal{X_k}} \it{Q} (s_{t+1}, k, x_k)|s_t = s, a_t = (k_t, x_{k_t})] \ \rm(3.1)
對於等式右邊，對每\mathcal{k} \in [K] 先計算 {x_k^ = \rm{argsup}{x_k \in \mathcal{X_k}} \ \it{Q}(s{t+1}, k, x_k)} ，接著選擇最大的 Q(s_{t+1, k , x_k^*})
值得註意的是，當 function Q 固定，對於任何 s \in S 以及 k \in [K] ，可以將 \ \rm{argsup_{\it{x_k \in \mathcal{X}_k}} \ \it{Q}(s, k, x_k)} 視作函數 x_k^Q : S \to \mathcal{X}_k ，則(3.1)中的 Bellman equation 可以改成
Q(s_t, k, x_k) = \mathop{\mathbb{E}}\limits_{r_t, s_{t+1}}[r_t + \gamma \ \mathop{\rm{max}}\limits_{k \in [K]} \it{Q}(s_{t+1}, k, x_k^Q(s_{t+1}))|s_t = s]
和DQN的思想一樣，用深度神經網絡 Q(s, k, x_k; w) 近似 Q(s, k, x_k) 用一個 deterministic policy network x_k(.;\theta):S \to \mathcal{X}_k 來近似 x_k^Q 。當 w 固定的時候，我們希望找到一組 \theta 滿足:
Q(s,k, x_k(s;\theta);w) \approx \mathop{\rm{sup}}\limits_{x_k \in \mathcal{X}_k} Q(s, k ,x_k; w) \rm{ \ for \ each \ }\mathcal{k} \in [K] \ \ (3.2)
設 w_t,\theta_t 為 t 時刻的 value network 和 deterministic policy network 的參數，對於固定的 n\ge1 ，定義 n-step 目標 y_t 為:
y_t = \sum_{i=0}^{n-1} \gamma^ir_{t+i}+\gamma^n\mathop{\rm{max}}\limits_{k \in [K]}Q(s_{t+n}, k, x_k(s_{t+n}, \theta_t); w_t) \ \ \ \ (3.3)
定義兩個 loss function ：
\mathcal{l_t^Q(w) = \frac{1}{2}[Q(s_t, k_t, x_{k_t};w)-y_t]^2} \ \ \rm{and} \ \ \mathcal{l_t^\Theta(\theta) = -\sum_{k=1}^{\rm{K}}\it{Q}(s_t, k, x_k(s_t; \theta);w_t)} \ \ \ \ (3.4)
文章用 stochastic gradient methods 更新 weights 。當 w 固定時，為最小化(3.4)中的 \mathcal{l_t^\Theta(\theta)} ，理想情況下可以透過一個符合 two-timescale update rule 的方式來完成。具體來說，更新 w 的時候用到的 stepsize \alpha_t 和更新 \theta 的 stepsize \beta_t 比較微不足道( asymptotically negligible )。同時需要 {\alpha_t, \beta_t} 滿足Robbins-Monro condition
具體演算法如下:
需要註意的是，在探索過程中演算法需要一個定義在 \mathcal{A} 上的分布 \xi ，實踐中可以為 \mathcal{A} 上的均勻分布。
The Asynchronous n-step P-DQN Algorithm
為了加速訓練過程，仿照 n-step DQN 文章提出了 asynchronous n-step P-DQN 。考慮一個每一個 process 計算自己的 local gradient 並和全域 「parameter server」 互動的 centralized distributed training framework ：每一個 process 執行一個獨立的環境產生轉移軌跡並用自己的轉移來計算 w 和 \theta 的梯度，這些梯度後續被一起用於計算全域的 parameters 。
具體演算法如下:
實驗
文章一共采用了三個實驗場景，分別是:1) a simulation example, 2) scoring a goal in simulated RoboCup soccer, 3) the solo mode in game KOG。
前面兩個實驗的詳細設定和結果可以可以透過閱讀論文了解，下面介紹第三個實驗:
Solo mode of King of Glory
在實驗中， game 的 state 用以179維的特征向量表示，數據由 game engin 直接生成。這些特征包含兩個部份( basic attributes of the units and the relative positions of other units with respect to the hero controlled by the player as well as the attacking relations between units )
實驗將英雄的 action 簡化成 K = 6 的離散動作: Move, Attack,UseSkill1,UseSkill2,UseSkill3,Retreat 。 一些 action 可能擁有額外 continuous parameters 來使行為更加精準。例如 k = Move ,方向由 x_k = \alpha 定義， \alpha \in [0,2\pi] 。值得註意的是，每一個英雄的技能是獨一無二的，完整的動作列以及關聯的 parameters 如下:
由於 Magic Point 和 Cool Down 的相關限制，實際操作中 max_{k \in [K]} 被替換成 max_{k \in [K] and \ k \ is \ usable} ,多步目標由前文的(3.3)計算
The reward for KoG
相關描述如下:
整體 reward 公式如下:
公式中系數只是大概的設定了一下，文章中的實驗在一定範圍內對這些數據並不是特別敏感。
文章采取了 Algorithm 2 ( with 48 parallel workers )， network x(\theta) \mu(\theta) are both in the size of 256-128-64 nodes in each hidden layer , Q(w) is in size of 256-128-64-64 為了縮短 episode length ,采用了跳幀( frame skipping )技術並設定 frame skipping parameter 為2。
更進一步，對 Algorithm 2 中的參數，有: t_{max} = 20 ；訓練用到 \epsilon-greedy(\epsilon = 0.255) 來采樣，具體為前五個動作概率為0.005而 Retreat 概率為0.0005；如果采樣得到的動作是不可行的，就在可行的動作中用貪心方法選擇。 learning rate 設定為0.001
文章中演算法與DDPG對比結果如下:
總結
兩年前寫這篇網誌的時候貌似Agent已經可以達到黃金段位了，過了兩年應該有新的方法得到段位更高的Agent。
