Current Research Interests

1. Reinforcement Learning Theory e.g. computational lower bounds in reinforcement learning [COLT 22, COLT 23]

2. Distribution Learning e.g. computationally efficient algorithm for learning hidden markov models [COLT 23]

3. Quantum Information Theory e.g. role of entangled measurements in learning quantum states

4. Discrepancy Theory e.g. discrepancy of column sparse matrices

Selected Publications

1. Learning Hidden Markov Models Using Conditional Samples
   with S.M. Kakade, A. Krishnamurthy and C. Zhang
   COLT 2023
   arxiv

2. Exponential Hardness of Reinforcement Learning with Linear Function Approximation
   with D. Kane, S. Liu, S. Lovett, C. Szepesvari and G. Weisz
   COLT 2023
   arxiv

3. Computational-Statistical Gaps in Reinforcement Learning
   with D. Kane, S. Lui and S. Lovett
   COLT 2022
   talk | arxiv | tweet

4. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
   with A. Agarwal, S. M. Kakade, J. D. Lee
   COLT 2020
   colt | arxiv

All Publications

1. Do PAC-Learners Learn the Marginal Distribution?
   with M. Hopkins, D. Kane, S. Lovett
   Preprint
   arxiv

2. Learning Hidden Markov Models Using Conditional Samples
   with S.M. Kakade, A. Krishnamurthy and C. Zhang
   COLT 2023
   arxiv

3. Exponential Hardness of Reinforcement Learning with Linear Function Approximation
   with D. Kane, S. Liu, S. Lovett, C. Szepesvari and G. Weisz
   COLT 2023
   arxiv

4. Computational-Statistical Gaps in Reinforcement Learning
   with D. Kane, S. Lui and S. Lovett
   COLT 2022
   arxiv | tweet

5. Realizable Learning is All You Need
   with M. Hopkins, D. Kane and S. Lovett
   COLT 2022
   arxiv | tweet

6. Point Location and Active Learning: Learning Halfspaces Almost Optimally
   with M. Hopkins, D. Kane, S. Lovett
   FOCS 2020
   focs | arxiv

7. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
   with A. Agarwal, S. M. Kakade, J. D. Lee
   COLT 2020
   colt | arxiv

8. Noise-tolerant, Reliable Active Classification with Comparison Queries
   with M. Hopkins, D. Kane, S. Lovett
   COLT 2020
   arxiv

9. Learning What To Remember
   with R. Bhattacharjee
   ALT 2022
   arxiv

10. Convergence of online k-means
    with S. Dasgupta, G. So
    AISTATS 2022
    arxiv

11. Bilinear Classes: A Structural Framework for Provable Generalization in RL
    with S. S. Du, S. M. Kakade, J. D. Lee, S. Lovett, W. Sun, R. Wang
    ICML 2021 (Long Talk)
    icml | arxiv | tweet

12. On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
    with A. Agarwal, S. M. Kakade, J. D. Lee
    JMLR 2021
    jmlr | arxiv

13. Q-learning with Function Approximation in Deterministic Systems
    with S. S. Du, J. D. Lee, R. 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