バンディット問題の拡張について - 基盤(S)離散構造処理系プロジェクト

1
北海道大学
Hokkaido University
bandit 問題の拡張について
北海道大学情報科学研究科
中村篤祥
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
2
multi-armed bandit 問題とは
スロットマシンID
1
2
K
．．．
時刻tにおける
x1(t)
報酬(reward)
x2(t)
xK(t)
各時刻t(=1,2,…)においてplayerは以下のことを行う。
playerは知らない
(選んだスロットマシンにつ
いてのみ知ることができる）
1. K台のスロットマシンから１台のスロットマシンitを選ぶ。
2. 選ばれたスロットマシンitから報酬 x it ( t ) を得る。
総利得
x
it
( t ) を最大化するためには各時刻においてどのようにスロットマシン
t
を選べばよいか？
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
3
確率的なmulti-armed bandit 問題
スロットマシンID
1
2
K
．．．
成功確率
報酬
θ1
x1(t)
θ2
x2(t)
playerは知らない
時刻によらず一定
θk
xK(t)
1 if success
xi (t )  
if fail
0
•x1(t), x2(t),…,xK(t)は独立
• xi(1), xi(2),…は未知の成功確率θiのBernulli process

目標1 expected total discounted reward
t 1
γ
 E( xit (t )) の最大化 (0<γ<1)
t 1
目標2 与えられた時刻Tまでの総利得
2010/05/08
T
x
t 1
it
( t ) の最大化
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
4
確率的なmulti-armed bandit問題の戦略
・Gittins Indexが最大のスロットマシンを選ぶ
成功、失敗回数がα、βであるようなスロットのGittins Index G(α,β)
以下のような確率p：成功確率がpであるとわかっているスロットマシン1と、
（成功回数,失敗回数）=(α,β)であるような成功確率未知のスロットマシン2
があったとき、時刻t=1にどちらのスロットマシンを選んでも、
optimal expected total discounted rewardが同じになるようなp
expected total discounted rewardを最大化する戦略 [ Gittins and Jones 1974]
・ε-greedy [Sutton & Barto 1998]
1－εの確率でそれまでの平均報酬が最大のマシンを選び、
εの確率でランダムに選ぶ。
・UCB1 [Auer, Cesa-Bianchi and Fisher 2002]
時刻tに x j 
2010/05/08
囲碁プログラムのモンテカルロ木探
索に用いられて著名になった。
2 ln t
が最大のマシンjを選ぶ。
x j :マシンjのそれまでの平均報酬
nj
n j :マシンjをそれまでに選んだ回数
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
5
adversarial bandit 問題
スロットマシンID
1
2
[Auer et al. 2002]
K
．．．
xi(t)∈[0,1] for all i=1,2,…,K
時刻tにおける
x1(t)
報酬(reward)
悪魔が選ぶ。
playerは知らない
各時刻t(=1,2,…,T)においてplayerは以下のことを行う。
x2(t)
xK(t)
1. K台のスロットマシンから１台のスロットマシンitを選ぶ。
2. 選ばれたスロットマシンitから報酬 x it ( t ) を得る。
T
GA (T )   x it ( t ) : （乱択)アルゴリズムの時刻Tにおける総利得
t 1
期待総利得 E(GA (T)) が大きなアルゴリズムAは？
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
6
乱択アルゴリズムExp3
[Auer et al. 2002]
// exponential-weight algorithm
Algorithm Exp3
for exploration and exploitation
Parameter: γ∈(0,1]
Initialization: wi(1)←1 for i=1,2,…,K
for t=1 to T
1. pi ( t )  (1 γ)
w i (t)
k
 w (t )
j1

γ
for i  1,..., K
K
j
2. itをp1(t),…,pk(t)の分布に従ってランダムに選ぶ
3. 報酬 xit ( t )  [0,1] を得る
4. for j=1,…,k
x j(t)/p j(t) if j  it
x̂ j ( t )  
otherwise
0
w j ( t  1)  w j ( t ) exp(γx̂ j ( t ) / K )
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
7
Exp3のexpected (weak) regret
[Auer et al. 2002]
T
１つのスロットマシンを選び続けた場合の総利得の最大値 Gmax (T )  max  x j ( t )
j
t 1
と比べて平均的にどのくらい後悔するかをGmax(T)－E[GExp3(T)]で測ると




   min1, K lnK のとき


 (e  1)T 


Gmax (T)  E[GExp3 (T)] ≦ 2.63 TK lnK
（xj(t)∈[0,1]なので、Gmax(T)－GExp3(T)≦Tが成り立つことに注意。）
また、ある報酬割当分布が存在し、どのような乱択アルゴリズムAに対しても
E[Gmax (T)  GA (T)] 


