Bounding fixed points of set-based Bellman operator and Nash equilibria of stochastic games. (August 2021)

• Record Type: Journal Article
• Authors: Li, Sarah H.Q.; Adjé, Assalé; Garoche, Pierre-Loïc; Açıkmeşe, Behçet
• Is Part Of: Automatica. Volume 130(2021)
• Publication Date: 2021-08
• Subjects: Markov decision process -- Learning theory -- Stochastic control -- Multi-agent systems -- Learning in games -- Decision making and autonomy; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2021.109685
• Languages: English
• ISSNs: 0005-1098

Abstract

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 the operator 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.