arXiv:2509.07901cs.LGmath.OC2025-09被引 1

提出模块化算法,优化非平稳在线博弈的动态差距

A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization

  • 分三模块自适应调整环境变化,动态融合多预测器
  • 达到最优动态差距上界,对可预测环境更高效
  • 结构灵活,适合需融合先验知识或适应新环境场景

本文研究在线凸凹优化问题,将其扩展至双人时变凸凹博弈。目标是最小化动态对偶间隙(D-DGap),该指标评估玩家策略在任意比较序列下的表现。现有算法在静态或可预测环境中性能不佳。为此,我们提出一种新型模块化算法,包含三个核心组件:自适应模块,根据非平稳程度动态调整;多预测器聚合模块,从多个候选预测器中选出最优者;集成模块,有效结合各组件优势。所提算法在最坏情况下实现近似最优的D-DGap上界,同时具备由预测误差驱动的约束性界。模块化设计支持灵活替换调节适应性的组件,以及融入来自多个预测器的“侧知识”。实验结果进一步验证了该方法的有效性与适应能力。

原文摘要 · Abstract (English)

This paper investigates the problem of Online Convex-Concave Optimization, which extends Online Convex Optimization to two-player time-varying convex-concave games. The goal is to minimize the dynamic duality gap (D-DGap), a critical performance measure that evaluates players' strategies against arbitrary comparator sequences. Existing algorithms fail to deliver optimal performance, particularly in stationary or predictable environments. To address this, we propose a novel modular algorithm with three core components: an Adaptive Module that dynamically adjusts to varying levels of non-stationarity, a Multi-Predictor Aggregator that identifies the best predictor among multiple candidates, and an Integration Module that effectively combines their strengths. Our algorithm achieves a minimax optimal D-DGap upper bound, up to a logarithmic factor, while also ensuring prediction error-driven D-DGap bounds. The modular design allows for the seamless replacement of components that regulate adaptability to dynamic environments, as well as the incorporation of components that integrate ``side knowledge'' from multiple predictors. Empirical results further demonstrate the effectiveness and adaptability of the proposed method.

在线优化非平稳性博弈论模块化设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。