Windowed A-K-MDP

Xiangwen Yang; Frankie Cho; Iadine Chades

cs.AISep 12, 2026

Windowed A-K-MDP

Authors: Xiangwen Yang, Frankie Cho, Iadine Chades

Organizations: Monash University Melbourne, Australia

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.

Figures & tables

Model	$\|\mathcal{S}\|$	$K$	$C_{W}$	$E$	Binary $J$	Windowed $J$
Aedes	6,097	61	–	9	0.1981	0
	6,097	305	–	96	0.03576	0.000386
Gouldian finch	162	8	203	203	30.000	9.344
	162	13	374	39	14.380	0
Fisheries	1,001	13	499	499	0.08264	0.002592
SONA	819	50	10,569	10,569	0.1441	0.02331

Table 1: Representative raw-native comparisons using the full action set

\mathcal{A}

C_{W}

is the complete candidate-family size and

E

the realised number of abstract-MDP solves. Dashes denote bounded Aedes runs; rows with

E<C_{W}

stopped at

J=0

. The SONA row is the local

K=50

result. Gaps use model-native reward units and are comparable only within rows.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: A binary-search trajectory that misses a feasible interval. The shaded regions satisfy

N(d)\leq K=2

for

V^{*}=(3,5,8)

. After probing

d=4,2,3,7/2

, the search contracts toward

4

without evaluating

[5/2,3)

, whose induced partition differs from the returned partition.

Model	$\|\mathcal{S}\|$	$\|\mathcal{A}\|$	$\gamma$	Artifact and treatment
Aedes	6,097	17	$1-10^{-8}$	Checksum-locked official three-island generator [ Péron, 2017 ] ; six-month step and near-undiscounted persistence objective.
Fire	91	2	.96	Constructed threatened-species fire-management replication.
Fisheries	1,001	11	.96	Downloaded $K$ -MDP package instance.
Forest	1,000	2	.99	Constructed forest-management benchmark.
Gouldian finch	162	4	.90	Latent-state MDP projection of the Gouldian MOMDP [ Chadès et al., 2012a ] ; observations and initial belief omitted.
Grey wolves	1,000	4	.96	Downloaded package instance; not the dimensionally different published wolf cases.

Appendix

Table 2: Artifact scope and discount factors for the ten-MDP corpus. The downloaded Reserve and grey-wolf instances differ from the dimensions of the corresponding published cases; Gouldian is a fully observable latent-state projection rather than the original MOMDP policy.

Figure 2: SONA worst-state value gap as a percentage of

\lVert V^{*}\rVert_{\infty}

, using the full action set

\mathcal{A}

. Independently anchored local Windowed optima are non-monotone in

K

. Combining candidates across the declared windows first gives zero gap at

K=6

and retains that policy for every larger budget.

$B_{A}$	Binary actions	Binary gap	Windowed actions	Windowed gap
2	I+AP	0.382075	I+AP	0.382075
3	I+AP+C	0.059130	I+AP+H	0.043192
4	I+AP+C (3 used)	0.059130	I+AP+C+H	0.023315

Appendix

Table 3: Optional SONA action-set sensitivity at

K=50

, exhaustive over feasible retained action sets

\mathcal{U}\subseteq\mathcal{A}

satisfying

|\mathcal{U}|\leq B_{A}

and the corresponding declared local Windowed families. This experiment is separate from the core state-budget comparison.

Explore similar work

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies
Aug 3, 2026Sterre Lutz, Daniël Vos, Matthijs T. J. Spaan +1Markov Decision Processes Sequential Decision Making
Delft University of Technology
Property-driven Causal Abstractions for Markov Decision Processes
Jul 29, 2026Jule Schmidt, Maximilian Weininger, Clemens Dubslaff +2Markov Decision Processes Causal Modeling
Ruhr-University Bochum, Germany · Eindhoven University of Technology, The Netherlands · Oxford University, UK +1
Adaptive Resolving Methods for Markov Decision Processes with Function Approximations
May 17, 2025Jiashuo Jiang, Yinyu Ye, Yiming ZongMarkov Decision Processes Optimal Policies
Department of Industrial Engineering & Decision Analytics, The Hong Kong University of Science and Technology · Department of Management Science & Engineering, Stanford University

Aug 3, 2026, cs.AIJ/K move · Enter open · S save

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

Sterre Lutz, Daniël Vos, Matthijs T. J. Spaan, Anna Lukina

Delft University of Technology

Markov Decision Processes Sequential Decision Making Minimax Small Models

Open paper AskPDF arXiv

Sequential decision-making in real-world applications often involves uncertainty about the environment's model. Uncertain Markov decision processes (UMDPs) represent the possible environments as a set of MDPs with shared states and actions but potentially different transition probabilities and rewards. Optimizing a single policy across all possible MDPs may sacrifice performance, while preparing an individually optimized policy for every MDP may violate operational, regulatory, or interpretability constraints on the number of policies that can be prepared and deployed. We consider settings in which model uncertainty is resolved shortly before execution, allowing the most suitable policy to be selected from a limited set prepared in advance. We introduce

k

-adaptable policy synthesis, which optimizes such a set of

k

policies under a minimax-regret objective. We prove that the problem is NP-hard and develop KAPS, an exact nested branch-and-bound algorithm with problem-specific bounds and heuristics. KAPS jointly optimizes which MDPs share a policy and the policies themselves. Experiments across various UMDP benchmarks show that the largest reduction in regret consistently occurs when increasing from one to two policies. In the single-policy setting, KAPS is competitive with existing methods in solution quality and proves optimality substantially more often.

Abstract

Explore similar work

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

Property-driven Causal Abstractions for Markov Decision Processes

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations