Reinforcement Learning (RL) has achieved tremendous success in recent years. However, the classical foundations of RL do not account for the risk sensitivity of the objective function, which is critical in various fields, including healthcare, finance, etc. A popular approach to incorporate risk sensitivity is to optimize a specific quantile of the cumulative reward distribution. However, exact quantile objectives are non-smooth and can change abruptly under small perturbations of the return distribution, making them difficult to optimize reliably when the transition model must be learned from data. Motivated by this instability, we develop UCB-BQRL, a model-based optimistic learning algorithm that maintains confidence sets for the transition kernel and plans using a lower-buffered quantile criterion. The buffered criterion smooths the exact quantile objective by averaging nearby lower quantiles, thereby improving stability under transition-estimation error. To compute the buffered-quantile policy at each episode, we introduce EVI-BQ, an exact dynamic-programming procedure. We establish a high-probability regret bound for UCB-BQRL, which up to logarithmic factors scales as O(eτ/ρτ+H2SAT), where ρτ is denoted as the root-level left-plateau threshold, which is a problem-dependent constant. Further, we establish an information-theoretic lower bound of Ω(H/ρτAT) for the regret of any algorithm dealing with a quantile objective function. Finally, we prove that the exact point-quantile evaluation 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.
Figures & tables
Figure 1: Cumulative expected-return regret RE(k) in the asset-selling experiment when UCB–BQRL is trained with target quantile τ=0.1 . Regret is measured relative to the finite-horizon expected-return-optimal benchmark. Curves show the mean over the three held-out seeds, and shaded regions show the descriptive pointwise variability bands defined in the preceding subsection.
Figure 2: Cumulative numerical τ -quantile policy gap Gτ(k) in the asset-selling experiment for τ=0.5 , measured relative to the approximate-frontier numerical reference. Curves show the mean over the three held-out seeds, and shaded regions show the descriptive pointwise variability bands defined in the preceding subsection.
Figure 3: Cumulative numerical τ -quantile policy gap Gτ(k) in the asset-selling experiment for τ=0.9 , measured relative to the capped-frontier numerical reference. Curves show the mean over the three held-out seeds, and shaded regions show the descriptive pointwise variability bands defined in the preceding subsection.
Figure 4: Selected final UCB–BQRL policies in the asset-selling experiment for τ∈{0.1,0.5,0.9} . For each target quantile, the displayed policy is taken from the held-out run with the smallest final quantile error; buffered-quantile error and seed number are used as tie-breakers. Dark-blue cells indicate Continue and light-gray cells indicate Stop . The displayed policies are selected for structural illustration and should not be interpreted as averages across seeds. The absorbing post-sale state is omitted.
Figure 5: Quantile functions of the root return law in the information-theoretic lower-bound construction. For the distinguished action a⋆ , the return is 0 with probability τ−ρ and H−1 otherwise, so its quantile function jumps at τ−ρ . For any suboptimal action a=a⋆ , the return is 0 with probability τ+ρ and H−1 otherwise, so its quantile function jumps at τ+ρ . Therefore, at the target level τ , the distinguished action has Qτ(Ga⋆)=H−1 , whereas any suboptimal action has Qτ(Ga)=0 . The open and closed circles reflect the left-continuous quantile convention.
City University of Hong Kong Hong Kong, China · University of Chicago Chicago, IL, USA · The Chinese University of Hong Kong, Shenzhen Shenzhen, Guangdong, China +1