🤖 machine learning

Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

This paper introduces UCB-BQRL, a model-based reinforcement learning algorithm that utilizes a smoothed lower-buffered quantile objective and an exact dynamic programming procedure (EVI-BQ) to achieve stable, risk-sensitive learning with provable regret bounds and computational hardness results for quantile evaluation.

Original authors: Mohammad Alipour-Vaezi, Huaiyang Zhong, Sajad Khodadadian

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammad Alipour-Vaezi, Huaiyang Zhong, Sajad Khodadadian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, there is a powerful method called reinforcement learning, where a computer program learns to make decisions by trying things out and seeing what happens. Imagine a student learning to ride a bike: they fall, adjust their balance, and eventually succeed. In the digital realm, these programs interact with an environment, receive rewards for good choices, and learn to maximize their total reward over time. For decades, the standard goal for these programs has been simple: get the highest average score possible. This approach works well for many tasks, from playing video games to managing inventory. However, in high-stakes fields like finance or healthcare, the average is not enough. A doctor does not just want a treatment that works well on average; they need one that avoids catastrophic failure, even if it means a slightly lower average success rate. Similarly, an investor might prefer a strategy that guarantees a safe minimum return over one that offers a huge potential gain but carries a risk of total loss. To handle these situations, researchers have turned to a concept called the "quantile." Instead of looking at the average, a quantile looks at a specific point in the distribution of outcomes, such as the bottom ten percent or the top ninety percent, allowing a decision-maker to focus on safety or aggression as needed.

The challenge, however, is that optimizing for these specific points in the distribution is notoriously difficult. Unlike the average, which changes smoothly when you tweak the environment, these specific points can jump abruptly. If a computer program learns the rules of the world from data, and that data has a tiny error, the program's idea of what constitutes a "safe" outcome can suddenly flip to something completely different. This instability makes it hard to build reliable learning systems for risk-sensitive goals. In a new study, researchers at Virginia Tech have developed a solution to this problem. They created a new learning algorithm that smooths out these abrupt jumps, allowing the computer to learn safely and effectively even when the data is imperfect.

The researchers, Mohammad Alipour-Vaezi, Huaiyang Zhong, and Sajad Khodadadian, introduced a method they call UCB-BQRL. The core idea is to replace the sharp, jagged target of a specific outcome with a "buffered" version. Instead of aiming for a single, precise point in the distribution of possible rewards, the algorithm aims for a small range just below that point. It averages the outcomes in this small range, creating a smooth, stable target that is much easier to learn from. Think of it like trying to balance a pencil on its tip versus balancing it on a small, flat platform; the platform is less sensitive to tiny wobbles. By using this smoothed target during the learning process, the algorithm can explore the environment and build a model of how things work without being thrown off by minor errors in its data. Once the learning is complete, the algorithm can still evaluate the final result against the original, sharp target, ensuring that the goal remains exactly what the user intended.

To test their method, the team applied it to a classic decision-making problem known as asset selling. In this scenario, a seller receives a series of offers for an item over a fixed period. At each step, the seller must decide whether to accept the current offer and stop, or reject it and wait for a new, random offer. The challenge is to find the right moment to stop to maximize the final price. In the real world, the seller does not know the exact probabilities of future offers; they must learn them from experience. The researchers ran simulations where their new algorithm had to learn these probabilities while trying to maximize a specific quantile of the final price. They compared their method against several established learning techniques, including those designed to maximize the average price and others that use different strategies to explore the unknown.

The results showed that the new algorithm excelled at its specific task. When the goal was to maximize the median outcome, or the middle ground, the new method learned a policy that performed significantly better than the others. When the goal shifted to maximizing the top ten percent of outcomes, it again outperformed the competition. Interestingly, even when the algorithm was trained to be very conservative, aiming for the bottom ten percent of outcomes, it did not perform terribly when judged by the standard average score. It remained competitive, suggesting that focusing on risk does not necessarily mean sacrificing overall performance. The study also included a rigorous mathematical proof showing that the algorithm's learning speed is as fast as theoretically possible given the difficulty of the problem. They demonstrated that the speed of learning depends on a specific property of the problem: how much the outcome distribution changes near the target point. If the distribution is very flat or unstable near that point, learning is inherently slower, and their method correctly accounts for this difficulty.

