Decentralized Learning in Online Queuing Systems

• URL: http://arxiv.org/abs/2106.04228v1
• Date: Tue, 8 Jun 2021 10:10:21 GMT
• Title: Decentralized Learning in Online Queuing Systems
• Authors: Flore Sentenac and Etienne Boursier and Vianney Perchet
• Abstract summary: Online queuing systems are composed of queues receiving packets at different rates. In the centralized case, the number of accumulated packets remains bounded as long as the ratio between service rates and arrival rates is larger than $1$. We propose the first learning decentralized algorithm guaranteeing stability of the system as long as the ratio of rates is larger than $1$.
• Score: 27.18971095426405
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by packet routing in computer networks, online queuing systems are composed of queues receiving packets at different rates. Repeatedly, they send packets to servers, each of them treating only at most one packet at a time. In the centralized case, the number of accumulated packets remains bounded (i.e., the system is \textit{stable}) as long as the ratio between service rates and arrival rates is larger than $1$. In the decentralized case, individual no-regret strategies ensures stability when this ratio is larger than $2$. Yet, myopically minimizing regret disregards the long term effects due to the carryover of packets to further rounds. On the other hand, minimizing long term costs leads to stable Nash equilibria as soon as the ratio exceeds $\frac{e}{e-1}$. Stability with decentralized learning strategies with a ratio below $2$ was a major remaining question. We first argue that for ratios up to $2$, cooperation is required for stability of learning strategies, as selfish minimization of policy regret, a \textit{patient} notion of regret, might indeed still be unstable in this case. We therefore consider cooperative queues and propose the first learning decentralized algorithm guaranteeing stability of the system as long as the ratio of rates is larger than $1$, thus reaching performances comparable to centralized strategies.

Related papers

• PADER: Paillier-based Secure Decentralized Social Recommendation [11.613857573146658]
  We propose PADER: a Paillier-based secure decentralized social recommendation system.<n>The training and inference of the recommendation model are carried out securely in a decentralized manner.<n>Experiment results show that our method only takes about one second to iterate through one user with hundreds of ratings.
  arXiv  Detail & Related papers  (2026-01-15T09:24:00Z)
• Benchmarking metaheuristic algorithms for the bi-objective redundancy allocation problem in repairable systems with multiple strategies [3.632189127068905]
  This article investigates a bi-objective redundancy allocation problem (RAP) for repairable systems.<n> Binary decisions jointly select the number of components and the standby strategy at the subsystem level.<n>System availability is evaluated using continuous-time Markov chains.
  arXiv  Detail & Related papers  (2025-12-20T12:16:37Z)
• Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems [1.1575091540914677]
  Shortest Path (SSP) problems provide a natural framework for modeling decentralized control in such settings.<n>We study decentralized multi-agent SSPs (Dec-MASSPs) under linear function approximation.<n>Applying novel symmetry-based arguments, we identify the structure of optimal policies.
  arXiv  Detail & Related papers  (2025-11-06T17:49:33Z)
• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
  arXiv  Detail & Related papers  (2025-06-16T08:42:31Z)
• Lite-PoT: Practical Powers-of-Tau Setup Ceremony [11.689131565202945]
  Zk-SNARKs rely on a one-time trusted setup to generate a public parameter, often known as the Powers of Tau" (PoT) string. The leakage of the secret parameter, $tau$, in the string would allow attackers to generate false proofs, compromising the soundness of all zk-SNARK systems built on it. We present Lite-PoT, which includes two key protocols designed to reduce participation costs.
  arXiv  Detail & Related papers  (2025-03-06T15:34:50Z)
• Learning in Strategic Queuing Systems with Small Buffers [3.6480791907166306]
  We show that when queues are learning, a small constant factor increase in server capacity, compared to what would be needed if centrally coordinating, suffices to keep the system stable. This work contributes to the growing literature on the impact of selfish learning in systems with carryover effects between rounds.
  arXiv  Detail & Related papers  (2025-02-13T02:23:23Z)
• Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach [0.0]
  This paper presents a novel and more scalable alternative, namely the sequential-move centralized training for decentralized execution.<n>It further pushes the applicability of the Bellman's principle of optimality, raising three new properties.<n> Experiments on two- and many-agent domains confirm the superiority of our novel approach.
  arXiv  Detail & Related papers  (2024-08-23T15:01:37Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  Non-concave games introduce significant game-theoretic and optimization challenges. We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria. We also show that Online Gradient Descent can efficiently approximate $Phi$-equilibria in non-trivial regimes.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness [9.731329071569018]
  We consider distributed kernel bandits where $N$ agents aim to collaboratively maximize an unknown reward function. We develop the first algorithm that achieves the optimal regret order with a communication cost that is sublinear in both $N$ and $T$.
  arXiv  Detail & Related papers  (2024-02-20T17:49:10Z)
• Simple Opinion Dynamics for No-Regret Learning [38.61048016579232]
  We study a cooperative multi-agent bandit setting in the distributed GOSSIP model. We introduce and analyze families of memoryless and time-independent protocols for this setting. For stationary reward settings, we prove for the first time that these simple protocols exhibit best-of-both-worlds behavior.
  arXiv  Detail & Related papers  (2023-06-14T17:59:15Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  We propose an algorithm that minimizes the regret over the horizon of time $T$. The proposed algorithm is applicable to domains such as recommendation systems and transportation.
  arXiv  Detail & Related papers  (2023-01-31T03:49:00Z)
• Decentralized model-free reinforcement learning in stochastic games with average-reward objective [1.9852463786440127]
  We show that our algorithm achieves both sublinear high probability regret of order $T3/4$ and sublinear expected regret of order $T2/3$. Our algorithm enjoys a low computational complexity and low memory space requirement compared to the previous works.
  arXiv  Detail & Related papers  (2023-01-13T15:59:53Z)
• Communication-Efficient Topologies for Decentralized Learning with $O(1)$ Consensus Rate [35.698182247676414]
  Decentralized optimization is an emerging paradigm in distributed learning in which agents achieve network-wide solutions by peer-to-peer communication without the central server. We show that the total number of iterations to reach a network-wide solution is affected by the speed at which the agents' information is mixed'' by communication. We propose a new family of topologies, EquiTopo, which has an (almost) constant degree and a network-size-independent consensus rate.
  arXiv  Detail & Related papers  (2022-10-14T15:02:01Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  We study decentralized linear bandits, where a network of $N$ agents acts cooperatively to solve a linear bandit-optimization problem. We propose DLUCB: a fully decentralized algorithm that minimizes the cumulative regret over the entire network. We show that our ideas extend naturally to the emerging, albeit more challenging, setting of safe bandits.
  arXiv  Detail & Related papers  (2020-12-01T07:33:00Z)
• Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
  shortest path (SSP) is a well-known problem in planning and control. We present the adversarial SSP model that also accounts for adversarial changes in the costs over time. We are the first to consider this natural setting of adversarial SSP and obtain sub-linear regret for it.
  arXiv  Detail & Related papers  (2020-06-20T12:10:35Z)

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.