Online Policy Evaluation for MDPs with Dynamic UBSR Measures

# Online Policy Evaluation for MDPs with Dynamic UBSR Measures
Source: [https://arxiv.org/html/2607.23030](https://arxiv.org/html/2607.23030)
Weikai Wang Erick DelageGERAD & Department of Decision Sciences, HEC Montréal, Canada \(weikai\.wang@hec\.ca\)GERAD & Department of Decision Sciences, HEC Montréal, Canada \(erick\.delage@hec\.ca\)

###### Abstract

Developing efficient function\-approximation methods for policy evaluation is a fundamental challenge in risk\-aware reinforcement learning\. Existing approaches either focus on restrictive classes of risk measures or rely on access to a simulator, limiting their applicability in fully online settings\. In this work, we propose computationally efficient online learning algorithms for policy evaluation in Markov decision processes \(MDPs\) with dynamic utility\-based shortfall risk \(UBSR\) measures under linear function approximation\. Specifically, we introduce the UBSR\-TD algorithm, establish conditions under which it converges almost surely, and develop several variants designed to accelerate convergence\. Our formulation shows that existing policy evaluation algorithms for risk\-neutral MDPs can be readily adapted to dynamic UBSR settings by incorporating a loss function into the temporal\-difference error\. Numerical experiments support our theoretical findings, and an application to a perishable inventory management problem with shelf\-life uncertainty demonstrates the practical effectiveness of the proposed methods\.

## 1Introduction

From AlphaGo defeating the world champion of Go\(Silveret al\.,[2017](https://arxiv.org/html/2607.23030#bib.bib15)\)to the fine tuning of large language models\(Ouyanget al\.,[2022](https://arxiv.org/html/2607.23030#bib.bib109)\), reinforcement learning \(RL\) has achieved remarkable successes\. A central component of RL is policy evaluation, which corresponds to assessing a given policy on a Markov decision process \(MDP\) and whose accuracy directly influences the effectiveness of subsequent policy improvement\. In theory, policy evaluation can be achieved using classical value iteration methods from dynamic programming \(DP\)\. In practice, however, the environment is rarely known in full, data collection may be costly or limited, and the curse of dimensionality often renders exact DP methods computationally infeasible\. These challenges have motivated efficient function approximation methods for estimating value functions from streaming or limited data, including temporal\-difference \(TD\)\-type algorithms\(Sutton and Barto,[2018](https://arxiv.org/html/2607.23030#bib.bib16)\)\.

The classical policy evaluation methods optimize the expected cumulative discounted cost and therefore implicitly assume that the decision\-maker is risk\-neutral\. In real\-world environments, however, policies may lead to severe adverse outcomes, particularly in high\-stakes fields such as finance, autonomous driving, and robotics\(Wang and Chapman,[2022](https://arxiv.org/html/2607.23030#bib.bib23)\), etc\. The need to limit exposure to such outcomes has motivated the development of risk\-aware RL methods, which incorporate risk measures into their objectives, statically or dynamically\. Following the seminal framework ofArtzneret al\.\([1999](https://arxiv.org/html/2607.23030#bib.bib18)\), much of the literature has focused on the entropic risk measure \(ERM\) and coherent risk measures, largely because of their analytical tractability\(Tamaret al\.,[2015](https://arxiv.org/html/2607.23030#bib.bib107); Feiet al\.,[2021](https://arxiv.org/html/2607.23030#bib.bib116); Lamet al\.,[2022](https://arxiv.org/html/2607.23030#bib.bib34); Zhanget al\.,[2024](https://arxiv.org/html/2607.23030#bib.bib110)\)\.

Despite these progresses, more general classes of risk measures remain relatively underexplored, limiting the capability of existing approaches in settings where the decision\-maker seeks to capture diverse risk preferences through customized loss functions\. In this context, utility\-based shortfall risk \(UBSR\) has attracted increasing interest because of its flexibility\. Defined in terms of a general loss function and a prescribed acceptability threshold, UBSR quantifies the minimum amount of additional capital required to reduce risk to an acceptable level\(Föllmer and Schied,[2016](https://arxiv.org/html/2607.23030#bib.bib44)\)\. This general formulation includes both the expectation and the ERM as special cases\. Empirical evidence also suggests that UBSR can effectively capture the heterogeneous risk preferences observed in human behavior\(Shenet al\.,[2014](https://arxiv.org/html/2607.23030#bib.bib3)\)\. Moreover, UBSR is well suited to modeling extreme losses and is the only convex risk measure that is elicitable, a property of particular importance for backtesting\(Bellini and Bignozzi,[2015](https://arxiv.org/html/2607.23030#bib.bib4)\)\.

While possessing several attractive properties, UBSR has received relatively limited attention in RL, partly because its general lack of coherence gives rise to substantial analytical difficulties\. Several studies have considered function approximation methods for MDPs with general dynamic risk measures\(Tamaret al\.,[2015](https://arxiv.org/html/2607.23030#bib.bib107); Yuet al\.,[2018](https://arxiv.org/html/2607.23030#bib.bib43); Köse and Ruszczyński,[2021](https://arxiv.org/html/2607.23030#bib.bib28); Coache and Jaimungal,[2024](https://arxiv.org/html/2607.23030#bib.bib11)\)\. However, these approaches typically require a sampling oracle to evaluate the risk measure and therefore are not applicable in an online setting\. Other methods estimate risk using online mini\-batches or episodic trajectories\(Huanget al\.,[2021](https://arxiv.org/html/2607.23030#bib.bib114); Marzbanet al\.,[2023](https://arxiv.org/html/2607.23030#bib.bib24); Coacheet al\.,[2023](https://arxiv.org/html/2607.23030#bib.bib25); Luo and Delage,[2026](https://arxiv.org/html/2607.23030#bib.bib112)\), but their convergence is not guaranteed\. For dynamic UBSR specifically,Shenet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib3)\)develops an online Q\-learning algorithm, but its function approximation version remains missing\. To the best of our knowledge, two questions remain open for RL with dynamic risk measures under function approximation: how to perform fully online policy evaluation and whether the resulting algorithm can be shown to converge almost surely\.Basuet al\.\([2008](https://arxiv.org/html/2607.23030#bib.bib113)\)resolves both for the average\-ERM criterion, but under a formulation outside the discounted MDP setting considered here\.

Motivated by this gap, this work aims to develop fully online policy evaluation algorithms for MDPs with dynamic UBSR under linear function approximation and establish their almost\-sure convergence\. Our contributions can be described as follows:

- •We develop UBSR\-TD, the first fully online policy evaluation algorithm for MDPs with dynamic UBSR under linear function approximation\. The method can be viewed as a natural extension of classical TD\(0\) to general loss functions\. We show that UBSR\-TD solves the fixed point of a projected risk\-aware Bellman equation and establish its almost\-sure convergence under suitable conditions\. As far as we are aware, this is the first almost\-sure convergence result for fully online policy evaluation in discounted MDPs with dynamic risk measures\.
- •TD\-type algorithms can converge slowly without careful hyperparameter tuning\(Sutton and Barto,[2018](https://arxiv.org/html/2607.23030#bib.bib16)\)\. To mitigate this issue, we introduce two extensions of UBSR\-TD that leverage historical and gradient information\. We evaluate the proposed methods numerically across different risks and parameter settings\. The results show that these variants can improve convergence over a broad range of scenarios\. Our formulations indicate that existing policy evaluation algorithms can be easily adapted to the dynamic UBSR framework by incorporating a loss function into the TD error\.
- •We further apply our method to perishable inventory management with both demand and product shelf\-life uncertainty, a growing field that has only been examined under risk neutrality\(Nahmias,[2011](https://arxiv.org/html/2607.23030#bib.bib86); Buet al\.,[2023](https://arxiv.org/html/2607.23030#bib.bib99); Abouee\-Mehriziet al\.,[2026](https://arxiv.org/html/2607.23030#bib.bib85)\)\. Existing risk\-aware models employ conditional Value\-at\-Risk or ERM as risk measures\(Feng and Xiao,[2008](https://arxiv.org/html/2607.23030#bib.bib102); Yalçındağet al\.,[2020](https://arxiv.org/html/2607.23030#bib.bib104); Pathy and Rahimian,[2024](https://arxiv.org/html/2607.23030#bib.bib103)\), but do not account for shelf\-life uncertainty\. We formulate an approximate dynamic programming model under dynamic UBSR and employ our proposed policy evaluation algorithms within a policy iteration scheme\. Numerical experiments show that our approach consistently outperforms static, myopic, and risk\-neutral benchmarks across diverse scenarios, highlighting the value of risk\-aware decision\-making\.

The remainder of the paper is organized as follows\. Section[2](https://arxiv.org/html/2607.23030#S2)introduces the basic definitions and formulates the policy evaluation problem for risk\-aware MDPs under dynamic UBSR\. Section[3](https://arxiv.org/html/2607.23030#S3)presents the UBSR\-TD algorithm, while Section[4](https://arxiv.org/html/2607.23030#S4)provides its convergence analysis\. Section[5](https://arxiv.org/html/2607.23030#S5)introduces extensions of UBSR\-TD designed to accelerate convergence\. Section[6](https://arxiv.org/html/2607.23030#S6)reports numerical experiments on algorithmic convergence and presents an application to a perishable inventory management problem\. Finally, Section[7](https://arxiv.org/html/2607.23030#S7)concludes the paper and discusses future research directions\.

## 2Preliminaries

Notations:Let\(Ω,\\mcF,\\mbP\)\(\\Omega,\\mcF,\\mbP\)be a finite probability space, whereΩ\\Omegais the finite sample space,\\mcF:=2\|Ω\|\\mcF:=2^\{\|\\Omega\|\}is aσ\\sigma\-algebra onΩ\\Omega, and\\mbP\\mbPis a probability measure on\(Ω,\\mcF\)\(\\Omega,\\mcF\)\. Let\\mcL​\(Ω\)\\mcL\(\\Omega\)denote the space of all real\-valued measurable functions on\(Ω,\\mcF,\\mbP\)\(\\Omega,\\mcF,\\mbP\)\. ForX,Y∈\\mcL​\(Ω\)X,Y\\in\\mcL\(\\Omega\), we writeX≥YX\\geq YifX​\(ω\)≥Y​\(ω\)X\(\\omega\)\\geq Y\(\\omega\), for allω∈Ω\\omega\\in\\Omegaand we sayX≥YX\\geq Yalmost surely \(a\.s\.\) ifX​\(ω\)≥Y​\(ω\)X\(\\omega\)\\geq Y\(\\omega\)for allω∈Ω\\omega\\in\\Omegasuch that\\mbP​\(ω\)\>0\\mbP\(\\omega\)\>0\.

### 2\.1Risk Measures

FollowingShapiroet al\.\([2021](https://arxiv.org/html/2607.23030#bib.bib73)\), given a finite probability space\(Ω,\\mcF,\\mbP\)\(\\Omega,\\mcF,\\mbP\), a risk measure is a mappingρ:\\mcL​\(Ω\)→\\mbR\\rho:\\mcL\(\\Omega\)\\to\\mbR\. Consider the following properties:

1. \(a\)\(Monotonicity\)ρ​\(X\)≥ρ​\(Y\)\\rho\(X\)\\geq\\rho\(Y\)for allX,Y∈\\mcL​\(Ω\)X,Y\\in\\mcL\(\\Omega\)such thatX≥YX\\geq Ya\.s\.;
2. \(b\)\(Translation invariance\)ρ​\(X\+λ\)=ρ​\(X\)\+λ\\rho\(X\+\\lambda\)=\\rho\(X\)\+\\lambdafor anyλ∈\\mbR\\lambda\\in\\mbR,X∈\\mcL​\(Ω\)X\\in\\mcL\(\\Omega\);
3. \(c\)\(Normalization\)ρ​\(0\)=0\\rho\(0\)=0;
4. \(d\)\(Convexity\) For allα∈\[0,1\]\\alpha\\in\[0,1\],X,Y∈\\mcL​\(Ω\)X,Y\\in\\mcL\(\\Omega\),ρ​\(α​X\+\(1−α\)​Y\)≤α​ρ​\(X\)\+\(1−α\)​ρ​\(Y\)\\rho\(\\alpha X\+\(1\-\\alpha\)Y\)\\leq\\alpha\\rho\(X\)\+\(1\-\\alpha\)\\rho\(Y\);
5. \(e\)\(Positive homogeneity\) For allλ≥0\\lambda\\geq 0,X∈\\mcL​\(Ω\)X\\in\\mcL\(\\Omega\),ρ​\(λ​X\)=λ​ρ​\(X\)\\rho\(\\lambda X\)=\\lambda\\rho\(X\)\.

A risk measure is called monetary if it satisfies properties \(a\)\-\(c\)\. It is called convex if it additionally satisfies \(d\), and coherent if it further satisfies \(e\)\.

We now introduce a special class of risk measures that possesses many desirable properties\.

###### Definition 2\.1\.

A risk measure on\(Ω,\\mcF,\\mbP\)\(\\Omega,\\mcF,\\mbP\)is called a utility\-based shortfall risk \(UBSR\) measure if it can be represented as:

\\SR​\(X\):=inf\{m∈\\mbR:\\mbE​\[ℓ​\(X−m\)\]≤0\},∀X∈\\mcL​\(Ω\),\\SR\(X\):=\\inf\\left\\\{m\\in\\mbR:\\mbE\[\\ell\(X\-m\)\]\\leq 0\\right\\\},\\quad\\forall X\\in\\mcL\(\\Omega\),for some continuous strictly increasing loss functionℓ:\\mbR→\\mbR\\ell:\\mbR\\to\\mbRsuch thatℓ​\(0\)=0\\ell\(0\)=0\.

Note that the original definition of UBSR inFöllmer and Schied \([2016](https://arxiv.org/html/2607.23030#bib.bib44)\)is limited to convex loss functions\. Here, we adopt the more general definition fromShenet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib3)\), which allows for a broader class of loss functions and, consequently, a wider class of risk measures\.

The following examples show that a lot of popular risk measures are special cases of UBSR\.

###### Example 2\.2\(Expected value\)\.

The expectation corresponds to the UBSR induced byℓ​\(x\)=x\\ell\(x\)=x, which we refer to as the risk\-neutral measure\.

###### Example 2\.3\(Expectile\)\.

The expectile is the only coherent UBSR\(Bellini and Bignozzi,[2015](https://arxiv.org/html/2607.23030#bib.bib4)\)\. It is induced by the loss functionℓEXP​\(x\):=τ​x\+−\(1−τ\)​x−\\ell\_\{\\mathrm\{EXP\}\}\(x\):=\\tau x^\{\+\}\-\(1\-\\tau\)x^\{\-\}, whereτ∈\[0,1\]\\tau\\in\[0,1\]controls risk aversion\. Asτ\\tauincreases from0to11, the expectile ranges from the essential infimum to the essential supremum of the random variable, with the expectation recovered atτ=0\.5\\tau=0\.5\.

###### Example 2\.4\(Entropic risk measure\)\.

The ERMρERM​\(X\):=1β​log⁡\(\\mbE​\[eβ​X\]\)\\rho\_\{\\mathrm\{ERM\}\}\(X\):=\\frac\{1\}\{\\beta\}\\log\(\\mbE\[\\mathrm\{e\}^\{\\beta X\}\]\)is a UBSR with loss functionℓERM​\(x\)=eβ​x−1\\ell\_\{\\mathrm\{ERM\}\}\(x\)=\\mathrm\{e\}^\{\\beta x\}\-1, withβ\>0\\beta\>0representing risk sensitivity\.

###### Example 2\.5\(Soft quantile\)\.

The soft quantile risk measure introduced inHauet al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib74)\)approximates the quantile risk measure while addressing the discontinuity and zero\-slope issues of the quantile loss\. It is defined through the loss function

ℓSQ​\(x\):=\{\(1−μ\)​\(κ​x\+κ2−1\),x<−κ,1−μκ​x,−κ≤x<0,μκ​x,0≤x<κ,μ​\(κ​x−κ2\+1\),x≥κ,\\displaystyle\\ell\_\{\\mathrm\{SQ\}\}\(x\)=withμ∈\(0,1\)\\mu\\in\(0,1\)serving as the risk level andκ\>0\\kappa\>0as the slope parameter\. Unlike the quantile loss, the soft quantile loss is continuous and strictly increasing\.

It is known that UBSR is elicitable, and it can be elicited by the scoring functionψ​\(y−z\)\\psi\(y\-z\)withψ​\(z\):=∫0zℓ​\(τ\)​𝑑τ\\psi\(z\):=\\int\_\{0\}^\{z\}\\ell\(\\tau\)d\\tau, \(see Theorem 4\.6,Bellini and Bignozzi \([2015](https://arxiv.org/html/2607.23030#bib.bib4)\)\), and\\SR​\(Y\)\\SR\(Y\)is the unique minimizer of the expected scoring function, namely,

\\SR​\(Y\)=\\argminz∈\\mbR​\\mbE​\[ψ​\(Y−z\)\]\.\\SR\(Y\)=\\argmin\_\{z\\in\\mbR\}\\mbE\[\\psi\(Y\-z\)\]\.\(1\)By the fundamental theorem of calculus,ψ​\(z\)\\psi\(z\)is differentiable andψ′​\(y\)=ℓ​\(y\)\\psi^\{\\prime\}\(y\)=\\ell\(y\), for ally∈\\mbRy\\in\\mbR\. FromEmmeret al\.\([2015](https://arxiv.org/html/2607.23030#bib.bib31)\), we know that ifψ\\psiis the squared error, then the minimizer is the expectation\.

As a summary for the properties of UBSR, we state as the following proposition\.

###### Proposition 2\.6\(Theorem 4\.113 inFöllmer and Schied \([2016](https://arxiv.org/html/2607.23030#bib.bib44)\)\)\.

For the UBSR measure defined in Definition[2\.1](https://arxiv.org/html/2607.23030#S2.Thmtheorem1), the following statements are equivalent: for any finite real\-valued random variableYY, we have \(i\)\\SR​\(Y\)=m∗\\SR\(Y\)=m^\{\*\}and \(ii\)\\mbE​\[ℓ​\(Y−m∗\)\]=0\\mbE\[\\ell\(Y\-m^\{\*\}\)\]=0\.

### 2\.2Risk\-aware MDPs

Consider an MDP\(\\mcX,\\mcA,P,c,γ\)\(\\mcX,\\mcA,P,c,\\gamma\), where\\mcX=\{1,…,N\}\\mcX=\\\{1,\\ldots,N\\\}and\\mcA\\mcAare finite state and action spaces,PPis the transition kernel,ccis the cost function, andγ∈\(0,1\)\\gamma\\in\(0,1\)is the discount factor\. A policyπ​\(a\|x\)\\pi\(a\|x\)specifies the probability of selecting actionaain statexx\. We focus on non\-anticipative policies with deterministic control, so thatπ\(⋅\|x\)\\pi\(\\cdot\|x\)is a Dirac measure for eachxx\. Underπ\\pi, the induced transition kernel isPπ​\(x′\|x\):=∑a∈\\mcAP​\(x′\|x,a\)​π​\(a\|x\)P^\{\\pi\}\(x^\{\\prime\}\|x\):=\\sum\_\{a\\in\\mcA\}P\(x^\{\\prime\}\|x,a\)\\pi\(a\|x\)forx,x′∈\\mcXx,x^\{\\prime\}\\in\\mcX, and the induced cost function iscπ​\(x\):=∑a∈\\mcAc​\(x,a\)​π​\(a\|x\)c^\{\\pi\}\(x\):=\\sum\_\{a\\in\\mcA\}c\(x,a\)\\pi\(a\|x\)forx∈\\mcXx\\in\\mcX, which is assumed bounded:maxx∈\\mcX⁡\|cπ​\(x\)\|≤c¯\\max\_\{x\\in\\mcX\}\|c^\{\\pi\}\(x\)\|\\leq\\bar\{c\}\. Since we study policy evaluation under a fixed policy, we omit the superscriptπ\\piand writePPandccfor the policy\-induced transition kernel and cost function\.

In the risk\-neutral policy evaluation setting, the objective is to evaluate the discounted cumulative costV¯\\bar\{V\}under a fixed policyπ\\pi:

V¯​\(x\):=\\mbE​\[∑n=0∞γn​c​\(Xn\)∣X0=x\],∀x∈\\mcX,\\bar\{V\}\(x\):=\\mbE\\left\[\\sum\_\{n=0\}^\{\\infty\}\\gamma^\{n\}c\(X\_\{n\}\)\\mid X\_\{0\}=x\\right\],\\quad\\forall x\\in\\mcX,\(2\)whereγ∈\(0,1\)\\gamma\\in\(0,1\)is some discount factor and\{Xn\}n≥0\\\{X\_\{n\}\\\}\_\{n\\geq 0\}represents the state trajectory, typically modeled as a Markov chain such thatXn\+1∼P\(⋅\|Xn\)X\_\{n\+1\}\\sim P\(\\cdot\|X\_\{n\}\)forn≥0n\\geq 0\.

To incorporate risk into an MDP, we adopt the dynamic risk measure ofRuszczyński \([2010](https://arxiv.org/html/2607.23030#bib.bib35)\), which recursively evaluates future random costs through nested mappings\. This structure ensures time consistency and yields a risk\-aware Bellman equation for the optimal cumulative risk\. To formulate the problem, we first introduce the notion of a risk map\.

###### Definition 2\.7\(Definition 3\.1,Shenet al\.\([2013](https://arxiv.org/html/2607.23030#bib.bib5)\)\)\.

A mapping\\mcR:\\mcX×\\mcL​\(\\mcX\)→\\mbR\\mcR:\\mcX\\times\\mcL\(\\mcX\)\\to\\mbRis said to be a risk map on the Markov chainPPif

1. \(i\)for eachx∈\\mcXx\\in\\mcX,\\mcRx​\(⋅\):=\\mcR​\(x,⋅\)\\mcR\_\{x\}\(\\cdot\):=\\mcR\(x,\\cdot\)is a risk measure;
2. \(ii\)\\mcR​\(⋅,Y\)∈\\mcL​\(\\mcX\)\\mcR\(\\cdot,Y\)\\in\\mcL\(\\mcX\)for eachY∈\\mcL​\(\\mcX\)Y\\in\\mcL\(\\mcX\)\.

The above definition guarantees that the risk map depends solely on the current statexx, which is referred to as a Markovian risk map inShenet al\.\([2013](https://arxiv.org/html/2607.23030#bib.bib5)\)\. Such a Markovian risk map ensures that the optimal policy remains stationary in infinite\-horizon settings\.

Throughout this work, we restrict our attention to the case where\\mcRx​\(⋅\)\\mcR\_\{x\}\(\\cdot\)is a UBSR measure\. For notation simplicity, we denote it by\\SRx​\(⋅\)\\SR\_\{x\}\(\\cdot\)\. Then for any fixed stageT\>0T\>0, the discountedTT\-stage total risk under policyπ\\piis defined as

VT​\(x\):=c​\(x\)\+γ​\\SRx0​\(c​\(X1\)\+γ​\\SRX1​\(c​\(X2\)\+⋯\+γ​\\SRXT−1​\(c​\(XT\)\)​⋯\)\),∀x∈\\mcX\.V\_\{T\}\(x\):=c\(x\)\+\\gamma\\SR\_\{x\_\{0\}\}\\left\(c\(X\_\{1\}\)\+\\gamma\\SR\_\{X\_\{1\}\}\(c\(X\_\{2\}\)\+\\cdots\+\\gamma\\SR\_\{X\_\{T\-1\}\}\(c\(X\_\{T\}\)\)\\cdots\)\\right\),\\quad\\forall x\\in\\mcX\.LettingT→∞T\\to\\infty, we obtain the infinite\-horizon discounted total risk under policyπ\\pias

V​\(x\):=limT→∞VT​\(x\),∀x∈\\mcX\.V\(x\):=\\lim\_\{T\\to\\infty\}V\_\{T\}\(x\),\\quad\\forall x\\in\\mcX\.\(3\)Under certain conditions, the limit in \([3](https://arxiv.org/html/2607.23030#S2.E3)\) exists for risk maps induced by the UBSR \(see Lemma 5\.3 and Theorem 5\.5 inShenet al\.\([2013](https://arxiv.org/html/2607.23030#bib.bib5)\)\)\. Furthermore, this results in the following risk\-aware Bellman equation under policyπ\\pi:

V​\(x\)=\\SRx​\(c​\(x\)\+γ​V​\(X′\)\),∀x∈\\mcX,V\(x\)=\\SR\_\{x\}\(c\(x\)\+\\gamma V\(X^\{\\prime\}\)\),\\quad\\forall x\\in\\mcX,\(4\)withX′∼P\(⋅\|x\)X^\{\\prime\}\\sim P\(\\cdot\|x\), andVVas the unique solution\.

### 2\.3Policy Evaluation with Function Approximation in the Risk\-neutral Case

In practical RL problems, the state space may be too large to compute value estimates explicitly for each state in\\mcX\\mcX\. A standard approach is to approximate the objective functionVVusing a linear function approximation based on a set of basis functions:

V\\bmtheta​\(x\):=\\bmtheta⊤​\\bmphi​\(x\)=∑i=1dθi​ϕi​\(x\),∀x∈\\mcX,V\_\{\\bmtheta\}\(x\):=\\bmtheta^\{\\top\}\\bmphi\(x\)=\\sum\_\{i=1\}^\{d\}\\theta\_\{i\}\\phi\_\{i\}\(x\),\\quad\\forall x\\in\\mcX,where\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}is the parameter vector and\\bmphi:\\mcX→\\mbRd\\bmphi:\\mcX\\to\\mbR^\{d\}is a feature mapping\. For eachi∈\{1,…,d\}i\\in\\\{1,\\ldots,d\\\}, define\\bmphii:=\(ϕi​\(1\),…,ϕi​\(N\)\)⊤∈\\mbRN\\bmphi\_\{i\}:=\(\\phi\_\{i\}\(1\),\\ldots,\\phi\_\{i\}\(N\)\)^\{\\top\}\\in\\mbR^\{N\}, which will be referred as basis vectors in\\mbRN\\mbR^\{N\}\. We assume that the collection\{\\bmphii\}i=1d\\\{\\bmphi\_\{i\}\\\}\_\{i=1\}^\{d\}is linearly independent, and let\\bmPhi:=\[\\bmphi1​⋯​\\bmphid\]∈\\mbRN×d\\bmPhi:=\[\\bmphi\_\{1\}\\ \\cdots\\ \\bmphi\_\{d\}\]\\in\\mbR^\{N\\times d\}denote the feature matrix\. Whend=Nd=N, exact representation ofVVover\\bmPhi\\bmPhiis possible\. In practice, however, computational considerations typically motivate the regimed≪Nd\\ll N, whereVVis approximated via a low\-dimensional linear representationV\\bmthetaV\_\{\\bmtheta\}\.

For the risk\-neutral formulation \([2](https://arxiv.org/html/2607.23030#S2.E2)\), the value functionV¯\\bar\{V\}satisfies the Bellman equation

\\mbE​\[γ​V¯​\(X′\)−V¯​\(X\)\+c​\(X\)∣X=x\]=0,∀x∈\\mcX,\\mbE\\left\[\\gamma\\bar\{V\}\(X^\{\\prime\}\)\-\\bar\{V\}\(X\)\+c\(X\)\\mid X=x\\right\]=0,\\quad\\forall x\\in\\mcX,whereX′∼P\(⋅\|x\)X^\{\\prime\}\\sim P\(\\cdot\|x\)\. However, this identity generally cannot be satisfied whenV¯\\bar\{V\}is replaced by its linear approximationV\\bmthetaV\_\{\\bmtheta\}, since the Bellman operator does not preserve the linear function class\.

The classical TD\(0\) algorithm\(Sutton and Barto,[2018](https://arxiv.org/html/2607.23030#bib.bib16)\)aims to find a parameter\\bmtheta¯\\bar\{\\bmtheta\}such thatV\\bmtheta¯V\_\{\\bar\{\\bmtheta\}\}well approximates the value functionV¯\\bar\{V\}\. The update rule is given by

\\bmthetan\+1=\\bmthetan\+ηn​\\bmphi​\(Xn\)​\[\(γ​\\bmphi​\(Xn\+1\)−\\bmphi​\(Xn\)\)⊤​\\bmthetan\+c​\(Xn\)\],n≥0,\\bmtheta\_\{n\+1\}=\\bmtheta\_\{n\}\+\\eta\_\{n\}\\bmphi\(X\_\{n\}\)\\left\[\(\\gamma\\bmphi\(X\_\{n\+1\}\)\-\\bmphi\(X\_\{n\}\)\)^\{\\top\}\\bmtheta\_\{n\}\+c\(X\_\{n\}\)\\right\],\\quad n\\geq 0,\(5\)whereηn\\eta\_\{n\}is some step size and\{Xn\}n≥0\\\{X\_\{n\}\\\}\_\{n\\geq 0\}is the state trajectory driven by the Markov chainPP\.

TD\(0\) is known as a semi\-gradient method\(Sutton and Barto,[2018](https://arxiv.org/html/2607.23030#bib.bib16)\)\. Its update direction is given bygn​\(\\bmtheta\):=\(yn−V\\bmtheta​\(Xn\)\)​∇\\bmthetaV\\bmtheta​\(Xn\)g\_\{n\}\(\\bmtheta\):=\(y\_\{n\}\-V\_\{\\bmtheta\}\(X\_\{n\}\)\)\\nabla\_\{\\bmtheta\}V\_\{\\bmtheta\}\(X\_\{n\}\), whereyn:=c​\(Xn\)\+γ​V\\bmthetan​\(Xn\+1\)y\_\{n\}:=c\(X\_\{n\}\)\+\\gamma V\_\{\\bmtheta\_\{n\}\}\(X\_\{n\+1\}\)is a sample\-based estimate of the Bellman update forV\\bmthetanV\_\{\\bmtheta\_\{n\}\}\. The directiongn​\(\\bmthetan\)g\_\{n\}\(\\bmtheta\_\{n\}\)is often referred to as the negative semi\-gradient of a certain squared loss function, sincegn​\(\\bmthetan\)=−∇\\bmtheta12​\(yn−V\\bmtheta​\(Xn\)\)2\|\\bmtheta=\\bmthetang\_\{n\}\(\\bmtheta\_\{n\}\)=\-\\nabla\_\{\\bmtheta\}\\frac\{1\}\{2\}\(y\_\{n\}\-V\_\{\\bmtheta\}\(X\_\{n\}\)\)^\{2\}\|\_\{\\bmtheta=\\bmtheta\_\{n\}\}, where the targetyny\_\{n\}is treated as fixed, ignoring its implicit dependence on\\bmthetan\\bmtheta\_\{n\}\. Suppose the Markov chainPPis ergodic with the vector of stationary distribution denoted asqq, the iterates\\bmthetan\\bmtheta\_\{n\}converges almost surely to a parameter\\bmtheta¯\\bar\{\\bmtheta\}that is the solution to the following root\-finding problem :

\\mbE​\[\\bmphi​\(X\)​\(\(γ​\\bmphi​\(X′\)−\\bmphi​\(X\)\)⊤​\\bmtheta¯\+c​\(X\)\)\]=𝟎,\\mbE\\left\[\\bmphi\(X\)\\left\(\(\\gamma\\bmphi\(X^\{\\prime\}\)\-\\bmphi\(X\)\)^\{\\top\}\\bar\{\\bmtheta\}\+c\(X\)\\right\)\\right\]=\\bm\{0\},\(6\)whereX∼qX\\sim q, andX′∼P\(⋅\|X\)X^\{\\prime\}\\sim P\(\\cdot\|X\)\.

It turns out that, such\\bmtheta¯\\bar\{\\bmtheta\}is a fixed point for the projected Bellman equation and minimizes the mean squared projected Bellman error\. We refer readers toDannet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib42)\)for further discussion on policy evaluation algorithms in the risk\-neutral case\.

## 3UBSR\-TD Algorithm

Motivated by the risk\-neutral setting, we consider a linear function approximation of the risk\-aware objective in \([3](https://arxiv.org/html/2607.23030#S2.E3)\)\. Our goal is to develop an online algorithm for finding a parameter\\bmtheta∗\\bmtheta^\{\*\}such thatV\\bmtheta∗V\_\{\\bmtheta^\{\*\}\}is a good approximation toVV\. In this section, we first present a stochastic value iteration algorithm for solving \([4](https://arxiv.org/html/2607.23030#S2.E4)\), then derive its linear function approximation based on the semi\-gradient method\.

SupposeVVis a solution to \([4](https://arxiv.org/html/2607.23030#S2.E4)\), then by Proposition[2\.6](https://arxiv.org/html/2607.23030#S2.Thmtheorem6), we know thatVVis a unique solution to the root finding problem

\\mbE​\[ℓ​\(c​\(X\)\+γ​V​\(X′\)−V​\(X\)\)∣X=x\]=0,∀x∈\\mcX\.\\mbE\\left\[\\ell\\left\(c\(X\)\+\\gamma V\(X^\{\\prime\}\)\-V\(X\)\\right\)\\mid X=x\\right\]=0,\\quad\\forall x\\in\\mcX\.\(7\)FollowingShenet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib3)\), it can be solved using the following stochastic approximation iteration:

Vn\+1\(x\)=Vn\(x\)\+ηnℓ\(c\(x\)\+γVn\(X′\)−Vn\(x\)\),∀x∈\\mcX,X′∼P\(⋅\|x\),V\_\{n\+1\}\(x\)=V\_\{n\}\(x\)\+\\eta\_\{n\}\\ell\\left\(c\(x\)\+\\gamma V\_\{n\}\(X^\{\\prime\}\)\-V\_\{n\}\(x\)\\right\),\\quad\\forall x\\in\\mcX,X^\{\\prime\}\\sim P\(\\cdot\|x\),\(8\)whereηn\\eta\_\{n\}is some step size\. Algorithm \([8](https://arxiv.org/html/2607.23030#S3.E8)\) can be interpreted as the policy\-evaluation counterpart of the synchronous version of the Q\-learning algorithm proposed inShenet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib3)\)\. Its almost sure convergence to the target value functionVVfollows from an analogous argument to that used in Theorem 3\.2 ofShenet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib3)\)\. An asynchronous variant can be derived similarly\.

Algorithm \([8](https://arxiv.org/html/2607.23030#S3.E8)\) is value\-function based and thus suffers from the curse of dimensionality when the state space is large\. We next heuristically derive its linear function approximation counterpart, with a rigorous convergence analysis provided in Section[4](https://arxiv.org/html/2607.23030#S4)\.

From \([1](https://arxiv.org/html/2607.23030#S2.E1)\), we replace the unknown value functionVVin \([4](https://arxiv.org/html/2607.23030#S2.E4)\) by its linear function approximationV\\bmthetaV\_\{\\bmtheta\}and define the sample\-based targety:=c​\(X\)\+γ​V\\bmtheta​\(X′\)y:=c\(X\)\+\\gamma V\_\{\\bmtheta\}\(X^\{\\prime\}\)\. Following the semi\-gradient principle, we treatyyas fixed when differentiating with respect to\\bmtheta\\bmtheta\. This leads to the surrogate minimization objective\\mbE​\[ψ​\(y−V\\bmtheta​\(X\)\)\]\\mbE\[\\psi\(y\-V\_\{\\bmtheta\}\(X\)\)\], where we average over the stationary distribution ofXXto obtain a single state\-independent parameter\\bmtheta∗\\bmtheta^\{\*\}\. Sinceψ\\psiis differentiable with derivativeℓ=ψ′\\ell=\\psi^\{\\prime\}, the corresponding first\-order condition is

\\mbE​\[ℓ​\(y−V\\bmtheta∗​\(X\)\)​∇\\bmthetaV\\bmtheta​\(X\)\|\\bmtheta=\\bmtheta∗\]=𝟎,\\mbE\\left\[\\ell\\left\(y\-V\_\{\\bmtheta^\{\*\}\}\(X\)\\right\)\\nabla\_\{\\bmtheta\}V\_\{\\bmtheta\}\(X\)\|\_\{\\bmtheta=\\bmtheta^\{\*\}\}\\right\]=\\bm\{0\},whereX∼qX\\sim q, andX′∼P\(⋅\|X\)X^\{\\prime\}\\sim P\(\\cdot\|X\)\. For the linear function approximationV\\bmtheta​\(x\)=\\bmtheta⊤​\\bmphi​\(x\)V\_\{\\bmtheta\}\(x\)=\\bmtheta^\{\\top\}\\bmphi\(x\), this condition becomes

\\mbE​\[\\bmphi​\(X\)​ℓ​\(\(γ​\\bmphi​\(X′\)−\\bmphi​\(X\)\)⊤​\\bmtheta∗\+c​\(X\)\)\]=𝟎\.\\mbE\\left\[\\bmphi\(X\)\\ell\\left\(\(\\gamma\\bmphi\(X^\{\\prime\}\)\-\\bmphi\(X\)\)^\{\\top\}\\bmtheta^\{\*\}\+c\(X\)\\right\)\\right\]=\\bm\{0\}\.\(9\)This leads to the following stochastic approximation scheme: given an observed sequence of states\{Xn\}n≥0\\\{X\_\{n\}\\\}\_\{n\\geq 0\}, the parameter\\bmthetan\\bmtheta\_\{n\}is updated recursively according to

\\bmthetan\+1=\\bmthetan\+ηn​\\bmphi​\(Xn\)​ℓ​\(\(γ​\\bmphi​\(Xn\+1\)−\\bmphi​\(Xn\)\)⊤​\\bmthetan\+c​\(Xn\)\),n≥0,\\bmtheta\_\{n\+1\}=\\bmtheta\_\{n\}\+\\eta\_\{n\}\\bmphi\(X\_\{n\}\)\\ell\\left\(\(\\gamma\\bmphi\(X\_\{n\+1\}\)\-\\bmphi\(X\_\{n\}\)\)^\{\\top\}\\bmtheta\_\{n\}\+c\(X\_\{n\}\)\\right\),\\quad n\\geq 0,\(10\)with\\bmtheta0\\bmtheta\_\{0\}arbitrarily initialized\. We call \([10](https://arxiv.org/html/2607.23030#S3.E10)\) theUBSR temporal\-difference \(UBSR\-TD\) algorithm\. Whenℓ\\ellis the identity function, which corresponds toψ\\psibeing the square loss, the UBSR\-TD algorithm \([10](https://arxiv.org/html/2607.23030#S3.E10)\) reduces to the classical TD\(0\) with linear function approximation\.

From the derivation of UBSR\-TD, the algorithm belongs to the semi\-gradient method\. Its update direction isg~n​\(\\bmthetan\)=−∇\\bmthetaψ​\(yn−V\\bmtheta​\(Xn\)\)\|\\bmtheta=\\bmthetan\\tilde\{g\}\_\{n\}\(\\bmtheta\_\{n\}\)=\-\\nabla\_\{\\bmtheta\}\\psi\(y\_\{n\}\-V\_\{\\bmtheta\}\(X\_\{n\}\)\)\|\_\{\\bmtheta=\\bmtheta\_\{n\}\}\. Clearly,g~n\\tilde\{g\}\_\{n\}serves as the general\-loss counterpart of the TD\(0\) update directiongng\_\{n\}\.

## 4Convergence for the UBSR\-TD Algorithm

In this section, we study the convergence of UBSR\-TD\. Since the algorithm updates the feature parameter\\bmtheta\\bmtheta, we first introduce notation linking the value\-function space to the feature space\.

Before proceeding, we assume that the Markov chainPPis ergodic\. This assumption is standard in the RL literature\(Tsitsiklis and Van Roy,[1997](https://arxiv.org/html/2607.23030#bib.bib1); Borkaret al\.,[2025](https://arxiv.org/html/2607.23030#bib.bib56)\)\.

\{assumption\}

The Markov chainPPis finite, aperiodic and irreducible\. Consequently, there exists a unique distributionqqsuch thatP⊤​q=qP^\{\\top\}q=q, andminx∈\\mcX⁡q​\(x\)\>0\\min\_\{x\\in\\mcX\}q\(x\)\>0\.

We now define the projection operator to the feature space\. Consider the inner product⟨\\bmv,\\bmw⟩q:=∑i=1Nq​\(i\)​\\bmvi​\\bmwi\\langle\\bmv,\\bmw\\rangle\_\{q\}:=\\sum\_\{i=1\}^\{N\}q\(i\)\\bmv\_\{i\}\\bmw\_\{i\}and the associatedqq\-weighted norm\\norm​vq:=⟨\\bmv,\\bmv⟩q\\norm\{v\}\_\{q\}:=\\sqrt\{\\langle\\bmv,\\bmv\\rangle\_\{q\}\}, for any\\bmv,\\bmw∈\\mbRN\\bmv,\\bmw\\in\\mbR^\{N\}, where\\bmvi\\bmv\_\{i\}denotes theii\-th component of\\bmv\\bmv\. Letspan​\(\\bmPhi\)\\mathrm\{span\}\(\\bmPhi\)denote the subspace spanned by the feature vectors\. The orthogonal projectionΠ:\\mcL​\(\\mcX\)→span​\(\\bmPhi\)\\Pi:\\mcL\(\\mcX\)\\to\\mathrm\{span\}\(\\bmPhi\)under theqq\-weighted norm is defined by

Π​\(\\bmv\):=\\argmin\\bmz∈span​\(\\bmPhi\)​\\norm​\\bmv−\\bmzq\.\\Pi\(\\bmv\):=\\argmin\_\{\\bmz\\in\\mathrm\{span\}\(\\bmPhi\)\}\\norm\{\\bmv\-\\bmz\}\_\{q\}\.
Following the results in the risk\-neutral case\(Tsitsiklis and Van Roy,[1997](https://arxiv.org/html/2607.23030#bib.bib1)\), we also try to find an optimal\\bmtheta∗\\bmtheta^\{\*\}that is a good approximation forVV\. Here we define the “good approximation” as the discrepancy\\norm​\\bmPhi​\\bmtheta∗−Vq\\norm\{\\bmPhi\\bmtheta^\{\*\}\-V\}\_\{q\}can be controlled by\\norm​Π​V−Vq\\norm\{\\Pi V\-V\}\_\{q\}multiplied by some fixed constant\.

We make the following assumptions that are essential for our analysis\.

\{assumption\}

There existL1,ϵ1\>0L\_\{1\},\\epsilon\_\{1\}\>0such that0<ϵ1≤ℓ​\(x\)−ℓ​\(y\)x−y≤L10<\\epsilon\_\{1\}\\leq\\frac\{\\ell\(x\)\-\\ell\(y\)\}\{x\-y\}\\leq L\_\{1\}, for allx≠y∈\\mbRx\\neq y\\in\\mbR\.

\{assumption\}

The loss functionℓ\\ellis either convex or concave on\[0,∞\)\[0,\\infty\)and either convex or concave on\(−∞,0\)\(\-\\infty,0\)\.

\{assumption\}

There exists a constantM\>0M\>0such thatmaxx∈\\mcX⁡\\norm​\\bmphi​\(x\)2≤M\\max\_\{x\\in\\mcX\}\\norm\{\\bmphi\(x\)\}\_\{2\}\\leq M\.

Assumption[4](https://arxiv.org/html/2607.23030#S4)is standard in the UBSR literature\(Shenet al\.,[2014](https://arxiv.org/html/2607.23030#bib.bib3); Hu and Zhang,[2018](https://arxiv.org/html/2607.23030#bib.bib29); Wang and Delage,[2025](https://arxiv.org/html/2607.23030#bib.bib26)\)and is typically used to establish contraction of the associated risk\-aware Bellman operators\. The risk\-neutral, expectile, and soft\-quantile risk measures satisfy it by definition\. Although ERM does not, a truncated variant can be constructed to satisfy the assumption \(see Section A\.2 inShenet al\.\([2014](https://arxiv.org/html/2607.23030#bib.bib3)\)\)\.

We next show some results regarding the stochastic value iteration \([8](https://arxiv.org/html/2607.23030#S3.E8)\)\. Notice that \([8](https://arxiv.org/html/2607.23030#S3.E8)\) can be written equivalently into the following general stochastic approximation form:

Vn\+1​\(x\)=Vn​\(x\)\+ηnα​\(\(\\mcH​Vn\)​\(x\)−Vn​\(x\)\+Mn\+1​\(x\)\),∀x∈\\mcX,V\_\{n\+1\}\(x\)=V\_\{n\}\(x\)\+\\frac\{\\eta\_\{n\}\}\{\\alpha\}\\left\(\(\\mcH V\_\{n\}\)\(x\)\-V\_\{n\}\(x\)\+M\_\{n\+1\}\(x\)\\right\),\\quad\\forall x\\in\\mcX,\(11\)whereα\\alphais some positive constant that will be specified later,\\mcH:\\mcL​\(\\mcX\)→\\mcL​\(\\mcX\)\\mcH:\\mcL\(\\mcX\)\\to\\mcL\(\\mcX\)is an operator andMn\+1M\_\{n\+1\}is a martingale difference sequence defined as follows: for allx∈\\mcXx\\in\\mcX,

\(\\mcH​Vn\)​\(x\)\\displaystyle\(\\mcH V\_\{n\}\)\(x\):=α​∑x′∈\\mcXP​\(x′\|x\)​ℓ​\(γ​Vn​\(x′\)−Vn​\(x\)\+c​\(x\)\)\+Vn​\(x\),\\displaystyle=\\alpha\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\ell\(\\gamma V\_\{n\}\(x^\{\\prime\}\)\-V\_\{n\}\(x\)\+c\(x\)\)\+V\_\{n\}\(x\),\(12\)Mn\+1​\(x\)\\displaystyle M\_\{n\+1\}\(x\):=α​ℓ​\(γ​Vn​\(X′\)−Vn​\(x\)\+c​\(x\)\)−α​∑x′∈\\mcXP​\(x′\|x\)​ℓ​\(γ​V​\(x′\)−V​\(x\)\+c​\(x\)\),\\displaystyle=\\alpha\\ell\(\\gamma V\_\{n\}\(X^\{\\prime\}\)\-V\_\{n\}\(x\)\+c\(x\)\)\-\\alpha\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\ell\(\\gamma V\(x^\{\\prime\}\)\-V\(x\)\+c\(x\)\),whereX′∼P\(⋅\|x\)X^\{\\prime\}\\sim P\(\\cdot\|x\)\. We have the following result regarding the operator\\mcH\\mcH\.

###### Lemma 4\.1\.

Under Assumptions[4](https://arxiv.org/html/2607.23030#S4)and[4](https://arxiv.org/html/2607.23030#S4), letγ<ϵ1/L1\\gamma<\\epsilon\_\{1\}/L\_\{1\}and selectα∈\(0,2​\(ϵ1−γ​L1\)L12​\(1\+γ\)2\)\\alpha\\in\(0,\\frac\{2\(\\epsilon\_\{1\}\-\\gamma L\_\{1\}\)\}\{L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\}\)\. Then the operator\\mcH\\mcHis anα¯\\bar\{\\alpha\}\-contraction on\(\\mcL\(\\mcX\),\\norm⋅q\)\(\\mcL\(\\mcX\),\\norm\{\\cdot\}\_\{q\}\)for someα¯∈\(0,1\)\\bar\{\\alpha\}\\in\(0,1\)\. Consequently,\\mcH\\mcHadmits a unique fixed pointVV, satisfyingV=\\mcH​VV=\\mcH V\. Furthermore,VVis a solution to \([7](https://arxiv.org/html/2607.23030#S3.E7)\)\.

SinceΠ\\Piis non\-expansive under\\norm⋅q\\norm\{\\cdot\}\_\{q\}, the compositionΠ​\\mcH\\Pi\\mcHis also anα¯\\bar\{\\alpha\}\-contraction under\\norm⋅q\\norm\{\\cdot\}\_\{q\}\. Because\\bmPhi\\bmPhihas full rank, there exists a unique\\bmtheta∗∈\\mbRd\\bmtheta^\{\*\}\\in\\mbR^\{d\}such that\\bmPhi​\\bmtheta∗=Π​\\mcH​\(\\bmPhi​\\bmtheta∗\)\\bmPhi\\bmtheta^\{\*\}=\\Pi\\mcH\(\\bmPhi\\bmtheta^\{\*\}\)\. Thus,\\bmPhi​\\bmtheta∗\\bmPhi\\bmtheta^\{\*\}is the unique fixed point of the operatorΠ​\\mcH\\Pi\\mcH\. We formally state the result as the following lemma\.

###### Lemma 4\.3\.

Under the assumptions of Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1),Π​\\mcH\\Pi\\mcHis a contraction on\(\\mcL\(\\mcX\),\\norm⋅q\)\(\\mcL\(\\mcX\),\\norm\{\\cdot\}\_\{q\}\)and has a fixed point of the form\\bmPhi​\\bmtheta∗\\bmPhi\\bmtheta^\{\*\}for a unique\\bmtheta∗∈\\mbRd\\bmtheta^\{\*\}\\in\\mbR^\{d\}\. Moreover,\\norm​\\bmPhi​\\bmtheta∗−Vq≤11−α¯​\\norm​Π​V−Vq\\norm\{\\bmPhi\\bmtheta^\{\*\}\-V\}\_\{q\}\\leq\\frac\{1\}\{1\-\\bar\{\\alpha\}\}\\norm\{\\Pi V\-V\}\_\{q\}\.

Clearly, ifd=Nd=N, we have\\norm​Π​V−Vq=0\\norm\{\\Pi V\-V\}\_\{q\}=0and Lemma[4\.3](https://arxiv.org/html/2607.23030#S4.Thmtheorem3)implies that\\bmPhi​\\bmtheta∗=V\\bmPhi\\bmtheta^\{\*\}=V\.

From \([10](https://arxiv.org/html/2607.23030#S3.E10)\), the UBSR\-TD update can be written as

α​\(\\bmthetan\+1−\\bmthetan\)ηn=α\\bmphi\(Xn\)ℓ\(\(γ\\bmphi\(Xn\+1\)−\\bmphi\(Xn\)\)⊤\\bmthetan\+c\(Xn\)\)=:H\(\\bmthetan,Yn\+1\),\\displaystyle\\frac\{\\alpha\(\\bmtheta\_\{n\+1\}\-\\bmtheta\_\{n\}\)\}\{\\eta\_\{n\}\}=\\alpha\\bmphi\(X\_\{n\}\)\\ell\\left\(\(\\gamma\\bmphi\(X\_\{n\+1\}\)\-\\bmphi\(X\_\{n\}\)\)^\{\\top\}\\bmtheta\_\{n\}\+c\(X\_\{n\}\)\\right\)=:H\(\\bmtheta\_\{n\},Y\_\{n\+1\}\),\(13\)whereYn\+1:=\(Xn,Xn\+1\)Y\_\{n\+1\}:=\(X\_\{n\},X\_\{n\+1\}\), andα\>0\\alpha\>0is some constant\. Define the filtration\\mcFn:=σ​\(\{\\bmthetai,Xi\}i≤n\)\\mcF\_\{n\}:=\\sigma\(\\\{\\bmtheta\_\{i\},X\_\{i\}\\\}\_\{i\\leq n\}\)\. Under Assumption[4](https://arxiv.org/html/2607.23030#S4), it is straightforward to see that\{Yn\}n≥1\\\{Y\_\{n\}\\\}\_\{n\\geq 1\}is also a Markov chain and is\\mcFn\\mcF\_\{n\}\-measurable\. Hence \([13](https://arxiv.org/html/2607.23030#S4.E13)\) fits in the classic form of a stochastic approximation with Markovian noise\(Borkaret al\.,[2025](https://arxiv.org/html/2607.23030#bib.bib56); Liuet al\.,[2025a](https://arxiv.org/html/2607.23030#bib.bib39)\)\. Then under proper conditions, the stochastic approximation \([13](https://arxiv.org/html/2607.23030#S4.E13)\) converges almost surely to an equilibrium point of the mean\-field ODE

d​\\bmvartheta​\(t\)d​t\\displaystyle\\frac\{d\\bmvartheta\(t\)\}\{dt\}=h​\(\\bmvartheta​\(t\)\):=\\mbEY∼dY​\[H​\(\\bmvartheta​\(t\),Y\)\]\\displaystyle=h\(\\bmvartheta\(t\)\)=\\mbE\_\{Y\\sim d\_\{Y\}\}\[H\(\\bmvartheta\(t\),Y\)\]\(14\)=α​∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ℓ​\(\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\\bmvartheta​\(t\)\+c​\(x\)\),\\displaystyle=\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmvartheta\(t\)\+c\(x\)\\right\),where\\bmvartheta​\(t\)\\bmvartheta\(t\)is the trajectory of the ODE at timettin\\mbRd\\mbR^\{d\}, anddYd\_\{Y\}is the stationary distribution of the Markov chain\{Yn\}n≥1\\\{Y\_\{n\}\\\}\_\{n\\geq 1\}withX0∼qX\_\{0\}\\sim qandXn∼P\(⋅\|Xn−1\)X\_\{n\}\\sim P\(\\cdot\|X\_\{n\-1\}\)forn≥1n\\geq 1\. If the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) has an equilibrium point\\bmtheta~\\tilde\{\\bmtheta\}, then we have

𝟎=∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ℓ​\(\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\\bmtheta~\+c​\(x\)\),\\bm\{0\}=\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\tilde\{\\bmtheta\}\+c\(x\)\\right\),\(15\)which is exactly the root finding problem \([9](https://arxiv.org/html/2607.23030#S3.E9)\)\.

It turns out that the conditions in Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1)ensure that the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) has a unique equilibrium, which coincides with the optimal\\bmtheta∗\\bmtheta^\{\*\}defined in Lemma[4\.3](https://arxiv.org/html/2607.23030#S4.Thmtheorem3)\.

###### Lemma 4\.4\.

Under the assumptions of Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1), the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) has a unique equilibrium point\\bmtheta∗\\bmtheta^\{\*\}, with\\bmPhi​\\bmtheta∗\\bmPhi\\bmtheta^\{\*\}being the unique fixed point for the operatorΠ​\\mcH\\Pi\\mcH\.

We now turn to establish the almost sure convergence of the UBSR\-TD algorithm \([10](https://arxiv.org/html/2607.23030#S3.E10)\)\. To do this, define an operator\\mcH^:\\mbRd→\\mbRd\\hat\{\\mcH\}:\\mbR^\{d\}\\to\\mbR^\{d\}as

\\mcH^​\(\\bmtheta\):=α​∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ℓ​\(\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\\bmtheta\+c​\(x\)\)\+\\bmtheta,∀\\bmtheta∈\\mbRd\.\\hat\{\\mcH\}\(\\bmtheta\):=\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\+c\(x\)\\right\)\+\\bmtheta,\\quad\\forall\\bmtheta\\in\\mbR^\{d\}\.\(16\)Then the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) can be written asd​\\bmvartheta​\(t\)d​t=\\mcH^​\(\\bmvartheta​\(t\)\)−\\bmvartheta​\(t\)\\frac\{d\\bmvartheta\(t\)\}\{dt\}=\\hat\{\\mcH\}\(\\bmvartheta\(t\)\)\-\\bmvartheta\(t\)and clearly the equilibrium point\\bmtheta∗\\bmtheta^\{\*\}of the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) is a fixed point for the operator\\mcH^\\hat\{\\mcH\}, i\.e\.,\\mcH^​\(\\bmtheta∗\)=\\bmtheta∗\\hat\{\\mcH\}\(\\bmtheta^\{\*\}\)=\\bmtheta^\{\*\}, which is exactly a solution to the root finding problem \([9](https://arxiv.org/html/2607.23030#S3.E9)\)\.

We make the following assumption on the iterative step size\.\{assumption\}The step size\{ηn\}n=0∞\\\{\\eta\_\{n\}\\\}\_\{n=0\}^\{\\infty\}satisfies∑n=0∞ηn=∞\\sum\_\{n=0\}^\{\\infty\}\\eta\_\{n\}=\\inftyand∑n=0∞ηn2<∞\\sum\_\{n=0\}^\{\\infty\}\\eta\_\{n\}^\{2\}<\\infty\. Furthermore, the limitlimn→∞\(ηn\+1−1−ηn−1\)=:η∗\\lim\_\{n\\to\\infty\}\\left\(\\eta\_\{n\+1\}^\{\-1\}\-\\eta\_\{n\}^\{\-1\}\\right\)=:\\eta^\{\*\}exists and is finite\. This assumption is somewhat stronger than the classical Robbins\-Monro condition and is required for technical reasons \(seeBorkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\)andLiuet al\.\([2025a](https://arxiv.org/html/2607.23030#bib.bib39)\)for details\)\. Commonly used choices, such asηn=b1/\(n\+b2\)δ\\eta\_\{n\}=b\_\{1\}/\(n\+b\_\{2\}\)^\{\\delta\}withb1,b2\>0,δ∈\(1/2,1\]b\_\{1\},b\_\{2\}\>0,\\delta\\in\(1/2,1\], satisfy this requirement\.

We are ready to present the almost sure convergence result for the UBSR\-TD algorithm\.

###### Theorem 4\.5\.

Suppose that Assumptions[4](https://arxiv.org/html/2607.23030#S4)\-[4](https://arxiv.org/html/2607.23030#S4)hold and thatγ<ϵ1/L1\\gamma<\\epsilon\_\{1\}/L\_\{1\}\. Then, the UBSR\-TD algorithm \([10](https://arxiv.org/html/2607.23030#S3.E10)\) converges almost surely to\\bmtheta∗\\bmtheta^\{\*\}, where\\bmtheta∗\\bmtheta^\{\*\}is defined as in Lemma[4\.3](https://arxiv.org/html/2607.23030#S4.Thmtheorem3)\.

Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)establishes that UBSR\-TD converges almost surely to a unique\\bmtheta∗\\bmtheta^\{\*\}, whereΦ​\\bmtheta∗\\Phi\\bmtheta^\{\*\}is a fixed point of the projected risk\-aware Bellman operatorΠ​\\mcH\\Pi\\mcH\. Lemma[4\.4](https://arxiv.org/html/2607.23030#S4.Thmtheorem4)then indicates that such\\bmtheta∗\\bmtheta^\{\*\}is a unique equilibrium of the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) and hence a solution to the root\-finding problem \([9](https://arxiv.org/html/2607.23030#S3.E9)\)\.

We comment on the proof of Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)\. Since the operator\\mcH^\\hat\{\\mcH\}is nonlinear in\\bmtheta\\bmtheta, the classical linear stochastic approximation result ofTsitsiklis and Van Roy \([1997](https://arxiv.org/html/2607.23030#bib.bib1)\)is not directly applicable\. We instead invoke the recent stochastic approximation framework with Markovian noise developed inBorkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\)to establish the almost sure convergence\. Although aperiodicity of the Markov chain is likely unnecessary to establish the almost sure convergence, as noted inTsitsiklis and Van Roy \([1997](https://arxiv.org/html/2607.23030#bib.bib1)\)for TD\(0\), we impose this assumption because our proof relies on Theorem 1 ofBorkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\), where aperiodicity is used to establish geometric ergodicity of the Markov chain\. Alternative techniques, such as those inLiuet al\.\([2025a](https://arxiv.org/html/2607.23030#bib.bib39)\), may establish convergence under weaker conditions and general state space, but would require a more involved analysis, as Assumption 3 ofLiuet al\.\([2025a](https://arxiv.org/html/2607.23030#bib.bib39)\)generally does not hold in our setting\.

The conditionγ<ϵ1/L1\\gamma<\\epsilon\_\{1\}/L\_\{1\}is essential for the well\-posedness and convergence of UBSR\-TD, ensuring convergence to a unique stationary point of the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\)\. When it is violated, the limiting ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) may admit multiple or unstable equilibria, as shown in the following example\.

###### Example 4\.6\.

Consider a zero\-cost, two\-state Markov chain with symmetric transitionsP​\(xi\|xj\)=1−P​\(xi\|xi\)=pP\(x\_\{i\}\|x\_\{j\}\)=1\-P\(x\_\{i\}\|x\_\{i\}\)=pfori≠j∈\{1,2\}i\\neq j\\in\\\{1,2\\\}\. Let the feature dimension be one with\\bmPhi=\[1​δ\]⊤\\bmPhi=\[1\\ \\delta\]^\{\\top\}andδ=891±465917182\\delta=\\frac\{891\\pm\\sqrt\{465917\}\}\{182\}\. Consider the expectile risk with loss functionℓ​\(y\)=L1​y\\ell\(y\)=L\_\{1\}yfory≥0y\\geq 0andℓ​\(y\)=ϵ1​y\\ell\(y\)=\\epsilon\_\{1\}yfory<0y<0\. We setϵ1=1−L1=1/11\\epsilon\_\{1\}=1\-L\_\{1\}=1/11andγ=9/10\>ϵ1/L1=1/10\\gamma=9/10\>\\epsilon\_\{1\}/L\_\{1\}=1/10, violating the conditions of Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)\. Nevertheless, one can easily identify the true value functionV​\(x\)=0V\(x\)=0for allxx, exactly represented by\\bmtheta∗=0\\bmtheta^\{\*\}=0\. Whenp=9/10p=9/10, Equation \([9](https://arxiv.org/html/2607.23030#S3.E9)\) holds for every\\bmtheta≥0\\bmtheta\\geq 0\. Consequently, the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) has a continuum of equilibria becaused​\\bmvartheta​\(t\)d​t=0\\frac\{d\\bmvartheta\(t\)\}\{dt\}=0for\\bmvartheta​\(t\)≥0\\bmvartheta\(t\)\\geq 0\. Therefore, within this region, the UBSR\-TD iterates have zero expected drift\. Whenp∈\(9/10,1\)p\\in\(9/10,1\), the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) has a unique equilibrium at\\bmtheta∗=0\\bmtheta^\{\*\}=0, which is unstable from the positive side, sinced​\\bmvartheta​\(t\)d​t\>0\\frac\{d\\bmvartheta\(t\)\}\{dt\}\>0whenever\\bmvartheta​\(t\)\>0\\bmvartheta\(t\)\>0\. Consequently, for\\bmtheta0\>0\\bmtheta\_\{0\}\>0, the UBSR\-TD iterates exhibit a positive expected drift away from zero\.

The bounds onγ\\gammacan be tightened by incorporating transition and feature information\. For example,Köse and Ruszczyński \([2021](https://arxiv.org/html/2607.23030#bib.bib28)\)derives a sufficient conditionγ<1/1\+χ\\gamma<1/\\sqrt\{1\+\\chi\}using the distortion coefficientχ\\chifor coherent risk measures\. In our example, this givesγ<19/10\\gamma<\\sqrt\{19\}/10for the expectile whenp=9/10p=9/10, improving on1/101/10but remaining below the true threshold9/109/10\. Therefore, the conditionγ<ϵ1/L1\\gamma<\\epsilon\_\{1\}/L\_\{1\}should be viewed as a robust sufficient condition for general UBSR satisfying Assumption[4](https://arxiv.org/html/2607.23030#S4), with sharper bounds available under problem\-specific structures\.

## 5Extensions

TD\-type algorithms are known to converge slowly when the step size is not carefully tuned\(Sutton and Barto,[2018](https://arxiv.org/html/2607.23030#bib.bib16)\)\. To address this issue, we introduce two extensions: UBSR\-TD\(λ\\lambda\) and UBSR\-Newton\. These algorithms possess distinct features and, as shown in our experiments, can outperform UBSR\-TD in certain settings\. We present them to highlight that existing risk\-neutral policy evaluation methods can be adapted to the dynamic UBSR objective by simply incorporating the loss function to the TD error\. The algorithm pseudo\-codes are provided in Appendix[A](https://arxiv.org/html/2607.23030#A1)\.

### 5\.1UBSR\-TD\(λ\\lambda\) Algorithm

Eligibility traces can accelerate learning by incorporating temporal\-difference information over multiple time steps\(Dannet al\.,[2014](https://arxiv.org/html/2607.23030#bib.bib42)\)\. By interpolating between TD learning and Monte\-Carlo sampling, they are regarded as one of the most natural extensions of TD\-type methods\(Sutton and Barto,[2018](https://arxiv.org/html/2607.23030#bib.bib16)\)\. In the following, we incorporate eligibility traces into UBSR\-TD\.

Letλ∈\[0,1\]\\lambda\\in\[0,1\]\. Given an observation of the streaming data\{Xn\}n≥0\\\{X\_\{n\}\\\}\_\{n\\geq 0\}\. Define a sequence of eligibility vector\\bmzetan∈\\mbRd\\bmzeta\_\{n\}\\in\\mbR^\{d\}as\\bmzetan:=∑k=0n\(γ​λ\)n−k​\\bmphi​\(Xk\)\\bmzeta\_\{n\}:=\\sum\_\{k=0\}^\{n\}\(\\gamma\\lambda\)^\{n\-k\}\\bmphi\(X\_\{k\}\), which can be recursively computed by

\\bmzetan\+1=γ​λ​\\bmzetan\+\\bmphi​\(Xn\+1\),\\bmzeta\_\{n\+1\}=\\gamma\\lambda\\bmzeta\_\{n\}\+\\bmphi\(X\_\{n\+1\}\),\(17\)with\\bmzeta0:=\\bmphi​\(X0\)\\bmzeta\_\{0\}:=\\bmphi\(X\_\{0\}\)\. TheUBSR\-TD\(λ\\lambda\) algorithmis defined as

\\bmthetan\+1=\\bmthetan\+ηn​\\bmzetan​ℓ​\(\(γ​\\bmphi​\(Xn\+1\)−\\bmphi​\(Xn\)\)⊤​\\bmthetan\+c​\(Xn\)\),\\bmtheta\_\{n\+1\}=\\bmtheta\_\{n\}\+\\eta\_\{n\}\\bmzeta\_\{n\}\\ell\\left\(\(\\gamma\\bmphi\(X\_\{n\+1\}\)\-\\bmphi\(X\_\{n\}\)\)^\{\\top\}\\bmtheta\_\{n\}\+c\(X\_\{n\}\)\\right\),\(18\)
Whenλ=0\\lambda=0, the algorithm reduces to UBSR\-TD\. Forλ\>0\\lambda\>0, however, UBSR\-TD\(λ\\lambda\) need not converge to the same objective \([9](https://arxiv.org/html/2607.23030#S3.E9)\) as UBSR\-TD, unlike its counterpart in the risk\-neutral setting\. This phenomenon is demonstrated in our numerical experiments \(see Section[6\.1\.2](https://arxiv.org/html/2607.23030#S6.SS1.SSS2)\)\.Köse and Ruszczyński \([2021](https://arxiv.org/html/2607.23030#bib.bib28)\)\(Section 5\) develops a related eligibility\-trace\-based TD\-type algorithm for MDPs with dynamic coherent risk measures\. Their analysis shows that, in the dynamic risk setting, TD\(λ\\lambda\)\-type algorithms generally solve a different root\-finding problem, with the original objective distorted by aλ\\lambda\-dependent weight matrix\. Moreover, as shown in our experiments, UBSR\-TD\(1\) generally does not minimize the projected value\-function error, in contrast to classical TD\(1\)\.

### 5\.2UBSR\-Newton Algorithm

Newton\-type methods have been widely used to accelerate TD\-type algorithms\(Givchi and Palhang,[2014](https://arxiv.org/html/2607.23030#bib.bib70); Panet al\.,[2017](https://arxiv.org/html/2607.23030#bib.bib69)\)\. By leveraging second\-order information, they are shown to improve convergence in risk\-neutral settings\. We next develop an analogous approach for the UBSR framework\. Throughout this subsection, we assume thatℓ\\ellis differentiable\. For notation simplicity, let\\bmXn:=\\bmphi​\(Xn\)\\bmX\_\{n\}:=\\bmphi\(X\_\{n\}\),\\bmZn:=γ​\\bmphi​\(Xn\+1\)−\\bmphi​\(Xn\)\\bmZ\_\{n\}:=\\gamma\\bmphi\(X\_\{n\+1\}\)\-\\bmphi\(X\_\{n\}\),cn:=c​\(Xn\)c\_\{n\}:=c\(X\_\{n\}\)\. Then\(\\bmXn,\\bmZn,cn\)\(\\bmX\_\{n\},\\bmZ\_\{n\},c\_\{n\}\)represents a one\-stage observation generated by the Markov chainPP\.

For the risk\-neutral problem \([2](https://arxiv.org/html/2607.23030#S2.E2)\),Liuet al\.\([2025b](https://arxiv.org/html/2607.23030#bib.bib2)\)use the full observation history to update both the second\-order information matrix and the improvement direction\. Extending this idea to the UBSR setting, given observations\(\\bmXi,\\bmZi,ci\)i≥0\{\(\\bmX\_\{i\},\\bmZ\_\{i\},c\_\{i\}\)\}\_\{i\\geq 0\}, we recursively update

\\bmtheta^n\+1=1n\+1​∑i=1n\+1\\bmtheta^i−1−\\bmH^n\+1−1​1n\+1​∑i=1n\+1\\bmXi​ℓ​\(\\bmZi⊤​\\bmtheta^i−1\+ci\),\\hat\{\\bmtheta\}\_\{n\+1\}=\\frac\{1\}\{n\+1\}\\sum\_\{i=1\}^\{n\+1\}\\hat\{\\bmtheta\}\_\{i\-1\}\-\\hat\{\\bmH\}\_\{n\+1\}^\{\-1\}\\frac\{1\}\{n\+1\}\\sum\_\{i=1\}^\{n\+1\}\\bmX\_\{i\}\\ell\\left\(\\bmZ\_\{i\}^\{\\top\}\\hat\{\\bmtheta\}\_\{i\-1\}\+c\_\{i\}\\right\),\(19\)where\\bmH^n\+1\\hat\{\\bmH\}\_\{n\+1\}is an empirical information matrix for \([9](https://arxiv.org/html/2607.23030#S3.E9)\) defined as

\\bmH^n\+1:=1n\+1​∑i=1n\+1\\bmXi​\\bmZi⊤​ℓ′​\(\\bmZi⊤​\\bmtheta^i−1\+ci\)\.\\hat\{\\bmH\}\_\{n\+1\}:=\\frac\{1\}\{n\+1\}\\sum\_\{i=1\}^\{n\+1\}\\bmX\_\{i\}\\bmZ\_\{i\}^\{\\top\}\\ell^\{\\prime\}\\left\(\\bmZ\_\{i\}^\{\\top\}\\hat\{\\bmtheta\}\_\{i\-1\}\+c\_\{i\}\\right\)\.\(20\)
As suggested inLiuet al\.\([2025b](https://arxiv.org/html/2607.23030#bib.bib2)\), Whenever\\bmH^n\\hat\{\\bmH\}\_\{n\}is invertable, the formulation in \([19](https://arxiv.org/html/2607.23030#S5.E19)\)\-\([20](https://arxiv.org/html/2607.23030#S5.E20)\) can be rewritten in a fully online form by introducing two auxiliary variables and applying the Sherman\-Morrison formula\. Consequently, the resulting update scheme requires no more thanO​\(d2\)O\(d^\{2\}\)additional computational and memory cost per iteration\. Moreover, to ensure the invertibility of an initial\\bmH^0\\hat\{\\bmH\}\_\{0\}, one can employ a “warm\-up” procedure: we use the firstn0n\_\{0\}samples to construct an invertible\\bmH^n0\\hat\{\\bmH\}\_\{n\_\{0\}\}before carrying out the Newton update\.

We summarize the modified iteration procedure as follows\. First, we initialize\\bmtheta^0\\hat\{\\bmtheta\}\_\{0\}and use the initialn0n\_\{0\}samples to compute:

\\bmH^n0:=1n0​∑i=1n0\\bmXi​\\bmZi⊤​ℓ′​\(\\bmZi⊤​\\bmtheta^0\+ci\),\\bmLn0:=1n0​∑i=1n0\\bmXi​ℓ​\(\\bmZi⊤​\\bmtheta^0\+ci\),\\hat\{\\bmH\}\_\{n\_\{0\}\}:=\\frac\{1\}\{n\_\{0\}\}\\sum\_\{i=1\}^\{n\_\{0\}\}\\bmX\_\{i\}\\bmZ\_\{i\}^\{\\top\}\\ell^\{\\prime\}\(\\bmZ\_\{i\}^\{\\top\}\\hat\{\\bmtheta\}\_\{0\}\+c\_\{i\}\),\\quad\\bmL\_\{n\_\{0\}\}:=\\frac\{1\}\{n\_\{0\}\}\\sum\_\{i=1\}^\{n\_\{0\}\}\\bmX\_\{i\}\\ell\(\\bmZ\_\{i\}^\{\\top\}\\hat\{\\bmtheta\}\_\{0\}\+c\_\{i\}\),\(21\)ensuring that\\bmH^n0\\hat\{\\bmH\}\_\{n\_\{0\}\}is invertable\. Note that for\\bmH^n0\\hat\{\\bmH\}\_\{n\_\{0\}\}to be full rank, it is necessary to haven0≥dn\_\{0\}\\geq d\. Let\\bmtheta^i=\\bmtheta¯i:=\\bmtheta^0\\hat\{\\bmtheta\}\_\{i\}=\\bar\{\\bmtheta\}\_\{i\}:=\\hat\{\\bmtheta\}\_\{0\}fori=1,⋯,n0i=1,\\cdots,n\_\{0\}\. Then starting fromn=n0n=n\_\{0\}, we recursively compute

\\bmtheta^n\+1=\\bmtheta¯n\+1−\\bmH^n\+1−1​\\bmLn\+1,\\hat\{\\bmtheta\}\_\{n\+1\}=\\bar\{\\bmtheta\}\_\{n\+1\}\-\\hat\{\\bmH\}\_\{n\+1\}^\{\-1\}\\bmL\_\{n\+1\},\(22\)where

\\bmtheta¯n\+1:=1n\+1​\(n​\\bmtheta¯n\+\\bmtheta^n\),\\bar\{\\bmtheta\}\_\{n\+1\}:=\\frac\{1\}\{n\+1\}\\left\(n\\bar\{\\bmtheta\}\_\{n\}\+\\hat\{\\bmtheta\}\_\{n\}\\right\),\(23\)\\bmLn\+1:=nn\+1​\\bmLn\+1n\+1​\\bmXn\+1​ℓ​\(\\bmZn\+1⊤​\\bmtheta^n\+cn\+1\),\\displaystyle\\bmL\_\{n\+1\}=\\frac\{n\}\{n\+1\}\\bmL\_\{n\}\+\\frac\{1\}\{n\+1\}\\bmX\_\{n\+1\}\\ell\\left\(\\bmZ\_\{n\+1\}^\{\\top\}\\hat\{\\bmtheta\}\_\{n\}\+c\_\{n\+1\}\\right\),\(24\)\\bmH^n\+1=nn\+1​\\bmH^n\+1n\+1​\\bmXn\+1​\\bmZn\+1⊤​ℓ′​\(\\bmZn\+1⊤​\\bmtheta^n\+cn\+1\)\.\\hat\{\\bmH\}\_\{n\+1\}=\\frac\{n\}\{n\+1\}\\hat\{\\bmH\}\_\{n\}\+\\frac\{1\}\{n\+1\}\\bmX\_\{n\+1\}\\bmZ\_\{n\+1\}^\{\\top\}\\ell^\{\\prime\}\\left\(\\bmZ\_\{n\+1\}^\{\\top\}\\hat\{\\bmtheta\}\_\{n\}\+c\_\{n\+1\}\\right\)\.\(25\)Once\\bmH^n−1\\hat\{\\bmH\}\_\{n\}^\{\-1\}is available,\\bmH^n\+1−1\\hat\{\\bmH\}\_\{n\+1\}^\{\-1\}can be computed recursively using the Sherman\-Morrison formula:

\\bmH^n\+1−1=n\+1n​\\bmH^n−1−n\+1n2​\\bmH^n−1​\\bmXn\+1​\\bmZn\+1⊤​\\bmH^n−1\(ℓ′​\(\\bmZn\+1⊤​\\bmtheta^n\+cn\+1\)\)−1\+1n​\\bmZn\+1⊤​\\bmH^n−1​\\bmXn\+1\.\\hat\{\\bmH\}\_\{n\+1\}^\{\-1\}=\\frac\{n\+1\}\{n\}\\hat\{\\bmH\}\_\{n\}^\{\-1\}\-\\frac\{\\frac\{n\+1\}\{n^\{2\}\}\\hat\{\\bmH\}\_\{n\}^\{\-1\}\\bmX\_\{n\+1\}\\bmZ\_\{n\+1\}^\{\\top\}\\hat\{\\bmH\}\_\{n\}^\{\-1\}\}\{\(\\ell^\{\\prime\}\(\\bmZ\_\{n\+1\}^\{\\top\}\\hat\{\\bmtheta\}\_\{n\}\+c\_\{n\+1\}\)\)^\{\-1\}\+\\frac\{1\}\{n\}\\bmZ\_\{n\+1\}^\{\\top\}\\hat\{\\bmH\}\_\{n\}^\{\-1\}\\bmX\_\{n\+1\}\}\.\(26\)We call the update \([21](https://arxiv.org/html/2607.23030#S5.E21)\)\-\([26](https://arxiv.org/html/2607.23030#S5.E26)\) theUBSR\-Newton algorithm\.

The UBSR\-Newton algorithm extends the ROPE method ofLiuet al\.\([2025b](https://arxiv.org/html/2607.23030#bib.bib2)\)for online robust policy evaluation, in whichℓ\\ellis chosen as the derivative of a smoothed Huber loss\. Our formulation generalizes ROPE to a broader class of Newton\-type algorithms, and the resulting algorithm can be interpreted as policy evaluation in a risk\-aware MDP framework with dynamic UBSR measures\.

Although almost sure convergence has not been established for either ROPE or UBSR\-Newton, techniques analogous to those inLiuet al\.\([2025b](https://arxiv.org/html/2607.23030#bib.bib2)\)may be used to derive uniform high\-probability bounds and variance estimators for UBSR\-Newton\.

## 6Experiments

In this section, we conduct numerical experiments to evaluate the algorithms proposed in the preceding sections\. We first examine the algorithms in a tabular MDP setting and validate the convergence result established in Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)\. We then further demonstrate the potential of our algorithms through a real\-world risk\-aware perishable inventory problem, where function approximation is required to address the curse of dimensionality\.

### 6\.1Convergence Experiments for Different Algorithms

We test the policy evaluation algorithms on a randomly generated MDP withN=10N=10states and 10 actions per state\. The nominal transition kernel is sampled uniformly on\[0,1\]\[0,1\]and normalized, the cost function is drawn from the normal distribution\\mcN​\(10,100\)\\mcN\(10,100\), and the deterministic policy is generated randomly\. The feature matrix is orthogonalized via QR decomposition to ensure full rank, The initial\\bmtheta0\\bmtheta\_\{0\}is set to𝟎\\bm\{0\}\. For UBSR\-TD, we useηn=2/\(n\+100\)2/3\\eta\_\{n\}=2/\(n\+100\)^\{2/3\}, a value calibrated in preliminary experiments to promote convergence\. We setn0=500n\_\{0\}=500for UBSR\-Newton, and the resulting\\bmH^n0\\hat\{\\bmH\}\_\{n\_\{0\}\}is observed to be invertable in all the test scenarios\.

We consider two representative UBSR measures: the expectile and the soft quantile\. For the expectile, Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)requiresγ<γEXP:=min⁡\{τ1−τ,1−ττ\}\\gamma<\\gamma\_\{\\mathrm\{EXP\}\}:=\\min\\\{\\frac\{\\tau\}\{1\-\\tau\},\\frac\{1\-\\tau\}\{\\tau\}\\\}\. For the soft quantile, we setκ=2\\kappa=2and varyμ∈\(0,1\)\\mu\\in\(0,1\)\. It is worth noting that, under these parameter choices, the soft quantile is neither convex nor concave over its entire domain, yet it still satisfies Assumption[4](https://arxiv.org/html/2607.23030#S4)\. Since both the loss functions for the expectile and soft quantile are piecewise linear and non\-differentiable at kink points, we use the left derivatives at those points for UBSR\-Newton\. Due to space limitation, we report the results for the soft quantile in Appendix[C\.1](https://arxiv.org/html/2607.23030#A3.SS1)\.

The algorithm’s performance is measured by theqq\-weighted distance\\norm​\\bmPhi​\\bmthetan−Π​Vq\\norm\{\\bmPhi\\bmtheta\_\{n\}\-\\Pi V\}\_\{q\}along the simulated trajectory, whereVVis computed by risk\-aware value iteration \(see Section 7 ofRuszczyński \([2010](https://arxiv.org/html/2607.23030#bib.bib35)\)\)\. Each algorithm is run independently 20 times for10610^\{6\}iterations, and the distance is averaged across the 20 trajectories at each iteration\.

#### 6\.1\.1Convergence Experiments ford=Nd=N

The first two rows of Figure[1](https://arxiv.org/html/2607.23030#S6.F1)show the convergence of UBSR\-TD, UBSR\-TD\(λ\\lambda\) and UBSR\-Newton \(labeled as TD\(0\.00\.0\), TD\(λ\\lambda\), Newton\) for the expectile whend=Nd=N\. The shaded regions represent the standard error of the first component of\\bmthetan\\bmtheta\_\{n\}\(\\bmtheta^n\\hat\{\\bmtheta\}\_\{n\}for UBSR\-Newton\) across 20 trajectories\. Under this setting, the features can recover the true value function\. The proposed algorithms are observed to converge to the true value function around10610^\{6\}iterations\. In case of UBSR\-TD, this occurs even when the discount\-factor restriction in Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)is not satisfied\. We can see that, UBSR\-Newton requires substantially fewer iterations than UBSR\-TD to reach a prescribed error threshold relative to the true value function\. In most settings, UBSR\-TD\(λ\\lambda\) converges faster than UBSR\-TD, with larger values ofλ\\lambdagenerally improving convergence, particularly for larger discount factors\. The standard error is relatively large in early iterations and gradually decreases as the algorithms converge\. As in the risk\-neutral setting, the variance of UBSR\-TD\(λ\\lambda\) increases withλ\\lambdaand UBSR\-Newton exhibits large variance during the early iterations possible due to the instability of\\bmH^n\\hat\{\\bmH\}\_\{n\}\.

#### 6\.1\.2Convergence Experiments ford<Nd<N

The last two rows of Figure[1](https://arxiv.org/html/2607.23030#S6.F1)report results for expectile withd=5<Nd=5<N, where the feature space cannot represent the true value function\. When the restriction onγ\\gammaholds, the proposed algorithms converge, but not necessarily to the projected value function\. As established in Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5), UBSR\-TD converges to the solution of \([9](https://arxiv.org/html/2607.23030#S3.E9)\)\. Therefore,\\norm​\\bmPhi​\\bmthetan−Π​Vq\\norm\{\\bmPhi\\bmtheta\_\{n\}\-\\Pi V\}\_\{q\}need not vanish\. UBSR\-Newton exhibits similar behavior\. When the restriction onγ\\gammafails, UBSR\-TD\(λ\\lambda\) may diverge, as observed forτ∈\{0\.6,0\.9\}\\tau\\in\\\{0\.6,0\.9\\\}andγ=0\.9\\gamma=0\.9\.

For expectile withτ=0\.5\\tau=0\.5, UBSR\-TD\(1\) reduces to TD\(1\), for which\\norm​\\bmPhi​\\bmthetan−Π​Vq\\norm\{\\bmPhi\\bmtheta\_\{n\}\-\\Pi V\}\_\{q\}is expected to converge to zero whend<Nd<N\(Tsitsiklis and Van Roy,[1997](https://arxiv.org/html/2607.23030#bib.bib1)\)\. However, this property generally fails in the risk\-aware setting\. Moreover, UBSR\-TD\(1\) need not achieve the smallest distance to the projected value function, as illustrated by the case whereτ=0\.6\\tau=0\.6andγ=0\.6\\gamma=0\.6\.

Overall, the experiments demonstrate the proposed algorithms’ ability to handle a broad range of risks and discount factors\. For practical applications, when the feature representation is imperfect, UBSR\-TD and UBSR\-Newton are practical choices: UBSR\-TD is better suited to low\-variance estimation, while UBSR\-Newton is preferred for faster convergence\.

![Refer to caption](https://arxiv.org/html/2607.23030v1/x1.png)

![Refer to caption](https://arxiv.org/html/2607.23030v1/x2.png)

Figure 1:Convergence results for expectile risk

### 6\.2Experiments on a Perishable Inventory Management Problem

Inventory management problems have been studied extensively\. When products are non\-perishable or have deterministic shelf lives, DP can often be used to compute optimal policies efficiently\(Nahmias,[2011](https://arxiv.org/html/2607.23030#bib.bib86)\)\. By contrast, stochastic shelf lives typically destroy classical structural properties, substantially increasing problem complexity and making standard heuristics, such as\(s,S\)\(s,S\)policies, generally suboptimal \(see Section 4 ofAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\)\)\. In large\-scale settings, exact DP also becomes computationally prohibitive because of the curse of dimensionality\. A common solution is approximate dynamic programming \(ADP\), in which the value function is approximated using low\-dimensional basis features\. Policy iteration is then carried out by alternating between policy improvement and policy evaluation steps\(Powell,[2011](https://arxiv.org/html/2607.23030#bib.bib87)\)\.

Stochastic shelf lives further motivate risk\-sensitive decision\-making in high\-stakes applications such as medical resource management\(Feng and Xiao,[2008](https://arxiv.org/html/2607.23030#bib.bib102); Hosseini\-Motlaghet al\.,[2019](https://arxiv.org/html/2607.23030#bib.bib105)\)\. Larger orders can improve service levels but increase the risk of wastage, whereas smaller orders reduce wastage but may result in severe shortages with significant medical consequences\. Motivated by these challenges, in this subsection, we propose UBSR\-based risk\-aware policy iteration algorithms within the ADP framework and apply it to the perishable platelet inventory system studied inAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\)\.

#### 6\.2\.1Model Formulation

The system state is defined as\\bmX=\(X1,⋯,Xm−1\)∈\\mcX⊂\\mbZ\+m−1\\bmX=\(X\_\{1\},\\cdots,X\_\{m\-1\}\)\\in\\mcX\\subset\\mbZ\_\{\+\}^\{m\-1\}, whereXiX\_\{i\}is the inventory level withiiperiods of remaining shelf life andmmis the maximum shelf life\. After observing the state, the decision\-maker ordersz∈\\mcZ:=\{0,⋯,z¯\}z\\in\\mcZ:=\\\{0,\\cdots,\\bar\{z\}\\\}\. The delivered units have random remaining shelf lives\\bmY=\(Y1,⋯,Ym\)\\bmY=\(Y\_\{1\},\\cdots,Y\_\{m\}\), with∑i=1mYi=z\\sum\_\{i=1\}^\{m\}Y\_\{i\}=z\. Conditional onzz, each unit independently has shelf lifeiiwith probabilitypi​\(z\)p\_\{i\}\(z\)under a multinomial logit model\. The random demandDDfollows a truncated negative binomial distribution\. See Section 6\.1 ofAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\)for details on the shelf\-life and demand distributions\.

An admissible policyμ:\\mcX→\\mcZ\\mu:\\mcX\\to\\mcZspecifies the order quantity for each state\. In each period, the decision\-maker observes the inventory state, places an order, and receives the delivery immediately\. Demand is subsequently realized and satisfied according to a first\-expire\-first\-out policy\. Unmet demand is lost, and each remaining unit loses one period of shelf life when the period ends\.

Given a state\\bmx=\(x1,…,xm−1\)∈\\mcX\\bmx=\(x\_\{1\},\\dots,x\_\{m\-1\}\)\\in\\mcXand policyμ\\mu, the next state\\bmX=\(X1,…,Xm−1\)\\bmX=\(X\_\{1\},\\dots,X\_\{m\-1\}\)evolves according to

Xj\\displaystyle X\_\{j\}:=\(xj\+1\+Yj\+1−\(D−∑i=1j\(xi\+Yi\)\)\+\)\+,j=1,…,m−2,\\displaystyle=\\Bigg\(x\_\{j\+1\}\+Y\_\{j\+1\}\-\\Big\(D\-\\sum\_\{i=1\}^\{j\}\(x\_\{i\}\+Y\_\{i\}\)\\Big\)^\{\+\}\\Bigg\)^\{\+\},\\quad j=1,\\dots,m\-2,\(27\)Xm−1\\displaystyle X\_\{m\-1\}:=\(Ym−\(D−∑i=1m−1\(xi\+Yi\)\)\+\)\+,\\displaystyle=\\Bigg\(Y\_\{m\}\-\\Big\(D\-\\sum\_\{i=1\}^\{m\-1\}\(x\_\{i\}\+Y\_\{i\}\)\\Big\)^\{\+\}\\Bigg\)^\{\+\},where\\bmY=\(Y1,…,Ym\)\\bmY=\(Y\_\{1\},\\dots,Y\_\{m\}\)denotes the random vector of received products under the orderμ​\(𝒙\)\\mu\(\\bm\{x\}\)\.

The one\-stage cost function is defined as

c​\(\\bmX,μ​\(\\bmX\)\):=\\displaystyle c\(\\bmX,\\mu\(\\bmX\)\)=c1​𝟏\{μ​\(\\bmX\)\>0\}\+c2​\(∑i=1m−1Xi\+μ​\(\\bmX\)−D\)\+\\displaystyle c\_\{1\}\\bm\{1\}\_\{\\\{\\mu\(\\bmX\)\>0\\\}\}\+c\_\{2\}\\left\(\\sum\_\{i=1\}^\{m\-1\}X\_\{i\}\+\\mu\(\\bmX\)\-D\\right\)^\{\+\}\(28\)\+c3​\(D−∑i=1m−1Xi−μ​\(\\bmX\)\)\+\+c4​\(X1\+Y1−D\)\+,\\displaystyle\+c\_\{3\}\\left\(D\-\\sum\_\{i=1\}^\{m\-1\}X\_\{i\}\-\\mu\(\\bmX\)\\right\)^\{\+\}\+c\_\{4\}\\left\(X\_\{1\}\+Y\_\{1\}\-D\\right\)^\{\+\},wherec1c\_\{1\},c2c\_\{2\},c3c\_\{3\},c4c\_\{4\}represent the fixed ordering, holding, shortage, and wastage costs, respectively\.

Our objective is to determine an optimal policy minimizing the infinite\-horizon discounted total risk \([3](https://arxiv.org/html/2607.23030#S2.E3)\) associated with the cost function \([28](https://arxiv.org/html/2607.23030#S6.E28)\) under the dynamic expectile risk\.

#### 6\.2\.2Approximate Policy Iteration

For a maximum inventory level of2020, the perishable inventory system has\(19\+mm−1\)=m​\(m\+1\)​⋯​\(m\+19\)20\!\\binom\{19\+m\}\{m\-1\}=\\frac\{m\(m\+1\)\\cdots\(m\+19\)\}\{20\!\}states\. The state\-space size grows polynomially asmmincreases, making explicit value iteration computationally expensive\.

We employ a linear function approximation of the value function:V~​\(\\bmx\):=∑i=1dθi​ϕi​\(\\bmx\)\\tilde\{V\}\(\\bmx\):=\\sum\_\{i=1\}^\{d\}\\theta\_\{i\}\\phi\_\{i\}\(\\bmx\),\\bmx∈\\mcX\\bmx\\in\\mcX, where\{ϕi\}i=1d\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{d\}are predefined basis functions\. FollowingAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\), we setϕ1​\(\\bmx\)=1\\phi\_\{1\}\(\\bmx\)=1andϕ2​\(𝒙\)=V^​\(∑i=1m−1xi\)\\phi\_\{2\}\(\\bm\{x\}\)=\\hat\{V\}\(\\sum\_\{i=1\}^\{m\-1\}x\_\{i\}\), whereV^\\hat\{V\}is the value function of the associated risk\-aware non\-perishable inventory problem, which can be computed efficiently via value iteration\. The remaining features capture the additional value structure induced by stochastic shelf\-life dynamics that is not represented byV^\\hat\{V\}\. We adopt the polynomial feature class Choice 4 of the state variables inAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\), comprisingxix\_\{i\},xi2x\_\{i\}^\{2\}, andxi​xjx\_\{i\}x\_\{j\}fori,j=1,…,m−1i,j=1,\\ldots,m\-1withi≠ji\\neq j\. All features are normalized to improve numerical stability and avoid computational scaling issues\.

Starting from an initial state\\bmx\\bmx, the policy improvement step at iterationnnis defined by

μn​\(\\bmx\):=\\argminz∈\\mcZ​\\SR​\[c​\(\\bmx,z\)\+γ​∑i=1dθn,i∗​ϕi​\(\\bmXμn−1\)\],\\mu\_\{n\}\(\\bmx\):=\\argmin\_\{z\\in\\mcZ\}\\SR\\left\[c\(\\bmx,z\)\+\\gamma\\sum\_\{i=1\}^\{d\}\\theta\_\{n,i\}^\{\*\}\\phi\_\{i\}\(\\bmX^\{\\mu\_\{n\-1\}\}\)\\right\],whereμn\\mu\_\{n\}and\{θn,i∗\}i=1d\\\{\\theta\_\{n,i\}^\{\*\}\\\}\_\{i=1\}^\{d\}are the policy and weight parameters at iterationnn;\\bmXμn−1\\bmX^\{\\mu\_\{n\-1\}\}denotes the random next state generated by the transition dynamics in \([27](https://arxiv.org/html/2607.23030#S6.E27)\) under policyμn−1\\mu\_\{n\-1\}; andγ∈\(0,1\)\\gamma\\in\(0,1\)is the discount factor\. When the transition dynamic is unknown or exact policy improvement is costly, we use simulation or heuristics for policy improvement with a fixed number of samples and and run UBSR\-TD or UBSR\-Newton for a fixed number of policy\-evaluation iterations\.

For benchmark comparisons, we consider two policies: astaticpolicy derived from the non\-perishable model, corresponding to the classical\(s,S\)\(s,S\)policy, and amyopicpolicy that directly minimizes the risk associated with the one\-stage cost\.

#### 6\.2\.3Experimental Setup

We consider a perishable inventory system with maximum inventory2020, shelf lifem∈\{3,5,8\}m\\in\\\{3,5,8\\\}, and discount factorγ=0\.6\\gamma=0\.6, which satisfies the UBSR\-TD convergence conditions in Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)forτ∈\(3/8,5/8\)\\tau\\in\(3/8,5/8\)\. Demand follows the negative binomial distribution in Table 1 ofAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\), with mean6\.26\.2\. Shelf\-life parameters are\(1,0\.5,−0\.2,−0\.1\)\(1,0\.5,\-0\.2,\-0\.1\)form=3m=3and the endogenous settings in Table 2 ofAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\)form=5,8m=5,8, where the negative coefficients imply that larger orders increase the probability of receiving items with lower period of remaining shelf life\.

We collect 60,000 online samples for policy evaluation, divide them into 20 trajectories of length 3,000, and average the resulting weight estimates\. For UBSR\-Newton, we use the first 1,000 samples of each trajectory for warm\-up, which yields an invertible\\bmH^n0\\hat\{\\bmH\}\_\{n\_\{0\}\}in most cases\. Trajectories with singular\\bmH^n0\\hat\{\\bmH\}\_\{n\_\{0\}\}are discarded\. Empirically, this is observed to have negligible impact on the results\.

Form=3m=3, exact policy improvement is computationally negligible\. Form=5m=5, however, each exact improvement step takes hours\. We therefore perform one exact step to obtain a myopic baseline, followed by approximate improvement using 50 simulated transitions per state\. This reduces runtime from hours to minutes while preserving reasonable empirical performance\. We run policy iteration for 20 iterations\. Form=8m=8, exact policy evaluation takes over 10 hours, making exact policy comparisons impractical\. We therefore only compare the runtime and optimality gap of UBSR\-TD and UBSR\-Newton for a single policy evaluation step form=8m=8\. The runtime and optimality gap results for a single policy evaluation step are reported in Appendix[C\.2](https://arxiv.org/html/2607.23030#A3.SS2)\.

#### 6\.2\.4Experimental Results form=3m=3

The left panel of Figure[2](https://arxiv.org/html/2607.23030#S6.F2)shows the optimal risk\-aware policies form=3m=3underτ∈\{0\.1,0\.5,0\.9\}\\tau\\in\\\{0\.1,0\.5,0\.9\\\}, representing risk\-seeking, risk\-neutral, and risk\-averse policies, respectively, and three cost settings: the baseline\(10,1,20,5\)\(10,1,20,5\), high ordering cost\(50,1,20,5\)\(50,1,20,5\), and high wastage cost\(10,1,20,50\)\(10,1,20,50\)\. Detailed optimality\-gap results for different policies are reported in Appendix[C\.3](https://arxiv.org/html/2607.23030#A3.SS3)\. We observe that the optimal policy is no longer of the classical\(s,S\)\(s,S\)form\. Asτ\\tauincreases, the ordering region expands to higher inventory levels to reduce shortage risk\. High ordering costs shrink the ordering region but increase order sizes, whereas high wastage costs also shrink the ordering region while reducing order quantities\.

![Refer to caption](https://arxiv.org/html/2607.23030v1/x3.png)

![Refer to caption](https://arxiv.org/html/2607.23030v1/x4.png)

Figure 2:\(Left\) Optimal risk\-aware policies form=3m=3; \(Right\) Optimality gaps of policy iteration with UBSR\-TD and UBSR\-Newton \(TD and NT\) form=3m=3\.![Refer to caption](https://arxiv.org/html/2607.23030v1/x5.png)Figure 3:Empirical cumulative distributions of simulated costs under policies obtained via policy iteration with UBSR\-TD under different risk and cost settings whenm=3m=3The right panel of Figure[2](https://arxiv.org/html/2607.23030#S6.F2)reports the percentage optimality gap at the zero\-inventory state over policy iterations form=3m=3, relative to the true optimum computed by value iteration with tolerance0\.010\.01\. Both methods converge within about 10 iterations, with UBSR\-Newton \(blue\) converging faster than UBSR\-TD \(red\)\. After 20 iterations, both achieve gaps below0\.2%0\.2\\%, demonstrating the effectiveness of the ADP framework and the proposed policy iteration methods\.

Figure[3](https://arxiv.org/html/2607.23030#S6.F3)shows the empirical cumulative distributions of simulated costs under UBSR\-TD policies form=3m=3across different risk and cost settings\. The distributions reflect the corresponding risk attitudes: the risk\-seeking policy \(τ=0\.1\\tau=0\.1; red\) yields greater dispersion and more extreme costs, the risk\-averse policy \(τ=0\.9\\tau=0\.9; green\) produces a more concentrated distribution with fewer extremes, and the risk\-neutral policy \(τ=0\.5\\tau=0\.5; blue\) lies between the two and minimizes the expectation\.

Moreover, we observe that higher wastage costs diminish the influence of risk awareness on the optimal policy\. Whenc4=50c\_\{4\}=50, the risk\-aware policies for differentτ\\tauvalues become similar in Figure[2](https://arxiv.org/html/2607.23030#S6.F2), producing nearly identical cost distributions in Figure[3](https://arxiv.org/html/2607.23030#S6.F3)\. This occurs because when wastage costs are dominating, the optimal policy constrains the inventory to a narrow range around77, close to the expected demand of6\.26\.2\.

Table 1:Results under varying policies, risk parameters, and cost settings form=5m=5Costτ\\tau0\.10\.40\.50\.60\.9\(10,1,20,5\)Optimal31\.2338\.4440\.2342\.3852\.98Static31\.30\(0\.24%\)38\.53\(0\.24%\)40\.33\(0\.25%\)42\.43\(0\.13%\)55\.50\(4\.75%\)Myopic31\.86\(2\.02%\)40\.03\(4\.15%\)41\.23\(2\.47%\)44\.01\(3\.84%\)54\.19\(2\.27%\)RN33\.18\(6\.27%\)38\.60\(0\.43%\)\-\-42\.55\(0\.39%\)66\.04\(24\.65%\)TD31\.30\(0\.24%\)38\.53\(0\.24%\)40\.43\(0\.49%\)42\.40\(0\.05%\)54\.13\(2\.16%\)Newton31\.30\(0\.24%\)38\.53\(0\.24%\)40\.43\(0\.49%\)42\.40\(0\.05%\)53\.79\(1\.54%\)\(80,1,20,5\)Optimal120\.40132\.51136\.13140\.21165\.96Static120\.50\(0\.09%\)132\.60\(0\.07%\)136\.14\(0\.01%\)140\.22\(0\.01%\)166\.05\(0\.05%\)Myopic188\.46\(56\.53%\)162\.65\(22\.75%\)165\.49\(21\.57%\)173\.77\(23\.93%\)200\.82\(21\.00%\)RN121\.66\(1\.05%\)132\.60\(0\.07%\)\-\-140\.37\(0\.11%\)170\.86\(2\.95%\)TD120\.70\(0\.25%\)132\.60\(0\.07%\)136\.14\(0\.01%\)140\.23\(0\.01%\)166\.04\(0\.05%\)Newton120\.41\(0\.01%\)132\.60\(0\.07%\)136\.14\(0\.01%\)140\.22\(0\.01%\)166\.04\(0\.05%\)\(10,1,20,80\)Optimal31\.3839\.6442\.5546\.2384\.09Static31\.46\(0\.24%\)40\.07\(1\.08%\)43\.30\(1\.76%\)50\.46\(9\.15%\)153\.24\(82\.23%\)Myopic31\.95\(1\.81%\)40\.69\(2\.63%\)42\.82\(0\.63%\)46\.51\(0\.60%\)101\.66\(20\.90%\)RN33\.17\(5\.70%\)39\.88\(0\.60%\)\-\-46\.33\(0\.22%\)87\.66\(4\.24%\)TD31\.46\(0\.24%\)39\.76\(0\.29%\)42\.64\(0\.21%\)46\.49\(0\.55%\)84\.56\(0\.56%\)Newton31\.46\(0\.24%\)39\.74\(0\.25%\)42\.63\(0\.17%\)46\.33\(0\.21%\)84\.14\(0\.06%\)

#### 6\.2\.5Experimental Results form=5m=5

As discussed in Section[6\.2\.2](https://arxiv.org/html/2607.23030#S6.SS2.SSS2),m=5m=5corresponds to a large\-scale setting: exact value iteration takes about five hours to reach a precision of0\.10\.1across the test instances, whereas the proposed policy iterations finish within one hour\.

Table[1](https://arxiv.org/html/2607.23030#S6.T1)reports exact evaluations of policies obtained by policy iterations across different risk and cost settings, with static, myopic, and risk\-neutral \(RN\) policies included as benchmarks\. Further results on cost instances and discussions are reported in Appendix[C\.3](https://arxiv.org/html/2607.23030#A3.SS3)\. Optimality gaps are shown in parentheses\. We observe that, the policy iteration methods achieve satisfactory optimality gaps across all scenarios: at worst2\.16%2\.16\\%for UBSR\-TD and1\.54%1\.54\\%for UBSR\-Newton, compared with82\.23%82\.23\\%,56\.53%56\.53\\%, and24\.65%24\.65\\%for the static, myopic, and risk\-neutral benchmarks\. Forτ=0\.1\\tau=0\.1andτ=0\.9\\tau=0\.9, the risk\-aware policies consistently outperform the risk\-neutral policy, with maximum improvements exceeding5%5\\%and18%18\\%, highlighting the value of risk\-aware control\.

Overall, these results demonstrate that the proposed ADP framework with policy iteration using UBSR\-TD and UBSR\-Newton achieves robust performance across a wide range of scenarios, substantially outperforming static, myopic, and risk\-neutral approaches\.

## 7Conclusions

In this work, we propose the first online policy evaluation algorithm for MDPs with dynamic UBSR measures under linear function approximation, the UBSR\-TD algorithm, prove its almost sure convergence, and introduce several variants designed to accelerate convergence\. Numerical experiments support our findings, and an application to perishable inventory management under shelf\-life uncertainty highlights the effectiveness and practical value of the proposed methods\.

Several directions worth further investigation\. First, extending the framework to nonlinear function approximation, such as neural networks, is a natural next step\. Second, relaxing the current theoretical restrictions on the discount factor remains an important open problem, as the existing bound is likely conservative\. Finally, developing theoretical analyses for the proposed algorithmic extensions is another promising direction for future research\.

## Acknowledgments

Weikai Wang is partially supported by IVADO and the Fonds de recherche du Québec \[2007773\]\. Erick Delage is partially supported by the Natural Sciences and Engineering Research Council of Canada \[Grant RGPIN\-2022\-05261\]\.

## References

- Platelet inventory management with approximate dynamic programming\.INFORMS Journal on Computing38\(1\),pp\. 207–231\.Cited by:[§C\.3](https://arxiv.org/html/2607.23030#A3.SS3.p3.7),[3rd item](https://arxiv.org/html/2607.23030#S1.I1.i3.p1.1),[§6\.2\.1](https://arxiv.org/html/2607.23030#S6.SS2.SSS1.p1.11),[§6\.2\.2](https://arxiv.org/html/2607.23030#S6.SS2.SSS2.p2.12),[§6\.2\.3](https://arxiv.org/html/2607.23030#S6.SS2.SSS3.p1.8),[§6\.2](https://arxiv.org/html/2607.23030#S6.SS2.p1.1),[§6\.2](https://arxiv.org/html/2607.23030#S6.SS2.p2.1)\.
- P\. Artzner, F\. Delbaen, J\. Eber, and D\. Heath \(1999\)Coherent measures of risk\.Mathematical Finance9\(3\),pp\. 203–228\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p2.1)\.
- J\. Bas\-Serrano, S\. Curi, A\. Krause, and G\. Neu \(2021\)Logistic Q\-learning\.InProceedings of the 24th International Conference on Artificial Intelligence and Statistics,Cited by:[Remark 3\.1](https://arxiv.org/html/2607.23030#S3.Thmtheorem1.p1.1.1)\.
- A\. Basu, T\. Bhattacharyya, and V\. S\. Borkar \(2008\)A learning algorithm for risk\-sensitive cost\.Mathematics of Operations Research33\(4\),pp\. 880–898\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- F\. Bellini and V\. Bignozzi \(2015\)On elicitable risk measures\.Quantitative Finance15\(5\),pp\. 725–733\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.23030#S2.SS1.p5.3),[Example 2\.3](https://arxiv.org/html/2607.23030#S2.Thmtheorem3.p1.6.6)\.
- V\. S\. Borkar, S\. Chen, A\. Devraj, I\. Kontoyiannis, and S\. Meyn \(2025\)The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning\.The Annals of Applied Probability35\(2\),pp\. 936–982\.Cited by:[Theorem B\.11](https://arxiv.org/html/2607.23030#A2.Thmtheorem11),[Appendix B](https://arxiv.org/html/2607.23030#A2.p4.1),[Appendix B](https://arxiv.org/html/2607.23030#A2.p5.5),[§4](https://arxiv.org/html/2607.23030#S4.p14.5),[§4](https://arxiv.org/html/2607.23030#S4.p17.6),[§4](https://arxiv.org/html/2607.23030#S4.p2.1),[§4](https://arxiv.org/html/2607.23030#S4.p20.2)\.
- V\. S\. Borkar \(2023\)Stochastic approximation: a dynamical systems viewpoint, 2nd edition\.Springer Singapore\.Cited by:[Proof B\.12](https://arxiv.org/html/2607.23030#A2.Thmtheorem12.p5.8.8)\.
- H\. Brezis \(2010\)Functional analysis, sobolev space and partial differential equations\.Springer,New York\.Cited by:[Proof B\.3](https://arxiv.org/html/2607.23030#A2.Thmtheorem3.p1.12.12)\.
- J\. Bu, X\. Gong, and X\. Chao \(2023\)Asymptotic optimality of base\-stock policies for perishable inventory systems\.Management Science69\(2\),pp\. 846–864\.Cited by:[3rd item](https://arxiv.org/html/2607.23030#S1.I1.i3.p1.1)\.
- S\. Chandak and V\. S\. Borkar \(2025\)A concentration bound for TD\(0\) with function approximation\.Stochastic Systems16\(1\),pp\. 44–60\.Cited by:[Proof B\.5](https://arxiv.org/html/2607.23030#A2.Thmtheorem5.p2.8.5)\.
- A\. Coache, S\. Jaimungal, and A\. Cartea \(2023\)Conditionally elicitable dynamic risk measures for deep reinforcement learning\.SIAM Journal on Financial Mathematics14\(4\),pp\. 1249–1289\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- A\. Coache and S\. Jaimungal \(2024\)Reinforcement learning with dynamic convex risk measures\.Mathematical Finance34\(2\),pp\. 557–587\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- C\. Dann, G\. Neumann, and J\. Peters \(2014\)Policy evaluation with temporal differences: a survey and comparison\.Journal of Machine Learning Research15\(1\),pp\. 809–883\.Cited by:[§2\.3](https://arxiv.org/html/2607.23030#S2.SS3.p5.1),[§5\.1](https://arxiv.org/html/2607.23030#S5.SS1.p1.1)\.
- S\. Emmer, M\. Kratz, and D\. Tasche \(2015\)What is the best risk measure in practice? a comparison of standard measures\.Journal of Risk18\(2\),pp\. 31–60\.Cited by:[§2\.1](https://arxiv.org/html/2607.23030#S2.SS1.p5.7)\.
- Y\. Fei, Z\. Yang, and Z\. Wang \(2021\)Risk\-sensitive reinforcement learning with function approximation: a debiasing approach\.InProceedings of the 38th International Conference on Machine Learning,pp\. 3198–3207\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p2.1)\.
- Y\. Feng and B\. Xiao \(2008\)A risk\-sensitive model for managing perishable products\.Operations Research56\(5\),pp\. 1305–1311\.Cited by:[3rd item](https://arxiv.org/html/2607.23030#S1.I1.i3.p1.1),[§6\.2](https://arxiv.org/html/2607.23030#S6.SS2.p2.1)\.
- H\. Föllmer and A\. Schied \(2016\)Stochastic finance: an introduction in discrete time, 4th edition\.Walter de Gruyter & Co\.,Berlin\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.23030#S2.SS1.p3.1),[Proposition 2\.6](https://arxiv.org/html/2607.23030#S2.Thmtheorem6)\.
- A\. Givchi and M\. Palhang \(2014\)Quasi Newton temporal difference learning\.InAsian Conference on Machine Learning,Cited by:[§5\.2](https://arxiv.org/html/2607.23030#S5.SS2.p1.6)\.
- J\. L\. Hau, E\. Delage, E\. Derman, M\. Ghavamzadeh, and M\. Petrik \(2025\)Q\-learning for quantile MDPs: a decomposition, performance, and convergence analysis\.InProceedings of the 28th International Conference on Artificial Intelligence and Statistics,Cited by:[Example 2\.5](https://arxiv.org/html/2607.23030#S2.Thmtheorem5.p1.3.1)\.
- S\. Hosseini\-Motlagh, M\. R\. G\. Samani, and S\. Homaei \(2019\)Blood supply chain management: robust optimization, disruption risk, and blood group compatibility \(a real\-life case\)\.Journal of Ambient Intelligence and Humanized Computing11,pp\. 1085–1104\.Cited by:[§6\.2](https://arxiv.org/html/2607.23030#S6.SS2.p2.1)\.
- Z\. Hu and D\. Zhang \(2018\)Utility\-based shortfall risk: efficient computations via Monte Carlo\.Naval Research Logistics65\(5\),pp\. 378–392\.Cited by:[§4](https://arxiv.org/html/2607.23030#S4.p10.1)\.
- A\. Huang, L\. Leqi, Z\. C\. Lipton,et al\.\(2021\)On the convergence and optimality of policy gradient for Markov coherent risk\.arXiv preprint arXiv:2103\.02827\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- U\. Köse and A\. Ruszczyński \(2021\)Risk\-averse learning by temporal difference methods with Markov risk measures\.Journal of Machine Learning Research22\(38\),pp\. 1–34\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1),[Remark 4\.2](https://arxiv.org/html/2607.23030#S4.Thmtheorem2.p1.12.12),[Example 4\.6](https://arxiv.org/html/2607.23030#S4.Thmtheorem6.p2.8.8),[§5\.1](https://arxiv.org/html/2607.23030#S5.SS1.p3.5)\.
- T\. Lam, A\. Verma, B\. K\. H\. Low, and P\. Jaillet \(2022\)Risk\-aware reinforcement learning with coherent risk measures and non\-linear function approximation\.InThe Eleventh International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p2.1)\.
- S\. D\. Liu, S\. Chen, and S\. Zhang \(2025a\)The ODE method for stochastic approximation and reinforcement learning with Markovian noise\.Journal of Machine Learning Research26\(24\),pp\. 1–76\.Cited by:[§4](https://arxiv.org/html/2607.23030#S4.p14.5),[§4](https://arxiv.org/html/2607.23030#S4.p17.6),[§4](https://arxiv.org/html/2607.23030#S4.p20.2)\.
- W\. Liu, J\. Tu, X\. Chen, and Y\. Zhang \(2025b\)Online estimation and inference for robust policy evaluation in reinforcement learning\.The Annals of Statistics53\(5\),pp\. 2128–2152\.Cited by:[Remark 3\.1](https://arxiv.org/html/2607.23030#S3.Thmtheorem1.p1.1.1),[§5\.2](https://arxiv.org/html/2607.23030#S5.SS2.p2.1),[§5\.2](https://arxiv.org/html/2607.23030#S5.SS2.p3.5),[§5\.2](https://arxiv.org/html/2607.23030#S5.SS2.p5.1),[§5\.2](https://arxiv.org/html/2607.23030#S5.SS2.p6.1)\.
- Y\. Luo and E\. Delage \(2026\)Actor\-critic algorithm for dynamic expectile and CVaR\.arXiv preprint arXiv:2605\.07857\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- S\. Marzban, E\. Delage, and J\. Y\. Li \(2023\)Deep reinforcement learning for option pricing and hedging under dynamic expectile risk measures\.Quantitative Finance23\(10\),pp\. 1411–1430\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- V\. Mnih, K\. Kavukcuoglu, D\. Silver,et al\.\(2015\)Human\-level control through deep reinforcement learning\.Nature518\(7540\),pp\. 529–533\.Cited by:[Remark 3\.1](https://arxiv.org/html/2607.23030#S3.Thmtheorem1.p1.1.1)\.
- S\. Nahmias \(2011\)Perishable inventory systems\.Springer Science & Business Media,New York\.Cited by:[3rd item](https://arxiv.org/html/2607.23030#S1.I1.i3.p1.1),[§6\.2](https://arxiv.org/html/2607.23030#S6.SS2.p1.1)\.
- L\. Ouyang, J\. Wu, X\. Jiang,et al\.\(2022\)Training language models to follow instructions with human feedback\.Advances in Neural Information Processing Systems35\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p1.1)\.
- Y\. Pan, A\. White, and M\. White \(2017\)Accelerated gradient temporal difference learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.31\.Cited by:[§5\.2](https://arxiv.org/html/2607.23030#S5.SS2.p1.6)\.
- S\. R\. Pathy and H\. Rahimian \(2024\)Value of risk aversion in perishable products supply chain management\.Computational Optimization and Applications89,pp\. 517–552\.Cited by:[3rd item](https://arxiv.org/html/2607.23030#S1.I1.i3.p1.1)\.
- W\. B\. Powell \(2011\)Approximate dynamic programming: solving the curses of dimensionality, 2nd edition\.Wiley\.Cited by:[§6\.2](https://arxiv.org/html/2607.23030#S6.SS2.p1.1)\.
- A\. Ruszczyński \(2010\)Risk\-averse dynamic programming for Markov decision processes\.Mathematical Programming, Series B125\(2\),pp\. 235–261\.Cited by:[§2\.2](https://arxiv.org/html/2607.23030#S2.SS2.p3.1),[§6\.1](https://arxiv.org/html/2607.23030#S6.SS1.p3.4)\.
- A\. Shapiro, D\. Dentcheva, and A\. Ruszczynski \(2021\)Lectures on stochastic programming: modeling and theory, 2nd edition\.MOS\-SIAM Series on Optimization,SIAM\.Cited by:[§2\.1](https://arxiv.org/html/2607.23030#S2.SS1.p1.2)\.
- Y\. Shen, W\. Stannat, and K\. Obermayer \(2013\)Risk\-sensitive Markov control processes\.SIAM Journal on Control and Optimization51\(5\),pp\. 3652–3672\.Cited by:[§2\.2](https://arxiv.org/html/2607.23030#S2.SS2.p4.1),[§2\.2](https://arxiv.org/html/2607.23030#S2.SS2.p5.8),[Definition 2\.7](https://arxiv.org/html/2607.23030#S2.Thmtheorem7)\.
- Y\. Shen, M\. J\. Tobia, T\. Sommer, and K\. Obermayer \(2014\)Risk\-sensitive reinforcement learning\.Neural Computation26\(7\),pp\. 1298–1328\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p3.1),[§1](https://arxiv.org/html/2607.23030#S1.p4.1),[§2\.1](https://arxiv.org/html/2607.23030#S2.SS1.p3.1),[§3](https://arxiv.org/html/2607.23030#S3.p2.4),[§3](https://arxiv.org/html/2607.23030#S3.p2.5),[Remark 4\.2](https://arxiv.org/html/2607.23030#S4.Thmtheorem2.p1.12.12),[§4](https://arxiv.org/html/2607.23030#S4.p10.1)\.
- D\. Silver, J\. Schrittwieser, K\. Simonyan,et al\.\(2017\)Mastering the game of go without human knowledge\.Nature550\(7676\),pp\. 354–359\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p1.1)\.
- R\. S\. Sutton and A\. G\. Barto \(2018\)Reinforcement learning: an introduction, 2nd edition\.MIT Press,Cambridge, MA\.Cited by:[2nd item](https://arxiv.org/html/2607.23030#S1.I1.i2.p1.1),[§1](https://arxiv.org/html/2607.23030#S1.p1.1),[§2\.3](https://arxiv.org/html/2607.23030#S2.SS3.p3.3),[§2\.3](https://arxiv.org/html/2607.23030#S2.SS3.p4.11),[§5\.1](https://arxiv.org/html/2607.23030#S5.SS1.p1.1),[§5](https://arxiv.org/html/2607.23030#S5.p1.1)\.
- A\. Tamar, Y\. Chow, M\. Ghavamzadeh, and S\. Mannor \(2015\)Policy gradient for coherent risk measures\.Advances in Neural Information Processing Systems28\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p2.1),[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- J\. N\. Tsitsiklis and B\. Van Roy \(1997\)An analysis of temporal\-difference learning with function approximation\.IEEE Transactions on Automatic Control42\(5\),pp\. 674–690\.Cited by:[§4](https://arxiv.org/html/2607.23030#S4.p2.1),[§4](https://arxiv.org/html/2607.23030#S4.p20.2),[§4](https://arxiv.org/html/2607.23030#S4.p5.4),[§6\.1\.2](https://arxiv.org/html/2607.23030#S6.SS1.SSS2.p2.5)\.
- W\. Wang and E\. Delage \(2025\)Planning and learning in average risk\-aware MDPs\.InAdvances in Neural Information Processing Systems,Vol\.38\.Cited by:[Lemma B\.6](https://arxiv.org/html/2607.23030#A2.Thmtheorem6),[§4](https://arxiv.org/html/2607.23030#S4.p10.1)\.
- Y\. Wang and M\. P\. Chapman \(2022\)Risk\-averse autonomous systems: a brief history and recent developments from the perspective of optimal control\.Artificial Intelligence311,pp\. 103743\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p2.1)\.
- S\. Yalçındağ, S\. B\. Güre, G\. Carello, and E\. Lanzarone \(2020\)A stochastic risk\-averse framework for blood donation appointment scheduling under uncertain donor arrivals\.Health Care Management Science23,pp\. 535–555\.Cited by:[3rd item](https://arxiv.org/html/2607.23030#S1.I1.i3.p1.1)\.
- P\. Yu, W\. B\. Haskell, and H\. Xu \(2018\)Approximate value iteration for risk\-aware Markov decision processes\.IEEE Transactions on Automatic Control63\(9\),pp\. 3135–3142\.Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p4.1)\.
- R\. Zhang, Y\. Hu, and N\. Li \(2024\)Soft robust MDPs and risk\-sensitive mdps: equivalence, policy gradient, and sample complexity\.InThe Twelfth International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2607.23030#S1.p2.1)\.

## Appendices

## Appendix AAlgorithm Pseudo\-codes

Input:Online streaming data

\{Xn\}n≥0\\\{X\_\{n\}\\\}\_\{n\\geq 0\}, initial parameter

\\bmtheta0\\bmtheta\_\{0\},

γ∈\(0,1\)\\gamma\\in\(0,1\), step size

\{ηn\}n≥0\\\{\\eta\_\{n\}\\\}\_\{n\\geq 0\}, training horizon

TT
Output:Finial estimator

\\bmthetaT\\bmtheta\_\{T\}
1

2for*n=0n=0toT−1T\-1*do

3Compute

\\bmthetan\+1\\bmtheta\_\{n\+1\}through \([10](https://arxiv.org/html/2607.23030#S3.E10)\)\.

4end for

Algorithm 1UBSR\-TD AlgorithmInput:Online streaming data

\{Xn\}n≥0\\\{X\_\{n\}\\\}\_\{n\\geq 0\}, initial parameter

\\bmtheta0\\bmtheta\_\{0\},

λ∈\[0,1\]\\lambda\\in\[0,1\],

γ∈\(0,1\)\\gamma\\in\(0,1\), step size

\{ηn\}n≥0\\\{\\eta\_\{n\}\\\}\_\{n\\geq 0\}, training horizon

TT
Output:Finial estimator

\\bmthetaT\\bmtheta\_\{T\}
1

2Set

\\bmzeta0=\\bmphi​\(X0\)\\bmzeta\_\{0\}=\\bmphi\(X\_\{0\}\)\.

3for*n=0n=0toT−1T\-1*do

4

5Compute

\\bmthetan\+1\\bmtheta\_\{n\+1\}through \([18](https://arxiv.org/html/2607.23030#S5.E18)\)\.

6Compute

\\bmzetan\+1\\bmzeta\_\{n\+1\}through \([17](https://arxiv.org/html/2607.23030#S5.E17)\)

7end for

Algorithm 2UBSR\-TD\(λ\\lambda\) AlgorithmInput:Online streaming data

\{\(\\bmXn,\\bmZn,cn\)\}n≥1\\\{\(\\bmX\_\{n\},\\bmZ\_\{n\},c\_\{n\}\)\\\}\_\{n\\geq 1\}, initialization step

n0≥dn\_\{0\}\\geq d, initial parameter

\\bmtheta^0\\hat\{\\bmtheta\}\_\{0\},

γ∈\(0,1\)\\gamma\\in\(0,1\), training horizon

TT
Output:Finial estimator

\\bmtheta^T\\hat\{\\bmtheta\}\_\{T\}
1

2Compute

\\bmH^n0−1\\hat\{\\bmH\}\_\{n\_\{0\}\}^\{\-1\}and

\\bmLn0\\bmL\_\{n\_\{0\}\}according to \([21](https://arxiv.org/html/2607.23030#S5.E21)\)\.

3Set

\\bmtheta¯n0=\\bmtheta^n0=\\bmtheta^0\\bar\{\\bmtheta\}\_\{n\_\{0\}\}=\\hat\{\\bmtheta\}\_\{n\_\{0\}\}=\\hat\{\\bmtheta\}\_\{0\}\.

4for*n=n0\+1n=n\_\{0\}\+1toTT*do

5Compute

\\bmtheta¯n\\bar\{\\bmtheta\}\_\{n\}through \([23](https://arxiv.org/html/2607.23030#S5.E23)\)\.

6Compute

\\bmLn\\bmL\_\{n\}and

\\bmH^n−1\\hat\{\\bmH\}\_\{n\}^\{\-1\}through \([24](https://arxiv.org/html/2607.23030#S5.E24)\) and \([26](https://arxiv.org/html/2607.23030#S5.E26)\)\.

7Update the parameter estimate

\\bmtheta^n\\hat\{\\bmtheta\}\_\{n\}through \([22](https://arxiv.org/html/2607.23030#S5.E22)\)\.

8end for

Algorithm 3UBSR\-Newton Algorithm
## Appendix BOmitted Proofs in Section[4](https://arxiv.org/html/2607.23030#S4)

###### Proof B\.1\(Proof of Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1)\)\.

We first show that\\mcH\\mcHis a contraction on\(\\mcL\(\\mcX\),\\norm⋅q\)\(\\mcL\(\\mcX\),\\norm\{\\cdot\}\_\{q\}\)\.

By Assumption[4](https://arxiv.org/html/2607.23030#S4)and the monotonicity ofℓ\\ell, for anya,b∈\\mbRa,b\\in\\mbR, there exists someξ\(a,b\)∈\[ϵ1,L1\]\\xi\_\{\(a,b\)\}\\in\[\\epsilon\_\{1\},L\_\{1\}\]such thatℓ​\(a\)−ℓ​\(b\)=ξ\(a,b\)​\(a−b\)\\ell\(a\)\-\\ell\(b\)=\\xi\_\{\(a,b\)\}\(a\-b\)\. Using this property, for anyV1,V2∈\\mcL​\(\\mcX\)V\_\{1\},V\_\{2\}\\in\\mcL\(\\mcX\), there exists someξ\(x,x′\):=ξ\(x,x′,V1,V2\)∈\[ϵ1,L1\]\\xi\_\{\(x,x^\{\\prime\}\)\}:=\\xi\_\{\(x,x^\{\\prime\},V\_\{1\},V\_\{2\}\)\}\\in\[\\epsilon\_\{1\},L\_\{1\}\]such that

\\norm​\\mcH​\(V1\)−\\mcH​\(V2\)q2\\displaystyle\\norm\{\\mcH\(V\_\{1\}\)\-\\mcH\(V\_\{2\}\)\}\_\{q\}^\{2\}=\\displaystyle=∑x∈\\mcXq\(x\)\(α∑x′∈\\mcXP\(x′\|x\)\(ℓ\(γV1\(x′\)−V1\(x\)\+c\(x\)\)−ℓ\(γV2\(x′\)−V2\(x\)\+c\(x\)\)\)\\displaystyle\\sum\_\{x\\in\\mcX\}q\(x\)\\Bigg\(\\alpha\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\Big\(\\ell\(\\gamma V\_\{1\}\(x^\{\\prime\}\)\-V\_\{1\}\(x\)\+c\(x\)\)\-\\ell\(\\gamma V\_\{2\}\(x^\{\\prime\}\)\-V\_\{2\}\(x\)\+c\(x\)\)\\Big\)\+V1\(x\)−V2\(x\)\)2\\displaystyle\\qquad\+V\_\{1\}\(x\)\-V\_\{2\}\(x\)\\Bigg\)^\{2\}=\\displaystyle=∑x∈\\mcXq​\(x\)​\(α​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′\)​\(γ​Δ​\(x′\)−Δ​\(x\)\)\+Δ​\(x\)\)2\\displaystyle\\sum\_\{x\\in\\mcX\}q\(x\)\\Bigg\(\\alpha\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\}\)\}\(\\gamma\\Delta\(x^\{\\prime\}\)\-\\Delta\(x\)\)\+\\Delta\(x\)\\Bigg\)^\{2\}=\\displaystyle=α2​∑x∈\\mcXq​\(x\)​\(∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′\)​\(γ​Δ​\(x′\)−Δ​\(x\)\)\)2\\displaystyle\\alpha^\{2\}\\sum\_\{x\\in\\mcX\}q\(x\)\\Bigg\(\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\}\)\}\(\\gamma\\Delta\(x^\{\\prime\}\)\-\\Delta\(x\)\)\\Bigg\)^\{2\}\+2​α​∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′\)​\(γ​Δ​\(x′\)−Δ​\(x\)\)​Δ​\(x\)\+∑x∈\\mcXq​\(x\)​\(Δ​\(x\)\)2\\displaystyle\+2\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\}\)\}\(\\gamma\\Delta\(x^\{\\prime\}\)\-\\Delta\(x\)\)\\Delta\(x\)\+\\sum\_\{x\\in\\mcX\}q\(x\)\(\\Delta\(x\)\)^\{2\}=:\\displaystyle=:α2​∑x∈\\mcXq​\(x\)​T1​\(x\)\+2​α​∑x∈\\mcXq​\(x\)​T2​\(x\)\+\\norm​Δq2,\\displaystyle\\alpha^\{2\}\\sum\_\{x\\in\\mcX\}q\(x\)T\_\{1\}\(x\)\+2\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)T\_\{2\}\(x\)\+\\norm\{\\Delta\}\_\{q\}^\{2\},where we defineΔ​\(x\):=V1​\(x\)−V2​\(x\)\\Delta\(x\):=V\_\{1\}\(x\)\-V\_\{2\}\(x\), for allx∈\\mcXx\\in\\mcX\. For the first term, we have

∑x∈\\mcXq​\(x\)​T1​\(x\)\\displaystyle\\sum\_\{x\\in\\mcX\}q\(x\)T\_\{1\}\(x\)≤∑x∈\\mcXq​\(x\)​\(∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′\)​\|γ​Δ​\(x′\)−Δ​\(x\)\|\)2\\displaystyle\\leq\\sum\_\{x\\in\\mcX\}q\(x\)\\left\(\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\}\)\}\|\\gamma\\Delta\(x^\{\\prime\}\)\-\\Delta\(x\)\|\\right\)^\{2\}≤∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​\(ξ\(x,x′\)​\|γ​Δ​\(x′\)−Δ​\(x\)\|\)2\\displaystyle\\leq\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\left\(\\xi\_\{\(x,x^\{\\prime\}\)\}\|\\gamma\\Delta\(x^\{\\prime\}\)\-\\Delta\(x\)\|\\right\)^\{2\}≤L12​∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​\(γ​Δ​\(x′\)−Δ​\(x\)\)2\\displaystyle\\leq L\_\{1\}^\{2\}\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\(\\gamma\\Delta\(x^\{\\prime\}\)\-\\Delta\(x\)\)^\{2\}=L12​∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​\(γ2​Δ2​\(x′\)\+Δ2​\(x\)−2​γ​Δ​\(x′\)​Δ​\(x\)\)\\displaystyle=L\_\{1\}^\{2\}\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\(\\gamma^\{2\}\\Delta^\{2\}\(x^\{\\prime\}\)\+\\Delta^\{2\}\(x\)\-2\\gamma\\Delta\(x^\{\\prime\}\)\\Delta\(x\)\)≤L12​\(1\+γ\)2​\\norm​Δq2,\\displaystyle\\leq L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\\norm\{\\Delta\}\_\{q\}^\{2\},where the second inequality follows from Jensen’s inequality; the third inequality follows from Assumption[4](https://arxiv.org/html/2607.23030#S4)and the last inequality from the invariant distribution equation and the Cauchy\-Schwarz inequality:

\|∑x∈\\mcXq\(x\)∑x′∈\\mcXP\(x′\|x\)Δ\(x′\)Δ\(x\)\|=\|\\mbE\[Δ\(X′\)Δ\(X\)\]\|≤\(\\mbE\[Δ2\(X′\)\]\\mbE\[Δ2\(X\)\]\)12=\\normΔq2,\\left\|\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\Delta\(x^\{\\prime\}\)\\Delta\(x\)\\right\|=\|\\mbE\[\\Delta\(X^\{\\prime\}\)\\Delta\(X\)\]\|\\leq\(\\mbE\[\\Delta^\{2\}\(X^\{\\prime\}\)\]\\mbE\[\\Delta^\{2\}\(X\)\]\)^\{\\frac\{1\}\{2\}\}=\\norm\{\\Delta\}\_\{q\}^\{2\},\(29\)whereX∼qX\\sim qandX′∼P\(⋅\|X\)X^\{\\prime\}\\sim P\(\\cdot\|X\)\. This inequality extends directly to thenn\-step case by replacingx′x^\{\\prime\}withxnx\_\{n\}andPPwith thenn\-step transition kernelPnP^\{n\}, yielding\|\\mbE​\[Δ​\(Xn\)​Δ​\(X\)\]\|≤\\norm​Δq2\|\\mbE\[\\Delta\(X\_\{n\}\)\\Delta\(X\)\]\|\\leq\\norm\{\\Delta\}\_\{q\}^\{2\}, since\(Pn\)⊤​q=q\(P^\{n\}\)^\{\\top\}q=qby the invariant distribution equation\.

For the second term, we have

∑x∈\\mcXq​\(x\)​T2​\(x\)\\displaystyle\\sum\_\{x\\in\\mcX\}q\(x\)T\_\{2\}\(x\)=∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′\)​\(γ​Δ​\(x′\)​Δ​\(x\)−Δ2​\(x\)\)\\displaystyle=\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\}\)\}\(\\gamma\\Delta\(x^\{\\prime\}\)\\Delta\(x\)\-\\Delta^\{2\}\(x\)\)≤∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′\)​\(γ2​\(Δ2​\(x′\)\+Δ2​\(x\)\)−Δ2​\(x\)\)≤\(γ​L1−ϵ1\)​\\norm​Δq2,\\displaystyle\\leq\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\}\)\}\\Big\(\\frac\{\\gamma\}\{2\}\(\\Delta^\{2\}\(x^\{\\prime\}\)\+\\Delta^\{2\}\(x\)\)\-\\Delta^\{2\}\(x\)\\Big\)\\leq\(\\gamma L\_\{1\}\-\\epsilon\_\{1\}\)\\norm\{\\Delta\}\_\{q\}^\{2\},where the first inequality follows from the AM\-GM inequalitya​b≤12​\(a2\+b2\)ab\\leq\\frac\{1\}\{2\}\(a^\{2\}\+b^\{2\}\), for alla,b∈\\mbRa,b\\in\\mbR, and the last inequality follows from the invariant distribution equation and Assumption[4](https://arxiv.org/html/2607.23030#S4)\.

As a result, we obtain that

\\norm​\\mcH​\(V1\)−\\mcH​\(V2\)q2≤\(α2​L12​\(1\+γ\)2\+2​α​\(γ​L1−ϵ1\)\+1\)​\\norm​Δq2\.\\norm\{\\mcH\(V\_\{1\}\)\-\\mcH\(V\_\{2\}\)\}\_\{q\}^\{2\}\\leq\\left\(\\alpha^\{2\}L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\+2\\alpha\(\\gamma L\_\{1\}\-\\epsilon\_\{1\}\)\+1\\right\)\\norm\{\\Delta\}\_\{q\}^\{2\}\.To ensure that\\mcH\\mcHis a contraction under\\norm⋅q\\norm\{\\cdot\}\_\{q\}, we require thatg​\(α\):=α2​L12​\(1\+γ\)2\+2​α​\(γ​L1−ϵ1\)\+1<1g\(\\alpha\):=\\alpha^\{2\}L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\+2\\alpha\(\\gamma L\_\{1\}\-\\epsilon\_\{1\}\)\+1<1\. This givesα<2​\(ϵ1−γ​L1\)L12​\(1\+γ\)2\\alpha<\\frac\{2\(\\epsilon\_\{1\}\-\\gamma L\_\{1\}\)\}\{L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\}\. Sinceα\>0\\alpha\>0, we require thatϵ1−γ​L1\>0\\epsilon\_\{1\}\-\\gamma L\_\{1\}\>0\. Moreover, we haveminα\>0⁡g​\(α\)=g​\(ϵ1−γ​L1L12​\(1\+γ\)2\)=−\(ϵ1−γ​L1\)2L12​\(1\+γ\)2\+1\>0\\min\_\{\\alpha\>0\}g\(\\alpha\)=g\(\\frac\{\\epsilon\_\{1\}\-\\gamma L\_\{1\}\}\{L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\}\)=\-\\frac\{\(\\epsilon\_\{1\}\-\\gamma L\_\{1\}\)^\{2\}\}\{L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\}\+1\>0\. Thereforeg​\(α\)∈\(0,1\)g\(\\alpha\)\\in\(0,1\)forα∈\(0,2​\(ϵ1−γ​L1\)L12​\(1\+γ\)2\)\\alpha\\in\(0,\\frac\{2\(\\epsilon\_\{1\}\-\\gamma L\_\{1\}\)\}\{L\_\{1\}^\{2\}\(1\+\\gamma\)^\{2\}\}\)\. By Banach’s fixed point theorem, there exists a unique fixed pointVVfor\\mcH\\mcHon\(\\mcL\(\\mcX\),\\norm⋅q\)\(\\mcL\(\\mcX\),\\norm\{\\cdot\}\_\{q\}\)such thatV=\\mcH​VV=\\mcH V\. This implies thatVVis also a solution to \([7](https://arxiv.org/html/2607.23030#S3.E7)\)\.

###### Proof B\.2\(Proof of Lemma[4\.3](https://arxiv.org/html/2607.23030#S4.Thmtheorem3)\)\.

By the Pythagorean theorem, for anyV∈\\mcL​\(\\mcX\)V\\in\\mcL\(\\mcX\), we have

\\norm​Vq2=\\norm​Π​Vq2\+\\norm​V−Π​Vq2,\\norm\{V\}\_\{q\}^\{2\}=\\norm\{\\Pi V\}\_\{q\}^\{2\}\+\\norm\{V\-\\Pi V\}\_\{q\}^\{2\},since⟨Π​V,V−Π​V⟩q=0\\langle\\Pi V,V\-\\Pi V\\rangle\_\{q\}=0\. By Theorem[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1),\\mcH\\mcHis a contraction under\\norm⋅q\\norm\{\\cdot\}\_\{q\}andΠ\\Piis non\-expansive, it follows thatΠ​\\mcH\\Pi\\mcHis a contraction on\(\\mcL\(\\mcX\),\\norm⋅q\)\(\\mcL\(\\mcX\),\\norm\{\\cdot\}\_\{q\}\)\. Hence, by Banach’s fixed point theorem,Π​\\mcH\\Pi\\mcHadmits a unique fixed point\. Moreover, by the definition of the projection operator and\{\\bmphii\}i=1d\\\{\\bmphi\_\{i\}\\\}\_\{i=1\}^\{d\}are linearly independent, this fixed point can be expressed as\\bmPhi​\\bmtheta∗\\bmPhi\\bmtheta^\{\*\}for some unique vector\\bmtheta∗∈\\mbRd\\bmtheta^\{\*\}\\in\\mbR^\{d\}\.

SinceV∈\\mcL​\(\\mcX\)V\\in\\mcL\(\\mcX\)and is the fixed point of\\mcH\\mcH, we have

\\norm​\\bmPhi​\\bmtheta∗−Π​Vq=\\norm​Π​\\mcH​\(\\bmPhi​\\bmtheta∗\)−Π​Vq≤\\norm​\\mcH​\(\\bmPhi​\\bmtheta∗\)−Vq=\\norm​\\mcH​\(\\bmPhi​\\bmtheta∗\)−\\mcH​Vq≤α¯​\\norm​\\bmPhi​\\bmtheta∗−Vq,\\norm\{\\bmPhi\\bmtheta^\{\*\}\-\\Pi V\}\_\{q\}=\\norm\{\\Pi\\mcH\(\\bmPhi\\bmtheta^\{\*\}\)\-\\Pi V\}\_\{q\}\\leq\\norm\{\\mcH\(\\bmPhi\\bmtheta^\{\*\}\)\-V\}\_\{q\}=\\norm\{\\mcH\(\\bmPhi\\bmtheta^\{\*\}\)\-\\mcH V\}\_\{q\}\\leq\\bar\{\\alpha\}\\norm\{\\bmPhi\\bmtheta^\{\*\}\-V\}\_\{q\},whereα¯\\bar\{\\alpha\}is the contraction factor for\\mcH\\mcH\. Note that

\\norm​\\bmPhi​\\bmtheta∗−Vq≤\\norm​\\bmPhi​\\bmtheta∗−Π​Vq\+\\norm​Π​V−Vq≤α¯​\\norm​\\bmPhi​\\bmtheta∗−Vq\+\\norm​Π​V−Vq\.\\norm\{\\bmPhi\\bmtheta^\{\*\}\-V\}\_\{q\}\\leq\\norm\{\\bmPhi\\bmtheta^\{\*\}\-\\Pi V\}\_\{q\}\+\\norm\{\\Pi V\-V\}\_\{q\}\\leq\\bar\{\\alpha\}\\norm\{\\bmPhi\\bmtheta^\{\*\}\-V\}\_\{q\}\+\\norm\{\\Pi V\-V\}\_\{q\}\.It follows that\\norm​\\bmPhi​\\bmtheta∗−Vq≤11−α¯​\\norm​Π​V−Vq\\norm\{\\bmPhi\\bmtheta^\{\*\}\-V\}\_\{q\}\\leq\\frac\{1\}\{1\-\\bar\{\\alpha\}\}\\norm\{\\Pi V\-V\}\_\{q\}\. This completes the proof\.

###### Proof B\.3\(Proof of Lemma[4\.4](https://arxiv.org/html/2607.23030#S4.Thmtheorem4)\)\.

From Lemma[4\.3](https://arxiv.org/html/2607.23030#S4.Thmtheorem3), we know that there exists a unique\\bmtheta∗∈\\mbRd\\bmtheta^\{\*\}\\in\\mbR^\{d\}such that\\bmPhi​\\bmtheta∗=Π​\\mcH​\(\\bmPhi​\\bmtheta∗\)\\bmPhi\\bmtheta^\{\*\}=\\Pi\\mcH\(\\bmPhi\\bmtheta^\{\*\}\), i\.e\.,\\bmPhi​\\bmtheta∗\\bmPhi\\bmtheta^\{\*\}is the unique fixed point forΠ​\\mcH\\Pi\\mcH\. From the Hilbert projection theorem \(Corollary 5\.4,Brezis \([2010](https://arxiv.org/html/2607.23030#bib.bib54)\)\), we know that⟨\\mcH​\(\\bmPhi​\\bmtheta∗\)−\\bmPhi​\\bmtheta∗,\\bmu⟩q=0\\langle\\mcH\(\\bmPhi\\bmtheta^\{\*\}\)\-\\bmPhi\\bmtheta^\{\*\},\\bmu\\rangle\_\{q\}=0for any\\bmu∈span​\(\\bmPhi\)\\bmu\\in\\mathrm\{span\}\(\\bmPhi\)\. Sinceq\>0q\>0, such\\bmPhi​\\bmtheta∗\\bmPhi\\bmtheta^\{\*\}is unique inspan​\(\\bmPhi\)\\mathrm\{span\}\(\\bmPhi\)\. Since\\bmPhi\\bmPhiis full rank,\\bmtheta∗\\bmtheta^\{\*\}is also unique\. This implies that\\bmtheta∗\\bmtheta^\{\*\}is the unique solution to

\\bmPhi⊤​\\diag​\(q\)​\(\\mcH​\(\\bmPhi​\\bmtheta∗\)−\\bmPhi​\\bmtheta∗\)=𝟎\.\\bmPhi^\{\\top\}\\diag\(q\)\(\\mcH\(\\bmPhi\\bmtheta^\{\*\}\)\-\\bmPhi\\bmtheta^\{\*\}\)=\\bm\{0\}\.\(30\)Recalling the definition of\\mcH\\mcH, \([30](https://arxiv.org/html/2607.23030#A2.E30)\) can be equivalently written as

∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ℓ​\(\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\\bmtheta∗\+c​\(x\)\)=𝟎\.\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta^\{\*\}\+c\(x\)\\right\)=\\bm\{0\}\.This implies that\\bmtheta∗\\bmtheta^\{\*\}is the unique solution of \([15](https://arxiv.org/html/2607.23030#S4.E15)\), i\.e\., the unique equilibrium of the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\)\. This completes the proof\.

Before proving Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5), we present several lemmas that are necessary to establish the theorem\. We first show that\\mcH^\\hat\{\\mcH\}defined in \([16](https://arxiv.org/html/2607.23030#S4.E16)\) is a contraction on\(\\mcL\(\\mbRd\),\\norm⋅2\)\(\\mcL\(\\mbR^\{d\}\),\\norm\{\\cdot\}\_\{2\}\)\.

###### Lemma B\.4\.

Under the assumptions of Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1), the operator\\mcH^\\hat\{\\mcH\}is a contraction on\(\\mcL\(\\mbRd\),\\norm⋅2\)\(\\mcL\(\\mbR^\{d\}\),\\norm\{\\cdot\}\_\{2\}\)\.

###### Proof B\.5\.

From \([30](https://arxiv.org/html/2607.23030#A2.E30)\) and Assumption[4](https://arxiv.org/html/2607.23030#S4), we know that for any\\bmtheta1,\\bmtheta2∈\\mbRd\\bmtheta\_\{1\},\\bmtheta\_\{2\}\\in\\mbR^\{d\}with\\bmtheta1≠\\bmtheta2\\bmtheta\_\{1\}\\neq\\bmtheta\_\{2\}, there exists someξ\(x,x′,\\bmtheta1,\\bmtheta2\)∈\[ϵ1,L1\]\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\\in\[\\epsilon\_\{1\},L\_\{1\}\]such that

\(\\bmtheta1−\\bmtheta2\)⊤​\\bmPhi⊤​\\diag​\(q\)​\(\\mcH​\(\\bmPhi​\\bmtheta1\)−\\bmPhi​\\bmtheta1−\\mcH​\(\\bmPhi​\\bmtheta2\)\+\\bmPhi​\\bmtheta2\)\\displaystyle\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\bmPhi^\{\\top\}\\diag\(q\)\(\\mcH\(\\bmPhi\\bmtheta\_\{1\}\)\-\\bmPhi\\bmtheta\_\{1\}\-\\mcH\(\\bmPhi\\bmtheta\_\{2\}\)\+\\bmPhi\\bmtheta\_\{2\}\)=\\displaystyle=\(\\bmtheta1−\\bmtheta2\)⊤α∑x∈\\mcXq\(x\)\\bmphi\(x\)∑x′∈\\mcXP\(x′\|x\)\{ℓ\(\(γ\\bmphi\(x′\)−\\bmphi\(x\)\)⊤\\bmtheta1\+c\(x\)\)\\displaystyle\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\Big\\\{\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\_\{1\}\+c\(x\)\\right\)−ℓ\(\(γ\\bmphi\(x′\)−\\bmphi\(x\)\)⊤\\bmtheta2\+c\(x\)\)\}\\displaystyle\\qquad\-\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\_\{2\}\+c\(x\)\\right\)\\Big\\\}=\\displaystyle=\(\\bmtheta1−\\bmtheta2\)⊤​α​∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\(\\bmtheta1−\\bmtheta2\)\\displaystyle\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)=\\displaystyle=α​\(\\bmtheta1−\\bmtheta2\)⊤​\\bmXi​\(\\bmtheta1,\\bmtheta2\)​\(\\bmtheta1−\\bmtheta2\),\\displaystyle\\alpha\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\),where we denote

\\bmXi​\(\\bmtheta1,\\bmtheta2\):=∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤∈\\mbRd×d\.\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\):=\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\in\\mbR^\{d\\times d\}\.\(31\)Putting\(\\bmtheta1−\\bmtheta2\)⊤\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}inside the summations, we have

α​\(\\bmtheta1−\\bmtheta2\)⊤​\\bmXi​\(\\bmtheta1,\\bmtheta2\)​\(\\bmtheta1−\\bmtheta2\)\\displaystyle\\alpha\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\(32\)=\\displaystyle=α​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​\(\\bmtheta1−\\bmtheta2\)⊤​\\bmphi​\(x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\(\\bmtheta1−\\bmtheta2\)\\displaystyle\\alpha\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\bmphi\(x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)=\\displaystyle=α​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​f\\bmdelta​\(x′\)​f\\bmdelta​\(x\)−f\\bmdelta2​\(x\)\)\\displaystyle\\alpha\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma f\_\{\\bmdelta\}\(x^\{\\prime\}\)f\_\{\\bmdelta\}\(x\)\-f\_\{\\bmdelta\}^\{2\}\(x\)\)≤\\displaystyle\\leqα​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​f\\bmdelta2​\(x′\)\+f\\bmdelta2​\(x\)2−f\\bmdelta2​\(x\)\)\\displaystyle\\alpha\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\\left\(\\gamma\\frac\{f\_\{\\bmdelta\}^\{2\}\(x^\{\\prime\}\)\+f\_\{\\bmdelta\}^\{2\}\(x\)\}\{2\}\-f\_\{\\bmdelta\}^\{2\}\(x\)\\right\)=\\displaystyle=α​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ2−1\)​f\\bmdelta2​\(x\)\\displaystyle\\alpha\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\\left\(\\frac\{\\gamma\}\{2\}\-1\\right\)f\_\{\\bmdelta\}^\{2\}\(x\)\+α​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​γ2​f\\bmdelta2​\(x′\)\\displaystyle\\qquad\+\\alpha\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\\frac\{\\gamma\}\{2\}f\_\{\\bmdelta\}^\{2\}\(x^\{\\prime\}\)≤\\displaystyle\\leqα​\(γ2−1\)​ϵ1​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​f\\bmdelta2​\(x\)\+α​γ​L12​∑x∈\\mcX∑x′∈\\mcXq​\(x\)​P​\(x′\|x\)​f\\bmdelta2​\(x′\)\\displaystyle\\alpha\\left\(\\frac\{\\gamma\}\{2\}\-1\\right\)\\epsilon\_\{1\}\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)f\_\{\\bmdelta\}^\{2\}\(x\)\+\\frac\{\\alpha\\gamma L\_\{1\}\}\{2\}\\sum\_\{x\\in\\mcX\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}q\(x\)P\(x^\{\\prime\}\|x\)f\_\{\\bmdelta\}^\{2\}\(x^\{\\prime\}\)=\\displaystyle=α​\(γ​\(ϵ1\+L1\)2−ϵ1\)​\\norm​f\\bmdeltaq2<0,\\displaystyle\\alpha\\left\(\\frac\{\\gamma\(\\epsilon\_\{1\}\+L\_\{1\}\)\}\{2\}\-\\epsilon\_\{1\}\\right\)\\norm\{f\_\{\\bmdelta\}\}\_\{q\}^\{2\}<0,where we denotef\\bmdelta​\(x\):=\\bmphi⊤​\(x\)​\\bmdelta∈\\mbRf\_\{\\bmdelta\}\(x\):=\\bmphi^\{\\top\}\(x\)\\bmdelta\\in\\mbRandf\\bmdelta:=\\bmPhi​\\bmdelta∈\\mbRNf\_\{\\bmdelta\}:=\\bmPhi\\bmdelta\\in\\mbR^\{N\}with\\bmdelta:=\\bmtheta1−\\bmtheta2∈\\mbRd\\bmdelta:=\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\\in\\mbR^\{d\}\. The first inequality follows from the AM\-GM inequality, the second inequality follows from the invariant distribution equalityP⊤​q=qP^\{\\top\}q=qand the exchange of sum overxxandx′x^\{\\prime\}, the last inequality follows from the fact that that we requireγ<ϵ1/L1\\gamma<\\epsilon\_\{1\}/L\_\{1\}, henceγ​\(ϵ1\+L1\)2−ϵ1<0\\frac\{\\gamma\(\\epsilon\_\{1\}\+L\_\{1\}\)\}\{2\}\-\\epsilon\_\{1\}<0\.

Before moving forward, we introduce an assumption on\\bmPhi\\bmPhi, which will be seen shortly to be non\-restrictive\. LetλM,λm\\lambda\_\{M\},\\lambda\_\{m\}denote the largest and smallest singular value of\\diag​\(q\)​\\bmPhi\\sqrt\{\\diag\(q\)\}\\bmPhi, and suppose that

0<λm≤λM<2​ϵ1−γ​\(ϵ1\+L1\)α2​L12​\(γ\+1\)2,0<\\lambda\_\{m\}\\leq\\lambda\_\{M\}<\\sqrt\{\\frac\{2\\epsilon\_\{1\}\-\\gamma\(\\epsilon\_\{1\}\+L\_\{1\}\)\}\{\\alpha^\{2\}L\_\{1\}^\{2\}\(\\gamma\+1\)^\{2\}\}\},whereα\>0\\alpha\>0is a constant satisfying the conditions of Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1)\. Here we haveλm\>0\\lambda\_\{m\}\>0since we have assumed that\\bmPhi\\bmPhihas full column rank andq\>0q\>0\. Because the feature vectors may be rescaled without altering the algorithm \(with the parameter vector\\bmtheta\\bmthetaget scaled accordingly\), this assumption entails no loss of generality \(also see Section 2\.1 inChandak and Borkar \([2025](https://arxiv.org/html/2607.23030#bib.bib61)\)\)\.

On the other hand, we have

\\norm​α​\\bmXi​\(\\bmtheta1,\\bmtheta2\)​\(\\bmtheta1−\\bmtheta2\)22\\displaystyle\\norm\{\\alpha\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\}\_\{2\}^\{2\}=\\displaystyle=\\norm​\\bmPhi⊤​\\diag​\(q\)​\(\\mcH​\(\\bmPhi​\\bmtheta1\)−\\bmPhi​\\bmtheta1−\\mcH​\(\\bmPhi​\\bmtheta2\)\+\\bmPhi​\\bmtheta2\)22\\displaystyle\\norm\{\\bmPhi^\{\\top\}\\diag\(q\)\(\\mcH\(\\bmPhi\\bmtheta\_\{1\}\)\-\\bmPhi\\bmtheta\_\{1\}\-\\mcH\(\\bmPhi\\bmtheta\_\{2\}\)\+\\bmPhi\\bmtheta\_\{2\}\)\}\_\{2\}^\{2\}=\\displaystyle=\\norm​\\bmPhi⊤​\\diag​\(q\)​\\diag​\(q\)​\(\\mcH​\(\\bmPhi​\\bmtheta1\)−\\bmPhi​\\bmtheta1−\\mcH​\(\\bmPhi​\\bmtheta2\)\+\\bmPhi​\\bmtheta2\)22\\displaystyle\\norm\{\\bmPhi^\{\\top\}\\sqrt\{\\diag\(q\)\}\\sqrt\{\\diag\(q\)\}\(\\mcH\(\\bmPhi\\bmtheta\_\{1\}\)\-\\bmPhi\\bmtheta\_\{1\}\-\\mcH\(\\bmPhi\\bmtheta\_\{2\}\)\+\\bmPhi\\bmtheta\_\{2\}\)\}\_\{2\}^\{2\}≤\\displaystyle\\leqλM2α2∑x∈\\mcX\(q​\(x\)∑x′∈\\mcXP\(x′\|x\)\(ℓ\(\(γ\\bmphi\(x′\)−\\bmphi\(x\)\)⊤\\bmtheta1\+c\(x\)\)\\displaystyle\\lambda\_\{M\}^\{2\}\\alpha^\{2\}\\sum\_\{x\\in\\mcX\}\\Bigg\(\\sqrt\{q\(x\)\}\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\Big\(\\ell\\big\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\_\{1\}\+c\(x\)\\big\)−ℓ\(\(γ\\bmphi\(x′\)−\\bmphi\(x\)\)⊤\\bmtheta2\+c\(x\)\)\)\)2\\displaystyle\\qquad\-\\ell\\big\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\_\{2\}\+c\(x\)\\big\)\\Big\)\\Bigg\)^\{2\}≤\\displaystyle\\leqλM2​α2​∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​\(ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\(\\bmtheta1−\\bmtheta2\)\)2\\displaystyle\\lambda\_\{M\}^\{2\}\\alpha^\{2\}\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\Bigg\(\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\\Bigg\)^\{2\}≤\\displaystyle\\leqλM2​α2​L12​∑x∈\\mcXq​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​\(γ​f\\bmdelta​\(x′\)−f\\bmdelta​\(x\)\)2\\displaystyle\\lambda\_\{M\}^\{2\}\\alpha^\{2\}L\_\{1\}^\{2\}\\sum\_\{x\\in\\mcX\}q\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\(\\gamma f\_\{\\bmdelta\}\(x^\{\\prime\}\)\-f\_\{\\bmdelta\}\(x\)\)^\{2\}≤\\displaystyle\\leqλM2​α2​L12​\(γ\+1\)2​\\norm​f\\bmdeltaq2,\\displaystyle\\lambda\_\{M\}^\{2\}\\alpha^\{2\}L\_\{1\}^\{2\}\(\\gamma\+1\)^\{2\}\\norm\{f\_\{\\bmdelta\}\}\_\{q\}^\{2\},where the first inequality follows from the definition of the spectral norm induced by the Euclidean norm, the second inequality is obtained using Assumption[4](https://arxiv.org/html/2607.23030#S4)together with Jensen’s inequality, and the final inequality is a consequence of the Cauchy\-Schwarz inequality \([29](https://arxiv.org/html/2607.23030#A2.E29)\)\.

Therefore, for any\\bmtheta1,\\bmtheta2∈\\mbRd\\bmtheta\_\{1\},\\bmtheta\_\{2\}\\in\\mbR^\{d\}with\\bmtheta1≠\\bmtheta2\\bmtheta\_\{1\}\\neq\\bmtheta\_\{2\}, we have

\\mcH^​\(\\bmtheta1\)−\\mcH^​\(\\bmtheta2\)\\displaystyle\\hat\{\\mcH\}\(\\bmtheta\_\{1\}\)\-\\hat\{\\mcH\}\(\\bmtheta\_\{2\}\)=\\displaystyle=α​∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​\(ℓ​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\\bmtheta1\+c​\(x\)\)\\displaystyle\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\Bigg\(\\ell\\left\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\_\{1\}\+c\(x\)\\right\)−ℓ\(γ\\bmphi\(x′\)−\\bmphi\(x\)\)⊤\\bmtheta2\+c\(x\)\)\)\+\\bmtheta1−\\bmtheta2\\displaystyle\\qquad\-\\ell\\left\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\_\{2\}\+c\(x\)\\right\)\\Bigg\)\+\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}=\\displaystyle=α​∑x∈\\mcXq​\(x\)​\\bmphi​\(x\)​∑x′∈\\mcXP​\(x′\|x\)​ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\(\\bmtheta1−\\bmtheta2\)\+\\bmtheta1−\\bmtheta2\\displaystyle\\alpha\\sum\_\{x\\in\\mcX\}q\(x\)\\bmphi\(x\)\\sum\_\{x^\{\\prime\}\\in\\mcX\}P\(x^\{\\prime\}\|x\)\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\+\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}=\\displaystyle=\(\\bmI\+α​\\bmXi​\(\\bmtheta1,\\bmtheta2\)\)​\(\\bmtheta1−\\bmtheta2\)\.\\displaystyle\\left\(\\bmI\+\\alpha\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\\right\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\.Taking the Euclidean norm, we obtain that

\\norm​\\mcH^​\(\\bmtheta1\)−\\mcH^​\(\\bmtheta2\)22\\displaystyle\\norm\{\\hat\{\\mcH\}\(\\bmtheta\_\{1\}\)\-\\hat\{\\mcH\}\(\\bmtheta\_\{2\}\)\}\_\{2\}^\{2\}≤\\displaystyle\\leq\\norm​\\bmtheta1−\\bmtheta222\+α​\(\\bmtheta1−\\bmtheta2\)⊤​\(\\bmXi​\(\\bmtheta1,\\bmtheta2\)\+\\bmXi⊤​\(\\bmtheta1,\\bmtheta2\)\)​\(\\bmtheta1−\\bmtheta2\)\\displaystyle\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}^\{2\}\+\\alpha\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\left\(\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\+\\bmXi^\{\\top\}\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\\right\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\+α2​\(\\bmtheta1−\\bmtheta2\)⊤​\\bmXi⊤​\(\\bmtheta1,\\bmtheta2\)​\\bmXi​\(\\bmtheta1,\\bmtheta2\)​\(\\bmtheta1−\\bmtheta2\)\\displaystyle\\qquad\+\\alpha^\{2\}\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)^\{\\top\}\\bmXi^\{\\top\}\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\\bmXi\(\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)≤\\displaystyle\\leq\\norm​\\bmtheta1−\\bmtheta222\+α​\(γ​\(ϵ1\+L1\)−2​ϵ1\)​\\norm​f\\bmdeltaq2\+λM2​α2​L12​\(γ\+1\)2​\\norm​f\\bmdeltaq2\\displaystyle\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}^\{2\}\+\\alpha\\left\(\\gamma\(\\epsilon\_\{1\}\+L\_\{1\}\)\-2\\epsilon\_\{1\}\\right\)\\norm\{f\_\{\\bmdelta\}\}\_\{q\}^\{2\}\+\\lambda\_\{M\}^\{2\}\\alpha^\{2\}L\_\{1\}^\{2\}\(\\gamma\+1\)^\{2\}\\norm\{f\_\{\\bmdelta\}\}\_\{q\}^\{2\}≤\\displaystyle\\leqβ~​\\norm​\\bmtheta1−\\bmtheta222,\\displaystyle\\tilde\{\\beta\}\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}^\{2\},where the last inequality follows from the fact that

\\norm​f\\bmdeltaq2\\displaystyle\\norm\{f\_\{\\bmdelta\}\}\_\{q\}^\{2\}=\\norm​\\bmPhi​\(\\bmtheta1−\\bmtheta2\)q2=\\norm​\\diag​\(q\)​\\bmPhi​\(\\bmtheta1−\\bmtheta2\)22\\displaystyle=\\norm\{\\bmPhi\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\}\_\{q\}^\{2\}=\\norm\{\\sqrt\{\\diag\(q\)\}\\bmPhi\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\}\_\{2\}^\{2\}≥\(min\\bmtheta≠𝟎⁡\\norm​\\diag​\(q\)​\\bmPhi​\\bmtheta22\\norm​\\bmtheta22\)​\\norm​\\bmtheta1−\\bmtheta222=λm2​\\norm​\\bmtheta1−\\bmtheta222,\\displaystyle\\geq\\left\(\\min\_\{\\bmtheta\\neq\\bm\{0\}\}\\frac\{\\norm\{\\sqrt\{\\diag\(q\)\}\\bmPhi\\bmtheta\}\_\{2\}^\{2\}\}\{\\norm\{\\bmtheta\}\_\{2\}^\{2\}\}\\right\)\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}^\{2\}=\\lambda\_\{m\}^\{2\}\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}^\{2\},and the definition ofλM\\lambda\_\{M\}that

α​\(γ​\(ϵ1\+L1\)−2​ϵ1\)\+λM2​α2​L12​\(γ\+1\)2<0,\\alpha\\left\(\\gamma\(\\epsilon\_\{1\}\+L\_\{1\}\)\-2\\epsilon\_\{1\}\\right\)\+\\lambda\_\{M\}^\{2\}\\alpha^\{2\}L\_\{1\}^\{2\}\(\\gamma\+1\)^\{2\}<0,which yields a contraction factor

β~:=1−λm2​\(−α​\(γ​\(ϵ1\+L1\)−2​ϵ1\)−λM2​α2​L12​\(γ\+1\)2\)<1\.\\tilde\{\\beta\}:=1\-\\lambda\_\{m\}^\{2\}\\left\(\-\\alpha\(\\gamma\(\\epsilon\_\{1\}\+L\_\{1\}\)\-2\\epsilon\_\{1\}\)\-\\lambda\_\{M\}^\{2\}\\alpha^\{2\}L\_\{1\}^\{2\}\(\\gamma\+1\)^\{2\}\\right\)<1\.Therefore we conclude that\\mcH^\\hat\{\\mcH\}is a contraction on\(\\mcL\(\\mbRd\),\\norm⋅q\)\(\\mcL\(\\mbR^\{d\}\),\\norm\{\\cdot\}\_\{q\}\)\. This completes the proof\.

Next we prove some property regardingHHdefined in \([13](https://arxiv.org/html/2607.23030#S4.E13)\)\. We first show a property of the loss functionℓ\\ell\.

###### Lemma B\.6\(Lemma B\.19 inWang and Delage \([2025](https://arxiv.org/html/2607.23030#bib.bib26)\)\)\.

For any loss functionℓ:\\mbR→\\mbR\\ell:\\mbR\\to\\mbRwithℓ​\(0\)=0\\ell\(0\)=0satisfying Assumptions[4](https://arxiv.org/html/2607.23030#S4)and[4](https://arxiv.org/html/2607.23030#S4), defineℓs​\(z\):=1s​ℓ​\(s​z\)\\ell\_\{s\}\(z\):=\\frac\{1\}\{s\}\\ell\(sz\), for allz∈\\mbRz\\in\\mbR\. We haveℓ∞​\(z\):=lims→∞ℓs​\(z\)\\ell\_\{\\infty\}\(z\):=\\lim\_\{s\\to\\infty\}\\ell\_\{s\}\(z\)exists and the convergence is uniform on compact sets\. Furthermore,ℓ∞\\ell\_\{\\infty\}also satisfies Assumptions[4](https://arxiv.org/html/2607.23030#S4)and[4](https://arxiv.org/html/2607.23030#S4)\.

DefineHs​\(\\bmtheta,y\):=1s​H​\(s​\\bmtheta,y\)H\_\{s\}\(\\bmtheta,y\):=\\frac\{1\}\{s\}H\(s\\bmtheta,y\), fors≥1s\\geq 1, as a rescaled version of the functionHHwith respect to\\bmtheta\\bmtheta\. We also definehs​\(\\bmtheta\):=\\mbEY∼dY​Hs​\(\\bmtheta,Y\)h\_\{s\}\(\\bmtheta\):=\\mbE\_\{Y\\sim d\_\{Y\}\}H\_\{s\}\(\\bmtheta,Y\), wheredYd\_\{Y\}is the stationary distribution for the Markov chain\{Yn\}n≥1\\\{Y\_\{n\}\\\}\_\{n\\geq 1\}\.

###### Lemma B\.7\.

Under the assumptions of Lemma[4\.1](https://arxiv.org/html/2607.23030#S4.Thmtheorem1),H∞​\(\\bmtheta,y\):=lims→∞Hs​\(\\bmtheta,y\)H\_\{\\infty\}\(\\bmtheta,y\):=\\lim\_\{s\\to\\infty\}H\_\{s\}\(\\bmtheta,y\)exists and is finite for each\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}andy∈\\mcYy\\in\\mcY\. Consequently,h∞​\(\\bmtheta\):=\\mbEY∼dY​\[H∞​\(\\bmtheta,Y\)\]h\_\{\\infty\}\(\\bmtheta\):=\\mbE\_\{Y\\sim d\_\{Y\}\}\[H\_\{\\infty\}\(\\bmtheta,Y\)\]exists and is finite, andlims→∞hs​\(\\bmtheta\)=h∞​\(\\bmtheta\)\\lim\_\{s\\to\\infty\}h\_\{s\}\(\\bmtheta\)=h\_\{\\infty\}\(\\bmtheta\)for each\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}\.

###### Proof B\.8\.

By definition, for any\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\},y=\(x,x′\)∈\\mcYy=\(x,x^\{\\prime\}\)\\in\\mcY, we have

lims→∞Hs​\(\\bmtheta,y\)\\displaystyle\\lim\_\{s\\to\\infty\}H\_\{s\}\(\\bmtheta,y\)=lims→∞1s​α​\\bmphi​\(x\)​ℓ​\(\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​s​\\bmtheta\+c​\(x\)\)\\displaystyle=\\lim\_\{s\\to\\infty\}\\frac\{1\}\{s\}\\alpha\\bmphi\(x\)\\ell\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}s\\bmtheta\+c\(x\)\\right\)=α\\bmphi\(x\)ℓ∞\(\(γ\\bmphi\(x′\)−\\bmphi\(x\)\)⊤\\bmtheta\)=:H∞\(\\bmtheta,y\),\\displaystyle=\\alpha\\bmphi\(x\)\\ell\_\{\\infty\}\\left\(\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\\bmtheta\\right\)=:H\_\{\\infty\}\(\\bmtheta,y\),exists and is finite\. Here the second equality follows from the fact thatlims→∞\|1s​ℓ​\(s​z\+c\)−1s​ℓ​\(s​z\)\|≤lims→∞1s​L1​\|s​z\+c−s​z\|=0\\lim\_\{s\\to\\infty\}\|\\frac\{1\}\{s\}\\ell\(sz\+c\)\-\\frac\{1\}\{s\}\\ell\(sz\)\|\\leq\\lim\_\{s\\to\\infty\}\\frac\{1\}\{s\}L\_\{1\}\|sz\+c\-sz\|=0for anyc∈\\mbRc\\in\\mbR, hence following Lemma[B\.6](https://arxiv.org/html/2607.23030#A2.Thmtheorem6),lims→∞1s​ℓ​\(s​z\+c\)=ℓ∞​\(z\)\\lim\_\{s\\to\\infty\}\\frac\{1\}\{s\}\\ell\(sz\+c\)=\\ell\_\{\\infty\}\(z\)\. As a result,h∞​\(\\bmtheta\):=\\mbEY∼qY​\[H∞​\(\\bmtheta,Y\)\]h\_\{\\infty\}\(\\bmtheta\):=\\mbE\_\{Y\\sim q\_\{Y\}\}\[H\_\{\\infty\}\(\\bmtheta,Y\)\]exists and is finite for any fixed\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}since

\\norm​h∞​\(\\bmtheta\)2\\displaystyle\\norm\{h\_\{\\infty\}\(\\bmtheta\)\}\_\{2\}=α​‖\\mbE​\[\\bmphi​\(X\)​\(ℓ∞​\(\(γ​\\bmphi​\(X′\)−\\bmphi​\(X\)\)⊤​\\bmtheta\)\)\]‖2\\displaystyle=\\alpha\\left\\\|\\mbE\[\\bmphi\(X\)\(\\ell\_\{\\infty\}\(\(\\gamma\\bmphi\(X^\{\\prime\}\)\-\\bmphi\(X\)\)^\{\\top\}\\bmtheta\)\)\]\\right\\\|\_\{2\}≤α​\\mbE​\[‖\\bmphi​\(X\)​\(ℓ∞​\(\(γ​\\bmphi​\(X′\)−\\bmphi​\(X\)\)⊤​\\bmtheta\)−ℓ∞​\(0\)\)‖2\]≤α​M2​L1​\(γ\+1\)​\\norm​\\bmtheta2<∞,\\displaystyle\\leq\\alpha\\mbE\\left\[\\left\\\|\\bmphi\(X\)\\left\(\\ell\_\{\\infty\}\(\(\\gamma\\bmphi\(X^\{\\prime\}\)\-\\bmphi\(X\)\)^\{\\top\}\\bmtheta\)\-\\ell\_\{\\infty\}\(0\)\\right\)\\right\\\|\_\{2\}\\right\]\\leq\\alpha M^\{2\}L\_\{1\}\(\\gamma\+1\)\\norm\{\\bmtheta\}\_\{2\}<\\infty,for any random statesX,X′X,X^\{\\prime\}in\\mcX\\mcX, where the first inequality is from Jensen’s inequality and the fact thatℓ∞​\(0\)=0\\ell\_\{\\infty\}\(0\)=0; the second inequality follows from the triangular inequality, Assumptions[4](https://arxiv.org/html/2607.23030#S4),[4](https://arxiv.org/html/2607.23030#S4)\.

Note that\\norm​Hs​\(\\bmtheta,y\)2≤α​M​L1​\(\(γ\+1\)​M​\\norm​\\bmtheta2\+c¯\)\\norm\{H\_\{s\}\(\\bmtheta,y\)\}\_\{2\}\\leq\\alpha ML\_\{1\}\(\(\\gamma\+1\)M\\norm\{\\bmtheta\}\_\{2\}\+\\bar\{c\}\)for alls≥1s\\geq 1,\\bmtheta∈\\mbRd,y∈\\mcY\\bmtheta\\in\\mbR^\{d\},y\\in\\mcY\. By the bounded convergence theorem, we havelims→∞hs​\(\\bmtheta\)=h∞​\(\\bmtheta\)\\lim\_\{s\\to\\infty\}h\_\{s\}\(\\bmtheta\)=h\_\{\\infty\}\(\\bmtheta\)for each\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}\. This completes the proof\.

###### Lemma B\.9\.

The functionHHis Lipschitz continuous with respect to\\bmtheta\\bmtheta, i\.e\., there exists a constantL2L\_\{2\}such that\\norm​H​\(\\bmtheta1,y\)−H​\(\\bmtheta2,y\)2≤L2​\\norm​\\bmtheta1−\\bmtheta22\\norm\{H\(\\bmtheta\_\{1\},y\)\-H\(\\bmtheta\_\{2\},y\)\}\_\{2\}\\leq L\_\{2\}\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}, for any\\bmtheta1,\\bmtheta2∈\\mbRd\\bmtheta\_\{1\},\\bmtheta\_\{2\}\\in\\mbR^\{d\},y∈\\mcYy\\in\\mcY\.

###### Proof B\.10\.

By Assumption[4](https://arxiv.org/html/2607.23030#S4), fory=\(x,x′\)∈\\mcYy=\(x,x^\{\\prime\}\)\\in\\mcY, for any\\bmtheta1,\\bmtheta2∈\\mbRd\\bmtheta\_\{1\},\\bmtheta\_\{2\}\\in\\mbR^\{d\}, there exists someξ\(x,x′,\\bmtheta1,\\bmtheta2\)∈\[ϵ1,L1\]\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\\in\[\\epsilon\_\{1\},L\_\{1\}\]such that,

\\norm​H​\(\\bmtheta1,y\)−H​\(\\bmtheta2,y\)2\\displaystyle\\norm\{H\(\\bmtheta\_\{1\},y\)\-H\(\\bmtheta\_\{2\},y\)\}\_\{2\}=‖α​\\bmphi​\(x\)​\(ξ\(x,x′,\\bmtheta1,\\bmtheta2\)​\(γ​\\bmphi​\(x′\)−\\bmphi​\(x\)\)⊤​\(\\bmtheta1−\\bmtheta2\)\)‖2\\displaystyle=\\Big\\\|\\alpha\\bmphi\(x\)\\left\(\\xi\_\{\(x,x^\{\\prime\},\\bmtheta\_\{1\},\\bmtheta\_\{2\}\)\}\(\\gamma\\bmphi\(x^\{\\prime\}\)\-\\bmphi\(x\)\)^\{\\top\}\(\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\)\\right\)\\Big\\\|\_\{2\}≤α​M2​L1​\(γ\+1\)​\\norm​\\bmtheta1−\\bmtheta22\.\\displaystyle\\leq\\alpha M^\{2\}L\_\{1\}\(\\gamma\+1\)\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\}\_\{2\}\.This completes the proof\.

We invoke a recent stochastic approximation result with Markovian noise to establish the almost sure convergence of our UBSR\-TD algorithm \([10](https://arxiv.org/html/2607.23030#S3.E10)\)\. We refer readers to Section 2\.2 ofBorkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\)for the definitions of a small function and aperiodicity of a Markov chain\.

###### Theorem B\.11\(Theorem 1,Borkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\)\)\.

Consider the stochastic approximation

\\bmthetan\+1=\\bmthetan\+ηn​f​\(\\bmthetan,Yn\+1\),\\bmtheta\_\{n\+1\}=\\bmtheta\_\{n\}\+\\eta\_\{n\}f\(\\bmtheta\_\{n\},Y\_\{n\+1\}\),\(33\)wheref:\\mbRd×\\mcY→\\mbRdf:\\mbR^\{d\}\\times\\mcY\\to\\mbR^\{d\},\{Yn\}n≥1\\\{Y\_\{n\}\\\}\_\{n\\geq 1\}is an irreducible and aperiodic Markov chain on\\mcY\\mcY, with unique stationary distributiondYd\_\{Y\}, and transition kernelPP\. Suppose the following conditions hold:

1. \(i\)The step size\{ηn\}n≥1\\\{\\eta\_\{n\}\\\}\_\{n\\geq 1\}satisfies Assumption[4](https://arxiv.org/html/2607.23030#S4)\.
2. \(ii\)There exists a constant\\mfL\\mfLsuch that for eachy∈\\mcYy\\in\\mcY,\\norm​f​\(𝟎,y\)≤\\mfL\\norm\{f\(\\bm\{0\},y\)\}\\leq\\mfL, and \\norm​f​\(\\bmtheta1,y\)−f​\(\\bmtheta2,y\)≤\\mfL​\\norm​\\bmtheta1−\\bmtheta2,∀\\bmtheta1,\\bmtheta2∈\\mbRd\.\\norm\{f\(\\bmtheta\_\{1\},y\)\-f\(\\bmtheta\_\{2\},y\)\}\\leq\\mfL\\norm\{\\bmtheta\_\{1\}\-\\bmtheta\_\{2\}\},\\quad\\forall\\bmtheta\_\{1\},\\bmtheta\_\{2\}\\in\\mbR^\{d\}\.
3. \(iii\)The Lyapunov drift criterion \(V4\) holds with respect to the Lyapunov functionv:\\mcY→\[1,∞\)v:\\mcY\\to\[1,\\infty\), i\.e\., for a small functionssand constantsδ\>0\\delta\>0,b<∞b<\\infty, \\mbE​\[v​\(Yn\+1\)−v​\(Yn\)\|Yn=y\]≤−δ​v​\(y\)\+b​s​\(y\),∀y∈\\mcY\.\\mbE\[v\(Y\_\{n\+1\}\)\-v\(Y\_\{n\}\)\|Y\_\{n\}=y\]\\leq\-\\delta v\(y\)\+bs\(y\),\\quad\\forall y\\in\\mcY\.
4. \(iv\)The scaled vector fieldf¯∞​\(\\bmtheta\)\\bar\{f\}\_\{\\infty\}\(\\bmtheta\)exists for each\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}, wheref¯∞​\(\\bmtheta\):=limr→∞f¯r​\(\\bmtheta\)\\bar\{f\}\_\{\\infty\}\(\\bmtheta\):=\\lim\_\{r\\to\\infty\}\\bar\{f\}\_\{r\}\(\\bmtheta\),f¯r​\(\\bmtheta\):=\\mbEY∼dY​\[fr​\(\\bmtheta,Y\)\]\\bar\{f\}\_\{r\}\(\\bmtheta\):=\\mbE\_\{Y\\sim d\_\{Y\}\}\[f\_\{r\}\(\\bmtheta,Y\)\], andfr​\(\\bmtheta,y\):=1r​f​\(r​\\bmtheta,y\)f\_\{r\}\(\\bmtheta,y\):=\\frac\{1\}\{r\}f\(r\\bmtheta,y\)forr≥1r\\geq 1,y∈\\mcYy\\in\\mcY\. Moreover, the ODE d​\\bmvartheta​\(t\)d​t=f¯∞​\(\\bmvartheta​\(t\)\),\\frac\{d\\bmvartheta\(t\)\}\{dt\}=\\bar\{f\}\_\{\\infty\}\(\\bmvartheta\(t\)\),\(34\)is globally asymptotically stable\.
5. \(v\)The ODE d​\\bmvartheta​\(t\)d​t=f¯​\(\\bmvartheta​\(t\)\),\\frac\{d\\bmvartheta\(t\)\}\{dt\}=\\bar\{f\}\(\\bmvartheta\(t\)\),\(35\)is globally asymptotically stable, wheref¯​\(\\bmtheta\):=\\mbEY∼dY​\[f​\(\\bmtheta,Y\)\]\\bar\{f\}\(\\bmtheta\):=\\mbE\_\{Y\\sim d\_\{Y\}\}\[f\(\\bmtheta,Y\)\], for all\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}\.

Then the sequence\{\\bmthetan\}n≥0\\\{\\bmtheta\_\{n\}\\\}\_\{n\\geq 0\}generated by \([33](https://arxiv.org/html/2607.23030#A2.E33)\) converges a\.s\. to the invariant set of the ODE \([35](https://arxiv.org/html/2607.23030#A2.E35)\)\.

We note that inBorkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\), the transition kernel is allowed to depend on\\bmtheta\\bmthetaand the Lipschitz constant\\mfL\\mfLin \(ii\) can be a function ofyy, which necessitates additional continuity and measurable assumptions \(see inequality \(30\) and Assumption \(A2\) inBorkaret al\.\([2025](https://arxiv.org/html/2607.23030#bib.bib56)\)\)\. In contrast, since the transition kernel in our framework does not depend on\\bmtheta\\bmthetaand\\mfL\\mfLis a constant, these assumptions are omitted from Theorem[B\.11](https://arxiv.org/html/2607.23030#A2.Thmtheorem11)for clarity\.

###### Proof B\.12\(Proof of Theorem[4\.5](https://arxiv.org/html/2607.23030#S4.Thmtheorem5)\)\.

It is straightforward to see that \([13](https://arxiv.org/html/2607.23030#S4.E13)\) is the stochastic approximation with Markovian noise \([33](https://arxiv.org/html/2607.23030#A2.E33)\) withf​\(\\bmtheta,y\):=1α​H​\(θ,y\)f\(\\bmtheta,y\):=\\frac\{1\}\{\\alpha\}H\(\\theta,y\),f¯​\(\\bmtheta\):=1α​h​\(\\bmtheta\)\\bar\{f\}\(\\bmtheta\):=\\frac\{1\}\{\\alpha\}h\(\\bmtheta\),f¯∞​\(\\bmtheta\):=1α​h∞​\(\\bmtheta\)\\bar\{f\}\_\{\\infty\}\(\\bmtheta\):=\\frac\{1\}\{\\alpha\}h\_\{\\infty\}\(\\bmtheta\),f¯r​\(\\bmtheta\):=1α​hr​\(\\bmtheta\)\\bar\{f\}\_\{r\}\(\\bmtheta\):=\\frac\{1\}\{\\alpha\}h\_\{r\}\(\\bmtheta\), withHH,hh,h∞h\_\{\\infty\},hrh\_\{r\}defined in \([13](https://arxiv.org/html/2607.23030#S4.E13)\), \([14](https://arxiv.org/html/2607.23030#S4.E14)\), Lemma[B\.7](https://arxiv.org/html/2607.23030#A2.Thmtheorem7), respectively, for all\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}andy∈\\mcYy\\in\\mcY\. We show our algorithm satisfies all the conditions required by Theorem[B\.11](https://arxiv.org/html/2607.23030#A2.Thmtheorem11)\.

\(i\) Condition \(i\) is satisfied by enforcing Assumption[4](https://arxiv.org/html/2607.23030#S4)\.

\(ii\) Condition \(ii\) is proved by Lemma[B\.9](https://arxiv.org/html/2607.23030#A2.Thmtheorem9)by letting\\mfL:=L2/α\\mfL:=L\_\{2\}/\\alpha\.

\(iii\) Under Assumption[4](https://arxiv.org/html/2607.23030#S4), the Markov chain\{Yn\}n≥1\\\{Y\_\{n\}\\\}\_\{n\\geq 1\}is finite, irreducible and aperiodic\. The Lyapunov drift condition \(V4\) holds trivially withv​\(y\)≡1v\(y\)\\equiv 1,s​\(y\)≡1s\(y\)\\equiv 1for ally∈\\mcYy\\in\\mcYand anyb\>δb\>\\delta\. In particular,

\\mbE​\[v​\(Yn\+1\)−v​\(Yn\)∣Yn=y\]=0≤−δ\+b,∀y∈\\mcY\.\\mbE\\left\[v\(Y\_\{n\+1\}\)\-v\(Y\_\{n\}\)\\mid Y\_\{n\}=y\\right\]=0\\leq\-\\delta\+b,\\qquad\\forall\\,y\\in\\mcY\.
\(v\) Lemma[B\.4](https://arxiv.org/html/2607.23030#A2.Thmtheorem4)shows that\\mcH^\\hat\{\\mcH\}is a contraction, while Lemma[4\.4](https://arxiv.org/html/2607.23030#S4.Thmtheorem4)establishes that\\bmtheta∗\\bmtheta^\{\*\}is a unique equilibrium point of the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\)\. Consequently, we have𝟎=\\mcH^​\(\\bmtheta∗\)−\\bmtheta∗\\bm\{0\}=\\hat\{\\mcH\}\(\\bmtheta^\{\*\}\)\-\\bmtheta^\{\*\}, implying that\\bmtheta∗\\bmtheta^\{\*\}is a fixed point of\\mcH^\\hat\{\\mcH\}\. Then by Theorem 12\.1 inBorkar \([2023](https://arxiv.org/html/2607.23030#bib.bib6)\), it follows that\\bmtheta∗\\bmtheta^\{\*\}is globally asymptotically stable for the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\)\. Sinceα\>0\\alpha\>0is a constant, it follows that\\bmtheta∗\\bmtheta^\{\*\}is also globally asymptotically stable for the ODE \([35](https://arxiv.org/html/2607.23030#A2.E35)\)\.

\(iv\) Lemma[B\.7](https://arxiv.org/html/2607.23030#A2.Thmtheorem7)establishes thath∞​\(\\bmtheta\)h\_\{\\infty\}\(\\bmtheta\)exists, is finite, and satisfiesh∞​\(\\bmtheta\)=lims→∞hs​\(\\bmtheta\)h\_\{\\infty\}\(\\bmtheta\)=\\lim\_\{s\\to\\infty\}h\_\{s\}\(\\bmtheta\)for all\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}\. Consequently, it follows thatf¯∞​\(\\bmtheta\)=lims→∞f¯s​\(\\bmtheta\)\\bar\{f\}\_\{\\infty\}\(\\bmtheta\)=\\lim\_\{s\\to\\infty\}\\bar\{f\}\_\{s\}\(\\bmtheta\)also exists and is finite for all\\bmtheta∈\\mbRd\\bmtheta\\in\\mbR^\{d\}\. The ODE

d​\\bmvartheta​\(t\)d​t=h∞​\(\\bmvartheta​\(t\)\),\\frac\{d\\bmvartheta\(t\)\}\{dt\}=h\_\{\\infty\}\(\\bmvartheta\(t\)\),\(36\)is then the ODE \([14](https://arxiv.org/html/2607.23030#S4.E14)\) withc​\(x\)≡0c\(x\)\\equiv 0,ℓ​\(x\)=ℓ∞​\(x\)\\ell\(x\)=\\ell\_\{\\infty\}\(x\)for allx∈\\mcXx\\in\\mcX, and𝟎\\bm\{0\}is an equilibrium for \([36](https://arxiv.org/html/2607.23030#A2.E36)\)\. Then following a similar step as the proof of \(v\), we conclude that such an equilibrium point is globally asymptotically stable\. Moreover, it is also a globally asymptotically stable equilibrium for the ODE \([34](https://arxiv.org/html/2607.23030#A2.E34)\)\.

Therefore, by applying Theorem[B\.11](https://arxiv.org/html/2607.23030#A2.Thmtheorem11), we obtain that the sequence\{\\bmthetan\}n≥1\\\{\\bmtheta\_\{n\}\\\}\_\{n\\geq 1\}generated by the UBSR\-TD algorithm \([10](https://arxiv.org/html/2607.23030#S3.E10)\) converges almost surely to\\bmtheta∗\\bmtheta^\{\*\}\. The rest of the result then follows from Lemma[4\.3](https://arxiv.org/html/2607.23030#S4.Thmtheorem3)\. This completes the proof\.

## Appendix CFurther Experiments

### C\.1Convergence Experiments for Soft Quantile

Figure[4](https://arxiv.org/html/2607.23030#A3.F4)shows the convergence of the policy evaluation algorithms under soft\-quantile risk across different risk parameters and discount factors, under the setting of Section[6\.1\.1](https://arxiv.org/html/2607.23030#S6.SS1.SSS1)\. The first two rows correspond tod=Nd=N, and the last two tod<Nd<N; shaded regions indicate standard errors\. All methods converge to the true value function whend=Nd=N\. UBSR\-TD and UBSR\-Newton converge to the same objective whend<Nd<N\. UBSR\-TD\(1\) does not minimize the distance to the projected value function for the case ofd=5d=5,γ=0\.05\\gamma=0\.05,μ=0\.8\\mu=0\.8, and diverges for the case ofd=5d=5,γ=0\.9\\gamma=0\.9, andμ=0\.8\\mu=0\.8\.

![Refer to caption](https://arxiv.org/html/2607.23030v1/x6.png)

![Refer to caption](https://arxiv.org/html/2607.23030v1/x7.png)

Figure 4:Convergence results for soft\-quantile risk
### C\.2Runtime Comparison for Different ADP Policy Evaluation Algorithms

Table 2:Compuational times of different policy evaluation algorithmsmm358τ\\tau0\.40\.50\.60\.40\.50\.60\.40\.50\.6VI5\.74s5\.40s7\.48s376\.25s396\.71s673\.51s\>\>14h\>\>17h\>\>35hTD171\.10s\(7\.99%\)160\.71s\(6\.70%\)171\.76s\(8\.00%\)171\.32s\(0\.87%\)161\.45s\(0\.70%\)173\.18s\(0\.37%\)178\.25s\(0\.76%\)165\.91s\(1\.20%\)175\.66s\(1\.27%\)Newton198\.12s\(2\.07%\)183\.31s\(0\.45%\)198\.98s\(2\.74%\)201\.36s\(2\.48%\)186\.43s\(0\.62%\)202\.82s\(7\.70%\)216\.02s\(3\.12%\)197\.30s\(0\.40%\)212\.77s\(7\.44%\)

We compare the runtime of policy evaluation for the static policy in Section[6\.2](https://arxiv.org/html/2607.23030#S6.SS2)\. Table[2](https://arxiv.org/html/2607.23030#A3.T2)reports the average runtime \(CPU time\) of UBSR\-TD and UBSR\-Newton for one policy evaluation step \(60,000 online sampling iterations\) based on 20 independent runs, and compares it with exact policy evaluation by value iteration using a tolerance of0\.10\.1\. Experiments are conducted usingm=3,5,8m=3,5,8, cost parameters\(c1,c2,c3,c4\)=\(10,1,20,5\)\(c\_\{1\},c\_\{2\},c\_\{3\},c\_\{4\}\)=\(10,1,20,5\), andτ=0\.4,0\.5,0\.6\\tau=0\.4,0\.5,0\.6\. The values in parentheses denote the optimality gap between the averaged function approximation and the value computed by value iteration at the empty\-inventory state\.

The results show that the computational cost of value iteration grows rapidly withmm, increasing from only a few seconds whenm=3m=3to more than 10 hours whenm=8m=8\. By contrast, UBSR\-TD and UBSR\-Newton require approximately 200 seconds across all settings while maintaining relative errors below10%10\\%\. Their runtimes increase moderately withmmas the number of features grows from 7 to 37\. UBSR\-Newton is consistently more computationally expensive than UBSR\-TD because it additionally requires the processing of the information matrix\. Overall, these results demonstrate that function approximation effectively alleviates the curse of dimensionality in the perishable inventory management problem\.

### C\.3Further Details of ADP Policy Comparisons

Table[3](https://arxiv.org/html/2607.23030#A3.T3)reports the exact evaluations of policies obtained by value and policy iteration for the perishable inventory management problem under different risk and cost settings in Section[6\.2](https://arxiv.org/html/2607.23030#S6.SS2)whenm=3m=3\. Static, myopic, and risk\-neutral \(RN\) policies are included as benchmarks, with optimality gaps shown in parentheses\.

It can be seen that, the static policy performs poorly, with optimality gaps reaching512\.31%512\.31\\%, highlighting the inadequacy of classical\(s,S\)\(s,S\)policies for perishable inventory\. The myopic policy performs much better, with gaps below3%3\\%in most cases, but can still reach30\.49%30\.49\\%in the extreme case\. The risk\-neutral policy generally outperforms these benchmarks but can exceed a6%6\\%gap under strong risk sensitivity\. In contrast, the policy iteration methods consistently achieve average gaps below0\.2%0\.2\\%, demonstrating their effectiveness\.

Table 3:Results under varying policies, risk parameters, and cost settings form=3m=3τ\\tauCost\(10,1,20,5\)\(20,1,20,5\)\(50,1,20,5\)\(80,1,20,5\)\(10,1,20,20\)\(10,1,20,50\)\(10,1,20,80\)0\.1Optimal34\.4954\.02101\.45144\.5337\.0840\.4742\.96Static36\.52\(5\.91%\)59\.77\(10\.65%\)122\.80\(21\.04%\)181\.45\(25\.54%\)47\.08\(26\.98%\)68\.03\(68\.09%\)88\.68\(106\.44%\)Myopic34\.66\(0\.49%\)55\.22\(2\.22%\)105\.17\(3\.67%\)188\.59\(30\.49%\)37\.22\(0\.38%\)40\.61\(0\.33%\)43\.01\(0\.13%\)RN35\.91\(4\.12%\)57\.45\(6\.36%\)105\.85\(4\.34%\)147\.65\(2\.16%\)37\.98\(2\.44%\)40\.88\(1\.00%\)43\.22\(0\.60%\)TD34\.49\(0\.02%\)54\.09\(0\.14%\)101\.46\(0\.01%\)144\.54\(0\.01%\)37\.09\(0\.02%\)40\.48\(0\.02%\)42\.97\(0\.03%\)Newton34\.49\(0\.02%\)54\.03\(0\.02%\)101\.46\(0\.01%\)144\.54\(0\.01%\)37\.09\(0\.02%\)40\.48\(0\.02%\)42\.97\(0\.03%\)0\.4Optimal49\.6172\.43132\.50184\.2863\.1179\.0989\.88Static66\.26\(33\.56%\)113\.77\(57\.07%\)204\.79\(54\.56%\)253\.68\(37\.66%\)137\.07\(117\.20%\)278\.31\(251\.91%\)419\.40\(366\.61%\)Myopic49\.67\(0\.12%\)72\.87\(0\.61%\)135\.73\(2\.44%\)188\.17\(2\.11%\)63\.13\(0\.03%\)79\.10\(0\.02%\)89\.90\(0\.02%\)RN49\.66\(0\.09%\)72\.62\(0\.26%\)132\.87\(0\.28%\)184\.60\(0\.17%\)63\.14\(0\.05%\)79\.11\(0\.03%\)89\.89\(0\.01%\)TD49\.63\(0\.03%\)72\.46\(0\.04%\)132\.52\(0\.02%\)184\.30\(0\.01%\)63\.13\(0\.03%\)79\.10\(0\.02%\)89\.89\(0\.01%\)Newton49\.62\(0\.02%\)72\.44\(0\.01%\)132\.51\(0\.01%\)184\.29\(0\.00%\)63\.12\(0\.01%\)79\.10\(0\.02%\)89\.89\(0\.01%\)0\.5Optimal54\.8378\.15140\.54194\.7973\.4094\.37108\.68Static72\.94\(33\.03%\)122\.58\(56\.85%\)216\.48\(54\.04%\)267\.53\(37\.34%\)158\.48\(115\.90%\)329\.56\(249\.20%\)500\.63\(360\.66%\)Myopic54\.85\(0\.02%\)78\.45\(0\.39%\)142\.67\(1\.52%\)199\.91\(2\.63%\)73\.41\(0\.01%\)94\.40\(0\.02%\)108\.71\(0\.03%\)TD54\.84\(0\.01%\)78\.18\(0\.04%\)140\.55\(0\.01%\)194\.80\(0\.01%\)73\.42\(0\.02%\)94\.38\(0\.01%\)108\.70\(0\.02%\)Newton54\.84\(0\.01%\)78\.18\(0\.04%\)140\.55\(0\.01%\)194\.80\(0\.00%\)73\.41\(0\.01%\)94\.38\(0\.01%\)108\.69\(0\.01%\)0\.6Optimal60\.7484\.54149\.08205\.5685\.33112\.22130\.72Static89\.50\(47\.34%\)144\.49\(70\.92%\)230\.27\(54\.47%\)285\.22\(38\.75%\)215\.41\(152\.46%\)467\.55\(316\.62%\)719\.79\(450\.65%\)Myopic60\.76\(0\.03%\)84\.69\(0\.18%\)151\.97\(1\.94%\)210\.15\(2\.23%\)85\.34\(0\.02%\)112\.26\(0\.03%\)131\.64\(0\.71%\)RN60\.89\(0\.25%\)84\.65\(0\.13%\)149\.14\(0\.04%\)205\.85\(0\.14%\)85\.34\(0\.02%\)112\.23\(0\.01%\)130\.81\(0\.08%\)TD60\.76\(0\.02%\)84\.56\(0\.03%\)149\.13\(0\.04%\)205\.57\(0\.00%\)85\.34\(0\.02%\)112\.24\(0\.01%\)130\.75\(0\.03%\)Newton60\.75\(0\.01%\)84\.56\(0\.03%\)149\.12\(0\.03%\)205\.58\(0\.01%\)85\.34\(0\.02%\)112\.23\(0\.01%\)130\.75\(0\.02%\)0\.9Optimal93\.54118\.31189\.77256\.15154\.58213\.98247\.63Static148\.14\(58\.37%\)218\.22\(84\.45%\)284\.89\(50\.13%\)350\.61\(36\.88%\)421\.61\(172\.75%\)968\.93\(352\.81%\)1516\.28\(512\.31%\)Myopic93\.54\(0\.01%\)118\.34\(0\.03%\)190\.34\(0\.30%\)258\.55\(0\.94%\)156\.07\(0\.96%\)214\.13\(0\.07%\)247\.80\(0\.07%\)RN100\.69\(7\.65%\)126\.39\(6\.83%\)196\.78\(3\.70%\)264\.99\(3\.45%\)156\.19\(1\.04%\)214\.63\(0\.30%\)263\.37\(6\.36%\)TD93\.56\(0\.02%\)118\.34\(0\.03%\)189\.84\(0\.04%\)256\.25\(0\.04%\)154\.60\(0\.01%\)214\.01\(0\.01%\)247\.69\(0\.02%\)Newton93\.55\(0\.02%\)118\.34\(0\.03%\)189\.83\(0\.03%\)256\.17\(0\.01%\)154\.59\(0\.01%\)213\.99\(0\.00%\)247\.66\(0\.01%\)

Table[4](https://arxiv.org/html/2607.23030#A3.T4)presents the exact performance of the policies generated by value iteration and policy iteration under the various risk and cost specifications considered in Section[6\.2](https://arxiv.org/html/2607.23030#S6.SS2)form=5m=5\. Compared to the case ofm=3m=3, the static policy now performs substantially better than the myopic policy in most cases\. In particular, it dominates the myopic policy whenτ=0\.4\\tau=0\.4and0\.60\.6, and in several instances even slightly outperforms the policy obtained through policy iteration\. As noted inAbouee\-Mehriziet al\.\([2026](https://arxiv.org/html/2607.23030#bib.bib85)\), this behavior can be attributed to the fact that, asmmincreases, the perishable inventory model becomes closer to its non\-perishable counterpart, with the limiting casem→∞m\\to\\inftycoinciding with the non\-perishable inventory problem\. Accordingly, for larger values ofmm, the optimal policy is expected to more closely resemble the static policy\.

Table 4:Results under varying policies, risk parameters, and cost settings form=5m=5τ\\tauMethod\(10,1,20,5\)\(20,1,20,5\)\(50,1,20,5\)\(80,1,20,5\)\(10,1,20,20\)\(10,1,20,50\)\(10,1,20,80\)0\.1Optimal31\.2346\.4184\.81120\.4031\.2631\.3231\.38Static31\.30\(0\.24%\)46\.47\(0\.14%\)84\.87\(0\.08%\)120\.50\(0\.09%\)31\.33\(0\.24%\)31\.40\(0\.24%\)31\.46\(0\.24%\)Myopic31\.86\(2\.02%\)48\.40\(4\.28%\)92\.69\(9\.29%\)188\.46\(56\.53%\)31\.88\(1\.99%\)31\.92\(1\.90%\)31\.95\(1\.81%\)RN33\.18\(6\.27%\)48\.52\(4\.55%\)86\.41\(1\.89%\)121\.66\(1\.05%\)33\.23\(6\.31%\)33\.15\(5\.85%\)33\.17\(5\.70%\)TD31\.30\(0\.24%\)46\.47\(0\.14%\)84\.94\(0\.16%\)120\.70\(0\.25%\)31\.33\(0\.24%\)31\.40\(0\.24%\)31\.46\(0\.24%\)Newton31\.30\(0\.24%\)46\.47\(0\.14%\)84\.87\(0\.08%\)120\.41\(0\.01%\)31\.33\(0\.24%\)31\.40\(0\.25%\)31\.46\(0\.24%\)0\.4Optimal38\.4454\.3895\.02132\.5138\.7539\.2139\.64Static38\.53\(0\.24%\)54\.54\(0\.28%\)95\.10\(0\.08%\)132\.60\(0\.07%\)38\.86\(0\.28%\)39\.48\(0\.67%\)40\.07\(1\.08%\)Myopic40\.03\(4\.15%\)60\.18\(10\.66%\)113\.22\(19\.15%\)162\.65\(22\.75%\)40\.18\(3\.68%\)40\.44\(3\.12%\)40\.69\(2\.63%\)RN38\.60\(0\.43%\)54\.59\(0\.39%\)95\.10\(0\.08%\)132\.60\(0\.07%\)38\.94\(0\.50%\)39\.44\(0\.58%\)39\.88\(0\.60%\)TD38\.53\(0\.24%\)54\.46\(0\.14%\)95\.10\(0\.08%\)132\.60\(0\.07%\)38\.85\(0\.26%\)39\.42\(0\.53%\)39\.76\(0\.29%\)Newton38\.53\(0\.24%\)54\.46\(0\.14%\)95\.10\(0\.08%\)132\.60\(0\.07%\)38\.85\(0\.25%\)39\.31\(0\.25%\)39\.74\(0\.25%\)0\.5Optimal40\.2356\.4697\.67136\.1340\.7941\.7842\.55Static40\.33\(0\.25%\)56\.55\(0\.15%\)97\.75\(0\.08%\)136\.14\(0\.01%\)40\.91\(0\.30%\)42\.14\(0\.85%\)43\.30\(1\.76%\)Myopic41\.23\(2\.47%\)61\.50\(8\.92%\)115\.07\(17\.82%\)165\.49\(21\.57%\)41\.54\(1\.83%\)42\.21\(1\.03%\)42\.82\(0\.63%\)TD40\.43\(0\.49%\)56\.55\(0\.15%\)97\.75\(0\.08%\)136\.14\(0\.01%\)40\.89\(0\.26%\)41\.90\(0\.29%\)42\.64\(0\.21%\)Newton40\.43\(0\.49%\)56\.55\(0\.15%\)97\.75\(0\.08%\)136\.14\(0\.01%\)40\.89\(0\.26%\)41\.96\(0\.43%\)42\.63\(0\.17%\)0\.6Optimal42\.3858\.83100\.60140\.2143\.3744\.9146\.23Static42\.43\(0\.13%\)59\.10\(0\.47%\)100\.69\(0\.08%\)140\.22\(0\.01%\)44\.02\(1\.49%\)47\.20\(5\.11%\)50\.46\(9\.15%\)Myopic44\.01\(3\.84%\)64\.59\(9\.79%\)121\.33\(20\.60%\)173\.77\(23\.93%\)44\.46\(2\.50%\)45\.45\(1\.21%\)46\.51\(0\.60%\)RN42\.55\(0\.39%\)58\.98\(0\.27%\)100\.93\(0\.32%\)140\.37\(0\.11%\)43\.49\(0\.27%\)45\.00\(0\.21%\)46\.33\(0\.22%\)TD42\.40\(0\.05%\)58\.93\(0\.18%\)100\.69\(0\.08%\)140\.23\(0\.01%\)43\.45\(0\.18%\)45\.04\(0\.28%\)46\.49\(0\.55%\)Newton42\.40\(0\.05%\)58\.91\(0\.15%\)100\.69\(0\.08%\)140\.22\(0\.01%\)43\.45\(0\.19%\)45\.17\(0\.58%\)46\.33\(0\.21%\)0\.9Optimal52\.9871\.42119\.55165\.9661\.5874\.2084\.09Static55\.50\(4\.75%\)74\.72\(4\.61%\)119\.66\(0\.09%\)166\.05\(0\.05%\)74\.31\(20\.67%\)113\.64\(53\.15%\)153\.24\(82\.23%\)Myopic54\.19\(2\.27%\)75\.45\(5\.64%\)139\.19\(16\.42%\)200\.82\(21\.00%\)62\.75\(1\.89%\)82\.17\(10\.73%\)101\.66\(20\.90%\)RN66\.04\(24\.65%\)82\.62\(15\.68%\)126\.23\(5\.59%\)170\.86\(2\.95%\)67\.94\(10\.32%\)76\.07\(2\.52%\)87\.66\(4\.24%\)TD54\.13\(2\.16%\)71\.77\(0\.49%\)119\.65\(0\.08%\)166\.04\(0\.05%\)62\.66\(1\.76%\)75\.33\(1\.52%\)84\.56\(0\.56%\)Newton53\.79\(1\.54%\)71\.60\(0\.25%\)119\.65\(0\.08%\)166\.04\(0\.05%\)61\.68\(0\.16%\)74\.32\(0\.16%\)84\.14\(0\.06%\)