Online Optimization in X-Armed Bandits
We consider a generalization of stochastic bandit problems where the set of arms, X, is allowed to be a generic topological space. We constraint the mean-payoff function with a dissimilarity function over X in a way that is more general than Lipschitz. We construct an arm selection policy whose regret improves upon previous result for a large class of problems. In particular, our results imply that if X is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally Hölder with a known exponent, then the expected regret is bounded up to a logarithmic factor by $n$, i.e., the rate of the growth of the regret is independent of the dimension of the space. Moreover, we prove the minimax optimality of our algorithm for the class of mean-payoff functions we consider.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Productization Challenges of Contextual Multi-Armed Bandits
Contextual Multi-Armed Bandits is a well-known and accepted online optimization algorithm, that is used in many Web experiences to tailor content or presentation to users' traffic. Much has been published on theoretical …
Multi-Armed BanditsStochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
Multi-armed bandit (MAB) problems are widely applied to online optimization tasks that require balancing exploration and exploitation. In practical scenarios, these tasks often involve multiple conflicting objectives, gi…
Multi-Armed BanditsEvolutionary Multi-Armed Bandits with Genetic Thompson Sampling
As two popular schools of machine learning, online learning and evolutionary computations have become two important driving forces behind real-world decision making engines for applications in biomedicine, economics, and…
Decision MakingEvolutionary AlgorithmsMulti-Armed BanditsSequential Decision Making+1Adversarial Attacks on Combinatorial Multi-Armed Bandits
We study reward poisoning attacks on Combinatorial Multi-armed Bandits (CMAB). We first provide a sufficient and necessary condition for the attackability of CMAB, a notion to capture the vulnerability and robustness of …
Multi-Armed BanditsFairness of Exposure in Online Restless Multi-armed Bandits
Restless multi-armed bandits (RMABs) generalize the multi-armed bandits where each arm exhibits Markovian behavior and transitions according to their transition dynamics. Solutions to RMAB exist for both offline and onli…
FairnessMulti-Armed Bandits