analiza aiqbench
This research addresses a critical gap in offline reinforcement learning by providing formal proofs and an algorithm (PEC) to verify the distinguishability assumption required for modeling non-Markovian environments as Regular Decision Processes. The work demonstrates that existing guarantees often fail when this assumption is violated, offering a rigorous method to restore validity even when policies visit every automaton state. By verifying these results in Lean 4, the authors establish a high standard of formal correctness for theoretical advances in sequential decision-making under complex dynamics.
Exact Distinguishability in Non-Markovian Decision Processes
arXiv:2610.01527v1 Announce Type: cross Abstract: Non-Markovian environments are often modeled as Regular Decision Processes (RDPs), where dynamics depend on the interaction history through a finite automaton. Existing offline guarantees for RDPs rely on a distinguishability assumption on the behaviour policy but provide no means of verifying it. When the assumption is violated, distinct models may explain the data equally well. We study when data collected under a fixed behaviour policy can distinguish two candidate RDPs. We prove that the posterior odds between observationally equivalent candidates remain equal to the prior odds at every sample size, even when the policy visits every automaton state, and verify both results formally in Lean 4. We then characterize this equivalence exactly and derive PEC, an algorithm that decides it in time linear in the size of the product automaton. The distinguishability assumption of prior work fails on three of our four test environments, and the experiment identified by PEC restores it in each case.
Abstract:Non-Markovian environments are often modeled as Regular Decision Processes (RDPs), where dynamics depend on the interaction history through a finite automaton. Existing offline guarantees for RDPs rely on a distinguishability assumption on the behaviour policy but provide no means of verifying it. When the assumption is violated, distinct models may explain the data equally well. We study when data collected under a fixed behaviour policy can distinguish two candidate RDPs. We prove that the posterior odds between observationally equivalent candidates remain equal to the prior odds at every sample size, even when the policy visits every automaton state, and verify both results formally in Lean 4. We then characterize this equivalence exactly and derive PEC, an algorithm that decides it in time linear in the size of the product automaton. The distinguishability assumption of prior work fails on three of our four test environments, and the experiment identified by PEC restores it in each case.
26 pages, 7 figures. Code and Lean 4 proofs: this https URL
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
arXiv:2610.01527 [cs.LG]
(or arXiv:2610.01527v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.01527 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 267 cuvinte
