Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search

arXiv:2610.23565v1 [cs.LG] 16 Oct 2026

Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search Quynh Trinh∗,1 Trung Nguyen∗,1 Nam Nguyen1,2 Tuan Dam1,† 1 Hanoi University of Science and Technology, Hanoi, Vietnam 2 Center for AI Research, VinUniversity, Hanoi, Vietnam ∗ Equal contribution † Correspondence to: Tuan Dam <tuandq@soict.hust.edu.vn>

Abstract Monte-Carlo Tree Search (MCTS) typically stores only scalar mean estimates, which makes it poorly suited for tail-risk objectives such as conditional value-atrisk (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.

1

Introduction

Monte-Carlo Tree Search (MCTS) drives some of the most capable planning systems ever built, from AlphaGo [28] and AlphaZero [29] to MuZero [26]. Classical variants such as UCT [19], Fixed-DepthMCTS [27], and Power-UCT [8] store a scalar value estimate at each edge, usually an empirical mean. This is sufficient when the objective is expected return, but it is inadequate for risk-sensitive planning. In safety-critical domains such as autonomous driving, medical treatment planning, and financial decision making, two actions can have similar means but very different lower-tail behavior. A simple example illustrates the problem. Suppose a root action a1 returns 5 deterministically, while another action a2 returns 10 with probability 1/2 and 0 with probability 1/2. Both actions have the same expected value, but their lower-tail conditional value-at-risk (CVaR) is different: for small τ , a1 has CVaR equal to 5, whereas a2 has CVaR equal to 0. A scalar mean estimate cannot distinguish these two return laws once their means are known. A risk-sensitive planner, however, should prefer a1 when the objective is to protect against poor outcomes. This requires preserving distributional information at the Q-edges of the search tree. This paper develops distributional MCTS algorithms for finite-depth risk-sensitive planning. We introduce Categorical Thompson Sampling with Optimism (CATSO) and Particle Thompson Sampling with Optimism (PATSO). Both algorithms maintain finite-support empirical backup laws at Q-edges. CATSO represents each Q-edge law using categorical atoms with Dirichlet Thompson sampling, while PATSO represents it using adaptive weighted particles. At action selection time, both algorithms draw a Thompson-sampled Q-edge law, compute its lower-tail CVaR, and add the polynomial optimism bonus of Shah et al. [27] to ensure sufficient exploration.

The algorithms keep V-nodes scalar by backing up a visit-weighted average of child Q-edge CVaR scores, so Q-edges store distributions while V-nodes propagate scalar risk-sensitive summaries. This avoids distributional V-node convolutions while still letting lower-tail information drive the search. Our main result proves an O(n−1/2 ) root value-error bound against the finite-depth nested CVaR target (Section 5), which yields an O(n−1/2 ) risk-sensitive simple regret. CATSO incurs an additional finite-grid discretization bias, and capped PATSO adds a tunable Wasserstein compression bias. Our contributions are: • We introduce CATSO and PATSO, two non-parametric distributional MCTS algorithms that maintain empirical backup laws at Q-edges. • We propose a CVaR-sensitive scalar V-backup that aggregates visit-weighted child Q-edge CVaR scores rather than child Q-edge means. • We prove an O(n−1/2 ) root value-error bound for the finite-depth nested CVaR target after n rollouts, which directly upper-bounds the risk-sensitive simple regret. • We characterize the additional approximation terms introduced by finite CATSO grids and capped PATSO particle compression. • We evaluate the algorithms on stochastic planning benchmarks where mean-optimal and CVaRoptimal behavior differ. Existing distributional MCTS methods such as DNG-MCTS [1] and D2NG-POMCP [2] rely on parametric return models, such as Gaussian or mixture distributions. In contrast, CATSO and PATSO are non-parametric: we estimate Q-edge backup laws directly from backed-up samples. This makes our methods suitable for planning problems with multimodal, skewed, or heavy-tailed return distributions, where parametric approximations can obscure the lower-tail behavior that CVaR is designed to measure.

2

Related Work

MCTS with non-asymptotic guarantees and distributional backups. While UCT [19] established asymptotic convergence for MCTS, the breakthrough finite-sample analysis is due to Shah et al. [27], who modeled each tree node as a non-stationary bandit and proved O(n−1/2 ) root value convergence using a polynomial exploration bonus; Dam et al. [8] extended this framework to power-mean backups. However, these analyses rely on scalar point estimates and do not capture tail risk. Existing distributional MCTS methods place parametric posteriors over returns—such as Normal-Gamma models in DNG-MCTS [1, 2] or Gaussian Wasserstein barycenters in W-MCTS [9]—or address heuristic multi-objective search [16]. Parametric assumptions can obscure lower-tail behavior in multimodal or heavy-tailed domains. Most recently, Zhang et al. [32] proposed CVaR-MCTS and a distributionally robust variant (also termed Wasserstein-MCTS, distinct from the Gaussian barycenter method of Dam et al. [9]) that optimize expected reward subject to a static cumulative-cost CVaR constraint with PAC tail-safety and regret guarantees. In contrast, CATSO and PATSO maintain non-parametric empirical backup laws at Q-edges while keeping V-nodes scalar, directly optimizing the unconstrained nested finite-depth CVaR of reward with an O(n−1/2 ) finite-budget root value-error guarantee. Thompson sampling in stationary vs. non-stationary CVaR bandits. Thompson sampling has been combined with MCTS over scalar or Gaussian posteriors [1, 15]. In the stationary multi-armed bandit literature, Riou and Honda [25] established logarithmic regret for Dirichlet Thompson sampling on bounded-support rewards, which Baudry et al. [3] extended to support-aware stationary CVaR bandits via multinomial grids (M-CVTS) and adaptive particles (B-CVTS). Our local bandit analysis builds on this Dirichlet convex-polytope machinery, but stationary CVaR bandit guarantees do not transfer directly to MCTS: the backed-up samples Qt (sh , a) = rt (sh , a) + γ V̂ τ (sh+1 ) have a non-stationary law that drifts as the searched subtree evolves. Controlling this coupled evolution requires pairing Dirichlet CVaR Thompson sampling with a polynomial optimism bonus and establishing our threestage proof roadmap (local non-stationary CVaR bandit concentration, one-step W1 -Lipschitz CVaR lifting across Q-edges, and backward induction). Risk-sensitive RL Beyond tree search, risk-sensitive RL has been studied through policy gradients [30, 6], distributional RL [7, 18], robust MDPs [17, 23], and Wasserstein DRO [12]. Recent theoretical work has established provably efficient episodic regret and PAC sample-complexity bounds 2

across two primary objectives: static trajectory CVaR, including near-minimax-optimal learning [31] and reward-free CVaR exploration [22], and nested (iterated) CVaR, including tabular episodic learning [11], function approximation with human feedback [5], and generative-model sample complexity [10]. Whereas these works bound global episodic regret or offline sample complexity across full MDP state spaces, our work addresses online finite-budget Monte-Carlo tree search from a given root state s0 , proving non-asymptotic O(n−1/2 ) root value-error and simple-regret guarantees for nested CVaR planning.

3

Setting

MDP and finite-depth planning. We consider a discounted MDP M = ⟨S, A, R, P, γ⟩, where S is the state space, A is a finite action set, R(· | s, a) is a stochastic reward kernel with support in [0, Rmax ] 1 , P(· | s, a) is a stochastic transition kernel over S, and γ ∈ [0, 1) is the discount factor. MCTS plans from a root state s0 by Psimulating depth-H trajectories, using a fixed rollout policy πro at depth H; we write GπHro (s) = k≥0 γ k rk for the resulting discounted return. For the analysis, every internal node has finitely many legal actions and every encountered transition kernel has finite support. For a real-valued X and τ ∈ (0, 1], the lower-tail conditional value-at-risk is Z 1 τ −1 CVaRτ (X) := F (u) du, (1) τ 0 X the average of the worst τ -fraction of outcomes, with CVaR1 (X) = E[X]. We also write CVaRτ (P ) for laws P ; for finitely supported P , this is the discrete formula (10). The same τ is used for selection, backup, and evaluation throughout. Although we state the theory for lower-tail CVaR, this is without loss of generality: upper-tail risk can be handled by applying the same framework to −X, equivalently using CVaRτ (X) := − CVaRτ (−X). Lower-tail CVaR.

Finite-depth nested CVaR target. Set Ve τ (sH ) := CVaRτ (GπHro (sH )) and, for h = H − 1, . . . , 0, define the Bellman-backup law   Dτ (sh , a) := L R(sh , a, S ′ ) + γ Ve τ (S ′ ) , S ′ ∼ P(· | sh , a), (2) with reward sampled from R(sh , a, S ′ ), and e τ (sh , a) := CVaRτ (Dτ (sh , a)) , Q

e τ (sh , a). Ve τ (sh ) := max Q a∈A(sh )

(3)

Write Ve τ (s0 ) := Ve0τ (s0 ). At τ = 1, (3) reduces to the standard finite-depth risk-neutral Bellman recursion; for τ < 1, it is a nested time-consistent CVaR target, distinct from the static P CVaRτ ( t≥0 γ t rt ). All guarantees are stated relative to (3). Algorithmic root value estimate. After n rollouts, each visited Q-edge (s, a) maintains an embT (n) (s, a), where Ts,a (n) is its visit count, with empirical CVaR score pirical backup law D s,a bT (n) (s, a)). The scalar V-node estimate is the visit-weighted average b cτ,n (s, a) := CVaRτ (D s,a X Ts,a (n) VbTτs (n) (s) := b cτ,n (s, a), (4) Ts (n) a∈A(s)

with each action initialized before backup; Vbnτ (s0 ) is the root estimate returned after n rollouts. Risk-sensitive simple regret.

The risk-sensitive simple regret relative to (3) is h i SRτ (n) := E Ve τ (s0 ) − Vbnτ (s0 ) ,

and our main theorem controls the stronger absolute error h i Eτ (n) := E Vbnτ (s0 ) − Ve τ (s0 ) ≥ SRτ (n),

(5)

(6)

so any O(n−1/2 ) bound on Eτ (n) transfers to SRτ (n). 1 Note that this assumption is for the sake of simplicity, the analysis remains valid if one assumes any closed bounded reward interval [Rmin , Rmax ] by shifting the interval up by Rmin constant and the fact that CVaRτ (X + c) = CVaRτ (X) + c for any constant c.

3

4

Algorithms

We replace the scalar mean at each Q-edge with an empirical backup law, used both for risk-sensitive exploration (Thompson-sampled CVaR scores) and risk-sensitive backup (empirical Q-edge CVaR scores). V-nodes remain scalar, propagating a visit-weighted average of child Q-edge CVaR values. 4.1

Distributional Q-Edges

On a rollout, the scalar sample stored at Q-edge (sh , a) is Qt (sh , a) := rt (sh , a) + γ Vb τ (sh+1 ),

(7)

where Vb τ (sh+1 ) is the current scalar CVaR-sensitive continuation value. CATSO and PATSO differ only in how they represent the empirical law of these samples. Categorical Thompson Sampling with Optimism (CATSO) represents the Q-edge law as a categorical distribution on a fixed ordered grid ZN (sh , a) = {z0 (sh , a) < · · · < zN (sh , a)}. It maintains Dirichlet parameters α0 (sh , a), . . . , αN (sh , a), giving the posterior-center law bt (sh , a) = D

N X

pi (sh , a)δzi (sh ,a) ,

i=0

αi (sh , a) pi (sh , a) = PN . ℓ ℓ=0 α (sh , a)

(8)

When a backed-up sample Qt (sh , a) is observed, CATSO assigns it to the nearest grid atom and increments the corresponding Dirichlet parameter. The theoretical analysis uses a fixed grid chosen before search. In experiments, we also consider an adaptive-grid implementation, described in Appendix F (Figure 1), which expands the support range when new backed-up samples fall outside the current interval. This adaptive variant is treated as an implementation heuristic, introducing the projection bias of Remark 5.7, and is not the object of the fixed-grid Dirichlet posterior-tail proof. Particle Thompson Sampling with Optimism (PATSO) uses adaptive weighted particles. With current support S(sh , a) = {x1 , . . . , xM } and weights αj , bt (sh , a) = D

M X

p̄j (sh , a)δxj (sh ,a) ,

j=1

αj (sh , a) p̄j (sh , a) = PM . ℓ ℓ=1 α (sh , a)

(9)

Uncapped PATSO represents the empirical law exactly; capped PATSO keeps at most U particles per edge, adding the compression bias of Remark 5.8. 4.2

Discrete CVaR Computation Pm Both algorithms only evaluate CVaR of finitely supported laws. For P = i=1 wi δxi with x1 ≤ P Pj · · · ≤ xm and i wi = 1, set cj := i=1 wi , c0 := 0, k := min{j : cj ≥ τ }. Then ! k−1 1 X CVaRτ (P ) = wi xi + (τ − ck−1 )xk . (10) τ i=1 Since CATSO atoms and PATSO particles are stored sorted, this costs linear time in the support size. 4.3

CVaR Thompson Selection

At node sh , each action draws a Dirichlet sample over its current support — atoms {zi } for CATSO, particles {xj } for PATSO — yielding the Thompson-sampled CVaR score e cτ (sh , a) := P CVaRτ ( i Li (sh , a)δ· ). The selected action is at ∈ arg max {e cτ (sh , a) + B(n, sh , a)} ,

B(n, sh , a) := C

a∈A(sh )

Tsh (n)1/4 . (Tsh ,a (n) ∨ 1)1/2

(11)

The polynomial bonus follows the finite-sample MCTS analysis of Shah et al. [27]: Thompson sampling drives distributional exploration, while the bonus prevents premature underexploration as descendant values still evolve. 4

Algorithm 1: CATSO

Algorithm 2: PATSO

1 SelectAction(sh ): 1 SelectAction(sh ): 2 for a ∈ {1, 2, . . . , A} do 2 for a ∈ {1, 2, . . . , A} do 0 N 3 L(sh , a) ∼ Dir(α(sh , a)) 3 L(sh , a) ∼ Dir(α (sh , a), . . . , α (sh , a))
τ b c (sh , a) ← b cτ (sh , a) ← CVaRτ S(sh , a), L(sh , a)
4  τ CVaRτ [z0 (sh , a), . . . , zN (sh , a)], L(sh , a) 5 a = arg max b c (s , a) + B(n, s , a) a h h  τ 4 a = arg maxa b c (sh , a) + B(n, sh , a) 6 return a 5 return a 7 SimulateV(sh , t): 6 SimulateV(sh , t): 8 a = SelectAction(sh ) 7 a = SelectAction(sh ) 9 SimulateQ(sh , a, t) 8 SimulateQ(sh , a, t) 10 Tsh (t) = Tsh (t) + 1 9 Tsh (t) = Tsh (t) + 1 11 for a′ ∈ {1, 2, . . . , A} such that Ts ,a′ (t) > 0 do Ph 10 for a′ ∈ {1, 2, . . . , A} do 12 p̄j (sh , a′ ) ← αj (sh , a′ )/ ℓ αℓ (sh , a′ ) P ℓ ′ τ ′ 11 pi (sh , a′ ) ← αi (sh , a′ )/ N α (s , a ) h ℓ=0 13 b c (sh , a ) ←
12 b cτ (sh , a′ ) ← CVaRτ S(sh , a′ ), p̄(sh , a′ )
′ ′ ′ CVaRτ [z0 (sh , a ), . . . , zN (sh , a )], p(sh , a ) T (t) ′ P sh ,a bτ 14 V b cτ (sh , a′ ) P Tsh ,a′ (t) τ Ts (t) (sh ) ← a′ Ts (t) bτ h h b c (sh , a′ ) 13 V Ts (t) (sh ) ← a′ T (t) s h h 15 SimulateQ(sh , a, t): 14 SimulateQ(sh , a, t): 16 sh+1 ∼ P(·|sh , a), rt (sh , a) ∼ R(sh , a, sh+1 ) 15 sh+1 ∼ P(·|sh , a), rt (sh , a) ∼ R(sh , a, sh+1 ) 17 if node sh+1 not expanded then 16 if node sh+1 not expanded then 18 Rollout(sh+1 ) 17 Rollout(sh+1 ) 19 else 18 else 20 SimulateV(sh+1 , t) 19 SimulateV(sh+1 , t) 21 Tsh ,a (t) = Tsh ,a (t) + 1 20 Tsh ,a (t) = Tsh ,a (t) + 1 bτ 22 Qt (sh , a) = rt (sh , a) + γ V Ts (t) (sh+1 ) bτ h+1 Qt (sh , a) = rt (sh , a) + γ V 21 Ts (t) (sh+1 ) h+1 23 if Qt (sh , a) ∈ S(sh , a) then 22 i ← arg mini |Qt (sh , a) − zi (sh , a)| 24 αj (sh , a) += 1 // at the matching 23 αi (sh , a) ← αi (sh , a) + 1 atom xj 24 Update p(sh , a) = [p0 (sh , a), . . . , pN (sh , a)] 25 else 26 S(sh , a) ← S(sh , a) ∪ {Qt (sh , a)} 27 α(sh , a) ← (α(sh , a), 1)

Figure 1: Comparison of CATSO (left) and PATSO (right). Both methods share rollout, expansion, and SimulateV (which backs up scalar V-nodes using a visit-weighted average of child CVaR). They differ in their Q-edge representation (SimulateQ): CATSO uses categorical Dirichlet atoms, whereas PATSO uses adaptive weighted particles. SelectAction relies on the CVaR of a Thompson-sampled Q-edge plus a polynomial bonus B(n, s, a) (Eq. (11)). For expected-value planning, τ = 1.

4.4

Pseudocode

Figure 1 gives complete pseudocode. The two algorithms share tree traversal, rollout, and scalar V-backup; they differ only in the Q-edge representation and update. CATSO initializes every Q-edge with the unit Dirichlet prior (1, . . . , 1); PATSO starts with an empty particle set, with at least one forced visit per action before any Dirichlet draw so that α(s, a) is nonempty. 4.5

CVaR-Average V-Backup

Define the empirical CVaR score at each Q-edge:   bt (sh , a) , b cτ,t (sh , a) := CVaRτ D

(12)

and back up at V-nodes a visit-weighted average of child Q-edge CVaR scores, so that the parent Q-edge sample is VbTτs (t) (sh ) :=

X

h

a∈A(sh )

Tsh ,a (t) b cτ,t (sh , a), Tsh (t)

Qt (sh , a) = rt (sh , a) + γ VbTτs (t) (sh+1 ). (13) h

Distributions thus live only at Q-edges; V-nodes store scalar risk-sensitive summaries, avoiding distributional convolutions while still propagating lower-tail information up the tree. Note that (13) is P b a), which differ in general; an arithmetic average of CVaRs, not the CVaR of the mixture a wa D(s, we use the former because V-nodes are scalar by design. At τ = 1, CVaR1 equals the mean, so (13) P T (t) b reduces to the standard average-mean V-backup VbT1s (t) (sh ) = a Tssh ,a(t) Q Tsh ,a (t) (sh , a) with h h b h , a) = E b Q(s [X], recovering expected-value planning. Dt (sh ,a)

5

4.6 Root Recommendation After n rollouts, the planner returns the scalar root value Vbnτ (s0 ) from (13) and the empirical root Q-edge CVaR action b aCVaR ∈ arg max b cτ,n (s0 , a). (14) n a∈A(s0 )

Remark 4.1. Vbnτ (s0 ) is the object controlled by the main convergence theorem, while (14) is the risk-sensitive root action used in experiments.

5

Theoretical Analysis

We prove that CATSO and PATSO converge to the finite-depth nested CVaR target Ve τ (s0 ) in three steps: (i) a single-node CVaR bandit analysis; (ii) a one-step CVaR lifting lemma showing that child V-concentration implies plug-in Q-edge CVaR concentration; (iii) backward induction over the finite-depth tree. The main quantity controlled is the scalar root estimate   X Ts,a (n) bT (n) (s, a) , VbTτs (n) (s) = b cτ,n (s, a), b cτ,n (s, a) = CVaRτ D s,a Ts (n) a∈A(s)

whose absolute error upper-bounds the simple regret (5). The proof of step (i) is given in Appendix C, where we analyze the local CVaR bandit problem and derive the CATSO/PATSO suboptimal-arm pull bounds. Step (ii) is proved in Appendix D.1 through the one-step CVaR lifting lemma. Step (iii) is completed in the rest of Appendix D, which apply backward induction separately to CATSO and PATSO and then translate the root value-error bound into the risk-sensitive simple-regret guarantee. 5.1

CVaR-Objective Non-Stationary Bandits

Consider K arms with bounded non-stationary payoffs {Ra,t } ⊂ [0, R] and empirical law Fba,m := Pm 1 τ b t=1 δRa,t . Assume each Fa,m stabilizes to a limiting law Fa , and write ca := CVaRτ (Fa ), m τ τ ⋆ τ τ c⋆ := maxa ca , aτ ∈ arg maxa ca , b ca,m := CVaRτ (Fba,m ). The node-level scalar backup is the visit-weighted average K X Ta (n) τ b cτn := b c , (15) n a,Ta (n) a=1 which reduces to the standard average-mean backup at τ = 1. Definition 5.1 (Convergence with concentration). (Vbn )n≥1 converges with concentration to V , written plimn→∞ Vbn = V , if limn E[Vbn ] = V and there exists c > 0 with P(|Vbn − V | > ε) ≤ c/(nε2 ) for all n ≥ 1, ε > 0. Assumption 5.2 (Asymptotic CVaR stationarity with concentration). For every arm a, plimm→∞ b cτa,m = cτa , and the CVaR maximizer a⋆τ ∈ arg maxa cτa is unique. Remark 5.3 (Role of Assumption 5.2 in MCTS). Assumption 5.2 describes the local bandit problem at each V-node of the MCTS tree: fixing sh , each a ∈ A(sh ) is an arm with empirical score b cτa,m := τ τ τ e b Qm (sh , a) and limiting value ca := Q (sh , a). The armwise convergence is therefore not an extra modeling assumption: it is verified by backward induction via Lemma 5.5. If plimn→∞ Vbnτ (sh+1 ) = b τn (sh , a) = Q e τ (sh , a). The terminal Ve τ (sh+1 ) for every child sh+1 , the lemma yields plimn→∞ Q rollout estimator starts the induction, and the one-step lifting propagates it upward through the finitedepth tree. Uniqueness of a⋆τ is a standard nondegeneracy condition simplifying the suboptimal-pull bounds; ties can be handled by replacing a⋆τ with the optimal set A⋆τ := arg maxa cτa and treating only actions outside it as suboptimal. ea,T (t) ) plus Both algorithms select using the Thompson-sampled CVaR score e cτa (t) := CVaRτ (D a the polynomial bonus,   t1/4 τ I(t) ∈ arg max e ca (t) + C . (16) a∈[K] (Ta (t) ∨ 1)1/2 For a probability law Fon [0, Rmax ] and threshold c ∈ R, define the upper-tail risk information numτ,+ ber Kinf (F, c) := inf KL(F ∥G) : G ∈ P([0, Rmax ]), CVaRτ (G) ≥ c , and its grid-restricted  (N ),τ,+ version on ZN = {z0 < · · · < zN } ⊂ [0, Rmax ], Kinf (F, c) := inf KL(F ∥G) : G ∈ P(ZN ), CVaRτ (G) ≥ c . 6

Theorem 5.4 (CATSO/PATSO in CVaR non-stationary bandits). Suppose Assumption 5.2 holds, each arm is sampled once initially, and selection follows (16). Under the fixed-grid CATSO conditions of Appendix C.3 (resp. uncapped PATSO conditions of Appendix C.5), there exists CB < ∞ such that E[|b cτn − cτ⋆ |] ≤ CB n−1/2 ,

E[Ta (n)] ≤

(1 + ϵ0 ) log n + O(n1/2 ), •,τ,+ Kinf (Fa , cτ⋆ )

for every CVaR-suboptimal a ̸= a⋆τ and ϵ0 > 0, where • = (N ) for CATSO and is omitted for PATSO. The proof rests on the decomposition |b cτn − cτ⋆ | ≤

K X Ta (n) a=1

n

b cτa,Ta (n) − cτa + R

X Ta (n) a̸=a⋆ τ

n

.

The first term is controlled by Assumption 5.2; the second by the CVaR suboptimal-arm pull bound — the CVaR-average analogue of the standard scalar MCTS argument. 5.2 One-Step CVaR Lifting Why does MCTS require a non-stationary bandit formulation together with an asymptotic CVaR stationarity condition (Assumption 5.2)? Unlike variation-budget or change-point models for exogenous environment shifts, the non-stationarity in MCTS is endogenous to the search: at an internal node sh , pulling action a yields a backed-up sample Qi = Ri + γ V̂Nτ i (Si′ ), whose distribution drifts as the descendant value estimate V̂Nτ i (Si′ ) evolves. Because edge samples are not i.i.d. draws from a fixed law, stationary CVaR bandit guarantees [3, 25] cannot be applied recursively as-is. Instead, following the non-stationary MCTS paradigm established for expected-value and power-mean planning [27, 8], each node requires that its drifting arm payoffs eventually stabilize with polynomial concentration—ruling out persistent or adversarial drift. Assumption 5.2 is the CVaR analogue of this local stabilization condition, replacing empirical-mean convergence with empirical-CVaR convergence. Crucially, its armwise concentration requirement is an inductive property verified across the tree rather than an external environmental assumption: Lemma 5.5 below provides the induction step, showing that scalar CVaR concentration at child nodes (sh+1 ) implies W1 concentration of the plug-in backup law at (sh , a), which by CVaR Lipschitzness verifies Assumption 5.2 at depth h. Lemma 5.5 (One-step CVaR lifting for plug-in Q-edge laws). Fix (sh , a) and let (Xi , Si )i≥1 be i.i.d. one-step samples from the reward-transition kernel at (sh , a), with Xi ∈ [0, Rmax ] and Si ∼ P (· | (1) (M ) (m) sh , a). Assume P (· | sh , a) has finite support {sh+1 , . . . , sh+1 } with pm := P (sh+1 | sh , a) > 0, P (m) (m) n n τ (m) pmin := minm pm , and let Nm := i=1 1{Si = sh+1 }. For each sh+1 , let V (sh+1 ) be the (m) limiting scalar CVaR value and Vb τ (s ) its estimator after k local visits, with k

h+1

Rmax (m) (m) 0 ≤ Vbkτ (sh+1 ), V τ (sh+1 ) ≤ , 1−γ

(m)

(m)

plim Vbkτ (sh+1 ) = V τ (sh+1 ).

k→∞

(n)

:= Xi + γ VbNτ n (Si ), Gi := Xi + γV τ (Si ),, where Si (m) n bn (sh , a) := 1 Pn δ (n) , and NSni = Nm when Si = sh+1 , with empirical and population laws D i=1 q̄i n b τn (sh , a) := CVaRτ (D bn (sh , a)), Dτ (sh , a) is defined in (2). The corresponding CVaR Q-values Q τ τ Q (sh , a) := CVaRτ (D (sh , a)). Then

Define plug-in and oracle backed-up samples q̄i

b τ (sh , a) = Qτ (sh , a). plim Q n

n→∞

5.3 From Bandits to MCTS b τn (sh , a) bn (sh , a)) and Vbnτ (sh ) For each depth h, set Q := CVaRτ (D := P Tsh ,a (n) b τ (s , a). Q a Tsh (n) h,Tsh ,a (n) h Theorem 5.6 (Convergence of CATSO and uncapped PATSO). Run CATSO (resp. uncapped PATSO) on a finite-depth tree of depth H with bounded rewards and finite transition support at every Q-edge. Assume the terminal rollout estimator has an O(n−1/2 ) L1 rate, the local CVaR-optimal action at each internal node is unique, and Theorem 5.4 applies at every internal node. Then there exists C ′ > 0 such that h i E Vbnτ (s0 ) − Ve τ (s0 ) ≤ C ′ n−1/2 , 7

for the fixed-grid CATSO target and the uncapped PATSO target. For CATSO against the unprojected target with grid mesh ∆N , the bound becomes C ′ n−1/2 + O(∆N /τ ). Since SRτ (n) ≤ E[|Vbnτ (s0 ) − Ve τ (s0 )|], Theorem 5.6 yields SRτ (n) = O(n−1/2 ) up to the stated approximation terms. Remark 5.7 (CATSO discretization bias). The exact O(n−1/2 ) CATSO statement is for the fixed-grid target; against the unprojected backup law with mesh ∆N , CVaR Lipschitzness adds an O(∆N /τ ) bias, with depth-dependent constants absorbed. Remark 5.8 (Capped PATSO). Theorem 5.6 concerns uncapped PATSO. If capped PATSO satisfies uncap b cap , D bm W1 (D ) ≤ εU (s, a), then every CVaR estimate gains an additional εU (s, a)/τ bias, and m,U the root bound becomes C ′ n−1/2 + O(εU /τ ). 5.4 Memory and Computation CATSO. Each Q-edge stores N + 1 atoms with Dirichlet parameters, costing O(N ) per edge. Selection draws one Dirichlet vector and computes the discrete CVaR of the sorted categorical law in O(N ). Total memory after n rollouts is O(N |En |) over the explored Q-edges En . PATSO. Uncapped PATSO stores one weighted particle per distinct backed-up return (O(m) after m visits), representing the empirical Q-edge law exactly. For bounded memory, we cap at U particles per edge: when insertion would exceed U , the closest adjacent pair (xi , αi ), (xi+1 , αi+1 ) is merged into   αi xi + αi+1 xi+1 , αi + αi+1 , αi + αi+1 preserving the first moment. Capped PATSO uses O(U ) memory and O(U ) CVaR-selection cost per edge, with the compression bias quantified by Remark 5.8; increasing U trades memory for a smaller bias.

6

Experiments

We evaluate whether distributional Q-edge information improves planning when expected return and lower-tail return favor different actions. Each benchmark contains a safe option with modest reward and a risky option with attractive mean but poor lower-tail outcomes — directly testing the paper’s central claim that scalar MCTS does not preserve enough information for CVaR. All methods plan from the same initial state with the same rollout policy, search depth, and budget; the resulting root recommendation or value estimate is evaluated by independent Monte-Carlo rollouts. Detailed information about the environments, algorithms, and setup is provided in Appendix F. 6.1 Experimental Questions Q1 (lower-tail return). Does Monte-Carlo CVaR return of CATSO/PATSO exceed that of scalar baselines? Q2 (catastrophic outcomes). How often do recommended policies encounter environmentspecific catastrophic events (bankruptcy, trap cells, severe-cost transitions, cliff falls)? Q3 (root estimate quality). For oracle-evaluable environments, does the root CVaR value gap — the empirical analogue of the simple regret (5) — shrink with planning budget? Another interesting question that one can raise is how sensitive the algorithm performance according to the representation of the empirical distribution, because of the space limit, we postpone the answer and leave it in Appendix F. 6.2 Environments We evaluate on five stochastic benchmarks designed such that the mean-optimal and CVaR-optimal actions differ. Autonomous Vehicle [24]: A road network gridworld where faster routes (like highways) typically incur low costs but carry a risk of rare, extreme penalties (e.g., crashes). Two-Level Risky Treasure: A two-step environment forcing a choice between a guaranteed safe reward or a risky branch leading to either an extreme payout or a severe penalty. Risky Shortcut Gridworld: A navigation task offering a long, safe route versus a short, hazardous route where stochastic wind can push the agent off a cliff. Betting Game [4]: A repeated fractional betting scenario where aggressive wagers maximize expected growth but risk bankruptcy. Guarded Maze [14, 20, 21]: A maze featuring a short path with a high risk of triggering a severe penalty from a guard, contrasted with a longer, entirely safe alternative. 8

6.3 Algorithms and Baselines We compare CATSO and PATSO with scalar MCTS baselines (UCT-style planners and max/powerbackup variants), which store scalar Q-edge statistics and select on scalar value estimates. CATSO and PATSO instead store empirical Q-edge laws and select via the Thompson-sampled CVaR score plus the polynomial bonus (11). For scalar baselines, CVaR is applied only at evaluation time — the planner recommends a root action and we estimate its CVaR with independent rollouts — so all methods are compared on the same risk-sensitive objective. 6.4 Metrics d τ (n) = CVaR value gap. For oracle-evaluable environments, we compute the quantity Gap τ τ e b V (s0 ) − Vn (s0 ) (lower is better) at the root node. Monte-Carlo CVaR return. Lower-tail CVaR of the return distribution induced by the recommended root action follows (14) (higher is better). Note that we use static CVaR for evaluation, that is we take the average among τ -worst trajectories in the Monte-Carlo evaluation. Catastrophic count. Number of evaluation rollouts that encounter the environment-specific catastrophic event (lower is better; an interpretable safety metric, not a replacement for CVaR). 6.5 Results Figures 2a–3 summarize results across planning budgets for three environments, since the paper page limit is restricted, we refer to table 4 in appendix F for full results. CATSO and PATSO consistently improve the metrics that depend on lower-tail behavior. Scalar baselines, compressing each Q-edge to scalar statistics, are repeatedly drawn to high-mean branches with poor tails — favoring higher-cost path in Autonomous Vehicle and shorter risky routes in the Guarded Maze and Risky Shortcut Gridworld. By contrast, the distributional methods preserve enough information to identify actions with similar or even worse means but safer lower tails. The two distributional methods are complementary: CATSO is stable when the categorical grid is fine but incurs discretization bias on sharp or widely separated modes, whereas PATSO adapts its support to observed backed-up returns and handles sparse or multimodal laws naturally, with capping trading memory for a small compression bias (Remark 5.8). 6.6 Takeaways Three conclusions emerge. (i) Maintaining empirical Q-edge laws is useful in practice, not only in theory. (ii) The gains of CATSO and PATSO show up precisely on lower-tail metrics — CVaR value gap, Monte-Carlo CVaR return, catastrophic count. (iii) Scalar baselines remain competitive on expected return, indicating that the improvement reflects preserved tail information, not better exploration.

7

Discussion

CATSO and PATSO show that MCTS can reason about lower-tail risk without storing full return distributions at every node. The key design choice is to keep V-nodes scalar while maintaining empirical backup laws at Q-edges. This allows the planner to use CVaR-sensitive Thompson sampling for exploration and a CVaR-average scalar backup for value propagation. As a result, the methods preserve tail information that scalar mean-based MCTS discards, while retaining the standard O(n−1/2 ) finite-depth convergence rate up to representation bias. The theory is stated for a finite-depth nested CVaR target. This target is appropriate for risk-sensitive tree search, but it is not the same as static CVaR of the full infinite-horizon trajectory return. CATSO also depends on a finite grid and therefore incurs discretization bias, while capped PATSO trades memory for a tunable W1 compression bias. Future work should study distributional V-nodes, adaptive risk levels, learned model dynamics, and extensions to partially observed or continuouscontrol settings.

9

(a) CVaR value gap across environments vs. simulation budget. Lower is better.

(b) Monte-Carlo CVaR return of the policies recommended by each planner. Higher is better.

Figure 2: CVaR planning performance across environments: value gap during planning (top) and return of recommended policies (bottom) with ± standard deviation.

Figure 3: Catastrophic-event count across evaluation rollouts. Lower is better.

10

References [1] Aijun Bai, Feng Wu, and Xiaoping Chen. Bayesian mixture modelling and inference based thompson sampling in monte-carlo tree search. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper/ 2013/file/846c260d715e5b854ffad5f70a516c88-Paper.pdf. [2] Aijun Bai, Feng Wu, Zongzhang Zhang, and Xiaoping Chen. Thompson sampling based monte-carlo planning in pomdps. the International Conference on Automated Planning and Scheduling, 24(1), 2014. [3] Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric-Ambrym Maillard. Optimal thompson sampling strategies for support-aware cvar bandits. In International Conference on Machine Learning, pages 716–726. PMLR, 2021. [4] Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74:361–379, 2011. [5] Yu Chen, Yihan Du, Pihe Hu, Siwei Wang, Desheng Wu, and Longbo Huang. Provably efficient iterated cvar reinforcement learning with function approximation and human feedback. In International Conference on Learning Representations, 2024. [6] Y. Chow, A. Tamar, S. Mannor, and M. Pavone. Risk-sensitive and robust decision-making: a cvar optimization approach. In Advances in Neural Information Processing Systems, 2015. [7] Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018. [8] Tuan Dam, Odalric-Ambrym Maillard, and Emilie Kaufmann. Power mean estimation in stochastic monte-carlo tree search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 894–918. PMLR, 15–19 Jul 2024. URL https:// proceedings.mlr.press/v244/dam24a.html. [9] Tuan Quang Dam, Pascal Stenger, Lukas Schneider, Joni Pajarinen, Carlo D’Eramo, and Odalric-Ambrym Maillard. Monte-Carlo tree search with uncertainty propagation via optimal transport. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 12377–12401. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/ v267/dam25c.html. [10] Zilong Deng, Simon Khan, and Shaofeng Zou. Near-optimal sample complexity for iterated cvar reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, volume 258, pages 3907–3915. PMLR, 2025. [11] Yihan Du, Siwei Wang, and Longbo Huang. Provably efficient risk-sensitive reinforcement learning: Iterated cvar and worst path. In International Conference on Learning Representations, 2023. [12] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115–166, 2018. [13] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707–738, 2015. [14] Ido Greenberg, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Efficient riskaverse reinforcement learning. In Advances in Neural Information Processing Systems, volume 35, pages 32639–32652, 2022. 11

[15] Nir Greshler, David Ben Eli, Carmel Rabinovitz, Gabi Guetta, Liran Gispan, Guy Zohar, and Aviv Tamar. A bayesian approach to online planning. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=NS8z5FinYl. [16] Conor F Hayes, Mathieu Reymond, Diederik M Roijers, Enda Howley, and Patrick Mannion. Risk aware and multi-objective decision making with distributional monte carlo tree search. arXiv preprint arXiv:2102.00966, 2021. [17] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257–280, 2005. [18] Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a CVaR policy. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020. [19] Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1, 2006. [20] Yudong Luo, Guiliang Liu, Pascal Poupart, and Yangchen Pan. An alternative to variance: Gini deviation for risk-averse policy gradient. In Advances in Neural Information Processing Systems, volume 36, pages 60922–60946, 2023. [21] Yudong Luo, Yangchen Pan, Han Wang, Philip Torr, and Pascal Poupart. A simple mixture policy parameterization for improving sample efficiency of CVaR optimization. In RLC, pages 573–592, 2024. [22] Xinyi Ni, Guanlin Liu, and Lifeng Lai. Risk-sensitive reward-free reinforcement learning with cvar. In International Conference on Machine Learning, volume 235, pages 37999–38017. PMLR, 2024. [23] Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005. [24] Marc Rigter, Bruno Lacerda, and Nick Hawes. Risk-averse bayes-adaptive reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 1142–1154, 2021. [25] Charles Riou and Junya Honda. Bandit algorithms based on thompson sampling for bounded reward distributions. In Algorithmic Learning Theory, pages 777–826. PMLR, 2020. [26] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604–609, 2020. [27] Devavrat Shah, Qiaomin Xie, and Zhi Xu. Nonasymptotic analysis of monte carlo tree search. Operation Research, 70(6):3234–3260, 2022. [28] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016. [29] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144, 2018. [30] Aviv Tamar, Yonatan Glassner, and Shie Mannor. Optimizing the cvar via sampling. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1), 2015. [31] Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-minimax-optimal risk-sensitive reinforcement learning with cvar. In International Conference on Machine Learning, volume 202, pages 35864–35907. PMLR, 2023. [32] Zuyuan Zhang, Arnob Ghosh, and Tian Lan. Tail-risk-safe monte carlo tree search under pac-level guarantees. arXiv preprint, 2025. 12

