Bandit Algorithms

37.10 Exercises 474

apples cannot be sold. Good apples yield a unit reward when sold, while the sale

of a bad apple costs the companyc >0.

(a)Formulate this problem as a partial monitoring problem: DetermineLand Φ.
(b) What is the minimax regret in this problem?
(c)What do you think about this problem? Will actual farmers be excited about
your analysis?

37.4(Two-action partial monitoring games are trivial, hopeless or

easy) LetG= (L,Φ) be a partial monitoring game withk= 2 actions. Prove

thatGis either trivial, hopeless or easy.

37.5(Complete lower bound for hard games) Complete the last step in

the proof of Theorem 37.10.

37.6(Lower bound for easy games) Prove Theorem 37.12.

37.7(Lower bound for hopeless games) Prove Theorem 37.11.

37.8(Existence of stationary distribution) Prove Lemma 37.13.

Hint You should first solve the first four parts of Exercise 38.7 in the next

chapter.

37.9 Prove Lemma 37.14.

37.10 Prove the last two inequalities shown in Eq. (37.19). In particular, let

j∈Aand show that:

(a) For anyb∈[k] such thatb=j,P ̃tj/Ptb≤ 4 k;
(b) For anya∈Nj∩A,b∈Najsuch thatb 6 =j,QtjaP ̃tj/Ptb≤ 4 k;
(c)The setsS={b∈[k] :b=j}and the setsSa={b∈[k] :b∈Naj,b 6 =j}
wherea∈Nj∩Aare all disjoint. Hence,
∑

b:`b=`k

1 +

∑

a∈Nk∩A

∑

b∈Nak:`b 6 =`k

1 ≤K.

(d) Put things together and show that the bound of Eq. (37.19) indeed holds.

37.11(Upper bound for hard games) Complete the details to prove
Theorem 37.21.

37.12 Suppose thataandbare globally observable and letv: [k]×[F]→Rbe

a function satisfying Eq. (37.3).

(a)Show that ifa,bare pairwise observable, thenvcan be chosen so that
‖v‖∞≤1 +F.
(b)Next letF= 2 and construct a game and pair of actionsa,b(not pairwise
observable) such that for allvsatisfying Eq. (37.3),‖v‖∞≥ckfor constant
c >1.