UCB Algorithm

1/9

Regret Bound for UCB

(Adapted from the proof by Auer et al., 2002)

Shivaram Kalyanakrishnan

shivaram@cse.iitb.ac.in

Department of Computer Science and Engineering Indian Institute of Technology Bombay

August 2018

2/9

UCB

- Pull each arm once.

- At timet∈ {n,n+1, . . .}, for every arma,ucb^t_a^def= ˆp^t_a+ r2 ln(t)

u^t_a ; pullargmax_aucb^t_a.

R 1

0

pa t ucb at

Shivaram Kalyanakrishnan (2018) UCB Regret 2 / 9

2/9

UCB Algorithm

UCB

- Pull each arm once.

- At timet∈ {n,n+1, . . .}, for every arma,ucb^t_a^def= ˆp^t_a+ r2 ln(t)

u^t_a ; pullargmax_aucb^t_a.

R 1

0

pa t ucb at

2/9

UCB

- Pull each arm once.

- At timet∈ {n,n+1, . . .}, for every arma,ucb^t_a^def= ˆp^t_a+ r2 ln(t)

u^t_a ; pullargmax_aucb^t_a.

R 1

0

pa t ucb at

Recall thatR^T=Tp_⋆−PT−1 t=0 E[r^t].

Shivaram Kalyanakrishnan (2018) UCB Regret 2 / 9

2/9

UCB Algorithm

UCB

- Pull each arm once.

- At timet∈ {n,n+1, . . .}, for every arma,ucb^t_a^def= ˆp^t_a+ r2 ln(t)

u^t_a ; pullargmax_aucb^t_a.

R 1

0

pa t ucb at

Recall thatR^T=Tp_⋆−PT−1 t=0 E[r^t].

We shall show that UCB achievesR^T=O P

a:pa6=p⋆ 1

p_⋆−p_alog(T) .

3/9

∆a=p_⋆−pa(instance-specificconstant).

Shivaram Kalyanakrishnan (2018) UCB Regret 3 / 9

3/9

Notation

∆a

=defp_⋆−pa(instance-specificconstant).

LetZ_a^t be theeventthat armais pulled at timet.

3/9

∆a=p_⋆−pa(instance-specificconstant).

LetZ_a^t be theeventthat armais pulled at timet.

Letz^tabe arandom variablethat takes value 1 if armais pulled at timet, and 0 otherwise.

Shivaram Kalyanakrishnan (2018) UCB Regret 3 / 9

3/9

Notation

∆a

=defp_⋆−pa(instance-specificconstant).

LetZ_a^t be theeventthat armais pulled at timet.

Letz^tabe arandom variablethat takes value 1 if armais pulled at timet, and 0 otherwise.

Observe thatE[z^ta] =P{Za^t}(1) + (1−P{Za^t})(0) =P{Za^t}.

3/9

∆a=p_⋆−pa(instance-specificconstant).

LetZ_a^t be theeventthat armais pulled at timet.

Letz^tabe arandom variablethat takes value 1 if armais pulled at timet, and 0 otherwise.

Observe thatE[z^ta] =P{Za^t}(1) + (1−P{Za^t})(0) =P{Za^t}.

As in the algorithm,u^tais arandom variablethat denotes the number of pulls armahas received up to (and excluding) timet:

u^ta=

t−1

X

i=0

zⁱa.

Shivaram Kalyanakrishnan (2018) UCB Regret 3 / 9

3/9

Notation

∆a

=defp_⋆−pa(instance-specificconstant).

LetZ_a^t be theeventthat armais pulled at timet.

Letz^tabe arandom variablethat takes value 1 if armais pulled at timet, and 0 otherwise.

Observe thatE[z^ta] =P{Za^t}(1) + (1−P{Za^t})(0) =P{Za^t}.

As in the algorithm,u^tais arandom variablethat denotes the number of pulls armahas received up to (and excluding) timet:

u^ta=

t−1

X

i=0

zⁱa.

We define an instance-specificconstant

¯u^T_a=^def 8

(∆a)² ln(T)

that will serve in our proof as a “sufficient” number of pulls of armafor horizonT.

4/9

Shivaram Kalyanakrishnan (2018) UCB Regret 4 / 9

4/9

Step 1: Show that R

= P

a:pa6=p_⋆

E [u

]∆

.

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

4/9

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

=Tp_⋆−

T−1

X

t=0

X

a∈A

P{Za^t}E[r^t|Z^ta]