1
min TK , T
20
が成り立つ。ただし、期待値は報酬割当とアルゴリズムの乱択の両方に関して
とるものとする。
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
8
online linear optimization 問題
[McMahan and Blum 2004]
K⊆Rn :コンパクト閉凸集合
xt∈Rn
時刻tにおける
報酬ベクトル
悪魔が選ぶ。
playerは知らない
各時刻t(=1,2,…,T)においてplayerは以下のことを行う。
xt
1. Kから１点qtを選ぶ
2. 選ばれた点qtに対する利得 xt・qt を得る。
T
GA (T )   x t  qt : （乱択)アルゴリズムの時刻Tにおける総利得
t 1
期待総利得 E(GA (T)) が大きなアルゴリズムAは？
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
9
Abernethyらのアルゴリズム
[Abernethy et al. 2008]
Algorithm BOLO (仮称)
// Bandit Online Linear Optimization
Input: η>0, θ-self-concordant R
Initialization: q1  argminqK R (q)
for t=1 to T
1. {e1,e2,…,en}←∇2R(qt)の固有ベクトル
{λ1,λ2,…,λn}← ∇2R(qt)の固有値
2. itを{1,2,…,n}からランダムに選ぶ。
εtを{－1,1}からランダムに選ぶ。
3. rt  qt   t it 1 / 2eit
4. 報酬 xt・rt を得る。
5. 次のように更新する。
1/ 2
xˆ t  n( x t  rt ) t it eit
t
qt 1  argminqK   xˆ t  q  R (q)
s 1
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
10
BOLOのexpected regretの上界
T

maxqK E( x t  q)  E(GBOLO (T))  O n T ln T
t 1



   ln T , T  8 ln Tのとき


4n T


2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
11
インターネット広告はbandit問題
広告枠
スポーツページには
どの広告を出したら
T回の表示で最も多
くクリックされるか？
player=広告配信システム
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
12
multiple play設定
広告枠は複数
１回のプレイでk個選択
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
13
FExp3-k (Exp3のmultiple play 拡張版)
Algorithm FExp3
Parameter: γ∈(0,1]
Initialization: wi(1)←1 for i=1,2,…,K
for t=1 to T
K
1



1. if argmaxj{1,2,...,K } w j ( t )     w i ( t ) (1   ) then
 k K  i1
t
1  
    (1   ) を満たすαtをもとめる。
  t   w i (t)  k K 
w i ( t ) t
w i ( t ) t
S0 (t )  {i : w i (t )   t }, w'i (t )   t for　i  S0 (t )
else
S0←φ
2. w'i (t )  w i (t )　for　i  {1,2,..., K}  S0 (t )
3.


w 'i ( t )
γ

pi ( t )  k (1 γ) K
  for i  1,..., K

w' j (t ) K 

j

1


2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
14
FExp3-k つづき(Exp3のmultiple play 拡張版)
4. S(t)←iが選ばれる確率がpi(t) になるように{1,2,…,K}からk個選択
5. 報酬xi(t)∈[0,1] for i∈S(t)を得る
6. for j=1,…,k
x j(t)/p j(t) if j  S( t )
x̂ j ( t )  
otherwise
0
w j ( t ) exp(kγx̂ j ( t ) / K ) if　j  S0 ( t )
w j ( t  1)  
w j (t)
otherwise

2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
15
FExp3のexpected (weak) regret
同じk個のスロットマシンを選び続けた場合の総利得の最大値
Gmax k (T ) 
T
max
S {1,2,...,K },|S|k
  x (t)
jS
t 1
j
と比べると
K
Gmax k (T)  E[GFExp 3 (T)] ≦ 2.63 kTK ln
k




   min1, K ln(K / k ) のとき


(e  1)kT 



また、ある報酬割当分布が存在し、どのような乱択アルゴリズムAに対しても
2

1
K

k
K k 
 


E[Gmax k (T )  GA (T )]  min 
kT 
 TK ,
8K


5  K 

が成り立つ。ただし、期待値は報酬割当とアルゴリズムの乱択の両方に関して
とるものとする。
2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム
北海道大学 Hokkaido University
16
今後の拡張について
協調フィルタリングのbanditモデル
ユーザの好みはいくつかの好みのタイプの混合として表現で
きると仮定して、最適な混合割合と比べた場合、リグレットが
少ない方法を考案する。
 情報検索のbanditモデル
１回にk個ずつ結果が提示されるとしてT回までみるとした場
合に最も多く欲しいものが含まれている結果提示方法は？適
合度フィードバックしながら適度に良い結果を返す。低次元の
学習問題にどのように落とすか。

2010/05/08
ERATO湊離散構造プロジェクトキックオフシンポジウム