Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach

• URL: http://arxiv.org/abs/2408.13139v1
• Date: Fri, 23 Aug 2024 15:01:37 GMT
• Title: Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach
• Authors: Johan Peralez, Aurélien Delage, Jacopo Castellini, Rafael F. Cunha, Jilles S. Dibangoye,
• Abstract summary: epsilon training for decentralized execution paradigm emerged as the state-of-the-art approach to epsilon-optimally solving decentralized partially observable decision processes. This paper presents a novel and more scalable alternative, namely sequential-move centralized training for decentralized execution.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Centralized training for decentralized execution paradigm emerged as the state-of-the-art approach to epsilon-optimally solving decentralized partially observable Markov decision processes. However, scalability remains a significant issue. This paper presents a novel and more scalable alternative, namely sequential-move centralized training for decentralized execution. This paradigm further pushes the applicability of Bellman's principle of optimality, raising three new properties. First, it allows a central planner to reason upon sufficient sequential-move statistics instead of prior simultaneous-move ones. Next, it proves that epsilon-optimal value functions are piecewise linear and convex in sufficient sequential-move statistics. Finally, it drops the complexity of the backup operators from double exponential to polynomial at the expense of longer planning horizons. Besides, it makes it easy to use single-agent methods, e.g., SARSA algorithm enhanced with these findings applies while still preserving convergence guarantees. Experiments on two- as well as many-agent domains from the literature against epsilon-optimal simultaneous-move solvers confirm the superiority of the novel approach. This paradigm opens the door for efficient planning and reinforcement learning methods for multi-agent systems.

Related papers

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
  The optimistic gradient method is useful in addressing minimax optimization problems. Motivated by the observation that the conventional version suffers from the need for a large batch size, we introduce and analyze a new formulation termed Samevareps-generativeOGOG.
  arXiv  Detail & Related papers  (2024-01-26T01:16:59Z)
• Non-stationary Reinforcement Learning under General Function Approximation [60.430936031067006]
  We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA. We show that SW-OPEA is provably efficient as long as the variation budget is not significantly large.
  arXiv  Detail & Related papers  (2023-06-01T16:19:37Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  Gradient Descent (SGD) and its variants have become the dominant methods in the large-scale optimization machine learning (ML) problems. We provide formal guarantees of a few convex optimization methods and proposing improved algorithms.
  arXiv  Detail & Related papers  (2022-07-31T19:41:22Z)
• Decentralized Safe Multi-agent Stochastic Optimal Control using Deep FBSDEs and ADMM [16.312625634442092]
  We propose a novel safe and scalable decentralized solution for multi-agent control in the presence of disturbances. Decentralization is achieved by augmenting to each agent's optimization variables, copy variables, for its neighbors. To enable safe consensus solutions, we incorporate an ADMM-based approach.
  arXiv  Detail & Related papers  (2022-02-22T03:57:23Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Holdout SGD: Byzantine Tolerant Federated Learning [43.446891082719944]
  This work presents a new distributed Byzantine tolerant federated learning algorithm, HoldOut SGD, for Gradient Descent (SGD) optimization. HoldOut SGD uses the well known machine learning technique of holdout estimation, in a distributed fashion, in order to select parameter updates that are likely to lead to models with low loss values. We provide formal guarantees for the HoldOut SGD process in terms of its convergence to the optimal model, and its level of resilience to the fraction of Byzantine workers.
  arXiv  Detail & Related papers  (2020-08-11T10:16:37Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.