10 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…
Rate-optimal Design for Anytime Best Arm Identification
Junpei Komiyama, Kyoungseok Jang, Junya Honda
We consider the best arm identification problem, where the goal is to identify the arm with the highest mean reward from a set of arms under a limited sampling budget. This pro…
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…
Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems
Botao Chen, Junya Honda
This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in size-invariant combinatorial semi-bandit problems. Recently, Honda et al. (2023) an…
Optimal Regret of Bernoulli Bandits under Global Differential Privacy
Achraf Azize, Yulian Wu, Junya Honda +3
As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges as a timely question. In this context, regr…
Learning with Posterior Sampling for Revenue Management under Time-varying Demand
Kazuma Shimizu, Junya Honda, Shinji Ito +1
This paper discusses the revenue management (RM) problem to maximize revenue by pricing items or services. One challenge in this problem is that the demand distribution is unknown…
Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds
Shinji Ito, Taira Tsuchiya, Junya Honda
Follow-The-Regularized-Leader (FTRL) is known as an effective and versatile approach in online learning, where appropriate choice of the learning rate is crucial for smaller regret…
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…
Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring
Taira Tsuchiya, Shinji Ito, Junya Honda
Partial monitoring is a generic framework of online decision-making problems with limited feedback. To make decisions from such limited feedback, it is necessary to find an appropr…