Research map / Bandits and online learning / RL theory and MDPs

Online Learning in Risk Sensitive constrained MDP

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Regret bounds with function approximation

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a primal-dual value-iteration algorithm for online constrained MDPs with an entropic risk constraint, using an OCE representation with an augmented budget state and a truncated dual update, with sublinear regret and violation bounds.

Problem

Maximizing expected cumulative reward in a finite-horizon episodic MDP subject to an entropic risk constraint on cumulative utility, learned online without knowledge of transitions; standard primal-dual methods fail because strong duality and Markov optimality do not hold.

Approach

Rewrites the entropic risk via the Optimized Certainty Equivalent and augments the state with a continuous budget variable so a linear Bellman recursion applies; uses optimistic value iteration per Lagrangian with a truncated dual update capped at a threshold xi to handle the possible absence of strong duality.

Key results

• Algorithm achieves regret of Õ(Vg,max K^{3/4} + sqrt(H^4 S^2 A log(1/δ)) K^{3/4}) with high probability.
• Constraint violation bound Õ(Vg,max sqrt(H^3 S^2 A log(1/δ)) K^{3/4}), claimed as first sublinear result for risk-sensitive CMDP.
• Grid-world experiments with K=15,000 show the empirical risk rises to meet threshold B=2.2 and the dual variable stabilizes once feasible.

Measured effects reported in the paper

Surprising findings

• The optimal policy for an entropic-risk-constrained CMDP may not be Markovian, unlike the unconstrained entropic risk setting.
• Strong duality may fail for entropic risk constraints because the risk value is not linear in occupancy measure.

Limitations

• Regret and violation bounds scale as K^{3/4}, not the sqrt(K) of risk-neutral CMDPs.
• Relies on Assumption 3.2 (existence of a Markov optimal policy in augmented space), with Slater-type condition left for future work.
• Empirical evaluation limited to a small 5x5 grid-world.

Experimental setup

Datasets: simulated 5x5 grid-world

Benchmarks: 5x5 grid-world simulation

Metrics: regret constraint violation empirical reward empirical entropic risk

Builds on: Ghosh et al. 2022 (risk-neutral CMDP primal-dual regret) Wang et al. 2024 (augmented MDP for OCE risk measures) Jin et al. 2020 (Q-learning UCB / uniform concentration) Efroni et al. 2020 (primal-dual CMDP)

Closest papers by meaning

• Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization (ICLR 2025 · similarity 0.92)
• Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.91)
• Truly No-Regret Learning in Constrained MDPs (ICML 2024 · similarity 0.91)
• A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents (ICML 2025 · similarity 0.90)
• Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.90)
• Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.90)