Decision-Making Under Complete Uncertainty: You Will Regret Not Being Greedy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909488138682368 |
|---|---|
| author | Atanasov, Kristijan Ismail, Mehmet Mallmann-Trenn, Frederik |
| author_facet | Atanasov, Kristijan Ismail, Mehmet Mallmann-Trenn, Frederik |
| contents | In this paper, we propose a probabilistic game-theoretic model to study the properties of the worst-case regret of the greedy strategy under complete (Knightian) uncertainty. In a game between a decision-maker (DM) and an adversarial agent (Nature), the DM observes a realization of product ratings for each product. Upon observation, the DM chooses a strategy, which is a function from the set of observations to the set of products. We study the theoretical properties, including the worst-case regret of the greedy strategy that chooses the product with the highest observed average rating. We prove that, with respect to the worst-case regret, the greedy strategy is optimal and that, in the limit, the regret of the greedy strategy converges to zero. We validate the model on data collected from Google reviews for restaurants, showing that the greedy strategy not only performs according to the theoretical findings but also outperforms the uniform strategy and the Thompson Sampling algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07593 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decision-Making Under Complete Uncertainty: You Will Regret Not Being Greedy Atanasov, Kristijan Ismail, Mehmet Mallmann-Trenn, Frederik Computer Science and Game Theory In this paper, we propose a probabilistic game-theoretic model to study the properties of the worst-case regret of the greedy strategy under complete (Knightian) uncertainty. In a game between a decision-maker (DM) and an adversarial agent (Nature), the DM observes a realization of product ratings for each product. Upon observation, the DM chooses a strategy, which is a function from the set of observations to the set of products. We study the theoretical properties, including the worst-case regret of the greedy strategy that chooses the product with the highest observed average rating. We prove that, with respect to the worst-case regret, the greedy strategy is optimal and that, in the limit, the regret of the greedy strategy converges to zero. We validate the model on data collected from Google reviews for restaurants, showing that the greedy strategy not only performs according to the theoretical findings but also outperforms the uniform strategy and the Thompson Sampling algorithm. |
| title | Decision-Making Under Complete Uncertainty: You Will Regret Not Being Greedy |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.07593 |