バンディットアルゴリズムの評価と因果推論 |

結果ユーザーによるフィードバックが観測され、クリックしたか否かがわかります。
$$r_i \sim D_r(.|X_i, a_i)$$
この予測と選択の一連の流れを行う部分をPolicy($\pi$)と呼びます。
$$a_i = \pi(X_i)$$
教科書的にはtのフィードバックを利用してt+1で使われるPolicyを更新するという内容がよく出て来るのですが、実装の都合などでバッチで更新されるケースが実務的には多く、今回もその内容に乗っ取って話を進めます。

この時、手元に残っているログは以下の様なものになります。
$$\{X_i, r_i, a_i\}_{i=1}^N$$
リクエスト(i)毎にContext(X)と、選んだ広告画像(a)と、結果クリックされたか(r)が溜まっている状態です。
また、ログが取得できている期間ではPolicyは一つしかないものと考えます（$\pi_0$）

2. 比較の話

さて、ここでPolicyに何かしらの改良を加えるアイデアを思いついたとします。ここで問題になるのは「どの様にして既存のPolicyとこの改良を加えたPolicyを比較するか？」という点です。（より良いPolicyは獲得しうる報酬(r)の合計がより大きい方だと考えます。）

この二つのPolicyを比較する為のGolden Standardな検証デザインは何か？ということを考えた場合、おそらく皆さんご存知の通りABテスト（RCT）という答えになるかと思います。つまり、未来におけるリクエストの半分をランダムに既存のPolicyに割り振り、残りの半分を新規のPolicyに割り振り、それぞれで獲得できたクリックの数を比較するといった方法です。

ãRCT cartoonãã®ç»åæ¤ç´¢çµæ

しかし、この様なABテストを実施するためには実際に新規のPolicyを実装する必要がありますし、さらに結果的に大失敗と終わる可能性のあるアイデアにある程度のリクエスト数（ユーザー）を割り振らないといけません。また、もし思いついたアイデアが１つでは無く100個で有れば、検証のためのコストは非常に高くなってしまいます。

この様な社会科学でよくみられる様な「実験の実施コストが高い」という理由から、どうにかして手持ちのデータからRCTの結果を再現したいという要求が生まれることになります。

3. replay-method

過去のログに置いて新しいPolicyの評価を行うためには、まず実際に選択を行わせる必要があります。これは新Policy($\pi(X)$)に過去ログの$X_i$を入力してやれば得る事ができます。

$$a_{1,i} = \pi(X_i)$$

問題となるのはその評価を入手する事です。過去の選択($a_{0,i} = \pi_0(X_i) $)を実行した時の報酬($r_i$)は観測されていますが、$a_{0,i}$以外の選択を実行した時の報酬は観測されていません。（あるリクエストにおいて広告画像1を見せた結果の報酬は観測しているが、広告画像2を見せた結果の報酬は観測していないので。）

つまり、新Policyの報酬は既存のPolicyと同じ選択肢を選んだ時でしか観測されないわけです。よってそれをそのまま評価と考えると新Policyの評価は以下の様に算出されます。

$$V_{naiive}(\pi) = \frac{1}{N} \sum_{i=1}^N {r_i 1(a_{0,i} =a_{1,i})}$$

この方法は、もし既存のPolicyが選択肢をランダムに選んでいた場合には評価が正しいという事が分かっており、こちらの論文でreplay-methodとして提案されています。しかし、ランダムでは無い場合には既存のPolicyによって生じるサンプリングバイアスの影響を受ける為にこの評価方法はABテストの近似としては不満足なものとなってしまいます。

4. Direct method

次に簡単な方法は、予測モデルによって観測されなかった選択肢の報酬を予測してしまうDirect Methodと呼ばれる方法です。つまり、ある選択肢が選ばれたデータを学習データとして、その選択肢が選ばれなかったデータに対して予測を行う訳です。この辺りの論文での実験だとridge回帰によって予測を行ったりしています。そして、予測された報酬の平均をPolicyの評価として扱います。

