Learning stable strategies for agents with uncertain goals in timed settings
Learning Rational Strategies for Temporal Objectives in Multi-Agent Systems
Machine LearningLogic in Computer ScienceMultiagent Systems
Summary
This paper looks at how multiple agents (like robots or software programs) can learn to act in ways that meet their uncertain goals which happen over time and involve randomness. The authors focus on finding strategies where each agent's goals, expressed in a precise time-dependent way, have the best chance of being met without anyone wanting to change their own actions afterward. They use advanced learning methods that don’t need prior knowledge of the environment to find such stable strategies. The approach was tested in simulated game-like settings with multiple players acting simultaneously.
What this means in practice
- •For robotics teams: Design cooperative robot controllers that reliably achieve timed tasks despite facing uncertain and changing environmental dynamics.
- •For autonomous vehicle developers: Develop strategic decision-making modules ensuring stable interactions among multiple autonomous vehicles with complex temporal goals under uncertainty.
Authors
Omar Adalat, Edwin Hamel-De le Court, Francesco Belardinelli
Abstract
We study rational synthesis for stochastic multi-agent systems with unknown dynamics, where each agent is equipped with its own probabilistic temporal objective specified using Probabilistic Linear Temporal Logic on Finite Traces ($\mathsf{PLTL}_f}$). We impose solution concepts (e.g., Nash equilibrium, subgame-perfect equilibrium) as constraints on the joint strategy profile, using payoffs derived from each agent's probability of satisfying its temporal objective. In particular, we formulate per-agent rational synthesis as finding a strategy profile -- if one exists -- such that (i) the designated agent's probabilistic temporal constraint is satisfied, and (ii) the profile represents a stable solution under a chosen solution concept. We give conditional convergence guarantees for tabular Nash-Q learning, certify satisfaction with simultaneous finite-sample confidence bounds, and assess strategic stability with approximate best-response checking. Our approach operates in a stochastic \emph{Multi-Agent Reinforcement Learning} (MARL) environment, where model-free learning algorithms attempt to attain extremal satisfaction probabilities for temporal objectives automatically compiled into reward automata. Our approach is empirically validated using 8 general-sum concurrent stochastic games.