A Note on the Two Dependent Bernoulli Arms

2 002 , V ol. 13, N o.2 p p 195～2 00

A N ot e on t h e T w o D e pe n de n t B e rn ou lli A rm s D al H o K im ¹⁾ ・Y oung Joon Ch a・Jae M an Le e ^{2 )}

A b s tra c t

W e con sider th e Bern ou lli t w o - arm ed b an dit problem . It is w ell kn ow n th at th e m y optic str at eg y is optim al w h en th e prior distribut ion is con cen tr at ed at t w o p oint s in th e un it s qu ar e. W e in v estig at e s ev er al ca se s in t h e u nit squ ar e w h et h er th e m y opt ic st r at egy is opt im al or n ot . In g en eral, t h e m y optic st r at egy is n ot optim al w h en t h e prior dist ribu tion is n ot con cen t rat ed at t w o point s in t h e u nit squ ar e

K e y w o rd s : Ban dit pr oblem , Bern ou lli, m y opic, opt im al., prior dist ribu t ion , t w o - arm ed.

1 . T w o - A rm e d B an dit P ro ble m s

Con sider t w o depen dent B ern oulli arm s (or ex perim en t s ) w ith t h e prior for (

,

) on ly con cen tr at ed on t w o point s in t h e u nit squ are . S o arm 1 g en er at es i.i.d. Bern oulli r an dom v ariables (g en erically den ot ed by X ) w it h m ean

, an d arm 2 g en er at es i.i.d . Bern ou lli r an dom v ariab les (g en erically den ot ed by Y ) w it h m ean

. F u rth erm or e, ev ery ^X is in dep en den t of ev ery ^Y . T h e dis cou nt s equ en ce is t h e N - h orizon un iform . Obj ect iv e is t o m ax im ize t h e ex p ect ed sum of N ob serv at ion s w h en N is fix ed . T his t w o- arm ed Ban dit problem is w ell int r odu ced in B erry an d F rist edt (1985).

It is of int er est t o kn ow un der w h at con dition s t h e m y opic str at eg y is opt im al : alw ay s select th e arm w it h g reat er m ean . It is called m y opic b ecau s e it "b eh av es "

a s if t h er e w er e alw ay s ju st on m ore trial t o b e allocat ed. W h en th e m y opic str at eg y is opt im al, it m ean s t h at t h e opt im al st rat eg y does n ot depen d on th e n um b er of t rials r em ainin g : it is tim e in v arian t , s o t o sp eak .

F eldm an (1962) con sider ed t his pr oblem in t h e ca se t h at (

,

) is eith er

1. Depar tm ent of St atist ics , Kyungpook Nation al Univ er sity , 702- 701, Kor ea E - m ail : dalkim @knu .ac.kr

2. Depar tm ent of St atist ics , Andon g Nation al Univ er sity , Kyeon gbuk 760- 749, Kor ea

( a , b) or ( b , a ) w h ere 0 a < b 1 . S o t h e dist ribu tion of (

,

) can b e specified by th e sin gle n um b er = P (

= a ) = P (

= b) . H e con sider ed th e pr ocedu re w hich m in im ize s t h e ex pect ed nu m b er of "m ist ak es " m ade by th e st atist ician du rin g th e pr ocedu r e (or m inim izes t h e ex pect ed n um b er of t h e in ferior arm ). In fact , t his is equ iv alen t t o m ax im izin g t h e ex pect ed nu m b er of su cce s ses in t his situ at ion .

F or j = 1 , , N an d 0 1 , w e sh all con sider th e sit u ation in w hich th e t ot al n um b er of ob serv ation s r em ainin g t o b e t ak en is j an d t h e dist ribu t ion of

an d

2

is specified by t h e pr ob ability = P (

= a ) . In t his sit u ation , let

X

den ot e t h e pr ocedur e w hich specifies t h at th e fir st ob s erv at ion sh ould b e t ak en on X an d t h en an opt im al procedur e sh ould b e adopt ed ov er t h e rem ain in g j - 1 ob serv ation s , an d let m

