Selected Publications

1. Learning Hidden Markov Models Using Conditional Samples
   with Sham Kakade, Akshay Krishnamurthy and Cyril Zhang
   COLT 2023
   arxiv

2. Computational-Statistical Gaps in Reinforcement Learning
   with Daniel Kane, Sihan Liu and Shachar Lovett
   COLT 2022
   talk | arxiv | tweet

3. Realizable Learning is All You Need
   with Max Hopkins, Daniel Kane and Shachar Lovett
   COLT 2022
   arxiv | tweet

4. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
   with Alekh Agarwal, Sham Kakade and Jason Lee
   COLT 2020
   colt | arxiv

All Publications

Google Scholar

1. Generalized de-Finiti Theorem: Lifting pure state algorithms to mixed states
   with Adam Bene Watts, John Bostanci, Matthias Caro, Daniel Grier and Sihan Liu
   Under submission

2. Improved classical shadows from local symmetries in the Schur basis
   with Daniel Grier and Sihan Liu
   Under submission
   arxiv

3. Do PAC-Learners Learn the Marginal Distribution?
   with Max Hopkins, Daniel Kane and Shachar Lovett
   ALT 2025
   arxiv

4. Learning Hidden Markov Models Using Conditional Samples
   with Sham Kakade, Akshay Krishnamurthy and Cyril Zhang
   COLT 2023
   arxiv

5. Exponential Hardness of Reinforcement Learning with Linear Function Approximation
   with Daniel Kane, Sihan Liu, Shachar Lovett, Csaba Szepesvari and Gillert Weisz
   COLT 2023
   arxiv

6. Computational-Statistical Gaps in Reinforcement Learning
   with Daniel Kane, Sihan Liu and Shachar Lovett
   COLT 2022
   arxiv | tweet

7. Realizable Learning is All You Need
   with Max Hopkins, Daniel Kane and Shachar Lovett
   COLT 2022
   arxiv | tweet

8. Learning What To Remember
   with Robi Bhattacharjee
   ALT 2022
   arxiv

9. Convergence of online k-means
   with Sanjoy Dasgupta and Geelon So
   AISTATS 2022
   arxiv

10. Bilinear Classes: A Structural Framework for Provable Generalization in RL
    with Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Wen Sun and Ruosong Wang
    ICML 2021 (Long Talk)
    icml | arxiv | tweet

11. On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
    with Alekh Agarwal, Sham Kakade and Jason Lee
    JMLR 2021
    jmlr | arxiv

12. Point Location and Active Learning: Learning Halfspaces Almost Optimally
    with Max Hopkins, Daniel Kane and Shachar Lovett
    FOCS 2020
    focs | arxiv

13. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
    with Alekh Agarwal, Sham Kakade and Jason Lee
    COLT 2020
    colt | arxiv

14. Noise-tolerant, Reliable Active Classification with Comparison Queries
    with Max Hopkins, Daniel Kane and Shachar Lovett
    COLT 2020
    arxiv

15. Q-learning with Function Approximation in Deterministic Systems
    with Simon Du Jason Lee and Ruosong Wang
    NeurIPS 2020
    arxiv

Talks

1. Computational-Statistical Gaps in Reinforcement Learning: (talk) (slides)
   Microsoft Research New York Seminar
   Yale Foundations of Data Science Seminar
   EnCORE Fall Retreat
   TTIC Machine Learning Seminar Series
   UCLA Big Data and Machine Learning weekly seminar
   Brown Robotics Group (George Konidaris's group)
   Berkeley RL Reading Group (Jiantao Jiao's group)

2. Equivalence between Realizable and Agnostic Learning: (slides)
   Cornell Theory Seminar
   MSR New York ML Reading Group

3. Theory of Generalization in Reinforcement Learning: (slides)
   RL Theory Seminar
   UCSD AI Seminar
   UCSD Theory Seminar