Online Linear Optimization with Many Hints Ashok Cutkosky Department of Computer Science Dept. of Electrical and Computer Engineering University of Utah Boston University Salt Lake City, UT

We study an online linear optimization (OLO) problem in which the learner is provided access to K "hint" vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic regret whenever there exists a convex combination of the K hints that has positive correlation with the cost vectors. This significantly extends prior work that considered only the case K =1. To accomplish this, we develop a way to combine many arbitrary OLO algorithms to obtain regret only a logarithmically worse factor than the minimum regret of the original algorithms in hindsight; this result is of independent interest.