<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.EmailStyle18
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri",sans-serif;
mso-ligatures:none;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 70.85pt 70.85pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="SV" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:14.0pt">Welcome to an IDA Machine Learning Seminar on Wednesday, December 6 at 15:15 in Ada Lovelace<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:16.0pt;color:black">Pure Exploration in Bandits with Linear Constraints</span></b><b><span lang="EN-US" style="font-size:16.0pt;color:black"><o:p></o:p></span></b></p>
<p class="MsoNormal"><b><span style="font-size:16.0pt;color:black"><a href="https://research.chalmers.se/person/dubhashi"><span lang="EN-US" style="color:#225785;text-decoration:none">Devdatt Dubhashi</span></a></span></b><b><span lang="EN-US" style="font-size:16.0pt;color:black">,
Professor, Chalmers University of Technology<o:p></o:p></span></b></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:16.0pt;color:black"><o:p> </o:p></span></b></p>
<p class="MsoNormal"><i><span lang="EN-US">Abstract:</span></i><span lang="EN-US"> We address the problem of identifying the optimal policy with fixed confidence in a multi-armed bandit setup, when the arms are subject to linear constraints. Unlike the standard
best-arm identification problem which is well studied, the optimal policy in this case may not be deterministic and could mix between several arms. This changes the geometry of the problem which we characterize via an information-theoretic lower bound. We
introduce two asymptotically optimal algorithms for this setting, one based on the Track-and-Stop method and the other based on a game-theoretic approach. Both these algorithms try to track an optimal allocation based on the lower bound and computed by a weighted
projection onto the boundary of a normal cone. Finally, we provide empirical results that validate our bounds and visualize how constraints change the hardness of the problem.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Location: <b>Ada Lovelace,</b> <a href="https://www.ida.liu.se/department/location/search.en.shtml?keyword=ada">
https://www.ida.liu.se/department/location/search.en.shtml?keyword=ada</a><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">------------------<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">The list of future seminars in the series is available at:
</span><a href="http://www.ida.liu.se/research/machinelearning/seminars/" target="_BLANK2"><span lang="EN-US">http://www.ida.liu.se/research/machinelearning/seminars/</span></a><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">You can subscribe to the seminar series' calendar using this ics link:
<a href="https://outlook.office365.com/owa/calendar/4d811ae47ce446f58d11a7c2f50a7ed8@ad.liu.se/0f5253d7bc7841248c71eb4c28eb2d668927992292494627279/calendar.ics" target="_BLANK2">
https://outlook.office365.com/owa/calendar/4d811ae47ce446f58d11a7c2f50a7ed8@ad.liu.se/0f5253d7bc7841248c71eb4c28eb2d668927992292494627279/calendar.ics</a><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
</body>
</html>