Appendix of “Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search” Table of Contents A Notations

13

B CVaR and Wasserstein Preliminaries

14

B.1 Discrete CVaR Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

B.2 CVaR–Wasserstein Lipschitz Property . . . . . . . . . . . . . . . . . . . . . . . .

15

B.3 Empirical W1 Concentration . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

C Local CVaR Bandit Analysis

16

C.1 Non-Stationary CVaR Bandit Setup . . . . . . . . . . . . . . . . . . . . . . . . .

16

C.2 CATSO posterior CVaR tails on a fixed grid . . . . . . . . . . . . . . . . . . . . . .

17

C.3 CATSO CVaR suboptimal-arm pulls . . . . . . . . . . . . . . . . . . . . . . . . . .

20

C.4 PATSO Posterior CVaR Tails . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

C.5 PATSO CVaR suboptimal-arm pulls . . . . . . . . . . . . . . . . . . . . . . . . . .

31

D MCTS Convergence Proofs

37

D.1 One-Step CVaR Lifting for Q-Edges . . . . . . . . . . . . . . . . . . . . . . . . .

37

D.2 Convergence of CATSO in MCTS . . . . . . . . . . . . . . . . . . . . . . . . . .

38

D.3 Convergence of PATSO in MCTS . . . . . . . . . . . . . . . . . . . . . . . . . .

