中文題目：在線鞍點問題的近點法

論文題目：Proximal Point Method for Online Saddle Point Problem

錄用期刊/會議：The 31st International Conference on Neural Information Processing (ICONIP 2024)（CCF-C類期刊）

錄用時間：2024.7.28

作者列表：

1) 孟慶鑫 中國石油大學（北京）人工智能學院 控制科學與工程 博18級

2) 劉建偉 中國石油大學（北京）人工智能學院 自動化系 教師

摘要:

本文主要研究在線鞍點問題，涉及一系列兩人時變凸凹博弈?？紤]到環境的非平穩性，我們采用對偶間隙動態納什均衡后悔函數作為算法的性能指標設計。我們提出了近端點法的三種變體：在線近點法（OPPM）、樂觀OPPM（OptOPPM）和具有多個預測因子的OptOPPM。每種算法都保證了對偶間隙和動態納什均衡后悔函數的上限，當與對偶間隙后悔函數進行比較時，實現了接近最優后悔上界。具體來說，在某些良性環境中，例如平穩回報函數序列，這些算法保持了一個幾乎恒定的后悔上界。實驗結果進一步驗證了這些算法的有效性。最后，本文討論了使用動態納什均衡后悔上界作為性能指標的潛在可靠性問題。技術附錄和代碼可以在以下網址獲取https://github.com/qingxin6174/PPM-for-OSP.

背景與動機:

在線鞍點（The Online Saddle Point）問題涉及一系列兩人時變凸凹博弈。在第輪中，玩家1和2共同選擇一對策略。在這里，玩家1將收益最小化，而玩家2將收益最大化。兩位玩家沒有對當前或未來收益函數的先驗知識。在最終確定策略對后，環境顯示了一個連續的收益函數?，它滿足以下條件：在??上是凸的，并且在??上是凹的。沒有對環境施加額外的假設，從而允許潛在的規律性甚至對抗性行為。目標是為玩家提供近似納什均衡的決策算法，確保玩家在大多數回合中的決策接近鞍點。

主要內容:

我們提出了解決OSP（The Online Saddle Point）問題的近點法的三種變體：在線近點法（the Online Proximal Point Method，OPPM），樂觀OPPM（the Optimistic OPPM，OptOPPM）允許任意預測器，OptOPPM具有多個預測器，增強了算法處理多個預測器的能力。結果如表1所示。

表1：論文的結果總結。

在該表中，包含了多項式對數因子，表示凸凹收益函數序列的累積差，表示單個預測器的累積誤差，表示第??個預測器的累積誤差。

結論:

本研究通過引入三種自適應性算法來解決在線鞍點問題近端點法：OPPM、OptOPPM和OptOPPM多個預測器。這些方法是為了維持D-Gap (The duality gap) 以及NE-Reg (The dynamic Nash equilibrium regret)的上界而精心設計的，確保與D-Gap相關的性能接近最優。在有利條件下，如取不變的收益函數，三種自適應性算法OPPM、OptOPPM和OptOPPM保持接近不變的后悔度量上限。該研究還質疑了NE-Reg作為后悔度量函數的有效性，并通過實驗支持了我們的質疑和觀點。

作者簡介:

劉建偉，教師，學者。發表學術研究論文280多篇。