Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

1 Introduction

• Quantile learning is challenging because small transition-estimation errors can shift probability mass across the target and substantially change policy value, while expected reward may miss downside reliability needs.Source: §1 · pp. 2–3
• UCB-BQRL combines transition confidence sets with a lower-buffered quantile objective that averages quantiles below the target to stabilize model-based planning.The buffered criterion remains connected to the exact quantile objective used to define regret.Source: §1 · p. 3
• UCB-BQRL’s high-probability regret bound yields sublinear exact-quantile regret with a logarithmically decreasing buffer schedule, up to a finite instance-dependent transient.The bound comprises cumulative buffering and statistical-learning terms.Source: §1 · pp. 3–4
• For some finite-horizon MDPs, every learning algorithm incurs expected exact-quantile regret of at least Ω(H/ρ_τ√(AT)), making dependence on 1/ρ_τ unavoidable.Source: §1 · p. 4
• Exact point-quantile and lower-buffered quantile evaluation are PP-hard under polynomial-time Turing reductions, even for a fixed policy in a two-state, one-action finite-horizon MDP.The result distinguishes the statistical role of an exact-planning oracle from its general computational tractability.Source: §1 · p. 4
• EVI-BQ provides an exact dynamic-programming procedure for solving the buffered quantile planning problem used by the algorithm.Source: §1 · p. 4

2.1 Risk-Sensitive MDPs

• Quantile MDP work develops known-kernel dynamic programming for fixed quantile levels, while Alipour-Vaezi et al. (2026) study quantile RL with unknown kernels.The paper distinguishes its fixed-quantile optimization objective from constraint-based risk methods and notes that quantile backups are non-smooth and set-valued.Source: §2.1 · pp. 5–6

2.2 Optimism and Upper Confidence Bounds (UCB)

• Optimistic confidence-set planning underlies regret guarantees for expectation-maximizing RL, but quantile objectives can change discontinuously and defeat standard value-difference analyses.The related work notes that extending optimism to MDPs with tail-sensitive criteria requires new contraction and sensitivity arguments.Source: §2.2 · pp. 6–7

2.3 Function Approximation and Model-Based Deep RL

• Most model-based deep RL methods optimize expected return and use heuristic or approximate uncertainty, while regret analysis for tail-sensitive objectives with function approximation remains less developed.Learned models may also be inaccurate outside the observed data distribution.Source: §2.3 · p. 7

• The model is a finite-horizon MDP with finite state and action spaces and deterministic rewards in [0, 1].Source: §3 · p. 8
• Policies are deterministic and history-dependent, with histories defined by the state and action sequence through each stage.Source: §3 · p. 8
• Ordinary point-quantile QMDP can use scalar state–quantile policies, but exact lower-buffered frontier algorithms do not use that representation.Source: §3 · p. 8
• The target-τ lower-buffered objective averages ordinary quantiles just below τ, smoothing discontinuous backups and yielding global Wasserstein-Lipschitz stability.Source: §3 · pp. 8–9
• For finite-support root returns, the uniform left-plateau threshold determines the buffer width for buffered and exact values to coincide and appears in both regret bounds.Source: §3 · p. 9

4.1 UCB–BQRL Algorithm

• UCB–BQRL maintains transition confidence sets and optimistically replans with a lower-buffered quantile objective.The buffer parameter is chosen in (0, τ].Source: §4.1 · p. 10
• Its “estimate → buffer → plan” structure replaces the unstable point quantile with a globally Lipschitz buffered objective.Source: §4.1 · pp. 10–11
• EVI–BQ plans over achievable return-law frontiers rather than storing a single scalar value at each state and stage.Its backward recursion constructs return laws together with labels encoding deterministic continuation policies.Source: §4.1 · pp. 12–13
• Proposition 1 establishes that EVI–BQ exactly implements the optimistic buffered re-planning step required by UCB–BQRL.The claim assumes a nonempty confidence set and existence of the maximizers in Algorithm 2.Source: §4.1 · p. 15

4.2.1 High-probability Regret Upper Bound

• A logarithmic buffer schedule yields sublinear regret, and its buffering cost vanishes once the buffer falls below the root-level plateau threshold ρ_τ.The general upper-bound analysis allows non-increasing buffer sequences; the remaining regret terms arise from statistical transition-estimation error.Source: §4.2.1 · pp. 16–17