( ) den ot e th e ex pect ed nu m b er of m ist ak es durin g th e

j ob serv ation s for w h ich t h e procedur e

X

is u sed . S im ilarly , let

Y

den ot e t h e pr ocedu re w hich specifies t h at t h e fir st ob serv at ion sh ou ld b e t ak en on Y an d t h en an opt im al procedur e sh ould b e adopt ed ov er t h e rem ain in g j - 1 ob serv ation s , an d let m

( ) den ot e t h e ex p ect ed n um b er of m ist ak es w h en th e pr ocedu re

Y

is u s ed.

F u rth erm or e, let

X Y

b e th e procedur e w hich specifies t h at t h e fir st ob serv ation sh ould b e t ak en on X , t h e secon d ob serv at ion sh ou ld b e t ak en on Y , an d th en an opt im al pr ocedu r e sh ould b e adopt ed ov er th e r em ain in g j - 2 ob serv ation s . S im ilarly , let

YX

b e t h e pr ocedu r e w h ich specifies t h at t h e fir st ob serv ation sh ould b e t ak en on Y , t h e secon d ob s erv at ion sh ould b e t ak en on X , an d th en an opt im al pr ocedu r e sh ould b e adopt ed ov er th e r em ain in g j - 2 ob serv ation s . A lso, let m

( ) an d m

( ) b e t h e ex pect ed n um b er s of m ist ak es for t h es e pr ocedu r es .

A s u su al, for t h e prior pr ob ab ilit y , let ( X ) , ( Y ) , ( X , Y ) , or ( Y , X ) den ot e t h e post erior pr ob ab ilit y w h en eit h er X (or Y ) is t ak en or ( X , Y ) (or ( Y , X ) ) ar e t ak en in th at or der . T h e follow in g t w o lem m a s an d T h eor em 1 ar e g iv en in DeGr oot (1970).

L e m m a 1 . F or an d for 0 1 , j = 2 , 3 , m

( ) = m

( ) .

L e m m a 2 . F or each fix ed v alu e of t in t h e int erv al 0 t 1 , t h e pr ob ab ilit ies P { ( X ) t } an d P { ( Y ) t } ar e n on decr ea sin g fu n ction s or ( 0 1 ).

T h e o re m 1 . Let

b e a procedur e w hich specifie s t h at an ob serv at ion

sh ould b e t ak en on X at an y st ag e for w h ich = P (

= a ) < 1 / 2 an d t h at an

ob serv ation sh ould b e t ak en on Y at an y st a g e for w hich > 1 / 2 . T h en

is an opt im al sequ ent ial pr ocedur e.

T h eor em 1 m ean s th at at ev ery st ag e th e st at ist ician sh ould t ak en an ob serv ation on t h e ran dom v ariab le X an d Y for w h ich t h er e is t h e gr eat er pr ob ab ilit y t h at th e ob serv ed v alu e w ill b e 1. In oth er w ord s , th e opt im al pr ocedu re is t h e m y opic pr ocedur e un der w hich th e st at ist ician m ak es a ch oice at each st ag e a s if it w er e t h e fin al st ag e.

K elley (1974 ) con sider ed t h e ca se t h at t h e prior for (

,

) is con cent r at ed on t w o p oint s : ( a , b) an d ( c , d ) w h er e 0 a , b , c , d 1 . F or n = 0 , , N , let V

( ) den ot e t h e optim al ex pect ed g ain for t h e r em ain in g n trials w h en is t h e curr ent prior distribut ion for (

,

) . T h es e fu n ction s ar e defin ed by th e follow in g r ecur siv e form ula s .

V

( ) = 0 , an d

V

( ) = m ax {E [ X + V

( ( X ) ) ] , E [ Y + V

( ( Y ) ) ]} for n = 1 , , N , w h er e ( X ) den ot es t h e p ost erior distribut ion aft er an ob serv at ion on X , an d

( Y ) t h e p ost erior dist rib ut ion aft er an ob serv at ion on Y . It follow s from ab ov e form u la s t h at th er e ex ist s fu n ct io V

