Toward Finding Strong Pareto Optimal Policies in Multi-Agent Reinforcement Learning

• URL: http://arxiv.org/abs/2410.19372v1
• Date: Fri, 25 Oct 2024 08:19:49 GMT
• Title: Toward Finding Strong Pareto Optimal Policies in Multi-Agent Reinforcement Learning
• Authors: Bang Giang Le, Viet Cuong Ta,
• Abstract summary: We show that any algorithm where each agent only optimize their reward is subject to suboptimal convergence. This observation bridges the multi-objective optimization framework and multi-agent reinforcement learning together. We show that our proposed method can converge efficiently and outperform the other methods in terms of the optimality of the convergent policies.
• Score: 0.20718016474717196
• License:
• Abstract: In this work, we study the problem of finding Pareto optimal policies in multi-agent reinforcement learning problems with cooperative reward structures. We show that any algorithm where each agent only optimizes their reward is subject to suboptimal convergence. Therefore, to achieve Pareto optimality, agents have to act altruistically by considering the rewards of others. This observation bridges the multi-objective optimization framework and multi-agent reinforcement learning together. We first propose a framework for applying the Multiple Gradient Descent algorithm (MGDA) for learning in multi-agent settings. We further show that standard MGDA is subjected to weak Pareto convergence, a problem that is often overlooked in other learning settings but is prevalent in multi-agent reinforcement learning. To mitigate this issue, we propose MGDA++, an improvement of the existing algorithm to handle the weakly optimal convergence of MGDA properly. Theoretically, we prove that MGDA++ converges to strong Pareto optimal solutions in convex, smooth bi-objective problems. We further demonstrate the superiority of our MGDA++ in cooperative settings in the Gridworld benchmark. The results highlight that our proposed method can converge efficiently and outperform the other methods in terms of the optimality of the convergent policies. The source code is available at \url{https://github.com/giangbang/Strong-Pareto-MARL}.

Related papers

• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Optimistic Multi-Agent Policy Gradient [23.781837938235036]
  Relative overgeneralization (RO) occurs when agents converge towards a suboptimal joint policy. No methods have been proposed for addressing RO in multi-agent policy gradient (MAPG) methods. We propose a general, yet simple, framework to enable optimistic updates in MAPG methods that alleviate the RO problem.
  arXiv  Detail & Related papers  (2023-11-03T14:47:54Z)
• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  We present a multi-agent PPO algorithm in which the local policy of each agent is updated similarly to vanilla PPO. We prove that with standard regularity conditions on the Markov game and problem-dependent quantities, our algorithm converges to the globally optimal policy at a sublinear rate.
  arXiv  Detail & Related papers  (2023-05-08T16:20:03Z)
• Multi-Task Off-Policy Learning from Bandit Feedback [54.96011624223482]
  We propose a hierarchical off-policy optimization algorithm (HierOPO), which estimates the parameters of the hierarchical model and then acts pessimistically with respect to them. We prove per-task bounds on the suboptimality of the learned policies, which show a clear improvement over not using the hierarchical model. Our theoretical and empirical results show a clear advantage of using the hierarchy over solving each task independently.
  arXiv  Detail & Related papers  (2022-12-09T08:26:27Z)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  We study the multi-goal task assignment and path finding (MG-TAPF) problem from theoretical and algorithmic perspectives. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent path finding problem and solve the MG-TAPF problem optimally and bounded-suboptimally.
  arXiv  Detail & Related papers  (2022-08-02T03:17:29Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning [11.91425153754564]
  We show that in environments with a highly multi-modal reward landscape, value decomposition, and parameter sharing can be problematic and lead to undesired outcomes. In contrast, policy gradient (PG) methods with individual policies provably converge to an optimal solution in these cases. We present practical suggestions on implementing multi-agent PG algorithms for either high rewards or diverse emergent behaviors.
  arXiv  Detail & Related papers  (2022-06-15T13:03:05Z)
• Optimizer Amalgamation [124.33523126363728]
  We are motivated to study a new problem named Amalgamation: how can we best combine a pool of "teacher" amalgamations into a single "student" that can have stronger problem-specific performance? First, we define three differentiable mechanisms to amalgamate a pool of analyticals by gradient descent. In order to reduce variance of the process, we also explore methods to stabilize the process by perturbing the target.
  arXiv  Detail & Related papers  (2022-03-12T16:07:57Z)
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning [8.819672165548477]
  We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP)
  arXiv  Detail & Related papers  (2020-10-30T00:57:50Z)
• Multi-Agent Trust Region Policy Optimization [34.91180300856614]
  We show that the policy update of TRPO can be transformed into a distributed consensus optimization problem for multi-agent cases. We propose a decentralized MARL algorithm, which we call multi-agent TRPO (MATRPO)
  arXiv  Detail & Related papers  (2020-10-15T17:49:47Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
  arXiv  Detail & Related papers  (2020-06-15T19:40:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.