Pure Exploration and Regret Minimization in Matching Bandits
Finding an optimal matching in a weighted graph is a standard combinatorial problem. We consider its semi-bandit version where either a pair or a full matching is sampled sequentially. We prove that it is possible to leverage a rank-1 assumption on the adjacency matrix to reduce the sample complexity and the regret of off-the-shelf algorithms up to reaching a linear dependency in the number of vertices (up to poly log terms).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simple Regret Minimization for Contextual Bandits
There are two variants of the classical multi-armed bandit (MAB) problem that have received considerable attention from machine learning researchers in recent years: contextual bandits and simple regret minimization. Con…
Multi-Armed BanditsOnline Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
Motivated by the recency effect in online learning, we study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper. In this setting, we are given $n$ arms with unknown sub-Gaussia…
Multi-Armed BanditsOn the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
We study a stochastic multi-armed bandit problem where an agent is granted a free exploration budget before regret accumulates, a setting not captured by the classic regret minimization or pure exploration paradigms. The…
Multi-Armed BanditsNear-Optimal Collaborative Learning in Bandits
This paper introduces a general multi-agent bandit model in which each agent is facing a finite set of arms and may communicate with other agents through a central controller in order to identify, in pure exploration, or…
Federated LearningExperimental Design for Regret Minimization in Linear Bandits
In this paper we propose a novel experimental design-based algorithm to minimize regret in online stochastic linear and combinatorial bandits. While existing literature tends to focus on optimism-based algorithms--which …
Experimental Design