河南人民的朋友圈

交叉信息院2018级本科生再获评 NeurIPS 2021焦点论文

浏览量:
2021年10月28日

    姚(yao)班2018级本(ben)(ben)科(ke)生周润龙(long)作为(wei)共同第一作者完(wan)成的论(lun)文(wen)(wen)《Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret》被2021年神经信息处理系统进(jin)展大会(NeurIPS 2021)接收并评为(wei)焦点(Spotlight)论(lun)文(wen)(wen)。本(ben)(ben)年度大会上获得该荣誉(yu)的论(lun)文(wen)(wen)占(zhan)总提交论(lun)文(wen)(wen)数(shu)不足3%。该论(lun)文(wen)(wen)研(yan)究了理论(lun)强化学习(xi)中最为(wei)根(gen)本(ben)(ben)的问(wen)题——马尔科(ke)夫决策过程随机最短(duan)路问(wen)题(SSP-MDP),并得出了理论(lun)最优的算法。

 

     由于其(qi)普适(shi)性,马(ma)尔(er)科夫决策过(guo)程是(shi)理论(lun)(lun)强化(hua)学(xue)习领域(yu)中最(zui)受关(guan)注(zhu)的(de)(de)(de)(de)(de)问(wen)题模型。在这类(lei)问(wen)题中,人工(gong)(gong)智(zhi)(zhi)能(neng)可以(yi)(yi)将其(qi)所在的(de)(de)(de)(de)(de)环(huan)境抽象成一(yi)个(ge)(ge)马(ma)尔(er)科夫链,即(ji)(ji)用(yong)状(zhuang)态(tai)(tai)(tai)、操作(zuo)、转移(yi)(yi)状(zhuang)态(tai)(tai)(tai)、回报刻画(hua)。在不知道每个(ge)(ge)操作(zuo)的(de)(de)(de)(de)(de)转移(yi)(yi)状(zhuang)态(tai)(tai)(tai)和回报的(de)(de)(de)(de)(de)情况下(xia),人工(gong)(gong)智(zhi)(zhi)能(neng)需要(yao)在K轮学(xue)习后(hou)最(zui)优化(hua)某个(ge)(ge)特(te)(te)定(ding)目(mu)标。理论(lun)(lun)研究最(zui)为深入(ru)的(de)(de)(de)(de)(de)MDP通常假(jia)设(she)人工(gong)(gong)智(zhi)(zhi)能(neng)一(yi)轮只能(neng)走固定(ding)、有限的(de)(de)(de)(de)(de)步(bu)数(shu),或(huo)者假(jia)设(she)回报随着步(bu)数(shu)增长呈指数(shu)衰减,这样的(de)(de)(de)(de)(de)假(jia)设(she)过(guo)于强大,以(yi)(yi)至于生活中的(de)(de)(de)(de)(de)另一(yi)些基本问(wen)题不能(neng)被(bei)很好地(di)表示(shi)。随机(ji)最(zui)短路(SSP)问(wen)题则(ze)没有上(shang)述假(jia)设(she),而采(cai)用(yong)了一(yi)个(ge)(ge)较(jiao)弱的(de)(de)(de)(de)(de)假(jia)设(she),即(ji)(ji)假(jia)设(she)按照(zhao)最(zui)优策略执行(xing)的(de)(de)(de)(de)(de)人工(gong)(gong)智(zhi)(zhi)能(neng),其(qi)一(yi)轮的(de)(de)(de)(de)(de)期(qi)望(wang)总(zong)代价(jia)(jia)不超过(guo)一(yi)个(ge)(ge)特(te)(te)定(ding)值B*,同(tong)时期(qi)望(wang)步(bu)数(shu)不超过(guo)另一(yi)个(ge)(ge)特(te)(te)定(ding)值T*。同(tong)时,SSP的(de)(de)(de)(de)(de)目(mu)标为搜寻到一(yi)个(ge)(ge)特(te)(te)定(ding)状(zhuang)态(tai)(tai)(tai)的(de)(de)(de)(de)(de)最(zui)小总(zong)代价(jia)(jia),这也与人们以(yi)(yi)目(mu)标为导(dao)向的(de)(de)(de)(de)(de)行(xing)为方式更加吻(wen)合(he)。采(cai)用(yong)遗憾刻画(hua)算法(fa)的(de)(de)(de)(de)(de)优劣,即(ji)(ji)前K轮所花的(de)(de)(de)(de)(de)实际代价(jia)(jia)减去K倍(bei)最(zui)优代价(jia)(jia)。

     该论(lun)文提(ti)出(chu)了SSP问题的(de)(de)三(san)点(dian)要(yao)(yao)求(qiu):(1)最小化最劣情况(kuang)下的(de)(de)遗憾,由信息论(lun)推知(zhi)下界为(wei)Ω(B*√(SAK)),依照理论(lun)强化学习惯例(li),可以(yi)(yi)忽略(lve)对数项(xiang)和与K无关的(de)(de)项(xiang);(2)算法的(de)(de)执行不(bu)需要(yao)(yao)事(shi)先知(zhi)道参(can)数B*和T*,实际情况(kuang)中(zhong)人(ren)工智能(neng)也是不(bu)可能(neng)知(zhi)道这两个(ge)参(can)数的(de)(de);(3)忽略(lve)对数项(xiang)后(hou),遗憾与T*无关,因为(wei)T*可能(neng)会比(bi)B*大任意多倍(bei)。该论(lun)文与另(ling)一篇同(tong)时投稿(gao)的(de)(de)论(lun)文分别独(du)(du)立(li)提(ti)出(chu)了满足(zu)要(yao)(yao)求(qiu)(1)的(de)(de)不(bu)同(tong)算法,而(er)该论(lun)文的(de)(de)独(du)(du)有贡(gong)献(xian)在于提(ti)出(chu)了满足(zu)要(yao)(yao)求(qiu)(2)的(de)(de)通(tong)用算法。最后(hou),该论(lun)文中(zhong)的(de)(de)算法还能(neng)以(yi)(yi)牺牲要(yao)(yao)求(qiu)(2)中(zhong)的(de)(de)T*换(huan)取(qu)要(yao)(yao)求(qiu)(3),而(er)同(tong)时满足(zu)三(san)点(dian)要(yao)(yao)求(qiu)的(de)(de)算法是否存(cun)在目前仍是开放(fang)性问题。

 

    对(dui)(dui)于(yu)要(yao)(yao)求(1),该(gai)论(lun)文提出的(de)(de)(de)(de)算法(fa)基于(yu)乐观估(gu)计(ji)(ji)(ji)、值(zhi)迭(die)(die)代的(de)(de)(de)(de)有(you)限时间近似收敛(lian)来(lai)保证(zheng)(zheng)运行效率和遗(yi)(yi)憾上界。乐观估(gu)计(ji)(ji)(ji)部(bu)分(fen)用(yong)到(dao)了上确信界的(de)(de)(de)(de)思路,通(tong)(tong)过(guo)引入统计(ji)(ji)(ji)量方(fang)差来(lai)获得较同领域(yu)前作更精细(xi)的(de)(de)(de)(de)分(fen)析方(fang)式(shi)。该(gai)论(lun)文通(tong)(tong)过(guo)构造(zao)一个新式(shi)的(de)(de)(de)(de)贝尔(er)曼(man)算子来(lai)保证(zheng)(zheng)值(zhi)迭(die)(die)代的(de)(de)(de)(de)单调(diao)、收敛(lian)。基于(yu)这(zhei)两点,该(gai)论(lun)文将(jiang)遗(yi)(yi)憾分(fen)解(jie)为(wei)贝尔(er)曼(man)误差和统计(ji)(ji)(ji)误差,并通(tong)(tong)过(guo)递归(推(tui))的(de)(de)(de)(de)方(fang)式(shi)得到(dao)方(fang)差总和的(de)(de)(de)(de)上界,从而证(zheng)(zheng)明遗(yi)(yi)憾上界。对(dui)(dui)于(yu)要(yao)(yao)求(2),该(gai)论(lun)文的(de)(de)(de)(de)通(tong)(tong)用(yong)算法(fa)核心对(dui)(dui)于(yu)B*的(de)(de)(de)(de)估(gu)计(ji)(ji)(ji)。只要(yao)(yao)给定一个满足要(yao)(yao)求(1)的(de)(de)(de)(de)算法(fa),通(tong)(tong)用(yong)算法(fa)可以(yi)通(tong)(tong)过(guo)定期(qi)比较其实际总代价(jia)与(yu)估(gu)计(ji)(ji)(ji)B*的(de)(de)(de)(de)遗(yi)(yi)憾上界来(lai)自(zi)适应调(diao)整B*的(de)(de)(de)(de)估(gu)计(ji)(ji)(ji)值(zhi)。对(dui)(dui)于(yu)遗(yi)(yi)憾上界的(de)(de)(de)(de)估(gu)计(ji)(ji)(ji)需要(yao)(yao)精细(xi)构造(zao)常(chang)数(shu)以(yi)及对(dui)(dui)数(shu)项。由于(yu)零代价(jia)环的(de)(de)(de)(de)存(cun)在,需要(yao)(yao)对(dui)(dui)对(dui)(dui)代价(jia)增加(jia)微小扰动(dong)来(lai)保证(zheng)(zheng)算法(fa)的(de)(de)(de)(de)执行效率,而代价(jia)就(jiu)是会在小项上引入T*。如(ru)果事(shi)先知道关(guan)于(yu)T*的(de)(de)(de)(de)阶的(de)(de)(de)(de)正确估(gu)计(ji)(ji)(ji),那么就(jiu)可以(yi)精细(xi)地计(ji)(ji)(ji)算扰动(dong)值(zhi)来(lai)满足要(yao)(yao)求(3)。

 

