Optimistic Reinforcement Learning with Quantile Objectives

• URL: http://arxiv.org/abs/2511.09652v1
• Date: Fri, 14 Nov 2025 01:02:21 GMT
• Title: Optimistic Reinforcement Learning with Quantile Objectives
• Abstract summary: UCB-QRL is an optimistic learning algorithm for the $$-quantile objective in finite-horizon Markov decision processes.<n>We show that UCB-QRL yields a high-probability regret bound $mathcal Oleft((2/)H+1HsqrtSATHlog (2SATH/)right.
• Score: 6.759916334688207
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $τ$-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 $\mathcal O\left((2/κ)^{H+1}H\sqrt{SATH\log(2SATH/δ)}\right)$ in the episodic setting with $S$ states, $A$ actions, $T$ episodes, and $H$ horizons. Here, $κ>0$ is a problem-dependent constant that captures the sensitivity of the underlying MDP's quantile value.

Related papers

• Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives [2.153824429735596]
  We develop a model-based optimistic learning algorithm that maintains confidence sets for the transition kernel and plans using a lower-buffered quantile criterion.<n>We prove that the exact point-quantile evaluation and exact lower-buffered quantile evaluation are PP-hard under Turing-time reductions.
  arXiv  Detail & Related papers  (2026-08-23T05:41:32Z)
• Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding [9.43984448422843]
  We introduce a K-step lookahead Q-function that truncates planning to the next K steps.<n>We numerically evaluate the performance of our algorithm under the objective of maximizing reward.<n> Empirical results demonstrate superior cumulative rewards over state-of-the-art RL methods across synthetic MDPs and RL environments.
  arXiv  Detail & Related papers  (2026-01-31T15:44:12Z)
• Provably Efficient and Agile Randomized Q-Learning [35.14581235983678]
  We propose a novel variant of Q-learning algorithm, refereed to as RandomizedQ, which integrates sampling-based exploration with agile, step-wise, policy updates.<n> Empirically, RandomizedQ exhibits outstanding performance compared to existing Q-learning variants with both bonus-based and Bayesian-based exploration on standard benchmarks.
  arXiv  Detail & Related papers  (2025-06-30T16:08:29Z)
• Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism [1.4999444543328293]
  We propose a model-based algorithm based on novel cost and reward function estimators. Our algorithm achieves a regret upper bound of $widetildemathcalO((bar C - bar C_b)-1H2.5 SsqrtAK)$ where $bar C$ is the cost budget for an episode.
  arXiv  Detail & Related papers  (2024-10-14T04:51:06Z)
• Stochastic Q-learning for Large Discrete Action Spaces [79.1700188160944]
  In complex environments with discrete action spaces, effective decision-making is critical in reinforcement learning (RL) We present value-based RL approaches which, as opposed to optimizing over the entire set of $n$ actions, only consider a variable set of actions, possibly as small as $mathcalO(log(n)$)$. The presented value-based RL methods include, among others, Q-learning, StochDQN, StochDDQN, all of which integrate this approach for both value-function updates and action selection.
  arXiv  Detail & Related papers  (2024-05-16T17:58:44Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  We show how to achieve minimax-optimal regret without incurring any burn-in cost.<n>We extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances.
  arXiv  Detail & Related papers  (2023-07-25T15:42:11Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL) We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.
  arXiv  Detail & Related papers  (2023-05-29T17:11:28Z)
• Provably Efficient Neural Offline Reinforcement Learning via Perturbed Rewards [33.88533898709351]
  VIPeR amalgamates the randomized value function idea with the pessimism principle. It implicitly obtains pessimism by simply perturbing the offline data multiple times. It is both provably and computationally efficient in general Markov decision processes (MDPs) with neural network function approximation.
  arXiv  Detail & Related papers  (2023-02-24T17:52:12Z)
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret [23.418957451727255]
  We propose a novel UCRL-style algorithm for quantum reinforcement learning (RL) We establish an $mathcalO(mathrmpoly(S, A, H, log T))$ worst-case regret for it, where $T$ is the number of episodes. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with $d$-dimensional linear representation.
  arXiv  Detail & Related papers  (2023-02-21T16:23:11Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  Two-player zero-sum Markov games are arguably the most basic setting in multi-agent reinforcement learning. We develop a learning algorithm that learns an $varepsilon$-approximate Markov NE policy using $$ widetildeObigg. We derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities.
  arXiv  Detail & Related papers  (2022-08-22T17:24:55Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
  arXiv  Detail & Related papers  (2022-06-13T19:11:22Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  We study human-in-the-loop reinforcement learning (RL) with trajectory preferences. Instead of receiving a numeric reward at each step, the agent only receives preferences over trajectory pairs from a human overseer. We propose the first optimistic model-based algorithm for PbRL with general function approximation.
  arXiv  Detail & Related papers  (2022-05-23T09:03:24Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  We consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies $Pi$ that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank $d$ of the underlying MDP.
  arXiv  Detail & Related papers  (2021-06-22T03:20:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.