Learning the Switching Rate by Discretising Bernoulli Sources Online Phishing Pages

The expert tracking algorithm Fixed-Share depends on a parameter, called the switching rate. The switching rate can be learned online with regret 1 2 log T + O(1) bits. The current fastest method to achieve this 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 bins have to be determined algorithmically, and the final number of outcomes T must be known in advance. 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.