Team Variance Optimization of n n -Player Stochastic Games with Separately Controlled Chains

Li Xia · 2025

Read Team Variance Optimization of n n -Player Stochastic Games with Separately Controlled Chains by Li Xia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22335.txt.

Introduction

Li Xia, writing alone in two thousand twenty-five, studies games where each of many players runs their own chain of states. All share one aim: to keep the spread of their joint gains low. No player sees the others' states or acts. Since the spread aim is not a sum over steps, the classic step rule fails. Xia draws diff and slope forms for how the aim moves when a plan is nudged. He proves a steady pure best-reply plan exists, and gives a two-level tuning method.

Catalog record

CREATORLi Xia
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22335

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Team Variance Optimization of n n -Player Stochastic Games with Separately Controlled Chains Li Xia Abstract In this paper, we study a subclass of n n -player stochastic games, in which each player has their own internal state controlled only by their own action and their objective is a common goal called team variance which measures the total variation of the random rewards of all players. It is assumed that players cannot observe each others’ state/action. Thus, players’ internal chains are controlled separately by their own action and they are coupled through the objective of team variance. Since the variance metric is not additive or Markovian, the dynamic programming principle fails in this problem. We study this problem from the viewpoint of sensitivity-based optimization. A difference formula and a derivative formula for team variance with respect to policy perturbations are derived, which provide sensitivity information to guide decentralized optimization. The existence of a stationary pure Nash equilibrium policy is derived. We further develop a bilevel optimization algorithm that iteratively updates the team mean at the outer level and minimizes the team variance at the inner level, where the team mean serves as a signal to coordinate the optimization of n n players in a decentralized manner. We prove that the algorithm can converge to a strictly local minimum or a first-order stationary point in the space of mixed policies. Finally, we demonstrate the effectiveness of our approach using a numerical experiment of energy management in smart grid, where the assumption of separately controlled chains holds naturally. Keywords : Markov decision process, stochastic game, team variance, sensitivity-based optimization, decentralized optimization 1 Introduction Variance is a widely adopted metric to measure the deviation of a random variable. It can be used as an optimization objective when the stability, safety, or risk of systems is concerned. For Markov decision processes (MDPs) or reinforcement learning, the system rewards are a series of random variables controlled by policies and the classical optimization objective is the expectation of these random rewards. However, it is reasonable to consider other metrics of random rewards such that the policy optimization is superior, which belongs to the framework of risk-sensitive MDPs or even distributional reinforcement learning ( Bellemare et al. 2023 ) . Such framework of risk-sensitive decision-making is particularly useful for applications where uncertainty and variability are critical, such as finance, supply chain management, and robotics. Some widely adopted risk measures in risk-sensitive MDPs include variance ( Sobel 1982 ; Xia 2020 ) , exponential utility function ( Howard and Matheson 1972 ; Borkar and Meyn 2002 ; Cavazos-Cadena et al. 2023 ; Blancas-Rivera and Jasso-Fuentes 2024 ) , value-at-risk (VaR) ( Li et al. 2022 ) , conditional value-at-risk (CVaR) ( Bäuerle and Ott 2011 ; Xia et al. 2023 ) , probability ( White 1993 ; Wen et al. 2024 ) , prospect theory ( Etesami et al. 2018 ; Wu and Zhang 2024 ) , etc. When variance is adopted as a risk metric, it is referred to as the mean-variance optimization in MDPs, which suffers from the failure of dynamic programming principle caused by the non-additivity or non-separable property of variance metrics. Some pioneering works about variance-related MDPs refer to Sobel 1982 and Filar et al. 1989 . There are a series of relevant works along this research stream where the variance-constrained or variance-penalized mean metrics of MDPs are studied with the aid of mathematical programming ( White 1992 ; Chung 1994 ; Sobel 1994 ; Borkar 2024 ) . Another research stream is directly studying the variance-related criterion of MDPs in a restricted policy set where the mean metric already reaches its optimum value ( Hernández-Lerma et al. 1999 ; Guo and Song 2009 ; Huang 2018 ; Xia 2018 ) . Reinforcement learning is also a research stream to study the variance-related risk measure in stochastic dynamic systems ( Tamar et al. 2012 ; Prashanth and Ghavamzadeh 2013 ; Bisi et al. 2020 ) , where policy gradient-based algorithms are usually employed to do optimization in a data-driven manner. Furthermore, in financial engineering, there also exists a stream of research efforts that study the mean-variance optimization for multi-period portfolio selection problems ( Li and Ng 2000 ; Zhou and Li 2000 ; Zhou and Yin 2004 ) , where an embedding method is proposed to particularly solve this portfolio model in the framework of stochastic control. Nevertheless, the problem of variance optimization of stochastic dynamic systems is still challenging, especially on the issues of algorithmic study and efficient computation of optimal policies. The aforementioned literature focuses on the optimization of variance-related risk metrics in the scenario of a single decision-maker. It is a natural extension to consider risk metrics in the scenario of multiple decision-makers, which is called risk-sensitive stochastic games in mathematics or multi-agent reinforcement learning in computer science. However, stochastic games and multi-agent reinforcement learning have significant challenges caused by the coupling behaviors of joint actions of multiple decision-makers, which makes the decision-making environment not stationary for each individual decision-maker. Local information observation is another significant challenge, since it widely exists that each decision-maker only observes its own local information and has no willingness or communication capability to share their information. Constrained by these challenges, most of the existing literature in stochastic games and multi-agent reinforcement learning focuses on the risk-neutral objectives, i.e., the expectation of random rewards. The studies of multi-agent reinforcement learning concentrate on the sample efficiency and learning capability to find \epsilon -approximate Nash equilibrium (NE) policies, and can be categorized into cooperative algorithms (such as team games or potential games) and noncooperative algorithms (such as zero-sum or general-sum games). Since the remarkable success of AlphaGo, a substantial and growing body of literature on multi-agent reinforcement learning has emerged. Yongacoglu et al. 2021 present a two-timescale Q-learning algorithm that achieves team optimality in a stochastic team game under full state observability but no action sharing, and the algorithm’s provable convergence is also provided. Yan et al. 2024 provably find lower confidence bounds and sample complexity results for a model-based reinforcement learning algorithm that can find an \epsilon -approximate NE of a two-player zero-sum Markov game. For a comprehensive understanding on the theories and algorithms of multi-agent reinforcement learning, audience can refer to a recent survey by Zhang et al. 2021 . For stochastic games, more attention has been paid to the analysis of mathematical models and the existence of equilibrium policies. Considering the aforementioned challenges in stochastic games, some special structures are usually assumed to leverage the rigorous analysis and proofs. For example, Etesami 2024 aims to find stationary NE policies in a local information observable n -player stochastic game, with assumption that players’ internal chains are driven by independent transition probabilities. The author develops polynomial-time learning algorithms based on dual averaging and dual mirror descent, and demonstrates the effectiveness of finding an \epsilon -NE policy using numerical experiments for energy management in smart grid. In contrast to the risk-neutral objectives, there exists much less literature studying the risk-sensitive stochastic games with variance-related risk measures, where players seek to maximize expected rewards (mean) while simultaneously minimizing variability (variance) in outcomes. The fundamental difficulties include the non-stationarity and the

Read the complete text