Computer Science – Data Structures and Algorithms
Scientific paper
2010-08-22
Computer Science
Data Structures and Algorithms
Scientific paper
Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say `predict 0' or `predict 1', and our payoff is $+1$ if the prediction is correct and $-1$ otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far. In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting $0$ or always predicting $1$. This can be formulated as the experts problem in which we require exponentially small regret with respect to one special expert (which corresponds to the `no prediction' strategy in our setting). It was shown by Even-Dar et al. (COLT'07) that constant expected loss can be achieved. In this paper we give an algorithm that has small regret and exponentially small loss (in expectation), achieving the optimal tradeoff between the two. For a sequence of length $T$ our algorithm has an amortized per time step regret $\epsilon $ and loss $e^{-\epsilon^2 T+1}/\sqrt{T}$ in expectation for all strings. The algorithm extends to the general expert setting, yielding essentially zero loss with respect to the special expert and optimal loss/regret tradeoff. We show that the strong loss bounds of the algorithm have some surprising consequences. First, we obtain a parameter free algorithm for the experts problem that has optimal {\em adaptive regret} bounds, i.e. bounds with respect to the optimum that is allowed to change arms multiple times. Moreover, for {\em any window of size $n$} the regret of our algorithm to any expert never exceeds $O(\sqrt{n(\log N+\log T)})$, where $N$ is the number of experts and $T$ is the time horizon.
Kapralov Michael
Panigrahy Rina
No associations
LandOfFree
Prediction without loss in multi-armed bandit problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Prediction without loss in multi-armed bandit problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prediction without loss in multi-armed bandit problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165698