Rafael F Cunha
email: r.f.cunha@rug.nl

Jacopo Castellini
email: jacopo.castellini@insa-lyon.fr

Johan Peralez
email: johan.peralez@insa-lyon.fr

Jilles S Dibangoye
email: j.s.dibangoye@rug.nl

On Convex Optimal Value Functions For POSGs

Multi-agent planning and reinforcement learning can be challenging when agents cannot see the state of the world or communicate with each other due to communication costs, latency, or noise. Partially Observable Stochastic Games (POSGs) provide a mathematical framework for modelling such scenarios. This paper aims to improve the efficiency of planning and reinforcement learning algorithms for POSGs by identifying the underlying structure of optimal state-value functions. The approach involves reformulating the original game from the perspective of a trusted third party who plans on behalf of the agents simultaneously. From this viewpoint, the original POSGs can be viewed as Markov games where states are occupancy states, i.e., posterior probability distributions over the hidden states of the world and the stream of actions and observations that agents have experienced so far. This study mainly proves that the optimal state-value function is a convex function of occupancy states expressed on an appropriate basis in all zero-sum, common-payoff, and Stackelberg POSGs.

Introduction

The Partially Observable Stochastic Game (POSG) framework is widely used for formalizing problems in multi-agent sequential decision-making [START_REF] Harsanyi | Games with Incomplete Information Played by "Bayesian" Players[END_REF][START_REF] Hansen | Dynamic programming for partially observable stochastic games[END_REF][START_REF] Shoham | Multiagent systems: Algorithmic, game-theoretic, and logical foundations[END_REF]. This framework is designed to address situations where multiple agents interact with each other to control a dynamic environment and optimize their individual preferences despite stochasticity and sensing uncertainty. Recently, researchers have focused on the subclasses of zero-sum, common-payoff, and Stackelberg POSGs (st-POSGs) [START_REF] Von | Theory of Games and Economic Behavior[END_REF][START_REF] Daniel | The complexity of decentralized control of Markov decision processes[END_REF][START_REF] Tambe | Security and game theory: algorithms, deployed systems, lessons learned[END_REF]. Various approaches have been developed to solve POSGs, with many relying on dynamic programming. These approaches aim to find a solution for the original game by recursively finding solutions for its subgames. However, often solutions of interest exist within a continuum, which requires leveraging uniform continuity properties of optimal state-value functions. Unfortunately, there is a lack of knowledge regarding the uniform continuity properties of optimal state-value functions, which can make it challenging to generalize knowledge from one partial solution to another, restricting the efficiency of existing techniques.

Recent advancements in studying optimal state-value functions for games have showcased innovative ways to generalize knowledge from past experiences. These approaches utilize uniform continuity properties, providing insights into the underlying structure of optimal state-value functions for specific games. The structural analysis of optimal state-value functions can be traced back to the seventies, with [START_REF] Smallwood | The optimal control of partially observable Markov decision processes over a finite horizon[END_REF] demonstrating that the optimal state-value functions of finite-horizon Partially Observable Markov Decision Processes (POMDPs) are piecewise linear and convex functions of belief states. This discovery paved the way for a collection of efficient algorithms, including those developed by [START_REF] Smith | Point-based POMDP algorithms: Improved analysis and implementation[END_REF], [START_REF] Pineau | Anytime point-based approximations for large POMDPs[END_REF], [START_REF] Shani | A survey of point-based POMDP solvers[END_REF]. As such, many authors have since investigated the underlying structure of optimal value functions for subclasses of finite-horizon POSGs. For instance, [START_REF] Gmytrasiewicz | A framework for sequential planning in multiagent settings[END_REF] have shown that piecewise linearity and convexity of optimal state-value functions of belief states extends to Interactive Partially Observable Markov Decision Processes (I-POMDPs). Fehr et al. [2018] demonstrates that POMDPs with Lipschitz reward functions have Lipschitz-continuous near-optimal value functions. Similarly, [START_REF] Jilles | Scaling up decentralized MDPs through heuristic search[END_REF][START_REF] Jilles | Optimally solving dec-POMDPs as continuous-state MDPs[END_REF] have proven that the optimal state-value functions of finite-horizon common-payoff POSGs (dec-POMDPs) are piecewise linear and convex functions of occupancy states on the standard basis. In finite-horizon one-sided zero-sum POSGs (zs-POSGs), [START_REF] Sylvain Sorin | Stochastic games with incomplete information[END_REF], [START_REF] Horák | zero-sum partially observable stochastic games[END_REF] have demonstrated the convexity of the optimal state-value function over belief states. Moreover, Wiggers et al. [2016] have established the linearity of optimal state-value functions of finitehorizon best-response problems in the space of distributions over the histories of an agent. Recently, [START_REF] Delage | and common-reward partially observable stochastic games[END_REF] have complemented this linearity property by demonstrating the Lipchitz-continuity, which generalizes values between occupancy states for finite-horizon zs-POSGs.

It is worth noting that uniform continuity properties are not all equal. For instance, the linearity property highlighted in [START_REF] Auke | Structure in the value function of two-player zero-sum games of incomplete information[END_REF] does not facilitate the generalization of values from one experience to another. Utilizing this property in isolation proves challenging. Undoubtedly, the Lipchitz-continuity property from [START_REF] Delage | and common-reward partially observable stochastic games[END_REF] is useful in generalizing values across different experiences. However, it is worth noting that this approach can sometimes result in poor generalization. Generally, the stronger the uniform continuity property, the better. Unfortunately, there is no constructive approach for revealing the underlying structure of optimal state-value functions. Presently, exhibiting a uniform continuity property appears more like an art than science. This paper introduces a methodology for identifying the underlying structure of optimal state-value functions to address this bottleneck and enhance the ability to create efficient planning and reinforcement learning algorithms for finite-horizon POSGs. The approach involves reformulating the original game from the perspective of a trusted third party who plans on behalf of the agents simultaneously. From this viewpoint, the original finite-horizon POSGs can be viewed as finite-horizon Markov games where states are occupancy states, which are posterior probability distributions over the hidden states of the world and the stream of actions and observations that agents have experienced so far (i.e., their private histories). Contributions. This study provides a proof that the optimal state-value function for the best-response problem, specifically for a slave game, is piecewise linear and convex over occupancy states when expressed on the standard basis, and linear over occupancy states when expressed appropriately. Additionally, the study presents the uniform continuity properties of optimal state-value functions for certain well-known subclasses of finite-horizon POSGs, which are master games. Specifically, when expressed appropriately, the optimal state-value functions for two subclasses of POSGs, namely zs-POSGs and st-POSGs, are convex over occupancy states. These uniform continuity properties are stronger than the previous ones. Moreover, the study demonstrates that the optimal state-value functions of dec-POMDPs are piecewise linear and convex over occupancy states when expressed on the standard basis-a property originally established by [START_REF] Jilles | Optimally solving dec-POMDPs as continuous-state MDPs[END_REF]. We instead provide a simpler proof. The authors emphasize the tightness of these properties, which is evidenced by the fact that they match pre-existing results in narrower settings under further assumptions. The study highlights a methodology to reveal uniform continuity properties of optimal value functions of master games, which is perhaps the most significant takeaway of this paper. This methodology comprises a series of transformations that produce three models for master and slave games, each sufficient to solve the others optimally. However, the last master and slave game formulations make it possible to exhibit uniform continuity properties that were not possible with the previous ones, yet the sufficiency of the former required the introduction of the latter. The key to establishing uniform continuity properties for master games appears to be the ability to appropriately express the optimal value function of the master games with those of the slave games. The authors hope that these findings will serve as a foundation for more efficient planning and reinforcement learning algorithms to exploit the structural properties inherent in POSGs.

The current paper is structured as follows, with each section delving into a unique representation of master and slave games, as illustrated in Figure 1. Section 2 presents a formal description of these games, along with the relevant solution concepts. It also introduces the notations used throughout the document, preliminary properties, and Bellman's equations for the state-and action-value functions under fixed joint policies. In Section 3, a reformulation of master and slave games from the perspective of a trusted third party (or central planner) who plans on behalf of the agents is presented, providing a framework for optimal decision-making at the planning phase and decentralized decision-making at the execution phase. Section 4 examines the connections between master and slave games through summaries of the central planner's knowledge, namely occupancy states. Finally, the main results of this paper are provided in Section 5. The convexity properties of the optimal state-value functions of all slave and master games are presented here. The paper concludes with a discussion on the potential impact of the current findings.

Background

This section formally describes master and slave games and the solution concepts of interest. Additionally, this section introduces the notation used throughout the document, preliminary properties, and Bellman's equations for the state-and action-value functions.

Notation. This paper uses uppercase letter Y to refer to random variables and lowercase letter y to refer to their realizations. The corresponding domains are represented by calligraphic uppercase letter Y. When we want to represent a vector containing all values of y between two integers t 0 and t 1 , we use the notation y t 0 :t 1 . Similarly, y i 0 :i 1 represents a shorthand notation for the vector (y i 0 , . . . , y i 1 ), where i 0 and i 1 are integers satisfying i 0 ≤ i 1 . If i 1 < i 0 , we represent this as y i 1 :i 0 . = ∅. However, when we want to represent the Cartesian product of all values of domains Y i 0 , . . . , Y i 1 between two integers i 0 and i 1 , we use the notation Y i 0 :i 1 .

= Y i 0 × . . . × Y i 1 . We use subscripts to represent control interval indexes and superscripts to index agents. The probability of an event is denoted by Pr{•}, and the expectation of a random variable is represented by E{•}. When dealing with a finite set Y, we represent the cardinality of Y with |Y|, and N ≤|Y| as a set of integers ranging from 0 to |Y|. Additionally, P(Y) represents the (|Y| -1)-dimensional real simplex. The set-theoretic support of a function f : Y → R is represented by supp(f ), which is the set of points in Y where f is non-zero. We use the short-hand notations y i 0 : and y :i 1 to represent the vector y i 0 :n and y 0:i 1 , respectively, where i 0 and i 1 are integers satisfying i 0 , i 1 ∈ N ≤n . Finally, we use the Kronecker delta δ • (•) : Y 0 × Y 1 → {0, 1} in our calculations.

Master Games as POSGs

This subsection will discuss finite-horizon POSGs and their solution concepts, including the Bellman's equations. To help readers better understand the concepts presented in this paper, we will use a simple toy master game called the tiger problem, illustrated in Figure 2.

Example 1. In the tiger problem, there are two doors, one hiding a tiger named Hobbes, and the other hiding a pile of gold. Two agents, Calvin and Susie, aim to determine which door contains the treasure so that they can claim it as quickly as possible. The tiger can be on the left, referred to as x tl , or on the right, referred to as x tr . The agents can perform one of three actions: u ol (open left), u or (open right), and u l (listen). Even after opening a door, there are only two possible observations for each agent: to hear the tiger on the left, z hl , or to hear the tiger on the right, z hr . If both agents perform u l , the state of the world remains unchanged. However, any other joint action results in a transition to either state with a probability of 0.5, effectively resetting the problem. When the world is in state x tl , the joint action (u l , u l ) results in observation z hl for any agent with a probability of 0.85 and observation z hr with a probability of 0.15. This applies similarly for state x tr . Regardless of the state, all other joint actions result in either observation with a probability of 0.5. In a POSG, schematically depicted in Figure 3, agents begin with uncertain knowledge about the game's initial belief state, which is determined by the initial belief state s 0 , i.e., a distribution over hidden states. At each time step, the game is in a particular state x, and each agent i can choose an action u i from their action space. The game then responds by transitioning to a new state x ′ , based on the actions of all agents u, and a transition probability distribution (p u x,x ′ ) x,x ′ ∈X ,u∈U . Additionally, each agent i receives an immediate reward r i xu and individual observation z i , based on joint observation z and an observation probability distribution (p u,z

p u,z x ′ p u,z x ′ p u,z x ′ p u,z x ′ p u,z x ′ p u,z x ′ State start State State Observation 1 Reward 1 Observation 1 Reward 1 Observation 1 Reward 1 Observation 2 Reward 2 Observation 2 Reward 2 Observation 2 Reward 2 Action 1 Action 1 Action 2 Action 2 Time t t+1 t+2 Hidden Agent 1's viewpoint Agent 2's viewpoint p u x,x ′ p u x,x ′ p u x,x ′
x ′ ) x ′ ∈X ,u∈U ,z∈Z , providing them with potentially incomplete and noisy knowledge about the game's current state x ′ . This process continues until the horizon is exhausted. Definition 1. A n-agent, partially observable stochastic game (POSG) is given by a tuple M . = (X , U, Z, p, r). The set X represents a finite collection of hidden states, denoted as x. The finite set of joint actions is denoted as U = U 1: , and the actions taken by the agents are denoted as u = u 1:n . The finite set of observations is denoted as Z = Z 1: , and the observations made by the agents are denoted as z = z 1:n . The transition function p u,z

x,x ′ is given by p u

x,x ′ • p u,z x ′ , and specifies the probability of the process state being x ′ and having observation z after taking action u in hidden state x. The reward function r x,u specifies the reward vector r 1:n

x,u received by the agents after they take joint action u in state x.

Assumptions. Throughout the paper, we assume that the process described by M operates under the following conditions: the observation space of each agent i is made up of a public subspace and a private subspace, denoted as Z i = W × Zi , cf. [START_REF] Kovařìk | Rethinking formal models of partially observable multiagent decision making[END_REF].

The public observations are accessible to all agents. Additionally, rewards are bounded on both sides, with a positive scalar c such that ∥r

•,• ∥ ∞ ≤ c.
The planning horizon, referred to as ℓ, is finite. However, if an infinite-horizon solution is required, any ℓ-horizon solution where ℓ = ⌈log γ ((1 -γ)ϵ/c)⌉ can provide an ϵ-close approximation to any infinite-horizon solution. This finding holds for a discount factor γ ∈ [0, 1) and scalar ϵ > 0.

ς i 0 ς i,1 1 ς i,|U i ||Z i | 1 • • • • • • depth ℓ branching |U i ||Z i |
Figure 4: A ℓ-step policy tree captures a sequence of ℓ time steps, each of which can be conditioned on the outcome of previous decisions. Each node is labelled with the decision made if it is reached.

The goal of solving game M is to identify a joint policy that satisfies a specific criterion based on the problem at hand. This involves determining a series of individual decision rules for each agent, denoted by a 1:n 0:ℓ-1 or simply a 0: . Under a joint policy, every time step t, each agent i follows a unique private decision rule a i t : o i t → ς i t , where ς i t ∈ P(U i ), which is dependent on the t-step private history o i t . = (u i 0:t-1 , z i 1:t ), with the first private history being o i 0 . = ∅, as shown in Figure 4. Every joint policy a 0: will have a performance index induced by state-value functions υ a 0: M,γ,0: that are defined as follows.

Definition 2. For every agent i, the t-step state-value function υ i,at: M,γ,t : X × O t → R under the joint policy a t: is given by: for any arbitrary hidden state x t and joint history o t ,

υ i,at: M,γ,t (x t , o t ) . = E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |x t , o t , a t: }, with boundary condition υ • M,γ,ℓ (•) . = 0.
One can extend Definition 2 by abuse of notation to hold over posterior probability distributions over hidden states and histories as follows.

Definition 3. For every agent i, the t-step state-value function υ i,at: M,γ,t : P(X × O t ) → R under joint policy a t: is given by: for any distribution s t ,

υ i,at: M,γ,t (s t ) . = E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |s t , a t: }, with boundary condition υ i,• M,γ,ℓ (•) . = 0.
The performance index for joint policy a 0: at initial belief state s 0 is given by υ a 0: M,γ,0 (s 0 ). As discussed below, defining the Bellman's equations underlying state-value functions under a fixed joint policy will prove useful.

Lemma 1. The t-step state-value function υ i,at: M,γ,t : X ×O t → R satisfies a recursion formula, known as Bellman's equations, i.e., for any arbitrary hidden state x t and joint history o t ,

υ i,at: M,γ,t (x t , o t ) = ut∈U a t (u t |o t ) • q i,a t+1: M,γ,t (x t , o t , u t ) q i,a t+1: M,γ,t (x t , o t , u t ) . = r i xtut + γ x t+1 ∈X z∈Z p ut,z t+1 xt,x t+1 • υ i,a t+1: M,γ,t+1 (x t+1 , (o t , u t , z t+1 )), ( 1
)
with boundary condition υ i,• M,γ,ℓ (•) = q i,• M,γ,ℓ (•) . = 0.
Proof. The proof proceeds by induction. It is obviously true at the last time step t = ℓ -1, i.e., for every hidden state x t , and joint history o t ,

υ a ℓ-1 M,γ,ℓ-1 (x ℓ-1 , o ℓ-1 ) . = E{r x ℓ-1 ,U ℓ-1 |x ℓ-1 , o ℓ-1 , a ℓ-1 }.
Expanding the expectation over joint actions results in the following expression:

υ a ℓ-1 M,γ,ℓ-1 (x ℓ-1 , o ℓ-1 ) = u ℓ-1 ∈U a ℓ-1 (u ℓ-1 |o ℓ-1 ) • q • M,γ,ℓ-1 (x ℓ-1 , o ℓ-1 , u ℓ-1 ), where q • M,γ,ℓ-1 (x ℓ-1 , o ℓ-1 , u ℓ-1 ) . = r x ℓ-1 ,u ℓ-1 .
Suppose the induction hypothesis holds from time step t + 1 onward. The recursive scheme holds for time step t, for hidden state x t and joint history o t ,

