summaries: The submission presents a way of improving training of deep implicit networks, that take Cartesian coordinates (e.g., 2D or 3D) as inputs. The method uses additional embeddings of the input coordinates, similarly to Positional Encodings and variations (SIREN, FFN), with 2 differences: - embeddings corresponding to higher spatial frequencies are only be made available later during the optimization phase, and only if the network does not fit well enough - they can be made available selectively on different parts of the input space, based on a spatial grid. This method makes it possible to better represent inputs where the maximal spatial frequency changes a lot between regions (e.g., an image with large smooth regions, and regions of higher detail), and compares favorably to similar methods.

summaries: This paper proposes an improvement of implicit function approximation for image and mesh generation. The main contribution is to use a progressive low resolution to high resolution optimization as well as spatially adapt this `masking`. Performance is shown to be better than FFN by a significant margin.

summaries: This paper highlights a problem with Position Encoding models that use Fourier features: they're very sensitive to a bandwidth parameter that trades-off between reproduction of low- and high-spatial frequency features. Their solution is an iterative feedback algorithm that reconstructs images in a coarse-to-fine manner. They describe incremental improvements across-the-board, and large and impressive improvements in their 2D silhouette reconstruction task.

summaries: Implicit neural representations are a promising approach to learning compressed representations of data --- for example they can learn to represent an image where the network inputs are the (x,y) coordinates and the outputs are the RGB pixel values. This idea has all sorts of applications in data science and physics.   This work provides a method for improving the optimization of these implicit neural representations. It addresses the challenge that standard MLPs are biased towards learning low-spatial frequencies, and that a dataset (e.g. an image to compress) can have different frequency distributions in different regions.

summaries: The paper presents a technique for dealing with the problem of choosing bandwidths for positional encodings in implicit functions. The method presented uses higher frequency positional encodings as training progresses and clips the maximum frequency when a quality criterion has been reached for a position (therefore it is spatially adaptive) in order to avoid the appearance of artifacts.  Results on several domains (images, 3d occupancy, and mesh deformations) are presented with good results in all cases.

abstractText: Multilayer-perceptrons (MLP) are known to struggle with learning functions of high-frequencies, and in particular cases with wide frequency bands. We present a spatially adaptive progressive encoding (SAPE) scheme for input signals of MLP networks, which enables them to better fit a wide range of frequencies without sacrificing training stability or requiring any domain specific preprocessing. SAPE gradually unmasks signal components with increasing frequencies as a function of time and space. The progressive exposure of frequencies is monitored by a feedback loop throughout the neural optimization process, allowing changes to propagate at different rates among local spatial portions of the signal space. We demonstrate the advantage of SAPE on a variety of domains and applications, including regression of low dimensional signals and images, representation learning of occupancy networks, and a geometric task of mesh transfer between 3D shapes.

authors:
Matan Atzmon
Yaron Lipman

title: SAL: sign agnostic learning of shapes from raw data

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Oshrat Bar
Amnon Drory
Raja Giryes

title: A spectral perspective of neural networks robustness to label noise, 2021

authors:
Alberto Bietti
Julien Mairal

title: On the inductive bias of neural tangent kernels

venue: In Advances in Neural Information Processing Systems,

authors:
Yuan Cao
Zhiying Fang
Yue Wu
Ding-Xuan Zhou
Quanquan Gu

title: Towards understanding the spectral bias of deep learning

venue: In International Joint Conference on Artificial Intelligence,

authors:
Rohan Chabra
Jan E Lenssen
Eddy Ilg
Tanner Schmidt
Julian Straub
Steven Lovegrove
Richard Newcombe

title: Deep local shapes: Learning local sdf priors for detailed 3d reconstruction

venue: In European Conference on Computer Vision,

authors:
Zhiqin Chen
Hao Zhang

title: Learning implicit fields for generative shape modeling

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Ch Dash
Ajit Kumar Behera
Satchidananda Dehuri
Sung-Bae Cho

title: Radial basis function neural networks: A topical state-of-the-art survey

venue: Open Computer Science,

authors:
Thomas Davies
Derek Nowrouzezahrai
Alec Jacobson

title: On the effectiveness of weightencoded neural implicit 3d shapes

authors:
Zhantao Deng
Jan Bednařík
Mathieu Salzmann
Pascal Fua

title: Better patch stitching for parametric surface reconstruction

venue: arXiv preprint arXiv:2010.07021,

authors:
Benjamin Eckart
Kihwan Kim
Alejandro Troccoli
Alonzo Kelly
Jan Kautz

title: Accelerated generative models for 3d point cloud data

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Philipp Erler
Paul Guerrero
Stefan Ohrhallinger
Niloy J Mitra
Michael Wimmer

title: Points2surf learning implicit surfaces from point clouds

authors:
D. Ezuz
B. Heeren
O. Azencot
M. Rumpf
M. Ben-Chen

title: Elastic correspondence between triangle meshes

venue: Computer Graphics Forum,

authors:
Kyle Genova
Forrester Cole
Daniel Vlasic
Aaron Sarna
William T. Freeman
Thomas Funkhouser

title: Learning shape templates with structured implicit functions

venue: In International Conference on Computer Vision (ICCV),

authors:
Kyle Genova
Forrester Cole
Avneesh Sud
Aaron Sarna
Thomas Funkhouser

title: Local deep implicit functions for 3d shape

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Amos Gropp
Lior Yariv
Niv Haim
Matan Atzmon
Yaron Lipman

title: Implicit geometric regularization for learning shapes

venue: In International Conference on Machine Learning,

authors:
Zekun Hao
Hadar Averbuch-Elor
Noah Snavely
Serge Belongie

title: Dualsdf: Semantic shape manipulation using a two-level representation

authors:
Alec Jacobson
Ilya Baran
Jovan Popovic
Olga Sorkine

title: Bounded biharmonic weights for real-time deformation

venue: ACM Trans. Graph.,

authors:
Chiyu "Max" Jiang
Avneesh Sud
Ameesh Makadia
Jingwei Huang
Matthias Niessner
Thomas Funkhouser

title: Local implicit grid representations for 3d scenes

authors:
Guolin Ke
Di He
Tie-Yan Liu

title: Rethinking positional encoding in language pre-training

venue: In International Conference on Learning Representations,

authors:
L.J. Latecki
R. Lakamper

title: Shape similarity measure based on correspondence of visual parts

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Chen-Hsuan Lin
Wei-Chiu Ma
Antonio Torralba
Simon Lucey

title: Barf: Bundle-adjusting neural radiance fields

venue: arXiv preprint arXiv:2104.06405,

authors:
Shichen Liu
Shunsuke Saito
Weikai Chen
Hao Li

title: Learning to infer implicit surfaces without 3d supervision

venue: arXiv preprint arXiv:1911.00767,

authors:
Xuanqing Liu
Hsiang-Fu Yu
I. Dhillon
Cho-Jui Hsieh

title: Learning to encode position for transformer with continuous dynamical model

venue: In ICML,

authors:
Antoine Liutkus
Ondřej Cífka
Shih-Lun Wu
Umut Şimşekli
Yi-Hsuan Yang
Gaël Richard

title: Relative positional encoding for transformers with linear complexity, 2021

authors:
Julien N.P. Martel
David B. Lindell
Connor Z. Lin
Eric R. Chan
Marco Monteiro
Gordon Wetzstein

title: Acorn: Adaptive coordinate networks for neural representation

venue: ACM Trans. Graph. (SIGGRAPH),

authors:
Ricardo Martin-Brualla
Noha Radwan
Mehdi S.M. Sajjadi
Jonathan T. Barron
Alexey Dosovitskiy
Daniel Duckworth

title: NeRF in the Wild: Neural Radiance Fields for Unconstrained Photo Collections

authors:
Ishit Mehta
Michaël Gharbi
Connelly Barnes
Eli Shechtman
Ravi Ramamoorthi
Manmohan Chandraker

title: Modulated periodic activations for generalizable local functional representations, 2021

authors:
Lars Mescheder
Michael Oechsle
Michael Niemeyer
Sebastian Nowozin
Andreas Geiger

title: Occupancy networks: Learning 3d reconstruction in function space

authors:
Mateusz Michalkiewicz
Jhony Kaesemodel Pontes
Dominic Jack
Mahsa Baktashmotlagh
Anders Eriksson

title: Implicit surface representations as layers in neural networks

venue: IEEE/CVF International Conference on Computer Vision (ICCV),

authors:
Ben Mildenhall
Pratul P. Srinivasan
Matthew Tancik
Jonathan T. Barron
Ravi Ramamoorthi
Ren Ng

title: Nerf: Representing scenes as neural radiance fields for view synthesis

venue: In ECCV,

authors:
Jeong Joon Park
Peter Florence
Julian Straub
Richard Newcombe
Steven Lovegrove

title: Deepsdf: Learning continuous signed distance functions for shape representation

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Keunhong Park
Utkarsh Sinha
Jonathan T. Barron
Sofien Bouaziz
Dan B Goldman
Steven M. Seitz
Ricardo Martin-Brualla

title: Deformable neural radiance fields

venue: arXiv preprint arXiv:2011.12948,

authors:
Songyou Peng
Michael Niemeyer
Lars Mescheder
Marc Pollefeys
Andreas Geiger

title: Convolutional occupancy networks

venue: In European Conference on Computer Vision (ECCV),

authors:
Nasim Rahaman
Aristide Baratin
Devansh Arpit
Felix Draxler
Min Lin
Fred Hamprecht
Yoshua Bengio
Aaron Courville

title: On the spectral bias of neural networks

authors:
Rajesh Rao
Dana Ballard

title: Predictive coding in the visual cortex: a functional interpretation of some extra-classical receptive-field effects

venue: Nature neuroscience, 2:79–87,

authors:
Basri Ronen
David Jacobs
Yoni Kasten
Shira Kritchman

title: The convergence rate of neural networks for learned functions of different frequencies

venue: In NeurIPS,

authors:
Shunsuke Saito
Zeng Huang
Ryota Natsume
Shigeo Morishima
Angjoo Kanazawa
Hao Li

title: Pifu: Pixel-aligned implicit function for high-resolution clothed human digitization

venue: In The IEEE International Conference on Computer Vision (ICCV),

authors:
Patrick Schmidt
Janis Born
Marcel Campen
Leif Kobbelt

title: Distortion-minimizing injective maps between surfaces

authors:
Patrick Schmidt
Marcel Campen
Janis Born
Leif Kobbelt

title: Inter-surface maps via constantcurvature metrics

authors:
Vincent Sitzmann
Michael Zollhöfer
Gordon Wetzstein

