Routine Bandits: Minimizing Regret on Recurring Problems
Lists
Only you see this
Abstract
We study a variant of the multi-armed bandit problem in which a learner faces every day one of $$\mathcal {B}$$ many bandit instances, and call it a routine bandit. More specifically, at each period , the same bandit $$b^h_\star $$ is considered during $$T > 1$$ consecutive time steps, but the identity $$b^h_\star $$ is unknown to the learner. We assume all rewards distribution are Gaussian standard. Such a situation typically occurs in recommender systems when a learner may repeatedly serve the same user whose identity is unknown due to privacy issues. By combining bandit-identification tests with a KLUCB type strategy, we introduce the KLUCB for Routine Bandits (KLUCB-RB) algorithm. While independently running KLUCB algorithm at each period leads to a cumulative expected regret of $$\varOmega (H \log T)$$ after H many periods when $$T \rightarrow \infty $$ , KLUCB-RB benefits from previous periods by aggregating observations from similar identified bandits, which yields a non-trivial scaling of $$\varOmega (\log T)$$ . This is achieved without knowing which bandit instance is being faced by KLUCB-RB on this period, nor knowing a priori the number of possible bandit instances. We provide numerical illustration that confirm the benefit of KLUCB-RB while using less information about the problem compared with existing strategies for similar problems.
BibTeX
@inproceedings{saber2021routine,
author = {Hassan Saber and Léo Saci and Odalric-Ambrym Maillard and Audrey Durand},
title = {{Routine Bandits: Minimizing Regret on Recurring Problems}},
booktitle = {ECML/PKDD},
year = {2021},
url = {https://openreview.net/forum?id=W2dclLld1n},
}Loading related content...