In “Regret Bounds for Sleeping Experts and Bandits”  Kleinberg, Niculescu-Mizil, and Sharma (2008) propose an algorithm for selecting among a list of experts some of whom may be sleeping.  At each time step $t$, the algorithm ranks the experts in order of preference with a permutation vector $\sigma(t)$.   The first analyzed algorithm is Follow The Awake Leader (FTAL) for the case where all of the expert predictions and rewards are observed.  Next they explore a natural extension of upper confidence bound algorithm for the multi-armed bandit setting.  In the adversarial setting, they prove that the regret is at least $O(\sqrt{t\, K \log K})$ for $K$ bandits at time $t$.

Related Posts via Categories

• Link/Book(pdf): “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems”
• Link: AlphaGo Wins against one of the best Go Players on the Planet
• Ted Dunning on Bandits
• “Stochastic Superoptimization” and “Programming by Optimization”
• “Generalized Thompson sampling for sequential decision-making and causal inference”
• “Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained”
• “An Empirical Evaluation of Thompson Sampling”
• “Linear Bandits in High Dimension and Recommendation Systems”
• “A Survey of Monte Carlo Tree Search Methods”
• Schwarzenegger Bandit Success Formula