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

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.