The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability

Anthony T. Nixon

cs.AIMar 22, 2026

The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability

Authors: Anthony T. Nixon

Organizations: DefSig

Abstract

Any capacity-limited observer induces a canonical quotient on its environment: two situations that no bounded agent can distinguish are, for that agent, the same. We formalise this for finite POMDPs. A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories and a probe-exact quotient merging histories that no controller in the family can distinguish. The quotient is canonical, minimal, and unique-a bounded-interaction analogue of the Myhill-Nerode theorem. For clock-aware probes, it is exactly decision-sufficient for objectives that depend only on the agent's observations and actions; for latent-state rewards, we use an observation-Lipschitz approximation bound. The main theorem object is the clock-aware quotient; scalable deterministic-stationary experiments study a tractable coarsening with gap measured on small exact cases and explored empirically at larger scale. We validate theorem-level claims on Tiger and GridWorld. We also report operational case studies on Tiger, GridWorld, and RockSample as exploratory diagnostics of approximation behavior and runtime, not as theorem-facing evidence when no exact cross-family certificate is available; heavier stress tests are archived in the appendix and artifact package.

Figures & tables

Panel of Figure 1 — Figure 1: (a) Any system with hidden state, an observation channel, and a bounded observer $(m,T,\delta_{O})$ admits a canonical quotient—a minimal equivalence over situations the observer cannot distinguish. (b) The POMDP instantiation: observation histories are probed by all bounded FSCs; pairwise $\mathcal{W}_{1}$ distances (maximised over policies) are clustered; the quotient POMDP preserves all observation laws with certified value loss.

Panel of Figure 2 — Figure 2: Refinement lattice for Tiger ( $T{=}4$ ). Solid arrows: increasing $\varepsilon$ coarsens the quotient (Definition 5.1 ). Dashed arrows: increasing $m$ refines the quotient (Proposition 4.11 —larger probe class $\Rightarrow$ finer partition). Data from operational capacity sweep.

Tier	Representative results	What the tier supports	Certificate type
Tier I: theorem-aligned exact	Tables 2 , 3 , 4	Theorem-level statements about $Q^{\mathrm{clk}}_{m,T}$ on the stated bounded exact cases, including measured cross-family transfer on tractable exact instances	Exhaustive clock-aware enumeration on the stated finite benchmark and horizon
Tier II: operational exact-for-family	Table 5	Exact statements about the operational family $Q^{\mathrm{op}}_{m,T}$ and controller-subset certification within that family	Full deterministic-stationary FSC tensor together with reported $\delta_{S}$ certificate
Tier III: operational empirical scaling	Tables 6 , 13 , 10 , 11	Compression, stability, and runtime evidence for the tractable operational quotient $Q^{\mathrm{op}}_{m,T}$ ; not theorem validation for $Q^{\mathrm{clk}}_{m,T}$ unless an explicit bridge is reported	Sampling confidence intervals, ARI checks, runtime reporting, and explicit disclosure when no theorem-level certificate is available

Table 1: Evidence tiers used in the experiments section. This is the claim-to-evidence contract for the empirical narrative.

Benchmark	$T$	$\|Q^{\mathrm{op}}\|$	$\|Q^{\mathrm{clk}}\|$	ARI	$\max_{h,h^{\prime}}\|d^{\mathrm{clk}}-d^{\mathrm{op}}\|$	Obs. value changed?
Tiger	2	4	4	1.000	0.490	No
Tiger	4	11	16	0.961	1.315	No
Tiger	6	22	64	0.953	2.077	No
Tiger	8	37	256	0.956	2.795	No
Tiger	10	56	1024	0.959	3.499	No
GridWorld 3x3	2	6	6	1.000	0.347	No

Table 2: Exact comparison between the theorem-level clock-aware quotient and the operational deterministic-stationary quotient. The stationary witness row is the didactic separation guaranteed by Proposition 4.10 . The column

\max|d^{\mathrm{clk}}-d^{\mathrm{op}}|

reports the largest absolute pairwise

\mathcal{W}_{1}

difference (unnormalized); values exceeding

1

