提出一种可证明正确的风险感知蒙特卡洛树搜索算法
Entropic Risk-Aware Monte Carlo Tree Search
- 基于上置信界树搜索框架，结合熵风险度量的动态规划结构
- 根节点经验熵风险值收敛至最优，且后悔率呈多项式集中
- 适合需权衡风险与收益的决策场景，如金融或自动驾驶
我们提出一种可证明正确的蒙特卡洛树搜索（MCTS）算法，用于求解具有熵风险度量（ERM）目标的风险感知马尔可夫决策过程（MDP）。我们提供了非渐近分析，证明该算法：(i) 正确性——根节点处获得的经验ERM收敛至最优ERM；(ii) 拥有多项式后悔率集中性。该算法成功利用了先前工作在风险感知MDP中提出的、针对ERM目标的动态规划形式，将其融入基于上置信界的树搜索框架。最后，我们通过一系列实验，将所提出的风险感知MCTS方法与相关基线进行对比。
原文摘要 · Abstract (English)
We propose a provably correct Monte Carlo tree search (MCTS) algorithm for solving risk-aware Markov decision processes (MDPs) with entropic risk measure (ERM) objectives. We provide a non-asymptotic analysis of our proposed algorithm, showing that the algorithm: (i) is correct in the sense that the empirical ERM obtained at the root node converges to the optimal ERM; and (ii) enjoys polynomial regret concentration. Our algorithm successfully exploits the dynamic programming formulations for solving risk-aware MDPs with ERM objectives introduced by previous works in the context of an upper confidence bound-based tree search algorithm. Finally, we provide a set of illustrative experiments comparing our risk-aware MCTS method against relevant baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。