Dylan Foster

Preprints/Under Review

1. 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.
   2024. [Audrey's talk]

2. 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.
   2024.

3. The Statistical Complexity of Interactive Decision Making
   

   Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin.
   2021.

2024

4. 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. [Phil's talk]

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

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

6. The Power of Resets in Online Reinforcement Learning
   

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

7. 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, and Yunbei Xu.
   NeurIPS 2024. Spotlight presentation.

8. Can Large Language Models Explore In-Context?
   

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

9. Online Estimation via Offline Estimation: An Information-Theoretic Framework
   

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

10. Scalable Online Exploration via Coverability
    

    Philip Amortila, Dylan J. Foster, and Akshay Krishnamurthy.
    ICML 2024.

11. Rich-Observation Reinforcement Learning with Continuous Latent Dynamics
    

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

12. Harnessing Density Ratios for Online Reinforcement Learning
    

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

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

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

2023

14. Efficient Model-Free Exploration in Low-Rank MDPs
    

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

15. Model-Free Reinforcement Learning with the Decision-Estimation Coefficient
    

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

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

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

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

    Andrew Wagenmaker and Dylan J. Foster.
    COLT 2023.

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

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

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

    Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J. Foster.
    COLT 2023.

20. 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.

21. Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games
    

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

22. 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.

23. Orthogonal Statistical Learning
    

    Dylan J. Foster and Vasilis Syrgkanis.
    Annals of Statistics, 2023.
    Conference version appeared at COLT 2019 as "Statistical Learning with a Nuisance Component".

24. Minimax Rates for Conditional Density Estimation via Empirical Entropy
    

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

25. 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.

2022

26. 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.

27. 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.

28. Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information
    

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

29. On the Complexity of Adversarial Decision Making
    

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

30. Understanding the Eluder Dimension
    

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

31. Interaction-Grounded Learning with Action-Inclusive Feedback
    

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

32. Contextual Bandits with Large Action Spaces: Made Practical
    

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

2021

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

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

34. 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

35. 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.

36. Adapting to Misspecification in Contextual Bandits
    

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

37. Independent Policy Gradient Methods for Competitive Reinforcement Learning
    

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

38. Beyond UCB: Optimal and Efficient Contextual Bandits
    with Regression Oracles
    

    Dylan J. Foster and Alexander Rakhlin.
    ICML 2020.
    Best spotlight talk, 14th Annual New York Academy of Science ML Symposium.
    Now in Vowpal Wabbit! Use the --squarecb option or see here for more information.

39. Logarithmic Regret for Adversarial Online Control
    

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

40. Naive Exploration is Optimal for Online LQR
    

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

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

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

42. 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.
    

43. Open Problem: Model Selection for Contextual Bandits
    

    Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo.
    COLT 2020 Open Problem.
    

44. Learning Nonlinear Dynamical Systems from a Single Trajectory
    

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

2019

45. Model Selection for Contextual Bandits
    

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

46. Hypothesis Set Stability and Generalization
    

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

47. Distributed Learning with Sublinear Communication
    

    Jayadev Acharya, Christopher De Sa, Dylan J. Foster, and Karthik Sridharan.
    ICML 2019. Long talk.
    Best spotlight talk, 13th Annual New York Academy of Science ML Symposium.

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

    Dylan J. Foster and Andrej Risteski.
    COLT 2019.
    

49. 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.
    

50. Statistical Learning with a Nuisance Component
    

    Dylan J. Foster and Vasilis Syrgkanis.
    COLT 2019. Best Paper Award.
    Extended abstract for Orthogonal Statistical Learning.
    Short version appeared in Sister Conference Best Paper Track at IJCAI 2020.

2018

51. Contextual Bandits with Surrogate Losses: Margin Bounds
    and Efficient Algorithms
    

    Dylan J. Foster and Akshay Krishnamurthy.
    NeurIPS 2018.
    

52. Uniform Convergence of Gradients for Non-Convex
    Learning and Optimization
    

    Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan.
    NeurIPS 2018. Short version at ICML 2018 Nonconvex Optimization workshop.
    

53. 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.

54. 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.
    

55. Online Learning: Sufficient Statistics and the Burkholder Method
    

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

56. Inference in Sparse Graphs with Pairwise Measurements
    and Side Information
    

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

2017

57. Parameter-Free Online Learning via Model Selection
    

    Dylan J. Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan.
    NeurIPS 2017. Spotlight presentation.
    

58. Spectrally-Normalized Margin Bounds for Neural Networks
    

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

59. ZigZag: A New Approach to Adaptive Online Learning
    

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

2016

60. Learning in Games: Robustness of Fast Convergence
    

    Dylan J. Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Éva Tardos.
    NeurIPS 2016. Preliminary version at Ad Auctions workshop at EC 2016.
    

2015

61. Adaptive Online Learning
    

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

Technical Reports and Notes

62. ℓ_∞ Vector Contraction for Rademacher Complexity
    

    Dylan J. Foster and Alexander Rakhlin
    Technical note.
    2019.