arise because the sequence-level metric sums contributions over

T

time steps.

Benchmark	Obj.	$T$	Hist.	Cls.	$t_{\mathrm{orig}}$	$t_{Q^{\mathrm{clk}}}$	Policy	$V_{\mathrm{orig}}$	$V_{Q^{\mathrm{clk}}}$
Tiger	Obs score	2	7	4	0.000	0.000	L L	1.000	1.000
Tiger	Action+obs score	2	7	4	0.000	0.000	OL OL	1.000	1.000
Tiger	Obs score	4	31	16	0.001	0.003	L L L L	2.000	2.000
Tiger	Action+obs score	4	31	16	0.001	0.003	OL OL OL OL	2.000	2.000
Tiger	Obs score	6	127	64	0.008	0.132	L L L L L L	3.000	3.000
Tiger	Action+obs score	6	127	64	0.009	0.139	OL OL OL OL OL OL	3.000	3.000

Table 3: Exact preservation of bounded observation-action objectives under the clock-aware quotient

Q^{\mathrm{clk}}_{m,T}

Benchmark	Reward	$T$	Hist.	Cls.	$t_{\mathrm{orig}}$	$t_{Q^{\mathrm{clk}}}$	Policy	$V_{\mathrm{orig}}$	$V_{Q^{\mathrm{clk}}\rightarrow M}$
Tiger	Tiger reward	2	7	4	0.000	0.000	L L	-2.000	-2.000
Tiger	Tiger reward	4	31	16	0.000	0.009	L L L L	-4.000	-4.000
Tiger	Tiger reward	6	127	64	0.005	0.386	L L L L L L	-6.000	-6.000
Tiger	Tiger reward	8	511	256	0.061	19.515	L L L L L L L L	-8.000	-8.000
Tiger	Tiger reward	10	2047	1024	0.663	1549.370	L L L L L L L L L L	-10.000	-10.000
GridWorld 3x3	Goal reward	2	21	6	0.000	0.001	D U	0.311	0.311

Table 4: Latent-state planning impact on clock-aware exact cases. Values are reported on the original model; regret is relative to the original-model optimum.

Benchmark	$\varepsilon$	$k$	$\delta_{S}$	Op. exact classes	Approx. classes	ARI
Tiger ( $T{=}4$ )	0.0	1	0.980	16	11	0.961
Tiger ( $T{=}4$ )	0.0	3	0.245	16	15	0.994
Tiger ( $T{=}4$ )	0.0	5	0.000	16	16	1.000
GridWorld $3{\times}3$ ( $T{=}2$ )	0.3	1	0.233	6	4	0.981
GridWorld $3{\times}3$ ( $T{=}2$ )	0.3	3	0.000	6	6	1.000
GridWorld $3{\times}3$ ( $T{=}2$ )	0.3	5	0.000	6	6	1.000

Table 5: Operational partition recovery and probe-envelope certification on the deterministic-stationary

m{=}2

benchmarks. Here

\delta_{S}:=\|d-d_{S}\|_{\infty}

is an a posteriori certificate computed from the full deterministic-stationary FSC tensor.

Benchmark	$\|S\|$	$\varepsilon{=}0$	$\varepsilon{=}0.1$	$\varepsilon{=}0.25$	$\varepsilon{=}0.45$	Cache (s)	95% CI on $\max\mathcal{W}_{1}$
GridWorld $8{\times}8$	64	6	6	4	3	0.28	$[0.32,\,0.41]$
GridWorld $10{\times}10$	100	6	6	4	3	0.30	$[0.33,\,0.42]$
RockSample $(4,4)$	257	5	5	4	3	0.48	$[0.35,\,0.47]$
Random $\|S\|{=}50$	50	6	3	3	3	0.22	$[0.02,\,0.11]$
Random $\|S\|{=}100$	100	6	3	3	3	0.35	$[0.02,\,0.11]$

Table 6: Operational quotient class counts (

m{=}1

T{=}2

, sampling-based,

500

trajectories). The 95% CI column reports the bootstrap confidence interval on

\max_{h,h^{\prime}}\mathcal{W}_{1}

