证明了稀疏熵正则化在博弈中的最优性,提升大规模博弈求解效率。
On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
- 提出树结构范数分析框架,揭示稀疏熵正则化的强凸性本质
- 证明其性能接近理论极限,优于现有算法的对数因子
- 适合研究博弈计算、在线学习与优化算法的学者
一阶方法(FOMs)是求解大规模序贯博弈均衡最高效的算法。其核心在于选择合适的距离生成函数(即正则化项),而该函数的强凸性模量与直径之比是影响算法性能的关键参数。本文最终证明:权重为1的稀疏熵(DilEnt)正则化函数在扩展形式博弈策略空间中几乎最优,误差仅含对数因子。该正则化项与核化在线镜面上升(KOMWU)算法迭代等价,但传统分析无法解释此现象。本文通过引入一对原对偶树形单纯形范数,建立自然分析视角,重现了与KOMWU一致的性能预测。结合新的序列形式策略空间在线学习下界,证明该比值近乎最优。进一步应用该分析技术,改进了预言式在线镜面下降(Clairvoyant OMD)的收敛率,得到在n人博弈中以$\mathcal{O}(n \log |\mathcal{V}| \log T / T)$速率逼近粗相关均衡的结果,其中$|\mathcal{V}|$为玩家缩减正规形式策略数,为当前最优。
原文摘要 · Abstract (English)
First-order methods (FOMs) are arguably the most scalable algorithms for equilibrium computation in large extensive-form games. To operationalize these methods, a distance-generating function, acting as a regularizer for the strategy space, must be chosen. The ratio between the strong convexity modulus and the diameter of the regularizer is a key parameter in the analysis of FOMs. A natural question is then: what is the optimal distance-generating function for extensive-form decision spaces? In this paper, we make a number of contributions, ultimately establishing that the weight-one dilated entropy (DilEnt) distance-generating function is optimal up to logarithmic factors. The DilEnt regularizer is notable due to its iterate-equivalence with Kernelized OMWU (KOMWU) -- the algorithm with state-of-the-art dependence on the game tree size in extensive-form games -- when used in conjunction with the online mirror descent (OMD) algorithm. However, the standard analysis for OMD is unable to establish such a result; the only current analysis is by appealing to the iterate equivalence to KOMWU. We close this gap by introducing a pair of primal-dual treeplex norms, which we contend form the natural analytic viewpoint for studying the strong convexity of DilEnt. Using these norm pairs, we recover the diameter-to-strong-convexity ratio that predicts the same performance as KOMWU. Along with a new regret lower bound for online learning in sequence-form strategy spaces, we show that this ratio is nearly optimal. Finally, we showcase our analytic techniques by refining the analysis of Clairvoyant OMD when paired with DilEnt, establishing an $\mathcal{O}(n \log |\mathcal{V}| \log T/T)$ approximation rate to coarse correlated equilibrium in $n$-player games, where $|\mathcal{V}|$ is the number of reduced normal-form strategies of the players, establishing the new state of the art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。