Beyond the practical success, the researchers uncovered a surprising fact about the mathematics of these problems. They proved that calculating the exact value of a specific outcome point for a fixed strategy is computationally extremely hard, even for very simple scenarios with just two possible states and one action. This means that while their algorithm provides a way to learn effectively, the perfect, exact calculation of the best possible strategy is likely impossible to do quickly for complex real-world problems. This finding separates the statistical ability to learn from the computational ability to plan perfectly. The researchers' work does not claim to have solved every risk-sensitive problem, but it provides a robust, stable framework for learning when the stakes are high and the data is noisy. By smoothing the path forward, they have made it possible for artificial intelligence to navigate the delicate balance between safety and reward with a level of reliability that was previously out of reach.

Technical Summary: Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

1. Problem Formulation

The paper addresses the challenge of Risk-Sensitive Reinforcement Learning (RL) in finite-horizon Markov Decision Processes (MDPs) with unknown transition dynamics. While classical RL focuses on maximizing the expected cumulative reward, this work targets the optimization of a specific $\tau$ -quantile of the cumulative reward distribution.

The core difficulty lies in the nature of quantile objectives:

Non-smoothness: Exact quantile functions are non-smooth and can change abruptly under small perturbations of the return distribution.
Instability: In online learning where the transition model must be estimated from data, small estimation errors can shift probability mass across the target quantile level, causing the policy value to change discontinuously. This makes standard "optimism in the face of uncertainty" approaches, which rely on smooth value differences, difficult to apply directly.

The objective is to find a policy $\pi$ that maximizes $V_{\pi, P^*}^{\tau, 0}(\bar{s})$ , the $\tau$ -quantile of the return distribution starting from a fixed initial state $\bar{s}$ under the true transition kernel $P^*$ .

2. Methodology

2.1 Lower-Buffered Quantile Criterion

To overcome the instability of exact quantiles, the authors introduce a lower-buffered quantile objective. Instead of optimizing the exact $\tau$ -quantile $Q_\tau(X)$ , the algorithm optimizes an averaged version over a small interval below $\tau$ :
$Q^\beta_\tau(X) := \frac{1}{\ell_\beta(\tau)} \int_{\tau-\ell_\beta(\tau)}^{\tau} Q_u(X) du$
where $\ell_\beta(\tau) = \min\{\beta, \tau\}$ and $\beta$ is a buffer parameter. This smoothing renders the objective globally Lipschitz continuous with respect to the Wasserstein distance, stabilizing the planning process against transition-estimation errors while maintaining a direct connection to the exact quantile as $\beta \to 0$ .

2.2 UCB–BQRL Algorithm

The proposed algorithm, UCB–BQRL, is a model-based, optimistic learning algorithm operating in episodes. Its structure follows an "estimate $\to$ buffer $\to$ plan" paradigm:

Confidence Sets: At each episode $t$ , the algorithm maintains a confidence set $\mathcal{C}_t^\delta$ of plausible transition kernels based on observed data, using $\ell_1$ confidence radii.
Optimistic Planning: Within this confidence set, the algorithm selects a transition kernel $P$ and a deterministic history-dependent policy $\pi$ that maximizes the lower-buffered quantile value.
Execution: The selected policy is executed in the true environment, and counts are updated for the next episode.
Buffer Schedule: The buffer parameter $\beta_t$ is non-increasing (e.g., logarithmic decay), allowing the algorithm to start with a smoothed objective for stability and gradually converge to the exact quantile objective.

2.3 EVI–BQ Planning Oracle

To solve the optimistic planning step, the authors introduce EVI–BQ (Extended Value Iteration for Buffered Quantiles).

Unlike standard value iteration which tracks scalar expected values, EVI–BQ tracks the full return law (probability distribution of cumulative rewards) for each state and stage.
It maintains a "frontier" of achievable return laws and their corresponding recursive policy labels.
The algorithm performs backward recursion from the horizon $H$ to $0$, constructing mixtures of return laws based on transition probabilities and selecting actions that maximize the lower-buffered quantile.
The authors prove that EVI–BQ correctly solves the optimistic planning problem over the confidence set.

3. Key Contributions