title: Scene representation networks: Continuous 3d-structure-aware neural scene representations

authors:
Vincent Sitzmann
Julien Martel
Alexander Bergman
David Lindell
Gordon Wetzstein

title: Implicit neural representations with periodic activation functions

authors:
Towaki Takikawa
Joey Litalien
Kangxue Yin
Karsten Kreis
Charles Loop
Derek Nowrouzezahrai
Alec Jacobson
Morgan McGuire
Sanja Fidler

title: Neural geometric level of detail: Real-time rendering with implicit 3D shapes

authors:
Matthew Tancik
Pratul P. Srinivasan
Ben Mildenhall
Sara Fridovich-Keil
Nithin Raghavan
Utkarsh Singhal
Ravi Ramamoorthi
Jonathan T. Barron
Ren Ng

title: Fourier features let networks learn high frequency functions in low dimensional domains

venue: NeurIPS,

authors:
Matthew Tancik
Ben Mildenhall
Terrance Wang
Divi Schmidt
Pratul P. Srinivasan
Jonathan T. Barron
Ren Ng

title: Learned initializations for optimizing coordinate-based neural representations

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Ł ukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Da Xu
Chuanwei Ruan
Evren Korpeoglu
Sushant Kumar
Kannan Achan

title: Self-attention with functional time representation learning

authors:
Zhi-Qin John Xu
Yaoyu Zhang
Yanyang Xiao

title: Training behavior of deep neural network in frequency domain

venue: In ICONIP,

authors:
Alex Yu
Vickie Ye
Matthew Tancik
Angjoo Kanazawa

title: pixelNeRF: Neural radiance fields from one or few images

venue: In CVPR,

authors:
Qingnan Zhou
Alec Jacobson

title: Thingi10k: A dataset of 10,000 3d-printing models

venue: arXiv preprint arXiv:1605.04797,

heading: 1 Introduction

text:
Neural implicit functions have recently emerged as a powerful representation paradigm for modeling complex signals. Their continuous nature sets them apart from typical discrete representations (i.e. pixels, voxels, meshes), allowing to capture high resolution details in various domains such as images [41, 43], 3d shapes [31, 6] and radiance fields [30, 32], while retaining a reasonably compact representation. In this formulation, a deep neural network is trained with the goal of faithfully mapping input coordinates to a corresponding target domain, effectively learning the representation of signal properties such as magnitude, color, or shape occupancy.
Implementing implicit neural representations with common neural structures, e.g., multilayer pereceptrons with ReLU activations (ReLU MLPs), proves to be challenging in the presence of signals with high frequencies. Consequently, recent works have demonstrated that deep implicit networks benefit from mapping the input coordinates [30, 43], or the intermediate features [41] to positional encodings. That is, before feeding them into a neural layer, they are first transformed to an overparameterized, high dimensional space, typically by multiple periodic functions.
Positional encodings1 have been shown to enable highly detailed mappings of signals by MLP networks. For example, Fourier Feature Networks [43] suggested to map input coordinates of signals to a high dimensional space using sinusoidal functions. In their work, they show that the frequency
1In this paper, we use the term “positional encodings” in lower case letters to denote the family of encoding methods that map coordinates to a higher dimensional space. Not to be confused with the term “Positional Encoding” coined by [30, 43], which refers to a particular mapping scheme in this family.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
of these sinusoidal encodings is the dominant factor in obtaining high quality signal reconstructions. In particular, they present compelling arguments for randomly sampling frequency values from an isotropic Gaussian distribution with a carefully selected scale, providing a striking improvement over mapping coordinates directly via standard MLPs.
Despite the success of positional encodings, there are still some concerns left unaddressed: (i) Choosing the right frequency scale requires manual tuning, oftentimes involving a tedious parameter sweep; (ii) The frequency distribution scale may change between different inputs, and accordingly it becomes harder to tune a “one-fits-all” model for signals that are composed of a large range of frequencies (Fig. 1); (iii) Frequencies are selected for the entire input in a global, spatially invariant manner, thus missing an opportunity to better adapt to local high frequencies (Fig. 2).
Our work investigates mitigations to the aforementioned challenges. We study the setting of positional encodings as input to implicit neural networks and present Spatially-Adaptive Progressive Encoding (SAPE). SAPE is a policy for learning implicit functions, relying on two core ideas: (i) guiding the neural optimization process by gradually unmasking signal components with increasing frequencies over time, and (ii) allowing the mask progression to propagate at different rates among local spatial portions of the signal space. To govern this process, we introduce a feedback loop to control the progression of revealed encoding frequencies as a bi-variate function of time and space.
Our work enables MLP networks to adaptively fit a varying spectrum of fine details that previous methods struggle to capture in a single shot, without involved tuning of parameters or domain specific preprocessing. SAPE excels in learning implicit functions with a large Lipschitz constant, without sacrificing quality of details or optimization stability, in problems that require meticulous configuration to achieve convergence. To highlight the latter, in Section 5.1 we present the tasks of 2D silhouettes deformation and 3D mesh transfer – both require stable optimization from the get-go in order to avoid convergence to sub-optimal local minima.
SAPE is encoding-agnostic: it is not limited to a specific positional encoding type. It can be easily applied to the learning process of coordinate-based neural implicit functions of various domains including images, 2D shapes, 3D occupancy maps and surfaces, showing improvement in all of them.

heading: 2 Related work

text:
Implicit neural representations. Recent works show the capability of deep neural networks in representing different functions (e.g., 2D/3D scenes or objects) as an implicit, memory efficient continuous function [8]. These networks are used as a signed distance function (SDF) [1, 15, 31] or as an occupancy network, either binary [6, 28, 33] or soft volumetric density [26, 30, 49].
Several works train such networks to represent a collection of 3D shapes via 3D data supervision [6, 16, 29, 28, 31], reconstruct 3D shapes [5, 11, 13, 14, 18, 42] or infer them from 2D images [22, 37, 40]. Recent works employ spatial data structures to scale the represented shapes size [25, 42].
Positional encodings (PE). have been suggested as higher dimensional network input for various purposes. Radial basis function (RBF) networks [7] use weighted sums of embedded RBF encodings due to their symmetric property. [47] used random Fourier Features to map time spans. In natural language processing, Transformers [19, 23, 24, 46] leverage sinusoidal positional encoding to maintain the order of token sequences. Our work differs by focusing on how to encode the inputs to MLPs in order to improve network implicit representations.
The closest works to ours are SIREN [41] and Fourier feature networks (FFN) [43]. SIREN suggests to replace the ReLU activations in the network by periodic ones. FFN [43] encodes the inputs to the network by projecting them to a higher dimensional space using a family of encoding functions. In the appendix we provide an illustration of this approach with some examplary used encodings. The analysis of [43] demonstrates that FFN improves the learning of implicit neural representation compared to other alternatives. A follow-up work in [44] accelerates the training convergence by using a meta-learned initialization of the network weights. The contemporary work of [27] extends SIREN with a modulation network, to allow representing multiple shapes within a single network.
Concurrently to our work, Park et al. [32] extend NERF to non-rigidly deforming scenes, and BARF [21] extends NERF for cases of imperfect camera poses. Both these works show the advantage of employing coarse-to-fine annealing linearly over the frequency bandwidth of the positional encoding. The coarse-to-fine approach bears similarity to our progressive frequency approach. Different from us, these works do not use a feedback loop or spatial encoding, which, as we show in the following, further closes the gap between the regressed function and the ground truth.
As a final remark, SAPE’s concept of feedback loop resonates with the idea of "predictive coding" in computational neuroscience [35], suggesting another angle to appreciate the rationale of our method.

heading: 3 Preliminaries

text:
The setting of implicit neural representation is commonly formulated as learning a mapping function fθ, using a neural network, from an input of low dimensional position coordinates p ∈ Rd to an output value in the target domain. The network training data are coordinates samples as the input and an expected value of the function, or signal, as the output. Examples of such mappings include pixel locations to intensity values for images, or 3D space coordinates to binary surface occupancy labels.
Achieving such mappings using conventional neural networks with ReLU is hard. It has been shown that ReLU networks exhibit a behaviour of spectral bias [34, 3, 36, 2, 48, 4]. Networks tend to learn low frequency functions first, as they are characterized by a global behaviour, and are therefore more stable to optimize. Spectral bias, however, also prevents networks from properly learning to fit functions that change at a high rate, e.g., functions with a large Lipschitz constant. When visual domains are concerned, this is mostly evident in delicate details missing from the network output.
To mitigate this deficiency, recent works proposed to replace the ReLU activation layers with periodic sine functions [41] or map the input to some higher dimensional space in order to learn a mapping with high frequencies [30, 43]. In the latter approach, the input p is encoded to a high dimensional embedding by a family of functionals ei : Rd → R, such that:
E(p) = (e1(p), e2(p), . . . , en(p)) , (1)
where usually n d. Tancik et al. [43], for example, suggest the following encoding: EFFN (p) = ( cos(2πb>1 p), sin(2πb > 1 p), ..., cos(2πb > np), sin(2πb > np) ) , (2)
where bi are frequency vectors randomly sampled i.i.d. from a Gaussian distribution with standard deviation σ. Other examples of positional encodings are included in the appendix.
These embedding schemes facilitate learning of complex functions, at the price of introducing a second associated phenomenon: the spectral bias characteristic of the network is reduced. The implication in this case is twofold. Positional encodings can cause neural optimizations processes to become unstable, and consequently converge to a bad local minimum (Fig. 9). In addition, when fitting functions of varying levels of details/frequencies, neurons predicting smooth, low frequency areas are still exposed to encoding dimensions of high frequency. That, in turn, may complicate the learning process, as networks have to learn where to ignore such embedding dimensions.
Indeed, Tancik et al. [43] advocate a careful choice of the standard deviation of frequency distribution, σ in their method, showing that using low values yields missing details in the network output, and using values that are very high results in noisy artifacts. Thereupon, for such static encodings the value of σ requires a parameter sweep per sample.

heading: 4 Spatially-Adaptive Progressive Encoding (SAPE)

