125 citations · 148 across the 19 of their papers we have counts for
24 papers
Expected Sample Complexity in Multi-Armed Bandits
Nadav Sukenik, Nadav Merlis
Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an envi…
Adaptive Bandit Algorithms for Contextual Matching Markets
Shiyun Lin, Simon Mauras, Vianney Perchet +1
We study bandit learning in matching markets, where players and arms constitute the two market sides, and the players' utilities are linear in the arm contexts. In each round, new…
Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching
Nadav Merlis
We study tabular reinforcement learning problems with multiple steps of lookahead information. Before acting, the learner observes steps of future transition and reward real…
Online Linear Regression with Paid Stochastic Features
Nadav Merlis, Kyoungseok Jang, Nicolò Cesa-Bianchi
We study an online linear regression setting in which the observed feature vectors are corrupted by noise and the learner can pay to reduce the noise level. In practice, this may h…
On the Hardness of Reinforcement Learning with Transition Look-Ahead
Corentin Pla, Hugo Richard, Marc Abeille +2
We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of actions before decidi…
Stable Matching with Ties: Approximation Ratios and Learning
Shiyun Lin, Simon Mauras, Nadav Merlis +1
We study matching markets with ties, where workers on one side of the market may have tied preferences over jobs, determined by their matching utilities. Unlike classical two-sided…
Improved Algorithms for Contextual Dynamic Pricing
Matilde Tullii, Solenne Gaucher, Nadav Merlis +1
In contextual dynamic pricing, a seller sequentially prices goods based on contextual information. Buyers will purchase products only if the prices are below their valuations. The…
Reinforcement Learning with Lookahead Information
Nadav Merlis
We study reinforcement learning (RL) problems in which agents observe the reward or transition realizations at their current state before deciding which action to take. Such observ…
On Bits and Bandits: Quantifying the Regret-Information Trade-off
Itai Shufaro, Nadav Merlis, Nir Weinberger +1
In many sequential decision problems, an agent performs a repeated task. He then suffers regret and obtains information that he may use in the following rounds. However, sometimes…
The Value of Reward Lookahead in Reinforcement Learning
Nadav Merlis, Dorian Baudry, Vianney Perchet
In reinforcement learning (RL), agents sequentially interact with changing environments while aiming to maximize the obtained rewards. Usually, rewards are observed only after acti…
Ranking with Popularity Bias: User Welfare under Self-Amplification Dynamics
Guy Tennenholtz, Martin Mladenov, Nadav Merlis +2
While popularity bias is recognized to play a crucial role in recommmender (and other ranking-based) systems, detailed analysis of its impact on collective user welfare has largely…
Reinforcement Learning with History-Dependent Dynamic Contexts
Guy Tennenholtz, Nadav Merlis, Lior Shani +2
We introduce Dynamic Contextual Markov Decision Processes (DCMDPs), a novel reinforcement learning framework for history-dependent environments that generalizes the contextual MDP…
On Preemption and Learning in Stochastic Scheduling
Nadav Merlis, Hugo Richard, Flore Sentenac +3
We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristic…
Reinforcement Learning with a Terminator
Guy Tennenholtz, Nadav Merlis, Lior Shani +5
We present the problem of reinforcement learning with exogenous termination. We define the Termination Markov Decision Process (TerMDP), an extension of the MDP framework, in which…
Query-Reward Tradeoffs in Multi-Armed Bandits
Nadav Merlis, Yonathan Efroni, Shie Mannor
We consider a stochastic multi-armed bandit setting where reward must be actively queried for it to be observed. We provide tight lower and upper problem-dependent guarantees on bo…
Ensemble Bootstrapping for Q-Learning
Oren Peer, Chen Tessler, Nadav Merlis +1
Q-learning (QL), a common reinforcement learning algorithm, suffers from over-estimation bias due to the maximization term in the optimal Bellman operator. This bias may lead to su…
Confidence-Budget Matching for Sequential Budgeted Learning
Yonathan Efroni, Nadav Merlis, Aadirupa Saha +1
A core element in decision-making under uncertainty is the feedback on the quality of the performed actions. However, in many applications, such feedback is restricted. For example…
Reinforcement Learning with Trajectory Feedback
Yonathan Efroni, Nadav Merlis, Shie Mannor
The standard feedback model of reinforcement learning requires revealing the reward of every visited state-action pair. However, in practice, it is often the case that such frequen…
Lenient Regret for Multi-Armed Bandits
Nadav Merlis, Shie Mannor
We consider the Multi-Armed Bandit (MAB) problem, where an agent sequentially chooses actions and observes rewards for the actions it took. While the majority of algorithms try to…
Tight Lower Bounds for Combinatorial Multi-Armed Bandits
Nadav Merlis, Shie Mannor
The Combinatorial Multi-Armed Bandit problem is a sequential decision-making problem in which an agent selects a set of arms on each round, observes feedback for each of these arms…
Never Worse, Mostly Better: Stable Policy Improvement in Deep Reinforcement Learning
Pranav Khanna, Guy Tennenholtz, Nadav Merlis +2
In recent years, there has been significant progress in applying deep reinforcement learning (RL) for solving challenging problems across a wide variety of domains. Nevertheless, c…
Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh +1
State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing \emph{full-planning} on Mar…
Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
Nadav Merlis, Shie Mannor
We consider the combinatorial multi-armed bandit (CMAB) problem, where the reward function is nonlinear. In this setting, the agent chooses a batch of arms on each round and receiv…
Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning
Tom Zahavy, Matan Haroush, Nadav Merlis +2
Learning how to act when there are many available actions in each state is a challenging task for Reinforcement Learning (RL) agents, especially when many of the actions are redund…