Symbiotic Local Search for Small Decision Tree Policies in MDPs

D 2025

Symbiotic Local Search for Small Decision Tree Policies in MDPs

ANDRIUSHCHENKO, Roman; Milan ČEŠKA; Debraj CHAKRABORTY; Sebastian JUNGES; Jan KŘETÍNSKÝ et al.

Základní údaje

Originální název

Symbiotic Local Search for Small Decision Tree Policies in MDPs

Autoři

ANDRIUSHCHENKO, Roman; Milan ČEŠKA; Debraj CHAKRABORTY; Sebastian JUNGES; Jan KŘETÍNSKÝ a Filip MACÁK

Vydání

Rio de Janeiro, Brazil, Proceedings of Machine Learning Research, Volume 286: Conference on Uncertainty in Artificial Intelligence (UAI 2025), od s. 132-148, 17 s. 2025

Nakladatel

ML Research Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00143671

Organizační jednotka

Fakulta informatiky

ISSN

UT WoS

001592914500007

Klíčová slova anglicky

Computer Science; Artificial Intelligence; Theory& Methods

Štítky

core_A, firank_A

Změněno: 12. 2. 2026 17:02, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We study decision making policies in Markov decision processes (MDPs). Two key performance indicators of such policies are their value and their interpretability. On the one hand, policies that optimize value can be efficiently computed via a plethora of standard methods. However, the representation of these policies may prevent their interpretability. On the other hand, policies with good interpretability, such as policies represented by a small decision tree, are computationally hard to obtain. This paper contributes a local search approach to find policies with good value, represented by small decision trees. Our local search symbiotically combines learning decision trees from valueoptimal policies with symbolic approaches that optimize the size of the decision tree within a constrained neighborhood. Our empirical evaluation shows that this combination provides drastically smaller decision trees for MDPs that are significantly larger than what can be handled by optimal decision tree learners.

Návaznosti

MUNI/I/1757/2021, interní kód MU

Název: MUNI Award in Science and Humanities (Akronym: Křetínský)

Investor: Masarykova univerzita, MUNI Award in Science and Humanities, MASH - MUNI Award in Science and Humanities

101171844, interní kód MU

Název: Intelligence-Oriented Verification&Controller Synthesis

Investor: Evropská unie, Intelligence-Oriented Verification&Controller Synthesis, ERC CoG - Evropská rada pro výzkum (ERC)

Citovat

ANDRIUSHCHENKO, Roman; Milan ČEŠKA; Debraj CHAKRABORTY; Sebastian JUNGES; Jan KŘETÍNSKÝ a Filip MACÁK. Symbiotic Local Search for Small Decision Tree Policies in MDPs. In Proceedings of Machine Learning Research, Volume 286: Conference on Uncertainty in Artificial Intelligence (UAI 2025). Rio de Janeiro, Brazil: ML Research Press, 2025, s. 132-148. ISSN 2640-3498.

@inproceedings{2553777,
   author = {Andriushchenko, Roman and Češka, Milan and Chakraborty, Debraj and Junges, Sebastian and Křetínský, Jan and Macák, Filip},
   address = {Rio de Janeiro, Brazil},
   booktitle = {Proceedings of Machine Learning Research, Volume 286: Conference on Uncertainty in Artificial Intelligence (UAI 2025)},
   keywords = {Computer Science; Artificial Intelligence; Theory& Methods},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Rio de Janeiro, Brazil},
   pages = {132-148},
   publisher = {ML Research Press},
   title = {Symbiotic Local Search for Small Decision Tree Policies in MDPs},
   url = {https://proceedings.mlr.press/v286/andriushchenko25a.html},
   year = {2025}
}

TY  - CONF
ID  - 2553777
AU  - Andriushchenko, Roman - Češka, Milan - Chakraborty, Debraj - Junges, Sebastian - Křetínský, Jan - Macák, Filip
PY  - 2025
TI  - Symbiotic Local Search for Small Decision Tree Policies in MDPs
PB  - ML Research Press
CY  - Rio de Janeiro, Brazil
KW  - Computer Science
KW  - Artificial Intelligence
KW  - Theory&
KW  - Methods
UR  - https://proceedings.mlr.press/v286/andriushchenko25a.html
N2  - We study decision making policies in Markov decision processes (MDPs). Two key performance indicators of such policies are their value and their interpretability. On the one hand, policies that optimize value can be efficiently computed via a plethora of standard methods. However, the representation of these policies may prevent their interpretability. On the other hand, policies with good interpretability, such as policies represented by a small decision tree, are computationally hard to obtain. This paper contributes a local search approach to find policies with good value, represented by small decision trees. Our local search symbiotically combines learning decision trees from valueoptimal policies with symbolic approaches that optimize the size of the decision tree within a constrained neighborhood. Our empirical evaluation shows that this combination provides drastically smaller decision trees for MDPs that are significantly larger than what can be handled by optimal decision tree learners.
ER  -

ANDRIUSHCHENKO, Roman; Milan ČEŠKA; Debraj CHAKRABORTY; Sebastian JUNGES; Jan KŘETÍNSKÝ a Filip MACÁK. Symbiotic Local Search for Small Decision Tree Policies in MDPs. In \textit{Proceedings of Machine Learning Research, Volume 286: Conference on Uncertainty in Artificial Intelligence (UAI 2025)}. Rio de Janeiro, Brazil: ML Research Press, 2025, s.~132-148. ISSN~2640-3498.

Přehled o publikaci