υ at: M,γ,t (x t , o t ) . = E ℓ-1 τ =t γ τ -t • r Xτ ,Uτ |x t , o t , a t: .
Splitting the immediate reward and the future rewards leads to the following expression:

υ at: M,γ,t (x t , o t ) = E r xt,Ut + γ ℓ-1 τ =t+1 γ τ -t-1 • r Xτ ,Uτ |x t , o t , a t: .
Expanding the expectation of the future rewards over all histories at time step t + 1 yields:

υ at: M,γ,t (x t , o t ) = E r xt,Ut + γE ℓ-1 τ =t+1 γ τ -t-1 • r Xτ ,Uτ |X t+1 , (o t , U t , Z t+1 ), a t+1: |x t , o t , a t .
The inner expectation is the state-value function of hidden states and histories at time step t + 1, by Definition 2 of υ a t+1:

M,γ,t+1 , i.e.,

υ at: M,γ,t (x t , o t ) = E{r xt,Ut + γυ a t+1: M,γ,t+1 (X t+1 , (o t , U t , Z t+1 ))|x t , o t , a t }.
The application of definition of q a t+1:

M,γ,t in (1) produces the following expression:

υ at: M,γ,t (x t , o t ) = E{q a t+1: M,γ,t (x t , o t , U t )|x t , o t , a t }.
Finally, the expansion of the expectation over joint actions produces the target expression:

υ at: M,γ,t (x t , o t ) = ut∈U a t (u t |o t ) • q a t+1: M,γ,t (x t , o t , u t ).
Hence, the proof holds for any arbitrary time step t. Which ends the proof.

Solution Concepts

After learning how to calculate the state-and action-value functions for a fixed joint policy, we also need to determine how to identify a suitable policy for each agent based on statevalue functions. Unfortunately, no universal definition of good policies can be applied to all multi-agent sequential decision-making problems. Instead, this paper proposes solution concepts that refine the notion of a best-response policy, including but not limited to Nash Equilibrium, optimal joint policy, or strong Stackelberg joint policy. To better understand the concept of best response, consider the scenario where an agent knows how other agents will act. In this case, the multi-agent sequential decision-making problem becomes simple, and the agent is left with a single-agent problem of selecting the utility-maximizing policy based on the other agents' fixed policies, i.e., a best-response policy.

Definition 4. A best-response policy of agent i to joint policy a ¬i 0: ∈ A ¬i 0: of the other agents is a policy a i 0:

∈ A i 0: satisfying υ i,(a i 0: ,a ¬i 0: ) M,γ,0 (s 0 ) ≥ υ i,(a i 0: ,a ¬i 0: ) M,γ,0 (s 0 ), for all a i 0: ∈ A i 0: . Set A i 0: (a ¬i 0:
) of best-responses w.r.t. a ¬i 0: is made of all the possible randomized policies and is thus infinite except in degenerate cases where a unique (deterministic) best-response, i.e.,

A i 0: (a ¬i 0: ) . = {a i 0: ∈ A i 0: |υ i,(a i 0: ,a ¬i 0: ) M,γ,0 (s 0 ) ≥ υ i,(a i 0: ,a ¬i 0: ) M,γ,0 (s 0 ), ∀a i 0: ∈ A i 0: }.
The properties of best-response policies are numerous and significant. Firstly, they yield the same performance index for a specific joint policy a ¬i 0: of the other agents. Consequently, deterministic (or pure) policies are just as effective as randomized policies. Additionally, if a randomized policy is a best-response, every deterministic policy within its support must also be a best response. Perfect recall ensures that these properties hold, regardless of whether the best-response is deterministic, mixed, or stochastic.

Up to this point, it is assumed that an agent knows other agents' policies. However, an agent may not know how other agents will act. Nevertheless, it is possible to utilize the concept of best-response to define all solution concepts of interest in this paper. A notable example of such concepts is the most central notion in non-cooperative game theory, namely the Nash Equilibrium. A formal definition follows. Definition 5. A joint policy a 0: ∈ A 0: is a Nash Equilibrium if the policy of any agent is a best response to those of the other agents, i.e., a i 0: ∈ A i 0: (a ¬i 0: ) for every agent i. A Nash Equilibrium exists in any game with a finite set of agents and a finite deterministic policy space per agent. A Nash equilibrium refers to a stable joint policy where no agent is willing to deviate from its policy, provided they know the policies other agents will follow. Multiple Nash equilibria can exist, all of which are self-enforcing if agents adhere to such behaviour. Each agent's best interest is to stick with its policy. However, it is important to note that these equilibria may not be optimal for the agents, meaning they may not provide optimal values for any agent and can often offer significantly different values. All solution concepts considered onward are refinements of Nash Equilibria. Optimization problems determining the best-response policies are slave games for a master game. To solve a master game, it is necessary to address a multitude of slave games, which may potentially be infinite in number. This is due to numerous Nash equilibria involving mutually beneficial best-response policies.

In this paper, we will be placing a particular emphasis on three significant subclasses of POSGs: zero-sum POSG (zs-POSG), common-payoff POSG (dec-POMDP), and Stackelberg POSG (st-POSG). Our primary objective is to exhibit the underlying structure of their optimal value functions. Definition 6. A two-player POSG M is said to be a zs-POSG if the sum of the rewards of both players equals zero, i.e., r 1 = -r 2 .

Optimally solving zs-POSG M aims at finding a Nash equilibrium. Interestingly, every Nash equilibrium of a zs-POSG M will yield the same performance index at the initial belief state s 0 :

υ i, * M,γ,0 (s 0 ) . = max a i 0: ∈A i 0:
min a ¬i 0: ∈A ¬i 0:

υ i,a 0: M,γ,0 (s 0 ). Definition 7. A n-player POSG M is a dec-POMDP if all players have the same rewards, i.e., r 1 = . . . = r n .

Optimally solving dec-POMDP M aims at finding an optimal joint policy, i.e., a Nash equilibrium whose performance index at the initial belief state s 0 is: υ * M,γ,0 (s 0 ) . = max a 1: 0: ∈A 1: 0:

υ a 0: M,γ,0 (s 0 ).

Definition 8. A two-player POSG M is a st-POSG if (the leader) player 1 publicly announces its policy to (the follower) player 2 beforehand.

Optimally solving st-POSG M aims at finding a strong Stackelberg equilibrium, i.e., a Nash equilibrium whose performance index is:

υ 1, * M,γ,0 (s 0 ) . = max a 1 0: ∈A 1 0:
max a 2 0: ∈A 2 0: (a 1 0: ) υ 1,a 0: M,γ,0 (s 0 ). It is worth noting that solving a POSG optimally, and in particular solving zs-POSG, dec-POMDP, and st-POSG optimally, aims at finding a Nash equilibrium.

Slave Games As POMDPs

In this subsection, we will formally introduce the concept of slave games as a mean to determine a best-response policy for an agent given a master game expressed as a POSG alongside the joint policy that the other agents follow. We will also delve into the expression of slave games as POMDPs and their corresponding solution concepts, including Bellman's optimality equations. To aid comprehension, we will utilize a particular scenario of the tiger problem as an example, depicted in Figure 5.

Example 2. In this particular scenario of the tiger problem, Calvin follows a predetermined policy a ¬i 0: , while Susie is aware of this. Nevertheless, Susie must still identify the correct door to claim the treasure as quickly as possible, cf. ) is characterized by the tuple (X , O, U i , Z i , p, r i ). Here, X represents a finite space of hidden states, O denotes the space of hidden joint histories, U i is the finite action space, and Z i represents the finite observation space. All other aspects of M (a ¬i 0: ) are consistent with those in M . Let us consider master game M . Within M , there exists a slave game denoted by M (a ¬i 0: ). Agent i is part of a POMDP, as depicted in Figure 6. At each time step, the state of the world is determined by the underlying state in M and the joint history of all agents. However, agent i can only access its private history, not the underlying state nor the histories of the other agents. Regardless, agent i can still utilize their history to make informed decisions, which results in an immediate reward signal and a new observation. This process repeats in a new underlying state and joint history at each successive time step until the game concludes. The goal of solving the slave game M (a ¬i 0: ) is to find a best-response policy a i 0: for agent i. A best-response policy will maximize the expected γ-discounted cumulative reward, starting from the initial belief state s 0 , providing the other agents act according to a ¬i 0: . Every best-response policy will have the same performance index at the initial belief state s 0 .

p u,z x ′ p u,z x ′ p u,
Definition 10. Consider a slave game M (a ¬i 0: ) w.r.t. the master game M . The t-step optimal value function υ i M (a ¬i 0: ),γ,t :

O i t → R of M (a ¬i 0:
) is given by: for any arbitrary private history o i t ,

υ i M (a ¬i 0: ),γ,t (o i t ) . = max a i t: ∈A i t: E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |o i t , a i t: , a ¬i 0: }. with boundary condition υ i M (a ¬i 0: ),γ,ℓ (•) . = 0.
One can extend Definition 10 by abuse of notation to hold over posterior probability distributions over private histories of agent i, namely marginal occupancy states, as follows.

Definition 11. Consider a slave game M (a ¬i 0: ) w.r.t. the master game M . The t-step optimal value function υ i M (a ¬i 0: ),γ,t : P(O i t ) → R of any best-response policy is given by: for any arbitrary marginal occupancy state s m,i t ,

υ i M (a ¬i 0: ),γ,t (s m,i t ) . = max a i t: ∈A i t: E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |s m,i t , a i t: , a ¬i 0: }. with boundary condition υ i M (a ¬i 0: ),γ,ℓ (•) . = 0.
When dealing with a slave game formulated as a POMDP, it is important to note that the agent only has access to partial information about the game state. Therefore, relying on the state to reason in such a process is not feasible. Enumerating and evaluating all ℓ-step policy alternatives is computationally expensive. Instead, the best-response policy can be computed based on the private history of that agent.

Lemma 2. The t-step optimal state-value function υ i M (a ¬i 0: ),γ,t : O i t → R of a slave game M (a ¬i 0: ) satisfies a recursion formula, known as Bellman's optimality equations, i.e., for any arbitrary private history o i t , we have:

υ i M (a ¬i 0: ),γ,t (o i t ) = max u i t ∈U i q i M (a ¬i 0: ),γ,t (o i t , u i t ), q i M (a ¬i 0: ),γ,t (o i t , u i t ) . = E{r i Xt,Ut + γυ i M (a ¬i 0: ),γ,t+1 (⟨o i t , u i t , Z i t+1 ⟩)|o i t , u i t , a ¬i 0: } with boundary condition υ i M (a ¬i 0: ),γ,ℓ (•) = q i M (a ¬i 0: ),γ,t (•, •) . = 0.
Proof. The proof starts by defining the best-response policy from time step t onward, providing joint policy of the other agents a ¬i 0: ∈ A ¬i 0: , cf. Definition 10:

υ i M (a ¬i 0: ),γ,t (o i t ) . = max a i t: ∈A i t: E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |o i t , a i t: , a ¬i 0: }. Let υ i,a i t:
M (a ¬i 0: ),γ,t : It is worth noticing that the policy (u i t , a i t+1: ) rooted at history o i t can be written recursively as a tree ⟨u i t , (a i,z i t+1: ) z i ∈Z i ⟩ with initial action being u i t and the tree after seeing private observation z i being a i,z i t+1: . Consequently, replacing (u i t , a i t+1: ) by ⟨u i t , (a i,z i t+1: ) z i ∈Z i ⟩ results in the following expression:

