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

• URL: http://arxiv.org/abs/2203.10142v2
• Date: Sun, 25 Aug 2024 01:00:49 GMT
• Title: Infinite-Horizon Reach-Avoid Zero-Sum Games via Deep Reinforcement Learning
• Abstract summary: 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. 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. We show that the proposed method could learn reliably the reach-avoid set and the optimal control policy even with neural network approximation.
• Score: 27.411127773300468
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Sparse Additive Off-Policy Evaluation for Reinforcement Learning with Potentially Limited Number of Trajectories [25.791211571263148]
  We develop a new framework for flexible, nonlinear, and interpretable off-policy evaluation for infinite-horizon reinforcement learning.<n>We derive high-probability finite-sample error bounds for estimating the value function of a target policy.
  arXiv  Detail & Related papers  (2026-08-23T21:02:55Z)
• Learning-Based Stochastic Optimal Control with Infinite-Horizon Probabilistic Constraints [9.67618824743514]
  We consider optimal control problems with infinite-horizon joint chance constraints.<n>We reformulate the original problem as a constrained Markov decision process.<n>We show that it converges to a deterministic Markov policy defined over the augmented state space.
  arXiv  Detail & Related papers  (2026-08-02T11:00:41Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• Certified Approximate Reachability (CARe): Formal Error Bounds on Deep Learning of Reachable Sets [45.67587657709892]
  We introduce an epsilon-approximate Hamilton-Jacobi Partial Differential Equation (HJ-PDE), which establishes a relationship between training loss and accuracy of the true reachable set. To the best of our knowledge, Certified Approximate Reachability (CARe) is the first approach to provide soundness guarantees on learned reachable sets of continuous dynamical systems.
  arXiv  Detail & Related papers  (2025-03-31T10:02:57Z)
• Resilient Constrained Reinforcement Learning [87.4374430686956]
  We study a class of constrained reinforcement learning (RL) problems in which multiple constraint specifications are not identified before study. It is challenging to identify appropriate constraint specifications due to the undefined trade-off between the reward training objective and the constraint satisfaction. We propose a new constrained RL approach that searches for policy and constraint specifications together.
  arXiv  Detail & Related papers  (2023-12-28T18:28:23Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria. We provide explicit convergence guarantees for both deterministic and deterministic environments.
  arXiv  Detail & Related papers  (2023-12-27T15:21:25Z)
• Convex Hulls of Reachable Sets [18.03395556436054]
  Reachable sets play a critical role in control, but remain notoriously challenging to compute. We characterize the convex hulls of reachable sets as the convex hulls of solutions of an ordinary differential equation with initial conditions on the sphere. This finite-dimensional characterization unlocks an efficient sampling-based estimation algorithm to accurately over-approximate reachable sets.
  arXiv  Detail & Related papers  (2023-03-30T19:31:41Z)
• A Quantum Optimal Control Problem with State Constrained Preserving Coherence [68.8204255655161]
  We consider a three-level $Lambda$-type atom subjected to Markovian decoherence characterized by non-unital decoherence channels. We formulate the quantum optimal control problem with state constraints where the decoherence level remains within a pre-defined bound.
  arXiv  Detail & Related papers  (2022-03-24T21:31:34Z)
• Failing with Grace: Learning Neural Network Controllers that are Boundedly Unsafe [18.34490939288318]
  We consider the problem of learning a feed-forward neural network (NN) controller to safely steer an arbitrarily shaped robot in a compact workspace. We propose an approach that lifts such assumptions on the data that are hard to satisfy in practice. We provide a simulation study that verifies the efficacy of the proposed scheme.
  arXiv  Detail & Related papers  (2021-06-22T15:51:52Z)
• Safe Learning of Uncertain Environments for Nonlinear Control-Affine Systems [10.918870296899245]
  We consider the problem of safe learning in nonlinear control-affine systems subject to unknown additive uncertainty. We model uncertainty as a Gaussian signal and use state measurements to learn its mean and covariance bounds. We show that with an arbitrarily large probability we can guarantee that the state will remain in the safe set, while learning and control are carried out simultaneously.
  arXiv  Detail & Related papers  (2021-03-02T01:58:02Z)
• Improper Learning with Gradient-based Policy Optimization [62.50997487685586]
  We consider an improper reinforcement learning setting where the learner is given M base controllers for an unknown Markov Decision Process. We propose a gradient-based approach that operates over a class of improper mixtures of the controllers.
  arXiv  Detail & Related papers  (2021-02-16T14:53:55Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Deep Constrained Q-learning [15.582910645906145]
  In many real world applications, reinforcement learning agents have to optimize multiple objectives while following certain rules or satisfying a set of constraints. We propose Constrained Q-learning, a novel off-policy reinforcement learning framework restricting the action space directly in the Q-update to learn the optimal Q-function for the induced constrained MDP and the corresponding safe policy.
  arXiv  Detail & Related papers  (2020-03-20T17:26:03Z)
• Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning [70.01650994156797]
  Off- evaluation of sequential decision policies from observational data is necessary in batch reinforcement learning such as education healthcare. We develop an approach that estimates the bounds of a given policy. We prove convergence to the sharp bounds as we collect more confounded data.
  arXiv  Detail & Related papers  (2020-02-11T16:18:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.