arXiv preprint ·
Stochastic Games with Distributional Entropy Objectives
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We introduce \emph{stochastic games with distributional entropy objectives}, two-player zero-sum games whose configurations are probability distributions over the states of a finite arena and whose stage reward is Shannon entropy. Over an infinite discounted horizon, MIN seeks to concentrate the distribution, while MAX seeks to disperse it. Because entropy is nonlinear, it matters whether strategic and transition randomness are averaged before entropy is evaluated or sampled first. We formalise three resulting semantics: averaged-distribution, sampled-profile, and sampled-transition. This semantic choice fundamentally changes the game-theoretic structure. Averaged-distribution games need not be determined, even on a four-state deterministic arena, whereas both sampled semantics are determined and admit optimal stationary randomised strategies. We give contractive Bellman characterisations and convergent finite-horizon approximations for the upper and lower averaged values and the two sampled values. Moreover, even the lower value under averaged-distribution semantics dominates the value under either sampled semantics, while the sampled-profile and sampled-transition values are incomparable in general. For fixed rational discount and positive rational promise gap, the averaged-distribution (upper and lower value) gap problems and both sampled gap problems lie in PSPACE; for a single entropy minimiser, the averaged and sampled-profile problems lie in NP. Finally, under all three semantics, entropy optimisation is NP-hard to approximate within a suitable fixed additive constant, already for deterministic one-player games, where pure memoryless strategies are optimal.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)
Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Differentiable Exact Learning
Tensorized Automata: Algebraically Informed Representation Learning for Sequential Decision Making
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.