Stability and Learning in Strategic Queuing Systems
- URL: http://arxiv.org/abs/2003.07009v1
- Date: Mon, 16 Mar 2020 03:59:00 GMT
- Title: Stability and Learning in Strategic Queuing Systems
- Authors: Jason Gaitonde, Eva Tardos
- Abstract summary: We study the phenomenon in the context of a game modeling queuing systems.
routers compete for servers, where packets that do not get service will be resent at future rounds.
This paper is the first to study the effect of selfish learning in a queuing system.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bounding the price of anarchy, which quantifies the damage to social welfare
due to selfish behavior of the participants, has been an important area of
research. In this paper, we study this phenomenon in the context of a game
modeling queuing systems: routers compete for servers, where packets that do
not get service will be resent at future rounds, resulting in a system where
the number of packets at each round depends on the success of the routers in
the previous rounds. We model this as an (infinitely) repeated game, where the
system holds a state (number of packets held by each queue) that arises from
the results of the previous round. We assume that routers satisfy the no-regret
condition, e.g. they use learning strategies to identify the server where their
packets get the best service.
Classical work on repeated games makes the strong assumption that the
subsequent rounds of the repeated games are independent (beyond the influence
on learning from past history). The carryover effect caused by packets
remaining in this system makes learning in our context result in a highly
dependent random process. We analyze this random process and find that if the
capacity of the servers is high enough to allow a centralized and knowledgeable
scheduler to get all packets served even with double the packet arrival rate,
and queues use no-regret learning algorithms, then the expected number of
packets in the queues will remain bounded throughout time, assuming older
packets have priority. This paper is the first to study the effect of selfish
learning in a queuing system, where the learners compete for resources, but
rounds are not all independent: the number of packets to be routed at each
round depends on the success of the routers in the previous rounds.
Related papers
- 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) - Full Stage Learning to Rank: A Unified Framework for Multi-Stage Systems [40.199257203898846]
We propose an improved ranking principle for multi-stage systems, namely the Generalized Probability Ranking Principle (GPRP)
GPRP emphasizes both the selection bias in each stage of the system pipeline as well as the underlying interest of users.
Our core idea is to first estimate the selection bias in the subsequent stages and then learn a ranking model that best complies with the downstream modules' selection bias.
arXiv Detail & Related papers (2024-05-08T06:35:04Z) - Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback [7.8539454948826375]
This paper studies multi-stage systems with end-to-end bandit feedback.
Each job needs to go through multiple stages, each managed by a different agent, before generating an outcome.
The goal of this paper is to develop distributed online learning algorithms that achieve sublinear regret in adversarial environments.
arXiv Detail & Related papers (2024-04-06T05:34:12Z) - Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
In many two-agent systems, each agent learns separately and the rewards of the two agents are not perfectly aligned.
We model these systems as Stackelberg games with decentralized learning and show that standard regret benchmarks result in worst-case linear regret for at least one player.
We develop algorithms to achieve near-optimal $O(T2/3)$ regret for both players with respect to these benchmarks.
arXiv Detail & Related papers (2024-02-29T23:38:28Z) - A Study of Forward-Forward Algorithm for Self-Supervised Learning [65.268245109828]
We study the performance of forward-forward vs. backpropagation for self-supervised representation learning.
Our main finding is that while the forward-forward algorithm performs comparably to backpropagation during (self-supervised) training, the transfer performance is significantly lagging behind in all the studied settings.
arXiv Detail & Related papers (2023-09-21T10:14:53Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
This paper considers a multi-server system with multiple servers and multiple types of jobs, where different job types require different amounts of processing time at different servers.
The goal is to schedule jobs on servers without knowing the statistics of the processing times.
We propose a new algorithm, which combines the MaxWeight scheduling policy with discounted upper confidence bound (UCB) to simultaneously learn statistics and schedule jobs to servers.
arXiv Detail & Related papers (2022-09-02T15:37:02Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning.
We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures.
Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
arXiv Detail & Related papers (2022-01-30T06:10:04Z) - Decentralized Learning in Online Queuing Systems [27.18971095426405]
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$.
arXiv Detail & Related papers (2021-06-08T10:10:21Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action.
We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents.
Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
arXiv Detail & Related papers (2020-07-10T09:33:05Z) - Learning from Learners: Adapting Reinforcement Learning Agents to be
Competitive in a Card Game [71.24825724518847]
We present a study on how popular reinforcement learning algorithms can be adapted to learn and to play a real-world implementation of a competitive multiplayer card game.
We propose specific training and validation routines for the learning agents, in order to evaluate how the agents learn to be competitive and explain how they adapt to each others' playing style.
arXiv Detail & Related papers (2020-04-08T14:11:05Z) - Predictive Bandits [68.8204255655161]
We introduce and study a new class of bandit problems, referred to as predictive bandits.
In each round, the decision maker first decides whether to gather information about the rewards of particular arms.
The decision maker then selects an arm to be actually played in the round.
arXiv Detail & Related papers (2020-04-02T17:12:33Z)
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.