On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs
This paper discusses how to efficiently choose from $n$ unknowndistributions the $k$ ones whose means are the greatest by a certainmetric, up to a small relative error. We study the topic under twostandard settings---multi-armed bandits and hidden bipartitegraphs---which differ in the nature of the input distributions. In theformer setting, each distribution can be sampled (in the i.i.d.manner) an arbitrary number of times, whereas in the latter, eachdistribution is defined on a population of a finite size $m$ (andhence, is fully revealed after $m$ samples). For both settings, weprove lower bounds on the total number of samples needed, and proposeoptimal algorithms whose sample complexities match those lower bounds.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms …
Multi-Armed BanditsObservation-Augmented Contextual Multi-Armed Bandits for Robotic Search and Exploration
We introduce a new variant of contextual multi-armed bandits (CMABs) called observation-augmented CMABs (OA-CMABs) wherein a robot uses extra outcome observations from an external information source, e.g. humans. In OA-C…
Bayesian InferenceDecision MakingDecision Making Under UncertaintyMulti-Armed BanditsRisk averse non-stationary multi-armed bandits
This paper tackles the risk averse multi-armed bandits problem when incurred losses are non-stationary. The conditional value-at-risk (CVaR) is used as the objective function. Two estimation methods are proposed for this…
Multi-Armed BanditsAutonomous Drug Design with Multi-Armed Bandits
Recent developments in artificial intelligence and automation support a new drug design paradigm: autonomous drug design. Under this paradigm, generative models can provide suggestions on thousands of molecules with spec…
Drug DesignMulti-Armed BanditsDiversity-Driven Selection of Exploration Strategies in Multi-Armed Bandits
We consider a scenario where an agent has multiple available strategies to explore an unknown environment. For each new interaction with the environment, the agent must select which exploration strategy to use. We provid…
DiversityMulti-Armed Bandits