o i t → E{ ℓ-1 τ =t γ τ -t •
υ i M (a ¬i 0: ),γ,t (o i t ) = max ⟨u i t ,(a i,z i t+1: ) z i ∈Z i ⟩∈A i t: E{r i Xt,Ut + γυ i,a i,Z i t+1 t+1: M (a ¬i 0: ),γ,t+1 (o i t , u i t , Z i t+1 )|o i t , (u i t , a i t+1: , a ¬i 0: )}.
One can split the max operator into two parts, the first one over private actions max u i t ∈U i and the other one over the future decision rules max

(a i,z i t+1: ) z i ∈Z i ∈A i t+1:
, as follows:

υ i M (a ¬i 0: ),γ,t (o i t ) = max u i t ∈U i E{r i Xt,Ut + γ max a i,Z i t+1 t+1: ∈A i t+1: υ i,a i,Z i t+1 t+1: M (a ¬i 0: ),γ,t+1 (⟨o i t , u i t , Z i t+1 ⟩)|o i t , (u i t , a ¬i 0: )}.
By Definition 10, we know that the following holds:

υ i M (a ¬i 0: ),γ,t+1 ((o i t , u i t , z i t+1 )) . = max a i,z i t+1 t+1: ∈A i t+1: υ i,a i,z i t+1 t+1: M (a ¬i 0: ),γ,t+1 (⟨o i t , u i t , z i t+1 ⟩),
which leads us to the following expression:

υ i M (a ¬i 0: ),γ,t (o i t ) = max u i t ∈U i E{r i Xt,Ut + γυ i M (a ¬i 0: ),γ,t+1 (⟨o i t , u i t , Z i t+1 ⟩)|o i t , (u i t , a ¬i 0: )}.
Which ends the proof.

The tabular nature of state-and action-value functions in a slave game results in linearity over marginal occupancy states.

Corollary 1. The t-step optimal state-value function υ i M (a ¬i 0: ),γ,t : P(O i t ) → R is linear over posterior probability distributions of private histories, i.e., for any arbitrary marginal occupancy state s m,i t ,

υ i M (a ¬i 0: ),γ,t (s m,i t ) = o i t ∈O i t s m,i t (o i t ) • υ i M (a ¬i 0: ),γ,t (o i t ).
Similarly, the t-step optimal action-value function q i M (a ¬i 0: ),γ,t : P(O i t ) × A i → R is linear over posterior probability distributions of private histories, i.e., for any arbitrary marginal occupancy state s m,i t and private decision rule a i t ,

q i M (a ¬i 0: ),γ,t (s m,i t , a i t ) = o i t ∈O i t s m,i t (o i t ) u i t ∈U i a i t (u i t |o i t ) • q i M (a ¬i 0: ),γ,t (o i t , u i t ).
with boundary condition

υ i M (a ¬i 0: ),γ,ℓ (•) = q i M (a ¬i 0: ),γ,ℓ (•, •) . = 0.
Proof. The proof follows directly from that in Lemma 2.

The optimal state-and action-value functions in slave games are shown to be linear across probability distributions of private histories in Corollary 1. However, it is important to note that this finding cannot be directly applied to the optimal value function of the master game. This is because the master game requires optimal value function formulations for all the slave games, encompassing all agents' histories. Efforts have been made to apply Corollary 1 in showing the uniform continuity properties of optimal value functions of master games. A notable instance is incorporating a weak convexity property for the optimal value functions of zs-POSGs by Wiggers et al. [2016]. To gain a more comprehensive understanding of this, it is essential to define some basilar concepts.

Definition 12. Let s t ∈ P(X ×O t ) be a posterior probability distribution over hidden states and joint histories, namely an occupancy state, and define the corresponding factors:

• marginal occupancy state s m,i t , i.e., for any private history

o i t , s m,i t (o i t ) = xt∈X o ¬i t ∈O ¬i t s t (x t , o i t , o ¬i t ),
• conditional occupancy state s c,i t , i.e., for any hidden state x t and joint history

⟨o i t , o ¬i t ⟩, s c,i t (x t , o ¬i t |o i t ) = s t (x t , o i t , o ¬i t )/s m,i t (o i t ).
We shall use short-hand notation s t . = s m,i t ⊙ s c,i t to represent occupancy state s t given by: for any arbitrary hidden state x t and joint history o

t , s t (x t , o t ) = s m,i t (o i t ) • s c,i t (x t , o ¬i t |o i t )
. Intuitively, the t-step conditional occupancy state s c,i t is a summary of the suffix joint policy a ¬i :t-1 together with the initial belief s 0 . Consequently, a slave game M (a ¬i 0: ) can be expressed as a sequence of slave subgames, one slave subgame M (s c,i t , a ¬i t: ) for each time step t. So, solving slave game M (a ¬i 0: ) relies on solving sequence of slave subgames ⟨M (a ¬i 0: ), M (s c,i 1 , a ¬i 1: ), . . . , M (s c,i ℓ-1 , a ¬i ℓ-1: )⟩ through Bellman's principle of optimality. We are now ready to state the convexity properties of interest.

Theorem 1. [Wiggers et al.] Consider the zs-POSG M . The t-step optimal state-value function υ i, * M,γ,t : P(X × O t ) → R is convex over marginal occupancy states for a fixed conditional occupancy state, i.e., for any occupancy state

s t . = s m,¬i t ⊙ s c,¬i t , υ i, * M,γ,t (s t ) = max a i t: ∈A i t: υ i M (s c,¬i t ,a i t: ),γ,t (s m,¬i t ),
where

υ i M (s c,¬i t ,a i t: ),γ,t . = -υ ¬i M (s c,¬i t ,a i t: ),γ,t and M (s c,¬i t , a i t:
) describes the slave subgame given the conditional occupancy state s c,¬i t and private decision rule a i t: . Theorem 1 stipulates that the optimal value functions for zs-POSGs are convex functions of marginal occupancy states, given a fixed conditional occupancy state. However, this property alone does not facilitate value generalization across different occupancy states. To address this challenge, [START_REF] Delage | and common-reward partially observable stochastic games[END_REF] integrated Lipschitz continuity and the convexity property in Theorem 1, thus allowing for the generalization across occupancy states.

Theorem 2. [Delage et al.]

υ i, * M,γ,t (s t ) ≤ υ i M (s c,¬i t ,a i t: ),γ,t (s m,¬i t ) + κ t ∥s t -s m,¬i t ⊙ sc,¬i t ∥,
where

υ i M (s c,¬i t ,a i t: ),γ,t . = -υ ¬i M (s c,¬i t ,a i t: ),γ,t
, and M (s c,¬i t , a i t: ) describes the slave subgame given conditional occupancy state s c,¬i t and private decision rule a i t: , and

κ t . = 1-γ ℓ-t 1-γ c is the Lipschitz constant at time step t.
Using Theorem 2 allows the generalization of values across various occupancy states by harmonizing local convexity and Lipschitz continuity properties. Nonetheless, it is worth noting that the Lipschitz constant can result in imprecise approximations, which may ultimately impede algorithmic efficiency.

Problem Reformulations

The existing literature on master and slave games primarily focuses on an agent-centric perspective. However, this approach poses significant challenges in terms of knowledge transfer from Markov games to POSGs. In particular, the agent-centric perspective is not always geared to ease optimal decision-making. As such, adopting a more generalized approach to knowledge transfer is necessary to address this limitation. This section examines the dynamics of master and slave games from the perspective of a trusted third party acting on behalf of all involved agents simultaneously. To accomplish this goal, we shall introduce two reformulations: plan-time Markov games, which use the history available at planning time to the trusted third party about master or slave games, and occupancy Markov games, which leverage sufficient statistics to represent the history available to the trusted third party. We shall demonstrate that both reformulations maintain the ability to solve the original master or slave games optimally.

Master Game Reformulations

In this subsection, we will discuss agents delegating their decision-making authority to a trusted third party, also known as a central planner. Within this setting, we shall distinguish between the planning and execution phases. During the planning phase, the central planner is given the power to make decisions on behalf of the agents by using publicly available information about the environment, agents, decisions, and perceptions. It is important to note that the central planner may have information at the planning time that is typically unknown to all agents at the execution stage. At the planning time, the central planner provides the agents with decision rules to follow at each time step, but each agent may only have access to their private decision rules. However, it is important to note that the central planner may not have access to agent histories or decisions at the execution stage. From the central planner viewpoint, the plan-time environment includes the original environment and Games can be viewed as interactions between agents and their environment or, alternatively, as interactions between a central planner and a plan-time environment, resulting in what is known as a plan-time Markov game. However, this alternate perspective does not impact how agents behave in the original game. Both approaches to the game can yield similar solutions under mild conditions. For example, if agents disclose all of their confidential information at every stage, both views are equivalent. Nonetheless, agents may possess divergent and conflicting information about the game at each stage. In plan-time Markov games, a central planner executes a joint decision rule on behalf of all agents and receives public observations available to all agents involved in the game. Figure 8 illustrates the process. The initial belief state, history of public observations, and joint policy are integral components of plan-time histories.

Definition 13. A plan-time history for the central planner at time step t includes the initial belief state and the joint policy of all agents up to time step t -1, and the history of public observation up to time step t, i.e., y t . = ⟨s 0 , a 0:t-1 , w 1:t ⟩, with boundary condition y 0 . = s 0 .

The plan-time histories describe a simultaneous-moves stochastic Markov game, i.e., a plan-time Markov game. During the execution phase, the agents do not have access to the plan-time history, the exception being public observations. Consequently, since the central planner makes decisions on behalf of the agents, these decisions cannot rely on the plan- M is given by a tuple

0 t t + 1 t + 2 . . . Time y 0 y t y t+1 y t+2 • • • a 0 a t a t+1 w t w t+1 w t+2
M ′ . = ⟨Y, A, W, ρ M ′ , ω M ′ , r M ′ ⟩,
where Y is the space of all plan-time histories; A is the space of actions describing joint decision rules; W is the space of public observations;

ρ M ′ : Y × A × W → Y is the deterministic transition rule, where ρ M ′ (y t , a t , w t+1 ) . = (y t , a t , w t+1 ); ω M ′ : Y × A × W → [0, 1] is the public observation model, where ω M ′ (w t+1 |y t , a t ) . = Pr{w t+1 |y t , a t }; and r M ′ : Y × A → R n describes the reward function-i.e., r i M ′ (y t , a t ) . = xt∈X ot∈Ot Pr{x t , o t |y t } ut∈U r i xtut • a t (u t |o t ).
Definition 14 provides a central-planner viewpoint about the master game M . It differs from that of [START_REF] Nayyar | Optimal control strategies in delayed sharing information structures[END_REF], [START_REF] Oliehoek | Sufficient plan-time statistics for decentralized POMDPs[END_REF], [START_REF] Jilles | Optimally solving dec-POMDPs as continuous-state MDPs[END_REF] by allowing the explicit utilization of public observations. Doing so shall later prove useful to connect our general results to narrower settings. Please note that M ′ is a Markov game in which the agents cannot observe the states. This means that the solution for this game involves a sequence of actions conditional on public observations, where the state of the game has no impact on the actions taken. The main objective of solving game M ′ is to find a sequence of actions a 1: 0: conditional on public observations, also known as a joint policy a 0: . This policy is determined by a performance index represented by state-value functions. To better understand the relationship between games M and M ′ , we introduce the state-value function under a joint policy a 0: when expressed in the plan-time game M ′ .

Definition 15. The t-step state-value function υ i,at:

M ′ ,γ,t : Y t → R of agent i under joint policy a t: is given by: for any arbitrary plan-time history y t ,

υ i,at: M ′ ,γ,t (y t ) = E{ ℓ-1 τ =t γ τ -t • r i M ′ (Y τ , a τ )|y t , a t: }, with boundary condition υ i,• M ′ ,γ,ℓ (•) . = 0.
The optimal joint policy for the original master game M can be found by searching for an optimal joint policy in the surrogate master game M ′ .

Proposition 1. In a master game M and the corresponding plan-time Markov game M ′ , if a joint policy a 0: has the optimal performance index in M ′ at the initial belief state s 0 , it will also have the same optimal performance index in M at the initial belief state s 0 .

Proof. First, the solution of interest for both games lies in joint policies. Second, regardless of solution concepts of interest, the state-value functions under a joint policy characterize a good solution. Let a 0: be a Nash equilibrium of the plan-time game M ′ , i.e., for any agent i, a i 0: ∈ A i 0: (a ¬i 0: ),

A i 0: (a ¬i 0: ) . = {a i 0: |a i 0: ∈ A i 0: : υ i,(a i 0: ,a ¬i 0: ) M ′ ,γ,0 (y 0 ) ≥ υ i,(a i 0: ,a ¬i 0: ) M ′ ,γ,0 (y 0 ), ∀a i 0: ∈ A i 0: }.
Let us show that it is also a Nash equilibrium for the master game M . To do so, it only suffices to show that υ a 0: M ′ ,γ,0 (y 0 ) = υ a 0: M,γ,0 (s 0 ) for any arbitrary joint policy a 0: .

υ a 0: M ′ ,γ,0 (y 0 ) . = E{ ℓ-1 t=0 γ t • r M ′ (Y t , a t )|y 0 , a 0: }. ( 2
)
The injection of definition of r M ′ , cf. Definition 14, into (2), results in the following:

υ a 0: M ′ ,γ,0 (y 0 ) = ℓ-1 t=0 γ t E xt∈X ot∈Ot Pr{x t , o t |y t } ut∈U r xt,ut • a t (u t |o t )|y 0 , a 0: .
Replace the expression into the bracket with an expectation leads us to the following

υ a 0: M ′ ,γ,0 (y 0 ) = E ℓ-1 t=0 γ t E (xt,ot)∼Pr{•|Yt},ut∼at(•|ot) {r xtut }|y 0 , a 0: .
Exploiting the linearity of the expectation gives us the following expression

υ a 0: M ′ ,γ,0 (y 0 ) = E (x 0:ℓ-1 ,o 0:ℓ-1 ,u 0:ℓ-1 )∼Pr{•|y 0 ,a 0: } { ℓ-1 t=0 γ t • r xtut } = E{ ℓ-1 t=0 γ t • r Xt,Ut |y 0 , a 0: } = E{ ℓ-1 t=0 γ t • r Xt,Ut |s 0 , a 0: }, (since y 0 . = s 0 ) . = υ a 0:
M,γ,0 (s 0 ).

The expression presented above demonstrates that for any arbitrary joint policy a 0: , both M ′ and M deliver the same evaluation, that is to say, υ a 0: M ′ ,γ,0 (y 0 ) = υ a 0: M,γ,0 (s 0 ). As the statevalue functions characterize a Nash equilibrium, the fact that M ′ and M provide the same evaluation for a fixed joint policy indicates that if a joint policy a 0: is a Nash equilibrium for M ′ , it is also a Nash equilibrium for M . This argument can similarly apply to refinements of Nash equilibria, such as subgame perfect Nash equilibria or optimal joint policies. This concludes the proof.

According to Proposition 1, solving the plan-time Markov game M ′ is the same as solving the master game M . However, keeping track of the plan-time histories in M ′ can be hard as they constantly grow with each time step. To simplify things, we can summarize history using the concept of occupancy state, cf. Figure 9 x tl

.125

x tr z hr , z hr .125

x tl

.125

x tr z hr , z hl .125

x tl

.125

x tr z hl , z hr .125

x tl

.125

x tr

Figure 9: Illustration of a plan-time history y 1 and its corresponding occupancy state s 1 in case of no public observations.

The probability distributions over hidden states and joint histories lay in the space P(X ×O), which includes the space of reachable occupancy states S.

s t+1 (x t+1 , (o t , u t , zt+1 , w t+1 )) ∝ xt∈X s t (x t , o t ) • p ut,⟨z t+1 ,w t+1 ⟩ xt,x t+1 • a t (u t |o t ).
• The observation probability model ω The occupancy-state Markov game falls under the category of Markov games. Since the public observations have been made explicit, the reformulation leads to a stochastic rather than a deterministic process, as shown in Dibangoye et al. [2016]. The aim of solving M ′′ is to find a joint policy similar to the ones used in both M and M ′ . However, in this game, occupancy states replace plan-time histories, which can lead to overlooking crucial information, such as the joint policy. Doing so may not be the best approach for optimal decision-making. The substitution of occupancy states to plan-time histories requires guarantees that the former are sufficient statistics of the latter concerning three aspects: (i) predicting the current expected reward, (ii) predicting the next public observations, and (iii) estimating the next occupancy state. With these properties in hand, one can formally define a Markov game. Formal proofs of these properties follow.

M ′′ : S × A × W → [0, 1]
Lemma 3. The t-step occupancy state, defined as s t . = Pr{X t , O t |y t }, is a sufficient statistic of the plan-time history y t for an accurate prediction of the expected reward that will be received immediately after executing the decision rule a t , i.e., r M ′ (y t , a t ) = r M ′′ (s t , a t ).

Proof. The proof starts with the definition of the expected reward conditional on plan-time history y t and decision rule a t , i.e.,

r M ′ (y t , a t ) . = E{r Xt,Ut |y t , a t }.
The expansion over hidden states, joint histories and joint actions leads to the following expression:

r M ′ (y t , a t ) = xt∈X ot∈Ot ut∈U Pr{x t , o t , u t |y t , a t } • r xt,ut .
The decomposition of the joint probability as the product of conditional probabilities gives the following expression:

r M ′ (
r M ′ (y t , a t ) = xt∈X ot∈Ot ut∈U a t (u t |o t ) • r xt,ut • s t (x t , o t ).
By the definition of r M ′′ (s t , a t ), from Definition 17, the following holds:

r M ′ (y t , a t ) = r M ′′ (s t , a t ).
Which ends the proof.

ω M ′ (w t+1 |y t , a t ) = xt∈X ot∈Ot ut∈U x t+1 ∈X zt+1 ∈ Z Pr{x t , o t , u t , x t+1 , zt+1 , w t+1 |y t , a t }.
The decomposition of the joint probability as a product of conditional probabilities yields the following result:

ω M ′ (w t+1 |y t , a t ) = xt∈X ot∈Ot ut∈U x t+1 ∈X zt+1 ∈ Z Pr{x t+1 , zt+1 , w t+1 |y t , a t , x t , o t , u t } • Pr{x t |y t , a t , u t , o t } • Pr{u t |y t , a t , o t } • Pr{o t |y t , a t }.
The first factor is the game's dynamics; the second factor is the probability of the hidden states given plan-time history and joint history; the third factor is the probability of joint actions given decision rule and joint history, and the last factor is the probability of joint histories given the plan-time history, i.e.,

ω M ′ (w t+1 |y t , a t ) = xt∈X ot∈Ot ut∈U x t+1 ∈X zt+1 ∈ Z Pr{x t+1 , zt+1 , w t+1 |x t , u t } • Pr{x t |y t , o t } • Pr{u t |a t , o t } • Pr{o t |y t }.
Re-arranging and re-naming terms yield the following expression

ω M ′ (w t+1 |y t , a t ) = xt∈X ot∈Ot ut∈U x t+1 ∈X zt+1 ∈ Z p ut,⟨z t+1 ,w t+1 ⟩ xt,x t+1 • a t (u t |o t ) • s t (x t , o t ).
Consequently, the following equality holds by Definition 17 for ω M ′′ (w t+1 |s t , a t ):

ω M ′ (w t+1 |y t , a t ) = ω M ′′ (w t+1 |s t , a t ).
Which ends the proof.

Lemma 5. The t-step occupancy state, defined as s t . = Pr{X t , O t |y t }, is a sufficient statistic of the plan-time history y t for predicting the subsequent occupancy state following the executing of the decision rule a t and the reception of public observation w t+1 , i.e., ρ M ′ (y t , a t , w t+1 ) = ρ M ′′ (s t , a t , w t+1 ).

Proof. In demonstrating the sufficiency of the occupancy states, we also derive the rule for updating occupancy states from one time step to the next. For the process defined by M ′ , the only information that the central planner obtains during the plan time t is the fact that a particular decision rule a t has been followed, and public observation w t+1 has been received at the end of the plan time. If (y t , a t , w t+1 ) denotes the total data available to the central planner at plan time t + 1, then we can write:

y t+1 . = (y t , a t , w t+1 ),
y t+1 represents the plan-time history before time step t + 1 plus the additional information that a particular decision rule was recorded and public observation occurred. By Definition 16, occupancy states are written as follows: for every hidden state x t+1 , joint history o t , joint action u t , and joint observation ⟨z t+1 , w t+1 ⟩,

s t+1 (x t+1 , (o t , u t , ⟨z t+1 , w t+1 ⟩)) . = Pr{x t+1 , (o t , u t , ⟨z t+1 , w t+1 ⟩)|y t+1 }. (3)
The application of Bayes' rule and the substitution of y t+1 by (y t , a t , w t+1 ) in (3) yield

s t+1 (x t+1 , (o t , u t , ⟨z t+1 , w t+1 ⟩)) = Pr{x t+1 , o t , u t , zt+1 , w t+1 |y t , a t } Pr{w t+1 |y t , a t } . ( 4
)
From Lemma 4, we know that the denominator of ( 4) is given

ω M ′ (w t+1 |y t , a t ) = ω M ′′ (w t+1 |s t , a t ).
The expansion of the joint probability in the numerator of (4) as a product of conditional probabilities yields

s t+1 (x t+1 , (o t , u t , ⟨z t+1 , w t+1 ⟩)) ∝ xt∈X Pr{x t , x t+1 , o t , u t , zt+1 , w t+1 |y t , a t }.
The expansion of the joint probability as a product of conditional probabilities gives us the following expression:

s t+1 (x t+1 , (o t , u t , ⟨z t+1 , w t+1 ⟩)) ∝ xt∈X Pr{x t+1 ,
s t+1 (x t+1 , (o t , u t , ⟨z t+1 , w t+1 ⟩)) ∝ xt∈X p ut,z t+1 ,w t+1 xt,x t+1 • a t (u t |o t ) • s t (x t , o t ).
Consequently, the following equality holds by Definition 17 for ρ M ′′ (s t , a t , w t+1 ):

s t+1 = ρ M ′′ (s t , a t , w t+1 ).
Which ends the proof.

We introduce state-value functions for a fixed joint policy under M ′′ to determine if occupancy states are sufficient. These state-value functions compute the expected cumulative γ-discounted reward from the initial belief state s 0 onward. They are represented as

υ a 0: M ′′ ,γ,0 (s 0 ) . = E{ ℓ-1 t=0 γ t • r M ′′ (S t , a t )|s 0 , a 0: }.
Definition 18. The t-step state-value function υ i,at: M ′′ ,γ,t : S t → R under the joint policy a t: is given by: for any occupancy state s t ,

υ i,at: M ′′ ,γ,t (s t ) . = E ℓ-1 τ =t γ τ -t • r i M ′′ (S τ , a τ )|s t , a t: , with boundary condition υ i,• M,γ,ℓ (•) . = 0.
According to the following lemma, the state-value functions satisfy Bellman's equations for occupancy states at every time step.

Lemma 6. The t-step state-value function υ i,at: M ′′ ,γ,t : S t → R under the joint policy a 0: satisfies Bellman's equations: for any occupancy state s t ,

υ i,at: M ′′ ,γ,t (s t ) = q i,a t+1: M ′′ ,γ,t (s t , a t ), q i,a t+1: M ′′ ,γ,t (s t , a t ) . = r i M ′′ (s t , a t ) + γ s t+1 ∈S t+1 p M ′′ (s t , a t , s t+1 ) • υ i,a t+1: M ′′ ,γ,t+1 (s t+1 ), with boundary condition υ i,• M ′′ ,γ,ℓ (•) . = 0.
Proof. The proof follows directly from the definition of the state-value functions under joint policy a 0: over the occupancy states: for time step t, occupancy state s t ,

υ at: M ′′ ,γ,t (s t ) . = E ℓ-1 τ =t γ τ -t • r M ′′ (S τ , a τ )|s t , a t: ,
Exploiting the fact that r M ′′ (s t , a t ) is not a random variable, we obtain the following expression:

υ at: M ′′ ,γ,t (s t ) = r M ′′ (s t , a t ) + γE ℓ-1 τ =t+1 γ τ -t-1 • r M ′′ (S τ , a τ )|s t , a t: .
The expansion of the expectation over all next occupancy states (through public observations) gives the following expression:

υ at: M ′′ ,γ,t (s t ) = r M ′′ (s t , a t ) + γE E{ ℓ-1 τ =t+1 γ τ -t-1 • r M ′′ (S τ , a τ )|s t+1 , a t+1: }|s t , a t .
The injection of Definition 18 of υ a t+1:

M ′′ ,γ,t+1 (s t+1 ) instead of the inner expectation gives the following expression:

υ at: M ′′ ,γ,t (s t ) = r M ′′ (s t , a t ) + γE s t+1 ∼p M ′′ (st,at,•) υ a t+1: M ′′ ,γ,t+1 (s t+1 )|s t , a t .
By definition of the expectation, we know that the expression becomes:

Definition 18 = r M ′′ (s t , a t ) + γ s t+1 ∈S t+1 p M ′′ (s t , a t , s t+1 ) • υ a t+1: M ′′ ,γ,t+1 (s t+1 ) . = q a t+1: M ′′ ,γ,t (s t , a t ).
Which ends the proof.

It is important to recognize that state-and action-value functions in the master game M under a fixed joint policy, which have a tabular nature, inherently display uniform continuity characteristics. The following explanation highlights the simple yet significant linear properties associated with these functions, providing a fixed joint policy. It is worth noting that these uniform continuity properties apply to occupancy states.

Lemma 7. The t-step state-value function υ i,at: M ′′ ,γ,t : S t → R under joint policy a t: is linear over occupancy states: for any occupancy state s t ,

υ i,at: M ′′ ,γ,t (s t ) = xt∈X ,ot∈Ot s t (x t , o t ) • υ i,at: M,γ,t (x t , o t ).
Similarly, the t-step action-value function q i,a t+1:

M ′′ ,t : S t × A t → R under the joint policy a t+1: is linear over occupancy states and joint decision rules: for any occupancy state s t ∈ S t and joint decision rule a t q i,a t+1:

M ′′ ,γ,t (s t , a t ) = xt∈X ,ot∈Ot s t (x t , o t ) ut∈U a t (u t |o t ) • q i,a t+1: M,γ,t (x t , o t , u t ).
Proof. The proof starts with the definition of the state-and action-value functions for a fixed joint policy at time step t and occupancy state s t ,

υ at: M ′′ ,γ,t (s t ) . = E{ ℓ-1 τ =t γ τ -t • r M ′′ (S τ , a τ )|s t , a t: }.
It is worth noticing that the dynamics of occupancy states are stochastic, which makes it possible to rewrite υ at: M ′′ ,γ,t (s t ) as follows:

υ at: M ′′ ,γ,t (s t ) = q a t+1: M ′′ ,γ,t (s t , a t ) q a t+1: M ′′ ,γ,t (s t , a t ) = r M ′′ (s t , a t ) + γ s t+1 ∈S t+1 p M ′′ (s t , a t , s t+1 ) • υ a t+1: M ′′ ,γ,t+1 (s t+1 ).
The property naturally holds when the horizon is exhausted, i.e., υ

• M ′′ ,γ,ℓ (•) = q • M ′′ ,γ,ℓ (•, •)
. = 0. Suppose it also holds at time step t + 1 onward, i.e., υ a t+1:

M ′′ ,γ,t+1 (s t+1 ) = xt∈X ot∈Ot s t+1 (x t , o t ) • υ a t+1: M,γ,t+1 (x t , o t ) q a t+2: M ′′ ,γ,t+1 (s t+1 , a t+1 ) = xt∈X ot∈Ot s t+1 (x t , o t ) ut∈U a t+1 (u t |o t ) • q a t+2: M,γ,t+1 (x t , o t , u t ).
Then, it follows that

υ at: M ′′ ,γ,t (s t ) = q a t+1: M,γ,t (s t , a t ) q a t+1: M ′′ ,γ,t (s t , a t ) = xt∈X ot∈Ot s t (x t , o t ) ut∈U a t (u t |o t ) • q a t+1: M,γ,t (x t , o t , u t ) q a t+1: M,γ,t (x t , o t , u t ) = r xt,ut + γ x t+1 ∈X ,z t+1 ∈Z p utz t+1 xtx t+1 • υ a t+1: M,γ,t+1 (x t+1 , (o t , u t , z t+1 )).
Re-arranging terms then yield the target results, i.e.,

υ at: M ′′ ,γ,t (s t ) = xt∈X ot∈Ot s t (x t , o t ) • υ at: M,γ,t (x t , o t ) q a t+1: M ′′ ,γ,t (s t , a t ) = xt∈X ot∈Ot s t (x t , o t ) ut∈U a t (u t |o t ) • q a t+1: M,γ,t (x t , o t , u t ).
Hence, the property holds for any arbitrary time step. Which ends the proof.

Lemma 7 highlights that when a fixed joint policy is utilized, the state-and action-value functions can be elegantly expressed as linear functions of occupancy states across all types of master games that are represented as partially observable stochastic games. This linearity property is a fundamental aspect that contributes greatly to proving the convexity property of optimal value functions for specific master games, including the common-reward partially observable stochastic games family (dec-POMDP).

The conditions for the sufficiency of occupancy states in optimally solving master games as occupancy-state Markov games are presented in the following proposition.

Proposition 2. Let M be a master game, M ′ be the corresponding plan-time Markov game, and M ′′ the associated occupancy-state Markov game. If we let a 0: be a solution of M ′′ , then a 0: is also a solution of M and M ′ .

Proof. Proposition 1 demonstrates that a solution for M ′ is also valid for M . The only thing left to prove is that if a 0: is a solution for M ′′ , then it is also a solution for M ′ . Initially, we need to show that the state-value function for any particular time step t under a fixed joint policy is dependent on the plan-time history y t only through the corresponding occupancy state s t , which is defined as (Pr{x t , o t |y t }) xt∈X ,ot∈Ot . For any arbitrary fixed joint policy a t: ,

υ at: M ′ ,γ,t (y t ) . = E{ ℓ-1 τ =t γ τ -t • r M ′ (Y τ , a τ )|y t , a t: }.
The application of Lemma 3, Lemma 4, and Lemma 5, lead to the following expression:

υ at: M ′ ,γ,t (y t ) = E{ ℓ-1 τ =t γ τ -t • r M ′′ (S τ , a τ )|s t , a t: }, . = υ at: M ′′ ,γ,t (s t ).
Which ends the proof.

Please note that Propositions 1 and 2 do not provide a practical solution to master games. Rather, they show that finding a solution to either reformulated version will result in a valid solution for the original master game. It is crucial to remember that the solution for these reformulated games does not depend on their states, as they are non-observable. Therefore, it is not advisable to use state-dependent solutions when solving these reformulations, as is often done in fully observable settings.

Slave Game Reformulations

This subsection presents a new perspective on the slave games, viewed from the point of view of a trusted third party. As depicted in Figure 11, the slave games were originally formulated as a single-agent decision-making problem, assuming that other agents had a fixed joint policy. However, this approach led to weak uniform continuity properties, as discussed in Theorems 1 and 2, due to the use of different viewpoints to describe master and slave games, making it difficult to blend their value functions. This subsection aims to provide a unified perspective of both master and slave games from the point of view of a trusted third party, making it easier to identify properties of the slave games that can be applied to master games.

The central planner can think for one agent when considering a trusted third-party viewpoint. The other agents have a predetermined collective strategy, and this information is known to the central planner and the agent for whom it makes decisions. The central plan-ner then gives that agent a set of rules to follow at every time step. In this scenario, the central planner can receive information about the action taken and the observations made by the specific agent it decides for. The private plan-time environment, viewed from the trusted third party's perspective, includes the original game environment and all interacting agents. However, unlike the master game's plan-time environment, the other agents have a predetermined joint policy, and the central planner can only see the private history of the agent they are reasoning for, not the private histories of the other agents. This reformulation turns the slave games into the private plan-time Markov game. Still, it does not affect how the single agent, the central planner, is reasoning to act in the original environment.

Additionally, we will prove that both games, although not equivalent, can lead to equivalent solutions under mild conditions. The central planner collects data at the end of each time step, known as the private plan-time history. This includes the initial belief state, the private history of the specific agent taken into account, and the collective policy of all other agents.

i , U i , Z i , ρ i M ′ , ω i M ′ , r i M ′ ⟩.
Here, Y i represents a space of private plan-time histories, U i is the finite action space, and Z i is the finite observation space. Mappings ρ i M ′ , ω i M ′ , and r i M ′ are formally defined as follows:

• Mapping ρ i M ′ : Y i × U i × Z i → Y i
describes a transition rule over private plan-time histories, i.e., for any private plan-time history y i t , action u i t , and observation z i t+1 , the next private plan-time history is given by:

ρ i M ′ (y i t , u i t , z i t+1 ) . = (y i t , a ¬i t , u i t , z i t+1 ). • Mapping ω i M ′ : Y i × U i × Z i → [0, 1
] is the observation rule, i.e., for any private plantime history y i t , action u i t , and observation z i t+1 , the observation probability is given by:

ω i M ′ (z i t+1 |y i t , u i t ) . = Pr{z i t+1 |y i t , u i t , a ¬i t }. • Mapping r i M ′ : Y i × U i → R defines the reward model, i.e.
, for any private plan-time history y i t , action u i t , the reward is given by:

r i M ′ (y i t , u i t ) . = E{r i Xt,Ut |y i t , u i t , a ¬i t }.
Upon careful examination of private plan-time Markov games, it becomes apparent that they can be constructed using slave games. This removes the need for the explicit creation of the former, allowing for the generation of its components as required. Slave games are linked to partially observable Markov decision processes, while private plan-time Markov games have a more direct connection. However, it is important to note that private plan-time Markov games were introduced as surrogate games for the original slave games, and their objectives remain the same. Solving a private plan-time Markov game aims to determine the agent's best-response policy, denoted as a i 0: . Interestingly, a one-to-one mapping exists between private plan-time histories in these games and private histories in slave games, i.e., E{ ℓ-1 τ =t γ τ -t • r i Xτ Uτ |y i t , a t: }.

0 t t + 1 t + 2 . . . Time y i 0 y i t y i t+1 y i t+2 • • • u i 0 u i t u i t+1 z i t z i t+1 z i t+2 r i 0 r i t r i t+1 r i t+2 • • •
φ i M ′ : Y i → O i y i t . = (s 0 , o i t ,
The optimal state-value functions of private plan-time Markov game M ′ (a ¬i 0: ) exhibit a special property: they are also solutions of the Bellman's optimality equations.

Lemma 8. The t-step optimal state-value function υ i M ′ (a ¬i t: ),γ,t : Y i t → R is the solution of Bellman's optimality equations, i.e., for any arbitrary private plan-time history y i t ,

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max u i t ∈U i q i M ′ (a ¬i t: ),γ,t (y i t , u i t ), q i M ′ (a ¬i t: ),γ,t (y i t , u i t ) . = r i M ′ (y i t , u i t ) + γ z i t+1 ∈Z i ω i M ′ (z i t+1 |y i t , u i t ) • υ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 )), with boundary condition υ i M ′ ,γ,ℓ (•) = q i M ′ ,γ,ℓ (•) . = 0.
Proof. The proof follows directly from the definition of optimal state-value functions for private plan-time Markov game M ′ (a ¬i t: ), cf. Definition 21, i.e.,

υ i M ′ (a ¬i t: ),γ,t (y i t ) . = max a i t: ∈A i t: E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |y i t , a t: }. Let υ i,a i t:
M ′ (a ¬i t: ),γ,t : y i t → E{ ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |y i t , a t: } be a t-step value function under the policy a i t: in the slave game M ′ (a ¬i t: ). Re-arranging terms by decoupling the immediate reward from the future rewards leads successively to the following expressions:

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max (u i t ,a i t+1: )∈A i t: E{r i Xt,Ut + γυ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , Z i t+1 ))|y i t , u i t , a ¬i t , a t+1: }, where υ i,a i t+1: M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 )) . = E{ ℓ-1 τ =t+1 γ τ -t-1 • r i Xτ ,Uτ |ρ i M ′ (y i t , u i t , z i t+1
), a t+1: }. It is worth noticing that policy (u i t , a i t+1: ) rooted at history o i t can be written recursively as a tree ⟨u i t , (a i,z i t+1: ) z i ∈Z i ⟩ with initial action being u i t and the subtree after seeing private observation z i being a i,z i t+1: . Consequently, replacing (u i t , a i t+1: ) by ⟨u i t , (a i,z i t+1: ) z i ∈Z i ⟩ results in:

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max ⟨u i t ,(a i,z i t+1: ) z i ∈Z i ⟩∈A i t: E{r i Xt,Ut + γυ i,a i,z i t+1 t+1: M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 ))|y i t , u i t , a ¬i t , a t+1: }.
One can split the max operator into two parts, the first one over private actions max u i t ∈U i and the other one over the future decision rules max

