Research map / Learning theory and algorithms / Combinatorial and search optimization
Efficient Constraint Generation for Stochastic Shortest Path Problems
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.
Introduces CG-iLAO*, a heuristic search algorithm for SSPs that reinterprets iLAO* as variable/constraint generation on the VI LP and adds a separation oracle so only violated (active) actions are added, ignoring inactive actions.
Problem
Solving Stochastic Shortest Path problems optimally wastes computation on Q-values of sub-optimal actions, since existing heuristic search methods (LRTDP, iLAO*) must consider all applicable actions in every Bellman backup.
Approach
Relates heuristic search to constraint generation in the LP encoding of value iteration and introduces an efficient separation oracle that tracks changes in V to add only violated action constraints, allowing inactive actions to be ignored during partial expansion while preserving optimality and epsilon-consistency.
Key results
- CG-iLAO* achieves the highest total coverage of 1300 instances with h-roc, versus 1202 for LRTDP and 1200 for iLAO*.
- CG-iLAO* solves problems up to 8x faster than LRTDP and up to 3x faster than iLAO* (speedups with h-roc).
- CG-iLAO* considers only 43-65% of iLAO*'s total actions and ignores up to 57% of them.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-roc | coverage: 1200 -> 1300 | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-LMcut | coverage: 990 -> 1030 | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-max | coverage: 600 -> 661 | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-roc | Q-values computed: 4× fewer Q-values | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-roc and equal Q-value budget | instances solved: 1149 -> 1300 | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-roc and equal Q-value budget | instances solved: 1052 -> 1300 | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · PARC-R with h-roc | runtime speedup over LRTDP: 2.0--8.4 | Helped |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · PARC-N with h-roc | runtime speedup over LRTDP: 0.7--0.9 | Hurt |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · ExBW with h-roc | runtime speedup over LRTDP: 0.9--2.9 | Mixed |
| Use constraint generation to add only greedy or subsequently violated actions instead of expanding all applicable actions | iLAO* · All domains with h-roc | actions considered relative to iLAO*: 43--65% | Helped |
| Use h-roc instead of h-max | CG-iLAO* · All domains | coverage: 661 -> 1300 | Helped |
| Use h-LMcut instead of h-max | CG-iLAO* · All domains | coverage: 661 -> 1030 | Helped |
Surprising findings
- The value function of CG-iLAO* can decrease during execution even with a monotonic heuristic, unlike other Bellman-backup algorithms.
- With the least informative heuristic h-max, LRTDP is slightly more Q-value efficient than CG-iLAO*.
Limitations
- Gains depend on heuristic informativeness; with weak heuristics (h-max) the advantage disappears or reverses.
- Value function may decrease during search, requiring additional bookkeeping; the approach is evaluated only on SSP planning benchmarks.
- Separation oracle adds Q-value computations overhead.
Experimental setup
Datasets: Triangle Tire World with Head-start Probabilistic Blocks World Exploding Blocks World Probabilistic PARC Printer
Benchmarks: Triangle Tire World with Head-start Probabilistic Blocks World Exploding Blocks World Probabilistic PARC Printer
Metrics: coverage CPU time number of Q-value computations speedup fraction of actions ignored
Baselines: iLAO* LRTDP FTVI
Builds on: iLAO* LRTDP FTVI value iteration constraint generation
Closest papers by meaning
- General Error Bounds in Heuristic Search Algorithms for Stochastic Shortest Path Problems (AAAI 2016 · similarity 0.89)
- Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems (NeurIPS 2022 · similarity 0.87)
- Near-optimal Regret Bounds for Stochastic Shortest Path (ICML 2020 · similarity 0.87)
- Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret (NeurIPS 2021 · similarity 0.87)
- Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path (NeurIPS 2021 · similarity 0.87)
- Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems (NeurIPS 2025 · similarity 0.84)
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.