research
∙
08/28/2023
Rate-Optimal Policy Optimization for Linear Markov Decision Processes
We study regret minimization in online episodic linear Markov Decision P...
share
research
∙
07/02/2023
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
We study a generalization of boosting to the multiclass setting. We intr...
research
∙
03/12/2023
The tree reconstruction game: phylogenetic reconstruction using reinforcement learning
We propose a reinforcement-learning algorithm to tackle the challenge of...
research
∙
03/02/2023
Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation
We present the OMG-CMDP! algorithm for regret minimization in adversaria...
research
∙
02/27/2023
On Differentially Private Online Predictions
In this work we introduce an interactive variant of joint differential p...
research
∙
02/03/2023
Pseudonorm Approachability and Applications to Regret Minimization
Blackwell's celebrated approachability theory provides a general framewo...
research
∙
02/01/2023
Uniswap Liquidity Provision: An Online Learning Approach
Decentralized Exchanges (DEXs) are new types of marketplaces leveraging ...
research
∙
01/30/2023
Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation
We study reinforcement learning with linear function approximation and a...
research
∙
01/29/2023
Concurrent Shuffle Differential Privacy Under Continual Observation
We introduce the concurrent shuffle model of differential privacy. In th...
research
∙
11/27/2022
Counterfactual Optimism: Rate Optimal Regret for Stochastic Contextual MDPs
We present the UC^3RL algorithm for regret minimization in Stochastic Co...
research
∙
07/28/2022
Regret Minimization and Convergence to Equilibria in General-sum Markov Games
An abundance of recent impossibility results establish that regret minim...
research
∙
07/22/2022
Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP
We present regret minimization algorithms for stochastic contextual MDPs...
research
∙
06/19/2022
Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation
Myopic exploration policies such as epsilon-greedy, softmax, or Gaussian...
research
∙
06/09/2022
There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes
Interpretability is an essential building block for trustworthiness in r...
research
∙
05/19/2022
What killed the Convex Booster ?
A landmark negative result of Long and Servedio established a worst-case...
research
∙
05/17/2022
Strategizing against Learners in Bayesian Games
We study repeated two-player games where one of the players, the learner...
research
∙
03/02/2022
Learning Efficiently Function Approximation for Contextual MDP
We study learning contextual MDPs using a function approximation for bot...
research
∙
02/27/2022
Benign Underfitting of Stochastic Gradient Descent
We study to what extent may stochastic gradient descent (SGD) be underst...
research
∙
02/12/2022
Stochastic Strategic Patient Buyers: Revenue maximization using posted prices
We consider a seller faced with buyers which have the ability to delay t...
research
∙
02/11/2022
A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
We study the problem of semi-supervised learning of an adversarially-rob...
research
∙
02/10/2022
Monotone Learning
The amount of training-data is one of the key factors which determines t...
research
∙
01/31/2022
Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
The standard assumption in reinforcement learning (RL) is that agents ob...
research
∙
01/31/2022
Cooperative Online Learning in Stochastic and Adversarial MDPs
We study cooperative online learning in stochastic and adversarial Marko...
research
∙
01/31/2022
Fair Wrapping for Black-box Predictions
We introduce a new family of techniques to post-process ("wrap") a black...
research
∙
12/29/2021
Differentially-Private Clustering of Easy Instances
Clustering is a fundamental problem in data analysis. In differentially ...
research
∙
12/06/2021
Nonstochastic Bandits with Composite Anonymous Feedback
We investigate a nonstochastic bandit setting in which the loss of an ac...
research
∙
11/07/2021
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
A dynamic algorithm against an adaptive adversary is required to be corr...
research
∙
10/19/2021
FriendlyCore: Practical Differentially Private Aggregation
Differentially private algorithms for common metric aggregation tasks, s...
research
∙
06/29/2021
Optimal Rates for Random Order Online Optimization
We study online convex optimization in the random order model, recently ...
research
∙
06/22/2021
Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
There have been many recent advances on provably efficient Reinforcement...
research
∙
06/05/2021
Differentially Private Multi-Armed Bandits in the Shuffle Model
We give an (ε,δ)-differentially private algorithm for the multi-armed ba...
research
∙
06/04/2021
Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions
We study the stochastic Multi-Armed Bandit (MAB) problem with random del...
research
∙
03/24/2021
Minimax Regret for Stochastic Shortest Path
We study the Stochastic Shortest Path (SSP) problem in which an agent ha...
research
∙
03/15/2021
Competitive Equilibria with Unequal Budgets: Supporting Arbitrary Pareto Optimal Allocations
We consider a market setting of agents with additive valuations over het...
research
∙
01/31/2021
Online Markov Decision Processes with Aggregate Bandit Feedback
We study a novel variant of online finite-horizon Markov Decision Proces...
research
∙
01/26/2021
Separating Adaptive Streaming from Oblivious Streaming
We present a streaming problem for which every adversarially-robust stre...
research
∙
12/29/2020
Learning Adversarial Markov Decision Processes with Delayed Feedback
Reinforcement learning typically assumes that the agent observes feedbac...
research
∙
10/27/2020
Adversarial Dueling Bandits
We introduce the problem of regret minimization in Adversarial Dueling B...
research
∙
10/04/2020
Kidney exchange and endless paths: On the optimal use of an altruistic donor
We consider a well-studied online random graph model for kidney exchange...
research
∙
10/02/2020
The Sparse Vector Technique, Revisited
We revisit one of the most basic and widely applicable techniques in the...
research
∙
09/13/2020
Oracle-Efficient Reinforcement Learning in Factored MDPs with Unknown Structure
We consider provably-efficient reinforcement learning (RL) in non-episod...
research
∙
08/21/2020
Beyond Individual and Group Fairness
We present a new data-driven model of fairness that, unlike existing sta...
research
∙
07/24/2020
Detecting malicious PDF using CNN
Malicious PDF files represent one of the biggest threats to computer sec...
research
∙
07/19/2020
A Theory of Multiple-Source Adaptation with Limited Target Labeled Data
We study multiple-source domain adaptation, when the learner has access ...
research
∙
06/20/2020
Adversarial Stochastic Shortest Path
Stochastic shortest path (SSP) is a well-known problem in planning and c...
research
∙
05/07/2020
Reinforcement Learning with Feedback Graphs
We study episodic reinforcement learning in Markov decision processes wh...
research
∙
04/16/2020
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
We present a differentially private learner for halfspaces over a finite...
research
∙
04/13/2020
Adversarially Robust Streaming Algorithms via Differential Privacy
A streaming algorithm is said to be adversarially robust if its accuracy...
research
∙
02/25/2020
Three Approaches for Personalization with Applications to Federated Learning
The standard objective in machine learning is to train a single model fo...
research
∙
02/24/2020
