MARC

 008260126s2025        us                              c    eng  d
■001000017357203
■00520260202103147
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798314865866
■035    ▼a(MiAaPQ)AAI31995839
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aElumar,  Eray  Can.▼0(orcid)0000-0002-2929-3690
■24510▼aMulti-Armed  Bandits  With  Probes  and  Knapsacks:  Algorithms,  Theory  and  Applications
■260    ▼a[Sl]▼bCarnegie  Mellon  University▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a173  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  86-11,  Section:  B.
■500    ▼aAdvisor:  Yagan,  Osman.
■5021  ▼aThesis  (Ph.D.)--Carnegie  Mellon  University,  2025.
■520    ▼aThe  multi-armed  bandit  (MAB)  framework  is  a  fundamental  paradigm  in  decision  theory  and  machine  learning,  in  which  a  decision-maker  sequentially  selects  one  of  K  available  actions  at  each  round,  with  the  objective  of  maximizing  the  cumulative  reward  over  time.  The  main  challenge  lies  in  balancing  exploration  of  new  actions  with  exploitation  of  known  ones-an  essential  trade-off  for  making  optimal,  data-driven  decisions  in  complex,  uncertain  environments  with  limited  information,  such  as  clinical  trials,  online  advertising,  and  recommendation  systems.  Motivated  by  these  challenges  and  applications,  we  propose  and  analyze  two  different  multi-armed  bandit  models  with  broad  practical  relevance,  which  are  i)  bandits  with  probes,  and  ii)  bandits  with  anytime  knapsacks.  Additionally,  we  focus  on  utilizing  the  multi-armed  bandit  framework  in  iii)  dataset  labeling  with  LLMs  (large  language  models).First,  we  study  the  MAB  model  with  probes,  where  before  pulling  an  arm,  the  decision-maker  is  allowed  to  probe  one  arm  at  an  associated  cost  to  observe  its  reward  for  that  round.  Based  on  the  probe's  outcome,  the  decision-maker  can  choose  to  pull  the  probed  arm  or  any  other  arm.  Alternatively,  an  arm  may  be  pulled  directly  without  employing  the  probe.  This  variation  is  of  particular  interest  due  to  its  extensive  range  of  applications,  including  online  learning  augmented  with  machine  learning  advice,  hyper-parameter  optimization  for  machine  learning  models,  and  wireless  communications.  The  introduction  of  the  probing  mechanism  significantly  expands  the  action  space,  adding  complexity  to  the  problem,  as  the  decision-maker  must  judiciously  balance  exploration  and  exploitation  while  also  considering  whether  to  probe  an  arm.  To  address  these  challenges,  we  propose  a  novel  algorithm  that  efficiently  determines  the  optimal  action  in  each  round  to  maximize  the  cumulative  reward.  Through  rigorous  analysis,  we  derive  a  theoretical  gap-independent  regret  bound  on  the  order  of  O(  √  T),  and  a  gap-dependent  regret  bound  on  the  order  of  O(log  T);  and  demonstrate  the  empirical  performance  of  our  algorithm  through  simulation  results.Secondly,  we  study  the  MAB  model  with  anytime  knapsacks.  This  model  is  similar  to  the  bandits  with  knapsacks  (BwK)  problem,  however,  there  is  an  anytime  constraint  on  the  average  cost  instead  of  a  fixed  total  cost  budget.  This  formulation  finds  broad  applications  in  areas  including  inventory  management,  online  advertising,  and  portfolio  management.  We  propose  an  algorithm  that  employs  upper  confidence  bounds  to  efficiently  explore  the  decision  space  while  strategically  under-utilizing  the  available  budget  to  reduce  the  number  of  rounds  that  need  to  be  skipped  to  satisfy  the  anytime  cost  constraint.  We  derive  theoretical  gap-dependent  regret  bounds  and  demonstrate  that,  despite  the  increased  constraints  relative  to  the  standard  BwK  model,  our  formulation  achieves  the  same  gap-dependent  regret  bounds  of  O(log  T).  We  provide  simulation  results  to  corroborate  the  theoretical  findings  and  illustrate  the  empirical  performance  of  the  proposed  algorithm.Lastly,  to  illustrate  the  practical  utility  of  the  MAB  framework  in  the  newest  problem  settings,  we  examine  the  task  of  labeling  a  dataset  using  different  LLMs.  In  this  scenario,  we  have  access  to  various  LLMs,  each  with  distinct  costs  and  capabilities,  and  a  model  capable  of  extracting  contextual  information  from  individual  data  instances.  We  propose  an  algorithm  that  leverages  this  context  information  to  select  a  subset  of  LLMs,  as  opposed  to  traditional  weighted  majority  voting  methods  that  query  all  available  LLMs  for  each  label.  We  demonstrate  the  utility  of  our  proposed  algorithm  in  this  problem  setting  with  simulation  results.
■590    ▼aSchool  code:  0041.
■650  4▼aComputer  science
■650  4▼aStatistics
■650  4▼aComputer  engineering
■650  4▼aElectrical  engineering
■653    ▼aMulti-armed  bandits
■653    ▼aOnline  learning
■653    ▼aStatistical  decision  theory
■690    ▼a0984
■690    ▼a0463
■690    ▼a0464
■690    ▼a0544
■71020▼aCarnegie  Mellon  University▼bElectrical  and  Computer  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g86-11B.
■790    ▼a0041
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17357203▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서