(a i,z i t+1: ) z i ∈Z i ∈A i t+1:
, as follows:

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max u i t ∈U i E{r i Xt,Ut + γ max a i,z i t+1 t+1: ∈A i t+1: υ i,a i,z i t+1 t+1: M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 ))|y i t , u i t , a ¬i t }.
By Definition 21, we know that the following holds:

υ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 )) . = max a i,z i t+1 t+1: ∈A i t+1: υ i,a i,z i t+1 t+1: M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 )),
which leads us to the following expression:

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max u i t ∈U i E{r i Xt,Ut + γυ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , Z i t+1 ))|y i t , u i t , a ¬i t }.
By the application of Definition 20, we know that r i M ′ (y i t , u i t )

. = E{r i Xt,Ut |y i t , u i t , a ¬i t }, which results in the following expression:

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max u i t ∈U i r i M ′ (y i t , u i t ) + γE{υ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , Z i t+1 ))|y i t , u i t , a ¬i t } .
The expansion over the private observations of the expectation yields the following expression:

υ i M ′ (a ¬i t: ),γ,t (y i t ) = max u i t ∈U i q i M ′ (a ¬i t: ),γ,t (y i t , u i t ), q i M ′ (a ¬i t: ),γ,t (y i t , u i t ) . = r i M ′ (y i t , u i t ) + γ z i t+1 ∈Z i ω i M ′ (z i t+1 |y i t , u i t ) • υ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 )).
Which ends the proof.

The following proposition explicitly connects the games M (a ¬i 0: ) and M ′ (a ¬i 0: ), such that solving either game solves the other. Proposition 3. Let M (a ¬i 0: ) be a slave game and M ′ (a ¬i 0: ) be the corresponding private plantime Markov game. If we let a i 0: be the best-response policy of M ′ (a ¬i 0: ), then it is also the best-response policy of M (a ¬i 0: ).

Proof. The proof consists in demonstrating that optimal state-value functions for M ′ (a ¬i t: ) and M (a ¬i 0: ) achieve the same performance index on equivalent inputs, i.e., for any time step t and private plan-time history

