Online Linear Optimization with Many Hints
This work addresses the challenge of leveraging multiple hints for improved decision-making in online optimization, representing a significant extension beyond single-hint scenarios.
The paper tackles the online linear optimization problem by providing an algorithm that achieves logarithmic regret when multiple hints are available, extending prior work limited to a single hint. The result includes a method to combine multiple algorithms with only a logarithmic increase in regret compared to the best in hindsight.
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.