Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

Abstract:We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

Machine Learning (cs.LG); Multiagent Systems (cs.MA)

arXiv:2611.04072 [cs.LG]

(or arXiv:2611.04072v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2611.04072 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

experiment_reproducibility/README.txt

experiment_reproducibility/derived/pooled_summary.csv

experiment_reproducibility/derived/size_specific_summary.csv

experiment_reproducibility/experiments/_bootstrap.py

experiment_reproducibility/experiments/plot_maintex_sampled_scaling.py

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/calibration_finals.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/dimension_progress.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/main_finals.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/reward_summary.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/selected_configs.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/selected_configs_used.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/shape_summary.csv

experiment_reproducibility/experiments/results/truncation_linear_sampled_maintex/tune_finals.csv

experiment_reproducibility/experiments/run_maintex_sampled_scaling.py

experiment_reproducibility/figure3/plot_compact.py

experiment_reproducibility/figure3/summary.csv

experiment_reproducibility/provenance.csv

experiment_reproducibility/requirements.txt

experiment_reproducibility/src/io_utils.py

experiment_reproducibility/src/large_scale_envs.py

experiment_reproducibility/src/sampled_actor_critic.py

experiment_reproducibility/summarize_records.py

(17 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.