(

1{,}000

resamples). Total histories are

\sum_{d=0}^{T}|O|^{d}

21

for

|O|{=}4

benchmarks,

13

for

|O|{=}3

(RockSample).

Benchmark	$\|S\|$	Quotient $\|S\|$	PBVI orig (s)	PBVI quot (s)	Speedup
Tiger	2	3	0.001	0.001	$\sim 1{\times}$
GridWorld $3{\times}3$	9	6	0.003	0.002	$1.9{\times}$
GridWorld $5{\times}5$	25	5	0.008	0.003	$2.4{\times}$
Net. Monitor ( $n{=}4$ )	16	4	0.005	0.002	$2.1{\times}$
RockSample $(4,4)$	257	3	0.092	0.004	$15{\times}$

Table 7: PBVI planning on original vs. quotient POMDPs (

m{=}1

T{=}3

\varepsilon{=}0.5

). Speedup is measured as original PBVI time divided by total quotient pipeline time (partition + build + quotient PBVI).

Appendix figures & tables27 assets

Supplementary material from the paper’s appendix.

Appendix

Dimension	State bisimulation	PSRs / OOMs	This work
Abstraction target	States	Predictive statistics	Observation histories
Distinguishing power	All policies / actions	Open-loop test sequences	Bounded $(m,T)$ controller family
Comparison object	One-step transitions	Linear predictors	Finite-horizon observation laws
Loop type	Open-loop (per-action)	Open-loop	Closed-loop
Quotient output	State partition	Low-rank representation	History partition $\to$ quotient POMDP

Appendix

Table 8: Comparison of abstraction frameworks along key structural dimensions.

Panel of Figure 3 — Figure 3: Tiger POMDP quotient structures for $m=1$ , $T=2$ . Left: operational exact-for-family quotient (7 classes). Right: $\varepsilon=0.5$ quotient merges $L$ and $R$ (3 classes).

Tier	Verification target	Command / artifact path	Serial budget and role
I	Theorem tables plus operational core through Table 6	pythonpaper/generate_theory_first_tables.py and python-mexperiments.run_basic_results--profilequick--seed7--no-parallel	${<}3$ min; intended reviewer verification target.
II	Long-horizon extension (Tables 10 , 11 , Figures 4 , 5 )	Add --include-hierarchical-scaling--max-horizon10 to the operational driver	${\sim}10$ min serial; horizon-scaling narrative only.
III	Heaviest stress rows (Tables 13 , 14 )	Same driver for rerunning; artifact-only: pythonartifacts/tier3/verify_tier3_artifacts.py	$5$ – $30$ s per row, up to 2 h for largest $m{=}2$ ; archival. Verifier: ${<}1$ s.

Appendix

Table 9: Three-tier reproduction contract. Tier I is the intended fast verification target for the paper’s core claims; Tiers II–III are optional extensions for stress-testing the operational pipeline.

$T$	Method	Segment $\tau$	Layers $L$	Runtime (s)	Histories processed
4	Direct	–	1	0.05	31
4	Layered	4	1	0.05	31
6	Direct	–	1	0.96	127
6	Layered	4	2	0.05	38
8	Direct	–	1	16.42	511
8	Layered	4	2	0.10	62

Appendix

Table 10: Operational direct vs. layered runtime on Tiger full-actions (

m{=}1

\varepsilon{=}0.5

, deterministic-stationary probe family).

$T$	Method	FSCs used	Runtime (s)	Classes	ARI vs. full
4	Full op.-exact	147	2.53	10	1.000
5	Full op.-exact	147	10.95	16	1.000
6	Full op.-exact	147	46.11	30	1.000
7	Full op.-exact	147	194.27	50	1.000
7	Calibrated subset (empirical)	10	12.96	50	0.9997
8	Calibrated subset (empirical)	10	53.69	77	–

Appendix

Table 11: Operational exact-for-family and empirical calibrated-subset horizon scaling on Tiger full-actions (

m{=}2

\varepsilon{=}0.5

). The calibrated-subset rows reuse a

k{=}10

subset chosen at

T{=}6

and do not carry a full

\delta_{S}

