Zobrazeno 1 - 10
of 209
pro vyhledávání: '"Degenne, P."'
We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive two lower bounds on the stopping time of any algorithm.
Externí odkaz:
http://arxiv.org/abs/2411.01898
Autor:
Poiani, Riccardo, Degenne, Rémy, Kaufmann, Emilie, Metelli, Alberto Maria, Restelli, Marcello
In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the algorithm can choose to sample an arm
Externí odkaz:
http://arxiv.org/abs/2406.03033
We revisit the identification of an $\varepsilon$-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the literature: the diameter, $D$, and the optimal bias span, $H$, which sat
Externí odkaz:
http://arxiv.org/abs/2405.17108
Autor:
Degenne, Rémy, Mathieu, Timothée
We prove lower bounds on the error of any estimator for the mean of a real probability distribution under the knowledge that the distribution belongs to a given set. We apply these lower bounds both to parametric and nonparametric estimation. In the
Externí odkaz:
http://arxiv.org/abs/2403.01892
We propose EB-TC$\varepsilon$, a novel sampling rule for $\varepsilon$-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC$\varepsilon$ is an *anytime* s
Externí odkaz:
http://arxiv.org/abs/2305.16041
Autor:
Degenne, Rémy
In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. It then answers a query about the set of distributions. A good algorithm will have a small probability of error. Wh
Externí odkaz:
http://arxiv.org/abs/2303.09468
Autor:
Ying, Kexing, Degenne, Rémy
We present the formalization of Doob's martingale convergence theorems in the mathlib library for the Lean theorem prover. These theorems give conditions under which (sub)martingales converge, almost everywhere or in $L^1$. In order to formalize thos
Externí odkaz:
http://arxiv.org/abs/2212.05578
Autor:
Jourdan, Marc, Degenne, Rémy
A Top Two sampling rule for bandit identification is a method which selects the next arm to sample from among two candidate arms, a leader and a challenger. Due to their simplicity and good empirical performance, they have received increased attentio
Externí odkaz:
http://arxiv.org/abs/2210.05431
The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variance
Externí odkaz:
http://arxiv.org/abs/2210.00974
Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models (Russo, 2016), for parametric families of arms. They select the next arm to sample from by randomizing among two candidate arms, a
Externí odkaz:
http://arxiv.org/abs/2206.05979