Bandits with Side Observations: Bounded vs. Logarithmic Regret
We consider the classical stochastic multi-armed bandit but where, from time to time and roughly with frequency $\epsilon$, an extra observation is gathered by the agent for free. We prove that, no matter how small $\epsilon$ is the agent can ensure a regret uniformly bounded in time. More precisely, we construct an algorithm with a regret smaller than $\sum_i \frac{\log(1/\epsilon)}{\Delta_i}$, up to multiplicative constant and loglog terms. We also prove a matching lower-bound, stating that no reasonable algorithm can outperform this quantity.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits
The stochastic multi-arm bandit problem has been extensively studied under standard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many…
Decision MakingFrom Optimality to Robustness: Adaptive Re-Sampling Strategies in Stochastic Bandits
The stochastic multi-arm bandit problem has been extensively studied under standard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many…
Decision MakingBandits with Delayed, Aggregated Anonymous Feedback
We study a variant of the stochastic $K$-armed bandit problem, which we call "bandits with delayed, aggregated anonymous feedback". In this problem, when the player pulls an arm, a reward is generated, however it is not …
Lipschitz Bandits with Stochastic Delayed Feedback
The Lipschitz bandit problem extends stochastic bandits to a continuous action set defined over a metric space, where the expected reward function satisfies a Lipschitz condition. In this work, we introduce a new problem…
Bounded Regret for Finitely Parameterized Multi-Armed Bandits
We consider the problem of finitely parameterized multi-armed bandits where the model of the underlying stochastic environment can be characterized based on a common unknown parameter. The true parameter is unknown to th…
Multi-Armed Bandits