A tree-weighting approach to sequential decision problems with multiplicative loss

Suleyman S. Kozat, Andrew Carl Singer, Andrew J. Bean

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we consider sequential decision problems in which the decision at each time is taken as a convex-combination of observations and whose performance metric is multiplicatively compounded over time. Such sequential decision problems arise in gambling, investing and in a host of signal processing applications from statistical language modeling to mixed-modality multimedia signal processing. Using a competitive algorithm framework, we construct sequential strategies that asymptotically achieve the performance of the best piecewise-convex strategy that could have been chosen by observing the entire sequence of outcomes in advance. Using the notion of context-trees, a mixture approach is able to asymptotically achieve the performance of the best choice of both the partitioning of the space of past observations and convex strategies within each region, for every sequence of outcomes. This performance is achieved with linear complexity in the depth of the context-tree, per decision. For the application of sequential investment, we also investigate transaction costs incurred for each decision. An explicit algorithmic description and examples demonstrating the performance of the algorithms are given. Our methods can be used to sequentially combine probability distributions produced by different statistical language models used in speech recognition or natural language processing and by different modalities in multimedia signal processing.

Original languageEnglish (US)
Pages (from-to)890-905
Number of pages16
JournalSignal Processing
Volume91
Issue number4
DOIs
StatePublished - Apr 1 2011

Keywords

  • Context-tree
  • Convex-combination
  • Investment
  • Piecewise models
  • Portfolio
  • Universal

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A tree-weighting approach to sequential decision problems with multiplicative loss'. Together they form a unique fingerprint.

Cite this