The operator approach to entropy games

Abstract

Entropy games and matrix multiplication games have been recently introduced by Asarin et al. They model the situation in which one player (Despot) wishes to minimize the growth rate of a matrix product, whereas the other player (Tribune) wishes to maximize it. We develop an operator approach to entropy games. This allows us to show that entropy games can be cast as stochastic mean payoff games in which some action spaces are simplices and payments are given by a relative entropy (Kullback-Leibler divergence). In this way, we show that entropy games with a fixed number of states belonging to Despot can be solved in polynomial time. This approach also allows us to solve these games by a policy iteration algorithm, which we compare with the spectral simplex algorithm developed by Protasov.

arXiv comment29 pages. This is an extended version of the article with the same title and authors published in the Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Leibniz International Proceedings in Informatics (LIPIcs), volume 66, pages 6:1--6:14, 2017

References in corpus (6)

• A maximin characterization of the escape rate of nonexpansive mappings in metrically convex spaces
• Definable zero-sum stochastic games
• Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
• A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
• Entropy Games and Matrix Multiplication Games
• Hourglass alternative and the finiteness conjecture for the spectral characteristics of sets of non-negative matrices

Cited by in corpus (14)

• Polyconvex anisotropic hyperelasticity with neural networks
• A Tropical Approach to Neural Networks with Piecewise Linear Activations
• Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area
• Some open questions on morphological operators and representations in the deep learning era
• Tropical Polynomial Division and Neural Networks
• Accurate Computation of the Log-Sum-Exp and Softmax Functions
• Differentiating through Log-Log Convex Programs
• Parameterized Convex Universal Approximators for Decision-Making Problems
• Gradient Networks
• Advances in the training, pruning and enforcement of shape constraints of Morphological Neural Networks using Tropical Algebra
• Tropical Geometry and Piecewise-Linear Approximation of Curves and Surfaces on Weighted Lattices
• Min-Max-Plus Neural Networks
• Disciplined Geometric Programming
• Stabilising the Metzler matrices with applications to dynamical systems