Fast adaptive learning in repeated stochastic games by game abstraction

An agent must learn and adapt quickly when playing against other agents. This process is challenging in particular when playing in stochastic environments against other learning agents. In this paper, we introduce a fast and adaptive learning algorithm for repeated stochastic games (FAL-SG). FAL-SG utilizes lossy game abstraction to reduce the state space of the game and facilitate learning and adapting rapidly. We analyze FAL-SG's performance by proving bounds on the abstraction loss and prediction mistakes and show that FAL-SG satisfies three criteria prescribed for multiagent learning algorithms. We successfully establish the robustness and scalability of FAL-SG with extensive theoretical and experimental results.

• Publication year

  2014

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2014-05-05

• Fields of study

  Computer Science

• Identifiers
  DOI 10.65109/bohi3349
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Just add Pepper: extending learning algorithms for repeated matrix games to repeated Markov games

  2012cited by this paper
• Lossy stochastic game abstraction with bounds

  2012influential reference
• When speed matters in learning against adversarial opponents

  2012cited by this paper
• Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning

  2011cited by this paper
• Convergence, Targeted Optimality, and Safety in Multiagent Learning

  2010cited by this paper
• A Polynomial-time Nash Equilibrium Algorithm for Repeated Stochastic Games

  2008cited by this paper
• Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker

  2007cited by this paper
• A general criterion and an algorithmic framework for learning in multi-agent systems

  2007cited by this paper
• Towards a Unified Theory of State Abstraction for MDPs

  2006cited by this paper
• Prediction, learning, and games

  2006cited by this paper
• Using additive expert ensembles to cope with concept drift

  2005cited by this paper
• Non-Stationary Policy Learning in 2-Player Zero Sum Games

  2005cited by this paper
• Performance Bounded Reinforcement Learning in Strategic Interactions

  2004cited by this paper
• Convergence and No-Regret in Multiagent Learning

  2004influential reference
• AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents

  2003cited by this paper
• Correlated Q-Learning

  2003cited by this paper
• Model-Based Clustering, Discriminant Analysis, and Density Estimation

  2002influential reference
• Multiagent learning using a variable learning rate

  2002influential reference
• Leading Best-Response Strategies in Repeated Games

  2001cited by this paper
• R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning

  2001cited by this paper
• Abstraction Methods for Game Theoretic Poker

  2000cited by this paper
• Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm

  1998cited by this paper
• Markov Games as a Framework for Multi-Agent Reinforcement Learning

  1994cited by this paper
• The weighted majority algorithm

  1989cited by this paper
• Maximum likelihood from incomplete data via the EM - algorithm plus discussions on the paper

  1977cited by this paper
• ACTIVITY ANALYSIS OF PRODUCTION AND ALLOCATION

  1952cited by this paper

• Computation Offloading Scheduling Using Game Abstraction in Ultra-dense Networks

  2024cites this paper
• An online learning algorithm to play discounted repeated games in wireless networks

  2022cites this paper
• Stochastic Game Model of Data Clustering

  2021cites this paper
• Thompson sampling for Markov games with piecewise stationary opponent policies

  2021cites this paper
• Independent learning approaches: overcoming multi-agent learning pathologies in team-games

  2020influential citation
• A distributed algorithm to obtain repeated games equilibria with discounting

  2020cites this paper
• Confronting barriers to human-robot cooperation: balancing efficiency and risk in machine behavior

  2020cites this paper
• When autonomous agents model other agents: An appeal for altered judgment coupled with mouths, ears, and a little more tape

  2020cites this paper
• Cooperation in Games

  2019cites this paper
• Achieving cooperation through deep multiagent reinforcement learning in sequential prisoner's dilemmas

  2019cites this paper
• Discrete Gift Exchange Game : Effects of Limited Choices on Opponent Interaction

  2019cites this paper
• Bayes-ToMoP: A Fast Detection and Best Response Algorithm Towards Sophisticated Opponents

  2018cites this paper
• Towards Cooperation in Sequential Prisoner's Dilemmas: a Deep Multiagent Reinforcement Learning Approach

  2018cites this paper
• A Novel Approach by Cooperative Multiagent Fault Pair Learning (CMFPL)

  2018cites this paper
• Multi-Agent Cooperation Based on Reinforcement Learning with Internal Reward in Maze Problem

  2018cites this paper
• A Framework for Dynamic Decision Making by Multi-agent Cooperative Fault Pair Algorithm (MCFPA) in Retail Shop Application

  2018cites this paper
• A Survey of Self-Organization Mechanisms in Multiagent Systems

  2017cites this paper
• A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity

  2017influential citation
• Cooperating with machines

  2017cites this paper
• Intelligent decision-making in coupled socio-ecological systems

  2017cites this paper
• Prediction-Based Multi-Agent Reinforcement Learning in Inherently Non-Stationary Environments

  2017cites this paper
• Efficiently detecting switches against non-stationary opponents

  2017cites this paper
• An exploration strategy for non-stationary opponents

  2017cites this paper
• Comparison Between Reinforcement Learning Methods with Different Goal Selections in Multi-Agent Cooperation

  2017cites this paper
• Towards a Fast Detection of Opponents in Repeated Stochastic Games

  2017cites this paper
• Identifying and Tracking Switching, Non-Stationary Opponents: A Bayesian Approach

  2016cites this paper
• Synthetic learning agents in game-playing social environments

  2016cites this paper
• Proceedings in Adaptation, Learning and Optimization

  2016cites this paper
• Prediction-Based Multi-Agent Reinforcement Learning for Inherently Non-Stationary Environments

  2016cites this paper
• Reinforcement Learning with Internal Reward for Multi-Agent Cooperation: A Theoretical Approach

  2016cites this paper
• Accelerating Multiagent Reinforcement Learning by Equilibrium Transfer

  2015cites this paper
• A Survey of Self-organisation Mechanisms in Multi-Agent Systems

  2015cites this paper
• Non-Myopic Learning in Repeated Stochastic Games

  2014cites this paper
• Robust Learning for Repeated Stochastic Games via Meta-Gaming

  2014cites this paper
• Using a Priori Information for Fast Learning Against Non-stationary Opponents

  2014cites this paper