## 1 Introduction  
Cooperative decision-making under uncertainty is a common problem in many scenarios such as sensor networks and airport service robots. Consider a scenario where a robot soccer team cooperates to beat the opponent. A total of 11 robot players dash in a simulated field, kicking, passing, and shooting a ball to score a goal. Each of them could only acquire his local observation and every action taken is uncertain, which means passing may be unsuccessful or shooting may be biased. Another example is congestion control, which is an important task in the Internet. The router's buffer accommodates transient packets to guarantee a stable network link. The distributed routers need to come up with a strategy to avoid congestion. These kinds of problems can be modeled as a decentralized partially observable Markov decision process (Dec-POMDP), which provides a general multi-agent model for decision-making under uncertainty. However, Dec-POMDPs are provably intractable (NEXP-Complete, nondeterministic exponential time, it is known that \(\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXP}\)[1] and difficult to solve with the number of joint policies growing explosively [2]. One of the primary reasons is that the search space of Dec-POMDPs grows exponentially with the number of actions and observations, and doubly exponentially with the horizon of the problem [3]. The optimal policy can be extracted from the optimal Q-value function \(\text{Q}^{*}\) for Dec-POMDPs, but solving \(\text{Q}^{*}\) is also proved to be NEXP-Complete [4]. In a previous work [5], Monte Carlo tree search (MCTS) [6] is introduced into the MMDP (Multiagent MDP) model, which is a simplified model for Dec-POMDPs, to solve ad hoc agent teams decision-making. MCTS is a sample-based tree search algorithm using Monte Carlo simulations as state evaluations, which has been successful in Computer Go [7]. MCTS will converge to the optimal value if exploration (find new nodes that are not sampled) and exploitation (find promising nodes that are already sampled) are traded off appropriately when given sufficient time and can be stopped at any time to get an approximate result. To tackle the doubly exponential problem, we propose an offline algorithm called a clustering and expansion with Monte-Carlo algorithm (CEMC) based on incremental clustering and expansion (ICE), a version of generalized multi-agent A* (GMAA*) with incremental clustering and expansion, which is the best heuristic method in this literature. MCTS is integrated into the CEMC framework to fast obtain the approximate Q-value function. MCTS is an anytime algorithm, and its efficiency is up to sample times and the degree of accuracy of the Q-value function evaluation. Thus, we propose an adaptive sample method according to the horizon and the number of joint actions and observations. The best upper bound found in the MCTS algorithm is used to prune the nodes that will not be the optimal ones in any case. The term MCTS in this paper denotes the specific algorithm that uses UCB1 (a version of upper confidence bound) as the tree selection policy proposed by [PERSON] and [PERSON] [6; 8]. The key contribution is twofold: We present a new Q-value function representation--Monte Carlo Q-value function \(\text{Q}_{\text{MC}}\) and an offline planning algorithm CEMC. Heavy playout for simulation policy and adaptive sample are introduced to speed up the computation of \(\text{Q}_{\text{MC}}\). The algorithm CEMC calculates the Q-value functions as required, without computing and storing all Q-value functions and it uses an extended pruning strategy for the policy pool. We present empirical results demonstrating that CEMC outperforms the best heuristic algorithm with a compact Q-value presentation in term of runtime for the same horizon, and has less memory usage for larger problems. The remainder of this paper is structured as follows. We first introduce some related work in Section 2.