Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.00228 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912214712057856 |
|---|---|
| author | Yang, Yuanyuan Zhang, Ruimin Morgenstern, Jamie Xu, Haifeng |
| author_facet | Yang, Yuanyuan Zhang, Ruimin Morgenstern, Jamie Xu, Haifeng |
| contents | In this paper, we study the Markovian Pandora's Box Problem, where decisions are governed by both order constraints and Markovianly correlated rewards, structured within a shared directed acyclic graph. To the best of our knowledge, previous work has not incorporated Markovian dependencies in this setting. This framework is particularly relevant to applications such as data or computation driven algorithm design, where exploration of future models incurs cost.
We present optimal fully adaptive strategies where the associated graph forms a forest. Under static transition, we introduce a strategy that achieves a near optimal expected payoff in multi line graphs and a 1/2 approximation in forest-structured graphs. Notably, this algorithm provides a significant speedup over the exact solution, with the improvement becoming more pronounced as the graph size increases. Our findings deepen the understanding of sequential exploration under Markovian correlations in graph-based decision-making. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00228 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Markovian Pandora's box Yang, Yuanyuan Zhang, Ruimin Morgenstern, Jamie Xu, Haifeng Computer Science and Game Theory In this paper, we study the Markovian Pandora's Box Problem, where decisions are governed by both order constraints and Markovianly correlated rewards, structured within a shared directed acyclic graph. To the best of our knowledge, previous work has not incorporated Markovian dependencies in this setting. This framework is particularly relevant to applications such as data or computation driven algorithm design, where exploration of future models incurs cost. We present optimal fully adaptive strategies where the associated graph forms a forest. Under static transition, we introduce a strategy that achieves a near optimal expected payoff in multi line graphs and a 1/2 approximation in forest-structured graphs. Notably, this algorithm provides a significant speedup over the exact solution, with the improvement becoming more pronounced as the graph size increases. Our findings deepen the understanding of sequential exploration under Markovian correlations in graph-based decision-making. |
| title | Markovian Pandora's box |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.00228 |