174 citations · 680 across the 52 of their papers we have counts for
53 papers
Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
Fan Chen, Dylan J. Foster, Yanjun Han +3
We develop a unifying framework for information-theoretic lower bound in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's…
The Power of Resets in Online Reinforcement Learning
Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin
Simulators are a pervasive tool in reinforcement learning, but most existing algorithms cannot efficiently exploit simulator access -- particularly in high-dimensional domains that…
Online Estimation via Offline Estimation: An Information-Theoretic Framework
Dylan J. Foster, Yanjun Han, Jian Qian +1
The classical theory of statistical estimation aims to estimate a parameter of interest under data generated from a fixed design ("offline estimation"), while the contemporary t…
Foundations of Reinforcement Learning and Interactive Decision Making
Dylan J. Foster, Alexander Rakhlin
Interactive decision making is the problem of learning to act well in an unknown environment, using the data that one's own actions generate to continuously improve, and arises in…
Efficient Model-Free Exploration in Low-Rank MDPs
Zakaria Mhammedi, Adam Block, Dylan J. Foster +1
A major challenge in reinforcement learning is to develop practical, sample-efficient algorithms for exploration in high-dimensional domains where generalization and function appro…
On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring
Dylan J. Foster, Dean P. Foster, Noah Golowich +1
A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learnin…
Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory
Andrew Wagenmaker, Dylan J. Foster
We consider the development of adaptive, instance-dependent algorithms for interactive decision making (bandits, reinforcement learning, and beyond) that, rather than only performi…
Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL
Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin
We study the design of sample-efficient algorithms for reinforcement learning in the presence of rich, high-dimensional observations, formalized via the Block MDP problem. Existing…
Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games
Dylan J. Foster, Noah Golowich, Sham M. Kakade
We consider the problem of decentralized multi-agent reinforcement learning in Markov games. A fundamental question is whether there exist algorithms that, when adopted by all agen…
Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient
Dylan J. Foster, Noah Golowich, Yanjun Han
A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what a…
Model-Free Reinforcement Learning with the Decision-Estimation Coefficient
Dylan J. Foster, Noah Golowich, Jian Qian +2
We consider the problem of interactive decision making, encompassing structured bandits and reinforcement learning with general function approximation. Recently, Foster et al. (202…
Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression
Aleksandrs Slivkins, Xingyu Zhou, Karthik Abinav Sankararaman +1
We consider contextual bandits with linear constraints (CBwLC), a variant of contextual bandits in which the algorithm consumes multiple resources subject to linear constraints on…
The Role of Coverage in Online Reinforcement Learning
Tengyang Xie, Dylan J. Foster, Yu Bai +2
Coverage conditions -- which assert that the data logging distribution adequately covers the state space -- play a fundamental role in determining the sample complexity of offline…
Contextual Bandits with Large Action Spaces: Made Practical
Yinglun Zhu, Dylan J. Foster, John Langford +1
A central problem in sequential decision making is to develop algorithms that are practical and computationally efficient, yet support the use of flexible, general-purpose models.…
Guaranteed Discovery of Control-Endogenous Latent States with Multi-Step Inverse Models
Alex Lamb, Riashat Islam, Yonathan Efroni +7
In many sequential decision-making tasks, the agent is not able to model the full complexity of the world, which consists of multitudes of relevant and irrelevant information. For…
On the Complexity of Adversarial Decision Making
Dylan J. Foster, Alexander Rakhlin, Ayush Sekhari +1
A central problem in online learning and decision making -- from bandits to reinforcement learning -- is to understand what modeling assumptions lead to sample-efficient learning g…
Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information
Yonathan Efroni, Dylan J. Foster, Dipendra Misra +2
In real-world reinforcement learning applications the learner's observation space is ubiquitously high-dimensional with both relevant and irrelevant information about the task at h…
Interaction-Grounded Learning with Action-inclusive Feedback
Tengyang Xie, Akanksha Saran, Dylan J. Foster +5
Consider the problem setting of Interaction-Grounded Learning (IGL), in which a learner's goal is to optimally interact with the environment with no explicit reward to ground its p…
The Statistical Complexity of Interactive Decision Making
Dylan J. Foster, Sham M. Kakade, Jian Qian +1
A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algor…
Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi +1
We consider the offline reinforcement learning problem, where the aim is to learn a decision making policy from logged data. Offline RL -- particularly when coupled with (value) fu…
Minimax Rates for Conditional Density Estimation via Empirical Entropy
Blair Bilodeau, Dylan J. Foster, Daniel M. Roy
We consider the task of estimating a conditional density using i.i.d. samples from a joint distribution, which is a fundamental problem with applications in both classification and…
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…
Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
Dylan J. Foster, Akshay Krishnamurthy
A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise, often quantified by the performanc…
Understanding the Eluder Dimension
Gene Li, Pritish Kamath, Dylan J. Foster +1
We provide new insights on eluder dimension, a complexity measure that has been extensively used to bound the regret of algorithms for online bandits and reinforcement learning wit…