4.2.2 Information-Theoretic Lower Bound for Quantile Regret

• An information-theoretic lower bound for exact-quantile regret holds even for a two-state MDP with deterministic rewards, independently of the learner’s buffer sequence or planning procedure.The theorem assumes A ≥ 2 and H ≥ 2; its hard instances can switch the τ-quantile between 0 and H−1.Source: §4.2.2 · pp. 17–18

4.2.3 Computational hardness of exact quantile evaluation

• Exact quantile and exact lower-buffered quantile evaluation are PP-hard under polynomial-time Turing reductions, even for a fixed policy in a two-state, one-action finite-horizon MDP.The hardness also holds with binary transition probabilities and deterministic rational rewards in [0, 1].Source: §4.2.3 · pp. 18–19

5 Numerical Experiment

• Because exact EVI–BQ can require rapidly growing return-law frontiers, the numerical study instead uses a computational approximation with candidate-model, frontier-capping, and pruning rules.It therefore does not execute the exact oracle analyzed in the theoretical results.Source: §5 · p. 20

5.1 Model Formulation

• The H = 10 asset-selling MDP has 25 offer states and an absorbing post-sale state; stopping yields s/24, while continuing gives zero reward and a new offer.The learner knows the reward function and transition structure but estimates continuation probabilities from observed trajectories; Stop weakly dominates Continue in the final period.Source: §5.1 · p. 20

5.2 Implementation and Experimental Design

• Before each episode, the implementation updates empirical transitions, constructs row-wise ℓ1 confidence radii with a tunable multiplier, and replans using β_t = τ/log(e + t).The practical implementation preserves UCB–BQRL’s confidence-set and buffered-planning principles.Source: §5.2 · p. 21
• The practical planner evaluates six representative kernels and retains one return law per stage–state, producing deterministic stage-dependent Markov policies rather than EVI–BQ’s history-dependent policies.For each action it selects the largest lower-buffered τ-quantile, using mean return to break ties.Source: §5.2 · pp. 21–22
• The experiment compares UCB–BQRL with six established reinforcement-learning benchmarks: the model-based optimistic algorithm UCBVI, ε-greedy Q-learning, on-policy SARSA, Thompson sampling, TRPO, and PPO.Source: §5.2 · p. 23

5.3 Learning Results

• At episode 2000, expected-return regret was 15.73 for UCBVI, 229.00 for UCB–BQRL, and 586.19 for SARSA.UCBVI had the lowest mean regret, while UCB–BQRL was second-best despite training on a lower-tail quantile.Source: Figure 1 · p. 26, §5.3 · p. 26

5.2 Implementation and Experimental Design

• The numerical policy gaps use a common approximate-frontier reference, not exact quantile regret; variability bands from three held-out seeds are descriptive, not inferential.The reference computation is restricted for tractability, so it is numerical rather than unrestricted optimal quantile evaluation.Source: §5.2 · p. 25, §5.3 · pp. 26–28

5.3 Learning Results

• At τ=0.5, UCB–BQRL's episode-2000 cumulative numerical policy gap was 1.15, versus 9.13 for UCBVI and 114.43 for ε-greedy Q-learning.UCB–BQRL maintained the smallest cumulative gap through most of training.Source: Figure 2 · p. 27, §5.3 · p. 27
• At τ=0.9, UCB–BQRL's episode-2000 cumulative numerical policy gap was 0.79, versus 2.79 for UCBVI and 56.38 for the next-smallest baseline.UCB–BQRL again had the smallest cumulative gap, consistent with its planning objective's dependence on the target quantile.Source: §5.3 · p. 27, Figure 3 · p. 28

5.4 Policy and Risk Interpretation

• At the first decision period, the displayed policy continued for offers ≤13 at τ=0.1, ≤21 at τ=0.5, and ≤23 at τ=0.9, so continuation expanded with τ.At τ=0.1 it accepted initial offers of at least 14; at τ=0.9 it accepted only the maximum offer, 24.Source: §5.4 · p. 29
• For all three target quantiles, the stopping region expanded near the horizon, and every displayed policy stopped for every offer in the final decision period.The passage attributes this pattern to having fewer remaining opportunities for a better offer after choosing Continue.Source: §5.4 · p. 29
• Figure 4 shows that the learned stopping rule depends jointly on the target quantile, current offer, and remaining decision periods.The subsection presents these as joint determinants of UCB–BQRL's stopping rule.Source: §5.4 · p. 29
• Changing the target quantile alters the value assigned to a policy.Source: §5.4 · p. 29
• Changing the target quantile also alters the state-wise decisions produced by UCB–BQRL.Source: §5.4 · p. 29

