# Polynomial Regret Concentration of UCB for Non-Deterministic State Transitions

arXiv: https://arxiv.org/abs/2502.06900 · HTML: https://mlsanity.com/paper/2502.06900/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Solving General-Utility Markov Decision Processes in the Single-Trial Regime with Online Planning](https://mlsanity.com/paper/2505.15782/) (2025)

## Abstract (arXiv)

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.