Symbiotic Local Search for Small Decision Tree Policies in MDPs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00143671" target="_blank" >RIV/00216224:14330/25:00143671 - isvavai.cz</a>
Result on the web
<a href="https://proceedings.mlr.press/v286/andriushchenko25a.html" target="_blank" >https://proceedings.mlr.press/v286/andriushchenko25a.html</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Symbiotic Local Search for Small Decision Tree Policies in MDPs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10200 - Computer and information sciences
Result continuities
Project
—
Continuities
V - Vyzkumna aktivita podporovana z jinych verejnych zdroju
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of Machine Learning Research, Volume 286: Conference on Uncertainty in Artificial Intelligence (UAI 2025)
ISBN
—
ISSN
2640-3498
e-ISSN
—
Number of pages
17
Pages from-to
132-148
Publisher name
ML Research Press
Place of publication
Rio de Janeiro, Brazil
Event location
Rio de Janeiro, Brazil
Event date
Jan 1, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001592914500007