174 citations · 680 across the 52 of their papers we have counts for
7 papers · 1 filter
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…