🤖 AI

dtControl2+ $\varepsilon$ : Trading Optimality for Explainability in MDPs via Decision Trees

Dit artikel introduceert dtControl2+ $\varepsilon$ , een uitbreiding van de geavanceerde tool dtControl2 die aanzienlijk kleinere en meer menselijk begrijpelijke beslisboomcontrollers voor Markov-beslissingsprocessen genereert door een controleerbare hoeveelheid optimaliteit ( $\varepsilon$ ) in te ruilen voor verbeterde verklaarbaarheid.

Oorspronkelijke auteurs: Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, Maximilian Weininger

Gepubliceerd 2026-07-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, Maximilian Weininger

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren hoe hij door een doolhof moet navigeren. In de wereld van de informatica wordt dit "controller synthesis" genoemd. Je geeft de robot een reeks regels en een doel, en een computerprogramma berekent de perfecte zetten om daar te komen. Maar hier komt de crux: voor complexe doolhoven spuugt de computer vaak een enorme, rommelige lijst met instructies uit—één voor elke vierkante meter waar de robot ooit terecht zou kunnen komen. Het is alsof je een kookboek hebt van een miljoen pagina's, waarbij elke pagina alleen zegt: "draai links" of "draai rechts" voor een specifiek, minuscuul moment. Hoewel deze lijst wiskundig gezien perfect is, is het voor een mens onmogelijk om te lezen, laat staan te begrijpen. Als de robot crasht, kan niemand naar die gigantische lijst kijken en zeggen: "Ah, ik zie het, hij draaide links omdat hij in de war was door de rode muur." We hebben deze instructies nodig die kort, simpel en uitlegbaar zijn, als een duidelijke kaart in plaats van een gigantisch spreadsheet.

Dit is waar "beslissingsbomen" (decision trees) om de hoek komen kijken. Denk aan een beslissingsboom als een stroomdiagram of een spelletje "20 vragen". In plaats van een enorme lijst, heb je een eenvoudige structuur: "Als de muur links is, ga naar rechts; anders, ga rechtdoor." Dit zijn veel gemakkelijker te begrijpen voor mensen. Echter, zelfs deze bomen kunnen te groot en ingewikkeld worden als de robot te maken krijgt met lastige situaties of zeldzame "randgevallen" (corner cases). De grote vraag die onderzoekers zich stellen is: Kunnen we deze bomen nog kleiner en simpeler maken zonder dat de robot crasht? Het antwoord ligt in een concept genaamd "epsilon-optimaliteit". Stel je voor dat je tegen de robot zegt: "Je hoeft niet 100% perfect te zijn; je mag 99,9% perfect zijn." Deze kleine mate van toegestane imperfectie geeft de robot (en de computer) de vrijheid om minuscule, onwaarschijnlijke details te negeren, wat resulteert in een veel kortere, schonere set instructies die nog steeds veilig de taak volbrengt.

Dit is waar de paper "dtControl 2+ε: Trading Optimality for Explainability in MDPs via Decision Trees" een nieuw hulpmiddel introduceert genaamd dtControl 2+ε dat precies dit doet. De onderzoekers hebben, werkend met Markov Decision Processes (een chique wiskundige manier om systemen met willekeur te beschrijven, zoals een robot die kan uitglijden op een natte vloer), een systeem gebouwd dat een complexe, perfecte controller neemt en deze inkrimpt tot een kleine, voor mensen leesbare beslissingsboom. Ze doen dit door een kleine, gecontroleerde hoeveelheid fout ( $\epsilon$ ) toe te laten.

