Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is regret (loss in payoff) with respect to a set of experts. For example if we measure performance with respect to two constant experts one that always predicts 0's and another that always predicts 1's it is well known that one can get regret @math with respect to the best expert by using, say, the weighted majority algorithm. But this algorithm does not provide performance guarantee in any interval. There are other algorithms that ensure regret @math in any interval of length @math . In this paper we show a randomized algorithm that in an amortized sense gets a regret of @math for any interval when the sequence is partitioned into intervals arbitrarily. We empirically estimated the constant in the @math for @math upto 2000 and found it to be small -- around 2.1. We also experimentally evaluate the efficacy of this algorithm in predicting high frequency stock data.
@cite_22: We analyze a sequential game between a Gambler and a Casino. The Gambler allocates bets from a limited budget over a fixed menu of gambling events that are offered at equal time intervals, and the Casino chooses a binary loss outcome for each of the events. We derive the optimal min-max strategies for both participants. We then prove that the minimum cumulative loss of the Gambler, assuming optimal play by the Casino, is exactly a well-known combinatorial quantity: the expected number of draws needed to complete a multiple set of “cards” in the generalized Coupon Collector’s Problem. We show that this quantity and the optimal strategy of the Gambler can be efficiently estimated from a simple random walk.
@cite_7: 
@cite_8: We consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for online learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and online learning algorithms. We also prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts.
@cite_6: We study online learnability of a wide class of problems, extending the results of (Rakhlin, Sridharan, Tewari, 2010) to general notions of performance measure well beyond external regret. Our framework simultaneously captures such well-known notions as internal and general Phi-regret, learning with non-additive global cost functions, Blackwell's approachability, calibration of forecasters, adaptive regret, and more. We show that learnability in all these situations is due to control of the same three quantities: a martingale convergence term, a term describing the ability to perform well if future is known, and a generalization of sequential Rademacher complexity, studied in (Rakhlin, Sridharan, Tewari, 2010). Since we directly study complexity of the problem instead of focusing on efficient algorithms, we are able to improve and extend many known results which have been previously derived via an algorithmic construction.
@cite_0: 
@cite_5: 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. For a sequence of length @math our algorithm has regret @math and loss @math in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors. Our techniques extend to the general setting of @math experts, where the related problem of trading off regret to the best expert for regret to the special' expert has been studied by Even- (COLT'07). We obtain essentially zero loss with respect to the special expert and optimal loss regret tradeoff, improving upon the results of Even- and settling the main question left open in their paper. The strong loss bounds of the algorithm have some surprising consequences. A simple iterative application of our algorithm gives essentially optimal regret bounds at multiple time scales, bounds with respect to @math -shifting optima as well as regret bounds with respect to higher norms of the input sequence.
@cite_15: We consider the following problem. At each point of discrete time the learner must make a prediction; he is given the predictions made by a pool of experts. Each prediction and the outcome, which is disclosed after the learner has made his prediction, determine the incurred loss. It is known that, under weak regularity, the learner can ensure that his cumulative loss never exceedscL+alnn, wherecandaare some constants,nis the size of the pool, andLis the cumulative loss incurred by the best expert in the pool. We find the set of those pairs (c, a) for which this is true.
@cite_16: We consider the design of online master algorithms for combining the predictions from a set of experts where the absolute loss of the master is to be close to the absolute loss of the best expert. For the case when the master must produce binary predictions, the Binomial Weighting algorithm is known to be optimal when the number of experts is large. It has remained an open problem how to design master algorithms based on binomial weights when the predictions of the master are allowed to be real valued. In this paper we provide such an algorithm and call it the Binning algorithm because it maintains experts in an array of bins. We show that this algorithm is optimal in a relaxed setting in which we consider experts as continuous quantities. The algorithm is efficient and near-optimal in the standard experts setting.
@cite_13: We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts . Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictins. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We then show how this leads to certain kinds of pattern recognition learning algorithms with performance bounds that improve on the best results currently know in this context. We also compare our analysis to the case in which log loss is used instead of the expected number of mistakes.
@cite_12: We study online regret minimization algorithms in an experts setting. In this setting, the algorithm chooses a distribution over experts at each time step and receives a gain that is a weighted average of the experts' instantaneous gains. We consider a bicriteria setting, examining not only the standard notion of regret to the best expert, but also the regret to the average of all experts, the regret to any given fixed mixture of experts, or the regret to the worst expert. This study leads both to new understanding of the limitations of existing no-regret algorithms, and to new algorithms with novel performance guarantees. More specifically, we show that any algorithm that achieves only @math cumulative regret to the best expert on a sequence of T trials must, in the worst case, suffer regret @math to the average, and that for a wide class of update rules that includes many existing no-regret algorithms (such as Exponential Weights and Follow the Perturbed Leader), the product of the regret to the best and the regret to the average is, in the worst case, ?(T). We then describe and analyze two alternate new algorithms that both achieve cumulative regret only @math to the best expert and have only constant regret to any given fixed distribution over experts (that is, with no dependence on either T or the number of experts N). The key to the first algorithm is the gradual increase in the "aggressiveness" of updates in response to observed divergences in expert performances. The second algorithm is a simple twist on standard exponential-update algorithms.
There is large body on work on regret style analysis for prediction. Numerous works including @cite_7 @cite_13 have examined the optimal amount of regret achievable with respect to two or more experts. A good reference for the results in this area is @cite_0 . It is well known that in the case of static experts, the optimal regret achievable is exactly equal to the Rademacher complexity of the predictions of the experts (chapter 8 in @cite_0 ). Recent works such as @cite_16 @cite_22 @cite_8 have extended this analysis to other settings. Measures other than the standard regret measure have been studied in @cite_6 The question of what can be achieved if one would like to have a significantly better guarantee with respect to a fixed expert or a distribution of experts was asked before in @cite_12 @cite_5 . Tradeoffs between regret and minimum payoff were also examined in @cite_15 , where the author studied the set of values of @math for which an algorithm can have payoff @math , where @math is the payoff of the best arm and @math are constants.