# Infinite-Horizon Reach-Avoid Zero-Sum Games via Deep Reinforcement Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 18 Mar 2022.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Regularisation of Neural Networks by Enforcing Lipschitz Continuity](https://mlsanity.com/paper/1804.04368/) (2018)
- [Control Barrier Function Based Quadratic Programs for Safety Critical Systems](https://mlsanity.com/paper/1609.06408/) (2016)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Hamilton-Jacobi Reachability: A Brief Overview and Recent Advances](https://mlsanity.com/paper/1709.07523/) (2017)
- [DeepReach: A Deep Learning Approach to High-Dimensional Reachability](https://mlsanity.com/paper/2011.02082/) (2020)
- [Safety and Liveness Guarantees through Reach-Avoid Reinforcement Learning](https://mlsanity.com/paper/2112.12288/) (2021)
- [Reach-Avoid Problems with Time-Varying Dynamics, Targets and Constraints](https://mlsanity.com/paper/1410.6445/) (2014)
- [Decomposition of Reachable Sets and Tubes for a Class of Nonlinear Systems](https://mlsanity.com/paper/1611.00122/) (2016)
- [Robust Tracking with Model Mismatch for Fast and Safe Planning: an SOS Optimization Approach](https://mlsanity.com/paper/1808.00649/) (2018)
- [Underapproximation of Reach-Avoid Sets for Discrete-Time Stochastic Systems via Lagrangian Methods](https://mlsanity.com/paper/1704.03555/) (2017)
- [Reach-Avoid Problems via Sum-of-Squares Optimization and Dynamic Programming](https://mlsanity.com/paper/1807.11553/) (2018)
- [Exact and Efficient Hamilton-Jacobi-based Guaranteed Safety Analysis via System Decomposition](https://mlsanity.com/paper/1609.05248/) (2016)

## Built on by (most cited first, 6 of 6)

- [The Safety Filter: A Unified View of Safety-Critical Control in Autonomous Systems](https://mlsanity.com/paper/2309.05837/) (2023)
- [Safe Multi-Agent Reinforcement Learning with Convergence to Generalized Nash Equilibrium](https://mlsanity.com/paper/2411.15036/) (2024)
- [Do No Harm: A Counterfactual Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/2405.11669/) (2024)
- [Deep Reinforcement Learning for Reach-Avoid-Stay Problems](https://mlsanity.com/paper/2410.02898/) (2024)
- [Zero-Sum Positional Differential Games as a Framework for Robust Reinforcement Learning: Deep Q-Learning Approach](https://mlsanity.com/paper/2405.02044/) (2024)
- [A Safe Exploration Strategy for Model-free Task Adaptation in Safety-constrained Grid Environments](https://mlsanity.com/paper/2408.00997/) (2024)

## Abstract (arXiv)

In this paper, we consider the infinite-horizon reach-avoid zero-sum game problem, where the goal is to find a set in the state space, referred to as the reach-avoid set, such that the system starting at a state therein could be controlled to reach a given target set without violating constraints under the worst-case disturbance. We address this problem by designing a new value function with a contracting Bellman backup, where the super-zero level set, i.e., the set of states where the value function is evaluated to be non-negative, recovers the reach-avoid set. Building upon this, we prove that the proposed method can be adapted to compute the viability kernel, or the set of states which could be controlled to satisfy given constraints, and the backward reachable set, or the set of states that could be driven towards a given target set. Finally, we propose to alleviate the curse of dimensionality issue in high-dimensional problems by extending Conservative Q-Learning, a deep reinforcement learning technique, to learn a value function such that the super-zero level set of the learned value function serves as a (conservative) approximation to the reach-avoid set. Our theoretical and empirical results suggest that the proposed method could learn reliably the reach-avoid set and the optimal control policy even with neural network approximation.