Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and Inverse Learning

Shenghui Chen, Yue Yu, David Fridovich-Keil, Ufuk Topcu

Introduction

In classical game theory, the Nash Equilibrium serves as the foundational solution concept, predicated on the assumption that all players are perfectly rational agents with infinite computational capacity. However, empirical observations of human behavior and biological systems often reveal "bounded rationality"—a state where agents make near-optimal decisions influenced by cognitive limits, heuristics, or inherent noise.

This paper introduces the Soft-Bellman Equilibrium (SBE), a novel framework designed for multi-player Markov games that explicitly accounts for such boundedly rational behavior. By integrating "soft" reinforcement learning principles into a multi-agent game-theoretic context, the authors provide a robust mathematical structure for both computing equilibrium states (the forward problem) and inferring underlying agent motivations from observed interactions (the inverse problem).

The Soft-Bellman Equilibrium (SBE)

The SBE departs from traditional maximization by incorporating a causal entropy term into the agents' objective functions. Instead of strictly choosing the action with the highest expected utility, agents follow a "soft-max" policy. This approach acknowledges that agents are more likely to select high-reward actions but maintain a degree of exploration or stochasticity.

The study focuses on Affine Markov Games. In these environments, while players may have independent movement dynamics, their rewards are coupled through an affine function of the joint behavior of all participants. This structure is particularly relevant for modeling scenarios where the benefits or costs of an action depend linearly on the actions of others, such as traffic flow or collaborative foraging.

Forward Solutions and Inverse Learning

The authors address two primary challenges: solving for the equilibrium and learning rewards from data.

The Forward Problem

To determine the SBE in a known game environment, the authors transform the equilibrium conditions into a nonlinear least-squares optimization problem. A critical insight in this process is the shift from optimizing policies directly to optimizing over the state-action frequency matrix. This transformation is pivotal; it allows the authors to prove that under specific conditions—primarily concerning the coupling matrix $C$—the equilibrium is both existent and unique.

The Inverse Problem

The inverse learning task involves observing agent trajectories and inferring the reward parameters that generated that behavior. The authors employ Implicit Differentiation to bridge this gap. By treating the forward equilibrium solution as a differentiable function of the reward parameters, they can utilize a projected-gradient descent method. This allows the model to "tune" hidden reward structures until the resulting SBE aligns with the observed expert trajectories.

Experimental Evaluation

The framework was evaluated using the Predator-Prey OpenAI Gym (ma-gym) environment, a 5x5 GridWorld where two predators must coordinate to capture a randomly moving prey. Since standard human datasets for this specific task are limited, the researchers generated synthetic expert trajectories using a multi-agent reinforcement learning proxy to simulate human-like interaction.

Key Results

The SBE approach was compared against a "decoupled" baseline that treats agents as independent learners, ignoring the strategic influence of their peers.

  • Accuracy: The SBE algorithm significantly outperformed the baseline, reducing the Kullback-Leibler (KL) divergence between predicted and observed policies by at least two orders of magnitude.
  • Convergence and Stability: In the predator-prey environment, the SBE approach demonstrated superior stability, reaching a significantly lower error threshold ($<1$) compared to the baseline ($>590$).
  • Behavioral Modeling: Heatmap analysis indicated that the SBE model accurately captured agent interactions across the grid, particularly in high-interaction states where the decoupled baseline failed to predict coordinated behavior.

Discussion and Future Directions

The Soft-Bellman Equilibrium provides a mathematically rigorous way to model multi-agent systems where perfect rationality is an unrealistic assumption. By accounting for the coupling between agents and the inherent noise in decision-making, it offers a more nuanced view of strategic interaction than traditional Nash-based models.

However, several avenues for future research remain. The current reliance on an affine reward structure, while flexible, may need to be generalized for highly non-linear real-world rewards. Furthermore, while the synthetic results are compelling, validating the SBE framework against real-world human interaction data—such as the INTERACTION dataset for autonomous driving—is a necessary next step. Finally, scaling the nonlinear least-squares solution to high-dimensional state spaces will be essential for applying this framework to complex, large-scale simulations.

Summary updated

BibTeX
@inproceedings{chen2023soft,
  author = {Shenghui Chen and Yue Yu and David Fridovich-Keil and Ufuk Topcu},
  title = {{Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and Inverse Learning}},
  booktitle = {CDC},
  year = {2023},
  url = {https://openreview.net/forum?id=NJnALlmNAo},
}
Figure