Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Technical Reports

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» People
» Worldwide sites
» Downloads
Content starts here

  Click here for full text: PDF

On Sequential Strategies for Loss Functions with Memory

Merhav, Neri; Ordentlich, Erik; Seroussi, Gadiel; Weinberger, Marcelo J.



Abstract: The problem of optimal sequential decision for individual sequences, relative to a class of competing off-line reference strategies, is studied for general loss functions with memory. This problem is motivated by applications in which actions may have "longterm" effects, or there is a cost for switching from one action to another. As a first step, we consider the case in which the reference strategies are taken from a finite set of generic "experts". We then focus on finite-state reference strategies, assuming finite action and observation spaces. We show that key properties that hold for finite-state strategies in the context of memoryless loss functions, do not carry over to the case of loss functions with memory. As a result, an infinite family of randomized finite-state strategies is seen to be the most appropriate reference class for this case, and the problem is basically different from its memoryless counterpart. Based on Vovk's exponential weighting technique, infinite-horizon on-line decision schemes are devised. For an arbitrary sequence of observations of length n, the excess normalized loss of these schemes relative to the best expert in a corresponding reference class is shown to be upper-bounded by an 0 (n-1/3) term in the case of a finite class, or an 0 ([1n n)/n]1/3) term for the class of randomized finite-state strategies. These results parallel the 0 (n-1/2) bounds attained by previous schemes for memoryless loss functions. By letting the number of states in the reference class grow, the notion of finite-state predictability is also extended. Notes: Please note. This abstract contains formulae which cannot be represented here.

28 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.