Formulation of Online Quantile RL: The paper formulates the episodic finite-horizon RL problem with unknown transitions and a fixed quantile objective.
UCB–BQRL Algorithm: Introduction of a model-based algorithm combining transition confidence sets with a lower-buffered smooth approximation of the quantile objective.
Exact Planning Procedure (EVI–BQ): Development of an exact dynamic programming procedure to solve the buffered planning problem, handling the non-Markovian nature of quantile objectives via state-augmented return laws.
Regret Analysis:
- Upper Bound: A high-probability regret bound for UCB–BQRL is established. Under a logarithmic buffer schedule, the regret scales as $\tilde{O}(e^{\tau/\rho_\tau} + H^2\sqrt{SAT})$ , where $\rho_\tau$ is a problem-dependent constant (root-level left-plateau threshold).
- Lower Bound: An information-theoretic lower bound of $\Omega(\frac{H}{\rho_\tau}\sqrt{AT})$ is proven for any algorithm dealing with exact quantile objectives. This demonstrates that the dependence on $1/\rho_\tau$ is unavoidable and highlights a fundamental statistical barrier.
Computational Hardness: The paper proves that 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. This separates the statistical learnability from computational tractability.

4. Results

Theoretical Results

Sublinear Regret: The algorithm achieves sublinear regret with respect to the number of episodes $T$ , provided the buffer schedule decreases appropriately. The regret consists of a finite transient term (due to the initial buffering gap) and a statistical learning term.
Statistical Barrier: The lower bound confirms that the difficulty of learning quantile objectives is intrinsically linked to the local geometry of the return distribution near the target quantile (specifically the plateau width $\rho_\tau$ ). Small plateaus require higher statistical precision to distinguish between policies.
Computational Limits: The PP-hardness result indicates that while the problem is statistically learnable, exact planning is computationally intractable in general, justifying the use of the exact planner as a theoretical oracle rather than a scalable implementation.

Numerical Experiments

The authors evaluate UCB–BQRL on a finite-horizon asset-selling problem (an optimal stopping problem).

Setup: The algorithm is compared against standard benchmarks (UCBVI, Q-learning, SARSA, Thompson Sampling, TRPO, PPO) across target quantiles $\tau \in \{0.1, 0.5, 0.9\}$ .
Findings:
- Quantile Performance: UCB–BQRL significantly outperforms all benchmarks when policies are evaluated based on the target quantile criterion. For $\tau=0.5$ and $\tau=0.9$ , it achieves the smallest cumulative policy gap.
- Expected Return: When evaluated on the standard expected return criterion, UCB–BQRL (trained for a conservative $\tau=0.1$ ) remains competitive (second-best), suggesting that optimizing for risk sensitivity does not necessarily degrade expected performance in this setting.
- Policy Structure: The learned policies exhibit a clear threshold structure: lower $\tau$ values lead to more conservative stopping rules (accepting lower offers), while higher $\tau$ values lead to more aggressive strategies (waiting for higher offers).

5. Significance and Claims

The paper claims to provide the first comprehensive framework for online learning with quantile objectives under unknown dynamics. Its significance lies in:

Stabilizing Risk-Sensitive Learning: By introducing the lower-buffered quantile, the authors resolve the instability caused by the non-smoothness of exact quantiles, enabling the application of optimism-based exploration.
Characterizing Statistical Limits: The work identifies the root-level left-plateau threshold ( $\rho_\tau$ ) as a critical problem-dependent parameter governing the difficulty of learning. It establishes that the statistical complexity of quantile RL is fundamentally different from expected-return RL due to the sensitivity of quantiles to small distributional shifts.
Separating Statistics and Computation: The paper rigorously distinguishes between the statistical learnability of the problem (achievable with sublinear regret) and its computational hardness (PP-hard exact evaluation), clarifying the role of the exact planner as a theoretical tool.
Practical Applicability: Through the asset-selling experiment, the authors demonstrate that the proposed method effectively learns risk-sensitive policies that adapt to the target quantile, outperforming standard expectation-based methods in risk-sensitive metrics.

The authors remain modest regarding the computational scalability of the exact planner (EVI–BQ), acknowledging that practical implementations require approximations (e.g., candidate models, pruning) which introduce planning errors, though the theoretical framework provides the necessary bounds for analysis.