Learning the Switching Rate by Discretising Bernoulli Sources Online
Steven de Rooij, Tim van Erven; JMLR W&CP 5:432-439, 2009.
The expert tracking algorithm Fixed-Share depends on a parameter alpha, called the switching rate. If the final number of outcomes T is known in advance, then the switching rate can be learned with regret 1/2 log T + O(1) bits. The current fastest method that achieves this, Learn-alpha, is based on optimal discretisation of the Bernoulli distributions into O(√T) bins and runs in O(T√T) time; however the exact locations of these points have to be determined algorithmically. This paper introduces a new discretisation scheme with the same regret bound for known T, that specifies the number and positions of the discretisation points explicitly. The scheme is especially useful when T is not known in advance: a new fully on-line algorithm, Refine-Online, is presented, which runs in O(T√T log T) time and achieves a regret of 1/2 log 3 log T + O(log log T) bits.