Source-linked AI summary
Provably Efficient Risk-Sensitive Offline Reinforcement Learning via Optimized Certainty Equivalents
Hanzhen Wang, Boxiang Lyu, Zhongxiang Dai, Siyang Gao, Dake Zhang, Shuang Qiu
TL;DR
Offline risk-sensitive RL lacks a general theoretical treatment for fixed datasets, although additional interaction can be costly. This paper develops pessimistic algorithms and bounds for dynamic and static OCE, including linear function approximation. It reports sublinear upper bounds, a minimax lower bound, and utility-dependent guarantees for the function-approximation setting.
Problem
Existing risk-sensitive RL research largely focuses on online settings or particular risk measures, leaving provably efficient offline methods for general OCE underdeveloped.
Source: §1 · p. 2Method
The paper develops pessimistic offline algorithms for dynamic and static OCE and extends the framework to linear function approximation.
Source: §1 · p. 3, §2.4 · p. 7, §3.2 · p. 11Results
The algorithms have sublinear suboptimality upper bounds, the first general-OCE offline minimax lower bound is established, and the linear-function-approximation extension is described as the first provably efficient OCE algorithm in that setting.
Source: §1 · p. 3Takeaways & Limitations
The framework treats both major OCE formulations and characterizes learning difficulty in relation to risk sensitivity and utility functions.
Source: §1 · p. 3, §7 · p. 23The analysis assumes the utility function is Lipschitz on [−H, H], a regularity condition beyond the general OCE definition.
Source: §2.2 · p. 6
Abstract
from arXiv · showhide
Risk-sensitive reinforcement learning (RL) addresses decision-making under uncertainty and adverse outcomes. Learning risk-sensitive policies from fixed datasets is important when additional interaction with the environment is costly. Existing work on risk-sensitive RL focuses on online settings or specific risk measures, leaving a general theoretical understanding of its offline setting underdeveloped. In this work, we investigate efficient offline risk-sensitive RL using the optimized certainty equivalent (OCE), a general class of risk measures. We consider two formulations: dynamic-OCE RL, which applies OCE recursively at each step, and static-OCE RL, which applies a single OCE to the cumulative rewards. Under the tabular setting, we develop pessimistic value-iteration algorithms for both formulations and establish tight sublinear suboptimality bounds, explicitly capturing how risk sensitivity, encoded by utility functions, affects learning difficulty. Moreover, we establish minimax suboptimality lower bounds to characterize the problem's fundamental limits. To handle large state spaces, we further develop pessimistic least-squares value-iteration algorithms that incorporate the general OCE risk criterion into linear function approximation. We establish utility-dependent sublinear guarantees with explicit dependence on the feature dimension $d$. To our knowledge, we provide the first offline algorithms along with the first upper and lower suboptimality bounds for both dynamic- and static-OCE RL.
1 Introduction
Offline risk-sensitive RL lacks a general theory for OCE, despite the importance of learning from fixed datasets when further interaction is costly. This work develops algorithms and upper and lower bounds for dynamic and static OCE, and extends the framework to linear function approximation.
1 Introduction
- Existing offline risk-sensitive RL studies often focus on a single risk measure, while earlier general OCE formulations chiefly address online learning.OCE unifies measures including CVaR, entropic risk, and mean-variance.Source: §1 · p. 2
- The paper develops provably efficient offline algorithms for both dynamic-OCE and static-OCE RL, with sublinear upper bounds and a minimax lower bound for general OCE risk measures.The bounds characterize how risk sensitivity affects learning difficulty and apply to both formulations.Source: §1 · p. 3
- Linear function approximation extends the framework beyond tabular MDPs, with the paper claiming the first provably efficient OCE risk-sensitive RL algorithm in this setting.The introduction describes this extension as broadening the theory's relevance to large-scale applications.Source: §1 · p. 3
- The paper frames its contributions as a theoretical framework combining efficient offline algorithms, upper and lower bound analyses, and linear function approximation.The introduction also situates offline risk-sensitive learning in applications where further environment interaction can be costly.Source: §1 · pp. 2–3
1.1 Related Works
- Prior work includes online entropic, iterated-CVaR, dynamic-OCE, and static-OCE methods, while offline work includes entropic risk with linear function approximation.The cited offline entropic method does not address the more general OCE setting.Source: §1.1 · p. 4
2 Problem Setup
The setup formalizes offline learning with a fixed dataset and introduces OCE as a general risk measure under a utility regularity condition. It defines dynamic OCE through recursive evaluation and static OCE through a total-return objective represented with an augmented budget state.
2.1 Offline Reinforcement Learning
- Offline RL uses a fixed dataset generated by a behavior policy, and learning difficulty depends on how well that policy's state-action distribution covers the optimal policy.The single-policy concentrability coefficient captures this coverage dependence.Source: §2.1 · p. 5
2.2 Optimized Certainty Equivalent
- OCE unifies risk criteria such as CVaR, entropic risk, and mean-variance through utility choices, and the analysis assumes the utility is Lipschitz on [−H, H].The paper notes this regularity condition holds for the commonly used utilities it lists.Source: §2.2 · pp. 5–6
2.3 Dynamic-OCE RL
- Dynamic-OCE RL applies the OCE recursively from the horizon back to the initial step, yielding a modified Bellman equation.The formulation considers Markovian policies.Source: §2.3 · pp. 6–7
2.4 Static-OCE RL
- Static-OCE RL evaluates risk on total return and handles history-dependent optimal policies by augmenting state with a residual budget updated by subtracting each reward.The budget is discretized on a ς-net for practical computation.Source: §2.4 · pp. 7–8
- The setup seeks policies with small suboptimality for the dynamic and static offline objectives, including a discrete-budget version of the static objective.The static formulation optimizes over an initial budget in [0, H].Source: §2.4 · pp. 7–8
3 Risk-Sensitive Offline RL with OCE
This section develops pessimistic value-iteration algorithms for dynamic- and static-OCE offline RL and analyzes their suboptimality. The bounds reflect utility-dependent learning difficulty, while the static formulation additionally uses a budget state.
3.1 Dynamic-OCE Pessimistic Value Iteration
- DOCE-PVI estimates transitions and rewards, then uses an OCE-aware pessimistic Bellman update and a greedy policy for dynamic-OCE RL.Its uncertainty bonus incorporates a utility-dependent factor; when u(t) = t, the algorithm reduces to risk-neutral pessimistic value iteration.Source: §3.1 · pp. 8–9
- The dynamic-OCE bound has the same O(√(C*|S|/K)) dependence on coverage, state-space size, and sample size as comparable risk-neutral offline value-iteration results.Its utility-dependent error term reflects the risk preferences encoded by u, while retaining the K^-1/2 rate.Source: §3.1 · pp. 9–10
3.2 Static-OCE Pessimistic Value Iteration
- SOCE-PVI uses an augmented state with a residual budget that is updated using estimated rewards, making the learned policy Markovian on that augmented space.Static-OCE applies OCE once to total return, unlike dynamic-OCE's recursive application; the budget must be updated and discretized iteratively.Source: §3.2 · p. 11
- The discrete-budget static-OCE guarantee adds (1 + Lu)ς discretization error to the Bellman statistical error; the continuous-budget analysis incurs no discretization error.The theorem's main result concerns deterministic rewards; the stochastic-reward extension uses a Bellman update based on the joint law of (s′, r).Source: §3.2 · pp. 11–12
4 Information-Theoretic Lower Bounds
The section establishes minimax suboptimality lower bounds for offline risk-sensitive RL under general OCE, for both dynamic and static formulations. The bounds capture utility-dependent difficulty, and budget discretization preserves the lower-bound order.
4 Information-Theoretic Lower Bounds
- The lower bound is for general OCE risk measures, with the utility function u and choice of ρ specializing it to concrete risk measures.For static-OCE RL, budget discretization changes the lower bound by at most additive (1 + Lu)ς, preserving its order.Source: §4 · p. 13
- Theorem 8 gives a minimax lower bound for both dynamic- and static-OCE offline RL, with suboptimality depending on coverage, state-space size, horizon, and utility.The lower bound decays at rate K^-1/2 and is presented as the first lower bound for offline OCE-RL.Source: §4 · pp. 12–14
- The comparison with upper bounds is restricted to their common dependence on coverage, state-space size, and sample size, namely √(C*|S|/K).Comparisons with most prior risk-sensitive lower bounds are indicative rather than direct because they use different information and sampling structures.Source: §4 · p. 14
5 Linear Function Approximation for Offline RL with OCE
The section extends pessimistic offline OCE value iteration to linear MDPs, with separate algorithms for dynamic and static OCE. Their guarantees depend on feature dimension and utility sensitivity; the static method also incurs a budget-grid discretization error.
5 Linear Function Approximation for Offline RL with OCE
- The linear-MDP extension targets large state spaces where tabular suboptimality bounds can be large, using a feature representation with dimension d.The reward function and transition model both admit a linear structure in the assumed model.Source: §5 · p. 14
5.1 Dynamic-OCE Pessimistic Least-Squares Value Iteration
- DOCE-PLSVI applies linear approximation separately to reward and transition-related components of the dynamic-OCE Bellman update.The section introduces the linear-MDP setting, where reward and transition admit linear structure and tabular MDPs are a special case.Source: §5.1 · p. 14, §5 · p. 14
- The dynamic-OCE guarantee depends explicitly on utility sensitivity, recovers the risk-neutral case, and has an entropic-utility factor that grows exponentially with horizon.For risk-neutral utility, the bound is comparable to a linear-MDP guarantee under matched coverage and regularization assumptions.Source: §5.1 · p. 16
5.2 Static-OCE Pessimistic Least-Squares Value Iteration
- SOCE-PLSVI uses ridge-regression estimators under a linear-MDP assumption and augments the state with a budget that tracks reward history.The budget construction applies OCE once to cumulative rewards; implementation uses a grid and the guarantee accounts for its discretization.Source: §5.2 · pp. 16–18
- The static-OCE guarantee combines a feature-dimension-dependent continuous-budget statistical error with an additive (1 + Lu)ς grid-discretization error.Its bound also depends on utility sensitivity and the optimal initial budget; the risk-neutral specialization is comparable to offline risk-neutral RL under aligned assumptions.Source: §5.2 · p. 18
6 Theoretical Analysis
The analysis bounds suboptimality by controlling Bellman errors, using different arguments for dynamic and static OCE and for tabular versus linear-function settings. A constructed hard-instance family yields a minimax lower bound for both OCE formulations.
6.1 Analysis of the Tabular Setting
- Dynamic-OCE tabular analysis controls Bellman error with an OCE-reweighted transition kernel and utility-sensitive concentration, while static-OCE analysis uses an augmented budget state and a single expectation error.For static OCE, the grid-based guarantee adds (1 + Lu)ς to the continuous-budget guarantee.Source: §6.1 · pp. 19–20
- The static-OCE proof transfers a continuous-budget statistical guarantee to the grid-based algorithm, while dynamic OCE bounds a separate OCE estimation error.The dynamic analysis controls that error through the utility function and concentration, then sums the resulting bounds using the concentrability coefficient.Source: §6.1 · pp. 19–20
6.2 Analysis of the Lower Bound
- The constructed hard instances yield a minimax suboptimality lower bound for both dynamic and static OCE, with the same suboptimality expression on the instance.The absorbing-state construction makes the nontrivial OCE evaluation occur only once, allowing the same information-theoretic argument for both formulations.Source: §6.2 · p. 21
6.3 Analysis of the Function Approximation Setting
- In linear function approximation, Bellman-error control relies on ridge-regression estimation and feature-dependent analysis rather than tabular visitation counts.Dynamic OCE uses separate reward and utility-transformed continuation estimates; static OCE uses one regression and needs no auxiliary OCE optimizer or linearization argument.Source: §6.3 · pp. 21–23
7 Conclusion
The paper concludes with offline algorithms and upper and lower bounds for dynamic and static OCE, including linear-function extensions. Its discussion highlights that static OCE can require history-dependent policies, while dynamic and static formulations treat cumulative risk differently.
7 Conclusion
- The paper develops offline algorithms and suboptimality bounds for both OCE formulations, establishes a minimax lower bound, and extends the algorithms and upper bounds to linear function approximation.The conclusion frames these results as a response to prior work focused mainly on online settings or specific risk measures.Source: §7 · p. 23
A.1 An Auxiliary Property of OCE
- For a bounded positive random variable, optimizing OCE requires only a finite set of budget values rather than the entire budget domain.The auxiliary property is established for X in [0, M].Source: §A.1 · p. 25
A.2 Discussion of Static-OCE and augmented MDP
- In the CVaR example, a history-dependent policy achieves cumulative-reward CVaR 0.75, exceeding the 0.5 attained by every history-independent policy.The example illustrates that static-OCE optimal policies may be history-dependent in the original MDP.Source: §A.2 · p. 26
A.3 Comparison between Dynamic-OCE RL and Static-OCE RL
- Dynamic mean-variance OCE accounts for stagewise reward variances, whereas static OCE also accounts for covariance across time steps.The discussion says dynamic risk can be less stable and less interpretable than its static counterpart.Source: §A.3 · p. 27
A.4 Discussion on the discretization of b
The static-OCE budget is discretized for computational tractability, and the section bounds the resulting suboptimality error. The added error vanishes as the grid is refined.
A.4 Discussion on the discretization of b
- Discretizing the static-OCE budget makes the implementation computationally tractable when the optimal policy may depend on history.The budget is ideally continuous over [0, H], but the implementation uses a ς-net.Source: §A.4 · p. 28
- A stability assumption on the optimal initial budget supports a bound on the error induced by discretization.The section introduces the assumption before stating the discretization-error lemma.Source: §A.4 · p. 28
- The additional suboptimality from discretization is at most (1 + Lu)ς and vanishes as the grid is refined.The total gap is decomposed into the continuous-budget suboptimality gap and the additional discretization error.Source: §A.4 · pp. 28–29
B.1 Lemmas for Theorem 4
The dynamic-OCE analysis relates policy suboptimality to Bellman estimation error and algorithmic bonuses. Concentration bounds and recursive lemmas support the guarantees for the tabular and linear-function-approximation settings.
B.1 Lemmas for Theorem 4
- The dynamic-OCE Bellman operator and recursive lemmas relate value estimates to policy suboptimality.The section also defines a probability measure and a state-action distribution used in the analysis.Source: §B.1 · pp. 29–32
- On the stated event, suboptimality is controlled by Bellman estimation error, while the general bound depends on that error and the bonus term.The resulting suboptimality bound applies to both tabular and linear-function-approximation settings.Source: §B.1 · pp. 29, 33, 34
B.2 Proof of Theorem 4
- Lemmas 24 and 25 state inequalities for any δ ∈ (0, 1), state-action pair (s, a), and stage h, holding with probability at least 1 − δ; displayed bounds involve max{1, Nh(s, a)}.Source: §B.1 · pp. 34–35
B.3 Lemmas for Theorem 7
The static-OCE analysis uses a joint transition–reward model to bound Bellman estimation error and resulting suboptimality. It first treats a continuous budget, then accounts for the extra error from implementing a budget grid.
B.3 Lemmas for Theorem 7
- The stochastic-reward extension assumes access to a joint transition–reward model and uses an expectation over next state and reward in its Bellman update.When the reward is deterministic, this extension specializes to the deterministic-reward setting.Source: §B.3 · p. 37
- On the stated event, the static-OCE Bellman estimation error is nonnegative and at most twice the bonus Γh.The subsequent suboptimality bound for Algorithms 2 and 4 depends on the estimation error and bonus, in both tabular and linear-function-approximation settings.Source: §B.3 · pp. 39–40
B.4 Proof of Theorem 7
- The proof first analyzes the continuous-budget recursion independently of the grid, then adds at most (1 + Lu)ς to the suboptimality gap for the grid implementation.The concentration bound is combined with the suboptimality lemma to establish the continuous-budget claim.Source: §B.4 · pp. 41–42
Appendix C. Proofs for Section 4
The appendix constructs a flexible hard MDP to establish an information-theoretic lower bound shared by dynamic-OCE-PVI and static-OCE-PVI. The construction also encompasses several earlier hard instances.
Appendix C. Proofs for Section 4
- The construction has |S|+2 states, including two additional absorbing states named good and bad.The figure illustrates the transition dynamics for each regular state si.Source: Appendix C · pp. 42–43, Figure 2 · p. 43
- The hard MDP M† embeds several constructions from prior work, including those of Jin et al. (2021), Xu et al. (2023), and Xie et al. (2021).The cited special cases use a single regular state, a tree structure before the absorbing states, or a specified horizon configuration, respectively.Source: Appendix C · p. 43
- Dynamic-OCE-PVI and static-OCE-PVI share the same information-theoretic lower bound on the hard instance Ma*.In the absorbing-state setup, dynamic-OCE-PVI evaluates the true OCE only once at a deterministic time step.Source: Appendix C · p. 43
C.1 Lemmas for Theorem 8
The proof establishes that Algorithms 3 and 4 have matching suboptimality forms on a constructed hard MDP, with dynamic- and static-OCE formulations sharing the relevant value and suboptimality structure. Theorem 8’s argument does not require a differentiable utility or an interior maximizer.
C.1 Lemmas for Theorem 8
- Algorithms 3 and 4 have the same form of suboptimality gaps under the constructed hard MDP.The dynamic- and static-OCE settings also share the form of the values that induce those gaps.Source: §C.1 · pp. 44–45
C.2 Proof of Theorem 8
- Theorem 8’s argument requires neither a differentiable utility nor an interior maximizer.The proof uses a maximizer over the specified interval for its suboptimality expression.Source: §C.2 · p. 48
D.1 Lemmas for Theorem 9
These appendical results provide concentration and function-class bounds used in the proofs of Theorems 9 and 10. Theorem 9’s proof controls covering-number growth, while a separate joint transition–reward model extends the static linear analysis to stochastic rewards.
D.1 Lemmas for Theorem 9
- For dynamic-OCE concentration, the fixed-function error is conditionally zero-mean and [1 + (H − h)Lu]-sub-Gaussian.The function class uses a budget parameter b and bounded parameter norms.Source: §D.1 · pp. 48, 50
D.2 Proof of Theorem 9
- Theorem 9’s proof bounds the function-class covering contribution by a constant multiple of d^2ζ.The proof selects concentration parameters and uses Assumption 5 to bound the relevant function class uniformly over stages.Source: §D.2 · p. 54
D.3 Lemmas for Theorem 10
- The stochastic-reward extension models the joint pair (s′, r) linearly and estimates it from the empirical joint law.When rewards are deterministic, the argument reduces to the deterministic-reward case of Theorem 10.Source: §D.3 · p. 54
D.4 Proof of Theorem 10
Theorem 10’s proof first establishes a statistical bound for a continuous-budget recursion under the joint transition–reward model, then transfers it to the discrete-budget implementation. The appendix also supplies supporting concentration and covering-number lemmas.
D.4 Proof of Theorem 10
- The stochastic-reward proof uses the joint transition–reward law and reduces to the deterministic-reward case when rewards are deterministic.It establishes the bound for a continuous-budget recursion before transferring it to the grid implementation.Source: §D.4 · p. 57
- The discrete-budget statement adds an (1 + Lu)ς term to the continuous-budget statistical bound.The proof obtains the continuous-budget term first and applies Lemma 13 for the discrete-budget result.Source: §D.4 · p. 60
Appendix E. Other Supporting Lemmas
- The supporting lemmas assume conditionally zero-mean sub-Gaussian noise and give a Euclidean-ball covering-number bound.The concentration setup uses predictable feature vectors and a deterministic positive-definite initial matrix.Source: Appendix E · p. 60