certificate.

Figure 4: Operational runtime scaling with horizon (log scale): monolithic, layered, and empirical calibrated-subset tracks.

Figure 5: Layered bound validation (Theorem 5.6 ). Each bar compares the empirical LHS distortion (blue) against the theoretical RHS bound (orange) for eight test cases spanning single-layer reduction, wrapper contraction (deterministic and stochastic), and long-horizon theorem bounds ( $T\in\{4,8,10\}$ ). All checks satisfy LHS $\leq$ RHS.

Dimension	Growth	Technique	Demonstrated
States $\|S\|$	$O(\|S\|^{2})$ per belief	Sampling-based $\mathcal{W}_{1}$	$\|S\|{=}4{,}096$ (sampling), $\|S\|{=}100$ (sampling)
FSCs $\|\mathcal{F}\|$	$\|A\|^{m}m^{m\|O\|}$	Greedy FSC subsets	Certified: $6{,}405\to 5$ , $147\to 5$ $m{=}2$ scaling: $5{,}193$ FSCs on RockSample Empirical: $147\to 10$ calibrated subset
Histories $\|O\|^{T}$	Exp. in $T$	Layered horizon decomposition	Direct to $T{=}10$ ; layered to $T{=}20$
Observations $\|O\|$	$\|O\|^{T}$ histories	$\delta_{O}$ -coarsening (Prop. 5.5 )	GridWorld $4\to 2$ obs

Appendix

Table 12: Scalability: each complexity dimension and how it is addressed, separating operational exact-for-family benchmark certification from empirical long-horizon calibrated subsets.

Track	Benchmark	$\|S\|$	$\|O\|$	$T$	Method	$\varepsilon{=}0$	$\varepsilon{=}0.3$	Runtime (s)	95% CI on $\max\mathcal{W}_{1}$
Scale-up	Net. Mon. ( $n{=}12$ )	4,096	3	2	Sampling	13	5	$\sim 5$	$[0.31,\,0.43]$
Large $\|O\|$	Random	2,000	10	2	Sampling	111	10	$\sim 30$	$[0.10,\,0.20]$
Long $T$	Net. Mon. ( $n{=}10$ )	1,024	3	20	Layered	13	5	$\sim 25$	$[0.67,\,0.84]$

Appendix

Table 13: Meaningful-scale experiments: sampling-based and layered quotient construction (

m{=}1

500

trajectories). The 95% CI column reports the bootstrap confidence interval on

\max_{h,h^{\prime}}\mathcal{W}_{1}

(

1{,}000

resamples); for the layered track, the CI is on the segment-level (

\tau{=}4

) cache.

Benchmark	$\|S\|$	$m$	$T$	FSCs	$\varepsilon{=}0$	$\varepsilon{=}0.1$	$\varepsilon{=}0.3$	$\varepsilon{=}0.5$	Runtime (s)	95% CI on $\max\mathcal{W}_{1}$
RockSample $(4,4)$	257	1	2	9	5	5	4	3	0.5	$[0.35,\,0.47]$
RockSample $(4,4)$	257	2	2	5,193	5	5	5	5	321	$[1.00,\,1.00]$
Net. Mon. ( $n{=}4$ )	16	1	3	5	14	9	6	5	1.1	$[0.48,\,0.66]$
Net. Mon. ( $n{=}4$ )	16	2	3	1,605	14	14	14	6	353	$[0.67,\,0.84]$
Net. Mon. ( $n{=}9$ )	512	1	2	10	5	5	4	3	11	$[0.28,\,0.40]$
Net. Mon. ( $n{=}9$ )	512	2	2	6,410	5	5	5	3	6,802	$[0.39,\,0.49]$

Appendix

Table 14: Probe-family scaling:

m{=}1

vs.

m{=}2

quotient class counts at medium scale (sampling-based,

500

trajectories). The 95% CI column reports the bootstrap confidence interval on

\max_{h,h^{\prime}}\mathcal{W}_{1}

(

1{,}000

resamples).

$m$	$\varepsilon$	Classes	Compression	Policies
1	0.0	6	0.29	5
1	0.2	5	0.24	5
1	0.35	3	0.14	5
1	0.5	3	0.14	5
2	0.0	6	0.29	6,405
2	0.2	6	0.29	6,405

Appendix

Table 15: Quotient class counts for GridWorld

3\times 3

(

|S|=9

T=2

). Total histories:

21

$\varepsilon$	Empirical error	$D_{m,T}^{\mathcal{W}}$	$L_{R}T\varepsilon$	$L_{R}TD$	Prop A.1
Panel A: Tiger, synthetic $L_{R}{=}1$
0.0	$\approx 0$	0.00	0.00	0.00	0.0
0.1	$\approx 0$	0.00	0.20	0.00	3.4
0.3	$\approx 0$	0.00	0.60	0.00	10.2
0.5	0.12	0.24	1.00	0.49	17.0
Panel B: Tiger, standard reward $L_{R}{=}110$ (vacuous)

Appendix

Table 16: Value-function error bounds across reward scales. Panel A: Tiger full actions with synthetic

L_{R}{=}1

reward (tight bounds). Panel B: Tiger with standard reward

L_{R}{=}110

(vacuous—bound exceeds reward range). Panel C: GridWorld

3{\times}3

goal reward

L_{R}\approx 2

(moderate—informative bound at small

\varepsilon

). All use

m{=}1

T{=}2

. The column

L_{R}T\varepsilon

is the provable bound from Theorem 3.6 ; the column

L_{R}TD

reports the tighter empirical proxy

L_{R}\cdot T\cdot D_{m,T}^{\mathcal{W}}

, which is always valid but follows from the partition construction only when

D_{m,T}^{\mathcal{W}}\leq\varepsilon

