The Operator Approach to Entropy Games
Copyright policy )The Operator Approach to Entropy Games
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.
29 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
- French National Centre for Scientific Research France
- University of Paris France
- French Institute for Research in Computer Science and Automation France
- PSL Research University France
- Columbia University United States
risk sensitive control, FOS: Computer and information sciences, 330, Policy iteration, Miscellaneous applications of operator theory, Perron eigenvalues, 91A15, 47H05, 93E20, Computer Science - Computer Science and Game Theory, FOS: Mathematics, stochastic games, Mathematics - Optimization and Control, F.2.1 Numerical Algorithms and Problems, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Shapley operators, 2-person games, 004, policy iteration, Stochastic games, stochastic differential games, 1991 Mathematics Subject Classification. G.2.1 Combinatorial algorithms, Optimization and Control (math.OC), Probability distributions: general theory, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Stochastic games, Risk sensitive control, Computer Science and Game Theory (cs.GT), ddc: ddc:004
risk sensitive control, FOS: Computer and information sciences, 330, Policy iteration, Miscellaneous applications of operator theory, Perron eigenvalues, 91A15, 47H05, 93E20, Computer Science - Computer Science and Game Theory, FOS: Mathematics, stochastic games, Mathematics - Optimization and Control, F.2.1 Numerical Algorithms and Problems, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Shapley operators, 2-person games, 004, policy iteration, Stochastic games, stochastic differential games, 1991 Mathematics Subject Classification. G.2.1 Combinatorial algorithms, Optimization and Control (math.OC), Probability distributions: general theory, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Stochastic games, Risk sensitive control, Computer Science and Game Theory (cs.GT), ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).9 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!