Windowed A-K-MDP

• URL: http://arxiv.org/abs/2609.13676v1
• Date: Sat, 12 Sep 2026 03:01:17 GMT
• Title: Windowed A-K-MDP
• Abstract summary: K-MDP methods address this problem by building simpler MDPs with at most K abstract states.<n>We show that the previously proposed A-K-MDP algorithm that relies on selecting a discretisation divisor using binary search can skip better abstract states.<n>We propose Windowed A-K-MDP, an algorithm that generates every distinct feasible partition induced within a declared divisor window.
• Score: 2.4687962186994663
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Markov decision processes (MDPs) are used to support decision-making in conservation of biodiversity, but policies, even over small state spaces, can be difficult to interpret for conservation managers. K-MDP methods address this problem by building simpler MDPs with at most K abstract states. We show that the previously proposed A-K-MDP algorithm that relies on selecting a discretisation divisor using binary search can skip better abstract states. To fix this issue, we propose Windowed A-K-MDP, an algorithm that generates every distinct feasible partition induced within a declared divisor window and evaluates candidates until reaching the ideal value loss (J = 0) or exhausting the family of candidates. Across 33 K-MDP instances, Windowed improved 25 and tied 8.

Related papers

• Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning [4.024538378639506]
  This paper defines Realizable Abstractions, a new relation between generic low-level MDPs and their associated high-level decision processes.<n>We show that any abstract policy for Realizable Abstractions can be translated into near-optimal policies for the low-level MDP, through a suitable composition of options.<n>We propose RARL, a new HRL algorithm that returns compositional and near-optimal low-level policies.
  arXiv  Detail & Related papers  (2025-12-04T16:26:56Z)
• Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs [2.7262923206583136]
  We study a class of infinite MDPs: one-counter MDPs (OC-MDPs)<n>We consider two characteristic objectives: reaching a target state (state-reachability) and reaching a target state with counter value zero.<n>We introduce two natural classes of concisely represented strategies based on a (possibly infinite) partition of counter values in intervals.
  arXiv  Detail & Related papers  (2025-03-02T08:32:17Z)
• Robust Counterfactual Inference in Markov Decision Processes [3.047215509762019]
  Current approaches assume a specific causal model to make counterfactuals identifiable.<n>We propose a novel non-parametric approach that computes tight bounds on counterfactual transition probabilities.
  arXiv  Detail & Related papers  (2025-02-19T13:56:20Z)
• Prospective Side Information for Latent MDPs [80.00842638151558]
  We study the class of LMDPs with em prospective side information, when an agent receives additional, weakly revealing, information at the beginning of each episode. We show that, surprisingly, this problem is not captured by contemporary settings and algorithms designed for partially observed environments. We then establish that any sample efficient algorithm must suffer at least $Omega(K2/3)$-regret, as opposed to standard $Omega(sqrtK)$ lower bounds, and design an algorithm with a matching upper bound.
  arXiv  Detail & Related papers  (2023-10-11T15:37:31Z)
• B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming Approach to Solving POMDPs [17.956744635160568]
  We propose an extension to the RTDP-Bel algorithm which we call Belief Branch and Bound RTDP (B$3$RTDP) Our algorithm uses a bounded value function representation and takes advantage of this in two novel ways. We empirically demonstrate that B$3$RTDP can achieve greater returns in less time than the state-of-the-art SARSOP solver on known POMDP problems.
  arXiv  Detail & Related papers  (2022-10-22T21:42:59Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid. We propose a theory characterizing the approximation error of the particle filtering techniques that these algorithms use.
  arXiv  Detail & Related papers  (2022-10-10T21:11:55Z)
• Continuous MDP Homomorphisms and Homomorphic Policy Gradient [51.25171126424949]
  We extend the definition of MDP homomorphisms to encompass continuous actions in continuous state spaces. We propose an actor-critic algorithm that is able to learn the policy and the MDP homomorphism map simultaneously.
  arXiv  Detail & Related papers  (2022-09-15T15:26:49Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
  We introduce a new approach to address safe RL problems under the framework of Early TerminatedP (ET-MDP) We first define the ET-MDP as an unconstrained algorithm with the same optimal value function as its corresponding CMDP. An off-policy algorithm based on context models is then proposed to solve the ET-MDP, which thereby solves the corresponding CMDP with better performance and improved learning efficiency.
  arXiv  Detail & Related papers  (2021-07-09T04:24:40Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  We consider the regret problem for reinforcement learning in latent Markov Decision Processes (LMDP) In an LMDP, an MDP is randomly drawn from a set of $M$ possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We show that the key link is a notion of separation between the MDP system dynamics.
  arXiv  Detail & Related papers  (2021-02-09T16:49:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22: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.