PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity

Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, Enrique Munoz de Cote

arXiv:1707.09183v2cs.MAcs.LG

TL;DR

Multiagent learning must adapt to opponents whose changing strategies make the learning target non-stationary, while fragmented research uses differing assumptions. This survey synthesizes game theory, reinforcement learning, and multi-armed bandit approaches into a framework and taxonomy of five increasingly sophisticated categories. It reports broad coverage of experimental and theoretical results and identifies four open research avenues, while noting limitations such as convergence time and lost guarantees in non-stationary settings.

  • Problem

    Concurrent adaptation makes multiagent environments non-stationary, violating assumptions behind single-agent methods and motivating specialized analysis across fragmented research communities.

  • Method

    The survey reviews algorithms across game theory, reinforcement learning, and multi-armed bandits, organizing them by five approaches to non-stationarity and environment and opponent characteristics.

  • Results

    The survey finds experimental work concentrated in repeated and stochastic games, with theoretical results including optimal-policy, non-exploitability, and equilibrium-convergence guarantees.

  • Takeaways & Limitations

    The taxonomy structures implicit assumptions, positions algorithms by their handling of non-stationarity, and clusters future research into diversity, dynamics, objectives, and applications.

  • Takeaways & Limitations

    Some model-free approaches may take longer to converge, while many approaches lose theoretical guarantees in non-stationary environments.

Abstract

from arXiv · show

The key challenge in multiagent learning is learning a best response to the behaviour of other agents, which may be non-stationary: if the other agents adapt their strategy as well, the learning target moves. Disparate streams of research have approached non-stationarity from several angles, which make a variety of implicit assumptions that make it hard to keep an overview of the state of the art and to validate the innovation and significance of new works. This survey presents a coherent overview of work that addresses opponent-induced non-stationarity with tools from game theory, reinforcement learning and multi-armed bandits. Further, we reflect on the principle approaches how algorithms model and cope with this non-stationarity, arriving at a new framework and five categories (in increasing order of sophistication): ignore, forget, respond to target models, learn models, and theory of mind. A wide range of state-of-the-art algorithms is classified into a taxonomy, using these categories and key characteristics of the environment (e.g., observability) and adaptation behaviour of the opponents (e.g., smooth, abrupt). To clarify even further we present illustrative variations of one domain, contrasting the strengths and limitations of each category. Finally, we discuss in which environments the different approaches yield most merit, and point to promising avenues of future research.

1. Introduction

Multiagent learning is difficult because concurrently adapting agents make the environment non-stationary, undermining assumptions behind single-agent methods. This survey organizes fragmented research into a coherent taxonomy of how algorithms address that challenge.

  • 1. Introduction: Concurrent adaptation makes each agent perceive the joint behaviour and environment as non-stationary.An agent’s actions affect other agents’ objectives, while other agents simultaneously learn and adapt.
  • 1. Introduction: Research communities make differing assumptions about opponents, including stationarity, adaptation speed, objectives, robustness, and strategic reasoning.Game theory, bandits, reinforcement learning, behavioural game theory, and planning address these questions differently.
  • 1. Introduction: The survey provides a coherent view of algorithms from reinforcement learning, multi-armed bandits, and game theory for long-term rewards in non-stationary environments.It addresses competitive and cooperative scenarios across multiple domains.
  • 1. Introduction: Its framework categorizes non-stationarity handling by increasing sophistication: ignore, forget, respond to target opponents, learn opponent models, and theory of mind.The survey also analyzes environment and opponent characteristics, illustrates category strengths and limitations, and identifies open research avenues.

2. Formal approaches from different domains that model non-stationarity

