Research map / Reinforcement learning / MDPs and planning
Provably Efficient Partially Observable Risk-sensitive Reinforcement Learning with Hindsight Observation
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 Beta Vector Value Iteration (BVVI), a UCB-style algorithm for entropic risk-sensitive POMDPs with hindsight observation, and proves the first regret bound for this setting.
Problem
Regret and sample complexity of risk-sensitive reinforcement learning under the entropic risk measure in tabular POMDPs, which are generally intractable without extra structure.
Approach
Uses hindsight observation (hidden states revealed at episode end) to learn the model, a change-of-measure to a reference model with uniform emissions, risk beliefs and beta vectors to obtain a simplified Bellman recursion, and a belief-dependent bonus for optimistic exploration.
Key results
- Regret upper bound of order tilde-O((e^{|gamma|H}-1)/(|gamma|H) * H^{5/2} sqrt(K S^2 A O)) with probability 1-4delta, stated in the abstract as tilde-O with H^2 sqrt(KHS^2OA).
- Sample complexity K ~ (1/(eps^2 delta^2)) ((e^{|gamma|H}-1)/(|gamma|H))^2 H^5 S^2 O A ln(KHSOA/delta).
- Claims improvement over risk-neutral hindsight-free bound in S, A, H and matching the fully observable risk-sensitive bound up to H factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BVVI for risk-sensitive RL with hindsight observations | Partially observable episodic RL · Risk-sensitive POMDP with hindsight observations | regret upper bound | Helped |
| Use BVVI in the risk-neutral setting | Risk-neutral POMDP with hindsight observations · Risk-neutral setting | regret upper bound: our regret: \mathcal{\tilde{O}}\left(\frac{e^{\abs{\gamma } H}-1}{\abs{\gamma}H}H^\frac{5}{2}\sqrt{KS^2AO}\right); exist | Helped |
| Use BVVI in the completely observable setting | Risk-sensitive RL · Completely observable setting | regret upper bound: our regret: \tilde{O}\left(\frac{e^{|\gamma| H}-1}{|\gamma| H} \sqrt{K H^4 S^2 A}\right) | No clear effect |
Limitations
- Tabular setting only; function approximation left as future work.
- Regret bound has H-dependence (H^{5/2} or H^2 sqrt(H)) above the lower bound and the risk-neutral lower bound is only nearly matched.
- Relies on hindsight observation of hidden states, which is a strong assumption.
Experimental setup
Metrics: regret sample complexity
Baselines: Risk-sensitive RL regret bound for MDPs (Theorem C.1 of cited work) Fully observable entropic risk algorithm (algorithm 1 in cited work)
Builds on: UCB risk-sensitive belief (risk-sensitive POMDP literature) alpha-vector
Closest papers by meaning
- Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning (ICML 2024 · similarity 0.90)
- A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents (ICML 2025 · similarity 0.90)
- Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.89)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.89)
- Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight (ICLR 2024 · similarity 0.89)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.