[Theory] NOW: 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>*


On Thu, Jun 12, 2025 at 10:36 AM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Wed, Jun 11, 2025 at 5:59 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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>*
>>
>>
>> On Thu, Jun 5, 2025 at 10:00 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *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/20250612/7e63ef24/attachment-0001.html>