Entropy Objectives in Markov Decision Processes

• URL: http://arxiv.org/abs/2606.21726v1
• Date: Fri, 19 Jun 2026 20:25:38 GMT
• Title: Entropy Objectives in Markov Decision Processes
• Abstract summary: We consider the problem of synthesizing control policies that enforce a concentration property on the state distributions of a system.<n>We first show that even relaxed versions of this problem are complexity-theoretically hard.<n>We then present a sound and (conditionally) relatively complete method to verify and synthesize strategies for such entropy objectives.
• Score: 5.654132722460059
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the problem of synthesizing control policies that enforce a concentration property on the state distributions of a stochastic system. We present a formalization of this problem in terms of synthesizing strategies for maintaining an entropy-based objective in Markov Decision Processes (MDPs). We first show that even relaxed versions of this problem are complexity-theoretically hard. We then present a sound and (conditionally) relatively complete method to verify and synthesize strategies for such entropy objectives. The main challenge is the non-linear nature of such objectives, and our approach addresses this by exploiting and combining ideas from convex duality and invariant synthesis. We also investigate the role of memory and randomization in ensuring entropy objectives. Finally, we implement our ideas to evaluate our approach empirically on a few illustrative benchmarks.

Related papers

• Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning [2.375990942704781]
  POMDPs are the standard framework for decision-making under uncertainty.<n>While sampling-based methods scale well, they lack formal correctness guarantees, making them unsuitable for safety-critical applications.<n>We propose a synthesis framework that integrates sampling, automata learning, and model-checking.
  arXiv  Detail & Related papers  (2026-05-14T06:37:31Z)
• Causal Algorithmic Recourse: Foundations and Methods [57.73269033551628]
  Key feature of AI systems is the ability to provide recommendations for how an individual may reverse a negative decision.<n>Existing approaches treat recourse outcomes as counterfactuals of a fixed unit.<n>We develop a causal framework that models recourse as a process over pre- and post-intervention outcomes.
  arXiv  Detail & Related papers  (2026-05-12T00:55:19Z)
• Step-Aware Policy Optimization for Reasoning in Diffusion Large Language Models [57.42778606399764]
  Diffusion language models (dLLMs) offer a promising, non-autoregressive paradigm for text generation.<n>Current reinforcement learning approaches often rely on sparse, outcome-based rewards.<n>We argue that this stems from a fundamental mismatch with the natural structure of reasoning.
  arXiv  Detail & Related papers  (2025-10-02T00:34:15Z)
• 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)
• Invariant Measures for Data-Driven Dynamical System Identification: Analysis and Application [0.0]
  We propose a novel approach for performing dynamical system identification, based upon the comparison of simulated and observed physical invariant measures.<n>We gain robustness against pervasive challenges in system identification including noise, chaos, and slow sampling.
  arXiv  Detail & Related papers  (2025-01-31T23:27:33Z)
• PCA for Point Processes [1.7499351967216341]
  We introduce a novel statistical framework for the analysis of replicated point processes.<n>By treating point process realizations as random measures, we adopt a functional analysis perspective.<n>Key theoretical contributions include establishing a Karhunen-Loeve expansion for the random measures.
  arXiv  Detail & Related papers  (2024-04-30T15:57:18Z)
• Entropic Matching for Expectation Propagation of Markov Jump Processes [31.376561087029454]
  We propose a novel, tractable latent inference scheme for Markov jump processes.<n>Our approach is based on an entropic matching framework that can be embedded into the well-known expectation propagation algorithm.
  arXiv  Detail & Related papers  (2023-09-27T12:07:21Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  Three major challenges in reinforcement learning are the complex dynamical systems with large state spaces, the costly data acquisition processes, and the deviation of real-world dynamics from the training environment deployment. We study distributionally robust Markov decision processes with continuous state spaces under the widely used Kullback-Leibler, chi-square, and total variation uncertainty sets. We propose a model-based approach that utilizes Gaussian Processes and the maximum variance reduction algorithm to efficiently learn multi-output nominal transition dynamics.
  arXiv  Detail & Related papers  (2023-09-05T13:42:11Z)
• Learning non-Markovian Decision-Making from State-only Sequences [57.20193609153983]
  We develop a model-based imitation of state-only sequences with non-Markov Decision Process (nMDP) We demonstrate the efficacy of the proposed method in a path planning task with non-Markovian constraints.
  arXiv  Detail & Related papers  (2023-06-27T02:26:01Z)
• Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics [64.72260320446158]
  We propose a method for synthesising controllers for Markov jump linear systems. Our method is based on a finite-state abstraction that captures both the discrete (mode-jumping) and continuous (stochastic linear) behaviour of the MJLS. We apply our method to multiple realistic benchmark problems, in particular, a temperature control and an aerial vehicle delivery problem.
  arXiv  Detail & Related papers  (2022-12-01T17:36:30Z)
• Controller Synthesis for Omega-Regular and Steady-State Specifications [9.901800502055929]
  We present an algorithm to find a deterministic policy satisfying $omega$-regular and steady-state constraints. We experimentally evaluate our approach.
  arXiv  Detail & Related papers  (2021-06-05T19:34:22Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  Decision making under uncertainty is critical to real-world, autonomous systems. Model Predictive Control (MPC) methods have demonstrated favorable performance in practice, but remain limited when dealing with complex distributions. We show that this framework leads to successful planning in challenging, non optimal control problems.
  arXiv  Detail & Related papers  (2020-11-15T22:36:59Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.