Entropic Risk for Turn-Based Stochastic Games

Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, Jakob Piribauer

Introduction

In the realm of stochastic modeling, such as Markov Decision Processes (MDPs) and Stochastic Games (SGs), the traditional objective is to maximize the expected total reward. While mathematically convenient, expectation-maximization is inherently risk-blind. An agent following such a strategy might pursue a high-payout path despite a significant probability of catastrophic failure. To address this, risk-aware objectives have been developed; however, many existing measures—like Conditional Value-at-Risk (CVaR)—introduce significant computational overhead, often requiring agents to utilize complex randomization or infinite memory.

This paper introduces Entropic Risk (ERisk) to turn-based stochastic games for the first time. ERisk provides a robust framework for modeling risk-averse behavior against an adversary while maintaining the computational simplicity of traditional objectives. Crucially, the authors demonstrate that ERisk allows for pure memoryless deterministic (MD) strategies, making it a highly attractive alternative for practical applications.

The Entropic Risk Objective

ERisk quantifies risk by applying an exponential utility function to rewards, effectively penalizing "bad" outcomes more heavily than "good" ones. The authors define ERisk as:

$$ERisk_\gamma(X) = -\frac{1}{\gamma} \log_b(\mathbb{E}[b^{-\gamma X}])$$

By exponentially re-weighting outcomes, ERisk provides a mathematically sound way to handle risk. The authors identify two primary hurdles in existing risk-aware research that ERisk helps overcome:

  1. Complexity: Most risk measures require agents to remember past states (memory) or use randomization to make optimal future decisions.
  2. Scope: Extending risk measures from single-agent MDPs to multi-agent SGs, where an adversary actively works against the agent, is mathematically non-trivial.

Methodology and Reductions

To analyze ERisk within the game-theoretic framework, the authors employ several innovative techniques to bridge the gap between risk-aversion and game solvability.

Reduction to Reachability

The authors prove that maximizing ERisk is equivalent to minimizing "Negative Exponential Utility" (NegUtil). They further show that finding the optimal ERisk value can be reduced to solving a reachability objective in a modified game. Although this reduction introduces irrational transition probabilities, it allows the researchers to leverage established tools from game theory to prove the existence of optimal values.

Complexity Frameworks

The "threshold problem"—deciding if an optimal value exceeds a specific target $t$—is analyzed through different mathematical lenses depending on the nature of the inputs:

  • Algebraic Cases: Handled using the existential theory of the reals ($\exists\mathbb{R}$).
  • General Cases: Addressed using Schanuel’s conjecture for transcendental instances.
  • Approximation: To manage the irrational numbers inherent in exponential functions, the authors developed a rounding technique to allow for efficient approximation within a desired precision ($\epsilon$).

Key Insights: Strategy and Consistency

The most significant finding of the paper is the simplicity of strategies. Despite the non-linear nature of the ERisk objective, the resulting games are determined and admit pure memoryless deterministic (MD) strategies. This means an agent only needs to know their current state to make an optimal choice, without needing to randomize or recall the history of the game. This is a major advantage over measures like CVaR, which often require infinite memory.

Furthermore, ERisk is time-consistent. Unlike many other risk measures, it is history-independent; an optimal move today remains optimal regardless of how much "luck" (good or bad) the agent experienced in previous turns.

Computational Results

The paper establishes a comprehensive complexity landscape for the ERisk threshold problem and value computation:

Problem Instance Threshold Problem Complexity Optimal Value Computation
Small Algebraic MDPs PTIME PTIME
Small Algebraic SGs NP ∩ coNP Polynomial Space
Algebraic SGs PSPACE (in $\exists\mathbb{R}$) PSPACE (approximation)
General SGs Decidable (subject to Schanuel's) PSPACE (approximation)

For small algebraic instances, ERisk sits in the same complexity class as standard reachability games, making it computationally tractable for many practical scenarios.

Conclusion and Future Directions

While this work provides a rigorous foundation for ERisk in stochastic games, several avenues for future research remain. The current proofs assume non-negative rewards ($r \ge 0$); extending this to include negative rewards presents a significant mathematical challenge, as the reduction to reachability games would no longer be straightforward. Additionally, the general decidability results rely on the unproven Schanuel’s conjecture from transcendental number theory. Finally, the authors suggest that future work should involve experimental evaluation to see how these algorithms perform on realistic, large-scale systems such as autonomous navigation or traffic optimization.

Summary updated

BibTeX
@article{baier2024entropic,
  author = {Christel Baier and Krishnendu Chatterjee and Tobias Meggendorfer and Jakob Piribauer},
  title = {{Entropic Risk for Turn-Based Stochastic Games}},
  journal = {Inf. Comput.},
  year = {2024},
  doi = {10.1016/j.ic.2024.105214},
}
Figure