y i t , υ i M ′ (a ¬i t: ),γ,t (y i t ) = υ i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ))
. Consequently, the best-response policy a i t: solution of Bellman's optimality equations for M ′ (a ¬i t: ) achieves the best performance index also for M (a ¬i 0: ). Thus, it is also a best-response policy for M (a ¬i 0: ). Starting with the definition of the optimal action-value function for M (a ¬i 0: ) at time step t and private history φ i M ′ (y i t ), we have that:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) . = max a i t+1: ∈A i t+1: E ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |φ i M ′ (y i t ), u i t , a i t+1: , a ¬i 0:
. There is no loss in replacing (φ i M ′ (y i t ), a ¬i :t-1 ) by y i t , consequently it follows that:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = max a i t+1: ∈A i t+1: E ℓ-1 τ =t γ τ -t • r i Xτ ,Uτ |y i t , u i t , a ¬i t , a t+1: .
The following splits the immediate and the future rewards:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = max a i t+1: ∈A i t+1: E r i Xt,Ut + γ ℓ-1 τ =t+1 γ τ -t-1 • r i Xτ ,Uτ |y i t , u i t , a ¬i t , a t+1: .
Re-arranging terms leads to the following expression:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = max a i t+1: ∈A i t+1: E r i Xt,Ut |y i t , u i t , a ¬i t + γE ℓ-1 τ =t+1 γ τ -t-1 • r i Xτ ,
q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = r i M ′ (y i t , u i t ) + γ max a i t+1: ∈A i t+1: E ℓ-1 τ =t+1 γ τ -t-1 • r i Xτ ,Uτ |y i t , (u i t , a i t+1: , a ¬i t+1: ) .
The expansion of all private observations of agent i produces the following expression:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = r i M ′ (y i t , u i t ) + γE z i t+1 ∼Pr{•|y i t ,u i t ,a ¬i 0: } {υ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 ))}
By the application of Definition 20, we know that ω i M ′ (z i t+1 |y i t , u i t )

. = Pr{z i t+1 |y i t , u i t , a ¬i t }, which results in the following expression:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = r i M ′ (y i t , u i t ) + γ z i t+1 ∈Z i ω i M ′ (z i t+1 |y i t , u i t ) • υ i M ′ (a ¬i t+1: ),γ,t+1 (ρ i M ′ (y i t , u i t , z i t+1 )).
By the application of the definition of q i M ′ (a ¬i t: ),γ,t (y i t , u i t ), it follows that:

q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ) = q i M ′ (a ¬i t: ),γ,t (y i t , u i t ).
The greedy selection of the best-response policy a i 0: w.r.t. joint policy a ¬i 0: of the other agents is given as follows: at time step t, and private history φ i M ′ (y i t ),

a i t (φ i M ′ (y i t )) ∈ arg max u i t ∈U i q i M (a ¬i 0: ),γ,t (φ i M ′ (y i t ), u i t ), ∈ arg max u i t ∈U i q i M ′ (a ¬i t: ),γ,t (y i t , u i t ).
Which ends the proof.

Proposition 3 demonstrates that a solution for M ′ (a ¬i 0: ) can also serve as a solution for the original slave game M (a ¬i 0: ). Nonetheless, like other historical data, private plan-time histories grow in size with each time step, making them less feasible to use. Hence, we suggest a substitute statistic, private occupancy states, to tackle this problem. Nevertheless, before we delve deeper into this subject, it is essential to establish the definition of private occupancy states.

Definition 22. Each agent i has a private occupancy state at a specific time step t, represented as s i t (also denoted as

s i,o i t t
when needed to make the dependence from a given private history o i t more explicit). This state is the posterior probability distribution over hidden states and joint histories based on their private plan-time history y i t , expressed as Pr{X t , O t |y i t }. The initial condition is defined as s i 0 = s 0 . The concept of hierarchical information-sharing in two-agent games has been studied extensively, with research indicating that the private occupancy state can be expressed in a more concise manner [START_REF] Sylvain Sorin | Stochastic games with incomplete information[END_REF][START_REF] Hadfield-Menell | Cooperative inverse reinforcement learning[END_REF], Horák et al., 2017, Xie et al., 2020]. If agent 2 has unrestricted access to agent 1's actions and observations at every time step t without incurring any cost, denoted by (u 1 t-1 , z 1 t ) ⊑ z 2 t , then the private occupancy state at that specific time step t can be represented as a posterior probability distribution over the hidden states, commonly referred to as the belief state. This is denoted as Pr{x t |y 2 t }, where x belongs to the set X . Furthermore, if agent 2 can observe the underlying state of the game, i.e., one-sidedness, then the private occupancy state at a specific time step t is equivalent to that underlying state. The conciseness of private occupancy states is crucial in identifying strong uniform continuity properties for the optimal state-value functions.

The optimal state-and action-value functions of a slave game can be better understood through private occupancy states. Revealing the uniform continuity property of those value functions allows for knowledge transfer between different private occupancy states. While private occupancy states can be more concise for a single slave game, it is important to consider knowledge transfer between multiple slave games. Transfer of knowledge from one slave game to another one is important because to solve a master game, we need to solve multiple slave games. Defining private occupancy states as posterior distributions over hidden states and histories of other agents ¬i or as private histories of agent i, as shown by [START_REF] Auke | Structure in the value function of two-player zero-sum games of incomplete information[END_REF], is adequate for solving a single slave game optimally. However, using a more concise statistic for a single slave game would make knowledge transfer between slave games more difficult, especially in exhibiting the relationship between the optimal state-value function of the master game and the corresponding slave games. This insight explains why previous attempts to establish convexity properties of the optimal state-value functions of the master game failed. The following section explores how private occupancy states are sufficient for optimally solving any slave game.

Connecting Slave and Master Games

This section will discuss an alternative method to solve a slave game by utilizing private occupancy states instead of private plan-time histories. We will analyze if using private occupancy states is enough to solve the reformulated slave games optimally. Furthermore, we will establish a correlation between private occupancy states and occupancy states to merge the state-value functions of master and slave games. We will first define the Markov decision process that private occupancy states induce. )) be its corresponding slave game. A private occupancy-state Markov decision process is given by a tuple M ′′ (a ¬i 0:

0 t t + 1 t + 2 . . . Time s i 0 s i t s i t+1 s i t+2 • • • u i 0 u i t u i t+1 z i t z i t+1 z i t+2 r i 0 r i t r i t+1 r i t+2 • • •
) . = (S i , U i , Z i , ω i M ′′ , ρ i M ′′ , p i M ′′ , r i M ′′ ).
Here, S i is the finite private occupancystate space, U i represents the finite action space, and Z i is the finite observation space. Mappings ω i M ′′ , ρ i M ′′ , p i M ′′ , and r i M ′′ are formally described as follows.

• The observation function

ω i M ′′ : S i × U i × Z i → [0, 1]
s i t+1 (x t+1 , (o t , u t , z i t+1 , z ¬i t+1 )) ∝ xt∈X p ut⟨z i t+1 ,z ¬i t+1 ⟩ xtx t+1 • a ¬i t (u ¬i t |o ¬i t ) • s i t (x t , o t ).
• The transition probability function

p i M ′′ : S i × U i × S i → [0, 1]
gives the probability of private occupancy state s i t+1 upon taking action u i t in private occupancy state s i t , i.e.,

p i M ′′ (s i t , u i t , s i t+1 ) . = z i t+1 ∈Z i ω i M ′′ (z i t+1 |s i t , u i t ) • δ ρ i M ′′ (s i t ,u i t ,z i t+1 ) (s i t+1 ). • The reward model r i M ′′ : S i × U i → R
s i t (x t , o t ) u ¬i t ∈U ¬i a ¬i t (u ¬i t |o ¬i t ) • r i xt,ut .
The Markov decision process associated with private occupancy states is called the private occupancy-state Markov decision process, as depicted in Figure 13. Using occupancy states for master game reformulations raises questions similar to those regarding the use of private occupancy states in the context of slave games. Bellman's principle of optimality allows us to solve M ′′ (a ¬i 0: ) by solving recursively a sequence of smaller Markov decision processes ⟨M ′′ (a ¬i 0: ), M ′′ (a ¬i 1: ), . . . , M ′′ (a ¬i ℓ-1: )⟩. The reader may wonder if private occupancy states are sufficient statistics for optimally solving slave games through private occupancy-state Markov decision processes. One way to prove this claim is to demonstrate that private occupancy states are sufficient statistics of private plan-time histories for optimally solving M ′′ (a ¬i 0: ), as private plan-time histories are proven to preserve the ability to solve the original slave games optimally, as outlined in Proposition 3.

Sufficiency of Private Occupancy States

This subsection illustrates how private occupancy states can act as sufficient statistics for the complete data accessible to the trusted third party who is reasoning on behalf of agent i in any given slave game M (a ¬i 0: ) (or M ′ (a ¬i 0: )). These statistics are sufficient for optimally solving any slave game. Using this as a basis, we prove that the optimal action-and statevalue functions of a slave game M (a ¬i 0: ) (or M ′ (a ¬i 0: )) depend on private plan-time histories only through private occupancy states.

Theorem 3. For each agent i, the private occupancy state at time step t, defined as

s i t . = Pr{X t , O t |y i t }
, is a sufficient statistic of the private plan-time history y i t for optimally solving M ′ (a ¬i 0: ), i.e.,

E{ ℓ-1 τ =t γ τ -t • r i M ′′ (S i τ , U i τ )|s i t , a i t: , a ¬i 0: } = E{ ℓ-1 τ =t γ τ -t • r i M ′ (Y i τ , U i τ )|y i t , a i t: , a ¬i 0: }.
Also, an optimal solution for M ′′ (a ¬i 0: ) is also a solution for M (a ¬i 0: ) (respectively, M ′ (a ¬i 0: )).

To prove this theorem, we must establish three properties. Firstly, we need to prove that private occupancy states are enough to accurately predict the probability of an observation being received by agent i after taking action u i t , as stated in Lemma 9. Secondly, we must show that the private occupancy states describe a Markov process, meaning that the current private occupancy state is enough to estimate the next one, as stated in Lemma 10. Finally, we must prove that the private occupancy states are sufficient to accurately estimate the immediate reward when taking action u i t , as stated in Lemma 11. In the following, we will establish these three fundamental properties to demonstrate the sufficiency of private occupancy states of private plan-time histories for optimally solving slave games.

u i t -i.e., ω i M ′ (z i t+1 |y i t , u i t ) = ω i M ′′ (z i t+1 |s i t , u i t ).
Proof. For each agent i, the probability of private observation z i t+1 at the end of time step t + 1 can be rewritten as the sum over all possible hidden states x t , and joint histories o ¬i t , and private actions u ¬i t at the end of time step t, as well as all joint observations z ¬i t+1 , and hidden states x t+1 at the end of time step t + 1, i.e.,

ω i M ′ (z i t+1 |y i t , u i t ) . = Pr{z i t+1 |y i t , a ¬i t , u i t } = xt∈X o ¬i t ∈O ¬i t u ¬i t ∈U ¬i z ¬i t+1 ∈Z ¬i x t+1 ∈X Pr{x t , o ¬i t , u ¬i t , z ¬i t+1 , x t+1 |y i t , a ¬i t , u i t }.
The application of Bayes' rule and the replacement of y i t by (s 0 , o i t , a ¬i :t-1 ) yield

ω i M ′ (z i t+1 |y i t , u i t ) = xt∈X o ¬i t ∈O ¬i t u ¬i t ∈U ¬i z ¬i t+1 ∈Z ¬i x t+1 ∈X Pr{s 0 , x t , o t , u t , z t+1 , x t+1 , a ¬i :t } Pr{y i t , a ¬i t , u i t } . ( 5
)
The expansion of the joint probability in (5) as a product of conditional probabilities yields

ω i M ′ (z i t+1 |y i t , u i t ) = xt∈X o ¬i t ∈O ¬i t u ¬i t ∈U ¬i z ¬i t+1 ∈Z ¬i x t+1 ∈X Pr{z t+1 , x t+1 |s 0 , x t , o t , u t , a ¬i :t } • Pr{u ¬i t |s 0 , x t , o t , a ¬i :t , u i t } • Pr{x t , o ¬i t |y i t , a ¬i t , u i t } • Pr{y i t , a ¬i t , u i t }/ Pr{y i t , a ¬i t , u i t }. ( 6
)
The first probability in ( 6) is simply the dynamics (p

utz t+1 xtx t+1 ) of M , i.e., ω i M ′ (z i t+1 |y i t , u i t ) = xt∈X u ¬i t ∈U ¬i z ¬i t+1 ∈Z ¬i x t+1 ∈X p utz t+1 xtx t+1 o ¬i t ∈O ¬i t Pr{u ¬i t |s 0 , x t , o t , a ¬i :t , u i t } • Pr{x t , o ¬i t |y i t , a ¬i t , u i t }. ( 7
)
The second probability in (7) defines the probability of taking joint action u ¬i t upon experiencing joint history o ¬i t , i.e.,

ω i M ′ (z i t+1 |y i t , u i t ) = xt∈X u ¬i t ∈U ¬i z ¬i t+1 ∈Z ¬i x t+1 ∈X p utz t+1 xtx t+1 o ¬i t ∈O ¬i t a ¬i t (u ¬i t |o ¬i t ) • Pr{x t , o ¬i t |y i t , a ¬i t , u i t }. ( 8
)
The third probability in (8) defines the probability of the previous private occupancy state at hidden state x t and joint history o t , i.e.,

ω i M ′ (z i t+1 |y i t , u i t ) = xt∈X u ¬i t ∈U ¬i z ¬i t+1 ∈Z ¬i x t+1 ∈X p utz t+1 xtx t+1 o ¬i t ∈O ¬i t a ¬i t (u ¬i t |o ¬i t ) • s i t (x t , o t ) . = ω i M ′′ (z i t+1 |s i t , u i t ).
Which ends the proof.

Based on

i t+1 ) = ρ i M ′′ (s i t , u i t , z i t+1 ).
Proof. In demonstrating the sufficiency of private occupancy states, we also derive the rule for updating private occupancy states from one time step to the next. For the process defined by M ′ (a ¬i 0: ), the only information that agent i obtains during time step t is the fact that a particular decision rule a ¬i t has been followed by agents ¬i, private action u i t has been executed by agent i, and private observation z i t+1 has been received at the end of time step t + 1 by agent i, then we can write

y i t+1 . = (y i t , a ¬i t , u i t , z i t+1 ).
That is, y i t+1 represents the private plan-time history of agent i before time step t + 1 plus the additional information that a particular decision rule and private action were recorded and private observation occurred. By Definition 22, private occupancy states are written as follows: for every hidden state x t+1 , history o ¬i t , action u ¬i t , and observation z ¬i t+1 ,

s i t+1 (x t+1 , (o t , u t , z t+1 )) . = Pr{x t+1 , o ¬i t , u ¬i t , z ¬i t+1 |y i t+1 }. (9)
The application of Bayes' rule and the substitution of y i t+1 by (y i t , a ¬i t , u i t , z i t+1 ) in ( 9) yield

s i t+1 (x t+1 , (o ¬i t , u ¬i t , z ¬i t+1 , o i t+1 )) = Pr{s 0 , o t , u t , z t+1 , x t+1 , a ¬i :t }/ Pr{y i t+1 }. (10)
The expansion of (10) over all hidden states x t produces

s i t+1 (x t+1 , (o ¬i t , u ¬i t , z ¬i t+1 , o i t+1 )) = xt∈X Pr{s 0 , x t , o t , u t , z t+1 , x t+1 , a ¬i :t }/ Pr{y i t+1 }. ( 11
)
The expansion of the joint probability in the numerator of (11) as a product of conditional probabilities yields

s i t+1 (x t+1 , (o ¬i t , u ¬i t , z ¬i t+1 , o i t+1 )) = xt∈X Pr{z t+1 , x t+1 |s 0 , x t , o t , u t , a ¬i :t } • Pr{u ¬i t |s 0 , x t , o t , a ¬i :t , u i t } • Pr{x t , o ¬i t |s 0 , o ¬i t , a ¬i :t , u i t } • Pr{s 0 , o ¬i t , a ¬i :t , u i t } Pr{y i t+1 } . ( 12
)
The first probability in the numerator of ( 12) is independent of private plan-time history y i t , decision rule a ¬i t at the end of time step t; it is simply the dynamics of M , i.e.,

s i t+1 (x t+1 , (o ¬i t , u ¬i t , z ¬i t+1 , o i t+1 )) = xt∈X p utz t+1 xtx t+1 • Pr{u ¬i t |s 0 , x t , o t , a ¬i :t , u i t } • Pr{x t , o ¬i t |s 0 , o ¬i t , a ¬i :t , u i t } • Pr{y i t , a ¬i t , u i t } Pr{y i t+1 } . ( 13
)
The second probability in the numerator of ( 13) defines the probability of taking joint action u ¬i t of agents ¬i upon experiencing joint history o ¬i t , i.e.,

= xt∈X p utz t+1 xtx t+1 • a ¬i t (u ¬i t |o ¬i t ) • Pr{x t , o ¬i t |s 0 , o ¬i t , a ¬i :t+1 , u i t } • Pr{y i t ,a ¬i t ,u i t } Pr{y i t+1 } . (14) (9)
Moreover, the third probability in the numerator of ( 14) will be independent of private action u i t as well as decision rule a ¬i t , since current decision rule alternatives do not affect current joint history. Hence, it defines the probability of the previous private occupancy state at hidden state x t and joint history o ¬i t , i.e.,

= xt∈X p utz t+1 xtx t+1 • a ¬i t (u ¬i t |o ¬i t ) • s i t (x t , o t ) • Pr{y i t , a ¬i t , u i t } Pr{y i t+1 } . ( (9)
) 15
The last probability in the numerator of ( 15) can be simplified by the denominator in (15), i.e.,

= xt∈X p utz t+1 xtx t+1 • a ¬i t (u ¬i t |o ¬i t ) • s i t (x t , o t )/ Pr{z i t+1 |y i t , a ¬i t , u i t }. (9)
From Lemma 9, we know the denominator in ( 16) depends on private plan-time history y i t only through corresponding private occupancy state s i t , i.e.,

