Affordable Access

Bounding Fixed Points of Set-based Bellman Operator and Nash Equilibria of Stochastic Games

Authors
  • Li, Sarah
  • Adjé, Assalé
  • Garoche, Pierre-Loïc
  • Açıkmeşe, Behçet
Publication Date
Apr 01, 2021
Source
HAL
Keywords
Language
English
License
Unknown
External links

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.

Report this publication

Statistics

Seen <100 times