Zo werkt hun magie: In plaats van elke individuele beweging van de robot te proberen uit te leggen, kijkt het hulpmiddel naar de kaart en vraagt: "Welke bewegingen doen er echt toe?" Als een robot zich in een plek bevindt waar hij bijna zeker nooit naartoe zal gaan, of waar elke beweging die hij maakt tot hetzelfde resultaat leidt, zegt het hulpmiddel: "Laten we dat deel overslaan met uitleggen." Het destilleert de controller terug naar de "essentie". In een test met een robot op een heuvel had de perfecte controller tientallen complexe regels. Het nieuwe hulpmiddel, dat een kleine fout van slechts 0,001 toeliet, reduceerde de instructies tot slechts vijf knooppunten (de beslispunten in de boom). De resulterende regel was prachtig simpel: "Ga omhoog naar de top, ga naar rechts naar de rand, en ga dan naar beneden." Het was niet in elk microscopisch scenario wiskundig perfect, maar het was zo dicht bij perfect dat het verschil verwaarloosbaar was, en het was iets dat een mens binnen enkele seconden kon begrijpen.

Het team heeft hun hulpmiddel getest tegen andere state-of-the-art methoden en vond dat het een enorme verbetering was. In veel gevallen produceerde hun hulpmiddel beslissingsbomen die orders van grootte kleiner waren dan de concurrentie. Sterker nog, in bijna de helft van de testgevallen die ze uitvoerden, maakte het toestaan van een kleine fout van $\epsilon = 10^{-2}$ (0,01) het mogelijk om de volledige controller terug te brengen tot een enkele knoop. Dit betekent dat de robot gewoon één hoofdbeweging kan kiezen, en als die actie niet mogelijk is, elke andere beschikbare beweging willekeurig kan kiezen, en nog steeds bijna net zo goed zal presteren als de complexe, perfecte strategie. Dit is een feit dat eerdere hulpmiddelen volledig over het hoofd zagen.

De onderzoekers zijn voorzichtig om te vermelden dat ze niet gewoon gokten; ze gebruikten een krachtige model checker (een hulpmiddel dat wiskundig verifieert of een systeem werkt) om elke vereenvoudigde boom dubbel te controleren. Ze bewezen dat, zelfs met deze agressieve vereenvoudigingen, de prestaties van de robot nooit onder de toegestane veiligheidsgrens zakken. Ze lieten ook zien dat hun hulpmiddel werkt voor diverse soorten doelen, niet alleen het bereiken van een bestemming, maar ook het vermijden van gevaar of het verzamelen van beloningen.

Kortom, deze paper presenteert een manier om een kleine, controleerbare hoeveelheid wiskundige perfectie in te ruilen voor een enorme winst in menselijk begrip. Door de computer toe te staan toe te geven dat hij niet elk klein detail hoeft uit te leggen, hebben de onderzoekers controllers gecreëerd die niet alleen veilig en effectief zijn, maar ook klein genoeg om op een ansichtkaart te passen en simpel genoeg om een mens aan een vriend uit te leggen. Het verandert een verwarrende, miljoen pagina's tellende instructiehandleiding in een heldere handleiding van drie stappen.

Technische Samenvatting: dtControl2+ε: Handelingsoptimaliteit voor verklaarbaarheid in MDP's via Beslissingsbomen

Probleemstelling

Controller-synthese voor Markov Decision Processes (MDP's) levert vaak optimale controllers op die worden gerepresenteerd als grote, ongestructureerde staat-actie-tabellen. Hoewel deze tabellen wiskundig precies zijn, zijn ze onpraktisch voor implementatie op apparaten met beperkte middelen en missen ze verklaarbaarheid, wat validatie en certificering belemmert. Bestaande tools, zoals dtControl2, proberen deze controllers te representeren als Beslissingsbomen (Decision Trees, DT's) om de interpreteerbaarheid te verbeteren. Echter, zelfs deze DT's kunnen voor grote systemen of systemen met veel randgevallen te complex worden voor menselijk begrip.

