Research map / Reinforcement learning / MDPs and planning
Flipping-based Policy for Chance-Constrained Markov Decision Processes
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 flipping-based (two-action randomized) policies for chance-constrained MDPs, proves their optimality via a Bellman-style and convexification argument, and shows CPO/PCPO-based training of such policies improves reward on Safety Gym.
Problem
Safe RL under joint chance constraints in CMDPs, where deterministic or standard stochastic policies can be suboptimal and joint chance constraints are hard to optimize directly.
Approach
A state-dependent flipping-based policy randomizes between two action candidates with a state-dependent probability; the paper proves such policies are optimal for CCMDPs and conservatively approximates joint chance constraints by expected cumulative safety constraints so that CPO/PCPO can train them by mixing two trained policies.
Key results
- In a numerical point-navigation example at 17% violation probability, the flipping-based policy achieved mean reward 1.8259 versus 0.8667 for the deterministic policy.
- On Safety Gym PointGoal2, flipping mixtures increase expected reward over CPO and PCPO at cost limits where the reward profile is convex, but not elsewhere.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a flipping-based policy instead of a deterministic policy | Policy for the numerical example · Numerical example | mean reward: 0.8667 -> 1.8259 | Helped |
| Use a flipping-based policy instead of a deterministic policy | Policy for the numerical example · Numerical example | violation probability: 17% -> 17% | No clear effect |
| Transform CPO into a flipping-based policy | CPO · Safety Gym PointGoal2 | expected cumulative reward | Helped |
| Transform PCPO into a flipping-based policy | PCPO · Safety Gym PointGoal2 | expected cumulative reward | Helped |
| Transform CPO or PCPO into a flipping-based policy | CPO and PCPO · Safety Gym PointGoal2 | expected cumulative reward | No clear effect |
Surprising findings
- Flipping-based policies do not help at intervals where the reward-vs-cost profile is not convex, so gains depend on the base algorithm's performance.
- Flipping-based policies produced broader confidence intervals in Safety Gym results.
Limitations
- Flip probability in the practical algorithm is not state-dependent, so the theoretical optimality is not fully achieved.
- Requires training multiple policies for different cost limits and selecting a combination.
- Results only for smooth (non-discontinuous) settings; theory has gaps for non-smooth functions.
Experimental setup
Datasets: Safety Gym PointGoal2 Safety Gym CarGoal2
Benchmarks: Safety Gym PointGoal2 Safety Gym CarGoal2
Metrics: expected cumulative reward expected cumulative cost
Baselines: CPO PCPO P3O CUP
Builds on: Constrained Policy Optimization PCPO OmniSafe
Closest papers by meaning
- Probabilistic Shielding for Safe Reinforcement Learning (AAAI 2025 · similarity 0.90)
- Long-Term Safe Reinforcement Learning with Binary Feedback (AAAI 2024 · similarity 0.90)
- Balance Reward and Safety Optimization for Safe Reinforcement Learning: A Perspective of Gradient Manipulation (AAAI 2024 · similarity 0.88)
- Embedding Safety into RL: A New Take on Trust Region Methods (ICML 2025 · similarity 0.88)
- A Provable Approach for End-to-End Safe Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration (AAAI 2024 · similarity 0.88)
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.