Bounding fixed points of set-based Bellman operator and Nash equilibria of stochastic games

DOI10.1016/J.AUTOMATICA.2021.109685MaRDI QIDQ2665331zbMATH OpenOpenAlexFDO

Authors Sarah H. Q. Li, Assalé Adjé, Pierre-Loïc Garoche, Behçet Açıkmeşe

Publication date 19 November 2021

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.07889

zbMATH Keywords

learning theoryMarkov decision processmulti-agent systemsstochastic controllearning in gamesdecision making and autonomy

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40) Stochastic games, stochastic differential games (91A15) Stochastic systems in control theory (general) (93E03) Rationality and learning in game theory (91A26) Multi-agent systems (93A16)

Abstract: Motivated by uncertain parameters encountered in Markov decision processes (MDPs) and stochastic games, we study the effect of parameter uncertainty on Bellman operator-based algorithms under a set-based framework. Specifically, we first consider a family of MDPs where the cost parameters are in a given compact set; we then define a Bellman operator acting on a set of value functions to produce a new set of value functions as the output under all possible variations in the cost parameter. We prove the existence of a fixed point of this set-based Bellman operator by showing that it is contractive on a complete metric space, and explore its relationship with the corresponding family of MDPs and stochastic games. Additionally, we show that given interval set bounded cost parameters, we can form exact bounds on the set of optimal value functions. Finally, we utilize our results to bound the value function trajectory of a player in a stochastic game.

Recommendations

• An operator solution of stochastic games
• Nash \(\epsilon\)-equilibria for stochastic games with total reward functions: an approach through Markov decision processes.
• Stochastic Shortest Path Games
• scientific article; zbMATH DE number 1507320
• Bounded Parameter Markov Decision Processes with Average Reward Criterion

Cites work

• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 3238721 (Why is no real title available?)
• scientific article; zbMATH DE number 3281219 (Why is no real title available?)
• 10.1162/1532443041827880
• Bounded-parameter Markov decision processes
• Computer Science Logic
• Controlled Markov Processes With Safety State Constraints
• Flow control using the theory of zero sum Markov games
• Game-theoretic goal recognition models with applications to security domains
• Interval iteration algorithm for MDPs and IMDPs
• Markov chain approach to probabilistic guidance for swarms of autonomous agents
• Percentile Optimization for Markov Decision Processes with Parameter Uncertainty
• Perturbation and stability theory for Markov control problems
• Robust Dynamic Programming
• Robust Markov Decision Processes
• Singulary perturbed Markov control problem: Limiting average cost
• Stability and singular perturbations in constrained Markov decision problems
• Stochastic Games

Cited in

(2)

• A switching control strategy for policy selection in stochastic dynamic programming problems
• Set-based value operators for non-stationary and uncertain Markov decision processes

This page was built for publication: Bounding fixed points of set-based Bellman operator and Nash equilibria of stochastic games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2665331)