UNIVERSAL SCHEMES FOR SEQUENTIAL DECISION FROM INDIVIDUAL DATA SEQUENCES

Sequential decision algorithms are investigated, under a family of add itive performance criteria, for individual data sequences, with variou s application areas in information theory and signal processing. Simpl e universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n-1 log n, where n is the sa mple size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSM's), is s tudied. It is shown that Markovian machines with sufficiently long mem ory exist that are asymptotically nearly as good as any given FSM (det erministic or randomized) for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric s chemes is discussed with special attention to the recursive least squa res (RLS) algorithm.