Off-Policy Evaluation of Ranking Policies under Diverse User Behavior (日本語版)

KDD2023 Research track 採択論文の解説スライド
https://arxiv.org/abs/2306.15098

English version: https://speakerdeck.com/harukakiyohara_/adaptive-ope-of-ranking-policies

1. Off-Policy Evaluation of Ranking Policies under Diverse User Behavior Haruka Kiyohara, Masatoshi Uehara, Yusuke Narita, Nobuyuki Shimizu, Yasuo Yamamoto, Yuta Saito 清原 明加（Haruka Kiyohara） https://sites.google.com/view/harukakiyohara August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 1
2. ランキング推薦は⾄る所で使われている ランキング推薦の事例 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 2 • 検索エンジン • ⾳楽配信 • Eコマース • ニュース配信 • など沢⼭..! これらランキング推薦の 性能評価をオフラインでできる? … …
3. ランキング推薦はどのように成り⽴っている？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 3 ranking with 𝑲 items a coming user context clicks reward(s) a ranking policy … ▼ これを評価したい
4. オフ⽅策評価（Off-Policy Evaluation; OPE） August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 4 ranking with 𝑲 items a coming user context clicks reward(s) a logging policy an evaluation policy …
5. 推定したい⽅策価値 ⽬標は、ランキング推薦⽅策の得る期待報酬を推定すること。 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 5
6. 推定したい⽅策価値 ⽬標は、ランキング推薦⽅策の得る期待報酬を推定すること。 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 6 position-wise policy value に分解できる （ランキング全体に依存）
7. ナイーブな⼿法: Inverse Propensity Scoring [Strehl+,10] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 7 importance weight ・unbiased ・variance
8. ナイーブな⼿法: Inverse Propensity Scoring [Strehl+,10] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 8 importance weight evaluation logging ranking A ranking B more less less more ・unbiased ・variance
9. ナイーブな⼿法: Inverse Propensity Scoring [Strehl+,10] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 9 importance weight evaluation logging ranking A ranking B more less less more ・unbiased ・variance 分布シフトを補正している
10. ナイーブな⼿法: Inverse Propensity Scoring [Strehl+,10] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 10 importance weight evaluation logging ranking A more less ・unbiased ・variance 重みが⼤きくばらつきに繋がる
11. ナイーブな⼿法: Inverse Propensity Scoring [Strehl+,10] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 11 importance weight ・unbiased ・variance When 𝜋0 is the uniform random policy,
12. ナイーブな⼿法: Inverse Propensity Scoring [Strehl+,10] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 12 importance weight ・unbiased ・variance!! When 𝜋0 is the uniform random policy, （組み合わせ⾏動による）
13. 分散減少のためのユーザー⾏動モデル ユーザーがランキング内の⼀部のアイテムのみに影響を受けると仮定する。 • Independent IPS [Li+,18] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 13
14. 分散減少のためのユーザー⾏動モデル ユーザーがランキング内の⼀部のアイテムのみに影響を受けると仮定する。 • Independent IPS [Li+,18] • Reward Interaction IPS [McInerney+,20] August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 14
15. 仮定を導⼊すれば正確な推定ができるのか？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 15 Bias Variance IIPS RIPS IPS independent cascade standard click model IIPS: [Li+,18], RIPS: [McInerney+,20], IPS: [Precup+,00] ユーザー⾏動モデル (仮定) の強さにより 偏り (bias) -分散 (variance) のトレードオフ
16. 仮定を導⼊すれば正確な推定ができるのか？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 16 Bias Variance IIPS RIPS IPS independent cascade standard click model IIPS: [Li+,18], RIPS: [McInerney+,20], IPS: [Precup+,00] これら既存の推定量は 実応⽤場⾯で本当に正確なのか..？ ユーザー⾏動モデル (仮定) の強さにより 偏り (bias) -分散 (variance) のトレードオフ
17. Adaptive IPS for diverse users August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 17
18. 例えば、検索ワードやこれまでの検索履歴によって変わりうる。 実世界では状況に応じ多様なユーザー⾏動が存在する August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 18 検索ワード: clothes (一般的) -> 上位のアイテムのみを閲覧する 検索ワード: T-shirts (より詳しい) -> 沢山のアイテムを閲覧してからクリック clothes … T-shirts …
19. 既存⼿法の問題：多様なユーザー⾏動に対応できない August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 19 Our idea 全ユーザーに対して単⼀の仮定を置く
20. 既存⼿法の問題：多様なユーザー⾏動に対応できない August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 20 Our idea 真のユーザー⾏動仮定 ミスマッチが発⽣！
21. 既存⼿法の問題：多様なユーザー⾏動に対応できない August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 21 Our idea データの偏りを 補正できない 真のユーザー⾏動仮定 ミスマッチが発⽣！
22. 既存⼿法の問題：多様なユーザー⾏動に対応できない August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 22 Our idea 余分な分散が発⽣ 真のユーザー⾏動仮定 ミスマッチが発⽣！
23. 提案アイデア：ユーザー⾏動に対して適応的に August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 23 提案アイデア adaptive! -> ユーザー⾏動仮定のミスマッチを減らせる！
24. 提案アイデア：ユーザー⾏動に対して適応的に August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 24 提案アイデア … example of complex (1) 既存の仮定では捉えられない 複雑なユーザー⾏動 より多様なユーザー⾏動にも対応することで、 さらにミスマッチを減少！
25. 提案推定量: Adaptive IPS August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 25 統計的に優れた点 • どんなユーザー行動に対しても不偏性を満たす。 • データの重みづけ補正に基づく全ての推定量の中で最小分散を実現。 importance weight を 依存するアイテムにのみ考える
26. AIPSはどのくらい分散を減少できるのか？ AIPSは依存しないアイテム集合に対する重み分だけ分散を減少！ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 26 : 関連するアイテム集合 : 関連しないアイテム集合
27. ユーザー⾏動が分からず推定するとどうなるのか？ ユーザー⾏動 𝑐 は現実には観測できないので、代わりに ̂ 𝑐 を⽤いるとする. August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 27 重なりの度合いが重要
28. ユーザー⾏動が分からず推定するとどうなるのか？ ユーザー⾏動 𝑐 は現実には観測できないので、代わりに ̂ 𝑐 を⽤いるとする. August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 28 重なりの度合いが重要
29. ユーザー⾏動が分からず推定するとどうなるのか？ ユーザー⾏動 𝑐 は現実には観測できないので、代わりに ̂ 𝑐 を⽤いるとする. August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 29 small bias large bias 偏りの原因になる 重なりの度合いが重要
30. 偏りと分散のトレードオフを調整するには？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 30 action set
31. 偏りと分散のトレードオフを調整するには？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 31 action set 弱い仮定または仮定なしの場合 = 偏りが⼩さいが, 分散は⼤きくなる
32. 偏りと分散のトレードオフを調整するには？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 32 action set 強い仮定 (例: IIPSのindependentなど) = 偏りは⼤きいが, 分散は⼩さくできる 弱い仮定または仮定なしの場合 = 偏りが⼩さいが, 分散は⼤きくなる
33. 偏りと分散のトレードオフを調整するには？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 33 action set 強い仮定 (例: IIPSのindependentなど) = 偏りは⼤きいが, 分散は⼩さくできる 弱い仮定または仮定なしの場合 = 偏りが⼩さいが, 分散は⼤きくなる 偏りと分散の トレードオフが存在
34. 偏りと分散のトレードオフを調整するには？ August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 34 action set 𝒄 を正確に推定するより、 $ 𝒄 をより良い偏り-分散のトレードオフを 実現するために最適化できないか? 強い仮定 (例: IIPSのindependentなど) = 偏りは⼤きいが, 分散は⼩さくできる 弱い仮定または仮定なしの場合 = 偏りが⼩さいが, 分散は⼤きくなる
35. 偏りと分散のトレードオフを調整するには？ ユーザー⾏動 バイアス バリアンス MSE 真のユーザー⾏動 0.0 0.5 0.50 最適化したユーザー⾏動 0.1 0.3 0.31 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 35 (バイアス)2 + バリアンス＝MSE action set 𝒄 を正確に推定するより、 $ 𝒄 をより良い偏り-分散のトレードオフを 実現するために最適化できないか?
36. 偏りと分散のトレードオフを調整するには？ ユーザー⾏動 バイアス バリアンス MSE 真のユーザー⾏動 0.0 0.5 0.50 最適化したユーザー⾏動 0.1 0.3 0.31 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 36 (バイアス)2 + バリアンス＝MSE action set 𝒄 を正確に推定するより、 $ 𝒄 をより良い偏り-分散のトレードオフを 実現するために最適化できないか? これをcontext毎にやりたい！
37. どうやってユーザー⾏動を 推定 最適化 すれば良い? August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 37 MSEを最小化するように 理論分析に基づき、推定したMSEを最⼩化するようにユーザー⾏動を最適化。
38. どうやってユーザー⾏動を 推定 最適化 すれば良い? August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 38 MSE estimation: [Su+,20] [Udagawa+,23] MSEを最小化するように 理論分析に基づき、推定したMSEを最⼩化するようにユーザー⾏動を最適化。
39. どうやってユーザー⾏動を 推定 最適化 すれば良い? 理論分析に基づき、推定したMSEを最⼩化するようにユーザー⾏動を最適化。 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 39 context space MSEを最小化するように
40. どうやってユーザー⾏動を 推定 最適化 すれば良い? 理論分析に基づき、推定したMSEを最⼩化するようにユーザー⾏動を最適化。 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 40 context space MSEを最小化するように
41. どうやってユーザー⾏動を 推定 最適化 すれば良い? 理論分析に基づき、推定したMSEを最⼩化するようにユーザー⾏動を最適化。 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 41 context space MSEを最小化するように
42. どうやってユーザー⾏動を 推定 最適化 すれば良い? 理論分析に基づき、推定したMSEを最⼩化するようにユーザー⾏動を最適化。 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 42 context space MSEを最小化するように
43. Experiments August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 43
44. 多様なユーザー⾏動下で実験 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 44 依存するポジションからの作用 (simple) (diverse) (complex) user behavior distributions
45. AIPSは多様なユーザー⾏動下で正確な推定を可能に IPS (⾚)：どんなユーザー⾏動に対しても分散が⼤きい August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 45 performance: a lower value is better (simple) (diverse) (complex) user behavior distributions
46. AIPSは多様なユーザー⾏動下で正確な推定を可能に IIPS (⻘) RIPS (紫)：分散は⼩さいが、複雑なユーザー⾏動で偏りが⼤きい August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 46 performance: a lower value is better (simple) (diverse) (complex) user behavior distributions
47. AIPSは多様なユーザー⾏動下で正確な推定を可能に AIPS (true) (灰⾊)：不偏性を満たしながら分散を下げるのでMSEが⼩さく August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 47 performance: a lower value is better (simple) (diverse) (complex) user behavior distributions
48. AIPSは多様なユーザー⾏動下で正確な推定を可能に AIPS (true) (灰⾊)：しかし、ユーザー⾏動が複雑になると徐々に分散が⼤きく August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 48 performance: a lower value is better (simple) (diverse) (complex) user behavior distributions
49. AIPSは多様なユーザー⾏動下で正確な推定を可能に AIPS (緑) ：偏りと分散を両⽅バランス良く⼩さくできる August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 49 performance: a lower value is better (simple) (diverse) (complex) user behavior distributions
50. AIPSは多様なユーザー⾏動下で正確な推定を可能に AIPS (緑) ：特に多様かつ複雑なユーザー⾏動のもとで正確に性能推定! August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 50 performance: a lower value is better (simple) (diverse) (complex) user behavior distributions
51. AIPSは様々な実験条件下で正確な推定を可能に AIPSは状況に適応的に偏り-分散のバランスを取ることでMSEを最⼩化 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 51 lengths of ranking data sizes
52. 実データ実験 Eコマースサイトの実データで実験 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 52 75% 以上の試行で既存手法より正確に 特に最悪ケースの性能を改善
53. まとめ • 偏り-分散のバランスの調整が正確なオフライン評価の鍵に。 • しかし、既存⼿法は全員のユーザーに⼀様なユーザー⾏動モデルを仮定し、 多様なユーザー⾏動とのミスマッチから余分な偏りや分散が発⽣。 • 対して、提案したAIPSでは多様なユーザー⾏動に対し適応的な ユーザー⾏動モデルにより、より正確かつデータ効率の良い性能推定が可能。 AIPSは多様なユーザー⾏動下でも⾮常に正確なオフライン評価を実現! August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 53
54. Thank you for listening! contact: hk844@cornell.edu August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 54
55. References August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 55
56. References (1/2) [Saito+,21] Yuta Saito, Shunsuke Aihara, Megumi Matsutani, and Yusuke Narita. “Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation.” NeurIPS dataset&benchmark, 2021. https://arxiv.org/abs/2008.07146 [Li+,18] Shuai Li, Yasin Abbasi-Yadkori, Branislav Kveton, S. Muthukrishnan, Vishwa Vinay, and Zheng Wen. “Offline Evaluation of Ranking Policies with Click Models.” KDD, 2018. https://arxiv.org/abs/1804.10488 [McInerney+,20] James McInerney, Brian Brost, Praveen Chandar, Rishabh Mehrotra, and Ben Carterette. “Counterfactual Evaluation of Slate Recommendations with Sequential Reward Interactions.” KDD, 2020. https://arxiv.org/abs/2007.12986 [Strehl+,10] Alex Strehl, John Langford, Sham Kakade, and Lihong Li. “Learning from Logged Implicit Exploration Data.” NeurIPS, 2010. https://arxiv.org/abs/1003.0120 [Athey&Imbens,16] Susan Athey and Guido Imbens. “Recursive Partitioning for Heterogeneous Causal Effects.” PNAS, 2016. https://arxiv.org/abs/1504.01132 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 56
57. References (2/2) [Kiyohara+,22] Haruka Kiyohara, Yuta Saito, Tatsuya Matsuhiro, Yusuke Narita, Nobuyuki Shimizu, and Yasuo Yamamoto. “Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model.” WSDM, 2022. https://arxiv.org/abs/2202.01562 [Su+,20] Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. “Adaptive Estimator Selection for Off-Policy Evaluation.” ICML, 2020. https://arxiv.org/abs/2002.07729 [Udagawa+,23] Takuma Udagawa, Haruka Kiyohara, Yusuke Narita, Yuta Saito, and Kei Tateno. “Policy-Adaptive Estimator Selection for Off-Policy Evaluation.” AAAI, 2023. https://arxiv.org/abs/2211.13904 August 2023 Adaptive OPE of Ranking Policies @ KDDʼ23 57