This section contrasts how multi-armed bandits, reinforcement learning, and game theory formalize interaction, information, and non-stationarity. Bandits distinguish stochastic and adversarial rewards, while MDP-based reinforcement learning assumes stationarity and learns policies from experience when the model is unknown.

  • Formal approaches from different domains that model non-stationarity: Different domains make distinct assumptions about prior information and online observability, shaping how they model and cope with opponent non-stationarity.These distinctions provide the basis for characterizing environment properties and solution approaches.
  • Formal approaches from different domains that model non-stationarity: The formal models differ in how much reasoning is available before versus during interaction, linking solution concepts to characteristic abilities to handle opponent adaptation.The section also standardizes terminology by treating player and agent, reward and payoff, and rounds and steps interchangeably.
  • 2.1 Multi-armed bandits: A stochastic bandit selects among arms with reward distributions, repeatedly balancing exploration of uncertain arms against exploitation of high observed rewards.The policy chooses one arm per round and observes only that arm’s reward.
  • 2.1 Multi-armed bandits: UCB1 uses upper confidence indices based on past rewards and play counts to balance exploration and exploitation, achieving logarithmic regret under bounded rewards.The algorithm initially plays each arm once, then selects using its confidence index.
  • 2.1 Multi-armed bandits: Adversarial bandits let an adversary fix each arm’s reward sequence before play, whereas adaptive adversaries can change the optimal action over time and require modified regret measures.The standard regret definition is inadequate when the adversary adapts online.
  • 2.2 Reinforcement Learning: An MDP models an agent choosing actions from states, with transition dynamics, rewards, and observations describing interaction with the environment.Figure 1 depicts actions affecting state; Figure 2 represents transitions with action, probability, and reward triplets.
  • 2.2 Reinforcement Learning: MDPs assume stationary transition probabilities and reward distributions, making them adequate for optimal single-agent decisions but mismatched to changing multiagent environments.The optimal policy maps states to actions and maximizes expected reward under this stationary model.
  • 2.2 Reinforcement Learning: Reinforcement-learning algorithms can learn an optimal policy from interaction without a complete a priori MDP description, using trial and error to discover rewarding actions.Q-learning estimates expected discounted payoff for state-action pairs and is an off-policy method.

3. Learning in multiagent environments

Multiagent learning is non-stationary because agents concurrently adapt, making an agent’s best response dependent on opponents’ policies. The survey introduces a framework that models opponent behaviour through policy-generating functions, beliefs, and influence functions, and organizes approaches into five categories.

  • The problem: Concurrent adaptation makes each agent perceive the joint behaviour and environment as non-stationary.An agent must account for how other agents behave while those agents simultaneously learn and adapt.
  • The problem: An agent’s optimal policy is a best response dependent on the other agents’ policies.If opponents are not learning and use stochastic policies, the environment is Markovian and single-agent algorithms suffice.
  • A new framework: The framework separates three modelling steps for opponent behaviour: policy-generating functions, beliefs, and influence functions.Policy-generating functions describe how opponents obtain policies; beliefs assign likelihoods to those functions; influence functions map beliefs into a lower-dimensional influence space.
  • A new framework: Policy-generating functions map observation histories into policies and capture opponents’ adaptation dynamics within an assumed set of possible functions.Deterministic functions can represent memory-bounded models with hidden states and support assumptions about policy change or revisitation.
  • A new framework: Beliefs represent uncertainty over opponents’ policy-generating functions using locally inferred observation histories.An agent infers another agent’s local history through p(h_j|h_i), potentially producing crisp or full belief representations.
  • A new framework: Influence functions partition beliefs according to equivalent best responses and can reduce the complexity of deriving those responses.This reduction may be lossless or heuristic, depending on the assumptions imposed or learned over the influence function.
  • Five categories: The survey categorizes algorithms by increasing sophistication: ignore, forget, respond to target opponents, learn opponent models, and theory of mind.The framework emphasizes how algorithms handle non-stationary behaviour and aligns the taxonomy with their assumptions.

4. Illustrative Example - Iterated Prisoner’s Dilemma

