Bounded Regret for Finite-Armed Structured Bandits
We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory
In this paper, we propose a constant word (RAM model) algorithm for regret minimisation for both finite and infinite Stochastic Multi-Armed Bandit (MAB) instances. Most of the existing regret minimisation algorithms need…
Multi-Armed BanditsBounded Regret for Finitely Parameterized Multi-Armed Bandits
We consider the problem of finitely parameterized multi-armed bandits where the model of the underlying stochastic environment can be characterized based on a common unknown parameter. The true parameter is unknown to th…
Multi-Armed BanditsA Novel Confidence-Based Algorithm for Structured Bandits
We study finite-armed stochastic bandits where the rewards of each arm might be correlated to those of other arms. We introduce a novel phased algorithm that exploits the given structure to build confidence sets over the…
Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards
We study stochastic linear bandits with heavy-tailed rewards, where the rewards have a finite $(1+\epsilon)$-absolute central moment bounded by $\upsilon$ for some $\epsilon \in (0,1]$. We improve both upper and lower bo…
Experimental DesignMulti-Armed BanditsOptimally Confident UCB: Improved Regret for Finite-Armed Bandits
I present the first algorithm for stochastic finite-armed bandits that simultaneously enjoys order-optimal problem-dependent regret and worst-case regret. Besides the theoretical results, the new algorithm is simple, eff…