= xt∈X p utz t+1 xtx t+1 • a ¬i t (u ¬i t |o ¬i t ) • s i t (x t , o t )/ Pr{z i t+1 |s i t , a ¬i t , u i t }. (9)
where

ω i M ′′ (z i t+1 |s i t , u i t ) . = Pr{z i t+1 |s i t , a ¬i t , u i t }
serves as a normalizing constant. The important feature of the update rule of private occupancy states is that the calculation of the private occupancy states after time step t + 1 requires only s i t , the private occupancy state at time step t; thus, s i t+1 summarizes all the information gained before time step t and represents a sufficient statistic of the complete data y i t+1 available to agent i for predicting the joint history.

Lemma 10 essentially states that private occupancy states describe a Markov process.

Lemma 11. For each agent i, the private occupancy state at time step t, defined as

s i t . = Pr{X t , O t |y i t }
, is a sufficient statistic of the private plan-time history y i t for an accurate prediction of the expected reward that will be received immediately after executing the private action

u i t , i.e., r i M ′ (y i t , u i t ) = r i M ′′ (s i t , u i t ).
Proof. The proof starts with the definition of the expected reward conditional on private plan-time history y i t , the joint decision rule a ¬i t of agents ¬i, and private action u i t of agent i, i.e.,

r i M ′ (y i t , u i t ) . = E{r i Xt,Ut |y i t , a ¬i t , u i t } = xt∈X u ¬i t ∈U ¬i r i Xt,Ut o ¬i t ∈O ¬i t Pr{x t , o ¬i t , u ¬i t |y i t , a ¬i t , u i t }. (17)
The expansion of the joint probability in (17) as a product of conditional probabilities produces

(17) = xt∈X u ¬i t ∈U ¬i r i xtut o ¬i t ∈O ¬i t Pr{u ¬i t |o ¬i t , y i t , a ¬i t , u i t } • Pr{x t , o ¬i t |y i t , a ¬i t , u i t }. (18)
The first probability in (18) describes the probability of taking joint action u ¬i t given joint history o ¬i t and joint decision rule a ¬i t of agents ¬i, i.e.,

= xt∈X u ¬i t ∈U ¬i r i xtut o ¬i t ∈O ¬i t a ¬i t (u ¬i t |o ¬i t ) • Pr{x t , o ¬i t |y i t , a ¬i t , u i t }. (17)
The second probability in ( 19) describes the probability of the hidden state being x t and the other agents having joint history o ̸ i t at the current private occupancy state, i.e.,

= xt∈X u ¬i t ∈U ¬i r i xtut o ¬i t ∈O ¬i t a ¬i t (u ¬i t |o ¬i t ) • s i t (x t , o t ). (17)
Which ends the proof.

The three lemmas, namely Lemma 9, Lemma 10, and Lemma 11, establish that private occupancy states are enough to serve as statistics for private plan-time histories. These lemmas also describe a Markov decision process with discrete time and continuous states. The bestresponse policy a i 0: for the private occupancy-state Markov decision process M ′′ (a ¬i 0: ) can also be used as the best-response policy for the private plan-time Markov game M ′ (a ¬i 0: ) (and M (a ¬i 0: )):

a i t (φ i M ′ (y i t )) (20) ∈ arg max u i t ∈U i q i M (a ¬i 0: ),γ,t (o i t , u i t ) ∈ arg max u i t ∈U i q i M ′ (a ¬i t: ),γ,t (y i t , u i t ) ∈ arg max u i t ∈U i r i M ′ (y i t , u i t ) + γ z i t+1 ∈Z i ω i M ′ (z i t+1 |y i t , u i t ) • υ i M ′ (a ¬i t+1: ),γ,t+1 (y i t , u i t , z i t+1 ) (21) ∈ arg max u i t ∈U i r i M ′′ (s i t , u i t ) + γ z i t+1 ∈Z i ω i M ′′ (z i t+1 |s i t , u i t ) • υ i M ′′ (a ¬i t+1: ),γ,t+1 (s i t , u i t , z i t+1 ) (22) ∈ arg max u i t ∈U i q i M ′′ (a ¬i t: ),γ,t (s i t , u i t ).
By applying Lemmas 9, 10, and 11 to Equation (21), we can arrive at Equation ( 22). Therefore, it can be concluded that private occupancy states act as sufficient statistics of private histories and private plan-time histories, which enables to optimally solving slave games according to Theorem 3.

Occupancy States As Mixtures of Private Occupancy States

The subsection explores the relationship between sufficient statistics for a master game and its corresponding slave games. It demonstrates that occupancy states can be expressed using various basis sets. While the typical representation of occupancy states uses the canonical basis, a finite collection of unit vectors, one can also rewrite occupancy states based on the private occupancy states of a fixed agent. These basis changes are crucial when identifying the convexity properties of state-and action-value functions for the master game As we will illustrate, certain state-and action-value functions only reveal their structure when expressed under a specific basis set.

s t = o i t ∈O i t λ i,o i t • s i,o i t t such that o i t ∈O i t λ i,o i t = 1 and λ i,o i t ≥ 0. ( 23
)
Proof. The proof starts with the definition of occupancy states, i.e., for any time step t and plan-time history y t . = (s 0 , a :t-1 , w 1:t ), we have:

s t (x t , o t ) . = Pr{x t , o t |y t }, ∀x t ∈ X , o t ∈ O t . ( 24
)
The expansion of (24) with histories o i t ∈ O i t of agent i leads to

s t (x t , o t ) = o i t ∈O i t Pr{x t , o t , o i t |y t }. (25)
The expansion of (25) as the product of conditional probability distributions gives

s t (x t , o t ) = o i t ∈O i t Pr{x t , o t , |o i t , y t } • Pr{o i t |y t }. (26)
The first factor in (26) depends on a i :t-1 only through o i t . It simply corresponds to private occupancy state given by s

i,o i t t (x t , o t ) . = Pr{x t , o t |s 0 , a ¬i :t-1 , o i t }, i.e., s t (x t , o t ) = o i t ∈O i t s i,o i t t (x t , o t ) • Pr{o i t |y t }. (27)
The second factor in ( 27) is simply a non-negative coefficient, denoted λ i,o i t , defining the probability of history o i t when agents follow joint policy a :t-1 starting in an initial belief state s 0 , i.e.,

s t (x t , o t ) = o i t ∈O i t λ i,o i t • s i,o i t t (x t , o t ).

It is worth noticing that

o i t ∈O i t λ i,o i t = o i t ∈O i t Pr{o i t |y t } = 1. Which ends the proof. s B 0 1 s B 1 1 .5 ∅∅ u l , u ol z hl , z hl .25
x tl

.25

x tr z hl , z hr .25

x tl

.25

x tr

.5

∅∅ u l , u ol z hr , z hl .25

x tl

.25

x tr z hr , z hr .25

x tl

.25

x tr ∅∅ u l , u ol z hl , z hl .125

x tl

.125

x tr z hr , z hr .125

x tl

.125

x tr z hr , z hl .125

x tl

.125

x tr z hl , z hr .125

x tl

.125

x tr Figure 14: Tree representations of occupancy state s 1 in both B 0 and B 1 for the case with no public observations.

Lemma 12 provides an alternative perspective on the nature of occupancy states. An occupancy state is a mathematical entity that captures the state of an occupancy-state Markov game M ′ from various viewpoints.

So far, we have described occupancy states from the perspective of the central planner, using the standard coordinate system, i.e.,

s t = (xt,ot)∈X ×Ot
λ (xt,ot) • e (xt,ot) such that (xt,ot)∈X ×Ot λ (xt,ot) = 1 and λ (xt,ot) ≥ 0

where e (xt,ot) is a one-hot vector associated with pair (x t , o t ) ∈ X × O t . In the canonical basis B 0 , which consists of all elements e (xt,ot) where (x t , o t ) is in X × O t , the occupancy state s B 0 t is represented as (λ (xt,ot) ) (xt,ot)∈X ×Ot . This representation is objective because neither agents nor the central planner can access general information on states and joint histories denoted as (x t , o t ). This representation is useful in multi-agent systems without self-interested agents, such as dec-POMDPs. However, more informative coordinate systems are needed in self-interested games like zs-POSGs or st-POSGs. Therefore, private occupancy states

s i,o i t t
from agent i's perspective are used to describe occupancy states in M ′′ , as shown in Equation ( 23). These private occupancy states convey information on the occupancy state s t in M ′′ given that agent i experienced private history o i . Interestingly, using either the basis of canonical occupancy states in Equation ( 28) or the basis of private occupancy states for agent i in

B i = {s i,o i t : o i t ∈ O i t }
results in the same information on the occupancy state of M ′ , but in different coordinate systems. The vector s B i t expresses the occupancy state using the basis set B i , specific to agent i. Figure 14 illustrates two different representations of the same occupancy state, where s B 0 1 = (.125 .125 .125 .125 .125 .125 .125 .125 ) and s B 1 1 = (.5 .5). Despite the significant differences between vectors s B 0 t and s B i t , they convey the same occupancy state using different languages or basis sets.

Convexity of Optimal Value Functions of Master Games

In this section, we are ready to present the main findings of our research. Our focus initially is on the uniform continuity features of state-value functions in slave games. Secondly, we will demonstrate the correlation between solutions for a master game and its corresponding slave games. Lastly, we will provide evidence for the three convexity properties for statevalue functions in specific and significant master games.

Piecewise Linearity and Convexity

This subsection demonstrates the piecewise linear and convex nature of optimal state-value functions over private occupancy states in private occupancy-state Markov games. It is worth noting that the sufficiency of private occupancy states concerning private plan-time history for optimally solving private occupancy-state Markov games facilitates the ability to recover the solution of the original slave game. Proof. To prove piecewise linearity and convexity, it is important to note that all bestresponse policies result in a unique state-value function. This means mixed best-response policies are just as good as pure policies in their support. Therefore, when searching for the optimal value function for a slave game, one can focus solely on pure best-response policies. We define the optimal value for any given time step t and private occupancy state s i t to derive the property. = max a i t: ∈A i,pure t:

υ i M ′′ (
υ i,at: M ′′ ,γ,t (s i t ).
The point-wise maximum of linear functions over private occupancy states is a piecewise linear and convex function of private occupancy states.

Theorem 4 establishes that for any slave game, the optimal state-value functions are piecewise linear and convex over private occupancy states. In the case of a two-agent one-sided POSG, where agent 2 perceives both the underlying state of the game as well as the actions and perceptions of agent 1, the optimal state-value functions ⟨υ 1 M ′′ (s 0 ,a 2 0: ),γ,0 , υ 1

M ′′ (a 2 1: ),γ,1 , . . . , υ 1 M ′′ (a 2
ℓ-1: ),γ,ℓ-1 ⟩ of the slave game are tabular functions that map underlying states to real values.

Corollary 2. For any arbitrary time step t, the slave game M ′′ (a ¬i 0: ) has a piecewise linear and convex (PWLC) optimal action-value function of private occupancy states q i M ′′ (a ¬i t: ),γ,t : S i t × U i → R. Consequently, at each time step t there exists a finite collection of linear functions of private occupancy states, denoted as Q M ′′ (a ¬i t: ),γ,t , s.t. for any private occupancy state s i t , it follows:

q i M ′′ (a ¬i t: ),γ,t (s i t , u i t ) = max q i,a t: M ′′ ,γ,t ∈Q M ′′ (a ¬i t:
),γ,t q i,at: M ′′ ,γ,t (s i t , u i t ).

Corollary 3 shows optimal state-value functions are piecewise linear and convex over occupancy states in the standard basis for any slave game.

υ i M ′′ (a ¬i t: ),γ,t (s B 0 t ) = max υ i,a t: M ′′ ,γ,t ∈V M ′′ (a ¬i t:
),γ,t υ i,at: M ′′ ,γ,t (s B 0 t ).

Optimal Value Functions Are Convex

This subsection presents our key finding. However, we must first demonstrate that the optimal state-value function of the slave game M ′′ (a ¬i 0: ) (as well as M ′ (a ¬i 0: ) and M (a ¬i 0: )) can be expressed as a linear function of occupancy states from the perspective of agent i, using the basis B i . This proof is based on the premise that private occupancy states are sufficient for determining the optimal state-value function of slave game M ′′ (a ¬i 0: ) and the representation of occupancy states as a combination of private occupancy states. Before proceeding, we would like to establish some fundamental preliminary results.

Lemma 13. For each agent i, the immediate expected reward function over occupancy states, denoted as r i M ′′ :

S B i ×A i → R,
r i M ′′ (s B i t , a i t ) = o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i |o i ) • r i M ′′ (s i,o i t t , u i t ).
Proof.

o i t ∈O i t λ i,o i t = 1 λ i,o i t ≥ 0.
Re-arranging terms leads to

(29) = o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i t |o i t )   xt∈X o ¬i t ∈O ¬i t s i,o i t t (x t , o t ) u ¬i t ∈U ¬i a ¬i t (u ¬i t |o ¬i t ) • r i xt,ut   . ( 30
)
The injection of r i M ′′ (s i,o i t t , u i t ) into the expression in the parentheses of (30) yields

r i M ′′ (s B i t , a i t ) = o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i t |o i t ) • r i M ′′ (s i,o i t t , u i t ),
which ends the proof.

Lemma 13 demonstrates a property that is easily proven for occupancy states expressed in the standard basis. This lemma confirms that the linearity property of the immediate reward remains valid regardless of the agent viewpoint, as long as occupancy states are expressed on the corresponding basis.

Lemma 14. For each agent i, the transition rule over occupancy states expressed in B i , denoted as

ρ i M ′ : S B i ×A i → S B i ,
) . = Pr{o i t , u i t , z i t+1 |s B i t , a i t }, (31)
The expansion of (31) over all hidden states x t , x t+1 , private action u ¬i t , joint history o ¬i t , and joint observation z ¬i t+1 yields,

s B i t+1 (s i,(o i t ,u i t ,z i t+1 ) t+1 ) = xt,x t+1 ∈X u ¬i t ∈U ¬i o ¬i t ∈O ¬i t z ¬i t+1 ∈Z ¬i Pr{x t , u t , o t , x t+1 , z t+1 |s B i t , a i t }.
The expansion of the joint probability into the product of conditional probabilities gives

s B i t+1 (s i t+1 ) = o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i t |o i t ) z i t+1 ∈Z i ω i M ′′ (z i t+1 |s i,o i t t , u i t ) • δ ρ i M ′′ (s i,o i t t ,u i t ,z i t+1 ) (s i t+1 ). (33)
The injection of

p i M ′′ (s i,o i t t , u i t , s i,(o i t ,u i t ,z i t+1 ) t+1
), cf. Definition 23, into (33) yields:

s B i t+1 = o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i t |o i t ) z i t+1 ∈Z i p i M ′′ (s i,o i t t , u i t , s i,(o i t ,u i t ,z i t+1 ) t+1 ) • s i,(o i t ,u i t ,z i t+1 ) t+1
. which ends the proof.

Like the previous lemma, Lemma 14 demonstrates that the transition from one occupancy state to another is a linear function, regardless of the basis used or the perspective of any agent. The selection of the decision rules, known as the policy of agent i, creates a nonobservable and deterministic Markov game, which is another occupancy-state Markov game from the perspective of agent i. Definition 24. A n-agent, simultaneous-move, occupancy Markov game w.r.t. M ′′ (a ¬i 0: ) is given by a tuple ⟨S B i , A i , ρ i M ′′ , r i M ′′ ⟩, where S B i is the occupancy-state space, occupancy states being conditional probability distributions over private occupancy states given a joint policy followed so far; A i is the space of actions describing decision rules of agent i; ρ i M ′′ : S B i × A i → S B i is the deterministic transition rule, and r i M ′′ : S B i × A i → R describes the linear reward function over occupancy states.

It is worth noting that M ′′ (a ¬i 0: ) serves as a restricted version of M ′′ , which solely takes into account the occupancy states based on the joint policy a ¬i 0: of all agents, except for agent i. Private occupancy states suffice to optimally solve M ′′ (a ¬i 0: ) (and M (a ¬i 0: )). Additionally, M ′ (a ¬i 0: ) (and M (a ¬i 0: )) encompass a finite number of private occupancy states. Therefore, the optimal value function over private occupancy states can be represented as a tabular function, which ultimately becomes a finite vector of values. This leads to a crucial conclusion.

Theorem 5. For each agent i, the t-step optimal state-value function for slave game M ′′ (a ¬i 0: ) (respectively M ′ (a ¬i 0: ) and M (a ¬i 0: )), denoted as υ

. = o i t ∈O i t λ i,o i t • s i,o i t t such that o i t ∈O i t λ i,o i t = 1 and λ i,o i t ≥ 0, υ i M ′′ (a ¬i t: ),γ,t (s B i t ) = o i t ∈O i t λ i,o i t • υ i M ′′ (a ¬i t: ),γ,t (s i,o i t t ).
Proof. The proof proceeds by induction. The statement trivially holds at time step t = ℓ, since υ i,• M ′′ ,γ,ℓ (•) = 0. Suppose the statement holds from time step t + 1 onward-i.e.,

υ i M ′′ (a ¬i t+1: ),γ,t+1 (s B i t+1 ) = o i t+1 ∈O i t+1 λ i,o i t+1 • υ i M ′′ (a ¬i t+1: ),γ,t+1 (s i,o i t+1 t+1
).

We can now prove it also holds for time step t. We start with the definition of the optimal state-value function for slave game M ′′ (a ¬i 0: ) given any arbitrary occupancy state s B i t at any time step t, i.e.,

υ i M ′′ (a ¬i t: ),γ,t (s B i t ) . = max a i t: ∈A i t: υ i,at: M ′′ ,γ,t (s B i t ). (34)
Bellman's optimality equations allow us to rewrite (34) as follows

(34) = max a i t ∈A i t r i M ′′ (s B i t , a i t ) + γ max a i t+1: ∈A i t+1: υ i,a t+1: M ′′ ,γ,t+1 (ρ i M ′′ (s B i t , a i t )) . ( 35
)
Re-arranging terms in ( 35) using (34) leads us to the following expression

(34) = max a i t ∈A i t r i M ′′ (s B i t , a i t ) + γυ i M ′′ (a ¬i t+1: ),γ,t+1 (ρ i M ′′ (s B i t , a i t )) . ( 36
)
Using the induction hypothesis, Lemma 14, and Lemma 13 into (36) yields

(34) = max a i t ∈A i t o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i t |o i t ) r i M ′′ (s i,o i t t , u i t ) + γ z i t+1 ∈Z i p i M ′′ (s i,o i t t , u i t , s i,(o i t ,u i t ,z i t+1 ) t+1 ) • υ i M ′′ (a ¬i t+1: ),γ,t+1 (s i,(o i t ,u i t ,z i t+1 ) t+1
) Re-arranging terms using definition of action-value function q i M ′′ (a ¬i t: ),γ,t gives the following expression

(34) = max a i t ∈A i t o i t ∈O i t λ i,o i t u i t ∈U i a i t (u i t |o i t ) • q i M ′′ (a ¬i t: ),γ,t (s i,o i t t , u i t )
One can reason independently for each private occupancy state s i,o i t t , which produces

(34) = o i t ∈O i t λ i,o i t max u i t ∈U i q i M ′′ (a ¬i t: ),γ,t (s i,o i t t , u i t ).
Hence, we have

(34) = o i t ∈O i t λ i,o i t • υ i M ′′ (a ¬i t: ),γ,t (s i,o i t t ).
Which ends the proof.

Theorem 5 states that the optimal state-value functions for any slave game, denoted as M ′′ (a ¬i 0: ), M ′ (a ¬i 0: ) and M (a ¬i 0: ), are linear over occupancy states expressed in the right basis. This holds true regardless of whether agent i maximizes or minimizes the γ-discounted sum of rewards. This theorem is a useful tool for establishing convexity properties in various classes of games.

Replacing value function υ i,at: M,γ,t by υ ¬i,at: M,γ,t into (37) using the zero-sum property of the game, i.e., υ i,at: M,γ,t + υ ¬i,at: M,γ,t = 0, yields:

υ i, * M ′′ ,γ,t (s B ¬i t ) . = max a i t: ∈A i t:
max a ¬i t: ∈A ¬i t:

E{υ ¬i,at:

M,γ,t (X t , O t )|s B ¬i t }. ( 38
)
The application of Lemma 7 into (38) results in the following expression:

υ i, * M ′′ ,γ,t (s B ¬i t ) = max a i t: ∈A i t:
max a ¬i t: ∈A ¬i t:

υ ¬i,at:

M ′′ ,γ,t (s B ¬i t ). ( 39
)
The application of Theorem 5 into (39) results in the following expression:

υ i, * M ′′ ,γ,t (s B ¬i t ) = max a i t: ∈A i t:
-υ ¬i Theorem 6 shows that the optimal state-value functions for an agent operating in a zero-sum game M , either maximizing or minimizing, are either convex or concave functions of the occupancy states expressed in the opponent viewpoint. It is inappropriate to assume that the optimal value functions of the zero-sum game M are linear since the basis differs between agents. Remarkably, the stronger uniform continuity property is that these optimal statevalue functions represent the maximum of concave functions over occupancy states expressed in the standard basis. As discussed later, when the former uniform continuity property fails, the latter still applies. In the case of a two-agent one-sided zs-POSG, where agent 2 perceives both the underlying state of the game as well as the actions and perceptions of agent 1, the optimal state-value functions υ 1, * M ′′ ,γ,0: of the master game are convex functions of the belief states. We shall now focus on another essential subclass of POSGs: st-POSGs.

s B 2 t , s B 2 t . = o 2 t ∈O 2 t λ 2,o 2 t • s 2,o 2 t t such that o 2 t ∈O 2 t λ 2,o 2 t = 1 and λ 2,o 2 t ≥ 0 υ 1, * M ′′ ,γ,t (s B 2 t ) = max υ 1 M ′′ (a 1 t: ),γ,t ∈Vt υ 1 M ′′ (a 1 t: ),γ,t (s B 2 t )
where υ 1 M ′′ (a

υ 1, * M ′′ ,γ,t (s B 2 t ) = max a 1 t: ∈A 1 t: s 2 t ∈supp(s B 2 t ) λ 2,s 2 t • υ 1 M ′′ (a 1 t: ),γ,t (s 2 t ). ( 41
)
The application of Theorem 5 into (41) results in the following expression:

υ 1, * M ′′ ,γ,t (s B 2 t ) = max a 1 t: ∈A 1 t: υ 1 M ′′ (a 1 t: ),γ,t (s B 2 t ). If we let V 1 t . = {υ 1 M ′′ (a 1 t:
),γ,t |a 1 t: ∈ A 1 t: } be a (possibly uncountable) collection of vectors, then we have that

υ 1, * M ′′ ,γ,t (s B 2 t ) = max υ 1 M ′′ (a 1 t: ),γ,t ∈V 1 t υ 1 M ′′ (a 1 t: ),γ,t (s B 2 t ).
Which ends the proof.

According to Theorem 7, the optimal state-value functions for strong Stackelberg equilibria from the leader's perspective are convex when expressed in terms of occupancy states from the follower's viewpoint. In the case of a two-agent one-sided st-POSG, where agent 2 perceives both the underlying state of the game as well as the actions and perceptions of agent 1, the optimal state-value functions υ 1, * M ′′ ,γ,0: of the master game are convex functions of the belief states. Moving forward, we will investigate the structure of the optimal statevalue function in common-reward partially observable stochastic games. }, then (42) holds. Which ends the proof

Discussion

The previous subsection elucidates the optimal state-value functions for zs-POSGs, st-POSGs, and dec-POMDPs, demonstrating that they are convex functions of occupancy states expressed on the appropriate basis. A crucial element in determining the appropriate basis for occupancy states is its ability to reveal the convexity properties of the optimal state-value functions. The standard basis for occupancy states, which possess stronger generalization capabilities, is sufficient to disclose the convexity properties of POSGs with a single criterion. However, it often fails to reveal the underlying convexity properties of the optimal state-value functions for POSGs with two criteria, one per agent.

For instance, in dec-POMDPs, the objective is to find a joint policy that maximizes the expected discounted cumulative reward. [START_REF] Jilles | Optimally solving dec-POMDPs as continuous-state MDPs[END_REF] established that the optimal state-value function for partially observable stochastic games with common reward is piecewise linear and convex in the occupancy state expressed in the standard basis. Theorem 8 explicitly connects the optimal state-value functions for the best-response problems. Conversely, in zs-POSGs and st-POSGs, the aim is to discover joint policies that maximize the expected discounted cumulative reward of one agent while simultaneously constraining on the expected discounted cumulative reward of the other. In the latter, the basis of interest is determined by the private occupancy states of the other agents. Occupancy states expressed on this basis can reveal the convexity properties of the optimal statevalue functions for zs-POSGs and st-POSGs. Notice, however, that not all bases have the same generalization power. The standard basis, a collection of one-hot vectors, exhibits a stronger generalization power than the basis from the opponent's viewpoint. Unfortunately, the optimal state-value functions for zs-POSGs and st-POSGs are not convex functions of occupancy states expressed on the standard basis as illustrated in the following example. optimal state-value function over the initial occupancy states expressed in the standard basis cannot generally be convex. This negative property holds at the initial stage of the game and throughout its progression.

Theorem 6 establishes the property of convexity for zero-sum partially observable stochastic games (zs-POSGs) over occupancy states expressed as distributions over private occupancy states. However, it is noteworthy that when the occupancy states match the private occupancy states, the convexity property vanishes. Convex functions of occupancy states expressed in the standard basis permit generalization from one private occupancy state to another, as seen in Figure 16. Conversely, convex functions of distributions over private occupancy states do not allow for generalization from one private occupancy state to another, with the only known exception being when private occupancy states simplify into the underlying states, such as in one-sided two-agent POSGs, as illustrated in Figure 17. In such games, the optimal state-value functions are convex functions of the belief states.

It is worth noting that the convexity property outlined in Theorem 6 is not applicable during the initial stage of zs-POSGs, as all initial occupancy states are also private occupancy states. Therefore, it is not a useful tool in this particular scenario. This same limitation applies to st-POSGs. However, in zs-POSGs, it is possible to leverage the maximum of concave functions and generalize from one occupancy state to another, even during the first stage of the game, as demonstrated in Figure 16. Unfortunately, st-POSGs do not offer this fallback solution.

Conclusion

Partially Observable Stochastic Games are extensively used to formalize various problems in multi-agent sequential decision-making. However, analyzing the underlying structure of optimal state-value functions is a difficult task, leading to inefficient planning and reinforcement learning algorithms. This paper proposes a three-step methodology to unveil the underlying structure of optimal state-value functions for subclasses of POSGs, including but not restricted to zs-POSGs, st-POSGs, and dec-POMDPs.

The first step involves recasting the original game as a master game and best-response problems as slave games viewed from the perspective of the central planner. The master and slave games are then reformulated as Markov games, where states are the plan-time total data available to the central planner. The second step of the methodology summarizes the plan-time total data available to the central planner using the concept of occupancy states. Occupancy states refer to a posterior probability distribution over hidden states of the game and the stream of actions and observations that agents may encounter at execution time. The final step of the approach blends together the optimal state-value functions from both slave and master games. In particular, it shows that changing the basis on which occupancy states are expressed from the standard basis to agent viewpoints reveals the underlying structures. It enabled us to prove that the optimal state-value functions for zs-POSGs, st-POSGs, and dec-POMDPs are convex functions of occupancy states expressed on the appropriate basis. [START_REF] Auke | Structure in the value function of two-player zero-sum games of incomplete information[END_REF] and [START_REF] Delage | and common-reward partially observable stochastic games[END_REF] previously exhibited underlying uniform continuity properties in the optimal state-value functions of zs-POSGs. Unfortunately, these properties are either hard to use in practice or provide poor generalization capabilities. Our findings provide uniform continuity properties of the optimal state-value functions that are either equal (e.g., dec-POMDPs) or stronger than pre-existed ones (e.g., zs-POSGs and st-POSGs), cf. Table 1. Table 1: Uniform continuity properties of optimal value functions of POSG M . We use notations such as "S B Convex" to indicate the convexity of the optimal value functions over occupancy states when expressed in basis B.

We have considered three perception assumptions to evaluate the accuracy and relevance of our main findings. Firstly, it must be acknowledged that in fully observable Markov games, optimal state-value functions are tabular functions of occupancy states for all twoagent and zero-sum, Stackelberg, and common reward criteria. These occupancy states are the underlying states of the game within this context, as stated by [START_REF] Puterman | Markov Decision Processes, Discrete Stochastic Dynamic Programming[END_REF], [START_REF] Filar | Competitive Markov decision processes[END_REF]. Secondly, we have examined the optimal state-value functions of POSGs with public actions and observations. In this case, the application of our analysis has shown that the optimal state-value functions are convex functions of the belief states for common reward criteria, as previously established by [START_REF] Smallwood | The optimal control of partially observable Markov decision processes over a finite horizon[END_REF], [START_REF] Sondik | The optimal control of partially observable markov decision processes over the infinite horizon: Discounted cost[END_REF]. Lastly, we have considered two-agent, one-sided POSGs. A direct application of our findings demonstrates that the optimal state-value functions of the one-sided POSGs are convex functions of the belief states for all two-agent and zero-sum, Stackelberg, as well as common reward criteria, as previously established by [START_REF] Horák | zero-sum partially observable stochastic games[END_REF], [START_REF] Xie | Optimally solving two-agent decentralized pomdps under one-sided information sharing[END_REF]. These results are consistent with previously established properties, thus providing additional support for the accuracy of our findings, even when applied to more restrictive settings.

To summarize, the proposed methodology provides a comprehensive approach to analyzing the underlying structure of optimal state-value functions in POSGs. This approach is particularly useful for specific subclasses, including but not restricted to zero-sum, Stackelberg, and common reward partially observable stochastic games, where it is crucial to uncover the underlying structure to develop efficient planning and reinforcement learning algorithms. The authors anticipate that these findings will serve as a foundation to reveal the fundamental structures of optimal state-value functions in other games and to develop more efficient planning and reinforcement learning algorithms that leverage these structural properties. Future work in that direction includes describing Bellman's optimality equations leveraging upon the exhibited structures of the optimal state-value functions along the design of appropriate algorithms capable of exploiting these structures. This approach has proven particularly successful in many narrow settings including but not restricted to one-sided partially observable stochastic games [START_REF] Hadfield-Menell | Cooperative inverse reinforcement learning[END_REF]

Figure 1 :

 1 Figure 1: The paper employs a three-step transformation methodology to convert original games into appropriate representations for optimal decision-making. The methodology involves the use of several game-theoretic models, including Partially Observable Stochastic Game (POSG), Partially Observable Markov Decision Process (POMDP), Markov Decision Process (MDP), Plan-Time Markov Game (PTMG), and Occupancy-State Markov Game (OMG). Best viewed in color.

Figure 2 :

 2 Figure 2: Illustration of agents and their environment for the tiger problem.

Figure 3 :

 3 Figure 3: A graphical model of a two-agent, partially observable stochastic game.

