Paper deep dive
The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting
Nazlı Nur Karabulut, Tanya Braun
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/20/2026, 4:03:29 AM
Summary
This paper addresses the exponential complexity of Decentralized Partially Observable Markov Decision Processes (DecPOMDPs) by introducing 'policy-counted' DecPOMDPs. While previous methods using agent symmetry and counting reduced model complexity, they suffered from an exploding policy space. The authors propose shifting the counting mechanism from agents to policies, allowing for a compact representation that maintains polynomial tractability with respect to the number of agents. They provide a formal definition, utility calculation analysis, and a dynamic programming operator to solve these policy-counted DecPOMDPs efficiently.
Entities (9)
Relation Signals (6)
Nazlı Nur Karabulut → affiliatedwith → University of Münster
confidence 99% · Affiliation: Computer Science Department, University of Münster
Tanya Braun → affiliatedwith → University of Münster
confidence 99% · Affiliation: Computer Science Department, University of Münster
DecPOMDP → suffersfrom → Exponential Complexity
confidence 96% · DecPOMDPs are known to suffer from exponential complexity in the number of agents.
The Curious Case of Exploding DecPOMDPs → publishedat → SUM2026
confidence 95% · paper accepted at the 17th International Conference on Scalable Uncertainty Management (SUM2026)
Policy-Counted DecPOMDP → solves → Policy Space Explosion
confidence 95% · redirect our focus from counting agents to counting policies, which actually enables tractability in agent numbers
Policy-Counted DecPOMDP → uses → Dynamic Programming
confidence 93% · present policy-counted dynamic programming using the compact representation to solve policy-counted DecPOMDPs efficiently
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Decentralised partially observable Markov decision processes (DecPOMDPs) provide a general framework for modelling multi-agent decision making under uncertainty. However, DecPOMDPs are known to suffer from exponential complexity in the number of agents. One way to combat this intractability in agent numbers is to look at partitions of agents that exhibit a form of symmetry among agents, allowing for a compact encoding by counting. However, a challenge arises as the policy space explodes, even though the model complexity and evaluation cost reduce to a polynomial dependence. In this paper, we redirect our focus from counting agents to counting policies, which actually enables tractability in agent numbers for so called policy-counted DecPOMDPs. Further, we present policy-counted dynamic programming using the compact representation to solve policy-counted DecPOMDPs efficiently.
Tags
Links
- Source: https://arxiv.org/abs/2608.17749v2
- Canonical: https://arxiv.org/abs/2608.17749v2
Trouble viewing inline? Open PDF directly →
Full Text
86,690 characters extracted from source content.
Expand or collapse full text
The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy CountingThanks: Full version including appendix of a paper accepted at the 17th International Conference on Scalable Uncertainty Management (SUM2026) under the same name. Affiliation: Computer Science Department, University of Münster, Münster, Germany E-mail nnur.karabulut,tanya.braun@uni-muenster.de Nazlı Nur Karabulut OrcID: 0000-0001-7958-5627 Affiliation: Computer Science Department, University of Münster, Münster, Germany E-mail nnur.karabulut,tanya.braun@uni-muenster.de Tanya Braun OrcID: 0000-0003-0282-4284 Abstract Decentralised partially observable Markov decision processes (DecPOMDPs) provide a general framework for modelling multi-agent decision making under uncertainty. However, DecPOMDPs are known to suffer from exponential complexity in the number of agents. One way to combat this intractability in agent numbers is to look at partitions of agents that exhibit a form of symmetry among agents, allowing for a compact encoding by counting. However, a challenge arises as the policy space explodes, even though the model complexity and evaluation cost reduce to a polynomial dependence. In this paper, we redirect our focus from counting agents to counting policies, which actually enables tractability in agent numbers for so called policy-counted DecPOMDPs. Further, we present policy-counted dynamic programming using the compact representation to solve policy-counted DecPOMDPs efficiently. 1 Introduction Large-scale agent systems involve a huge number of interacting agents that have to coordinate decisions in uncertain environments. To formalise the setting, decentralised partially observable Markov decision processes (DecPOMDPs) provide a framework to compute a joint policy for a set of cooperative agents that maximises some joint utility function in an environment that is considered to be stationary and describable by a probabilistic transition model. When agents are self-interested, the problem is formalised as a partially observable stochastic game (POSG), in which each agent has its own utility function. However, solving multi-agent decision making problems is notoriously difficult as the number of potential policies escalates exponentially with the number of agents. To deal with this problem, researchers have proposed various approaches: Early work focuses on dynamic programming using pruning techniques for POSGs [6]. Building on this basis, Szer et al. present point-based dynamic programming for DecPOMDPs [26] and Seuken et al. propose memory-bounded dynamic programming [25]. The dynamic programming operator was later extended with approximate pruning techniques to improve scalability for POSGs [14]. In addition to dynamic programming–based approaches, Szer et al. [27] propose multiagent A* (MAA*), a policy search algorithm that groups action–observation histories of agents at the same stage when they share the same optimal Q-values in a Bayesian game formulation of the problem [20]. Newer work optimises MAA* even further [12, 13]. Additional research has examined more structured subclasses to improve scalability, e.g., for POSGs, examples include zero-sum formulations [31, 7, 29], one-sided POSGs where only one agent is affected by uncertainty [9, 8, 4], and common-payoff POSGs that restrict agents to share identical rewards [5]. Another lane of work focuses on so-called lifting [21]. Lifting exploits symmetries between objects, also sometimes referred to as indistinguishability or exchangeability, which allows for tractable inference [18] and has been used to great extent in probabilistic inference (e.g., [16, 3, 28, 2]) and single-agent decision making (e.g., [23, 24, 15]). In multi-agent systems, lifting is applied to agents, allowing for a more compact problem formulation using partitions of agents. The basic assumption, first described by Braun et al. [1], is that, within a partition, permutations of joint actions and observations have the same effect on the joint transition or reward, allowing for counting actions and observations in histograms. Adding in an assumption about conditional independence among agents of a partition even allows for working with a single representative agent per partition without counting necessary, leading to a drastic reduction in complexity for so-called isomorphic DecPOMDPs. However, without that assumption, a reduction can only be made in model complexity and evaluation cost, while —almost counter-intuitively— the policy space explodes [1]. More recently, we have presented isomorphic POSGs and lifted dynamic programming to work with the compact encoding, yielding a runtime polynomial in the number of agents [10]. We have extended this work to counting policies to circumvent an explosion in the policy space for partitioned POSGs [11]. Invigorated by the progress made in counting POSGs, this work takes on the case of exploding DecPOMDPs under counting, a challenge left open by Braun et al. [1] by moving the counting focus to policies. Specifically, the contributions are threefold: (i) a new definition of counting DecPOMDPs that allows for counting policies, preventing the explosion in the policy space, (i) an updated utility calculation including an analysis that shows tractability in agent numbers, and (i) a dynamic programming operator to solve policy-counted DecPOMDPs. As such, we solve the above-mentioned challenge and additionally provide a dedicated solution method. When showing tractability, we assume a fixed number of partitions that is much smaller than the number of agents. The paper is organised as follows: We start with DecPOMDPs and dynamic programming. Then we analyse the problem of exploding DecPOMDPs and show how to use counting for policies to circumvent the problem, followed by counting dynamic programming. We end with a conclusion. 2 Preliminaries In this section, we define DecPOMDPs and provide an overview of dynamic programming for DecPOMDPs. 2.1 Decentralised POMDPs The definition is based on [19] and [22], using random variables S with ran(S)ran(S) referring to the set of (range) values it can take. Bold symbols denote sets, (time) steps t are denoted by superscript t, sequences over a discrete interval [ts:te][t_s:t_e] are denoted by superscript ts:tet_s:t_e, and omitting an element i from a set or sequence is denoted by subscript −i-i. To add an element to a sequence, we use ∘ . Definition 1 A (ground) DecPOMDP M is a tuple (,S,,T,R,,Ω,τ)( I, S, A, T, R, O, ,τ), • I a set of N agents, • S a random variable with a set of states as a range, • =Aii∈ A=\A_i\_i∈ I a set of decision random variables, each AiA_i with a set of local actions as range, • T(S′,S,)=P(S′∣S,)T(S ,S, A)=P(S S, A) a transition function, • R(S,)R(S, A) a reward function, • =Oii∈ O=\O_i\_i∈ I a set of random variables, each OiO_i with a set of local observations as range, • Ω(,S)=P(∣S) ( O,S)=P( O S) a sensor function11 1 For ease of exposition regarding counting and to be consistent with [1], we omit A from Ω , which does not make the problem inherently easier to solve [22]., and • τ a horizon. Each agent i follows a local policy πit _i^t mapping local observation histories o0:to^0:t to actions a, which can be represented as a depth-t policy tree (see Fig. 1). A joint policy is a tuple =(π1,…,πn) π=( _1,..., _n). The semantics of the ground model M is given by the joint policy space ΠM _M. The DecPOMDP problem asks for the joint policy that yields the maximum expected utility (with horizon τ): MEU(M)=(argmax∈ΠMUM(),max∈ΠMUM()) MEU(M)=( *arg\;max_ π∈ _MU_M( π), _ π∈ _MU_M( π)) (1) where UM()U_M( π) is calculated recursively over τ steps, by summing over joint observations and next states, and then weighted according to the prior T(s0,.,.)T(s^0,.\ ,.\ ), i.e., UM()=∑s0∈ran(S)T(s0,.,.)UM(s0,⊥0:0)U_M( π)= _s^0 (S)T(s^0,.\ ,.\ )U_M π(s^0, ^0:0) with UM(st,0:t)=R(st,(0:t))+∑st+1∈ran(S)T(st+1,st,(0:t))∑t+1∈ran()Ω(t+1,st+1)UM(st+1,0:t+1) splitU_M π(s^t, o^0:t)=R(s_t, π( o^0:t))+& _s^t+1 (S)T(s^t+1,s^t, π( o^0:t))\\ &\ \ \ _ o^t+1 ( O) ( o^t+1,s^t+1)U_M π(s^t+1, o^0:t+1) split (2) ending with UM(s,0:τ−1)=R(s,(o0:τ−1))U_M π(s, o^0:τ-1)=R(s, π(o^0:τ-1)), where (0:t) π( o^0:t) denotes the joint action at step t ((⊥) π( ): root actions) and 0:t+1=0:t∘t+1 o^0:t+1= o^0:t o^t+1 the updated history. In a DecPOMDP, all agents share a single joint reward function R(S,)R(S, A) and cooperate to maximize the total expected utility. However, each agent decides what to do next on its own, not being able to observe the full state or the other agents’ observations. Nonetheless, agents are not fully independent since they depend on a joint state and receive the reward jointly. aaaxyaabxyabaxyabbxybaaxybabxybbaxybbbxy Figure 1: Policies at level t=1t=1 available to agents with actions a,ba,b and observations x,yx,y 2.2 Dynamic Programming Dynamic programming is a solution method for multi-agent decision making that is shared between DecPOMDPs and POSGs [19]. It builds increasingly deeper policy trees from sub-trees for individual agents, while eliminating weakly-dominated policies at each depth [26]. Algorithm 1 shows the dynamic programming operator which consists of three steps. First, an exhaustive backup is performed to build all possible policies Πit=πi,jtj=1mt _i^t=\ _i,j^t\_j=1^m_t of depth t from the input policies Πit−1=πi,jt−1j=1mt−1 _i^t-1=\ _i,j^t-1\_j=1^m_t-1 for each agent i. Then, for each policy πi,jt∈Πit _i,j^t∈ _i^t, the operator calculates the corresponding value vector Vi,jtV_i,j^t, representing the value of that policy for each possible combination of state s∈ran(S)s (S) and policies of the other agents −it∈−it π_-i^t∈ _-i^t, which is defined as follows with =πi,jt∘−i π= _i,j^t π_-i Vi(s,)=R(s,(⊥))+∑s′∈ran(S)T(s′,s,(⊥))∑∈ran()Ω(,s)Vi(s′,.) splitV_i(s, π)=R(s, π( ))+ _s (S)T(s ,s, π( )) _ o ( O) ( o,s)V_i(s , π. o) split (3) where . π. o denotes the sub-policies after following an observation. During pruning, the operator eliminates policies that are weakly-dominated by others (solvable by a linear programme, see Section 0.A.1), meaning that over the complete space of ran(S)×−itran(S)× _-i^t there is always another policy with at least as high a value, i.e., ∀s∈ran(S),−it∈−it∃πi,j′t∈Πit:Vi(s,πi,jt∘−it)≤Vi(s,πi,j′t∘−it) split∀ s (S), π_-i^t∈ _-i^t∃π_i,j ^t∈ _i^t:V_i(s,π_i,j^t π_-i^t)≤ V_i(s,π_i,j ^t π_-i^t) split (4) Algorithm 1 Multi-agent Dynamic Programming Operator function MA-DP(set of policies Πit−1 _i^t-1 for each agent i∈i∈ I with value vectors it−1 V_i^t-1) for each agent i∈i∈ I do Πit← _i^t← Perform exhaustive backup using Πit−1 _i^t-1 it← V_i^t← Calculate new value vectors while ∃πi,jt∈Πit:∃ _i,j^t∈ _i^t: Eq. 4 holds for some i∈i∈ I do Πit←Πit∖πi,jt _i^t← _i^t \ _i,j^t\, it←it∖vi,jt V_i^t← V_i^t \v_i,j^t\ return (Πit,it)i∈\( _i^t, V_i^t)\_i∈ I 3 A Case of Exploding DecPOMDPs The basic idea of lifting DecPOMDPs is that the agent set is partitioned into sets of agents that behave indistinguishably among each other, meaning that it does not matter which agent performs which action within a partition, only how many do so [21, 16, 1]. In such a case, it is enough to count the agents and store the counts in a histogram. To illustrate the point, consider N=12N=12 indistinguishable agents with the actions a,ba,b available as an example. Imagine that 88 agents perform a while the remaining 44 perform b. Then, there exist (128)=12!8!⋅4!=495 128= 12!8!· 4!=495 ways to make the 1212 agents perform the actions, all of which result in the same outcome ρ. Therefore, we can construct a histogram [4,8][4,8] that maps to ρ, replacing 495495 mappings. While this leads to a drastic decrease in model complexity, the policy space explodes in the formalisation chosen in [1]. To understand why, we next discuss the assumptions and design choices, left at times implicit in the original paper. Then, we look at the (in)tractability results. 3.1 Assumptions & Definitions Braun et al. [1] name as their basic assumption indistinguishability among agents. They posit that indistinguishability requires agents to have the same local actions and observations, and that another consequence is that permutations of actions (observations) map to the same outcome in transition, reward, and sensor function, which we posit boils down to two assumptions, which we formalise next. The first assumption is that all agents i,ji,j in a partition ℑ⊆ I I have the same action and observation space: ran(Ai)=ran(Aj)∧ran(Oi)=ran(Oj)ran(A_i)=ran(A_j) (O_i)=ran(O_j) (5) which follows the requirement definition in [1]. The second assumption is that the transition, reward, and sensor functions T, R, and Ω are symmetric, meaning that exchanging actions or observations between agents of a partition has no effect on the outcome of T, R, and Ω , which can be formally expressed for the actions of two agents as: ∀∈ran(),=(ai∘aj∘−i,−j):∀ a ( A), a=(a_i a_j a_-i,-j): T(s′,s,ai∘aj∘−i,−j)=T(s′,s,aj∘ai∘−i,−j) splitT(s ,s,a_i a_j a_-i,-j)&=T(s ,s,a_j a_i a_-i,-j) split (7) The same holds for the actions in R and the observations in Ω . We now generalise Eq. 7 to entire partitions, to build interchangeability among agents within a partition. The set of agents I is divided into K partitions ℑ1,…,ℑK I_1,..., I_K of indistinguishable agents. For each partition ℑk I_k, let k=(ai)i∈ℑk a_k=(a_i)_i∈ I_k and k=(oi)i∈ℑk o_k=(o_i)_i∈ I_k denote the joint action and observation tuples of the agents in that partition. With the extension of symmetric behaviour to partitions, swapping the actions or observations of agents within the same partition does not change a function’s outcome. Formally, for any permutation θ of ℑk I_k, T(s′,s,k,−k)=T(s′,s,θ(k),−k)−k,s). splitT(s ,s, a_k, a_-k)&=T(s ,s,θ( a_k), a_-k) o_-k,s). split (8) with the same holding for any permutations of actions in T and observations in Ω . These assumptions are analogous to those made for counting in POSGs [11]. Equations 5 and 8 allow for encoding actions and observations using histograms, which can then be used to compactly encode T, R, and Ω by replacing the individual mappings from all θ(k)θ( a_k) to an outcome ρ with a single mapping h↦ρh ρ, with h being a histogram of the counts of actions in k a_k, which is identical for all θ(k)θ( a_k). The same holds for the permutations of observations in k o_k. Formally, histograms are defined as follows: Definition 2 Given a set of n agents I and a set of m values ν=v1,…,vmν=\v_1,…,v_m\, a histogram h is defined as h=(vl,nl)l=1mh=\(v_l,n_l)\_l=1^m with ∑l=1mnl=n _l=1^mn_l=n where each nln_l denotes the number of instances with value vlv_l. We use h(vl)h(v_l) to refer to nln_l. [n1,…,nm][n_1,...,n_m] is used as a shorthand. A counting random variable (CRV) #[V]\#_ I[V] is a syntactic construct whose range consists of all histograms over the range values of variable V, i.e., ν=ran(V)ν=ran(V), that meet ∑lnl=|| _ln_l=| I|. Considering the shorthand example h=[4,8]h=[4,8] from above for actions a,ba,b and n=12n=12, the full version reads h=(a,8),(b,4)h=\(a,8),(b,4)\. Braun et al. [1] then define a partitioned DecPOMDP that uses such histograms as range values for actions and observations in each partition for every affected component of the DecPOMDP. Definition 3 ([1]) A counting DecPOMDP M¯c M_c is a tuple (¯,S¯,¯c,T¯,R¯,¯c,Ω¯,τ)( I, S, A_c, T, R, O_c, ,τ), with • ¯ I a partitioning ℑkk=1K\ I_k\_k=1^K of N agents, with nk=|ℑk|n_k=| I_k| and |¯|=∑knk=N| I|= _kn_k=N, • S a random variable with a set of states as range, • ¯c=#ℑk[Ak]k=1K A_c=\\#_ I_k[A_k]\_k=1^K a set of decision CRVs, • T¯(S′,S,¯c) T(S ,S, A_c) a transition function with counted actions, • R¯(S,¯c) R(S, A_c) a reward function with counted actions, • ¯c=#ℑk[Ok]k=1K O_c=\\#_ I_k[O_k]\_k=1^K a set of CRVs, • Ω¯(¯c,S) ( O_c,S) a sensor function with counted observations, and • τ a horizon. The equivalence between a DecPOMDP fulfilling Eqs. 5 and 8 and a counting DecPOMDP can be shown by construction, replacing all mappings with permutations of inputs with a single mapping with a histogram and vice versa (see App. 0.B.1). 3.2 (In)Tractability Results For a ground DecPOMDP, the model complexity lies in O(s2aN)O(s^2a^N) for T, O(saN)O(sa^N) for R, and O(soN)O(so^N) for Ω with s=|ran(S)|s=|ran(S)|, a=maxi∈|ran(Ai)|a= _i∈ I|ran(A_i)|, and o=maxi∈|ran(Oi)|o= _i∈ I|ran(O_i)|, while the cost of evaluating a joint policy lies in O(soNτ)O(so^Nτ) and the policy space size in O(aN(oτ−1)o−1)O(a N(o^τ-1)o-1) [19]. Using CRVs allows for reducing the model size and evaluation cost from exponential to polynomial. Theorem 3.1 ([1], Thm. 2) A counting DecPOMDP M¯c M_c allows for representation [i.e., model] and cost to depend polynomially on N. The theorem holds by the range sizes of the CRVs, which are capped by NaN^a, a=maxk|ran(Ak)|a= _k|ran(A_k)|, and NoN^o, o=maxk|ran(Ok)|o= _k|ran(O_k)|, as an upper bound on the number of histograms given by the binomial coefficient (N+v−1v−1)≤Nv N+v-1v-1≤ N^v, v∈a,ov∈\a,o\ [16]. Compared to the ground case, a and o are replaced by NaN^a and NoN^o, while K replaces N in the exponent, yielding a polynomial dependence on N, assuming that K≪NK N. However, the number of policies explodes: Since the size of the policy space contains o in the exponent, replacing o with NoN^o means that N remains in the exponent, all the while a is replaced with NaN^a, leading to an expression that has N in the base as well as the exponent. Corollary 1 The policy space of a counting DecPOMDP M¯c M_c depends exponentially on N. The crux is the choice of CRVs in the action and observation set used for building policies. In contrast, we use plain variables and count policies instead, which is a small change with profound effects. 4 Containing the Fire by Counting Policies For a polynomial dependence on the agent numbers, we keep plain variables in the action and observation sets, enabled by Eq. 5, but use CRVs in the transition, reward, and sensor function, enabled by Eq. 8. With plain variables, there is a set of (representative) policies available in each partition, which allows for structuring the policy space by counting the number of agents following each representative policy and updating the MEUMEU calculations. We first formalise counted policies before renewing the definition of counting DecPOMDPs. Last, we look at the effect of counted policies on the MEUMEU calculation and complexity. 4.1 Counted Policies Let us consider the example from the beginning of Section 3 with 1212 agents and actions a,ba,b available. At step t=1t=1, assuming two possible observations x,yx,y, each of the 1212 agents has the same 88 policies available, see Fig. 1. Instead of tracking all possible policies for each individual agent, we can use these 88 policies as representative policies to keep track of agent behaviour in histograms: For example, the partition policy in which all agents follow the first policy is encoded by [12,0,0,0,0,0,0,0][12,0,0,0,0,0,0,0], while the other configuration in which one agent follows the second policy and the remaining agents follow the first one is encoded by [11,1,0,0,0,0,0,0][11,1,0,0,0,0,0,0]. In this way, all possible partition policies can be compactly encoded. More formally, according to Eq. 5, the set of policies for any two agents i,ji,j within a partition ℑk I_k is established using the same sets of actions Ai=Aj=AkA_i=A_j=A_k and observations Oi=Oj=OkO_i=O_j=O_k. As a result, their local policy space is the same, i.e., Πi=Πj=Πk _i= _j= _k. These policies are referred to as representative policies Πk _k of partition ℑk I_k and can be counted for each partition. Definition 4 Let the set of J representative policies of a partition ℑk I_k be given by Πk=π1,…,πJ _k=\ _1,…, _J\. A counted partition policy over Πk _k is a histogram hkΠ=(πj,mj)j=1Jh _k=\( _j,m_j)\_j=1^J, where mj≥0m_j≥ 0 is the number of agents in ℑk I_k following policy πj _j, and ∑j=1Jmj=nk _j=1^Jm_j=n_k. The counted policy space for partition ℑk I_k, denoted by HkΠH _k, is given by the set of all histograms meeting ∑j=1Jmj=nk _j=1^Jm_j=n_k. The joint counted policy space over all partitions is given by Π=×k=1KHΠk H =×_k=1^KH _k. The counted policy space of all partitions except k is denoted by −kΠ H _-k and of all agents except some agent i∈ℑki∈ I_k by −iΠ H _-i where ∑j=1Jmj=nk−1 _j=1^Jm_j=n_k-1 for HkΠH _k without i. 4.2 A Renewed Definition To distinguish the two definitions, we use policy-counted DecPOMDP as a name here, which is still a DecPOMDP with a partitioned agent set fulfilling Eqs. 5 and 8. Definition 5 A policy-counted DecPOMDP M¯ M is a tuple (¯,S¯,¯,T¯,R¯,¯,¯,τ)( I, S, A, T, R, O, ,τ), with • ¯ I a partitioning ℑkk=1K\ I_k\_k=1^K of N agents, nk=|ℑk|n_k=| I_k| and |¯|=∑knk=N| I|= _kn_k=N, • S a random variable with a set of states as range, • ¯=Akk=1K A=\A_k\_k=1^K a set of decision random variables, • T¯(S′,S,¯c) T(S ,S, A_c) a transition function with counted actions, • R¯(S,¯c) R(S, A_c) a reward function with counted actions, • ¯=Okk=1K O=\O_k\_k=1^K a set of random variables, • Ω¯(¯c,S) ( O_c,S) a sensor function with counted observations, and • τ a horizon. where ¯c=#ℑk[Ak]k=1K A_c=\\#_ I_k[A_k]\_k=1^K and ¯c=#ℑk[Ok]k=1K O_c=\\#_ I_k[O_k]\_k=1^K. The difference between Definition 3 and Definition 5 only lies in ¯c A_c and ¯c O_c versus ¯ A and ¯ O, which are CRVs in the former and plain variables in the latter case, as the set of actions and observations available. Since Eq. 8 holds in both definitions, T¯ T, R¯ R, and Ω¯ are the same with CRVs as inputs for actions and observations. This encoding captures the symmetric behaviour of agents within each partition and helps to reduce the model complexity by operating over counted representations instead of enumerating all individual agents. Theorem 4.1 establishes the equivalence between the ground DecPOMDP and its counted version of Definition 5. Theorem 4.1 A ground DecPOMDP M that meets Eqs. 5 and 8 is equivalent to a policy-counted DecPOMDP M¯ M. The full proof can be found in Section 0.B.2, which is based on the fact that one can be converted into the other by construction and vice versa. Having established the equivalence between ground and counting DecPOMDPs, we now show how the counting formulation affects the model complexity. Theorem 4.2 For a fixed number of partitions K, fixed action and observation spaces, and a fixed horizon τ, the model complexity of a counting DecPOMDP M¯c M_c is polynomial in the number of agents N. The full proof can be found in Section 0.B.3, where we show that using histograms within agent partitions keeps the model size polynomial in N. 4.3 Counted Utility Calculation As the policy space is given by joint counted policies, we can update the semantics and MEUMEU calculation. The semantics of the policy-counted DecPOMDP M¯ M is given by the joint counted policy space Π H . The policy-counted DecPOMDP problem asks for the joint counted policy that yields the maximum expected utility (with horizon τ), which is again computed by recursively calculating the expected utility over the next states and observations, until reaching τ. However, the sum over observations can now be turned into a sum over counted observations: Given a joint counted policy, each partition is partitioned again into groups following a representative policy according to the counted partition policy, with group sizes corresponding to the histogram counts. For a given (representative) observation history, the recursive call to the next utility as well as the remaining sub-policy are the same for these agents, making them indistinguishable among themselves. As such, for each of these groups, we can count observations in histograms over the (sub)group with a particular representative policy and observation history, and let the sum go over the cross product of these histograms. Conditioning these groups on their shared observation history means that groups split up further, which can in the worst case lead to singletons if the group size is small to begin with or τ is very large but the overall complexity is still going to be only polynomial as we show afterwards. Additionally, we only need this deep recursion for the utility definition here and are able to define policy-counted dynamic programming using a single step. To formalise this setting, we define the space of representative observation histories as well as the space of observation histograms given a representative observation history. Definition 6 Given a step t, a representative observation history pk0:t,op_k^0:t,o of a partition ℑk I_k is a sequence of observations ot′∈ran(Ok)o^t (O_k) of length t, t′∈1,…,tt ∈\1,…,t\, with o0=⊥o^0= as an empty observation. Given a representative observation history pk0:t,op_k^0:t,o, let pkt′,op_k^t ,o refer to the entry at point t′t in the sequence and pk0:t−1,op_k^0:t-1,o refer to the subsequence without the last entry pkt,op_k^t,o. Finally, let P0:t,okP^0:t,o_k denote the space of representative observation histories of length t for the agents in partition ℑk I_k, i.e., Pk0:t,o=⊥×t′=1tran(Ok)P^0:t,o_k= ×_t =1^tran(O_k). Definition 7 Given a step t, a counted partition policy hkΠh_k , and a representative policy π∈Πkπ∈ _k for a partition ℑk I_k, a counted partition observation is a set of histograms hk,p0:t,oko,πp0:t,ok∈P0:t,ok\h_k,p^0:t,o_k^o,π\_p^0:t,o_k∈ P^0:t,o_k where hk,p0:t,oko,π h_k,p^0:t,o_k^o,π =(ol,nl)ol∈ran(Ok) =\(o_l,n_l)\_o_l (O_k) with ∑ol∈ran(Ok)nl _o_l (O_k)n_l =hk,p0:t−1,oko,π(pkt)if t>0hkΠ(π)if t=0 = casesh_k,p^0:t-1,o_k^o,π(p_k^t)&if $t>0$\\ h_k (π)&if $t=0$ cases (9) and p0:t,ok=p0:t−1,ok∘pktp^0:t,o_k=p^0:t-1,o_k p_k^t. Let Hko,πH_k^o,π denote the space of counted partition observations for a given representative policy π, i.e., the set of all possible sets of histograms that fulfil Definition 7. Given a joint counted policy Π h , let Hko,ΠH_k^o, denote the space of counted partition observations over all representative policies Πk _k, i.e., Hko,Π=×π∈ΠkHko,πH_k^o, =×_π∈ _kH_k^o,π, and o,Π H^o, the space of joint counted observations, i.e., o,Π=×k=1KHko,Π H^o, =×_k=1^KH_k^o, . Note that the observation histogram in Definition 7 holds counts nln_l for p0:t,o∘olp^0:t,o o_l. Based on these definitions, we can now rewrite Eq. 1 as follows: MEU(M¯)=(argmaxΠ∈ΠUM¯(Π),maxΠ∈ΠUM¯(Π)) MEU( M)=( *arg\;max_ h ∈ H U_ M( h ), _ h ∈ H U_ M( h )) (10) where UM¯(Π)U_ M( h ) is calculated recursively over τ steps and weighted according to the prior T(s0,.,.)T(s^0,.\ ,.\ ), i.e., UM¯(Π)=∑s0∈ran(S)T(s0,.,.)UM¯Π(s0,⊥0:0)U_ M( h )= _s^0 (S)T(s_0,.\ ,.\ )U_ M h (s^0, ^0:0) with UM¯Π(st,(o,Π)0:t)=R(st,a)+∑st+1∈ran(S)T(st+1,st,a)∑o,Π∈o,ΠMul(o,Π)⋅Ω(o,st+1)UM¯Π(st+1,(o,Π)0:t∘o,Π) split&U_ M h (s^t,( h^o, )^0:t)=R(s^t, h^a)+ _s^t+1 (S)T(s^t+1,s^t, h^a)\\ &\ \ \ _ h^o, ∈ H^o, Mul( h^o, )· ( h^o,s^t+1)U_ M h (s^t+1,( h^o, )^0:t h^o, ) split (11) with Mul(o,Π)Mul( h^o, ) the multinomial coefficient, denoting the number of ground permutations encoded by the histograms [28], where for each partition ℑk I_k, the counted partition action hka∈ah^a_k∈ h^a as input to R and T is given by adding up, for each action a∈ran(Ak)a (A_k), how often a is carried out over all representative policies and all representative observation histories using the counts in the latest counted partition observation if the observation history plus the newest observation map to a in the current representative policy, i.e., hka=(al,nl)al∈ran(Ak)withnl=∑π∈Πk∑p∈P0:t−1,ok∑o∈ran(Ok)ho,Π,tk,p(o)πk(p∘o)=alif t>0∑π∈ΠkhkΠ(π)|π(⊥)=alif t=0 splith^a_k&=\(a_l,n_l)\_a_l (A_k) \\ n_l&= cases _ subarraycπ∈\\ _k subarray _ subarraycp∈\\ P^0:t-1,o_k subarray _ subarrayco∈\\ ran(O_k) subarrayh^o, ,t_k,p(o) 1_ _k(p o)=a_l&if $t>0$\\ _π∈ _kh_k (π) π( )=a_l&if $t=0$ cases split (12) with hk,po,Π,t∈ko,Π,t∈(ko,Π)o:th^o, ,t_k,p∈ h_k^o, ,t∈( h_k^o, )^o:t and 1 being the indicator function returning 11 if πk(p∘o)=al _k(p o)=a_l. The counted observation hko∈ran(#ℑk[Ok])h_k^o (\#_ I_k[O_k]) as input to Ω is given by adding up, for each observation o∈ran(Ok)o (O_k), how often o is observed over all representative policies and all representative observation histories in the latest counted partition observation, i.e., hok=(ol,nl)ol∈ran(Ok)withnl=∑π∈Πk∑p∈P0:t−1,okho,Π,tk,p(ol) splith^o_k=\(o_l,n_l)\_o_l (O_k) n_l= _π∈ _k _p∈ P^0:t-1,o_kh^o, ,t_k,p(o_l) split (13) The utility calculation for a ground DecPOMDP and an equivalent policy-counted DecPOMDP is equivalent again, leading to the same maximum expected utility. The trick is that calculations that lead to the same result are only performed once in the counted case, which is possible due to the histograms essentially encoding when calculations lead to the same result. Theorem 4.3 The maximum expected utility for a ground DecPOMDP M that meets Eqs. 5 and 8 is equal to the maximum expected utility of the corresponding policy-counted DecPOMDP M¯ M. That is, MEU(M)=MEU(M¯)MEU(M)=MEU( M). The full proof can be found in Section 0.B.4, where we show that both models give the same utility by mapping ground policies to counted policies. Next, we look at evaluation cost and policy space size. Theorem 4.4 For a fixed number of partitions K, fixed representative action and observation spaces, and a fixed horizon τ, the cost of evaluating a joint counted policy and the size of the overall joint counted policy space in a policy-counted DecPOMDP depend polynomially on the number of agents N. The full proof can be found in Section 0.B.5, which relies on the joint counted observation space and the joint counted policy space depending polynomially on the number of agents N, as nk≤Nn_k≤ N agents are distributed onto the different representative observations and policies, which can be characterised using the binomial coefficient. Thus, we have reduced the complexity from an exponential one to a polynomial one for N. As such, a policy-counted DecPOMDP is tractable in the number of agents. Corollary 2 Given a fixed number of partitions K, fixed representative action and observation spaces, and a fixed horizon τ, a policy-counted DecPOMDP is tractable in the number of agents N. With the number of agents N no longer appearing in the exponent, we are able to solve larger problem instances in terms of N compared to the ground case, especially if the number of partitions K is small. Next, we use the counting encoding to speed up dynamic programming for DecPOMDPs. 5 Policy-Counted Dynamic Programming In this section, we extend the standard dynamic programming operator for policy-counted DecPOMDPs. Because of the equivalence between the ground and policy-counted versions of DecPOMDPs, we can show that the value computations are equivalent, allowing for computing values at a partition level as well as pruning representative policies. The policy-counted dynamic programming operator still follows the three general steps of exhaustive backup, value computation, and pruning but on a partition-level. That is, Algorithm 1 still applies but computes value vectors and performs pruning according to counted versions of those equations for each partition (see Eqs. 14 and 15). During the exhaustive backup, the operator builds all representative policies of depth t based on the policies of depth t−1t-1 for each partition and then computes their corresponding value vectors. Since the operator builds increasingly deeper policies, the value computation stays at the top level, building its counted joint action from the root actions in the representative policies, i.e., with t=0t=0 in Eq. 12 to build a h^a, and uses empty representative histories, i.e., Definition 7 with t=0t=0 as well to build o,Π H^o, . Thus, for a state s and joint counted policy −iΠ h_-i of the other agents and partitions, the value computation for a given representative policy πk _k is defined as follows with πk⊕−iΠ _k h_-i adding 11 to the corresponding count in hkΠh_k of −iΠ h_-i to form a full joint counted policy: V¯k(s,Π)=R(s,a)+∑s′∈ran(S)T(s′,s,a)∑o,Π∈o,ΠMul(o,Π)⋅Ω(o,s′)V¯k(s′,Π.o,Π) split V_k(s, h )=R(s, h^a)+& _s (S)T(s ,s, h^a)\\ &\ \ \ _ h^o, ∈ H^o, Mul( h^o, )· ( h^o,s ) V_k(s , h . h^o, ) split (14) where .o,Π h. h^o, denotes the policy histogram that follows from the observation histogram o,Π h^o, . Specifically, given depth t of the representative policies Πkt _k^t used for Π h , the joint counted policy Π h , and the current joint counted observation o,Π h^o, , the new policy histogram is calculated by adding up how often a subpolicy πl∈Πkt−1 _l∈ _k^t-1 remains over the different representative policies π∈Πktπ∈ _k^t when following the different observations o∈ran(Ok)o (O_k) given the counts in hko,Π∈o,Πh_k^o, ∈ h^o, for o, i.e., .o,Π=(πl,nl)πl∈Πkt−1withnl=∑π∈Πkt∑o∈ran(Ok)hko,Π(o)|π.o=πl split h. h^o, =\( _l,n_l)\_ _l∈ _k^t-1 n_l= _π∈ _k^t _o (O_k)h^o, _k(o) π.o= _l split During pruning, the operator eliminates weakly dominated representative policies πk _k based on the following equation (solvable by a linear programme, see Section 0.A.2): foralls∈ran(S),−it∈−it∃πl≠kt∈Πkt:V¯k(s,πkt⊕−it)≤V¯k(s,πlt⊕−it) splitforalls (S), h_-i^t∈ H_-i^t∃π_l≠ k^t∈ _k^t: V_k(s,π_k^t h_-i^t)≤ V_k(s,π_l^t h_-i^t) split (15) Equation 15 ensures that, for each state and each counted policy of the other partitions, a representative policy is only pruned if there exists another one with equal or higher value. Next, we show that counted dynamic programming using Eqs. 14 and 15 is equivalent to dynamic programming using Eqs. 3 and 4, which is a culmination of the formalisations and theorems so far. Theorem 5.1 Using policy-counted dynamic programming on a policy-counted DecPOMDP M¯ M is equivalent to using standard dynamic programming on a ground DecPOMDP M, in which Eqs. 5 and 8 hold. The full proof can be found in App. 0.B.6, where we show that each step of the dynamic programming operator works equivalently in both the ground and counted models. Given the equivalence of the policy-counted and standard version of dynamic programming, correctness of the policy-counted version follows directly from the correctness of the standard version. Corollary 3 Policy-counted dynamic programming using Eqs. 14 and 15 is correct. Next, we show that policy-counted dynamic programming depends polynomially on the number of agents assuming a fixed and small number of representative actions and observations and partitions as well as horizon. Theorem 5.2 For a fixed number of partitions K, fixed representative action and observation spaces, and a fixed horizon τ, the runtime of policy-counted dynamic programming in a policy-counted DecPOMDP M¯ M depends polynomially on the number of agents N. The full proof can be found in App. 0.B.7, which analyzes the polynomial runtime of the backup, value calculation, and pruning steps. Appendix 0.C shows the well-known DecTiger model [17] as ground, counting, and policy-counted DecPOMDPs to highlight the similarities and differences between the models. In summary, policy-counted dynamic programming is able to use the compact encoding of policy-counted DecPOMDPs to generate a solution that is equivalent to the ground solution in time polynomial in N instead of exponential in N, assuming all other parameters to be fixed. As the DecTiger example shows, the pay-off only arises if N is sufficiently large, i.e., if the assumption of N≪KN K indeed holds. Otherwise the counting of policies introduces too much overhead. Future work is left to deal with the remaining exponent that can still become rather large. 6 Conclusion This paper presents policy-counted DecPOMDPs, which exploit a partitioned agent set under certain structural assumptions to reduce the complexity from exponential to polynomial in the number of agents, assuming all other parameters to be fixed. Specifically, we are able to use representative policies per partition, enabling counting how many agents follow which policy, which allows for a compact representation and considerably reduces the model’s size, computing cost, and policy space, leading to tractability in agent numbers assuming a fixed number of partitions, horizon, and representative action and observation spaces. Additionally, we present a policy-counted dynamic programming for policy-counted DecPOMDPs that updates policies and values as well as prunes policies directly at the partition level. As a consequence, policy-counted DecPOMDPs offer a lot of potential for large-scale applications such as nanoscale medical systems. In future research, we aim to further enhance scalability by working on policy encodings as well as applying lifting to large state spaces, to enable additional complexity reductions. Another idea is to look at approximations, considering that histograms are rarely needed in count steps of 11. References [1] Braun, T., Gehrke, M., Lau, F., Möller, R.: Lifting in Multi-agent Systems under Uncertainty. In: UAI-22 Proc. of the 38th Conference on Uncertainty in Artificial Intelligence. p. 1–8. AUAI Press (2022) [2] Braun, T., Möller, R.: Lifted Junction Tree Algorithm. In: Proc. of KI 2016: Advances in Artificial Intelligence. p. 30–42. Springer (2016) [3] Van den Broeck, G., Taghipour, N., Meert, W., Davis, J., De Raedt, L.: Lifted Probabilistic Inference by First-order Knowledge Compilation. In: IJCAI-11 Proc. of the 22nd International Joint Conference on Artificial Intelligence. p. 2178–2185. IJCAI Organization (2011) [4] Carr, S., Jansen, N., Bharadwaj1, S., Spaan, M.T.J., Topcu, U.: Safe policies for factored partially observable stochastic games. In: RSS-21 Proc. of Robotics: Science and Systems XVII. p. 1–11. RSS Foundation (2021) [5] Emery-Montemerlo, R., Gordon, G., Schneider, J., Thrun, S.: Approximate solutions for partially observable stochastic games with common payoffs. In: AAAMAS-04 Proc. of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. p. 136–143. IEEE (2004) [6] Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI-04 Proc. of the 19th National Conference on Artificial Intelligence. vol. 4, p. 709–715 (2004) [7] Horák, K., Bošanskỳ, B.: Solving partially observable stochastic games with public observations. In: Proc. of the AAAI conference on Artificial Intelligence. p. 547–552. AAAI Press (2019) [8] Horák, K., Bošanskỳ, B., Kiekintveld, C., Kamhoua, C.: Compact Representation of Value Function in Partially Observable Stochastic Games. In: IJCAI-19 Proc. of the 28th International Joint Conference on Artificial Intelligence. p. 350–356. IJCAI Organisation (2019) [9] Horák, K., Bošanskỳ, B., Pěchouček, M.: Heuristic Search Value Iteration for One-sided Partially Observable Stochastic Games. In: AAAI-17 Proc. of the 31st AAAI Conference on Artificial Intelligence. p. 558–564 (2017) [10] Karabulut, N.N., Braun, T.: Lifting partially observable stochastic games. In: International Conference on Scalable Uncertainty Management. p. 201–216. Springer (2024) [11] Karabulut, N.N., Braun, T.: Counting agents in partially observable stochastic games. In: European Conference on Symbolic and Quantitative Approaches with Uncertainty. p. 207–222. Springer (2025) [12] Koops, W., Jansen, N., Junges, S., Simao, T.D.: Recursive Small-step Multi-agent A* for Dec-POMDPs. In: IJCAI-23 Proceedings of the 32nd International Joint Conference on Artificial Intelligence. p. 5402–5410. IJCAI Organization (2023) [13] Koops, W., Junges, S., Jansen, N.: Approximate Dec-POMDP Solving Using Multi-agent A*. In: IJCAI-24 Proceedings of the 33nd International Joint Conference on Artificial Intelligence. p. 6743–6751. IJCAI Organization (2024) [14] Kumar, A., Zilberstein, S.: Dynamic programming approximations for partially observable stochastic games. In: FLAIRS-09 Proc. of the 22nd International Florida Artificial Intelligence Research Society Conference. AAAI Press (2009) [15] Marwitz, F., Braun, T., Möller, R., Gehrke, M.: Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions. In: AAMAS-26 Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (2026), https://arxiv.org/pdf/2505.22147v2 [16] Milch, B., Zettelmoyer, L.S., Kersting, K., Haimes, M., Kaelbling, L.P.: Lifted Probabilistic Inference with Counting Formulas. In: AAAI-08 Proc. of the 23rd AAAI Conference on Artificial Intelligence. p. 1062–1068. AAAI Press (2008) [17] Nair, R., Tambe, M., Yokoo, M., Pynadath, D.V., Marsella, S.: Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings. In: IJCAI-03 Proc. of the 18th International Joint Conference on Artificial Intelligence. p. 705–711. IJCAI Organization (2003) [18] Niepert, M., Van den Broeck, G.: Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference. In: AAAI-14 Proc. of the 28th AAAI Conference on Artificial Intelligence. p. 2467–2475. AAAI Press (2014) [19] Oliehoek, F.A., Amato, C.: A Concise Introduction to Decentralised POMDPs. Springer (2016) [20] Oliehoek, F.A., Whiteson, S., Spaan, M.T.: Lossless Clustering of Histories in Decentralized POMDPs. In: AAMAS-09 Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems. p. 577–584. IFAAMAS (2009) [21] Poole, D.: First-order Probabilistic Inference. In: IJCAI-03 Proc. of the 18th International Joint Conference on Artificial Intelligence. p. 985–991. IJCAI Organization (2003) [22] Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach. Pearson (2021) [23] Sanner, S., Boutilier, C.: Practical Solution Techniques for First-order MDPs. Artificial Intelligence Journal 173, 748–788 (2009) [24] Sanner, S., Kersting, K.: Symbolic Dynamic Programming for First-order POMDPs. In: AAAI-10 Proc. of the 24th AAAI Conference on Artificial Intelligence. p. 1140–1146. AAAI Press (2010) [25] Seuken, S., Zilberstein, S.: Memory-Bounded Dynamic Programming for DEC-POMDPs. In: IJCAI-07 Proceedings of the 21st International Joint Conference on Artificial Intelligence. p. 2009–2015. IJCAI Organization (2007) [26] Szer, D., Charpillet, F.: Point-based dynamic programming for dec-pomdps. In: AAAI. vol. 6, p. 1233–1238 (2006) [27] Szer, D., Charpillet, F., Zilberstein, S.: MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs. In: UAI-05 Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence. p. 576–583. ACM (2005) [28] Taghipour, N., Fierens, D., Davis, J., Blockeel, H.: Lifted Variable Elimination: Decoupling the Operators from the Constraint Language. Journal of Artificial Intelligence Research 47(1), 393–439 (2013) [29] Tomášek, P., Horák, K., Aradhye, A., Bošanskỳ, B., Chatterjee, K.: Solving partially observable stochastic shortest-path games. In: IJCAI-21 Proc. of the 30th International Joint Conference on Artificial Intelligence. p. 4182–4189. IJCAI Organisation (2021) [30] Vaidya, P.M.: Speeding-up Linear Programming Using Fast Matrix Multiplication. In: 30th Annual Symposium on Foundations of Computer Science. p. 332–337. IEEE Computer Society (1989) [31] Wiggers, A.J., Oliehoek, F.A., Roijers, D.M.: Structure in the value function of two-player zero-sum games of incomplete information. In: ECAI-16 Proc. of the 22nd European Conference on Artificial Intelligence. p. 1628–1629. IOS Press (2016) The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting (Supplementary Material) Appendix 0.A Linear Programmes This section provides the linear programmes used during the pruning step in dynamic programming, which repeats the pruning condition from the main paper and then lists the linear programme. 0.A.1 Ground DecPOMDP Formally, a policy πi,jt _i,j^t is pruned if the following holds, ∀s∈ran(S),−it∈−it∃πi,j′t∈Πit:Vi′(s,πi,jt∘−it)≤Vi′(s,πi,j′t∘−it) split∀ s (S), π_-i^t∈ _-i^t∃π_i,j ^t∈ _i^t:V_i (s,π_i,j^t π_-i^t)≤ V _i(s,π_i,j ^t π_-i^t) split which can be solved by solving the following linear programme (prune πi,jt _i,j^t if d<0d<0): variables: bi(s,−i),d b_i(s, π_-i),d maximise: d d constraints: ∀πi,j′t∈Πit ∀π_i,j ^t∈ _i^t ∑s∈ran(S)∑−i∈−itbi(s,−i)Vi(s,πi,jt,−it) \ \ _s (S) _ π_-i∈ _-i^tb_i(s, π_-i)V_i(s,π_i,j^t, π_-i^t) −∑s∈ran(S)∑−i∈Π−itbi(s,−i)Vi(s,πi,j′t,−it)−d≤0 \ \ \ \ - _s (S) _ π_-i∈ _-i^tb_i(s, π_-i)V_i(s,π_i,j ^t, π_-i^t)-d≤ 0 ∑s∈ran(S)∑−i∈Π−itbi(s,−i)=1,bi(s,−i)>0 _s (S) _ π_-i∈ _-i^tb_i(s, π_-i)=1,b_i(s, π_-i)>0 0.A.2 Policy-Counted DecPOMDP Formally, a representative policy πkt _k^t is pruned if the following holds, which can still be solved using a linear program: ∀s∈ran(S),−it∈−it∃πl≠kt∈Πkt:V¯k′(s,πkt⊕−it)≤V¯′k(s,πlt⊕−it), split∀ s (S), h_-i^t∈ H_-i^t∃π_l≠ k^t∈ _k^t: V_k (s,π_k^t h_-i^t)≤ V _k(s,π_l^t h_-i^t), split which can be solved by solving the following linear programme (prune πk,lt _k,l^t if d<0d<0): variables: bk(s,−i),d b_k(s, h_-i),d maximise: d d constraints: ∀πk,l′t∈Πkt ∀π_k,l ^t∈ _k^t ∑s∈ran(S)∑−i∈−itbk(s,−i)Vk(s,πk,lt⊕−it) \ \ _s (S) _ h_-i∈ H_-i^tb_k(s, h_-i)V_k(s,π_k,l^t h_-i^t) −∑s∈ran(S)∑−i∈−bk(s,−i)Vk(s,πk,l′t⊕−it)−d≤0 \ \ \ \ - _s (S) _ h_-i∈ H_-i^tb_k(s, h_-i)V_k(s,π_k,l ^t h_-i^t)-d≤ 0 ∑s∈ran(S)∑−i∈−bk(s,−i)=1,bk(s,−i)>0 _s (S) _ h_-i∈ H_-i^tb_k(s, h_-i)=1,b_k(s, h_-i)>0 Appendix 0.B Full Proofs 0.B.1 Equivalence between a Ground DecPOMDP and a Counting DecPOMDP This theorem shows equivalence between a ground DecPOMDP and a counting DecPOMDP based on Eqs. 5 and 8. Theorem 0.B.1 A ground DecPOMDP M that meets Eqs. 5 and 8 is equivalent to a counting DecPOMDP M¯c M_c. Proof To convert a DecPOMDP M=(,S,,,T,R,Ω,τ)M=( I,S, A, O,T,R, ,τ) into a counting DecPOMDP M¯c=(¯,S,¯c,¯c,T¯,R¯,Ω¯,τ) M_c=( I,S, A_c, O_c, T, R, ,τ), we apply Eqs. 5 and 8. First, agents within the same partition share the same action and observation spaces, meaning that for any i,j∈ℑki,j∈ I_k, Ai=AjA_i=A_j and Oi=OjO_i=O_j, which is provided by Eq. 5. For each partition ℑk I_k, we introduce the CRVs #ℑk[Ak]\#_ I_k[A_k] and #ℑk[Ok]\#_ I_k[O_k] for actions and observations, whose ranges are all histograms over the local action space ran(Ak)ran(A_k) and observation space ran(Ok)ran(O_k). To build the transition, sensor, and reward functions, based on Eq. 8, we replace (Ai)i∈ℑk(A_i)_i∈ I_k and (Oi)i∈ℑk(O_i)_i∈ I_k with CRVs #ℑk[Ak]\#_ I_k[A_k] and #ℑk[Ok]\#_ I_k[O_k] in the inputs of the transition, reward, and sensor function for each partition, with a histogram hkh_k mapping to ρ for all permutations of a partition input k a_k or k o_k mapping to ρ for which h is the histogram representation. To convert a counting DecPOMDP into a ground DecPOMDP fulfilling Eqs. 5 and 8, we essentially reverse the steps above: The agent set I is the union of the partitions ⋃k=1Kℑk _k=1^K I_k. The action and observation sets are given by Ak,ii∈ℑk\A_k,i\_i∈ I_k and Ok,ii∈ℑk\O_k,i\_i∈ I_k, fulfilling Eq. 5. In the transition, reward, and sensor function, the CRV inputs are replaced by the action and observation sets, with a histogram h mapping to ρ being replaced by a set of mappings over all permutations of the values that agents can take according to the counts in h, all mapping to ρ, thereby leading to the functions fulfilling Eq. 8. 0.B.2 Full Proof for Theorem 2 We repeat Theorem 4.1 and then provide its proof. Theorem 0.B.2 A ground DecPOMDP M that meets Eqs. 5 and 8 is equivalent to a counting DecPOMDP M¯ M. Proof First, we convert a DecPOMDP M=(,S,,,T,R,,τ)M=( I, S, A, O, T, R, ,τ), in which Eqs. 5 and 8 hold, into a counting DecPOMDP M¯=(¯,¯,¯,¯,T¯,R¯,,τ) M=( I, S, A, O, T, R, ,τ). Agents that share the same action and observation spaces, meaning Ai=AjA_i=A_j and Oi=OjO_i=O_j for i,j∈i,j∈ I by Eq. 5, as well as exhibit symmetric behaviour as in Eq. 7 are grouped into a partition, storing for each partition a decision variable Ak=Ai=AjA_k=A_i=A_j and an observation variable Ok=Oi=OjO_k=O_i=O_j. To construct the counted functions T¯ T, R¯ R, and Ω¯ based on Eq. 8, we replace (Ai)i∈ℑk(A_i)_i∈ I_k with a CRV #ℑk[Ak]\#_ I_k[A_k] in the inputs of the transition, reward, and sensor function for each partition. We do the same with the observation variables in the sensor function. For each function and each partition, we then construct from a mapping with a partition action k a_k (partition observation k o_k) mapping to an outcome ρ a new mapping with a histogram hkh_k replacing k a_k (k o_k), counting how often each a∈ran(Ak)a (A_k) (o∈ran(Ok)o (O_k)) occurs in k a_k (k o_k) for the counts in hkh_k, and discard all mappings with permutations of k a_k (k o_k). Second, we convert a counting DecPOMDP into a DecPOMDP M that meets Eqs. 5 and 8 by setting =⋃kℑk I= _k I_k, Ai=AkA_i=A_k and Oi=OkO_i=O_k for all i∈ℑki∈ I_k in each partition ℑk I_k, making M fulfil Eq. 5, and then essentially expanding the counted functions into their ground versions, i.e., replacing each CRV #ℑk[Vk]\#_ I_k[V_k], V∈A,OV∈\A,O\, with a set of variables Vk,1,…,Vk,nkV_k,1,…,V_k,n_k as inputs and mapping the different inputs v to an outcome ρ, whenever the histogram representation of v maps to ρ, which makes M meet Eq. 8. 0.B.3 Full Proof of Theorem 3 We repeat Theorem 4.2 and then provide its proof. Theorem 0.B.3 For a fixed number of partitions K, fixed action and observation spaces, and a fixed horizon τ, the model complexity of a counting DecPOMDP M¯c M_c is polynomial in N. Proof The histogram space of a CRV for partition ℑk,k∈1,…,K I_k,k∈\1,…,K\ of size nkn_k with m possible values has size (nk+m−1m−1)≤nkm n_k+m-1m-1≤ n_k^m [16]. As we assume K is fixed and K≪NK N, nkn_k and N have the same order of magnitude, i.e., nk≤Nn_k≤ N. As such, due to the range sizes of their inputs, the sizes of the functions T¯ T, R¯ R and Ω¯ lie in O(s2NKa)O(s^2N^Ka), O(sNKa)O(sN^Ka), and O(sNKo)O(sN^Ko), respectively, with s=|ran(S¯)|s=|ran( S)|, a=maxk|ran(Ak)|a= _k|ran(A_k)|, and o=maxk|ran(Ok)|o= _k|ran(O_k)|, depending polynomially on N. 0.B.4 Full Proof of Theorem 4 We repeat Theorem 4.3 and then provide its proof. Theorem 0.B.4 The maximum expected utility for a ground DecPOMDP M that meets Eqs. 5 and 8 is equal to the maximum expected utility of the corresponding policy-counted DecPOMDP M¯ M. That is, MEU(M)=MEU(M¯)MEU(M)=MEU( M). Proof Let ΠM _M be set of possible joint policies in the ground model M. In the policy-counted model M¯ M, we convert any ground joint policy =(π1,…,πN) π=( _1,..., _N) into a joint counted policy of histograms Π=(h1,…,hK) h =(h_1,...,h_K), where each hkh_k counts the number of agents in partition ℑk I_k assigned to each representative policy in Πk _k. To establish value equivalence, consider any ground policy π and its corresponding policy histogram Π h and an empty joint (counted observation) at the start. Based on Theorem 4.1, the reward, transition, and observation functions return the same values between the two models given equivalent inputs. As a result, the immediate rewards in Eqs. 2 and 11 are identical, i.e., R(s,)=R¯(s,a)R(s, a)= R(s, h^a), with the joint action in Eq. 2 and the joint counted action in Eq. 11 being equivalent, since the same policies are followed between the ground and the policy-counted version and thus, the actions in the roots are identical, adding up to the counts in the counted joint action. The following sum over states is identical in both equations with the transition functions returning the same values. The sum over joint (counted) observations is equivalent, since every ground joint observation can be translated into a joint counted observation, with the counted version combining those ground joint observations with the same counted representation into one summand and multiplying that summand with the number of instances using the multinomial coefficient [28]. The summand value is identical, since the sensor functions return the same value for equivalent inputs. As such, the calculations at the end of the first step are equivalent. Subsequent utility calculations have as the observation history an equivalent input as just argued. Thus, with the same arguments as before, the further joint (counted) actions are equivalent, with the action histogram being a counted representation of the ground joint action, which also holds for further joint (counted) observations. Therefore, the expected utilities UM()U_M( π) and UM¯(Π)U_ M( h ) are identical. As this can be done for every ground policy with its corresponding policy histogram, the counted policy space Π H and the ground policy space ΠM _M yield the same maximum expected utility, that is MEU(M)=MEU(M¯)MEU(M)=MEU( M). 0.B.5 Full Proof of Theorem 5 We repeat Theorem 4.4 and then provide its proof. Theorem 0.B.5 For a fixed number of partitions K, fixed action and observation spaces, and a fixed horizon τ, the cost of evaluating a joint counted policy and the size of the overall joint counted policy space in a policy-counted DecPOMDP depend polynomially on the number of agents N. Proof For the cost of evaluating a joint counted policy, consider Eq. 11 with a sum over states, which is of size s=|ran(S)|s=|ran(S)|, and a sum over joint counted observations. With a=maxk|ran(Ak)|,o=maxk|ran(Ok)|a= _k|ran(A_k)|,o= _k|ran(O_k)|, the space of joint counted observations is structured for each partition by the number of representative policies p and the number of representative observation histories h, which are given by [19] p p =|Πk|=aoτ−1o−1 =| _k|=a o^τ-1o-1 h h =|Pk0:τ,o|=oτ =|P_k^0:τ,o|=o^τ Each representative history can have up to nk≤Nn_k≤ N agents following that particular history with K≪NK N, which are distributed onto o possible observations. Thus, the number of histograms per partition is given by H=(N+o−1o−1)≤No H= N+o-1o-1≤ N^o Therefore, the size of the joint counted observation space is given by the size of the cross product of K partitions, p representative policies, and h representative histories, i.e., HKphH^Kph, which is capped by HKph≤(No)Kaoτoτ=NKao2τ+1 H^Kph≤(N^o)^Ka^o^τo^τ=N^Kao^2τ+1 and as such, depends polynomially on N. The size of the joint counting policy space is capped by ∏k=1K(nk+p−1p−1)≤NKp=NKaoτ−1o−1 _k=1^K n_k+p-1p-1≤ N^Kp=N^Ka o^τ-1o-1 and thereby, also depends polynomially on N. 0.B.6 Full Proof of Theorem 6 We repeat Theorem 5.1 and then provide its proof. Theorem 0.B.6 Using policy-counted dynamic programming on a policy-counted DecPOMDP M¯ M is equivalent to using standard dynamic programming on a ground DecPOMDP M, in which Eqs. 5 and 8 hold. Proof We show equivalence by considering the different steps of the dynamic programming operator. Exhaustive backup: Given Eq. 5, the policies for each agent in a partition ℑk I_k are identical, meaning that the exhaustive backup can be performed using representative policies for each partition. Value computation: Given that MEU(M¯)=MEU(M)MEU( M)=MEU(M) by Theorem 4.3 and as such UM¯Π=UMU h _ M=U π_M for equivalent policies Π h and π, V¯k′=Vi′ V _k=V _i for all i∈ℑki∈ I_k as the value computation is a rewriting of the utility computation, meaning that the value calculations can be performed for counted partition policies at each partition. Pruning: Since V¯k′=Vi′ V _k=V _i for all i∈ℑki∈ I_k, Eq. 4 for pruning is identical for all i∈ℑki∈ I_k given a representative policy πk∈Πk _k∈ _k, meaning that πk _k can be checked for pruning once per partition and thus, pruning can be performed for representative policies per partition. Given the equivalence of the three steps, we can conclude that the overall procedure yields an equivalent result. 0.B.7 Full Proof of Theorem 7 We repeat Theorem 5.2 and then provide its proof. Theorem 0.B.7 For a fixed number of partitions K, fixed action and observation spaces, and a fixed horizon τ, the runtime of policy-counted dynamic programming in a policy-counted DecPOMDP M¯ M depends polynomially on the number of agents N. Proof Again, we consider the three steps of the dynamic programming operator to show polynomial dependence on the number of agents N, which reuses definitions of Theorem 4.2. Exhaustive backup: With a=maxk|ran(Ak)|,o=maxk|ran(Ok)|a= _k|ran(A_k)|,o= _k|ran(O_k)|, the number of policies to generate per partition is given by p=aoτ−1o−1p=a o^τ-1o-1 [19], meaning KpKp over all partitions, which is independent of N. Value calculation: Eq. 14 depends polynomially on N since the sum over joint counted observations depends polynomially on N. In contrast to the recursive calculation of UM¯ΠU h _ M, we do not need to consider representative observation histories for t>0t>0, meaning that the size of the space of histograms is capped by (No)Kp=NKoa(oτ−1)o−1(N^o)^Kp=N Koa(o^τ-1)o-1, which is polynomial in N. Pruning: Solving the pruning part can be done using a linear programme, which can be solved in time polynomial w.r.t. the number of variables and constraints [30], whose numbers again depends polynomially on N, since the number of variables and constraints depends on the counted policy space Π H , which depends polynomially on N. Given that each step depends polynomially on N, the overall runtime depends polynomially on N. Appendix 0.C DecTiger Example We provide the different model definitions, look at model and worst-case policy space sizes, and consider the differences when applying the dynamic programming operator. 0.C.1 Model Definition We use the specification of the DecTiger benchmark from the MADP tool box. 22 2 https://github.com/MADPToolbox/MADP/blob/master/problems/dectiger.dpomdp. Listing 1 shows the original DecTiger version in the MADP input format. The DecPOMDP model reads as follows: • =agent1,agent2 I=\agent_1,agent_2\, • S, ran(S)=ran(S)=\tiger-left, tiger-right=tl,tr\=\tl,tr\, • =Aii∈ A=\A_i\_i∈ I, ∀i∈:ran(Ai)=∀ i∈ I:ran(A_i)=\listen, open-left, open-right=li,ol,or\=\li,ol,or\, and • =Oii∈ O=\O_i\_i∈ I, ∀i∈:ran(Oi)=∀ i∈ I:ran(O_i)=\hear-left, hear-right=hl,hr\=\hl,hr\. with T, R, and Ω (= O in Listing 1) in tabular notation in full below (lines are reordered compared to the listing to match the order of the inputs in the definitions). S A1A_1 A2A_2 TtlT_tl TtrT_tr tltl lili lili 11 00 tltl lili olol 0.50.5 0.50.5 tltl lili oror 0.50.5 0.50.5 tltl olol lili 0.50.5 0.50.5 tltl olol olol 0.50.5 0.50.5 tltl olol oror 0.50.5 0.50.5 tltl oror lili 0.50.5 0.50.5 tltl oror olol 0.50.5 0.50.5 tltl oror oror 0.50.5 0.50.5 trtr lili lili 00 11 trtr lili olol 0.50.5 0.50.5 trtr lili oror 0.50.5 0.50.5 trtr olol lili 0.50.5 0.50.5 trtr olol olol 0.50.5 0.50.5 trtr olol oror 0.50.5 0.50.5 trtr oror lili 0.50.5 0.50.5 trtr oror olol 0.50.5 0.50.5 trtr oror oror 0.50.5 0.50.5 S A1A_1 A2A_2 R tltl lili lili −2-2 tltl lili olol −101-101 tltl lili oror 99 tltl olol lili −101-101 tltl olol olol −50-50 tltl olol oror −100-100 tltl oror lili 99 tltl oror olol −100-100 tltl oror oror 2020 trtr lili lili −2-2 trtr lili olol 99 trtr lili oror −101-101 trtr olol lili 99 trtr olol olol 2020 trtr olol oror −100-100 trtr oror lili −101-101 trtr oror olol −100-100 trtr oror oror −50-50 S A1A_1 A2A_2 Ωhl,hl _hl,hl Ωhr,hl _hr,hl Ωhl,hr _hl,hr Ωhr,hr _hr,hr tltl lili lili 0.72250.7225 0.12750.1275 0.12750.1275 0.02250.0225 tltl lili olol 0.250.25 0.250.25 0.250.25 0.250.25 tltl lili oror 0.250.25 0.250.25 0.250.25 0.250.25 tltl olol lili 0.250.25 0.250.25 0.250.25 0.250.25 tltl olol olol 0.250.25 0.250.25 0.250.25 0.250.25 tltl olol oror 0.250.25 0.250.25 0.250.25 0.250.25 tltl oror lili 0.250.25 0.250.25 0.250.25 0.250.25 tltl oror olol 0.250.25 0.250.25 0.250.25 0.250.25 tltl oror oror 0.250.25 0.250.25 0.250.25 0.250.25 trtr lili lili 0.72250.7225 0.12750.1275 0.12750.1275 0.02250.0225 trtr lili olol 0.250.25 0.250.25 0.250.25 0.250.25 trtr lili oror 0.250.25 0.250.25 0.250.25 0.250.25 trtr olol lili 0.250.25 0.250.25 0.250.25 0.250.25 trtr olol olol 0.250.25 0.250.25 0.250.25 0.250.25 trtr olol oror 0.250.25 0.250.25 0.250.25 0.250.25 trtr oror lili 0.250.25 0.250.25 0.250.25 0.250.25 trtr oror olol 0.250.25 0.250.25 0.250.25 0.250.25 trtr oror oror 0.250.25 0.250.25 0.250.25 0.250.25 with Ts′=T(s′,s,a1,a2),s′∈tl,trT_s =T(s ,s,a_1,a_2),s ∈\tl,tr\ and Ωo1,o2=Ω((o1,o2),s,a1,a2) _o_1,o_2= ((o_1,o_2),s,a_1,a_2), o1,o2∈hl,hro_1,o_2∈\hl,hr\. The transition function only states that as long as both agents only listen, the state does not change (identity). When at least one agent opens a door, the game basically restarts with the new state being set according to a uniform distribution. It is basically a way of keeping the game infinite by resetting the state to an arbitrary one whenever the agents end the game by opening a door (to either lose—tiger, or win—gold). One could argue that opening a door only ends the game and might not necessarily imply a restart. In that case, one would keeping the state as is in all cases ((1,0)(1,0) distribution for all tltl lines, (0,1)(0,1) distribution for all trtr lines) and re-spawn the game with an arbitrary starting state, sampled from a (0.5,0.5)(0.5,0.5) distribution, for do-overs. The DecTiger model has the same action and observation sets for both agents and exhibits a counting symmetry. Thus, it can be rewritten into a counting model (Definition 3) with K=1K=1. We index the one partition with c. • ¯=ℑc=agent1,agent2 I= I_c=\agent_1,agent_2\, • S=tl,trS=\tl,tr\, • A¯c=#ℑc[Ac] A_c=\\#_ I_c[A_c]\, where the local action range is ran(Ac)=ran(Ai)=li,ol,orran(A_c)=ran(A_i)=\li,ol,or\, AiA_i from the ground DecPOMDP definition, • T¯(S′,S,A¯c)=P(S′∣S,A¯c) T(S ,S, A_c)=P(S S, A_c), • R¯(S,A¯c) R(S, A_c), • O¯c=#ℑk[Ok] O_c=\\#_ I_k[O_k]\, where the local observation range is ran(O)=hl,hrran(O)=\hl,hr\. • Ω¯(O¯c,S)=P(O¯c∣S) ( O_c,S)=P( O_c S) with T¯ T, R¯ R, and Ω¯ following after the specification of the policy-counted DecPOOMDP version. In a policy-counted DecPOMDP (Definition 5), the action and observation variables are plain variables again. The CRVs only occur within the transition, reward, and sensor functions. Specifically, for the policy-counted DecTiger example, the model is defined as follows: • ¯=ℑc=agent1,agent2 I= I_c=\agent_1,agent_2\, • S=tl,trS=\tl,tr\, • A¯=Ac A=\A_c\, ran(Ac)=ran(Ai)=li,ol,orran(A_c)=ran(A_i)=\li,ol,or\, • T¯(S′,S,A¯c)=P(S′∣S,A¯c) T(S ,S, A_c)=P(S S, A_c), • R¯(S,A¯c) R(S, A_c), • O¯=Okk=1K O=\O_k\_k=1^K, ran(Oc)=hl,hrran(O_c)=\hl,hr\. • Ω¯(O¯c,S)=P(O¯c∣S) ( O_c,S)=P( O_c S) with A¯c A_c and O¯c O_c defined as for the counting DecPOMDP above. The functions T¯ T, R¯ R, and Ω¯ are given below in tabular notation with #A\#A short for #ℑk[Ak]\#_ I_k[A_k] (histogram positions: [li,ol,or][li,ol,or]) and Ω¯h _h for Ω(S,#A,#ℑk[Ok]=h) (S,\#A,\#_ I_k[O_k]=h): S #A\#A T¯tl T_tl T¯tr T_tr tltl [2,0,0][2,0,0] 1.01.0 0.00.0 tltl [1,1,0][1,1,0] 0.50.5 0.50.5 tltl [1,0,1][1,0,1] 0.50.5 0.50.5 tltl [0,1,1][0,1,1] 0.50.5 0.50.5 tltl [0,2,0][0,2,0] 0.50.5 0.50.5 tltl [0,0,2][0,0,2] 0.50.5 0.50.5 trtr [2,0,0][2,0,0] 0.00.0 1.01.0 trtr [1,1,0][1,1,0] 0.50.5 0.50.5 trtr [1,0,1][1,0,1] 0.50.5 0.50.5 trtr [0,1,1][0,1,1] 0.50.5 0.50.5 trtr [0,2,0][0,2,0] 0.50.5 0.50.5 trtr [0,0,2][0,0,2] 0.50.5 0.50.5 S #A\#A R¯ R tltl [2,0,0][2,0,0] −2-2 tltl [1,1,0][1,1,0] −101-101 tltl [0,2,0][0,2,0] −50-50 tltl [0,1,1][0,1,1] −100-100 tltl [0,0,2][0,0,2] 2020 tltl [1,0,1][1,0,1] 99 trtr [2,0,0][2,0,0] −2-2 trtr [1,1,0][1,1,0] 99 trtr [0,2,0][0,2,0] 2020 trtr [0,1,1][0,1,1] −100-100 trtr [0,0,2][0,0,2] −50-50 trtr [1,0,1][1,0,1] −101-101 S #A\#A Ω¯[2,0] _[2,0] Ω¯[1,1] _[1,1] Ω¯[0,2] _[0,2] tltl [2,0,0][2,0,0] 0.72250.7225 0.12750.1275 0.02250.0225 tltl [1,1,0][1,1,0] 0.250.25 0.250.25 0.250.25 tltl [0,2,0][0,2,0] 0.250.25 0.250.25 0.250.25 tltl [0,1,1][0,1,1] 0.250.25 0.250.25 0.250.25 tltl [0,0,2][0,0,2] 0.250.25 0.250.25 0.250.25 tltl [1,0,1][1,0,1] 0.250.25 0.250.25 0.250.25 trtr [2,0,0][2,0,0] 0.72250.7225 0.12750.1275 0.02250.0225 trtr [1,1,0][1,1,0] 0.250.25 0.250.25 0.250.25 trtr [1,0,1][1,0,1] 0.250.25 0.250.25 0.250.25 trtr [0,2,0][0,2,0] 0.250.25 0.250.25 0.250.25 trtr [0,1,1][0,1,1] 0.250.25 0.250.25 0.250.25 trtr [0,0,2][0,0,2] 0.250.25 0.250.25 0.250.25 Note that the rows to not add up to one because the histogram [1,1][1,1] in Ω¯ stands for two joint observations, (hl,hr)(hl,hr) and (hr,hl)(hr,hl), meaning that the probability for Ω¯[1,1] _[1,1] has to be counted twice for the probability distribution to add up to 11. In general, a multinomial coefficient provides the number of inputs represented by a histogram, i.e., nk!/∏lnl!n_k!/ _ln_l!. Before moving on to model and policy space sizes, we list the DecTiger specification in the MADP toolbox. Listing 1 DecTiger specification in the MADP toolbox (without the comments from the source) ⬇ agents: 2 discount: 1 values: reward states: tiger-left tiger-right start: uniform actions: listen open-left open-right listen open-left open-right observations: hear-left hear-right hear-left hear-right # Transition probabilities T: * : uniform T: listen listen : identity # Observation probabilities: <2 actions> : <state> : <2 observations> : probability O: * : uniform O: listen listen : tiger-left : hear-left hear-left : 0.7225 O: listen listen : tiger-left : hear-left hear-right : 0.1275 O: listen listen : tiger-left : hear-right hear-left : 0.1275 O: listen listen : tiger-left : hear-right hear-right : 0.0225 O: listen listen : tiger-right : hear-left hear-left : 0.7225 O: listen listen : tiger-right : hear-left hear-right : 0.1275 O: listen listen : tiger-right : hear-right hear-left : 0.1275 O: listen listen : tiger-right : hear-right hear-right : 0.0225 # Rewards: <2 actions> : <state> : * : * : reward R: listen listen: * : * : * : -2 R: open-left open-left : tiger-left : * : * : -50 R: open-right open-right : tiger-right : * : * : -50 R: open-left open-left : tiger-right : * : * : 20 R: open-right open-right : tiger-left : * : * : 20 R: open-left open-right : tiger-left : * : * : -100 R: open-left open-right : tiger-right : * : * : -100 R: open-right open-left : tiger-left : * : * : -100 R: open-right open-left : tiger-right : * : * : -100 R: open-left listen : tiger-left : * : * : -101 R: listen open-right : tiger-right : * : * : -101 R: listen open-left : tiger-left : * : * : -101 R: open-right listen : tiger-right : * : * : -101 R: listen open-right : tiger-left : * : * : 9 R: listen open-left : tiger-right : * : * : 9 R: open-right listen : tiger-left : * : * : 9 R: open-left listen : tiger-right : * : * : 9 0.C.2 Model and Policy Space Sizes The following table characterises the ground, counting, and policy-counted model M, M¯c M_c, M¯ M regarding different parameters: • Number of agents: N, number of partitions: K, horizon τ • State size: s • Size of a local / partition action: a, that is |ran(Ai)||ran(A_i)|, |ran(#ℑ[Ac])||ran(\#_ I[A_c])|, |ran(Ac)||ran(A_c)|, respectively • Size of the joint (counted) action: a • Size of a local / partition observation: o, that is |ran(Oi)||ran(O_i)|, |ran(#ℑ[Oc])||ran(\#_ I[O_c])|, |ran(Oc)||ran(O_c)|, respectively • Size of the joint (counted) action: o • Size of local / partition policy space per state: p, i.e., local policy π over Ai,OiA_i,O_i, partition policy over OPENOPEN#ℑ[Ac]),#ℑ[Oc])\#_ I[A_c]),\#_ I[O_c]), counted policy over representative policies over Ak,OkA_k,O_k • Size of the joint (counted) policy space per state: p • Size of the transition, reward, and sensor functions by range sizes of the inputs: T, R, Ω M M¯c M_c M¯ M s 22 22 22 a 33 (N+3−13−1)=(N+22) N+3-13-1= N+22 33 a 3N3^N (N+22)K N+22^K (N+22)K N+22^K o 22 (N+2−12−1)=(N+11) N+2-12-1= N+11 22 o 2N2^N (N+11)K N+11^K (N+11)K N+11^K p 32τ−12−13 2^τ-12-1 (N+22)(N+11)τ−1(N+11)−1 N+22 N+11^τ-1 N+11-1 (N+32τ2−1−132τ2−1−1) pmatrixN+3 2^τ2-1-1\\ 3 2^τ2-1-1 pmatrix p 3N2τ−12−13^N 2^τ-12-1 (N+22)K(N+11)τ−1(N+11)−1 N+22^K N+11^τ-1 N+11-1 (N+32τ2−1−132τ2−1−1)K pmatrixN+3 2^τ2-1-1\\ 3 2^τ2-1-1 pmatrix^K T 2⋅2⋅3N2· 2· 3^N 2⋅2⋅(N+22)K2· 2· N+22^K 2⋅2⋅(N+22)K2· 2· N+22^K R 2⋅3N2· 3^N 2⋅(N+22)K2· N+22^K 2⋅(N+22)K2· N+22^K Ω 2⋅2N2· 2^N 2⋅(N+11)K2· N+11^K 2⋅(N+11)K2· N+11^K 0.C.3 Dynamic Programming We consider the three steps of dynamic programming (backup, value calculation, pruning) for the levels t=0t=0 and t=1t=1 for the three versions of the DecTiger example. Level t=0t=0 Backup: The operator for the ground version builds three policies for each of its two agents, each policy having a single (root) node for one of the actions li,ol,orli,ol,or, building six policies overall. A counting programming operator for the counting version would build six policies for its one partition, each with a single (root) node for one of the action histograms [2,0,0],[1,1,0],[1,0,1],[0,1,1],[0,2,0],[0,0,2][2,0,0], [1,1,0], [1,0,1], [0,1,1], [0,2,0], [0,0,2]. The counted programming operator for the policy-counted version builds three representative policies for its one partition, each with a single (root) node for one of the actions li,ol,orli,ol,or. With two available agents, there are six counted policies over the three representative ones: [2,0,0],[1,1,0],[1,0,1],[0,1,1],[0,2,0],[0,0,2][2,0,0], [1,1,0], [1,0,1], [0,1,1], [0,2,0], [0,0,2]. Value Computation: For the ground version, the operator calculates the values for each of its two agents for each of its three policies. For each policy, the computation has to be performed for each state tl,trtl,tr and each of the other agent’s three policies. For the counting version, the operator calculates the values for its one partition for each of its six policies. For each policy, the computation has to be performed for each state tl,trtl,tr. For the policy-counted version, the operator calculates the values for its one partition for each of its six counted policies. For each policy, the computation has to be performed for each state tl,trtl,tr. Pruning: In the ground version, the operator checks for each of the two agents, whether one of its three policies is (weakly) dominated by one of the other two policies for each state tl,trtl,tr and each of the three policies of the other agent (does not need to be the same policy over all states and policies of the other agent), until there are no more policies to prune. In the counting version, the operator would check for its one partition, whether any of its six policies is (weakly) dominated by one of the other five policies for each state tl,trtl,tr, until there are no more policies to prune. In the policy-counted version, the operator checks for its one partition, whether any of its three representative policies is dominated by one of the other two policies for each state tl,trtl,tr and each of the other counted policies over the remaining partition, which contains only one agent, i.e., [1,0,0],[0,1,0],[0,0,1][1,0,0], [0,1,0], [0,0,1] (that is just the three representative policies), until there are no more policies to prune. Comment: The difference between the counting and policy-counted versions is not as pronounced at this level, with the ground version also working within the same order of magnitude. Level t=1t=1 Backup: With no policies pruned, the operator for the ground version builds for its two agent each 2727 policies out of its previous three policies and two possible observations hl,hrhl,hr, with each policy having a root node and two children, one for each observation. The actions in the nodes are each possible combination of li,ol,orli,ol,or. With no policies pruned, the operator for the counting version would build for its one partition 216216 policies out of its previous six policies and three possible counted observations [0,2],[1,1],[2,0][0,2],[1,1],[2,0]. The policies would have a root node and three children, one for each possible histogram, with the nodes containing each possible combination of the six action histograms. The operator for the policy-counted version builds the same 2727 (representative) policies out of its previous three representative policies and two possible observations hl,hrhl,hr that the ground version has. With two available agents, there are then 378378 counted policies. Value Computation: For the ground version, the operator performs the same calculations outlined for level t=0t=0 for its 2727 policies for each combination of state tl,trtl,tr and policy of the other agent (2727 as well) for each agent. For the counting version, the operator calculates the values for its one partition for each of its 216216 policies for each state tl,trtl,tr. For the policy-counted version, the operator calculates the values for its one partition for each of the 378378 counted policies. For each policy, the computation has to be performed for each state tl,trtl,tr. Pruning: Pruning again follows the same procedure as outlined above, for two agents and each of their 2727 policies in each state and for each of the other agent’s policies in the ground version. In the counting version, the 12961296 policies of its one partition get checked for each state tl,trtl,tr. In the policy-counted version, the 2727 representative policies of its one partition are checked for each state and each counted policy of the remaining partition, i.e., the 2727 representative policies. Comment: This numerical example illustrates impressively that policy counting only pays off if the number of agents is large or at least outweighs the number of representative policies. That is the number of agents should at least be an order larger than the number of representative actions and observations available.