Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits
We consider the problem of regret minimization in non-parametric stochastic bandits. When the rewards are known to be bounded from above, there exists asymptotically optimal algorithms, with asymptotic regret depending on an infimum of Kullback-Leibler divergences (KL). These algorithms are computationally expensive and require storing all past rewards, thus simpler but non-optimal algorithms are often used instead. We introduce several methods to approximate the infimum KL which reduce drastically the computational and memory costs of existing optimal algorithms, while keeping their regret guaranties. We apply our findings to design new variants of the MED and IMED algorithms, and demonstrate their interest with extensive numerical simulations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that ev…
Multi-Armed BanditsThompson Sampling is Asymptotically Optimal in General Environments
We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. W…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Thompson SamplingOne-step corrected projected stochastic gradient descent for statistical estimation
A generic, fast and asymptotically efficient method for parametric estimation is described. It is based on the projected stochastic gradient descent on the log-likelihood function corrected by a single step of the Fisher…
Online Identification of Stochastic Continuous-Time Wiener Models Using Sampled Data
It is well known that ignoring the presence of stochastic disturbances in the identification of stochastic Wiener models leads to asymptotically biased estimators. On the other hand, optimal statistical identification, v…
Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality
We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite time. We show that, surprisingly, the n…