(observed in all tested configurations at

\varepsilon>0

$\varepsilon$	Min cl.	Max cl.	Min val. err.	Max val. err.
0.0	7	7	0.000	0.000
0.2	5	7	0.000	0.000
0.4	3	7	0.000	0.108
0.6	3	3	0.058	0.145

Appendix

Table 17: Noise sensitivity (Tiger,

m=1

T=2

). Range over accuracy

\in\{0.70,0.75,0.80,0.85,0.90,0.95\}

Benchmark	Method	$\varepsilon$	Classes	Val. err.	$D_{m,T}^{\mathcal{W}}$	Time (s)
Tiger full actions
	$\varepsilon$ -quotient	0.3	4	0.000	0.000	$\ast$
	Truncation ( $d{=}1$ )	0.3	5	0.000	0.000	$<0.01$
	Random partition	0.3	3.7	0.041	0.082	$<0.01$
	Belief-distance	0.3	6	0.000	0.000	$<0.01$
	Bisimulation	0.3	6	0.000	0.000	0.05

Appendix

Table 18: Full baseline comparison (

m=1

T=2

), both benchmarks.

Ablation	Variant	Classes ( $\varepsilon{=}0.3$ )	Note
Metric	$\mathcal{W}_{1}$ (discrete $d_{O}$ )	7	Default
	TV-equivalent	7	Same on Tiger (binary $O$ )
Memory	$m=1$ (3 FSCs)	7	Coarser
	$m=2$ (147 FSCs)	14	Finer, 0 value error
Approx.	Full enum. (147 FSCs)	14	Exact
	Greedy $k{=}5$	14	ARI $=1.0$ , $2.1\times$ faster

Appendix

Table 19: Ablation studies (Tiger full actions,

T=2

Benchmark	$m$	Depth	FSCs	Rank (90%)	Rank (95%)	Rank (99%)
Tiger ( $T{=}4$ )	1	3	3	1	1	1
Tiger ( $T{=}4$ )	2	3	147	3	4	7
Grid $3{\times}3$ ( $T{=}2$ )	1	1	5	1	2	4
Grid $3{\times}3$ ( $T{=}2$ )	2	1	6,405	2	3	5

Appendix

Table 20: Effective rank of the FSC distinguishing matrix.

Benchmark	$T$	$\varepsilon{=}0$	$0.1$	$0.2$	$0.3$	$0.5$	$0.6$
Grid $5{\times}5$	2	6	6	5	4	3	3
Grid $5{\times}5$	3	22	16	12	9	6	5
Random $\|S\|{=}20$	2	6	3	3	3	3	3
Random $\|S\|{=}20$	3	22	4	4	4	4	4

Appendix

Table 21: Quotient class counts for larger POMDPs (

m=1

). Total histories:

21

(

T{=}2

85

(

T{=}3

Grid	$\|S\|$	Classes	Compression	Time (s)
$3\times 3$	9	4	$0.19$	0.03
$4\times 4$	16	4	$0.19$	0.04
$5\times 5$	25	4	$0.19$	0.05
$6\times 6$	36	4	$0.19$	0.07

Appendix

Table 22: Scaling: wall-clock time vs. state-space size (GridWorld,

T{=}2

m{=}1

\varepsilon{=}0.3

Experiment	Time (s)
Tiger reproduction	$<0.1$
Capacity sweep	$0.5$ – $1.0$
Value loss bounds	$0.3$ – $0.5$
Metric sensitivity	$1.0$ – $2.0$
Baseline comparison	$0.5$ – $1.0$
Low-rank analysis	$0.5$ – $2.0$

Appendix

Table 23: Wall-clock time per experiment (quick profile, single CPU core).

Benchmark	$\|S\|$	$m$	FSCs	Enum (s)	Cache (s)	Cache %
Tiger	2	1	3	${<}0.01$	$0.004$	$99.0$
GridWorld $3{\times}3$	9	1	5	${<}0.01$	$0.034$	$99.8$
RockSample(4,4)	257	1	9	${<}0.01$	$0.472$	$100.0$

Appendix

Table 24: Pipeline stage breakdown (single CPU core,

m{=}1

T{=}2

). Distance cache (

\mathcal{W}_{1}

LP solves) dominates in all non-trivial cases.

Trajectories	Mean ARI	Min ARI	Replications
50	0.991	0.961	5
100	0.994	0.971	5
250	0.994	0.971	5
500	0.998	0.971	5
1,000	0.994	0.971	5

Appendix

Table 25: Operational sampling convergence on GridWorld

3{\times}3

(

m{=}1

T{=}2

5

replications per sample count, averaged over

\varepsilon\in\{0,0.3,0.5\}

). Minimum ARI stabilizes by

100

trajectories.

$\varepsilon$	Mean classes	Min	Max
0.0	6.0	6	6
0.1	6.0	6	6
0.25	4.0	4	4
0.45	3.0	3	3

Appendix

Table 26: Partition stability: class counts across

10

independent random seeds (GridWorld

10{\times}10

|S|{=}100

m{=}1

T{=}2

500

trajectories).

Trajectories	Coverage	Mean CI width
100	$97.0\%$	$0.199$
250	$96.5\%$	$0.127$
500	$96.0\%$	$0.090$

Appendix

Table 27: Empirical coverage of 95% bootstrap CIs on

\max_{h,h^{\prime}}\mathcal{W}_{1}

(GridWorld

3{\times}3

m{=}1

T{=}2

200

replications).

Benchmark	$\|S\|$	$\|A\|$	$\|O\|$	$\varepsilon{=}0$	$\varepsilon{=}0.3$	$\varepsilon{=}0.5$
Hallway ( $L{=}10$ )	10	3	3	5	5	3
Hallway ( $L{=}20$ )	20	3	3	5	5	3
Network ( $n{=}4$ )	16	5	3	5	4	3
Network ( $n{=}5$ )	32	6	3	5	4	3

Appendix

Table 28: Quotient class counts on additional benchmarks (

m{=}1

T{=}2

). Total histories:

13

Benchmark	$m$	$\varepsilon$	Policies	Classes	$V^{*}_{\text{orig}}$	Value gap
Tiger	1	0.0	3	4	0.373	0.000
Tiger	1	0.3	3	4	0.373	0.000
Tiger	1	0.5	3	3	0.373	0.000
Tiger	2	0.3	147	4	0.373	0.000
Tiger	2	0.5	147	3	0.373	0.000
Hallway	1	0.0	3	5	0.262	0.000

Appendix

Table 29: Planning on original vs. quotient: value gap under exhaustive policy search (

T{=}2

$b_{0}(s_{L})$	$\varepsilon{=}0$ (classes / ARI)	$\varepsilon{=}0.3$ (classes / ARI)	$\varepsilon{=}0.5$ (classes / ARI)
0.5	4 / 1.00	4 / 1.00	3 / 1.00
0.3	4 / 1.00	4 / 1.00	3 / 1.00
0.1	4 / 1.00	3 / 0.89	3 / 1.00
0.7	4 / 1.00	4 / 1.00	3 / 1.00
0.9	4 / 1.00	3 / 0.89	3 / 1.00

Appendix

Table 30: Partition stability under initial-belief perturbation (Tiger full actions,

m{=}1

T{=}2

). ARI measured against the uniform-belief (

b_{0}=[0.5,0.5]

) partition.

Symbol	Meaning
$M=\langle S,A,O,P,Z,R,b_{0}\rangle$	Finite POMDP
$S,A,O$	State, action, observation sets
$P(s,a,s^{\prime})$	Transition kernel $\mathbb{P}(s^{\prime}\mid s,a)$
$Z(s^{\prime},a,o)$	Observation kernel $\mathbb{P}(o\mid s^{\prime},a)$
$R(s,a)$	Reward function
$b_{t}\in\Delta(S)$	Belief state at time $t$

Appendix

Table 31: Principal notation.

Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes study sequential decisions when agents must act from incomplete, noisy observations of hidden states.

See all 88 papers

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs
Sep 8, 2026Xiangwu Wang, Chengwei Cao, Hongyuan TangMulti-Agent System Optimization Multi-Agent Coordination
University of Hong Kong · University of California, San Diego · Carnegie Mellon University
Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment
Apr 10, 2026Anthony T. NixonMulti-Agent Communication Task-Oriented Semantic Communication
Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes
Jul 29, 2026Zuyuan Zhang, Yongshan Chen, Mahdi Imani +1Markov Decision Processes Partially Observable RL
Department of Electrical and Computer Engineering, The George Washington University · Department of Electrical and Computer Engineering, Northeastern University

Sep 8, 2026J/K move · Enter open · S save

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

Xiangwu Wang, Chengwei Cao, Hongyuan Tang

University of Hong Kong · University of California, San Diego · Carnegie Mellon University

Multi-Agent System Optimization Multi-Agent Coordination Multi-Agent Planning

Open paper AskPDF arXiv

Persistent communication limits force a multi-agent system to decide which agents may coordinate throughout a rollout. Current proximity alone is insufficient: separated agents may interact later, whereas a large pair reward may remain unreachable until it is heavily discounted. We introduce Reachability-Certified Subteam Decomposition (RCSD) for finite multi-agent Markov decision processes with factorized physical dynamics, finite-range ordered pair rewards, and almost-sure motion bounds. RCSD combines a speed-limit lower bound on pairwise contact time with a reward envelope to form a current-state affinity. For any capacity-valid persistent partition, the sum of cut affinities bounds the reward-deletion error of every unchanged stationary Markov state-feedback policy. A product of team-optimal policies for the resulting cut MDP incurs at most twice this certificate in regret against the centralized optimum. Both bounds are worst-case tight. On a controlled five-agent family, RCSD-Exact reduces aggregate normalized execution regret by 56.0%, 28.8%, and 25.3% relative to uniform, distance-only, and envelope-only partitions. A separate stochastic two-dimensional study finds no bound violation over 384 exact-partition and 1,440 restricted-controller evaluations. Exact four-agent evidence favors RCSD over uniform and distance-only grouping; raw evidence for current contact is borderline and envelope-only is unresolved. Across balanced 8-20-agent strata, controller-library utility is mixed: pointwise paired intervals favor RCSD over distance and current contact, include zero for uniform, and favor envelope-only and Value-MIP over RCSD. Partition construction remains subsecond in median up to 100 agents; this last result does not include affinity formation or MDP planning.

Abstract

Partially Observable Markov Decision Processes

Explore similar work

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment

Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes