There are many sequential decision problems which can be appropriately modeled as a repeated game, in which the decision-maker is competing with an adversary. For instance, in the problem of virus detection in a computer network, the aim is to label incoming packets as either clean or infected, while a hacker aims to design infected packets that escape detection. Similar problems arise in other areas of computer security (including spam filtering and detection of denial-of service attacks), in internet search (such as deciding if a highly-linked web page is genuinely authoritative and should have high page rank), and in financial applications (such as portfolio optimization). In these problems, the decision-maker aims to perform almost as well as the best element of some comparison class. Even for decision problems that are not inherently adversarial, it is often appealing to model them in this way, since the assumptions are sufficiently weak that effective learning algorithms for these adversarial settings are very widely applicable. Many of the key algorithmic approaches to online learning problems can be viewed as methods involving regularization, an idea that has its origins in the solution of ill-posed problems, such as statistical estimation problems. This project aims to exploit this regularization viewpoint in the analysis and design of methods for complex online learning problems. In particular, its aims are (1) To develop techniques for decision problems with limited feedback. (2) To develop techniques for decision problems with complex losses that cannot be simply decomposed into a sum across trials. (3) To develop efficient learning algorithms that can simultaneously compete effectively with a variety of rich comparison classes and a variety of constraints on the adversary. (4) To improve our understanding of the relationships between online decision problems (in adversarial settings) and statistical decision problems (in probabilistic settings). Successful research outcomes of this project are likely to increase our understanding of complex sequential decision problems and to provide design methodologies for effective learning algorithms for these problems, and hence have a significant potential for practical impact in many application areas, including computer security and computational finance.
