MARC

 008260126s2025        us                              c    eng  d
■001000017358464
■00520260202104706
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798288866678
■035    ▼a(MiAaPQ)AAI32117150
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a519
■1001  ▼aLi,  Xinyu.
■24513▼aAn  α-Potential  Game  Framework  for  Non-Cooperative  Dynamic  Games:  Theory  and  Algorithms
■260    ▼a[Sl]▼bUniversity  of  California,  Berkeley▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a164  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-01,  Section:  B.
■500    ▼aAdvisor:  Guo,  Xin.
■5021  ▼aThesis  (D.Eng.)--University  of  California,  Berkeley,  2025.
■520    ▼aMulti-agent  systems  naturally  arise  in  many  real-world  scenarios  where  multiple  decision-makers  interact,  such  as  autonomous  driving,  network  design,  and  financial  markets.  Analyzing  multi-agent  non-cooperative  games  is  inherently  challenging  due  to  the  asymmetry  among  players  and  the  diverse  structures  of  the  games.  This  thesis  introduces  a  unified  framework  to  analyze  N-player  non-cooperative  games  in  dynamic  settings,  considering  both  discrete-time  and  continuous-time  state  transitions.  Additionally,  efficient  reinforcement  learning  (RL)  algorithms  and  stochastic  control  techniques  are  proposed  to  identify  strategies  for  each  player  that  lead  to  approximate  Nash  equilibria  (NE).The  first  part  of  this  thesis  introduces  and  analyzes  a  general  class  of  dynamic  N-player  non-cooperative  games  called  α-potential  games.  In  this  framework,  the  change  in  a  player's  objective  function  resulting  from  a  unilateral  deviation  from  her  strategy  is  equal  to  the  change  in  a  common  function,  called  the  α-potential  function,  up  to  an  error  α.  The  existence  of  an  α-potential  function  simplifies  the  challenging  task  of  finding  α-Nash  equilibria  in  dynamic  games  to  minimizing  the  α-potential  function,  as  the  optimizer  of  the  α-potential  function  is  shown  to  be  an  α-Nash  equilibrium  of  the  game.In  Chapter  2,  we  focus  on  Markov  games  with  finite  state  space,  finite  action  space,  and  Markovian  policy.  The  state  transition  follows  a  discrete-time  Markov  decision  process.  In  this  case,  we  establish  the  existence  of  an  associated  α-potential  function.  Additionally,  we  provide  a  semi-infinite  linear  program  to  find  α  and  its  corresponding  α-potential  function  for  any  Markov  game.  We  study  two  important  classes  of  practically  significant  Markov  games,  Markov  congestion  games  and  the  perturbed  Markov  team  games,  via  the  framework  of  Markov  α-potential  games,  with  explicit  characterization  of  an  upper  bound  for  α  and  its  relation  to  game  parameters.  Furthermore,  we  study  two  equilibrium  approximation  algorithms,  namely  the  projected  gradient-ascent  algorithm  and  the  sequential  maximum  improvement  algorithm,  along  with  their  Nash  regret  analysis,  and  corroborate  the  results  with  numerical  experiments  using  model-free  RL  algorithms.In  Chapter  3,  we  study  dynamic  games  with  continuous-time  state  transitions,  focusing  on  general  classes  of  states,  actions,  and  controls/policies,  with  a  particular  emphasis  on  stochastic  differential  games.  An  analytical  characterization  of  the  α-potential  function  is  established,  with  α  represented  in  terms  of  the  magnitude  of  the  asymmetry  of  the  second-order  derivatives  of  the  players'  objective  functions.  For  stochastic  differential  games  in  which  the  state  dynamic  is  a  controlled  diffusion,  α  is  characterized  in  terms  of  the  number  of  players,  the  choice  of  admissible  strategies,  and  the  intensity  of  interactions  and  the  level  of  heterogeneity  among  players.  Two  classes  of  stochastic  differential  games,  namely  distributed  games  and  games  with  mean  field  interactions,  are  analyzed  to  highlight  the  dependence  of  α  on  general  game  characteristics.  To  analyze  the  α-NE,  the  associated  optimization  problem  is  embedded  into  a  conditional  McKean-Vlasov  control  problem.  A  verification  theorem  is  established  to  construct  α-NE  based  on  solutions  to  an  infinite-dimensional  Hamilton-Jacobi-Bellman  equation,  which  is  reduced  to  a  system  of  ordinary  differential  equations  for  linear-quadratic  (LQ)  games.  We  conclude  by  case-studying  an  N-player  LQ  game  on  a  graph  network,  analyzing  α  under  different  graph  structures,  and  deriving  the  explicit  solutions  to  the  α-NE. Since  our  framework  reduces  multi-agent  games  to  a  single  optimization  problem,  the  second  part  of  this  thesis  focuses  on  designing  efficient  algorithms  for  single-agent  reinforcement  learning  (RL).  While  much  progress  has  been  made  in  RL  for  discrete  Markov  decision  processes,  continuous  RL  remains  less  explored.  Therefore,  in  Chapter  4,  we  propose  and  analyze  two  new  policy  learning  methods:  regularized  policy  gradient  (RPG)  and  iterative  policy  optimization  (IPO),  for  a  class  of  discounted  linear-quadratic  control  (LQC)  problems  with  continuous  state  space  and  continuous  action  space,  over  an  infinite  time  horizon  with  entropy  regularization.  Assuming  access  to  the  exact  policy  evaluation,  both  proposed  approaches  are  proved  to  converge  linearly  in  finding  optimal  policies.  Moreover,  the  IPO  method  can  achieve  a  super-linear  convergence  rate  once  it  enters  a  local  region  around  the  optimal  policy.  Finally,  when  the  optimal  policy  for  an  RL  problem  in  a  known  environment  is  appropriately  transferred  as  the  initial  policy  to  an  RL  problem  in  an  unknown  environment,  the  IPO  method  is  shown  to  converge  at  a  super-linear  rate  if  the  two  environments  are  sufficiently  close.  A  model-free  version  of  the  policy-based  methods  is  also  discussed.  Performances  of  these  proposed  algorithms  are  supported  by  numerical  examples.
■590    ▼aSchool  code:  0028.
■650  4▼aApplied  mathematics
■650  4▼aStatistics
■650  4▼aMathematics
■653    ▼aMulti-agent  systems
■653    ▼aNash  equilibria
■653    ▼aReinforcement  learning
■653    ▼aMarkovian  policy
■653    ▼aStochastic  control
■690    ▼a0364
■690    ▼a0800
■690    ▼a0405
■690    ▼a0463
■71020▼aUniversity  of  California,  Berkeley▼bIndustrial  Engineering  &  Operations  Research.
■7730  ▼tDissertations  Abstracts  International▼g87-01B.
■790    ▼a0028
■791    ▼aD.Eng.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358464▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서