text:
Our proposed approach, SAPE, is a policy for guiding the optimization of implicit neural representations based on input coordinates. SAPE relies on the delicate balance of the two phenomena that govern the learning process: it reconciles the effects of the spectral bias and the expressiveness of high frequency encodings in a manner that benefits from both. It maintains a stable optimization, without sacrificing the ability to fit fine signal details. SAPE is composed of two key components: progressive encoding and spatial adaptivity, which allow it to be less sensitive to the encoding frequency bandwidth, i.e., the choice of the standard deviation in the case of [43] (Fig. 4). Next, we detail each of the mechanisms that compose SAPE. The full algorithm is included in the appendix.
Without loss of generality, in our description below we assume the encoding functionals are sorted by their respective Lipschitz constants (LC), i.e. LC(e1) ≤ LC(e2) ≤ · · · ≤ LC(en). For example, we sort the Fourier features encoding by the frequency value ‖bi‖. We set the first d dimensions to the identity encodings: ei(p) = pi, ∀i ≤ d, thereby exposing the network to the original input position coordinates p ∈ Rd as well. Progressive encoding. A core part of SAPE is progressively fitting the frequencies. The first layer of the network encodes an input position p with a set of functionals ei. In order to use only part of the functionals at different stages of training, it multiplies the encoding dimensions with a soft mask, which progresses as a function of the optimization iteration t:
Eprog(p, t) = (ê0(p, t), ê1(p, t), ê2(p, t), . . . , ên(p, t)) = α(t) >E(p), (3)
where êi(p, t) = αi(t) ei(p) is the progression control for the encoding functional ei, regulated by the elements of masking vector α(t) ∈ [0, 1]n. During the optimization, we progressively reveal encoding features in a manner that allows the encoding neurons to be tuned to different states according to the value of αi(t), where αi(t) = 1 corresponds to the state on, αi(t) = 0 means off and 0 < αi(t) < 1 denotes partially on (Fig. 3).
We define a policy Φ that controls the progression of the mask vector α(t) by α(t + 1) = Φ [α(t)|α(0)] . In this work, we use the following progression rule for the mask of the ith encoding dimension at time step t:
ΦP [α(t)] : αi(t+ 1) = clamp ( t− τ · (i− d) τ , 0, 1 ) , if i > d
1, otherwise, (4)
where τ = T/2n represents the number of iterations each encoding dimension takes to progress from 0 to 1 and T is the maximal number of iterations in the optimization. Essentially, ΦP performs a linear progression sequentially for each encoding i until it is fully exposed, s.t. αi(t) = 1. When a certain encoding dimension mask achieves saturation, we continue to the following one. We allow a technical exception to this rule, for proper progression of correlated masks of encoding dimensions sharing the same Lipschitz constant, e.g., pairs of cos, sin in the encoding in Eq. (2). For initialization, the first d positional encoding masks are fully exposed right from the beginning, and in our setting, correspond with the identity encoding functionals.
Notice that previous methods, which introduce all encoding dimensions to the network at once, can now be formulated as a specific case in our framework, where α(t+ 1) = 1.
Spatial adaptivity. When t > T/2, the progression policy ΦP achieves global saturation in terms of revealing encoding dimensions, so that the masking vector becomes α(t) = 1. For signals of global-like characteristics, e.g., have a low LC, the network is compelled to learn how to cope with undesirable encoding dimensions of high frequency to regress a smooth, slowly changing signal. This can lead to sub-optimal outputs, often visible in the form of visual artifacts (Fig. 1, mid-bottom).
Given loss function L and convergence threshold ε, a simple improvement to policy ΦP may apply early stopping when L < ε. However, for signals with varying levels of detail as a function of spatial position p, this improvement is not sufficient: early stopping does not occur due to areas characterized by high frequencies. Relying on a global threshold ε is inherently a sub-optimal decision, as when learning an implicit neural function with positional encoding, different spatial segments of the signal in question may converge at different rates (Fig. 2).
To solve this problem, we set the mask vector to be spatially sensitive: α(t,p). By design, the new policy ΦSA progresses the encoding of each spatial location p separately, per encoding dimension i. To simplify our explanation, in the current setting we assume the signal can be discretized to distinct spatial segments on a regular grid, each tracked independently (e.g., pixels, voxels). The progressive, spatially adaptive policy is controlled by a feedback loop, where the independent regression loss of each signal segment is used to control the progression:
ΦSA [α(t,p)] : α(t+ 1,p) = { ΦP (α(t)) , if L(t,p) ≥ ε α(t,p), otherwise
(5)
For implicit functions, at inference time we assume signals can be regressed with “pseudo-continuous” coordinates p. Therefore, to support coordinates p that did not appear during training and have no mask recordings, we extend the estimated parameters of α(T,p) continuously over the entire input domain by a linear interpolation.
One common example that benefits from spatial adaptivity is natural 2D image containing blurry, out-of-focus areas in the background together with sharp, detailed foreground objects. To shed more light on the behaviour of our algorithm, Figs. 6 and 8 demonstrate examples of spatial heat maps, highlighting the maximal encoding frequency achieved per spatial location, upon convergence.
a. Forward mask
b. Loss feedback
Sparse grid sampling. We now extend our method to cases where model fθ is optimized by coordinates p that do not lie on a regular grid, or when it is simply infeasible to store parameters α(t,p) per sampled coordinate p during training. In this setting, we discretize the input domain and store parameters αu in a sparse grid G, where for a grid of resolution rd ⊆ Rd, we denote u as the multidimensional grid coordinates. In the forward pass, we obtain the original encoding mask α(t,p) per sampled point p by encoding a linear interpolation of the masking parameters over the nearest grid nodes (see the inset (a) on the left):
α(t,p) = ∑
u∈NG(p)
wp,uα(t,u), (6)
where NG(p) are the neighboring grid coordinates in the vicinity of p, and wp,u are the interpolation weights for a sample p over the multidimensional grid G such that ∑ u∈NG wp,u = 1. During training, the loss L(t,u) at time t for a given grid point u is accumulated over all sampled points p affected by u (inset (b) above):
L(t,u) = 1∑ p wp,u ∑ p wp,uL(t,p). (7)
Here, L(t,p) is the loss for the original coordinate p. To obtain the overall training loss, we sum over all the used points for training at time t. We note that the linear interpolation used during the forward pass has an added benefit: since only local neighbors participate per update of the original coordinate p, sparse weights allow for efficient accumulations during forward and backward pass updates.

heading: 5 Experiments

text: We evaluate SAPE on a variety of common 2D and 3D regressions tasks. In addition, we demonstrate how it may be used to improve the tasks of deforming 2D silhouettes and transferring mesh connectivity between 3D shapes. We demonstrate our results using the Fourier feature encoding [43] (Eq. (2)). We emphasize that SAPE is agnostic to the encoding used and applicable to other mapping schemes as well. More examples, as well as the full implementation details appear in the appendix.

heading: 5.1 Evaluations

text:
We test SAPE on a variety of problems: regression tasks optimized by a direct supervision and geometric tasks optimized by an indirect supervision. All configurations employ 256 unique frequency encodings sampled from a Gaussian distribution. For fair evaluation, the distribution scale and number of neural layers remain the same for all inputs in the same problem setting. However, hyperparameter values may vary per problem. For convergence threshold ε, we set the values of 1e−3 for regression tasks and 1e−2 for geometric tasks. See the appendixfor full description of implementation details. We compare the settings of 6 MLP configurations:
1) No encoding: Basic ReLU MLP without encoding. 2) SIREN: An MLP with sine activations based on the implementation of Sitzmann et al. [41]. 3) RBF-grid: An MLP with repeated radial basis function as a first encoding layer. 4) SAPE + RBF-grid. 5) FFN: An MLP network with Fourier features as the first encoding layer, see Eq. (2). 6) SAPE + FFN.
The bandwidths of encoding functions in 3) and 5) are optimally selected by a grid search over a validation set or taken from a public implementation, depending on the task. For the SAPE variants we use double the σ of these bandwidths, as SAPE is not sensitive to a particular value, as long as it allows high frequency encodings. The quantitative results are summarized in Tables 1 and 2. Below is an overview of each task.
2D image regression. In this task we optimize the networks to map 2D input pixel coordinates, normalized to [−1, 1]2, to their RGB values. We conduct the evaluation on the same test sets as Tancik et al. [43], which contain a dataset of natural images and a synthetic dataset of text images. Similar to them, the network is trained on regularly spaced grid containing 25% of the pixels. We use the evaluation metric of PSNR over the entire image, compared to the ground truth image. Quantitative results are reported in Table 1 on the left.
3D occupancy. In this task, we use a similar setting to occupancy networks [28]: the model is trained to classify an input 3D coordinate for being inside or outside the training shape. For training, we sample 9 million points divided into 3 equal groups: uniformly sampled points in [−1, 1]3, surface points perturbed with random Gaussian noise vectors using σ = 0.1 and σ = 0.01. We evaluate the quality of the result by estimating the intersection-over-union (IoU) with respect to the ground truth shape by sampling additional 1e6 random points and 1e6 more challenging samples near the surface, and report the average IoU score.
We compare the networks on two test sets. The first set is composed of 10 selected models from the Thingi10K dataset [50]. The second, more challenging test set is composed of 4 models from TurboSquid2. The quantitative results are summarized in Table 1, middle section. Qualitative results are shown in the appendix.
2D silhouettes. Here, we optimize an MLP to deform a unit circle represented as a polyline to a target 2D point cloud of a silhouette shape. Fig. 9 shows a number of examples of such target shapes. We start by calibrating the MLP to learn a simple mapping from p ∈ [0, 1] to the 2D unit circle: f(p) = (cos(2πp), sin(2πp)). We then optimize the mapping function by minimizing the symmetric chamfer distance between the network output and the silhouette.
To evaluate the performance of the different methods, we test the networks on 20 shapes from the MPEF7 dataset [20] and measure the intersection over union between the resulting shape and the target shape; the results are reported in Table 1. Fig. 9 shows qualitative results of this task and snapshots from the optimization process. Due to the expressiveness of both FFN and SIREN networks, the chamfer loss causes distortions in the early stage of the optimization that cannot be recovered, leading to undesired results. The coarse-to-fine optimization of SAPE allows both avoiding distortions and matching high frequencies of the target shape.
2https://www.turbosquid.com
3D mesh transfer. In this task, we would like to transfer a 3D source mesh to a target shape [45, 9, 12, 38, 39], which is represented by a mesh or a point cloud. The MLP receives the vertices of the source mesh and outputs transformed vertices, such that together with the source tessellation, the optimized mesh fits the target shape while respecting the structure of the source mesh in terms of distortion. In addition, we may utilize a set of marked correspondence points between the input shapes that enable the estimation of an initial affine transformation between the source and the target, followed by a biharmonic deformation [17]. The optimization loss for this task is composed of two terms: A distance loss that measures the symmetric chamfer distance between the optimized mesh and the target shape, and a structural term that measures the discrete conformal energy between the optimized mesh and the source mesh.
We test the different networks on 6 pairs of meshes and evaluate the results by measuring the chamfer and Hausdorff distances between the target shape and the output mesh. The distortion of the transferred meshing is measured by Dirichlet energy with respect to the source mesh. Table 2 shows the quantitative results. Qualitative results are shown in Fig. 5.
Standard MLPs struggle to fit the target shape and remain close to the source mesh, therefore obtaining low Dirichlet energy but also high Chamfer and Hausdorff distances and thus failing the task. SAPE’s feedback specifies the regions on the mesh that are distanced from the target shape. That allows the optimization to gradually increase the frequencies used in high curvature areas while avoiding large distortions at the beginning of the optimization, when global deformations take place. For that reason, contrary to other methods such as FFN and SIREN, SAPE is able to avoid solutions of bad local minima and reconstruct the target signal better.

