Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization

• URL: http://arxiv.org/abs/2608.30271v2
• Date: Sat, 05 Sep 2026 21:45:56 GMT
• Title: Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
• Abstract summary: We study decentralized online optimization of payoffs over an internal action set under efficient separation access.<n>We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BRL)<n>We give four wrapper instantiations covering three DR-submodular problems.
• Score: 46.739099064298735
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of $\widetilde O(\sqrt{T})$. Over $T$ rounds, each agent uses $T$ neighbor-mixing steps and $\widetilde O(T)$ separation-oracle calls. We give four wrapper instantiations covering three DR-submodular maximization problems.

Related papers

• Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems [0.0]
  We model agent selection and communication as a cooperative game with task-conditioned net utility $U(Cmid x)=V(Cmid x)-sum_iin Cc_i$.<n>We propose a marginal-value activation rule and greedy router, extend the model to optimize communication edges with per-edge costs, and use estimated Shapley values to predict which agents are worth contacting before and during execution.
  arXiv  Detail & Related papers  (2026-07-24T19:25:21Z)
• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling [3.396870608435494]
  We study a cooperative Markov game with a global agent and $n$ homogeneous local agents in a communication-constrained regime.<n>We prove that these approximate best-response dynamics converge to an $widetildeO (1/sqrtk)$-approximate Nash Equilibrium.
  arXiv  Detail & Related papers  (2026-03-04T06:14:24Z)
• Multi-Agent Stage-wise Conservative Linear Bandits [2.2557806157585834]
  We study the linear bandit problem in a multi-agent networked setting.<n>Agents must satisfy stage-wise conservative constraints.<n>We propose MA-SCLUCB, an episodic algorithm alternating between action selection and consensus-building phases.
  arXiv  Detail & Related papers  (2025-10-01T07:29:18Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization [11.889570525184801]
  We present two decentralized online algorithms for the monotone continuous DR-submodular-Frank problem. The first one, One-shot Decentralized Meta-Wolfe (Mono-DMFW), achieves a $(1-1/e)$regret bound $O(T4/5)$. Next, inspired by the non-oblivious boosting function citepzhang2022, we propose the Decentralized Online Boosting Gradient Ascent (DOBGA) algorithm.
  arXiv  Detail & Related papers  (2022-08-18T07:32:28Z)
• Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification [74.10976684469435]
  offline reinforcement learning (RL) algorithms can be transferred to multi-agent settings directly. We propose a simple yet effective method, Offline Multi-Agent RL with Actor Rectification (OMAR), to tackle this critical challenge. OMAR significantly outperforms strong baselines with state-of-the-art performance in multi-agent continuous control benchmarks.
  arXiv  Detail & Related papers  (2021-11-22T13:27:42Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)

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.