Titre :

Pure Exploration in Bandits with Linear Constraints

Auteur(s) :

Carlsson, Emil [Auteur]
Chalmers University of Technology [Gothenburg, Sweden]
Basu, Debabrota [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Scool [Scool]
Johansson, Fredrik D. [Auteur]
Chalmers University of Technology [Gothenburg, Sweden]
Dubhashi, Devdatt [Auteur]
Chalmers University of Technology [Gothenburg, Sweden]

Titre de la manifestation scientifique :

International Conference on Artificial Intelligence and Statistics

Ville :

Valencia (Espagne)

Pays :

Espagne

Date de début de la manifestation scientifique :

2024-05

Titre de l’ouvrage :

Proceedings of Machine Learning Research (PMLR)

Titre de la revue :

Proceedings of Machine Learning Research (PMLR)

Date de publication :

2024-05

Discipline(s) HAL :

Informatique [cs]/Apprentissage [cs.LG]
Informatique [cs]/Intelligence artificielle [cs.AI]
Informatique [cs]/Théorie de l'information [cs.IT]
Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

We address the problem of identifying the optimal policy with a fixed confidence level in a multi-armed bandit setup, when the arms are subject to linear constraints. Unlike the standard best-arm identification problem ...
Lire la suite >We address the problem of identifying the optimal policy with a fixed confidence level in a multi-armed bandit setup, when the arms are subject to linear constraints. Unlike the standard best-arm identification problem which is well studied, the optimal policy in this case may not be deterministic and could mix between several arms. This changes the geometry of the problem which we characterize via an information-theoretic lower bound. We introduce two asymptotically optimal algorithms for this setting, one based on the Track-and-Stop method and the other based on a game-theoretic approach. Both these algorithms try to track an optimal allocation based on the lower bound and computed by a weighted projection onto the boundary of a normal cone. Finally, we provide empirical results that validate our bounds and visualize how constraints change the hardness of the problem.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

REPUBLIC: Vers l'IA responsable avec l'apprentissage par renforcement sous contraintes
Causal eXplanations in Reinforcement Learning

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL