Universal Randomized Switching
Süleyman S. Kozat, Andrew C. Singer · IEEE Transactions on Signal Processing · 2009
In this paper, we consider a competitive approach to sequential decision problems, suitable for a variety of signal processing applications where at each of a succession of times, a selection must be made from among a fixed set of strategies (or outcomes). For each such decision and outcome pair, loss is incurred, and it is the time-accumulation of these losses that is sought to be minimized. Rather than using a statistical performance measure, our goal in this pursuit is to sequentially accumulate loss that is no larger than that of the best loss that could be obtained through a partitioning of the sequence of observations into an arbitrary fixed number of segments and independently selecting a different strategy for each segment. For this purpose, we introduce a randomized sequential algorithm built upon that of Kozat and Singer that asymptotically achieves the performance of a noncausal algorithm that would be able to choose the number of segments and the best algorithm for each segment, based on observing the whole observation processa priori. In addition to improving upon the bounds of Kozat and Singer as well as Gyorgy, the results we provide hold for more general loss functions than the square-error loss studied therein.