Research map / Reinforcement learning / MDPs and planning
Approximate Bilevel Difference Convex Programming for Bayesian Risk 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 approximate bilevel difference convex programming (ABDCP) to solve infinite-horizon Bayesian risk MDPs offline, yielding finite state controller policies with lower and upper value bounds and convergence guarantees.
Problem
Infinite-horizon MDPs with unknown (epistemic) parameters estimated from data; distributionally robust MDPs are overly conservative and not time-consistent, and existing BR-MDP approximations only handle finite horizons without gap guarantees.
Approach
Reformulates the infinite-horizon BR-MDP (nested convex risk over Bayesian posteriors) as a bilevel difference convex program, approximates the continuous belief space with a finite posterior set using convex-combination interpolation, and iteratively adds reachable posteriors; the approximate value gives a lower bound and the induced finite state controller gives an upper bound.
Key results
- On path planning with N=10, ABDCP-CVaR (alpha=0.8) achieves the lowest expected cost of 66.02 versus 79.43 for DR-MDP and 82.59 for Nominal.
- ABDCP-CVaR (alpha=0.95) attains the lowest CVaR(0.95) cost of 75.67 at N=10, versus 81.64 for DR-MDP and 94.10 for Nominal.
- Running time per replication is about 2500-2600 s for ABDCP-CVaR versus about 62 s for DR-MDP and Nominal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CVaR (α=0.95) instead of expectation | ABDCP · Path planning (N=10) | CVaR cost (α=0.95): 85.72 -> 75.67 | Helped |
| Use CVaR (α=0.95) instead of expectation | ABDCP · Path planning (N=10) | expected cost: 70.06(0.51) -> 67.51(0.24) | Helped |
| Use CVaR (α=0.8) instead of expectation | ABDCP · Path planning (N=10) | expected cost: 70.06(0.51) -> 66.02(0.38) | Helped |
| Use CVaR (α=0.8) instead of expectation | ABDCP · Path planning (N=10) | CVaR cost (α=0.8): 82.06 -> 75.50 | Helped |
| Use CVaR (α=0.95) instead of expectation | ABDCP · Path planning (N=1000) | CVaR cost (α=0.95): 66.34 -> 66.14 | Helped |
| Use CVaR (α=0.95) instead of expectation | ABDCP · Path planning (N=1000) | expected cost: 64.15(0.05) -> 65.18(0.03) | Hurt |
| Use CVaR (α=0.8) instead of expectation | ABDCP · Path planning (N=1000) | expected cost: 64.15(0.05) -> 65.17(0.04) | Hurt |
| Use CVaR (α=0.8) instead of expectation | ABDCP · Path planning (N=1000) | CVaR cost (α=0.8): 65.97 -> 65.84 | Helped |
| Use ABDCP-CVaR (α=0.95) instead of Nominal | Path planning · Path planning (N=10) | CVaR cost (α=0.95): 94.10 -> 75.67 | Helped |
| Use ABDCP-CVaR (α=0.8) instead of DR-MDP | Path planning · Path planning (N=10) | expected cost: 79.43(0.15) -> 66.02(0.38) | Helped |
| Increase data size | Path planning · Path planning | expected cost: 70.06(0.51) -> 64.15(0.05) | Mixed |
| Increase CVaR risk level from α=0.8 to α=0.95 | ABDCP-CVaR · Path planning (N=10) | expected cost: 66.02(0.38) -> 67.51(0.24) | Hurt |
Surprising findings
- The expectation-risk variant (ABDCP-EXP, i.e., CALP) is faster but gives the least robustness at small data size.
- DR-MDP is overly conservative and has the smallest variability but worse mean cost than BR-MDP-based ABDCP.
Limitations
- Requires a finite parameter space; continuous parameters handled only via discretization.
- No iteration complexity analysis; the approximation depends on the posterior set size and the convergence threshold.
- Computational cost grows substantially (about 40x DR-MDP runtime) and no function approximation for scalability.
Experimental setup
Datasets: simulated historical traffic time and accident logs for path planning (N=10, N=1000)
Benchmarks: offline path planning on 10x10 grid multi-item inventory control
Metrics: expected cost CVaR cost at alpha=0.95 and 0.8 running time
Baselines: CALP DR-MDP Nominal (MLE)
Builds on: Bayesian risk MDP approximate linear programming for POMDPs disciplined convex-concave programming point-based value iteration
Closest papers by meaning
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.88)
- On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (NeurIPS 2026 · similarity 0.87)
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.87)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.87)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.86)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.86)
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.