63 citations · 75 across the 16 of their papers we have counts for
18 papers
Best Arm Identification for Bandits with Shifting Means
Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal +2
We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean re…
Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability
Dirk van der Hoeven, Julia Olkhovskaia, Tim van Erven
We consider the fundamental problem of estimating a discrete distribution on a domain of size with high probability in Kullback-Leibler divergence. We provide upper and lower b…
When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
Antoine Moulin, Emmanuel Esposito, Dirk van der Hoeven
We consider the problem setting of prediction with expert advice with possibly heavy-tailed losses, i.e. the only assumption on the losses is an upper bound on their second moments…
Online Newton Method for Bandit Convex Optimisation
Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore +1
We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most $d^{3.5} \sqrt{n} \ma…
High-Probability Risk Bounds via Sequential Predictors
Dirk van der Hoeven, Nikita Zhivotovskiy, Nicolò Cesa-Bianchi
Online learning methods yield sequential regret bounds under minimal assumptions and provide in-expectation risk bounds for statistical learning. However, despite the apparent adva…
Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts
Dirk van der Hoeven, Ciara Pike-Burke, Hao Qiu +1
We investigate online classification with paid stochastic experts. Here, before making their prediction, each expert must be paid. The amount that we pay each expert directly influ…
Delayed Bandits: When Do Intermediate Observations Help?
Emmanuel Esposito, Saeed Masoudian, Hao Qiu +3
We study a -armed bandit with delayed feedback and intermediate observations. We consider a model where intermediate observations have a form of a finite state, which is observe…
A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs
Dirk van der Hoeven, Lukas Zierahn, Tal Lancewicki +2
We derive a new analysis of Follow The Regularized Leader (FTRL) for online learning with delayed bandit feedback. By separating the cost of delayed feedback from that of bandit fe…
Learning on the Edge: Online Learning with Stochastic Feedback Graphs
Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven +1
The framework of feedback graphs is a generalization of sequential decision-making with bandit or full information feedback. In this work, we study an extension where the directed…
A Regret-Variance Trade-Off in Online Learning
Dirk van der Hoeven, Nikita Zhivotovskiy, Nicolò Cesa-Bianchi
We consider prediction with expert advice for strongly convex and bounded losses, and investigate trade-offs between regret and "variance" (i.e., squared difference of learner's pr…
A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Bianchi +1
We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We pres…
Nonstochastic Bandits and Experts with Arm-Dependent Delays
Dirk van der Hoeven, Nicolò Cesa-Bianchi
We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. While the setting in which delays only depend on time has been extensivel…
Beyond Bandit Feedback in Online Multiclass Classification
Dirk van der Hoeven, Federico Fusco, Nicolò Cesa-Bianchi
We study the problem of online multiclass classification in a setting where the learner's feedback is determined by an arbitrary directed graph. While including bandit feedback as…
Distributed Online Learning for Joint Regret with Communication Constraints
Dirk van der Hoeven, Hédi Hadiji, Tim van Erven
We consider distributed online learning for joint regret with communication constraints. In this setting, there are multiple agents that are connected in a graph. Each round, an ad…
MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
Tim van Erven, Wouter M. Koolen, Dirk van der Hoeven
We provide a new adaptive method for online convex optimization, MetaGrad, that is robust to general convex losses but achieves faster rates for a broad class of special functions,…
Comparator-adaptive Convex Bandits
Dirk van der Hoeven, Ashok Cutkosky, Haipeng Luo
We study bandit convex optimization methods that adapt to the norm of the comparator, a topic that has only been studied before for its full-information counterpart. Specifically,…
Exploiting the Surrogate Gap in Online Multiclass Classification
Dirk van der Hoeven
We present Gaptron, a randomized first-order algorithm for online multiclass classification. In the full information setting we show expected mistake bounds with respect to the log…
The Many Faces of Exponential Weights in Online Learning
Dirk van der Hoeven, Tim van Erven, Wojciech Kotłowski
A standard introduction to online learning might place Online Gradient Descent at its center and then proceed to develop generalizations and extensions like Online Mirror Descent a…