通过少量询问，快速找到不确定马尔可夫优化中的最优解。
Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids
- 逐对询问用户偏好，动态缩小权重不确定范围。
- 在4个标准马尔可夫上，用更少轮次达到最优。
- 无需每轮计算最小最大后悔值，效率更高。
本文提出一种高效偏好获取框架，用于解决权重信息不确定的马尔可夫优化问题。当精确权重未知但存在可能取值范围时，该方法通过逐步询问元素间偏好，利用马尔可夫结构特性迭代收缩参数不确定性区域。目标是通过少量查询实现精确最优解，避免传统方法在每轮迭代中计算最小最大后悔值或调用线性规划求解器。在四个标准马尔可夫实例上的实验表明，该方法比现有技术更快收敛至最优，并显著减少偏好询问次数。
原文摘要 · Abstract (English)
This paper presents an efficient preference elicitation framework for uncertain matroid optimization, where precise weight information is unavailable, but insights into possible weight values are accessible. The core innovation of our approach lies in its ability to systematically elicit user preferences, aligning the optimization process more closely with decision-makers' objectives. By incrementally querying preferences between pairs of elements, we iteratively refine the parametric uncertainty regions, leveraging the structural properties of matroids. Our method aims to achieve the exact optimum by reducing regret with a few elicitation rounds. Additionally, our approach avoids the computation of Minimax Regret and the use of Linear programming solvers at every iteration, unlike previous methods. Experimental results on four standard matroids demonstrate that our method reaches optimality more quickly and with fewer preference queries than existing techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。