21.3 Bibliographic remarks 255
whereak=argmaxa∈A‖a‖^2 V(πk)− 1 and the stepsize is chosen to optimizef
along the line connectingπkandδak.
γk= argmaxγ∈[0,1]f((1−γ)πk+γδak) =
1
d‖ak‖
2
V(πk)−^1 −^1
‖a‖^2 V(πk)− 1 − 1
. (21.8)
Ifπ 0 is chosen to be the uniform distribution overA, then the number of
iterations beforeg(πk)≤εis at mostO(dlog log|A|+d/ε). For a slightly more
sophisticated choice of initialization the dependence on|A|can be eliminated
entirely. More importantly, this other initialization has a core set of sizeO(n),
which means that running the algorithm in Eq. (21.7) for justO(dlog logd)
iterations produces a design withg(π)≤ 2 dand a core set ofO(dlog logd).
4 If the action set is infinite, then approximately optimal designs can sometimes
still be found efficiently. Unfortunately the algorithms in the infinite case tend
to be much ‘heavier’ and less practical.
5 The smallest ellipsoid containing some setK ⊂Rdis called theminimum
volume enclosing ellipsoid(MVEE) ofK. As remarked, theD-optimal
design problem is equivalent to finding a MVEE ofAwith the added constraint
that the ellipsoid must be centered. Or equivalently, finding the MVEE of the
symmetrized setA∪{−a:a∈A}. The MVEE of a convex set is also called
John’s ellipsoid, which has many applications in optimization and beyond.
21.3 Bibliographic remarks
The Kiefer–Wolfowitz theorem is due to Kiefer and Wolfowitz [1960]. The
algorithm in Note 3 is due to Fedorov [1972]. A similar variant was also proposed
by Wynn [1970] and the name Wynn’s method is sometimes used. The algorithm
is a specialization of Frank–Wolfe’s algorithm, which was originally intended for
quadratic programming [Frank and Wolfe, 1956]. Todd [2016] wrote a nice book
about minimum volume ellipsoids and related algorithms where you can also find
many more references and improvements to the basic algorithms. Chapter 3 of his
book also includes discussion of alternative initializations and convergence rates
for various algorithms. The duality betweenD-optimal design and the MVEE
problem was shown by Silvey and Sibson [1972]. Although the connection between
minimum volume ellipsoids and experimental design is well known, previous
applications of these results to bandits used John’s theorem without appropriate
symmetrization, which made the resulting arguments more cumbersome. For
more details on finding approximately optimal designs for infinite sets see the
article by Hazan et al. [2016], references there-in and the book by Gr ̈otschel et al.
[2012].
