Title :
Universal Randomized Switching
Author :
Kozat, Suleyman S. ; Singer, Andrew C.
Author_Institution :
Electr. & Electron. Eng. Dept., Koc Univ., Istanbul, Turkey
fDate :
3/1/2010 12:00:00 AM
Abstract :
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 process a 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.
Keywords :
decision theory; randomised algorithms; signal processing; noncausal algorithm; randomized sequential algorithm; sequential decision problems; signal processing application; universal randomized switching; Prediction; quantization; randomized; sequential decisions; switching; universal;
Journal_Title :
Signal Processing, IEEE Transactions on
DOI :
10.1109/TSP.2009.2037062