Impact Of Decentralized Learning On Player Utilities In Stackelberg Games

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 e

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydonahue2024impact

Related papers

• Online Learning In Stackelberg Games With An Omniscient Follower (2023)0.00
• Decentralized Model-free Reinforcement Learning In Stochastic Games With Average-reward Objective (2023)0.00
• Regret Bounds For Decentralized Learning In Cooperative Multi-agent Dynamical Systems (2020)0.00
• Decentralized Optimal Equilibrium Learning In Stochastic Games Via Single-bit Feedback (2026)0.00
• Learning A Game By Paying The Agents (2025)0.00
• Sample-efficient Learning Of Stackelberg Equilibria In General-sum Games (2021)0.00
• Distributed No-regret Learning In Multi-agent Systems (2020)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00