A Generalized Minimax Q-Learning Algorithm for Two-Player Zero-Sum Stochastic Games
From MaRDI portal
Abstract: We consider the problem of two-player zero-sum games. This problem is formulated as a min-max Markov game in the literature. The solution of this game, which is the min-max payoff, starting from a given state is called the min-max value of the state. In this work, we compute the solution of the two-player zero-sum game utilizing the technique of successive relaxation that has been successfully applied in the literature to compute a faster value iteration algorithm in the context of Markov Decision Processes. We extend the concept of successive relaxation to the setting of two-player zero-sum games. We show that, under a special structure on the game, this technique facilitates faster computation of the min-max value of the states. We then derive a generalized minimax Q-learning algorithm that computes the optimal policy when the model information is not known. Finally, we prove the convergence of the proposed generalized minimax Q-learning algorithm utilizing stochastic approximation techniques, under an assumption on the boundedness of iterates. Through experiments, we demonstrate the effectiveness of our proposed algorithm.
Cited in
(4)- Learning Algorithms for Two-Person Zero-Sum Stochastic Games with Incomplete Information
- A note on generalized second-order value iteration in Markov decision processes
- Decision-making problem for two-player Markov game: perspective of feedback control
- Optimal finite-horizon tracking control in affine nonlinear systems: a Stackelberg game approach with H₂/H_ framework
This page was built for publication: A Generalized Minimax Q-Learning Algorithm for Two-Player Zero-Sum Stochastic Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076027)
