An official website of the United States government
We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an ϵ-Nash equilibrium with time complexity O(1ϵ2), given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with ~O(1mins,aπ(a|s)δ) sample complexity to achieve δ approximation error w.r.t~the ℓ2 norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of ~O(1/ϵ5). Simulation studies are presented.
more »
« less
A characterization of nested canalyzing functions with maximum average sensitivity
Nested canalyzing functions (NCFs) are a class of Boolean functions which are used to model certain biological phenomena. We derive a complete characterization of NCFs with the largest average sensitivity, expressed in terms of a simple structural property of the NCF. This characterization provides an alternate, but elementary, proof of the tight upper bound on the average sensitivity of any NCF established by Klotz et al. (2013). We also utilize the characterization to derive a closed form expression for the number of NCFs that have the largest average sensitivity.
more »
« less
- Award ID(s):
- 1633028
- PAR ID:
- 10067739
- Date Published:
- Journal Name:
- Discrete applied mathematics
- ISSN:
- 1872-6771
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The North American Newark Canyon Formation (NCF; ∼113–98 Ma) presents an opportunity to examine how terrestrial carbonate facies reflect different aspects of paleoclimate during one of the hottest periods of Earth's history. The lower NCF type section preserves heterogeneous palustrine facies and the upper NCF preserves lacustrine deposits. We combined carbonate facies analysis withδ13C,δ18O, and Δ47data sets to assess which carbonate facies preserve stable isotope signals that are most representative of climatic conditions. Palustrine facies record the heterogeneity of the original wetland environment in which they formed. Using the pelmicrite facies that formed in deeper wetlands, we interpret a lower temperature zone (35–40°C) to reflect warm season water temperatures. In contrast, a mottled micrite facies which formed in shallower wetlands records hotter temperatures (36–68°C). These hotter temperatures reflect radiatively heated “bare‐skin” temperatures that occurred in a shallow depositional setting. The lower lacustrine unit has been secondarily altered by hydrothermal fluids while the upper lacustrine unit likely preserves primary temperatures andδ18Owaterof catchment‐integrated precipitation. Resultantly, the palustrine pelmicrite and lacustrine micrite are the facies most likely to reflect ambient climate conditions, and therefore, are the best facies to use for paleoclimate interpretations. Average warm season water temperatures of 41.1 ± 3.6°C and 37.8 ± 2.5°C are preserved by the palustrine pelmicrite (∼113–112 Ma) and lacustrine micrite (∼112–103 Ma), respectively. These data support previous interpretations of the mid‐Cretaceous as a hothouse climate and demonstrate the importance of characterizing facies for identifying the data most representative of past climates.more » « less
-
Abstract The timing of deformation and deposition within syntectonic basins provides critical information for understanding the evolution of strain in mountain belts. In the U.S. Cordillera, contractional deformation was partitioned between the Sevier thrust belt in Utah and several structural provinces in the hinterland in Nevada. One hinterland province, the Central Nevada thrust belt (CNTB), accommodated up to ∼15 km of shortening; however, in most places, this deformation can only be bracketed between Permian and Eocene. Cretaceous deposits of the Newark Canyon Formation (NCF), which are sparsely exposed along the length of the CNTB, offer the opportunity to constrain deformation timing. Here, we present mapping and U-Pb zircon geochronology from the NCF in the Diamond Mountains, which demonstrate deposition of the NCF during proximal CNTB deformation. Deposition of the basal NCF member was under way no earlier than ca. 114 Ma, a tuff in the middle part of the section was deposited at ca. 103 Ma, and the youngest member was deposited no earlier than ca. 99 Ma. Intraformational angular unconformities and abrupt along- and across-strike thickness changes indicate that NCF deposition was related to growth of an east-vergent fault-propagation fold. Clast compositions define unroofing of upper Paleozoic sedimentary rocks, which we interpret as the progressive erosion of an anticline ∼10 km to the west. CNTB deformation was contemporaneous with shortening in the Sevier thrust belt, which defines middle Cretaceous strain partitioning between frontal and interior components of the Cordillera. Strain partitioning may have been promoted by renewed underthrusting during a period of high-flux magmatism.more » « less
-
Abstract Documenting the spatio‐temporal progression of deformation within fold‐thrust belts is critical for understanding orogen dynamics. In the North American Cordillera, the geometry, magnitude, and timing of contractional deformation across a broad region of Nevada known as the “Sevier hinterland” has been difficult to characterize due to minimal exposures of syn‐contractional sedimentary rocks and overprinting of Cenozoic extension. To address this, we present geologic mapping and U‐Pb zircon geochronology from three exposures of the Cretaceous Newark Canyon Formation (NCF) in central Nevada. In the Cortez Mountains, NCF deposition between ∼119 and 110 Ma is hypothesized to be related to generation of relief by thrusting/folding to the west. In the Fish Creek Range, NCF deposition between ∼130 and 100 Ma was related to motion on an east‐vergent thrust fault. In the Pancake Range, NCF deposition is bracketed between ∼129 and 66 Ma and post‐dated east‐vergent folding. We incorporate these timing constraints into a compilation of deformation timing in the Sevier hinterland. Late Jurassic (∼165 and 155 Ma) shortening, which is largely post‐dated shortening in the Luning‐Fencemaker thrust belt to the west and pre‐dated initial deformation in the Sevier fold‐thrust belt to the east, is interpreted to represent diffuse, low‐magnitude deformation that accompanied eastward propagation of the basal Cordilleran décollement. Cretaceous (∼130 and 75 Ma) hinterland shortening, which includes deformation associated with NCF deposition, was contemporaneous with shortening in the Sevier fold‐thrust belt. This is interpreted to represent long‐duration strain partitioning between the foreland and hinterland during continued coupling above the basal décollement and the progressive westward underthrusting of thick North American lower‐middle crust.more » « less
-
Discrete graphical dynamical systems serve as effective formal models in many contexts, including simulations of agent-based models, propagation of contagions in social networks and study of biological phenomena. A class of Boolean functions, called nested canalyzing functions (NCFs), has been used as a good model of certain biological phenomena. Motivated by these biological applications, we study a variety of analysis problems for synchronous graphical dynamical systems (SyDSs) over the Boolean domain, where each local function is an NCF. Each analysis problem involves testing whether the phase space of a given SyDS satisfies a certain property. We present intractability results for some properties as well as efficient algorithms for others. In several cases, our results clearly delineate intractable and efficiently solvable versions of problemsmore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
