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

DOI10.1016/J.AUTOMATICA.2021.109685zbMATH Open1478.91011arXiv2001.07889OpenAlexW3162477856MaRDI QIDQ2665331FDOQ2665331

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

Publication date: 19 November 2021

Published in: Automatica (Search for Journal in Brave)

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.

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)

Cites Work

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

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)