11.5 Notes 152
11.5 Notes
1 Exp3 is nearly optimal in the sense that its expected regret cannot be improved
significantly in the worst case. The distribution of its regret, however, is very far
from optimal. Define therandom regretto be the random variable measuring
the actual deficit of the learner relative to the best arm in hindsight:
Rˆn= max
i∈[k]
∑n
t=1
xti−
∑n
t=1
Xt
︸ ︷︷ ︸
in terms of rewards
=
∑n
t=1
Yt−min
i∈[k]
∑n
t=1
yti
︸ ︷︷ ︸
in terms of losses
.
In Exercise 11.5 you will show that for all large enoughnand reasonable
choices ofηthere exists a bandit such that the random regret of Exp3 satisfies
P(Rˆn≥n/4)> 1 /131. In the same exercise you should explain why this does
not contradict the upper bound. That Exp3 has such a high variance is a
serious limitation, which we address in the next chapter.
2 What happens when the range of the rewards is unbounded? This has been
studied by Allenberg et al. [2006], where some (necessarily much weaker)
positive results are presented.
3 In the full information setting the learner observes the whole vector
xt∈[0,1]kat the end of roundt, but the reward is stillxtAt. This setting is
also calledprediction with expert advice. Exponential weighting is still
a good idea, but the estimated rewards can now be replaced by the actual
rewards. The resulting algorithm is sometimes called Hedge or the exponential
weights algorithm. The proof as written goes through in almost the same way,
but one should replace the polynomial upper bound onexp(x) with Hoeffding’s
lemma. This analysis gives a regret of
√
nlog(k)/ 2 , which is optimal in an
asymptotic sense [Cesa-Bianchi and Lugosi, 2006].
4 A more sophisticated algorithm and analysis shaves a factor of
√
log(k)from
the regret upper bound in Theorem 11.2 [Audibert and Bubeck, 2009, 2010a,
Bubeck and Cesa-Bianchi, 2012]. The algorithm is an instantiation of mirror
descent from convex optimization, which we present in Chapter 28. More details
are in Exercise 28.13. Interestingly, this algorithm not only shaves off the extra√
log(k)factor from the regret, also achievesO(log(n))-regret in the stochastic
setting [Zimmert and Seldin, 2018].
5 The initial distribution (the ‘prior’)P 1 does not have to be uniform. By biasing
the prior towards a specific action the regret can be reduced when the favored
action turns out to be optimal. There is a price for this, however, if the optimal
arm is not favored [Lattimore, 2015a].
6 We assumed that the adversary chooses the rewards at the start of the game.
Such adversaries are calledoblivious. An adversary is calledreactiveor
nonobliviousifxtis allowed to depend on the historyx 1 ,A 1 ,...,xt− 1 ,At− 1.
Despite the fact that this is clearly a harder problem the result we obtained
can be generalized to this setting without changing the analysis. It is another
question whether the definition of regret makes sense for reactive environments.