The survey contrasts five approaches to opponent-induced non-stationarity through variations of the infinite-horizon iterated prisoner’s dilemma. These examples show how each approach depends on assumptions about opponent strategies and changes.

  • Common domain: The illustrative domain is the infinite-horizon iterated prisoner’s dilemma, in which agents A and O repeatedly play the game.The prisoner’s dilemma has two players, two actions—cooperate and defect—and payoffs satisfying t_pd > r_pd > p_pd > s_pd and 2r_pd > p_pd + s_pd.
  • Ignore: Ignoring non-stationarity can work against a simple stationary mixed opponent but becomes problematic when that opponent changes strategy.The example uses π_m = (0.25, 0.75), with defect selected at higher probability, as the stationary assumption.
  • Forget: Forgetting adapts toward stationary policies by continuously learning and adjusting its learning rate to changing opponent behaviour.WoLF-PHC generalizes Q-learning and was proposed to converge to a stationary policy in self-play.
  • Respond to target opponents: Responding to target opponents assumes a known class of strategies and can become restricted when the opponent uses a strategy outside that class.HM-MDPs model the known strategies as stationary modes with stochastic transitions; adding a new strategy can leave the learned policy suboptimal after changes.
  • Learn opponent models: Learning opponent models starts without predefined opponent strategies and models several stationary strategies with infrequent changes to derive an acting policy.The example opponent may switch from Pavlov to Tit-for-Tat and later return to a previously used strategy.
  • Theory of mind: Theory of mind assumes strategic reasoning and best-responds to recursive reasoning levels about the agents’ possible strategies.A distribution over strategies such as Bully, random, and Pavlov represents level-zero reasoning in the example.
  • Taxonomy: The survey extends the examples into a taxonomy of state-of-the-art game-theoretic, bandit, and reinforcement-learning algorithms.The taxonomy includes environmental and opponent characteristics alongside the five sophistication categories.

5. Algorithms

The survey categorises algorithms by how they handle non-stationarity and compares them across observability, opponent adaptation, and application domains. Approaches range from ignoring non-stationarity to recursive models of other agents.

  • Table 2 classifies algorithms by non-stationarity handling, observability, opponent adaptation, and application domain.The listed domains include one-shot, repeated, stochastic, and extensive-form games, sequential decision tasks, and multi-armed bandits.
  • 5.1 Ignore: Fictitious play assumes a stationary opponent strategy, so it cannot compute a best response when the opponent changes strategy.It estimates the opponent’s mixed strategy from historical play frequencies.
  • 5.1 Ignore: Independent learners ignore other agents and optimise as if the environment were stationary, whereas joint-action learners explicitly model opponents’ joint actions.Both approaches are presented within model-free reinforcement learning.
  • 5.2 Forget: Forgetting old information and updating from recent observations addresses the limitation of failing to incorporate current information.FAL uses a fixed observation-history window and entropy-based hypothesis pruning to predict the opponent’s next action.
  • 5.3 Respond to target opponents: HM-MDPs represent non-stationarity with hidden stochastic modes, each modelled as a stationary MDP requiring its own policy.They require the number of modes to be fixed initially and provide no online learning.
  • 5.3 Respond to target opponents: Targeted counter-strategies can exploit their intended opponent successfully but may be insufficiently robust across different opponents.The survey reports this limitation in its discussion of frequentist best response.
  • 5.4 Learn opponent models: Opponent-model learning updates the model and derived policy to keep up with a non-stationary opponent.Examples include models for history-dependent policies and switching among stationary strategies.
  • 5.4 Learn opponent models: ζ-R-max adapts R-max using leave-one-out cross-validation of learning progress and retains a PAC-MDP efficiency guarantee.Its limitation is computational cost, which depends on the number of states and actions at every iteration.

6. Discussion

The discussion reviews five categories for handling non-stationary behaviour, then examines their strengths, limitations, domains, theoretical results, related research, and future directions.

  • The discussion covers strengths and limitations, experimental domains, theoretical results, related research, and promising future research.

6.1 Strengths and limitations of each category

