5 papers
Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader
Jongyeong Lee, Junya Honda, Shinji Ito +1
Follow-the-regularized-leader framework has shown effectiveness and flexibility in online learning problems, where the choice of learning rates are known to be crucial. Recently, a…
A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for -Set Semi-Bandit Problem
Botao Chen, Jongyeong Lee, Chansoo Kim +1
This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in -set semi-bandit problems. FTPL has been studied extensively as a promising cand…
Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
Chaiwon Kim, Jongyeong Lee, Min-hwan Oh
We study the decoupled multi-armed bandit problem, where the learner separately selects one arm for exploration and one, possibly different, arm for exploitation at each round. In…
Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems
Jongyeong Lee, Junya Honda, Shinji Ito +1
Follow-the-Regularized-Leader (FTRL) policies have achieved Best-of-Both-Worlds (BOBW) results in various settings through hybrid regularizers, whereas analogous results for Follow…
Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds
Jongyeong Lee, Junya Honda, Shinji Ito +1
This paper studies the optimality of the Follow-the-Perturbed-Leader (FTPL) policy in both adversarial and stochastic -armed bandits. Despite the widespread use of the Follow-th…