6.1 Toolkit Novelty

• Lower buffering averages quantiles below the target to smooth discontinuous quantile changes, and the regret bound separates transition-learning error from buffering approximation error.This addresses both transition uncertainty and local quantile instability; as the buffer shrinks, the buffered criterion connects to the original objective.Source: §6.1 · pp. 30–31

6.2 Computational Aspects

• EVI–BQ tracks finite remaining-return laws and policy-tree labels to plan exactly, but its rapidly growing representation and confidence-set optimization make it a theoretical oracle, not a scalable generic algorithm.Practical approximations such as sampling, discretization, or pruning introduce planning error, which must be controlled for sublinear regret.Source: §6.2 · p. 31

6.3 Comparison with Prior Work

• Confidence sets address transition uncertainty while lower buffering stabilizes planning; the lower bound reflects an intrinsic challenge, as small probability changes can flip exact quantile values.The buffer balances approximation to the exact target quantile against sensitivity to transition-estimation error.Source: §6.3 · p. 31

6.4 Role of the Root-Level Plateau Parameter

• The root-level plateau width determines when buffering recovers the exact initial-state quantile and acts as a margin-like parameter governing quantile fragility and learning difficulty.Below the plateau width, buffered and exact values coincide, so the buffering error vanishes after a finite transient under a decreasing buffer schedule.Source: §6.4 · p. 32

6.5 Computational Hardness and Future Research

• Exact point-quantile and lower-buffered quantile evaluation are PP-hard even for a fixed policy in a restricted finite-horizon MDP, motivating approximate planners with explicit planning-error guarantees.Suggested directions include confidence-set discretization, candidate-model sampling, pruning, distributional value approximations, and deep RL methods.Source: §6.5 · p. 32

Proof of Theorem 1

• With probability at least 1−δ, the true kernel P★ and planned kernel P_t both belong to C_t.Source: Proof of Theorem 1 · p. 40
• Lemma 3 supplies a probability-at-least-1−δ event stated to hold for every episode t=0,…,T−1.Source: Proof of Theorem 1 · p. 40
• The proof conditions on observations before episode t together with the planned model P_t, under which the counts are fixed.Source: Proof of Theorem 1 · p. 40
• For stage rewards in [0,1] and β_t≤τ, Definition 1 gives ℓ_β_t(τ)=β_t before Lemma 4 is applied.Source: Proof of Theorem 1 · p. 40
• An inequality remains valid even if its left-hand side is negative, because it follows from an upper bound on the absolute value.Source: Proof of Theorem 1 · p. 41
• The proof identifies its t=0 term as a martingale-difference sequence with respect to the episode filtration.Source: Proof of Theorem 1 · p. 41
• The confidence-containment and Lemma 3 events hold simultaneously with probability at least 1−2δ by a union bound.On their intersection, the proof proceeds with both events in force.Source: Proof of Theorem 1 · pp. 40–41

Proof of Theorem 2

• An unknown distinguished action controls the only informative transition, from the initial state to a high-reward absorbing state; identifying the optimal quantile policy is equivalent to finding the best Bernoulli arm.After the first action, transitions are deterministic, so the episode’s informative randomness comes from that initial transition.Source: Proof of Theorem 2 · pp. 41–42
• At target level τ, the distinguished action has quantile H−1 while every suboptimal action has quantile 0, giving an exact per-episode gap of H−1.The distinguished and suboptimal return laws place probability τ−ρ and τ+ρ, respectively, on return 0.Source: Proof of Theorem 2 · p. 43
• The constructed instance has root-level left-plateau threshold ρτ = ρ.For the distinguished action, the CDF left limit at its τ-quantile is τ−ρ; suboptimal actions have threshold τ, so the minimum is ρ.Source: Proof of Theorem 2 · p. 43
• The learning interaction is an A-armed Bernoulli bandit with the distinguished action as the higher-mean arm, and the proof transfers bandit suboptimal selections into quantile regret.The final reduction expresses expected quantile regret as (H−1) times an expected quantity of suboptimal selections.Source: Proof of Theorem 2 · p. 44

