{"662483":{"#nid":"662483","#data":{"type":"event","title":"AI4OPT\/ARC Joint Seminar: Dylan Foster, Microsoft Research","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAI4OPT\/ARC Joint Seminar\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EDylan Foster (Microsoft Research)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EThursday, October 27, 2022, Noon \u0026ndash; 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAtrium in Coda on the 9\u003Csup\u003Eth\u003C\/sup\u003E floor\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003EAlso live streamed at: \u003Ca href=\u0022https:\/\/gatech.zoom.us\/j\/99381428980\u0022\u003Ehttps:\/\/gatech.zoom.us\/j\/99381428980\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Statistical Complexity of Interactive Decision Making\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp;\u0026nbsp;\u003C\/strong\u003EA fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. This question is analogous to the classical problem of optimal (supervised) statistical learning, where there are well-known complexity measures (e.g., VC dimension and Rademacher complexity) that govern the statistical complexity of learning. However, characterizing the statistical complexity of interactive learning is substantially more challenging due to the adaptive nature of the problem. In this talk, we will introduce a new complexity measure, the Decision-Estimation Coefficient, which is necessary and sufficient for sample-efficient interactive learning. In particular, we will provide:\u003C\/p\u003E\r\n\r\n\u003Col\u003E\r\n\t\u003Cli\u003Ea lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit.\u003C\/li\u003E\r\n\t\u003Cli\u003Ea unified algorithm design principle, Estimation-to-Decisions, which attains a regret bound matching our lower bound, thereby achieving optimal sample-efficient learning as characterized by the Decision-Estimation Coefficient.\u003C\/li\u003E\r\n\u003C\/ol\u003E\r\n\r\n\u003Cp\u003ETaken together, these results give a theory of learnability for interactive decision making. When applied to reinforcement learning settings, the Decision-Estimation Coefficient recovers essentially all existing hardness results and lower bounds.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003ENote: Catered lunch will be served at the seminar. So, please stop by 15 minutes before the seminar to pick up lunch.\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EClick here to sign up for AI4OPT seminar announcements:\u0026nbsp;\u0026nbsp;\u003Ca href=\u0022https:\/\/lists.isye.gatech.edu\/mailman\/listinfo\/ai4opt-seminars\u0022\u003Ehttps:\/\/lists.isye.gatech.edu\/mailman\/listinfo\/ai4opt-seminars\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Statistical Complexity of Interactive Decision Making"}],"uid":"35702","created_gmt":"2022-10-24 14:13:27","changed_gmt":"2022-10-24 14:13:27","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-10-27T13:00:00-04:00","event_time_end":"2022-10-27T14:00:00-04:00","event_time_end_last":"2022-10-27T14:00:00-04:00","gmt_time_start":"2022-10-27 17:00:00","gmt_time_end":"2022-10-27 18:00:00","gmt_time_end_last":"2022-10-27 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}