3.4k citations · 4.9k across the 135 of their papers we have counts for
41 papers · 1 filter
Spectral bandits for smooth graph functions with applications in recommender systems
Tomáš Kocák, Michal Valko, Rémi Munos +2
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this paper, we study a bandit problem where the payoffs of arms are smooth on a graph…
Black-box optimization of noisy functions with unknown smoothness
Jean-Bastien Grill, Michal Valko, Rémi Munos
We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around…
Middle-mile logistics through the lens of goal-conditioned reinforcement learning
Onno Eberhard, Thibaut Cuvelier, Michal Valko +1
Middle-mile logistics describes the problem of routing parcels through a network of hubs linked by trucks with finite capacity. We rephrase this as a multi-object goal-conditioned…
Active multiple matrix completion with adaptive confidence sets
Andrea Locatelli, Alexandra Carpentier, Michal Valko
In this work, we formulate a new multi-task active learning setting in which the learner's goal is to solve multiple matrix completion problems simultaneously. At each round, the l…
Spectral bandits
Tomáš Kocák, Rémi Munos, Branislav Kveton +2
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this work, we study a bandit problem where the payoffs of arms are smooth on a graph.…
Online learning with Erdős-Rényi side-observation graphs
Tomáš Kocák, Gergely Neu, Michal Valko
We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case wher…
Extreme bandits
Alexandra Carpentier, Michal Valko
In many areas of medicine, security, and life sciences, we want to allocate limited resources to different sources in order to detect extreme values. In this paper, we study an eff…
Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
Daniele Calandriello, Alessandro Lazaric, Michal Valko
One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasibl…
Pliable rejection sampling
Akram Erraqabi, Michal Valko, Alexandra Carpentier +1
Rejection sampling is a technique for sampling from difficult distributions. However, its use is limited due to a high rejection rate. Common adaptive rejection sampling methods ei…
A single algorithm for both restless and rested rotting bandits
Julien Seznec, Pierre Ménard, Alessandro Lazaric +1
In many application domains (e.g., recommender systems, intelligent tutoring systems), the rewards associated to the actions tend to decrease over time. This decay is either caused…
Spectral bandits for smooth graph functions
Michal Valko, Rémi Munos, Branislav Kveton +1
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this paper, we study a bandit problem where the payoffs of arms are smooth on a graph…
Adaptive multi-fidelity optimization with fast learning rates
Come Fiegel, Victor Gabillon, Michal Valko
In multi-fidelity optimization, biased approximations of varying costs of the target function are available. This paper studies the problem of optimizing a locally smooth function…
Best of both worlds: Stochastic & adversarial best-arm identification
Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2
We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial sce…
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
Pierre Perrault, Vianney Perchet, Michal Valko
We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits…
Proximal Point Nash Learning from Human Feedback
Daniil Tiapkin, Daniele Calandriello, Denis Belomestny +5
Traditional Reinforcement Learning from Human Feedback (RLHF) often relies on reward models, frequently assuming preference structures like the Bradley--Terry model, which may not…
Nash Learning from Human Feedback
Rémi Munos, Michal Valko, Daniele Calandriello +14
Reinforcement learning from human feedback (RLHF) has emerged as the main paradigm for aligning large language models (LLMs) with human preferences. Typically, RLHF involves the in…
Model-free Posterior Sampling via Learning Rate Randomization
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +6
In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the bes…
Demonstration-Regularized RL
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +5
Incorporating expert demonstrations has empirically helped to improve the sample efficiency of reinforcement learning (RL). This paper quantifies theoretically to what extent this…
Fast Rates for Maximum Entropy Exploration
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +7
We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. In this work, we study the maxim…
Adapting to game trees in zero-sum imperfect information games
Côme Fiegel, Pierre Ménard, Tadashi Kozuno +3
Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn -optimal strategies in a zero-sum IIG thro…
Curiosity in Hindsight: Intrinsic Exploration in Stochastic Environments
Daniel Jarrett, Corentin Tallec, Florent Altché +3
Consider the problem of exploration in sparse-reward or reward-free environments, such as in Montezuma's Revenge. In the curiosity-driven paradigm, the agent is rewarded for how mu…
Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +6
We consider reinforcement learning in an environment modeled by an episodic, finite, stage-dependent Markov decision process of horizon with states, and actions. The pe…
From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses
Daniil Tiapkin, Denis Belomestny, Eric Moulines +5
We propose the Bayes-UCBVI algorithm for reinforcement learning in tabular, stage-dependent, episodic Markov decision process: a natural extension of the Bayes-UCB algorithm by Kau…
Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times
Daniele Calandriello, Luigi Carratino, Alessandro Lazaric +2
Computing a Gaussian process (GP) posterior has a computational cost cubical in the number of historical points. A reformulation of the same GP posterior highlights that this compl…