Recherche heuristique pour jeux stochastiques (à somme nulle)

Olivier Buffet, Jilles Dibangoye, Abdallah Saffidine, Vincent Thomas

TL;DR

This paper introduces a novel heuristic search algorithm for solving two-player, zero-sum stochastic games. It extends existing heuristic search methods like HSVI to handle the complexities of adversarial decision-making, guaranteeing convergence to an e-optimal solution in finite time.

What Problem Does This Paper Address?

Sequential decision-making problems, especially those involving uncertainty and multiple agents, are notoriously difficult to solve optimally. While heuristic search algorithms like A* and its variants have been successful in deterministic settings and single-agent stochastic problems (like Markov Decision Processes - MDPs), extending them to multi-agent scenarios, particularly adversarial ones like zero-sum stochastic games (zs-SGs), presents a significant challenge. In zs-SGs, each player has opposing objectives, making it crucial to consider both optimistic and pessimistic estimates of future outcomes. Existing methods for zs-SGs often rely on exact dynamic programming, which can be computationally prohibitive, or reinforcement learning, which may lack convergence guarantees. This paper aims to bridge this gap by developing a heuristic search algorithm that can efficiently find near-optimal strategies in these complex adversarial environments.

Methods

The core of this paper is the adaptation of the Heuristic Search Value Iteration (HSVI) algorithm to the domain of two-player, zero-sum stochastic games. The key innovation lies in how HSVI's single-agent optimistic approach is extended to handle the adversarial nature of zs-SGs.

  • Dual Heuristics: Instead of a single heuristic, the algorithm uses both a majorant (U) and a minorant (L) function. These represent optimistic and pessimistic bounds on the optimal value function, respectively.
  • Nash Equilibrium (NE) for Action Selection: In each state, the algorithm computes the Nash Equilibrium for two auxiliary games: one derived from the majorant (U) and another from the minorant (L). The players then select their actions based on these NEs, with Player 1 acting optimistically (guided by U) and Player 2 acting pessimistically (guided by L). This ensures that the algorithm considers the worst-case scenario for each player.
  • Trajectory Generation: Similar to HSVI, the algorithm generates trajectories by exploring the state space. The selection of the next state is guided by an "excess" function that prioritizes states where the gap between the majorant and minorant is largest, indicating areas of high uncertainty.
  • Point-Based Updates: The majorant and minorant functions are updated iteratively using point-based operators, focusing on states visited during trajectory generation.
  • Convergence Guarantees: The paper proves that this adapted algorithm converges to an e-optimal solution in finite time, building upon theoretical results from single-agent heuristic search.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Adversarial Optimism/Pessimism: The most crucial insight is the elegant extension of heuristic search to adversarial settings by employing dual heuristics (majorant and minorant) and deriving player actions from Nash Equilibria of auxiliary games. This allows the algorithm to maintain optimism for one player while simultaneously accounting for the other player's opposing objectives.
  • Nash Equilibrium as a Guiding Principle: Using NEs of Shapley matrix games derived from the bounds (U and L) provides a principled way to select actions in each state that are robust to the opponent's strategy.
  • Finite-Time Convergence in Adversarial Settings: Achieving finite-time convergence guarantees for heuristic search in zs-SGs is a significant theoretical contribution, as many existing methods struggle with this.
  • Importance of Initial Bounds: The paper highlights the necessity of initializing the majorant and minorant functions appropriately (e.g., using operators like GTRIV, GORAU, GMDPU) to ensure they are "uniformly improvable" and lead to convergence.

Key Results

The paper's primary result is the theoretical guarantee of convergence for the proposed heuristic search algorithm for two-player, zero-sum stochastic games. Specifically, the algorithm is proven to find an e-optimal solution in finite time. The paper also establishes that if the Nash Equilibrium values for the majorant and minorant games in a given state are equal, then this value is indeed the optimal value for that state in the zs-SG.

Limitations and Future Work

  • Computational Cost: While the algorithm guarantees convergence, the computation of Nash Equilibria for the auxiliary games at each step can be computationally expensive, especially for large state and action spaces.
  • Empirical Evaluation: The paper is primarily theoretical and lacks empirical validation. Implementing and evaluating the algorithm on benchmark zs-SGs is a crucial next step.
  • Generalization to Non-Zero-Sum Games: The current work is limited to zero-sum games. Extending it to general-sum games, where players' objectives are not strictly opposed, is a significant future direction.
  • Unattenuated Criteria: The current algorithm assumes discounted rewards. Adapting it to problems with non-attenuated criteria (infinite horizon without discounting) is another open question.
  • Partially Observable Stochastic Games (POSGs): A long-term goal is to extend this work to solve partially observable zs-SGs, which adds another layer of complexity due to incomplete information.
  • Other Heuristic Search Algorithms: Exploring the applicability of other heuristic search frameworks like LAO*, RTDP, and HDP to zs-SGs is also suggested.

Summary updated

Abstract

National audience
BibTeX
@inproceedings{buffet2018recherche,
  author = {Olivier Buffet and Jilles Dibangoye and Abdallah Saffidine and Vincent Thomas},
  title = {{Recherche heuristique pour jeux stochastiques (à somme nulle)}},
  booktitle = {JFPDA},
  year = {2018},
}
Figure