Bandit Algorithms

28.7 Exercises 327

28.14(Minimax theorem) In this exercise you will prove simplifications of

Sion’s minimax theorem.

(a)Use the tools from online linear optimization to prove Sion’s minimax theorem
whenX=Pk− 1 andY=Pj− 1 andf(x,y) =x>Gyfor someG∈Rk×j.
(b)Generalize your result to the case whenXandYare compact subsets ofRd
andf:X×Y→Ris convex/concave and has bounded gradients.

Hint Consider a repeated simultaneous game where the first player chooses
(xt)∞t=1and the second player chooses (yt)∞t=1. The loss in roundtto the first
player isf(xt,yt) and the loss to the second player is−f(xt,yt). See what happens
to the average iteratesx ̄n=n^1

∑n

t=1xtandy ̄n=

1

n

∑n

t=1ytwhen (xt) and (yt)

are chosen by regret minimizing algorithms. For the second part notice that for

convex functionsg:X→Rit holds thatg(x)−g(x′)≤〈x−x′,∇g(x)〉.

28.15(Counterexample to Sion without compactness) Find examples

ofX,Yandfsatisfy the conditions of Sion’s theorem except that neitherXnor

Yare compact and where the statement does not hold.