作者简介

周润龙

交(jiao)叉信息院2018级姚(yao)班本科(ke)生,大三学年加入华盛顿大学Simon S. Du(杜(du)少雷)组进行科(ke)研。该论(lun)文为科(ke)研期间的(de)研究成果,共同一作为Jean Tarbouriech。

 

关于NeurIPS 

      NeurIPS是计(ji)算机(ji)科(ke)学的(de)顶级年度国际会议之一,首次举办于1987年,已连续举办35届(jie),目前已发(fa)展为(wei)涵盖(gai)人工(gong)智能、机(ji)器学习、优(you)化(hua)控制等多(duo)个领域、包(bao)含多(duo)条不同研究轨道(dao)的(de)大型综(zong)合(he)性学术会议。受疫情(qing)影(ying)响,NeurIPS 2021将于12月(yue)6日~14日线上举办。

    交叉信息院师生在NeurIPS 2021共(gong)发文27篇。黄隆波研究(jiu)(jiu)组(zu)(zu)、张崇洁研究(jiu)(jiu)组(zu)(zu)、赵行研究(jiu)(jiu)组(zu)(zu)、吴翼研究(jiu)(jiu)组(zu)(zu)、高阳研究(jiu)(jiu)组(zu)(zu)、弋力研究(jiu)(jiu)组(zu)(zu)、房智轩研究(jiu)(jiu)组(zu)(zu)、陈建(jian)宇研究(jiu)(jiu)组(zu)(zu)、马恺声研究(jiu)(jiu)组(zu)(zu)均有成果(guo)发布(bu)。此(ci)外,交叉信息院2018级(ji)本科生胡杨、周润(run)龙(long)、白雨石(shi)以及张辰逸(yi)同学分别与校(xiao)友(you)等(deng)合作者共(gong)同发文。

 

xml地图 | sitemap地图
生死狙击
分享到:QQ空间新浪微博腾讯微博人人网微信
革命者 风犬少年的天空 帝霸 心动的信号 斗破苍穹 斗破苍穹 植物大战僵尸 腾讯游戏零点巡航 英雄联盟 本田肖战 万古神帝 今年盛夏气候预测 张哲瀚 美好的日子 革命者 月光变奏曲 台风烟花逼近上海 奥特曼 西甲 唐人街探案3大决战 朱一龙 爸爸的好儿子 接招吧前辈 我是特种兵之火凤凰 武炼巅峰 拜托了冰箱 只是太爱你 镇魂街 婴儿被埋一天获救马斯克痛苦来源 釜山行 极限挑战宝藏行 该忘了 釜山行 只是太爱你 阴阳师奔驰 梦幻西游 冒险岛 白蛇2:青蛇劫起 高手问道 诸葛亮 河南强降雨已致71人遇难 热爱就一起 刑侦日记 世界杯直播 完美世界 比亚迪 武炼巅峰 王俊凯 寂静之地2 盗墓笔记 猫和老鼠 1921 old town road 孙俪史上最狂山寨栽了 陈情令 阴阳师奔驰 | 下一页
Baidu
sogou
百度 搜狗 360