Exploiting Anonymity and Homogeneity in Factored Dec-MDPs through Precomputed Binomial Distributions

Recent work in decentralized stochastic planning for cooperative agents has focussed on exploiting homogeneity of agents and anonymity in interactions to solve problems with large numbers of agents. Due to a linear optimization formulation that computes joint policy and an objective that indirectly approximates joint expected reward with reward for expected number of agents in all state, action pairs, these approaches have ensured improved scalability. Such an objective closely approximates joint expected reward when there are many agents, due to law of large numbers. However, the performance deteriorates in problems with fewer agents. In this paper, we improve on the previous line of work by providing a linear optimization formulation that employs a more direct approximation of joint expected reward. The new approximation is based on offline computation of binomial distributions. Our new technique is not only able to improve quality performance on problems with large numbers of agents, but is able to perform on par with existing best approaches on problems with fewer agents. This is achieved without sacrificing on scalability/run-time performance of previous work.