heading: 5.2 Ablation

text:
Progressive vs. non-progressive. Similar to the setting described in Section 5.1, we train an MLP on randomly sampled pixels of images. We map 2D pixel coordinates to RGB values and measure the PSNR over all pixels compared to the ground truth image.
Fig. 6 and Fig. 7 (left) show a comparison between the performance of FFN with and without SAPE when training on 25% of the pixels. Our results show that due to progressive-spatial adjustment of the encoding, SAPE is less sensitive to tuning of the standard deviation (σ) of distribution of frequencies bi. By contrast, FFN suffers from a fragile trade-off between underfitting and overfitting, which results in either blurry pixels in high frequency regions or noise in the smooth background areas.
A similar phenomena is shown in the 3D example in Fig. 10. In this task, we train an occupancy network using the setting described in Section 5.1. For regulating the level of encoding across the scene our method uses a voxel map of resolution 1283 for spatial encoding. This map is updated based on feedback loss during training. Without SAPE, low frequency encodings cannot represent detailed structures like the car object in the scene. Increasing the frequency bandwidth results in noisy surfaces and undesired blob artifacts in empty spaces. By contrast, SAPE achieves better representation of detailed regions, as well as of smooth surfaces.
Spatial progressive vs. non-spatial progressive. To demonstrate the advantage of using spatially adaptive encoding, we compare it to a variant of SAPE that globally progresses the frequency level of encodings for all spatial areas equally, and converges when all training samples fit. Fig. 2 shows the advantage of using the spatial encoding in SAPE for a 1D regression task. In addition, Table 1
shows quantitative improvement gained by SAPE applied on FF, compared to a global progression (Progressive FF).
Note that the non-spatial variant is equivalent to SAPE with a spatial grid of resolution one. Fig. 8 and Fig. 7 (right) show the benefit of the spatial encoding component for a 2D image regression task (similar to the one above). We also show how increasing the grid resolution affects the quality of the result in a 2D image regression task. We observe that the quality stays at its highest when the spatial grid resolution approximates the sampling ratio of coordinates during training.

heading: 6 Limitations and Future Work

text:
When SAPE is employed with a sampling grid, the chosen resolution provides a trade-off between memory and quality. Choosing a grid of low resolution may yield sub-optimal outputs (see examples in the appendix). As SAPE’s varying frequencies sampling grid bears some resemblance to multiresolution analysis and wavelet transforms, future extensions to SAPE may solve this issue by maintaining the masking parameters in a sparse structure such as an Octree [42] or GMM [10].
When using very high frequencies, SAPE may enhance inherent output noise, as the maximal frequency encoding gets picked for the noisy portions of the signal.
In this work we investigated a linear progression policy for unmasking frequency encodings. Followup works may extend our scheme to a more optimized curriculum, for example, using meta-learning.

heading: 7 Conclusions

text:
We presented a policy for improving the quality of signals learned by coordinate based optimizations. We rely on two major contributions: progressive introduction of positional encodings, and spatial adaptivity, which allows different rates of progression per signal location. Our method is simple to implement and improves the implicit neural representation result of MLP networks in various tasks.
Given the surge of applications that use positional encodings, and the ease of deploying SAPE, we believe our approach will be useful for many problems in the vision and graphics domains. Specifically, the fact that SAPE is encoding-agnostic and insensitive to most encoding hyperparameters provides stable training and facilitates the use of positional encodings in novel tasks.

heading: 8 Broader Impact Statement

text: SAPE is a method for boosting the accuracy of learned implicit neural functions. It can be leveraged to enable new applications or improve various downstream tasks that involve precise processing of signals, like segmentation, or reconstruction of complex signals, such as streaming video or signed distanced functions. Beyond the domains of vision and graphics, we conjecture SAPE might also benefit applications in speech, audio, and signal processing in general. Depending on their use, all mentioned applications may have a positive or negative impact. SAPE can be used to facilitate novel applications that require accurate recovery of signals, like 3D reconstruction for AR and VR. It can also be misused for the purpose of generating fake media, including audio, video and images.

heading: Acknowledgements

text: We would like to thank Hao (Richard) Zhang, Hadar Averbuch-Elor and Rinon Gal for their insightful comments, and the anonymous reviewers for their helpful remarks. This work was supported in part by the Israel Science Foundation grant no. 2492/20 and by the ERC-StG grant no. 757497 (SPADE).

title: SAPE: Spatially-Adaptive Progressive Encoding for Neural Optimization


summaries: The authors provide an analysis of an entropy regularized extra-gradient method for zero sum games. The proposed algorithms have last iterate convergence guarantees to the equilibrium of the regularized game at rate that is dimension free (up to double logarithmic factors) regardless if the unregularized game has a unique equilibrium. The algorithms can be used to find approximate equilibria of the unregularized game and in Markov zero sum games.

summaries: The paper studies two standard classes of games with entropy regularization: two-player zero-sum matrix games and zero-sum Markov games. For the regularized matrix games, the authors apply the mirror descent approach (using KL distance) to the regularized objective, and propose two first-order descent/ascent algorithms using different optimistic predictions: the Predictive Update (PU) and the Optimistic Multiplicative Weights Update (OMWU). The authors prove that both algorithms converge to the unique Nash equilibrium of the regularized game with constant stepsizes, linearly. The authors characterize the linear convergence via four measures: KL distance, infinity norm, optimality gap, and duality gap. It is featured by last-iterate convergence and almost dimension-free. For the regularized Markov games, the authors apply the proposed PU and OMWU to the $Q$-value functions at each state and prove the convergence in infinite norm to the optimal $Q$-value function of the regularized game. The convergence rate is slightly worse than the linear rate, but it is also almost dimension-free. The authors also provide computational experiments to verify the usefulness of the proposed algorithms.

summaries: The authors propose to use mirror descent to solve classic entropy-regularized competitive games. Linear convergence rates are obtained for the proposed algorithm. In addition, the authors propose to use such an algorithm to solve the subproblem in the entropy-regularized Markov game and obtain a linear convergence rate to the regularized equilibrium.

summaries: This paper proposes to leverage entropic regularization and optimistic-type methods to solve zero-sum (ZS) matrix games and ZS Markov games. The authors begin with ZS matrix games on the simplex: they add entropic regularization, thus transforming this game into a strongly-concave/strongly-concave problem. Slight variants of Mirror-prox/extragradient and optimistic mirror descent with multiplicative updates are introduced, and the authors show that, for several performance measures, the last-iterate of these methods converge linearly to a solution of the regularized problem thanks to the added strong convexity/concavity. Their rates are (almost) dimension-free, and do not require the uniqueness of the solution. As a consequence, they explain how to obtain $\epsilon$-Nash-equilibrium with $O(1/\epsilon)$ iterations by tuning the regularization parameter. Finally, the authors propose to put to use their results to tackle ZS infinite-horizon Markov games.

summaries: In this work, the authors aim to complete the recent line of research in last-iterate convergence guarantees for saddle-point optimization (applicable to game theory, GANs, etc.) with efficient methods that converge to an approximate Nash equilibrium *without* the equilibrium uniqueness guarantee. The key is to simply apply the previously analyzed methods (OMWU in particular) on a regularized version of the payoff. The regularization ensures uniqueness of what is called QRE, quantal response equilibrium, which can be used for finding an approximate Nash equilibrium. As a bonus, the authors show that their results apply to Markov games too.

abstractText: This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled as a constrained saddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods in the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, especially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization in single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods to find the quantal response equilibrium (QRE)—which are solutions to zero-sum two-player matrix games with entropy regularization—at a linear rate. The proposed algorithms can be implemented in a decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own payoff without observing the opponent’s actions directly. In addition, by controlling the knob of entropy regularization, the proposed algorithms can locate an approximate Nash equilibrium of the unregularized matrix game at a sublinear rate without assuming the Nash equilibrium to be unique. Our methods also lead to efficient policy extragradient algorithms for solving entropy-regularized zero-sum Markov games at a linear rate. All of our convergence rates are nearly dimension-free, which are independent of the size of the state and action spaces up to logarithm factors, highlighting the positive role of entropy regularization for accelerating convergence.

authors:
S. Arora
E. Hazan
S. Kale

title: The multiplicative weights update method: a meta-algorithm and applications

venue: Theory of Computing, 8(1):121–164.

authors:
Y. Bai
C. Jin

title: Provable self-play algorithms for competitive reinforcement learning

venue: International Conference on Machine Learning, pages 551–560. PMLR.

authors:
M. Bowling
M. Veloso

title: Rational and convergent learning in stochastic games

venue: Proceedings of the 17th international joint conference on Artificial intelligence-Volume 2, pages 1021–1026.

authors:
S. Cen
C. Cheng
Y. Chen
Y. Wei
Y. Chi

title: Fast global convergence of natural policy gradient methods with entropy regularization

venue: arXiv preprint arXiv:2007.06558.

authors:
S. Cen
Y. Wei
Y. Chi

title: Fast policy extragradient methods for competitive games with entropy regularization

venue: arXiv preprint arXiv:2105.15186.

authors:
N. Cesa-Bianchi
G. Lugosi

title: Prediction, learning, and games

venue: Cambridge university press.

authors:
C. Daskalakis
A. Deckelbaum
A. Kim

title: Near-optimal no-regret algorithms for zero-sum games

venue: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235–254. SIAM.

authors:
C. Daskalakis
D.J. Foster
N. Golowich

title: Independent policy gradient methods for competitive reinforcement learning

venue: Advances in Neural Information Processing Systems, volume 33, pages 5527–5540.

authors:
C. Daskalakis
A. Ilyas
V. Syrgkanis
H. Zeng

title: Training GANs with optimism

venue: International Conference on Learning Representations (ICLR 2018).

authors:
C. Daskalakis
I. Panageas

title: Last-iterate convergence: Zero-sum games and constrained min-max optimization

