Asymptotic Randomised Control with applications to bandits
We consider a general multi-armed bandit problem with correlated (and simple contextual and restless) elements, as a relaxed control problem. By introducing an entropy regularisation, we obtain a smooth asymptotic approximation to the value function. This yields a novel semi-index approximation of the optimal decision process. This semi-index can be interpreted as explicitly balancing an exploration-exploitation trade-off as in the optimistic (UCB) principle where the learning premium explicitly describes asymmetry of information available in the environment and non-linearity in the reward function. Performance of the resulting Asymptotic Randomised Control (ARC) algorithm compares favourably well with other approaches to correlated multi-armed bandits.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Generalised correlated batched bandits via the ARC algorithm with application to dynamic pricing
The Asymptotic Randomised Control (ARC) algorithm provides a rigorous approximation to the optimal strategy for a wide class of Bayesian bandits, while retaining low computational complexity. In particular, the ARC appro…
ARCWhen and why randomised exploration works (in linear bandits)
We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the $d$-dimensional line…
Thompson SamplingNon-asymptotic bounds for sampling algorithms without log-concavity
Discrete time analogues of ergodic stochastic differential equations (SDEs) are one of the most popular and flexible tools for sampling high-dimensional probability measures. Non-asymptotic analysis in the $L^2$ Wasserst…
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notab…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Thompson SamplingEfficient Inference Without Trading-off Regret in Bandits: An Allocation Probability Test for Thompson Sampling
Using bandit algorithms to conduct adaptive randomised experiments can minimise regret, but it poses major challenges for statistical inference (e.g., biased estimators, inflated type-I error and reduced power). Recent a…
Thompson Sampling