Impact of Decentralized Learning on Player Utilities in Stackelberg Games

• URL: http://arxiv.org/abs/2403.00188v2
• Date: Fri, 21 Jun 2024 17:11:10 GMT
• Title: Impact of Decentralized Learning on Player Utilities in Stackelberg Games
• Authors: Kate Donahue, Nicole Immorlica, Meena Jagadeesan, Brendan Lucier, Aleksandrs Slivkins,
• Abstract summary: 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.
• Score: 57.08270857260131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When deployed in the world, a learning agent such as a recommender system or a chatbot often repeatedly interacts with another learning agent (such as a user) over time. In many such two-agent systems, each agent learns separately and the rewards of the two agents are not perfectly aligned. To better understand such cases, we examine the learning dynamics of the two-agent system and the implications for each agent's objective. We model these systems as Stackelberg games with decentralized learning and show that standard regret benchmarks (such as Stackelberg equilibrium payoffs) result in worst-case linear regret for at least one player. To better capture these systems, we construct a relaxed regret benchmark that is tolerant to small learning errors by agents. We show that standard learning algorithms fail to provide sublinear regret, and we develop algorithms to achieve near-optimal $O(T^{2/3})$ regret for both players with respect to these benchmarks. We further design relaxed environments under which faster learning ($O(\sqrt{T})$) is possible. Altogether, our results take a step towards assessing how two-agent interactions in sequential and decentralized learning environments affect the utility of both agents.

Related papers

• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  We investigate learning the equilibria in non-stationary multi-agent systems. We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
  arXiv  Detail & Related papers  (2023-06-12T23:48:24Z)
• MERMAIDE: Learning to Align Learners using Model-Based Meta-Learning [62.065503126104126]
  We study how a principal can efficiently and effectively intervene on the rewards of a previously unseen learning agent in order to induce desirable outcomes. This is relevant to many real-world settings like auctions or taxation, where the principal may not know the learning behavior nor the rewards of real people. We introduce MERMAIDE, a model-based meta-learning framework to train a principal that can quickly adapt to out-of-distribution agents.
  arXiv  Detail & Related papers  (2023-04-10T15:44:50Z)
• 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)
• Learning in Stackelberg Games with Non-myopic Agents [60.927889817803745]
  We study Stackelberg games where a principal repeatedly interacts with a non-myopic long-lived agent, without knowing the agent's payoff function. We provide a general framework that reduces learning in presence of non-myopic agents to robust bandit optimization in the presence of myopic agents.
  arXiv  Detail & Related papers  (2022-08-19T15:49:30Z)
• Retrieval-Augmented Reinforcement Learning [63.32076191982944]
  We train a network to map a dataset of past experiences to optimal behavior. The retrieval process is trained to retrieve information from the dataset that may be useful in the current context. We show that retrieval-augmented R2D2 learns significantly faster than the baseline R2D2 agent and achieves higher scores.
  arXiv  Detail & Related papers  (2022-02-17T02:44:05Z)
• Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration [35.75029940279768]
  We study multi-agent reinforcement learning in the most basic cooperative setting -- Markov teams. We propose an algorithm in which each agent independently runs a stage-based V-learning style algorithm. We show that the agents can learn an $epsilon$-approximate Nash equilibrium policy in at most $proptowidetildeO (1/epsilon4)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T02:45:12Z)
• Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games [5.205867750232226]
  This paper addresses the problem of learning an equilibrium efficiently in general-sum Markov games. We propose an algorithm in which each agent independently runs optimistic V-learning to efficiently explore the unknown environment. We show that the agents can find an $epsilon$-approximate CCE in at most $widetildeO( H6S A /epsilon2)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T02:01:22Z)
• PsiPhi-Learning: Reinforcement Learning with Demonstrations using Successor Features and Inverse Temporal Difference Learning [102.36450942613091]
  We propose an inverse reinforcement learning algorithm, called emphinverse temporal difference learning (ITD) We show how to seamlessly integrate ITD with learning from online environment interactions, arriving at a novel algorithm for reinforcement learning with demonstrations, called $Psi Phi$-learning.
  arXiv  Detail & Related papers  (2021-02-24T21:12:09Z)
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems [3.9599054392856488]
  quadratic analysis is challenging in Multi-Agent Reinforcement Learning (MARL) We propose a MARL algorithm based on the construction of an auxiliary single-agent LQ problem. We show that our algorithm provides a $tildeO(sqrtT)$ regret bound.
  arXiv  Detail & Related papers  (2020-01-27T23:37:41Z)

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.