[Theory] Re: [Theory Lunch] Gene Li, Wednesday 5/25 12:30pm-1:30pm, JCL 390.

Wed May 25 10:58:55 CDT 2022

Reminder: happening in 1 hour!
________________________________
From: Theory <theory-bounces at mailman.cs.uchicago.edu> on behalf of Adela DePavia <adepavia at uchicago.edu>
Sent: Monday, May 23, 2022 10:33 AM
To: theory at mailman.cs.uchicago.edu <theory at mailman.cs.uchicago.edu>
Cc: gene at ttic.edu <gene at ttic.edu>
Subject: [Theory] [Theory Lunch] Gene Li, Wednesday 5/25 12:30pm-1:30pm, JCL 390.

Join us for the last Theory Lunch of the 2021-2022 academic year!

Date: May 25th, Wednesday
Time: 12:30pm CT
Location: JCL 390

Speaker: Gene Li<https://urldefense.com/v3/__https://gxli97.github.io/__;!!BpyFHLRN4TMTrA!80yUS6t6ag0R1MhpfNaD14expuypT_ciDOVReh33H6DB3r17tToDUxPXfz6ObSXzGIIXzfOZVbZPLySv7-fD93bDVA$>

Title: Understanding the Eluder Dimension

Zoom: [link<https://urldefense.com/v3/__https://www.google.com/url?q=https*3A*2F*2Fuchicago.zoom.us*2Fj*2F93525953536*3Fpwd*3Db29aMVhMWThxWEZJNGVEN0pUWXd1Zz09&sa=D&ust=1651938555707000&usg=AOvVaw0ToWwB3NYeJ1K6diEsCtJV__;JSUlJSUlJQ!!BpyFHLRN4TMTrA!80yUS6t6ag0R1MhpfNaD14expuypT_ciDOVReh33H6DB3r17tToDUxPXfz6ObSXzGIIXzfOZVbZPLySv7-eDkHE65Q$>]

Abstract: Russo and Van Roy introduced the notion of eluder dimension for a function class and used it to analyze algorithms for the multi-armed bandit problem with function approximation. Since then, eluder dimension has been extensively used to construct and analyze the regret of algorithms for bandits and reinforcement learning with function approximation. Despite widespread use, little is known about when the eluder dimension is bounded.

This talk presents several new insights on the eluder dimension. We will focus on the so-called combinatorial eluder dimension. We prove an equivalence relationship with two other familiar learning-theoretic quantities, the star number and the threshold dimension. We also discuss separations between eluder dimension and sign-rank.

Based on joint work with Pritish Kamath, Dylan Foster, and Nathan Srebro.

COVID Policy: As per university policy, masking is not currently required for in-person attendance. Please note that we will have fully masked and social-distanced tables available to accommodate any attendees who would prefer such arrangements. Please contact us if you have any questions or feedback.

[Theory Lunch Webpage<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$>]
[Theory Lunch Calendar<https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$>]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220525/7ad1fd58/attachment-0001.html>