調べた方法1. 理論的に保証されてる!: Off-Policy Evaluation手法を用いて過去のログデータからオンライン性能を推定(@ ファッションアイテムの推薦)
- 自分はusaitoさん & wantedlyさんの勉強会に参加してこのOff-Policy Evaluation(以下、OPE) 分野を知った。
- 今回は概要紹介 & 自分の感想を話すので、更に詳しくはusaitoさんの資料やOPE関連の論文を読むと良さそう!
Off-Policy Evaluation(OPE)とは?
OPEは新しいpolicyを製品に導入することなく、その性能を正確に評価する事を目的とした方法論。具体的には、稼働中の意思決定システム logging policy \(\pi_{0}\) で得たログを使って、施策 target policy \(\pi\) のオンライン性能を推定したい。
OPE文献で用いられるnotation
- \(\mathbf{x} \in X\): contextベクトル(モデルに入力する特徴量…!)
- \(a \in A\): 意思決定タスクにおいて選択される行動(action)。基本的には離散変数。\(A\) は行動空間。
- \(\pi(a|\mathbf{x})\): 意思決定policyが context \(\mathbf{x}\) を受け取って行動 \(a\) を選択する確率。
- \(r \sim p(r|\mathbf{x}, a)\): 選択された行動に基づいて得られる報酬(reward)(ex. click, 購入, 翌週も継続利用してくれる)
強化学習っぽいnotation…!Off-Policy Learningという分野もあるっぽいし、 contextual banditを想定したOPE論文が多い印象…!🤔
OPEが解きたい問題:
まず、任意の意思決定policyの性能を以下の様に定義(=要は報酬の期待値!🤔):
\[
V(\pi)
:= \mathbb{E}_{p(\mathbf{x})\pi(a|\mathbf{x})p(r|\mathbf{x},a)}[r]
= \mathbb{E}_{p(\mathbf{x})\pi(a|\mathbf{x})}[q(\mathbf{x},a)]
\]
ここで \(q(\mathbf{x}, a) := \mathbb{E}[r|\mathbf{x}, a]\) は、あるcontext \(\mathbf{x}\) において行動 \(a\) を選択した場合の報酬 \(r\) の期待値。 (ex. 報酬 \(r\) をclickするか否かと定義した場合は、\(V(\pi)\) はCTRになる🤔)
OPEでは、\(\pi_{0}\) で得られた過去の \(n\) 個のログデータ \(D := {(\mathbf{x}_i, a_i , r_i)}_{i=1}^{n}\) のみを用いて、(\(\pi_{0}\) とは異なる) \(\pi\) の性能 \(V(\pi)\) を高い精度で推定したい。その為にOPE推定量 \(\hat{V}(\pi)\) を開発したい。
そしてOPE推定量の精度は、MSE(平均二乗誤差)によって定量化される:
\[
MSE(\hat{V}(\pi)) = \mathbb{E}_{D} [(V(\pi) - \hat{V}(\pi;D))^2]
\]
各OPE推定量を比較する為の視点: biasとvariance
OPE推定量の評価に用いるMSE(平均二乗誤差)は、以下の様に \((推定量のbias)^2\) と \((推定量のvariance)\) に分解できる。
\[
MSE(\hat{V}(\pi)) = \mathbb{E}_{D} [(V(\pi) - \hat{V}(\pi;D))^2]
\\
= Bias[\hat{V}(\pi)]^2 + \mathbb{V}_{D}[\hat{V}(\pi;D)]
\]
よって、各OPE推定量の良し悪しを比較する際はbiasとvarianceに注目すると良いらしい。 (ex. 推定量Aは biasは小さいがvarianceが大きい。推定量Bはbiasは大きいがvarianceが小さい)
代表的な3つのOPE推定量
基本的にこれら3つのOPE推定量が、OPE研究の基礎になっているらしい:
- DM(Direct Method)推定量
- IPS(Inverse Propensity Scoring)推定量
- DR(Doubly Robust)推定量
この3つのOPE推定量さえ抑えておけば、他の多くのOPE論文が読みやすいはず…!
代表的なOPE推定量① DM(Direct Method)
過去の観測データから事前に報酬期待値 \(q(\mathbf{x}, a) := \mathbb{E}[r|\mathbf{x}, a]\) の予測モデル \(\hat{q}(\mathbf{x}, a)\) を学習しておき、それをOPEに用いる。
\[
\hat{V}_{DM}(\pi;D) = \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{\pi}[\hat{q}(\mathbf{x}_{i}, a)]
\]
- 特徴: OPEの精度が報酬予測モデル \(\hat{q}\) に大きく依存する為、biasは大きい。一方でvarianceは小さい。
- ただそもそも精度の良い報酬予測モデル \(\hat{q}\) を作れる時点で、それを使った意思決定policyを運用すれば良いので、OPEとしての実用性は低め。
代表的なOPE推定量② IPS(Inverse Propensity Scoring)
観測された各報酬 \(r_i\) を、logging policy による行動の選ばれやすさ(=propensity score) の逆数で観測報酬を重み付けしたOPE推定量。
\[
\hat{V}_{IPS}(\pi;D)
= \frac{1}{n} \sum_{i=1}^{n} \frac{\pi(a_i|\mathbf{x}_i)}{\pi_{0}(a_i|\mathbf{x}_i)} r_{i}
\]
- biasは小さい(=仮定を満たせば不偏: \(\mathbb{E}_{D} [\hat{V}_{IPS}(\pi)] = V(\pi)\))。
- データ数nが小さい時は分散が大きく不安定だが、nが大きくなるにつれ真の値に収束。
- 先進的なOPE推定量の多くがこのIPS推定量に基づいており、重要なOPE推定量。
- \(\frac{\pi(a_i|\mathbf{x}_i)}{\pi_{0}(a_i|\mathbf{x}_i)}\) を重要度重みと呼ぶ。
代表的なOPE推定量③ DR(Doubly Robust)
DMとIPSを組み合わせた推定量。 DM推定量をベースラインとしつつ、報酬期待値予測モデル \(\hat{q}\) の誤差をIPS重み付けで補正している。
\[
\hat{V}_{DR}(\pi;D) = \hat{V}_{DM}(\pi;D)
\\
+ \frac{1}{n} \sum_{i=1}^{n} (r_{i} - \hat{q}(\mathbf{x}_i, a_i)) \frac{\pi(a_i|\mathbf{x}_i)}{\pi_{0}(a_i|\mathbf{x}_i)}
\]
- 特徴: DM推定量の性質により \(n\) が小さい時のvarianceを抑えつつ、IPS推定量の性質(=仮定を満たせば不偏)を受けて真の値に収束していく。
大規模行動空間を持つ意思決定タスクでOPEが難しい問題
行動空間が小さい(=行動の選択肢が少ない)場合、IPS推定量に基づく信頼性の高い手法が多く登場した。
しかしこれらの手法は、行動空間が大きい程、真のpolicy性能に対する Bias と Variance がどんどん増える可能性がある。(=後述するIPSの仮定を満たせなくなるから!) (論文読んでた感じでは、行動数が1000を超えたくらいから”大規模行動空間”と言えるのかな🤔)
よって、大規模行動空間に耐えうるOPE推定量は最近のOPE研究の主要なトピックらしい。 先日の勉強会でusaitoさんが紹介されてた「大規模行動空間に耐えうるOPE推定量の開発」の論文を読み、概要と感想を紹介します..!
IPS推定量が不偏推定量になる為の仮定
IPS推定量 \(\hat{V}_{IPS}(\pi;D)\) は、以下のCommon Support Assumptionを満たした場合に真の性能 \(V(\pi)\) に対して不偏になる:
\[
\pi(a|\mathbf{x}) > 0 \rightarrow \pi_{0}(a|\mathbf{x}) > 0, \forall a \in A, \mathbf{x} \in X
\]
つまり、「target policy \(\pi\) がsupportする(=選択し得る)全ての行動を、logging policy \(\pi_{0}\) もsupportしていてくれ！」という仮定…!
大規模行動空間であるほどこの仮定が成立しづらくなり、IPS推定量の bias & variance が増大していく。
この仮定って、 \(\pi_{0}\) が決定論的な意思決定policyの場合(= context \(\mathbf{x}\) が定まると選択する行動 \(a\) が一意に定まるpolicy)、基本的には成立できないよなぁ🤔
逆に、 \(\pi_{0}\) が全てのcontext \(\mathbf{x}\) に対して全ての行動 \(a\) を選び得る場合(ex. 一様ランダムに行動を選ぶpolicy)は仮定が成立するので、観察データさえ増やせばIPS推定量で真の性能を確度高く推定できるはず…!🤔
大規模行動空間に耐えうるOPE推定量: MIPS推定量の提案
論文では、大規模行動空間に耐えうるOPE推定量として、IPS推定量の行動 \(a\) を action embedding \(\mathbf{e}\) (i.e. 行動の特徴量みたいな!🤔) で置き換えた Marginalized IPS(MIPS)推定量を提案。
\[
\hat{V}_{MIPS}(\pi:D)
= \frac{1}{n} \sum_{i=1}^{n} \frac{p(e_i|x_i, \pi)}{p(e_i|x_i, \pi_{0})} r_{i}
\]
(IPSではlogging policy \(\pi_{0}\) が行動 \(a\) を選ぶ確率で重み付けしていたが、MIPSでは 行動の特徴 \(\mathbf{e}\) を選ぶ確率で重み付けする…!)
MIPS推定量が不偏推定量になる為の仮定
MIPS推定量が不偏になる為の条件として、以下の “Common Embedding Support Assumption” を満たす必要がある:
\[
p(e|x, \pi) > 0 → p(e|x, \pi_{0}) > 0, \forall e \in E, x \in X
\]
大規模行動空間では、前述のcommon support assumption よりも common embedding support assumption の方が遥かに成立させやすい。 (全く同じ行動をsupportしてなくても、特徴が似た行動をsupportしていればOK!)
(MIPSが不偏推定量になる為の条件はもう一つあるが割愛:No Direct Effect仮定)
(ただ結局この仮定も、logging policy \(\pi_{0}\) が決定論的なモデルの場合はかなり厳しいんだよなぁ…。OPEの観点では決定論的な推薦モデルはご法度というか、かなり扱いづらそうな印象🤔)
(ぼやき)決定論的なモデルはなぁ…
決定論的なモデル用のIPS推定量の式もあるので無理じゃないんだろうけど、logging policy \(\pi_{0}\) とtarget policy \(\pi\) が相当似てる場合を除いて、IPSが不偏推定量になる仮定を満たせないよなぁ。。。
(以下は、\(\pi\) が決定論的モデルver.の各種OPE推定量の式。元の式の特殊なケース)
\[
\hat{V}_{DM}(\pi;D)
= \frac{1}{n} \sum_{i=1}^{n} \hat{q}(\mathbf{x}_{i}, \pi(\mathbf{x}_{i}))
\]
\[
\hat{V}_{IPS}(\pi;D)
= \frac{1}{n} \sum_{i=1}^{n} \frac{\mathbb{I}[\pi(\mathbf{x}_{i}) = a_i]}{\pi_{0}(a_i|\mathbf{x}_i)} r_{i}
\]
\[
\hat{V}_{DR}(\pi;D) = \hat{V}_{DM}(\pi;D)
\\
+ \frac{1}{n} \sum_{i=1}^{n} (r_{i} - \hat{q}(\mathbf{x}_i, a_i)) \frac{\mathbb{I}[\pi(\mathbf{x}_{i}) = a_i]}{\pi_{0}(a_i|\mathbf{x}_i)}
\]
ちなみにOPEの実験はこんなデータがあればいいらしい！
(再掲)
OPEは、logging policy \(\pi_{0}\) で収集した過去の \(n\) 個のログデータ \(D := {(\mathbf{x}_i, a_i , r_i)}_{i=1}^{n}\) のみを用いて、(\(\pi_{0}\) とは異なる) target policy \(\pi\) の性能を推定する。
- → policy A で収集した \(D_{A}\) と policy B で収集した \(D_{B}\) さえ用意できれば、推定値 = \(\hat{V}(\pi_{A}; D_{B})\) と真の値= \(V(\pi_{A};D_{A})\) を比較してOPE推定量の実験ができる!
- → ABテストの際に得られるログデータを使えば、自社の環境に適したOPE推定量を探したりできそう!
- ちなみに、オープンソースのOPE実験用データセットにはOpen Bandit Datasetがある: ZOZOTOWNの推薦枠で収集されたオンライン実験データ
