摘要：DecentralizedPOMDPs (Dec-POMDPs)are becomingincreasinglypopularas modelsformultiagentplan- ning under uncertainty,but solving a Dec-POMDP exactly is known to be an intractable combinatorial op- timization problem. In this paper we apply the Cross-Entropy (CE) method, a recently introduced method for combinatorial optimization, to Dec-POMDPs, resulting in a randomized (sampling-based) algorithm for approximately solving Dec-POMDPs. This algorithm operates by sampling pure policies from an ap- propriatelyparametrizedstochasticpolicy,andthenevaluatesthesepolicieseitherexactlyorapproximately in order to define the next stochastic policy to sample from, and so on until convergence. Experimental results demonstrate that the CE method can search huge spaces efficiently, supporting our claim that com- binatorial optimization methods can bring leverage to the approximate solution of Dec-POMDPs.