venue: arXiv preprint arXiv:1807.04252.

title: The limit points of (optimistic) gradient descent in minmax optimization

venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 9256–9266.

authors:
Y. Freund
R.E. Schapire

title: Adaptive game playing using multiplicative weights

venue: Games and Economic Behavior, 29(1-2):79–103.

authors:
M. Geist
B. Scherrer
O. Pietquin

title: A theory of regularized Markov decision processes

venue: International Conference on Machine Learning, pages 2160–2169.

authors:
I.J. Goodfellow
J. Pouget-Abadie
M. Mirza
B. Xu
D. Warde-Farley
S. Ozair
A. Courville
Y. Bengio

title: Generative adversarial networks

venue: arXiv preprint arXiv:1406.2661.

authors:
P.T. Harker
Pang
J.-S.

title: Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications

authors:
J. Hofbauer
W.H. Sandholm

title: On the global convergence of stochastic fictitious play

authors:
Hsieh
Y.-G.
F. Iutzeler
J. Malick
P. Mertikopoulos

title: On the convergence of single-call stochastic extra-gradient methods

venue: arXiv preprint arXiv:1908.08465.

authors:
V.R. Konda
J.N. Tsitsiklis

title: Actor-critic algorithms

venue: Advances in neural information processing systems, pages 1008–1014. Citeseer.

title: The extragradient method for finding saddle points and other problems

title: Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes

venue: arXiv preprint arXiv:2102.00135.

authors:
Q. Lei
S.G. Nagarajan
I. Panageas
X. Wang

title: Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
T. Liang
J. Stokes

title: Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks

venue: The 22nd International Conference on Artificial Intelligence and Statistics, pages 907–915. PMLR.

title: Markov games as a framework for multi-agent reinforcement learning

venue: Machine Learning Proceedings, pages 157–163. Elsevier.

authors:
R.D. McKelvey
T.R. Palfrey

title: Quantal response equilibria for normal form games

venue: Games and economic behavior, 10(1):6–38.

authors:
J. Mei
C. Xiao
C. Szepesvari
D. Schuurmans

title: On the global convergence rates of softmax policy gradient methods

venue: arXiv preprint arXiv:2005.06392.

authors:
P. Mertikopoulos
B. Lecouat
H. Zenati
Foo
C.-S.
V. Chandrasekhar
G. Piliouras

title: Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

venue: International Conference on Learning Representations.

authors:
P. Mertikopoulos
C. Papadimitriou
G. Piliouras

title: Cycles in adversarial regularized learning

venue: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703–2717. SIAM.

authors:
P. Mertikopoulos
W.H. Sandholm

title: Learning in games via reinforcement and regularization

venue: Mathematics of Operations Research, 41(4):1297–1324.

authors:
A. Mokhtari
A. Ozdaglar
S. Pattathil

title: A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

venue: International Conference on Artificial Intelligence and Statistics, pages 1497–1507. PMLR.

authors:
A. Mokhtari
A.E. Ozdaglar
S. Pattathil

title: Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems

venue: SIAM Journal on Optimization, 30(4):3230–3251.

title: Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems

venue: SIAM Journal on Optimization, 15(1):229–251.

authors:
G. Neu
A. Jonsson
V. Gómez

title: A unified view of entropy-regularized Markov decision processes

venue: arXiv preprint arXiv:1705.07798.

authors:
J. Perolat
B. Scherrer
B. Piot
O. Pietquin

title: Approximate dynamic programming for two-player zero-sum Markov games

venue: International Conference on Machine Learning, pages 1321–1329. PMLR.

authors:
A. Rakhlin
K. Sridharan

title: Optimization, learning, and games with predictable sequences

venue: arXiv preprint arXiv:1311.1869.

authors:
Y. Savas
M. Ahmadi
T. Tanaka
U. Topcu

title: Entropy-regularized stochastic games

venue: 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5955–5962. IEEE.

title: Stochastic games

venue: Proceedings of the National Academy of Sciences, 39(10):1095–1100.

authors:
V. Syrgkanis
A. Agarwal
H. Luo
R.E. Schapire

title: Fast convergence of regularized learning in games

venue: Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2, pages 2989–2997.

title: On linear convergence of iterative methods for the variational inequality problem

venue: Journal of Computational and Applied Mathematics, 60(1-2):237–252.

authors:
Wei
C.-Y
Lee
C.-W
M. Zhang
H. Luo

title: Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. arXiv preprint arXiv:2102.04540

authors:
Wei
C.-Y.
Lee
C.-W.
M. Zhang
H. Luo

title: Linear last-iterate convergence in constrained saddle-point optimization

venue: International Conference on Learning Representations (ICLR).

authors:
Q. Xie
Y. Chen
Z. Wang
Z. Yang

title: Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium

venue: Conference on Learning Theory, pages 3674–3682. PMLR.

authors:
A. Yadav
S. Shah
Z. Xu
D. Jacobs
T. Goldstein

title: Stabilizing adversarial nets with prediction methods

venue: arXiv preprint arXiv:1705.07364.

authors:
W. Zhan
S. Cen
B. Huang
Y. Chen
J.D. Lee
Y. Chi

title: Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence

venue: arXiv preprint arXiv:2105.11066.

authors:
K. Zhang
S. Kakade
T. Basar
L. Yang

title: Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity

venue: Advances in Neural Information Processing Systems, 33.

authors:
Y. Zhao
Y. Tian
J.D. Lee
S.S. Du

title: Provably efficient policy gradient methods for two-player zero-sum Markov games

venue: arXiv preprint arXiv:2102.08903.

heading: 1 Introduction

text:
Finding the equilibrium of competitive games, which can be viewed as constrained saddle-point optimization problems with probability simplex constraints, lies at the heart of modern machine learning and decision making paradigms such as Generative Adversarial Networks (GANs) (Goodfellow et al., 2014), competitive reinforcement learning (RL) (Littman, 1994), game theory (Shapley, 1953), adversarial training (Mertikopoulos et al., 2018b), to name a few.
In this paper, we study one of the most basic forms of competitive games, namely two-player zero-sum games, in both the matrix setting and the Markov setting. Our goal is to find the equilibrium policies of both players in an independent and decentralized manner (Daskalakis et al., 2020; Wei et al., 2021a) with guaranteed last-iterate convergence. Namely, each player will execute symmetric and independent updates iteratively using its own payoff without observing the opponent’s actions directly, and the final policies of the iterative process should be a close approximation to the equilibrium up to any prescribed precision. This kind of algorithms is more advantageous and versatile especially in federated environments, as it requires neither prior coordination between the players like twotimescale algorithms, nor a central controller to collect and disseminate the policies of all the players, which are often unavailable due to privacy constraints.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1.1 Last-iterate convergence in competitive games

text:
In recent years, there have been significant progresses in understanding the last-iterate convergence of simple iterative algorithms for unconstrained saddle-point optimization, where one is interested in bounding the sub-optimality of the last iterate of the algorithm, rather than say, the ergodic iterate — which is the average of all the iterations — that are commonly studied in the earlier literature. This shift of focus is motivated, for example, by the infeasibility of averaging large machine learning models in training GANs (Goodfellow et al., 2014). While vanilla Gradient Descent / Ascent (GDA) may diverge or cycle even for bilinear matrix games (Daskalakis et al., 2018), quite remarkably, small modifications lead to guaranteed last-iterate convergence to the equilibrium in a non-asymptotic fashion. A flurry of algorithms is proposed, including Optimistic Gradient Descent Ascent (OGDA) (Rakhlin and Sridharan, 2013; Daskalakis and Panageas, 2018b; Wei et al., 2021b), predictive updates (Yadav et al., 2017), implicit updates (Liang and Stokes, 2019), and more. Several unified analyses of these algorithms have been carried out (see, e.g. Mokhtari et al. (2020a); Liang and Stokes (2019) and references therein), where these methods in principle all make clever extrapolation of the local curvature in a predictive manner to accelerate convergence. With slight abuse of terminology, in this paper, we refer to this ensemble of algorithms as extragradient methods (Korpelevich, 1976; Tseng, 1995; Mertikopoulos et al., 2018a; Harker and Pang, 1990).
However, saddle-point optimization in the constrained setting, which includes competitive games as a special case, remains largely under-explored even for bilinear matrix games. While it is possible to reformulate constrained bilinear games to unconstrained ones using softmax parameterization of the probability simplex, this approach falls short of preserving the bilinear structure and convexconcave properties in the original problem, which are crucial to the convergence of gradient methods. Therefore, there is a strong necessity of understanding and developing improved extragradient methods in the constrained setting. Daskalakis and Panageas (2018a) proposed the optimistic variant of the multiplicative weight updates (MWU) method (Arora et al., 2012) – which is extremely natural and popular for optimizing over probability simplexes – called Optimistic Multiplicative Weight Updates (OMWU), and established the asymptotic last-iterate convergence of OMWU for matrix games. Very recently, Wei et al. (2021b) established non-asymptotic last-iterate convergences of OMWU. However, these last-iterate convergence results require the Nash equilibrium to be unique, and cannot be applied to problems with multiple Nash equilibria.

heading: 1.2 Our contributions

