MARC

 008260126s2022        us                              c    eng  d
■001000017360497
■00520260202105536
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798263397593
■035    ▼a(MiAaPQ)AAI32314829
■035    ▼a(MiAaPQ)GeorgiaTech66568
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a621.3
■1001  ▼aChen,  Zaiwei.
■24512▼aA  Unified  Lyapunov  Framework  for  Finite-Sample  Analysis  of  Reinforcement  Learning  Algorithms
■260    ▼a[Sl]▼bGeorgia  Institute  of  Technology▼c2022
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2022
■300    ▼a297  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-06,  Section:  B.
■500    ▼aAdvisor:  Maguluri,  Siva  Theja;Clarke,  John  Paul.
■5021  ▼aThesis  (Ph.D.)--Georgia  Institute  of  Technology,  2022.
■520    ▼aReinforcement  learning  is  a  framework  for  solving  sequential  decision-making  problems  without  requiring  the  environmental  model,  and  is  viewed  as  a  promising  approach  to  achieve  artificial  intelligence.  However,  there  is  a  huge  gap  between  the  empirical  successes  and  the  theoretical  understanding  of  reinforcement  learning.  In  this  thesis,  we  make  an  effort  to  bridging  such  gap.More  formally,  this  thesis  focuses  on  designing  data-efficient  reinforcement  learning  algorithms  and  establishing  their  finite-sample  guarantees.  Specifically,  we  aim  at  answering  the  following  question:  suppose  we  carry  out  some  reinforcement  learning  algorithm  with  finite  amount  of  samples  (or  with  finite  number  of  iterations),  then  what  can  we  say  about  the  performance  of  the  output  of  the  algorithm?  The  more  detailed  motivation  and  the  research  background  are  presented  in  Chapter  1.Part  I:  Stochastic  Approximation.  The  main  body  of  this  thesis  is  divided  into  three  parts.  In  the  first  part  of  the  thesis,  we  focus  on  studying  the  stochastic  approximation  method.  Stochastic  approximation  is  the  major  workhorse  for  large-scale  optimization  and  machine  learning,  and  is  widely  used  in  reinforcement  learning  for  both  algorithm  design  and  algorithm  analysis.  Therefore,  understanding  the  behavior  of  SA  algorithms  is  of  fundamental  interest  to  the  analysis  of  RL  algorithms.In  Chapter  2  and  Chapter  3,  we  consider  Markovian  stochastic  approximation  under  a  contractive  operator  and  under  a  strongly  pseudo-monotone  operator,  and  establish  their  finite-sample  guarantees.  These  two  results  on  stochastic  approximation  are  used  in  later  parts  of  the  thesis  to  study  reinforcement  learning  algorithms  with  a  tabular  representation  and  with  linear  function  approximation.  The  main  technique  we  use  to  analyze  those  stochastic  approximation  algorithms  is  the  Lyapunov-drift  method.  Specifically,  we  construct  novel  Lyapunov  functions  (e.g.,  generalized  Moreau  envelope  in  the  case  of  stochastic  approximation  under  a  contraction  assumption)  to  capture  the  dynamics  of  the  corresponding  stochastic  approximation  algorithms,  and  control  the  discretization  error  and  the  stochastic  error.  This  enables  us  to  derive  the  one-step  drift  inequality,  which  can  be  repeatedly  used  to  establish  the  finite-sample  bounds.In  Chapter  4,  we  switch  our  focus  from  finite-sample  analysis  to  asymptotic  analysis,  and  characterize  the  stationary  distribution  of  the  centered-scaled  iterates  of  several  popular  stochastic  approximation  algorithms.  Specifically,  we  show  that  for  stochastic  gradient  descent,  linear  stochastic  approximation,  and  contractive  stochastic  approximation,  the  stationary  distribution  of  the  centered  iterates  (after  proper  scaling)  is  a  Gaussian  distribution  with  mean  zero  and  a  covariance  matrix  being  the  unique  solution  of  an  appropriate  Lyapunov  equation.  For  stochastic  approximation  beyond  these  three  types,  we  numerically  demonstrate  that  the  stationary  distribution  may  not  be  Gaussian  in  general.  The  main  technique  we  used  for  such  asymptotic  analysis  is  also  Lyapunov  method,  where  the  characteristic  function  was  used  as  the  test  function.Part  II:  Reinforcement  Learning  with  a  Tabular  Representation.  In  the  second  part  of  this  thesis,  we  focus  on  reinforcement  learning  with  a  tabular  representation.  The  preliminaries  of  reinforcement  learning  are  presented  in  Chapter  5.In  Chapter  6  and  Chapter  7,  we  consider  the  TD-learning  algorithm  for  solving  the  policy  evaluation  problem,  which  refers  to  the  problem  of  estimating  the  performance  of  a  given  policy.  Solving  the  policy  evaluation  problem  is  an  important  intermediate  step  in  the  popular  actor-critic  framework  for  ultimately  finding  an  optimal  policy.  More  specifically,  we  consider  on-policy  TD-learning  algorithms  such  as  n-step  TD  and  TD(λ)  in  Chapter  6.  By  establishing  finite-sample  guarantees  of  n-step  TD  and  TD(λ)  as  explicit  functions  of  the  parameters  n  and  λ,  we  provide  theoretical  insight  into  the  open  problem  about  the  efficiency  of  bootstrapping,  which  is  about  how  to  choose  the  parameters  n  and  λ  so  that  n-step  TD  and  TD(λ)  achieve  their  best  performance.In  Chapter  7,  we  study  the  problem  of  policy  evaluation  using  off-policy  sampling,  where  the  policy  used  to  collect  samples  and  the  policy  whose  value  function  we  aim  at  estimating  is  different.  We  provide  finite-sample  analysis  of  a  generic  off-policy  multi-step  TD-learning  algorithm,  which  subsumes  several  popular  existing  algorithms  such  as  Qπ  (λ),  Tree-Backup(λ),  Retrace(λ),  and  V  -trace  as  its  special  cases.  In  addition,  our  finite-sample  bounds  demonstrate  a  trade-off  between  the  variance  (which  arises  due  to  the  product  of  the  importance  sampling  ratios)  and  the  bias  in  the  limit  point  (which  arises  due  to  various  modifications  to  the  importance  sampling  ratios).  Understanding  such  bias-variance  trade-off  is  at  the  heart  of  off-policy  learning.
■590    ▼aSchool  code:  0078.
■650  4▼aComputer  engineering
■653    ▼aDecision-making
■653    ▼aReinforcement  learning
■690    ▼a0464
■71020▼aGeorgia  Institute  of  Technology.
■7730  ▼tDissertations  Abstracts  International▼g87-06B.
■790    ▼a0078
■791    ▼aPh.D.
■792    ▼a2022
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360497▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서