Shivaram Kalyanakrishnan (2018) UCB Regret 4 / 9

4/9

Step 1: Show that R

= P

a:pa6=p_⋆

E [u

]∆

.

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

=Tp_⋆−

T−1

X

t=0

X

a∈A

P{Za^t}E[r^t|Z^ta]

=Tp_⋆−

T−1

X

t=0

X

a∈A

E[z^ta]pa

4/9

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

=Tp_⋆−

T−1

X

t=0

X

a∈A

P{Za^t}E[r^t|Z^ta]

=Tp_⋆−

T−1

X

t=0

X

a∈A

E[z^ta]pa

= X

a∈A

E[u^T_a]

!

p_⋆−X

a∈A

E[u^T_a]pa

Shivaram Kalyanakrishnan (2018) UCB Regret 4 / 9

4/9

Step 1: Show that R

= P

a:pa6=p_⋆

E [u

]∆

.

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

=Tp_⋆−

T−1

X

t=0

X

a∈A

P{Za^t}E[r^t|Z^ta]

=Tp_⋆−

T−1

X

t=0

X

a∈A

E[z^ta]pa

= X

a∈A

E[u^T_a]

!

p_⋆−X

a∈A

E[u^T_a]pa

=X

a∈A

E[u^Ta](p_⋆−pa)

4/9

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

=Tp_⋆−

T−1

X

t=0

X

a∈A

P{Za^t}E[r^t|Z^ta]

=Tp_⋆−

T−1

X

t=0

X

a∈A

E[z^ta]pa

= X

a∈A

E[u^T_a]

!

p_⋆−X

a∈A

E[u^T_a]pa

=X

a∈A

E[u^Ta](p_⋆−pa)

= X

a:pa6=p⋆

E[u^Ta]∆a.

Shivaram Kalyanakrishnan (2018) UCB Regret 4 / 9

4/9

Step 1: Show that R

= P

a:pa6=p_⋆

E [u

]∆

.

R^T=Tp_⋆−

T−1

X

t=0

E[r^t]

=Tp_⋆−

T−1

X

t=0

X

a∈A

P{Za^t}E[r^t|Z^ta]

=Tp_⋆−

T−1

X

t=0

X

a∈A

E[z^ta]pa

= X

a∈A

E[u^T_a]

!

p_⋆−X

a∈A

E[u^T_a]pa

=X

a∈A

E[u^Ta](p_⋆−pa)

= X

a:pa6=p⋆

E[u^Ta]∆a.

To show the regret bound, we shall show for each sub-optimal armathat

E[u^Ta] =O 1

(∆a)²log(T)

.

5/9

Shivaram Kalyanakrishnan (2018) UCB Regret 5 / 9

5/9

Step 2: Split sub-optimal pulls into two regimes.

To proveE[u^Ta] =O 1

∆²_alog(T)

, we showE[u^Ta]≤¯u^Ta+Cfor some constantC.

5/9

To proveE[u^Ta] =O 1

∆²_alog(T)

, we showE[u^Ta]≤¯u^Ta+Cfor some constantC.

E[u^T_a] =

T−1

X

t=0

E[z^t_a]

Shivaram Kalyanakrishnan (2018) UCB Regret 5 / 9

5/9

Step 2: Split sub-optimal pulls into two regimes.

To proveE[u^Ta] =O 1

∆²_alog(T)

, we showE[u^Ta]≤¯u^Ta+Cfor some constantC.

E[u^T_a] =

T−1

X

t=0

E[z^t_a]

=

T−1

X

t=0

P{Z_a^t}

5/9

To proveE[u^Ta] =O 1

∆²_alog(T)

, we showE[u^Ta]≤¯u^Ta+Cfor some constantC.

E[u^T_a] =

T−1

X

t=0

E[z^t_a]

=

T−1

X

t=0

P{Z_a^t}

=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}+

T−1

X

t=0

P{Za^t and(u^ta≥¯u^Ta)}

Shivaram Kalyanakrishnan (2018) UCB Regret 5 / 9

5/9

Step 2: Split sub-optimal pulls into two regimes.

To proveE[u^Ta] =O 1

∆²_alog(T)

, we showE[u^Ta]≤¯u^Ta+Cfor some constantC.

E[u^T_a] =

T−1

X

t=0

E[z^t_a]

=

T−1

X

t=0

P{Z_a^t}

=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}+

T−1

X

t=0

P{Za^t and(u^ta≥¯u^Ta)}

=A+B.

5/9

To proveE[u^Ta] =O 1