text:
Motivated by the algorithmic role of entropy regularization in single-agent RL (Neu et al., 2017; Geist et al., 2019; Cen et al., 2020) as well as its wide use in game theory to account for imperfect and noisy information (McKelvey and Palfrey, 1995; Savas et al., 2019), we initiate the design and analysis of extragradient algorithms using multiplicative updates for finding the quantal response equilibrium (QRE), which are solutions to competitive games with entropy regularization (McKelvey and Palfrey, 1995). While finding QRE is of interest in its own right, by controlling the knob of entropy regularization, the QRE provides a close approximation to the Nash equilibrium (NE), and in turn acts as a smoothing scheme for finding the NE. Our contributions are summarized below.
• Near dimension-free last-iterate convergence to QRE of entropy-regularized matrix games. We propose two policy extragradient algorithms to solve entropy-regularized matrix games, namely the Predictive Update (PU) and OMWU methods, where both players execute symmetric and multiplicative updates without knowing the entire payoff matrix nor the opponent’s actions. Encouragingly, we show that the last iterate of the proposed algorithms converges to the unique QRE at a linear rate that is almost independent of the size of the action spaces. Roughly speaking, to find an ϵ-optimal QRE in terms of Kullback-Leibler (KL) divergence, it takes no more than Õ ( 1 ητ log ( 1 ϵ )) iterations,
where Õ(·) hides logarithmic dependencies. Here, τ is the regularization parameter, and η is the learning rate of both players. Maximizing the learning rate, the iteration complexity is bounded by Õ ((1 + ∥A∥∞/τ) log(1/ϵ)), where ∥A∥∞ = maxi,j |Ai,j | is the ℓ∞ norm of the payoff matrix A. • Last-iterate convergence to ϵ-NE of unregularized matrix games without uniqueness assumption. The QRE provides an accurate approximation to the NE by setting the entropy regularization τ sufficiently small, therefore our result directly translates to finding a NE with last-iterate convergence guarantee. Roughly speaking, to find an ϵ-NE (Zhang et al., 2020, Definition 2.1), it takes no more than Õ ( 1 + ∥A∥∞ϵ ) iterations with optimized learning rates, which is again independent of the size
of the action spaces up to logarithmic factors. Unlike prior literature (Daskalakis and Panageas, 2018a; Wei et al., 2021b), our last-iterate convergence guarantee does not require the NE to be unique.
• Extensions to two-player zero-sum Markov games. By connecting value iteration with matrix games, we propose a policy extragradient method for solving infinite-horizon discounted entropyregularized zero-sum Markov games, which finds an ϵ-optimal minimax soft Q-function—in terms of ℓ∞ error—in at most Õ ( 1 τ(1−γ)2 log 2 ( 1 ϵ )) iterations, where γ ∈ (0, 1) is the discount factor.
To the best of our knowledge, our paper is the first that develops policy extragradient algorithms for solving entropy-regularized competitive games with multiplicative updates and dimension-free linear last-iterate convergence, and demonstrates entropy regularization as a smoothing technique to find ϵ-NE without the uniqueness assumption. Table 1 provides detailed comparisons of the proposed methods with prior arts for solving matrix games. Our results highlight the positive role of entropy regularization for accelerating convergence and safeguarding against imperfect information in competitive games. We defer the complete proof of our results to Cen et al. (2021).

heading: 1.3 Related works

text:
Our work lies at the intersection of saddle-point optimization, game theory, and reinforcement learning. In what follows, we discuss a few topics that are closely related to ours.
Unregularized matrix game. Freund and Schapire (1999) showed that many standard methods such as GDA and MWU have a converging average duality gap at the rate of O(1/ √ T ), which is improved to O(1/T ) by considering optimistic variants of these methods, such as OGDA and OMWU (Rakhlin and Sridharan, 2013; Daskalakis et al., 2011; Syrgkanis et al., 2015). However, the last-iterate convergence of these methods are less understood until recently (Daskalakis and Panageas, 2018a; Wei et al., 2021b). In particular, under the assumption that the NE is unique for the unregularized matrix game, Daskalakis and Panageas (2018a) showed the asymptotic convergence of the last iterate of OMWU to the unique equilibrium, and Wei et al. (2021b) showed the last iterate of OMWU achieves a linear rate of convergence after an initial phase of sublinear convergence, however the rates therein can be highly pessimistic in terms of the problem dimension, while our rate for entropy-regularized OMWU is dimension-free up to logarithmic factors.
Saddle-point optimization. Considerable progress has been made towards understanding OGDA and extragradient (EG) methods in the unconstrained convex-concave saddle-point optimization with general objective functions (Mokhtari et al., 2020a,b; Nemirovski, 2004; Liang and Stokes, 2019). However, the last-iterate convergence of constrained convex-concave saddle-point optimization still lacks theoretical understanding in general and most works fall short of characterizing a finite-time convergence result. In particular, Mertikopoulos et al. (2018a) demonstrated the asymptotic lastiterate convergence of EG, and Hsieh et al. (2019) investigated similar questions for single-call EG algorithms. Lei et al. (2021) showed that OMWU converges to the equilibrium locally without
an explicit rate. Wei et al. (2021b) showed that the last-iterate of OGDA converges linearly for strongly-convex strongly-concave constrained saddle-point optimization with an explicit rate.
Entropy regularization in RL and games. In single-agent RL, the role of entropy regularization as an algorithmic mechanism to encourage exploration and accelerate convergence has been investigated extensively (Neu et al., 2017; Geist et al., 2019; Mei et al., 2020; Cen et al., 2020; Lan, 2021; Zhan et al., 2021). Turning to the game setting, entropy regularization is used to account for imperfect information in the seminal work of McKelvey and Palfrey (1995) that introduced the QRE, and a few representative works on entropy and more general regularizations in games include Savas et al. (2019); Hofbauer and Sandholm (2002); Mertikopoulos and Sandholm (2016).
Zero-sum Markov games. There have been a significant recent interest in developing provably efficient self-play algorithms for Markov games, including model-based algorithms (Perolat et al., 2015; Zhang et al., 2020), value-based algorithms (Bai and Jin, 2020; Xie et al., 2020), and policybased algorithms (Daskalakis et al., 2020; Wei et al., 2021a; Zhao et al., 2021). The iteration complexities in prior works (Perolat et al., 2015; Daskalakis et al., 2020; Wei et al., 2021a; Zhao et al., 2021) depend on various notions of concentrability coefficient and therefore can scale quite pessimistically with the problem dimension. Our approach can be regarded as a policy-based algorithm to approximate value iteration, which can be implemented in a decentralized manner with symmetric and multiplicative updates from both players, and the iteration complexity is almost independent of the size of the state-action space.
Notation. We denote by ∆(A) the probability simplex over the set A. We overload the functions such as log(·) and exp(·) to take vector inputs with the understanding that the function is applied in an entrywise manner. For instance, given any vector z = [zi]1≤i≤n ∈ Rn, the notation exp(z) denotes exp(z) := [exp(zi)]1≤i≤n; other functions are defined analogously. Given two probability distributions µ and µ′ over A, the KL divergence from µ′ to µ is defined by KL ( µ ∥µ′ ) := ∑ a∈A µ(a) log µ(a) µ′(a) . Given a matrix A, ∥A∥∞ is used to denote entrywise maximum norm, namely, ∥A∥∞ = maxi,j |Ai,j |. The all-one vector is denoted as 1.

heading: 2 Zero-sum matrix games with entropy regularization

text: We first consider a two-player zero-sum game with bilinear objective and probability simplex constraints, and demonstrate the positive role of entropy regularization in solving this problem. Throughout this paper, let A = {1, . . . ,m} and B = {1, . . . , n} be the action spaces of each player.

heading: 2.1 Background and problem formulation

text:
Zero-sum two-player matrix game. The focal point of this subsection is a constrained two-player zero-sum matrix game, which can be formulated as the following min-max problem (or saddle point optimization problem):
max µ∈∆(A) min ν∈∆(B)
f(µ, ν) := µ⊤Aν, (1)
where A ∈ Rm×n denotes the payoff matrix, µ ∈ ∆(A) and ν ∈ ∆(B) stand for the mixed/randomized policies of each player, defined respectively as distributions over the probability simplex ∆(A) and ∆(B). A pair of policies (µ⋆, ν⋆) is said to be a Nash equilibrium (NE) of (1) if f(µ⋆, ν) ≥ f(µ⋆, ν⋆) ≥ f(µ, ν⋆) for all (µ, ν) ∈ ∆(A)×∆(B). Entropy-regularized zero-sum two-player matrix game. There is no shortage of scenarios where the payoff matrix A might not be known perfectly. In an attempt to accommodate imperfect knowledge of A, McKelvey and Palfrey (1995) proposed a seminal extension to the Nash equilibrium called the quantal response equilibrium (QRE) when the payoffs are perturbed by Gumbel-distributed noise. Formally, this amounts to solving the following matrix game with entropy regularization (Mertikopoulos and Sandholm, 2016):
max µ∈∆(A) min ν∈∆(B)
fτ (µ, ν) := µ ⊤Aν + τH(µ)− τH(ν), (2)
where H(π) = −∑i πi log(πi) denotes the Shannon entropy of a distribution π, and τ ≥ 0 is the regularization parameter. As is well known, the optimal solution (µ⋆τ , ν ⋆ τ ) to (2), dubbed as the QRE,
is unique whenever τ > 0 (due to the presence of strong concavity/convexity), which satisfies the following fixed point equations:µ ⋆ τ (a) = exp([Aν⋆τ ]a/τ)∑m a=1 exp([Aν ⋆ τ ]a/τ) ∝ exp([Aν⋆τ ]a/τ), for all a ∈ A,
ν⋆τ (b) = exp(−[A⊤µ⋆τ ]b/τ)∑n
b=1 exp(−[A⊤µ⋆τ ]b/τ) ∝ exp(−[A⊤µ⋆τ ]b/τ), for all b ∈ B.
(3)
Goal. We aim to efficiently compute the QRE of the entropy-regularized matrix game in a decentralized manner, and investigate how an efficient solver of QRE can be leveraged to find a NE of the unregularized matrix game (1). Namely, we only assume access to “first-order information” as opposed to full knowledge of the payoff matrix A or the actions of the opponent. The information received by each player is formally described in the following sampling oracle. Definition 1 (Sampling oracle for matrix games). For any policy pair (µ, ν) and payoff matrix A, the sampling oracle returns the exact values of µ⊤A and Aν.
Additional notation. For notational convenience, we let ζ represent the concatenation of µ ∈ R|A| and ν ∈ R|B|, namely, ζ = (µ, ν). The solution to (2), which is specified in (3), is denoted by ζ⋆τ = (µ ⋆ τ , ν ⋆ τ ). For any ζ = (µ, ν) and ζ
′ = (µ′, ν′), we shall often abuse the notation and let KL ( ζ ∥ ζ ′ ) = KL ( µ ∥µ′ ) + KL ( ν ∥ ν′ ) . The duality gap of the entropy-regularized matrix game (2) at ζ = (µ, ν) is defined as DualGapτ (ζ) = maxµ′∈∆(A) fτ (µ ′, ν) − minν′∈∆(B) fτ (µ, ν′) which is clearly nonnegative and DualGapτ (ζ ⋆ τ ) = 0. Similarly, let the optimality gap of the entropy-
regularized matrix game (2) at ζ = (µ, ν) be OptGap(ζ) = ∣∣fτ (µ, ν)− fτ (µ⋆τ , ν⋆τ )∣∣.

heading: 2.2 Proposed extragradient methods: PU and OMWU