Figure 5 .

 5 Definition 9. Consider the master game M . A slave game M (a ¬i 0:

Figure 5 :

 5 Figure 5: Illustration of agents and their environment for the tiger problem where Calvin acts according to a public and fixed policy.

Figure 7 :

 7 Figure 7: A plan-time environment for the tiger problem from the perspective of a trusted third party. While each agent knows its decision and perception, which may differ from one agent to the other, the trusted third party has only access to public observations about the plan-time environment.

Figure 8 :

 8 Figure 8: Influence diagram for a plan-time Markov game.

Figure 10 :

 10 Figure 10: Influence diagram for an occupancy-state Markov game.

Figure 11 :

 11 Figure 11: A plan-time environment for the tiger problem from the perspective of the trusted third party, now reasoning only on behalf of Suzie given that Calvin's policy is plan-time. He knows Suzie's decisions and perceptions, but when it comes to Calvin, he has only access to public observations, including Calvin's policy and the plan-time environment.

Figure 12 :

 12 Figure 12: Influence diagram for a private plan-time Markov game.

Figure 13 :

 13 Figure 13: Influence diagram for a private occupancy-state Markov game.

Example 3 .Figure 16 :Figure 17 :

 31617 Figure 16: The figure showcases the optimal state-value functions for the one-stage tiger game. Best viewed in color.

  Consider a zs-POSG M . The t-step optimal state-value function υ i, * M,γ,t : P(X × O t ) → R is κ t -Lipschitz continuous over occupancy states. There exists a collection V i t of linear functions across marginal occupancy states such that for any occupancy state s t .

	= s m,¬i t	⊙ s c,¬i t	, and vector υ ¬i M (s c,¬i t	,a i t: ),γ,t	∈ V i t associated to conditional
	occupancy state sc,¬i

t

, the following holds:

.

  Definition 16. A t-step occupancy state s t is a posterior probability distribution over hidden states and joint histories conditional upon a t-step plan-time history y t , i.e., for any arbitrary hidden state x

		plan-time history y 1		occupancy state s 1
	∅		∅		∅∅
	u l		u ol		u l , u ol
	z hl	z hr	z hl	z hr	z hl , z hl
	?	?	?	?	.125

t , joint history o t , s t (x t , o t ) . = Pr{x t , o t |y t }.

  A is the space of actions describing joint decision rules; W is the space of public observations available to all agents involved in the game. Mappings ρ M ′′ , ω M ′′ , p M ′′ , and r M ′′ are described as follows: and receiving public observation w t+1 -i.e., for any arbitrary hidden state x t+1 , joint history o t , joint action u t , and joint (private) observation zt+1 ,

This convex space indicates that combining occupancy states by blending joint policies can produce a new occupancy state. These occupancy states describe a Markov game called the occupancy-state Markov game. In this game, the central planner simultaneously makes decisions for all agents and receives public observations as feedback, as shown in Figure 10. Definition 17. A n-agent, simultaneous-move, occupancy-state Markov game w.r.t. M ′ (resp. M ) is given by a tuple M ′′ . = ⟨S, A, W, ρ M ′′ , ω M ′′ , p M ′′ , r M ′′ ⟩, where S is the occupancystate space, occupancy states being conditional probability distributions over hidden states and joint histories; • The deterministic transition rule ρ M ′′ : S × A × W → S prescribes the next occupancy state s t+1 . = ρ M ′′ (s t , a t , w t+1 ) upon taking decision rule a t in occupancy state s t

  ′′ (s t , a t , s t+1 ) . = w∈W ω M ′′ (w t+1 |s t , a t ) • δ ρ M ′′ (st,at,w t+1 ) (s t+1 ).

		s 0	s t		s t+1	s t+2	• • •
			w t	w t+1	w t+2
			a 0	a t	a t+1
	Time	0	t		t + 1	t + 2	. . .
					prescribes the probability
	of receiving public observation w t+1 upon taking decision rule a t in occupancy state
	s t -i.e.,
	ω M ′′ (w t+1 |s t , a t )	. =	xt∈X ot∈Ot ut∈U x t+1 ∈X zt+1 ∈	Z p ut,⟨z t+1 ,w t+1 ⟩ xt,x t+1

• a t (u t |o t ) • s t (x t , o t ). • The transition probability model p M ′′ : S × A × S → [0, 1] defines the probability of reaching next occupancy state s t+1 upon taking decision rule a t in occupancy state s t -i.e., p M • The reward model r M ′′ : S × A → R n describes the linear reward function upon taking decision rule a t in occupancy state s t -i.e., r i M ′′ (s t , a t ) . = xt∈X ot∈Ot s t (x t , o t ) ut∈U a t (u t |o t ) • r i xt,ut .

  y t , a t ) = xt∈X ot∈Ot ut∈U Pr{x t |y t , a t , o t , u t } Pr{u t |y t , a t , o t } • r xt,ut • Pr{o t |y t }. ′ (y t , a t ) = xt∈X ot∈Ot ut∈U Pr{x t |y t , o t } Pr{u t |a t , o t } • r xt,ut • Pr{o t |y t }. Finally re-arranging terms, noticing that s t (x t , o t ) . = Pr{x, o|y t } = Pr{x t |y t , o t } • Pr{o t |y t } and a t (u t |o t ) . = Pr{u t |a t , o t }, we have that

	By removing terms that do not influence conditional probabilities, we obtain the following
	expression:
	r M

  of the plan-time history y t for predicting of the next public observation w t+1 following the executing of the decision rule a t , i.e., ω M ′ (w t+1 |y t , a t ) = ω M ′′ (w t+1 |s t , a t ). The proof starts with the definition of the probability of receiving public observation w t+1 upon taking decision rule a t in plan-time history y t , i.e., ω M ′ (w t+1 |y t , a

	Proof.

Lemma 4. The t-step occupancy state, defined as s t . = Pr{X t , O t |y t }, is a sufficient statistic t ) . = Pr{w t+1 |y t , a t }. The expansion of the conditional probability Pr{w t+1 |y t , a t } over hidden states x t , x t+1 , joint histories o t , and joint actions u t and joint private observations zt+1 , result in the following expression:

  zt+1 , w t+1 |x t , o t , u t , y t , a t } • Pr{x t |y t , a t , o t , u t } • Pr{u t |y t , a t , o t } • Pr{o t |y t , a t }

	Re-arranging terms

  Lemma 9. For each agent i, the private occupancy state at time step t, defined as s i

	. = t for prediction of t t }, is a sufficient statistic of the private plan-time history y i Pr{X t , O t |y i the next private observation z i t+1 following the execution of the private action

  Lemma 9, it is possible to make precise predictions about a private observation z i t+1 by knowing private occupancy state s i t , private decision a ¬i t , and private action u i t . This prediction can be made without knowing the private plan-time history y i t . Lemma 10. For each agent i, the private occupancy state at time step t, defined as s i

	. = t for predicting the t t }, is a sufficient statistic of the private plan-time history y i Pr{X t , O t |y i subsequent private occupancy state following the execution the private action u i t and the reception of the private observation z i t+1 , i.e., ρ i M ′ (y i t , u i t , z

  Lemma 12. Consider a joint policy a 0: and initial belief state s 0 . For every agent i and t-step private history o i t , let λ i,o i t .

	= Pr{o i t |y t = (s 0 , o i . t , a :t-1 )} be the private occupancy state given y i . = (s 0 , a :t-1 , w 1:t )} be the probability of o i t given t . For any t-step occupancy state s t y t and s i,o i t t . = Pr{X t , O t |y i t . = Pr{X t , O t |y t . = (s 0 , a :t-1 , w 1:t )} there exists (λ i,o i t , s i,o i t t ) o i t ∈O i

t such that s t can be expressed as a mixture of private occupancy states of any agent i, i.e.,

  Theorem 4. Let M be a master game. Let M ′′ (a ¬i 0: ) and M ′ (a ¬i 0: ) be slave games w.r.t. M and policy a ¬i 0: ∈ A ¬i 0: for agents ¬i. For any arbitrary time step t, the slave game M ′′ (a ¬i 0: ) has a piecewise linear and convex (PWLC) optimal state-value function of private occupancy states, i.e., υ i M ′′ (a ¬i t: ),γ,t : S i t → R. Consequently, at each time step t there exists a finite collection of linear functions of private occupancy states, denoted as V M ′′ (a ¬i t: ),γ,t , s.t.

	for any private occupancy state s i t , it follows:
	υ i M ′′ (a ¬i t: ),γ,t (s i t ) = max υ i,a t: M ′′ ,γ,t ∈V M ′′ (a ¬i t:	),γ,t	υ i,at: M ′′ ,γ,t (s i t ).

  Corollary 3. For any arbitrary time step t, the slave game M ′′ (a ¬i 0: ) has a piecewise linear and convex (PWLC) optimal state-value function of occupancy states expressed in the standard basis, i.e., υ i M ′′ (a ¬i t: ),γ,t : S B 0 t → R. Consequently, at each time step t there exists a finite collection of linear functions of occupancy states, denoted as V M ′′ (a ¬i t: ),γ,t , s.t. for any occupancy state s B 0

t , it follows:

  is linear over occupancy states expressed in B i and decision rules of agent i-i.e., for occupancy state s B i

	1 and λ i,o i t ≥ 0, and decision rule a i t ,	t	. = o i t ∈O i t	λ i,o i t •s i,o i t t	such that o i t ∈O i t	λ i,o i t =

  The proof starts with the definition of the immediate expected reward at occupancy state s B i

	Given that occupancy states are mixtures of private occupancy states, i.e.,
	s B i t =	λ i,o i t • s	i,o i t t	such that
	o i t ∈O i t
	t , and decision rule a i t ,
		r i M ′′ (s B i t , a i t )	. = E{r i Xt,Ut |s B i t , a t }.
	The expansion of the expectation over all private occupancy states, hidden states, and
	private actions gives the following expression
	r i M ′′ (s B i t , a i t ) =	λ i,o i t		s	i,o i t t (x t , o t )	a i t (u i t |o i ) • a ¬i t (u ¬i t |o ¬i t ) • r i xt,ut . (29)
	o i t ∈O i t	xt∈X o ¬i t ∈O ¬i t			ut∈U

  is linear over occupancy states expressed in B i and decision rules of agent i-i.e., for occupancy state s B i The proof starts with the definition of the next-step occupancy state s B i

	1 and λ i,o i t ≥ 0, and decision rule a i t ,	t	. = o i t ∈O i t	λ i,o i t • s	i,o i t t	such that o i t ∈O i t	λ i,o i t =
	ρ i M ′′ (s B i t , a i t ) =	λ i,o i t	a i t (u i t |o i t )		p i M ′′ (s	i,o i t t , u i t , s i,(o i t ,u i t ,z i t+1 ) t+1	) • s	i,(o i t ,u i t ,z i t+1 ) t+1	.
	o i t ∈O i t	u i t ∈U i	z i t+1 ∈Z i
	Proof. t+1 upon taking decision rule a i t in occupancy state s B i t , i.e.,	. = ρ i M ′′ (s B i t , a i t )
		s B i t+1 (s	i,(o i t ,u i t ,z i t+1 ) t+1

  The first factor in the decomposition of the joint probability is the dynamics model, i.e., p ut,z t+1 xt,x t+1 , the second denotes the probability of taking joint action given decision rules, i.e.,

	a i t (u i t |o i t ) • a ¬i t (u ¬i t |o ¬i t ), and the following factor is the value at private occupancy state s i,o i t t (x t , o t ), and the last factor is the value at occupancy state s B i t (s i,o i t t ), i.e.,
					
	= a i t (u i t |o i t ) • λ i,o i t	 		p ut,z t+1 xt,x t+1 • a ¬i t (u ¬i t |o ¬i t ) • s i,o i t t (x t , o t )	  .
		xt,x t+1 ∈X u ¬i t ∈U ¬i o ¬i t ∈O ¬i t z ¬i t+1 ∈Z ¬i
					(32)
	The injection of ω i M ′′ (z i t+1 |s	i,o i t t , u i t ), cf. Definition 23, into (32) yields
		= a i t (u i t |o i t ) • s B i t (s	i,o i t t ) • ω i M ′′ (z i t+1 |s i,o i t t , u i t ).
	If we group together all s the private history (o i t , u i t , z i i,(o i t ,u i t ,z i t+1 ) t+1 t+1 ), we have that: with the same private occupancy state s i t+1 regardless
	(31) =			Pr{x t+1 , z t+1 |x t , u t , o t , s B i t , a i t }
	xt,x t+1 ∈X u ¬i t ∈U ¬i o ¬i t ∈O ¬i t z ¬i t+1 ∈Z ¬i
	• Pr{u t |x t , o t , s B i t , a i t } • Pr{x t , o ¬i t |o i t , s B i t , a i t } • Pr{o i t |s B i t , a i t }.

  Theorem 6. Let M ′′ be a two-agent, zero-sum, simultaneous-move, occupancy Markov game w.r.t. M and M ′ , where occupancy states are expressed in the basis of an agent. The t-step optimal state-value function of any agent i, denoted as υ i, * M ′′ ,γ,t : S B ¬i is a convex function over occupancy states expressed in the basis of agent ¬i. For each agent i, at each time step t there exists a collection V i t of (possibly uncountable) vectors s.t. for any occupancy state s B ¬i Also, the tstep optimal state-value function of any agent i, denoted as υ i, * M ′′ ,γ,t : S B 0 are the maximum of concave (CConcave) functions over occupancy states expressed in the standard basis. For each agent i, at each time step t there exists a (possibly uncountable) collection The proof holds at any arbitrary time step t, any (maximizing) agent i, and any arbitrary occupancy state s B ¬i t , we start with the definition of the optimal value and then use Lemma 7 and Theorem 5, i.e.,

	1 and λ ¬i,o ¬i t ≥ 0,	t	. = o ¬i t ∈O ¬i t	λ ¬i,o ¬i t • s	¬i,o ¬i t t	such that o ¬i t ∈O ¬i t	λ ¬i,o ¬i t	=
			υ i, * M ′′ ,γ,t (s B ¬i t ) = max υ i M ′′ (a i t:	),γ,t	∈V i t	υ i M ′′ (a i t: ),γ,t (s B ¬i t ),
	where υ i M ′′ (a i t: ),γ,t	. = -υ ¬i M ′′ (a i
	V i t = {V i M ′′ (a i								t:	} of
	vectors s.t. for any occupancy state s B 0 t ,
	υ i, * M ′′ ,γ,t (s B 0 t ) = max V i M ′′ (a i t:	),γ,t	∈V i t	min υ i,a t: M ′′ ,γ,t ∈V i M ′′ (a i t:	),γ,t	υ i,at: M ′′ ,γ,t (s B 0 t ),
	where υ i,at: M ′′ ,γ,t	. = -υ ¬i,at: M υ i, * M ′′ ,γ,t (s B ¬i t )	. = max a i t: ∈A i t:	min a ¬i t: ∈A ¬i t:	E{υ i,at: M,γ,t (X

t → R, t: ),γ,t , with boundary condition υ •, * M ′′ ,γ,ℓ (•) = 0. t → R, t: ),γ,t |a i t: ∈ A i t: } of finite collections V i M ′′ (a i t:

),γ,t = {υ i,at: M ′′ ,γ,t |a ¬i t: ∈ A ¬i,pure ′′ ,γ,t , with boundary condition υ •, * M ′′ ,γ,ℓ (•) = 0. Proof. t , O t )|s B ¬i t }.

  ),γ,t is linear in occupancy states expressed in B ¬i but concave in occupancy states expressed in B 0 . If we let υ i

	It is worth noticing that υ ¬i M ′′ (a i t: M ′′ (a i t: ),γ,t follows that	. = -υ ¬i M ′′ (a i t: ),γ,t , then it
	υ i, * M ′′ ,γ,t (s B ¬i t ) = max a i t: ∈A i t:	υ i M ′′ (a i t: ),γ,t (s B ¬i t ).
	If we let V i t then we have that υ i, * . = {υ i M ′′ (a i t: ),γ,t |a i t: ∈ A i t: } be a (possibly uncountable) collection of vectors, M ′′ ,γ,t (s B ¬i t ) = max υ i M ′′ (a i ),γ,t ∈V i t υ i M ′′ (a i t ). If we let V i t . = t: ),γ,t (s B ¬i t: {V i M ′′ (a i t: ),γ,t |a i t: ∈ A i t: } and be a (possibly uncountable) collection of finite collections V i M ′′ (a i t: ),γ,t = {υ i,at: M ′′ ,γ,t |a ¬i t: ∈ A ¬i t: } of vectors, then we have that
	υ i, * M ′′ ,γ,t (s B 0 t ) =	max M ′′ (a i V i t: ),γ,t	∈V i t	min M ′′ (a i t: M ′′ ,γ,t ∈V i υ i,a t:	),γ,t	υ i,at: M ′′ ,γ,t (s B 0 t ),
	which ends the proof.

M ′′ (a i t: ),γ,t (s B ¬i t ).

Theorem 7. Let

  M ′′ be a two-agent, Stackelberg, simultaneous-move, occupancy Markov game w.r.t. M and M ′ , where occupancy states are expressed on the basis of the follower. The t-step optimal leader state-value function, denoted as υ 1, * M ′′ ,γ,t : S B 2 is a convex function over occupancy states expressed in basis set B 2 . Consequently, at each time step t there exists a collection V t of (possibly uncountable) vectors s.t. for any occupancy state

t → R,

  Theorem 8. Let M ′′ be a n-agent, common-reward, simultaneous-move, occupancy Markov game w.r.t. M ′ and M . The t-step optimal state-value function, denoted as υ * M ′′ ,γ,t : S B 0 t → R, is a piecewise linear and convex function over occupancy states expressed in the basis set B 0 . Consequently, at each time step t there exists a finite collection of vectors V t s.t. for any occupancy state s B 0 t , Proof. The proof holds for arbitrary time step t, arbitrary agent i, and arbitrary occupancy state s B 0 t . We start with the definition of the optimal value at s B 0 t , i.e., With all agents having the same reward model, one can show that restricting attention to pure policies does not hurt optimality because any pure policy that is a best-response policy achieves the same performance index.

	υ * M ′′ ,γ,t (s B 0 t ) = max υ a t: M ′′ ,γ,t ∈Vt t ) M ′′ ,γ,t (s B 0 . = max a i t: ∈A i t: max a ¬i t: ∈A ¬i υ at: M ′′ ,γ,t (s B 0 t ) t: E{υ at: M,γ,t (X t , O t )|s B 0 t }. The application of Lemma 1 into (43) results in the following expression: υ * M ′′ ,γ,t (s B 0 t ) = max a i t: ∈A i t: max a ¬i t: ∈A ¬i t: υ at: M ′′ ,γ,t (s B 0 t ). υ * M ′′ ,γ,t (s B 0 t ) = max at:∈A i,pure t: ⊗A ¬i,pure t: υ at: M ′′ ,γ,t (s B 0 t ). with boundary condition υ υ * Consequently, defining the finite collection V t . = {υ at: M ′′ ,γ,t |a t: ∈ A i,pure t: ⊗ A ¬i,pure t:	(42) (43)

* M ′′ ,γ,ℓ (•) . = 0.

  OursS B 0 PWLC (Th. 4) S B i Linear (Th. 5)S B 2 Convex (Th. 6) S B 0 CConcave S B 2 Convex (Th. 7) S B 0 PWLC (Th. 8)

				Master Games
		Slave Games	zs-POSG	st-POSG	dec-POMDP
	Dibangoye et al.	N.A.	N.A.	N.A.	S B 0 PWLC
	Wiggers et al.	P(O i ) Linear	P(O i ) Convex	N.A.	N.A.
	Delage et al.	N.A.	S B 0 Lipschitz	N.A.	N.A.

Acknowledgements

Jilles S. Dibangoye thanks God, who inspired this piece of work. This work was supported by ANR project Planning and Learning to Act in Systems of Multiple Agents under Grant ANR-19-CE23-0018, and ANR project Data and Prior, Machine Learning and Control under Grant ANR-19-CE23-0006, and ANR project Multi-Agent Trust Decision Process for the Internet of Things under Grant ANR-21-CE23-0016, all funded by French Agency ANR.

The function within the bracket represents the optimal value of the best-response at the initial occupancy state. It has been demonstrated that this function is a concave function of the initial occupancy states expressed in the standard basis. However, no more concise statistics can generally be found as the initial occupancy state is also the private occupancy state. Unfortunately, the point-wise maximum of concave functions is not convex. Therefore, the