Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
The paper considers the problem of global optimization in the setup of stochastic process bandits. We introduce an UCB algorithm which builds a cascade of discretization trees based on generic chaining in order to render possible his operability over a continuous domain. The theoretical framework applies to functions under weak probabilistic smoothness assumptions and also extends significantly the spectrum of application of UCB strategies. Moreover generic regret bounds are derived which are then specialized to Gaussian processes indexed on infinite-dimensional spaces as well as to quadratic forms of Gaussian processes. Lower bounds are also proved in the case of Gaussian processes to assess the optimality of the proposed algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Gaussian Processesglobal-optimizationSimilar Papers 제목 키워드 기반
Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits
Stochastic multi-armed bandits (MABs) provide a fundamental reinforcement learning model to study sequential decision making in uncertain environments. The upper confidence bounds (UCB) algorithm gave birth to the renais…
Decision MakingMulti-Armed BanditsSequential Decision MakingAlgorithms for Infinitely Many-Armed Bandits
We consider multi-armed bandit problems where the number of arms is larger than the possible number of experiments. We make a stochastic assumption on the mean-reward of a new selected arm which characterizes its probabi…
On Lai's Upper Confidence Bound in Multi-Armed Bandits
In this memorial paper, we honor Tze Leung Lai's seminal contributions to the topic of multi-armed bandits, with a specific focus on his pioneering work on the upper confidence bound. We establish sharp non-asymptotic re…
Multi-Armed BanditsUpper Confidence Bounds for Combining Stochastic Bandits
We provide a simple method to combine stochastic bandit algorithms. Our approach is based on a "meta-UCB" procedure that treats each of $N$ individual bandit algorithms as arms in a higher-level $N$-armed bandit problem …
Model SelectionBayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits
Bayesian bandit algorithms with approximate Bayesian inference have been widely used in real-world applications. Despite the superior practical performance, their theoretical justification is less investigated in the lit…
Bayesian InferenceThompson Sampling