∆²_alog(T)

, we showE[u^Ta]≤¯u^Ta+Cfor some constantC.

E[u^T_a] =

T−1

X

t=0

E[z^t_a]

=

T−1

X

t=0

P{Z_a^t}

=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}+

T−1

X

t=0

P{Za^t and(u^ta≥¯u^Ta)}

=A+B.

We showAis upper-bounded by¯u^T_a andBis upper-bounded by a constant.

Shivaram Kalyanakrishnan (2018) UCB Regret 5 / 9

6/9

Step 3: Bounding A.

6/9

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

Shivaram Kalyanakrishnan (2018) UCB Regret 6 / 9

6/9

Step 3: Bounding A.

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

=

T−1

X

t=0

¯u^T_a−1

X

m=0

P{Za^tand(u^ta=m)}

6/9

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

=

T−1

X

t=0

¯u^T_a−1

X

m=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0 T−1

X

t=0

P{Za^tand(u^ta=m)}

Shivaram Kalyanakrishnan (2018) UCB Regret 6 / 9

6/9

Step 3: Bounding A.

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

=

T−1

X

t=0

¯u^T_a−1

X

m=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0 T−1

X

t=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0

P{(Za⁰and(u⁰a=m))or(Za¹and(u¹a=m))or. . . or(Za^T−1and(u^T−1a =m))}

6/9

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

=

T−1

X

t=0

¯u^T_a−1

X

m=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0 T−1

X

t=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0

P{(Za⁰and(u⁰a=m))or(Za¹and(u¹a=m))or. . . or(Za^T−1and(u^T−1a =m))}

≤

¯ u^T_a−1

X

m=0

1

Shivaram Kalyanakrishnan (2018) UCB Regret 6 / 9

6/9

Step 3: Bounding A.

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

=

T−1

X

t=0

¯u^T_a−1

X

m=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0 T−1

X

t=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0

P{(Za⁰and(u⁰a=m))or(Za¹and(u¹a=m))or. . . or(Za^T−1and(u^T−1a =m))}

≤

¯ u^T_a−1

X

m=0

1

= ¯u^T_a.

6/9

A=

T−1

X

t=0

P{Za^t and(u^ta<¯u^Ta)}

=

T−1

X

t=0

¯u^T_a−1

X

m=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0 T−1

X

t=0

P{Za^tand(u^ta=m)}

=

¯ u^T_a−1

X

m=0

P{(Za⁰and(u⁰a=m))or(Za¹and(u¹a=m))or. . . or(Za^T−1and(u^T−1a =m))}

≤

¯ u^T_a−1

X

m=0

1

= ¯u^T_a.

We have used the fact that for 0≤i<j≤t−1,(Z_aⁱ and(uⁱ_a=m))and (Z_a^j and(u^j_a=m))are mutually exclusive.

Shivaram Kalyanakrishnan (2018) UCB Regret 6 / 9

7/9

Step 4.1: Bounding B.

7/9

B=

T−1

X

t=0

P{Z_a^t and(u^t_a ≥¯u^T_a)}

Shivaram Kalyanakrishnan (2018) UCB Regret 7 / 9

7/9

Step 4.1: Bounding B.

B=

T−1

X

t=0

P{Z_a^t and(u^t_a ≥¯u^T_a)}

≤

T−1

X

t=0

P (

ˆ p^ta+

r2 u^ta

ln(t)≥ˆp^t_⋆+ r2

u^t_⋆ln(t)

!

and(u^ta≥¯u^Ta) )

7/9

B=

T−1

X

t=0

P{Z_a^t and(u^t_a ≥¯u^T_a)}

≤

T−1

X

t=0

P (

ˆ p^ta+

r2 u^ta

ln(t)≥ˆp^t_⋆+ r2

u^t_⋆ln(t)

!

and(u^ta≥¯u^Ta) )

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P (

ˆ pa(x) +

r2

xln(t)≥ˆp_⋆(y) + r2

yln(t) )

where

ˆ

pa(x)is the empirical mean of the firstxpulls of arma, and ˆ

p_⋆(y)is the empirical mean of the firstypulls of arm⋆.

Shivaram Kalyanakrishnan (2018) UCB Regret 7 / 9

8/9

Step 4.2: Bounding B.

Fixx∈ {¯u^Ta,¯u^Ta+1, . . . ,t}andy∈ {1,2, . . . ,t}.

8/9

We have:

ˆpa(x) + r2

xln(t)≥ˆp_⋆(y) + r2