Proof of Theorem 3

• Exact QMDP evaluation is PP-hard via reduction from the threshold version of counting 0/1-knapsack solutions to the Kth-largest-subset problem, PP-complete under polynomial-time Turing reductions (Haase and Kiefer, 2016, Theorem 3).Source: Proof of Theorem 3 · pp. 44–45
• The reduction constructs a horizon n+1 MDP with two states, one action, and transitions to state 1 with probability 1/2, yielding a return formed from independent Bernoulli indicators and item rewards.With only one action, the MDP has a unique deterministic policy, so evaluation and planning coincide.Source: Proof of Theorem 3 · pp. 44–45
• The point-quantile threshold test distinguishes instances with at least M qualifying subsets from those with fewer, thereby deciding the counting-knapsack problem.When the count is at least M, the return CDF at c reaches at least M/2^n, which exceeds τ; the converse case reverses the threshold test.Source: Proof of Theorem 3 · p. 45
• With β = 2^−(n+1) and τ−β = M−1, when the knapsack count is below M, every u in (τ−β, τ] has Q_u(R)>c in this threshold-counting comparison.Source: Proof of Theorem 3 · p. 45
• Because the constructed MDP has only one action and thus one policy, exact point-quantile and lower-buffered quantile planning are also PP-hard.The planning problems contain evaluation as a special case.Source: Proof of Theorem 3 · p. 45

Proof of Proposition 1

• Backward induction establishes that each state-stage frontier contains exactly the finite return laws achievable by deterministic continuation policies, with labels identifying the generating policies.At the terminal stage, the only achievable law is the point mass at zero.Source: Proof of Proposition 1 · p. 46
• At each earlier stage, a deterministic policy chooses an action and then follows the continuation policy associated with the observed next state.The induction hypothesis supplies the continuation return laws, and stored labels encode the corresponding policy choices.Source: Proof of Proposition 1 · p. 46
• At the root, the algorithm maximizes the stated Q objective over exactly the return laws achievable by deterministic policies under the fixed model P.Source: Proof of Proposition 1 · p. 46

Proof of Corollary 1

• The proof uses the logarithmic schedule β_{T−1}=τ log(e+T−1).The passage also states a consequent expression involving 1/β_{T−1}, but its formatting is ambiguous.Source: Proof of Corollary 1 · p. 46
• The cumulative β-increment term is bounded by 2HKτ, and substituting the two bounds into Theorem 1 completes the proof.Source: Proof of Corollary 1 · p. 46

• With high probability, the true transition kernel and each returned optimistic model belong to the episode confidence sets.The confidence-set containment guarantee follows across episodes, stages, and state–action pairs by a union bound.Source: Technical Lemmas · p. 47
• Weissman’s lemma provides an ℓ1 concentration bound for the empirical distribution of i.i.d. categorical samples.The proof combines Hoeffding’s inequality with a union bound.Source: Technical Lemmas · pp. 47–48
• The buffered optimistic decomposition bounds the gap between the optimal true-model value and the value of the returned policy using buffering gaps.The true model and its optimal policy are feasible for the buffered optimistic planning problem when the true kernel lies in the confidence set.Source: Technical Lemmas · p. 48
• For return laws supported on [0, H], buffered-quantile sensitivity is bounded through the quantile-function differences over the buffer interval, using the W1 quantile representation.The representation expresses W1 as the integral of absolute quantile-function differences over [0, 1].Source: Technical Lemmas · pp. 48–49
• For a fixed induced policy, cumulative rewards can differ only from stages h+1 through H−1; the cited sum is at most 1 and contains exactly H−h−1 terms.Source: Technical Lemmas · pp. 50–51
• For finite state, action, and horizon sets with deterministic rewards in [0, 1], a positive root-level threshold makes the buffering gap zero below that threshold and bounds cumulative cost under logarithmic buffering.With β_t = τ log(e + t), the buffering gap is zero for all t ≥ K_τ.Source: Technical Lemmas · pp. 52–53
• For every deterministic policy, Δ_beta = 0 when 0 < beta <= rho_tau; for each u in [tau-beta, tau], Fπ(xπ−) < u <= Fπ(xπ).Source: Technical Lemmas · p. 53