This paper presents a novel decentralized bi-level stochastic optimization approach based on the progressive hedging algorithm for multi-agent systems (MAS) in multi-energy microgrids (MEMGs) to enhance network flexibility. In the proposed model, suppliers and consumers of three energy carrier of power, heat, and hydrogen are considered. This system further consists of multi-energy storage systems such as plug-in electric vehicle aggregators, thermal energy storage, and hydrogen energy storage with the application of power-to-hydrogen and hydrogen-to-power technologies. Furthermore, the Latin Hypercube Sampling method has been utilized to manage the uncertainties. In addition, a penalty function and a power exchange pricing model are evaluated by the electrical marginal price of each microgrid to determine the agreed power exchange among the MEMGs. The suggested work performs over a MAS with three MEMGs. The total profit of each microgrid is maximized over a 24-h scheduling in three diverse case studies. Ultimately, the proposed decentralized bi-level optimization approach, by converging through seven iterations, indicates an effective performance as a promising solution to a MAS-based framework. Besides, the optimal scheduling of the MEMGs were converged in the same profit for the diverse network topologies. Implementing multi-energy storage systems plays a major role in increasing total profit of MEMGs and improving the reliability performance of MAS-based structure.