The survey contrasts five categories for handling opponent-induced non-stationarity, highlighting different information requirements, adaptability, convergence speed, and computational costs.

  • Ignore: Ignore algorithms require no extra opponent information but generally lose theoretical guarantees in non-stationary environments.They are advised when no extra information can be obtained from the environment.
  • Forget: Forget algorithms account for non-stationarity without modeling opponents, but may take longer to converge.They are suitable when no a priori opponent information is available and learning time is unconstrained.
  • Respond to target opponents: Respond-to-target-opponent algorithms efficiently handle restricted opponent classes, but their adaptability is constrained when opponents use broader strategies.The survey gives worst-case opponents, stochastic switching, and Nash-equilibrium convergence as examples of target classes.
  • Learn opponent models: Learn-opponent-model algorithms can reuse models when an opponent returns to a strategy and usually learn faster, but require stationarity long enough for modeling.That stationarity requirement may be unrealistic in some scenarios.
  • Theory of mind: Theory-of-mind algorithms can model populations but require complex strategic reasoning with high computational costs and have mainly been studied in unrepeated games.Their population modeling follows from how they obtain an acting policy.

6.2 Experimental domains and applications

Experimental work spans formal games and application domains including negotiation, smart grids, routing, security, and surveillance, with settings varying in state spaces, observability, and adaptation demands.

  • Game-theoretic domains: Formal evaluations commonly use extensive-form, repeated, and stochastic games to study interactions with non-stationary opponents.These settings range from poker and simple matrix games to probabilistic grid-worlds.
  • Repeated games: Repeated-game benchmarks include 2x2 games, rock-scissors-paper, and the three-agent lemonade stand game requiring fast adaptation.In the lemonade stand game, vendors choose among 12 positions and rewards depend on all agents’ actions.
  • Other domains: Other evaluations cover application areas ranging from aerospace to security and surveillance.
  • Negotiation: Automated negotiation appears in e-commerce, virtual agents, diplomacy, and coloured trails, where preference learning models opponents’ profiles online.These models aim to reach Pareto-optimal outcomes.
  • Routing and smart cities: Routing environments model non-stationarity through changing optimal prices driven by other ISPs’ strategies and network load.Smart-city traffic networks represent different stationary environments through traffic patterns and traffic-light configurations.

6.3 Theoretical results

Theoretical work provides guarantees concerning regret, exploration, equilibrium convergence, best responses, robustness, and switch detection across stationary and non-stationary settings.

  • Regret bounds: Regret bounds cover adversarial, stochastic, and Markov-chain bandits, while fewer results address sequential decision or multiagent problems.
  • Efficient exploration guarantees: Efficient-exploration guarantees use sample-complexity results in both adversarial stationary and non-stationary environments.
  • Convergence to Nash equilibrium: Convergence guarantees to Nash equilibrium have been established under conditions including local rewards, partial observations, and complete information, often in self-play.
  • Best response: Best-response results address the loss of Q-learning’s optimal-policy guarantees in non-stationary environments by targeting improved guarantees or best-response policies.
  • Robustness guarantees: Robustness results express safety, security, or non-exploitability through expected rewards or regret bounds, alongside switch-detection results.

6.4 Related areas

Related research connects non-stationary multiagent learning to concept drift, transfer learning, ad-hoc coordination, partial observability, evolutionary game theory, and behavioural game theory.

  • Supervised learning and concept drift: Concept drift studies changing input-target relationships over time and categorizes changes such as sudden, gradual, recurrent, and outlier-driven drift.
  • Transfer learning: Transfer learning reuses experience from related tasks, with past-policy reuse inspiring work on recurring changes in multiagent systems.
  • Multiagent interaction without prior coordination: Ad-hoc teamwork concerns robust and efficient collaboration with previously unknown teammates without prior coordination.
  • Partial observability and planning: MMDPs model cooperative stochastic planning with shared payoffs, while POMDPs represent limited observations at greater computational cost than MDPs.
  • Evolutionary game theory: Evolutionary game theory links reinforcement learning dynamics to population-level equilibrium attraction and welfare analysis.
  • Behavioural game theory: Behavioural game theory adds human characteristics such as fairness, reciprocity, and deception to improve modeling of human behaviour.

6.5 Open questions and promising avenues of future research

The paper identifies open questions in multiagent learning and connects them to four promising research lines, including diversity, dynamic interactions, and applications.

  • Four promising research lines organize open questions in multiagent learning.The section presents example research questions within each line.
  • Extending the scope of MAL: Extending the scope of multiagent learning involves diversity in opponents, dynamic interactions, and applications.
  • Classification limitations: The classification-limitations challenge concerns identifying what is missing in multiagent learning.

