Bandit Problem Index

--- lang: ja-jp tags: Survey title: Bandit Problem Index --- # Bandit Problem Index ## Why - RecSys2019論文読み会での発表では、バンディットアルゴリズムを応用した調査が多数報告されており、そのインパクトの大きさを感じたため。 ## What - MLPシリーズ: 「バンディット問題の理論とアルゴリズム」 - Pythonでバンディットアルゴリズムの実装を試してみる - どのような問題を解くことができるのかについての把握をする - 腕の数って毎回変わってしまって良いのか？ - 機械学習のように腕の特徴量みたいなものを考慮することはあるのか？ - gamblrの枠組で考えるなら、$K$頭の競走馬の期待勝率が導出されている時に、オッズと合わせてどのような賭け方をすれば良いかを決定してくれる？ - ==2~4章をざっと読んだら6章のABテストに進む== ## Overview > バンディット問題（bandit problem）とは、選択肢の集合から１つの要素を選択し、その選択肢に対する報酬を得るがほかの選択肢の報酬情報は得られない、というプロセスを繰り返す設定において、報酬和の最大化を目指す逐次決定問題です。 ### Keywords - exploration - exploitation - policy - cumulative rewards ### Problems - バンディット問題が扱うのは、「探索と知識利用のバランスのとり方」 - いつもと同じものばかり選んでいたら（知識利用）、新しい良いものに気がつけない - 新しいものばかり選んでいたら（探索）、いつものやつのほうが良かったと思うこともある - 確率的バンディット・敵対的バンディット問題の２つの分類が存在する ### Terminologies - **exploration**: 探索 - **exploitation**: 知識利用 - **arm**: １回の試行における選択肢 - **policy**: どのarmを引くかを決定する方策 ### Applications - ゲーム木の探索 - オンライン経路制御 - 推薦システム - 治験 - 広告配信 ### Modeling #### Evaluation $X_{i}\left(t\right)$をアーム$i$の時刻$t$における報酬の関数とし、プレイヤーは時刻$t$において$i\left(t\right)$番目のアームを選択する。 - **有限時間区間の累積報酬**: $\sum_{t=1}^{T}X_{i\left(t\right)}\left(t\right)$ - **無限時間区間の（幾何割引）の累積報酬**: $\sum_{t=1}^{\inf}\gamma^{t-1}X_{i\left(t\right)}\left(t\right)$ #### Regret $$ \text{Regret}\left(T\right) = \max_{i\in\{1,\ldots,K\}}\sum_{t=1}^{T}X_{i}\left(t\right) - \sum_{t=1}^{T}X_{i\left(t\right)}\left(t\right) $$ 直感的な理解としては、実際に取った方策から得られる$T$時点での累積報酬よりも、ある一つのアームを引き続けた場合に得られた累積報酬の最大値がどれほど大きいかで「後悔」の程度を定量化している。期待リグレットや擬リグレットといった概念も存在する。毎回どのアームを選択するかを決定する方策そのものが確率的な振る舞いをするものもあるので、その場合には期待値を取って評価せざるを得ず、期待リグレットが利用される。 ## Stochastic Bandit Algorithm ### Keywords - 中心極限定理 - 大偏差原理 - 一貫性（consistency）: 方策の合理性 - 期待リグレットの上界・下界 - 特に期待リグレットの上界（この方策に従えば後悔の程度は高々これくらいという期待値）は方策の評価指標といえる #### 中心極限定理 > 標本平均$\hat{\mu}$の確率分布はサンプル数$n$が大きい場合は簡単には計算できませんが、その場合に最も一般的に用いられる**近似方法**が以下に述べられる中心極限定理です。中心極限定理は近似手法の一つ。標準化された標本平均$\frac{\sqrt{n}\left(\hat{\mu}_{n}-\mu\right)}{\sigma}$の分布は**標準正規分布**に弱収束する。すなわち、任意の$x \in \mathbb{R}$で次が成り立つ。 $$ \lim_{n \rightarrow \infty}\mathbb{P}\left[ \frac{\sqrt{n}\left(\hat{\mu}_{n}-\mu\right)}{\sigma} \leq x\right] = \Phi\left(x\right) $$ ただし、$\Phi\left(x\right) = \int_{-\infty}^{x}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{t^{2}}{2}\right)\text{d}t$は標準正規分布の累積分布関数を表す。標本平均のサイズ$n$が大きくなれば、標本平均が真の（母集団）平均から外れる確率が、標準正規分布によって抑え込めるということ。なお、標本平均は「標準化」されているので$\frac{\sqrt{n}\left(\hat{\mu}_{n}-\mu\right)}{\sigma}$という形式を取っていることに注意する。中心極限定理による標本平均の近似誤差は$O\left(\frac{1}{\sqrt{n}}\right)$程度であることが知られている（ベーリー・エッセンの定理）。 #### 裾確率 ![](https://i.imgur.com/WaKyn1G.png) 中心極限定理は平均が大きい分布であれば良い近似の精度を示すが、生起確率の低い事象の確率分布に対しては当てはまりが悪いことがわかる（小さい誤差で近似するために大きなサンプルが必要になる）。平均が小さい分布に対して近似を試みる時の上下限について、次のような定理がある。 ##### ヘフディングの不等式 $\text{i.i.d.}$な確率変数$X_{i} \in \left[0, 1\right]$と任意の$\Delta \gt 0$について、サイズ$n$の標本平均$\mu_{n}$について次が成立する。 $$ \mathbb{P} \left[ \hat{\mu}_{n} \leq \mu - \Delta \right] \leq \text{e}^{-2n\Delta^{2}} $$ $$ \mathbb{P} \left[ \hat{\mu}_{n} \geq \mu + \Delta \right] \leq \text{e}^{-2n\Delta^{2}} $$ 意味するところは、標本平均が真の（母集団）平均から任意の正の実数$\Delta$だけ小さい（大きい）ものとしてサンプリングされる確率は$\text{e}^{-2n\Delta^{2}}$以下になる、ということ。分布や平均$\mu$と$\Delta$の間に依存性をもたせた（なんらかを仮定した）場合には、もう少し良い近似が可能になる（例えば、$X_{i}$はベルヌーイ分布からサンプリングされる、など）。 ##### チェルノフ・ヘフディングの不等式 $\mu$と$x$はベルヌーイ分布に従う確率変数とする。 $\text{i.i.d.}$な確率変数$X_{i} \in \left[ 0, 1 \right]$と任意の$0 \leq x \leq \mu$について次が成立する。 $$ \mathbb{P} \left[ \hat{\mu}_{n} \leq x \right] \leq \text{e}^{-n \cdot d\left( x, \mu \right)} $$ また、任意の$\mu \leq x \leq 1$にたいして次が成立する。 $$ \mathbb{P} \left[ \hat{\mu}_{n} \geq x \right] \leq \text{e}^{-n \cdot d\left( x, \mu \right)} $$ ヘフディングの不等式と比較して、$\Delta$が$x$と$\mu$の間のカルバック・ライブラー情報量に置き換わっていることに注意する。ピンスカーの不等式から、$d\left( x, \mu \right) \geq 2\left( x - \mu \right)^{2}$であるから、$\text{e}^{d\left( x, \mu \right)} \leq \text{e}^{2\left( x - \mu \right)^{2}}$となり、チェルノフ・ヘフディングの不等式はより精密な上界を与えていることが言える（高々これくらいの確率に抑え込めると評価できているということ）。 #### 大偏差原理 > 低確率で起きる事象の確率を指数関数の形で評価する理論体系を**大偏差原理**と呼びます。 #### 定式化 - $K$: アームの数 - $i$: アームのインデックス（識別子） - $\mu_{i}$: アーム$i$を引いた時に得られる報酬の**期待値** - $P_{i} = P\left(\mu_{i}\right)$: 報酬の確率分布 - 各アームの報酬の期待値は全部のアームで共通の確率分布に従って得られると仮定 - $t$: 時刻 - $X_{i}\left(t\right) \sim P_{i}$: 時刻$t$にアーム$i$を引いた時の報酬（の観測値） - $i\left(t\right)$: プレイヤーが時刻$t$において引くアームの識別子 - $\mu^{\ast}$: 最適なアームについての報酬の期待値 - $N_{i}\left(t\right)$: 時刻$t$の**開始時点**までにアーム$i$を引いた回数 - つまり$t-1$までに何回$i$を引いたかということ #### 問題設定第2式で$i:\mu_{i}\leq\mu^{\ast}$としていないのは、$\mu_{i} = \mu^{\ast}$については差の項が0になるから。$\Delta_{i} = \mu^{\ast} - \mu_{i}$とする。 $$ \text{regret}\left(T\right) = \sum_{t=1}^{T}\left(\mu^{\ast}-\mu_{i\left(t\right)}\right) = \sum_{i:\mu_{i}\lt\mu^{\ast}}\left(\mu^{\ast}-\mu_{i}\right)N_{i}\left(T+1\right) = \sum_{i:\mu_{i}\lt\mu^{\ast}}\Delta_{i}N_{i}\left(T+1\right) $$ このリグレットの期待値「期待リグレット」の最小化を確率的バンディット問題では扱う。 $$ \mathbb{E}\left[\text{regret}\left(T\right)\right] = \sum_{i:\mu_{i}\lt\mu^{\ast}}\Delta_{i}\mathbb{E}\left[N_{i}\left(T+1\right)\right] $$ #### 一貫性（consistency）方策の合理性についての定義。ある方策が一貫性を持つとは、任意の固定した$a \gt 0$と真の確率分布の組$\{P_{i}\}_{i=1}^{K} \in \mathcal{P}^{K}$に対して、その方策のもとで$\mathbb{E}\left[\text{regret}\left(T\right)\right] = o\left(T^{a}\right)$が成り立つことを言う。 $T$が十分に大きいとき、期待リグレットは$T^{a}$で抑え込めることを「一貫性」と定義している。 > 方策が一貫性を持つとは、リグレットが常にどんな多項式オーダーよりも小さくなることを指しています。 #### 一貫性のある方策のもとでの期待リグレットの下界 ~~方策に一貫性が担保されていれば、「損しても高々これくらい」という状況を作り出せる、ということか？~~ ← 解釈としてはむしろ逆であり、「一貫性を保つ（合理的に十分に探索した）」と言える方策を取った場合には、「少なくともこれくらいの損をしてしまう」という**下限**を与えている。 $D\left( P\left( \mu^{\prime} \right) \| P\left( \mu \right) \right)$が$\mu \gt \mu^{\prime}$について単調増加かつ連続とする。一貫性をもつアルゴリズムを用いたとき、任意の$i \ne i^{\ast}$と十分大きい$T$に対して $$ \mathbb{E}\left[ N_{i}\left( T \right) \right] \geq \frac{\left( 1 - \text{o}\left( 1 \right) \right)\ln T}{D\left( P\left( \mu_{i} \right) \| P\left( \mu^{\ast} \right) \right)} $$ が成り立つ。また、その結果として、 $$ \mathbb{E}\left[ \text{regret} \left( T \right) \right] \geq \left( 1 - \text{o}\left( 1 \right) \right) \sum_{i:\mu_{i}\lt\mu^{\ast}} \frac{\Delta_{i} \ln T}{D\left( P\left( \mu_{i} \right) \| P\left( \mu^{\ast} \right) \right)} $$ が得られる。この定理により、ある一定の条件に従う確率変数を扱う期待リグレットはある定数よりも小さくできないことがわかる。また、問題設定に応じて$K$個の選択肢の中でどれが一番かを決めるために必要な各アームにおける試行回数の下界が導出できるということ。 ==**P.25に面白い問題がたくさん並んでいるので、あとで確認して手で解いておくこと。**== #### $\epsilon$-貪欲法一貫性のある方策であり、最も実装が容易なもの。アーム数が多い場合にはパフォーマンスがあまり良くない。 - $\hat{\mu_{i}}\left( t \right) = \frac{1}{N_{i}\left( t \right)}\sum_{s\in\{1,2,\ldots,t-1\}:i\left(s\right)=i}X_{i}\left(s\right)$: 時刻$t$に引く**前**でのアーム$i$の報酬の標本平均 - $\hat{\mu}_{i, n}$: アーム$i$を$n$回引いた時点でのアーム$i$の標本平均（大偏差原理より歪みがち） - つまり$\hat{\mu}_{i}\left(t\right) = \hat{\mu}_{i, N_{i}\left(t\right)}$ということ > 全体のアーム選択数$T$のうち$\epsilon T$回を探索期間としてすべてのアームを一様に選択し、残りの$\left( 1 - \epsilon \right)T$回を活用期間としてそれまでで最も標本平均の高かったアーム$\hat{i}^{\ast}$を引き続けるものです。 - Q. 『一様に選択』とは、一様分布からサンプリングするのか、それとも順番に（決定的に）選んでいくのか - A. 決定的に選ぶ ##### Algorithm - **パラメータ**：$\epsilon \gt 0$ - **入力**：全体のアーム選択数$T$ 1. すべてのアーム$i$を$\frac{\epsilon T}{K}回引く$ 2. アーム$\hat{i}^{\ast}\left( \epsilon T + 1 \right) = \text{argmax}_{i} \hat{\mu}_{i}^{\ast}\left( \epsilon T + 1 \right)$を$\left(1-\epsilon\right)T$回引く - $\epsilon T$回引いた時点で報酬の標本平均が最も大きいアーム$\hat{i}^{\ast}$を残りずっと引き続けるということ - Q. $\epsilon T$は$K$で割り切れる必要はある？ - A. ==WIP== ## Appendix ### カルバック・ライブラー情報量（Divergence） > 確率論と情報理論における２つの確率分布の差異を図る尺度である > 応用上は「真の」確率分布$P$と任意の確率分布$Q$に対するカルバック・ライブラー情報量が計算されることが多い自分の言葉で捉えれば、「$P$に対して$Q$は、確率変数の定義域の上で全体的にどれくらい離れているかの程度を表す尺度」となる - 離散分布・連続分布どちらの確率分布の集合に対しても定義される - 確率変数の定義域に基づいて定義されるため、離散分布同士、連続分布同士でなければ計算することはできない **$Q$の$P$に対するカルバック・ライブラー情報量**は次のように定義される。 #### 離散確率分布 $$ D_{\text{KL}}\left(Q\|P\right) = \sum_{i}Q\left(i\right)\log\frac{Q\left(i\right)}{P\left(i\right)} $$ #### 連続確率分布 $$ D_{\text{KL}}\left(Q\|P\right) = \int_{-\infty}^{\infty} q\left(x\right)\log\frac{q\left(x\right)}{p\left(x\right)} \text{d}x $$ この定義だと、ベルヌーイ分布のように確率変数が実数全体ではない連続確率分布を扱うことはできない。より一般にはラドン・ニコディム導関数というものを利用して[こんな感じ](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%90%E3%83%83%E3%82%AF%E3%83%BB%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%BC%E6%83%85%E5%A0%B1%E9%87%8F#%E5%AE%9A%E7%BE%A9)で定義されるらしい。 #### 交差エントロピーとの関連性 - **平均情報量**: $H\left(P\right)=-\sum_{X\in\Omega}P\left(X\right)\log P\left(X\right)$ - **交差エントロピー**: $H\left(P, Q\right)=-\sum_{X\in\Omega}P\left(X\right)\log Q\left(X\right)$ 上記のように定義するとき、以下のような関連性がある（連続確率分布についても同様のため省略）。 $$ D_{\text{KL}}\left(Q\|P\right) = H\left(Q, P\right) - H\left(Q\right) $$