Youtube推薦系統最大提升：RL Off policy + 推薦系統
分享一下谷歌的一篇強推薦系統&強化學習相結合的論文，據說獲得了Youtube近兩年單次上線的最高收益：Top-K Off-Policy Correction for a REINFORCE Recommender System
谷歌這篇paper將強化學習應用於推薦系統之中，獲得了很明顯的收益，文中仔細的介紹了在Youtube上的具體實踐方案，以及每個細節帶了什麼樣的收益，解決了哪些常見推薦系統中存在的問題，非常值得一讀。因為知乎排版問題大家也可以去博客中閱讀 。
Top-K Off-Policy Correction for a REINFORCE Recommender System on Youtube | 王鳴輝的博客
另外發個廣告，位元組跳動抖音火山技術團隊開啟2020屆校招提前批，內推可免筆試，失敗也不影響正常秋招流程， 需要內推可發我郵箱 [email protected] or [email protected] ,社招同學也歡迎，演算法，大數據，服務端等都要
文章前三分之一 是一個粗略的概況，後三分之二比較細節，可以酌情跳著看看。
傳統監督學習的方案在推薦系統中有局限
- system bias
- 新推薦系統訓練使用的樣本是當前推薦系統推薦給用戶的，而沒被推薦的item的反饋無從而知
- Pigeon-hole(tends to provide myopic recommendations)
- optimize to maximize directly immediate response
- 傾向於推薦大眾化的or用戶熟悉的item
強化學習在推薦系統中的困難
- Large action space
- Expensive exploration
- Learning off-policy
- Partial observability
- Noisy reward
Contributions
- REINFORCE Recommender: We scale a REINFORCE policygradient-based approach to learn a neural recommendation policy in a extremely large action space.
- Off-Policy Candidate Generation: We apply off-policy correction to learn from logged feedback, collected from an ensemble of prior model policies. We incorporate a learned neural model of the behavior policies to correct data biases.
- Top-K Off-Policy Correction: We offer a novel top-K offpolicy correction to account for the fact that our recommender outputs multiple items at a time.
- Benefits in Live Experiments: We demonstrate in live experiments, which was rarely done in existing RL literature, the value of these approaches to improve user long term satisfaction.
基本定義
- Agent: candidate generator
- State: user interest, context
- reward: user satisfaction
- Action: nominate from a catalogue of millions of videos
Data Source
user trajectory
State Representation
嘗試了LSTM,GRU，最後使用的Chaos Free RNN(CFN),因為其比較穩定並且高效。
Adding Context
Reward
Discounted Future Reward
Youtube online metric
| | All | Desktop | Mobile | Tablet |
| -------------- | ----- | ------- | ------ | ------ || Online Metrics | 0.30% | 0.13% | 0.35% | 0.17% |ActionPolicy-based RL
Learn a stochastic policy $pi_{ heta}left(a_{t} | s_{t}
ight)=operatorname{Pr}left[a_{t} | s_{t} ; heta
ight]$ to maximize cumulative reward
Trajectory generated by following the policy
Cumulative reward of the trajectory
Method: Maximize cumulative reward with gradient ascent
gradient of weighted log-likelihood
softmax over actions
Sampled softmax training, serving is preformed by fast nearest neighbor lookup before sampling.
Off-Policy Learning
不像傳統RL,由於環境場景的限制，我們無法通過當前策略與生成的軌跡在線更新策略，而是收集歷史的策略（不同於當前更新策略的分布）的反饋行為。 實際情況是以幾個小時為周期收集數據，在舊策略下的軌跡數據上更新策略參數。 由於軌跡數據是由歷史策略生產來，公式（2）的naive policy gradient estimator 就不再是無偏的了。
Address the distribution mismatch with importance weighting.
不論怎樣從β採樣，都可以校正成無偏估計。但importance weight的值會因為鏈式相乘而迅速變得很大或者很小，從而導致估計的方差變得很大。
為了減少梯度的方差,忽略t時間後的鏈式乘積,並採用一階近似
a biased estimator of the policy gradient with lower variance:
Achiam et al. [1] 證明了在總獎勵的一階近似影響限制在 $Oleft(E_{s sim d^{eta}}left[D_{T V}(pi | eta)[s]
ight]
ight)$, $D_{T V}$ 是 $pi(cdot | s)$ 和 $eta(cdot | s)$ 的variance, $d^{eta}$ 是discounted future state distribution
This estimator trades off the variance of the exact off-policy correction while still correcting for the large bias of a non-corrected policy gradient, which is better suited for on-policy learning.
Parametrising the policy π
Estimating the behavior policy β
公式(3)中有個困難是獲取策略$eta$, 理想情況下我們可以記錄策略選擇的action的概率，但是在這個場景下 1. 系統中有很多agents，其中許多我們無法控制 2. 一些agents有確定性策略，設$eta$為0或1無法高效利用logged feedback.
因此採用[39]中提出的方法，用記錄下來的行為來估計多agents的混合策略$eta$.
Given a set of logged feedback $mathcal{D}=left{left(mathbf{s}{i}, a{i}
ight), i=1, cdots, N
ight}$, Strehlet al. [39] estimates $hat{eta}(a)$ independent of user state by aggregate action frequency throughout the corpus.
相反，我們採用了上下文獨立的neural estimator。對每一個被收集的state-action pair，用另一個softmax估計$hat{eta}_{ heta^{prime}}(a|s)$
如圖1，我們重複利用了從RNN生成出來的用戶狀態 s， 用另一個softmax層對混合策略進行建模。為了避免其對生成用戶狀態的主策略影響，block掉其對梯度的回傳。我們也嘗試過將兩個策略分開建模，不過這帶來了額外的計算開銷，並且沒有任何指標在離線和線上實驗有提升。
儘管兩個策略共享參數，但是他們之間有兩個顯著的區別： 1. 考慮到長期獎勵，主策略$pi_{ heta}$使用帶權的softmax訓練，而$eta_{ heta^{prime}}$僅用 state-action pairs訓練。 2. $pi_{ heta}$用軌跡上非零獎勵的item訓練，而$eta_{ heta^{prime}}$使用軌跡上的全部item，以免在估計$eta$中引入bias
In [39], it is argued that that a behavior policy that is deterministically choosing an action a given state s at time t1 and action b at time t2 can be treated as randomizing between action a and b over the timespan of the logging.
本文也同樣認同上邊的觀點，這也解釋了為什麼行為策略可以是0或者1的確定性策略。除此之外，因為我們同時有多個策略，如果一個策略固定在狀態s下選擇行為a，而另一個策略會固定選擇行為b，那麼估計$hat{eta}_{ heta^{prime}}$ 將近似於在狀態s下動作a發生的頻率。
Top-K Off-Policy Correction
另一個挑戰是我們會一次性給用戶推薦一頁共K個item，用戶可能會全部看到也可能只會看到一部分，並可能與不止一個item發生交互，我們需要選擇一系列相關的item而非一個item。也就是說我們要找到一個策略$Pi_{Theta}(A | s)$,每個動作A選擇k個items，去最大化預期累計收益。
$$max {Theta} mathbb{E}{ au sim Pi_{ heta}}left[sum_{t} rleft(s_{t}, A_{t}
ight)
ight]$$
通過策略動作 $s_{0} sim
ho_{0}, A_{t} sim Pileft( | s_{t}
ight), s_{t+1} sim mathbf{P}left(cdot | s_{t}, A_{t}
ight)$ 可以得到軌跡$ au=left(s_{0}, A_{0}, s_{1}, cdots
ight)$ 但是這樣動作空間會呈指數級增長，當候選集有幾百萬的時候，更是大的可怕。 為了解決問題，我們假定一組不重複items的預期獎勵等於每個item預期獎勵的總和（This assumption holds if users inspect each item on a page independently）
另外我們限制自己通過softmax 策略獨立採樣每個item a 並去重，生成一組動作A。 $$Pi_{Theta}left(A^{prime} | s
ight)=prod_{a in A^{prime}} pi_{ heta}(a | s)$$ 這裡$A^{prime}$包含重複items，A是去重後的集合。
在上述假設下，我們可以通過簡單修改方程式(2)的梯度更新邏輯，來調整強化學習演算法。
$alpha_{ heta}(a | s)=1-left(1-pi_{ heta}(a | s)
ight)^{K}$ 是item a出現在非重複集合A的概率。這裡 K = |A『| > |A| = k。 我們可以通過將$pi_{ heta}$替換為$alpha_{ heta}$去更新公式(3)，來引入top-K off-policy 修正因子。
比較公式(6)和公式(3)，top-K policy增加了一個額外的乘數
我們可以仔細的看一下這個額外的乘數： - 隨著$pi_{ heta}(a|s)
ightarrow 0, lambda_{K}(s, a)
ightarrow K$, 相比於標準的off-policy correction，top-K off-policy correction 的更新增大K倍。 - 隨著$pi_{ heta}(a|s)
ightarrow 1, lambda_{K}(s, a)
ightarrow 0$, 乘數會使策略更新趨向於0 - 隨著K的增加，乘數減少梯度到0會快於$pi_{ heta}(a|s)$來達到一個合理的範圍
總之，當期望項目在softmax策略πθ中具有小質量時，前K校正比標準校正更積極地推高其可能性。 一旦softmax政策πθ（·| s）在理想項目上投入合理的質量（以確保它可能出現在前K項），則校正後將梯度歸零並且不再試圖推高其可能性。 這反過來允許其他感興趣的項目在softmax policy中佔據一些質量。 正如我們將在模擬和實時實驗中展示的那樣，當標準的off-policy correctuib收斂於選擇單個項目時最優的策略時，top-K correction會產生更好的top-K 推薦。
Variance Reduction Techniques
如前文所說，我們使用一階近似去減少梯度估計得方差。但是由於大的importance weight,梯度仍然會有很大的方差.大的importance weight是由於新策略和舊策略偏差大，尤其在舊策略探索比較少的區域。That is,$pi(a | s) gg eta(a | s)$ and d (2) large variance in the β estimate. 我們測試了在counterfactual learning和RL文獻中提出的幾種技術來控制梯度估計的方差。這些技術中的大部分可降低方差,但代價是在梯度估計中引入一些偏差。
Weight Capping.
Normalized Importance Sampling (NIS).
n是batch size,n增加等價於調低學習率
Trusted Region Policy Optimization (TRPO). TRPO 通過增加正則項，懲罰兩個策略間的KL散度，來預防新策略π偏離行為策略，取得的效果類似於梯度裁剪。
Address System Bias
實驗組可以更傾向於尾部
Exploration
訓練數據的分布對於學習一個好策略很重要。現在，探索現有系統很少採取的行動的Exploration policies已經被廣泛研究。實踐中，暴力探索如 ?-greedy，在Youtube中是不合適的，它大概率會導致一些不合適宜的推薦和不好的用戶體驗。, Schnabel et al. [35] 研究了探索的成本。 我們使用了Boltzmann exploration [12] 在不影響用戶體驗的情況下得到探索數據的好處。我們考慮採用隨機策略，即推薦item是從$pi_{ heta}$採樣而來，而非概率最高的K個items。這裡計算開銷是個挑戰，我們需要計算完整的softmax。因此我們使用最近鄰方案去尋找top M個items，算一個小的softmax，再據此進行採樣。通過讓 M >> K,我們仍可以得到大部分probability mass，限制不好推薦項的風險，保證計算效率。實踐中，我們通過返回K個prob最高的items，和從M-K中採樣K-K個items來平衡EE問題（exploration and exploitation）
Simulation
我們首先設計模擬實驗，以便在更加可控的環境下闡明off-policy correction。 為了簡化我們的模擬，我們假設問題是無狀態的，換句話說，獎勵R獨立於用戶狀態，並且動作也不會改變用戶狀態。因此，可以獨立地選擇軌跡上的每個動作.
Off-policy correction
第一個模擬實驗中，我們假設有10個items $mathcal{A}=left{a_{i}, i=1, cdots, 10
ight}$,$rleft(a_{i}
ight)=i$。當我們選擇一個item時，最優策略就是一直選第十個，因為其獎勵最大。 $$ pi^{*}left(a_{i}
ight)=mathbb{I}(i=10) $$ 我們用無狀態softmax參數化$pi{ heta}$, $$ pileft(a_{i}
ight)=frac{e^{ heta_{i}}}{sum_{j} e^{ heta_{j}}} $$ 從行為策略β採樣，不考慮數據bias，如公式(1)簡單地用用策略梯度 $$ pileft(a_{i}
ight)=frac{rleft(a_{i}
ight) etaleft(a_{i}
ight)}{sum_{j} rleft(a_{j}
ight) etaleft(a_{j}
ight)} $$ 這有一個明顯的缺點，行為策略越選擇次優item，新的策略就約會偏向選同一個item。
圖2比較了當策略β傾向選擇獎勵最少的item時，有無off-policy修正下的$pi{ heta}$。如圖2所示，左邊為不考慮數據偏差簡單應用策略梯度，導致sub-optimal policy。最壞情況，行為策略一直選獎勵最少的，我們也會學到一個類似舊策略的不好的策略（比如一直選獎勵最少的）。而應用off-policy correction讓我們學到一個最優策略$pi{*}$,不論收集的數據如何，如圖(2)右邊所示
Top-K off-policy correction
為了理解標準off-policy correction和top-K off-policy correction的區別，我們設計了個可以推薦多個items的實驗。同樣我們假設有10 items，$rleft(a_{1}
ight)=10, rleft(a_{2}
ight)=9$ , 剩下的獎勵都是1，$rleft(a_{i}
ight)=1, forall i=3, cdots, 10$。我們專註於推薦兩個item，即K = 2。行為策略β是均勻分布，每個item有同等的機會。
從β中採樣到$left(a_{i}, r_{i}
ight)$,標準的off-policy correction有以下形式的SGD更新，
SGD持續增加$a_i$與$π_θ$下的預期獎勵成比例的可能性，直到
當$pi_{ heta}left(a_{i}
ight)$很小時，$lambda_{K}left(a_{i}
ight) approx K$, SGD會更激進的增加$a_i$的可能性。當$pi_{ heta}left(a_{i}
ight)$到一個足夠大的值時$lambda_{K}left(a_{i}
ight)$ 接近於0。因此，即使$pi_{ heta}left(a_{i}
ight)$仍然小於1，SGD也不再強制增加item的可能性。這反過來使第二好的項目在學習的策略中佔有一些地位。
圖3左邊展示了標準方式和top-K學到的策略$pi_ heta$.我們可以看到雖然從標準off-policy correction學到的策略已經被校準[23]過，切它也按獎勵的大小保證了順序，但是收斂的策略幾乎將整個質量全部集中於top-1 item，即$pileft(a_{1}
ight) approx 1.0$。這導致策略基本沒有學到次優項（本例中的$a_2$）和其餘之間的區別.而top-K correction的收斂策略在保證item順序於獎勵順序一致的情況下，也為第二的item保留了significant mass。因此，我們可以為用戶推薦兩個高獎勵的items，獲得更高的整體獎勵。
Live Experiments
這是Youtube近兩年以來單次上線取得的最大收益
| | All | Desktop | Mobile | Tablet |
| -------------- | ----- | ------- | ------ | ------ || Online Metrics | 0.86% | 0.36% | 1.04% | 0.68% |我們在Youtube的RNN候選生成模型做了一些列AB實驗。這個模型是眾多候選生成模型中的一個，在展示前會有一個獨立的rank model去進行打分排序。模型根據上述RL演算法來訓練，實時獎勵反應著用戶的行為，推薦的視頻沒被點擊的獎勵為0.長期獎勵R會在4-10小時內做聚合。每個實驗中control model和test model用相同的reward函數。實驗運行了很多天，模型在線上持續訓練，新事件會在24小時內訓練。實驗期間，我們關注了各種線上指標，不過這裡我們主要關注用戶觀看視頻時長,ViewTime.
這裡介紹的實驗描述了對生產系統的多個連續改進。 所以，最新的推薦系統為下一個實驗提供訓練數據，這導致一旦生產系統採用新方法，後續實驗就不能與早期系統進行比較。 因此，以下每個實驗會作為組件單獨分析，並在每個部分中說明新方法接收數據是由什麼推薦系統提供的。
Exploration
我們首先要理解exploratory data 在提高模型質量方面的價值。 特別是，我們想衡量是否要在之前描述的採樣softmax模型下使用隨機策略，要比一直根據softmax推薦概率最高的K個item的模型要好。 我們先弄一組實驗對比隨機策略和確定性出一個。在實驗中，控制群體使用確定性策略，而一小部分測試流量用隨機策略，如Exploration節所述。 兩個實驗都是基於公式(2)里的softmax模型訓練。為了控制隨機策略的隨機性，我們調整公式(5)的temperature.一個較低的T是隨機策略偏向於確定性策略，而T值變大會導致item的推薦偏向於等概率隨機。 當T設為1時，ViewTime沒有統計顯著性變化，這表明採樣所引入的這些隨機性沒有直接傷害用戶體驗。
但是這個實驗的設置沒有考慮有探索數據對於訓練的益處。從歷史記錄數據中學習的一個主要偏差是模型沒有觀察到前一個推薦策略未選擇的Action的反饋,探索性數據會緩解這一問題。我們有搞了一個跟進實驗，在訓練中引入了探索數據。為此，我們首先將平台用戶分為了3個buckets，90%，5%，5%。前兩個buckets基於確定性模型使用確定性策略，最後一個bucket用基於帶探索性數據訓練模型的stochastic policy。確定性模型用前兩個buckets訓練，隨機模型用第一個和第三個bucket訓練。這樣兩個模型訓練使用的數據量時相等的，但隨機模型會因為探索數據更容易觀察到一些罕見的state,action pair.
按此實驗流程，我們觀察到測試群體中的ViewTime統計學顯著性地增加了0.07％。 雖然改進不大，但它來自相對少量的勘探數據（只有5％的用戶在用隨機政策）。隨著隨機政策的全面啟動，我們預計會有更高的收益。
Off-policy Correction
使用完隨機策略之後，我們在訓練中引入off-policy correction。這塊我們用了更傳統的A/B測試設置,都使用了全部數據。實際上，我們用了很少的用戶作為測試人群，所以數據基本全部來自control model。control model由公式(2)確定，只用reward調整樣本的權重。測試模型使用圖1的結構，即用來學習 serving policy $pi_{ heta}$ 也學習 behavior policy $eta_{ heta_{prime}}$. serving policy 用公式(3)中off-policy correction 訓練，樣本權重不止依賴與reward，還依賴importance weight$frac{pi_{ heta}}{eta_{ heta^{prime}}}$ 去解決data bias。
在實驗期間，我們觀察到學習策略（測試）的開始是通過行為策略（控制）獲取的數據。圖4繪製了由我們的提名者根據對照人群中的視頻等級在對照和實驗中選擇的視頻的CDF（rank 1是control model中推薦最多的視頻，最右邊是最少被推薦的視頻）。我們可以看到test model（綠色）更傾向於那些較少被control model探索過的視頻。我們看到top ranks之外的視頻被推薦數提升了三倍，這與我們在圖2中展現的模擬實驗結論是一致的。當忽略數據收集與處理的bias會產生強者恆強的現象。因此視頻被推薦，可能僅僅是因為他在behavior policy里曾大量被推薦，而off-policy correction可以幫忙解決這個問題。
有趣的是,在線上實驗中,我們並沒有觀察到control與test群體之間的 ViewTime 發生統計顯著性變化。然而,我們看到視頻數量增加了0.53%,這在統計學上是顯著的,這表明用戶確實得到了更多的享受。（註：個人覺得這個對發文側會有一個顯著的促進，作者留存應該會提升，長期看也對用戶也是正向的，不過谷歌這篇論文沒有提
Top-K Off-Policy
我們現在聚焦於理解是否Top-K off-policy比標準的off-policy提升用戶體驗。我們用同樣的模型結構使用公式6的top-K off-policy corrected梯度更新訓練，然後和上一節的off-policy模型比較。在本實驗中,我們讓方程 (8)的 K = 16 和上限 c=e^3 ;後邊我們會更詳細地探討這些超參數。
雖然我們之前測試過的標準off-policy correction過於關注top-1 item，而top-K off-policy correction收斂於更平穩的政策，其中會有non-zero mass在用戶其他感興趣的項目上。 這反過來導致更好的top-K推薦。 鑒於我們可以推薦多個項目，top-K policy讓我們向用戶提供比標準off-policy correction更好的整體體驗。 特別是，我們發現測試流量中ViewTime增加了0.85％，觀看的視頻數量略微減少了0.16％。（註：短視頻的話，可以再關注下finish指標的變化
Understanding Hyperparameters
最後，我們直接比較不同的超參數的選擇如何影響top-K off-policy correction對平台上的用戶體驗。我們在top-K off-policy correction成為生產模型後進行了這些測試。
Number of actions
我們先測了下top-K中的K。我們用$K in{1,2,16,32}$訓練了三個結構相同的模型。The control (production) model is the top-K off-policy model with K = 16. 我們在圖5畫了5天實驗的結果。當K=1時,top-K就是標準的off-policy correction。與基線K = 16相比 K = 1 導致ViewTime掉了0.66%。K = 2 也不好，不過差距變小了，ViewTime下降了0.35%，K = 32的效果類似基線。我們後續的實驗顯示K = 8 在ViewTime上有一定的正向(+0.15% statistically significant)
Capping
這裡我們來探討下方差減小技術對學到的推薦系統的最終質量的影響。論文Section4.4里weight capping在最初實驗里拿到了最大的收益。我們沒有觀察到normalized importance sampling,or TRPO [36]對指標的提升。我們搞了個回歸測試研究weight capping的影響，比較了c = e^3和c = e^5。當我們取消對importance weight的限制時，學到的策略$π_θ$可能會過度適應一些意外獲得高回報的logged actions。 Swaminathan和Joachims [43]描述了傾向過擬合的類似效果。 在線上實驗中，當the cap on importance weight被增大時，我們觀察到ViewTime顯著下降了0.52％。
Conclusion and Future Works
這篇paper講了policy gradient-based top-K推薦系統在Youtube上的應用。我們將REINFORCE的action space擴展到數百萬這個級別，並且穩定的運行在線上生產環境中。為了展示這種方法的全部收益，我們演示了如何通過結合a learned logging policy和新穎的top K-off-policy correction來解決logged data中的bias。我們進行了廣泛的分析和實驗，來衡量了解和解決這些潛在的biases的重要性。 我們認為這些是使強化學習對推薦產生實際影響的重要步驟，並為研究人員和從業人員探索將RL應用於推薦系統提供了堅實的基礎。
- Reinforement Learning Framework for Recommender Systems
- Future Work
- Better state representation through LRD
- Better exploration and planning
- Beyond systems and user:improve Youtube ecosystem
參考
- https://www.youtube.com/watch?v=HEqQ2_1XRTs
- https://arxiv.org/pdf/1812.02353.pdf
推薦閱讀：