Line 1: Diversity in opponents

Opponent diversity complicates optimal action because agents may differ in learning characteristics, objectives, actuators, and world representations. Scalable approaches therefore consider population-level responses and the accessibility of opponents’ knowledge.

  • Heterogeneous agents can differ in learning characteristics, objectives, actuators, and representations of the world, complicating optimal action.
  • Algorithms that interact with many agents can become intractable in large multiagent domains, motivating population-level generalisation.
  • Population-level methods aim to respond to classes of populations rather than individual opponents.
  • Determining interaction strength can help decide whether to interact with an agent or treat it as part of the environment.
  • Methods in the learn category assume access to knowledge describing opponents’ observations, although such information is often inaccessible in real situations.

Line 2: Dynamic interactions

Dynamic multiagent settings challenge algorithms that assume synchronous, fixed interactions and require learning under concurrent, changing participation. Reusing prior information and addressing exploratory action noise are proposed directions for reducing learning demands and instability.

  • Many algorithms assume synchronous interactions among all agents, whereas real-world coordination and negotiation can involve asynchronous, concurrent threads.
  • Learning opponent models can require many repeated interactions, motivating reuse of prior information to reduce learning time.
  • Offline opponent portfolios and advice to agents are examples of information-reuse approaches for multiagent learning.
  • A changing number of opponents, including agents that enter or leave during interaction, can affect the environment and acting policy.
  • Simultaneous exploration by multiple learning agents can create exploratory action noise for the rest of the system.

Line 3: Learning objectives

Learning algorithms differ in whether they seek convergence to an optimal policy or track changing payoffs, and transient performance can favor tracking. The survey also proposes analysing how much non-stationarity algorithms tolerate or induce.

  • Convergent algorithms target an optimal policy, whereas tracking algorithms follow solution payoffs without convergence guarantees.
  • In a stationary task, a tracking algorithm can outperform an algorithm that converges to the optimal policy in certain cases.
  • The survey calls for broader convergence results covering convergence, optimality, and non-exploitability in multiagent learning.
  • Tolerated non-stationarity measures how much non-stationarity an algorithm accepts without sacrificing optimality.
  • Induced non-stationarity is proposed as a second concept for analysing multiagent systems.

Line 4: Applications

The survey identifies generic negotiation under reinforcement learning as understudied, especially in nonstationary settings where preferences may evolve. It also highlights deep reinforcement learning as an emerging direction for handling nonstationarity.

  • Negotiation and MAS: Generic negotiation with reinforcement learning remains understudied, particularly beyond Q-learning for competitive market trading.The survey points to limited work on bilateral and multilateral negotiation.
  • Negotiation and MAS: Nonstationary negotiation remains unresolved when preferences such as risk tolerance or fairness attitudes evolve.
  • Deep RL and MAS: Deep reinforcement learning introduces nonstationarity challenges, while its large sample requirements motivate specialized handling of experience.The supplied passage identifies this as an emerging research direction but does not provide further algorithmic details.

7. Conclusions

The survey organizes research on nonstationary sequential decision making into a framework of five algorithmic approaches and classifies state-of-the-art methods accordingly. It identifies strengths, limitations, application guidelines, theoretical results, and four avenues for future research, while emphasizing that fundamental work remains necessary.

  • 7. Conclusions: The framework distinguishes five approaches to nonstationarity: ignore, forget, respond to target opponents, learn opponent models, and theory of mind.
  • 7. Conclusions: The survey classifies state-of-the-art algorithms, illustrates each category, and identifies strengths, limitations, and guideline scenarios for applying them.
  • 7. Conclusions: Most experiments use repeated or stochastic games, while theoretical results include optimal-policy, non-exploitability, and equilibrium-convergence guarantees.
  • 7. Conclusions: Future research is clustered into diversity in opponents, dynamic interactions, learning objectives, and applications.
  • 7. Conclusions: Further fundamental research is required for breakthrough guarantees and demonstrations of algorithmic performance in nonstationary environments.
Loading 1707.09183v2…