2022/08/07 by Hakan Gökcesu, Gokcesu, Hakan, Süleyman S. Kozat +1
Computer Science · Decision Sciences · #68Q25 (Secondary) #68Q32 (Primary) 68T05 #Advanced Bandit Algorithms Research #Age of Information Optimization #Auction Theory and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2208.03708
openalex publication_date 2022/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the prediction with expert advice setting, where the aim is to produce a decision by combining the decisions generated by a set of experts, e.g., independently running algorithms. We achieve the min-max optimal dynamic regret under the prediction with expert advice setting, i.e., we can compete against time-varying (not necessarily fixed) combinations of expert decisions in an optimal manner. Our end-algorithm is truly online with no prior information, such as the time horizon or loss ranges, which are commonly used by different algorithms in the literature. Both our regret guarantees and the min-max lower bounds are derived with the general consideration that the expert losses can have time-varying properties and are possibly unbounded. Our algorithm can be adapted for restrictive scenarios regarding both loss feedback and decision making. Our guarantees are universal, i.e., our end-algorithm can provide regret guarantee against any competitor sequence in a min-max optimal manner with logarithmic complexity. Note that, to our knowledge, for the prediction with expert advice problem, our algorithms are the first to produce such universally optimal, adaptive and truly online guarantees with no prior knowledge.