<div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div><div dir="ltr"><div><div><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><font face="arial, sans-serif"> Wednesday</font><span class="gmail_default" style="font-family:arial,sans-serif">, August 17th</span><font face="arial, sans-serif"> at</font><b><font face="arial, sans-serif"> </font><span style="background-color:rgb(255,255,0)"><font face="verdana, sans-serif">11:00 am CT</font></span></b></font></font></div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where: </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><br></div><div><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap"> via Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=294c5b73-bf11-476a-8690-aef000154634" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></div><div><br></div><div><div dir="ltr"><div><div><div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Aadirupa Saha, TTIC</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><b style="letter-spacing:normal;color:rgb(34,34,34)">Title: </b><span style="letter-spacing:normal;color:rgb(34,34,34)"> Learning to Make Context-Dependent Predictions Through Preference Elicitation </span>
</font></p><div dir="ltr"><font face="arial, sans-serif"><b>Abstract:</b> Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: "Do you prefer Item A over B?", rather than their absolute counterparts: ``How much do you score items A and B on a scale of [0-10]?".</font></div><div dir="ltr"><font face="arial, sans-serif"><br>Drawing inspirations and with the hope of building cost-effective user-friendly systems, this led to the famous formulation of Dueling Bandits (DB) [Yue&Joachims'11], which was followed by a huge surge of interest in the online learning from pairwise preferences in the Bandits-Online ML community. While the setting could be extremely useful in diverse fields of real-life applications, starting from recommendation systems, to crowd-sourcing platforms, to search-engine optimization, online retail, or even more complex tasks like designing multi-player games or training chat-bots/ humanoid robots, just to name a few, unfortunately, the existing DB techniques were predominantly limited only to the simpler settings of only pairwise-preferences, finite decision spaces, and stochastic environments, which are clearly unrealistic from a practical standpoint.<br><br>In this work, we studied the practical framework of contextual dueling bandits where the goal of the learner is to make customized predictions based on the users' need (or user context). More formally, we study the K-armed contextual dueling bandit problem, which is a sequential decision making setting where the learner uses the contextual information to make two decisions, but only observes <i>preference-based (relative) feedback</i> suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class F. We provide a new algorithm that achieves the optimal regret rate for a new notion of `best response' regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over F. This resolves an open problem of Dudík et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits. We will conclude the talk with a brief overview of the potential of bringing preference-based learning into real-world systems.</font></div><div dir="ltr"><font face="arial, sans-serif"><br></font></div><div dir="ltr"><font face="arial, sans-serif"><span style="white-space:pre-wrap">(based on the joint work with Akshay Krishnamurthy, "Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability", ALT 2022).</span><br><br><b>Speaker Bio:</b> Aadirupa is visiting faculty at TTI Chicago. Before this, she was a postdoctoral researcher at Microsoft Research New York City. She obtained her Ph.D. from the Department of Computer Science, Indian Institute of Science, Bangalore, advised by Aditya Gopalan and Chiranjib Bhattacharyya. Aadirupa was an intern at Microsoft Research, Bangalore, Inria, Paris, and Google AI, Mountain View. </font><span style="font-family:arial,sans-serif">Her research interests include Bandits, Reinforcement Learning, Optimization, Learning theory, Algorithms. Off late, she is also very interested in working on problems in the intersection of ML and Game theory, Algorithmic fairness, and Privacy.</span></div><div><br></div></div></div></div></div></div></div></div></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;color:rgb(80,0,80);font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div></div></div></div><br></div><div><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Aug 17, 2022 at 10:00 AM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div dir="ltr"><div><div><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><font face="arial, sans-serif"> Wednesday</font><span class="gmail_default" style="font-family:arial,sans-serif">, August 17th</span><font face="arial, sans-serif"> at</font><b><font face="arial, sans-serif"> </font><span style="background-color:rgb(255,255,0)"><font face="verdana, sans-serif">11:00 am CT</font></span></b></font></font></div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where: </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><br></div><div><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap"> via Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=294c5b73-bf11-476a-8690-aef000154634" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></div><div><br></div><div><div dir="ltr"><div><div><div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Aadirupa Saha, TTIC</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><b style="letter-spacing:normal;color:rgb(34,34,34)">Title: </b><span style="letter-spacing:normal;color:rgb(34,34,34)"> Learning to Make Context-Dependent Predictions Through Preference Elicitation </span>
</font></p><div dir="ltr"><font face="arial, sans-serif"><b>Abstract:</b> Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: "Do you prefer Item A over B?", rather than their absolute counterparts: ``How much do you score items A and B on a scale of [0-10]?".</font></div><div dir="ltr"><font face="arial, sans-serif"><br>Drawing inspirations and with the hope of building cost-effective user-friendly systems, this led to the famous formulation of Dueling Bandits (DB) [Yue&Joachims'11], which was followed by a huge surge of interest in the online learning from pairwise preferences in the Bandits-Online ML community. While the setting could be extremely useful in diverse fields of real-life applications, starting from recommendation systems, to crowd-sourcing platforms, to search-engine optimization, online retail, or even more complex tasks like designing multi-player games or training chat-bots/ humanoid robots, just to name a few, unfortunately, the existing DB techniques were predominantly limited only to the simpler settings of only pairwise-preferences, finite decision spaces, and stochastic environments, which are clearly unrealistic from a practical standpoint.<br><br>In this work, we studied the practical framework of contextual dueling bandits where the goal of the learner is to make customized predictions based on the users' need (or user context). More formally, we study the K-armed contextual dueling bandit problem, which is a sequential decision making setting where the learner uses the contextual information to make two decisions, but only observes <i>preference-based (relative) feedback</i> suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class F. We provide a new algorithm that achieves the optimal regret rate for a new notion of `best response' regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over F. This resolves an open problem of Dudík et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits. We will conclude the talk with a brief overview of the potential of bringing preference-based learning into real-world systems.</font></div><div dir="ltr"><font face="arial, sans-serif"><br></font></div><div dir="ltr"><font face="arial, sans-serif"><span style="white-space:pre-wrap">(based on the joint work with Akshay Krishnamurthy, "Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability", ALT 2022).</span><br><br><b>Speaker Bio:</b> Aadirupa is visiting faculty at TTI Chicago. Before this, she was a postdoctoral researcher at Microsoft Research New York City. She obtained her Ph.D. from the Department of Computer Science, Indian Institute of Science, Bangalore, advised by Aditya Gopalan and Chiranjib Bhattacharyya. Aadirupa was an intern at Microsoft Research, Bangalore, Inria, Paris, and Google AI, Mountain View. </font><span style="font-family:arial,sans-serif">Her research interests include Bandits, Reinforcement Learning, Optimization, Learning theory, Algorithms. Off late, she is also very interested in working on problems in the intersection of ML and Game theory, Algorithmic fairness, and Privacy.</span></div><div><br></div></div></div></div></div></div></div></div></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;color:rgb(80,0,80);font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr" class="gmail_attr"><br></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Aug 16, 2022 at 1:06 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div dir="ltr"><div><div><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><font face="arial, sans-serif"> Wednesday</font><span class="gmail_default" style="font-family:arial,sans-serif">, August 17th</span><font face="arial, sans-serif"> at</font><b><font face="arial, sans-serif"> </font><span style="background-color:rgb(255,255,0)"><font face="verdana, sans-serif">11:00 am CT</font></span></b></font></font></div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where: </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><br></div><div><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap"> via Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=294c5b73-bf11-476a-8690-aef000154634" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></div><div><br></div><div><div dir="ltr"><div><div><div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Aadirupa Saha, TTIC</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><b style="letter-spacing:normal;color:rgb(34,34,34)">Title: </b><span style="letter-spacing:normal;color:rgb(34,34,34)"> Learning to Make Context-Dependent Predictions Through Preference Elicitation </span>
</font></p><div dir="ltr"><font face="arial, sans-serif"><b>Abstract:</b> Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: "Do you prefer Item A over B?", rather than their absolute counterparts: ``How much do you score items A and B on a scale of [0-10]?".</font></div><div dir="ltr"><font face="arial, sans-serif"><br>Drawing inspirations and with the hope of building cost-effective user-friendly systems, this led to the famous formulation of Dueling Bandits (DB) [Yue&Joachims'11], which was followed by a huge surge of interest in the online learning from pairwise preferences in the Bandits-Online ML community. While the setting could be extremely useful in diverse fields of real-life applications, starting from recommendation systems, to crowd-sourcing platforms, to search-engine optimization, online retail, or even more complex tasks like designing multi-player games or training chat-bots/ humanoid robots, just to name a few, unfortunately, the existing DB techniques were predominantly limited only to the simpler settings of only pairwise-preferences, finite decision spaces, and stochastic environments, which are clearly unrealistic from a practical standpoint.<br><br>In this work, we studied the practical framework of contextual dueling bandits where the goal of the learner is to make customized predictions based on the users' need (or user context). More formally, we study the K-armed contextual dueling bandit problem, which is a sequential decision making setting where the learner uses the contextual information to make two decisions, but only observes <i>preference-based (relative) feedback</i> suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class F. We provide a new algorithm that achieves the optimal regret rate for a new notion of `best response' regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over F. This resolves an open problem of Dudík et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits. We will conclude the talk with a brief overview of the potential of bringing preference-based learning into real-world systems.</font></div><div dir="ltr"><font face="arial, sans-serif"><br></font></div><div dir="ltr"><font face="arial, sans-serif"><span style="white-space:pre-wrap">(based on the joint work with Akshay Krishnamurthy, "Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability", ALT 2022).</span><br><br><b>Speaker Bio:</b> Aadirupa is visiting faculty at TTI Chicago. Before this, she was a postdoctoral researcher at Microsoft Research New York City. She obtained her Ph.D. from the Department of Computer Science, Indian Institute of Science, Bangalore, advised by Aditya Gopalan and Chiranjib Bhattacharyya. Aadirupa was an intern at Microsoft Research, Bangalore, Inria, Paris, and Google AI, Mountain View. </font><span style="font-family:arial,sans-serif">Her research interests include Bandits, Reinforcement Learning, Optimization, Learning theory, Algorithms. Off late, she is also very interested in working on problems in the intersection of ML and Game theory, Algorithmic fairness, and Privacy.</span></div><div><br></div></div></div></div></div></div></div></div></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;color:rgb(80,0,80);font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr" class="gmail_attr"><br></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Aug 13, 2022 at 10:25 AM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div dir="ltr"><div><div style="font-size:small"><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><font face="arial, sans-serif"> Wednesday</font><span class="gmail_default" style="font-family:arial,sans-serif">, August 17th</span><font face="arial, sans-serif"> at</font><b><font face="arial, sans-serif"> </font><span style="background-color:rgb(255,255,0)"><font face="verdana, sans-serif">11:00 am CT</font></span></b></font></font></div><div style="font-size:small"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where: </font><font color="#000000"> </font></b><font color="#000000"><span>Talk</span> will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> <span>TTIC</span>, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><br></div><div style="font-size:small"><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap"> via Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=294c5b73-bf11-476a-8690-aef000154634" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></div><div style="font-size:small"><br></div><div><div dir="ltr"><div><div><div><div><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Aadirupa Saha, TTIC</p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="font-size:11pt;margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><b style="letter-spacing:normal;color:rgb(34,34,34)">Title: </b><span style="letter-spacing:normal;color:rgb(34,34,34)"> Learning to Make Context-Dependent Predictions Through Preference Elicitation </span>
</font></p><div dir="ltr"><font face="arial, sans-serif"><b>Abstract:</b> Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: "Do you prefer Item A over B?", rather than their absolute counterparts: ``How much do you score items A and B on a scale of [0-10]?".</font></div><div dir="ltr"><font face="arial, sans-serif"><br>Drawing inspirations and with the hope of building cost-effective user-friendly systems, this led to the famous formulation of Dueling Bandits (DB) [Yue&Joachims'11], which was followed by a huge surge of interest in the online learning from pairwise preferences in the Bandits-Online ML community. While the setting could be extremely useful in diverse fields of real-life applications, starting from recommendation systems, to crowd-sourcing platforms, to search-engine optimization, online retail, or even more complex tasks like designing multi-player games or training chat-bots/ humanoid robots, just to name a few, unfortunately, the existing DB techniques were predominantly limited only to the simpler settings of only pairwise-preferences, finite decision spaces, and stochastic environments, which are clearly unrealistic from a practical standpoint.<br><br>In this work, we studied the practical framework of contextual dueling bandits where the goal of the learner is to make customized predictions based on the users' need (or user context). More formally, we study the K-armed contextual dueling bandit problem, which is a sequential decision making setting where the learner uses the contextual information to make two decisions, but only observes <i>preference-based (relative) feedback</i> suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class F. We provide a new algorithm that achieves the optimal regret rate for a new notion of `best response' regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over F. This resolves an open problem of Dudík et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits. We will conclude the talk with a brief overview of the potential of bringing preference-based learning into real-world systems.</font></div><div dir="ltr"><font face="arial, sans-serif"><br></font></div><div dir="ltr"><font face="arial, sans-serif"><span style="white-space:pre-wrap">(based on the joint work with Akshay Krishnamurthy, "Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability", ALT 2022).</span><br><br><b>Speaker Bio:</b> Aadirupa is visiting faculty at TTI Chicago. Before this, she was a postdoctoral researcher at Microsoft Research New York City. She obtained her Ph.D. from the Department of Computer Science, Indian Institute of Science, Bangalore, advised by Aditya Gopalan and Chiranjib Bhattacharyya. Aadirupa was an intern at Microsoft Research, Bangalore, Inria, Paris, and Google AI, Mountain View. </font><span style="font-family:arial,sans-serif">Her research interests include Bandits, Reinforcement Learning, Optimization, Learning theory, Algorithms. Off late, she is also very interested in working on problems in the intersection of ML and Game theory, Algorithmic fairness, and Privacy.</span></div><div style="font-size:small"><br>
</div></div></div></div></div></div></div></div></div></div><div class="gmail_quote" style="font-size:small"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;color:rgb(80,0,80);font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div></div></div><div style="font-size:small"><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div><br></div></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div>
</div>