text:
To begin, assume we are given a pair of policies z1 ∈ ∆(A), z2 ∈ ∆(B) employed by each player respectively. If we proceed with fictitious play, i.e. player 1 (resp. player 2) aims to optimize its own policy by assuming the opponent’s policy is fixed as z2 (resp. z1), the saddle-point optimization problem (2) is then decoupled into two independent min/max optimization problems:
max µ∈∆(A) µ⊤Az2 + τH(µ)− τH(z2) and min ν∈∆(B) z⊤1 Aν + τH(z1)− τH(ν),
which are naturally solved via mirror descent / ascent with KL divergence. Specifically, one step of mirror descent / ascent takes the formµ (t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Az2]a), for all a ∈ A,
ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤z1]b), for all b ∈ B, (4)
where η is the learning rate. The above update rule forms the basis of our algorithm design.
Motivation: a form of implicit updates with linear convergence. It turns out, if we could select the policy pair (z1, z2) = ζ(t+1) := (µ(t+1), ν(t+1)) as the ones to be taken in the future, and call the resulting update rule as the Implicit Update (IU) method:
Implicit Update:
µ (t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν(t+1)]a), for all a ∈ A,
ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ(t+1)]b), for all b ∈ B. (5)
Though unrealistic — since it uses the future updates — it leads to a one-step convergence to the QRE when η = 1/τ (see the optimality condition in (3)). Encouragingly, we have the following linear convergence guarantee of IU when adopting a general learning rate. Proposition 1 (Linear convergence of IU). Assume 0 < η ≤ 1/τ , then for all t ≥ 0, the iterates ζ(t) := (µ(t), ν(t)) of the IU method in (5) satisfy KL ( ζ⋆τ ∥ ζ(t) ) ≤ (1− ητ)tKL ( ζ⋆τ ∥ ζ(0) ) .
In words, the IU method achieves an appealing linear rate of convergence that is independent of the problem dimension. Motivated by this observation, we seek to design algorithms where the policies (z1, z2) employed in (4) serve as good predictions of (µ(t+1), ν(t+1)), such that the resulting algorithms are both practical and retain the appealing convergence rate of IU.
Proposed algorithms. We propose two extragradient algorithms for solving the entropy-regularized matrix game, namely the Predictive Update (PU) method and the Optimistic Multiplicative Weights
Algorithm 1: The PU method 1 initialization: µ(0), ν(0). 2 for t = 0, 1, 2, · · · do 3 Update µ̄ and ν̄ according to{
µ̄(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν(t)]a), ν̄(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ(t)]b).
4 Update µ and ν according to{ µ(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν̄(t+1)]a), ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ̄(t+1)]b).
Algorithm 2: The OMWU method 1 initialization: µ(0) = µ̄(0), ν(0) = ν̄(0). 2 for t = 0, 1, 2, · · · do 3 Update µ̄ and ν̄ according to{
µ̄(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν̄(t)]a), ν̄(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ̄(t)]b).
4 Update µ and ν according to{ µ(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν̄(t+1)]a), ν(t+1)(b) ∝ ν(t)(b)1−ητ exp(−η[A⊤µ̄(t+1)]b).
Update (OMWU) method, the latter adapted from Rakhlin and Sridharan (2013); Daskalakis et al. (2011). Detailed procedures can be found in Algorithm 1 and Algorithm 2, respectively. On a high level, both algorithms maintain two intertwined sequences {(µ(t), ν(t))}t≥0 and {(µ̄(t), ν̄(t))}t≥0, and in each iteration t = 0, 1, . . ., proceed in two steps:
• The midpoint (µ̄(t+1), ν̄(t+1)) serves as a prediction of (µ(t+1), ν(t+1)) by running one step of mirror descent / ascent (cf. (4)) from either (z1, z2) = (µ(t), ν(t)) (for PU) or (z1, z2) = (µ̄(t), ν̄(t)) (for OMWU).
• The update of (µ(t+1), ν(t+1)) then mimics the implicit update (5) using the prediction (µ̄(t+1), ν̄(t+1)) obtained above.
When the proposed algorithms converge, both (µ(t), ν(t)) and (µ̄(t), ν̄(t)) converge to the same point. The two players are completely symmetric and adopt the same learning rate, and require only first-order information provided by the sampling oracle. While the two algorithms resemble each other in many aspects, a key difference lies in the query and use of the sampling oracle: in each iteration, OMWU makes a single call to the sampling oracle for gradient evaluation, while PU calls the sampling oracle twice. It is worth noting that, when τ = 0 (i.e., no entropy regularization is enforced), the OMWU method in Algorithm 2 reduces to the method analyzed in Rakhlin and Sridharan (2013); Daskalakis and Panageas (2018a); Wei et al. (2021b) without entropy regularization.
Remark 1. It is worth highlighting that the proposed algorithms are different from Mertikopoulos et al. (2018a), as the extragradient is only applied to the bilinear term but not the entropy regularization term. This seemingly small, but important, difference leads to a more concise closed-form update rule and a cleaner analysis, as shall be seen momentarily.

heading: 2.3 Performance guarantees

text:
We are now positioned to present our main theorem concerning the last-iterate convergence of PU and OMWU for solving (2).
Theorem 1 (Last-iterate convergence of PU and OMWU). Suppose that the learning rates η = ηPU of PU in Algorithm 1 and η = ηOMWU of OMWU in Algorithm 2 satisfy
0 < ηPU ≤ 1
τ + 2 ∥A∥∞ , and 0 < ηOMWU ≤ min
{ 1
2τ + 2 ∥A∥∞ ,
1
4 ∥A∥∞
} . (6)
Then for any t ≥ 0, the iterates ζ(t) = (µ(t), ν(t)) and ζ̄(t) = (µ̄(t), ν̄(t)) of PU and OMWU achieve • Linear convergence of policies in KL divergence and entrywise log-ratios:
max { KL ( ζ⋆τ ∥ ζ(t) ) , 12KL ( ζ⋆τ ∥ ζ̄(t+1) )} ≤ (1− ητ)tKL ( ζ⋆τ ∥ ζ(0) ) , (7a)∥∥∥∥log ζ(t)ζ⋆τ ∥∥∥∥ ∞ ≤ 2(1− ητ)t ∥∥∥∥log ζ(0)ζ⋆τ ∥∥∥∥ ∞ + 8 ∥A∥∞ τ (1− ητ)t/2KL ( ζ⋆τ ∥ ζ(0) )1/2 . (7b)
• Linear convergence of values in optimality and duality gaps:
OptGapτ (ζ̄ (t)) ≤ η−1 · 1 1− (τ + ∥A∥∞)η · (1− ητ) t 1− (1− ητ)tKL ( ζ⋆τ ∥ ζ(0) ) , (7c)
DualGapτ (ζ̄ (t)) ≤ ( η−1 + 2τ−1∥A∥2∞ ) (1− ητ)t−1KL ( ζ⋆τ ∥ ζ(0) ) . (7d)
Remark 2. Setting µ(0) and ν(0) to be uniform policies leads to a universal bound KL ( ζ⋆τ ∥ ζ(0) ) = log |A|+ log |B| − H(µ⋆τ )−H(ν⋆τ ) ≤ log |A|+ log |B|.
Remark 3. Similar results continue to hold even when the two players use different regularization parameters τµ, τν > 0 in (2), as long as the regularization parameter τ is replaced by max{τµ, τν} in the upper bounds of the learning rate, and the contraction parameter is replaced by 1−min{τµ, τν}η.
Theorem 1 characterizes the convergence of the last-iterates ζ(t) and ζ̄(t) of PU and OMWU as long as the learning rate lies within the specified ranges. While PU doubles the number of calls to the sampling oracle, it also allows roughly as large as twice the learning rate compared with OMWU (cf. (6)). Compared with the vast literature analyzing the average-iterate performance of variants of extragradient methods, our results contribute towards characterizing the last-iterate convergence of multiplicative update methods in the presence of entropy regularization and simplex constraints, which to the best of our knowledge, are the first of its kind. Several remarks are in order.
Linear convergence to QRE. To achieve an ϵ-accurate estimate of the QRE in terms of the KL divergence, the bound (7a) tells that it is sufficient to take
1
ητ log
( log |A|+ log |B|
ϵ ) iterations using either PU or OMWU. Notably, this iteration complexity does not depend on any hidden constants and only depends double logarithmically on the cardinality of action spaces, which is almost dimension-free. Maximizing the learning rate, the iteration complexity is bounded by (1 + ∥A∥∞/τ) log(1/ϵ) (modulo log factors), which only depends on the ratio ∥A∥∞/τ . Entrywise error of the policy log-ratios. Both PU and OMWU enjoy strong entrywise guarantees in the sense we can guarantee the convergence of the ℓ∞ norm of the log-ratios between the learned policy pair and the QRE at the same dimension-free linear rate (cf. (7b)), which suggests the policy pair converges in a somewhat uniform manner across the entire action space.
Linear convergence of optimality and duality gaps. Our theorem also establishes the last-iterate convergence of the game values in terms of the optimality gap (cf. (7c)) and the duality gap (cf. (7d)) for both PU and OMWU. In particular, as will be seen, bounding the optimality gap of matrix games turns out to be the key enabler for generalizing our algorithms to Markov games, and bounding the duality gap allows to directly translate our results to finding a NE of unregularized matrix games.
Last-iterate convergence to approximate NE. The entropy-regularized matrix game can be thought as a smooth surrogate of the unregularized matrix game (1); in particular, it is possible to find an ϵ-NE by setting τ sufficiently small in (2). According to (Zhang et al., 2020, Definition 2.1), a policy pair ζ = (µ, ν) is an ϵ-NE if it satisfies DualGap(ζ) := maxµ′∈∆(A) f(µ′, ν)−minν′∈∆(B) f(µ, ν′) ≤ ϵ.
Observe that setting τ = ϵ/4log |A|+log |B| guarantees that |fτ (µ, ν) − f(µ, ν)| < ϵ/4 uniformly over (µ, ν) ∈ ∆(A)×∆(B) in view of the boundedness of the Shannon entropy H(·). Theorem 7 (cf. (7d)) also ensures that our proposed algorithms find an approximate QRE ζ̄(T ) such that DualGapτ (ζ̄
(T )) ≤ ϵ/2 after taking T = Õ ( 1 ηϵ ) iterations, which is no more than Õ ( 1 + ∥A∥∞ϵ ) iterations with optimized learning rates. It follows immediately that
DualGap(ζ̄(T )) ≤ DualGapτ (ζ̄ (T )) + max
µ′,ν′ ∣∣∣fτ (µ′, ν̄(T ))− fτ (µ̄(T ), ν′)− (f(µ′, ν̄(T ))− f(µ̄(T ), ν′))∣∣∣ ≤ ϵ, and therefore ζ̄(T ) is an ϵ-NE. Intriguingly, unlike prior work (Daskalakis and Panageas, 2018a;
Wei et al., 2021b) that analyzed the last-iterate convergence of OMWU in the unregularized setting (τ = 0), our last-iterate convergence does not require the NE of (1) to be unique.
Rationality. Another attractive feature of the algorithms developed above is being rational (as introduced in Bowling and Veloso (2001)) in the sense that the algorithm returns the best-response
policy of one player when the opponent takes any fixed stationary policy. More specially, in terms of matrix games, when player 2 sticks to a stationary policy ν, the update of player 1 reduces to µ(t+1)(a) ∝ µ(t)(a)1−ητ exp(η[Aν]a). In this case, Theorem 1 can be established in exactly the same fashion by restricting attention only to the updates of µ(t).
No-regret learning of OMWU. Besides convergence to equilibria, in game-theoretical settings, it is often desirable to design and implement no-regret algorithms, which are capable of providing black-box guarantees over arbitrary sequences played by the opponent (Cesa-Bianchi and Lugosi, 2006; Rakhlin and Sridharan, 2013). Fortunately, it turns out that entropy regularization not only accelerates the convergence, but also enables no-regret learning somewhat “for free”: it encourages exploration by putting a positive mass on every action, therefore guards against adversaries. By using a properly chosen learning rate schedule, the proposed OMWU (Algorithm 2) can be further established as a no-regret algorithm; the details can be found in (Cen et al., 2021).

