# Zero-sum turn games using Q-learning: finite computation with security guarantees

arXiv: https://arxiv.org/abs/2509.13585 · HTML: https://mlsanity.com/paper/2509.13585/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 5 of 5)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Feature-Based Q-Learning for Two-Player Stochastic Games](https://mlsanity.com/paper/1906.00423/) (2019)
- [On Reinforcement Learning for Turn-based Zero-sum Markov Games](https://mlsanity.com/paper/2002.10620/) (2020)

## Abstract (arXiv)

This paper addresses zero-sum ``turn'' games, in which only one player can make decisions at each state. We show that pure saddle-point state-feedback policies for turn games can be constructed from dynamic programming fixed-point equations for a single value function or Q-function. These fixed-points can be constructed using a suitable form of Q-learning. For discounted costs, convergence of this form of Q-learning can be established using classical techniques. For undiscounted costs, we provide a convergence result that applies to finite-time deterministic games, which we use to illustrate our results. For complex games, the Q-learning iteration must be terminated before exploring the full-state, which can lead to policies that cannot guarantee the security levels implied by the final Q-function. To mitigate this, we propose an ``opponent-informed'' exploration policy for selecting the Q-learning samples. This form of exploration can guarantee that the final Q-function provides security levels that hold, at least, against a given set of policies. A numerical demonstration for a multi-agent game, Atlatl, indicates the effectiveness of these methods.