43

D.4 Risk-Sensitive Simple-Regret Bound . . . . . . . . . . . . . . . . . . . . . . . . .

46

E Memory Capping and W1 Compression

47

E.1 Merge-on-Insert (Precise Algorithm) . . . . . . . . . . . . . . . . . . . . . . . . .

47

E.2 Bound on W1 Error Under Capping . . . . . . . . . . . . . . . . . . . . . . . . .

48

F Experimental Details

48

F.1

Parameter Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

F.2

Environments and Algorithms Hyperparameters . . . . . . . . . . . . . . . . . . .

48

F.3

Full Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

F.4

Sensitivity of CATSO/PATSO Grid Representation . . . . . . . . . . . . . . . . .

51

G Limitations

A

52

Notations

Table 1 provides an overview of the standard notation adopted throughout this work. Context-specific notation, when required, will be explicitly defined within the corresponding definition. 13

Notation

Meaning

M = ⟨S, A, R, P, γ⟩

Discounted MDP with state space S, action space A, reward kernel R, transition kernel P, and discount γ ∈ (0, 1). Root state of the search tree. State or search-tree node at depth h. Finite search depth. Legal actions at state or node s. Random reward obtained after taking action a in state s and transitioning to S′. Lower and upper reward bounds. In the simplified presentation, rewards are often assumed to lie in [0, Rmax ]. Rollout policy used at terminal search depth. Discounted rollout return from state s at depth H under πro . CVaR risk level. Smaller τ focuses on a more extreme lower tail. Lower-tail conditional value-at-risk of random variable X. CVaR of a random variable with probability law P . Dirac point mass at x. Probability law of random variable Y , i.e., L(Y )(B) = P(Y ∈ B). 1-Wasserstein distance between probability laws P and Q. Convergence with concentration as in Definition 5.1.

s0 sh H A(s) R(s, a, S ′ ) Rmin , Rmax πro GπHro (s) τ CVaRτ (X) CVaRτ (P ) δx L(Y ) W1 (P, Q) plim Vbn = V n→∞

Table 1: General notation.

B

CVaR and Wasserstein Preliminaries

B.1 Discrete CVaR Formula −1 Derivation for (1) Recall the quantile function FX (u) = inf{x : FX (x) ≥ u} for u ∈ (0, 1]. By d

−1 the inverse-transform identity, if U ∼ Unif(0, 1) then FX (U ) = X, so conditioning on U ≤ τ samples the lower τ -tail of X. Averaging yields Z  −1  1 τ −1 CVaRτ (X) = E FX (U ) U ≤ τ = F (u) du, (17) τ 0 X

which, when FX is continuous and strictly increasing, reduces to the familiar E[X | X ≤ VaRτ (X)]. An equivalent Rockafellar–Uryasev variational form, n  o CVaRτ (X) = sup η − τ1 E (η − X)+ , (18) η∈R

handles atoms cleanly and is the form typically used for optimization. Pm P From (1) to (10). For P = i=1 wi δxi with x1 ≤ · · · ≤ xm , the CDF F (x) = i:xi ≤x wi is a right-continuous step function, so the quantile function is piecewise constant: −1 FX (u) = xj

where cj =

for u ∈ (cj−1 , cj ],

j = 1, . . . , m,

(19)

Pj

i=1 wi and c0 = 0. Letting k = min{j : cj ≥ τ } and splitting the integral at ck−1 ,

Z τ 0

−1 FX (u) du =

k−1 X Z cj j=1

=

k−1 X

cj−1

Z τ xj du +

xk du ck−1

wj xj + (τ − ck−1 ) xk .

j=1

The first sum collects the atoms fully contained in the lower tail (each contributing its full mass wj ), while the second term takes the fractional remainder τ − ck−1 of the boundary atom xk so that the total mass integrated equals exactly τ . Dividing by τ gives (10). Remark B.1. When τ = ck for some index k, the boundary term vanishes and (10) reduces to the Pk conditional mean c1k i=1 wi xi over the smallest k atoms, as expected. 14

B.2 CVaR–Wasserstein Lipschitz Property We first record the well-known Lipschitz property of CVaR with respect to the Wasserstein-1 distance. Lemma B.2 (CVaR is 1/τ -Lipschitz in W1 ). Let P and Q be probability distributions supported on [0, M ]. Then for any τ ∈ (0, 1]: 1 CVaRτ (P ) − CVaRτ (Q) ≤ W1 (P, Q). τ R τ Proof. Recall CVaRτ (P ) = τ1 0 FP−1 (u) du where FP−1 is the quantile function. By the quantile representation of W1 : Z 1 Z τ W1 (P, Q) = |FP−1 (u) − FQ−1 (u)| du ≥ |FP−1 (u) − FQ−1 (u)| du. 0

0

Therefore: Z
1 τ −1 FP (u) − FQ−1 (u) du τ 0 Z 1 τ −1 ≤ |FP (u) − FQ−1 (u)| du τ 0 1 ≤ W1 (P, Q). τ

CVaRτ (P ) − CVaRτ (Q) =

B.3 Empirical W1 Concentration This subsection proves Theorem B.3 in a way that keeps the random visit counts explicit. The object controlled below is the deterministic-prefix empirical law of the first m backups recorded at the root edge. The stopped-time child-value term is left visible, rather than implicitly replacing a random visit count by a deterministic sample size inside the proof. Theorem B.3 (Root-backup W1 reduction). Fix a root action a ∈ As0 and let τt be the global simulation index of the t-th visit to edge (s0 , a). On that visit, write (rt , St′ ) for the sampled reward and next state, and define Qt = rt + γ Vbτ (St′ ), Gt = rt + γ Ve (St′ ). t

Let

m X bm (s0 , a) := 1 D δ , m t=1 Qt

D(s0 , a) := L(G1 ).

Then PATSO satisfies m 
 γ X Rmax −1/2 b ∆t (a) + CFG E W1 Dm (s0 , a), D(s0 , a) ≤ m , m t=1 1−γ where

h i ∆t (a) := E Vbτt (St′ ) − Ve (St′ ) .

In particular, if the stopped-time child-value errors satisfy ∆t (a) ≤ CV t−1/2 for all t ≥ 1, then   
 bm (s0 , a), D(s0 , a) ≤ 2γCV + CFG Rmax m−1/2 . E W1 D 1−γ For CATSO, add O(Rmax /(N (1−γ))) discretization error. Proof. Fix a ∈ As0 and an integer m ≥ 1. Define the oracle empirical law m 1 X oracle bm D (s0 , a) := δG . m t=1 t Because each visit to the root edge draws a fresh reward/next-state sample from (R, P )(· | s0 , a), the oracle samples {Gt }m t=1 are i.i.d. with law D(s0 , a). By the triangle inequality for W1 ,


oracle oracle bm , D ≤ W1 D bm , D bm bm W1 D + W1 D ,D . | {z } | {z } (I)

15

(II)

(20)

I. coupling term.

Consider the natural coupling m

πm :=

1 X δ . m t=1 (Qt ,Gt )

bm and D b oracle , so the coupling characterization of W1 gives Its marginals are D m Z
oracle bm , D bm W1 D ≤ |x − y| dπm (x, y) m

=

1 X |Q − Gt | m t=1 t

=

γ X b Vτt (St′ ) − Ve (St′ ) . m t=1

m

(21)

Taking expectations in (21) yields m m i γ X γ X h b ′ ′ e E[(I)] ≤ E Vτt (St ) − V (St ) = ∆t (a). m t=1 m t=1

II. i.i.d. empirical-measure term. The oracle law D(s0 , a) is supported on [0, Rmax /(1 − γ)]. By the one-dimensional bounded-support case of Fournier and Guillin [13], there exists a universal constant CFG > 0 such that 
 b oracle , D ≤ CFG Rmax m−1/2 . E W1 D m 1−γ III. combine.

Substituting the bounds from Steps 1–2 into (20) proves the first claim: m 
 γ X Rmax −1/2 b ∆t (a) + CFG E W1 Dm (s0 , a), D(s0 , a) ≤ m . m t=1 1−γ

If moreover ∆t (a) ≤ CV t−1/2 for all t ≥ 1, then m m γ X γCV X −1/2 ∆t (a) ≤ t ≤ 2γCV m−1/2 , m t=1 m t=1

which gives the displayed O(m−1/2 ) bound. For CATSO, nearest-atom projection contributes an additional O(Rmax /(N (1 − γ))) term in W1 . Remark B.4 (Why Theorem 5.3 is stated with a fixed prefix). The counts Ta (n) and Ts,a (n) are bm (s0 , a) for a deterministic random variables. Theorem 5.3 therefore controls the empirical law D prefix length m. Passing from a fixed m to the adaptive choice m = Ts0 ,a (n) requires a separate stopped-time argument; that extra step is not hidden inside the proof above.

C

Local CVaR Bandit Analysis

C.1 Non-Stationary CVaR Bandit Setup Throughout Sections C.2–C.5 we fix a CVaR level τ ∈ (0, 1] and polynomial-bonus exponents bonus(t, n) := C

t1/4 . n1/2

For each arm a ∈ [K], let Fa denote its return law and define cτa := CVaRτ (Fa ),

cτ⋆ := max cτa , a∈[K]

a⋆τ ∈ arg max cτa . a∈[K]

We assume the maximizer is unique whenever a suboptimal-pull statement is made. 16

For a probability law F on [0, R] and a threshold c ∈ R, define the upper-tail risk information number n o τ,+ Kinf (F, c) := inf KL(F ∥G) : G ∈ P([0, R]), CVaRτ (G) ≥ c . On a fixed grid ZN = {z0 < · · · < zN } ⊂ [0, R], define the grid-restricted version n o (N ),τ,+ Kinf (F, c) := inf KL(F ∥G) : G ∈ P(ZN ), CVaRτ (G) ≥ c . When the empirical law of arm a after n pulls is Fba,n and the maintained posterior is sampled as a random law Pea,n , the posterior-sampled CVaR score is cτa,n := CVaRτ (Pea,n ). The risk-sensitive Thompson-with-bonus index is then Ut (a) := cτa,Ta (t) + C

t1/4 , (Ta (t) ∨ 1)1/2

where Ta (t) is the number of pulls of arm a before round t. For the detailed setup and assumptions, refer to section 5.1. C.2 CATSO posterior CVaR tails on a fixed grid CATSO is the only place where we currently prove a posterior large-deviation statement for a CVaRbased Thompson score. The proof uses the fixed-simplex Dirichlet geometry of Riou and Honda [25]. Lemma C.1 (Dirichlet convex-set tail; Riou and Honda [25]). Let ∆N := {q ∈ [0, 1]N +1 : PN P N +1 with αi ≥ 1, set A := i=0 qi = 1}. For α ∈ N i αi and p := α/A ∈ ∆N , and let L ∼ Dir(α). If C ⊆ ∆N is closed and convex and p ∈ / C, then  
N RH N/2 RH e1/12 √1 P(L ∈ C) ≤ CN A exp −A inf KL(p∥q) , CN := Γ(N , +1) 2π q∈C

P

where KL(p∥q) := i pi log(pi /qi ), with KL(p∥q) = +∞ if pi > 0 and qi = 0 for some i. Proposition C.2 (CATSO posterior CVaR upper tail on a fixed grid). Fix a risk level τ ∈ (0, 1] and an ordered grid ZN =P{z0 < z1 < · · · < zN } ⊂ [0, R]. Let α = αa (m) ∈ NN +1 with αa,i (m) ≥ 1, set A = Aa,m := i αa,i (m) and p = Pαa (m) := α/A ∈ ∆N , and draw La (m) ∼ Dir(αa (m)). Define the Thompson-sampled categorical law and its lower-tail CVaR X
TS TS b a,m b a,m D := La,i (m)δzi , b cτa,m := CVaRτ D , i

P and for q ∈ ∆N write CVaRτ (q; ZN ) := CVaRτ ( i qi δzi ) =

1 τ

Rτ 0

Fq−1 (u) du, with

(N ),τ,+ Kinf (p, c)