Een kritieke uitdaging is dat het verkleinen van de DT-omvang niet triviaal is; het verwijderen van één cruciale beslissing kan de controller incorrect maken. Bov Furthermore, bieden veel schaalbare synthesemethoden alleen $\epsilon$ -optimale controllers (prestaties binnen $\epsilon$ van de optimale waarde), terwijl bestaande DT-constructietools doorgaans streven naar een exacte ( $\epsilon=0$ ) representatie, waardoor ze het niet benutten dat de toegestane onnauwkeurigheid de vereenvoudiging van de uitleg kan vergemakkelijken.

Methodologie

Het artikel presenteert dtControl2+ε, een tool die de state-of-the-art dtControl2 uitbreidt door een " $\epsilon$ "-functionaliteit te introduceren. De kernworkflow integreert nauw met de probabilistische modelchecker Storm om kleinere, verklaarbare DT's te construeren, terwijl wordt gegarandeerd dat de resulterende controller $\epsilon$ -optimaal blijft.

De methodologie verloopt in drie hoofdfasen:

1. Modeloplossing en Datasetconstructie

In plaats van te beginnen met een deterministische optimale controller, genereert de tool een initiële dataset die permissief is (het mappen van staten naar verzamelingen toegestane acties) of gecombineerd (het beperken van permissieve acties tot bereikbare staten).

Permissieve Strategieën: De tool identificeert acties die optimaal zijn of dezelfde waarde opleveren, waardoor de DT staten kan "verenigen".
Reductieheuristieken: Voordat de DT wordt geleerd, identificeert en verwijdert de tool staten waar de specifieke keuze van een actie de uitkomst niet beïnvloedt of waar de geïntroduceerde fout begrensd is door $\epsilon$ $ϵ$ . Belangrijke reductietechnieken zijn onder meer:
- AllOpt: Het verwijderen van staten waar alle beschikbare acties optimaal zijn.
- Agency: Het verwijderen van staten waar het verschil tussen de beste en slechtst mogelijke uitkomsten kleiner is dan $\epsilon$ .
- Dominance: Het verwijderen van staten die bijna zeker worden bereikt vanuit andere staten, ongeacht de gemaakte keuze.
- Unreach: Het verwijderen van staten die onbereikbaar zijn vanuit de initiële staat onder elke consistente controller.

2. Beslissingsboomleren

De tool maakt gebruik van een aangepaste versie van het standaard heuristiek-gebaseerde DT-constructiealgoritme (Algoritme 1) met diverse verbeteringen:

Predicaatextractie: Extraheert automatisch relevante predikaten uit de hoogwaardige modelbeschrijving (bijv. PRISM-taal transitie-guards), wat een verbetering is ten opzichte van de semi-automatische template-aanpak van eerdere tools.
Onzuiverheidsmaten (Impurity Measures): Introduceert modelspecifieke weging voor onzuurheidsberekeningen. In plaats van uniforme weging, gebruikt het:
- Imp_Simulation: Weegt staten op basis van bezoekfrequentie (met een veiligheidsvloer om $\epsilon$ -optimaliteit te waarborgen).
- Imp_Agency: Weegt staten op basis van hun agency (potentiële fout).
- Imp_CoE (Cost of Error): Weegt staten op basis van de impact van het kiezen van de slechtste actie in die specifieke staat.
Agressieve Heuristieken met Verificatie: De tool past Early-Stopping toe (het stoppen van splitsingen wanneer de onzuurheid onder een drempelwaarde ligt) en Greedy Pruning (het inklappen van subbomen). In tegenstelling tot eerdere "agressieve" benaderingen die de betrouwbaarheid in gevaar brachten, gebruikt dtControl2+ε Storm om de $\epsilon$ -optimaliteit van de resulterende boom na deze stappen te verifiëren. Als de precisie-eis wordt geschonden, versoepelt de tool de heuristieken en probeert deze opnieuw.

3. Verificatielus

Een uniek kenmerk is de nauwe koppeling met Storm voor verificatie na constructie. De tool controleert de precisie van de gegenereerde DT. Als de afwijking van de optimale waarde groter is dan $\epsilon$ , gaat de tool terug (backtrack) en vermindert de agressiviteit van de heuristieken (bijv. het verhogen van de stop-drempel of het uitschakelen van pruning), waardoor wordt gegarandeerd dat de uiteindelijke output gegarandeerd $\epsilon$ -optimaal is.

Belangrijkste Bijdragen

De dtControl2+ε Tool: Een zelfstandige tool die dtControl2 uitbreidt om kleinere DT's te construeren door gebruik te maken van de toegestane onnauwkeurigheid $\epsilon$ .
Veilige vs. Agressieve Heuristieken: Een framework dat "veilige" reducties (die $\epsilon$ -optimaliteit per definitie behouden) duidelijk scheidt van "agressieve" heuristieken (die gevalideerd worden via model checking).
Automatische Predicaatextractie: Een methode om beslissingspredikaten direct af te leiden uit de transitie-guards van het model, wat de noodzaak voor handmatige domeinkennis bij predicaatselectie wegneemt.
Ondersteuning voor Diverse Doelstellingen: De aanpak dekt standaarddoelstellingen (bereikbaarheid, veiligheid, reach-avoid, beloningsgebaseerd) en ondersteunt uniek genoeg ook Linear Temporal Logic (LTL) eigenschappen door het afhandelen van geheugen-gebaseerde controllers.

Resultaten

De auteurs hebben dtControl2+ε geëvalueerd tegenover dtControl2, dtPaynt, dtNESt en een reimplementatie van de CAV15-aanpak op 38 benchmarks (inclusief PRISM-modellen met tot 500.000 staten).

Groottevermindering: Zelfs voor exacte representatie ( $\epsilon=0$ ) produceert dtControl2+ε DT's die orders van grootte kleiner zijn dan die van dtControl2, dankzij verbeterde initiële datasets en veilige heuristieken.
Impact van $\epsilon$ : Wanneer een $\epsilon = 10^{-2}$ wordt toegestaan, produceerde de tool voor bijna de helft van de benchmarks een enkele-node DT, wat aantoont dat een enkele actie (met een uniforme willekeurige fallback) vaak voldoende is voor $\epsilon$ -optimaliteit.
Vergelijking:
- vs. dtControl2: dtControl2+ε produceert consequent kleinere bomen.
- vs. dtPaynt: dtPaynt liep bij de meeste benchmarks vast en produceerde grotere bomen waar het slaagde.
- vs. dtNESt: dtNESt is een sterke concurrent voor $\epsilon=0$ , maar dtControl2+ε produceert bomen die maximaal de helft zo groot zijn in 23 van de 38 benchmarks, en een orde van grootte kleiner in 10 gevallen. Opvallend genoeg faalt dtNESt vaak of produceert grotere bomen wanneer $\epsilon > 0$ , terwijl dtControl2+ε uitblinkt in het exploiteren van onnauwkeurigheid.
Schaalbaarheid: De tool loste alle benchmarks op, behalve één, binnen een tijdslimiet van 20 minuten, wat de haalbaarheid op grote, complexe modellen aantoont.

Betekenis

Het artikel stelt dat dtControl2+ε een significante vooruitgang vormt in de huidige stand van de techniek voor verklaarbare controller-synthese. Door een controleerbare hoeveelheid optimaliteit in te ruilen voor compactheid, stelt de tool in staat om menselijk begrijpelijke controllers te genereren die voorheen te complex waren om te interpreteren. Het vermogen om automatisch structurele inzichten af te leiden (bijv. identificeren dat een enkele regel volstaat voor $\epsilon$ -optimaliteit) en om LTL-eigenschappen te ondersteunen, onderscheidt het van bestaande tools. De auteurs benadrukken dat hun aanpak garanties biedt voor $\epsilon$ -optimaliteit, in tegenstelling tot eerdere heuristiek-gebaseerde pruning-methoden die de correctheid in gevaar konden brengen.