Bandit Algorithms

26.9 Exercises 299

(e)f(x) =|x|onR.

(f)f(x) = max{|x|,x^2 }onR.

26.4Prove Theorem 26.3.

26.5Prove Corollary 26.7.

26.6Prove Proposition 26.13.

26.7 Letfbe the convex function given in Example 26.9.

(a) Forx,y∈dom(f) findDf(x,y).
(b) Computef∗(u) and∇f∗(u).
(c) Find dom(∇f∗).
(d) Show that foru,v∈(−∞,0]d,

Df∗(u,v) =−

∑d

i=1

(ui−vi)^2

uiv^2 i

.

(e) Verify the claims in Theorem 26.6.

26.8 Let f : Rd → R ̄ be the unnormalized negentropy function from

Example 26.10. We have seen in Example 26.5 thatDf(x,y) =

∑

i(xilog(xi/yi) +

yi−xi).

(a) Computef∗(u) and∇f∗(u).
(b) Find dom(∇f∗).
(c) Show that foru,v∈Rd,

Df∗(u,v) =

∑d

i=1

exp(vi)(vi−ui) + exp(ui)−exp(vi).

(d) Verify the claims in Theorem 26.6.

26.9Letfbe Legendre. Show thatf ̃given byf ̃(x) =f(x) +〈x,u〉is also

Legendre for anyu∈Rd.

26.10 Letfbe the unnormalized negentropy function from Example 26.5.

(a) Prove thatfis Legendre.
(b) Giveny∈[0,∞)d, prove that argminx∈Pd− 1 Df(x,y) =y/‖y‖ 1.

26.11 Letα∈[0, 1 /d] andA=Pd− 1 ∩[α,1]dandfbe the unnormalized

negentropy function. Lety∈[0,∞)dandx=argminx∈ADf(x,y) and assume

thaty 1 ≤y 2 ≤···≤yd. Letmbe the smallest value such that

ym(1−(m−1)α)≥α

∑d

j=m

yj.