the grid-restricted upper-tail information number := inf{KL(p∥q) : q ∈ ∆N , CVaRτ (q; ZN ) ≥ c}. Then, for every c ∈ R, n (
o (N ),τ,+ RH N/2
(N + 1) CN Aa,m exp −Aa,m Kinf Pαa (m) , c , c > CVaRτ (Pαa (m) ; ZN ), τ P b ca,m ≥ c αa (m) ≤ 1, c ≤ CVaRτ (Pαa (m) ; ZN ). Equivalently, the Riou and Honda [25] exponential bound is valid in the genuine upper-tail regime (N ),τ,+ Kinf (Pαa (m) , c) > 0. Proof. Condition on the vector α = αa (m). Throughout the proof, write A = Aa,m ,

p = Pαa (m) =

If c ≤ CVaRτ (p; ZN ), 17

α . A

then the claimed bound is simply the trivial inequality
P b cτa,m ≥ c αa (m) ≤ 1. Thus it remains to prove the exponential bound in the case c > CVaRτ (p; ZN ). For q = (q0 , . . . , qN ) ∈ ∆N , define cumulative sums S−1 (q) := 0,

Sk (q) :=

k X

0 ≤ k ≤ N.

qi ,

i=0

For each k ∈ {0, . . . , N }, define ( Ck+ (c) :=

q ∈ ∆N : Sk−1 (q) ≤ τ ≤ Sk (q),

τ zk +

k−1 X

) qi (zi − zk ) ≥ τ c ,

i=0

where an empty sum is interpreted as zero. We first identify the CVaR superlevel set as a finite union of these sets. Fix q ∈ ∆N . If Sk−1 (q) ≤ τ ≤ Sk (q), PN then the lower τ -tail of the discrete law i=0 qi δzi consists of all atoms z0 , . . . , zk−1 and a fractional amount τ − Sk−1 (q) of the atom zk . Hence Z τ τ CVaRτ (q; ZN ) = Fq−1 (u) du =

0 k−1 X

qi zi + τ − Sk−1 (q) zk

i=0

= τ zk +

k−1 X

qi (zi − zk ).

i=0

Therefore, on the region Sk−1 (q) ≤ τ ≤ Sk (q), the condition CVaRτ (q; ZN ) ≥ c is exactly the affine inequality τ zk +

k−1 X

qi (zi − zk ) ≥ τ c.

i=0

Since for every q ∈ ∆N there exists at least one k ∈ {0, . . . , N } such that Sk−1 (q) ≤ τ ≤ Sk (q), we obtain N [ {q ∈ ∆N : CVaRτ (q; ZN ) ≥ c} = Ck+ (c). k=0

Each set Ck+ (c) is a closed convex polytope: it is the intersection of the simplex with finitely many affine half-space constraints, namely Sk−1 (q) ≤ τ,

Sk (q) ≥ τ,

τ zk +

k−1 X

qi (zi − zk ) ≥ τ c.

i=0

Because we are in the case c > CVaRτ (p; ZN ), we have p∈ / {q ∈ ∆N : CVaRτ (q; ZN ) ≥ c} . 18

Consequently,

p∈ / Ck+ (c)

for every k = 0, . . . , N.

Thus Lemma C.1 applies to each Ck+ (c). With the convention that inf ∅ KL(p∥·) = +∞, we get P

La (m) ∈ Ck+ (c)

(
RH N/2 αa (m) ≤ CN A exp −A

) inf

q∈Ck+ (c)

KL(p∥q) .

Using the union representation of the superlevel event and a union bound, ! N [
+ τ P b ca,m ≥ c αa (m) = P La (m) ∈ Ck (c) αa (m) k=0

≤

N X

P La (m) ∈ Ck+ (c) αa (m)

k=0 RH N/2 ≤ CN A

N X

(

)

exp −A

k=0

inf

q∈Ck+ (c)

KL(p∥q)

(

)

RH N/2 ≤ (N + 1)CN A exp −A min

inf

0≤k≤N q∈C + (c)

KL(p∥q) .

k

Finally, since {q ∈ ∆N : CVaRτ (q; ZN ) ≥ c} =

N [

Ck+ (c),

k=0

we have min

inf

0≤k≤N q∈C + (c)

(N ),τ,+

KL(p∥q) = inf {KL(p∥q) : q ∈ ∆N , CVaRτ (q; ZN ) ≥ c} = Kinf

(p, c).

k

Substituting p = Pαa (m) and A = Aa,m proves the claimed upper-tail bound. Remark C.3 (Why the statement is not valid with the same exponential prefactor for all c). If c ≤ CVaRτ (Pαa (m) ; ZN ), then Pαa (m) itself belongs to the CVaR superlevel set, and therefore
(N ),τ,+ Pαa (m) , c = 0. Kinf In this non-tail regime, the Riou and Honda [25] convex-set tail lemma is not applicable because its end-tail condition p ∈ / C fails. Moreover, the prefactor RH N/2 (N + 1)CN Aa,m

can be smaller than 1 for small Aa,m , so the original “for every c” exponential display is not a valid replacement for the trivial probability bound 1. Remark C.4 (Fractional CATSO projection weights). The proof above is fully justified by the integerparameter form of the Riou and Honda [25] lemma. If CATSO uses linear categorical projection and updates X αi ← αi + ωi , ωi ∈ [0, 1], ωi = 1, i

then the posterior parameters need not remain integer-valued. In that case one should either use hard binning, so that αP i ∈ N, or explicitly assume/prove the following real-parameter analogue: for α ∈ [1, ∞)N +1 , A = i αi , p = α/A, and every closed convex C ⊆ ∆N with p ∈ / C,   Dir N/2 P(L ∈ C) ≤ CN A exp −A inf KL(p∥q) , q∈C

Dir for a dimension-only constant CN . Under this real-parameter lemma, the proof of Proposition C.2 RH Dir is unchanged, with CN replaced by CN .

19

C.3 CATSO CVaR suboptimal-arm pulls This section provides CVaR suboptimal-arm pull bounds. The result is stated in reduction form: the post-convergence part is proved, and the optimal-arm lower-tail contribution is isolated as an explicit remainder. Lemma C.5 (CATSO posterior-center concentration on a fixed grid). Fix an arm a and grid ZN = {z0 < z1 < · · · < zN }. On the r-th local pull of arm a, CATSO adds a random weight vector Wa,r = (Wa,r,0 , . . . , Wa,r,N ) ∈ ∆N to the Dirichlet parameter, with E[Wa,r | Ha,r−1 ] = pa a.s. for all r ≥ 1 (some Pmpa ∈ ∆N ) and 0 ≤ Wa,r,i ≤ 1. With initial prior αa,i (0) = 1 for all i, define αa,i (m) = 1 + r=1 Wa,r,i and Pαa (m) := αa (m)/(m + N + 1). Then for every ε > 0, ∞ X

P ∥Pαa (m) − pa ∥∞ > ε < ∞.

m=1

Proof. Write m

W a,m :=

1 X Wa,r . m r=1

Pαa (m) =

1 + mW a,m , m+N +1

Then

where 1 = (1, . . . , 1). Hence Pαa (m) − pa =

m 1 − (N + 1)pa (W a,m − pa ) + . m+N +1 m+N +1

Let Ba := ∥1 − (N + 1)pa ∥∞ . Choose



 2Ba mε := ∨ 1. ε

For all m ≥ mε ,

Ba ε Ba ≤ ≤ . m+N +1 m 2

Therefore, for m ≥ mε , n  εo ∥Pαa (m) − pa ∥∞ > ε ⊆ ∥W a,m − pa ∥∞ > . 2 For each coordinate i, the sequence Wa,r,i − pa,i is a bounded martingale-difference sequence with range length at most 1. By Hoeffding–Azuma, !   m mε2 1 X ε P (Wa,r,i − pa,i ) > ≤ 2 exp − . m r=1 2 2 Taking a union bound over i = 0, . . . , N , for all m ≥ mε ,  
mε2 . P ∥Pαa (m) − pa ∥∞ > ε ≤ 2(N + 1) exp − 2 Thus

∞ X

  ∞ X
mε2 P ∥Pαa (m) − pa ∥∞ > ε ≤ mε + 2(N + 1) exp − < ∞. 2 m=m m=1 ε

Define the optimal-arm lower-tail term " n  X Lτn,CATSO := E 1 e cτa⋆τ (t) < cτ⋆ − C t=1

20

t1/4 (Na⋆τ (t) ∨ 1)1/2

# .

Lemma C.6 (Optimal-arm CATSO lower-tail term). Assume the fixed-grid CATSO setting of Lemma C.7 with each arm pulled once initially, and write aτ⋆ := a⋆τ , p⋆ := paτ⋆ , cτ⋆ := CVaRτ (p⋆ ; ZN ). Assume the fixed-grid posterior-center concentration: there exist BN , bN > 0 such that for every m ≥ 1 and s > 0,   P ∥Pα(m) − p⋆ ∥1 > s ≤ BN exp(−bN ms2 ). aτ ⋆

(N ),τ,−

Assume also the fixed-grid Dirichlet lower-tail bound: (p, c) := inf{KL(p∥q) : q ∈ P with Kinf ∆N , CVaRτ (q; ZN ) ≤ c}, for L ∼ Dir(α), A = i αi , p = α/A, and any c < CVaRτ (p; ZN ),  P   n o (N ),τ,− low N/2 P CVaRτ exp −A Kinf (p, c) . i Li δzi ≤ c α ≤ CN A Then Lτn,CATSO = O(1), and in particular Lτn,CATSO = O(n1/2 ). Proof. Write mt := Naτ⋆ (t) ∨ 1, Let

∆t := C

t1/4 1/2

.

mt

n o Et := e cτaτ⋆ (t) < cτ⋆ − ∆t .

It is enough to show that

∞ X

P(Et ) < ∞.

t=1

For m ≥ 1, define ∆t,m := C

t1/4 . m1/2

On the event {mt = m}, we have ∆t = ∆t,m , and m∆2t,m = C 2 t1/2 . We first record a quadratic lower bound for the lower-tail information number. The CVaR functional is 1/τ -Lipschitz in W1 , and on [0, R], W1 (p, q) ≤ Hence

R ∥p − q∥1 . 2

R ∥p − q∥1 . 2τ n o τ Gt,m := ∥Pα(m) − p ∥ ≤ ∆ . ⋆ 1 t,m aτ ⋆ R

|CVaRτ (p; ZN ) − CVaRτ (q; ZN )| ≤ Let On Gt,m , CVaRτ (Pα(m) ; ZN ) ≥ cτ⋆ − aτ ⋆

∆t,m . 2

Therefore, for every q ∈ ∆N satisfying CVaRτ (q; ZN ) ≤ cτ⋆ − ∆t,m , we have CVaRτ (Pα(m) ; ZN ) − CVaRτ (q; ZN ) ≥ aτ ⋆

∆t,m . 2

Using the same Lipschitz bound again, ∥Pα(m) − q∥1 ≥ aτ ⋆

τ ∆t,m . R

By Pinsker’s inequality, KL(Pα(m) ∥q) ≥ aτ ⋆

1 (m) τ2 2 ∥Pαaτ − q∥21 ≥ ∆ . ⋆ 2 2R2 t,m 21

Thus, on Gt,m , (N ),τ,−

Kinf



 , cτ⋆ − ∆t,m ≥ λτ ∆2t,m , Pα(m) aτ

λτ :=

⋆

τ2 . 2R2

Now decompose t X

P(Et ) ≤

P(Et , mt = m, Gt,m ) +

m=1

t X

P(mt = m, Gct,m ).

m=1

For the bad-center part, by the assumed posterior-center concentration,     τ 2 C 2 1/2 τ2 2 c t . P(Gt,m ) ≤ BN exp −bN m 2 ∆t,m = BN exp −bN R R2 Therefore

t X

P(mt = m, Gct,m ) ≤ BN t exp



m=1

 τ 2 C 2 1/2 −bN t . R2

For the good-center part, condition on the pre-round history. On {mt = m} ∩ Gt,m , the fixed-grid Dirichlet lower-tail bound gives
low P(Et | Ft−1 ) ≤ CN (m + N + 1)N/2 exp −(m + N + 1)λτ ∆2t,m . Since m ≤ t and m∆2t,m = C 2 t1/2 ,   ′ N/2 P(Et | Ft−1 ) ≤ CN t exp −λτ C 2 t1/2 , ′ for a constant CN depending only on N . Hence t X

  ′ N/2 P(Et , mt = m, Gt,m ) ≤ CN t exp −λτ C 2 t1/2 .

m=1

Combining the two bounds, ′ N/2 P(Et ) ≤ BN t exp(−c1 t1/2 ) + CN t exp(−c2 t1/2 )

for positive constants c1 , c2 . Since ∞ X

√

tr e−c t < ∞

for every fixed r < ∞, c > 0,

t=1

we get

∞ X τ sup Ln,CATSO ≤ P(Et ) < ∞. n≥1 t=1

This proves the claim. Lemma C.7 (CATSO CVaR suboptimal-arm pulls). Adopt the notation of Section 5.1, with each arm P having fixed grid law Fa = i pia δzi , pa ∈ ∆N , and unique CVaR-optimal arm a⋆τ . Suppose CATSO selects o n t1/4 I(t) ∈ arg max b cτa (t) + C (Ta (t)∨1) , 1/2 a∈[K]

where Ta (t) is the number of pulls of arm a before round t. Assume Lemma C.5, that p 7→ (N ),τ,+ (N ),τ,+ Kinf (p, u) is ∥ · ∥∞ -continuous on ∆N for every fixed u < cτ⋆ , and that c 7→ Kinf (Fa , c) is left-continuous at c = cτ⋆ . Then for every suboptimal a ̸= a⋆τ and every ϵ0 > 0, E[Ta (n)] ≤

(1 + ϵ0 ) log n (N ),τ,+

Kinf

(Fa , cτ⋆ )

22

+ O(n1/2 ).

Proof. Fix a CVaR-suboptimal arm a ̸= a⋆τ . Write (N ),τ,+

Ka (c) := Kinf

(Fa , c),

Ka⋆ := Ka (cτ⋆ ).

Since a is CVaR-suboptimal and the CVaR-optimal arm is unique, cτa < cτ⋆ . Thus, for ϵ1 > 0 small enough,

u := cτ⋆ − ϵ1

satisfies

cτa < u < cτ⋆ . For such ϵ1 , the fixed-grid CVaR superlevel set {q ∈ ∆N : CVaRτ (q; ZN ) ≥ u} is closed and does not contain pa . Hence Ka (u) > 0. Choose ϵ3 > 0 such that κ := κτa (ϵ1 , ϵ3 ) := Ka (cτ⋆ − ϵ1 ) − ϵ3 > 0. By the assumed continuity of (N ),τ,+

p 7−→ Kinf there exists ϵ2 > 0 such that, whenever

(p, cτ⋆ − ϵ1 ),

∥p − pa ∥∞ ≤ ϵ2 , we have

(N ),τ,+

Kinf (p, cτ⋆ − ϵ1 ) ≥ Ka (cτ⋆ − ϵ1 ) − ϵ3 = κ. In particular, on this event the information number is strictly positive. Therefore cτ⋆ − ϵ1 > CVaRτ (p; ZN ), (N ),τ,+

because otherwise p itself would be feasible in the definition of Kinf (p, cτ⋆ − ϵ1 ), forcing the information number to be zero. Hence the corrected upper-tail Proposition C.2 is applicable on this good-center event. For clarity, write Pα(m) a for the posterior center of arm a after exactly m local updates, so that, on the event {Ta (t) = m}, Pαa (t) = Pα(m) , a

Aa,t = m + N + 1.

The extra N + 1 comes from the unit Dirichlet prior on the N + 1 grid atoms. Define the bonus

t1/4 . (Ta (t) ∨ 1)1/2 &  ' 1/2 C 1/2 n , mβ := ϵ1   log n + (N/2 + 1) log log(en) mKL := , κ βt (a) := C

Set

and m0 := max{1, mβ , mKL }. We first decompose the number of pulls of arm a. The event {I(t) = a, Ta (t) < m0 } can occur at most m0 times. Therefore " n # X E[Ta (n)] = E 1{I(t) = a} ≤ m0 + A1 + A2 , t=1

23

where " n # X  τ τ A1 := E 1 I(t) = a, Ta (t) ≥ m0 , b ca (t) ≥ c⋆ − βt (a), ∥Pαa (t) − pa ∥∞ ≤ ϵ2 , t=1

and " n # X    A2 := E 1 I(t) = a, Ta (t) ≥ m0 , [b cτa (t) < cτ⋆ − βt (a)] ∪ ∥Pαa (t) − pa ∥∞ > ϵ2 . t=1

Bound on A1 . Let Ft−1 denote the history immediately before the Thompson draw at round t. On the event Ta (t) ≥ m0 , we have βt (a) = C

t1/4 n1/4 n1/4 ≤ C 1/2 ≤ C 1/2 ≤ ϵ1 . 1/2 (Ta (t) ∨ 1) m0 m β

Hence

b cτa (t) ≥ cτ⋆ − βt (a)

=⇒

b cτa (t) ≥ cτ⋆ − ϵ1 .

Dropping the event {I(t) = a}, which can only increase the probability, we obtain n X    A1 ≤ E 1 Ta (t) ≥ m0 , ∥Pαa (t) − pa ∥∞ ≤ ϵ2 P (b cτa (t) ≥ cτ⋆ − ϵ1 | Ft−1 ) . t=1

Now fix a history with Ta (t) = m ≥ m0

∥Pαa (t) − pa ∥∞ ≤ ϵ2 .

and

By the choice of ϵ2 , (N ),τ,+

Kinf

(Pαa (t) , cτ⋆ − ϵ1 ) ≥ κ > 0.

Thus cτ⋆ −ϵ1 is a genuine upper-tail threshold for the posterior center, and the corrected Proposition C.2 gives RH P (b cτa (t) ≥ cτ⋆ − ϵ1 | Ft−1 ) ≤ (N + 1)CN (m + N + 1)N/2 exp {−(m + N + 1)κ} .

If one uses the real-parameter Dirichlet tail lemma instead of the integer-count Riou and Honda [25] RH lemma, replace CN by the corresponding dimension-only constant. Define

fκ (m) := (m + N + 1)N/2 exp {−(m + N + 1)κ} .

The function fκ (m) is decreasing for all sufficiently large m. Since m0 → ∞ with n, for all sufficiently large n, sup fκ (m) = fκ (m0 ). m≥m0

The finitely many smaller n can be absorbed into the final O(n1/2 ) term. Therefore RH A1 ≤ (N + 1)CN n (m0 + N + 1)N/2 exp {−(m0 + N + 1)κ} .

Since m0 ≥ mKL and fκ is eventually decreasing, RH A1 ≤ (N + 1)CN n (mKL + N + 1)N/2 exp {−mKL κ} · O(1).

By definition of mKL , exp{−mKL κ} ≤

1 . n[log(en)]N/2+1

Also mKL + N + 1 = O(log n). Hence A1 ≤ O(1)

(log n)N/2 = O(1). [log(en)]N/2+1 24

Bound on A2 .

Write A2 ≤ R1 + R2 ,

where R1 := E

" n X

# 1 {I(t) = a, b cτa (t) < cτ⋆ − βt (a)}

,

t=1

and

" n # X  R2 := E 1 I(t) = a, ∥Pαa (t) − pa ∥∞ > ϵ2 . t=1

For R2 , the event {I(t) = a, Ta (t) = m} can occur at most once for each m ∈ {0, . . . , n − 1}, namely at the round of the (m + 1)-st pull of arm a. Hence n−1  X  R2 ≤ P ∥Pα(m) − p ∥ > ϵ = O(1), a ∞ 2 a m=0

by Lemma C.5. The m = 0 term is just a finite constant. For R1 , suppose that I(t) = a

and b cτa (t) < cτ⋆ − βt (a).

Then Ut (a) = b cτa (t) + βt (a) < cτ⋆ . Since I(t) = a maximizes the index, Ut (a⋆τ ) ≤ Ut (a) < cτ⋆ . Therefore b cτa⋆τ (t) < cτ⋆ − βt (a⋆τ ). Consequently, " n # o X n R1 ≤ E 1 b cτa⋆τ (t) < cτ⋆ − βt (a⋆τ ) = Lτn,CATSO ≤ O(n1/2 ). t=1

Combining the bounds on A1 , R1 , and R2 , we obtain E[Ta (n)] ≤ m0 + O(n1/2 ) + O(1). Since m0 ≤ 1 + mβ + mKL , we have m0 ≤ Hence E[Ta (n)] ≤

log n + (N/2 + 1) log log(en) + O(n1/2 ). κ

log n + (N/2 + 1) log log(en) + O(n1/2 ) + O(n1/2 ). κτa (ϵ1 , ϵ3 )

It remains to choose ϵ1 and ϵ3 . By the assumed left-continuity of (N ),τ,+

c 7−→ Kinf

(Fa , c)

at c = cτ⋆ , for every ϵ0 > 0 we can choose ϵ1 > 0 small enough, and then ϵ3 > 0 small enough, so that 1 1 + ϵ0 /2 ≤ (N ),τ,+ . κτa (ϵ1 , ϵ3 ) K (Fa , cτ⋆ ) inf

Since log log(en) = o(log n), 25

for all sufficiently large n, (1 + ϵ0 ) log n log n + (N/2 + 1) log log(en) ≤ (N ),τ,+ . τ κa (ϵ1 , ϵ3 ) K (Fa , cτ⋆ ) inf

1/2

Absorbing the finitely many small-n cases into the O(n

) term gives

(1 + ϵ0 ) log n

+ O(n1/2 ),

E[Ta (n)] ≤

(N ),τ,+

Kinf

(Fa , cτ⋆ )

which proves the lemma. C.4

PATSO Posterior CVaR Tails

Assumption C.8 (PATSO posterior CVaR upper tail, history-conditional). Fix τ ∈ (0, 1]. For each arm a, local sample size m ≥ 1, and threshold c ∈ (cτa , R], assume that for every η > 0 there exists Cτ,η,c > 0 such that, whenever the pre-round history has Ta (t) = m, n  o τ,+ b P (b cτa (t) ≥ c| Ft−1 ) ≤ Cτ,η,c exp −m Kinf (Fa,m , c) − η a.s. Proposition C.9 (Uncapped PATSO posterior CVaR upper tail). Fix τ ∈ (0, 1] and consider uncapped PATSO, so that after m ≥ 1 pulls of arm a the particle support equals the support of the empirical PMm law of the first m returns. Write Fba,m = j=1 pj δsj with s1 < · · · < sMm , pj = nj /m, nj ∈ N, P j nj = m, draw La (m) ∼ Dir(n1 , . . . , nMm ), and define X TS TS b a,m b a,m D := La,j (m)δsj , b cτa,m := CVaRτ (D ). j τ,+ For a probability law F on [0, R], set Kinf (F, c) := inf{KL(F ∥G) : G ∈ P([0, R]), CVaRτ (G) ≥ c}. Then for every c ∈ R and η > 0 there exists Cη < ∞, independent of m, such that   n
o τ,+ b P b cτa,m ≥ c Fba,m ≤ Cη exp −m Kinf (Fa,m , c) − η a.s.; 1 1 one may take Cη = exp{ 12 + 2πη }. In particular, Assumption C.8 holds for uncapped exact-particle PATSO.

Proof. Fix m ≥ 1 and condition on the empirical law Fba,m =

Mm X

pj δsj ,

s1 < · · · < sMm ,

pj =

j=1

nj . m

Under uncapped PATSO, the particle support and the Dirichlet parameters are therefore fixed by Fba,m : Sa (m) = {s1 , . . . , sMm },

αa (m) = (n1 , . . . , nMm ).

For readability, write M := Mm , p = (p1 , . . . , pM ), and   M   X qj = 1 . ∆M −1 := q = (q1 , . . . , qM ) ∈ [0, 1]M :   j=1

For q ∈ ∆M −1 , define cumulative sums S0 (q) := 0,

Sk (q) :=

k X

qj ,

1 ≤ k ≤ M.

j=1

For each k ∈ {1, . . . , M }, define   Ck+ (c) := q ∈ ∆M −1 : Sk−1 (q) ≤ τ ≤ Sk (q),  26

τ sk +

k−1 X j=1

  qj (sj − sk ) ≥ τ c . 

As in the fixed-grid CATSO proof, on the region Sk−1 (q) ≤ τ ≤ Sk (q), PM the lower-tail CVaR of the discrete law j=1 qj δsj is given by   M k−1 k−1 X X X
  τ CVaRτ qj δsj = qj sj + τ − Sk−1 (q) sk = τ sk + qj (sj − sk ). j=1

Therefore,

j=1

j=1

 

   M M  X [ q ∈ ∆M −1 : CVaRτ  qj δsj  ≥ c = Ck+ (c).   j=1

k=1

Each Ck+ (c) is a closed convex polytope, since it is the intersection of the simplex with finitely many affine half-space constraints.

Define the support-restricted information number     M   X KSτ,+ (p, c) := inf KL(p∥q) : q ∈ ∆M −1 , CVaRτ  qj δsj  ≥ c .   j=1

Here KL(p∥q) :=

M X

pj log

j=1

pj . qj

If c ≤ CVaRτ (Fba,m ), then p itself is feasible in the definition of Kτ,+ (Fba,m , c), so inf

τ,+ b Kinf (Fa,m , c) = 0.

Thus

  n  o τ,+ b P b cτa,m ≥ c Fba,m ≤ 1 ≤ Cη emη = Cη exp −m Kinf (Fa,m , c) − η ,

provided Cη ≥ 1. Hence the desired inequality is trivial in this non-tail case. It remains to consider the genuine upper-tail case c > CVaRτ (Fba,m ). Then p ∈ / Ck+ (c) for every k. Applying the Riou and Honda [25] Dirichlet convex-set tail bound to PM each closed convex set Ck+ (c), with total Dirichlet mass m = j=1 nj , gives ( )   + RH (M −1)/2 P La (m) ∈ C (c) Fba,m ≤ C m exp −m inf KL(p∥q) , M −1

k

q∈Ck+ (c)

where

 M −1 e1/12 1 √ . Γ(M ) 2π Using the union representation of the CVaR superlevel event and a union bound,    RH (M −1)/2 P b cτa,m ≥ c Fba,m ≤ M CM × exp −mKSτ,+ (p, c) . −1 m RH CM −1 =

Now compare the support-restricted and unrestricted information numbers. Every probability law of the form M X qj δsj , q ∈ ∆M −1 , j=1

27

is also an element of P([0, R]). Therefore the unrestricted feasible set is larger, and hence τ,+ b Kinf (Fa,m , c) ≤ KSτ,+ (p, c).

Consequently, n o τ,+ b exp{−mKSτ,+ (p, c)} ≤ exp −mKinf (Fa,m , c) . It remains only to control the dimension-dependent prefactor uniformly in m. Set r m d := M − 1, x := . 2π Since M = d + 1, d  e1/12 1 √ md/2 Γ(d + 1) 2π d+1 d = e1/12 x d! ∞ X r+1 r ≤ e1/12 x r! r=0

RH (M −1)/2 M CM = (d + 1) −1 m

= e1/12 (1 + x)ex ≤ e1/12 e2x . For every η > 0, r m 1 2x = 2 ≤ ηm + . 2π 2πη Hence RH (M −1)/2 M CM ≤ exp −1 m

Define

 Cη := exp



1 1 + 12 2πη

1 1 + 12 2πη



eηm .

 .

Combining the previous displays gives   n  o τ,+ b P b cτa,m ≥ c Fba,m ≤ Cη exp −m Kinf (Fa,m , c) − η . This proves the claim. Lemma C.10 (PATSO empirical-law concentration). Fix an arm a. Suppose the local observations from arm a, Xa,1 , Xa,2 , . . . , are i.i.d. with law Fa . Define the empirical law m 1 X Fba,m := δX . m r=1 a,r

Let DL denote the Lévy distance. Then, for every ϵ > 0, ∞ X

  P DL (Fba,m , Fa ) > ϵ < ∞.

m=1

Proof. Let ∥Fba,m − Fa ∥∞ := sup Fba,m (x) − Fa (x) x∈R

be the Kolmogorov distance between the two distribution functions. The Lévy distance is bounded by the Kolmogorov distance: DL (Fba,m , Fa ) ≤ ∥Fba,m − Fa ∥∞ . 28

Indeed, if ∥Fba,m − Fa ∥∞ ≤ ϵ, then for every x, Fa (x − ϵ) − ϵ ≤ Fa (x) − ϵ ≤ Fba,m (x) ≤ Fa (x) + ϵ ≤ Fa (x + ϵ) + ϵ, which is exactly the defining Lévy-distance condition with radius ϵ. By the Dvoretzky–Kiefer–Wolfowitz inequality,   P ∥Fba,m − Fa ∥∞ > ϵ ≤ 2 exp(−2mϵ2 ). Therefore

  P DL (Fba,m , Fa ) > ϵ ≤ 2 exp(−2mϵ2 ).

Summing over m,

∞ X

∞  X 2 b P DL (Fa,m , Fa ) > ϵ ≤ 2 e−2mϵ < ∞.



m=1

m=1

Lemma C.11 (Optimal-arm lower-tail term for uncapped PATSO). Assume the stationary local-bandit model for the optimal arm a⋆τ , with rewards supported on [0, R], and write aτ⋆ := a⋆τ , F⋆ := Faτ⋆ , cτ⋆ := CVaRτ (F⋆ ). For uncapped PATSO, after m ≥ 1 pulls of aτ⋆ the empirical and Thompsonsampled particle laws are 1 Fb⋆,m = m

m X

δX⋆,r =

r=1

Mm X n

j

m δsj ,

Fe⋆,m =

j=1

Mm X

L ∼ Dir(n1 , . . . , nMm ).

Lj δsj ,

j=1

Assume each arm is initialized once, and let e cτaτ⋆ (t) := CVaRτ (Fe⋆,Naτ (t) ). Then ⋆ " n # n o X τ τ τ t1/4 Ln,PATSO := E 1 e caτ⋆ (t) < c⋆ − C (N τ (t)∨1)1/2 = O(1), a⋆

t=1

and in particular Lτn,PATSO = O(n1/2 ). Proof. Let mt := Naτ⋆ (t) ∨ 1, Define the event

∆t := C

t1/4 1/2

.

mt

n o Et := e cτaτ⋆ (t) < cτ⋆ − ∆t .

It is enough to show that

∞ X

P(Et ) < ∞.

t=1

We use two standard concentration facts. First, by the Dvoretzky–Kiefer–Wolfowitz inequality, for every m ≥ 1 and u > 0,   2 P ∥Fb⋆,m − F⋆ ∥∞ > u ≤ 2e−2mu . Second, conditionally on Fb⋆,m , the Dirichlet-weighted CDF Fe⋆,m (x) satisfies the Bayesian-bootstrap DKW bound   2 P ∥Fe⋆,m − Fb⋆,m ∥∞ > u Fb⋆,m ≤ 2me−cB mu 29

for a universal constant cB > 0. Indeed, at each empirical support point sk , X Fe⋆,m (sk ) = Lj j≤k

is beta-distributed with mean Fb⋆,m (sk ), by aggregation of Dirichlet coordinates. Applying a beta Chernoff bound and union-bounding over at most m support points gives the display. Because the laws are supported on [0, R], W1 (P, Q) ≤ R∥FP − FQ ∥∞ . Also, CVaR is 1/τ -Lipschitz in W1 . Hence R |CVaRτ (P ) − CVaRτ (Q)| ≤ ∥FP − FQ ∥∞ . τ Now fix t and condition on the event mt = m. Set ∆t,m := C Then

t1/4 . m1/2

m∆2t,m = C 2 t1/2 .

If

CVaRτ (Fe⋆,m ) < cτ⋆ − ∆t,m , then at least one of the following two events occurs:   ∆t,m Gt,m := CVaRτ (Fb⋆,m ) < cτ⋆ − , 2 or   ∆t,m Ht,m := CVaRτ (Fe⋆,m ) < CVaRτ (Fb⋆,m ) − . 2 For Gt,m , the CVaR–Kolmogorov Lipschitz bound and DKW give   τ ∆t,m P(Gt,m ) ≤ P ∥Fb⋆,m − F⋆ ∥∞ > 2R ! 2 2 τ ∆t,m ≤ 2 exp −2m 4R2  2 2  τ C 1/2 = 2 exp − t . 2R2 For Ht,m , conditionally on Fb⋆,m ,   τ ∆t,m b b e b P(Ht,m | F⋆,m ) ≤ P ∥F⋆,m − F⋆,m ∥∞ > F⋆,m 2R ! τ 2 ∆2t,m ≤ 2m exp −cB m 4R2   cB τ 2 C 2 1/2 ≤ 2t exp − t , 4R2 because m ≤ t. Therefore, using the union bound over possible values m ∈ {1, . . . , t}, √ P(Et ) ≤ C1 t exp(−C2 t) for constants C1 , C2 > 0 depending only on (C, τ, R). Since ∞ √ X te−C2 t < ∞, t=1

we get sup Lτn,PATSO ≤

n≥1

∞ X t=1

This proves the claim. 30

P(Et ) < ∞.

C.5 PATSO CVaR suboptimal-arm pulls Lemma C.12 (PATSO CVaR suboptimal-arm pulls). Adopt the notation of Section 5.1 with a⋆τ the unique CVaR-optimal arm, and write Ta (t) := Ta (t − 1), b cτa (t) := e cτa,Ta (t) . Assume PATSO selects n o t1/4 I(t) ∈ arg max b cτa (t) + C (Ta (t)∨1) , 1/2 a∈[K]

τ,+ and that F 7→ Kinf (F, u) is DL -continuous for every fixed u < cτ⋆ and c left-continuous at c = cτ⋆ . Then for every suboptimal a ̸= a⋆τ and every ϵ0 > 0,

E[Ta (n)] ≤

τ,+ 7→ Kinf (Fa , c) is

(1 + ϵ0 ) log n + O(n1/2 ). τ,+ Kinf (Fa , cτ⋆ )

Proof. Fix a CVaR-suboptimal arm a ̸= a⋆τ , and write t1/4 . (Ta (t) ∨ 1)1/2 Assume each arm is initialized once, or equivalently absorb the finitely many rounds with Ta (t) = 0 into the final O(1) term. Hence below Fba,m is only used for m ≥ 1. βt (a) := C

Since a is CVaR-suboptimal and the CVaR-optimal arm is unique, cτa < cτ⋆ . Choose 0 < ϵ1 < cτ⋆ − cτa so that u := cτ⋆ − ϵ1 satisfies cτa < u < cτ⋆ . Let η, ϵ3 > 0, and define τ,+ κτa (ϵ1 , η, ϵ3 ) := Kinf (Fa , cτ⋆ − ϵ1 ) − η − ϵ3 . For ϵ1 , η, ϵ3 sufficiently small, κτa (ϵ1 , η, ϵ3 ) > 0. τ,+ Indeed, by left-continuity of c 7→ Kinf (Fa , c) at c = cτ⋆ , and because cτ⋆ > cτa , the information number at cτ⋆ − ϵ1 is positive for ϵ1 small enough.

Set C∗ := Cτ,η,cτ⋆ −ϵ1 , &  ' 1/2 C 1/2 mβ := n , ϵ1   log(C∗ n) mKL := , κτa (ϵ1 , η, ϵ3 ) and m0 := max{1, mβ , mKL }. For small n, one may replace log(C∗ n) by log(eC∗ n); this only changes constants and avoids irrelevant negative-log edge cases. We decompose E[Ta (n)] = E

" n X

# 1{I(t) = a} ≤ m0 + B1 + B2 ,

t=1

where " n # o X n τ τ B1 := E 1 I(t) = a, Ta (t) ≥ m0 , b ca (t) ≥ c⋆ − βt (a), DL (Fba,Ta (t) , Fa ) ≤ ϵ2 , t=1

and " n # h io X n B2 := E 1 I(t) = a, Ta (t) ≥ m0 , [b cτa (t) < cτ⋆ − βt (a)] ∪ DL (Fba,Ta (t) , Fa ) > ϵ2 . t=1

31

Dropping the event {I(t) = a} and conditioning on the local sample size,

Bound on B1 .

n n−1 X X

B1 ≤

  P b cτa (t) ≥ cτ⋆ − βt (a), DL (Fba,m , Fa ) ≤ ϵ2 , Ta (t) = m .

t=1 m=m0

If m ≥ m0 ≥ mβ and t ≤ n, then βt (a) = C

n1/4 t1/4 ≤ C ≤ ϵ1 . 1/2 (m ∨ 1)1/2 m0

Therefore b cτa (t) ≥ cτ⋆ − βt (a)

=⇒

b cτa (t) ≥ cτ⋆ − ϵ1 .

Hence B1 ≤

n n−1 X X

  P b cτa (t) ≥ cτ⋆ − ϵ1 , DL (Fba,m , Fa ) ≤ ϵ2 , Ta (t) = m .

t=1 m=m0

By the assumed continuity of τ,+ F 7→ Kinf (F, cτ⋆ − ϵ1 )

at Fa , for every ϵ3 > 0 there exists ϵ2 > 0 such that DL (Fba,m , Fa ) ≤ ϵ2

=⇒

τ,+ b τ,+ Kinf (Fa,m , cτ⋆ − ϵ1 ) ≥ Kinf (Fa , cτ⋆ − ϵ1 ) − ϵ3 .

Using the history-conditional form of Assumption C.8, on the event {Ta (t) = m, DL (Fba,m , Fa ) ≤ ϵ2 }, we have P (b cτa (t) ≥ cτ⋆ − ϵ1 |Ft−1 ) ≤ C∗ exp {−mκτa (ϵ1 , η, ϵ3 )} . Thus B1 ≤ C∗

n n−1 X X

  exp {−mκτa (ϵ1 , η, ϵ3 )} × P DL (Fba,m , Fa ) ≤ ϵ2 , Ta (t) = m .

t=1 m=m0

Since m ≥ m0 ,

exp{−mκτa } ≤ exp{−m0 κτa }.

Also, for each fixed t, n−1 X

  P DL (Fba,m , Fa ) ≤ ϵ2 , Ta (t) = m ≤ 1.

m=m0

Therefore B1 ≤ C∗ n exp {−m0 κτa (ϵ1 , η, ϵ3 )} ≤ 1 by the definition of mKL . Bound on B2 .

Write B2 ≤ R1 + R2 ,

where R1 := E

" n X

# 1 {I(t) = a, b cτa (t) < cτ⋆ − βt (a)}

= O(n1/2 ),

t=1

and

" n # o X n b R2 := E 1 I(t) = a, Ta (t) ≥ m0 , DL (Fa,Ta (t) , Fa ) > ϵ2 . t=1

For R2 , the event {I(t) = a, Ta (t) = m} 32

can occur at most once for each m. Hence n−1  X  R2 ≤ P DL (Fba,m , Fa ) > ϵ2 = O(1) m=m0

by Lemma C.10. This is why it is cleaner to sum from m = m0 , rather than from m = 0. Combining the bounds on B1 , R1 , and R2 , E[Ta (n)] ≤ m0 + O(n1/2 ) + O(1). By the definition of m0 , m0 ≤

log(C∗ n) + O(n1/2 ). κτa (ϵ1 , η, ϵ3 )

Finally, by left-continuity of τ,+ c 7→ Kinf (Fa , c) at c = cτ⋆ , for every ϵ0 > 0 we can choose ϵ1 , η, ϵ3 > 0 sufficiently small so that

1 κτa (ϵ1 , η, ϵ3 )

≤

1 + ϵ0 /2 . τ,+ Kinf (Fa , cτ⋆ )

Since C∗ is fixed after ϵ1 , η are fixed, log(C∗ n) = log n + O(1). Therefore, for all sufficiently large n, log(C∗ n) (1 + ϵ0 ) log n ≤ τ,+ . κτa (ϵ1 , η, ϵ3 ) Kinf (Fa , cτ⋆ ) Absorbing finitely many small-n cases into the O(n1/2 ) term gives E[Ta (n)] ≤

(1 + ϵ0 ) log n + O(n1/2 ), τ,+ Kinf (Fa , cτ⋆ )

as claimed. Remark C.13 (Uncapped PATSO). The statement above is for the uncapped particle representation. A cap-and-merge implementation adds a separate approximation bias, which should be tracked explicitly rather than folded into the risk-KL term. Lemma C.14. Let CATSO be applied to a non-stationary bandit problem whose payoff sequence satisfies Assumption C.8. Define the estimator b cτn =

K X Ta (n) a=1

n

b cτa,Ta (n) ,

and let δ⋆,n = cτ⋆ − cτ⋆,n . For any ϵ0 > 0, the following upper bound holds: E[ b cn − cτ⋆,n ] ≤ δ⋆,n +

K √ o R X n (1 + ϵ0 ) log n + O( n) . (N ),τ,+ n K (Fa , cτ⋆ ) ⋆ a̸=aτ

inf

Proof. We observe that |b cτn − cτ⋆ | ≤ b cτn − cτ⋆,n + cτ⋆ − cτ⋆,n = b cτn − cτ⋆,n + |δ⋆,n |

(22)

We have PK b cτn − cτ⋆,n =

cτa,Ta (n) − µτ∗,n ) a̸=aτ⋆ Ta (n)(b n

(23)

Therefore E[ b cτn − cτ⋆,n ] ≤ R

K X E[Ta (n)] a̸=a⋆ τ

33

n

(24)

According to Lemma C.7, we have E[ b cτn − cτ⋆,n ] ≤ R

K X E[Ta (n)]

n

a̸=a⋆ τ

K

R X ≤ n ⋆

(

(1 + ϵ0 ) log n (N ),τ,+

Kinf

a̸=aτ

(Fa , cτ⋆ )

√

)

+ O( n) ,

(25)

which concludes the proof. Lemma C.15. Let PATSO (Particle Thompson Sampling with Optimistic Bonus) be applied to a non-stationary bandit problem whose payoff process satisfies Assumption 5.2. Define the estimator b cτn =

K X Ta (n)

n

a=1

b cτa,Ta (n) ,

and let δ⋆,n = cτ⋆ − cτ⋆,n . For any p ≥ 1 and ϵ0 > 0, the following holds: K   τ √ R X  (1 + ϵ0 ) log n τ cn − c⋆ ≤ δ⋆,n + E b + O( n) . τ,+ τ n Kinf (Fa , c⋆ ) ⋆ a̸=aτ

Proof. Similar to Lemma C.14, we can derive cτn − cτ⋆,n ] ≤ |δ⋆,n | + R E[ b

K X E[Ta (n)]

n

a̸=a⋆ τ

.

(26)

and the bound is obtained as a direct corollary of Lemma C.12. Proof Of Theorem 5.4 for CATSO case Proof. We first prove that lim E[b cτn ] = cτ⋆ . According to the result of Lemma C.14, we have n→∞

K X

E[Ta (n)] n a=1,a̸=a⋆ τ ) ( K √ R X (1 + ϵ0 ) log n + O( n) ≤ |δ⋆,n | + (N ),τ,+ n K (Fa , cτ⋆ ) ⋆

E[|b cτn − cτ⋆ |] ≤ |δ⋆,n | + R

a=1,a̸=aτ

(27)

(28)

inf

with δ⋆,n = cτ⋆ − cτ⋆,n , and because lim cτ∗,n = cτ⋆ , we can conclude that n→∞

lim E[b cτn ] = cτ⋆ .

n→∞

Second, we prove that ∀n ≥ 1, ∀0 < ε ≤ n−1/2 (log n)−1/2 , ∃c > 0 that P (|b cτn − cτ⋆ | > ε) ≤ cn−1 ε−2 . We observe that |b cτn − cτ⋆ | ≤ b cτn − cτ⋆,n + cτ⋆ − cτ⋆,n = b cτn − cτ⋆,n + |δ⋆,n | =⇒P(|b cτn − cτ⋆ | ≥ ϵ) ≤ P( b cτn − cτ⋆,n

≥ ϵ/2) + P(|δ⋆,n | ≥ ϵ/2).

(29) (30)

Because lim |δ⋆,n | = 0, therefore, ∃N0 > 0 such that ∀n ≥ N0 , we have |δ⋆,n | < ϵ/2 that means n→n

∀n > N0 , P(|δ⋆,n | ≥ ϵ/2) = 0. Next, according to Lemma C.14, R E[ b cτn − cτ⋆,n ] ≤ n

K X

(

(1 + ϵ0 ) log n (N ),τ,+

a=1,a̸=a⋆ τ

Kinf

34

(Fa , cτ⋆ )

) √ + O( n) = O(n−1/2 ),

(31)

that leads to cτn − cτ⋆,n ≥ ϵ/2) ≤ P( b

E[ b cτn − cτ⋆,n ] O(n−1/2 ) = . ϵ/2 ϵ/2

(32)

Therefore, ∃c > 0, ∀0 < ϵ ≤ n−1/2 such that P( b cτn − cτ⋆,n

≥ ϵ/2) ≤ cn

−1/2

−2

(ϵ)(ϵ

) ≤ cn

−1/2

 n

−1/2



ϵ−2 = cn−1 ϵ−2 ,

(33)

which means ∀n ≥ N0 , ∀0 < ε < n−1/2 , ∃c > 0 that P (|b cτn − cτ⋆ | > ε) ≤ cn−1 ε−2 . With 0 < ϵ ≤ n−1/2 ⇒ ϵ−2 ≤ n−1 , so that n−1 ϵ−2 ≤ n−2 . With 1 ≤ n < N0 ⇒ n−1 ε−2 ≤ N0−2 . Therefore ∀C > N0−2 ⇒ P (|b cτn − cτ⋆ | > ε) ≤ 1 < Cn−1 ε−2 , which means ∀n ≥ 1, ∀0 < ε ≤ n−1/2 , ∃C > 0 that P (|b cτn − cτ⋆ | > ε) ≤ Cn−1 ε−2 . Next, we prove the following claim Claim.

P |b cτn − cτ⋆ | > ε ≤ C n−1 ε−2 , ∀ε > n−1/2 , for a universal constant C > 0 depending only on problem parameters (K, R, etc.).

By Lemma C.14 we have b cτn − cτ⋆ ≤ R

X Ta (n) a̸=aτ⋆

n

:= An .

P √ Let Sn = a̸=aτ⋆ Ta (n). Lemma C.7 implies that ∃c1 > 0 such that E[Sn ] ≤ c1 (K − 1) n. By Azuma–Hoeffding,  t2 
P Sn − E[Sn ] ≥ t ≤ exp − . 2n √ εn Choose t = 2R − c1 (K − 1) n (valid since ε > n−1/2 ), then  εn  = P Sn > ≤ exp(−c3 nε2 ) ≤ 12 n−1 ε−2 . 2R Therefore,

P |b cτn − cτ⋆ | > ε ≤ P(An > ε) ≤ C n−1 ε−2 , which completes the proof. Proof Of Theorem 5.4 for PATSO case Proof. The proof follows the same steps as Theorem 5.4 for CATSO case. We first prove that lim E[b cτn ] = cτ⋆ . According to the result of Lemma C.15, we have n→∞

K X

E[Ta (n)] n a=1,a̸=a⋆ τ ) ( K √ R X (1 + ϵ0 ) log n ≤ |δ⋆,n | + + o( n) + O(1) τ,+ n Kinf (Fa , cτ⋆ ) a=1,a̸=a⋆

E[|b cτn − cτ⋆ |] ≤ |δ⋆,n | + R

τ

with δ⋆,n = cτ⋆ − cτ⋆,n , and because

lim cτ∗,n = cτ⋆ , we can conclude that n→∞ lim E[b cτn ] = cτ⋆ .

n→∞

35

(34)

(35)

Second, we prove that ∀n ≥ 1, ∀0 < ε < n−1/2 , ∃c > 0 that P (|b cτn − cτ⋆ | > ε) ≤ cn−1 ε−2 . We observe that |b cτn − cτ⋆ | ≤ b cτn − cτ⋆,n + |δ⋆,n | cτn − cτ⋆,n + cτ⋆ − cτ⋆,n = b cτn − cτ⋆,n =⇒P(|b cτn − cτ⋆ | ≥ ϵ) ≤ P( b

≥ ϵ/2) + P(|δ⋆,n | ≥ ϵ/2).

(36) (37)

Because lim |δ⋆,n | = 0, therefore, ∃N0 > 0 such that ∀n ≥ N0 , we have |δ⋆,n | < ϵ/2 that means n→n

∀n > N0 , P(|δ⋆,n | ≥ ϵ/2) = 0. Next, according to Lemma C.15, R E[ b cτn − cτ⋆,n ] ≤ n

(

K X a=1,a̸=a⋆ τ

√ (1 + ϵ0 ) log n + o( n) + O(1) τ,+ Kinf (Fa , cτ⋆ )

) = O(n−1/2 ),

(38)

that leads to P( b cτn − cτ⋆,n ≥ ϵ/2) ≤

cτn − cτ⋆,n ] E[ b O(n−1/2 ) = . ϵ/2 ϵ/2

(39)

Therefore, ∃c > 0, ∀0 < ϵ < n−1/2 such that cτn − cτ⋆,n P( b

≥ ϵ/2) ≤ cn

−1/2

−2

(ϵ)(ϵ

) ≤ cn

−1/2

 n

−1/2



ϵ−2 = cn−1 ϵ−2 ,

(40)

which means ∀n ≥ N0 , ∀0 < ε < n−1/2 , ∃c > 0 that P (|b cτn − cτ⋆ | > ε) ≤ cn−1 ε−2 . With 0 < ϵ < n−1/2 ⇒ ϵ−2 > n−1 , so that n−1 ϵ−2 > n−2 . With 1 ≤ n < N0 ⇒ n−1 ε−2 > N0−2 . Therefore ∀C > N0−2 ⇒ P (|b cτn − cτ⋆ | > ε) ≤ 1 < Cn−1 ε−2 , which means ∀n ≥ 1, ∀0 < ε < n−1/2 , ∃C > 0 that P (|b cτn − cτ⋆ | > ε) ≤ Cn−1 ε−2 . Similarly to CATSO, we prove the following claim Claim.

P |b cτn − cτ⋆ | > ε ≤ C n−1 ε−2 , ∀ε > n−1/2 , for a universal constant C > 0 depending only on problem parameters (K, R, etc.).

Setup & decomposition.

By Lemma C.15 we have b cτn − cτ⋆ ≤ R

K X Ta (n) a̸=aτ⋆

n

:= An .

PK √ Let Sn = a̸=aτ⋆ Ta (n). Lemma C.12 implies ∃c1 > 0 such that E[Sn ] ≤ c1 (K − 1) n. By Azuma–Hoeffding,  t2 
. P Sn − E[Sn ] ≥ t ≤ exp − 2n √ εn Choose t = 2R − c1 (K − 1) n (valid since ε > n−1/2 ), then  εn  = P Sn > ≤ exp(−c3 nε2 ) ≤ 12 n−1 ε−2 . 2R Therefore,

P |b cτn − cτ⋆ | > ε ≤ P(An > ε) ≤ C n−1 ε−2 , which completes the proof. 36

D

MCTS Convergence Proofs

D.1 One-Step CVaR Lifting for Q-Edges Proof of Lemma 5.5 Proof. Let Rmax . 1−γ All plug-in and oracle backed-up samples lie in [0, Rh ]. Rh :=

Define the oracle empirical law n X b or (sh , a) := 1 D δG . n n i=1 i

The samples Gi = Xi + γV τ (Si ) are i.i.d. with law Dτ (sh , a). By the W1 -Lipschitz property of CVaR,   b τn (sh , a) − Qτ (sh , a) ≤ 1 W1 D bn (sh , a), Dτ (sh , a) . Q τ Using the triangle inequality,       bn , Dτ ≤ W1 D bn , D bnor + W1 D bnor , Dτ . W1 D We first control the oracle empirical-measure term. Since all laws are supported on [0, Rh ], W1 (P, Q) ≤ Rh ∥FP − FQ ∥∞ . Therefore, by the Dvoretzky–Kiefer–Wolfowitz inequality,     bnor , Dτ > τ ε P W1 D 2   τε > ≤ P FDb or − FDτ n 2Rh ∞   2 2 nτ ε ≤ 2 exp − . 2Rh2 Since 2e−x ≤ 2/(ex) for x > 0, this term is bounded by 4Rh2 1 . eτ 2 nε2 (n)

Next control the plug-in term. Couple each plug-in sample q̄i Gi . Then n   X (n) bn , D bnor ≤ 1 W1 D q̄ − Gi n i=1 i

with the corresponding oracle sample

n

=

γ X bτ V n (Si ) − V τ (Si ) n i=1 NSi

=γ

M X Nn

m

m=1

n

≤ γ max

1≤m≤M

(m) τ (m) VbNτ m n (s h+1 ) − V (sh+1 ) (m) τ (m) VbNτ m n (s h+1 ) − V (sh+1 ) .

If γ = 0, this term is identically zero. Assume below that γ > 0. Let

o n npm n for all m = 1, . . . , M . En := Nm ≥ 2 37

By a multiplicative Chernoff bound, P(Enc ) ≤

M X

 np   npm  min n ≤ M exp − . P Nm < 2 8 m=1

For 0 < ε ≤ Rh , this is bounded by

8M Rh2 1 . epmin nε2 For ε > Rh , the target probability is zero because both CVaR values lie in [0, Rh ]. On En , every child count satisfies

npm . 2 Thus, using the stopped-count concentration assumption and a union bound,     bn , D bnor > τ ε , En P W1 D 2   M X τε (m) τ (m) > ≤ P VbNτ m ) − V (s ) , E n (s n h+1 h+1 2γ m=1   M 2 X 2cm 2γ ≤ npm τ ε m=1 ! M 8γ 2 X cm 1 = 2 . 2 τ p nε m=1 m n Nm ≥

Combining the oracle empirical-measure term, the plug-in term, and the count event gives a constant cQ > 0 such that   b τn (sh , a) − Qτ (sh , a) > ε ≤ cQ P Q nε2 for every n ≥ 1 and every ε > 0. b τn (sh , a) and Qτ (sh , a) lie in [0, Rh ], It remains to prove convergence of expectations. Since both Q the displayed tail bound implies convergence in probability, and boundedness then implies convergence in L1 . Hence h i b τ (sh , a) − Qτ (sh , a) = 0. lim E Q n n→∞

Therefore, h i b τn (sh , a) = Qτ (sh , a). lim E Q

n→∞

Together with the concentration inequality, this is exactly b τn (sh , a) = Qτ (sh , a), plim Q n→∞

this concludes the proof. D.2

Convergence of CATSO in MCTS

Theorem D.1 (Finite-depth CVaR convergence of CATSO). Let CATSO run on a finite tree of depth H with bounded rewards and finite transition support at every Q-edge. Let

  b τ (sh , a) := CVaRτ D bn (sh , a) Q n

be the empirical CVaR Q-edge estimator after n local visits to edge (sh , a). Then, for every node sh and every action a ∈ A(sh ), b τn (sh , a) = Q e τ (sh , a), plim Q n→∞

and plim Vbnτ (sh ) = Ve τ (sh ).

n→∞

Proof. We prove the result by backward induction on the remaining depth d := H − h. 38

Base case.

At terminal depth H, the rollout or leaf estimator is assumed to satisfy plim Vbnτ (sh ) = Ve τ (sh ). n→∞

Thus the claim holds at depth H. Induction hypothesis.

Assume that for every child state sh+1 at depth h + 1, plim Vbnτ (sh+1 ) = Ve τ (sh+1 ).

n→∞

We prove the two claims for a node sh at depth h. I: Q-edge CVaR convergence. Fix an action a ∈ A(sh ). On the i-th local visit to edge (sh , a), write the sampled reward and next state as Xi ∼ R(sh , a, Si ),

Si ∼ P (· | sh , a).

The plug-in backed-up sample stored at the Q-edge is (n)

q̄i

= Xi + γ VbNτ Sn (Si ), i

where NSni is the number of times child state Si appears among the first n local visits to edge (sh , a). The corresponding oracle backed-up sample is Gi = Xi + γ Ve τ (Si ). Therefore the population Q-edge law is Dτ (sh , a) := L(Gi ), and the population CVaR Q-value is e τ (sh , a) = CVaRτ (Dτ (sh , a)) . Q By the induction hypothesis, every child estimator Vbnτ (sh+1 ) converges with concentration to Ve τ (sh+1 ). Therefore Lemma 5.5 applies and gives b τ (sh , a) = Q e τ (sh , a). plim Q n

n→∞

Since a was arbitrary, this proves Q-edge convergence for all actions at sh . II: V-node convergence from the local bandit theorem. At node sh , view each action a ∈ A(sh ) as an arm whose empirical CVaR estimator is b τn (sh , a), b cτa,n := Q and whose limiting CVaR value is e τ (sh , a). cτa := Q Step I verifies the armwise assumption plim b cτa,n = cτa

n→∞

for every action a. Hence Assumption 5.2 holds for the local bandit at node sh . By Theorem 5.4, the local CATSO V-backup X Ts ,a (n) h bτ Q (sh , a) Vbnτ (sh ) = Tsh (n) Tsh ,a (n) a∈A(sh )

satisfies

e τ (sh , a). plim Vbnτ (sh ) = max Q a∈A(sh )

n→∞

By definition of the target recursion, e τ (sh , a) = Ve τ (sh ). max Q

a∈A(sh )

Therefore

plim Vbnτ (sh ) = Ve τ (sh ).

n→∞

39

Conclusion. The induction step proves both Q-edge and V-node convergence at depth h whenever V-node convergence holds at depth h + 1. Since the terminal case holds, the result follows for every node in the finite-depth tree. Proof of Theorem 5.6 for CATSO case Proof. We prove the stronger statement that, for every depth h and every node sh at that depth, there exist constants Ch,V , Ch,Q < ∞ such that h i E Vbnτ (sh ) − Ve τ (sh ) ≤ Ch,V n−1/2 and, for every action a ∈ A(sh ), h i b τn (sh , a) − Q e τ (sh , a) ≤ Ch,Q n−1/2 . E Q The desired theorem follows by taking h = 0 and sh = s0 . We use backward induction on the remaining depth H − h. Base case.

At depth H, the claimed V-rate holds by the terminal assumption: h i E Vbnτ (sh ) − Ve τ (sh ) ≤ CH n−1/2 .

Thus the induction starts with CH,V := CH . Induction hypothesis.

Assume that, for all nodes sh+1 at depth h + 1, h i E Vbnτ (sh+1 ) − Ve τ (sh+1 ) ≤ Ch+1,V n−1/2 .

We prove the corresponding Q-rate and V-rate at depth h. I: Q-edge CVaR rate.

Fix a node sh and an action a ∈ A(sh ). Let (1)

(M )

{sh+1 , . . . , sh+1 } be the finite support of P (· | sh , a), and write (m)

pm := P (sh+1 | sh , a). On the i-th local visit to edge (sh , a), let Xi ∼ R(sh , a, Si ),

Si ∼ P (· | sh , a).

Define the plug-in backed-up sample (n)

q̄i

:= Xi + γ VbNτ Sn (Si ), i

where NSni is the number of appearances of child state Si among the first n local visits to edge (sh , a). Define also the oracle sample

Gi := Xi + γ Ve τ (Si ). Let

Then

n X bn (sh , a) := 1 D δ (n) , n i=1 q̄i

  b τn (sh , a) = CVaRτ D bn (sh , a) , Q

Dhτ (sh , a) := L(G1 ).

e τ (sh , a) = CVaRτ (Dhτ (sh , a)) . Q

By the 1/τ -Lipschitz property of CVaR in W1 ,   bn (sh , a), Dhτ (sh , a) . b τn (sh , a) − Q e τ (sh , a) ≤ 1 W1 D Q τ 40

Introduce the oracle empirical law n 1X or bh,n δG . D (sh , a) := n i=1 i

The triangle inequality gives       or bh,n , Dhτ ≤ W1 D bh,n , D bh,n bnor , Dτ . W1 D + W1 D For the first term, couple each plug-in sample with its oracle counterpart. Then n   X (n) bn , D bnor ≤ 1 W1 D q̄ − Gi n i=1 i n

=

γ X bτ V n (Si ) − Ve τ (Si ) n i=1 NSi

=γ

M X Nn

m

n

m=1

(m) e τ (m) VbNτ m n (s h+1 ) − V (sh+1 ) .

n , Taking expectations and using the induction hypothesis at the stopped count Nm h  i bn , D bnor E W1 D   n M X Nm n −1/2 ≤γ E Ch+1,V (Nm ∨ 1) n m=1 M

≤

γCh+1,V X hp n i E Nm n m=1 M

γCh+1,V X p n] E[Nm n m=1 ! M X √ = γCh+1,V pm n−1/2 .

≤

m=1

The inequality p p n] ≤ n] E[Nm E[ Nm uses Jensen’s inequality. For the second term, the oracle samples G1 , . . . , Gn are i.i.d. and bounded. Let Rh := Rmax

H−h−1 X

γ ℓ = Rmax

ℓ=0

1 − γ H−h . 1−γ

τ

Then D (sh , a) is supported on [0, Rh ]. By the one-dimensional empirical W1 bound, h  i b or , Dτ ≤ CFG Rh n−1/2 . E W1 D n Combining the two bounds yields h

b τ (sh , a) − Q e τ (sh , a) E Q n

i

" # M X 1 √ ≤ γCh+1,V pm + CFG Rh n−1/2 . τ m=1

Thus the Q-rate holds with  1 Ch,Q := γCh+1,V max sh ,a τ ′

X

s ∈supp(P (·|sh ,a))

41

 p P (s′ | sh , a) + CFG Rh  .

Fix a node sh . Write

II: V-node CVaR-average rate.

e τ (sh , a), qaτ := Q and let

q⋆τ := max qaτ = Ve τ (sh ), a∈A(sh )

a⋆τ (sh ) ∈ arg max qaτ a∈A(sh )

be the unique CVaR-optimal action. For readability, write Ta (n) := Tsh ,a (n),

wa (n) :=

Ta (n) . n

The algorithm uses the CVaR-average V-backup X bτ Vbnτ (sh ) = wa (n)Q h,Ta (n) (sh , a). a∈A(sh )

Subtracting q⋆τ and adding/subtracting qaτ gives Vbnτ (sh ) − q⋆τ =

X

  X τ bτ wa (n) Q wa (n) (qaτ − q⋆τ ) . h,Ta (n) (sh , a) − qa +

a

a

Taking absolute values and using that all CVaR values lie in [0, Rh ], X τ bτ Vbnτ (sh ) − q⋆τ ≤ wa (n) Q h,Ta (n) (sh , a) − qa + Rh a

X

wa (n).

a̸=a⋆ τ (sh )

For suboptimal actions, the Q-error is also bounded by Rh . Hence X

⋆ τ bτ Vbnτ (sh ) − q⋆τ ≤ Q h,Ta⋆ (n) (sh , aτ ) − q⋆ + 2Rh τ

wa (n).

a̸=a⋆ τ (sh )

Taking expectations gives i i h h bτ e τ (sh , a⋆τ ) + 2Rh (sh , a⋆τ ) − Q E Vbnτ (sh ) − Ve τ (sh ) ≤ E Q h,Ta⋆ (n) τ n

X

E[Ta (n)].

a̸=a⋆ τ (sh )

(41) We first bound the suboptimal-weight term. By the local CATSO suboptimal-arm pull bound, E[Ta (n)] ≤ La log n + Da n1/2 for constants La , Da < ∞. Therefore, 1 X n

E[Ta (n)] = O(n−1/2 ),

a̸=a⋆ τ (sh )

since log n/n = O(n−1/2 ). It remains to control the optimal-action Q-error at the random count Ta⋆τ (n). Let X Sn := Ta (n). a̸=a⋆ τ (sh )

Then Ta⋆τ (n) = n − Sn . By Markov’s inequality and the suboptimal-pull bound,  n  2E[Sn ] = O(n−1/2 ). ≤ P Sn > 2 n On the event {Sn ≤ n/2}, we have Ta⋆τ (n) ≥ 42

n . 2

Using the stopped-count form of the Q-rate from I, n oi h bτ e τ (sh , a⋆τ ) 1 Sn ≤ n (sh , a⋆τ ) − Q E Q Ta⋆ (n) τ 2  n −1/2 ≤ Ch,Q . 2 On the complement {Sn > n/2}, the absolute error is bounded by Rh . Thus i h e τ (sh , a⋆τ ) bτ (sh , a⋆τ ) − Q E Q (n) Ta⋆ τ  √ n ≤ 2 Ch,Q n−1/2 + Rh P Sn > 2 = O(n−1/2 ). Substituting this and the suboptimal-weight bound into (41) gives i h E Vbnτ (sh ) − Ve τ (sh ) ≤ Ch,V n−1/2 for some finite constant Ch,V . In sum. The induction proves the V-rate at depth h whenever it holds at depth h + 1. Since the terminal case holds, the claim holds for every node in the finite-depth tree. In particular, at the root s0 , h i E Vbnτ (s0 ) − Ve τ (s0 ) ≤ C ′ n−1/2 for a finite constant C ′ = C0,V . D.3 Convergence of PATSO in MCTS Similarly, we can derive the following Theorem Theorem D.2 (Finite-depth CVaR convergence of PATSO). Let PATSO run on a finite tree of depth H with bounded rewards and finite transition support at every Q-edge. Let

  b τn (sh , a) := CVaRτ D bn (sh , a) Q

be the empirical CVaR Q-edge estimator after n local visits to edge (sh , a). Then, for every node sh and every action a ∈ A(sh ), b τn (sh , a) = Q e τ (sh , a), plim Q n→∞

and plim Vbnτ (sh ) = Ve τ (sh ).

n→∞

Proof. The proof follows the same steps as Theorem D.1 by applying the results of Lemma 5.5 and Theorem 5.4. Proof of Theorem 5.6 for PATSO case Proof. We prove the stronger statement that, for every depth h and every node sh at that depth, there exists a constant Ch,V < ∞ such that h i E Vbnτ (sh ) − Ve τ (sh ) ≤ Ch,V n−1/2 . The desired result follows by taking h = 0 and sh = s0 . We proceed by backward induction on the remaining depth H − h. Base case.

At terminal depth H, the claim is exactly the assumed rollout/leaf rate: h i E Vbnτ (sH ) − Ve τ (sH ) ≤ CH n−1/2 .

Thus the induction starts with CH,V := CH . 43

Induction hypothesis.

Assume that for every child node sh+1 at depth h + 1, i h E Vbnτ (sh+1 ) − Ve τ (sh+1 ) ≤ Ch+1,V n−1/2 .

We prove the corresponding statement at an arbitrary node sh at depth h. I: Q-edge CVaR convergence.

Fix an action a ∈ A(sh ). Let (1)

(M )

{sh+1 , . . . , sh+1 } be the finite support of P (· | sh , a), and write (m)

pm := P (sh+1 | sh , a). On the i-th local visit to edge (sh , a), let Xi ∼ R(sh , a, Si ),

Si ∼ P (· | sh , a).

The backed-up sample stored by PATSO is q i = Xi + γ Vbℓτi (Si ), where ℓi is the local visit count of the child state Si at the moment this backup is formed. The corresponding oracle backed-up sample is Gi = Xi + γ Ve τ (Si ). Define the empirical PATSO Q-edge law after n local visits by n X bn (sh , a) := 1 δq , D n i=1 i

and define the oracle law by Dτ (sh , a) := L(G1 ). Since uncapped PATSO stores one particle per distinct observed backed-up return, its maintained bn (sh , a). particle law is exactly D The empirical and population Q-edge CVaR values are   b τ (sh , a) := CVaRτ D bn (sh , a) , Q n and e τ (sh , a) := CVaRτ (Dτ (sh , a)) . Q We show that the armwise condition needed by the local PATSO bandit theorem holds. Introduce the oracle empirical law n X bnor (sh , a) := 1 D δG . n i=1 i By the 1/τ -Lipschitz property of CVaR in W1 ,   b τn (sh , a) − Q e τ (sh , a) ≤ 1 W1 D bn (sh , a), Dτ (sh , a) . Q τ Using the triangle inequality,       bn , Dτ ≤ W1 D bn , D bnor + W1 D bnor , Dτ . W1 D For the first term, use the natural index-wise coupling n

1X πn := δ(q ,G ) . n i=1 i i 44

bn and D b or , so This coupling has marginals D n n   X bn , D b or ≤ 1 W1 D |q − Gi | n n i=1 i n

=

γ X bτ V (Si ) − Ve τ (Si ) . n i=1 ℓi (m)

n Group the sum according to the sampled child state. If child state sh+1 is observed Nm times among the first n visits to edge (sh , a), then its local child estimator appears with visit indices n r = 1, . . . , Nm . Hence n

Nm M X   X (m) (m) bn , D b or ≤ γ Vb τ (s ) − Ve τ (sh+1 ) . W1 D n n m=1 r=1 r h+1

Taking expectations and applying the induction hypothesis, h  i bn , D bnor E W1 D  n  Nm M γCh+1,V X X ≤ E r−1/2  n m=1 r=1 M

≤

2γCh+1,V X hp n i E Nm n m=1 M

2γCh+1,V X p n] E[Nm n m=1 ! M X √ pm n−1/2 . = 2γCh+1,V

≤

m=1

The second inequality uses N X

√ r−1/2 ≤ 2 N ,

r=1

and the third uses Jensen’s inequality. For the second term, the oracle samples Gi = Xi + γ Ve τ (Si ) are i.i.d. and bounded. Let Rh := Rmax

H−h−1 X

γ ℓ = Rmax

ℓ=0

1 − γ H−h . 1−γ

τ

Then D (sh , a) is supported on [0, Rh ]. By the one-dimensional empirical W1 bound, h  i b or , Dτ ≤ CFG Rh n−1/2 . E W1 D n Combining the two W1 bounds gives h

b τn (sh , a) − Q e τ (sh , a) E Q

i

" # M X 1 √ ≤ 2γCh+1,V pm + CFG Rh n−1/2 . τ m=1

e τ (sh , a) at rate Thus, for every action a, the empirical Q-edge CVaR estimator converges to Q −1/2 1 O(n ) in L . Since all quantities are bounded, the same argument also verifies the armwise convergence-with-concentration premise used by the local PATSO bandit theorem. 45

II: Apply the local PATSO CVaR bandit theorem at sh . At node sh , view every action a ∈ A(sh ) as a local bandit arm with limiting CVaR value e τ (sh , a). cτa := Q The local optimal CVaR value is cτ⋆ := max cτa = Ve τ (sh ). a∈A(sh )

The empirical arm score after m local pulls is b τ (sh , a). b cτa,m := Q m By I, the armwise empirical CVaR scores satisfy the required asymptotic stationarity/concentration condition for the local bandit at sh . The V-node backup used by the algorithm is exactly the CVaR-average local bandit backup: Vbnτ (sh ) =

X a∈A(sh )

Tsh ,a (n) b τ Q (sh , a). Tsh (n) Tsh ,a (n)

By the local PATSO CVaR bandit theorem with the O(n−1/2 ) L1 rate, i h E Vbnτ (sh ) − cτ⋆ ≤ Ch,B n−1/2 , for some constant Ch,B < ∞. Since cτ⋆ = Ve τ (sh ), we obtain i h E Vbnτ (sh ) − Ve τ (sh ) ≤ Ch,V n−1/2 , with Ch,V := Ch,B . Conclusion. The induction step shows that if all child V-estimators at depth h + 1 have the O(n−1/2 ) L1 rate, then the V-estimator at every parent node sh also has the O(n−1/2 ) L1 rate. Since the terminal case holds, the claim follows for every node in the finite-depth tree. In particular, at the root node s0 there exists a finite constant C ′ = C0,V such that h i E Vbnτ (s0 ) − Ve τ (s0 ) ≤ C ′ n−1/2 .

D.4 Risk-Sensitive Simple-Regret Bound The convergence theorems in Section 5 control the absolute root value error h i Eτ (n) := E Vbnτ (s0 ) − Ve τ (s0 ) . The risk-sensitive simple regret used in the main text is the signed root value gap h i SRτ (n) := E Ve τ (s0 ) − Vbnτ (s0 ) . Since x ≤ |x| for every real number x, we have h i SRτ (n) = E Ve τ (s0 ) − Vbnτ (s0 ) h i ≤ E Ve τ (s0 ) − Vbnτ (s0 ) = Eτ (n). Thus any upper bound on the absolute root value error immediately gives the same-order upper bound on SRτ (n). 46

Corollary D.3 (Risk-sensitive simple regret of CATSO). Under the assumptions of Theorem 5.6, fixed-grid CATSO satisfies SRτ (n) ≤ CCATSO n−1/2 . For the unprojected target with grid mesh ∆N , SRτ (n) ≤ CCATSO n−1/2 + O



∆N τ

 .

Proof. Theorem 5.6 gives Eτ (n) ≤ CCATSO n−1/2 for the fixed-grid target, and adds the discretization term O(∆N /τ ) for the unprojected target. Since SRτ (n) ≤ Eτ (n), the result follows. Corollary D.4 (Risk-sensitive simple regret of uncapped PATSO). Under the assumptions of Theorem 5.6, uncapped PATSO satisfies SRτ (n) ≤ CPATSO n−1/2 . Proof. Theorem 5.6 gives Eτ (n) ≤ CPATSO n−1/2 . The claim follows from SRτ (n) ≤ Eτ (n).

Corollary D.5 (Risk-sensitive simple regret of capped PATSO). Suppose capped PATSO satisfies the compression condition   uncap b cap (s, a), D bm W1 D (s, a) ≤ εK (s, a) m,K at every visited Q-edge. Then SRτ (n) ≤ CPATSO n−1/2 + O

ε  K

τ

,

where depth-dependent constants are absorbed into the O(·) term. Proof. By the 1/τ -Lipschitz property of CVaR in W1 , replacing the uncapped empirical Q-edge law by the capped law changes each empirical CVaR score by at most εK /τ . Propagating this additive bias through the finite depth tree gives the stated additional term. Combining with the uncapped PATSO bound and using SRτ (n) ≤ Eτ (n) proves the result.

E

Memory Capping and W1 Compression

E.1

Merge-on-Insert (Precise Algorithm)

We keep a sorted container of pairs {(Qi , αi )}M i=1 with M ≤ K. Upon receiving a new sample z: 1. Match: If mini |z − Qi | ≤ εtol , let i⋆ = arg mini |z − Qi | and set αi⋆ ← αi⋆ + 1. 2. Insert: Else if M < K, insert (z, 1) and keep the list sorted. 3. Merge: Else (overflow): find j with smallest gap |Qj+1 − Qj |, replace the pair by  
αj Qj + αj+1 Qj+1 new new Q ,α = , αj + αj+1 , αj + αj+1 then insert (z, 1) in sorted order. 47

(a) Autonomous vehicle

(b) Risky shortcut gridworld

(c) Guarded maze Rigter et al. [24]

Figure 4: Example risk-sensitive planning environments. Each contains a short risky route and a longer safer route; the risky route can have higher expected return but exposes the agent to catastrophic lower-tail outcomes. (2a) the map has black: highways, red: main roads, blue: streets, green: lanes (2b) S: start cell, G: goal cell, X: cliff cell, wind cell is indicated as the blue cell with an arrow points down. (2c) Red cell: guard cell, green cell: goal cell, gray cell: obstacle. E.2

Bound on W1 Error Under Capping

Define range := maxi Qi − mini Qi and let Pb be the (uncapped) empirical distribution and Pe the capped distribution after applying the procedure above. With nearest-neighbor merges:  range  X W1 (Pb, Pe) ≤ (αj + αj+1 ) · |Qj+1 − Qj | = O . K merges Since the Bellman operator
is 1/(1 − γ)-Lipschitz in W1 , the root-value error contributed by
capping is O range/(K(1 − γ)) and the simple-regret additive term is O range/(K(1 − γ)2 ) , which is dominated by the proven O(n−1/2 ) term for moderate K.

F

Experimental Details

All experiments were conducted on the I9 14900K processor, 6.00 GHz, with 24 cores and 32 threads in each core, 62 GB RAM. Whenever feasible, we opted for open-source implementations of algorithms and environments. The tuning process takes around 3 hours and the evaluation takes around 2 hours with the best configuration for each environment. F.1 Parameter Selection We conduct the hyperparameter-tuning experiments with 10 seeds for each environments. Specifically, we search over the number of atoms N in the grid {10, 11, . . . , 200}, polynomial bonus constant C in the set {1, 2, 4, 8} and the CVaR τ value in {0.05, 0.1, 0.2, 0.25} for CATSO and PATSO. For the baselines, we also tune to find the best config in terms of bias c, exploration bonus ϵ and the power p. F.2 Environments and Algorithms Hyperparameters For each environment, we run CATSO and PATSO with the baselines UCT, PowerUCT, MaxUCT with 50 seeds, each seed uses 104 to 105 simulations depending on the complexity of the environment and the tree depth is set to equal the environment horizon. At each simulation checkpoint, we compute the regret at the root node and perform 200 Monte Carlo evaluation rollouts at each simulation to compute the average of catastrophic count and CVaR return (worst τ -portion of the trajectories in term of return). Below are the detailed environment configurations. For the hyperparameter used in each environment, refer to table 2. One important note for CATSO is that, since it is difficult to determine a reasonable heuristic grid for the return distribution in the Q-Edge, we choose to build the distribution adaptively. Specifically, we initialize qmin = 0 and qmax = 0.01 and build the empirical distribution by discretizing the interval [qmin , qmax ] into N atoms, then the planner will adaptively expand the distribution as it receives more samples. Details of the adaptive distribution construction is in line 9 to 13 of the pseudo-code in figure 5. And for PATSO, as describe in appendix E, we use capped version of the particle distribution for memory capability in practical. 48

Table 2: Algorithm hyperparameters used for each environment. The value auto means that the code uses USE_AUTO_BIAS and computes the effective bias adaptively at runtime. Environment

Algorithm

Hyperparameters

Two-level Risky Treasure

UCT MaxUCT PowerUCT CATSO PATSO

bias=auto, epsilon=0.5 bias=auto, epsilon=0.5 bias=auto, epsilon=0.5, p=2.0 n_atoms=25, optimism=2.0, p=1.0, cvar_tau=0.25 max_particles=128, optimism=2.0, p=1.0, cvar_tau=0.25

Autonomous Vehicle

UCT MaxUCT PowerUCT CATSO PATSO

bias=10, epsilon=0.2 bias=10, epsilon=0.2 bias=10, epsilon=0.2, p=2.0 n_atoms=100, optimism=4.0, p=1.0, cvar_tau=0.05 max_particles=64, optimism=2.0, p=1.0, cvar_tau=0.05

Risky Shortcut Gridworld

UCT MaxUCT PowerUCT CATSO PATSO

bias=auto, epsilon=0.1 bias=auto, epsilon=0.1 bias=auto, epsilon=0.1, p=2.0 n_atoms=100, optimism=2.0, p=1.0, cvar_tau=0.05 max_particles=100, optimism=2.0, p=1.0, cvar_tau=0.05

Betting Game

UCT MaxUCT PowerUCT CATSO PATSO

bias=2, epsilon=0.05 bias=2, epsilon=0.05 bias=2, epsilon=0.05, p=2.0 n_atoms=50, optimism=8.0, p=1.0, cvar_tau=0.25 max_particles=32, optimism=1.0, p=1.0, cvar_tau=0.25

Guarded Maze

UCT MaxUCT PowerUCT CATSO PATSO

bias=auto, epsilon=0.1 bias=auto, epsilon=0.1 bias=auto, epsilon=0.1, p=2.0 n_atoms=100, optimism=1.0, p=1.0, cvar_tau=0.25 max_particles=128, optimism=4.0, p=1.0, cvar_tau=0.25

Autonomous Vehicle [24] • Task: A route-planning problem where the agent must navigate through a road network to reach a destination. See figure 4a for the map. • Goal: Reach the goal while avoiding routes with rare but severe travel-cost outcomes. • Action Space: Move {Up, Down, Left, Right}. • State Space: Discrete (x, y) position of the agent. • Reward: Traversing the road pays a stochastic cost, based on the road types. Details are provided table 3. • Transition Dynamics: The transition across the road is deterministic, while the cost type is sampled with probability {0.4, 0.2, 0.4}. The horizon is 7. • Catastrophic Feature: Traversing a high-risk road and receiving the largest cost outcome. Two-level Risky Treasure • Task: A small sequential decision problem in which the agent chooses between a safe option and a risky treasure branch, and later decides whether to continue or abort after observing a hint. • Goal: Maximize return by balancing the high upside of the treasure against the risk of failure. • Action Space: At the root, the actions are {safe, risky}; after entering the risky branch, the actions are {abort, proceed}. • State Space: Current decision stage, observed hint, and terminal status. • Reward: The safe branch yields a reward of 2, while the risky branch yields either a high positive reward or a negative failure penalty, namely 500 or -10, respectively. The abort reward is -1. • Transition Dynamics: Choosing the risky branch reveals a noisy hint about the hidden treasure state. The agent then chooses whether to abort safely or proceed to a stochastic success/failure outcome with success probability of 0.40. The horizon is 2. • Catastrophic Feature: Treasure failure after choosing to proceed, i.e., receiving the -10 reward.

49

Table 3: Cost distribution used in the Autonomous Vehicle environment. Road Type Small Cost Medium Cost Large Cost Lane Street Main Road Highway

4 2 3 1

4 3 4 2

4 5 7 10

Risky Shortcut Gridworld • Task: A cliff-style gridworld where the agent may choose between a short but dangerous shortcut and a longer safer path. See figure 4b for the map. • Goal: Reach the goal while avoiding the cliff. • Action Space: Four movement actions: {Up, Right, Down, Left}. • State Space: Grid position of the agent together with the current time step. • Reward: An ordinary step gives reward -1, reaching the goal gives reward 5, and falling into the cliff gives reward -20. • Transition Dynamics: The movement is deterministic, except when the agent is in a windy cell, there is a 2% chance of being dragged down the hill. The horizon is 32. • Catastrophic Feature: Entering a cliff cell. Betting Game • Task: A finite-horizon gambling problem where the agent repeatedly chooses how much of its current bankroll to bet. • Goal: Maximize return while avoiding ruin. • Action Space: Nine discrete betting actions, where action a ∈ {0, . . . , 8} corresponds to betting a fraction a/8 of the current bankroll. • State Space: Current bankroll and current time step, i.e. (b, t). • Reward: Each action yields a stochastic gain or loss determined by the chosen bet fraction and the outcome of the bet. • Transition Dynamics: After each action, the bankroll is updated according to the stochastic bet outcome. The episode terminates when the bankroll reaches zero, reaches the maximum bankroll, or the horizon is exhausted. The horizon is 6. • Catastrophic Feature: Bankruptcy, i.e. the bankroll reaches zero. Guarded Maze • Task: A grid-navigation problem where the agent must move from a start cell to a goal cell while deciding whether to pass through a risky guarded region. • Goal: Reach the goal with high return while avoiding dangerous guard outcomes. • Action Space: Four movement actions: {Up, Down, Left, Right}. • State Space: Agent position on the grid together with the current time step. • Reward: Each step pays -1 reward, when in the guard cell, the reward is sampled in the set {−60, −30, 0, 30, 60} in normal distribution. • Transition Dynamics: Movement is constrained by the maze layout and walls. Entering the guarded region triggers a stochastic outcome, which may produce a large negative reward as described above. The horizon is 20. • Catastrophic Feature: A severe negative guard outcome. F.3

Full Results

For completeness, we show the full the detail experimental results of the experiment, which are already depicted in section 6. Recall that the standard deviation of Two-Level Risky Treasure is zero because the algorithms converge in earlier simulation checkpoint due to its short in horizon and simple transition dynamics. 50

Table 4: Performance across all environments and algorithms at final simulation budget. Best values per environment and metric are shown in bold. Environment

Algorithm

CVaR Regret

CVaR Return

Catastrophic Count

Two-Level Risky Treasure

UCT MaxUCT PowerUCT CATSO PATSO

12.000 12.000 12.000 0.020 0.000

−10.000 ± 0.000 −10.000 ± 0.000 −10.000 ± 0.000 2.000 ± 0.000 2.000 ± 0.000

119.84 120.24 120.26 0.00 0.00

Autonomous Vehicle

UCT MaxUCT PowerUCT CATSO PATSO

7.574 7.564 7.566 1.428 5.059

−31.702 ± 1.229 −31.644 ± 1.278 −31.744 ± 1.208 −31.368 ± 1.419 −28.240 ± 0.323

2.78 3.36 3.28 3.36 0.00

Risky Shortcut Gridworld

UCT MaxUCT PowerUCT CATSO PATSO

20.000 20.000 20.000 0.528 2.748

−14.550 ± 7.484 −13.950 ± 7.698 −13.300 ± 8.103 0.000 ± 0.000 0.000 ± 0.000

8.08 7.92 7.70 0.00 0.00

Betting Game

UCT MaxUCT PowerUCT CATSO PATSO

0.062 0.062 0.062 0.024 0.008

−15.996 ± 0.008 −15.984 ± 0.027 −16.000 ± 0.000 −5.613 ± 5.630 −13.714 ± 2.407

21.12 23.06 22.70 2.02 8.46

Guarded Maze

UCT MaxUCT PowerUCT CATSO PATSO

0.126 0.126 0.125 0.012 0.033

−0.132 ± 0.049 −0.136 ± 0.051 −0.135 ± 0.050 −0.042 ± 0.001 −0.039 ± 0.000

61.70 60.04 61.74 1.32 0.00

F.4

Sensitivity of CATSO/PATSO Grid Representation

We study the sensitivity of CATSO and PATSO to the size of their distributional representations. Specifically, we vary the number of categorical atoms N for CATSO and the maximum number of particles U for PATSO. We evaluate the resulting computational cost, memory usage, and planning performance. For comparison, UCT is shown as a scalar baseline. All experiments use the adaptivegrid implementation of CATSO and the capped version of PATSO used in our practical experiments. Figure 6 shows peak memory and search time as a function of representation size. As expected, increasing N for CATSO leads to a higher computational and memory cost, since each Q-edge maintains more categorical atoms and the CVaR computation must process a larger support. Similarly, increasing the particle cap U increases the computational cost of PATSO. The effect is particularly pronounced for uncapped PATSO, whose support can grow with the number of distinct backed-up returns. In contrast, capped PATSO provides a bounded representation size and therefore offers a direct trade-off between computational cost and distributional fidelity. Figure 7 reports the resulting planning performance. Overall, the performance of CATSO is relatively stable across the tested values of N , although very small grids can provide insufficient resolution for the underlying return distribution. PATSO exhibits a similar trend with respect to U : increasing the particle cap provides additional capacity to represent the empirical distribution, but the performance gains become smaller once a sufficiently large support is available. These results suggest that moderate representation sizes can retain most of the risk-sensitive planning benefit without incurring the full computational cost of a large representation. Finally, we measures the compression error of capped PATSO relative to uncapped PATSO. Figure 8 shows the compression error decreases as the particle cap U increases, showing that a larger cap allows the capped representation to more closely match the empirical distribution maintained by uncapped PATSO. This agrees with the theoretical characterization in Remark 5.8, where the compression error contributes an additional approximation term to the CVaR estimate. 51

Algorithm 3: CATSO Adaptive SimulateQ 1 SimulateQ(sh , a, t): 2 sh+1 ∼ P(·|sh , a), rt (sh , a) ∼ R(sh , a, sh+1 ) 3 if node sh+1 not expanded then 4 Rollout(sh+1 ) 5 else 6 SimulateV(sh+1 , t) 7 Tsh ,a (t) = Tsh ,a (t) + 1 8 Qt (sh , a) = rt (sh , a) + γ VbTτs (t) (sh+1 ) h+1

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

/ [Qmin (sh , a), Qmax (sh , a)] then if Qt (sh , a) ∈ ziold (sh , a) ← zi (sh , a), 0 ≤ i ≤ N αiold (sh , a) ← αi (sh , a), 0 ≤ i ≤ N Qmax (sh , a) = max{Qt (sh , a), Qmax (sh , a)} Qmin (sh , a) = min{Qt (sh , a), Qmin (sh , a)} △z = (Qmax (sh , a) − Qmin (sh , a))/N zi (sh , a) = Qmin (sh , a) + i△z, 0 ≤ i ≤ N α ei (sh , a) ← 1, 0 ≤ i ≤ N for j = 0, . . . , N do i⋆ ← arg mini |zjold (sh , a) − zi (sh , a)| α ei⋆ (sh , a) ← α ei⋆ (sh , a) + αjold (sh , a) − 1 αi (sh , a) ← α ei (sh , a), 0 ≤ i ≤ N i ← arg mini |Qt (sh , a) − zi (sh , a)| αi (sh , a) ← αi (sh , a) + 1 Update p(sh , a) = [p0 (sh , a), . . . , pN (sh , a)] Figure 5: Pseudocode for the adaptive distribution construction in SimulateQ of CATSO.

Figure 6: Peak memory and search time of CATSO, PATSO, and UCT as a function of the representation size N and U .

Overall, the sensitivity results demonstrate the practical trade-off between representation capacity and computational efficiency. CATSO trades a larger categorical grid for finer distributional resolution, while PATSO trades a larger particle cap for lower compression error. In practice, moderate values of N and U provide a reasonable balance between planning performance, memory usage, and search time.

G

Limitations

CATSO and PATSO make MCTS risk-sensitive by storing empirical backup laws at Q-edges while keeping V-nodes scalar. This design is lightweight, but it also has several limitations. 52

Figure 7: Planning performance of CATSO, PATSO, and UCT as a function of the representation size N and U .

Figure 8: Compression quality of capped PATSO relative to uncapped PATSO as a function of the particle cap U . CATSO discretization bias. CATSO represents each Q-edge law on a fixed categorical grid. This gives bounded memory and simple Dirichlet updates, but it introduces a grid approximation error. If the grid is too coarse, sharp tail behavior or multimodal return distributions may be poorly represented. Adaptive grids can improve empirical performance, but changing the grid requires reprojection. PATSO memory growth and compression bias. Uncapped PATSO represents the empirical Q-edge law exactly, but its support can grow linearly with the number of distinct backed-up returns. Capped PATSO controls memory by merging particles, but this introduces a separate W1 compression error. Since CVaR is sensitive to tail mass, careless merging can distort the lower tail; the cap must therefore be chosen large enough that the compression bias is below the statistical error. Scalability beyond tabular finite-depth search. The present analysis is for tabular finite-depth MCTS. Extending the approach to large or continuous state spaces, learned dynamics, partial observability, or neural value approximators requires additional approximation analysis. In particular, model error and function-approximation error would interact with the Q-edge distributional estimates and the CVaR backup.

NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: All the claims made in the abstract and introduction are shown properly in sections 5 and 6. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. 53

• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The limitations are discussed in appendix G. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: All assumptions are stated in section 3, 5 and appendix B. While the complete proofs are in section 5, appendix C, D and E. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility

54

Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Section 6 and Appendix F provide all the information about the experiment procedures, environments, algorithms and their configuration in the experiment. Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: An anonymized .zip file containing the code, dependency specifications, and instructions necessary to faithfully reproduce the main experimental results is included in the supplementary material, in accordance with the NeurIPS Code and Data Submission Guidelines. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

55

• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //neurips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: Appendix F clearly defines the environment setups, algorithm hyperparameters for both the main process and tuning process. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: The results are averaged over 50 seeds × 200 independent Monte Carlo runs, with standard deviation plotted in Figure 2 and Table 4 and empirical safety verified as detailed in Section 6 and Appendix F. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources

56

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Appendix F explicitly details the compute resources (CPU Intel Core i9 14900K, 62 GB RAM) and the execution times for both the tuning experiment (2 to 4 hours per environment) and the main experiments (1 to 3 hours per environment). Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The research focuses on foundational theoretical and algorithmic machine learning methodology (Sections 5), which fully conforms to the NeurIPS Code of Ethics. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [N/A] Justification: This is foundational theoretical research on risk-sensitive planning (Sections 4 and 5) evaluated on synthetic distributions (Section 6) presenting no immediate foreseeable negative societal impacts or direct paths to malicious applications. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mecha57

nisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The paper does not introduce or release high-risk models, language models, or scraped datasets (all data are simulated as per Appendix F). Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: All the environments represented in the paper, if adapted from existing works, are cited properly in Section 6. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: All new environments and algorithms are documented in detail in supplementary and appendix F. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

58

• The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: The paper studies risk awareness in MCTS planning algorithm and does not involve human subjects. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: The research utilizes synthetic environments (Appendix F) and does not involve human subjects. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [N/A] Justification: LLMs are not used as a component of the core theoretical methodology or algorithm design (sections 4 and 5) Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

59

Related documents

• Gradient-Free Sampling from Generative Models via Stochastic Bounded Extremum Seeking#1200219
• Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion#436425
• The Epistemic Challenge to Longtermism#100801
• Profile-Aware Trustworthy Recipe Generation with Planner-Critic Agentic Remediation#1187647
• Access to Live AI Advice and Behavior Under Risk: An Incentivized Experiment#984285