Publications

You can also find my articles on my Google Scholar profile.

Monograph

Foundations of Reinforcement Learning and Interactive Decision Making

Dylan J. Foster and Alexander Rakhlin.
Preprint, 2023.
Actively being updated. Originally developed as lecture notes for 9.522: Statistical Reinforcement Learning and Decision Making.

Thesis

Adaptive Learning: Algorithms and Complexity

Dylan J. Foster.
PhD Thesis, Department of Computer Science, Cornell University, 2019.
Cornell CS Doctoral Dissertation Award.

Preprints

The Statistical Complexity of Interactive Decision Making

Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin.
Preprint (under review), 2021. [talk].

2025

Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment

Audrey Huang, Adam Block, Qinghua Liu, Nan Jiang, Akshay Krishnamurthy, and Dylan J. Foster.
ICML, 2025.

Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration

Dylan J. Foster, Zakaria Mhammedi, and Dhruv Rohatgi.
COLT, 2025.

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification

Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster.
COLT, 2025. [Dhruv's talk].

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning

Dhruv Rohatgi and Dylan J. Foster.
COLT, 2025.

Self-Improvement in Language Models: The Sharpening Mechanism

Audrey Huang*, Adam Block*, Dylan J. Foster*, Dhruv Rohatgi, Cyril Zhang, Max Simchowitz, Jordan T. Ash, and Akshay Krishnamurthy.
ICLR, 2025. Oral presentation.

Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization

Audrey Huang, Wenhao Zhan, Tengyang Xie, Jason D. Lee, Wen Sun, Akshay Krishnamurthy, and Dylan J. Foster.
ICLR, 2025. Spotlight presentation. [Audrey's talk].

Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF

Tengyang Xie*, Dylan J. Foster*, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin.
ICLR, 2025. [XPO Trainer in TRL].

2024

Reinforcement Learning Under Latent Dynamics: Toward Statistical and Algorithmic Modularity

Philip Amortila, Dylan J. Foster, Nan Jiang, Akshay Krishnamurthy, and Zakaria Mhammedi.
NeurIPS, 2024. Oral presentation. [Podcast, Phil's talk].

Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning

Dylan J. Foster, Adam Block, and Dipendra Misra.
NeurIPS, 2024. Spotlight presentation. [talk].

The Power of Resets in Online Reinforcement Learning

Zakaria Mhammedi, Dylan J. Foster, and Alexander Rakhlin.
NeurIPS, 2024. Spotlight presentation. [Zak's talk].

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability

Fan Chen, Dylan J. Foster, Yanjun Han, Jian Qian, Alexander Rakhlin, Yunbei Xu.
NeurIPS, 2024. Spotlight presentation.

Can Large Language Models Explore In-Context?

Akshay Krishnamurthy, Keegan Harris, Dylan J. Foster, Cyril Zhang, Aleksandrs Slivkins.
NeurIPS, 2024.

Online Estimation via Offline Estimation: An Information-Theoretic Framework

Dylan J. Foster, Yanjun Han, Jian Qian, Alexander Rakhlin.
NeurIPS, 2024.

Scalable Online Exploration via Coverability

Philip Amortila, Dylan J. Foster, and Akshay Krishnamurthy.
ICML, 2024. [Phil's talk].

Rich-Observation Reinforcement Learning with Continuous Latent Dynamics

Yuda Song, Lili Wu, Dylan J. Foster, and Akshay Krishnamurthy.
ICML, 2024.

Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression

Adam Block, Dylan J. Foster, Akshay Krishnamurthy, Max Simchowitz, Cyril Zhang.
ICLR, 2024.

Harnessing Density Ratios for Online Reinforcement Learning

Philip Amortila, Dylan J. Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie.
ICLR, 2024. Spotlight presentation.

Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression

Aleksandrs Slivkins, Xingyu Zhou, Karthik Abinav Sankararaman, and Dylan J. Foster.
JMLR, 2024.
Conference version previously appeared at COLT 2023.

2023

Efficient Model-Free Exploration in Low-Rank MDPs

Zakaria Mhammedi, Adam Block, Dylan J. Foster, and Alexander Rakhlin.
NeurIPS, 2023.
Note: arXiv version improves upon results in NeurIPS version, removing reachability assumption.

Model-Free Reinforcement Learning with the Decision Estimation Coefficient

Dylan J. Foster, Noah Golowich, Jian Qian, Ayush Sekhari, and Alexander Rakhlin.
NeurIPS, 2023.

Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL

Zakaria Mhammedi, Dylan J. Foster, and Alexander Rakhlin.
ICML, 2023. Oral presentation.

Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games

Dylan J. Foster, Noah Golowich, and Sham M. Kakade.
ICML, 2023.

Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

Dylan J. Foster, Noah Golowich, and Yanjun Han.
COLT, 2023. [talk].

Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory

Andrew Wagenmaker and Dylan J. Foster.
COLT, 2023.

On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring

Dylan J. Foster, Dean Foster, Noah Golowich, and Alexander Rakhlin.
COLT, 2023.

The Role of Coverage in Online Reinforcement Learning

Tengyang Xie*, Dylan J. Foster*, Yu Bai, Nan Jiang, and Sham M. Kakade.
ICLR, 2023. Oral presentation. [Tengyang's talk].

Guaranteed Discovery of Control-Endogenous Latent States with Multi-Step Inverse Models

Alex Lamb, Riashat Islam, Yonathan Efroni, Aniket Didolkar, Dipendra Misra, Dylan J. Foster, Lekan Molu, Rajan Chari, Akshay Krishnamurthy, and John Langford.
TMLR, 2023.

Minimax Rates for Conditional Density Estimation via Empirical Entropy

Blair Bilodeau, Dylan J. Foster, and Daniel Roy.
Annals of Statistics, 2023.

2022

On the Complexity of Adversarial Decision Making

Dylan J. Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan.
NeurIPS, 2022. Oral presentation.

Understanding the Eluder Dimension

Gene Li, Pritish Kamath, Dylan J. Foster, and Nathan Srebro.
NeurIPS, 2022.

Interaction-Grounded Learning with Action-Inclusive Feedback

Tengyang Xie, Akanksha Saran, Dylan J. Foster, Lekan Molu, Ida Momennejad, Nan Jiang, Paul Mineiro, John Langford.
NeurIPS, 2022.

Contextual Bandits with Large Action Spaces: Made Practical

Yinglun Zhu, Dylan J. Foster, Paul Mineiro, and John Langford.
ICML, 2022.

Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation

Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu.
COLT, 2022.
Oral presentation at NeurIPS 2021 Offline Reinforcement Learning workshop..

Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information

Yonathan Efroni, Dylan J. Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford.
COLT, 2022.

Lower Bounds for Non-Convex Stochastic Optimization

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth.
Mathematical Programming, Series A, 2022.

2021

Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

Dylan J. Foster and Akshay Krishnamurthy.
NeurIPS, 2021. Oral presentation.

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

Dylan J. Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu.
COLT, 2021.

2020

Learning the Linear Quadratic Regulator from Nonlinear Observations

Zakaria Mhammedi, Dylan J. Foster, Max Simchowitz, Dipendra Misra, Wen Sun, Akshay Krishnamurthy, Alexander Rakhlin, and John Langford.
NeurIPS, 2020.

Independent Policy Gradient Methods for Competitive Reinforcement Learning

Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich.
NeurIPS, 2020.

Adapting to Misspecficiation in Contextual Bandits

Dylan J. Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert.
NeurIPS, 2020.

Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles

Dylan J. Foster and Alexander Rakhlin.
ICML, 2020.
Now in Vowpal Wabbit! Use the --squarecb option or see here for more information.

Naive Exploration is Optimal for Online LQR

Max Simchowitz and Dylan J. Foster.
ICML, 2020.

Logarithmic Regret for Adversarial Online Control

Dylan J. Foster and Max Simchowitz.
ICML, 2020.

Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance

Blair Bilodeau, Dylan J. Foster, and Daniel Roy.
ICML, 2020.

Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan.
COLT, 2020.

Open Problem: Model Selection for Contextual Bandits

Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo.
COLT Open Problem, 2020.
Solution by Teodor Marinov and Julian Zimmert.

Learning Nonlinear Dynamical Systems from a Single Trajectory

Dylan J. Foster, Alexander Rakhlin, and Tuhin Sarkar.
L4DC, 2020. Full oral presentation.

2019

Model Selection for Contextual Bandits

Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo.
NeurIPS, 2019. Spotlight presentation.

Hypothesis Set Stability and Generalization

Dylan J. Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan.
NeurIPS, 2019.

Distributed Learning with Sublinear Communication

Jayadev Acharya, Christopher De Sa, Dylan J. Foster, and Karthik Sridharan.
ICML, 2019. Long talk.

Orthogonal Statistical Learning

Dylan J. Foster and Vasilis Syrgkanis.
COLT, 2019. Best Paper Award.
Journal version in Annals of Statistics (2023).

The Complexity of Making the Gradient Small in Stochastic Convex Optimization

Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, and Blake Woodworth.
COLT, 2019. Best Student Paper Award.

Sum-of-Squares Meets Square Loss: Fast Rates for Agnostic Tensor Completion

Dylan J. Foster and Andrej Risteski.
COLT, 2019.

2018

Contextual Bandits with Surrogate Losses: Margin Bounds and Efficient Algorithms

Dylan J. Foster and Akshay Krishnamurthy.
NeurIPS, 2018.

Uniform Convergence of Gradients for Non-Convex Learning and Optimization

Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan.
NeurIPS, 2018.

Practical Contextual Bandits with Regression Oracles

Dylan J. Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E. Schapire.
ICML, 2018. Long talk.
Now in Vowpal Wabbit (thanks to Alberto Bietti!). Try it with the --regcb or --regcbopt option.

Logistic Regression: The Importance of Being Improper

Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan.
COLT, 2018. Best Student Paper Award.

Online Learning: Sufficient Statistics and the Burkholder Method

Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan.
COLT, 2018.

Inference in Sparse Graphs with Pairwise Measurements and Side Information

Dylan J. Foster, Daniel Reichman, and Karthik Sridharan.
AISTATS, 2018.

2017

Spectrally-Normalized Margin Bounds for Neural Networks

Peter L. Bartlett, Dylan J. Foster, and Matus J. Telgarsky.
NeurIPS, 2017. Spotlight presentation.

Parameter-free online learning via model selection

Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan.
NeurIPS, 2017. Spotlight presentation.

ZigZag: A new approach to adaptive online learning

Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan.
COLT, 2017.

2016

Learning in Games: Robustness of Fast Convergence

Dylan J. Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Éva Tardos.
NeurIPS, 2016.

2015

Adaptive Online Learning

Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan.
NeurIPS, 2015. Spotlight presentation.

Technical Reports

ℓ_∞ Vector Contraction for Rademacher Complexity

Dylan J. Foster and Alexander Rakhlin.
Technical Report, 2019.

* denotes equal contribution, α denotes alphabetical order.

Dylan Foster