Back to Upcoming EventsThis Event has Passed

FDS Seminar: Gaurav Mahajan (UCSD)

Friday, January 13, 2023    
1:00PM – 2:00PM

“Computational-Statistical Gaps in Reinforcement Learning”

Speaker: Gaurav Mahajan (UCSD)

Abstract: A fundamental assumption in theory of reinforcement learning is “RL with linear function approximation”. Under this assumption, the optimal value function (either Q*, or V*, or both) can be obtained as the linear combination of finitely many known basis functions. Even though it was observed as early as 1963 that there are empirical benefits of using linear function approximation, only recently a series of work designed sample efficient algorithms for this setting. These works posed an important open problem: Can we design polynomial time algorithms for this setting?   In this talk, I will go over recent progress on this open problem: a surprising computational-statistical gap in reinforcement learning. Even though we have polynomial sample complexity algorithms, under standard hardness assumption (NP != RP) there are no polynomial time algorithms for this setting. I will start by going over a few algorithmic ideas for designing sample efficient algorithms in RL and then move on to show how to build hard MDPs which satisfy linear function approximation assumption from hard 3-SAT instances. I will end the talk by discussing a few open problems in RL and sequence modelling.

Remote presentation only.

Join from PC, Mac, Linux, iOS or Android:
Or Telephone:203-432-9666 (2-ZOOM if on-campus) or 646 568 7788
One Tap Mobile: +12034329666,,94359913798# US (Bridgeport)

Meeting ID: 943 5991 3798
International numbers available:


Submit an Event

Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.

Submit an Event

Share your event ideas with us using the form below.

"*" indicates required fields

MM slash DD slash YYYY
Start Time*
End Time*