|
|
|
|
Optimal amortized regret in every interval
Rina Panigrahy, Preyas Popat
Abstract:
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 exam-
ple if we measure performance with respect to
two constant experts one that always predicts
0â??s and another that always predictsâ?? it is
1â??s
well known that one can get regret O( T ) with
respect to the best expert by using, say, the
weighted majority algorithm [LW89]. But this
algorithm does not provide performance guaran-
tee in any interval. There are other algorithms
(see [BM07, FSSW97, Vov99]) that ensure regret
â??
O( x log T ) in any interval of length x. In this
paper we show a randomized algorithm that in an
â??
amortized sense gets a regret of O( x) for any
interval when the sequence is partitioned into in-
tervals arbitrarily. We empirically estimated the
constant in the O() for T upto 2000 and found it
to be small â?? around 2.1. We also experimentally
evaluate the efficacy of this algorithm in predict-
ing high frequency stock data.
Keywords:
Pages: 663-671
PS Link:
PDF Link: /papers/14/p663-panigrahy.pdf
BibTex:
@INPROCEEDINGS{Panigrahy14,
AUTHOR = "Rina Panigrahy
and Preyas Popat",
TITLE = "Optimal amortized regret in every interval",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "663--671"
}
|
|
