Bandit algorithm memo

広告や推薦で使われるバンディットアルゴリズムの論文を読む際に死なないように調べた
LinUCB を調べて死んだ

バンディットアルゴリズム

利得が確率的に決まるものは stochastic,利得が恣意的に決められてしまう(悪魔が決める)ものは adversarial というらしい
また,腕を選ぶために専門家がいる場合(context 情報がある場合)は contextual,いない場合には non-contextual と呼ぶらしい*1

epsilon-greedy

  • 確率 epsilon でランダムに腕を選ぶ
  • 確率 1 - epsilon で利得最大の腕を選ぶ

ucb(upper confidence bound)

  • 利得と信頼の和が最大の腕を選ぶ
  • 信頼は,その腕をなんども選ぶと小さくなるような項

exp4*2

各腕から得られる文脈情報(context)を利用して,腕を選ぶ

  • 各腕から x の文脈情報が得られる
    • x は,ユーザ情報やページ情報
  • 文脈情報を 1,..,K に変換する専門家 pi_i(x) を考える
    • K は腕の数
    • pi_i(x) はマルチクラスの分類器みたいなもの
  • 専門家 pi_i(x) および専門家の信頼度 w(pi_i) から腕を選ぶf:id:laughing:20131231233253p:plain
  • ユーザが引いた腕を予測した専門家の信頼度 w(pi_i) が更新される

epoch-greedy*3

これも contextual bandit
epsilon-greedy と似ているが,exploration と exploitation をあわせて 1 epoch とし,これを繰り返す

  • ランダムに腕を選ぶ(exploration)
    • context, arm, reward を履歴として保存する
  • 全履歴を調べて,reward を最大化するような専門家を選ぶ(learning)
    • 上と同じで専門家はマルチクラスの分類器みたいなもの
  • 専門家の意見に従って,複数回腕を引く(exploitation)

LinUCB*4*5

腕ごとに context 情報 x_{t,a} が与えられるときのバンディットアルゴリズム
t-1 までに得られた context と reward から,時刻 t における reward を予測する

UCB と付くことから分かるように,UCB 的なモデルになっていて,
reward 項と upper confidence 項で構成される
a_t = {\rm argmax}_{a \in A_t} ({\bf x}_{t,a}^T \hat{\theta}_a + \alpha \sqrt{ {\bf x}_{t,a}^T {\bf A}_a^{-1} {\bf x}_{t,a} })
係数 \theta は,腕 a に関する context の履歴から線形回帰で求める
また,A は context の履歴の隣接行列で,第2項はモデルの確からしさを表す項と書かれている

各腕で共通する特徴を分けて学習する hybrid 的なモデルも書かれている

Yahoo! Research の実験では,ただの epsilon-greedy に比べて,CTR が 12% 改善したと書かれている
とは言っても,epsilon-greedy はパーソナル要素無いので...

感想

  • non-contextual bandit だと most popular 的なランキングを動的に作成するのに向いている(context が無いので,みんな一緒の物が出る)
  • contextual bandit だとユーザごとに準最適なものが出せる(context にユーザ情報が含まれる場合に限るが)ので,より広告や推薦によさそう
    • ただ,ユーザが訪れるたびに更新される系でないと意味ない感じ
    • 1日1回推薦を作るとかだと,普通に最適なものを計算したほうが良いはず

ボーダーランズ/ サイコ バンディット ラテックスマスク

ボーダーランズ/ サイコ バンディット ラテックスマスク