Reinforcement Learning With Reward Machines in Stochastic Games

• URL: http://arxiv.org/abs/2305.17372v3
• Date: Mon, 28 Aug 2023 18:10:17 GMT
• Title: Reinforcement Learning With Reward Machines in Stochastic Games
• Abstract summary: We develop an algorithm called Q-learning with reward machines for games (QRM-SG) We prove that Q-functions learned in QRM-SG converge to the Q-functions at a Nash equilibrium. The three case studies show that QRM-SG can learn the best-response strategies effectively.
• Score: 25.834116101920834
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We investigate multi-agent reinforcement learning for stochastic games with complex tasks, where the reward functions are non-Markovian. We utilize reward machines to incorporate high-level knowledge of complex tasks. We develop an algorithm called Q-learning with reward machines for stochastic games (QRM-SG), to learn the best-response strategy at Nash equilibrium for each agent. In QRM-SG, we define the Q-function at a Nash equilibrium in augmented state space. The augmented state space integrates the state of the stochastic game and the state of reward machines. Each agent learns the Q-functions of all agents in the system. We prove that Q-functions learned in QRM-SG converge to the Q-functions at a Nash equilibrium if the stage game at each time step during learning has a global optimum point or a saddle point, and the agents update Q-functions based on the best-response strategy at this point. We use the Lemke-Howson method to derive the best-response strategy given current Q-functions. The three case studies show that QRM-SG can learn the best-response strategies effectively. QRM-SG learns the best-response strategies after around 7500 episodes in Case Study I, 1000 episodes in Case Study II, and 1500 episodes in Case Study III, while baseline methods such as Nash Q-learning and MADDPG fail to converge to the Nash equilibrium in all three case studies.

Related papers

• Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games [6.622208195193136]
  This paper studies the convergence of Stackelberg Q-value iteration in two-player general-sum Markov games from a control-theoretic perspective.<n>To the best of the authors' knowledge, this paper offers the first finite-time convergence guarantees for Q-value iteration in general-sum Markov games under Stackelberg interactions.
  arXiv  Detail & Related papers  (2026-04-06T03:48:42Z)
• Discriminative Policy Optimization for Token-Level Reward Models [55.98642069903191]
  Process reward models (PRMs) provide more nuanced supervision compared to outcome reward models (ORMs)<n>Q-RM explicitly learns token-level Q-functions from preference data without relying on fine-grained annotations.<n>Reinforcement learning with Q-RM significantly enhances training efficiency, achieving convergence 12 times faster than ORM on GSM8K and 11 times faster than step-level PRM on MATH.
  arXiv  Detail & Related papers  (2025-05-29T11:40:34Z)
• RSQ: Learning from Important Tokens Leads to Better Quantized LLMs [65.5558181902098]
  Layer-wise quantization is a key technique for efficiently compressing large models without expensive retraining. We propose RSQ (Rotate, Scale, then Quantize), which applies rotations to the model to mitigate outliers. We demonstrate that RSQ consistently outperforms baseline methods across multiple downstream tasks and three model families.
  arXiv  Detail & Related papers  (2025-03-03T18:46:33Z)
• Multi-agent Reinforcement Learning with Deep Networks for Diverse Q-Vectors [3.9801926395657325]
  This paper proposes a deep Q-networks (DQN) algorithm capable of learning various Q-vectors using Max, Nash, and Maximin strategies. The effectiveness of this approach is demonstrated in an environment where dual robotic arms collaborate to lift a pot.
  arXiv  Detail & Related papers  (2024-06-12T03:30:10Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• QADYNAMICS: Training Dynamics-Driven Synthetic QA Diagnostic for Zero-Shot Commonsense Question Answering [48.25449258017601]
  State-of-the-art approaches fine-tune language models on QA pairs constructed from CommonSense Knowledge Bases. We propose QADYNAMICS, a training dynamics-driven framework for QA diagnostics and refinement.
  arXiv  Detail & Related papers  (2023-10-17T14:27:34Z)
• Continuous-time q-learning for mean-field control problems [4.3715546759412325]
  We study the q-learning, recently coined as the continuous time counterpart of Q-learning by Jia and Zhou (2023), for continuous time Mckean-Vlasov control problems. We show that two q-functions are related via an integral representation under all test policies. Based on the weak martingale condition and our proposed searching method of test policies, some model-free learning algorithms are devised.
  arXiv  Detail & Related papers  (2023-06-28T13:43:46Z)
• Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics [38.5932141555258]
  We study the dynamics of smooth Q-Learning, a popular reinforcement learning algorithm. We show a sufficient condition on the rate of exploration such that the Q-Learning dynamics is guaranteed to converge to a unique equilibrium in any game.
  arXiv  Detail & Related papers  (2023-01-23T18:39:11Z)
• MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning [63.46052494151171]
  We propose textitmulti-agent alternate Q-learning (MA2QL), where agents take turns to update their Q-functions by Q-learning. We prove that when each agent guarantees a $varepsilon$-convergence at each turn, their joint policy converges to a Nash equilibrium. Results show MA2QL consistently outperforms IQL, which verifies the effectiveness of MA2QL, despite such minimal changes.
  arXiv  Detail & Related papers  (2022-09-17T04:54:32Z)
• Independent and Decentralized Learning in Markov Potential Games [3.8779763612314633]
  We focus on the independent and decentralized setting, where players do not have knowledge of the game model and cannot coordinate. In each stage, players update their estimate of Q-function that evaluates their total contingent payoff based on the realized one-stage reward. We prove that the policies induced by our learning dynamics converge to the set of stationary Nash equilibria in Markov potential games with probability 1.
  arXiv  Detail & Related papers  (2022-05-29T07:39:09Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) learns successful equilibrium policies after a few interactions with the environment. We demonstrate our approach experimentally on an autonomous driving simulation benchmark.
  arXiv  Detail & Related papers  (2022-03-14T17:24:03Z)
• Resolving Implicit Coordination in Multi-Agent Deep Reinforcement Learning with Deep Q-Networks & Game Theory [0.0]
  We address two major challenges of implicit coordination in deep reinforcement learning: non-stationarity and exponential growth of state-action space. We demonstrate that knowledge of game type leads to an assumption of mirrored best responses and faster convergence than Nash-Q. Inspired by the dueling network architecture, we learn both a single and joint agent representation, and merge them via element-wise addition.
  arXiv  Detail & Related papers  (2020-12-08T17:30:47Z)
• Few-Shot Complex Knowledge Base Question Answering via Meta Reinforcement Learning [55.08037694027792]
  Complex question-answering (CQA) involves answering complex natural-language questions on a knowledge base (KB) The conventional neural program induction (NPI) approach exhibits uneven performance when the questions have different types. This paper proposes a meta-reinforcement learning approach to program induction in CQA to tackle the potential distributional bias in questions.
  arXiv  Detail & Related papers  (2020-10-29T18:34:55Z)
• On Information Asymmetry in Competitive Multi-Agent Reinforcement Learning: Convergence and Optimality [78.76529463321374]
  We study the system of interacting non-cooperative two Q-learning agents. We show that this information asymmetry can lead to a stable outcome of population learning.
  arXiv  Detail & Related papers  (2020-10-21T11:19:53Z)

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.