Optimal Constrained sc-LTL Planning in MDPs via Switching Policies

• URL: http://arxiv.org/abs/2608.05021v1
• Date: Wed, 05 Aug 2026 16:24:54 GMT
• Title: Optimal Constrained sc-LTL Planning in MDPs via Switching Policies
• Abstract summary: We study the synthesis of optimal policies for planning problems on Markov decision processes with both objectives and safety constraints specified in co-safe linear temporal logic (sc-LTL)<n>Our problems are inherently non-Markovian due to the complexity of the sc-LTL specification and may require policy randomization to balance the objective and constraint.<n>A grid world case study demonstrates that our switching policies can achieve the optimal trade-off between the objective and the safety constraint and validates both optimality and tractability.
• Score: 2.5735476569508995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the synthesis of optimal policies for planning problems on Markov decision processes with both objectives and safety constraints specified in co-safe linear temporal logic (sc-LTL). Our problems are inherently non-Markovian due to the complexity of the sc-LTL specification and may require policy randomization to balance the objective and constraint. We propose a novel approach that reduces the constrained sc-LTL planning problem to a constrained reachability problem on an extended model. We then show that a class of switching policies constructed from stationary policies for the individual sc-LTL specifications is sufficient for optimality for the constrained reachability problem. Our finding enables a tractable linear program to compute the optimal policy. A grid world case study demonstrates that our switching policies can achieve the optimal trade-off between the objective and the safety constraint and validates both optimality and tractability.

Related papers

• Exact Model-Free Policy Iteration for Co-safe LTL Planning [2.5735476569508995]
  This work studies model-free reinforcement learning for co-safe linear temporal logic objectives in finite Markov decision processes.<n>We develop a new two-step model-free reinforcement learning method that first uses a discounted surrogate to identify a clamp set.<n>We prove almost-sure convergence of the policy evaluation step and finite termination of the policy iteration algorithm at an optimal policy.
  arXiv  Detail & Related papers  (2026-08-05T16:58:25Z)
• Feasibility Restoration under Conflicting STL Specifications with Pareto-Optimal Refinement [18.383508411056944]
  Signal Temporal Logic (STL) is expressive language that specifies expressive requirements in robotics.<n>STL specifications may become conflicting in real-world applications, where safety rules, traffic regulations, task and objectives can be cannot be satisfied together.<n>We propose a unified two-stage framework that first restores feasibility via minimal relaxation, then refine the feasible solution by formulating it as a value-aware multi-objective optimization problem.
  arXiv  Detail & Related papers  (2026-03-06T23:41:01Z)
• 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)
• Alignment of large language models with constrained learning [93.2264691508005]
  We study the problem of computing an optimal large language model (LLM) policy for a constrained alignment problem.<n>We employ Lagrangian duality to develop an iterative dual-based alignment method that alternates between updating the policy via Lagrangian and updating a dual variable via dual descent.
  arXiv  Detail & Related papers  (2025-05-26T01:04:56Z)
• 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)
• Constrained Decision Transformer for Offline Safe Reinforcement Learning [16.485325576173427]
  We study the offline safe RL problem from a novel multi-objective optimization perspective. We propose the constrained decision transformer (CDT) approach, which can dynamically adjust the trade-offs during deployment.
  arXiv  Detail & Related papers  (2023-02-14T21:27:10Z)
• Policy Optimization with Linear Temporal Logic Constraints [37.27882290236194]
  We study the problem of policy optimization with linear temporal logic constraints. We develop a model-based approach that enjoys a sample complexity analysis for guaranteeing both task satisfaction and cost optimality.
  arXiv  Detail & Related papers  (2022-06-20T02:58:02Z)
• COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimation [73.17078343706909]
  offline constrained reinforcement learning (RL) problem, in which the agent aims to compute a policy that maximizes expected return while satisfying given cost constraints, learning only from a pre-collected dataset. We present an offline constrained RL algorithm that optimize the policy in the space of the stationary distribution. Our algorithm, COptiDICE, directly estimates the stationary distribution corrections of the optimal policy with respect to returns, while constraining the cost upper bound, with the goal of yielding a cost-conservative policy for actual constraint satisfaction.
  arXiv  Detail & Related papers  (2022-04-19T15:55:47Z)
• Model-Free Reinforcement Learning for Optimal Control of MarkovDecision Processes Under Signal Temporal Logic Specifications [7.842869080999489]
  We present a model-free reinforcement learning algorithm to find an optimal policy for a finite-horizon Markov decision process. We illustrate the effectiveness of our approach in the context of robotic motion planning for complex missions under uncertainty and performance objectives.
  arXiv  Detail & Related papers  (2021-09-27T22:44:55Z)
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
  In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward and avoids violation of certain constraints. This is the first-time analysis of SRL algorithms with global optimal policies.
  arXiv  Detail & Related papers  (2020-11-11T16:05:14Z)
• Guided Constrained Policy Optimization for Dynamic Quadrupedal Robot Locomotion [78.46388769788405]
  We introduce guided constrained policy optimization (GCPO), an RL framework based upon our implementation of constrained policy optimization (CPPO) We show that guided constrained RL offers faster convergence close to the desired optimum resulting in an optimal, yet physically feasible, robotic control behavior without the need for precise reward function tuning.
  arXiv  Detail & Related papers  (2020-02-22T10:15:53Z)

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.