75 citations · 820 across the 81 of their papers we have counts for
52 papers · 1 filter
Trading off rewards and errors in multi-armed bandits
Akram Erraqabi, Alessandro Lazaric, Michal Valko +2
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm…
Large-scale semi-supervised learning with online spectral graph sparsification
Daniele Calandriello, Alessandro Lazaric, Michal Valko
We introduce Sparse-HFS, a scalable algorithm that can compute solutions to SSL problems using only O(n polylog(n)) space and O(m polylog(n)) time.
Improved large-scale graph learning through ridge spectral sparsification
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric +1
Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Lapl…
Analysis of Nystrom method with sequential ridge leverage scores
Daniele Calandriello, Alessandro Lazaric, Michal Valko
Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of c…
Maximum Entropy Semi-Supervised Inverse Reinforcement Learning
Julien Audiffren, Michal Valko, Alessandro Lazaric +1
A popular approach to apprenticeship learning (AL) is to formulate it as an inverse reinforcement learning (IRL) problem. The MaxEnt-IRL algorithm successfully integrates the maxim…
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
Jean Tarbouriech, Matteo Pirotta, Michal Valko +1
We study the sample complexity of learning an -optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access…
TD-JEPA: Latent-predictive Representations for Zero-Shot Reinforcement Learning
Marco Bagatella, Matteo Pirotta, Ahmed Touati +2
Latent prediction--where agents learn by predicting their own latents--has emerged as a powerful paradigm for training general representations in machine learning. In reinforcement…
Zero-Shot Whole-Body Humanoid Control via Behavioral Foundation Models
Andrea Tirinzoni, Ahmed Touati, Jesse Farebrother +5
Unsupervised reinforcement learning (RL) aims at pre-training agents that can solve a wide range of downstream tasks in complex environments. Despite recent advancements, existing…
Fast Adaptation with Behavioral Foundation Models
Harshit Sikchi, Andrea Tirinzoni, Ahmed Touati +6
Unsupervised zero-shot reinforcement learning (RL) has emerged as a powerful paradigm for pretraining behavioral foundation models (BFMs), enabling agents to solve a wide range of…
Temporal Difference Flows
Jesse Farebrother, Matteo Pirotta, Andrea Tirinzoni +3
Predictive models of the future are fundamental for an agent's ability to reason and plan. A common strategy learns a world model and unrolls it step-by-step at inference, where sm…
Simple Ingredients for Offline Reinforcement Learning
Edoardo Cetin, Andrea Tirinzoni, Matteo Pirotta +3
Offline reinforcement learning algorithms have proven effective on datasets highly connected to the target downstream task. Yet, leveraging a novel testbed (MOOD) in which trajecto…
Layered State Discovery for Incremental Autonomous Exploration
Liyu Chen, Andrea Tirinzoni, Alessandro Lazaric +1
We study the autonomous exploration (AX) problem proposed by Lim & Auer (2012). In this setting, the objective is to discover a set of -optimal policies reaching a set $\mathcal…
On the Complexity of Representation Learning in Contextual Linear Bandits
Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric
In contextual linear bandits, the reward function is assumed to be a linear combination of an unknown reward vector and a given embedding of context-arm pairs. In practice, the emb…
Improved Adaptive Algorithm for Scalable Active Learning with Weak Labeler
Yifang Chen, Karthik Sankararaman, Alessandro Lazaric +6
Active learning with strong and weak labelers considers a practical setting where we have access to both costly but accurate strong labelers and inaccurate but cheap predictions pr…
Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees
Andrea Tirinzoni, Matteo Papini, Ahmed Touati +2
We study the problem of representation learning in stochastic contextual linear bandits. While the primary concern in this domain is usually to find realizable representations (i.e…
Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path
Liyu Chen, Andrea Tirinzoni, Matteo Pirotta +1
We study the sample complexity of learning an -optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access…
Contextual bandits with concave rewards, and an application to fair ranking
Virginie Do, Elvis Dohmatob, Matteo Pirotta +2
We consider Contextual Bandits with Concave Rewards (CBCR), a multi-objective bandit problem where the desired trade-off between the rewards is defined by a known concave objective…
Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
Rui Yuan, Simon S. Du, Robert M. Gower +2
We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear pol…
Temporal Abstractions-Augmented Temporally Contrastive Learning: An Alternative to the Laplacian in RL
Akram Erraqabi, Marlos C. Machado, Mingde Zhao +4
In reinforcement learning, the graph Laplacian has proved to be a valuable tool in the task-agnostic setting, with applications ranging from skill discovery to reward shaping. Rece…
Don't Change the Algorithm, Change the Data: Exploratory Data for Offline Reinforcement Learning
Denis Yarats, David Brandfonbrener, Hao Liu +4
Recent progress in deep learning has relied on access to large and diverse datasets. Such data-driven progress has been less evident in offline reinforcement learning (RL), because…
Differentially Private Exploration in Reinforcement Learning with Linear Representation
Paul Luyo, Evrard Garcelon, Alessandro Lazaric +1
This paper studies privacy-preserving exploration in Markov Decision Processes (MDPs) with linear representation. We first consider the setting of linear-mixture MDPs (Ayoub et al.…
Top Ranking for Multi-Armed Bandit with Noisy Evaluations
Evrard Garcelon, Vashist Avadhanula, Alessandro Lazaric +1
We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent, and possibly biased, \emph{evaluations} of the true reward o…
Adaptive Multi-Goal Exploration
Jean Tarbouriech, Omar Darwiche Domingues, Pierre Ménard +3
We introduce a generic strategy for provably efficient multi-goal exploration. It relies on AdaGoal, a novel goal selection scheme that leverages a measure of uncertainty in reachi…
Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection
Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano +3
We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first de…