33 citations · 128 across the 25 of their papers we have counts for
26 papers
Reverse-KL Policy Distillation: Statistical Guarantees and Limits
Haolin Liu, Chen-Yu Wei, Julian Zimmert
Reverse Kullback-Leibler (KL) distillation has shown empirical promise for training language models, but its statistical guarantees and limits remain poorly understood. In particul…
An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
Haolin Liu, Chen-Yu Wei, Julian Zimmert
We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coeffi…
Decision Making in Hybrid Environments: A Model Aggregation Approach
Haolin Liu, Chen-Yu Wei, Julian Zimmert
Recent work by Foster et al. (2021, 2022, 2023b) and Xu and Zeevi (2023) developed the framework of decision estimation coefficient (DEC) that characterizes the complexity of gener…
Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Haolin Liu, Zakaria Mhammedi, Chen-Yu Wei +1
We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedba…
Incentive-compatible Bandits: Importance Weighting No More
Julian Zimmert, Teodor V. Marinov
We study the problem of incentive-compatible online learning with bandit feedback. In this class of problems, the experts are self-interested agents who might misrepresent their pr…
Optimal cross-learning for contextual bandits with unknown context distributions
Jon Schneider, Julian Zimmert
We consider the problem of designing contextual bandit algorithms in the ``cross-learning'' setting of Balseiro et al., where the learner observes the loss for the action they play…
Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
Haolin Liu, Chen-Yu Wei, Julian Zimmert
We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback, without prior knowledge on transitions or access to simulato…
Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
Haolin Liu, Chen-Yu Wei, Julian Zimmert
We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from…
A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays
Saeed Masoudian, Julian Zimmert, Yevgeny Seldin
We propose a new best-of-both-worlds algorithm for bandits with variably delayed feedback. In contrast to prior work, which required prior knowledge of the maximal delay $d_{\mathr…
A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
Christoph Dann, Chen-Yu Wei, Julian Zimmert
Best-of-both-worlds algorithms for online learning which achieve near-optimal regret in both the adversarial and the stochastic regimes have received growing attention recently. Ex…
Best of Both Worlds Policy Optimization
Christoph Dann, Chen-Yu Wei, Julian Zimmert
Policy optimization methods are popular reinforcement learning algorithms in practice. Recent works have built theoretical foundation for them by proving regret bounds e…
Refined Regret for Adversarial MDPs with Linear Function Approximation
Yan Dai, Haipeng Luo, Chen-Yu Wei +1
We consider learning in an adversarial Markov Decision Process (MDP) where the loss functions can change arbitrarily over episodes and the state space can be arbitrarily large.…
A Unified Algorithm for Stochastic Path Problems
Christoph Dann, Chen-Yu Wei, Julian Zimmert
We study reinforcement learning in stochastic path (SP) problems. The goal in these problems is to maximize the expected sum of rewards until the agent reaches a terminal state. We…
A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning
Christoph Dann, Mehryar Mohri, Tong Zhang +1
Thompson Sampling is one of the most effective methods for contextual bandits and has been generalized to posterior sampling for certain MDP settings. However, existing posterior s…
A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback
Saeed Masoudian, Julian Zimmert, Yevgeny Seldin
We present a modified tuning of the algorithm of Zimmert and Seldin [2020] for adversarial multiarmed bandits with delayed feedback, which in addition to the minimax optimal advers…
Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality
Teodor V. Marinov, Mehryar Mohri, Julian Zimmert
We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite…
The Pareto Frontier of model selection for general Contextual Bandits
Teodor V. Marinov, Julian Zimmert
Recent progress in model selection raises the question of the fundamental limits of these techniques. Under specific scrutiny has been model selection for general contextual bandit…
A Model Selection Approach for Corruption Robust Reinforcement Learning
Chen-Yu Wei, Christoph Dann, Julian Zimmert
We develop a model selection approach to tackle reinforcement learning with adversarial corruption in both transition and reward. For finite-horizon tabular MDPs, without prior kno…
Adapting to Misspecification in Contextual Bandits
Dylan J. Foster, Claudio Gentile, Mehryar Mohri +1
A major research direction in contextual bandits is to develop algorithms that are computationally efficient, yet support flexible, general-purpose function approximation. Algorith…
Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
Christoph Dann, Teodor V. Marinov, Mehryar Mohri +1
We provide improved gap-dependent regret bounds for reinforcement learning in finite episodic Markov decision processes. Compared to prior work, our bounds depend on alternative de…
Model Selection in Contextual Stochastic Bandit Problems
Aldo Pacchiano, My Phan, Yasin Abbasi-Yadkori +4
We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base…
An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays
Julian Zimmert, Yevgeny Seldin
We propose a new algorithm for adversarial multi-armed bandits with unrestricted delays. The algorithm is based on a novel hybrid regularizer applied in the Follow the Regularized…
Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
Julian Zimmert, Tor Lattimore
The information-theoretic analysis by Russo and Van Roy (2014) in combination with minimax duality has proved a powerful tool for the analysis of online learning algorithms in full…
Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
Julian Zimmert, Haipeng Luo, Chen-Yu Wei
We develop the first general semi-bandit algorithm that simultaneously achieves regret for stochastic environments and regret for adve…