Optimistic Reinforcement Learning with Quantile Objectives

Mohammad Alipour-Vaezi, Huaiyang Zhong, Kwok-Leung Tsui, Sajad Khodadadian · 2025

Read Optimistic Reinforcement Learning with Quantile Objectives by Mohammad Alipour-Vaezi, Huaiyang Zhong, Kwok-Leung Tsui, Sajad Khodadadian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-09652.txt.

Introduction

Mohammad Alipour-Vaezi and three co-authors build a reinforcement learning algorithm that optimizes a chosen quantile of total reward instead of the average. In healthcare and finance, the average outcome is the wrong target; decision-makers care about bad-tail or good-tail quantiles. Classical reinforcement learning foundations ignore that risk sensitivity entirely.

Their algorithm, UCB-QRL, works optimistically: estimate the transition probabilities, then optimize the quantile value over a confidence ball around the estimate. Iterating that loop yields a high-probability regret bound for finite-horizon problems, expressed through the numbers of states, actions, episodes, and horizon length. A problem-dependent constant captures how sensitive the quantile value is to model errors, shaping the guarantee's strength.

Catalog record

CREATORMohammad Alipour-Vaezi, Huaiyang Zhong, Kwok-Leung Tsui, Sajad Khodadadian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-09652

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimistic Reinforcement Learning with Quantile Objectives Mohammad Alipour-Vaezi, Huaiyang Zhong, Kwok-Leung Tsui, Sajad Khodadadian Abstract 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 and finance. A popular approach to incorporate risk sensitivity is to optimize a specific quantile of the cumulative reward distribution. In this paper, we develop UCB–QRL , an optimistic learning algorithm for the τ \tau -quantile objective in finite-horizon Markov decision processes (MDPs). UCB–QRL is an iterative algorithm in which, at each iteration, we first estimate the underlying transition probability and then optimize the quantile value function over a confidence ball around this estimate. We show that UCB–QRL yields a high-probability regret bound 𝒪 ⁡ ( ( 2 / κ ) H + 1 ​ H ​ S ​ A ​ T ​ H ​ log ⁡ ( 2 ​ S ​ A ​ T ​ H / δ ) ) \mathcal{O}\left((2/\kappa)^{H+1}H\sqrt{SATH\log(2SATH/\delta)}\right) in the episodic setting with S S states, A A actions, T T episodes, and H H horizons. Here, κ > 0 \kappa>0 is a problem-dependent constant that captures the sensitivity of the underlying MDP’s quantile value. Keywords: Reinforcement Learning; Risk-Sensitive Control; Quantile Markov Decision Process; Optimism in the Face of Uncertainty; Regret Analysis. 1 Introduction Reinforcement learning (RL) provides a general framework for sequential decision making by learning policies through interaction with an unknown environment [ 36 ] . Over the past decade, RL—often coupled with powerful function approximators such as deep neural networks, linear models, splines, and even quantum circuits—has revolutionized our ability to solve complex, high-dimensional decision-making problems. This synergy has enabled RL agents to achieve superhuman performance in games, competitive results in robotic control and locomotion, and large-scale deployment in recommendation systems and operations research [ 15 , 6 , 34 , 44 ] . Despite these advances, classical RL methods face an important limitation: they typically optimize expected return and are therefore risk–neutral [ 29 ] . This highlights the need for formulations that account for the variability and reliability of returns while maintaining data efficiency and principled exploration. Upper Confidence Bound (UCB) RL operationalizes optimism in the face of uncertainty. At the beginning of each episode, the learner forms confidence regions around the empirical transition model, plans in the most favorable (optimistic) Markov Decision Process (MDP) within those regions, and executes the resulting greedy policy. This plan–act–learn loop achieves near–minimax regret for finite episodic MDPs under the expectation objective [ 4 , 3 ] . Classical UCB methods are intrinsically risk–neutral : they optimize expected return [ 26 ] . In safety–critical control, service-level guarantees, and finance, tail performance (e.g., high-percentile delivery time or loss) is paramount [ 42 ] . Quantile or Value-at-Risk (VaR)-based objectives capture such requirements directly. The Quantile Markov Decision Process (QMDP) furnishes a backward dynamic program for \tau –quantile values, where the quantile operator is defined as Q_{\tau}(X)\coloneqq\inf\{x\in\mathbb{R}:\ \mathbb{P}(X\leq x)\geq\tau\} for the (left-continuous) \tau –quantile, via an operator on next-step quantile value maps [ 25 ] . A central obstacle in applying the quantile objective in RL is analytical: quantiles are nonlinear and can change abruptly with small distributional perturbations. In contrast to expectation operators, the quantile function lacks smoothness and convexity; therefore, classical optimism analyzes that linearize value differences fail. We overcome this by (i) expressing the one–step QMDP backup as the quantile of a continuation–mixture random variable, and (ii) proving a sharp, local Lipschitz property of this mapping under a benign quantile margin at level \tau . Informally, if the CDF of the continuation–mixture has a jump of size at least \kappa , then the \tau –quantile is (2/\kappa) –Lipschitz with respect to the 1-Wasserstein distance. Coupled with a TV \!\to W_{1} bound for mixtures and a coupling argument that uses a single auxiliary uniform variable to “align” next-state randomness, this yields a clean propagation inequality that is directly analogous to expectation-based analyzes with explicit \kappa –dependence. Contributions. 1. Algorithmic framework. We introduce UCB–QRL , an optimism-based learning algorithm for quantile objectives in finite-horizon MDPs. Each episode estimates the transition model, builds an \ell_{1} confidence set, and plans in the most favorable model via a quantile-aware planner. 2. High-probability regret guarantees. We study the convergence of UCB–QRL algorithm and establish a high-probability regret bound of order \mathcal{O}\left((2/\kappa)^{H+1}H\sqrt{SATH\log(2SATH/\delta)}\right) in the episodic setting, where \kappa is a problem-dependent constant that captures the sensitivity of the underlying MDP’s quantile value. 2 Related Work 2.1 Risk-Sensitive MDPs Risk-sensitive objectives in sequential decision making have been studied under several paradigms. Early work on percentile/quantile criteria analyzed existence, structure, and computation in controlled Markov processes with known dynamics, including shortest-path and service-level formulations [ 16 , 13 ] . The Quantile MDP (QMDP) framework formalizes dynamic programming for fixed quantile levels and establishes a backward recursion and planning algorithms under known kernels [ 25 ] . Closely related, distributional RL propagates the full return distribution and has yielded practical quantile parameterizations such as QR-DQN and IQN [ 5 , 12 , 11 , 32 , 41 ] . While distributional RL methods typically optimize expectation , their estimators provide tools for learning quantile slices. Beyond quantiles, classical risk-sensitive control optimizes exponential-utility (entropic) criteria, leading to modified Bellman equations and dynamic consistency [ 22 ] . Mean–variance MDPs study return–variance trade-offs but face time-inconsistency without special structure [ 35 , 28 , 20 ] . Coherent risk measures—especially Conditional Value-at-Risk (CVaR) [ 31 , 10 ] —enable convex surrogates and have been widely explored in RL via value-based, policy-gradient, and actor–critic methods as either objectives or constraints [ 9 , 37 , 30 ] . Constrained MDPs (CMDPs) and safe RL incorporate chance- or CVaR-type constraints using Lagrangian, primal–dual, or Lyapunov approaches [ 2 , 8 , 45 , 27 , 1 ] . These lines of research are largely complementary to our setting, which maximizes a fixed quantile objective rather than enforcing it as a constraint, and thus requires handling the non-smooth, set-valued nature of the quantile backup itself. Methodologically, quantile regression [ 24 ] underlies many practical estimators used by distributional/quantile RL, but most of this literature does not address online regret with unknown transitions [ 12 , 11 , 41 ] . 2.2 Optimism and Upper Confidence Bounds (UCB) Optimism in the face of uncertainty provides near-minimax regret guarantees for expectation-maximizing RL by planning in confidence sets built around empirical transition models. In average-reward communicating MDPs, the UCRL2 algorithm achieves \tilde{\mathcal{O}}(DS\sqrt{AT}) -type guarantees via \ell_{1} confidence sets and Extended Value Iteration (EVI) [ 23 ] . In finite-horizon problems, UCBVI algorithm attains \tilde{\mathcal{O}}(H\sqrt{SAT}) with Hoeffding bonuses and \tilde{\mathcal{O}}(\sqrt{HSAT}) with Bernstein bonuses [ 4 ] . Robust and distributionally robust MDPs planning against uncertainty sets at decision time, yielding max–min or ambiguity-aware backups that are algorithmically akin to optimistic EVI subroutines [ 43 , 19 , 40 , 14 ] . Adapting optimism to nonlinear , tail-focused criteria poses additional challenges: quantile objectives are non-smooth and can change abruptly under small distributional perturbations, so linear value-difference decompositions used for expectation do not directly apply. In one-step settings, bandit studies have

Read the complete text