Top-K Off-Policy Correction for a REINFORCE Recommender System.

[usaito]

0. 論文概要

Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, Ed H. Chi. 2019. Top-K Off-Policy Correction for a REINFORCE Recommender System. In The Twelfth ACM International Conference on Web Search and Data Mining (WSDM’ 19), February 11-15, 2019, Melbourne, VIC, Australia.

** 図表は全て本論文からの引用です.

1. 要約

• Youtubeなどのコンテンツ推薦に, ユーザーの興味遷移を考慮に入れるため強化学習を適用.
• しかし, onlineで学習, 探索するとユーザー体験を大きく害するので, logged bandit feedbackを利用する際のbiasを除去する方法を提案.
• さらに, 今回はK個のコンテンツを推薦するような方策を学習する状況にbias除去を拡張.

2. 背景

• 推薦システムにおいて, 推薦するコンテンツが変化するとユーザーの興味（状態）も変化すると考えられる. （将来interactするitemが変化する）
• よって, 取った行動による状態変化もモデル化する強化学習を用いて, ユーザーのlong term satisfactionを最大化したい.
• しかし, 推薦システムでon-policyで推薦方策を学習することは, 主に探索期間において大きくユーザー体験を害する危険性が考えられるため, 過去の方策によって集められたデータから新たなpolicyを得たい.
• そのようなlogged bandit feedbackを用いると方策更新にbiasが生じる（勾配方策定理が成り立たない）ため, 補正が必要である.
• また今回は, Youtubeの動画推薦などTop-Kアイテムを推薦する系にも適用できるアルゴリズムを用いることが想定されるため, bias補正をTop-K推薦の場合にまで拡張することを考えたい.

3. 手法

bias除去

今回用いるnotationは以下の通り. ユーザーの状態遷移を考慮に入れたMDP.

ここで, 方策πのパラメータθは, 勾配方策定理により, 以下をサンプルから推定したもので更新する.

しかし, 背景でも述べたように今回は推薦システムに方策を適用することを考えるので, 勾配を計算するのに用いるtrajectoryは, 自身ではなくて, 過去の方策(behavior policy) βによるものである. これにより, 勾配方策定理が成り立たないため, パラメータ更新に工夫が必要である.

本論文では, Importance Samplingを用いることで, このlogged bandit feedbackを用いることに起因するbiasを取り除く. de-biasされた勾配は以下の通り. これは真の報酬の勾配に対してunbiasedである.

Propensity Scoreのように, behavior policyで逆重み付けしていると解釈できる. 勾配の更新式がわかったので, ここからユーザーの状態s のモデル化に入る. 本論文では, RNNの一種であるCFNを用いて状態をモデル化する. (deep learning詳しくないので, そろそろ勉強しなければ)

また, 上述したbias除去のためには, behavior policy βを推定することが必要である. (もちろんlogとして残っていればそれを用いれば良いのだが, 複数のpolicyが混ざっていたりする状況の方が一般的). これは, RNNで得られたユーザーの状態表現を用いて別のNetworkで推定する. behavior policyの推定ように状態表現を別に得るやり方も試したそうだが, 精度は変わらなかったそう.

behavior policyの推定部分も含めたarchitectureは以下の通り.

Top-Kへの拡張

さて, 大きな問題である勾配推定のbiasを除去する方法を提案した後は, この勾配推定をTop-Kの状況に拡張することを考える. 累積報酬を書き換えると以下のようになる. Aがk個のitemで構成されるactionになる.

ここで, 推薦されるアイテム集合Aは, stochastic policyから独立に復元サンプリングすることによって得ることとする.

このような状況のもとで, bias補正前の勾配は, アイテムaがアイテム集合Aに現れる確率を用いて以下のように書き換えられる.

このTop-K versionの勾配に対して, bias補正をかけると,

よって, Kの値が変わると, softmax値が小さいアイテムから報酬が得られた場合について, パラメータの更新度合いを変化させるような役割を持つ. この効果については, 実験で検証する.

4. 実験

4.1. 報酬が状態に依存しない場合（人工データ）

報酬が状態に依存せず, アイテムごとに報酬が決定している状況において, behavior policyによって得られたbandit feedbackから, 最適な方策を求める. bias除去を入れた場合と入れなかった場合を比較.

アイテムのindexが大きくなるにつれて, 報酬が大きくなるように報酬構造は設計されている. よって, bias除去を入れることによって, 最大の報酬を与えるアイテムに大きな確率が割り当てられていて, うまく方策を学習できていることがわかる.

4.2. 報酬が状態に依存しない場合のTop-K推薦（人工データ）

次に, 先ほどの実験をK個のアイテムを推薦可能とする状況に拡張する. 今回は, K=2として, 10個のアイテムはまたも状態非依存で以下のように決まっているとする.

a_1 = 10, a_2 = 9, a_i = 1, (i = 3, 4, ..., 10.)

つまり, 一つ目と二つ目のアイテムを推薦するような方策を学習したい. 単純なbias除去とTop-Kの状況に拡張したbias除去（λが入っているやつ）の2つの方策を比較.

Top-Kを考慮に入れた勾配で更新することで, 2つ目のアイテムとそれ以外の差が明確になっているため, パッケージとしてより良い推薦ができるとの結果.

4.3. 実データを用いた実験

Youtubeの視聴時間を報酬と見て, A/Bテストで異なる方策で動画を推薦した. Top K個の動画を推薦する場合を考えて, K=1, 2, 16, 32で5日間実験した時の結果がFigure 5. K=16をbaselineとしている.

ある程度の大きさのKを設定して推薦することで, 視聴時間を改善できることが示された.

5. コメント

• 推薦によって, 報酬だけではなくてユーザーの状態が変化するというのはとても現実的な設定で, 広告配信など他にも適用が考えられるため非常に参考になった.

• スペースの関係からか, 実験について図を掲載せずに結果だけ述べている部分があったので少し残念

• そろそろでぃーぷらーにんぐ勉強しないと

6. 関連論文ピックアップ

• Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. 2016. Recommendations As Treatments: Debiasing Learning and Evaluation. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48 (ICML’16). 1670–1679.