Performance-Driven Environment Abstraction with Multi-Timescale Learning

• URL: http://arxiv.org/abs/2606.17377v1
• Date: Tue, 16 Jun 2026 00:19:23 GMT
• Title: Performance-Driven Environment Abstraction with Multi-Timescale Learning
• Abstract summary: We study performance-driven environment abstraction for decision-making in large Markov decision processes.<n>We model abstraction as a controlled approximation obtained by aggregating the state space.<n>For a fixed partition, we establish a performance guarantee that separates value-function approximation error from the loss introduced by action sharing.
• Score: 14.594941665205148
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study performance-driven environment abstraction for decision-making in large Markov decision processes. Rather than preserving geometric or topological structure, we seek abstractions that directly optimize decision quality. We model abstraction as a controlled approximation obtained by aggregating the state space and enforcing a shared action distribution within each aggregated state. For a fixed partition, we establish a performance guarantee that separates value-function approximation error from the loss introduced by action sharing. Guided by this analysis, we develop a multi-timescale reinforcement learning framework that jointly adapts the policy and a tree-structured environment abstraction. The resulting algorithm refines and coarsens regions of the state space based on Q-value discrepancies, balancing performance against abstraction size and complexity. Empirical results demonstrate substantial state compression, improved sample efficiency, and faster replanning compared to actor-critic baselines.

Related papers

• Adaptive Latent Trajectory Anchoring for Action Segmentation Dataset Condensation [53.60856261088647]
  This paper proposes to shift the condensation paradigm from optimization-based inversion to deterministic latent mapping.<n>We represent action segments as continuous trajectories anchored by sparse latent points in the noise manifold.<n>Our framework significantly outperforms state-of-the-art methods in segmentation performance across common datasets.
  arXiv  Detail & Related papers  (2026-07-10T04:00:26Z)
• Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm [64.43268969806098]
  A core challenge of Monte Carlo Tree Search (MCTS) is its sample efficiency, which can be improved by grouping state-action pairs.<n>We break with the paradigm of grouping value-equivalent states or state-action pairs and instead group states and state-action pairs with possibly different values.<n>We call this abstraction framework Known Value Difference Abstractions ( KVDA), which infers the value differences by analysis of the immediate rewards.
  arXiv  Detail & Related papers  (2025-10-29T11:03:44Z)
• Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes [32.156826903097134]
  Homomorphic Policy Gradient (HPG) guarantees optimal policy equivalence under sufficient conditions.<n>EBHPG balances computational efficiency and the performance loss induced by aggregation.
  arXiv  Detail & Related papers  (2025-10-11T02:40:03Z)
• Q-function Decomposition with Intervention Semantics with Factored Action Spaces [51.01244229483353]
  We consider Q-functions defined over a lower dimensional projected subspace of the original action space, and study the condition for the unbiasedness of decomposed Q-functions.<n>This leads to a general scheme which we call action decomposed reinforcement learning that uses the projected Q-functions to approximate the Q-function in standard model-free reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2025-04-30T05:26:51Z)
• Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes [37.15580574143281]
  offline reinforcement learning (RL) This paper considers the sample complexity of distributionally robust linear Markov decision processes (MDPs) with an uncertainty set characterized by the total variation distance using offline data. We develop a pessimistic model-based algorithm and establish its sample complexity bound under minimal data coverage assumptions.
  arXiv  Detail & Related papers  (2024-03-19T17:48:42Z)
• 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)
• Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping [7.691755449724638]
  Reinforcement learning often needs to deal with the exponential growth of states and actions in high-dimensional spaces. We learn the inherent structure of action-wise similar MDP to appropriately balance the performance degradation versus sample/computational complexity.
  arXiv  Detail & Related papers  (2023-06-22T15:40:10Z)
• Policy Gradient Methods in the Presence of Symmetries and State Abstractions [46.66541516203923]
  Reinforcement learning (RL) on high-dimensional and complex problems relies on abstraction for improved efficiency and generalization. We study abstraction in the continuous-control setting, and extend the definition of Markov decision process (MDP) homomorphisms to the setting of continuous state and action spaces. We propose a family of actor-critic algorithms that are able to learn the policy and the MDP homomorphism map simultaneously.
  arXiv  Detail & Related papers  (2023-05-09T17:59:10Z)
• Hierarchical State Abstraction Based on Structural Information Principles [70.24495170921075]
  We propose a novel mathematical Structural Information principles-based State Abstraction framework, namely SISA, from the information-theoretic perspective. SISA is a general framework that can be flexibly integrated with different representation-learning objectives to improve their performances further.
  arXiv  Detail & Related papers  (2023-04-24T11:06:52Z)
• A Direct Approximation of AIXI Using Logical State Abstractions [6.570488724773507]
  We propose a practical integration of logical state abstraction with AIXI, a Bayesian optimality notion for reinforcement learning agents. We address the problem of selecting the right subset of features to form state abstractions. Exact Bayesian model learning is then achieved using a suitable generalisation of Context Tree Weighting over abstract state sequences.
  arXiv  Detail & Related papers  (2022-10-13T11:30:56Z)
• Randomized Value Functions via Posterior State-Abstraction Sampling [21.931580762349096]
  We argue that an agent seeking out latent task structure must explicitly represent and maintain its uncertainty over that structure. We introduce a practical algorithm for doing this using two posterior distributions over state abstractions and abstract-state values. In empirically validating our approach, we find that substantial performance gains lie in the multi-task setting.
  arXiv  Detail & Related papers  (2020-10-05T23:04:18Z)
• Invariant Causal Prediction for Block MDPs [106.63346115341862]
  Generalization across environments is critical to the successful application of reinforcement learning algorithms to real-world challenges. We propose a method of invariant prediction to learn model-irrelevance state abstractions (MISA) that generalize to novel observations in the multi-environment setting.
  arXiv  Detail & Related papers  (2020-03-12T21:03:01Z)

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.