heading: 3 Zero-sum Markov games with entropy regularization

text: Leveraging the success of PU and OMWU in solving the entropy-regularized matrix games, this section extends our current analysis to solve the zero-sum two-player Markov game with entropy regularization, which is again formulated as finding the equilibrium of a saddle-point optimization problem. We start by introducing its basic setup, which will be followed by the proposed policy extragradient method with its theoretical guarantees.

heading: 3.1 Background and problem formulation

text:
We consider a discounted Markov Game (MG) which is defined as M = {S,A,B, P, r, γ}, with discrete state space S, action spaces of two players A and B, transition probability P , reward function r : S × A × B → [0, 1] and discount factor γ ∈ [0, 1). A policy µ : S → ∆(A) (resp. ν : S → ∆(B)) defines how player 1 (resp. player 2) reacts to a given state s, where the probability of taking action a ∈ A (resp. b ∈ B) is µ(a|s) (resp. ν(b|s)). The transition probability kernel P : S ×A×B → ∆(S) defines the dynamics of the Markov game, where P (s′|s, a, b) specifies the probability of transiting to state s′ from state s when the players take actions a and b respectively.
Motivated by entropy regularization in Markov decision processes (MDP) (Geist et al., 2019), we consider an entropy-regularized variant of MG, where the value function is defined as
V µ,ντ (s) := E [ ∞∑ t=0 γt (r(st, at, bt)− τ logµ(at|st) + τ log ν(bt|st)) ∣∣ s0 = s] , (8)
where the quantity τ ≥ 0 denotes the regularization parameter, and the expectation is evaluated over the randomness of the transition kernel as well as the policies. The regularized Q-function Qµ,ντ of a
policy pair (µ, ν) is related to V µ,ντ as Qµ,ντ (s, a, b) = r(s, a, b) + γEs′∼P (·|s,a,b) [ V µ,ντ (s ′) ] . (9)
We will call V µ,ντ and Q µ,ν τ the soft value function and soft Q-function, respectively. A policy pair (µ⋆τ , ν ⋆ τ ) is said to be the quantal response equilibrium (QRE) of the entropy-regularized MG, if its value attains the minimax value of the entropy-regularized MG over all states s ∈ S, i.e.
V ⋆τ (s) = max µ min ν V µ,ντ (s) = min ν max µ
V µ,ντ (s) := V µ⋆τ ,ν ⋆ τ τ (s),
where V ⋆τ is called the optimal minimax soft value function, and similarly Q ⋆ τ := Q
µ⋆τ ,ν ⋆ τ
τ is called the optimal minimax soft Q-function.
Goal. Our goal is to find the QRE of the entropy-regularized MG in a decentralized manner where the players only observe its own reward without accessing the opponent’s actions. By setting the regularization parameter sufficiently small τ , this also allows us to find an approximate NE of the unregularized MG.

heading: 3.2 From value iteration to policy extragradient methods

text:
Entropy-regularized value iteration. It is known that classical dynamic programming approaches such as value iteration can be extended to solve MG (Perolat et al., 2015), where each iteration amounts to solving a series of matrix games for each state. Similar to the single-agent case (Cen et al., 2020), we can extend these approaches to solve the entropy-regularized MG. Setting the stage, let us introduce the per-state Q-value matrix Q(s) := Q(s, ·, ·) ∈ R|A|×|B| for every s ∈ S, where the element indexed by the action pair (a, b) is Q(s, a, b). Similarly, we define the per-state policies µ(s) := µ(·|s) ∈ ∆(A) and ν(s) := ν(·|s) ∈ ∆(B) for both players. In parallel to the original Bellman operator, we denote the soft Bellman operator Tτ as
Tτ (Q)(s, a, b) := r(s, a, b) + γEs′∼P (·|s,a,b) [
max µ(s′)∈∆(A) min ν(s′)∈∆(B)
fτ ( Q(s′);µ(s′), ν(s′) )] ,
where for each per-state Q-value matrix Q(s), we introduce an entropy-regularized matrix game in the form of
max µ∈∆(A) min ν∈∆(B)
fτ ( Q(s);µ(s), ν(s) ) := µ(s)⊤Q(s)ν(s)− τH(µ(s)) + τH(ν(s)).
The entropy-regularized value iteration then proceeds as
Q(t+1) = Tτ (Q(t)), (10)
where Q(0) is an initialization. By definition, the optimal minimax soft Q-function obeys Tτ (Q⋆τ ) = Q⋆τ and therefore corresponds to the fix point of the soft Bellman operator. Given the above entropyregularized value iteration, the following lemma states its iterates contract linearly to the optimal minimax soft Q-function at a rate of the discount factor γ. Proposition 2. The entropy-regularized value iteration (10) converges at a linear rate, i.e. ∥Q(t) − Q⋆τ∥∞ ≤ γt∥Q(0) −Q⋆τ∥∞.
Approximate value iteration via policy extragradient methods. Proposition 2 suggests that the optimal minimax soft Q-function of the entropy-regularized MG can be found by solving a series of entropy-regularized matrix games induced by {Q(t)}t≥0 in (10), a task that can be accomplished by adopting the fast extragradient methods developed earlier. To proceed, we first define the following sampling oracle, which makes it rigorous that the proposed algorithm does not require access to the Q-function of the entire MG, but only its own single-agent Q-function when playing against the opponent’s policy. Definition 2 (Sampling oracle for Markov games). Given any policy pair µ(s), ν(s) and Q-value matrix Q(s) for any s ∈ S, the sampling oracle returns
[Q(s)ν(s)]a = Eb∼ν(s) [Q(s, a, b)] , and [Q(s)⊤µ(s)]b = Ea∼µ(s) [Q(s, a, b)]
for any a ∈ A and b ∈ B.
Algorithm 3: Policy Extragradient Method for Entropy-regularized Markov Game 1 initialization: Q(0) = 0. 2 for t = 0, 1, 2, · · · , Tmain do 3 Let Q(t) denote
Q(t)(s, a, b) = r(s, a, b) + γEs′∼P (·|s,a,b)V (t)(s′). (11)
4 Invoke PU (Algorithm 1) or OMWU (Algorithm 2) for Tsub iterations to solve the following entropy-regularized matrix game for every state s, where the initialization is set as uniform distributions:
max µ(s)∈∆(A) min ν(s)∈∆(B)
fτ ( Q(t)(s);µ(s), ν(s) ) .
Return the last iterate µ̄(t,Tsub)(s), ν̄(t,Tsub)(s). 5 Set V (t+1)(s) = fτ ( Q(t)(s); µ̄(t,Tsub)(s), ν̄(t,Tsub)(s) ) .
Encouragingly, by judiciously setting the number of iterations in both the outer loop (for updating the Q-value matrices) and the inner loop (for updating the QRE of the corresponding Q-value matrix), we are guaranteed to find the QRE of the entropy-regularized MG in a small number of iterations without solving the iteration-varying matrix games exactly, as dictated by the following theorem.
Theorem 2. Assume |A| ≥ |B| and τ ≤ 1. Setting η = 1−γ2(1+τ(log |A|+1−γ)) , the total iterations (namely, the product Tmain · Tsub) required for Algorithm 3 to achieve ∥∥Q(Tmain) −Q⋆τ∥∥∞ ≤ ϵ is at most O ( (log |A|+1/τ)
(1−γ)2 ( log log |A|(1−γ)ϵ )2) .
Theorem 2 ensures that within Õ (
1 τ(1−γ)2 log 2 ( 1 ϵ )) iterations, Algorithm 3 finds a pair of policies
whose value is close to the optimal minimax soft Q-function Q⋆τ in an entrywise manner to a prescribed accuracy ϵ. Remarkably, the iteration complexity is independent of the dimensions of the state space and the action space (up to log factors).
Remark 4 (Duality gap and solving the unregularized MG). Solving the entropy-regularized MG provides a viable strategy to find an ϵ-approximate NE of the unregularized MG, where the optimality of a policy pair is typically gauged by the duality gap. Fortunately, this can be achieved similar to the case of matrix games, and we refer interested readers to Cen et al. (2021) for details.

heading: 4 Conclusions

text:
This paper develops provably efficient policy extragradient methods (PU and OMWU) for entropyregularized matrix games and Markov games, whose last iterates are guaranteed to converge linearly to the quantal response equilibrium at a linear rate. Encouragingly, the rate of convergence is independent of the dimension of the problem, i.e. the sizes of the space space and the action space. In addition, the last iterates of the proposed algorithms can also be used to locate Nash equilibria for the unregularized competitive games without assuming the uniqueness of the Nash equilibria by judiciously tuning the amount of regularization. This work opens up interesting opportunities for further investigations of policy extragradient methods for solving competitive games. For example, can we develop a two-time-scale policy extragradient algorithms for Markov games where the Qfunction is updated simultaneously with the policy but potentially at a different time scale, using samples, such as in an actor-critic algorithm (Konda and Tsitsiklis, 2000)?
Acknowledgments and Disclosure of Funding
S. Cen and Y. Chi are supported in part by the grants ONR N00014-18-1-2142 and N00014-19-12404, ARO W911NF-18-1-0303, NSF CCF-1901199, CCF-2007911 and CCF-2106778. Y. Wei is supported in part by the NSF grants CCF-2007911, DMS-2147546/2015447 and CCF-2106778.

title: Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization