Efficient Tree Generation for Globally Optimal Decisions under Probabilistic Outcomes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908337270947840 |
|---|---|
| author | Ozturk, Berk Punla-Green, She'ifa Servi, Les |
| author_facet | Ozturk, Berk Punla-Green, She'ifa Servi, Les |
| contents | Many real-world problems require making sequences of decisions where the outcomes of each decision are probabilistic and uncertain, and the availability of different actions is constrained by the outcomes of previous actions. There is a need to generate policies that are adaptive to uncertainty, globally optimal, and yet scalable as the state space grows. In this paper, we propose the generation of optimal decision trees, which dictate which actions should be implemented in different outcome scenarios, while maximizing the expected reward of the strategy. Using a combination of dynamic programming and mixed-integer linear optimization, the proposed methods scale to problems with large but finite state spaces, using problem-specific information to prune away large subsets of the state space that do not yield progress towards rewards. We demonstrate that the presented approach is able to find the globally optimal decision tree in linear time with respect to the number states explored. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17983 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Tree Generation for Globally Optimal Decisions under Probabilistic Outcomes Ozturk, Berk Punla-Green, She'ifa Servi, Les Optimization and Control Data Structures and Algorithms 90C39 Many real-world problems require making sequences of decisions where the outcomes of each decision are probabilistic and uncertain, and the availability of different actions is constrained by the outcomes of previous actions. There is a need to generate policies that are adaptive to uncertainty, globally optimal, and yet scalable as the state space grows. In this paper, we propose the generation of optimal decision trees, which dictate which actions should be implemented in different outcome scenarios, while maximizing the expected reward of the strategy. Using a combination of dynamic programming and mixed-integer linear optimization, the proposed methods scale to problems with large but finite state spaces, using problem-specific information to prune away large subsets of the state space that do not yield progress towards rewards. We demonstrate that the presented approach is able to find the globally optimal decision tree in linear time with respect to the number states explored. |
| title | Efficient Tree Generation for Globally Optimal Decisions under Probabilistic Outcomes |
| topic | Optimization and Control Data Structures and Algorithms 90C39 |
| url | https://arxiv.org/abs/2504.17983 |