[Paper] Relu and softplus neural nets as zero-sum turn-based games

Source: arXiv - 2512.20582v1

Overview

The paper by Gaubert and Vlassopoulos reveals a surprising bridge between two seemingly unrelated worlds: deep learning with ReLU (and Softplus) activations and classic zero‑sum turn‑based games. By interpreting a neural‑network forward pass as the solution of a backward‑recursion game, the authors open up new ways to analyze, certify, and even train networks using game‑theoretic tools.

Key Contributions

• Game‑theoretic reinterpretation: Shows that evaluating a ReLU network is equivalent to solving a zero‑sum, turn‑based stopping game (the “ReLU net game”).
• Shapley‑Bellman recursion: Demonstrates that the network output can be obtained by a backward recursion identical to the Shapley operator used in dynamic programming.
• Path‑integral (Feynman‑Kac) formula: Derives a discrete stochastic representation of the network output as an expected total payoff over game trajectories.
• Robustness certificates: Leverages monotonicity of Shapley operators to bound network outputs from input bounds, providing a new method for robustness verification.
• Inverse game training: Casts network training as an inverse problem—recovering game transition probabilities and rewards that reproduce observed input‑output pairs.
• Extension to Softplus: Generalizes the framework to Softplus activations via an entropic regularization of the ReLU game.

Methodology

1. Backward game construction: Starting from the network’s output layer, the authors walk backwards through each hidden layer. At each node they define a two‑player turn: the “max” player chooses a ReLU activation (i.e., whether the neuron is active), while the “min” player selects a linear continuation. This yields a zero‑sum game whose terminal payoff is the original input vector.
2. Shapley operator mapping: Each layer’s affine transformation followed by ReLU is mapped to a Shapley operator—a max‑min update rule familiar from stochastic games. Repeated application of these operators reproduces the forward pass.
3. Path‑integral representation: By fixing optimal policies for both players, the game induces a Markovian transition kernel. The network output becomes the expected sum of stage rewards along a random trajectory, analogous to the Feynman‑Kac formula in physics.
4. Robustness analysis: Because Shapley operators are monotone, any known bounds on the input (e.g., an ℓ∞ ball around a data point) propagate to provable bounds on the output without enumerating all possible perturbations.
5. Inverse problem for training: Given a dataset of (input, desired output) pairs, the authors formulate a convex optimization that finds game parameters (transition probabilities, stage rewards) whose induced Shapley recursion matches the data, effectively “training” the network via game synthesis.
6. Softplus extension: Replacing the hard max of ReLU with a softmax‑type smoothing yields an entropically regularized game, preserving the same structural insights while handling smooth activations.

Results & Findings

• Exact equivalence: The authors prove mathematically that for any feed‑forward ReLU network, the forward evaluation equals the value of the constructed zero‑sum game.
• Path‑integral formula: They provide an explicit discrete Feynman‑Kac expression, enabling Monte‑Carlo style estimations of network outputs and gradients.
• Robustness bounds: Using simple input interval bounds, they derive output intervals that are provably tight for several benchmark networks, outperforming naive Lipschitz‑based estimates.
• Training as inverse game: Experiments on synthetic data show that solving the inverse game problem recovers network parameters that match the original network’s behavior, confirming the feasibility of the approach.
• Softplus regularization: The entropic version retains the game‑theoretic structure and yields smoother value functions, suggesting a principled way to handle non‑piecewise linear activations.

Practical Implications

• Verification tools: Developers can embed the Shapley‑operator based bound computation into safety‑critical pipelines (e.g., autonomous driving) to certify that small input perturbations cannot cause large output swings.
• Explainability: The optimal policies of the two players act as certificates that explain which neurons (or paths) dominate a particular prediction, offering a game‑theoretic lens for interpretability.
• Robust training: By framing training as an inverse game, one can incorporate robustness constraints directly into the optimization (e.g., enforce transition probabilities that limit worst‑case payoffs).
• Monte‑Carlo inference: The path‑integral representation enables stochastic sampling methods for estimating network outputs and gradients, potentially useful for large‑scale models where exact backpropagation is costly.
• Extension to other activations: The Softplus result hints that many modern activations (Swish, GELU) might admit similar entropic game formulations, opening a research avenue for unified analysis across architectures.

Limitations & Future Work

• Scalability: Constructing and storing the full game transition matrix grows exponentially with network width, so practical implementations will need clever approximations or sparsity exploitation.
• Policy computation: Finding optimal policies for large networks may be computationally intensive; the paper relies on theoretical existence rather than efficient algorithms.
• Empirical validation: Experiments are limited to small synthetic networks; applying the framework to state‑of‑the‑art deep models (e.g., ResNets) remains an open challenge.
• Extension to other architectures: Convolutional, recurrent, or attention‑based layers are not covered; adapting the game‑theoretic view to these structures is a promising direction.
• Robustness tightness: While bounds improve over naive Lipschitz estimates, they may still be conservative for highly non‑linear regions; tighter certificates could be explored via refined game policies.

---

Bottom line: By recasting ReLU (and Softplus) networks as zero‑sum turn‑based games, Gaubert and Vlassopoulos provide a fresh analytical toolkit that blends dynamic programming, stochastic processes, and deep learning. For developers focused on model reliability, interpretability, and novel training regimes, this game‑theoretic perspective opens up concrete, albeit still nascent, pathways to more robust AI systems.

Authors

• Stephane Gaubert
• Yiannis Vlassopoulos

Paper Information

• arXiv ID: 2512.20582v1
• Categories: cs.LG, cs.GT, math.OC
• Published: December 23, 2025
• PDF: Download PDF