科研動(dòng)態(tài)
在線(xiàn)鞍點(diǎn)問(wèn)題的近點(diǎn)法
中文題目：在線(xiàn)鞍點(diǎn)問(wèn)題的近點(diǎn)法
論文題目：Proximal Point Method for Online Saddle Point Problem
錄用期刊/會(huì)議：The 31st International Conference on Neural Information Processing (ICONIP 2024)（CCF-C類(lèi)期刊）
錄用時(shí)間：2024.7.28
作者列表：
1) 孟慶鑫 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 控制科學(xué)與工程 博18級(jí)
2) 劉建偉 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 自動(dòng)化系 教師
摘要:
本文主要研究在線(xiàn)鞍點(diǎn)問(wèn)題，涉及一系列兩人時(shí)變凸凹博弈。考慮到環(huán)境的非平穩(wěn)性，我們采用對(duì)偶間隙動(dòng)態(tài)納什均衡后悔函數(shù)作為算法的性能指標(biāo)設(shè)計(jì)。我們提出了近端點(diǎn)法的三種變體：在線(xiàn)近點(diǎn)法（OPPM）、樂(lè)觀(guān)OPPM（OptOPPM）和具有多個(gè)預(yù)測(cè)因子的OptOPPM。每種算法都保證了對(duì)偶間隙和動(dòng)態(tài)納什均衡后悔函數(shù)的上限，當(dāng)與對(duì)偶間隙后悔函數(shù)進(jìn)行比較時(shí)，實(shí)現(xiàn)了接近最優(yōu)后悔上界。具體來(lái)說(shuō)，在某些良性環(huán)境中，例如平穩(wěn)回報(bào)函數(shù)序列，這些算法保持了一個(gè)幾乎恒定的后悔上界。實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了這些算法的有效性。最后，本文討論了使用動(dòng)態(tài)納什均衡后悔上界作為性能指標(biāo)的潛在可靠性問(wèn)題。技術(shù)附錄和代碼可以在以下網(wǎng)址獲取https://github.com/qingxin6174/PPM-for-OSP.
背景與動(dòng)機(jī):
在線(xiàn)鞍點(diǎn)（The Online Saddle Point）問(wèn)題涉及一系列兩人時(shí)變凸凹博弈。在第
輪中，玩家1和2共同選擇一對(duì)策略
。在這里，玩家1將收益最小化，而玩家2將收益最大化。兩位玩家沒(méi)有對(duì)當(dāng)前或未來(lái)收益函數(shù)的先驗(yàn)知識(shí)。在最終確定策略對(duì)后，環(huán)境顯示了一個(gè)連續(xù)的收益函數(shù)
?，它滿(mǎn)足以下條件：
在??上是凸的，并且
在??上是凹的。沒(méi)有對(duì)環(huán)境施加額外的假設(shè)，從而允許潛在的規(guī)律性甚至對(duì)抗性行為。目標(biāo)是為玩家提供近似納什均衡的決策算法，確保玩家在大多數(shù)回合中的決策接近鞍點(diǎn)。
主要內(nèi)容:
我們提出了解決OSP（The Online Saddle Point）問(wèn)題的近點(diǎn)法的三種變體：在線(xiàn)近點(diǎn)法（the Online Proximal Point Method，OPPM），樂(lè)觀(guān)OPPM（the Optimistic OPPM，OptOPPM）允許任意預(yù)測(cè)器，OptOPPM具有多個(gè)預(yù)測(cè)器，增強(qiáng)了算法處理多個(gè)預(yù)測(cè)器的能力。結(jié)果如表1所示。
表1：論文的結(jié)果總結(jié)。
在該表中，
包含了多項(xiàng)式對(duì)數(shù)因子，
表示凸凹收益函數(shù)序列的累積差，
表示單個(gè)預(yù)測(cè)器的累積誤差，
表示第??個(gè)預(yù)測(cè)器的累積誤差。
結(jié)論:
本研究通過(guò)引入三種自適應(yīng)性算法來(lái)解決在線(xiàn)鞍點(diǎn)問(wèn)題近端點(diǎn)法：OPPM、OptOPPM和OptOPPM多個(gè)預(yù)測(cè)器。這些方法是為了維持D-Gap (The duality gap) 以及NE-Reg (The dynamic Nash equilibrium regret)的上界而精心設(shè)計(jì)的，確保與D-Gap相關(guān)的性能接近最優(yōu)。在有利條件下，如取不變的收益函數(shù)，三種自適應(yīng)性算法OPPM、OptOPPM和OptOPPM保持接近不變的后悔度量上限。該研究還質(zhì)疑了NE-Reg作為后悔度量函數(shù)的有效性，并通過(guò)實(shí)驗(yàn)支持了我們的質(zhì)疑和觀(guān)點(diǎn)。
作者簡(jiǎn)介:
劉建偉，教師，學(xué)者。發(fā)表學(xué)術(shù)研究論文280多篇。