CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning.

[usaito]

0. 論文概要

Yi Su, Lequn Wang, Michele Santacatterina, Thorsten Joachims. CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning. arXiv:1811.02672.

1. 要約

• Off-Policy Evaluationにおける新たな推定量であるCABを提案
• CABは, Clipped IPSやDMよりbiasが小さく, IPSやDRよりもvarianceが小さい
• CABは, sub-differentiableなためpolicy optimizationの目的関数としても使える.

2. 背景

• 近年Off-Policy Evaluationでは良好なbias-varianceを達成するためにIPSとDMを混ぜるアプローチが主流
• その中のStatic Blending (SB)は, propensity scoreにadaptiveではなく, switchはsub-differentiableではないため, policy optimizationの目的関数として用いることができない.
• propensity scoreについてadaptiveにblendingすることでSBよりも良い推定精度を誇り, かつsub-differentiableな推定量を作りたい.

3. 手法

Notation

OPEは, logging policy π_0 によって集められたログデータSを用いて, new policy πの性能を推定したいという問題設定.

ここで, policyの性能(expected reward)は以下のように定義される.

また, Rをよく推定することができれば, これを最適化することで新たな方策を作ることも可能である. (Off-Policy Learning)

Estimators

まずは既存の推定量をいくつか紹介する.

• Direct Method (DM)
  DMは, 報酬構造をモデル化することによりexpected rewardを推定するという考え方. δが報酬の推定値である. この手法は, 報酬構造をうまくモデル化できなかった際にbiasが大きくなってしまうことが指摘されている.

• Inverse Propensity Score (IPS)
  IPSは, logging policy π_0を推定することを通してexpected rewardを推定しようとする考え方. pは, propensity scoreと呼ばれ, 真の値がSに含まれるならば, IPSによる推定は不偏であることが示される. しかし, pは多くの場合推定せねばならず, その推定に誤差が生じた場合, expected rewardの推定にもbiasが生まれる.

• Clipped Inverse Propensity Score (CIPS)
  IPSは, π / p の値 (importance weight)がとても大きくなるようなサンプルが存在する場合, 推定の分散が大きくなってしまうという問題を抱えている. これを軽減するために, importance weightの値が定数Mより大きくならないような制約を加えたのがCIPSである.

• Doubly Robust (DR)
  DMはbiasが大きい, IPSはvarianceが大きいという問題をそれぞれ抱えていた. DRは, DMとIPSを組み合わせることにより, DMよりbiasが小さくIPSよりvariaceが小さい推定量を構築するという考え方で広く用いられている.

• Static Blending (SB)
  SBは, DMとIPSを組み合わせるという意味ではDRと似た考え方に基づくが, DMとIPSで独立にexpected rewardを推定した上で, それらの推定値の重み付け平均により最終的な推定を行う.

• SWITCH
  SWITCHは, SBよりもAdaptiveな推定量で, importance weightの値に基づいて, サンプルごとにDMとIPSのどちらを用いるか決定する（switchする）という方法である. この方法の問題点は, indicator functionの存在により微分不可能な点を含むことから, policy optimizationに用いることができないことである.

Proposed Estimator

• Continuous Adaptive Blending (CAB)
  CABは, importance weightについてadaptiveにDMとIPSをblendingする部分で, SWITCHとは異なり重み付け平均を用いることでsub-differentiableな推定量である.

Theoretical Analysis

CABのbiasとvarianceを以下のように導出した.

CABのbiasはDMやCIPSのそれより小さく, varianceはDRやIPSのそれよりも小さいと主張されている.

4. 実験

複数の推定量による比較がなされている実データでの実験についてのみ紹介する.

Off-Policy Evaluation

OPEでよく用いられるmulti-class classificationのデータを用いた検証. UCIから9つのデータセットについて, 各推定量の真のexpected rewardに対するMSEで評価. ハイパーパラメータMを持つ推定量に関しては, Mをlog-scaleで変化させた時のMSEのグラフが描画されている.

CABは, SWITCHと同程度かそれ以上の推定精度を示しただけでなく, どのデータセットに対しても安定してある程度の推定精度を誇っていることが見て取れる.

Unbiased Learning-to-Rank

ここでは, Yahoo LTR challenge corpusを用いて, LTRのimplicit feedbackログデータを用いてpolicyの性能を推定する. 評価方法は先ほどと同じ. データ数を4段階用意してそれぞれで実験した.

Off-Policy Evaluationと同等の結果で, CABが安定した性能を見せた.

5. コメント

• policy optimizationにも使うことができる形で精度が高い推定量を構築したのは非常に大きい
• 一方で, DMとIPSをいかにblendするか、というアイデアでの研究はそろそろ限界にきつつあると感じた. 新しいフレームワークが台頭してきそう

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

• Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning.
  In International Conference on Machine Learning (ICML), 2011.