yln(t)

=⇒ ˆpa(x) + r2

xln(t)≥p_⋆

! or

ˆ p_⋆(y) +

r2

yln(t)<p_⋆

.

Shivaram Kalyanakrishnan (2018) UCB Regret 8 / 9

8/9

Step 4.2: Bounding B.

Fixx∈ {¯u^Ta,¯u^Ta+1, . . . ,t}andy∈ {1,2, . . . ,t}.

We have:

ˆpa(x) + r2

xln(t)≥ˆp_⋆(y) + r2

yln(t)

=⇒ ˆpa(x) + r2

xln(t)≥p_⋆

! or

ˆ p_⋆(y) +

r2

yln(t)<p_⋆

.

Sincex≥¯u^Ta, we have q2

xln(t)≤q

2

¯u^T_a ln(t)≤^∆₂^a, and so ˆpa(x) +

r2

xln(t)≥p_⋆ =⇒ ˆpa(x)≥pa+∆a

2 .

8/9

We have:

ˆpa(x) + r2

xln(t)≥ˆp_⋆(y) + r2

yln(t)

=⇒ ˆpa(x) + r2

xln(t)≥p_⋆

! or

ˆ p_⋆(y) +

r2

yln(t)<p_⋆

.

Sincex≥¯u^Ta, we have q2

xln(t)≤q

2

¯u^T_a ln(t)≤^∆₂^a, and so ˆpa(x) +

r2

xln(t)≥p_⋆ =⇒ ˆpa(x)≥pa+∆a

2 .

In summary:

ˆ pa(x)+

r2

xln(t)≥ˆp_⋆(y)+

s 2

yln(t) =⇒

ˆ

pa(x)≥pa+∆a

2

or ˆp_⋆(y)<p_⋆− s

2 yln(t)

! .

Shivaram Kalyanakrishnan (2018) UCB Regret 8 / 9

9/9

Step 4.3: Bounding B.

Continuing from Step 4.1, and now invoking Hoeffding’s Inequality:

B≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P (

ˆ pa(x) +

r2

xln(t)≥ˆp_⋆(y) + r2

yln(t) )

9/9

Continuing from Step 4.1, and now invoking Hoeffding’s Inequality:

B≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P (

ˆ pa(x) +

r2

xln(t)≥ˆp_⋆(y) + r2

yln(t) )

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P

ˆ

pa(x)≥pa+∆a

2

+P

ˆ

p_⋆(y)<p_⋆− r2

yln(t)

Shivaram Kalyanakrishnan (2018) UCB Regret 9 / 9

9/9

Step 4.3: Bounding B.

Continuing from Step 4.1, and now invoking Hoeffding’s Inequality:

B≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P (

ˆ pa(x) +

r2

xln(t)≥ˆp_⋆(y) + r2

yln(t) )

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P

ˆ

pa(x)≥pa+∆a

2

+P

ˆ

p_⋆(y)<p_⋆− r2

yln(t)

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

e^−2x(^∆a₂ )²+e^−2y

q2 yln(t)2

9/9

Continuing from Step 4.1, and now invoking Hoeffding’s Inequality:

B≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P (

ˆ pa(x) +

r2

xln(t)≥ˆp_⋆(y) + r2

yln(t) )

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P

ˆ

pa(x)≥pa+∆a

2

+P

ˆ

p_⋆(y)<p_⋆− r2

yln(t)

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

e^−2x(^∆a₂ )²+e^−2y

q2 yln(t)2

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

e^{−4 ln(t)}+e^{−4 ln(t)}

≤

T−1

X

t=0

t² 2

t⁴

≤

∞

X

t=0

2 t² =π²

3.

Shivaram Kalyanakrishnan (2018) UCB Regret 9 / 9

9/9

Step 4.3: Bounding B.

Continuing from Step 4.1, and now invoking Hoeffding’s Inequality:

B≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P (

ˆ pa(x) +

r2

xln(t)≥ˆp_⋆(y) + r2

yln(t) )

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

P

ˆ

pa(x)≥pa+∆a

2

+P

ˆ

p_⋆(y)<p_⋆− r2

yln(t)

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

e^−2x(^∆a₂ )²+e^−2y

q2 yln(t)2

≤

T−1

X

t=0 t

X

x=¯u^T_a t

X

y=1

e^{−4 ln(t)}+e^{−4 ln(t)}

≤

T−1

X

t=0

t² 2

t⁴

≤

∞

X

t=0

2 t² =π²

3.

We are done.