Competing with stationary prediction strategies

This paper belongs to the area of learning theory that has been variously referred to as prediction with expert advice, competitive on-line prediction, p rediction of individual sequences, and universal on-line learning; see [7] for a re view. There are many proof techniques known in this field; this paper is based on K alnishkan and Vyugin's Weak Aggregating Algorithm [16], but it is possible that som e of the numerous other techniques could be used instead. In Section 2 we give the main definitions and state our main results, Th e-orems 1-4; their proofs are given in Sections 3-6. In Section 7 we inf ormally discuss the notion of stationarity, and Section 8 concludes.