增强学习模型解决博弈均衡问题的研究

摘要摘要自 从博 弈论 ( G a m e T h e o r y ) 诞生以后，由 于其解决对策、决 策问 题的 指导 性，许多学科领域都引入了博弈论的思想。而博弈论中 N a s h均衡的思想也成为解决许多策略 选择问 题重要 依据和途径。如何能 在博弈问 题中更 好的利用 N a s h均衡的思想和方法， 使我们得到更优的策略，并将其应用于具体的实际问题从而获得更佳的收益，这正是本文所讨论的。首 先， 我 们引入了 增强学习算 法的思 想。 增强学习 算法的历史 要追溯到 计算机科学和控制论的早期。 近来主要致力于机器学习和人工智能领域。 增强学习算 法的 主要思想是 在一个不断重 复进行的决策过 程或者类似的决策 过程中， 分析每次的决 策和得到的收 益以 及对以 后决策过程的影响， 总结出一定的 关于这 个( 类)决策过程的规律， 得到一定的决策策略以指导以后的决策， 从而使得决策者能够获得一个更好的收益。有了 增强学习 算法的思想， 我们希望能将这一思 想用于对博弈中N a s h 均衡 的求解问 题。 我 们将一个 博弈看作一 个近 似的 重复博弈， 把博弈中的 每一个参与人看作一 个使用增强 学习 算法思 想的A g e n t .然后 将这个博弈问题 重复的进 行， 把每一次博 弈过程 ( 参与人的选择和收益)记 录到博 弈的 历史中， 通过每一个A g e n t 对博弈历史 利用评估函 数进行评估， 然后调整这个博弈的 策略。 最终通过 对策略8 h “ 学31; ， 每一 个A g e n 的 策略收敛到某一个策 略上， 这 个策略能使A g e n t 获得 一个更好的收 益 ( 评估函 数评估) 。 而依据N a s h 均 衡的思 想， 这 个策略就是这个 博弈的N a s h 均衡。这也为 我们提供了一种求博 弈N a s h 均衡的 方 祛.最后，我们将运用增强学习算法思想求解Na s h均衡的方法来解决一个实际的博弈问题带约束的质量服务路由， 给出了一个基于增强学习算法的路由模型 和算法。 我 们将每一个交 换节点都看做一个A g e n t ，并且它 们都利 用增强学习 算 法的 思想来 对路由 选择的策略进 行 “ 学习” ，根 据路由 的历史 ( 选 择和所产生 的 消耗) 来调整 路由 策略以使 得网 络能更好的满 足约 束， 提高服务 质爱。 这样，每一个交换节点都不需要保存网络的结构和变化情况， 只需根据路由的历史就能判断出网络的情况，并且作出调整。关 健字: 博弈、 N a s h均衡、增强 学习算法、策略搜索、 路由 模型、带 约束的质量服务路由。声 卜 曰 . 川-.A f te r t h e G a m e th e o ry w a s b o rn, i t w a s i n t r o d u ced in t o m a n y o t h e r fi e l d s , b e c a u s e o f i t ' s g u i d a n c e i n s o l v i n g c o u n t e r m e a s u r e s a n d d e c i s io n - m a k i n g p ro b l e m s , a n d t h e c o n ce p t o f N a s h e q u i l ib r i u m a l s o b e c a m e a n i m p o r t a n t b a s is . I n t h i s t h e s is , w ef o c u s o n h o w t o u s e t h e c o n cep t o f N a s h e q u i li b r i u m b e tt e r t o f i n d o p t ima l s t r a t e g y ,a n d h o w t o u s e i t t o s o lv e s o m e p r a c t i c a l l y p ro b l e m.F i r s t l y , w e in t ro d u c e t h e i d e a l o f r e i n f o r ce m e n t l e a r n i n g a l g o r i t h m . T h e h i s t o ryo f r e i n f o r c e me n t le a rni n g a l g o r i t h m g o e s b a c k to t h e e a r l y d a y s o f c y b e r n e t i c s a n dc o m p u t e r s c ie n ce. L a t e l y , i t h a s a t tr a c t e d c o n s id e r a b l e i n t e r e s t i n t h e m a c h in e l e a rn i n g a n d a r ti fi c i a l i n t e l l i g e n ce c o m m u n i t ie s . T h e m a i n i d e a l o f re i n f o r c e m e n t t e a m i n g is t oc o n c l u d e s o me rul e s o f a r e p e a t e d d e c i s i o n - ma k in g p r o c e s s b y a n a ly z i n g t h er e l a t io n s h ip b e t w e e n d e c i s i o n a n d u t i l it y a n d t h e e ff e c t t o l a t e r d e c i s i o n - m a k in gp r o c e s s e s .S e c o n d l y , w e h o p e i t i s u s e f u l f o r fi n d i n g N a s h E q u i l i b r iu m. S o , w e r e g a r d ag a m e a s a n a ppro x i m a t e re p e a t e d g a m e , a n d r e g a r d t h e p l a y e r in t h e g a me a s a n Ag e n t w h i c h i s g u id e d b y r e in f o r ce m e n t t e a m i n g . T h e n , w e p l a y t h e g a m e r e p e a t e d l y ; r e c o r d t h e p r o c e s s i n t o t h e g a m e h i s t o ry . T h e a g e n t a n a l y z e s a n d e v a l u a t e s t h e d e c i s i o n a c c o r d i n g t o t h e h i s t o r y , a n d a d j u s t s t h e s tr a t e g y . A f t e r t h e 'l e a rn i n g ', t h e a g e n t 's s t r a t e g y c o n v e r g e s t o a s t r a t e g y w h i c h c a n m a x i m iz e t h e u t i l i t y . A c c o r d i n g t o t h ec o n c e p t o f N a s h鞠u i l i b r iu m , t h i s s t r a t e g y i s j u s t t h e N a s h E q u i l i b r i u m. S o , i tp rov i d e s a m e t h o d t o fi n d N a s h鞠u i l i b r i u m .F in a l l y , w e u s e t h e me t h o d t o s o l v e a p r a c t i c a l p ro b l e m , t h e c o n s t r a i n e d q u a l i t y - o f - s e r v i ce r o u t i n g . W e g iv e a ro u ti n g m o d e l a n d a n a l g o r i t h m b a s e d o n re i n f o r c e m e n t t e a m i n g a l g o r i t h m . E v e ry n o d e i s t r e a d e d a s a n a g e n t . ho r d e r t os a t is fi e s t h e c o n s t r a i n t s a n d i m p rov e s t h e q u a l i t y o f s e r v ice, t h e a g e n t u s e s t h e r e i n f o r ce m e n t l e a rn i n g a lg o r i t h m t o l e a rn t h e ro u t i n g s t r a t e g y f ro m t h e h i s t o ry ( c h o i cea n d t h e c o s t) . T h e r e f o r e , e v e r y n o d e c a n k n o w t h e s t a t u s o f t h e n e t b y e v a l u a t i n g t h eh i s t o ry a n d ma k e c h a n g e s r a p id l y i n s t e a d o f k e e p i n g a l a r g e mo u n t o f i n f o r ma t i o na b o u t t h e n e t .K e y w o r d s : G a me s , N a s h E q u i l i b r i u m, R e i n f o r c e m e n t L e a rni n g A l g o r i t h m , P o l i c yS e a r c h , R o u t in g Mo d e l , C o n s t r a i n e d Q u a li t y - o f - S e r v i ce R o u t i n g .Y8 9 8 9 9 3声明本人声明所呈交的 论文是我个人在导师指导下进行的 研究工作及 取得的 研究成果。 尽我所知， 除了 文中 特别加以标 注和致谢的 地方外， 论文中 不包含其他人已经 发表或撰 写过的 研究成果， 也不包 含为 获得云南 大学或其 他教育 机构的学位或证明 而使用过 的材料。 与我一同 工作的同志 对本研究 所做的任何贡 献均已 在论文中作了明确的说明并表示了谢意。研究 生 签 名 : 里色么璧， 日 期 : 一