mlsanityData to 14 Oct 2026

On the Uniqueness of Solution for the Bellman Equation of LTL Objectives

arXiv 2404.05074 ↗First posted 7 Apr 2024cs.AI cs.ROcited by 3

Not on the map. Why?

Abstract (arXiv)

Surrogate rewards for linear temporal logic (LTL) objectives are commonly utilized in planning problems for LTL objectives. In a widely-adopted surrogate reward approach, two discount factors are used to ensure that the expected return approximates the satisfaction probability of the LTL objective. The expected return then can be estimated by methods using the Bellman updates such as reinforcement learning. However, the uniqueness of the solution to the Bellman equation with two discount factors has not been explicitly discussed. We demonstrate with an example that when one of the discount factors is set to one, as allowed in many previous works, the Bellman equation may have multiple solutions, leading to inaccurate evaluation of the expected return. We then propose a condition for the Bellman equation to have the expected return as the unique solution, requiring the solutions for states inside a rejecting bottom strongly connected component (BSCC) to be 0. We prove this condition is sufficient by showing that the solutions for the states with discounting can be separated from those for the states without discounting under this condition

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 12 of its 25 references that are in the map. First posted on arXiv 7 Apr 2024.

Builds on

12 of 25 references.

References · 12

  1. 2016Reinforcement Learning With Temporal Logic Rewardscited by 117
  2. 2019Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guaranteescited by 77
  3. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 75
  4. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 75
  5. 2017Environment-Independent Task Specifications via GLTLcited by 67
  6. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 54
  7. 2014Verification of Markov Decision Processes using Learning Algorithmscited by 39
  8. 2021Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logiccited by 39
  9. 2019Certified Reinforcement Learning with Logic Guidancecited by 36
  10. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 32
  11. 2019Temporal Logic Guided Safe Reinforcement Learning Using Control Barrier Functionscited by 21
  12. 2023Eventual Discounting Temporal Logic Counterfactual Experience Replaycited by 19

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2024Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Explorationcited by 5
  2. 2025Accelerated Learning with Linear Temporal Logic using Differentiable Simulationcited by 1
  3. 2025Is Bellman Equation Enough for Learning Control?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards
  2. 2024Directed Exploration in Reinforcement Learning from Linear Temporal Logic
  3. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
  4. 2025Dual-Objective Reinforcement Learning with Novel Hamilton-Jacobi-Bellman Formulations
  5. 2026Exact Model-Free Policy Iteration for Co-safe LTL Planning
  6. 2026Generalised Bellman recurrence and three dualities in sequential decision-making
  7. 2025Theoretical Barriers in Bellman-Based Reinforcement Learning
  8. 2024LTL-Constrained Policy Optimization with Cycle Experience Replay