A General Framework of Multi-Armed Bandit Processes by Arm Switch Restrictions
This paper proposes a general framework of multi-armed bandit (MAB) processes by introducing a type of restrictions on the switches among arms evolving in continuous time. The Gittins index process is constructed for any single arm subject to the restrictions on switches and then the optimality of the corresponding Gittins index rule is established. The Gittins indices defined in this paper are consistent with the ones for MAB processes in continuous time, integer time, semi-Markovian setting as well as general discrete time setting, so that the new theory covers the classical models as special cases and also applies to many other situations that have not yet been touched in the literature. While the proof of the optimality of Gittins index policies benefits from ideas in the existing theory of MAB processes in continuous time, new techniques are introduced which drastically simplify the proof.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon ta…
Multi-Armed Banditsreinforcement-learningReinforcement LearningReinforcement Learning (RL)Discrepancy-Based Algorithms for Non-Stationary Rested Bandits
We study the multi-armed bandit problem where the rewards are realizations of general non-stationary stochastic processes, a setting that generalizes many existing lines of work and analyses. In particular, we present a …
On Kernelized Multi-Armed Bandits with Constraints
We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hil…
Multi-Armed BanditsThompson SamplingCorrelated Multi-armed Bandits with a Latent Random Source
We consider a novel multi-armed bandit framework where the rewards obtained by pulling the arms are functions of a common latent random variable. The correlation between arms due to the common random source can be used t…
Multi-Armed BanditsThe Blinded Bandit: Learning with Adaptive Feedback
We study an online learning setting where the player is temporarily deprived of feedback each time it switches to a different action. Such model of \emph{adaptive feedback} naturally occurs in scenarios where the environ…