Towards optimal algorithms for prediction with expert advice

DOI10.1137/1.9781611974331.CH39MaRDI QIDQ4575616zbMATH OpenOpenAlexFDO

Authors Yuval Peres, Balasubramanian Sivan, N. V. Gravin

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.3040

Mathematics Subject Classification ID

Inference from stochastic processes and prediction (62M20) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the optimal algorithm, adversary and regret for the case of 3 experts. Further, we show that the optimal algorithm for $2$ and $3$ experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary. Remarkably, our proof shows that the probability matching algorithm is not only optimal against this particular randomized adversary, but also minimax optimal. Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of $4$ experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.

Recommendations

• How to better use expert advice
• A closer look at adaptive regret
• A closer look at adaptive regret
• How to use expert advice
• Tight lower bounds for multiplicative weights algorithmic families

Cited in

(20)

• The best expert versus the smartest algorithm
• On the asymptotic optimality of the comb strategy for prediction with expert advice
• Dynamic games in cyber-physical security: an overview
• Improving and benchmarking of algorithms for decision making with lower previsions
• Prediction with expert advice: a PDE perspective
• Asymptotically optimal strategies for online prediction with history-dependent experts
• On the Prior Sensitivity of Thompson Sampling
• Prediction with Expert Advice under Discounted Loss
• scientific article; zbMATH DE number 7370589 (Why is no real title available?)
• Tight lower bounds for multiplicative weights algorithmic families
• Finite-time 4-expert prediction problem
• Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality
• Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case
• Optimal anytime regret with two experts
• Relaxing the i.i.d. assumption: adaptively minimax optimal regret via root-entropic regularization
• Numerical solution of a PDE arising from prediction with expert advice
• Optimal prediction using expert advice and randomized Littlestone dimension
• Thompson sampling for adversarial bit prediction
• Efficient and optimal fixed-time regret with two experts
• Supermartingales in prediction with expert advice

This page was built for publication: Towards optimal algorithms for prediction with expert advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575616)