A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be $Θ\left( \sqrt{T K \log (N/K) } \right)$, where $K$ is the number of arms, $N$ is the number of experts, and $T$ is the time horizon.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Regret Lower Bounds in Multi-agent Multi-armed Bandit
Multi-armed Bandit motivates methods with provable upper bounds on regret and also the counterpart lower bounds have been extensively studied in this context. Recently, Multi-agent Multi-armed Bandit has gained significa…
Query-Reward Tradeoffs in Multi-Armed Bandits
We consider a stochastic multi-armed bandit setting where reward must be actively queried for it to be observed. We provide tight lower and upper problem-dependent guarantees on both the regret and the number of queries.…
Multi-Armed BanditsOn Optimal Robustness to Adversarial Corruption in Online Decision Problems
This paper considers two fundamental sequential decision-making problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus on stochastic regimes in which an adversary may corrupt …
Decision MakingSequential Decision MakingTight Lower Bounds for Combinatorial Multi-Armed Bandits
The Combinatorial Multi-Armed Bandit problem is a sequential decision-making problem in which an agent selects a set of arms on each round, observes feedback for each of these arms and aims to maximize a known reward fun…
Decision MakingMulti-Armed BanditsSequential Decision MakingUnderstanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
We study the stochastic multi-armed bandit problem in the $P$-pass streaming model. In this problem, the $n$ arms are present in a stream and at most $m<n$ arms and their statistics can be stored in the memory. We give a…
Multi-Armed Bandits