Windowed A-K-MDP

# Windowed A-𝐾-MDP
Source: [https://arxiv.org/html/2609.13676](https://arxiv.org/html/2609.13676)
Xiangwen YangFrankie ChoAffiliation:Monash UniversityAffiliation:Melbourne, AustraliaEmail:[frankie\.cho@monash\.edu](mailto:)Iadine ChadesAffiliation:Monash UniversityAffiliation:Melbourne, AustraliaEmail:[iadine\.chades@monash\.edu](mailto:)

###### 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\.KK\-MDP methods address this problem by building simpler MDPs with at mostKKabstract states\. We show that the previously proposed A\-KK\-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\-KK\-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=0J=0\) or exhausting the family of candidates\. Across 33KK\-MDP instances, Windowed improved 25 and tied 8\.

## 1Introduction

MDPs have been used to inform sequential decisions under uncertainty in many conservation of biodiversity problems\([Marescot et al\., 2013](https://arxiv.org/html/2609.13676#bib.bib11)\)\. However, MDP policies even for small states space can be difficult to interpret by humans, preventing opportunities to guide managers on the ground\.KK\-MDPs algorithms have been proposed to address this problem by reducing the original MDP state space toKKabstract states\([Ferrer\-Mestres et al\., 2020](https://arxiv.org/html/2609.13676#bib.bib1);[Ferrer\-Mestres et al\., 2024](https://arxiv.org/html/2609.13676#bib.bib2)\)\. For example, the original sea\-otter and northern\-abalone model, with 819 states and four actions\([Chadès et al\., 2012b](https://arxiv.org/html/2609.13676#bib.bib5)\)was transformed into a ten\-state A\-KK\-MDP with a small loss of performance \(value loss = 2\.8%\)\([Ferrer\-Mestres et al\., 2020](https://arxiv.org/html/2609.13676#bib.bib1)\)\.

In A\-KK\-MDP, the action/value abstractionϕad∗\\phi\_\{a^\{\*\}\_\{d\}\}groups states sharing an optimal action and a discretised optimal value\. Its published divisor\-selection loop uses midpoint binary updates\([Ferrer\-Mestres et al\., 2020](https://arxiv.org/html/2609.13676#bib.bib1)\)\. At each iteration, the update direction is determined by whether the resulting abstraction contains at mostKKstates,N⁡\(d\)≤KN\(d\)\\leq K\. However, this condition is not monotone in the divisordd, so the binary search can skip a feasible partition with lower value loss\. Instead, our proposed Windowed A\-KK\-MDP derives the exact values at which the induced partition changes\. In its complete branch, it generates each distinct feasible partition inside a fixed interval around the repaired binary anchor and evaluates until reaching no value loss \(J=0J=0\) or exhausting the family\. Its guarantee is local to that declared interval and abstraction family\.

Compared with the published binary\-search procedure, we make three contributions\. First, we provide a counterexample showing that the number of abstract states is not monotone indd, and that binary search can therefore miss a feasible partition with lower decision loss\. Second, within a specified divisor window, we derive the exact values ofddat which the induced partition can changes\. Third, we compare Windowed A\-KK\-MDP with a repaired Binary baseline using the same construction and evaluation procedure\. Across the conservation problems considered, Windowed A\-KK\-MDP finds compact policies with lower decision loss when better partitions are missed by binary search\.

## 2Problem formulation

LetM=\(𝒮,𝒜,P,r,γ\)M=\(\\mathcal\{S\},\\mathcal\{A\},P,r,\\gamma\)be a finite MDP, where𝒮\\mathcal\{S\}is the state space,𝒜\\mathcal\{A\}is the action set,∅≠𝒜⁡\(s\)⊆𝒜\\varnothing\\neq\\mathcal\{A\}\(s\)\\subseteq\\mathcal\{A\}is the set of actions available at statess,PPis the transition kernel,rris the reward, andγ∈\[0,1\)\\gamma\\in\[0,1\)is the discount factor\. AssumeV∗​\(s\)≥0V^\{\*\}\(s\)\\geq 0andVmax:=maxs⁡V∗​\(s\)\>0V\_\{\\max\}:=\\max\_\{s\}V^\{\*\}\(s\)\>0\. Lowest\-index tie\-breaking fixes an optimal deterministic policyπ∗\\pi^\{\*\}\.

AKK\-MDPMK=\(𝒮K,𝒜,PK,rK,γ,ϕ\)M\_\{K\}=\(\\mathcal\{S\}\_\{K\},\\mathcal\{A\},P\_\{K\},r\_\{K\},\\gamma,\\phi\)is an MDP with at mostKKstates and solving aKK\-MDP problem means finding the best reduced state space \(\|𝒮K\|≤K\|\\mathcal\{S\}\_\{K\}\|\\leq K\) so that the value loss between the ground MDP and theKK\-MDP is minimal\. Here, we study the empirically best\-performingKK\-MDP variant reported by[Ferrer\-Mestres et al\. \(2020\)](https://arxiv.org/html/2609.13676#bib.bib1)that uses the action/value abstraction, formally:

ϕad∗​\(s\)=\(π∗​\(s\),⌈V∗​\(s\)/d⌉\),\\phi\_\{a^\{\*\}\_\{d\}\}\(s\)=\\bigl\(\\pi^\{\*\}\(s\),\\lceil V^\{\*\}\(s\)/d\\rceil\\bigr\),\(1\)and writeϕd:=ϕad∗\\phi\_\{d\}:=\\phi\_\{a^\{\*\}\_\{d\}\}\. States with the same action/value\-bin pair form one abstract state, soN⁡\(d\):=\|\{ϕd​\(s\):s∈𝒮\}\|N\(d\):=\\left\|\\left\\\{\\phi\_\{d\}\(s\):s\\in\\mathcal\{S\}\\right\\\}\\right\|is the induced number of abstract states\. A divisor is feasible whenN⁡\(d\)≤KN\(d\)\\leq K\. More generally, letN⁡\(ϕ\):=\|\{ϕ⁡\(s\):s∈𝒮\}\|N\(\\phi\):=\|\\\{\\phi\(s\):s\\in\\mathcal\{S\}\\\}\|, soN⁡\(ϕd\)=N⁡\(d\)N\(\\phi\_\{d\}\)=N\(d\)\. We restrict attention to budgets satisfyingN⁡\(Vmax\)≤KN\(V\_\{\\max\}\)\\leq K, the minimum block count attainable by this divisor family on\(0,Vmax\]\(0,V\_\{\\max\}\]\.

For a state mappingϕ\\phi, we define its abstract state set𝒮ϕ:=\{ϕ⁡\(s\):s∈𝒮\}\\mathcal\{S\}\_\{\\phi\}:=\\\{\\phi\(s\):s\\in\\mathcal\{S\}\\\}and constituent blocksBk:=\{s∈𝒮:ϕ⁡\(s\)=k\}B\_\{k\}:=\\\{s\\in\\mathcal\{S\}:\\phi\(s\)=k\\\}\. Following[Abel et al\. \(2016\)](https://arxiv.org/html/2609.13676#bib.bib10);[Ferrer\-Mestres et al\. \(2020\)](https://arxiv.org/html/2609.13676#bib.bib1), we use uniform within\-block weightsωϕ​\(s∣k\):=1/\|Bk\|\\omega\_\{\\phi\}\(s\\mid k\):=1/\|B\_\{k\}\|fors∈Bks\\in B\_\{k\}\. The action set for abstract statekkis𝒜ϕ​\(k\):=⋂s∈Bk𝒜⁡\(s\)\\mathcal\{A\}\_\{\\phi\}\(k\):=\\bigcap\_\{s\\in B\_\{k\}\}\\mathcal\{A\}\(s\)\. Whenϕ=ϕd\\phi=\\phi\_\{d\},𝒜ϕ​\(k\)≠∅\\mathcal\{A\}\_\{\\phi\}\(k\)\\neq\\varnothingfor everyk∈𝒮ϕk\\in\\mathcal\{S\}\_\{\\phi\}, becauseπ∗​\(s\)\\pi^\{\*\}\(s\)is the same for alls∈Bks\\in B\_\{k\}and this common action belongs to𝒜⁡\(s\)\\mathcal\{A\}\(s\)for everys∈Bks\\in B\_\{k\}\.

Fork,k′∈𝒮ϕk,k^\{\\prime\}\\in\\mathcal\{S\}\_\{\\phi\}anda∈𝒜ϕ​\(k\)a\\in\\mathcal\{A\}\_\{\\phi\}\(k\), the abstract reward and transition kernel are

rϕ​\(k,a\)\\displaystyle r\_\{\\phi\}\(k,a\):=∑s∈Bkωϕ​\(s∣k\)​r​\(s,a\),\\displaystyle:=\\sum\_\{s\\in B\_\{k\}\}\\omega\_\{\\phi\}\(s\\mid k\)r\(s,a\),Pϕ​\(k′∣k,a\)\\displaystyle P\_\{\\phi\}\(k^\{\\prime\}\\mid k,a\):=∑s∈Bkωϕ​\(s∣k\)​∑s′∈Bk′P⁡\(s′∣s,a\)\.\\displaystyle:=\\sum\_\{s\\in B\_\{k\}\}\\omega\_\{\\phi\}\(s\\mid k\)\\sum\_\{s^\{\\prime\}\\in B\_\{k^\{\\prime\}\}\}P\(s^\{\\prime\}\\mid s,a\)\.
Together withγ\\gamma, these quantities define the abstract MDP\. We solve it using the same lowest\-index tie\-breaking and lift its policy asπ~ϕ​\(s\):=πϕ​\(ϕ⁡\(s\)\)\\widetilde\{\\pi\}\_\{\\phi\}\(s\):=\\pi\_\{\\phi\}\(\\phi\(s\)\)\.

Following[Ferrer\-Mestres et al\. \(2020, Eq\. \(1\)\)](https://arxiv.org/html/2609.13676#bib.bib1), we evaluate a fixed abstractionϕ\\phiby its maximum statewise value loss on the original MDP,J⁡\(ϕ\):=maxs∈𝒮⁡\[V∗​\(s\)−Vπ~ϕ​\(s\)\]\+J\(\\phi\):=\\max\_\{s\\in\\mathcal\{S\}\}\[V^\{\*\}\(s\)\-V^\{\\widetilde\{\\pi\}\_\{\\phi\}\}\(s\)\]\_\{\+\}, where\[x\]\+:=max⁡\{x,0\}\[x\]\_\{\+\}:=\\max\\\{x,0\\\}\. For a fixedϕ\\phi,J⁡\(ϕ\)J\(\\phi\)is the inner maximisation in their K\-MDP gap objective\. Whereas their objective minimises over all admissible reduced state spaces, Windowed compares only candidates induced within the declared divisor window\. We retain the worst\-state criterion because an average under a chosen initial\-state distribution could conceal a large loss at an infrequently weighted but decision\-critical state\.

## 3Windowed search

Consider an MDP with two states that share the same optimal action, and have optimal valuesV∗=\(2,3\)V^\{\*\}=\(2,3\)\. For a budget ofK=1K=1abstract state, the value bin indices atd=3/2,2,3d=3/2,2,3are respectively\(2,2\),\(1,2\),\(1,1\)\(2,2\),\(1,2\),\(1,1\)\. Thus, forFK\(d\):=𝟙\{N\(d\)≤K\}F\_\{K\}\(d\):=\\mathds\{1\}\\\{N\(d\)\\leq K\\\}, the two states are grouped together atd=3/2d=3/2, separated atd=2d=2, and grouped together again atd=3d=3\. Hence,N⁡\(d\)=1,2,1N\(d\)=1,2,1, respectively, showing that the conditionN⁡\(d\)≤KN\(d\)\\leq Kis not monotone indd\. Thus, a binary trajectory can discard a feasible interval;[appendixA](https://arxiv.org/html/2609.13676#A1)gives a three\-state missed\-partition example\. Our conservative baseline, endpoint\-repaired Binary, retains the feasible endpointd=Vmaxd=V\_\{\\max\}before applying the midpoint updates of[Ferrer\-Mestres et al\. \(2020\)](https://arxiv.org/html/2609.13676#bib.bib1)\.

We address this problem by exploiting the structure of the abstraction in[equation1](https://arxiv.org/html/2609.13676#S2.E1)\. ForV∗​\(s\)\>0V^\{\*\}\(s\)\>0andd\>0d\>0, the integer assignment⌈V∗​\(s\)/d⌉\\lceil V^\{\*\}\(s\)/d\\rceilremains constant except whenddcrosses a valueV∗​\(s\)/mV^\{\*\}\(s\)/m, wheremmis a positive integer\. Becauseπ∗​\(s\)\\pi^\{\*\}\(s\)is fixed, the induced partition can change only at one of these divisor values\. For a fixed closed windowW=\[L,R\]W=\[L,R\]withL\>0L\>0, we defineℬ⁡\(W\)\\mathcal\{B\}\(W\)as the set containing the window endpoints and all values ofddat which the induced partition may change:

ℬ\(W\):=\{L,R\}∪\{V∗​\(s\)m:V∗\(s\)\>0,m∈ℕ\+,L<V∗​\(s\)m<R\}\.\\mathcal\{B\}\(W\):=\\\{L,R\\\}\\cup\\left\\\{\\frac\{V^\{\*\}\(s\)\}\{m\}:V^\{\*\}\(s\)\>0,\\;m\\in\\mathbb\{N\}\_\{\+\},\\;L<\\frac\{V^\{\*\}\(s\)\}\{m\}<R\\right\\\}\.\(2\)These points are analytic, generally non\-uniform, and not a numerical grid\. First\-occurrence canonicalisation, denotedcan⁡\(ϕ\)\\operatorname\{can\}\(\\phi\), relabels blocks as0,1,…0,1,\\ldotsin ground\-state order so that label permutations of the same partition are deduplicated\.

###### Theorem 1\(Closed\-window completeness\)\.

AssumeV∗​\(s\)≥0V^\{\*\}\(s\)\\geq 0for everys∈𝒮s\\in\\mathcal\{S\},0<L<R0<L<R, fixed tie\-breaking forπ∗\\pi^\{\*\}, and\{d∈\[L,R\]:N⁡\(d\)≤K\}≠∅\\\{d\\in\[L,R\]:N\(d\)\\leq K\\\}\\neq\\varnothing\. LetL=β0<⋯<βB=RL=\\beta\_\{0\}<\\dots<\\beta\_\{B\}=Rbe the sorted distinct points inℬ⁡\(W\)\\mathcal\{B\}\(W\)\. Thenϕd\\phi\_\{d\}is constant on\[βi,βi\+1\)\[\\beta\_\{i\},\\beta\_\{i\+1\}\)for everyi=0,…,B−1i=0,\\ldots,B\-1\. Consequently, the complete enumeration that evaluates one representative from each interval, together with the endpointRR, realises every distinct partition induced on\[L,R\]\[L,R\]and attainsmin\{J\(ϕd\):d∈\[L,R\],N\(d\)≤K\}\\min\\\{J\(\\phi\_\{d\}\):d\\in\[L,R\],\\;N\(d\)\\leq K\\\}\.

Letdbd\_\{b\}be the feasible divisor returned by endpoint\-repaired Binary\. The reported binary64 implementation usesdmin:=max⁡\{10−10​Vmax,10−12\}d\_\{\\min\}:=\\max\\\{10^\{\-10\}V\_\{\\max\},10^\{\-12\}\\\}and setsL:=max⁡\{db/ρ,dmin\}L:=\\max\\\{d\_\{b\}/\\rho,d\_\{\\min\}\\\},R:=min⁡\{ρ​db,Vmax\}R:=\\min\\\{\\rho d\_\{b\},V\_\{\\max\}\\\}, andW:=\[L,R\]W:=\[L,R\]\. We fixρ=2\.5\\rho=2\.5before evaluation as a coverage–cost choice, not a theoretically optimal value, and use10−410^\{\-4\}only as the stopping tolerance of the Binary anchor search; neither is updated during a run\. The numerical floor is an implementation convention, not a theorem assumption\. Every reported run verifies0<dmin≤db≤Vmax0<d\_\{\\min\}\\leq d\_\{b\}\\leq V\_\{\\max\}and a nondegenerate windowL<RL<R\. The window is fixed, not updated: the guarantee covers\[L,R\]\[L,R\]but notd∉\[L,R\]d\\notin\[L,R\]\. Becausecan⁡\(ϕdb\)\\operatorname\{can\}\(\\phi\_\{d\_\{b\}\}\)is retained, Windowed cannot return a larger gap than endpoint\-repaired Binary under the same builder and evaluator\. IfCWC\_\{W\}is the number of distinct feasible candidates in a completed window, thenCW≤\|𝒮\|​⌈Vmax/L⌉\+2C\_\{W\}\\leq\|\\mathcal\{S\}\|\\lceil V\_\{\\max\}/L\\rceil\+2; the tighter incidence count and binary64 guard are given in[appendixC](https://arxiv.org/html/2609.13676#A3)\.

EndpointRepairedDivisorSearchdenotes only the divisor\-selection loop underlying Algorithm 4 of[Ferrer\-Mestres et al\. \(2020\)](https://arxiv.org/html/2609.13676#bib.bib1), augmented to retain the feasible upper endpointd=Vmaxd=V\_\{\\max\}\. Its probes constructϕd\\phi\_\{d\}only to testN⁡\(d\)≤KN\(d\)\\leq Kand return the anchordbd\_\{b\}; they do not construct or solve an abstract MDP\.[Algorithm1](https://arxiv.org/html/2609.13676#alg1)presents the complete Windowed procedure, including the subsequent partition enumeration and abstract\-MDP evaluations\.

Algorithm 1Windowed A\-KK\-MDP1:solved MDP

MMwith

V∗≥0V^\{\*\}\\geq 0; lowest\-index tie\-broken

π∗\\pi^\{\*\}; state budget

KK;

ρ\>1\\rho\>1; Binary stopping tolerance

δb\>0\\delta\_\{b\}\>0
2:

Vmax←maxs∈𝒮⁡V∗​\(s\)V\_\{\\max\}\\leftarrow\\max\_\{s\\in\\mathcal\{S\}\}V^\{\*\}\(s\)
3:assert

Vmax\>0V\_\{\\max\}\>0and

N⁡\(Vmax\)≤KN\(V\_\{\\max\}\)\\leq K
4:

dmin←max⁡\{10−10​Vmax,10−12\}d\_\{\\min\}\\leftarrow\\max\\\{10^\{\-10\}V\_\{\\max\},10^\{\-12\}\\\}
5:

db←EndpointRepairedDivisorSearch​\(V∗,π∗,K,δb\)d\_\{b\}\\leftarrow\\textsc\{EndpointRepairedDivisorSearch\}\(V^\{\*\},\\pi^\{\*\},K,\\delta\_\{b\}\)
6:assert

N⁡\(db\)≤KN\(d\_\{b\}\)\\leq Kand

0<dmin≤db≤Vmax0<d\_\{\\min\}\\leq d\_\{b\}\\leq V\_\{\\max\}
7:

L←max⁡\{db/ρ,dmin\}L\\leftarrow\\max\\\{d\_\{b\}/\\rho,d\_\{\\min\}\\\}
8:

R←min⁡\{ρ​db,Vmax\}R\\leftarrow\\min\\\{\\rho d\_\{b\},V\_\{\\max\}\\\};

W←\[L,R\]W\\leftarrow\[L,R\]⊳\\trianglerightfixed throughout the run

9:assert

L<RL<R
10:construct and sort

ℬ⁡\(W\)=\{β0,…,βB\}\\mathcal\{B\}\(W\)=\\\{\\beta\_\{0\},\\ldots,\\beta\_\{B\}\\\}using[equations2](https://arxiv.org/html/2609.13676#S3.E2)and[3](https://arxiv.org/html/2609.13676#A3.E3), where

L=β0<⋯<βB=RL=\\beta\_\{0\}<\\cdots<\\beta\_\{B\}=R
11:

𝒟←\{\(βi\+βi\+1\)/2:0≤i<B\}∪\{R,db\}\\mathcal\{D\}\\leftarrow\\\{\(\\beta\_\{i\}\+\\beta\_\{i\+1\}\)/2:0\\leq i<B\\\}\\cup\\\{R,d\_\{b\}\\\}
12:

𝒞←\[can⁡\(ϕdb\)\]\\mathcal\{C\}\\leftarrow\[\\,\\operatorname\{can\}\(\\phi\_\{d\_\{b\}\}\)\\,\]⊳\\trianglerightretain Binary

13:for

d∈𝒟d\\in\\mathcal\{D\}do

14:

ϕ←can⁡\(ϕd\)\\phi\\leftarrow\\operatorname\{can\}\(\\phi\_\{d\}\)
15:if

N⁡\(ϕ\)≤KN\(\\phi\)\\leq Kand

ϕ∉𝒞\\phi\\notin\\mathcal\{C\}then

16:append

ϕ\\phito

𝒞\\mathcal\{C\}
17:for

ϕ∈𝒞\\phi\\in\\mathcal\{C\}in Critical order \([appendixF](https://arxiv.org/html/2609.13676#A6)\), Binary firstdo

18:build and solve the compact MDP and compute

J⁡\(ϕ\)J\(\\phi\)
19:if

J⁡\(ϕ\)=0J\(\\phi\)=0then

20:return

ϕ\\phi,zero\-gap\-found

21:return

arg⁡minϕ∈𝒞​J​\(ϕ\)\\arg\\min\_\{\\phi\\in\\mathcal\{C\}\}J\(\\phi\),all\-candidates\-checked

The algorithm shows the complete branch\. The implementation first computes a finite breakpoint\-incidence bound\. If it exceedsImax=100,000I\_\{\\max\}=100\{,\}000, a deterministic bounded stream evaluates at mostEmax=96E\_\{\\max\}=96distinct candidates\. ReachingJ=0J=0still certifies the objective lower bound; a positive capped run is labelledlowest\-gap\-foundand has no complete\-window claim\. Exact bounds, binary64 guards, run outcomes, and the proof of[theorem1](https://arxiv.org/html/2609.13676#Thmtheorem1)appear in[appendicesC](https://arxiv.org/html/2609.13676#A3)and[B](https://arxiv.org/html/2609.13676#A2)\. Throughout,EEdenotes the realised number of abstract\-MDP solves andCWC\_\{W\}the complete family size\. Only the bounded branch enforcesE≤EmaxE\\leq E\_\{\\max\}; complete runs may haveE\>EmaxE\>E\_\{\\max\}\.

## 4Results

We evaluate 33 case–KKpairs from 10 solved MDPs, seven ecological models and three controls\. All comparison uses the full action set𝒜\\mathcal\{A\}, the same abstract\-MDP builder and evaluator, differing only in the candidate partitions\. Windowed improves 25 rows and ties 8 because it retains the repaired Binary candidate; on the 17 informative completed windows, it improves/ties 14/3\. Three bounded*Aedes*runs reachJ=0J=0, whereasK=305K=305stops atEmax=96E\_\{\\max\}=96and is reported aslowest\-gap\-found\.[Table1](https://arxiv.org/html/2609.13676#S4.T1)and the appendix provide the remaining accounting\.

Table 1:Representative raw\-native comparisons using the full action set𝒜\\mathcal\{A\}\.CWC\_\{W\}is the complete candidate\-family size andEEthe realised number of abstract\-MDP solves\. Dashes denote bounded*Aedes*runs; rows withE<CWE<C\_\{W\}stopped atJ=0J=0\. The SONA row is the localK=50K=50result\. Gaps use model\-native reward units and are comparable only within rows\.[Table1](https://arxiv.org/html/2609.13676#S4.T1)reports representative rows; the complete ledger is in the artifact\. At GouldianK=13K=13, Critical reachesJ=0J=0afterE=39E=39ofCW=374C\_\{W\}=374candidate solves\. Across the 17 informative completed windows, Windowed improves/ties 14/3\. The separately frozen extension improves/ties five/three of its eight nonzero rows; its protocol is in[appendixE](https://arxiv.org/html/2609.13676#A5)\. Equal\-budget and cross\-KKSONA analyses are reported in[appendicesF](https://arxiv.org/html/2609.13676#A6)and[G](https://arxiv.org/html/2609.13676#A7)\.

## 5Conclusions

MDP policies are often simplified in an ad\-hoc manner to increase uptake by conservation managers, but compact representation doesn’t necessarily need to come at a performance loss\. Improving on\([Ferrer\-Mestres et al\., 2020](https://arxiv.org/html/2609.13676#bib.bib1)\), we have shown that midpoint binary search can miss A\-K\-MDP partitions becauseN⁡\(d\)N\(d\)is not monotone\. Our Windowed A\-KK\-MDP provides a systematic search of the distinct partitions within a stated window, improving 25 of 33 cases and tying the remainder\. For conservation managers, this reduces the risk that a policy is simplified at an unnecessary cost to decision performance\. Although compactness alone does not establish interpretability, it provides a stronger basis for examining and implementing simplified policies\.

## References

- Abelet al\.\(2016\)D\. Abel, D\. Hershkowitz, and M\. LittmanNear optimal behavior via approximate state abstraction\.InInternational Conference on Machine Learning,pp\. 2915–2923\.Cited by:[§2](https://arxiv.org/html/2609.13676#S2.p3.1)\.
- Ahluwaliaet al\.\(2021\)V\. S\. Ahluwalia, L\. N\. Steimle, and B\. T\. DentonPolicy\-based branch\-and\-bound for infinite\-horizon multi\-model markov decision processes\.Computers & Operations Research126,pp\. 105108\.Cited by:[Table 2](https://arxiv.org/html/2609.13676#A4.T2.2.8.5.1.1),[Table 2](https://arxiv.org/html/2609.13676#A4.T2.2.9.5.1.1)\.
- Chadèset al\.\(2012a\)I\. Chadès, J\. Carwardine, T\. Martin, S\. Nicol, R\. Sabbadin, and O\. BuffetMOMDPs: a solution for modelling adaptive management problems\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.26,pp\. 267–273\.Cited by:[Table 2](https://arxiv.org/html/2609.13676#A4.T2.2.6.5.1.1)\.
- Chadèset al\.\(2012b\)I\. Chadès, J\. M\. R\. Curtis, and T\. G\. MartinSetting realistic recovery targets for two interacting endangered species, sea otter and northern abalone: managing interacting endangered species\.Conserv\. Biol\.26\(6\),pp\. 1016–1025\(en\)\.Cited by:[§1](https://arxiv.org/html/2609.13676#S1.p1.1)\.
- Ferrer\-Mestreset al\.\(2024\)J\. Ferrer\-Mestres, T\. G\. Dietterich, O\. Buffet, and I\. ChadèsInterpretable solutions for stochastic dynamic programming\.bioRxiv,pp\. 2024–08\.Cited by:[§1](https://arxiv.org/html/2609.13676#S1.p1.1)\.
- Ferrer\-Mestreset al\.\(2020\)J\. Ferrer\-Mestres, T\. G\. Dietterich, O\. Buffet, and I\. ChadèsSolving k\-mdps\.InProceedings of the 30th International Conference on Automated Planning and Scheduling \(ICAPS\),pp\. 110–118\.Cited by:[Appendix C](https://arxiv.org/html/2609.13676#A3.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2609.13676#S1.p1.1),[§1](https://arxiv.org/html/2609.13676#S1.p2.1),[§2](https://arxiv.org/html/2609.13676#S2.p2.1),[§2](https://arxiv.org/html/2609.13676#S2.p3.1),[§2](https://arxiv.org/html/2609.13676#S2.p6.1),[§3](https://arxiv.org/html/2609.13676#S3.p1.1),[§3](https://arxiv.org/html/2609.13676#S3.p4.1),[§5](https://arxiv.org/html/2609.13676#S5.p1.1)\.
- Marescotet al\.\(2013\)L\. Marescot, G\. Chapron, I\. Chadès, P\. L\. Fackler, C\. Duchamp, E\. Marboutin, and O\. GimenezComplex decisions made simple: a primer on stochastic dynamic programming\.Methods in Ecology and Evolution4\(9\),pp\. 872–884\.Cited by:[§1](https://arxiv.org/html/2609.13676#S1.p1.1)\.
- Marmote development team \(2026\)Marmote development teamMarmote: markovian modelling tools and environments\.Note:Version 1\.3\.1, tandem\-queue control tutorialExternal Links:[Link](https://marmote.gitlabpages.inria.fr/marmote/)Cited by:[Appendix D](https://arxiv.org/html/2609.13676#A4.p2.1)\.
- OpenSourceEconomics \(2026\)OpenSourceEconomicsruspy: infinite\-horizon single\-agent discrete\-choice models and bus\-engine replacement software\.Note:Public software and documentation, accessed 2026External Links:[Link](https://ruspy.readthedocs.io/)Cited by:[Appendix D](https://arxiv.org/html/2609.13676#A4.p2.1)\.
- Péron \(2017\)M\. PéronSimultaneous actions\.rar\.Note:figshare SoftwareExternal Links:[Document](https://dx.doi.org/10.6084/m9.figshare.4557565.v1),[Link](https://doi.org/10.6084/m9.figshare.4557565.v1)Cited by:[Table 2](https://arxiv.org/html/2609.13676#A4.T2.2.2.5.1.1)\.
- Sargent and Stachurski \(2026\)T\. J\. Sargent and J\. StachurskiDynamic programming: inventory\-control model and public code\.Note:QuantEconExternal Links:[Link](https://quantecon.github.io/book-dp1-public-companion/)Cited by:[Appendix D](https://arxiv.org/html/2609.13676#A4.p2.1)\.

## Limitations and scope

The guarantee is limited to the declared A\-KK\-MDP family, divisor window, and tie\-breaking rule; it is not global over arbitrary partitions or alld\>0d\>0\. The repeated budgets are descriptive rather than independent replications, and neither smallKKnor lowJJestablishes human interpretability, ecological validity, or ease of implementation\.

## Code and evidence availability

The accompanying anonymised artifact records the protocols, model identities, candidate and policy hashes, verification scripts, and rows underlying each reported table and figure\.

## Appendix ANon\-monotone feasibility

###### Proposition 1\.

The predicate𝟙\{N\(d\)≤K\}\\mathbb\{1\}\\\{N\(d\)\\leq K\\\}can be non\-monotone inddeven for two states sharing one action, withK=1K=1and nonnegative values\.

###### Proof\.

TakeV∗=\(2,3\)V^\{\*\}=\(2,3\)\. The value bins are\(2,2\)\(2,2\)atd=3/2d=3/2,\(1,2\)\(1,2\)atd=2d=2, and\(1,1\)\(1,1\)atd=3d=3, so feasibility is true, false, then true asddgrows\. A single state givesN⁡\(d\)≡1N\(d\)\\equiv 1, while two states with different optimal actions giveN⁡\(d\)≡2N\(d\)\\equiv 2; both cases are monotone\. Thus the two\-state, shared\-action example is minimal\. ∎

The failure can also change which states are grouped\. WithV∗=\(3,5,8\)V^\{\*\}=\(3,5,8\), one shared action, andK=2K=2, everyd∈\[5/2,3\)d\\in\[5/2,3\)induces

\{\{1,2\},\{3\}\},\\\{\\\{1,2\\\},\\\{3\\\}\\\},whereasd=4d=4induces

\{\{1\},\{2,3\}\}\.\\\{\\\{1\\\},\\\{2,3\\\}\\\}\.Bisecting\[0,8\]\[0,8\]probes4,2,3,7/2,…4,2,3,7/2,\\dotsand converges to the upper feasible region without evaluating the earlier feasible interval \([figure1](https://arxiv.org/html/2609.13676#A1.F1)\)\.

Figure 1:A binary\-search trajectory that misses a feasible interval\. The shaded regions satisfyN⁡\(d\)≤K=2N\(d\)\\leq K=2forV∗=\(3,5,8\)V^\{\*\}=\(3,5,8\)\. After probingd=4,2,3,7/2d=4,2,3,7/2, the search contracts toward44without evaluating\[5/2,3\)\[5/2,3\), whose induced partition differs from the returned partition\.
## Appendix BProof of[theorem1](https://arxiv.org/html/2609.13676#Thmtheorem1)

Fixsswithv=V∗​\(s\)\>0v=V^\{\*\}\(s\)\>0\. Form≥2m\\geq 2,⌈v/d⌉=m\\lceil v/d\\rceil=mexactly whenv/m≤d<v/\(m−1\)v/m\\leq d<v/\(m\-1\); the value is one whend≥vd\\geq v\. Thus⌈v/d⌉\\lceil v/d\\rceilchanges only atd=v/md=v/m\. Atb=v/mb=v/mit equalsmm, immediately left ofbbit equalsm\+1m\+1, and immediately right ofbbit remainsmm\. The coordinate is therefore right\-continuous and constant on each\[βi,βi\+1\)\[\\beta\_\{i\},\\beta\_\{i\+1\}\)\. A state withV∗​\(s\)=0V^\{\*\}\(s\)=0has⌈0/d⌉=0\\lceil 0/d\\rceil=0for alld\>0d\>0and never changes, and every action labelπ∗​\(s\)\\pi^\{\*\}\(s\)is fixed\. Hence the full mapping vector, and so the induced partition, is constant on each half\-open interval; the mapping at the closed endpointRRis evaluated separately\. Canonicalisation relabels blocks by first occurrence, which removes only label permutations of the same equivalence relation, and the deterministic builder, solver, and lift are invariant to those\. Exhaustive comparison over the resulting finite set therefore attains the stated minimum\. ∎

## Appendix CImplementation notes

### Finite candidate bound\.

Forv=V∗​\(s\)\>0v=V^\{\*\}\(s\)\>0, only integers in

⌊vR⌋\+1≤m≤⌈vL⌉−1\\left\\lfloor\\frac\{v\}\{R\}\\right\\rfloor\+1\\leq m\\leq\\left\\lceil\\frac\{v\}\{L\}\\right\\rceil\-1\(3\)contribute breakpoints\. Define

IW:=∑v∈uniq⁡\{V∗​\(s\):V∗​\(s\)\>0\}\|\{m∈ℕ\+:L<vm<R\}\|\.I\_\{W\}:=\\sum\_\{v\\in\\operatorname\{uniq\}\\\{V^\{\*\}\(s\):V^\{\*\}\(s\)\>0\\\}\}\\left\|\\left\\\{m\\in\\mathbb\{N\}\_\{\+\}:L<\\frac\{v\}\{m\}<R\\right\\\}\\right\|\.\(4\)The complete canonical candidate\-family sizeCWC\_\{W\}satisfies

CW≤\|ℬ⁡\(W\)\|≤IW\+2≤\|𝒮\|​⌈VmaxL⌉\+2\.C\_\{W\}\\leq\|\\mathcal\{B\}\(W\)\|\\leq I\_\{W\}\+2\\leq\|\\mathcal\{S\}\|\\left\\lceil\\frac\{V\_\{\\max\}\}\{L\}\\right\\rceil\+2\.\(5\)Only distinct feasible mappings require abstract\-MDP construction and solution\. A candidate evaluation is one such solve;EEis the realised number andEmaxE\_\{\\max\}is a cap, not a realised count\.

### Divisor search versus candidate evaluation\.

EndpointRepairedDivisorSearchis only the divisor\-selection loop of Algorithm 4 in[Ferrer\-Mestres et al\. \[2020\]](https://arxiv.org/html/2609.13676#bib.bib1), augmented to retaind=Vmaxd=V\_\{\\max\}\. Its probes constructϕd\\phi\_\{d\}only to testN⁡\(d\)≤KN\(d\)\\leq K; the abstract MDP for the returned anchor is built later whenϕdb\\phi\_\{d\_\{b\}\}is evaluated as a candidate\.

### Floating\-point implementation\.

[Theorem1](https://arxiv.org/html/2609.13676#Thmtheorem1)is an exact\-arithmetic statement\. In binary64 the midpoint\(βi\+βi\+1\)/2\(\\beta\_\{i\}\+\\beta\_\{i\+1\}\)/2can round toβi\+1\\beta\_\{i\+1\}when consecutive breakpoints are one unit in the last place \(ULP\) apart, so the representative would probe the neighbouring interval\. The implementation therefore evaluates each computed boundary and its two adjacent representable values\. Finite\-precision completeness is defined with respect to the distinct partitions generated under the recorded binary64 convention\. The saved canonical mappings and lifted policies, rather than rounded decimal divisor values, identify the evaluated candidates\.

### Bounded enumeration\.

Before enumerating, the implementation computes the breakpoint\-incidence countIWI\_\{W\}in[equation4](https://arxiv.org/html/2609.13676#A3.E4)\. IfIW≤Imax=100,000I\_\{W\}\\leq I\_\{\\max\}=100\{,\}000, it constructs the complete candidate set and uses the deterministic ordering in[appendixF](https://arxiv.org/html/2609.13676#A6)\. Otherwise, it constructs a deterministic adaptive prefix by repeatedly probing the widest remaining interval inlog⁡d\\log dand evaluates at mostEmax=96E\_\{\\max\}=96candidates\. The realised number of abstract\-MDP solves isE≤EmaxE\\leq E\_\{\\max\}\. A capped run that ends with a positive value gap reportslowest\-gap\-foundand does not claim that every candidate in the window was evaluated\.

### Meaning of the run outcomes\.

A run reportsall\-candidates\-checkedwhen every distinct feasible partition induced within the declared window has been evaluated\. A run may stop earlier withzero\-gap\-foundafter verifyingJ=0J=0, because zero is the lowest possible value gap\. A capped run that ends withJ\>0J\>0reportslowest\-gap\-found; this is the smallest gap among the evaluated candidates but need not be the smallest gap over the complete window\.

## Appendix DModel scope and provenance

[Table2](https://arxiv.org/html/2609.13676#A4.T2)states the exact computational object used in each case\. In particular, “package instance” is not synonymous with reproducing a published table\. Value gap is reported only within a row: different reward scales and discounts make its magnitude incomparable across domains\.

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\.The 12\-row extension uses a 36\-state tandem\-queue controller from Marmote\[[Marmote development team, 2026](https://arxiv.org/html/2609.13676#bib.bib8)\], a 41\-state inventory\-control model from QuantEcon\[[Sargent and Stachurski, 2026](https://arxiv.org/html/2609.13676#bib.bib7)\], and a 90\-state bus\-engine replacement adapter derived from ruspy\[[OpenSourceEconomics, 2026](https://arxiv.org/html/2609.13676#bib.bib9)\]\. The accompanying artifact records the source URLs, revisions, licences, generated arrays, and model hashes used in these experiments\.

## Appendix EEvaluation details and representative results

All comparisons retain the full action set𝒜\\mathcal\{A\}, respect state\-dependent availability, and use the same abstract\-MDP builder, solver, lifting rule, and objective\. The 12\-row extension uses tandem\-queue, inventory\-control, and bus\-replacement models\. Before observing their gaps, we setK0:=\|\{π∗​\(s\):s∈𝒮\}\|K\_\{0\}:=\|\\\{\\pi^\{\*\}\(s\):s\\in\\mathcal\{S\}\\\}\|and fixedK=K0\+⌈q⁡\(\|𝒮\|−K0\)⌉K=K\_\{0\}\+\\lceil q\(\|\\mathcal\{S\}\|\-K\_\{0\}\)\\rceilforq∈\{0,0\.05,0\.10,0\.20\}q\\in\\\{0,0\.05,0\.10,0\.20\\\}\. Windowed improves/ties endpoint\-repaired Binary in 5/3 of the 8 nonzero rows\.

## Appendix FEqual\-budget search comparison

Every comparator starts with Binary and targetsEeff=min⁡\{96,CW\}E\_\{\\mathrm\{eff\}\}=\\min\\\{96,C\_\{W\}\\\}distinct feasible mappings in the same window\. Critical explores endpoints and midpoints of feasible intervals nearestlog⁡db\\log d\_\{b\}first and removes duplicates\. Over the 17\-row subset defined in Results, it outperforms/ties/underperforms the better of log\-grid and the 30\-seed log\-random median in 6/9/2 rows \(Fisheries 4/1/2, Gouldian 1/8/0, SONA 1/0/0\)\. Log\-grid uses a base\-2 van der Corput sequence inlog⁡d\\log d; log\-random samples uniformly in log space for fixed seeds 0–29\. A random seed reaches the in\-window optimum in every informative row\. Thus we claim complete in\-window coverage, not universal search\-order superiority\.

## Appendix GCross\-budget SONA analysis

For the focused SONA analysis, we sweep every integerK∈\{4,…,50\}K\\in\\\{4,\\ldots,50\\\}using the full action set𝒜\\mathcal\{A\}, while respecting state\-dependent action availability, and combine the distinct partitions from all 47 declared windows\. Independently selected windows do not produce a monotone at\-most\-KKresult: the local search attainsJ=0J=0forK=6,…,13K=6,\\ldots,13but has positive value gap atK=14K=14\. Combining the distinct candidates from all declared windows retains a six\-block policy withJ=0J=0and 100% agreement with the tie\-broken ground policy for everyK≥6K\\geq 6\. Thus six blocks are sufficient within the declared collection of windows, but this does not prove that six is minimal over all possible partitions\. The plotted normalised gap is

100​J/max⁡\{maxs∈𝒮⁡\|V∗​\(s\)\|,10−15\};100\\,J/\\max\\\{\\max\_\{s\\in\\mathcal\{S\}\}\|V^\{\*\}\(s\)\|,10^\{\-15\}\\\};for this raw\-native SONA instance the denominator is∥V∗∥∞=10\.666566655282647\\lVert V^\{\*\}\\rVert\_\{\\infty\}=10\.666566655282647\.

Figure 2:SONA worst\-state value gap as a percentage of∥V∗∥∞\\lVert V^\{\*\}\\rVert\_\{\\infty\}, using the full action set𝒜\\mathcal\{A\}\. Independently anchored local Windowed optima are non\-monotone inKK\. Combining candidates across the declared windows first gives zero gap atK=6K=6and retains that policy for every larger budget\.For a fixed finite set of budgets𝒦\\mathcal\{K\}, let𝒞k\\mathcal\{C\}\_\{k\}be the complete candidate family from the declared window atkkand define

𝒞∪:=⋃k∈𝒦\{can⁡\(ϕ\):ϕ∈𝒞k\},J∪​\(K\):=minϕ∈𝒞∪N⁡\(ϕ\)≤K⁡J⁡\(ϕ\)\.\\mathcal\{C\}^\{\\cup\}:=\\bigcup\_\{k\\in\\mathcal\{K\}\}\\\{\\operatorname\{can\}\(\\phi\):\\phi\\in\\mathcal\{C\}\_\{k\}\\\},\\qquad J^\{\\cup\}\(K\):=\\min\_\{\\begin\{subarray\}\{c\}\\phi\\in\\mathcal\{C\}^\{\\cup\}\\\\ N\(\\phi\)\\leq K\\end\{subarray\}\}J\(\\phi\)\.\(6\)Exhausting every declared window gives the exact minimum over this fixed union, andJ∪​\(K\)J^\{\\cup\}\(K\)is non\-increasing because the eligible set can only grow withKK\. This is not an optimum over arbitrary partitions\.

## Appendix HOptional action\-set sensitivity

This appendix experiment is separate from the core A\-KK\-MDP formulation\. AtK=50K=50, for eachBAB\_\{A\}we exhaustively compare every retained action set𝒰⊆𝒜\\mathcal\{U\}\\subseteq\\mathcal\{A\}with\|𝒰\|≤BA\|\\mathcal\{U\}\|\\leq B\_\{A\}and𝒰∩𝒜⁡\(s\)≠∅\\mathcal\{U\}\\cap\\mathcal\{A\}\(s\)\\neq\\varnothingfor everyss\. We solve each restricted ground MDP and use𝒜ϕ,𝒰​\(k\):=𝒰∩⋂s∈Bk𝒜⁡\(s\)\\mathcal\{A\}\_\{\\phi,\\mathcal\{U\}\}\(k\):=\\mathcal\{U\}\\cap\\bigcap\_\{s\\in B\_\{k\}\}\\mathcal\{A\}\(s\)in its abstract MDP, reporting the lowest gap attained within the corresponding declared local windows\. I, AP, C, and H denote introduction, antipoaching, control, and half AP/control\. Windowed ties Binary atBA=2B\_\{A\}=2and reduces value gap by 27\.0% and 60\.6% atBA=3B\_\{A\}=3andBA=4B\_\{A\}=4, respectively\. Because the methods may select different action sets, these results are not directly comparable with the main\-text experiment using the full action set𝒜\\mathcal\{A\}\.

Table 3:Optional SONA action\-set sensitivity atK=50K=50, exhaustive over feasible retained action sets𝒰⊆𝒜\\mathcal\{U\}\\subseteq\\mathcal\{A\}satisfying\|𝒰\|≤BA\|\\mathcal\{U\}\|\\leq B\_\{A\}and the corresponding declared local Windowed families\. This experiment is separate from the core state\-budget comparison\.