Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives

• URL: http://arxiv.org/abs/2605.12581v1
• Date: Tue, 12 May 2026 15:46:35 GMT
• Title: Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives
• Abstract summary: Linear Temporal Logic (LTL) provides a rigorous language for specifying such tasks.<n>In this paper, we bridge this gap with a novel, sound reward-shaping mechanism.<n>By integrating this mechanism into an enhanced Monte Carlo Planning framework, we empower agents to navigate the fog' of partial observability.
• Score: 9.094127664014627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Synthesising autonomous agents that can navigate uncertain environments while adhering to complex temporal constraints remains a fundamental challenge. While Linear Temporal Logic (LTL) provides a rigorous language for specifying such tasks, the inherent undecidability of qualitatively verifying LTL satisfaction in partially observable Markov decision processes renders quantitative synthesis difficult, especially when designing reliable reward signals for approximate solvers. In this paper, we bridge this gap with a novel, sound reward-shaping mechanism that dynamically generates belief-dependent rewards grounded in certified LTL satisfaction. By integrating this mechanism into an enhanced Monte Carlo Planning framework, we empower agents to navigate the `fog' of partial observability with a search process focused on maximising verifiable success. Our experiments demonstrate that this approach not only thrives in scenarios where existing solvers fail but also maintains effectiveness and scalability across diverse benchmark domains.

Related papers

• Causal Reward World Models: Zero-shot Reward Design for Automated Skill Generation [23.371552518874807]
  Automated Reward Design (ARD) aims to replace manual reward engineering in reinforcement learning with language-driven reward function synthesis.<n>Existing approaches based on large language models (LLMs) remain inherently correlation-driven, relying on iterative environmental feedback to refine reward hypotheses for each specific task.<n>We propose the Causal Reward World Model (CRWM), which explicitly models the causal relationships between candidate reward components and task-targeted physical variables through offline pre-training on multi-task interaction data.
  arXiv  Detail & Related papers  (2026-06-22T12:57:17Z)
• HyperLens: Quantifying Cognitive Effort in LLMs with Fine-grained Confidence Trajectory [10.351595331564353]
  We identify an intrinsic magnification mechanism in transformer architectures.<n>We introduce HyperLens, a high-resolution probe designed to trace confidence trajectories.<n>Across datasets, HyperLens reveals a consistent divergence in confidence trajectories that separates complex from simple tasks.
  arXiv  Detail & Related papers  (2026-05-07T06:32:57Z)
• Understanding by Reconstruction: Reversing the Software Development Process for LLM Pretraining [66.89012795621349]
  Large Language Models (LLMs) often struggle with the deep, long-horizon reasoning required for complex software engineering.<n>We propose a novel paradigm: understanding via reconstruction.<n>We introduce a framework that synthesizes latent agentic trajectories using a multi-agent simulation.
  arXiv  Detail & Related papers  (2026-03-11T09:23:20Z)
• daVinci-Agency: Unlocking Long-Horizon Agency Data-Efficiently [35.39097522391409]
  Large Language Models (LLMs) excel at short-term tasks, scaling them to long-horizon agentic synthesis remains challenging.<n>We propose daVinci-Agency, which systematically mines structured supervision from chain-of-PRs.<n>DaVinci-Agency's PR-grounded structure inherently preserves the causal dependencies and iterative refinements essential for teaching persistent goal-cycle behavior.
  arXiv  Detail & Related papers  (2026-02-02T13:23:39Z)
• Discovering Process-Outcome Credit in Multi-Step LLM Reasoning [3.584086358722852]
  Reinforcement Learning (RL) serves as a potent paradigm for enhancing reasoning capabilities in Large Language Models (LLMs)<n>We propose a novel framework designed to provide continuous reward signals.<n>Our model exhibits superior out-of-distribution robustness, demonstrating promising zero-shot transfer capabilities to unseen and challenging reasoning tasks.
  arXiv  Detail & Related papers  (2026-02-01T05:44:09Z)
• Rectifying LLM Thought from Lens of Optimization [48.98086817378953]
  Long chain-of-thought (CoT) prompting enables thorough exploration and deliberation.<n>Despite advances, long-CoT LLMs often exhibit suboptimal reasoning behaviors.<n>We introduce RePro, a novel approach to refine LLM reasoning during post-training.
  arXiv  Detail & Related papers  (2025-12-01T17:41:08Z)
• A Fano-Style Accuracy Upper Bound for LLM Single-Pass Reasoning in Multi-Hop QA [65.38186593873313]
  Multi-Hop Question Answering (MHQA) requires integrating dispersed, interdependent evidence through sequential reasoning under noise.<n>We introduce a proof-of-concept multi-call framework for MHQA, InfoQA.<n>We construct a stringent and noise-rich benchmark to validate our theory and framework.
  arXiv  Detail & Related papers  (2025-09-25T14:11:57Z)
• Control Synthesis in Partially Observable Environments for Complex Perception-Related Objectives [2.7038841665524846]
  This work studies the problem of synthesizing optimal policies for perception-related objectives in environments modeled by partially observable Markov decision processes.<n>Our solution is to transform the mboxsc-iLTL objectives into reachability objectives by constructing the product of the belief MDP and a deterministic finite automaton built from the sc-iLTL objective.<n>To overcome the scalability challenge due to the product, we introduce a Monte Carlo Tree Search (MCTS) method that converges in probability to the optimal policy.
  arXiv  Detail & Related papers  (2025-06-27T22:02:07Z)
• Directed Exploration in Reinforcement Learning from Linear Temporal Logic [59.707408697394534]
  Linear temporal logic (LTL) is a powerful language for task specification in reinforcement learning.<n>We show that the synthesized reward signal remains fundamentally sparse, making exploration challenging.<n>We show how better exploration can be achieved by further leveraging the specification and casting its corresponding Limit Deterministic B"uchi Automaton (LDBA) as a Markov reward process.
  arXiv  Detail & Related papers  (2024-08-18T14:25:44Z)
• Entropy-Regularized Token-Level Policy Optimization for Language Agent Reinforcement [67.1393112206885]
  Large Language Models (LLMs) have shown promise as intelligent agents in interactive decision-making tasks. We introduce Entropy-Regularized Token-level Policy Optimization (ETPO), an entropy-augmented RL method tailored for optimizing LLMs at the token level. We assess the effectiveness of ETPO within a simulated environment that models data science code generation as a series of multi-step interactive tasks.
  arXiv  Detail & Related papers  (2024-02-09T07:45:26Z)
• Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
  We design a predictive layer for structured-output prediction (SOP) It can be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints. Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over a structured output space.
  arXiv  Detail & Related papers  (2022-06-01T12:02:38Z)

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.