( ) = max {F

( ) , G

( ) } n s F

( ) an d

G

( ) su ch t h at

for n = 1 , , N

T h es e fun ction s are als o defin ed r ecu r siv ely . Let ^F

( ) = 0 an d ^G

( ) = 0 . T h en for n = 1 , , N ,

F

( ) = E [ X + m ax {F

( ( X ) ) , G

( ( X ) ) }] , an d

G

( ) = E [ Y + m ax {F

( ( Y ) ) , G

( ( Y ) ) }] .

Let D

( ) = F

( ) - G

( ) , t h e r elat iv e a dv ant ag e of ex p erim en t 1 ov er ex p erim en t 2. Recur siv e form ula s m ay b e dev elop ed for defin in g D

( ) . In fact ,

D

( ) = E (

) - E (

) , an d for n = 2 , , N ,

D

( ) = E [ D

( ( X ) )

] + E [ D

( ( Y ) )

] w h er e X

den ot es m ax {X , 0 } an d X

den ot es m in {X , 0 } .

U sin g th ese form ula s , t h e optim al st r at egies can b e ch ar act erized . If a b an d

c d , t h en ^D

( ) 0 for all an d for ^{n = 1 , , N} . S o th e optim al st r at egy is

t o alw ay s u se arm 2. N ow a s su m e th at b > a an d c > d .

T h e o re m 2 . F or each n = 1 , 2 , . N , t h e follow in g ar e t ru e :

(ⅰ) D

( ) is a st rict ly in cr ea sin g fun ct ion of . (ⅱ) D

( ) is a con t in u ou s fun ct ion of .

(ⅲ) D

( ) < 0 an d D

( ) > 0 .

(ⅳ) T h er e ex ist s an u niqu e

( 0 , 1) su ch th at D

(

) = 0 .

T h eor em 2 w a s pr ov ed by K elly (1974 ). T his t h eor em m ean s t h at t h e optim al str at eg y is det erm in ed by an u niqu e sequ en ce of con st ant s

,

, , ,

. F r om ab ov e r esu lt s , it follow s th at w h en ev er a b an d c d th e m y opic str at eg y is opt im al. A lso, t his is t ru e w h en ev er a b an d c d . W h en b > a an d c > d , from ab ov e t h eor em , t h e m y opic st r at egy w ill b e opt im al if an d only if

1

=

= =

= w h er e

,

, ,

ar e t h os e u niqu e con st an t s det erm in in g t h e opt im al st r at egy .

In s ear ch for con dit ion s un der w h ich t h e m y opic st rat eg y is opt im al, K elley (1974 ) sh ow ed t h at for N 3 , ex cept for som e sim ple special ca ses , F eldm an ' s a s sum ption th at a = d an d b = c is n eces s ary for th e con clu sion t h at m y opic st rat eg ie s ar e optim al.

T h e o re m 3 . S u ppose t h e prior dist ribu tion on (

,

) is con cent r at ed at t w o poin t s ( a , b) an d ( c , d ) in t h e un it squ ar e an d t h at N 3 . T h e m y opic str at eg y is opt im al if an d on ly if on e of t h e follow in g fou r con dition s h old s .

(ⅰ) a b an d c d , (ⅱ) a b an d c d , (ⅲ) a + b = c + d = 1 , (ⅳ) ( c , d ) = ( b , a ) .

T h eor em 3 w a s also pr ov ed by K elly (1974 ). T his t h eorem g iv e s n eces sary an d sufficient con dit ion s for t h e opt im alit y of t h e m y optic st r at egy in t erm s of

a , b, c an d d .

2 . M ain Re s ult s

N ow w e con sider m ore g en er al sit u at ion s . Qu est ion : Ev en if th e prior dist ribu tion is n ot con cen tr at ed at t w o p oint s , does th e m y opic str at eg y r em ain opt im al for som e ca ses ?

Let G b e t h e dist ribu t ion on { (

,

) | 0

1 , i = 1 , 2 } , an d let F

