Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Categorical Thompson Sampling with Optimism (CATSO) and Particle Thompson Sampling with Optimism (PATSO), novel distributional Monte-Carlo Tree Search (MCTS) algorithms designed to optimize for tail-risk objectives like CVaR, unlike traditional scalar-valued MCTS. By maintaining finite-support empirical backup laws at Q-edges using categorical atoms or adaptive particles, these methods enable risk-sensitive action selection and propagate risk-aware continuation values. The algorithms achieve an $O(n^{-1/2})$ bound on root value error and demonstrate improved lower-tail returns and reduced catastrophic outcomes in stochastic planning benchmarks where mean-optimal and risk-sensitive policies diverge.
Risk-sensitive planning with MCTS is now possible, with new algorithms achieving provable regret bounds and outperforming mean-optimal policies in avoiding catastrophic outcomes.
Monte-Carlo Tree Search (MCTS) typically stores only scalar mean estimates, which makes it poorly suited for tail-risk objectives such as conditional value-at-risk (CVaR). We introduce Categorical Thompson Sampling with Optimism (CATSO) and Particle Thompson Sampling with Optimism (PATSO), two distributional MCTS algorithms that maintain finite-support empirical backup laws at Q-edges. CATSO represents Q-edge laws with categorical atoms and Dirichlet Thompson sampling, while PATSO represents them with adaptive particles. Both algorithms select actions using the CVaR of a Thompson-sampled Q-edge law plus a polynomial optimism bonus, and propagate scalar continuation values through visit-weighted averages of child Q-edge CVaR scores. For the finite-depth nested CVaR planning target, we prove an $O(n^{-1/2})$ bound on the root value error after $n$ rollouts, which upper-bounds the risk-sensitive simple regret. CATSO adds a fixed-grid discretization bias, while capped PATSO adds a tunable Wasserstein compression bias. Experiments on stochastic planning benchmarks show that distributional Q-edges improve lower-tail return and reduce catastrophic outcomes when mean-optimal and risk-sensitive behavior differ.