AI4OPT/ARC Joint Seminar: Dylan Foster, Microsoft Research

*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************

Event Details
  • Date/Time:
    • Thursday October 27, 2022
      12:00 pm - 1:00 pm
  • Location: Atrium in Coda on the 9th floor
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: The Statistical Complexity of Interactive Decision Making

Full Summary: No summary paragraph submitted.

AI4OPT/ARC Joint Seminar

Dylan Foster (Microsoft Research)

Thursday, October 27, 2022, Noon – 1:00 pm

Atrium in Coda on the 9th floor

Also live streamed at: https://gatech.zoom.us/j/99381428980

Title: The Statistical Complexity of Interactive Decision Making

Abstract:  A 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:

  1. a lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit.
  2. a 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.

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

Note: Catered lunch will be served at the seminar. So, please stop by 15 minutes before the seminar to pick up lunch.

---------------------------------------------------------------

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu

Click here to sign up for AI4OPT seminar announcements:  https://lists.isye.gatech.edu/mailman/listinfo/ai4opt-seminars

Additional Information

In Campus Calendar
No
Groups

ARC

Invited Audience
Faculty/Staff, Postdoc, Graduate students, Undergraduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: mb121
  • Workflow Status: Published
  • Created On: Oct 24, 2022 - 10:13am
  • Last Updated: Oct 24, 2022 - 10:13am