b e t h e

corr esp on din g m arg in al dist ribu tion of th e

( i = 1 , 2 ) .

Ca se 1: { (

,

) |

= 0 } .

S in ce F

is t o th e righ t of F

, w e alw ay s u se arm 2. S o t h e m y opic str at eg y is opt im al.

Ca se 2: { (

,

) |

} . S in ce

a .s ., w e alw ay s u se arm 1. S o th e m y opic st rat eg y is opt im al.

Ca se 3 : { (

,

) |

+

= 1 } . Let v

= E [

] an d v

= E [

] . S o E [

] = 1 - v

an d E [

] = 1 - 2 v

+ v

. Let n = 2 . A s su m e st ay - on - a - w inn er

ru le. Con sider

= v

+ v

+ ( 1 - v

) [ ( v

- v

) / ( 1 - v

) ( 1 - v

) ] - { ( 1 - v

) + ( 1 - 2v

+ v

) + v

[ ( v

- v

) / v

v

]}

w h er e den ot es m ax im u m . W e sh ow t h at if v

1 / 2 , t h en 0 for an y v

su ch th at v

v

v

. N ow

= 2 ( 2v

- 1) + [ ^{( v}

- v

) ( 1 - v

)

] ^- [ ^{( v}

- v

) v

] ^.

ⅰ) ( v

- v

) > v

: = 2 ( 2v

- 1) 0 .

ⅱ) ( 1 - v

) ( v

- v

) v

: = 2( 2v

- 1) + ( v

- v

) - v

= ( 2v

- 1) + [ ( v

- v

) - ( 1 - v

)

] 0 .

ⅲ) ( v

- v

) < ( 1 - v

)

: = 2 ( 2v

- 1 ) + ( 1 - v

)

- v

= 2v

- 1 0 . N ow con sider

' = v

+ v

[ v

/ v

( 1 - v

) ] + ( 1 - v

) [ ( v

- v

) / ( 1 - v

) ( 1 - v

) ]

- { ( 1 - v

) + ( 1 - v

) [ ( 1 - 2v

+ v

) / ( 1 - v

) v

] + v

[ ( v

- v

) / v

v

]}

= ( 2v

- 1) + [ v

v

( 1 - v

) ] + [ ( v

- v

) ( 1 - v

)

]

- [ ( 1 - 2v

+ v

) v

( 1 - v

) ] - [ ( v

- v

) v

] S in ce [ v

v

( 1 - v

) ] [ ( 1 - 2v

+ v

) v

( 1 - v

) ]

an d

( 2v

- 1) + [ ^{( v}

- v

) ( 1 - v

)

] ^- [ ^{( v}

- v

) v

] ^{0 from ca se,} w e can g et ea sily ' 0 .

Ca se 4 : { (

,

) | 0

,

1 } In g en er al, m y opic str at eg y is n ot opt im al in

t h e un it squ are . W e h av e t h e follow in g coun t er ex am ple. A s su m e n = 2 . Con sider

G = F

F

, dF

(

)

( 1 -

)

d

, an d dF

(

) d

. T h en

E (

| F

) = 1 / 2 - for s om e > 0 an d E (

| F

) = 1 / 2 . S o in th is ca se , m y opic

str at eg y is n ot optim al.

Re f e ren c e

1. Berry , D . A . an d F rist edt B . (1985 ) B an d it P roblem s , Ch apm an an d H all, N ew Y ork .

2. D eGr oot , M . H . (1970) Op t im al S ta tis tical D e cis ions , M cGr aw - H ill, N ew Y ork .

3. F eldm an , D . (1962) Con t ribu tion s t o t h e ' t w o- arm ed b an dit ' problem . A nn. M a th. S ta t is t . 33: 847 - 856.

4. K elley , T . A . (1974 ) A n ot e on t h e Bern ou lli t w o- arm ed b an dit problem . A nn. S ta t is t. 2: 1056 - 1062.

[ 2002년 9월 접수, 2002년 10월 채택 ]