$$\hat{r}_a(X)=E[r_a|X]\\
V_{DM}(\pi) = \frac{1}{N} \sum_{i=1}^N {\hat{r}(X_i, \pi(X_i))}
$$

こちらの方法は、機械学習の実務をやっている方には割と自然な発想な気がしますが、２つの問題点があります。

1つは$\hat{r}(X, a)$を表現するのに十分なデータが得る事が非常に難しいという点にあります。多くの場合報酬はユーザーの意思決定に依存するので、その意思決定を高い精度で近似出来ている必要が出て来るのですが、これは実際問題かなり難しいタスクになるでしょう。また、学習の元になっているデータもsampling biasを持つデータとなってしまっています。どちらもサンプルサイズの増加によって消える様な問題では無い為に、この評価方法もやはりABテストの近似としては不満足なものとなってしまいます。

5. Inversed Propensity Score

この様な問題において因果推論を扱う分析ではPropensity Score（$p_a$）がよく用いられます。最初の方法と同様に既存と新規のPolicyの選択が同一になったサンプルだけを評価に用いますが、この時に既存のPolicyでその選択肢が選ばれる確率の逆数をsampling weightとして用います。

$$p_a = p(a|X_i) \\
V_{ips}(\pi) = \frac{1}{N} \sum_{i=1}^N {\frac{r_i 1(a_{0,i} =a_{1,i})}{p_a}}
$$

この時Propensity Scoreはlogistic regression等で推定することも出来ますし、Thompson Samplingを利用している場合ではサンプリングのプロセスを繰り返すことでその確率を直接得る事が出来ます。Offline Policy Evaluationの文献を見ていると後者の方法を用いている事が多い様に思えます。

この様なIPSと呼ばれる方法の問題点は、Propensity Scoreが非常に小さい時に評価に対して大きな影響を与える事になり、結果的に評価の推定値の分散を押し上げてしまう事にあります。しかしIPSはサンプルサイズが大きくなるとABテストの結果に一致していくというメリットもあります。

6. Doubly Robust

最後にIPSとDMを掛け合わせたdoubly robustを紹介します。（参照）

$$
V_{dr}(\pi) = \frac{1}{N} \sum_{i=1}^N {\frac{(r_a – \hat{r_a}(X_i))1(a_{0,i} =a_{1,i})}{p_a} +\hat{r}_{\pi(X_i)}(X_i)}
$$

第一項は過去のPolicyと新規のPolicyの選択が一致しない場合には0になってしまうため、その様な場合にはDMと同様の評価を行う様になっています。
一致した場合には報酬予測の誤差をIPSで重みを掛け、DMの評価にそれを足し合わせています。報酬予測の精度が高いと第一項が0に近付いていくので、報酬予測の精度が悪い時にはIPSを使うといった構造だと解釈することも可能です。

7. まとめ

改めて問題を整理して考えると、新Policyの評価が難しいのは評価が過去ログの全サンプルで入手することが出来ず、欠損が発生しているという構造上の問題から生じていました。そして、どの様なサンプルで欠損が起きるかが既存のPolicyに依存しているため、欠損がランダムではなく何かしらのメカニズムを元に起きているという事情ありました。

これらの事から新Policyの評価は欠損のある評価データからいかに、欠損のない評価を推定するか？という欠損データにおける因果推論の捉える課題と同様な状態である事が分かります。よって、Propenstiy ScoreやDoubly Robustの様な方法が使われているわけです。

今回紹介した方法の他にもMorerobust Doubly Robustの応用や、もう少し複雑なバンディット問題のオフライン評価の話などが最近の研究では取り扱われています。もし興味を持たれた方は調べてみると面白いと思います。

引用文献

Li, Lihong, et al. “Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms.” Proceedings of the fourth ACM international conference on Web search and data mining. ACM, 2011.
Dudík, Miroslav, John Langford, and Lihong Li. “Doubly robust policy evaluation and learning.” arXiv preprint arXiv:1103.4601 (2011).

Author

yasui