PaperlayerView exact revision on arXiv

Source-linked AI summary

Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

Mohammad Alipour-Vaezi, Huaiyang Zhong, Sajad Khodadadian

arXiv:2608.22227v1cs.LGmath.OC

TL;DR

Quantile-based risk objectives are difficult to optimize when transition models are learned from data. The paper introduces buffered optimistic learning and establishes regret guarantees, lower bounds, and computational-hardness results for quantile objectives.

  • Problem

    Expectation can be inadequate when reinforcement-learning applications require safety constraints or attention to risk-sensitive performance.

  • Method

    UCB-BQRL combines optimistic transition-kernel confidence sets with lower-buffered quantile planning, while EVI-BQ exactly solves the buffered objective.

  • Results

    The paper establishes high-probability regret guarantees, an information-theoretic lower bound, and sublinear exact-quantile regret under a logarithmically decreasing buffer schedule.

  • Takeaways & Limitations

    Buffered quantile learning provides a theoretically grounded framework for risk-sensitive online reinforcement learning with stable quantile optimization.

  • Takeaways & Limitations

    The analysis assumes finite state-action spaces and deterministic rewards bounded in [0,1].

Abstract

from arXiv · show

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 $\mathcal{O}(\mathrm{e}^{τ/ρ_τ}+H^2\sqrt{SAT})$, 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/ρ_τ\sqrt{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.

1 Introduction

The paper addresses online finite-horizon reinforcement learning with unknown transitions when maximizing a fixed quantile is important but unstable under transition-estimation error. It introduces buffered optimistic learning and establishes statistical guarantees alongside exact-planning hardness results.

  • Algorithm: UCB–BQRL combines transition confidence sets with a lower-buffered quantile objective for optimistic model-based learning under unknown dynamics.The buffer averages ordinary quantiles over an interval below the target, smoothing the criterion while retaining its connection to exact-quantile regret.
  • Results: O(e^{τ/ρ_τ}+H^2√SAT) is the high-probability regret scaling established for UCB–BQRL, up to logarithmic factors.Here, ρ_τ is the problem-dependent root-level left-plateau threshold, and the resulting exact-quantile regret is sublinear under a logarithmically decreasing buffer schedule, aside from a finite instance-dependent transient term.
  • Results: Ω(H/ρ_τ√AT) is an information-theoretic lower bound on expected exact-quantile regret for some finite-horizon MDPs and every learning algorithm.The result shows that dependence on 1/ρ_τ is unavoidable.
  • Computational complexity: Exact point-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.This separates the statistical role of an exact planning oracle from its computational tractability in general instances.
  • Planning: EVI–BQ provides an exact dynamic-programming procedure for the buffered quantile planning problem arising within UCB–BQRL.This procedure solves the buffered objective used at each episode.

2 Related Work

Prior work studies quantile and other risk-sensitive objectives, distributional estimators, optimistic planning, and model-based or approximate RL. This paper addresses the less-developed problem of online regret for fixed quantile maximization under unknown transition dynamics.

  • Quantile and distributional RL: Quantile MDP research established structural and computational foundations, including backward-recursion and planning procedures for fixed quantile levels with known transition kernels.Related work also incorporates quantile risk into RL with unknown kernels.
  • Quantile and distributional RL: Distributional RL propagates return distributions and provides practical quantile parameterizations such as QR-DQN and IQN, although it typically optimizes expected return.Its estimators remain useful for learning quantile slices.
  • Risk-sensitive control: Classical risk-sensitive control includes dynamically consistent exponential-utility criteria, time-inconsistent mean–variance MDPs, and convex CVaR formulations used as objectives or constraints.CMDPs and safe RL extend these ideas through chance-type or CVaR-type constraints and Lagrangian, primal–dual, or Lyapunov-based methods.
  • Optimism under uncertainty: Optimistic RL commonly plans over confidence sets using EVI-type procedures, but nonlinear tail objectives create non-smooth, discontinuous responses that defeat standard value-difference decompositions.Extending optimism to MDPs therefore requires new contraction and sensitivity arguments.
  • Function approximation and model-based RL: Function approximation and model-based deep RL improve scalability, planning, and sample efficiency, but most methods target expected return and use heuristic uncertainty mechanisms.Regret analysis for nonlinear, tail-sensitive objectives under function approximation remains substantially less developed.

3 Preliminaries

The paper studies finite-horizon tabular MDPs with bounded deterministic rewards and optimizes a fixed target quantile of the return distribution. Lower-buffered quantiles locally smooth this objective, yielding Wasserstein-Lipschitzness, while the root-level left-plateau threshold governs agreement with the exact quantile and appears in regret bounds.

  • MDP setting: The setting is a finite-horizon MDP with finite state and action spaces, transition kernel P★, and deterministic rewards r_h(s,a) ∈ [0,1].The planning horizon is H, with S = |S| denoting the number of states.
  • Quantile objective: The objective is the τ-quantile of the return distribution from a fixed designated initial state, for a target level τ ∈ (0,1).The paper considers deterministic history-dependent policies in the finite tabular setting.
  • Lower-buffered quantile: The lower-buffered quantile averages ordinary quantiles over levels immediately below the target, providing local smoothing of the objective.For β ∈ (0,1) and q ∈ (0,1], the lower integration limit is ℓ_β(q) = min{β,q}.
  • Quantile objective: Exact quantile backups are non-smooth and can change discontinuously under small distributional perturbations.This instability motivates replacing the exact objective with a lower-buffered quantile.
  • Stability and plateau threshold: The resulting functional is globally Lipschitz in Wasserstein distance, enabling UCB-style regret bounds under standard finite tabular assumptions.For finite-support root return laws, the root quantile is constant on a nonzero interval ending at τ; the smallest uniform width is the root-level left-plateau threshold, which controls buffered–exact agreement and enters both regret bounds.

4 Optimistic Buffered Quantile Learning

This section introduces UCB–BQRL, which learns transition confidence sets and plans with a lower-buffered quantile objective, using EVI–BQ for exact optimistic re-planning. It establishes regret guarantees, an information-theoretic lower bound, and PP-hardness for exact quantile evaluations.

  • UCB–BQRL: UCB–BQRL maintains transition confidence sets and replaces unstable point-quantile planning with a lower-buffered, globally Lipschitz objective.Its estimate → buffer → plan structure preserves optimism while stabilizing planning under transition-estimation error.
  • EVI–BQ: EVI–BQ exactly implements the optimistic buffered re-planning step by recursively computing achievable return-law frontiers rather than scalar state values.For each candidate model, it works backward from stage H to stage 0 and retains full return distributions.
  • Regret guarantees: O(e^(τ/ρ_τ) + H^2√(SAT)) is the high-probability regret scaling established for UCB–BQRL, up to logarithmic factors.The buffering gap vanishes once the non-increasing buffer becomes smaller than the root-level plateau width ρ_τ.
  • Fundamental limits: Ω(H/ρ_τ√(AT)) is an information-theoretic lower bound for exact quantile regret, independent of the learner’s buffer schedule or planning procedure.The bound holds even for a two-state MDP with deterministic rewards, showing that dependence on ρ_τ is intrinsic.
  • Computational hardness: PP-hardness under polynomial-time Turing reductions applies to both exact finite-horizon quantile evaluation and exact lower-buffered quantile evaluation.This remains true for a fixed deterministic policy in a two-state, one-action finite-horizon MDP with binary transition probabilities and deterministic rational rewards in [0, 1].

5 Numerical Experiment

The numerical study evaluates a practical UCB–BQRL implementation on a finite-horizon asset-selling MDP using an approximate buffered-quantile planner. UCB–BQRL is competitive on expected-return regret and superior on quantile-sensitive policy gaps, while learning threshold stopping rules that vary with the target quantile and remaining horizon.

  • Implementation: The implementation replans each episode with empirical transition estimates, row-wise ℓ1 confidence radii, a tunable confidence multiplier, and buffer schedule β_t = τ/log(e + t).It approximates the exact EVI–BQ optimization with a computationally tractable planner and does not execute the unrestricted oracle because its return-law frontiers can grow rapidly.
  • Performance: At episode 2000, UCBVI has mean cumulative expected-return regret 15.73, compared with 229.00 for UCB–BQRL and 586.19 for SARSA.UCB–BQRL is therefore second-best on this conventional expected-return measure despite optimizing a lower-tail quantile.
  • Performance: For τ = 0.5, UCB–BQRL has the smallest cumulative numerical policy gap, with mean value 1.15 at episode 2000 versus 9.13 for UCBVI and 114.43 for ε-greedy Q-learning.The numerical policy gap is distinct from the exact quantile regret analyzed theoretically.
  • Performance: For τ = 0.9, UCB–BQRL again has the smallest cumulative numerical policy gap, reaching 0.79 at episode 2000 versus 2.79 for UCBVI and 56.38 for the next-smallest baseline.This advantage reflects that UCB–BQRL’s planning objective explicitly depends on the target quantile.
  • Learned stopping rules: At the first decision period, continuation thresholds are offers s ≤ 13 for τ = 0.1, s ≤ 21 for τ = 0.5, and s ≤ 23 for τ = 0.9.Thus, higher τ expands the continuation region: τ = 0.1 accepts offers of at least 14, whereas τ = 0.9 accepts only offer 24.
  • Learned stopping rules: For every τ, the stopping region expands as the horizon shortens, and all displayed policies choose Stop for every offer in the final decision period.The learned rule therefore depends jointly on target quantile, current offer, and remaining decision periods.

6 Discussion

The discussion presents lower buffering as a stabilizer for quantile learning under transition uncertainty, while clarifying that exact buffered planning is computationally difficult and that the root-level plateau governs both approximation and statistical difficulty.

  • Methodological implications: Lower buffering smooths nonlinear, discontinuous quantile objectives, reducing sensitivity to transition uncertainty while approaching the exact objective as the buffer shrinks.The regret decomposition separates transition-estimation error from buffered-objective approximation error.
  • Computational scope: EVI–BQ tracks full return distributions and policy-tree labels, making it an exact optimistic planning oracle rather than a scalable generic algorithm.Return-law growth with horizon, states, and actions can make confidence-set optimization costly.
  • Regret interpretation: The buffer balances exact-quantile accuracy against statistical stability, while confidence sets address transition uncertainty and lower buffering stabilizes planning.The lower bound indicates that quantile sensitivity is intrinsic: small transition-probability changes can switch the exact quantile between low and high values.
  • Root-level plateau: The root-level plateau ρ_τ determines when buffering recovers the exact objective and captures local return-distribution geometry analogous to a margin or gap.When the buffer is smaller than the plateau width, buffered and exact quantile values coincide after a finite transient under a decreasing schedule; smaller ρ_τ indicates a more fragile threshold.
  • Computational scope: Exact point-quantile and lower-buffered quantile evaluation are PP-hard even for a fixed policy in a highly restricted finite-horizon MDP.Thus, EVI–BQ is best viewed as an exact planning oracle, motivating approximate planners with explicit planning-error guarantees.

Appendix · Proof of Theorem 1

The proof of Theorem 1 starts from quantile regret and combines confidence-set containment with a high-probability event established through martingale and concentration arguments. A union bound yields simultaneous validity with probability at least 1 − 2δ.

  • Proof of Theorem 1: The proof begins from the definition of quantile regret.
  • Proof of Theorem 1: With probability at least 1 − δ, both the true transition kernel P★ and planned model P_t belong to the confidence set C_t.
  • Proof of Theorem 1: Lemma 3 provides a probability-at-least-1 − δ event holding for every episode t = 0, ..., T − 1.
  • Proof of Theorem 1: The argument conditions on observations before episode t together with the planned model P_t, with the counts fixed.
  • Proof of Theorem 1: Because stage rewards lie in [0, 1] and β_t ≤ τ, Definition 1 gives ℓ_βt(τ) = β_t before applying Lemma 4.
  • Proof of Theorem 1: The proof treats the relevant sequence as a martingale difference sequence with respect to the episode filtration, while allowing the left-hand side of (7) to be negative through an absolute-value bound.
  • Proof of Theorem 1: Combining the martingale event with confidence containment and applying a union bound gives simultaneous validity with probability at least 1 − 2δ.

Proof of Theorem 2

The proof constructs a two-state finite-horizon MDP in which identifying the optimal τ-quantile policy is equivalent to identifying the best arm in a stochastic Bernoulli bandit. The distinguished action yields an exact τ-quantile of H−1, while every other action yields 0, creating a per-episode quantile gap of H−1.

  • Hard-instance construction: A two-state MDP hides a distinguished action a★, with randomness only in the first transition and both states absorbing thereafter.The first action determines whether the process reaches the high-reward absorbing state.
  • Bandit reduction: The learner’s interaction is equivalent to an A-armed Bernoulli bandit whose distinguished arm exceeds every other arm by a transition-probability gap of 2ρ.Selecting action a observes whether the first transition reaches s1, with success probability p(a).
  • Return distribution: The return is 0 if the process remains in s0 and H−1 if it reaches s1, so each policy induces a two-point return distribution.Rewards are zero in s0 and one in s1 from stages 1 through H−1.
  • Quantile separation: At the target level τ, the distinguished action has Q_τ(G_a★) = H−1, whereas every suboptimal action has Q_τ(G_a) = 0.Their quantile functions jump at τ−ρ and τ+ρ, respectively, placing τ on opposite sides of the jumps.
  • Gap and plateau constant: The per-episode exact τ-quantile gap is H−1, and the constructed instance has root-level plateau constant ρ_τ = ρ.The plateau calculation gives a minimum distance of ρ for deterministic policies.

Proof of Theorem 3

The proof reduces threshold counting 0/1-knapsack to quantile evaluation using a two-state, one-action finite-horizon MDP. This establishes PP-hardness for both exact point-quantile and exact lower-buffered quantile evaluation, and consequently for their planning versions.

  • Reduction source: The reduction starts from threshold counting 0/1-knapsack, equivalent to the Kth largest subset problem and PP-complete under polynomial-time Turing reductions.The source asks whether at least M subsets have total weight at most K.
  • MDP construction: H=n+1 and a two-state, one-action MDP encode independent Bernoulli(1/2) state indicators whose weighted sum is the unique policy’s total return.The construction uses deterministic rewards based on the knapsack weights, while intermediate transitions move to state 1 with probability 1/2.
  • Point-quantile evaluation: Exact point-quantile evaluation decides the threshold counting-knapsack problem, making exact QMDP evaluation PP-hard.The reduction distinguishes whether the knapsack count is at least M by comparing the return quantile with a threshold c.
  • Lower-buffered quantile evaluation: Exact lower-buffered quantile evaluation is likewise PP-hard, using β=2^-(n+1) to separate the relevant quantiles across the return lattice.The endpoint τ−β has measure zero, so it does not affect the reduction.
  • Planning hardness: Because the constructed MDP has one action and one policy, both exact point-quantile planning and exact lower-buffered quantile planning are PP-hard.Planning contains evaluation as a special case in this construction.

Proof of Proposition 1

The proof uses backward induction to show that each frontier exactly represents finite return laws achievable by deterministic continuation policies. Consequently, at the root, the algorithm optimizes the buffered-quantile objective over all deterministic-policy return laws for the fixed model P.

  • Inductive characterization: Backward induction establishes that each frontier contains exactly the finite return laws achievable from a state and stage under deterministic continuation policies, with generating-policy labels.The induction starts from the terminal stage and proceeds through observed next states and their continuation policies.
  • Inductive characterization: At stage H, no reward remains, so the only achievable return law is the point mass δ0.This supplies the base case for the backward induction.
  • Inductive characterization: The induction step represents a policy by its stored action and, after each observed next state, the labeled continuation policy generating the corresponding return law.Thus, the frontier construction captures the return laws generated by deterministic policies at the preceding stage.
  • Root optimization: At the root state and stage, the algorithm maximizes Q_β^τ(D) over exactly all return laws achievable under deterministic policies for fixed model P.This follows by applying the frontier characterization at h = 0 and the initial state.

Proof of Corollary 1

The proof uses a logarithmic schedule, β_{T−1} = τ log(e+T−1), and bounds the cumulative β-weighted term by 2HKτ. Substituting these bounds into Theorem 1 completes the proof.

  • Proof of Corollary 1: β_{T−1} = τ log(e+T−1) follows from the logarithmic schedule.The passage also states that 1/β_{T−1} = log(e+T−1).
  • Proof of Corollary 1: 2HKτ bounds the cumulative term Σ_{t=0}^{T−1} Δ_{β_t}.The proof states 2 Σ_{t=0}^{T−1} Δ_{β_t} ≤ 2HKτ.
  • Proof of Corollary 1: Substituting the two established bounds into Theorem 1 completes the proof.The passage explicitly concludes the argument with a proof-completion statement.

Technical Lemmas

The technical lemmas establish confidence-set validity, concentration, buffered-quantile stability, and return-law perturbation control. Together, they provide the probabilistic and analytical ingredients for the regret analysis, including bounded buffering costs.

  • Confidence and concentration: Lemma 1 establishes high-probability containment of the true transition kernel and the returned optimistic model in the episode-wise confidence sets.The argument uses a union bound over episodes, stages, and state–action pairs.
  • Confidence and concentration: Lemma 2 provides an ℓ1 concentration inequality for empirical transition distributions using a sign-vector representation, Hoeffding’s inequality, and a union bound.The bound controls the probability that the empirical and true distributions differ by at least ε in ℓ1 distance.
  • Buffered optimism: The buffered optimistic decomposition compares the optimal true model-policy value with the optimistic buffered-planning value under confidence-set feasibility.The proof bounds bracketed error terms by Δβ_t and uses feasibility of (P★, π★) for the optimistic problem.
  • Buffered-quantile sensitivity: Buffered quantiles are Lipschitz with respect to W1 because their defining quantile average is bounded by the full integral of quantile differences.The proof uses the one-dimensional quantile representation of W1 for probability measures supported on [0, H].
  • Return-law perturbation: A maximal coupling bounds return-law changes for a fixed induced policy by tracking the first transition mismatch between two kernels.Before mismatch trajectories coincide; after a mismatch at stage h, reward differences can arise only during the remaining H−h−1 stages.
  • Buffering cost: Δβ_t = 0 for all t ≥ Kτ under the logarithmic buffer schedule β_t = τ log(e+t), yielding a constant cumulative buffering cost.The threshold Kτ is determined by the root-level left-plateau threshold ρτ.
Loading 2608.22227v1…