为随机状态转移的强化学习提供了更优的理论保障。
Polynomial Regret Concentration of UCB for Non-Deterministic State Transitions
- 基于UCB算法，推导出多项式后悔率集中边界。
- 证明该边界在非确定性环境下依然成立，性能稳定。
- 适合研究决策算法理论保证的研究者和应用开发者。
蒙特卡洛树搜索（MCTS）在完全信息场景中表现出色，但在随机和不完全信息领域应用受限。本文将MCTS的理论框架扩展至随机环境，针对动作导致概率性状态转移的问题，基于Shah等（2020）的工作，推导了具有随机转移的多臂赌博机问题中上置信界（UCB）算法的多项式后悔率集中边界，提供了更优的理论保障。主要贡献在于证明这些边界同样适用于非确定性环境，确保了在随机设定下的鲁棒性能。这一结果拓宽了MCTS在具有概率性结果的实际决策问题中的适用范围，如自主系统和金融决策。
原文摘要 · Abstract (English)
Monte Carlo Tree Search (MCTS) has proven effective in solving decision-making problems in perfect information settings. However, its application to stochastic and imperfect information domains remains limited. This paper extends the theoretical framework of MCTS to stochastic domains by addressing non-deterministic state transitions, where actions lead to probabilistic outcomes. Specifically, building on the work of Shah et al. (2020), we derive polynomial regret concentration bounds for the Upper Confidence Bound algorithm in multi-armed bandit problems with stochastic transitions, offering improved theoretical guarantees. Our primary contribution is proving that these bounds also apply to non-deterministic environments, ensuring robust performance in stochastic settings. This broadens the applicability of MCTS to real-world decision-making problems with probabilistic outcomes, such as in autonomous systems and financial decision-making.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。