[Theory] 6/12 Talks at TTIC: Idan Attias, IDEAL Institute

[Mary Marre via Theory]

*When*:    Thursday, June 12, 2025 at* 11:00** am** CT *

*Where*:   Talk will be given *live, in-person* at
               TTIC, 6045 S. Kenwood Avenue
               5th Floor, *Room 530*

*Virtually*: via Panopto (livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=3086c76d-1016-42fc-98e4-b2f4002cb7d3>
)

*Who:  *    Idan Attias, IDEAL Institute


*Title: *Multi-Armed Bandits: Adaptivity to Causal Structure and
Capacity-Constrained Learning with Delays
*Abstract: *First part - We investigate the problem of adapting to the
presence or absence of causal structure in multi-armed bandit problems. In
addition to the usual reward signal, we assume the learner has access to
additional variables, observed in each round after acting. When these
variables d-separate the action from the reward, existing work in causal
bandits demonstrates that one can achieve strictly better rates of regret.
Our goal is to adapt to this favorable “conditionally benign” structure if
it is present in the environment, while simultaneously recovering
worst-case minimax regret if it is not. Notably, the learner has no prior
knowledge of whether the favorable structure holds. In this paper, we
establish the Pareto optimal frontier of adaptive rates.

Based on joint work with Ziyi Liu and Dan Roy, presented at ICML 2024.

Second part - We study online learning with delays under a novel “capacity
constraint” that limits how many past rounds can be tracked simultaneously
for delayed feedback. Under “clairvoyance” (i.e., delay durations are
revealed upfront each round) and/or “preemptibility” (i.e., we have ability
to stop tracking previously chosen round feedback), we establish matching
upper and lower bounds (up to logarithmic terms) on achievable regret,
characterizing the “optimal capacity” needed to match the minimax rates of
classical delayed online learning, which implicitly assume unlimited
capacity. Our algorithms achieve minimax-optimal regret across all capacity
levels, with performance gracefully degrading under suboptimal capacity.

Based on joint work with Alexander Ryabchenko and Dan Roy, to appear at
COLT 2025.

*Bio: *Idan Attias is a postdoctoral researcher at the IDEAL Institute,
working with Lev Reyzin (UIC) and Avrim Blum (TTIC). His primary research
interests lie in the foundations of machine learning theory and data-driven
sequential decision-making, with intersections in game theory, private data
analysis, optimization, information theory, and theoretical computer
science. He has published several papers in top machine learning and
theoretical computer science venues. His work has been recognized with
multiple Oral and Spotlight presentations. Most recently, he received the
ICML 2024 Best Paper Award and was selected as a Rising Star in Data
Science.

*Host: *Avrim Blum <avrim at ttic.edu>




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250605/7b95e077/attachment.html>