Y. Mansour

Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits

Idan Attias, Orin Levy, Alexander Ryabchenko +2

Can vanilla policy optimization explore enough to achieve near-optimal regret in stochastic contextual bandits? We show that standard exponential policy updates driven by offline r…

Near-Optimal Stochastic Linear Bandits with Delay

Ofir Schlisselberg, Mengxiao Zhang, Yishay Mansour

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits e…

Cost-Aware Learning

Clara Mohri, Amir Globerson, Haim Kaplan +2

We consider the problem of Cost-Aware Learning, where sampling different components of a finite-sum objective incurs different costs. The objective is to reach a target error while…

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

Shashaank Aiyer, Yishay Mansour, Shay Moran +2

We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the f…

Collaborating in Multi-Armed Bandits with Strategic Agents

Idan Barnea, Ofir Schlisselberg, Yishay Mansour

We study collaborative learning in multi-agent Bayesian bandit problems, where strategic agents collectively solve the same bandit instance. While multiple agents can accelerate le…

Online Set Learning from Precision and Recall Feedback

Lee Cohen, Yishay Mansour, Shay Moran +1

We consider the problem of learning an unknown subset $N_{target}$ of a domain in an online setting. In each round $t$ , the learner predicts a set of items $N_{t}$ and receive…

Theoretical Foundations and Effective Algorithms for Policy-Aware Simulator Learning

Christoph Dann, Yishay Mansour, Mehryar Mohri

Model-based reinforcement learning (MBRL) agents typically learn world models by minimizing predictive loss. However, powerful RL optimizers inevitably exploit minor model inaccura…

Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation

Orin Levy, Aviv Rosenberg, Alon Cohen +1

We introduce \texttt{OPO-CMDP}, the first policy optimization algorithm for stochastic Contextual Markov Decision Process (CMDPs) under general offline function approximation. Our…

Optimal Regret for Policy Optimization in Contextual Bandits

Orin Levy, Yishay Mansour

We present the first high-probability optimal regret bound for a policy optimization technique applied to the problem of stochastic contextual multi-armed bandit (CMAB) with genera…

Online Learning in MDPs with Partially Adversarial Transitions and Losses

Ofir Schlisselberg, Tal Lancewicki, Yishay Mansour

We study reinforcement learning in MDPs whose transition function is stochastic at most steps but may behave adversarially at a fixed subset of $Λ$ steps per episode. This model ca…

The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration

Idan Barnea, Orin Levy, Yishay Mansour

We study cooperative multi-agent reinforcement learning in the setting of reward-free exploration, where multiple agents jointly explore an unknown MDP in order to learn its dynami…

Stochastic Linear Bandits with Parameter Noise

Daniel Ezer, Alon Peled-Cohen, Yishay Mansour

We study the stochastic linear bandits with parameter noise model, in which the reward of action $a$ is $a^{⊤} θ$ where $θ$ is sampled i.i.d. We show a regret upper bound of $\wid…

Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback

Orin Levy, Liad Erez, Alon Cohen +1

We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over $K$ actions in the presence of delayed feedback, a scenario where loss observati…

Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback

Ofir Schlisselberg, Tal Lancewicki, Peter Auer +1

We study the multi-armed bandit problem with adversarially chosen delays in the Best-of-Both-Worlds (BoBW) framework, which aims to achieve near-optimal performance in both stochas…

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback

Tal Lancewicki, Yishay Mansour

We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent…

Rising Rested MAB with Linear Drift

Omer Amichay, Yishay Mansour

We consider non-stationary multi-arm bandit (MAB) where the expected reward of each action follows a linear function of the number of times we executed the action. Our main result…

Individual Regret in Cooperative Stochastic Multi-Armed Bandits

Idan Barnea, Tal Lancewicki, Yishay Mansour

We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We analyzed a variant of Cooperat…

Batch Ensemble for Variance Dependent Regret in Stochastic Bandits

Asaf Cassel, Orin Levy, Yishay Mansour

Efficiently trading off exploration and exploitation is one of the key challenges in online Reinforcement Learning (RL). Most works achieve this by carefully estimating the model u…

Delay as Payoff in MAB

Ofir Schlisselberg, Ido Cohen, Tal Lancewicki +1

In this paper, we investigate a variant of the classical stochastic Multi-armed Bandit (MAB) problem, where the payoff received by an agent (either cost or reward) is both delayed,…