強化學習：如何處理大規模離散動作空間

在深度學習大潮之後，搜索推薦等領域模型該如何升級迭代呢？強化學習在遊戲等領域大放異彩，那是否可將強化學習應用到搜索推薦領域呢？推薦搜索問題往往也可看作是序列決策的問題，引入強化學習的思想來實現長期回報最大的想法也是很自然的，事實上在工業界已有相關探索。因此後面將會寫一個系列來介紹近期強化學習在搜索推薦業務上的應用。

本次將介紹兩篇解決強化學習中大規模離散動作空間的論文。

第一篇是 DeepMind 在2015年發表的，題目為：

Deep Reinforcement Learning in Large Discrete Action Space

鏈接為：

https://arxiv.org/abs/1512.07679

適合精讀；

第二篇是發表在 AAAI2019 上，題目為 ：

Large-scale Interactive Recommendation with Tree-structured Policy Gradient

鏈接為：

https://arxiv.org/abs/1811.05869

適合泛讀。

一、Introduction

傳統的推薦模型在建模時只考慮單次推薦，那是否可以考慮連續推薦形成的序列來改善推薦策略呢？事實上已經有一些工作引入強化學習來對推薦過程進行建模。但有個問題就是推薦場景涉及的 item 數目往往非常高，大規模離散動作空間會使得一些 RL 方法無法有效應用。比如基於 DQN 的方法在學習策略時使用：

其中 A 表示 item 集合，對 A 中所有 item 均要計算一次 Q 函數。如果 |A| 非常大的話從時間開銷上來講無法接受。但這個方法有個優點就是 Q 函數往往在動作上有較好的泛化性。而基於 actor-critic 的方法中 actor 網絡往往類似一個分類器，輸出經過 softmax 後是動作上的概率分佈，所以就避免了 DQN 類方法中的性能問題，但是這類方法缺點就是對未出現過的 action 泛化能力並不好。所以就需要尋找一種針對動作空間來說複雜度為次線性而且在動作空間上能較好泛化的方法。

二、Wolpertinger Architecture

該算法是第一篇論文提出來的，整體流程如下。

整個算法基於 actor-critic 框架，通過 DDPG 來訓練參數，這裡只介紹文章的重點部分即 action 的選擇。算法先經過

得到 proto-action

，但

可能並不是一個有效的 action ，也就是說

。然後從 A 中找到 k 個和

最相似的 action ，表示為：

該步可在對數時間內得到近似解，屬於次線性複雜度，避免了時間複雜度過高的問題。但是有些 Q 值低的 action 可能也恰好出現在

的周圍，所以直接選擇一個和

最接近的 action 並不是很理想的做法。為了避免選出異常的 action ，需要通過 action 對應的 Q 值再進行一次修正，表示為：

其中涉及的參數

包括 action 產生過程的

和 critic 網絡的

。通過 Q 值的篩選可使得算法在 action 選擇上更加魯棒。

三、TPGR 模型

該算法是第二篇論文提出來的，主要思路是對 item 集合先預處理聚類從而解決效率問題，模型框架圖如下。左半部分展示了一個平衡的樹結構，整顆樹對應著將 item 全集進行層次聚類的結果，每個根節點對應一個具體的 item 。右半部分展示瞭如何基於樹結構進行決策，具體來說每個非葉節點對應一個策略網絡，從根節點到葉子節點的路徑中使用多個策略網絡分別進行決策。TPGR 模型可使決策的複雜度從

降低到

，其中 d 表示樹的深度。下面分別介紹下左右兩部分。

TPGR模型框架圖

• 平衡的層次聚類

這步目的是將 item 全集進行層次聚類，聚類結果可通過樹結構進行表示。文中強調這裡是平衡的樹結構，也就是說子樹高度差小於等於1，而且子樹均符合平衡性質。設樹的深度為 d ，除去葉子節點的父節點外其他中間節點的子樹數均為 c ，可以得到 d 、c 和 item 數目 |A| 的關係如下：

涉及如何表示 item 和如何進行聚類兩個問題。第一個問題，可以使用評分矩陣、基於矩陣分解方法得到的隱向量等方法作為 item 的表示。而第二個問題，文章提出了兩種方法。篇幅有限，只介紹基於 Kmeans 改進的方法，具體來說：先進行正常的 Kmeans 聚類得到的簇中心 ( c 個 ) ，然後遍歷所有簇，以歐幾里得距離作為相似度指標將和簇中心最近的 item 加到當前簇中，遍歷所有簇一遍後繼續循環遍歷所有簇，直到將所有 item 都進行了分配為止。通過這種分配的方式可使得最後每個簇的 item 數目基本一致，也就達到了平衡的要求。

• 基於樹結構的策略網絡

之前提到，每個非葉節點均對應一個策略網絡。其輸入是當前節點對應的狀態，輸出則是每個子節點上的概率分佈，也就是移動到每個子節點的概率。在上面的框架圖中，根節點為

，根據其策略網絡輸出的概率移動到

，以此類推，最後到

，將

推薦給 user 。策略網絡具體採用 REINFORCE 算法，梯度更新公式為：

其中

表示

策略下狀態 s 採取動作 a 的期望累積回報，可通過採用抽樣來進行估計。

四、總結

一般推薦系統中會有召回步驟將候選的 item 範圍縮小到幾十到幾百量級，所以從這個角度來看處理大規模離散動作的必要性就不那麼大了。

TPGR 模型中平衡樹和子樹數目限制只是為了使時間複雜度保證是對數量級，也就是解決大規模離散動作空間的前提。而 item 分佈都會有傾斜的情況，所以實際情況下將所有 item 集合聚類成數目基本一致的多個簇在實際情況下並不合理。這點肯定會影響到模型效果，所以樹的構建可能還需要更多的探索和嘗試。

楊鎰銘，滴滴出行高級算法工程師，碩士畢業於中國科學技術大學，知乎「記錄廣告、推薦等方面的模型積累」專欄作者。