Competitive Markov decision processes
Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Markov and semi-Markov decision processes (90C40) Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02) Stochastic games, stochastic differential games (91A15)
Under the curious making attribut ``competitive, Markov decision processes (MDP) are considered in which two decision makers compete against one another: Markov games as they have named it firstly by Zachrisson (1964). Although originally considered by Shapley already in 1953 -- usual MDP only in 1957 by Bellman -- these two problem classes widely had been treated independently of each other. Meanwhile hundreds of papers dispersedly have been appeared, summarized to survey papers again. Already since 1987 it was a challenge for the authors to create a textbook on this matter. The intention that already mathematically ripe pupils, all the more students and research workers can understand the book and that it can build a bridge between mathematicians, operations researchers, engineers and game theoreticians, is well succeeded. It could succeed only in that the authors restricted themselves on that case being of interest to the majority of readers: Discrete time, finite state space, finite action spaces and perfect information. Some more difficult sections are marked by an asterisk. The book satisfies also the specialist by a competent treatment of problems and tools for their solution as Bellman's principle, Tauberian theorems and Puiseux series. The book is conspiciuously realized for its mathematical exactness and its vivid language. The list of references restricts itself to only 102 items and takes only those sources into account which evidently have been used for preparation of the text. The symbolism used is especially chosen by the authors, mnemotechnically simple to understand and pleasant. Also the popular box representation with diagonal divider is used. After the introductory chapter, the two major parts I ``Mathematical Programming Perspective (Chapters 2 and 3), II ``Existence, Structure and Application (Chapters 4-6) and four very useful appendices (on (bi)matrix games, Hardy-Littlewood theorem, Markov chains and Puiseux series, resp.) follow. Each of the Chapters 2-6 closes with bibliographic notes. Then the serious reader will be challenged by a greater number of high-level exercises, also for modelling of engineering applications by the given theory. The noncompetitive case in Chapter 2 as a special case of the competitive one are MDP in strict sense. Here the reader will find all interesting things on it, summarized in textbook style. Summable MDP are those whose total reward is summable. This class comprehends the discounted, the terminating case and finite horizon. The limiting average process (LAP) will be brought into opposition to the former and connections between these two are showed. Linear programming (LP) as the main tool for solution is treated under some assumptions. Different strategy classes (deterministic, stationary, Markov, behavioral) are compared. The policy improvement method is also treated. The optimization aspect of stochastic games is considered in Chapter 3. The known fact is shown to the reader that LP fails already in simple examples. Greater subclasses of games (single controller, SER-SIT, switching controller) are presented in which it is possible to use LP for solution. Also the LAP is treated in detail, known by the Big match as an example. A description of typical techniques of nonlinear programming follows. Chapter 4 comprehends a refined analysis of summable games. Existence theorems of optimal strategies within specified strategy classes are emphasized here. In all but the last sections, zero-sum games are considered. Section 4.1 is a repetition of the foregoing matter for reading Part II independently. Also the notion of total reward optimality is treated and a reformulation of it as an LAP is undertaken. The final section 4.6 is devoted to non-zero-sum games, they are solved by complementarity problems and by a classification of equilibrium points. The structure of Chapter 5 is similar to that of Chapter 4. Many new results from the last decade were composed. Finally, for a special treatment of those classes of games which possess the orderfield property, Chapter 6 is dedicated. This property has proved to play a central role because it is possible to solve such games in a finite number of steps. In the presentation, a point is made of that these classes are not artificially created but immediately result under modelling of economic and engineering processes. Taking the authors' conception of the book into account, under today's state-of-the-art, all essential aspects of stochastic games have been treated and this in a brilliant way. No serious mistake has been found. To a broad group of readers, the book warmly can recommanded for studying stochastic games.
- Competing Markov decision processes
- A multicriteria competitive Markov decision process
- Continuity of the value of competitive Markov decision processes
- Markov decision processes
- MARKOV DECISION PROCESSES
- scientific article; zbMATH DE number 4154239
- scientific article; zbMATH DE number 420890
- Markov decision processes
- Bidding games on Markov decision processes
- Pure equilibria in a simple dynamic model of strategic market game
- Two-person second-order games. I: Formulation and transition anatomy
- On asymptotic optimization of a class of nonlinear stochastic hybrid systems
- Indices for families of competing Markov decision processes with influence
- Markov games with incomplete information
- A multicriteria competitive Markov decision process
- Multiagent learning using a variable learning rate
- Zero-sum discounted reward criterion games for piecewise deterministic Markov processes
- An abstraction-refinement methodology for reasoning about network games
- Tropically convex constraint satisfaction
- A stochastic game approach to the security issue of networked control systems under jamming attacks
- On discounted stochastic games with incomplete information on payoffs and a security application
- A characterization of stationary Nash equilibria of constrained stochastic games with independent state processes
- Robust optimal strategies in Markov decision problems
- Approximate counting in SMT and value estimation for probabilistic programs
- Completely mixed strategies for generalized bimatrix and switching controller stochastic game
- Approachability in Stackelberg stochastic games with vector costs
- Nonzero-sum risk-sensitive finite-horizon continuous-time stochastic games
- Computation of weighted sums of rewards for concurrent MDPs
- The complexity of synchronizing Markov decision processes
- Approximation of discounted minimax Markov control problems and zero-sum Markov games using Hausdorff and Wasserstein distances
- Zero-sum Markov games with random state-actions-dependent discount factors: existence of optimal strategies
- Continuous-time constrained stochastic games under the discounted cost criteria
- Advances in dynamic games. Applications to economics, finance, optimization and stochastic control.
- A nonzero-sum stochastic differential game in the orthant
- Rationality and bounded information in repeated games, with application to the iterated prisoner's dilemma
- Constrained stochastic games with the average payoff criteria
- Spectral theorem for convex monotone homogeneous maps, and ergodic control
- Quantitative solution of omega-regular games
- Stochastic methods based on Newton method to the stochastic variational inequality problem with constraint conditions
- Cooperative Markov decision processes: time consistency, greedy players satisfaction, and cooperation maintenance
- Nonzero-sum games for continuous-time jump processes under the expected average payoff criterion
- A note on the Nash equilibria of some multi-player reachability/safety games
- Some game-theoretic remarks on two-player generalized cops and robbers games
- Nonzero-sum risk-sensitive average stochastic games: The case of unbounded costs
- Solving possibilistic games with incomplete information
- On completely mixed stochastic games
- Multi-agent reinforcement learning: a selective overview of theories and algorithms
- A game-theoretic approach for the synthesis of complex systems
- Comparison of algorithms for simple stochastic games
- Zero-sum semi-Markov games with state-action-dependent discount factors
- A nonzero-sum risk-sensitive stochastic differential game in the orthant
- Discounted stochastic games for continuous-time jump processes with an uncountable state space
- Existence of equilibrium strategies in fuzzy stochastic games with finite sets of states and decisions
- Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
- Algorithms and conditional lower bounds for planning problems
- Code aware resource management
- Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives
- Automatic verification of competitive stochastic systems
- Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
- Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs
- A survey on the relationship between the game of cops and robbers and other game representations
- Risk-sensitive average equilibria for discrete-time stochastic games
- Optimizing over pure stationary equilibria in consensus stopping games
- Generalized cops and robbers: a multi-player pursuit game on graphs
- Deciding probabilistic bisimilarity distance one for probabilistic automata
- A non-iterative algorithm for generalized pig games
- Stochastic approximations of constrained discounted Markov decision processes
- A multiscale decision theory analysis for revenue sharing in three-stage supply chains
- POMDPs under probabilistic semantics
- Qualitative analysis of concurrent mean-payoff games
- Looking at mean-payoff and total-payoff through windows
- Online calibrated forecasts: memory efficiency versus universality for learning in games
- Zero-sum continuous-time Markov pure jump game over a fixed duration
- Symblicit algorithms for mean-payoff and shortest path in monotonic Markov decision processes
- Average-energy games
- Recursive stochastic games with positive rewards
- An epistemic approach to stochastic games
- Orderfield property of mixtures of stochastic games
- Average optimality for risk-sensitive control with general state space
- Concurrent games with tail objectives
- Concurrent reachability games
- On stochastic games in economics
- A note on two-person zero-sum communicating stochastic games
- SPAR: Stochastic Programming with Adversarial Recourse
- Service rate control of closed Jackson networks from game theoretic perspective
- Optimal cost almost-sure reachability in POMDPs
- A leader-follower partially observed, multiobjective Markov game
- Model checking discounted temporal properties
- Competing Markov decision processes
- Bounding fixed points of set-based Bellman operator and Nash equilibria of stochastic games
- Two-person zero-sum stochastic games with varying discount factors
- Graph planning with expected finite horizon
- What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
- STRONG AVERAGE OPTIMALITY FOR CONTROLLED NONHOMOGENEOUS MARKOV CHAINS*
- Expected reachability-time games
- Recursive Markov decision processes and recursive stochastic games
- Uniqueness of the fixed point of nonexpansive semidifferentiable maps
- A finite exact algorithm to solve a dice game
- Qualitative analysis of VASS-induced MDPs
- Primary user emulation attack game in cognitive radio networks: queuing aware dogfight in spectrum
- The expected total cost criterion for Markov decision processes under constraints
- Nonzero-sum constrained discrete-time Markov games: the case of unbounded costs
- Tropical polyhedra are equivalent to mean payoff games
- Discounting and averaging in games across time scales
- Blackwell optimal strategies in priority mean-payoff games
- On memoryless quantitative objectives
- Equational weighted tree transformations with discounting
- Robust shortest path planning and semicontractive dynamic programming
- Graph Games and Reactive Synthesis
This page was built for publication: Competitive Markov decision processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382287)
