We study Nash equilibria learning of a general-sum stochastic game with an
unknown transition probability density function. Agents take actions at the
current environment state and their joint action influences the transition of
the environment state and their immediate rewards. Each agent only observes the
environment state and its own immediate reward and is unknown about the actions
or immediate rewards of others. We introduce the concepts of weighted
asymptotic Nash equilibrium with probability 1 and in probability. For the case
with exact pseudo gradients, we design a two-loop algorithm by the equivalence
of Nash equilibrium and variational inequality problems. In the outer loop, we
sequentially update a constructed strongly monotone variational inequality by
updating a proximal parameter while employing a single-call extra-gradient
algorithm in the inner loop for solving the constructed variational inequality.
We show that if the associated Minty variational inequality has a solution,
then the designed algorithm converges to the k^{1/2}-weighted asymptotic Nash
equilibrium. Further, for the case with unknown pseudo gradients, we propose a
decentralized algorithm, where the G(PO)MDP gradient estimator of the pseudo
gradient is provided by Monte-Carlo simulations. The convergence to the k^{1/4}
-weighted asymptotic Nash equilibrium in probability is achieved.

研究了一种具有未知转移概率密度函数的一般和随机游戏的纳什平衡学习。介绍一种加权渐近纳什均衡的概念，并提出了两种算法，一种是针对精确伪梯度的，另一种是针对未知伪梯度的。

通用和随机博弈纳什均衡学习的去中心化策略梯度

Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Games

We fix a fundamental issue in the stochastic extragradient method by
providing a new sampling strategy that is motivated by approximating implicit
updates. Since the existing stochastic extragradient algorithm, called
Mirror-Prox, of (Juditsky et al., 2011) diverges on a simple bilinear problem
when the domain is not bounded, we prove guarantees for solving variational
inequality that go beyond existing settings. Furthermore, we illustrate
numerically that the proposed variant converges faster than many other methods
on bilinear saddle-point problems. We also discuss how extragradient can be
applied to training Generative Adversarial Networks (GANs) and how it compares
to other methods. Our experiments on GANs demonstrate that the introduced
approach may make the training faster in terms of data passes, while its higher
iteration complexity makes the advantage smaller.

通过新的采样策略来解决随机外推梯度法中的基本问题，并且证明可以解决变分不等式问题，以及比其他方法更快地收敛于双线性鞍点问题，同时探讨了外推梯度法在训练生成式对抗网络中的应用及其与其他方法的比较。

重新审视随机外推算法

Revisiting Stochastic Extragradient

This paper analyzes simultaneous route-and-departure-time (SRDT) dynamic user
equilibrium (DUE) that incorporates the notion of boundedly rational (BR) user
behavior in the selection of departure time and route choices. Intrinsically,
the boundedly rational dynamic user equilibrium (BR-DUE) model we present
assumes that travelers do not always seek the least costly
route-and-departure-time choice. Rather, their perception of travel cost is
affected by an indifference band describing travelers' tolerance of the
difference between their experienced travel costs and the minimum travel cost.
An extension of the BR-DUE problem is the so-called variable tolerance dynamic
user equilibrium (VT-BR-DUE) wherein endogenously determined tolerances may
depend not only on paths, but also on the established path departure rates.
This paper presents a unified approach for modeling both BR-DUE and VT-BR-DUE,
which makes significant contributions to model formulation, analysis of
existence, solution characterization, and heuristic numerical computation of
such problems. The VT-BR-DUE problem, together with the BR-DUE problem as a
special case, is formulated as a variational inequality. We provide a very
general existence result for VT-BR-DUE and BR-DUE that relies on assumptions
weaker than those required for mere DUE models. Moreover, a characterization of
the solution set is provided based on rigorous topological analysis. Finally,
three computational algorithms are proposed based on the VI and DVI
formulations. Numerical studies are conducted to assess the proposed algorithms
in terms of solution quality, convergence, and computational efficiency.

本文提出了一种统一方法来建模同时路线和出发时间动态用户均衡，包括有限理性用户行为概念；我们提供了 VT-BR-DUE 的存在性和解决方案的表征，并提出了基于 VI 和 DVI 公式的三种计算算法，以评估解决方案质量，收敛性和计算效率。