基於強化學習的 Contextual Bandits 算法在推薦場景中的應用

文章作者：楊夢月、張露露

內容來源：滴滴科技合作

出品平臺：DataFunTalk

註：轉載請聯繫原作者。

導讀：本文是對滴滴 AI Labs 和中科院大學聯合提出的 WWW 2020 Research Track 的 Oral 長文 "Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation" 的詳細解讀。

在這篇文章中，滴滴 AI Labs 提出了一種基於強化學習的層次自適應的多臂老虎機的資源限制下的個性化推薦方法 ( HATCH )。該方法將資源限制下的用戶推薦問題建模成一個資源限制下的上下文老虎機問題，並使用層次結構同時達到資源分配策略和個性化推薦策略同時優化的目的。

多臂老虎機是一個非常典型的決策方法，被廣泛的應用於推薦系統中。一般情況下，當多臂老虎機算法觀察到系統當中的狀態 ( state ) 時，會從候選的多個動作 ( action ) 當中選擇一個在環境當中執行，之後得到環境的反饋回報 ( reward )。算法的目標是最大化累計回報，在推薦系統當中，state 一般對應用戶上下文，比如用戶特徵等，action 對應於可供推薦的項目，比如廣告，商品等等。reward 一般為用戶在得到推薦結果之後的反饋，通常情況下會使用點擊率等。多臂老虎機作為一種決策方法，其最重要的就是提供探索 ( exploration ) - 開發 ( exploitation ) 功能。開發是指策略 ( policy ) 採用當前預估出的最佳推薦，探索則是選擇更多非最佳策略從而為深入挖掘用戶喜好提供了可能性。

本文所考慮的問題是，有些時候推薦行為會在系統中產生資源消耗，該資源消耗會影響策略的表現。比如對於一個成熟的電商網站，一般情況下其每天的流量可以被看作一個定值，如果將流量看作一種資源，那麼廣告展示的行為就可以看作一種資源消耗。並且這種消耗是單元消耗，即一次推薦產生的資源消耗為1。資源限制不僅會限制推薦的次數，並且會對探索開發功能產生很大的影響。

目前有很多貪心策略用於資源限制下的上下文多臂老虎機問題，即在訓練的時候完全不考慮資源的分配，而採用"有即分配"的方法。該方法會產生比較大的問題，假設系統每天之內有一個資源預算總量，並且該資源總量比一天總共的推薦次數少得多，那麼這種方法就會在算法執行的早期花掉所有的資源，從而忽視後來的高質量用戶的請求。貪心策略可以被看作"短視"的策略，因為其分配策略不會考慮剩餘的資源以及用戶信息這種較為高級的信息。但是同時考慮資源分配和用戶推薦實際上是一個比較複雜的問題，因為這兩種策略在執行過程中會相互影響，從而很難直接得到比較好的策略結果。

本文為了資源分配的長期規劃，解決貪心策略的短視問題，提出了一種層次自適應的上下文多臂老虎機方法。該方法能夠使用層級結構同時優化資源分配策略與用戶個性化推薦策略。該方法分別設置了兩層策略，上層策略為資源分配，下層策略為個性化推薦，如上圖所示。該方法首先需要做一些預處理，即將系統中存在的大量用戶特徵信息收集起來，並將其進行聚類，得到不同的用戶種類，並得到每個類別出現的概率 ∮ 和類別的特徵中心點 x~。這麼做的原因是，本文假設了在推薦系統當中，雖然用戶反饋會根據推薦策略的不同而產生變化，但是用戶的特徵在一段時間滿足一個固定不變的分布。這個假設使得在學習過程當中，用戶類別的概率和類別特徵的中心點不會產生變化。通過這個假設，可以將上下文多臂老虎機的目標函數將最大化累計回報轉化為最大化單輪期望回報，設每個類別的用戶類別價值為 u，單輪期望回報如下：

其中 p 表示分配資源的概率，但是由於 u 不能直接獲得，所以設計了資源分配層用於估計 u。

設為用戶特徵集合，為用戶反饋集合，則該層在每一輪學習步 t 中，都通過一個線性方程預估出每個用戶類別的價值，則存在以下的線性方程。在得到估計用戶價值的 û 之後，通過解決一個線性規劃問題可以得到資源分配概率，在執行推薦結果之後，使用用戶反饋更新該層參數 θ~。該層使用一個標準的上下文多臂老虎機方法作為推薦方法，採用線性方程估計該方法當中基於用戶特徵的每個推薦項目 action 的預估回報，並採用探索策略進行推薦探索，其策略選擇方法遵循下式：該式子當中第一項為期望回報預估，第二項為置信度，作為探索策略的方法。這種探索策略可以使得較少被執行過的 action 有比僅使用第一項估計產生的被選擇概率更大的機率被選擇。在該用戶被分配了資源之後，將以該個性化推薦結果進行推薦，並得到用戶反饋。得到用戶反饋之後，採用以下式更新個性化推薦層的參數：由於上下文多臂老虎機方法是一種在線學習方法，其沒有一個標準的經驗損失函數用來更新參數，所以一般情況下會使用累計遺憾的程度來描述模型效果。本文中累計遺憾為：表示真實情況中的最佳回報與算法提供的最佳的 action 真實回報之間的差距。本文通過證明，得到累計遺憾為 。模擬實驗採用一個模擬數據生成器，該生成器滿足線性生成規則，在該實驗上分析累計遺憾在不同的實驗設置下與基線之間的對比：

實驗結果說明本文提出的 HATCH 能夠得到低的累計遺憾。

真實數據採用 Yahoo Today Model 的公開數據集，並篩選出了推薦數量最多的6種新聞推薦 action 的 event ( x ( 用戶特徵 ),a ( 推薦新聞 ),r ( 是否點擊 ) ) 進行拒絕採樣的離線驗證。

從圖中看出，在不同的實驗設置下，HATCH 均能達到最佳的平均 CTR。

並且本文分析了探索效果，發現在早期學習過程中，擁有較小估計價值的用戶類別，也存在有稍微大的概率被分配資源的情況。說明不僅在個性化推薦層，事實上在資源分配層該算法也具有一定的探索性，這種探索性使得在分配資源的過程中能夠首先對用戶類別的價值做充分的探索之後才進行開發策略。避免在早期的策略不合適造成整個訓練過程策略分布的偏差。

滴滴團隊指出，該方法雖然能夠動態自適應的分配資源，但是真實世界的環境其實在隨著時間的變化而變化。所以指出可以將該方法在動態變化的環境中進行推廣。

論文地址：

Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation

https://arxiv.org/abs/2004.01136

本文方法代碼在 github 可見：

https://github.com/ymy4323460/HATCH

今天的分享就到這裡，謝謝大家。

如果您喜歡本文，點擊右上角，把文章分享到朋友圈~~

歡迎加入 DataFunTalk 推薦系統技術交流群，跟同行零距離交流。如想進群，請加逃課兒同學的微信（微信號：DataFunTalker），回覆：推薦系統，逃課兒會自動拉你進群。

關於我們：

DataFunTalk 專注於大數據、人工智慧技術應用的分享與交流。發起於2017年，在北京、上海、深圳、杭州等城市舉辦超過100場線下沙龍、論壇及峰會，已邀請近500位專家和學者參與分享。其公眾號 DataFunTalk 累計生產原創文章400+，百萬+閱讀，5萬+精準粉絲。

一個在看，一段時光！👇